From: glenn@curie.ces.cwru.edu (Glenn Crocker)
Subject: Optimization, esp for MIPS
Organization: Case Western Reserve University
Distribution: gnu
Date: Mon, 12 Oct 1992 03:27:58 GMT

This is based on a post I made a couple of weeks ago, but I know more
now, so the question has changed from "can somebody fix this?" to "can
I fix this?"


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 -v -S min2.c
Reading specs from /usr/local/lib/gcc-lib/decstation/2.2.2/specs
gcc version 2.2.2
/usr/local/lib/gcc-lib/decstation/2.2.2/cpp -lang-c -v -undef -D__GNUC__=2 -D__
ANSI_COMPAT -DMIPSEL -DR3000 -DSYSTYPE_BSD -D_SYSTYPE_BSD -Dbsd4_2 -Dhost_mips -
Dmips -Dultrix -Dunix -D__ANSI_COMPAT -D__MIPSEL__ -D__R3000__ -D__SYSTYPE_BSD__
 -D___SYSTYPE_BSD__ -D__bsd4_2__ -D__host_mips__ -D__mips__ -D__ultrix__ -D__uni
x__ -D__ANSI_COMPAT -D__MIPSEL -D__R3000 -D__SYSTYPE_BSD -D___SYSTYPE_BSD -D__bs
d4_2 -D__host_mips -D__mips -D__ultrix -D__unix -D__OPTIMIZE__ -D__LANGUAGE_C__
-D__LANGUAGE_C -DLANGUAGE_C min2.c /usr/tmp/cca07279.i
GNU CPP version 2.2.2 [AL 1.1, MM 19] DECstation running ultrix
 /usr/local/lib/gcc-lib/decstation/2.2.2/cc1 /usr/tmp/cca07279.i -mgpopt -quiet
-dumpbase min2.c -O3 -version -fforce-addr -fforce-mem -o min2.s
GNU C version 2.2.2 [AL 1.1, MM 19] DECstation running ultrix compiled by GNU C
version 2.2.2.

Gives us this MIPS .s file:

---------------------------------
...
        li      $5,2
        move    $4,$0
        la      $3,a
$L10:
        lw      $2,0($3)
        addu    $4,$4,1
        addu    $5,$5,$2
        slt     $2,$4,1024
        .set    noreorder
        .set    nomacro
        bne     $2,$0,$L10
        addu    $3,$3,4
        .set    macro
        .set    reorder
--------------------------

Now, what would be nicer would be this:


----------------------------
        li      $5,2
        move    $4,$0
        la      $3,a
	li	$6,1024		# We know how far the loop will go beforehand
$L10:
        lw      $2,0($3)
        addu    $4,$4,1
        addu    $5,$5,$2	# We got rid of the 'slt', which is nice.
        .set    noreorder
        .set    nomacro
        bne     $4,$6,$L10	# And we just have to do a 'bne'.  Yay.
        addu    $3,$3,4
        .set    macro
        .set    reorder
--------------------------

What this basically entails is figuring out that 'i' is getting
incremented by 1 each time through the loop, and thus that the loop
will get executed exactly 1024 times, so rather than using a
'branch-if-less-than' (which on the MIPS is 2 instructions, an 'slt'
and a 'bne'), we can use a single 'branch-if-not-equal'.

The loop induction code already figures this stuff out, but doesn't
change the conditional at the end of the loop, most likely because it
doesn't matter on most processors.

So, my question is: Is this added in the mythical and highly-awaited
gcc 2.3?  If not, I'm willing to hack around with this, but I'd really
appreciate some pointers as to where this sort of optimization ought
to be added.  (i.e.  should it go in the already-damn-long
strength_reduce(), or perhaps in unroll_loop(), or somewhere else
altogether?)  Should I add a new -foption, or have this be a
side-effect of -funroll-loops?

Thanks for any information you can give me about this.

-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 |