[EarlyCSE] Common gc.relocate calls.

[dantrushin]

Summary

gc.relocate intrinsic is special in that its second and third operands
are not real values, but indices into relocate's parent statepoint list
of GC pointers.
To be CSE'd, they need special handling in isEqual() and getHashCode().

[dantrushin]

Remove debug leftover

[reames]

Just to be clear, if the indices are the same, gc.relocates would already be removed right? i.e. the thing you're trying to solve is that the standpoint can have two operands which are the same value and thus two gc.relocates which are equivalent but not textually identical? Just want to make sure I understand the problem properly.

Another solution to the same problem would be to canonicalize the statepoint in an instcombine rule to avoid duplicate operands in the gc operand section. Have you explored that possibility?

[dantrushin]

In D80445#2051699, @reames wrote:

Just to be clear, if the indices are the same, gc.relocates would already be removed right? i.e. the thing you're trying to solve is that the standpoint can have two operands which are the same value and thus two gc.relocates which are equivalent but not textually identical? Just want to make sure I understand the problem properly.

That's right.

Another solution to the same problem would be to canonicalize the statepoint in an instcombine rule to avoid duplicate operands in the gc operand section. Have you explored that possibility?

Well, CSE solution looked to me more elegant - all I need is adjust hash and the rest will be done automatically.
While in instcombine after statepoint operand uniqueing I would have to visit all relocates and update them. Second logical step would be to implement gc.relocate CSE'ing there which I didn't want to do.
And operand uniqueing itself is sort of CSE, so I would need to implement it in InstCombine using some sort of Set etc.

Also, operands might be equivalent, but not textually identical, which InstCombine cannot handle.
(I'm not sure if LLVM's CSE can. This sounds as value numbering).

[reames]

LGTM

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

 //===- EarlyCSE.cpp - Simple and fast CSE pass ----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass performs a simple dominator tree walk that eliminates trivially

 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.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/Allocator.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Casting.h"
template <> struct DenseMapInfo<CallValue> {
   static unsigned getHashValue(CallValue Val);
   static bool isEqual(CallValue LHS, CallValue RHS);
 };
 
 } // end namespace llvm
 
 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
   Instruction *Inst = Val.Inst;
+
+  // gc.relocate is 'special' call: its second and third operands are
+  // not real values, but indices into statepoint's argument list.
+  // Get values they point to.
+  if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(Inst))
+    return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
+                        GCR->getBasePtr(), GCR->getDerivedPtr());
+
   // Hash all of the operands as pointers and mix in the opcode.
   return hash_combine(
       Inst->getOpcode(),
       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
 }
 
 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
   if (LHS.isSentinel() || RHS.isSentinel())
     return LHSI == RHSI;
+
+  // See comment above in `getHashValue()`.
+  if (const GCRelocateInst *GCR1 = dyn_cast<GCRelocateInst>(LHSI))
+    if (const GCRelocateInst *GCR2 = dyn_cast<GCRelocateInst>(RHSI))
+      return GCR1->getOperand(0) == GCR2->getOperand(0) &&
+             GCR1->getBasePtr() == GCR2->getBasePtr() &&
+             GCR1->getDerivedPtr() == GCR2->getDerivedPtr();
+
   return LHSI->isIdenticalTo(RHSI);
 }
 
 //===----------------------------------------------------------------------===//
 // EarlyCSE implementation
 //===----------------------------------------------------------------------===//
 
 namespace {

llvm/test/Transforms/EarlyCSE/gc_relocate.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -early-cse -S < %s | FileCheck %s
+
+declare void @func()
+declare i32 @"personality_function"()
+
+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, i32 addrspace(1)* [[IN:%.*]], i32 addrspace(1)* [[IN]])
+; CHECK-NEXT:    [[BASE:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 7, i32 7)
+; 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, i32 addrspace(1)* [[BASE]], i32 addrspace(1)* [[BASE]])
+; CHECK-NEXT:    br label [[NEXT:%.*]]
+; CHECK:       next:
+; CHECK-NEXT:    [[BASE_RELOC:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 7, i32 7)
+;
+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)* %in, i32 addrspace(1)* %in)
+  %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
+}
+
+; Negative test: Check that relocates from different statepoints are not CSE'd
+define i1 @test_two_calls(i32 addrspace(1)* %in1, i32 addrspace(1)* %in2) gc "statepoint-example" {
+; CHECK-LABEL: @test_two_calls(
+; 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, i32 addrspace(1)* [[IN1:%.*]], i32 addrspace(1)* [[IN2:%.*]])
+; CHECK-NEXT:    [[IN1_RELOC1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 7, i32 7)
+; CHECK-NEXT:    [[IN2_RELOC1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 8, i32 8)
+; 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, i32 addrspace(1)* [[IN1_RELOC1]], i32 addrspace(1)* [[IN2_RELOC1]])
+; CHECK-NEXT:    [[IN1_RELOC2:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 7, i32 7)
+; CHECK-NEXT:    [[IN2_RELOC2:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN2]], i32 7, i32 8)
+;
+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)* %in1, i32 addrspace(1)* %in2)
+  %in1.reloc1 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 7)
+  %in2.reloc1 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 8, 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)* %in1.reloc1, i32 addrspace(1)* %in2.reloc1)
+  %in1.reloc2 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 7)
+  %in2.reloc2 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 8)
+  %cmp1 = icmp eq i32 addrspace(1)* %in1.reloc2, null
+  %cmp2 = icmp eq i32 addrspace(1)* %in2.reloc2, null
+  %cmp = and i1 %cmp1, %cmp2
+  ret i1 %cmp
+}
+
+; Negative test: Check that relocates from normal and exceptional pathes are not be CSE'd
+define i32 addrspace(1)* @test_invoke(i32 addrspace(1)* %in) gc "statepoint-example" personality i32 ()* @"personality_function" {
+; CHECK-LABEL: @test_invoke(
+; CHECK-NEXT:    [[SAFEPOINT_TOKEN:%.*]] = invoke 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)* [[IN:%.*]])
+; CHECK-NEXT:    to label [[INVOKE_NORMAL_DEST:%.*]] unwind label [[EXCEPTIONAL_RETURN:%.*]]
+; CHECK:       invoke_normal_dest:
+; CHECK-NEXT:    [[OUT:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[SAFEPOINT_TOKEN]], i32 7, i32 7)
+; CHECK-NEXT:    ret i32 addrspace(1)* [[OUT]]
+; CHECK:       exceptional_return:
+; CHECK-NEXT:    [[LANDING_PAD:%.*]] = landingpad token
+; CHECK-NEXT:    cleanup
+; CHECK-NEXT:    [[OUT1:%.*]] = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token [[LANDING_PAD]], i32 7, i32 7)
+; CHECK-NEXT:    ret i32 addrspace(1)* [[OUT1]]
+;
+  %safepoint_token = invoke 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)* %in)
+  to label %invoke_normal_dest unwind label %exceptional_return
+
+invoke_normal_dest:
+  %out = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 7)
+  ret i32 addrspace(1)* %out
+
+exceptional_return:
+  %landing_pad = landingpad token
+  cleanup
+  %out1 = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(token %landing_pad, i32 7, i32 7)
+  ret i32 addrspace(1)* %out1
+}
+
+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)