[RS4GC] Prune inputs of BDV if they are BDV themselves

[dmakogon]

Summary

There's a stage in RS4GC when we remove all nodes from the state list if all of their inputs are base pointers.
Consider the following PHI:

loop:
  %ph = phi i8* [ %ph, %loop ], [ %b, %block ]

Say %b is a base value. Then we should remove the %ph from the states list, because it's equal to %b.
This patch just skips all the input values if they are equal to the value currently being processed.

If in the example above we had a user of %ph for which we were asked to find a base value,
we'd clone that user and replaced %ph uses with the %b base value.
With the patch %ph is treated as a base pointer, so no cloning happens.

[mkazantsev]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

939

What if V->stripPointerCasts() == BDV, will this still return false?

[mkazantsev]

Will this patch handle the following example:

loop: 
  %outer_phi = phi (%start, %inner_phi)
  br inner_loop

inner_loop:
  %inner_phi = phi(%start, %outer_phi)
  %inner.cond = <smth>
  br %inner.cond, inner_loop, outer_backedge

outer_backedge:
  outer_cond = ...
  br outer_cond, loop, exit

exit:
...

Here both inner_phi and outer_phi are in fact equal to one another (and both equal to start), but still different values. Will it work? If no, is there a plan to make it work?

[mkazantsev]

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

939

One possible way to get that is

%ph = phi i8* [ %ph2, %loop ], [ %b, %block ]
%ph1 = bitcast %ph to i32*
%ph2 = bitcast %ph1 to i8*

[reames]

LGTM

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

937

Please rephrase this comment to emphasize this is handling the phi case (as no other instruction can have itself as operand in reachable code).

[dmakogon]

In D123846#3453716, @mkazantsev wrote:

Will this patch handle the following example:

loop: 
  %outer_phi = phi (%start, %inner_phi)
  br inner_loop

inner_loop:
  %inner_phi = phi(%start, %outer_phi)
  %inner.cond = <smth>
  br %inner.cond, inner_loop, outer_backedge

outer_backedge:
  outer_cond = ...
  br outer_cond, loop, exit

exit:
...

Here both inner_phi and outer_phi are in fact equal to one another (and both equal to start), but still different values. Will it work? If no, is there a plan to make it work?

No, these PHIs won't be removed at this stage of RS4GC.
However there won't be any cloning here. During states meet phase we will figure out that they both have the %start base. Merging two equal bases is not a conflict state.

[dmakogon]

Added more test cases with derived pointers.
Fixed comment message.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

#endif
   // a base pointer for happens to be a base pointer itself.  (Or a sub-graph
   // feeding it does.)
   SmallVector<Value *> ToRemove;
   do {
     ToRemove.clear();
     for (auto Pair : States) {
       Value *BDV = Pair.first;
       auto canPruneInput = [&](Value *V) {
-        Value *BDV = findBaseOrBDV(V, Cache);
-        if (V->stripPointerCasts() != BDV)
+        // BDV is present in the states map, so in case when the input is the
+        // BDV itself, we'd return false. So explicitly check this case.
+        if (V == BDV)
+          return true;
+        Value *VBDV = findBaseOrBDV(V, Cache);
+        if (V->stripPointerCasts() != VBDV)
           return false;
         // The assumption is that anything not in the state list is
         // propagates a base pointer.
-        return States.count(BDV) == 0;
+        return States.count(VBDV) == 0;
       };
 
       bool CanPrune = true;
       visitBDVOperands(BDV, [&](Value *Op) {
         CanPrune = CanPrune && canPruneInput(Op);
       });
       if (CanPrune)
         ToRemove.push_back(BDV);

llvm/test/Transforms/RewriteStatepointsForGC/base-pointers-14.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -rewrite-statepoints-for-gc < %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @foo() gc "statepoint-example"
 
-; FIXME: In this test case %b6.base, which is inserted by RS4GC, is identical
-; to %b6.
 define i8 addrspace(1)* @test1(i1 %c, i8 addrspace(1)* %b1, i8 addrspace(1)* %b2) gc "statepoint-example" {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  left:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP:%.*]], label [[MERGE2:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[B5:%.*]] = phi i8 addrspace(1)* [ [[B2:%.*]], [[LEFT:%.*]] ], [ [[B5]], [[LOOP]] ]
 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[MERGE2]]
 ; CHECK:       merge2:
-; CHECK-NEXT:    [[B6_BASE:%.*]] = phi i8 addrspace(1)* [ [[B1:%.*]], [[LEFT]] ], [ [[B2]], [[LOOP]] ], !is_base_value !0
-; CHECK-NEXT:    [[B6:%.*]] = phi i8 addrspace(1)* [ [[B1]], [[LEFT]] ], [ [[B5]], [[LOOP]] ]
-; CHECK-NEXT:    [[STATEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* elementtype(void ()) @foo, i32 0, i32 0, i32 0, i32 0) [ "deopt"(), "gc-live"(i8 addrspace(1)* [[B6]], i8 addrspace(1)* [[B6_BASE]]) ]
-; CHECK-NEXT:    [[B6_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 1, i32 0)
-; CHECK-NEXT:    [[B6_BASE_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 1, i32 1)
+; CHECK-NEXT:    [[B6:%.*]] = phi i8 addrspace(1)* [ [[B1:%.*]], [[LEFT]] ], [ [[B5]], [[LOOP]] ]
+; CHECK-NEXT:    [[STATEPOINT_TOKEN:%.*]] = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* elementtype(void ()) @foo, i32 0, i32 0, i32 0, i32 0) [ "deopt"(), "gc-live"(i8 addrspace(1)* [[B6]]) ]
+; CHECK-NEXT:    [[B6_RELOCATED:%.*]] = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token [[STATEPOINT_TOKEN]], i32 0, i32 0)
 ; CHECK-NEXT:    ret i8 addrspace(1)* [[B6_RELOCATED]]
 ;
 left:
   br i1 %c, label %loop, label %merge2
 
 loop:
   %b5 = phi i8 addrspace(1)* [ %b2, %left ], [ %b5, %loop ]
   br i1 %c, label %loop, label %merge2