NDLI: A practical and fast iterative algorithm for φ-function computation using DJ graphs

Content Provider	ACM Digital Library
Author	Ramakrishna, U. Das, Dibyendu
Copyright Year	2005
Abstract	We present a new and practical method of computing φ-function for all variables in a function for Static Single Assignment (SSA) form. The new algorithm is based on computing the $\textbf{Merge}$ set of each node in the control flow graph of a function (a node here represents a basic block and the terms will be used interchangeably). Merge set of a node $\textit{n}$ is the set of nodes $\textit{N},$ where φ-functions may need to be placed if variables are defined in $\textit{n}.$ It is not necessary for $\textit{n}$ to have a definition of a variable in it. Thus, the merge set of $\textit{n}$ is dictated by the underlying structure of the CFG. The new method presented here precomputes the merge set of every node in the CFG using an iterative approach. Later, these merge sets are used to carry out the actual φ-function placement. The advantages are in examples where $\textit{dense}$ definitions of variables are present (i.e., original definitions of variables---user defined or otherwise, in a majority of basic blocks). Our experience with SSA in the High Level Optimizer (optimization levels +O3/+O4) shows that most examples from the Spec2000 benchmark suite require a high percentage of basic blocks to have their φ points computed. Previous methods of computing the same relied on the dominance frontier $(\textit{DF})$ concept, first introduced by Cytron et al. The method presented in this paper gives a new effective iterative solution to the problem. Also, in cases, where the control flow graph does not change, our method does not require any additional computation for new definitions introduced as part of optimizations. We present implementation details with results from Spec2000 benchmarks. Our algorithm runs faster than the existing methods used.
Starting Page	426
Ending Page	440
Page Count	15
File Format	PDF
ISSN	01640925
e-ISSN	15584593
DOI	10.1145/1065887.1065890
Volume Number	27
Issue Number	3
Journal	ACM Transactions on Programming Languages and Systems (TOPLAS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	DJ Graph Dominance Frontier 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

Efficiently computing Φ-nodes on-the-fly

The Static Single Assignment Form and its Computation (1998)

Efficiently computing static single assignment form and the control dependence graph (1991)

Static Single Assignment Form for Explicitly Parallel Programs: Theory and Practice (1994)

Efficiently computing static single assignment form and the control dependence graph (1991)

Single-pass generation of static single-assignment form for structured languages

Incremental computation of dominator trees

A Multi-variable Algorithm for Placing Phi-nodes

Using static single assignment form in a code optimizer

A practical and fast iterative algorithm for φ-function computation using DJ graphs

Similar Documents

Efficiently computing Φ-nodes on-the-fly

The Static Single Assignment Form and its Computation (1998)

Efficiently computing static single assignment form and the control dependence graph (1991)

Static Single Assignment Form for Explicitly Parallel Programs: Theory and Practice (1994)

Efficiently computing static single assignment form and the control dependence graph (1991)

Single-pass generation of static single-assignment form for structured languages

Incremental computation of dominator trees

A Multi-variable Algorithm for Placing Phi-nodes

Using static single assignment form in a code optimizer

A practical and fast iterative algorithm for φ-function computation using DJ graphs