Thumbnail
Access Restriction
Subscribed

Author Graham, Susan L. ♦ Wegman, Mark
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Common subexpression elimination ♦ Code optimization ♦ Reducibility ♦ Depth-first search ♦ Live-dead analysis ♦ Path compression ♦ Flow graph ♦ Information propagation ♦ Global flow analysis ♦ Go-to-less programming ♦ Data flow
Abstract ible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of e edges, the algorithm has a worst case time bound of O(e log e) function operations. It is also shown that in programming terms, the number of operations is proportional to e plus the number of exits from program loops. Consequently a restriction to one-entry one-exit control structures guarantees linearity. The algorithm can be extended to yet larger classes of function spaces and graphs by relaxing the time bound. Examples are given of code improvement problems which can be solved using the algorithm.
Description Affiliation: Univ. of California, Berkeley, Berkeley (Graham, Susan L.; Wegman, Mark)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 18
Issue Number 12
Page Count 1
Starting Page 716
Ending Page 716


Open content in new tab

   Open content in new tab
Source: ACM Digital Library