Clean up CFG on JumpThreading

[arkangath]

Summary

In some loop situations, when the loop blocks become unreachable, JumpThreading would leave dead blocks behind. It could also generate self-referencing instructions (on a dead cfg).

This patch cleans up those blocks.

[lebedev.ri]

Note that for unreachable IR, self-referencing, and other forms of invalidity of IR, is legal.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

451

Would it not be sufficient to just add the block into Unreachable set?

[arkangath]

In D138027#3927365, @lebedev.ri wrote:

Note that for unreachable IR, self-referencing, and other forms of invalidity of IR, is legal.

Yup, I'm aware :)
Nevertheless, it's probably good form to clean up after a pass.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

451

I don't know - the code I copied it from already did this, so I just kept it.

[arkangath]

Ping

[nikic]

This doesn't really make sense to me. It deletes trivial cycles, but there may be dead cycles that are larger.

[arkangath]

In D138027#4004662, @nikic wrote:

This doesn't really make sense to me. It deletes trivial cycles, but there may be dead cycles that are larger.

I don't understand what you mean.
Should the patch be rejected because it doesn't clean *everything* ?

[lebedev.ri]

Please can you explain the larger goal you are trying to achieve here?
The minimal test you've added is very minimal, and does not show any ill-behaviour.

llvm/test/Transforms/JumpThreading/self-block.ll

1

The old result is not a misompile: https://godbolt.org/z/Ecf181P75
Unreachable code can take many weird forms.

[nikic]

In D138027#4004683, @arkangath wrote:

In D138027#4004662, @nikic wrote:

This doesn't really make sense to me. It deletes trivial cycles, but there may be dead cycles that are larger.

I don't understand what you mean.
Should the patch be rejected because it doesn't clean *everything* ?

Yes. Doing this in JumpThreading makes sense only if it avoids issues related to self-referential instructions (inside JumpThreading), and it cannot do so unless it removes all unreachable blocks. For example, I don't think it covers the case from https://reviews.llvm.org/D139783.

If this is *not* about self-referential instructions breaking JumpThreading itself, then you need to make the motivation for this clearer -- for example, are you addressing a phase ordering problem? (If so, please add a phase ordering test.)

[arkangath]

I am aware that the IR after the transformation is legal (as I mentioned in a previous comment).

In the larger scope of things, LLVm is being used as a compiler toolchain for a commercial project (sorry for being coy, but you know how big corp is... and I'm not particularly happy about it either).
There is another transform pass being run after JumpThreading which iterates over the blocks on a function, without checking their reachability or checking the CFG. That pass errors beause it finds a self-referencing instruction. Whether that instruction is reachable or not is irrelevant. I suggested to the team to just run CFGSimplify (or CSE I guess), but that has a compile-time cost, and if JumpThreading already knows the blocks are dead, might as well drop them there and then.

As for more complicated inputs, I would welcome an example. I thought that JumpThreading would eventually reduce any unreachable CFG into a self-referencing block. Nevertheless, _some_ clean up is better than no clean up?

llvm/test/Transforms/JumpThreading/self-block.ll

1

Yes, I am aware. What change is being requested?

[lebedev.ri]

In D138027#4004728, @arkangath wrote:

I am aware that the IR after the transformation is legal (as I mentioned in a previous comment).

In the larger scope of things, LLVm is being used as a compiler toolchain for a commercial project (sorry for being coy, but you know how big corp is... and I'm not particularly happy about it either).
There is another transform pass being run after JumpThreading which iterates over the blocks on a function, without checking their reachability or checking the CFG.

Is that an upstream pass, or a downstream one?

That pass errors beause it finds a self-referencing instruction. Whether that instruction is reachable or not is irrelevant. I suggested to the team to just run CFGSimplify (or CSE I guess), but that has a compile-time cost, and if JumpThreading already knows the blocks are dead, might as well drop them there and then.

As for more complicated inputs, I would welcome an example. I thought that JumpThreading would eventually reduce any unreachable CFG into a self-referencing block. Nevertheless, _some_ clean up is better than no clean up?

[nikic]

In D138027#4004728, @arkangath wrote:

I am aware that the IR after the transformation is legal (as I mentioned in a previous comment).

In the larger scope of things, LLVm is being used as a compiler toolchain for a commercial project (sorry for being coy, but you know how big corp is... and I'm not particularly happy about it either).
There is another transform pass being run after JumpThreading which iterates over the blocks on a function, without checking their reachability or checking the CFG. That pass errors beause it finds a self-referencing instruction. Whether that instruction is reachable or not is irrelevant. I suggested to the team to just run CFGSimplify (or CSE I guess), but that has a compile-time cost, and if JumpThreading already knows the blocks are dead, might as well drop them there and then.

Pass correctness cannot depend on their position in the pipeline. If a pass cannot deal with self-referential IR (by skipping unreachable blocks or in some other way), that's a problem with that pass, not whatever produced the IR.

[arkangath]

Is that an upstream pass, or a downstream one?

Ok took me a while to figure it out, but it appears to be a downstream pass which does something like
for (auto &BB : F)

for (auto &I : BB)

and then infinite-recurses when trying to transform a BinaryOperator.

The .ll file I added on the patch is a bugpoint reduced case.
Incidentally, we have a different patch fixing D139783 but that's not relevant for this case.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

for (auto &BB : F) {
 
       if (pred_empty(&BB)) {
         // When processBlock makes BB unreachable it doesn't bother to fix up
         // the instructions in it. We must remove BB to prevent invalid IR.
         LLVM_DEBUG(dbgs() << "  JT: Deleting dead block '" << BB.getName()
                           << "' with terminator: " << *BB.getTerminator()
                           << '\n');
         LoopHeaders.erase(&BB);
         LVI->eraseBlock(&BB);
+        // If the removed block is a predecessor of a loop block
+        // (referencing itself), then there might be PHIs that will
+        // be simplifiable.  Preserve those to prevent invalid IR.
+        DeleteDeadBlock(&BB, DTU, true);
+        Changed = true;
+        continue;
+      }
+
+      if (pred_size(&BB) == 1 && *pred_begin(&BB) == &BB) {
+        LoopHeaders.erase(&BB);
+        LVI->eraseBlock(&BB);
+        // Manually remove the terminator, otherwise the block
+        // deletion will see a pending reference to the Value being
+        // destroyed, which will trigger assertions.
+        BB.getTerminator()->eraseFromParent();
         DeleteDeadBlock(&BB, DTU);
         Changed = true;
         continue;
       }
 
       // processBlock doesn't thread BBs with unconditional TIs. However, if BB
       // is "almost empty", we attempt to merge BB with its sole successor.
       auto *BI = dyn_cast<BranchInst>(BB.getTerminator());

llvm/test/Transforms/JumpThreading/removed-use.ll

 ; RUN: opt -S < %s -jump-threading | FileCheck %s
 ; CHECK-LABEL: @foo
 ; CHECK: bb6:
 ; CHECK-NEXT: ret void
-; CHECK: bb3:
-; CHECK: br label %bb3
+; CHECK-NOT: bb3:
 define void @foo() {
 entry:
   br i1 true, label %bb6, label %bb3
 
 bb3:
   %x0 = phi i32 [ undef, %entry ], [ %x1, %bb5 ]
   %y  = and i64 undef, 1
   %p  = icmp ne i64 %y, 0

llvm/test/Transforms/JumpThreading/self-block.ll

+; RUN: opt -S -jump-threading %s -o - | FileCheck %s
+
+; Verifies that a self-referencing BasicBlock gets culled.
+; Note: SimplifyCFG would also clean this up but the "add"
+; instruction would become self-referencing when the phi
+; is simplified.
+define void @test() {
+; CHECK-LABEL: @test
+; CHECK: bb397:
+; CHECK-NEXT: ret void
+; CHECK-NOT: bb243:
+entry:
+  br i1 true, label %bb397, label %bb215
+
+bb215:                                            ; preds = %entry
+  br label %bb243
+
+bb243:                                            ; preds = %bb243, %bb215
+  %_4792_ = phi i32 [ %_3125_, %bb243 ], [ 1, %bb215 ]
+  %_3125_ = add i32 %_4792_, 1
+  br label %bb243
+
+bb397:                                            ; preds = %entry
+  ret void
+}

llvm/test/Transforms/JumpThreading/unreachable-loops.ll

 ; This gets into a state that could cause instruction simplify
 ; to hang - an insertelement instruction has itself as an operand.
 
 define void @PR48362() {
 ;
 ; CHECK-LABEL: @PR48362(
 ; CHECK-NEXT:  cleanup.cont1500:
 ; CHECK-NEXT:    unreachable
-; CHECK:       if.end1733:
-; CHECK-NEXT:    [[I82:%.*]] = load i32, i32* undef, align 1
-; CHECK-NEXT:    [[TOBOOL1731_NOT:%.*]] = icmp eq i32 [[I82]], 0
-; CHECK-NEXT:    br label [[IF_END1733:%.*]]
+; CHECK-NOT:       if.end1733:
 ;
 cleanup1491:                                      ; preds = %for.body1140
   switch i32 0, label %cleanup2343.loopexit4 [
   i32 0, label %cleanup.cont1500
   i32 128, label %lbl_555.loopexit
   ]
 
 cleanup.cont1500:                                 ; preds = %cleanup1491