[InstCombine] Handle gc.relocate(null) in one iteration

[skatkov]

Summary

InstCombine adds users of transformed instruction to working list to
process on the same iteration. However gc.relocate may have a hidden
user (next gc.relocate) which is connected through gc.statepoint intrinsic and
there is no direct def-use chain between them.

In this case if the next gc.relocation is already processed it will not be added
to worklist and will not be able to be processed on the same iteration.
Let's we have the following case:
A = gc.relocate(null)
B = statepoint(A)
C = gc.relocate(B, hidden(A))
If C is already considered then after replacement of A with null, statepoint B
instruction will be added to the queue but not C.
C can be processed only on the next iteration.

If the chain of relocation is pretty long the many iteration may be required.
This change is to reduce the number of iteration to meet the latest changes
related to reducing infinite loop threshold.

This is a quick (not best) fix. In the follow up patches I plan to move gc relocation
handling into statepoint handler. This should also help to remove unused gc live
entries in statepoint bundle.

[skatkov]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

1818

safe -> save.

[dantrushin]

Can gc.relocate(null) be constant folded? I quickly glanced over code and it seems it's not. Could you double-check it?
After quick look through initial worklist construction in AddReachableCodeToWorklist from Transforms/InstCombine/InstructionCombining.cpp, it seems to me that if gc.relocate(null) was constant folded, this problem would not exist.
Am I missed something here?

[reames]

I don't think this is quite the right factoring, for two reasons:

1. This applies to the other gc_relocate transforms as well (e.g. undef, non-null, etc..)
2. This applies in the other direction to a chain of dead gc.relocates. (Actually, it looks like we don't recurse the chain at all?)

I'm not sure on the right approach here. One idea would be to add a gc_statepoint case to the intrinsic switch and phrase many of these transforms as a change to the statepoint operand list. (i.e. we can remove null, undef, and duplicate entries and thus have to renumber gc.relocates.)

One way to think about it is that the "statepoint" is really the whole sequence. And as a result, we're not doing a transform on one instruction at a time, but the whole "unit" of instructions. Not sure I really like that though.

[skatkov]

Need to think about other approach

[skatkov]

I've updated the patch, please take a look.

[reames]

LGTM

Serguei and I discussed this one fairly extensively offline. Long term, we're probably going to move to a model where we process all of the projections for a statepoint in a single pass when visiting the statepoint, but for the moment, we need to decrease the number of instcombine iterations. In particular, with recent efforts to clamp the number of iterations in debug builds, we are seeing R+A crashes in downstream tests, so this change is really a regression fix.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::assume: {
     if (Known.isAllOnes() && isAssumeWithEmptyBundle(*II))
       return eraseInstFromFunction(*II);
 
     // Update the cache of affected values for this assumption (we might be
     // here because we just simplified the condition).
     AC.updateAffectedValues(II);
     break;
   }
+  case Intrinsic::experimental_gc_statepoint: {
+    auto &GCSP = *cast<GCStatepointInst>(II);
+    // Let's we have the following case:
+    // A = gc.relocate(null)
+    // B = statepoint(A)
+    // C = gc.relocate(A)
+    // A will be substituted with null and its user B will be added to worklist.
+    // Statepoint B is not simplified and if C was considered before it will be
+    // re-considered after simplification of A.
+    // To resolve this case while processing statepoint B we add all gc.relocate
+    // users to worklist to give a chance to be simplified to null.
+    // This is to reduce the number of InstCombine iteration.
+    // Actually C can be transformed on the next iteration.
+    // chains in one iteration.
+    // TODO: we can handle relocation here, it will reduce the number of
+    // relocations to re-consider and also helps to reduce the number of
+    // gc live pointers in statepoint instruction bundle.
+    for (const GCRelocateInst *Reloc : GCSP.getGCRelocates())
+      Worklist.add(const_cast<GCRelocateInst *>(Reloc));
+    break;
+  }
   case Intrinsic::experimental_gc_relocate: {
     auto &GCR = *cast<GCRelocateInst>(II);
 
     // If we have two copies of the same pointer in the statepoint argument
     // list, canonicalize to one.  This may let us common gc.relocates.
     if (GCR.getBasePtr() == GCR.getDerivedPtr() &&
         GCR.getBasePtrIndex() != GCR.getDerivedPtrIndex()) {
       auto *OpIntTy = GCR.getOperand(2)->getType();
Instruction *InstCombinerImpl::visitCallBase(CallBase &Call) {
 
   bool Changed = false;
 
   // Mark any parameters that are known to be non-null with the nonnull
   // attribute.  This is helpful for inlining calls to functions with null
   // checks on their arguments.
   SmallVector<unsigned, 4> ArgNos;
   unsigned ArgNo = 0;
 
   for (Value *V : Call.args()) {
     if (V->getType()->isPointerTy() &&
         !Call.paramHasAttr(ArgNo, Attribute::NonNull) &&
         isKnownNonZero(V, DL, 0, &AC, &Call, &DT))
       ArgNos.push_back(ArgNo);
     ArgNo++;
   }
 

llvm/test/Transforms/InstCombine/statepoint-iter.ll

+; RUN: opt < %s -instcombine -instcombine-max-iterations=1 -S | FileCheck %s
+; These tests check the optimizations specific to
+; pointers being relocated at a statepoint.
+
+
+declare void @func()
+
+define i1 @test_null(i1 %cond) gc "statepoint-example" {
+entry:
+  br i1 %cond, label %left, label %right
+
+right:
+  br label %merge
+
+left:
+  %safepoint_token = tail 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* null)
+  %pnew = call i32* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 7)
+  br label %merge
+
+merge:
+  %pnew_phi = phi i32* [null, %right], [%pnew, %left]
+  %safepoint_token2 = tail 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* %pnew_phi)
+  %pnew2 = call i32* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 7)
+  %cmp = icmp eq i32* %pnew2, null
+  ret i1 %cmp
+; CHECK-LABEL: test_null
+; CHECK-NOT: %pnew
+; CHECK-NOT: %pnew2
+; CHECK: ret i1 true
+}
+
+define i32* @test_undef(i1 %cond) gc "statepoint-example" {
+entry:
+  br i1 %cond, label %left, label %right
+
+right:
+  br label %merge
+
+left:
+  %safepoint_token = tail 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* undef)
+  %pnew = call i32* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token,  i32 7, i32 7)
+  br label %merge
+
+merge:
+  %pnew_phi = phi i32* [undef, %right], [%pnew, %left]
+  %safepoint_token2 = tail 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* %pnew_phi)
+  %pnew2 = call i32* @llvm.experimental.gc.relocate.p1i32(token %safepoint_token2,  i32 7, i32 7)
+  ret i32* %pnew2
+; CHECK-LABEL: test_undef
+; CHECK-NOT: %pnew
+; CHECK-NOT: %pnew2
+; CHECK: ret i32* undef
+}
+
+declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
+declare i32* @llvm.experimental.gc.relocate.p1i32(token, i32, i32)