llvm dev - Nov 2008 - [LLVMdev] Problem in CodeExtractor::severSplitPHINodes()

Hi,

I found a problem in CodeExtractor::severSplitPHINodes()
<CodeExtractor.cpp>.

The algorithm first separates the header block into two, one containing only
PHI nodes and the other containing the remaining non-PHI nodes. The variable
NewBB holds the pointer to the latter half block. Later, it tries to update
DT information.

if (DT)
    DT->splitBlock(NewBB);

In splitBlock, it checks if the NewBB has only one successor. I'm not sure
why this is required, but it will fail on cases where NewBB has multiple
successors, which are pretty common. For example, a switch or a conditional
branch in NewBB can break this check.

Could anyone tell me how to fix this please?

Thanks a lot.

Jack
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20081119/c5323109/attachment.html>

On Nov 19, 2008, at 7:41 AM, Jack Tzu-Han Hung wrote:
> Hi,
>
> I found a problem in CodeExtractor::severSplitPHINodes()  
> <CodeExtractor.cpp>.
>
> The algorithm first separates the header block into two, one  
> containing only PHI nodes and the other containing the remaining non- 
> PHI nodes. The variable NewBB holds the pointer to the latter half  
> block. Later, it tries to update DT information.
>
> if (DT)
>     DT->splitBlock(NewBB);
>
> In splitBlock, it checks if the NewBB has only one successor. I'm  
> not sure why this is required, but it will fail on cases where NewBB  
> has multiple successors, which are pretty common. For example, a  
> switch or a conditional branch in NewBB can break this check.
DT->splitBlock() updates dominator information _after_ the block is  
split. The comments in header says,

   /// splitBlock - BB is split and now it has one successor. Update  
dominance
   /// frontier to reflect this change.
   void splitBlock(BasicBlock *BB);

Immediately after the split the NewBB can have only one successor.
>
>
> Could anyone tell me how to fix this please?
>
> Thanks a lot.
>
> Jack
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-
Devang



-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20081119/3fc155ff/attachment.html>

Hi Devang,

Thanks for your reply.

But if you look at the comment of BasicBlock::splitBasicBlock(), it says
that "...an unconditional branch is added to the new BB, and the rest of
the
instructions in the BB are moved to the newBB, including the old
terminator."

So, the terminator of the newBB is exactly the same as the terminator of the
oldBB. IF the oldBB has multiple successors, then newBB will have multiple
successors.

Actually there is an example for this (in "wc", the word count
program):

for (gotsp = 1; len = read(fd, buf, MAXBSIZE);){
  if (len == -1) {
    perror(file);
    exit(1);
  }
  // do other stuff
}

Compiled with llvm-gcc -O1, the loop header has three successors: one to
inside the loop, one to outside the loop, and the third to a block that
contains exit(1).

ExtractLoop() has problem with this this example.

Thanks a lot.

Jack




On Wed, Nov 19, 2008 at 7:41 PM, Devang Patel <dpatel at apple.com> wrote:
>
> On Nov 19, 2008, at 7:41 AM, Jack Tzu-Han Hung wrote:
>
> Hi,
>
> I found a problem in CodeExtractor::severSplitPHINodes()
> <CodeExtractor.cpp>.
>
> The algorithm first separates the header block into two, one containing
> only PHI nodes and the other containing the remaining non-PHI nodes. The
> variable NewBB holds the pointer to the latter half block. Later, it tries
> to update DT information.
>
> if (DT)
>     DT->splitBlock(NewBB);
>
> In splitBlock, it checks if the NewBB has only one successor. I'm not
sure
> why this is required, but it will fail on cases where NewBB has multiple
> successors, which are pretty common. For example, a switch or a conditional
> branch in NewBB can break this check.
>
>
> DT->splitBlock() updates dominator information _after_ the block is
split.
> The comments in header says,
>
>   /// splitBlock - BB is split and now it has one successor. Update
> dominance
>
>   /// frontier to reflect this change.
>
>
>   void splitBlock(BasicBlock *BB);
>
> Immediately after the split the NewBB can have only one successor.
>
>
>
> Could anyone tell me how to fix this please?
>
> Thanks a lot.
>
> Jack
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
> -
> Devang
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

-- 
Jack Tzu-Han Hung
www.cs.princeton.edu/~thhung
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20081120/d80b9349/attachment.html>