llvm dev - Aug 2021 - Unreachable CFG subcomponent produced by jump threading

Hi,

I have a program where during compilation an unreachable subcomponent of the CFG
was created after an edge is removed by jump threading. Looks like this
situation is not handled currently in jump threading. It would be great if
anyone can give some advice.

The snippet of the IR:

11:                                               ; preds = %32, %10
  %12 = phi i16 [ undef, %10 ], [ %21, %32 ]   ; after jump threading, [%21,
%32] will remain but %32 is already made unreachable
  %13 = load i1, i1* @f, align 8
  %14 = zext i1 %13 to i16
  br label %17

15:                                               ; preds = %22
  %16 = icmp slt i16 %23, 77
  br i1 %16, label %25, label %27

17:                                               ; preds = %25, %11
  %18 = phi i16 [ 0, %11 ], [ %26, %25 ]
  %19 = phi i16 [ %12, %11 ], [ %21, %25 ]
  br label %20

; CHECK: or
20:                                               ; preds = %17
  %21 = or i16 %19, %14
  store i16 %21, i16* %1, align 4, !tbaa !15
  br label %22

22:                                               ; preds = %20
  %23 = add i16 %18, 1
  %24 = icmp slt i16 %23, 7
  br i1 %24, label %25, label %15

25:                                               ; preds = %22, %15
  %26 = phi i16 [ %23, %22 ], [ 0, %15 ]
  br label %17, !llvm.loop !17

; This bb will be deleted because in bb15 the jump to here is removed.
27:                                               ; preds = %15
  br label %28

; This bb will become unreachable because bb27 is deleted, but it
; still has predecessor %32 so it won't be trivally deleted.
; CHECK-NOT: load i1, i1* @d
28:                                               ; preds = %27, %32
  %29 = phi i16 [ %33, %32 ], [ %23, %27 ]
  %30 = load i1, i1* @d, align 4
  br i1 %30, label %32, label %31

; This bb will become unreachable because bb27 is deleted.
; CHECK-NOT: store i1 true, i1* @f
31:                                               ; preds = %28
  store i1 true, i1* @f, align 8
  br label %32

; This bb will become unreachable because bb27 is deleted.
; CHECK-NOT: store i1 false, i1* @d
32:                                               ; preds = %31, %28
  %33 = and i16 %29, 11
  store i1 false, i1* @d, align 4
  %34 = icmp eq i16 %33, 0
  br i1 %34, label %11, label %28, !llvm.loop !19

As described in the IR comments, the branch to bb28 will be removed by jump
threading, then bb28, bb31, and bb32 will become unreachable, but %12 uses bb32
as incoming block which causes problems in later passes.

In the current jump threading implementation, if an incoming edge to a block is
removed and there is no predecessor left, the block will be deleted. But this
does not cover the situation above, because the unreachable blocks are connected
to each other. This is probably a corner case, but Iet me ask: should we enhance
jump threading to capture this scenario?

I can think of two fixes:

1.       Do some clean up to eliminate unreachable blocks at the end of jump
threading. This seems to violate some existing assumption. E.g. I saw this
comment from existing code:  "  // JumpThreading must not processes blocks
unreachable from entry. It's a waste of compute time and can potentially
lead to hangs."

2.       When each block is processed, identity the above scenario and deal with
it. This probably requires update of DT for every iteration? Which could be very
expensive.

Any advice/suggestion is greatly appreciated!

Thanks,
Duanyang

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210813/c8cb583e/attachment.html>

Can you post an actual IR that can be run through -jump-threading that
shows the problem?
What is the actual problem? What problems in later passes does it cause?|

Roman

On Sat, Aug 14, 2021 at 5:18 PM jingduanyang via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>
> Hi,
>
>
>
> I have a program where during compilation an unreachable subcomponent of
the CFG was created after an edge is removed by jump threading. Looks like this
situation is not handled currently in jump threading. It would be great if
anyone can give some advice.
>
>
>
> The snippet of the IR:
>
>
>
> 11:                                               ; preds = %32, %10
>
>   %12 = phi i16 [ undef, %10 ], [ %21, %32 ]   ; after jump threading,
[%21, %32] will remain but %32 is already made unreachable
>
>   %13 = load i1, i1* @f, align 8
>
>   %14 = zext i1 %13 to i16
>
>   br label %17
>
>
>
> 15:                                               ; preds = %22
>
>   %16 = icmp slt i16 %23, 77
>
>   br i1 %16, label %25, label %27
>
>
>
> 17:                                               ; preds = %25, %11
>
>   %18 = phi i16 [ 0, %11 ], [ %26, %25 ]
>
>   %19 = phi i16 [ %12, %11 ], [ %21, %25 ]
>
>   br label %20
>
>
>
> ; CHECK: or
>
> 20:                                               ; preds = %17
>
>   %21 = or i16 %19, %14
>
>   store i16 %21, i16* %1, align 4, !tbaa !15
>
>   br label %22
>
>
>
> 22:                                               ; preds = %20
>
>   %23 = add i16 %18, 1
>
>   %24 = icmp slt i16 %23, 7
>
>   br i1 %24, label %25, label %15
>
>
>
> 25:                                               ; preds = %22, %15
>
>   %26 = phi i16 [ %23, %22 ], [ 0, %15 ]
>
>   br label %17, !llvm.loop !17
>
>
>
> ; This bb will be deleted because in bb15 the jump to here is removed.
>
> 27:                                               ; preds = %15
>
>   br label %28
>
>
>
> ; This bb will become unreachable because bb27 is deleted, but it
>
> ; still has predecessor %32 so it won't be trivally deleted.
>
> ; CHECK-NOT: load i1, i1* @d
>
> 28:                                               ; preds = %27, %32
>
>   %29 = phi i16 [ %33, %32 ], [ %23, %27 ]
>
>   %30 = load i1, i1* @d, align 4
>
>   br i1 %30, label %32, label %31
>
>
>
> ; This bb will become unreachable because bb27 is deleted.
>
> ; CHECK-NOT: store i1 true, i1* @f
>
> 31:                                               ; preds = %28
>
>   store i1 true, i1* @f, align 8
>
>   br label %32
>
>
>
> ; This bb will become unreachable because bb27 is deleted.
>
> ; CHECK-NOT: store i1 false, i1* @d
>
> 32:                                               ; preds = %31, %28
>
>   %33 = and i16 %29, 11
>
>   store i1 false, i1* @d, align 4
>
>   %34 = icmp eq i16 %33, 0
>
>   br i1 %34, label %11, label %28, !llvm.loop !19
>
>
>
> As described in the IR comments, the branch to bb28 will be removed by jump
threading, then bb28, bb31, and bb32 will become unreachable, but %12 uses bb32
as incoming block which causes problems in later passes.
>
>
>
> In the current jump threading implementation, if an incoming edge to a
block is removed and there is no predecessor left, the block will be deleted.
But this does not cover the situation above, because the unreachable blocks are
connected to each other. This is probably a corner case, but Iet me ask: should
we enhance jump threading to capture this scenario?
>
>
>
> I can think of two fixes:
>
> 1.       Do some clean up to eliminate unreachable blocks at the end of
jump threading. This seems to violate some existing assumption. E.g. I saw this
comment from existing code:  “  // JumpThreading must not processes blocks
unreachable from entry. It's a waste of compute time and can potentially
lead to hangs.”
>
> 2.       When each block is processed, identity the above scenario and deal
with it. This probably requires update of DT for every iteration? Which could be
very expensive.
>
>
>
> Any advice/suggestion is greatly appreciated!
>
>
>
> Thanks,
>
> Duanyang
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev