BlockFrequencyImpl asserts on multiple edges between same MBBs with different weights in LLVM 3.2

We are developing a new backend for a custom processor using LLVM.
After updating to LLVM 3.2, we run into an assertion in BlockFrequencyImpl.h. The offending test-case looks basically like this:

for ( ... ) {

   switch (i) {
   case 100: // do something
     break;
   case 102: // do something else
     break;
   case 103: // do some more
     break;
   case 104: // now something different
     break;
   default: // handle other cases
   }
}

The compiler creates a jumptable for this and inserts an entry for 'case 101' that points to the default block. The machine-basic-block (MBB) of the switch therefore contains two edges to the default MBB, one edge for the jumptable, and another one for the jump handling the case when the index is not in the jumptable.
For some reason, our backend assigns those edges different weights (let's say 24 for the default edge and 16 for the others).

In LLVM 3.1, getSumForBlock in lib/CodeGen/MachineBranchProbability.cpp
used getEdgeWeight(MBB*, MBB*), which always return the weight of the first edge to the default block, i.e., it calculated the sum of the weights as 24+16+24+16+16 = 96. In LLVM 3.2 getSumForBlock was changed to use getEdgeWeight(MBB*, MBB::succ_iterator), causing it to calculate the sum of weights now correctly as 24+16+16+16+16 = 88.

However, in include/llvm/Analysis/BlockFrequencyImpl.h:202 doBlock() uses getEdgeProbability(MBB*, MBB*) when iterating over the ingoing edges of the default block, which only returns the probability for the first edge twice. Due to this and the now correct result of getSumForBlock, the sum of the probabilities of the outgoing edges of the switch block is now greater than 1, and the frequency of the default MBB is larger than the sum of the frequencies of its predecessors, which triggers the assertion in BlockFrequencyImpl.h:246 if the default block is the loop tail.

I attached a patch that makes getEdgeWeight(MBB*,MBB*) behave similar to getEdgeWeight(BasicBlock*,BasicBlock*), i.e., it sums up the weights of all edges to the same successor, and that fixes BlockFrequencyImpl to iterate over every predecessor only once.

However, an alternative option could be to simply disallow different edge weights for edges with the same source and destination, or to make the call to getEdgeFreq(Pred,BB) in BlockFrequencyImpl distinguish between the edges, which would eliminate the need for an additional PtrSet, but is not that easy to implement.

I could not reproduce that problem with the X86 or the ARM backend, so I cannot really provide you with a testcase that works without our backend (which is available on github however..).

Regards,
  Stefan

0001-Bugfix-to-support-multiple-edges-between-the-same-MB.patch (3.97 KB)

Hi Stefan,

The MachineBasicBlock CFG is supposed to be a proper graph without duplicate edges, unlike the LLVM IR CFG.

I thought I had cleaned up all the cases where we created duplicate MBB edges, but it looks like I missed something.

If you can find the place that creates the duplicate MBB edge, that would be great.

/jakob

Hi,

0001-Bugfix-to-avoid-creating-duplicate-edges-in-if-conve.patch (822 Bytes)

Thanks! r173395.

/jakob