1

Interprocedural Control DependenceJames Ezick and Kiri Wagstaff CS 612 May 4, 1999

2

OutlineMotivation Some essential terms Constructing the interprocedural postdominance relation Answering interprocedural control dependence queries Future work

3

MotivationAs we have seen in class the Roman Chariots formulation for intraprocedural control dependence (Pingali & Bilardi) has allowed control dependence queries to be answered in (optimal) time proportional to the output size. We seek to extend that work to cover control flow graphs representing multiple procedures without the need for fully cloning each function.

4

How would that make the world better?Recall that control dependence (conds) is the same as the edge dominance frontier relation of the reverse graph. Recall that the dominance frontier relation is used in the construction of SSA form representations. If we could build this representation faster it would allow us perform a wide range of code optimizations in a more uniform and more efficient manner.

5

Valid Paths - Context Sensitive AnalysisValid path: A path from START to END in which call and return edges occur in well-nested pairs and in which these pairs correspond to call sites and the return sites specific to these call sites.STARTabcdFENDThis is intended to exactly capture our intuition of a call stack.

6

Other TermsNode w interprocedurally postdominates v if every valid path from v to end contains w. Node w is ip control dependent on edge (u v) if w ip postdominates v w does not strictly ip postdominate uWe notice immediately that these definitions are completely analogous to their intraprocedural counterparts - they however incorporate the notion of valid paths.

7

First postdominence, then the world!As the definitions suggest there is a tight relationship between control dependence and postdominance. To compute control dependence we first would like to compute postdominance subject to the following criteria: We minimize cloning to the fullest possible extent. We are able to parallelize the process. (One function - one thread). We can deal with all common code constructs (including recursion).

8

Computing PostdominanceIn the intraprocedural case every path through the control flow graph is a valid path and the resulting postdominance relation is a tree. Algorithms exist to produce this tree which run in time linear in the size of the control flow graph (Rodgers, et al.). The introduction of non-valid paths into the CFG breaks this property - the transitive reduction is now a DAG.

9

How is this done today?We use iterative methods and context sensitive flow analysis to compute postdominance and control dependence. This involves keeping a table of inputs and outputs. Convergence occurs due to the finite nature of the table but it is not guaranteed to occur quickly.

10

General DescriptionFirst, we do a generalized form of dataflow analysis in which each procedure acts as a single block box transition function. By keeping a table of inputs and outputs of this function for each procedure we gain efficiency and can detect termination. After the interprocedural relationships are understood - we compute the intraprocedural info for each procedure in the usual way.

11

Where we break downStartEndF-startF-aF-endG-startG-aG-endABCDEHIJKLCall FCall GCall GCall FRet GRet FRet GRet FEndStartLJKHG-startG-aG-endF-endF-aF-startIDEBCANotice the existence of an invalid path: Start-A-B-(F-Start)-(F-a)-(F-end)-K-L-EndControl Flow GraphPostdominance DAG

12

So What?We could ignore the invalid paths and claim that we are being “conservative”. However, if we do this we lose the fact that A is postdominated by both F and G - this is vital information that we can’t sacrifice and still expect to be able to compute control dependence. We need to construct this DAG in its full form.

13

ObservationsWe notice that the postdominance relations for F and G are subgraphs of the entire postdominance relation. This begs the question - Can we simply compute the postdominance relation with place-holders for F and G and then simply splice the F and G graphs in later? What information would we need to do this?

14

First AttemptIs it enough to simply know the two nodes that “bookend” all the calls to a specific function?StartEndCall FRet FCall FRet FABCDEGHIStartEndADBCEHCall FGIRet FCall FRet FEndStartDBCIGHEAWe notice that these two distinct control flow graphs produce the same postdominance DAG minus the presence of the F subgraph. Further, [A,D] bookends the calls to F in each case.

15

Defeat!Clearly, this technique fails to capture the fact that in the first case the F subgraph should postdominate both B and C whereas in the second case it should not. Conclusion: we need to know more than which link to break - we need to know what to do with the ancestors of the destination.

16

Correct Solutions after SplicingStartDBCIGHEFAStartDCIGHEFABCase ICase IIWe need more information than which connection to break to accurately do this splice.EndEnd

17

What do we need to know?We can think of a tree or a DAG as a representation of a partial order. Specifically we can think of the postdominance relation as a partial order since it is reflexive, anti-symmetric and transitive. Given this insight, we see that we need to inject the F subgraph into the partial order. Simply knowing two bounds is not enough to do this.

18

It gets worseIn the example provided we only needed to place B & C - singleton ancestors of D. In fact we can build CFGs where we have arbitrarily complex subgraphs feeding into D.DAFWe want to “splice” F in between D and A.UVWXYZ

19

In order to inject F into the partial order we must also inject F into every path from a terminal to D.100,1000,0F40,7560,6070,7050,8090,9065,45We define the partial order as := (a,b) < (c,d) iff (a

20

Union PostdominanceWe say that a set T union postdominates a set S in an interprocedural control flow graph if every valid path from an element of S to end contains an element of T. In the preceding case we must determine for each element of the subtree if it is union postdominated by all of the calls to a specific function. This is clearly not promising. This extends Generalized Dominators (Gupta 92).

21

OK, so we do that - what then?Our problems do not end there - consider the following CFG.StartEndBCDEICall FRet FCall GRet GCall HRet HF-StartF-EndF-AF-BCall HRet HG-StartG-EndH-StartH-EndH-AControl Flow Graph for MainControl Flow Graph for FControl Flow Graph for GControl Flow Graph for HG-AG-CG-DG-EG-B

22

When we splice in and expand the graphs for F and G we get two copies of H!HHEndStartEF-EndF-BF-AF-StartCBG-CG-StartG-DG-EG-BG-EndDAIMaybe this isn’t so bad - can’t we just “merge” them somehow?G-A

23

Oh, it’s bad.Given the partial postdominance relation all I can recover from it about H is that H should be a child of I. I don’t know which link from I to break; also I again don’t know what to do with the other children of I. As with the previous case I can create CFGs that make this arbitrarily complicated. Further I must now do UPD queries over the entire CFG.

24

Plan “A” is a loserIt is clear that we cannot simply compute these function DAGs independently and then splice them together since the splicing is more expensive than the original computation. We need to find a way to incorporate the splicing information into the original computation. In essence we need subgraph “placeholders” for each function.

25

A New HopeIt is clear that in order to construct the postdominator relation componentwise we need more a priori information. In essence we need to understand all of the possible call sequences a program segment can initiate - then we let transitivity do the rest. To that end we introduce the notion of “sparse stubs”.

26

Sparse StubsGiven a program for which we want to construct a control flow graph we construct a sparse representation in parallel that captures only calls and branches. We then use this sparse representation as a “stub” which we inject into the gap between a call and return. This stub then captures what we need to construct a PDD into which we can inject full subgraphs.