[SimplifyCFG] Avoid shifting by a too large exponent.

[fhahn]

Summary

TI->getBitWidth can be > 64 and in those cases the shift will be UB due
to the exponent being too large.

To fix this, cap the shift at 63. I think this should work out fine,
because TableSize is itself a 64 bit type and the maximum table size
must fit in the type. Also, if we would underestimate the size here, at
most we get an extra ZExt.

[spatel]

Are the tests changing with this patch? Use --check-globals with update_test_checks.py to verify that the table entries are as expected?

[fhahn]

In D124608#3480598, @spatel wrote:

Are the tests changing with this patch? Use --check-globals with update_test_checks.py to verify that the table entries are as expected?

Thanks, I updated the test with --check-globals. It looks like the update script doesn't use the pattern for the global at its uses, I'll file a bug for that.

There are no test changes. I think for test changes we would need a table with a size larger than fits into a 64 bit integer.

[spatel]

In D124608#3482047, @fhahn wrote:

In D124608#3480598, @spatel wrote:

Are the tests changing with this patch? Use --check-globals with update_test_checks.py to verify that the table entries are as expected?

Thanks, I updated the test with --check-globals. It looks like the update script doesn't use the pattern for the global at its uses, I'll file a bug for that.

There are no test changes. I think for test changes we would need a table with a size larger than fits into a 64 bit integer.

I see. So was this bug found only by inspection?
It's hard to keep track of the various size constraints in this code, but this seems ok. LGTM.

[fhahn]

In D124608#3482419, @spatel wrote:

In D124608#3482047, @fhahn wrote:

In D124608#3480598, @spatel wrote:

Are the tests changing with this patch? Use --check-globals with update_test_checks.py to verify that the table entries are as expected?

Thanks, I updated the test with --check-globals. It looks like the update script doesn't use the pattern for the global at its uses, I'll file a bug for that.

There are no test changes. I think for test changes we would need a table with a size larger than fits into a 64 bit integer.

I see. So was this bug found only by inspection?

It was found when using a Clang build with UBSan :)

[arichardson]

llvm/test/Transforms/SimplifyCFG/X86/switch-to-lookup-large-types.ll

24

@fhahn These two functions are identical, was this supposed to use an i64 in the switch?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

case BitMapKind: {
     // Mask off.
     return Builder.CreateTrunc(DownShifted, BitMapElementTy, "switch.masked");
   }
   case ArrayKind: {
     // Make sure the table index will not overflow when treated as signed.
     IntegerType *IT = cast<IntegerType>(Index->getType());
     uint64_t TableSize =
         Array->getInitializer()->getType()->getArrayNumElements();
-    if (TableSize > (1ULL << (IT->getBitWidth() - 1)))
+    if (TableSize > (1ULL << std::min(IT->getBitWidth() - 1, 63u)))
       Index = Builder.CreateZExt(
           Index, IntegerType::get(IT->getContext(), IT->getBitWidth() + 1),
           "switch.tableidx.zext");
 
     Value *GEPIndices[] = {Builder.getInt32(0), Index};
     Value *GEP = Builder.CreateInBoundsGEP(Array->getValueType(), Array,
                                            GEPIndices, "switch.gep");
     return Builder.CreateLoad(

llvm/test/Transforms/SimplifyCFG/X86/switch-to-lookup-large-types.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature --scrub-attributes
+; RUN: opt -passes=simplifycfg --switch-to-lookup -S %s | FileCheck %s
+target triple = "x86_64-unknown-linux-gnu"
+
+
+define i8 @switch_to_lookup_i64(i128 %x){
+; CHECK-LABEL: define {{[^@]+}}@switch_to_lookup_i64
+; CHECK-SAME: (i128 [[X:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i128 [[X]], 3
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
+; CHECK:       common.ret:
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i8 [ [[SWITCH_LOAD:%.*]], [[SWITCH_LOOKUP]] ], [ 10, [[START:%.*]] ]
+; CHECK-NEXT:    ret i8 [[COMMON_RET_OP]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i8], [3 x i8]* @switch.table.switch_to_lookup_i64, i32 0, i128 [[X]]
+; CHECK-NEXT:    [[SWITCH_LOAD]] = load i8, i8* [[SWITCH_GEP]], align 1
+; CHECK-NEXT:    br label [[COMMON_RET]]
+;
+start:
+  switch i128 %x, label %default [
+  i128 0, label %end
+  i128 1, label %bb1
+  i128 2, label %bb2
+  ]
+
+bb1:
+  br label %end
+
+bb2:
+  br label %end
+
+default:
+  ret i8 10
+
+end:
+  %p = phi i8 [ 1, %bb1 ], [ 2, %bb2 ], [ 3, %start ]
+  ret i8 %p
+}
+define i8 @switch_to_lookup_i128(i128 %x){
+; CHECK-LABEL: define {{[^@]+}}@switch_to_lookup_i128
+; CHECK-SAME: (i128 [[X:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i128 [[X]], 3
+; CHECK-NEXT:    br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
+; CHECK:       common.ret:
+; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i8 [ [[SWITCH_LOAD:%.*]], [[SWITCH_LOOKUP]] ], [ 10, [[START:%.*]] ]
+; CHECK-NEXT:    ret i8 [[COMMON_RET_OP]]
+; CHECK:       switch.lookup:
+; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i8], [3 x i8]* @switch.table.switch_to_lookup_i128, i32 0, i128 [[X]]
+; CHECK-NEXT:    [[SWITCH_LOAD]] = load i8, i8* [[SWITCH_GEP]], align 1
+; CHECK-NEXT:    br label [[COMMON_RET]]
+;
+start:
+  switch i128 %x, label %default [
+  i128 0, label %end
+  i128 1, label %bb1
+  i128 2, label %bb2
+  ]
+
+bb1:
+  br label %end
+
+bb2:
+  br label %end
+
+default:
+  ret i8 10
+
+end:
+  %p = phi i8 [ 1, %bb1 ], [ 2, %bb2 ], [ 3, %start ]
+  ret i8 %p
+}