Interactive instruction scheduling and block ordering
AssigneeIntle Corporation
InventorsChristopher M. McKinsey, Jayashankar Bharadwaj
Life of this patent
Estimating the term…
Abstract
In some embodiments, the invention includes a method of compiling instructions of a program. The method includes receiving instructions for code motion and controlling the code motion while interacting with block ordering. The code motion may be done as part of various activities including instruction scheduling, partial redundancy elimination, and loop invariant removal. The scheduling may involve making an assessment of the cost of scheduling an instruction that takes into account generation and/or elimination of branches due to resulting block order update and determining whether to make the code motion based on the cost. Instruction scheduling may involve regeneration of predicate expressions to invert conditional branches.
Claims23
A method of compiling instructions of a program, comprising:
- receiving instructions for code motion;
- and
- controlling the code motion while interacting with block ordering, wherein the controlling includes:
- (a) establishing a physical order before the code motion, wherein the blocks include populated blocks;
- (b) performing code motion for one of the instructions;
- (c) if the step of code motion in (b) causes (1) a partially empty block to become populated, (2) the creation and population of a new block, or (3) a populated block to be emptied or made partially empty, then the physical ordering of blocks is updated, and
- (d) repeating (b) and (c) until the code motion for the instructions is completed.
An article comprising:
- a computer readable medium having instructions thereon which when executed cause a computer to perform the following method:
- receiving instructions for code motion;
- and
- controlling the code motion while interacting with block ordering, wherein the controlling includes:
- (a) establishing a physical order before the code motion, wherein the blocks include populated blocks;
- (b) performing code motion for one of the instructions;
- (c) if the step of code motion in (b) causes (1) a partially empty block to become populated, (2) the creation and population of a new block, or (3) a populated block to be emptied or made partially empty, then the physical ordering of blocks is updated, and
- (d) repeating (b) and (c) until the code motion for the instructions is completed.
A system comprising:
- a computer including memory, wherein the memory that includes instructions that when executed cause the computer to perform the following method:
- receiving instructions for code motion;
- and
- controlling the code motion while interacting with block ordering, wherein the controlling includes:
- (a) establishing a physical order before the code motion, wherein the blocks include populated blocks;
- (b) performing code motion for one of the instructions;
- (c) if the step of code motion in (b) causes (1) a partially empty block to become populated, (2) the creation and population of a new block, or (3) a populated block to be emptied or made partially empty, then the physical ordering of blocks is updated, and
- (d) repeating (b) and (c) until the code motion for the instructions is completed.
An article comprising:
- a machine readable medium having a program thereon which is created by a compiler that performs the following method:
- receiving instructions for code motion;
- and
- controlling the code motion while interacting with block ordering, wherein the controlling includes:
- (a) establishing a physical order before the code motion, wherein the blocks include populated blocks;
- (b) performing code motion for one of the instructions;
- (c) if the step of code motion in (b) causes (1) a partially empty block to become populated, (2) the creation and population of a new block, or (3) a populated block to be emptied or made partially empty, then the physical ordering of blocks is updated, and
- (d) repeating (b) and (c) until the code motion for the instructions is completed.
Dependencies are inferred from the claim text.