LLVM 22.0.0git
ReachingDefAnalysis.cpp
Go to the documentation of this file.
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
11#include "llvm/ADT/SmallSet.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"),
26
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(MO.getReg(), 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(MO.getReg(), 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, DefFrameIndex) ||
62 TII->isStackSlotCopy(MI, 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(NumRegUnits, 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(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, -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(LiveRegs[Unit], 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, 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, FrameIndex, TII))
149 continue;
150 MBBFrameObjsReachingDefs[{MBBNumber, FrameIndex}].push_back(CurInstr);
151 }
152 if (!isValidRegDef(MO))
153 continue;
154 for (MCRegUnit Unit : TRI->regunits(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, 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 =
178 int NumInsts = std::distance(NonDbgInsts.begin(), 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;
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 :
231 processDefs(&MI);
232 leaveBasicBlock(MBB);
233}
234
236 dbgs() << "RDA results for " << MF.getName() << "\n";
237 int Num = 0;
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(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, Reg, Defs);
259 MO.print(dbgs(), TRI);
261 for (MachineInstr *Def : Defs)
262 Nums.push_back(InstToNumMap[Def]);
263 llvm::sort(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
277 MF = &mf;
278 const TargetSubtargetInfo &STI = MF->getSubtarget();
279 TRI = STI.getRegisterInfo();
280 TII = STI.getInstrInfo();
281 LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
282 init();
283 traverse();
286 return false;
287}
288
290 // Clear the internal vectors.
291 MBBOutRegsInfos.clear();
292 MBBReachingDefs.clear();
293 MBBFrameObjsReachingDefs.clear();
294 InstIds.clear();
295 LiveRegs.clear();
296}
297
300 init();
301 traverse();
302}
303
305 NumRegUnits = TRI->getNumRegUnits();
306 NumStackObjects = MF->getFrameInfo().getNumObjects();
307 ObjectIndexBegin = MF->getFrameInfo().getObjectIndexBegin();
308 MBBReachingDefs.init(MF->getNumBlockIDs());
309 // Initialize the MBBOutRegsInfos
310 MBBOutRegsInfos.resize(MF->getNumBlockIDs());
311 LoopTraversal Traversal;
312 TraversedMBBOrder = Traversal.traverse(*MF);
313}
314
316 // Traverse the basic blocks.
317 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
318 processBasicBlock(TraversedMBB);
319#ifndef NDEBUG
320 // Make sure reaching defs are sorted and unique.
321 for (unsigned MBBNumber = 0, NumBlockIDs = MF->getNumBlockIDs();
322 MBBNumber != NumBlockIDs; ++MBBNumber) {
323 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
324 int LastDef = ReachingDefDefaultVal;
325 for (int Def : MBBReachingDefs.defs(MBBNumber, Unit)) {
326 assert(Def > LastDef && "Defs must be sorted and unique");
327 LastDef = Def;
328 }
329 }
330 }
331#endif
332}
333
335 assert(InstIds.count(MI) && "Unexpected machine instuction.");
336 int InstId = InstIds.lookup(MI);
337 int DefRes = ReachingDefDefaultVal;
338 unsigned MBBNumber = MI->getParent()->getNumber();
339 assert(MBBNumber < MBBReachingDefs.numBlockIDs() &&
340 "Unexpected basic block number.");
341 int LatestDef = ReachingDefDefaultVal;
342
343 if (Reg.isStack()) {
344 // Check that there was a reaching def.
345 int FrameIndex = Reg.stackSlotIndex();
346 auto Lookup = MBBFrameObjsReachingDefs.find({MBBNumber, FrameIndex});
347 if (Lookup == MBBFrameObjsReachingDefs.end())
348 return LatestDef;
349 auto &Defs = Lookup->second;
350 for (int Def : Defs) {
351 if (Def >= InstId)
352 break;
353 DefRes = Def;
354 }
355 LatestDef = std::max(LatestDef, DefRes);
356 return LatestDef;
357 }
358
359 for (MCRegUnit Unit : TRI->regunits(Reg)) {
360 for (int Def : MBBReachingDefs.defs(MBBNumber, Unit)) {
361 if (Def >= InstId)
362 break;
363 DefRes = Def;
364 }
365 LatestDef = std::max(LatestDef, DefRes);
366 }
367 return LatestDef;
368}
369
370MachineInstr *ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
371 Register Reg) const {
372 return hasLocalDefBefore(MI, Reg)
373 ? getInstFromId(MI->getParent(), getReachingDef(MI, Reg))
374 : nullptr;
375}
376
378 Register Reg) const {
379 MachineBasicBlock *ParentA = A->getParent();
380 MachineBasicBlock *ParentB = B->getParent();
381 if (ParentA != ParentB)
382 return false;
383
384 return getReachingDef(A, Reg) == getReachingDef(B, Reg);
385}
386
387MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
388 int InstId) const {
389 assert(static_cast<size_t>(MBB->getNumber()) <
390 MBBReachingDefs.numBlockIDs() &&
391 "Unexpected basic block number.");
392 assert(InstId < static_cast<int>(MBB->size()) &&
393 "Unexpected instruction id.");
394
395 if (InstId < 0)
396 return nullptr;
397
398 for (auto &MI : *MBB) {
399 auto F = InstIds.find(&MI);
400 if (F != InstIds.end() && F->second == InstId)
401 return &MI;
402 }
403
404 return nullptr;
405}
406
408 assert(InstIds.count(MI) && "Unexpected machine instuction.");
409 return InstIds.lookup(MI) - getReachingDef(MI, Reg);
410}
411
413 Register Reg) const {
414 return getReachingDef(MI, Reg) >= 0;
415}
416
418 InstSet &Uses) const {
419 MachineBasicBlock *MBB = Def->getParent();
421 while (++MI != MBB->end()) {
422 if (MI->isDebugInstr())
423 continue;
424
425 // If/when we find a new reaching def, we know that there's no more uses
426 // of 'Def'.
427 if (getReachingLocalMIDef(&*MI, Reg) != Def)
428 return;
429
430 for (auto &MO : MI->operands()) {
431 if (!isValidRegUseOf(MO, Reg, TRI))
432 continue;
433
434 Uses.insert(&*MI);
435 if (MO.isKill())
436 return;
437 }
438 }
439}
440
442 InstSet &Uses) const {
443 for (MachineInstr &MI :
445 for (auto &MO : MI.operands()) {
446 if (!isValidRegUseOf(MO, Reg, TRI))
447 continue;
448 if (getReachingDef(&MI, Reg) >= 0)
449 return false;
450 Uses.insert(&MI);
451 }
452 }
453 auto Last = MBB->getLastNonDebugInstr();
454 if (Last == MBB->end())
455 return true;
456 return isReachingDefLiveOut(&*Last, Reg);
457}
458
460 InstSet &Uses) const {
461 MachineBasicBlock *MBB = MI->getParent();
462
463 // Collect the uses that each def touches within the block.
465
466 // Handle live-out values.
467 if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), Reg)) {
468 if (LiveOut != MI)
469 return;
470
473 while (!ToVisit.empty()) {
475 if (Visited.count(MBB) || !MBB->isLiveIn(Reg))
476 continue;
477 if (getLiveInUses(MBB, Reg, Uses))
478 llvm::append_range(ToVisit, MBB->successors());
479 Visited.insert(MBB);
480 }
481 }
482}
483
485 InstSet &Defs) const {
486 if (auto *Def = getUniqueReachingMIDef(MI, Reg)) {
487 Defs.insert(Def);
488 return;
489 }
490
491 for (auto *MBB : MI->getParent()->predecessors())
492 getLiveOuts(MBB, Reg, Defs);
493}
494
496 InstSet &Defs) const {
498 getLiveOuts(MBB, Reg, Defs, VisitedBBs);
499}
500
502 InstSet &Defs,
503 BlockSet &VisitedBBs) const {
504 if (VisitedBBs.count(MBB))
505 return;
506
507 VisitedBBs.insert(MBB);
508 LiveRegUnits LiveRegs(*TRI);
509 LiveRegs.addLiveOuts(*MBB);
510 if (Reg.isPhysical() && LiveRegs.available(Reg))
511 return;
512
513 if (auto *Def = getLocalLiveOutMIDef(MBB, Reg))
514 Defs.insert(Def);
515 else
516 for (auto *Pred : MBB->predecessors())
517 getLiveOuts(Pred, Reg, Defs, VisitedBBs);
518}
519
521 Register Reg) const {
522 // If there's a local def before MI, return it.
523 MachineInstr *LocalDef = getReachingLocalMIDef(MI, Reg);
524 if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
525 return LocalDef;
526
528 MachineBasicBlock *Parent = MI->getParent();
529 for (auto *Pred : Parent->predecessors())
530 getLiveOuts(Pred, Reg, Incoming);
531
532 // Check that we have a single incoming value and that it does not
533 // come from the same block as MI - since it would mean that the def
534 // is executed after MI.
535 if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
536 return *Incoming.begin();
537 return nullptr;
538}
539
541 unsigned Idx) const {
542 assert(MI->getOperand(Idx).isReg() && "Expected register operand");
543 return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
544}
545
547 MachineOperand &MO) const {
548 assert(MO.isReg() && "Expected register operand");
549 return getUniqueReachingMIDef(MI, MO.getReg());
550}
551
553 MachineBasicBlock *MBB = MI->getParent();
554 LiveRegUnits LiveRegs(*TRI);
555 LiveRegs.addLiveOuts(*MBB);
556
557 // Yes if the register is live out of the basic block.
558 if (!LiveRegs.available(Reg))
559 return true;
560
561 // Walk backwards through the block to see if the register is live at some
562 // point.
563 for (MachineInstr &Last :
565 LiveRegs.stepBackward(Last);
566 if (!LiveRegs.available(Reg))
567 return InstIds.lookup(&Last) > InstIds.lookup(MI);
568 }
569 return false;
570}
571
573 Register Reg) const {
574 MachineBasicBlock *MBB = MI->getParent();
575 auto Last = MBB->getLastNonDebugInstr();
576 if (Last != MBB->end() &&
577 getReachingDef(MI, Reg) != getReachingDef(&*Last, Reg))
578 return true;
579
580 if (auto *Def = getLocalLiveOutMIDef(MBB, Reg))
581 return Def == getReachingLocalMIDef(MI, Reg);
582
583 return false;
584}
585
587 Register Reg) const {
588 MachineBasicBlock *MBB = MI->getParent();
589 LiveRegUnits LiveRegs(*TRI);
590 LiveRegs.addLiveOuts(*MBB);
591 if (Reg.isPhysical() && LiveRegs.available(Reg))
592 return false;
593
594 auto Last = MBB->getLastNonDebugInstr();
595 int Def = getReachingDef(MI, Reg);
596 if (Last != MBB->end() && getReachingDef(&*Last, Reg) != Def)
597 return false;
598
599 // Finally check that the last instruction doesn't redefine the register.
600 for (auto &MO : Last->operands())
601 if (isValidRegDefOf(MO, Reg, TRI))
602 return false;
603
604 return true;
605}
606
608 Register Reg) const {
609 LiveRegUnits LiveRegs(*TRI);
610 LiveRegs.addLiveOuts(*MBB);
611 if (Reg.isPhysical() && LiveRegs.available(Reg))
612 return nullptr;
613
614 auto Last = MBB->getLastNonDebugInstr();
615 if (Last == MBB->end())
616 return nullptr;
617
618 if (Reg.isStack()) {
619 int FrameIndex = Reg.stackSlotIndex();
620 if (isFIDef(*Last, FrameIndex, TII))
621 return &*Last;
622 }
623
624 int Def = getReachingDef(&*Last, Reg);
625
626 for (auto &MO : Last->operands())
627 if (isValidRegDefOf(MO, Reg, TRI))
628 return &*Last;
629
630 return Def < 0 ? nullptr : getInstFromId(MBB, Def);
631}
632
634 return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
635 MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
636 MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
637}
638
639// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
640// not define a register that is used by any instructions, after and including,
641// 'To'. These instructions also must not redefine any of Froms operands.
642template<typename Iterator>
643bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
644 MachineInstr *To) const {
645 if (From->getParent() != To->getParent() || From == To)
646 return false;
647
649 // First check that From would compute the same value if moved.
650 for (auto &MO : From->operands()) {
651 if (!isValidReg(MO))
652 continue;
653 if (MO.isDef())
654 Defs.insert(MO.getReg());
655 else if (!hasSameReachingDef(From, To, MO.getReg()))
656 return false;
657 }
658
659 // Now walk checking that the rest of the instructions will compute the same
660 // value and that we're not overwriting anything. Don't move the instruction
661 // past any memory, control-flow or other ambiguous instructions.
662 for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
663 if (mayHaveSideEffects(*I))
664 return false;
665 for (auto &MO : I->operands())
666 if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
667 return false;
668 }
669 return true;
670}
671
673 MachineInstr *To) const {
674 using Iterator = MachineBasicBlock::iterator;
675 // Walk forwards until we find the instruction.
676 for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
677 if (&*I == To)
678 return isSafeToMove<Iterator>(From, To);
679 return false;
680}
681
683 MachineInstr *To) const {
685 // Walk backwards until we find the instruction.
686 for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
687 if (&*I == To)
688 return isSafeToMove<Iterator>(From, To);
689 return false;
690}
691
693 InstSet &ToRemove) const {
696 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
697}
698
699bool
701 InstSet &Ignore) const {
703 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
704}
705
706bool
708 InstSet &ToRemove, InstSet &Ignore) const {
709 if (Visited.count(MI) || Ignore.count(MI))
710 return true;
711 else if (mayHaveSideEffects(*MI)) {
712 // Unless told to ignore the instruction, don't remove anything which has
713 // side effects.
714 return false;
715 }
716
717 Visited.insert(MI);
718 for (auto &MO : MI->operands()) {
719 if (!isValidRegDef(MO))
720 continue;
721
723 getGlobalUses(MI, MO.getReg(), Uses);
724
725 for (auto *I : Uses) {
726 if (Ignore.count(I) || ToRemove.count(I))
727 continue;
728 if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
729 return false;
730 }
731 }
732 ToRemove.insert(MI);
733 return true;
734}
735
737 InstSet &Dead) const {
738 Dead.insert(MI);
739 auto IsDead = [this, &Dead](MachineInstr *Def, Register Reg) {
740 if (mayHaveSideEffects(*Def))
741 return false;
742
743 unsigned LiveDefs = 0;
744 for (auto &MO : Def->operands()) {
745 if (!isValidRegDef(MO))
746 continue;
747 if (!MO.isDead())
748 ++LiveDefs;
749 }
750
751 if (LiveDefs > 1)
752 return false;
753
755 getGlobalUses(Def, Reg, Uses);
756 return llvm::set_is_subset(Uses, Dead);
757 };
758
759 for (auto &MO : MI->operands()) {
760 if (!isValidRegUse(MO))
761 continue;
762 if (MachineInstr *Def = getMIOperand(MI, MO))
763 if (IsDead(Def, MO.getReg()))
764 collectKilledOperands(Def, Dead);
765 }
766}
767
769 Register Reg) const {
771 return isSafeToDefRegAt(MI, Reg, Ignore);
772}
773
775 InstSet &Ignore) const {
776 // Check for any uses of the register after MI.
777 if (isRegUsedAfter(MI, Reg)) {
778 if (auto *Def = getReachingLocalMIDef(MI, Reg)) {
780 getGlobalUses(Def, Reg, Uses);
782 return false;
783 } else
784 return false;
785 }
786
787 MachineBasicBlock *MBB = MI->getParent();
788 // Check for any defs after MI.
789 if (isRegDefinedAfter(MI, Reg)) {
791 for (auto E = MBB->end(); I != E; ++I) {
792 if (Ignore.count(&*I))
793 continue;
794 for (auto &MO : I->operands())
795 if (isValidRegDefOf(MO, Reg, TRI))
796 return false;
797 }
798 }
799 return true;
800}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
aarch64 promote const
ReachingDefAnalysis InstSet & ToRemove
ReachingDefAnalysis InstSet InstSet & Ignore
MachineBasicBlock & MBB
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
A set of register units.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Register const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:56
static bool isValidRegUseOf(const MachineOperand &MO, Register Reg, const TargetRegisterInfo *TRI)
static bool mayHaveSideEffects(MachineInstr &MI)
static bool isFIDef(const MachineInstr &MI, int FrameIndex, const TargetInstrInfo *TII)
static bool isValidRegDef(const MachineOperand &MO)
static cl::opt< bool > PrintAllReachingDefs("print-all-reaching-defs", cl::Hidden, cl::desc("Used for test purpuses"), cl::Hidden)
static bool isValidRegDefOf(const MachineOperand &MO, Register Reg, const TargetRegisterInfo *TRI)
static bool isValidRegUse(const MachineOperand &MO)
#define DEBUG_TYPE
Remove Loads Into Fake Uses
bool IsDead
This file defines generic set operations that may be used on set's of different types,...
This file defines the SmallSet class.
#define LLVM_DEBUG(...)
Definition: Debug.h:119
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:165
iterator end()
Definition: DenseMap.h:81
Register isStoreToStackSlot(const MachineInstr &MI, int &FrameIndex) const override
If the specified machine instruction is a direct store to a stack slot, return the virtual or physica...
A set of register units used to track register liveness.
Definition: LiveRegUnits.h:31
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
TraversalOrder traverse(MachineFunction &MF)
void append(unsigned MBBNumber, unsigned Unit, int Def)
ArrayRef< ReachingDef > defs(unsigned MBBNumber, unsigned Unit) const
void replaceFront(unsigned MBBNumber, unsigned Unit, int Def)
void init(unsigned NumBlockIDs)
void prepend(unsigned MBBNumber, unsigned Unit, int Def)
void startBasicBlock(unsigned MBBNumber, unsigned NumRegUnits)
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
instr_iterator instr_begin()
iterator_range< livein_iterator > liveins() const
reverse_instr_iterator instr_rbegin()
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
reverse_instr_iterator instr_rend()
LLVM_ABI iterator getLastNonDebugInstr(bool SkipPseudoOp=true)
Returns an iterator to the last non-debug instruction in the basic block, or end().
MachineInstrBundleIterator< MachineInstr, true > reverse_iterator
instr_iterator instr_end()
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
unsigned getNumObjects() const
Return the number of objects.
int getObjectIndexBegin() const
Return the minimum frame object index.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Representation of each machine instruction.
Definition: MachineInstr.h:72
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:359
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
This class provides the reaching def analysis.
MachineInstr * getLocalLiveOutMIDef(MachineBasicBlock *MBB, Register Reg) const
Return the local MI that produces the live out value for Reg, or nullptr for a non-live out or non-lo...
void traverse()
Traverse the machine function, mapping definitions.
bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved forwards to just before To.
bool isRegUsedAfter(MachineInstr *MI, Register Reg) const
Return whether the given register is used after MI, whether it's a local use or a live out.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const
Return whether removing this instruction will have no effect on the program, returning the redundant ...
MachineInstr * getMIOperand(MachineInstr *MI, unsigned Idx) const
If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it.
void printAllReachingDefs(MachineFunction &MF)
void reset()
Re-run the analysis.
int getReachingDef(MachineInstr *MI, Register Reg) const
Provides the instruction id of the closest reaching def instruction of Reg that reaches MI,...
void init()
Initialize data structures.
void getGlobalUses(MachineInstr *MI, Register Reg, InstSet &Uses) const
Collect the users of the value stored in Reg, which is defined by MI.
void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const
Assuming MI is dead, recursively search the incoming operands which are killed by MI and collect thos...
bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved backwards to just after To.
void getLiveOuts(MachineBasicBlock *MBB, Register Reg, InstSet &Defs, BlockSet &VisitedBBs) const
Search MBB for a definition of Reg and insert it into Defs.
int getClearance(MachineInstr *MI, Register Reg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Reg ...
bool hasLocalDefBefore(MachineInstr *MI, Register Reg) const
Provide whether the register has been defined in the same basic block as, and before,...
bool isReachingDefLiveOut(MachineInstr *MI, Register Reg) const
Return whether the reaching def for MI also is live out of its parent block.
bool getLiveInUses(MachineBasicBlock *MBB, Register Reg, InstSet &Uses) const
For the given block, collect the instructions that use the live-in value of the provided register.
bool isSafeToDefRegAt(MachineInstr *MI, Register Reg) const
Return whether a MachineInstr could be inserted at MI and safely define the given register without af...
bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, Register Reg) const
Return whether A and B use the same def of Reg.
void getReachingLocalUses(MachineInstr *MI, Register Reg, InstSet &Uses) const
Provides the uses, in the same block as MI, of register that MI defines.
bool isRegDefinedAfter(MachineInstr *MI, Register Reg) const
Return whether the given register is defined after MI.
MachineInstr * getUniqueReachingMIDef(MachineInstr *MI, Register Reg) const
If a single MachineInstr creates the reaching definition, then return it.
void getGlobalReachingDefs(MachineInstr *MI, Register Reg, InstSet &Defs) const
Collect all possible definitions of the value stored in Reg, which is used by MI.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2StackSlot(int FI)
Convert a non-negative frame index to a stack slot register value.
Definition: Register.h:48
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:380
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:470
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:401
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:541
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:176
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
bool empty() const
Definition: SmallVector.h:82
size_t size() const
Definition: SmallVector.h:79
void resize(size_type N)
Definition: SmallVector.h:639
void push_back(const T &Elt)
Definition: SmallVector.h:414
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1197
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
@ FrameIndex
Definition: ISDOpcodes.h:90
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
LLVM_ABI Printable printRegUnit(unsigned Unit, const TargetRegisterInfo *TRI)
Create Printable object to print register units on a raw_ostream.
bool set_is_subset(const S1Ty &S1, const S2Ty &S2)
set_is_subset(A, B) - Return true iff A in B
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2155
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1669
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:207
auto instructionsWithoutDebug(IterT It, IterT End, bool SkipPseudoOp=true)
Construct a range iterator which begins at It and moves forwards until End is reached,...
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
MachineBasicBlock * MBB
The basic block.
Definition: LoopTraversal.h:89
bool IsDone
True if the block that is ready for its final round of processing.
Definition: LoopTraversal.h:95
bool PrimaryPass
True if this is the first time we process the basic block.
Definition: LoopTraversal.h:92