[JumpThreading] Fix threading with unusual PHI nodes.

[efriedma]

Summary

If the block being cloned contains a PHI node, in general, we need to clone that PHI node, even though it's trivial. If the operand of the PHI is an instruction in the block being cloned, the correct value for the operand doesn't exist until SSAUpdater constructs it.

We usually don't hit this issue because we try to avoid threading across loop headers, but it's possible to hit this in some cases involving irreducible CFGs. I added a flag to allow threading across loop headers to make the testcase simpler.

Thanks to Brian Rzycki for reducing the testcase.

Fixes https://bugs.llvm.org/show_bug.cgi?id=42085.

[brzycki]

Hi @efriedma , thank you for debugging and identifying the true root cause of PR42085. My comments are inline.

lib/Transforms/Scalar/JumpThreading.cpp

110 ↗

(On Diff #206977)

I have concerns about adding this flag in this patch without a bit more testing and general test-cases for loop header threading. I fear this is a proverbial can of worms for any third party user of opt who discovers this flag and starts using it.

1993 ↗

(On Diff #206977)

Nit: please consider naming New to something like NewPN.

[efriedma]

lib/Transforms/Scalar/JumpThreading.cpp

110 ↗

(On Diff #206977)

Thinking about it a bit more, I think it's only possible to reproduce this issue if a PHI node operand is specifically another instruction in the same basic block, since we don't rewrite any other values. That implies the block dominates its predecessor, i.e. it's a loop header. This means either LoopHeaders computation is disabled, or it's falling out of date due to CFG changes.

If we remove this flag, the only way to test this change is to check an IR file where a transform causes the loop headers to fall out of date, then threading happens. Your original testcase works like this, but it's fragile: it could break in unintuitive ways due to other changes.

I'm not really concerned about adding experimental flags; it's something we do routinely, and it doesn't seem to cause any confusion. I can rename the flag if that helps?

[brzycki]

Hi @efriedma, comments are inline.

lib/Transforms/Scalar/JumpThreading.cpp

110 ↗

(On Diff #206977)

That implies the block dominates its predecessor, i.e. it's a loop header.

This helps me understand why I was down the path of LoopHeader analysis. In D63629 that's exactly what is happening: we calculate all loop headers and then immediately alter the state for trivially constant TIs causing the true loop headers to emerge to FindFunctionBackedges().

I think it's only possible to reproduce this issue if a PHI node operand is specifically another instruction in the same basic block, since we don't rewrite any other values.

I suspect you're right. The failing IR is unusual in several ways and I noticed this. I've never seen clang pass JT a CFG with this property.

I'm not really concerned about adding experimental flags; it's something we do routinely, and it doesn't seem to cause any confusion.

I've thought about it a bit more and agree with you. It'd be better to find the latent bugs in JT if external users enable the flag in their non-standard flows. I'm fine with leaving as-is.

[efriedma]

Fix variable name.

[brzycki]

LGTM.

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

cl::desc("The number of predecessors to search for a stronger "
            "condition to use to thread over a weaker condition"),
   cl::init(3), cl::Hidden);
 
 static cl::opt<bool> PrintLVIAfterJumpThreading(
     "print-lvi-after-jump-threading",
     cl::desc("Print the LazyValueInfo cache after JumpThreading"), cl::init(false),
     cl::Hidden);
 
+static cl::opt<bool> ThreadAcrossLoopHeaders(
+    "jump-threading-across-loop-headers",
+    cl::desc("Allow JumpThreading to thread across loop headers, for testing"),
+    cl::init(false), cl::Hidden);
+
+
 namespace {
 
   /// This pass performs 'jump threading', which looks at blocks that have
   /// multiple predecessors and multiple successors.  If one or more of the
   /// predecessors of the block can be proven to always jump to one of the
   /// successors, we forward the edge from the predecessor to the successor by
   /// duplicating the contents of this block.
   ///
bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
   SmallPtrSet<BasicBlock *, 16> Unreachable;
   assert(DTU && "DTU isn't passed into JumpThreading before using it.");
   assert(DTU->hasDomTree() && "JumpThreading relies on DomTree to proceed.");
   DominatorTree &DT = DTU->getDomTree();
   for (auto &BB : F)
     if (!DT.isReachableFromEntry(&BB))
       Unreachable.insert(&BB);
 
+  if (!ThreadAcrossLoopHeaders)
     FindLoopHeaders(F);
 
   bool EverChanged = false;
   bool Changed;
   do {
     Changed = false;
     for (auto &BB : F) {
       if (Unreachable.count(&BB))
         continue;
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   // Set the block frequency of NewBB.
   if (HasProfileData) {
     auto NewBBFreq =
         BFI->getBlockFreq(PredBB) * BPI->getEdgeProbability(PredBB, BB);
     BFI->setBlockFreq(NewBB, NewBBFreq.getFrequency());
   }
 
   BasicBlock::iterator BI = BB->begin();
-  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
-    ValueMapping[PN] = PN->getIncomingValueForBlock(PredBB);
+  // Clone the phi nodes of BB into NewBB. The resulting phi nodes are trivial,
+  // since NewBB only has one predecessor, but SSAUpdater might need to rewrite
+  // the operand of the cloned phi.
+  for (; PHINode *PN = dyn_cast<PHINode>(BI); ++BI) {
+    PHINode *NewPN = PHINode::Create(PN->getType(), 1, PN->getName(), NewBB);
+    NewPN->addIncoming(PN->getIncomingValueForBlock(PredBB), PredBB);
+    ValueMapping[PN] = NewPN;
+  }
 
   // Clone the non-phi instructions of BB into NewBB, keeping track of the
   // mapping and using it to remap operands in the cloned instructions.
   for (; !BI->isTerminator(); ++BI) {
     Instruction *New = BI->clone();
     New->setName(BI->getName());
     NewBB->getInstList().push_back(New);
     ValueMapping[&*BI] = New;

llvm/trunk/test/Transforms/JumpThreading/loop-phi.ll

+; RUN: opt < %s -jump-threading -S -jump-threading-across-loop-headers | FileCheck %s
+
+; Make sure we correctly distinguish between %tmp15 and %tmp16 when we clone
+; body2.
+
+; CHECK:      body2.thread:
+; CHECK-NEXT: %tmp163 = add i32 %tmp165, 1
+; CHECK-NEXT: br label %latch1
+
+; CHECK:      latch1:
+; CHECK-NEXT: %tmp165 = phi i32 [ %tmp163, %body2.thread ], [ %tmp16, %body2 ]
+; CHECK-NEXT: %tmp154 = phi i32 [ %tmp165, %body2.thread ], [ %tmp15, %body2 ]
+
+define i32 @test(i1 %ARG1, i1 %ARG2, i32 %n) {
+entry:
+  br label %head1
+
+head1:                                            ; preds = %entry, %body1
+  %tmp = phi i32 [ 0, %entry ], [ %tmp16, %body1 ]
+  %tmp3 = phi i32 [ 0, %entry ], [ %tmp16, %body1 ]
+  %tmp4 = phi i32 [ 0, %entry ], [ %tmp16, %body1 ]
+  br i1 %ARG1, label %exit, label %body2
+
+body1:                                            ; preds = %latch1
+  %tmp12 = icmp sgt i32 %tmp16, 1
+  br i1 %tmp12, label %body2, label %head1
+
+body2:                                            ; preds = %head1, %body1
+  %tmp14 = phi i32 [ %tmp16, %body1 ], [ %tmp, %head1 ]
+  %tmp15 = phi i32 [ %tmp16, %body1 ], [ %tmp3, %head1 ]
+  %tmp16 = add i32 %tmp14, 1
+  br i1 %ARG2, label %exit, label %latch1
+
+latch1:                                           ; preds = %body2
+  %tmp18 = icmp sgt i32 %tmp16, %n
+  br i1 %tmp18, label %exit, label %body1
+
+exit:                                             ; preds = %latch1, %body2, %head1
+  %rc = phi i32 [ %tmp15, %body2 ], [ %tmp15, %latch1 ], [ -1, %head1 ]
+  ret i32 %rc
+}

llvm/trunk/test/Transforms/JumpThreading/lvi-tristate.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -jump-threading -simplifycfg -S < %s | FileCheck %s
-; CHECK-NOT: bb6:
-; CHECK-NOT: bb7:
-; CHECK-NOT: bb8:
-; CHECK-NOT: bb11:
-; CHECK-NOT: bb12:
-; CHECK: bb:
-; CHECK: bb2:
-; CHECK: bb4:
-; CHECK: bb10:
-; CHECK: bb13:
 declare void @ham()
 
 define void @hoge() {
+; CHECK-LABEL: @hoge(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = and i32 undef, 1073741823
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[TMP]], 5
+; CHECK-NEXT:    br i1 [[COND]], label [[BB10:%.*]], label [[BB13:%.*]]
+; CHECK:       bb10:
+; CHECK-NEXT:    tail call void @ham()
+; CHECK-NEXT:    br label [[BB13]]
+; CHECK:       bb13:
+; CHECK-NEXT:    ret void
+;
 bb:
   %tmp = and i32 undef, 1073741823
   %tmp1 = icmp eq i32 %tmp, 2
   br i1 %tmp1, label %bb12, label %bb2
 
 bb2:
   %tmp3 = icmp eq i32 %tmp, 3
   br i1 %tmp3, label %bb13, label %bb4

llvm/trunk/test/Transforms/JumpThreading/select.ll

cond.false.15.i:                                  ; preds = %cond.false.10.i
   br label %.exit
 
 .exit:                                  ; preds = %entry, %cond.false.i, %cond.false.6.i, %cond.false.10.i, %cond.false.15.i
   %cond23.i = phi i1 [ false, %entry ], [ true, %cond.false.i ], [ false, %cond.false.6.i ], [ %phitmp, %cond.false.15.i ], [ true, %cond.false.10.i ]
   %j.add3 = select i1 %cond23.i, i32 %j, i32 %add3
   ret i32 %j.add3
 
 ; CHECK-LABEL: @unfold3
-; CHECK: br i1 %cmp.i, label %.exit.thread2, label %cond.false.i
+; CHECK: br i1 %cmp.i, label %.exit.thread3, label %cond.false.i
 ; CHECK: br i1 %cmp4.i, label %.exit.thread, label %cond.false.6.i
-; CHECK: br i1 %cmp8.i, label %.exit.thread2, label %cond.false.10.i
+; CHECK: br i1 %cmp8.i, label %.exit.thread3, label %cond.false.10.i
 ; CHECK: br i1 %cmp13.i, label %.exit.thread, label %.exit
-; CHECK: br i1 %phitmp, label %.exit.thread, label %.exit.thread2
-; CHECK: br label %.exit.thread2
+; CHECK: br i1 %phitmp, label %.exit.thread, label %.exit.thread3
+; CHECK: br label %.exit.thread3
 }
 
 define i32 @unfold4(i32 %u, i32 %v, i32 %w, i32 %x, i32 %y, i32 %z, i32 %j) nounwind {
 entry:
   %add3 = add nsw i32 %j, 2
   %cmp.i = icmp slt i32 %u, %v
   br i1 %cmp.i, label %.exit, label %cond.false.i
 

 .exit:                                  ; preds = %entry, %cond.false.i, %cond.false.6.i, %cond.false.10.i, %cond.false.15.i
   %cond23.i = phi i32 [ 1, %entry ], [ 0, %cond.false.i ], [ 1, %cond.false.6.i ], [ %conv, %cond.false.15.i ], [ 0, %cond.false.10.i ]
   %lnot.i18 = icmp eq i32 %cond23.i, 1
   %j.add3 = select i1 %lnot.i18, i32 %j, i32 %add3
   ret i32 %j.add3
 
 ; CHECK-LABEL: @unfold4
 ; CHECK: br i1 %cmp.i, label %.exit.thread, label %cond.false.i
-; CHECK: br i1 %cmp4.i, label %.exit.thread3, label %cond.false.6.i
+; CHECK: br i1 %cmp4.i, label %.exit.thread4, label %cond.false.6.i
 ; CHECK: br i1 %cmp8.i, label %.exit.thread, label %cond.false.10.i
-; CHECK: br i1 %cmp13.i, label %.exit.thread3, label %.exit
-; CHECK: br i1 %lnot.i18, label %.exit.thread, label %.exit.thread3
-; CHECK: br label %.exit.thread3
+; CHECK: br i1 %cmp13.i, label %.exit.thread4, label %.exit
+; CHECK: br i1 %lnot.i18, label %.exit.thread, label %.exit.thread4
+; CHECK: br label %.exit.thread4
 }
 
 define i32 @unfold5(i32 %u, i32 %v, i32 %w, i32 %x, i32 %y, i32 %z, i32 %j) nounwind {
 entry:
   %add3 = add nsw i32 %j, 2
   %cmp.i = icmp slt i32 %u, %v
   br i1 %cmp.i, label %.exit, label %cond.false.i
 

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

bb1:    ; preds = %entry, %bb
   br i1 %3, label %bb3, label %bb2
 
 bb2:    ; preds = %bb1
   %4 = tail call i32 (...) @f2() nounwind    ; <i32> [#uses=0]
   ret i32 %res.0
 
 bb3:    ; preds = %bb1
 ; CHECK: bb3:
-; CHECK: %res.01 = phi i32 [ 1, %bb1.thread ], [ 0, %bb1 ]
-; CHECK: ret i32 %res.01
+; CHECK: %res.02 = phi i32 [ 1, %bb1.thread ], [ 0, %bb1 ]
+; CHECK: ret i32 %res.02
   ret i32 %res.0
 }
 
 declare i32 @f1(...)
 
 declare i32 @f2(...)
 
 
bb1:    ; preds = %entry, %bb
   br i1 %3, label %bb3, label %bb2
 
 bb2:    ; preds = %bb1
   %4 = tail call i32 (...) @f2() nounwind
   ret i32 %res.0
 
 bb3:    ; preds = %bb1
 ; CHECK: bb3:
-; CHECK: %res.01 = phi i32 [ 1, %bb1.thread ], [ 0, %bb1 ]
-; CHECK: ret i32 %res.01
+; CHECK: %res.02 = phi i32 [ 1, %bb1.thread ], [ 0, %bb1 ]
+; CHECK: ret i32 %res.02
   ret i32 %res.0
 }
 
 define i32 @test3(i8** %x, i1 %f) {
 ; Correctly thread loads of different (but compatible) types, placing bitcasts
 ; as necessary in the predecessors. This is especially tricky because the same
 ; predecessor ends up with two entries in the PHI node and they must share
 ; a single cast.