llvm dev - Sep 2014 - [LLVMdev] PHINode containing itself causes segfault when compiling Blender OpenCL kernel with R600 backend

Hi!

I'm trying to run Blender using Mesa OpenCL implementation on a radeonsi  
card. First the kernel didn't want to compile, but that was caused by a  
bug in it (they were using . instead of -> in 1 place), and after fixing  
this bug I've got the kernel to compile...

...But after that, LLVM started to crash during translation of IR into  
shader code with R600 backend.

I've done some investigation and figured out that the crash is caused by a  
PHINode containing itself. SIAnnotateControlFlow::handleLoopCondition()  
can't handle such situation - it recurses into itself, calls  
Phi->eraseFromParent() inside the inner execution, returns into outer one,  
gets zeroed out object and crashes when trying to do something with its  
members... for example when trying to erase it again.

I have no real background in LLVM or GCC, so the concept of PHINode itself  
was a real discovery for me :) and PHINode containing itself does look  
even more strange... I've tried to understand the semantics of such  
PHINodes from reading the code and got a suspicion that the rest of LLVM  
code just ignores PHINodes equal to their parent... So I've tried to fix  
the bug by making handleLoopCondition() skip IncomingValues equal to the  
Phi itself, but the bug didn't go away! Surprisingly, PHINode may not just  
contain itself directly, but it also may contain itself inside another  
PHINode, i.e. Phi->getIncomingValue(0)->getIncomingValue(0) == Phi, which
results in the same problem with SIAnnotateControlFlow...

Besides "how to make a correct fix" :), my question also is: what are
the
real semantics of a PHINode containing itself directly or indirectly? I've  
done some tracing and saw such PHINodes added by the optimizer, in  
llvm::InlineFunction()... but what do they mean and how to deal with them  
correctly?

-- 
With best regards,
   Vitaliy Filippov

On Sun, Sep 21, 2014 at 01:54:40AM +0400, Vitaliy Filippov
wrote:
> Hi!
> 
> I'm trying to run Blender using Mesa OpenCL implementation on a
> radeonsi card. First the kernel didn't want to compile, but that was
> caused by a bug in it (they were using . instead of -> in 1 place),
> and after fixing this bug I've got the kernel to compile...
> 
> ...But after that, LLVM started to crash during translation of IR
> into shader code with R600 backend.
> 
Can you file a bug for this at bugs.freedesktop.org and post the output
of blender with the environment variable R600_DEUBG=cs,compute

-Tom
> I've done some investigation and figured out that the crash is
> caused by a PHINode containing itself.
> SIAnnotateControlFlow::handleLoopCondition() can't handle such
> situation - it recurses into itself, calls Phi->eraseFromParent()
> inside the inner execution, returns into outer one, gets zeroed out
> object and crashes when trying to do something with its members...
> for example when trying to erase it again.
> 
> I have no real background in LLVM or GCC, so the concept of PHINode
> itself was a real discovery for me :) and PHINode containing itself
> does look even more strange... I've tried to understand the
> semantics of such PHINodes from reading the code and got a suspicion
> that the rest of LLVM code just ignores PHINodes equal to their
> parent... So I've tried to fix the bug by making
> handleLoopCondition() skip IncomingValues equal to the Phi itself,
> but the bug didn't go away! Surprisingly, PHINode may not just
> contain itself directly, but it also may contain itself inside
> another PHINode, i.e. Phi->getIncomingValue(0)->getIncomingValue(0)
> == Phi, which results in the same problem with
> SIAnnotateControlFlow...
> 
> Besides "how to make a correct fix" :), my question also is: what
> are the real semantics of a PHINode containing itself directly or
> indirectly? I've done some tracing and saw such PHINodes added by
> the optimizer, in llvm::InlineFunction()... but what do they mean
> and how to deal with them correctly?
> 
> -- 
> With best regards,
>   Vitaliy Filippov
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

> Can you file a bug for this at bugs.freedesktop.org and post the output
> of blender with the environment variable R600_DEUBG=cs,compute
OK, I'll do that soon (in several hours). I've looked at that output by 
myself, the blender kernel llvm assembly dump was there. I can also 
provide the stack traces of the crash...

But can you give me a hint about the PHINode? What does it mean when it 
contains itself?..

--
With best regards,
   Vitaliy Filippov

On 9/20/14, 5:54 PM, Vitaliy Filippov wrote:
> Hi!
>
> I'm trying to run Blender using Mesa OpenCL implementation on a 
> radeonsi card. First the kernel didn't want to compile, but that was 
> caused by a bug in it (they were using . instead of -> in 1 place), 
> and after fixing this bug I've got the kernel to compile...
>
> ...But after that, LLVM started to crash during translation of IR into 
> shader code with R600 backend.
>
> I've done some investigation and figured out that the crash is caused 
> by a PHINode containing itself. 
> SIAnnotateControlFlow::handleLoopCondition() can't handle such 
> situation - it recurses into itself, calls Phi->eraseFromParent() 
> inside the inner execution, returns into outer one, gets zeroed out 
> object and crashes when trying to do something with its members... for 
> example when trying to erase it again.
>
> I have no real background in LLVM or GCC, so the concept of PHINode 
> itself was a real discovery for me :) and PHINode containing itself 
> does look even more strange... I've tried to understand the semantics 
> of such PHINodes from reading the code and got a suspicion that the 
> rest of LLVM code just ignores PHINodes equal to their parent... So 
> I've tried to fix the bug by making handleLoopCondition() skip 
> IncomingValues equal to the Phi itself, but the bug didn't go away! 
> Surprisingly, PHINode may not just contain itself directly, but it 
> also may contain itself inside another PHINode, i.e. 
> Phi->getIncomingValue(0)->getIncomingValue(0) == Phi, which results
in
> the same problem with SIAnnotateControlFlow...
>
> Besides "how to make a correct fix" :), my question also is: what
are
> the real semantics of a PHINode containing itself directly or 
> indirectly? I've done some tracing and saw such PHINodes added by the 
> optimizer, in llvm::InlineFunction()... but what do they mean and how 
> to deal with them correctly?
If a phi-node contains itself as one of its inputs, then that input will 
contain the last dynamic value of that phi-node (which means, 
essentially, that its value does not change).  If you have:

r1 = phi (bb1, p1) (bb2, r1)

... then if control-flow enters from basic block bb1, then r1 is set to 
the value p1 whereas if control-flow enters from basic block bb2 r1 will 
have its value set to r1 (meaning that it won't change).

For more information on phi-nodes and why they exist, I recommend 
reading "Efficiently computing static single assignment form and the 
control dependence graph" by Ron Cytron et. al.

Regards,

John Criswell

Thanks for the explanation... but does it satisfy SSA? It seems that register
gets overwritten more than 1 time when using itself as input? Shouldn't SSA
unroll such structures into ones that don't reference itself?

And is it the same with LLVM's internal structures (PHINode)? I mean, is
PHINode a "register" or just an "expression"? If it's
meant to be an expression, then it still looks strange to be recursive, because
there's no "previous" value for it to reference...
-- 
With best regards,
  Vitaliy Filippov
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140923/f62f1f62/attachment.html>

> Can you file a bug for this at bugs.freedesktop.org and post the output
> of blender with the environment variable R600_DEUBG=cs,compute
Filed https://bugs.freedesktop.org/show_bug.cgi?id=84232

> Can you file a bug for this at bugs.freedesktop.org and post the output
> of blender with the environment variable R600_DEUBG=cs,compute
Can you give me a hint on what handleLoop() and handleLoopCondition()  
functions in SIAnnotateControlFlow are intended for?

--
With best regards,
   Vitaliy Filippov