Date: Thu, 28 Nov 1996 10:38:41 GMT
From: kvhk AT ivs4 DOT barco DOT com (Koen Van Herck)
Message-Id: <9611281038.AA06988@ivs4.>
To: e DOT oti AT stud DOT warande DOT ruu DOT nl
Cc: djgpp AT delorie DOT com
In-Reply-To: <329C62F6.23F6@stud.warande.ruu.nl> (message from Elliott Oti on Wed, 27 Nov 1996 07:49:10 -0800)
Subject: Re: Optimization
Reply-To: Koen DOT VanHerck AT barco DOT com


> Check if a series of operations can be replaced by a sequence of differential
> ops -
> eg
>  for(i=0;i<100;i++)a[320*i + x] = 5;
> becomes
>  for(i=x;i<32000 + x;i+=320)a[i] = 5   (saves 100 multiplies)
> and so on.
> 

You made a good point, of course, but you didn't count on the
capabilities of gcc. I have tried this out, and guess what ?
GCC is smart enough to translate the first form into the second. As a
matter of fact, the loop itself is almost identical in both cases.

I have an even better example:

   int x, y, a[5][10];

   for (y = 0; y < 5; y++)
      for (x = 0; x < 10; x++)
	 a[y][x] = x * y;

Question: how many multiplications are in this code ? 
Answer: Five. The code is replaced by something like

   for (y = 0; y < 5; y++)
   { 
      data = y * 9;
      ptr = a[y][9];
      for (x = 9; x >= 0; x--)
      {
         *ptr = data;
         ptr--;
         data -= y;
      }
   }

The y * 9 is calculated with a leal instruction. I don't know if this
is more efficient than a multiplication. Perhaps it is. Then it's even
better than five multiplications !

Here is the assembler listing:

  25:array.c       ****    for (y = 0; y < 5; y++)
  91 009c 31F6     		xorl %esi,%esi
  92 009e 89E9     		movl %ebp,%ecx
  93              		.align 2,0x90
  94              	L20:
  26:array.c       ****    {
  27:array.c       ****       for (x = 0; x < 10; x++)
  96 00a0 BB090000 		movl $9,%ebx
  96      00
  97 00a5 8D915CFF 		leal -164(%ecx),%edx
  97      FFFF
  98 00ab 8D04F6   		leal (%esi,%esi,8),%eax
  99 00ae 8D36     		.align 2,0x90
 100              	L24:
  28:array.c       ****       {
  29:array.c       **** 	 a[y][x] = x * y;
 102 00b0 8902     		movl %eax,(%edx)
 104 00b2 83C2FC   		addl $-4,%edx
 105 00b5 29F0     		subl %esi,%eax
 106 00b7 4B       		decl %ebx
 107 00b8 79F6     		jns L24
 109 00ba 83C128   		addl $40,%ecx
 110 00bd 46       		incl %esi
 111 00be 83FE04   		cmpl $4,%esi
 112 00c1 7EDD     		jle L20
  30:array.c       ****       }
  31:array.c       ****    }



----
Koen Van Herck
Electronic Design Engineer
E-mail: Koen DOT VanHerck AT barco DOT com

 BBBB    AAA   RRRR    CCC   OOO     B A R C O   V I S U A L   S Y S T E M S
 B   B  A   A  R   R  C     O   O    A division of  Barco Projection Systems
 B BB   A AAA  R RR  C    OO  O  OO   
 B   B  A   A  R   R  C     O   O    Noordlaan 5      Tel +32 (0)56 36 85 71
 BBBB   A   A  R   R   CCC   OOO     B-8520 Kuurne    Fax +32 (0)56 36 83 55