초록 ▼

This patent describes a method of compiling a computer program from a sequence of 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 b

This patent describes a method of compiling a computer program from a sequence of 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. The method comprising the steps of: reading the computer instructions in blocks; allocating each set branch instruction to an initial node in a dominator tree, the initial node being the node which contains the corresponding effect branch instruction; for the first determining the effect of migrating set branch instructions to each of a set of ancestor nodes in the dominator tree based on a performance cost parameter and selecting an ancestor node with the best performance cost parameter; locating said set branch instruction at the selected ancestor node. Repeating the determining and locating steps for each of the set branch instructions

대표청구항 ▼

The invention claimed is: 1. A method of compiling a computer program from a sequence of computer instructions, the method comprising; a) 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 plu

The invention claimed is: 1. A method of compiling a computer program from a sequence of computer instructions, the method comprising; a) 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; b) allocating each set branch instruction to an initial node in a dominator tree, said initial node being the node which contains the corresponding effect branch instruction; c) determining the effect of migrating set branch instructions to each of a set of ancestor nodes in the dominator tree based on a performance cost parameter and selecting an ancestor node with the best performance cost parameter; d) locating said set branch instruction at the ancestor node determined by step c); and e) repeating steps c) and d) for said plurality of set branch instructions wherein prior to step c), a priority list is formed of set branch instructions arranged in order of priority, based on their frequency of execution in a computer system; and where steps c) and d) are repeated on the set branch instructions in their order of priority. 2. A method of compiling a computer program from a sequence of computer instructions, the method comprising: a) 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 ranch instructions which each implement a ranch to a target address; b) allocating each set branch instruction to an initial node in a dominator tree, said initial node being the node which contains the corresponding effect branch instruction; c) determining the effect of migrating set branch instructions to each of a set of ancestor nodes in the dominator tree based on a performance cost parameter and selecting an ancestor node with the best performance cost parameter; d) locating said set branch instruction at the ancestor node determined by step c); and e) repeating steps c) and d) for said plurality of set branch instructions; wherein the performance cost parameter is the pitch of the set branch instruction multiplied by the execution frequency of the block at the ancestor node under determination. 3. A method according to claim 2, wherein the performance cost parameter is modified by adding a stall increment which is the number of stall cycles multiplied by the execution frequency of the block at the ancestor node under determination. 4. A method of operating a computer system to compile a computer program from a sequence of computer instructions, the method comprising: executing a dominator tree constructor function in the computer system to read, in block, said computer instructions including a plurality of first set branch instructions which each identify a target address for a branch and a plurality of second, effect branch instructions which each implement a branch to the target address specified in the associated set branch instruction, and to allocate each set branch instruction to an initial node in a dominator tree, said initial node being the node which contains the corresponding effect branch instruction; executing a determiner function which determines the effect of migrating a set branch instruction to each of a set of ancestor nodes in the dominator tree based on a performance cost parameter; comparing said cost parameters to determine the optimum location for the set branch instruction; and outputting a program code sequence including said set branch instructions located as determined by the determiner function. 5. A method according to claim 4, wherein the comparing step comprises holding a best-so-far candidate after each determination. 6. A method according to claim 4, wherein the comparing step comprises holding said cost parameter in a value table. 7. A method according to claim 4, which comprises executing a lister function which lists the set branch instructions in order of priority, based on their frequency of execution. 8. A method according to claim 4, wherein the performance cost parameter is the pitch of the set branch instruction multiplied by the execution frequency of the block at the ancestor node under determination. 9. A compiler, tangibly embodied on a computer readable medium, for compiling a computer program from a sequence of compute instructions, the compiler comprising: a dominator tree constructor for 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 implement a branch to the target address specified in the associated set branch instruction and for allocating each set branch instruction to an initial node in a dominator tree, said initial node being located in the block which contains the corresponding effect branch instruction; a determiner for determining the effect of migrating a set branch instruction to each of a set of ancestor nodes in the dominator tree based on a performance cost parameter; a cost heuristic evaluator which determines said performance cost parameter for each possible migration; and means for determining the effect of each potential migration to locate the optimal position for the set branch instruction under determination. 10. A compiler according to claim 9, which comprises a value table for holding benefit values determined by said cost heuristic circuit. 11. A compiler according to claim 9, which includes a lister for forming a priority list of set branch instructions, based on their frequency of execution in a computer system. 12. A compiler according to claim 9, wherein the cost heuristic circuit operates to determine the performance cost parameter as the pitch of the branch set-up instruction multiplied by the execution frequency of the block at the ancestor node under determination.