llvm dev - Jan 2013 - [LLVMdev] 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Bugfix-to-support-multiple-edges-between-the-same-MB.patch
Type: text/x-patch
Size: 4064 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130123/32c3094f/attachment.bin>

On Jan 23, 2013, at 12:36 PM, Stefan Hepp <stefan at stefant.org> wrote:
> 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.
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,


On 01/23/2013 11:30 PM, Jakob Stoklund Olesen wrote:
> If you can find the place that creates the duplicate MBB edge, that would
be great.
>
Found it :) It happens in lib/CodeGen/IfConversion.cpp at the very end 
in MergeBlocks. I attached a small patch that should resolve that issue. 
Our tests now compile sucessfully even without my previous patch.

regards,
  Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Bugfix-to-avoid-creating-duplicate-edges-in-if-conve.patch
Type: text/x-patch
Size: 822 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130124/480b5b8a/attachment.bin>