[LLVMdev] 'loop invariant code motion' and 'Reassociate Expression'

[Duncan Sands]

Hi Preston,

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