Misha Brukman wrote:> LLVM Machine code is in SSA.This explains quite a lot. I though it's possible to just reduce convert phis into copy instructions in predecessors -- all of which will have the same destination register.> gets you two definitions of r. So we have machine PHI nodes merge the > two possible values into one for result of r. These phis get removed > after register allocation. So you would write code like: > > if (a cond b) then > r1 = 1 > else > r2 = 0 > > r = phi(r1, r2)Ok, I see.> > The reason I'm asking is that I try to support 64-bit comparison and I do > > it by generating code like: > > > > // if high1 cond high2: goto operand0 > > // if high1 reverse_cond high2: goto operand1 > > the second if should just be an unconditional branch to operand1: > clearly, if (high1 cond high2) is false, the reverse condition is true.Actually, you've found a bug: it should be swapped_cond, not reverse_cond.> > but this means that operand0 and operand1 (the successor basic blocks) > > suddenly get more predecessor than recorded in phi nodes, and > > LiveVariables.cpp asserts on that. > > Naturally, as PHI nodes need to have as many entries as there are > predecessors.Ehmm... this means the 'SelectPHINodes' function I've copy-pasted from X86 backend needs more work... gotta do that now. - Volodya
On Fri, 9 Jul 2004, Vladimir Prus wrote:> Misha Brukman wrote: > > > LLVM Machine code is in SSA. > > This explains quite a lot. I though it's possible to just reduce convert phis > into copy instructions in predecessors -- all of which will have the same > destination register.There are algorithms for eliminating PHI nodes, but they aren't quite so simple. Consider what happens when you have phi nodes in a block like this: Loop: A = phi (B, Loop), (0, OutOfLoop) B = phi (A, Loop), (1, OutOfLoop) ... br Loop No matter how you insert copies in the predecessors, you can't maintain the semantics of the phis (which are simultaneous assignment). This is obviously possible to handle, it's just not entirely trivial. FWIW, this is known as the "swap problem". More importantly, SSA is useful for the code generator. It makes live variable analysis almost trivial for example, and is a natural representation to use for other reasons: you have to have an infinite # of regs before register allocation, why not make them SSA? -Chris -- http://llvm.cs.uiuc.edu/ http://www.nondot.org/~sabre/Projects/
Chris Lattner wrote:> On Fri, 9 Jul 2004, Vladimir Prus wrote: > > Misha Brukman wrote: > > > LLVM Machine code is in SSA. > > > > This explains quite a lot. I though it's possible to just reduce convert > > phis into copy instructions in predecessors -- all of which will have the > > same destination register. > > There are algorithms for eliminating PHI nodes, but they aren't quite so > simple. Consider what happens when you have phi nodes in a block like > this: > > Loop: > A = phi (B, Loop), (0, OutOfLoop) > B = phi (A, Loop), (1, OutOfLoop) > > ... > br Loop > > No matter how you insert copies in the predecessors, you can't maintain > the semantics of the phis (which are simultaneous assignment). This is > obviously possible to handle, it's just not entirely trivial. FWIW, this > is known as the "swap problem".Thanks for explaning!> More importantly, SSA is useful for the code generator. It makes live > variable analysis almost trivial for example, and is a natural > representation to use for other reasons: you have to have an infinite # of > regs before register allocation, why not make them SSA?Yes, this is reasonable thing. - Volodya