<p>I am looking for an optimization algorithm that would make use of invariants in regions of code. For example</p>
<pre><code>if (n == 0) f(n);
</code></pre>
<p>should be changed to</p>
<pre><code>if (n == 0) f(0);
</code></pre>
<p>or</p>
<pre><code>if (n &gt;= 0) {
    // ... 
    if (n &lt;= 0) f(n);
    if (n &lt; 0) ...
}
</code></pre>
<p>should be changed to</p>
<pre><code>if (n &gt;= 0) {
    // ... 
    if (n &lt;= 0) f(0);
    if (false) ...
}
</code></pre>
<p>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.</p>
<p>For example I could image this case:</p>
<pre><code>if (i % 2 == 0) {
    bool cond1 = i % 3 == 0;
    bool cond2 = i % 6 == 0;
}
</code></pre>
<p>Here <code>cond1</code> and <code>cond2</code> always have the same value and thus one computation can be elided, but I have no idea on how to implement such a transform.</p>
<p>My compiler uses SSA form somewhat similar to LLVM IR.</p>

<optimization><static-single-assignment>
Optimization algorithm using conditional invariants
CC BY-SA 4.0
2023-11-27T11:26:04.467Z
I guess the last example might be handled by the SSAPRE algorithm described [here](http://www.cs.cmu.edu/~hopper/745project/ssapre1.pdf), but I found this paper very hard to understand.
chrysante
CC BY-SA 4.0
2023-11-27T16:19:39.790Z
One of the optimizations you're describing is called constant [propagation](https://en.wikipedia.org/wiki/Constant_folding).  More advanced versions track multiple possible values, and/or equivalences (i is equal to j here), or conditions (i < 10 here).
Erik Eidt
CC BY-SA 4.0
2023-11-27T16:41:33.390Z
@ErikEidt I did implement "sparse conditional constant propagation" as described in [this paper](https://dl.acm.org/doi/pdf/10.1145/103135.103136) in chapter 3.4, but unless my implementation is incorrect this algorithm does not do these transforms. Is there a better constant propagation algorithm?
chrysante
CC BY-SA 4.0
2023-11-27T17:03:51.737Z
https://developers.redhat.com/blog/2021/04/28/value-range-propagation-in-gcc-with-project-ranger
Moonchild
CC BY-SA 4.0
2023-11-27T17:16:26.963Z
@Moonchild Thank you! Value range propagation might be the keyword I was looking for.
chrysante
CC BY-SA 4.0
2023-11-27T17:58:40.477Z
@Moonchild It would be great if you could expand that link into an answer!
Alexis King
CC BY-SA 4.0
2023-11-27T19:52:34.283Z
Such optimizations are dangerous unless one has a means of preserving control, sequencing, address, and data dependencies within the resulting code.  If `x` is a static array, then changing `if (p == x+1) *p=1; ` with `if (p == x+1) x[1] = 0;` would only be valid if all downstream processes would behave as though the left-hand operand of the assignment was based upon `p` rather than `x` (either because they recognize what's it's based on, or because they don't care).
supercat
CC BY-SA 4.0
2023-11-27T20:00:26.107Z
What kind of code are you seeking to optimize?  On many platforms, if `x` has just been found to equal something, using it will often be at least as efficient as using a constant, and if a programmer writes `if (x==5) foo(x);` rather than `if (x==5) foo(5);`, that would often suggest that either the programmer wasn't interested in any performance gains from using the latter form, or didn't expect that there would be any.
supercat
CC BY-SA 4.0
2023-11-27T20:22:49.150Z
@supercat _Such optimizations are dangerous unless one has a means of preserving control, sequencing, address, and data dependencies within the resulting code._ -- Yes, absolutely. Maybe I should have been more explicit with this, but the code is in SSA form, so every variable stays constant after its assignment. And the expression `foo(x)` is symbolic here. It may be a more complex expression, or even if it is just a function call, replacing the argument with a constant may motivate the inliner to inline the call if otherwise it hadn't.
chrysante
CC BY-SA 4.0
2023-11-27T20:23:26.880Z
@supercat It is for a general purpose programming language
chrysante
CC BY-SA 4.0
2023-11-27T20:25:03.870Z
@AlexisKing I don't really have anything useful to say other than 'look at existing resources on value range analysis'
Moonchild
CC BY-SA 4.0
2023-11-27T21:25:34.950Z
@chrysante: Even when using SSA form, maintaining dependencies may be important if one wants to allow optimizing transforms to reorder operations, but still ensure that invariants such a memory safety that are upheld by all individual parts of a program will be upheld by the program as a whole.
supercat
CC BY-SA 4.0
2023-11-27T21:47:15.917Z
@supercat I'm not sure if I understand you correctly. Sure, moving loads, stores or function calls around and changing their relativ order is generally not a safe transform, but replacing the use of one SSA value with another that is proven to be equal should be safe under all circumstances?
chrysante
CC BY-SA 4.0
2023-11-27T21:54:51.003Z
@chrysante: Suppose a loop like `while((i & 0xFFFF) != x) i*=3;` is followed by `if (x < 65536) arr[x]=1;`.  Looking at those two pieces of the code in isolation, neither would be able to modify `arr[65536]`, but applying the kind of inference described in the question (eliminating the `if`) without recording that doing so would require the assignment to `arr` to be sequenced after the execution of the loop (preventing its elision) could result in code being transformed in a manner that unconditionally stores 1 to `arr[x]`.
supercat
CC BY-SA 4.0
2023-11-27T22:00:36.943Z
@chrysante: Somewhat similar issues may arise if code which is running in a privileged context is using a pointer to data which can be accessed from a non-privileged thread.  If code does something like `x=*p; if (x < 65536) arr[x] = 123;` around the time that non-privileged code modifies `*p`, it may be acceptable for `x` to receive any value that `*p` has held or well hold, but only if *both uses of `x` act upon the same value*.
supercat
CC BY-SA 4.0
2023-11-27T22:38:56.193Z
@supercat In the first example if the while loop ever terminates x has to be less than 65536 and thus the if statement can be executed unconditionally. So yes the while loop has to be sequenced before the if statement, otherwise we could not make that assumption. I hope I'm getting your point now :-)
chrysante
CC BY-SA 4.0
2023-11-27T22:50:15.903Z
@supercat I think now I really get your point: The (possibly infinite) loop acts as a check for the array access even though it is totally unrelated to the access. So if I first perform the transform I describe here and then perhaps in a later stage delete the loop because the value of i is not needed then the code would break. That is a good point!
chrysante
CC BY-SA 4.0
2023-11-27T23:18:30.403Z
@chrysante: The code *as written* does not rely upon the `while` loop serving such a purpose, and I would view an assumption that code doesn't rely on a `while` loop serving such a purpose as reasonable *if a compiler refrains from transforming code that doesn't rely upon the loop working that way into code that does*.  The maintainers of clang and gcc see nothing wrong with treating endless loops as "anything can happen" UB, even though such treatment makes it possible for a program to violate invariants even if every individual portion of it has defined behavior upholding them.
supercat
CC BY-SA 4.0
2023-11-27T23:22:32.253Z
@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.
supercat
CC BY-SA 4.0
2023-11-27T23:39:26.450Z
That is crazy! I guess technically both languages allow that transform but I'm also not sure how desirable that is.
chrysante
CC BY-SA 4.0
2023-12-01T11:27:41.430Z
I disagree with your first example. `if (n == 0) f(n);` shouldn't necessarily be changed to `if (n == 0) f(0);`. Imagine for instance if you have: `if (n == 0) f(0); else if (n == 1) f(1);`. In this case it's obvious that the code can be refactored `if (n == 0 or n == 1) f(n);`. And there are similar cases where it's much less obvious.
Stef
CC BY-SA 4.0
2023-12-01T13:23:36.510Z
@Stef They're not mutually excluse, you would just have to schedule your proposed transform first.
chrysante
<p>The first examples with just less than and greater than can be solved using range-based invariants.</p>
<p>Each time you pass a branch the condition of that branch gets added to the invariants of the scope.</p>
<p>Then you have optimizations rewrite rules that involve <code>(n &gt;= A) =&gt; (n &lt; A) == false</code> and similar rules.</p>
<p>Doing the same with modulo invariants is more complicated. It would require something like decomposing a <code>i % A*B == C</code> into <code>(i % A == C%A) &amp;&amp; (i % B == C*B)</code> (proving this is correct in at least this cases). And then finding that one of them matches a invariant.</p>

CC BY-SA 4.0
2023-11-27T12:49:48.830Z
2023-11-27T12:49:48.830Z
ratchet freak
CC BY-SA 4.0
2023-11-27T15:09:51.857Z
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)
chrysante
# Optimization algorithm using conditional invariants
Posted by: username_0 on 2023-11-27
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.
**Tags:** optimization static-single-assignment
> **Comments:**
> **username_0**: I guess the last example might be handled by the SSAPRE algorithm described [here](http://www.cs.cmu.edu/~hopper/745project/ssapre1.pdf), but I found this paper very hard to understand.  
> **username_1**: One of the optimizations you're describing is called constant [propagation](https://en.wikipedia.org/wiki/Constant_folding).  More advanced versions track multiple possible values, and/or equivalences (i is equal to j here), or conditions (i < 10 here).  
> **username_0**: @ErikEidt I did implement "sparse conditional constant propagation" as described in [this paper](https://dl.acm.org/doi/pdf/10.1145/103135.103136) in chapter 3.4, but unless my implementation is incorrect this algorithm does not do these transforms. Is there a better constant propagation algorithm?  
> **username_2**: https://developers.redhat.com/blog/2021/04/28/value-range-propagation-in-gcc-with-project-ranger  
> **username_0**: @Moonchild Thank you! Value range propagation might be the keyword I was looking for.  
> **username_3**: @Moonchild It would be great if you could expand that link into an answer!  
> **username_4**: Such optimizations are dangerous unless one has a means of preserving control, sequencing, address, and data dependencies within the resulting code.  If `x` is a static array, then changing `if (p == x+1) *p=1; ` with `if (p == x+1) x[1] = 0;` would only be valid if all downstream processes would behave as though the left-hand operand of the assignment was based upon `p` rather than `x` (either because they recognize what's it's based on, or because they don't care).  
> **username_4**: What kind of code are you seeking to optimize?  On many platforms, if `x` has just been found to equal something, using it will often be at least as efficient as using a constant, and if a programmer writes `if (x==5) foo(x);` rather than `if (x==5) foo(5);`, that would often suggest that either the programmer wasn't interested in any performance gains from using the latter form, or didn't expect that there would be any.  
> **username_0**: @supercat _Such optimizations are dangerous unless one has a means of preserving control, sequencing, address, and data dependencies within the resulting code._ -- Yes, absolutely. Maybe I should have been more explicit with this, but the code is in SSA form, so every variable stays constant after its assignment. And the expression `foo(x)` is symbolic here. It may be a more complex expression, or even if it is just a function call, replacing the argument with a constant may motivate the inliner to inline the call if otherwise it hadn't.  
> **username_0**: @supercat It is for a general purpose programming language  
> **username_2**: @AlexisKing I don't really have anything useful to say other than 'look at existing resources on value range analysis'  
> **username_4**: @chrysante: Even when using SSA form, maintaining dependencies may be important if one wants to allow optimizing transforms to reorder operations, but still ensure that invariants such a memory safety that are upheld by all individual parts of a program will be upheld by the program as a whole.  
> **username_0**: @supercat I'm not sure if I understand you correctly. Sure, moving loads, stores or function calls around and changing their relativ order is generally not a safe transform, but replacing the use of one SSA value with another that is proven to be equal should be safe under all circumstances?  
> **username_4**: @chrysante: Suppose a loop like `while((i & 0xFFFF) != x) i*=3;` is followed by `if (x < 65536) arr[x]=1;`.  Looking at those two pieces of the code in isolation, neither would be able to modify `arr[65536]`, but applying the kind of inference described in the question (eliminating the `if`) without recording that doing so would require the assignment to `arr` to be sequenced after the execution of the loop (preventing its elision) could result in code being transformed in a manner that unconditionally stores 1 to `arr[x]`.  
> **username_4**: @chrysante: Somewhat similar issues may arise if code which is running in a privileged context is using a pointer to data which can be accessed from a non-privileged thread.  If code does something like `x=*p; if (x < 65536) arr[x] = 123;` around the time that non-privileged code modifies `*p`, it may be acceptable for `x` to receive any value that `*p` has held or well hold, but only if *both uses of `x` act upon the same value*.  
> **username_0**: @supercat In the first example if the while loop ever terminates x has to be less than 65536 and thus the if statement can be executed unconditionally. So yes the while loop has to be sequenced before the if statement, otherwise we could not make that assumption. I hope I'm getting your point now :-)  
> **username_0**: @supercat I think now I really get your point: The (possibly infinite) loop acts as a check for the array access even though it is totally unrelated to the access. So if I first perform the transform I describe here and then perhaps in a later stage delete the loop because the value of i is not needed then the code would break. That is a good point!  
> **username_4**: @chrysante: The code *as written* does not rely upon the `while` loop serving such a purpose, and I would view an assumption that code doesn't rely on a `while` loop serving such a purpose as reasonable *if a compiler refrains from transforming code that doesn't rely upon the loop working that way into code that does*.  The maintainers of clang and gcc see nothing wrong with treating endless loops as "anything can happen" UB, even though such treatment makes it possible for a program to violate invariants even if every individual portion of it has defined behavior upholding them.  
> **username_4**: @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.  
> **username_0**: That is crazy! I guess technically both languages allow that transform but I'm also not sure how desirable that is.  
> **username_5**: I disagree with your first example. `if (n == 0) f(n);` shouldn't necessarily be changed to `if (n == 0) f(0);`. Imagine for instance if you have: `if (n == 0) f(0); else if (n == 1) f(1);`. In this case it's obvious that the code can be refactored `if (n == 0 or n == 1) f(n);`. And there are similar cases where it's much less obvious.  
> **username_0**: @Stef They're not mutually excluse, you would just have to schedule your proposed transform first.  
---
## 1 answers
### Answer by username_6 on 2023-11-27. Score: 1
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.
> **Comments:**
> **username_0** (2023-11-27): 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)  
---
