Introduce bitset metadata format and bitset lowering pass.

This patch introduces a new mechanism that allows IR modules to co-operatively
build pointer sets corresponding to addresses within a given set of
globals. One particular use case for this is to allow a C++ program to
efficiently verify (at each call site) that a vtable pointer is in the set
of valid vtable pointers for the class or its derived classes. One way of
doing this is for a toolchain component to build, for each class, a bit set
that maps to the memory region allocated for the vtables, such that each 1
bit in the bit set maps to a valid vtable for that class, and lay out the
vtables next to each other, to minimize the total size of the bit sets.

The patch introduces a metadata format for representing pointer sets, an
'@llvm.bitset.test' intrinsic and an LTO lowering pass that lays out the globals
and builds the bitsets, and documents the new feature.

Differential Revision: http://reviews.llvm.org/D7288

llvm-svn: 230054

1 files changed, 34 insertions, 0 deletions

diff --git a/llvm/test/Transforms/LowerBitSets/constant.ll b/llvm/test/Transforms/LowerBitSets/constant.ll
new file mode 100644
index 00000000000..230c57c2a6e
--- /dev/null
+++ b/llvm/test/Transforms/LowerBitSets/constant.ll
@@ -0,0 +1,34 @@
+; RUN: opt -S -lowerbitsets < %s | FileCheck %s
+
+target datalayout = "e-p:32:32"
+
+@a = constant i32 1
+@b = constant [2 x i32] [i32 2, i32 3]
+
+!0 = !{!"bitset1", i32* @a, i32 0}
+!1 = !{!"bitset1", [2 x i32]* @b, i32 4}
+
+!llvm.bitsets = !{ !0, !1 }
+
+declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone
+
+; CHECK: @foo(
+define i1 @foo() {
+  ; CHECK: ret i1 true
+  %x = call i1 @llvm.bitset.test(i8* bitcast (i32* @a to i8*), metadata !"bitset1")
+  ret i1 %x
+}
+
+; CHECK: @bar(
+define i1 @bar() {
+  ; CHECK: ret i1 true
+  %x = call i1 @llvm.bitset.test(i8* bitcast (i32* getelementptr ([2 x i32]* @b, i32 0, i32 1) to i8*), metadata !"bitset1")
+  ret i1 %x
+}
+
+; CHECK: @baz(
+define i1 @baz() {
+  ; CHECK-NOT: ret i1 true
+  %x = call i1 @llvm.bitset.test(i8* bitcast (i32* getelementptr ([2 x i32]* @b, i32 0, i32 0) to i8*), metadata !"bitset1")
+  ret i1 %x
+}