Region based optimizations using data dependence graphs

Abstract

Region based optimization may be accomplished by creating dependence graphs for each block and then incrementally computing a single dependence graph for the region. First dependence DAGs are created for each block in the region. This includes defining incoming and outgoing dangling edges for each block. Each dependence DAG is then linked as a control flow graph. Examining of each incoming dangling edge within each block of the region then takes place, with the process traversing each path along the control flow graph in reverse, attempting to match each incoming dangling edge with a corresponding incoming or outgoing dangling edge, stopping only if an outgoing match is found, the same block is examined twice, or the top of the region is found. A similar process takes place for each outgoing dangling edge, traversing each path along the control flow path forward, attempting to match each outgoing dangling edge with a corresponding incoming dangling edge, stopping only if a match is found, the same block is examined twice, or the bottom of the region is found. The region may then be reduced to a single block with incoming dangling edges being any unmatched incoming dangling edges at the top of the region and outgoing dangling edges being any unmatched outgoing dangling edges at the bottom of the region. Optimization may occur during or after this reduction step to improve performance in the program. Nested loops may be handled by building the dependence graph for the inner most loop first and treating it like a dependence DAG for a block when processing the outer loops.