[SimplifyCFG] Delete the unnecessary range check for small mask operation

[Allen]

Summary

When the small mask value little than 64, we can eliminate the checking
for upper limit of the range by enlarge the lookup table size to its next
pow2 value.

Fixes https://github.com/llvm/llvm-project/issues/65120

[RKSimon]

@Allen abandon this? AFAICT this was re-submitted as a github PR: https://github.com/llvm/llvm-project/pull/65835

[Allen]

Yes, thanks

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 
   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 {
+    const APInt *MaskC;
+    if (UseSwitchConditionAsTableIndex &&
+        match(TableIndex, m_And(m_Value(), m_APInt(MaskC)))) {
+      APInt SCVPlus1 = *MaskC + 1;
+      const uint64_t *RawData = MaskC->getRawData();
+      // Expand the size of the table when the MaskC < 64.
+      if (SCVPlus1.isPowerOf2() && SCVPlus1.logBase2() <= 6 && RawData) {
+        assert(TableSize <= RawData[0] && "unexpect mask value");
+        // The range check will be deleted later when we enlarge the lookup
+        // table because the check always return true.
+        TableSize = RawData[0] + 1;
+      }
+    }
+
     Value *Cmp = Builder.CreateICmpULT(
         TableIndex, ConstantInt::get(MinCaseVal->getType(), TableSize));
     RangeCheckBranch =
         Builder.CreateCondBr(Cmp, LookupBB, SI->getDefaultDest());
     if (DTU)
       Updates.push_back({DominatorTree::Insert, BB, LookupBB});
   }
 

llvm/test/Transforms/SimplifyCFG/switch_mask.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --scrub-attributes
+; RUN: opt -passes=simplifycfg --switch-to-lookup -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; https://alive2.llvm.org/ce/z/2bNvhg
+define noundef i1 @switch_lookup_with_small_mask(i64 noundef %x) {
+; CHECK-LABEL: @switch_lookup_with_small_mask(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[AND:%.*]] = and i64 [[X:%.*]], 15
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i64 [[AND]], 16
+; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = trunc i64 [[AND]] to i16
+; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i16 [[SWITCH_CAST]], 1
+; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i16 1030, [[SWITCH_SHIFTAMT]]
+; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i16 [[SWITCH_DOWNSHIFT]] to i1
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i1 [[SWITCH_MASKED]], i1 false
+; CHECK-NEXT:    ret i1 [[TMP1]]
+;
+entry:
+  %and = and i64 %x, 15
+  switch i64 %and, label %default [
+  i64 10, label %lor.end
+  i64 1, label %lor.end
+  i64 2, label %lor.end
+  ]
+
+default:                                          ; preds = %entry
+  br label %lor.end
+
+lor.end:                                          ; preds = %entry, %entry, %entry, %default
+  %0 = phi i1 [ true, %entry ], [ false, %default ], [ true, %entry ], [ true, %entry ]
+  ret i1 %0
+}