[Statepoints] Relocating vectors of pointers

[reames]

Summary

Currently, we try to split vectors of pointers back into their component pointer elements during rewrite-statepoints-for-gc. This is less than ideal since presumably the vectorizer chose to vectorize for a reason. :) It's also been a source of bugs - in particular, the relocation logic as currently implemented was recently discovered to be wrong.

The alternate approach is to allow gc.relocates of vector-of-pointer type and update the backend to handle them. That's what this patch tries to do. This won't actually enable vector-of-pointers in practice - there are some RS4GC changes needed - but the lowering is standalone and testable so it makes sense to separate.

Note that there are some known cases around vector constants which this patch does not handle. Once this is in, I'll send another patch with test cases. I decided to separate them since it would let me make progress on other parts - RS4GC, frontend changes - in parallel. The additional changes required don't look particularly complex.

[sanjoy]

As I've said in person, I'm worried about LLVM (SelectionDAG & later,
specifically) making assumptions on how spill slots can be used. For
instance, if there is an assumption that spill slots are strictly
frame local, then this transform becomes legal (gc_ref is a callee
saved register):

[%rsp + 48] = gc_ref
call _foo ## statepoint
gc_ref_relocated = [%rsp + 48]

>

[%rsp + 48] = gc_ref
gc_ref_relocated = [%rsp + 48]
call _foo ## statepoint

Since the call to _foo could not have possibly clobbered a frame local
location (since the frame is where you spill registers to *avoid* them
getting clobbered!).

In fact, I suspect this is unsound even today. I still can't see the
whole picture, but for instance, in MachineLICM.cpp you have:

static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
  for (MachineInstr::mmo_iterator o = MI->memoperands_begin(),
         oe = MI->memoperands_end(); o != oe; ++o) {
    if (!(*o)->isStore() || !(*o)->getPseudoValue())
      continue;
    if (const FixedStackPseudoSourceValue *Value =
        dyn_cast<FixedStackPseudoSourceValue>((*o)->getPseudoValue())) {
      if (Value->getFrameIndex() == FI)
        return true;
    }
  }
  return false;
}

and I don't see how a STATEPOINT node (as created in
StatepointLowering.cpp) gets a FixedStackPseudoSourceValue in its
memoperands vector (the loads and stores we generate around the
STATEPOINT node the right aliasing information).

[reames]

In D15632#313619, @sanjoy wrote:

As I've said in person, I'm worried about LLVM (SelectionDAG & later,
specifically) making assumptions on how spill slots can be used.

The general concern is a valid one. I think I've talked myself/you've talked me around to an alternate approach. If we add new flags to StackObject called 'isDeoptSpil' and 'isGCSpill' we can customize the behaviour much more obviously and safely. I'm going to restructure this patch in that direction unless someone speaks up to say that's a bad idea.

For
instance, if there is an assumption that spill slots are strictly
frame local, then this transform becomes legal (gc_ref is a callee
saved register):

[%rsp + 48] = gc_ref
call _foo ## statepoint
gc_ref_relocated = [%rsp + 48]

>

[%rsp + 48] = gc_ref
gc_ref_relocated = [%rsp + 48]
call _foo ## statepoint

Since the call to _foo could not have possibly clobbered a frame local
location (since the frame is where you spill registers to *avoid* them
getting clobbered!).

This is supposed to be handled by the volatile, load, and store flags we put on the memory operands in emitPatchPoint, but see below....

In fact, I suspect this is unsound even today. I still can't see the
whole picture, but for instance, in MachineLICM.cpp you have:

static bool InstructionStoresToFI(const MachineInstr *MI, int FI) {
  for (MachineInstr::mmo_iterator o = MI->memoperands_begin(),
         oe = MI->memoperands_end(); o != oe; ++o) {
    if (!(*o)->isStore() || !(*o)->getPseudoValue())
      continue;
    if (const FixedStackPseudoSourceValue *Value =
        dyn_cast<FixedStackPseudoSourceValue>((*o)->getPseudoValue())) {
      if (Value->getFrameIndex() == FI)
        return true;
    }
  }
  return false;
}

To the best of my knowledge, this code is incorrect. See http://reviews.llvm.org/D15730 with a proposed fix.

and I don't see how a STATEPOINT node (as created in
StatepointLowering.cpp) gets a FixedStackPseudoSourceValue in its
memoperands vector (the loads and stores we generate around the
STATEPOINT node the right aliasing information).

This is done in emitPatchPoint at around 1129 in CodeGen/TargetLoweringBase.cpp

[sanjoy]

In D15632#315852, @reames wrote:

This is done in emitPatchPoint at around 1129 in CodeGen/TargetLoweringBase.cpp

I was only looking at StatepointLowering.cpp -- there we create a
STATEPOINT node without any indication that it may touch the created
spill slots (as opposed to the store and load instructions we create).
However, if the invariant is that "no mem operands == touches the
whole heap", then this is fine.

[reames]

This patch needs to be rebased on http://reviews.llvm.org/D15759 "[Statepoints] Use Indirect operands for spill slots" and 256312: "[GC] Make GCStrategy::isGCManagedPointer a type predicate not a value", before further review. Note that the approach described in this review is different from the one I settled on in D15759.

[reames]

Rebased patch. Ready for review. Removing several reviewers who are likely not interested in the remaining changes since the backend bits were separated and already landed.

[reames]

ping!

[pgavlin]

LGTM.

include/llvm/CodeGen/SelectionDAG.h

SDDbgInfo::DbgIterator ByvalParmDbgEnd()   {
     return DbgInfo->ByvalParmDbgEnd();
   }
 
   void dump() const;
 
   /// Create a stack temporary, suitable for holding the
   /// specified value type.  If minAlign is specified, the slot size will have
   /// at least that alignment.
-  SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
+  SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1,
+                               bool isSS = false);
 
   /// Create a stack temporary suitable for holding
   /// either of the specified value types.
   SDValue CreateStackTemporary(EVT VT1, EVT VT2);
 
   SDValue FoldConstantArithmetic(unsigned Opcode, SDLoc DL, EVT VT,
                                  SDNode *Cst1, SDNode *Cst2);
 

include/llvm/IR/Intrinsics.td

 def int_experimental_gc_statepoint : Intrinsic<[llvm_i32_ty],
                                [llvm_i64_ty, llvm_i32_ty,
                                 llvm_anyptr_ty, llvm_i32_ty,
                                 llvm_i32_ty, llvm_vararg_ty],
                                 [Throws]>;
 
 def int_experimental_gc_result   : Intrinsic<[llvm_any_ty], [llvm_i32_ty],
                                              [IntrReadMem]>;
-def int_experimental_gc_relocate : Intrinsic<[llvm_anyptr_ty],
+def int_experimental_gc_relocate : Intrinsic<[llvm_any_ty],
                                 [llvm_i32_ty, llvm_i32_ty, llvm_i32_ty],
                                 [IntrReadMem]>;
 
 // Deprecated: will be removed in a couple of weeks
 def int_experimental_gc_result_int : Intrinsic<[llvm_anyint_ty], [llvm_i32_ty]>;
 def int_experimental_gc_result_float : Intrinsic<[llvm_anyfloat_ty],
                                                  [llvm_i32_ty]>;
 def int_experimental_gc_result_ptr : Intrinsic<[llvm_anyptr_ty], [llvm_i32_ty]>;

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

SDValue Tmp1 = getLoad(TLI.getPointerTy(getDataLayout()), dl,
                          Node->getOperand(0), Node->getOperand(2),
                          MachinePointerInfo(VS), false, false, false, 0);
   return getStore(Tmp1.getValue(1), dl, Tmp1, Node->getOperand(1),
                   MachinePointerInfo(VD), false, false, 0);
 }
 
 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
 /// specified value type.
-SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) {
+SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign,
+                                           bool isSS) {
   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
   unsigned ByteSize = VT.getStoreSize();
   Type *Ty = VT.getTypeForEVT(*getContext());
   unsigned StackAlign =
       std::max((unsigned)getDataLayout().getPrefTypeAlignment(Ty), minAlign);
 
-  int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false);
+  int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, isSS);
   return getFrameIndex(FrameIdx, TLI->getPointerTy(getDataLayout()));
 }
 
 /// CreateStackTemporary - Create a stack temporary suitable for holding
 /// either of the specified value types.
 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) {
   unsigned Bytes = std::max(VT1.getStoreSize(), VT2.getStoreSize());
   Type *Ty1 = VT1.getTypeForEVT(*getContext());

lib/CodeGen/SelectionDAG/StatepointLowering.cpp

for (int i = 0; i < 40000; i++) {
 
     if (NextSlotToAllocate >= NumSlots) {
       assert(NextSlotToAllocate == NumSlots);
       // record stats
       if (NumSlots + 1 > StatepointMaxSlotsRequired) {
         StatepointMaxSlotsRequired = NumSlots + 1;
       }
 
-      SDValue SpillSlot = Builder.DAG.CreateStackTemporary(ValueType);
+      SDValue SpillSlot = Builder.DAG.CreateStackTemporary(ValueType, 1, true);
       const unsigned FI = cast<FrameIndexSDNode>(SpillSlot)->getIndex();
       Builder.FuncInfo.StatepointStackSlots.push_back(FI);
       AllocatedStackSlots.push_back(true);
       return SpillSlot;
     }
     if (!AllocatedStackSlots[NextSlotToAllocate]) {
       const int FI = Builder.FuncInfo.StatepointStackSlots[NextSlotToAllocate];
       AllocatedStackSlots[NextSlotToAllocate] = true;
getIncomingStatepointGCValues(Bases, Ptrs, Relocations, StatepointSite,
                                 Builder);
 
 #ifndef NDEBUG
   // Check that each of the gc pointer and bases we've gotten out of the
   // safepoint is something the strategy thinks might be a pointer into the GC
   // heap.  This is basically just here to help catch errors during statepoint
   // insertion. TODO: This should actually be in the Verifier, but we can't get
   // to the GCStrategy from there (yet).
+  // TODO: This needs to become a predicate on the Type so we can call
+  // getScalarType here.  The current hack around for vectors needs fixed
+  // before submission.
   GCStrategy &S = Builder.GFI->getStrategy();
   for (const Value *V : Bases) {
+    if (V->getType()->isVectorTy())
+      continue;
     auto Opt = S.isGCManagedPointer(V);
     if (Opt.hasValue()) {
       assert(Opt.getValue() &&
              "non gc managed base pointer found in statepoint");
     }
   }
   for (const Value *V : Ptrs) {
+    if (V->getType()->isVectorTy())
+      continue;
     auto Opt = S.isGCManagedPointer(V);
     if (Opt.hasValue()) {
       assert(Opt.getValue() &&
              "non gc managed derived pointer found in statepoint");
     }
   }
   for (const Value *V : Relocations) {
+    if (V->getType()->isVectorTy())
+      continue;
     auto Opt = S.isGCManagedPointer(V);
     if (Opt.hasValue()) {
       assert(Opt.getValue() && "non gc managed pointer relocated");
     }
   }
 #endif
 
   // Before we actually start lowering (and allocating spill slots for values),

lib/CodeGen/TargetLoweringBase.cpp

 }
 
 /// Replace/modify any TargetFrameIndex operands with a targte-dependent
 /// sequence of memory operands that is recognized by PrologEpilogInserter.
 MachineBasicBlock*
 TargetLoweringBase::emitPatchPoint(MachineInstr *MI,
                                    MachineBasicBlock *MBB) const {
   MachineFunction &MF = *MI->getParent()->getParent();
+  const MachineFrameInfo &MFI = *MF.getFrameInfo();
 
   // MI changes inside this loop as we grow operands.
   for(unsigned OperIdx = 0; OperIdx != MI->getNumOperands(); ++OperIdx) {
     MachineOperand &MO = MI->getOperand(OperIdx);
     if (!MO.isFI())
       continue;
 
     // foldMemoryOperand builds a new MI after replacing a single FI operand
     // with the canonical set of five x86 addressing-mode operands.
     int FI = MO.getIndex();
     MachineInstrBuilder MIB = BuildMI(MF, MI->getDebugLoc(), MI->getDesc());
 
     // Copy operands before the frame-index.
     for (unsigned i = 0; i < OperIdx; ++i)
       MIB.addOperand(MI->getOperand(i));
-    // Add frame index operands: direct-mem-ref tag, #FI, offset.
+    // Add frame index operands recognized by stackmaps.cpp
+    if (MFI.isSpillSlotObjectIndex(FI)) {
+      // indirect-mem-ref tag, size, #FI, offset.
+      MIB.addImm(StackMaps::IndirectMemRefOp);
+      MIB.addImm(MFI.getObjectSize(FI));
+      MIB.addOperand(MI->getOperand(OperIdx));
+      MIB.addImm(0);
+    } else {
+      // direct-mem-ref tag, #FI, offset.
       MIB.addImm(StackMaps::DirectMemRefOp);
       MIB.addOperand(MI->getOperand(OperIdx));
       MIB.addImm(0);
+    }
     // Copy the operands after the frame index.
     for (unsigned i = OperIdx + 1; i != MI->getNumOperands(); ++i)
       MIB.addOperand(MI->getOperand(i));
 
     // Inherit previous memory operands.
     MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
     assert(MIB->mayLoad() && "Folded a stackmap use to a non-load!");
 
     // Add a new memory operand for this FI.
-    const MachineFrameInfo &MFI = *MF.getFrameInfo();
     assert(MFI.getObjectOffset(FI) != -1);
 
     unsigned Flags = MachineMemOperand::MOLoad;
     if (MI->getOpcode() == TargetOpcode::STATEPOINT) {
       Flags |= MachineMemOperand::MOStore;
       Flags |= MachineMemOperand::MOVolatile;
     }
     MachineMemOperand *MMO = MF.getMachineMemOperand(

lib/IR/Verifier.cpp

case Intrinsic::experimental_gc_result: {
     auto *TargetFuncType = cast<FunctionType>(PT->getElementType());
     Assert(CS.getType() == TargetFuncType->getReturnType(),
            "gc.result result type does not match wrapped callee", CS);
     break;
   }
   case Intrinsic::experimental_gc_relocate: {
     Assert(CS.getNumArgOperands() == 3, "wrong number of arguments", CS);
 
+    Assert(isa<PointerType>(CS.getType()->getScalarType()),
+           "gc.relocate must return a pointer or a vector of pointers", CS);
+
     // Check that this relocate is correctly tied to the statepoint
 
     // This is case for relocate on the unwinding path of an invoke statepoint
     if (ExtractValueInst *ExtractValue =
           dyn_cast<ExtractValueInst>(CS.getArgOperand(0))) {
       Assert(isa<LandingPadInst>(ExtractValue->getAggregateOperand()),
              "gc relocate on unwind path incorrectly linked to the statepoint",
              CS);
Assert(GCParamArgsStart <= BaseIndex && BaseIndex < GCParamArgsEnd,
            "gc.relocate: statepoint base index doesn't fall within the "
            "'gc parameters' section of the statepoint call",
            CS);
     Assert(GCParamArgsStart <= DerivedIndex && DerivedIndex < GCParamArgsEnd,
            "gc.relocate: statepoint derived index doesn't fall within the "
            "'gc parameters' section of the statepoint call",
            CS);
 
-    // Relocated value must be a pointer type, but gc_relocate does not need to return the
-    // same pointer type as the relocated pointer. It can be casted to the correct type later
-    // if it's desired. However, they must have the same address space.
+    // Relocated value must be either a pointer type or vector-of-pointer type,
+    // but gc_relocate does not need to return the same pointer type as the
+    // relocated pointer. It can be casted to the correct type later if it's
+    // desired. However, they must have the same address space and 'vectorness'. 
     GCRelocateOperands Operands(CS);
-    Assert(Operands.getDerivedPtr()->getType()->isPointerTy(),
+    Assert(Operands.getDerivedPtr()->getType()->getScalarType()->isPointerTy(),
            "gc.relocate: relocated value must be a gc pointer", CS);
 
-    // gc_relocate return type must be a pointer type, and is verified earlier in
-    // VerifyIntrinsicType().
-    Assert(cast<PointerType>(CS.getType())->getAddressSpace() ==
-           cast<PointerType>(Operands.getDerivedPtr()->getType())->getAddressSpace(),
+    auto ResultType = CS.getType();
+    auto DerivedType = Operands.getDerivedPtr()->getType();
+    Assert(ResultType->isVectorTy() == DerivedType->isVectorTy(),
+           "gc.relocate: vector relocates to vector and pointer to pointer", CS);
+    Assert(ResultType->getPointerAddressSpace() ==
+           DerivedType->getPointerAddressSpace(),
            "gc.relocate: relocating a pointer shouldn't change its address space", CS);
     break;
   }
   case Intrinsic::eh_exceptioncode:
   case Intrinsic::eh_exceptionpointer: {
     Assert(isa<CatchPadInst>(CS.getArgOperand(0)),
            "eh.exceptionpointer argument must be a catchpad", CS);
     break;