[CGP] Fix the rematerialization of gc.relocates

[skatkov]

Summary

If we want to substitute the relocation of derived pointer with gep of base then
we must ensure that relocation of base dominates the relocation of derived pointer.

Currently only check for basic block is present. However it is possible that both
relocation are in the same basic block but relocation of derived pointer is defined
earlier.

The patch moves the relocation of base pointer right before relocation of derived
pointer in this case.

[skatkov]

ping

[reames]

lib/CodeGen/CodeGenPrepare.cpp

951 ↗

(On Diff #110181)

Doing this linear scan of the basic block once per gc-relocate seems needless expensive compile time wise. I'd do one of the following:

1. Canonicalize the location of the base pointer before the derived relocations, run that code once per statepoint, then visit the gc-relocates only once it has run.
2. Reorganize the code to identify all remat candidates, then scan once for earliest required position, then materialize all including the moved base pointer.

Smaller comments:

• Group the BB check with the scan code since they're all handling the same case.
• Since we have to do the linear scan anyways, should we just handle the duplicate case at the same time?

956 ↗

(On Diff #110181)

Rather than scanning all instructions in the block, you can start at the statepoint.

[skatkov]

lib/CodeGen/CodeGenPrepare.cpp

951 ↗

(On Diff #110181)

It is not once per gc-relocate, it is once per RelocatedBase and all gc-relocate corresponding to RelocatedBase.

However I think I can do a bit smarter here. Specifically, I can check that the relocation I met before RelocatedBase is actually gc-relocate corresponding that base and move RelocatedBase right before this gc-relocate. So it should be faster and does not require utility map.

I will upload a new patch.

956 ↗

(On Diff #110181)

I cannot start with statepoint because it might be located in a different basic block then RelocateBase.

[reames]

LGTM

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

 }
 
 // Takes a RelocatedBase (base pointer relocation instruction) and Targets to
 // replace, computes a replacement, and affects it.
 static bool
 simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase,
                           const SmallVectorImpl<GCRelocateInst *> &Targets) {
   bool MadeChange = false;
+  // We must ensure the relocation of derived pointer is defined after
+  // relocation of base pointer. If we find a relocation corresponding to base
+  // defined earlier than relocation of base then we move relocation of base
+  // right before found relocation. We consider only relocation in the same
+  // basic block as relocation of base. Relocations from other basic block will
+  // be skipped by optimization and we do not care about them.
+  for (auto R = RelocatedBase->getParent()->getFirstInsertionPt();
+       &*R != RelocatedBase; ++R)
+    if (auto RI = dyn_cast<GCRelocateInst>(R))
+      if (RI->getStatepoint() == RelocatedBase->getStatepoint())
+        if (RI->getBasePtrIndex() == RelocatedBase->getBasePtrIndex()) {
+          RelocatedBase->moveBefore(RI);
+          break;
+        }
+
   for (GCRelocateInst *ToReplace : Targets) {
     assert(ToReplace->getBasePtrIndex() == RelocatedBase->getBasePtrIndex() &&
            "Not relocating a derived object of the original base object");
     if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
       // A duplicate relocate call. TODO: coalesce duplicates.
       continue;
     }
 

llvm/trunk/test/Transforms/CodeGenPrepare/statepoint-relocate.ll

 
 right:
        %ptr-base = call i32* @llvm.experimental.gc.relocate.p0i32(token %tok, i32 7, i32 7)
        ; CHECK: call i32* @llvm.experimental.gc.relocate.p0i32(token %tok, i32 7, i32 7)
        %ret-base = load i32, i32* %ptr-base
        ret i32 %ret-base
 }
 
+define i32 @test_sor_noop_same_bb(i1 %external-cond, i32* %base) gc "statepoint-example" {
+; CHECK-LABEL: @test_sor_noop_same_bb
+; Here base relocate doesn't dominate derived relocate. Make sure that we don't
+; produce undefined use of the relocated base pointer.
+entry:
+       %ptr1 = getelementptr i32, i32* %base, i32 15
+       ; CHECK: getelementptr i32, i32* %base, i32 15
+       %ptr2 = getelementptr i32, i32* %base, i32 5
+       ; CHECK: getelementptr i32, i32* %base, i32 5
+       %tok = call token (i64, i32, i1 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i1f(i64 0, i32 0, i1 ()* @return_i1, i32 0, i32 0, i32 0, i32 0, i32* %base, i32* %ptr1, i32* %ptr2)
+       ; CHECK: call i32* @llvm.experimental.gc.relocate.p0i32(token %tok, i32 7, i32 7)
+       %ptr2-new = call i32* @llvm.experimental.gc.relocate.p0i32(token %tok, i32 7, i32 9)
+       %ret2-new = load i32, i32* %ptr2-new
+       ; CHECK: getelementptr i32, i32* %base-new, i32 5
+       %ptr1-new = call i32* @llvm.experimental.gc.relocate.p0i32(token %tok, i32 7, i32 8)
+       %ret1-new = load i32, i32* %ptr1-new
+       ; CHECK: getelementptr i32, i32* %base-new, i32 15
+       %base-new = call i32* @llvm.experimental.gc.relocate.p0i32(token %tok, i32 7, i32 7)
+       %ret-new = add i32 %ret2-new, %ret1-new
+       ret i32 %ret-new
+}
+
 declare token @llvm.experimental.gc.statepoint.p0f_i1f(i64, i32, i1 ()*, i32, i32, ...)
 declare i32* @llvm.experimental.gc.relocate.p0i32(token, i32, i32)
 declare [3 x i32]* @llvm.experimental.gc.relocate.p0a3i32(token, i32, i32)