LLVM 17.0.0git
MachineLoopUtils.cpp
Go to the documentation of this file.
1//=- MachineLoopUtils.cpp - Functions for manipulating loops ----------------=//
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
13using namespace llvm;
14
15namespace {
16// MI's parent and BB are clones of each other. Find the equivalent copy of MI
17// in BB.
18MachineInstr &findEquivalentInstruction(MachineInstr &MI,
20 MachineBasicBlock *PB = MI.getParent();
21 unsigned Offset = std::distance(PB->instr_begin(), MachineBasicBlock::instr_iterator(MI));
22 return *std::next(BB->instr_begin(), Offset);
23}
24} // namespace
25
29 const TargetInstrInfo *TII) {
30 MachineFunction &MF = *Loop->getParent();
31 MachineBasicBlock *Preheader = *Loop->pred_begin();
32 if (Preheader == Loop)
33 Preheader = *std::next(Loop->pred_begin());
34 MachineBasicBlock *Exit = *Loop->succ_begin();
35 if (Exit == Loop)
36 Exit = *std::next(Loop->succ_begin());
37
38 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(Loop->getBasicBlock());
39 if (Direction == LPD_Front)
40 MF.insert(Loop->getIterator(), NewBB);
41 else
42 MF.insert(std::next(Loop->getIterator()), NewBB);
43
45 auto InsertPt = NewBB->end();
46 for (MachineInstr &MI : *Loop) {
47 MachineInstr *NewMI = MF.CloneMachineInstr(&MI);
48 NewBB->insert(InsertPt, NewMI);
49 for (MachineOperand &MO : NewMI->defs()) {
50 Register OrigR = MO.getReg();
51 if (OrigR.isPhysical())
52 continue;
53 Register &R = Remaps[OrigR];
54 R = MRI.createVirtualRegister(MRI.getRegClass(OrigR));
55 MO.setReg(R);
56
57 if (Direction == LPD_Back) {
58 // Replace all uses outside the original loop with the new register.
59 // FIXME: is the use_iterator stable enough to mutate register uses
60 // while iterating?
62 for (auto &Use : MRI.use_operands(OrigR))
63 if (Use.getParent()->getParent() != Loop)
64 Uses.push_back(&Use);
65 for (auto *Use : Uses) {
66 const TargetRegisterClass *ConstrainRegClass =
67 MRI.constrainRegClass(R, MRI.getRegClass(Use->getReg()));
68 assert(ConstrainRegClass &&
69 "Expected a valid constrained register class!");
70 (void)ConstrainRegClass;
71 Use->setReg(R);
72 }
73 }
74 }
75 }
76
77 for (auto I = NewBB->getFirstNonPHI(); I != NewBB->end(); ++I)
78 for (MachineOperand &MO : I->uses())
79 if (MO.isReg() && Remaps.count(MO.getReg()))
80 MO.setReg(Remaps[MO.getReg()]);
81
82 for (auto I = NewBB->begin(); I->isPHI(); ++I) {
83 MachineInstr &MI = *I;
84 unsigned LoopRegIdx = 3, InitRegIdx = 1;
85 if (MI.getOperand(2).getMBB() != Preheader)
86 std::swap(LoopRegIdx, InitRegIdx);
87 MachineInstr &OrigPhi = findEquivalentInstruction(MI, Loop);
88 assert(OrigPhi.isPHI());
89 if (Direction == LPD_Front) {
90 // When peeling front, we are only left with the initial value from the
91 // preheader.
92 Register R = MI.getOperand(LoopRegIdx).getReg();
93 if (Remaps.count(R))
94 R = Remaps[R];
95 OrigPhi.getOperand(InitRegIdx).setReg(R);
96 MI.removeOperand(LoopRegIdx + 1);
97 MI.removeOperand(LoopRegIdx + 0);
98 } else {
99 // When peeling back, the initial value is the loop-carried value from
100 // the original loop.
101 Register LoopReg = OrigPhi.getOperand(LoopRegIdx).getReg();
102 MI.getOperand(LoopRegIdx).setReg(LoopReg);
103 MI.removeOperand(InitRegIdx + 1);
104 MI.removeOperand(InitRegIdx + 0);
105 }
106 }
107
108 DebugLoc DL;
109 if (Direction == LPD_Front) {
110 Preheader->ReplaceUsesOfBlockWith(Loop, NewBB);
111 NewBB->addSuccessor(Loop);
112 Loop->replacePhiUsesWith(Preheader, NewBB);
113 Preheader->updateTerminator(Loop);
114 TII->removeBranch(*NewBB);
115 TII->insertBranch(*NewBB, Loop, nullptr, {}, DL);
116 } else {
117 Loop->replaceSuccessor(Exit, NewBB);
118 Exit->replacePhiUsesWith(Loop, NewBB);
119 NewBB->addSuccessor(Exit);
120
121 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
123 bool CanAnalyzeBr = !TII->analyzeBranch(*Loop, TBB, FBB, Cond);
124 (void)CanAnalyzeBr;
125 assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
127 TII->insertBranch(*Loop, TBB == Exit ? NewBB : TBB,
128 FBB == Exit ? NewBB : FBB, Cond, DL);
129 if (TII->removeBranch(*NewBB) > 0)
130 TII->insertBranch(*NewBB, Exit, nullptr, {}, DL);
131 }
132
133 return NewBB;
134}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
SmallPtrSet< MachineInstr *, 2 > Uses
SmallVector< MachineOperand, 4 > Cond
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
A debug info location.
Definition: DebugLoc.h:33
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const override
Insert branch code into the end of the specified MachineBasicBlock.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.
instr_iterator instr_begin()
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
void ReplaceUsesOfBlockWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Given a machine basic block that branched to 'Old', change the code and CFG so that it branches to 'N...
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
void insert(iterator MBBI, MachineBasicBlock *MBB)
Representation of each machine instruction.
Definition: MachineInstr.h:68
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:678
bool isPHI() const
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
MachineOperand class - Representation of each machine instruction operand.
void setReg(Register Reg)
Change the register this operand corresponds to.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
TargetInstrInfo - Interface to description of machine instruction set.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
Iterator for intrusive lists based on ilist_node.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
MachineBasicBlock * PeelSingleBlockLoop(LoopPeelDirection Direction, MachineBasicBlock *Loop, MachineRegisterInfo &MRI, const TargetInstrInfo *TII)
Peels a single block loop.
@ LPD_Back
Peel the last iteration of the loop.
@ LPD_Front
Peel the first iteration of the loop.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:723