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!

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.

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?

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.

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.