LLVM  10.0.0svn
LiveRangeShrink.cpp
Go to the documentation of this file.
1 //===- LiveRangeShrink.cpp - Move instructions to shrink live range -------===//
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 ///
9 /// \file
10 /// This pass moves instructions close to the definition of its operands to
11 /// shrink live range of the def instruction. The code motion is limited within
12 /// the basic block. The moved instruction should have 1 def, and more than one
13 /// uses, all of which are the only use of the def.
14 ///
15 ///===---------------------------------------------------------------------===//
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/Debug.h"
30 #include <iterator>
31 #include <utility>
32 
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "lrshrink"
36 
37 STATISTIC(NumInstrsHoistedToShrinkLiveRange,
38  "Number of insructions hoisted to shrink live range.");
39 
40 namespace {
41 
42 class LiveRangeShrink : public MachineFunctionPass {
43 public:
44  static char ID;
45 
46  LiveRangeShrink() : MachineFunctionPass(ID) {
48  }
49 
50  void getAnalysisUsage(AnalysisUsage &AU) const override {
51  AU.setPreservesCFG();
53  }
54 
55  StringRef getPassName() const override { return "Live Range Shrink"; }
56 
57  bool runOnMachineFunction(MachineFunction &MF) override;
58 };
59 
60 } // end anonymous namespace
61 
62 char LiveRangeShrink::ID = 0;
63 
65 
66 INITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false,
67  false)
68 
69 using InstOrderMap = DenseMap<MachineInstr *, unsigned>;
70 
71 /// Returns \p New if it's dominated by \p Old, otherwise return \p Old.
72 /// \p M maintains a map from instruction to its dominating order that satisfies
73 /// M[A] > M[B] guarantees that A is dominated by B.
74 /// If \p New is not in \p M, return \p Old. Otherwise if \p Old is null, return
75 /// \p New.
76 static MachineInstr *FindDominatedInstruction(MachineInstr &New,
77  MachineInstr *Old,
78  const InstOrderMap &M) {
79  auto NewIter = M.find(&New);
80  if (NewIter == M.end())
81  return Old;
82  if (Old == nullptr)
83  return &New;
84  unsigned OrderOld = M.find(Old)->second;
85  unsigned OrderNew = NewIter->second;
86  if (OrderOld != OrderNew)
87  return OrderOld < OrderNew ? &New : Old;
88  // OrderOld == OrderNew, we need to iterate down from Old to see if it
89  // can reach New, if yes, New is dominated by Old.
90  for (MachineInstr *I = Old->getNextNode(); M.find(I)->second == OrderNew;
91  I = I->getNextNode())
92  if (I == &New)
93  return &New;
94  return Old;
95 }
96 
97 /// Builds Instruction to its dominating order number map \p M by traversing
98 /// from instruction \p Start.
100  InstOrderMap &M) {
101  M.clear();
102  unsigned i = 0;
103  for (MachineInstr &I : make_range(Start, Start->getParent()->end()))
104  M[&I] = i++;
105 }
106 
107 bool LiveRangeShrink::runOnMachineFunction(MachineFunction &MF) {
108  if (skipFunction(MF.getFunction()))
109  return false;
110 
112 
113  LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
114 
115  InstOrderMap IOM;
116  // Map from register to instruction order (value of IOM) where the
117  // register is used last. When moving instructions up, we need to
118  // make sure all its defs (including dead def) will not cross its
119  // last use when moving up.
121 
122  for (MachineBasicBlock &MBB : MF) {
123  if (MBB.empty())
124  continue;
125  bool SawStore = false;
126  BuildInstOrderMap(MBB.begin(), IOM);
127  UseMap.clear();
128 
129  for (MachineBasicBlock::iterator Next = MBB.begin(); Next != MBB.end();) {
130  MachineInstr &MI = *Next;
131  ++Next;
132  if (MI.isPHI() || MI.isDebugInstr())
133  continue;
134  if (MI.mayStore())
135  SawStore = true;
136 
137  unsigned CurrentOrder = IOM[&MI];
138  unsigned Barrier = 0;
139  MachineInstr *BarrierMI = nullptr;
140  for (const MachineOperand &MO : MI.operands()) {
141  if (!MO.isReg() || MO.isDebug())
142  continue;
143  if (MO.isUse())
144  UseMap[MO.getReg()] = std::make_pair(CurrentOrder, &MI);
145  else if (MO.isDead() && UseMap.count(MO.getReg()))
146  // Barrier is the last instruction where MO get used. MI should not
147  // be moved above Barrier.
148  if (Barrier < UseMap[MO.getReg()].first) {
149  Barrier = UseMap[MO.getReg()].first;
150  BarrierMI = UseMap[MO.getReg()].second;
151  }
152  }
153 
154  if (!MI.isSafeToMove(nullptr, SawStore)) {
155  // If MI has side effects, it should become a barrier for code motion.
156  // IOM is rebuild from the next instruction to prevent later
157  // instructions from being moved before this MI.
158  if (MI.hasUnmodeledSideEffects() && Next != MBB.end()) {
159  BuildInstOrderMap(Next, IOM);
160  SawStore = false;
161  }
162  continue;
163  }
164 
165  const MachineOperand *DefMO = nullptr;
166  MachineInstr *Insert = nullptr;
167 
168  // Number of live-ranges that will be shortened. We do not count
169  // live-ranges that are defined by a COPY as it could be coalesced later.
170  unsigned NumEligibleUse = 0;
171 
172  for (const MachineOperand &MO : MI.operands()) {
173  if (!MO.isReg() || MO.isDead() || MO.isDebug())
174  continue;
175  Register Reg = MO.getReg();
176  // Do not move the instruction if it def/uses a physical register,
177  // unless it is a constant physical register or a noreg.
178  if (!Register::isVirtualRegister(Reg)) {
179  if (!Reg || MRI.isConstantPhysReg(Reg))
180  continue;
181  Insert = nullptr;
182  break;
183  }
184  if (MO.isDef()) {
185  // Do not move if there is more than one def.
186  if (DefMO) {
187  Insert = nullptr;
188  break;
189  }
190  DefMO = &MO;
191  } else if (MRI.hasOneNonDBGUse(Reg) && MRI.hasOneDef(Reg) && DefMO &&
192  MRI.getRegClass(DefMO->getReg()) ==
193  MRI.getRegClass(MO.getReg())) {
194  // The heuristic does not handle different register classes yet
195  // (registers of different sizes, looser/tighter constraints). This
196  // is because it needs more accurate model to handle register
197  // pressure correctly.
198  MachineInstr &DefInstr = *MRI.def_instr_begin(Reg);
199  if (!DefInstr.isCopy())
200  NumEligibleUse++;
201  Insert = FindDominatedInstruction(DefInstr, Insert, IOM);
202  } else {
203  Insert = nullptr;
204  break;
205  }
206  }
207 
208  // If Barrier equals IOM[I], traverse forward to find if BarrierMI is
209  // after Insert, if yes, then we should not hoist.
210  for (MachineInstr *I = Insert; I && IOM[I] == Barrier;
211  I = I->getNextNode())
212  if (I == BarrierMI) {
213  Insert = nullptr;
214  break;
215  }
216  // Move the instruction when # of shrunk live range > 1.
217  if (DefMO && Insert && NumEligibleUse > 1 && Barrier <= IOM[Insert]) {
218  MachineBasicBlock::iterator I = std::next(Insert->getIterator());
219  // Skip all the PHI and debug instructions.
220  while (I != MBB.end() && (I->isPHI() || I->isDebugInstr()))
221  I = std::next(I);
222  if (I == MI.getIterator())
223  continue;
224 
225  // Update the dominator order to be the same as the insertion point.
226  // We do this to maintain a non-decreasing order without need to update
227  // all instruction orders after the insertion point.
228  unsigned NewOrder = IOM[&*I];
229  IOM[&MI] = NewOrder;
230  NumInstrsHoistedToShrinkLiveRange++;
231 
232  // Find MI's debug value following MI.
233  MachineBasicBlock::iterator EndIter = std::next(MI.getIterator());
234  if (MI.getOperand(0).isReg())
235  for (; EndIter != MBB.end() && EndIter->isDebugValue() &&
236  EndIter->getOperand(0).isReg() &&
237  EndIter->getOperand(0).getReg() == MI.getOperand(0).getReg();
238  ++EndIter, ++Next)
239  IOM[&*EndIter] = NewOrder;
240  MBB.splice(I, &MBB, MI.getIterator(), EndIter);
241  }
242  }
243  }
244  return false;
245 }
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
unsigned Reg
STATISTIC(NumFunctions, "Total number of functions")
bool hasOneDef(unsigned RegNo) const
Return true if there is exactly one operand defining the specified register.
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:461
bool isPHI() const
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
static MachineInstr * FindDominatedInstruction(MachineInstr &New, MachineInstr *Old, const InstOrderMap &M)
Returns New if it&#39;s dominated by Old, otherwise return Old.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
INITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false, false) using InstOrderMap
static void BuildInstOrderMap(MachineBasicBlock::iterator Start, InstOrderMap &M)
Builds Instruction to its dominating order number map M by traversing from instruction Start...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
char & LiveRangeShrinkID
LiveRangeShrink pass.
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:822
unsigned const MachineRegisterInfo * MRI
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Represent the analysis usage information of a pass.
self_iterator getIterator()
Definition: ilist_node.h:81
void initializeLiveRangeShrinkPass(PassRegistry &)
bool isCopy() const
bool isDebugInstr() const
bool isConstantPhysReg(unsigned PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
MachineOperand class - Representation of each machine instruction operand.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
def_instr_iterator def_instr_begin(unsigned RegNo) const
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:64
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
#define I(x, y, z)
Definition: MD5.cpp:58
bool hasOneNonDBGUse(unsigned RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register...
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:171
bool isReg() const
isReg - Tests if this is a MO_Register operand.
aarch64 promote const
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:69
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
bool isSafeToMove(AliasAnalysis *AA, bool &SawStore) const
Return true if it is safe to move this instruction.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19