www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Walter's talk on D backend

reply Dibyendu Majumdar <d.majumdar gmail.com> writes:
Hi,

I watched the talk on D backend; I thought it could have been 
very interesting but actually was very scant in details.

Two questions:

Just because expressions are in a tree, how does it make the 
backend SSA? It wasn't clear if the D backend uses virtual 
registers, and if these can be assigned only once. If that is the 
case then are their Phi instructions?

The register allocator description also did not really explain 
how it works. There was mention of coloring - was that a 
reference to graph coloring?

It seems that there is a lot of potential for Walter to do deep 
dive video recordings on the backend, where each topic is fully 
explored / explained.
Sep 18
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 18 September 2024 at 12:34:29 UTC, Dibyendu 
Majumdar wrote:

 Hi,

 I watched the talk on D backend; I thought it could have been 
 very interesting but actually was very scant in details.

 Two questions:

 Just because expressions are in a tree, how does it make the 
 backend SSA? It wasn't clear if the D backend uses virtual 
 registers, and if these can be assigned only once. If that is 
 the case then are their Phi instructions?

 The register allocator description also did not really explain 
 how it works. There was mention of coloring - was that a 
 reference to graph coloring?

 It seems that there is a lot of potential for Walter to do deep 
 dive video recordings on the backend, where each topic is fully 
 explored / explained.


The backend does not use SSA. Nor Phi instructions.
Sep 19
parent max haughton <maxhaton gmail.com> writes:
On Thursday, 19 September 2024 at 08:38:29 UTC, Stefan Koch wrote:


 The backend does not use SSA. Nor Phi instructions.


Indeed e.g. consider the IR generated within a loop. One couldn't 
do an algorithm like value numbering.

That being said, looking past the C heritage of the project there 
is a fairly clean idea shining through.
Sep 19
prev sibling next sibling parent max haughton <maxhaton gmail.com> writes:
On Wednesday, 18 September 2024 at 12:34:29 UTC, Dibyendu 
Majumdar wrote:

 Hi,

 I watched the talk on D backend; I thought it could have been 
 very interesting but actually was very scant in details.

 Two questions:

 Just because expressions are in a tree, how does it make the 
 backend SSA? It wasn't clear if the D backend uses virtual 
 registers, and if these can be assigned only once. If that is 
 the case then are their Phi instructions?

 The register allocator description also did not really explain 
 how it works. There was mention of coloring - was that a 
 reference to graph coloring?

 It seems that there is a lot of potential for Walter to do deep 
 dive video recordings on the backend, where each topic is fully 
 explored / explained.


I have wondered about the register allocator before too. I didn't 
get much of an intuition from reading the code but quite possible 
I missed something.
Sep 19
prev sibling next sibling parent reply Dibyendu Majumdar <mobile majumdar.org.uk> writes:
It seems to me that Walter may have based his original 
implementation on the C compiler by Dennis Ritchie.

The DMR C compiler had expression trees and separately control 
flow IR.
Here is a snippet from DMR's explanation of how registers were 
allocated - it sounds similar to what Walter described.

     Each expression tree, as it is read in, is subjected to a 
fairly comprehensive analysis. This is performed by the optim 
routine and a number of subroutines; the major things done are

     Modifications and simplifications of the tree so its value 
may be computed more efficiently and conveniently by the code 
generator.

     Marking each interior node with an estimate of the number of 
registers required to evaluate it. This register count is needed 
to guide the code generation algorithm.

     The basic organization is simple: a depth-first scan of the 
tree.
Sep 20
parent Walter Bright <newshound2 digitalmars.com> writes:
On 9/20/2024 12:17 PM, Dibyendu Majumdar wrote:

 It seems to me that Walter may have based his original implementation on the C 
 compiler by Dennis Ritchie.


That would be pure coincidence because I have never seen the code for Ritchie's 
implementation. Or maybe great minds think alike :-)

But I did carefully read the Pascal compiler source code printed in BYTE 
magazine in the 1970's.



      The basic organization is simple: a depth-first scan of the tree.


That's how the Tiny Pascal compiler worked, how D's CTFE works, how my 
Javascript implementation worked, etc.
Sep 22
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/18/2024 5:34 AM, Dibyendu Majumdar wrote:

 I watched the talk on D backend; I thought it could have been very interesting 
 but actually was very scant in details.


Can't really do a deep dive on what should be a semester-length course in 40 
minutes. I was hoping to simply provide a roadmap to where in the code
generator 
the important things were done, as otherwise it's just a confusing mass of code.



 Just because expressions are in a tree, how does it make the backend SSA? It 
 wasn't clear if the D backend uses virtual registers, and if these can be 
 assigned only once. If that is the case then are their Phi instructions?


It's like SSA in that the elem node is "assigned" a single value that never
changes.



 The register allocator description also did not really explain how it works. 
 There was mention of coloring - was that a reference to graph coloring?


I don't know if it's exactly like graph coloring, but it's about preparing bit 
vectors of register use and the live range of variable (also expressed as a bit 
vector), and mapping a register onto 0's in a register's bit vector.



 It seems that there is a lot of potential for Walter to do deep dive video 
 recordings on the backend, where each topic is fully explored / explained.


I've already been asked to do one on the AArch64 implementation!
Sep 22
next sibling parent reply claptrap <clap trap.com> writes:
On Sunday, 22 September 2024 at 08:35:14 UTC, Walter Bright wrote:

 On 9/18/2024 5:34 AM, Dibyendu Majumdar wrote:

 I watched the talk on D backend; I thought it could have been 
 very interesting but actually was very scant in details.


 Can't really do a deep dive on what should be a semester-length 
 course in 40 minutes. I was hoping to simply provide a roadmap 
 to where in the code generator the important things were done, 
 as otherwise it's just a confusing mass of code.



 Just because expressions are in a tree, how does it make the 
 backend SSA? It wasn't clear if the D backend uses virtual 
 registers, and if these can be assigned only once. If that is 
 the case then are their Phi instructions?


 It's like SSA in that the elem node is "assigned" a single 
 value that never changes.


Can more than one elem reference the same (lvalue) variable? Eg..

int x = 100;
x = x+1;
x = y+1;

That's three different elem, but do they all have the same 'x' as 
their target?
Sep 22
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/22/2024 3:55 AM, claptrap wrote:

 Can more than one elem reference the same (lvalue) variable? Eg..
 
 int x = 100;
 x = x+1;
 x = y+1;


Yes.


 That's three different elem, but do they all have the same 'x' as their target?


The single assignment refers to the value of the elem tree node, not the value 
of the variables.
Sep 22
parent reply claptrap <clap trap.com> writes:
On Monday, 23 September 2024 at 05:36:18 UTC, Walter Bright wrote:

 On 9/22/2024 3:55 AM, claptrap wrote:

 Can more than one elem reference the same (lvalue) variable? 
 Eg..
 
 int x = 100;
 x = x+1;
 x = y+1;


 Yes.


 That's three different elem, but do they all have the same 'x' 
 as their target?


 The single assignment refers to the value of the elem tree 
 node, not the value of the variables.


Then it's not SSA, the whole point of SSA is that **variables** 
are only ever assigned once. So it'd be like...

int x0 = 100;
x1 = x0+1;
x2 = y1+1;

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.
Sep 23
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Sep 23
next sibling parent reply claptrap <clap trap.com> writes:
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?
Sep 23
next sibling parent reply user1234 <user1234 12.de> writes:
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.)

<!--
(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 "%"

-->
Sep 23
parent reply claptrap <clap trap.com> writes:
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
Sep 23
parent reply user1234 <user1234 12.de> writes:
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".
Sep 23
parent reply claptrap <clap trap.com> writes:
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.
Sep 23
next sibling parent reply user1234 <user1234 12.de> writes:
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
```

2. %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
```

3. 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".
Sep 23
parent reply claptrap <clap trap.com> writes:
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.
Sep 23
parent reply user1234 <user1234 12.de> writes:
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.
Sep 23
parent reply claptrap <clap trap.com> writes:
On Monday, 23 September 2024 at 18:05:34 UTC, user1234 wrote:

 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.


You have source code, with variables, each time you assign to a 
variable it gets a new name, x ==> x0,x1,x2...

Those assignments become "nodes" in the SSA IR, for LLVM 
x0,x1,x2.. become %3,%7,%8 or whatever, so yes those nodes 
represent the variable 'x' at that point in the program.

Yes you have other nodes that don't directly represent variables 
in the source code, but they do represent temporaries in the 
evaluation of expressions. So if you rejig the original source so 
it has one operation per statement, a more complex expression 
would require you to give names to the temporaries, those also 
become nodes. So they are temporary variables!

But then Im also not sure if its just the use of "variable" for 
something that never changes that bothers you, in the same way 
"immutable variable" makes no sense?
Sep 23
parent reply user1234 <user1234 12.de> writes:
On Monday, 23 September 2024 at 19:47:52 UTC, claptrap wrote:

 On Monday, 23 September 2024 at 18:05:34 UTC, user1234 wrote:

 [...]


 You have source code, with variables, each time you assign to a 
 variable it gets a new name, x ==> x0,x1,x2...

 [...]


Call IR nodes "variables" if you like spreading confusion.
Sep 23
parent reply claptrap <clap trap.com> writes:
On Monday, 23 September 2024 at 22:51:47 UTC, user1234 wrote:

 On Monday, 23 September 2024 at 19:47:52 UTC, claptrap wrote:

 On Monday, 23 September 2024 at 18:05:34 UTC, user1234 wrote:

 [...]


 You have source code, with variables, each time you assign to 
 a variable it gets a new name, x ==> x0,x1,x2...

 [...]


 Call IR nodes "variables" if you like spreading confusion.


Never seen anyone else call them "nodes" tbh, i'm just using that 
terminology to try and communicate with you. The LLVM docs calls 
them instructions for example, so yeah technically an instruction 
that has a result, and that result represents the *value" of the 
variable at that point.

I mean SSA is always presented as a sequence of instructions, not 
a tree, so I dont even get why you call them nodes anyway.

*shrug*
Sep 23
parent reply user1234 <user1234 12.de> writes:
On Tuesday, 24 September 2024 at 00:08:03 UTC, claptrap wrote:

 On Monday, 23 September 2024 at 22:51:47 UTC, user1234 wrote:

 On Monday, 23 September 2024 at 19:47:52 UTC, claptrap wrote:

 [...]


 Call IR nodes "variables" if you like spreading confusion.


 Never seen anyone else call them "nodes" tbh, i'm just using 
 that terminology to try and communicate with you. The LLVM docs 
 calls them instructions for example, so yeah technically an 
 instruction that has a result, and that result represents the 
 *value" of the variable at that point.

 I mean SSA is always presented as a sequence of instructions, 
 not a tree, so I dont even get why you call them nodes anyway.

 *shrug*


You're a factor of exhaustion.
Sep 23
parent claptrap <clap trap.com> writes:
On Tuesday, 24 September 2024 at 06:56:28 UTC, user1234 wrote:

 On Tuesday, 24 September 2024 at 00:08:03 UTC, claptrap wrote:

 On Monday, 23 September 2024 at 22:51:47 UTC, user1234 wrote:

 On Monday, 23 September 2024 at 19:47:52 UTC, claptrap wrote:

 [...]


 Call IR nodes "variables" if you like spreading confusion.


 Never seen anyone else call them "nodes" tbh, i'm just using 
 that terminology to try and communicate with you. The LLVM 
 docs calls them instructions for example, so yeah technically 
 an instruction that has a result, and that result represents 
 the *value" of the variable at that point.

 I mean SSA is always presented as a sequence of instructions, 
 not a tree, so I dont even get why you call them nodes anyway.

 *shrug*


 You're a factor of exhaustion.


Don't shoot the messenger. :)
Sep 24
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/23/2024 6:39 AM, claptrap wrote:

 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.


The working out is "dead assignment elimination" which is another DFA that DMD
does.
Sep 25
parent reply claptrap <clap trap.com> writes:
On Wednesday, 25 September 2024 at 11:44:22 UTC, Walter Bright 
wrote:

 On 9/23/2024 6:39 AM, claptrap wrote:

 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.


 The working out is "dead assignment elimination" which is 
 another DFA that DMD does.


Is that different from the DCE that you linked the source code to 
earlier? I mean dead code elimination, and dead assignment 
elimination are different routines in DMD?

Maybe my question wasn't clear but I was asking how it is done, 
not what is it called. IE.. if you have 3 assignments to X, how 
determine if any of them are redundant?
Sep 25
next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 25 September 2024 at 19:31:52 UTC, claptrap wrote:

 On Wednesday, 25 September 2024 at 11:44:22 UTC, Walter Bright 
 wrote:

 On 9/23/2024 6:39 AM, claptrap wrote:

 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.


 The working out is "dead assignment elimination" which is 
 another DFA that DMD does.


 Is that different from the DCE that you linked the source code 
 to earlier? I mean dead code elimination, and dead assignment 
 elimination are different routines in DMD?

 Maybe my question wasn't clear but I was asking how it is done, 
 not what is it called. IE.. if you have 3 assignments to X, how 
 determine if any of them are redundant?


You look if there is a write to X without a (live) use of X 
beforehand.
whether that can eliminate the x += 1 in
x += 1
x = y.

is up to the quality of implementation.
I should note that data flow analysis is necessary to produce 
good ssa in the first place.
naive SSA leads to a horribly bloated IR. Which is why it's not a 
first choice, if memory is limited.
Sep 25
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
When dead assignments are eliminated, the rvalue expression no longer serves a 
purpose and is eliminated. This process repeats until no more optimizations can 
be done.
Sep 26
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/23/2024 2:43 AM, claptrap wrote:

 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?


By using DFA (Data Flow Analysis).

https://github.com/dlang/dmd/blob/master/compiler/src/dmd/backend/gother.d#L1375

DMD does do all the conventional data flow analysis optimizations.
Sep 23
parent reply Dibyendu Majumdar <mobile majumdar.org.uk> writes:
On Tuesday, 24 September 2024 at 06:14:52 UTC, Walter Bright 
wrote:

 On 9/23/2024 2:43 AM, claptrap wrote:

 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?


 By using DFA (Data Flow Analysis).

 https://github.com/dlang/dmd/blob/master/compiler/src/dmd/backend/gother.d#L1375

 DMD does do all the conventional data flow analysis 
 optimizations.


Yes well, SSA is supposed to make it easier to do some 
optimizations, but all optimizations are possible without SSA - 
using data flow analysis, etc.

But the description provided so far does not show DMD compiler 
uses SSA.
Sep 24
next sibling parent claptrap <clap trap.com> writes:
On Tuesday, 24 September 2024 at 22:20:31 UTC, Dibyendu Majumdar 
wrote:

 On Tuesday, 24 September 2024 at 06:14:52 UTC, Walter Bright


 Yes well, SSA is supposed to make it easier to do some 
 optimizations, but all optimizations are possible without SSA - 
 using data flow analysis, etc.

 But the description provided so far does not show DMD compiler 
 uses SSA.


It clearly doesn't use SSA, it happens to generate some sequences 
of temporaries that are SSA, but probably every compiler does 
that. Its like a fence with only half the panels installed, is it 
still a fence? Maybe, does it actual do what it's supposed to? 
Nope.
Sep 24
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/24/2024 3:20 PM, Dibyendu Majumdar wrote:

 But the description provided so far does not show DMD compiler uses SSA.


And it doesn't. It uses binary trees, which are very much like SSA.
Sep 25
next sibling parent Dibyendu Majumdar <mobile majumdar.org.uk> writes:
On Wednesday, 25 September 2024 at 11:41:59 UTC, Walter Bright 
wrote:

 On 9/24/2024 3:20 PM, Dibyendu Majumdar wrote:

 But the description provided so far does not show DMD compiler 
 uses SSA.


 And it doesn't. It uses binary trees, which are very much like 
 SSA.


The problem is they are not ... so its confusing for people if 
you make such a claim.
Sep 25
prev sibling parent reply claptrap <clap trap.com> writes:
On Wednesday, 25 September 2024 at 11:41:59 UTC, Walter Bright 
wrote:

 On 9/24/2024 3:20 PM, Dibyendu Majumdar wrote:

 But the description provided so far does not show DMD compiler 
 uses SSA.


 And it doesn't. It uses binary trees, which are very much like 
 SSA.


If multiple nodes in the tree can point to the same shared state, 
IE variables, then it's not actually like SSA. In the same way a 
function where the most of the instructions dont access global 
state isnt like a pure function because most of it is pure.
Sep 25
parent Walter Bright <newshound2 digitalmars.com> writes:
On 9/25/2024 12:31 PM, claptrap wrote:

 If multiple nodes in the tree can point to the same shared state, IE
variables, 
 then it's not actually like SSA.


They don't.

Only after all other DFA is complete does the compiler do common
subexpressions, 
and the common subexpressions create trees with multiple parents.
Sep 26
prev sibling next sibling parent reply Dibyendu Majumdar <mobile majumdar.org.uk> writes:
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;
```
Sep 23
parent reply Dibyendu Majumdar <mobile majumdar.org.uk> writes:
On Monday, 23 September 2024 at 16:57:47 UTC, Dibyendu Majumdar 
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.


 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;
 ```


If the IR is SSA then it needs to output something like this:

```
int x = foo();
if (x == 1)
    x1 = 5;
else
    x2 = 6;
x3 = phi(x1,x2)
```
Sep 23
parent reply Walter Bright <newshound2 digitalmars.com> writes:
```
x = x + 6
```

```
r1 = x
r2 = 6
r3 = r1 + r2
x = r3
```

The r's are only assigned once.
Sep 23
next sibling parent reply claptrap <clap trap.com> writes:
On Tuesday, 24 September 2024 at 06:23:24 UTC, Walter Bright 
wrote:

 ```
 x = x + 6
 ```

 ```
 r1 = x
 r2 = 6
 r3 = r1 + r2
 x = r3
 ```

 The r's are only assigned once.


Doesn't that just come implicitly from them being temporaries?

For SSA the x's would have to be assigned only once, so the last 
line "x=r3", x would be renamed there.
Sep 24
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 9/24/2024 12:47 AM, claptrap wrote:

 Doesn't that just come implicitly from them being temporaries?


Yes, exactly.
Sep 24
parent reply claptrap <clap trap.com> writes:
On Tuesday, 24 September 2024 at 09:42:25 UTC, Walter Bright 
wrote:

 On 9/24/2024 12:47 AM, claptrap wrote:

 Doesn't that just come implicitly from them being temporaries?


 Yes, exactly.


```
x = x + 1
x = y + 1
```

So if you have that, how do you determine that the first 
assignment to 'x' is redundant?
Sep 24
parent Walter Bright <newshound2 digitalmars.com> writes:
On 9/24/2024 10:52 AM, claptrap wrote:

 So if you have that, how do you determine that the first assignment to 'x' is 
 redundant?


I posted a link to rmdeadass().
Sep 26
prev sibling parent reply Dibyendu Majumdar <mobile majumdar.org.uk> writes:
On Tuesday, 24 September 2024 at 06:23:24 UTC, Walter Bright 
wrote:

 ```
 x = x + 6
 ```

 ```
 r1 = x
 r2 = 6
 r3 = r1 + r2
 x = r3
 ```

 The r's are only assigned once.


You did not quite answer my question - how is the example snippet 
translated?

Also what is the value of x above? Clearly x is assigned to more 
than once - first assignment is not shown, so this is not SSA.
Sep 24
parent Walter Bright <newshound2 digitalmars.com> writes:
On 9/24/2024 3:11 PM, Dibyendu Majumdar wrote:

 On Tuesday, 24 September 2024 at 06:23:24 UTC, Walter Bright wrote:

 ```
 x = x + 6
 ```

 ```
 r1 = x
 r2 = 6
 r3 = r1 + r2
 x = r3
 ```

 The r's are only assigned once.


 
 You did not quite answer my question - how is the example snippet translated?


I don't understand what you're asking for.



 Also what is the value of x above? Clearly x is assigned to more than once - 
 first assignment is not shown, so this is not SSA.


I said it was like SSA in that the nodes are assigned only once.
Sep 26
prev sibling parent reply Bruce Carneal <bcarneal gmail.com> writes:
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.


Here are some musings from Grok given this prompt:

What are the pros and cons of employing an SSA architecture in a 
compiler back end?  What does SSA enable that alternative 
approaches do not?

https://x.com/i/grok/share/cQC4v0ZFIHoRbSAV4D9Gz98eV

In answering the question: "What, if anything, has superseded 
SSA?" Grok has:

https://x.com/i/grok/share/FTF6QzKzqF0nxQ3wrPo48oEoE

I've not detected any hallucinations in these but I've been out 
of the compiler biz a long time and didn't dig into the responses.

FWIW, my opinion is that SSA provides a lot stronger framework to 
build upon going forward.  Better optimization possibilities 
certainly but also a better ecosystem.

Corrections, additions, opinions all welcome of course.
Sep 23
parent Walter Bright <newshound2 digitalmars.com> writes:
Thanks for the links.

I've been able to do these things with the binary tree version.
Sep 23
prev sibling parent reply Patriciabin <patriciabinita543 gmail.com> writes:
Two questions: Just because expressions are in a tree, how does 
it make the backend SSA? It wasn't clear if the D backend uses 
virtual registers ... Ah, the obligatory comment from Walter 
Bright talking about D in posts about Zig. Nothing wrong with it, 
just a bit funny how predictable ...Today, Let's discuss how to 
tackle a business problem while working as a data analyst. -- 
Outline the problem that the company is facing.

https://spacebarcounter.org/spacebarclicker
Oct 07
parent Walter Bright <newshound2 digitalmars.com> writes:
On 10/7/2024 11:15 PM, Patriciabin wrote:

 Ah, the obligatory comment from Walter Bright talking about D in posts about
Zig. 


It's hard to find an HN topic about D that doesn't include posts about Zig and
Rust.

You're right that there's nothing wrong with it.
Oct 09
prev sibling parent reply Dibyendu Majumdar <mobile majumdar.org.uk> writes:
On Sunday, 22 September 2024 at 08:35:14 UTC, Walter Bright wrote:

 On 9/18/2024 5:34 AM, Dibyendu Majumdar wrote:


 The register allocator description also did not really explain 
 how it works. There was mention of coloring - was that a 
 reference to graph coloring?


 I don't know if it's exactly like graph coloring, but it's 
 about preparing bit vectors of register use and the live range 
 of variable (also expressed as a bit vector), and mapping a 
 register onto 0's in a register's bit vector.


Given the description of the expression tree - does the register 
allocator work globally across the whole method/function or just 
on each expression tree?
Sep 25
parent Walter Bright <newshound2 digitalmars.com> writes:
On 9/25/2024 1:18 AM, Dibyendu Majumdar wrote:

 Given the description of the expression tree - does the register allocator
work 
 globally across the whole method/function or just on each expression tree?


It works on the basic blocks.

I did an experiment increasing the granularity to the expression level, but the 
results were disappointing and I went back to the basic block level.
Sep 26
prev sibling parent reply Greg Gritton <GregNada gmail.com> writes:
On Wednesday, 18 September 2024 at 12:34:29 UTC, Dibyendu 
Majumdar wrote:

 Hi,

 I watched the talk on D backend; I thought it could have been 
 very interesting but actually was very scant in details.


Where is the talk on the D backend?
Oct 01
parent Salih Dincer <salihdb hotmail.com> writes:
On Wednesday, 2 October 2024 at 03:18:38 UTC, Greg Gritton wrote:

 On Wednesday, 18 September 2024 at 12:34:29 UTC, Dibyendu 
 Majumdar wrote:

 Hi,

 I watched the talk on D backend; I thought it could have been 
 very interesting but actually was very scant in details.


 Where is the talk on the D backend?


https://www.youtube.com/live/FKI9M-KRjvA?si=D3cLc3dqu9wVNKuG
The first speech is already on the 1st day of DConf'24...

SDB 79
Oct 09