dynamic single assignment

Peter Vanbroekhoven             

Dynamic single assignment and pointer conversion.

Although classic compiler optimizations like constant propagation, common subexpression elimination and dead code elimination certainly have their use within a compiler, they are not sufficient for optimizing code for modern processors. In a multi-processor environment, one may want to parallelize code such that parts of the code can be run in parallel and the code possibly executes faster. This however requires techniques quite different from those used in classic compiler optimizations. On vector processors, the same operation can be executed on a whole vector of operands at once. Also new processors sometimes include special instructions that allow executing an operation on multiple operand sets (typically 4, but depending on the size of the individual operands), like MMX and SSE instructions on x86. To get the maximum out of these facilities, we need techniques that are substantially different from classic compiler techniques. Also there is the growing performance gap between processors and main memory, and to bridge this gap we need techniques more advanced than classic compiler techniques.

If we look at each of the different examples above, i.e. , parallelization, compiling for vector processors or MMX and SSE instruction sets, or optimizing memory use, a central theme is that we need to know how operations can be reordered without changing the functionality of the code. In case of parallelization, code executed in parallel with other code can be interleaved in any way so we can only parallelize if reordering is allowed. On vector machines we want to execute multiple operations in parallel. Besides the need to verify that this is allowed, one needs to reorder the code in order to group operations that can be executed in parallel. When optimizing memory use, we want to reorder operations e.g. , in order to reduce the set of data that is live such that less memory is needed. One can see that for each of these optimizations one wants the maximum opportunity for reordering to be present, and have as accurate information about this available. And this is where dynamic single assignment and pointer conversion come in.

Code in dynamic single assignment (or DSA) form is such that during execution there is only a single assignment to each memory element, be it a scalar variable or each of the elements of an array. Another way to formulate this is that no value is ever overwritten. In multiple assignment code, we have to make sure all reads for a certain value happen before that value is overwritten. This clearly limits the reordering we can do on the code, and this we call dependencies. Transforming the code to DSA removes those dependencies by removing overwriting of values. The only restrictions on reordering is then that we cannot read a value before it is written. As such, DSA provides the maximum opportunity for reordering, aside from changes of algorithm ( i.e. , changes in data flow). In the field of parallelization, dynamic single assignment has been used by Featrier [1], but this work is both limited in applicability and scalability. The work of Kienhuis [2] extends on Feautrier's work, but still has many limitations. In our work we are trying to devise a new automatic method for transformation to DSA that both works for real size applications and that is extendible.

One of the constructs that currently cannot be transformored to DSA automatically is the use of pointers. The problems with pointers are that in a certain way they render the memory locations they point to anonymous, and that pointer arithmetic is allowed instead of direct indexing of memory. One approach is to handle pointers conservatively in analyses as either possibly pointing to anything or pointing to a certain set of data as determined by pointer analyses. Another approach is to convert pointer references to direct references to the arrays these pointers point to. In the context of hardware synthesis, this approach has been used [3], but the resulting program, though nicely mappable onto hardware, is not interesting for analyses since it derives basically nothing about data flow. We are working on extending this method such that the data flow is exposed.

For more details on dynamic single assignment, see [4]. Pointer conversion is part of future work.

[1] P. Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming , 20(1):23-53, 1991. [2] B. Kienhuis. Matparser: An array dataflow analysis compiler. Technical report, University of California, Berkeley, February 2000. [3] L. Séméria and G. De Micheli. Spc: Synthesis of pointers in C: Application of pointer analysis to the behavioral synthesis from C. In proceedings of the International Conference on Computer-Aided Design ICCAD'98 , pages 321-326, November 1998. [4] P. Vanbroekhoven, G. Janssens, M. Bruynooghe, H. Corporaal, and F. Catthoor. A step towards a scalable dynamic single assignment conversion. Technical Report CW 360 , KULeuven, April 2003.

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to  upgrade your browser .

Enter the email address you signed up with and we'll email you a reset link.

• We're Hiring!
• Help Center

A practical dynamic single assignment transformation

2007, ACM Transactions on Design Automation of Electronic Systems

This paper presents a novel method to construct a dynamic single assignment (DSA) form of array intensive, pointer free C programs. A program in DSA form does not perform any destructive update of scalars and array elements; that is, each element is written at most once. As DSA makes the dependencies between variable references explicit, it facilitates complex analyses and optimizations of programs. Existing transformations into DSA perform a complex data flow analysis with exponential analysis time, and they work only for a limited class of input programs. Our method removes irregularities from the data flow by adding copy assignments to the program, so that it can use simple data flow analyses. The presented DSA transformation scales very well with growing program sizes and overcomes a number of important limitations of existing methods. We have implemented the method and it is being used in the context of memory optimization and verification of those optimizations. Experiments sh...

Related Papers

Lecture Notes in Computer Science

Gerda Janssens

ACM SIGPLAN Notices

The focus of this paper is on a data flow-transformation called advanced copy propagation. After an array is assigned, we can, under certain conditions, replace a read from this array by the righthand side of the assignment. If so, the intermediate assignment can be skipped. In case it becomes dead code, it can be eliminated. Where necessary we distinguish between the different elements of arrays as well as the different runtime instances of statements, allowing us to do propagation over global loop and condition scopes. We have formalized two basic operations: non-recursive propagation that operates on two statements and recursive propagation that operates on one statement. A global algorithm uses these two operations to do propagation on code involving any number of statements. Running our prototype implementation on some multimedia kernels shows that we can get a decrease in memory acesses between 22% and 43%.

Journal of Electronic Testing

Martin Palkovic

Journal of Low Power Electronics

Journal of Universal …

KC Shashidhar (DESICS Division, IMEC vzw, Kapeldreef 75, B-3001 Heverlee, and Department of Computer Science, Katholieke Universiteit Leuven, Belgium [email protected]) ... Maurice Bruynooghe (Department of Computer Science, Katholieke Universiteit Leuven, Belgium ...

Journal of Signal Processing Systems

RELATED PAPERS

ACM Transactions on Programming Languages and Systems

2007 Design, Automation & Test in Europe Conference & Exhibition

Todor Stefanov

Electronic Notes in Theoretical Computer Science

Proceedings of the 33rd ACM SIGPLAN conference on Programming Language Design and Implementation - PLDI '12

Nick Johnson

Proceedings of the 15th international conference on Parallel architectures and compilation techniques - PACT '06

Christophe Alias , Lawrence Rauchwerger

Christophe Alias

Saman Amarasinghe

Diego Garbervetsky , F. Fernandez

Sylvain Girbal

Proceedings European Design and Test Conference. ED & TC 97

Emile Aarts

Mattias O'Nils , Martin Palkovic , Benny Thörnberg

Miguel Miranda

Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming - PPoPP '08

J. Ramanujam , Ponnuswamy Sadayappan

International Journal of Parallel Programming

Dirk Stroobandt , Harald Devos , Jan Van Campenhout

Journal of Signal …

Jordi Carrabina

Embedded Systems for Real- …

Dermot Cochran

Sigplan Notices

Uday Bondhugula

Ponnuswamy Sadayappan

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Kostas Masselos

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Alex Nicolau

Pierre Amiranoff

Proceedings of the 20th annual international conference on Supercomputing - ICS '06

Nicolas Vasilache

Proceedingsof the 10th international workshop on Software & compilers for embedded systems - SCOPES '07

Christophe Poucet

Proceedings of the 19th annual international conference on Supercomputing - ICS '05

Proceedings IEEE International Conference on Application-Specific Systems, Architectures, and Processors. ASAP 2003

Optimizations and Machine Code Generation

Sanjay Rajopadhye

Application-Specific Systems, Architectures, and Processors

Paul Feautrier , S. Rajopadhye

10th Working Conference on Reverse Engineering, 2003. WCRE 2003. Proceedings.

Denis Barthou , Christophe Alias

RELATED TOPICS

•   We're Hiring!
•   Help Center
• Find new research papers in:
• Health Sciences
• Earth Sciences
• Cognitive Science
• Mathematics
• Computer Science
• Academia ©2024

• Open Advanced Search
• Enterprise Plans

Get 20M+ Full-Text Papers For Less Than $1.50/day.  Start a 14-Day Trial for You or Your Team.

Learn more →.

Sorry, your browser isn't supported.

Upgrading to a modern browser will give you the best experience with DeepDyve.

• Google Chrome

A practical dynamic single assignment transformation

• References BETA
• Recommended
• Add to Folder

Have problems reading an article? Let us know here.

Thanks for helping us catch any problems with articles on DeepDyve. We'll do our best to fix them.

How was the reading experience on this article?

Check all that apply - Please note that only the first page is available if you have not selected a reading option after clicking "Read Article".

Include any more information that will help us locate the issue and fix it faster for you.

Thank you for submitting a report!

Submitting a report will send us an email through our customer support system.

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

• ACM Transactions on Design Automation of... /
• Volume 12 Issue 4
• Subject Areas /
• Computer Science

This paper presents a novel method to construct a dynamic single assignment (DSA) form of array intensive, pointer free C programs. A program in DSA form does not perform any destructive update of scalars and array elements; that is, each element is written at most once. As DSA makes the dependencies between variable references explicit, it facilitates complex analyses and optimizations of programs. Existing transformations into DSA perform a complex data flow analysis with exponential analysis time, and they work only for a limited class of input programs. Our method removes irregularities from the data flow by adding copy assignments to the program, so that it can use simple data flow analyses. The presented DSA transformation scales very well with growing program sizes and overcomes a number of important limitations of existing methods. We have implemented the method and it is being used in the context of memory optimization and verification of those optimizations. Experiments show that in practice, the method scales well indeed, and that added copy operations can be removed in case they are unwanted.

ACM Transactions on Design Automation of Electronic Systems (TODAES) – Association for Computing Machinery

Published: Sep 1, 2007

Recommended Articles

There are no references for this article..

• {{#if ref_link}} {{ref_title}} {{ref_author}} {{else}} {{ref_title}} {{ref_author}} {{/if}}

Share the Full Text of this Article with up to 5 Colleagues for FREE

Sign up for your 14-day free trial now.

Read and print from thousands of top scholarly journals.

Continue with Facebook

Log in with Microsoft

Already have an account? Log in

Save Article to Bookmarks

Bookmark this article. You can see your Bookmarks on your DeepDyve Library .

To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.

Sign Up Log In

Subscribe to Journal Email Alerts

To subscribe to email alerts, please log in first, or sign up for a DeepDyve account if you don’t already have one.

Copy and paste the desired citation format or use the link below to download a file formatted for EndNote

Reference Managers

Follow a Journal

To get new article updates from a journal on your personalized homepage, please log in first, or sign up for a DeepDyve account if you don’t already have one.

Access the full text.

Sign up today, get DeepDyve free for 14 days.

Our policy towards the use of cookies

All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.

cookie policy

SSA-based Compiler Design

• Fabrice Rastello 0 ,
• Florent Bouchez Tichadou 1

Inria, Grenoble, France

You can also search for this editor in PubMed   Google Scholar

University of Grenoble Alpes, Grenoble, France

Provides first single-source reference to widely adopted, static-single assignment (SSA) form of compiler design

Offers readers state-of-the-art, advanced compiler optimization techniques

Includes content from globally recognized compiler research centers and engineering practitioners

18k Accesses

1 Citations

31 Altmetric

• Table of contents

About this book

Editors and affiliations, about the editors, bibliographic information.

• Publish with us

This is a preview of subscription content, log in via an institution to check access.

Access this book

• Available as EPUB and PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (24 chapters)

Front matter, vanilla ssa, introduction.

• Jeremy Singer

Properties and Flavours

• Philip Brisk, Fabrice Rastello

Standard Construction and Destruction Algorithms

• Jeremy Singer, Fabrice Rastello

Advanced Construction Algorithms for SSA

• Dibyendu Das, Upadrasta Ramakrishna, Vugranam C. Sreedhar

SSA Reconstruction

• Sebastian Hack

Functional Representations of SSA

• Lennart Beringer
• Markus Schordan, Fabrice Rastello

Propagating Information Using SSA

• Florian Brandner, Diego Novillo
• Benoît Boissinot, Fabrice Rastello

Loop Tree and Induction Variables

• Sebastian Pop, Albert Cohen

Redundancy Elimination

• Vivek Sarkar, Fabrice Rastello

Static Single Information Form

• Fernando Magno Quintão Pereira, Fabrice Rastello

Graphs and Gating Functions

• James Stanier, Fabrice Rastello

Psi-SSA Form

• François de Ferrière

Hashed SSA Form: HSSA

• Massimiliano Mantione, Fred Chow
• Engineering a Compiler
• Modern Compiler Design
• static-single assignment compiler
• SSA Form and Code Generation

This book provides readers with a single-source reference to static-single assignment

(SSA)-based compiler design. It is the first (and up to now only) book that covers

in a deep and comprehensive way how an optimizing compiler can be designed using

the SSA form. After introducing vanilla SSA and its main properties, the authors

describe several compiler analyses and optimizations under this form. They illustrate

how compiler design can be made simpler and more efficient, thanks to the SSA form.

This book also serves as a valuable text/reference for lecturers, making the teaching of

compilers simpler and more effective. Coverage also includes advanced topics, such as

code generation, aliasing, predication and more, making this book a valuable reference

for advanced students and practicing engineers.

Fabrice Rastello

Florent Bouchez Tichadou

Fabrice Rastello is an Inria research director and the leader of the CORSE (Compiler Optimization and Runtime SystEms) Inria team. His expertize includes automatic parallelization (PhD thesis on tiling as a loop transformations), and compiler back-end optimizations (engineer at STMicroelectronics’s compiler group + researcher at Inria). Among others, he advised several PhD thesis so as to fully revisit register allocation for JIT compilation in the light of Static Single Assignment (SSA) properties. He likes mixing theory (mostly graphs, algorithmic, and algebra) and practice (industrial transfer). His current research topics include: (i) combining run-time techniques with static compilation, hybrid compilation being an example of such approach he is trying to promote; (ii) performance debugging through static and dynamic (binary instrumentation) analysis; (iii) revisiting compilers infrastructure for pattern specific programs.

Florent Bouchez Tichadou received his Ph.D. in computer science in 2009 at the ENS Lyon in France, working on program compilation. He was then a post-doctoral fellow at the Indian Institute of Science (IISc) in Bangalore, India. He worked for three years at Kalray, a startup company in the Grenoble area in France. Since 2013, he is an assistant professor at the Université Grenoble Alpes (UGA).

Book Title : SSA-based Compiler Design

Editors : Fabrice Rastello, Florent Bouchez Tichadou

DOI : https://doi.org/10.1007/978-3-030-80515-9

Publisher : Springer Cham

eBook Packages : Computer Science , Computer Science (R0)

Copyright Information : The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2022

Hardcover ISBN : 978-3-030-80514-2 Published: 09 December 2022

Softcover ISBN : 978-3-030-80517-3 Published: 09 December 2023

eBook ISBN : 978-3-030-80515-9 Published: 08 December 2022

Edition Number : 1

Number of Pages : XVII, 382

Number of Illustrations : 116 b/w illustrations, 32 illustrations in colour

Topics : Circuits and Systems , Programming Languages, Compilers, Interpreters , Processor Architectures

Policies and ethics

• Find a journal
• Track your research

Lesson 6: Static Single Assignment

• discussion thread
• static single assignment
• SSA slides from Todd Mowry at CMU another presentation of the pseudocode for various algorithms herein
• Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency by Boissinot on more sophisticated was to translate out of SSA form
• tasks due March 8

You have undoubtedly noticed by now that many of the annoying problems in implementing analyses & optimizations stem from variable name conflicts. Wouldn’t it be nice if every assignment in a program used a unique variable name? Of course, people don’t write programs that way, so we’re out of luck. Right?

Wrong! Many compilers convert programs into static single assignment (SSA) form, which does exactly what it says: it ensures that, globally, every variable has exactly one static assignment location. (Of course, that statement might be executed multiple times, which is why it’s not dynamic single assignment.) In Bril terms, we convert a program like this:

Into a program like this, by renaming all the variables:

Of course, things will get a little more complicated when there is control flow. And because real machines are not SSA, using separate variables (i.e., memory locations and registers) for everything is bound to be inefficient. The idea in SSA is to convert general programs into SSA form, do all our optimization there, and then convert back to a standard mutating form before we generate backend code.

Just renaming assignments willy-nilly will quickly run into problems. Consider this program:

If we start renaming all the occurrences of a , everything goes fine until we try to write that last print a . Which “version” of a should it use?

To match the expressiveness of unrestricted programs, SSA adds a new kind of instruction: a ϕ-node . ϕ-nodes are flow-sensitive copy instructions: they get a value from one of several variables, depending on which incoming CFG edge was most recently taken to get to them.

In Bril, a ϕ-node appears as a phi instruction:

The phi instruction chooses between any number of variables, and it picks between them based on labels. If the program most recently executed a basic block with the given label, then the phi instruction takes its value from the corresponding variable.

You can write the above program in SSA like this:

It can also be useful to see how ϕ-nodes crop up in loops.

(An aside: some recent SSA-form IRs, such as MLIR and Swift’s IR , use an alternative to ϕ-nodes called basic block arguments . Instead of making ϕ-nodes look like weird instructions, these IRs bake the need for ϕ-like conditional copies into the structure of the CFG. Basic blocks have named parameters, and whenever you jump to a block, you must provide arguments for those parameters. With ϕ-nodes, a basic block enumerates all the possible sources for a given variable, one for each in-edge in the CFG; with basic block arguments, the sources are distributed to the “other end” of the CFG edge. Basic block arguments are a nice alternative for “SSA-native” IRs because they avoid messy problems that arise when needing to treat ϕ-nodes differently from every other kind of instruction.)

Bril in SSA

Bril has an SSA extension . It adds support for a phi instruction. Beyond that, SSA form is just a restriction on the normal expressiveness of Bril—if you solemnly promise never to assign statically to the same variable twice, you are writing “SSA Bril.”

The reference interpreter has built-in support for phi , so you can execute your SSA-form Bril programs without fuss.

The SSA Philosophy

In addition to a language form, SSA is also a philosophy! It can fundamentally change the way you think about programs. In the SSA philosophy:

• definitions == variables
• instructions == values
• arguments == data flow graph edges

In LLVM, for example, instructions do not refer to argument variables by name—an argument is a pointer to defining instruction.

Converting to SSA

To convert to SSA, we want to insert ϕ-nodes whenever there are distinct paths containing distinct definitions of a variable. We don’t need ϕ-nodes in places that are dominated by a definition of the variable. So what’s a way to know when control reachable from a definition is not dominated by that definition? The dominance frontier!

We do it in two steps. First, insert ϕ-nodes:

Then, rename variables:

Converting from SSA

Eventually, we need to convert out of SSA form to generate efficient code for real machines that don’t have phi -nodes and do have finite space for variable storage.

The basic algorithm is pretty straightforward. If you have a ϕ-node:

Then there must be assignments to x and y (recursively) preceding this statement in the CFG. The paths from x to the phi -containing block and from y to the same block must “converge” at that block. So insert code into the phi -containing block’s immediate predecessors along each of those two paths: one that does v = id x and one that does v = id y . Then you can delete the phi instruction.

This basic approach can introduce some redundant copying. (Take a look at the code it generates after you implement it!) Non-SSA copy propagation optimization can work well as a post-processing step. For a more extensive take on how to translate out of SSA efficiently, see “Revisiting Out-of-SSA Translation for Correctness, Code Quality, and Efficiency” by Boissinot et al.

• One thing to watch out for: a tricky part of the translation from the pseudocode to the real world is dealing with variables that are undefined along some paths.
• Previous 6120 adventurers have found that it can be surprisingly difficult to get this right. Leave yourself plenty of time, and test thoroughly.
• You will want to make sure the output of your “to SSA” pass is actually in SSA form. There’s a really simple is_ssa.py script that can check that for you.
• You’ll also want to make sure that programs do the same thing when converted to SSA form and back again. Fortunately, brili supports the phi instruction, so you can interpret your SSA-form programs if you want to check the midpoint of that round trip.
• For bonus “points,” implement global value numbering for SSA-form Bril code.