[JumpThreading] Perform phi-translation in SimplifyPartiallyRedundantLoad.

[trentxintong]

Summary

In case we are loading on a phi-load in SimplifyPartiallyRedundantLoad.
Try to phi translate it into incoming values in the predecessors before
we search for available loads.

This needs https://reviews.llvm.org/D30524

[trentxintong]

Update test.

[junbuml]

We had some discussion about improving this function in D30352. Based on that I added Renato and Daniel as reviewer.

lib/Transforms/Scalar/JumpThreading.cpp

1005 ↗

(On Diff #90359)

Maybe LI->isUnordered() ?

[trentxintong]

Address junbuml's comment.

lib/Transforms/Scalar/JumpThreading.cpp

1005 ↗

(On Diff #90359)

Good catch.

[trentxintong]

Gentle ping.

[• dberlin]

lib/Transforms/Scalar/JumpThreading.cpp

1009 ↗

(On Diff #90375)

Value actually has a doPhiTranslation you can use here.

[• dberlin]

LGTM once using DoPhiTranslation.

[trentxintong]

Address dberlin's comment.

[trentxintong]

@dberlin can you please also take a look at https://reviews.llvm.org/D30524 ? Its needed for this patch. Thanks!

[• dberlin]

lib/Transforms/Scalar/JumpThreading.cpp

940 ↗

(On Diff #91949)

This logic looks overly complex.

Isn't this all simply

TranslateableLoaddedPhiPtr = LoadedPtr->doPhiTranslation(LoadBB, PredBB)

here, and then

if (TranslateableLoadedPhiPtr == LoadedPtr)
    if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
    return false

(IE what it was before).

1011 ↗

(On Diff #91949)

And here, translateableloadedphiptr will already be LI->getOperand(0) (which is the pointer operand)
or LI->getPointerOperand (if the translation fails)

[trentxintong]

lib/Transforms/Scalar/JumpThreading.cpp

940 ↗

(On Diff #91949)

Do not we need the PredBB then ? we are not iterating over the predecessors here. Otherwise, I think doPhiTranslation would be a perfect fit for this.

[• dberlin]

lib/Transforms/Scalar/JumpThreading.cpp

940 ↗

(On Diff #91949)

good point, missed that. I would still simplify the logic

I would just define a helper:

static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB)
{
  if (Instruction *OpInst = dyn_cast<Instruction>(Op))
     if (OpInst->getParent() == BB)
       return true;
  return false;
}

Then here
if (opDefinedByBlock(LoadedPtr, LoadBB) && !isa<PHINode>(LoadedPtr))

return false;

and below, just always phi translate (phi translate returns either the original pointer, or the phi translated version, it never returns null)

[trentxintong]

Address dberlin's comments

[trentxintong]

@dberlin does this look good to you ? Thanks.

[• dberlin]

I already accepted it, so i can't accept it again :)
But LGTM.
Thank you for working through this :P

[trentxintong]

can you please also take a look at https://reviews.llvm.org/D30524. Its a preparation patch for this patch.

llvm/trunk/lib/Transforms/Scalar/JumpThreading.cpp

while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;
 }
 
+/// Return true if Op is an instruction defined in the given block.
+static bool isOpDefinedInBlock(Value *Op, BasicBlock *BB) {
+  if (Instruction *OpInst = dyn_cast<Instruction>(Op))
+    if (OpInst->getParent() == BB)
+      return true;
+  return false;
+}
+
 /// SimplifyPartiallyRedundantLoad - If LI is an obviously partially redundant
 /// load instruction, eliminate it by replacing it with a PHI node.  This is an
 /// important optimization that encourages jump threading, and needs to be run
 /// interlaced with other jump threading tasks.
 bool JumpThreadingPass::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
   // Don't hack volatile and ordered loads.
   if (!LI->isUnordered()) return false;
 
   // If the load is defined in a block with exactly one predecessor, it can't be
   // partially redundant.
   BasicBlock *LoadBB = LI->getParent();
   if (LoadBB->getSinglePredecessor())
     return false;
 
   // If the load is defined in an EH pad, it can't be partially redundant,
   // because the edges between the invoke and the EH pad cannot have other
   // instructions between them.
   if (LoadBB->isEHPad())
     return false;
 
   Value *LoadedPtr = LI->getOperand(0);
 
-  // If the loaded operand is defined in the LoadBB, it can't be available.
-  // TODO: Could do simple PHI translation, that would be fun :)
-  if (Instruction *PtrOp = dyn_cast<Instruction>(LoadedPtr))
-    if (PtrOp->getParent() == LoadBB)
-      return false;
+  // If the loaded operand is defined in the LoadBB and its not a phi,
+  // it can't be available in predecessors.
+  if (isOpDefinedInBlock(LoadedPtr, LoadBB) && !isa<PHINode>(LoadedPtr))
 
   // Scan a few instructions up from the load, to see if it is obviously live at
   // the entry to its block.
   BasicBlock::iterator BBIt(LI);
   bool IsLoadCSE;
   if (Value *AvailableVal = FindAvailableLoadedValue(
           LI, LoadBB, BBIt, DefMaxInstsToScan, AA, &IsLoadCSE)) {
     // If the value of the load is locally available within the block, just use
bool JumpThreadingPass::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
 
   // If we got here, the loaded value is transparent through to the start of the
   // block.  Check to see if it is available in any of the predecessor blocks.
   for (BasicBlock *PredBB : predecessors(LoadBB)) {
     // If we already scanned this predecessor, skip it.
     if (!PredsScanned.insert(PredBB).second)
       continue;
 
-    // Scan the predecessor to see if the value is available in the pred.
     BBIt = PredBB->end();
     unsigned NumScanedInst = 0;
-    Value *PredAvailable = FindAvailableLoadedValue(
-        LI, PredBB, BBIt, DefMaxInstsToScan, AA, &IsLoadCSE, &NumScanedInst);
+    Value *PredAvailable = nullptr;
+    // NOTE: We don't CSE load that is volatile or anything stronger than
+    // unordered, that should have been checked when we entered the function.
+    assert(LI->isUnordered() && "Attempting to CSE volatile or atomic loads");
+    // If this is a load on a phi pointer, phi-translate it and search
+    // for available load/store to the pointer in predecessors.
+    Value *Ptr = LoadedPtr->DoPHITranslation(LoadBB, PredBB);
+    PredAvailable = FindAvailablePtrLoadStore(
+        Ptr, LI->getType(), LI->isAtomic(), PredBB, BBIt, DefMaxInstsToScan,
+        nullptr, &IsLoadCSE, &NumScanedInst);
 
-    // If PredBB has a single predecessor, continue scanning through the single
-    // predecessor.
+    // If PredBB has a single predecessor, continue scanning through the
+    // single precessor.
     BasicBlock *SinglePredBB = PredBB;
     while (!PredAvailable && SinglePredBB && BBIt == SinglePredBB->begin() &&
            NumScanedInst < DefMaxInstsToScan) {
       SinglePredBB = SinglePredBB->getSinglePredecessor();
       if (SinglePredBB) {
         BBIt = SinglePredBB->end();
-        PredAvailable = FindAvailableLoadedValue(
-            LI, SinglePredBB, BBIt, (DefMaxInstsToScan - NumScanedInst), AA,
-            &IsLoadCSE, &NumScanedInst);
+        PredAvailable = FindAvailablePtrLoadStore(
+            Ptr, LI->getType(), LI->isAtomic(), SinglePredBB, BBIt,
+            (DefMaxInstsToScan - NumScanedInst), nullptr, &IsLoadCSE,
+            &NumScanedInst);
       }
     }
 
     if (!PredAvailable) {
       OneUnavailablePred = PredBB;
       continue;
     }
 
bool JumpThreadingPass::SimplifyPartiallyRedundantLoad(LoadInst *LI) {
   }
 
   // If the value isn't available in all predecessors, then there will be
   // exactly one where it isn't available.  Insert a load on that edge and add
   // it to the AvailablePreds list.
   if (UnavailablePred) {
     assert(UnavailablePred->getTerminator()->getNumSuccessors() == 1 &&
            "Can't handle critical edge here!");
-    LoadInst *NewVal =
-        new LoadInst(LoadedPtr, LI->getName() + ".pr", false,
-                     LI->getAlignment(), LI->getOrdering(), LI->getSynchScope(),
-                     UnavailablePred->getTerminator());
+    LoadInst *NewVal = new LoadInst(
+        LoadedPtr->DoPHITranslation(LoadBB, UnavailablePred),
+        LI->getName() + ".pr", false, LI->getAlignment(), LI->getOrdering(),
+        LI->getSynchScope(), UnavailablePred->getTerminator());
     NewVal->setDebugLoc(LI->getDebugLoc());
     if (AATags)
       NewVal->setAAMetadata(AATags);
 
     AvailablePreds.push_back(std::make_pair(UnavailablePred, NewVal));
   }
 
   // Now we know that each predecessor of this block has a value in

llvm/trunk/test/Transforms/JumpThreading/thread-loads.ll

 end:
   ret i32 0
 }
 
 declare void @fn2(i64)
 declare void @fn3(i64)
 
 
+; Make sure we phi-translate and make the partially redundant load in
+; merge fully redudant and then we can jump-thread the block with the
+; store.
+;
+; CHECK-LABEL: define i32 @phi_translate_partial_redundant_loads(i32, i32*, i32*
+; CHECK: merge.thread:
+; CHECK: store
+; CHECK: br label %left_x
+;
+; CHECK: left_x:
+; CHECK-NEXT: ret i32 20
+define i32 @phi_translate_partial_redundant_loads(i32, i32*, i32*)  {
+  %cmp0 = icmp ne i32 %0, 0
+  br i1 %cmp0, label %left, label %right
+
+left:
+  store i32 1, i32* %1, align 4
+  br label %merge
+
+right:
+  br label %merge
+
+merge:
+  %phiptr = phi i32* [ %1, %left ], [ %2, %right ]
+  %newload = load i32, i32* %phiptr, align 4
+  %cmp1 = icmp slt i32 %newload, 5
+  br i1 %cmp1, label %left_x, label %right_x
+
+left_x:
+  ret i32 20
+
+right_x:
+  ret i32 10
+}
+
 !0 = !{!3, !3, i64 0}
 !1 = !{!"omnipotent char", !2}
 !2 = !{!"Simple C/C++ TBAA"}
 !3 = !{!"int", !1}
 !4 = !{ i32 0, i32 1 }
 !5 = !{ i32 8, i32 10 }
 !6 = !{!6}
 !7 = !{!7, !6}
 !8 = !{!8, !6}
 !9 = !{!7}
 !10 = !{!8}