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/CodeGen/LivePhysRegs.h"
11 #include "llvm/CodeGen/ReachingDefAnalysis.h"
12 #include "llvm/CodeGen/TargetRegisterInfo.h"
13 #include "llvm/CodeGen/TargetSubtargetInfo.h"
14 #include "llvm/Support/Debug.h"
15
16 using namespace llvm;
17
18 #define DEBUG_TYPE "reaching-deps-analysis"
19
20 char ReachingDefAnalysis::ID = 0;
21 INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
22 true)
23
isValidReg(const MachineOperand & MO)24 static bool isValidReg(const MachineOperand &MO) {
25 return MO.isReg() && MO.getReg();
26 }
27
isValidRegUse(const MachineOperand & MO)28 static bool isValidRegUse(const MachineOperand &MO) {
29 return isValidReg(MO) && MO.isUse();
30 }
31
isValidRegUseOf(const MachineOperand & MO,MCRegister PhysReg)32 static bool isValidRegUseOf(const MachineOperand &MO, MCRegister PhysReg) {
33 return isValidRegUse(MO) && MO.getReg() == PhysReg;
34 }
35
isValidRegDef(const MachineOperand & MO)36 static bool isValidRegDef(const MachineOperand &MO) {
37 return isValidReg(MO) && MO.isDef();
38 }
39
isValidRegDefOf(const MachineOperand & MO,MCRegister PhysReg)40 static bool isValidRegDefOf(const MachineOperand &MO, MCRegister PhysReg) {
41 return isValidRegDef(MO) && MO.getReg() == PhysReg;
42 }
43
enterBasicBlock(MachineBasicBlock * MBB)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
leaveBasicBlock(MachineBasicBlock * MBB)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
processDefs(MachineInstr * MI)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().asMCReg(), TRI); Unit.isValid();
125 ++Unit) {
126 // This instruction explicitly defines the current reg unit.
127 LLVM_DEBUG(dbgs() << printReg(*Unit, TRI) << ":\t" << CurInstr
128 << '\t' << *MI);
129
130 // How many instructions since this reg unit was last written?
131 if (LiveRegs[*Unit] != CurInstr) {
132 LiveRegs[*Unit] = CurInstr;
133 MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
134 }
135 }
136 }
137 InstIds[MI] = CurInstr;
138 ++CurInstr;
139 }
140
reprocessBasicBlock(MachineBasicBlock * MBB)141 void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
142 unsigned MBBNumber = MBB->getNumber();
143 assert(MBBNumber < MBBReachingDefs.size() &&
144 "Unexpected basic block number.");
145
146 // Count number of non-debug instructions for end of block adjustment.
147 auto NonDbgInsts =
148 instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end());
149 int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
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
processBasicBlock(const LoopTraversal::TraversedMBBInfo & TraversedMBB)186 void ReachingDefAnalysis::processBasicBlock(
187 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
188 MachineBasicBlock *MBB = TraversedMBB.MBB;
189 LLVM_DEBUG(dbgs() << printMBBReference(*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 :
201 instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end()))
202 processDefs(&MI);
203 leaveBasicBlock(MBB);
204 }
205
runOnMachineFunction(MachineFunction & mf)206 bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
207 MF = &mf;
208 TRI = MF->getSubtarget().getRegisterInfo();
209 LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
210 init();
211 traverse();
212 return false;
213 }
214
releaseMemory()215 void ReachingDefAnalysis::releaseMemory() {
216 // Clear the internal vectors.
217 MBBOutRegsInfos.clear();
218 MBBReachingDefs.clear();
219 InstIds.clear();
220 LiveRegs.clear();
221 }
222
reset()223 void ReachingDefAnalysis::reset() {
224 releaseMemory();
225 init();
226 traverse();
227 }
228
init()229 void ReachingDefAnalysis::init() {
230 NumRegUnits = TRI->getNumRegUnits();
231 MBBReachingDefs.resize(MF->getNumBlockIDs());
232 // Initialize the MBBOutRegsInfos
233 MBBOutRegsInfos.resize(MF->getNumBlockIDs());
234 LoopTraversal Traversal;
235 TraversedMBBOrder = Traversal.traverse(*MF);
236 }
237
traverse()238 void ReachingDefAnalysis::traverse() {
239 // Traverse the basic blocks.
240 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
241 processBasicBlock(TraversedMBB);
242 #ifndef NDEBUG
243 // Make sure reaching defs are sorted and unique.
244 for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
245 for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) {
246 int LastDef = ReachingDefDefaultVal;
247 for (int Def : RegUnitDefs) {
248 assert(Def > LastDef && "Defs must be sorted and unique");
249 LastDef = Def;
250 }
251 }
252 }
253 #endif
254 }
255
getReachingDef(MachineInstr * MI,MCRegister PhysReg) const256 int ReachingDefAnalysis::getReachingDef(MachineInstr *MI,
257 MCRegister PhysReg) const {
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 *
getReachingLocalMIDef(MachineInstr * MI,MCRegister PhysReg) const277 ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
278 MCRegister PhysReg) const {
279 return hasLocalDefBefore(MI, PhysReg)
280 ? getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg))
281 : nullptr;
282 }
283
hasSameReachingDef(MachineInstr * A,MachineInstr * B,MCRegister PhysReg) const284 bool ReachingDefAnalysis::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
285 MCRegister PhysReg) const {
286 MachineBasicBlock *ParentA = A->getParent();
287 MachineBasicBlock *ParentB = B->getParent();
288 if (ParentA != ParentB)
289 return false;
290
291 return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
292 }
293
getInstFromId(MachineBasicBlock * MBB,int InstId) const294 MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
295 int InstId) const {
296 assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
297 "Unexpected basic block number.");
298 assert(InstId < static_cast<int>(MBB->size()) &&
299 "Unexpected instruction id.");
300
301 if (InstId < 0)
302 return nullptr;
303
304 for (auto &MI : *MBB) {
305 auto F = InstIds.find(&MI);
306 if (F != InstIds.end() && F->second == InstId)
307 return &MI;
308 }
309
310 return nullptr;
311 }
312
getClearance(MachineInstr * MI,MCRegister PhysReg) const313 int ReachingDefAnalysis::getClearance(MachineInstr *MI,
314 MCRegister PhysReg) const {
315 assert(InstIds.count(MI) && "Unexpected machine instuction.");
316 return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
317 }
318
hasLocalDefBefore(MachineInstr * MI,MCRegister PhysReg) const319 bool ReachingDefAnalysis::hasLocalDefBefore(MachineInstr *MI,
320 MCRegister PhysReg) const {
321 return getReachingDef(MI, PhysReg) >= 0;
322 }
323
getReachingLocalUses(MachineInstr * Def,MCRegister PhysReg,InstSet & Uses) const324 void ReachingDefAnalysis::getReachingLocalUses(MachineInstr *Def,
325 MCRegister PhysReg,
326 InstSet &Uses) const {
327 MachineBasicBlock *MBB = Def->getParent();
328 MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
329 while (++MI != MBB->end()) {
330 if (MI->isDebugInstr())
331 continue;
332
333 // If/when we find a new reaching def, we know that there's no more uses
334 // of 'Def'.
335 if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
336 return;
337
338 for (auto &MO : MI->operands()) {
339 if (!isValidRegUseOf(MO, PhysReg))
340 continue;
341
342 Uses.insert(&*MI);
343 if (MO.isKill())
344 return;
345 }
346 }
347 }
348
getLiveInUses(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Uses) const349 bool ReachingDefAnalysis::getLiveInUses(MachineBasicBlock *MBB,
350 MCRegister PhysReg,
351 InstSet &Uses) const {
352 for (MachineInstr &MI :
353 instructionsWithoutDebug(MBB->instr_begin(), MBB->instr_end())) {
354 for (auto &MO : MI.operands()) {
355 if (!isValidRegUseOf(MO, PhysReg))
356 continue;
357 if (getReachingDef(&MI, PhysReg) >= 0)
358 return false;
359 Uses.insert(&MI);
360 }
361 }
362 auto Last = MBB->getLastNonDebugInstr();
363 if (Last == MBB->end())
364 return true;
365 return isReachingDefLiveOut(&*Last, PhysReg);
366 }
367
getGlobalUses(MachineInstr * MI,MCRegister PhysReg,InstSet & Uses) const368 void ReachingDefAnalysis::getGlobalUses(MachineInstr *MI, MCRegister PhysReg,
369 InstSet &Uses) const {
370 MachineBasicBlock *MBB = MI->getParent();
371
372 // Collect the uses that each def touches within the block.
373 getReachingLocalUses(MI, PhysReg, Uses);
374
375 // Handle live-out values.
376 if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), PhysReg)) {
377 if (LiveOut != MI)
378 return;
379
380 SmallVector<MachineBasicBlock *, 4> ToVisit(MBB->successors());
381 SmallPtrSet<MachineBasicBlock*, 4>Visited;
382 while (!ToVisit.empty()) {
383 MachineBasicBlock *MBB = ToVisit.back();
384 ToVisit.pop_back();
385 if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
386 continue;
387 if (getLiveInUses(MBB, PhysReg, Uses))
388 llvm::append_range(ToVisit, MBB->successors());
389 Visited.insert(MBB);
390 }
391 }
392 }
393
getGlobalReachingDefs(MachineInstr * MI,MCRegister PhysReg,InstSet & Defs) const394 void ReachingDefAnalysis::getGlobalReachingDefs(MachineInstr *MI,
395 MCRegister PhysReg,
396 InstSet &Defs) const {
397 if (auto *Def = getUniqueReachingMIDef(MI, PhysReg)) {
398 Defs.insert(Def);
399 return;
400 }
401
402 for (auto *MBB : MI->getParent()->predecessors())
403 getLiveOuts(MBB, PhysReg, Defs);
404 }
405
getLiveOuts(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Defs) const406 void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
407 MCRegister PhysReg, InstSet &Defs) const {
408 SmallPtrSet<MachineBasicBlock*, 2> VisitedBBs;
409 getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
410 }
411
getLiveOuts(MachineBasicBlock * MBB,MCRegister PhysReg,InstSet & Defs,BlockSet & VisitedBBs) const412 void ReachingDefAnalysis::getLiveOuts(MachineBasicBlock *MBB,
413 MCRegister PhysReg, InstSet &Defs,
414 BlockSet &VisitedBBs) const {
415 if (VisitedBBs.count(MBB))
416 return;
417
418 VisitedBBs.insert(MBB);
419 LivePhysRegs LiveRegs(*TRI);
420 LiveRegs.addLiveOuts(*MBB);
421 if (!LiveRegs.contains(PhysReg))
422 return;
423
424 if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
425 Defs.insert(Def);
426 else
427 for (auto *Pred : MBB->predecessors())
428 getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
429 }
430
431 MachineInstr *
getUniqueReachingMIDef(MachineInstr * MI,MCRegister PhysReg) const432 ReachingDefAnalysis::getUniqueReachingMIDef(MachineInstr *MI,
433 MCRegister PhysReg) const {
434 // If there's a local def before MI, return it.
435 MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
436 if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
437 return LocalDef;
438
439 SmallPtrSet<MachineInstr*, 2> Incoming;
440 MachineBasicBlock *Parent = MI->getParent();
441 for (auto *Pred : Parent->predecessors())
442 getLiveOuts(Pred, PhysReg, Incoming);
443
444 // Check that we have a single incoming value and that it does not
445 // come from the same block as MI - since it would mean that the def
446 // is executed after MI.
447 if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
448 return *Incoming.begin();
449 return nullptr;
450 }
451
getMIOperand(MachineInstr * MI,unsigned Idx) const452 MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
453 unsigned Idx) const {
454 assert(MI->getOperand(Idx).isReg() && "Expected register operand");
455 return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
456 }
457
getMIOperand(MachineInstr * MI,MachineOperand & MO) const458 MachineInstr *ReachingDefAnalysis::getMIOperand(MachineInstr *MI,
459 MachineOperand &MO) const {
460 assert(MO.isReg() && "Expected register operand");
461 return getUniqueReachingMIDef(MI, MO.getReg());
462 }
463
isRegUsedAfter(MachineInstr * MI,MCRegister PhysReg) const464 bool ReachingDefAnalysis::isRegUsedAfter(MachineInstr *MI,
465 MCRegister PhysReg) const {
466 MachineBasicBlock *MBB = MI->getParent();
467 LivePhysRegs LiveRegs(*TRI);
468 LiveRegs.addLiveOuts(*MBB);
469
470 // Yes if the register is live out of the basic block.
471 if (LiveRegs.contains(PhysReg))
472 return true;
473
474 // Walk backwards through the block to see if the register is live at some
475 // point.
476 for (MachineInstr &Last :
477 instructionsWithoutDebug(MBB->instr_rbegin(), MBB->instr_rend())) {
478 LiveRegs.stepBackward(Last);
479 if (LiveRegs.contains(PhysReg))
480 return InstIds.lookup(&Last) > InstIds.lookup(MI);
481 }
482 return false;
483 }
484
isRegDefinedAfter(MachineInstr * MI,MCRegister PhysReg) const485 bool ReachingDefAnalysis::isRegDefinedAfter(MachineInstr *MI,
486 MCRegister PhysReg) const {
487 MachineBasicBlock *MBB = MI->getParent();
488 auto Last = MBB->getLastNonDebugInstr();
489 if (Last != MBB->end() &&
490 getReachingDef(MI, PhysReg) != getReachingDef(&*Last, PhysReg))
491 return true;
492
493 if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
494 return Def == getReachingLocalMIDef(MI, PhysReg);
495
496 return false;
497 }
498
isReachingDefLiveOut(MachineInstr * MI,MCRegister PhysReg) const499 bool ReachingDefAnalysis::isReachingDefLiveOut(MachineInstr *MI,
500 MCRegister PhysReg) const {
501 MachineBasicBlock *MBB = MI->getParent();
502 LivePhysRegs LiveRegs(*TRI);
503 LiveRegs.addLiveOuts(*MBB);
504 if (!LiveRegs.contains(PhysReg))
505 return false;
506
507 auto Last = MBB->getLastNonDebugInstr();
508 int Def = getReachingDef(MI, PhysReg);
509 if (Last != MBB->end() && getReachingDef(&*Last, PhysReg) != Def)
510 return false;
511
512 // Finally check that the last instruction doesn't redefine the register.
513 for (auto &MO : Last->operands())
514 if (isValidRegDefOf(MO, PhysReg))
515 return false;
516
517 return true;
518 }
519
520 MachineInstr *
getLocalLiveOutMIDef(MachineBasicBlock * MBB,MCRegister PhysReg) const521 ReachingDefAnalysis::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
522 MCRegister PhysReg) const {
523 LivePhysRegs LiveRegs(*TRI);
524 LiveRegs.addLiveOuts(*MBB);
525 if (!LiveRegs.contains(PhysReg))
526 return nullptr;
527
528 auto Last = MBB->getLastNonDebugInstr();
529 if (Last == MBB->end())
530 return nullptr;
531
532 int Def = getReachingDef(&*Last, PhysReg);
533 for (auto &MO : Last->operands())
534 if (isValidRegDefOf(MO, PhysReg))
535 return &*Last;
536
537 return Def < 0 ? nullptr : getInstFromId(MBB, Def);
538 }
539
mayHaveSideEffects(MachineInstr & MI)540 static bool mayHaveSideEffects(MachineInstr &MI) {
541 return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
542 MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
543 MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
544 }
545
546 // Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
547 // not define a register that is used by any instructions, after and including,
548 // 'To'. These instructions also must not redefine any of Froms operands.
549 template<typename Iterator>
isSafeToMove(MachineInstr * From,MachineInstr * To) const550 bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
551 MachineInstr *To) const {
552 if (From->getParent() != To->getParent() || From == To)
553 return false;
554
555 SmallSet<int, 2> Defs;
556 // First check that From would compute the same value if moved.
557 for (auto &MO : From->operands()) {
558 if (!isValidReg(MO))
559 continue;
560 if (MO.isDef())
561 Defs.insert(MO.getReg());
562 else if (!hasSameReachingDef(From, To, MO.getReg()))
563 return false;
564 }
565
566 // Now walk checking that the rest of the instructions will compute the same
567 // value and that we're not overwriting anything. Don't move the instruction
568 // past any memory, control-flow or other ambiguous instructions.
569 for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
570 if (mayHaveSideEffects(*I))
571 return false;
572 for (auto &MO : I->operands())
573 if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
574 return false;
575 }
576 return true;
577 }
578
isSafeToMoveForwards(MachineInstr * From,MachineInstr * To) const579 bool ReachingDefAnalysis::isSafeToMoveForwards(MachineInstr *From,
580 MachineInstr *To) const {
581 using Iterator = MachineBasicBlock::iterator;
582 // Walk forwards until we find the instruction.
583 for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
584 if (&*I == To)
585 return isSafeToMove<Iterator>(From, To);
586 return false;
587 }
588
isSafeToMoveBackwards(MachineInstr * From,MachineInstr * To) const589 bool ReachingDefAnalysis::isSafeToMoveBackwards(MachineInstr *From,
590 MachineInstr *To) const {
591 using Iterator = MachineBasicBlock::reverse_iterator;
592 // Walk backwards until we find the instruction.
593 for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
594 if (&*I == To)
595 return isSafeToMove<Iterator>(From, To);
596 return false;
597 }
598
isSafeToRemove(MachineInstr * MI,InstSet & ToRemove) const599 bool ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI,
600 InstSet &ToRemove) const {
601 SmallPtrSet<MachineInstr*, 1> Ignore;
602 SmallPtrSet<MachineInstr*, 2> Visited;
603 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
604 }
605
606 bool
isSafeToRemove(MachineInstr * MI,InstSet & ToRemove,InstSet & Ignore) const607 ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
608 InstSet &Ignore) const {
609 SmallPtrSet<MachineInstr*, 2> Visited;
610 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
611 }
612
613 bool
isSafeToRemove(MachineInstr * MI,InstSet & Visited,InstSet & ToRemove,InstSet & Ignore) const614 ReachingDefAnalysis::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
615 InstSet &ToRemove, InstSet &Ignore) const {
616 if (Visited.count(MI) || Ignore.count(MI))
617 return true;
618 else if (mayHaveSideEffects(*MI)) {
619 // Unless told to ignore the instruction, don't remove anything which has
620 // side effects.
621 return false;
622 }
623
624 Visited.insert(MI);
625 for (auto &MO : MI->operands()) {
626 if (!isValidRegDef(MO))
627 continue;
628
629 SmallPtrSet<MachineInstr*, 4> Uses;
630 getGlobalUses(MI, MO.getReg(), Uses);
631
632 for (auto I : Uses) {
633 if (Ignore.count(I) || ToRemove.count(I))
634 continue;
635 if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
636 return false;
637 }
638 }
639 ToRemove.insert(MI);
640 return true;
641 }
642
collectKilledOperands(MachineInstr * MI,InstSet & Dead) const643 void ReachingDefAnalysis::collectKilledOperands(MachineInstr *MI,
644 InstSet &Dead) const {
645 Dead.insert(MI);
646 auto IsDead = [this, &Dead](MachineInstr *Def, MCRegister PhysReg) {
647 if (mayHaveSideEffects(*Def))
648 return false;
649
650 unsigned LiveDefs = 0;
651 for (auto &MO : Def->operands()) {
652 if (!isValidRegDef(MO))
653 continue;
654 if (!MO.isDead())
655 ++LiveDefs;
656 }
657
658 if (LiveDefs > 1)
659 return false;
660
661 SmallPtrSet<MachineInstr*, 4> Uses;
662 getGlobalUses(Def, PhysReg, Uses);
663 for (auto *Use : Uses)
664 if (!Dead.count(Use))
665 return false;
666 return true;
667 };
668
669 for (auto &MO : MI->operands()) {
670 if (!isValidRegUse(MO))
671 continue;
672 if (MachineInstr *Def = getMIOperand(MI, MO))
673 if (IsDead(Def, MO.getReg()))
674 collectKilledOperands(Def, Dead);
675 }
676 }
677
isSafeToDefRegAt(MachineInstr * MI,MCRegister PhysReg) const678 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI,
679 MCRegister PhysReg) const {
680 SmallPtrSet<MachineInstr*, 1> Ignore;
681 return isSafeToDefRegAt(MI, PhysReg, Ignore);
682 }
683
isSafeToDefRegAt(MachineInstr * MI,MCRegister PhysReg,InstSet & Ignore) const684 bool ReachingDefAnalysis::isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg,
685 InstSet &Ignore) const {
686 // Check for any uses of the register after MI.
687 if (isRegUsedAfter(MI, PhysReg)) {
688 if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
689 SmallPtrSet<MachineInstr*, 2> Uses;
690 getGlobalUses(Def, PhysReg, Uses);
691 for (auto *Use : Uses)
692 if (!Ignore.count(Use))
693 return false;
694 } else
695 return false;
696 }
697
698 MachineBasicBlock *MBB = MI->getParent();
699 // Check for any defs after MI.
700 if (isRegDefinedAfter(MI, PhysReg)) {
701 auto I = MachineBasicBlock::iterator(MI);
702 for (auto E = MBB->end(); I != E; ++I) {
703 if (Ignore.count(&*I))
704 continue;
705 for (auto &MO : I->operands())
706 if (isValidRegDefOf(MO, PhysReg))
707 return false;
708 }
709 }
710 return true;
711 }
712