Page MenuHomePhabricator

Floating Point SCEV Analysis
AbandonedPublic

Authored by delena on May 26 2016, 11:37 AM.

Details

Summary

As we already discussed in llvm-dev forum http://lists.llvm.org/pipermail/llvm-dev/2016-May/099724.html
I'm working on FP SCEV analysis in order to enable loop vectorization with FP induction variables.
Trying to minimize the first patch, I implemented only simple cases. Once this patch is accepted, I continue to fill the gaps between integer and fp scevs.

this is the minimal test case I started from:
float fp_inc;

float x = init;
for (int i=0;i<N;i++){
  A[i] = x;
  x += fp_inc; // Loop invariant variable or constant
}

All optimizations and SCEV recurrence will come in the next patches.
I ran some tests to be sure that correctness is not broken.

Diff Detail

Repository
rL LLVM

Event Timeline

delena updated this revision to Diff 58655.May 26 2016, 11:37 AM
delena retitled this revision from to Floating Point SCEV Analysis.
delena updated this object.
delena set the repository for this revision to rL LLVM.
delena added a subscriber: llvm-commits.
sanjoy edited edge metadata.May 30 2016, 12:02 AM

Hi Elena,

I have made some minor comments inline, but I still stand by my earlier comment that we should do something like this as a last resort. As an initial step we should at least evaluate how far we can we can get on relevant workloads without teaching SCEV about floating point values at all.

../include/llvm/Analysis/ScalarEvolutionExpressions.h
310

What is the intent behind making SCEVFAddExpr and SCEVFMulExpr subclasses of SCEVNAryExpr? Does (a + b + c) represent ((a + b) + c) or (a + (b + c))?

../lib/Analysis/ScalarEvolution.cpp
1503

Note: getSExtValue will assert for integers that are large than 64 bits.

2544

Depending on how we define the associativity of an SCEVFAddExpr, this may or may not be valid.

2875

This is all duplicated code. If we go ahead with this, we should definitely common this with the integer version.

2895

I thought floating point in general isn't distributive?

I still stand by my earlier comment that we should do something like this as a last resort.

It is very convenient way to answer all questions about FP variables that being changed and used inside loop.

../include/llvm/Analysis/ScalarEvolutionExpressions.h
310

I planned to use SCEVFAddExpr and SCEVFMulExpr to couple FP calculations, like it is done for integer operations.
for example: a + const1 + b + const2 = a + b + const3
or a * 0.0 = 0
If compiler supports FP reduction, it can support any FP simplification in this mode. I assume that fast-math should allow all these transformations.

../lib/Analysis/ScalarEvolution.cpp
1503

I'll fix. thank you.

2875

I thought about limitations in FP manipulations relatively to integer values. If fast-math allows all manipulations, we definitely can share the code.

delena updated this revision to Diff 59372.Jun 2 2016, 6:45 AM
delena edited edge metadata.

I implemented IV simplification for FP using FP SCEV. No the following loop is covered:

float x = init;
for (int i=0;i<N;i++){

A[i] = x;
x += fp_inc; // Loop invariant variable or constant

}

And the result is calculated as x = init + fp_inc*N

I implemented IV simplification for FP using FP SCEV. No the following loop is covered:

float x = init;

for (int i=0;i<N;i++){
  A[i] = x;
  x += fp_inc; // Loop invariant variable or constant
}

And the result is calculated as x = init + fp_inc*N

Hi Elena,

Replacing x with fp_inc*N should require fast-math - and it's not clear to me what fast-math allows.
If this is correct with fast-math, we should be able to use this to get the backedge taken count - which would be a good reason for doing this in SCEV.

I don't know if this has been established before, but the vectorization tests use FP re-association, so fast-math is also required there.

Thanks,
Silviu

spatel added a subscriber: scanon.

Replacing x with fp_inc*N should require fast-math - and it's not clear to me what fast-math allows.
If this is correct with fast-math, we should be able to use this to get the backedge taken count - which would be a good reason for doing this in SCEV.

I don't know if this has been established before, but the vectorization tests use FP re-association, so fast-math is also required there.

These are the same questions raised in PR27894:
https://llvm.org/bugs/show_bug.cgi?id=27894

An even simpler test case still raises questions if we support changes to the FP env:
https://llvm.org/bugs/show_bug.cgi?id=27899

[cc'ing @scanon for FP semantics questions]

sanjoy added a comment.Jun 2 2016, 2:30 PM

float x = init;

for (int i=0;i<N;i++){
  A[i] = x;
  x += fp_inc; // Loop invariant variable or constant
}

If this is correct with fast-math, we should be able to use this to
get the backedge taken count - which would be a good reason for doing
this in SCEV.

Shouldn't SCEV today be able to compute the backedge taken count of
the above loop (since the controlling induction variable is
integral)?

float x = init;

for (int i=0;i<N;i++){
  A[i] = x;
  x += fp_inc; // Loop invariant variable or constant
}

If this is correct with fast-math, we should be able to use this to
get the backedge taken count - which would be a good reason for doing
this in SCEV.

Shouldn't SCEV today be able to compute the backedge taken count of
the above loop (since the controlling induction variable is
integral)?

Hi Sanjoy,

For that loop, yes, SCEV should be able to figure out the backedge taken count today.

But using that reasoning I think we should be able to get the backedge taken count for the following loop (again, I don't know if this is actually correct):

float i = 0.f;
for (; i < N; i+=fp_inc) {}

This was something previously raised by Michael on the llvm-dev thread.

delena added a comment.Jun 5 2016, 5:30 AM

float x = init;

for (int i=0;i<N;i++){
  A[i] = x;
  x += fp_inc; // Loop invariant variable or constant
}

If this is correct with fast-math, we should be able to use this to
get the backedge taken count - which would be a good reason for doing
this in SCEV.

Shouldn't SCEV today be able to compute the backedge taken count of
the above loop (since the controlling induction variable is
integral)?

Hi Sanjoy,

For that loop, yes, SCEV should be able to figure out the backedge taken count today.

But using that reasoning I think we should be able to get the backedge taken count for the following loop (again, I don't know if this is actually correct):

float i = 0.f;
for (; i < N; i+=fp_inc) {}

This was something previously raised by Michael on the llvm-dev thread.

Yes, it is possible with FP SCEV. I implemented fp-range and backedge taken count calculation, but I don't want to put everything in this patch.
Community should also decide about the flag, whether it will be "-ffast-math" or something else.

delena abandoned this revision.Jun 14 2016, 4:44 AM

The FP SCEV concept is rejected.