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" 19 #include "llvm/ADT/iterator_range.h" 20 #include "llvm/CodeGen/MachineBasicBlock.h" 21 #include "llvm/CodeGen/MachineFunction.h" 22 #include "llvm/CodeGen/MachineFunctionPass.h" 23 #include "llvm/CodeGen/MachineInstr.h" 24 #include "llvm/CodeGen/MachineOperand.h" 25 #include "llvm/CodeGen/MachineRegisterInfo.h" 26 #include "llvm/InitializePasses.h" 27 #include "llvm/Pass.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.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) { 47 initializeLiveRangeShrinkPass(*PassRegistry::getPassRegistry()); 48 } 49 50 void getAnalysisUsage(AnalysisUsage &AU) const override { 51 AU.setPreservesCFG(); 52 MachineFunctionPass::getAnalysisUsage(AU); 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 64 char &llvm::LiveRangeShrinkID = LiveRangeShrink::ID; 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. 99 static void BuildInstOrderMap(MachineBasicBlock::iterator 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 111 MachineRegisterInfo &MRI = MF.getRegInfo(); 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. 120 DenseMap<unsigned, std::pair<unsigned, MachineInstr *>> UseMap; 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. 179 if (!Reg.isVirtual()) { 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 } 246