[LLVMdev] Bug in BranchFolding.cpp:OptimizeBlock

[Villmow, Micah]

I've ran across an issue in BranchFolding.cpp where it is incorrectly
folding a branch to the wrong fallthrough location. This is in LLVM 2.4
and seems to be in 2.5 also.

The code in question is:

void BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {

  MachineFunction::iterator FallThrough = MBB;

  ++FallThrough;

  

  // If this block is empty, make everyone use its fall-through, not the
block

  // explicitly.  Landing pads should not do this since the landing-pad
table

  // points to this block.

  if (MBB->empty() && !MBB->isLandingPad()) {

    // Dead block?  Leave for cleanup later.

    if (MBB->pred_empty()) return;

    

    if (FallThrough == MBB->getParent()->end()) {

      // TODO: Simplify preds to not branch here if possible!

    } else {

      // Rewrite all predecessors of the old block to go to the
fallthrough

      // instead.

      while (!MBB->pred_empty()) {

        MachineBasicBlock *Pred = *(MBB->pred_end()-1);

        Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);

      }

      

      // If MBB was the target of a jump table, update jump tables to go
to the

      // fallthrough instead.

      MBB->getParent()->getJumpTableInfo()->

        ReplaceMBBInJumpTables(MBB, FallThrough);

      MadeChange = true;

    }

    return;

  }

 

The problem with this section of code is that FallThrough is not
guaranteed to be a successor of MBB or even a descendent of MBB.

The bitcode I've attached is a case where there are 5 basic blocks,
where the first four end with conditional branches to an early return,
as specified with initial.dot. 

TailMergeBlocks in BranchFolding::runOnMachineFunction merges the 4
early return blocks to a single basic block and numbers renumbers them,
as specified with tailmerge.dot.

When it runs optimize block on the if.end14 block, it enters the above
segment of code, removing it and replacing it with FallThrough, which is
NOT its successor block and links two blocks changing the structure of
the program as shown in Optimizeblock.dot.

 

I've attached a possible solution as a p4diff as I don't have svn setup
on this machine, but let me know of any comments about the patch.

 

All of the files are attached in bugzilla, #3616, 
http://llvm.org/bugs/show_bug.cgi?id=3616

 

Micah Villmow

Systems Engineer

Advanced Technology & Performance

Advanced Micro Devices Inc.

S1-609 One AMD Place

Sunnyvale, CA. 94085

P: 408-749-3966

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090218/2b321739/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: optimizeblock.diff
Type: application/octet-stream
Size: 873 bytes
Desc: optimizeblock.diff
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090218/2b321739/attachment.obj>