1. intermediate code is basic blocks connected with edges. Each block has a bit vector the size of which is the number of local variables. If a variable is referenced in a basic block, the corresponding bit is set.
2. basic blocks are sorted in depth first order
3. variables are sorted by "weight", which is incremented for each use, incremented by 10 for each use in a loop, by 100 for each use in a nested loop, etc.
4. code is generated with nothing assigned to registers, but registers used are marked in a bit vector, one per basic block
5. Now the register allocator allocates registers unused in a basic block to variables that are used in the basic block, in the order of the weights
6. Assigning variables to registers often means less registers are used for code generation, so more registers become available, so the process is done again until no more registers can be assigned
There are more nuances, such as variables passed to a function via registers, which introduces complications - should it stay in a register, or be moved into memory? But dealing with that is why I get paid the Big Bucks.
1. intermediate code is basic blocks connected with edges. Each block has a bit vector the size of which is the number of local variables. If a variable is referenced in a basic block, the corresponding bit is set.
2. basic blocks are sorted in depth first order
3. variables are sorted by "weight", which is incremented for each use, incremented by 10 for each use in a loop, by 100 for each use in a nested loop, etc.
4. code is generated with nothing assigned to registers, but registers used are marked in a bit vector, one per basic block
5. Now the register allocator allocates registers unused in a basic block to variables that are used in the basic block, in the order of the weights
6. Assigning variables to registers often means less registers are used for code generation, so more registers become available, so the process is done again until no more registers can be assigned
There are more nuances, such as variables passed to a function via registers, which introduces complications - should it stay in a register, or be moved into memory? But dealing with that is why I get paid the Big Bucks.