3 A random set of notes about sdcc and how it works.
5 Michael on the register allocation stage:
6 -----------------------------------------
7 Lets trace how the register allocator in the mcs51 port works.
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.
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.
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
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
27 Input to mcs51_assignRegisters is an array of basic blocks. Assign
28 registers is normally called at the end of a function.
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
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
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.
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.
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.
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).
94 The Register Allocation story.
96 Before I get into this there are a few important fields
97 on the iCode & oprtand data structures that need to be
102 ->key - is an unique number assigned to this
103 iCode when this icode is allocated.
105 ->seq - sequence number of the iCode given in
106 acesnding order of execution.
110 ->key - unique number for an operand when operand
113 OP_LIVEFROM(op) - sequence number of the iCode where it was
114 first defined. Computed in SDCClrange.c
116 OP_LIVETO(op) - sequence number of the iCode where it is
117 last used. Computed in SDCClrange.c
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.
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??).
133 Also Added check for memory map in SDCCmem.c allocLocal
134 and allocglobal for "eeprom" memory space (AVR).
140 Tracing parmBytes and function calls.
143 void printf(const char *format);
145 void puts(const char *s)
150 Generates the pseudo-code:
154 pop l (not hl - so parmBytes is too small)
156 parmBytes for a function call seems to be setup in geniCodeCall in
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.
167 My bug is probably in geniCodeParms - it's probably computing the
168 size of pointers wrong.
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.
176 So the bug is probably in getSize. 's' is not an aggregate, so the
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.
188 Next bug is global function parameters not being pushed correctly. i.e
190 unsigned int counter;
194 printf("Counter is %u\n", counter);
206 printf("Counter is %u\n", &counter);
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 :)