Why can't CSE recognize const_int's in HIGH LO_SUM pair?

Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[John David Anglin]

In looking into the failure of 20010119-1.c at -O1 on the PA, I am wondering
why large constant values in HIGH LO_SUM pairs aren't recognized in jump
expansion?  For example, we have the following situation comparing 10 and
20000:

(insn 10 5 12 (set (reg/v:SI 95)
        (const_int 10 [0xa])) -1 (nil)
    (nil))

...

(insn/i 24 70 25 (set (reg:SI 99)
        (high:SI (const_int 20000 [0x4e20]))) -1 (nil)
    (nil))

(insn/i 25 24 26 (set (reg:SI 100)
	(lo_sum:SI (reg:SI 99)
	    (const_int 20000 [0x4e20]))) -1 (nil)
    (nil))

(jump_insn/i 26 25 71 (set (pc)
	(if_then_else (le (reg/v:SI 95)
		(reg:SI 100))
	    (label_ref 30)
	    (pc))) -1 (nil)
    (nil))

If I reduce the constant 20000 to 8191 so that it can be loaded in a single
insn, we get for the initial rtl:

(insn/i 24 23 25 (set (reg:SI 99)
        (const_int 8191 [0x1fff])) -1 (nil)
    (nil))

(jump_insn/i 25 24 26 (set (pc)
	(label_ref 30)) 270 {jump} (nil)
(nil))

and the dead code branch gets eliminated.  At higher opt levels, it appears
the loop pass detects the HIGH LO_SUM pair and deletes the dead code.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Richard Henderson]

On Fri, Sep 07, 2001 at 07:07:12PM -0400, John David Anglin wrote:
> (insn/i 24 70 25 (set (reg:SI 99)
>         (high:SI (const_int 20000 [0x4e20]))) -1 (nil)
>     (nil))
> 
> (insn/i 25 24 26 (set (reg:SI 100)
> 	(lo_sum:SI (reg:SI 99)
> 	    (const_int 20000 [0x4e20]))) -1 (nil)
>     (nil))

Why are you using high/lo_sum for constants?  high/lo_sum has
rather loose semantics, and you can't pull much information 
from them.

Better would be to emit the actual constants that the insns
in question will load into the hardware registers.


r~

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[John David Anglin]

> Better would be to emit the actual constants that the insns
> in question will load into the hardware registers.

Jeff probably could give the best answer but I think it has to do with
the way move insns are done in general.  I think the philosophy was to
make the rtl match as closely as possible the machine code.  However, I recall
a few months ago there were issues with high/lo_sum in pic code generation 
and one of the solutions discussed was delaying the generation of high/lo_sum
pairs until after reload.  Clearly, it is easier for the compiler to
deal with a simple constant or address.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Richard Henderson]

On Fri, Sep 07, 2001 at 09:30:05PM -0400, John David Anglin wrote:
> I think the philosophy was to make the rtl match as closely as
> possible the machine code.

Um, no, that's plainly false.  The machine will load some number
that has high bits set, and add some number that has low bits set.
If you ask Alpha to load 0x10001000, you'll get

	(set (reg) (const_int 0x10000000))
	(set (reg) (plus (reg) (const_int 0x1000))

which is exactly what the machine code is doing.  No need for 
high/lo_sum, and by not using them, we expose the exact constant
fragments to cse/combine/etc.


r~

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[John David Anglin]

> On Fri, Sep 07, 2001 at 09:30:05PM -0400, John David Anglin wrote:
> > I think the philosophy was to make the rtl match as closely as
> > possible the machine code.
> 
> Um, no, that's plainly false.  The machine will load some number
> that has high bits set, and add some number that has low bits set.
> If you ask Alpha to load 0x10001000, you'll get
> 
> 	(set (reg) (const_int 0x10000000))
> 	(set (reg) (plus (reg) (const_int 0x1000))
> 
> which is exactly what the machine code is doing.  No need for 
> high/lo_sum, and by not using them, we expose the exact constant
> fragments to cse/combine/etc.

I see what you saying.  Is jump expansion smart enough to figure out
that the final result for the above is the constant 0x10001000?  I'll
try to look into what's involved in changing to the above next week.

I think what has confused the issue is that the HP assembler knows how
to extract the high and low parts.  However, as you note, there are
benefits to creating the high and low parts directly in the compiler.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Jan Hubicka]

> > 	(set (reg) (const_int 0x10000000))
> > 	(set (reg) (plus (reg) (const_int 0x1000))
> 
> I see what you saying.  Is jump expansion smart enough to figure out
> that the final result for the above is the constant 0x10001000?  I'll
> try to look into what's involved in changing to the above next week.

CSE should fold the expression and drop REG_EQUAL note containing the constant
on the second instruction. Most of passes (with an notable exception of
combiner) are aware of these notes and can use them to get the constant back.

> 
> I think what has confused the issue is that the HP assembler knows how
> to extract the high and low parts.  However, as you note, there are
> benefits to creating the high and low parts directly in the compiler.

Honza
> 
> Dave
> -- 
> J. David Anglin                                  dave.anglin@nrc.ca
> National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Richard Henderson]

On Sat, Sep 08, 2001 at 03:50:32PM -0400, John David Anglin wrote:
> I see what you saying.  Is jump expansion smart enough to figure out
> that the final result for the above is the constant 0x10001000?

Yes.

> I think what has confused the issue is that the HP assembler knows how
> to extract the high and low parts.

So does the Alpha and Sparc assemblers, actually.  ;-)  We just don't
use that feature.


r~

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Bernd Schmidt]

On Fri, 7 Sep 2001, Richard Henderson wrote:

> On Fri, Sep 07, 2001 at 07:07:12PM -0400, John David Anglin wrote:
> > (insn/i 24 70 25 (set (reg:SI 99)
> >         (high:SI (const_int 20000 [0x4e20]))) -1 (nil)
> >     (nil))
> >
> > (insn/i 25 24 26 (set (reg:SI 100)
> > 	(lo_sum:SI (reg:SI 99)
> > 	    (const_int 20000 [0x4e20]))) -1 (nil)
> >     (nil))
>
> Why are you using high/lo_sum for constants?  high/lo_sum has
> rather loose semantics, and you can't pull much information
> from them.
>
> Better would be to emit the actual constants that the insns
> in question will load into the hardware registers.

Can we assume that an expression of the form (lo_sum (reg) (constant))
always has the same value as the constant itself?  That could possibly
help CSE.


Bernd

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[John David Anglin]

> > Why are you using high/lo_sum for constants?  high/lo_sum has
> > rather loose semantics, and you can't pull much information
> > from them.
> >
> > Better would be to emit the actual constants that the insns
> > in question will load into the hardware registers.
> 
> Can we assume that an expression of the form (lo_sum (reg) (constant))
> always has the same value as the constant itself?  That could possibly
> help CSE.

I am fairly certain that it is true on the PA.  In fact, I think more
generally the form (lo_sum (reg) (rtx)) is always equivalent to (rtx).
(reg) is always (high (rtx)).  If this is not true on all ports, possibly
a flag bit (unchanging?) could be set in the LO_SUM to indicate this.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[law]

  In message < 200109081718.f88HIpZ0020468@hiauly1.hia.nrc.ca >you write:
  > I am fairly certain that it is true on the PA.  In fact, I think more
  > generally the form (lo_sum (reg) (rtx)) is always equivalent to (rtx).
  > (reg) is always (high (rtx)).  If this is not true on all ports, possibly
  > a flag bit (unchanging?) could be set in the LO_SUM to indicate this.
Yes, this is true for compile time constants on the PA.  It is not true for
symbolic references.  We can (and do) take advantage of the overlap in
bits set by HIGH and LO_SUM on the PA for symbolic addresses.  This allows
a series of different LO_SUM expressions to share a single HIGH expression.

We could do the same for compile-time constants, but don't.


This is mostly historical -- the PA port is modeled after the SPARC port;
the SPARC used HIGH/LO_SUM for constants, so the PA does the same thing.


We could just as easily emit

(set (reg1) (const_int HHHHHHH)
(set (reg2) (plus (reg1) (const_int LLLLLL)))

Where HHHHH are the high bits and LLLLL are the low bits.  This might be
easier for the optimizers to grok.


Or, we could just emit 

(set (reg) (const_int XXXXXXXX))

And keep it in that form until a later point in the compilation process.

jeff

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Richard Henderson]

On Mon, Sep 10, 2001 at 10:23:01AM -0600, law@redhat.com wrote:
> Or, we could just emit 
> 
> (set (reg) (const_int XXXXXXXX))
> 
> And keep it in that form until a later point in the compilation process.

The thing I like about exposing the split early is that
gcse gets to move these expressions around.  If you expose
the split later, nothing is going to move the parts around
as aggressively.


r~

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[David Edelsohn]

>>>>> Richard Henderson writes:

Richard> The thing I like about exposing the split early is that
Richard> gcse gets to move these expressions around.  If you expose
Richard> the split later, nothing is going to move the parts around
Richard> as aggressively.

	However, splitting the constant early inhibits other optimizations
in GCC which do not see the entire constant.  Additionally, other parts of
GCC do not try to synthesize the larger constants internally if patterns
don't accept the full constant range.

David

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Daniel Berlin]

On Mon, 10 Sep 2001, Richard Henderson wrote:

> On Mon, Sep 10, 2001 at 10:23:01AM -0600, law@redhat.com wrote:
> > Or, we could just emit
> >
> > (set (reg) (const_int XXXXXXXX))
> >
> > And keep it in that form until a later point in the compilation process.
>
> The thing I like about exposing the split early is that
> gcse gets to move these expressions around.  If you expose
> the split later, nothing is going to move the parts around
> as aggressively.

It's only going to move them around if they were redundant anyway, and in
all likelyhood, they'll still be redundant in the form (set (reg)
(const_int)).  However, splitting them can also introduce more regions
that prevent code motion, since there can be more instructions we can't
move above.
We'd be better off integrating the ability to move these parts/eliminate
pieces,  around into  the scheduler (since it has all the dependencies
needed), than we would trying to figure out where it's profitable to do
the various techniques to allow us to do code motion where we couldn't
before (since it requires control flow restructuring, etc).

 >
>
> r~
>

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[law]

  In message < 20010910095948.A8881@redhat.com >you write:
  > The thing I like about exposing the split early is that
  > gcse gets to move these expressions around.  If you expose
  > the split later, nothing is going to move the parts around
  > as aggressively.
True.  But with the way things are currently implemented I don't think
we actually lose anything on the PA by not exposing the subexpressions
to gcse.  Instead of commonizing the HIGH and LO_SUM parts with other
idential ones elsewhere, we end up commonizing (set (reg) (const_int))


jeff

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Richard Henderson]

On Mon, Sep 10, 2001 at 11:29:56AM -0600, law@redhat.com wrote:
> True.  But with the way things are currently implemented I don't think
> we actually lose anything on the PA by not exposing the subexpressions
> to gcse.  Instead of commonizing the HIGH and LO_SUM parts with other
> idential ones elsewhere, we end up commonizing (set (reg) (const_int))

Consider

	(set (reg A) (const_int 0x10001))
	(set (reg B) (const_int 0x10002))

as

	(set (reg T) (const_int 0x10000))
	(set (reg A) (plus (reg T) (const_int 1)))
	(set (reg B) (plus (reg T) (const_int 2)))

Now consider A and B loaded on two different paths.  Code motion can
then pull T up into the dominator.


r~

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Daniel Berlin]

Richard Henderson <rth@redhat.com> writes:

SW> On Mon, Sep 10, 2001 at 11:29:56AM -0600, law@redhat.com wrote:
> > True.  But with the way things are currently implemented I don't think
>> we actually lose anything on the PA by not exposing the subexpressions
>> to gcse.  Instead of commonizing the HIGH and LO_SUM parts with other
>> idential ones elsewhere, we end up commonizing (set (reg) (const_int))
>
> Consider
>
> 	(set (reg A) (const_int 0x10001))
> 	(set (reg B) (const_int 0x10002))

>
> as
>
> 	(set (reg T) (const_int 0x10000))
> 	(set (reg A) (plus (reg T) (const_int 1)))
> 	(set (reg B) (plus (reg T) (const_int 2)))
>
> Now consider A and B loaded on two different paths.  Code motion can
> then pull T up into the dominator.
And thus, increase register pressure.
Without rematerialization,  or live range splitting, we'd spill twice
as much as we would before here.
But this won't *really* happen, because we'd split it before register
allocation.
And since we CSE the hard regs after register allocation, it might be
gone.
And if that doesn't do it, we could change the current  scheduling
into something like dominator path scheduling could move that
without any copies.
--Dan

>
>
> r~

-- 
"When I have a kid, I want to buy one of those strollers for
twins.  Then put the kid in and run around, looking frantic.
When he gets older, I'd tell him he used to have a brother, but
he didn't obey.
"-Steven Wright

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Richard Henderson]

On Mon, Sep 10, 2001 at 02:09:00PM -0400, Daniel Berlin wrote:
> Without rematerialization,  or live range splitting, we'd spill twice
> as much as we would before here.

But reload _does_ do simple rematerialization.  See reg_equiv_constant.



r~

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Daniel Berlin]

Richard Henderson <rth@redhat.com> writes:

> On Mon, Sep 10, 2001 at 02:09:00PM -0400, Daniel Berlin wrote:
> > Without rematerialization,  or live range splitting, we'd spill twice
>> as much as we would before here.
>
> But reload _does_ do simple rematerialization.  See
> reg_equiv_constant.
Right, but it's very *simple* rematerialization.
I had some numbers somewhere that said we do so much better with
advanced remat it's not even funny, but i don't recall them exactly,
so i don't want to quote them.


>
>
>
> r~

-- 
"There's a fine line between fishing and standing on the shore
looking like an idiot.
"-Steven Wright

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[law]

  In message < 20010910104403.E8881@redhat.com >you write:
  > On Mon, Sep 10, 2001 at 11:29:56AM -0600, law@redhat.com wrote:
  > > True.  But with the way things are currently implemented I don't think
  > > we actually lose anything on the PA by not exposing the subexpressions
  > > to gcse.  Instead of commonizing the HIGH and LO_SUM parts with other
  > > idential ones elsewhere, we end up commonizing (set (reg) (const_int))
  > 
  > Consider
  > 
  > 	(set (reg A) (const_int 0x10001))
  > 	(set (reg B) (const_int 0x10002))
  > 
  > as
  > 
  > 	(set (reg T) (const_int 0x10000))
  > 	(set (reg A) (plus (reg T) (const_int 1)))
  > 	(set (reg B) (plus (reg T) (const_int 2)))
  > 
  > Now consider A and B loaded on two different paths.  Code motion can
  > then pull T up into the dominator.
But recall that we don't do this right now on the PA due to implementation
issues.

jeff

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[John David Anglin]

>   > 	(set (reg T) (const_int 0x10000))
>   > 	(set (reg A) (plus (reg T) (const_int 1)))
>   > 	(set (reg B) (plus (reg T) (const_int 2)))
>   > 
>   > Now consider A and B loaded on two different paths.  Code motion can
>   > then pull T up into the dominator.
> But recall that we don't do this right now on the PA due to implementation
> issues.

I was planning on trying to implement this later this week.  At the moment,
I am pounding nails helping with a new house for my sister.

It is clear that either the above, or just

(set (reg A) (const_int)) 

is better than the current high/lo_sum.  However, I don't see a consensis
from the discussion as to which approach is better.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[law]

  In message < 200109110311.f8B3BrYm014073@hiauly1.hia.nrc.ca >you write:
  > >   > 	(set (reg T) (const_int 0x10000))
  > >   > 	(set (reg A) (plus (reg T) (const_int 1)))
  > >   > 	(set (reg B) (plus (reg T) (const_int 2)))
  > >   > 
  > >   > Now consider A and B loaded on two different paths.  Code motion can
  > >   > then pull T up into the dominator.
  > > But recall that we don't do this right now on the PA due to implementatio
  > n
  > > issues.
  > 
  > I was planning on trying to implement this later this week.  At the moment,
  > I am pounding nails helping with a new house for my sister.
Sounds like fun :-)   I've spent most of my spare time over the last few
months renovating our old house.  Richard -- you probably wouldn't recognize
the old house anymore :-)

Anyway....

  > It is clear that either the above, or just
  > 
  > (set (reg A) (const_int)) 
  > 
  > is better than the current high/lo_sum.  However, I don't see a consensis
  > from the discussion as to which approach is better.
I'm not sure either.

(set (reg a) (const_int ))	/* High part */
(set (reg b) (plus (reg a) (const_int))  /* Low part */

Has the advantage of being able to share the high part across multiple
constant loads, much like we do for symbolic references with offsets.

The only downside I see offhand is CSE knows high/lo_sum is somewhat special,
but I would expect it to be able to grok the above sequence just as well to
determine the constant value for (reg b).

jeff

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[John David Anglin]

> (set (reg a) (const_int ))	/* High part */
> (set (reg b) (plus (reg a) (const_int))  /* Low part */
> 
> Has the advantage of being able to share the high part across multiple
> constant loads, much like we do for symbolic references with offsets.
> 
> The only downside I see offhand is CSE knows high/lo_sum is somewhat special,
> but I would expect it to be able to grok the above sequence just as well to
> determine the constant value for (reg b).

A crack at partially implementing the above approach is here:
< http://gcc.gnu.org/ml/gcc-patches/2001-09/msg00906.html >.  Most of
the infrastructure to implement it was already in place.

It fixes the fail of 20000731-1.c at -O1.  The one clear advantage to
this approach that I can see is that constants expressed in the above
form are recognized during jump expansion.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[law]

  In message < 200109241702.f8OH2K3T028166@hiauly1.hia.nrc.ca >you write:
  > It fixes the fail of 20000731-1.c at -O1.  The one clear advantage to
  > this approach that I can see is that constants expressed in the above
  > form are recognized during jump expansion.
Yes.  

Another approach is to allow all constants in compare/branch insns initially,
then use define_splits and friends to lower to the actual capabilities of
the chip later.

jeff

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[John David Anglin]

> Another approach is to allow all constants in compare/branch insns initially,
> then use define_splits and friends to lower to the actual capabilities of
> the chip later.

Ths could be the best approach but my first impression was that it
was likely more work to implement.

Dave
-- 
J. David Anglin                                  dave.anglin@nrc.ca
National Research Council of Canada              (613) 990-0752 (FAX: 952-6605)

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[law]

  In message < 200109241719.f8OHJdj1028320@hiauly1.hia.nrc.ca >you write:
  > > Another approach is to allow all constants in compare/branch insns initia
  > lly,
  > > then use define_splits and friends to lower to the actual capabilities of
  > > the chip later.
  > 
  > Ths could be the best approach but my first impression was that it
  > was likely more work to implement.
I could probably send you the stuff I was playing with (assuming that I can
still find it :-)

jeff

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Richard Henderson]

On Sat, Sep 08, 2001 at 10:27:54AM +0100, Bernd Schmidt wrote:
> Can we assume that an expression of the form (lo_sum (reg) (constant))
> always has the same value as the constant itself?  That could possibly
> help CSE.

Probably.


r~

Re: Why can't CSE recognize const_int's in HIGH LO_SUM pair?

[Richard Kenner]

    If you ask Alpha to load 0x10001000, you'll get

	(set (reg) (const_int 0x10000000))
	(set (reg) (plus (reg) (const_int 0x1000))

    which is exactly what the machine code is doing.  No need for
    high/lo_sum, and by not using them, we expose the exact constant
    fragments to cse/combine/etc.

That's true for integers, but not symbolic constants.