docs/BitSets.rst

   1 =======
   2 Bitsets
   3 =======
   4
   5 This is a mechanism that allows IR modules to co-operatively build pointer
   6 sets corresponding to addresses within a given set of globals. One example
   7 of a use case for this is to allow a C++ program to efficiently verify (at
   8 each call site) that a vtable pointer is in the set of valid vtable pointers
   9 for the type of the class or its derived classes.
  10
  11 To use the mechanism, a client creates a global metadata node named
  12 ``llvm.bitsets``.  Each element is a metadata node with three elements:
  13 the first is a metadata string containing an identifier for the bitset,
  14 the second is a global variable and the third is a byte offset into the
  15 global variable.
  16
  17 This will cause a link-time optimization pass to generate bitsets from the
  18 memory addresses referenced from the elements of the bitset metadata. The pass
  19 will lay out the referenced globals consecutively, so their definitions must
  20 be available at LTO time. The `GlobalLayoutBuilder`_ class is responsible for
  21 laying out the globals efficiently to minimize the sizes of the underlying
  22 bitsets. An intrinsic, :ref:`llvm.bitset.test <bitset.test>`, generates code
  23 to test whether a given pointer is a member of a bitset.
  24
  25 :Example:
  26
  27 ::
  28
  29     target datalayout = "e-p:32:32"
  30
  31     @a = internal global i32 0
  32     @b = internal global i32 0
  33     @c = internal global i32 0
  34     @d = internal global [2 x i32] [i32 0, i32 0]
  35
  36     !llvm.bitsets = !{!0, !1, !2, !3, !4}
  37
  38     !0 = !{!"bitset1", i32* @a, i32 0}
  39     !1 = !{!"bitset1", i32* @b, i32 0}
  40     !2 = !{!"bitset2", i32* @b, i32 0}
  41     !3 = !{!"bitset2", i32* @c, i32 0}
  42     !4 = !{!"bitset2", i32* @d, i32 4}
  43
  44     declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone
  45
  46     define i1 @foo(i32* %p) {
  47       %pi8 = bitcast i32* %p to i8*
  48       %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset1")
  49       ret i1 %x
  50     }
  51
  52     define i1 @bar(i32* %p) {
  53       %pi8 = bitcast i32* %p to i8*
  54       %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset2")
  55       ret i1 %x
  56     }
  57
  58     define void @main() {
  59       %a1 = call i1 @foo(i32* @a) ; returns 1
  60       %b1 = call i1 @foo(i32* @b) ; returns 1
  61       %c1 = call i1 @foo(i32* @c) ; returns 0
  62       %a2 = call i1 @bar(i32* @a) ; returns 0
  63       %b2 = call i1 @bar(i32* @b) ; returns 1
  64       %c2 = call i1 @bar(i32* @c) ; returns 1
  65       %d02 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 0)) ; returns 0
  66       %d12 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 1)) ; returns 1
  67       ret void
  68     }
  69
  70 .. _GlobalLayoutBuilder: http://llvm.org/klaus/llvm/blob/master/include/llvm/Transforms/IPO/LowerBitSets.h