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"
11 #include "llvm/CodeGen/LivePhysRegs.h"
12 #include "llvm/CodeGen/ReachingDefAnalysis.h"
13 #include "llvm/CodeGen/TargetRegisterInfo.h"
14 #include "llvm/CodeGen/TargetSubtargetInfo.h"
15 #include "llvm/Support/Debug.h"
16 
17 using namespace llvm;
18 
19 #define DEBUG_TYPE "reaching-deps-analysis"
20 
21 char ReachingDefAnalysis::ID = 0;
22 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
23                 true)
24 
isValidReg(const MachineOperand & MO)25 static bool isValidReg(const MachineOperand &MO) {
26   return MO.isReg() && MO.getReg();
27 }
28 
isValidRegUse(const MachineOperand & MO)29 static bool isValidRegUse(const MachineOperand &MO) {
30   return isValidReg(MO) && MO.isUse();
31 }
32 
isValidRegUseOf(const MachineOperand & MO,MCRegister PhysReg,const TargetRegisterInfo * TRI)33 static bool isValidRegUseOf(const MachineOperand &MO, MCRegister PhysReg,
34                             const TargetRegisterInfo *TRI) {
35   if (!isValidRegUse(MO))
36     return false;
37   return TRI->regsOverlap(MO.getReg(), PhysReg);
38 }
39 
isValidRegDef(const MachineOperand & MO)40 static bool isValidRegDef(const MachineOperand &MO) {
41   return isValidReg(MO) && MO.isDef();
42 }
43 
isValidRegDefOf(const MachineOperand & MO,MCRegister PhysReg,const TargetRegisterInfo * TRI)44 static bool isValidRegDefOf(const MachineOperand &MO, MCRegister PhysReg,
45                             const TargetRegisterInfo *TRI) {
46   if (!isValidRegDef(MO))
47     return false;
48   return TRI->regsOverlap(MO.getReg(), PhysReg);
49 }
50 
enterBasicBlock(MachineBasicBlock * MBB)51 void ReachingDefAnalysis::enterBasicBlock(MachineBasicBlock *MBB) {
52   unsigned MBBNumber = MBB->getNumber();
53   assert(MBBNumber < MBBReachingDefs.size() &&
54          "Unexpected basic block number.");
55   MBBReachingDefs[MBBNumber].resize(NumRegUnits);
56 
57   // Reset instruction counter in each basic block.
58   CurInstr = 0;
59 
60   // Set up LiveRegs to represent registers entering MBB.
61   // Default values are 'nothing happened a long time ago'.
62   if (LiveRegs.empty())
63     LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
64 
65   // This is the entry block.
66   if (MBB->pred_empty()) {
67     for (const auto &LI : MBB->liveins()) {
68       for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
69         // Treat function live-ins as if they were defined just before the first
70         // instruction.  Usually, function arguments are set up immediately
71         // before the call.
72         if (LiveRegs[*Unit] != -1) {
73           LiveRegs[*Unit] = -1;
74           MBBReachingDefs[MBBNumber][*Unit].push_back(-1);
75         }
76       }
77     }
78     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
79     return;
80   }
81 
82   // Try to coalesce live-out registers from predecessors.
83   for (MachineBasicBlock *pred : MBB->predecessors()) {
84     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
85            "Should have pre-allocated MBBInfos for all MBBs");
86     const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
87     // Incoming is null if this is a backedge from a BB
88     // we haven't processed yet
89     if (Incoming.empty())
90       continue;
91 
92     // Find the most recent reaching definition from a predecessor.
93     for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
94       LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
95   }
96 
97   // Insert the most recent reaching definition we found.
98   for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
99     if (LiveRegs[Unit] != ReachingDefDefaultVal)
100       MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
101 }
102 
leaveBasicBlock(MachineBasicBlock * MBB)103 void ReachingDefAnalysis::leaveBasicBlock(MachineBasicBlock *MBB) {
104   assert(!LiveRegs.empty() && "Must enter basic block first.");
105   unsigned MBBNumber = MBB->getNumber();
106   assert(MBBNumber < MBBOutRegsInfos.size() &&
107          "Unexpected basic block number.");
108   // Save register clearances at end of MBB - used by enterBasicBlock().
109   MBBOutRegsInfos[MBBNumber] = LiveRegs;
110 
111   // While processing the basic block, we kept `Def` relative to the start
112   // of the basic block for convenience. However, future use of this information
113   // only cares about the clearance from the end of the block, so adjust
114   // everything to be relative to the end of the basic block.
115   for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
116     if (OutLiveReg != ReachingDefDefaultVal)
117       OutLiveReg -= CurInstr;
118   LiveRegs.clear();
119 }
120 
processDefs(MachineInstr * MI)121 void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
122   assert(!MI->isDebugInstr() && "Won't process debug instructions");
123 
124   unsigned MBBNumber = MI->getParent()->getNumber();
125   assert(MBBNumber < MBBReachingDefs.size() &&
126          "Unexpected basic block number.");
127 
128   for (auto &MO : MI->operands()) {
129     if (!isValidRegDef(MO))
130       continue;
131     for (MCRegUnitIterator Unit(MO.getReg().asMCReg(), TRI); Unit.isValid();
132          ++Unit) {
133       // This instruction explicitly defines the current reg unit.
134       LLVM_DEBUG(dbgs() << printRegUnit(*Unit, TRI) << ":\t" << CurInstr
135                         << '\t' << *MI);
136 
137       // How many instructions since this reg unit was last written?
138       if (LiveRegs[*Unit] != CurInstr) {
139         LiveRegs[*Unit] = CurInstr;
140         MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
141       }
142     }
143   }
144   InstIds[MI] = CurInstr;
145   ++CurInstr;
146 }
147 
reprocessBasicBlock(MachineBasicBlock * MBB)148 void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
149   unsigned MBBNumber = MBB->getNumber();
150   assert(MBBNumber < MBBReachingDefs.size() &&
151          "Unexpected basic block number.");
152 
153   // Count number of non-debug instructions for end of block adjustment.
154   auto NonDbgInsts =
155     instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end());
156   int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
157 
158   // When reprocessing a block, the only thing we need to do is check whether
159   // there is now a more recent incoming reaching definition from a predecessor.
160   for (MachineBasicBlock *pred : MBB->predecessors()) {
161     assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
162            "Should have pre-allocated MBBInfos for all MBBs");
163     const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
164     // Incoming may be empty for dead predecessors.
165     if (Incoming.empty())
166       continue;
167 
168     for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
169       int Def = Incoming[Unit];
170       if (Def == ReachingDefDefaultVal)
171         continue;
172 
173       auto Start = MBBReachingDefs[MBBNumber][Unit].begin();
174       if (Start != MBBReachingDefs[MBBNumber][Unit].end() && *Start < 0) {
175         if (*Start >= Def)
176           continue;
177 
178         // Update existing reaching def from predecessor to a more recent one.
179         *Start = Def;
180       } else {
181         // Insert new reaching def from predecessor.
182         MBBReachingDefs[MBBNumber][Unit].insert(Start, Def);
183       }
184 
185       // Update reaching def at end of of BB. Keep in mind that these are
186       // adjusted relative to the end of the basic block.
187       if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
188         MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts;
189     }
190   }
191 }
192 
processBasicBlock(const LoopTraversal::TraversedMBBInfo & TraversedMBB)193 void ReachingDefAnalysis::processBasicBlock(
194     const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
195   MachineBasicBlock *MBB = TraversedMBB.MBB;
196   LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
197                     << (!TraversedMBB.IsDone ? ": incomplete\n"
198                                              : ": all preds known\n"));
199 
200   if (!TraversedMBB.PrimaryPass) {
201     // Reprocess MBB that is part of a loop.
202     reprocessBasicBlock(MBB);
203     return;
204   }
205 
206   enterBasicBlock(MBB);
207   for (MachineInstr &MI :
208        instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end()))
209     processDefs(&MI);
210   leaveBasicBlock(MBB);
211 }
212 
runOnMachineFunction(MachineFunction & mf)213 bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
214   MF = &mf;
215   TRI = MF->getSubtarget().getRegisterInfo();
216   LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
217   init();
218   traverse();
219   return false;
220 }
221 
releaseMemory()222 void ReachingDefAnalysis::releaseMemory() {
223   // Clear the internal vectors.
224   MBBOutRegsInfos.clear();
225   MBBReachingDefs.clear();
226   InstIds.clear();
227   LiveRegs.clear();
228 }
229 
reset()230 void ReachingDefAnalysis::reset() {
231   releaseMemory();
232   init();
233   traverse();
234 }
235 
init()236 void ReachingDefAnalysis::init() {
237   NumRegUnits = TRI->getNumRegUnits();
238   MBBReachingDefs.resize(MF->getNumBlockIDs());
239   // Initialize the MBBOutRegsInfos
240   MBBOutRegsInfos.resize(MF->getNumBlockIDs());
241   LoopTraversal Traversal;
242   TraversedMBBOrder = Traversal.traverse(*MF);
243 }
244 
traverse()245 void ReachingDefAnalysis::traverse() {
246   // Traverse the basic blocks.
247   for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
248     processBasicBlock(TraversedMBB);
249 #ifndef NDEBUG
250   // Make sure reaching defs are sorted and unique.
251   for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
252     for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) {
253       int LastDef = ReachingDefDefaultVal;
254       for (int Def : RegUnitDefs) {
255         assert(Def > LastDef && "Defs must be sorted and unique");
256         LastDef = Def;
257       }
258     }
259   }
260 #endif
261 }
262 
getReachingDef(MachineInstr * MI,MCRegister PhysReg) const263 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI,
264                                         MCRegister PhysReg) const {
265   assert(InstIds.count(MI) && "Unexpected machine instuction.");
266   int InstId = InstIds.lookup(MI);
267   int DefRes = ReachingDefDefaultVal;
268   unsigned MBBNumber = MI->getParent()->getNumber();
269   assert(MBBNumber < MBBReachingDefs.size() &&
270          "Unexpected basic block number.");
271   int LatestDef = ReachingDefDefaultVal;
272   for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
273     for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
274       if (Def >= InstId)
275         break;
276       DefRes = Def;
277     }
278     LatestDef = std::max(LatestDef, DefRes);
279   }
280   return LatestDef;
281 }
282 
283 MachineInstr *
getReachingLocalMIDef(MachineInstr * MI,MCRegister PhysReg) const284 ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
285                                            MCRegister PhysReg) const {
286   return hasLocalDefBefore(MI, PhysReg)
287     ? getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg))
288     : nullptr;
289 }
290 
hasSameReachingDef(MachineInstr * A,MachineInstr * B,MCRegister PhysReg) const291 bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
292                                              MCRegister PhysReg) const {
293   MachineBasicBlock *ParentA = A->getParent();
294   MachineBasicBlock *ParentB = B->getParent();
295   if (ParentA != ParentB)
296     return false;
297 
298   return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
299 }
300 
getInstFromId(MachineBasicBlock * MBB,int InstId) const301 MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
302                                                  int InstId) const {
303   assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
304          "Unexpected basic block number.");
305   assert(InstId < static_cast<int>(MBB->size()) &&
306          "Unexpected instruction id.");
307 
308   if (InstId < 0)
309     return nullptr;
310 
311   for (auto &MI : *MBB) {
312     auto F = InstIds.find(&MI);
313     if (F != InstIds.end() && F->second == InstId)
314       return &MI;
315   }
316 
317   return nullptr;
318 }
319 
getClearance(MachineInstr * MI,MCRegister PhysReg) const320 int ReachingDefAnalysis::getClearance(MachineInstr *MI,
321                                       MCRegister PhysReg) const {
322   assert(InstIds.count(MI) && "Unexpected machine instuction.");
323   return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
324 }
325 
hasLocalDefBefore(MachineInstr * MI,MCRegister PhysReg) const326 bool ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI,
327                                             MCRegister PhysReg) const {
328   return getReachingDef(MI, PhysReg) >= 0;
329 }
330 
getReachingLocalUses(MachineInstr * Def,MCRegister PhysReg,InstSet & Uses) const331 void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def,
332                                                MCRegister PhysReg,
333                                                InstSet &Uses) const {
334   MachineBasicBlock *MBB = Def->getParent();
335   MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
336   while (++MI != MBB->end()) {
337     if (MI->isDebugInstr())
338       continue;
339 
340     // If/when we find a new reaching def, we know that there's no more uses
341     // of 'Def'.
342     if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
343       return;
344 
345     for (auto &MO : MI->operands()) {
346       if (!isValidRegUseOf(MO, PhysReg, TRI))
347         continue;
348 
349       Uses.insert(&*MI);
350       if (MO.isKill())
351         return;
352     }
353   }
354 }
355 
getLiveInUses(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Uses) const356 bool ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB,
357                                         MCRegister PhysReg,
358                                         InstSet &Uses) const {
359   for (MachineInstr &MI :
360        instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end())) {
361     for (auto &MO : MI.operands()) {
362       if (!isValidRegUseOf(MO, PhysReg, TRI))
363         continue;
364       if (getReachingDef(&MI, PhysReg) >= 0)
365         return false;
366       Uses.insert(&MI);
367     }
368   }
369   auto Last = MBB->getLastNonDebugInstr();
370   if (Last == MBB->end())
371     return true;
372   return isReachingDefLiveOut(&*Last, PhysReg);
373 }
374 
getGlobalUses(MachineInstr * MI,MCRegister PhysReg,InstSet & Uses) const375 void ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, MCRegister PhysReg,
376                                         InstSet &Uses) const {
377   MachineBasicBlock *MBB = MI->getParent();
378 
379   // Collect the uses that each def touches within the block.
380   getReachingLocalUses(MI, PhysReg, Uses);
381 
382   // Handle live-out values.
383   if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), PhysReg)) {
384     if (LiveOut != MI)
385       return;
386 
387     SmallVector<MachineBasicBlock *, 4> ToVisit(MBB->successors());
388     SmallPtrSet<MachineBasicBlock*, 4>Visited;
389     while (!ToVisit.empty()) {
390       MachineBasicBlock *MBB = ToVisit.pop_back_val();
391       if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
392         continue;
393       if (getLiveInUses(MBB, PhysReg, Uses))
394         llvm::append_range(ToVisit, MBB->successors());
395       Visited.insert(MBB);
396     }
397   }
398 }
399 
getGlobalReachingDefs(MachineInstr * MI,MCRegister PhysReg,InstSet & Defs) const400 void ReachingDefAnalysis::getGlobalReachingDefs(MachineInstr *MI,
401                                                 MCRegister PhysReg,
402                                                 InstSet &Defs) const {
403   if (auto *Def = getUniqueReachingMIDef(MI, PhysReg)) {
404     Defs.insert(Def);
405     return;
406   }
407 
408   for (auto *MBB : MI->getParent()->predecessors())
409     getLiveOuts(MBB, PhysReg, Defs);
410 }
411 
getLiveOuts(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Defs) const412 void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
413                                       MCRegister PhysReg, InstSet &Defs) const {
414   SmallPtrSet<MachineBasicBlock*, 2> VisitedBBs;
415   getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
416 }
417 
getLiveOuts(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Defs,BlockSet & VisitedBBs) const418 void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
419                                       MCRegister PhysReg, InstSet &Defs,
420                                       BlockSet &VisitedBBs) const {
421   if (VisitedBBs.count(MBB))
422     return;
423 
424   VisitedBBs.insert(MBB);
425   LivePhysRegs LiveRegs(*TRI);
426   LiveRegs.addLiveOuts(*MBB);
427   if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
428     return;
429 
430   if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
431     Defs.insert(Def);
432   else
433     for (auto *Pred : MBB->predecessors())
434       getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
435 }
436 
437 MachineInstr *
getUniqueReachingMIDef(MachineInstr * MI,MCRegister PhysReg) const438 ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
439                                             MCRegister PhysReg) const {
440   // If there's a local def before MI, return it.
441   MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
442   if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
443     return LocalDef;
444 
445   SmallPtrSet<MachineInstr*, 2> Incoming;
446   MachineBasicBlock *Parent = MI->getParent();
447   for (auto *Pred : Parent->predecessors())
448     getLiveOuts(Pred, PhysReg, Incoming);
449 
450   // Check that we have a single incoming value and that it does not
451   // come from the same block as MI - since it would mean that the def
452   // is executed after MI.
453   if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
454     return *Incoming.begin();
455   return nullptr;
456 }
457 
getMIOperand(MachineInstr * MI,unsigned Idx) const458 MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
459                                                 unsigned Idx) const {
460   assert(MI->getOperand(Idx).isReg() && "Expected register operand");
461   return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
462 }
463 
getMIOperand(MachineInstr * MI,MachineOperand & MO) const464 MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
465                                                 MachineOperand &MO) const {
466   assert(MO.isReg() && "Expected register operand");
467   return getUniqueReachingMIDef(MI, MO.getReg());
468 }
469 
isRegUsedAfter(MachineInstr * MI,MCRegister PhysReg) const470 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI,
471                                          MCRegister PhysReg) const {
472   MachineBasicBlock *MBB = MI->getParent();
473   LivePhysRegs LiveRegs(*TRI);
474   LiveRegs.addLiveOuts(*MBB);
475 
476   // Yes if the register is live out of the basic block.
477   if (!LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
478     return true;
479 
480   // Walk backwards through the block to see if the register is live at some
481   // point.
482   for (MachineInstr &Last :
483        instructionsWithoutDebug(MBB->instr_rbegin(), MBB->instr_rend())) {
484     LiveRegs.stepBackward(Last);
485     if (!LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
486       return InstIds.lookup(&Last) > InstIds.lookup(MI);
487   }
488   return false;
489 }
490 
isRegDefinedAfter(MachineInstr * MI,MCRegister PhysReg) const491 bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI,
492                                             MCRegister PhysReg) const {
493   MachineBasicBlock *MBB = MI->getParent();
494   auto Last = MBB->getLastNonDebugInstr();
495   if (Last != MBB->end() &&
496       getReachingDef(MI, PhysReg) != getReachingDef(&*Last, PhysReg))
497     return true;
498 
499   if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
500     return Def == getReachingLocalMIDef(MI, PhysReg);
501 
502   return false;
503 }
504 
isReachingDefLiveOut(MachineInstr * MI,MCRegister PhysReg) const505 bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI,
506                                                MCRegister PhysReg) const {
507   MachineBasicBlock *MBB = MI->getParent();
508   LivePhysRegs LiveRegs(*TRI);
509   LiveRegs.addLiveOuts(*MBB);
510   if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
511     return false;
512 
513   auto Last = MBB->getLastNonDebugInstr();
514   int Def = getReachingDef(MI, PhysReg);
515   if (Last != MBB->end() && getReachingDef(&*Last, PhysReg) != Def)
516     return false;
517 
518   // Finally check that the last instruction doesn't redefine the register.
519   for (auto &MO : Last->operands())
520     if (isValidRegDefOf(MO, PhysReg, TRI))
521       return false;
522 
523   return true;
524 }
525 
526 MachineInstr *
getLocalLiveOutMIDef(MachineBasicBlock * MBB,MCRegister PhysReg) const527 ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
528                                           MCRegister PhysReg) const {
529   LivePhysRegs LiveRegs(*TRI);
530   LiveRegs.addLiveOuts(*MBB);
531   if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
532     return nullptr;
533 
534   auto Last = MBB->getLastNonDebugInstr();
535   if (Last == MBB->end())
536     return nullptr;
537 
538   int Def = getReachingDef(&*Last, PhysReg);
539   for (auto &MO : Last->operands())
540     if (isValidRegDefOf(MO, PhysReg, TRI))
541       return &*Last;
542 
543   return Def < 0 ? nullptr : getInstFromId(MBB, Def);
544 }
545 
mayHaveSideEffects(MachineInstr & MI)546 static bool mayHaveSideEffects(MachineInstr &MI) {
547   return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
548          MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
549          MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
550 }
551 
552 // Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
553 // not define a register that is used by any instructions, after and including,
554 // 'To'. These instructions also must not redefine any of Froms operands.
555 template<typename Iterator>
isSafeToMove(MachineInstr * From,MachineInstr * To) const556 bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
557                                        MachineInstr *To) const {
558   if (From->getParent() != To->getParent() || From == To)
559     return false;
560 
561   SmallSet<int, 2> Defs;
562   // First check that From would compute the same value if moved.
563   for (auto &MO : From->operands()) {
564     if (!isValidReg(MO))
565       continue;
566     if (MO.isDef())
567       Defs.insert(MO.getReg());
568     else if (!hasSameReachingDef(From, To, MO.getReg()))
569       return false;
570   }
571 
572   // Now walk checking that the rest of the instructions will compute the same
573   // value and that we're not overwriting anything. Don't move the instruction
574   // past any memory, control-flow or other ambiguous instructions.
575   for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
576     if (mayHaveSideEffects(*I))
577       return false;
578     for (auto &MO : I->operands())
579       if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
580         return false;
581   }
582   return true;
583 }
584 
isSafeToMoveForwards(MachineInstr * From,MachineInstr * To) const585 bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From,
586                                                MachineInstr *To) const {
587   using Iterator = MachineBasicBlock::iterator;
588   // Walk forwards until we find the instruction.
589   for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
590     if (&*I == To)
591       return isSafeToMove<Iterator>(From, To);
592   return false;
593 }
594 
isSafeToMoveBackwards(MachineInstr * From,MachineInstr * To) const595 bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From,
596                                                 MachineInstr *To) const {
597   using Iterator = MachineBasicBlock::reverse_iterator;
598   // Walk backwards until we find the instruction.
599   for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
600     if (&*I == To)
601       return isSafeToMove<Iterator>(From, To);
602   return false;
603 }
604 
isSafeToRemove(MachineInstr * MI,InstSet & ToRemove) const605 bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI,
606                                          InstSet &ToRemove) const {
607   SmallPtrSet<MachineInstr*, 1> Ignore;
608   SmallPtrSet<MachineInstr*, 2> Visited;
609   return isSafeToRemove(MI, Visited, ToRemove, Ignore);
610 }
611 
612 bool
isSafeToRemove(MachineInstr * MI,InstSet & ToRemove,InstSet & Ignore) const613 ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
614                                     InstSet &Ignore) const {
615   SmallPtrSet<MachineInstr*, 2> Visited;
616   return isSafeToRemove(MI, Visited, ToRemove, Ignore);
617 }
618 
619 bool
isSafeToRemove(MachineInstr * MI,InstSet & Visited,InstSet & ToRemove,InstSet & Ignore) const620 ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
621                                     InstSet &ToRemove, InstSet &Ignore) const {
622   if (Visited.count(MI) || Ignore.count(MI))
623     return true;
624   else if (mayHaveSideEffects(*MI)) {
625     // Unless told to ignore the instruction, don't remove anything which has
626     // side effects.
627     return false;
628   }
629 
630   Visited.insert(MI);
631   for (auto &MO : MI->operands()) {
632     if (!isValidRegDef(MO))
633       continue;
634 
635     SmallPtrSet<MachineInstr*, 4> Uses;
636     getGlobalUses(MI, MO.getReg(), Uses);
637 
638     for (auto *I : Uses) {
639       if (Ignore.count(I) || ToRemove.count(I))
640         continue;
641       if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
642         return false;
643     }
644   }
645   ToRemove.insert(MI);
646   return true;
647 }
648 
collectKilledOperands(MachineInstr * MI,InstSet & Dead) const649 void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI,
650                                                 InstSet &Dead) const {
651   Dead.insert(MI);
652   auto IsDead = [this, &Dead](MachineInstr *Def, MCRegister PhysReg) {
653     if (mayHaveSideEffects(*Def))
654       return false;
655 
656     unsigned LiveDefs = 0;
657     for (auto &MO : Def->operands()) {
658       if (!isValidRegDef(MO))
659         continue;
660       if (!MO.isDead())
661         ++LiveDefs;
662     }
663 
664     if (LiveDefs > 1)
665       return false;
666 
667     SmallPtrSet<MachineInstr*, 4> Uses;
668     getGlobalUses(Def, PhysReg, Uses);
669     return llvm::set_is_subset(Uses, Dead);
670   };
671 
672   for (auto &MO : MI->operands()) {
673     if (!isValidRegUse(MO))
674       continue;
675     if (MachineInstr *Def = getMIOperand(MI, MO))
676       if (IsDead(Def, MO.getReg()))
677         collectKilledOperands(Def, Dead);
678   }
679 }
680 
isSafeToDefRegAt(MachineInstr * MI,MCRegister PhysReg) const681 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
682                                            MCRegister PhysReg) const {
683   SmallPtrSet<MachineInstr*, 1> Ignore;
684   return isSafeToDefRegAt(MI, PhysReg, Ignore);
685 }
686 
isSafeToDefRegAt(MachineInstr * MI,MCRegister PhysReg,InstSet & Ignore) const687 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg,
688                                            InstSet &Ignore) const {
689   // Check for any uses of the register after MI.
690   if (isRegUsedAfter(MI, PhysReg)) {
691     if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
692       SmallPtrSet<MachineInstr*, 2> Uses;
693       getGlobalUses(Def, PhysReg, Uses);
694       if (!llvm::set_is_subset(Uses, Ignore))
695         return false;
696     } else
697       return false;
698   }
699 
700   MachineBasicBlock *MBB = MI->getParent();
701   // Check for any defs after MI.
702   if (isRegDefinedAfter(MI, PhysReg)) {
703     auto I = MachineBasicBlock::iterator(MI);
704     for (auto E = MBB->end(); I != E; ++I) {
705       if (Ignore.count(&*I))
706         continue;
707       for (auto &MO : I->operands())
708         if (isValidRegDefOf(MO, PhysReg, TRI))
709           return false;
710     }
711   }
712   return true;
713 }
714