Getting rid of phi instructions?

Hi all,

is there a pass to get rid of phi-instructions in a function? There's no loop involved.

I have a function approx. like this:

void @func() {
entry:
  …
bb1:
  …
bb2:
  …
  %tmp100 = phi i32 [ 0, bb1 ], [ 1, bb2 ] …
  %tmp101 = getelementptr …, %tmp100
  tail call void @anotherfunc(…, %tmp101)
  ret void
}

I would like it to rather be something like this:

void @func() {
entry:
  …
bb1:
  ...
  %tmp90 = getelementptr …, %tmp89
  tail call void @anotherfunc(%tmp90)
  ret void
bb2:
  …
  %tmp101 = getelementptr …, %tmp100
  tail call void @anotherfunc(%tmp101)
  ret void
}

Best regards,
Teemu

Hi all,

is there a pass to get rid of phi-instructions in a function? There's no loop involved.

reg2mem.

I have a function approx. like this:

void @func() {
entry:

bb1:

bb2:

%tmp100 = phi i32 [ 0, bb1 ], [ 1, bb2 ] …
%tmp101 = getelementptr …, %tmp100
tail call void @anotherfunc(…, %tmp101)
ret void
}

I would like it to rather be something like this:

void @func() {
entry:

bb1:
...
%tmp90 = getelementptr …, %tmp89
tail call void @anotherfunc(%tmp90)
ret void
bb2:

%tmp101 = getelementptr …, %tmp100
tail call void @anotherfunc(%tmp101)
ret void
}

reg2mem won't do quite this transformation... not sure exactly what you need.

-Eli

I need to get rid of phis. This code is compiled from C++ and for some functions
there are no phis, but multiple call instructions. I am targeting hardware
in the end, and the next tool reading the IR does not like phis when it's generating VHDL.
My questions may be somewhat silly from the viewpoint of software compilation for a CPU.

Thanks.

Teemu

Mmm... reg2mem will transform IR with PHI's into IR without them, but
it generates a bunch of alloca's, which I would assume are not cheap
to lower to VHDL. You might have to write your own pass to get the
precise transformation you're looking for.

-Eli

Right. Thanks. I need to see the reg2mem source code.

Teemu

lib/Transforms/Scalar/Reg2Mem.cpp in the LLVM source tree.

-Eli

For what it's worth, mem2reg will *not* remove all phi's (see note in
top of the file mentioned above). Something to keep in mind, if you
absolutely need no phi's at all. Writing the transform to finish the
job is a bit more work, which I believe is why it's not already done
in the existing mem2reg.

Just FYI :slight_smile:

~Will

the next tool reading the IR does not like phis when it's generating VHDL.

If you're doing a conversion from LLVM IR to some other non-SSA IR
(like the tool's), you can do the phi node removal yourself as you
convert. Basically, every predecessor block referenced by a phi node
will have an assignment to that variable before branching. There are
techniques to make the resultant code more efficient, see Cytron et
al.[1].

[1] "Efficiently computing static single assignment form and the
control dependence graph"
http://www.eecs.umich.edu/~mahlke/583w03/reading/cytron_toplas_91.pdf

the next tool reading the IR does not like phis when it's generating VHDL.

If you're doing a conversion from LLVM IR to some other non-SSA IR
(like the tool's), you can do the phi node removal yourself as you
convert. Basically, every predecessor block referenced by a phi node
will have an assignment to that variable before branching. There are
techniques to make the resultant code more efficient, see Cytron et
al.[1].

[1] "Efficiently computing static single assignment form and the
control dependence graph"
http://www.eecs.umich.edu/~mahlke/583w03/reading/cytron_toplas_91.pdf

The idea in [1] does not work for all cases. There are two problems
1) consider the code
l1:
    x1 = 1
    br l2
l2 :
    x = phi [l1 x1] [l2 x2]
    x2 = x + 1
    br false l1 l3
l3 :
    print x

Because x1 and x2's liveness range are conflicting, the following
out-of-SSA is not correct.

l1:
    x1 = 1
    x = x1
    br l2
l2 :
    x2 = x + 1
    x = x2
    br false l1 l3
l3 :
    print x

Since x = x2 kills the x = x1

2) the other problem is that all phinodes need to be update atomically,
l:
  x = 1
  y = 0
  br l'
l':
y = phi [l x] [l' x]
x = phi [l y ] [l' y]
br l

So, we may need more temporaries to break the interference. Here are
some work on fixing the issues

Practical improvements to the construction and destruction of static
single assignment form
  http://www.citeulike.org/user/JianzhouZhao/article/2755291
Translating out of static single assignment form
  http://www.citeulike.org/user/JianzhouZhao/article/7350004