[LLVMdev] Optimizing Boolean Expression

[Eli Friedman]

On Thu, Jun 17, 2010 at 4:30 PM, Ehsan Amiri <ehsanamiri at gmail.com> wrote:
> Hello
>
> I compiled the following program using the web interface
>
> #include <stdio.h>
> #include <stdlib.h>
>
> int main(int argc, char **argv) {
>   int a; int b; int c; int d;
>   int X = 10;
>   a = 777;
>   b = a | (atoi(argv[1]));
>   c = b | (atoi(argv[2]));
>   a = c | (atoi(argv[4]));
>   b = a | (atoi(argv[5]));
>   d = b | (atoi(argv[6]));
>   a = d | (atoi(argv[7]));
>   b = a | (atoi(argv[8]));
>   c = b | (atoi(argv[9]));
>   if (c) {
>     X = 2000;
>   }
>   printf("%d\n", X);
>  return 0;
> }
>
>
> It is easy to see that the condition of the if statement will be satisfied,
> but non of the optimization levels of the web interface seem to understand
> this. If I remove all OR operations except the first two, then the code will
> be optimized as expected. I guess this is because InstCombine, SCCP or
> whatever pass who is responsible for this optimization is called a constant
> number of times rather than "enough times". (For example call it in a loop
> until it reports no simplification was done). Now my questions:
>
> 1- Is my understanding correct that this optimization is not done? Maybe if
> I choose flags correctly it is done?

Yes; instcombine normally handles situations like this, but there's a
recursion limit so pathological cases don't blow the stack and/or
cause very long running times.  In this particular case, I believe the
limit is in llvm::ComputeMaskedBits.

> 2- Do you think I can use LLVM library in way that this kind of optimization
> is performed? For example is it possible that I call passes responsible for
> this in a loop and then ask them in each iteration if they did something
> useful and then I stop when they say they didn't find something new?

I don't think there's any way to make a pass perform this optimization
without modifying the LLVM code or writing your own pass to perform
it.  Is this really an important case for you?

-Eli