Y.Li,T.Tan,Y.Zhang,and J.Xue XX:11 Below we describe our BU and TD passes,including their finite domain D and data-flow equations used.In both cases,the ordering relation is 2 and the meet operator n is U. All our transfer functions given below are easily seen to be distributive over 2D Domain A SCp is a set of statement sequences ending at the same statement P,with all statements identified by their line numbers (or labels).The domain D for BU and TD is: D=Suffix(S) (1) SESCp where Suffix(S)returns the set of all suffixes of S,including e(the empty string).Note that e is necessary when P appears in a control-flow cycle(i.e.,a loop or recursion).In the IFDS framework,the data-flow facts used are generated on the fly for efficiency reasons. We make use of the car,cdr and cons functions operating on sequences in the standard manner.If s and s'are two sequences,then s+s'returns the concatenation of s and s'. Graph Representation The BU and TD passes operate on the GICFG representation of a program.Without loss of generality,we assume that a node,i.e.,basic block in GIcFG contains one single statement.Thus,a node and the statement represented by it are used interchangeably.Let ENTRY be the entry node of GIcrG and EXIT be the node for P in SCp.Given a node n,succ(n)(pred(n))is the set of its successors (predecessors)in GIcrG. BU:Bottom-Up Analysis BU computes a global property,PANTI,for every node n in GIcFC,backwards against the control flow,starting at EXIT.PANTIou(n)represents the set of suffixes in D that are partially anticipable at the entry of n,i.e.,that appear on some outgoing path of n ending at EXIT.Thus,we have the following initialization at EXIT: PANTIO(EXIT)={P} (2) which means that our point of interest P in SCp is partially anticipable at the entry of EXIT. The transfer equations at a node n in GICFG are given by: PANTIin(n)=PANTIOut(n) (3) n'∈succ(n) PANTIout (n)=GEN2U(n)UPANTI(n) (4) Due to the presence of PANTIin(n)in(4),whatever is anticipable at the exit of n are also anticipable at the entry of n.No old data-flow facts(i.e.,known suffixes)are killed,because some sequences in SCp may share some common suffixes but have different prefixes.GENou is applied to generate all the new suffixes partially anticipable at a node: GENa0(n)=U ADD-SUFFIX-SEENa0(n,s) (5) sEPANTIiT(n) Given a partially anticipable suffix s at the exit of a node n,cons(n,s)will also be partially anticipable at the entry of n if cons(n,s)ED.Hence,we have: ADD-SUFFIX-SEEN(n,)=(cons(n,s)}if cons(n,s)ED (6) otherwise The following lemma follows immediately from the data-flow equations(2)-(6) Lemma 1.For any node n,e PANTIi(n)and eg PANTIout (n)always hold. Example 2.Figure 5 illustrates the BU pass with the data-flow results shown.We start with PANTIout (EXIT)=PANTIout (12)={w}and finish with PANTIout (ENTRY)={ncw,cw,w}. EC00P2016Y. Li, T. Tan, Y. Zhang, and J. Xue XX:11 Below we describe our BU and TD passes, including their finite domain D and data-flow equations used. In both cases, the ordering relation v is ⊇ and the meet operator u is ∪. All our transfer functions given below are easily seen to be distributive over 2 D. Domain A SC P is a set of statement sequences ending at the same statement P, with all statements identified by their line numbers (or labels). The domain D for BU and TD is: D = [ S∈SCP Suffix(S) (1) where Suffix(S) returns the set of all suffixes of S, including  (the empty string). Note that  is necessary when P appears in a control-flow cycle (i.e., a loop or recursion). In the IFDS framework, the data-flow facts used are generated on the fly for efficiency reasons. We make use of the car, cdr and cons functions operating on sequences in the standard manner. If s and s 0 are two sequences, then s ++ s 0 returns the concatenation of s and s 0 . Graph Representation The BU and TD passes operate on the GICFG representation of a program. Without loss of generality, we assume that a node, i.e., basic block in GICFG contains one single statement. Thus, a node and the statement represented by it are used interchangeably. Let ENTRY be the entry node of GICFG and EXIT be the node for P in SC P . Given a node n, succ(n) (pred(n)) is the set of its successors (predecessors) in GICFG. BU: Bottom-Up Analysis BU computes a global property, PANTI, for every node n in GICFG, backwards against the control flow, starting at EXIT. PANTIout(n) represents the set of suffixes in D that are partially anticipable at the entry of n, i.e., that appear on some outgoing path of n ending at EXIT. Thus, we have the following initialization at EXIT: PANTIout(EXIT) = {P} (2) which means that our point of interest P in SC P is partially anticipable at the entry of EXIT. The transfer equations at a node n in GICFG are given by: PANTIin(n) = [ n0∈succ(n) PANTIout(n 0 ) (3) PANTIout(n) = GENBU(n) ∪ PANTIin(n) (4) Due to the presence of PANTIin(n) in (4), whatever is anticipable at the exit of n are also anticipable at the entry of n. No old data-flow facts (i.e., known suffixes) are killed, because some sequences in SC P may share some common suffixes but have different prefixes. GENBU is applied to generate all the new suffixes partially anticipable at a node: GENBU(n) = [ s ∈ PANTIin(n) ADD-SUFFIX-SEENBU(n, s) (5) Given a partially anticipable suffix s at the exit of a node n, cons(n, s) will also be partially anticipable at the entry of n if cons(n, s) ∈ D. Hence, we have: ADD-SUFFIX-SEENBU(n, s) =  {cons(n, s)} if cons(n, s) ∈ D ∅ otherwise (6) The following lemma follows immediately from the data-flow equations (2) – (6). I Lemma 1. For any node n,  /∈ PANTIin(n) and  /∈ PANTIout(n) always hold. I Example 2. Figure 5 illustrates the BU pass with the data-flow results shown. We start with PANTIout(EXIT) = PANTIout(12) = {w} and finish with PANTIout(ENTRY) = {ncw, cw, w}. E COO P 2 0 1 6