<p>A general approach is to automatically infer loop invariants.  There are techniques for inferring loop invariants that can be expressed in <a href="https://en.wikipedia.org/wiki/Presburger_arithmetic" rel="nofollow">Presburger arithmetic</a>, i.e., linear expressions over the integers plus quantifiers.  These typically rely upon the fact that there exist decision procedures for Presburger arithmetic, e.g., <a href="http://www.cs.umd.edu/~pugh/papers/omega.pdf" rel="nofollow">the Omega method</a> (see also <a href="http://www.cs.umd.edu/projects/omega/" rel="nofollow">the web site</a>).</p>

<p>These methods should be enough to build a special optimization that can solve your first two challenges.  For instance, you can use those methods to find loop strides.  In particular, you can use those methods to characterize the values of <code>i</code> that will reach the then-block of the if-statement: you can first check whether the sequence of values of <code>i</code> lies in an arithmetic progression, then characterize the progression (deduce find the minimum value of <code>i</code>, deduce the maximum value of <code>i</code>, and deduce the stride).</p>

<p>These methods have been studied in depth in the compiler literature on loop vectorization, where we want to know whether we can execute each iteration of the loop in parallel on a separate core.  Similar techniques should be useful for your kind of problem as well.</p>

<p>I don't know whether there's any reasonable algorithm for your third example, or whether anyone has studied that sort of thing in the compiler literature.</p>

CC BY-SA 3.0
2014-02-28T03:03:29.183Z
2014-02-28T03:03:29.183Z
D.W.
<p>Let's say that you have some loop</p>

<pre><code>for(i=0;i&lt;n;i++){
    if(i &gt; 3 &amp;&amp; i &lt; 8){ p(i); }
}
</code></pre>

<p>How would I go about automatically fusing that into</p>

<pre><code>for(i=4;i&lt;8;i++){
    p(i);
}
</code></pre>

<p>How about</p>

<pre><code>for(i=0;i&lt;n;i++){
    if(isodd(n)){p(i);}
}
</code></pre>

<p>To </p>

<pre><code>for(i=1;i&lt;n;i+=2){
    p(i);
}
</code></pre>

<p>And for the final challenge, fuse</p>

<pre><code>for(i=0;;i++){
    if((i&gt;&gt;2)%2 == 0){ p(i); }
}
</code></pre>

<p>To</p>

<pre><code>for(i=0;;i+=8){
    for(j=0;j&lt;4;j++){ p(i+j); }
}
</code></pre>

<p>I'm not asking how to do this by hand. I want the compiler to figure out how to do this. I have a gut feeling like this is some well known problem, I just don't know what name it has, or even how I'd google for it.</p>

<optimization><compilers>
Compiler Optimization: How do you automatically fuse conditionals into the loop index?
Evan
# Compiler Optimization: How do you automatically fuse conditionals into the loop index?

(Asked by: username_0 on 2014-02-27)

Let's say that you have some loop
for(i=0;i 3 && i < 8){ p(i); }
}

How would I go about automatically fusing that into
for(i=4;i<8;i++){
    p(i);
}

How about
for(i=0;i
To 
for(i=1;i
And for the final challenge, fuse
for(i=0;;i++){
    if((i>>2)%2 == 0){ p(i); }
}

To
for(i=0;;i+=8){
    for(j=0;j<4;j++){ p(i+j); }
}

I'm not asking how to do this by hand. I want the compiler to figure out how to do this. I have a gut feeling like this is some well known problem, I just don't know what name it has, or even how I'd google for it.

**Tags:** optimization, compilers

---

## 1 answers

### Answer by username_1 on 2014-02-28. Score: 3 | Accepted answer

A general approach is to automatically infer loop invariants. There are techniques for inferring loop invariants that can be expressed in [Presburger arithmetic](https://en.wikipedia.org/wiki/Presburger_arithmetic), i.e., linear expressions over the integers plus quantifiers. These typically rely upon the fact that there exist decision procedures for Presburger arithmetic, e.g., [the Omega method](http://www.cs.umd.edu/~pugh/papers/omega.pdf) (see also [the web site](http://www.cs.umd.edu/projects/omega/)).

These methods should be enough to build a special optimization that can solve your first two challenges. For instance, you can use those methods to find loop strides. In particular, you can use those methods to characterize the values of `i` that will reach the then-block of the if-statement: you can first check whether the sequence of values of `i` lies in an arithmetic progression, then characterize the progression (deduce find the minimum value of `i`, deduce the maximum value of `i`, and deduce the stride).

These methods have been studied in depth in the compiler literature on loop vectorization, where we want to know whether we can execute each iteration of the loop in parallel on a separate core. Similar techniques should be useful for your kind of problem as well.

I don't know whether there's any reasonable algorithm for your third example, or whether anyone has studied that sort of thing in the compiler literature.


---

