LLVM 17.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
9#include "llvm/ADT/SmallSet.h"
15#include "llvm/Support/Debug.h"
16
17using namespace llvm;
18
19#define DEBUG_TYPE "reaching-deps-analysis"
20
22INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
23 true)
24
25static bool isValidReg(const MachineOperand &MO) {
26 return MO.isReg() && MO.getReg();
27}
28
29static bool isValidRegUse(const MachineOperand &MO) {
30 return isValidReg(MO) && MO.isUse();
31}
32
33static bool isValidRegUseOf(const MachineOperand &MO, MCRegister PhysReg,
34 const TargetRegisterInfo *TRI) {
35 if (!isValidRegUse(MO))
36 return false;
37 return TRI->regsOverlap(MO.getReg(), PhysReg);
38}
39
40static bool isValidRegDef(const MachineOperand &MO) {
41 return isValidReg(MO) && MO.isDef();
42}
43
44static bool isValidRegDefOf(const MachineOperand &MO, MCRegister PhysReg,
45 const TargetRegisterInfo *TRI) {
46 if (!isValidRegDef(MO))
47 return false;
48 return TRI->regsOverlap(MO.getReg(), PhysReg);
49}
50
51void ReachingDefAnalysis::enterBasicBlock(MachineBasicBlock *MBB) {
52 unsigned MBBNumber = MBB->getNumber();
53 assert(MBBNumber < MBBReachingDefs.size() &&
54 "Unexpected basic block number.");
55 MBBReachingDefs[MBBNumber].resize(NumRegUnits);
56
57 // Reset instruction counter in each basic block.
58 CurInstr = 0;
59
60 // Set up LiveRegs to represent registers entering MBB.
61 // Default values are 'nothing happened a long time ago'.
62 if (LiveRegs.empty())
63 LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
64
65 // This is the entry block.
66 if (MBB->pred_empty()) {
67 for (const auto &LI : MBB->liveins()) {
68 for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); ++Unit) {
69 // Treat function live-ins as if they were defined just before the first
70 // instruction. Usually, function arguments are set up immediately
71 // before the call.
72 if (LiveRegs[*Unit] != -1) {
73 LiveRegs[*Unit] = -1;
74 MBBReachingDefs[MBBNumber][*Unit].push_back(-1);
75 }
76 }
77 }
78 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
79 return;
80 }
81
82 // Try to coalesce live-out registers from predecessors.
84 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
85 "Should have pre-allocated MBBInfos for all MBBs");
86 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
87 // Incoming is null if this is a backedge from a BB
88 // we haven't processed yet
89 if (Incoming.empty())
90 continue;
91
92 // Find the most recent reaching definition from a predecessor.
93 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
94 LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
95 }
96
97 // Insert the most recent reaching definition we found.
98 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit)
99 if (LiveRegs[Unit] != ReachingDefDefaultVal)
100 MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
101}
102
103void ReachingDefAnalysis::leaveBasicBlock(MachineBasicBlock *MBB) {
104 assert(!LiveRegs.empty() && "Must enter basic block first.");
105 unsigned MBBNumber = MBB->getNumber();
106 assert(MBBNumber < MBBOutRegsInfos.size() &&
107 "Unexpected basic block number.");
108 // Save register clearances at end of MBB - used by enterBasicBlock().
109 MBBOutRegsInfos[MBBNumber] = LiveRegs;
110
111 // While processing the basic block, we kept `Def` relative to the start
112 // of the basic block for convenience. However, future use of this information
113 // only cares about the clearance from the end of the block, so adjust
114 // everything to be relative to the end of the basic block.
115 for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
116 if (OutLiveReg != ReachingDefDefaultVal)
117 OutLiveReg -= CurInstr;
118 LiveRegs.clear();
119}
120
121void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
122 assert(!MI->isDebugInstr() && "Won't process debug instructions");
123
124 unsigned MBBNumber = MI->getParent()->getNumber();
125 assert(MBBNumber < MBBReachingDefs.size() &&
126 "Unexpected basic block number.");
127
128 for (auto &MO : MI->operands()) {
129 if (!isValidRegDef(MO))
130 continue;
131 for (MCRegUnitIterator Unit(MO.getReg().asMCReg(), TRI); Unit.isValid();
132 ++Unit) {
133 // This instruction explicitly defines the current reg unit.
134 LLVM_DEBUG(dbgs() << printRegUnit(*Unit, TRI) << ":\t" << CurInstr
135 << '\t' << *MI);
136
137 // How many instructions since this reg unit was last written?
138 if (LiveRegs[*Unit] != CurInstr) {
139 LiveRegs[*Unit] = CurInstr;
140 MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
141 }
142 }
143 }
144 InstIds[MI] = CurInstr;
145 ++CurInstr;
146}
147
148void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
149 unsigned MBBNumber = MBB->getNumber();
150 assert(MBBNumber < MBBReachingDefs.size() &&
151 "Unexpected basic block number.");
152
153 // Count number of non-debug instructions for end of block adjustment.
154 auto NonDbgInsts =
156 int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
157
158 // When reprocessing a block, the only thing we need to do is check whether
159 // there is now a more recent incoming reaching definition from a predecessor.
161 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
162 "Should have pre-allocated MBBInfos for all MBBs");
163 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
164 // Incoming may be empty for dead predecessors.
165 if (Incoming.empty())
166 continue;
167
168 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
169 int Def = Incoming[Unit];
170 if (Def == ReachingDefDefaultVal)
171 continue;
172
173 auto Start = MBBReachingDefs[MBBNumber][Unit].begin();
174 if (Start != MBBReachingDefs[MBBNumber][Unit].end() && *Start < 0) {
175 if (*Start >= Def)
176 continue;
177
178 // Update existing reaching def from predecessor to a more recent one.
179 *Start = Def;
180 } else {
181 // Insert new reaching def from predecessor.
182 MBBReachingDefs[MBBNumber][Unit].insert(Start, Def);
183 }
184
185 // Update reaching def at end of of BB. Keep in mind that these are
186 // adjusted relative to the end of the basic block.
187 if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
188 MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts;
189 }
190 }
191}
192
193void ReachingDefAnalysis::processBasicBlock(
194 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
195 MachineBasicBlock *MBB = TraversedMBB.MBB;
197 << (!TraversedMBB.IsDone ? ": incomplete\n"
198 : ": all preds known\n"));
199
200 if (!TraversedMBB.PrimaryPass) {
201 // Reprocess MBB that is part of a loop.
202 reprocessBasicBlock(MBB);
203 return;
204 }
205
206 enterBasicBlock(MBB);
207 for (MachineInstr &MI :
209 processDefs(&MI);
210 leaveBasicBlock(MBB);
211}
212
214 MF = &mf;
215 TRI = MF->getSubtarget().getRegisterInfo();
216 LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
217 init();
218 traverse();
219 return false;
220}
221
223 // Clear the internal vectors.
224 MBBOutRegsInfos.clear();
225 MBBReachingDefs.clear();
226 InstIds.clear();
227 LiveRegs.clear();
228}
229
232 init();
233 traverse();
234}
235
237 NumRegUnits = TRI->getNumRegUnits();
238 MBBReachingDefs.resize(MF->getNumBlockIDs());
239 // Initialize the MBBOutRegsInfos
240 MBBOutRegsInfos.resize(MF->getNumBlockIDs());
241 LoopTraversal Traversal;
242 TraversedMBBOrder = Traversal.traverse(*MF);
243}
244
246 // Traverse the basic blocks.
247 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
248 processBasicBlock(TraversedMBB);
249#ifndef NDEBUG
250 // Make sure reaching defs are sorted and unique.
251 for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
252 for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) {
253 int LastDef = ReachingDefDefaultVal;
254 for (int Def : RegUnitDefs) {
255 assert(Def > LastDef && "Defs must be sorted and unique");
256 LastDef = Def;
257 }
258 }
259 }
260#endif
261}
262
264 MCRegister PhysReg) const {
265 assert(InstIds.count(MI) && "Unexpected machine instuction.");
266 int InstId = InstIds.lookup(MI);
267 int DefRes = ReachingDefDefaultVal;
268 unsigned MBBNumber = MI->getParent()->getNumber();
269 assert(MBBNumber < MBBReachingDefs.size() &&
270 "Unexpected basic block number.");
271 int LatestDef = ReachingDefDefaultVal;
272 for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); ++Unit) {
273 for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
274 if (Def >= InstId)
275 break;
276 DefRes = Def;
277 }
278 LatestDef = std::max(LatestDef, DefRes);
279 }
280 return LatestDef;
281}
282
284ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
285 MCRegister PhysReg) const {
286 return hasLocalDefBefore(MI, PhysReg)
287 ? getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg))
288 : nullptr;
289}
290
292 MCRegister PhysReg) const {
293 MachineBasicBlock *ParentA = A->getParent();
294 MachineBasicBlock *ParentB = B->getParent();
295 if (ParentA != ParentB)
296 return false;
297
298 return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
299}
300
301MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
302 int InstId) const {
303 assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
304 "Unexpected basic block number.");
305 assert(InstId < static_cast<int>(MBB->size()) &&
306 "Unexpected instruction id.");
307
308 if (InstId < 0)
309 return nullptr;
310
311 for (auto &MI : *MBB) {
312 auto F = InstIds.find(&MI);
313 if (F != InstIds.end() && F->second == InstId)
314 return &MI;
315 }
316
317 return nullptr;
318}
319
321 MCRegister PhysReg) const {
322 assert(InstIds.count(MI) && "Unexpected machine instuction.");
323 return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
324}
325
327 MCRegister PhysReg) const {
328 return getReachingDef(MI, PhysReg) >= 0;
329}
330
332 MCRegister PhysReg,
333 InstSet &Uses) const {
334 MachineBasicBlock *MBB = Def->getParent();
336 while (++MI != MBB->end()) {
337 if (MI->isDebugInstr())
338 continue;
339
340 // If/when we find a new reaching def, we know that there's no more uses
341 // of 'Def'.
342 if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
343 return;
344
345 for (auto &MO : MI->operands()) {
346 if (!isValidRegUseOf(MO, PhysReg, TRI))
347 continue;
348
349 Uses.insert(&*MI);
350 if (MO.isKill())
351 return;
352 }
353 }
354}
355
357 MCRegister PhysReg,
358 InstSet &Uses) const {
359 for (MachineInstr &MI :
361 for (auto &MO : MI.operands()) {
362 if (!isValidRegUseOf(MO, PhysReg, TRI))
363 continue;
364 if (getReachingDef(&MI, PhysReg) >= 0)
365 return false;
366 Uses.insert(&MI);
367 }
368 }
369 auto Last = MBB->getLastNonDebugInstr();
370 if (Last == MBB->end())
371 return true;
372 return isReachingDefLiveOut(&*Last, PhysReg);
373}
374
376 InstSet &Uses) const {
377 MachineBasicBlock *MBB = MI->getParent();
378
379 // Collect the uses that each def touches within the block.
380 getReachingLocalUses(MI, PhysReg, Uses);
381
382 // Handle live-out values.
383 if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), PhysReg)) {
384 if (LiveOut != MI)
385 return;
386
389 while (!ToVisit.empty()) {
391 if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
392 continue;
393 if (getLiveInUses(MBB, PhysReg, Uses))
394 llvm::append_range(ToVisit, MBB->successors());
395 Visited.insert(MBB);
396 }
397 }
398}
399
401 MCRegister PhysReg,
402 InstSet &Defs) const {
403 if (auto *Def = getUniqueReachingMIDef(MI, PhysReg)) {
404 Defs.insert(Def);
405 return;
406 }
407
408 for (auto *MBB : MI->getParent()->predecessors())
409 getLiveOuts(MBB, PhysReg, Defs);
410}
411
413 MCRegister PhysReg, InstSet &Defs) const {
415 getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
416}
417
419 MCRegister PhysReg, InstSet &Defs,
420 BlockSet &VisitedBBs) const {
421 if (VisitedBBs.count(MBB))
422 return;
423
424 VisitedBBs.insert(MBB);
425 LivePhysRegs LiveRegs(*TRI);
426 LiveRegs.addLiveOuts(*MBB);
427 if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
428 return;
429
430 if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
431 Defs.insert(Def);
432 else
433 for (auto *Pred : MBB->predecessors())
434 getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
435}
436
439 MCRegister PhysReg) const {
440 // If there's a local def before MI, return it.
441 MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
442 if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
443 return LocalDef;
444
446 MachineBasicBlock *Parent = MI->getParent();
447 for (auto *Pred : Parent->predecessors())
448 getLiveOuts(Pred, PhysReg, Incoming);
449
450 // Check that we have a single incoming value and that it does not
451 // come from the same block as MI - since it would mean that the def
452 // is executed after MI.
453 if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
454 return *Incoming.begin();
455 return nullptr;
456}
457
459 unsigned Idx) const {
460 assert(MI->getOperand(Idx).isReg() && "Expected register operand");
461 return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
462}
463
465 MachineOperand &MO) const {
466 assert(MO.isReg() && "Expected register operand");
467 return getUniqueReachingMIDef(MI, MO.getReg());
468}
469
471 MCRegister PhysReg) const {
472 MachineBasicBlock *MBB = MI->getParent();
473 LivePhysRegs LiveRegs(*TRI);
474 LiveRegs.addLiveOuts(*MBB);
475
476 // Yes if the register is live out of the basic block.
477 if (!LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
478 return true;
479
480 // Walk backwards through the block to see if the register is live at some
481 // point.
482 for (MachineInstr &Last :
484 LiveRegs.stepBackward(Last);
485 if (!LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
486 return InstIds.lookup(&Last) > InstIds.lookup(MI);
487 }
488 return false;
489}
490
492 MCRegister PhysReg) const {
493 MachineBasicBlock *MBB = MI->getParent();
494 auto Last = MBB->getLastNonDebugInstr();
495 if (Last != MBB->end() &&
496 getReachingDef(MI, PhysReg) != getReachingDef(&*Last, PhysReg))
497 return true;
498
499 if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
500 return Def == getReachingLocalMIDef(MI, PhysReg);
501
502 return false;
503}
504
506 MCRegister PhysReg) const {
507 MachineBasicBlock *MBB = MI->getParent();
508 LivePhysRegs LiveRegs(*TRI);
509 LiveRegs.addLiveOuts(*MBB);
510 if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
511 return false;
512
513 auto Last = MBB->getLastNonDebugInstr();
514 int Def = getReachingDef(MI, PhysReg);
515 if (Last != MBB->end() && getReachingDef(&*Last, PhysReg) != Def)
516 return false;
517
518 // Finally check that the last instruction doesn't redefine the register.
519 for (auto &MO : Last->operands())
520 if (isValidRegDefOf(MO, PhysReg, TRI))
521 return false;
522
523 return true;
524}
525
528 MCRegister PhysReg) const {
529 LivePhysRegs LiveRegs(*TRI);
530 LiveRegs.addLiveOuts(*MBB);
531 if (LiveRegs.available(MBB->getParent()->getRegInfo(), PhysReg))
532 return nullptr;
533
534 auto Last = MBB->getLastNonDebugInstr();
535 if (Last == MBB->end())
536 return nullptr;
537
538 int Def = getReachingDef(&*Last, PhysReg);
539 for (auto &MO : Last->operands())
540 if (isValidRegDefOf(MO, PhysReg, TRI))
541 return &*Last;
542
543 return Def < 0 ? nullptr : getInstFromId(MBB, Def);
544}
545
547 return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
548 MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
549 MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
550}
551
552// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
553// not define a register that is used by any instructions, after and including,
554// 'To'. These instructions also must not redefine any of Froms operands.
555template<typename Iterator>
556bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
557 MachineInstr *To) const {
558 if (From->getParent() != To->getParent() || From == To)
559 return false;
560
561 SmallSet<int, 2> Defs;
562 // First check that From would compute the same value if moved.
563 for (auto &MO : From->operands()) {
564 if (!isValidReg(MO))
565 continue;
566 if (MO.isDef())
567 Defs.insert(MO.getReg());
568 else if (!hasSameReachingDef(From, To, MO.getReg()))
569 return false;
570 }
571
572 // Now walk checking that the rest of the instructions will compute the same
573 // value and that we're not overwriting anything. Don't move the instruction
574 // past any memory, control-flow or other ambiguous instructions.
575 for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
576 if (mayHaveSideEffects(*I))
577 return false;
578 for (auto &MO : I->operands())
579 if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
580 return false;
581 }
582 return true;
583}
584
586 MachineInstr *To) const {
587 using Iterator = MachineBasicBlock::iterator;
588 // Walk forwards until we find the instruction.
589 for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
590 if (&*I == To)
591 return isSafeToMove<Iterator>(From, To);
592 return false;
593}
594
596 MachineInstr *To) const {
598 // Walk backwards until we find the instruction.
599 for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
600 if (&*I == To)
601 return isSafeToMove<Iterator>(From, To);
602 return false;
603}
604
606 InstSet &ToRemove) const {
609 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
610}
611
612bool
614 InstSet &Ignore) const {
616 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
617}
618
619bool
621 InstSet &ToRemove, InstSet &Ignore) const {
622 if (Visited.count(MI) || Ignore.count(MI))
623 return true;
624 else if (mayHaveSideEffects(*MI)) {
625 // Unless told to ignore the instruction, don't remove anything which has
626 // side effects.
627 return false;
628 }
629
630 Visited.insert(MI);
631 for (auto &MO : MI->operands()) {
632 if (!isValidRegDef(MO))
633 continue;
634
636 getGlobalUses(MI, MO.getReg(), Uses);
637
638 for (auto *I : Uses) {
639 if (Ignore.count(I) || ToRemove.count(I))
640 continue;
641 if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
642 return false;
643 }
644 }
645 ToRemove.insert(MI);
646 return true;
647}
648
650 InstSet &Dead) const {
651 Dead.insert(MI);
652 auto IsDead = [this, &Dead](MachineInstr *Def, MCRegister PhysReg) {
653 if (mayHaveSideEffects(*Def))
654 return false;
655
656 unsigned LiveDefs = 0;
657 for (auto &MO : Def->operands()) {
658 if (!isValidRegDef(MO))
659 continue;
660 if (!MO.isDead())
661 ++LiveDefs;
662 }
663
664 if (LiveDefs > 1)
665 return false;
666
668 getGlobalUses(Def, PhysReg, Uses);
669 return llvm::set_is_subset(Uses, Dead);
670 };
671
672 for (auto &MO : MI->operands()) {
673 if (!isValidRegUse(MO))
674 continue;
675 if (MachineInstr *Def = getMIOperand(MI, MO))
676 if (IsDead(Def, MO.getReg()))
677 collectKilledOperands(Def, Dead);
678 }
679}
680
682 MCRegister PhysReg) const {
684 return isSafeToDefRegAt(MI, PhysReg, Ignore);
685}
686
688 InstSet &Ignore) const {
689 // Check for any uses of the register after MI.
690 if (isRegUsedAfter(MI, PhysReg)) {
691 if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
693 getGlobalUses(Def, PhysReg, Uses);
695 return false;
696 } else
697 return false;
698 }
699
700 MachineBasicBlock *MBB = MI->getParent();
701 // Check for any defs after MI.
702 if (isRegDefinedAfter(MI, PhysReg)) {
704 for (auto E = MBB->end(); I != E; ++I) {
705 if (Ignore.count(&*I))
706 continue;
707 for (auto &MO : I->operands())
708 if (isValidRegDefOf(MO, PhysReg, TRI))
709 return false;
710 }
711 }
712 return true;
713}
aarch64 promote const
MachineBasicBlock & MBB
ReachingDefAnalysis InstSet & ToRemove
ReachingDefAnalysis InstSet InstSet & Ignore
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
#define LLVM_DEBUG(X)
Definition: Debug.h:101
Rewrite Partial Register Uses
hexagon gen pred
IRTranslator LLVM IR MI
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static bool mayHaveSideEffects(MachineInstr &MI)
static bool isValidRegDefOf(const MachineOperand &MO, MCRegister PhysReg, const TargetRegisterInfo *TRI)
static bool isValidRegDef(const MachineOperand &MO)
static bool isValidRegUseOf(const MachineOperand &MO, MCRegister PhysReg, const TargetRegisterInfo *TRI)
static bool isValidRegUse(const MachineOperand &MO)
#define DEBUG_TYPE
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool IsDead
This file defines generic set operations that may be used on set's of different types,...
This file defines the SmallSet class.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:50
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
This class provides the basic blocks traversal order used by passes like ReachingDefAnalysis and Exec...
Definition: LoopTraversal.h:65
TraversalOrder traverse(MachineFunction &MF)
unsigned getNumRegUnits() const
Return the number of (native) register units in the target.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
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...
bool isLiveIn(MCPhysReg Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
reverse_instr_iterator instr_rend()
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()
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
MachineInstrBundleIterator< MachineInstr > iterator
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Representation of each machine instruction.
Definition: MachineInstr.h:68
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:320
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.
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 isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg) const
Return whether a MachineInstr could be inserted at MI and safely define the given register without af...
bool getLiveInUses(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Uses) const
For the given block, collect the instructions that use the live-in value of the provided register.
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 * getLocalLiveOutMIDef(MachineBasicBlock *MBB, MCRegister PhysReg) const
Return the local MI that produces the live out value for PhysReg, or nullptr for a non-live out or no...
MachineInstr * getMIOperand(MachineInstr *MI, unsigned Idx) const
If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it.
void getReachingLocalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const
Provides the uses, in the same block as MI, of register that MI defines.
void reset()
Re-run the analysis.
bool isRegUsedAfter(MachineInstr *MI, MCRegister PhysReg) const
Return whether the given register is used after MI, whether it's a local use or a live out.
bool hasLocalDefBefore(MachineInstr *MI, MCRegister PhysReg) const
Provide whether the register has been defined in the same basic block as, and before,...
void init()
Initialize data structures.
void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Defs, BlockSet &VisitedBBs) const
Search MBB for a definition of PhysReg and insert it into Defs.
bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, MCRegister PhysReg) const
Return whether A and B use the same def of PhysReg.
void getGlobalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const
Collect the users of the value stored in PhysReg, 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 isRegDefinedAfter(MachineInstr *MI, MCRegister PhysReg) const
Return whether the given register is defined after MI.
int getReachingDef(MachineInstr *MI, MCRegister PhysReg) const
Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI,...
bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved backwards to just after To.
void getGlobalReachingDefs(MachineInstr *MI, MCRegister PhysReg, InstSet &Defs) const
Collect all possible definitions of the value stored in PhysReg, which is used by MI.
MachineInstr * getUniqueReachingMIDef(MachineInstr *MI, MCRegister PhysReg) const
If a single MachineInstr creates the reaching definition, then return it.
bool isReachingDefLiveOut(MachineInstr *MI, MCRegister PhysReg) const
Return whether the reaching def for MI also is live out of its parent block.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
int getClearance(MachineInstr *MI, MCRegister PhysReg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
size_type size() const
Definition: SmallPtrSet.h:93
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
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:365
iterator begin() const
Definition: SmallPtrSet.h:403
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
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:179
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:809
void resize(size_type N)
Definition: SmallVector.h:642
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:29
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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 a range to a container.
Definition: STLExtras.h:2129
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
auto instructionsWithoutDebug(IterT It, IterT End, bool SkipPseudoOp=true)
Construct a range iterator which begins at It and moves forwards until End is reached,...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
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