GENERAL FLOW PROBLEMS AND GRAPH GRAMMARS Lishing Liu Computer Science Department Cornell University Ithaca, N.Y. 14853 TR 77--H308 1. Introduction A standard approach to compile-time program optimiza- tion is to analyze the controle flow graph of a program. In the early 70's the interval approach tA, c, Ar?l) was introduc- ed to solve flow problems. It has been recognized that reducibility" is a desired property on flow graphs when flow problems are solved. Hecht and Ull?an t?Ul] Give two simple graph grar?nar rules T1 and T2 for reducible graphs. tlL-an (?U, U] shows that the cormon subexpression eli?ination problem on reducible graphs can be solved in O?eloge) bit- vector steps, where e is the number of edges in flow graphs. Another approach is to propagate information through flow graphs until the propagating process converges. General formulation of data flow problems using lattice theoretic framework is also introduced. Representatives of such work can be found in !AU2, Fxz, HU2, Kul, Ke, Ki, U3. Recently Graham and Wegman [GWJ present a new algorithpt for global flow analysis which combines a modification of interval approach with a modification of the transfor?atioms T1 and T2 introduced by Hecht and Ulimen. The idea is to decompose the graph reduction rules into simpler forms so that a flow analysis problem can easily be reduced into a smaller- sized problem when the flow graph is reduced. It has been shown that a forward inforration propaGation problem on a reducible graph can be solved n C(eloge) funct?ona? step Farrow, Kenn?dy and Zucconi [?KzJ d?fins a class SSFG of semi-structured flow graphs. The graph grt?Tar for `# SSFG is dn extension of the B?j grar?r (named for Bo'?hm and Jacopini). The graph gr??Tar rules are rather simple so t:?t many flow problems on >SSFG can be solve? n 0(o) `rctior.el steps. In this paper we extend the idea of "acceptable assi- gnment" in (GW1 and formulate general data flo anal?:s?s problems in terms of lattice tneoret?c fr?e?ork. In c.?'?ra_ data flow analysis problems can be classifie? into fr?n najor classes, the forward information propagation probI?ns and the reverse information propagation problems. M0cifyL?g slightly the three transformations T1, T2 and 13 intrn?jced in [?Wi we show that these data flow problems on reducible flow graphs with "fast" function spaces can be sol??d in Oeloge) functional steps. The generalization of the method in [GW? to general forward information propagation problers is straightfor?rd ?or the bac?ward information prcpaqa- tion problems, we don't treat them es forward proble?s on the reversed graphs and no reverse graph reduction rules are needed. We also define new graph gr?c"ars SG()?). The class SG(k) of flow graphs generated by SG(k) is wider than SSFG ?neral data flow problems with "fast" function spaces can be solved using 0(e) functional steps on a flow graph in Y S? (k) The paper is organized as follows. In section 2 so""e basic definitions and results un flow analysis are presented. In section 3 we formulate general flow analys?s probla?s and show how they are solved on reducible flow graphs. In section 4 new graph grasmars SGCk) are defined and examined. Section 5 is the sasinary. 2. preliminaries A (directed) graph is a pair (N,E1 where N is a finite set of nodes and E Mx?; is a set of edges. Given a graph G `?,E) we say that a non-empty sequence of nodes p0,p1,.. is apathfrosp0tooflengthk provided that for all i between 0 and k-l, (pi'?i+l? is an edge. tet e=(x,v) he an edge, we say that e enters y and leaves x, ? is a predecessor of y andy is a successor of x. pred(x)wlll denote the set of predecessors of x, and Succ(x) will denote the set of successors of x. An edge (x,x) is celled a self-loop. A path from x to x is called a cycle. A graph with a single node and no edges a called a trivialgraph. 2.1 ?eoucibjeurapns A flawgraph G CN,E,n0) is a graph (N,E) together with a distinguished entrynode n0 such that for all x in N there is a path frcxn n0 to x in G. Reducible graphs were originally defined by Allen and Cocke in terms of `intervals'. We will use an eguivalent definition using the transfornations T1 and T2 introd'jced by flecht and Ullean tWJll let G (?,f,n3) be a given flow graph. Transfon?a- tions T1 and T2 ire defined as follows: T1 --H If a is a self-loop in G then T1CG,e) = (N,E- c: (sxs) . The pair (s,=>) is finite if for each p in S there is a constant k such that if p =?> q then P -?-- 7 7 i ` kp, where --> is the i-fold composition of =>. We say that (s,=>) is finiteCh??&?-?u??eL (PCR) if the following conditions are satisfied: (1) (S,=>) is finite, and (2) if p q and p r and there is no t with q --> t or r => t then q = where ?> is the reflexive transitive closure of =>. The following theorern gives a test for FCR property. Theorem !Se?: Let => be a relation on S. Then (S,=>) is FCR if and only if Cl) => is finite, and (2) if p => q and p => r then there is a t in S such that q => t and r => t. ?::ernPle: tet S be the set of flow graphs. Define the relation => on S as G1 => G2 if and only if G2 = Ti(G1), i --H 1,2. It is shown in tHUl? that (S,=>) is FCR. 3. GlobalDataFlowProblens In this section we are going to generalize the res?'lts of fGWJ . In 3.1 soT-?e lattice algebra is presented. In --H 3.3 str.?ight?sr?srd can?a1ization -?? oata low problem definitions will be given. In 3.4 we first state some lemmas and the key constructions in tne proofs which are direct abstractions of the results in fGWJ, then we show how the reverse problems can be handled in a similar fashion without introducing reverse graph transformations. 3.1 SometatticeAlgebra As flow analysis is a general term, instead of looking at few typical examples we will formulate flow anal?"sis problems using lattice theoretic constructs [Xi,KU2i. Definition: A semi-lattice is a set L together with a binary meet operation A such that for all x, y and z in L X A X = X (ide?pctent) X A Cv A = A A Z Cassociativity) X ? y = A X Ccc:me:t=tivity). Given a semi-lattice L, for x, y in we say that x S y if X A y x. L iS said to nave a zero senent 0 if 0 : x f? all x ? t. t is said to have an ore elerent 1 if x s 1 frr all x ? t. ret f: L L be a function from L to L. We sey that f is monotonic if x s implies f(x) ? f(y) for all x, y L. f is distributive if fC?y) = f(x) A fCy) for all x, y L. We also extend the "faatness" defined in [GW). f is fast if for all x in L, X A f(x) s (f.f)(x). A set F of functions fr? L to is a?? to be fast ?esp. distr?b"tive) if all funct?ons in F are fast (resp. d?stributive) If 9 Md h are func bra fron a set 5 to a seri-lattice t, then -9 (gAh) denotes the function fro? s to t such that (gAh) (5) = g(s) A h(s) for all s( S. We say that g s h if g ? h = g. idL will denote the identity function on t. Now we are ready to define data flow problens formally by extending the information propagation problem definition in [GWJ. 3.2 Info?eetionPropagationproblens Definition: A monotoneinformationpropagationframework is a tuple D (L,A,F), where L is a semi-lattice with meet A and F is a set of functions from L to L such that F is closed under function co?position and function meet. D is fast Cresp. distributive) if F is fast resp. distribu- tive). The notion of monotone framework was first introduced in [KU]. Through out this report we assume that all problems are defined under a monotone fr??nework. In [KU] it is shown that the constant propagation problem is usually formulated under a monotone but non?istributive framswork, and it is observed that it is not quite satisfactory to solve such problems by finding fixed points of ecuations. Definition: An informationpropagationprohl?rn is a tuple Ip = (c,D,N,x0) where G = (N,t,n0) is a flow graph, D = (L,?,F) is a monotone infnrnation propagation fr??ework, N: E F is a ?anction fro:t E to and x0 L is the boundary infoi?ation associated with the ar-try node n0. 10 For notational convenience, if M: E F is as in the above definition, then ?e denote M(e) for e in ?. If ? =??o'???'?k is a path in C then fp will denote the composition of functions f f If p is (p0,p1). the null path then f = idt. p Notice that idt might not be in the function space F. Actually, if F is fast then adjoining idL to F might not preserve the fastness property. Definition: let IP = (G,D,N,x0) be an information propaga- tion probles where a CN,E,n0) and D = (t,A,F). A function FP: N L ? afixeooointforIP if FP(n0)sx0 and FP(n) ? ?e?FpCm)) for all mclred(n). A function S: N L is asafeassignmenttoIP if sCn) ? fp(X0) for all path p from n0 to any node n. A function AA: N t is anacceptableassignmentIP if AA is safe and if s AA for all fixed point FP for IP. The ahove definition is a direct abstraction of the infornation propagation problem definition in (G?) To solve such a problen is to find an acceptable assign=ent. An acceptable assignment is an assigr?ent of information to nodes in such a way that the information at each node never exceeds any inforoation propagated fro? n0 to that node, while the assig?rent is at least as good as any ft?ed point. A t??ical axample of the ?nfornation propagation proble? is the cocoon sube?.oression eli??tinstion problen. tat G = (N,E,n0) be any flow grap c a certain procran. For 11 n N let b(n) be tne computation block represented by n. An expression, say A+B, is said to be available at a node n if no path fran tne previous evaluation of A+B to n can modify either A or s. To fo??late the problem of find- ing available expressions at all nodes we first introduce the well-known functions KILL and G? used for this puroose. KILL and GEN are functions fran 5 to the set of expressions computerd in tnis program: For e = Cm,n) in 5. Cl) GENCe), denoted GEN5, is the set of all expressions a in such that a is computed somewhere in bCm) and that none of the variables involved in a is modi- fied within bCm) after that canputation of C21 KILLCm), denoted KILLe is the set of expressions a in such that some variables involved in a are modified without recomputing a within bCm) afterwards. Then the ccis'on subexpression elimination problem can be formulated as the information propagation problem IP CG,D,M,x0), where 6 D = CL, 4F) with L = 2 A = set intersection F = set of all functions from L to L, M is ?efine as M(e) = GK(G??e KILLe) for ees, 12 where CX: Lxt F is the funct?on such that CXCx,y) (:) = (z-y) u 5 for all x, y and z in L, x0 the ?spty set. In implementation, el=?ents of L can be represented as bit-vectors. And it can be shown fGw] that GX(x,y)'GKCx?,y?) = GK(?'-y)nx,??-x)ny) and GK(x,y)AQ?(x',y') = GX(x?x ,ysy') Hence the functional operations can be carried out effic?ent- ly using logical bit-vector operations like AND or OR. 3.3 ReverseInformationPrupa?atiun?rorjer.? Another class of flow problens rsg?ires propagation of ?nforaation from the end of a progran. There are sone diffi- culties in defining this kind of proble'ns on general flow graphs. According to the definition of a flow grap: there could be several nodes withcut sages leav?ng th=--H?. A cor-na- tional program return in a basic blon? nay not be located if we sinply look at a flow graph without any return message. But fortunately the program return infronaton an ba collec- ted when the flow graph is constructed fron a progr?n. Therefore, in dealing with reverse propagation problams, we may assume that the flow graph for a progra? is constructed in the following way: (1) First construct an extra return node r. C2) Construct flow graph as usaual. ?Jt when a node n is formed and the block b(n) has 13 a return instruction at an exit, we add an edge (n,r). (3) b(r) contains no computation at all. It is easily seen that if the original flow graph for a program is reduciole then the new graph constructed as above is still reducible. The return node r constructed has the property that it is the only node without leaving edges. Hence the above steps give a construction of a harnock graph [GWJ The extension of the information propagation problem definition to the reverse information propagation problens is cuite obvious now. The reverse probles is just like a mirror image of the forward problem, information is propagat- ed backwards from the return node instead of being propagated from the entry node n0. The reason we need a separate definition for the reverse problems is that the reverse of a reducible graph might not be reducible, and hence we do not want to treat the reverse problens as forward problems on the reversed graphs. Definition: A reverseinformationpropagationproblem is a tuple RIP CGr?D???Xo)? where Gr = (N,E,n0) is a flow graph with a return node r such that r is the only node in N without leaving edges, D CL,A,?) is a monotone informa- tion propagation framework, M: E ?+ F is a funct?on ?rom E to F, and x0EL is the boundary information associated with r. 14 Again we denote ??) by ?e for e?E. If p = p0,p1,...,p? is a path in G then f denotes the p function co=position f ,f o+. ..f If (po,pl) CP1,P2) ?k-l P3c). p is the null path then let f be Notice that in p i?t p functions are co=posed in the reverse order. That is, ?hen is used, f(p??1,p?) will be applied first. Definition: Tat RIP = CGr?D?M?xc) be a reverse infor-ation propagation problen. A function Fp: ? t 5 afi?ed0i?t forRIP if FP(r) 5 x0 and for all a (?,n) in F, FP(n) ? ?e(FP(n)). A function S: N L is asafeassig=ent toRIP if for all path p roe a node n to r, S(n 5 fp(X?? A function AA: N L i? ,????-ab?e??siur?5ntto?IP AA is safe and FP 5 AA for all fixed point FP for RIP. vo solve a reverse inforratian problen is to f?nd an acceptable assigninent. That is to find an assignrent of infornation to nodes such that the assign-?ort 15 no rt?ore than any infornation which can be pronagated fron r and that it is at least as better as any fixed point solution. An exanple of a reverse 1n?orrat?on probleo is the well-known live variable analysis proble=. We will fol?ow the notation in [FKz]. The problen is to deterr?ne for each basic block b in a progr?? the set LI?T(b) of all variables x for which there is a path frc?n the entry point of b to a reference of x such that this path is X?lear (i.e. contains no re-definition of X) 15 Let INSIDECb) be the set of all variables x which are live on entry to block b because there is a use of x within b which is not preceded by any re-definition of x in b. Let TF?UCb) be the set of all variables x for which there exists an Xclear path through b. Both INSIDE and THRU can be computed by local examination of basic blocks and can be implemented as bit-vectors. Then the live variable analysis problem can be formu- lated as a reverse information propagation problem RIP (Gr?D?M?X0) where Gr is a flow graph with return node r for a certain program, D = CL,A,F) where t = 2 is the power set of the set ?/of all variables used in a program, A is the set union operation, and F is' the set of all functions T?,y of the form T?,y(z) x u (y n z) for x, y, z ? L. It can easily be verified that such D is distributive and fast. As no variables can be live at the end of a progran, x0 --H o+. Notice that o+ is the 1 elenent of L (and hence x0 is again a trivial information). Initially if u is a node in Gr representing a basic block b and if Cu,v) is an edge in Gr then the propagation function ?((u,v)) is defined as TINSIDE(b),ThRD(b) The eguation among the live infromation is LIV?(b) = IflSIDE(b) u u (THRU(b) n ?1VE(c)), c?SCb) where 5(b) denotes the set of all basic block represented by nodes wh?ch are entered by an edge leaving the node 16 representing block b. it can b? shown that T?,y Tx ,y T???y? ),(yny'? and T?,y Tx# ,y =T(xux'),(yuy'). Therefore functional operations can also be implemented efficiently using logical bit-vector operations li 1 or n no then return; let e = (jn,n) be the uni?ue edge in IN(n); fflf R2 or R4 are applicable to e then begin apply ?2 or R4 to e and t'pdate P; n return; end if R5 is applicable to Cm,n); begin A: apply ?? to ?,n) and update P; if before applyign the R there is a unique edge ?,n?) in OJTn), n # n0 then begin call Algorithrr 1 on nw; if is now applicable to Cn,n') ffi? begin n := to A; end 14 n := end 15 else iterate := false; end of Up Figure7 - ??-? 41 ?hen UP(n) is called in Algorithm 2, and 54 are not applicable to any edge in OUT rn), and therefore it tries to apply 52' 54 or 55 to collapse a possible edge in INCn). If none of ?2' ?2 and 55 is applicable to edges in IN(n) then iterate is set to false so that Algoritnm 2 will process the next node n at statement 2. In UP we need a chain of 55 reductions since an R5 reduction might create another instan- Ce of 55 application whicb night not be easily detected at node m. The situation is illustrated in Sigure 8 below. xl) __ Fi ure 9 55 In Figure 8, after an R5 applies to Cm7n), it might not be easy to verify the applicability of on Cm,n?) as JoUT(m)I could be very large. ?efore we prove the correctness of Algorithm 2 we need some observations. Ob???vation1: If there are ?? ?2' 54 or 55 reductions on edges in OUT(n) between two calls of Algorithm I on n, then the second ?all of Algorithm 1 will not change OUT(n). 42 Observation2: t'iring the execution of a call of nP(n), if none of R2, R4 and R5 is performed then iterate will be set to false, otherwise n will be set to :5 upon exit of ?P, where :5 is the unique predecessor of n upon entry to `:P(n). Observation3: In a call of DOWN(n), n is never changed. Just before the exit from a call of DCWNCn), a call of Algoritnm I on n will be executed. ?r?na4.3: Right before n is set to 5, I < 5 < 1NI,?at state:5ent 2 of Alogrithm 2, for :5 = l,2,? 5-1 either :5 has been eliminate? (by R2, R4, or R5) or the following will be tfle.- (a? OUT(n1 cannot be ch??ged by calling Algorit?n 1 on :,:. (b? XNCni? cannot be changed by calling Algorithi 1 on :5. (c? Neither R2 nor R4 is applicable to edges in 0UT(m?. Cd? None of R2, R4 and R5 is applicable to edges in IN(m). Proof: The proof is by induction on 5. When 5 = 1 the l?ama is clearly true. Assume that the ler?rta is true for 5 < K, where 1 K < INI. We need to show that the lenma is also true when 5 = Let o+ denote the moment when n is set to K at state- stateeeent 2 of AIgorithm 2. So there is a moment o+ when 43 n is about to be set to X-I at statement 2 of Algorithm 2. Assume that the lesna is violated by some m < K at ?. Of course m cannot hav? been eliminated fras ? before $. First consider (a). Assume that (a) is false at o+. Let ri be the last time before o+ when (a) is changed from true to false for In. By Observation 1, the change of y' must be causes by R21 R4 or R5 on some edge e --H &n,n) in OUTCm). But then by Observation 2 and Observation 3, a call of Algorithm I on in will be executed at statement 7 of Aigorithm 2. Then, by Observation I, we get a contradiction to the choice of ?. Therefore (a) must be true at o+. Assume that Cb) is false at *. Again consider the last moment n before o+ when (b) is changed from true to false for in. By reasoning similar to the above argument the change at fl cannot be caused by an Algorithin I call or by R2, R4 or R5 on an edge in OUT?). The change cannot be caused by an R2 reduction as the only possible choice of R2 at n is an R2 on an edge in OUT(ni). The change cannot be caused by R4 as in that case the test at statement I of DOWN would be true and hence the execution of DowN would force fb) true at in again. Similarly the change cannot be caused by R5. Therefore the change at ? can never occur and so (b) must be true at o+. Assume that (c) is false at o+. Again consider the last time n before * when (c) is changed fr?? true to ?lse for In. The change cP?,nnot be caused by R2 or R4 as the construction of DOWN and UP would force the red?ctjon to be 44 carried out before n is set to X at stat&???nt 2 ?f Algorit?n 2. By Observation 2 L?e change cannot be caused by R5 reduction on an edge in OUT(rn). Therefore the only possible change at n is an R5 on an edge in OUT(n) such that n is successor of m. But then by construction of up CcJ has to be true again before $, which would violate the choi.?e of n. Hence Cc) nust be true at o+. Assume that Cd) is false at $. If R2 or are appli- cable to an edge (n,m) in INCn) then n < m by the choi? of acyclic order l,2,...,IN!. Fence, by (a), (b) and Cc) violation must be that an R5 can apply to an edge (n,n). Consider the last time ? before ? when (d) is chanced fr? true to false for m. By Observation 2 the change cannot be caused by R5 reduction on an edge in OUTCm). Then the only possible change at n is depicted in the picture below. That is, the at n must create a duplicate of an edge fr?si n to n such that R5 is applicable to Cn,m) after n But after the red?ct?on at fl stat??ents 10 - 13 and statement a of LTP would eli?n?nate node m by an R5 reduction which would rontradict the assueption that m has not been elisin?t?? at o+. Hence Cd) suet also be true at o+. 45 le::::a4.4: Algoritha 2 always terminates. Proof: We will prove that each iteration of the for loop in Algorit?in 2 will eventually terminate. Then, since 5 never gets modified except at statement 1 in Alcorith: 2, and hence at most NJ iterations can be executed, Algorit'? 2 will finally terminate We prove by induction on 5 that the -th iteration of the for loop will be executed and will ter?inate, for o s < When 5 = 0 the assertion is obviously true. Assume that the assertion is true for all a 5 < where K < NJ. Then after the termination of the first N-1 for loop iterations n will be set to have value X at state- ment 2 of Algoritha 2. From this point on iterate will eventually be set to false in Up since the number of possible reductions on G is no more than and hence statement 8 of DO?? and then statement 15 of Up will eventually be exe??ted. And then the v-th iteration of the for loop will also ter=inate. Therefore the lemma is proved by induction principle. 46 Theore':4.5: Algoriths 2 terninates with correct output. Proof: During the execution of Algoriths 2 a reduc- tion can be perforned only after being verified applicable, and the parse list P is always updated after each reduction. Therefore, if G is reduced to the trivial graph at the end of Algorithe 2 then P zust be a correct parse. On the other hand, suppose ? is not the triv?al graph at the end of Algoriths 2. Hy L-e=?a 4.3 no further reduc- tions is applicable. Thus by FCR property c ? >fficc?? Hence the failure report is correct. `So' let us exanine the running ti:ne of Aigorit?un 2. Theorem4.6: Algorit?n 2 terminates in Ofiaji steps on a flow graph = CN,E,n0) p?cf: Fros lrnna 4.4 Algorit?? 2 will eventually terninate on G. tet A be t:?e nunt?r of iterations executed on the for loop and let b be the nursher of iteratior? ted on the inner loop of Algor?ths 1. tat C be the `?tal an0unt of work spent on the exe?jtion of stat??ents 7 - 9 of Algorithm 2. The total running tir? of Algoritt 2 on Is OCA+B+c). clearly A = NI. B is O(;E!) since in L?Cn) itarate is set to false unless an P5 reduction is perfo?ed and the total nucrer of reductions i5 no rore than ,si. ?y la-?.s 4.2 47 the total nw?ber of steps spent on statesent 7 of Algorithm 2 is o(I?I + B) and hence is o(IEI). The total nunber of steps spent on statement S of Algorith:s 2 is clearly bounded by the amount of work spent on a2 and R4? and hence is o(?EI + 8), or o(IEI). Similarly statement 9 takes o(I?I) steps in total. Therefore C is OCIEl). And hence Algorithn 2 terninates in oclEl) steps. ?urollary4.7: SG(k) parsing on a flow graph G = (N,E,n0) can be done in OCIEl) elementary steps. Proof: The proof follows from Theoren 4.5 and Theoren 4.6. 1 4.4 Information Propagation Probless on Sc(k) We have shown that an S(:(k) parser works in o(IEt) t??e. In this section we present a solution nethod for inforsation propagation problens on Y We cannot apply the problern reduction technicr?e of [?w? directly by decomposing each SGCk) reduction rule intO a series of Tj T2? and T3? transfor:nations, s?nce a1 and R2 could be very costly. Furthersore, the existence of dupli- cated edges precludes eliminating edges in a straightforward way. To get around these difficulties we will ?se a weighting techni??e to r'ssenber infoi?tion. We perfors the problen reduction technique ?escribed in section 3 by manipulating the weighted inftrmatiom properly, Let IP = ?,D,M,x0) be any inforr?tion prQm:'t! )n problem, where G = CN,E.n0) and D = (t,A,F). Two weig?tinq functions W1, W2: N ? FUfidL? will be used. InItiall,' = W2Cn) = i% for each node m. The weight?ng functions are used to mimic another reduction of the infornation propa gation problem. Let W = CGThD,M,x0) denote the mimicked problem. When an R1 reduction eliminates a sel?-loop at node n t?= mimicked problem does not really eliminate the self- loop and the information associated with the self-loop is aco?ualated in w1Cn1. When a reduction ?, R4 or ?? applies to an edge (?n,n) in G, the mimicked probl?¶ first elL?inates the simicked self-loop at n by applying the reduction tech- nique described in the proof of Lemma 3.1 using the accumual--H ated information W1(n). W2 is used to store flow inforsation for edges eliminated by R2 reductions. ?hen an reduction applies to an edge e = lm,n) in G we do not update ?e as e" ?e for all edges e' in OtT?) , as that c'=?ld e very slow. Instead we store f in e ???? The invariant relation we r?ntain between IP and UP is that M?) = MCe',.w2(m) for all edges e = Cxn,n) in IP. Notice that G is the same as G e.?ept for several mimicked self-loops which are already eIus'i?ated fran G by R1 The actIons on each reduction rule of SG?? are des- cribed below. 49 R1: Let --H ??,e) be defined for a aelf loop a at node v. Action: W1(v) := w1(v) A R2: Let = R2CG,e) he defined for e = (u,v), u ,f v, v#n Action: M(e). := MCe) A O??(v).?M(e)); (I) W2(u? := W2&)'M(e); Notice that the assign?¶ent in (1) has the side effect of modifying the value of M(e). Any acceptable assignment AA to the reduced problem can be extended to an acceptable assign- nent to the original problem by fefiring AACv) := M(e) CAACu)); where ?(e) is evaluated using the MCe) obtained in (1). R3: Let = R3CG,e,e') be defined for e and a' Action: M(e') := M(e?) A M(e); R4: Let G' = R4(G,e) be defined for e (u,v), u ? v, v,'n0. Action: M(e) := N(e) A CW1(v)?M(e)); (2) if Cv,u) c E then W1(u) := for each Cv,w) c E, v ? w do if Cu1w) ? ? then else M((u,w)) 50 Any acceptable assignnent AA to the reduced problem can be extended to an acceptable assign sent to the origir?l problen by defining AACv) := M(e)(AA(u)); where M(e) is evaluated using the M(e) obtained in (2) R5: Let G? = R5(G,e) be defined for a = (u,v), u ? v, v ? no. Action: ?Ce) := MCe)?(W1(v)?MCe)), (3) if (v,w) E a then where a' is the new edge created fro::, u to w, Any acceptable assignrent AA to the reduced problem can be extended to an acceptable assirn- men to the or?g??al problem by defining == M(e) (??(u)); where MCe) is eval?ated using the Mte) obtained in ?) When a flow graph is reduced to the trivial grap? ?e sisply define AA(n0) := W1(x0) and this acceptable assignment to the trivial graph can be extended backwards to giva an acceptable assignnent to the original inforsation propagation problem. Coabining the above with corollary 4.7 we get 51 Theorem4.8: Let G = (N,E,n0) be in o+? and let IP SG(k) (G,D,X,x0) be an information propagation problem on G. If D is fast tnen an acceptable assignment to IP can be found using o(IEt) functional operations. 5 4.5 Reverse Inforsation Propagation Problems on To aolve reverse information propagation problems on we also use weighting technique to solve mimicked problems. To handle the problem reduction construction in Lemma 3.5 efficiently we eliminate a self-loop at node v in the mimicked problem only when there are no nore than k+l edges leaving v. But thcn we need to handle R2 reduction carefully. Another problem is that if AA is an acceptable assignment to a reduced problem on 52(Gr,e) than we want to extend AA to an acceptable assignment to the orig?nal problem efficiently. According to the construction of tesa 3.6 and Corollary 3.7, if e = ?,v?, in order to extend AA and to define AA(v) we need to take the reet of all M((y,w))CAA(?)? over w?s such that w ?Suoc(v) before the R2 reduction. But this is quite expensive if succ(v) is very large before the R2 reduction. To overcome the ?ve two difficulties, when R2 applies tc an edge (u,v), we collapse u into v instead of collapsing v into u. temma4.10: Let RIP = CGrrD1M,x0) be a reverse infornation propagation problem, where Gr = (N,E,n0) is a flow graph with return node r. Let e Cu,v), v ,L no, be the unicue non-looping edge entering v and the only edge lea?ing u. Then a reverse information Propagation problem RIP' CGr'?D,M',Xo? Gr = CN-fu),E',n), can be found such that an acceptable assignment to RIP can be obtained from an accept- able assignment to RIP' using one funct?on applicat?on Proof: Let w = Pred(u) Define G' such t?at r = cEt (w,u) IwcW)) u ((w,v) IWEW), n = n0 if u $ n0, n = v if u = n0. M' is defined as follows. For all W E w-fvj, M'CCw,v)) = M(Cw,u))?N(e). Suppose (v,u;? t?en --H M((y,u))?M(e) if Cv,v) ? E, and M' C(v,v)) = MC(v,v)) C??Cv,u))?N(e)) if (v,v) E E. For all fx,y) E E, y $ u, define N'C(x,y)) = .M(Cx,y)). ?otice that all function compositions are "backwards as we are dealing with reverse problems. Let AA' be any acceptable assignr=ent to RIP'. Define AA such that AA(u) = fe(?(v)) and AA(z) = if z $ u we need to show that AA is acceptable to R?. First we show that any fixed po?nt for Rip, if restri- cted to N-(u), is also a fixed Point for RIP'. so let FP be a fixed point for RIP. In Gr'? if (x,y) c ?`, x ? W, then (x,y) CFP(y)) = f' (FP FPCx) ? f (x,y) (y)). If w w--Hfv), or if 53 w = v and (v1v) a E, then FP(w) ? f (FP(u)) ?,u1 (u,v) (FP(v)), hence ?p(w) S ?`(w,v) (vPCv)). If v c W and Cv,v) E E then IPCv) ? Cv,v) (?(v)) and Fp(v) < ?(v,u) ?pp (u)) s ?(v,u) ??e?p(v))), therefore RP(v) S CFP(v)) is also true. ?ence ?P, when restricted to ?-(u), is a fixed point for RIP'. it remains to show that AA is safe for ?P. Let P P0'P1? ?,p? be a path froni p0 to the retu?n node r in Let p' be the path obtained fro= p by replacing all consecutive occurences of w,u,v with w,u, where w is any node in W. Then p' is a path in r if p0 # u. Since w,v w,u,v for all w in W, AA(p0) = AA' (p0) S fp (x0) s ?pCX?) if p0 ? u. If p0 = u then p1 = v, hence AA?) = ???(v)? ? ?eCfp1,p2,...,p?(Xo)) = f=p(x0). Therefore AA is also safe to RIP and is then acceptable to RIP. The possible change of the entry node n0 in the ab?ve le=na could be inconvenient if we solve both forward and reverse problems at the same time. But proper renaling of nodes can overcome this difficulty easily without maintain- ng two different flow graphs. To implement the construction in te==a 4.10 efficient- ly we use a weighting function W2 to store information on the edges eliminated by R2. Define two weighting f?r?tion ?l' W2: id Initially w1Cn) = ?2(n) = id or all no?-s I in N. tet 54 RIP = (Gr,D,M,x0) be the mimicked problem. Again Gr is the same as Gr except for some self-loops which are already eli- minated froin Gr' and the jn?or"at?on of these self-loops is stored in W1. w2 is usec to store inor=ation on those edges elimir?ted by ?2 The invariant relation be?een RIP and RIP is that M((u,v)) = M(u,v)).W2Cv) for all edges (n,v1 in ? r Notice that the weight w2?) above is the weight associated with node v instead of the ?eight associated with node u in the forward problen case. It is worth mentioning that, by construction of Algorithm 1, if there are no r?ore than k+l edges leaving a node n then all self-loops at n will be eli?inated if Algorithm 1 is called at n. Therefore before we do reduction R4 or .R5 on an edge (rn,n), all infornation on self-loops at n has been stored in w1c?). The actions taken by each rule of s??? are described R1: let G = R (Gre) be defined for a self-loop at v. r 1 Action: W1 (v) := W1(v). N(e); R Let G, = R Cc ,e) be def?ned fcr e = (u,v), u $ v, 2 r 2 r v#n. Action: if v = r then /? see the renark after actions t/ else /t node u will be eliinina?ed, soe te?a 4.10 k/ below. 55 begin M(e) := W1(u).M(e) (4) W2Cv) := ?(e).W2(v) end Again notice that the assignment in (4) has the side effect of modifying gCei. If AA is an acceptable assignnent to the reduced problem then we can extend AA to an accep- table assigr-nt to the original problem by defin--H ing AACu) M(e)(AA(v)); where M(e) is evaluat- ed using the MCe) obtained in (4). R3: Let G' = R3(Gr,e,e') be defined for edges e and e' r froi u to v. Action: NCe') N(e?) A R4: Let Gr' = R4(GrC) be defined for e - Cu,v), u I' v, v $ n0. Action: if v --H r then /* see the renark after R5 actions */ else begin for each (v,w) in E do M(Cv,w)) := W1(v).M((v,w)); (5) if (v,u) E E then W1(u) := for each (v,w) ?, v u do if ?,w? ? E then M?L?CCv,w?? else M?Cu,w)? :--H M?Cu,w)? A 56 end If AA is an acceptable assignment to the reduced problein then we can extenied to an acceptable assignnent to the original problem by defining AACv) := p\ ?CCv,w)?CAACw))?; where each Cv,w)EE MCCv,w)) is evaluated using the P(?Cv,wl? obtai?ed in C5). R Let G' - R 5 r s(Gr?C) be defined for e --H (u,v?, u ? v, v,'n. 0 Action: if v = r tnen /* see re???rk below */ else /* let (v,w) be the unique edge leaving v begin N(Cv,v)) := w1(v?.M(Cv,v)1; (6) let e' be the new edge created from u to v X(e).M?(v,v)); end 57 If AA is an acceptable assignment to the reduced problem then we can extend AA to an acceptable assignment to the original probl?n by defining AA?) M(Cv,w)) CAA(w)); where ?`((v,w)) is evaluated using the ?Cv,w)) obtained in (6). Remark: If Gr E Y SGCk) and the return node r has a unique entering edge e then the graph obtained from G with r and e eliminated ??uld still be in Y and hence can still be reduced to the SG (k) trivial graph. Therefore we nay ass?re that the parser never tries to collapse the return no?e r. If Gr E then eventually we will get the sG(k) graph n0 e r and then we simply do the following: M(e) W1Cn0)?N(e); AA(r) x0; AA(n0) ?(e) fx0); Notice that, in the above actions, M((x,y)) is updated by W1(x) only when node x is about to be eliminated by the parser. Therefore the infornation stored in W1(x) ?i11 be andled properly 1? a 4.10 eoebi?s us to a.? le W1 ? redbctiofls effic(entiy. 58 Theorem4.11: tet RIP CGr,D,M,x0) be a reverse information propa- gation problen. If G = CN E,n0) E and D is fast then r SCk) an acceptable assignment to RIP can be found using o(JE!? fuctional operations. Proof: The action on each reduction described above uses only a bounded nuinber of functional operations. Then the theorem follows fro:n Theoren 4.6. 5 5 Sur?nary Extending the results of Graham and Weqnan we show how reverse infor:nation propagation problens on reducible graphs can be solved without introduc?ng reverse transformations The arbitrary boundary formulation of flow problens is quite natural and could be useful in doing flow analysis on subroutines or in assertion search in progran proving tools. The weighting technique used in flow analysis on SG?) enables us to reduce probless in a non-trivial fashion. ?iL: such weighting technique it is possible to design efficient flow analysis nethods on different classes of flow graphs if reasonably good graph parsers are available. -- - - - - ACKNOWL?DGEM?t?Ts I like to ackn?ledge Alan Dezners for his critical c?mments on a draft of this paper and his suggestions on the presentation of algorithns 59 rAi. tAs] EASUJ ?ibl1o?n? Allen, F.F., "Control Flow Analysis", AGN SiGPLAN Notices (newsletter) 5:7, July 1970, pp71=79. Ashcroft, E. and N?nna, Z., "Translating Program Schenas to while-Schemes", SlAM J. Cc'"put., 4:2, June 1975, pp. 125-146. 60 Aho, A.V., Sethi, R. and Ullean, J.D., "Code notini--H "ation and Finite Churc?-P.osser Systems", TP.-92, Computer Sci. Lab., Dept. of E. E., Princeton tJniv. N.J., 1971. tAuli Ano, A.V. and UlInan, J.D., TheTheoryofParsing, TranslationandConpilin?, Prentice Fall, Englewoof Cliffs, N.J., 1973. [AU23 Aho, A.V. and Ulloan, J.D., "Node Listings for Reducible Grap??, Troc. 7th Anni. ACA. Syrposius on Theory of Computing, May 1975, pp. 177-185. fBJJ ?ohm, c. and Jacopini, G., "Fl? Diagrams, Turing Machines, and Languages with only Two Formulation Rules", CACM, 19:5, May 1966, pp. 366--H371. (Ci Cooke, J., "Global Co?on Subexprasalon E1i?inationw, ACM SIGPLAN Notices (newsletter), 5:7, July 1970, pp. 20--H24. [CS] Cocke, J. and Schwartz, J.T., ProgranningLanguaces andTheirConoilers, Courant Institute, N.Y. New York, 13,C. tFKZl tFKU] Farrow, R., ?nnedy, K. and Zucconi, t., "Graph Gra?ars and Global Prccr? Data Flow Analysis", Proc. 17th lEE Syrposiun on Foundati?r.s of Conputer Science, Houston, Texas, Oct 1976, pp. 42-56. Fong, A., Earn, J. and Ulloan, J.D., "Applicatiors of Lattice Aloobra to Loop , Cor.f??enra Recort 0 ? ?no. ACY S??t?51? or P?i.- Lpies ?rograrn?no- an??ages, Oar. 195, pp. 1-9. (GWl Grahar., S.L. and ?eg"an, M., "A ra?t and Usually Linear Algorith for Global Flow Ana1?"is", L. A?, 23:1, Jan. 1976, pp. 172--H202. jFUlj' n..echt, ."?.S. an IThar, O?D., "0 rap Reduciblity", S?A' J. C?r?ut. 1:2, 0,: 1972, pp. l'8--H202. tHu21 61 Hecht, M.S. and Ullean, J.D., "Analysis of a Simple Algorit? for Glohal Flow Analysis", Proc. ACM Conf. on Principles of Prograrning Languages, noston, Mass., Oct. 1973, pp. 207--H217. [BU3J vecht, M.S. and Ull:"an, J.D., "Characterizations of Reducible Graphs", J. ACM, 21:3, July 1974, pp. 367- 375. fHUJ Ixull Hopcroft, J.?. and Ulirnan, J.D., "An nlogn Algoritnm for Reduction of Flow Graphs", Proc. 6th Annl. Princeton conf. on Information Sciences and Systen's, 1972. Earn, J.B. and Uliman, J.D., "Global Optimization and Iterative Algoritins", TR-146, Computer Sci. Lab., Dept. of E.E., Princeton Univ., Princeton, N.J., Jan. 1974. fKU2J Earn, J.B. and Ullean, J.D., "Monotone Data Flow Analysis Frameworks", TR-169, Co'"puter Sci. Lab., Dept. of E.E., Princa?n Univ., Princeton, N.J., Jan. 1975. Ixel Kennedy, K., "Node Listings Applied to Data Flow Analysis", Conf. Record of 2nd?A? Symposium on Principles o? Prograsmin" Languages, Jan. 1975, pp. 10--H21. rxii Kildall, G.A., "A Unified Approach to Global Proe?aa Optimization", Proc. ACM SIGACT?SI0PIA?? Symposium on Principles of Prograimr?ing tanguages, Boston, Mass., Oct, 1973, pp. 194--H206. fT3 Tarian, R.E., "Deptn-?irst Search and Linear Graph Algorith"s", S?'4 J. Ccnput.,?1:2, Sept. 1972, pp. 146--H160. [Sel Sethi, R., "Testing for Church-Rosser Property", JACM, 21,4, Oct. 1974. (Ul Uliman, J.D., "Fast Alqorithn for the Elimination of Common Subexpressions", Acta lnfor"at?ca, 2:3, Dec. 1973, pp. 191--H123. fwi? Wirth, N., "On the Composition of Well-structured Prograins", Con utin Surveys, 6:4, Dec. 1974.