LLVM 19.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"
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 (MCRegUnit Unit : TRI->regunits(LI.PhysReg)) {
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 (MCRegUnit Unit : TRI->regunits(MO.getReg().asMCReg())) {
132 // This instruction explicitly defines the current reg unit.
133 LLVM_DEBUG(dbgs() << printRegUnit(Unit, TRI) << ":\t" << CurInstr << '\t'
134 << *MI);
135
136 // How many instructions since this reg unit was last written?
137 if (LiveRegs[Unit] != CurInstr) {
138 LiveRegs[Unit] = CurInstr;
139 MBBReachingDefs[MBBNumber][Unit].push_back(CurInstr);
140 }
141 }
142 }
143 InstIds[MI] = CurInstr;
144 ++CurInstr;
145}
146
147void ReachingDefAnalysis::reprocessBasicBlock(MachineBasicBlock *MBB) {
148 unsigned MBBNumber = MBB->getNumber();
149 assert(MBBNumber < MBBReachingDefs.size() &&
150 "Unexpected basic block number.");
151
152 // Count number of non-debug instructions for end of block adjustment.
153 auto NonDbgInsts =
155 int NumInsts = std::distance(NonDbgInsts.begin(), NonDbgInsts.end());
156
157 // When reprocessing a block, the only thing we need to do is check whether
158 // there is now a more recent incoming reaching definition from a predecessor.
160 assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
161 "Should have pre-allocated MBBInfos for all MBBs");
162 const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
163 // Incoming may be empty for dead predecessors.
164 if (Incoming.empty())
165 continue;
166
167 for (unsigned Unit = 0; Unit != NumRegUnits; ++Unit) {
168 int Def = Incoming[Unit];
169 if (Def == ReachingDefDefaultVal)
170 continue;
171
172 auto Start = MBBReachingDefs[MBBNumber][Unit].begin();
173 if (Start != MBBReachingDefs[MBBNumber][Unit].end() && *Start < 0) {
174 if (*Start >= Def)
175 continue;
176
177 // Update existing reaching def from predecessor to a more recent one.
178 *Start = Def;
179 } else {
180 // Insert new reaching def from predecessor.
181 MBBReachingDefs[MBBNumber][Unit].insert(Start, Def);
182 }
183
184 // Update reaching def at end of BB. Keep in mind that these are
185 // adjusted relative to the end of the basic block.
186 if (MBBOutRegsInfos[MBBNumber][Unit] < Def - NumInsts)
187 MBBOutRegsInfos[MBBNumber][Unit] = Def - NumInsts;
188 }
189 }
190}
191
192void ReachingDefAnalysis::processBasicBlock(
193 const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
194 MachineBasicBlock *MBB = TraversedMBB.MBB;
196 << (!TraversedMBB.IsDone ? ": incomplete\n"
197 : ": all preds known\n"));
198
199 if (!TraversedMBB.PrimaryPass) {
200 // Reprocess MBB that is part of a loop.
201 reprocessBasicBlock(MBB);
202 return;
203 }
204
205 enterBasicBlock(MBB);
206 for (MachineInstr &MI :
208 processDefs(&MI);
209 leaveBasicBlock(MBB);
210}
211
213 MF = &mf;
214 TRI = MF->getSubtarget().getRegisterInfo();
215 LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
216 init();
217 traverse();
218 return false;
219}
220
222 // Clear the internal vectors.
223 MBBOutRegsInfos.clear();
224 MBBReachingDefs.clear();
225 InstIds.clear();
226 LiveRegs.clear();
227}
228
231 init();
232 traverse();
233}
234
236 NumRegUnits = TRI->getNumRegUnits();
237 MBBReachingDefs.resize(MF->getNumBlockIDs());
238 // Initialize the MBBOutRegsInfos
239 MBBOutRegsInfos.resize(MF->getNumBlockIDs());
240 LoopTraversal Traversal;
241 TraversedMBBOrder = Traversal.traverse(*MF);
242}
243
245 // Traverse the basic blocks.
246 for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder)
247 processBasicBlock(TraversedMBB);
248#ifndef NDEBUG
249 // Make sure reaching defs are sorted and unique.
250 for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
251 for (MBBRegUnitDefs &RegUnitDefs : MBBDefs) {
252 int LastDef = ReachingDefDefaultVal;
253 for (int Def : RegUnitDefs) {
254 assert(Def > LastDef && "Defs must be sorted and unique");
255 LastDef = Def;
256 }
257 }
258 }
259#endif
260}
261
263 MCRegister PhysReg) const {
264 assert(InstIds.count(MI) && "Unexpected machine instuction.");
265 int InstId = InstIds.lookup(MI);
266 int DefRes = ReachingDefDefaultVal;
267 unsigned MBBNumber = MI->getParent()->getNumber();
268 assert(MBBNumber < MBBReachingDefs.size() &&
269 "Unexpected basic block number.");
270 int LatestDef = ReachingDefDefaultVal;
271 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
272 for (int Def : MBBReachingDefs[MBBNumber][Unit]) {
273 if (Def >= InstId)
274 break;
275 DefRes = Def;
276 }
277 LatestDef = std::max(LatestDef, DefRes);
278 }
279 return LatestDef;
280}
281
283ReachingDefAnalysis::getReachingLocalMIDef(MachineInstr *MI,
284 MCRegister PhysReg) const {
285 return hasLocalDefBefore(MI, PhysReg)
286 ? getInstFromId(MI->getParent(), getReachingDef(MI, PhysReg))
287 : nullptr;
288}
289
291 MCRegister PhysReg) const {
292 MachineBasicBlock *ParentA = A->getParent();
293 MachineBasicBlock *ParentB = B->getParent();
294 if (ParentA != ParentB)
295 return false;
296
297 return getReachingDef(A, PhysReg) == getReachingDef(B, PhysReg);
298}
299
300MachineInstr *ReachingDefAnalysis::getInstFromId(MachineBasicBlock *MBB,
301 int InstId) const {
302 assert(static_cast<size_t>(MBB->getNumber()) < MBBReachingDefs.size() &&
303 "Unexpected basic block number.");
304 assert(InstId < static_cast<int>(MBB->size()) &&
305 "Unexpected instruction id.");
306
307 if (InstId < 0)
308 return nullptr;
309
310 for (auto &MI : *MBB) {
311 auto F = InstIds.find(&MI);
312 if (F != InstIds.end() && F->second == InstId)
313 return &MI;
314 }
315
316 return nullptr;
317}
318
320 MCRegister PhysReg) const {
321 assert(InstIds.count(MI) && "Unexpected machine instuction.");
322 return InstIds.lookup(MI) - getReachingDef(MI, PhysReg);
323}
324
326 MCRegister PhysReg) const {
327 return getReachingDef(MI, PhysReg) >= 0;
328}
329
331 MCRegister PhysReg,
332 InstSet &Uses) const {
333 MachineBasicBlock *MBB = Def->getParent();
335 while (++MI != MBB->end()) {
336 if (MI->isDebugInstr())
337 continue;
338
339 // If/when we find a new reaching def, we know that there's no more uses
340 // of 'Def'.
341 if (getReachingLocalMIDef(&*MI, PhysReg) != Def)
342 return;
343
344 for (auto &MO : MI->operands()) {
345 if (!isValidRegUseOf(MO, PhysReg, TRI))
346 continue;
347
348 Uses.insert(&*MI);
349 if (MO.isKill())
350 return;
351 }
352 }
353}
354
356 MCRegister PhysReg,
357 InstSet &Uses) const {
358 for (MachineInstr &MI :
360 for (auto &MO : MI.operands()) {
361 if (!isValidRegUseOf(MO, PhysReg, TRI))
362 continue;
363 if (getReachingDef(&MI, PhysReg) >= 0)
364 return false;
365 Uses.insert(&MI);
366 }
367 }
368 auto Last = MBB->getLastNonDebugInstr();
369 if (Last == MBB->end())
370 return true;
371 return isReachingDefLiveOut(&*Last, PhysReg);
372}
373
375 InstSet &Uses) const {
376 MachineBasicBlock *MBB = MI->getParent();
377
378 // Collect the uses that each def touches within the block.
379 getReachingLocalUses(MI, PhysReg, Uses);
380
381 // Handle live-out values.
382 if (auto *LiveOut = getLocalLiveOutMIDef(MI->getParent(), PhysReg)) {
383 if (LiveOut != MI)
384 return;
385
388 while (!ToVisit.empty()) {
390 if (Visited.count(MBB) || !MBB->isLiveIn(PhysReg))
391 continue;
392 if (getLiveInUses(MBB, PhysReg, Uses))
393 llvm::append_range(ToVisit, MBB->successors());
394 Visited.insert(MBB);
395 }
396 }
397}
398
400 MCRegister PhysReg,
401 InstSet &Defs) const {
402 if (auto *Def = getUniqueReachingMIDef(MI, PhysReg)) {
403 Defs.insert(Def);
404 return;
405 }
406
407 for (auto *MBB : MI->getParent()->predecessors())
408 getLiveOuts(MBB, PhysReg, Defs);
409}
410
412 MCRegister PhysReg, InstSet &Defs) const {
414 getLiveOuts(MBB, PhysReg, Defs, VisitedBBs);
415}
416
418 MCRegister PhysReg, InstSet &Defs,
419 BlockSet &VisitedBBs) const {
420 if (VisitedBBs.count(MBB))
421 return;
422
423 VisitedBBs.insert(MBB);
424 LiveRegUnits LiveRegs(*TRI);
425 LiveRegs.addLiveOuts(*MBB);
426 if (LiveRegs.available(PhysReg))
427 return;
428
429 if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
430 Defs.insert(Def);
431 else
432 for (auto *Pred : MBB->predecessors())
433 getLiveOuts(Pred, PhysReg, Defs, VisitedBBs);
434}
435
438 MCRegister PhysReg) const {
439 // If there's a local def before MI, return it.
440 MachineInstr *LocalDef = getReachingLocalMIDef(MI, PhysReg);
441 if (LocalDef && InstIds.lookup(LocalDef) < InstIds.lookup(MI))
442 return LocalDef;
443
445 MachineBasicBlock *Parent = MI->getParent();
446 for (auto *Pred : Parent->predecessors())
447 getLiveOuts(Pred, PhysReg, Incoming);
448
449 // Check that we have a single incoming value and that it does not
450 // come from the same block as MI - since it would mean that the def
451 // is executed after MI.
452 if (Incoming.size() == 1 && (*Incoming.begin())->getParent() != Parent)
453 return *Incoming.begin();
454 return nullptr;
455}
456
458 unsigned Idx) const {
459 assert(MI->getOperand(Idx).isReg() && "Expected register operand");
460 return getUniqueReachingMIDef(MI, MI->getOperand(Idx).getReg());
461}
462
464 MachineOperand &MO) const {
465 assert(MO.isReg() && "Expected register operand");
466 return getUniqueReachingMIDef(MI, MO.getReg());
467}
468
470 MCRegister PhysReg) const {
471 MachineBasicBlock *MBB = MI->getParent();
472 LiveRegUnits LiveRegs(*TRI);
473 LiveRegs.addLiveOuts(*MBB);
474
475 // Yes if the register is live out of the basic block.
476 if (!LiveRegs.available(PhysReg))
477 return true;
478
479 // Walk backwards through the block to see if the register is live at some
480 // point.
481 for (MachineInstr &Last :
483 LiveRegs.stepBackward(Last);
484 if (!LiveRegs.available(PhysReg))
485 return InstIds.lookup(&Last) > InstIds.lookup(MI);
486 }
487 return false;
488}
489
491 MCRegister PhysReg) const {
492 MachineBasicBlock *MBB = MI->getParent();
493 auto Last = MBB->getLastNonDebugInstr();
494 if (Last != MBB->end() &&
495 getReachingDef(MI, PhysReg) != getReachingDef(&*Last, PhysReg))
496 return true;
497
498 if (auto *Def = getLocalLiveOutMIDef(MBB, PhysReg))
499 return Def == getReachingLocalMIDef(MI, PhysReg);
500
501 return false;
502}
503
505 MCRegister PhysReg) const {
506 MachineBasicBlock *MBB = MI->getParent();
507 LiveRegUnits LiveRegs(*TRI);
508 LiveRegs.addLiveOuts(*MBB);
509 if (LiveRegs.available(PhysReg))
510 return false;
511
512 auto Last = MBB->getLastNonDebugInstr();
513 int Def = getReachingDef(MI, PhysReg);
514 if (Last != MBB->end() && getReachingDef(&*Last, PhysReg) != Def)
515 return false;
516
517 // Finally check that the last instruction doesn't redefine the register.
518 for (auto &MO : Last->operands())
519 if (isValidRegDefOf(MO, PhysReg, TRI))
520 return false;
521
522 return true;
523}
524
527 MCRegister PhysReg) const {
528 LiveRegUnits LiveRegs(*TRI);
529 LiveRegs.addLiveOuts(*MBB);
530 if (LiveRegs.available(PhysReg))
531 return nullptr;
532
533 auto Last = MBB->getLastNonDebugInstr();
534 if (Last == MBB->end())
535 return nullptr;
536
537 int Def = getReachingDef(&*Last, PhysReg);
538 for (auto &MO : Last->operands())
539 if (isValidRegDefOf(MO, PhysReg, TRI))
540 return &*Last;
541
542 return Def < 0 ? nullptr : getInstFromId(MBB, Def);
543}
544
546 return MI.mayLoadOrStore() || MI.mayRaiseFPException() ||
547 MI.hasUnmodeledSideEffects() || MI.isTerminator() ||
548 MI.isCall() || MI.isBarrier() || MI.isBranch() || MI.isReturn();
549}
550
551// Can we safely move 'From' to just before 'To'? To satisfy this, 'From' must
552// not define a register that is used by any instructions, after and including,
553// 'To'. These instructions also must not redefine any of Froms operands.
554template<typename Iterator>
555bool ReachingDefAnalysis::isSafeToMove(MachineInstr *From,
556 MachineInstr *To) const {
557 if (From->getParent() != To->getParent() || From == To)
558 return false;
559
560 SmallSet<int, 2> Defs;
561 // First check that From would compute the same value if moved.
562 for (auto &MO : From->operands()) {
563 if (!isValidReg(MO))
564 continue;
565 if (MO.isDef())
566 Defs.insert(MO.getReg());
567 else if (!hasSameReachingDef(From, To, MO.getReg()))
568 return false;
569 }
570
571 // Now walk checking that the rest of the instructions will compute the same
572 // value and that we're not overwriting anything. Don't move the instruction
573 // past any memory, control-flow or other ambiguous instructions.
574 for (auto I = ++Iterator(From), E = Iterator(To); I != E; ++I) {
575 if (mayHaveSideEffects(*I))
576 return false;
577 for (auto &MO : I->operands())
578 if (MO.isReg() && MO.getReg() && Defs.count(MO.getReg()))
579 return false;
580 }
581 return true;
582}
583
585 MachineInstr *To) const {
586 using Iterator = MachineBasicBlock::iterator;
587 // Walk forwards until we find the instruction.
588 for (auto I = Iterator(From), E = From->getParent()->end(); I != E; ++I)
589 if (&*I == To)
590 return isSafeToMove<Iterator>(From, To);
591 return false;
592}
593
595 MachineInstr *To) const {
597 // Walk backwards until we find the instruction.
598 for (auto I = Iterator(From), E = From->getParent()->rend(); I != E; ++I)
599 if (&*I == To)
600 return isSafeToMove<Iterator>(From, To);
601 return false;
602}
603
605 InstSet &ToRemove) const {
608 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
609}
610
611bool
613 InstSet &Ignore) const {
615 return isSafeToRemove(MI, Visited, ToRemove, Ignore);
616}
617
618bool
620 InstSet &ToRemove, InstSet &Ignore) const {
621 if (Visited.count(MI) || Ignore.count(MI))
622 return true;
623 else if (mayHaveSideEffects(*MI)) {
624 // Unless told to ignore the instruction, don't remove anything which has
625 // side effects.
626 return false;
627 }
628
629 Visited.insert(MI);
630 for (auto &MO : MI->operands()) {
631 if (!isValidRegDef(MO))
632 continue;
633
635 getGlobalUses(MI, MO.getReg(), Uses);
636
637 for (auto *I : Uses) {
638 if (Ignore.count(I) || ToRemove.count(I))
639 continue;
640 if (!isSafeToRemove(I, Visited, ToRemove, Ignore))
641 return false;
642 }
643 }
644 ToRemove.insert(MI);
645 return true;
646}
647
649 InstSet &Dead) const {
650 Dead.insert(MI);
651 auto IsDead = [this, &Dead](MachineInstr *Def, MCRegister PhysReg) {
652 if (mayHaveSideEffects(*Def))
653 return false;
654
655 unsigned LiveDefs = 0;
656 for (auto &MO : Def->operands()) {
657 if (!isValidRegDef(MO))
658 continue;
659 if (!MO.isDead())
660 ++LiveDefs;
661 }
662
663 if (LiveDefs > 1)
664 return false;
665
667 getGlobalUses(Def, PhysReg, Uses);
668 return llvm::set_is_subset(Uses, Dead);
669 };
670
671 for (auto &MO : MI->operands()) {
672 if (!isValidRegUse(MO))
673 continue;
674 if (MachineInstr *Def = getMIOperand(MI, MO))
675 if (IsDead(Def, MO.getReg()))
676 collectKilledOperands(Def, Dead);
677 }
678}
679
681 MCRegister PhysReg) const {
683 return isSafeToDefRegAt(MI, PhysReg, Ignore);
684}
685
687 InstSet &Ignore) const {
688 // Check for any uses of the register after MI.
689 if (isRegUsedAfter(MI, PhysReg)) {
690 if (auto *Def = getReachingLocalMIDef(MI, PhysReg)) {
692 getGlobalUses(Def, PhysReg, Uses);
694 return false;
695 } else
696 return false;
697 }
698
699 MachineBasicBlock *MBB = MI->getParent();
700 // Check for any defs after MI.
701 if (isRegDefinedAfter(MI, PhysReg)) {
703 for (auto E = MBB->end(); I != E; ++I) {
704 if (Ignore.count(&*I))
705 continue;
706 for (auto &MO : I->operands())
707 if (isValidRegDefOf(MO, PhysReg, TRI))
708 return false;
709 }
710 }
711 return true;
712}
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
A set of register units.
#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 register units used to track register liveness.
Definition: LiveRegUnits.h:30
bool available(MCPhysReg Reg) const
Returns true if no part of physical register Reg is live.
Definition: LiveRegUnits.h:116
void stepBackward(const MachineInstr &MI)
Updates liveness when stepping backwards over the instruction MI.
void addLiveOuts(const MachineBasicBlock &MBB)
Adds registers living out of 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.
iterator_range< MCRegUnitIterator > regunits(MCRegister Reg) const
Returns an iterator range over all regunits for Reg.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
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()
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.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:327
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...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
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:818
void resize(size_type N)
Definition: SmallVector.h:651
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
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
NodeAddr< DefNode * > Def
Definition: RDFGraph.h:384
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 range R to container C.
Definition: STLExtras.h:2082
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.
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