Global control flow treatment of predicated code

• US 5,937,195 A
• Filed: 11/27/1996
• Issued: 08/10/1999
• Est. Priority Date: 11/27/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Ju, Dz-ching, Gillies, David M.
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): DAM, TUAN QUANG
• Application Number:
  US08/756,600
• Time in Patent Office: 986 Days
• Field of Search: 395/701, 395/703, 395/704, 395/705, 395/706, 395/709, 395/377, 712/201, 712/216
• US Class Current: 717/156
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis

Abstract

The relationships among predicates are tracked globally by uniformly treating both control flow and explicit predicates by mapping them to a single connected partition graph. This allows for the analysis of predicate relations based on the scope of an entire procedure. This predicate analysis can be invoked by various phases of compiler optimization without being constrained by an incremental update of any persistent data structures.

Claims

1. A computer system for processing predicated code having a plurality of predicates, the system comprising:

means for determining a domain for each predicate;

means for partitioning each determined domain into disjoint subsets; and

means for constructing a partition graph from each of the partitioned domains to capture global relations of the predicates, wherein the partition graph is used in data flow analysis of the predicated code during compilation of the predicated code.

2. The system of claim 1, wherein the means for partitioning each predicate comprises:

means for partitioning control predicates.

3. The system of claim 2, wherein the means for partitioning control predicates comprises:

means for creating a virtual node on each critical edge and on each back edge, so as to split the critical and back edges;

means for ascertaining equivalent control nodes;

means for assigning the same predicate to each set of equivalent control nodes; and

means for forming partitions in predicates assigned to nodes with merge points and switch points.

4. The system of claim 3, wherein the means for partitioning control predicates further comprises:

means for forming partitions in an immediate dominator to a non-start node that does not have a predecessor node.

5. The system of claim 3, wherein the means for partitioning control predicates further comprises:

means for assigning predicate p0 to a start node as its control predicate.

6. The system of claim 1, wherein the means for partitioning each predicate comprises:

means for partitioning materialized predicates.

7. The system of claim 6, wherein the means for partitioning materialized predicates comprises:

means for forming partitions in predicates assigned to nodes with compare instructions.

8. The system of claim 6, wherein the means for partitioning materialized predicates comprises:

means for forming partitions in predicates assigned to nodes with definitional instructions that define the predicates.

9. The system of claim 1, wherein the predicated code is divided into basic blocks, the system further comprising:

means for determining whether two blocks are disjoint.

10. The system of claim 1, wherein the predicated code is divided into basic blocks, the system further comprising:

means for determining whether one block is a superset of another block.

11. The system of claim 1, wherein the predicated code is divided into basic blocks, the system further comprising:

means for determining whether two blocks are complementary to each other.

12. The system of claim 1, further comprising:

means for performing if-conversion on the control flow graph code to form predicates for each instruction in the graph code.

13. The system of claim 12, wherein:

the means for performing if conversion acts before the means for partitioning each domain.

14. The system of claim 12, wherein:

the means for performing if conversion acts after the means for constructing a partition graph.

15. A system of claim 1, wherein the domain comprises all traces required to completely execute a basic block of predicated code, whereby a trace is a set of instructions that are guarded by a particular predicate P, such that all instructions of the trace are executed when P is true.

16. The system of claim 1, wherein the predicated code is divided into basic blocks, the system further comprising:

means for creating control predicates for the basic blocks.

17. A system of claim 1, wherein

the processing of predicate code can be invoked by various phases of compiler optimization without being constrained by an incremental update of any persistent data structures.

18. A computer system for processing code divided into a plurality of basic blocks, the system comprising:

means for determining a domain for each block;

means for partitioning each determined domain into disjoint subsets; and

means for constructing a partition graph from each of the partitioned domains to capture global relations of the blocks, wherein the partition graph is used in data flow analysis of the code during compilation of the code.

19. The system of claim 18 further comprising:

means for determining whether two blocks are disjoint.

20. The system of claim 18 further comprising:

means for determining whether one block is a superset of another block.

21. The system of claim 18 further comprising:

means for determining whether two blocks are complementary to each other.

22. A computer implemented method for processing predicated code having a plurality of predicates, the method comprising the steps of:

determining a domain for each predicate;

partitioning each domain of the predicates into disjoint subsets;

constructing a partition graph to capture global relations of the predicates; and

utilizing the partition graph in data flow analysis of the predicated code during compilation of the predicated code.

23. The method of claim 22, wherein the step of partitioning each predicate comprises the step of:

partitioning control predicates.

24. The method of claim 23, wherein the step of partitioning control predicates comprises the steps of:

creating a virtual node on each critical edge and on each back edge, so as to split the critical and back edges;

ascertaining equivalent control nodes;

assigning the same predicate to each set of equivalent control nodes; and

forming partitions in predicates assigned to nodes with merge points and switch points.

25. The method of claim 24, wherein the step of partitioning control predicates further comprises the step of:

forming partitions in an immediate dominator to a non-start node that does not have a predecessor node.

26. The method of claim 24, wherein the step of partitioning control predicates further comprises the step of:

assigning predicate p0 to a start node as its control predicate.

27. The method of claim 22, wherein the step of partitioning each predicate comprises the step of:

partitioning materialized predicates.

28. The method of claim 27, wherein the step of partitioning materialized predicates comprises the step of:

forming partitions in predicates assigned to nodes with compare instructions.

29. The method of claim 27, wherein the step of partitioning materialized predicates comprises the step of:

forming partitions in predicates assigned to nodes with definitional instructions that define the predicates.

30. The method of claim 22, wherein the predicated code is divided into basic blocks, the method further comprising the step of:

determining whether two blocks are disjoint.

31. The method of claim 22, wherein the predicated code is divided into basic blocks, the method further comprising the step of:

determining whether one block is a superset of another block.

32. The method of claim 22, wherein the predicated code is divided into basic blocks, the method further comprising the step of:

determining whether two blocks are complementary to each other.

33. The method of claim 22, further comprising the step of:

performing if-conversion on the control flow graph code to form predicates for each instruction in the graph code.

34. The method of claim 33, wherein:

the step of performing if conversion is performed before the step of partitioning each domain.

35. The method of claim 33, wherein:

the step of performing if conversion is performed after the step of constructing a partition graph.

36. The method of claim 22, wherein the predicated code is divided into basic blocks, the method further comprising the step of:

creating control predicates for the basic blocks.

37. A computer system for processing predicated code having a plurality of predicates to construct a partition graph that allows for globally analyzing predicate relations, the system comprising:

means for determining a domain for each predicate;

means for partitioning each determined domain into disjoint subsets; and

means for constructing the partition graph from each of the partitioned domains to capture global relations of the predicates, wherein the partition graph is used in data flow analysis of the predicated code during compilation of the predicated code.

38. The system of claim 37, wherein the means for partitioning each predicate comprises:

means for partitioning control predicates; and

means for partitioning materialized predicates.

39. The system of claim 38, wherein the means for partitioning control predicates comprises:

means for creating a virtual node on each critical edge and on each back edge, so as to split the critical and back edges;

means for ascertaining equivalent control nodes;

means for assigning the same predicate to each set of equivalent control nodes;

means for forming partitions in predicates assigned to nodes with merge points and switch points;

means for forming partitions in an immediate dominator to a non-start node that does not have a predecessor node; and

means for assigning predicate p0 to a start node as its control predicate.

40. The system of claim 38, wherein the means for partitioning materialized predicates comprises:

means for forming partitions in predicates assigned to nodes with compare instructions.