XX:12 Program Tailoring:Slicing by Sequential Criteria TD:Top-Down Analysis TD computes a global property,PAVAlL,for every node n in GIcFG,forwards along the control flow,starting from ENTRY and visiting only the nodes reachable in BU.The basic idea is simple.A statement sequence SE SCp starts at ENTRY and flows forwards along the control flow and ends up with its first statement car(S)removed on encountering the node representing car(S).Therefore,a node n is included in the tailored program T(SCp)if the remaining suffix of S that flows to the entry of a node n appears also in PANTIout (n)or the entire sequence S has been removed upon reaching n(when P in SCp appears in a control-flow cycle).Formally,PAVAlLi(n)computes the set of suffixes s ED to represent implicitly (for efficiency reasons)the fact that their corresponding prefixes p,such that p+s=S for some SE SCp,are partially available at the entry of n. As all the sequences in SCp\PANTIout (ENTRY)have been filtered out by BU,we only need to focus on the ones partially anticipable at ENTRY.Hence,our initialization is: PAVAILi(ENTRY)=SCP n PANTIu(ENTRY) (7) The transfer equations at a non-ENTRY node in GICFG are given by: PAVAILi(n)=PAVAILO(n') (8) n'∈pred(n) PAVAILou(n)= ∫GENo(n)if PANTIou(n)≠O (9) 1☑ otherwise During the top-down pass,we only need to visit a node n if n is reachable during the bottom-up pass,which happens when PANTIout(n). Unlike GENu,GENo may preserve/kill an old data-fact and generate some new ones: GENrD(n)= ADD-SUFFIX-EXPECTED-TO-SEErD(n,s) (10) EPAVAILin(n) As a suffix s EPAVAlLin(n)represents the fact that its corresponding prefix p,such that p+s=S for some SE SCp,is partially available at the entry of n,we have: ADD-SUFFIX-EXPECTED-TO-SEE,(n,)=otherwise ∫{cdrs)}if car(s)=n (11) There are two cases.If car(s)=n,then cdr(s)is generated,indicating that p+n is partially available at the exit of n.At the same time,s is killed(for efficiency not correctness),as s would be redundantly propagated otherwise.If car(s)n,then s is simply preserved. Example 3.Figure 5 illustrates the TD pass with the data-flow results shown.We start with PAVAILin(ENTRY)=SCnPANTIout(ENTRY)={ncw}and finish with PAVAILin(EXIT)= PAVAILin(12)={ncw,w).At node 27,PAVAILout(27)={w},since PAVAILi(27)={cw}. Tailored Program Finally,a node n is included in T(SCp)if TAlLORED(n)holds: TAILORED(n)=PAVAILi(n)nPANTIout(n)VeE PAVAILi(n) (12) The first disjunct suffices if P in SCp is not in a cycle(in GICFG).If s E PAVAlLin(n)n PANTIout(n),then a prefix p,such that p+s=S for some SE PAVAlLin(ENTRY),is partially available at the entry of n,then n must be in T(SCp),since it lies on a path passing through all statements in S.If P is in a cycle,then the whole sequence S that starts at ENTRY ends up being removed eventually,resulting in eE PAVAILin(n).Then n should be included in T(SCp)as well.Note that e PANTIout(n)by Lemma 1.XX:12 Program Tailoring: Slicing by Sequential Criteria TD: Top-Down Analysis TD computes a global property, PAVAIL, for every node n in GICFG, forwards along the control flow, starting from ENTRY and visiting only the nodes reachable in BU. The basic idea is simple. A statement sequence S ∈ SC P starts at ENTRY and flows forwards along the control flow and ends up with its first statement car(S) removed on encountering the node representing car(S). Therefore, a node n is included in the tailored program T (SC P ) if the remaining suffix of S that flows to the entry of a node n appears also in PANTIout(n) or the entire sequence S has been removed upon reaching n (when P in SC P appears in a control-flow cycle). Formally, PAVAILin(n) computes the set of suffixes s ∈ D to represent implicitly (for efficiency reasons) the fact that their corresponding prefixes p, such that p ++ s = S for some S ∈ SC P , are partially available at the entry of n. As all the sequences in SC P \ PANTIout(ENTRY) have been filtered out by BU, we only need to focus on the ones partially anticipable at ENTRY. Hence, our initialization is: PAVAILin(ENTRY) = SC P ∩ PANTIout(ENTRY) (7) The transfer equations at a non-ENTRY node in GICFG are given by: PAVAILin(n) = [ n0∈pred(n) PAVAILout(n 0 ) (8) PAVAILout(n) =  GENTD(n) if PANTIout(n) 6= ∅ ∅ otherwise (9) During the top-down pass, we only need to visit a node n if n is reachable during the bottom-up pass, which happens when PANTIout(n) 6= ∅. Unlike GENBU, GENTD may preserve/kill an old data-fact and generate some new ones: GENTD(n) = [ s ∈ PAVAILin(n) ADD-SUFFIX-EXPECTED-TO-SEETD(n, s) (10) As a suffix s ∈ PAVAILin(n) represents the fact that its corresponding prefix p, such that p ++ s = S for some S ∈ SC P , is partially available at the entry of n, we have: ADD-SUFFIX-EXPECTED-TO-SEETD(n, s) =  {cdr(s)} if car(s) = n {s} otherwise (11) There are two cases. If car(s) = n, then cdr(s) is generated, indicating that p++ n is partially available at the exit of n. At the same time, s is killed (for efficiency not correctness), as s would be redundantly propagated otherwise. If car(s) 6= n, then s is simply preserved. I Example 3. Figure 5 illustrates the TD pass with the data-flow results shown. We start with PAVAILin(ENTRY) = SC w ∩ PANTIout(ENTRY) = {ncw} and finish with PAVAILin(EXIT) = PAVAILin(12) = {ncw, w}. At node 27, PAVAILout(27) = {w}, since PAVAILin(27) = {cw}. Tailored Program Finally, a node n is included in T (SC P ) if TAILORED(n) holds: TAILORED(n) = PAVAILin(n) ∩ PANTIout(n) 6= ∅ ∨  ∈ PAVAILin(n) (12) The first disjunct suffices if P in SC P is not in a cycle (in GICFG). If s ∈ PAVAILin(n) ∩ PANTIout(n), then a prefix p, such that p ++ s = S for some S ∈ PAVAILin(ENTRY), is partially available at the entry of n, then n must be in T (SC P ), since it lies on a path passing through all statements in S. If P is in a cycle, then the whole sequence S that starts at ENTRY ends up being removed eventually, resulting in  ∈ PAVAILin(n). Then n should be included in T (SC P ) as well. Note that  /∈ PANTIout(n) by Lemma 1