LLVM  14.0.0git
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/InitializePasses.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.
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  LLVM_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.isDebugOrPseudoInstr())
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() && !MI.isPseudoProbe() &&
160  Next != MBB.end()) {
161  BuildInstOrderMap(Next, IOM);
162  SawStore = false;
163  }
164  continue;
165  }
166 
167  const MachineOperand *DefMO = nullptr;
168  MachineInstr *Insert = nullptr;
169 
170  // Number of live-ranges that will be shortened. We do not count
171  // live-ranges that are defined by a COPY as it could be coalesced later.
172  unsigned NumEligibleUse = 0;
173 
174  for (const MachineOperand &MO : MI.operands()) {
175  if (!MO.isReg() || MO.isDead() || MO.isDebug())
176  continue;
177  Register Reg = MO.getReg();
178  // Do not move the instruction if it def/uses a physical register,
179  // unless it is a constant physical register or a noreg.
181  if (!Reg || MRI.isConstantPhysReg(Reg))
182  continue;
183  Insert = nullptr;
184  break;
185  }
186  if (MO.isDef()) {
187  // Do not move if there is more than one def.
188  if (DefMO) {
189  Insert = nullptr;
190  break;
191  }
192  DefMO = &MO;
193  } else if (MRI.hasOneNonDBGUse(Reg) && MRI.hasOneDef(Reg) && DefMO &&
194  MRI.getRegClass(DefMO->getReg()) ==
195  MRI.getRegClass(MO.getReg())) {
196  // The heuristic does not handle different register classes yet
197  // (registers of different sizes, looser/tighter constraints). This
198  // is because it needs more accurate model to handle register
199  // pressure correctly.
200  MachineInstr &DefInstr = *MRI.def_instr_begin(Reg);
201  if (!DefInstr.isCopy())
202  NumEligibleUse++;
203  Insert = FindDominatedInstruction(DefInstr, Insert, IOM);
204  } else {
205  Insert = nullptr;
206  break;
207  }
208  }
209 
210  // If Barrier equals IOM[I], traverse forward to find if BarrierMI is
211  // after Insert, if yes, then we should not hoist.
212  for (MachineInstr *I = Insert; I && IOM[I] == Barrier;
213  I = I->getNextNode())
214  if (I == BarrierMI) {
215  Insert = nullptr;
216  break;
217  }
218  // Move the instruction when # of shrunk live range > 1.
219  if (DefMO && Insert && NumEligibleUse > 1 && Barrier <= IOM[Insert]) {
220  MachineBasicBlock::iterator I = std::next(Insert->getIterator());
221  // Skip all the PHI and debug instructions.
222  while (I != MBB.end() && (I->isPHI() || I->isDebugOrPseudoInstr()))
223  I = std::next(I);
224  if (I == MI.getIterator())
225  continue;
226 
227  // Update the dominator order to be the same as the insertion point.
228  // We do this to maintain a non-decreasing order without need to update
229  // all instruction orders after the insertion point.
230  unsigned NewOrder = IOM[&*I];
231  IOM[&MI] = NewOrder;
232  NumInstrsHoistedToShrinkLiveRange++;
233 
234  // Find MI's debug value following MI.
235  MachineBasicBlock::iterator EndIter = std::next(MI.getIterator());
236  if (MI.getOperand(0).isReg())
237  for (; EndIter != MBB.end() && EndIter->isDebugValue() &&
238  EndIter->hasDebugOperandForReg(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 }
i
i
Definition: README.txt:29
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
MachineInstr.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
Insert
Vector Rotate Left Mask Mask Insert
Definition: README_P9.txt:112
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
Pass.h
llvm::MachineRegisterInfo::def_instr_begin
def_instr_iterator def_instr_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:397
Statistic.h
llvm::initializeLiveRangeShrinkPass
void initializeLiveRangeShrinkPass(PassRegistry &)
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
DenseMap.h
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
llvm::MachineInstr::isCopy
bool isCopy() const
Definition: MachineInstr.h:1291
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:636
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
BuildInstOrderMap
static void BuildInstOrderMap(MachineBasicBlock::iterator Start, InstOrderMap &M)
Builds Instruction to its dominating order number map M by traversing from instruction Start.
Definition: LiveRangeShrink.cpp:100
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::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:111
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MCID::Barrier
@ Barrier
Definition: MCInstrDesc.h:154
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::LiveRangeShrinkID
char & LiveRangeShrinkID
LiveRangeShrink pass.
Definition: LiveRangeShrink.cpp:65
MachineFunctionPass.h
llvm::Register::isVirtualRegister
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
llvm::MachineFunction::getName
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
Definition: MachineFunction.cpp:541
iterator_range.h
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:360
llvm::MachineRegisterInfo::hasOneDef
bool hasOneDef(Register RegNo) const
Return true if there is exactly one operand defining the specified register.
Definition: MachineRegisterInfo.h:444
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::MachineBasicBlock::splice
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Definition: MachineBasicBlock.h:950
llvm::MachineRegisterInfo::hasOneNonDBGUse
bool hasOneNonDBGUse(Register RegNo) const
hasOneNonDBGUse - Return true if there is exactly one non-Debug use of the specified register.
Definition: MachineRegisterInfo.cpp:419
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
llvm::MachineRegisterInfo::isConstantPhysReg
bool isConstantPhysReg(MCRegister PhysReg) const
Returns true if PhysReg is unallocatable and constant throughout the function.
Definition: MachineRegisterInfo.cpp:513
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:592
FindDominatedInstruction
static MachineInstr * FindDominatedInstruction(MachineInstr &New, MachineInstr *Old, const InstOrderMap &M)
Returns New if it's dominated by Old, otherwise return Old.
Definition: LiveRangeShrink.cpp:77
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
INITIALIZE_PASS
INITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false, false) using InstOrderMap
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:240
MachineOperand.h
raw_ostream.h
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
TargetRegisterInfo.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:270
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37