Patent ID: 6654952
Filing Date: 2003-11-25
Classification: G06F

Abstract:
A method for performing region based optimizations of a program comprised of blocks including:representing each block as a dependence graph, said dependence graph including incoming dangling edges corresponding to uses within the block which have not been previously defined within the block and outgoing dangling edges corresponding to definitions within the block that are live coming out of the block; considering each dependence graph in the context of a control flow graph; reducing a region of dependence graphs by: examining each incoming dangling edge within each block; traversing each path along the control flow graph in reverse, attempting to match each incoming dangling edge with a corresponding outgoing dangling edge, stopping only if a match is found or the top of the region is found, terminating said path if the same block is reached twice; examining each outgoing dangling edge within each block; traversing each path along the control flow graph forward, attempting to match each outgoing dangling edge with a corresponding incoming or outgoing dangling edge, stopping only if an outgoing match is found or the bottom of the region is found, terminating said path if the same block is reached twice; representing the region as a single block, said single block having a dependence graph with incoming dangling edges being any unmatched incoming dangling edge at the top of the region and outgoing dangling edges being any unmatched outgoing dangling edge at the bottom of the region.