From a065cf13cd6da7ecd142a71957f048f5141d2954 Mon Sep 17 00:00:00 2001 From: Matthias Braun Date: Wed, 7 Jan 2015 23:58:38 +0000 Subject: [PATCH] RegisterCoalescer: Fix valuesIdentical() in some subrange merge cases. I got confused and assumed SrcIdx/DstIdx of the CoalescerPair is a subregister index in SrcReg/DstReg, but they are actually subregister indices of the coalesced register that get you back to SrcReg/DstReg when applied. Fixed the bug, improved comments and simplified code accordingly. Testcase by Tom Stellard! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@225415 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/RegisterCoalescer.cpp | 171 +++++++++++++--------------- test/CodeGen/R600/subreg-coalescer-crash.ll | 45 ++++++++ 2 files changed, 126 insertions(+), 90 deletions(-) create mode 100644 test/CodeGen/R600/subreg-coalescer-crash.ll diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp index ad9aec36a97..7a0c36ee347 100644 --- a/lib/CodeGen/RegisterCoalescer.cpp +++ b/lib/CodeGen/RegisterCoalescer.cpp @@ -158,18 +158,16 @@ namespace { /// Add the LiveRange @p ToMerge as a subregister liverange of @p LI. /// Subranges in @p LI which only partially interfere with the desired - /// LaneMask are split as necessary. - /// @p DestLaneMask are the lanes that @p ToMerge will end up in after the - /// merge, @p PrevLaneMask the ones it currently occupies. + /// LaneMask are split as necessary. @p LaneMask are the lanes that + /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange + /// lanemasks already adjusted to the coalesced register. void mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge, - unsigned DstLaneMask, unsigned PrevLaneMask, - CoalescerPair &CP); + unsigned LaneMask, CoalescerPair &CP); /// Join the liveranges of two subregisters. Joins @p RRange into /// @p LRange, @p RRange may be invalid afterwards. - void joinSubRegRanges(LiveRange &LRange, unsigned LMask, - LiveRange &RRange, unsigned RMask, - const CoalescerPair &CP); + void joinSubRegRanges(LiveRange &LRange, LiveRange &RRange, + unsigned LaneMask, const CoalescerPair &CP); /// We found a non-trivially-coalescable copy. If /// the source value number is defined by a copy from the destination reg @@ -1542,18 +1540,19 @@ class JoinVals { /// (Main) register we work on. const unsigned Reg; - /// When coalescing a subregister range this is the LaneMask in Reg. - unsigned SubRegMask; + // Reg (and therefore the values in this liverange) will end up as subregister + // SubIdx in the coalesced register. Either CP.DstIdx or CP.SrcIdx. + const unsigned SubIdx; + // The LaneMask that this liverange will occupy the coalesced register. May be + // smaller than the lanemask produced by SubIdx when merging subranges. + const unsigned LaneMask; + /// This is true when joining sub register ranges, false when joining main /// ranges. const bool SubRangeJoin; /// Whether the current LiveInterval tracks subregister liveness. const bool TrackSubRegLiveness; - // Location of this register in the final joined register. - // Either CP.DstIdx or CP.SrcIdx. - const unsigned SubIdx; - // Values that will be present in the final live range. SmallVectorImpl &NewVNInfo; @@ -1644,7 +1643,7 @@ class JoinVals { SmallVector Vals; unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const; - VNInfo *stripCopies(VNInfo *VNI, unsigned LaneMask, unsigned &Reg) const; + std::pair followCopyChain(const VNInfo *VNI) const; bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const; ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); void computeAssignment(unsigned ValNo, JoinVals &Other); @@ -1654,16 +1653,14 @@ class JoinVals { bool isPrunedValue(unsigned ValNo, JoinVals &Other); public: - JoinVals(LiveRange &LR, unsigned Reg, unsigned subIdx, - SmallVectorImpl &newVNInfo, - const CoalescerPair &cp, LiveIntervals *lis, - const TargetRegisterInfo *tri, unsigned SubRegMask, - bool SubRangeJoin, bool TrackSubRegLiveness) - : LR(LR), Reg(Reg), SubRegMask(SubRegMask), SubRangeJoin(SubRangeJoin), - TrackSubRegLiveness(TrackSubRegLiveness), SubIdx(subIdx), + JoinVals(LiveRange &LR, unsigned Reg, unsigned SubIdx, unsigned LaneMask, + SmallVectorImpl &newVNInfo, const CoalescerPair &cp, + LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin, + bool TrackSubRegLiveness) + : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask), + SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness), NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()), - TRI(tri), Assignments(LR.getNumValNums(), -1), - Vals(LR.getNumValNums()) + TRI(TRI), Assignments(LR.getNumValNums(), -1), Vals(LR.getNumValNums()) {} /// Analyze defs in LR and compute a value mapping in NewVNInfo. @@ -1715,29 +1712,33 @@ unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) } /// Find the ultimate value that VNI was copied from. -VNInfo *JoinVals::stripCopies(VNInfo *VNI, unsigned LaneMask, unsigned &Reg) - const { +std::pair JoinVals::followCopyChain( + const VNInfo *VNI) const { + unsigned Reg = this->Reg; + while (!VNI->isPHIDef()) { SlotIndex Def = VNI->def; MachineInstr *MI = Indexes->getInstructionFromIndex(Def); assert(MI && "No defining instruction"); if (!MI->isFullCopy()) - return VNI; + return std::make_pair(VNI, Reg); unsigned SrcReg = MI->getOperand(1).getReg(); if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) - return VNI; + return std::make_pair(VNI, Reg); const LiveInterval &LI = LIS->getInterval(SrcReg); - VNInfo *ValueIn; + const VNInfo *ValueIn; // No subrange involved. - if (LaneMask == 0 || !LI.hasSubRanges()) { + if (!SubRangeJoin || !LI.hasSubRanges()) { LiveQueryResult LRQ = LI.Query(Def); ValueIn = LRQ.valueIn(); } else { // Query subranges. Pick the first matching one. ValueIn = nullptr; for (const LiveInterval::SubRange &S : LI.subranges()) { - if ((S.LaneMask & LaneMask) == 0) + // Transform lanemask to a mask in the joined live interval. + unsigned SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask); + if ((SMask & LaneMask) == 0) continue; LiveQueryResult LRQ = S.Query(Def); ValueIn = LRQ.valueIn(); @@ -1749,22 +1750,26 @@ VNInfo *JoinVals::stripCopies(VNInfo *VNI, unsigned LaneMask, unsigned &Reg) VNI = ValueIn; Reg = SrcReg; } - return VNI; + return std::make_pair(VNI, Reg); } bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1, const JoinVals &Other) const { - unsigned Reg0 = Reg; - VNInfo *Stripped0 = stripCopies(Value0, SubRegMask, Reg0); - unsigned Reg1 = Other.Reg; - VNInfo *Stripped1 = stripCopies(Value1, Other.SubRegMask, Reg1); - if (Stripped0 == Stripped1) + const VNInfo *Orig0; + unsigned Reg0; + std::tie(Orig0, Reg0) = followCopyChain(Value0); + if (Orig0 == Value1) return true; - // Special case: when merging subranges one of the ranges is actually a copy, - // so we can't simply compare VNInfos but have to resort to comparing - // position and register of the Def. - return Stripped0->def == Stripped1->def && Reg0 == Reg1; + const VNInfo *Orig1; + unsigned Reg1; + std::tie(Orig1, Reg1) = Other.followCopyChain(Value1); + + // The values are equal if they are defined at the same place and use the + // same register. Note that we cannot compare VNInfos directly as some of + // them might be from a copy created in mergeSubRangeInto() while the other + // is from the original LiveInterval. + return Orig0->def == Orig1->def && Reg0 == Reg1; } /// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. @@ -2340,14 +2345,14 @@ void JoinVals::eraseInstrs(SmallPtrSetImpl &ErasedInstrs, } } -void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, unsigned LMask, - LiveRange &RRange, unsigned RMask, +void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange, + unsigned LaneMask, const CoalescerPair &CP) { SmallVector NewVNInfo; - JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), - NewVNInfo, CP, LIS, TRI, LMask, true, true); - JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), - NewVNInfo, CP, LIS, TRI, RMask, true, true); + JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask, + NewVNInfo, CP, LIS, TRI, true, true); + JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask, + NewVNInfo, CP, LIS, TRI, true, true); /// Compute NewVNInfo and resolve conflicts (see also joinVirtRegs()) /// Conflicts should already be resolved so the mapping/resolution should @@ -2385,14 +2390,12 @@ void RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, unsigned LMask, void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge, - unsigned DstLaneMask, - unsigned PrevLaneMask, - CoalescerPair &CP) { + unsigned LaneMask, CoalescerPair &CP) { BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); for (LiveInterval::SubRange &R : LI.subranges()) { unsigned RMask = R.LaneMask; // LaneMask of subregisters common to subrange R and ToMerge. - unsigned Common = RMask & DstLaneMask; + unsigned Common = RMask & LaneMask; // There is nothing to do without common subregs. if (Common == 0) continue; @@ -2400,7 +2403,7 @@ void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI, DEBUG(dbgs() << format("\t\tCopy+Merge %04X into %04X\n", RMask, Common)); // LaneMask of subregisters contained in the R range but not in ToMerge, // they have to split into their own subrange. - unsigned LRest = RMask & ~DstLaneMask; + unsigned LRest = RMask & ~LaneMask; LiveInterval::SubRange *CommonRange; if (LRest != 0) { R.LaneMask = LRest; @@ -2413,14 +2416,13 @@ void RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI, CommonRange = &R; } LiveRange RangeCopy(ToMerge, Allocator); - joinSubRegRanges(*CommonRange, CommonRange->LaneMask, RangeCopy, - PrevLaneMask, CP); - DstLaneMask &= ~RMask; + joinSubRegRanges(*CommonRange, RangeCopy, Common, CP); + LaneMask &= ~RMask; } - if (DstLaneMask != 0) { - DEBUG(dbgs() << format("\t\tNew Lane %04X\n", DstLaneMask)); - LI.createSubRangeFrom(Allocator, DstLaneMask, ToMerge); + if (LaneMask != 0) { + DEBUG(dbgs() << format("\t\tNew Lane %04X\n", LaneMask)); + LI.createSubRangeFrom(Allocator, LaneMask, ToMerge); } } @@ -2429,10 +2431,10 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); bool TrackSubRegLiveness = MRI->tracksSubRegLiveness(); - JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI, - 0, false, TrackSubRegLiveness); - JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), NewVNInfo, CP, LIS, TRI, - 0, false, TrackSubRegLiveness); + JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), 0, NewVNInfo, CP, LIS, + TRI, false, TrackSubRegLiveness); + JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), 0, NewVNInfo, CP, LIS, + TRI, false, TrackSubRegLiveness); DEBUG(dbgs() << "\t\tRHS = " << RHS << "\n\t\tLHS = " << LHS @@ -2450,48 +2452,37 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { // All clear, the live ranges can be merged. if (RHS.hasSubRanges() || LHS.hasSubRanges()) { BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); + + // Transform lanemasks from the LHS to masks in the coalesced register and + // create initial subranges if necessary. unsigned DstIdx = CP.getDstIdx(); if (!LHS.hasSubRanges()) { - unsigned Mask = CP.getNewRC()->getLaneMask(); - unsigned DstMask = TRI->composeSubRegIndexLaneMask(DstIdx, Mask); + unsigned Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask() + : TRI->getSubRegIndexLaneMask(DstIdx); // LHS must support subregs or we wouldn't be in this codepath. - assert(DstMask != 0); - LHS.createSubRangeFrom(Allocator, DstMask, LHS); - DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg()) - << ' ' << LHS << '\n'); + assert(Mask != 0); + LHS.createSubRangeFrom(Allocator, Mask, LHS); } else if (DstIdx != 0) { // Transform LHS lanemasks to new register class if necessary. for (LiveInterval::SubRange &R : LHS.subranges()) { - unsigned DstMask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask); - R.LaneMask = DstMask; + unsigned Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask); + R.LaneMask = Mask; } - DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg()) - << ' ' << LHS << '\n'); } + DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg()) + << ' ' << LHS << '\n'); + // Determine lanemasks of RHS in the coalesced register and merge subranges. unsigned SrcIdx = CP.getSrcIdx(); if (!RHS.hasSubRanges()) { - unsigned Mask = SrcIdx != 0 - ? TRI->getSubRegIndexLaneMask(SrcIdx) - : MRI->getMaxLaneMaskForVReg(LHS.reg); - - DEBUG(dbgs() << "\t\tRHS Mask: " - << format("%04X", Mask) << "\n"); - mergeSubRangeInto(LHS, RHS, Mask, 0, CP); + unsigned Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask() + : TRI->getSubRegIndexLaneMask(SrcIdx); + mergeSubRangeInto(LHS, RHS, Mask, CP); } else { // Pair up subranges and merge. for (LiveInterval::SubRange &R : RHS.subranges()) { - unsigned RMask = R.LaneMask; - if (SrcIdx != 0) { - // Transform LaneMask of RHS subranges to the ones on LHS. - RMask = TRI->composeSubRegIndexLaneMask(SrcIdx, RMask); - DEBUG(dbgs() << "\t\tTransform RHS Mask " - << format("%04X", R.LaneMask) << " to subreg " - << TRI->getSubRegIndexName(SrcIdx) - << " => " << format("%04X", RMask) << "\n"); - } - - mergeSubRangeInto(LHS, R, RMask, R.LaneMask, CP); + unsigned Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask); + mergeSubRangeInto(LHS, R, Mask, CP); } } diff --git a/test/CodeGen/R600/subreg-coalescer-crash.ll b/test/CodeGen/R600/subreg-coalescer-crash.ll new file mode 100644 index 00000000000..e841637b504 --- /dev/null +++ b/test/CodeGen/R600/subreg-coalescer-crash.ll @@ -0,0 +1,45 @@ +; RUN: llc -march=r600 -mcpu=SI -verify-machineinstrs -o - %s +; ModuleID = 'bugpoint-reduced-simplified.bc' +target datalayout = "e-p:32:32-p1:64:64-p2:64:64-p3:32:32-p4:64:64-p5:32:32-p24:64:64-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64" +target triple = "r600--" + +; SI: s_endpgm +; Function Attrs: nounwind +define void @row_filter_C1_D0() #0 { +entry: + br i1 undef, label %for.inc.1, label %do.body.preheader + +do.body.preheader: ; preds = %entry + %0 = insertelement <4 x i32> zeroinitializer, i32 undef, i32 1 + br i1 undef, label %do.body56.1, label %do.body90 + +do.body90: ; preds = %do.body56.2, %do.body56.1, %do.body.preheader + %1 = phi <4 x i32> [ %6, %do.body56.2 ], [ %5, %do.body56.1 ], [ %0, %do.body.preheader ] + %2 = insertelement <4 x i32> %1, i32 undef, i32 2 + %3 = insertelement <4 x i32> %2, i32 undef, i32 3 + br i1 undef, label %do.body124.1, label %do.body.1562.preheader + +do.body.1562.preheader: ; preds = %do.body124.1, %do.body90 + %storemerge = phi <4 x i32> [ %3, %do.body90 ], [ %7, %do.body124.1 ] + %4 = insertelement <4 x i32> undef, i32 undef, i32 1 + br label %for.inc.1 + +do.body56.1: ; preds = %do.body.preheader + %5 = insertelement <4 x i32> %0, i32 undef, i32 1 + %or.cond472.1 = or i1 undef, undef + br i1 %or.cond472.1, label %do.body56.2, label %do.body90 + +do.body56.2: ; preds = %do.body56.1 + %6 = insertelement <4 x i32> %5, i32 undef, i32 1 + br label %do.body90 + +do.body124.1: ; preds = %do.body90 + %7 = insertelement <4 x i32> %3, i32 undef, i32 3 + br label %do.body.1562.preheader + +for.inc.1: ; preds = %do.body.1562.preheader, %entry + %storemerge591 = phi <4 x i32> [ zeroinitializer, %entry ], [ %storemerge, %do.body.1562.preheader ] + %add.i495 = add <4 x i32> %storemerge591, undef + unreachable +} + -- 2.11.0