COMPILERS MUTHERFUCKER

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > COMPILERS MUTHERFUCKER

what is best in optimizer pipeline
	value numbering
	code motion
	peepholing
	loop idiom recognition
	legalization
	thread gassing
	op banning

Malcolm XML: Aug 8, 2009; I always knew it would end like ｔｈｉｓ．

https://fun.irq.dk/funroll-loops.org/

# ¿ Jun 27, 2017 22:28

Adbot: ADBOT LOVES YOU

# ¿ May 1, 2024 22:13

Malcolm XML: Aug 8, 2009; I always knew it would end like ｔｈｉｓ．

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)

CPS >> SSA

# ¿ Jun 28, 2017 10:08

Malcolm XML: Aug 8, 2009; I always knew it would end like ｔｈｉｓ．

rjmccall posted:

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

yeah but equivalent doesn't mean better than

continuations for life

# ¿ Jun 28, 2017 20:46

Malcolm XML: Aug 8, 2009; I always knew it would end like ｔｈｉｓ．

rjmccall posted:

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

but that paper is cool

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/join-points-pldi17.pdf

# ¿ Jun 28, 2017 20:47

Malcolm XML: Aug 8, 2009; I always knew it would end like ｔｈｉｓ．

peep my neg hole

# ¿ Jun 28, 2017 21:19

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > COMPILERS MUTHERFUCKER