3
$\begingroup$

Let's say that you have some loop

for(i=0;i<n;i++){
    if(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<n;i++){
    if(isodd(n)){p(i);}
}

To

for(i=1;i<n;i+=2){
    p(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.

$\endgroup$
2
$\begingroup$

A general approach is to automatically infer loop invariants. There are techniques for inferring loop invariants that can be expressed in 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 (see also the web site).

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.