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  unsigned 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.
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...
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
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...
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
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
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
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.