[GC] Remove buggy untested optimization from statepoint lowering

[reames]

Summary

A downstream test case (still in the process of being properly reduced, will be added here) revealed that we have a bug in how we handle duplicate relocations. If we have the same SDValue relocated twice, and that value happens to be a constant (such as null), we only export one of the two llvm::Values. Exporting on a per llvm::Value basis is required to allow lowering of gc.relocates in following basic blocks (e.g. invokes). Without it, we end up with a use of an undefined vreg and bad things happen.

Rather than fixing the optimization - which appears to be hard - I propose we simply remove it. There are no tests in tree that change with this code removed. If we find out later that this did matter for something, we can reimplement a variation of this in CodeGenPrepare to catch the easy cases without complicating the lowering code.

Thanks to Denis and Serguei who did all the hard work of figuring out what went wrong here. The patch is by far the easy part. :)

[skatkov]

Here is a simple test showing the problem:

; RUN: llc < %s -verify-machineinstrs

declare void @func()

define i1 @test() gc "statepoint-example" {
entry:
  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* null, i32 addrspace(1)* null)
  %base = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 7)
  %derived = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 8)
  %safepoint_token2 = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %base, i32 addrspace(1)* %derived)
  br label %next

next:
  %base_reloc = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 7)
  %derived_reloc = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 8)
  %cmp1 = icmp eq i32 addrspace(1)* %base_reloc, null
  %cmp2 = icmp eq i32 addrspace(1)* %derived_reloc, null
  %cmp = and i1 %cmp1, %cmp2
  ret i1 %cmp
}

declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
declare i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token, i32, i32) #3

[skatkov]

without this patch I get the following crash (which disappears with it):

# After Instruction Selection
# Machine code for function test: IsSSA, TracksLiveness

bb.0.entry:
  successors: %bb.1(0x80000000); %bb.1(100.00%)

  ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
  STATEPOINT 0, 0, 0, @func, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, <regmask $bh $bl $bp $bph $bpl $bx $ebp $ebx $hbp $hbx $rbp $rbx $r12 $r13 $r14 $r15 $r12b $r13b $r14b $r15b $r12bh $r13bh $r14bh $r15bh $r12d $r13d $r14d $r15d $r12w $r13w $r14w $r15w $r12wh and 3 more...>, implicit-def $rsp, implicit-def $ssp
  ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
  ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
  STATEPOINT 0, 0, 0, @func, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, <regmask $bh $bl $bp $bph $bpl $bx $ebp $ebx $hbp $hbx $rbp $rbx $r12 $r13 $r14 $r15 $r12b $r13b $r14b $r15b $r12bh $r13bh $r14bh $r15bh $r12d $r13d $r14d $r15d $r12w $r13w $r14w $r15w $r12wh and 3 more...>, implicit-def $rsp, implicit-def $ssp
  ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
  %1:gr32 = MOV32r0 implicit-def dead $eflags
  %0:gr64 = SUBREG_TO_REG 0, killed %1:gr32, %subreg.sub_32bit

bb.1.next:
; predecessors: %bb.0

  TEST64rr %2:gr64, %2:gr64, implicit-def $eflags
  %3:gr8 = SETCCr 4, implicit $eflags
  $al = COPY %3:gr8
  RET 0, $al

# End machine code for function test.

*** Bad machine code: Reading virtual register without a def ***
- function:    test
- basic block: %bb.1 next (0x1dc1350)
- instruction: TEST64rr %2:gr64, %2:gr64, implicit-def $eflags
- operand 0:   %2:gr64

*** Bad machine code: Reading virtual register without a def ***
- function:    test
- basic block: %bb.1 next (0x1dc1350)
- instruction: TEST64rr %2:gr64, %2:gr64, implicit-def $eflags
- operand 1:   %2:gr64
LLVM ERROR: Found 2 machine code errors.
Stack dump:
0.      Program arguments: /localhome/skatkov/work/llvm/build/buildDA/bin/llc -verify-machineinstrs
1.      Running pass 'Function Pass Manager' on module '<stdin>'.
2.      Running pass 'Verify generated machine code' on function '@test'
 #0 0x00007fb96b956360 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /localhome/skatkov/work/llvm/src/llvm/lib/Support/Unix/Signals.inc:564:0
 #1 0x00007fb96b9563f3 PrintStackTraceSignalHandler(void*) /localhome/skatkov/work/llvm/src/llvm/lib/Support/Unix/Signals.inc:625:0
 #2 0x00007fb96b954484 llvm::sys::RunSignalHandlers() /localhome/skatkov/work/llvm/src/llvm/lib/Support/Signals.cpp:68:0
 #3 0x00007fb96b955d9f SignalHandler(int) /localhome/skatkov/work/llvm/src/llvm/lib/Support/Unix/Signals.inc:406:0
 #4 0x00007fb968cc25d0 __restore_rt (/lib64/libpthread.so.0+0xf5d0)
 #5 0x00007fb96806b2c7 raise (/lib64/libc.so.6+0x362c7)
 #6 0x00007fb96806c9b8 abort (/lib64/libc.so.6+0x379b8)
 #7 0x00007fb96b80f9ea llvm::install_bad_alloc_error_handler(void (*)(void*, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, bool), void*) /localhome/skatkov/work/llvm/src/llvm/lib/Support/ErrorHandling.cpp:130:0
 #8 0x00007fb96bffe29d (anonymous namespace)::MachineVerifierPass::runOnMachineFunction(llvm::MachineFunction&) /localhome/skatkov/work/llvm/src/llvm/lib/CodeGen/MachineVerifier.cpp:294:0

[dantrushin]

LGTM.
I think, doing this in CodeGenPrepare is a good idea.

llvm/include/llvm/CodeGen/FunctionLoweringInfo.h

public:
   /// This method is called from TargetLowerinInfo::isSDNodeSourceOfDivergence
   /// to get the Value corresponding to the live-in virtual register.
   const Value * getValueFromVirtualReg(unsigned Vreg);
 
   /// Track virtual registers created for exception pointers.
   DenseMap<const Value *, unsigned> CatchPadExceptionPointers;
 
   /// Keep track of frame indices allocated for statepoints as they could be
-  /// used across basic block boundaries.  This struct is more complex than a
-  /// simple map because the stateopint lowering code de-duplicates gc pointers
-  /// based on their SDValue (so %p and (bitcast %p to T) will get the same
-  /// slot), and we track that here.
-
-  struct StatepointSpillMap {
-    using SlotMapTy = DenseMap<const Value *, Optional<int>>;
-
-    /// Maps uniqued llvm IR values to the slots they were spilled in.  If a
-    /// value is mapped to None it means we visited the value but didn't spill
-    /// it (because it was a constant, for instance).
-    SlotMapTy SlotMap;
-
-    /// Maps llvm IR values to the values they were de-duplicated to.
-    DenseMap<const Value *, const Value *> DuplicateMap;
-
-    SlotMapTy::const_iterator find(const Value *V) const {
-      auto DuplIt = DuplicateMap.find(V);
-      if (DuplIt != DuplicateMap.end())
-        V = DuplIt->second;
-      return SlotMap.find(V);
-    }
-
-    SlotMapTy::const_iterator end() const { return SlotMap.end(); }
-  };
-
-  /// Maps gc.statepoint instructions to their corresponding StatepointSpillMap
-  /// instances.
-  DenseMap<const Instruction *, StatepointSpillMap> StatepointSpillMaps;
+  /// used across basic block boundaries (e.g. for an invoke).  For each
+  /// gc.statepoint instruction, maps uniqued llvm IR values to the slots they
+  /// were spilled in.  If a value is mapped to None it means we visited the
+  /// value but didn't spill it (because it was a constant, for instance). 
+  using StatepointSpillMapTy = DenseMap<const Value *, Optional<int>>;
+  DenseMap<const Instruction *, StatepointSpillMapTy> StatepointSpillMaps;
 
   /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in
   /// the entry block.  This allows the allocas to be efficiently referenced
   /// anywhere in the function.
   DenseMap<const AllocaInst*, int> StaticAllocaMap;
 
   /// ByValArgFrameIndexMap - Keep track of frame indices for byval arguments.
   DenseMap<const Argument*, int> ByValArgFrameIndexMap;

llvm/lib/CodeGen/SelectionDAG/StatepointLowering.cpp

static void reservePreviousStackSlotForValue(const Value *IncomingValue,
 
   // Cache this slot so we find it when going through the normal
   // assignment loop.
   SDValue Loc =
       Builder.DAG.getTargetFrameIndex(*Index, Builder.getFrameIndexTy());
   Builder.StatepointLowering.setLocation(Incoming, Loc);
 }
 
-/// Remove any duplicate (as SDValues) from the derived pointer pairs.  This
-/// is not required for correctness.  It's purpose is to reduce the size of
-/// StackMap section.  It has no effect on the number of spill slots required
-/// or the actual lowering.
-static void
-removeDuplicateGCPtrs(SmallVectorImpl<const Value *> &Bases,
-                      SmallVectorImpl<const Value *> &Ptrs,
-                      SmallVectorImpl<const GCRelocateInst *> &Relocs,
-                      SelectionDAGBuilder &Builder,
-                      FunctionLoweringInfo::StatepointSpillMap &SSM) {
-  DenseMap<SDValue, const Value *> Seen;
-
-  SmallVector<const Value *, 64> NewBases, NewPtrs;
-  SmallVector<const GCRelocateInst *, 64> NewRelocs;
-  for (size_t i = 0, e = Ptrs.size(); i < e; i++) {
-    SDValue SD = Builder.getValue(Ptrs[i]);
-    auto SeenIt = Seen.find(SD);
-
-    if (SeenIt == Seen.end()) {
-      // Only add non-duplicates
-      NewBases.push_back(Bases[i]);
-      NewPtrs.push_back(Ptrs[i]);
-      NewRelocs.push_back(Relocs[i]);
-      Seen[SD] = Ptrs[i];
-    } else {
-      // Duplicate pointer found, note in SSM and move on:
-      SSM.DuplicateMap[Ptrs[i]] = SeenIt->second;
-    }
-  }
-  assert(Bases.size() >= NewBases.size());
-  assert(Ptrs.size() >= NewPtrs.size());
-  assert(Relocs.size() >= NewRelocs.size());
-  Bases = NewBases;
-  Ptrs = NewPtrs;
-  Relocs = NewRelocs;
-  assert(Ptrs.size() == Bases.size());
-  assert(Ptrs.size() == Relocs.size());
-}
-
 /// Extract call from statepoint, lower it and return pointer to the
 /// call node. Also update NodeMap so that getValue(statepoint) will
 /// reference lowered call result
 static std::pair<SDValue, SDNode *> lowerCallFromStatepointLoweringInfo(
     SelectionDAGBuilder::StatepointLoweringInfo &SI,
     SelectionDAGBuilder &Builder, SmallVectorImpl<SDValue> &PendingExports) {
   SDValue ReturnValue, CallEndVal;
   std::tie(ReturnValue, CallEndVal) =
#endif
   auto &SpillMap = Builder.FuncInfo.StatepointSpillMaps[StatepointInstr];
 
   for (const GCRelocateInst *Relocate : SI.GCRelocates) {
     const Value *V = Relocate->getDerivedPtr();
     SDValue SDV = Builder.getValue(V);
     SDValue Loc = Builder.StatepointLowering.getLocation(SDV);
 
     if (Loc.getNode()) {
-      SpillMap.SlotMap[V] = cast<FrameIndexSDNode>(Loc)->getIndex();
+      SpillMap[V] = cast<FrameIndexSDNode>(Loc)->getIndex();
     } else {
       // Record value as visited, but not spilled. This is case for allocas
       // and constants. For this values we can avoid emitting spill load while
       // visiting corresponding gc_relocate.
       // Actually we do not need to record them in this map at all.
       // We do this only to check that we are not relocating any unvisited
       // value.
-      SpillMap.SlotMap[V] = None;
+      SpillMap[V] = None;
 
       // Default llvm mechanisms for exporting values which are used in
       // different basic blocks does not work for gc relocates.
       // Note that it would be incorrect to teach llvm that all relocates are
       // uses of the corresponding values so that it would automatically
       // export them. Relocates of the spilled values does not use original
       // value.
       if (Relocate->getParent() != StatepointInstr->getParent())
         Builder.ExportFromCurrentBlock(V);
     }
   }
 }
 
 SDValue SelectionDAGBuilder::LowerAsSTATEPOINT(
     SelectionDAGBuilder::StatepointLoweringInfo &SI) {
   // The basic scheme here is that information about both the original call and
   // the safepoint is encoded in the CallInst.  We create a temporary call and
   // lower it, then reverse engineer the calling sequence.
 
   NumOfStatepoints++;
   // Clear state
   StatepointLowering.startNewStatepoint(*this);
+  assert(SI.Bases.size() == SI.Ptrs.size() &&
+         SI.Ptrs.size() == SI.GCRelocates.size());
 
 #ifndef NDEBUG
-  // We schedule gc relocates before removeDuplicateGCPtrs since we _will_
-  // encounter the duplicate gc relocates we elide in removeDuplicateGCPtrs.
   for (auto *Reloc : SI.GCRelocates)
     if (Reloc->getParent() == SI.StatepointInstr->getParent())
       StatepointLowering.scheduleRelocCall(*Reloc);
 #endif
 
-  // Remove any redundant llvm::Values which map to the same SDValue as another
-  // input.  Also has the effect of removing duplicates in the original
-  // llvm::Value input list as well.  This is a useful optimization for
-  // reducing the size of the StackMap section.  It has no other impact.
-  removeDuplicateGCPtrs(SI.Bases, SI.Ptrs, SI.GCRelocates, *this,
-                        FuncInfo.StatepointSpillMaps[SI.StatepointInstr]);
-  assert(SI.Bases.size() == SI.Ptrs.size() &&
-         SI.Ptrs.size() == SI.GCRelocates.size());
-
   // Lower statepoint vmstate and gcstate arguments
   SmallVector<SDValue, 10> LoweredMetaArgs;
   SmallVector<MachineMemOperand*, 16> MemRefs;
   lowerStatepointMetaArgs(LoweredMetaArgs, MemRefs, SI, *this);
 
   // Now that we've emitted the spills, we need to update the root so that the
   // call sequence is ordered correctly.
   SI.CLI.setChain(getRoot());

llvm/test/CodeGen/X86/statepoint-duplicates-export.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc  -verify-machineinstrs < %s | FileCheck %s
+
+; Check that we can export values of "duplicated" gc.relocates without a crash
+; "duplicate" here means maps to same SDValue.  We previously had an
+; optimization which tried to reduce number of spills/stackmap entries in such
+; cases, but it incorrectly handled exports across basis block boundaries
+; leading to a crash in this case.
+
+target triple = "x86_64-pc-linux-gnu"
+
+declare void @func()
+
+define i1 @test() gc "statepoint-example" {
+; CHECK-LABEL: test:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    pushq %rax
+; CHECK-NEXT:    .cfi_def_cfa_offset 16
+; CHECK-NEXT:    callq func
+; CHECK-NEXT:  .Ltmp0:
+; CHECK-NEXT:    callq func
+; CHECK-NEXT:  .Ltmp1:
+; CHECK-NEXT:    movb $1, %al
+; CHECK-NEXT:    popq %rcx
+; CHECK-NEXT:    .cfi_def_cfa_offset 8
+; CHECK-NEXT:    retq
+entry:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* null, i32 addrspace(1)* null)
+  %base = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 7)
+  %derived = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 8)
+  %safepoint_token2 = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %base, i32 addrspace(1)* %derived)
+  br label %next
+
+next:
+  %base_reloc = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 7)
+  %derived_reloc = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 8)
+  %cmp1 = icmp eq i32 addrspace(1)* %base_reloc, null
+  %cmp2 = icmp eq i32 addrspace(1)* %derived_reloc, null
+  %cmp = and i1 %cmp1, %cmp2
+  ret i1 %cmp
+}
+
+; Showing redundant fill on first statepoint and spill/fill on second one
+define i1 @test2(i32 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: test2:
+; CHECK:       # %bb.0: # %entry
+; CHECK-NEXT:    subq $24, %rsp
+; CHECK-NEXT:    .cfi_def_cfa_offset 32
+; CHECK-NEXT:    movq %rdi, {{[0-9]+}}(%rsp)
+; CHECK-NEXT:    callq func
+; CHECK-NEXT:  .Ltmp2:
+; CHECK-NEXT:    movq {{[0-9]+}}(%rsp), %rax
+; CHECK-NEXT:    movq %rax, {{[0-9]+}}(%rsp)
+; CHECK-NEXT:    callq func
+; CHECK-NEXT:  .Ltmp3:
+; CHECK-NEXT:    movq {{[0-9]+}}(%rsp), %rax
+; CHECK-NEXT:    orq {{[0-9]+}}(%rsp), %rax
+; CHECK-NEXT:    sete %al
+; CHECK-NEXT:    addq $24, %rsp
+; CHECK-NEXT:    .cfi_def_cfa_offset 8
+; CHECK-NEXT:    retq
+entry:
+  %safepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %arg, i32 addrspace(1)* %arg)
+  %base = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 7)
+  %derived = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 8)
+  %safepoint_token2 = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 0, i32 0, void ()* @func, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %base, i32 addrspace(1)* %derived)
+  br label %next
+
+next:
+  %base_reloc = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 7)
+  %derived_reloc = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 8)
+  %cmp1 = icmp eq i32 addrspace(1)* %base_reloc, null
+  %cmp2 = icmp eq i32 addrspace(1)* %derived_reloc, null
+  %cmp = and i1 %cmp1, %cmp2
+  ret i1 %cmp
+}
+
+
+declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
+declare i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token, i32, i32)