LLVM  10.0.0svn
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,
19  MachineBasicBlock *BB) {
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 
39  if (Direction == LPD_Front)
40  MF.insert(Loop->getIterator(), NewBB);
41  else
42  MF.insert(std::next(Loop->getIterator()), NewBB);
43 
44  // FIXME: Add DenseMapInfo trait for Register so we can use it as a key.
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];
55  R = MRI.createVirtualRegister(MRI.getRegClass(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 }
instr_iterator instr_begin()
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
virtual unsigned insertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB, MachineBasicBlock *FBB, ArrayRef< MachineOperand > Cond, const DebugLoc &DL, int *BytesAdded=nullptr) const
Insert branch code into the end of the specified MachineBasicBlock.
A debug info location.
Definition: DebugLoc.h:33
Peel the first iteration of the loop.
bool isPHI() const
virtual unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const
Remove the branching code at the end of the specific MBB.
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
const HexagonInstrInfo * TII
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:677
bool isPhysical() const
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:95
void setReg(Register Reg)
Change the register this operand corresponds to.
MachineBasicBlock * CreateMachineBasicBlock(const BasicBlock *bb=nullptr)
CreateMachineBasicBlock - Allocate a new MachineBasicBlock.
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
TargetInstrInfo - Interface to description of machine instruction set.
unsigned const MachineRegisterInfo * MRI
iterator_range< mop_iterator > defs()
Returns a range over all explicit operands that are register definitions.
Definition: MachineInstr.h:498
self_iterator getIterator()
Definition: ilist_node.h:81
virtual bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify=false) const
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e...
MachineInstr * CloneMachineInstr(const MachineInstr *Orig)
Create a new MachineInstr which is a copy of Orig, identical in all ways except the instruction has n...
iterator_range< use_iterator > use_operands(unsigned Reg) const
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Peel the last iteration of the loop.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New)
Replace successor OLD with NEW and update probability info.
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:255
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:63
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
#define I(x, y, z)
Definition: MD5.cpp:58
iterator end()
Definition: DenseMap.h:82
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
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
Instructions::iterator instr_iterator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void insert(iterator MBBI, MachineBasicBlock *MBB)
IRTranslator LLVM IR MI
void RemoveOperand(unsigned OpNo)
Erase an operand from an instruction, leaving it with one fewer operand than it started with...
Register getReg() const
getReg - Returns the register number.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:415
MachineBasicBlock * PeelSingleBlockLoop(LoopPeelDirection Direction, MachineBasicBlock *Loop, MachineRegisterInfo &MRI, const TargetInstrInfo *TII)
Peels a single block loop.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19