TECHNIQUES FOR DETERMINING INSTRUCTION DEPENDENCIES

摘要

One embodiment sets forth a method for efficiently determining memory resource dependencies between instructions included in a software application. For each instruction, a dependency analyzer uses overlapping search techniques to identify one or more overlaps between the memory elements included in the current instruction and the memory elements included in previous instructions. The dependency analyzer then maps objects included in the instructions to a set of partition elements wherein each partition element represents a set of memory elements that are functionally equivalent for dependency analysis. Subsequently, the dependency analyzer uses the set of partition elements to determine memory dependencies between the instructions at the memory element level. Advantageously, the disclosed techniques enable the compiler to retain an acceptable compilation speed while tuning the instruction ordering at a fine-grained memory element level, thereby increasing the speed at which the processor may execute the software application.

主权项

1. A method for incrementally determining instruction dependencies in a software application, the method comprising:
receiving a first instruction included in the software application; identifying a first new object that is included in the first instruction, is associated with a first new set of memory elements, and is not already included in a partition structure that includes a set of disjunt partition elements representing memory element overlaps between objects; incrementally updating the partition structure to include the first new object and the first new set of memory elements; identifying a matching partition element associated with the first new object; performing a look-up operation on the matching partition element to determine an object dependency between the first new object and a previous object included in a previously received instruction; anddetermining an instruction dependency between the first instruction and the previously received instruction based on the object dependency.