LLVM  15.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"
28 #include <algorithm>
29 #include <cassert>
30 #include <iterator>
31 #include <tuple>
32 #include <utility>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "regalloc"
37 
38 // Reserve an address that indicates a value that is known to be "undef".
39 static VNInfo UndefVNI(0xbad, SlotIndex());
40 
42  unsigned NumBlocks = MF->getNumBlockIDs();
43  Seen.clear();
44  Seen.resize(NumBlocks);
45  EntryInfos.clear();
46  Map.resize(NumBlocks);
47 }
48 
50  SlotIndexes *SI,
52  VNInfo::Allocator *VNIA) {
53  MF = mf;
54  MRI = &MF->getRegInfo();
55  Indexes = SI;
56  DomTree = MDT;
57  Alloc = VNIA;
59  LiveIn.clear();
60 }
61 
62 void LiveRangeCalc::updateFromLiveIns() {
63  LiveRangeUpdater Updater;
64  for (const LiveInBlock &I : LiveIn) {
65  if (!I.DomNode)
66  continue;
67  MachineBasicBlock *MBB = I.DomNode->getBlock();
68  assert(I.Value && "No live-in value found");
69  SlotIndex Start, End;
70  std::tie(Start, End) = Indexes->getMBBRange(MBB);
71 
72  if (I.Kill.isValid())
73  // Value is killed inside this block.
74  End = I.Kill;
75  else {
76  // The value is live-through, update LiveOut as well.
77  // Defer the Domtree lookup until it is needed.
78  assert(Seen.test(MBB->getNumber()));
79  Map[MBB] = LiveOutPair(I.Value, nullptr);
80  }
81  Updater.setDest(&I.LR);
82  Updater.add(Start, End, I.Value);
83  }
84  LiveIn.clear();
85 }
86 
87 void LiveRangeCalc::extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
88  ArrayRef<SlotIndex> Undefs) {
89  assert(Use.isValid() && "Invalid SlotIndex");
90  assert(Indexes && "Missing SlotIndexes");
91  assert(DomTree && "Missing dominator tree");
92 
93  MachineBasicBlock *UseMBB = Indexes->getMBBFromIndex(Use.getPrevSlot());
94  assert(UseMBB && "No MBB at Use");
95 
96  // Is there a def in the same MBB we can extend?
97  auto EP = LR.extendInBlock(Undefs, Indexes->getMBBStartIdx(UseMBB), Use);
98  if (EP.first != nullptr || EP.second)
99  return;
100 
101  // Find the single reaching def, or determine if Use is jointly dominated by
102  // multiple values, and we may need to create even more phi-defs to preserve
103  // VNInfo SSA form. Perform a search for all predecessor blocks where we
104  // know the dominating VNInfo.
105  if (findReachingDefs(LR, *UseMBB, Use, PhysReg, Undefs))
106  return;
107 
108  // When there were multiple different values, we may need new PHIs.
109  calculateValues();
110 }
111 
112 // This function is called by a client after using the low-level API to add
113 // live-out and live-in blocks. The unique value optimization is not
114 // available, SplitEditor::transferValues handles that case directly anyway.
116  assert(Indexes && "Missing SlotIndexes");
117  assert(DomTree && "Missing dominator tree");
118  updateSSA();
119  updateFromLiveIns();
120 }
121 
122 bool LiveRangeCalc::isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
123  MachineBasicBlock &MBB, BitVector &DefOnEntry,
124  BitVector &UndefOnEntry) {
125  unsigned BN = MBB.getNumber();
126  if (DefOnEntry[BN])
127  return true;
128  if (UndefOnEntry[BN])
129  return false;
130 
131  auto MarkDefined = [BN, &DefOnEntry](MachineBasicBlock &B) -> bool {
132  for (MachineBasicBlock *S : B.successors())
133  DefOnEntry[S->getNumber()] = true;
134  DefOnEntry[BN] = true;
135  return true;
136  };
137 
138  SetVector<unsigned> WorkList;
139  // Checking if the entry of MBB is reached by some def: add all predecessors
140  // that are potentially defined-on-exit to the work list.
142  WorkList.insert(P->getNumber());
143 
144  for (unsigned i = 0; i != WorkList.size(); ++i) {
145  // Determine if the exit from the block is reached by some def.
146  unsigned N = WorkList[i];
148  if (Seen[N]) {
149  const LiveOutPair &LOB = Map[&B];
150  if (LOB.first != nullptr && LOB.first != &UndefVNI)
151  return MarkDefined(B);
152  }
153  SlotIndex Begin, End;
154  std::tie(Begin, End) = Indexes->getMBBRange(&B);
155  // Treat End as not belonging to B.
156  // If LR has a segment S that starts at the next block, i.e. [End, ...),
157  // std::upper_bound will return the segment following S. Instead,
158  // S should be treated as the first segment that does not overlap B.
159  LiveRange::iterator UB = upper_bound(LR, End.getPrevSlot());
160  if (UB != LR.begin()) {
161  LiveRange::Segment &Seg = *std::prev(UB);
162  if (Seg.end > Begin) {
163  // There is a segment that overlaps B. If the range is not explicitly
164  // undefined between the end of the segment and the end of the block,
165  // treat the block as defined on exit. If it is, go to the next block
166  // on the work list.
167  if (LR.isUndefIn(Undefs, Seg.end, End))
168  continue;
169  return MarkDefined(B);
170  }
171  }
172 
173  // No segment overlaps with this block. If this block is not defined on
174  // entry, or it undefines the range, do not process its predecessors.
175  if (UndefOnEntry[N] || LR.isUndefIn(Undefs, Begin, End)) {
176  UndefOnEntry[N] = true;
177  continue;
178  }
179  if (DefOnEntry[N])
180  return MarkDefined(B);
181 
182  // Still don't know: add all predecessors to the work list.
183  for (MachineBasicBlock *P : B.predecessors())
184  WorkList.insert(P->getNumber());
185  }
186 
187  UndefOnEntry[BN] = true;
188  return false;
189 }
190 
191 bool LiveRangeCalc::findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB,
192  SlotIndex Use, unsigned PhysReg,
193  ArrayRef<SlotIndex> Undefs) {
194  unsigned UseMBBNum = UseMBB.getNumber();
195 
196  // Block numbers where LR should be live-in.
197  SmallVector<unsigned, 16> WorkList(1, UseMBBNum);
198 
199  // Remember if we have seen more than one value.
200  bool UniqueVNI = true;
201  VNInfo *TheVNI = nullptr;
202 
203  bool FoundUndef = false;
204 
205  // Using Seen as a visited set, perform a BFS for all reaching defs.
206  for (unsigned i = 0; i != WorkList.size(); ++i) {
207  MachineBasicBlock *MBB = MF->getBlockNumbered(WorkList[i]);
208 
209 #ifndef NDEBUG
210  if (MBB->pred_empty()) {
211  MBB->getParent()->verify();
212  errs() << "Use of " << printReg(PhysReg, MRI->getTargetRegisterInfo())
213  << " does not have a corresponding definition on every path:\n";
214  const MachineInstr *MI = Indexes->getInstructionFromIndex(Use);
215  if (MI != nullptr)
216  errs() << Use << " " << *MI;
217  report_fatal_error("Use not jointly dominated by defs.");
218  }
219 
220  if (Register::isPhysicalRegister(PhysReg) && !MBB->isLiveIn(PhysReg)) {
221  MBB->getParent()->verify();
223  errs() << "The register " << printReg(PhysReg, TRI)
224  << " needs to be live in to " << printMBBReference(*MBB)
225  << ", but is missing from the live-in list.\n";
226  report_fatal_error("Invalid global physical register");
227  }
228 #endif
229  FoundUndef |= MBB->pred_empty();
230 
231  for (MachineBasicBlock *Pred : MBB->predecessors()) {
232  // Is this a known live-out block?
233  if (Seen.test(Pred->getNumber())) {
234  if (VNInfo *VNI = Map[Pred].first) {
235  if (TheVNI && TheVNI != VNI)
236  UniqueVNI = false;
237  TheVNI = VNI;
238  }
239  continue;
240  }
241 
242  SlotIndex Start, End;
243  std::tie(Start, End) = Indexes->getMBBRange(Pred);
244 
245  // First time we see Pred. Try to determine the live-out value, but set
246  // it as null if Pred is live-through with an unknown value.
247  auto EP = LR.extendInBlock(Undefs, Start, End);
248  VNInfo *VNI = EP.first;
249  FoundUndef |= EP.second;
250  setLiveOutValue(Pred, EP.second ? &UndefVNI : VNI);
251  if (VNI) {
252  if (TheVNI && TheVNI != VNI)
253  UniqueVNI = false;
254  TheVNI = VNI;
255  }
256  if (VNI || EP.second)
257  continue;
258 
259  // No, we need a live-in value for Pred as well
260  if (Pred != &UseMBB)
261  WorkList.push_back(Pred->getNumber());
262  else
263  // Loopback to UseMBB, so value is really live through.
264  Use = SlotIndex();
265  }
266  }
267 
268  LiveIn.clear();
269  FoundUndef |= (TheVNI == nullptr || TheVNI == &UndefVNI);
270  if (!Undefs.empty() && FoundUndef)
271  UniqueVNI = false;
272 
273  // Both updateSSA() and LiveRangeUpdater benefit from ordered blocks, but
274  // neither require it. Skip the sorting overhead for small updates.
275  if (WorkList.size() > 4)
276  array_pod_sort(WorkList.begin(), WorkList.end());
277 
278  // If a unique reaching def was found, blit in the live ranges immediately.
279  if (UniqueVNI) {
280  assert(TheVNI != nullptr && TheVNI != &UndefVNI);
281  LiveRangeUpdater Updater(&LR);
282  for (unsigned BN : WorkList) {
283  SlotIndex Start, End;
284  std::tie(Start, End) = Indexes->getMBBRange(BN);
285  // Trim the live range in UseMBB.
286  if (BN == UseMBBNum && Use.isValid())
287  End = Use;
288  else
289  Map[MF->getBlockNumbered(BN)] = LiveOutPair(TheVNI, nullptr);
290  Updater.add(Start, End, TheVNI);
291  }
292  return true;
293  }
294 
295  // Prepare the defined/undefined bit vectors.
297  bool DidInsert;
298  std::tie(Entry, DidInsert) = EntryInfos.insert(
299  std::make_pair(&LR, std::make_pair(BitVector(), BitVector())));
300  if (DidInsert) {
301  // Initialize newly inserted entries.
302  unsigned N = MF->getNumBlockIDs();
303  Entry->second.first.resize(N);
304  Entry->second.second.resize(N);
305  }
306  BitVector &DefOnEntry = Entry->second.first;
307  BitVector &UndefOnEntry = Entry->second.second;
308 
309  // Multiple values were found, so transfer the work list to the LiveIn array
310  // where UpdateSSA will use it as a work list.
311  LiveIn.reserve(WorkList.size());
312  for (unsigned BN : WorkList) {
314  if (!Undefs.empty() &&
315  !isDefOnEntry(LR, Undefs, *MBB, DefOnEntry, UndefOnEntry))
316  continue;
317  addLiveInBlock(LR, DomTree->getNode(MBB));
318  if (MBB == &UseMBB)
319  LiveIn.back().Kill = Use;
320  }
321 
322  return false;
323 }
324 
325 // This is essentially the same iterative algorithm that SSAUpdater uses,
326 // except we already have a dominator tree, so we don't have to recompute it.
327 void LiveRangeCalc::updateSSA() {
328  assert(Indexes && "Missing SlotIndexes");
329  assert(DomTree && "Missing dominator tree");
330 
331  // Interate until convergence.
332  bool Changed;
333  do {
334  Changed = false;
335  // Propagate live-out values down the dominator tree, inserting phi-defs
336  // when necessary.
337  for (LiveInBlock &I : LiveIn) {
338  MachineDomTreeNode *Node = I.DomNode;
339  // Skip block if the live-in value has already been determined.
340  if (!Node)
341  continue;
342  MachineBasicBlock *MBB = Node->getBlock();
343  MachineDomTreeNode *IDom = Node->getIDom();
344  LiveOutPair IDomValue;
345 
346  // We need a live-in value to a block with no immediate dominator?
347  // This is probably an unreachable block that has survived somehow.
348  bool needPHI = !IDom || !Seen.test(IDom->getBlock()->getNumber());
349 
350  // IDom dominates all of our predecessors, but it may not be their
351  // immediate dominator. Check if any of them have live-out values that are
352  // properly dominated by IDom. If so, we need a phi-def here.
353  if (!needPHI) {
354  IDomValue = Map[IDom->getBlock()];
355 
356  // Cache the DomTree node that defined the value.
357  if (IDomValue.first && IDomValue.first != &UndefVNI &&
358  !IDomValue.second) {
359  Map[IDom->getBlock()].second = IDomValue.second =
360  DomTree->getNode(Indexes->getMBBFromIndex(IDomValue.first->def));
361  }
362 
363  for (MachineBasicBlock *Pred : MBB->predecessors()) {
364  LiveOutPair &Value = Map[Pred];
365  if (!Value.first || Value.first == IDomValue.first)
366  continue;
367  if (Value.first == &UndefVNI) {
368  needPHI = true;
369  break;
370  }
371 
372  // Cache the DomTree node that defined the value.
373  if (!Value.second)
374  Value.second =
375  DomTree->getNode(Indexes->getMBBFromIndex(Value.first->def));
376 
377  // This predecessor is carrying something other than IDomValue.
378  // It could be because IDomValue hasn't propagated yet, or it could be
379  // because MBB is in the dominance frontier of that value.
380  if (DomTree->dominates(IDom, Value.second)) {
381  needPHI = true;
382  break;
383  }
384  }
385  }
386 
387  // The value may be live-through even if Kill is set, as can happen when
388  // we are called from extendRange. In that case LiveOutSeen is true, and
389  // LiveOut indicates a foreign or missing value.
390  LiveOutPair &LOP = Map[MBB];
391 
392  // Create a phi-def if required.
393  if (needPHI) {
394  Changed = true;
395  assert(Alloc && "Need VNInfo allocator to create PHI-defs");
396  SlotIndex Start, End;
397  std::tie(Start, End) = Indexes->getMBBRange(MBB);
398  LiveRange &LR = I.LR;
399  VNInfo *VNI = LR.getNextValue(Start, *Alloc);
400  I.Value = VNI;
401  // This block is done, we know the final value.
402  I.DomNode = nullptr;
403 
404  // Add liveness since updateFromLiveIns now skips this node.
405  if (I.Kill.isValid()) {
406  if (VNI)
407  LR.addSegment(LiveInterval::Segment(Start, I.Kill, VNI));
408  } else {
409  if (VNI)
410  LR.addSegment(LiveInterval::Segment(Start, End, VNI));
411  LOP = LiveOutPair(VNI, Node);
412  }
413  } else if (IDomValue.first && IDomValue.first != &UndefVNI) {
414  // No phi-def here. Remember incoming value.
415  I.Value = IDomValue.first;
416 
417  // If the IDomValue is killed in the block, don't propagate through.
418  if (I.Kill.isValid())
419  continue;
420 
421  // Propagate IDomValue if it isn't killed:
422  // MBB is live-out and doesn't define its own value.
423  if (LOP.first == IDomValue.first)
424  continue;
425  Changed = true;
426  LOP = IDomValue;
427  }
428  }
429  } while (Changed);
430 }
431 
433  ArrayRef<SlotIndex> Defs,
434  const SlotIndexes &Indexes) {
435  const MachineFunction &MF = *MBB->getParent();
436  BitVector DefBlocks(MF.getNumBlockIDs());
437  for (SlotIndex I : Defs)
438  DefBlocks.set(Indexes.getMBBFromIndex(I)->getNumber());
439 
440  SetVector<unsigned> PredQueue;
441  PredQueue.insert(MBB->getNumber());
442  for (unsigned i = 0; i != PredQueue.size(); ++i) {
443  unsigned BN = PredQueue[i];
444  if (DefBlocks[BN])
445  return true;
446  const MachineBasicBlock *B = MF.getBlockNumbered(BN);
447  for (const MachineBasicBlock *P : B->predecessors())
448  PredQueue.insert(P->getNumber());
449  }
450  return false;
451 }
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:1520
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:454
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:1749
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:576
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:344
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector.
Definition: BitVector.h:328
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:116
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:87
llvm::MachineRegisterInfo::getTargetRegisterInfo
const TargetRegisterInfo * getTargetRegisterInfo() const
Definition: MachineRegisterInfo.h:151
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:798
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:234
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:334
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:114
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:115
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:159
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:666
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
llvm::LiveRangeUpdater
Helper class for performant LiveRange bulk updates.
Definition: LiveInterval.h:934
llvm::LiveRangeCalc::resetLiveOutMap
void resetLiveOutMap()
Reset Map and Seen fields.
Definition: LiveRangeCalc.cpp:41
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:143
BitVector.h
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:313
llvm::BitVector
Definition: BitVector.h:75
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:339
llvm::LiveRangeUpdater::setDest
void setDest(LiveRange *lr)
Select a different destination live range.
Definition: LiveInterval.h:967
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:402
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::SlotIndexes::getMBBStartIdx
SlotIndex getMBBStartIdx(unsigned Num) const
Returns the first index in the given basic block number.
Definition: SlotIndexes.h:465
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:112
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
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:243
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:63
llvm::MachineDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: MachineDominators.h:174
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LiveRange::getNextValue
VNInfo * getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator)
getNextValue - Create a new value number and return it.
Definition: LiveInterval.h:331
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:234
llvm::SlotIndexes::getMBBFromIndex
MachineBasicBlock * getMBBFromIndex(SlotIndex index) const
Returns the basic block which the given index falls in.
Definition: SlotIndexes.h:513
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:359
llvm::MachineBasicBlock::pred_empty
bool pred_empty() const
Definition: MachineBasicBlock.h:341
llvm::MachineFunction
Definition: MachineFunction.h:257
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:1088
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:209
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:432
llvm::MachineFunction::getBlockNumbered
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
Definition: MachineFunction.h:788
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:454
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:1180
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
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:71
SmallVector.h
N
#define N
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:49
llvm::LiveRangeCalc::setLiveOutValue
void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
Definition: LiveRangeCalc.h:229
SlotIndexes.h
raw_ostream.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
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:111
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:607
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::IndexedMap::resize
void resize(typename StorageT::size_type s)
Definition: IndexedMap.h:60
TargetRegisterInfo.h
SetVector.h
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
MachineDominators.h