git.gag.com Git - fw/sdcc/blob - doc/random-notes.txt

   1 Random notes
   2 ------------
   3 A random set of notes about sdcc and how it works.
   4
   5 Michael on the register allocation stage:
   6 -----------------------------------------
   7 Lets trace how the register allocator in the mcs51 port works.
   8
   9 Some concepts:
  10 eBBlock
  11         A basic block.  I can't remember the conditions, but a basic block
  12 is one that is easy to optimise and analyse.  I guess this means that it has
  13 a nice set of assignments and a reasonably straight flow.
  14 iCode
  15         Intermediate code.  Provides the interface between the parser + optimiser
  16 and the code generator by providing an abstract machine with infinite registers
  17 which the parser can generate for and the back end can turn into real code.
  18 iTemps
  19         An iTemp is a temporary register used in iCode.  These will eventually
  20 be either replaced, allocated into a register, or placed onto the stack by the
  21 backend.
  22 Live range
  23      The live range of an iTemp is the part of the code that the iTemp is used
  24 over.  Generally the live range of an iTemp is from its first assignment to its
  25 last use.
  26
  27 Input to mcs51_assignRegisters is an array of basic blocks.  Assign
  28 registers is normally called at the end of a function.
  29
  30 In pseudo code,
  31 1.  For each basic block, pack the registers in the block.
  32     In this case register packing consists of:
  33        Remove any unneded iTemps that are just used in assignments.
  34        Mark anything that can be rematerialised as rematerialisable.
  35            There is no way I spelt that correctly.  Something is rematerialisable
  36            if it can be generated easily and is constant, and hence dosn't need
  37            to be cached away in an iTemp.  An example is the address of something.
  38        Packs iTemps that are only used once into normally unavailable registers.
  39     Register packing removes unneeded iTemps.
  40 2.  Determine what number and type of registers are needed for each
  41     live range.
  42     It does
  43        If the iTemp lives for zero time, don't bother assigning
  44        If its not an iTemp, skip for now.
  45        If its a conditional (determined in the register packing), skip as it will
  46        be stored in carry.
  47        If the iTemp is already packed from 1.c, skip
  48        If the iTemp is remat and some other magic, skip.
  49        Else set the number and type of registers based on the size of the iTemp.
  50 3.  Assign registers for each segment.
  51     For each iCode, do
  52         If it is a IPOP (pop of an iTemp at the end of a block), reset the LR.
  53         De-assign the live ranges of the iTemps that expire here.
  54             For each iTemp, do
  55                 If this iTemp is still alive, skip
  56                 If this iTemp is spilt on the stack, free the location and continue.
  57                 If there are no registers assigned (?), continue.
  58                 Some magic using IFX and IPOP
  59                 If the iTemp has no registers, continue.
  60                 If the result of this iCode doesnt yet have registers, allocate them now.  Weird.
  61                 Deallocate the registers used.
  62         Skip instructions that dont need registers (IFX, JUMPTABLE, POINTER_SET)
  63         Only assign registers to the result of this iCode.
  64         If the iCode has registers, or has been spilt, continue.
  65         If this will cause a spill as it needs more registers than are free, then
  66             Find those that can be spilt.
  67             Spill this if its easy.
  68             Spill this if its the least used.
  69         Allocate registers to the result iTemp
  70         If any registers in the result are shared with the operand, make them line up.
  71 4.  Create the register mask for each segment.
  72     For each iCode, do
  73         Set the used register bit vector from the used registers.
  74         Mark these registers as used in the higher function.  This lets the generator
  75         decide which registers need to be saved when calling or being called by a function.
  76         Hmm.  It seems to re-setup the used register bit vector.
  77 5.  Redo the stack offsets.
  78 6.  Turn the basic blocks into an intermediate code chain.
  79         Takes the array of basic blocks and pulls them out into one iCode chain.
  80 7.  Optimise the labels in the iCode chain.
  81         Skipped if the label optimisations are turned off.
  82         Remove any gotos that go to the next line.
  83         Simplify any chained gotos
  84         Remove unreferenced labels
  85         Remove unreferenced code.
  86 7.  Generate the mcs51 code from the iCode chain.
  87 8.  Deallocate everything (registers and stack locations).
  88
  89 Sandeep:
  90 --------
  91 =======
  92 Sandeep:
  93 --------
  94 The Register Allocation story.
  95
  96 Before I get into this there are a few important fields
  97 on the iCode & oprtand data structures that need to be
  98 addressed.
  99
 100 iCode.
 101 -----
 102         ->key  -  is an unique number assigned to this
 103                   iCode when this icode is allocated.
 104
 105         ->seq  - sequence number of the iCode given in
 106                  ascending order of execution.
 107
 108 operand.
 109 -------
 110         ->key  - unique number for an operand when operand
 111                  is allocated.
 112
 113 OP_LIVEFROM(op) - sequence number of the iCode where it was
 114                   first defined. Computed in SDCClrange.c
 115
 116 OP_LIVETO(op)   - sequence number of the iCode where it is
 117                   last used. Computed in SDCClrange.c
 118
 119
 120
 121
 122 Sandeep:
 123 --------
 124 Adding memory maps for AVR, setup default map for
 125 local & global variables in port.h will be initialised
 126 by the _<port>_finaliseOptions() [good functions]..some
 127 kludges remain because of the "overlay" segment for 8051.
 128
 129 The memory segment stuff will have to be made more flexible.
 130 Currently there does not seem to be a 1-to-1 correspondence
 131 between storage class & memory map. (should there be??).
 132
 133 Also Added check for memory map in SDCCmem.c allocLocal
 134 and allocglobal for "eeprom" memory space (AVR).
 135
 136
 137
 138 Michael:
 139 --------
 140 Tracing parmBytes and function calls.
 141
 142 Bug:
 143 void printf(const char *format);
 144
 145 void puts(const char *s)
 146 {
 147         printf(s);
 148 }
 149
 150 Generates the pseudo-code:
 151           hl = s
 152           push hl
 153           call printf
 154           pop l (not hl - so parmBytes is too small)
 155
 156 parmBytes for a function call seems to be setup in geniCodeCall in
 157 SDCCicode.c.
 158
 159 geniCodeCall:
 160 * Takes care of calls with side effects (?)
 161 * Generates the icode to push the parameters (this also computes the
 162   resulting stack size)
 163 * Generates a CALL or PCALL depending on if its a function or pointer to.
 164 * Computes the result
 165 * Adds the code for the call to the chain.
 166
 167 My bug is probably in geniCodeParms - it's probably computing the
 168 size of pointers wrong.
 169
 170 geniCodeParms:
 171 * A 'parm' node causes this to be run on the tree branches.
 172 * It switches on the stack mode and sendto mode, and adds the
 173   instructions required to push or put.
 174 * A push adds the result of 'getSize' to the stack size.
 175
 176 So the bug is probably in getSize.  's' is not an aggregate, so the
 177 bug is in getSize().
 178
 179 It seems that IS_SPEC() is being set, deferencing *s so that it's size
 180 is sizeof(char) == 1.  It's either a SPECIFIER or a DECLARATOR - seems that
 181 were the wrong way around.  This is set in SDCCsymt.c, SDCCval.c, and the
 182 yacc file. SDCCsymt.c and SDCCval.c havnt really changed in 5 days - must
 183 be SDCC.y.  Nope, no changes.  diff against 5 days ago shows only interesting
 184 changes are in SDCCicode.  Same with -14 days.
 185
 186 Michael
 187 -------
 188 Next bug is global function parameters not being pushed correctly. i.e
 189
 190 unsigned int counter;
 191
 192 void print(void)
 193 {
 194         printf("Counter is %u\n", counter);
 195 }
 196 generates:
 197 _print::
 198         ld hl,#_counter
 199         push hl
 200         ld hl,#str_1
 201         push hl
 202         call printf
 203         fix, ret
 204
 205 which is more like:
 206         printf("Counter is %u\n", &counter);
 207
 208 First looking in SDCCicode.c for the stuff that generates function calls:
 209 Probably a bug in geniCodeParams.
 210 Nope, a bug in my stuff :)
 211
 212 Michael
 213 -------
 214 Comparing the dhrystone code vs Hitech C v7.50
 215
 216 cp:
 217         ld      hl,__r
 218         ld      (_Next_Ptr_Glob),hl
 219 vs:
 220         ld      hl,#__r
 221         ld      iy,#_Next_Ptr_Glob
 222         ld      0(iy),l
 223         ld      1(iy),h
 224
 225 cp:
 226         ld      a,#<__r
 227         add     a,#0x27
 228         ld      iy,#_Ptr_Glob
 229         ld      0(iy),a
 230         ld      a,#>__r
 231         adc     a,#0x00
 232         ld      1(iy),a
 233 vs:
 234         ld      hl,__r+027h
 235         ld      (_Ptr_Glob),hl
 236
 237 cp:
 238         ld      iy,#_Next_Ptr_Glob
 239         ld      a,0(iy)
 240         ld      (hl),a
 241         inc     hl
 242         ld      a,1(iy)
 243         ld      (hl),a
 244
 245 vs:
 246         ld      bc,(_Next_Ptr_Glob)
 247         ld      hl,(_Ptr_Glob)
 248         ld      (hl),c
 249         inc     hl
 250         ld      (hl),b
 251
 252
 253 cp:
 254         ld      bc,(_Ptr_Glob)
 255         ld      l,c
 256         ld      h,b
 257         inc     hl
 258         inc     hl
 259         ld      (hl),#0x00
 260         inc     hl
 261         ld      (hl),#0x00
 262 vs:
 263         ld      iy,(_Ptr_Glob)
 264         ld      (iy+2),0
 265         ld      (iy+3),0
 266
 267
 268 strcpy is inlined as:
 269 u12:
 270         ld      a,(hl)
 271         ldi
 272         or      a
 273         jp      nz,u12
 274
 275 cp:
 276         ld      a,#<_Arr_2_Glob
 277         add     a,#0x2E
 278         ld      -80(ix),a
 279         ld      a,#>_Arr_2_Glob
 280         adc     a,#0x03
 281         ld      -79(ix),a
 282 ;       genAssign (pointer)
 283 ;       AOP_STK for _main_sloc1_1_0
 284         ld      l,-80(ix)
 285         ld      h,-79(ix)
 286         ld      (hl),#0x0A
 287         inc     hl
 288         ld      (hl),#0x00
 289 vs:
 290         ld      hl,0Ah
 291         ld      (_Arr_2_Glob+032Eh),hl
 292
 293 cp:
 294         ld      a,-72(ix)
 295         or      a,a
 296         jp      nz,00126$
 297         ld      a,-71(ix)
 298         and     a,#0x03
 299 ; Rule 4: Changed jp order
 300         jp      z,00127$
 301 00126$:
 302         jp      00102$
 303 00127$:
 304
 305 vs:
 306         ld      (ix+-7),c
 307         ld      (ix+-6),b
 308         ld      a,c
 309         ld      l,a
 310         ld      a,b
 311         and     03h
 312         ld      h,a
 313         ld      a,l
 314         or      h
 315         jp      nz,l12
 316
 317 cp:
 318         ld      a,-82(ix)
 319         or      a,-81(ix)
 320         sub     a,#0x01
 321         ld      a,#0x00
 322         rla
 323         ld      iy,#_Bool_Glob
 324         ld      0(iy),a
 325         ld      1(iy),#0x00
 326
 327 vs:
 328         ld      a,l
 329         or      h
 330         ld      hl,01h
 331         jp      z,u42
 332         dec     hl
 333 u42:
 334         ld      (_Bool_Glob),hl
 335
 336 ;C:\TEMP\DHRY.C: 173: Int_3_Loc = 5 * Int_1_Loc - Int_2_Loc;
 337 is turned into:
 338         ld      l,(ix+-13)
 339         ld      h,(ix+-12)
 340         ld      d,h
 341         ld      e,l
 342         add     hl,hl
 343         add     hl,hl
 344         add     hl,de
 345
 346 Comapring two types of cmpeq:
 347         ld      a,c             ; 4
 348         cp      a,#0xFB         ; 7
 349         jp      nz,00119$       ; 10
 350         ld      a,b             ; 4
 351         cp      a,#0xFF         ; 7
 352 ; Rule 5: Changed jump logic
 353         jp      z,00101$        ; 10
 354 00119$:
 355         ; 21 to 42
 356
 357 vs:
 358         ld      hl,#val         ; 10
 359         or      a               ; 4
 360         sbc     hl,bc           ; 15
 361         jp      z,...           ; 10
 362         ; Always 39 - worse
 363
 364 Comaring break even point for shift:
 365         ld      a,#0x03+1       ; 7
 366         jp      00114$          ; 10
 367 00113$:
 368         sra     b               ; 8
 369         rr      c               ; 8
 370 00114$:
 371         dec     a               ; 4
 372         jp      nz,00113$       ; 10
 373
 374         ; Bytes: 2+3+1+1+1+3 = 11
 375         ; t-states = 17+n*30
 376 vs
 377         sra     b
 378         rr      c ...
 379         ; Bytes: 2*n
 380         ; t-states = 16*n
 381
 382         Ah, pick 4