LCOV - code coverage report
Current view: top level - lib/CodeGen - RenameIndependentSubregs.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 169 169 100.0 %
Date: 2017-09-14 15:23:50 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             : ///   %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/MachineInstrBuilder.h"
      36             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      37             : #include "llvm/CodeGen/Passes.h"
      38             : #include "llvm/Target/TargetInstrInfo.h"
      39             : 
      40             : using namespace llvm;
      41             : 
      42             : #define DEBUG_TYPE "rename-independent-subregs"
      43             : 
      44             : namespace {
      45             : 
      46       15307 : class RenameIndependentSubregs : public MachineFunctionPass {
      47             : public:
      48             :   static char ID;
      49       15399 :   RenameIndependentSubregs() : MachineFunctionPass(ID) {}
      50             : 
      51       15363 :   StringRef getPassName() const override {
      52       15363 :     return "Rename Disconnected Subregister Components";
      53             :   }
      54             : 
      55       15348 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      56       15348 :     AU.setPreservesCFG();
      57       15348 :     AU.addRequired<LiveIntervals>();
      58       15348 :     AU.addPreserved<LiveIntervals>();
      59       15348 :     AU.addRequired<SlotIndexes>();
      60       15348 :     AU.addPreserved<SlotIndexes>();
      61       15348 :     MachineFunctionPass::getAnalysisUsage(AU);
      62       15348 :   }
      63             : 
      64             :   bool runOnMachineFunction(MachineFunction &MF) override;
      65             : 
      66             : private:
      67      639098 :   struct SubRangeInfo {
      68             :     ConnectedVNInfoEqClasses ConEQ;
      69             :     LiveInterval::SubRange *SR;
      70             :     unsigned Index;
      71             : 
      72             :     SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
      73             :                  unsigned Index)
      74      210638 :       : 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       20212 : INITIALIZE_PASS_BEGIN(RenameIndependentSubregs, DEBUG_TYPE,
     116             :                       "Rename Independent Subregisters", false, false)
     117       20212 : INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
     118       20212 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
     119      151199 : INITIALIZE_PASS_END(RenameIndependentSubregs, DEBUG_TYPE,
     120             :                     "Rename Independent Subregisters", false, false)
     121             : 
     122       47722 : bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
     123             :   // Shortcut: We cannot have split components with a single definition.
     124       95444 :   if (LI.valnos.size() < 2)
     125             :     return false;
     126             : 
     127       34235 :   SmallVector<SubRangeInfo, 4> SubRangeInfos;
     128       68470 :   IntEqClasses Classes;
     129       34235 :   if (!findComponents(Classes, SubRangeInfos, LI))
     130             :     return false;
     131             : 
     132             :   // Create a new VReg for each class.
     133          24 :   unsigned Reg = LI.reg;
     134          48 :   const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
     135          24 :   SmallVector<LiveInterval*, 4> Intervals;
     136          24 :   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          64 :   for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
     141             :        ++I) {
     142          40 :     unsigned NewVReg = MRI->createVirtualRegister(RegClass);
     143          40 :     LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
     144          40 :     Intervals.push_back(&NewLI);
     145             :     DEBUG(dbgs() << ' ' << PrintReg(NewVReg));
     146             :   }
     147             :   DEBUG(dbgs() << '\n');
     148             : 
     149          24 :   rewriteOperands(Classes, SubRangeInfos, Intervals);
     150          24 :   distribute(Classes, SubRangeInfos, Intervals);
     151          24 :   computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
     152          24 :   return true;
     153             : }
     154             : 
     155       34235 : 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       34235 :   unsigned NumComponents = 0;
     161      173789 :   for (LiveInterval::SubRange &SR : LI.subranges()) {
     162      315957 :     SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents));
     163      210638 :     ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
     164             : 
     165      105319 :     unsigned NumSubComponents = ConEQ.Classify(SR);
     166      105319 :     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       68470 :   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       68468 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     177       34234 :   Classes.grow(NumComponents);
     178       34234 :   unsigned Reg = LI.reg;
     179      269522 :   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     180      166891 :     if (!MO.isDef() && !MO.readsReg())
     181          71 :       continue;
     182      166749 :     unsigned SubRegIdx = MO.getSubReg();
     183      333498 :     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
     184      166749 :     unsigned MergedID = ~0u;
     185     1772820 :     for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {
     186      552912 :       const LiveInterval::SubRange &SR = *SRInfo.SR;
     187     1105824 :       if ((SR.LaneMask & LaneMask).none())
     188             :         continue;
     189      560390 :       SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
     190      669873 :       Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
     191             :                        : Pos.getBaseIndex();
     192      560150 :       const VNInfo *VNI = SR.getVNInfoAt(Pos);
     193      279955 :       if (VNI == nullptr)
     194             :         continue;
     195             : 
     196             :       // Map to local representant ID.
     197      559910 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
     198             :       // Global ID
     199      279955 :       unsigned ID = LocalID + SRInfo.Index;
     200             :       // Merge other sets
     201      279955 :       MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);
     202             :     }
     203             :   }
     204             : 
     205             :   // Early exit if we ended up with a single equivalence class.
     206       34234 :   Classes.compress();
     207       34234 :   unsigned NumClasses = Classes.getNumClasses();
     208       34234 :   return NumClasses > 1;
     209             : }
     210             : 
     211          24 : void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
     212             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     213             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     214          48 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     215          48 :   unsigned Reg = Intervals[0]->reg;
     216          24 :   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
     217         326 :        E = MRI->reg_nodbg_end(); I != E; ) {
     218         556 :     MachineOperand &MO = *I++;
     219         279 :     if (!MO.isDef() && !MO.readsReg())
     220           1 :       continue;
     221             : 
     222         554 :     SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
     223         673 :     Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
     224             :                      : Pos.getBaseIndex();
     225         277 :     unsigned SubRegIdx = MO.getSubReg();
     226         554 :     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
     227             : 
     228         277 :     unsigned ID = ~0u;
     229        1624 :     for (const SubRangeInfo &SRInfo : SubRangeInfos) {
     230        1070 :       const LiveInterval::SubRange &SR = *SRInfo.SR;
     231        2140 :       if ((SR.LaneMask & LaneMask).none())
     232             :         continue;
     233         555 :       const VNInfo *VNI = SR.getVNInfoAt(Pos);
     234         277 :       if (VNI == nullptr)
     235             :         continue;
     236             : 
     237             :       // Map to local representant ID.
     238         554 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
     239             :       // Global ID
     240         554 :       ID = Classes[LocalID + SRInfo.Index];
     241             :       break;
     242             :     }
     243             : 
     244         554 :     unsigned VReg = Intervals[ID]->reg;
     245         277 :     MO.setReg(VReg);
     246             : 
     247         277 :     if (MO.isTied() && Reg != VReg) {
     248             :       /// Undef use operands are not tracked in the equivalence class but need
     249             :       /// to be update if they are tied.
     250           2 :       MO.getParent()->substituteRegister(Reg, VReg, 0, TRI);
     251             : 
     252             :       // substituteRegister breaks the iterator, so restart.
     253           2 :       I = MRI->reg_nodbg_begin(Reg);
     254             :     }
     255             :   }
     256             :   // TODO: We could attempt to recompute new register classes while visiting
     257             :   // the operands: Some of the split register may be fine with less constraint
     258             :   // classes than the original vreg.
     259          24 : }
     260             : 
     261          24 : void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
     262             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     263             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     264          24 :   unsigned NumClasses = Classes.getNumClasses();
     265          48 :   SmallVector<unsigned, 8> VNIMapping;
     266          48 :   SmallVector<LiveInterval::SubRange*, 8> SubRanges;
     267          48 :   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
     268         176 :   for (const SubRangeInfo &SRInfo : SubRangeInfos) {
     269         104 :     LiveInterval::SubRange &SR = *SRInfo.SR;
     270         208 :     unsigned NumValNos = SR.valnos.size();
     271         104 :     VNIMapping.clear();
     272         104 :     VNIMapping.reserve(NumValNos);
     273         104 :     SubRanges.clear();
     274         104 :     SubRanges.resize(NumClasses-1, nullptr);
     275         330 :     for (unsigned I = 0; I < NumValNos; ++I) {
     276         452 :       const VNInfo &VNI = *SR.valnos[I];
     277         452 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
     278         452 :       unsigned ID = Classes[LocalID + SRInfo.Index];
     279         226 :       VNIMapping.push_back(ID);
     280         373 :       if (ID > 0 && SubRanges[ID-1] == nullptr)
     281         189 :         SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
     282             :     }
     283         312 :     DistributeRange(SR, SubRanges.data(), VNIMapping);
     284             :   }
     285          24 : }
     286             : 
     287             : static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
     288         699 :   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     289         335 :     if (SR.liveAt(Pos))
     290             :       return true;
     291             :   }
     292             :   return false;
     293             : }
     294             : 
     295          24 : void RenameIndependentSubregs::computeMainRangesFixFlags(
     296             :     const IntEqClasses &Classes,
     297             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     298             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     299          48 :   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
     300          24 :   const SlotIndexes &Indexes = *LIS->getSlotIndexes();
     301         112 :   for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
     302         128 :     LiveInterval &LI = *Intervals[I];
     303          64 :     unsigned Reg = LI.reg;
     304             : 
     305          64 :     LI.removeEmptySubRanges();
     306             : 
     307             :     // There must be a def (or live-in) before every use. Splitting vregs may
     308             :     // violate this principle as the splitted vreg may not have a definition on
     309             :     // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
     310         236 :     for (const LiveInterval::SubRange &SR : LI.subranges()) {
     311             :       // Search for "PHI" value numbers in the subranges. We must find a live
     312             :       // value in each predecessor block, add an IMPLICIT_DEF where it is
     313             :       // missing.
     314         915 :       for (unsigned I = 0; I < SR.valnos.size(); ++I) {
     315         466 :         const VNInfo &VNI = *SR.valnos[I];
     316         446 :         if (VNI.isUnused() || !VNI.isPHIDef())
     317         180 :           continue;
     318             : 
     319          53 :         SlotIndex Def = VNI.def;
     320          53 :         MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
     321         212 :         for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
     322         106 :           SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
     323         212 :           if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
     324          99 :             continue;
     325             : 
     326             :           MachineBasicBlock::iterator InsertPos =
     327           7 :             llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
     328          14 :           const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF);
     329             :           MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
     330          21 :                                                DebugLoc(), MCDesc, Reg);
     331          14 :           SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef);
     332           7 :           SlotIndex RegDefIdx = DefIdx.getRegSlot();
     333          21 :           for (LiveInterval::SubRange &SR : LI.subranges()) {
     334           7 :             VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
     335          14 :             SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
     336             :           }
     337             :         }
     338             :       }
     339             :     }
     340             : 
     341         477 :     for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     342         285 :       if (!MO.isDef())
     343             :         continue;
     344         124 :       unsigned SubRegIdx = MO.getSubReg();
     345         124 :       if (SubRegIdx == 0)
     346             :         continue;
     347             :       // After assigning the new vreg we may not have any other sublanes living
     348             :       // in and out of the instruction anymore. We need to add new dead and
     349             :       // undef flags in these cases.
     350         115 :       if (!MO.isUndef()) {
     351         170 :         SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
     352          85 :         if (!subRangeLiveAt(LI, Pos))
     353             :           MO.setIsUndef();
     354             :       }
     355         115 :       if (!MO.isDead()) {
     356         342 :         SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot();
     357         114 :         if (!subRangeLiveAt(LI, Pos))
     358             :           MO.setIsDead();
     359             :       }
     360             :     }
     361             : 
     362          64 :     if (I == 0)
     363          24 :       LI.clear();
     364          64 :     LIS->constructMainRangeFromSubranges(LI);
     365             :     // A def of a subregister may be a use of other register lanes. Replacing
     366             :     // such a def with a def of a different register will eliminate the use,
     367             :     // and may cause the recorded live range to be larger than the actual
     368             :     // liveness in the program IR.
     369          64 :     LIS->shrinkToUses(&LI);
     370             :   }
     371          24 : }
     372             : 
     373      134821 : bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
     374             :   // Skip renaming if liveness of subregister is not tracked.
     375      134821 :   MRI = &MF.getRegInfo();
     376      134821 :   if (!MRI->subRegLivenessEnabled())
     377             :     return false;
     378             : 
     379             :   DEBUG(dbgs() << "Renaming independent subregister live ranges in "
     380             :         << MF.getName() << '\n');
     381             : 
     382       17581 :   LIS = &getAnalysis<LiveIntervals>();
     383       17581 :   TII = MF.getSubtarget().getInstrInfo();
     384             : 
     385             :   // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
     386             :   // created vregs end up with higher numbers but do not need to be visited as
     387             :   // there can't be any further splitting.
     388       17581 :   bool Changed = false;
     389      679284 :   for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
     390     1288244 :     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
     391     1288244 :     if (!LIS->hasInterval(Reg))
     392      438473 :       continue;
     393      205649 :     LiveInterval &LI = LIS->getInterval(Reg);
     394      363576 :     if (!LI.hasSubRanges())
     395      157927 :       continue;
     396             : 
     397       47722 :     Changed |= renameComponents(LI);
     398             :   }
     399             : 
     400             :   return Changed;
     401             : }

Generated by: LCOV version 1.13