This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] GCSE: Changing PARAM_MAX_GCSE_PASSES to 2.


Hi.

I think changing the max number of gcse passes to be greater than one
may be beneficial.  Consider this little example:

#include <ctype.h>

int test() {
	unsigned char			*ReadPtr;

        while (!isdigit(*ReadPtr))
          ReadPtr++;
 
	while (isdigit(*ReadPtr++))
	  ;
}

mips code for the test program:

0000000000000000 <test>:
   0:   90a40000        lbu     $a0,0($a1)
   4:   3c070000        lui     $a3,0x0
   8:   08000006        j       18 <test+0x18>
   c:   24e60001        addiu   $a2,$a3,1
  10:   24a50001        addiu   $a1,$a1,1
  14:   90a40000        lbu     $a0,0($a1)
  18:   308200ff        andi    $v0,$a0,0xff	***
  1c:   00461021        addu    $v0,$v0,$a2
  20:   90430000        lbu     $v1,0($v0)
  24:   30630004        andi    $v1,$v1,0x4
  28:   1060fff9        beqz    $v1,10 <test+0x10>
  2c:   308200ff        andi    $v0,$a0,0xff	***
  30:   24e40001        addiu   $a0,$a3,1
  34:   00441021        addu    $v0,$v0,$a0
  38:   90430000        lbu     $v1,0($v0)
  3c:   30630004        andi    $v1,$v1,0x4
  40:   10600009        beqz    $v1,68 <test+0x68>
  44:   24a50001        addiu   $a1,$a1,1
  48:   90a40000        lbu     $a0,0($a1)
  4c:   308200ff        andi    $v0,$a0,0xff	***
  50:   24e40001        addiu   $a0,$a3,1
  54:   00441021        addu    $v0,$v0,$a0
  58:   90430000        lbu     $v1,0($v0)
  5c:   30630004        andi    $v1,$v1,0x4
  60:   1460fff9        bnez    $v1,48 <test+0x48>
  64:   24a50001        addiu   $a1,$a1,1
  68:   03e00008        jr      $ra
  6c:   00000000        nop

the instructions marked (***) are redundent and should of been removed
by COMBINE.  There are 8 instruction in the first loop and 8 in the
second loop.

After pre-processing, you get:

int test() {
  unsigned char *ReadPtr; 
  while (!((_ctype+1)[(unsigned)*ReadPtr] & (0x04)))
    ReadPtr++; 
  while (((_ctype+1)[(unsigned)*ReadPtr++] & (0x04)))
    ;
}

insns generated for (unsigned)*ReadPtr: 
(set (reg:QI 210)
        (mem:QI (reg/v/f:SI 182 [ ReadPtr ]) ))
(set (reg:SI 201)
        (zero_extend:SI (reg:QI 210) ))

this extension is preferred for CSE and should be cleaned up by COMBINE 
later on. Hence the 2 seperate instruction intead of just one:
(set (reg:SI 210)                          
        (zero_extend:SI (mem:QI (reg/v/f:SI 182 [ ReadPtr ]) )))
 
after pre in GCSE, the first set is moved out of the second loop, but
doing so, the liveness from the first loop to the second loop is changed
such that set(reg:SI 201) is no longer the last use.  In LIFE, it cannot
set the REG_DEAD note and hence COMBINE cannot clean up the extension.


Before GCSE:
------------
(insn 68 81 69 0 bug.c:22 (set (reg:QI 200)
        (mem:QI (reg/v/f:SI 182 [ ReadPtr ]) [0 (* <anonymous>) S1 A8]))
204 {movqi_internal} (nil)
    (nil))
                                                                                                              
(insn 69 68 70 0 bug.c:22 (set (reg:SI 201)
        (zero_extend:SI (reg:QI 200))) 137 {*mips.md:3554} (nil)
   
(nil))                                                                                                              

...

(jump_insn 76 75 9 0 bug.c:22 (set (pc)
        (if_then_else (ne:SI (reg:SI 207)
                (const_int 0 [0x0]))
            (label_ref 33)
            (pc))) 246 {branch_zero} (nil)
    (expr_list:REG_BR_PRED (concat (const_int 13 [0xd])
            (const_int 3600 [0xe10]))
        (nil)))
 
(code_label 24 9 60 1 4 "" [1 uses])
 
...

(insn 11 80 12 1 bug.c:22 (set (reg/s:QI 184)
        (mem:QI (reg/v/f:SI 182 [ ReadPtr ]) [0 (* <anonymous>) S1 A8]))
204 {movqi_internal} (nil)
    (nil))
 
(insn 12 11 14 1 bug.c:22 (set (reg/s:SI 183)
        (zero_extend:SI (reg/s:QI 184))) 137 {*mips.md:3554} (nil)
    (nil))
 
...
 
(jump_insn 19 18 29 1 bug.c:22 (set (pc)
        (if_then_else (eq:SI (reg/s:SI 190)
                (const_int 0 [0x0]))
            (label_ref 24)
            (pc))) 246 {branch_zero} (nil)
    (nil))
 
...

(code_label 33 46 64 2 5 "" [2 uses])
 
(insn 36 64 37 2 bug.c:24 (set (reg:QI 193)
        (mem:QI (reg/v/f:SI 182 [ ReadPtr ]) [0 (* <anonymous>) S1 A8]))
204 {movqi_internal} (nil)
    (nil))
 
(insn 37 36 38 2 bug.c:24 (set (reg:SI 191)
        (zero_extend:SI (reg:QI 193))) 137 {*mips.md:3554} (nil)
    (nil))
 
...
 
(jump_insn 44 34 49 2 bug.c:24 (set (pc)
        (if_then_else (ne:SI (reg:SI 199)
                (const_int 0 [0x0]))
            (label_ref 33)
            (pc))) 246 {branch_zero} (nil)
    (nil))
 
...


AFTER GCSE:
-----------

(insn 68 81 69 0 bug.c:22 (set (reg:QI 210)
        (mem:QI (reg/v/f:SI 182 [ ReadPtr ]) [0 (* <anonymous>) S1 A8]))
204 {movqi_internal} (nil)
    (nil))
 
(insn 69 68 70 0 bug.c:22 (set (reg:SI 201)
        (zero_extend:SI (reg:QI 210))) 137 {*mips.md:3554} (nil)
    (nil))
 
...

(jump_insn 76 75 93 0 bug.c:22 (set (pc)
        (if_then_else (ne:SI (reg:SI 207)
                (const_int 0 [0x0]))
            (label_ref 33)
            (pc))) 246 {branch_zero} (nil)
    (expr_list:REG_BR_PRED (concat (const_int 13 [0xd])
            (const_int 3600 [0xe10]))
        (nil)))

... 
 
(insn 11 80 12 2 bug.c:22 (set (reg:QI 210)
        (mem:QI (reg/v/f:SI 182 [ ReadPtr ]) [0 (* <anonymous>) S1 A8]))
204 {movqi_internal} (nil)
    (nil))
 
(insn 12 11 15 2 bug.c:22 (set (reg/s:SI 183)
        (zero_extend:SI (reg:QI 210))) 137 {*mips.md:3554} (nil)
    (nil))
 
...

(jump_insn 19 18 29 2 bug.c:22 (set (pc)
        (if_then_else (eq:SI (reg/s:SI 190)
                (const_int 0 [0x0]))
            (label_ref 24)
            (pc))) 246 {branch_zero} (nil)
    (nil))

...
  
(jump_insn 95 94 96 3 (set (pc)
        (label_ref 33)) -1 (nil)
    (nil))

(code_label 98 46 97 4 8 "" [1 uses])
 
(insn 89 97 33 4 (set (reg:QI 210)
        (mem:QI (reg/v/f:SI 182 [ ReadPtr ]) [0 (* <anonymous>) S1 A8]))
204 {movqi_internal} (nil)
    (nil))

...

(code_label 33 89 64 5 5 "" [2 uses])
 
(insn 37 64 39 5 bug.c:24 (set (reg:SI 191)
        (zero_extend:SI (reg:QI 210))) 137 {*mips.md:3554} (nil)
    (nil))
 
...
 
(jump_insn 44 34 49 5 bug.c:24 (set (pc)
        (if_then_else (ne:SI (reg:SI 199)
                (const_int 0 [0x0]))
            (label_ref 98)
            (pc))) 246 {branch_zero} (nil)
    (nil))

...

-------------------------------------------------------------------------------

In above, insn 89 now lives in a seperate block, and edges to code label
33 now sees an use of reg 210 instead.

This problem can be fixed if pre is re-run another time, which will
hoist and copy insn 89 out of the loop (or by changing the
MAX-GCSE-PASSES default to 2).  GCSE will run again only if there were
changes in previous passes.  This then allows COMBINE to do the work and
we have 7 instr in the first loop and 6 in the second:

0000000000000000 <test>:
   0:   90a40000        lbu     $a0,0($a1)
   4:   3c080000        lui     $t0,0x0
   8:   25060001        addiu   $a2,$t0,1
   c:   00861821        addu    $v1,$a0,$a2
  10:   90620000        lbu     $v0,0($v1)
  14:   30420004        andi    $v0,$v0,0x4
  18:   1440000f        bnez    $v0,58 <test+0x58>
  1c:   00c03821        move    $a3,$a2
  20:   24a50001        addiu   $a1,$a1,1
  24:   90a40000        lbu     $a0,0($a1)
  28:   00861821        addu    $v1,$a0,$a2
  2c:   90620000        lbu     $v0,0($v1)
  30:   30420004        andi    $v0,$v0,0x4
  34:   1040fffa        beqz    $v0,20 <test+0x20>
  38:   00000000        nop
  3c:   25070001        addiu   $a3,$t0,1
  40:   00871821        addu    $v1,$a0,$a3
  44:   90620000        lbu     $v0,0($v1)
  48:   30420004        andi    $v0,$v0,0x4
  4c:   10400007        beqz    $v0,6c <test+0x6c>
  50:   24a50001        addiu   $a1,$a1,1
  54:   90a40000        lbu     $a0,0($a1)
  58:   00871821        addu    $v1,$a0,$a3
  5c:   90620000        lbu     $v0,0($v1)
  60:   30420004        andi    $v0,$v0,0x4
  64:   1440fffb        bnez    $v0,54 <test+0x54>
  68:   24a50001        addiu   $a1,$a1,1
  6c:   03e00008        jr      $ra
  70:   00000000        nop


regards
David.


2004-03-12  David Ung  <davidu@mips.com>

	* params.def: Change PARAM_MAX_GCSE_PASSES default to 2.

Index: params.def
===================================================================
RCS file: /n/olympia/cvsroot/gcc/gcc-cvs/gcc/gcc/params.def,v
retrieving revision 1.33.4.1.3400.1
diff -c -3 -p -r1.33.4.1.3400.1 params.def
*** params.def  24 Feb 2004 18:35:54 -0000      1.33.4.1.3400.1
--- params.def  12 Mar 2004 12:15:11 -0000
*************** DEFPARAM(PARAM_MAX_GCSE_MEMORY,
*** 130,136 ****
  DEFPARAM(PARAM_MAX_GCSE_PASSES,
        "max-gcse-passes",
        "The maximum number of passes to make when doing GCSE",
!       1)
   
  /* This parameter limits the number of insns in a loop that will be
unrolled,
     and by how much the loop is unrolled.
--- 130,136 ----
  DEFPARAM(PARAM_MAX_GCSE_PASSES,
        "max-gcse-passes",
        "The maximum number of passes to make when doing GCSE",
!       2)
   
  /* This parameter limits the number of insns in a loop that will be
unrolled,
     and by how much the loop is unrolled.



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]