Home | History | Annotate | Download | only in CodeGen 
      1 //===- LiveRangeShrink.cpp - Move instructions to shrink live range -------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 ///===---------------------------------------------------------------------===//
      9 ///
     10 /// \file
     11 /// This pass moves instructions close to the definition of its operands to
     12 /// shrink live range of the def instruction. The code motion is limited within
     13 /// the basic block. The moved instruction should have 1 def, and more than one
     14 /// uses, all of which are the only use of the def.
     15 ///
     16 ///===---------------------------------------------------------------------===//
     17 
     18 #include "llvm/ADT/DenseMap.h"
     19 #include "llvm/ADT/Statistic.h"
     20 #include "llvm/ADT/iterator_range.h"
     21 #include "llvm/CodeGen/MachineBasicBlock.h"
     22 #include "llvm/CodeGen/MachineFunction.h"
     23 #include "llvm/CodeGen/MachineFunctionPass.h"
     24 #include "llvm/CodeGen/MachineInstr.h"
     25 #include "llvm/CodeGen/MachineOperand.h"
     26 #include "llvm/CodeGen/MachineRegisterInfo.h"
     27 #include "llvm/CodeGen/TargetRegisterInfo.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() && Next != MBB.end()) {
    160           BuildInstOrderMap(Next, IOM);
    161           SawStore = false;
    162         }
    163         continue;
    164       }
    165 
    166       const MachineOperand *DefMO = nullptr;
    167       MachineInstr *Insert = nullptr;
    168 
    169       // Number of live-ranges that will be shortened. We do not count
    170       // live-ranges that are defined by a COPY as it could be coalesced later.
    171       unsigned NumEligibleUse = 0;
    172 
    173       for (const MachineOperand &MO : MI.operands()) {
    174         if (!MO.isReg() || MO.isDead() || MO.isDebug())
    175           continue;
    176         unsigned Reg = MO.getReg();
    177         // Do not move the instruction if it def/uses a physical register,
    178         // unless it is a constant physical register or a noreg.
    179         if (!TargetRegisterInfo::isVirtualRegister(Reg)) {
    180           if (!Reg || MRI.isConstantPhysReg(Reg))
    181             continue;
    182           Insert = nullptr;
    183           break;
    184         }
    185         if (MO.isDef()) {
    186           // Do not move if there is more than one def.
    187           if (DefMO) {
    188             Insert = nullptr;
    189             break;
    190           }
    191           DefMO = &MO;
    192         } else if (MRI.hasOneNonDBGUse(Reg) && MRI.hasOneDef(Reg) && DefMO &&
    193                    MRI.getRegClass(DefMO->getReg()) ==
    194                        MRI.getRegClass(MO.getReg())) {
    195           // The heuristic does not handle different register classes yet
    196           // (registers of different sizes, looser/tighter constraints). This
    197           // is because it needs more accurate model to handle register
    198           // pressure correctly.
    199           MachineInstr &DefInstr = *MRI.def_instr_begin(Reg);
    200           if (!DefInstr.isCopy())
    201             NumEligibleUse++;
    202           Insert = FindDominatedInstruction(DefInstr, Insert, IOM);
    203         } else {
    204           Insert = nullptr;
    205           break;
    206         }
    207       }
    208 
    209       // If Barrier equals IOM[I], traverse forward to find if BarrierMI is
    210       // after Insert, if yes, then we should not hoist.
    211       for (MachineInstr *I = Insert; I && IOM[I] == Barrier;
    212            I = I->getNextNode())
    213         if (I == BarrierMI) {
    214           Insert = nullptr;
    215           break;
    216         }
    217       // Move the instruction when # of shrunk live range > 1.
    218       if (DefMO && Insert && NumEligibleUse > 1 && Barrier <= IOM[Insert]) {
    219         MachineBasicBlock::iterator I = std::next(Insert->getIterator());
    220         // Skip all the PHI and debug instructions.
    221         while (I != MBB.end() && (I->isPHI() || I->isDebugInstr()))
    222           I = std::next(I);
    223         if (I == MI.getIterator())
    224           continue;
    225 
    226         // Update the dominator order to be the same as the insertion point.
    227         // We do this to maintain a non-decreasing order without need to update
    228         // all instruction orders after the insertion point.
    229         unsigned NewOrder = IOM[&*I];
    230         IOM[&MI] = NewOrder;
    231         NumInstrsHoistedToShrinkLiveRange++;
    232 
    233         // Find MI's debug value following MI.
    234         MachineBasicBlock::iterator EndIter = std::next(MI.getIterator());
    235         if (MI.getOperand(0).isReg())
    236           for (; EndIter != MBB.end() && EndIter->isDebugValue() &&
    237                  EndIter->getOperand(0).isReg() &&
    238                  EndIter->getOperand(0).getReg() == 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