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