[SimplifyCFG] Enable switch to lookup table for more types.

[craig.topper]

Summary

This transform has been restricted to legal types since
https://reviews.llvm.org/rG65df808f6254617b9eee931d00e95d900610b660
in 2012.

This is particularly restrictive on RISCV64 which only has i64
as a legal integer type. i32 is a very common type in code
generated from C, but we won't form a lookup table with it.
This also effects other common types like i8/i16 types on ARM,
AArch64, RISCV, etc.

This patch proposes to allow power of 2 types larger than 8 bit, if
they will fit in the largest legal integer type in DataLayout.
These types are common in C code so generally well handled in
the backends.

We could probably do this for other types like i24 and rely on
alignment and padding to allow the backend to use a single wider
load. This isn't my main concern right now and it will need more
tests.

We could also allow larger types up to some limit and let the
backend split into multiple loads, but we need to define that
limit. It's also not my main concern right now.

[lebedev.ri]

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

[fhahn]

In D107233#2918643, @lebedev.ri wrote:

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

[lebedev.ri]

In D107233#2922165, @fhahn wrote:

In D107233#2918643, @lebedev.ri wrote:

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

[fhahn]

In D107233#2922195, @lebedev.ri wrote:

In D107233#2922165, @fhahn wrote:

In D107233#2918643, @lebedev.ri wrote:

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

I guess in this case, the reference is a historical artifact. I assume the test added to llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll in the commit should be sufficient to guard against the reported issue.

[lebedev.ri]

In D107233#2922212, @fhahn wrote:

In D107233#2922195, @lebedev.ri wrote:

In D107233#2922165, @fhahn wrote:

In D107233#2918643, @lebedev.ri wrote:

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

I guess in this case, the reference is a historical artifact. I assume the test added to llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll in the commit should be sufficient to guard against the reported issue.

I'm not sure i follow. Is it a profitability check, or is it guarding against some crash somewhere in backend?
We can nicely lower i96 load, https://godbolt.org/z/scP8sj5jf, and i suspect it will still be more performant than the switch lowering.

[fhahn]

In D107233#2922212, @fhahn wrote:

In D107233#2922195, @lebedev.ri wrote:

In D107233#2922165, @fhahn wrote:

In D107233#2918643, @lebedev.ri wrote:

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

I guess in this case, the reference is a historical artifact. I assume the test added to llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll in the commit should be sufficient to guard against the reported issue.

The crash was in the AArch64 backend due to the emitted table using un-emittable constants. I don't really have any further insight and cannot say if it is still an issue. I can check a patch against the original source to check if it crashes.

[lebedev.ri]

In D107233#2922229, @fhahn wrote:

In D107233#2922212, @fhahn wrote:

In D107233#2922195, @lebedev.ri wrote:

In D107233#2922165, @fhahn wrote:

In D107233#2918643, @lebedev.ri wrote:

Can we just revert rL168970?
What exactly was the rdar://12779436 about, can anyone look it up?

It's an Apple-internal bug report of a crash that was the reason for the revert. As long as the test that has been added in rL168970 passes that should be fine. I can also verify against the original C++ source.

Note that most people don't have access to any such internal bugtrackers.
What was the crast?

I guess in this case, the reference is a historical artifact. I assume the test added to llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll in the commit should be sufficient to guard against the reported issue.

The crash was in the AArch64 backend due to the emitted table using un-emittable constants. I don't really have any further insight and cannot say if it is still an issue. I can check a patch against the original source to check if it crashes.

Aha. But that was not a reasonable fix. It would still crash just the same should anyone produce such an IR,
the fix should have been in the backend, and indeed, it no longer crashes, for a long while now: https://godbolt.org/z/34nf7q5xz
So back to my original question: can we just essentially revert that commit?

[craig.topper]

I was trying to determine what else the current check is protecting like vectors or floating point. It looks like ValidLookupTableConstant may largely filter out vectors. Though the recursion in ValidLookupTableConstant for ConstantExpr seems like it might be incomplete. It only visits operand 0. Though there are probably no operations that takes a scalar as a first operand and returns a vector result.

[craig.topper]

If the type is very large and the constants are small we will generate a very large table which could be a lot worse than the original switch. Of course we could use a smaller type for the lookup table and the extend the constants in such a case, but that's additional work I can't sign up for. So I think it is still reasonable to have some kind of limit in place here.

[lebedev.ri]

Could you please add a FIXME somewhere around ShouldBuildLookupTable in the code summarizing that support for larger-than-largest-legal-integer types can likely be added?

[craig.topper]

Add another TODO.

[lebedev.ri]

LGTM, this looks very limited-enough.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 //===- SimplifyCFG.cpp - Code to perform CFG simplification ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
bool SwitchLookupTable::WouldFitInRegister(const DataLayout &DL,
   // are <= 15, we could try to narrow the type.
 
   // Avoid overflow, fitsInLegalInteger uses unsigned int for the width.
   if (TableSize >= UINT_MAX / IT->getBitWidth())
     return false;
   return DL.fitsInLegalInteger(TableSize * IT->getBitWidth());
 }
 
+static bool isTypeLegalForLookupTable(Type *Ty, const TargetTransformInfo &TTI,
+                                      const DataLayout &DL) {
+  // Allow any legal type.
+  if (TTI.isTypeLegal(Ty))
+    return true;
+
+  auto *IT = dyn_cast<IntegerType>(Ty);
+  if (!IT)
+    return false;
+
+  // Also allow power of 2 integer types that have at least 8 bits and fit in
+  // a register. These types are common in frontend languages and targets
+  // usually support loads of these types.
+  // TODO: We could relax this to any integer that fits in a register and rely
+  // on ABI alignment and padding in the table to allow the load to be widened.
+  // Or we could widen the constants and truncate the load.
+  unsigned BitWidth = IT->getBitWidth();
+  return BitWidth >= 8 && isPowerOf2_32(BitWidth) &&
+         DL.fitsInLegalInteger(IT->getBitWidth());
+}
+
 /// Determine whether a lookup table should be built for this switch, based on
 /// the number of cases, size of the table, and the types of the results.
+// TODO: We could support larger than legal types by limiting based on the
+// number of loads required and/or table size. If the constants are small we
+// could use smaller table entries and extend after the load.
 static bool
 ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
                        const TargetTransformInfo &TTI, const DataLayout &DL,
                        const SmallDenseMap<PHINode *, Type *> &ResultTypes) {
   if (SI->getNumCases() > TableSize || TableSize >= UINT64_MAX / 10)
     return false; // TableSize overflowed, or mul below might overflow.
 
   bool AllTablesFitInRegister = true;
   bool HasIllegalType = false;
   for (const auto &I : ResultTypes) {
     Type *Ty = I.second;
 
     // Saturate this flag to true.
-    HasIllegalType = HasIllegalType || !TTI.isTypeLegal(Ty);
+    HasIllegalType = HasIllegalType || !isTypeLegalForLookupTable(Ty, TTI, DL);
 
     // Saturate this flag to false.
     AllTablesFitInRegister =
         AllTablesFitInRegister &&
         SwitchLookupTable::WouldFitInRegister(DL, TableSize, Ty);
 
     // If both flags saturate, we're done. NOTE: This *only* works with
     // saturating flags, and all flags have to saturate first due to the

llvm/test/Transforms/SimplifyCFG/RISCV/switch_to_lookup_table-rv32.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -switch-to-lookup=true -keep-loops=false -S -mattr=+f | FileCheck %s
 ; RUN: opt < %s -passes='simplifycfg<no-keep-loops;switch-to-lookup>' -S -mattr=+f | FileCheck %s
 target datalayout = "e-m:e-p:32:32-i64:64-n32-S128"
 target triple = "riscv32-unknown-elf"
 
 ; The table for @f
 ; CHECK: @switch.table.f = private unnamed_addr constant [7 x i32] [i32 55, i32 123, i32 0, i32 -1, i32 27, i32 62, i32 1], align 4
 
+; The char table for char
+; CHECK: @switch.table.char = private unnamed_addr constant [9 x i8] c"7{\00\FF\1B>\01!T", align 1
+
+; The float table for @h
+; CHECK: @switch.table.h = private unnamed_addr constant [4 x float] [float 0x40091EB860000000, float 0x3FF3BE76C0000000, float 0x4012449BA0000000, float 0x4001AE1480000000], align 4
+
 ; The table for @foostring
 ; CHECK: @switch.table.foostring = private unnamed_addr constant [4 x i8*] [i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str2, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str3, i64 0, i64 0)], align 4
 
 ; A simple int-to-int selection switch.
 ; It is dense enough to be replaced by table lookup.
 ; The result is directly by a ret from an otherwise empty bb,
 ; so we return early, directly from the lookup bb.
 

 
 }
 
 ; Same thing, but with i8's
 
 define i8 @char(i32 %c) {
 ; CHECK-LABEL: @char(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 42, label [[RETURN:%.*]]
-; CHECK-NEXT:    i32 43, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i32 44, label [[SW_BB2:%.*]]
-; CHECK-NEXT:    i32 45, label [[SW_BB3:%.*]]
-; CHECK-NEXT:    i32 46, label [[SW_BB4:%.*]]
-; CHECK-NEXT:    i32 47, label [[SW_BB5:%.*]]
-; CHECK-NEXT:    i32 48, label [[SW_BB6:%.*]]
-; CHECK-NEXT:    i32 49, label [[SW_BB7:%.*]]
-; CHECK-NEXT:    i32 50, label [[SW_BB8:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       sw.bb1:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb2:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb3:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb4:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb5:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb6:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb7:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb8:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.default:
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 42
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 9
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i8], [9 x i8]* @switch.table.char, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i8, i8* [[SWITCH_GEP]], align 1
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ 15, [[SW_DEFAULT]] ], [ 84, [[SW_BB8]] ], [ 33, [[SW_BB7]] ], [ 1, [[SW_BB6]] ], [ 62, [[SW_BB5]] ], [ 27, [[SW_BB4]] ], [ -1, [[SW_BB3]] ], [ 0, [[SW_BB2]] ], [ 123, [[SW_BB1]] ], [ 55, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 15, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[RETVAL_0]]
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 42, label %return
   i32 43, label %sw.bb1
   i32 44, label %sw.bb2
   i32 45, label %sw.bb3

 }
 
 ; A switch used to initialize two variables, an i8 and a float.
 
 declare void @dummy(i8 signext, float)
 define void @h(i32 %x) {
 ; CHECK-LABEL: @h(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 [[X:%.*]], label [[SW_DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[SW_EPILOG:%.*]]
-; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i32 2, label [[SW_BB2:%.*]]
-; CHECK-NEXT:    i32 3, label [[SW_BB3:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       sw.bb1:
-; CHECK-NEXT:    br label [[SW_EPILOG]]
-; CHECK:       sw.bb2:
-; CHECK-NEXT:    br label [[SW_EPILOG]]
-; CHECK:       sw.bb3:
-; CHECK-NEXT:    br label [[SW_EPILOG]]
-; CHECK:       sw.default:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_EPILOG:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i32 [[X]], 8
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 89655594, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x float], [4 x float]* @switch.table.h, i32 0, i32 [[X]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load float, float* [[SWITCH_GEP]], align 4
 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 ; CHECK:       sw.epilog:
-; CHECK-NEXT:    [[A_0:%.*]] = phi i8 [ 7, [[SW_DEFAULT]] ], [ 5, [[SW_BB3]] ], [ 88, [[SW_BB2]] ], [ 9, [[SW_BB1]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[B_0:%.*]] = phi float [ 0x4023FAE140000000, [[SW_DEFAULT]] ], [ 0x4001AE1480000000, [[SW_BB3]] ], [ 0x4012449BA0000000, [[SW_BB2]] ], [ 0x3FF3BE76C0000000, [[SW_BB1]] ], [ 0x40091EB860000000, [[ENTRY]] ]
+; CHECK-NEXT:    [[A_0:%.*]] = phi i8 [ [[SWITCH_MASKED]], [[SWITCH_LOOKUP]] ], [ 7, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[B_0:%.*]] = phi float [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 0x4023FAE140000000, [[ENTRY]] ]
 ; CHECK-NEXT:    call void @dummy(i8 signext [[A_0]], float [[B_0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   switch i32 %x, label %sw.default [
   i32 0, label %sw.epilog
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2

llvm/test/Transforms/SimplifyCFG/RISCV/switch_to_lookup_table-rv64.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -switch-to-lookup=true -keep-loops=false -S -mattr=+f | FileCheck %s
 ; RUN: opt < %s -passes='simplifycfg<no-keep-loops;switch-to-lookup>' -S -mattr=+f | FileCheck %s
 target datalayout = "e-m:e-p:64:64-i64:64-i128:128-n64-S128"
 target triple = "riscv64-unknown-elf"
 
+; The table for @f
+; CHECK: @switch.table.f = private unnamed_addr constant [7 x i32] [i32 55, i32 123, i32 0, i32 -1, i32 27, i32 62, i32 1], align 4
+
+; The char table for char
+; CHECK: @switch.table.char = private unnamed_addr constant [9 x i8] c"7{\00\FF\1B>\01!T", align 1
+
+; The float table for @h
+; CHECK: @switch.table.h = private unnamed_addr constant [4 x float] [float 0x40091EB860000000, float 0x3FF3BE76C0000000, float 0x4012449BA0000000, float 0x4001AE1480000000], align 4
+
 ; The table for @foostring
 ; CHECK: @switch.table.foostring = private unnamed_addr constant [4 x i8*] [i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str1, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str2, i64 0, i64 0), i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str3, i64 0, i64 0)], align 8
 
 ; A simple int-to-int selection switch.
 ; It is dense enough to be replaced by table lookup.
 ; The result is directly by a ret from an otherwise empty bb,
 ; so we return early, directly from the lookup bb.
 
 define i32 @f(i32 %c) {
 ; CHECK-LABEL: @f(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 42, label [[RETURN:%.*]]
-; CHECK-NEXT:    i32 43, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i32 44, label [[SW_BB2:%.*]]
-; CHECK-NEXT:    i32 45, label [[SW_BB3:%.*]]
-; CHECK-NEXT:    i32 46, label [[SW_BB4:%.*]]
-; CHECK-NEXT:    i32 47, label [[SW_BB5:%.*]]
-; CHECK-NEXT:    i32 48, label [[SW_BB6:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       sw.bb1:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb2:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb3:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb4:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb5:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb6:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.default:
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 42
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 7
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [7 x i32], [7 x i32]* @switch.table.f, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]], align 4
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ 15, [[SW_DEFAULT]] ], [ 1, [[SW_BB6]] ], [ 62, [[SW_BB5]] ], [ 27, [[SW_BB4]] ], [ -1, [[SW_BB3]] ], [ 0, [[SW_BB2]] ], [ 123, [[SW_BB1]] ], [ 55, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 15, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 42, label %return
   i32 43, label %sw.bb1
   i32 44, label %sw.bb2
   i32 45, label %sw.bb3

 
 }
 
 ; Same thing, but with i8's
 
 define i8 @char(i32 %c) {
 ; CHECK-LABEL: @char(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 42, label [[RETURN:%.*]]
-; CHECK-NEXT:    i32 43, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i32 44, label [[SW_BB2:%.*]]
-; CHECK-NEXT:    i32 45, label [[SW_BB3:%.*]]
-; CHECK-NEXT:    i32 46, label [[SW_BB4:%.*]]
-; CHECK-NEXT:    i32 47, label [[SW_BB5:%.*]]
-; CHECK-NEXT:    i32 48, label [[SW_BB6:%.*]]
-; CHECK-NEXT:    i32 49, label [[SW_BB7:%.*]]
-; CHECK-NEXT:    i32 50, label [[SW_BB8:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       sw.bb1:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb2:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb3:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb4:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb5:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb6:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb7:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.bb8:
-; CHECK-NEXT:    br label [[RETURN]]
-; CHECK:       sw.default:
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[C:%.*]], 42
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 9
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [9 x i8], [9 x i8]* @switch.table.char, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i8, i8* [[SWITCH_GEP]], align 1
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
-; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ 15, [[SW_DEFAULT]] ], [ 84, [[SW_BB8]] ], [ 33, [[SW_BB7]] ], [ 1, [[SW_BB6]] ], [ 62, [[SW_BB5]] ], [ 27, [[SW_BB4]] ], [ -1, [[SW_BB3]] ], [ 0, [[SW_BB2]] ], [ 123, [[SW_BB1]] ], [ 55, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 15, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    ret i8 [[RETVAL_0]]
 ;
 entry:
   switch i32 %c, label %sw.default [
   i32 42, label %return
   i32 43, label %sw.bb1
   i32 44, label %sw.bb2
   i32 45, label %sw.bb3

 }
 
 ; A switch used to initialize two variables, an i8 and a float.
 
 declare void @dummy(i8 signext, float)
 define void @h(i32 %x) {
 ; CHECK-LABEL: @h(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i32 [[X:%.*]], label [[SW_DEFAULT:%.*]] [
-; CHECK-NEXT:    i32 0, label [[SW_EPILOG:%.*]]
-; CHECK-NEXT:    i32 1, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i32 2, label [[SW_BB2:%.*]]
-; CHECK-NEXT:    i32 3, label [[SW_BB3:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       sw.bb1:
-; CHECK-NEXT:    br label [[SW_EPILOG]]
-; CHECK:       sw.bb2:
-; CHECK-NEXT:    br label [[SW_EPILOG]]
-; CHECK:       sw.bb3:
-; CHECK-NEXT:    br label [[SW_EPILOG]]
-; CHECK:       sw.default:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[SW_EPILOG:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul i32 [[X]], 8
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 89655594, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x float], [4 x float]* @switch.table.h, i32 0, i32 [[X]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load float, float* [[SWITCH_GEP]], align 4
 ; CHECK-NEXT:    br label [[SW_EPILOG]]
 ; CHECK:       sw.epilog:
-; CHECK-NEXT:    [[A_0:%.*]] = phi i8 [ 7, [[SW_DEFAULT]] ], [ 5, [[SW_BB3]] ], [ 88, [[SW_BB2]] ], [ 9, [[SW_BB1]] ], [ 42, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[B_0:%.*]] = phi float [ 0x4023FAE140000000, [[SW_DEFAULT]] ], [ 0x4001AE1480000000, [[SW_BB3]] ], [ 0x4012449BA0000000, [[SW_BB2]] ], [ 0x3FF3BE76C0000000, [[SW_BB1]] ], [ 0x40091EB860000000, [[ENTRY]] ]
+; CHECK-NEXT:    [[A_0:%.*]] = phi i8 [ [[SWITCH_MASKED]], [[SWITCH_LOOKUP]] ], [ 7, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[B_0:%.*]] = phi float [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 0x4023FAE140000000, [[ENTRY]] ]
 ; CHECK-NEXT:    call void @dummy(i8 signext [[A_0]], float [[B_0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   switch i32 %x, label %sw.default [
   i32 0, label %sw.epilog
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2

llvm/test/Transforms/SimplifyCFG/rangereduce.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -S | FileCheck %s
 ; RUN: opt < %s -passes='simplifycfg<switch-to-lookup>' -S | FileCheck %s
 
 target datalayout = "e-n32"
 
 define i32 @test1(i32 %a) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[COMMON_RET:%.*]] [
-; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 2, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 3, label [[THREE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.test1, i32 0, i32 [[TMP4]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]], align 4
+; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       common.ret:
-; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
-; CHECK:       one:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       two:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       three:
-; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
   switch i32 %a, label %def [
   i32 97, label %one
   i32 101, label %two
   i32 105, label %three
   i32 109, label %three
   ]
 
two:
   ret i128 1143
 three:
   ret i128 99783
 }
 
 ; Optimization shouldn't trigger; no holes present
 define i32 @test3(i32 %a) {
 ; CHECK-LABEL: @test3(
-; CHECK-NEXT:    switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [
-; CHECK-NEXT:    i32 97, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 98, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 99, label [[THREE:%.*]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[A:%.*]], 97
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 3
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], [3 x i32]* @switch.table.test3, i32 0, i32 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]], align 4
+; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       common.ret:
-; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
-; CHECK:       one:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       two:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       three:
-; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
   switch i32 %a, label %def [
   i32 97, label %one
   i32 98, label %two
   i32 99, label %three
   ]
 
 def:

 }
 
 define i32 @test6(i32 %a) optsize {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], -109
 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[COMMON_RET:%.*]] [
-; CHECK-NEXT:    i32 3, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 2, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 1, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 0, label [[THREE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 4
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], [4 x i32]* @switch.table.test6, i32 0, i32 [[TMP4]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]], align 4
+; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       common.ret:
-; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
-; CHECK:       one:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       two:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       three:
-; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
   switch i32 %a, label %def [
   i32 -97, label %one
   i32 -101, label %two
   i32 -105, label %three
   i32 -109, label %three
   ]
 

 }
 
 define i32 @test8(i32 %a) optsize {
 ; CHECK-LABEL: @test8(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 30
 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[COMMON_RET:%.*]] [
-; CHECK-NEXT:    i32 0, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 1, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 2, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 4, label [[THREE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 5
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i32], [5 x i32]* @switch.table.test8, i32 0, i32 [[TMP4]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]], align 4
+; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       common.ret:
-; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
-; CHECK:       one:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       two:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       three:
-; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
   switch i32 %a, label %def [
   i32 97, label %one
   i32 101, label %two
   i32 105, label %three
   i32 113, label %three
   ]
 

 }
 
 define i32 @test9(i32 %a) {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 6
 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 1
 ; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 [[TMP1]], 31
 ; CHECK-NEXT:    [[TMP4:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    switch i32 [[TMP4]], label [[COMMON_RET:%.*]] [
-; CHECK-NEXT:    i32 6, label [[ONE:%.*]]
-; CHECK-NEXT:    i32 7, label [[TWO:%.*]]
-; CHECK-NEXT:    i32 0, label [[THREE:%.*]]
-; CHECK-NEXT:    i32 2, label [[THREE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp ult i32 [[TMP4]], 8
+; CHECK-NEXT:    br i1 [[TMP5]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], [8 x i32]* @switch.table.test9, i32 0, i32 [[TMP4]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, i32* [[SWITCH_GEP]], align 4
+; CHECK-NEXT:    br label [[COMMON_RET]]
 ; CHECK:       common.ret:
-; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ]
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
-; CHECK:       one:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       two:
-; CHECK-NEXT:    br label [[COMMON_RET]]
-; CHECK:       three:
-; CHECK-NEXT:    br label [[COMMON_RET]]
 ;
   switch i32 %a, label %def [
   i32 18, label %one
   i32 20, label %two
   i32 6, label %three
   i32 10, label %three
   ]