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 
~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