----- 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
> 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.Instead of a pass, the marking could be a utility routine that client front ends can run? Or maybe it's not a big deal. I guess I'll find out when I modify the Julia front-end :-)> 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.I concur that holes and duplicates should be allowed. - Arch Robison Intel Corporation
On 20 August 2014 18:24, Hal Finkel <hfinkel at anl.gov> wrote:> 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.What about inlining? Say metadata IDs 1, 2, 3 from loop 1 are inlined onto metadata 1, 2, 3 from loop 2. You'll end up with 1, 2, 3, 1, 2, 3, what does that mean? Then, an optimization pass removes 1, 2, leaves 3, 1, and deletes 2, 3. Does that mean they're out of order? Inlining will probably have to learn how to re-order in every linined to loops while still keeping the original ids on the original loops. That will also involve adding N to the { M+1 ~ K } set that were left after the inlining N nodes at position M. cheers, --renato
----- Original Message -----> From: "Renato Golin" <renato.golin at linaro.org> > To: "Hal Finkel" <hfinkel at anl.gov> > Cc: "Arnold Schwaighofer" <aschwaighofer at apple.com>, "Arch Robison" <arch.robison at intel.com>, "LLVM Dev" > <llvmdev at cs.uiuc.edu> > Sent: Wednesday, August 20, 2014 2:16:56 PM > Subject: Re: [LLVMdev] Proposal for ""llvm.mem.vectorize.safelen" > > On 20 August 2014 18:24, Hal Finkel <hfinkel at anl.gov> wrote: > > 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. > > What about inlining? Say metadata IDs 1, 2, 3 from loop 1 are inlined > onto metadata 1, 2, 3 from loop 2. You'll end up with 1, 2, 3, 1, 2, > 3, what does that mean? Then, an optimization pass removes 1, 2, > leaves 3, 1, and deletes 2, 3. Does that mean they're out of order?I don't understand. I think that the numbering would need to be specific to the loop id. -Hal> > Inlining will probably have to learn how to re-order in every linined > to loops while still keeping the original ids on the original loops. > That will also involve adding N to the { M+1 ~ K } set that were left > after the inlining N nodes at position M. > > cheers, > --renato >-- Hal Finkel Assistant Computational Scientist Leadership Computing Facility Argonne National Laboratory
Alexander Musman
2014-Aug-20 19:42 UTC
[LLVMdev] Proposal for ""llvm.mem.vectorize.safelen"
Thanks for working on this. I expect that stmts are emitted without reordering by clang, though may be there are some corner cases I do not know about. I attached a clang patch for experiments - it adds "!"safelen" !LoopId Len N" metadata for loops with "omp simd safelen(Len)" (see test/OpenMP/simd_metadata.c for example). You will also need to change "safelen" to whatever metadata name we'll come up with. Thanks, Alexander 2014-08-20 21:57 GMT+04:00 Robison, Arch <arch.robison at intel.com>:> > 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. > > Instead of a pass, the marking could be a utility routine that client > front ends can run? Or maybe it's not a big deal. I guess I'll find out > when I modify the Julia front-end :-) > > > 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. > > I concur that holes and duplicates should be allowed. > > - Arch Robison > Intel Corporation > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140820/c3cde653/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: clang_safelen_marking Type: application/octet-stream Size: 6624 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140820/c3cde653/attachment.obj>