# Optimization algorithm using conditional invariants

I am looking for an optimization algorithm that would make use of invariants in regions of code. For example

if (n == 0) f(n);


should be changed to

if (n == 0) f(0);


or

if (n >= 0) {
// ...
if (n <= 0) f(n);
if (n < 0) ...
}


should be changed to

if (n >= 0) {
// ...
if (n <= 0) f(0);
if (false) ...
}


Now I could come up with an algorithm that does this for these simple cases (basically traverse a dominator tree of the function, keep track of all given conditions, annotate uses and then do a formal evaluation). But I wonder if there are any more general algorithms that do the above transform and perhaps more sophisticated optimizations.

For example I could image this case:

if (i % 2 == 0) {
bool cond1 = i % 3 == 0;
bool cond2 = i % 6 == 0;
}


Here cond1 and cond2 always have the same value and thus one computation can be elided, but I have no idea on how to implement such a transform.

My compiler uses SSA form somewhat similar to LLVM IR.

• I guess the last example might be handled by the SSAPRE algorithm described here, but I found this paper very hard to understand. Nov 27, 2023 at 11:26
• developers.redhat.com/blog/2021/04/28/… Nov 27, 2023 at 17:03
• @Moonchild It would be great if you could expand that link into an answer! Nov 27, 2023 at 17:58
• @chrysante: I chose the particular looping construct because it's the simplest one I've found where clang, even at the -O1 setting, will transform code whose components all uphold memory-safety invariants into code which does not; gcc will do likewise when configured for C++, but when configured for C code it always generates code for the loop. A more useful behavior would be to omit the loop while keeping the bounds check, but neither clang nor gcc does that. Nov 27, 2023 at 23:22
• @Stef They're not mutually excluse, you would just have to schedule your proposed transform first. Dec 1, 2023 at 13:23

The first examples with just less than and greater than can be solved using range-based invariants.

Each time you pass a branch the condition of that branch gets added to the invariants of the scope.

Then you have optimizations rewrite rules that involve (n >= A) => (n < A) == false and similar rules.

Doing the same with modulo invariants is more complicated. It would require something like decomposing a i % A*B == C into (i % A == C%A) && (i % B == C*B) (proving this is correct in at least this cases). And then finding that one of them matches a invariant.

• Thanks, but I guess this is what I meant with traverse a dominator tree of the function, keep track of all given conditions, annotate uses and then do a formal evaluation. But before I spend hours implementing that I wanted to know if there is anything more powerful (which there probably is) Nov 27, 2023 at 15:09