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)2for 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
x3′ σ3
x1′ σ2
x1′ σ1
x1′ σ0
x0′
• 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
x3′ σ3
x1′ σ2
x1′ σ1
x1′ σ0
x0′
σ0ci
x0′ σ1ci
x1′ σ2ci
x1′ σ3ci
x1′ σ4ci
x3′
• 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
x3′ σ3
x1′ σ2
x1′ σ1
x1′ σ0
x0′
σ0ci
x0′ σ1ci
x1′ σ2ci
x1′ σ3ci
x1′ σ4ci
x3′
• 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
x3′ σ3
x1′ σ2
x1′ σ1
x1′ σ0
x0′
σ0ci
x0′ σ1ci
x1′ σ2ci
x1′ σ3ci
x1′ σ4ci
x3′
σ0ci
y0′ σ1ci
y1′ σ2ci
y1′ σ3ci
y1′ σ4ci
y3′ σ4
y3′ σ3
y1′ σ2
y1′ σ1
y1′ σ0
y0′
• 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
x3′ σ3
x1′ σ2
x1′ σ1
x1′ σ0
x0′
σ0ci
x0′ σ1ci
x1′ σ2ci
x1′ σ3ci
x1′ σ4ci
x3′
σ4
y3′ σ3
y1′ σ2
y1′ σ1
y1′ σ0
y0′
Sp
Ci
Ri
Ep
Sq
Eq
σ0
x0
σ1
x1
σ2
x1
σ3
x2
σ4
x3
σ4
x3′ σ3
x1′ σ2
x1′ σ1
x1′ σ0
x0′
σ0ci
x0′ σ1ci
x1′ σ2ci
x1′ σ3ci
x1′ σ4ci
x3′
σ0ci
y0′ σ1ci
y1′ σ2ci
y1′ σ3ci
y1′ σ4ci
y3′ σ4
y3′ σ3
y1′ σ2
y1′ σ1
y1′ σ0
y0′
σ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
x3′ σ3
x1′ σ2
x1′ σ1
x1′ σ0
x0′
σ0ci
x0′ σ1ci
x1′ σ2ci
x1′ σ3ci
x1′ σ4ci
x3′
σ4
y3′ σ3
y1′ σ2
y1′ σ1
y1′ σ0
y0′
• 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,
◮ 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?
◮ 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
x3′ s2
x1′ s1
x1′ s0
x0′
• 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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
• 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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
s4 s5 s6
s4
x0′ s5
x1′ s6
x3′
• 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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
s4 s5 s6
s4
x0′ s5
x1′ s6
x3′
s4
y0′ s5
y1′ s6
y3′
• 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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
s4 s5 s6
s4
x0′ s5
x1′ s6
x3′
s4
y0′ s5
y1′ s6
y3′
• 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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
s4 s5 s6
s4
x0′ s5
x1′ s6
x3′
s4
y0′ s5
y1′ s6
y3′
s0ci
y0′ s1ci
y1′ s2ci
y1′ s3ci
y3′ s3
y3′ s2
y1′ s1
y1′ s0
y0′
• 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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
s4 s5 s6
s4
x0′ s5
x1′ s6
x3′
s4
y0′ s5
y1′ s6
y3′ s3
y3′ s2
y1′ s1
y1′ s0
y0′
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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
s4 s5 s6
s4
x0′ s5
x1′ s6
x3′
s4
y0′ s5
y1′ s6
y3′
s0ci
y0′ s1ci
y1′ s2ci
y1′ s3ci
y3′ s3
y3′ s2
y1′ s1
y1′ s0
y0′
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
x3′ s2
x1′ s1
x1′ s0
x0′
s0ci
x0′ s1ci
x1′ s2ci
x1′ s3ci
x3′
s4 s5 s6
s4
x0′ s5
x1′ s6
x3′
s4
y0′ s5
y1′ s6
y3′ s3
y3′ s2
y1′ s1
y1′ s0
y0′
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
(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
◮ 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
(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
◮ 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
• 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
◮ Therecursive return sequence (RRS)refers to the subpath that unfolds recursion
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
◮ 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
• 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
◮ 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
• 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
Call p xσ0
σci
x1
σcici
x2
σcicici
x2
σcicicici
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
σ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
σ x0′
σci
x1′ σcici
x2′
σcicici
x2′ σcicicici
x2′
σcicicicici
x2′
• 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
σ x0′
σci
x1′ σcici
x2′
σcicici
x2′ σcicicici
x2′
σcicicicici
x2′ σ
x0′ σci
x1′ σcici
x2′
σcicici
x2′
σcicicici
x2′
σcicicicici
x2′
• 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
σ x0′
σci
x1′ σcici
x2′
σcicici
x2′ σcicicici
x2′
σcicicicici
x2′
σci
x1′ σcici
x2′
σcicici
x2′ σcicicici
x2′
σcicicicici
x2′
• 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
σ x0′
σci
x1′ σcici
x2′
σcicici
x2′ σcicicici
x2′
σcicicicici
x2′ σ
x0′ σci
x1′ σcici
x2′
σcicici
x2′
σcicicici
x2′
σcicicicici
x2′
σci
x1′ σcici
x2′
σcicici
x2′ σcicicici
x2′
σcicicicici
x2′ σ
x1′′
σci
x2′′
σcici
x2′′
σcicici
x2′′
σcicicici
x2′′
• 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
σ x0′⊓x1′′
σci
x1′⊓x2′′
σcici
x2′⊓x2′′
σcicici
x2′⊓x2′′
σcicicici
x2′⊓x2′′
σcicicicici
x2′⊓x2′′
σ x1′′
σci
x2′′
σcici
x2′′
• We need to merge the data values of corresponding call strings reaching the entry of Ep
fromSp andRi
