INCREMENTAL INTERPROCEDURAL DATAFLOW ANALYSIS DURING COMPILATION

摘要

Instead of performing local dataflow analyses on all procedures during a multi-file optimized code generation, those dataflow analyses are done only on a generally much smaller set of procedures that were actually impacted by source code edits. Incremental inter-procedural dataflow analysis (IIPDA) code identifies a set of procedures to be recompiled due to impact from one or more edits and does local dataflow analyses only on them. Results of the incremental approach for use in generating optimized code match the results of a more expensive exhaustive interprocedural dataflow analysis of all procedures, even when call graph structure has been changed by the edits. The impacted procedures are identified based on which procedures were edited, dataflow values, intermediate language representations, and a portion of the call graph.

主权项

1. A process to facilitate compilation throughput and programmer productivity for a program which includes a set AS containing all procedures called in the program, the process comprising:
(A) initializing a set IS of impacted procedure nodes by including within IS each member of a set BS of basis procedure nodes and marking each member of IS as unvisited, each node being a node in a call graph of the program, procedures represented by nodes of IS being a smaller set of procedures than AS, procedures represented by nodes of BS also being a smaller set of procedures than AS; (B) for each unvisited member node Mem of IS, performing the following step C in a designated propagation order in the call graph: (C) for each target node of Mem, performing the following steps D and I through K: (D) for each source node of the target node when the target node represents a non-recursive procedure, performing the following steps E through H: (E) loading a previous dataflow value for the source node when the source node is unvisited and represents a non-recursive procedure; (F) reading a current intermediate language representation of the source node's procedure; (G) running a local dataflow analysis for the source node using the source node's dataflow value and current intermediate language representation, thereby producing a dataflow result of the source node; (H) merging the source node dataflow result, in the designated propagation order, into a dataflow value for the target node and marking the source node visited; (I) finalizing the merged dataflow of the target node, using a conservative dataflow when the target node represents a recursive procedure; (J) comparing the finalized dataflow of the target node with a previous dataflow of the target node from a point prior to step A; (K) adding the target node to the set IS of impacted procedures when the comparing step J detects a difference in the finalized dataflow of the target node and the previous dataflow of the target node; and (L) presenting the procedures represented by nodes of the set IS as a set of one or more procedures which is smaller than AS and which are subject to recompilation due to direct or indirect impact by at least one edit.