Talk:Static single-assignment form

attribution

The introduction to the article states "SSA was developed by Ron Cytron, Jeanne Ferrante, Barry Rosen, Mark Wegman, and Ken Zadeck, researchers at IBM in the 1980s".

The current terminology is indeed that popularized by the IBM team. The ideas are a decade older.

The final sentence of Wegman and Zadeck's POPL85 "Constant Propagation with Conditional Branches" is ""We would also like to thank John Reif who made a special trip to Yorktown to help us understand his work". They are acknowleging the important of the referenced Rief and Lewis' POPL77 paper "Symbolic evaluation and the global value graph" where Phi-nodes are termed "birthpoints". Rief and Lewis in turn mention work done at Massachusetts Computer Associates: Shapiro and Saint's "The Representation of Algorithms" (CA-7002-1432, Feb 1970); Karr's "P-graphs" (CA-7501-1511, Jan 1975). Jsyjr (talk) 05:28, 31 January 2008 (UTC)

mistake

Currently the main page says "if the node A defines a certain variable, then that definition and that definition alone will reach every node A dominates", but this is clearly untrue. The variable can be redefined in other nodes that A dominates. For instance:

 x = 0;
 if(foo())
   bar()
 else
   baz()
 x = 6;
 biz();

The entire code there is dominated by the initial block with x=0 (assuming no non-local control flow out of one of the functions), but the definition of x=0 does not reach biz().

I plan on correcting this once I decide how it should be worded.

arrays and structs

Arrays and structs require special treatment that ought to be described. Loisel 09:53, 22 Apr 2005 (UTC)

Sure. I don't know much about this currently, if you'd like to add it. I'd suggest a separate section, to avoid overwhelming the novice. Deco 16:44, 22 Apr 2005 (UTC)

lwn

There is an explaination of tree SSA in gcc at linux weekly news.

can we have an example involving a loop

I think i can see how this would apply to loops but i'm not sure enough to write an example. Plugwash 23:00, 2 May 2005 (UTC)

That's a good idea. It does make things a little more interesting. Will look at this when I have time, if no one else does first. Deco 05:14, 3 May 2005 (UTC)

Summer 2004

Please change summer 2004 (in GCC description) to a correct month --200.178.63.180 05:53, 8 May 2005 (UTC)

Removed from mains article in SSA Extensions

Is it necessary to enumerate all known SSA extensions? Should each extension have a separate page? What about gated single assignment form, which is probably the most popular SSA extension?

I don't believe we're likely any time soon to have enough material to justify separate pages on each form. Let's keep it all here until one becomes too large. I'm not sure which SSA form is most popular, but I'd hazard a guess of "ordinary" SSA. Deco 02:05, 7 Jun 2005 (UTC)

SSA and AST

The article says SSA is not suitable for tree representations. I can see where this is can be true, but I can also come up with tree representations where it could work (I think). More importantly, GCC now implements a kind of tree-ssa. Anyone care to elaborate on that?? Madhu 03:59, 19 February 2006 (UTC)

It's more accurate to say that SSA is normally used with linear intermediate representations, not tree-based IRs, but there's no reason it can't be used with tree-based IR as long as reaching definitions are clear. I'll just remove the statement you noted.

As for Tree-SSA, just based on my initial impression it still uses a 3-address (linear) format, but each individual instruction is represented using a tree, for backward compatibility with GCC's tree IR. Deco 06:29, 19 February 2006 (UTC)

"Φ function" verses "Φ-function"

The literature (e.g. the classic Cryton et al paper, Andrew Appel's books, most papers I have read) use a hyphen between "Φ" and "function". Why is this not followed here? Is it the case that the original authors made a mistake and most literature follows them, either out of respect or ignorance? I don't think that you could say that "Φ" is used as an adjective, so it seems to me that a hyphen is indicated. However, I'm far from confident about this. I'd like to know definitively the correct way to write this term, and I believe that Wikipedia should be a guide in this respect. --Mike Van Emmerik 23:03, 5 August 2006 (UTC)

We should probably follow what the literature says. Regarding its English correctness, see hyphen. I would regard this as a "noun noun" phrase, which generally is not hyphenated (e.g., ice cream, department store manager), but again I wouldn't contradict the literature. Deco 01:41, 6 August 2006 (UTC)

idom(n)

Can you please explain me what id idom(n). It is given that idom(n) is the immediate dominator of node n. but if a node has two predecessors (dominator) what will be the idom (n)? —Preceding unsigned comment added by Rudk (talk • contribs) 05:26, 27 March 2009 (UTC)

In a flow graph, a node n dominates a node m if every path from the graph's entry node to m must pass through n. If m has more than one predecessor, neither of those predecessors can be its dominator. Instead, its dominator will be a predecessor farther along the path back to the entry node. (Use of "back indicates traversing edges against their direction.)

Given the set of nodes that dominate m, often denoted DOM(n), its immediate dominator is the node in the DOM set closest to m in the graph. Another way to picture the relationship is that inside DOM(m) you will find one node dominated by all the other nodes in DOM(m). That node is m's immediate dominator, sometimes denoted IDOM(m). [The notation IDOM(m) suggests that IDOM is a set and might mislead you into thinking that IDOM(m) can be more than one node. IDOM(m) is a single node in the flow graph.] --Kdcooper (talk) 22:04, 26 August 2009 (UTC)

examples

PyPy uses SSA for both compilation of RPython and JIT. Should I add this to the list of implementations? It's already sort of long. —Preceding unsigned comment added by Fijal (talk • contribs) 04:41, 1 April 2010 (UTC)

Possibile mistake in section Variations that reduce the number of Φ functions

When you describe the semi-pruned SSA the last phrase says: On the other hand, pruned SSA form will contain more Φ functions. But pruned SSA is better than semi-pruned, so it will contain less Φ functions. 93.145.207.190 (talk) 08:14, 6 August 2010 (UTC) by mickey_mouse

Notation interpretation

In the currently provided example control flow graphs, in which way are two arrows coming from one box to be interpreted? --Abdull (talk) 15:09, 8 October 2010 (UTC)

Is SSA an IR or a property of an IR?

The first sentence says that SSA form is an IR, but I think it is a property of an IR. 129.13.72.198 (talk) 13:14, 11 January 2011 (UTC)

Human after all

Humans can see that the first assignment is not necessary, and that the value of y being used in the third line comes from the second assignment of y. A program would have to perform reaching definition analysis to determine this.

I don't think people have any mystical computational power that stems from having a soul - a human needs to perform reaching definition analysis too... ~ Booya ^Bazooka 14:22, 16 March 2011 (UTC)

Terrible language

The article is a mostly unreadable convolute of terrible grammar and should _really_ be rewritten by someone with a firm grip of the English grammar. Example: "new variables typically indicated by the original name with a subscript in textbooks". *Shudder*