September 23
On 9/23/2024 1:23 AM, claptrap wrote:
> Thats why OP asked about phi instructions, you need them to merge the versions of a variable that reach the start of a basic block. Or at least you need to have some mechanism for it.

Seems to me it's the same thing from a different angle.

September 23
On Monday, 23 September 2024 at 08:44:04 UTC, Walter Bright wrote:
> On 9/23/2024 1:23 AM, claptrap wrote:
>> Thats why OP asked about phi instructions, you need them to merge the versions of a variable that reach the start of a basic block. Or at least you need to have some mechanism for it.
>
> Seems to me it's the same thing from a different angle.

How do you do dead code elimination in your backend? I mean if you have 3 assignments to X, and say 5 uses of X, how do you determine if any of the assignments are redundant?


September 23

On Monday, 23 September 2024 at 09:43:50 UTC, claptrap wrote:

>

On Monday, 23 September 2024 at 08:44:04 UTC, Walter Bright wrote:

>

On 9/23/2024 1:23 AM, claptrap wrote:

>

Thats why OP asked about phi instructions, you need them to merge the versions of a variable that reach the start of a basic block. Or at least you need to have some mechanism for it.

Seems to me it's the same thing from a different angle.

How do you do dead code elimination in your backend? I mean if you have 3 assignments to X, and say 5 uses of X, how do you determine if any of the assignments are redundant?

I cant reply for DMD but as I detect a confusion, let me add something about that... SSA is not about variables it's about nodes assigned uniquely once

So if X is a variable then each use of it is either a load or a store. (there can be bit cast and ptr arithmetic too, but let keep thing simple.)

September 23

On Monday, 23 September 2024 at 11:03:45 UTC, user1234 wrote:

>

On Monday, 23 September 2024 at 09:43:50 UTC, claptrap wrote:

>

I cant reply for DMD but as I detect a confusion, let me add something about that... SSA is not about variables it's about nodes assigned uniquely once

So if X is a variable then each use of it is either a load or a store. (there can be bit cast and ptr arithmetic too, but let keep thing simple.)

(pseudo LLVM IR, to illustrate, with X, a global uint)

%1 = i32  load  ptr @X
%3 = i32  add   i32 %1, i32 %1
     i32  store ptr @X, i32 %3
    (LLVM does not make store reuseable, that'd be be a non-sense)


You see variables are not accessed as-is, either you have a load or a store.
An SSA node is what starts with "%"

That's counter to everything I've read about it. It is defined as "variables are only assigned once", so each time you assign a new value to X, it gets a suffix, so each assignment to X becomes a new variable X0,X1... and so on.

It makes it explicit what definition reaches what uses of X. Even through all the control flow. That's actually what makes SSA useful.

A quick google says LLVM IR is SSA for registers but not memory locations. So I don't think your example shows anything.

What would show SSA is if you cant assign to a register multiple times. Eg..

%1 = i32  load  ptr @X
%2 = i32  load  ptr @Y
%2 = i32  add   i32 %1, i32 %2

That would be invalid in SSA

September 23

On Monday, 23 September 2024 at 11:49:27 UTC, claptrap wrote:

>

On Monday, 23 September 2024 at 11:03:45 UTC, user1234 wrote:

>

On Monday, 23 September 2024 at 09:43:50 UTC, claptrap wrote:

>

I cant reply for DMD but as I detect a confusion, let me add something about that... SSA is not about variables it's about nodes assigned uniquely once

So if X is a variable then each use of it is either a load or a store. (there can be bit cast and ptr arithmetic too, but let keep thing simple.)

(pseudo LLVM IR, to illustrate, with X, a global uint)

%1 = i32  load  ptr @X
%3 = i32  add   i32 %1, i32 %1
     i32  store ptr @X, i32 %3
    (LLVM does not make store reuseable, that'd be be a non-sense)


You see variables are not accessed as-is, either you have a load or a store.
An SSA node is what starts with "%"

That's counter to everything I've read about it. It is defined as "variables are only assigned once", so each time you assign a new value to X, it gets a suffix, so each assignment to X becomes a new variable X0,X1... and so on.

It makes it explicit what definition reaches what uses of X. Even through all the control flow. That's actually what makes SSA useful.

A quick google says LLVM IR is SSA for registers but not memory locations. So I don't think your example shows anything.

What would show SSA is if you cant assign to a register multiple times. Eg..

%1 = i32  load  ptr @X
%2 = i32  load  ptr @Y
%2 = i32  add   i32 %1, i32 %2

That would be invalid in SSA

Yes. That's impossible. Also the reasoning that each SSA instruction is a state of a register is not totally exact (that's not yours tho). At the IR stage the notion of register does not exist yet. However it's true that it's often the case.

Otherwise, my example showed that reasoning at the level of a variable is not relevant, for DCE at least. Actually an unused load should never be generated.
What can happen is something like

X + 1; // %1 = load ...
       // %2 = add

then DCE will realize that %2 is never used and drop %2 and %1.

IIRC D detects such cases at the front-end level and emits an error: "expression <...> has not effect".

September 23

On Monday, 23 September 2024 at 12:31:27 UTC, user1234 wrote:

> >

What would show SSA is if you cant assign to a register multiple times. Eg..

%1 = i32  load  ptr @X
%2 = i32  load  ptr @Y
%2 = i32  add   i32 %1, i32 %2

That would be invalid in SSA

Yes. That's impossible. Also the reasoning that each SSA instruction is a state of a register is not totally exact (that's not yours tho). At the IR stage the notion of register does not exist yet. However it's true that it's often the case.

Its poor choice of words on my part, my mental model is of SSA IR as like assembly language with infinite "virtual registers". But essentially its instructions that return a constant value.

%1 = i32  load  ptr @X

%1 is a constant value. But i find it hard not to think of it as a register, because it's all so assembly like.

>

Otherwise, my example showed that reasoning at the level of a variable is not relevant, for DCE at least. Actually an unused load should never be generated.
What can happen is something like

X + 1; // %1 = load ...
       // %2 = add

then DCE will realize that %2 is never used and drop %2 and %1.

Well yeah, when you convert to SSA each new definition of a variable (each time you assign a new value to it) you get a new virtual register, so

int x = 100 ==> x0 = 100     ==> %0 = 100
x = 10      ==> x1 = 10      ==> %1 = 10
x = x*x     ==> x2 = x1*x1   ==> %2 = mul %1,%1

So x ==> x0,x1,x2 ==> %0,%1,%2

The point is it makes it explicit which definition of X, reaches what use of X, even if you don't actually know that %0,%1,%2 are actual definitions of X.

But that isn't how Walters backend works as far as I can tell from his talk, since multiple elem can point to the same variable. If you have an 3 "elem" that store to variable "X", and one use of "X", there's no way to tell if any of those stores are redundant without actually working out how they all depend on each other.

September 23

On Monday, 23 September 2024 at 13:39:46 UTC, claptrap wrote:

>

On Monday, 23 September 2024 at 12:31:27 UTC, user1234 wrote:

> >

What would show SSA is if you cant assign to a register multiple times. Eg..

%1 = i32  load  ptr @X
%2 = i32  load  ptr @Y
%2 = i32  add   i32 %1, i32 %2

That would be invalid in SSA

Yes. That's impossible. Also the reasoning that each SSA instruction is a state of a register is not totally exact (that's not yours tho). At the IR stage the notion of register does not exist yet. However it's true that it's often the case.

Its poor choice of words on my part, my mental model is of SSA IR as like assembly language with infinite "virtual registers". But essentially its instructions that return a constant value.

%1 = i32  load  ptr @X

%1 is a constant value. But i find it hard not to think of it as a register, because it's all so assembly like.

>

Otherwise, my example showed that reasoning at the level of a variable is not relevant, for DCE at least. Actually an unused load should never be generated.
What can happen is something like

X + 1; // %1 = load ...
       // %2 = add

then DCE will realize that %2 is never used and drop %2 and %1.

Well yeah, when you convert to SSA each new definition of a variable (each time you assign a new value to it) you get a new virtual register, so

int x = 100 ==> x0 = 100     ==> %0 = 100
x = 10      ==> x1 = 10      ==> %1 = 10
x = x*x     ==> x2 = x1*x1   ==> %2 = mul %1,%1

So x ==> x0,x1,x2 ==> %0,%1,%2

The point is it makes it explicit which definition of X, reaches what use of X, even if you don't actually know that %0,%1,%2 are actual definitions of X.

I see. Actually each access to x is a different load. Remember that the front-end has solved what is x, in each case. Here it turns out it's the same. (maybe actually what you're looking for is how a D VarExp gets handled in the "glue-layer" ?)

Assuming x is an alloca (I let you imagine if it's a non-tls global and used in a threaded context, that would be an other piece of cake, at least not optimizable as I'll present it...) so

int x = 100;
x = 10;
x = x*x;

gives more something like

store x, 100

store x, 10

%1 = load x    // x as LHS
%2 = load x    // x as RHS
%3 = mul %1 %2 // x * x but as rvalue

store ptr x, %3

what an optimizer will see with that list of SSA nodes is, in 3 steps:

  1. first store can be dropped (dead code), giving
store x, 10

%1 = load x    // x as LHS
%2 = load x    // x as RHS
%3 = mul %1 %2 // x * x but as rvalue

store ptr x, %3
  1. %1 and %2 are consecutive common sub expressions, with no side effects, giving
store x, 10

%1 = load x    // x as LHS and RHS
%2 = mul %1 %1 // x * x but as rvalue
     store ptr x, %2
  1. x is not stored between the load and the mul, ending up with
store ptr x, 100 // 10 * 10 with constant folding
>

But that isn't how Walters backend works as far as I can tell from his talk, since multiple elem can point to the same variable. If you have an 3 "elem" that store to variable "X", and one use of "X", there's no way to tell if any of those stores are redundant without actually working out how they all depend on each other.

Sorry, I knewn this had the potential to go off topic. It's really just the word "variable" that has initially triggered me. Let's call this "SSA node".

September 23

On Monday, 23 September 2024 at 14:39:12 UTC, user1234 wrote:

>

On Monday, 23 September 2024 at 13:39:46 UTC, claptrap wrote:

>

On Monday, 23 September 2024 at 12:31:27 UTC, user1234 wrote:

Sorry, I knewn this had the potential to go off topic. It's really just the word "variable" that has initially triggered me. Let's call this "SSA node".

first 3 web hits...

"In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a type of intermediate representation (IR) where each variable is assigned exactly once"
https://en.wikipedia.org/wiki/Static_single-assignment_form

"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"
https://www.geeksforgeeks.org/static-single-assignment-with-relevant-examples/

"At its core, the SSA form of any program source program introduces only one new constraint: all variables are assigned (i.e., stored to) exactly once."
https://blog.yossarian.net/2020/10/23/Understanding-static-single-assignment-forms

SSA is by definition about assigning variables only once. You can call them nodes if you want, but the %n is referring to a variable of some sort.

Look at it this way, you can only think of them as nodes in a graph because the variables are renamed on each definition, if they weren't you'd have nodes with the same "%n" at the front.

September 23

On Monday, 23 September 2024 at 08:44:04 UTC, Walter Bright wrote:

>

On 9/23/2024 1:23 AM, claptrap wrote:

>

Thats why OP asked about phi instructions, you need them to merge the versions of a variable that reach the start of a basic block. Or at least you need to have some mechanism for it.

Seems to me it's the same thing from a different angle.

It isn't?

Perhaps you could show what the IR looks like for something like this:

int x = foo();
if (x == 1)
   x = 5;
else
   x = 6;
September 23

On Monday, 23 September 2024 at 15:46:25 UTC, claptrap wrote:

>

On Monday, 23 September 2024 at 14:39:12 UTC, user1234 wrote:

>

[...]

first 3 web hits...

"In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a type of intermediate representation (IR) where each variable is assigned exactly once"
https://en.wikipedia.org/wiki/Static_single-assignment_form

[...]

In the results, the use of the word "variable" is just wrong. That's exactly what's misleading. An SSA node is not a variable node and it does not represent a variable either.