https://www.mdu.se/

Software-intensive systems in most domains, from autonomous vehicles to health, are becoming predominantly parallel to efficiently manage large amount of data in short (even real-) time. There is an incredibly rich literature on languages for parallel computing, thus it is difficult for researchers and practitioners, even experienced in this very field, to get a grasp on them. With this work we provide a comprehensive, structured, and detailed snapshot of documented research on those languages to identify trends, technical characteristics, open challenges, and research directions. In this article, we report on planning, execution, and results of our systematic peer-reviewed as well as grey literature review, which aimed at providing such a snapshot by analysing 225 studies.

Control dependency (CD) and Static Single Assignment (SSA) form are the basis of many program analyses, transformation, and optimization techniques, and these are implemented and used by modern compilers such as GCC and LLVM. Most state-of-the-art algorithms approximate these computations by using postdominator relations and dominance frontiers (DF) respectively for efficiency reasons which have been used for over three decades. Dominator-based SSA transformation and control dependencies exhibit a non-dual relationship. Recently, it has been shown that DF-based SSA computation is grossly imprecise, and Weak and Strong Control Closure (WCC and SCC) have wider applicability in capturing control dependencies than postdominator-based CD computation. Our main contribution in this article is the proof of duality between the generation of f functions and the computation of weakly deciding (WD) vertices which are the most computationally expensive part of SSA program construction and WCC/SCC computation respectively. We have provided a duality theorem and its constructive proof by means of an algorithm that can compute both thef functions and the WD vertices seamlessly. We have used this algorithm to compute SSA programs and WCC, and performed experiments on real-world industrial benchmarks. The practical efficiency of our algorithm is (i) almost equal to the best state-of-the-art algorithm in computing WCC, and (ii) closer to (but not as efficient as) the DF-based algorithms in computing SSA programs. Moreover, our algorithm achieves the ultimate precision in computing WCC and SSA programs with respect to the inputs of these algorithms and obtains wider applicability in the WCC computation (handling nonterminating programs).

In recent years, maintaining test code quality has gained more attention due to increased automation and the growing focus on issues caused during this process. Test code may become long and complex, but maintaining its quality is mostly a manual process, that may not scale in big software projects. Moreover, bugs in test code may give a false impression about the correctness or performance of the production code. Static program analysis (SPA) tools are being used to maintain the quality of software projects nowadays. However, these tools are either not used to analyse test code, or any analysis results on the test code are suppressed. This is especially true since SPA tools are not tailored to generate precise warnings on test code. This paper investigates the use of SPA on test code by employing three state-of-the-art general-purpose static analysers on a curated set of projects used in the industry and a random sample of relatively popular and large open-source C/C++ projects. We have found a number of built-in code checking modules that can detect quality issues in the test code. However, these checkers need some tailoring to obtain relevant results. We observed design choices in test frameworks that raise noisy warnings in analysers and propose a set of augmentations to the checkers or the analysis framework to obtain precise warnings from static analysers.

Control dependency is a fundamental concept in many program analyses, transformation, parallelization, and compiler optimization techniques. An overwhelming number of definitions of control dependency relations are found in the literature that capture various kinds of program control flow structures. Weak and strong control closure (WCC and SCC) relations capture nontermination insensitive and sensitive control dependencies and subsume all previously defined control dependency relations. In this paper, we have shown that static dependency-based program slicing requires the repeated computation of WCC and SCC. The state-of-the-art WCC and SCC algorithm provided by Danicic et al. has the cubic and the quartic worst-case complexity in terms of the size of the control flow graph and is a major obstacle to be used in static program slicing. We have provided a simple yet efficient method to compute the minimal WCC and SCC which has the quadratic and cubic worst-case complexity and proved the correctness of our algorithms. We implemented ours and the state-of-the-art algorithms in the Clang/LLVM compiler framework and run experiments on a number of SPEC CPU 2017 benchmarks. Our WCC method performs a maximum of 23.8 times and on average 10.6 times faster than the state-of-the-art method to compute WCC. The performance curves of our WCC algorithm for practical applications are closer to the NlogN curve in the microsecond scale. Our SCC method performs a maximum of 226.86 times and on average 67.66 times faster than the state-of-the-art method to compute SCC. Evidently, we improve the practical performance of WCC and SCC computation by an order of magnitude. 

Control dependence is a fundamental concept used in many program analysis techniques such as program slicing, program debugging, program parallelization, and detecting security leaks. Since the introduction of this concept in the late eighties, numerous definitions of control dependencies and their computation methods have been developed. The later definitions are progressively more generalized covering a wide spectrum of modern programming language constructs. The most generalized concepts are the weak and strong control closure (WCC and SCC) that capture the nontermination (in)sensitive control dependencies of a given program. In this paper, we have developed a novel method to compute WCC incrementally. Any client application of WCC such as program slicing requires computing the WCC repeatedly in a fixpoint computation. An incremental algorithm to compute WCC will improve the performance of the client application significantly. We have provided the proof of correctness and the theoretical worst-case complexity of our algorithm. We have performed an experimental evaluation on well-known benchmarks, and our experiments reveal that we have significantly improved the practical efficiency in computing WCC incrementally. We have obtained an average speedup of 31.03 in all benchmarks and a maximum speedup of 35.29 than the best state-of-the-art algorithm computing WCC.

Many program analysis techniques depend on capturing the control dependencies of the program. Most existing control dependence algorithms either compute intraprocedural control dependencies only, or they compute control dependence relations that are not precise in general including nonterminating systems. Weak control closure (WCC) subsumes all known nontermination insensitive control dependence relations, including those that are appropriate for nonterminating systems. In this paper, we provide the first formal development of an algorithm to compute the WCC for interprocedural programs capturing the weak form of interprocedural control dependencies. The method is widely applicable due to the generality of WCC. Theorems on the theoretical results of soundness, precision, and the worst-case complexity of our method are also included. We have compared our algorithm with a WCC computation algorithm based on a state-of-The-Art interprocedural control dependence computation algorithm. The latter algorithm loses soundness, and we improve the precision by 15.21% on all our experimental benchmarks. This empirical evidence suggests that our algorithm is more effective for any client application of WCC requiring interprocedural program analysis.

Existing proofs of correctness for dependence-based slicing methods are limited either to the slicing of intraprocedural programs [2, 39], or the proof is only applicable to a specific slicing method [4, 41]. We contribute a general proof of correctness for dependence-based slicing methods such as Weiser [50, 51], or Binkley et al. [7, 8], for interprocedural, possibly nonterminating programs. The proof uses well-formed weak and strong control closure relations, which are the interprocedural extensions of the generalised weak/strong control closure provided by Danicic et al. [13], capturing various nonterminating-insensitive and nontermination-sensitive control-dependence relations that have been proposed in the literature. Thus, our proof framework is valid for a whole range of existing control-dependence relations. We have provided a definition of semantically correct (SC) slice. We prove that SC slices agree with Weiser slicing, that deterministic SC slices preserve termination, and that nondeterministic SC slices preserve the nondeterministic behavior of the original programs.

The Static Single Assignment (SSA) form is an intermediate representation used for the analysis and optimization of programs in modern compilers. The ϕ-function placement is the most computationally expensive part of converting any program into its SSA form. The most widely-used ϕ-function placement algorithms are based on computing dominance frontiers (DF). However, this kind of algorithms works under the limiting assumption that all variables are defined at the beginning of the program, which is not the case for local variables. In this paper, we introduce an innovative ϕ-placement algorithm based on computing reaching definitions (RD), which generates a precise number of ϕ-functions. We provided theorems and proofs showing the correctness and the theoretical computational complexity of our algorithms. We implemented our approach and a well-known DF-based algorithm in the Clang/LLVM compiler framework, and performed experiments on a number of benchmarks. The results show that the limiting assumption of the DF-based algorithm when compared with the more accurate results of our RD-based approach leads to generating up to 87% (69% on average) superfluous ϕ-functions on all benchmarks, and thus brings about a significant precision loss. Moreover, even though our approach computes more information to generate precise results, it is able to analyze up to 92.96% procedures (65.63% on average) of all benchmarks with execution time within twice the execution time of the reference DF-based approach. © 2020 Elsevier Inc.

Control dependency is a fundamental concept in many program analyses, transformation, parallelization, and compiler optimization techniques. An overwhelming number of definitions of control dependency relations are found in the literature that capture various kinds of program control flow structures. Weak and strong control closure (WCC and SCC) relations capture nontermination insensitive and sensitive control dependencies and subsume all previously defined control dependency relations. In this paper, we have shown that static dependency-based program slicing requires the repeated computation of WCC and SCC. The state-of-the-art WCC algorithm provided by Danicic et al. has the cubic worst-case complexity in terms of the size of the control flow graph and is a major obstacle to be used in static program slicing. We have provided a simple yet efficient method to compute the minimal WCC which has the quadratic worst-case complexity and proved the correctness of our algorithms. We implemented ours and the state-of-the-art algorithms in the Clang/LLVM compiler framework and run experiments on a number of SPEC CPU 2017 benchmarks. Our method performs a maximum of 23.8 times and on average 11.1 times faster than the state-of-the-art method. The performance curves of our WCC algorithm for practical applications are closer to the NlogN curve in the microsecond scale. Evidently, we improve the practical performance of WCC computation by an order of magnitude.

The Static Single Assignment (SSA) form is an intermediate representation used for the analysis and optimization of programs in modern compilers. The φ-function placement is the most computationally expensive part of converting any program into its SSA form. The most widely-used φ-function placement algorithms are based on computing dominance frontiers. However, this kind of algorithms works under the limiting assumption that all variables are defined at the beginning of the program, which is not the case for local variables. In this paper, we introduce an innovative algorithm based on computing reaching definitions, only assuming that global variables and formal parameters are defined at the beginning of the program. We implemented our algorithm and compared it to a well-known dominance frontiers-based algorithm in the Clang/LLVM compiler framework by performing experiments on a benchmarking suite for Perl. The results of our experiments show that, besides a few computationally expensive cases, our algorithm is fairly efficient, and most notably it produces up to 169% and on an average 74% fewer φ-functions than the reference dominance frontiers-based algorithm.