[llvm-dev] Working on FP SCEV Analysis

[Andrew Trick via llvm-dev]

> On May 16, 2016, at 3:03 PM, Andrew Trick <atrick at apple.com> wrote:
> 
> 
>> On May 16, 2016, at 2:42 PM, Sanjoy Das <sanjoy at playingwithpointers.com> wrote:
>> 
>> [+CC Andy]
>> 
>> Hi Elena,
>> 
>> I don't have any fundamental issues with teaching SCEV about floating
>> point types, but given this will be a major change, I think a high
>> level roadmap should be discussed on llvm-dev before we start
>> reviewing and committing changes.
>> 
>> Here are some issues that I think are worth discussing:
>> 
>> - Core motivation: why do we even care about optimizing floating
>> point induction variables?  What situations are they common in?  Do
>> programmers _expect_ compilers to optimize them well?  (I haven't
>> worked on our vectorizers so pardon the possibly stupid question)
>> in the example you gave, why do you need SCEV to analyze the
>> increment to vectorize the loop (i.e how does it help)?  What are
>> some other concrete cases you'll want to optimize?
>> 
>> - I presume you'll want SCEV expressions for `sitofp` and `uitofp`.
>> (The most important question:) With these in the game, what is the
>> canonical representation of SCEV expressions that can be expressed
>> as, say, both `sitofp(A + B)` and `sitofp(A) + sitofp(B)`?
>> 
>> Will we have a way to mark expressions (like we have `nsw` and
>> `nuw` for `sext` and `zext`) which we can distribute `sitofp` and
>> `uitofp` over?
>> 
>> Same questions for `fptosi` and `fptoui`.
>> 
>> - How will you partition the logic between floating and integer
>> expressions in SCEV-land?  Will you have, say, `SCEVAddExpr` do
>> different things based on type, or will you split it into
>> `SCEVIAddExpr` and `SCEVFAddExpr`? [0]
>> 
>> * There are likely to be similarities too -- e.g. the "inductive"
>>   or "control flow" aspect of `SCEVAddRecExpr` is likely to be
>>   common between floating point add recurrences[1], and integer add
>>   recurrences; and part of figuring out the partitioning is also
>>   figuring out how to re-use these bits of logic.
>> 	
>> 
>> [0]: I'll prefer the latter since e.g. integer addition is
>> associative, but floating point addition isn't; and it is better to
>> force programmers to handle the two operations differently.
>> 
>> [1]: For instance, things like this:
>> https://github.com/llvm-mirror/llvm/blob/master/lib/Analysis/ScalarEvolution.cpp#L7564
>> are likely to stay common between floating point and integer add recs.
>> 
>> — Sanjoy
> 
> I don’t think it makes sense to consider a floating point induction variable an “add recurrence” unless it the inductive value can be promoted to an integer. (The computational properties of chained recurrences are defined on integers).
> 
> IndVarSimplify handleFloatingPointIV is supposed to promote your FP induction variables to integers so that SCEV can analyze them. After all the loop opts runs, the LSR is supposed to cleanup any casts during optimizeShadowIV.

That said, there are probably many reasons (e.g. non-integer initial value) that you can’t promote a FP IV to an Integer, but you may still want to vectorize it in fast-math mode. I’ll leave it to MichaelZ and Adam to comment on how best to prepare such loops for vectorization.

-Andy