Recursion in LibCallSimplifier

Hi all,

Can someone suggest an appropriate way to go about implementing a recursive LibCallSimplifier transformation, one that can restore the effects of calls to one or more IRBuilder::createXxx() functions if a nested simplification step fails?

As a motivating example consider the following:

extern char a[];
const char s3[] = "123";
const char s5[] = "12345";
size_t f (_Bool x, int i)
  return strlen (x ? s3 + i: s5 + i);

Because the contents of the s3 and s5 strings are known, the strlen() call above can be folded to x ? 3 - i : 5 - i in two (possibly recursive) steps, one for each subexpression of the ternary expression. (The transformations are already done for the simpler calls strlen(s3 - i) and strlen(x ? s3 : s5).)

On the other hand, the call below cannot be folded because nothing is known about a:

size_t g (_Bool x, int i)
  return strlen (x ? s3 + i: a + i);

Because the ternary expressions can nest arbitrarily deep, a fully general folder lends itself to a recursive implementation. If any step of the recursion fails, either a) the effects of all prior steps on the IR need to be reversed, or b) the IR must not change until all steps succeed.

LibCallSimplifier calls the IRBuilder class convenience members to build up simplified expressions and insert them into the IR. With that, a) above would seem a suitable approach. Unfortunately, since it changes the IR (the first time to add instructions and then to remove them), it means that any but the first simplification failure causes InstCombinePass to loop indefinitely as it revisits the same instructions after each change. I haven’t found a way to avoid this so I’m wondering if I either missed something or if b) would be the right approach, or if there’s some other solution altogether.

Thanks in advance!

Disclaimer: not the code area I’m most familiar with.

A possible approach would be to 1) check if the expression is foldable and 2) if it is, perform the actual fold. It sounds better than adding and eventually removing them, but it also means a two-pass walk through the IR. Another (unorthodox) approach would be to build the transformation as the analysis goes, as a composition of function on the IR, and run the function once the test passes.

Thanks for the suggestions, Serge. I took the second approach in ⚙ D122686 [InstCombine] Fold calls to strnlen (PR46455).