llvm dev - Nov 2011 - [LLVMdev] Alternate instruction sequences

On Thu, 10 Nov 2011 10:46:27 +0100, Duncan Sands wrote:
> Hi Carlo, the general policy is to canonicalize IR to some particular
> choice.  For example, if I1, I2, etc are all equivalent to each 
> other,
> then usually one of them will have been chosen as the canonical form
> (say I1) and all the others will be turned into I1.  If this is not
> the best choice for some target, then the code generators for that
> target need to transform it into something better for the target, but
> this is not at the IR level.
This might work for single instructions or simple instruction sequences 
but doesn't apply to, let's say, regions. As an example, take a loop 
that could be rewritten (unrolled, tiled, etc.) so that different 
versions of the same loop have wildly different memory access patterns. 
In this case, in order to choose the "best" version, the IR-level 
transform would have to know the details of the cache/memory subsytems 
of the current arch.

On Thu, 2011-11-10 at 12:59 +0100, Carlo Alberto Ferraris
wrote:
> On Thu, 10 Nov 2011 10:46:27 +0100, Duncan Sands wrote:
> > Hi Carlo, the general policy is to canonicalize IR to some particular
> > choice.  For example, if I1, I2, etc are all equivalent to each 
> > other,
> > then usually one of them will have been chosen as the canonical form
> > (say I1) and all the others will be turned into I1.  If this is not
> > the best choice for some target, then the code generators for that
> > target need to transform it into something better for the target, but
> > this is not at the IR level.
> 
> This might work for single instructions or simple instruction sequences 
> but doesn't apply to, let's say, regions. As an example, take a
loop
> that could be rewritten (unrolled, tiled, etc.) so that different 
> versions of the same loop have wildly different memory access patterns. 
> In this case, in order to choose the "best" version, the IR-level
> transform would have to know the details of the cache/memory subsytems 
> of the current arch.
There has been some good work in this general area by Jason Ansel and
collaborators at MIT. They have developed a project called PetaBricks
(which has been released under the MIT license) --
http://projects.csail.mit.edu/petabricks/ -- and I think that this is
going to be a very important technique, at least for numerical
algorithms, in the near future. As there is apparently interest, I think
that we should strongly consider added an "alternatives" feature (on
the
block and/or function level) to the LLVM IR in order to facilitate
implementing this kind of approach. I think that it is often true that
only the backend code generator has enough information to choose between
alternative implementations, and so I think this would be an appropriate
addition. If we specify that each alternative must have identical side
effects, then I think that the default (backward-compatible)
implementation is easy: ignore the alternatives.

 -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
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory

On Thu, 10 Nov 2011 06:43:15 -0600, Hal Finkel wrote:
> As there is apparently interest, I think
> that we should strongly consider added an "alternatives" feature
(on
> the
> block and/or function level) to the LLVM IR in order to facilitate
> implementing this kind of approach.
Probably adding an explicit mechanism will be met with considerable 
resistence because it involves modifying the IR. That's why I was 
proposing to sidestep the issue by leveraging what the IR already 
provides.
Unfortunately I haven't heard any suggestion/feedback about the 
proposed syntax. Should I interpret this lack of comments as an 
indication of it being a good solution or what? Can I go ahead and make 
a patch for the docs to formalize the idea?
B.r.
Carlo Alberto