Call graph correction using control flow constraints

Simple item page
dc.contributor.advisorMcKinley, Kathryn S.en
dc.creatorLee, Byeongcheolen
dc.date.accessioned2015-08-26T20:47:25Zen
dc.date.available2015-08-26T20:47:25Zen
dc.date.issued2006-05en
dc.description.abstractDynamic optimizers for object-oriented languages collect a variety of profile data to drive optimization decisions. In particular, the dynamic call graph (DCG) informs key structural optimizations such as which methods to optimize and how to optimize them. Unfortunately, current low-overhead call-stack hardware and software sampling methods are subject to sampling bias, which loses accuracy of 40 to 50% when compared with a perfect call graph. This paper introduces DCG correction, a novel approach that uses static and dynamic control-flow graphs (CFGs) to improve DCG accuracy. We introduce the static frequency dominator (FDOM) relation, which extends the dominator relation on the CFG to capture relative execution frequencies and expose static constraints on DCG edges, which we use to correct DCG edge frequencies. Using conservation of flow principles, we further show how to use dynamic CFG basic block profiles to correct DCG edge frequencies intraprocedurally and interprocedurally. We implement and evaluate DCG correction in Jikes RVM on the SPEC JVM98 and DaCapo benchmarks. Default DCG sampling attains an average accuracy of 52-59% compared with perfect, whereas FDOM correction improves average accuracy to 64-68%, while adding 0.2% average overhead. The dynamic correction raises accuracy to 85% on average, while adding 1.2% average overhead. We then provide dynamically corrected DCGs to the inliner with mixed results -1% average degradations and improvements across a variety of configurations. However, prior work shows that increased DCG accuracy in production VMs has benefits. We believe that high-accuracy DCGs will become more important in the future as the complexity and modularity of object-oriented programs increases.en
dc.description.departmentComputer Sciencesen
dc.format.mediumelectronicen
dc.identifier.urihttp://hdl.handle.net/2152/30457en
dc.language.isoengen
dc.relation.ispartofUT Electronic Theses and Dissertationsen
dc.rightsCopyright © is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works.en
dc.rights.restrictionRestricteden
dc.subjectDynamic optimizersen
dc.subjectObject-oriented languagesen
dc.subjectComputer programmingen
dc.titleCall graph correction using control flow constraintsen
dc.typeThesisen
dc.type.genreThesisen
thesis.degree.departmentComputer Sciencesen
thesis.degree.disciplineComputer Sciencesen
thesis.degree.grantorThe University of Texas at Austinen
thesis.degree.levelMastersen
thesis.degree.nameMaster of Artsen

Access full-text files

Original bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
txu-oclc-70869252.pdf
Size:
427.88 KB
Format:
Adobe Portable Document Format
Description:
Access restricted to UT Austin EID holders
Download

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.66 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

UT Electronic Theses and Dissertations