Gated Single Assignment [Was: Online explanation of Dijkstra's Guarded Command Language]
Tommy thorn <tommyatnumba-tu.com--not@yahoo.com> 14 jun 2004 17:46:58 -0400.
- LOGIN & Help
Efficient building and placing of gating functions
- Computer Science
Research output : Chapter in Book/Report/Conference proceeding › Conference contribution
In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at @-nodes. The gating functions specify the control dependence for each reaching definition at a @-node. We introduce a new concept of gating path, which is a path in the control flow graph from the immediate dominator u of a node o to v, such that every node in the path is dominated by w Previous algorithms start with #-function placement, and then traverse the control flow graph to compute the gating functions. By formulating the problem into gating path construction, we are able to identify not only a node, but also a gating path expression which defines a gating function for the φ-node.
Publication series
Asjc scopus subject areas, online availability.
- 10.1145/207110.207115
Library availability
Related links.
- Link to publication in Scopus
- Link to the citations in Scopus
Fingerprint
- Control-Flow Graph Computer Science 100%
- Nodes Engineering 100%
- Efficient Building Engineering 100%
- Linear Time Mathematics 100%
- Dominator Mathematics 100%
- Control Dependence Computer Science 50%
- Reaching Definition Computer Science 50%
- Path Expression Computer Science 50%
T1 - Efficient building and placing of gating functions
AU - Tu, Peng
AU - Padua, David
N1 - Publisher Copyright: © 1995 ACM.
PY - 1995/6/18
Y1 - 1995/6/18
N2 - In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at @-nodes. The gating functions specify the control dependence for each reaching definition at a @-node. We introduce a new concept of gating path, which is a path in the control flow graph from the immediate dominator u of a node o to v, such that every node in the path is dominated by w Previous algorithms start with #-function placement, and then traverse the control flow graph to compute the gating functions. By formulating the problem into gating path construction, we are able to identify not only a node, but also a gating path expression which defines a gating function for the φ-node.
AB - In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at @-nodes. The gating functions specify the control dependence for each reaching definition at a @-node. We introduce a new concept of gating path, which is a path in the control flow graph from the immediate dominator u of a node o to v, such that every node in the path is dominated by w Previous algorithms start with #-function placement, and then traverse the control flow graph to compute the gating functions. By formulating the problem into gating path construction, we are able to identify not only a node, but also a gating path expression which defines a gating function for the φ-node.
UR - http://www.scopus.com/inward/record.url?scp=1542295479&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=1542295479&partnerID=8YFLogxK
U2 - 10.1145/207110.207115
DO - 10.1145/207110.207115
M3 - Conference contribution
AN - SCOPUS:1542295479
T3 - Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
BT - Proceedings of the ACM SIGPLAN 1995 Conference on Programming language Design and Implementation, PLDI 1995
PB - Association for Computing Machinery
T2 - 1995 ACM SIGPLAN Conference on Programming language Design and Implementation, PLDI 1995
Y2 - 18 June 1995 through 21 June 1995
A new algorithm for building the GSA-form
- Part II. Invited Lectures and Contributed Lectures
- 2. Parallel Software Technologies
- Published: December 1996
- Volume 1 , pages 403–409, ( 1996 )
Cite this article
- Sung-Soon Park 1 ,
- Seong-Uk Choi 2 &
- Myong-Soon Park 2
20 Accesses
Explore all metrics
Gated Single Assignment (GSA) form is used to transform an imperative program into a form suitable for dataflow interpretation. We describe a GSA-formed Control Flow Graph (CFG) that contains gating functions and the information of switches. We also present an algorithm to transform an imperative program into a GSA-formed CFG. Transformation of an imperative program into a GSA-formed CFG provides the basis for generating dataflow graphs(DFG).
By using GSA-formed CFG, we can transform an imperative program into a DFG more simply comparing with previous methods, and show an expectation of use with demand- and control-driven model. As we create an intermediate form which has essential information for translation, it will be used to do transformations for various kinds of dataflow models.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Similar content being viewed by others
Automatic Synthesis of Data-Flow Analyzers
Generalized Program Sketching by Abstract Interpretation and Logical Abduction
Streamlining Control Flow Graph Construction with DCFlow
A.V. Aho et al., Compilers Principles. Techniques and Tools. Addison Wesley. 1986.
Z.M. Ariola et al., Compilation of Id: A Subset of Id, CSG Memo 315. MIT. Jul. 1990.
R.A. Ballance et al., The Program Dependence Web A Representation Supporting Control-. Data-. and Demand-Driven Interpretation of Imperative Languages. Proc. of the ACM SIGPLAN, ACM. New York. pp. 257–271, Jun. 1990.
M. Beck et al., From Control Flow to Dataflow. Journal of Parallel and Distributed Computing. Vol. 12, pp. 118–129. 1991.
Article MathSciNet Google Scholar
P.L. Campbell et al., Refining and Defining the Program Dependence Web. Technical Report No. 93-6. The University of New Mexico. Feb. 1993.
R. Cytron et al., Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM TOPLAS. Vol. 13, No. 4, ACM. New York. pp. 451–490. Oct. 1991.
Google Scholar
J.B. Dennis. Dataflow supercomputers. Computers. Vol. 13. No. 11, pp. 48–56, Nov. 1980.
Article Google Scholar
J. Ferrante et al., The Program Dependence Graph and Its Use in Optimization. ACM TOPLAS. Vol. 9, No. 3. pp. 319–349, Jul. 1987.
Article MATH MathSciNet Google Scholar
D.J. Hwang et al., Exploiting Spatial And Temporal Parallelism In the Multithreaded Node Architecture Implemented on Superscalr RISC processors. Proc. of the 1993 ICPP, Vol. 1, pp. 51–54, Aug. 1993.
Kai Hwang. Advanced Computer Architecture, McGRAW-HILL. 1993.
K.J. Ottenstein et al., Gated Single Assignment Form: Dataflow Interpretation for Imperative Languages. Tech. rep., Los Alamos National Laboratory. Oct. 30. 1989.
M.S. Park et al., Construction of SSA and Elimination of Redundant Switch in DFG Transformation using Control Dependence. Proc. of ICS. Taichung. Taiwan. pp. 1049–1056. Dec. 13–15. 1992.
G. Papadopoulos, Implementation of a general purpose dataflow multiprocessor. Ph.D thesis. Massachusetts Institute of Technology. 1988.
E.H. Rho et al., Compilation of A Functional Language For the Multithreaded Architecture: DAVRID. Proc. of the 1994 ICPP, Vol. 2. pp. 39–242. Aug. 1994.
V. Sarkar. PTRAN—The IBM Parallel Translation System. Research Report RC 16194 (70566) IBM Research Division. T.J. Watson Research Center. Yorktown Heights. NY. 1990.
K.R. Traub. A Compiler for the MIT Tagged Token Dataflow Architecture. Master Thesis. MIT press. Aug. 1986.
Download references
Author information
Authors and affiliations.
Dept. of Computer Science, Anyang University, 430-714, Kyungki-Do, Korea
Sung-Soon Park
Dept. of Computer Science, Korea University, 136-701, Seoul, Korea
Seong-Uk Choi & Myong-Soon Park
You can also search for this author in PubMed Google Scholar
Rights and permissions
Reprints and permissions
About this article
Park, SS., Choi, SU. & Park, MS. A new algorithm for building the GSA-form. Wuhan Univ. J. of Nat. Sci. 1 , 403–409 (1996). https://doi.org/10.1007/BF02900861
Download citation
Issue Date : December 1996
DOI : https://doi.org/10.1007/BF02900861
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Intermediate Form
- Program Graph
- Dataflow Graph
- Imperative Program
- Imperative Language
- Find a journal
- Publish with us
- Track your research
IMAGES
VIDEO
COMMENTS
The Gated Static Single Assignment (GSA) form was proposed by Ottenstein et al. in 1990, as an intermediate representation for implementing advanced static analyses and optimisation passes in compilers. Compared to SSA, GSA records additional data dependencies and provides more context, making optimisations more effective and allowing one to ...
Computer Science. 1996. TLDR. A technique that exploits the single assignment property of GSA to perform demand-driven symbolic analysis using the use-def chains embedded in the variable names and a technique that can obtain more precise results from the predicated possible values using path conditions are introduced. Expand.
The Gated Static Single Assignment (GSA) form was pro-posed by Ottenstein et al. in 1990, as an intermediate rep-resentation for implementing advanced static analyses and optimisation passes in compilers. Compared to SSA, GSA records additional data dependencies and provides more con-
Gated Static Single Assignment Yann Herklotz1 Delphine Demange 2Sandrine Blazy CPP'23, 16th January 1 Imperial College London 2 IRISA, Inria, CNRS, Univ de Rennes 1. Overview 1 Refresher on SSA 2 Translation from SSA to GSA 3 Proof of SSA to GSA Translation 4 Summary 2. Refresher on SSA.
Gated single assignment (gated SSA, GSA) mentioned below provides an interpretable (data- or demand-driven) IR that uses this concept. Psi-SSA ( ψ -SSA) also mentioned below is a very similar IR but more appropriate to code generation for architectures with predication.
The first step towards this goal is the translation of the GCC intermediate representation into the Gated Single Assignment (GSA) form, an extension of Static Single Assignment (SSA) that captures data/control dependences and reaching definition information for scalar and array variables. This paper presents a simple and fast GSA construction ...
Analysis of symbolic expressions benefits from a suitable program representation. We show how to build thinned gated single-assignment (TGSA) form, a value-oriented program representation which is more complete than standard SSA form, defined on all reducible programs, and better for representing symbolic expressions than program dependence graphs or original GSA form.
An almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at ø-nodes, and introduces a new concept of gating path, which is path in the control flow graph from the immediate dominator u of a node to v, such that every node in the path is dominated by u. In this paper, we present an almost-linear time algorithm for constructing ...
The XARK compiler operates on top of the Gated Single Assignment (GSA) form of a high-level intermediate representation (IR) of the source code. Recognition is carried out through a demand-driven ...
The Gated Single-Assignment (GSA) program representa-tion is an extension of the Static Single Assignment (SSA) representation [CFR+ 91]. GSA was introduced by Bal-lance, Ma,ccabe and Ottenstein as a part of Program De-pendence Web (PDW) [BM090]. GSA is a convenient representation for several program analysis and optimiza-
In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a type of intermediate representation (IR) where each variable is assigned exactly once. SSA is used in most high-quality optimizing compilers for imperative languages, including LLVM, the GNU Compiler Collection, and many commercial compilers.. There are efficient algorithms for converting ...
The Gated Static Single Assignment (GSA) form was proposed by Ottenstein et al. in 1990, as an intermediate representation for implementing advanced static analyses and optimisation passes in compilers. Compared to SSA, GSA records additional data dependencies and provides more context, making optimisations more effective and allowing one to ...
The Future Gated Single Assignment Form (FGSA) is presented, a new static single assignment form which can be used by an optimizing compiler as its internal representation and the micro-architecture as its instruction set, and is efficiently computable by using a series of T1/T2 transformations. Expand. 3. 1 Excerpt.
In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at 0—nodes. The gating functions specify the control dependences for each reaching definition at a node. We introduce a new concept of gating path, which is a path in the control flow graph ...
This is somewhat mitigated by translating it to static single assignment (SSA) form [53] or one of its variants, such as gated SSA [213], thinned gated SSA [82] or future gated SSA [60], but in ...
These are used in gated single assignment form . Alpern et al. [6] presented a precursor of GSA for structured code, to detect equality of variables. This chapter adopts their notations, i.e., a ϕ if for an if-then-else construction, a ϕ entry for the entry of a loop, and a ϕ exit for its exit. The original usage of GSA was by Ballance et al ...
> approach based on single assignment. Brandis thesis is nicely written, but he didn't invent the GSA form. AFAIK, Ballance, Maccabe, and Ottenstein introduced the GSA as /gated single-assignment form/ in "The Program Dependence Web: A Representation Supporting Control-, Data-, and Demand-Driven Interpretation of Imperative Languages".
Abstract. In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at @-nodes. The gating functions specify the control dependence for each reaching definition at a @-node. We introduce a new concept of gating path, which is a path in the control flow ...
Abstract. Gated Single Assignment (GSA) form is used to transform an imperative program into a form suitable for dataflow interpretation. We describe a GSA-formed Control Flow Graph (CFG) that contains gating functions and the information of switches. We also present an algorithm to transform an imperative program into a GSA-formed CFG.
The Future Gated Single Assignment Form (FGSA) is presented, a new static single assignment form which can be used by an optimizing compiler as its internal representation and the micro-architecture as its instruction set, and is efficiently computable by using a series of T1/T2 transformations. We present a new static single assignment form which can be used by an optimizing compiler as its ...