[JumpThreading] Missing optimization: thread over a nearly empty basicblock

[XChy]

Alive2 proof: https://alive2.llvm.org/ce/z/Lv9e4r

Description:

define i1 @src(i1 %c1) {
entry:                                      
  %c = call i1 @cond()
  br i1 %c, label %then, label %else

then:                                        
  call void @dummy()
  br i1 %c1, label %else, label %return

else:                                         
  br label %return

return:                                           
  %retval.0 = phi i1 [ true, %else ], [ false, %then ]
  ret i1 %retval.0
}

can be folded to:

define i1 @tgt(i1 %c1) {
entry:
  %c = call i1 @cond()
  br i1 %c, label %then, label %return

then:                                        
  call void @dummy()
  br i1 %c1, label %else, label %return

else:                                         
  br label %return

return:                                           
  %retval.0 = phi i1 [ true, %entry ], [ false, %then ], [true, %else]
  ret i1 %retval.0
}

The conditional branch in BB entry can thread directly through nearly empty BB else to return.

Real-world motivation

This snippet of IR is derived from auto-generated qemu/xxx/qapi-visit-dump.c (after inline and O3 pipeline).
The example above is a reduced version. If you're interested in the original suboptimal IR and optimal IR, contact me to get it(Too big to upload here).

Let me know if you can confirm that it's an optimization opportunity, thanks.

[elhewaty]

Hi, I find this one interesting. Can you mention a good starting point?

[XChy]

@elhewaty , I once worked on similar things in SimplifyCFG and JumpThreading pass (#67275). A possible solution is to relax the non-empty phis constraint at

llvm-project/llvm/lib/Transforms/Utils/Local.cpp

Line 1017 in a02a0e8

if (BB->phis().empty() || Succ->phis().empty())

, and then handle the empty basicblock without phi correctly.

[elhewaty]

@XChy why can't the branch in BB then folded directly to return instead of else, as else only goes to return, So shouldn't every jump to else goes to return?

[XChy]

@elhewaty , the phi in return constraints it. When coming from then, the phi is false. But when coming from else, the phi is true. If we thread then directly, we need to remove then from phi and the semantics changes.
Jumping from entry demands modification on the phi, as the motivating example shows.

[XChy]

This missed optimization opportunity also exists in CPython/_ctypes/_ctypes.c.