No description available.

Den här magisteruppsatsen presenterar en metod för points-to analys som är avsedd för aktiviteter inom mjukvaruutveckling. Applikationer för mjukvaruutveckling som använder resultatet från en points-to analys är oftast intresserad av en liten del av det program som analyseras. För att göra metoden mer effektiv presenteras också ett antal approximationer som kommer att reducera storleken på analysen. En implementation av metoden och approximationerna gjordes för att kunna utvärdera metoden och approximationerna. Resultatet visar att approximationerna som gjordes på analysen inte påverkar precisionen avsevärt. Resultatet visar också att tiden för att göra en analys kortas ner mycket genom att göra approximationer på analysen. / This master’s thesis is presenting an approach to points-to analysis that is targeted to software engineering activities. Software engineering applications that use the result of points-to analysis are often only interested of a small amount of the classes in an application. In order to make the analysis more efficient, a couple of approximations are presented that will reduce the size of the analysis scope. An implementation was constructed to evaluate the approach and the approximations. The experimental result shows that the approximations made on the analysis are in the most cases not affecting the precision at all for the relevant parts of the application being analyzed. The experimental results also show that the analysis time is shortened considerable by using approximations.

Both major open-source compilers, GCC and LLVM, have a mature link-time optimization framework usable on most current programs. They are however not free from many performance issues, which prevent them to perform certain analyses and optimizations. We analyze bottlenecks and identify multiple places for improvement, focusing on improving interprocedural points-to analysis. For this purpose, we design a new data structure derived from Bloom filters and use it to significantly improve performance and memory consumption of link-time optimization. Powered by TCPDF (www.tcpdf.org)

Points-to analysis is a static program analysis that tries to predict the dynamic behavior of programs without running them. It computes reference information by approximating for each pointer in the program a set of possible objects to which it could point to at runtime. In order to justify new analysis techniques, they need to be compared to the state of the art regarding their accuracy and efficiency. One of the main parameters influencing precision in points-to analysis is context-sensitivity that provides the analysis of each method separately for different contexts it was called on. The problem raised due to providing such a property to points-to analysis is decreasing of analysis scalability along with increasing memory consumption used during analysis process. The goal of this thesis is to present a comparison of precision and scalability of context-sensitive and context-insensitive analysis using three different points-to analysis techniques (Spark, Paddle, P2SSA) produced by two research groups. This comparison provides basic trade-offs regarding scalability on the one hand and efficiency and accuracy on the other. This work was intended to involve previous research work in this field consequently to investigate and implement several specific metrics covering each type of analysis regardless context-sensitivity – Spark, Paddle and P2SSA. These three approaches for points-to analysis demonstrate the intended achievements of different research groups. Common output format enables to choose the most efficient type of analysis for particular purpose.

A program slice consists of a subset of the statements of a program that can potentially affect values computed at some point of interest. Such a point of interest along with a set of variables is called a slicing criterion. Slicing tools are useful for several applications, such as program understanding, testing, program integration, and so forth. Slicing object oriented programs has some special problems that need to be addressed due to features like inheritance, polymorphism and dynamic binding. Alias analysis is important for precision of slices. In this thesis we implement a slicing tool for sequential Java programs in the Soot framework. Soot is a front-end for Java developed at McGill University and it provides several forms of intermediate code. We have integrated the slicer into the framework. We also propose an improved technique for intraprocedural points-to analysis. We have implemented this technique and compare the results of the analysis with those for a flow-insensitive scheme in Soot. Performance results of the slicer are reported for several benchmarks.

Les analyses statiques ont pour but de déterminer les propriétés des programmes au moment de la compilation. Contrairement aux analyses dynamiques, le comportement exact du programme ne peut être connu. Par conséquent, on a recours à des approximations pour remédier à ce manque d'information. Malgré ces approximations, les analyses statiques permettent des optimisations et des transformations efficaces pour améliorer les performances des programmes. Parmi les premières analyses du processus d'optimisation figure l'analyse des pointeurs. Son but est d'analyser statiquement un programme en entrée et de fournir en résultat une approximation des emplacements mémoire vers lesquels pointent ses variables pointeurs. Cette analyse est considérée comme l'une des analyses de programmes les plus délicates et l'information qu'elle apporte est très précieuse pour un grand nombre d'autres analyses clientes. En effet, son résultat est nécessaire à d'autres optimisations, comme la propagation de constante, l'élimination du code inutile, le renommage des scalaires ainsi que la parallélisation automatique des programmes. L'analyse des pointeurs est très nécessaire pour l'exploitation du parallélisme présent dans les applications scientifiques écrites en C. Ceci est dû au fait que les tableaux, très présents dans ce type d'applications, sont accédés via les pointeurs. Il devient nécessaire d'analyser les dépendances entre les éléments de tableau dans le but de paralléliser les boucles. Le langage C présente beaucoup de difficultés lors de son analyse par la liberté qu'il offre aux utilisateurs pour gérer et manipuler la mémoire par le biais des pointeurs. Ces difficultés apparaissent par exemple lors de l'accès aux tableaux par pointeurs, l'allocation dynamique (via «malloc») ainsi que les structures de données récursives. L'un des objectifs principaux de cette thèse est de déterminer les emplacements mémoire vers lesquels les pointeurs pointent. Ceci se fait en assurant plusieurs dimensions comme : - la sensibilité au flot de contrôle, c'est-à-dire la mise à jour des informations d'un point programme à un autre ; - la non-sensibilité au contexte, c'est-à-dire l'utilisation de résumés au lieu de l'analyse du corps de la fonction à chaque appel ; - la modélisation des champs pointeurs des structures de données agrégées, dans laquelle chaque champ représente un emplacement mémoire distinct. D'autres aspects sont pris en compte lors de l'analyse des programmes écrits en C comme la précision des emplacements mémoire alloués au niveau du tas, l'arithmétique sur pointeurs ou encore les pointeurs vers tableaux. Notre travail permet l'amélioration des résultats des analyses clientes et en particulier il permet la parallélisation des boucles lorsqu'on accède aux éléments de tableaux via les pointeurs, la détection de code inutile ou le calcul du graphe de dépendances. Il est implémenté dans le compilateur parallélliseur PIPS (Parallélisation Interprocédurale de Programmes Scientifiques) et permet d'analyser, en particulier, les applications scientifiques de traitement du signal tout en assurant une analyse intraprocédurale précise et une analyse interprocédurale efficace via les résumés. / Static analysis algorithms strive to extract the information necessary for the understanding and optimization of programs at compile time. The potential values of the variables of type pointer are the most difficult information to determine. This information is often used to assess if two pointers are potential aliases, i.e. if they can point to the same memory area. An analysis of pointers, also called points-to analysis, may provide more precision to other analyses such as constant propagation, analysis of dependencies or analysis of live variables. The analysis of pointers is very important for the exploitation of parallelism in scientific C programs since the most important structures they manipulate are arrays, which are typically accessed by pointers. It is necessary to analyse the dependencies between arrays in order to exploit the parallelism between loops. C language is very hard to analyse since it allows to users to manipulate the memory through pointers. These difficulties arise for example when accessing arrays by pointers, dynamic allocation (via "malloc") and recursive data structures. Points-to analysis may also attempt to handle recursive data structures and other structures that are accessed by pointers. This work provides a points-to analysis which is : - flow-sensitive, by taking into account the order of execution of instructions ; - field-sensitive, since structure fields are treated as individual locations ; - context-insensitive, because functions summaries are computed to avoid re-analyzing functions bodies. Other issues such as heap modeling, pointer arithmetics and pointers to arrays are also taken into account while analyzing C programs. Our intraprocedural analysis provides precise results to client analyses, in particular it allows parallelization when accessing the array elements loops via pointers, detecting useless code or computing the dependency graph. while our interprocedural one allows to propagate them efficiently. Our work is implemented within the PIPS (Parallélisation Interprocédurale de Programmes Scientifiques) parallelizer, a framework designed to analyze, optimize and parallelize scientific and signal processing applications. Keywords : static analysis, points-to analysis, flow-sensitive, context-insensitive, field-sensitive.

Pointer analysis is one of the key static analyses during compilation. The efficiency of several compiler optimizations and transformations depends directly on the scalability and precision of the underlying pointer analysis. Recent advances still lack an efficient and scalable context-sensitive inclusion-based pointer analysis. In this work, we propose four novel techniques to improve the scalability of context-sensitive points-to analysis for C/C++ programs. First, we develop an efficient way of storing the approximate points-to information using a multi-dimensional bloom filter (multibloom). By making use of fast hash functions and exploiting the spatial locality of the points-to information, our multibloom-based points-to analysis offers significant savings in both analysis time and memory requirement. Since the representation never resets any bit in the multibloom, no points-to information is ever lost; and the analysis is sound, though approximate. This allows a client to trade off a minimal amount of precision but gain huge savings(two orders less) in memory requirement. By making use of multiple random and independent hash functions, the algorithm also achieves high precision and runs, on an average,2×faster than Andersen’s points-to analysis. Using Mod/Ref analysis as a client, we illustrate that the precision is above 98% of that of Andersen’s analysis. Second, we devise a sound randomized algorithm that processes a group of constraints in a less precise but efficient manner and the remaining constraints in a more precise manner. By randomly choosing different groups of constraints across different runs, the analysis results in different points-to information, each of which is guaranteed to be sound. By joining the results of a few runs, the analysis obtains an approximation that is very close to the one obtained by the more precise analysis and still proves efficient in terms of the analysis time. We instantiate our technique to develop a randomized context-sensitive points-to analysis. By varying the level of randomization, a client of points-to analysis can trade off minimal precision (less than 5%) for large gain in efficiency(over 50% reduction in analysis time). We also develop an adaptive version of the randomized algorithm that carefully varies the randomization across different runs to achieve maximum benefit in terms of analysis time and precision without pre-setting the randomization percentage and the number of runs. Third, we transform the points-to analysis problem into finding a solution to a system of linear equations. By making novel use of prime factorization, we illustrate how to transform complex points-to constraints into a set of linear equations and transform the solution back as a points-to solution. We prove that our algorithm is sound and show that our technique is 1.8×faster than Andersen’s analysis for large benchmarks. Finally, we observe that the order in which points-to constraints are processed plays a vital role in the algorithm efficiency. We prove that finding an optimal ordering to compute the fixpoint solution is NP-Hard. We then propose a greedy heuristic based on the amount of points-to information computed by a constraint to prioritize the constraints. This results in a dynamic ordering of the constraint evaluation which, in turn, results in skewed evaluation of constraints where each constraint is evaluated repeatedly and different number of times in a single iteration. Our prioritized analysis achieves, on an average, an improvement of 33% over Andersen’s points-to analysis. We illustrate that our algorithms help in scaling the state-of-the-art pointer analyses. We also believe that the techniques developed would be useful for other program analyses and transformations.

Languages such as C use pointers very heavily. Implementation of operations on dynamically linked structures is, however, quite difficult. This can cause the programmer to make more mistakes than usual. One method for dealing with this situation is to use the static analysis tools. This thesis elaborates on the extension to the Code Listener architecture which is an interface for building static analysis tools. Code Listener is able to construct a call-graph or a control flow graph for a given source code and send it to the analyzing tool. One ability of the architecture is that it can conduct the live variable analysis internally. It detects places in the control flow graph where some subset of variables may be killed. The problem was that every variable for which a pointer address was assigned could not been killed, before. This decision had been made because there was no assurance that the variable could never been used through the pointer. So the goal of this work was to design and incorporate a points-to analysis which is able to exclude some references from the set of considered pointers to improve the live variable analysis.