Home | History | Annotate | Download | only in docs 
      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 
     14 1. a metadata object representing an identifier for the bitset
     15 2. either a global variable or a function
     16 3. a byte offset into the global (generally zero for functions)
     17 
     18 Each bitset must exclusively contain either global variables or functions.
     19 
     20 .. admonition:: Limitation
     21 
     22   The current implementation only supports functions as members of bitsets on
     23   the x86-32 and x86-64 architectures.
     24 
     25 This will cause a link-time optimization pass to generate bitsets from the
     26 memory addresses referenced from the elements of the bitset metadata. The
     27 pass will lay out referenced global variables consecutively, so their
     28 definitions must be available at LTO time.
     29 
     30 A bit set containing functions is transformed into a jump table, which
     31 is a block of code consisting of one branch instruction for each of the
     32 functions in the bit set that branches to the target function, and redirect
     33 any taken function addresses to the corresponding jump table entry. In the
     34 object file's symbol table, the jump table entries take the identities of
     35 the original functions, so that addresses taken outside the module will pass
     36 any verification done inside the module.
     37 
     38 Jump tables may call external functions, so their definitions need not
     39 be available at LTO time. Note that if an externally defined function is a
     40 member of a bitset, there is no guarantee that its identity within the module
     41 will be the same as its identity outside of the module, as the former will
     42 be the jump table entry if a jump table is necessary.
     43 
     44 The `GlobalLayoutBuilder`_ class is responsible for laying out the globals
     45 efficiently to minimize the sizes of the underlying bitsets. An intrinsic,
     46 :ref:`llvm.bitset.test <bitset.test>`, generates code to test whether a
     47 given pointer is a member of a bitset.
     48 
     49 :Example:
     50 
     51 ::
     52 
     53     target datalayout = "e-p:32:32"
     54 
     55     @a = internal global i32 0
     56     @b = internal global i32 0
     57     @c = internal global i32 0
     58     @d = internal global [2 x i32] [i32 0, i32 0]
     59 
     60     define void @e() {
     61       ret void
     62     }
     63 
     64     define void @f() {
     65       ret void
     66     }
     67 
     68     declare void @g()
     69 
     70     !llvm.bitsets = !{!0, !1, !2, !3, !4, !5, !6}
     71 
     72     !0 = !{!"bitset1", i32* @a, i32 0}
     73     !1 = !{!"bitset1", i32* @b, i32 0}
     74     !2 = !{!"bitset2", i32* @b, i32 0}
     75     !3 = !{!"bitset2", i32* @c, i32 0}
     76     !4 = !{!"bitset2", i32* @d, i32 4}
     77     !5 = !{!"bitset3", void ()* @e, i32 0}
     78     !6 = !{!"bitset3", void ()* @g, i32 0}
     79 
     80     declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone
     81 
     82     define i1 @foo(i32* %p) {
     83       %pi8 = bitcast i32* %p to i8*
     84       %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset1")
     85       ret i1 %x
     86     }
     87 
     88     define i1 @bar(i32* %p) {
     89       %pi8 = bitcast i32* %p to i8*
     90       %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset2")
     91       ret i1 %x
     92     }
     93 
     94     define i1 @baz(void ()* %p) {
     95       %pi8 = bitcast void ()* %p to i8*
     96       %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset3")
     97       ret i1 %x
     98     }
     99 
    100     define void @main() {
    101       %a1 = call i1 @foo(i32* @a) ; returns 1
    102       %b1 = call i1 @foo(i32* @b) ; returns 1
    103       %c1 = call i1 @foo(i32* @c) ; returns 0
    104       %a2 = call i1 @bar(i32* @a) ; returns 0
    105       %b2 = call i1 @bar(i32* @b) ; returns 1
    106       %c2 = call i1 @bar(i32* @c) ; returns 1
    107       %d02 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 0)) ; returns 0
    108       %d12 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 1)) ; returns 1
    109       %e = call i1 @baz(void ()* @e) ; returns 1
    110       %f = call i1 @baz(void ()* @f) ; returns 0
    111       %g = call i1 @baz(void ()* @g) ; returns 1
    112       ret void
    113     }
    114 
    115 .. _GlobalLayoutBuilder: http://llvm.org/klaus/llvm/blob/master/include/llvm/Transforms/IPO/LowerBitSets.h
    116