LLVM  16.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"
26 #include "llvm/InitializePasses.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.
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.isDebugOrPseudoInstr())
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() && !MI.isPseudoProbe() &&
159  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  Register 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->isDebugOrPseudoInstr()))
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->hasDebugOperandForReg(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 }
i
i
Definition: README.txt:29
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:50
Pass.h
llvm::MachineRegisterInfo::def_instr_begin
def_instr_iterator def_instr_begin(Register RegNo) const
Definition: MachineRegisterInfo.h:405
Statistic.h
llvm::initializeLiveRangeShrinkPass
void initializeLiveRangeShrinkPass(PassRegistry &)
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
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:1336
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:167
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:667
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
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:48
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:99
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
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:110
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MCID::Barrier
@ Barrier
Definition: MCInstrDesc.h:156
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LiveRangeShrinkID
char & LiveRangeShrinkID
LiveRangeShrink pass.
Definition: LiveRangeShrink.cpp:64
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:567
iterator_range.h
llvm::MachineOperand::getReg
Register getReg() const
getReg - Returns the register number.
Definition: MachineOperand.h:359
llvm::MachineRegisterInfo::hasOneDef
bool hasOneDef(Register RegNo) const
Return true if there is exactly one operand defining the specified register.
Definition: MachineRegisterInfo.h:452
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
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:1009
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:415
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:515
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:623
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:76
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:305
INITIALIZE_PASS
INITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false, false) using InstOrderMap
llvm::MachineBasicBlock::empty
bool empty() const
Definition: MachineBasicBlock.h:277
MachineOperand.h
raw_ostream.h
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
InitializePasses.h
Debug.h
llvm::MachineBasicBlock::end
iterator end()
Definition: MachineBasicBlock.h:307