where are my phi-nodes?

Hi,

I am interested in SSA and read llvm uses SSA in its ir. I decided to write a simple program and compile it with llvm to the human readable assembly language representation of the ir. I expected phi nodes all over the place. However, I could not find a single one! Could you tell my why that is so?

I compiled with “llvm-gcc -emit-llvm test.c -S -o test.ll”. Attached to this message are the source and the resulting ll output.

Thanks in advance,

Maarten Faddegon

test.c (143 Bytes)

test.ll (2.64 KB)

They have been converted into stores. If you want PHI nodes to appear,
try running the "mem2reg" pass with "opt -mem2reg test.ll -S".

Hi Maarten,

I compiled with "llvm-gcc -emit-llvm test.c -S -o test.ll". Attached to this
message are the source and the resulting ll output.

compile with optimization. The llvm-gcc front-end "cheats" and stores/loads all
values to/from memory, avoiding the need to construct phi nodes; instead it lets
the optimizers do that. For what it's worth the dragonegg plugin produces phi
nodes directly, even at -O0. I don't know what clang does.

Ciao,

Duncan.

If you're talking about variables, clang emits stores and loads, of course. C/C++
variables specify their semantics in terms of objects in memory; SSA conversion
is an optimization which does break (obviously invalid) programs. Any attempt
by the frontend to emit variables in true SSA form is just duplicating this
optimization — in the case of dragonegg, because the SSA conversion is
implicit in how gcc creates the IR it lowers from.

John.

I compiled with "llvm-gcc -emit-llvm test.c -S -o test.ll". Attached to this
message are the source and the resulting ll output.

compile with optimization. The llvm-gcc front-end "cheats" and stores/loads all
values to/from memory, avoiding the need to construct phi nodes; instead it lets
the optimizers do that. For what it's worth the dragonegg plugin produces phi
nodes directly, even at -O0. I don't know what clang does.

If you're talking about variables, clang emits stores and loads, of course. C/C++
variables specify their semantics in terms of objects in memory; SSA conversion
is an optimization which does break (obviously invalid) programs. Any attempt
by the frontend to emit variables in true SSA form is just duplicating this
optimization — in the case of dragonegg, because the SSA conversion is
implicit in how gcc creates the IR it lowers from.

Makes sense. However, grep'ing on CreatePHI in clang's CodeGen module I see several
places where clang's 'front-end' is doing this. What is the rational for that?

- Fariborz

We do emit phis when the semantics aren't defined in terms of memory,
e.g. with expressions that have multiple paths of control flow (like the
conditional operator or null-checked derived-to-base conversions).

John.

We do emit phis when the semantics aren't defined in terms of memory,
e.g. with expressions that have multiple paths of control flow (like the
conditional operator or null-checked derived-to-base conversions).

But at least for conditional operator, there are labels, conditionals and branches.
Optimizer should be able to build the phi nodes from control flow. I don't know
why not. But I am sure there is good reason for it being in the fe. (maybe it makes
optimizer's work easier).

- fariborz

Making phis explicitly in these cases does remove a small amount of work from
the optimizer, and it produces slightly better code at -O0, but mostly it's just
convenient. Emitting an alloca with associated loads and stores would actually
be less obvious.

John.

FWIW, the fast register allocator is going to undo any -O0 performance win from phi nodes.
It spills and reloads all registers that are live across blocks.
Phi nodes are no worse than going through an alloca, though.

/jakob