Stack Overflow
Stack Overflow

Questions tagged [ssa]

Static single assignment is a property of a compiler's intermediate representation for optimization and static analysis.

Static single assignment is an intermediate representation where each "variable" is assigned only once. When translating from a form with mutable variables, each variable is replaced with a set of variables representing each possible assignment in order to make the definition and usage of every value explicit.

63 questions
33
votes
14 answers

Do you find you still need variables you can change, and if so why?

One of the arguments I've heard against functional languages is that single assignment coding is too hard, or at least significantly harder than "normal" programming. But looking through my code, I realized that I really don't have many (any?) use…
MarkusQ
  • 21,814
  • 3
  • 56
  • 68
18
votes
2 answers

Converting SSA to stack machine

It is well known how to convert code from SSA representation to a register machine. (Basically, graph coloring register allocation is the core of such conversion.) But what's the general method for converting from SSA to a stack machine? (CIL byte…
rwallace
  • 31,405
  • 40
  • 123
  • 242
15
votes
2 answers

LLVM opt mem2reg has no effect

I am currently playing around with LLVM and am trying to write a few optimizers to familiarize myself with opt and clang. I wrote a test.c file that is as follow: int foo(int aa, int bb, int cc){ int sum = aa + bb; return sum/cc; } I…
Brenda So
  • 191
  • 1
  • 8
10
votes
1 answer

SSA for stack machine code

I'm working on a compiler for a stack machine (specifically CIL) and I've parsed the code into a graph of basic blocks. From here I'm looking to apply SSA to the methods, but it's not going too well. My first attempt (while working with a flat…
Serafina Brocious
  • 30,433
  • 12
  • 89
  • 114
10
votes
0 answers

Calculating administrative normal form

Administrative Normal Form is an intermediate representation of code, suitable for use by compilers, that is logically equivalent to Single Static Assignment but has some advantages. For example, checking whether a program is a valid SSA form is an…
rwallace
  • 31,405
  • 40
  • 123
  • 242
9
votes
1 answer

Can I translate an AST to SSA, or do I need to translate to a CFG then to SSA?

Can I translate an Abstract Syntax Tree directly into SSA form, or will I need to create a control flow graph and then create the Static Single Assignment form from said CFG? And in the context of a control flow graph: how do I represent this for a…
Jon Flow
  • 495
  • 3
  • 11
8
votes
1 answer

How to generate LLVM SSA Format

I write the following C code where variable X is being assigned twice: int main() { int x; x = 10; x = 20; return 0; } Compile and generate IR representation using the following command clang -emit-llvm -c ssa.c IR…
Shehbaz Jaffer
  • 1,944
  • 8
  • 23
  • 30
6
votes
1 answer

What is the difference between `select` and `phi` in LLVM IR?

For example, I have a C code: void foo(int x) { int y; if (x > 0) { y = 1; } else { y = 2; } // do something with y } To simplify this code in LLVM IR level (where y can be put in the register rather than stack),…
Evian
  • 1,035
  • 1
  • 9
  • 22
6
votes
1 answer

How would a register + stack based virtual machine work?

I know how register based and how stack based virtual machines work independently. I know the advantages and disadvantages of both. What I want to know is that has anyone ever tried to merge the two? I tried to search the net for the existence of…
Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
5
votes
1 answer

Getting "minimal" SSA from LLVM

The LLVM's opt -S -mem2reg pass produces the so-called "pruned" SSA -- the form that has all the dead phi functions removed. I would like to keep those phi instructions in the IR, obtaining the "minimal" SSA, but I'm failing to find an easy way to…
Kostya
  • 1,072
  • 11
  • 24
5
votes
1 answer

Static Single Assignment: not all possible paths define a variable - how to insert PHI?

I am implementing SSA construction for a compiler I'm writing. There is something I don't understand in the SSA algorithms (using the Cytron paper and the book Modern Compiler Implementation in Java, second edition by A.W. Appel). What if a variable…
Daniel A.A. Pelsmaeker
  • 47,471
  • 20
  • 111
  • 157
3
votes
1 answer

What are good, freely available SSA/SCCP resources?

This is what I could come up with so far: gcc related: SSA for Trees Tree SSA – A New Optimization Framework for GCC Tree SSA A New Optimization Infrastructure for GCC Design and Implementation of Tree SSA Other: An Implementation of Sparse…
none
  • 5,701
  • 28
  • 32
3
votes
0 answers

What does "clobbers" mean in the context of LLVM's memory dependence analysis

I am new to LLVM and i am currently working on something involving memory dependence analysis. Reading the docs i find the term "clobber" is used quite heavily. Now, i do understand what a clobbered register is in terms of e.g inline assembler, but…
eeg
  • 43
  • 5
3
votes
1 answer

Chordal graphs and SSA form programs

My question is about why every SSA form program corresponds to a chordal graph by default. Wikipedia defines chordal graphs as a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of…
yazan daba
  • 219
  • 5
  • 11
3
votes
1 answer

Meaning of a variable in GCC SSA format

I want to look at the SSA format GCC uses, so I tried the following simple test program: #include int main(int argc, char **argv) { int n = 0; int i; for (i = 0; i < 13; i++) n += argc; …
rwallace
  • 31,405
  • 40
  • 123
  • 242
1
2 3 4 5