[SimplifyCFG] Infinite loop of transformations on branch on widenable condition

[d-makogon]

I was investigating an xfailed test llvm/test/Transforms/SimplifyCFG/pr52290.ll. Running SimplifyCFG on it results in assert crash:

opt: llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp:240: bool iterativelySimplifyCFG(llvm::Function&, const llvm::TargetTransformInfo&, llvm::DomTreeUpdater*, const llvm::SimplifyCFGOptions&): Assertion `IterCnt++ < 1000 && "Iterative simplification didn't converge!"' failed.

Here is the IR:

define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb6, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb6:                                              ; preds = %bb2
  br label %bb7

bb7:                                              ; preds = %bb6, %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}

SimplifyCFG applies some certain set of transformations, and then applying another one reverts the IR to the state before those first transformations. It continues until the assert fails.

Here are the transformations applied step by step:

1. We simplify the unconditional branch in bb6:

define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb7, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb7:                                              ; preds = %bb2, %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}

2. Then update the bb2 to branch to bb1 on true condition (this is done by tryWidenCondBranchToCondBranch in SimplifyCFG.cpp):

define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb2, %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb1, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb7:                                              ; preds = %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}

3. Then (when trying to optimize conditional branch in bb1) decide that bb2 should branch to bb7 on true condition (through a new bb7.critedge block):

define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb7.critedge, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb7.critedge:                                     ; preds = %bb2
  br label %bb7

bb7:                                              ; preds = %bb7.critedge, %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}

Then repeat the same thing starting from step 1 over and over again.

Step 3 is done because SimplifyCFG looks at branch condition in bb1 which is undef and tries to find a "known value" for it in its predecessors. I think it supposes that if we came to bb1 from bb2, which also has a branch on undef, then it can assume undef in bb1 is true too, so it changes the br in bb2 to branch to bb7 on taken path.

Disabling step 2 transformation from here solves the issue and the infinite loop is gone.

Does anyone have ideas on how to resolve this? Maybe we should consider disabling the conditional br to conditional br widening?

[llvmbot]

@llvm/issue-subscribers-bug

[xortator]

One possible fix here is to insert unconditional branch on step 3. But step 2 still seems strange and doubtably profitable (even if correct) to me.
@d-makogon can you pls prototype a fix that would insert an unconditional branch?

[xortator]

Seems that undef isn't important for the bug, so my proposal doesn't stand. Alternatively, we can abstain from transform 2 when the dest block has the properties that make transform 3 possible (no side effects etc).

My strong preference would be to not widen guards in SimplifyCFG because it's just a wrong place for it, but I can't prove we don't need it.