[JumpThreading] Don't try to rewrite a use if it's already valid.

[mzolotukhin]

Summary

When recording uses we need to rewrite after cloning a loop we need to
check if the use is not dominated by the original def. The initial
assumption was that the cloned basic block will introduce a new path and
thus the original def will only dominate the use if they are in the same
BB, but as the reproducer from PR37745 shows it's not always the case.

This fixes PR37745.

[Ka-Ka]

The fix solves the problem I saw originally in a out of tree target (described in PR37745) but I don't know JumpThreading enough to say if the fix is good or not. Thanks for working on this.

[mzolotukhin]

Could anyone review this fix please?

[davide]

LGTM. @kuhar ?

[kuhar]

In D48111#1138598, @davide wrote:

LGTM. @kuhar ?

I'm not familiar with this part of the optimizer enough to say anything more than it doesn't look obviously broken to me.

[brzycki]

This problem seems to be aggravated by the new SSAUpdaterBulk() patch pushed on May 12 ( D44282 ) since the PR37745.ll test case does not fail before that date. I don't understand the SSA updater change enough to understand why this problem only happens with the new bulk updates, @mzolotukhin do you happen to know why?

This is a minimal fix, much smaller than the big SSA changes so other than my request for a comment change it LGTM.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

2032

Please add a comment stating why the domination check should be skipped: it's non-trivial as it's a different check than the User is BB in the old code.

[mzolotukhin]

do you happen to know why?

The difference compared to the old SSAUpdater is in how we handled uses and defs located in the same block - it did not lead to a problem with the old SSAUpdater, but was unnecessary anyway, since such uses don't need to be rewritten (not in general, but in this particular case when the use is still dominated by its existing def).

Michael

[brzycki]

In D48111#1144223, @mzolotukhin wrote:

do you happen to know why?

The difference compared to the old SSAUpdater is in how we handled uses and defs located in the same block - it did not lead to a problem with the old SSAUpdater, but was unnecessary anyway, since such uses don't need to be rewritten (not in general, but in this particular case when the use is still dominated by its existing def).

Michael

Thanks @mzolotukhin for the explanation. And for what it's worth, a delayed LGTM.

[mzolotukhin]

Thanks, Brian!

llvm/lib/Transforms/Scalar/JumpThreading.cpp

bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   // nodes in BB.
   TerminatorInst *PredTerm = PredBB->getTerminator();
   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
     if (PredTerm->getSuccessor(i) == BB) {
       BB->removePredecessor(PredBB, true);
       PredTerm->setSuccessor(i, NewBB);
     }
 
+  // Enqueue required DT updates.
+  DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
+                     {DominatorTree::Insert, PredBB, NewBB},
+                     {DominatorTree::Delete, PredBB, BB}});
+
+  // Apply all updates we queued with DDT and get the updated Dominator Tree.
+  DominatorTree *DT = &DDT->flush();
+
   // If there were values defined in BB that are used outside the block, then we
   // now have to update all uses of the value to use either the original value,
   // the cloned value, or some PHI derived value.  This can require arbitrary
   // PHI insertion, of which we are prepared to do, clean these up now.
   SSAUpdaterBulk SSAUpdate;
 
   for (Instruction &I : *BB) {
     SmallVector<Use*, 16> UsesToRename;
 
     // Scan all uses of this instruction to see if it is used outside of its
     // block, and if so, record them in UsesToRename. Also, skip phi operands
     // from PredBB - we'll remove them anyway.
     for (Use &U : I.uses()) {
       Instruction *User = cast<Instruction>(U.getUser());
       if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
         if (UserPN->getIncomingBlock(U) == BB ||
             UserPN->getIncomingBlock(U) == PredBB)
           continue;
-      } else if (User->getParent() == BB)
+      } else if (DT->dominates(&I, U))
         continue;
 
       UsesToRename.push_back(&U);
     }
 
     // If there are no uses outside the block, we're done with this instruction.
     if (UsesToRename.empty())
       continue;
     unsigned VarNum = SSAUpdate.AddVariable(I.getName(), I.getType());
 
     // We found a use of I outside of BB - we need to rename all uses of I that
     // are outside its block to be uses of the appropriate PHI node etc.
     SSAUpdate.AddAvailableValue(VarNum, BB, &I);
     SSAUpdate.AddAvailableValue(VarNum, NewBB, ValueMapping[&I]);
     for (auto *U : UsesToRename)
       SSAUpdate.AddUse(VarNum, U);
   }
 
-  DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
-                     {DominatorTree::Insert, PredBB, NewBB},
-                     {DominatorTree::Delete, PredBB, BB}});
-
-  // Apply all updates we queued with DDT and get the updated Dominator Tree.
-  DominatorTree *DT = &DDT->flush();
   SSAUpdate.RewriteAllUses(DT);
 
   // At this point, the IR is fully up to date and consistent.  Do a quick scan
   // over the new instructions and zap any that are constants or dead.  This
   // frequently happens because of phi translation.
   SimplifyInstructionsInBlock(NewBB, TLI);
 
   // Update the edge weight from BB to SuccBB, which should be less than before.

llvm/test/Transforms/JumpThreading/PR37745.ll

+; RUN: opt -jump-threading -verify-each -S -mtriple=x86_64-- -o - %s
+
+define void @foo() {
+entry:
+  br i1 false, label %A, label %B
+
+A:
+  %x = phi i32 [ undef, %entry ], [ %z, %B ]
+  br label %B
+
+B:
+  %y = phi i32 [ undef, %entry ], [ %x, %A ]
+  %z = add i32 %y, 1
+  %cmp = icmp ne i32 %z, 0
+  br i1 %cmp, label %exit, label %A
+
+exit:
+  ret void
+}