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