Chapter 5 Node Orders, Node Listing: Chapter 5 Node Orders, Node Listing 5.1 Reasonable node order 5.1.1 Interval Order is reasonable 5.1.2 rPOSTORDER is reasonable 5.2 A Dominator Algorithm for a Reducible Flow graph. 5.3 Node Listing 5.3.1 Strong Node Listing 5.3.2 Weak Node Listing
PowerPoint Presentation: Intraprocedural analysis It enables the compiler to optimize across different files and can result in significant performance improvement. Solution of Intraprocedural data flow analysis problem is: Find an equation relation information at the top node in a flow graph. Pick a strategy that specify in what order nodes are to be visited. Select appropriate initial estimate for the information. Visit the nodes according to the strategy chosen in step (b). To visit a node apply the equation of step (a).
PowerPoint Presentation: Two strategies that specify in what nodes are to be visited. Reasonable node order Node listing Reasonable node order : Include each node exactly once. Visit the node in round robin fashion. Visit nodes until all information being propagated. drawback: In round robin each node is visited on each iteration. Node listing : Each node may occur more than once. Only one node pass through the nodes in listing suffices. Avoid the drawback of round robin.
PowerPoint Presentation: 5.1 Reasonable node orders Let be a flow graph. A node order of G is a list of nodes that include every node of G exactly once. A node order R of a flow graph G is call reasonable iff R topsorts the dominance relation of G. Prove: Interval order(page 65) and rPOSTORDER is reasonable.
PowerPoint Presentation: 5.1.1 Interval order is reasonable Reduction of a flow graph: Let G be an RFG and let ∏ be a parse of G by T1 and T2. A reduction of an RFG G with respect to parse ∏ is any Gi , 0<=i<=m, where G0 = G, G(i+1) is the result of the (i + 1) st transformation in ∏ applied to Gi . The string of a node : The string of a node of a reduction of an RFG G with respect to a parse ∏ is defined recursively as follows, In G, the string of each node w is ‘w’. When every node x(with string a) consumes node y(with string b) in Gi to from G(i+1) then a’,’b is the string of the merged node z. The string of any node v, where v is not represents by x or y in (b), is the same in G(i+1) as it was in Gi .
PowerPoint Presentation: Let x be a node in a reduction G’ of an RFG G with respect to parse ∏ and suppose x represent region R of G. A parse order of a region R is the string of x. A parse order of an RFG G is the string of the node representing the limit of the flow graph. Lemma 5.2 : If P is a parse order of an RFG G, then P is parse order of the DAG D of G. Assume that P is a parse order of G. Clearly, each background arc has no effect on the construction of P. Thus all backward arcs can be ignored. Therefore P is also a parse order of D.
PowerPoint Presentation: Theorem 5.1 : Any parse order of an RFG G topsorts the DAG D of G. Corollary 5.1 : From theorem 3.2(page 61) it can be stated that “An interval order topsorts the DAG of an RFG”. Lemma 5.3 : From observation 2.8(page 42) it can be stated that “Any linear order that topsorts the DAG D of an RFG G also topsorts the dominance relation of G”. Finally from corollary 5.1 and Lemma 5.3 we can conclude that, “ An interval order topsorts the dominance relation of an RFG ”.
PowerPoint Presentation: 5.1.2 rPOSTORDER is reasonable POSTORDER is the order in which each node was last visited while growing DFST of a flow graph. rPOSTORDER is the reverse of POSTORDER. So, for each node x. Theorem 5.2: rPOSTORDER topsorts the DAG of an RFG. ** rPOSTORDER topsorts the dominance relation of a flow graph. That is if x dominates y then.
PowerPoint Presentation: Let, G is the flow graph in which x dominates y. T is DFST of G and x ≠ y. Since x dominates y, any path from initial node to y will include x and x reached before y while growing T. x is an ancestor of y in T. if not then, y is ancestor of x in T y is to the right side of x in T x is to the right of y in T If any one of this three is true then there would be a path in G from s to y not including x. its contradicting x dominates y. According to algorithm 3.2 (page 68), thus y is last visited before x is last visited. That is,
PowerPoint Presentation: 5.2 A dominator Algorithm for a Reducible Flow Graph Algorithm 5.1: “Computes sets DOM(x), the dominators of x, for each node x”. Inputs: Reducible flow graph, represent the predecessor list. Nodes of G are numbered from 1 to n by rPOSTORDER . Outputs: Sets for each node y.
PowerPoint Presentation: A dominator Algorithm for a Reducible Flow Graph (cont.) Method: Sets DOM(1)…. DOM(n) are global, and each represented by a bit vector of length n. Use (). Procedure G = (N, A, s)) integer j, k for j :=1 to n by 1 do DOM(j) := {j}; endfor for j := 2 to n by 1 do := endfor return
PowerPoint Presentation: 5.3 Node Listing When we solve Intraprocedural data flow analysis problem information at each node in a CFG that is propagated to all other nodes need to be propagated over cycle free paths. “Node Listing” is an intermediate representation of a flow graph that facilitates this propagation. Two type of node listing: Strong (rely on the concept of simple path) Weak (rely on the concept of basic path)
PowerPoint Presentation: 5.3.1 Strong Node listing A strong node listing for a flow graph G = (N,A,s) is a sequence of nodes from N such that all simple paths of G are subsequences thereof. Example: (1,2,3,2,1) is a strong node listing. A strong node listing is called minimal iff there is no shorter strong node listing for G. 1 2 3
PowerPoint Presentation: Observations : For any flow graph there exists a strong node listing of length at most . If a flow graph is a DAG then any topsort of G is a (minimal) strong node listing for G. There are three important results about strong node listing for RFG are: Every RFG has a strong node listing of length at most . There exists RFGs for which no s trong node listing is shorter than . A strong node listing for an RFG with arcs be constructed in time
PowerPoint Presentation: 5.3.2 Weak Node Listing A weak node listing for a flow graph is a sequence ( ), , of nodes from N such that all basic paths of G are subsequences thereof. A basic path in a flow graph is a simple path ( ), k>1, such that there is no shorter simple path from to which is a subsequences of ( ).
PowerPoint Presentation: The simple path ( ) is not basic Because it contains the basic path ( ). Observation: “Every strong node listing is also a weak node Listing” . -x- 1 2 3 4 5