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 cant remeber 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 dosnt 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 unavailble registers.
  39     Register packing removes unneeded iTemps.
  40 2.  Determine what number and type of regsiters are needed for each
  41     live range.
  42     It does
  43        If the iTemp lives for zero time, dont 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                  acesnding 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 intersting
 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 :)