Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.
About 2,368 papers for “Pointer analysis”
Michael Hind · 2001
During the past twenty-one years, over seventy-five papers and nine Ph.D. theses have been published on pointer analysis. Given the tomes of work on this topic one may wonder, “Haven'trdquo; we solved this problem yet?'' With input from many researchers in the field, this paper describes issues related to pointer analysis and remaining open problems.
Cited by 580
Smaragdakis, Yannis, Balatsouras, George · CERN Document Server (European Organization for Nuclear Research) · 2015
This monograph introduces and surveys the most common modern approaches to pointer analysis, with an emphasis on distilling the essence of common analysis algorithms. With an eye towards ease of exposition and concreteness, the presentation aspires to be rather more tutorial and hands-on than other surveys of the pointer analysis area.
Cited by 0
Yannis Smaragdakis, George Balatsouras · Foundations and Trends® in Programming Languages · 2015
Pointer analysis is a fundamental static program analysis, with a rich literature and wide applications. The goal of pointer analysis is to compute an approximation of the set of program objects that a pointer variable or expression can refer to. We present an introduction and survey of pointer analysis techniques, with an emphasis on distilling the essence of common analysis algorithms. To this end, we focus on a declarative presentation of a common core of pointer analyses: algorithms are modeled as configurable, yet easy-to-follow, logical specifications. The specifications serve as a starting point for a broader discussion of the literature, as independent threads spun from the declarative model.
Cited by 181Open access
Susan Horwitz And · 2008
this paper, we explore techniques for modular pointer analysis: analyzing small pieces of the program (e.g., individual functions or files), then combining the results of the individual analyses. We expect our modular approach to have two important benefits: ffl It will permit algorithms like Andersen's to be applied to much larger programs than would otherwise be possible, thus permitting reasonably precise analysis of at least medium-sized programs
Cited by 0
Jianwen Zhu · Digest of technical papers/Digest of technical papers - IEEE/ACM International Conference on Computer-Aided Design · 2002
One of the bottlenecks in the recent movement of hardware synthesis from behavioral C programs is the difficulty in reasoning about runtime pointer values at compile time. The pointer analysis problem has been investigated in the compiler community for two decades, which has yielded efficient, polynomial time algorithms for context-insensitive analysis. However, at the accuracy level for which hardware synthesis is desired, namely context and flow sensitive analysis, the time and space complexity of the best algorithms reported grow exponentially with program size. In this paper, we present our first step towards a new analysis technology which potentially leads to almost-linear time complexity and sub-linear space complexity algorithm even for the most accurate analysis. The key idea that contributes to this efficiency is to implicitly encode the pointer-to relation in the Boolean domain, thereby capturing the procedure transfer function completely, compactly and canonically. This represents a wide departure from the traditional techniques, all of which explicitly capture pointer-to relation using variations of point-to graph, which have to be re-evaluated for different calling contexts. Experiments for our first flow-insensitive algorithm on common benchmarks show promising result.
Cited by 40
Horwitz, Susan, Shapiro, Marc · Minds at UW (University of Wisconsin) · 2012
Cited by 0Open access
Suan Hsi Yong, Susan Horwitz · Lecture notes in computer science · 2004
Cited by 25
Yu Yang, Greg Szubzda, Xiaofang Chen et al. · 2011
�Affected 50 million people �Had $6 billion cost �Causes? The alarm system was stalled due to a concurrency bug! This part will not be traversed if backtrack naively! dependent visited state Naïve backtracking does not work!
Cited by 0
Anonymous · Figshare · 2023
SVF Pointer Analysis Issues
Cited by 0Open access
Anonymous · Figshare · 2023
SVF Pointer Analysis Issues
Cited by 0Open access
Ben Hardekopf, Calvin Lin · Lecture notes in computer science · 2007
Cited by 50
Anonymous · Figshare · 2023
SVF Pointer Analysis Issues
Cited by 0Open access
Vishwanath Raman · 2004
Pointer analysis has been studied for over two decades. It answers the following question – For variables of pointer types, what are the set of objects they may point to at runtime. The analysis is also called Points-to analysis. Pointer analysis is used in a variety of applications, including live variable
Cited by 0
Vishwanath Raman Computer, Vishwanath Raman · 2004
Cited by 0
Michael Burke, Paul R. Carini, Jong-Deok Choi et al. · 1997
Cited by 0
Marcio Buss, Daniel Brand, et al. · 2008
We propose a new abstraction for pointer analysis that represents reads and writes to memory instead of traditional points-to relations. Compared to points-to graphs, our Assign-Fetch Graph (AFG) leads to concise procedure summaries that can be used in any calling context. Also, its flexibility supports new analysis techniques with different trade-offs between speed and precision. For efficiency, we build a summary for each procedure that assumes distinct pointers from the environment are not aliased and restore soundness when the summary is used in a context with aliases. We present two pointer analysis techniques based on our AFG. The first takes the flow-insensitive view adopted by many authors; the second considers statement ordering. In addition to being more precise, we find that this “flow-aware” analysis runs faster. We conclude with experimental results showing it is practical.
Cited by 0
Silvian Calman · TSpace · 2005
Pointer analysis is a critical problem in optimizing compiler, parallelizing compiler, software engineering and most recently, hardware synthesis. While recent efforts have suggested the symbolic method, which uses Bryant's Binary Decision Diagram as an alternative to capture the point-to relation, no speed advantage has been demonstrated for context-insensitive analysis, and results for context-sensitive analysis are only preliminary. We refine the concept of symbolic transfer function proposed earlier and establish a common framework for both context-insensitive and context-sensitive pointer analysis. With this framework, the transfer function of a procedure can abstract away the impact of its callers and callees, and represent its point-to information completely, compactly and canonically. In addition, we propose a symbolic representation of the invocation graph, which can otherwise be exponentially large. In contrast to the classical frameworks where context-sensitive point-to information of a procedure has to be obtained by the application of its transfer function exponentially many times, our method can obtain point-to information of all contexts in a single application. Our experimental evaluation on a wide range of C benchmarks indicates that our context-sensitive pointer analysis can be made almost as fast as its context-insensitive counterpart.
Cited by 0Open access
Γεώργιος Καστρίνης · 2020
Η στατική ανάλυση στοχεύει στον αυτόματο συμπερασμό ιδιοτήτων που κάποιο πρόγραμμα μπορεί να επιδείξει σε κάθε πιθανή εκτέλεση, χωρίς στην πράξη να εκτελείται. Η στατική ανάλυση δεικτών αποτελεί μια μεγάλη υποκατηγορία της που επικεντρώνεται στα δυναμικά αντικείμενα που δύνανται να ‘δείξουν’ οι εκφράσεις ενός προγράμματος σε κάποια εκτέλεση του. Η εξέλιξη των γλωσσών προγραμματισμού με την πάροδο των χρόνων οδήγησε στην προσθήκη πολλών επιπέδων αφαίρεσης, τα οποία σαν αποτέλεσμα έχουν ο αυτόματος συμπερασμός για κάποιο πρόγραμμα να αποτελεί τουλάχιστον μία πρόκληση αν όχι και μία αδύνατη προσπάθεια. Συνεπώς, κάθε πρακτικός αλγόριθμος στατικής ανάλυσης πρέπει να στοχεύσει σε μια εκτίμηση των πραγματικών αποτελεσμάτων με κάποια μορφή ανακρίβειας—είτε υπολογίζοντας περισσότερα είτε λιγότερα. Σε αυτή τη διατριβή παρουσιάζουμε πώς μπορούμε να σχεδιάσουμε ακριβείς και συνάμα αποδοτικούς αλγορίθμους ανάλυσης δεικτών εφαρμόζοντας διαφορετικές πολιτικές σε διαφορετικά σημεία του προγράμματος. Συμπληρωματικά, δεδομένου ότι ένας αλγόριθμος ανάλυσης δεικτών με βεβαιώσεις εγκυρότητας για όλα τα σημεία του προγράμματος καθώς και πρακτικά αποτελέσματα δεν αποτελεί ρεαλιστική κατεύθυνση, δείχνουμε πώς μπορούμε να σχεδιάσουμε αναλύσεις με ισχυρές βεβαιώσεις εγκυρότητας για συγκεκριμένα κομμάτια ενός προγράμματος. Προηγούμενοι αλγόριθμοι για ανάλυση δεικτών εισήγαγαν την έννοια των συμφραζομένων (context) για να αντιμετωπίσουν το αυξανόμενο πρόβλημα της ανακρίβειας έναντι της αποδοτικότητας. Τα συμφραζόμενα χρησιμοποιούνται για να επαυξήσουν στοιχεία της ανάλυσης ώστε η ανάλυση να καταφέρει να είναι πιο ακριβής χωρίς ταυτόχρονα να πρέπει να κάνει θυσίες στον τομέα της αποδοτικότητας. Παρουσιάζουμε επωφελείς τρόπους συνδυασμού διάφορων ειδών συμφραζομένων σε διαφορετικά σημεία του προγράμματος, χωρίς αυτοί οι συνδυασμοί να επιφέρουν το κόστος που θα παρουσίαζε μία αφελής προσέγγιση. Μία δεύτερη απόπειρα για δημιουργία αναλύσεων που παρουσιάζουν υψηλή ακρίβεια και αποδοτικότητα μας οδηγεί σε μια ανάλυση ενδοσκόπησης (introspection). Εφαρμόζουμε ένα σύνηθες μοτίβο στο οποίο μια φτηνή ανακριβής ανάλυση εφαρμόζεται πρώτη ώστε να συλλέξει διάφορες μετρικές για το πρόγραμμα, και στη συνέχεια μια δεύτερη πιο ακριβής (και ακριβή) ανάλυση μπορεί να εφαρμοστεί μόνο σε συγκεκριμένα σημεία του προγράμματος—υπό την υπόθεση ότι η πιο ακριβής μεταχείριση των υπολοίπων θα είχε μόνο αρνητικά αποτελέσματα στην συνολική απόδοση. Εν συνεχεία, μετατοπίζουμε την προσοχή μας προς μια ανάλυση που υπό-εκτιμά τα αποτελέσματα της (σε αντίθεση με το σύνηθες των αναλύσεων που υπολογίζουν μία υπέρ εκτίμηση). Με αυτή την αντιμετώπιση, η ανάλυση μας αναφέρει λιγότερα αποτελέσματα αλλά μπορεί να παρέχει ισχυρές βεβαιώσεις ότι αυτά θα ισχύουν πάντα. Βασιζόμενοι πάνω σε παρατηρήσεις για τις ιδιότητες που παρουσιάζουν αναλύσεις αυτού του είδους, εφαρμόζουμε μια ειδική δομή δεδομένων η οποία επιφέρει επιταχύνσεις στον αλγόριθμο μας σχεδόν κατά δύο τάξεις μεγέθους. Τέλος, στην τέταρτη συνεισφορά της διατριβής, επιστρέφουμε ξανά στην οικογένεια αναλύσεων που υπερεκτιμούν τα αποτελέσματα τους. Ο στόχος μας είναι η δημιουργία ενός αρκετά αποδοτικού αλγορίθμου που όντως παράγει έγκυρα αποτελέσματα χωρίς περιορισμούς στο υποκείμενο πρόγραμμα. Κατά συνέπεια, αυτό μας οδηγεί σε μία συντηρητική ανάλυση, που μπορεί να παρέχει βεβαιώσεις εγκυρότητας ακόμα και υπό την παρουσία άγνωστου κώδικα, αλλά ταυτόχρονα αποφεύγει την σπατάλη υπολογισμών σε δεδομένα που αργότερα θα χρειαστεί να ανατραπούν για την διατήρηση των βεβαιώσεων αυτών.
Cited by 0Open access
Lu, John Meng-Yang · Rice Digital Scholarship Archive (Rice University) · 2009
Many powerful code optimization techniques rely on accurate information connecting the definitions and uses of values in a program. This information is difficult to produce for programs written with pointer-based languages such as C. For values in memory locations, accurate information is difficult to obtain at call sites and pointer-based memory operations. Most compilers conservatively assume that call sites and pointer-based operations may access any memory location. This greatly weakens the effectiveness of many optimizations and leaves opportunities for improvement.\nThis dissertation examines how to implement an interprocedural pointer analyzer for C in order to provide more accurate information about which memory locations call sites and pointer-based memory operations may access. The key issues of pointer analysis versus alias analysis, modeling of call sites, modeling of the heap, and usage of interprocedural path information are discussed. Solutions given for the first two questions and various solutions for the last two questions were used to build pointer analyzers of varying power and complexity. All versions of the analyzer were tested over a suite of programs, and we demonstrate that pointer analysis for programs of about 30K lines can easily be done with the computational power of current machines. The resulting pointer-analyzed programs were tested, and we show that their performance is better than non-analyzed programs. The data for each analyzers' performance and each analyzed programs' performance was used to look at the trade-offs among analysis time, analysis accuracy, and performance of the analyzed code. These results were also compared with interprocedural MOD/REF analysis. We also show that the analyzer can speed up the execution times of the rest our optimizer.\nA new optimization, register promotion, that was specifically designed to use the information generated by pointer analysis was also developed. Register promotion moves a variable that normally resides in memory to a register for portions of the code in which it is safe to do so. Our experimental results for register promotion show that it is effective in reducing memory traffic.
Cited by 0Open access
Susan Horwitz, Phil Pfeiffer, Thomas Reps · ACM SIGPLAN Notices · 1989
Our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. We are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as Lisp and Pascal. We have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependencies of a program written in such a language. Our algorithms account for destructive updates to fields of a structure and thus are not limited to the cases where all structures are trees or acyclic graphs; they are applicable to programs that build cyclic structures. Our technique extends an analysis method described by Jones and Muchnick that determines an approximation to the actual layouts of memory that can arise at each program point during execution. We extend the domain used in their abstract interpretation so that the (abstract) memory locations are labeled by the program points that set their contents. Data dependencies are then determined from these memory layouts according to the component labels found along the access paths that must be traversed during execution to evaluate the program's statements and predicates. For structured programming constructs, the technique can be extended to distinguish between loop-carried and loop-independent dependencies, as well as to determine lower bounds on minimum distances for loop-carried dependencies.
Cited by 58Open access