Fast, Combined Forwards-Backwards Pass Global Optimization Framework for Dynamic Compilers

Abstract

The various aspects provide a dynamic compilation framework that includes a machine-independent optimization module operating on a computing device and methods for optimizing code with the machine-independent optimization module using a single, combined-forwards-backwards pass of the code. In the various aspects, the machine-independent optimization module may generate a graph of nodes from the IR, optimize nodes in the graph using forwards and backwards optimizations, and propagating the forwards and backwards optimizations to nodes in a bounded subgraph recognized or defined based on the position of the node currently being optimized. In the various aspects, the machine-independent optimization module may optimize the graph by performing forwards and/or backwards optimizations during a single pass through the graph, thereby achieving an effective degree of optimization and shorter overall compile times. Thus, the various aspects may provide a global optimization framework for dynamic compilers that is faster and more efficient than existing solutions.

What is claimed is: 
     
         1 . A method of optimizing an intermediate representation of source code, comprising:
 generating a data dependence graph from the intermediate representation, wherein the data dependence graph comprises a plurality of nodes;   selecting a node in the data dependence graph;   applying an optimization to the selected node;   recognizing a bounded subgraph of the data dependence graph based on the selected node;   initializing a subgraph node list;   adding successor and predecessor nodes of the selected node in the bounded subgraph to the subgraph node list;   choosing a node from the subgraph node list;   applying the optimization to the chosen node;   determining whether the chosen node is an entry node or an exit node;   adding successor and predecessor nodes of the chosen node to the subgraph node list unless it is determined that the chosen node is the entry node or the exit node; and   removing the chosen node from the subgraph node list.   
     
     
         2 . The method of  claim 1 , wherein recognizing a bounded subgraph of the data dependence graph based on the selected node comprises:
 identifying the entry node, wherein the entry node is a predecessor node of the selected node;   scanning through the data dependence graph;   determining whether the exit node is detected, wherein the exit node is a successor node of the selected node; and   defining the bounded subgraph based on the entry node and the exit node in response to determining that the exit node is detected.   
     
     
         3 . The method of  claim 1 , wherein selecting a node in the data dependence graph comprises:
 initializing a ready list;   adding a start node to the ready list;   selecting a node in the ready list; and   incrementing a visitation counter of the selected node.   
     
     
         4 . The method of  claim 3 , wherein selecting a node in the ready list comprises:
 determining whether there is a control flow node in the ready list;   selecting the control flow node in response to determining that a control flow node is in the ready list; and   selecting a data node in response to determining that there are no control flow nodes in the ready list.   
     
     
         5 . The method of  claim 3 , further comprising:
 for each successor of the selected node, determining whether predecessors of a successor node have all been visited;   adding the successor node to the ready list in response to determining that the successor node's predecessors have all been visited; and   removing the selected node from the ready list.   
     
     
         6 . The method of  claim 3 , wherein applying an optimization to the selected node comprises determining whether the selected node has been visited more than twice, and wherein the method further comprises:
 determining whether to apply a forwards optimization on the selected node in response to determining that the selected node has not been visited more than twice;   applying the forwards optimization on the selected node in response to determining to apply the forwards optimization on the selected node;   determining whether to apply a backwards optimization on the selected node in response to determining that the selected node has not been visited more than twice; and   applying the backwards optimization on the selected node in response to determining to apply the backwards optimization.   
     
     
         7 . The method of  claim 6 , further comprising:
 choosing a successor node from the subgraph node list;   incrementing a visitation counter of the chosen successor node;   determining whether the chosen successor node has been visited more than twice;   determining whether to apply the forwards optimization on the chosen successor node in response to determining that the chosen successor node has not been visited twice;   applying the forwards optimization on the chosen successor node in response to determining to apply the forwards optimization;   determining whether the chosen successor node is the exit node;   adding successors of the chosen successor node to the subgraph node list unless it is determined that the chosen successor node is the exit node or it is determined not to apply the forwards optimization on the chosen successor node; and   removing the chosen successor node from the subgraph node list.   
     
     
         8 . The method of  claim 6 , further comprising:
 choosing a predecessor node from the subgraph node list;   incrementing a visitation counter of the chosen predecessor node;   determining whether the chosen predecessor node has been visited more than twice;   determining whether to apply the backwards optimization on the chosen predecessor node in response to determining that the chosen predecessor node has not been visited twice;   applying the backwards optimization on the chosen predecessor node in response to determining to apply the backwards optimization;   determining whether the chosen predecessor node is the entry node;   adding a predecessor of the chosen predecessor node to the subgraph node list unless it is determined that the chosen predecessor node is the entry node or it is determined not to apply the backwards optimization on the chosen predecessor node; and   removing the chosen predecessor node from the subgraph node list.   
     
     
         9 . The method of  claim 3 , further comprising:
 determining whether the ready list is empty;   determining whether all nodes in the data dependence graph have been visited in response to determining that the ready list is empty; and   adding an unvisited node to the ready list in response to determining that all nodes in the data dependence graph have not been visited.   
     
     
         10 . The method of  claim 1 , further comprising:
 determining whether the subgraph node list is empty; and   selecting another node in the subgraph node list in response to determining that the subgraph node list is not empty.   
     
     
         11 . A computing device, comprising:
 a memory; and   a processor coupled to the memory, wherein the processor is configured with processor-executable instructions to perform operations comprising:
 generating a data dependence graph from an intermediate representation of source code, wherein the data dependence graph comprises a plurality of nodes; 
 selecting a node in the data dependence graph; 
 applying an optimization to the selected node; 
 recognizing a bounded subgraph of the data dependence graph based on the selected node; 
 initializing a subgraph node list; 
 adding successor and predecessor nodes of the selected node in the bounded subgraph to the subgraph node list; 
 choosing a node from the subgraph node list; 
 applying the optimization to the chosen node; 
 determining whether the chosen node is an entry node or an exit node; 
 adding successor and predecessor nodes of the chosen node to the subgraph node list unless it is determined that the chosen node is the entry node or the exit node; and 
 removing the chosen node from the subgraph node list. 
   
     
     
         12 . The computing device of  claim 11 , wherein the processor is configured with processor-executable instructions to perform operations such that recognizing a bounded subgraph of the data dependence graph based on the selected node comprises:
 identifying the entry node, wherein the entry node is a predecessor node of the selected node;   scanning through the data dependence graph;   determining whether the exit node is detected, wherein the exit node is a successor node of the selected node; and   defining the bounded subgraph based on the entry node and the exit node in response to determining that the exit node is detected.   
     
     
         13 . The computing device of  claim 11 , wherein the processor is configured with processor-executable instructions to perform operations such that selecting a node in the data dependence graph comprises:
 initializing a ready list;   adding a start node to the ready list;   selecting a node in the ready list; and   incrementing a visitation counter of the selected node.   
     
     
         14 . The computing device of  claim 13 , wherein the processor is configured with processor-executable instructions to perform operations such that selecting a node in the ready list comprises:
 determining whether there is a control flow node in the ready list;   selecting the control flow node in response to determining that a control flow node is in the ready list; and   selecting a data node in response to determining that there are no control flow nodes in the ready list.   
     
     
         15 . The computing device of  claim 13 , wherein the processor is configured with processor-executable instructions to perform operations further comprising:
 for each successor of the selected node, determining whether predecessors of a successor node have all been visited;   adding the successor node to the ready list in response to determining that the successor node's predecessors have all been visited; and   removing the selected node from the ready list.   
     
     
         16 . The computing device of  claim 13 , wherein the processor is configured with processor-executable instructions to perform operations such that applying an optimization to the selected node comprises determining whether the selected node has been visited more than twice, and wherein the processor is configured with processor-executable instructions to perform operations further comprising:
 determining whether to apply a forwards optimization on the selected node in response to determining that the selected node has not been visited more than twice;   applying the forwards optimization on the selected node in response to determining to apply the forwards optimization on the selected node;   determining whether to apply a backwards optimization on the selected node in response to determining that the selected node has not been visited more than twice; and   applying the backwards optimization on the selected node in response to determining to apply the backwards optimization.   
     
     
         17 . The computing device of  claim 16 , wherein the processor is configured with processor-executable instructions to perform operations further comprising:
 choosing a successor node from the subgraph node list;   incrementing a visitation counter of the chosen successor node;   determining whether the chosen successor node has been visited more than twice;   determining whether to apply the forwards optimization on the chosen successor node in response to determining that the chosen successor node has not been visited twice;   applying the forwards optimization on the chosen successor node in response to determining to apply the forwards optimization;   determining whether the chosen successor node is the exit node;   adding successors of the chosen successor node to the subgraph node list unless it is determined that the chosen successor node is the exit node or it is determined not to apply the forwards optimization on the chosen successor node; and   removing the chosen successor node from the subgraph node list.   
     
     
         18 . The computing device of  claim 16 , wherein the processor is configured with processor-executable instructions to perform operations further comprising:
 choosing a predecessor node from the subgraph node list;   incrementing a visitation counter of the chosen predecessor node;   determining whether the chosen predecessor node has been visited more than twice;   determining whether to apply the backwards optimization on the chosen predecessor node in response to determining that the chosen predecessor node has not been visited twice;   applying the backwards optimization on the chosen predecessor node in response to determining to apply the backwards optimization;   determining whether the chosen predecessor node is the entry node;   adding a predecessor of the chosen predecessor node to the subgraph node list unless it is determined that the chosen predecessor node is the entry node or it is determined not to apply the backwards optimization on the chosen predecessor node; and   removing the chosen predecessor node from the subgraph node list.   
     
     
         19 . The computing device of  claim 13 , wherein the processor is configured with processor-executable instructions to perform operations further comprising:
 determining whether the ready list is empty;   determining whether all nodes in the data dependence graph have been visited in response to determining that the ready list is empty; and   adding an unvisited node to the ready list in response to determining that all nodes in the data dependence graph have not been visited.   
     
     
         20 . A non-transitory processor-readable storage medium having stored thereon processor-executable software instructions configured to cause a processor of a computing device to perform operations for optimizing an intermediate representation of source code, the operations comprising:
 generating a data dependence graph from the intermediate representation, wherein the data dependence graph comprises a plurality of nodes;   selecting a node in the data dependence graph;   applying an optimization to the selected node;   recognizing a bounded subgraph of the data dependence graph based on the selected node;   initializing a subgraph node list;   adding successor and predecessor nodes of the selected node in the bounded subgraph to the subgraph node list;   choosing a node from the subgraph node list;   applying the optimization to the chosen node;   determining whether the chosen node is an entry node or an exit node;   adding successor and predecessor nodes of the chosen node to the subgraph node list unless it is determined that the chosen node is the entry node or the exit node; and   removing the chosen node from the subgraph node list.