[LLVMbugs] [Bug 3616] New: Bug in BranchFolding.cpp:OptimizeBlock

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=3616

           Summary: Bug in BranchFolding.cpp:OptimizeBlock
           Product: libraries
           Version: 2.4
          Platform: PC
        OS/Version: Windows XP
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Common Code Generator Code
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: micah.villmow at amd.com
                CC: llvmbugs at cs.uiuc.edu


Created an attachment (id=2579)
 --> (http://llvm.org/bugs/attachment.cgi?id=2579)
Rar file including cfg graphs, bitcode and possible patch

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.


-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.