DOC PREVIEW
Dynamic Points To Sets

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Dynamic Points-To Sets: A Comparison with Static Analyses and PotentialApplications in Program Understanding and OptimizationMarkus Mock*, Manuvir Das+, Craig Chambers*, and Susan J. Eggers**Department of Computer Science and EngineeringUniversity of WashingtonBox 352350, Seattle WA 98195-2350{mock, chambers, eggers}@cs.washington.edu+Microsoft ResearchRedmond, WA [email protected] CSE Technical Report 01-03-01Microsoft Research Technical Report MSR-TR-2001-38March 20012AbstractIn this paper, we compare the behavior of pointersin C programs, as approximated by static pointeranalysis algorithms, with the actual behavior of pointerswhen these programs are run. In order to perform thiscomparison, we have implemented several well knownpointer analysis algorithms, and we have built aninstrumentation infrastructure for tracking pointervalues during program execution. Our experiments show that for a number ofprograms from the Spec95 and Spec2000 benchmarksuites, the pointer information produced by staticpointer analyses is far worse than the actual behaviorobserved at run-time. These results have twoimplications: First, a tool like ours can be used tosupplement static program understanding tools insituations where the static pointer information is toocoarse to be usable. Second, a feedback-directedcompiler can use profile data on pointer values toimprove program performance, by ignoring aliases thatdo not arise at run time (and inserting appropriate run-time checks to ensure safety). For example, we wereable to obtain a factor of 6 speedup on a frequentlyexecuted routine from m88ksim.1. IntroductionMany programming languages in use today, such asC, allow the use of pointers. Pointers are usedextensively in C programs to simulate call-by-referencesemantics in procedure calls, to emulate object-orienteddispatch via function pointers, to avoid the expensivecopying of large objects, to implement list, tree, or othercomplex data structures, and as references to objectsallocated dynamically on the heap. While pointers are auseful and powerful feature, they also make programshard to understand, and often prevent an optimizingcompiler from making code-improving transformations.In an attempt to compensate for these negativeeffects, many pointer analysis algorithms have beendevised over the past decade[1,3,4,6,7,10,11,16,18,19,20]. These algorithms try togive a conservative approximation of the possible setsof variables, data structures, or functions a particularpointer could point to at a specific program point; theseare referred to as points-to sets. These sets can be used,for instance, by an optimizing compiler to determinethat two expressions might be aliased, i.e., refer to thesame object. Several classes of pointer analysis algorithms havebeen designed. While flow- and context-sensitivealgorithms potentially produce more precise results,they generally do not scale well. In addition, recentwork [5,9] suggests that for typical C programs (e.g.SPEC benchmarks) Das’s fast and highly scalablealgorithm produces results as good as those of a context-sensitive algorithm. However, even its points-to sets areoften still on the order of tens or even hundreds ofobjects. Clearly, such points-to sets are too large to bevery useful in a program understanding tool, where theuser might like to know what objects a pointer storemight modify.Instead of designing yet another pointer analysisalgorithm, we wanted to find out how well the staticallycomputed points-to set agree with actual programbehavior, i.e., how many different objects are referencedat a particular pointer dereference compared to thenumber of objects in the points-to set computed by astate-of-the-art pointer analysis algorithm. Dynamicpoints-to sets may tell us how close actual algorithmsare to the theoretical optimum1, and they can also beused to improve program understanding tools, andenable dynamic optimizations that take aliasrelationships into account.For example, instead of presenting the user withhundreds of potential candidate targets of a pointerdereference *p, the program understanding tool coulduse the dynamically observed targets of *p and presentthose to the user; in addition, when the static anddynamic sets agree, it could also inform the user that thestatic information is in fact optimal and not just aconservative approximation. Moreover, in somesituations the potentially unsound dynamic sets aremore useful for program understanding than optimalpoints-to sets: if the user is interested in what a pointerpointed to in a particular program run, for instance whendebugging a program, it is actually more useful to1Since the dynamic points-to set sizes may be distinct fordifferent inputs, they are potentially unsound and could besmaller than the optimal sound solution, which in general isnot computable, since pointer-analysis has been shown to beundecidable [15]. For programs exercising a large fraction oftheir execution paths, such as the SPEC benchmarks,however, we expect the dynamic sets to be not much smallerthan an optimal solution.Dynamic Points-To Sets: A Comparison with Static Analyses and Potential Applications in Program Understanding and OptimizationMarkus Mock*, Manuvir Das+, Craig Chambers*, and Susan J. Eggers**Department of Computer Science and EngineeringUniversity of WashingtonBox 352350, Seattle WA 98195-2350{mock, chambers, eggers}@cs.washington.edu+Microsoft ResearchRedmond, WA [email protected] only the dynamically observed targets ratherthan all potential targets for all possible executions asan optimal (undecidable) static analysis would.To obtain dynamic points-to information in thisstudy, we used a slightly modified version of the Calpainstrumentation tool [13] to observe the dynamicpoints-to sets of a set of programs taken from theSPEC95 and SPEC2000 benchmark suites. The staticaverage points-to set sizes ranged from 1.0 to 21.2 forthe best of the scalable static pointer analysis algorithmwe used, while the dynamic points-to set sizes were onaverage (geometric mean) a factor of 3.3 smaller.Additionally, for the large majority (over 98%) ofdereferences the dynamic points-to sets were actuallysingletons. This means that in 98% of the time a toolsimilar to ours integrated into a program understandingtool, would be able to exactly tell the user the target of adereference, a much higher fraction than what ispossible with static analysis alone (41% ofdereferences) demonstrating the


Dynamic Points To Sets

Download Dynamic Points To Sets
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Dynamic Points To Sets and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Dynamic Points To Sets 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?