The Road Not Taken: Estimating Path Execution Frequency Statically

被引：19

作者：

Buse, Raymond P. L. ^{[1
]}

Weimer, Westley ^{[1
]}

机构：

[1] Univ Virginia, Charlottesville, VA 22903 USA

来源：

2009 31ST INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, PROCEEDINGS | 2009年

关键词：

SYNTHETIC WORKLOAD GENERATION;

D O I：

10.1109/ICSE.2009.5070516

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A variety of compilers, static analyses, and testing frameworks rely heavily on path frequency information. Uses for such information range from optimizing transformations to bug finding. Path frequencies art, typically obtained through profiling, but that approach is severely restricted: it requires running programs in an indicative environment, and on indicative test inputs. We present a descriptive statistical model of path frequency based on features that can be readily obtained from a program's source code. Our model is over 90% accurate with respect to several benchmarks, and is sufficient for selecting the 5% of paths that account for over half of a prograim's total runtime. We demonstrate our technique's robustness by measuring its performance as a static branch predictor finding it to be more accurate than. previous approaches on average. Finally, our qualitative analysis of the model provides insight into which source-level features indicate "hot paths."

引用

页码：144 / 154

页数：11

共 33 条

[11]

Boyer Michael, 2008, WORKSH SOFTW TOOLS M

[12] Evidence-based static branch prediction using machine learning [J].

Calder, B ;

Grunwald, D ;

Jones, M ;

Lindsay, D ;

Martin, J ;

Mozer, M ;

Zorn, B .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1997, 19 (01) :188-222

[13]

CHEN TY, 2004, INT C QUAL SOFTW, P146

[14] Software profiling for hot path prediction: Less is more [J].

Duesterwald, E ;

Bala, V .

ACM SIGPLAN NOTICES, 2000, 35 (11) :202-211

[15]

EMOND EJ, 2002, J MULTICRITERIA DECI, P17

[16]

Goldsmith Simon F., 2007, P 6 JOINT M EUR SOFT, P395, DOI DOI 10.1145/1287624.1287681

[17]

Graham SL, 2004, ACM SIGPLAN NOTICES, V39, P49, DOI 10.1145/989393.989401

[18]

Gupta R, 2003, COMPILER DESIGN HANDBOOK, P143

[19]

HOLMES G, 1994, AUSTR NZ C INT INF S

[20]

Kremenek T, 2003, LECT NOTES COMPUT SC, V2694, P295

← 1 2 3 4 →