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$ Commented Nov 27, 2023 at 11:26
  • 1
    $\begingroup$ developers.redhat.com/blog/2021/04/28/… $\endgroup$ Commented Nov 27, 2023 at 17:03
  • 1
    $\begingroup$ @Moonchild It would be great if you could expand that link into an answer! $\endgroup$ 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$ 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$ 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$ Commented Nov 27, 2023 at 15:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.