[LLVMdev] Reasoning about Floating Point in Optimizations

[Philip Reames]

Good evening all,

Inspired by http://llvm.org/bugs/show_bug.cgi?id=3299, I've spent the 
last few hours looking at various test cases involving float point 
variables in loops and trying to identify some of our short comings on 
the optimization front.  Before I go any further, I want to share my 
findings with the community and ask for feedback on how best to approach 
this.

Essentially, the motivating examples are things like these two:
void func() {
    // this loop does not get pruned
    for (float i = 0.0f; i < 1000.0f; i += 1.2f) {
    }
}

int foo3() {
   // this loop does not get pruned
   for(int i = 0; i < 1000.0f; i++) {
   }
   return 0;
}

When the IR is generated and optimized, we are currently unable to 
recognize these as fixed trip count loops.  As such, we do not optimize 
them away.  If we extend the second example to compute a running sum of 
the indexes, we aren't able to recognize that constant calculation 
either.  (We do both optimizations if the upper bound constant is 
converted to an integer in the second loop.)

Looking into this, I discovered two sets of possible issues:
1) InstCombine does not take advantage of instruction sequences in which 
a variable integer is converted to a float and then immediate compared 
to a floating point constant.  In many cases, these can be converted to 
an integer comparison.
   %conv = sitofp i32 %0 to float
   %cmp = fcmp olt float %conv, 1.000000e+03

2) ScalarEvolution is completely ignorant of floating point values and 
doesn't recognize fixed (or even bounded) trip counts.  The end result 
of this is that the loop appears possible infinite to loop-deletion and 
can't be safely deleted.

The general approach I'm considering is to introduce a series of 
transformation in InstCombine based on the sitofp/fcmp(const) pattern 
and to extend SCEV to be FP aware.  The first part doesn't worry me too 
much - though I will want a careful review from someone more familiar 
with FP semantics than myself - but the second one I'm unsure of.  Is 
this the right approach to be taking?  Or is there a better way to 
address this problem?


Note: I'm working off the head of SVN as of around 6pm.

Note 2: I don't have any personal stake in this topic, I just grabbed it 
as an interesting case to investigate.  If someone is already looking at 
this, let me know, I'll go find something else to work on.

Yours,
Philip Reames