LLVM  6.0.0svn
LiveRangeShrink.cpp
Go to the documentation of this file.
1 //===- LiveRangeShrink.cpp - Move instructions to shrink live range -------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 ///===---------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// This pass moves instructions close to the definition of its operands to
12 /// shrink live range of the def instruction. The code motion is limited within
13 /// the basic block. The moved instruction should have 1 def, and more than one
14 /// uses, all of which are the only use of the def.
15 ///
16 ///===---------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Support/Debug.h"
31 #include <iterator>
32 #include <utility>
33 
34 using namespace llvm;
35 
36 #define DEBUG_TYPE "lrshrink"
37 
38 STATISTIC(NumInstrsHoistedToShrinkLiveRange,
39  "Number of insructions hoisted to shrink live range.");
40 
41 namespace {
42 
43 class LiveRangeShrink : public MachineFunctionPass {
44 public:
45  static char ID;
46 
47  LiveRangeShrink() : MachineFunctionPass(ID) {
49  }
50 
51  void getAnalysisUsage(AnalysisUsage &AU) const override {
52  AU.setPreservesCFG();
54  }
55 
56  StringRef getPassName() const override { return "Live Range Shrink"; }
57 
58  bool runOnMachineFunction(MachineFunction &MF) override;
59 };
60 
61 } // end anonymous namespace
62 
63 char LiveRangeShrink::ID = 0;
64 
66 
67 INITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false,
68  false)
69 
70 using InstOrderMap = DenseMap<MachineInstr *, unsigned>;
71 
72 /// Returns \p New if it's dominated by \p Old, otherwise return \p Old.
73 /// \p M maintains a map from instruction to its dominating order that satisfies
74 /// M[A] > M[B] guarantees that A is dominated by B.
75 /// If \p New is not in \p M, return \p Old. Otherwise if \p Old is null, return
76 /// \p New.
77 static MachineInstr *FindDominatedInstruction(MachineInstr &New,
78  MachineInstr *Old,
79  const InstOrderMap &M) {
80  auto NewIter = M.find(&New);
81  if (NewIter == M.end())
82  return Old;
83  if (Old == nullptr)
84  return &New;
85  unsigned OrderOld = M.find(Old)->second;
86  unsigned OrderNew = NewIter->second;
87  if (OrderOld != OrderNew)
88  return OrderOld < OrderNew ? &New : Old;
89  // OrderOld == OrderNew, we need to iterate down from Old to see if it
90  // can reach New, if yes, New is dominated by Old.
91  for (MachineInstr *I = Old->getNextNode(); M.find(I)->second == OrderNew;
92  I = I->getNextNode())
93  if (I == &New)
94  return &New;
95  return Old;
96 }
97 
98 /// Builds Instruction to its dominating order number map \p M by traversing
99 /// from instruction \p Start.
101  InstOrderMap &M) {
102  M.clear();
103  unsigned i = 0;
104  for (MachineInstr &I : make_range(Start, Start->getParent()->end()))
105  M[&I] = i++;
106 }
107 
108 bool LiveRangeShrink::runOnMachineFunction(MachineFunction &MF) {
109  if (skipFunction(*MF.getFunction()))
110  return false;
111 
113 
114  DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n');
115 
116  InstOrderMap IOM;
117  // Map from register to instruction order (value of IOM) where the
118  // register is used last. When moving instructions up, we need to
119  // make sure all its defs (including dead def) will not cross its
120  // last use when moving up.
122 
123  for (MachineBasicBlock &MBB : MF) {
124  if (MBB.empty())
125  continue;
126  bool SawStore = false;
127  BuildInstOrderMap(MBB.begin(), IOM);
128  UseMap.clear();
129 
130  for (MachineBasicBlock::iterator Next = MBB.begin(); Next != MBB.end();) {
131  MachineInstr &MI = *Next;
132  ++Next;
133  if (MI.isPHI() || MI.isDebugValue())
134  continue;
135  if (MI.mayStore())
136  SawStore = true;
137 
138  unsigned CurrentOrder = IOM[&MI];
139  unsigned Barrier = 0;
140  MachineInstr *BarrierMI = nullptr;
141  for (const MachineOperand &MO : MI.operands()) {
142  if (!MO.isReg() || MO.isDebug())
143  continue;
144  if (MO.isUse())
145  UseMap[MO.getReg()] = std::make_pair(CurrentOrder, &MI);
146  else if (MO.isDead() && UseMap.count(MO.getReg()))
147  // Barrier is the last instruction where MO get used. MI should not
148  // be moved above Barrier.
149  if (Barrier < UseMap[MO.getReg()].first) {
150  Barrier = UseMap[MO.getReg()].first;
151  BarrierMI = UseMap[MO.getReg()].second;
152  }
153  }
154 
155  if (!MI.isSafeToMove(nullptr, SawStore)) {
156  // If MI has side effects, it should become a barrier for code motion.
157  // IOM is rebuild from the next instruction to prevent later
158  // instructions from being moved before this MI.
159  if (MI.hasUnmodeledSideEffects() && Next != MBB.end()) {
160  BuildInstOrderMap(Next, IOM);
161  SawStore = false;
162  }
163  continue;
164  }
165 
166  const MachineOperand *DefMO = nullptr;
167  MachineInstr *Insert = nullptr;
168 
169  // Number of live-ranges that will be shortened. We do not count
170  // live-ranges that are defined by a COPY as it could be coalesced later.
171  unsigned NumEligibleUse = 0;
172 
173  for (const MachineOperand &MO : MI.operands()) {
174  if (!MO.isReg() || MO.isDead() || MO.isDebug())
175  continue;
176  unsigned Reg = MO.getReg();
177  // Do not move the instruction if it def/uses a physical register,
178  // unless it is a constant physical register or a noreg.
180  if (!Reg || MRI.isConstantPhysReg(Reg))
181  continue;
182  Insert = nullptr;
183  break;
184  }
185  if (MO.isDef()) {
186  // Do not move if there is more than one def.
187  if (DefMO) {
188  Insert = nullptr;
189  break;
190  }
191  DefMO = &MO;
192  } else if (MRI.hasOneNonDBGUse(Reg) && MRI.hasOneDef(Reg) && DefMO &&
193  MRI.getRegClass(DefMO->getReg()) ==
194  MRI.getRegClass(MO.getReg())) {
195  // The heuristic does not handle different register classes yet
196  // (registers of different sizes, looser/tighter constraints). This
197  // is because it needs more accurate model to handle register
198  // pressure correctly.
199  MachineInstr &DefInstr = *MRI.def_instr_begin(Reg);
200  if (!DefInstr.isCopy())
201  NumEligibleUse++;
202  Insert = FindDominatedInstruction(DefInstr, Insert, IOM);
203  } else {
204  Insert = nullptr;
205  break;
206  }
207  }
208 
209  // If Barrier equals IOM[I], traverse forward to find if BarrierMI is
210  // after Insert, if yes, then we should not hoist.
211  for (MachineInstr *I = Insert; I && IOM[I] == Barrier;
212  I = I->getNextNode())
213  if (I == BarrierMI) {
214  Insert = nullptr;
215  break;
216  }
217  // Move the instruction when # of shrunk live range > 1.
218  if (DefMO && Insert && NumEligibleUse > 1 && Barrier <= IOM[Insert]) {
219  MachineBasicBlock::iterator I = std::next(Insert->getIterator());
220  // Skip all the PHI and debug instructions.
221  while (I != MBB.end() && (I->isPHI() || I->isDebugValue()))
222  I = std::next(I);
223  if (I == MI.getIterator())
224  continue;
225 
226  // Update the dominator order to be the same as the insertion point.
227  // We do this to maintain a non-decreasing order without need to update
228  // all instruction orders after the insertion point.
229  unsigned NewOrder = IOM[&*I];
230  IOM[&MI] = NewOrder;
231  NumInstrsHoistedToShrinkLiveRange++;
232 
233  // Find MI's debug value following MI.
234  MachineBasicBlock::iterator EndIter = std::next(MI.getIterator());
235  if (MI.getOperand(0).isReg())
236  for (; EndIter != MBB.end() && EndIter->isDebugValue() &&
237  EndIter->getOperand(0).isReg() &&
238  EndIter->getOperand(0).getReg() == MI.getOperand(0).getReg();
239  ++EndIter, ++Next)
240  IOM[&*EndIter] = NewOrder;
241  MBB.splice(I, &MBB, MI.getIterator(), EndIter);
242  }
243  }
244  }
245  return false;
246 }
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.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
unsigned getReg() const
getReg - Returns the register number.
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
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:332
bool isPHI() const
Definition: MachineInstr.h:826
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
Reg
All possible values of the reg field in the ModR/M byte.
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:639
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:82
void initializeLiveRangeShrinkPass(PassRegistry &)
bool isCopy() const
Definition: MachineInstr.h:857
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.
bool isDebugValue() const
Definition: MachineInstr.h:816
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:285
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:59
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 instruction using the specified regis...
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:141
bool isReg() const
isReg - Tests if this is a MO_Register operand.
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
aarch64 promote const
#define DEBUG(X)
Definition: Debug.h:118
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:49
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
bool isSafeToMove(AliasAnalysis *AA, bool &SawStore) const
Return true if it is safe to move this instruction.