graph must be in single static assignment (ssa) form however

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

ValidationError: Graph must be in single static assignment (SSA) form, however 'layer1_0_relu0_fwd' has been used as output names multiple times

When converting MXNet i3d_resnet50_v1_custom model to onxx I got an error like this:

onxx version I used: 1.2.1

Bug fixed with the help of github discussion .

Installing the onnx and support library

!apt-get install protobuf-compiler libprotoc-dev

!pip install onnx==1.7

Cloning the mxnet v1.x

!rm -r incubator-mxnet

!git clone -b v1.x --single-branch https://github.com/apache/incubator-mxnet.git

Building the wheel

%cd /content/incubator-mxnet/python/mxnet/onnx/

!python setup.py install --force

Finally importing and using

import mx2onnx

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged mxnet gluon onnx or ask your own question .

• The Overflow Blog
• Masked self-attention: How LLMs learn relationships between tokens
• Deedy Das: from coding at Meta, to search at Google, to investing with Anthropic
• Featured on Meta
• User activation: Learnings and opportunities
• Preventing unauthorized automated access to the network
• Feedback Requested: How do you use the tagged questions page?

Hot Network Questions

• What happens if parents refuse to name their newborn child?
• Problems regressing y on x/y?
• Is it possible to know where the Sun is just by looking at the Moon?
• The meaning of the recursive type μt.t
• Can you find a grand tour of the rooms in this 12x12 grid?
• Help with unidentified character denoting temperature, 19th century thermodynamics
• Is it ethical to edit grammar, spelling, and wording errors in survey questions after the survey has been administered, prior to publication?
• Where is this NPC's voice coming from?
• Do pilots have to produce their pilot license to police when asked?
• Find all tuples with prescribed ordering
• Do we have volitional control over our level of skepticism?
• World's smallest Sudoku!
• How does a rotating system behave as mass varies?
• Randomly color the words
• MegaRAID device can't start in Windows, error code 10 I/O adapter hardware error has occurred
• Book where the humans discover tachyon technology and use this against a race of liquid metal beings
• What is "illegal, immoral or improper" use in CPOL?
• Why would elves care what happens to Middle Earth?
• Questions about using a public grill
• Used car dealership refused to let me use my OBDII on their car, is this a red flag?
• Informal "chats" with potential grad school advisors
• In the Silmarillion or the Appendices to ROTK, Do the Dwarves of Khazad-dûm know about the Balrog below prior to Durin receiving the ring?
• Does the A320 have an audible A/THR disconnect sound?
• How to Organise/Present Built Worlds?

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.

• Engineering Mathematics
• Discrete Mathematics
• Operating System
• Computer Networks
• Digital Logic and Design
• C Programming
• Data Structures
• Theory of Computation
• Compiler Design
• Computer Org and Architecture

Static Single Assignment (with relevant examples)

Static Single Assignment was presented in 1988 by Barry K. Rosen, Mark N, Wegman, and F. Kenneth Zadeck. 

In compiler design, Static Single Assignment ( shortened SSA) is a means of structuring the IR (intermediate representation) such that every variable is allotted a value only once and every variable is defined before it’s use. The prime use of SSA is it simplifies and improves the results of compiler optimisation algorithms, simultaneously by simplifying the variable properties. Some Algorithms improved by application of SSA – 

• Constant Propagation –   Translation of calculations from runtime to compile time. E.g. – the instruction v = 2*7+13 is treated like v = 27
• Value Range Propagation –   Finding the possible range of values a calculation could result in.
• Dead Code Elimination – Removing the code which is not accessible and will have no effect on results whatsoever.
• Strength Reduction – Replacing computationally expensive calculations by inexpensive ones.
• Register Allocation – Optimising the use of registers for calculations.

Any code can be converted to SSA form by simply replacing the target variable of each code segment with a new variable and substituting each use of a variable with the new edition of the variable reaching that point. Versions are created by splitting the original variables existing in IR and are represented by original name with a subscript such that every variable gets its own version.

Example #1:

Convert the following code segment to SSA form:

Here x,y,z,s,p,q are original variables and x 2 , s 2 , s 3 , s 4 are versions of x and s. 

Example #2:

Here a,b,c,d,e,q,s are original variables and a 2 , q 2 , q 3 are versions of a and q. 

Phi function and SSA codes

The three address codes may also contain goto statements, and thus a variable may assume value from two different paths.

Consider the following example:-

Example #3:

When we try to convert the above three address code to SSA form, the output looks like:-

Attempt #3:

We need to be able to decide what value shall y take, out of x 1 and x 2 . We thus introduce the notion of phi functions, which resolves the correct value of the variable from two different computation paths due to branching.

Hence, the correct SSA codes for the example will be:-

Solution #3:

Thus, whenever a three address code has a branch and control may flow along two different paths, we need to use phi functions for appropriate addresses.

Similar Reads

Please login to comment....

• Best Smartwatches in 2024: Top Picks for Every Need
• Top Budgeting Apps in 2024
• 10 Best Parental Control App in 2024
• Top Language Learning Apps in 2024
• GeeksforGeeks Practice - Leading Online Coding Platform

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Lab 7: Static Single-Assignment Form

In this lab, you will build a static single-assignment form (SSA) for your Tiger compiler to perform optimizations. SSA is a state-of-the-art IR also used in production compilers such as GCC or LLVM.

This lab consists of two parts: first, in part A, you will design and implement data structures defining the static single-assigment form. You will also implement translations from CFG to SSA as well as translations from SSA back to CFG. Second, in part B, you will implement several classic data-flow analysis and optimizations on SSA.

Getting Started

First check out the source we offered you for lab7:

these commands will first commit your changes to the lab6 branch of your local Git repository, and then create a local lab7 branch and check out the remote lab7 branch into the new local lab7 branch.

Do not forget to resolve any conflicts before commit to the local lab7 branch:

You should first import the new lab7 code into your favorite IDE, and make sure the code compiles. There are a bunch of new files that you should browse through:

Hand-in Procedure

When you finished your lab, zip you code and submit to the online teaching system .

Part A: Static Single-Assignment Form (SSA)

The static single-assignment form (SSA) is an important compiler intermediate representation, in which each variable is assigned (statically) at most once. SSA is more advantageous over other compiler IRs in that its single-assignment property makes program analysis and optimization simpler and more efficient. As a result, SSA has become a de-factor IR in modern optimizing compilers for imperative, OO, or even functional languages.

In this part of the lab, you will build a static single-assigment form for your Tiger compiler, and conduct optimizations based on your SSA IR. To aid in your implementation, we have given some hints for most exercises, but keep in mind that these hints are not mandatory, and you are free (and encouraged) to propose your own ideas.

SSA Data Structure

To better reuse your existing code base, you will implement SSA by leveraging data structures already designed for the control-flow graph. This design decision makes the interfaces cleaner and more elegant hence simplifying subsequent compilation phases.

Dominator Trees

You will be constructing the SSA form with the following 5 steps: 1) calculate dominators; 2) build dominator trees; 3) calculate dominance frontiers; 4) place φ-functions; and 5) rename variables.

In this part, you will finish the first two steps, that is, you will first calculate dominators then build a dominator tree for a given CFG.

Dominance Frontier

In this part of the lab, you will be implementing the third step to build an SSA, that is, you will calculate the dominance frontier for each node. The dominance frontier DF[n] of a node n is the set of all nodes d such that n dominates an immediate predecessor of d , but n does not strictly dominate d . Intuitively, the dominance frontier DF[n] for a node n is the set of nodes where n 's dominance stops.

φ-function Placement

In this part, you will implement the fourth step to build an SSA, that is, you will be implementing the φ-function placement. The φ-function placement algorithm places φ-functions at the top of corresponding blocks. Specifically, for a definition

to a variable x in a basic block n , this algorithm will place a φ-function

at the top of each n 's dominance frontier d ∈ DF[n] .

Renaming the Variables

In this part of the lab, you will be implementing the fifth and last step to build an SSA, that is, you will rename variables to make its definition unique.

To this point, your Tiger compiler can convert all legal MiniJava programs to SSA forms. Do regression test your Tiger compiler and fix potential bugs.

Translation Out of SSA Forms

Modern machines do not support the φ-functions directly, hence φ-functions must be eliminated before execution. This task is accomplished by the translation out of SSA forms.

To this point, your Tiger compiler can convert any SSA form back to a corresponding CFG. Do not forget to regression test your Tiger compiler.

Part B: SSA-based Optimizations

SSA makes compiler optimizations not only easier to engineer but also more efficient to execute, largely due to its single-assignment property. This nice property make it much easier to calculate the data-flow information required to perform optimizations.

In this part of the lab, you will re-implement several optimizations that we have done on the CFG on SSA again: dead code-elimination, constant propagation, copy propagation, among others. And you will also implement several novel optimizations that are particularly suitable for SSA: conditional constant propagation, global value numbering, among others.

Dead-code Elimination

In SSA, a statement x = e is dead, if the variable x is not used by any other statement (and e does not have side effects). As a result, this statement x = e can be safely eliminated.

Constant Propagation

In SSA, given a statement of the form x = c in which c is a constant, we can propagate the constant c to any use of variable x .

Copy Propagation

In SSA, given a copy statement x = y , then any use of x can be replaced by y .

φ-function Elimination

In SSA, if a φ-function is of a special form taking a list of same arguments:

where c is a constant, then this φ-function can be eliminated by rewriting it to a normal assignment to x :

Note that, often the time, this special form of φ-function x = φ(c, c, ..., c) might be generated by constant propagation optimizations, which substituted φ-function arguments by constants.

Similarly, the φ-function:

can be eliminated by rewriting it to an assignment statement:

where y is a variable.

Conditional Constant Propagation

Global value numbering, partial redundancy elimination.

Do not forget to test Tiger compiler after finishing all these optimizations.

Part C: SSA Program Analysis

This completes the lab. Remember to hand in your solution to the online teaching system.

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement . We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

as input graph multiple times #164

vicwer commented Nov 29, 2021 • edited Loading

daquexian commented Dec 7, 2021

Sorry, something went wrong.

No branches or pull requests

Static single assignment form for machine code

New citation alert added.

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

New Citation Alert!

Please log in to your account

Information & Contributors

Bibliometrics & citations, view options.

• Farvardin K Reppy J (2020) A New Backend for Standard ML of New Jersey Proceedings of the 32nd Symposium on Implementation and Application of Functional Languages 10.1145/3462172.3462191 (55-66) Online publication date: 2-Sep-2020 https://dl.acm.org/doi/10.1145/3462172.3462191
• MacQueen D Harper R Reppy J (2020) The history of Standard ML Proceedings of the ACM on Programming Languages 10.1145/3386336 4 :HOPL (1-100) Online publication date: 12-Jun-2020 https://dl.acm.org/doi/10.1145/3386336
• Farvardin K Reppy J Donaldson A Torlak E (2020) From folklore to fact: comparing implementations of stacks and continuations Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation 10.1145/3385412.3385994 (75-90) Online publication date: 11-Jun-2020 https://dl.acm.org/doi/10.1145/3385412.3385994
• Show More Cited By

Index Terms

General and reference

Document types

Computing standards, RFCs and guidelines

Mathematics of computing

Mathematical analysis

Mathematical optimization

Software and its engineering

Software notations and tools

Source code generation

General programming languages

Theory of computation

Design and analysis of algorithms

Recommendations

Static Single Assignment (SSA) is an effective intermediate representation in optimizing compilers. However, traditional SSA form and optimizations are not applicable to programs represented as native machine instructions because the use of dedicated ...

Predicated Static Single Assignment

Increases in instruction level parallelism are needed to exploit the potential parallelism available in future wide issue architectures. Predicated execution is an architectural mechanism that increases instruction level parallelism by removing branches ...

Advances in static single assignment form and register allocation

Information, published in.

Rutgers Univ., New Brunswick, NJ

Univ. of Colorado, Boulder, and Microsoft Research

Univ. of Colorado, Boulder

Rowan Univ., Glassboro, NJ

• SIGPLAN: ACM Special Interest Group on Programming Languages
• SIGSOFT: ACM Special Interest Group on Software Engineering

Association for Computing Machinery

New York, NY, United States

Publication History

Permissions, check for updates, acceptance rates, contributors, other metrics, bibliometrics, article metrics.

• 25 Total Citations View Citations
• 1,040 Total Downloads
• Downloads (Last 12 months) 129
• Downloads (Last 6 weeks) 16
• Mühlberg J Lüttgen G (2014) Symbolic object code analysis International Journal on Software Tools for Technology Transfer (STTT) 10.1007/s10009-012-0256-8 16 :1 (81-102) Online publication date: 1-Feb-2014 https://dl.acm.org/doi/10.1007/s10009-012-0256-8
• Colombet Q Boissinot B Brisk P Hack S Rastello F Gupta R Mooney V (2011) Graph-coloring and treescan register allocation using repairing Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems 10.1145/2038698.2038708 (45-54) Online publication date: 9-Oct-2011 https://dl.acm.org/doi/10.1145/2038698.2038708
• Mühlberg J Lüttgen G (2011) Verifying compiled file system code Formal Aspects of Computing 10.1007/s00165-011-0198-z 24 :3 (375-391) Online publication date: 20-Aug-2011 https://doi.org/10.1007/s00165-011-0198-z
• Boissinot B Brandner F Darte A de Dinechin B Rastello F (2011) A non-iterative data-flow algorithm for computing liveness sets in strict SSA programs Proceedings of the 9th Asian conference on Programming Languages and Systems 10.1007/978-3-642-25318-8_13 (137-154) Online publication date: 5-Dec-2011 https://dl.acm.org/doi/10.1007/978-3-642-25318-8_13
• Mühlberg J Lüttgen G (2010) Symbolic object code analysis Proceedings of the 17th international SPIN conference on Model checking software 10.5555/1928137.1928140 (4-21) Online publication date: 27-Sep-2010 https://dl.acm.org/doi/10.5555/1928137.1928140
• Yardimci E Franz M (2009) Mostly static program partitioning of binary executables ACM Transactions on Programming Languages and Systems 10.1145/1538917.1538918 31 :5 (1-46) Online publication date: 3-Jul-2009 https://dl.acm.org/doi/10.1145/1538917.1538918
• Boissinot B Darte A Rastello F de Dinechin B Guillon C (2009) Revisiting Out-of-SSA Translation for Correctness, Code Quality and Efficiency Proceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization 10.1109/CGO.2009.19 (114-125) Online publication date: 22-Mar-2009 https://dl.acm.org/doi/10.1109/CGO.2009.19

View options

View or Download as a PDF file.

View online with eReader .

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Share this publication link.

Copying failed.

Share on social media

Affiliations, export citations.

• Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
• Download citation
• Copy citation

We are preparing your search results for download ...

We will inform you here when the file is ready.

Your file of search results citations is now ready.

Your search export query has expired. Please try again.