[llvm-dev] Unreachable CFG subcomponent produced by jump threading

[Roman Lebedev via llvm-dev]

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