[RS4GC] Refactor code for Rematerializing in presence of phi. NFC

[anna]

Summary

This is an NFC refactoring change as a precursor to the actual fix for rematerializing in
presence of phi.
https://reviews.llvm.org/D24399

Pasted from review:
findRematerializableChainToBasePointer changed to return the root of the
chain. instead of true or false.
move the PHI matching logic into the caller by inspecting the root return value.
This includes an assertion that the alternate root is in the liveset for the
call.

Tested with current RS4GC tests.

[reames]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1818

Not quite what I had in mind, but this works. I'd expected you to remove the BaseValue parameter at the same time. I'd expected the return value to basically be the first instruction we couldn't prove was part of a rematerializable chain. The caller would then look to see if that was something it knew how to handle.

1913

The nesting here gets confusing. I'd suggest extracting a isEquivelentPHI helper. This might already exist in fact.

[anna]

[RS4GC] Refactor code for Rematerializing in presence of phi. NFC
Addressed both review comments above.

[reames]

LGTM. The semantic fix will be much more obvious when rebased on top of this. Thanks!

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

static void findLiveReferences(
   for (size_t i = 0; i < records.size(); i++) {
     struct PartiallyConstructedSafepointRecord &info = records[i];
     analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info);
   }
 }
 
 // Helper function for the "rematerializeLiveValues". It walks use chain
 // starting from the "CurrentValue" until it meets "BaseValue". Only "simple"
-// values are visited (currently it is GEP's and casts). Returns true if it
-// successfully reached "BaseValue" and false otherwise.
-// Fills "ChainToBase" array with all visited values. "BaseValue" is not
-// recorded.
-static bool findRematerializableChainToBasePointer(
+// values are visited (currently it is GEP's and casts). Returns the Root of the
+// chain if it successfully reached "BaseValue" and null otherwise.  Fills
+// "ChainToBase" array with all visited values. "BaseValue" is not recorded.
+static Value* findRematerializableChainToBasePointer(
   SmallVectorImpl<Instruction*> &ChainToBase,
   Value *CurrentValue, Value *BaseValue) {
 
   // We have found a base value
-  if (CurrentValue == BaseValue) {
-    return true;
-  }
+  if (CurrentValue == BaseValue)
+    return CurrentValue;
 
-  // Check for same values, when both BaseValue and CurrentValue are phi nodes.
-  // PHI nodes that have the same incoming values, and belonging to the same
-  // basic blocks are essentially the same SSA value.  Such an example of same
-  // BaseValue, CurrentValue phis is created by findBasePointer, when a phi has
-  // incoming values with different base pointers. This phi is marked as
-  // conflict, and hence an additional phi with the same incoming values get
-  // generated. We need to identify the BaseValue (.base version of phi) and
-  // CurrentValue (the phi node itself) as the same, so that we can
-  // rematerialize the gep and casts below. This is a workaround for the
-  // deficieny in the findBasePointer algorithm.
-  if (PHINode *CurrentPhi = dyn_cast<PHINode>(CurrentValue))
-    if (PHINode *BasePhi = dyn_cast<PHINode>(BaseValue)) {
-      auto PhiNum = CurrentPhi->getNumIncomingValues();
-      if (PhiNum != BasePhi->getNumIncomingValues() ||
-          CurrentPhi->getParent() != BasePhi->getParent())
-        return false;
-      // Map of incoming values and their corresponding basic blocks of
-      // CurrentPhi.
-      SmallDenseMap<Value *, BasicBlock *, 8> CurrentIncomingValues;
-      for (unsigned i = 0; i < PhiNum; i++)
-        CurrentIncomingValues[CurrentPhi->getIncomingValue(i)] =
-            CurrentPhi->getIncomingBlock(i);
-
-      // Both current and base PHIs should have same incoming values and
-      // the same basic blocks corresponding to the incoming values.
-      for (unsigned i = 0; i < PhiNum; i++) {
-        auto CIVI = CurrentIncomingValues.find(BasePhi->getIncomingValue(i));
-        if (CIVI == CurrentIncomingValues.end())
-          return false;
-        BasicBlock *CurrentIncomingBB = CIVI->second;
-        if (CurrentIncomingBB != BasePhi->getIncomingBlock(i))
-          return false;
-      }
-      return true;
-    }
+  // If both are phi nodes, we check if the incoming values of the phi nodes are
+  // the same (i.e. they are same SSA values) at the caller side.
+  if (isa<PHINode>(CurrentValue) && isa<PHINode>(BaseValue))
+    return CurrentValue;
 
   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;
+      return nullptr;
 
     ChainToBase.push_back(CI);
     return findRematerializableChainToBasePointer(ChainToBase,
                                                   CI->getOperand(0), BaseValue);
   }
 
   // Not supported instruction in the chain
-  return false;
+  return nullptr;
 }
 
 // Helper function for the "rematerializeLiveValues". Compute cost of the use
 // chain we are going to rematerialize.
 static unsigned
 chainToBasePointerCost(SmallVectorImpl<Instruction*> &Chain,
                        TargetTransformInfo &TTI) {
   unsigned Cost = 0;
static void rematerializeLiveValues(CallSite CS,
   // Record values we are going to delete from this statepoint live set.
   // We can not di this in following loop due to iterator invalidation.
   SmallVector<Value *, 32> LiveValuesToBeDeleted;
 
   for (Value *LiveValue: Info.LiveSet) {
     // For each live pointer find it's defining chain
     SmallVector<Instruction *, 3> ChainToBase;
     assert(Info.PointerToBase.count(LiveValue));
-    bool FoundChain =
+    Value *RootNode =
       findRematerializableChainToBasePointer(ChainToBase,
                                              LiveValue,
                                              Info.PointerToBase[LiveValue]);
     // Nothing to do, or chain is too long
-    if (!FoundChain ||
+    if (!RootNode ||
         ChainToBase.size() == 0 ||
         ChainToBase.size() > ChainLengthThreshold)
       continue;
 
+    // The only scenario where returned root node is not equal to the base
+    // pointer (original root node) is when both are phi nodes.
+    if (RootNode != Info.PointerToBase[LiveValue]) {
+      // Check for same values, when both BaseValue and RootNode are phi nodes.
+      // PHI nodes that have the same incoming values, and belonging to the same
+      // basic blocks are essentially the same SSA value.  Such an example of
+      // same BaseValue, RootNode phis is created by findBasePointer, when a phi
+      // has incoming values with different base pointers. This phi is marked as
+      // conflict, and hence an additional phi with the same incoming values get
+      // generated. We need to identify the newly generated AlternateRootPhi
+      // (.base version of phi) and RootNode (the original phi node itself) as
+      // the same, so that we can rematerialize the gep and casts below. This is
+      // a workaround for the deficieny in the findBasePointer algorithm.
+      PHINode *OrigRootPhi = cast<PHINode>(RootNode);
+      PHINode *AlternateRootPhi = cast<PHINode>(Info.PointerToBase[LiveValue]);
+
+      auto AreSameIncomingValues =
+          [](unsigned &PhiNum,
+             SmallDenseMap<Value *, BasicBlock *, 8> &CurrentIncomingValues,
+             PHINode &AlternateRootPhi) {
+
+            for (unsigned i = 0; i < PhiNum; i++) {
+              auto CIVI =
+                  CurrentIncomingValues.find(AlternateRootPhi.getIncomingValue(i));
+              if (CIVI == CurrentIncomingValues.end())
+                return false;
+              BasicBlock *CurrentIncomingBB = CIVI->second;
+              if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i))
+                return false;
+            }
+            return true;
+
+          };
+      unsigned PhiNum = OrigRootPhi->getNumIncomingValues();
+      if (PhiNum != AlternateRootPhi->getNumIncomingValues() ||
+          OrigRootPhi->getParent() != AlternateRootPhi->getParent())
+        continue;
+      // Map of incoming values and their corresponding basic blocks of
+      // OrigRootPhi.
+      SmallDenseMap<Value *, BasicBlock *, 8> CurrentIncomingValues;
+      for (unsigned i = 0; i < PhiNum; i++)
+        CurrentIncomingValues[OrigRootPhi->getIncomingValue(i)] =
+            OrigRootPhi->getIncomingBlock(i);
+
+      // Both current and base PHIs should have same incoming values and
+      // the same basic blocks corresponding to the incoming values.
+      if (!AreSameIncomingValues(PhiNum, CurrentIncomingValues,
+                                 *AlternateRootPhi))
+        continue;
+      // Now that the phi nodes are proved to be the same, assert that
+      // findBasePointer's newly generated AlternateRootPhi is present in the
+      // liveset of the call.
+      assert(Info.LiveSet.count(AlternateRootPhi));
+    }
     // Compute cost of this chain
     unsigned Cost = chainToBasePointerCost(ChainToBase, TTI);
     // TODO: We can also account for cases when we will be able to remove some
     //       of the rematerialized values by later optimization passes. I.e if
     //       we rematerialized several intersecting chains. Or if original values
     //       don't have any uses besides this statepoint.
 
     // For invokes we need to rematerialize each chain twice - for normal and