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

    <tr>
        <th>Summary</th>
        <td>
            `isGuaranteedNotToBeUndefOrPoison` is taking too long to execute
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            slow-compile,
            llvm:optimizations,
            missed-optimization,
            llvm:analysis
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          DianQK
      </td>
    </tr>
</table>

<pre>
    Using the script can reproduce this:

```sh
#!/usr/bin/env bash

num_switches="$1"

cat <<EOF
define i64 @foo(i64 noundef %i) {
start:
  br label %loop

loop:
EOF
echo -n "  %nonpoison = phi i64 [ 0, %start ]"

for i in $(seq 0 $((num_switches - 1))); do
  echo -n ", [ %nonpoison, %bb$i ]"
done

echo ", [ %nonpoison, %bb ], [ %i, %back_to_loop ]"

cat <<EOF
  switch i64 %i, label %exit0 [
    i64 -1, label %exit1
    i64 2, label %back_to_loop
    i64 0, label %bb
 ]

exit0:
  br label %exit1

exit1:
  %r = phi i64 [ %nonpoison, %loop ], [ undef, %exit0 ]
  ret i64 %r

back_to_loop:
  br label %loop

bb:
  switch i64 %nonpoison, label %loop [
EOF

for i in $(seq 0 $((num_switches - 1))); do
  echo "    i64 $i, label %bb$i"
done
cat <<EOF
  ]

EOF

for i in $(seq 0 $((num_switches - 1))); do
  echo "bb$i:"
  echo "  br label %loop"
done

echo "}"
```

```sh
./gen.sh 50 | opt -passes=instsimplify --disable-output
```

This is primarily due to a recursive check we're performing on a phi node that contains itself:
`%nonpoison = phi i64 [ 0, %start ], [ %nonpoison, %bb0 ], [ %nonpoison, %bb1 ], [ %nonpoison, %bb2 ], [ %nonpoison, %bb3 ], ..., [ %nonpoison, %bbn ], [ %nonpoison, %bb ], [ %i, %back_to_loop ]`.

The following code explains why returning true after exceeding the recursion depth:
https://github.com/llvm/llvm-project/blob/d6c0839c9c823754fb84e47c5bacf1a3b3d0f618/llvm/lib/Analysis/ValueTracking.cpp#L7885-L7889
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy0Vk2P4zYM_TXKhUggS_7KwYdk0vTQotsCu70uZJmO1XEkV5Lno7--kGxnk5npTBdoASOxzSfy8ZGiLJxTJ41YkWxPGDsooX_7iTBGssNKjL4ztprerWrTPFdfnNIn8B2Ck1YNHqTQYHGwphklgu-UI3xHaLxyOl2uC0-ME5YQdhydJexYK03YEfUD1GKy050ez1_do_KyQ0f4IbBgaRL-olkKD4TfEX73w6cjobsGW6URVJ4CSWlrDGFleNBm1A22QFimCNsCKfaE7pwX1k_cAGoLvaixD5jemGEKEO8iYgqAsjOw1kAYg4DURg9GOaOB8AMMnZpiZ3ughN0FRAwCJDtcSLfGggIVnKSElQ7_BDrfE1ZeZwxrSAjbzhffQ2Mi1ysWMUq2v-EyR65rwlL1LXRjNE4M4vqPFk8LLwC1GIS8_-rN16DMTVovawEwpTEpMju4SIxPytPgOyIhgtbJK0hyZWY31mseVyB6C6qDKbCc8g5B3yr4EmrGJAuGsMy-quwban0TY9IrdttsWzI9RI8W_SKInQLeJPJuM9b1Yr9V9obNzbpZ4Kkg_13rxe6HOXyqXkoeX1113OvOuFTkf2A2E-C7icM15Vey_tO-KJa2XubVW-NrQ9jxhHrjOsgokOIOzOBhPQjn4rBS2nmnzkOv2mdYrxvlRN3j2ox-GP1r55875UA5GKw6C6v6Z2hGBG9AgEU5WqceEGSH8h4ekbDCIgxoW2PPYf4aDSJ2qTZNGLrCgzTaC6UdKO-wb-chnNPvHVvvzAj6ISL5EME-RPAFsdls3gXqD13926GW081SFYTW9L15DCrLIC4-DX3U9bF7Dvt5tDqegHZEEK1HC_gkEZvlWJyrZzQ0OPhuqkPn_RDPRXYMbaR8N9Ybac6EHfv-YflbD9b8gdKH07E3NWHHJpe05Fu5lSXjRZa2dZliWsiQQpsIXvOGtnlSXvlRYd1Oi_7ZKUfY8XfRj_jZCnmv9Gkjh4Ew_nNRltk6_G5XTcWbLd-KFVZJkSasoAVPV11VlEVbcMmSvC3TGstUJq1EkdKcM9y2yUpVjLKMcponaVJm6YZludxShikXgtIcSUrxLFS_CdQ2xp5WyrkRq4TTJKGruDfd_NnhevO4luY8qB6no4owFlPiOzN4dVZ_Ca-MdhfjWTmHzfra-HKhuKgQv2ZsFUWux5MjKe2V8-4bNa98jxXJqXI_jsIK7RGbX4z_bPb4Jcz3T_bXqblyGvatF_ex4sZAb-IN4BPK0eNqtH313QWP0oR6zeo8VOzvAAAA__9a_sfs">