isGuaranteedNotToBeUndefOrPoison is taking too long to execute

[dianqk]

Using the script can reproduce this:

#!/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 "}"

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

llvm-project/llvm/lib/Analysis/ValueTracking.cpp

Lines 7885 to 7889 in d6c0839

	// If V is used as a branch condition before reaching CtxI, V cannot be
	// undef or poison.
	// br V, BB1, BB2
	// BB1:
	// CtxI ; V cannot be undef or poison here

[nikic]

/cherry-pick 462eb7e

[llvmbot]

/pull-request #130474