[llvm-dev] Working on FP SCEV Analysis
Amara Emerson via llvm-dev
llvm-dev at lists.llvm.org
Tue May 24 08:00:22 PDT 2016
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
>
More information about the llvm-dev
mailing list