LLVM  11.0.0git
ReachingDefAnalysis.cpp
Go to the documentation of this file.
1 //===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
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 #include "llvm/ADT/SmallSet.h"
14 #include "llvm/Support/Debug.h"
15 
16 using namespace llvm;
17 
18 #define DEBUG_TYPE "reaching-deps-analysis"
19 
21 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
22  true)
23 
24 static bool isValidReg(const MachineOperand &MO) {
25  return MO.isReg() && MO.getReg();
26 }
27 
28 static bool isValidRegUse(const MachineOperand &MO) {
29  return isValidReg(MO) && MO.isUse();
30 }
31 
32 static bool isValidRegUseOf(const MachineOperand &MO, int PhysReg) {
33  return isValidRegUse(MO) && MO.getReg() == PhysReg;
34 }
35 
36 static bool isValidRegDef(const MachineOperand &MO) {
37  return isValidReg(MO) && MO.isDef();
38 }
39 
40 static bool isValidRegDefOf(const MachineOperand &MO, int PhysReg) {
41  return isValidRegDef(MO) && MO.getReg() == PhysReg;
42 }
43 
44 void ReachingDefAnalysis::enterBasicBlock(MachineBasicBlock *MBB) {
45  unsigned MBBNumber = MBB->getNumber();
46  assert(MBBNumber < MBBReachingDefs.size() &&
47  "Unexpected basic block number.");
48  MBBReachingDefs[MBBNumber].resize(NumRegUnits);
49 
50  // Reset instruction counter in each basic block.
51  CurInstr = 0;
52 
53  // Set up LiveRegs to represent registers entering MBB.
54  // Default values are 'nothing happened a long time ago'.
55  if (LiveRegs.empty())
56  LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
57 
58  // This is the entry block.
59  if (MBB->pred_empty()) {
60  for (const auto &LI : MBB->liveins()) {
61  for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
62  // Treat function live-ins as if they were defined just before the first
63  // instruction. Usually, function arguments are set up immediately
64  // before the call.
65  if (LiveRegs[*Unit] != -1) {
66  LiveRegs[*Unit] = -1;
67  MBBReachingDefs[MBBNumber][*Unit].push_back(-1);
68  }
69  }
70  }
71  LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
72  return;
73  }
74 
75  // Try to coalesce live-out registers from predecessors.
76  for (MachineBasicBlock *pred : MBB->predecessors()) {
77  assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
78  "Should have pre-allocated MBBInfos for all MBBs");
79  const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
80  // Incoming is null if this is a backedge from a BB
81  // we haven't processed yet
82  if (Incoming.empty())
83  continue;
84 
85  // Find the most recent reaching definition from a predecessor.
86  for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
87  LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
88  }
89 
90  // Insert the most recent reaching definition we found.
91  for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
92  if (LiveRegs[Unit] != ReachingDefDefaultVal)
93  MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
94 }
95 
96 void ReachingDefAnalysis::leaveBasicBlock(MachineBasicBlock *MBB) {
97  assert(!LiveRegs.empty() && "Must enter basic block first.");
98  unsigned MBBNumber = MBB->getNumber();
99  assert(MBBNumber < MBBOutRegsInfos.size() &&
100  "Unexpected basic block number.");
101  // Save register clearances at end of MBB - used by enterBasicBlock().
102  MBBOutRegsInfos[MBBNumber] = LiveRegs;
103 
104  // While processing the basic block, we kept `Def` relative to the start
105  // of the basic block for convenience. However, future use of this information
106  // only cares about the clearance from the end of the block, so adjust
107  // everything to be relative to the end of the basic block.
108  for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
109  if (OutLiveReg != ReachingDefDefaultVal)
110  OutLiveReg -= CurInstr;
111  LiveRegs.clear();
112 }
113 
114 void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
115  assert(!MI->isDebugInstr() && "Won't process debug instructions");
116 
117  unsigned MBBNumber = MI->getParent()->getNumber();
118  assert(MBBNumber < MBBReachingDefs.size() &&
119  "Unexpected basic block number.");
120 
121  for (auto &MO : MI->operands()) {
122  if (!isValidRegDef(MO))
123  continue;
124  for (MCRegUnitIterator Unit(MO.getReg(), TRI); Unit.isValid(); ++Unit) {
125  // This instruction explicitly defines the current reg unit.
126  LLVM_DEBUG(dbgs() << printReg(*Unit, TRI) << ":\t" << CurInstr
127  << '\t' << *MI);
128 
129  // How many instructions since this reg unit was last written?
130  if (LiveRegs[*Unit] != CurInstr) {
131  LiveRegs[*Unit] = CurInstr;
132  MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
133  }
134  }
135  }
136  InstIds[MI] = CurInstr;
137  ++CurInstr;
138 }
139 
140 void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
141  unsigned MBBNumber = MBB->getNumber();
142  assert(MBBNumber < MBBReachingDefs.size() &&
143  "Unexpected basic block number.");
144 
145  // Count number of non-debug instructions for end of block adjustment.
146  int NumInsts = 0;
147  for (const MachineInstr &MI : *MBB)
148  if (!MI.isDebugInstr())
149  NumInsts++;
150 
151  // When reprocessing a block, the only thing we need to do is check whether
152  // there is now a more recent incoming reaching definition from a predecessor.
153  for (MachineBasicBlock *pred : MBB->predecessors()) {
154  assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
155  "Should have pre-allocated MBBInfos for all MBBs");
156  const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
157  // Incoming may be empty for dead predecessors.
158  if (Incoming.empty())
159  continue;
160 
161  for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
162  int Def = Incoming[Unit];
163  if (Def == ReachingDefDefaultVal)
164  continue;
165 
166  auto Start = MBBReachingDefs[MBBNumber][Unit].begin();
167  if (Start != MBBReachingDefs[MBBNumber][Unit].end() && *Start < 0) {
168  if (*Start >= Def)
169  continue;
170 
171  // Update existing reaching def from predecessor to a more recent one.
172  *Start = Def;
173  } else {
174  // Insert new reaching def from predecessor.
175  MBBReachingDefs[MBBNumber][Unit].insert(Start, Def);
176  }
177 
178  // Update reaching def at end of of BB. Keep in mind that these are
179  // adjusted relative to the end of the basic block.
180  if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
181  MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts;
182  }
183  }
184 }
185 
186 void ReachingDefAnalysis::processBasicBlock(
187  const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
188  MachineBasicBlock *MBB = TraversedMBB.MBB;
190  << (!TraversedMBB.IsDone ? ": incomplete\n"
191  : ": all preds known\n"));
192 
193  if (!TraversedMBB.PrimaryPass) {
194  // Reprocess MBB that is part of a loop.
195  reprocessBasicBlock(MBB);
196  return;
197  }
198 
199  enterBasicBlock(MBB);
200  for (MachineInstr &MI : *MBB) {
201  if (!MI.isDebugInstr())
202  processDefs(&MI);
203  }
204  leaveBasicBlock(MBB);
205 }
206 
208  MF = &mf;
209  TRI = MF->getSubtarget().getRegisterInfo();
210  LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
211  init();
212  traverse();
213  return false;
214 }
215 
217  // Clear the internal vectors.
218  MBBOutRegsInfos.clear();
219  MBBReachingDefs.clear();
220  InstIds.clear();
221  LiveRegs.clear();
222 }
223 
225  releaseMemory();
226  init();
227  traverse();
228 }
229 
231  NumRegUnits = TRI->getNumRegUnits();
232  MBBReachingDefs.resize(MF->getNumBlockIDs());
233  // Initialize the MBBOutRegsInfos
234  MBBOutRegsInfos.resize(MF->getNumBlockIDs());
235  LoopTraversal Traversal;
236  TraversedMBBOrder = Traversal.traverse(*MF);
237 }
238 
240  // Traverse the basic blocks.
241  for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
242  processBasicBlock(TraversedMBB);
243 #ifndef NDEBUG
244  // Make sure reaching defs are sorted and unique.
245  for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
246  for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) {
247  int LastDef = ReachingDefDefaultVal;
248  for (int Def : RegUnitDefs) {
249  assert(Def > LastDef && "Defs must be sorted and unique");
250  LastDef = Def;
251  }
252  }
253  }
254 #endif
255 }
256 
258  assert(InstIds.count(MI) && "Unexpected machine instuction.");
259  int InstId = InstIds.lookup(MI);
260  int DefRes = ReachingDefDefaultVal;
261  unsigned MBBNumber = MI->getParent()->getNumber();
262  assert(MBBNumber < MBBReachingDefs.size() &&
263  "Unexpected basic block number.");
264  int LatestDef = ReachingDefDefaultVal;
265  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
266  for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
267  if (Def >= InstId)
268  break;
269  DefRes = Def;
270  }
271  LatestDef = std::max(LatestDef, DefRes);
272  }
273  return LatestDef;
274 }
275 
276 MachineInstr* ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
277  int PhysReg) const {
278  return getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg));
279 }
280 
282  int PhysReg) const {
283  MachineBasicBlock *ParentA = A->getParent();
284  MachineBasicBlock *ParentB = B->getParent();
285  if (ParentA != ParentB)
286  return false;
287 
288  return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
289 }
290 
291 MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
292  int InstId) const {
293  assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
294  "Unexpected basic block number.");
295  assert(InstId < static_cast<int>(MBB->size()) &&
296  "Unexpected instruction id.");
297 
298  if (InstId < 0)
299  return nullptr;
300 
301  for (auto &MI : *MBB) {
302  auto F = InstIds.find(&MI);
303  if (F != InstIds.end() && F->second == InstId)
304  return &MI;
305  }
306 
307  return nullptr;
308 }
309 
310 int
312  assert(InstIds.count(MI) && "Unexpected machine instuction.");
313  return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
314 }
315 
316 bool
318  return getReachingDef(MI, PhysReg) >= 0;
319 }
320 
322  InstSet &Uses) const {
323  MachineBasicBlock *MBB = Def->getParent();
325  while (++MI != MBB->end()) {
326  if (MI->isDebugInstr())
327  continue;
328 
329  // If/when we find a new reaching def, we know that there's no more uses
330  // of 'Def'.
331  if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
332  return;
333 
334  for (auto &MO : MI->operands()) {
335  if (!isValidRegUseOf(MO, PhysReg))
336  continue;
337 
338  Uses.insert(&*MI);
339  if (MO.isKill())
340  return;
341  }
342  }
343 }
344 
345 bool
347  InstSet &Uses) const {
348  for (auto &MI : *MBB) {
349  if (MI.isDebugInstr())
350  continue;
351  for (auto &MO : MI.operands()) {
352  if (!isValidRegUseOf(MO, PhysReg))
353  continue;
354  if (getReachingDef(&MI, PhysReg) >= 0)
355  return false;
356  Uses.insert(&MI);
357  }
358  }
359  return isReachingDefLiveOut(&MBB->back(), PhysReg);
360 }
361 
362 void
364  InstSet &Uses) const {
365  MachineBasicBlock *MBB = MI->getParent();
366 
367  // Collect the uses that each def touches within the block.
368  getReachingLocalUses(MI, PhysReg, Uses);
369 
370  // Handle live-out values.
371  if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), PhysReg)) {
372  if (LiveOut != MI)
373  return;
374 
376  ToVisit.insert(ToVisit.begin(), MBB->successors().begin(),
377  MBB->successors().end());
379  while (!ToVisit.empty()) {
380  MachineBasicBlock *MBB = ToVisit.back();
381  ToVisit.pop_back();
382  if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
383  continue;
384  if (getLiveInUses(MBB, PhysReg, Uses))
385  ToVisit.insert(ToVisit.end(), MBB->successors().begin(),
386  MBB->successors().end());
387  Visited.insert(MBB);
388  }
389  }
390 }
391 
393  InstSet &Defs) const {
395  getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
396 }
397 
398 void
400  InstSet &Defs, BlockSet &VisitedBBs) const {
401  if (VisitedBBs.count(MBB))
402  return;
403 
404  VisitedBBs.insert(MBB);
405  LivePhysRegs LiveRegs(*TRI);
406  LiveRegs.addLiveOuts(*MBB);
407  if (!LiveRegs.contains(PhysReg))
408  return;
409 
410  if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
411  Defs.insert(Def);
412  else
413  for (auto *Pred : MBB->predecessors())
414  getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
415 }
416 
418  int PhysReg) const {
419  // If there's a local def before MI, return it.
420  MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
421  if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
422  return LocalDef;
423 
426  for (auto *Pred : MI->getParent()->predecessors())
427  getLiveOuts(Pred, PhysReg, Incoming, VisitedBBs);
428 
429  // If we have a local def and an incoming instruction, then there's not a
430  // unique instruction def.
431  if (!Incoming.empty() && LocalDef)
432  return nullptr;
433  else if (Incoming.size() == 1)
434  return *Incoming.begin();
435  else
436  return LocalDef;
437 }
438 
440  unsigned Idx) const {
441  assert(MI->getOperand(Idx).isReg() && "Expected register operand");
442  return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
443 }
444 
446  MachineOperand &MO) const {
447  assert(MO.isReg() && "Expected register operand");
448  return getUniqueReachingMIDef(MI, MO.getReg());
449 }
450 
451 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI, int PhysReg) const {
452  MachineBasicBlock *MBB = MI->getParent();
453  LivePhysRegs LiveRegs(*TRI);
454  LiveRegs.addLiveOuts(*MBB);
455 
456  // Yes if the register is live out of the basic block.
457  if (LiveRegs.contains(PhysReg))
458  return true;
459 
460  // Walk backwards through the block to see if the register is live at some
461  // point.
462  for (auto Last = MBB->rbegin(), End = MBB->rend(); Last != End; ++Last) {
463  LiveRegs.stepBackward(*Last);
464  if (LiveRegs.contains(PhysReg))
465  return InstIds.lookup(&*Last) > InstIds.lookup(MI);
466  }
467  return false;
468 }
469 
471  int PhysReg) const {
472  MachineBasicBlock *MBB = MI->getParent();
473  if (getReachingDef(MI, PhysReg) != getReachingDef(&MBB->back(), PhysReg))
474  return true;
475 
476  if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
477  return Def == getReachingLocalMIDef(MI, PhysReg);
478 
479  return false;
480 }
481 
482 bool
484  MachineBasicBlock *MBB = MI->getParent();
485  LivePhysRegs LiveRegs(*TRI);
486  LiveRegs.addLiveOuts(*MBB);
487  if (!LiveRegs.contains(PhysReg))
488  return false;
489 
490  MachineInstr *Last = &MBB->back();
491  int Def = getReachingDef(MI, PhysReg);
492  if (getReachingDef(Last, PhysReg) != Def)
493  return false;
494 
495  // Finally check that the last instruction doesn't redefine the register.
496  for (auto &MO : Last->operands())
497  if (isValidRegDefOf(MO, PhysReg))
498  return false;
499 
500  return true;
501 }
502 
504  int PhysReg) const {
505  LivePhysRegs LiveRegs(*TRI);
506  LiveRegs.addLiveOuts(*MBB);
507  if (!LiveRegs.contains(PhysReg))
508  return nullptr;
509 
510  MachineInstr *Last = &MBB->back();
511  int Def = getReachingDef(Last, PhysReg);
512  for (auto &MO : Last->operands())
513  if (isValidRegDefOf(MO, PhysReg))
514  return Last;
515 
516  return Def < 0 ? nullptr : getInstFromId(MBB, Def);
517 }
518 
520  return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
521  MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
522  MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
523 }
524 
525 // Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
526 // not define a register that is used by any instructions, after and including,
527 // 'To'. These instructions also must not redefine any of Froms operands.
528 template<typename Iterator>
529 bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
530  MachineInstr *To) const {
531  if (From->getParent() != To->getParent())
532  return false;
533 
534  SmallSet<int, 2> Defs;
535  // First check that From would compute the same value if moved.
536  for (auto &MO : From->operands()) {
537  if (!isValidReg(MO))
538  continue;
539  if (MO.isDef())
540  Defs.insert(MO.getReg());
541  else if (!hasSameReachingDef(From, To, MO.getReg()))
542  return false;
543  }
544 
545  // Now walk checking that the rest of the instructions will compute the same
546  // value and that we're not overwriting anything. Don't move the instruction
547  // past any memory, control-flow or other ambiguous instructions.
548  for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
549  if (mayHaveSideEffects(*I))
550  return false;
551  for (auto &MO : I->operands())
552  if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
553  return false;
554  }
555  return true;
556 }
557 
559  MachineInstr *To) const {
560  return isSafeToMove<MachineBasicBlock::reverse_iterator>(From, To);
561 }
562 
564  MachineInstr *To) const {
565  return isSafeToMove<MachineBasicBlock::iterator>(From, To);
566 }
567 
569  InstSet &ToRemove) const {
572  return isSafeToRemove(MI, Visited, ToRemove, Ignore);
573 }
574 
575 bool
577  InstSet &Ignore) const {
579  return isSafeToRemove(MI, Visited, ToRemove, Ignore);
580 }
581 
582 bool
584  InstSet &ToRemove, InstSet &Ignore) const {
585  if (Visited.count(MI) || Ignore.count(MI))
586  return true;
587  else if (mayHaveSideEffects(*MI)) {
588  // Unless told to ignore the instruction, don't remove anything which has
589  // side effects.
590  return false;
591  }
592 
593  Visited.insert(MI);
594  for (auto &MO : MI->operands()) {
595  if (!isValidRegDef(MO))
596  continue;
597 
599  getGlobalUses(MI, MO.getReg(), Uses);
600 
601  for (auto I : Uses) {
602  if (Ignore.count(I) || ToRemove.count(I))
603  continue;
604  if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
605  return false;
606  }
607  }
608  ToRemove.insert(MI);
609  return true;
610 }
611 
613  InstSet &Dead) const {
614  Dead.insert(MI);
615  auto IsDead = [this, &Dead](MachineInstr *Def, int PhysReg) {
616  unsigned LiveDefs = 0;
617  for (auto &MO : Def->operands()) {
618  if (!isValidRegDef(MO))
619  continue;
620  if (!MO.isDead())
621  ++LiveDefs;
622  }
623 
624  if (LiveDefs > 1)
625  return false;
626 
628  getGlobalUses(Def, PhysReg, Uses);
629  for (auto *Use : Uses)
630  if (!Dead.count(Use))
631  return false;
632  return true;
633  };
634 
635  for (auto &MO : MI->operands()) {
636  if (!isValidRegUse(MO))
637  continue;
638  if (MachineInstr *Def = getMIOperand(MI, MO))
639  if (IsDead(Def, MO.getReg()))
640  collectKilledOperands(Def, Dead);
641  }
642 }
643 
645  int PhysReg) const {
647  return isSafeToDefRegAt(MI, PhysReg, Ignore);
648 }
649 
651  InstSet &Ignore) const {
652  // Check for any uses of the register after MI.
653  if (isRegUsedAfter(MI, PhysReg)) {
654  if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
656  getReachingLocalUses(Def, PhysReg, Uses);
657  for (auto *Use : Uses)
658  if (!Ignore.count(Use))
659  return false;
660  } else
661  return false;
662  }
663 
664  MachineBasicBlock *MBB = MI->getParent();
665  // Check for any defs after MI.
666  if (isRegDefinedAfter(MI, PhysReg)) {
667  auto I = MachineBasicBlock::iterator(MI);
668  for (auto E = MBB->end(); I != E; ++I) {
669  if (Ignore.count(&*I))
670  continue;
671  for (auto &MO : I->operands())
672  if (isValidRegDefOf(MO, PhysReg))
673  return false;
674  }
675  }
676  return true;
677 }
bool getLiveInUses(MachineBasicBlock *MBB, int PhysReg, InstSet &Uses) const
For the given block, collect the instructions that use the live-in value of the provided register...
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
bool isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const
Return whether the reaching def for MI also is live out of its parent block.
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:760
bool IsDead
bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved forwards to just before To.
MachineInstr * getLocalLiveOutMIDef(MachineBasicBlock *MBB, int PhysReg) const
Return the local MI that produces the live out value for PhysReg, or nullptr for a non-live out or no...
static bool mayHaveSideEffects(MachineInstr &MI)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool isRegUsedAfter(MachineInstr *MI, int PhysReg) const
Return whether the given register is used after MI, whether it&#39;s a local use or a live out...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
bool PrimaryPass
True if this is the first time we process the basic block.
Definition: LoopTraversal.h:92
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
void push_back(const T &Elt)
Definition: SmallVector.h:246
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
bool mayLoadOrStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read or modify memory.
Definition: MachineInstr.h:965
void getLiveOuts(MachineBasicBlock *MBB, int PhysReg, InstSet &Defs, BlockSet &VisitedBBs) const
Search MBB for a definition of PhysReg and insert it into Defs.
void getGlobalUses(MachineInstr *MI, int PhysReg, InstSet &Uses) const
Collect the users of the value stored in PhysReg, which is defined by MI.
F(f)
bool contains(MCPhysReg Reg) const
Returns true if register Reg is contained in the set.
Definition: LivePhysRegs.h:106
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.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:559
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
iterator_range< succ_iterator > successors()
bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, int PhysReg) const
Return whether A and B use the same def of PhysReg.
This class provides the reaching def analysis.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
MachineBasicBlock & MBB
int getClearance(MachineInstr *MI, MCPhysReg PhysReg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
static bool isValidRegDefOf(const MachineOperand &MO, int PhysReg)
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:784
void reset()
Re-run the analysis.
bool mayRaiseFPException() const
Return true if this instruction could possibly raise a floating-point exception.
Definition: MachineInstr.h:975
static bool isValidRegUseOf(const MachineOperand &MO, int PhysReg)
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
reverse_iterator rend()
bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const
Return whether removing this instruction will have no effect on the program, returning the redundant ...
void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const
Assuming MI is dead, recursively search the incoming operands which are killed by MI and collect thos...
reverse_iterator rbegin()
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:792
bool isReturn(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:750
INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false, true) static bool isValidReg(const MachineOperand &MO)
int getReachingDef(MachineInstr *MI, int PhysReg) const
Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI...
MachineInstrBundleIterator< MachineInstr > iterator
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void init()
Initialize data structures.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved backwards to just after To.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:375
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:180
iterator_range< pred_iterator > predecessors()
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
bool isDebugInstr() const
bool hasLocalDefBefore(MachineInstr *MI, int PhysReg) const
Provide whether the register has been defined in the same basic block as, and before, MI.
bool isRegDefinedAfter(MachineInstr *MI, int PhysReg) const
Return whether the given register is defined after MI.
hexagon gen pred
size_type size() const
Definition: SmallPtrSet.h:92
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:439
BlockVerifier::State From
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
static bool isValidRegDef(const MachineOperand &MO)
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:883
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:513
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:280
Representation of each machine instruction.
Definition: MachineInstr.h:62
iterator begin() const
Definition: SmallPtrSet.h:392
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
#define I(x, y, z)
Definition: MD5.cpp:59
TraversalOrder traverse(MachineFunction &MF)
void getReachingLocalUses(MachineInstr *MI, int PhysReg, InstSet &Uses) const
Provides the uses, in the same block as MI, of register that MI defines.
size_t size() const
Definition: SmallVector.h:66
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
iterator_range< livein_iterator > liveins() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBasicBlock * MBB
The basic block.
Definition: LoopTraversal.h:89
aarch64 promote const
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
static bool isValidRegUse(const MachineOperand &MO)
IRTranslator LLVM IR MI
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
Definition: MachineInstr.h:775
MachineInstr * getUniqueReachingMIDef(MachineInstr *MI, int PhysReg) const
If a single MachineInstr creates the reaching definition, then return it.
Register getReg() const
getReg - Returns the register number.
bool IsDone
True if the block that is ready for its final round of processing.
Definition: LoopTraversal.h:95
bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg) const
Return whether a MachineInstr could be inserted at MI and safely define the given register without af...
#define DEBUG_TYPE
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:466
void traverse()
Traverse the machine function, mapping definitions.
MachineInstr * getMIOperand(MachineInstr *MI, unsigned Idx) const
If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:164
void resize(size_type N)
Definition: SmallVector.h:390