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