A Framework for Memory Efficient Context-Sensitive Program Analysis

Static program analysis is an important part of both optimizing compilers and software engineering tools for program verification and model checking. Static analyses approximate the run-time behavior of a given program. This is done by abstracting from the concrete semantics of programs and from concrete values. Such analyses can be context-sensitive or -insensitive, i.e., an analysis may or may not distinguish different analysis results for different execution paths, i.e. different contexts, e.g., different call contexts of a method or alternative intra-procedural executions paths due to control statements. Context-sensitive analyses are, in general, more precise than their context-insensitive counterparts, but also more expensive in terms of time and memory consumption.

With conditional execution, the number of different contexts grows, in general, exponentially with the program size. Adding iterations leads, in general, to countable infinitely many contexts. With the number of contexts grow the analysis time and the memory to capture a mapping of contexts to analysis results. Merging the analyzed information of different contexts reduces the memory consumption at the cost of analysis precision. We should therefore aim for compact representations of the mapping of context to analysis information.

The memory usage problem related to context-sensitive analyses is not just a theoretical issue; several papers, e.g., [19, 25], evaluating various inter-procedural context-sensitive data-flow approaches report severe memory problems when using call context sensitivity with a call-depths k ≥ 2, and the path-explosion problem, e.g., [5, 8], has for a long time been a major issue in program verification and model checking.

In this paper, we present a technique to capture context-sensitive analysis information in general. We do not distinguish between inter-procedural call context sensitivity [34] and intra-procedural trace or path sensitivity [32]. In both cases we map contexts to analysis values for each program point in a memory efficient way. Our approach is based on so-called χ-terms [39, 40] that capture the analysis results of different contexts. The main benefit of χ-terms is that it avoids all syntactic redundancies of sub-terms and values and is, hence, a memory efficient representation of context-sensitive analysis information [12].

We assume a Static Single Assignment (SSA) [10, 29] representation of the programs. We further assume a program analysis following a standard data-flow analysis approach as given, e.g., in [26]. It iterates over an SSA representation of the program and updates the analysis information at each node using the node’s transfer functions until a fixed point is reached. It can be implemented using a worklist initialized with a start node. Iteratively, a node is taken from the worklist, its transfer function is applied, and, if its analysis value has changed, all control-flow dependent nodes are added to the worklist until it is empty.

In SSA graphs, ϕ-nodes are used to select between different definitions of a variable assigned in different control paths of the execution. There is a close relation between ϕ-nodes and χ-terms. We create a new χ-term as the result of the transfer function of a ϕ-node. Each χ-term encodes the various control-flow dependent analysis value options that were available when the transfer function was applied.

The reason why χ-terms are expected to be so memory efficient—and actually turn out to be in practice [12]—in capturing program analysis values is the following. A ϕ-node defines a χ-term that merges the analysis values from p ≥ 2 predecessor paths or contexts, each encoded in one of the p sub-terms. They have been created in the p contexts and, in general, need to be captured as part of the respective context’s analysis result. Instead of creating a whole new χ-term representation, the new term is represented by a new χ-node referring to the p existing χ-sub-term representations. Another advantage of χ-terms is that they capitalize on the redundancy savings during their construction, i.e., while executing the transfer function of the corresponding ϕ-node. This avoids using extensive memory first before redundancies are possibly eventually eliminated. The memory footprint of the χ-term representations just grows monotonically and expensive explicit memory management, i.e, redundancy elimination and garbage collection, is avoided.

Traditionally context-sensitivity is used for both intra- and inter-procedural data-flow analysis. However, for the sake of simplicity, our presentation of χ-terms in Sections 2–5 will focus on intra-procedural context-sensitivity where the various contexts are due to control statements. It is, however, important to notice that χ-terms can be used for any type of SSA-based context-sensitive static program analysis, e.g., for an intra-procedural compiler optimization as well as for an intra-procedural program verification.

There are also similarities between our χ-terms (represented as directed acyclic graphs) and the (directed, cyclic) value graphs that are used in Global Value Numbering [2], since they also capture the history of control flow. The main difference between the two approaches is the memory efficiency we achieve by avoiding data redundancy. Our approach can be seen as a generalization of Global Value Numbering where we trade precision for memory efficiency. This will be further discussed in Section 6.

χ-terms can also be understood as a generalization of Binary Decision Diagrams (BDD) [1] used to represent logical functions. An BDD is a redundancy-free representation of Boolean functions as a directed acyclic graph (DAG) that allows an efficient computation of frequently used operations such as disjunction, conjunction and function composition. A logical function f(A,B,C) = ¬AB¬C ∨ AC, e.g., with the truth table given in Fig. 1 (left), can be represented as a decision tree (middle). Removing and reusing redundant subtrees can simplify the decision tree and result in a much smaller BDD (right). Enforcing the same order of the parameters in a BDD on each path from the root to a leaf leads to Ordered BDDs. The main idea from OBDDs that we use in our implementation of χ-terms is the DAG representation and the redundancy elimination for memory efficiency. Furthermore, the leaves on OBDDs represent decisions based on the logical values (true/false) whereas χ-terms allow for multiple decisions in the leaves (the leaves represent context-insensitive analysis values).

Different representations of the function f(A,B,C) = ¬AB¬C ∨ AC

Full size image

It is NP-hard to find a parameter order leading to a minimal representation of the corresponding OBDD [6]. While memory efficiency is one of the main objectives of our approach, optimizing the order of nodes in χ-terms is not a part of this paper. Instead we simply use an order that is defined by the order in which the corresponding ϕ-nodes are analyzed. Related program analysis approaches exploiting (O)BDD ideas will be further discussed in Section 6.

This paper is a complement to our paper Memory Efficient Context-Sensitive Program Analysis [12]. In [12] we give an informal presentation of χ-terms and evaluate the memory efficiency by comparing the memory foot-prints of χ-terms with four other data structures (context table, context tree in two variants, and double hash map) often used to capture context-sensitive analysis information. The experiments use context-sensitive points-to analysis information taken from ten different benchmark programs. The results show that χ-terms are indeed memory efficient. They use on average only 13% of the memory used by the second best approach. A closer look at the context-sensitive analysis values used in the experiments show that they in general have a rather complex structure when presented using the other data structures, it is only the χ-terms with their redundancy elimination that can deduce (and make use of) the fact that a majority of these structures can be simplified, and made much smaller. Hence, [12] provides the experimental evidence that χ-terms are memory efficient, this paper presents χ-terms as a general framework for memory efficient context-sensitive program analyses.

Our contributions in this paper are the following:

1. 1.

   We propose χ-terms, a generalization of OBDDs, as a memory efficient representation, to capture context-sensitive analysis values in an SSA-based program analysis.

2. 2.

   We propose approximations in the representation of χ-terms to control memory explosion when handling context-sensitive analysis information in conditional control-flow and iterations (control-flow cycles), including the handling of unbounded iterations.

3. 3.

   We prove that any sound context-insensitive analysis has a corresponding sound context-sensitive analysis based on χ-terms that is guaranteed to reach a fixed point.

The remainder of the paper is structured as follows:

• In Section 2, we define concrete and abstract analysis semantics, and introduce the term representation of context-insensitive analysis results.

• In Section 3, we introduce χ-terms and operations on χ-terms. We also prove that a sound context-insensitive analysis can be generalized to a sound context-sensitive analysis using χ-terms.

• In Section 4, we address the problem of terminating a data-flow analysis. The problem with the potentially infinite size of a χ-term can be avoided by introducing different widening approximations. We introduce such approximations and show that the resulting approximated analysis is sound and guaranteed to reach a fix point.

• In Section 5, we introduce and discuss the compact representation of χ-terms using redundancy-free direct acyclic graphs (DAGs), a generalization of Ordered Binary Decision Diagrams (OBDDs). Moreover, we present a fast and memory efficient algorithm for creating approximated χ-term in DAG format that avoids redundant sub-terms. We conclude the section by discussing memory management and its effect on the memory footprint.

• Section 6 discusses related works.

• Section 7 concludes the paper.

In this section, we introduce assumptions and notations that will be used throughout this paper. We start by outlining concrete and abstract analysis semantics for a data-flow analysis followed by a term representation for a context-insensitive analysis, which we then take as a point of departure for defining context-sensitive analysis values.

2.1 Concrete Analysis Semantics

Let a program \(P \in \mathcal {P}\) (\(\mathcal {P}\) the set of all syntactically correct programs) be represented by its program graph \(G=(N, E, n^{0}) \in \mathcal {G}\) (\(\mathcal {G}\) the set of all such program graphs G of programs in \(\mathcal {P}\)) in Static Single Assignment (SSA) form [10, 29] with

• N a set of nodes taken from a finite set of node kinds including ϕ nodes representing selections of values computed in different program paths,

• E a set of data- and control-dependency edges, and

• n⁰ ∈ N the unique start node without any predecessors in G.^{Footnote 1}

The nodes in an SSA graph represent data- and control-operations, and the edges their dependencies. The specific node type ϕ is used to represent a selection of one of the dynamic predecessor. An SSA graph with only forward edges represents a program with no cycles. A program with control flow cycles includes backward edges (loops).

A program state (n,v) ∈ (N × V ) is defined as a pair of the current node n ∈ N (the program pointer) and variable values v ∈ V. Let \(\llbracket \rrbracket ^{*}: \mathcal {G} \times V \mapsto 2^{(N \times V)^{*}}\) be a trace semantics function defining the semantics of all \(P\in \mathcal {P}\). For a program \(G\in \mathcal {G}\), it maps an initial state (n⁰,v⁰) to traces, i.e., a set of possibly infinite sequences of states:

where each such trace represents a possible program execution according to the semantics of the language. \((n^{\prime },v^{\prime })\in \mathit {next}(n,v)\) represents the next possible state(s) after a current state (n,v). Notice that ⟦⟧^∗ gives a set of possible sequence of states (traces) whereas next(n,v) just gives a set of possible states to choose the next single current state from. Due to non-determinism in the programming language semantics, there are, in general, more than one states in next(n,v). Hence, there are, in general, several traces for one and the same program graph G and initial state v⁰.

⟦⟧^∗ is defined as a composition of semantics functions \(\llbracket \rrbracket _{k}^{\mathit {data}}: V \mapsto V\) and \(\llbracket \rrbracket _{k}^{\mathit {ctrl}}: N \mapsto N\), one such pair for each of the different node kinds k, defining the mapping of a current state to the next state(s): \((n^{\prime }, v^{\prime }) \in \mathit {next}(n,v)\) with \(v^{\prime } \in \llbracket {v} \rrbracket _{k}^{\mathit {data}}\), \(n^{\prime } \in \llbracket {n} \rrbracket _{k}^{\mathit {ctrl}}\), kind(n) = k, and \((n,n^{\prime }) \in E\).

The update function \(\llbracket \rrbracket _{\phi }^{\mathit {data}}\) for ϕ nodes is defined as \(\llbracket {v} \rrbracket _{\phi }^{\mathit {data}}=v\). With \(\llbracket {n} \rrbracket _{\phi }^{\mathit {ctrl}}\) the control flow edge successor of n, we have \(\mathit {next}(n,v)=(n^{\prime },v)\) if n is a ϕ node and \((n,n^{\prime }) \in E\). Notice that a ϕ-node does not change the input value; its semantics is a non-strict function that just selects the predecessor value computed at the dynamic predecessor block and provides it to its dynamic successors.

2.2 Abstract Analysis Semantics

Let a Monotone Data-flow Framework [26] \((A, \sqsubseteq , F, \iota )\) define every sound, context-in sensitive program analysis I with

• A is an abstraction of V.

• \(\mathit {CPO}_{A} = (A, \sqsubseteq )\) a complete partial order fulfilling the ascending chain property representing the analysis values. ⊥ is the smallest such value. CPO_A induces a semi-lattice \({\mathscr{L}}_{A}=\{A,\sqcup , \bot \}\) with \(a\sqsubseteq b \Leftrightarrow a\sqcup b=b\). (n,a) ∈ (N,A) defines an abstract program state in n.

• F a set of transfer functions one for each kind k of nodes \({f_{k}^{p}}:A^{p} \mapsto A\) including a special transfer or join function for ϕ nodes \(f_{\phi }^{p}: A^{p} \mapsto A; f_{\phi }=\sqcup (a_{1}, \ldots ,a_{p})\), with p the number of predecessors of a node.

• ι ∈ A the initial abstract value of n⁰.

Assume I is a valid abstraction of ⟦⟧^∗ for each \(G \in \mathcal {G}\) and the corresponding initial state v⁰ in the sense of Abstract Interpretation [9]. Then corresponding abstraction and concretization functions map traces to abstract program states and vice versa. More specifically, we assume that I abstracts each trace ending in (n,v) with (n,α(v)) and interprets an abstract state (n,a) as traces ending in (n,v),v ∈ γ(a).

For the result of a valid abstraction of ⟦⟧^∗, it holds for any abstract state (n,a) and kind(n) = k:

i.e., the union of the output values of applying the semantics function of n to any concrete input value v ∈ γ(a) (left-hand side) is not larger than (is abstracted by) applying the corresponding transfer function to the abstract value a and then concretizing the abstract output (right-hand side).

Moreover, any fair sequence of transfer function updates, beginning with initial abstract states (n⁰,ι) in the start node and (n,⊥), otherwise, terminates in a valid fixed point, i.e., the concretization of the fixed point abstract state in n for a program (graph) G is an over-approximation (abstraction) of the possible traces ending in n.

2.3 Term Based Context-Insensitive Analysis

Definition 1 (⊔-terms)

Let \((A, \sqsubseteq , F, \iota )\) define a context-in sensitive program analysis I. The set of all ⊔-terms U_A over the abstract values A is defined recursively:

where is a unique function symbol representing f. For the transfer function ⊔ of ϕ-nodes, we use the function symbol \(\dot \sqcup \).

Notice, even if the set of abstract values A were finite, U_A is infinite since there is no upper limit on the depth of the terms.

In Fig. 2, we illustrate a simple code sequence with corresponding ⊔-term representation for variable f. In the code, we have marked block numbers (#0 - #6) to identify the related ⊔-term nodes. For example, the variable a is assigned a value in each branch (#1, #2) of the first if-statement. Therefore, the corresponding ϕ node’s transfer function at the beginning of Block #3 creates a term \(\dot \sqcup (1,3)\). Similarly, the term for variable b is \(\dot \sqcup (4,2)\). Consequently, the term for variable c in Block #3 is

Finally, the term for variable f in Block #6 becomes:

From Fig. 2, we can notice that all ⊔-terms have a natural tree representation and that (sub-) terms/trees can be used to express/construct larger terms/trees. The abstract analysis values A form the leaves of the tree and the function symbols (including the join function symbol \(\dot \sqcup \)) the interior nodes. Notice also that the tree representation contains a lot of redundancies. For example, the identical sub-trees in the upper left and right corners both represent the value for variable c. Finally, a program containing loops will be represented by a ⊔-term tree with an infinite depth.

A source code example with the corresponding tree representation for the ⊔-term for variable f

Full size image

The context-insensitive transfer functions f,⊔ of function symbols \(\mathtt {f}, \dot \sqcup \) are defined on A, not on U_A. However, we can generalize them by recursively applying them on sub-terms and evaluating them at the leaves of a ⊔-term. This approach defines an evaluation of ⊔-terms.

For example, assume that we use set union ∪ as our ⊔-operator and that the transfer functions of the operators + and − are applied element by element on sets (e.g. + ({1,2},{3,4}) = {4,5,6}). In this case, the evaluation of the ⊔-term expressions for variables c and f defined by (1) and (2) can be evaluated as:

According to this context-insensitive analysis, the possible values for variables c and f are {3,5,7} and {0,2,4,6,8,10,12,14}, respectively. The eval_⊔ approach outlined above will not terminate for programs containing loops. Loop handling will be addressed in Section 4.1.

Definition 2 (≡_⊔)

is an equivalence relation on ⊔-terms t₁,t₂ ∈ U_A:

Definition 3 (\(\sqsubseteq _{\sqcup }\))

is a partial order relation on ⊔-terms t₁,t₂ ∈ U_A:

Obviously, if \((A, \sqsubseteq , F, \iota )\) defines a sound analysis, then so does \((U_{A}, \sqsubseteq _{\sqcup }, F, \iota )\). It just separates the construction of transfer function terms from their evaluation. This exercise only becomes meaningful when we substitute the evaluation of the ⊔ function, i.e., the transfer function of ϕ-nodes, with a less abstract evaluation, as done in the next section.

In this section, we introduce χ-function symbols and χ-terms as a context-sensitive replacement of \(\dot \sqcup \) and ⊔-terms. We give an intuition on how to interpret χ-function symbols as a selection operator over possible control-flow paths. Given this interpretation, we can identify certain properties (e.g. switching behavior) which in turn motivates a rewrite rule for syntactic manipulation of χ-terms without changing the context-sensitive information they represent called the Shannon expansion. By introducing the Shannon expansion, we can finally define equivalence ≡_χ (the basis for a formal interpretation of χ-terms), partial order \(\sqsubseteq _{\chi }\), and \((X_{A}, \sqsubseteq _{\chi }, F, \iota )\) as a sound context-sensitive analysis based on χ-terms, which will follow next.

3.1 χ-Function Symbols

In the context-insensitive analyses introduced so far, each SSA ϕ-node of a program corresponds to one or more \(\dot \sqcup \)-function symbols in the ⊔-terms generated by an analysis. In the context-sensitive analyses we introduce next, a ϕ-node of a program corresponds to one or more χ-function symbols (short χ-functions), which we use to introduce context-sensitivity. Each χ-function \({\chi ^{b}_{j}}\in \mathtt {X}\) is identified by a pair (b,j) where:

1. 1.

   The block number \(b = \mathit {block}({\chi ^{b}_{j}}), b\in [1,B]\) indicates the basic block containing its corresponding ϕ-node. Here B is the number of basic blocks in a program P.

2. 2.

   The iteration index \(j = \mathit {index}({\chi ^{b}_{j}})\) is an integer starting at index 0. The index j corresponds to the interpretation of ϕ-node in the j th run-time iteration over block b. The use of iteration indices will be discussed in detail in Section 3.4. For now, it just syntactically distinguishes χ-function symbols that correspond to the same ϕ-node in a block b.

3. 3.

   The forward edges of an SSA graph induce a partial order ≺ of its ϕ-nodes. The block numbering respects this partial order, i.e.,

   $$ \phi_{1} \prec \phi_{2} \Rightarrow \mathit{block}(\chi^{b_{1}}_{j_{1}})<\mathit{block}(\chi^{b_{2}}_{j_{2}}) $$

   where \(\chi ^{b_{1}}_{j_{1}}\) and \(\chi ^{b_{2}}_{j_{2}}\) are χ-functions corresponding to ϕ₁ and ϕ₂, resp.

4. 4.

   The arity of a χ-function, denoted \(\mathit {arity}({\chi ^{b}_{j}})\), is the number p of predecessor blocks of the corresponding ϕ-node. It is the same regardless of the iteration index.

Notice, in order to separate iterations occurring at run-time when a program is executed from iterations of the analysis to establish a fixed point we will explicitly use the notion run-time iterations when referring to the former type of iteration.

3.2 χ-Terms

In this section, we formally define χ-terms along with some related general concepts.

Definition 4 (χ-terms)

Let \((A, \sqsubseteq , F, \iota )\) define a context-in sensitive program analysis I. The set of all χ-terms X_A over the abstract values A is defined recursively:

Similar to the ⊔-terms, each abstract value a ∈ A is a χ-term (3) and a transfer function symbol applied to χ-terms is a χ-term (4). ϕ correspond \({\chi ^{b}_{j}}\) functions that also induce χ-terms (5).

We have previously associated all χ-functions \({\chi ^{b}_{j}}\) with a block number \(b = block({\chi ^{b}_{j}})\) and arity \(arity({\chi ^{b}_{j}})\). These notations can be extended to χ-terms as well.

Definition 5 (Block number and arity)

The block number of a χ-term t ∈ X_A, denoted block(t), is defined as:

From now on we will often skip the iteration index to simplify the notations. In these cases, we assume that all involved χ-functions, from a certain block b, have the same iteration index.

As an example of χ-terms, we once again take a look at the values for variables c and f from Fig. 2:

So far, χ-terms are elements of a term algebra. While we will give a formal interpretation later, an intuitive understanding of their semantics will help. Following the semantics of ϕ-nodes, χ-terms represent how different control-flow predecessors define the value of a variable. For example, we denote the value of variable a in block #3 in Fig. 2 using χ-terms as a = χ³(1,3) with the following interpretation: variable a has the value 1 if block #3 was reached from the first predecessor block (block #1) in the program execution; a has the value 3 if it was reached from second predecessor block (block #2). Similar (but more complex) are the interpretations of the χ-terms representing the variables c and f above. In short, in addition to a set of possible values, a χ-term also contains information about the control-flow path that generated each of these values. It abstracts, however, from the conditions leading to the different paths.

Definition 6 (Function set)

The function set of a χ-term t ∈ X_A, denoted func(t), is the set of all χ-function symbols \({\chi ^{b}_{j}}\in \mathtt {X}\) used to construct t.

For example, func(f) = {χ³,χ⁶} for the χ-term defined in (7).

3.3 The Tree Representation of χ-Terms

Terms in general (as well as ⊔- and χ-terms) have a tree representation. Many notions and χ-term operations are easiest to understand as tree properties. Basic notions include:

• The leaves of a χ-term t ∈ X_A, denoted \(\mathit {leaves}(t)\subseteq A\), correspond to the set of all leaves in the tree representation of t.

• The subterms of a χ-term t ∈ X_A, denoted \(\mathit {subterms}(t)\subseteq X_{A}\), correspond to the set of all χ-functions-rooted subtrees of t in the tree representation of t. Transfer-function-symbol-rooted subtrees and the leaves are not included. Also, t itself is not included if t is a χ-function-rooted term whereas all χ-function-rooted subterms are included if t is a transfer-function-symbol-rooted term.

• The children of χ-term t ∈ X_A, denoted \(\mathit {children}(t)\subseteq X_{A}\), is defined as:

  $$ \mathit{children}(t) = \left\{ \begin{array}{ll} \{t_{1},\ldots,t_{p}\} & \text{ if } t ={\chi^{b}_{j}}(t_{1},\ldots, t_{p}) \\ \emptyset & \text{ otherwise} \end{array}\right. $$

• The depth of a χ-term t ∈ X_A, denoted depth(t), is the max number of χ functions on any path from the leaves to the root of the tree representation of t.

• Let n ∈ X_A be a node in the tree representation of a χ-term t ∈ X_A. The depth of subterm s in t, denoted depth(t,s) = depth(t) − depth(s), is the depth of the node representing s in the tree representation of t.

We exemplify the basic tree notations on the χ-term of variable f introduced in (7):

3.4 Basic χ-Term Operations

In this section, we present basic operations on χ-terms as a prerequisite for defining an equivalence relation and an evaluation function of χ-terms.

We observe that two ϕ nodes \(n, n^{\prime }\) in the same block b and interpreted in the same run-time iteration j have the same switching behavior. We do not know statically which dynamic values are selected and which of the static predecessors of \(n, n^{\prime }\) computes these values. However, we do know that it is the same predecessor for both ϕ nodes n and \(n^{\prime }\).

Recall that χ-function symbols represented the transfer function of ϕ nodes. Given two ϕ-nodes ϕ(x₁,…,x_p) and \(\phi ^{\prime }(y_{1},\ldots ,y_{p})\) from the same block b (for selecting the values of variables x and y, respectively, valid in b). For any execution of the program it holds that in the same run-time iteration j over b

Thus, the selection behavior of a ϕ-node is determined by a pair (b,j) where b is the block number and j is the iteration index. We abstract from this property of the ϕ-node interpretation in the insensitive transfer function ⊔ and its interpretation in ⊔-terms. In contrast, we will keep this property of ϕ-nodes in the context-sensitive transfer function \({\chi ^{b}_{j}}\) and its interpretation in χ-terms.

This property is the basis for defining the most important operation, the Shannon expansion, used to manipulate χ-terms without affecting their value. To define this operation, we first introduce restriction of χ-terms as an auxiliary operation.

Definition 7 (Restriction)

The restriction of a χ-term t ∈ X_A to the k:th branch of \({\chi ^{b}_{j}}\), denoted t|_(b,j):k, is a new χ-term where every sub-term \({\chi ^{b}_{j}}(t_{1},\ldots ,t_{p})\) in t has been replaced by its k:th child t_k.

For example from (7):

and we might have the following restrictions:

The χ-term restriction defines a new χ-term t|_(b,j):k by only considering the value from the k:th predecessor of block b (in run-time iteration j) in the construction of a new term \(t^{\prime }\). It should also be noticed that if we restrict to the k:th branch of \({\chi ^{b}_{j}}\) and \({\chi ^{b}_{j}}\not \in \mathit {func}(t)\) then t = t|_(b,j):k, i.e., the term t is left unaffected.

Definition 8 (Shannon expansion)

The Shannon expansion of a χ-term t ∈ X_A over \({\chi ^{b}_{j}}\) is a new χ-term \(t^{\prime }\) defined as:

Notice that Shannon expansion over any sub-term with root function symbol \({\chi ^{b}_{j}}\) is just a new term with the root \({\chi ^{b}_{j}}(... )\) of all possible restrictions of \({\chi ^{b}_{j}}\). It allows to revert the order of χ-functions in a χ-term. Notice also that the Shannon expansion creates a new χ-term that encodes the same context-sensitive information as the original χ-term. It is just a rewrite rule that can be used to manipulate χ-terms.

Below we illustrate the Shannon expansion over χ³ using the χ-term for variable c defined in (6).

and over χ⁶ and χ³ using as before the χ-term for variable f defined in (7):

The first equivalence is reached by expansion over χ⁶, cf. line (8), the second by expansion over χ³, cf. line (9). Recall that the example did not contain any loop; the loop index 0 is the same and could therefore be removed.

Figure 3 shows the tree representation of variable c before and after the Shannon expansion over χ³. The effect of the Shannon expansion is to create a new term/tree with χ³ as root. This also has the effect of pushing the node corresponding to the transfer functions of operation + closer to the leaves.

Two tree representations of variable c: Before (left) and after (right) Shannon expansion

Full size image

In general, repeated Shannon expansions over all available χ-functions (as we did for the variable f above) will result in a term/tree with all χ-terms being positioned close to the root, e.g., χ³(χ⁶(…),χ⁶(…)), and all nodes corresponding to regular transfer functions being pushed to the leaves.

In the following we define the equivalence and redundancy properties of χ-terms, which allow to evaluate and to simplify them.

Definition 9 (equivalence, redundancy)

Two χ-terms are equivalent (≡) iff

1. 1.

   They are the equivalent context-insensitive values

   $$ \begin{array}{@{}rcl@{}} v \equiv w \Leftrightarrow v\equiv_{\sqcup} w, \text{ where } v,w \in U_{A} \end{array} $$
2. 2.

   They have (syntactically) the same root and equivalent subterms

   $$ \begin{array}{@{}rcl@{}} {\chi_{j}^{b}}(t_{1},\dots,t_{p}) \equiv {\chi_{j}^{b}}(t^{\prime}_{1},\dots,t^{\prime}_{p}) &\Leftrightarrow& t_{1}\equiv t^{\prime}_{1}, \dots, t_{p}\equiv t^{\prime}_{p} \\ \mathtt{f}(t_{1},\dots,t_{p}) \equiv \mathtt{f}(t^{\prime}_{1},\dots,t^{\prime}_{p}) &\Leftrightarrow& t_{1}\equiv t^{\prime}_{1}, \dots, t_{p}\equiv t^{\prime}_{p} \end{array} $$
3. 3.

   They are a Shannon expansion of each other (see Definition 8)

4. 4.

   The root is a redundantχ operation that can be eliminated (redundancy elimination) if all its sub-terms are equivalent.

   $$ \begin{array}{@{}rcl@{}} {\chi_{i}^{b}}(t_{1},\dots,t_{p})\equiv t \Leftrightarrow t_{1}\equiv t_{2}\equiv {\dots} \equiv t_{p}\equiv t \end{array} $$
5. 5.

   If the block represented by b is a loop head and the loop index is 0, the value of the corresponding χ-term is equal to the loop-entry value.

   $$ {\chi_{0}^{b}}(t_{1},t_{2})\equiv t_{1} \text{ iff } b \text{ block number of a loop head} $$

The basic idea formalized in the definition above is that two χ-terms are equivalent if we can guarantee that they encode the same context-sensitive information. Some additional remarks related to the five parts of this definition:

1. 1.

   Recall from Definition 4 that χ-terms can also be values of the context-insensitive analysis lattice. Hence, v ≡ w above refers to the equivalence ≡_⊔ of context-insensitive analysis values.

2. 2.

   χ-terms can contain function symbols with χ-subterms and \(\mathtt {f}(\chi _{i},\dots ,\chi _{k}) \equiv \mathtt {f}(\chi ^{\prime }_{1},\dots ,\chi ^{\prime }_{k})\) requires the syntactic equivalence of the function symbols and the equivalence of the operands.

3. 3.

   Shannon expansions generate a new χ-term representing exactly the same context-sensitive information as argued before.

4. 4.

   Redundancy elimination is, just as the Shannon expansion, a rewrite rule leading to syntactically new χ-terms that encode the same context-sensitive information. They are, thus, a necessary part of the equivalence definition. Redundancy implies that a χ-term t containing a redundant sub-term χ^r can be reduced without any loss of information. The process of removing redundant χ-sub-terms is called redundancy elimination and uses the following pattern

   $$ \begin{array}{@{}rcl@{}} {\ldots} \chi^{i}(\ldots,\chi^{r}(t^{\prime},\ldots,t^{\prime}),\ldots)\ldots\ \equiv {\ldots} \chi^{i}(\ldots,t^{\prime},\ldots)\ldots \end{array} $$

   In the tree view of a χ-term, this corresponds to replacing a sub-tree rooted χ^r by any of its (all equivalent) sub-terms.

5. 5.

   This property can be trivially derived from the semantics of ϕ-nodes in loop heads. It defines the initial value of the fixed-point analysis of loops.

3.5 χ-Term Evaluation

In Section 2.3, we used eval_⊔ : U_A↦A to evaluate a context-insensitive ⊔-term. That is, to associate each ⊔-term with a concrete analysis result a ∈ A. We are now ready for a similar evaluation eval_χ for context-insensitive χ-terms: eval_χ : X_A↦X_A is performed in three steps:

1. 1.

   Repeatedly apply Shannon expansion over all χ-functions in func(t). That is, push the non χ-term nodes to the leaves and separate ⊔-sub-terms (with only operation symbols and leaves A) and the \({\chi ^{b}_{j}}\) function symbols using Shannon expansion.

2. 2.

   Evaluate the ⊔-sub-terms with eval_⊔.

3. 3.

   Apply redundancy elimination until no further simplification is possible.

We call the evaluation process, eval_χ an “equivalence conversion”, short EC. It simplifies the χ-terms representation of context-sensitive information without losing any control-flow information. Algorithm 1 is a recursive implementation of EC. Additionally, it enforces the same order of χ-functions from the leaves to the root in all χ-terms by picking the highest (b,j)-ranked χ-function (with largest j and largest b as secondary ranking criterion) in each Shannon expansion step. This leads to normalized χ-terms that are free from operation and \(\dot \sqcup \) symbols.

The result of eval_χ is in general a χ-term. To get a context-insensitive value that can be compared to eval_⊔ we introduce a second transformation collapse_χ : X_A↦A. It maps a χ-term not containing any function symbol to an element of the underlying context-insensitive analysis A CPO.

1. 1.

   Substitute all \({\chi ^{b}_{j}}\) function symbols with \(\dot \sqcup \).

2. 2.

   Apply eval_⊔.

We refer to this widening the “termination conversion”, short TC. It removes any remaining control-flow information by applying the context-insensitive join operator \(\dot \sqcup \) in place of all remaining χ-functions. More precisely, we substituted all \({\chi _{j}^{b}}\)-functions with \(\dot \sqcup \) whose evaluation replaces the control-flow dependencies of the result encoded by the χ-functions with a conservative approximation that merges the results of all possible control-flow options.

As an example of applying eval_χ, we evaluate the χ-term for c defined in Equation (6):

As an example of applying eval_χ and collapse_χ, we evaluate the χ-terms for f defined in (7). The first EC 1 steps, the Shannon expansion over the χ-terms, have been shown already in (8) and (9):

As these two examples show, the effect of applying eval_χ (push operators to the leaves, evaluate ⊔-terms, apply redundancy elimination) often simplifies a χ-term expression considerably by removing all superfluous redundancies. The final result c = 5 and the intermediate result f = χ⁶(0,10) represent the full context-sensitive information where all effective control-flow decisions are kept. The interpretation of these results is the following: variable c in block #3 (Fig. 2) will always take the value 5 regardless of the control-flow, and variable f in block #6 will take the values 0 or 10 depending on whether we enter the final if statement or not. The example also shows, that we lose information when we apply collapse_χ : f = {0,10} does not refer to the control-flow context any longer. Still, it is more precise than the context-insensitive result {0,2,4,6,8,10,12,14} of the evaluation of the corresponding ⊔-term discussed earlier.

Notice that for each finite χ-term, collapse_χ ∘eval_χ terminates with a value from A, the abstract analysis domain from the context-insensitive analysis. This is obvious as eval_χ removes all operations and collapse_χ removes all χ-function symbols and applies eval_⊔ to compute an A value.

Analogously to the partial order relation on ⊔-terms (Definition 3), we define such a relation on χ-terms:

Definition 10 (\(\sqsubseteq _{\chi }\))

is a partial order relation on χ-terms. Let t₁,t₂ ∈ X_A

That is, \(t_{1} \sqsubseteq _{\chi } t_{2}\) if the following cases recursively apply: (base case i) t₁,t₂ ∈ U_A and evaluate to a₁,a₂ ∈ A, resp., with \(a_{1}\sqsubseteq a_{2}\); (ii) equivalence conversions do not have an impact; (iii) Widening (i.e. replacing \({\chi ^{b}_{j}}\) with \(\dot \sqcup \)) gives a larger χ-term, e.g., \({\chi ^{b}_{j}}(t_{1},\ldots ,t_{p}) \sqsubseteq _{\chi } \dot \sqcup (t_{1},\ldots ,t_{p})\); (iv) both terms t₁,t₂ are rooted with the same χ-function symbol and the respective children \(s_{i}, s^{\prime }_{i}\) are pairwise ordered \(s_{i}\sqsubseteq s^{\prime }_{i}\); (v) t₁ is smaller than a sub-term of t₂.

An important part of collapse_χ was to substitute χ-function symbols with \(\dot \sqcup \). We refer to this type of approximation as the ⊔-approximation. In Section 4, we use ⊔-approximations to introduce two alternative approaches guaranteeing the termination of χ-term based context-sensitive analyses.

Definition 11 (⊔-approximation)

Let t ∈ X_A be a χ-term and let s be a sub-term of t rooted by a χ-symbol \({\chi ^{b}_{j}}\). The ⊔-approximation of t with respect to s, denoted \(t^{*}_{s}\), is a new term where the root χ-symbol \({\chi ^{b}_{j}}\) in s is replaced by \(\dot \sqcup \).

The definition is easy to understand using the tree representation of t. It simply means that we replace the root χ-symbol \({\chi ^{b}_{j}}\) in a sub-term s by \(\dot \sqcup \). Intuitively, any ⊔-approximation is conservative, since it replaces the selective χ-term with an approximation that merges all possible control-flow options. With Definition 10, the partial order relations on χ-terms, we can formulated this intuition in the following

Theorem 1

Let t = χ(…,s,…) ∈ X_A be a χ-term and let \(s=\chi ^{\prime }(\ldots )\in X_{A}\) be a sub-term of t then \(t \sqsubseteq _{\chi } t^{*}_{s}\).

Proof

This follows directly from cases (iii) and (iv) in Definition 10. We define q as a new χ-term, the result of applying \(\dot \sqcup \) on sub-term s, then

□

Theorem 1 is important, since it tells us how to make conservative approximations of χ-terms. That is, we can in any phase of the analysis replace a χ-term χ(t₁,…,t_p) with \(\dot \sqcup (t_{1}, \ldots , t_{p})\) and still maintain a conservative approach.

3.6 Analysis Soundness

In this section, we prove the soundness of our context-sensitive analysis assuming it terminates. We end the section discussing issues related to termination (reaching a fixed point) and analysis accuracy.

The following two lemmata state that the induced context-sensitive transfer functions on X_A are monotone, provided that the initial context-insensitive transfer functions on A were monotone.

Lemma 2

Let \((A, \sqsubseteq , F, \iota )\) define a sound context-insensitive program analysis and \((X_{A}, \sqsubseteq _{\chi }, F, \iota )\) define the corresponding context-sensitive program analysis using χ-terms. Then

Proof

As \(t_{i}\in \mathit {subterms}({\chi _{j}^{b}}(t_{1}, \ldots , t_{p}))\), the claim follows directly from case (v) of Definition 10. □

Lemma 3

Let \((A, \sqsubseteq , F, \iota )\) define a sound context-insensitive program analysis and \((X_{A}, \sqsubseteq _{\chi }, F, \iota )\) define the corresponding context-sensitive program analysis using χ-terms. Let denote the function symbol of the context-insensitive transfer function f. Then \(\forall f\in F, t_{i}\in X_{A}, t^{\prime }_{i}\in X_{A}, i\in [1,p]\)

Proof

We prove the claim by structural induction on the depth of the χ-terms.Induction basis: The claim holds if \(\mathit {depth}(t_{i})=\mathit {depth}(t^{\prime }_{i})=0\). This implies \(t_{i}, t^{\prime }_{i} \in A\), \(t_{i} \sqsubseteq t^{\prime }_{i}\), and

since the context-insensitive transfer functions f : A^p↦A are monotone. Hence, \(\mathtt {f}(t_{1},\ldots , t_{p}) \sqsubseteq _{\chi } \mathtt {f}(t^{\prime }_{1}, \ldots , t^{\prime }_{p})\) for the induction basis according to (i) of Definition 10.Induction step: Provided it holds

if \(\mathit {depth}(s_{l}) \leq k, \mathit {depth}(s^{\prime }_{l}) \leq k\). Then the claim holds for arguments of \(\mathit {depth}(t_{i})\leq k+1, \mathit {depth}(t^{\prime }_{i}) \leq k+1\). W.l.o.g. let \(t_{i} = {\chi ^{b}_{j}}(s_{i_{1}}, \ldots , s_{i_{p^{\prime }}})\) and \(t^{\prime }_{i} = {\chi ^{b}_{j}}(s^{\prime }_{i_{1}}, \ldots , s^{\prime }_{i_{p^{\prime }}})\). Since, \(t_{i} \sqsubseteq _{\chi } t^{\prime }_{i}\), it follows from (iv) of Definition 10 and from the induction step’s precondition \(\forall i\in [1,p], l\in [1,p^{\prime }]\) that

Further

because of cases (ii) and (iv) of of Definition 10, which concludes the induction step and proves the claim. □

Hence, according to Lemmas 2 and 3, if \((A, \sqsubseteq , F, \iota )\) defines a sound analysis, monotone transfer functions are guaranteed for the context-sensitive analysis \((X_{A}, \sqsubseteq _{\chi }, F, \iota )\). Still it does only little more than separating the construction of transfer function terms from their evaluation. Compared to the previously discussed insensitive analysis \((U_{A}, \sqsubseteq _{\sqcup }, F, \iota )\), it only performs some equivalence transformations between the construction of transfer function terms and their evaluation. However, we can state the following theorem:

Theorem 4

Let \((A, \sqsubseteq , F, \iota )\) define a sound context-insensitive program analysis and \((X_{A}, \sqsubseteq _{\chi }, F, \iota )\) define the corresponding context-sensitive program analysis using χ-terms. If the corresponding context-sensitive analysis \((X_{A}, \sqsubseteq _{\chi }, F, \iota )\) terminates, then it is sound.

We acknowledge some issues that need to be discussed. First, the context-sensitive analysis is not guaranteed to terminate, in general, as the ascending chain property does not hold in the CPO \((X_{A}, \sqsubseteq _{\chi })\). Although an analysis χ-term fixed-point still exists as the transfer functions are monotone, it is not iteratively computable any longer. Instead, χ-terms may grow infinitely when applying standard iterative data-flow analysis. This is a problem that will be addressed in Section 4.

Second, while \((A, \sqsubseteq , F, \iota )\) and \((U_{A}, \sqsubseteq _{\sqcup }, F, \iota )\) produce the same result, the result of \((X_{A}, \sqsubseteq _{\chi }, F, \iota )\) may be more accurate (smaller, still conservative) than the original analysis results. This is because we distribute the transfer functions over the meet operation and can apply them to more concrete (smaller) input values in different control flow predecessors, which, in turn, potentially allows for more concrete results.

As an example of this change in analysis precision, we can take a look at eval_⊔ and eval_χ previously computed for the variables c and f:

By pushing the transfer functions of operators + and − to the leaves, we can deduce that c in block #3 always takes the value 5, and that f is either 0 or 10 exploiting the improved precision of eval_χ(c).

This does not only work in the example. In general, collapse_χ(eval_χ()) gives more precise (smaller) analysis results than eval_⊔. We notice that the same accuracy could be achieved by a semantic-preserving source code transformation that duplicates code after a control flow conjunction into the different branches before this conjunction (code in-lining). This transformation would obviously not terminate for loop conjunctions, neither does our χ-term construction in these cases. This would lead to an exponential growth for sequential code with conditional statements; just as our χ-term construction lets them grow exponentially.

To exemplify this, cf. to the code in Fig. 2 again replicated in Fig. 4 (left) and assume that the blocks #3 − #6 were copied into both branches #1 and #2 of the first if statement, and in both copies, block #6 were moved into block #5 and into a new else block of the second if statement. The result of such a semantics preserving transformation is given in Fig. 4 (right). It is easy to see that now even a context-insensitive analysis using eval_⊔ would achieve the same accuracy as a context-sensitive analysis based on eval_χ on the original program: c = 5 for both copies in blocks #3a and #3b, f = 10 for the copies in blocks #6aa and #6ba, and f = 0 for the copies in blocks #6ab and #6bb.

Source code example from Fig. 2 before and after a semantics preserving code cloning transformation

Full size image

The tree-based χ-term representation is (arguably) already better than representations based on the cloned code. However, we will introduce a more compact χ-term representation that does not contain any redundancies in Section 5.

Finally, in order to simplify our notations, we will from now on present the results in their normal form in our examples. That is, rather than presenting χ-terms involving complex combinations of context-insensitive values, ⊔-operators, and χ-functions, we will show them after having applied normalize, cf. Algorithm 1, i.e., push operator transfer functions to the leaves, evaluate ⊔-terms, apply redundancy elimination, and at the same time give an ordered structure based on the χ-term ranking. For example, instead of the complete χ-terms for c and f in given (6) and (7), respectively, we will show them as c = 5 and f = χ⁶(0,10).

As observed in Section 3.4, an analysis based on fixed-point iteration starting with ⊥ does not terminate since the ascending chain property does not hold in the CPO \((X_{A}, \sqsubseteq _{\chi })\). The χ-terms represent different values that are context-dependent on the different control-flows options and there are countable many such options. More specifically, χ-terms will grow infinitely when applying a standard iterative data-flow analysis on a program involving loops or any other cycles in the control-flow graph. In this section, we will handle this problem by introducing one type of widening applying ⊔-approximation to control-flow cycles (referred to as the l-loop-approximation). It will guarantee finitely sized χ-terms and analysis termination. We will also introduce another type of widening (referred to as the k-approximation) limiting the depths of χ-terms and allowing the analysis precision to be adjusted by an integer parameter k.

4.1 Loop Handling

Control-flow cycles, e.g. loops, generate χ-terms with an infinite depth and prevent analysis termination. For guaranteeing termination, we define a loop-approximated CPO in which the the ascending chain property holds. Therefore, we introduce a widening step, the ⊔-approximation, in the transfer functions of ϕ nodes generated for the loop heads.

We illustrated the idea with an introductory example. Assume a \((X_{A}, \sqsubseteq _{\chi }, F, \iota )\) based value analysis that, in turn, generalizes an context-insensitive value analysis \((A, \sqsubseteq , F, \iota )\) with \((A, \sqsubseteq )\) defining a integer constant (flat) lattice and F straightforward transfer functions for operators + and −: if arguments are constants they calculate the constant result, if one argument is ⊥(⊤) the result is ⊥(⊤).

For the code fragment and the corresponding SSA sub-graph in Fig. 5, the analysis generates χ-terms for the loop-escaping variable x assigned to y (cf. Fig. 5) as follows:

Loop approximation example, code fragment (left) and SSA sub-graph (right). The basic blocks and the control flow between them was omitted here

Full size image

In the example, \({\chi ^{w}_{j}}\) (\({\chi ^{i}_{j}}\)) represents the (selection) semantics of the ϕ node corresponding to the while (if) block after 0…j completed run-time iterations; \({x^{w}_{j}}\) is the term representing the analysis value of x after 0…j completed run-time iterations conservatively assuming that such a program execution is realizable in a concrete run. Especially, \({x^{w}_{0}}\) represents x for the control flow option that does not iterate over the loop body, and, trivially, it is x = 1, as defined in point 5 of Definition 9. \({x^{w}_{1}}\) represents x for the control flow option that does zero or one run-time iteration over the loop body. After analyzing the loop body (and the included conditional code) and a few transformations \({x^{w}_{1}}\), can be interpreted as follows: x = 1 for no iteration or \({\chi ^{i}_{0}}(2,0)\) for one run-time iteration, which, in turn is 2 or 0 depending on the executed branch of the if statement in the body. \({x^{w}_{2}}\) represents x for the control flow option that iterates zero, once, or twice, and the χ-term gets large already. The final result after 0…2 run-time iterations and normalization \({\chi ^{w}_{2}}(1,{\chi ^{i}_{1}}({\chi ^{w}_{1}}(2,{\chi ^{i}_{0}}(3,1)),{\chi ^{w}_{1}}(0,{\chi ^{i}_{0}}(1,-1))))\) can be interpreted as x = 1 for no run-time iteration, or \(x={\chi ^{i}_{0}}(2,0)\) for one run-time iteration. For two run-time iterations, \(x={\chi ^{i}_{1}}({\chi ^{i}_{0}}(3,1),{\chi ^{i}_{0}}(1,-1))\), i.e., 3, 1, or − 1 depending on the four possible combinations of control flow options in the two run-time iterations over the if statement in the loop body.

The general pattern is \({x^{b}_{j}} = {\chi ^{b}_{j}}(\ldots \chi ^{b}_{j-1}({\ldots \chi ^{b}_{0}}(\ldots ) \ldots ){\ldots } )\). That is, a χ-term for the j-th loop contains and depend on decisions \({\chi ^{b}_{0}}, {\ldots } , \chi ^{b}_{j-1}\) with the same block number b and iteration indices 0,…,j − 1. This pattern occurs over and over again, since each loop iteration results in a new composition of χ^b with itself. This results in countably many χ-terms and, hence, in a non-terminating analysis if no measure is taken to stop the analysis.

One possible way to handle this problem is, for a χ-term \(t={\chi ^{b}_{j}}(t_{1},\ldots ,t_{p})\), to replace every sub-term of t that has the same block number as t by its ⊔-approximation. Using this approach, the approximated term(s) for the example are:

The terms \({x^{w}_{j}}={\chi ^{w}_{j}}(t_{1}, t_{2}) = {\chi ^{w}_{j}}(1,\top )\) represent the value of x after \(0 {\dots } j\) run-time iterations and \(t_{1}= {x^{w}_{0}} = 1\) the value after the 0-th iteration, actually no iteration. However, t₂ = ⊤ represents all abstract values after 1,…,j run-time iterations. Since a ⊔-approximation is always larger than the term it is applied to, this widening does not sacrifice the monotonicity of updates. Notice, disregarding loop indices in \({\chi ^{w}_{2}}\) and \({\chi ^{w}_{3}}\), the terms are the same and will remain so in all the following run-time iterations.

In general, assume program graphs \(\mathcal {G}_{0}\) with a loop nesting depth of 0, i.e., they do not contain any loops, only sequential and conditional code. Trivially, all χ-terms analyzed for the nodes of \(\mathcal {G}_{0}\) have a finite depth. Further, assume program graphs \(\mathcal {G}_{1}\) with a loop nesting depth of 1, i.e., all with loops contain program graphs of \(\mathcal {G}_{0}\). If we applied the described ⊔-approximation on all χ-terms generated by the ϕ nodes of loop heads, the χ-terms would have a final depth, i.e., for each w.l.o.g.

Structural induction on all such sets of program graphs \(\mathcal {G}_{0}, \mathcal {G}_{1}, {\ldots } \mathcal {G}_{i}, \mathcal {G}_{i+1}, \ldots \) shows that this ⊔-approximation on χ-terms stemming from loop heads leads to final depths of all χ-terms in an analysis of arbitrary program graphs \(\mathcal {G}\).

As the loop indices j are arbitrary, we reached a fixed point when the χ-terms do not change disregarding these loop indices and we can stop the analysis of the loops.

Under this widening abstraction, we extend the equivalence Definition 9 by:

which makes (all) the loop indices \(j, j^{\prime }\) obsolete. As the updates are monotone, the depths of χ-terms is finite, and the set of χ-functions is finite too, the analysis is guaranteed to terminate in a fixed point.

In the above example, we get the fixed point

The interpretation is that x = 1 if there has been no run-time iteration and x = ⊤, i.e., unknown, if there has been one or more run-time iterations.

We refer to the above analysis as 1-loop-analysis: for a given loop head ϕ-node, it replaces every sub-term of the corresponding χ-term \({\chi ^{b}_{j}}(t_{1},\ldots ,t_{p})\) with indices j − 1,…,1 by their ⊔-approximation. In the next section, we generalize the 1-loop-analysis to l-loop-analysis and conclude with a general widening abstraction that replaces the fixed point condition in (10).

4.2 The l-Approximation

As stated above, we can get a more precise analysis if we instead used a 2-loop-analysis where we ⊔-approximated all sub-terms of \({\chi ^{b}_{j}}(t_{1},\ldots ,t_{p})\) with indices j − 2,…,1. This idea can of course be generalized to an arbitrary number l:

Definition 12 (l-loop-approximated χ-term)

Let t ∈ X_A be a χ-term rooted by a χ-function \({\chi ^{b}_{j}}\) and let \(F \subseteq \mathit {func}(t)\) be all χ-functions of t, such that

The l-loop-approximation of t is then a new χ-term where every \({\chi ^{x}_{y}} \in F\) has been replaced by \(\dot \sqcup \).

An analysis where every newly created χ-term related to a loop head ϕ-node is immediately loop approximated is said to be a l-loop-approximated analysis.

This l-loop-approximation is easy to understand as a tree manipulation. We make a post order traversal of the tree and replace each χ-term having the same block number as the root node \({\chi ^{b}_{j}}\), and an iteration index in range 1,…,j − l, with their corresponding ⊔-approximation. This approach is implemented in Algorithm 7 and discussed in Section 5.4.

The l-loop-approximation is conservative, since any ⊔-approximation is conservative. As the special case of a 1-loop-approximation, it also guarantees that every χ-term has a finite depth. However, as for this special case, we need in general guarantee that we do not get new χ-functions with new loop indices j and, hence, never reach a fixed point for the (finite depth) χ-terms.

Before we present a general solution, we recap the example of Fig. 5 once again. For the χ-term of \({x^{w}_{3}}\), the 2-loop-approximation is given below

This analysis result can be interpreted as x = 1 for no iteration, or \(x={\chi ^{i}_{2}}(2,0)\) for one run-time iteration, depending on the if condition in this run-time iteration. For two and three run-time iterations, the result is ⊤, i.e., we do not know.

Continuing with the analysis of the loop using this 2-loop-approximated term gives:

The final analysis result can be interpreted as x = 1 for no iteration, or \(x={\chi ^{i}_{3}}(2,0)\) for one run-time iteration, depending on the if condition in this run-time iteration. For two, three, and four run-time iterations, it is ⊤, i.e., we do not know the result. Once again, disregarding loop indices, the χ-terms \({\chi ^{w}_{3}}\) and \({\chi ^{w}_{4}}\) are the same . We have reached a fixed point, if we abstract two, three, and four run-time iterations to all further run-time iterations.

To formalize and generalize this, we extend the equivalence Definition 9 generalizing on (10). We do this in two steps. First, we introduce a loop index substitution and second, we define terms under this substitution as equivalent.

Definition 13 (Loop index substitution)

The loop-index-substituted χ-term of a χ-term t, denoted loop_index_sub(t), is the term identical to t except for all loop indices j of the χ-functions in func(t) are consistently replaced by j − 1.

Under the l-loop-approximation (a widening abstraction), we extend the equivalence Definition 9 by:

If we apply loop index substitution with any update, the updates are still monotone, the depths of χ-terms is finite, and the set of χ-functions is finite. Hence, the analysis is guaranteed to terminate in a fixed point.

4.3 The k-Approximation

The l-loop-approximation is sufficient to guarantee a conservative analysis that terminates, and thereby be sound. However, in practice, it is likely to be both slow and memory costly since the χ-terms, although finite, are likely to get large. A straightforward way to reduce the size of the χ-terms is to limit their maximum depth. This idea is similar to the finite call depth in a CFA analysis [34], or the context depth limitations in object-sensitive or this-sensitive points-to analysis [23, 24, 27].

In our case, we keep track of the last k control-flow options that might influence the value of a variable. Assuming a control-flow based block numbering as outlined in Section 3.1, this means that we keep more ”recent” control-flow options whereas more “remote” options are ⊔-approximated.

The k-approximation of χ-terms is easy to understand using the tree representation G_t = {N,E,r}. Whenever a new χ-term t is generated, we replace all χ-terms \(t_{sub}={\chi ^{b}_{i}}(t_{1}, {\ldots } , t_{p})\) in subterms(t) that has depth(t_sub,t) ≥ k with \(\dot \sqcup (t_{1}, \ldots ,t_{p})\). The process starts in the leaves and proceeds towards the root node. The result is a new χ-term t^(k) with depth(t^(k)) ≤ k that only embodies the last k control-flow options that might influence the value. Notice also that in the case k = 0 all context-sensitive information is lost and we have a context-insensitive analysis. An algorithm for k-approximation is formalized and discussed in Section 5.3.

The following example shows the result of two different k-approximations of the same χ-term a and Fig. 6 shows the corresponding tree representations.

Two different finite k approximations a⁽²⁾ and a⁽¹⁾ and of the same χ-term a

Full size image

4.4 Approximation Summary

The l-loop-approximation and the k-approximation can be seen as two different strategies to apply the ⊔-approximation. The aim of the l-approximation is to avoid generating infinite χ-terms when analyzing loops and other cyclic control-flow dependencies. It also guarantees analysis termination. The purpose of the k-approximation is to, at the cost of analysis precision, speed up the analysis and reduce the memory costs. They can be used separately or combined into what we refer to as a k,l-approximated analysis where loop related χ-terms are l-loop -approximated, and where all sub-terms having a depth ≥ k are ⊔-approximated.

The k,l-approximation is conservative since any ⊔-approximation is conservative. It also guarantees that every χ-term has a finite depth and that the analysis will terminate. Hence,

Theorem 5

Let \((A, \sqsubseteq , F, \iota )\) define a sound context-insensitive program analysis. Then \((k, l, X_{A}, \sqsubseteq _{\chi }, F, \iota )\), the corresponding k,l-approximated context-sensitive program analysis using χ-terms, is sound as well.

Theorem 5 concludes our formal presentation of χ-term based context-sensitive data-flow analysis. It shows that any sound context-insensitive analysis can be transformed into a sound context-sensitive χ-term based analysis that is guaranteed to terminate.

In this section, we discuss the compact representations of χ-terms along with some implementation details allowing for fast and memory efficient analyses. We start with a introductory example of compact χ-term representations in Section 5.1. In Section 5.2, we show how to create and maintain the redundant-free DAG-based representations of χ-terms without creating larger intermediate terms with redundancies that would then be in need of subsequent redundancy elimination. In Section 5.3, we introduce the creation of k-approximated χ-terms that limit their depth to an adjustable parameter k in order to trade precision against memory. In Section 5.4 we show an algorithm for l-loop-approximation to limit the size of loop-head χ-terms. Finally, in Section 5.5, we discuss the memory management of these two variants of χ-term representations.

5.1 Introductory Example of a Compact s of χ-Terms Representation

Consider the simple code fragment of Fig. 7. After the normalization with Algorithm 1 applying equivalence conversion (EC) but no termination conversion (TC) of eval_χ, the χ-terms for the variables x,y,a,b in are:

A source code example with corresponding basic block and SSA graphs

Full size image

As discussed in Section 3.3, every χ-term can naturally be viewed as a tree. This is illustrated in Fig. 8 (left) where we show the tree representation of the χ-term for the variable a. Each edge represents a particular control-flow option and each path from the root node to a leaf value contains the sequence of control-flow decisions required for that particular leaf value to be calculated in the corresponding program run.

Term for variable a = χ¹⁰(χ⁴(1,2),χ⁷(χ⁴(1,2),2)) is illustrated by its tree and directed acyclic graph representations (root at the bottom)

Full size image

Obviously, representing χ-terms as trees is in practice by far too expensive. A more cost efficient representation is a directed acyclic graph (DAG), similar to Binary-Decision-Diagrams (BDDs) [6, 7], which avoids redundant sub-trees. This is illustrated in Fig. 8 (right).

The property of the suggested DAG representation of terms is that every sub-tree is only constructed once, and then referred to when needed elsewhere instead of being reconstructed whenever needed. We need to maintain this value semantics of sub-term DAGs in a redundancy-free, hence, memory efficient, representation (implementation) of χ-terms.

Still, we can interpret the χ-terms in the DAG representation as before in the tree representation. For example, both representations of the term analyzed for the variable a can be interpreted as the values 1 and 2, resp., depending on the same control flows of the program, e.g., a = 1 if the conditions in all blocks #1,#4,#7 are true and, consequently, the left predecessor provides the value of a in all blocks #4,#7,#10.

Not only the interpretation is the same for the two representations, tree or DAG. Also the operations can be applied to both representations. Especially, the DAG representation does not need to be unfolded to a tree, in order to apply eval_χ including Shannon expansion and redundancy elimination.

For example, the below sequence shows the evaluation steps during normalization of Algorithm 1, applied to the χ-term for variable s = a + b.

The χ-term notation corresponds to the tree representation including some redundancy. For example, the sub-terms χ⁴(1,2) (in lines 2 and 3 of the example transformation) and χ⁴(4,5) (in the last line) occur several times in one and the same term, but cannot be removed by redundancy elimination.

Figure 9 shows the same evaluation steps directly transforming the DAG representation of the χ-term. The leftmost DAG in the figure represents the χ-term for s. The DAGs from left to the right correspond to new χ-terms after each evaluation step in the lines of the example (each equivalent to the original term). In each χ-term, any sub-term is only represented once and then referred to, e.g., the sub-terms χ⁴(1,2) and χ⁴(4,5) again.

Evaluation steps applying the equivalence conversions (EC) of eval_χ on the term generated for variable s = a + b = +(χ¹⁰(χ⁴(1,2),χ⁷(χ⁴(1,2),2)),χ⁷(3,4)) in directed acyclic graph representation

Full size image

It remains to show how a DAG based χ-term representation can be implemented efficiently maintaining the property that each sub-term is only constructed once, and than referred to when needed elsewhere.

5.2 Efficient Updates of Redundant-Free χ-Terms

We capture all unique χ-terms in a repository. When a new χ-term needs to be created during analysis, we check if there is an equivalent χ-term already captured in this repository. A straight-forward implementation of ≡_χ would recursively apply the Shannon expansion to bring the χ-terms in a normal form with χ-nodes ordered the same way, then recursively apply redundancy elimination on the (sub-) terms, and finally check for the equivalence of χ-terms by comparing the root nodes and their children recursively. This is a too expensive implementation.

Our suggested implementation implements redundancy elimination on-the-fly. It is based on maintaining some properties of the terms captured in the repository, and on aggressive hashing as outlined below and presented in detail in Algorithms 2 and 3 that follows.

Property (i): By construction, χ-terms stored in the repository do not contain operation function symbols f. Instead, χ-terms are captured in normal form after applying all equivalence conversions (EC) steps of eval_χ.

Property (ii): Each basic unique χ-term is a unique context-sensitive value a. We refer to a as the value number vn = a of the basic χ-term.

Property (iii): Each non-basic χ-term represents a unique context-insensitive value; it is also identified with a unique value number vn. Each non-basic χ-term is rooted by a χ-function symbol \({\chi ^{b}_{j}}\), which is uniquely determined by a block number b and an iteration index j. Each non-basic χ-term is captured as a tuple \([{\chi ^{b}_{j}},vn_{1}, \dots , vn_{p}]\) with the unique identifier of the root χ-function symbol \({\chi ^{b}_{j}}\) and \(vn_{1}, \dots , vn_{p}\) the value numbers for its children.

Note that the roots of different non-basic χ-terms may have the same χ-function symbol but different vn; vice-versa, identical χ-terms always have the same vn and the same χ-function symbol.

Property (iv): We avoid χ-function symbols \({\chi ^{b}_{j}}\) occurring in different orderings on the paths from the root to the leaves of a χ-term representation. This property trivially holds for the basic χ-terms (not containing χ-function symbols at all). For the non-basic χ-terms, it can easily be maintained by following the standard update order of a (forward) program analysis where SSA nodes are analyzed and updated in a data-driven way: nodes before their successors; inner loop nodes before outer loops. Otherwise, any consistent order scheme can be enforced if needed by Shannon expansion.

Property (v): We maintain a hash-map h mapping each χ-term created earlier—its root node and its sub-terms’ value numbers—to its corresponding value number vn:

Here \(\mathtt {r} \in \{{\chi ^{b}_{j}},\mathtt {f}\}\) is a χ- or an operation-function symbol. Note that we maintain the operation-function symbols in this mapping, but not in the representation of χ-terms. We also maintain the inverse mapping:

Assuming (i)–(v), two cases need to be distinguished when analyzing and updating an SSA node node. Next we informally describe them before we formalize them in Algorithms 2 and 3.

Case 1

node is a ϕ node in block b analyzed under the current loop index j and has the predecessors node₁,…,node_p. Recall that the (current) analysis values of these predecessors are χ-terms identified with their respective (current) value numbers vn₁,…,vn_p. If h contains a value number vn for the tuple \(({\chi ^{b}_{j}}, vn_{1}, \ldots , vn_{p})\), a corresponding χ-term has been created earlier, which is then analysis update for this node. Otherwise, in the special case of vn₁ = … = vn_p, we choose vn₁ as the value analyzed for node and book-keep this in h. This implements redundancy elimination. No new χ-term has to be created; the repository does not change. In general, if at least two predecessor value numbers are different, we create a new unique χ-term, i.e., a root \({\chi ^{b}_{j}}\) with a references to its children vn₁,…vn_p, and add it to the repository. We also create a new value number vn for this new unique term and book-keep this in h.

Case 2

node is an operation node with a function symbol and with the predecessor (argument) values vn₁,…,vn_p. Again, we check if the result of this update is known from before by consulting the hash-map h(,vn₁,…,vn_p). If h contains a corresponding value number vn, the new χ-term has been created earlier, which is then the analysis update for node. Again, no new χ-term has to be created; the repository does not change.

Otherwise, we need to recursively apply the Shannon expansion over the predecessor χ-terms h^− 1(vn₁),…,h^− 1(vn_p) to push to the leaves of these terms.

In the base case, vn₁,…,vn_p represent basic context-insensitive values. In this base case, we apply the insensitive analysis function f of to its insensitive arguments denoted by vn₁,…,vn_p and get a insensitive result denoted by vn. If it has not been computed earlier, we update h accordingly.

In the recursive case, at least one of the χ-terms h^− 1(vn₁),…,h^− 1(vn_p) has a χ-function symbol as its root. Assume \({\chi ^{b}_{j}}\) is the root of all these χ-terms with the highest iteration index j and block number b as the secondary ordering criterion, i.e., the highest (b,j)-rank. Accordingly, we implement the following Shannon expansion as a recursion step:

Each restriction \(t|_{(b,j):l}, l\in [1 {\ldots } p^{\prime }]\) constitutes a new χ-term creation request, i.e., a recursive application of Case 2 until the insensitive base cased is reached. Each such request leads to a χ-term with a corresponding value number vn^l. The final χ-term creation

is an application of Case 1.

The analysis update of SSA nodes is given in Algorithm 2. It calls the redundancy free χ-term creation formalized in Algorithm 3. Both algorithms follow the two cases described above.

The algorithms use the functions preds, current_analysis, type, basic, apply, arity, and new. They are informally defined as follows. The function preds applied to an SSA node returns the predecessors of node in the SSA graph. The function current_analysis applied to an SSA node returns the value number of the χ-term analyzed for node. The function type applied to an SSA node returns its node type, i.e., \({\phi _{j}^{b}}\) or . The test function basic(vn) checks if the term h^− 1(vn) is an context-insensitive value (true) or contains a χ-function symbol (false). Assume basic(vn_i) is true for all parameters i ∈ [1,p], i.e., h^− 1(vn_i) = a_i ∈ A, a context insensitive analysis value, then we \(apply(\mathtt {f},vn_{1},\dots ,vn_{p})\). This evaluates the context-insensitive transfer function f of to the context-insensitive analysis values:

returning the value number vn equal to the resulting basic context-insensitive value and equal to eval_⊔ in Section 2. According to its definition, the function arity(\({\chi ^{b}_{j}}\)) gives the number of children of a χ-node. Finally, the function new just creates a new χ-node of the DAG representing all χ-terms.

5.3 The k-Approximated χ-Term Creation

In case we want to limit the size of χ-terms by limiting their depths to k, we can replace the call to \(\mathit {create}({\chi _{j}^{b}},vn_{1},\dots ,vn_{p})\) with a call to the widening function \(\mathit {k\_approx}(k,[{\chi _{j}^{b}},vn_{1},\dots ,vn_{p}])\), cf. the out-commented alternative line in Algorithm 2. This alternative assures that the terms \(h^{-1}(vn_{1}),\dots ,h^{-1}(vn_{p})\) have depths of at most k − 1 by merging too deep leaves applying the insensitive meet function ⊔ instead of keeping context separated with the corresponding χ functions. The function k_approx and its subroutine collapse are defined in the Algorithms 4 and 5, respectively.

The two cases n = a ∈ A and k = 0 of k_approx defined in Algorithm 4 are base cases. The recursive step creates a new χ-term guaranteed to have sub-terms with maximum depth k − 1.

The function collapse defined in Algorithm 5 aggressively collapses any sub-terms by ⊔-approximating any remaining non-basic χ-term.

5.4 The l-Approximated χ-Term Creation

Section 4.2 introduce the l-approximation as a mean to stabilize the analysis of loops and to guarantee analysis termination. The basic idea is to replace every subterm \({\chi _{q}^{b}}(t_{1},\dots ,t_{p})\), with indices \(q = j-l,\dots ,0\), of a loop head χ-term \({\chi _{j}^{b}}\) by their ⊔-approximation. The function l_approx and its subroutine loop_approx are defined in the Algorithms 6 and 7, respectively.

Algorithms 6 starts by checking if the node is a loop head. A loop head χ-term always looks like \([{\chi _{j}^{b}},vn_{1},vn_{2}]\), a χ-function \({\chi _{j}^{b}}\), and two abstract values representing the loop entry value (represented by vn₁) and the values after one or more run-time iterations (represented by vn₂). We have two special cases where no approximation takes place: 1) At first entry (j = 0) we know that vn₁ is the value to use (point 5 of Definition 9). 2) The first l run-time iterations are not approximated and we apply the default handling for new χ-terms (Algorithm create). The actual approximation is handled in function loop_approx.

Algorithm 7, loop_approx(l,b,j,vn), recursively traverses vn in search of subterms \({\chi _{x}^{y}}\) with block number y = b and iteration index x = j − l which then are ⊔-approximated using \(\mathit {create}(\sqcup ,vn^{\prime }_{1},\ldots ,vn^{\prime }_{p})\). Notice: 1) we search for subterms with iterations index x = j − l since more remote subterms (x > j − l) will not exist if the l-approximation is applied consistently, and 2) \(\mathit {create}(\sqcup ,vn^{\prime }_{1},\ldots ,vn^{\prime }_{p})\) makes use of Case 2 of the create algorithm and pushes ⊔ to the leaves where it is applied.

5.5 Memory Management of χ-Terms During Analysis

Finally, we show that the memory consumed by the intermediate results of χ-terms can be controlled on-the-fly by identifying unused χ-(sub-)terms that can be freed directly. This means that we do not create large redundant-free but unused intermediate analysis results and that the size of the finally analyzed χ-terms is actually an upper bound of the memory footprint consumed during the whole analysis. We argued for this property of our χ-term representation in [12] and exploited it there by assessing and comparing only the memory sizes of the final analysis results of χ-term-based and alternative representations. Below we describe the “garbage collection” that guarantees this property.

Since χ-terms are directed acyclic graphs, we can use simple reference counting to free unused χ-(sub-)terms. Since value numbers are unique for each χ-(sub-)term, we can book-keep the references to a value number in order to count the references to each χ-(sub-)term and maintain a simple function:

There are only few locations in our analysis algorithms where new references to value numbers are added. One is the call \(vn \leftarrow \mathit {new}([ {\chi _{j}^{b}},vn_{1},\dots ,vn_{p}])\) in Algorithm 3. Each execution of this call to new, we set \(\mathit {count}(vn)\leftarrow 0\) (no reference to vn is added yet) and \(\forall i \in [1,p]: \mathit {count}(vn_{i}) \leftarrow \mathit {count}(vn_{i})+1\).

The roots references of the χ-terms are the analysis values for each SSA node captured in current_analysis(node). Hence, on each execution of an analysis value update \(\mathit {current\_analysis}(\mathit {node}) \leftarrow vn\) in Algorithm 2, we might need to update the reference count(vn), as well. More specifically, if a value number vn returned by the create call is different from the value number \(vn^{\prime }\) analyzed so far for the current node, we need to increase the count for vn and decrease it for \(vn^{\prime }\). To do so, we substitute the last line in Algorithm 2 by

The function maybe_free, detailed in Algorithm 8, is straight forward: it decreases the reference count for the argument value number \(vn^{\prime }\), checks if there are any references left and, if not, it frees the corresponding χ-term n, removes its footprint from the hash-maps, and, if n is not basic, recursively calls itself to the sub-terms’ value numbers.

Finally, free(n) is implemented using free-lists. Assume n is a basic χ-term representing a context-insensitive value, e.g., ⊥,⊤, constants or elements a of a power set lattice A. All context-insensitive values of the same analysis lattice require the same amount of memory, e.g., a symbolic constant or a bit vector. Hence, we can maintain separate free-lists for each context-insensitive analysis lattice.

Assume n is a χ-terms representing a context-sensitive value. Each node in this term captures its constant-size χ- or operation function symbol, and p value numbers vn_i referring to its children. While p can be different for different ϕ or operation SSA nodes, we can maintain separate free-lists for each fixed p occurring in the SSA representation of the program under analysis.

Global Value Numbering (GVN) is an approach to capture semantically equivalent values, (sub-) expressions, and assignments used, e.g., to propagate constants, to simplify expressions, and to eliminate redundancy, with the goals of optimizing the internal representation of a computer program [2]. So-called value graphs represent the symbolic executions of statements and expressions in a program. Splitting the value graphs into congruent partitions allows each partition to be replaced with the same program representation.

There are similarities between our χ-terms (represented with directed acyclic graphs) and the (directed, cyclic) value graphs. Both representations are based on an SSA representation of a program and use a graph to model how control-flow decisions affect the analysis values.

However, our main goal is to save representation space during analysis: χ-terms are therefore reduced to their normal form online during their construction while analyzing the value of each statement and expression. Instead of trying to conservatively proof the equivalence of (sub-) expressions, GVN uses an optimistic fixed-point iteration approach. Value graphs must be constructed first before partitioning can reduce them, which does not save analysis space. Moreover, the optimistic approach makes it difficult to find algebraic identities, e.g., that a = b + 1,c = a − 1 implies b == c, while our χ-term normalization naturally exploits algebraic identities.

Rütting et al. [17, 33] present an efficient approach to constant propagation using value graphs. Their approach is restricted to constant propagation whereas ours can be applied on any data-flow analysis problem. We use the Shannon expansion to push operators to the leaves, where the operation can be evaluated. This is not the case in the value graphs, where the operator nodes remain scattered over the value graphs. Moreover, by using χ-terms and pushing the evaluation to the leaves, we automatically remove the redundancies.

Harris et al. [11] use Satisfiability Modulo Theory (SMT) to create a path-sensitive analysis to verify safety properties of C programs. Their approach, called Satisfiability Module Path Programs, enumerates the existing paths in the program by using the Satisfiability Theory (SAT) formulas given by the control-flow in the program. Their approach is more precise than ours but does not scale to larger programs.^{Footnote 2}

Heinze et al. [13] take a similar approach. They apply data-flow analysis on an SSA representation of the program to derive variable path predicates for each SSA variable in the program. The path predicate contains detailed information (predicates) about every control decision that might influence a given variable value. These variable predicates can later be fed to an SMT solver to verify certain program properties.

Our χ-terms is an abstraction of the path-sensitive approaches used in Rütting et al., Harris et al. and Heinze et al. We only keep track of the last k contexts that might influence a given variable value, and we disregard detailed information under which control-flow predicates these contexts get active. Thus, we trade precision for performance allowing us to handle much larger programs.

In general, higher precision can be reached by using context-sensitive analysis at the cost of a larger memory consumption. This implies the need of data structures with efficient memory usage and operations that makes quick manipulations on these structures. Here the usage of Binary Decision Diagrams (BDD) offer such an approach, which was exploited before, especially, for Points-to Analysis:

• Zhu and Calman [42, 43] present an approach to points-to analysis that uses Symbolic Pointers. Blocks of memory are source (domain) and target (range) of references (pointers). Points-to relations are modelled as directed graph of such blocks. Each block has an id corresponding to a unique Boolean formula. An edge is represented as a pair of domain and range block ids, i.e., pairs of Boolean domain and range functions. These Boolean functions are captured as BDDs and updated during analysis using BDD operations. This saves memory and preserves update performance.

• Berndl et al. [4] use BDDs to minimize the representation of the points-to data. The points-to relations between variables and sets of abstract objects are represented by binary strings. For large programs, the number of such sets can be very large. The BDD approach reduces the memory of partially redundant points-to sets. An evaluation shows that the approach is beneficial for both execution time and memory consumption.

• Whaley and Lam [41] create a clone for different invocations of a method call (call paths). A context-insensitive analysis on the extended call graph representing all clones results in a context-sensitive analysis. The context-sensitive relations are captured using BDDs leading to an efficient memory usage.

• Based on benchmarks on different context-insensitive and context-sensitive analysis variants, Lhotak and Hendren [18] conclude that the best method for points-to analysis is object-sensitive [28]. The usage of BDDs in capturing the analysis data allows to increase the size of the analyzed programs. The same authors also discuss the effect on precision and efficiency of context-sensitive points-to analyses [20]. It shows that the precision is application dependent and that the efficiency depends on the used analysis method. The analysis framework, PADDLE is based on object-sensitivity and uses a BDD representation for the context-sensitive information. The resulting reduction of memory usage opens up for a more sensitive analyses to get a better accuracy.

• Ball and Rajamani introduce Bebop [3], a path-sensitive inter-procedural data-flow analysis tool for C programs. It adds data-flow facts to each vertex in a control-flow graph allowing to rule out paths that are not feasible in the analysis. For memory efficiency, the set of facts are captured in BDDs.

All above papers show that the usage of BDD provides memory efficient approaches to capture context-sensitive points-to information. Our paper introduces a systematic approach to generalize context-insensitive to context-sensitive analyses using BDDs.

Kim et al. [16] state the importance of utilizing different dimensions of sensitivity in static program analysis to improve the analysis precision. They present a general framework to capture many different dimensions of sensitivity, such as, context-, flow-, trace-sensitivity, that encompass a large variety of well-known analyses in all these dimensions and combination thereof. Using abstract interpretation, they show that each context-sensitive analysis instance of their framework is sound. Furthermore, they point out the importance of using a “sparse representation” based on “dictionaries” to handle the analysis data without providing any further implementation details. We focus on a data structure that have a sparse representation, and therefore suggest χ-terms as an efficient and flexible data structure to handle analysis information from any analysis generated by this framework.

Adding context-sensitivity to a context-insensitive analysis increases the precision of the results, but makes it more expensive in space and time. Therefore, it is a problem to select the variant and the depth of context-sensitivity. The ideal is a variant with positive effect on the result precision, but without using too much memory and time. In the following discussion, we call an approach selective if it selects among different context-sensitive analysis variants and adaptive if it selects the depth k of context-sensitivity:

• Kastrinis et al. [15] describe a selective approach creating an extended points-to analysis by combining the two different context-sensitive approaches (call-site- and object-sensitivity). The selection is guided by the available information at different analysis points. Such information includes knowledge about the type of calls and the type of the program. The evaluation shows that a combined approach (using additional depth of information) is successful concerning precision without introducing high performance and memory costs.

• Li et al. [22] present the so-called SCALAR framework implementing a selective approach, where different context-sensitive methods are compared and selected based on an estimation of the scalability risk. Pre-analysis using a first context-insensitive approach gives an approximation of the needed resources (total scalability threshold). This guides the automatic selection of the most suitable method amongst the available object- or type-sensitive methods in a second context-sensitive analysis. This approach meets scalability needs reducing the risk of timeouts.

• For better scalability allowing the analysis of larger programs and/or a better precision, an adaptive approach for context-sensitive analysis can be used. Smaragdakis et al. [35] suggest a two-step approach including a context-insensitive analysis to find procedures that can be analyzed with a context-sensitive method to increase precision without drawbacks on the performance (time and space). The first step selects methods or objects that should be analyzed a second time based on a mix of costs, e.g., the size of points-to sets or the maximum size of fields’ points-to sets relative to the number of fields. The idea is to avoid the methods or objects with high cost in the context-sensitive analysis phase. The evaluation shows that the approach gives good results in precision and scalability in the comparison with object-sensitivity, call-site-sensitivity, and type-sensitivity.

• Lee et al. [30] suggest the selection of a reasonable depth of context-sensitivity for k-call-string sensitivity. Their adaptive approach makes an impact estimation of the use of k-call-string-sensitivity balancing the expected precision and the analysis costs. The first step is a pre-analysis for finding the least value of k, fulfilling the context demand of context-sensitivity depending on the analysis queries. In a second step, each procedure is analyzed with the recommended depth k of context-sensitivity. This approach has been evaluated against a context-insensitive approach using ten software packages written in C. The result shows an improvement in precision.

• Jeong et al. [14] present a data-driven approach. Using machine learning on a large code base, their adaptive approach can learn the heuristic rules for selecting the depth of contexts. This learned heuristic is then used in the analysis of new programs. The results of analyzing new programs show that the approach is a fast alternative in comparison to the state-of-the-art points-to analyses.

• Li et al. [21] describe an adaptive approach called ZIPPER that strives to reduce the imprecision in points-to analysis by selecting methods that should use context-sensitive analysis. This selection relies on previously constructed Precision Flow Graphs (PFG) that are based on Object Flow Graphs [38]. Using the PFG of a class and based on the value flow of each method, the approach selects which methods to analyze in a context-(in)sensitive way. The results show that the precision is similar to 2-object-sensitive pointer analysis [28].

Thiessen and Lhotak [37] present another pointer analysis variant related to our k approximation. It uses transformation strings instead of the traditional context-strings. The idea combines the context-free language (CFL) reachability formulation of points-to analysis [31, 36] with k-object-sensitivity [28]. In CFL-reachability, abstract points-to relations are represented by paths (strings of node labels) in the call graph. Such a path relates sub-paths at the caller and callee sites, i.e., caller and callee contexts, referred to as a context transformation. Points-to analysis is formulated as an algebraic structure of context transformations. This abstraction can then be k-limited. The evaluation shows that this string abstraction instead of traditional context strings has a positive effect in most cases on the analysis time and on the overall precision.

The present paper formalizes the informal descriptions of χ-terms from our conference paper [40]. The paper is inspired by the ideas first presented, hinted, and implicitly assumed by Martin Trapp in his dissertation [39] (published in German). In our presentation of χ-terms, we have refined many of the notations that he introduced. We have also been able to prove many of the statements that he presented and implicitly assumed. The unique contributions in this paper are:

1. 1.

   We proved that a sound context-insensitive program analysis with the partial order relation \(\sqsubseteq \) has a corresponding sound context-sensitive program analysis using the partial order relation \(\sqsubseteq _{\chi }\).

2. 2.

   We proved that a ⊔-approximation of a χ-term is always conservative. This means that we in any phase of the analysis can widen a χ-term by its ⊔-approximation. This saves memory and still guarantees the soundness of the approach.

3. 3.

   We have presented two different parameterized approximations (k-approximation and l-loop-approximation) and proved that any analysis based on these approximations are sound and guaranteed to reach a fixed point.

4. 4.

   We give algorithms implementing an efficient construction of redundancy-free DAG-based χ-terms. The DAG representation and aggressive reuse of already existing χ-(sub-)terms give a very memory efficient representation of context-sensitive information. We also show how to manage the (theoretically) exponential memory consumption, using both widening operations and garbage collection.

Finally, this paper is a complement to our paper Memory Efficient Context-Sensitive Program Analysis [12] that evaluates the memory efficiency by comparing the memory foot-prints of χ-terms with four other data structures. The experiments use context-sensitive points-to analysis information taken from ten different Java benchmark programs. The results show that χ-terms are indeed memory efficient. They use on average only 13% of the memory used by the second best approach. Hence, [12] provides the experimental evidence, this paper presents χ-terms as a general framework for memory efficient context-sensitive program analyses.

Static program analysis is an important part of both optimizing compilers and software engineering tools for program verification and model checking. Such analyses can be context-sensitive or -insensitive, i.e., an analysis may or may not distinguish different analysis results for different execution paths. Context-sensitive analyses are, in general, more precise than their context-insensitive counterparts but also more expensive in terms of time and memory consumption.

This paper presents χ-terms as a means to capture context-sensitive analysis values for programs represented as SSA-graphs. Each meet point of execution paths in the program, i.e., each ϕ-node, is mapped to a χ-term whose children represent the alternative analysis values of these paths. The χ-terms are represented by graphs without any redundancy, which generalizes the idea behind OBDDs [6, 7].

For languages with conditional execution, the number of different contexts grows, in general, exponentially with the program size. Adding run-time iterations lead, in general, to countably (infinitely) many contexts. To handle this path-explosion problem, we introduce k-approximation and l-loop-approximation that limit the size of the context-sensitive information. We prove that each context-insensitive data-flow analysis has a corresponding k,l-approximated context-sensitive analysis, and we also prove that these k,l-approximated χ-terms form a partial ordered relation with a finite depth, thus, guaranteeing every data-flow analysis to reach a fixed point if their insensitive counterpart did.

The paper also give algorithms for how to implement redundancy-free, DAG-based, χ-terms. The DAG representation and aggressive reuse of already existing χ-(sub-)terms give a very memory efficient representation of context-sensitive information.

Finally, context-sensitive program analysis often comes with memory problems. We propose χ-terms as presented in this paper as a solution to this problem. The theory presented here is supported by experiments in [12] showing the memory efficiency of using χ-terms.