Incorrect Simple pattern matching in lib/CodeGen/IfConversion.cpp


The if-converter tries to match 'Simple' patterns looking like this:

     // Simple (split, no rejoin):
     // EBB
     // | \_
     // | |
     // | TBB---> exit
     // |
     // FBB

The IfConverter::ValidSimple method (lib/CodeGen/IfConversion.cpp:461) checks if TBB matches this pattern. It basically does this by simply checking if AnalyseBranch fails on that block (IfConversion.cpp:640).

This fails if TBB contains something that AnalyseBranch is not able to understand but is still a branch and may have fallthrough edges.

In my case, TBB ends with a predicated indirect branch, which comes from a jumptable-jump that has been if-converted into TBB, i.e., TBB can either jump to some computed address or fall through to the next block. AnalyzeBranch returns true on that block since it is not a simple conditional jump. ValidSimple however assumes that since IsBrAnalysable is false, TBB does not branch and does not fall through, therefore the if-converter merges EBB and TBB, adding FBB as fall-through to the new block, and the fallthrough block of TBB is no longer reached. This causes the compiled program to execute FBB instead of the fallthrough-block of TBB, leading to incorrect behaviour.

I added the following check to IfConverter::ValidSimple(), which fixes my problems:

   if (!TrueBBI.BB->succ_empty())
     return false;

but I have no idea if there is a less conservative way of checking for the Simple pattern (e.g., an unconditional indirect jump might still be allowed at the end of TBB).

I use the code from the LLVM 3.2 release, but it is basically the same in LLVM 3.1 and in head.