Re: Loop optimizer issues

[Michael S. Zick <mszick at goquest dot com>]

On Tuesday 03 June 2003 04:03 am, Zdenek Dvorak wrote:
> Hello,
>
> > >>The fold function can be used for simplifying these expressions.
> > >>
> > >>However as Zack has pointed out in his paper there are 4 fold
> > >> functions: 3 at rtl level, and one fold at tree level.
> > >
> > >and one more of mine that I have added due to iv analysis :-( I
> > >just cannot cope with other rtl simplifiers that hapily "simplify"
> > >2*3*4*x to (((x << 2) * 3) << 1).
> >
> > Huh? Why shouldn't that just simplify to 24*x (or (x << 4) + (x <<
> > 3))???  
Ah, yes - the old "decompose into [shift | shift and add] sequence;
minimize".  
We are not talking of speeding up the compiler here, but this does 
generate a "make it as canonical as possible" answer.
Provided you adopt some rules of ordering on the result;
"bit order" is convenient rule.

> > If this is a serious example than this indicates not that you
> > need yet another friggin' RTL folder, but that the existing one is
> > utterly broken
> > Gr.
>
> in fact you are half-right; if it did simplification to (x<<4) + (x<<3),
> it would be still useless for me.  I do not need to simplify in sense
> "make it run fast", but in sense "make it as canonical as possible so
> that it is easy to manipulate/compare/...
>
The answer is: F.x 'equiv' (x<<3)+(x<<4)

'equiv' NOT 'eq' since (+) does not imply order on the sub-expressions.
Or; use the "bit order" rule to always order the shifts least-to-most
and use an 'eq' check.

In the name pool for 'x' define the name of F.x at this point as the
character string: "(x<<3)+(x<<4)" or as a list of node pointers for
each of the components of that character string.

Characters are easier on the e-mail client, so...
What you have, in effect, is:
#name "(x<<3)" T.x.0
#name "(x<<4)" T.x.1
#name "(x<<3)+(x<<4)" T.x.2 
and
#alias "T.x.0+T.x.1" T.x.2
When later encountering another "(*)" expression "on x", 
do the same - decompose to [shift | shift and add] and 
minimize.  If, along the way, you find a name already defined
(such as "(x<<4)") then you have a common sub-expression
usable as the pointer to "T.x.1"

Note that the same decomposed representation can be used
to go from "constant" to "expression".
I.E:
#const "24" "(x<<3)+(x<<4)"
or decomposing the (4):
#name "(x<<2)+(x<<2)" "(x<<4)"

Just a matter of factoring based on the bit representation of
the constant. 
If you don't have a copy of that "bit parallel" find {leading|trailing}
{one|zero} routine I posted, drop me a note.

Mike
> Zdenek