# Compiler Optimization: How do you automatically fuse conditionals into the loop index?

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);
}


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.

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).