Slicing Shared-Memory Concurrent Programs The Threaded System Dependence Graph Revisited
Carlos Galindo, Marisa Llorens, Sergio Pérez, Josep Silva · 2023
Program slicing is a program analysis technique to identify the parts of a program that can influence the values computed at a given program point. Its application to concurrent programs with shared memory revealed a new program dependence between threads called interference and uncovered some problems associated with concurrent executions such as time travel. To solve these problems, a new program representation for slicing concurrent programs was proposed: the threaded System Dependence Graph (tSDG), which aimed at solving the time travel problem and to provide context-sensitive slices for concurrent programs. In this paper, we show that the problem remains unsolved because the tSDG is not context-sensitive in some situations. We give a counterexample for the tSDG and identify situations where the tSDG is imprecise, generating context-insensitive slices for concurrent programs. To solve these imprecisions, we redesign the tSDG to become context-sensitive in those situations, solving the inaccuracy problem and preserving the solution to time travel. The new program representation is always as precise as the previous tSDG, and sometimes it is more precise. That is, the slices computed with the new graph are always smaller or equal than those computed with the previous tSDG.