<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/149712>149712</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [LLVM][BranchFolding] Infinite loop happens in BranchFolding with BPF jumptable support
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          yonghong-song
      </td>
    </tr>
</table>

<pre>
    The following commit is the anticipated bpf jump table support.
 https://github.com/yonghong-song/llvm-project/commit/18902253d63e6ec0c0a3650e8bab8b714a22be9d

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 ...

</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzsV19v2zYQ_zT0y8ECeZSs6MEPdlwDBVpsQLO9BpRESWxpUiCpFPn2Aymnrt2mNbJlG7ABhizweL-73_2heMJ71Rsp16TYkmK3EFMYrFs_WtMP1vRLb02_qG37uL4bJHRWa_tZmR4aezioAMpDGCQIE1SjRhFkC_XYwcfpMEIQtZbgp3G0LmSEbmAIYfSEbwjuCe57FYapzhp7ILg_M0hwr_XDYTk6-1E2geB-Nkdwz24qiljwdsXlSja0oYKvCipvalHf1CXLBWItq5bQDaGb7RTgswrD7GRtHyQ8Id3CW-jsZFrYOmGaYW91G4kNwoMwoEynjAoStLVjBoRuzvkfiTs5OttOjXSRVrLJMrgdZPMJ7BS-sQvCtNBaEFBPSrfZrIIZfLCTa-KuVh6RVvT4oxuCOTQiQJA-YNbEUIIyATprCd7ENxEJxZeaYAWk3MY99_da1FLf34NmUa4xPXl65oSnTQDwYFULBDcfA5urAAjfJZBiS0mxI3xHcEVwNcOQYsvOVpGUu--h4U_Q-HfR8jO0yMnJkDDovHyU9DbYk9cCCBaACSnpakb4ZlbFbdRmJ1CNFzJ-kp1go_v1JWzU5hfaxZPJ_EJQnpScDJMz8e9pLdI8TzPP4KLJtJhbbVRaBGXNXJ0wCNM_UyVJY7kMwvXR1C524_IXhOWHr6qHFG9uL5TzZNvAWxBtK2MCy-UhNiEsW1lP_dIa_RjxUrMsO6tb6QiWL_MBfo4NhL8huAJt-688PjbCvHjnHu-E0u-l6-VW2-ZTPFtiwuo6o6m20iumcKdjwE9NI7237ihis2hQzZBC2wmtl2FwduoH6Jw9fEGjm3fWfopJ6axLzWwNBKG0B9tBdEkKH4CDMj64qYnZ8oRubk87QUvThyHuPzqWToOjhXiisLm6r-TFnueFV_Jir8KL_Vle16SOX0kRXz11LFLkL8n1S4L4m3_6_D5pKvPFRndW2a9Yez9ITH5lYvi_pqfyEy_-PK_iSl75i3n9dUfa_yfaPxT9_Lrov_6h9J-sfX5d9Iu_NfpZll1cku4G6SQIJ09TxrfcYdZbtGveVrwSC7lmZcEpIl2tFsO6arsOi65aVaypC1GwiuUMeZfnWNZFRRdqjRQLWiJlOc9xlVVdLqpSFGWTszIvOpJTeRBKZ_EqllnXL5T3k1yzvCoZLtLs4NNciGjkZ0hSgvEyvHDrNKDVU-9JTrXywZ9gggo6DZTv3v3-Pl6di-3ZjBVngrdfz1cwiHGUxsdP2fk0ltK8_XWfJsqzgXIxOb3-wUAZvfl2jkwcfJwjZ5IPa_wjAAD__-WXo1w">