Section 2: Compiler
91
TI
-
89 / TI
-
92 Plus Sierra C Assembler Reference Manual
Not for Distribution
Beta Version February 2, 2001
Each variable lifetime is assigned a weight that is determined by the number of
times the variable is referenced, how deeply nested (inside loops) the references
are, and how many instructions the lifetime spans. The greater the number of
times the variable is referenced and the more deeply nested the references are,
the higher the assigned priority; the more instructions the lifetime spans, the
lower the assigned priority. The lifetimes are then sorted by priority in descending
order. Finally, attempts are made to fit as many variable lifetimes into as few
machine registers and stack locations as possible. Going through the prioritized
lifetimes list, as many nonoverlapping lifetimes as possible are assigned to the
first register. After going through the entire prioritized list, the allocation process
moves to the next register or stack location. Register and stack space allocation
occur in the following order:
1. Fit integer type objects into data registers until there are no more integer
type objects to be assigned or there are no more data registers to be
allocated.
2. Fit pointer type objects into address registers until there are no more pointer
type objects to be assigned or there are no more address registers to be
allocated.
3. Fit integer type objects into address registers until there are no more integer
type objects to be assigned or there are no more address registers to be
allocated.
4. Fit floating-point type objects into floating-point registers until there are no
more floating-point type objects to be assigned or there are no more
floating-point registers to be allocated.
5. Fit ten-byte objects into ten-byte units on the stack until there are no more
ten-byte objects to be assigned memory locations.
6. Fit eight-byte objects into eight-byte units on the stack until there are no
more eight-byte objects to be assigned memory locations.
7. Fit four-byte objects into four-byte units on the stack until there are no more
four-byte objects to be assigned memory locations.
8. Fit two-byte objects into two-byte units on the stack until there are no more
two-byte objects to be assigned memory locations.
9. Fit one-byte objects into one-byte units on the stack until there are no more
one-byte objects to be assigned memory locations.
The register allocation algorithm described above is extremely powerful and it
has some interesting properties. A variable declared register may not make it
into a register if all of its lifetimes are assigned low priorities during the second
phase of the allocation process, whereas a variable not declared register may
make it into a register if its lifetimes are assigned high priorities. Every variable in
