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/CodeGen/TargetRegisterInfo.h" 27 #include "llvm/InitializePasses.h" 28 #include "llvm/Pass.h" 29 #include "llvm/Support/Debug.h" 30 #include "llvm/Support/raw_ostream.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) { 48 initializeLiveRangeShrinkPass(*PassRegistry::getPassRegistry()); 49 } 50 51 void getAnalysisUsage(AnalysisUsage &AU) const override { 52 AU.setPreservesCFG(); 53 MachineFunctionPass::getAnalysisUsage(AU); 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 65 char &llvm::LiveRangeShrinkID = LiveRangeShrink::ID; 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. 100 static void BuildInstOrderMap(MachineBasicBlock::iterator 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 112 MachineRegisterInfo &MRI = MF.getRegInfo(); 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. 121 DenseMap<unsigned, std::pair<unsigned, MachineInstr *>> UseMap; 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.isDebugInstr()) 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. 180 if (!Register::isVirtualRegister(Reg)) { 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->isDebugInstr())) 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->getDebugOperandForReg(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 } 247