git.gag.com Git - fw/sdcc/blob - doc/SDCCUdoc-6.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
   2 <HTML>
   3 <HEAD>
   4  <META NAME="GENERATOR" CONTENT="SGML-Tools 1.0.7">
   5  <TITLE>SDCC Compiler User Guide: Optimizations</TITLE>
   6  <LINK HREF="SDCCUdoc-7.html" REL=next>
   7  <LINK HREF="SDCCUdoc-5.html" REL=previous>
   8  <LINK HREF="SDCCUdoc.html#toc6" REL=contents>
   9 </HEAD>
  10 <BODY>
  11 <A HREF="SDCCUdoc-7.html">Next</A>
  12 <A HREF="SDCCUdoc-5.html">Previous</A>
  13 <A HREF="SDCCUdoc.html#toc6">Contents</A>
  14 <HR>
  15 <H2><A NAME="Optimizations"></A> <A NAME="s6">6. Optimizations</A> </H2>
  16
  17 <P>SDCC performs a a host of standard optimizations in addition to some MCU
  18 specific optimizations.
  19 <H2><A NAME="Sub-expression Elimination"></A> <A NAME="ss6.1">6.1 Sub-expression elimination</A>
  20  </H2>
  21
  22 <P>The compiler does local and global common subexpression elimination.
  23 <P><CODE>eg. </CODE>
  24 <P>
  25 <PRE>
  26 i = x + y + 1;
  27 j = x + y;
  28
  29 </PRE>
  30 <P>will be translated to
  31 <P>
  32 <PRE>
  33 iTemp = x + y
  34 i = iTemp + 1
  35 j = iTemp
  36
  37 </PRE>
  38 <P>Some subexpressions are not as obvious as the above example.
  39 <P>eg.
  40 <P>
  41 <PRE>
  42 a-&gt;b[i].c = 10;
  43 a-&gt;b[i].d = 11;
  44
  45 </PRE>
  46 <P>In this case the address arithmetic a-&gt;b[i] will be computed
  47 only once; the equivalent code in C would be.
  48 <P>
  49 <PRE>
  50 iTemp = a-&gt;b[i];
  51 iTemp.c = 10;
  52 iTemp.d = 11;
  53
  54 </PRE>
  55 <P>The compiler will try to keep these temporary variables in registers.
  56 <H2><A NAME="Dead-code elimination"></A> <A NAME="ss6.2">6.2 Dead-Code elimination.</A>
  57  </H2>
  58
  59 <P>eg.
  60 <P>
  61 <PRE>
  62 int global;
  63 void f () {
  64   int i;
  65   i = 1;    /* dead store */
  66   global
  67  = 1; /* dead store */
  68   global = 2;
  69   return;
  70   global = 3; /* unreachable
  71  */
  72 }
  73
  74 </PRE>
  75 <P>will be changed to
  76 <P>
  77 <PRE>
  78 int global; void f ()
  79 {
  80  global = 2;
  81  return;
  82 }
  83
  84 </PRE>
  85 <H2><A NAME="Copy-Propagation"></A> <A NAME="ss6.3">6.3 Copy-Propagation:</A>
  86  </H2>
  87
  88 <P>eg.
  89 <P>
  90 <PRE>
  91 int f() {
  92    int i, j;
  93    i = 10;
  94    j = i;
  95    return j;
  96 }
  97
  98 </PRE>
  99 <P>will be changed to
 100 <P>
 101 <PRE>
 102 int f() {
 103     int i,j;
 104     i = 10;
 105     j = 10;
 106     return 10;
 107
 108 }
 109
 110 </PRE>
 111 <P>Note: the dead stores created by this copy propagation will be eliminated
 112 by dead-code elimination .
 113 <H2><A NAME="Loop Optimizations"></A> <A NAME="ss6.4">6.4 Loop optimizations</A>
 114  </H2>
 115
 116 <P>Two types of loop optimizations are done by SDCC loop invariant lifting
 117 and strength reduction of loop induction variables.In addition to the strength
 118 reduction the optimizer marks the induction variables and the register allocator
 119 tries to keep the induction variables in registers for the duration of the
 120 loop. Because of this preference of the register allocator , loop induction
 121 optimization causes an increase in register pressure, which may cause unwanted
 122 spilling of other temporary variables into the stack / data space . The compiler
 123 will generate a warning message when it is forced to allocate extra space either
 124 on the stack or data space. If this extra space allocation is undesirable then
 125 induction optimization can be eliminated either for the entire source file
 126 ( with --noinduction option) or for a given function only (#pragma NOINDUCTION).
 127 <H3><A NAME="Loop Invariant"></A> Loop Invariant: </H3>
 128
 129 <P>eg
 130 <P>
 131 <PRE>
 132 for (i = 0 ; i &lt; 100 ; i ++)
 133      f += k + l;
 134
 135 </PRE>
 136 <P>changed to
 137 <P>
 138 <PRE>
 139 itemp = k + l;
 140 for ( i = 0; i &lt; 100; i++ ) f += itemp;
 141
 142 </PRE>
 143 <P>As mentioned previously some loop invariants are not as apparent, all static
 144 address computations are also moved out of the loop.
 145 <H3><A NAME="Strength Reduction"></A> Strength reduction : </H3>
 146
 147 <P>This optimization substitutes an expression by a cheaper expression.
 148 <P>eg.
 149 <P>
 150 <PRE>
 151 for (i=0;i &lt; 100; i++) ar[i*5] = i*3;
 152
 153 </PRE>
 154 <P>changed to
 155 <P>
 156 <PRE>
 157 itemp1 = 0;
 158 itemp2 = 0;
 159 for (i=0;i&lt; 100;i++) {
 160      ar[itemp1]
 161  = itemp2;
 162      itemp1 += 5;
 163      itemp2 += 3;
 164 }
 165
 166 </PRE>
 167 <P>The more expensive multiplication is changed to a less expensive addition.
 168 <H3><A NAME="Loop reversing"></A> Loop reversing: </H3>
 169
 170 <P>This optimization is done to reduce the overhead of checking loop boundaries
 171 for every iteration. Some simple loops can be reversed and implemented using
 172 a "decrement and jump if not zero" instruction. SDCC checks for the following
 173 criterion to determine if a loop is reversible (note: more sophisticated compiers
 174 use data-dependency analysis to make this determination, SDCC uses a more simple
 175 minded analysis).
 176 <P>
 177 <UL>
 178 <LI>The 'for' loop is of the form
 179 "for ( &lt;symbol&gt; = &lt;expression&gt;
 180 ; &lt;sym&gt; [&lt; | &lt;=] &lt;expression&gt; ; [&lt;sym&gt;++
 181 | &lt;sym&gt; += 1])
 182 &lt;for body&gt;"</LI>
 183 <LI>The &lt;for body&gt; does not contain "continue" or 'break".</LI>
 184 <LI>All goto's are contained within the loop.</LI>
 185 <LI>No function calls within the loop.</LI>
 186 <LI>The loop control variable &lt;sym&gt; is not assigned any value within
 187 the loop</LI>
 188 <LI>The loop control variable does NOT participate in any arithmetic operation
 189 within the loop.</LI>
 190 <LI>There are NO switch statements in the loop.</LI>
 191 </UL>
 192 <P>Note djnz instruction can be used for 8-bit values ONLY, therefore it is
 193 advantageous to declare loop control symbols as either 'char' or 'short', ofcourse
 194 this may not be possible on all situations.
 195 <H2><A NAME="Algebraic Simplifications"></A> <A NAME="ss6.5">6.5 Algebraic simplifications:</A>
 196  </H2>
 197
 198 <P>SDCC does numerous algebraic simplifications, the following is a small
 199 sub-set of these optimizations.
 200 <P>
 201 <PRE>
 202 eg
 203 i = j + 0 ; /* changed to */ i = j;
 204 i /= 2; /* changed to */ i &gt;&gt;=
 205  1;
 206 i = j - j ; /* changed to */ i = 0;
 207 i = j / 1 ; /* changed to */ i = j;
 208
 209 </PRE>
 210 <P>Note the subexpressions given above are generally introduced by macro expansions
 211 or as a result of copy/constant propagation.
 212 <H2><A NAME="Switch Statement"></A> <A NAME="ss6.6">6.6 'switch' statements.</A>
 213  </H2>
 214
 215 <P>SDCC changes switch statements to jump tables when the following conditions
 216 are true.
 217 <P>
 218 <UL>
 219 <LI>The case labels are in numerical sequence , the labels need not be in order,
 220 and the starting number need not be one or zero.</LI>
 221 </UL>
 222 <P>eg
 223 <P>
 224 <PRE>
 225 switch(i) {                         switch (i) {
 226 case 4:...
 227                           case 1: ...
 228 case 5:...                          case
 229  2: ...
 230 case 3:...                          case 3: ...
 231 case 6:...
 232                   case 4: ...
 233 }                                   }
 234
 235 </PRE>
 236 <P>Both the above switch statements will be implemented using a jump-table.
 237 <P>
 238 <UL>
 239 <LI>The number of case labels is at least three, since it takes two conditional
 240 statements to handle the boundary conditions.</LI>
 241 <LI>The number of case labels is less than 84, since each label takes 3 bytes
 242 and a jump-table can be utmost 256 bytes long. </LI>
 243 </UL>
 244 <P>Switch statements which have gaps in the numeric sequence or those that
 245 have more that 84 case labels can be split into more than one switch statement
 246 for efficient code generation.
 247 <P>eg
 248 <P>
 249 <PRE>
 250 switch (i) {
 251 case 1: ...
 252 case 2: ...
 253 case 3: ...
 254 case 4: ...
 255 case
 256  9: ...
 257 case 10: ...
 258 case 11: ...
 259 case 12: ...
 260 }
 261
 262 </PRE>
 263 <P>If the above switch statement is broken down into two switch statements
 264 <P>
 265 <PRE>
 266 switch (i) {
 267 case 1: ...
 268 case 2: ...
 269 case 3: ...
 270 case 4: ...
 271 }switch (i) {
 272 case 9: ...
 273 case 10: ...
 274 case 11: ...
 275 case 12:...
 276
 277 }
 278
 279 </PRE>
 280 <P>then both the switch statements will be implemented using jump-tables whereas
 281 the unmodified switch statement will not be .
 282 <H2><A NAME="bit shifting"></A> <A NAME="ss6.7">6.7 bit-shifting operations.</A>
 283  </H2>
 284
 285 <P>Bit shifting is one of the most frequently used operation in embedded programming
 286 . SDCC tries to implement bit-shift operations in the most efficient way possible.
 287 <P>eg.
 288 <P>
 289 <PRE>
 290 unsigned short i;...
 291 i&gt;&gt;= 4;
 292 ..
 293
 294 </PRE>
 295 <P>generates the following code.
 296 <P>
 297 <PRE>
 298 mov a,_i
 299 swap a
 300 anl a,#0x0f
 301 mov _i,a
 302
 303 </PRE>
 304 <P>In general SDCC will never setup a loop if the shift count is known. Another
 305 example
 306 <P>
 307 <PRE>
 308 unsigned int i;
 309 ...
 310 i &gt;&gt;= 9;
 311 ...
 312
 313 </PRE>
 314 <P>will generate
 315 <P>
 316 <PRE>
 317 mov a,(_i + 1)
 318 mov (_i + 1),#0x00
 319 clr c
 320 rrc a
 321 mov _i,a
 322
 323 </PRE>
 324 <P>Note that SDCC stores numbers in little-endian format (i.e. lowest order
 325 first)
 326 <H3><A NAME="bit rotation"></A> Bit-rotation: </H3>
 327
 328 <P>A special case of the bit-shift operation is bit rotation, SDCC recognizes
 329 the following expression to be a left bit-rotation.
 330 <P>
 331 <PRE>
 332 unsigned char i;
 333 ...
 334 i = ( ( i &lt;&lt; 1) | ( i &gt;&gt; 7));
 335 ...
 336
 337 </PRE>
 338 <P>will generate the following code.
 339 <P>
 340 <PRE>
 341 mov a,_i
 342 rl a
 343 mov _i,a
 344
 345 </PRE>
 346 <P>SDCC uses pattern matching on the parse tree to determine this operation
 347 .Variations of this case will also be recognized as bit-rotation i.e i = ((i
 348 &gt;&gt; 7) | (i &lt;&lt; 1)); /* left-bit rotation */
 349 <H2><A NAME="Highest Order Bit"></A> <A NAME="ss6.8">6.8 Highest Order Bit.</A>
 350  </H2>
 351
 352 <P>It is frequently required to obtain the highest order bit of an integral
 353 type (int,long,short or char types). SDCC recognizes the following expression
 354 to yield the highest order bit and generates optimized code for it.
 355 <P>
 356 <PRE>
 357 eg
 358 unsigned int gint;
 359 foo () {
 360 unsigned char hob;
 361    ...
 362    hob
 363  = (gint &gt;&gt; 15) &amp; 1;
 364    ..
 365 }
 366
 367 </PRE>
 368 <P>Will generate the following code.
 369 <P>
 370 <PRE>
 371                              61 ;  hob.c 7
 372    000A E5*01
 373  62         mov  a,(_gint + 1)
 374    000C 33                   63         rlc
 375  a
 376    000D E4                   64         clr  a
 377    000E 13
 378  65         rrc  a
 379    000F F5*02                66         mov  _foo_hob_1_1,a
 380
 381 </PRE>
 382 <P>Variations of this case however will NOT be recognized . It is a standard
 383 C expression , so I heartily recommend this be the only way to get the highest
 384 order bit, (it is portable). Of course it will be recognized even if it is
 385 embedded in other expressions.
 386 <P>
 387 <PRE>
 388 eg.xyz = gint + ((gint &gt;&gt; 15) &amp; 1);
 389
 390 </PRE>
 391 <P>will still be recognized.
 392 <H2><A NAME="Peep-Hole"></A> <A NAME="ss6.9">6.9 Peep-hole optimizer.</A>
 393  </H2>
 394
 395 <P>The compiler uses a rule based , pattern matching and re-writing mechanism
 396 for peep-hole optimization . It is inspired by 'copt' a peep-hole optimizer
 397 by Christopher W. Fraser (cwfraser@microsoft.com). A default set of rules are
 398 compiled into the compiler, additional rules may be added with the --peep-file
 399 &lt;filename&gt; option. The rule language is best illustrated with examples.
 400 <P>
 401 <PRE>
 402 replace {
 403 mov %1,a
 404 mov a,%1 } by { mov %1,a
 405  }
 406
 407 </PRE>
 408 <P>The above rule will the following assembly sequence
 409 <P>
 410 <PRE>
 411 mov r1,a
 412 mov a,r1
 413
 414 </PRE>
 415 <P>to
 416 <P>
 417 <PRE>
 418 mov r1,a
 419
 420 </PRE>
 421 <P>Note: All occurrences of a '%n' ( pattern variable ) must denote
 422 the same string. With the above rule, the assembly sequence
 423 <P>
 424 <PRE>
 425 mov r1,a
 426 mov a,r2
 427
 428 </PRE>
 429 <P>will remain unmodified. Other special case optimizations may be added by
 430 the user (via --peep-file option), eg. some variants of the 8051 MCU allow
 431 only 'AJMP' and 'ACALL' , the following two rules will change all 'LJMP' &amp;
 432 'LCALL' to 'AJMP' &amp; 'ACALL'.
 433 <P>
 434 <PRE>
 435 replace { lcall %1 } by { acall %1 }
 436
 437 replace { ljmp %1 } by { ajmp %1 }
 438
 439 </PRE>
 440 <P>The inline-assembler' code is also passed through the peep hole optimizer,
 441 thus the peephole optimizer can also be used as an assembly level macro expander.
 442 The rules themselves are MCU dependent whereas the rule language infra-structure
 443 is MCU independent. Peephole optimization rules for other MCU can be easily
 444 programmed using the rule language.
 445 <P>The syntax for a rule is as follows ,
 446 <P>
 447 <PRE>
 448 rule := replace [ restart ] '{' &lt;assembly sequence&gt;
 449  '\n'
 450                             '}' by '{' '\n'
 451
 452                              &lt;assembly sequence&gt; '\n'
 453
 454                    '}' [if &lt;functionName&gt; ] '\n'
 455 &lt;assembly
 456  sequence&gt; := assembly instruction (each instruction including labels must
 457  be on a separate line).
 458
 459 </PRE>
 460 <P>The optimizer will apply to the rules one by one from the top in the sequence
 461 of their appearance, it will terminate when all rules are exhausted. If the
 462 'restart' option is specified, then the optimizer will start matching the rules
 463 again from the top, this option for a rule is expensive (performance), it is
 464 intended to be used in situations where a transformation will trigger the same
 465 rule again. A good example of this the following rule.
 466 <P>
 467 <PRE>
 468 replace restart {
 469 pop %1
 470 push %1 } by {
 471
 472 ; nop
 473 }
 474
 475 </PRE>
 476 <P>Note that the replace pattern cannot be a blank, but can be a comment line.
 477 Without the 'restart' option only the inner most 'pop' 'push' pair would be
 478 eliminated. i.e.
 479 <P>
 480 <PRE>
 481 pop ar1
 482 pop ar2
 483 push ar2
 484 push ar1
 485
 486 </PRE>
 487 <P>would result in
 488 <P>
 489 <PRE>
 490 pop ar1
 491 ; nop
 492 push ar1
 493
 494 </PRE>
 495 <P>with the 'restart' option the rule will be applied again to the resulting
 496 code and the all the 'pop' 'push' pairs will be eliminated to yield
 497 <P>
 498 <PRE>
 499 ; nop
 500 ; nop
 501
 502 </PRE>
 503 <P>A conditional function can be attached to a rule. Attaching rules are somewhat
 504 more involved, let me illustrate this with an example.
 505 <P>
 506 <PRE>
 507 replace {
 508      ljmp %5
 509 %2:} by {
 510      sjmp
 511  %5
 512 %2:} if labelInRange
 513
 514 </PRE>
 515 <P>The optimizer does a look-up of a function name table defined in function
 516 'callFuncByName' in the source file SDCCpeeph.c , with the name 'labelInRange',
 517 if it finds a corresponding entry the function is called. Note there can be
 518 no parameters specified for these functions, in this case the use of '%5'
 519 is crucial, since the function labelInRange expects to find the label in that
 520 particular variable (the hash table containing the variable bindings is passed
 521 as a parameter). If you want to code more such functions , take a close look
 522 at the function labelInRange and the calling mechanism in source file SDCCpeeph.c.
 523 I know this whole thing is a little kludgey , may be some day we will have
 524 some better means. If you are looking at this file, you will also see the default
 525 rules that are compiled into the compiler, you can your own rules in the default
 526 set there if you get tired of specifying the --peep-file option.
 527 <HR>
 528 <A HREF="SDCCUdoc-7.html">Next</A>
 529 <A HREF="SDCCUdoc-5.html">Previous</A>
 530 <A HREF="SDCCUdoc.html#toc6">Contents</A>
 531 </BODY>
 532 </HTML>