Re: [tree-ssa] CCP inefficiencies

[law at redhat dot com]

In message <7C33061F-3F6F-11D7-B968-000393575BCC@dberlin.org>, Daniel Berlin wr
ites:
 >
 >On Thursday, February 13, 2003, at 11:10  AM, law@redhat.com wrote:
 >
 >> In message <1045151865.10505.54.camel@frodo>, Diego Novillo writes:
 >>> On Wed, 2003-02-12 at 18:08, law@redhat.com wrote:
 >>>
 >>>> It looks like a lot of the problem is the over-eager copying of nodes
 >>>> so that we can replace their operands and try to fold them.  This is
 >>>> in itself rather expensive, but it also creates lots of garbage for
 >>>> the collector to clean up.  Ugh.
 >>>>
 >>> Yeah.  Attribute that to Diego being a lazy bum(1).  I originally had
 >>> the idea of having some sort of undo buffer so that CCP could try the
 >>> replacement and fold, but copying the expression tree was so much 
 >>> easier
 >>> :)
 >> Or a non-destructive simplifier.  I'm not sure which is going to make
 >> more sense, but it's pretty clear we need something better than just
 >> copying the nodes.
 >>
 >Yeah, I was going to look at a non-destructive simplifier eventually, 
 >but i presume this is what you've done in your work.
 >We should always be able to determine if a node will become constant or 
 >has a good chance before ever copying it just by seeing if
 >1. we've replaced all variables with constants
 >2. we've replaced a unary operator on a variable with a unary operator 
 >on a constant
 >3. we've replaced a binary operator on two variables with a binary 
 >operator on two constants
 >etc
 >
 >There's no need to copy the node to check if any of these cases hold.
I originally started with similar criteria -- interestingly enough 
we want to go ahead with simplifications *anytime* we're able to replace
a variable with a constant.

This was somewhat of a surprise, but failing to do so was causing us to
miss simplifications of certain relationals.  For example, if you
had:

  (lt (ssa_name X) (ssa_name Y))


  Let's assume that X has the unsigned bit set, but that it varies.  Let's
  then assume that we know Y is zero.  Even though you don't know what
  values X might take, you know that the comparison is always false.

There were other examples, but that's the type I saw we were missing
most often when requiring all variables to be replaced by constants
before copying & simplifying.

jeff