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/MachineFrameInfo.h"
14#include "llvm/CodeGen/TargetInstrInfo.h"
15#include "llvm/CodeGen/TargetRegisterInfo.h"
16#include "llvm/CodeGen/TargetSubtargetInfo.h"
17#include "llvm/Support/Debug.h"
18
19using namespace llvm;
20
21#define DEBUG_TYPE "reaching-defs-analysis"
22
23AnalysisKey ReachingDefAnalysis::Key;
24
25ReachingDefAnalysis::Result
26ReachingDefAnalysis::run(MachineFunction &MF,
27 MachineFunctionAnalysisManager &MFAM) {
28 ReachingDefInfo RDI;
29 RDI.run(mf&: MF);
30 return RDI;
31}
32
33PreservedAnalyses
34ReachingDefPrinterPass::run(MachineFunction &MF,
35 MachineFunctionAnalysisManager &MFAM) {
36 MFPropsModifier _(*this, MF);
37
38 auto &RDI = MFAM.getResult<ReachingDefAnalysis>(IR&: MF);
39 OS << "Reaching definitions for for machine function: " << MF.getName()
40 << '\n';
41 RDI.print(OS);
42 return PreservedAnalyses::all();
43}
44
45INITIALIZE_PASS(ReachingDefInfoWrapperPass, DEBUG_TYPE,
46 "Reaching Definitions Analysis", false, true)
47
48char ReachingDefInfoWrapperPass::ID = 0;
49
50ReachingDefInfoWrapperPass::ReachingDefInfoWrapperPass()
51 : MachineFunctionPass(ID) {}
52
53ReachingDefInfo::ReachingDefInfo() = default;
54ReachingDefInfo::ReachingDefInfo(ReachingDefInfo &&) = default;
55ReachingDefInfo::~ReachingDefInfo() = default;
56
57bool ReachingDefInfo::invalidate(
58 MachineFunction &MF, const PreservedAnalyses &PA,
59 MachineFunctionAnalysisManager::Invalidator &) {
60 // Check whether the analysis, all analyses on machine functions, or the
61 // machine function's CFG have been preserved.
62 auto PAC = PA.getChecker<ReachingDefAnalysis>();
63 return !PAC.preserved() &&
64 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
65 !PAC.preservedSet<CFGAnalyses>();
66}
67
68void ReachingDefInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
69 AU.setPreservesAll();
70 MachineFunctionPass::getAnalysisUsage(AU);
71}
72
73MachineFunctionProperties
74ReachingDefInfoWrapperPass::getRequiredProperties() const {
75 return MachineFunctionProperties().setNoVRegs();
76}
77
78static bool isValidReg(const MachineOperand &MO) {
79 return MO.isReg() && MO.getReg();
80}
81
82static bool isValidRegUse(const MachineOperand &MO) {
83 return isValidReg(MO) && MO.isUse();
84}
85
86static bool isValidRegUseOf(const MachineOperand &MO, Register Reg,
87 const TargetRegisterInfo *TRI) {
88 if (!isValidRegUse(MO))
89 return false;
90 return TRI->regsOverlap(RegA: MO.getReg(), RegB: Reg);
91}
92
93static bool isValidRegDef(const MachineOperand &MO) {
94 return isValidReg(MO) && MO.isDef();
95}
96
97static bool isValidRegDefOf(const MachineOperand &MO, Register Reg,
98 const TargetRegisterInfo *TRI) {
99 if (!isValidRegDef(MO))
100 return false;
101 return TRI->regsOverlap(RegA: MO.getReg(), RegB: Reg);
102}
103
104static bool isFIDef(const MachineInstr &MI, int FrameIndex,
105 const TargetInstrInfo *TII) {
106 int DefFrameIndex = 0;
107 int SrcFrameIndex = 0;
108 if (TII->isStoreToStackSlot(MI, FrameIndex&: DefFrameIndex) ||
109 TII->isStackSlotCopy(MI, DestFrameIndex&: DefFrameIndex, SrcFrameIndex))
110 return DefFrameIndex == FrameIndex;
111 return false;
112}
113
114void ReachingDefInfo::enterBasicBlock(MachineBasicBlock *MBB) {
115 unsigned MBBNumber = MBB->getNumber();
116 assert(MBBNumber < MBBReachingDefs.numBlockIDs() &&
117 "Unexpected basic block number.");
118 MBBReachingDefs.startBasicBlock(MBBNumber, NumRegUnits);
119
120 // Reset instruction counter in each basic block.
121 CurInstr = 0;
122
123 // Set up LiveRegs to represent registers entering MBB.
124 // Default values are 'nothing happened a long time ago'.
125 if (LiveRegs.empty())
126 LiveRegs.assign(n: NumRegUnits, val: ReachingDefDefaultVal);
127
128 // This is the entry block.
129 if (MBB == &MBB->getParent()->front()) {
130 for (const auto &LI : MBB->liveins()) {
131 for (MCRegUnit Unit : TRI->regunits(Reg: LI.PhysReg)) {
132 // Treat function live-ins as if they were defined just before the first
133 // instruction. Usually, function arguments are set up immediately
134 // before the call.
135 if (LiveRegs[static_cast<unsigned>(Unit)] != FunctionLiveInMarker) {
136 LiveRegs[static_cast<unsigned>(Unit)] = FunctionLiveInMarker;
137 MBBReachingDefs.append(MBBNumber, Unit, Def: FunctionLiveInMarker);
138 }
139 }
140 }
141 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
142 return;
143 }
144
145 // Try to coalesce live-out registers from predecessors.
146 for (MachineBasicBlock *pred : MBB->predecessors()) {
147 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
148 "Should have pre-allocated MBBInfos for all MBBs");
149 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
150 // Incoming is null if this is a backedge from a BB
151 // we haven't processed yet
152 if (Incoming.empty())
153 continue;
154
155 // Find the most recent reaching definition from a predecessor.
156 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
157 LiveRegs[Unit] = std::max(a: LiveRegs[Unit], b: Incoming[Unit]);
158 }
159
160 // Insert the most recent reaching definition we found.
161 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
162 if (LiveRegs[Unit] != ReachingDefDefaultVal)
163 MBBReachingDefs.append(MBBNumber, Unit: static_cast<MCRegUnit>(Unit),
164 Def: LiveRegs[Unit]);
165}
166
167void ReachingDefInfo::leaveBasicBlock(MachineBasicBlock *MBB) {
168 assert(!LiveRegs.empty() && "Must enter basic block first.");
169 unsigned MBBNumber = MBB->getNumber();
170 assert(MBBNumber < MBBOutRegsInfos.size() &&
171 "Unexpected basic block number.");
172 // Save register clearances at end of MBB - used by enterBasicBlock().
173 MBBOutRegsInfos[MBBNumber] = LiveRegs;
174
175 // While processing the basic block, we kept `Def` relative to the start
176 // of the basic block for convenience. However, future use of this information
177 // only cares about the clearance from the end of the block, so adjust
178 // everything to be relative to the end of the basic block.
179 for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
180 if (OutLiveReg != ReachingDefDefaultVal)
181 OutLiveReg -= CurInstr;
182 LiveRegs.clear();
183}
184
185void ReachingDefInfo::processDefs(MachineInstr *MI) {
186 assert(!MI->isDebugInstr() && "Won't process debug instructions");
187
188 unsigned MBBNumber = MI->getParent()->getNumber();
189 assert(MBBNumber < MBBReachingDefs.numBlockIDs() &&
190 "Unexpected basic block number.");
191
192 for (auto &MO : MI->operands()) {
193 if (MO.isFI()) {
194 int FrameIndex = MO.getIndex();
195 if (!isFIDef(MI: *MI, FrameIndex, TII))
196 continue;
197 MBBFrameObjsReachingDefs[{MBBNumber, FrameIndex}].push_back(Elt: CurInstr);
198 }
199 if (!isValidRegDef(MO))
200 continue;
201 for (MCRegUnit Unit : TRI->regunits(Reg: MO.getReg().asMCReg())) {
202 // This instruction explicitly defines the current reg unit.
203 LLVM_DEBUG(dbgs() << printRegUnit(Unit, TRI) << ":\t" << CurInstr << '\t'
204 << *MI);
205
206 // How many instructions since this reg unit was last written?
207 if (LiveRegs[static_cast<unsigned>(Unit)] != CurInstr) {
208 LiveRegs[static_cast<unsigned>(Unit)] = CurInstr;
209 MBBReachingDefs.append(MBBNumber, Unit, Def: CurInstr);
210 }
211 }
212 }
213 InstIds[MI] = CurInstr;
214 ++CurInstr;
215}
216
217void ReachingDefInfo::reprocessBasicBlock(MachineBasicBlock *MBB) {
218 unsigned MBBNumber = MBB->getNumber();
219 assert(MBBNumber < MBBReachingDefs.numBlockIDs() &&
220 "Unexpected basic block number.");
221
222 // Count number of non-debug instructions for end of block adjustment.
223 auto NonDbgInsts =
224 instructionsWithoutDebug(It: MBB->instr_begin(), End: MBB->instr_end());
225 int NumInsts = std::distance(first: NonDbgInsts.begin(), last: NonDbgInsts.end());
226
227 // When reprocessing a block, the only thing we need to do is check whether
228 // there is now a more recent incoming reaching definition from a predecessor.
229 for (MachineBasicBlock *pred : MBB->predecessors()) {
230 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
231 "Should have pre-allocated MBBInfos for all MBBs");
232 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
233 // Incoming may be empty for dead predecessors.
234 if (Incoming.empty())
235 continue;
236
237 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
238 int Def = Incoming[Unit];
239 if (Def == ReachingDefDefaultVal)
240 continue;
241
242 auto Defs = MBBReachingDefs.defs(MBBNumber, Unit: static_cast<MCRegUnit>(Unit));
243 if (!Defs.empty() && Defs.front() < 0) {
244 if (Defs.front() >= Def)
245 continue;
246
247 // Update existing reaching def from predecessor to a more recent one.
248 MBBReachingDefs.replaceFront(MBBNumber, Unit: static_cast<MCRegUnit>(Unit),
249 Def);
250 } else {
251 // Insert new reaching def from predecessor.
252 MBBReachingDefs.prepend(MBBNumber, Unit: static_cast<MCRegUnit>(Unit), Def);
253 }
254
255 // Update reaching def at end of BB. Keep in mind that these are
256 // adjusted relative to the end of the basic block.
257 if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
258 MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts;
259 }
260 }
261}
262
263void ReachingDefInfo::processBasicBlock(
264 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
265 MachineBasicBlock *MBB = TraversedMBB.MBB;
266 LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
267 << (!TraversedMBB.IsDone ? ": incomplete\n"
268 : ": all preds known\n"));
269
270 if (!TraversedMBB.PrimaryPass) {
271 // Reprocess MBB that is part of a loop.
272 reprocessBasicBlock(MBB);
273 return;
274 }
275
276 enterBasicBlock(MBB);
277 for (MachineInstr &MI :
278 instructionsWithoutDebug(It: MBB->instr_begin(), End: MBB->instr_end()))
279 processDefs(MI: &MI);
280 leaveBasicBlock(MBB);
281}
282
283void ReachingDefInfo::run(MachineFunction &mf) {
284 MF = &mf;
285 const TargetSubtargetInfo &STI = MF->getSubtarget();
286 TRI = STI.getRegisterInfo();
287 TII = STI.getInstrInfo();
288 LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
289 init();
290 traverse();
291}
292
293void ReachingDefInfo::print(raw_ostream &OS) {
294 // Create a map from instruction to numerical ids.
295 // Since a reaching def can come after instruction,
296 // this map needs to be populated first.
297 int Num = 0;
298 DenseMap<MachineInstr *, int> InstToNumMap;
299 for (MachineBasicBlock &MBB : *MF) {
300 for (MachineInstr &MI : MBB) {
301 InstToNumMap[&MI] = Num;
302 ++Num;
303 }
304 }
305
306 SmallPtrSet<MachineInstr *, 2> Defs;
307 for (MachineBasicBlock &MBB : *MF) {
308 OS << printMBBReference(MBB) << ":\n";
309 for (MachineInstr &MI : MBB) {
310 for (MachineOperand &MO : MI.operands()) {
311 Register Reg;
312 if (MO.isFI()) {
313 int FrameIndex = MO.getIndex();
314 Reg = Register::index2StackSlot(FI: FrameIndex);
315 } else if (MO.isReg()) {
316 if (MO.isDef())
317 continue;
318 Reg = MO.getReg();
319 if (!Reg.isValid())
320 continue;
321 } else
322 continue;
323 Defs.clear();
324 getGlobalReachingDefs(MI: &MI, Reg, Defs);
325 MO.print(os&: OS, TRI);
326 SmallVector<int, 0> Nums;
327 for (MachineInstr *Def : Defs)
328 Nums.push_back(Elt: InstToNumMap[Def]);
329 llvm::sort(C&: Nums);
330 OS << ":{ ";
331 for (int Num : Nums)
332 OS << Num << " ";
333 OS << "}\n";
334 }
335 OS << InstToNumMap[&MI] << ": " << MI << "\n";
336 }
337 }
338}
339
340bool ReachingDefInfoWrapperPass::runOnMachineFunction(MachineFunction &mf) {
341 RDI.run(mf);
342 return false;
343}
344
345void ReachingDefInfo::releaseMemory() {
346 // Clear the internal vectors.
347 MBBOutRegsInfos.clear();
348 MBBReachingDefs.clear();
349 MBBFrameObjsReachingDefs.clear();
350 InstIds.clear();
351 LiveRegs.clear();
352}
353
354void ReachingDefInfo::reset() {
355 releaseMemory();
356 init();
357 traverse();
358}
359
360void ReachingDefInfo::init() {
361 NumRegUnits = TRI->getNumRegUnits();
362 NumStackObjects = MF->getFrameInfo().getNumObjects();
363 ObjectIndexBegin = MF->getFrameInfo().getObjectIndexBegin();
364 MBBReachingDefs.init(NumBlockIDs: MF->getNumBlockIDs());
365 // Initialize the MBBOutRegsInfos
366 MBBOutRegsInfos.resize(N: MF->getNumBlockIDs());
367 LoopTraversal Traversal;
368 TraversedMBBOrder = Traversal.traverse(MF&: *MF);
369}
370
371void ReachingDefInfo::traverse() {
372 // Traverse the basic blocks.
373 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
374 processBasicBlock(TraversedMBB);
375#ifndef NDEBUG
376 // Make sure reaching defs are sorted and unique.
377 for (unsigned MBBNumber = 0, NumBlockIDs = MF->getNumBlockIDs();
378 MBBNumber != NumBlockIDs; ++MBBNumber) {
379 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
380 int LastDef = ReachingDefDefaultVal;
381 for (int Def :
382 MBBReachingDefs.defs(MBBNumber, static_cast<MCRegUnit>(Unit))) {
383 assert(Def > LastDef && "Defs must be sorted and unique");
384 LastDef = Def;
385 }
386 }
387 }
388#endif
389}
390
391int ReachingDefInfo::getReachingDef(MachineInstr *MI, Register Reg) const {
392 assert(InstIds.count(MI) && "Unexpected machine instuction.");
393 int InstId = InstIds.lookup(Val: MI);
394 int DefRes = ReachingDefDefaultVal;
395 unsigned MBBNumber = MI->getParent()->getNumber();
396 assert(MBBNumber < MBBReachingDefs.numBlockIDs() &&
397 "Unexpected basic block number.");
398 int LatestDef = ReachingDefDefaultVal;
399
400 if (Reg.isStack()) {
401 // Check that there was a reaching def.
402 int FrameIndex = Reg.stackSlotIndex();
403 auto Lookup = MBBFrameObjsReachingDefs.find(Val: {MBBNumber, FrameIndex});
404 if (Lookup == MBBFrameObjsReachingDefs.end())
405 return LatestDef;
406 auto &Defs = Lookup->second;
407 for (int Def : Defs) {
408 if (Def >= InstId)
409 break;
410 DefRes = Def;
411 }
412 LatestDef = std::max(a: LatestDef, b: DefRes);
413 return LatestDef;
414 }
415
416 for (MCRegUnit Unit : TRI->regunits(Reg)) {
417 for (int Def : MBBReachingDefs.defs(MBBNumber, Unit)) {
418 if (Def >= InstId)
419 break;
420 DefRes = Def;
421 }
422 LatestDef = std::max(a: LatestDef, b: DefRes);
423 }
424 return LatestDef;
425}
426
427MachineInstr *ReachingDefInfo::getReachingLocalMIDef(MachineInstr *MI,
428 Register Reg) const {
429 return hasLocalDefBefore(MI, Reg)
430 ? getInstFromId(MBB: MI->getParent(), InstId: getReachingDef(MI, Reg))
431 : nullptr;
432}
433
434bool ReachingDefInfo::hasSameReachingDef(MachineInstr *A, MachineInstr *B,
435 Register Reg) const {
436 MachineBasicBlock *ParentA = A->getParent();
437 MachineBasicBlock *ParentB = B->getParent();
438 if (ParentA != ParentB)
439 return false;
440
441 return getReachingDef(MI: A, Reg) == getReachingDef(MI: B, Reg);
442}
443
444MachineInstr *ReachingDefInfo::getInstFromId(MachineBasicBlock *MBB,
445 int InstId) const {
446 assert(static_cast<size_t>(MBB->getNumber()) <
447 MBBReachingDefs.numBlockIDs() &&
448 "Unexpected basic block number.");
449 assert(InstId < static_cast<int>(MBB->size()) &&
450 "Unexpected instruction id.");
451
452 if (InstId < 0)
453 return nullptr;
454
455 for (auto &MI : *MBB) {
456 auto F = InstIds.find(Val: &MI);
457 if (F != InstIds.end() && F->second == InstId)
458 return &MI;
459 }
460
461 return nullptr;
462}
463
464int ReachingDefInfo::getClearance(MachineInstr *MI, Register Reg) const {
465 assert(InstIds.count(MI) && "Unexpected machine instuction.");
466 return InstIds.lookup(Val: MI) - getReachingDef(MI, Reg);
467}
468
469bool ReachingDefInfo::hasLocalDefBefore(MachineInstr *MI, Register Reg) const {
470 return getReachingDef(MI, Reg) >= 0;
471}
472
473void ReachingDefInfo::getReachingLocalUses(MachineInstr *Def, Register Reg,
474 InstSet &Uses) const {
475 MachineBasicBlock *MBB = Def->getParent();
476 MachineBasicBlock::iterator MI = MachineBasicBlock::iterator(Def);
477 while (++MI != MBB->end()) {
478 if (MI->isDebugInstr())
479 continue;
480
481 // If/when we find a new reaching def, we know that there's no more uses
482 // of 'Def'.
483 if (getReachingLocalMIDef(MI: &*MI, Reg) != Def)
484 return;
485
486 for (auto &MO : MI->operands()) {
487 if (!isValidRegUseOf(MO, Reg, TRI))
488 continue;
489
490 Uses.insert(Ptr: &*MI);
491 if (MO.isKill())
492 return;
493 }
494 }
495}
496
497bool ReachingDefInfo::getLiveInUses(MachineBasicBlock *MBB, Register Reg,
498 InstSet &Uses) const {
499 for (MachineInstr &MI :
500 instructionsWithoutDebug(It: MBB->instr_begin(), End: MBB->instr_end())) {
501 for (auto &MO : MI.operands()) {
502 if (!isValidRegUseOf(MO, Reg, TRI))
503 continue;
504 if (getReachingDef(MI: &MI, Reg) >= 0)
505 return false;
506 Uses.insert(Ptr: &MI);
507 }
508 }
509 auto Last = MBB->getLastNonDebugInstr();
510 if (Last == MBB->end())
511 return true;
512 return isReachingDefLiveOut(MI: &*Last, Reg);
513}
514
515void ReachingDefInfo::getGlobalUses(MachineInstr *MI, Register Reg,
516 InstSet &Uses) const {
517 MachineBasicBlock *MBB = MI->getParent();
518
519 // Collect the uses that each def touches within the block.
520 getReachingLocalUses(Def: MI, Reg, Uses);
521
522 // Handle live-out values.
523 if (auto *LiveOut = getLocalLiveOutMIDef(MBB: MI->getParent(), Reg)) {
524 if (LiveOut != MI)
525 return;
526
527 SmallVector<MachineBasicBlock *, 4> ToVisit(MBB->successors());
528 SmallPtrSet<MachineBasicBlock*, 4>Visited;
529 while (!ToVisit.empty()) {
530 MachineBasicBlock *MBB = ToVisit.pop_back_val();
531 if (Visited.count(Ptr: MBB) || !MBB->isLiveIn(Reg))
532 continue;
533 if (getLiveInUses(MBB, Reg, Uses))
534 llvm::append_range(C&: ToVisit, R: MBB->successors());
535 Visited.insert(Ptr: MBB);
536 }
537 }
538}
539
540void ReachingDefInfo::getGlobalReachingDefs(MachineInstr *MI, Register Reg,
541 InstSet &Defs) const {
542 if (auto *Def = getUniqueReachingMIDef(MI, Reg)) {
543 Defs.insert(Ptr: Def);
544 return;
545 }
546
547 for (auto *MBB : MI->getParent()->predecessors())
548 getLiveOuts(MBB, Reg, Defs);
549}
550
551void ReachingDefInfo::getLiveOuts(MachineBasicBlock *MBB, Register Reg,
552 InstSet &Defs) const {
553 SmallPtrSet<MachineBasicBlock*, 2> VisitedBBs;
554 getLiveOuts(MBB, Reg, Defs, VisitedBBs);
555}
556
557void ReachingDefInfo::getLiveOuts(MachineBasicBlock *MBB, Register Reg,
558 InstSet &Defs, BlockSet &VisitedBBs) const {
559 if (VisitedBBs.count(Ptr: MBB))
560 return;
561
562 VisitedBBs.insert(Ptr: MBB);
563 LiveRegUnits LiveRegs(*TRI);
564 LiveRegs.addLiveOuts(MBB: *MBB);
565 if (Reg.isPhysical() && LiveRegs.available(Reg))
566 return;
567
568 if (auto *Def = getLocalLiveOutMIDef(MBB, Reg))
569 Defs.insert(Ptr: Def);
570 else
571 for (auto *Pred : MBB->predecessors())
572 getLiveOuts(MBB: Pred, Reg, Defs, VisitedBBs);
573}
574
575MachineInstr *ReachingDefInfo::getUniqueReachingMIDef(MachineInstr *MI,
576 Register Reg) const {
577 // If there's a local def before MI, return it.
578 MachineInstr *LocalDef = getReachingLocalMIDef(MI, Reg);
579 if (LocalDef && InstIds.lookup(Val: LocalDef) < InstIds.lookup(Val: MI))
580 return LocalDef;
581
582 SmallPtrSet<MachineInstr*, 2> Incoming;
583 MachineBasicBlock *Parent = MI->getParent();
584 for (auto *Pred : Parent->predecessors())
585 getLiveOuts(MBB: Pred, Reg, Defs&: Incoming);
586
587 // Check that we have a single incoming value and that it does not
588 // come from the same block as MI - since it would mean that the def
589 // is executed after MI.
590 if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
591 return *Incoming.begin();
592 return nullptr;
593}
594
595MachineInstr *ReachingDefInfo::getMIOperand(MachineInstr *MI,
596 unsigned Idx) const {
597 assert(MI->getOperand(Idx).isReg() && "Expected register operand");
598 return getUniqueReachingMIDef(MI, Reg: MI->getOperand(i: Idx).getReg());
599}
600
601MachineInstr *ReachingDefInfo::getMIOperand(MachineInstr *MI,
602 MachineOperand &MO) const {
603 assert(MO.isReg() && "Expected register operand");
604 return getUniqueReachingMIDef(MI, Reg: MO.getReg());
605}
606
607bool ReachingDefInfo::isRegUsedAfter(MachineInstr *MI, Register Reg) const {
608 MachineBasicBlock *MBB = MI->getParent();
609 LiveRegUnits LiveRegs(*TRI);
610 LiveRegs.addLiveOuts(MBB: *MBB);
611
612 // Yes if the register is live out of the basic block.
613 if (!LiveRegs.available(Reg))
614 return true;
615
616 // Walk backwards through the block to see if the register is live at some
617 // point.
618 for (MachineInstr &Last :
619 instructionsWithoutDebug(It: MBB->instr_rbegin(), End: MBB->instr_rend())) {
620 LiveRegs.stepBackward(MI: Last);
621 if (!LiveRegs.available(Reg))
622 return InstIds.lookup(Val: &Last) > InstIds.lookup(Val: MI);
623 }
624 return false;
625}
626
627bool ReachingDefInfo::isRegDefinedAfter(MachineInstr *MI, Register Reg) const {
628 MachineBasicBlock *MBB = MI->getParent();
629 auto Last = MBB->getLastNonDebugInstr();
630 if (Last != MBB->end() &&
631 getReachingDef(MI, Reg) != getReachingDef(MI: &*Last, Reg))
632 return true;
633
634 if (auto *Def = getLocalLiveOutMIDef(MBB, Reg))
635 return Def == getReachingLocalMIDef(MI, Reg);
636
637 return false;
638}
639
640bool ReachingDefInfo::isReachingDefLiveOut(MachineInstr *MI,
641 Register Reg) const {
642 MachineBasicBlock *MBB = MI->getParent();
643 LiveRegUnits LiveRegs(*TRI);
644 LiveRegs.addLiveOuts(MBB: *MBB);
645 if (Reg.isPhysical() && LiveRegs.available(Reg))
646 return false;
647
648 auto Last = MBB->getLastNonDebugInstr();
649 int Def = getReachingDef(MI, Reg);
650 if (Last != MBB->end() && getReachingDef(MI: &*Last, Reg) != Def)
651 return false;
652
653 // Finally check that the last instruction doesn't redefine the register.
654 for (auto &MO : Last->operands())
655 if (isValidRegDefOf(MO, Reg, TRI))
656 return false;
657
658 return true;
659}
660
661MachineInstr *ReachingDefInfo::getLocalLiveOutMIDef(MachineBasicBlock *MBB,
662 Register Reg) const {
663 LiveRegUnits LiveRegs(*TRI);
664 LiveRegs.addLiveOuts(MBB: *MBB);
665 if (Reg.isPhysical() && LiveRegs.available(Reg))
666 return nullptr;
667
668 auto Last = MBB->getLastNonDebugInstr();
669 if (Last == MBB->end())
670 return nullptr;
671
672 // Check if Last is the definition
673 if (Reg.isStack()) {
674 int FrameIndex = Reg.stackSlotIndex();
675 if (isFIDef(MI: *Last, FrameIndex, TII))
676 return &*Last;
677 } else {
678 for (auto &MO : Last->operands())
679 if (isValidRegDefOf(MO, Reg, TRI))
680 return &*Last;
681 }
682
683 int Def = getReachingDef(MI: &*Last, Reg);
684 return Def < 0 ? nullptr : getInstFromId(MBB, InstId: Def);
685}
686
687static bool mayHaveSideEffects(MachineInstr &MI) {
688 return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
689 MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
690 MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
691}
692
693// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
694// not define a register that is used by any instructions, after and including,
695// 'To'. These instructions also must not redefine any of Froms operands.
696template <typename Iterator>
697bool ReachingDefInfo::isSafeToMove(MachineInstr *From, MachineInstr *To) const {
698 if (From->getParent() != To->getParent() || From == To)
699 return false;
700
701 SmallSet<Register, 2> Defs;
702 // First check that From would compute the same value if moved.
703 for (auto &MO : From->operands()) {
704 if (!isValidReg(MO))
705 continue;
706 if (MO.isDef())
707 Defs.insert(V: MO.getReg());
708 else if (!hasSameReachingDef(A: From, B: To, Reg: MO.getReg()))
709 return false;
710 }
711
712 // Now walk checking that the rest of the instructions will compute the same
713 // value and that we're not overwriting anything. Don't move the instruction
714 // past any memory, control-flow or other ambiguous instructions.
715 for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
716 if (mayHaveSideEffects(*I))
717 return false;
718 for (auto &MO : I->operands())
719 if (MO.isReg() && MO.getReg() && Defs.count(V: MO.getReg()))
720 return false;
721 }
722 return true;
723}
724
725bool ReachingDefInfo::isSafeToMoveForwards(MachineInstr *From,
726 MachineInstr *To) const {
727 using Iterator = MachineBasicBlock::iterator;
728 // Walk forwards until we find the instruction.
729 for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
730 if (&*I == To)
731 return isSafeToMove<Iterator>(From, To);
732 return false;
733}
734
735bool ReachingDefInfo::isSafeToMoveBackwards(MachineInstr *From,
736 MachineInstr *To) const {
737 using Iterator = MachineBasicBlock::reverse_iterator;
738 // Walk backwards until we find the instruction.
739 for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
740 if (&*I == To)
741 return isSafeToMove<Iterator>(From, To);
742 return false;
743}
744
745bool ReachingDefInfo::isSafeToRemove(MachineInstr *MI,
746 InstSet &ToRemove) const {
747 SmallPtrSet<MachineInstr*, 1> Ignore;
748 SmallPtrSet<MachineInstr*, 2> Visited;
749 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
750}
751
752bool ReachingDefInfo::isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
753 InstSet &Ignore) const {
754 SmallPtrSet<MachineInstr*, 2> Visited;
755 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
756}
757
758bool ReachingDefInfo::isSafeToRemove(MachineInstr *MI, InstSet &Visited,
759 InstSet &ToRemove, InstSet &Ignore) const {
760 if (Visited.count(Ptr: MI) || Ignore.count(Ptr: MI))
761 return true;
762 else if (mayHaveSideEffects(MI&: *MI)) {
763 // Unless told to ignore the instruction, don't remove anything which has
764 // side effects.
765 return false;
766 }
767
768 Visited.insert(Ptr: MI);
769 for (auto &MO : MI->operands()) {
770 if (!isValidRegDef(MO))
771 continue;
772
773 SmallPtrSet<MachineInstr*, 4> Uses;
774 getGlobalUses(MI, Reg: MO.getReg(), Uses);
775
776 for (auto *I : Uses) {
777 if (Ignore.count(Ptr: I) || ToRemove.count(Ptr: I))
778 continue;
779 if (!isSafeToRemove(MI: I, Visited, ToRemove, Ignore))
780 return false;
781 }
782 }
783 ToRemove.insert(Ptr: MI);
784 return true;
785}
786
787void ReachingDefInfo::collectKilledOperands(MachineInstr *MI,
788 InstSet &Dead) const {
789 Dead.insert(Ptr: MI);
790 auto IsDead = [this, &Dead](MachineInstr *Def, Register Reg) {
791 if (mayHaveSideEffects(MI&: *Def))
792 return false;
793
794 unsigned LiveDefs = 0;
795 for (auto &MO : Def->operands()) {
796 if (!isValidRegDef(MO))
797 continue;
798 if (!MO.isDead())
799 ++LiveDefs;
800 }
801
802 if (LiveDefs > 1)
803 return false;
804
805 SmallPtrSet<MachineInstr*, 4> Uses;
806 getGlobalUses(MI: Def, Reg, Uses);
807 return llvm::set_is_subset(S1: Uses, S2: Dead);
808 };
809
810 for (auto &MO : MI->operands()) {
811 if (!isValidRegUse(MO))
812 continue;
813 if (MachineInstr *Def = getMIOperand(MI, MO))
814 if (IsDead(Def, MO.getReg()))
815 collectKilledOperands(MI: Def, Dead);
816 }
817}
818
819bool ReachingDefInfo::isSafeToDefRegAt(MachineInstr *MI, Register Reg) const {
820 SmallPtrSet<MachineInstr*, 1> Ignore;
821 return isSafeToDefRegAt(MI, Reg, Ignore);
822}
823
824bool ReachingDefInfo::isSafeToDefRegAt(MachineInstr *MI, Register Reg,
825 InstSet &Ignore) const {
826 // Check for any uses of the register after MI.
827 if (isRegUsedAfter(MI, Reg)) {
828 if (auto *Def = getReachingLocalMIDef(MI, Reg)) {
829 SmallPtrSet<MachineInstr*, 2> Uses;
830 getGlobalUses(MI: Def, Reg, Uses);
831 if (!llvm::set_is_subset(S1: Uses, S2: Ignore))
832 return false;
833 } else
834 return false;
835 }
836
837 MachineBasicBlock *MBB = MI->getParent();
838 // Check for any defs after MI.
839 if (isRegDefinedAfter(MI, Reg)) {
840 auto I = MachineBasicBlock::iterator(MI);
841 for (auto E = MBB->end(); I != E; ++I) {
842 if (Ignore.count(Ptr: &*I))
843 continue;
844 for (auto &MO : I->operands())
845 if (isValidRegDefOf(MO, Reg, TRI))
846 return false;
847 }
848 }
849 return true;
850}
851