LCOV - code coverage report
Current view: top level - lib/CodeGen - RenameIndependentSubregs.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 147 147 100.0 %
Date: 2018-07-13 00:08:38 Functions: 12 13 92.3 %
Legend: Lines: hit not hit

          Line data    Source code
       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             : ///   %0:sub0<read-undef> = ...
      14             : ///   %0:sub1 = ...
      15             : ///   use %0:sub0
      16             : ///   %0:sub0 = ...
      17             : ///   use %0:sub0
      18             : ///   use %0:sub1
      19             : /// sub0 and sub1 are never used together, and we have two independent sub0
      20             : /// definitions. This pass will rename to:
      21             : ///   %0:sub0<read-undef> = ...
      22             : ///   %1:sub1<read-undef> = ...
      23             : ///   use %1:sub1
      24             : ///   %2:sub1<read-undef> = ...
      25             : ///   use %2:sub1
      26             : ///   use %0:sub0
      27             : //
      28             : //===----------------------------------------------------------------------===//
      29             : 
      30             : #include "LiveRangeUtils.h"
      31             : #include "PHIEliminationUtils.h"
      32             : #include "llvm/CodeGen/LiveInterval.h"
      33             : #include "llvm/CodeGen/LiveIntervals.h"
      34             : #include "llvm/CodeGen/MachineFunctionPass.h"
      35             : #include "llvm/CodeGen/MachineInstrBuilder.h"
      36             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      37             : #include "llvm/CodeGen/Passes.h"
      38             : #include "llvm/CodeGen/TargetInstrInfo.h"
      39             : 
      40             : using namespace llvm;
      41             : 
      42             : #define DEBUG_TYPE "rename-independent-subregs"
      43             : 
      44             : namespace {
      45             : 
      46       18930 : class RenameIndependentSubregs : public MachineFunctionPass {
      47             : public:
      48             :   static char ID;
      49       19027 :   RenameIndependentSubregs() : MachineFunctionPass(ID) {}
      50             : 
      51       18895 :   StringRef getPassName() const override {
      52       18895 :     return "Rename Disconnected Subregister Components";
      53             :   }
      54             : 
      55       18879 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      56       18879 :     AU.setPreservesCFG();
      57             :     AU.addRequired<LiveIntervals>();
      58             :     AU.addPreserved<LiveIntervals>();
      59             :     AU.addRequired<SlotIndexes>();
      60             :     AU.addPreserved<SlotIndexes>();
      61       18879 :     MachineFunctionPass::getAnalysisUsage(AU);
      62       18879 :   }
      63             : 
      64             :   bool runOnMachineFunction(MachineFunction &MF) override;
      65             : 
      66             : private:
      67      377046 :   struct SubRangeInfo {
      68             :     ConnectedVNInfoEqClasses ConEQ;
      69             :     LiveInterval::SubRange *SR;
      70             :     unsigned Index;
      71             : 
      72             :     SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
      73             :                  unsigned Index)
      74      242748 :       : 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             :   /// 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             :   /// 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             :   /// 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       26316 : INITIALIZE_PASS_BEGIN(RenameIndependentSubregs, DEBUG_TYPE,
     116             :                       "Rename Independent Subregisters", false, false)
     117       26316 : INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
     118       26316 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
     119      146610 : INITIALIZE_PASS_END(RenameIndependentSubregs, DEBUG_TYPE,
     120             :                     "Rename Independent Subregisters", false, false)
     121             : 
     122       60177 : bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
     123             :   // Shortcut: We cannot have split components with a single definition.
     124       60177 :   if (LI.valnos.size() < 2)
     125             :     return false;
     126             : 
     127       38995 :   SmallVector<SubRangeInfo, 4> SubRangeInfos;
     128             :   IntEqClasses Classes;
     129       38995 :   if (!findComponents(Classes, SubRangeInfos, LI))
     130             :     return false;
     131             : 
     132             :   // Create a new VReg for each class.
     133          34 :   unsigned Reg = LI.reg;
     134          34 :   const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
     135             :   SmallVector<LiveInterval*, 4> Intervals;
     136          34 :   Intervals.push_back(&LI);
     137             :   LLVM_DEBUG(dbgs() << printReg(Reg) << ": Found " << Classes.getNumClasses()
     138             :                     << " equivalence classes.\n");
     139             :   LLVM_DEBUG(dbgs() << printReg(Reg) << ": Splitting into newly created:");
     140          85 :   for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
     141             :        ++I) {
     142         102 :     unsigned NewVReg = MRI->createVirtualRegister(RegClass);
     143          51 :     LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
     144          51 :     Intervals.push_back(&NewLI);
     145             :     LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg));
     146             :   }
     147             :   LLVM_DEBUG(dbgs() << '\n');
     148             : 
     149          34 :   rewriteOperands(Classes, SubRangeInfos, Intervals);
     150          34 :   distribute(Classes, SubRangeInfos, Intervals);
     151          34 :   computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
     152             :   return true;
     153             : }
     154             : 
     155       38995 : 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      160369 :   for (LiveInterval::SubRange &SR : LI.subranges()) {
     162      364122 :     SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents));
     163      121374 :     ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
     164             : 
     165      121374 :     unsigned NumSubComponents = ConEQ.Classify(SR);
     166      121374 :     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       38995 :   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       38992 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     177       38992 :   Classes.grow(NumComponents);
     178       38992 :   unsigned Reg = LI.reg;
     179      264281 :   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     180      186379 :     if (!MO.isDef() && !MO.readsReg())
     181             :       continue;
     182             :     unsigned SubRegIdx = MO.getSubReg();
     183      186215 :     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
     184             :     unsigned MergedID = ~0u;
     185     1466871 :     for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {
     186      640328 :       const LiveInterval::SubRange &SR = *SRInfo.SR;
     187      640328 :       if ((SR.LaneMask & LaneMask).none())
     188             :         continue;
     189      306630 :       SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
     190      306630 :       Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
     191             :                        : Pos.getBaseIndex();
     192      306630 :       const VNInfo *VNI = SR.getVNInfoAt(Pos);
     193      306391 :       if (VNI == nullptr)
     194             :         continue;
     195             : 
     196             :       // Map to local representant ID.
     197      306391 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
     198             :       // Global ID
     199      306391 :       unsigned ID = LocalID + SRInfo.Index;
     200             :       // Merge other sets
     201      306391 :       MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);
     202             :     }
     203             :   }
     204             : 
     205             :   // Early exit if we ended up with a single equivalence class.
     206       38992 :   Classes.compress();
     207       38992 :   unsigned NumClasses = Classes.getNumClasses();
     208       38992 :   return NumClasses > 1;
     209             : }
     210             : 
     211          34 : void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
     212             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     213             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     214          34 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     215          34 :   unsigned Reg = Intervals[0]->reg;
     216          34 :   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
     217         336 :        E = MRI->reg_nodbg_end(); I != E; ) {
     218             :     MachineOperand &MO = *I++;
     219         304 :     if (!MO.isDef() && !MO.readsReg())
     220             :       continue;
     221             : 
     222         300 :     auto *MI = MO.getParent();
     223         300 :     SlotIndex Pos = LIS->getInstructionIndex(*MI);
     224         300 :     Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
     225             :                      : Pos.getBaseIndex();
     226             :     unsigned SubRegIdx = MO.getSubReg();
     227         300 :     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
     228             : 
     229             :     unsigned ID = ~0u;
     230        1810 :     for (const SubRangeInfo &SRInfo : SubRangeInfos) {
     231        1055 :       const LiveInterval::SubRange &SR = *SRInfo.SR;
     232        1055 :       if ((SR.LaneMask & LaneMask).none())
     233             :         continue;
     234         303 :       const VNInfo *VNI = SR.getVNInfoAt(Pos);
     235         300 :       if (VNI == nullptr)
     236             :         continue;
     237             : 
     238             :       // Map to local representant ID.
     239         300 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
     240             :       // Global ID
     241         300 :       ID = Classes[LocalID + SRInfo.Index];
     242             :       break;
     243             :     }
     244             : 
     245         600 :     unsigned VReg = Intervals[ID]->reg;
     246         300 :     MO.setReg(VReg);
     247             : 
     248         300 :     if (MO.isTied() && Reg != VReg) {
     249             :       /// Undef use operands are not tracked in the equivalence class,
     250             :       /// but need to be updated if they are tied; take care to only
     251             :       /// update the tied operand.
     252             :       unsigned OperandNo = MI->getOperandNo(&MO);
     253           3 :       unsigned TiedIdx = MI->findTiedOperandIdx(OperandNo);
     254           6 :       MI->getOperand(TiedIdx).setReg(VReg);
     255             : 
     256             :       // above substitution breaks the iterator, so restart.
     257           3 :       I = MRI->reg_nodbg_begin(Reg);
     258             :     }
     259             :   }
     260             :   // TODO: We could attempt to recompute new register classes while visiting
     261             :   // the operands: Some of the split register may be fine with less constraint
     262             :   // classes than the original vreg.
     263          34 : }
     264             : 
     265          34 : void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
     266             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     267             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     268          34 :   unsigned NumClasses = Classes.getNumClasses();
     269             :   SmallVector<unsigned, 8> VNIMapping;
     270             :   SmallVector<LiveInterval::SubRange*, 8> SubRanges;
     271          34 :   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
     272         284 :   for (const SubRangeInfo &SRInfo : SubRangeInfos) {
     273         125 :     LiveInterval::SubRange &SR = *SRInfo.SR;
     274         125 :     unsigned NumValNos = SR.valnos.size();
     275             :     VNIMapping.clear();
     276         125 :     VNIMapping.reserve(NumValNos);
     277             :     SubRanges.clear();
     278         125 :     SubRanges.resize(NumClasses-1, nullptr);
     279         591 :     for (unsigned I = 0; I < NumValNos; ++I) {
     280         466 :       const VNInfo &VNI = *SR.valnos[I];
     281         233 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
     282         466 :       unsigned ID = Classes[LocalID + SRInfo.Index];
     283         233 :       VNIMapping.push_back(ID);
     284         381 :       if (ID > 0 && SubRanges[ID-1] == nullptr)
     285         154 :         SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
     286             :     }
     287         250 :     DistributeRange(SR, SubRanges.data(), VNIMapping);
     288             :   }
     289          34 : }
     290             : 
     291             : static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
     292         416 :   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     293         347 :     if (SR.liveAt(Pos))
     294             :       return true;
     295             :   }
     296             :   return false;
     297             : }
     298             : 
     299          34 : void RenameIndependentSubregs::computeMainRangesFixFlags(
     300             :     const IntEqClasses &Classes,
     301             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     302             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     303          34 :   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
     304          34 :   const SlotIndexes &Indexes = *LIS->getSlotIndexes();
     305         204 :   for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
     306          85 :     LiveInterval &LI = *Intervals[I];
     307          85 :     unsigned Reg = LI.reg;
     308             : 
     309          85 :     LI.removeEmptySubRanges();
     310             : 
     311             :     // There must be a def (or live-in) before every use. Splitting vregs may
     312             :     // violate this principle as the splitted vreg may not have a definition on
     313             :     // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
     314         217 :     for (const LiveInterval::SubRange &SR : LI.subranges()) {
     315             :       // Search for "PHI" value numbers in the subranges. We must find a live
     316             :       // value in each predecessor block, add an IMPLICIT_DEF where it is
     317             :       // missing.
     318         993 :       for (unsigned I = 0; I < SR.valnos.size(); ++I) {
     319         243 :         const VNInfo &VNI = *SR.valnos[I];
     320         468 :         if (VNI.isUnused() || !VNI.isPHIDef())
     321         196 :           continue;
     322             : 
     323          47 :         SlotIndex Def = VNI.def;
     324          47 :         MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
     325         141 :         for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
     326             :           SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
     327          94 :           if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
     328          85 :             continue;
     329             : 
     330             :           MachineBasicBlock::iterator InsertPos =
     331           9 :             llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
     332           9 :           const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF);
     333             :           MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
     334          18 :                                                DebugLoc(), MCDesc, Reg);
     335           9 :           SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef);
     336             :           SlotIndex RegDefIdx = DefIdx.getRegSlot();
     337          20 :           for (LiveInterval::SubRange &SR : LI.subranges()) {
     338          11 :             VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
     339          11 :             SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
     340             :           }
     341             :         }
     342             :       }
     343             :     }
     344             : 
     345         482 :     for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     346         312 :       if (!MO.isDef())
     347             :         continue;
     348             :       unsigned SubRegIdx = MO.getSubReg();
     349         139 :       if (SubRegIdx == 0)
     350             :         continue;
     351             :       // After assigning the new vreg we may not have any other sublanes living
     352             :       // in and out of the instruction anymore. We need to add new dead and
     353             :       // undef flags in these cases.
     354         127 :       if (!MO.isUndef()) {
     355          90 :         SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
     356          90 :         if (!subRangeLiveAt(LI, Pos))
     357             :           MO.setIsUndef();
     358             :       }
     359         127 :       if (!MO.isDead()) {
     360         126 :         SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot();
     361         126 :         if (!subRangeLiveAt(LI, Pos))
     362             :           MO.setIsDead();
     363             :       }
     364             :     }
     365             : 
     366          85 :     if (I == 0)
     367             :       LI.clear();
     368          85 :     LIS->constructMainRangeFromSubranges(LI);
     369             :     // A def of a subregister may be a use of other register lanes. Replacing
     370             :     // such a def with a def of a different register will eliminate the use,
     371             :     // and may cause the recorded live range to be larger than the actual
     372             :     // liveness in the program IR.
     373          85 :     LIS->shrinkToUses(&LI);
     374             :   }
     375          34 : }
     376             : 
     377      183191 : bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
     378             :   // Skip renaming if liveness of subregister is not tracked.
     379      183191 :   MRI = &MF.getRegInfo();
     380      183191 :   if (!MRI->subRegLivenessEnabled())
     381             :     return false;
     382             : 
     383             :   LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "
     384             :                     << MF.getName() << '\n');
     385             : 
     386       23230 :   LIS = &getAnalysis<LiveIntervals>();
     387       23230 :   TII = MF.getSubtarget().getInstrInfo();
     388             : 
     389             :   // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
     390             :   // created vregs end up with higher numbers but do not need to be visited as
     391             :   // there can't be any further splitting.
     392             :   bool Changed = false;
     393      820654 :   for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
     394      774194 :     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
     395     1303967 :     if (!LIS->hasInterval(Reg))
     396      529773 :       continue;
     397      244421 :     LiveInterval &LI = LIS->getInterval(Reg);
     398      428665 :     if (!LI.hasSubRanges())
     399      184244 :       continue;
     400             : 
     401       60177 :     Changed |= renameComponents(LI);
     402             :   }
     403             : 
     404             :   return Changed;
     405             : }

Generated by: LCOV version 1.13