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