[InstCombine] Move handling of gc.relocate in a gc.statepoint

[skatkov]

Summary

The only def for gc.relocate is a gc.statepoint. But real dependency is not
described by def-use chain. Instead this dependency is encoded by indecies
of operands in gc-live bundle of statepoint as integer constants in gc.relocate.

InstCombine operates by def-use chain. As a result when value in gc-live bundle
is simplified the gc.statepoint itself is not simplified but it might simplify dependent
gc.relocates. To trigger the optimization of gc.relocate we now unconditionally trigger
check of all dependent gc.relocates by adding them to worklist.

This CL handles of gc.relocates as process of gc.statepoint optimization considering
gc.statepoint and related gc.relocate as whole entity.

[skatkov]

ping

[reames]

LGTM

As a follow up, it would be nice to handle two additional optimizations:

1. Canonicalize each pointer to a single index in the statepoint operand list
2. Shrink the gc-live bundle to remove any pointers not needed after (1)

[skatkov]

In D85954#2230604, @reames wrote:

LGTM

As a follow up, it would be nice to handle two additional optimizations:

1. Canonicalize each pointer to a single index in the statepoint operand list
2. Shrink the gc-live bundle to remove any pointers not needed after (1)

See https://reviews.llvm.org/D85959.

Thank you for review.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::assume: {
 
     // 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);
+    for (const GCRelocateInst *Reloc : GCSP.getGCRelocates()) {
+      GCRelocateInst &GCR = *const_cast<GCRelocateInst *>(Reloc);
 
-    // 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();
-      return replaceOperand(*II, 2,
-          ConstantInt::get(OpIntTy, GCR.getBasePtrIndex()));
+      // Remove the relocation if unused.
+      if (GCR.use_empty()) {
+        eraseInstFromFunction(GCR);
+        continue;
       }
 
-    // Translate facts known about a pointer before relocating into
-    // facts about the relocate value, while being careful to
-    // preserve relocation semantics.
       Value *DerivedPtr = GCR.getDerivedPtr();
-
-    // Remove the relocation if unused, note that this check is required
-    // to prevent the cases below from looping forever.
-    if (II->use_empty())
-      return eraseInstFromFunction(*II);
+      Value *BasePtr = GCR.getBasePtr();
 
       // Undef is undef, even after relocation.
-    // TODO: provide a hook for this in GCStrategy.  This is clearly legal for
-    // most practical collectors, but there was discussion in the review thread
-    // about whether it was legal for all possible collectors.
-    if (isa<UndefValue>(DerivedPtr))
-      // Use undef of gc_relocate's type to replace it.
-      return replaceInstUsesWith(*II, UndefValue::get(II->getType()));
+      if (isa<UndefValue>(DerivedPtr) || isa<UndefValue>(BasePtr)) {
+        replaceInstUsesWith(GCR, UndefValue::get(GCR.getType()));
+        eraseInstFromFunction(GCR);
+        continue;
+      }
 
-    if (auto *PT = dyn_cast<PointerType>(II->getType())) {
+      if (auto *PT = dyn_cast<PointerType>(GCR.getType())) {
         // The relocation of null will be null for most any collector.
         // TODO: provide a hook for this in GCStrategy.  There might be some
         // weird collector this property does not hold for.
-      if (isa<ConstantPointerNull>(DerivedPtr))
+        if (isa<ConstantPointerNull>(DerivedPtr)) {
           // Use null-pointer of gc_relocate's type to replace it.
-        return replaceInstUsesWith(*II, ConstantPointerNull::get(PT));
+          replaceInstUsesWith(GCR, ConstantPointerNull::get(PT));
+          eraseInstFromFunction(GCR);
+          continue;
+        }
 
         // isKnownNonNull -> nonnull attribute
-      if (!II->hasRetAttr(Attribute::NonNull) &&
+        if (!GCR.hasRetAttr(Attribute::NonNull) &&
             isKnownNonZero(DerivedPtr, DL, 0, &AC, II, &DT)) {
-        II->addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
-        return II;
+          GCR.addAttribute(AttributeList::ReturnIndex, Attribute::NonNull);
+          // We discovered new fact, re-check users.
+          Worklist.pushUsersToWorkList(GCR);
         }
       }
 
+      // 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();
+        GCR.setOperand(2, ConstantInt::get(OpIntTy, GCR.getBasePtrIndex()));
+      }
+
       // TODO: bitcast(relocate(p)) -> relocate(bitcast(p))
       // Canonicalize on the type from the uses to the defs
 
       // TODO: relocate((gep p, C, C2, ...)) -> gep(relocate(p), C, C2, ...)
+    }
     break;
   }
-
   case Intrinsic::experimental_guard: {
     // Is this guard followed by another guard?  We scan forward over a small
     // fixed window of instructions to handle common cases with conditions
     // computed between guards.
     Instruction *NextInst = II->getNextNonDebugInstruction();
     for (unsigned i = 0; i < GuardWideningWindow; i++) {
       // Note: Using context-free form to avoid compile time blow up
       if (!isSafeToSpeculativelyExecute(NextInst))