6
$\begingroup$

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.

$\endgroup$
22
  • $\begingroup$ I guess the last example might be handled by the SSAPRE algorithm described here, but I found this paper very hard to understand. $\endgroup$
    – chrysante
    Commented Nov 27, 2023 at 11:26
  • 1
    $\begingroup$ developers.redhat.com/blog/2021/04/28/… $\endgroup$
    – Moonchild
    Commented Nov 27, 2023 at 17:03
  • 1
    $\begingroup$ @Moonchild It would be great if you could expand that link into an answer! $\endgroup$
    – Alexis King ♦
    Commented Nov 27, 2023 at 17:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – supercat
    Commented Nov 27, 2023 at 23:22
  • 1
    $\begingroup$ @Stef They're not mutually excluse, you would just have to schedule your proposed transform first. $\endgroup$
    – chrysante
    Commented Dec 1, 2023 at 13:23

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – chrysante
    Commented Nov 27, 2023 at 15:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .