URL's to opimization rules of thumb (C language)

"Sergey" <sd@obninsk.ru>
12 Jun 1999 21:24:40 -0400

          From comp.compilers

Related articles
URL's to opimization rules of thumb (C language) sd@obninsk.ru (Sergey) (1999-06-12)
Re: URL's to opimization rules of thumb (C language) bill@megahits.com (Bill A.) (1999-06-19)
| List of all articles for this month |

From: "Sergey" <sd@obninsk.ru>
Newsgroups: comp.compilers
Date: 12 Jun 1999 21:24:40 -0400
Organization: NoOrg
Keywords: optimize, question

Hi All !


I am looking for internet resources with description of common-known
tecniques (rules of thumb) and features widely used in implementations
of popular C compilers. Or examples of optimization tricks already
embedded (and still not-embedded, but desired) in code-generators. I
am interesting especially for 8-bit MCU like Intel 8051/251, but other
also welcome.


Such rules/tricks may be dependent on:


1) source code (for example, constant folding, trivial compare, evident
expression)
2) data type and math implementation
3) CPU features (instructions length/speed/side effect)
4) Possible evident inline equvalent replacements
5) Etc ( my aim - to continue, enhance and classify this list :)


Well, some examples to illustrate what I take in mind.


-------- Example of 1):
    #include <stdio.h>
    main()
    { printf("Hello, World !!!"); /* 1 */
          printf("Hello, World !!!"); /* 2 */
          printf("World !!!"); /* 3 */
    }


    Many C compilers can dedicate storage for string
    "Hello, World !!!" only one time
    (say at anonimous address ADDR_HELLO_WORLD),
    and then put this address in lines /* 1 */ and /* 2 */
    to parameter list for function 'printf'.
    But I don't know C compiler who can generate call in line /* 3 */
    with address (ADDR_HELLO_WORLD+7) instead of dedicating
    separate storage for string "World !!!".




-------- Example of 1) or/and 2):


    func(long X, long Y)
    {
          if ( X < Y ) printf( "X < Y"); /* 1 */
          if ( X < 0 ) printf( "X < 0"); /* 2 */
          if ( X > -1 ) printf( "X > -1"); /* 3 */
    }


    Dummy C-compiler generate the same code sequence for
    lines /* 1 */, /* 2 */ and /* 3 */.
    It will produce code for common-case comparing of two numbers.
    For big-size types, such as long/float it's may be calls to library
functions.


    Smart C compiler in case /* 2 */ take into account
    only MSB (sign bit) of X.


    Very smart C compiler take into account that X is integer and
    (X > -1 ) is equvalent ( X >= 0 ) and in other words, !(X<0),
    so in case /* 3 */ may be checked only MSB (sign bit) of X also
    (like in case /* 2 */)




-------- Example of 1):
    float Pow10[MAX_POW] = { 1.,10.,100.,1000.,10000., 100000., 1000000.,
.... };


    int order(float X)
    { register int i;


          for(i=0; i < MAX_POW; i++) {
                if( ( x >= Pow10[i] ) /* 1 */
                          && ( x < Pow10[i+1] ) /* 2 */
                      )
                          return(i);
          }
          return( -1 );
    }


    Dummy C compiler will calculate address of Pow10[i] and Pow10[i+1]
independently.
    Smart C compiler calculate address of Pow10[i] for line /* 1 */
    and use it as a BASE for line /* 2 */ like with temporary pointer:


          for(i=0; i < MAX_POW; i++) {
                register float *ptr = &Pow10[i];


                if( ( x >= *ptr ) /* 1 */
                          && ( x < *(ptr + 1) ) /* 2 */
                      )


-------- Example of 1) or/and 2):
    long x,y,z;


    x = y / 10;
    z = y % 10;


    Many complier implement integer division via call library function or


-------- Example of 2) or/and 3):


    unsigned func(unsigned x)
    {
          x = x * 1; /* 1 */
          x = x * 2; /* 2 */
          x = x * 8; /* 3 */
          x = x * 16; /* 4 */
          return(x);
    }


    Dummy C compiler generate the same code for lines /*1*/, /*2*/, /*3*/, /*
4 */
    and produce instructions for common-case multiplication (inline MUL or
calls to
    library functions).


    Good C compiler:
              - ignore line /*1*/.
              - replace x = x * 2 with code as for x << = 1;
              - replace x = x * 8 with code as for x << = 3;
              - replace x = x * 16 with code as for x << = 4;
    and each case produce inline code for calculating SHIFT_UNSIGNED_TO_LEFT
    (usually using suitable instructions like Intel 8051 'RL' [, 'RLC'] -
rotate to left [with carry flag] )


    Very good C compiler replace lines /*1*/, /*2*/, /*3*/, /* 4 */
    with x *= 256 but produce code as for (x <<= 8).


    Smart C compiler (with option 'FULL OPTIMIZATION' )
    just generate code for return( x <<= 8) making result consisting of 2
bytes:
                Result.HIGH = X.LOW;
                Result.LOW = 0;
  and don't produce any code for calculating SHIFT_UNSIGNED_TO_LEFT.






-------- Example of 3) and 4):
      void func_A(void);
      void func_B(void);
      void func_C(void);
      unsigned func_D(unsigned X);
      unsigned func_E(unsigned X);


    void func_A(void)
    { func_B(); /* 1 */;
    }
    void func_B(void)
    { /* Do something */
          func_C(); /* 2 */
    }
    void func_C(void)
    { /* Do something */
    }
      unsigned func_D(unsigned X)
      { /* Do something */
            return( func_E(unsigned X) ); /* 3 */
      }
      unsigned func_E(unsigned X)
      { return( /*something*/ ); /* 4 */
      }


      main()
      { register unsigned X;


          func_A(); /* 5 */
          X = func_D(X); /* 6 */
          /* Do something*/
      }


    Dummy C compiler can produce code only 'as in source'.
    Smart C compiler (with option 'FULL OPTIMIZATION'):
            - in line /* 1 */ replace 'CALL func_B' to 'JMP func_B'
                also in lines /* 2 */, /* 3 */ is possible to make JUMP's so save
                stack space (and time, if possible)


      Very Smart C compiler:
            - in line /* 5 */ will call 'func_B' directly


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


I think this theme very old. Anybody interested in also ?
May be exist many big books with theories and empirical tricks.
Well, I want know all and anything.
But more desirable internet resources.


I try to collect cases like above and put it all in set of
C-sources which can be used as a tests for ANSI C compilers.
and illustrate power or idiotism of them.
No 'complex' cases.
Only evident and easy to recognize (exist simple rule 'to see' ).
I hope that compiler authors can easy implement this features.


It's very important for Embedded and Real Time applications
having not only 'ANSI-compatible C compiler',
but also truly efficient, smart code-generator / optimizer.


Try to compile evident cases like above and make a look to assembler
code...:)
Many optimizing code-generators work like 'code-garbage generators'.




Thanks in advance for all who can say anything usefull.


Sergey


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.