Index: llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -700,14 +700,19 @@ class BDVState { public: enum StatusTy { - // Starting state of lattice - Unknown, - // Some specific base value -- does *not* mean that instruction - // propagates the base of the object - // ex: gep %arg, 16 -> %arg is the base value - Base, - // Need to insert a node to represent a merge. - Conflict + // Starting state of lattice + Unknown, + // The original value is the base itself. + Base, + // Some specific base value -- does *not* mean that instruction + // propagates the base of the object + // ex: gep %arg, 16 -> %arg is the base value + Derived, + // Merging not-derived values with different bases. + DifferentBases, + // Merging values with different bases and at least one of the values is + // derived. Need to insert a node to represent a merge. + Conflict }; BDVState() { @@ -716,8 +721,9 @@ explicit BDVState(Value *OriginalValue) : OriginalValue(OriginalValue) {} - explicit BDVState(Value *OriginalValue, StatusTy Status, Value *BaseValue = nullptr) - : OriginalValue(OriginalValue), Status(Status), BaseValue(BaseValue) { + explicit BDVState(Value *OriginalValue, StatusTy Status, + Value *BaseValue = nullptr) + : OriginalValue(OriginalValue), Status(Status), BaseValue(BaseValue) { assert(Status != Base || BaseValue); } @@ -727,6 +733,9 @@ bool isBase() const { return getStatus() == Base; } bool isUnknown() const { return getStatus() == Unknown; } + bool isDerived() const { return getStatus() == Derived; } + bool isBaseOrDerived() const { return isBase() || isDerived(); } + bool isDifferentBases() const { return getStatus() == DifferentBases; } bool isConflict() const { return getStatus() == Conflict; } // Values of type BDVState form a lattice, and this function implements the @@ -746,25 +755,35 @@ BaseValue = Other.getBaseValue(); return; } - // We are base. - assert(isBase() && "Unknown state"); + + assert((isBase() || isDerived() || isDifferentBases()) && "Unknown state"); // If other is unknown - just keep our state. if (Other.isUnknown()) return; // If other is conflict - it is a final state. if (Other.isConflict()) return markConflict(); - // Other is base as well. - assert(Other.isBase() && "Unknown state"); - // If bases are different - Conflict. - if (getBaseValue() != Other.getBaseValue()) + // If merging two bases or derived values with the same base pointers then + // keep our state or update to derived if merging with a derived value. + if (isBaseOrDerived() && Other.isBaseOrDerived() && + getBaseValue() == Other.getBaseValue()) { + if (Other.isDerived()) + Status = BDVState::Derived; + return; + } + // If merging two values that are not bases themselves, then we are in a + // conflict state. + if (isDerived() || Other.isDerived()) return markConflict(); - // We are identical, do nothing. + assert((Other.isBase() || Other.isDifferentBases()) && "Unknown state"); + // Otherwise we are merging two or more base values. + Status = BDVState::DifferentBases; + BaseValue = nullptr; } bool operator==(const BDVState &Other) const { - return OriginalValue == Other.OriginalValue && BaseValue == Other.BaseValue && - Status == Other.Status; + return OriginalValue == Other.OriginalValue && + BaseValue == Other.BaseValue && Status == Other.Status; } bool operator!=(const BDVState &other) const { return !(*this == other); } @@ -783,6 +802,12 @@ case Base: OS << "B"; break; + case Derived: + OS << "D"; + break; + case DifferentBases: + OS << "DB"; + break; case Conflict: OS << "C"; break; @@ -795,7 +820,8 @@ private: AssertingVH OriginalValue; // instruction this state corresponds to StatusTy Status = Unknown; - AssertingVH BaseValue = nullptr; // Non-null only if Status == Base. + AssertingVH BaseValue = + nullptr; // Non-null only if Status == Base or Derived. }; } // end anonymous namespace @@ -827,7 +853,9 @@ // b1 b2 b3 b4 // CONFLICT // When algorithm terminates, all PHIs will either have a single concrete - // base or be in a conflict state. + // base, have different incoming bases or be in a conflict state if it has + // different bases for its incoming values and at least one of them is + // derived. // - For every conflict, insert a dummy PHI node without arguments. Add // these to the base[Instruction] = BasePtr mapping. For every // non-conflict, add the actual base. @@ -971,7 +999,10 @@ if (I != States.end()) return I->second; assert(areBothVectorOrScalar(BaseValue, Input)); - return BDVState(BaseValue, BDVState::Base, BaseValue); + BDVState::StatusTy Status = BDVState::Base; + if (Input->stripPointerCasts() != BaseValue) + Status = BDVState::Derived; + return BDVState(BaseValue, Status, BaseValue); }; bool Progress = true; @@ -1004,6 +1035,8 @@ if (OldState != NewState) { Progress = true; States[BDV] = NewState; + LLVM_DEBUG(dbgs() << "New state " << NewState << " for " << *BDV + << "\n"); } } @@ -1032,7 +1065,7 @@ "why did it get added?"); assert(!State.isUnknown() && "Optimistic algorithm didn't complete!"); - if (!State.isBase() || !isa(BaseValue->getType())) + if (!State.isBaseOrDerived() || !isa(BaseValue->getType())) continue; // extractelement instructions are a bit special in that we may need to // insert an extract even when we know an exact base for the instruction. @@ -1117,14 +1150,14 @@ // pointer. auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) { Value *BDV = findBaseOrBDV(Input, Cache); - Value *Base = nullptr; - if (!States.count(BDV)) { + Value *Base = BDV; + if (!States.count(BDV)) assert(areBothVectorOrScalar(BDV, Input)); - Base = BDV; - } else { - // Either conflict or base. + else { assert(States.count(BDV)); - Base = States[BDV].getBaseValue(); + auto &State = States[BDV]; + if (State.isBaseOrDerived() || State.isConflict()) + Base = State.getBaseValue(); } assert(Base && "Can't be null"); // The cast is needed since base traversal may strip away bitcasts @@ -1240,7 +1273,11 @@ // relation and one of the base pointer relation! FIXME for (auto Pair : States) { auto *BDV = Pair.first; - Value *Base = Pair.second.getBaseValue(); + auto &State = Pair.second; + Value *Base = State.getBaseValue(); + // If the state is merging different bases, then its value is base itself. + if (State.isDifferentBases()) + Base = State.getOriginalValue(); assert(BDV && Base); // Only values that do not have known bases or those that have differing // type (scalar versus vector) from a possible known base should be in the @@ -2276,12 +2313,13 @@ continue; // PHI nodes that have the same incoming values, and belonging to the same // basic blocks are essentially the same SSA value. When the original phi - // has incoming values with different base pointers, the original phi is - // marked as conflict, and an additional `AlternateRootPhi` with the same - // incoming values get generated by the findBasePointer function. We need - // to identify the newly generated AlternateRootPhi (.base version of phi) - // and RootOfChain (the original phi node itself) are the same, so that we - // can rematerialize the gep and casts. This is a workaround for the + // has incoming values with different base pointers and at least one of + // them is derived, the original phi is marked as conflict, and an + // additional `AlternateRootPhi` with the same incoming values get + // generated by the findBasePointer function. We need to identify the + // newly generated AlternateRootPhi (.base version of phi) and RootOfChain + // (the original phi node itself) are the same, so that we can + // rematerialize the gep and casts. This is a workaround for the // deficiency in the findBasePointer algorithm. if (!AreEquivalentPhiNodes(*OrigRootPhi, *AlternateRootPhi)) continue; Index: llvm/test/Transforms/RewriteStatepointsForGC/base-pointers-14.ll =================================================================== --- llvm/test/Transforms/RewriteStatepointsForGC/base-pointers-14.ll +++ llvm/test/Transforms/RewriteStatepointsForGC/base-pointers-14.ll @@ -6,8 +6,6 @@ declare void @foo() gc "statepoint-example" -; FIXME: In this test case %b6.base, which is inserted by RS4GC, is identical -; to %b6. define i8 addrspace(1)* @test1(i1 %c, i8 addrspace(1)* %b1, i8 addrspace(1)* %b2) gc "statepoint-example" { ; CHECK-LABEL: @test1( ; CHECK-NEXT: left: @@ -71,22 +69,17 @@ ret i8 addrspace(1)* %b6 } -; FIXME: In this test case %b5.base and %b6.base (inserted by RS4GC) are -; identical to %b5 and %b6 ; correspondingly. define i8 addrspace(1)* @test3(i1 %c, i8 addrspace(1)* %b1, i8 addrspace(1)* %b2) gc "statepoint-example" { ; CHECK-LABEL: @test3( ; CHECK-NEXT: left: ; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP:%.*]], label [[MERGE2:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[B5_BASE:%.*]] = phi i8 addrspace(1)* [ [[B2:%.*]], [[LEFT:%.*]] ], [ [[B5_BASE]], [[LOOP]] ], [ [[B6_BASE_RELOCATED:%.*]], [[MERGE2]] ], !is_base_value !0 -; CHECK-NEXT: [[B5:%.*]] = phi i8 addrspace(1)* [ [[B2]], [[LEFT]] ], [ [[B5]], [[LOOP]] ], [ [[B6_RELOCATED:%.*]], [[MERGE2]] ] +; CHECK-NEXT: [[B5:%.*]] = phi i8 addrspace(1)* [ [[B2:%.*]], [[LEFT:%.*]] ], [ [[B5]], [[LOOP]] ], [ [[B6_RELOCATED:%.*]], [[MERGE2]] ] ; CHECK-NEXT: br i1 [[C]], label [[LOOP]], label [[MERGE2]] ; CHECK: merge2: -; CHECK-NEXT: [[B6_BASE:%.*]] = phi i8 addrspace(1)* [ [[B1:%.*]], [[LEFT]] ], [ [[B5_BASE]], [[LOOP]] ], !is_base_value !0 -; CHECK-NEXT: [[B6:%.*]] = phi i8 addrspace(1)* [ [[B1]], [[LEFT]] ], [ [[B5]], [[LOOP]] ] -; CHECK-NEXT: [[STATEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* elementtype(void ()) @foo, i32 0, i32 0, i32 0, i32 0) [ "deopt"(), "gc-live"(i8 addrspace(1)* [[B6_BASE]], i8 addrspace(1)* [[B6]]) ] -; CHECK-NEXT: [[B6_BASE_RELOCATED]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 0, i32 0) -; CHECK-NEXT: [[B6_RELOCATED]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 0, i32 1) +; CHECK-NEXT: [[B6:%.*]] = phi i8 addrspace(1)* [ [[B1:%.*]], [[LEFT]] ], [ [[B5]], [[LOOP]] ] +; CHECK-NEXT: [[STATEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* elementtype(void ()) @foo, i32 0, i32 0, i32 0, i32 0) [ "deopt"(), "gc-live"(i8 addrspace(1)* [[B6]]) ] +; CHECK-NEXT: [[B6_RELOCATED]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 0, i32 0) ; CHECK-NEXT: br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]] ; CHECK: exit: ; CHECK-NEXT: ret i8 addrspace(1)* [[B6_RELOCATED]]