Record Details

STRENGTH REDUCTION OF LARGE EXPRESSIONS

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title STRENGTH REDUCTION OF LARGE EXPRESSIONS
 
Creator DHANESHWAR, VM
DHAMDHERE, DM
 
Subject global program optimization
algorithm
transformation
code optimization
strength reduction
dead code elimination
large expressions
data flow analysis
decomposition of data flows
fixed point
 
Description Strength reduction of a large expression cannot be performed as a second-order effect of optimizing its subexpression(s). The ideas of composite hoisting and strength reduction are used to develop an algorithm for the strength reduction of a large expression (SRLE) as a single entity using the framework for partial redundancy elimination. SRLE subsumes the conventional optimizations of code hoisting, common subexpression elimination, loop invariant movement and strength reduction, thereby performing comprehensive optimization of a program. It performs partial-redundancy elimination as effectively as other recent algorithms, and also eliminates several suboptimalities of previously published work in partial-redundancy-based strength reduction. The SRLE algorithm involves use of nonsingular bidirectional data flows, giving rise to interesting issues concerning the desired fixed point of the data flows. A solution method based on the principle of decomposition of bidirectional data flows into a sequence of unidirectional data flows is shown to achieve the desired fixed point of the bidirectional data flows more elegantly than earlier methods. Experimental results as well as proof of correctness of the algorithm are included.
 
Publisher CHAPMAN HALL LTD
 
Date 2011-07-20T06:18:51Z
2011-12-26T12:51:20Z
2011-12-27T05:37:56Z
2011-07-20T06:18:51Z
2011-12-26T12:51:20Z
2011-12-27T05:37:56Z
1995
 
Type Article
 
Identifier JOURNAL OF PROGRAMMING LANGUAGES, 3(2), 95-120
0963-9306
http://dspace.library.iitb.ac.in/xmlui/handle/10054/5378
http://hdl.handle.net/10054/5378
 
Language en