Mechanism for ordering lists of local variables associated with a plurality of code blocks
A compilation mechanism is disclosed for facilitating the keeping of local variables in the same hardware registers across multiple code blocks. In one implementation, each code block has a list of local variables associated therewith. This list of local variables represents the local variables that should be loaded into registers prior to entering a code block. For multiple code blocks, the various lists may have local variables in common. In one implementation, the mechanism orders the local variables in the various lists in such a manner that, as much as possible, the same local variables are placed in the same slots of the various lists. By doing so, the mechanism minimizes the movement of local variables from register to register when going from code block to code block.
1. A machine readable medium comprising instructions, which when executed by one or more processors, cause the one or more processors to perform the following:
(a) selecting one of a plurality of code blocks to be a current code block;
(b) accessing a current list of local variables, wherein the current list is associated with the current code block;
(c) determining a successor code block for the current code block, wherein the current code block falls through or branches to the successor code block;
(d) accessing a successor list of local variables, wherein the successor list is associated with the successor code block;
(e) selecting one of the local variables in the current list;
(f) determining whether the selected local variable is also in the successor list;
(g) determining whether the selected local variable has been ordered into a particular slot in the successor list when the selected local variable is in the successor list;
(h) selecting a desired slot, when the selected local variable has not been ordered into a particular slot in the successor list;
(i) ordering the selected local variable into the desired slot in the successor list; and
(j) ordering the selected local variable into the same desired slot in the current list, when the selected local variable has not already been ordered into the desired slot in the current list.
2. The machine readable medium of claim 1 , further comprising instructions for causing one or more processors to perform the following:
(k) when the selected local variable has been ordered into a particular slot in the successor list, ordering the selected local variable into the same particular slot in the current list, when the selected local variable has not already been ordered into the particular slot in the current list.
3. The machine readable medium of claim 2 , further comprising instructions for causing one or more processors to perform the following:
(l) selecting another local variable in the current list to be the selected local variable; and
(m) repeating (f) through (l) until each of the local variables in the current list has been selected.
4. The machine readable medium of claim 3 , further comprising instructions for causing one or more processors to perform the following:
(n) selecting another one of the plurality of code blocks to be the current code block; and
(o) repeating (b) through (n) until each of the code blocks in the plurality of code blocks has been selected.
5. The machine readable medium of claim 1 , wherein selecting a desired slot comprises:
determining whether the selected local variable has been ordered into a certain slot in the current list; and
when the selected local variable has been ordered into a certain slot in the current list, selecting the certain slot as the desired slot.
6. The machine readable medium of claim 1 , wherein selecting a desired slot comprises:
determining a set of mutually unordered slots, wherein the set of mutually unordered slots comprises slots that are currently unordered in both the current list and the successor list; and
selecting one of the mutually unordered slots as the desired slot.
7. The machine readable medium of claim 6 , wherein the current code block is part of a loop, and wherein selecting one of the mutually unordered slots as the desired slot comprises:
accessing a target list of local variables, wherein the target list is associated with a code block that is a backwards branch target in the loop; and
determining whether any of the mutually unordered slots have been ordered in the target list with another local variable.
8. The machine readable medium of claim 6 , wherein the current code block is part of a loop, and wherein selecting one of the mutually unordered slots as the desired slot comprises:
(p) accessing a target list of local variables, wherein the target list is associated with a code block that is a backwards branch target in the loop;
(q) selecting one of the mutually unordered slots as a current unordered slot;
(r) determining whether the current unordered slot has been ordered in the target list with another local variable;
(s) assigning a desirability factor to the current unordered slot, wherein a less favorable desirability factor is assigned to the current unordered slot when the current unordered slot has been ordered in the target list with another local variable;
(t) selecting another of the mutually unordered slots as the current unordered slot;
(u) repeating (r) through (t) until all of the mutually unordered slots have been selected; and
(v) selecting a mutually unordered slot with the best desirability factor as the desired slot.
9. The machine readable medium of claim 6 , wherein the current code block is part of a loop, and wherein selecting one of the mutually unordered slots as the desired slot comprises:
accessing a target list of local variables, wherein the target list is associated with a code block that is a backwards branch target in the loop; and
determining whether any of the mutually unordered slots have been ordered in the target list with the selected local variable.
10. The machine readable medium of claim 6 , wherein the current code block is part of a loop, and wherein selecting one of the mutually unordered slots as the desired slot comprises:
(p) accessing a target list of local variables, wherein the target list is associated with a code block that is a backwards branch target in the loop;
(q) selecting one of the mutually unordered slots as a current unordered slot;
(r) determining whether the current unordered slot has been ordered in the target list with the selected local variable;
(s) assigning a desirability factor to the current unordered slot, wherein a more favorable desirability factor is assigned to the current unordered slot when the current unordered slot has been ordered in the target list with the selected local variable;
(t) selecting another of the mutually unordered slots as the current unordered slot;
(u) repeating (r) through (t) until all of the mutually unordered slots have been selected; and
(v) selecting a mutually unordered slot with the best desirability factor as the desired slot.
11. The machine readable medium of claim 6 , wherein the current code block has a second successor code block, and wherein selecting one of the mutually unordered slots as the desired slot comprises:
accessing a second successor list of local variables, wherein the second successor list is associated with the second successor code block; and
determining whether any of the mutually unordered slots have been ordered in the second successor list with another local variable.
12. The machine readable medium of claim 6 , wherein the current code block has a second successor code block, and wherein selecting one of the mutually unordered slots as the desired slot comprises:
accessing a second successor list of local variables, wherein the second successor list is associated with the second successor code block; and
determining whether any of the mutually unordered slots have been ordered in the second successor list with the selected local variable.