[LLVMdev] Incorrect Simple pattern matching in lib/CodeGen/IfConversion.cpp

[Stefan Hepp]

Hello!

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.

Regards,
   Stefan