Optimizing Boolean Expression

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?

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?

Best
Ehsan

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

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.

I did a few other tests, it does optimization upto six ORs and stops optimizing when there are seven or more OR instructions.

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?

Optimizing Boolean expressions are really important for me. I may have long straight lines of Boolean operations and then I may want to optimize based on setting a variable to TRUE or FALSE. I think depths larger than six may happen sometimes in my application.

Something extra that I may need is this. I have a line of code a = b | c. Now I know for some reason that a = FALSE. This implies that b = FALSE and c = FALSE as well. Now I want to propagate all three values in the code and simplify as much as possible. Does by any chance LLVM do this?

Best
Ehsan