[gvn] CSE gc.relocates based on meaning, not spelling

[reames]

Summary

The last two operands to a gc.relocate represent indices into the associated gc.statepoint's gc bundle list. (Effectively, gc.relocates are projections from the gc.statepoints multiple return values.)

We can use this to recognize when two gc.relocates are equivalent (and can be CSEd), even when the indices are non-equal. This is particular useful when considering a chain of multiple statepoints as it lets us eliminate all duplicate gc.relocates in a single pass.

The meat of the change isn't actually in GVN. For some reason, we had been marking gc.relocates as reading memory. This change undoes that. I believe this to be a legacy of very early implementation conservatism, but a skeptical view is appreciated. (The EarlyCSE change is simply moving the special casing from readonly to readnone handling.)

[skatkov]

LGTM but please separate GVN and EarlyCSE changes.

[reames]

A bit of follow up here. This was reverted in cfe8f8e0f0 because the readnone changes exposed a couple of problems.

First, Serguei hit a couple of bugs in the lowering for statepoints which code movement exposed. These were fixed by D98324, and D98393 respectively. Both issues could in theory have occurred without the readnone change, but became much more common afterwards.

Second, Serguei hit an issue w/LICM sinking gc.relocates and gc.results out of loops, creating phis of token type (which are illegal). I'm going to explore a fix for this once I more fully understand the issue, but in the meantime, Serguei reverted the original change as we seem to keep hitting more issues.

To be clear, I support Serguei's revert and think it's fully justified given the multiple issues found. We'll revisit and try to reapply once exposed issues have all been fixed.

[reames]

FYI, I filed https://bugs.llvm.org/show_bug.cgi?id=49607 for tracking try two at this.

llvm/lib/Transforms/Scalar/GVN.cpp

 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Statepoint.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"

 //===----------------------------------------------------------------------===//
 //                     ValueTable Internal Functions
 //===----------------------------------------------------------------------===//
 
 GVN::Expression GVN::ValueTable::createExpr(Instruction *I) {
   Expression e;
   e.type = I->getType();
   e.opcode = I->getOpcode();
+  if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(I)) {
+    // gc.relocate is 'special' call: its second and third operands are
+    // not real values, but indices into statepoint's argument list.
+    // Use the refered to values for purposes of identity.
+    e.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
+    e.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
+    e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
+  } else {
     for (Use &Op : I->operands())
       e.varargs.push_back(lookupOrAdd(Op));
+  }
   if (I->isCommutative()) {
     // Ensure that commutative instructions that only differ by a permutation
     // of their operands get the same value number by sorting the operand value
     // numbers.  Since commutative operands are the 1st two operands it is more
     // efficient to sort by hand rather than using, say, std::sort.
     assert(I->getNumOperands() >= 2 && "Unsupported commutative instruction!");
     if (e.varargs[0] > e.varargs[1])
       std::swap(e.varargs[0], e.varargs[1]);

llvm/test/Transforms/GVN/gc_relocate.ll

entry:
   ret i1 %cmp
 }
 
 define i1 @test_call(i32 addrspace(1)* %in) gc "statepoint-example" {
 ; CHECK-LABEL: @test_call(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[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) [ "gc-live"(i32 addrspace(1)* [[IN:%.*]], i32 addrspace(1)* [[IN]]) ]
 ; CHECK-NEXT:    [[BASE:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 0)
-; CHECK-NEXT:    [[DERIVED:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 0, i32 1)
-; CHECK-NEXT:    [[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) [ "gc-live"(i32 addrspace(1)* [[BASE]], i32 addrspace(1)* [[DERIVED]]) ]
+; CHECK-NEXT:    [[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) [ "gc-live"(i32 addrspace(1)* [[BASE]], i32 addrspace(1)* [[BASE]]) ]
 ; CHECK-NEXT:    [[BASE_RELOC:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 0, i32 0)
-; CHECK-NEXT:    [[DERIVED_RELOC:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 0, i32 1)
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 addrspace(1)* [[BASE_RELOC]], null
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 addrspace(1)* [[DERIVED_RELOC]], null
-; CHECK-NEXT:    [[CMP:%.*]] = and i1 [[CMP1]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[CMP]]
+; CHECK-NEXT:    ret i1 [[CMP1]]
 ;
 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) ["gc-live"(i32 addrspace(1)* %in, i32 addrspace(1)* %in)]
   %base = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 0)
   %derived = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 0, i32 1)
   %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) ["gc-live"(i32 addrspace(1)* %base, i32 addrspace(1)* %derived)]
   br label %next