Johannes Doerfert
2014-Aug-20 16:18 UTC
[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
On 08/20, Arnold Schwaighofer wrote:> > > On Aug 20, 2014, at 8:08 AM, Robison, Arch <arch.robison at intel.com> wrote: > > > >> I recommend that you send patches for an implementation > >> (including the Loop::GetAnnotatedVectorSafelen function > >> and associated updates to the vectorizer) for review. > > > > I expect to send the patches for review later this week. > > > >> Make sure to remember LangRef updates! > > > > Thanks for the reminder. > > > >> Also, looking at the original proposal again, I see no reason > >> to restrict this to an i32: we might as well allow it to be an > >> i64 obviously we don't have billion-lane vectors, but the > >> metadata can also be useful for other kinds of analysis). > > > > I doubt there is much advantage between knowing the minimum loop-carried > > dependence difference is 1u<<31 or 1u<<63. Unless there is a clear > > need for the higher values less than infinity, It would seem simpler > > for now to adopt the same conventions as llvm.loop.vectorize.width > > so that some processing infrastructure can be shared easily. > > > >> I don't like using the name 'safelen' however. I can forgive OpenMP > >> for choosing such a short name because people need to type it, > >> but I'd prefer that the metadata have a more-descriptive name. > >> minimum_dependency_distance is perhaps better. > > > > I'm open to naming suggestions, though I'm wondering if sticking with > > what is now a term of art in OpenMP might be the least of all evils, > > because the semantics turn out to be a little more subtle than > > just a minimum dependence distance. My current wording of the semantics > > for safelen of k are: > > > > /// The loop can be assumed to have no loop-carried > > /// lexically backward dependencies with distance less than k. > > This means you would allow lexically forward dependencies which complicates things (this would need more infrastructure in clang). You need to carry over “source order” from the front-end. Because the dependency is loop carried llvm would be allowed to move loads and stores within the loop:This should not be that hard (see below).> Lexical forward dependency: > > #pragma vectorize safelen(4) > for (i = …) { > a[i] = b[i] + z[i]; > c[i] = a[i-1] + 1; > } > > LLVM might tranform this loop to: > > for (i = …) { > c[i] = a[i-1] + 1; > a[i] = b[i] + z[i]; > } > > if we now vectorize this (without knowledge of the orignal source order) we get the wrong answer: > > for (i = …) { > c[i] = a[i-1:i+2] + 1; > a[i:i+3] = b[i] + z[i]; > } > > Alternatively, the metadata loop.vectorize.safelen would have to prevent any such reordering of accesses i.e. any pass that reorders memory accesses would have to be aware of it which is fragile.Could we number the memory accesses for such loops (e.g., in clang)? Adding metadata to each memory access which points to the safelen annotation and contains an increasing constant would be similarly fragile as other constructions we use at the moment. However, it would allow us to determine iff the current order is still the original one or not. (At least if I did not miss anything). Best regards, Johannes -- Johannes Doerfert Researcher / PhD Student Compiler Design Lab (Prof. Hack) Saarland University, Computer Science Building E1.3, Room 4.26 Tel. +49 (0)681 302-57521 : doerfert at cs.uni-saarland.de Fax. +49 (0)681 302-3065 : http://www.cdl.uni-saarland.de/people/doerfert -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 213 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140820/12b3dcf1/attachment.sig>
Arnold Schwaighofer
2014-Aug-20 16:29 UTC
[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
> On Aug 20, 2014, at 9:18 AM, Johannes Doerfert <doerfert at cs.uni-saarland.de> wrote: > > On 08/20, Arnold Schwaighofer wrote: >> >> >> This means you would allow lexically forward dependencies which complicates things (this would need more infrastructure in clang). You need to carry over “source order” from the front-end. Because the dependency is loop carried llvm would be allowed to move loads and stores within the loop: > This should not be that hard (see below). > >> Lexical forward dependency: >> >> #pragma vectorize safelen(4) >> for (i = …) { >> a[i] = b[i] + z[i]; >> c[i] = a[i-1] + 1; >> } >> >> LLVM might tranform this loop to: >> >> for (i = …) { >> c[i] = a[i-1] + 1; >> a[i] = b[i] + z[i]; >> } >> >> if we now vectorize this (without knowledge of the orignal source order) we get the wrong answer: >> >> for (i = …) { >> c[i] = a[i-1:i+2] + 1; >> a[i:i+3] = b[i] + z[i]; >> } >> >> Alternatively, the metadata loop.vectorize.safelen would have to prevent any such reordering of accesses i.e. any pass that reorders memory accesses would have to be aware of it which is fragile. > Could we number the memory accesses for such loops (e.g., in clang)? > Adding metadata to each memory access which points to the safelen > annotation and contains an increasing constant would be similarly > fragile as other constructions we use at the moment. However, it would > allow us to determine iff the current order is still the original one or > not. (At least if I did not miss anything).This is what I meant by carry over source order. You either teach clang to number accesses or you have an early llvm pass that does the same.
On 20 August 2014 17:29, Arnold Schwaighofer <aschwaighofer at apple.com> wrote:> This is what I meant by carry over source order. You either teach clang to number accesses or you have an early llvm pass that does the same.Does Clang do any early reordering of source code? If so, we need to teach Clang to deal with that, to keep *source* order, not IR order. cheers, --renato
----- Original Message -----> From: "Arnold Schwaighofer" <aschwaighofer at apple.com> > To: "Johannes Doerfert" <doerfert at cs.uni-saarland.de> > Cc: llvmdev at cs.uiuc.edu, "Arch Robison" <arch.robison at intel.com> > Sent: Wednesday, August 20, 2014 11:29:16 AM > Subject: Re: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen" > > > > On Aug 20, 2014, at 9:18 AM, Johannes Doerfert > > <doerfert at cs.uni-saarland.de> wrote: > > > > On 08/20, Arnold Schwaighofer wrote: > >> > >> > >> This means you would allow lexically forward dependencies which > >> complicates things (this would need more infrastructure in > >> clang). You need to carry over “source order” from the front-end. > >> Because the dependency is loop carried llvm would be allowed to > >> move loads and stores within the loop: > > This should not be that hard (see below). > > > >> Lexical forward dependency: > >> > >> #pragma vectorize safelen(4) > >> for (i = …) { > >> a[i] = b[i] + z[i]; > >> c[i] = a[i-1] + 1; > >> } > >> > >> LLVM might tranform this loop to: > >> > >> for (i = …) { > >> c[i] = a[i-1] + 1; > >> a[i] = b[i] + z[i]; > >> } > >> > >> if we now vectorize this (without knowledge of the orignal source > >> order) we get the wrong answer: > >> > >> for (i = …) { > >> c[i] = a[i-1:i+2] + 1; > >> a[i:i+3] = b[i] + z[i]; > >> } > >> > >> Alternatively, the metadata loop.vectorize.safelen would have to > >> prevent any such reordering of accesses i.e. any pass that > >> reorders memory accesses would have to be aware of it which is > >> fragile. > > Could we number the memory accesses for such loops (e.g., in > > clang)? > > Adding metadata to each memory access which points to the safelen > > annotation and contains an increasing constant would be similarly > > fragile as other constructions we use at the moment. However, it > > would > > allow us to determine iff the current order is still the original > > one or > > not. (At least if I did not miss anything). > > > This is what I meant by carry over source order. You either teach > clang to number accesses or you have an early llvm pass that does > the same.We must do this directly in the frontend. Relying on another pass run early would be bad because it would introduce a hard-to-enforce contract affecting correctness. Also, we should probably allow for missing access numbers, so long as everything is in order (because the optimizer might eliminate some of them). Some memory-access instructions might also have more than one access number (after GVN, vectorization, etc.), and we should allow for that. -Hal> _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Maybe Matching Threads
- [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
- [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
- [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
- [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
- [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"