Patent ID: 9015690
Filing Date: 2015-04-21
Classification: G06F

Abstract:
1. A computer implemented method for loop fusion of non-adjacent loops, the method comprising: building a node tree that represents parent-child relationships illustrating actual in-program-order execution for each node of a computer program, wherein node types in the tree include types which identify a beginning of at least one of an if-region, a loop region, and a basic block region; initializing a first transformation node to be the starting node; and performing a node transformation on the first transformation node and a second transformation node immediately succeeding in-program-order to the first transformation node, wherein a type of transformation is based at least in part on node types of the first and second transformation nodes, wherein the node transformation comprises: when either of the first transformation node or the second transformation node identifies a beginning of an if-region regardless of dependences: if-merging, head duplication, or tail duplication; when each of the first transformation node and the second transformation node identifies a beginning of a loop region: loop fusion; and when the first transformation node and the second transformation node identifies a beginning of a loop region and a basic block region, respectively: code motion; performing loop fusion on a first loop corresponding to a first loop node and on a second loop corresponding to a second loop node, said first and second loops being non-adjacent with an intervening in-program-order control flow instruction comprising an unconditional branch instruction, said performing occurring when: a path length from the first loop node and the second loop node to a same least common predecessor (LCP) node in the node tree is the same; and each node traversed along a path from the first loop node to the LCP, if any, has a same node type as a corresponding node traversed in a path from the second loop node to the LCP.