Paper Info
Title
Toward efficient flow-sensitive induction variable analysis and dependence testing for loop optimization
Abstract
This paper presents a new approach to improve flow-sensitive induction variable analysis and data dependence testing on intermediate program representations, such as control-flow graphs with low-level operations representations in single static assignment forms. Current compiler techniques have difficulties optimizing loops that exhibit irregular control flow patterns. The inaccuracy of loop analysis results in conservative estimations of array-based data dependences in loops, which negatively affects the speedup of the loop via parallelization and vectorization. Our approach is based on a novel CR# (CR-sharp) algebra that effectively represents the value progressions of (conditionally) updated variables in loops. The CR# forms of induction variables are constructed with a new flow-sensitive induction variable recognition algorithm. We also developed a new CR#-based nonlinear data dependence test that enables loops to be more effectively optimized.
Year
DOI
Venue
2006
10.1145/1185448.1185450
ACM Southeast Regional Conference 2005
Keywords
Field
DocType
new cr,data dependence testing,loop analysis result,flow-sensitive induction variable analysis,novel cr,array-based data dependence,nonlinear data dependence test,new approach,loop optimization,induction variable,flow-sensitive induction variable recognition,negative affect,control flow graph,control flow
Loop fusion,Loop dependence analysis,Computer science,Loop fission,Loop splitting,Loop optimization,Algorithm,Induction variable,Theoretical computer science,Loop tiling,Loop interchange
Conference
ISBN
Citations 
PageRank 
1-59593-315-8
4
0.40
References 
Authors
11
4
Name
Order
Citations
PageRank
Yixin Shou151.12
Robert A. van Engelen257364.68
Johnnie Birch351.12
Kyle Gallivan4889154.22