265 lines · cpp
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-exception6//7///===---------------------------------------------------------------------===//8///9/// \file10/// This pass moves instructions close to the definition of its operands to11/// shrink live range of the def instruction. The code motion is limited within12/// the basic block. The moved instruction should have 1 def, and more than one13/// 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 34using namespace llvm;35 36#define DEBUG_TYPE "lrshrink"37 38STATISTIC(NumInstrsHoistedToShrinkLiveRange,39 "Number of insructions hoisted to shrink live range.");40 41namespace {42 43class LiveRangeShrink : public MachineFunctionPass {44public: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 namespace62 63char LiveRangeShrink::ID = 0;64 65char &llvm::LiveRangeShrinkID = LiveRangeShrink::ID;66 67INITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false,68 false)69 70using 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 satisfies74/// 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, return76/// \p New.77static 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 it90 // 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 this99/// pass. We can be less conservative than hasUnmodeledSideEffects() when100/// deciding whether an instruction is a barrier because it is known that pseudo101/// probes are safe to move in this pass specifically (see commit 1cb47a063e2b).102static bool isCodeMotionBarrier(MachineInstr &MI) {103 return MI.hasUnmodeledSideEffects() && !MI.isPseudoProbe();104}105 106/// Builds Instruction to its dominating order number map \p M by traversing107/// from instruction \p Start.108static 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 119bool 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 the130 // register is used last. When moving instructions up, we need to131 // make sure all its defs (including dead def) will not cross its132 // 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 not167 // 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 later177 // 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 count189 // 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 yet215 // (registers of different sizes, looser/tighter constraints). This216 // is because it needs more accurate model to handle register217 // 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 is229 // 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 update247 // 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