Shinku ABOOKEN posted:

what are phi nodes? why are they bad?

rjmccall posted:

...

redleader posted:

good thread op

why can't c/c++ compilers emit warnings when they encounter undefined behaviour? is it just that it's too hard to fit into current compiler architecture? would it be a useless thing to include because every program would be filled with undefined behavior?

rjmccall posted:

it's the dominant way of handling data flow when control flow merges in ssa

here's a dumb c program

C code:

int x;
if (whatever) {
  x = foo();
} else {
  x = bar();
}
baz(x);

in a more explicit representation that isn't yet in proper ssa form, this looks like:

code:

  if %whatever goto trueBlock else goto falseBlock
trueBlock:
  %fooResult = call @foo()
  store %fooResult to %x
  goto contBlock
falseBlock:
  %barResult = call @bar()
  store %barResult to %x
  goto contBlock
contBlock:
  %mergedValue = load %x
  call @baz(%mergedValue)

the purpose of ssa is to make this data flow explicit, i.e. we don't want to see this opaque load from a variable, we want to see the last value stored there. in a lot of cases, that's easy enough to do, but how do we talk about it after this kind of control-flow merge, where the value is different based on where we came from?

phi nodes are the dominant answer. a phi node is a sort of pseudo-instruction you can put at the start of a block when it has multiple predecessors like this, and it basically says what the value is when coming from all the predecessors:

code:

  if %whatever goto trueBlock else goto falseBlock
trueBlock:
  %fooResult = call @foo()
  goto contBlock
falseBlock:
  %barResult = call @bar()
  goto contBlock
contBlock:
  %mergedValue = phi %fooResult from trueBlock, %barResult from falseBlock
  call @baz(%mergedValue)

they suck because they're a weird orthogonal special case. they look like instructions, but they can only go at the start of a block, and the values they use are not normally valid to reference in the block. if you were writing some optimization involving calls to @foo, and you wanted to insert code everywhere the return value is used, you can't add it here; you have to recognize that the use is a phi node and put the code at the end of trueBlock instead

the way better alternative is to say that basic blocks can have parameters and gotos can have arguments, which ends up looking kindof like a functional program with a lot of explicit tail calls:

code:

  if %whatever goto trueBlock else goto falseBlock
trueBlock:
  %fooResult = call @foo()
  goto contBlock(%fooResult)
falseBlock:
  %barResult = call @bar()
  goto contBlock(%barResult)
contBlock(%mergedValue):
  call @baz(%mergedValue)

Jabor posted:

For example, it would not be useful if the compiler threw a "potentially undefined behavior" warning any time you did arithmetic on a signed value.

Malcolm XML posted:

CPS >> SSA

redleader posted:

oh yeah, that's right

related (but possibly a little off topic) question: what's up with the c/c++ standards committees that makes them prefer undefined over implementation-defined behavior? i mean surely most compilers would know their target's behavior with (un)signed overflow (for example)

Captain Foo posted:

compilers are black magic to me op

Phobeste posted:

how long before the embedded world gets first class cortex m-4 and subsequent support for building from llvm. also how long until i can stop having to loving compile cross compilers. these questions are probably linked

Cocoa Crispies posted:

write one to disabuse yourself of that notion

Phobeste posted:

how long before the embedded world gets first class cortex m-4 and subsequent support for building from llvm. also how long until i can stop having to loving compile cross compilers. these questions are probably linked

rjmccall posted:

having a jit enables some really neat dynamic code generation and specialization tricks. i'd love to see more language implementations based on a sane language + execution environment that really take intelligent advantage of both static and dynamic information

instead it feels like jits always spend the bulk of their effort (both in development and at runtime) working around stupidity in the language / runtime model. "i couldn't possibly statically inline this trivial getter, it's in a different class file"

redleader posted:

related (but possibly a little off topic) question: what's up with the c/c++ standards committees that makes them prefer undefined over implementation-defined behavior? i mean surely most compilers would know their target's behavior with (un)signed overflow (for example)

Malcolm XML posted:

CPS >> SSA

Deep Dish Fuckfest posted:

how good is modern jitted code compared to what's emitted by a traditional toolchain these days anyway? i've heard about the ability to use info you don't have at compile time to potentially produce better code before, but i have no idea how much of a difference it makes in practice. or any idea what traditional optimizations aren't possible when you're jitting, if any

rjmccall posted:

you should read the spj paper linked from the tweet in the op

rjmccall posted:

you should read the spj paper linked from the tweet in the op

MALE SHOEGAZE posted:

i'm currently writing a toy language interpreter in rust and once im done with that i might try doing a lisp or maybe take a crack at writing a bad c compiler

rjmccall posted:

Malcolm XML posted:

yeah but equivalent doesn't mean better than

continuations for life

JewKiller 3000 posted:

you didn't answer my hard question so here's another easy one: to compile a compiler, do you need a compiler compiler? if so, how do you compile the compiler compiler?

JewKiller 3000 posted:

you didn't answer my hard question so here's another easy one: to compile a compiler, do you need a compiler compiler? if so, how do you compile the compiler compiler?

JewKiller 3000 posted:

you didn't answer my hard question so here's another easy one: to compile a compiler, do you need a compiler compiler? if so, how do you compile the compiler compiler?

RISCy Business posted:

who delivers the mailman's mail

JewKiller 3000 posted:

you didn't answer my hard question so here's another easy one: to compile a compiler, do you need a compiler compiler? if so, how do you compile the compiler compiler?