[RS4GC] Extract rematerilazable candidate search. NFC.

[skatkov]

Summary

Finding re-materialization chain for derived pointer does not depend on
call site. To avoid this finding for each call site it can be extracted in
a separate routine.

[reames]

General direction seems reasonable, a couple inline comments, but likely to converge to an LGTM quickly.

However, I'd suggest taking a step back and asking whether this code makes sense at all. I don't want to make this blocking, but I think it does make sense to reexamine before going much further.

Given a random derived pointer P and it's base B, we can always find the offset via sub(ptrtoint(P), ptrtoint(B)). Materializing the ptrtoint is maybe undesirable, but we already do this in a couple places in the existing code. (Remember, this is a lowering pass.) See gc.get.pointer.offset.

I'd argue this means we should either be remating everything, or nothing. The current heuristic - which amounts to "can we find the gep chain?" - really doesn't seem defensible.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

287

Shouldn't this always be the base pointer of the last element in the chain? If so, might be good to either not store explicitly, or at least assert.

2275

This really looks like something we should fix in the findBasePointer code, but we can leave it for the moment. We're adding complexity to avoid fixing another problem, and that seems non ideal.

2330

You're doing a copy here, but I don't see either the copy or the source modified. Did you mean this to be a const reference?

[skatkov]

I agree that this re-materialization is not great (especially cost model). Will explain my understanding in a separate comment.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

287

According to comment below (special handling of findBasePointer inefficiency) RootOfChain might differ from found base pointer and we need to keep it to make a replacement of RootOfChain during re-materialization.

According to findRematerializationCandidates, RootOfChain might be only base or alternative phi. This is by construction. What assert do you propose to add? Just to repeat a logic of findRematerializationCandidates?

If we solve the problem with inefficiency of findBasePointer we will need this field at all.

2275

Agreed. I wanted to keep it as NFC.

2330

Next line is a reverse of the chain.

[skatkov]

Hi Philip, I've tried to consider re-materialization of derived pointers from live range profitability.
Let's our dp = base + Idx *scale + offset.
Let's disp = dp - base = Idx *scale + offset. (this is about your potential proposal to remat all as I've understood it).

Let's we have the following points in a program:
0 Def of Idx and Off
1 Def of dp and probably disp if we consider this case.
2 Call site with statepoint (dp and base should ba alive here)
2.2 Remat of dp close to call site. (If we do re-materialization)
2.8 Remat of dp close to use. (If we do re-materialization)
3 Use of dp.

Now consider 5 scenarios of re-materialization:
A. No re-materialization at all.
B. Remat at call site
C. Remat at use
D. Remat at call site with disp pre-computerd.
E. Remat at call site with disp at use.

What live in different ranges?
[0,1) - Idx and off for A, B, C, D, E.
[1,2) -
A: base, dp
B: Off, Idx, base
C: Off, Idx, base
D: base, disp
E: base, disp
[2, 2.2) -
A: dp
B: Off, Idx, base
C: Off, Idx, base
D: base, disp
E: base, disp
[2.2, 2.8) -
A: dp
B: dp
C: Off, Idx, base
D: dp
E: base, disp
[2.8, 3) - only dp for A, B, C, D, E.

So in general case, in terms of liveness, no re-materialization is better than any re-materialization.
And disp case is better than Idx + Off in case both of them are not constant.
But if Idx and Off are constant and disp as a result we get
[0,1) - none
[1,2) -
A: base, dp
B: base
C: base
D: base
E: base
[2, 2.2) -
A: dp
B: base
C: base
D: base
E: base
[2.2, 2.8) -
A: dp
B: dp
C: base
D: dp
E: base
[2.8, 3) - only dp for A, B, C, D, E.
So any kind of re-materialization is better than no re-materialization.

So in terms of liveness, re-materialization is profitable if Idx and Off are constants.

However re-materialization has some additional effects.
First of all dp computation may potentially be folded into use and in the case re-materialization may be positive in spite of extend of live range due to we eliminate the derived pointer computation.

Additionally even if do not fold derived pointer into all users we may move the derived pointer computation from hot block to cold one (positive impact) or from cold block to hot block (negative impact).

Taking all above (which possibly misses some corner cases) I would say that re-materialization is profitable if

1. We can fold address computation to all users and Idx and Off are constants.
2. Rematerialization insert point is colder that original derived point computation and Idx and Off are constants.
3. If Idx and Off are not constants, think three times before moving to colder block.

Any thoguhts? Would be very glad to consider this from other angles and continue discussion.
For a while we can land this re-factoring due to it change nothing - NFC.

Sorry for the long comment.

[reames]

LGTM to this patch. All of my style/code concerns had good justifications.

On the general topic, I was thinking of remat slightly differently. You broke down the indexing expression into the component pieces (Scale, Idx, Disp). I was thinking about simply computing (Ptr-Base) or RawOffset. RawOffset might be factorable into component pieces, but I wasn't thinking in terms of extending the live ranges of those pieces.

Instead, I was thinking of rewriting this code:
base = ...
p = some_offset_function(base)
...
use (p)

Into
base = ...
rawoffset = some_offset_function(base) - p
...
p = base + rawoffset
use (p)

With this form, p+rawOffset should reliable fold into use (for memory uses at least), and the live range of rawoffset is exactly the same as the original p. We do have an extra variable in the sub-expression, but that's very localized register pressure as the variable for some_offset_function extends one instruction (sub) past the original definition of p.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

struct PartiallyConstructedSafepointRecord {
   Instruction *UnwindToken;
 
   /// Record live values we are rematerialized instead of relocating.
   /// They are not included into 'LiveSet' field.
   /// Maps rematerialized copy to it's original value.
   RematerializedValueMapTy RematerializedValues;
 };
 
+struct RematerizlizationCandidateRecord {
+  // Chain from derived pointer to base.
+  SmallVector<Instruction *, 3> ChainToBase;
+  // Original base.
+  Value *RootOfChain;
+  // Cost of chain.
+  InstructionCost Cost;
+};
+using RematCandTy = MapVector<Value *, RematerizlizationCandidateRecord>;
+
 } // end anonymous namespace
 
 static ArrayRef<Use> GetDeoptBundleOperands(const CallBase *Call) {
   Optional<OperandBundleUse> DeoptBundle =
       Call->getOperandBundle(LLVMContext::OB_deopt);
 
   if (!DeoptBundle.hasValue()) {
     assert(AllowStatepointWithNoDeoptInfo &&
if (CIVI == CurrentIncomingValues.end())
       return false;
     BasicBlock *CurrentIncomingBB = CIVI->second;
     if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i))
       return false;
   }
   return true;
 }
 
-// From the statepoint live set pick values that are cheaper to recompute then
-// to relocate. Remove this values from the live set, rematerialize them after
-// statepoint and record them in "Info" structure. Note that similar to
-// relocated values we don't do any user adjustments here.
-static void rematerializeLiveValues(CallBase *Call,
-                                    PartiallyConstructedSafepointRecord &Info,
-                                    PointerToBaseTy &PointerToBase,
-                                    TargetTransformInfo &TTI) {
+// Find derived pointers that can be recomputed cheap enough and fill
+// RematerizationCandidates with such candidates.
+static void
+findRematerializationCandidates(PointerToBaseTy PointerToBase,
+                                RematCandTy &RematerizationCandidates,
   const unsigned int ChainLengthThreshold = 10;
 
-  // 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 (auto P2B : PointerToBase) {
+    auto *Derived = P2B.first;
+    auto *Base = P2B.second;
+    // Consider only derived pointers.
+    if (Derived == Base)
+      continue;
 
-  for (Value *LiveValue: Info.LiveSet) {
-    // For each live pointer find its defining chain
+    // For each live pointer find its defining chain.
     SmallVector<Instruction *, 3> ChainToBase;
-    assert(PointerToBase.count(LiveValue));
     Value *RootOfChain =
-      findRematerializableChainToBasePointer(ChainToBase,
-                                             LiveValue);
+        findRematerializableChainToBasePointer(ChainToBase, Derived);
 
     // Nothing to do, or chain is too long
     if ( ChainToBase.size() == 0 ||
         ChainToBase.size() > ChainLengthThreshold)
       continue;
 
     // Handle the scenario where the RootOfChain is not equal to the
     // Base Value, but they are essentially the same phi values.
-    if (RootOfChain != PointerToBase[LiveValue]) {
+    if (RootOfChain != PointerToBase[Derived]) {
       PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
-      PHINode *AlternateRootPhi = dyn_cast<PHINode>(PointerToBase[LiveValue]);
+      PHINode *AlternateRootPhi = dyn_cast<PHINode>(PointerToBase[Derived]);
       if (!OrigRootPhi || !AlternateRootPhi)
         continue;
       // PHI nodes that have the same incoming values, and belonging to the same
       // basic blocks are essentially the same SSA value.  When the original phi
       // has incoming values with different base pointers, the original phi is
       // marked as conflict, and an additional `AlternateRootPhi` with the same
       // incoming values get generated by the findBasePointer function. We need
       // to identify the newly generated AlternateRootPhi (.base version of phi)
       // and RootOfChain (the original phi node itself) are the same, so that we
       // can rematerialize the gep and casts. This is a workaround for the
       // deficiency in the findBasePointer algorithm.
       if (!AreEquivalentPhiNodes(*OrigRootPhi, *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
+    // Compute cost of this chain.
     InstructionCost 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.
 
+    // Ok, there is a candidate.
+    RematerizlizationCandidateRecord Record;
+    Record.ChainToBase = ChainToBase;
+    Record.RootOfChain = RootOfChain;
+    Record.Cost = Cost;
+    RematerizationCandidates.insert({ Derived, Record });
+  }
+}
+
+// From the statepoint live set pick values that are cheaper to recompute then
+// to relocate. Remove this values from the live set, rematerialize them after
+// statepoint and record them in "Info" structure. Note that similar to
+// relocated values we don't do any user adjustments here.
+static void rematerializeLiveValues(CallBase *Call,
+                                    PartiallyConstructedSafepointRecord &Info,
+                                    PointerToBaseTy &PointerToBase,
+                                    RematCandTy &RematerizationCandidates,
+                                    TargetTransformInfo &TTI) {
+  // 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) {
+    auto It = RematerizationCandidates.find(LiveValue);
+    if (It == RematerizationCandidates.end())
+      continue;
+
+    RematerizlizationCandidateRecord &Record = It->second;
+
+    InstructionCost Cost = Record.Cost;
     // For invokes we need to rematerialize each chain twice - for normal and
     // for unwind basic blocks. Model this by multiplying cost by two.
-    if (isa<InvokeInst>(Call)) {
+    if (isa<InvokeInst>(Call))
       Cost *= 2;
-    }
-    // If it's too expensive - skip it
+
+    // If it's too expensive - skip it.
     if (Cost >= RematerializationThreshold)
       continue;
 
     // Remove value from the live set
     LiveValuesToBeDeleted.push_back(LiveValue);
 
-    // Clone instructions and record them inside "Info" structure
+    // Clone instructions and record them inside "Info" structure.
 
-    // Walk backwards to visit top-most instructions first
+    // For each live pointer find get its defining chain.
+    SmallVector<Instruction *, 3> ChainToBase = Record.ChainToBase;
+    // Walk backwards to visit top-most instructions first.
     std::reverse(ChainToBase.begin(), ChainToBase.end());
 
     // Utility function which clones all instructions from "ChainToBase"
     // and inserts them before "InsertBefore". Returns rematerialized value
     // which should be used after statepoint.
     auto rematerializeChain = [&ChainToBase](
         Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase) {
       Instruction *LastClonedValue = nullptr;
#endif
     };
 
     // Different cases for calls and invokes. For invokes we need to clone
     // instructions both on normal and unwind path.
     if (isa<CallInst>(Call)) {
       Instruction *InsertBefore = Call->getNextNode();
       assert(InsertBefore);
       Instruction *RematerializedValue = rematerializeChain(
-          InsertBefore, RootOfChain, PointerToBase[LiveValue]);
+          InsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
       Info.RematerializedValues[RematerializedValue] = LiveValue;
     } else {
       auto *Invoke = cast<InvokeInst>(Call);
 
       Instruction *NormalInsertBefore =
           &*Invoke->getNormalDest()->getFirstInsertionPt();
       Instruction *UnwindInsertBefore =
           &*Invoke->getUnwindDest()->getFirstInsertionPt();
 
       Instruction *NormalRematerializedValue = rematerializeChain(
-          NormalInsertBefore, RootOfChain, PointerToBase[LiveValue]);
+          NormalInsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
       Instruction *UnwindRematerializedValue = rematerializeChain(
-          UnwindInsertBefore, RootOfChain, PointerToBase[LiveValue]);
+          UnwindInsertBefore, Record.RootOfChain, PointerToBase[LiveValue]);
 
       Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
       Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
     }
   }
 
   // Remove rematerializaed values from the live set
   for (auto LiveValue: LiveValuesToBeDeleted) {
for (auto &Info : Records) {
     });
   }
 
   for (CallInst *CI : Holders)
     CI->eraseFromParent();
 
   Holders.clear();
 
+  // Compute the cost of possible re-materialization of derived pointers.
+  RematCandTy RematerizationCandidates;
+  findRematerializationCandidates(PointerToBase, RematerizationCandidates, TTI);
+
   // In order to reduce live set of statepoint we might choose to rematerialize
   // some values instead of relocating them. This is purely an optimization and
   // does not influence correctness.
   for (size_t i = 0; i < Records.size(); i++)
-    rematerializeLiveValues(ToUpdate[i], Records[i], PointerToBase, TTI);
+    rematerializeLiveValues(ToUpdate[i], Records[i], PointerToBase,
+                            RematerizationCandidates, TTI);
 
   // We need this to safely RAUW and delete call or invoke return values that
   // may themselves be live over a statepoint.  For details, please see usage in
   // makeStatepointExplicitImpl.
   std::vector<DeferredReplacement> Replacements;
 
   // Now run through and replace the existing statepoints with new ones with
   // the live variables listed.  We do not yet update uses of the values being