[PATCH] Minor loop optimizer enhancement

[Ulrich Weigand <weigand at i1 dot informatik dot uni-erlangen dot de>]

Hello,

we have a test case where the loop optimizer does not move the
following insn sequence (that computes inode*40) outside of a
loop, even though inode is loop-invariant:

(insn 2561 2559 2562 (set (reg:DI 1483)
        (ashift:DI (reg:DI 2442 [ inode ])
            (const_int 2 [0x2]))) -1 (nil)
    (expr_list:REG_EQUAL (ashift:DI (reg:DI 2442 [ inode ])
            (const_int 2 [0x2]))
        (nil)))

(insn 2562 2561 2563 (parallel [
            (set (reg:DI 1484)
                (plus:DI (reg:DI 1483)
                    (reg:DI 2442 [ inode ])))
            (clobber (reg:CC 33 %cc))
        ]) -1 (nil)
    (expr_list:REG_EQUAL (mult:DI (reg:DI 2442 [ inode ])
            (const_int 5 [0x5]))
        (nil)))

(insn 2563 2562 2565 (set (reg:DI 1485)
        (ashift:DI (reg:DI 1484)
            (const_int 3 [0x3]))) -1 (nil)
    (expr_list:REG_EQUAL (mult:DI (reg:DI 2442 [ inode ])
            (const_int 40 [0x28]))
        (nil)))

The reason for this is that the optimizer considers moving
insn 2561 as not desirable since it would increase the
life range of regno 1483 from 2 insns to the whole loop.
As result of not moving insn 2561, the other two insns
are considered unsafe to move:

Loop from 2549 to 3002: 170 real insns.
Continue at insn 2994.
Insn 2561: regno 1483 (life 2), savings 2 not desirable
Insn 2562: regno 1484 (life 51), cond forces 2561 not safe
Insn 2563: regno 1485 (life 50), cond forces 2562 not safe

Note that insn 2563, considered by itself, *would* be 
recognized as desirable to move, since the life range of 
1485 is rather large anyhow.

Note also that there is already code (in force_movables)
that recognizes that insn 2563 forces insn 2562, and thus
insn 2562 should inherit the priority attributes of insn
2563 when considering *its* desirability of moving.

The code falls short of passing on the increased priority
of 2562 to 2561, however.  (Actually, at the time 
force_movables determined that 2562 forces 2561, the latter 
insn *did* inherit the priority of the former --- but at 
that time, the priority of 2562 was *also* low since insn 
2563 had not yet been considered.)

The following fix changes force_movables to transitively
increase the priority of all insns forced, which results
in the expected behaviour of the loop optimizer:

Loop from 2549 to 3002: 170 real insns.
Continue at insn 2994.
Insn 2561: regno 1483 (life 52), savings 3  moved to 5377
Insn 2562: regno 1484 (life 51), cond forces 2561 savings 2  moved to 5378
Insn 2563: regno 1485 (life 50), cond forces 2562 savings 1  moved to 5379

Bootstrapped/regtested on s390-ibm-linux and s390x-ibm-linux.
OK for mainline/3.4 ?

Bye,
Ulrich

ChangeLog:

	* loop.c (force_movables): Transitively increase the priorities of
	all insns forces by an insn, not just the first one.


Index: gcc/loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.489
diff -c -p -r1.489 loop.c
*** gcc/loop.c	20 Jan 2004 16:55:56 -0000	1.489
--- gcc/loop.c	21 Jan 2004 21:01:51 -0000
*************** force_movables (struct loop_movables *mo
*** 1469,1480 ****
  	  m = 0;
  
  	/* Increase the priority of the moving the first insn
! 	   since it permits the second to be moved as well.  */
  	if (m != 0)
  	  {
  	    m->forces = m1;
! 	    m1->lifetime += m->lifetime;
! 	    m1->savings += m->savings;
  	  }
        }
  }
--- 1469,1486 ----
  	  m = 0;
  
  	/* Increase the priority of the moving the first insn
! 	   since it permits the second to be moved as well.
! 	   Likewise for insns already forced by the first insn.  */
  	if (m != 0)
  	  {
+ 	    struct movable *m2;
+ 
  	    m->forces = m1;
! 	    for (m2 = m1; m2; m2 = m2->forces)
! 	      {
! 		m2->lifetime += m->lifetime;
! 		m2->savings += m->savings;
! 	      }
  	  }
        }
  }
-- 
  Dr. Ulrich Weigand
  weigand@informatik.uni-erlangen.de