Idempotent Backward Slice

Have you ever wondered what programmers ask themselves when they need to fix a bug in a program? They need to understand how the program’s variables, functions, and data structures interact with each other. However, a program can be very large, and one doesn’t need to cover all instructions to fix a specific issue. Therefore, they can limit the scope of the search by selecting just a subset of instructions used to compute a given value at a program point. This subset of instructions is called a program slice [3], and it is an executable program that, given an input value, will always produce an output at the end of its execution.

Following the problem statement, we provide some definitions to contextualize our discussion. Then, we present an algorithm to show how we compute idempotent slices backwardly. Finally, we conclude this study in the respective section.

Note: this post references a video I produced as part of a series on compiler research topics, available on the Compilers Laboratory’s YouTube channel.

Problem Statement

Given a slice criterion, the goal is to compute all data and control dependencies backwardly in the CFG of a program. A slice criterion typically consists of a specific program point and a set of variables of interest at that point.

By analyzing the program’s CFG, we can identify all instructions that directly or indirectly affect the values of these variables at the given program point. This involves tracing both data dependencies, which capture how data values are propagated through the program, and control dependencies, which capture how the execution flow of the program is influenced by conditional statements.

The result is a backward slice, a subset of the program that includes only the relevant instructions needed to understand the behavior of the variables at the specified program point. Additionally, the new slice must be idempotent [1], meaning that given the same input, the program must consistently return the same value.

Formal Definitions

Control Flow Graph

A program is represented as a control flow graph (CFG):

• A digraph \(G = (N, E)\) consists of:
  • \(N\): set of program statements (nodes).
  • \(E\): directed edges representing control flow between statements.
• A flowgraph \((N, E, n_0)\) is a digraph where \(n_0\) is the entry node, and every node is reachable from \(n_0\).
• A hammock graph \((N, E, n_0, n_e)\) is a flowgraph with a unique exit node \(n_e\).
• Dominance: a node \(m\) dominates \(n\) if every path from \(n_0\) to \(n\) passes through \(m\).
• Post Dominance: \(m\) post dominates \(n\) if every path from \(n\) to \(n_e\) passes through \(m\).

Program Variables

Let \(V\) be the set of variables in a program \(P\). For each statement \(n\):

• \(\text{REF}(n)\): set of variables used at \(n\).
• \(\text{DEF}(n)\): set of variables modified at \(n\).

State Trajectory

A state trajectory of length \(k\) is a sequence: \((n_1, s_1), (n_2, s_2), ..., (n_k, s_k)\) where each \(n_i\) is a statement and each \(s_i\) is a mapping of variables to values.

Slicing Criterion

A slicing criterion \(C = (i, V)\) specifies:

• \(i\): a statement index where slicing occurs.
• \(V\): a subset of variables observed at \(i\).

Projection Function

A projection function extracts only relevant information from a state trajectory: \(\text{Proj}_{(i,V)}(n, s) = \begin{cases} (n, s \mid V), & \text{if } n = i \\ X, & \text{otherwise} \end{cases}\)

where \(s \mid V\) restricts \(s\) to the variables in \(V\).

For a trajectory \(T\), we apply: \(\text{Proj}_{(i,V)}(T) = \text{Proj}_{(i,V)}(t_1) ... \text{Proj}_{(i,V)}(t_n).\)

Definition of a Slice

A slice \(S\) of a program \(P\) satisfies:

1. \(S\) is obtained by deleting zero or more statements from \(P\).
2. \(S\) produces the same projection as \(P\) for all inputs where \(P\) terminates.

Algorithm

Although Weiser [3] proofs that there is no algorithm to compute statement-minimal slices, it is possible to use data and control flow analysis to approximate the computation of program slices.

Step 1: Compute Directly Relevant Variables

Define \(R_C(n)\), the set of relevant variables at statement \(n\): \(R_C(n) = \begin{cases} V, & \text{if } n = i \\ \{ v \mid v \in \text{REF}(n) \text{ and } w \in \text{DEF}(n) \cap R_C(m) \}, & \text{if } m \text{ is a successor of } n \end{cases}\)

This ensures that variables affecting \(V\) at \(i\) are traced back through the program.

Step 2: Identify Control Dependencies

A statement \(b\) influences a statement \(s\) if it controls whether \(s\) executes. Define INFL as: \(\text{INFL}(b) = \{ n \mid n \text{ is on a path from } b \text{ to its nearest post dominator} \}.\)

All statements affecting any \(n \in S_C\) are included in the slice.

Step 3: Construct the Slice

The final slice \(S_C\) consists of all statements where: \(R_C(n+1) \cap \text{DEF}(n) \neq \emptyset.\)

Conclusion

In this study, we have explored the concept of idempotent backward slicing, a powerful technique for program analysis and debugging. By defining key terms and presenting the problem statement, we have laid the groundwork for understanding how backward slices can be computed to isolate relevant instructions in a program. The definitions provided offer a clear framework for grasping the intricacies of slicing and its importance in analyzing program dependencies.

The algorithm section detailed the step-by-step process of computing idempotent backward slices. By following this algorithm, practitioners can effectively apply the technique in their program analysis tasks, ensuring that they can isolate and understand the critical parts of a program that influence specific variables at a given point.

In conclusion, idempotent backward slicing is an essential tool for developers and researchers, allowing them to focus on the critical parts of a program that influence specific variables at a given point. By ensuring that the slices are idempotent, we guarantee that the analysis is reliable and repeatable, providing consistent results for the same input. This study serves as a foundation for further exploration and application of slicing techniques in various domains of software engineering.

We encourage readers to refer to the provided references for a deeper understanding of the theoretical underpinnings and historical development of program slicing. The ongoing research and advancements in this field continue to enhance our ability to analyze and debug complex software systems efficiently.

References

[1] Rosen, Kenneth H., and Kamala Krithivasan. Discrete Mathematics and Its Applications. 7. ed., Global ed, McGraw-Hill, 2013.

[2] Tip, Frank. A Survey of Program Slicing Techniques. CWI (Centre for Mathematics and Computer Science), NLD. 1994.

[3] Weiser, Mark. Program Slicing. IEEE Transactions on Software Engineering, vol. SE-10, no. 4, pp. 352–57. 1984.