Patent ID: 7069555

Claim:
A computerized method for scheduling one or more instructions within one or more instruction blocks, the method comprising: analyzing a control flow and a data flow of the one or more instructions to determine registers accessed by the one or more instructions; constructing a region tree having one or more regions, each region containing a subset of the one or more instruction blocks; and, for each region in the region tree, performing the tasks of: creating a dependency graph of the subset of the one or more instruction blocks based on the registers accessed by the one or more instructions comprised in the subset of the one or more instruction blocks; and, scheduling each block in the subset of the one or more instruction blocks, wherein scheduling each block in the subset of the one or more instruction blocks comprises: constructing a ready list for holding ready-to-schedule instructions; obtaining a ready-to-schedule instruction from the ready list; scanning the ready list for one or more identical instructions to the ready-to-schedule instruction; and merging the one or more identical instructions into the ready-to-schedule instruction.