Menu
Search

Forums

Forum Index

September 23
Gravatar of Dibyendu MajumdarPosted by Dibyendu Majumdar
in reply to Dibyendu Majumdar		Reply
Dibyendu Majumdar
Gravatar of Dibyendu Majumdar
Posted in reply to Dibyendu Majumdar


Reply

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)
September 23
Gravatar of claptrapPosted by claptrap
in reply to user1234		Reply
claptrap
Gravatar of claptrap
Posted in reply to user1234


Reply

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?

September 23
Gravatar of Bruce CarnealPosted by Bruce Carneal
in reply to Walter Bright		Reply
Bruce Carneal
Gravatar of Bruce Carneal
Posted in reply to Walter Bright


Reply

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.

September 23
Gravatar of user1234Posted by user1234
in reply to claptrap		Reply
user1234
Gravatar of user1234
Posted in reply to claptrap


Reply

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.

September 24
Gravatar of claptrapPosted by claptrap
in reply to user1234		Reply
claptrap
Gravatar of claptrap
Posted in reply to user1234


Reply

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

September 23
Gravatar of Walter BrightPosted by Walter Bright
in reply to Bruce Carneal		Reply
Walter Bright
Gravatar of Walter Bright
Posted in reply to Bruce Carneal


Reply
Thanks for the links.

I've been able to do these things with the binary tree version.
September 23
Gravatar of Walter BrightPosted by Walter Bright
in reply to claptrap		Reply
Walter Bright
Gravatar of Walter Bright
Posted in reply to claptrap


Reply
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.
September 23
Gravatar of Walter BrightPosted by Walter Bright
in reply to Dibyendu Majumdar		Reply
Walter Bright
Gravatar of Walter Bright
Posted in reply to Dibyendu Majumdar


Reply
```
x = x + 6
```

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

The r's are only assigned once.
September 24
Gravatar of user1234Posted by user1234
in reply to claptrap		Reply
user1234
Gravatar of user1234
Posted in reply to claptrap


Reply

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.

September 24
Gravatar of claptrapPosted by claptrap
in reply to user1234		Reply
claptrap
Gravatar of claptrap
Posted in reply to user1234


Reply

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

« First   ‹ Prev
1 2 3 4 5 6
Next ›   Last »