Stefan Hepp
2013-Jan-23 20:36 UTC
[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>
Jakob Stoklund Olesen
2013-Jan-23 22:30 UTC
[LLVMdev] BlockFrequencyImpl asserts on multiple edges between same MBBs with different weights in LLVM 3.2
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
Stefan Hepp
2013-Jan-24 15:15 UTC
[LLVMdev] BlockFrequencyImpl asserts on multiple edges between same MBBs with different weights in LLVM 3.2
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>
Maybe Matching Threads
- [LLVMdev] BlockFrequencyImpl asserts on multiple edges between same MBBs with different weights in LLVM 3.2
- [LLVMdev] BlockFrequencyImpl asserts on multiple edges between same MBBs with different weights in LLVM 3.2
- [LLVMdev] Question regarding basic-block placement optimization
- [LLVMdev] Crash on accessing deleted MBBs (new backend)
- [LLVMdev] Question regarding basic-block placement optimization