LLVM  13.0.0git
LiveRangeCalc.cpp
Go to the documentation of this file.
1 //===- LiveRangeCalc.cpp - Calculate live ranges -------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Implementation of the LiveRangeCalc class.
10 //
11 //===----------------------------------------------------------------------===//
12 
14 #include "llvm/ADT/BitVector.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/ADT/SmallVector.h"
27 #include "llvm/MC/LaneBitmask.h"
30 #include <algorithm>
31 #include <cassert>
32 #include <iterator>
33 #include <tuple>
34 #include <utility>
35 
36 using namespace llvm;
37 
38 #define DEBUG_TYPE "regalloc"
39 
40 // Reserve an address that indicates a value that is known to be "undef".
41 static VNInfo UndefVNI(0xbad, SlotIndex());
42 
44  unsigned NumBlocks = MF->getNumBlockIDs();
45  Seen.clear();
46  Seen.resize(NumBlocks);
47  EntryInfos.clear();
48  Map.resize(NumBlocks);
49 }
50 
52  SlotIndexes *SI,
54  VNInfo::Allocator *VNIA) {
55  MF = mf;
56  MRI = &MF->getRegInfo();
57  Indexes = SI;
58  DomTree = MDT;
59  Alloc = VNIA;
61  LiveIn.clear();
62 }
63 
64 void LiveRangeCalc::updateFromLiveIns() {
65  LiveRangeUpdater Updater;
66  for (const LiveInBlock &I : LiveIn) {
67  if (!I.DomNode)
68  continue;
69  MachineBasicBlock *MBB = I.DomNode->getBlock();
70  assert(I.Value && "No live-in value found");
71  SlotIndex Start, End;
72  std::tie(Start, End) = Indexes->getMBBRange(MBB);
73 
74  if (I.Kill.isValid())
75  // Value is killed inside this block.
76  End = I.Kill;
77  else {
78  // The value is live-through, update LiveOut as well.
79  // Defer the Domtree lookup until it is needed.
80  assert(Seen.test(MBB->getNumber()));
81  Map[MBB] = LiveOutPair(I.Value, nullptr);
82  }
83  Updater.setDest(&I.LR);
84  Updater.add(Start, End, I.Value);
85  }
86  LiveIn.clear();
87 }
88 
89 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
90  ArrayRef<SlotIndex> Undefs) {
91  assert(Use.isValid() && "Invalid SlotIndex");
92  assert(Indexes && "Missing SlotIndexes");
93  assert(DomTree && "Missing dominator tree");
94 
95  MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
96  assert(UseMBB && "No MBB at Use");
97 
98  // Is there a def in the same MBB we can extend?
99  auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
100  if (EP.first != nullptr || EP.second)
101  return;
102 
103  // Find the single reaching def, or determine if Use is jointly dominated by
104  // multiple values, and we may need to create even more phi-defs to preserve
105  // VNInfo SSA form. Perform a search for all predecessor blocks where we
106  // know the dominating VNInfo.
107  if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
108  return;
109 
110  // When there were multiple different values, we may need new PHIs.
111  calculateValues();
112 }
113 
114 // This function is called by a client after using the low-level API to add
115 // live-out and live-in blocks. The unique value optimization is not
116 // available, SplitEditor::transferValues handles that case directly anyway.
118  assert(Indexes && "Missing SlotIndexes");
119  assert(DomTree && "Missing dominator tree");
120  updateSSA();
121  updateFromLiveIns();
122 }
123 
124 bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
125  MachineBasicBlock &MBB, BitVector &DefOnEntry,
126  BitVector &UndefOnEntry) {
127  unsigned BN = MBB.getNumber();
128  if (DefOnEntry[BN])
129  return true;
130  if (UndefOnEntry[BN])
131  return false;
132 
133  auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
134  for (MachineBasicBlock *S : B.successors())
135  DefOnEntry[S->getNumber()] = true;
136  DefOnEntry[BN] = true;
137  return true;
138  };
139 
140  SetVector<unsigned> WorkList;
141  // Checking if the entry of MBB is reached by some def: add all predecessors
142  // that are potentially defined-on-exit to the work list.
144  WorkList.insert(P->getNumber());
145 
146  for (unsigned i = 0; i != WorkList.size(); ++i) {
147  // Determine if the exit from the block is reached by some def.
148  unsigned N = WorkList[i];
150  if (Seen[N]) {
151  const LiveOutPair &LOB = Map[&B];
152  if (LOB.first != nullptr && LOB.first != &UndefVNI)
153  return MarkDefined(B);
154  }
155  SlotIndex Begin, End;
156  std::tie(Begin, End) = Indexes->getMBBRange(&B);
157  // Treat End as not belonging to B.
158  // If LR has a segment S that starts at the next block, i.e. [End, ...),
159  // std::upper_bound will return the segment following S. Instead,
160  // S should be treated as the first segment that does not overlap B.
161  LiveRange::iterator UB = upper_bound(LR, End.getPrevSlot());
162  if (UB != LR.begin()) {
163  LiveRange::Segment &Seg = *std::prev(UB);
164  if (Seg.end > Begin) {
165  // There is a segment that overlaps B. If the range is not explicitly
166  // undefined between the end of the segment and the end of the block,
167  // treat the block as defined on exit. If it is, go to the next block
168  // on the work list.
169  if (LR.isUndefIn(Undefs, Seg.end, End))
170  continue;
171  return MarkDefined(B);
172  }
173  }
174 
175  // No segment overlaps with this block. If this block is not defined on
176  // entry, or it undefines the range, do not process its predecessors.
177  if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
178  UndefOnEntry[N] = true;
179  continue;
180  }
181  if (DefOnEntry[N])
182  return MarkDefined(B);
183 
184  // Still don't know: add all predecessors to the work list.
185  for (MachineBasicBlock *P : B.predecessors())
186  WorkList.insert(P->getNumber());
187  }
188 
189  UndefOnEntry[BN] = true;
190  return false;
191 }
192 
193 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
194  SlotIndex Use, unsigned PhysReg,
195  ArrayRef<SlotIndex> Undefs) {
196  unsigned UseMBBNum = UseMBB.getNumber();
197 
198  // Block numbers where LR should be live-in.
199  SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
200 
201  // Remember if we have seen more than one value.
202  bool UniqueVNI = true;
203  VNInfo *TheVNI = nullptr;
204 
205  bool FoundUndef = false;
206 
207  // Using Seen as a visited set, perform a BFS for all reaching defs.
208  for (unsigned i = 0; i != WorkList.size(); ++i) {
209  MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
210 
211 #ifndef NDEBUG
212  if (MBB->pred_empty()) {
213  MBB->getParent()->verify();
214  errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())
215  << " does not have a corresponding definition on every path:\n";
216  const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
217  if (MI != nullptr)
218  errs() << Use << " " << *MI;
219  report_fatal_error("Use not jointly dominated by defs.");
220  }
221 
222  if (Register::isPhysicalRegister(PhysReg) && !MBB->isLiveIn(PhysReg)) {
223  MBB->getParent()->verify();
225  errs() << "The register " << printReg(PhysReg, TRI)
226  << " needs to be live in to " << printMBBReference(*MBB)
227  << ", but is missing from the live-in list.\n";
228  report_fatal_error("Invalid global physical register");
229  }
230 #endif
231  FoundUndef |= MBB->pred_empty();
232 
233  for (MachineBasicBlock *Pred : MBB->predecessors()) {
234  // Is this a known live-out block?
235  if (Seen.test(Pred->getNumber())) {
236  if (VNInfo *VNI = Map[Pred].first) {
237  if (TheVNI && TheVNI != VNI)
238  UniqueVNI = false;
239  TheVNI = VNI;
240  }
241  continue;
242  }
243 
244  SlotIndex Start, End;
245  std::tie(Start, End) = Indexes->getMBBRange(Pred);
246 
247  // First time we see Pred. Try to determine the live-out value, but set
248  // it as null if Pred is live-through with an unknown value.
249  auto EP = LR.extendInBlock(Undefs, Start, End);
250  VNInfo *VNI = EP.first;
251  FoundUndef |= EP.second;
252  setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
253  if (VNI) {
254  if (TheVNI && TheVNI != VNI)
255  UniqueVNI = false;
256  TheVNI = VNI;
257  }
258  if (VNI || EP.second)
259  continue;
260 
261  // No, we need a live-in value for Pred as well
262  if (Pred != &UseMBB)
263  WorkList.push_back(Pred->getNumber());
264  else
265  // Loopback to UseMBB, so value is really live through.
266  Use = SlotIndex();
267  }
268  }
269 
270  LiveIn.clear();
271  FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
272  if (!Undefs.empty() && FoundUndef)
273  UniqueVNI = false;
274 
275  // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
276  // neither require it. Skip the sorting overhead for small updates.
277  if (WorkList.size() > 4)
278  array_pod_sort(WorkList.begin(), WorkList.end());
279 
280  // If a unique reaching def was found, blit in the live ranges immediately.
281  if (UniqueVNI) {
282  assert(TheVNI != nullptr && TheVNI != &UndefVNI);
283  LiveRangeUpdater Updater(&LR);
284  for (unsigned BN : WorkList) {
285  SlotIndex Start, End;
286  std::tie(Start, End) = Indexes->getMBBRange(BN);
287  // Trim the live range in UseMBB.
288  if (BN == UseMBBNum && Use.isValid())
289  End = Use;
290  else
291  Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
292  Updater.add(Start, End, TheVNI);
293  }
294  return true;
295  }
296 
297  // Prepare the defined/undefined bit vectors.
299  bool DidInsert;
300  std::tie(Entry, DidInsert) = EntryInfos.insert(
301  std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
302  if (DidInsert) {
303  // Initialize newly inserted entries.
304  unsigned N = MF->getNumBlockIDs();
305  Entry->second.first.resize(N);
306  Entry->second.second.resize(N);
307  }
308  BitVector &DefOnEntry = Entry->second.first;
309  BitVector &UndefOnEntry = Entry->second.second;
310 
311  // Multiple values were found, so transfer the work list to the LiveIn array
312  // where UpdateSSA will use it as a work list.
313  LiveIn.reserve(WorkList.size());
314  for (unsigned BN : WorkList) {
316  if (!Undefs.empty() &&
317  !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
318  continue;
319  addLiveInBlock(LR, DomTree->getNode(MBB));
320  if (MBB == &UseMBB)
321  LiveIn.back().Kill = Use;
322  }
323 
324  return false;
325 }
326 
327 // This is essentially the same iterative algorithm that SSAUpdater uses,
328 // except we already have a dominator tree, so we don't have to recompute it.
329 void LiveRangeCalc::updateSSA() {
330  assert(Indexes && "Missing SlotIndexes");
331  assert(DomTree && "Missing dominator tree");
332 
333  // Interate until convergence.
334  bool Changed;
335  do {
336  Changed = false;
337  // Propagate live-out values down the dominator tree, inserting phi-defs
338  // when necessary.
339  for (LiveInBlock &I : LiveIn) {
340  MachineDomTreeNode *Node = I.DomNode;
341  // Skip block if the live-in value has already been determined.
342  if (!Node)
343  continue;
344  MachineBasicBlock *MBB = Node->getBlock();
345  MachineDomTreeNode *IDom = Node->getIDom();
346  LiveOutPair IDomValue;
347 
348  // We need a live-in value to a block with no immediate dominator?
349  // This is probably an unreachable block that has survived somehow.
350  bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
351 
352  // IDom dominates all of our predecessors, but it may not be their
353  // immediate dominator. Check if any of them have live-out values that are
354  // properly dominated by IDom. If so, we need a phi-def here.
355  if (!needPHI) {
356  IDomValue = Map[IDom->getBlock()];
357 
358  // Cache the DomTree node that defined the value.
359  if (IDomValue.first && IDomValue.first != &UndefVNI &&
360  !IDomValue.second) {
361  Map[IDom->getBlock()].second = IDomValue.second =
362  DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
363  }
364 
365  for (MachineBasicBlock *Pred : MBB->predecessors()) {
366  LiveOutPair &Value = Map[Pred];
367  if (!Value.first || Value.first == IDomValue.first)
368  continue;
369  if (Value.first == &UndefVNI) {
370  needPHI = true;
371  break;
372  }
373 
374  // Cache the DomTree node that defined the value.
375  if (!Value.second)
376  Value.second =
377  DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
378 
379  // This predecessor is carrying something other than IDomValue.
380  // It could be because IDomValue hasn't propagated yet, or it could be
381  // because MBB is in the dominance frontier of that value.
382  if (DomTree->dominates(IDom, Value.second)) {
383  needPHI = true;
384  break;
385  }
386  }
387  }
388 
389  // The value may be live-through even if Kill is set, as can happen when
390  // we are called from extendRange. In that case LiveOutSeen is true, and
391  // LiveOut indicates a foreign or missing value.
392  LiveOutPair &LOP = Map[MBB];
393 
394  // Create a phi-def if required.
395  if (needPHI) {
396  Changed = true;
397  assert(Alloc && "Need VNInfo allocator to create PHI-defs");
398  SlotIndex Start, End;
399  std::tie(Start, End) = Indexes->getMBBRange(MBB);
400  LiveRange &LR = I.LR;
401  VNInfo *VNI = LR.getNextValue(Start, *Alloc);
402  I.Value = VNI;
403  // This block is done, we know the final value.
404  I.DomNode = nullptr;
405 
406  // Add liveness since updateFromLiveIns now skips this node.
407  if (I.Kill.isValid()) {
408  if (VNI)
409  LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
410  } else {
411  if (VNI)
412  LR.addSegment(LiveInterval::Segment(Start, End, VNI));
413  LOP = LiveOutPair(VNI, Node);
414  }
415  } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
416  // No phi-def here. Remember incoming value.
417  I.Value = IDomValue.first;
418 
419  // If the IDomValue is killed in the block, don't propagate through.
420  if (I.Kill.isValid())
421  continue;
422 
423  // Propagate IDomValue if it isn't killed:
424  // MBB is live-out and doesn't define its own value.
425  if (LOP.first == IDomValue.first)
426  continue;
427  Changed = true;
428  LOP = IDomValue;
429  }
430  }
431  } while (Changed);
432 }
433 
435  ArrayRef<SlotIndex> Defs,
436  const SlotIndexes &Indexes) {
437  const MachineFunction &MF = *MBB->getParent();
438  BitVector DefBlocks(MF.getNumBlockIDs());
439  for (SlotIndex I : Defs)
440  DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());
441 
442  SetVector<unsigned> PredQueue;
443  PredQueue.insert(MBB->getNumber());
444  for (unsigned i = 0; i != PredQueue.size(); ++i) {
445  unsigned BN = PredQueue[i];
446  if (DefBlocks[BN])
447  return true;
448  const MachineBasicBlock *B = MF.getBlockNumbered(BN);
449  for (const MachineBasicBlock *P : B->predecessors())
450  PredQueue.insert(P->getNumber());
451  }
452  return false;
453 }
i
i
Definition: README.txt:29
llvm::array_pod_sort
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1381
llvm::SlotIndexes::getMBBRange
const std::pair< SlotIndex, SlotIndex > & getMBBRange(unsigned Num) const
Return the (start,end) range of the given basic block number.
Definition: SlotIndexes.h:455
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
MachineInstr.h
llvm
Definition: AllocatorList.h:23
llvm::upper_bound
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1605
llvm::MachineBasicBlock::isLiveIn
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Definition: MachineBasicBlock.cpp:574
LiveRangeCalc.h
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:343
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:327
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::SmallVector< unsigned, 16 >
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:118
ErrorHandling.h
llvm::LiveRangeCalc::extend
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
Definition: LiveRangeCalc.cpp:89
llvm::MachineRegisterInfo::getTargetRegisterInfo
const TargetRegisterInfo * getTargetRegisterInfo() const
Definition: MachineRegisterInfo.h:153
llvm::LiveRange::Segment
This represents a simple continuous liveness interval for a value.
Definition: LiveInterval.h:162
MachineBasicBlock.h
llvm::MachineFunction::getNumBlockIDs
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Definition: MachineFunction.h:685
UndefVNI
static VNInfo UndefVNI(0xbad, SlotIndex())
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:231
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:333
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:892
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:109
STLExtras.h
llvm::LiveRangeCalc::calculateValues
void calculateValues()
calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock.
Definition: LiveRangeCalc.cpp:117
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
MachineRegisterInfo.h
llvm::LiveRange::extendInBlock
std::pair< VNInfo *, bool > extendInBlock(ArrayRef< SlotIndex > Undefs, SlotIndex StartIdx, SlotIndex Kill)
Attempt to extend a value defined after StartIdx to include Use.
Definition: LiveInterval.cpp:564
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:568
llvm::SetVector::begin
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
llvm::LiveRange::begin
iterator begin()
Definition: LiveInterval.h:215
llvm::LiveRange::addSegment
iterator addSegment(Segment S)
Add the specified Segment to this range, merging segments as appropriate.
Definition: LiveInterval.cpp:548
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
SI
@ SI
Definition: SIInstrInfo.cpp:7463
llvm::LiveRangeUpdater
Helper class for performant LiveRange bulk updates.
Definition: LiveInterval.h:928
llvm::LiveRangeCalc::resetLiveOutMap
void resetLiveOutMap()
Reset Map and Seen fields.
Definition: LiveRangeCalc.cpp:43
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::report_fatal_error
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
BitVector.h
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:314
llvm::BitVector
Definition: BitVector.h:74
llvm::MachineFunction::verify
bool verify(Pass *p=nullptr, const char *Banner=nullptr, bool AbortOnError=true) const
Run the current MachineFunction through the machine code verifier, useful for debugger use.
Definition: MachineVerifier.cpp:321
llvm::LiveRangeUpdater::setDest
void setDest(LiveRange *lr)
Select a different destination live range.
Definition: LiveInterval.h:961
llvm::SlotIndexes::getInstructionFromIndex
MachineInstr * getInstructionFromIndex(SlotIndex index) const
Returns the instruction for the given index, or null if the given index has no instruction associated...
Definition: SlotIndexes.h:403
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::SlotIndexes::getMBBStartIdx
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:466
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:111
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::DomTreeNodeBase::getBlock
NodeT * getBlock() const
Definition: GenericDomTree.h:88
llvm::LiveRangeCalc::addLiveInBlock
void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())
addLiveInBlock - Add a block with an unknown live-in value.
Definition: LiveRangeCalc.h:244
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::MachineDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: MachineDominators.h:163
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LiveRange::getNextValue
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:323
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:225
llvm::SlotIndexes::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:514
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:349
llvm::MachineBasicBlock::pred_empty
bool pred_empty() const
Definition: MachineBasicBlock.h:331
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::MachineBasicBlock::getNumber
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
Definition: MachineBasicBlock.h:969
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
llvm::LiveRange::Segment::end
SlotIndex end
Definition: LiveInterval.h:164
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LiveRangeCalc::isJointlyDominated
static LLVM_ATTRIBUTE_UNUSED bool isJointlyDominated(const MachineBasicBlock *MBB, ArrayRef< SlotIndex > Defs, const SlotIndexes &Indexes)
A diagnostic function to check if the end of the block MBB is jointly dominated by the blocks corresp...
Definition: LiveRangeCalc.cpp:434
llvm::MachineFunction::getBlockNumbered
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Definition: MachineFunction.h:675
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:447
llvm::LiveRange::iterator
Segments::iterator iterator
Definition: LiveInterval.h:212
llvm::LiveRangeUpdater::add
void add(LiveRange::Segment)
Add a segment to LR and coalesce when possible, just like LR.addSegment().
Definition: LiveInterval.cpp:1179
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
LiveInterval.h
llvm::SetVector::end
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
llvm::DenseMapBase< DenseMap< LiveRange *, std::pair< BitVector, BitVector >, DenseMapInfo< LiveRange * >, llvm::detail::DenseMapPair< LiveRange *, std::pair< BitVector, BitVector > > >, LiveRange *, std::pair< BitVector, BitVector >, DenseMapInfo< LiveRange * >, llvm::detail::DenseMapPair< LiveRange *, std::pair< BitVector, BitVector > > >::iterator
DenseMapIterator< LiveRange *, std::pair< BitVector, BitVector >, DenseMapInfo< LiveRange * >, llvm::detail::DenseMapPair< LiveRange *, std::pair< BitVector, BitVector > > > iterator
Definition: DenseMap.h:70
SmallVector.h
N
#define N
LaneBitmask.h
llvm::LiveRangeCalc::reset
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
Definition: LiveRangeCalc.cpp:51
MachineOperand.h
llvm::LiveRangeCalc::setLiveOutValue
void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
Definition: LiveRangeCalc.h:230
SlotIndexes.h
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
MachineFunction.h
llvm::printReg
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Definition: TargetRegisterInfo.cpp:110
llvm::LiveRange::isUndefIn
bool isUndefIn(ArrayRef< SlotIndex > Undefs, SlotIndex Begin, SlotIndex End) const
Returns true if there is an explicit "undef" between Begin End.
Definition: LiveInterval.h:599
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::IndexedMap::resize
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:59
TargetRegisterInfo.h
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
MachineDominators.h