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/TargetInstrInfo.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 /// Returns whether this instruction is considered a code motion barrier by this 99 /// pass. We can be less conservative than hasUnmodeledSideEffects() when 100 /// deciding whether an instruction is a barrier because it is known that pseudo 101 /// probes are safe to move in this pass specifically (see commit 1cb47a063e2b). 102 static bool isCodeMotionBarrier(MachineInstr &MI) { 103 return MI.hasUnmodeledSideEffects() && !MI.isPseudoProbe(); 104 } 105 106 /// Builds Instruction to its dominating order number map \p M by traversing 107 /// from instruction \p Start. 108 static void BuildInstOrderMap(MachineBasicBlock::iterator Start, 109 InstOrderMap &M) { 110 M.clear(); 111 unsigned i = 0; 112 for (MachineInstr &I : make_range(Start, Start->getParent()->end())) { 113 if (isCodeMotionBarrier(I)) 114 break; 115 M[&I] = i++; 116 } 117 } 118 119 bool LiveRangeShrink::runOnMachineFunction(MachineFunction &MF) { 120 if (skipFunction(MF.getFunction())) 121 return false; 122 123 MachineRegisterInfo &MRI = MF.getRegInfo(); 124 const TargetInstrInfo &TII = *MF.getSubtarget().getInstrInfo(); 125 126 LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); 127 128 InstOrderMap IOM; 129 // Map from register to instruction order (value of IOM) where the 130 // register is used last. When moving instructions up, we need to 131 // make sure all its defs (including dead def) will not cross its 132 // last use when moving up. 133 DenseMap<Register, std::pair<unsigned, MachineInstr *>> UseMap; 134 135 for (MachineBasicBlock &MBB : MF) { 136 if (MBB.empty()) 137 continue; 138 139 MachineBasicBlock::iterator Next = MBB.begin(); 140 if (MBB.isEHPad()) { 141 // Do not track PHIs in IOM when handling EHPads. 142 // Otherwise their uses may be hoisted outside a landingpad range. 143 Next = MBB.SkipPHIsLabelsAndDebug(Next); 144 if (Next == MBB.end()) 145 continue; 146 } 147 148 BuildInstOrderMap(Next, IOM); 149 Next = MBB.SkipPHIsLabelsAndDebug(Next); 150 UseMap.clear(); 151 bool SawStore = false; 152 153 while (Next != MBB.end()) { 154 MachineInstr &MI = *Next; 155 Next = MBB.SkipPHIsLabelsAndDebug(++Next); 156 157 unsigned CurrentOrder = IOM[&MI]; 158 unsigned Barrier = 0; 159 MachineInstr *BarrierMI = nullptr; 160 for (const MachineOperand &MO : MI.operands()) { 161 if (!MO.isReg() || MO.isDebug()) 162 continue; 163 if (MO.isUse()) 164 UseMap[MO.getReg()] = std::make_pair(CurrentOrder, &MI); 165 else if (MO.isDead()) { 166 // Barrier is the last instruction where MO get used. MI should not 167 // be moved above Barrier. 168 auto It = UseMap.find(MO.getReg()); 169 if (It != UseMap.end() && Barrier < It->second.first) 170 std::tie(Barrier, BarrierMI) = It->second; 171 } 172 } 173 174 if (!MI.isSafeToMove(SawStore)) { 175 // If MI has side effects, it should become a barrier for code motion. 176 // IOM is rebuild from the next instruction to prevent later 177 // instructions from being moved before this MI. 178 if (isCodeMotionBarrier(MI) && Next != MBB.end()) { 179 BuildInstOrderMap(Next, IOM); 180 SawStore = false; 181 } 182 continue; 183 } 184 185 const MachineOperand *DefMO = nullptr; 186 MachineInstr *Insert = nullptr; 187 188 // Number of live-ranges that will be shortened. We do not count 189 // live-ranges that are defined by a COPY as it could be coalesced later. 190 unsigned NumEligibleUse = 0; 191 192 for (const MachineOperand &MO : MI.operands()) { 193 if (!MO.isReg() || MO.isDead() || MO.isDebug()) 194 continue; 195 Register Reg = MO.getReg(); 196 // Do not move the instruction if it def/uses a physical register, 197 // unless it is a constant physical register or a noreg. 198 if (!Reg.isVirtual()) { 199 if (!Reg || MRI.isConstantPhysReg(Reg)) 200 continue; 201 Insert = nullptr; 202 break; 203 } 204 if (MO.isDef()) { 205 // Do not move if there is more than one def. 206 if (DefMO) { 207 Insert = nullptr; 208 break; 209 } 210 DefMO = &MO; 211 } else if (MRI.hasOneNonDBGUse(Reg) && MRI.hasOneDef(Reg) && DefMO && 212 MRI.getRegClass(DefMO->getReg()) == 213 MRI.getRegClass(MO.getReg())) { 214 // The heuristic does not handle different register classes yet 215 // (registers of different sizes, looser/tighter constraints). This 216 // is because it needs more accurate model to handle register 217 // pressure correctly. 218 MachineInstr &DefInstr = *MRI.def_instr_begin(Reg); 219 if (!TII.isCopyInstr(DefInstr)) 220 NumEligibleUse++; 221 Insert = FindDominatedInstruction(DefInstr, Insert, IOM); 222 } else { 223 Insert = nullptr; 224 break; 225 } 226 } 227 228 // If Barrier equals IOM[I], traverse forward to find if BarrierMI is 229 // after Insert, if yes, then we should not hoist. 230 for (MachineInstr *I = Insert; I && IOM[I] == Barrier; 231 I = I->getNextNode()) 232 if (I == BarrierMI) { 233 Insert = nullptr; 234 break; 235 } 236 // Move the instruction when # of shrunk live range > 1. 237 if (DefMO && Insert && NumEligibleUse > 1 && Barrier <= IOM[Insert]) { 238 MachineBasicBlock::iterator I = std::next(Insert->getIterator()); 239 // Skip all the PHI and debug instructions. 240 while (I != MBB.end() && (I->isPHI() || I->isDebugOrPseudoInstr())) 241 I = std::next(I); 242 if (I == MI.getIterator()) 243 continue; 244 245 // Update the dominator order to be the same as the insertion point. 246 // We do this to maintain a non-decreasing order without need to update 247 // all instruction orders after the insertion point. 248 unsigned NewOrder = IOM[&*I]; 249 IOM[&MI] = NewOrder; 250 NumInstrsHoistedToShrinkLiveRange++; 251 252 // Find MI's debug value following MI. 253 MachineBasicBlock::iterator EndIter = std::next(MI.getIterator()); 254 if (MI.getOperand(0).isReg()) 255 for (; EndIter != MBB.end() && EndIter->isDebugValue() && 256 EndIter->hasDebugOperandForReg(MI.getOperand(0).getReg()); 257 ++EndIter) 258 IOM[&*EndIter] = NewOrder; 259 MBB.splice(I, &MBB, MI.getIterator(), EndIter); 260 } 261 } 262 } 263 return false; 264 } 265