Method for representing scalar data dependences for an optimizing compiler

• US 5,107,418 A
• Filed: 08/23/1990
• Issued: 04/21/1992
• Est. Priority Date: 06/11/1990
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Supercomputer Systems Limited Partnership
• Inventors: Cox, David M., Cramer, Timothy J.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US07/571,503
• Time in Patent Office: 607 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/700
• US Class Current: 717/155
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding

Abstract

A method for representing scalar data dependencies for an optimizing compiler wherein a global scalar data dependence graph is created to represent all of the scalar objects in an entire program. The scalar data dependencies are represented as three chains: a use-definition chain (ud); a definition-use chain (du) or a definition-definition chain (dd), and is created for the entire program and is maintained during the entire compilation or assembly of the program. The method for determining scalar data dependences for the entire program starts by analyzing the scalar data dependences within each basic block, in a single pass, processes all definitions and uses of all non-array data objects in the basic block, including simple variables and complex data objects such as records, unions, pointers and procedure calls in the presence of aliasing. From these objects, information is collected, such as whether the data objects are upwardly or downwardly exposed, pointers, pointer aliases, aggregate objects, array objects, uses, definitions; whether they are calls, indirect uses, or indirect definitions.

Claims

1. A method for constructing a global scalar data dependence graph for an optimizing compiler, the scalar data dependence graph representing relationships among scalar variables in one or more basic blocks that comprises an intermediate representation of a source code program to be executed on a computer processing system, the method of constructing the global scalar data dependence graph comprising the steps of:

(a) performing a prepass on the intermediate representation of the source code program to process symbol information and to process expression information for all of the basic blocks;

(b) building a local data dependence graph for each basic block, the local data dependence graph including one or more dependence nodes;

(c) generating a KILL Set for each dependence node for each basic block;

(d) generating an IN/OUT Set for each dependence node for each basic block; and

(e) connecting all of the local data dependence graphs together to form a global scalar data dependence graph.

2. The method of claim 1 wherein step (b) is performed in a single pass through the intermediate representation of the source code program.

3. The method of claim 1 wherein the dependence node is comprised of a data structure defining a definition-use chain, a use-definition chain and a definition-definition chain.

4. the method of claim 1 wherein the dependence node is capable of representing calls, simple, equivalenced, and aggregate variables.

5. The method of claim 1 wherein steps (b) through (e) further comprise the step of performing graph reduction by using conservative estimates for side effects calls and pointer dereferences.

6. The method of claim 1 wherein other information vital to subsequent optimizations is stored in the global scalar data dependence graph, including clear and exposed use bit vectors.

7. The method of claim 1 wherein the definition of a KILL Set in step (c);

is expanded to include all definitions that are not generated by the current basic block.