4 ms·

But the dragon book introduces three address code. SSA is a variant of three address code. Take a look here http://www.cs.columbia.edu/~aho/cs4115/Lectures/15

But the dragon book introduces three address code. SSA is a variant of three address code. Take a look here http://www.cs.columbia.edu/~aho/cs4115/Lectures/15-03-25.html#:~:text=Static%20single%2Dassignment%20(SSA),two%20different%20control%2Dflow%20paths http://www.cs.columbia.edu/~aho/cs4115/Lectures/15-03-25.htm....

sanxiyn 3y ago
Well yes, but you can't use the algorithm in the dragon book to generate three address code to generate SSA, because SSA has additional constraints. The dragon book really dropped the ball here, there is no excuse why it doesn't include any algorithm for SSA construction.
- deleted 3y ago
  [deleted]
k_g_b_ 3y ago
3AC/TAC is something fundamentally different than SSA. Sure, both somehow superficially constrain how you write variable assignment statements - if your intermediate representation contains such things and is a list of instructions. 3AC means that your "instructions" have <=3 operands, SSA means each "syntactic" variable is assigned at most once, that is: they are not a variable anymore. In fact, SSA transformation makes an imperative program referentially transparent (excluding any loads/stores from/to memory) and thus makes it a pure functional program (excluding memory). You can see a program in SSA form simply as a functional program where each basic block is a (nested) function and each PHI is a parameter of the function. SSA as a list of instructions/statements as in 3AC is a red herring and doesn't have any relation to why it's used in compilers/for static analysis. SSA is not a variant of 3AC, also because SSA transformation of 3AC requires the same algorithms as SSA transformation of any other common imperative IR does. In fact SSA makes no constraints on the number of operands in an instruction/operation what so ever.
- jobhdez 3y ago
  Three address code: ``` p = a + b q = p-c p = q * d ``` Ssa: ``` p1 = a+ b q1= p1 - c p2 = q1 * d ``` Given the above examples how is it not straightforward to use ssa instead of three address code using what the dragon book teaches? What is wrong with the above examples? In fact section 6.2.4 in the dragon book it says: “Two distinctive aspects distinguish SSA from three-address code. The first is that all assignments in SSA are to variables with distinct names; hence the term static single-assigment.” The second one is that ssa uses a function to combine two definitions
  - k_g_b_ 3y ago
    That's exactly what I mean with superficially similar. Sure, you can transform a non-3AC SSA IR into three address code or transform a 3AC IR into SSA form - as you have done in your example. However, you will need an SSA transformation/construction algorithm to do the latter, which is not that simple or straightforward, especially if you want to be somewhat optimal with placing the PHIs. You can also try to apply your existing analyses and program optimizations on the 3AC SSA - chances are high though that you'll have to adapt them to correctly handle PHIs however. If you simply treat them as a unanalyzed function calls you will likely suffer from a huge loss in analysis precision and optimization opportunities. On the other hand, if you write your analyses and transformations with SSA form as a precondition, you can reduce complexity because SSA form is referentially transparent, giving you a lot of things like use-def chains, dead code analysis, etc for more or less free. This is what people mean when they say that SSA is essential for modern compiler construction. That quote from the book is reductionist to the maximum possible extent and put's it in the direct comparison with 3AC, to which it only has the relation that both are transformations of IR instructions the result of both have nothing in common. The example is misleading because it displays the SSA IR also in 3AC - which is unnecessary - and it completely omits PHIs without which SSA properties simply do not hold and for which no 3AC correlation exists at all - they are not representable. In fact, control flow can easily be built such that a PHI has any amount of operands - e.g. a switch which might need significant additional code transformation to be representable as 3AC.
    - 3y ago

sanxiyn 3y ago

Well yes, but you can't use the algorithm in the dragon book to generate three address code to generate SSA, because SSA has additional constraints. The dragon book really dropped the ball here, there is no excuse why it doesn't include any algorithm for SSA construction.

deleted 3y ago
[deleted]

k_g_b_ 3y ago

3AC/TAC is something fundamentally different than SSA. Sure, both somehow superficially constrain how you write variable assignment statements - if your intermediate representation contains such things and is a list of instructions. 3AC means that your "instructions" have <=3 operands, SSA means each "syntactic" variable is assigned at most once, that is: they are not a variable anymore. In fact, SSA transformation makes an imperative program referentially transparent (excluding any loads/stores from/to memory) and thus makes it a pure functional program (excluding memory). You can see a program in SSA form simply as a functional program where each basic block is a (nested) function and each PHI is a parameter of the function. SSA as a list of instructions/statements as in 3AC is a red herring and doesn't have any relation to why it's used in compilers/for static analysis. SSA is not a variant of 3AC, also because SSA transformation of 3AC requires the same algorithms as SSA transformation of any other common imperative IR does. In fact SSA makes no constraints on the number of operands in an instruction/operation what so ever.

jobhdez 3y ago
Three address code: ``` p = a + b q = p-c p = q * d ``` Ssa: ``` p1 = a+ b q1= p1 - c p2 = q1 * d ``` Given the above examples how is it not straightforward to use ssa instead of three address code using what the dragon book teaches? What is wrong with the above examples? In fact section 6.2.4 in the dragon book it says: “Two distinctive aspects distinguish SSA from three-address code. The first is that all assignments in SSA are to variables with distinct names; hence the term static single-assigment.” The second one is that ssa uses a function to combine two definitions
- k_g_b_ 3y ago
  That's exactly what I mean with superficially similar. Sure, you can transform a non-3AC SSA IR into three address code or transform a 3AC IR into SSA form - as you have done in your example. However, you will need an SSA transformation/construction algorithm to do the latter, which is not that simple or straightforward, especially if you want to be somewhat optimal with placing the PHIs. You can also try to apply your existing analyses and program optimizations on the 3AC SSA - chances are high though that you'll have to adapt them to correctly handle PHIs however. If you simply treat them as a unanalyzed function calls you will likely suffer from a huge loss in analysis precision and optimization opportunities. On the other hand, if you write your analyses and transformations with SSA form as a precondition, you can reduce complexity because SSA form is referentially transparent, giving you a lot of things like use-def chains, dead code analysis, etc for more or less free. This is what people mean when they say that SSA is essential for modern compiler construction. That quote from the book is reductionist to the maximum possible extent and put's it in the direct comparison with 3AC, to which it only has the relation that both are transformations of IR instructions the result of both have nothing in common. The example is misleading because it displays the SSA IR also in 3AC - which is unnecessary - and it completely omits PHIs without which SSA properties simply do not hold and for which no 3AC correlation exists at all - they are not representable. In fact, control flow can easily be built such that a PHI has any amount of operands - e.g. a switch which might need significant additional code transformation to be representable as 3AC.
  - 3y ago