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