[LLVMdev] Alternate instruction sequences

[Hal Finkel]

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