Techniques for determining instruction dependencies

Abstract

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.