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.

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?

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.

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.

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.

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().

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.

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.