Index: include/llvm/CodeGen/LiveInterval.h =================================================================== --- include/llvm/CodeGen/LiveInterval.h +++ include/llvm/CodeGen/LiveInterval.h @@ -864,77 +864,5 @@ void Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI); }; - - /// Helper class that can divide MachineOperands of a virtual register into - /// equivalence classes of connected components. - /// MachineOperands belong to the same equivalence class when they are part of - /// the same SubRange segment or adjacent segments (adjacent in control - /// flow); Different subranges affected by the same MachineOperand belong to - /// the same equivalence class. - /// - /// Example: - /// vreg0:sub0 = ... - /// vreg0:sub1 = ... - /// vreg0:sub2 = ... - /// ... - /// xxx = op vreg0:sub1 - /// vreg0:sub1 = ... - /// store vreg0:sub0_sub1 - /// - /// The example contains 3 different equivalence classes: - /// - One for the (dead) vreg0:sub2 definition - /// - One containing the first vreg0:sub1 definition and its use, - /// but not the second definition! - /// - The remaining class contains all other operands involving vreg0. - /// - /// We provide a utility function here to rename disjunct classes to different - /// virtual registers. - class ConnectedSubRegClasses { - LiveIntervals &LIS; - MachineRegisterInfo &MRI; - const TargetInstrInfo &TII; - - public: - ConnectedSubRegClasses(LiveIntervals &LIS, MachineRegisterInfo &MRI, - const TargetInstrInfo &TII) - : LIS(LIS), MRI(MRI), TII(TII) {} - - /// Split unrelated subregister components and rename them to new vregs. - void renameComponents(LiveInterval &LI) const; - - private: - struct SubRangeInfo { - ConnectedVNInfoEqClasses ConEQ; - LiveInterval::SubRange *SR; - unsigned Index; - - SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR, - unsigned Index) - : ConEQ(LIS), SR(&SR), Index(Index) {} - }; - - /// \brief Build a vector of SubRange infos and a union find set of - /// equivalence classes. - /// Returns true if more than 1 equivalence class was found. - bool findComponents(IntEqClasses &Classes, - SmallVectorImpl &SubRangeInfos, - LiveInterval &LI) const; - - /// \brief Distribute the LiveInterval segments into the new LiveIntervals - /// belonging to their class. - void distribute(const IntEqClasses &Classes, - const SmallVectorImpl &SubRangeInfos, - const SmallVectorImpl &Intervals) const; - - /// \brief Constructs main liverange and add missing undef+dead flags. - void computeMainRangesFixFlags(const IntEqClasses &Classes, - const SmallVectorImpl &SubRangeInfos, - const SmallVectorImpl &Intervals) const; - - /// Rewrite Machine Operands to use the new vreg belonging to their class. - void rewriteOperands(const IntEqClasses &Classes, - const SmallVectorImpl &SubRangeInfos, - const SmallVectorImpl &Intervals) const; - }; } #endif Index: include/llvm/CodeGen/LiveIntervalAnalysis.h =================================================================== --- include/llvm/CodeGen/LiveIntervalAnalysis.h +++ include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -405,11 +405,6 @@ void splitSeparateComponents(LiveInterval &LI, SmallVectorImpl &SplitLIs); - /// Assure dead subregister definitions have their own vreg assigned. - /// This calls ConnectedSubRegClasses::splitSeparateSubRegComponent() - /// on each virtual register. - void renameDisconnectedComponents(); - /// For live interval \p LI with correct SubRanges construct matching /// information for the main live range. Expects the main live range to not /// have any segments or value numbers. Index: include/llvm/CodeGen/Passes.h =================================================================== --- include/llvm/CodeGen/Passes.h +++ include/llvm/CodeGen/Passes.h @@ -356,6 +356,11 @@ /// This pass splits the stack into a safe stack and an unsafe stack to /// protect against stack-based overflow vulnerabilities. FunctionPass *createSafeStackPass(const TargetMachine *TM = nullptr); + + /// This pass detects subregister lanes in a virtual register that are used + /// independently of other lanes and splits them into separate virtual + /// registers. + extern char &RenameIndependentSubregsID; } // End llvm namespace /// Target machine pass initializer for passes with dependencies. Use with Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -266,6 +266,7 @@ void initializeRegionOnlyViewerPass(PassRegistry&); void initializeRegionPrinterPass(PassRegistry&); void initializeRegionViewerPass(PassRegistry&); +void initializeRenameIndependentSubregsPass(PassRegistry&); void initializeReversePostOrderFunctionAttrsPass(PassRegistry&); void initializeRewriteStatepointsForGCPass(PassRegistry&); void initializeSafeStackPass(PassRegistry&); Index: lib/CodeGen/CMakeLists.txt =================================================================== --- lib/CodeGen/CMakeLists.txt +++ lib/CodeGen/CMakeLists.txt @@ -100,6 +100,7 @@ RegisterCoalescer.cpp RegisterPressure.cpp RegisterScavenging.cpp + RenameIndependentSubregs.cpp SafeStack.cpp ScheduleDAG.cpp ScheduleDAGInstrs.cpp Index: lib/CodeGen/CodeGen.cpp =================================================================== --- lib/CodeGen/CodeGen.cpp +++ lib/CodeGen/CodeGen.cpp @@ -68,6 +68,7 @@ initializePreISelIntrinsicLoweringPass(Registry); initializeProcessImplicitDefsPass(Registry); initializeRegisterCoalescerPass(Registry); + initializeRenameIndependentSubregsPass(Registry); initializeShrinkWrapPass(Registry); initializeSlotIndexesPass(Registry); initializeStackColoringPass(Registry); Index: lib/CodeGen/LiveInterval.cpp =================================================================== --- lib/CodeGen/LiveInterval.cpp +++ lib/CodeGen/LiveInterval.cpp @@ -20,16 +20,14 @@ #include "llvm/CodeGen/LiveInterval.h" -#include "PHIEliminationUtils.h" +#include "LiveRangeUtils.h" #include "RegisterCoalescer.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" -#include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" #include using namespace llvm; @@ -1176,40 +1174,6 @@ return EqClass.getNumClasses(); } -template -static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[], - EqClassesT VNIClasses) { - // Move segments to new intervals. - LiveRange::iterator J = LR.begin(), E = LR.end(); - while (J != E && VNIClasses[J->valno->id] == 0) - ++J; - for (LiveRange::iterator I = J; I != E; ++I) { - if (unsigned eq = VNIClasses[I->valno->id]) { - assert((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) && - "New intervals should be empty"); - SplitLRs[eq-1]->segments.push_back(*I); - } else - *J++ = *I; - } - LR.segments.erase(J, E); - - // Transfer VNInfos to their new owners and renumber them. - unsigned j = 0, e = LR.getNumValNums(); - while (j != e && VNIClasses[j] == 0) - ++j; - for (unsigned i = j; i != e; ++i) { - VNInfo *VNI = LR.getValNumInfo(i); - if (unsigned eq = VNIClasses[i]) { - VNI->id = SplitLRs[eq-1]->getNumValNums(); - SplitLRs[eq-1]->valnos.push_back(VNI); - } else { - VNI->id = j; - LR.valnos[j++] = VNI; - } - } - LR.valnos.resize(j); -} - void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[], MachineRegisterInfo &MRI) { // Rewrite instructions. @@ -1276,232 +1240,3 @@ // Distribute main liverange. DistributeRange(LI, LIV, EqClass); } - -void ConnectedSubRegClasses::renameComponents(LiveInterval &LI) const { - // Shortcut: We cannot have split components with a single definition. - if (LI.valnos.size() < 2) - return; - - SmallVector SubRangeInfos; - IntEqClasses Classes; - if (!findComponents(Classes, SubRangeInfos, LI)) - return; - - // Create a new VReg for each class. - unsigned Reg = LI.reg; - const TargetRegisterClass *RegClass = MRI.getRegClass(Reg); - SmallVector Intervals; - Intervals.push_back(&LI); - for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses; - ++I) { - unsigned NewVReg = MRI.createVirtualRegister(RegClass); - LiveInterval &NewLI = LIS.createEmptyInterval(NewVReg); - Intervals.push_back(&NewLI); - } - - rewriteOperands(Classes, SubRangeInfos, Intervals); - distribute(Classes, SubRangeInfos, Intervals); - computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals); -} - -bool ConnectedSubRegClasses::findComponents(IntEqClasses &Classes, - SmallVectorImpl &SubRangeInfos, - LiveInterval &LI) const { - // First step: Create connected components for the VNInfos inside the - // subranges and count the global number of such components. - unsigned NumComponents = 0; - for (LiveInterval::SubRange &SR : LI.subranges()) { - SubRangeInfos.push_back(SubRangeInfo(LIS, SR, NumComponents)); - ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ; - - unsigned NumSubComponents = ConEQ.Classify(SR); - NumComponents += NumSubComponents; - } - // Shortcut: With only 1 subrange, the normal separate component tests are - // enough and we do not need to perform the union-find on the subregister - // segments. - if (SubRangeInfos.size() < 2) - return false; - - // Next step: Build union-find structure over all subranges and merge classes - // across subranges when they are affected by the same MachineOperand. - const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); - Classes.grow(NumComponents); - unsigned Reg = LI.reg; - for (const MachineOperand &MO : MRI.reg_nodbg_operands(Reg)) { - if (!MO.isDef() && !MO.readsReg()) - continue; - unsigned SubRegIdx = MO.getSubReg(); - LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx); - unsigned MergedID = ~0u; - for (ConnectedSubRegClasses::SubRangeInfo &SRInfo : SubRangeInfos) { - const LiveInterval::SubRange &SR = *SRInfo.SR; - if ((SR.LaneMask & LaneMask) == 0) - continue; - SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent()); - Pos = MO.isDef() ? Pos.getRegSlot(MO.isEarlyClobber()) - : Pos.getBaseIndex(); - const VNInfo *VNI = SR.getVNInfoAt(Pos); - if (VNI == nullptr) - continue; - - // Map to local representant ID. - unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI); - // Global ID - unsigned ID = LocalID + SRInfo.Index; - // Merge other sets - MergedID = MergedID == ~0u ? ID : Classes.join(MergedID, ID); - } - } - - // Early exit if we ended up with a single equivalence class. - Classes.compress(); - unsigned NumClasses = Classes.getNumClasses(); - return NumClasses > 1; -} - -void ConnectedSubRegClasses::rewriteOperands(const IntEqClasses &Classes, - const SmallVectorImpl &SubRangeInfos, - const SmallVectorImpl &Intervals) const { - const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo(); - unsigned Reg = Intervals[0]->reg;; - for (MachineRegisterInfo::reg_nodbg_iterator I = MRI.reg_nodbg_begin(Reg), - E = MRI.reg_nodbg_end(); I != E; ) { - MachineOperand &MO = *I++; - if (!MO.isDef() && !MO.readsReg()) - continue; - - MachineInstr &MI = *MO.getParent(); - - SlotIndex Pos = LIS.getInstructionIndex(MI); - unsigned SubRegIdx = MO.getSubReg(); - LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx); - - unsigned ID = ~0u; - for (const SubRangeInfo &SRInfo : SubRangeInfos) { - const LiveInterval::SubRange &SR = *SRInfo.SR; - if ((SR.LaneMask & LaneMask) == 0) - continue; - LiveRange::const_iterator I = SR.find(Pos); - if (I == SR.end()) - continue; - - const VNInfo &VNI = *I->valno; - // Map to local representant ID. - unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI); - // Global ID - ID = Classes[LocalID + SRInfo.Index]; - break; - } - - unsigned VReg = Intervals[ID]->reg; - MO.setReg(VReg); - } -} - -void ConnectedSubRegClasses::distribute(const IntEqClasses &Classes, - const SmallVectorImpl &SubRangeInfos, - const SmallVectorImpl &Intervals) const { - unsigned NumClasses = Classes.getNumClasses(); - SmallVector VNIMapping; - SmallVector SubRanges; - BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); - for (const SubRangeInfo &SRInfo : SubRangeInfos) { - LiveInterval::SubRange &SR = *SRInfo.SR; - unsigned NumValNos = SR.valnos.size(); - VNIMapping.clear(); - VNIMapping.reserve(NumValNos); - SubRanges.clear(); - SubRanges.resize(NumClasses-1, nullptr); - for (unsigned I = 0; I < NumValNos; ++I) { - const VNInfo &VNI = *SR.valnos[I]; - unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI); - unsigned ID = Classes[LocalID + SRInfo.Index]; - VNIMapping.push_back(ID); - if (ID > 0 && SubRanges[ID-1] == nullptr) - SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask); - } - DistributeRange(SR, SubRanges.data(), VNIMapping); - } -} - -static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) { - for (const LiveInterval::SubRange &SR : LI.subranges()) { - if (SR.liveAt(Pos)) - return true; - } - return false; -} - -void ConnectedSubRegClasses::computeMainRangesFixFlags( - const IntEqClasses &Classes, - const SmallVectorImpl &SubRangeInfos, - const SmallVectorImpl &Intervals) const { - BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator(); - const SlotIndexes &Indexes = *LIS.getSlotIndexes(); - for (size_t I = 0, E = Intervals.size(); I < E; ++I) { - LiveInterval &LI = *Intervals[I]; - unsigned Reg = LI.reg; - - LI.removeEmptySubRanges(); - - // There must be a def (or live-in) before every use. Splitting vregs may - // violate this principle as the splitted vreg may not have a definition on - // every path. Fix this by creating IMPLICIT_DEF instruction as necessary. - for (const LiveInterval::SubRange &SR : LI.subranges()) { - // Search for "PHI" value numbers in the subranges. We must find a live - // value in each predecessor block, add an IMPLICIT_DEF where it is - // missing. - for (unsigned I = 0; I < SR.valnos.size(); ++I) { - const VNInfo &VNI = *SR.valnos[I]; - if (VNI.isUnused() || !VNI.isPHIDef()) - continue; - - SlotIndex Def = VNI.def; - MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def); - for (MachineBasicBlock *PredMBB : MBB.predecessors()) { - SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB); - if (subRangeLiveAt(LI, PredEnd.getPrevSlot())) - continue; - - MachineBasicBlock::iterator InsertPos = - llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg); - const MCInstrDesc &MCDesc = TII.get(TargetOpcode::IMPLICIT_DEF); - MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos, - DebugLoc(), MCDesc, Reg); - SlotIndex DefIdx = LIS.InsertMachineInstrInMaps(*ImpDef); - SlotIndex RegDefIdx = DefIdx.getRegSlot(); - for (LiveInterval::SubRange &SR : LI.subranges()) { - VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator); - SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI)); - } - } - } - } - - for (MachineOperand &MO : MRI.reg_nodbg_operands(Reg)) { - if (!MO.isDef()) - continue; - unsigned SubRegIdx = MO.getSubReg(); - if (SubRegIdx == 0) - continue; - // After assigning the new vreg we may not have any other sublanes living - // in and out of the instruction anymore. We need to add new dead and - // undef flags in these cases. - if (!MO.isUndef()) { - SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent()); - if (!subRangeLiveAt(LI, Pos)) - MO.setIsUndef(); - } - if (!MO.isDead()) { - SlotIndex Pos = LIS.getInstructionIndex(*MO.getParent()).getDeadSlot(); - if (!subRangeLiveAt(LI, Pos)) - MO.setIsDead(); - } - } - - if (I == 0) - LI.clear(); - LIS.constructMainRangeFromSubranges(LI); - } -} Index: lib/CodeGen/LiveIntervalAnalysis.cpp =================================================================== --- lib/CodeGen/LiveIntervalAnalysis.cpp +++ lib/CodeGen/LiveIntervalAnalysis.cpp @@ -1570,22 +1570,6 @@ ConEQ.Distribute(LI, SplitLIs.data(), *MRI); } -void LiveIntervals::renameDisconnectedComponents() { - ConnectedSubRegClasses SubRegClasses(*this, *MRI, *TII); - - // Iterate over all vregs. Note that we query getNumVirtRegs() the newly - // created vregs end up with higher numbers but do not need to be visited as - // there can't be any further splitting. - for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; ++I) { - unsigned Reg = TargetRegisterInfo::index2VirtReg(I); - LiveInterval *LI = VirtRegIntervals[Reg]; - if (LI == nullptr || !LI->hasSubRanges()) - continue; - - SubRegClasses.renameComponents(*LI); - } -} - void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) { assert(LRCalc && "LRCalc not initialized."); LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator()); Index: lib/CodeGen/LiveRangeUtils.h =================================================================== --- /dev/null +++ lib/CodeGen/LiveRangeUtils.h @@ -0,0 +1,59 @@ +//===-- LiveRangeUtils.h - Live Range modification utilities ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// This file contains helper function to modify live ranges. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_CODEGEN_LIVERANGEUTILS_H +#define LLVM_LIB_CODEGEN_LIVERANGEUTILS_H + +#include "llvm/CodeGen/LiveInterval.h" + +namespace llvm { + +/// Helper function to to split live segments assigned to different classes to +/// new live range objects. +template +static void DistributeRange(LiveRangeT &LR, LiveRangeT *SplitLRs[], + EqClassesT VNIClasses) { + // Move segments to new intervals. + typename LiveRangeT::iterator J = LR.begin(), E = LR.end(); + while (J != E && VNIClasses[J->valno->id] == 0) + ++J; + for (typename LiveRangeT::iterator I = J; I != E; ++I) { + if (unsigned eq = VNIClasses[I->valno->id]) { + assert((SplitLRs[eq-1]->empty() || SplitLRs[eq-1]->expiredAt(I->start)) && + "New intervals should be empty"); + SplitLRs[eq-1]->segments.push_back(*I); + } else + *J++ = *I; + } + LR.segments.erase(J, E); + + // Transfer VNInfos to their new owners and renumber them. + unsigned j = 0, e = LR.getNumValNums(); + while (j != e && VNIClasses[j] == 0) + ++j; + for (unsigned i = j; i != e; ++i) { + VNInfo *VNI = LR.getValNumInfo(i); + if (unsigned eq = VNIClasses[i]) { + VNI->id = SplitLRs[eq-1]->getNumValNums(); + SplitLRs[eq-1]->valnos.push_back(VNI); + } else { + VNI->id = j; + LR.valnos[j++] = VNI; + } + } + LR.valnos.resize(j); +} + +} // End llvm namespace + +#endif Index: lib/CodeGen/MachineScheduler.cpp =================================================================== --- lib/CodeGen/MachineScheduler.cpp +++ lib/CodeGen/MachineScheduler.cpp @@ -881,17 +881,6 @@ ShouldTrackPressure = SchedImpl->shouldTrackPressure(); ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks(); - - if (ShouldTrackLaneMasks) { - if (!ShouldTrackPressure) - report_fatal_error("ShouldTrackLaneMasks requires ShouldTrackPressure"); - // Dead subregister defs have no users and therefore no dependencies, - // moving them around may cause liveintervals to degrade into multiple - // components. Change independent components to have their own vreg to avoid - // this. - if (!DisconnectedComponentsRenamed) - LIS->renameDisconnectedComponents(); - } } // Setup the register pressure trackers for the top scheduled top and bottom Index: lib/CodeGen/TargetPassConfig.cpp =================================================================== --- lib/CodeGen/TargetPassConfig.cpp +++ lib/CodeGen/TargetPassConfig.cpp @@ -775,6 +775,8 @@ addPass(&TwoAddressInstructionPassID, false); addPass(&RegisterCoalescerID); + addPass(&RenameIndependentSubregsID); + // PreRA instruction scheduling. addPass(&MachineSchedulerID);