[LLVMdev] 'loop invariant code motion' and 'Reassociate Expression'
baldrick at free.fr
Fri May 3 08:58:06 PDT 2013
On 25/04/13 21:18, Preston Briggs wrote:
> On Thu, Apr 25, 2013 at 9:18 AM, Arnold Schwaighofer <aschwaighofer at apple.com
> <mailto:aschwaighofer at apple.com>> wrote:
> > On Apr 25, 2013, at 10:51 AM, Preston Briggs <preston.briggs at gmail.com
> <mailto:preston.briggs at gmail.com>> wrote:
> > > It's an interesting problem.
> > > The best stuff I've seen published is by Cooper, Eckhart, & Kennedy, in
> PACT '08.
> > > Cooper gives a nice intro in one of his lectures:
> > > I can't tell, quickly, what's going on in Reassociate;
> > Reasscociate is using a reverse postorder numbering, my guess is that the
> idea is from Briggs, Cooper ’94.
> I believe some of the ideas are from Briggs & Cooper,
> but there's other stuff in there I've never seen, e.g., Carmichael Numbers.
> I mean, we can all google Carmichael Numbers, but I had never heard of them in
> relation to this problem.
I added those. If you read the comments with Carmichael in them you'll see what
the problem was. I was confronted with that problem and thinking on it lead me
to Carmichael numbers. It's a general issue about having a
(value, multiplicity) pair to represent (value op value op ... op value): how
many bits are needed to store an arbitrary multiplicity? For all operations
that LLVM supports the answer is: the number of bits in "value". Any
multiplicity that is bigger than what fits in that number of bits is equivalent
to a smaller multiplicity that does fit in that number of bits.
More information about the llvm-dev