Index: lib/CodeGen/RegisterCoalescer.cpp =================================================================== --- lib/CodeGen/RegisterCoalescer.cpp +++ lib/CodeGen/RegisterCoalescer.cpp @@ -1396,11 +1396,29 @@ } else if (SrcLI.liveAt(Idx)) return false; - LLVM_DEBUG(dbgs() << "\tEliminating copy of value\n"); - - // Remove any DstReg segments starting at the instruction. + // If the undef copy defines a live-out value (i.e. an input to a PHI def), + // then replace it with an IMPLICIT_DEF. LiveInterval &DstLI = LIS->getInterval(DstReg); SlotIndex RegIndex = Idx.getRegSlot(); + LiveRange::Segment *Seg = DstLI.getSegmentContaining(RegIndex); + assert(Seg != nullptr && "No segment for defining instruction"); + if (VNInfo *V = DstLI.getVNInfoAt(Seg->end)) { + if (V->isPHIDef()) { + CopyMI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); + for (unsigned i = CopyMI->getNumOperands(); i != 0; --i) { + MachineOperand &MO = CopyMI->getOperand(i-1); + if (MO.isReg() && MO.isUse()) + CopyMI->RemoveOperand(i-1); + } + LLVM_DEBUG(dbgs() << "\tReplaced copy of value with an " + "implicit def\n"); + return false; + } + } + + // Remove any DstReg segments starting at the instruction. + LLVM_DEBUG(dbgs() << "\tEliminating copy of value\n"); + // Remove value or merge with previous one in case of a subregister def. if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) { VNInfo *VNI = DstLI.getVNInfoAt(RegIndex); @@ -1626,6 +1644,10 @@ deleteInstr(CopyMI); return false; // Not coalescable. } + if (CopyMI->isImplicitDef()) { + // Not coalesceable; eliminateUndefCopy turned it into implicit_def. + return false; + } // Coalesced copies are normally removed immediately, but transformations // like removeCopyByCommutingDef() can inadvertently create identity copies. @@ -2078,6 +2100,13 @@ /// True once Pruned above has been computed. bool PrunedComputed = false; + /// True if this value is determined to be identical to OtherVNI + /// (in valuesIdentical). This is used with CR_Erase where the erased + /// copy is redundant, i.e. the source value is already the same as + /// the destination. In such cases the subranges need to be updated + /// properly. See comment at pruneSubRegValues for more info. + bool Identical = false; + Val() = default; bool isAnalyzed() const { return WriteLanes.any(); } @@ -2256,7 +2285,7 @@ const VNInfo *Orig0; unsigned Reg0; std::tie(Orig0, Reg0) = followCopyChain(Value0); - if (Orig0 == Value1) + if (Orig0 == Value1 && Reg0 == Other.Reg) return true; const VNInfo *Orig1; @@ -2438,8 +2467,10 @@ // %this = COPY %ext <-- Erase this copy // if (DefMI->isFullCopy() && !CP.isPartial() - && valuesIdentical(VNI, V.OtherVNI, Other)) + && valuesIdentical(VNI, V.OtherVNI, Other)) { + V.Identical = true; return CR_Erase; + } // If the lanes written by this instruction were all undef in OtherVNI, it is // still safe to join the live ranges. This can't be done with a simple value @@ -2743,23 +2774,78 @@ } } +/// Consider the following situation when coalescing the copy between +/// %31 and %45 at 800. (The vertical lines represent live range segments.) +/// +/// Main range Subrange 0004 (sub2) +/// %31 %45 %31 %45 +/// 544 %45 = COPY %28 + + +/// | v1 | v1 +/// 560B bb.1: + + +/// 624 = %45.sub2 | v2 | v2 +/// 800 %31 = COPY %45 + + + + +/// | v0 | v0 +/// 816 %31.sub1 = ... + | +/// 880 %30 = COPY %31 | v1 + +/// 928 %45 = COPY %30 | + + +/// | | v0 | v0 <--+ +/// 992B ; backedge -> bb.1 | + + | +/// 1040 = %31.sub0 + | +/// This value must remain +/// live-out! +/// +/// Assuming that %31 is coalesced into %45, the copy at 928 becomes +/// redundant, since it copies the value from %45 back into it. The +/// conflict resolution for the main range determines that %45.v0 is +/// to be erased, which is ok since %31.v1 is identical to it. +/// The problem happens with the subrange for sub2: it has to be live +/// on exit from the block, but since 928 was actually a point of +/// definition of %45.sub2, %45.sub2 was not live immediately prior +/// to that definition. As a result, when 928 was erased, the value v0 +/// for %45.sub2 was pruned in pruneSubRegValues. Consequently, an +/// IMPLICIT_DEF was inserted as a "backedge" definition for %45.sub2, +/// providing an incorrect value to the use at 624. +/// +/// Since the main-range values %31.v1 and %45.v0 were proved to be +/// identical, the corresponding values in subranges must also be the +/// same. A redundant copy is removed because it's not needed, and not +/// because it copied an undefined value, so any liveness that originated +/// from that copy cannot disappear. When pruning a value that started +/// at the removed copy, the corresponding identical value must be +/// extended to replace it. +/// +/// There are cases where there is another value "in the way" that is also being +/// pruned here. To avoid that causing liveness to be extended incorrectly, we +/// do all the pruning first and then the extensions afterwards. +// void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) { - // Look for values being erased. bool DidPrune = false; - for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { - // We should trigger in all cases in which eraseInstrs() does something. - // match what eraseInstrs() is doing, print a message so - if (Vals[i].Resolution != CR_Erase && - (Vals[i].Resolution != CR_Keep || !Vals[i].ErasableImplicitDef || - !Vals[i].Pruned)) - continue; + // For each subrange in turn... + for (LiveInterval::SubRange &S : LI.subranges()) { + // Remember end points from pruned values that need liveness extending to + // them. + SmallVector EndPoints; + // Also remember pruned defs that required extension, so we can assert that + // liveness was extended as we expected. + SmallVector, 8> PrunedDefs; + + // Look for values being erased. + for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { + Val &V = Vals[i]; + // We should trigger in all cases in which eraseInstrs() does something. + if (V.Resolution != CR_Erase && + (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned)) + continue; + + // Check this subrange at the point where the copy will be removed. + SlotIndex Def = LR.getValNumInfo(i)->def; + SlotIndex OtherDef; + if (V.Identical) + OtherDef = V.OtherVNI->def; + + // Print message so mismatches with eraseInstrs() can be diagnosed. + LLVM_DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def << '\n'); - // Check subranges at the point where the copy will be removed. - SlotIndex Def = LR.getValNumInfo(i)->def; - // Print message so mismatches with eraseInstrs() can be diagnosed. - LLVM_DEBUG(dbgs() << "\t\tExpecting instruction removal at " << Def - << '\n'); - for (LiveInterval::SubRange &S : LI.subranges()) { LiveQueryResult Q = S.Query(Def); // If a subrange starts at the copy then an undefined value has been @@ -2768,7 +2854,17 @@ if (ValueOut != nullptr && Q.valueIn() == nullptr) { LLVM_DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask) << " at " << Def << "\n"); - LIS->pruneValue(S, Def, nullptr); + if (V.Identical && S.Query(OtherDef).valueOut()) { + // If V is identical to V.OtherVNI (and S was live at OtherDef), + // then we can't simply prune V from S. V needs to be replaced + // with V.OtherVNI. Remember the end points for later extension. + LLVM_DEBUG(dbgs() << "\t\t (will extend to end points)\n"); + auto SizeBefore = EndPoints.size(); + LIS->pruneValue(S, Def, &EndPoints); + if (SizeBefore != EndPoints.size()) + PrunedDefs.push_back(std::pair(Def, OtherDef)); + } else + LIS->pruneValue(S, Def, nullptr); DidPrune = true; // Mark value number as unused. ValueOut->markUnused(); @@ -2783,6 +2879,26 @@ ShrinkMask |= S.LaneMask; } } + // Now re-extend liveness to end points. + if (!EndPoints.empty()) { + LLVM_DEBUG(dbgs() << "\t\tExtending to EndPoints:"; + for (auto &EP : EndPoints) + dbgs() << " " << EP; + dbgs() << "\n"); + LIS->extendToIndices(S, EndPoints); + LLVM_DEBUG(dbgs() << "\t\t after extendToIndices: " << S << "\n"); +#ifndef NDEBUG + // Assert that liveness has been extended as expected. + for (auto DefPair : PrunedDefs) { + SlotIndex Def = DefPair.first; + SlotIndex OtherDef = DefPair.second; + // Make sure that the value at Def is really V.OtherVNI. + LiveRange::iterator Id = S.find(OtherDef); + LiveRange::iterator T = S.find(Def); + assert(Id != S.end() && T != S.end() && T->valno == Id->valno); + } +#endif + } } if (DidPrune) LI.removeEmptySubRanges(); Index: test/CodeGen/AMDGPU/coalescer-extend-pruned-subrange.mir =================================================================== --- /dev/null +++ test/CodeGen/AMDGPU/coalescer-extend-pruned-subrange.mir @@ -0,0 +1,128 @@ +# RUN: llc -mtriple=amdgcn--amdpal -mcpu=gfx803 -run-pass=simple-register-coalescing -o - %s | FileCheck -check-prefix=GCN %s + +# GCN: {{^body}} + +--- +name: foo +tracksRegLiveness: true +body: | + bb.0: + successors: %bb.2 + + %0:sreg_32_xm0 = S_MOV_B32 1 + %1:vgpr_32 = COPY %0 + INLINEASM &"; %1", 1, 327690, def %1, 2147483657, %1(tied-def 3) + %2:sreg_64 = V_CMP_NE_U32_e64 0, %1, implicit $exec + undef %3.sub0:sreg_128 = COPY %0 + %3.sub1:sreg_128 = COPY %0 + %3.sub2:sreg_128 = COPY %0 + %4:sreg_128 = COPY %3 + %5:vgpr_32 = V_MOV_B32_e32 -64, implicit $exec + %6:vreg_128 = COPY %4 + %7:sreg_32_xm0 = S_AND_B32 target-flags(amdgpu-gotprel) 1, %2.sub0, implicit-def dead $scc + %8:sreg_32_xm0 = S_MOV_B32 0 + %9:vgpr_32 = COPY %5 + %10:vreg_128 = COPY %6 + S_BRANCH %bb.2 + + bb.1: + %11:vgpr_32 = V_OR_B32_e32 %12.sub0, %12.sub1, implicit $exec + %13:vgpr_32 = V_OR_B32_e32 %11, %12.sub2, implicit $exec + %14:vgpr_32 = V_AND_B32_e32 1, %13, implicit $exec + %15:sreg_64_xexec = V_CMP_EQ_U32_e64 0, %14, implicit $exec + %16:vgpr_32 = V_CNDMASK_B32_e64 0, 1, %15, implicit $exec + BUFFER_STORE_DWORD_OFFEN_exact %16, undef %17:vgpr_32, undef %18:sreg_128, 0, 0, 0, 0, 0, implicit $exec :: (dereferenceable store 4 into constant-pool, align 1, addrspace 4) + S_ENDPGM + + bb.2: + successors: %bb.3, %bb.4 + + %19:sreg_64 = V_CMP_EQ_U32_e64 1, %7, implicit $exec + %20:sreg_64 = COPY $exec, implicit-def $exec + %21:sreg_64 = S_AND_B64 %20, %19, implicit-def dead $scc + $exec = S_MOV_B64_term %21 + SI_MASK_BRANCH %bb.4, implicit $exec + S_BRANCH %bb.3 + + bb.3: + successors: %bb.4 + + undef %22.sub0:sreg_128 = COPY %8 + %22.sub1:sreg_128 = COPY %8 + %22.sub2:sreg_128 = COPY %8 + %23:sreg_128 = COPY %22 + %24:vreg_128 = COPY %23 + %10:vreg_128 = COPY %24 + + bb.4: + successors: %bb.5 + + $exec = S_OR_B64 $exec, %20, implicit-def $scc + + bb.5: + successors: %bb.7, %bb.6 + + S_CBRANCH_SCC0 %bb.7, implicit undef $scc + + bb.6: + successors: %bb.9 + + %12:vreg_128 = COPY %10 + S_BRANCH %bb.9 + + bb.7: + successors: %bb.8, %bb.10 + + %25:vgpr_32 = V_AND_B32_e32 target-flags(amdgpu-gotprel32-hi) 1, %10.sub2, implicit $exec + %26:sreg_64 = V_CMP_EQ_U32_e64 1, %25, implicit $exec + %27:vgpr_32 = V_MOV_B32_e32 0, implicit $exec + %28:vreg_1 = COPY %27 + %29:sreg_64 = COPY $exec, implicit-def $exec + %30:sreg_64 = S_AND_B64 %29, %26, implicit-def dead $scc + $exec = S_MOV_B64_term %30 + SI_MASK_BRANCH %bb.10, implicit $exec + S_BRANCH %bb.8 + + bb.8: + successors: %bb.10 + + %31:vgpr_32 = BUFFER_LOAD_DWORD_OFFEN undef %32:vgpr_32, undef %33:sreg_128, 0, 0, 0, 0, 0, implicit $exec :: (dereferenceable load 4 from constant-pool, align 1, addrspace 4) + %34:sreg_64_xexec = V_CMP_NE_U32_e64 0, %31, implicit $exec + %35:vgpr_32 = V_CNDMASK_B32_e64 0, -1, %34, implicit $exec + %28:vreg_1 = COPY %35 + S_BRANCH %bb.10 + + bb.9: + successors: %bb.11 + + S_BRANCH %bb.11 + + bb.10: + successors: %bb.9 + + $exec = S_OR_B64 $exec, %29, implicit-def $scc + %36:vreg_1 = COPY %28 + %37:sreg_64_xexec = V_CMP_NE_U32_e64 0, %36, implicit $exec + %38:vgpr_32 = V_CNDMASK_B32_e64 0, 1, %37, implicit $exec + %39:vgpr_32 = V_MOV_B32_e32 0, implicit $exec + undef %40.sub0:vreg_128 = COPY %39 + %40.sub1:vreg_128 = COPY %39 + %40.sub2:vreg_128 = COPY %38 + %41:vreg_128 = COPY %40 + %12:vreg_128 = COPY %41 + S_BRANCH %bb.9 + + bb.11: + successors: %bb.2, %bb.1 + + %42:vgpr_32 = V_ADD_I32_e32 32, %9, implicit-def dead $vcc, implicit $exec + V_CMP_EQ_U32_e32 0, %42, implicit-def $vcc, implicit $exec + %43:vgpr_32 = COPY %42 + $vcc = S_AND_B64 $exec, killed $vcc, implicit-def dead $scc + %44:vreg_128 = COPY %12 + %9:vgpr_32 = COPY %43 + %10:vreg_128 = COPY %44 + S_CBRANCH_VCCNZ %bb.1, implicit killed $vcc + S_BRANCH %bb.2 + +... Index: test/CodeGen/AMDGPU/coalescing-subranges-another-copymi-not-live.mir =================================================================== --- /dev/null +++ test/CodeGen/AMDGPU/coalescing-subranges-another-copymi-not-live.mir @@ -0,0 +1,613 @@ +# RUN: llc -mtriple=amdgcn--amdpal -mcpu=gfx803 -run-pass=simple-register-coalescing -o - %s | FileCheck -check-prefix=GCN %s + +# With one version of the D48102 fix, this test failed with +# Assertion failed: (ValNo && "CopyMI input register not live"), function reMaterializeTrivialDef, file ../lib/CodeGen/RegisterCoalescer.cpp, line 1107. + +# GCN: {{^body}} + +--- | + ; ModuleID = 'bugpoint-reduced-simplified.bc' + target datalayout = "e-p:64:64-p1:64:64-p2:32:32-p3:32:32-p4:64:64-p5:32:32-p6:32:32-i64:64-v16:16-v24:32-v32:32-v48:64-v96:128-v192:256-v256:256-v512:512-v1024:1024-v2048:2048-n32:64-S32-A5" + target triple = "amdgcn--amdpal" + + ; Function Attrs: nounwind readnone speculatable + declare float @llvm.minnum.f32(float, float) #0 + + ; Function Attrs: nounwind + define dllexport amdgpu_cs void @_amdgpu_cs_main(<3 x i32>) local_unnamed_addr #1 !spirv.ExecutionModel !1 { + .entry: + br i1 undef, label %4, label %1, !amdgpu.uniform !2, !structurizecfg.uniform !2 + + ;