[ConstraintElim] Add option to limit number of rows tracked in system.
Once the constraint system grows too large in terms of number of rows,
queries can become very slow. This patch adds a new option to limit the
number of rows tracked.
The python script below can be used to generate worst-case IR with a
chain of conditional branches with N branches.
With this limit, we get the following runtimes:
* python3 generate.py 100: 0.1s
* python3 generate.py 1000: 2s
* python3 generate.py 10000: 4s
Without the limit, the case with 1000 chained conditions takes 20+
seconds.
generate.py:
import sys
N = int(sys.argv[1])
args = []
checks = []
for i in range(0, N):
args.append('i32 %l{}'.format(i))
checks.append("""
bb{0}:
%c{0} = icmp uge i32 %l{0}, 100
br i1 %c{0}, label %bb{1}, label %exit
""".format(i, i+1))
print("""
define i1 @foo({0}) {{
{1}
bb{2}:
%c{2} = icmp uge i32 %l0, 100
ret i1 %c{2}
exit:
ret i1 false
}}
""".format(' ,'.join(args), '\n'.join(checks), N))
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D140926