LCOV - code coverage report
Current view: top level - lib/CodeGen - RenameIndependentSubregs.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 145 145 100.0 %
Date: 2018-06-17 00:07:59 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       18799 : class RenameIndependentSubregs : public MachineFunctionPass {
      47             : public:
      48             :   static char ID;
      49       18895 :   RenameIndependentSubregs() : MachineFunctionPass(ID) {}
      50             : 
      51       18765 :   StringRef getPassName() const override {
      52       18765 :     return "Rename Disconnected Subregister Components";
      53             :   }
      54             : 
      55       18749 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      56       18749 :     AU.setPreservesCFG();
      57             :     AU.addRequired<LiveIntervals>();
      58             :     AU.addPreserved<LiveIntervals>();
      59             :     AU.addRequired<SlotIndexes>();
      60             :     AU.addPreserved<SlotIndexes>();
      61       18749 :     MachineFunctionPass::getAnalysisUsage(AU);
      62       18749 :   }
      63             : 
      64             :   bool runOnMachineFunction(MachineFunction &MF) override;
      65             : 
      66             : private:
      67      348891 :   struct SubRangeInfo {
      68             :     ConnectedVNInfoEqClasses ConEQ;
      69             :     LiveInterval::SubRange *SR;
      70             :     unsigned Index;
      71             : 
      72             :     SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
      73             :                  unsigned Index)
      74      226570 :       : 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       26770 : INITIALIZE_PASS_BEGIN(RenameIndependentSubregs, DEBUG_TYPE,
     116             :                       "Rename Independent Subregisters", false, false)
     117       26770 : INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
     118       26770 : INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
     119      148112 : INITIALIZE_PASS_END(RenameIndependentSubregs, DEBUG_TYPE,
     120             :                     "Rename Independent Subregisters", false, false)
     121             : 
     122       53303 : bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
     123             :   // Shortcut: We cannot have split components with a single definition.
     124       53303 :   if (LI.valnos.size() < 2)
     125             :     return false;
     126             : 
     127       36155 :   SmallVector<SubRangeInfo, 4> SubRangeInfos;
     128             :   IntEqClasses Classes;
     129       36155 :   if (!findComponents(Classes, SubRangeInfos, LI))
     130             :     return false;
     131             : 
     132             :   // Create a new VReg for each class.
     133          31 :   unsigned Reg = LI.reg;
     134          31 :   const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
     135             :   SmallVector<LiveInterval*, 4> Intervals;
     136          31 :   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          76 :   for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
     141             :        ++I) {
     142          90 :     unsigned NewVReg = MRI->createVirtualRegister(RegClass);
     143          45 :     LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
     144          45 :     Intervals.push_back(&NewLI);
     145             :     LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg));
     146             :   }
     147             :   LLVM_DEBUG(dbgs() << '\n');
     148             : 
     149          31 :   rewriteOperands(Classes, SubRangeInfos, Intervals);
     150          31 :   distribute(Classes, SubRangeInfos, Intervals);
     151          31 :   computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
     152             :   return true;
     153             : }
     154             : 
     155       36155 : 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      149440 :   for (LiveInterval::SubRange &SR : LI.subranges()) {
     162      339855 :     SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents));
     163      113285 :     ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
     164             : 
     165      113285 :     unsigned NumSubComponents = ConEQ.Classify(SR);
     166      113285 :     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       36155 :   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       36152 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     177       36152 :   Classes.grow(NumComponents);
     178       36152 :   unsigned Reg = LI.reg;
     179      243459 :   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     180      171237 :     if (!MO.isDef() && !MO.readsReg())
     181             :       continue;
     182             :     unsigned SubRegIdx = MO.getSubReg();
     183      171073 :     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
     184             :     unsigned MergedID = ~0u;
     185     1347701 :     for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {
     186      588314 :       const LiveInterval::SubRange &SR = *SRInfo.SR;
     187      588314 :       if ((SR.LaneMask & LaneMask).none())
     188             :         continue;
     189      287443 :       SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
     190      287443 :       Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
     191             :                        : Pos.getBaseIndex();
     192      287443 :       const VNInfo *VNI = SR.getVNInfoAt(Pos);
     193      287200 :       if (VNI == nullptr)
     194             :         continue;
     195             : 
     196             :       // Map to local representant ID.
     197      287200 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
     198             :       // Global ID
     199      287200 :       unsigned ID = LocalID + SRInfo.Index;
     200             :       // Merge other sets
     201      287200 :       MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID);
     202             :     }
     203             :   }
     204             : 
     205             :   // Early exit if we ended up with a single equivalence class.
     206       36152 :   Classes.compress();
     207       36152 :   unsigned NumClasses = Classes.getNumClasses();
     208       36152 :   return NumClasses > 1;
     209             : }
     210             : 
     211          31 : void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
     212             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     213             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     214          31 :   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
     215          31 :   unsigned Reg = Intervals[0]->reg;
     216          31 :   for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
     217         331 :        E = MRI->reg_nodbg_end(); I != E; ) {
     218             :     MachineOperand &MO = *I++;
     219         301 :     if (!MO.isDef() && !MO.readsReg())
     220             :       continue;
     221             : 
     222         299 :     SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
     223         299 :     Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber())
     224             :                      : Pos.getBaseIndex();
     225             :     unsigned SubRegIdx = MO.getSubReg();
     226         299 :     LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
     227             : 
     228             :     unsigned ID = ~0u;
     229        1773 :     for (const SubRangeInfo &SRInfo : SubRangeInfos) {
     230        1036 :       const LiveInterval::SubRange &SR = *SRInfo.SR;
     231        1036 :       if ((SR.LaneMask & LaneMask).none())
     232             :         continue;
     233         300 :       const VNInfo *VNI = SR.getVNInfoAt(Pos);
     234         299 :       if (VNI == nullptr)
     235             :         continue;
     236             : 
     237             :       // Map to local representant ID.
     238         299 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
     239             :       // Global ID
     240         299 :       ID = Classes[LocalID + SRInfo.Index];
     241             :       break;
     242             :     }
     243             : 
     244         598 :     unsigned VReg = Intervals[ID]->reg;
     245         299 :     MO.setReg(VReg);
     246             : 
     247         299 :     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          31 : }
     260             : 
     261          31 : void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
     262             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     263             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     264          31 :   unsigned NumClasses = Classes.getNumClasses();
     265             :   SmallVector<unsigned, 8> VNIMapping;
     266             :   SmallVector<LiveInterval::SubRange*, 8> SubRanges;
     267          31 :   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
     268         263 :   for (const SubRangeInfo &SRInfo : SubRangeInfos) {
     269         116 :     LiveInterval::SubRange &SR = *SRInfo.SR;
     270         116 :     unsigned NumValNos = SR.valnos.size();
     271             :     VNIMapping.clear();
     272         116 :     VNIMapping.reserve(NumValNos);
     273             :     SubRanges.clear();
     274         116 :     SubRanges.resize(NumClasses-1, nullptr);
     275         544 :     for (unsigned I = 0; I < NumValNos; ++I) {
     276         428 :       const VNInfo &VNI = *SR.valnos[I];
     277         214 :       unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
     278         428 :       unsigned ID = Classes[LocalID + SRInfo.Index];
     279         214 :       VNIMapping.push_back(ID);
     280         342 :       if (ID > 0 && SubRanges[ID-1] == nullptr)
     281         136 :         SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
     282             :     }
     283         232 :     DistributeRange(SR, SubRanges.data(), VNIMapping);
     284             :   }
     285          31 : }
     286             : 
     287             : static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
     288         412 :   for (const LiveInterval::SubRange &SR : LI.subranges()) {
     289         354 :     if (SR.liveAt(Pos))
     290             :       return true;
     291             :   }
     292             :   return false;
     293             : }
     294             : 
     295          31 : void RenameIndependentSubregs::computeMainRangesFixFlags(
     296             :     const IntEqClasses &Classes,
     297             :     const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
     298             :     const SmallVectorImpl<LiveInterval*> &Intervals) const {
     299          31 :   BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
     300          31 :   const SlotIndexes &Indexes = *LIS->getSlotIndexes();
     301         183 :   for (size_t I = 0, E = Intervals.size(); I < E; ++I) {
     302          76 :     LiveInterval &LI = *Intervals[I];
     303          76 :     unsigned Reg = LI.reg;
     304             : 
     305          76 :     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         204 :     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         922 :       for (unsigned I = 0; I < SR.valnos.size(); ++I) {
     315         222 :         const VNInfo &VNI = *SR.valnos[I];
     316         435 :         if (VNI.isUnused() || !VNI.isPHIDef())
     317         179 :           continue;
     318             : 
     319          43 :         SlotIndex Def = VNI.def;
     320          43 :         MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
     321         129 :         for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
     322             :           SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
     323          86 :           if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
     324          78 :             continue;
     325             : 
     326             :           MachineBasicBlock::iterator InsertPos =
     327           8 :             llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
     328           8 :           const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF);
     329             :           MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
     330          16 :                                                DebugLoc(), MCDesc, Reg);
     331           8 :           SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef);
     332             :           SlotIndex RegDefIdx = DefIdx.getRegSlot();
     333          16 :           for (LiveInterval::SubRange &SR : LI.subranges()) {
     334           8 :             VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
     335           8 :             SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
     336             :           }
     337             :         }
     338             :       }
     339             :     }
     340             : 
     341         460 :     for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
     342         308 :       if (!MO.isDef())
     343             :         continue;
     344             :       unsigned SubRegIdx = MO.getSubReg();
     345         134 :       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         124 :       if (!MO.isUndef()) {
     351          91 :         SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
     352          91 :         if (!subRangeLiveAt(LI, Pos))
     353             :           MO.setIsUndef();
     354             :       }
     355         124 :       if (!MO.isDead()) {
     356         123 :         SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot();
     357         123 :         if (!subRangeLiveAt(LI, Pos))
     358             :           MO.setIsDead();
     359             :       }
     360             :     }
     361             : 
     362          76 :     if (I == 0)
     363             :       LI.clear();
     364          76 :     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          76 :     LIS->shrinkToUses(&LI);
     370             :   }
     371          31 : }
     372             : 
     373      180454 : bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
     374             :   // Skip renaming if liveness of subregister is not tracked.
     375      180454 :   MRI = &MF.getRegInfo();
     376      180454 :   if (!MRI->subRegLivenessEnabled())
     377             :     return false;
     378             : 
     379             :   LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "
     380             :                     << MF.getName() << '\n');
     381             : 
     382       23203 :   LIS = &getAnalysis<LiveIntervals>();
     383       23203 :   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             :   bool Changed = false;
     389      776148 :   for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) {
     390      729742 :     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
     391     1210773 :     if (!LIS->hasInterval(Reg))
     392      481031 :       continue;
     393      248711 :     LiveInterval &LI = LIS->getInterval(Reg);
     394      444119 :     if (!LI.hasSubRanges())
     395      195408 :       continue;
     396             : 
     397       53303 :     Changed |= renameComponents(LI);
     398             :   }
     399             : 
     400             :   return Changed;
     401             : }

Generated by: LCOV version 1.13