LLVM  13.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 
14 using namespace llvm;
15 
16 namespace {
17 // MI's parent and BB are clones of each other. Find the equivalent copy of MI
18 // in BB.
19 MachineInstr &findEquivalentInstruction(MachineInstr &MI,
21  MachineBasicBlock *PB = MI.getParent();
22  unsigned Offset = std::distance(PB->instr_begin(), MachineBasicBlock::instr_iterator(MI));
23  return *std::next(BB->instr_begin(), Offset);
24 }
25 } // namespace
26 
30  const TargetInstrInfo *TII) {
31  MachineFunction &MF = *Loop->getParent();
32  MachineBasicBlock *Preheader = *Loop->pred_begin();
33  if (Preheader == Loop)
34  Preheader = *std::next(Loop->pred_begin());
35  MachineBasicBlock *Exit = *Loop->succ_begin();
36  if (Exit == Loop)
37  Exit = *std::next(Loop->succ_begin());
38 
39  MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(Loop->getBasicBlock());
40  if (Direction == LPD_Front)
41  MF.insert(Loop->getIterator(), NewBB);
42  else
43  MF.insert(std::next(Loop->getIterator()), NewBB);
44 
46  auto InsertPt = NewBB->end();
47  for (MachineInstr &MI : *Loop) {
48  MachineInstr *NewMI = MF.CloneMachineInstr(&MI);
49  NewBB->insert(InsertPt, NewMI);
50  for (MachineOperand &MO : NewMI->defs()) {
51  Register OrigR = MO.getReg();
52  if (OrigR.isPhysical())
53  continue;
54  Register &R = Remaps[OrigR];
56  MO.setReg(R);
57 
58  if (Direction == LPD_Back) {
59  // Replace all uses outside the original loop with the new register.
60  // FIXME: is the use_iterator stable enough to mutate register uses
61  // while iterating?
63  for (auto &Use : MRI.use_operands(OrigR))
64  if (Use.getParent()->getParent() != Loop)
65  Uses.push_back(&Use);
66  for (auto *Use : Uses) {
67  MRI.constrainRegClass(R, MRI.getRegClass(Use->getReg()));
68  Use->setReg(R);
69  }
70  }
71  }
72  }
73 
74  for (auto I = NewBB->getFirstNonPHI(); I != NewBB->end(); ++I)
75  for (MachineOperand &MO : I->uses())
76  if (MO.isReg() && Remaps.count(MO.getReg()))
77  MO.setReg(Remaps[MO.getReg()]);
78 
79  for (auto I = NewBB->begin(); I->isPHI(); ++I) {
80  MachineInstr &MI = *I;
81  unsigned LoopRegIdx = 3, InitRegIdx = 1;
82  if (MI.getOperand(2).getMBB() != Preheader)
83  std::swap(LoopRegIdx, InitRegIdx);
84  MachineInstr &OrigPhi = findEquivalentInstruction(MI, Loop);
85  assert(OrigPhi.isPHI());
86  if (Direction == LPD_Front) {
87  // When peeling front, we are only left with the initial value from the
88  // preheader.
89  Register R = MI.getOperand(LoopRegIdx).getReg();
90  if (Remaps.count(R))
91  R = Remaps[R];
92  OrigPhi.getOperand(InitRegIdx).setReg(R);
93  MI.RemoveOperand(LoopRegIdx + 1);
94  MI.RemoveOperand(LoopRegIdx + 0);
95  } else {
96  // When peeling back, the initial value is the loop-carried value from
97  // the original loop.
98  Register LoopReg = OrigPhi.getOperand(LoopRegIdx).getReg();
99  MI.getOperand(LoopRegIdx).setReg(LoopReg);
100  MI.RemoveOperand(InitRegIdx + 1);
101  MI.RemoveOperand(InitRegIdx + 0);
102  }
103  }
104 
105  DebugLoc DL;
106  if (Direction == LPD_Front) {
107  Preheader->replaceSuccessor(Loop, NewBB);
108  NewBB->addSuccessor(Loop);
109  Loop->replacePhiUsesWith(Preheader, NewBB);
110  if (TII->removeBranch(*Preheader) > 0)
111  TII->insertBranch(*Preheader, NewBB, nullptr, {}, DL);
112  TII->removeBranch(*NewBB);
113  TII->insertBranch(*NewBB, Loop, nullptr, {}, DL);
114  } else {
115  Loop->replaceSuccessor(Exit, NewBB);
116  Exit->replacePhiUsesWith(Loop, NewBB);
117  NewBB->addSuccessor(Exit);
118 
119  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
121  bool CanAnalyzeBr = !TII->analyzeBranch(*Loop, TBB, FBB, Cond);
122  (void)CanAnalyzeBr;
123  assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
124  TII->removeBranch(*Loop);
125  TII->insertBranch(*Loop, TBB == Exit ? NewBB : TBB,
126  FBB == Exit ? NewBB : FBB, Cond, DL);
127  if (TII->removeBranch(*NewBB) > 0)
128  TII->insertBranch(*NewBB, Exit, nullptr, {}, DL);
129  }
130 
131  return NewBB;
132 }
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:158
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:561
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:529
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:391
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
MachineBasicBlock.h
llvm::MachineInstr::defs
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:634
llvm::LPD_Front
@ LPD_Front
Peel the first iteration of the loop.
Definition: MachineLoopUtils.h:19
MachineLoopUtils.h
TargetInstrInfo.h
llvm::MachineRegisterInfo::use_operands
iterator_range< use_iterator > use_operands(Register Reg) const
Definition: MachineRegisterInfo.h:469
llvm::MachineFunction::insert
void insert(iterator MBBI, MachineBasicBlock *MBB)
Definition: MachineFunction.h:756
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
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
MachineRegisterInfo.h
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:583
llvm::MachineBasicBlock::addSuccessor
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
Definition: MachineBasicBlock.cpp:743
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:97
MachineLoopInfo.h
llvm::MachineInstr::getOperand
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:487
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
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:584
llvm::PeelSingleBlockLoop
MachineBasicBlock * PeelSingleBlockLoop(LoopPeelDirection Direction, MachineBasicBlock *Loop, MachineRegisterInfo &MRI, const TargetInstrInfo *TII)
Peels a single block loop.
Definition: MachineLoopUtils.cpp:27
llvm::Loop::LoopBounds::Direction
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:697
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:634
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:63
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:358
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::MachineBasicBlock::getFirstNonPHI
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: MachineBasicBlock.cpp:199
llvm::MachineFunction::CreateMachineBasicBlock
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
Definition: MachineFunction.cpp:414
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:944
llvm::MachineInstr::isPHI
bool isPHI() const
Definition: MachineInstr.h:1233
llvm::LoopPeelDirection
LoopPeelDirection
Definition: MachineLoopUtils.h:18
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:357
llvm::MachineBasicBlock::instr_begin
instr_iterator instr_begin()
Definition: MachineBasicBlock.h:252
llvm::MachineFunction
Definition: MachineFunction.h:227
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
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:20
llvm::MachineBasicBlock::replaceSuccessor
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
Definition: MachineBasicBlock.cpp:804
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:1383
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:1335
llvm::ilist_iterator
Iterator for intrusive lists based on ilist_node.
Definition: ilist_iterator.h:57
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
llvm::MachineOperand::setReg
void setReg(Register Reg)
Change the register this operand corresponds to.
Definition: MachineOperand.cpp:55
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:85
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
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44