### Analysis

Uday Khedker

Department of Computer Science and Engineering, Indian Institute of Technology, Bombay

## About These Slides

These slides constitute the lecture notes for CS618 Program Analysis course at IIT Bombay and have been made available as teaching material accompanying the book:

• Uday Khedker, Amitabha Sanyal, and Bageshri Karkare. Data Flow Analysis: Theory and Practice. CRC Press (Taylor and Francis Group).

2009.

Apart from the above book, some slides are based on the material from the following books

• S. S. Muchnick and N. D. Jones. Program Flow Analysis. Prentice Hall Inc. 1981.

These slides are being made available under GNU FDL v1.2 or later purely for

## Value Based Termination

## of Call String Construction

• Value based termination of call string construction (VBTCC) No need to construct call strings upto a fixed length

• Only as many call strings are constructed as are required

• Significant reduction in space and time

• Worst case call string length becomes linear in the size of the lattice instead of the original quadratic

All this is achieved by a simple change without compromising on the precision, simplicity, and generality of the classical method

Uday P. Khedker and Bageshri Karkare. Efficiency, Precision, Simplicity, and Generality in Interprocedural Data Flow Analysis: Resurrecting the Classical

• These slides are aimed at

◮ teaching rather than making a short technical presentation,

◮ It is assumed that the people going through these slides do not have the benefit of attending the associated lectures

• Hence these slides are verbose with plenty of additional comments (usually not found in other slides)

Required length of the call string is:

• K for non-recursive programs

• K ·(|L|+ 1)^{2}for recursive programs

M. Sharir and A. Pnueli. Two Approaches to Interprocedural Data Flow Analysis. InProgram Flow Analysis: Theory and Applications. S. S. Muchnick and N. D. Jones (Ed.) Prentice-Hall Inc. 1981.

Sp

Ci

Ri

Ep

Sq

Eq

Call q

Sp

Ci

Ri

Ep

Sq

Eq

Call q We will

• first work out the conventional call strings method on the example program,

• make useful observations about how it works, and

• convert it to VBTCC based call strings method

Sp

Ci

Ri

Ep

Sq

Eq

Call q σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

σ4

x_{3}^{′}
σ3

x_{1}^{′}
σ2

x_{1}^{′}
σ1

x_{1}^{′}
σ0

x_{0}^{′}

• Call strings remain same

• Associated data flow values may change

• Since the data flow values ofσ1 andσ2

were identical atSp, they must remain identical atCi too

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

σ4

x_{3}^{′}
σ3

x_{1}^{′}
σ2

x_{1}^{′}
σ1

x_{1}^{′}
σ0

x_{0}^{′}

σ0ci

x_{0}^{′}
σ1ci

x_{1}^{′}
σ2ci

x_{1}^{′}
σ3ci

x_{1}^{′}
σ4ci

x_{3}^{′}

• Call strings have been updated by suffixing the call site

• Associated data flow values remain same

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

σ4

x_{3}^{′}
σ3

x_{1}^{′}
σ2

x_{1}^{′}
σ1

x_{1}^{′}
σ0

x_{0}^{′}

σ0ci

x_{0}^{′}
σ1ci

x_{1}^{′}
σ2ci

x_{1}^{′}
σ3ci

x_{1}^{′}
σ4ci

x_{3}^{′}

• Call strings remain same

• Associated data flow values may change

• Since the data flow values ofσ1,σ2, and σ3were identical atSq, they must remain identical atEq too

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

σ4

x_{3}^{′}
σ3

x_{1}^{′}
σ2

x_{1}^{′}
σ1

x_{1}^{′}
σ0

x_{0}^{′}

σ0ci

x_{0}^{′}
σ1ci

x_{1}^{′}
σ2ci

x_{1}^{′}
σ3ci

x_{1}^{′}
σ4ci

x_{3}^{′}

σ0ci

y_{0}^{′}
σ1ci

y_{1}^{′}
σ2ci

y_{1}^{′}
σ3ci

y_{1}^{′}
σ4ci

y_{3}^{′}
σ4

y_{3}^{′}
σ3

y_{1}^{′}
σ2

y_{1}^{′}
σ1

y_{1}^{′}
σ0

y_{0}^{′}

• Call strings have been updated by removing the last call site

• Associated data flow values remain same

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

σ4

x_{3}^{′}
σ3

x_{1}^{′}
σ2

x_{1}^{′}
σ1

x_{1}^{′}
σ0

x_{0}^{′}

σ0ci

x_{0}^{′}
σ1ci

x_{1}^{′}
σ2ci

x_{1}^{′}
σ3ci

x_{1}^{′}
σ4ci

x_{3}^{′}

σ4

y_{3}^{′}
σ3

y_{1}^{′}
σ2

y_{1}^{′}
σ1

y_{1}^{′}
σ0

y_{0}^{′}

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

σ4

x_{3}^{′}
σ3

x_{1}^{′}
σ2

x_{1}^{′}
σ1

x_{1}^{′}
σ0

x_{0}^{′}

σ0ci

x_{0}^{′}
σ1ci

x_{1}^{′}
σ2ci

x_{1}^{′}
σ3ci

x_{1}^{′}
σ4ci

x_{3}^{′}

σ0ci

y_{0}^{′}
σ1ci

y_{1}^{′}
σ2ci

y_{1}^{′}
σ3ci

y_{1}^{′}
σ4ci

y_{3}^{′}
σ4

y_{3}^{′}
σ3

y_{1}^{′}
σ2

y_{1}^{′}
σ1

y_{1}^{′}
σ0

y_{0}^{′}

σ0

y0

σ1

y1

σ2

y1

σ3

y1

σ4

y3

• Call strings remain same

• Associated data flow values could change

• All call strings that had identical values atSp, have identical values atEpalso

Sp

Ci

Ri

Ep

Sq

Eq

Call q σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

σ4

x_{3}^{′}
σ3

x_{1}^{′}
σ2

x_{1}^{′}
σ1

x_{1}^{′}
σ0

x_{0}^{′}

σ0ci

x_{0}^{′}
σ1ci

x_{1}^{′}
σ2ci

x_{1}^{′}
σ3ci

x_{1}^{′}
σ4ci

x_{3}^{′}

σ4

y_{3}^{′}
σ3

y_{1}^{′}
σ2

y_{1}^{′}
σ1

y_{1}^{′}
σ0

y_{0}^{′}

• Data flow value invariant : Ifσ1andσ2 have equal values atSp, then

• Data flow value invariant : Ifσ1andσ2 have equal values atSp, then

◮ sinceσ1andσ2are transformed in the same manner by traversing the same set of paths,

◮ the values associated with them will also be transformed in the same manner and will continue to remain equal atEp.

• Data flow value invariant : Ifσ1andσ2 have equal values atSp, then

◮ sinceσ1andσ2are transformed in the same manner by traversing the same set of paths,

◮ the values associated with them will also be transformed in the same manner and will continue to remain equal atEp.

• We can reduce the amount of effort by

◮ Partitioning the call strings atSp for each procedurep

◮ Replacing all call strings in an equivalence class by its id

◮ Regenerating call strings atEp by replacing equivalence class ids by the call strings in them

• Data flow value invariant : Ifσ1andσ2 have equal values atSp, then

◮ sinceσ1andσ2are transformed in the same manner by traversing the same set of paths,

◮ the values associated with them will also be transformed in the same manner and will continue to remain equal atEp.

• We can reduce the amount of effort by

◮ Partitioning the call strings atSp for each procedurep

◮ Replacing all call strings in an equivalence class by its id

◮ Regenerating call strings atEp by replacing equivalence class ids by the call strings in them

• Can the partitions change?

• Data flow value invariant : Ifσ1andσ2 have equal values atSp, then

◮ sinceσ1andσ2are transformed in the same manner by traversing the same set of paths,

• We can reduce the amount of effort by

◮ Partitioning the call strings atSp for each procedurep

◮ Replacing all call strings in an equivalence class by its id

◮ Regenerating call strings atEp by replacing equivalence class ids by the call strings in them

• Can the partitions change?

◮ On a subsequent visit toSp, the partition may be different

◮ The data flow values atEp would also change in a similar manner

◮ The data flow value invariant still holds

Sp

Ci

Ri

E

Sq

Eq

Call q σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

Sp

Ci

Ri

Ep

Sq

Eq

Call q σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

• Call strings are partitioned using data flow values

• A unique id is assigned to each equivalence class

Sp

Ci

Ri

E

Sq

Eq

Call q σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

• Call strings are replaced by class ids

• Data flow values remain same

Sp

Ci

Ri

Ep

Sq

Eq

Call q σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

• Different class ids may get the same data flow value but a given class id has a single data flow value

• The data flow values could change but the class id names remain same

Sp

Ci

Ri

E

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

• Call strings reachingSqhave the call siteci suffixed to class ids created in the callerp

• Data flow values remain same

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

s4 s5 s6

• Call strings are partitioned atSq

• A unique id is assigned to each equivalence class

Sp

Ci

Ri

E

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

s4 s5 s6

s4

x_{0}^{′}
s5

x_{1}^{′}
s6

x_{3}^{′}

• Call strings are replaced by class ids

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

s4 s5 s6

s4

x_{0}^{′}
s5

x_{1}^{′}
s6

x_{3}^{′}

s4

y_{0}^{′}
s5

y_{1}^{′}
s6

y_{3}^{′}

• The data flow values could change but the class id names remain same

Sp

Ci

Ri

E

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

s4 s5 s6

s4

x_{0}^{′}
s5

x_{1}^{′}
s6

x_{3}^{′}

s4

y_{0}^{′}
s5

y_{1}^{′}
s6

y_{3}^{′}

• Call strings are regenerated by replacing the class ids by the call strings in the equivalence class

• Data flow values remain same

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

s4 s5 s6

s4

x_{0}^{′}
s5

x_{1}^{′}
s6

x_{3}^{′}

s4

y_{0}^{′}
s5

y_{1}^{′}
s6

y_{3}^{′}

s0ci

y_{0}^{′}
s1ci

y_{1}^{′}
s2ci

y_{1}^{′}
s3ci

y_{3}^{′}
s3

y_{3}^{′}
s2

y_{1}^{′}
s1

y_{1}^{′}
s0

y_{0}^{′}

• The last call site is removed from the call strings to recover the class ids ofp

• Data flow values remain same

Sp

Ci

Ri

E

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

s4 s5 s6

s4

x_{0}^{′}
s5

x_{1}^{′}
s6

x_{3}^{′}

s4

y_{0}^{′}
s5

y_{1}^{′}
s6

y_{3}^{′}
s3

y_{3}^{′}
s2

y_{1}^{′}
s1

y_{1}^{′}
s0

y_{0}^{′}

s3

s2

s1

s0

Sp

Ci

Ri

Ep

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

s4 s5 s6

s4

x_{0}^{′}
s5

x_{1}^{′}
s6

x_{3}^{′}

s4

y_{0}^{′}
s5

y_{1}^{′}
s6

y_{3}^{′}

s0ci

y_{0}^{′}
s1ci

y_{1}^{′}
s2ci

y_{1}^{′}
s3ci

y_{3}^{′}
s3

y_{3}^{′}
s2

y_{1}^{′}
s1

y_{1}^{′}
s0

y_{0}^{′}

s3

y3

s2

y1

s1

y1

s0

y0

σ0

y0

σ1

y1

σ2

y1

σ3

y1

σ4

y3

• Call strings are regenerated by replacing the class ids by the call strings in the equivalence class

Sp

Ci

Ri

E

Sq

Eq

σ0

x0

σ1

x1

σ2

x1

σ3

x2

σ4

x3

0 1 2 3

s3

x3

s2

x2

s1

x1

s0

x0

s3

x_{3}^{′}
s2

x_{1}^{′}
s1

x_{1}^{′}
s0

x_{0}^{′}

s0ci

x_{0}^{′}
s1ci

x_{1}^{′}
s2ci

x_{1}^{′}
s3ci

x_{3}^{′}

s4 s5 s6

s4

x_{0}^{′}
s5

x_{1}^{′}
s6

x_{3}^{′}

s4

y_{0}^{′}
s5

y_{1}^{′}
s6

y_{3}^{′}
s3

y_{3}^{′}
s2

y_{1}^{′}
s1

y_{1}^{′}
s0

y_{0}^{′}

s3

s2

s1

s0

• An equivalence classsi for a procedurep means that

• An equivalence classsi for a procedurep means that

All call strings in si would have identical data flow values at Ep

• An equivalence classsi for a procedurep means that

All call strings in si would have identical data flow values at Ep

(If two call strings are clubbed together in an equivalence class, they remain clubbed together untilEp is reached)

• An equivalence classsi for a procedurep means that

All call strings in si would have identical data flow values at Ep

(If two call strings are clubbed together in an equivalence class, they remain clubbed together untilEp is reached)

• We start creating equivalence classes atSp

• An equivalence classsi for a procedurep means that

All call strings in si would have identical data flow values at Ep

(If two call strings are clubbed together in an equivalence class, they remain clubbed together untilEp is reached)

• We start creating equivalence classes atSp

• Every visit toSp adjusts the equivalence classes

• An equivalence classsi for a procedurep means that

All call strings in si would have identical data flow values at Ep

• We start creating equivalence classes atSp

• Every visit toSp adjusts the equivalence classes

◮ If a new data flow value is discovered, a new equivalence class is created

◮ If a new call string is discovered, it will be included in an equivalence class based on its data flow value

• An equivalence classsi for a procedurep means that

All call strings in si would have identical data flow values at Ep

• We start creating equivalence classes atSp

• Every visit toSp adjusts the equivalence classes

◮ If a new data flow value is discovered, a new equivalence class is created

◮ If a new call string is discovered, it will be included in an equivalence class based on its data flow value

• It is possible to adjust equivalence classes at internal nodes too However, doing it at each statement may be inefficient

• Work list management as described later

• Correctness requirement:

◮ Whenever representation is performed atSp,Ep must be added to the work list

◮ In caseEp is to be processed but its predecessors have not been put on the work list (Ep may have been added due to representation), discardEp from the work list (has the effect of generating⊤value).

• Efficiency consideration: Process “inner calls” first

• Maintain a stack of work lists for the procedures being analyzed (At most one entry per procedure on the stack)

• Order the nodes in each work list in reverse post order

• Remove the head of work list for the procedure on top (sayp)

◮ If the selected node isSp

◦ Adjust the call string partition based on the data flow values

◦ Replace call strings by class ids

◦ InsertEpin the list forp

◮ If the selected node isCi calling procedureqthen

◦ Bringq on the top of stack

◦ InsertSq as the head of the list ofq

◮ If the selected node isEp

◦ Poppfrom the stack and add its successor return nodes to appropriate work lists

◦ Regenerate the call strings by replacing class ids by the call strings in the class

• Swap the roles ofSp andEp

• Swap the roles ofCi andRi

• Replace reverse post order by post order

• We first make important observations about the role of the length of a call string in recursive contexts in the classical call strings method

• Then we intuitively see how VBTCC serves the same role without actually constructing redundant call strings

• Finally we formally argue that the two methods are equivalent

Sp

Ci

Ri

Call p

• We consider self recursion for simplicity; the principles are general and are also applicable to indirect recursion

Sp

Ci

Ri

Ep

Call p

• We consider self recursion for simplicity; the principles are general and are also applicable to indirect recursion

• Context sensitivity requires processing each recursive path independently

Sp

Ci

Ri

Call p

• We consider self recursion for simplicity; the principles are general and are also applicable to indirect recursion

• Context sensitivity requires processing each recursive path independently

• For a given recursive path

◮ Therecursive call sequence (RCS)refers to the subpath that builds recursion

Sp

Ci

Ri

Ep

Call p

• Context sensitivity requires processing each recursive path independently

• For a given recursive path

◮ Therecursive call sequence (RCS) refers to the subpath that builds recursion

◮ Therecursive return sequence (RRS)refers to the subpath that unfolds recursion

Sp

Ci

Ri

Call p

• Context sensitivity requires processing each recursive path independently

• For a given recursive path

◮ Therecursive call sequence (RCS) refers to the subpath that builds recursion

◮ Therecursive return sequence (RRS) refers to the subpath that unfolds recursion

◮ Therecursion terminating path(RTP)refers to the subpath from RCS to RRS

Sp

Ci

Ri

Ep

Call p

• Context sensitivity requires processing each recursive path independently

• For a given recursive path

◮ Therecursive call sequence (RCS) refers to the subpath that builds recursion

◮ Therecursive return sequence (RRS) refers to the subpath that unfolds recursion

◮ Therecursion terminating path(RTP) refers to the subpath from RCS to RRS

(We assume that a static analysis can assign arbitrary data flow values to the unreachable parts of the program in the absence of an RTP)

Sp

Ci

Ri

Call p xσ0

• Data flow value reaching from outside

Sp

Ci

Ri

Ep

Call p xσ0

• The data flow valuehσ,x0iis propagated over RCS

Sp

Ci

Ri

Call p xσ0

• The data flow valuehσ,x0iis propagated over RCS

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

• The data flow valuehσ,x0iis propagated over RCS

• We get the new contextσci

and the new data flow valuex1

Sp

Ci

Ri

Call p xσ0

σci

x1

• The new pairhσci,x1iis propagated over RCS

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

• The new pairhσci,x1iis propagated over RCS

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

• The new pairhσci,x1iis propagated over RCS

• We gethσcici,x2iatSp

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

σcici

x2

• Now the third pairhσcici,x2i is propagated over RCS

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

• Now the third pairhσcici,x2i is propagated over RCS

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

• Now the third pairhσcici,x2i is propagated over RCS

• We get the new context σcicici atSp

• Assume that the data flow ceases to change

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

• Even if the data flow values do not change any further, we still need to propagate them in RCS in order to build call strings that are sufficiently large

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

• Even if the data flow values do not change any further, we still need to propagate them in RCS in order to build call strings that are sufficiently large

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

• Even if the data flow values do not change any further, we still need to propagate them in RCS in order to build call strings that are sufficiently large

• We need large call strings to allow for all changes in RRS (as will be clear soon)

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

• We need large call strings to allow for all changes in RRS (as will be clear soon)

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

• We need large call strings to allow for all changes in RRS (as will be clear soon)

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

• Assume that we construct all call strings as required by the conventional call strings method

• Many of these call strings are redundant in that they do not correspond to any new data flow value

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

• Assume that we construct all call strings as required by the conventional call strings method

• Many of these call strings are redundant in that they do not correspond to any new data flow value

• In our case, only the first two traversals

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

• Now we traverse the recursion terminating path

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

σ
x_{0}^{′}

σci

x_{1}^{′}
σcici

x_{2}^{′}

σcicici

x_{2}^{′}
σcicicici

x_{2}^{′}

σcicicicici

x_{2}^{′}

• Now we traverse the recursion terminating path

• For simplicity, we propagate only some call strings to Ep(possibly with changed data flow values)

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

σ
x_{0}^{′}

σci

x_{1}^{′}
σcici

x_{2}^{′}

σcicici

x_{2}^{′}
σcicicici

x_{2}^{′}

σcicicicici

x_{2}^{′}
σ

x_{0}^{′}
σci

x_{1}^{′}
σcici

x_{2}^{′}

σcicici

x_{2}^{′}

σcicicici

x_{2}^{′}

σcicicicici

x_{2}^{′}

• The call strings and data flow values reach the exit ofEp

unchanged

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

σ
x_{0}^{′}

σci

x_{1}^{′}
σcici

x_{2}^{′}

σcicici

x_{2}^{′}
σcicicici

x_{2}^{′}

σcicicicici

x_{2}^{′}

σci

x_{1}^{′}
σcici

x_{2}^{′}

σcicici

x_{2}^{′}
σcicicici

x_{2}^{′}

σcicicicici

x_{2}^{′}

• Now we start processing RRS

• The call strings ending withci

and their data flow values reach the entry of Ri unchanged

Sp

Ci

Ri

Ep

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

σ
x_{0}^{′}

σci

x_{1}^{′}
σcici

x_{2}^{′}

σcicici

x_{2}^{′}
σcicicici

x_{2}^{′}

σcicicicici

x_{2}^{′}
σ

x_{0}^{′}
σci

x_{1}^{′}
σcici

x_{2}^{′}

σcicici

x_{2}^{′}

σcicicici

x_{2}^{′}

σcicicicici

x_{2}^{′}

σci

x_{1}^{′}
σcici

x_{2}^{′}

σcicici

x_{2}^{′}
σcicicici

x_{2}^{′}

σcicicicici

x_{2}^{′}
σ

x_{1}^{′′}

σci

x_{2}^{′′}

σcici

x_{2}^{′′}

σcicici

x_{2}^{′′}

σcicicici

x_{2}^{′′}

• Now we start processing RRS

• The call strings ending withci

and their data flow values reach the entry of Ri unchanged

• The last occurrence ofci is removed and the call strings reach the entry ofEp with new data flow values

Sp

Ci

Ri

Call p xσ0

σci

x1

σcici

x2

σcicici

x2

σcicicici

x2

σcicicici. . . x2

σ
x_{0}^{′}⊓x_{1}^{′′}

σci

x_{1}^{′}⊓x_{2}^{′′}

σcici

x_{2}^{′}⊓x_{2}^{′′}

σcicici

x_{2}^{′}⊓x_{2}^{′′}

σcicicici

x_{2}^{′}⊓x_{2}^{′′}

σcicicicici

x_{2}^{′}⊓x_{2}^{′′}

σ
x_{1}^{′′}

σci

x_{2}^{′′}

σcici

x_{2}^{′′}

• We need to merge the data values of corresponding call strings reaching the entry of Ep

fromSp andRi