LLVM  16.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 
13 using namespace llvm;
14 
15 namespace {
16 // MI's parent and BB are clones of each other. Find the equivalent copy of MI
17 // in BB.
18 MachineInstr &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];
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!");
126  TII->removeBranch(*Loop);
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 }
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::MachineRegisterInfo::createVirtualRegister
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
Definition: MachineRegisterInfo.cpp:156
llvm::HexagonInstrInfo::removeBranch
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
Definition: HexagonInstrInfo.cpp:604
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::MachineBasicBlock::ReplaceUsesOfBlockWith
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...
Definition: MachineBasicBlock.cpp:1354
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::HexagonInstrInfo::analyzeBranch
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....
Definition: HexagonInstrInfo.cpp:434
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
MachineBasicBlock.h
llvm::MachineInstr::defs
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:678
llvm::LPD_Front
@ LPD_Front
Peel the first iteration of the loop.
Definition: MachineLoopUtils.h:18
MachineLoopUtils.h
TargetInstrInfo.h
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:477
llvm::MachineFunction::insert
void insert(iterator MBBI, MachineBasicBlock *MBB)
Definition: MachineFunction.h:873
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::count
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
MachineRegisterInfo.h
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:590
llvm::MachineBasicBlock::addSuccessor
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:762
llvm::Register::isPhysical
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:97
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:526
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:45
TBB
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
Definition: RISCVRedundantCopyElimination.cpp:76
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:48
llvm::HexagonInstrInfo::insertBranch
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.
Definition: HexagonInstrInfo.cpp:627
llvm::PeelSingleBlockLoop
MachineBasicBlock * PeelSingleBlockLoop(LoopPeelDirection Direction, MachineBasicBlock *Loop, MachineRegisterInfo &MRI, const TargetInstrInfo *TII)
Peels a single block loop.
Definition: MachineLoopUtils.cpp:26
llvm::Loop::LoopBounds::Direction
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:723
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:419
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineFunction::CloneMachineInstr
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
Definition: MachineFunction.cpp:383
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MachineBasicBlock::getFirstNonPHI
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: MachineBasicBlock.cpp:197
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:439
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1300
llvm::LoopPeelDirection
LoopPeelDirection
Definition: MachineLoopUtils.h:17
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineFunction
Definition: MachineFunction.h:257
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::LPD_Back
@ LPD_Back
Peel the last iteration of the loop.
Definition: MachineLoopUtils.h:19
llvm::MachineBasicBlock::replacePhiUsesWith
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.
Definition: MachineBasicBlock.cpp:1375
llvm::MachineBasicBlock::insert
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Definition: MachineBasicBlock.cpp:1327
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:56
llvm::MachineRegisterInfo::constrainRegClass
const TargetRegisterClass * constrainRegClass(Register Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
Definition: MachineRegisterInfo.cpp:82
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
PB
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::MachineBasicBlock::updateTerminator
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
Definition: MachineBasicBlock.cpp:657
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43