LowerTypeTests: Represent the memory region size with the constant size-1.

[pcc]

Summary

This means that we can use a shorter instruction sequence in the case where
the size is a power of two and on the boundary between two representations.

[eugenis]

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

686

I don;t get it. Why do we switch to a 32-bit check when BitSize == 129?

[eugenis]

LGTM

[pcc]

I'll land this once we've figured out the issue behind D28532.

llvm/include/llvm/IR/ModuleSummaryIndex.h

enum Kind {
     Unsat,     ///< Unsatisfiable type (i.e. no global has this type metadata)
     ByteArray, ///< Test a byte array (first example)
     Inline,    ///< Inlined bit vector ("Short Inline Bit Vectors")
     Single,    ///< Single element (last example in "Short Inline Bit Vectors")
     AllOnes,   ///< All-ones bit vector ("Eliminating Bit Vector Checks for
                ///  All-Ones Bit Vectors")
   } TheKind = Unsat;
 
-  /// Range of the size expressed as a bit width. For example, if the size is in
-  /// range [0,256), this number will be 8. This helps generate the most compact
+  /// Range of size-1 expressed as a bit width. For example, if the size is in
+  /// range [1,256], this number will be 8. This helps generate the most compact
   /// instruction sequences.
-  unsigned SizeBitWidth = 0;
+  unsigned SizeM1BitWidth = 0;
 };
 
 struct TypeIdSummary {
   TypeTestResolution TTRes;
 };
 
 /// 160 bits SHA1
 typedef std::array<uint32_t, 5> ModuleHash;

llvm/include/llvm/IR/ModuleSummaryIndexYAML.h

static void enumeration(IO &io, TypeTestResolution::Kind &value) {
     io.enumCase(value, "Single", TypeTestResolution::Single);
     io.enumCase(value, "AllOnes", TypeTestResolution::AllOnes);
   }
 };
 
 template <> struct MappingTraits<TypeTestResolution> {
   static void mapping(IO &io, TypeTestResolution &res) {
     io.mapOptional("Kind", res.TheKind);
-    io.mapOptional("SizeBitWidth", res.SizeBitWidth);
+    io.mapOptional("SizeM1BitWidth", res.SizeM1BitWidth);
   }
 };
 
 template <> struct MappingTraits<TypeIdSummary> {
   static void mapping(IO &io, TypeIdSummary& summary) {
     io.mapOptional("TTRes", summary.TTRes);
   }
 };

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

struct TypeIdLowering {
 
     /// All except Unsat: the start address within the combined global.
     Constant *OffsetedGlobal;
 
     /// ByteArray, Inline, AllOnes: log2 of the required global alignment
     /// relative to the start address.
     Constant *AlignLog2;
 
-    /// ByteArray, Inline, AllOnes: size of the memory region covering members
-    /// of this type identifier as a multiple of 2^AlignLog2.
-    Constant *Size;
+    /// ByteArray, Inline, AllOnes: one less than the size of the memory region
+    /// covering members of this type identifier as a multiple of 2^AlignLog2.
+    Constant *SizeM1;
 
-    /// ByteArray, Inline, AllOnes: range of the size expressed as a bit width.
-    unsigned SizeBitWidth;
+    /// ByteArray, Inline, AllOnes: range of SizeM1 expressed as a bit width.
+    unsigned SizeM1BitWidth;
 
     /// ByteArray: the byte array to test the address against.
     Constant *TheByteArray;
 
     /// ByteArray: the bit mask to apply to bytes loaded from the byte array.
     Constant *BitMask;
 
     /// Inline: the bit mask to test the address against.
Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
   Value *OffsetSHL = B.CreateShl(
       PtrOffset, ConstantExpr::getZExt(
                      ConstantExpr::getSub(
                          ConstantInt::get(Int8Ty, DL.getPointerSizeInBits(0)),
                          TIL.AlignLog2),
                      IntPtrTy));
   Value *BitOffset = B.CreateOr(OffsetSHR, OffsetSHL);
 
-  Constant *BitSizeConst = ConstantExpr::getZExt(TIL.Size, IntPtrTy);
-  Value *OffsetInRange = B.CreateICmpULT(BitOffset, BitSizeConst);
+  Constant *BitSizeConst = ConstantExpr::getZExt(TIL.SizeM1, IntPtrTy);
+  Value *OffsetInRange = B.CreateICmpULE(BitOffset, BitSizeConst);
 
   // If the bit set is all ones, testing against it is unnecessary.
   if (TIL.TheKind == TypeTestResolution::AllOnes)
     return OffsetInRange;
 
   TerminatorInst *Term = SplitBlockAndInsertIfThen(OffsetInRange, CI, false);
   IRBuilder<> ThenB(Term);
 
for (Metadata *TypeId : TypeIds) {
 
     TypeIdLowering TIL;
     TIL.OffsetedGlobal = ConstantExpr::getGetElementPtr(
         Int8Ty, CombinedGlobalAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)),
     TIL.AlignLog2 = ConstantInt::get(Int8Ty, BSI.AlignLog2);
     if (BSI.isAllOnes()) {
       TIL.TheKind = (BSI.BitSize == 1) ? TypeTestResolution::Single
                                        : TypeTestResolution::AllOnes;
-      TIL.SizeBitWidth = (BSI.BitSize <= 256) ? 8 : 32;
-      TIL.Size = ConstantInt::get((BSI.BitSize <= 256) ? Int8Ty : Int32Ty,
-                                  BSI.BitSize);
+      TIL.SizeM1BitWidth = (BSI.BitSize <= 128) ? 7 : 32;
+      TIL.SizeM1 = ConstantInt::get((BSI.BitSize <= 128) ? Int8Ty : Int32Ty,
+                                    BSI.BitSize - 1);
     } else if (BSI.BitSize <= 64) {
       TIL.TheKind = TypeTestResolution::Inline;
-      TIL.SizeBitWidth = (BSI.BitSize <= 32) ? 5 : 6;
-      TIL.Size = ConstantInt::get(Int8Ty, BSI.BitSize);
+      TIL.SizeM1BitWidth = (BSI.BitSize <= 32) ? 5 : 6;
+      TIL.SizeM1 = ConstantInt::get(Int8Ty, BSI.BitSize - 1);
       uint64_t InlineBits = 0;
       for (auto Bit : BSI.Bits)
         InlineBits |= uint64_t(1) << Bit;
       if (InlineBits == 0)
         TIL.TheKind = TypeTestResolution::Unsat;
       else
         TIL.InlineBits = ConstantInt::get(
             (BSI.BitSize <= 32) ? Int32Ty : Int64Ty, InlineBits);
     } else {
       TIL.TheKind = TypeTestResolution::ByteArray;
-      TIL.SizeBitWidth = (BSI.BitSize <= 256) ? 8 : 32;
-      TIL.Size = ConstantInt::get((BSI.BitSize <= 256) ? Int8Ty : Int32Ty,
-                                  BSI.BitSize);
+      TIL.SizeM1BitWidth = (BSI.BitSize <= 128) ? 7 : 32;
+      TIL.SizeM1 = ConstantInt::get((BSI.BitSize <= 128) ? Int8Ty : Int32Ty,
+                                    BSI.BitSize - 1);
       ++NumByteArraysCreated;
       ByteArrayInfo *BAI = createByteArray(BSI);
       TIL.TheByteArray = BAI->ByteArray;
       TIL.BitMask = BAI->MaskGlobal;
     }
 
     // Lower each call to llvm.type.test for this type identifier.
     for (CallInst *CI : TypeTestCallSites[TypeId]) {

llvm/test/Transforms/LowerTypeTests/Inputs/import-unsat.yaml

 ---
 GlobalValueMap:
   42:
     - TypeTests: [123]
 TypeIdMap:
   typeid1:
     TTRes:
       Kind: Unsat
-      SizeBitWidth: 0
+      SizeM1BitWidth: 0
 ...

llvm/test/Transforms/LowerTypeTests/function.ll

 
 !0 = !{i32 0, !"typeid1"}
 
 declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone
 
 define i1 @foo(i8* %p) {
   ; NATIVE: sub i64 {{.*}}, ptrtoint (void ()* @[[JT]] to i64)
   ; WASM32: sub i64 {{.*}}, ptrtoint (i8* getelementptr (i8, i8* null, i64 1) to i64)
-  ; WASM32: icmp ult i64 {{.*}}, 2
+  ; WASM32: icmp ule i64 {{.*}}, 1
   %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1")
   ret i1 %x
 }
 
 ; X86-LINUX:   define private void @[[JT]]() #[[ATTR:.*]] section ".text.cfi" align 8 {
 ; X86-WIN32:   define private void @[[JT]]() section ".text.cfi" align 8 {
 ; ARM:   define private void @[[JT]]() #[[ATTR:.*]] section ".text.cfi" align 4 {
 ; THUMB: define private void @[[JT]]() #[[ATTR:.*]] section ".text.cfi" align 4 {

llvm/test/Transforms/LowerTypeTests/import-unsat.ll

 ; Test that we correctly import an unsat resolution for type identifier "typeid1".
 ; RUN: opt -S -lowertypetests -lowertypetests-summary-action=import -lowertypetests-read-summary=%S/Inputs/import-unsat.yaml -lowertypetests-write-summary=%t < %s | FileCheck %s
 ; RUN: FileCheck --check-prefix=SUMMARY %s < %t
 
 ; SUMMARY:      GlobalValueMap:
 ; SUMMARY-NEXT:   42:
 ; SUMMARY-NEXT:     - TypeTests:
 ; SUMMARY-NEXT:         - 123
 ; SUMMARY-NEXT: TypeIdMap:
 ; SUMMARY-NEXT:   typeid1:
 ; SUMMARY-NEXT:     TTRes:
 ; SUMMARY-NEXT:       Kind:            Unsat
-; SUMMARY-NEXT:       SizeBitWidth:    0
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
 
 target datalayout = "e-p:32:32"
 
 declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone
 
 define i1 @foo(i8* %p) {
   %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1")
   ; CHECK: ret i1 false
   ret i1 %x
 }

llvm/test/Transforms/LowerTypeTests/simple.ll

define i1 @foo(i32* %p) {
 
   ; CHECK: [[R0:%[^ ]*]] = bitcast i32* [[A0]] to i8*
   %pi8 = bitcast i32* %p to i8*
   ; CHECK: [[R1:%[^ ]*]] = ptrtoint i8* [[R0]] to i32
   ; CHECK: [[R2:%[^ ]*]] = sub i32 [[R1]], ptrtoint ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]] to i32)
   ; CHECK: [[R3:%[^ ]*]] = lshr i32 [[R2]], 2
   ; CHECK: [[R4:%[^ ]*]] = shl i32 [[R2]], 30
   ; CHECK: [[R5:%[^ ]*]] = or i32 [[R3]], [[R4]]
-  ; CHECK: [[R6:%[^ ]*]] = icmp ult i32 [[R5]], 68
+  ; CHECK: [[R6:%[^ ]*]] = icmp ule i32 [[R5]], 67
   ; CHECK: br i1 [[R6]]
 
   ; CHECK: [[R8:%[^ ]*]] = getelementptr i8, i8* @bits_use.{{[0-9]*}}, i32 [[R5]]
   ; CHECK: [[R9:%[^ ]*]] = load i8, i8* [[R8]]
   ; CHECK: [[R10:%[^ ]*]] = and i8 [[R9]], 1
   ; CHECK: [[R11:%[^ ]*]] = icmp ne i8 [[R10]], 0
 
   ; CHECK: [[R16:%[^ ]*]] = phi i1 [ false, {{%[^ ]*}} ], [ [[R11]], {{%[^ ]*}} ]

 define i1 @bar(i32* %p) {
   ; CHECK: [[S0:%[^ ]*]] = bitcast i32* [[B0]] to i8*
   %pi8 = bitcast i32* %p to i8*
   ; CHECK: [[S1:%[^ ]*]] = ptrtoint i8* [[S0]] to i32
   ; CHECK: [[S2:%[^ ]*]] = sub i32 [[S1]], ptrtoint (i8* getelementptr (i8, i8* bitcast ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]] to i8*), i32 4) to i32)
   ; CHECK: [[S3:%[^ ]*]] = lshr i32 [[S2]], 8
   ; CHECK: [[S4:%[^ ]*]] = shl i32 [[S2]], 24
   ; CHECK: [[S5:%[^ ]*]] = or i32 [[S3]], [[S4]]
-  ; CHECK: [[S6:%[^ ]*]] = icmp ult i32 [[S5]], 2
+  ; CHECK: [[S6:%[^ ]*]] = icmp ule i32 [[S5]], 1
   %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid2")
 
   ; CHECK: ret i1 [[S6]]
   ret i1 %x
 }
 
 ; CHECK: @baz(i32* [[C0:%[^ ]*]])
 define i1 @baz(i32* %p) {
   ; CHECK: [[T0:%[^ ]*]] = bitcast i32* [[C0]] to i8*
   %pi8 = bitcast i32* %p to i8*
   ; CHECK: [[T1:%[^ ]*]] = ptrtoint i8* [[T0]] to i32
   ; CHECK: [[T2:%[^ ]*]] = sub i32 [[T1]], ptrtoint ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]] to i32)
   ; CHECK: [[T3:%[^ ]*]] = lshr i32 [[T2]], 2
   ; CHECK: [[T4:%[^ ]*]] = shl i32 [[T2]], 30
   ; CHECK: [[T5:%[^ ]*]] = or i32 [[T3]], [[T4]]
-  ; CHECK: [[T6:%[^ ]*]] = icmp ult i32 [[T5]], 66
+  ; CHECK: [[T6:%[^ ]*]] = icmp ule i32 [[T5]], 65
   ; CHECK: br i1 [[T6]]
 
   ; CHECK: [[T8:%[^ ]*]] = getelementptr i8, i8* @bits_use{{(\.[0-9]*)?}}, i32 [[T5]]
   ; CHECK: [[T9:%[^ ]*]] = load i8, i8* [[T8]]
   ; CHECK: [[T10:%[^ ]*]] = and i8 [[T9]], 2
   ; CHECK: [[T11:%[^ ]*]] = icmp ne i8 [[T10]], 0
 
   ; CHECK: [[T16:%[^ ]*]] = phi i1 [ false, {{%[^ ]*}} ], [ [[T11]], {{%[^ ]*}} ]
   %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid3")
   ; CHECK: ret i1 [[T16]]
   ret i1 %x
 }