Krishnendu Chatterjee
email: [krishnendu.chatterjee@ist.ac.at

Amir Kafshdar Goharshady
email: amir.goharshady]@ist.ac.at

Rasmus Ibsen-Jensen
email: r.ibsen-jensen@liverpool.ac.uk

Andreas Pavlogiannis
email: pavlogiannis@cs.au.dk

Optimal and Perfectly Parallel Algorithms for On-demand Data-flow Analysis *

Keywords: Data-flow analysis, IFDS, Treewidth

Interprocedural data-flow analyses form an expressive and useful paradigm of numerous static analysis applications, such as live variables analysis, alias analysis and null pointers analysis. The most widely-used framework for interprocedural data-flow analysis is IFDS, which encompasses distributive data-flow functions over a finite domain. On-demand data-flow analyses restrict the focus of the analysis on specific program locations and data facts. This setting provides a natural split between (i) an offline (or preprocessing) phase, where the program is partially analyzed and analysis summaries are created, and (ii) an online (or query) phase, where analysis queries arrive on demand and the summaries are used to speed up answering queries. In this work, we consider on-demand IFDS analyses where the queries concern program locations of the same procedure (aka same-context queries). We exploit the fact that flow graphs of programs have low treewidth to develop faster algorithms that are space and time optimal for many common data-flow analyses, in both the preprocessing and the query phase. We also use treewidth to develop query solutions that are embarrassingly parallelizable, i.e. the total work for answering each query is split to a number of threads such that each thread performs only a constant amount of work. Finally, we implement a static analyzer based on our algorithms, and perform a series of on-demand analysis experiments on standard benchmarks. Our experimental results show a drastic speed-up of the queries after only a lightweight preprocessing phase, which significantly outperforms existing techniques.

Introduction

Static data-flow analysis. Static program analysis is a fundamental approach for both analyzing program correctness and performing compiler optimizations [START_REF] Cousot | Static determination of dynamic properties of recursive procedures[END_REF][START_REF] Knoop | The interprocedural coincidence theorem[END_REF][START_REF] Muchnick | Advanced Compiler Design and Implementation[END_REF][START_REF] Torczon | Engineering a Compiler[END_REF][START_REF] Giegerich | Invariance of approximate semantics with respect to program transformations[END_REF]. Static data-flow analyses associate with each program location a set of data-flow facts which are guaranteed to hold under all program executions, and these facts are then used to reason about program correctness, report erroneous behavior, and optimize program execution. Static data-flow analyses have numerous applications, such as in pointer analysis (e.g., pointsto analysis and detection of null pointer dereferencing) [START_REF] Nanda | Accurate interprocedural null-dereference analysis for java[END_REF][START_REF] Shang | On-demand dynamic summary-based points-to analysis[END_REF][START_REF] Sridharan | Refinement-based context-sensitive points-to analysis for java[END_REF][START_REF] Sridharan | Demand-driven points-to analysis for java[END_REF][START_REF] Xu | Scaling cfl-reachability-based points-to analysis using context-sensitive must-not-alias analysis[END_REF][START_REF] Yan | Demand-driven context-sensitive alias analysis for java[END_REF][START_REF] Zheng | Demand-driven alias analysis for c[END_REF], in detecting privacy and security issues (e.g., taint analysis, SQL injection analysis) [START_REF] Arzt | FlowDroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps[END_REF][START_REF] Hovemeyer | Finding bugs is easy[END_REF][START_REF] Gould | Jdbc checker: A static analysis tool for SQL/JDBC applications[END_REF][START_REF] Guarnieri | Saving the world wide web from vulnerable javascript[END_REF][START_REF] Rapoport | Precise data flow analysis in the presence of correlated method calls[END_REF][START_REF] Krüger | CrySL: An Extensible Approach to Validating the Correct Usage of Cryptographic APIs[END_REF], as well as in compiler optimizations (e.g., constant propagation, reaching definitions, register allocation) [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF][START_REF] Grove | Interprocedural constant propagation: A study of jump function implementation[END_REF][START_REF] Sagiv | Precise interprocedural dataflow analysis with applications to constant propagation[END_REF][START_REF] Callahan | Interprocedural constant propagation[END_REF][START_REF] Appel | Modern Compiler Implementation in Java[END_REF].

Interprocedural analysis and the IFDS framework. Data-flow analyses fall in two large classes: intraprocedural and interprocedural. In the former, each procedure of the program is analyzed in isolation, ignoring the interaction between procedures which occurs due to parameter passing/return. In the latter, all procedures of the program are analyzed together, accounting for such interactions, which leads to results of increased precision, and hence is often preferable to intraprocedural analysis [START_REF] Reps | Undecidability of context-sensitive data-dependence analysis[END_REF][START_REF] Rountev | Interprocedural dataflow analysis in the presence of large libraries[END_REF][START_REF] Smaragdakis | Pick your contexts well: Understanding object-sensitivity[END_REF][START_REF] Späth | Context-, flow-, and field-sensitive data-flow analysis using synchronized pushdown systems[END_REF]]. To filter out false results, interprocedural analyses typically employ call-context sensitivity, which ensures that the underlying execution paths respect the calling context of procedure invocations. One of the most widely used frameworks for interprocedural data-flow analysis is the framework of Interprocedural Finite Distributive Subset (IFDS) problems [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF], which offers a unified formulation of a wide class of interprocedural data-flow analyses as a reachability problem. This elegant algorithmic formulation of data-flow analysis has been a topic of active study, allowing various subsequent practical improvements [START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF][START_REF] Naeem | Practical extensions to the ifds algorithm[END_REF][START_REF] Bodden | Spllift: Statically analyzing software product lines in minutes instead of years[END_REF][START_REF] Arzt | FlowDroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps[END_REF][START_REF] Rapoport | Precise data flow analysis in the presence of correlated method calls[END_REF][START_REF] Schubert | PhASAR: An inter-procedural static analysis framework for C/C++[END_REF] and implementations in prominent static analysis tools such as Soot [START_REF] Bodden | Inter-procedural data-flow analysis with IFDS/IDE and soot[END_REF] and WALA [START_REF] Pavlogiannis | Watson libraries for analysis[END_REF].

On-demand analysis. Exhaustive data-flow analysis is computationally expensive and often unnecessary. Hence, a topic of great interest in the community is that of on-demand data-flow analysis [START_REF] Babich | The method of attributes for data flow analysis[END_REF][START_REF] Duesterwald | Demand-driven computation of interprocedural data flow[END_REF][START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF][START_REF] Reps | Demand interprocedural program analysis using logic databases[END_REF][START_REF] Reps | Program analysis via graph reachability[END_REF][START_REF] Yuan | Demand-driven data flow analysis for communication optimization[END_REF][START_REF] Naeem | Practical extensions to the ifds algorithm[END_REF]. On-demand analyses have several applications, such as (quoting from [START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF][START_REF] Reps | Program analysis via graph reachability[END_REF]) (i) narrowing down the focus to specific points of interest, (ii) narrowing down the focus to specific data-flow facts of interest, (iii) reducing work in preliminary phases, (iv) sidestepping incremental updating problems, and (v) offering demand analysis as a user-level operation. On-demand analysis is also extremely useful for speculative optimizations in just-in-time compilers [START_REF] Chen | Data dependence profiling for speculative optimizations[END_REF][START_REF] Lin | A compiler framework for speculative optimizations[END_REF][START_REF] Bebenita | Spur: A trace-based JIT compiler for CIL[END_REF][START_REF] Flückiger | Correctness of speculative optimizations with dynamic deoptimization[END_REF], where dynamic information can dramatically increase the precision of the analysis. In this setting, it is crucial that the the on-demand analysis runs fast, to incur as little overhead as possible.

Example 1. As a toy motivating example, consider the partial program shown in Figure 1, compiled with a just-in-time compiler that uses speculative optimizations. Whether the compiler must compile the expensive function h depends on whether x is null in line 6. Performing a null-pointer analysis from the entry of f reveals that x might be null in line 6. Hence, if the decision to compile h relies only on an offline static analysis, h is always compiled, even when not needed. Now consider the case where the execution of the program is in line 4, and at this point the compiler decides on whether to compile h. It is clear that given this information, x cannot be null in line 6 and thus h does not have to be compiled. As we have seen above, this decision can not be made based on offline analysis. On the other hand, an on-demand analysis starting from the current program location will correctly conclude that x is not null in line 6. Note however, that this decision is made by the compiler during runtime. Hence, such an on-demand analysis is useful only if it can be performed extremely fast. It is also highly desirable that the time for running this analysis is predictable, so that the compiler can decide whether to run the analysis or simply compile h proactively.

The techniques we develop in this paper answer the above challenges rigorously. Our approach exploits a key structural property of flow graphs of programs, called treewidth.

Treewidth of programs.

A very well-studied notion in graph theory is the concept of treewidth of a graph, which is a measure of how similar a graph is to a tree (a graph has treewidth 1 precisely if it is a tree) [START_REF] Robertson | Graph minors. iii. planar tree-width[END_REF]. On one hand the treewidth property provides a mathematically elegant way to study graphs, and on the other hand there are many classes of graphs which arise in practice and have constant treewidth. The most important example is that the flow graph for goto-free programs in many classic programming languages have constant treewidth [START_REF] Thorup | All structured programs have small tree width and good register allocation[END_REF]. The low treewidth of flow graphs has also been confirmed experimentally for programs written in Java [START_REF] Gustedt | The treewidth of java programs[END_REF], C [START_REF] Krause | The tree-width of C[END_REF], Ada [START_REF] Burgstaller | On the tree width of ada programs[END_REF] and Solidity [START_REF] Chatterjee | The treewidth of smart contracts[END_REF].

Treewidth has important algorithmic implications, as many graph problems that are hard to solve in general admit efficient solutions on graphs of low treewidth. In the context of program analysis, this property has been exploited to develop improvements for register allocation [START_REF] Thorup | All structured programs have small tree width and good register allocation[END_REF][START_REF] Bodlaender | Linear-time register allocation for a fixed number of registers[END_REF] (a technique implemented in the Small Device C Compiler [START_REF] Dutta | Anatomy of a compiler[END_REF]), cache management [START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF], on-demand algebraic path analysis [START_REF] Chatterjee | Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth[END_REF], on-demand intraprocedural data-flow analysis of concurrent programs [START_REF] Chatterjee | Algorithms for algebraic path properties in concurrent systems of constant treewidth components[END_REF] and data-dependence analysis [START_REF] Chatterjee | Optimal dyck reachability for data-dependence and alias analysis[END_REF].

Problem statement. We focus on on-demand data-flow analysis in IFDS [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF][START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF][START_REF] Reps | Program analysis via graph reachability[END_REF]. The input consists of a supergraph G of n vertices, a data-fact domain D and a data-flow transformer function M . Edges of G capture control-flow within each procedure, as well as procedure invocations and returns. The set D defines the domain of the analysis, and contains the data facts to be discovered by the analysis for each program location. The function M associates with every edge (u, v) of G a data-flow transformer M (u, v) : 2 D → 2 D . In words, M (u, v) defines the set of data facts that hold at v in some execution that transitions from u to v, given the set of data facts that hold at u.

On-demand analysis brings a natural separation between (i) an offline (or preprocessing) phase, where the program is partially analyzed, and (ii) an online (or query) phase, where on-demand queries are handled. The task is to preprocess the input in the offline phase, so that in the online phase, the following types of on-demand queries are answered efficiently:

1. A pair query has the form (u, d 1 , v, d 2 ), where u, v are vertices of G in the same procedure, and d 1 , d 2 are data facts. The goal is to decide if there exists an execution that starts in u and ends in v, and given that the data fact d 1 held at the beginning of the execution, the data fact d 2 holds at the end. These are known as same-context queries and are very common in data-flow analysis [START_REF] Chaudhuri | Subcubic algorithms for recursive state machines[END_REF][START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF][START_REF] Chatterjee | Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth[END_REF]]. 2. A single-source query has the form (u, d 1 ), where u is a vertex of G and d 1 is a data fact. The goal is to compute for every vertex v that belongs to the same procedure as u, all the data facts that might hold in v as witnessed by executions that start in u and assuming that d 1 holds at the beginning of each such execution.

Previous results. The on-demand analysis problem admits a number of solutions that lie in the preprocessing/query spectrum. On the one end, the preprocessing phase can be disregarded, and every on-demand query be treated anew. Since each query starts a separate instance of IFDS, the time to answer it is O(n•|D| 3 ), for both pair and single-source queries [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF]. On the other end, all possible queries can be pre-computed and cached in the preprocessing phase in time O(n 2 • |D| 3 ), after which each query costs time proportional to the size of the output (i.e., O(1)) for pair queries and O(n• |D|) for single-source queries). Note that this full preprocessing also incurs a cost O(n 2 • |D| 2 ) in space for storing the cache table, which is often prohibitive. On-demand analysis was more thoroughly studied in [START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF]. The main idea is that, instead of pre-computing the answer to all possible queries, the analysis results obtained by handling each query are memoized to a cache table, and are used for speeding up the computation of subsequent queries. This is a heuristic-based approach that often works well in practice, however, the only guarantee provided is that of same-worst-case-complexity, which states that in the worst case, the algorithm uses O(n 2 • |D| 3 ) time and O(n 2 • |D| 2 ) space, similarly to the complete preprocessing case. This guarantee is inadequate for runtime applications such as the example of Figure 1, as it would require either (i) to run a full analysis, or (ii) to run a partial analysis which might wrongly conclude that h is reachable, and thus compile it. Both cases incur a large runtime overhead, either because we run a full analysis, or because we compile an expensive function.

Our contributions. We develop algorithms for on-demand IFDS analyses that have strong worst-case time complexity guarantees and thus lead to more predictable performance than mere heuristics. The contributions of this work are as follows:

1. We develop an algorithm that, given a program represented as a supergraph of size n and a data fact domain ) space at all times, which is proportional to the size of the input, and is thus space optimal. Hence, our algorithm not only improves upon previous state-of-the-art solutions, but also ensures optimality in both time and space. 2. We also show that after our one-time preprocessing, each query is embarrassingly parallelizable, i.e., every bit of the output can be produced by a single thread in O(1) time. This makes our techniques particularly useful to speculative optimizations, since the analysis is guaranteed to take constant time and thus incur little runtime overhead. Although the parallelization of data-flow analysis has been considered before [START_REF] Lee | Performing data flow analysis in parallel[END_REF][START_REF] Lee | A comprehensive approach to parallel data flow analysis[END_REF][START_REF] Rodriguez | Actor-based parallel dataflow analysis[END_REF], this is the first time to obtain solutions that span beyond heuristics and offer theoretical guarantees. Moreover, this is a rather surprising result, given that general IFDS is known to be P-complete. 3. We implement our algorithms on a static analyzer and experimentally evaluate their performance on various static analysis clients over a standard set of benchmarks. Our experimental results show that after only a lightweight preprocessing, we obtain a significant speedup in the query phase compared to standard on-demand techniques in the literature. Also, our parallel implementation achieves a speedup close to the theoretical optimal, which illustrates that the perfect parallelization of the problem is realized by our approach in practice. Recently, we exploited the low-treewidth property of programs to obtain faster algorithms for algebraic path analysis [START_REF] Chatterjee | Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth[END_REF] and intraprocedural reachability [START_REF] Chatterjee | Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs[END_REF]. Data-flow analysis can be reduced to these problems. Hence, the algorithms in [START_REF] Chatterjee | Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth[END_REF][START_REF] Chatterjee | Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs[END_REF] can also be applied to our setting. However, our new approach has two important advantages: (i) we show how to answer queries in a perfectly parallel manner, and (ii) reducing the problem to algebraic path properties and then applying the algorithms in [START_REF] Chatterjee | Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth[END_REF][START_REF] Chatterjee | Optimal reachability and a space-time tradeoff for distance queries in constant-treewidth graphs[END_REF] . Hence, our space usage and query times are better by a factor of log n ¶ . Moreover, when considering the complexity wrt n, i.e. considering D to be a constant, these results are optimal wrt both time and space. Hence, no further improvement is possible. Remark. Note that our approach does not apply to arbitrary CFL reachability in constant treewidth. In addition to the treewidth, our algorithms also exploit specific structural properties of IFDS. In general, small treewidth alone does not improve the complexity of CFL reachability [START_REF] Chatterjee | Optimal dyck reachability for data-dependence and alias analysis[END_REF].

Preliminaries

Model of computation. We consider the standard RAM model with word size W = Θ(log n), where n is the size of our input. In this model, one can store W bits in one word (aka "word tricks") and arithmetic and bitwise operations between pairs of words can be performed in O(1) time. In practice, word size is a property of the machine and not the analysis. Modern machines have words of size at least 64. Since the size of real-world input instances never exceeds 2 64 , the assumption of word size W = Θ(log n) is well-realized in practice and no additional effort is required by the implementer to account for W in the context of data flow analysis. Graphs. We consider directed graphs G = (V, E) where V is a finite set of vertices and E ⊆ V × V is a set of directed edges. We use the term graph to refer to directed graphs and will explicitly mention if a graph is undirected. For two vertices u, v ∈ V, a path P from u to v is a finite sequence of vertices P = (w i ) k i=0 such that w 0 = u, w k = v and for every i < k, there is an edge from w i to w i+1 in E. The length |P | of the path P is equal to k. In particular, for every vertex u, there is a path of length 0 from u to itself. We write P : u v to denote that P is a path from u to v and u v to denote the existence of such a path, i.e. that v is reachable from u. Given a set V ⊆ V of vertices, the induced subgraph of G on V is defined as

G[V ] = (V , E ∩ (V × V )). Finally, the graph G is called bipartite if the set V can be partitioned into two sets V 1 , V 2 , so that every edge has one end in V 1 and the other in V 2 , i.e. E ⊆ (V 1 × V 2 ) ∪ (V 2 × V 1 ).

The IFDS Framework

IFDS [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF] is a ubiquitous and general framework for interprocedural data-flow analyses that have finite domains and distributive flow functions. It encompasses a wide variety of analyses, including truly-live variables, copy constant propagation, possibly-uninitialized variables, secure information-flow, and gen/kill or bitvector problems such as reaching definitions, available expressions and live variables [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF][START_REF] Bodden | Inter-procedural data-flow analysis with IFDS/IDE and soot[END_REF]. IFDS obtains interprocedurally precise solutions. In contrast to intraprocedural analysis, in which precise denotes "meet-over-all-paths", interprocedurally precise solutions only consider valid paths, i.e. paths in which when a function reaches its end, control returns back to the site of the most recent call [START_REF] Sharir | Two approaches to interprocedural data flow analysis[END_REF]. Flow graphs and supergraphs. In IFDS, a program with k procedures is specified by a supergraph, i.e. a graph G = (V, E) consisting of k flow graphs G 1 , . . . , G k , one for each procedure, and extra edges modeling procedure-calls. Flow graphs represent procedures in the usual way, i.e. they contain one vertex v i for each statement i and there is an edge from v i to v j if the statement j may immediately follow the statement i in an execution of the procedure. The only exception is that a procedure-call statement i is represented by two vertices, a call vertex c i and a return-site vertex r i . The vertex c i only has incoming edges, and the vertex r i only has outgoing edges. There is also a call-to-return-site edge from c i to r i . The call-to-return-site edges are included for passing intraprocedural information, such as information about local variables, from c i to r i . Moreover, each flow graph G l has a unique start vertex s l and a unique exit vertex e l .

The supergraph G also contains the following edges for each procedure-call i with call vertex c i and return-site vertex r i that calls a procedure l: (i) an interprocedural call-to-start edge from c i to the start vertex of the called procedure, i.e. s l , and (ii) an interprocedural exit-to-return-site edge from the exit vertex of the called procedure, i.e. e l , to r i . Example 2. Figure 2 shows a simple C++ program on the left and its supergraph on the right. Each statement i of the program has a corresponding vertex v i in the supergraph, except for statement 7, which is a procedure-call statement and hence has a corresponding call vertex c 7 and return-site vertex r 7 . Interprocedurally valid paths. Not every path in the supergraph G can potentially be realized by an execution of the program. Consider a path P in G and let P be the sequence of vertices obtained by removing every v i from P , i.e. P only consists of c i 's and r i 's. Then, P is called a same-context valid path if P can be generated from S in this grammar:

S → c i S r i S for a procedure-call statement i | ε .
Moreover, P is called an interprocedurally valid path or simply valid if P can be generated from the nonterminal S in the following grammar:

S → S c i S for a procedure-call statement i | S .
For any two vertices u, v of the supergraph G, we denote the set of all interprocedurally valid paths from u to v by IVP(u, v) and the set of all same-context valid paths from u to v by SCVP(u, v). Informally, a valid path starts from a statement in a procedure p of the program and goes through a number of procedure-calls while respecting the rule that whenever a procedure ends, control should return to the return-site in its parent procedure. A same-context valid path is a valid path in which every procedure-call ends and hence control returns back to the initial procedure p in the same context. IFDS [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF]. An IFDS problem instance is a tuple I = (G, D, F, M, ) where:

-G = (V, E) is a supergraph as above.
-D is a finite set, called the domain, and each d ∈ D is called a data flow fact.

-The meet operator is either intersection or union.

-F ⊆ 2 D → 2 D is a set of distributive flow functions over , i.e. for each function f ∈ F and every two sets of facts

D 1 , D 2 ⊆ D, we have f (D 1 D 2 ) = f (D 1 ) f (D 2
). -M : E → F is a map that assigns a distributive flow function to each edge of the supergraph. Let P = (w i ) k i=0 be a path in G, e i = (w i-1 , w i ) and m i = M (e i ). In other words, the e i 's are the edges appearing in P and the m i 's are their corresponding distributive flow functions. The path function of P is defined as:

pf P := m k • • • • • m 2 • m 1 where • denotes function composition. The solution of I is the collection of values {MVP v } v∈V : MVP v := P ∈IVP(s main ,v) pf P (D).
Intuitively, the solution is defined by taking meet-over-all-valid-paths. If the meet operator is union, then MVP v is the set of data flow facts that may hold at v, when v is reached in some execution of the program. Conversely, if the meet operator is intersection, then MVP v consists of data flow facts that must hold at v in every execution of the program that reaches v. Similarly, we define the same-context solution of I as the collection of values {MSCP v } v∈V main defined as follows:

MSCP

v := P ∈SCVP(s main ,v) pf P (D). (1)
The intuition behind MSCP is similar to that of MVP, except that in MSCP v we consider meet-over-same-context-paths (corresponding to runs that return to the same stack state).

Remark 1. We note two points about the IFDS framework:

-As in [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF], we only consider IFDS instances in which the meet operator is union. Instances with intersection can be reduced to union instances by dualization [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF]. -For brevity, we are considering a global domain D, while in many applications the domain is procedure-specific. This does not affect the generality of our approach and our algorithms remain correct for the general case where each procedure has its own dedicated domain. Indeed, our implementation supports the general case.

Succinct representations. A distributive function f : 2 D → 2 D can be succinctly represented by a relation R f ⊆ (D ∪ {0}) × (D ∪ {0}
) defined as:

R f := {(0, 0)} ∪ {(0, b) | b ∈ f (∅)} ∪ {(a, b) | b ∈ f ({a}) -f (∅)}.
Given that f is distributive over union, we have

f ({d 1 , . . . , d k }) = f ({d 1 })∪• • •∪ f ({d k }). Hence, to specify f it is sufficient to specify f (∅) and f ({d}) for each d ∈ D. This is exactly what R f does.
In short, we have: Bounded Bandwidth Assumption. Following [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF], we assume that the bandwidth in function calls and returns is bounded by a constant. In other words, there is a small constant b, such that for every edge e that is a call-to-start or exit-toreturn-site edge, every vertex in the graph representation H M (e) has degree b or less. This is a classical assumption in IFDS [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF][START_REF] Bodden | Inter-procedural data-flow analysis with IFDS/IDE and soot[END_REF] and models the fact that every parameter in a called function is only dependent on a few variables in the callee (and conversely, every returned value is only dependent on a few variables in the called function).

f (∅) = {b ∈ D | (0, b) ∈ R f } and f ({d}) = f (∅) ∪ {b ∈ D | (d, b) ∈ R f }. Moreover,
Composition of distributive functions. Let f and g be distributive functions and R f and R g their succinct representations. It is easy to verify that g • f is also distributive, hence it has a succinct representation R g•f . Moreover, we have

R g•f = R f ; R g = {(a, b) | ∃c (a, c) ∈ R f ∧ (c, b) ∈ R g }. 0 a b 0 a b 0 a b 0 a b λx.{a} λx.x ∪ {a} λx. {a} x = ∅ ∅ x = ∅ Fig. 4: Obtaining H g•f (right) from H f and H g (left)
Example 4. In terms of graphs, to compute H g•f , we first take H f and H g , then contract corresponding vertices in the lower part of H f and the upper part of H g , and finally compute reachability from the topmost part to the bottommost part of the resulting graph. Consider f (x) = x ∪ {a}, g(x) = {a} for x = ∅ and g(∅) = ∅, then g • f (x) = {a} for all x ⊆ D. Figure 4 shows contracting of corresponding vertices in H f and H g (left) and using reachability to obtain

H g•f (right).
G = (V , E) where V = V × D * and E = ((u, d 1 ), (v, d 2 )) | e = (u, v) ∈ E ∧ (d 1 , d 2 ) ∈ R M (e) .
A path P in G is (same-context) valid, if the path P in G, obtained by ignoring the second component of every vertex in P , is (same-context) valid. As shown in [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF], for a data flow fact d ∈ D and a vertex v ∈ V, we have

d ∈ MVP v iff there is a valid path in G from (s main , d ) to (v, d) for some d ∈ D ∪ {0}.
Hence, the IFDS problem is reduced to reachability by valid paths in G. Similarly, the same-context IFDS problem is reduced to reachability by same-context valid paths in G.

Example 5. Consider a null pointer analysis on the program in Figure 2. At each program point, we want to know which pointers can potentially be null. We first model this problem as an IFDS instance. Let D = {x, ȳ}, where x is the data flow fact that x might be null and ȳ is defined similarly. Figure 5 shows the same program and its exploded supergraph. At point 8, the values of both pointers x and y are used. Hence, if either of x or y is null at 8, a null pointer error will be raised. However, as evidenced by the two valid paths shown in red, both x and y might be null at 8. The pointer y might be null because it is passed to the function f by value (instead of by reference) and keeps its local value in the transition from c 7 to r 7 , hence the edge ((c 7 , ȳ), (r 7 , ȳ)) is in G. On the other hand, the function f only initializes y, which is its own local variable, and does not change x (which is shared with main).

1 void f ( int *& x , int * y ) { 2 y = new int (1); 3 y = new int (2); 4 } 5 int main () { 6 int *x , * y ; 7 f (x , y ); 8 * x += * y ; 9 } v 5 v 6 c 7 r 7 v 8 v 9 v 1 v 2 v 3 v 4 ȳ x 0 ȳ x 0
Fig. 5: A Program (left) and its Exploded Supergraph (right).

Trees and Tree Decompositions

Trees. A rooted tree T = (V T , E T ) is an undirected graph with a distinguished "root" vertex r ∈ V T , in which there is a unique path P u v between every pair {u, v} of vertices. We refer to the number of vertices in V T as the size of T . For an arbitrary vertex v ∈ V T , the depth of v, denoted by d v , is defined as the length of the unique path P r v : r v. The depth or height of T is the maximum depth among its vertices. A vertex u is called an ancestor of v if u appears in P r v . In this case, v is called a descendant of u. In particular, r is an ancestor of every vertex and each vertex is both an ancestor and a descendant of itself. We denote the set of ancestors of v by A ↑ v and its descendants by D ↓ v . It is straightforward to see that for every 0 ≤ d ≤ d v , the vertex v has a unique ancestor with depth d. We denote this ancestor by a d v . The ancestor

p v = a dv-1 v of v at depth d v -1 is called the parent of v and v is a child of p v . The subtree T ↓ v corresponding to v is defined as T [D ↓ v ] = (D ↓ v , E T ∩ 2 D ↓ v ), i.e.
the part of T that consists of v and its descendants. Finally, a vertex v ∈ V T is called a leaf if it has no children. Given two vertices u, v ∈ V T , the lowest common ancestor lca(u, v) of u and v is defined as argmax w∈A ↑ u ∩A ↑ v d w . In other words, lca(u, v) is the common ancestor of u and v with maximum depth, i.e. which is farthest from the root.

Lemma 1 ([34]

). Given a rooted tree T of size n, there is an algorithm that preprocesses T in O(n) and can then answer lowest common ancestor queries, i.e. queries that provide two vertices u and v and ask for lca(u, v), in O(1).

Tree decompositions [START_REF] Robertson | Graph minors. iii. planar tree-width[END_REF]. Given a graph G = (V, E), a tree decomposition of G is a rooted tree T = (B, E T ) such that:

(i) Each vertex b ∈ B of T has an associated subset V (b) ⊆ V of vertices of G and b∈B V (b) = V.
For clarity, we call each vertex of T a "bag" and reserve the word vertex for G. Informally, each vertex must appear in some bag. (ii) For all (u, v) ∈ E, there exists a bag b ∈ B such that u, v ∈ V (b), i.e. every edge should appear in some bag. (iii) For any pair of bags b i , b j ∈ B and any bag b k that appears in the path

P : b i b j , we have V (b i ) ∩ V (b j ) ⊆ V (b k ), i.e
. each vertex should appear in a connected subtree of T . The width of the tree decomposition T = (B, E T ) is defined as the size of its largest bag minus 1. The treewidth tw(G) of a graph G is the minimal width among its tree decompositions. A vertex v ∈ V appears in a connected subtree, so there is a unique bag b with the smallest possible depth such that v ∈ V (b). We call b the root bag of v and denote it by rb(v).

v 1 v 5 v 4 v 2 v 3 v 7 v 6 {v 1 , v 2 , v 5 } {v 2 , v 3 , v 5 } {v 3 , v 4 , v 5 } {v 2 , v 6 , v 7 } b 1 b 2 b 3 b 4
Fig. 6: A Graph G (left) and its Tree Decomposition T (right).

It is well-known that flow graphs of programs have typically small treewidth [START_REF] Thorup | All structured programs have small tree width and good register allocation[END_REF]. For example, programs written in Pascal, C, and Solidity have treewidth at most 3, 6 and 9, respectively. This property has also been confirmed experimentally for programs written in Java [START_REF] Gustedt | The treewidth of java programs[END_REF], C [START_REF] Krause | The tree-width of C[END_REF] and Ada [START_REF] Burgstaller | On the tree width of ada programs[END_REF]. The challenge is thus to exploit treewidth for faster interprocedural on-demand analyses. The first step in this approach is to compute tree decompositions of graphs. As the follow-ing lemma states, tree decompositions of low-treewidth graphs can be computed efficiently.

Lemma 2 ( [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF]). Given a graph G with constant treewidth t, a binary tree decomposition of size O(n) bags, height O(log n) and width O(t) can be computed in linear time.

Separators [START_REF] Cygan | [END_REF]. The key structural property that we exploit in low-treewidth flow graphs is a separation property

. Let A, B ⊆ V. The pair (A, B) is called a separation of G if (i) A ∪ B = V,
. Let A = t∈T b V (t) and B = t∈T b V (t). Then (A, B) is a separation of G and its corresponding separator is A ∩ B = V (b) ∩ V (b ).
Example 6. Figure 6 shows a graph and one of its tree decompositions with width 2. In this example, we have rb

(v 5 ) = b 1 , rb(v 3 ) = b 2 , rb(v 4 ) = b 3 , and rb(v 7 ) = b 4 .
For the separator property of Lemma 3, consider the edge {b 2 , b 4 }. By removing it, T breaks into two parts, one containing the vertices

A = {v 1 , v 2 , v 3 , v 4 , v 5 } and the other containing B = {v 2 , v 6 , v 7 }. We have A ∩ B = {v 2 } = V (b 2 ) ∩ V (b 4 ). Also, any path from B -A = {v 6 , v 7 } to A -B = {v 1 , v 3 , v 4 , v 5 } or vice versa must pass through {v 2 }. Hence, (A, B) is a separation of G with separator V (b 2 ) ∩ V (b 4 ) = {v 2 }.

Problem definition

We consider same-context IFDS problems in which the flow graphs G i have a treewidth of at most t for a fixed constant t. We extend the classical notion of same-context IFDS solution in two ways: (i) we allow arbitrary start points for the analysis, i.e. we do not limit our analyses to same-context valid paths that start at s main ; and (ii) instead of a one-shot algorithm, we consider a two-phase process in which the algorithm first preprocesses the input instance and is then provided with a series of queries to answer. We formalize these points below. We fix an IFDS instance

I = (G, D, F, M, ∪) with exploded supergraph G = (V , E).
Meet over same-context valid paths. We extend the definition of MSCP by specifying a start vertex u and an initial set ∆ of data flow facts that hold at u. Formally, for any vertex v that is in the same flow graph as u, we define:

MSCP u,∆,v := P ∈SCVP(u,v) pf P (∆).
(

) 2
The only difference between (2) and ( 1) is that in (1), the start vertex u is fixed as s main and the initial data-fact set ∆ is fixed as D, while in (2), they are free to be any vertex/set.

G i = (V i , E i
), the answer to the single source query is a sequence of

|V i | • |D * | bits, one for each (v, d 2 ) ∈ V i × D * , signifying
whether it is reachable by same-context valid paths from (u, d 1 ). Intuitively, a single-source query asks for all pairs (v, d 2 ) such that (i) v is reachable from u by a same-context valid path and (ii)

d 2 ∈ MSCP u,{d1}∩D,v ∪ {0}.
Intuition. We note the intuition behind such queries. We observe that since the functions in F are distributive over ∪, we have MSCP u,∆,v = ∪ δ∈∆ MSCP u,{δ},v , hence MSCP u,∆,v can be computed by O(|∆|) single-source queries.

4 Treewidth-based Data-flow Analysis

Preprocessing

The original solution to the IFDS problem, as first presented in [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF], reduces the problem to reachability over a newly constructed graph. We follow a similar approach, except that we exploit the low-treewidth property of our flow graphs at every step. Our preprocessing is described below. It starts with computing constant-width tree decompositions for each of the flow graphs. We then use standard techniques to make sure that our tree decompositions have a nice form, i.e. that they are balanced and binary. Then comes a reduction to reachability, which is similar to [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF]. Finally, we precompute specific useful reachability information between vertices in each bag and its ancestors. As it turns out in the next section, this information is sufficient for computing reachability between any pair of vertices, and hence for answering IFDS queries.

Overview. Our preprocessing consists of the following steps:

(1) Finding Tree Decompositions. In this step, we compute a tree decomposition T i = (B i , E Ti ) of constant width t for each flow graph G i . This can either be done by applying the algorithm of [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF] directly on G i , or by using an algorithm due to Thorup [START_REF] Thorup | All structured programs have small tree width and good register allocation[END_REF] and parsing the program. (2) Balancing and Binarizing. In this step, we balance the tree decompositions T i using the algorithm of Lemma 2 and make them binary using the standard process of [START_REF] Chaudhuri | Shortest paths in digraphs of small treewidth. part i: Sequential algorithms[END_REF]. (3) LCA Preprocessing. We preprocess the T i 's for answering lowest common ancestor queries using Lemma 1. Steps (1)-(3) above are standard and well-known processes. We now provide details of steps ( 4)- [START_REF] Blackburn | The DaCapo benchmarks: Java benchmarking development and analysis[END_REF]. To skip the details and read about the query phase, see Section 4.3 below.

Step (4): Reduction to Reachability

In this step, our goal is to compute a new graph Ĝ from the exploded supergraph G such that there is a path from (u, d 1 ) to (v, d 2 ) in Ĝ iff there is a same-context valid path from (u, d 1 ) to (v, d 2 ) in G. The idea behind this step is the same as that of the tabulation algorithm in [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF]. Summary edges. Consider a call vertex c l in G and its corresponding return-site vertex r l . For d 1 , d 2 ∈ D * , the edge ((c l , d 1 ), (r l , d 2 )) is called a summary edge if there is a same-context valid path from (c l , d 1 ) to (r l , d 2 ) in the exploded supergraph G. Intuitively, a summary edge summarizes the effects of procedure calls (same-context interprocedural paths) on the reachability between c l and r l . From the definition of summary edges, it is straightforward to verify that the graph Ĝ obtained from G by adding every summary edge and removing every interprocedural edge has the desired property, i.e. a pair of vertices are reachable in Ĝ iff they are reachable by a same-context valid path in G. Hence, we first find all summary edges and then compute Ĝ. This is shown in Algorithm 1. We now describe what Algorithm 1 does. Let s p be the start point of a procedure p. A shortcut edge is an edge ((s p , d 1 ), (v, d 2 )) such that v is in the same procedure p and there is a same-context valid path from (s p , d 1 ) to (v, d 2 ) in G. The algorithm creates an empty graph H = (V , E ). Note that H is implicitly represented by only saving E . It also creates a queue Q of edges to be added to H (initially Q = E) and an empty set S which will store the summary edges. The goal is to construct H such that it contains (i) intraprocedural edges of G, (ii) summary edges, and (iii) shortcut edges.

Algorithm 1: Computing Ĝ in Step (4) 1 Q ← E; 2 S ← ∅; 3 E ← ∅; 4 while Q = ∅ do 5 Choose e = ((u, d1), (v, d2)) ∈ Q; 6 Q ← Q -{e}; 7 if (u, v) is
if ((sp, d3), (v, d2)) ∈ E ∪ Q then 13 Q ← Q ∪ {((sp, d3), (v, d2))}; 14 if u = sp and v = ep then 15 foreach (c l , d3) s.t. ((c l , d3), (u, d1)) ∈ E do 16 foreach d4 s.t. ((v, d2), (r l , d4)) ∈ E do 17 if ((c l , d3), (r l , d4)) ∈ E ∪ Q then 18 S ← S ∪ {((c l , d3), (r l , d4))}; 19 Q ← Q ∪ {((c l , d3), (r l , d4))}; 20 Ĝ ← G; 21 foreach e = ((u, d1), (v, d2)) ∈ E do
It constructs H one edge at a time. While there is an unprocessed intraprocedural edge e = ((u, d 1 ), (v, d 2 )) in Q, it chooses one such e and adds it to H (lines 5-10). Then, if (u, d 1 ) is reachable from (s p , d 3 ) via a same-context valid path, then by adding the edge e, the vertex (v, d 2 ) also becomes accessible from (s p , d 3 ). Hence, it adds the shortcut edge ((s p , d 3 ), (v, d 2 )) to Q, so that it is later added to the graph H. Moreover, if u is the start s p of the procedure p and v is its end e p , then for every call vertex c l calling the procedure p and its respective return-site r l , we can add summary edges that summarize the effect of calling p (lines [START_REF] Chatterjee | Optimal dyck reachability for data-dependence and alias analysis[END_REF][START_REF] Chatterjee | The treewidth of smart contracts[END_REF][START_REF] Chatterjee | Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth[END_REF][START_REF] Chatterjee | Efficient parameterized algorithms for data packing[END_REF][START_REF] Chatterjee | JTDec: A tool for tree decompositions in soot[END_REF][START_REF] Chatterjee | Algorithms for algebraic path properties in concurrent systems of constant treewidth components[END_REF]. Finally, lines 20-24 compute Ĝ as discussed above.

Correctness. As argued above, every edge that is added to H is either intraprocedural, a summary edge or a shortcut edge. Moreover, all such edges are added to H, because H is constructed one edge at a time and every time an edge e is added to H, all the summary/shortcut edges that might occur as a result of adding e to H are added to the queue Q and hence later to H. Therefore, Algorithm 1 correctly computes summary edges and the graph Ĝ. ). For a more detailed analysis, see [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF]Appendix].

Step (5): Local Preprocessing

In this step, we compute the set R local of local reachability edges, i.e. edges of the form ((u, d 1 ), (v, d 2 )) such that u and v appear in the same bag b of a tree decomposition T i and (u,

d 1 ) (v, d 2 ) in Ĝ. We write (u, d 1 ) local (v, d 2 ) to denote ((u, d 1 ), (v, d 2 )) ∈ R local .
Note that Ĝ has no interprocedural edges. Hence, we can process each T i separately. We use a divide-and-conquer technique similar to the kernelization method used in [START_REF] Chaudhuri | Shortest paths in digraphs of small treewidth. part i: Sequential algorithms[END_REF] (Algorithm 2).

Algorithm 2 processes each tree decomposition T i separately. When processing T , it chooses a leaf bag b l of T and computes all-pairs reachability on the induced subgraph H l = Ĝ[V (b l ) × D * ], consisting of vertices that appear in b l . Then, for each pair of vertices (u, d 1 ) and (v, d 2 ) s.t. u and v appear in b l and (u, d 1 ) (v, d 2 ) in H l , the algorithm adds the edge ((u, d 1 ), (v, d 2 )) to both R local and Ĝ (lines 7-9). Note that this does not change reachability relations in Ĝ, given that the vertices connected by the new edge were reachable by a path before adding it. Then, if b l is not the only bag in T , the algorithm recursively calls itself over the tree decomposition T -b l , i.e. the tree decomposition obtained by removing b l (lines 10-11). Finally, it repeats the reachability computation on H l (lines 12-14). The running time of the algorithm is O(n • |D * | 3 ).

Example 7. Consider the graph G and tree decomposition T given in Figure 6 and let D * = {0}, i.e. let Ĝ and Ḡ be isomorphic to G. Figure 7 illustrates the steps taken by Algorithm 2. In each step, a bag is chosen and a local all-pairs reachability computation is performed over the bag. Local reachability edges are added to R local and to Ĝ (if they are not already in Ĝ).

We now prove the correctness and establish the complexity of Algorithm 2. Correctness. We prove that when computeLocalReachability(T ) ends, the set R local contains all the local reachability edges between vertices that appear in the same bag in T. The proof is by induction on the size of T. If T consists of a single bag, then the local reachability computation on H l (lines 7-9) fills R local correctly. Now assume that T has n bags. Let

H -l = Ĝ[∪ bi∈T,i =l V (b i ) × D * ].
7 foreach u, v ∈ V (b l ), d1, d2 ∈ D * s.t. (u, d1) (v, d2) in Ĝ[V (b l ) × D * ] do 8 Ĝ = Ĝ ∪ {((u, d1), (v, d2))}; 9 R local = R local ∪ {((u, d1), (v, d2))}; 10 if bp = null then 11 computeLocalReachability(T -b l ); 12 foreach u, v ∈ V (b l ), d1, d2 ∈ D * s.t. (u, d1) (v, d2) in Ĝ[V (b l ) × D * ] do 13 Ĝ = Ĝ ∪ {((u, d1), (v, d2))}; 14 R local = R local ∪ {((u, d1), (v, d2))};
Intuitively, H -l is the part of Ĝ that corresponds to other bags in T , i.e. every bag except the leaf bag b l . After the local reachability computation at lines 7-9, (v, d 2 ) is reachable from (u, d 1 ) in H -l only if it is reachable in Ĝ. This is because (i) the vertices of H

(n • t 3 • |D * | 3 ) = O(n • |D * | 3
). Note that the treewidth t is a constant and hence the factor t 3 can be removed.

Step (6): Ancestors Reachability Preprocessing

This step aims to find reachability relations between each vertex of a bag and vertices that appear in the ancestors of that bag. As in the previous case, we compute a set R anc and write (u,

d 1 ) anc (v, d 2 ) if ((u, d 1 ), (v, d 2 )) ∈ R anc .
This step is performed by Algorithm 3. For each bag b and vertex (u, d) such that u ∈ V (b) and each 0 ≤ j < d v , we maintain two sets: F (u, d, b, j) and F (u, d, b, j) each containing a set of vertices whose first coordinate is in the ancestor of b at depth j. Intuitively, the vertices in F (u, d, b, j) are reachable After the execution of Algorithm 3, we have (v,

v 1 v 5 v 4 v 2 v 3 v 7 v 6 v 1 v 5 v 4 v 2 v 3 v 7 v 6 v 1 v 5 v 4 v 2 v 3 v 7 v 6 v 1 v 5 v 4 v 2 v 3 v 7 v 6 v 1 v 5 v 4 v 2 v 3 v 7 v 6 v 1 v 5 v 4 v 2 v 3 v 7 v 6 v 1 v 5 v 4 v 2 v 3 v 7 v 6 v 1 v 5 v 4 v 2 v 3 v 7 v 6 b 4 {v 2 , v 6 , v 7 } b 3 {v 3 , v 4 , v 5 } b 2 {v 2 , v 3 , v 5 } b 1 {v 1 , v 2 , v 5 } b 2 {v 2 , v 3 , v 5 } b 3 {v 3 , v 4 , v 5 } b 4 {v 2 , v 6 , v 7 }
d 2 ) ∈ F (u, d 1 , b, j) iff (i) (v, d 2 ) is reachable from (u,
4 foreach u ∈ V (b) ∩ V (bp), d ∈ D * do 5 foreach 0 ≤ j < d b do 6 F (u, d, b, j) ← F (u, d, bp, j); 7 F (u, d, b, j) ← F (u, d, bp, j); 8 foreach u, v ∈ V (b), d1, d2 ∈ D * do 9 if (u, d1) local (v, d2) then 10 F (u, d1, b, d b ) ← F (u, d1, b, d b ) ∪ {(v, d2)}; 11 F (v, d2, b, d b ) ← F (v, d2, b, d b ) ∪ {(u, d1)}; 12 foreach 0 ≤ j < d b do 13 F (u, d1, b, j) ← F (u, d1, b, j) ∪ F (v, d2, b, j); 14 F (v, d2, b, j) ← F (v, d2, b, j) ∪ F (u, d1, b, j) 15 Ranc ← {((u, d1), (v, d2)) | ∃b, j (v, d2) ∈ F (u, d1, b, j) ∨ (u, d1) ∈ F (v, d2, b, j)};
ancestor of b at depth j. Conversely, (u,

d 1 ) ∈ F (v, d 2 , b, j) iff (i) (v, d 2 ) is reach- able from (u, d 1 ) and (ii) v ∈ V (b) and u ∈ V (a j b ). Algorithm 3 has a runtime of O(n • |D| 3 • log n). See Appendix A.
1 for detailed proofs. In the next section, we show that this runtime can be reduced to O(n • |D| 3 ) using word tricks. , and so on. We use a similar encoding for F . Using this encoding, Algorithm 3 can be rewritten by word tricks and bitwise operations as follows:

Word Tricks

-Lines 5-6 copy F (u, d, b p , -) into F (u, d, b, -). However, we have to shift and align the bits, so these lines can be replaced by

F (u, d, b, -) ← F (u, d, b p , -) |V (b)| • |D * |;
-Line 10 sets a single bit to 1.

-Lines 12-13 perform a union, which can be replaced by the bitwise OR operation. Hence, these lines can be replaced by

F (u, d 1 , b, -) ← F (u, d 1 , b, -) OR F (v, d 2 , b, -);
-Computations on F can be handled similarly. Note that we do not need to compute R anc explicitly given that our queries can be written in terms of the F and F sets. It is easy to verify that using these word tricks, every W operations in lines 6, 7, 13 and 14 are replaced by one or two bitwise operations on words. Hence, the overall runtime of Algorithm 3 is reduced to

O n•|D * | 3 •log n W = O(n • |D * | 3 ).

Answering Queries

We now describe how to answer pair and single-source queries using the data saved in the preprocessing phase.

Parallelizability and Optimality

We now turn our attention to parallel versions of our query algorithms, as well as cases where the algorithms are optimal.

Parallelizability. Assume we have k threads in our disposal. Optimality. Observe that when |D| = O(1), i.e. when the domain is small, our algorithm is optimal : the preprocessing runs in O(n), which is proportional to the size of the input, and the pair query and single-source query run in times O(1) and O(n/ log n), respectively, each case being proportional to the size of the output. Small domains arise often in practice, e.g. in dead-code elimination or null-pointer analysis.

Experimental Results

We report on an experimental evaluation of our techniques and compare their performance to standard alternatives in the literature.

Benchmarks. We used 5 classical data-flow analyses in our experiments, including reachability (for dead-code elimination), possibly-uninitialized variables analysis, simple uninitialized variables analysis, liveness analysis of the variables, and reaching-definitions analysis. We followed the specifications in [START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF] for modeling the analyses in IFDS. We used real-world Java programs from the DaCapo benchmark suite [START_REF] Blackburn | The DaCapo benchmarks: Java benchmarking development and analysis[END_REF], obtained their flow graphs using Soot [START_REF] Vallée-Rai | Soot -a Java bytecode optimization framework[END_REF] and applied the JTDec tool [START_REF] Chatterjee | JTDec: A tool for tree decompositions in soot[END_REF] for computing balanced tree decompositions. Given that some of these benchmarks are prohibitively large, we only considered their main Java packages, i.e. packages containing the starting point of the programs. We experimented with a total of 22 benchmarks, which, together with the 5 analyses above, led to a total of 110 instances. Our instance sizes, i.e. number of vertices and edges in the exploded supergraph, range from 22 to 190, 591. See Appendix A.6 for details.

Implementation and comparison. We implemented both variants of our approach, i.e. sequential and parallel, in C++. We also implemented the parts of the clas-sical IFDS algorithm [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF] and its on-demand variant [START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF] responsible for samecontext queries. All of our implementations closely follow the pseudocodes of our algorithms and the ones in [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF][START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF], and no additional optimizations are applied. We compared the performance of the following algorithms for randomlygenerated queries:

-SEQ. The sequential variant of our algorithm.

-PAR. A variant of our algorithm in which the queries are answered using perfect parallelization and 12 threads. -NOPP. The classical same-context IFDS algorithm of [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF], with no preprocessing. NOPP performs a complete run of the classic IFDS algorithm for each query. -CPP. The classical same-context IFDS algorithm of [START_REF] Reps | Precise interprocedural dataflow analysis via graph reachability[END_REF], with complete preprocessing. In this algorithm, all summary edges and reachability information are precomputed and the queries are simple table lookups. -OD. The on-demand same-context IFDS algorithm of [START_REF] Horwitz | Demand interprocedural dataflow analysis[END_REF]. This algorithm does not preprocess the input. However, it remembers the information obtained in each query and uses it to speed-up the following queries. For each instance, we randomly generated 10,000 pair queries and 100 singlesource queries. In case of single-source queries, source vertices were chosen uniformly at random. For pair queries, we first chose a source vertex uniformly at random, and then chose a target vertex in the same procedure, again uniformly at random. Experimental setting. The results were obtained on Debian using an Intel Xeon E5-1650 processor (3.2 GHz, 6 cores, 12 threads) with 128GB of RAM. The parallel results used all 12 threads. Time limit. We enforced a preprocessing time limit of 5 minutes per instance. This is in line with the preprocessing times of state-of-the-art tools on benchmarks of this size, e.g. Soot takes 2-3 minutes to generate all flow graphs for each benchmark.

Results. We found that, except for the smallest instances, our algorithm consistently outperforms all previous approaches. Our results were as follows: Treewidth. The maximum width amongst the obtained tree decompositions was 9, while the minimum was 1. Hence, our experiments confirm the results of [START_REF] Gustedt | The treewidth of java programs[END_REF][START_REF] Chatterjee | JTDec: A tool for tree decompositions in soot[END_REF] and show that real-world Java programs have small treewidth. See Appendix A.6 for more details. Preprocessing Time. As in Figure 8, our preprocessing is more lightweight and scalable than CPP. Note that CPP preprocessing times out at 25 of the 110 instances, starting with instances of size < 50, 000, whereas our approach can comfortably handle instances of size 200, 000. Although the theoretical worst-case complexity of CPP preprocessing is O(n 2 • |D| 3 ), we observed that its runtime over our benchmarks grows more slowly. We believe this is because our benchmark programs generally consist of a large number of small procedures. Hence, the worst-case behavior of CPP preprocessing, which happens on instances with large procedures, is not captured by the DaCapo benchmarks. In contrast, our preprocessing time is O(n • |D| having small or large procedures does not matter to our algorithms. Hence, we expect that our approach would outperform CPP preprocessing more significantly on instances containing large functions. However, as Figure 8 demonstrates, our approach is faster even on instances with small procedures. Query Time. As expected, in terms of pair query time, NOPP is the worst performer by a large margin, followed by OD, which is in turn extremely less efficient than CPP, PAR and SEQ (Figure 9, top). This illustrates the underlying trade-off between preprocessing and query-time performance. Note that both CPP and our algorithms (SEQ and PAR), answer each pair query in O(1). They all have pair-query times of less than a millisecond and are indistinguishable in this case. The same trade-off appears in single-source queries as well (Figure 9, bottom). Again, NOPP is the worst performer, followed by OD. SEQ and CPP have very similar runtimes, except that SEQ outperforms CPP in some cases, due to word tricks. However, PAR is extremely faster, which leads to the next point. Parallelization. In Figure 9 (bottom right), we also observe that single-source queries are handled considerably faster by PAR in comparison with SEQ. Specifically, using 12 threads, the average single-source query time is reduced by a factor of 11.3. Hence, our experimental results achieve nearperfect parallelism and confirm that our algorithm is well-suited for parallel architectures.

Note that Figure 9 combines the results of all five mentioned data-flow analyses. However, the observations above hold independently for every single analysis, as well. Due to space constraints, analysis-specific figures are relegated to Appendix A.7. Each row starts with a global picture (left) and zooms into smaller time units (right) to differentiate between the algorithms. The plots above contain results over all five analyses. However, our observations hold independently for every single analysis, as well (See Appendix A.7).

Conclusion

We developed new techniques for on-demand data-flow analyses in IFDS, by exploiting the treewidth of flow graphs. Our complexity analysis shows that our techniques (i) have better worst-case complexity, (ii) offer certain optimality guarantees, and (iii) are embarrassingly paralellizable. Our experiments demonstrate these improvements in practice: after a lightweight one-time preprocessing, queries are answered as fast as the heavyweight complete preprocessing, and the parallel speedup is close to its theoretical optimal. The main limitation of our approach is that it only handles same-context queries. Using treewidth to speedup non-same-context queries is a challenging direction of future work. step and Section A.4 provides an algorithm for answering single-source queries using the data collected in this step. [START_REF] Bodden | Inter-procedural data-flow analysis with IFDS/IDE and soot[END_REF] Descendants Reachability Preprocessing. The algorithm computes reachability information between each vertex and vertices appearing in its subtree of the tree decomposition. Formally, for each pair of vertices (u, d 1 ) and (v, d 2 ) such that (i) rb(u) = b for some bag b ∈ B i and (ii) the root bag of v is a descendant of b in T i , the algorithm establishes and remembers whether there exists a path P : (u, d 1 ) (v, d 2 ) in Ĝ, such that the root bag of every vertex appearing in P is a descendant of b. Similar to the previous cases, we use the notation (u, d 1 ) desc (v, d 2 ) for this case. This step is performed by Algorithm 4. For each vertex (v, d) the algorithm keeps track of a set F (v, d) consisting of some vertices that are reachable from (v, d). First, each F (v, d) is initialized to only contain (v, d) itself. The algorithm processes each tree decomposition T i in a bottom-up manner. At each bag b, the algorithm considers every u ∈ V (b) and every v with root bag b and checks if there is a path from (u, d 1 ) to (v, d 2 ). If so, then every vertex reachable from (v, d 2 ) is also reachable from (u, d 1 ). Hence, the algorithm adds F (v, d 2 ) to F (u, d 1 ). Finally, the algorithm computes R desc as the set of all edges ((u, d 1 ), (v, d 2 )) such that (v, d 2 ) is in F (u, d 1 ). We denote the latter by (u, d 1 ) desc (v, d 2 ). Algorithm 4: Descendants Preprocessing in Step ( 7)

1 foreach v ∈ V, d ∈ D * do 2 F (v, d) ← {(v, d)}; 3 foreach Ti = (Bi, ET i ) do 4 foreach b ∈ Bi in bottom-up order do 5 foreach u, v ∈ V (b), d1, d2 ∈ D * do 6 if rb(v) = b and (u, d1) local (v, d2) then 7 F (u, d1) ← F (u, d1) ∪ F (v, d2); 8 R desc ← {((u, d1), (v, d2)) | (v, d2) ∈ F (u, d1)};
Correctness. We prove that at the end of Algorithm 4, we have (u, d) desc (w, d ) iff there exists a path P : (u, d) (w, d ) in Ĝ such that the root bags of all vertices appearing in P are descendants of the root bag rb(u) of u. First, if (u, d) desc (w, d ) then there exists a (v, d 2 ) such that (w, d ) was added to F (u, d) through F (v, d 2 ) in line 7. Given that (u, d) local (v, d 2 ) (the condition in line 6), the edge ((u, d), (v, d 2 )) is present in Ĝ. Hence, we can obtain the desired path P by adding this edge to the beginning of the path from (v, d 2 ) to (w, d ), which can in turn be obtained by repeating the same process. For the converse, suppose there exists a path P : (u, d) (w, d ) with the desired properties. By Lemma 4, P goes through each bag b that appears in the unique path between rb(u) and rb(w). Without loss of generality, we can assume that P enters and exits each such bag at most once, because the local reachability information between vertices in the same bag are now captured by the edges in R local which are entirely within that bag. For each bag b, let (v b , d b ) be the last vertex of b that is visited by P . It is straightforward to verify that using (v, Formally, we traverse each T i in a pre-order manner and assign an incremental index i(u, d 1 ) to each vertex (u, d 1 ) when the root bag of u is visited. For vertices with the same root bag, we assign the index in lexicographic order. After this traversal, for each vertex (u, d 1 ), the α u • |D * | vertices whose first component's root bag is a descendant of rb(u) receive contiguous indexes. We denote this set by ∇ u , the first index in this set by β u and its last index by γ u .

We store each F (u, d 1 ) as a binary sequence of length |∇ u | = α u • |D * |, whose first bit denotes whether the vertex with index β u is in F (u, d 1 ) or not, its second bit corresponds to the vertex with index β u + 1 and so on. We assume that the F (u, d 1 )'s are initially a sequence of 0's. Using this definition, Algorithm 4 can be rewritten by word tricks as follows:

-Line 2 is simply setting one bit in the sequence F (v, d) to 1. This bit should correspond to i(v, d), hence we can replace Line 2 with

F (v, d)[i(v, d) -β v ] ← 1;
-Line 7 is a union operation which can be implemented by the bitwise OR operation. We also have to align the indexes in F (u, d 1 ) and F (v, d 2 ), which can be achieved by shifting the bits in F (v, d 2 ) to the left. Hence, this line can be replaced with

F (u, d 1 ) ← F (u, d 1 ) OR F (v, d 2 ) (β v -β u );
Finally, we do not need to explicitly compute R desc . If we want to check whether (u, d 1 ) desc (v, d 2 ), we can look into the bit at index i(v, d 2 ) -β u of F (u, d 1 ). Using these tricks, every Θ(W ) = Ω(log n) operations in line 7 can be replaced by O(1) bitwise operations. Hence, the overall runtime of the algorithm is reduced by a factor of log n.

We now provide a more detailed proof of the runtime. Given that the tree decompositions are balanced, we have v∈V α

v = O(n • log n). Each time line 7 is executed, it takes O |F (v,d2)| W time.
Hence, the overall runtime is:

v∈V d2∈D * u∈V (rb(v)) d1∈D * |F (v, d 2 )| W ≤ |D * | 2 • t • v∈V α v • |D * | W = O n • log n • |D * | 3 W = O(n • |D * | 3 ).

A.4 Answering a Single-source Query

In this section, we show how to use the data collected by Step (7) of our preprocessing algorithm, i.e. descendants reachability preprocessing, to answer a single-source query.

Answering a Single-source Query. We handle a single-source query from (u, d 1 ) with u ∈ V i as follows: Correctness. Suppose there exists a path P : We use the indexes assigned to vertices in Section A.3. In Step (iii), for every (w, d 2 ) that satisfies the required conditions, we let F (w, d 2 ) be the contiguous subsequence of F (w, d 2 ) that corresponds to vertices in the desired subtree (either left or right). We set A as the union of F (w, d 2 ) and A. This can be achieved by the following bitwise OR operation (after shifting F (w, d 2 ) to align it with A):

(u, d 1 ) (v, d 3 ). Let b = lca(rb(u), rb(v)). If b = rb(u), then (v, d 3 ) is added to A at step (iv). Similarly, if b = rb(v), then (v,
A ← A OR F (w, d 2 ) β w ;

Using this technique, the runtime is reduced by a factor of W . Hence, the total runtime of the query is

O |V i | • |D * | 2 W .

A.6 Details of Benchmarks

Table 1 provides details of our benchmarks. For each benchmark, we report number of its procedures, number of vertices and edges in its flow graphs, and the width of the tree decompositions obtained by [START_REF] Chatterjee | JTDec: A tool for tree decompositions in soot[END_REF]. Note that [START_REF] Chatterjee | JTDec: A tool for tree decompositions in soot[END_REF] is not an exact tool, i.e. its output tree decompositions might not have the optimal width. Hence, the reported numbers are upper-bounds on treewidths of the benchmarks.

In the last 5 columns, we report sizes of the IFDS instances corresponding to each analysis. The size of an instance is the total number of vertices and edges of its exploded supergraph.

A.7 Analysis-specific Experimental Results

We performed experiments using 5 different data-flow analyses, namely (i) reachability (for dead-code elimination), (ii) possibly-uninitialized variables analysis, (iii) simple uninitialized variables analysis, (iv) liveness analysis and (v) reaching definitions. Due to space constraints, the figures in the main text combine the results of all analyses. In this section, we provide the same figures for each analysis separately.

Fig. 1 :

 1 Fig. 1: A partial C++ program.

Fig. 2 :

 2 Fig. 2: A C++ program (left) and its supergraph (right).

Fig. 3 :Example 3 .

 33 Fig. 3: Succinct representation of several distributive functions.

  Exploded supergraph. Given an IFDS instance I = (G, D, F, M, ∪) with supergraph G = (V, E), its exploded supergraph G is obtained by taking |D * | copies of each vertex in V , one corresponding to each element of D * , and replacing each edge e with the graph representation H M (e) of the flow function M (e). Formally,

  and (ii) no edge connects a vertex in A -B to a vertex in B -A or vice versa. If (A, B) is a separation, the set A ∩ B is called a separator. The following lemma states such a separation property for low-treewidth graphs. Lemma 3 (Cut Property [25]). Let T = (B, E T ) be a tree decomposition of G = (V, E) and e = {b, b } ∈ E T . If we remove e, the tree T breaks into two connected components, T b and T b , respectively containing b and b

( 4 )

 4 Reduction to Reachability. In this step, we modify the exploded supergraph G = (V , E) to obtain a new graph Ĝ = (V , Ê), such that for every pair of vertices (u, d 1 ) and (v, d 2 ), there is a path from (u, d 1 ) to (v, d 2 ) in Ĝ iff there is a same-context valid path from (u, d 1 ) to (v, d 2 ) in G. So, this step reduces the problem of reachability via same-context valid paths in G to simple reachability in Ĝ. (5) Local Preprocessing. In this step, for each pair of vertices (u, d 1 ) and (v, d 2 ) for which there exists a bag b such that both u and v appear in b, we compute and cache whether (u, d 1 ) (v, d 2 ) in Ĝ. We write (u, d 1 ) local (v, d 2 ) to denote a reachability established in this step. (6) Ancestors Reachability Preprocessing. In this step, we compute reachability information between each vertex in a bag and vertices appearing in its ancestors in the tree decomposition. Concretely, for each pair of vertices (u, d 1 ) and (v, d 2 ) such that u appears in a bag b and v appears in a bag b that is an ancestor of b, we establish and remember whether (u, d 1 ) (v, d 2 ) in Ĝ and whether (v, d 2 ) (u, d 1 ) in Ĝ. As above, we use the notations (u, d 1 ) anc (v, d 2 ) and (v, d 2 ) anc (u, d 1 ).

22 if u and v are not in the same procedure then 23 Ĝ = Ĝ -{e}; 24 Ĝ

 222324 ← Ĝ ∪ S;

  Complexity. Note that the graph H has at most O(|E| • |D * | 2 ) edges. Addition of each edge corresponds to one iteration of the while loop at line 4 of Algorithm 1. Moreover, each iteration takes O(|D * |) time, because the loop at line 11 iterates over at most |D * | possible values for d 3 and the loops at lines 15 and 16 have constantly many iterations due to the bounded bandwidth assumption (Section 2.1). Since |D * | = O(|D|) and |E| = O(n), the total runtime of Algorithm 1 is O(|n| • |D| 3

Algorithm 2 :4

 2 Local Preprocessing in Step (5) 1 R local ← ∅; 2 foreach Ti do 3 computeLocalReachability(Ti); Function computeLocalReachability(T ) 5 Choose a leaf bag b l of T ; 6 bp ← parent of b l ;

  l and H -l form a separation of Ĝ with separator (V (b l ) ∩ V (b p )) × D * (Lemma 3) and (ii) all reachability information in H l is now replaced by direct edges (line 8). Hence, by induction hypothesis, line 11 finds all the local reachability edges for T -b l and adds them to both R local and Ĝ. Therefore, after line 11, for every u, v ∈ V (b l ), we have (u, d 1 ) (v, d 2 ) in H l iff (u, d 1 ) (v, d 2 ) in Ĝ. Hence, the final all-pairs reachability computation of lines 12-14 adds all the local edges in b l to R local . Complexity. Algorithm 2 performs at most two local all-pair reachability computations over the vertices appearing in each bag, i.e. O(t • |D * |) vertices. Each such computation can be performed in O(t 3 • |D * | 3 ) using standard reachability algorithms. Given that the T i 's have O(n) bags overall, the total runtime of Algorithm 2 is O

Fig. 7 :

 7 Fig. 7: Local Preprocessing (Step 5) on the graph and decomposition of Figure 6

3 :

 3 d 1 ) and (ii) u ∈ V (b) and v ∈ V (a j b ), i.e. v appears in the Algorithm Ancestors Preprocessing in Step (6) 1 foreach Ti = (Bi, ET i ) do 2 foreach b ∈ Bi in top-down order do 3 bp ← parent of b;

  We now show how to reduce the time complexity of Algorithm 3 from O(n • |D * | 3 • log n) to O(n • |D * | 3 ) using word tricks. The idea is to pack the F and F sets of Algorithm 3 into words, i.e. represent them by a binary sequence. Given a bag b, we define δ b as the sum of sizes of all ancestors of b. The tree decompositions are balanced, so b has O(log n) ancestors. Moreover, the width is t, hence δ b = O(t • log n) = O(log n) for every bag b. We perform a top-down pass of each tree decomposition T i and compute δ b for each b. For every bag b, u ∈ V (b) and d 1 ∈ D * , we store F (u, d 1 , b, -) as a binary sequence of length δ b •|D * |. The first |V (b)|•|D * | bits of this sequence correspond to F (u, d 1 , b, d b ). The next |V (b p )| • |D * | correspond to F (u, d 1 , b, d b -1)

.Theorem 1 .

 1 Answering a Pair Query. Our algorithm answers a pair query from a vertex (u, d 1 ) to a vertex (v, d 2 ) as follows:(i) If u and v are not in the same flow graph, return 0 (no). (ii) Otherwise, let G i be the flow graph containing both u and v. Let b u = rb(u) and b v = rb(v) be the root bags of u and v in T i and let b = lca(b u , b v ). (iii) If there exists a vertex w ∈ V (b) and d 3 ∈ D * such that (u, d 1 ) anc (w, d 3 ) and (w, d 3 ) anc (v, d 2 ), return 1 (yes), otherwise return 0 (no). Correctness. If there is a path P : (u, d 1 ) (v, d 2 ), then we claim P must pass through a vertex (w, d 3 ) with w ∈ V (b). If b = b u or b = b v , the claim is obviously true. Otherwise, consider the path P : b u b v in the tree decomposition T i . This path passes through b (by definition of b). Let e = {b, b } be an edge of P . Applying the cut property (Lemma 3) to e, proves that P must pass through a vertex (w, d 3 ) with w ∈ V (b ) ∩ V (b). Moreover, b is an ancestor of both b u and b v , hence we have (u, d 1 ) anc (w, d 3 ) and (w, d 3 ) anc (v, d 2 ). Complexity. Computing LCA takes O(1) time. Checking all possible vertices (w, d 3 ) takes O(t • |D * |) = O(|D|). This runtime can be decreased to O |D| log n by word tricks. Answering a Single-source Query. Consider a single-source query from a vertex (u, d 1 ) with u ∈ V i . We can answer this query by performing |V i | × |D * | pair queries, i.e. by performing one pair query from (u, d 1 ) to (v, d 2 ) for each v ∈ V i and d 2 ∈ D * . Since |D * | = O(|D|), the total complexity is O |V i | • |D| • |D| log n for answering a single-source query. Using a more involved preprocessing method, we can slightly improve this time to O |Vi|•|D| 2 log n See Appendices A.2-A.5 for more details. Based on the results above, we now present our main theorem: Given an IFDS instance I = (G, D, F, M, ∪), our algorithm preprocesses I in time O(n • |D| 3 ) and can then answer each pair query and singlesource query in time

1 .

 1 Given a pair query of the form (u, d 1 , v, d 2 ), let b u (resp. b v ) be the root bag u (resp. v), and b = lca(b u , b v ) the lowest common ancestor of b u and b v . We partition the set V (b) × D * into k subsets {A i } 1≤i≤k . Then, thread i handles the set A i , as follows: for every pair (w, d 3 ) ∈ A i , the thread sets the output to 1 (yes) iff (u, d 1 ) anc (w, d 3 ) and (w, d 3 ) anc (v, d 2 ). 2. Recall that a single source query (u, d 1 ) is answered by breaking it down to |V i | × |D * | pair queries, where G i is the flow graph containing u. Since all such pair queries are independent, we parallelize them among k threads, and further parallelize each pair query as described above. With word tricks, parallel pair and single-source queries require O |D| k•log n and O n•|D| k•log n time, respectively. Hence, for large enough k, each query requires only O(1) time, and we achieve perfect parallelism.

Fig. 8 :

 8 Fig.8: Preprocessing times of CPP and SEQ/PAR (over all instances). A dot above the 300s line denotes a timeout.

Fig. 9 :

 9 Fig. 9: Comparison of pair query time (top row) and single source query time (bottom row) of the algorithms. Each dot represents one of the 110 instances.Each row starts with a global picture (left) and zooms into smaller time units (right) to differentiate between the algorithms. The plots above contain results over all five analyses. However, our observations hold independently for every single analysis, as well (See Appendix A.7).

  d 2 ) = (v b , d b ) in line 5 of the algorithm, leads to (w, d ) being added to F (u, d).Complexity. Note that the tree decompositions T i are balanced. Hence, for each vertex w of G, there are at most O(t • log n) = O(log n) vertices whose root bag is an ancestor of the root bag of w. Therefore, the total size ofF (u, d)'s is O(n • log n • |D * | 2 )and the runtime of the algorithm is O(n • log n • |D * | 3 ). The runtime can be reduced to O(n • |D * | 3 ) using word tricks. See Appendix A.3 for more details. A.3 Word Tricks in Descendants Reachability Preprocessing In this section, we show how to reduce the time complexity of Step (7) of our preprocessing algorithm from O(n • log n • |D * | 3 ) to O(n • |D * | 3 ) by employing word tricks. A crucial observation is that we can have (v, d 2 ) ∈ F (u, d 1 ) only if the root bag of v is a descendant of the root bag of u. Let α u be the number of vertices v whose root bag is a descendant of the root bag of u. Then, F (u, d 1 ) has at most α u • |D * | vertices. Therefore, we can encode F (u, d 1 ) as a binary string of length α u • |D * |.

  (i) Let A be a subset of vertices in V i × D * . Initialize it with A = ∅. (ii) Let b u = rb(u) be the root bag of u. (iii) For every proper ancestor b of b u , consider all (w, d 2 ) ∈ V (b) × D * such that (u, d 1 ) anc (w, d 2 ). a. Add (w, d 2 ) to A. b. If b u is a descendant of the left (resp. right) child of b, find all vertices (v, d 3 ) such that rb(v) appears in the right (resp. left) subtree of b and (w, d 2 ) desc (v, d 3 ) and add them to A. (iv) Add every vertex (v, d 3 ) such that (u, d 1 ) desc (v, d 3 ) to A. (v) Return A.

d 3 )

 3 is added to A at step (iii).a. Otherwise, by Lemma 4, there exists a vertex (w, d 2 ) with w ∈ V (b), such that (u, d 1 ) (w, d 2 ) and (w, d 2 ) (v, d 3 ). By correctness of Steps (6) and (7), we have (u, d 1 ) anc (w, d 2 ) and (w, d 2 ) desc (v, d 3 ). Moreover, by definition of b we know that rb(u) and rb(v) appear in opposite subtrees of b. Hence, (v, d 3 ) is added to A at step (iii).b. Complexity. The runtime of the algorithm is dominated by step (iii).b. Consider a vertex (v, d 3 ). For every appearance of v in a bag b , the vertex (v, d 3 ) can be added to A at most t • |D * | times, i.e. at the vertices (w, d 2 ) such that w ∈ V (lca(b u , b )). Given that the tree decomposition has O(|V i |) bags and each bag has at most t = O(1) vertices, the overall runtime of this algorithm is O(|V i | • |D * | 2 ). The runtime can be reduced by a factor of W by applying word tricks. See Section A.5 for more details. A.5 Word Tricks in the Query Phase We now show how to exploit word tricks in the query phase. Word Tricks in Answering a Pair Query. Steps (i) and (ii) are performed in O(1). In Step (iii), a vertex (w, d 3 ) satisfies (u, d 1 ) anc (w, d 3 ) and (w, d 3 ) anc (v, d 2 ), if and only if (w, d 3 ) ∈ F (u, d 1 , b u , d b ) and also (w, d 3 ) ∈ F (v, d 2 , b v , d b ). Hence, to perform this step, it suffices to take the bitwise AND of the binary sequences corresponding to F (u, d 1 , b u , d b ) and F (v, d 2 , b v , d b ) and check whether the result is non-zero. Hence, this step can be done using O |D * | W bitwise operations. Word Tricks in Answering a Single-source Query. We store A as a binary sequence of length |V i | • |D * | with each bit corresponding to one vertex in V i × D * .

Figure 10 Fig. 10 :

 1010 Fig. 10: Comparison of pair query times.

Fig. 11 :

 11 Fig. 11: Comparison of single source query times.

  D, solves the on-demand same-context IFDS problem while spending (i) O(n • |D| 3 ) time in the preprocessing phase, and (ii) O( |D|/ log n ) time for a pair query and O(n • |D| 2 / log n) time for a single-source query in the query phase. Observe that when |D| = O(1), the preprocessing and query times are proportional to the size of the input and outputs, respectively, and are thus optimal § . In addition, our algorithm uses O(n • |D| 2

  yields O(n • |D| 3 ) preprocessing time and O(n • log n • |D| 2 ) space, and has pair and single-source query time O(|D|) and O(n • |D| 2

  Reduction to reachability. As explained in Section 2.1, computing MSCP is reduced to reachability via same-context valid paths in the exploded supergraph G. This reduction does not depend on the start vertex and initial data flow facts. Hence, for a data flow fact d ∈ D, we have d ∈ MSCP u,∆,v iff in the exploded supergraph G the vertex (v, d) is reachable via same-context valid paths from a vertex (u, δ) for some δ ∈ ∆ ∪ {0}. Hence, we define the following types of queries:Pair query. A pair query provides two vertices (u, d 1 ) and (v, d 2 ) of the exploded supergraph G and asks whether they are reachable by a same-context valid path.Hence, the answer to a pair query is a single bit. Intuitively, if d 2 = 0, then the query is simply asking if v is reachable from u by a same-context valid path in G. Otherwise, d 2 is a data flow fact and the query is asking whether d 2 ∈ MSCP u,{d1}∩D,v .

Single-source query. A single-source query provides a vertex (u, d 1 ) and asks for all vertices (v, d 2 ) that are reachable from (u, d 1 ) by a same-context valid path. Assuming that u is in the flow graph

  an interprocedural edge, i.e. a call-to-start or exit-to-return-site edge then

	8	continue;
	9	p ← the procedure s.t. u, v ∈ Vp;
	10	E ← E ∪ {e};
	11	foreach d3 s.t. ((sp, d3), (u, d1)) ∈ E do
	12

Table 1 :

 1 Benchmarks used in our experiments.

	Benchmark name	Procedures	|Vi|	|Ei| Width Reach Poss Simp Live Defs
	avalon-framework-4.2.0 154	2399 3192 4	11182 92462 91143 95250 98743
	bootstrap	29	835	1047 4	3764 102389 101961 103307 106350
	commons-daemon	29	511	594	4	2210 22664 22484 23179 24371
	commons-io-1.3.1	217	3704 4787 5	16982 175145 173185 179098 190591
	commons-logging-1.0.4 54	764	956	3	3440 33393 33012 34222 36903
	constantine	34	643	786	3	2858 51495 51211 52225 51877
	dacapo-digest	8	230	295	3	1050 11821 11689 12081 13393
	dacapo-h2	58	1568 2062 9	7260 140638 139749 142497 144188
	dacapo-luindex	3	48	57	4	210 2296 2276 2358 2392
	dacapo-lusearch	5	324	373	4	1394 44606 44389 44982 51308
	dacapo-lusearch-fix	5	324	373	4	1394 44606 44389 44982 51308
	dacapo-tomcat	19	258	327	3	1170 9452 9334 9761 9987
	dacapo-xalan	11	194	250	3	888 10184 10107 10398 10744
	daytrader	13	320	371	3	1382 18653 18504 19019 19067
	guava-r07	87	918	1105 3	4046 21131 20668 22127 21584
	jline-0.9.95-SNAPSHOT 209	3023 4194 5	14434 151121 149357 154368 160924
	jnr-posix	168	1934 2439 4	8746 57559 56383 59553 60767
	junit-3.8.1	453	5548 7769 4	26634 167815 164800 173844 174189
	tomcat-juli	46	797	975	4	3544 48862 48386 49759 51434
	xerces 2 5 0	310	2648 3392 4	12080 56779 55688 59501 63792
	xml-apis-ext	2	6	6	1	24	22	22	22	24
	xml-apis-ext-1.3.04	2	6	6	1	24	22	22	27	24

§ Note that we count the input itself as part of the space usage.

The research was partly supported by Austrian Science Fund (FWF) Grant No. NFN S11407-N23 (RiSE/SHiNE), FWF Schrödinger Grant No. J-4220, Vienna Science and Technology Fund (WWTF) Project ICT15-003, Facebook PhD Fellowship Program, IBM PhD Fellowship Program, and DOC Fellowship No. 24956 of the Austrian Academy of Sciences ( ÖAW). in the preprocessing phase. Our algorithms for the query phase are almost identical to our previous work.

A Appendix

A.1 Correctness and Complexity of Ancestors Preprocessing

In this section, we prove the correctness and establish the complexity of Algorithm 3, which is used for Ancestors Preprocessing as Step (6) of our approach.

We start with the following lemma, which is a consequence of the cut property:

, then for every 1 ≤ i ≤ k and every path P : u v in G, there exists a vertex

Intuitively, the lemma above means that if the vertex u appears in the bag b u and the vertex v in b v , then every path P from u to v in G goes through every bag (and the intersection of every two consecutive bags) of the path P from b u to b v in T .

Correctness. After the execution of

. We provide a proof for correctness of F , the case with F can be handled similarly. Assume that conditions (i) and (ii) hold and let P : (u, d

A.2 Descendants Reachability Preprocessing

To speed up our single-source queries, we add another step to the preprocessing algorithm. This section deals with the new step, which is called descendants reachability preprocessing. Section A.3 discusses word tricks to speed up this


Dahye Hwang

Sang Do Noh
email: sdnoh@skku.edu

3D Visualization System of Manufacturing Big Data and Simulation Results of Production for an Automotive Parts Supplier

Keywords: 3D Visualization, Lot Tracking, Manufacturing Information

Recently, many manufacturers have recalled their products owing to quality issues. It is increasingly difficult to determine the cause of quality issues because of the complexity of the supply chain. Thus, it is essential to share manufacturing information throughout the product life cycle. However, small and medium-sized enterprises (SMEs) often lack the necessary infrastructure and information systems. This research proposes an open-source system allowing the 3D visualization of production history and simulation results. The production history includes products' time stamps and inspection results, defect information, and a status of each facility. This information is then used to construct a product workflow and simulation model. Further, it is possible to compare simulation results for up to three alternative scenarios. The system is developed using open-source libraries for easy diffusion and application to SMEs in the automobile industry. A method for the implementation of this system to Korean auto parts companies is introduced.

Introduction

As the companies involved in the production cycle of products are diverse, identifying the cause of quality issues is often extremely challenging and time-consuming [START_REF] Kaynak | A replication and extension of quality management into the supply chain[END_REF] [START_REF] Venugopalan | Analysis of Decision Models in Supply Chain Management[END_REF].

A more thorough record and analysis of production cycle information could mediate this challenge [START_REF]Survey on the level of informatization of SMEs[END_REF]. However, many small and medium-sized manufacturing companies have difficulty systematically organizing information generated during parts manufacturing due to a lack of appropriate information infrastructure [START_REF] Bala | Supply Chain Management: Some Issues and Challenges -A Review[END_REF] [START_REF] Ghobakhloo | Strategies for Successful Information Technology Adoption in Small and Medium-sized Enterprises[END_REF].

Additionally, as the fourth industrial revolution develops, the number of research efforts to digitize factories increases. However, most of this research surrounds realtime data exchange for virtual reality factory implementation or Cyber Physical System realization [6][7][8]. This study proposes an open-source 3D visualization system to cope with quality problems after shipment. If a quality problem occurs within the quality assurance period after its sale to customer, it is difficult to find the cause by simply checking production history of product. The purpose of this study is to provide users with an intuitive view of quality problem by visualizing production history data. The system presents process status and material flow of the product claimed after its delivery. It also allows users to simulate a production model with their inputs by using production history as the base information and returning simulation results in 3D.

3D Visualization of Production History and Simulation Results

The architecture of a 3D visualization system of production history and simulation results is shown in Fig 1 . It consists of a user application, a production history tracking system, a 3D visualization system with a simulation engine, and four databases. The user application manages the input and output of the system. A serial number with the "Product/Lot" information is used to track an item's production history. Production line code is used to load a layout and location data of facilities. Simulation settings include the total simulation time, warm-up time, process cycle time, loading/unloading time, buffer capacity, and defect rate. Finally, the user application outputs a 3D visualization of past production flow and simulation results.

A production history tracking system consists of two management modules: one for the process-facility library and one for the production history. While the process-facility library management module handles adding, editing, and deleting 3D models and the basic information for processes and facilities, the production history management module searches past production information of 'Product/Lot' using its serial number and configures a neutral file to represent the scenario. A 3D visualization system is composed of a simulation engine and three management modules for (1) rerun scenario/simulation, (2) 3D model control, and (3) data visualization. The rerun scenario/simulation model management module creates, saves, and cuts rerun scenarios or simulation models. Each scenario includes up to three simulation models and is created based on a neutral file generated from the production history tracking system. Rerun scenario contains real production history and visualization data, such as capacity, defect rate, process sequence, process-facility codes, and layout, to represent line status when the selected product was being produced. On the other hand, simulation model contains process time and buffer capacity in addition to the rerun scenario's visualization data. The 3D model control module accelerates or decelerates the speed of 3D objects in the presented animation. The data visualization module refines raw simulation data and shows the result in graphs and tables.

The four databases used in this system are (1) the process-facility library, (2) the manufacturing information database, (3) the process design database and (4) the rerun scenario database. Of these, the manufacturing information database and process design database are part of a legacy system, for example, MES. The process-facility library is a 3D model library consisting of a standard process-facility and a customized processfacility. A standard process-facility library provides a basic pre-modelled 3D model commonly used in the target industry, and a customized process-facility library containing user applied process-facility 3D models.

Implementation

In this study, a standard process-facility library was developed by selecting commonly used facilities found by visiting all the production lines of the target company. As a result, 23 types of facilities frequently used in the electric component manufacturing line were selected and modeled in 3D using Trimble's SketchUp Pro 2018.

To evaluate the performance of the developed 3D visualization system, authors requested software testing from the Korea Testing Laboratory. The evaluation measures the time required to run a single 3D process facility model and then divides the time by the size of the model file to calculate the speed (sec/MB). Table 1 summarizes the system environment for the performance evaluation. Seventeen models were selected at random from the process-facility library to measure the speed. Sizes of the model files used for the evaluation are between 1.00 MB and 1.6 MB. The loading speed of the model had a maximum of 0.768 sec/MB, a minimum of 0.692 sec/MB, and an average of 0.735 sec/MB. Additionally, the difference between the fastest loading time and the slowest loading time was very small, 0.076 sec, which suggests that the model loading speed is more affected by the loading preprocessing than by the model file size.

Visualization of a large amount of production history information with 3D animation makes it easier to identify the problematic process and the results of the inspection process than when viewing such information in the existing text-based documents. In particular, when confirming the production history information of each lot, it became easy to specify information on various layers such as time, process, and product as shown in Fig. 2. Facility which has defect history or is selected by user highlight in red or blue.

Fig. 2. Example of production history visualization

As a result of the simulation, the number of defects per hour, the number of defects per facility per hour, the utilization of each process, and the buffer utilization over time can be efficiently viewed and considered as seen in Fig. 3. Simulation results are available to show in 3D animation as production history visualization.

Conclusion

This research has developed an open-source based 3D visualization system of production history and simulation results for SMEs. Through this system, the production environment of specified product or lot can be represented in 3D. In this manner, users can better visualize supply chain occurrences and errors through analyzed data rather than through extensive text document-based data. For example, users who want to check a production line or process status at a specific production point can view the necessary information on a single screen without a separate query search or document comparison. To evaluate current production live productivity, a comparison of present production lines and hypothetical alternatives is possible through simulations that utilize adjustable settings.

Applications to the other production lines and improvement of the simulation engine's performance are required as a future works of the research.

Fig. 1 .

 1 Fig. 1. An Architecture of 3D visualization system

Fig. 3 .

 3 Fig. 3. Examples of simulation results

Table 1 .

 1 Tools/Software used in system development

	Item	Tool/Software
	OS	Windows 10 Pro 64 bit
	CPU	Intel Core i7-7700 CPU 3.60 GHz
	RAM	16 GB
	HDD	500 GB
	Programming Languages	C#
	Open-source Library	MonoGame

Acknowledgement

This work was supported by the Development of the Reconfigurable Manufacturing Core Technology based on the Flexible Assembly and ICT Converged Smart Systems grant of MOTIE/KEIT (10052972)