Context-sensitive analyses enable the precise analysis of programs with procedures, such that only the relevant procedures will be selected, because the calling context is being taken into account. In threaded programs, interference dependence models the efects of concurrent assignments and access to shared variables, but current definitions of this dependence prevent context-sensitivity. Our work redefines interference dependence in order to make it compatible with known context-sensitive analyses, enabling more precise analyses.
In the software engineering field of static analysis, context-sensitivity is a property that determines whether an analysis is able to distinguish the diferent calls made to a function, and only analyse the relevant ones. A context-sensitive analysis can produce faster and/or better results, by being able to ignore calls that are irrelevant to the question asked.
A common representation used to tackle software analyses are dependence graphs, which
represent instructions in a program as nodes and the relationships or dependences between
them as directed arcs. For example, interference dependence (denoted with ‧‧➡) is a relationship
that connects a variable definition and a variable usage in diferent parallel threads. It is useful
in the analysis of shared-memory concurrent programs. It was originally defined for program
slicing by Krinke [
Context-sensitive analyses can be performed in multiple ways. A simple but expensive method is to label each call and store the sequence of call labels that have already been analysed,
Enter f()
Enter g()
Enter f()
Enter g() DEF
USE
DEF
USE
but this leads to an explosion of states which makes the analysis too expensive. An alternative
is the use of summary edges, first proposed by Horwitz et al. [
In interference dependence, when a source of dependence is reached, all its dependences are transitively required (except for other interference dependences, which are analysed on a case-by-case basis), removing any restriction imposed by other aspects of the analysis, including context-sensitivity. Both requirements are conflictive, and thus the analysis can either consider interference or be context-sensitive.
Some authors, like Krinke [
Our approach is a redefinition of interference dependence, such that every instance of it appears between threads of the same procedure (removing all interprocedural jumps that break the calling context). However, interprocedural interference dependences must also be represented, and we designed a structure of dependences similar to the one generated by summaries. This allows us to use a system similar to Horwitz et al.’s, and produce context-sensitive interference dependences.
As an example, let’s observe the structures in the left side of Figure 1, in which a main procedure spawns two threads (A and B). Thread A calls procedure f, while thread B calls procedure g. Concurrently, a variable is defined in f (thread A) and used in g (thread B). Thus, an interference dependence connects the definition to the usage (marked as DEF and USE in the graphs, respectively).
Nanda and Ramesh’s approach place the interference dependence directly between the definition and the usage, making it an interprocedural dependence (shown as a dotted arc, it crosses the boundaries of a procedure, from f to g). As a consequence, since all the dependences of the definition are transitively required by the analysis, it is impossible to determine which calls to f are relevant and which are not, resulting in the analysis not being context-sensitive.
On the right side of Figure 1 we see our approach, which creates auxiliary nodes (pink and dashed) and arcs (vertical and dashed) to move the interference dependence from the real definition and usage to each of the calls to the procedures that perform these actions. The horizontal dotted arc represents the interference dependence, which is now intraprocedural. As a side-efect of this transformation, there is no doubt about which of the two calls to f in thread A produces the interference dependence, and we can take advantage of Horwitz et al.’s context-sensitivity framework.
In summary, our approach redefines interference dependence to be exclusively intraprocedural. It also generates new nodes that can trace the sequence of calls that link a concurrent definitionusage of a variable. With these two elements, our approach results in a context-sensitive analysis of concurrent programs, applying the framework of summaries laid out by Horwitz et al.
This work has been partially supported by the EU (FEDER) and the Spanish MCI/AEI under grant PID2019-104735RB-C41, and by the European Union’s Horizon 2020 research and innovation programme under grant agreement No 952215 (Tailor).