The more_likely heuristic used in the RTLgen pass takes time O(n) where n is the size of the function and is called m times, where m = O(n) is the number of if-then-else statements in the function. This can result in O(n^2) behavior.
This PR avoids this problem by limiting the depth of recursive calls on if-then-else statements. It also puts a fixed upper limit on the return value of size_stmt, since comparing the sizes of two large statements is meaningless. (The interesting case performance-wise is when one of the statements is small.)
The
more_likelyheuristic used in the RTLgen pass takes time O(n) where n is the size of the function and is called m times, where m = O(n) is the number of if-then-else statements in the function. This can result in O(n^2) behavior.This PR avoids this problem by limiting the depth of recursive calls on if-then-else statements. It also puts a fixed upper limit on the return value of
size_stmt, since comparing the sizes of two large statements is meaningless. (The interesting case performance-wise is when one of the statements is small.)