NDLI: Partial redundancy elimination in SSA form

Content Provider	ACM Digital Library
Author	Liu, Shin-Ming Kennedy, Robert Chan, Sun Tu, Peng Chow, Fred Lo, Raymond
Copyright Year	1999
Abstract	The SSAPRE algorithm for performing partial redundancy elimination based entirely on SSA form is presented. The algorithm is formulated based on a new conceptual framework, the factored redundancy graph, for analyzing redundancy, and representes the first sparse approach to the classical problem and on methods for its solution. With the algorithm description, theorems and their proofs are given showing that the algorithm produces the best possible code by the criteria of computational optimality and lifetime optimality of the introduced temporaries. In addition to the base algorithm, a practical implementation of SSAPRE that exhibits additional compile-time efficiencies is described. In closing, measurement statistics are provided that characterize the instances of the partial redundancy problem from a set of benchmark programs and compare optimization time spent by an implementation of SSAPRE aganist a classical partial redundancy elimination implementation. The data lend insight into the nature of partial redundancy elimination and demonstrate the expediency of this new approach.
Starting Page	627
Ending Page	676
Page Count	50
File Format	PDF
ISSN	01640925
e-ISSN	15584593
DOI	10.1145/319301.319348
Volume Number	21
Issue Number	3
Journal	ACM Transactions on Programming Languages and Systems (TOPLAS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Code motion Common subexpressions Data flow analysis Partial redundancy Static single assignment form
Content Type	Text
Resource Type	Article
Subject	Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A New Algorithm for Partial Redundancy Elimination based on SSA Form (1997)

Partial dead code elimination

An SSA-based algorithm for optimal speculative code motion under an execution profile

An SSA-based algorithm for optimal speculative code motion under an execution profile

A GENERALIZED METHOD FOR REALIZING PARTIAL REDUNDANCY ELIMINATION FOR NORMAL FORMS IN STATIC SINGLE ASSIGNMENT FORMS

Partial dead code elimination

Optimizing for space and time usage with speculative partial redundancy elimination

A new algorithm for partial redundancy elimination based on SSA form (1997)

Partial Redundancy Elimination in SSA Form (1999)

Partial redundancy elimination in SSA form

Similar Documents

A New Algorithm for Partial Redundancy Elimination based on SSA Form (1997)

Partial dead code elimination

An SSA-based algorithm for optimal speculative code motion under an execution profile

An SSA-based algorithm for optimal speculative code motion under an execution profile

A GENERALIZED METHOD FOR REALIZING PARTIAL REDUNDANCY ELIMINATION FOR NORMAL FORMS IN STATIC SINGLE ASSIGNMENT FORMS

Partial dead code elimination

Optimizing for space and time usage with speculative partial redundancy elimination

A new algorithm for partial redundancy elimination based on SSA form (1997)

Partial Redundancy Elimination in SSA Form (1999)

Partial redundancy elimination in SSA form