🚀 go-pugleaf

I've continued my exploration into GCC's loop optimization, and am a
bit stuck.

For this C code:

-------------------------
extern int a[1024];
extern int k2;

extern int baz(void);

int foo (void)
{
  int i;
  int k1 = 2;

  for (i = 0; i != 1024; i++)
    k1 += a[i];
  return k1;
}
------------------------------

GCC -O3 -fforce-addr -fforce-mem 

(MIPS gcc 2.2.2 plus some MIPS patches from Michael Meissner) gives us this
MIPS .s file:

------------------------------
        li      $5,2		# k1
        move    $4,$0		# i
        li      $6,1024		# Where i will stop
        la      $3,a
$L10:
        lw      $2,0($3)
        addu    $3,$3,4		# increment our address into 'a'.
        addu    $4,$4,1		# increment i
        .set    noreorder
        .set    nomacro
        bne     $4,$6,$L10	# use i for looping
        addu    $5,$5,$2
        .set    macro
        .set    reorder
-------------------------------

But this .s file would be better, and loop induction should get us this:

-------------------------------
        li      $4,2		# k1
        la      $3,a		# starting point in 'a'
        addu    $5,$3,4096	# ending point in 'a'
$L10:
        lw      $2,0($3)	# Note that the 'i' variable is gone.  Yay.
        addu    $3,$3,4
        .set    noreorder
        .set    nomacro
        bne     $3,$5,$L10	# use the ending point in 'a' for looping
        addu    $4,$4,$2
        .set    macro
        .set    reorder
------------------------------

Now, the reason GCC isn't generating the latter version of the code is
that (according to foo.c.loop) it's giving up on optimizing INSN 21:

...
giv of insn 21 not worth while, 0 vs 8.
...
(insn 21 30 22 (set (reg:SI 75)
       (ashift:SI (reg/v:SI 71)
           (const_int 2))) 106 {ashlsi3} (nil)
   (nil))

(This insn would give us this MIPS code, if it weren't optimized out:
	sll	$2,$3,2		# 21 ashlsi3
)

It gives up in strength_reduce(), at loop.c:3653, which is this:

	if (v->lifetime * threshold * benefit < insn_count) 
	  { /* output stuff */
	    v->ignore = 1;
            all_reduced = 0;
          }

At this point, the values of the variables I believe to be pertinent are:

v->lifetime	1
threshold	120
benefit		0
v->benefit	2
insn_count	8
add_cost	2
bl->biv_count	1

The line that causes benefit to be decremented to 0 is:

benefit -= add_cost * bl->biv_count;

The funny thing is that INSN 21 is eliminated during flow analysis.

So, any ideas about how to get it to recognize this nicely?  I just
wrapped the conditional in a "#if 0" so it will always try to do the
optimization, but this is a loss on compiling big programs (because
it'll be trying fruitless optimizations).

One idea I had that might be neat would be to have a new command-line
option which is formatted as a percentage, so if I say -Op100 then it
ignores all the heuristics about when to skip optimizations (-Op50
would halve the cutoffs, etc).  This would be spiffy, but to do it
right would require a gazillion new options (one for each cutoff),
which is a loss, especially because using those options intelligently
would require carnal knowledge of GCC's innards.  (Using the -foptions
already requires quite a bit of familiarity, but they're damned
handy.)  (Are we to the point of needing a ~/.gccrc yet?  :-)

-glenn
--
Glenn Crocker                   |  Hackers aren't unethical, they're
glenn@ces.cwru.edu              |  "Differently-ethical."
CWRU, Cleveland, OH             |
W (216)368-6133 H (216)791-4610 |