'loop invariant code motion' and 'Reassociate Expression'

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: http://www.cs.rice.edu/~keith/512/2012/Lectures/26ReassocII-1up.pdf
I can’t tell, quickly, what’s going on in Reassociate;
as usual, the documentation resolutely avoids giving any credit for the ideas.
Why is that?

Preston

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: http://www.cs.rice.edu/~keith/512/2012/Lectures/26ReassocII-1up.pdf
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.

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: http://www.cs.rice.edu/~keith/512/2012/Lectures/26ReassocII-1up.pdf
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.

Preston

Hi Preston,

>
> > 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:
http://www.cs.rice.edu/~keith/512/2012/Lectures/26ReassocII-1up.pdf
<http://www.cs.rice.edu/~keith/512/2012/Lectures/26ReassocII-1up.pdf>
> > 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.

Ciao, Duncan.