Possible CSE quirk involving SUBREG on the i386

Possible CSE quirk involving SUBREG on the i386

[John Wehle]

Compiling:

  unsigned short c;

  int
  func(unsigned short a)
    {
    unsigned short b;
 
    b = a;
    c = b;

    return b;
    }

for the i386 using egcs current with -O -S yields:

_func:
	pushl %ebp
	movl %esp,%ebp
	movl 8(%ebp),%eax
	movl %eax,%edx
	movw %ax,_c
	movzwl %dx,%eax
	leave
	ret

Which is interesting since I expected:

_func:
	pushl %ebp
	movl %esp,%ebp
	movl 8(%ebp),%eax
	movw %ax,_c
	movzwl %ax,%eax
	leave
	ret

The use of %edx seems wasteful.

-- John
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  In message < 199806300534.BAA27602@jwlab.FEITH.COM >you write:
  > Compiling:
  > 
  >   unsigned short c;
  > 
  >   int
  >   func(unsigned short a)
  >     {
  >     unsigned short b;
  >  
  >     b = a;
  >     c = b;
  > 
  >     return b;
  >     }
  > 
  > for the i386 using egcs current with -O -S yields:
  > 
  > _func:
  > 	pushl %ebp
  > 	movl %esp,%ebp
  > 	movl 8(%ebp),%eax
  > 	movl %eax,%edx
  > 	movw %ax,_c
  > 	movzwl %dx,%eax
  > 	leave
  > 	ret
  > 
  > Which is interesting since I expected:
  > 
  > _func:
  > 	pushl %ebp
  > 	movl %esp,%ebp
  > 	movl 8(%ebp),%eax
  > 	movw %ax,_c
  > 	movzwl %ax,%eax
  > 	leave
  > 	ret
I'm not sure this is really a CSE issue.  Though it might be a combine
issue.

;; Start of basic block 0, registers live: 6 [bp] 16 []
(insn 4 2 6 (set (reg:SI 22)
        (mem:SI (reg:SI 16 %argp))) 54 {movsi+2} (nil)
    (expr_list:REG_EQUIV (mem:SI (reg:SI 16 %argp))
        (nil)))
        
(insn 6 4 7 (set (reg/v:HI 21)
        (subreg:HI (reg:SI 22) 0)) 58 {movhi+1} (insn_list 4 (nil))
    (nil))

(note 7 6 8 "" NOTE_INSN_FUNCTION_BEG)

(note 8 7 10 "" NOTE_INSN_DELETED)

(note 10 8 16 0 NOTE_INSN_BLOCK_BEG)

(insn 16 10 18 (set (mem:HI (symbol_ref:SI ("c")))
        (subreg:HI (reg:SI 22) 0)) 58 {movhi+1} (nil)
    (expr_list:REG_DEAD (reg:SI 22)
        (nil)))

(insn 18 16 20 (set (reg:SI 24)
        (zero_extend:SI (reg/v:HI 21))) 86 {zero_extendhisi2} (insn_list 6 (nil))
    (expr_list:REG_DEAD (reg/v:HI 21)
        (nil)))

If we were to combine insns 6 & 18 I think we'd get the code you want.

I don't know why combine isn't doing this.

jeff

Re: Possible CSE quirk involving SUBREG on the i386

[Richard Henderson]

On Tue, Jun 30, 1998 at 01:12:33AM -0600, Jeffrey A Law wrote:
> I'm not sure this is really a CSE issue.  Though it might be a combine
> issue.

I concurr.  DaveM was reporting to me similar lossage in the Sparc
port with SImode subregs of DImode values with an example like

	void bar(ull x);
	void foo(ull x) { bar(x); }

I may have a look at it this evening.


r~

Re: Possible CSE quirk involving SUBREG on the i386

[David S. Miller]

   Date: Tue, 30 Jun 1998 15:15:14 -0700
   From: Richard Henderson <rth@dot.cygnus.com>

   On Tue, Jun 30, 1998 at 01:12:33AM -0600, Jeffrey A Law wrote:
   > I'm not sure this is really a CSE issue.  Though it might be a combine
   > issue.

   I concurr.  DaveM was reporting to me similar lossage in the Sparc
   port with SImode subregs of DImode values with an example like

	   void bar(ull x);
	   void foo(ull x) { bar(x); }

   I may have a look at it this evening.

Right, my current theory is that combine likes to look at things "3 at
a time" to determine candidates.  For some of the cases I was trying
to get to work, it would need to look at things "4 at a time".

Later,
David S. Miller
davem@dm.cobaltmicro.com

Re: Possible CSE quirk involving SUBREG on the i386

[Richard Henderson]

On Tue, Jun 30, 1998 at 08:18:19PM -0700, David S. Miller wrote:
> Right, my current theory is that combine likes to look at things "3 at
> a time" to determine candidates.  For some of the cases I was trying
> to get to work, it would need to look at things "4 at a time".

Well, thats what I thought too, except if it had properly been
looking at the subregs, 2 at a time might have been enough.


r~

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  In message < 199807010318.UAA26631@dm.cobaltmicro.com >you write:
  > Right, my current theory is that combine likes to look at things "3 at
  > a time" to determine candidates.  For some of the cases I was trying
  > to get to work, it would need to look at things "4 at a time".
Yup.  Combine looks at insns in groups of 2 or 3.

You can make it look at larger groups by making intermediate patterns.

Here's an example from the H8 port:

;; This is a "bridge" instruction.  Combine can't cram enough insns
;; together to crate a MAC instruction directly, but it can create
;; this instruction, which then allows combine to create the real
;; MAC insn.
;;
;; Unfortunately, if combine doesn't create a MAC instruction, this
;; insn must generate reasonably correct code.  Egad.
(define_insn ""
  [(set (match_operand:SI 0 "register_operand" "=a")
        (mult:SI
          (sign_extend:SI
            (mem:HI (post_inc:SI (match_operand:SI 1 "register_operand" "r"))))
          (sign_extend:SI
            (mem:HI (post_inc:SI (match_operand:SI 2 "register_operand" "r")))))
)]
  "TARGET_H8300S"
  "clrmac\;mac  %2,%1"
  [(set_attr "length" "6")
   (set_attr "cc" "none_0hit")])

(define_insn ""
  [(set (match_operand:SI 0 "register_operand" "=a")
        (plus (mult:SI
          (sign_extend:SI (mem:HI
            (post_inc:SI (match_operand:SI 1 "register_operand" "r"))))
          (sign_extend:SI (mem:HI
            (post_inc:SI (match_operand:SI 2 "register_operand" "r")))))
              (match_operand:SI 3 "register_operand" "0")))]
  "TARGET_H8300S"
  "mac  %2,%1"

Re: Possible CSE quirk involving SUBREG on the i386

[David S. Miller]

   Date: Tue, 30 Jun 1998 22:00:09 -0600
   From: Jeffrey A Law <law@hurl.cygnus.com>

   Yup.  Combine looks at insns in groups of 2 or 3.

   You can make it look at larger groups by making intermediate patterns.

   Here's an example from the H8 port:

Ok, that would work, neat trick :-)

However, it is really a workaround for the core problem.
But, I'm concerned that increasing the number of patterns combine
looks at in one go will increase compile time considerably.

The next question arises as to what a good number would be, perhaps
the code in combine can be made generic enough that a target header
define can tell it the max number of patterns to ever try to coalesce
at once?

Later,
David S. Miller
davem@dm.cobaltmicro.com

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  In message < 199807010559.WAA27729@dm.cobaltmicro.com >you write:
  > However, it is really a workaround for the core problem.
Yes.  But the core problem (IMHO) is rather difficult to solve.

  > But, I'm concerned that increasing the number of patterns combine
  > looks at in one go will increase compile time considerably.
I haven't seen this behavior yet, though I'm not adding lots of these
patterns :-)  The H8 port has one "bridge" pattern.  I think the
mn102 port has 2 or 3.

  > The next question arises as to what a good number would be, perhaps
  > the code in combine can be made generic enough that a target header
  > define can tell it the max number of patterns to ever try to coalesce
  > at once?
I'd be suprised if we could make combine do 4->3 without a lot of
work -- which then begs the question are the benefits enough to
justify the work considering the other things we could be working
on?

jeff

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  In message <199806300534.BAA27602@jwlab.FEITH.COM>you write:
  > Compiling:
  > 
  >   unsigned short c;
  > 
  >   int
  >   func(unsigned short a)
  >     {
  >     unsigned short b;
  >  
  >     b = a;
  >     c = b;
  > 
  >     return b;
  >     }
  > 
  > for the i386 using egcs current with -O -S yields:
  > 
  > _func:
  > 	pushl %ebp
  > 	movl %esp,%ebp
  > 	movl 8(%ebp),%eax
  > 	movl %eax,%edx
  > 	movw %ax,_c
  > 	movzwl %dx,%eax
  > 	leave
  > 	ret
  > 
  > Which is interesting since I expected:
  > 
  > _func:
  > 	pushl %ebp
  > 	movl %esp,%ebp
  > 	movl 8(%ebp),%eax
  > 	movw %ax,_c
  > 	movzwl %ax,%eax
  > 	leave
  > 	ret
  > 
  > The use of %edx seems wasteful.
Yes.  Wasteful.  Compiling this with the current sources yields:

func:
        pushl %ebp      # 32    movsi-2
        movl %esp,%ebp  # 34    movsi+2/1
        movzwl 8(%ebp),%eax     # 4     zero_extendhisi2+2/2
        movw %ax,c      # 16    movhi+1/1
        leave   # 37    leave
        ret     # 38    return_internal

Which is even better than what you expected ;-)

jeff

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  In message <199806300534.BAA27602@jwlab.FEITH.COM>you write:
  > Compiling:
  > 
  >   unsigned short c;
  > 
  >   int
  >   func(unsigned short a)
  >     {
  >     unsigned short b;
  >  
  >     b = a;
  >     c = b;
  > 
  >     return b;
  >     }
  > 
  > for the i386 using egcs current with -O -S yields:
  > 
  > _func:
  > 	pushl %ebp
  > 	movl %esp,%ebp
  > 	movl 8(%ebp),%eax
  > 	movl %eax,%edx
  > 	movw %ax,_c
  > 	movzwl %dx,%eax
  > 	leave
  > 	ret
  > 
  > Which is interesting since I expected:
  > 
  > _func:
  > 	pushl %ebp
  > 	movl %esp,%ebp
  > 	movl 8(%ebp),%eax
  > 	movw %ax,_c
  > 	movzwl %ax,%eax
  > 	leave
  > 	ret
  > 
  > The use of %edx seems wasteful.
Yes.  Wasteful.  Compiling this with the current sources yields:

func:
        pushl %ebp      # 32    movsi-2
        movl %esp,%ebp  # 34    movsi+2/1
        movzwl 8(%ebp),%eax     # 4     zero_extendhisi2+2/2
        movw %ax,c      # 16    movhi+1/1
        leave   # 37    leave
        ret     # 38    return_internal

Which is even better than what you expected ;-)

jeff

Re: Possible CSE quirk involving SUBREG on the i386

[John Wehle]

> I'm not sure this is really a CSE issue.  Though it might be a combine
> issue.

The reason that I mention CSE is prior to it we have:

(insn 6 4 7 (set (reg/v:HI 21)
        (subreg:HI (reg:SI 22) 0)) -1 (nil)
    (nil))

(insn 13 10 16 (set (reg/v:HI 23)
        (reg/v:HI 21)) -1 (nil)
    (nil))

(insn 16 13 18 (set (mem:HI (symbol_ref:SI ("c")))
        (reg/v:HI 23)) -1 (nil)
    (nil))

(insn 18 16 20 (set (reg:SI 24)
        (zero_extend:SI (reg/v:HI 23))) -1 (nil)
    (nil))

and after it we have:

(insn 6 4 7 (set (reg/v:HI 21)
        (subreg:HI (reg:SI 22) 0)) 57 {movhi+1} (nil)
    (nil))

(insn 16 10 18 (set (mem:HI (symbol_ref:SI ("c")))
        (subreg:HI (reg:SI 22) 0)) 57 {movhi+1} (nil)
    (nil))

(insn 18 16 20 (set (reg:SI 24)
        (zero_extend:SI (reg/v:HI 21))) 85 {zero_extendhisi2} (nil)
    (nil))

It appears that CSE changed (reg/v:HI 23) in insn 16 to
(subreg:HI (reg:SI 22) 0) yet it did not perform this
same substitution in insn 18.  I would have expected
the same substitution in both places.

-- John
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  > It appears that CSE changed (reg/v:HI 23) in insn 16 to
  > (subreg:HI (reg:SI 22) 0) yet it did not perform this
  > same substitution in insn 18.  I would have expected
  > the same substitution in both places.
In that case, you might see if it was rejected because the perceived
cost wasn't worth the benefit.  It may also be the case that the
zero_extendhisi pattern won't accept a subreg.  I haven't looked.

jeff

Re: Possible CSE quirk involving SUBREG on the i386

[Richard Henderson]

On Tue, Jun 30, 1998 at 03:04:46PM -0600, Jeffrey A Law wrote:
>   > It appears that CSE changed (reg/v:HI 23) in insn 16 to
>   > (subreg:HI (reg:SI 22) 0) yet it did not perform this
>   > same substitution in insn 18.  I would have expected
>   > the same substitution in both places.
> In that case, you might see if it was rejected because the perceived
> cost wasn't worth the benefit.  It may also be the case that the
> zero_extendhisi pattern won't accept a subreg.  I haven't looked.

Ho hum.  The explanation is simple here -- MODES_TIEABLE_P.

I believe that we can do slightly better for this; while only
the first four int regs can hold QImode values, all of them 
can hold HImode values.

This happens to cure this exact problem, but the same problem
will occur with unsigned char, and I don't see that we can do
anything about it.


r~


	* i386.h (HARD_REGNO_MODE_OK): Kill spurrious test.
	(MODES_TIEABLE_P): Tie SImode and HImode.

Index: config/i386/i386.h
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/config/i386/i386.h,v
retrieving revision 1.25
diff -c -p -d -r1.25 i386.h
*** i386.h	1998/06/20 00:04:17	1.25
--- i386.h	1998/07/01 10:28:31
*************** extern int ix86_arch;
*** 639,646 ****
     for cross-compiler testing.  */
  
  #define HARD_REGNO_MODE_OK(REGNO, MODE) \
!   ((REGNO) < 2 ? 1						\
!    : (REGNO) < 4 ? 1						\
     : FP_REGNO_P (REGNO)						\
     ? (((int) GET_MODE_CLASS (MODE) == (int) MODE_FLOAT		\
         || (int) GET_MODE_CLASS (MODE) == (int) MODE_COMPLEX_FLOAT)	\
--- 639,645 ----
     for cross-compiler testing.  */
  
  #define HARD_REGNO_MODE_OK(REGNO, MODE) \
!   ((REGNO) < 4 ? 1						\
     : FP_REGNO_P (REGNO)						\
     ? (((int) GET_MODE_CLASS (MODE) == (int) MODE_FLOAT		\
         || (int) GET_MODE_CLASS (MODE) == (int) MODE_COMPLEX_FLOAT)	\
*************** extern int ix86_arch;
*** 653,659 ****
     If HARD_REGNO_MODE_OK could produce different values for MODE1 and MODE2,
     for any hard reg, then this must be 0 for correct output.  */
  
! #define MODES_TIEABLE_P(MODE1, MODE2) ((MODE1) == (MODE2))
  
  /* Specify the registers used for certain standard purposes.
     The values of these macros are register numbers.  */
--- 652,661 ----
     If HARD_REGNO_MODE_OK could produce different values for MODE1 and MODE2,
     for any hard reg, then this must be 0 for correct output.  */
  
! #define MODES_TIEABLE_P(MODE1, MODE2)				\
!   ((MODE1) == (MODE2)						\
!    || ((MODE1) == SImode && (MODE2) == HImode			\
!        || (MODE1) == HImode && (MODE2) == SImode))
  
  /* Specify the registers used for certain standard purposes.
     The values of these macros are register numbers.  */

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  In message < 19980701033305.A23054@dot.cygnus.com >you write:
  > Ho hum.  The explanation is simple here -- MODES_TIEABLE_P.
  > 
  > I believe that we can do slightly better for this; while only
  > the first four int regs can hold QImode values, all of them 
  > can hold HImode values.
  > 
  > This happens to cure this exact problem, but the same problem
  > will occur with unsigned char, and I don't see that we can do
  > anything about it.
  > 
  > 
  > r~
  > 
  > 
  > 	* i386.h (HARD_REGNO_MODE_OK): Kill spurrious test.
  > 	(MODES_TIEABLE_P): Tie SImode and HImode.
Patch seems reasonble.  I think you should install it.

I think we're still trying to decide if we can relax MODES_TIEABLE_P's
need to be symmetric. :-)  That might help the char problem in some
cases.

jeff

Re: Possible CSE quirk involving SUBREG on the i386

[John Wehle]

> Ho hum.  The explanation is simple here -- MODES_TIEABLE_P.
> 
> I believe that we can do slightly better for this; while only
> the first four int regs can hold QImode values, all of them 
> can hold HImode values.
> 
> This happens to cure this exact problem, but the same problem
> will occur with unsigned char, and I don't see that we can do
> anything about it.

Why is there a requirement that MODES_TIEABLE_P be symmetrical?
On the i386 a QI mode register is accessible in SI mode so I
would think that adding:

  ((MODE1) == QImode && (MODE2) == SImode)

to MODES_TIEABLE_P would be useful.  BTW, this change solves
the unsigned char problem and survives a bootstrap.  I realize
that we need to avoid trying to use %esi and %edi in a situation
which requires QImode access ... though this seems like a register
allocation issue which could be handled separate from CSE and
COMBINE.  What are the thoughts on refining the definition of
MODES_TIEABLE_P so that it can be asymmetric and change:

  MODES_TIEABLE_P (X, Y)

to:

  MODES_TIEABLE_P (X, Y) && MODES_TIEABLE_P (Y, X)

where necessary to prevent the wrong kind of register from
being allocated?

I known ... things aren't that simple :-) though I welcome
being enlightened as to the complexities.

-- John
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------

Re: Possible CSE quirk involving SUBREG on the i386

[Richard Henderson]

On Wed, Jul 01, 1998 at 02:43:24PM -0400, John Wehle wrote:
> Why is there a requirement that MODES_TIEABLE_P be symmetrical?

Hmm.  You are right that the description of the macro would 
support an asymmetrical definition.  Someone more knowledgable
about how local works should comment on whether this is in fact
the case, or if the documentation should be reworded.


r~

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  In message < 199807011843.OAA02049@jwlab.FEITH.COM >you write:
  > Why is there a requirement that MODES_TIEABLE_P be symmetrical?
I believe it is related to HARD_REGNO_MODE_OK.  See MODES_TIEABLE_P
in the manual.

Basically local-alloc will try to tie two registers together if
MODES_TIEABLE_P is nonzero for two pseudos.

If we tie the pseudos together, they will be allocated into the
same hard reg -- and if HARD_REGNO_MODE_OK was nonzero for one
of them, then we lose.

jeff

Re: Possible CSE quirk involving SUBREG on the i386

[John Wehle]

>   > Why is there a requirement that MODES_TIEABLE_P be symmetrical?
> I believe it is related to HARD_REGNO_MODE_OK.  See MODES_TIEABLE_P
> in the manual.

I did. :-)

> Basically local-alloc will try to tie two registers together if
> MODES_TIEABLE_P is nonzero for two pseudos.

I noticed that. :-)

> If we tie the pseudos together, they will be allocated into the
> same hard reg -- and if HARD_REGNO_MODE_OK was nonzero for one
> of them, then we lose.

Right, which is why I'm proposing that combine_regs in local-alloc.c
be changed from using:

  || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg))

to:

  || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg))
  || !MODES_TIEABLE_P (GET_MODE (setreg), GET_MODE (usedreg))

and then update the manual to allow MODES_TIEABLE_P to be asymmetric.
This allows combine to handle zero extending a QImode register in an
optimal fashion on the i386.  Any reason I shouldn't go ahead and submit
a patch for this?

-- John
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------

Re: Possible CSE quirk involving SUBREG on the i386

[Jeffrey A Law]

  In message < 199807020417.AAA03219@jwlab.FEITH.COM >you write:
  > > Basically local-alloc will try to tie two registers together if
  > > MODES_TIEABLE_P is nonzero for two pseudos.
  > 
  > I noticed that. :-)
The other issue is reload; though it looks like the reload case is
handled by LIMIT_RELOAD_CLASS these days.

Based on the comments in combine.c, I think at one time MODES_TIEABLE_P
did have to be symmetric because of the reload issue.  I'm starting to
think we can relax this now.

The last issue is register allocation -- I get the impression from reading
the code in cse, combine & regclass that this change may make register 
allocation worse in some cases.  So we need to have some guess about the
benefit vs the cost.

I propose we table this until after egcs-1.1.  Or better yet, instead of
tabling it, we just install your patch in the mainline sources after egcs-1.1
branches.

That gives us plenty of time to study what actually happens instead of
doing something rather risky at this stage.

jeff

Re: Possible CSE quirk involving SUBREG on the i386

[John Wehle]

> Based on the comments in combine.c, I think at one time MODES_TIEABLE_P
> did have to be symmetric because of the reload issue.  I'm starting to
> think we can relax this now.
> 
> The last issue is register allocation -- I get the impression from reading
> the code in cse, combine & regclass that this change may make register 
> allocation worse in some cases.  So we need to have some guess about the
> benefit vs the cost.

Yep, I got the same impression though sometimes it's hard to guess without
trying it.

> I propose we table this until after egcs-1.1.  Or better yet, instead of
> tabling it, we just install your patch in the mainline sources after egcs-1.1
> branches.

Okay, I'll see about throwing together a patch.

> That gives us plenty of time to study what actually happens instead of
> doing something rather risky at this stage.

Sounds reasonable to me.

-- John
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------