[RS4GC] Fix algorithm to avoid setting vector BDV for scalar derived pointer

[anna]

Summary

This is a more general fix to 59029b9eef23 (D75704).
This patch does the following:

1. updates isKnownBaseValue to account for base pointer and

derived pointer having differing types.

2. This inturn allows us to populate the

lattice (States) for such derived pointers.

3. It also updates all states where the base and derived pointers have

differing types (vector versus scalar) and conservatively marks these
states as conflictcs.
Note that in 59029b9eef23, we were just fixing existing lattice values
and that too, only for uses of extractelement.

[anna]

fixed clang format. NFC w.r.t. prev diff.

[dantrushin]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

651

isa<VectorType>(V->getType()) != isa<VectorType>(Input->getType()) ?

[anna]

addressed review comments. fixed CI failure related to clang-tidy.

[dantrushin]

I hoped Philip will review this, because I'm not very familiar with this part of RS4GC and I have couple quetions here, see inline.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

641

Is Input a derived pointer here for which we check if V is a base of?.. Or vice versa?

884

Here I am confused.
Isn't Pair.second.getBaseValue() supposed to be base value for BDV? And we're asking the other way?
Same question for lines 944, 977 and few more below.

[anna]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

641

It's actually overloaded to answer two questions:

1. is V a knownBase?
2. Is V and Input having differing types (Input can be either the derivedPtr where V is the BasePtr or it can be the base pointer for V)

Technically, in most cases, we don't need Input because isKnownBaseResult is just depending on whether V is a knownBase.

I think a better factoring of the code will be to have a helper function which utilizes isKnownBaseResult and *then* checks whether Base and Input are both vector or both scalar type.

That will be cleaner and avoid the confusion below.

884

Yes, Pair.second.getBaseValue() is supposed to be base value for BDV.
This is actually just a check for the types to make sure we don't fail the assert here.
I think a cleaner assert is this:
assert((!isKnownBaseResult(BDV) || (BDV and Pair.second.getBaseValue() have differing scalar/vector types)) && "why did it get added")

Basically, knownBases that have different scalar/vector type from the

The lines you're referring to below will also be handled in similar way.

[anna]

Will avoid confusing usage with cleaner asserts.

[anna]

refactored code, made asserts cleaner.

[anna]

ping.

[skatkov]

From what I see it should work. The only thing worries me is that this isCorrectType seems to be not incorporated into solution but some side hack to solve the problem.
Unfortunately at this moment I do not have a better suggestion :(

If I understand correctly this is a fix for functional bug, so probably it makes sense to land it in this form.

Let me to thing one day more, if I cannot come up with some proposal I agree on this one.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

665

Confusing name...
areTypesMatched? or something like this?

[skatkov]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

665

May be even more specific - areBothVectorOrScalar?

[skatkov]

ok, I could not come up with something better, we can revisit at later.

Just please rename utility function to something more appropriate.

[anna]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

665

changed name to areBothVectorOrScalar.

[anna]

Landed as bb308b020522420413c7d3f2989a88f2fc423c56.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

static void analyzeParsePointLiveness(
   }
   if (PrintLiveSetSize) {
     dbgs() << "Safepoint For: " << Call->getCalledValue()->getName() << "\n";
     dbgs() << "Number live values: " << LiveSet.size() << "\n";
   }
   Result.LiveSet = LiveSet;
 }
 
-static bool isKnownBaseResult(Value *V);
+// Returns true is V is a knownBaseResult. If Input is passed in, we check that
+// Input and V are not conflicting type such as one being scalar type and the
+// other being vector type.
+static bool isKnownBaseResult(Value *V, Value *Input = nullptr);
 
 namespace {
 
 /// A single base defining value - An immediate base defining value for an
 /// instruction 'Def' is an input to 'Def' whose base is also a base of 'Def'.
 /// For instructions which have multiple pointer [vector] inputs or that
 /// transition between vector and scalar types, there is no immediate base
 /// defining value.  The 'base defining value' for 'Def' is the transitive
if (Found != Cache.end()) {
     return Found->second;
   }
   // Only a BDV available
   return Def;
 }
 
 /// Given the result of a call to findBaseDefiningValue, or findBaseOrBDV,
 /// is it known to be a base pointer?  Or do we need to continue searching.
-static bool isKnownBaseResult(Value *V) {
+static bool isKnownBaseResult(Value *V, Value *Input) {
   if (!isa<PHINode>(V) && !isa<SelectInst>(V) &&
       !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&
       !isa<ShuffleVectorInst>(V)) {
     // no recursion possible
     return true;
   }
+  // If we have the Input available, check that V and Input are both scalar or
+  // both vectors.
+  if (Input &&
+      isa<VectorType>(V->getType()) != isa<VectorType>(Input->getType()))
+    return false;
   if (isa<Instruction>(V) &&
       cast<Instruction>(V)->getMetadata("is_base_value")) {
     // This is a previously inserted base phi or select.  We know
     // that this is a base value.
     return true;
   }
 
   // We need to keep searching
   return false;
 }
 
 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 Status { Unknown, Base, Conflict };
 
   BDVState() : BaseValue(nullptr) {}

 
 /// For a given value or instruction, figure out what base ptr its derived from.
 /// For gc objects, this is simply itself.  On success, returns a value which is
 /// the base pointer.  (This is reliable and can be used for relocation.)  On
 /// failure, returns nullptr.
 static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache) {
   Value *Def = findBaseOrBDV(I, Cache);
 
-  if (isKnownBaseResult(Def))
+  if (isKnownBaseResult(Def, I))
     return Def;
 
   // Here's the rough algorithm:
   // - For every SSA value, construct a mapping to either an actual base
   //   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:
/* scope */ {
     Worklist.push_back(Def);
     States.insert({Def, BDVState()});
     while (!Worklist.empty()) {
       Value *Current = Worklist.pop_back_val();
       assert(!isKnownBaseResult(Current) && "why did it get added?");
 
       auto visitIncomingValue = [&](Value *InVal) {
         Value *Base = findBaseOrBDV(InVal, Cache);
-        if (isKnownBaseResult(Base))
+        if (isKnownBaseResult(Base, InVal))
           // Known bases won't need new instructions introduced and can be
           // ignored safely
           return;
         assert(isExpectedBDVType(Base) && "the only non-base values "
                "we see should be base defining values");
         if (States.insert(std::make_pair(Base, BDVState())).second)
           Worklist.push_back(Base);
       };
#ifndef NDEBUG
   LLVM_DEBUG(dbgs() << "States after initialization:\n");
   for (auto Pair : States) {
     LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
   }
 #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) {
-    if (isKnownBaseResult(baseValue))
-      return BDVState(baseValue);
-    auto I = States.find(baseValue);
+  auto GetStateForBDV = [&](Value *BaseValue, Value *Input) {
+    if (isKnownBaseResult(BaseValue, Input))
+      return BDVState(BaseValue);
+    auto I = States.find(BaseValue);
     assert(I != States.end() && "lookup failed!");
     return I->second;
   };
 
   bool Progress = true;
   while (Progress) {
 #ifndef NDEBUG
     const size_t OldSize = States.size();
 #endif
     Progress = false;
     // We're only changing values in this loop, thus safe to keep iterators.
     // Since this is computing a fixed point, the order of visit does not
     // effect the result.  TODO: We could use a worklist here and make this run
     // much faster.
     for (auto Pair : States) {
       Value *BDV = Pair.first;
-      assert(!isKnownBaseResult(BDV) && "why did it get added?");
+      assert(!isKnownBaseResult(BDV, Pair.second.getBaseValue()) &&
+             "why did it get added?");
 
       // Given an input value for the current instruction, return a BDVState
       // instance which represents the BDV of that value.
       auto getStateForInput = [&](Value *V) mutable {
         Value *BDV = findBaseOrBDV(V, Cache);
-        return getStateForBDV(BDV);
+        return GetStateForBDV(BDV, V);
       };
 
       BDVState NewState;
       if (SelectInst *SI = dyn_cast<SelectInst>(BDV)) {
         NewState = meetBDVState(NewState, getStateForInput(SI->getTrueValue()));
         NewState =
             meetBDVState(NewState, getStateForInput(SI->getFalseValue()));
       } else if (PHINode *PN = dyn_cast<PHINode>(BDV)) {

 
 #ifndef NDEBUG
   LLVM_DEBUG(dbgs() << "States after meet iteration:\n");
   for (auto Pair : States) {
     LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");
   }
 #endif
 
-  // Handle extractelement instructions and their uses.
+  // 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;
-    assert(!isKnownBaseResult(I) && "why did it get added?");
+    auto *BaseValue = State.getBaseValue();
+    assert(!isKnownBaseResult(I, BaseValue) && "why did it get added?");
     assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
 
+    if (!State.isBase() || !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 (!State.isBase() || !isa<ExtractElementInst>(I) ||
-        !isa<VectorType>(State.getBaseValue()->getType()))
-      continue;
+    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(BDVState::Base, BaseInst);
-
-    // We need to handle uses of the extractelement that have the same vector
-    // base as well but the use is a scalar type. Since we cannot reuse the
-    // same BaseInst above (may not satisfy property that base pointer should
-    // always dominate derived pointer), we conservatively set this as conflict.
-    // Setting the base value for these conflicts is handled in the next loop
-    // which traverses States.
-    for (User *U : I->users()) {
-      auto *UseI = dyn_cast<Instruction>(U);
-      if (!UseI || !States.count(UseI))
-        continue;
-      if (!isa<VectorType>(UseI->getType()) && States[UseI] == State)
-        States[UseI] = BDVState(BDVState::Conflict);
+    } 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(BDVState::Conflict);
     }
   }
 
   // Insert Phis for all conflicts
   // TODO: adjust naming patterns to avoid this order of iteration dependency
   for (auto Pair : States) {
     Instruction *I = cast<Instruction>(Pair.first);
     BDVState State = Pair.second;
-    assert(!isKnownBaseResult(I) && "why did it get added?");
+    assert(!isKnownBaseResult(I, State.getBaseValue()) &&
+           "why did it get added?");
     assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
 
     // Since we're joining a vector and scalar base, they can never be the
     // same.  As a result, we should always see insert element having reached
     // the conflict state.
     assert(!isa<InsertElementInst>(I) || State.isConflict());
 
     if (!State.isConflict())
#endif
   // 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 (isKnownBaseResult(BDV)) {
+    if (isKnownBaseResult(BDV, Input)) {
       Base = BDV;
     } else {
       // Either conflict or base.
       assert(States.count(BDV));
       Base = States[BDV].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;
   };
 
   // Fixup all the inputs of the new PHIs.  Visit order needs to be
   // deterministic and predictable because we're naming newly created
   // instructions.
   for (auto Pair : States) {
     Instruction *BDV = cast<Instruction>(Pair.first);
     BDVState State = Pair.second;
 
-    assert(!isKnownBaseResult(BDV) && "why did it get added?");
+    assert(!isKnownBaseResult(BDV, State.getBaseValue()) &&
+           "why did it get added?");
     assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
     if (!State.isConflict())
       continue;
 
     if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {
       PHINode *PN = cast<PHINode>(BDV);
       unsigned NumPHIValues = PN->getNumIncomingValues();
       for (unsigned i = 0; i < NumPHIValues; i++) {
#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();
     assert(BDV && Base);
-    assert(!isKnownBaseResult(BDV) && "why did it get added?");
+    assert(!isKnownBaseResult(BDV, Base) && "why did it get added?");
 
     LLVM_DEBUG(
         dbgs() << "Updating base value cache"
                << " for: " << BDV->getName() << " from: "
                << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none")
                << " to: " << Base->getName() << "\n");
 
     if (Cache.count(BDV)) {

llvm/test/Transforms/RewriteStatepointsForGC/scalar-base-vector.ll

 bb7:                                              ; preds = %bb25
   br label %latch
 
 latch:                                              ; preds = %bb25, %bb7
   %tmp6 = phi i8 addrspace(1)* [ %tmp27, %bb25 ], [ %tmp27, %bb7 ]
   br label %header
 }
 
+; Uses of extractelement that are of scalar type should not have the BDV
+; incorrectly identified as a vector type.
+define void @widget() gc "statepoint-example" {
+; CHECK-LABEL: @widget(
+; CHECK-NEXT:  bb6:
+; CHECK-NEXT:    [[BASE_EE:%.*]] = extractelement <2 x i8 addrspace(1)*> zeroinitializer, i32 1, !is_base_value !0
+; CHECK-NEXT:    [[TMP:%.*]] = extractelement <2 x i8 addrspace(1)*> undef, i32 1
+; CHECK-NEXT:    br i1 undef, label [[BB7:%.*]], label [[BB9:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    [[TMP8:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* [[TMP]], i64 12
+; CHECK-NEXT:    br label [[BB11:%.*]]
+; CHECK:       bb9:
+; CHECK-NEXT:    [[TMP10:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* [[TMP]], i64 12
+; CHECK-NEXT:    br i1 undef, label [[BB11]], label [[BB15:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP12_BASE:%.*]] = phi i8 addrspace(1)* [ [[BASE_EE]], [[BB7]] ], [ [[BASE_EE]], [[BB9]] ], !is_base_value !0
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i8 addrspace(1)* [ [[TMP8]], [[BB7]] ], [ [[TMP10]], [[BB9]] ]
+; CHECK-NEXT:    [[STATEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @snork, i32 0, i32 0, i32 0, i32 1, i32 undef, i8 addrspace(1)* [[TMP12_BASE]], i8 addrspace(1)* [[TMP12]])
+; CHECK-NEXT:    [[TMP12_BASE_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 8, i32 8)
+; CHECK-NEXT:    [[TMP12_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 8, i32 9)
+; CHECK-NEXT:    br label [[BB15]]
+; CHECK:       bb15:
+; CHECK-NEXT:    [[TMP16_BASE:%.*]] = phi i8 addrspace(1)* [ [[BASE_EE]], [[BB9]] ], [ [[TMP12_BASE_RELOCATED]], [[BB11]] ], !is_base_value !0
+; CHECK-NEXT:    [[TMP16:%.*]] = phi i8 addrspace(1)* [ [[TMP10]], [[BB9]] ], [ [[TMP12_RELOCATED]], [[BB11]] ]
+; CHECK-NEXT:    br i1 undef, label [[BB17:%.*]], label [[BB20:%.*]]
+; CHECK:       bb17:
+; CHECK-NEXT:    [[STATEPOINT_TOKEN1:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @snork, i32 0, i32 0, i32 0, i32 1, i32 undef, i8 addrspace(1)* [[TMP16_BASE]], i8 addrspace(1)* [[TMP16]])
+; CHECK-NEXT:    [[TMP16_BASE_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN1]], i32 8, i32 8)
+; CHECK-NEXT:    [[TMP16_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN1]], i32 8, i32 9)
+; CHECK-NEXT:    br label [[BB20]]
+; CHECK:       bb20:
+; CHECK-NEXT:    [[DOT05:%.*]] = phi i8 addrspace(1)* [ [[TMP16_BASE_RELOCATED]], [[BB17]] ], [ [[TMP16_BASE]], [[BB15]] ]
+; CHECK-NEXT:    [[DOT0:%.*]] = phi i8 addrspace(1)* [ [[TMP16_RELOCATED]], [[BB17]] ], [ [[TMP16]], [[BB15]] ]
+; CHECK-NEXT:    [[STATEPOINT_TOKEN2:%.*]] = call token (i64, i32, void (i8 addrspace(1)*)*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidp1i8f(i64 2882400000, i32 0, void (i8 addrspace(1)*)* @foo, i32 1, i32 0, i8 addrspace(1)* [[DOT0]], i32 0, i32 0, i8 addrspace(1)* [[DOT05]], i8 addrspace(1)* [[DOT0]])
+; CHECK-NEXT:    [[TMP16_BASE_RELOCATED3:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN2]], i32 8, i32 8)
+; CHECK-NEXT:    [[TMP16_RELOCATED4:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN2]], i32 8, i32 9)
+; CHECK-NEXT:    ret void
+;
+bb6:                                              ; preds = %bb3
+  %tmp = extractelement <2 x i8 addrspace(1)*> undef, i32 1
+  br i1 undef, label %bb7, label %bb9
+
+bb7:                                              ; preds = %bb6
+  %tmp8 = getelementptr inbounds i8, i8 addrspace(1)* %tmp, i64 12
+  br label %bb11
+
+bb9:                                              ; preds = %bb6, %bb6
+  %tmp10 = getelementptr inbounds i8, i8 addrspace(1)* %tmp, i64 12
+  br i1 undef, label %bb11, label %bb15
+
+bb11:                                             ; preds = %bb9, %bb7
+  %tmp12 = phi i8 addrspace(1)* [ %tmp8, %bb7 ], [ %tmp10, %bb9 ]
+  call void @snork() [ "deopt"(i32 undef) ]
+  br label %bb15
+
+bb15:                                             ; preds = %bb11, %bb9, %bb9
+  %tmp16 = phi i8 addrspace(1)* [ %tmp10, %bb9 ], [ %tmp12, %bb11 ]
+  br i1 undef, label %bb17, label %bb20
+
+bb17:                                             ; preds = %bb15
+  call void @snork() [ "deopt"(i32 undef) ]
+  br label %bb20
+
+bb20:                                             ; preds = %bb17, %bb15, %bb15
+  call void @foo(i8 addrspace(1)* %tmp16)
+  ret void
+}
+
+declare void @snork()
+declare void @foo(i8 addrspace(1)*)
 declare void @spam()
 declare <2 x i8 addrspace(1)*> @baz()