[SimplifyCFG] Find the smallest table considering overflow in `switchToLookupTable`

[DianQK]

Summary

Closes https://github.com/llvm/llvm-project/issues/64231.

[nikic]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6436

I don't like that the whole fold gets invoked twice with this flag flipped. Can we just pick the Min/Max that result in the smallest table size (i.e. Max-Min) here?

Ideally we would not even base this on signed/unsigned at all, because the smallest range might be both signed *and* unsigned wrapping. Consider something like -128, -1, 0, 127. This would pick [-128, 127] as the signed range, [0, -1] as the unsigned range, but a minimal range would be [127, 0] or [-1, -128]. This would be based around the largest gap between the case value. Though just signed/unsigned is probably the main useful case.

[DianQK]

Try to find a minimal range.
Some test cases got better and some got worse.

[DianQK]

I need to check these test case changes carefully.

I ran llvm-lit with alive. The result is:

Failed Tests (2):
  LLVM :: Transforms/SimplifyCFG/fold-branch-to-common-dest.ll
  LLVM :: Transforms/SimplifyCFG/speculate-call.ll

I haven't focused on whether this is an issue with alive or in itself, but it doesn't seem to be related to this patch.

I believe @signed_overflow1, @signed_overflow2, and @signed_overflow_negative have all changed for the better. @signed_overflow1 and @signed_overflow_negative exchange results. But since we prefer to start at 0, this reduces the number of sub/add instructions by one.
@covered_switch_with_bit_tests also becomes better, smaller table and fewer commands.
@f_i8_128 is our new test. @_TFO6reduce1E5toRawfS0_FT_Si becomes better.

@f_min_max_2, @f_min_max, @test, and @coveredswitch_test look to become worse. But their table size did get smaller.
I rechecked @f_min_max_2, @f_min_max and @test. They become from table with holes to table without holes. It's a "perfect" table?
I've also found that they luckily have a max and min value. Then we created a cover table.
If we want to deal with this situation, maybe we should add a condition to extend to a cover table.

@coveredswitch_test also luckily have a max and min value.

[DianQK]

Rebase.

[DianQK]

Maybe ready for a new review.

These test cases that went worse just happened to have the max and min values of bit width, and then created a cover table with holes.
I think I should create another patch that adds a threshold condition to grow into a cover table to handle this.

[khei4]

I'm still not sure about the correctness of this. It seems like only setting the BeginCaseVal and EndCaseVal to the appropriate values is enough to handle overflowing switch cases. Test transformations themselves look correct!

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6439

I think it's ok to use auto on this.

[DianQK]

In D156612#4647819, @khei4 wrote:

I'm still not sure about the correctness of this. It seems like only setting the BeginCaseVal and EndCaseVal to the appropriate values is enough to handle overflowing switch cases. Test transformations themselves look correct!

Could you explain more about the overflow?
If you're referring to RangeOverflow in the code, this is a special handling to avoid redundant calculation.
Or do you mean that we can always find the smallest table whose End minus Begin does not overflow? Yes. But we need to introduce an overflow offset calculation.
For example, [122, -128]([122, 128]) in the @f_i8_128 case.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6439

Thanks, if Nikita will continue to review it here, I'll change it directly. Otherwise I'll change it when I move to GitHub.

[DianQK]

In D156612#4647819, @khei4 wrote:

I'm still not sure about the correctness of this. It seems like only setting the BeginCaseVal and EndCaseVal to the appropriate values is enough to handle overflowing switch cases. Test transformations themselves look correct!

I seem to understand what you mean. Yes, this patch is looking for the appropriate BeginCaseVal and EndCaseVal.

[DianQK]

Migrated to https://github.com/llvm/llvm-project/pull/67885.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

ShouldBuildLookupTable(SwitchInst *SI, uint64_t TableSize,
   // Don't build a table that doesn't fit in-register if it has illegal types.
   if (HasIllegalType)
     return false;
 
   return isSwitchDense(SI->getNumCases(), TableSize);
 }
 
 static bool ShouldUseSwitchConditionAsTableIndex(
-    ConstantInt &MinCaseVal, const ConstantInt &MaxCaseVal,
+    ConstantInt &BeginCaseVal, const ConstantInt &EndCaseVal,
     bool HasDefaultResults, const SmallDenseMap<PHINode *, Type *> &ResultTypes,
     const DataLayout &DL, const TargetTransformInfo &TTI) {
-  if (MinCaseVal.isNullValue())
+  if (BeginCaseVal.isNullValue())
     return true;
-  if (MinCaseVal.isNegative() ||
-      MaxCaseVal.getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
+  if (BeginCaseVal.getValue().sge(EndCaseVal.getValue()))
+    return false;
+  if (BeginCaseVal.isNegative() ||
+      EndCaseVal.getLimitedValue() == std::numeric_limits<uint64_t>::max() ||
       !HasDefaultResults)
     return false;
   return all_of(ResultTypes, [&](const auto &KV) {
     return SwitchLookupTable::WouldFitInRegister(
-        DL, MaxCaseVal.getLimitedValue() + 1 /* TableSize */,
+        DL, EndCaseVal.getLimitedValue() + 1 /* TableSize */,
         KV.second /* ResultType */);
   });
 }
 
 /// Try to reuse the switch table index compare. Following pattern:
 /// \code
 ///     if (idx < tablesize)
 ///        r = table[idx]; // table does not contain default_value
if (DefaultConst == FalseConst) {
     CmpInst->replaceAllUsesWith(InvertedTableCmp);
     ++NumTableCmpReuses;
   }
 }
 
 /// If the switch is only used to initialize one or more phi nodes in a common
 /// successor block with different constant values, replace the switch with
 /// lookup tables.
-static bool SwitchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
+static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
                                 DomTreeUpdater *DTU, const DataLayout &DL,
                                 const TargetTransformInfo &TTI) {
   assert(SI->getNumCases() > 1 && "Degenerate switch?");
 
   BasicBlock *BB = SI->getParent();
   Function *Fn = BB->getParent();
   // Only build lookup table when we have a target that supports it or the
   // attribute is not set.
static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
   // Ignore switches with less than three cases. Lookup tables will not make
   // them faster, so we don't analyze them.
   if (SI->getNumCases() < 3)
     return false;
 
   // Figure out the corresponding result for each case value and phi node in the
   // common destination, as well as the min and max case values.
   assert(!SI->cases().empty());
-  SwitchInst::CaseIt CI = SI->case_begin();
-  ConstantInt *MinCaseVal = CI->getCaseValue();
-  ConstantInt *MaxCaseVal = CI->getCaseValue();
 
   BasicBlock *CommonDest = nullptr;
 
   using ResultListTy = SmallVector<std::pair<ConstantInt *, Constant *>, 4>;
   SmallDenseMap<PHINode *, ResultListTy> ResultLists;
 
   SmallDenseMap<PHINode *, Constant *> DefaultResults;
   SmallDenseMap<PHINode *, Type *> ResultTypes;
   SmallVector<PHINode *, 4> PHIs;
 
-  for (SwitchInst::CaseIt E = SI->case_end(); CI != E; ++CI) {
-    ConstantInt *CaseVal = CI->getCaseValue();
-    if (CaseVal->getValue().slt(MinCaseVal->getValue()))
-      MinCaseVal = CaseVal;
-    if (CaseVal->getValue().sgt(MaxCaseVal->getValue()))
-      MaxCaseVal = CaseVal;
+  SmallVector<ConstantInt *, 8> CaseVals;
+  for (auto CI : SI->cases()) {
+    ConstantInt *CaseVal = CI.getCaseValue();
+    CaseVals.push_back(CaseVal);
+  }
+
+  // We want to find a range of indexes that will create the minimal table.
+  // We can treat all possible index values as a circle. For example, the i8 is
+  // [-128, -1] and [0, 127]. After that find the minimal range from this circle
+  // that can cover all exist values. First, create an incrementing sequence.
+  llvm::sort(CaseVals, [](const ConstantInt *A, const ConstantInt *B) {
+    return A->getValue().slt(B->getValue());
+  });
+  SmallVectorImpl<ConstantInt *>::iterator CaseValIter = CaseVals.begin();
+  // We start by using the begin and end as the minimal table.
+  ConstantInt *BeginCaseVal = *CaseValIter;
+  ConstantInt *EndCaseVal = *CaseVals.rbegin();
+  bool RangeOverflow = false;
+  uint64_t MinTableSize = EndCaseVal->getValue()
+                              .ssub_ov(BeginCaseVal->getValue(), RangeOverflow)
+                              .getLimitedValue() +
+                          1;
+  // If there is no overflow, then this must be the minimal table.
+  if (RangeOverflow) {
+    auto MaxValue = APInt::getMaxValue(BeginCaseVal->getBitWidth());
+    while (CaseValIter != CaseVals.end()) {
+      auto *CurrentCaseVal = *CaseValIter++;
+      if (CaseValIter == CaseVals.end()) {
+        break;
+      }
+      ConstantInt *NextCaseVal = *CaseValIter;
+      auto NextVal = NextCaseVal->getValue();
+      auto CurVal = CurrentCaseVal->getValue();
+      uint64_t RequireTableSize =
+          (MaxValue - (NextVal - CurVal) + 1).getLimitedValue() + 1;
+      // FIXME: When there is more than one minimal table, we can choose the
+      // best one. The current simple strategy may not be the best.
+      if (((RequireTableSize < MinTableSize) ||
+           (RequireTableSize == MinTableSize &&
+            NextCaseVal->getValue().isZero()))) {
+        BeginCaseVal = NextCaseVal;
+        EndCaseVal = CurrentCaseVal;
+        MinTableSize = RequireTableSize;
+      }
+    }
+  }
+
+  for (const auto CI : SI->cases()) {
+    ConstantInt *CaseVal = CI.getCaseValue();
 
     // Resulting value at phi nodes for this case value.
     using ResultsTy = SmallVector<std::pair<PHINode *, Constant *>, 4>;
     ResultsTy Results;
-    if (!getCaseResults(SI, CaseVal, CI->getCaseSuccessor(), &CommonDest,
+    if (!getCaseResults(SI, CaseVal, CI.getCaseSuccessor(), &CommonDest,
                         Results, DL, TTI))
       return false;
 
     // Append the result from this case to the list for each phi.
     for (const auto &I : Results) {
       PHINode *PHI = I.first;
       Constant *Value = I.second;
       if (!ResultLists.count(PHI))
static bool switchToLookupTable(SwitchInst *SI, IRBuilder<> &Builder,
 
   for (const auto &I : DefaultResultsList) {
     PHINode *PHI = I.first;
     Constant *Result = I.second;
     DefaultResults[PHI] = Result;
   }
 
   bool UseSwitchConditionAsTableIndex = ShouldUseSwitchConditionAsTableIndex(
-      *MinCaseVal, *MaxCaseVal, HasDefaultResults, ResultTypes, DL, TTI);
+      *BeginCaseVal, *EndCaseVal, HasDefaultResults, ResultTypes, DL, TTI);
   uint64_t TableSize;
   if (UseSwitchConditionAsTableIndex)
-    TableSize = MaxCaseVal->getLimitedValue() + 1;
+    TableSize = EndCaseVal->getLimitedValue() + 1;
   else
-    TableSize =
-        (MaxCaseVal->getValue() - MinCaseVal->getValue()).getLimitedValue() + 1;
+    TableSize = MinTableSize;
 
   bool TableHasHoles = (NumResults < TableSize);
   bool NeedMask = (TableHasHoles && !HasDefaultResults);
   if (NeedMask) {
     // As an extra penalty for the validity test we require more cases.
     if (SI->getNumCases() < 4) // FIXME: Find best threshold value (benchmark).
       return false;
     if (!DL.fitsInLegalInteger(TableSize))
       return false;
   }
 
   if (!ShouldBuildLookupTable(SI, TableSize, TTI, DL, ResultTypes))
     return false;
 
   std::vector<DominatorTree::UpdateType> Updates;
 
   // Compute the maximum table size representable by the integer type we are
   // switching upon.
-  unsigned CaseSize = MinCaseVal->getType()->getPrimitiveSizeInBits();
+  unsigned CaseSize = BeginCaseVal->getType()->getPrimitiveSizeInBits();
   uint64_t MaxTableSize = CaseSize > 63 ? UINT64_MAX : 1ULL << CaseSize;
   assert(MaxTableSize >= TableSize &&
          "It is impossible for a switch to have more entries than the max "
          "representable value of its input integer type's size.");
 
   // If the default destination is unreachable, or if the lookup table covers
   // all values of the conditional variable, branch directly to the lookup table
   // BB. Otherwise, check that the condition is within the case range.
   const bool DefaultIsReachable =
       !isa<UnreachableInst>(SI->getDefaultDest()->getFirstNonPHIOrDbg());
   const bool GeneratingCoveredLookupTable = (MaxTableSize == TableSize);
 
   // Create the BB that does the lookups.
   Module &Mod = *CommonDest->getParent()->getParent();
   BasicBlock *LookupBB = BasicBlock::Create(
       Mod.getContext(), "switch.lookup", CommonDest->getParent(), CommonDest);
 
   // Compute the table index value.
   Builder.SetInsertPoint(SI);
   Value *TableIndex;
   ConstantInt *TableIndexOffset;
   if (UseSwitchConditionAsTableIndex) {
-    TableIndexOffset = ConstantInt::get(MaxCaseVal->getType(), 0);
+    TableIndexOffset = ConstantInt::get(EndCaseVal->getType(), 0);
     TableIndex = SI->getCondition();
   } else {
-    TableIndexOffset = MinCaseVal;
+    TableIndexOffset = BeginCaseVal;
     // If the default is unreachable, all case values are s>= MinCaseVal. Then
     // we can try to attach nsw.
     bool MayWrap = true;
-    if (!DefaultIsReachable) {
-      APInt Res = MaxCaseVal->getValue().ssub_ov(MinCaseVal->getValue(), MayWrap);
+    if (!DefaultIsReachable &&
+        EndCaseVal->getValue().sge(BeginCaseVal->getValue())) {
+      APInt Res =
+          EndCaseVal->getValue().ssub_ov(BeginCaseVal->getValue(), MayWrap);
       (void)Res;
     }
 
     TableIndex = Builder.CreateSub(SI->getCondition(), TableIndexOffset,
                                    "switch.tableidx", /*HasNUW =*/false,
                                    /*HasNSW =*/!MayWrap);
   }
 
   BranchInst *RangeCheckBranch = nullptr;
 
   if (!DefaultIsReachable || GeneratingCoveredLookupTable) {
     Builder.CreateBr(LookupBB);
     if (DTU)
       Updates.push_back({DominatorTree::Insert, BB, LookupBB});
     // Note: We call removeProdecessor later since we need to be able to get the
     // PHI value for the default case in case we're using a bit mask.
   } else {
     Value *Cmp = Builder.CreateICmpULT(
-        TableIndex, ConstantInt::get(MinCaseVal->getType(), TableSize));
+        TableIndex, ConstantInt::get(BeginCaseVal->getType(), TableSize));
     RangeCheckBranch =
         Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
     if (DTU)
       Updates.push_back({DominatorTree::Insert, BB, LookupBB});
   }
 
   // Populate the BB that does the lookups.
   Builder.SetInsertPoint(LookupBB);
if (Options.ForwardSwitchCondToPhi && ForwardSwitchConditionToPHI(SI))
     return requestResimplify();
 
   // The conversion from switch to lookup tables results in difficult-to-analyze
   // code and makes pruning branches much harder. This is a problem if the
   // switch expression itself can still be restricted as a result of inlining or
   // CVP. Therefore, only apply this transformation during late stages of the
   // optimisation pipeline.
   if (Options.ConvertSwitchToLookupTable &&
-      SwitchToLookupTable(SI, Builder, DTU, DL, TTI))
+      switchToLookupTable(SI, Builder, DTU, DL, TTI))
     return requestResimplify();
 
   if (ReduceSwitchRange(SI, Builder, DL, TTI))
     return requestResimplify();
 
   return false;
 }
 

llvm/test/Transforms/SimplifyCFG/X86/CoveredLookupTable.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -S %s | FileCheck %s
 ; RUN: opt -passes='simplifycfg<switch-to-lookup>' -S %s | FileCheck %s
 ; rdar://15268442
 
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin12.0.0"
 
 define i3 @coveredswitch_test(i3 %input) {
 ; CHECK-LABEL: @coveredswitch_test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[INPUT:%.*]], -4
-; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i24
-; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i24 [[SWITCH_CAST]], 3
-; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i24 7507338, [[SWITCH_SHIFTAMT]]
-; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i24 [[SWITCH_DOWNSHIFT]] to i3
-; CHECK-NEXT:    ret i3 [[SWITCH_MASKED]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i3 [[INPUT:%.*]], -2
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i3 [[INPUT]] to i18
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i18 [[SWITCH_CAST]], 3
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i18 42792, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i18 [[SWITCH_DOWNSHIFT]] to i3
+; CHECK-NEXT:    [[RESULT:%.*]] = select i1 [[TMP0]], i3 [[SWITCH_MASKED]], i3 -2
+; CHECK-NEXT:    ret i3 [[RESULT]]
 ;
 entry:
   switch i3 %input, label %bb8 [
   i3 0, label %bb7
   i3 1, label %bb
   i3 2, label %bb3
   i3 3, label %bb4
   i3 4, label %bb5

llvm/test/Transforms/SimplifyCFG/X86/switch-covered-bug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
 ; RUN: opt -S -passes='simplifycfg<switch-to-lookup>' < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
 
 ; rdar://17887153
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin12.0.0"
 
 define i64 @test(i3 %arg) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[ARG:%.*]], -4
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[ARG:%.*]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i3 [[SWITCH_TABLEIDX]], -2
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[DEFAULT:%.*]]
+; CHECK:       switch.lookup:
 ; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i4
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i64], ptr @switch.table.test, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i64], ptr @switch.table.test, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, ptr [[SWITCH_GEP]], align 8
-; CHECK-NEXT:    [[V3:%.*]] = add i64 [[SWITCH_LOAD]], 0
+; CHECK-NEXT:    br label [[DEFAULT]]
+; CHECK:       Default:
+; CHECK-NEXT:    [[V1:%.*]] = phi i64 [ 8, [[ENTRY:%.*]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
+; CHECK-NEXT:    [[V3:%.*]] = add i64 [[V1]], 0
 ; CHECK-NEXT:    ret i64 [[V3]]
 ;
 entry:
   switch i3 %arg, label %Default [
   i3 -2, label %Label6
   i3 1, label %Label1
   i3 2, label %Label2
   i3 3, label %Label3

llvm/test/Transforms/SimplifyCFG/X86/switch-table-bug.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
 ; RUN: opt -S -passes='simplifycfg<switch-to-lookup>' < %s -mtriple=x86_64-apple-darwin12.0.0 | FileCheck %s
 
 ; rdar://17735071
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin12.0.0"
 
 define i64 @_TFO6reduce1E5toRawfS0_FT_Si(i2) {
 ; CHECK-LABEL: @_TFO6reduce1E5toRawfS0_FT_Si(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i2 [[TMP0:%.*]], -2
-; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i2 [[SWITCH_TABLEIDX]] to i3
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i64], ptr @switch.table._TFO6reduce1E5toRawfS0_FT_Si, i32 0, i3 [[SWITCH_TABLEIDX_ZEXT]]
-; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i64, ptr [[SWITCH_GEP]], align 8
-; CHECK-NEXT:    ret i64 [[SWITCH_LOAD]]
+; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = zext i2 [[TMP0:%.*]] to i64
+; CHECK-NEXT:    ret i64 [[SWITCH_IDX_CAST]]
 ;
 entry:
   switch i2 %0, label %1 [
   i2 0, label %2
   i2 1, label %3
   i2 -2, label %4
   i2 -1, label %5
   ]

llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

 
 }
 
 ; The minimal table range is [122, -128]([122, 128]).
 
 define i32 @f_i8_128(i8 %c) {
 ; CHECK-LABEL: @f_i8_128(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    switch i8 [[C:%.*]], label [[SW_DEFAULT:%.*]] [
-; CHECK-NEXT:    i8 122, label [[RETURN:%.*]]
-; CHECK-NEXT:    i8 123, label [[SW_BB1:%.*]]
-; CHECK-NEXT:    i8 124, label [[SW_BB2:%.*]]
-; CHECK-NEXT:    i8 125, label [[SW_BB3:%.*]]
-; CHECK-NEXT:    i8 126, label [[SW_BB4:%.*]]
-; CHECK-NEXT:    i8 127, label [[SW_BB5:%.*]]
-; CHECK-NEXT:    i8 -128, 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 i8 [[C:%.*]], 122
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i8 [[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], ptr @switch.table.f_i8_128, i32 0, i8 [[SWITCH_TABLEIDX]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[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 i8 %c, label %sw.default [
   i8 122, label %return
   i8 123, label %sw.bb1
   i8 124, label %sw.bb2
   i8 125, label %sw.bb3
return:
   ret i32 %retval.0
 }
 
 ; The minimal table range is [3, 0].
 
 define i32 @f_min_max(i3 %c) {
 ; CHECK-LABEL: @f_min_max(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[C:%.*]], -4
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[C:%.*]], 3
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i3 [[SWITCH_TABLEIDX]], -2
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK:       switch.lookup:
 ; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i4
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], ptr @switch.table.f_min_max, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i32], ptr @switch.table.f_min_max, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
-; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 15, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
 entry:
   switch i3 %c, label %sw.default [
   i3 -4, label %return
   i3 -3, label %sw.bb1
   i3 -2, label %sw.bb2
   i3 -1, label %sw.bb3
   i3 0, label %sw.bb4
return:
   ret i32 %retval.0
 }
 
 ; The minimal table range is [-1, -4].
 
 define i32 @f_min_max_2(i3 %c) {
 ; CHECK-LABEL: @f_min_max_2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[C:%.*]], -4
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[C:%.*]], -1
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i3 [[SWITCH_TABLEIDX]], -2
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[RETURN:%.*]]
+; CHECK:       switch.lookup:
 ; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i4
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], ptr @switch.table.f_min_max_2, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i32], ptr @switch.table.f_min_max_2, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
-; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 15, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
 entry:
   switch i3 %c, label %sw.default [
   i3 -1, label %return
   i3 0, label %sw.bb1
   i3 1, label %sw.bb2
   i3 2, label %sw.bb3
   i3 3, label %sw.bb4

 
 ; Make sure we do not crash due to trying to generate an unguarded
 ; lookup (since i3 can only hold values in the range of explicit
 ; values) and simultaneously trying to generate a branch to deal with
 ; the fact that we have holes in the range.
 define i32 @covered_switch_with_bit_tests(i3) {
 ; CHECK-LABEL: @covered_switch_with_bit_tests(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[TMP0:%.*]], -4
-; CHECK-NEXT:    [[SWITCH_MASKINDEX:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i8
-; CHECK-NEXT:    [[SWITCH_SHIFTED:%.*]] = lshr i8 -61, [[SWITCH_MASKINDEX]]
-; CHECK-NEXT:    [[SWITCH_LOBIT:%.*]] = trunc i8 [[SWITCH_SHIFTED]] to i1
-; CHECK-NEXT:    br i1 [[SWITCH_LOBIT]], label [[SWITCH_LOOKUP:%.*]], label [[L6:%.*]]
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i3 [[TMP0:%.*]], 2
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i3 [[SWITCH_TABLEIDX]], -4
+; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[L6:%.*]]
 ; CHECK:       switch.lookup:
-; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i3 [[SWITCH_TABLEIDX]] to i4
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], ptr @switch.table.covered_switch_with_bit_tests, i32 0, i4 [[SWITCH_TABLEIDX_ZEXT]]
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.covered_switch_with_bit_tests, i32 0, i3 [[SWITCH_TABLEIDX]]
 ; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
 ; CHECK-NEXT:    br label [[L6]]
 ; CHECK:       l6:
 ; CHECK-NEXT:    [[R:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
 entry:
   switch i3 %0, label %l6 [
return:
   %storemerge = phi i1 [ true, %sw.bb ], [ false, %sw.default ]
   ret i1 %storemerge
 }
 
 define i32 @signed_overflow1(i8 %n) {
 ; CHECK-LABEL: @signed_overflow1(
 ; CHECK-NEXT:  start:
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[N:%.*]] to i2
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i2 [[TRUNC]], -2
-; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i2 [[SWITCH_TABLEIDX]] to i3
-; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.signed_overflow1, i32 0, i3 [[SWITCH_TABLEIDX_ZEXT]]
-; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
-; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
+; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = zext i2 [[TRUNC]] to i32
+; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul nsw i32 [[SWITCH_IDX_CAST]], 1111
+; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add nsw i32 [[SWITCH_IDX_MULT]], 1111
+; CHECK-NEXT:    ret i32 [[SWITCH_OFFSET]]
 ;
 start:
   %trunc = trunc i8 %n to i2
   switch i2 %trunc, label %bb1 [
   i2 0, label %bb6
   i2 1, label %bb3
   i2 -2, label %bb4
   i2 -1, label %bb5
bb6:                                              ; preds = %start, %bb3, %bb4, %bb5
   %.sroa.0.0 = phi i32 [ 4444, %bb5 ], [ 3333, %bb4 ], [ 2222, %bb3 ], [ 1111, %start ]
   ret i32 %.sroa.0.0
 }
 
 define i32 @signed_overflow2(i8 %n) {
 ; CHECK-LABEL: @signed_overflow2(
 ; CHECK-NEXT:  start:
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[N:%.*]] to i2
-; CHECK-NEXT:    switch i2 [[TRUNC]], label [[BB1:%.*]] [
-; CHECK-NEXT:    i2 1, label [[BB6:%.*]]
-; CHECK-NEXT:    i2 -2, label [[BB4:%.*]]
-; CHECK-NEXT:    i2 -1, label [[BB5:%.*]]
-; CHECK-NEXT:    ]
-; CHECK:       bb1:
-; CHECK-NEXT:    unreachable
-; CHECK:       bb4:
-; CHECK-NEXT:    br label [[BB6]]
-; CHECK:       bb5:
-; CHECK-NEXT:    br label [[BB6]]
-; CHECK:       bb6:
-; CHECK-NEXT:    [[DOTSROA_0_0:%.*]] = phi i32 [ 4444, [[BB5]] ], [ 3333, [[BB4]] ], [ 2222, [[START:%.*]] ]
-; CHECK-NEXT:    ret i32 [[DOTSROA_0_0]]
+; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i2 [[TRUNC]], 1
+; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = zext i2 [[SWITCH_TABLEIDX]] to i32
+; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul nsw i32 [[SWITCH_IDX_CAST]], 1111
+; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add nsw i32 [[SWITCH_IDX_MULT]], 2222
+; CHECK-NEXT:    ret i32 [[SWITCH_OFFSET]]
 ;
 start:
   %trunc = trunc i8 %n to i2
   switch i2 %trunc, label %bb1 [
   i2 1, label %bb3
   i2 -2, label %bb4
   i2 -1, label %bb5
   ]
bb6:                                              ; preds = %start, %bb3, %bb4, %bb5
   %.sroa.0.0 = phi i32 [ 4444, %bb5 ], [ 3333, %bb4 ], [ 2222, %bb3 ]
   ret i32 %.sroa.0.0
 }
 
 define i32 @signed_overflow_negative(i8 %n) {
 ; CHECK-LABEL: @signed_overflow_negative(
 ; CHECK-NEXT:  start:
 ; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i8 [[N:%.*]] to i2
-; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i2 [[TRUNC]], -2
-; CHECK-NEXT:    [[SWITCH_IDX_CAST:%.*]] = zext i2 [[SWITCH_TABLEIDX]] to i32
-; CHECK-NEXT:    [[SWITCH_IDX_MULT:%.*]] = mul nsw i32 [[SWITCH_IDX_CAST]], 1111
-; CHECK-NEXT:    [[SWITCH_OFFSET:%.*]] = add nsw i32 [[SWITCH_IDX_MULT]], 1111
-; CHECK-NEXT:    ret i32 [[SWITCH_OFFSET]]
+; CHECK-NEXT:    [[SWITCH_TABLEIDX_ZEXT:%.*]] = zext i2 [[TRUNC]] to i3
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.signed_overflow_negative, i32 0, i3 [[SWITCH_TABLEIDX_ZEXT]]
+; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
+; CHECK-NEXT:    ret i32 [[SWITCH_LOAD]]
 ;
 start:
   %trunc = trunc i8 %n to i2
   switch i2 %trunc, label %bb1 [
   i2 0, label %bb6
   i2 1, label %bb3
   i2 -2, label %bb4
   i2 -1, label %bb5