[StatepointsForGC] Identify values for rematerialization in presence of PHI

[anna]

Summary

While walking the use chain for identifying rematerializable values in RS4GC,
add the case where the current value and base value are the same PHI nodes.

This will aid rematerialization of geps and casts instead of adding gc.relocate.

[igor-laevsky]

Could you please add a couple of tests? Also you should update comment in the header of the "findRematerializableChainToBasePointer".

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1816–1817

I would emphasise in the comment that it's a termination condition, not a continuation of recursion. Also would be nice to move it closer to the "CurrentValue == BaseValue" case.

1820

This should be named PhiNum according to the llvm convensions

1824–1826

I think you should check that incoming blocks are equivalent. In theory we can have two phi nodes with similar incoming values which are assigned to the different basic blocks, i.e:

base_value    = phi (%a, BB1), (%b, BB2)
current_value = phi (%a, BB2), (%b, BB1)

Also we can have two equivalent phi nodes with values recorder in a different order, i.e:

base_value    = phi (%a, BB1), (%b, BB2)
current_value = phi (%b, BB2), (%a, BB1)

[anna]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1824–1826

IIUC, base_value != current_value for the first example?

base_value    = phi (%a, BB1), (%b, BB2)
current_value = phi (%a, BB2), (%b, BB1)

Although the value is coming from different basic blocks, since the incoming value is an SSA value, (%a, BB1) is same as (%a, BB2). There is only one definition for %a, and all uses are dominated by the def. So, base_value == current_value in the example.
Another concern that came to mind as I saw the example was, if we needed a recursive check if %a was also a phi node. Again, we do not need this check, for the same reason that %a is an SSA value.

Regarding the second example, I initially had this in mind while writing the patch, but the check complexity is O(n log n) for n = PhiNum. Didnt think it warranted the expense :) I'll add this case.

[igor-laevsky]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1824–1826

I still think that base_value != current_value at runtime. See extended example:

BB1:
  br %merge

BB2:
  br %merge

merge:
  base_value    = phi (%a, BB1), (%b, BB2)
  current_value = phi (%b, BB1), (%a, BB2)

Say at runtime control flow will go through BB1. This would mean that "base_value == %a" and "current_value == %b". In case if we go through BB2, situation will reverse: "base_value == %b" and "current_value == %a". This means that at runtime base_value will never be equal to the current_value.

I suspect this situation is hardly possible on practice, since we know that base_value is a base pointer for the current_value. Yet I'm not convinced that we can simply ignore this problem.

[anna]

Upcoming change to handle review comments and with test cases from these examples discussed in review.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1824–1826

I see your point. I was looking at the incoming data values statically, rather than the control flow at runtime. It would take exactly one path :)

[anna]

Added a test case to show what we are trying to solve.
Also, consider reordering of arguments in phi, and consider incoming basic blocks as well.

Frankly, the best solution would be to remove the extra base.phi that is getting created, but need to see how to go about it.
I think in the current form, where base pointers that are phi nodes have an extra 'phi.base' getting generated,
we would not need the extra checks to make sure that the incoming basic blocks are the same, and also, the arguments won't be reordered.
These would be beneficial once we can remove the extra base.phi that get created.

[igor-laevsky]

looks good.

[reames]

LGTM w/minor comment

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1802

I think it's important to call out in the comment that this is a workaround for deficiency in the base pointer rewriting code. That's not immediately obvious to everyone reading. :)

We really need to rewrite that code at some point. My initial prototype version has lived far longer than it should have.

[anna]

In D23920#527833, @reames wrote:

LGTM w/minor comment

Ah, didnt see the update before my commit. However, I had added comments saying how such PHIs are generated and from which part of the algorithm. I'll explicitly mention this is a workaround for the deficiency. Thanks!

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

static bool findRematerializableChainToBasePointer(
 
   // We have found a base value
   if (CurrentValue == BaseValue) {
     return true;
   }
 
   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {
     ChainToBase.push_back(GEP);
     return findRematerializableChainToBasePointer(ChainToBase,
                                                   GEP->getPointerOperand(),
                                                   BaseValue);
   }
 
   if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
     if (!CI->isNoopCast(CI->getModule()->getDataLayout()))
       return false;
 
     ChainToBase.push_back(CI);
     return findRematerializableChainToBasePointer(ChainToBase,
                                                   CI->getOperand(0), BaseValue);
   }
 
+  // PHI nodes that have the same incoming values, and belonging to the same
+  // basic blocks are essentially the same SSA value.
+  if (PHINode *PhiCurr = dyn_cast<PHINode>(CurrentValue))
+    if (PHINode *PhiBase = dyn_cast<PHINode>(BaseValue)) {
+      int phiNum = PhiCurr->getNumIncomingValues();
+      if (phiNum != PhiBase->getNumIncomingValues() ||
+          PhiCurr->getParent() != PhiBase->getParent())
+        return false;
+      for (unsigned i = 0; i < phiNum; i++)
+        if (PhiCurr->getIncomingValue(i) != PhiBase->getIncomingValue(i))
+          return false;
+      return true;
+    }
+
   // Not supported instruction in the chain
   return false;
 }
 
 // Helper function for the "rematerializeLiveValues". Compute cost of the use
 // chain we are going to rematerialize.
 static unsigned
 chainToBasePointerCost(SmallVectorImpl<Instruction*> &Chain,