[LLVM][BranchFolding] Infinite loop happens in BranchFolding with BPF jumptable support

[yonghong-song]

The following commit is the anticipated bpf jump table support.
yonghong-song@1890225

But with the above commit, I found BranchFolding has an infinite loop.
The following is the reproducer:

1. Check out the above commit and do a build.

2. Source code:

$ cat test2.c
  int foo(int a, int b) {
    __label__ l1, l2, l3, l4;
    void *jt1[] = {[0]=&&l1, [1]=&&l2};
    void *jt2[] = {[0]=&&l3, [1]=&&l4};
    int ret = 0;

    goto *jt1[a % 2];
    l1: ret += 1;
    l2: ret += 3;
    goto *jt2[b % 2];
    l3: ret += 5;
    l4: ret += 7;
    return ret;
  }

3. The following clang compilation has a hang:

$ clang --target=bpf -O2 -S test2.c
^C

4. Then I added '-mllvm -debug-only=branch-folder'

$ clang --target=bpf -O2 -S test2.c -mllvm -debug-only=branch-folder >& log
^C
$ cat log
TryTailMergeBlocks: %bb.0, %bb.2
  with successor %bb.1
  which has fall-through from %bb.0
Looking for common tails of at least 3 instructions
Common tail length of %bb.2 and %bb.0 is 1

TryTailMergeBlocks: %bb.0, %bb.1
  with successor %bb.2
  which has fall-through from %bb.1
Looking for common tails of at least 3 instructions
Common tail length of %bb.1 and %bb.0 is 1

TryTailMergeBlocks: %bb.0, %bb.1, %bb.2
  with successor %bb.3
  which has fall-through from %bb.2
Looking for common tails of at least 3 instructions
Common tail length of %bb.2 and %bb.1 is 3
Common tail length of %bb.2 and %bb.0 is 1
Common tail length of %bb.1 and %bb.0 is 1

Using common tail in %bb.2 for %bb.1
Common tail length of %bb.2 and %bb.0 is 1

TryTailMergeBlocks: %bb.0, %bb.2
  with successor %bb.4
  which has fall-through from %bb.3
Looking for common tails of at least 3 instructions
Common tail length of %bb.2 and %bb.0 is 1

TryTailMergeBlocks: %bb.4, %bb.3
  with successor %bb.5
  which has fall-through from %bb.4
Looking for common tails of at least 3 instructions

TryTailMergeBlocks: %bb.0, %bb.2
  with successor %bb.1
  which has fall-through from %bb.0
Looking for common tails of at least 3 instructions
Common tail length of %bb.2 and %bb.0 is 1

TryTailMergeBlocks: %bb.0, %bb.1
  with successor %bb.2
  which has fall-through from %bb.1
Looking for common tails of at least 3 instructions

TryTailMergeBlocks: %bb.0, %bb.2
  with successor %bb.4
  which has fall-through from %bb.2
Looking for common tails of at least 3 instructions
Common tail length of %bb.2 and %bb.0 is 1

TryTailMergeBlocks: %bb.4, %bb.3
  with successor %bb.5
  which has fall-through from %bb.4
Looking for common tails of at least 3 instructions

TryTailMergeBlocks: %bb.0, %bb.2
  with successor %bb.3
  which has fall-through from %bb.5
Looking for common tails of at least 3 instructions
Common tail length of %bb.2 and %bb.0 is 1

...

There are infinite TryTailMergeBlocks ...

[yonghong-song]

cc @nikic @OCHyams @oskarwirga Could you help take a look? Or let me know if I missed proper person who can actually debug this issue.

[yonghong-song]

Let us temporarily disable BranchFolding optimization. The following is the final asm code:

        .type   foo,@function                                                                                                   
foo:                                    # @foo                                                                                  
# %bb.0:                                # %entry                                                                                
                                        # kill: def $w2 killed $w2 def $r2                                                      
                                        # kill: def $w1 killed $w1 def $r1                                                      
        w3 = w1                                                                                                                 
        w3 >>= 31                                                                                                               
        w4 = w1                                                                                                                 
        w4 += w3                                                                                                                
        w4 &= -2                                                                                                                
        w1 -= w4                                                                                                                
        w3 = w2                                                                                                                 
        w3 >>= 31                                                                                                               
        w4 = w2                                                                                                                 
        w4 += w3                                                                                                                
        w4 &= -2                                                                                                                
        w2 -= w4                                                                                                                
        r2 <<= 32                                                                                                               
        r2 s>>= 32                                                                                                              
        r2 <<= 3                                                                                                                
        r3 = .L__const.foo.jt2 ll                                                                                               
        r3 += r2                                                                                                                
        r1 <<= 32                                                                                                               
        r1 s>>= 32                                                                                                              
        r1 <<= 3                                                                                                                
        r2 = .L__const.foo.jt1 ll                                                                                               
        r2 += r1                                                                                                                
        w0 = 0                                                                                                                  
        r1 = *(u64 *)(r2 + 0)                                                                                                   
        gotox r1                                                                                                                
        goto LBB0_4
.Ltmp0:                                 # Block address taken                                                                   
LBB0_1:                                 # %l1                                                                                   
                                        # =>This Inner Loop Header: Depth=1                                                     
        w0 += 1                                                                                                                 
        w0 += 3
        r1 = *(u64 *)(r3 + 0)
        gotox r1
.Ltmp1:                                 # Block address taken
LBB0_2:                                 # %l2
                                        # =>This Inner Loop Header: Depth=1
        w0 += 3
        r1 = *(u64 *)(r3 + 0)
        gotox r1
.Ltmp2:                                 # Block address taken
LBB0_3:                                 # %l3
        w0 += 5
        goto LBB0_5
.Ltmp3:                                 # Block address taken
LBB0_4:                                 # %l4
LBB0_5:                                 # %.split17
        w0 += 7
        exit
.Lfunc_end0:
        .size   foo, .Lfunc_end0-foo

I think that the key thing is 'goto LBB0_4' insn. If 'goto LBB0_4' is removed as in latest #149715. The infinite loop in BranchFolding is gone and everything is fine.

But the code with 'goto LBB0_4' is still legal, so I think it is worthwhile to fix BranchFolding.

[yonghong-song]

Okay, I think

       gotox r1                                                                                                                
       goto LBB0_4

Probably really illegal. So close this issue.