Patent ID: 7155707

Claim:
A method of compiling a computer program from a sequence of computer instructions, the method comprising: reading, in blocks said computer instructions including a plurality of first, set branch, instructions which each identify a target address for a branch and a plurality of associated second, effect branch instructions which each implement a branch to a target address; defining a set of target registers associated with each block for holding target addresses for the set branch instructions in that block; defining as a live range of blocks a set of blocks for which a target address of a particular set branch instruction is in a live state; using said set of target registers and said live range to ensure that target registers holding target addresses in a live state are not available for other uses; for each set branch instruction, allocating the set branch instruction to a respective initial node in a dominator tree, said initial node being the node which contains the effect branch instruction corresponding to the set branch instruction; determining an ancestor node in the dominator tree to which to migrate one or more of the branch instructions based on the live range of blocks so that target registers holding target addresses in a live state are not overwritten when the computer instructions are executed; and migrating one or more said branch instruction to the ancestor node.