Home | History | Annotate | Download | only in CodeGen 
      1 //===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===//
      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 /// Rename independent subregisters looks for virtual registers with
     11 /// independently used subregisters and renames them to new virtual registers.
     12 /// Example: In the following:
     13 ///   %vreg0:sub0<read-undef> = ...
     14 ///   %vreg0:sub1 = ...
     15 ///   use %vreg0:sub0
     16 ///   %vreg0:sub0 = ...
     17 ///   use %vreg0:sub0
     18 ///   use %vreg0:sub1
     19 /// sub0 and sub1 are never used together, and we have two independent sub0
     20 /// definitions. This pass will rename to:
     21 ///   %vreg0:sub0<read-undef> = ...
     22 ///   %vreg1:sub1<read-undef> = ...
     23 ///   use %vreg1:sub1
     24 ///   %vreg2:sub1<read-undef> = ...
     25 ///   use %vreg2:sub1
     26 ///   use %vreg0:sub0
     27 //
     28 //===----------------------------------------------------------------------===//
     29 
     30 #include "LiveRangeUtils.h"
     31 #include "PHIEliminationUtils.h"
     32 #include "llvm/CodeGen/LiveInterval.h"
     33 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
     34 #include "llvm/CodeGen/MachineFunctionPass.h"
     35 #include "llvm/CodeGen/MachineRegisterInfo.h"
     36 #include "llvm/CodeGen/Passes.h"
     37 #include "llvm/Target/TargetInstrInfo.h"
     38 #include "llvm/CodeGen/MachineInstrBuilder.h"
     39 
     40 using namespace llvm;
     41 
     42 #define DEBUG_TYPE "rename-independent-subregs"
     43 
     44 namespace {
     45 
     46 class RenameIndependentSubregs : public MachineFunctionPass {
     47 public:
     48   static char ID;
     49   RenameIndependentSubregs() : MachineFunctionPass(ID) {}
     50 
     51   const char *getPassName() const override {
     52     return "Rename Disconnected Subregister Components";
     53   }
     54 
     55   void getAnalysisUsage(AnalysisUsage &AU) const override {
     56     AU.setPreservesCFG();
     57     AU.addRequired<LiveIntervals>();
     58     AU.addPreserved<LiveIntervals>();
     59     AU.addRequired<SlotIndexes>();
     60     AU.addPreserved<SlotIndexes>();
     61     MachineFunctionPass::getAnalysisUsage(AU);
     62   }
     63 
     64   bool runOnMachineFunction(MachineFunction &MF) override;
     65 
     66 private:
     67   struct SubRangeInfo {
     68     ConnectedVNInfoEqClasses ConEQ;
     69     LiveInterval::SubRange *SR;
     70     unsigned Index;
     71 
     72     SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
     73                  unsigned Index)
     74       : ConEQ(LIS), SR(&SR), Index(Index) {}
     75   };
     76 
     77   /// Split unrelated subregister components and rename them to new vregs.
     78   bool renameComponents(LiveInterval &LI) const;
     79 
     80   /// \brief Build a vector of SubRange infos and a union find set of
     81   /// equivalence classes.
     82   /// Returns true if more than 1 equivalence class was found.
     83   bool findComponents(IntEqClasses &Classes,
     84                       SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     85                       LiveInterval &LI) const;
     86 
     87   /// \brief Distribute the LiveInterval segments into the new LiveIntervals
     88   /// belonging to their class.
     89   void distribute(const IntEqClasses &Classes,
     90                   const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     91                   const SmallVectorImpl<LiveInterval*> &Intervals) const;
     92 
     93   /// \brief Constructs main liverange and add missing undef+dead flags.
     94   void computeMainRangesFixFlags(const IntEqClasses &Classes,
     95       const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     96       const SmallVectorImpl<LiveInterval*> &Intervals) const;
     97 
     98   /// Rewrite Machine Operands to use the new vreg belonging to their class.
     99   void rewriteOperands(const IntEqClasses &Classes,
    100                        const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
    101                        const SmallVectorImpl<LiveInterval*> &Intervals) const;
    102 
    103 
    104   LiveIntervals *LIS;
    105   MachineRegisterInfo *MRI;
    106   const TargetInstrInfo *TII;
    107 };
    108 
    109 } // end anonymous namespace
    110 
    111 char RenameIndependentSubregs::ID;
    112 
    113 char &llvm::RenameIndependentSubregsID = RenameIndependentSubregs::ID;
    114 
    115 INITIALIZE_PASS_BEGIN(RenameIndependentSubregs, "rename-independent-subregs",
    116                       "Rename Independent Subregisters", false, false)
    117 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
    118 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
    119 INITIALIZE_PASS_END(RenameIndependentSubregs, "rename-independent-subregs",
    120                     "Rename Independent Subregisters", false, false)
    121 
    122 bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
    123   // Shortcut: We cannot have split components with a single definition.
    124   if (LI.valnos.size() < 2)
    125     return false;
    126 
    127   SmallVector<SubRangeInfo, 4> SubRangeInfos;
    128   IntEqClasses Classes;
    129   if (!findComponents(Classes, SubRangeInfos, LI))
    130     return false;
    131 
    132   // Create a new VReg for each class.
    133   unsigned Reg = LI.reg;
    134   const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
    135   SmallVector<LiveInterval*, 4> Intervals;
    136   Intervals.push_back(&LI);
    137   DEBUG(dbgs() << PrintReg(Reg) << ": Found " << Classes.getNumClasses()
    138         << " equivalence classes.\n");
    139   DEBUG(dbgs() << PrintReg(Reg) << ": Splitting into newly created:");
    140   for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
    141        ++I) {
    142     unsigned NewVReg = MRI->createVirtualRegister(RegClass);
    143     LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
    144     Intervals.push_back(&NewLI);
    145     DEBUG(dbgs() << ' ' << PrintReg(NewVReg));
    146   }
    147   DEBUG(dbgs() << '\n');
    148 
    149   rewriteOperands(Classes, SubRangeInfos, Intervals);
    150   distribute(Classes, SubRangeInfos, Intervals);
    151   computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
    152   return true;
    153 }
    154 
    155 bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,
    156     SmallVectorImpl<RenameIndependentSubregs::SubRangeInfo> &SubRangeInfos,
    157     LiveInterval &LI) const {
    158   // First step: Create connected components for the VNInfos inside the
    159   // subranges and count the global number of such components.
    160   unsigned NumComponents = 0;
    161   for (LiveInterval::SubRange &SR : LI.subranges()) {
    162     SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents));
    163     ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
    164 
    165     unsigned NumSubComponents = ConEQ.Classify(SR);
    166     NumComponents += NumSubComponents;
    167   }
    168   // Shortcut: With only 1 subrange, the normal separate component tests are
    169   // enough and we do not need to perform the union-find on the subregister
    170   // segments.
    171   if (SubRangeInfos.size() < 2)
    172     return false;
    173 
    174   // Next step: Build union-find structure over all subranges and merge classes
    175   // across subranges when they are affected by the same MachineOperand.
    176   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
    177   Classes.grow(NumComponents);
    178   unsigned Reg = LI.reg;
    179   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
    180     if (!MO.isDef() && !MO.readsReg())
    181       continue;
    182     unsigned SubRegIdx = MO.getSubReg();
    183     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
    184     unsigned MergedID = ~0u;
    185     for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {
    186       const LiveInterval::SubRange &SR = *SRInfo.SR;
    187       if ((SR.LaneMask & LaneMask) == 0)
    188         continue;
    189       SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
    190       Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
    191                        : Pos.getBaseIndex();
    192       const VNInfo *VNI = SR.getVNInfoAt(Pos);
    193       if (VNI == nullptr)
    194         continue;
    195 
    196       // Map to local representant ID.
    197       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
    198       // Global ID
    199       unsigned ID = LocalID + SRInfo.Index;
    200       // Merge other sets
    201       MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);
    202     }
    203   }
    204 
    205   // Early exit if we ended up with a single equivalence class.
    206   Classes.compress();
    207   unsigned NumClasses = Classes.getNumClasses();
    208   return NumClasses > 1;
    209 }
    210 
    211 void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
    212     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
    213     const SmallVectorImpl<LiveInterval*> &Intervals) const {
    214   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
    215   unsigned Reg = Intervals[0]->reg;;
    216   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
    217        E = MRI->reg_nodbg_end(); I != E; ) {
    218     MachineOperand &MO = *I++;
    219     if (!MO.isDef() && !MO.readsReg())
    220       continue;
    221 
    222     MachineInstr &MI = *MO.getParent();
    223 
    224     SlotIndex Pos = LIS->getInstructionIndex(MI);
    225     unsigned SubRegIdx = MO.getSubReg();
    226     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
    227 
    228     unsigned ID = ~0u;
    229     for (const SubRangeInfo &SRInfo : SubRangeInfos) {
    230       const LiveInterval::SubRange &SR = *SRInfo.SR;
    231       if ((SR.LaneMask & LaneMask) == 0)
    232         continue;
    233       LiveRange::const_iterator I = SR.find(Pos);
    234       if (I == SR.end())
    235         continue;
    236 
    237       const VNInfo &VNI = *I->valno;
    238       // Map to local representant ID.
    239       unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
    240       // Global ID
    241       ID = Classes[LocalID + SRInfo.Index];
    242       break;
    243     }
    244 
    245     unsigned VReg = Intervals[ID]->reg;
    246     MO.setReg(VReg);
    247   }
    248   // TODO: We could attempt to recompute new register classes while visiting
    249   // the operands: Some of the split register may be fine with less constraint
    250   // classes than the original vreg.
    251 }
    252 
    253 void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
    254     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
    255     const SmallVectorImpl<LiveInterval*> &Intervals) const {
    256   unsigned NumClasses = Classes.getNumClasses();
    257   SmallVector<unsigned, 8> VNIMapping;
    258   SmallVector<LiveInterval::SubRange*, 8> SubRanges;
    259   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
    260   for (const SubRangeInfo &SRInfo : SubRangeInfos) {
    261     LiveInterval::SubRange &SR = *SRInfo.SR;
    262     unsigned NumValNos = SR.valnos.size();
    263     VNIMapping.clear();
    264     VNIMapping.reserve(NumValNos);
    265     SubRanges.clear();
    266     SubRanges.resize(NumClasses-1, nullptr);
    267     for (unsigned I = 0; I < NumValNos; ++I) {
    268       const VNInfo &VNI = *SR.valnos[I];
    269       unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
    270       unsigned ID = Classes[LocalID + SRInfo.Index];
    271       VNIMapping.push_back(ID);
    272       if (ID > 0 && SubRanges[ID-1] == nullptr)
    273         SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
    274     }
    275     DistributeRange(SR, SubRanges.data(), VNIMapping);
    276   }
    277 }
    278 
    279 static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
    280   for (const LiveInterval::SubRange &SR : LI.subranges()) {
    281     if (SR.liveAt(Pos))
    282       return true;
    283   }
    284   return false;
    285 }
    286 
    287 void RenameIndependentSubregs::computeMainRangesFixFlags(
    288     const IntEqClasses &Classes,
    289     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
    290     const SmallVectorImpl<LiveInterval*> &Intervals) const {
    291   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
    292   const SlotIndexes &Indexes = *LIS->getSlotIndexes();
    293   for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
    294     LiveInterval &LI = *Intervals[I];
    295     unsigned Reg = LI.reg;
    296 
    297     LI.removeEmptySubRanges();
    298 
    299     // There must be a def (or live-in) before every use. Splitting vregs may
    300     // violate this principle as the splitted vreg may not have a definition on
    301     // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
    302     for (const LiveInterval::SubRange &SR : LI.subranges()) {
    303       // Search for "PHI" value numbers in the subranges. We must find a live
    304       // value in each predecessor block, add an IMPLICIT_DEF where it is
    305       // missing.
    306       for (unsigned I = 0; I < SR.valnos.size(); ++I) {
    307         const VNInfo &VNI = *SR.valnos[I];
    308         if (VNI.isUnused() || !VNI.isPHIDef())
    309           continue;
    310 
    311         SlotIndex Def = VNI.def;
    312         MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
    313         for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
    314           SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
    315           if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
    316             continue;
    317 
    318           MachineBasicBlock::iterator InsertPos =
    319             llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
    320           const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF);
    321           MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
    322                                                DebugLoc(), MCDesc, Reg);
    323           SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef);
    324           SlotIndex RegDefIdx = DefIdx.getRegSlot();
    325           for (LiveInterval::SubRange &SR : LI.subranges()) {
    326             VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
    327             SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
    328           }
    329         }
    330       }
    331     }
    332 
    333     for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
    334       if (!MO.isDef())
    335         continue;
    336       unsigned SubRegIdx = MO.getSubReg();
    337       if (SubRegIdx == 0)
    338         continue;
    339       // After assigning the new vreg we may not have any other sublanes living
    340       // in and out of the instruction anymore. We need to add new dead and
    341       // undef flags in these cases.
    342       if (!MO.isUndef()) {
    343         SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
    344         if (!subRangeLiveAt(LI, Pos))
    345           MO.setIsUndef();
    346       }
    347       if (!MO.isDead()) {
    348         SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot();
    349         if (!subRangeLiveAt(LI, Pos))
    350           MO.setIsDead();
    351       }
    352     }
    353 
    354     if (I == 0)
    355       LI.clear();
    356     LIS->constructMainRangeFromSubranges(LI);
    357   }
    358 }
    359 
    360 bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
    361   // Skip renaming if liveness of subregister is not tracked.
    362   if (!MF.getSubtarget().enableSubRegLiveness())
    363     return false;
    364 
    365   DEBUG(dbgs() << "Renaming independent subregister live ranges in "
    366         << MF.getName() << '\n');
    367 
    368   LIS = &getAnalysis<LiveIntervals>();
    369   MRI = &MF.getRegInfo();
    370   TII = MF.getSubtarget().getInstrInfo();
    371 
    372   // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
    373   // created vregs end up with higher numbers but do not need to be visited as
    374   // there can't be any further splitting.
    375   bool Changed = false;
    376   for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
    377     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
    378     if (!LIS->hasInterval(Reg))
    379       continue;
    380     LiveInterval &LI = LIS->getInterval(Reg);
    381     if (!LI.hasSubRanges())
    382       continue;
    383 
    384     Changed |= renameComponents(LI);
    385   }
    386 
    387   return Changed;
    388 }
    389