OSDN Git Service

Teach simplify-cfg how to correctly create covered lookup tables for switches on...
authorMichael Gottesman <mgottesman@apple.com>
Sun, 20 Oct 2013 07:04:37 +0000 (07:04 +0000)
committerMichael Gottesman <mgottesman@apple.com>
Sun, 20 Oct 2013 07:04:37 +0000 (07:04 +0000)
commit0b5fad68b296087b4d0132dcd19690d2cdce2c77
tree012660ae598fdfc70a21f60c3619cbc8c3367232
parent8f70847f98925153ad48fdeea1a8e72ee08d78eb
Teach simplify-cfg how to correctly create covered lookup tables for switches on iN with N >= 3.

One optimization simplify-cfg performs is the converting of switches to
lookup tables if the switch has > 4 cases. This is done by:

1. Finding the max/min case value and calculating the switch case range.
2. Create a lookup table basic block.
3. Perform a check in the switch's BB to see if the input value is in
the switch's case range. If the input value satisfies said predicate
branch to the lookup table BB, otherwise branch to the switch's default
destination BB using the default value as the result.

The conditional check consists of subtracting the min case value of the
table from any input iN value and then ensuring that said value is
unsigned less than the size of the lookup table represented as an iN
value.

If the lookup table is a covered lookup table, the size of the table will be N
which is 0 as an iN value. Thus the comparison will be an `icmp ult` of an iN
value against 0 which is always false yielding the incorrect result.

This patch fixes this problem by recognizing if we have a covered lookup table
and if we do, unconditionally jumps to the lookup table BB since the covering
property of the lookup table implies no input values could not be handled by
said BB.

rdar://15268442

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@193045 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Transforms/Utils/SimplifyCFG.cpp
test/Transforms/SimplifyCFG/CoveredLookupTable.ll [new file with mode: 0644]