Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 1 | //===- LiveRangeShrink.cpp - Move instructions to shrink live range -------===// |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 2 | // |
Chandler Carruth | 2946cd7 | 2019-01-19 08:50:56 +0000 | [diff] [blame] | 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 |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 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 | ///===---------------------------------------------------------------------===// |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 16 | |
| 17 | #include "llvm/ADT/DenseMap.h" |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 18 | #include "llvm/ADT/Statistic.h" |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 19 | #include "llvm/ADT/iterator_range.h" |
| 20 | #include "llvm/CodeGen/MachineBasicBlock.h" |
| 21 | #include "llvm/CodeGen/MachineFunction.h" |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/MachineFunctionPass.h" |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/MachineInstr.h" |
| 24 | #include "llvm/CodeGen/MachineOperand.h" |
David Blaikie | b3bde2e | 2017-11-17 01:07:10 +0000 | [diff] [blame] | 25 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
| 26 | #include "llvm/CodeGen/TargetRegisterInfo.h" |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 27 | #include "llvm/Pass.h" |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 28 | #include "llvm/Support/Debug.h" |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 29 | #include "llvm/Support/raw_ostream.h" |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 30 | #include <iterator> |
| 31 | #include <utility> |
| 32 | |
| 33 | using namespace llvm; |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 34 | |
| 35 | #define DEBUG_TYPE "lrshrink" |
| 36 | |
| 37 | STATISTIC(NumInstrsHoistedToShrinkLiveRange, |
| 38 | "Number of insructions hoisted to shrink live range."); |
| 39 | |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 40 | namespace { |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 41 | |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 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 | }; |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 59 | |
| 60 | } // end anonymous namespace |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 61 | |
| 62 | char LiveRangeShrink::ID = 0; |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 63 | |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 64 | char &llvm::LiveRangeShrinkID = LiveRangeShrink::ID; |
| 65 | |
| 66 | INITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false, |
| 67 | false) |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 68 | |
| 69 | using InstOrderMap = DenseMap<MachineInstr *, unsigned>; |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 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. |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 76 | static MachineInstr *FindDominatedInstruction(MachineInstr &New, |
| 77 | MachineInstr *Old, |
| 78 | const InstOrderMap &M) { |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 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. |
Eugene Zelenko | 5df3d89 | 2017-08-24 21:21:39 +0000 | [diff] [blame] | 99 | static void BuildInstOrderMap(MachineBasicBlock::iterator Start, |
| 100 | InstOrderMap &M) { |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 101 | M.clear(); |
| 102 | unsigned i = 0; |
| 103 | for (MachineInstr &I : make_range(Start, Start->getParent()->end())) |
| 104 | M[&I] = i++; |
| 105 | } |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 106 | |
| 107 | bool LiveRangeShrink::runOnMachineFunction(MachineFunction &MF) { |
Matthias Braun | f1caa28 | 2017-12-15 22:22:58 +0000 | [diff] [blame] | 108 | if (skipFunction(MF.getFunction())) |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 109 | return false; |
| 110 | |
| 111 | MachineRegisterInfo &MRI = MF.getRegInfo(); |
| 112 | |
Nicola Zaghen | d34e60c | 2018-05-14 12:53:11 +0000 | [diff] [blame] | 113 | LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 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; |
Shiva Chen | 801bf7e | 2018-05-09 02:42:00 +0000 | [diff] [blame] | 132 | if (MI.isPHI() || MI.isDebugInstr()) |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 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() && Next != MBB.end()) { |
| 159 | BuildInstOrderMap(Next, IOM); |
| 160 | SawStore = false; |
| 161 | } |
| 162 | continue; |
| 163 | } |
| 164 | |
| 165 | const MachineOperand *DefMO = nullptr; |
| 166 | MachineInstr *Insert = nullptr; |
| 167 | |
| 168 | // Number of live-ranges that will be shortened. We do not count |
| 169 | // live-ranges that are defined by a COPY as it could be coalesced later. |
| 170 | unsigned NumEligibleUse = 0; |
| 171 | |
| 172 | for (const MachineOperand &MO : MI.operands()) { |
| 173 | if (!MO.isReg() || MO.isDead() || MO.isDebug()) |
| 174 | continue; |
| 175 | unsigned Reg = MO.getReg(); |
| 176 | // Do not move the instruction if it def/uses a physical register, |
| 177 | // unless it is a constant physical register or a noreg. |
| 178 | if (!TargetRegisterInfo::isVirtualRegister(Reg)) { |
| 179 | if (!Reg || MRI.isConstantPhysReg(Reg)) |
| 180 | continue; |
| 181 | Insert = nullptr; |
| 182 | break; |
| 183 | } |
| 184 | if (MO.isDef()) { |
| 185 | // Do not move if there is more than one def. |
| 186 | if (DefMO) { |
| 187 | Insert = nullptr; |
| 188 | break; |
| 189 | } |
| 190 | DefMO = &MO; |
| 191 | } else if (MRI.hasOneNonDBGUse(Reg) && MRI.hasOneDef(Reg) && DefMO && |
| 192 | MRI.getRegClass(DefMO->getReg()) == |
| 193 | MRI.getRegClass(MO.getReg())) { |
| 194 | // The heuristic does not handle different register classes yet |
| 195 | // (registers of different sizes, looser/tighter constraints). This |
| 196 | // is because it needs more accurate model to handle register |
| 197 | // pressure correctly. |
| 198 | MachineInstr &DefInstr = *MRI.def_instr_begin(Reg); |
| 199 | if (!DefInstr.isCopy()) |
| 200 | NumEligibleUse++; |
| 201 | Insert = FindDominatedInstruction(DefInstr, Insert, IOM); |
| 202 | } else { |
| 203 | Insert = nullptr; |
| 204 | break; |
| 205 | } |
| 206 | } |
| 207 | |
| 208 | // If Barrier equals IOM[I], traverse forward to find if BarrierMI is |
| 209 | // after Insert, if yes, then we should not hoist. |
| 210 | for (MachineInstr *I = Insert; I && IOM[I] == Barrier; |
| 211 | I = I->getNextNode()) |
| 212 | if (I == BarrierMI) { |
| 213 | Insert = nullptr; |
| 214 | break; |
| 215 | } |
| 216 | // Move the instruction when # of shrunk live range > 1. |
| 217 | if (DefMO && Insert && NumEligibleUse > 1 && Barrier <= IOM[Insert]) { |
| 218 | MachineBasicBlock::iterator I = std::next(Insert->getIterator()); |
| 219 | // Skip all the PHI and debug instructions. |
Shiva Chen | 801bf7e | 2018-05-09 02:42:00 +0000 | [diff] [blame] | 220 | while (I != MBB.end() && (I->isPHI() || I->isDebugInstr())) |
Dehao Chen | 6b737dd | 2017-05-31 23:25:25 +0000 | [diff] [blame] | 221 | I = std::next(I); |
| 222 | if (I == MI.getIterator()) |
| 223 | continue; |
| 224 | |
| 225 | // Update the dominator order to be the same as the insertion point. |
| 226 | // We do this to maintain a non-decreasing order without need to update |
| 227 | // all instruction orders after the insertion point. |
| 228 | unsigned NewOrder = IOM[&*I]; |
| 229 | IOM[&MI] = NewOrder; |
| 230 | NumInstrsHoistedToShrinkLiveRange++; |
| 231 | |
| 232 | // Find MI's debug value following MI. |
| 233 | MachineBasicBlock::iterator EndIter = std::next(MI.getIterator()); |
| 234 | if (MI.getOperand(0).isReg()) |
| 235 | for (; EndIter != MBB.end() && EndIter->isDebugValue() && |
| 236 | EndIter->getOperand(0).isReg() && |
| 237 | EndIter->getOperand(0).getReg() == 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 | } |