To the best of my experience, handling case B (secondary induction) is
must-have, and if I’m not mistaken,
people aren’t opposed to that.
For me, handling case A (primary induction) is “why not?”, but I certainly admit
that that can be very naïve
thinking coming from lack of good understanding on SCEV and their proper usages.
Now, let’s assume we
can postpone discussion about case A. What is the best approach to handle case
B? Let me summarize
the discussion so far. Hope I didn’t miss anything.
1)
Extend SCEV was the initial approach taken by Elena.
Elena thinks this solution ”looks very structured”.
If I’m not mistaken, some people think this is overkill and
overly complicates already complicated SCEV.
Anyone care to look at the patch Elena came up with?
2)
IndVarSimplify::handleFloatingPointIV (mentioned by Andy)
This transforms integer-valued FP (primary) IV into integer IV
and convert.
Chandler says most of Graphics shading language use case
mentioned by Owen
should be handled here.
It certainly has the logic of detecting FP induction, but Andy
punted discussions
on non-integer valued IV issues to MichaelZ and Adam.
3)
extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze
the PHIs without SCEV support
(mentioned by Adam)
If this is the standard way to deal with all secondary
inductions, it certainly looks attractive.
Elena, would you try doing this and compare with 1)?
Thanks,
Hideki
----------------------
I looked at what our FORTRAN compiler (non-LLVM) does for the following (x, y,
z, and f are float by default typing,
based on names).
subroutine foo(x, y, z, A, N)
double precision A(N)
do f = x, y, z
A(f) = f
enddo
end
The frontend computes the trip count outside of the loop (per language rule) and
uses an integer primary
induction variable (compile-generated) for loop control. So, (future) FORTRAN
usage doesn’t seem to be
a good example for promoting support for case A (= FP primary induction
variable).
From: Chandler Carruth [mailto:chandlerc at google.com]
Sent: Thursday, May 19, 2016 7:03 PM
To: Demikhovsky, Elena <elena.demikhovsky at intel.com>; anemet at
apple.com; Sanjoy Das <sanjoy at playingwithpointers.com>
Cc: Saito, Hideki <hideki.saito at intel.com>; llvm-dev <llvm-dev at
lists.llvm.org>; Andrew Trick <atrick at apple.com>
Subject: Re: [llvm-dev] Working on FP SCEV Analysis
On Thu, May 19, 2016 at 7:03 AM Demikhovsky, Elena <elena.demikhovsky at
intel.com<mailto:elena.demikhovsky at intel.com>>
wrote:> One option would be to extend InductionDescriptor::isInductionPHI in the
vectorizer to directly analyze the PHIs without SCEV support as Sanjoy
suggested. I *think* that that could be sufficient to handle case B.
I implemented this with FP SCEV and the code looks very structured, including
SCEVExpander. Extending the existing structures without implementing FP SCEV
will be problematic.
And my end goal is to handle case *A*.
Ok, but there have been *numerous* requests for an explanation of why this is
important, and that hasn't emerged yet.
We really need to have a clear understanding of the relative importance of
solving these problems in order to understand the best approach.
- Elena
From: anemet at apple.com<mailto:anemet at apple.com> [mailto:anemet at
apple.com<mailto:anemet at apple.com>]
Sent: Thursday, May 19, 2016 07:43
To: Sanjoy Das <sanjoy at playingwithpointers.com<mailto:sanjoy at
playingwithpointers.com>>
Cc: Demikhovsky, Elena <elena.demikhovsky at
intel.com<mailto:elena.demikhovsky at intel.com>>; Saito, Hideki
<hideki.saito at intel.com<mailto:hideki.saito at intel.com>>;
llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Andrew Trick <atrick at apple.com<mailto:atrick at
apple.com>>
Subject: Re: [llvm-dev] Working on FP SCEV Analysis
On May 18, 2016, at 12:17 PM, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Demikhovsky, Elena wrote:> Even then, I'd personally want to see further evidence of why the
correct solution is to model the floating point IV in SCEV rather than
find a more powerful way of converting the IV to an integer that
models> the non-integer values taken on by the IV. As an example, if the use
case is the following code with appropriate flags to relax IEEE
semantics so this looks like normal algabra etc:
> for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A**
...
> I'd rather see us cleverly turn it into:
> float f = 0.01f;
> for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B**
I can later try to enhance IndVarSimplify::handleFloatingPointIV() in
order to convert**A** to **B**.
But **B** is exactly the case I’m starting from. The main IV “i” is
integer. The variable “f” is also considered as IV in this loop.
And this loop is not vectorized because “f” is floating point.
I don’t think that the case **B** is uncommon.
If B is the case we actually care about, I'd say changing SCEV to work with
floating points is an overkill. How would you expect an SCEVFAddExpr to help
vectorize B, other than tell you what the initial value and the increment is
(and these can be found with a simple value analysis)?
One option would be to extend InductionDescriptor::isInductionPHI in the
vectorizer to directly analyze the PHIs without SCEV support as Sanjoy
suggested. I *think* that that could be sufficient to handle case B.
Then if we find other pressing cases to handle we can rethink the strategy.
Also the current diagnostics is pretty bad for Hideki’s testcase with TTT as
float. This is what we currently report with -Rpass-analysis=loop-vectorize:
/tmp/sss.c:3:6: remark: loop not vectorized: value that could not be
identified as reduction is used outside the loop
[-Rpass-analysis=loop-vectorize]
I have no clue why we say that the value is used outside the loop. I think this
should just say that we have a loop-variant value that we couldn’t identify
either as an induction or as a reduction.
Adam
If we're interested in handling complex variants of A directly: computing
trip counts, proving away predicates etc. without translating the loops to use
integer IVs (perhaps because we can't legally do so), then I can see FP-SCEV
as a reasonable implementation strategy, but it looks like the general consensus
is that such cases are rare and generally not worth optimizing?
-- Sanjoy
-*/Elena/*
---------------------------------------------------------------------
Intel Israel (74) Limited
This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
---------------------------------------------------------------------
Intel Israel (74) Limited
This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160520/5ba72094/attachment.html>
Hi Hideki, I like this summary overall, thanks. More below.> On May 20, 2016, at 10:04 AM, Saito, Hideki <hideki.saito at intel.com> wrote: > > > To the best of my experience, handling case B (secondary induction) is must-have, and if I’m not mistaken, > people aren’t opposed to that. > > For me, handling case A (primary induction) is “why not?”, but I certainly admit that that can be very naïve > thinking coming from lack of good understanding on SCEV and their proper usages. Now, let’s assume we > can postpone discussion about case A. What is the best approach to handle case B? Let me summarize > the discussion so far. Hope I didn’t miss anything. > > 1) > Extend SCEV was the initial approach taken by Elena. > Elena thinks this solution ”looks very structured”. > If I’m not mistaken, some people think this is overkill and overly complicates already complicated SCEV. > Anyone care to look at the patch Elena came up with? > 2) > IndVarSimplify::handleFloatingPointIV (mentioned by Andy) > This transforms integer-valued FP (primary) IV into integer IV and convert. > Chandler says most of Graphics shading language use case mentioned by Owen > should be handled here. > It certainly has the logic of detecting FP induction, but Andy punted discussions > on non-integer valued IV issues to MichaelZ and Adam.My understanding is that we only need this for *A* not for *B*. On the specific issue of non-integer values, there is simply no attempt made in the code to deal with them. That said, I think it should be possible to compute the trip count and then derive an integer induction variable controlling the loop.> 3) > extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support > (mentioned by Adam) > If this is the standard way to deal with all secondary inductions, it certainly looks attractive. > Elena, would you try doing this and compare with 1)?Just to clarify, the code is currently structured to check if the PHI is an add-recurrence that was detected by SCEV. The idea is to add a fall-back to analyze the PHI directly if its type is a float. There is already precedence for such things in LV. We support more reductions (including floating-point) than what SCEV can analyze, therefore RecurrenceDescriptor::AddReductionVar needs to analyze PHIs directly. Adam> > Thanks, > Hideki > > ---------------------- > I looked at what our FORTRAN compiler (non-LLVM) does for the following (x, y, z, and f are float by default typing, > based on names). > > subroutine foo(x, y, z, A, N) > double precision A(N) > do f = x, y, z > A(f) = f > enddo > end > > The frontend computes the trip count outside of the loop (per language rule) and uses an integer primary > induction variable (compile-generated) for loop control. So, (future) FORTRAN usage doesn’t seem to be > a good example for promoting support for case A (= FP primary induction variable). > > > <> > <>From: Chandler Carruth [mailto:chandlerc at google.com] > Sent: Thursday, May 19, 2016 7:03 PM > To: Demikhovsky, Elena <elena.demikhovsky at intel.com>; anemet at apple.com; Sanjoy Das <sanjoy at playingwithpointers.com> > Cc: Saito, Hideki <hideki.saito at intel.com>; llvm-dev <llvm-dev at lists.llvm.org>; Andrew Trick <atrick at apple.com> > Subject: Re: [llvm-dev] Working on FP SCEV Analysis > > On Thu, May 19, 2016 at 7:03 AM Demikhovsky, Elena <elena.demikhovsky at intel.com <mailto:elena.demikhovsky at intel.com>> wrote: > > One option would be to extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support as Sanjoy suggested. I *think* that that could be sufficient to handle case B. <> > > I implemented this with FP SCEV and the code looks very structured, including SCEVExpander. Extending the existing structures without implementing FP SCEV will be problematic. > And my end goal is to handle case *A*. > Ok, but there have been *numerous* requests for an explanation of why this is important, and that hasn't emerged yet. > > We really need to have a clear understanding of the relative importance of solving these problems in order to understand the best approach. > > > > - Elena > > <>From: anemet at apple.com <mailto:anemet at apple.com> [mailto:anemet at apple.com <mailto:anemet at apple.com>] > Sent: Thursday, May 19, 2016 07:43 > To: Sanjoy Das <sanjoy at playingwithpointers.com <mailto:sanjoy at playingwithpointers.com>> > Cc: Demikhovsky, Elena <elena.demikhovsky at intel.com <mailto:elena.demikhovsky at intel.com>>; Saito, Hideki <hideki.saito at intel.com <mailto:hideki.saito at intel.com>>; llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>; Andrew Trick <atrick at apple.com <mailto:atrick at apple.com>> > > Subject: Re: [llvm-dev] Working on FP SCEV Analysis > > > On May 18, 2016, at 12:17 PM, Sanjoy Das via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > > > > Demikhovsky, Elena wrote: > > > Even then, I'd personally want to see further evidence of why the > correct solution is to model the floating point IV in SCEV rather than > find a more powerful way of converting the IV to an integer that models > > the non-integer values taken on by the IV. As an example, if the use > case is the following code with appropriate flags to relax IEEE > semantics so this looks like normal algabra etc: > > > for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A** > > ... > > > I'd rather see us cleverly turn it into: > > > float f = 0.01f; > > > for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B** > > I can later try to enhance IndVarSimplify::handleFloatingPointIV() in > order to convert**A** to **B**. > > But **B** is exactly the case I’m starting from. The main IV “i” is > integer. The variable “f” is also considered as IV in this loop. > > And this loop is not vectorized because “f” is floating point. > > I don’t think that the case **B** is uncommon. > > If B is the case we actually care about, I'd say changing SCEV to work with floating points is an overkill. How would you expect an SCEVFAddExpr to help vectorize B, other than tell you what the initial value and the increment is (and these can be found with a simple value analysis)? > > One option would be to extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support as Sanjoy suggested. I *think* that that could be sufficient to handle case B. > > Then if we find other pressing cases to handle we can rethink the strategy. > > Also the current diagnostics is pretty bad for Hideki’s testcase with TTT as float. This is what we currently report with -Rpass-analysis=loop-vectorize: > > /tmp/sss.c:3:6: remark: loop not vectorized: value that could not be > identified as reduction is used outside the loop > [-Rpass-analysis=loop-vectorize] > > I have no clue why we say that the value is used outside the loop. I think this should just say that we have a loop-variant value that we couldn’t identify either as an induction or as a reduction. > > Adam > > > > If we're interested in handling complex variants of A directly: computing trip counts, proving away predicates etc. without translating the loops to use integer IVs (perhaps because we can't legally do so), then I can see FP-SCEV as a reasonable implementation strategy, but it looks like the general consensus is that such cases are rare and generally not worth optimizing? > > -- Sanjoy > > > > -*/Elena/* > > --------------------------------------------------------------------- > Intel Israel (74) Limited > > This e-mail and any attachments may contain confidential material for > the sole use of the intended recipient(s). Any review or distribution > by others is strictly prohibited. If you are not the intended > recipient, please contact the sender and delete all copies. > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> > > --------------------------------------------------------------------- > Intel Israel (74) Limited > > This e-mail and any attachments may contain confidential material for > the sole use of the intended recipient(s). Any review or distribution > by others is strictly prohibited. If you are not the intended > recipient, please contact the sender and delete all copies. >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160520/9f81e5d4/attachment.html>
Michael Zolotukhin via llvm-dev
2016-May-20 18:37 UTC
[llvm-dev] Working on FP SCEV Analysis
Hi Hideki, Thanks for the summary!> On May 20, 2016, at 10:04 AM, Saito, Hideki via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > > To the best of my experience, handling case B (secondary induction) is must-have, and if I’m not mistaken, > people aren’t opposed to that. > > For me, handling case A (primary induction) is “why not?”, but I certainly admit that that can be very naïve > thinking coming from lack of good understanding on SCEV and their proper usages. Now, let’s assume we > can postpone discussion about case A. What is the best approach to handle case B? Let me summarize > the discussion so far. Hope I didn’t miss anything. > > 1) > Extend SCEV was the initial approach taken by Elena. > Elena thinks this solution ”looks very structured”. > If I’m not mistaken, some people think this is overkill and overly complicates already complicated SCEV. > Anyone care to look at the patch Elena came up with?Sorry if I missed it. Could you please post a link to the patch here? I’ve been mostly speculating on how complicated the SCEV solution would be, if the actual patch happens to be really simple and obvious, we can go this way. Michael> 2) > IndVarSimplify::handleFloatingPointIV (mentioned by Andy) > This transforms integer-valued FP (primary) IV into integer IV and convert. > Chandler says most of Graphics shading language use case mentioned by Owen > should be handled here. > It certainly has the logic of detecting FP induction, but Andy punted discussions > on non-integer valued IV issues to MichaelZ and Adam. > 3) > extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support > (mentioned by Adam) > If this is the standard way to deal with all secondary inductions, it certainly looks attractive. > Elena, would you try doing this and compare with 1)? > > Thanks, > Hideki > > ---------------------- > I looked at what our FORTRAN compiler (non-LLVM) does for the following (x, y, z, and f are float by default typing, > based on names). > > subroutine foo(x, y, z, A, N) > double precision A(N) > do f = x, y, z > A(f) = f > enddo > end > > The frontend computes the trip count outside of the loop (per language rule) and uses an integer primary > induction variable (compile-generated) for loop control. So, (future) FORTRAN usage doesn’t seem to be > a good example for promoting support for case A (= FP primary induction variable). > > > <> > <>From: Chandler Carruth [mailto:chandlerc at google.com] > Sent: Thursday, May 19, 2016 7:03 PM > To: Demikhovsky, Elena <elena.demikhovsky at intel.com>; anemet at apple.com; Sanjoy Das <sanjoy at playingwithpointers.com> > Cc: Saito, Hideki <hideki.saito at intel.com>; llvm-dev <llvm-dev at lists.llvm.org>; Andrew Trick <atrick at apple.com> > Subject: Re: [llvm-dev] Working on FP SCEV Analysis > > On Thu, May 19, 2016 at 7:03 AM Demikhovsky, Elena <elena.demikhovsky at intel.com <mailto:elena.demikhovsky at intel.com>> wrote: > > One option would be to extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support as Sanjoy suggested. I *think* that that could be sufficient to handle case B. <> > > I implemented this with FP SCEV and the code looks very structured, including SCEVExpander. Extending the existing structures without implementing FP SCEV will be problematic. > And my end goal is to handle case *A*. > Ok, but there have been *numerous* requests for an explanation of why this is important, and that hasn't emerged yet. > > We really need to have a clear understanding of the relative importance of solving these problems in order to understand the best approach. > > > > - Elena > > <>From: anemet at apple.com <mailto:anemet at apple.com> [mailto:anemet at apple.com <mailto:anemet at apple.com>] > Sent: Thursday, May 19, 2016 07:43 > To: Sanjoy Das <sanjoy at playingwithpointers.com <mailto:sanjoy at playingwithpointers.com>> > Cc: Demikhovsky, Elena <elena.demikhovsky at intel.com <mailto:elena.demikhovsky at intel.com>>; Saito, Hideki <hideki.saito at intel.com <mailto:hideki.saito at intel.com>>; llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>>; Andrew Trick <atrick at apple.com <mailto:atrick at apple.com>> > > Subject: Re: [llvm-dev] Working on FP SCEV Analysis > > > On May 18, 2016, at 12:17 PM, Sanjoy Das via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > > > > Demikhovsky, Elena wrote: > > > Even then, I'd personally want to see further evidence of why the > correct solution is to model the floating point IV in SCEV rather than > find a more powerful way of converting the IV to an integer that models > > the non-integer values taken on by the IV. As an example, if the use > case is the following code with appropriate flags to relax IEEE > semantics so this looks like normal algabra etc: > > > for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A** > > ... > > > I'd rather see us cleverly turn it into: > > > float f = 0.01f; > > > for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B** > > I can later try to enhance IndVarSimplify::handleFloatingPointIV() in > order to convert**A** to **B**. > > But **B** is exactly the case I’m starting from. The main IV “i” is > integer. The variable “f” is also considered as IV in this loop. > > And this loop is not vectorized because “f” is floating point. > > I don’t think that the case **B** is uncommon. > > If B is the case we actually care about, I'd say changing SCEV to work with floating points is an overkill. How would you expect an SCEVFAddExpr to help vectorize B, other than tell you what the initial value and the increment is (and these can be found with a simple value analysis)? > > One option would be to extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze the PHIs without SCEV support as Sanjoy suggested. I *think* that that could be sufficient to handle case B. > > Then if we find other pressing cases to handle we can rethink the strategy. > > Also the current diagnostics is pretty bad for Hideki’s testcase with TTT as float. This is what we currently report with -Rpass-analysis=loop-vectorize: > > /tmp/sss.c:3:6: remark: loop not vectorized: value that could not be > identified as reduction is used outside the loop > [-Rpass-analysis=loop-vectorize] > > I have no clue why we say that the value is used outside the loop. I think this should just say that we have a loop-variant value that we couldn’t identify either as an induction or as a reduction. > > Adam > > > > If we're interested in handling complex variants of A directly: computing trip counts, proving away predicates etc. without translating the loops to use integer IVs (perhaps because we can't legally do so), then I can see FP-SCEV as a reasonable implementation strategy, but it looks like the general consensus is that such cases are rare and generally not worth optimizing? > > -- Sanjoy > > > > -*/Elena/* > > --------------------------------------------------------------------- > Intel Israel (74) Limited > > This e-mail and any attachments may contain confidential material for > the sole use of the intended recipient(s). Any review or distribution > by others is strictly prohibited. If you are not the intended > recipient, please contact the sender and delete all copies. > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev> > > --------------------------------------------------------------------- > Intel Israel (74) Limited > > This e-mail and any attachments may contain confidential material for > the sole use of the intended recipient(s). Any review or distribution > by others is strictly prohibited. If you are not the intended > recipient, please contact the sender and delete all copies. > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160520/5c1c7084/attachment-0001.html>
Michael, she hasn’t posted a patch (or the link) yet, but she wrote “I
implemented this with FP SCEV and the code looks very structured, including
SCEVExpander”.
So, there is actual code that can be looked at. May have to wait until Sunday
morning in Israel.
Thanks,
Hideki
From: mzolotukhin at apple.com [mailto:mzolotukhin at apple.com]
Sent: Friday, May 20, 2016 11:38 AM
To: Saito, Hideki <hideki.saito at intel.com>
Cc: Chandler Carruth <chandlerc at google.com>; Demikhovsky, Elena
<elena.demikhovsky at intel.com>; Adam Nemet <anemet at apple.com>;
Sanjoy Das <sanjoy at playingwithpointers.com>; llvm-dev <llvm-dev at
lists.llvm.org>
Subject: Re: [llvm-dev] Working on FP SCEV Analysis
Hi Hideki,
Thanks for the summary!
On May 20, 2016, at 10:04 AM, Saito, Hideki via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
To the best of my experience, handling case B (secondary induction) is
must-have, and if I’m not mistaken,
people aren’t opposed to that.
For me, handling case A (primary induction) is “why not?”, but I certainly admit
that that can be very naïve
thinking coming from lack of good understanding on SCEV and their proper usages.
Now, let’s assume we
can postpone discussion about case A. What is the best approach to handle case
B? Let me summarize
the discussion so far. Hope I didn’t miss anything.
1)
Extend SCEV was the initial approach taken by Elena.
Elena thinks this solution ”looks very structured”.
If I’m not mistaken, some people think this is overkill and
overly complicates already complicated SCEV.
Anyone care to look at the patch Elena came up with?
Sorry if I missed it. Could you please post a link to the patch here? I’ve been
mostly speculating on how complicated the SCEV solution would be, if the actual
patch happens to be really simple and obvious, we can go this way.
Michael
2)
IndVarSimplify::handleFloatingPointIV (mentioned by Andy)
This transforms integer-valued FP (primary) IV into integer IV
and convert.
Chandler says most of Graphics shading language use case
mentioned by Owen
should be handled here.
It certainly has the logic of detecting FP induction, but Andy
punted discussions
on non-integer valued IV issues to MichaelZ and Adam.
3)
extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze
the PHIs without SCEV support
(mentioned by Adam)
If this is the standard way to deal with all secondary
inductions, it certainly looks attractive.
Elena, would you try doing this and compare with 1)?
Thanks,
Hideki
----------------------
I looked at what our FORTRAN compiler (non-LLVM) does for the following (x, y,
z, and f are float by default typing,
based on names).
subroutine foo(x, y, z, A, N)
double precision A(N)
do f = x, y, z
A(f) = f
enddo
end
The frontend computes the trip count outside of the loop (per language rule) and
uses an integer primary
induction variable (compile-generated) for loop control. So, (future) FORTRAN
usage doesn’t seem to be
a good example for promoting support for case A (= FP primary induction
variable).
From: Chandler Carruth [mailto:chandlerc at google.com]
Sent: Thursday, May 19, 2016 7:03 PM
To: Demikhovsky, Elena <elena.demikhovsky at
intel.com<mailto:elena.demikhovsky at intel.com>>; anemet at
apple.com<mailto:anemet at apple.com>; Sanjoy Das <sanjoy at
playingwithpointers.com<mailto:sanjoy at playingwithpointers.com>>
Cc: Saito, Hideki <hideki.saito at intel.com<mailto:hideki.saito at
intel.com>>; llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Andrew Trick <atrick at apple.com<mailto:atrick at
apple.com>>
Subject: Re: [llvm-dev] Working on FP SCEV Analysis
On Thu, May 19, 2016 at 7:03 AM Demikhovsky, Elena <elena.demikhovsky at
intel.com<mailto:elena.demikhovsky at intel.com>>
wrote:> One option would be to extend InductionDescriptor::isInductionPHI in the
vectorizer to directly analyze the PHIs without SCEV support as Sanjoy
suggested. I *think* that that could be sufficient to handle case B.
I implemented this with FP SCEV and the code looks very structured, including
SCEVExpander. Extending the existing structures without implementing FP SCEV
will be problematic.
And my end goal is to handle case *A*.
Ok, but there have been *numerous* requests for an explanation of why this is
important, and that hasn't emerged yet.
We really need to have a clear understanding of the relative importance of
solving these problems in order to understand the best approach.
- Elena
From: anemet at apple.com<mailto:anemet at apple.com> [mailto:anemet at
apple.com<mailto:anemet at apple.com>]
Sent: Thursday, May 19, 2016 07:43
To: Sanjoy Das <sanjoy at playingwithpointers.com<mailto:sanjoy at
playingwithpointers.com>>
Cc: Demikhovsky, Elena <elena.demikhovsky at
intel.com<mailto:elena.demikhovsky at intel.com>>; Saito, Hideki
<hideki.saito at intel.com<mailto:hideki.saito at intel.com>>;
llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Andrew Trick <atrick at apple.com<mailto:atrick at
apple.com>>
Subject: Re: [llvm-dev] Working on FP SCEV Analysis
On May 18, 2016, at 12:17 PM, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Demikhovsky, Elena wrote:> Even then, I'd personally want to see further evidence of why the
correct solution is to model the floating point IV in SCEV rather than
find a more powerful way of converting the IV to an integer that
models> the non-integer values taken on by the IV. As an example, if the use
case is the following code with appropriate flags to relax IEEE
semantics so this looks like normal algabra etc:
> for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A**
...
> I'd rather see us cleverly turn it into:
> float f = 0.01f;
> for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B**
I can later try to enhance IndVarSimplify::handleFloatingPointIV() in
order to convert**A** to **B**.
But **B** is exactly the case I’m starting from. The main IV “i” is
integer. The variable “f” is also considered as IV in this loop.
And this loop is not vectorized because “f” is floating point.
I don’t think that the case **B** is uncommon.
If B is the case we actually care about, I'd say changing SCEV to work with
floating points is an overkill. How would you expect an SCEVFAddExpr to help
vectorize B, other than tell you what the initial value and the increment is
(and these can be found with a simple value analysis)?
One option would be to extend InductionDescriptor::isInductionPHI in the
vectorizer to directly analyze the PHIs without SCEV support as Sanjoy
suggested. I *think* that that could be sufficient to handle case B.
Then if we find other pressing cases to handle we can rethink the strategy.
Also the current diagnostics is pretty bad for Hideki’s testcase with TTT as
float. This is what we currently report with -Rpass-analysis=loop-vectorize:
/tmp/sss.c:3:6: remark: loop not vectorized: value that could not be
identified as reduction is used outside the loop
[-Rpass-analysis=loop-vectorize]
I have no clue why we say that the value is used outside the loop. I think this
should just say that we have a loop-variant value that we couldn’t identify
either as an induction or as a reduction.
Adam
If we're interested in handling complex variants of A directly: computing
trip counts, proving away predicates etc. without translating the loops to use
integer IVs (perhaps because we can't legally do so), then I can see FP-SCEV
as a reasonable implementation strategy, but it looks like the general consensus
is that such cases are rare and generally not worth optimizing?
-- Sanjoy
-*/Elena/*
---------------------------------------------------------------------
Intel Israel (74) Limited
This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
---------------------------------------------------------------------
Intel Israel (74) Limited
This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160520/ab79bae3/attachment.html>
Adam, thanks for the clarification.
FP induction analysis should be useful for other loop optimizations that care
about cross-iteration dependence.
Thus, I think the mechanism is best implemented as an analysis or a utility, as
opposed to something confined
inside vectorizer. Any objections in this general direction?
Thanks,
Hideki
From: anemet at apple.com [mailto:anemet at apple.com]
Sent: Friday, May 20, 2016 11:32 AM
To: Saito, Hideki <hideki.saito at intel.com>
Cc: Chandler Carruth <chandlerc at google.com>; Demikhovsky, Elena
<elena.demikhovsky at intel.com>; Sanjoy Das <sanjoy at
playingwithpointers.com>; llvm-dev <llvm-dev at lists.llvm.org>; Andrew
Trick <atrick at apple.com>
Subject: Re: [llvm-dev] Working on FP SCEV Analysis
Hi Hideki,
I like this summary overall, thanks. More below.
On May 20, 2016, at 10:04 AM, Saito, Hideki <hideki.saito at
intel.com<mailto:hideki.saito at intel.com>> wrote:
To the best of my experience, handling case B (secondary induction) is
must-have, and if I’m not mistaken,
people aren’t opposed to that.
For me, handling case A (primary induction) is “why not?”, but I certainly admit
that that can be very naïve
thinking coming from lack of good understanding on SCEV and their proper usages.
Now, let’s assume we
can postpone discussion about case A. What is the best approach to handle case
B? Let me summarize
the discussion so far. Hope I didn’t miss anything.
1)
Extend SCEV was the initial approach taken by Elena.
Elena thinks this solution ”looks very structured”.
If I’m not mistaken, some people think this is overkill and
overly complicates already complicated SCEV.
Anyone care to look at the patch Elena came up with?
2)
IndVarSimplify::handleFloatingPointIV (mentioned by Andy)
This transforms integer-valued FP (primary) IV into integer IV
and convert.
Chandler says most of Graphics shading language use case
mentioned by Owen
should be handled here.
It certainly has the logic of detecting FP induction, but Andy
punted discussions
on non-integer valued IV issues to MichaelZ and Adam.
My understanding is that we only need this for *A* not for *B*.
On the specific issue of non-integer values, there is simply no attempt made in
the code to deal with them. That said, I think it should be possible to compute
the trip count and then derive an integer induction variable controlling the
loop.
3)
extend InductionDescriptor::isInductionPHI in the vectorizer to directly analyze
the PHIs without SCEV support
(mentioned by Adam)
If this is the standard way to deal with all secondary
inductions, it certainly looks attractive.
Elena, would you try doing this and compare with 1)?
Just to clarify, the code is currently structured to check if the PHI is an
add-recurrence that was detected by SCEV. The idea is to add a fall-back to
analyze the PHI directly if its type is a float.
There is already precedence for such things in LV. We support more reductions
(including floating-point) than what SCEV can analyze, therefore
RecurrenceDescriptor::AddReductionVar needs to analyze PHIs directly.
Adam
Thanks,
Hideki
----------------------
I looked at what our FORTRAN compiler (non-LLVM) does for the following (x, y,
z, and f are float by default typing,
based on names).
subroutine foo(x, y, z, A, N)
double precision A(N)
do f = x, y, z
A(f) = f
enddo
end
The frontend computes the trip count outside of the loop (per language rule) and
uses an integer primary
induction variable (compile-generated) for loop control. So, (future) FORTRAN
usage doesn’t seem to be
a good example for promoting support for case A (= FP primary induction
variable).
From: Chandler Carruth [mailto:chandlerc at google.com]
Sent: Thursday, May 19, 2016 7:03 PM
To: Demikhovsky, Elena <elena.demikhovsky at
intel.com<mailto:elena.demikhovsky at intel.com>>; anemet at
apple.com<mailto:anemet at apple.com>; Sanjoy Das <sanjoy at
playingwithpointers.com<mailto:sanjoy at playingwithpointers.com>>
Cc: Saito, Hideki <hideki.saito at intel.com<mailto:hideki.saito at
intel.com>>; llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Andrew Trick <atrick at apple.com<mailto:atrick at
apple.com>>
Subject: Re: [llvm-dev] Working on FP SCEV Analysis
On Thu, May 19, 2016 at 7:03 AM Demikhovsky, Elena <elena.demikhovsky at
intel.com<mailto:elena.demikhovsky at intel.com>>
wrote:> One option would be to extend InductionDescriptor::isInductionPHI in the
vectorizer to directly analyze the PHIs without SCEV support as Sanjoy
suggested. I *think* that that could be sufficient to handle case B.
I implemented this with FP SCEV and the code looks very structured, including
SCEVExpander. Extending the existing structures without implementing FP SCEV
will be problematic.
And my end goal is to handle case *A*.
Ok, but there have been *numerous* requests for an explanation of why this is
important, and that hasn't emerged yet.
We really need to have a clear understanding of the relative importance of
solving these problems in order to understand the best approach.
- Elena
From: anemet at apple.com<mailto:anemet at apple.com> [mailto:anemet at
apple.com<mailto:anemet at apple.com>]
Sent: Thursday, May 19, 2016 07:43
To: Sanjoy Das <sanjoy at playingwithpointers.com<mailto:sanjoy at
playingwithpointers.com>>
Cc: Demikhovsky, Elena <elena.demikhovsky at
intel.com<mailto:elena.demikhovsky at intel.com>>; Saito, Hideki
<hideki.saito at intel.com<mailto:hideki.saito at intel.com>>;
llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at
lists.llvm.org>>; Andrew Trick <atrick at apple.com<mailto:atrick at
apple.com>>
Subject: Re: [llvm-dev] Working on FP SCEV Analysis
On May 18, 2016, at 12:17 PM, Sanjoy Das via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:
Demikhovsky, Elena wrote:> Even then, I'd personally want to see further evidence of why the
correct solution is to model the floating point IV in SCEV rather than
find a more powerful way of converting the IV to an integer that
models> the non-integer values taken on by the IV. As an example, if the use
case is the following code with appropriate flags to relax IEEE
semantics so this looks like normal algabra etc:
> for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A**
...
> I'd rather see us cleverly turn it into:
> float f = 0.01f;
> for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B**
I can later try to enhance IndVarSimplify::handleFloatingPointIV() in
order to convert**A** to **B**.
But **B** is exactly the case I’m starting from. The main IV “i” is
integer. The variable “f” is also considered as IV in this loop.
And this loop is not vectorized because “f” is floating point.
I don’t think that the case **B** is uncommon.
If B is the case we actually care about, I'd say changing SCEV to work with
floating points is an overkill. How would you expect an SCEVFAddExpr to help
vectorize B, other than tell you what the initial value and the increment is
(and these can be found with a simple value analysis)?
One option would be to extend InductionDescriptor::isInductionPHI in the
vectorizer to directly analyze the PHIs without SCEV support as Sanjoy
suggested. I *think* that that could be sufficient to handle case B.
Then if we find other pressing cases to handle we can rethink the strategy.
Also the current diagnostics is pretty bad for Hideki’s testcase with TTT as
float. This is what we currently report with -Rpass-analysis=loop-vectorize:
/tmp/sss.c:3:6: remark: loop not vectorized: value that could not be
identified as reduction is used outside the loop
[-Rpass-analysis=loop-vectorize]
I have no clue why we say that the value is used outside the loop. I think this
should just say that we have a loop-variant value that we couldn’t identify
either as an induction or as a reduction.
Adam
If we're interested in handling complex variants of A directly: computing
trip counts, proving away predicates etc. without translating the loops to use
integer IVs (perhaps because we can't legally do so), then I can see FP-SCEV
as a reasonable implementation strategy, but it looks like the general consensus
is that such cases are rare and generally not worth optimizing?
-- Sanjoy
-*/Elena/*
---------------------------------------------------------------------
Intel Israel (74) Limited
This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
---------------------------------------------------------------------
Intel Israel (74) Limited
This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160520/3e728240/attachment-0001.html>
Adding support for FP inductions through isInductionPHI() is certainly possible, I have a relatively small local patch that does exactly that for simple fp add-recurrence cases, along with changes to the vectorizer to make it aware of FP inductions. It won't get give you the powerful reasoning capabilities of SCEV, but for the B-like cases it should work. Amara On 20 May 2016 at 19:31, Adam Nemet via llvm-dev <llvm-dev at lists.llvm.org> wrote:> Hi Hideki, > > I like this summary overall, thanks. More below. > > On May 20, 2016, at 10:04 AM, Saito, Hideki <hideki.saito at intel.com> wrote: > > > To the best of my experience, handling case B (secondary induction) is > must-have, and if I’m not mistaken, > people aren’t opposed to that. > > For me, handling case A (primary induction) is “why not?”, but I certainly > admit that that can be very naïve > thinking coming from lack of good understanding on SCEV and their proper > usages. Now, let’s assume we > can postpone discussion about case A. What is the best approach to handle > case B? Let me summarize > the discussion so far. Hope I didn’t miss anything. > > 1) > Extend SCEV was the initial approach taken by Elena. > Elena thinks this solution ”looks very structured”. > If I’m not mistaken, some people think this is overkill and > overly complicates already complicated SCEV. > Anyone care to look at the patch Elena came up with? > 2) > IndVarSimplify::handleFloatingPointIV (mentioned by Andy) > This transforms integer-valued FP (primary) IV into integer > IV and convert. > Chandler says most of Graphics shading language use case > mentioned by Owen > should be handled here. > It certainly has the logic of detecting FP induction, but > Andy punted discussions > on non-integer valued IV issues to MichaelZ and Adam. > > > My understanding is that we only need this for *A* not for *B*. > > On the specific issue of non-integer values, there is simply no attempt made > in the code to deal with them. That said, I think it should be possible to > compute the trip count and then derive an integer induction variable > controlling the loop. > > 3) > extend InductionDescriptor::isInductionPHI in the vectorizer to directly > analyze the PHIs without SCEV support > (mentioned by Adam) > If this is the standard way to deal with all secondary > inductions, it certainly looks attractive. > Elena, would you try doing this and compare with 1)? > > > Just to clarify, the code is currently structured to check if the PHI is an > add-recurrence that was detected by SCEV. The idea is to add a fall-back to > analyze the PHI directly if its type is a float. > > There is already precedence for such things in LV. We support more > reductions (including floating-point) than what SCEV can analyze, therefore > RecurrenceDescriptor::AddReductionVar needs to analyze PHIs directly. > > Adam > > > Thanks, > Hideki > > ---------------------- > I looked at what our FORTRAN compiler (non-LLVM) does for the following (x, > y, z, and f are float by default typing, > based on names). > > subroutine foo(x, y, z, A, N) > double precision A(N) > do f = x, y, z > A(f) = f > enddo > end > > The frontend computes the trip count outside of the loop (per language rule) > and uses an integer primary > induction variable (compile-generated) for loop control. So, (future) > FORTRAN usage doesn’t seem to be > a good example for promoting support for case A (= FP primary induction > variable). > > > > From: Chandler Carruth [mailto:chandlerc at google.com] > Sent: Thursday, May 19, 2016 7:03 PM > To: Demikhovsky, Elena <elena.demikhovsky at intel.com>; anemet at apple.com; > Sanjoy Das <sanjoy at playingwithpointers.com> > Cc: Saito, Hideki <hideki.saito at intel.com>; llvm-dev > <llvm-dev at lists.llvm.org>; Andrew Trick <atrick at apple.com> > Subject: Re: [llvm-dev] Working on FP SCEV Analysis > > On Thu, May 19, 2016 at 7:03 AM Demikhovsky, Elena > <elena.demikhovsky at intel.com> wrote: > >> One option would be to extend InductionDescriptor::isInductionPHI in the >> vectorizer to directly analyze the PHIs without SCEV support as Sanjoy >> suggested. I *think* that that could be sufficient to handle case B. > > I implemented this with FP SCEV and the code looks very structured, > including SCEVExpander. Extending the existing structures without > implementing FP SCEV will be problematic. > And my end goal is to handle case *A*. > > Ok, but there have been *numerous* requests for an explanation of why this > is important, and that hasn't emerged yet. > > We really need to have a clear understanding of the relative importance of > solving these problems in order to understand the best approach. > > > > > - Elena > > From: anemet at apple.com [mailto:anemet at apple.com] > Sent: Thursday, May 19, 2016 07:43 > To: Sanjoy Das <sanjoy at playingwithpointers.com> > Cc: Demikhovsky, Elena <elena.demikhovsky at intel.com>; Saito, Hideki > <hideki.saito at intel.com>; llvm-dev <llvm-dev at lists.llvm.org>; Andrew Trick > <atrick at apple.com> > > Subject: Re: [llvm-dev] Working on FP SCEV Analysis > > > > On May 18, 2016, at 12:17 PM, Sanjoy Das via llvm-dev > <llvm-dev at lists.llvm.org> wrote: > > > > > > Demikhovsky, Elena wrote: > >> Even then, I'd personally want to see further evidence of why the > correct solution is to model the floating point IV in SCEV rather than > find a more powerful way of converting the IV to an integer that models >> the non-integer values taken on by the IV. As an example, if the use > case is the following code with appropriate flags to relax IEEE > semantics so this looks like normal algabra etc: > >> for (float f = 0.01f; f < 1.0f; f += 0.01f) ç **A** > > ... > >> I'd rather see us cleverly turn it into: > >> float f = 0.01f; > >> for (int i = 1; i < 100; i += 1, f += 0.01f) ç **B** > > I can later try to enhance IndVarSimplify::handleFloatingPointIV() in > order to convert**A** to **B**. > > But **B** is exactly the case I’m starting from. The main IV “i” is > integer. The variable “f” is also considered as IV in this loop. > > And this loop is not vectorized because “f” is floating point. > > I don’t think that the case **B** is uncommon. > > > If B is the case we actually care about, I'd say changing SCEV to work with > floating points is an overkill. How would you expect an SCEVFAddExpr to > help vectorize B, other than tell you what the initial value and the > increment is (and these can be found with a simple value analysis)? > > > One option would be to extend InductionDescriptor::isInductionPHI in the > vectorizer to directly analyze the PHIs without SCEV support as Sanjoy > suggested. I *think* that that could be sufficient to handle case B. > > Then if we find other pressing cases to handle we can rethink the strategy. > > Also the current diagnostics is pretty bad for Hideki’s testcase with TTT as > float. This is what we currently report with > -Rpass-analysis=loop-vectorize: > > > /tmp/sss.c:3:6: remark: loop not vectorized: value that could not be > identified as reduction is used outside the loop > [-Rpass-analysis=loop-vectorize] > > > I have no clue why we say that the value is used outside the loop. I think > this should just say that we have a loop-variant value that we couldn’t > identify either as an induction or as a reduction. > > Adam > > > > > If we're interested in handling complex variants of A directly: computing > trip counts, proving away predicates etc. without translating the loops to > use integer IVs (perhaps because we can't legally do so), then I can see > FP-SCEV as a reasonable implementation strategy, but it looks like the > general consensus is that such cases are rare and generally not worth > optimizing? > > -- Sanjoy > > > -*/Elena/* > > --------------------------------------------------------------------- > Intel Israel (74) Limited > > This e-mail and any attachments may contain confidential material for > the sole use of the intended recipient(s). Any review or distribution > by others is strictly prohibited. If you are not the intended > recipient, please contact the sender and delete all copies. > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > > > > --------------------------------------------------------------------- > Intel Israel (74) Limited > > This e-mail and any attachments may contain confidential material for > the sole use of the intended recipient(s). Any review or distribution > by others is strictly prohibited. If you are not the intended > recipient, please contact the sender and delete all copies. > > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >