[RS4GC] Don't clone BDV if its inputs are not derived

[dmakogon]

Summary

This patch performs check if all the inputs of the BDV are base values themselves (i.e. not derived from some base)
If it's true for some BDV, we can avoid cloning it, because the clone would be identical to BDV (it may have different incoming values, because those may be cloned too).

[mkazantsev]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

725

What worries me is that we never check the consistency of state of IsDerived and BaseValue. There should be some invariant like "if BaseValue is defined and not equal to OriginalValue then IsDerived should be true", or whatsoever. Do you want to add some sanity checks to make sure these states are not self-contradictory?

Ideally I'd completely give up a separate boolean flag for IsDerived and answer the method through other fields, but not sure if it's possible.

1055

1. If I'm reading this code correctly, ToRemove should already be empty and you can assert that instead.
2. I don't feel comfortable using the same ToRemove vector for 2 different unrelated activities. Limit scope or declare a new one?

1056

Would that work here?

remove_if(States, [](It) { return !It.second.isDerived() ;}

?

1089

Please name the boolean parameter /* IsDerived*/ true

[skatkov]

I'm also looking into this. The idea is clear but I worry this adds a complexity with decoding the state.
I'm looking into the way to make it more straightforward. Probably it will require some re-factoring.

[dmakogon]

Added new enum values instead of the isDerived flag.

[skatkov]

Please go through all comments in findBasePointer and verify that they are up to date with you changes...

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

749

This is redundant, just use in place.

766–776

Add a comment.

[dmakogon]

Add more comments, update present ones.
Also there was a crash in lambda getBaseForInput. It relied on the old enum values. Fixed it.

[reames]

You're extending the algorithm in two ways at once. First, you're tracking whether a value which has a single base is itself that base pointer. Second, you're tracking whether a meet of two values is definitely a base pointer.

I see why the former is needed for the later, but can you get any benefit from only the former? If you can, separating that into it's own patch with tests would help reduce complexity. I think at a minimum you can use the former on its on to strengthen some asserts.

Another way to handle it would be to separate the "IsKnownBase" bit out of the lattice enum states, and track it separately. If you do that, please rename the lattice elements to reflect that they're tracking the number of contributing bases (e.g. unknown, onebase, manybases). We have some precedent for that in the BaseDefiningValueResult structure, so that somewhat makes sense.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

710

Naming wise, let me suggest "IsBase" and "HasSingleBase" for the states you're currently calling "Base", and "Derived".

Why?

1. This avoids the state name reuse which a) forces compile errors, and b) makes any missed comments much less confusing.

2. Derived seems to imply the pointer must be derived, when in practice, I believe you mean that it may be derived.

[dmakogon]

Removed unnecessary comment in test case

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

 namespace {
 
 /// Models the state of a single base defining value in the findBasePointer
 /// algorithm for determining where a new instruction is needed to propagate
 /// the base of this BDV.
 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
+    // The original value is the base itself.
+    Base,
+    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.
   };
 
   BDVState() {
     llvm_unreachable("missing state in map");
   }
 
   explicit BDVState(Value *OriginalValue)
     : OriginalValue(OriginalValue) {}
-  explicit BDVState(Value *OriginalValue, StatusTy Status, Value *BaseValue = nullptr)
+  explicit BDVState(Value *OriginalValue, StatusTy Status,
+                    Value *BaseValue = nullptr)
       : OriginalValue(OriginalValue), Status(Status), BaseValue(BaseValue) {
     assert(Status != Base || BaseValue);
   }
 
   StatusTy getStatus() const { return Status; }
   Value *getOriginalValue() const { return OriginalValue; }
   Value *getBaseValue() const { return BaseValue; }
 
   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
   // meet
   // operation.
   void meet(const BDVState &Other) {
     auto markConflict = [&]() {
       Status = BDVState::Conflict;
       BaseValue = nullptr;
     };
     // Conflict is a final state.
     if (isConflict())
       return;
     // if we are not known - just take other state.
     if (isUnknown()) {
       Status = Other.getStatus();
       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); }
 
   LLVM_DUMP_METHOD
   void dump() const {
     print(dbgs());
     dbgs() << '\n';
   }
 
   void print(raw_ostream &OS) const {
     switch (getStatus()) {
     case Unknown:
       OS << "U";
       break;
     case Base:
       OS << "B";
       break;
+    case Derived:
+      OS << "D";
+      break;
+    case DifferentBases:
+      OS << "DB";
+      break;
     case Conflict:
       OS << "C";
       break;
     }
     OS << " (base " << getBaseValue() << " - "
        << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << ")"
        << " for  "  << OriginalValue->getName() << ":";
   }
 
 private:
   AssertingVH<Value> OriginalValue; // instruction this state corresponds to
   StatusTy Status = Unknown;
-  AssertingVH<Value> BaseValue = nullptr; // Non-null only if Status == Base.
+  AssertingVH<Value> BaseValue =
+      nullptr; // Non-null only if Status == Base or Derived.
 };
 
 } // end anonymous namespace
 
 #ifndef NDEBUG
 static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) {
   State.print(OS);
   return OS;
static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache) {
   //   pointer or a PHI which obscures the base pointer.
   // - Construct a mapping from PHI to unknown TOP state.  Use an
   //   optimistic algorithm to propagate base pointer information.  Lattice
   //   looks like:
   //   UNKNOWN
   //   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.
   //  - For every conflict, add arguments for the base[a] of each input
   //   arguments.
   //
   // Note: A simpler form of this would be to add the conflict form of all
   // PHIs without running the optimistic algorithm.  This would be
#endif
 
   // Return a phi state for a base defining value.  We'll generate a new
   // base state for known bases and expect to find a cached state otherwise.
   auto GetStateForBDV = [&](Value *BaseValue, Value *Input) {
     auto I = States.find(BaseValue);
     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;
   while (Progress) {
 #ifndef NDEBUG
     const size_t OldSize = States.size();
 #endif
     Progress = false;
for (auto Pair : States) {
         auto OpState = GetStateForBDV(BDV, Op);
         NewState.meet(OpState);
       });
 
       BDVState OldState = States[BDV];
       if (OldState != NewState) {
         Progress = true;
         States[BDV] = NewState;
+        LLVM_DEBUG(dbgs() << "New state " << NewState << " for " << *BDV
+                          << "\n");
       }
     }
 
     assert(OldSize == States.size() &&
            "fixed point shouldn't be adding any new nodes to state");
   }
 
 #ifndef NDEBUG
   VerifyStates();
   LLVM_DEBUG(dbgs() << "States after meet iteration:\n");
   for (const auto &Pair : States) {
     LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
   }
 #endif
 
   // Handle all instructions that have a vector BDV, but the instruction itself
   // is of scalar type.
   for (auto Pair : States) {
     Instruction *I = cast<Instruction>(Pair.first);
     BDVState State = Pair.second;
     auto *BaseValue = State.getBaseValue();
     // 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
     // lattice.
     assert((!isKnownBaseResult(I) || !areBothVectorOrScalar(I, BaseValue)) &&
            "why did it get added?");
     assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
 
-    if (!State.isBase() || !isa<VectorType>(BaseValue->getType()))
+    if (!State.isBaseOrDerived() || !isa<VectorType>(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.
     // The problem is that we need to convert from a vector base to a scalar
     // base for the particular indice we're interested in.
     if (isa<ExtractElementInst>(I)) {
       auto *EE = cast<ExtractElementInst>(I);
       // TODO: In many cases, the new instruction is just EE itself.  We should
       // exploit this, but can't do it here since it would break the invariant
       // about the BDV not being known to be a base.
       auto *BaseInst = ExtractElementInst::Create(
           State.getBaseValue(), EE->getIndexOperand(), "base_ee", EE);
       BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
       States[I] = BDVState(I, BDVState::Base, BaseInst);
     } else if (!isa<VectorType>(I->getType())) {
       // We need to handle cases that have a vector base but the instruction is
       // a scalar type (these could be phis or selects or any instruction that
       // are of scalar type, but the base can be a vector type).  We
       // conservatively set this as conflict.  Setting the base value for these
       // conflicts is handled in the next loop which traverses States.
       States[I] = BDVState(I, BDVState::Conflict);
     }
   }
 
 #ifndef NDEBUG
   VerifyStates();
 #endif
 
   // Insert Phis for all conflicts
#endif
   // seen in the inference algorithm above.  As such, we must either already
   // know it's base defining value is a base, or have inserted a new
   // instruction to propagate the base of it's BDV and have entered that newly
   // introduced instruction into the state table.  In either case, we are
   // assured to be able to determine an instruction which produces it's base
   // 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
     if (Base->getType() != Input->getType() && InsertPt)
       Base = new BitCastInst(Base, Input->getType(), "cast", InsertPt);
     return Base;
   };
 
#ifndef NDEBUG
   VerifyStates();
 #endif
 
   // Cache all of our results so we can cheaply reuse them
   // NOTE: This is actually two caches: one of the base defining value
   // 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
     // lattice.
     assert((!isKnownBaseResult(BDV) || !areBothVectorOrScalar(BDV, Base)) &&
            "why did it get added?");
 
     LLVM_DEBUG(
for (auto P2B : PointerToBase) {
     // Base Value, but they are essentially the same phi values.
     if (RootOfChain != PointerToBase[Derived]) {
       PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
       PHINode *AlternateRootPhi = dyn_cast<PHINode>(PointerToBase[Derived]);
       if (!OrigRootPhi || !AlternateRootPhi)
         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;
     }
     // Compute cost of this chain.
     InstructionCost Cost = chainToBasePointerCost(ChainToBase, TTI);
     // TODO: We can also account for cases when we will be able to remove some
     //       of the rematerialized values by later optimization passes. I.e if

llvm/test/Transforms/RewriteStatepointsForGC/base-pointers-14.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -rewrite-statepoints-for-gc < %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 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:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP:%.*]], label [[MERGE2:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[B5:%.*]] = phi i8 addrspace(1)* [ [[B2:%.*]], [[LEFT:%.*]] ], [ [[B5]], [[LOOP]] ]
 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[MERGE2]]
 ; CHECK:       merge2:
loop:
   i32 2, label %left ]
 
 merge2:
   %b6 = phi i8 addrspace(1)* [ %b1, %left ], [ %b5, %loop ]
   call void @foo() [ "deopt"() ]
   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]]
 ;
 left:
   br i1 %c, label %loop, label %merge2
 
 loop: