[RS4GC] Treat a value that has a single base and no derived inputs as base value

[dmakogon]

Summary

With this patch we track a IsDerived state for BDVs.
It is true for a given BDV if any of its operands is not equal to its BDV (stripping pointer casts).
If we find out that a pointer for which we are finding a base has a single base and has no derived inputs, we say that this pointer is actually equal to its base, so it is a base pointer itself, hence there's no need to relocate the original base along with this 'derived' pointer.

[mkazantsev]

LGTM w/ nit.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

847

I think a clarifying comment is needed here. Does IsDerived = true mean that it must be a derived pointer, or does it simply mean that we haven't proven it's a base?

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

public:
   };
 
   BDVState() {
     llvm_unreachable("missing state in map");
   }
 
   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, bool IsDerived = true)
+      : OriginalValue(OriginalValue), Status(Status), BaseValue(BaseValue),
+        IsDerived(IsDerived) {
     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 isConflict() const { return getStatus() == Conflict; }
+  bool isDerived() const { return IsDerived; }
+  void setIsDerived(bool IsDerived) {
+    this->IsDerived = IsDerived;
+  }
 
   // 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;
+      IsDerived = true;
     };
     // 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();
+      IsDerived = Other.isDerived();
       return;
     }
     // We are base.
     assert(isBase() && "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())
       return markConflict();
-    // We are identical, do nothing.
+    // We have the same bases. If the other is derived, so we are.
+    IsDerived |= Other.isDerived();
   }
 
   bool operator==(const BDVState &Other) const {
     return OriginalValue == Other.OriginalValue && BaseValue == Other.BaseValue &&
-      Status == Other.Status;
+      Status == Other.Status && IsDerived == Other.IsDerived;
   }
 
   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 Conflict:
       OS << "C";
       break;
     }
     OS << " (base " << getBaseValue() << " - "
-       << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << ")"
-       << " for  "  << OriginalValue->getName() << ":";
+       << (getBaseValue() ? getBaseValue()->getName() : "nullptr")
+       << ", is derived = " << isDerived() << ")"
+       << " 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.
+  bool IsDerived = true;
 };
 
 } // end anonymous namespace
 
 #ifndef NDEBUG
 static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) {
   State.print(OS);
   return OS;
#endif
   // Did we manage to prove that Def itself must be a base pointer?
   if (!States.count(DefBase))
     return Def;
 
   // 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 = [&](BaseDefiningValueResult &BaseValue, Value *Input) {
     auto I = States.find(BaseValue);
-    if (I != States.end())
-      return I->second;
+    if (I == States.end() || BaseValue.isKnownBase()) {
       assert(areBothVectorOrScalar(BaseValue.getBDV(), Input));
-    return BDVState(BaseValue.getBDV(), BDVState::Base, BaseValue.getBDV());
+      return BDVState(BaseValue.getBDV(), BDVState::Base, BaseValue.getBDV(),
+                      /*IsDerived=*/false);
+    }
+    return I->second;
   };
 
   bool Progress = true;
   while (Progress) {
 #ifndef NDEBUG
     const size_t OldSize = States.size();
 #endif
     Progress = false;
for (auto Pair : States) {
              !areBothVectorOrScalar(BDV, Pair.second.getBaseValue())) &&
                  "why did it get added?");
 
       BDVState NewState(BDV);
       visitBDVOperands(BDV, [&](Value *Op) {
         auto BaseOrBDV = findBaseOrBDV(Op, Cache);
         Value *BDV = BaseOrBDV.getBDV();
         auto OpState = GetStateForBDV(BaseOrBDV, Op);
+        // If the operand is not the same as its BDV the state should be
+        // derived.
+        if (Op->stripPointerCasts() != BDV)
+          OpState.setIsDerived(true);
         NewState.meet(OpState);
       });
 
       BDVState OldState = States[Base];
       if (OldState != NewState) {
         Progress = true;
         States[Base] = NewState;
       }
#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.getBDV();
     Value *Base = Pair.second.getBaseValue();
     assert(BDV && Base);
+    if (!Pair.second.isDerived() && !isOriginalBaseResult(BDV))
+      Base = Pair.second.getOriginalValue();
     // 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((!Pair.first.isKnownBase() || !areBothVectorOrScalar(BDV, Base)) &&
            "why did it get added?");
 
     LLVM_DEBUG(dbgs() << "Updating base value cache"
                       << " for: " << BDV->getName() << " from: "

llvm/test/Transforms/RewriteStatepointsForGC/single-base.ll

 ; CHECK-NEXT:    [[B6]] = phi i8 addrspace(1)* [ [[B5]], [[LOOP]] ], [ [[B6]], [[INNER_LOOP]] ]
 ; CHECK-NEXT:    [[C2:%.*]] = call i1 @runtime_value()
 ; CHECK-NEXT:    br i1 [[C2]], label [[INNER_LOOP]], label [[INNER_LOOP_LATCH]]
 ; CHECK:       inner_loop_latch:
 ; CHECK-NEXT:    [[C3:%.*]] = call i1 @runtime_value()
 ; CHECK-NEXT:    br i1 [[C3]], label [[LOOP]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[MERGE:%.*]] = phi i8 addrspace(1)* [ [[B5]], [[LOOP]] ], [ [[B6]], [[INNER_LOOP_LATCH]] ]
-; 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)* [[MERGE]], i8 addrspace(1)* [[B1]]) ]
-; CHECK-NEXT:    [[MERGE_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 1, i32 0)
-; CHECK-NEXT:    [[B1_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 1, i32 1)
+; 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)* [[MERGE]]) ]
+; CHECK-NEXT:    [[MERGE_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    ret i8 addrspace(1)* [[MERGE_RELOCATED]]
 ;
 entry:
   br label %loop
 
 loop:
   %b5 = phi i8 addrspace(1)* [ %b1, %entry ], [ %b6, %inner_loop_latch ]
   %c1 = call i1 @runtime_value()

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[B5:%.*]] = phi i8 addrspace(1)* [ [[B1:%.*]], [[ENTRY:%.*]] ], [ [[B6:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[B6]] = phi i8 addrspace(1)* [ [[B1]], [[ENTRY]] ], [ [[B5]], [[LOOP]] ]
 ; CHECK-NEXT:    [[C1:%.*]] = call i1 @runtime_value()
 ; CHECK-NEXT:    br i1 [[C1]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
-; 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]], i8 addrspace(1)* [[B1]]) ]
-; CHECK-NEXT:    [[B6_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 1, i32 0)
-; CHECK-NEXT:    [[B1_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 1, i32 1)
+; 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:    ret i8 addrspace(1)* [[B6_RELOCATED]]
 ;
 entry:
   br label %loop
 
 loop:
   %b5 = phi i8 addrspace(1)* [ %b1, %entry ], [ %b6, %loop ]
   %b6 = phi i8 addrspace(1)* [ %b1, %entry ], [ %b5, %loop ]
   %c1 = call i1 @runtime_value()
   br i1 %c1, label %loop, label %exit
 
 exit:
   call void @foo() [ "deopt"() ]
   ret i8 addrspace(1)* %b6
 }