1327952Sdim//===- LiveRangeShrink.cpp - Move instructions to shrink live range -------===// 2319461Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6319461Sdim// 7319461Sdim///===---------------------------------------------------------------------===// 8319461Sdim/// 9319461Sdim/// \file 10319461Sdim/// This pass moves instructions close to the definition of its operands to 11319461Sdim/// shrink live range of the def instruction. The code motion is limited within 12319461Sdim/// the basic block. The moved instruction should have 1 def, and more than one 13319461Sdim/// uses, all of which are the only use of the def. 14319461Sdim/// 15319461Sdim///===---------------------------------------------------------------------===// 16327952Sdim 17327952Sdim#include "llvm/ADT/DenseMap.h" 18319461Sdim#include "llvm/ADT/Statistic.h" 19327952Sdim#include "llvm/ADT/iterator_range.h" 20327952Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 21327952Sdim#include "llvm/CodeGen/MachineFunction.h" 22319461Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 23327952Sdim#include "llvm/CodeGen/MachineInstr.h" 24327952Sdim#include "llvm/CodeGen/MachineOperand.h" 25319461Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 26327952Sdim#include "llvm/CodeGen/TargetRegisterInfo.h" 27360784Sdim#include "llvm/InitializePasses.h" 28327952Sdim#include "llvm/Pass.h" 29319461Sdim#include "llvm/Support/Debug.h" 30327952Sdim#include "llvm/Support/raw_ostream.h" 31327952Sdim#include <iterator> 32327952Sdim#include <utility> 33319461Sdim 34327952Sdimusing namespace llvm; 35327952Sdim 36319461Sdim#define DEBUG_TYPE "lrshrink" 37319461Sdim 38319461SdimSTATISTIC(NumInstrsHoistedToShrinkLiveRange, 39319461Sdim "Number of insructions hoisted to shrink live range."); 40319461Sdim 41327952Sdimnamespace { 42319461Sdim 43319461Sdimclass LiveRangeShrink : public MachineFunctionPass { 44319461Sdimpublic: 45319461Sdim static char ID; 46319461Sdim 47319461Sdim LiveRangeShrink() : MachineFunctionPass(ID) { 48319461Sdim initializeLiveRangeShrinkPass(*PassRegistry::getPassRegistry()); 49319461Sdim } 50319461Sdim 51319461Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 52319461Sdim AU.setPreservesCFG(); 53319461Sdim MachineFunctionPass::getAnalysisUsage(AU); 54319461Sdim } 55319461Sdim 56319461Sdim StringRef getPassName() const override { return "Live Range Shrink"; } 57319461Sdim 58319461Sdim bool runOnMachineFunction(MachineFunction &MF) override; 59319461Sdim}; 60319461Sdim 61327952Sdim} // end anonymous namespace 62327952Sdim 63319461Sdimchar LiveRangeShrink::ID = 0; 64327952Sdim 65319461Sdimchar &llvm::LiveRangeShrinkID = LiveRangeShrink::ID; 66319461Sdim 67319461SdimINITIALIZE_PASS(LiveRangeShrink, "lrshrink", "Live Range Shrink Pass", false, 68319461Sdim false) 69319461Sdim 70327952Sdimusing InstOrderMap = DenseMap<MachineInstr *, unsigned>; 71327952Sdim 72319461Sdim/// Returns \p New if it's dominated by \p Old, otherwise return \p Old. 73319461Sdim/// \p M maintains a map from instruction to its dominating order that satisfies 74319461Sdim/// M[A] > M[B] guarantees that A is dominated by B. 75319461Sdim/// If \p New is not in \p M, return \p Old. Otherwise if \p Old is null, return 76319461Sdim/// \p New. 77327952Sdimstatic MachineInstr *FindDominatedInstruction(MachineInstr &New, 78327952Sdim MachineInstr *Old, 79327952Sdim const InstOrderMap &M) { 80319461Sdim auto NewIter = M.find(&New); 81319461Sdim if (NewIter == M.end()) 82319461Sdim return Old; 83319461Sdim if (Old == nullptr) 84319461Sdim return &New; 85319461Sdim unsigned OrderOld = M.find(Old)->second; 86319461Sdim unsigned OrderNew = NewIter->second; 87319461Sdim if (OrderOld != OrderNew) 88319461Sdim return OrderOld < OrderNew ? &New : Old; 89319461Sdim // OrderOld == OrderNew, we need to iterate down from Old to see if it 90319461Sdim // can reach New, if yes, New is dominated by Old. 91319461Sdim for (MachineInstr *I = Old->getNextNode(); M.find(I)->second == OrderNew; 92319461Sdim I = I->getNextNode()) 93319461Sdim if (I == &New) 94319461Sdim return &New; 95319461Sdim return Old; 96319461Sdim} 97319461Sdim 98319461Sdim/// Builds Instruction to its dominating order number map \p M by traversing 99319461Sdim/// from instruction \p Start. 100327952Sdimstatic void BuildInstOrderMap(MachineBasicBlock::iterator Start, 101327952Sdim InstOrderMap &M) { 102319461Sdim M.clear(); 103319461Sdim unsigned i = 0; 104319461Sdim for (MachineInstr &I : make_range(Start, Start->getParent()->end())) 105319461Sdim M[&I] = i++; 106319461Sdim} 107319461Sdim 108319461Sdimbool LiveRangeShrink::runOnMachineFunction(MachineFunction &MF) { 109327952Sdim if (skipFunction(MF.getFunction())) 110319461Sdim return false; 111319461Sdim 112319461Sdim MachineRegisterInfo &MRI = MF.getRegInfo(); 113319461Sdim 114341825Sdim LLVM_DEBUG(dbgs() << "**** Analysing " << MF.getName() << '\n'); 115319461Sdim 116319461Sdim InstOrderMap IOM; 117319461Sdim // Map from register to instruction order (value of IOM) where the 118319461Sdim // register is used last. When moving instructions up, we need to 119319461Sdim // make sure all its defs (including dead def) will not cross its 120319461Sdim // last use when moving up. 121319461Sdim DenseMap<unsigned, std::pair<unsigned, MachineInstr *>> UseMap; 122319461Sdim 123319461Sdim for (MachineBasicBlock &MBB : MF) { 124319461Sdim if (MBB.empty()) 125319461Sdim continue; 126319461Sdim bool SawStore = false; 127319461Sdim BuildInstOrderMap(MBB.begin(), IOM); 128319461Sdim UseMap.clear(); 129319461Sdim 130319461Sdim for (MachineBasicBlock::iterator Next = MBB.begin(); Next != MBB.end();) { 131319461Sdim MachineInstr &MI = *Next; 132319461Sdim ++Next; 133341825Sdim if (MI.isPHI() || MI.isDebugInstr()) 134319461Sdim continue; 135319461Sdim if (MI.mayStore()) 136319461Sdim SawStore = true; 137319461Sdim 138319461Sdim unsigned CurrentOrder = IOM[&MI]; 139319461Sdim unsigned Barrier = 0; 140319461Sdim MachineInstr *BarrierMI = nullptr; 141319461Sdim for (const MachineOperand &MO : MI.operands()) { 142319461Sdim if (!MO.isReg() || MO.isDebug()) 143319461Sdim continue; 144319461Sdim if (MO.isUse()) 145319461Sdim UseMap[MO.getReg()] = std::make_pair(CurrentOrder, &MI); 146319461Sdim else if (MO.isDead() && UseMap.count(MO.getReg())) 147319461Sdim // Barrier is the last instruction where MO get used. MI should not 148319461Sdim // be moved above Barrier. 149319461Sdim if (Barrier < UseMap[MO.getReg()].first) { 150319461Sdim Barrier = UseMap[MO.getReg()].first; 151319461Sdim BarrierMI = UseMap[MO.getReg()].second; 152319461Sdim } 153319461Sdim } 154319461Sdim 155319461Sdim if (!MI.isSafeToMove(nullptr, SawStore)) { 156319461Sdim // If MI has side effects, it should become a barrier for code motion. 157319461Sdim // IOM is rebuild from the next instruction to prevent later 158319461Sdim // instructions from being moved before this MI. 159319461Sdim if (MI.hasUnmodeledSideEffects() && Next != MBB.end()) { 160319461Sdim BuildInstOrderMap(Next, IOM); 161319461Sdim SawStore = false; 162319461Sdim } 163319461Sdim continue; 164319461Sdim } 165319461Sdim 166319461Sdim const MachineOperand *DefMO = nullptr; 167319461Sdim MachineInstr *Insert = nullptr; 168319461Sdim 169319461Sdim // Number of live-ranges that will be shortened. We do not count 170319461Sdim // live-ranges that are defined by a COPY as it could be coalesced later. 171319461Sdim unsigned NumEligibleUse = 0; 172319461Sdim 173319461Sdim for (const MachineOperand &MO : MI.operands()) { 174319461Sdim if (!MO.isReg() || MO.isDead() || MO.isDebug()) 175319461Sdim continue; 176360784Sdim Register Reg = MO.getReg(); 177319461Sdim // Do not move the instruction if it def/uses a physical register, 178319461Sdim // unless it is a constant physical register or a noreg. 179360784Sdim if (!Register::isVirtualRegister(Reg)) { 180319461Sdim if (!Reg || MRI.isConstantPhysReg(Reg)) 181319461Sdim continue; 182319461Sdim Insert = nullptr; 183319461Sdim break; 184319461Sdim } 185319461Sdim if (MO.isDef()) { 186319461Sdim // Do not move if there is more than one def. 187319461Sdim if (DefMO) { 188319461Sdim Insert = nullptr; 189319461Sdim break; 190319461Sdim } 191319461Sdim DefMO = &MO; 192319461Sdim } else if (MRI.hasOneNonDBGUse(Reg) && MRI.hasOneDef(Reg) && DefMO && 193319461Sdim MRI.getRegClass(DefMO->getReg()) == 194319461Sdim MRI.getRegClass(MO.getReg())) { 195319461Sdim // The heuristic does not handle different register classes yet 196319461Sdim // (registers of different sizes, looser/tighter constraints). This 197319461Sdim // is because it needs more accurate model to handle register 198319461Sdim // pressure correctly. 199319461Sdim MachineInstr &DefInstr = *MRI.def_instr_begin(Reg); 200319461Sdim if (!DefInstr.isCopy()) 201319461Sdim NumEligibleUse++; 202319461Sdim Insert = FindDominatedInstruction(DefInstr, Insert, IOM); 203319461Sdim } else { 204319461Sdim Insert = nullptr; 205319461Sdim break; 206319461Sdim } 207319461Sdim } 208319461Sdim 209319461Sdim // If Barrier equals IOM[I], traverse forward to find if BarrierMI is 210319461Sdim // after Insert, if yes, then we should not hoist. 211319461Sdim for (MachineInstr *I = Insert; I && IOM[I] == Barrier; 212319461Sdim I = I->getNextNode()) 213319461Sdim if (I == BarrierMI) { 214319461Sdim Insert = nullptr; 215319461Sdim break; 216319461Sdim } 217319461Sdim // Move the instruction when # of shrunk live range > 1. 218319461Sdim if (DefMO && Insert && NumEligibleUse > 1 && Barrier <= IOM[Insert]) { 219319461Sdim MachineBasicBlock::iterator I = std::next(Insert->getIterator()); 220319461Sdim // Skip all the PHI and debug instructions. 221341825Sdim while (I != MBB.end() && (I->isPHI() || I->isDebugInstr())) 222319461Sdim I = std::next(I); 223319461Sdim if (I == MI.getIterator()) 224319461Sdim continue; 225319461Sdim 226319461Sdim // Update the dominator order to be the same as the insertion point. 227319461Sdim // We do this to maintain a non-decreasing order without need to update 228319461Sdim // all instruction orders after the insertion point. 229319461Sdim unsigned NewOrder = IOM[&*I]; 230319461Sdim IOM[&MI] = NewOrder; 231319461Sdim NumInstrsHoistedToShrinkLiveRange++; 232319461Sdim 233319461Sdim // Find MI's debug value following MI. 234319461Sdim MachineBasicBlock::iterator EndIter = std::next(MI.getIterator()); 235319461Sdim if (MI.getOperand(0).isReg()) 236319461Sdim for (; EndIter != MBB.end() && EndIter->isDebugValue() && 237319461Sdim EndIter->getOperand(0).isReg() && 238319461Sdim EndIter->getOperand(0).getReg() == MI.getOperand(0).getReg(); 239319461Sdim ++EndIter, ++Next) 240319461Sdim IOM[&*EndIter] = NewOrder; 241319461Sdim MBB.splice(I, &MBB, MI.getIterator(), EndIter); 242319461Sdim } 243319461Sdim } 244319461Sdim } 245319461Sdim return false; 246319461Sdim} 247