[RS4GC] Avoid usage of unrelocated values while rematerializing geps and casts

[anna]

Summary

When rematerializing for geps and casts in presence of phis, we need to make
sure that unrelocated values (the current Phi node) should never be used.
The relocation is only done for the base version of the phi, which is generated
by findBasePointers function.

This is a fix when IR verifier for safepoints identifies uses of unrelocated values,
which was generated due to commit rL279975.

[reames]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1819

I'm not really following why this is needed. How can there be uses of the original phi which don't get updated? Isn't that a missed relocation bug? Looking at the added test case, I don't see how that's related to the change?

If you could expand a bit more on the scenario which causes this and how we reach the problematic situation, I'd appreciate it.

[anna]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1819

Let's consider the first example:

%basephi = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ]
  %ptr.gep = getelementptr i32, i32 addrspace(1)* %basephi, i32 15
  call void @do_safepoint() ["deopt"() ]
  call void @use_obj32(i32 addrspace(1)* %ptr.gep)
  ret void

The findBasePointer function generates an additional phi for basephi:

%basephi.base = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ], !is_base_value !0

The ptr.gep still has basephi as the pointer operand, but the BaseValue passed into findRematerializableChainToBasePointer for this gep is the basephi.base (newly added phi by findBasePointer function).
We reach the point going up the use chain, where CurrentValue: basephi is same as BaseValue: basephi.base, both are the same phi nodes.
We then rematerialize the ptr.gep instead of relocating it, but the code after RS4GC becomes:

%basephi = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ]
 %basephi.base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 7, i32 7) ; 
%ptr.gep.remat = getelementptr i32, i32 addrspace(1)* %basephi, i32 15

The original basephi is never relocated, only basephi.base added by findBasePointer is relocated. However, the remat gep still points to the unrelocated value. This was what the original test case resulted in (left hand side of test1: contains_basephi). However, when passed through the ir-verifier, we can see that it's actually incorrect safepoint code.

P.S: The second test case is added to show that this problem never gets exposed when we relocate the gep. In this case too, basephi is never relocated, only the basephi.base and the ptr.gep gets relocated. Until now, this was not a problem since we never remat'ed geps/casts in the presence of this deficiency (creation of basephi.base in the findBasePointer algo).

I think the reason comes down to the fact that basephi.base is considered the BasePointer for relocation, since that is generated by findBasePointer. So, both the original fix and this new one for correct safepoint code, is to work around the findBasePointer deficiency. Should we go about this another way?

[reames]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1819

If I've read this correctly, I think the root issue here is that there's an undocumented assumption in the rematerialization code that a live derived pointer (which we must have if we're remating) must also keep it's base pointer live over the use site.

The problem (as you said) is that we're essentially inserting a use of a value which *isn't* live over the call. There's an equivalent version which *is*, but the original phi isn't.

I can see why your fix papers over the problem, but I'm concerned that it's not a root fix. In particular, how this interacts with multiple calls between the def and the use is unclear. I need to think through that further. I'll update again in the near future.

[reames]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1819

Ok, what do you think of the following restructuring:

• findRematerializableChainToBasePointer can be changed to return the root of the chain. Where we'd today return either true or false, we now return the root of the chain instead.
• 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.
• change the rematerializeChain function to explicitly replace uses of the original root with the updated root. This avoids the replaceAllUsesOf which worries me.

[anna]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1819

agree with the restructuring. I started with point 3 initially, but decided to go ahead with replaceAllUsesOf. I could not think of a reason this would be bad. Also, it could potentially reduce the number of times we hit the phi matching logic.

As you mention, replaceAllUsesOf is a very widespread semantic change, versus just replacing the uses of original root that we found in the chain. Much less riskier.

[anna]

The semantic change required to remat in presence of phi.
Only replace use in the remat chain, rather than replacing all uses with the live value.
This is rebased over the refactoring NFC change: https://reviews.llvm.org/D24780
Verified IR generated in tests with safepoint-verifier, and running some local tests.

[reames]

Looks close to ready, one more update should do it.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1983

ReplaceUnrelocatedUse doesn't need to be a reference. And shouldn't be.

2006

Strengthen this assert to include the root value and the new root value.

2016

I don't think you actually need this variable. If you just check OldRoot != NewRoot, doesn't that give you the same property?

[anna]

Addressed the 3 comments above.
Tested the asserts.

[reames]

LGTM. Thanks!

[anna]

Thanks Philip! local tests results look fine (some are ongoing). I'll check this in.

[anna]

Committed as: https://reviews.llvm.org/rL282150

Forgot to amend the commit, so this did not auto-close the revision.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

 // Helper function for the "rematerializeLiveValues". It walks use chain
 // starting from the "CurrentValue" until it reaches the root of the chain, i.e.
 // the base or a value it cannot process. Only "simple" values are processed
 // (currently it is GEP's and casts). The returned root is  examined by the
 // callers of findRematerializableChainToBasePointer.  Fills "ChainToBase" array
 // with all visited values.
 static Value* findRematerializableChainToBasePointer(
   SmallVectorImpl<Instruction*> &ChainToBase,
   Value *CurrentValue) {
 
   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {
     ChainToBase.push_back(GEP);
     return findRematerializableChainToBasePointer(ChainToBase,
                                                   GEP->getPointerOperand());
   }
 
   if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {
Value *RootOfChain =
       findRematerializableChainToBasePointer(ChainToBase,
                                              LiveValue);
 
     // Nothing to do, or chain is too long
     if ( ChainToBase.size() == 0 ||
         ChainToBase.size() > ChainLengthThreshold)
       continue;
 
+    bool ReplaceUnrelocatedUse = false;
     // Handle the scenario where the RootOfChain is not equal to the
     // Base Value, but they are essentially the same phi values.
     if (RootOfChain != Info.PointerToBase[LiveValue]) {
       PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);
       PHINode *AlternateRootPhi = dyn_cast<PHINode>(Info.PointerToBase[LiveValue]);
       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
       // deficieny 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));
+      ReplaceUnrelocatedUse = true;
     }
     // 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 (Value *LiveValue: Info.LiveSet) {
     // Clone instructions and record them inside "Info" structure
 
     // 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) {
+    auto rematerializeChain = [&ChainToBase](
+        Instruction *InsertBefore, Value *RootOfChain, Value *AlternateLiveBase,
+        bool &ReplaceUnrelocatedUse) {
       Instruction *LastClonedValue = nullptr;
       Instruction *LastValue = nullptr;
       for (Instruction *Instr: ChainToBase) {
         // Only GEP's and casts are suported as we need to be careful to not
         // introduce any new uses of pointers not in the liveset.
         // Note that it's fine to introduce new uses of pointers which were
         // otherwise not used after this statepoint.
         assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));
 
         Instruction *ClonedValue = Instr->clone();
         ClonedValue->insertBefore(InsertBefore);
         ClonedValue->setName(Instr->getName() + ".remat");
 
         // If it is not first instruction in the chain then it uses previously
         // cloned value. We should update it to use cloned value.
         if (LastClonedValue) {
           assert(LastValue);
           ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue);
 #ifndef NDEBUG
           // Assert that cloned instruction does not use any instructions from
           // this chain other than LastClonedValue
           for (auto OpValue : ClonedValue->operand_values()) {
             assert(!is_contained(ChainToBase, OpValue) &&
                    "incorrect use in rematerialization chain");
           }
 #endif
+        } else {
+          // For the first instruction, replace the use of unrelocated base i.e.
+          // RootOfChain/OrigRootPhi, with the corresponding PHI present in the
+          // live set. They have been proved to be the same PHI nodes.  Note
+          // that the *only* use of the RootOfChain is the first Value in the
+          // ChainToBase list.
+          if (ReplaceUnrelocatedUse)
+            ClonedValue->replaceUsesOfWith(RootOfChain, AlternateLiveBase);
         }
 
         LastClonedValue = ClonedValue;
         LastValue = Instr;
       }
       assert(LastClonedValue);
       return LastClonedValue;
     };
 
     // Different cases for calls and invokes. For invokes we need to clone
     // instructions both on normal and unwind path.
     if (CS.isCall()) {
       Instruction *InsertBefore = CS.getInstruction()->getNextNode();
       assert(InsertBefore);
-      Instruction *RematerializedValue = rematerializeChain(InsertBefore);
+      Instruction *RematerializedValue = rematerializeChain(
+          InsertBefore, RootOfChain, Info.PointerToBase[LiveValue],
+          ReplaceUnrelocatedUse);
       Info.RematerializedValues[RematerializedValue] = LiveValue;
     } else {
       InvokeInst *Invoke = cast<InvokeInst>(CS.getInstruction());
 
       Instruction *NormalInsertBefore =
           &*Invoke->getNormalDest()->getFirstInsertionPt();
       Instruction *UnwindInsertBefore =
           &*Invoke->getUnwindDest()->getFirstInsertionPt();
 
-      Instruction *NormalRematerializedValue =
-          rematerializeChain(NormalInsertBefore);
-      Instruction *UnwindRematerializedValue =
-          rematerializeChain(UnwindInsertBefore);
+      Instruction *NormalRematerializedValue = rematerializeChain(
+          NormalInsertBefore, RootOfChain, Info.PointerToBase[LiveValue],
+          ReplaceUnrelocatedUse);
+      Instruction *UnwindRematerializedValue = rematerializeChain(
+          UnwindInsertBefore, RootOfChain, Info.PointerToBase[LiveValue],
+          ReplaceUnrelocatedUse);
 
       Info.RematerializedValues[NormalRematerializedValue] = LiveValue;
       Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;
     }
   }
 
   // Remove rematerializaed values from the live set
   for (auto LiveValue: LiveValuesToBeDeleted) {

test/Transforms/RewriteStatepointsForGC/rematerialize-derived-pointers.ll

 
 merge:
   ; CHECK: %basephi.base = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ], !is_base_value !0
   ; CHECK: %basephi = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ]
   ; CHECK: %ptr.gep = getelementptr i32, i32 addrspace(1)* %basephi, i32 15
   ; CHECK: %statepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint
   ; CHECK: %basephi.base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 7, i32 7) ; (%basephi.base, %basephi.base)
   ; CHECK: %basephi.base.relocated.casted = bitcast i8 addrspace(1)* %basephi.base.relocated to i32 addrspace(1)*
-  ; CHECK: %ptr.gep.remat = getelementptr i32, i32 addrspace(1)* %basephi, i32 15
+  ; CHECK: %ptr.gep.remat = getelementptr i32, i32 addrspace(1)* %basephi.base.relocated.casted, i32 15
   ; CHECK: call void @use_obj32(i32 addrspace(1)* %ptr.gep.remat)
 
 
 
   %basephi = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ]
   %ptr.gep = getelementptr i32, i32 addrspace(1)* %basephi, i32 15
   call void @do_safepoint() ["deopt"() ]
   call void @use_obj32(i32 addrspace(1)* %ptr.gep)
   ret void
 }
+
+
+define void @test_intersecting_chains_with_phi(i1 %cond) gc "statepoint-example" {
+; CHECK-LABEL: test_intersecting_chains_with_phi
+entry:
+  %base1 = call i32 addrspace(1)* @new_instance()
+  %base2 = call i32 addrspace(1)* @new_instance()
+  br i1 %cond, label %here, label %there
+
+here:
+  br label %merge
+
+there:
+  br label %merge
+
+merge:
+  %basephi = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ]
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %basephi, i32 15
+  %ptr.cast = bitcast i32 addrspace(1)* %ptr.gep to i64 addrspace(1)*
+  %ptr.cast2 = bitcast i32 addrspace(1)* %ptr.gep to i16 addrspace(1)*
+  call void @do_safepoint() [ "deopt"() ]
+  ; CHECK: statepoint
+  ; CHECK: %ptr.gep.remat1 = getelementptr i32, i32 addrspace(1)* %basephi.base.relocated.casted, i32 15
+  ; CHECK: %ptr.cast.remat = bitcast i32 addrspace(1)* %ptr.gep.remat1 to i64 addrspace(1)*
+  ; CHECK: %ptr.gep.remat = getelementptr i32, i32 addrspace(1)* %basephi.base.relocated.casted, i32 15
+  ; CHECK: %ptr.cast2.remat = bitcast i32 addrspace(1)* %ptr.gep.remat to i16 addrspace(1)*
+  ; CHECK: call void @use_obj64(i64 addrspace(1)* %ptr.cast.remat)
+  ; CHECK: call void @use_obj16(i16 addrspace(1)* %ptr.cast2.remat)
+  call void @use_obj64(i64 addrspace(1)* %ptr.cast)
+  call void @use_obj16(i16 addrspace(1)* %ptr.cast2)
+  ret void
+}