[RS4GC] Handle ShuffleVector instruction in findBasePointer

[anna]

Summary

This patch modifies the findBasePointer to handle the shufflevector instruction.

Tests run: RS4GC tests, local downstream tests.

[reames]

LGTM w/changes applied.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

874 ↗

(On Diff #73300)

per lang ref, these should be the same type and thus the same value.

test/Transforms/RewriteStatepointsForGC/base-vector.ll

169 ↗

(On Diff #73300)

Add a test case which merges two distinct base values (i.e. arguments).

[anna]

test/Transforms/RewriteStatepointsForGC/base-vector.ll

169 ↗

(On Diff #73300)

Added test case with vector operand of shuffle vector being a phi with distinct bases.

llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache) {
   // Note: A simpler form of this would be to add the conflict form of all
   // PHIs without running the optimistic algorithm.  This would be
   // analogous to pessimistic data flow and would likely lead to an
   // overall worse solution.
 
 #ifndef NDEBUG
   auto isExpectedBDVType = [](Value *BDV) {
     return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||
-           isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV);
+           isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||
+           isa<ShuffleVectorInst>(BDV);
   };
 #endif
 
   // Once populated, will contain a mapping from each potentially non-base BDV
   // to a lattice value (described above) which corresponds to that BDV.
   // We use the order of insertion (DFS over the def/use graph) to provide a
   // stable deterministic ordering for visiting DenseMaps (which are unordered)
   // below.  This is important for deterministic compilation.
while (!Worklist.empty()) {
       } else if (SelectInst *SI = dyn_cast<SelectInst>(Current)) {
         visitIncomingValue(SI->getTrueValue());
         visitIncomingValue(SI->getFalseValue());
       } else if (auto *EE = dyn_cast<ExtractElementInst>(Current)) {
         visitIncomingValue(EE->getVectorOperand());
       } else if (auto *IE = dyn_cast<InsertElementInst>(Current)) {
         visitIncomingValue(IE->getOperand(0)); // vector operand
         visitIncomingValue(IE->getOperand(1)); // scalar operand
-      } else {
-        // There is one known class of instructions we know we don't handle.
-        assert(isa<ShuffleVectorInst>(Current));
+      } else if (auto *SV = dyn_cast<ShuffleVectorInst>(Current)) {
+        visitIncomingValue(SV->getOperand(0));
+        visitIncomingValue(SV->getOperand(1));
+      }
+      else {
         llvm_unreachable("Unimplemented instruction case");
       }
     }
   }
 
 #ifndef NDEBUG
   DEBUG(dbgs() << "States after initialization:\n");
   for (auto Pair : States) {
for (auto Pair : States) {
       } else if (PHINode *PN = dyn_cast<PHINode>(BDV)) {
         for (Value *Val : PN->incoming_values())
           NewState = meetBDVState(NewState, getStateForInput(Val));
       } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) {
         // The 'meet' for an extractelement is slightly trivial, but it's still
         // useful in that it drives us to conflict if our input is.
         NewState =
             meetBDVState(NewState, getStateForInput(EE->getVectorOperand()));
-      } else {
+      } else if (auto *IE = dyn_cast<InsertElementInst>(BDV)){
         // Given there's a inherent type mismatch between the operands, will
         // *always* produce Conflict.
-        auto *IE = cast<InsertElementInst>(BDV);
         NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(0)));
         NewState = meetBDVState(NewState, getStateForInput(IE->getOperand(1)));
+      } else {
+        // The only instance this does not return a Conflict is when both the
+        // vector operands are the same vector.
+        auto *SV = cast<ShuffleVectorInst>(BDV);
+        NewState = meetBDVState(NewState, getStateForInput(SV->getOperand(0)));
+        NewState = meetBDVState(NewState, getStateForInput(SV->getOperand(1)));
       }
 
       BDVState OldState = States[BDV];
       if (OldState != NewState) {
         Progress = true;
         States[BDV] = NewState;
       }
     }
auto MakeBaseInstPlaceholder = [](Instruction *I) -> Instruction* {
         UndefValue *Undef = UndefValue::get(SI->getType());
         std::string Name = suffixed_name_or(I, ".base", "base_select");
         return SelectInst::Create(SI->getCondition(), Undef, Undef, Name, SI);
       } else if (auto *EE = dyn_cast<ExtractElementInst>(I)) {
         UndefValue *Undef = UndefValue::get(EE->getVectorOperand()->getType());
         std::string Name = suffixed_name_or(I, ".base", "base_ee");
         return ExtractElementInst::Create(Undef, EE->getIndexOperand(), Name,
                                           EE);
-      } else {
-        auto *IE = cast<InsertElementInst>(I);
+      } else if (auto *IE = dyn_cast<InsertElementInst>(I)) {
         UndefValue *VecUndef = UndefValue::get(IE->getOperand(0)->getType());
         UndefValue *ScalarUndef = UndefValue::get(IE->getOperand(1)->getType());
         std::string Name = suffixed_name_or(I, ".base", "base_ie");
         return InsertElementInst::Create(VecUndef, ScalarUndef,
                                          IE->getOperand(2), Name, IE);
+      } else {
+        auto *SV = cast<ShuffleVectorInst>(I);
+        UndefValue *VecUndef = UndefValue::get(SV->getOperand(0)->getType());
+        std::string Name = suffixed_name_or(I, ".base", "base_sv");
+        return new ShuffleVectorInst(VecUndef, VecUndef, SV->getOperand(2),
+                                     Name, SV);
       }
     };
     Instruction *BaseInst = MakeBaseInstPlaceholder(I);
     // Add metadata marking this as a base value
     BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
     States[I] = BDVState(BDVState::Conflict, BaseInst);
   }
 
#endif
       BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));
       BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));
     } else if (auto *BaseEE =
                    dyn_cast<ExtractElementInst>(State.getBaseValue())) {
       Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();
       // Find the instruction which produces the base for each input.  We may
       // need to insert a bitcast.
       BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));
-    } else {
-      auto *BaseIE = cast<InsertElementInst>(State.getBaseValue());
+    } else if (auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){
       auto *BdvIE = cast<InsertElementInst>(BDV);
       auto UpdateOperand = [&](int OperandIdx) {
         Value *InVal = BdvIE->getOperand(OperandIdx);
         Value *Base = getBaseForInput(InVal, BaseIE);
         BaseIE->setOperand(OperandIdx, Base);
       };
       UpdateOperand(0); // vector operand
       UpdateOperand(1); // scalar operand
+    } else {
+      auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());
+      auto *BdvSV = cast<ShuffleVectorInst>(BDV);
+      auto UpdateOperand = [&](int OperandIdx) {
+        Value *InVal = BdvSV->getOperand(OperandIdx);
+        Value *Base = getBaseForInput(InVal, BaseSV);
+        BaseSV->setOperand(OperandIdx, Base);
+      };
+      UpdateOperand(0); // vector operand
+      UpdateOperand(1); // vector operand
     }
   }
 
   // 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;

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

; CHECK-DAG: (%objb.base, %objb)
   %objb = phi i64 addrspace(1)* [ %obj, %next1 ], [ %bdv, %merge ]
   br i1 %cnd, label %merge, label %next
 
 next:                                             ; preds = %merge
   call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
   ret i64 addrspace(1)* %objb
 }
 
+; identify base for shufflevector
+define void @test8(i64 addrspace(1)* %obj, i64 %idx) gc "statepoint-example" {
+; CHECK-LABEL: @test8
+; CHECK: %gep = getelementptr i64, i64 addrspace(1)* %obj, i64 1
+; CHECK: %gep2 = getelementptr i64, i64 addrspace(1)* %obj, i64 2
+; CHECK: %vec1.base = insertelement <4 x i64 addrspace(1)*> zeroinitializer, i64 addrspace(1)* %obj, i32 0, !is_base_value !0
+; CHECK: %vec1 = insertelement <4 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep, i32 0
+; CHECK: %vec2.base = insertelement <4 x i64 addrspace(1)*> zeroinitializer, i64 addrspace(1)* %obj, i32 2, !is_base_value !0
+; CHECK: %vec2 = insertelement <4 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep2, i32 2
+; CHECK: %vec.base = shufflevector <4 x i64 addrspace(1)*> %vec1.base, <4 x i64 addrspace(1)*> %vec2.base, <2 x i32> <i32 0, i32 2>, !is_base_value !0
+; CHECK: %vec = shufflevector <4 x i64 addrspace(1)*> %vec1, <4 x i64 addrspace(1)*> %vec2, <2 x i32> <i32 0, i32 2>
+; CHECK: %bdv.base = extractelement <2 x i64 addrspace(1)*> %vec.base, i64 %idx, !is_base_value !0
+; CHECK: %bdv = extractelement <2 x i64 addrspace(1)*> %vec, i64 %idx
+; CHECK: gc.statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: (%bdv.base, %bdv)
+entry:
+  %gep = getelementptr i64, i64 addrspace(1)* %obj, i64 1
+  %gep2 = getelementptr i64, i64 addrspace(1)* %obj, i64 2
+  %vec1 = insertelement <4 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep, i32 0
+  %vec2 = insertelement <4 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep2, i32 2
+  %vec = shufflevector <4 x i64 addrspace(1)*> %vec1, <4 x i64 addrspace(1)*> %vec2, <2 x i32> <i32 0, i32 2>
+  %bdv = extractelement <2 x i64 addrspace(1)*> %vec, i64 %idx
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  call void @use(i64 addrspace(1)* %bdv)
+  ret void
+}
+
+; Since the same 'base' vector is used in the shuffle operands, we do not need
+; create a shufflevector base.
+define void @test9(<4 x i64 addrspace(1)*> %vec1, i64 %idx) gc "statepoint-example" {
+; CHECK-LABEL: @test9
+; CHECK: %vec = shufflevector <4 x i64 addrspace(1)*> %vec1, <4 x i64 addrspace(1)*> %vec1, <2 x i32> <i32 0, i32 2>
+; CHECK: %base_ee = extractelement <4 x i64 addrspace(1)*> %vec1, i64 %idx, !is_base_value !0
+; CHECK: %bdv = extractelement <2 x i64 addrspace(1)*> %vec, i64 %idx
+; CHECK: gc.statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: (%base_ee, %bdv)
+entry:
+ ; shrinking vec1 into vec
+  %vec = shufflevector <4 x i64 addrspace(1)*> %vec1, <4 x i64 addrspace(1)*> %vec1, <2 x i32> <i32 0, i32 2>
+  %bdv = extractelement <2 x i64 addrspace(1)*> %vec, i64 %idx
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  call void @use(i64 addrspace(1)* %bdv)
+  ret void
+}
+
+; vector operand of shufflevector is a phi
+define i64 addrspace(1)* @test10(i1 %cnd, i64 addrspace(1)* %obj, i64 addrspace(1)* %obj2) gc "statepoint-example" {
+; CHECK-LABEL: @test10
+entry:
+  %vec1 = insertelement <4 x i64 addrspace(1)*> undef, i64 addrspace(1)* %obj, i32 0
+  br i1 %cnd, label %here, label %merge
+
+here:
+  %vec2 = insertelement <4 x i64 addrspace(1)*> undef, i64 addrspace(1)* %obj2, i32 2
+  br label %merge
+
+merge:                                           ; preds = %merge, %entry, %here
+; CHECK-LABEL: merge:
+; CHECK: %vec.base = phi <4 x i64 addrspace(1)*> [ %vec1.base, %entry ], [ %vec2.base, %here ], [ %vec3.base, %merge ], !is_base_value !0
+; CHECK: vec
+; CHECK: vec3.base = shufflevector <4 x i64 addrspace(1)*> %vec.base, <4 x i64 addrspace(1)*> %vec.base
+; CHECK: vec3
+; CHECK: bdv.base
+; CHECK: bdv
+  %vec = phi <4 x i64 addrspace(1)*> [ %vec1, %entry ], [ %vec2, %here], [ %vec3, %merge]
+  %vec3 = shufflevector <4 x i64 addrspace(1)*> %vec, <4 x i64 addrspace(1)*> %vec, <4 x i32> <i32 2, i32 0, i32 1, i32 3>
+  %bdv = extractelement <4 x i64 addrspace(1)*> %vec3, i32 0
+  br i1 %cnd, label %merge, label %next
+
+next:
+; CHECK-LABEL: next:
+; CHECK: gc.statepoint
+; CHECK: gc.relocate
+; CHECK-DAG: (%bdv.base, %bdv)
+  call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  ret i64 addrspace(1)* %bdv
+}
 declare void @do_safepoint()