Index: llvm/trunk/docs/BitSets.rst =================================================================== --- llvm/trunk/docs/BitSets.rst +++ llvm/trunk/docs/BitSets.rst @@ -1,221 +0,0 @@ -======= -Bitsets -======= - -This is a mechanism that allows IR modules to co-operatively build pointer -sets corresponding to addresses within a given set of globals. One example -of a 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 type of the class or its derived classes. - -To use the mechanism, a client creates a global metadata node named -``llvm.bitsets``. Each element is a metadata node with three elements: - -1. a metadata object representing an identifier for the bitset -2. either a global variable or a function -3. a byte offset into the global (generally zero for functions) - -Each bitset must exclusively contain either global variables or functions. - -.. admonition:: Limitation - - The current implementation only supports functions as members of bitsets on - the x86-32 and x86-64 architectures. - -An intrinsic, :ref:`llvm.bitset.test `, is used to test -whether a given pointer is a member of a bitset. - -Representing Type Information using Bitsets -=========================================== - -This section describes how Clang represents C++ type information associated with -virtual tables using bitsets. - -Consider the following inheritance hierarchy: - -.. code-block:: c++ - - struct A { - virtual void f(); - }; - - struct B : A { - virtual void f(); - virtual void g(); - }; - - struct C { - virtual void h(); - }; - - struct D : A, C { - virtual void f(); - virtual void h(); - }; - -The virtual table objects for A, B, C and D look like this (under the Itanium ABI): - -.. csv-table:: Virtual Table Layout for A, B, C, D - :header: Class, 0, 1, 2, 3, 4, 5, 6 - - A, A::offset-to-top, &A::rtti, &A::f - B, B::offset-to-top, &B::rtti, &B::f, &B::g - C, C::offset-to-top, &C::rtti, &C::h - D, D::offset-to-top, &D::rtti, &D::f, &D::h, D::offset-to-top, &D::rtti, thunk for &D::h - -When an object of type A is constructed, the address of ``&A::f`` in A's -virtual table object is stored in the object's vtable pointer. In ABI parlance -this address is known as an `address point`_. Similarly, when an object of type -B is constructed, the address of ``&B::f`` is stored in the vtable pointer. In -this way, the vtable in B's virtual table object is compatible with A's vtable. - -D is a little more complicated, due to the use of multiple inheritance. Its -virtual table object contains two vtables, one compatible with A's vtable and -the other compatible with C's vtable. Objects of type D contain two virtual -pointers, one belonging to the A subobject and containing the address of -the vtable compatible with A's vtable, and the other belonging to the C -subobject and containing the address of the vtable compatible with C's vtable. - -The full set of compatibility information for the above class hierarchy is -shown below. The following table shows the name of a class, the offset of an -address point within that class's vtable and the name of one of the classes -with which that address point is compatible. - -.. csv-table:: Bitsets for A, B, C, D - :header: VTable for, Offset, Compatible Class - - A, 16, A - B, 16, A - , , B - C, 16, C - D, 16, A - , , D - , 48, C - -The next step is to encode this compatibility information into the IR. The way -this is done is to create bitsets named after each of the compatible classes, -into which we add each of the compatible address points in each vtable. -For example, these bitset entries encode the compatibility information for -the above hierarchy: - -:: - - !0 = !{!"_ZTS1A", [3 x i8*]* @_ZTV1A, i64 16} - !1 = !{!"_ZTS1A", [4 x i8*]* @_ZTV1B, i64 16} - !2 = !{!"_ZTS1B", [4 x i8*]* @_ZTV1B, i64 16} - !3 = !{!"_ZTS1C", [3 x i8*]* @_ZTV1C, i64 16} - !4 = !{!"_ZTS1A", [7 x i8*]* @_ZTV1D, i64 16} - !5 = !{!"_ZTS1D", [7 x i8*]* @_ZTV1D, i64 16} - !6 = !{!"_ZTS1C", [7 x i8*]* @_ZTV1D, i64 48} - -With these bitsets, we can now use the ``llvm.bitset.test`` intrinsic to test -whether a given pointer is compatible with a bitset. Working backwards, -if ``llvm.bitset.test`` returns true for a particular pointer, we can also -statically determine the identities of the virtual functions that a particular -virtual call may call. For example, if a program assumes a pointer to be in the -``!"_ZST1A"`` bitset, we know that the address can be only be one of ``_ZTV1A+16``, -``_ZTV1B+16`` or ``_ZTV1D+16`` (i.e. the address points of the vtables of A, -B and D respectively). If we then load an address from that pointer, we know -that the address can only be one of ``&A::f``, ``&B::f`` or ``&D::f``. - -.. _address point: https://mentorembedded.github.io/cxx-abi/abi.html#vtable-general - -Testing Bitset Addresses -======================== - -If a program tests an address using ``llvm.bitset.test``, this will cause -a link-time optimization pass, ``LowerBitSets``, to replace calls to this -intrinsic with efficient code to perform bitset tests. At a high level, -the pass will lay out referenced globals in a consecutive memory region in -the object file, construct bit vectors that map onto that memory region, -and generate code at each of the ``llvm.bitset.test`` call sites to test -pointers against those bit vectors. Because of the layout manipulation, the -globals' definitions must be available at LTO time. For more information, -see the `control flow integrity design document`_. - -A bit set containing functions is transformed into a jump table, which is a -block of code consisting of one branch instruction for each of the functions -in the bit set that branches to the target function. The pass will redirect -any taken function addresses to the corresponding jump table entry. In the -object file's symbol table, the jump table entries take the identities of -the original functions, so that addresses taken outside the module will pass -any verification done inside the module. - -Jump tables may call external functions, so their definitions need not -be available at LTO time. Note that if an externally defined function is a -member of a bitset, there is no guarantee that its identity within the module -will be the same as its identity outside of the module, as the former will -be the jump table entry if a jump table is necessary. - -The `GlobalLayoutBuilder`_ class is responsible for laying out the globals -efficiently to minimize the sizes of the underlying bitsets. - -.. _control flow integrity design document: http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html - -:Example: - -:: - - target datalayout = "e-p:32:32" - - @a = internal global i32 0 - @b = internal global i32 0 - @c = internal global i32 0 - @d = internal global [2 x i32] [i32 0, i32 0] - - define void @e() { - ret void - } - - define void @f() { - ret void - } - - declare void @g() - - !llvm.bitsets = !{!0, !1, !2, !3, !4, !5, !6} - - !0 = !{!"bitset1", i32* @a, i32 0} - !1 = !{!"bitset1", i32* @b, i32 0} - !2 = !{!"bitset2", i32* @b, i32 0} - !3 = !{!"bitset2", i32* @c, i32 0} - !4 = !{!"bitset2", i32* @d, i32 4} - !5 = !{!"bitset3", void ()* @e, i32 0} - !6 = !{!"bitset3", void ()* @g, i32 0} - - declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - - define i1 @foo(i32* %p) { - %pi8 = bitcast i32* %p to i8* - %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset1") - ret i1 %x - } - - define i1 @bar(i32* %p) { - %pi8 = bitcast i32* %p to i8* - %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset2") - ret i1 %x - } - - define i1 @baz(void ()* %p) { - %pi8 = bitcast void ()* %p to i8* - %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset3") - ret i1 %x - } - - define void @main() { - %a1 = call i1 @foo(i32* @a) ; returns 1 - %b1 = call i1 @foo(i32* @b) ; returns 1 - %c1 = call i1 @foo(i32* @c) ; returns 0 - %a2 = call i1 @bar(i32* @a) ; returns 0 - %b2 = call i1 @bar(i32* @b) ; returns 1 - %c2 = call i1 @bar(i32* @c) ; returns 1 - %d02 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 0)) ; returns 0 - %d12 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 1)) ; returns 1 - %e = call i1 @baz(void ()* @e) ; returns 1 - %f = call i1 @baz(void ()* @f) ; returns 0 - %g = call i1 @baz(void ()* @g) ; returns 1 - ret void - } - -.. _GlobalLayoutBuilder: http://llvm.org/klaus/llvm/blob/master/include/llvm/Transforms/IPO/LowerBitSets.h Index: llvm/trunk/docs/LangRef.rst =================================================================== --- llvm/trunk/docs/LangRef.rst +++ llvm/trunk/docs/LangRef.rst @@ -4839,12 +4839,6 @@ !1 = !{!1} ; an identifier for the inner loop !2 = !{!2} ; an identifier for the outer loop -'``llvm.bitsets``' -^^^^^^^^^^^^^^^^^^ - -The ``llvm.bitsets`` global metadata is used to implement -:doc:`bitsets `. - '``invariant.group``' Metadata ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -12274,9 +12268,9 @@ that the optimizer can otherwise deduce or facts that are of little use to the optimizer. -.. _bitset.test: +.. _type.test: -'``llvm.bitset.test``' Intrinsic +'``llvm.type.test``' Intrinsic ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Syntax: @@ -12284,20 +12278,20 @@ :: - declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone + declare i1 @llvm.type.test(i8* %ptr, metadata %type) nounwind readnone Arguments: """""""""" The first argument is a pointer to be tested. The second argument is a -metadata object representing an identifier for a :doc:`bitset `. +metadata object representing a :doc:`type identifier `. Overview: """"""""" -The ``llvm.bitset.test`` intrinsic tests whether the given pointer is a -member of the given bitset. +The ``llvm.type.test`` intrinsic tests whether the given pointer is associated +with the given type identifier. '``llvm.donothing``' Intrinsic ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Index: llvm/trunk/docs/TypeMetadata.rst =================================================================== --- llvm/trunk/docs/TypeMetadata.rst +++ llvm/trunk/docs/TypeMetadata.rst @@ -0,0 +1,226 @@ +============= +Type Metadata +============= + +Type metadata is a mechanism that allows IR modules to co-operatively build +pointer sets corresponding to addresses within a given set of globals. LLVM's +`control flow integrity`_ implementation uses this metadata to efficiently +check (at each call site) that a given address corresponds to either a +valid vtable or function pointer for a given class or function type, and its +whole-program devirtualization pass uses the metadata to identify potential +callees for a given virtual call. + +To use the mechanism, a client creates metadata nodes with two elements: + +1. a byte offset into the global (generally zero for functions) +2. a metadata object representing an identifier for the type + +These metadata nodes are associated with globals by using global object +metadata attachments with the ``!type`` metadata kind. + +Each type identifier must exclusively identify either global variables +or functions. + +.. admonition:: Limitation + + The current implementation only supports attaching metadata to functions on + the x86-32 and x86-64 architectures. + +An intrinsic, :ref:`llvm.type.test `, is used to test whether a +given pointer is associated with a type identifier. + +.. _control flow integrity: http://clang.llvm.org/docs/ControlFlowIntegrity.html + +Representing Type Information using Type Metadata +================================================= + +This section describes how Clang represents C++ type information associated with +virtual tables using type metadata. + +Consider the following inheritance hierarchy: + +.. code-block:: c++ + + struct A { + virtual void f(); + }; + + struct B : A { + virtual void f(); + virtual void g(); + }; + + struct C { + virtual void h(); + }; + + struct D : A, C { + virtual void f(); + virtual void h(); + }; + +The virtual table objects for A, B, C and D look like this (under the Itanium ABI): + +.. csv-table:: Virtual Table Layout for A, B, C, D + :header: Class, 0, 1, 2, 3, 4, 5, 6 + + A, A::offset-to-top, &A::rtti, &A::f + B, B::offset-to-top, &B::rtti, &B::f, &B::g + C, C::offset-to-top, &C::rtti, &C::h + D, D::offset-to-top, &D::rtti, &D::f, &D::h, D::offset-to-top, &D::rtti, thunk for &D::h + +When an object of type A is constructed, the address of ``&A::f`` in A's +virtual table object is stored in the object's vtable pointer. In ABI parlance +this address is known as an `address point`_. Similarly, when an object of type +B is constructed, the address of ``&B::f`` is stored in the vtable pointer. In +this way, the vtable in B's virtual table object is compatible with A's vtable. + +D is a little more complicated, due to the use of multiple inheritance. Its +virtual table object contains two vtables, one compatible with A's vtable and +the other compatible with C's vtable. Objects of type D contain two virtual +pointers, one belonging to the A subobject and containing the address of +the vtable compatible with A's vtable, and the other belonging to the C +subobject and containing the address of the vtable compatible with C's vtable. + +The full set of compatibility information for the above class hierarchy is +shown below. The following table shows the name of a class, the offset of an +address point within that class's vtable and the name of one of the classes +with which that address point is compatible. + +.. csv-table:: Type Offsets for A, B, C, D + :header: VTable for, Offset, Compatible Class + + A, 16, A + B, 16, A + , , B + C, 16, C + D, 16, A + , , D + , 48, C + +The next step is to encode this compatibility information into the IR. The way +this is done is to create type metadata named after each of the compatible +classes, with which we associate each of the compatible address points in +each vtable. For example, these type metadata entries encode the compatibility +information for the above hierarchy: + +:: + + @_ZTV1A = constant [...], !type !0 + @_ZTV1B = constant [...], !type !0, !type !1 + @_ZTV1C = constant [...], !type !2 + @_ZTV1D = constant [...], !type !0, !type !3, !type !4 + + !0 = !{i64 16, !"_ZTS1A"} + !1 = !{i64 16, !"_ZTS1B"} + !2 = !{i64 16, !"_ZTS1C"} + !3 = !{i64 16, !"_ZTS1D"} + !4 = !{i64 48, !"_ZTS1C"} + +With this type metadata, we can now use the ``llvm.type.test`` intrinsic to +test whether a given pointer is compatible with a type identifier. Working +backwards, if ``llvm.type.test`` returns true for a particular pointer, +we can also statically determine the identities of the virtual functions +that a particular virtual call may call. For example, if a program assumes +a pointer to be a member of ``!"_ZST1A"``, we know that the address can +be only be one of ``_ZTV1A+16``, ``_ZTV1B+16`` or ``_ZTV1D+16`` (i.e. the +address points of the vtables of A, B and D respectively). If we then load +an address from that pointer, we know that the address can only be one of +``&A::f``, ``&B::f`` or ``&D::f``. + +.. _address point: https://mentorembedded.github.io/cxx-abi/abi.html#vtable-general + +Testing Addresses For Type Membership +===================================== + +If a program tests an address using ``llvm.type.test``, this will cause +a link-time optimization pass, ``LowerTypeTests``, to replace calls to this +intrinsic with efficient code to perform type member tests. At a high level, +the pass will lay out referenced globals in a consecutive memory region in +the object file, construct bit vectors that map onto that memory region, +and generate code at each of the ``llvm.type.test`` call sites to test +pointers against those bit vectors. Because of the layout manipulation, the +globals' definitions must be available at LTO time. For more information, +see the `control flow integrity design document`_. + +A type identifier that identifies functions is transformed into a jump table, +which is a block of code consisting of one branch instruction for each +of the functions associated with the type identifier that branches to the +target function. The pass will redirect any taken function addresses to the +corresponding jump table entry. In the object file's symbol table, the jump +table entries take the identities of the original functions, so that addresses +taken outside the module will pass any verification done inside the module. + +Jump tables may call external functions, so their definitions need not +be available at LTO time. Note that if an externally defined function is +associated with a type identifier, there is no guarantee that its identity +within the module will be the same as its identity outside of the module, +as the former will be the jump table entry if a jump table is necessary. + +The `GlobalLayoutBuilder`_ class is responsible for laying out the globals +efficiently to minimize the sizes of the underlying bitsets. + +.. _control flow integrity design document: http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html + +:Example: + +:: + + target datalayout = "e-p:32:32" + + @a = internal global i32 0, !type !0 + @b = internal global i32 0, !type !0, !type !1 + @c = internal global i32 0, !type !1 + @d = internal global [2 x i32] [i32 0, i32 0], !type !2 + + define void @e() !type !3 { + ret void + } + + define void @f() { + ret void + } + + declare void @g() !type !3 + + !0 = !{i32 0, !"typeid1"} + !1 = !{i32 0, !"typeid2"} + !2 = !{i32 4, !"typeid2"} + !3 = !{i32 0, !"typeid3"} + + declare i1 @llvm.type.test(i8* %ptr, metadata %typeid) nounwind readnone + + define i1 @foo(i32* %p) { + %pi8 = bitcast i32* %p to i8* + %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid1") + ret i1 %x + } + + define i1 @bar(i32* %p) { + %pi8 = bitcast i32* %p to i8* + %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid2") + ret i1 %x + } + + define i1 @baz(void ()* %p) { + %pi8 = bitcast void ()* %p to i8* + %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid3") + ret i1 %x + } + + define void @main() { + %a1 = call i1 @foo(i32* @a) ; returns 1 + %b1 = call i1 @foo(i32* @b) ; returns 1 + %c1 = call i1 @foo(i32* @c) ; returns 0 + %a2 = call i1 @bar(i32* @a) ; returns 0 + %b2 = call i1 @bar(i32* @b) ; returns 1 + %c2 = call i1 @bar(i32* @c) ; returns 1 + %d02 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 0)) ; returns 0 + %d12 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 1)) ; returns 1 + %e = call i1 @baz(void ()* @e) ; returns 1 + %f = call i1 @baz(void ()* @f) ; returns 0 + %g = call i1 @baz(void ()* @g) ; returns 1 + ret void + } + +.. _GlobalLayoutBuilder: http://llvm.org/klaus/llvm/blob/master/include/llvm/Transforms/IPO/LowerTypeTests.h Index: llvm/trunk/docs/index.rst =================================================================== --- llvm/trunk/docs/index.rst +++ llvm/trunk/docs/index.rst @@ -261,7 +261,7 @@ CoverageMappingFormat Statepoints MergeFunctions - BitSets + TypeMetadata FaultMaps MIRLangRef Index: llvm/trunk/include/llvm/Analysis/BitSetUtils.h =================================================================== --- llvm/trunk/include/llvm/Analysis/BitSetUtils.h +++ llvm/trunk/include/llvm/Analysis/BitSetUtils.h @@ -1,38 +0,0 @@ -//===- BitSetUtils.h - Utilities related to pointer bitsets ------*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file contains functions that make it easier to manipulate bitsets for -// devirtualization. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_BITSETUTILS_H -#define LLVM_ANALYSIS_BITSETUTILS_H - -#include "llvm/ADT/SmallVector.h" -#include "llvm/IR/CallSite.h" - -namespace llvm { - -/// A call site that could be devirtualized. -struct DevirtCallSite { - /// The offset from the address point to the virtual function. - uint64_t Offset; - /// The call site itself. - CallSite CS; -}; - -/// Given a call to the intrinsic @llvm.bitset.test, find all devirtualizable -/// call sites based on the call and return them in DevirtCalls. -void findDevirtualizableCalls(SmallVectorImpl &DevirtCalls, - SmallVectorImpl &Assumes, - CallInst *CI); -} - -#endif Index: llvm/trunk/include/llvm/Analysis/TypeMetadataUtils.h =================================================================== --- llvm/trunk/include/llvm/Analysis/TypeMetadataUtils.h +++ llvm/trunk/include/llvm/Analysis/TypeMetadataUtils.h @@ -0,0 +1,38 @@ +//===- TypeMetadataUtils.h - Utilities related to type metadata --*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains functions that make it easier to manipulate type metadata +// for devirtualization. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_TYPEMETADATAUTILS_H +#define LLVM_ANALYSIS_TYPEMETADATAUTILS_H + +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/CallSite.h" + +namespace llvm { + +/// A call site that could be devirtualized. +struct DevirtCallSite { + /// The offset from the address point to the virtual function. + uint64_t Offset; + /// The call site itself. + CallSite CS; +}; + +/// Given a call to the intrinsic @llvm.type.test, find all devirtualizable +/// call sites based on the call and return them in DevirtCalls. +void findDevirtualizableCalls(SmallVectorImpl &DevirtCalls, + SmallVectorImpl &Assumes, + CallInst *CI); +} + +#endif Index: llvm/trunk/include/llvm/IR/GlobalObject.h =================================================================== --- llvm/trunk/include/llvm/IR/GlobalObject.h +++ llvm/trunk/include/llvm/IR/GlobalObject.h @@ -21,6 +21,7 @@ namespace llvm { class Comdat; class MDNode; +class Metadata; class Module; class GlobalObject : public GlobalValue { @@ -114,8 +115,10 @@ /// Erase all metadata attachments with the given kind. void eraseMetadata(unsigned KindID); - /// Copy metadata from Src. - void copyMetadata(const GlobalObject *Src); + /// Copy metadata from Src, adjusting offsets by Offset. + void copyMetadata(const GlobalObject *Src, unsigned Offset); + + void addTypeMetadata(unsigned Offset, Metadata *TypeID); void copyAttributesFrom(const GlobalValue *Src) override; Index: llvm/trunk/include/llvm/IR/Intrinsics.td =================================================================== --- llvm/trunk/include/llvm/IR/Intrinsics.td +++ llvm/trunk/include/llvm/IR/Intrinsics.td @@ -663,9 +663,9 @@ LLVMVectorSameWidth<0, llvm_i1_ty>], [IntrArgMemOnly]>; -// Intrinsics to support bit sets. -def int_bitset_test : Intrinsic<[llvm_i1_ty], [llvm_ptr_ty, llvm_metadata_ty], - [IntrNoMem]>; +// Test whether a pointer is associated with a type metadata identifier. +def int_type_test : Intrinsic<[llvm_i1_ty], [llvm_ptr_ty, llvm_metadata_ty], + [IntrNoMem]>; def int_load_relative: Intrinsic<[llvm_ptr_ty], [llvm_ptr_ty, llvm_anyint_ty], [IntrReadMem, IntrArgMemOnly]>; Index: llvm/trunk/include/llvm/IR/LLVMContext.h =================================================================== --- llvm/trunk/include/llvm/IR/LLVMContext.h +++ llvm/trunk/include/llvm/IR/LLVMContext.h @@ -68,6 +68,7 @@ MD_invariant_group = 16, // "invariant.group" MD_align = 17, // "align" MD_loop = 18, // "llvm.loop" + MD_type = 19, // "type" }; /// Known operand bundle tag IDs, which always have the same value. All Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -192,13 +192,13 @@ void initializeLoopVersioningLICMPass(PassRegistry&); void initializeLoopVersioningPassPass(PassRegistry &); void initializeLowerAtomicLegacyPassPass(PassRegistry &); -void initializeLowerBitSetsPass(PassRegistry&); void initializeLowerEmuTLSPass(PassRegistry&); void initializeLowerExpectIntrinsicPass(PassRegistry&); void initializeLowerGuardIntrinsicPass(PassRegistry&); void initializeLowerIntrinsicsPass(PassRegistry&); void initializeLowerInvokePass(PassRegistry&); void initializeLowerSwitchPass(PassRegistry&); +void initializeLowerTypeTestsPass(PassRegistry&); void initializeMIRPrintingPassPass(PassRegistry&); void initializeMachineBlockFrequencyInfoPass(PassRegistry&); void initializeMachineBlockPlacementPass(PassRegistry&); Index: llvm/trunk/include/llvm/Transforms/IPO.h =================================================================== --- llvm/trunk/include/llvm/Transforms/IPO.h +++ llvm/trunk/include/llvm/Transforms/IPO.h @@ -214,14 +214,14 @@ /// manager. ModulePass *createBarrierNoopPass(); -/// \brief This pass lowers bitset metadata and the llvm.bitset.test intrinsic -/// to bitsets. -ModulePass *createLowerBitSetsPass(); +/// \brief This pass lowers type metadata and the llvm.type.test intrinsic to +/// bitsets. +ModulePass *createLowerTypeTestsPass(); /// \brief This pass export CFI checks for use by external modules. ModulePass *createCrossDSOCFIPass(); -/// \brief This pass implements whole-program devirtualization using bitset +/// \brief This pass implements whole-program devirtualization using type /// metadata. ModulePass *createWholeProgramDevirtPass(); Index: llvm/trunk/include/llvm/Transforms/IPO/LowerBitSets.h =================================================================== --- llvm/trunk/include/llvm/Transforms/IPO/LowerBitSets.h +++ llvm/trunk/include/llvm/Transforms/IPO/LowerBitSets.h @@ -1,205 +0,0 @@ -//===- LowerBitSets.h - Bitset lowering pass --------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines parts of the bitset lowering pass implementation that may -// be usefully unit tested. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TRANSFORMS_IPO_LOWERBITSETS_H -#define LLVM_TRANSFORMS_IPO_LOWERBITSETS_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" - -#include -#include -#include -#include -#include - -namespace llvm { - -class DataLayout; -class GlobalObject; -class Value; -class raw_ostream; - -namespace lowerbitsets { - -struct BitSetInfo { - // The indices of the set bits in the bitset. - std::set Bits; - - // The byte offset into the combined global represented by the bitset. - uint64_t ByteOffset; - - // The size of the bitset in bits. - uint64_t BitSize; - - // Log2 alignment of the bit set relative to the combined global. - // For example, a log2 alignment of 3 means that bits in the bitset - // represent addresses 8 bytes apart. - unsigned AlignLog2; - - bool isSingleOffset() const { - return Bits.size() == 1; - } - - bool isAllOnes() const { - return Bits.size() == BitSize; - } - - bool containsGlobalOffset(uint64_t Offset) const; - - bool containsValue(const DataLayout &DL, - const DenseMap &GlobalLayout, - Value *V, uint64_t COffset = 0) const; - - void print(raw_ostream &OS) const; -}; - -struct BitSetBuilder { - SmallVector Offsets; - uint64_t Min, Max; - - BitSetBuilder() : Min(std::numeric_limits::max()), Max(0) {} - - void addOffset(uint64_t Offset) { - if (Min > Offset) - Min = Offset; - if (Max < Offset) - Max = Offset; - - Offsets.push_back(Offset); - } - - BitSetInfo build(); -}; - -/// This class implements a layout algorithm for globals referenced by bit sets -/// that tries to keep members of small bit sets together. This can -/// significantly reduce bit set sizes in many cases. -/// -/// It works by assembling fragments of layout from sets of referenced globals. -/// Each set of referenced globals causes the algorithm to create a new -/// fragment, which is assembled by appending each referenced global in the set -/// into the fragment. If a referenced global has already been referenced by an -/// fragment created earlier, we instead delete that fragment and append its -/// contents into the fragment we are assembling. -/// -/// By starting with the smallest fragments, we minimize the size of the -/// fragments that are copied into larger fragments. This is most intuitively -/// thought about when considering the case where the globals are virtual tables -/// and the bit sets represent their derived classes: in a single inheritance -/// hierarchy, the optimum layout would involve a depth-first search of the -/// class hierarchy (and in fact the computed layout ends up looking a lot like -/// a DFS), but a naive DFS would not work well in the presence of multiple -/// inheritance. This aspect of the algorithm ends up fitting smaller -/// hierarchies inside larger ones where that would be beneficial. -/// -/// For example, consider this class hierarchy: -/// -/// A B -/// \ / | \ -/// C D E -/// -/// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and -/// bsE (E). If we laid out our objects by DFS traversing B followed by A, our -/// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to -/// cover the only 4 objects in its hierarchy, but not for bsA as it needs to -/// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows: -/// -/// Add bsC, fragments {{C}} -/// Add bsD, fragments {{C}, {D}} -/// Add bsE, fragments {{C}, {D}, {E}} -/// Add bsA, fragments {{A, C}, {D}, {E}} -/// Add bsB, fragments {{B, A, C, D, E}} -/// -/// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3 -/// fewer) objects, at the cost of bsB needing to cover 1 more object. -/// -/// The bit set lowering pass assigns an object index to each object that needs -/// to be laid out, and calls addFragment for each bit set passing the object -/// indices of its referenced globals. It then assembles a layout from the -/// computed layout in the Fragments field. -struct GlobalLayoutBuilder { - /// The computed layout. Each element of this vector contains a fragment of - /// layout (which may be empty) consisting of object indices. - std::vector> Fragments; - - /// Mapping from object index to fragment index. - std::vector FragmentMap; - - GlobalLayoutBuilder(uint64_t NumObjects) - : Fragments(1), FragmentMap(NumObjects) {} - - /// Add F to the layout while trying to keep its indices contiguous. - /// If a previously seen fragment uses any of F's indices, that - /// fragment will be laid out inside F. - void addFragment(const std::set &F); -}; - -/// This class is used to build a byte array containing overlapping bit sets. By -/// loading from indexed offsets into the byte array and applying a mask, a -/// program can test bits from the bit set with a relatively short instruction -/// sequence. For example, suppose we have 15 bit sets to lay out: -/// -/// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits), -/// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits), -/// L (4 bits), M (3 bits), N (2 bits), O (1 bit) -/// -/// These bits can be laid out in a 16-byte array like this: -/// -/// Byte Offset -/// 0123456789ABCDEF -/// Bit -/// 7 HHHHHHHHHIIIIIII -/// 6 GGGGGGGGGGJJJJJJ -/// 5 FFFFFFFFFFFKKKKK -/// 4 EEEEEEEEEEEELLLL -/// 3 DDDDDDDDDDDDDMMM -/// 2 CCCCCCCCCCCCCCNN -/// 1 BBBBBBBBBBBBBBBO -/// 0 AAAAAAAAAAAAAAAA -/// -/// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to -/// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done -/// in 1-2 machine instructions on x86, or 4-6 instructions on ARM. -/// -/// This is a byte array, rather than (say) a 2-byte array or a 4-byte array, -/// because for one thing it gives us better packing (the more bins there are, -/// the less evenly they will be filled), and for another, the instruction -/// sequences can be slightly shorter, both on x86 and ARM. -struct ByteArrayBuilder { - /// The byte array built so far. - std::vector Bytes; - - enum { BitsPerByte = 8 }; - - /// The number of bytes allocated so far for each of the bits. - uint64_t BitAllocs[BitsPerByte]; - - ByteArrayBuilder() { - memset(BitAllocs, 0, sizeof(BitAllocs)); - } - - /// Allocate BitSize bits in the byte array where Bits contains the bits to - /// set. AllocByteOffset is set to the offset within the byte array and - /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest - /// Processing Time) multiprocessor scheduling algorithm to lay out the bits - /// efficiently; the pass allocates bit sets in decreasing size order. - void allocate(const std::set &Bits, uint64_t BitSize, - uint64_t &AllocByteOffset, uint8_t &AllocMask); -}; - -} // end namespace lowerbitsets -} // end namespace llvm - -#endif // LLVM_TRANSFORMS_IPO_LOWERBITSETS_H Index: llvm/trunk/include/llvm/Transforms/IPO/LowerTypeTests.h =================================================================== --- llvm/trunk/include/llvm/Transforms/IPO/LowerTypeTests.h +++ llvm/trunk/include/llvm/Transforms/IPO/LowerTypeTests.h @@ -0,0 +1,205 @@ +//===- LowerTypeTests.h - type metadata lowering pass -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines parts of the type test lowering pass implementation that +// may be usefully unit tested. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H +#define LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" + +#include +#include +#include +#include +#include + +namespace llvm { + +class DataLayout; +class GlobalObject; +class Value; +class raw_ostream; + +namespace lowertypetests { + +struct BitSetInfo { + // The indices of the set bits in the bitset. + std::set Bits; + + // The byte offset into the combined global represented by the bitset. + uint64_t ByteOffset; + + // The size of the bitset in bits. + uint64_t BitSize; + + // Log2 alignment of the bit set relative to the combined global. + // For example, a log2 alignment of 3 means that bits in the bitset + // represent addresses 8 bytes apart. + unsigned AlignLog2; + + bool isSingleOffset() const { + return Bits.size() == 1; + } + + bool isAllOnes() const { + return Bits.size() == BitSize; + } + + bool containsGlobalOffset(uint64_t Offset) const; + + bool containsValue(const DataLayout &DL, + const DenseMap &GlobalLayout, + Value *V, uint64_t COffset = 0) const; + + void print(raw_ostream &OS) const; +}; + +struct BitSetBuilder { + SmallVector Offsets; + uint64_t Min, Max; + + BitSetBuilder() : Min(std::numeric_limits::max()), Max(0) {} + + void addOffset(uint64_t Offset) { + if (Min > Offset) + Min = Offset; + if (Max < Offset) + Max = Offset; + + Offsets.push_back(Offset); + } + + BitSetInfo build(); +}; + +/// This class implements a layout algorithm for globals referenced by bit sets +/// that tries to keep members of small bit sets together. This can +/// significantly reduce bit set sizes in many cases. +/// +/// It works by assembling fragments of layout from sets of referenced globals. +/// Each set of referenced globals causes the algorithm to create a new +/// fragment, which is assembled by appending each referenced global in the set +/// into the fragment. If a referenced global has already been referenced by an +/// fragment created earlier, we instead delete that fragment and append its +/// contents into the fragment we are assembling. +/// +/// By starting with the smallest fragments, we minimize the size of the +/// fragments that are copied into larger fragments. This is most intuitively +/// thought about when considering the case where the globals are virtual tables +/// and the bit sets represent their derived classes: in a single inheritance +/// hierarchy, the optimum layout would involve a depth-first search of the +/// class hierarchy (and in fact the computed layout ends up looking a lot like +/// a DFS), but a naive DFS would not work well in the presence of multiple +/// inheritance. This aspect of the algorithm ends up fitting smaller +/// hierarchies inside larger ones where that would be beneficial. +/// +/// For example, consider this class hierarchy: +/// +/// A B +/// \ / | \ +/// C D E +/// +/// We have five bit sets: bsA (A, C), bsB (B, C, D, E), bsC (C), bsD (D) and +/// bsE (E). If we laid out our objects by DFS traversing B followed by A, our +/// layout would be {B, C, D, E, A}. This is optimal for bsB as it needs to +/// cover the only 4 objects in its hierarchy, but not for bsA as it needs to +/// cover 5 objects, i.e. the entire layout. Our algorithm proceeds as follows: +/// +/// Add bsC, fragments {{C}} +/// Add bsD, fragments {{C}, {D}} +/// Add bsE, fragments {{C}, {D}, {E}} +/// Add bsA, fragments {{A, C}, {D}, {E}} +/// Add bsB, fragments {{B, A, C, D, E}} +/// +/// This layout is optimal for bsA, as it now only needs to cover two (i.e. 3 +/// fewer) objects, at the cost of bsB needing to cover 1 more object. +/// +/// The bit set lowering pass assigns an object index to each object that needs +/// to be laid out, and calls addFragment for each bit set passing the object +/// indices of its referenced globals. It then assembles a layout from the +/// computed layout in the Fragments field. +struct GlobalLayoutBuilder { + /// The computed layout. Each element of this vector contains a fragment of + /// layout (which may be empty) consisting of object indices. + std::vector> Fragments; + + /// Mapping from object index to fragment index. + std::vector FragmentMap; + + GlobalLayoutBuilder(uint64_t NumObjects) + : Fragments(1), FragmentMap(NumObjects) {} + + /// Add F to the layout while trying to keep its indices contiguous. + /// If a previously seen fragment uses any of F's indices, that + /// fragment will be laid out inside F. + void addFragment(const std::set &F); +}; + +/// This class is used to build a byte array containing overlapping bit sets. By +/// loading from indexed offsets into the byte array and applying a mask, a +/// program can test bits from the bit set with a relatively short instruction +/// sequence. For example, suppose we have 15 bit sets to lay out: +/// +/// A (16 bits), B (15 bits), C (14 bits), D (13 bits), E (12 bits), +/// F (11 bits), G (10 bits), H (9 bits), I (7 bits), J (6 bits), K (5 bits), +/// L (4 bits), M (3 bits), N (2 bits), O (1 bit) +/// +/// These bits can be laid out in a 16-byte array like this: +/// +/// Byte Offset +/// 0123456789ABCDEF +/// Bit +/// 7 HHHHHHHHHIIIIIII +/// 6 GGGGGGGGGGJJJJJJ +/// 5 FFFFFFFFFFFKKKKK +/// 4 EEEEEEEEEEEELLLL +/// 3 DDDDDDDDDDDDDMMM +/// 2 CCCCCCCCCCCCCCNN +/// 1 BBBBBBBBBBBBBBBO +/// 0 AAAAAAAAAAAAAAAA +/// +/// For example, to test bit X of A, we evaluate ((bits[X] & 1) != 0), or to +/// test bit X of I, we evaluate ((bits[9 + X] & 0x80) != 0). This can be done +/// in 1-2 machine instructions on x86, or 4-6 instructions on ARM. +/// +/// This is a byte array, rather than (say) a 2-byte array or a 4-byte array, +/// because for one thing it gives us better packing (the more bins there are, +/// the less evenly they will be filled), and for another, the instruction +/// sequences can be slightly shorter, both on x86 and ARM. +struct ByteArrayBuilder { + /// The byte array built so far. + std::vector Bytes; + + enum { BitsPerByte = 8 }; + + /// The number of bytes allocated so far for each of the bits. + uint64_t BitAllocs[BitsPerByte]; + + ByteArrayBuilder() { + memset(BitAllocs, 0, sizeof(BitAllocs)); + } + + /// Allocate BitSize bits in the byte array where Bits contains the bits to + /// set. AllocByteOffset is set to the offset within the byte array and + /// AllocMask is set to the bitmask for those bits. This uses the LPT (Longest + /// Processing Time) multiprocessor scheduling algorithm to lay out the bits + /// efficiently; the pass allocates bit sets in decreasing size order. + void allocate(const std::set &Bits, uint64_t BitSize, + uint64_t &AllocByteOffset, uint8_t &AllocMask); +}; + +} // end namespace lowertypetests +} // end namespace llvm + +#endif // LLVM_TRANSFORMS_IPO_LOWERTYPETESTS_H Index: llvm/trunk/include/llvm/Transforms/IPO/WholeProgramDevirt.h =================================================================== --- llvm/trunk/include/llvm/Transforms/IPO/WholeProgramDevirt.h +++ llvm/trunk/include/llvm/Transforms/IPO/WholeProgramDevirt.h @@ -99,32 +99,33 @@ AccumBitVector After; }; -// Information about an entry in a particular bitset. -struct BitSetInfo { +// Information about a member of a particular type identifier. +struct TypeMemberInfo { // The VTableBits for the vtable. VTableBits *Bits; // The offset in bytes from the start of the vtable (i.e. the address point). uint64_t Offset; - bool operator<(const BitSetInfo &other) const { + bool operator<(const TypeMemberInfo &other) const { return Bits < other.Bits || (Bits == other.Bits && Offset < other.Offset); } }; // A virtual call target, i.e. an entry in a particular vtable. struct VirtualCallTarget { - VirtualCallTarget(Function *Fn, const BitSetInfo *BS); + VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM); // For testing only. - VirtualCallTarget(const BitSetInfo *BS, bool IsBigEndian) - : Fn(nullptr), BS(BS), IsBigEndian(IsBigEndian) {} + VirtualCallTarget(const TypeMemberInfo *TM, bool IsBigEndian) + : Fn(nullptr), TM(TM), IsBigEndian(IsBigEndian) {} // The function stored in the vtable. Function *Fn; - // A pointer to the bitset through which the pointer to Fn is accessed. - const BitSetInfo *BS; + // A pointer to the type identifier member through which the pointer to Fn is + // accessed. + const TypeMemberInfo *TM; // When doing virtual constant propagation, this stores the return value for // the function when passed the currently considered argument list. @@ -137,37 +138,37 @@ // the vtable object before the address point (e.g. RTTI, access-to-top, // vtables for other base classes) and is equal to the offset from the start // of the vtable object to the address point. - uint64_t minBeforeBytes() const { return BS->Offset; } + uint64_t minBeforeBytes() const { return TM->Offset; } // The minimum byte offset after the address point. This covers the bytes in // the vtable object after the address point (e.g. the vtable for the current // class and any later base classes) and is equal to the size of the vtable // object minus the offset from the start of the vtable object to the address // point. - uint64_t minAfterBytes() const { return BS->Bits->ObjectSize - BS->Offset; } + uint64_t minAfterBytes() const { return TM->Bits->ObjectSize - TM->Offset; } // The number of bytes allocated (for the vtable plus the byte array) before // the address point. uint64_t allocatedBeforeBytes() const { - return minBeforeBytes() + BS->Bits->Before.Bytes.size(); + return minBeforeBytes() + TM->Bits->Before.Bytes.size(); } // The number of bytes allocated (for the vtable plus the byte array) after // the address point. uint64_t allocatedAfterBytes() const { - return minAfterBytes() + BS->Bits->After.Bytes.size(); + return minAfterBytes() + TM->Bits->After.Bytes.size(); } // Set the bit at position Pos before the address point to RetVal. void setBeforeBit(uint64_t Pos) { assert(Pos >= 8 * minBeforeBytes()); - BS->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal); + TM->Bits->Before.setBit(Pos - 8 * minBeforeBytes(), RetVal); } // Set the bit at position Pos after the address point to RetVal. void setAfterBit(uint64_t Pos) { assert(Pos >= 8 * minAfterBytes()); - BS->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal); + TM->Bits->After.setBit(Pos - 8 * minAfterBytes(), RetVal); } // Set the bytes at position Pos before the address point to RetVal. @@ -176,18 +177,18 @@ void setBeforeBytes(uint64_t Pos, uint8_t Size) { assert(Pos >= 8 * minBeforeBytes()); if (IsBigEndian) - BS->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size); + TM->Bits->Before.setLE(Pos - 8 * minBeforeBytes(), RetVal, Size); else - BS->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size); + TM->Bits->Before.setBE(Pos - 8 * minBeforeBytes(), RetVal, Size); } // Set the bytes at position Pos after the address point to RetVal. void setAfterBytes(uint64_t Pos, uint8_t Size) { assert(Pos >= 8 * minAfterBytes()); if (IsBigEndian) - BS->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size); + TM->Bits->After.setBE(Pos - 8 * minAfterBytes(), RetVal, Size); else - BS->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size); + TM->Bits->After.setLE(Pos - 8 * minAfterBytes(), RetVal, Size); } }; Index: llvm/trunk/lib/Analysis/BitSetUtils.cpp =================================================================== --- llvm/trunk/lib/Analysis/BitSetUtils.cpp +++ llvm/trunk/lib/Analysis/BitSetUtils.cpp @@ -1,82 +0,0 @@ -//===- BitSetUtils.cpp - Utilities related to pointer bitsets -------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file contains functions that make it easier to manipulate bitsets for -// devirtualization. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/BitSetUtils.h" -#include "llvm/IR/Intrinsics.h" -#include "llvm/IR/Module.h" - -using namespace llvm; - -// Search for virtual calls that call FPtr and add them to DevirtCalls. -static void -findCallsAtConstantOffset(SmallVectorImpl &DevirtCalls, - Value *FPtr, uint64_t Offset) { - for (const Use &U : FPtr->uses()) { - Value *User = U.getUser(); - if (isa(User)) { - findCallsAtConstantOffset(DevirtCalls, User, Offset); - } else if (auto CI = dyn_cast(User)) { - DevirtCalls.push_back({Offset, CI}); - } else if (auto II = dyn_cast(User)) { - DevirtCalls.push_back({Offset, II}); - } - } -} - -// Search for virtual calls that load from VPtr and add them to DevirtCalls. -static void -findLoadCallsAtConstantOffset(Module *M, - SmallVectorImpl &DevirtCalls, - Value *VPtr, uint64_t Offset) { - for (const Use &U : VPtr->uses()) { - Value *User = U.getUser(); - if (isa(User)) { - findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset); - } else if (isa(User)) { - findCallsAtConstantOffset(DevirtCalls, User, Offset); - } else if (auto GEP = dyn_cast(User)) { - // Take into account the GEP offset. - if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) { - SmallVector Indices(GEP->op_begin() + 1, GEP->op_end()); - uint64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType( - GEP->getSourceElementType(), Indices); - findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset + GEPOffset); - } - } - } -} - -void llvm::findDevirtualizableCalls( - SmallVectorImpl &DevirtCalls, - SmallVectorImpl &Assumes, CallInst *CI) { - assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::bitset_test); - - Module *M = CI->getParent()->getParent()->getParent(); - - // Find llvm.assume intrinsics for this llvm.bitset.test call. - for (const Use &CIU : CI->uses()) { - auto AssumeCI = dyn_cast(CIU.getUser()); - if (AssumeCI) { - Function *F = AssumeCI->getCalledFunction(); - if (F && F->getIntrinsicID() == Intrinsic::assume) - Assumes.push_back(AssumeCI); - } - } - - // If we found any, search for virtual calls based on %p and add them to - // DevirtCalls. - if (!Assumes.empty()) - findLoadCallsAtConstantOffset(M, DevirtCalls, - CI->getArgOperand(0)->stripPointerCasts(), 0); -} Index: llvm/trunk/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Analysis/CMakeLists.txt +++ llvm/trunk/lib/Analysis/CMakeLists.txt @@ -5,7 +5,6 @@ Analysis.cpp AssumptionCache.cpp BasicAliasAnalysis.cpp - BitSetUtils.cpp BlockFrequencyInfo.cpp BlockFrequencyInfoImpl.cpp BranchProbabilityInfo.cpp @@ -71,6 +70,7 @@ TargetTransformInfo.cpp Trace.cpp TypeBasedAliasAnalysis.cpp + TypeMetadataUtils.cpp ScopedNoAliasAA.cpp ValueTracking.cpp VectorUtils.cpp Index: llvm/trunk/lib/Analysis/TypeMetadataUtils.cpp =================================================================== --- llvm/trunk/lib/Analysis/TypeMetadataUtils.cpp +++ llvm/trunk/lib/Analysis/TypeMetadataUtils.cpp @@ -0,0 +1,82 @@ +//===- TypeMetadataUtils.cpp - Utilities related to type metadata ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains functions that make it easier to manipulate type metadata +// for devirtualization. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/TypeMetadataUtils.h" +#include "llvm/IR/Intrinsics.h" +#include "llvm/IR/Module.h" + +using namespace llvm; + +// Search for virtual calls that call FPtr and add them to DevirtCalls. +static void +findCallsAtConstantOffset(SmallVectorImpl &DevirtCalls, + Value *FPtr, uint64_t Offset) { + for (const Use &U : FPtr->uses()) { + Value *User = U.getUser(); + if (isa(User)) { + findCallsAtConstantOffset(DevirtCalls, User, Offset); + } else if (auto CI = dyn_cast(User)) { + DevirtCalls.push_back({Offset, CI}); + } else if (auto II = dyn_cast(User)) { + DevirtCalls.push_back({Offset, II}); + } + } +} + +// Search for virtual calls that load from VPtr and add them to DevirtCalls. +static void +findLoadCallsAtConstantOffset(Module *M, + SmallVectorImpl &DevirtCalls, + Value *VPtr, uint64_t Offset) { + for (const Use &U : VPtr->uses()) { + Value *User = U.getUser(); + if (isa(User)) { + findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset); + } else if (isa(User)) { + findCallsAtConstantOffset(DevirtCalls, User, Offset); + } else if (auto GEP = dyn_cast(User)) { + // Take into account the GEP offset. + if (VPtr == GEP->getPointerOperand() && GEP->hasAllConstantIndices()) { + SmallVector Indices(GEP->op_begin() + 1, GEP->op_end()); + uint64_t GEPOffset = M->getDataLayout().getIndexedOffsetInType( + GEP->getSourceElementType(), Indices); + findLoadCallsAtConstantOffset(M, DevirtCalls, User, Offset + GEPOffset); + } + } + } +} + +void llvm::findDevirtualizableCalls( + SmallVectorImpl &DevirtCalls, + SmallVectorImpl &Assumes, CallInst *CI) { + assert(CI->getCalledFunction()->getIntrinsicID() == Intrinsic::type_test); + + Module *M = CI->getParent()->getParent()->getParent(); + + // Find llvm.assume intrinsics for this llvm.type.test call. + for (const Use &CIU : CI->uses()) { + auto AssumeCI = dyn_cast(CIU.getUser()); + if (AssumeCI) { + Function *F = AssumeCI->getCalledFunction(); + if (F && F->getIntrinsicID() == Intrinsic::assume) + Assumes.push_back(AssumeCI); + } + } + + // If we found any, search for virtual calls based on %p and add them to + // DevirtCalls. + if (!Assumes.empty()) + findLoadCallsAtConstantOffset(M, DevirtCalls, + CI->getArgOperand(0)->stripPointerCasts(), 0); +} Index: llvm/trunk/lib/IR/LLVMContext.cpp =================================================================== --- llvm/trunk/lib/IR/LLVMContext.cpp +++ llvm/trunk/lib/IR/LLVMContext.cpp @@ -134,6 +134,10 @@ assert(LoopID == MD_loop && "llvm.loop kind id drifted"); (void)LoopID; + unsigned TypeID = getMDKindID("type"); + assert(TypeID == MD_type && "type kind id drifted"); + (void)TypeID; + auto *DeoptEntry = pImpl->getOrInsertBundleTag("deopt"); assert(DeoptEntry->second == LLVMContext::OB_deopt && "deopt operand bundle id drifted!"); Index: llvm/trunk/lib/IR/Metadata.cpp =================================================================== --- llvm/trunk/lib/IR/Metadata.cpp +++ llvm/trunk/lib/IR/Metadata.cpp @@ -1393,11 +1393,32 @@ return getMetadata(getContext().getMDKindID(Kind)); } -void GlobalObject::copyMetadata(const GlobalObject *Other) { +void GlobalObject::copyMetadata(const GlobalObject *Other, unsigned Offset) { SmallVector, 8> MDs; Other->getAllMetadata(MDs); - for (auto &MD : MDs) + for (auto &MD : MDs) { + // We need to adjust the type metadata offset. + if (Offset != 0 && MD.first == LLVMContext::MD_type) { + auto *OffsetConst = cast( + cast(MD.second->getOperand(0))->getValue()); + Metadata *TypeId = MD.second->getOperand(1); + auto *NewOffsetMD = ConstantAsMetadata::get(ConstantInt::get( + OffsetConst->getType(), OffsetConst->getValue() + Offset)); + addMetadata(LLVMContext::MD_type, + *MDNode::get(getContext(), {NewOffsetMD, TypeId})); + continue; + } addMetadata(MD.first, *MD.second); + } +} + +void GlobalObject::addTypeMetadata(unsigned Offset, Metadata *TypeID) { + addMetadata( + LLVMContext::MD_type, + *MDTuple::get(getContext(), + {llvm::ConstantAsMetadata::get(llvm::ConstantInt::get( + Type::getInt64Ty(getContext()), Offset)), + TypeID})); } void Function::setSubprogram(DISubprogram *SP) { Index: llvm/trunk/lib/Linker/IRMover.cpp =================================================================== --- llvm/trunk/lib/Linker/IRMover.cpp +++ llvm/trunk/lib/Linker/IRMover.cpp @@ -641,7 +641,7 @@ if (auto *NewGO = dyn_cast(NewGV)) { // Metadata for global variables and function declarations is copied eagerly. if (isa(SGV) || SGV->isDeclaration()) - NewGO->copyMetadata(cast(SGV)); + NewGO->copyMetadata(cast(SGV), 0); } // Remove these copied constants in case this stays a declaration, since @@ -967,7 +967,7 @@ Dst.setPersonalityFn(Src.getPersonalityFn()); // Copy over the metadata attachments without remapping. - Dst.copyMetadata(&Src); + Dst.copyMetadata(&Src, 0); // Steal arguments and splice the body of Src into Dst. Dst.stealArgumentListFrom(Src); Index: llvm/trunk/lib/Transforms/IPO/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Transforms/IPO/CMakeLists.txt +++ llvm/trunk/lib/Transforms/IPO/CMakeLists.txt @@ -19,7 +19,7 @@ Inliner.cpp Internalize.cpp LoopExtractor.cpp - LowerBitSets.cpp + LowerTypeTests.cpp MergeFunctions.cpp PartialInlining.cpp PassManagerBuilder.cpp Index: llvm/trunk/lib/Transforms/IPO/CrossDSOCFI.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/CrossDSOCFI.cpp +++ llvm/trunk/lib/Transforms/IPO/CrossDSOCFI.cpp @@ -36,7 +36,7 @@ #define DEBUG_TYPE "cross-dso-cfi" -STATISTIC(TypeIds, "Number of unique type identifiers"); +STATISTIC(NumTypeIds, "Number of unique type identifiers"); namespace { @@ -49,7 +49,7 @@ Module *M; MDNode *VeryLikelyWeights; - ConstantInt *extractBitSetTypeId(MDNode *MD); + ConstantInt *extractNumericTypeId(MDNode *MD); void buildCFICheck(); bool doInitialization(Module &M) override; @@ -73,10 +73,10 @@ return false; } -/// extractBitSetTypeId - Extracts TypeId from a hash-based bitset MDNode. -ConstantInt *CrossDSOCFI::extractBitSetTypeId(MDNode *MD) { +/// Extracts a numeric type identifier from an MDNode containing type metadata. +ConstantInt *CrossDSOCFI::extractNumericTypeId(MDNode *MD) { // This check excludes vtables for classes inside anonymous namespaces. - auto TM = dyn_cast(MD->getOperand(0)); + auto TM = dyn_cast(MD->getOperand(1)); if (!TM) return nullptr; auto C = dyn_cast_or_null(TM->getValue()); @@ -84,29 +84,27 @@ // We are looking for i64 constants. if (C->getBitWidth() != 64) return nullptr; - // Sanity check. - auto FM = dyn_cast_or_null(MD->getOperand(1)); - // Can be null if a function was removed by an optimization. - if (FM) { - auto F = dyn_cast(FM->getValue()); - // But can never be a function declaration. - assert(!F || !F->isDeclaration()); - (void)F; // Suppress unused variable warning in the no-asserts build. - } return C; } /// buildCFICheck - emits __cfi_check for the current module. void CrossDSOCFI::buildCFICheck() { // FIXME: verify that __cfi_check ends up near the end of the code section, - // but before the jump slots created in LowerBitSets. - llvm::DenseSet BitSetIds; - NamedMDNode *BitSetNM = M->getNamedMetadata("llvm.bitsets"); - - if (BitSetNM) - for (unsigned I = 0, E = BitSetNM->getNumOperands(); I != E; ++I) - if (ConstantInt *TypeId = extractBitSetTypeId(BitSetNM->getOperand(I))) - BitSetIds.insert(TypeId->getZExtValue()); + // but before the jump slots created in LowerTypeTests. + llvm::DenseSet TypeIds; + SmallVector Types; + for (GlobalObject &GO : M->global_objects()) { + Types.clear(); + GO.getMetadata(LLVMContext::MD_type, Types); + for (MDNode *Type : Types) { + // Sanity check. GO must not be a function declaration. + auto F = dyn_cast(&GO); + assert(!F || !F->isDeclaration()); + + if (ConstantInt *TypeId = extractNumericTypeId(Type)) + TypeIds.insert(TypeId->getZExtValue()); + } + } LLVMContext &Ctx = M->getContext(); Constant *C = M->getOrInsertFunction( @@ -138,13 +136,12 @@ IRBExit.CreateRetVoid(); IRBuilder<> IRB(BB); - SwitchInst *SI = IRB.CreateSwitch(&CallSiteTypeId, TrapBB, BitSetIds.size()); - for (uint64_t TypeId : BitSetIds) { + SwitchInst *SI = IRB.CreateSwitch(&CallSiteTypeId, TrapBB, TypeIds.size()); + for (uint64_t TypeId : TypeIds) { ConstantInt *CaseTypeId = ConstantInt::get(Type::getInt64Ty(Ctx), TypeId); BasicBlock *TestBB = BasicBlock::Create(Ctx, "test", F); IRBuilder<> IRBTest(TestBB); - Function *BitsetTestFn = - Intrinsic::getDeclaration(M, Intrinsic::bitset_test); + Function *BitsetTestFn = Intrinsic::getDeclaration(M, Intrinsic::type_test); Value *Test = IRBTest.CreateCall( BitsetTestFn, {&Addr, MetadataAsValue::get( @@ -153,7 +150,7 @@ BI->setMetadata(LLVMContext::MD_prof, VeryLikelyWeights); SI->addCase(CaseTypeId, TestBB); - ++TypeIds; + ++NumTypeIds; } } Index: llvm/trunk/lib/Transforms/IPO/IPO.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/IPO.cpp +++ llvm/trunk/lib/Transforms/IPO/IPO.cpp @@ -39,7 +39,7 @@ initializeLoopExtractorPass(Registry); initializeBlockExtractorPassPass(Registry); initializeSingleLoopExtractorPass(Registry); - initializeLowerBitSetsPass(Registry); + initializeLowerTypeTestsPass(Registry); initializeMergeFunctionsPass(Registry); initializePartialInlinerPass(Registry); initializePostOrderFunctionAttrsLegacyPassPass(Registry); Index: llvm/trunk/lib/Transforms/IPO/LowerBitSets.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/LowerBitSets.cpp +++ llvm/trunk/lib/Transforms/IPO/LowerBitSets.cpp @@ -1,1060 +0,0 @@ -//===-- LowerBitSets.cpp - Bitset lowering pass ---------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass lowers bitset metadata and calls to the llvm.bitset.test intrinsic. -// See http://llvm.org/docs/LangRef.html#bitsets for more information. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/IPO/LowerBitSets.h" -#include "llvm/Transforms/IPO.h" -#include "llvm/ADT/EquivalenceClasses.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/Triple.h" -#include "llvm/IR/Constant.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/GlobalObject.h" -#include "llvm/IR/GlobalVariable.h" -#include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/Intrinsics.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/Operator.h" -#include "llvm/Pass.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Transforms/Utils/BasicBlockUtils.h" - -using namespace llvm; -using namespace lowerbitsets; - -#define DEBUG_TYPE "lowerbitsets" - -STATISTIC(ByteArraySizeBits, "Byte array size in bits"); -STATISTIC(ByteArraySizeBytes, "Byte array size in bytes"); -STATISTIC(NumByteArraysCreated, "Number of byte arrays created"); -STATISTIC(NumBitSetCallsLowered, "Number of bitset calls lowered"); -STATISTIC(NumBitSetDisjointSets, "Number of disjoint sets of bitsets"); - -static cl::opt AvoidReuse( - "lowerbitsets-avoid-reuse", - cl::desc("Try to avoid reuse of byte array addresses using aliases"), - cl::Hidden, cl::init(true)); - -bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const { - if (Offset < ByteOffset) - return false; - - if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0) - return false; - - uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2; - if (BitOffset >= BitSize) - return false; - - return Bits.count(BitOffset); -} - -bool BitSetInfo::containsValue( - const DataLayout &DL, - const DenseMap &GlobalLayout, Value *V, - uint64_t COffset) const { - if (auto GV = dyn_cast(V)) { - auto I = GlobalLayout.find(GV); - if (I == GlobalLayout.end()) - return false; - return containsGlobalOffset(I->second + COffset); - } - - if (auto GEP = dyn_cast(V)) { - APInt APOffset(DL.getPointerSizeInBits(0), 0); - bool Result = GEP->accumulateConstantOffset(DL, APOffset); - if (!Result) - return false; - COffset += APOffset.getZExtValue(); - return containsValue(DL, GlobalLayout, GEP->getPointerOperand(), - COffset); - } - - if (auto Op = dyn_cast(V)) { - if (Op->getOpcode() == Instruction::BitCast) - return containsValue(DL, GlobalLayout, Op->getOperand(0), COffset); - - if (Op->getOpcode() == Instruction::Select) - return containsValue(DL, GlobalLayout, Op->getOperand(1), COffset) && - containsValue(DL, GlobalLayout, Op->getOperand(2), COffset); - } - - return false; -} - -void BitSetInfo::print(raw_ostream &OS) const { - OS << "offset " << ByteOffset << " size " << BitSize << " align " - << (1 << AlignLog2); - - if (isAllOnes()) { - OS << " all-ones\n"; - return; - } - - OS << " { "; - for (uint64_t B : Bits) - OS << B << ' '; - OS << "}\n"; -} - -BitSetInfo BitSetBuilder::build() { - if (Min > Max) - Min = 0; - - // Normalize each offset against the minimum observed offset, and compute - // the bitwise OR of each of the offsets. The number of trailing zeros - // in the mask gives us the log2 of the alignment of all offsets, which - // allows us to compress the bitset by only storing one bit per aligned - // address. - uint64_t Mask = 0; - for (uint64_t &Offset : Offsets) { - Offset -= Min; - Mask |= Offset; - } - - BitSetInfo BSI; - BSI.ByteOffset = Min; - - BSI.AlignLog2 = 0; - if (Mask != 0) - BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined); - - // Build the compressed bitset while normalizing the offsets against the - // computed alignment. - BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1; - for (uint64_t Offset : Offsets) { - Offset >>= BSI.AlignLog2; - BSI.Bits.insert(Offset); - } - - return BSI; -} - -void GlobalLayoutBuilder::addFragment(const std::set &F) { - // Create a new fragment to hold the layout for F. - Fragments.emplace_back(); - std::vector &Fragment = Fragments.back(); - uint64_t FragmentIndex = Fragments.size() - 1; - - for (auto ObjIndex : F) { - uint64_t OldFragmentIndex = FragmentMap[ObjIndex]; - if (OldFragmentIndex == 0) { - // We haven't seen this object index before, so just add it to the current - // fragment. - Fragment.push_back(ObjIndex); - } else { - // This index belongs to an existing fragment. Copy the elements of the - // old fragment into this one and clear the old fragment. We don't update - // the fragment map just yet, this ensures that any further references to - // indices from the old fragment in this fragment do not insert any more - // indices. - std::vector &OldFragment = Fragments[OldFragmentIndex]; - Fragment.insert(Fragment.end(), OldFragment.begin(), OldFragment.end()); - OldFragment.clear(); - } - } - - // Update the fragment map to point our object indices to this fragment. - for (uint64_t ObjIndex : Fragment) - FragmentMap[ObjIndex] = FragmentIndex; -} - -void ByteArrayBuilder::allocate(const std::set &Bits, - uint64_t BitSize, uint64_t &AllocByteOffset, - uint8_t &AllocMask) { - // Find the smallest current allocation. - unsigned Bit = 0; - for (unsigned I = 1; I != BitsPerByte; ++I) - if (BitAllocs[I] < BitAllocs[Bit]) - Bit = I; - - AllocByteOffset = BitAllocs[Bit]; - - // Add our size to it. - unsigned ReqSize = AllocByteOffset + BitSize; - BitAllocs[Bit] = ReqSize; - if (Bytes.size() < ReqSize) - Bytes.resize(ReqSize); - - // Set our bits. - AllocMask = 1 << Bit; - for (uint64_t B : Bits) - Bytes[AllocByteOffset + B] |= AllocMask; -} - -namespace { - -struct ByteArrayInfo { - std::set Bits; - uint64_t BitSize; - GlobalVariable *ByteArray; - Constant *Mask; -}; - -struct LowerBitSets : public ModulePass { - static char ID; - LowerBitSets() : ModulePass(ID) { - initializeLowerBitSetsPass(*PassRegistry::getPassRegistry()); - } - - Module *M; - - bool LinkerSubsectionsViaSymbols; - Triple::ArchType Arch; - Triple::ObjectFormatType ObjectFormat; - IntegerType *Int1Ty; - IntegerType *Int8Ty; - IntegerType *Int32Ty; - Type *Int32PtrTy; - IntegerType *Int64Ty; - IntegerType *IntPtrTy; - - // The llvm.bitsets named metadata. - NamedMDNode *BitSetNM; - - // Mapping from bitset identifiers to the call sites that test them. - DenseMap> BitSetTestCallSites; - - std::vector ByteArrayInfos; - - BitSetInfo - buildBitSet(Metadata *BitSet, - const DenseMap &GlobalLayout); - ByteArrayInfo *createByteArray(BitSetInfo &BSI); - void allocateByteArrays(); - Value *createBitSetTest(IRBuilder<> &B, BitSetInfo &BSI, ByteArrayInfo *&BAI, - Value *BitOffset); - void lowerBitSetCalls(ArrayRef BitSets, - Constant *CombinedGlobalAddr, - const DenseMap &GlobalLayout); - Value * - lowerBitSetCall(CallInst *CI, BitSetInfo &BSI, ByteArrayInfo *&BAI, - Constant *CombinedGlobal, - const DenseMap &GlobalLayout); - void buildBitSetsFromGlobalVariables(ArrayRef BitSets, - ArrayRef Globals); - unsigned getJumpTableEntrySize(); - Type *getJumpTableEntryType(); - Constant *createJumpTableEntry(GlobalObject *Src, Function *Dest, - unsigned Distance); - void verifyBitSetMDNode(MDNode *Op); - void buildBitSetsFromFunctions(ArrayRef BitSets, - ArrayRef Functions); - void buildBitSetsFromDisjointSet(ArrayRef BitSets, - ArrayRef Globals); - bool buildBitSets(); - bool eraseBitSetMetadata(); - - bool doInitialization(Module &M) override; - bool runOnModule(Module &M) override; -}; - -} // anonymous namespace - -INITIALIZE_PASS_BEGIN(LowerBitSets, "lowerbitsets", - "Lower bitset metadata", false, false) -INITIALIZE_PASS_END(LowerBitSets, "lowerbitsets", - "Lower bitset metadata", false, false) -char LowerBitSets::ID = 0; - -ModulePass *llvm::createLowerBitSetsPass() { return new LowerBitSets; } - -bool LowerBitSets::doInitialization(Module &Mod) { - M = &Mod; - const DataLayout &DL = Mod.getDataLayout(); - - Triple TargetTriple(M->getTargetTriple()); - LinkerSubsectionsViaSymbols = TargetTriple.isMacOSX(); - Arch = TargetTriple.getArch(); - ObjectFormat = TargetTriple.getObjectFormat(); - - Int1Ty = Type::getInt1Ty(M->getContext()); - Int8Ty = Type::getInt8Ty(M->getContext()); - Int32Ty = Type::getInt32Ty(M->getContext()); - Int32PtrTy = PointerType::getUnqual(Int32Ty); - Int64Ty = Type::getInt64Ty(M->getContext()); - IntPtrTy = DL.getIntPtrType(M->getContext(), 0); - - BitSetNM = M->getNamedMetadata("llvm.bitsets"); - - BitSetTestCallSites.clear(); - - return false; -} - -/// Build a bit set for BitSet using the object layouts in -/// GlobalLayout. -BitSetInfo LowerBitSets::buildBitSet( - Metadata *BitSet, - const DenseMap &GlobalLayout) { - BitSetBuilder BSB; - - // Compute the byte offset of each element of this bitset. - if (BitSetNM) { - for (MDNode *Op : BitSetNM->operands()) { - if (Op->getOperand(0) != BitSet || !Op->getOperand(1)) - continue; - Constant *OpConst = - cast(Op->getOperand(1))->getValue(); - if (auto GA = dyn_cast(OpConst)) - OpConst = GA->getAliasee(); - auto OpGlobal = dyn_cast(OpConst); - if (!OpGlobal) - continue; - uint64_t Offset = - cast(cast(Op->getOperand(2)) - ->getValue())->getZExtValue(); - - Offset += GlobalLayout.find(OpGlobal)->second; - - BSB.addOffset(Offset); - } - } - - return BSB.build(); -} - -/// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in -/// Bits. This pattern matches to the bt instruction on x86. -static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits, - Value *BitOffset) { - auto BitsType = cast(Bits->getType()); - unsigned BitWidth = BitsType->getBitWidth(); - - BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType); - Value *BitIndex = - B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1)); - Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex); - Value *MaskedBits = B.CreateAnd(Bits, BitMask); - return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0)); -} - -ByteArrayInfo *LowerBitSets::createByteArray(BitSetInfo &BSI) { - // Create globals to stand in for byte arrays and masks. These never actually - // get initialized, we RAUW and erase them later in allocateByteArrays() once - // we know the offset and mask to use. - auto ByteArrayGlobal = new GlobalVariable( - *M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr); - auto MaskGlobal = new GlobalVariable( - *M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr); - - ByteArrayInfos.emplace_back(); - ByteArrayInfo *BAI = &ByteArrayInfos.back(); - - BAI->Bits = BSI.Bits; - BAI->BitSize = BSI.BitSize; - BAI->ByteArray = ByteArrayGlobal; - BAI->Mask = ConstantExpr::getPtrToInt(MaskGlobal, Int8Ty); - return BAI; -} - -void LowerBitSets::allocateByteArrays() { - std::stable_sort(ByteArrayInfos.begin(), ByteArrayInfos.end(), - [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) { - return BAI1.BitSize > BAI2.BitSize; - }); - - std::vector ByteArrayOffsets(ByteArrayInfos.size()); - - ByteArrayBuilder BAB; - for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) { - ByteArrayInfo *BAI = &ByteArrayInfos[I]; - - uint8_t Mask; - BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask); - - BAI->Mask->replaceAllUsesWith(ConstantInt::get(Int8Ty, Mask)); - cast(BAI->Mask->getOperand(0))->eraseFromParent(); - } - - Constant *ByteArrayConst = ConstantDataArray::get(M->getContext(), BAB.Bytes); - auto ByteArray = - new GlobalVariable(*M, ByteArrayConst->getType(), /*isConstant=*/true, - GlobalValue::PrivateLinkage, ByteArrayConst); - - for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) { - ByteArrayInfo *BAI = &ByteArrayInfos[I]; - - Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0), - ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])}; - Constant *GEP = ConstantExpr::getInBoundsGetElementPtr( - ByteArrayConst->getType(), ByteArray, Idxs); - - // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures - // that the pc-relative displacement is folded into the lea instead of the - // test instruction getting another displacement. - if (LinkerSubsectionsViaSymbols) { - BAI->ByteArray->replaceAllUsesWith(GEP); - } else { - GlobalAlias *Alias = GlobalAlias::create( - Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, M); - BAI->ByteArray->replaceAllUsesWith(Alias); - } - BAI->ByteArray->eraseFromParent(); - } - - ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] + - BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] + - BAB.BitAllocs[6] + BAB.BitAllocs[7]; - ByteArraySizeBytes = BAB.Bytes.size(); -} - -/// Build a test that bit BitOffset is set in BSI, where -/// BitSetGlobal is a global containing the bits in BSI. -Value *LowerBitSets::createBitSetTest(IRBuilder<> &B, BitSetInfo &BSI, - ByteArrayInfo *&BAI, Value *BitOffset) { - if (BSI.BitSize <= 64) { - // If the bit set is sufficiently small, we can avoid a load by bit testing - // a constant. - IntegerType *BitsTy; - if (BSI.BitSize <= 32) - BitsTy = Int32Ty; - else - BitsTy = Int64Ty; - - uint64_t Bits = 0; - for (auto Bit : BSI.Bits) - Bits |= uint64_t(1) << Bit; - Constant *BitsConst = ConstantInt::get(BitsTy, Bits); - return createMaskedBitTest(B, BitsConst, BitOffset); - } else { - if (!BAI) { - ++NumByteArraysCreated; - BAI = createByteArray(BSI); - } - - Constant *ByteArray = BAI->ByteArray; - Type *Ty = BAI->ByteArray->getValueType(); - if (!LinkerSubsectionsViaSymbols && AvoidReuse) { - // Each use of the byte array uses a different alias. This makes the - // backend less likely to reuse previously computed byte array addresses, - // improving the security of the CFI mechanism based on this pass. - ByteArray = GlobalAlias::create(BAI->ByteArray->getValueType(), 0, - GlobalValue::PrivateLinkage, "bits_use", - ByteArray, M); - } - - Value *ByteAddr = B.CreateGEP(Ty, ByteArray, BitOffset); - Value *Byte = B.CreateLoad(ByteAddr); - - Value *ByteAndMask = B.CreateAnd(Byte, BAI->Mask); - return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0)); - } -} - -/// Lower a llvm.bitset.test call to its implementation. Returns the value to -/// replace the call with. -Value *LowerBitSets::lowerBitSetCall( - CallInst *CI, BitSetInfo &BSI, ByteArrayInfo *&BAI, - Constant *CombinedGlobalIntAddr, - const DenseMap &GlobalLayout) { - Value *Ptr = CI->getArgOperand(0); - const DataLayout &DL = M->getDataLayout(); - - if (BSI.containsValue(DL, GlobalLayout, Ptr)) - return ConstantInt::getTrue(M->getContext()); - - Constant *OffsetedGlobalAsInt = ConstantExpr::getAdd( - CombinedGlobalIntAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)); - - BasicBlock *InitialBB = CI->getParent(); - - IRBuilder<> B(CI); - - Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy); - - if (BSI.isSingleOffset()) - return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt); - - Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt); - - Value *BitOffset; - if (BSI.AlignLog2 == 0) { - BitOffset = PtrOffset; - } else { - // We need to check that the offset both falls within our range and is - // suitably aligned. We can check both properties at the same time by - // performing a right rotate by log2(alignment) followed by an integer - // comparison against the bitset size. The rotate will move the lower - // order bits that need to be zero into the higher order bits of the - // result, causing the comparison to fail if they are nonzero. The rotate - // also conveniently gives us a bit offset to use during the load from - // the bitset. - Value *OffsetSHR = - B.CreateLShr(PtrOffset, ConstantInt::get(IntPtrTy, BSI.AlignLog2)); - Value *OffsetSHL = B.CreateShl( - PtrOffset, - ConstantInt::get(IntPtrTy, DL.getPointerSizeInBits(0) - BSI.AlignLog2)); - BitOffset = B.CreateOr(OffsetSHR, OffsetSHL); - } - - Constant *BitSizeConst = ConstantInt::get(IntPtrTy, BSI.BitSize); - Value *OffsetInRange = B.CreateICmpULT(BitOffset, BitSizeConst); - - // If the bit set is all ones, testing against it is unnecessary. - if (BSI.isAllOnes()) - return OffsetInRange; - - TerminatorInst *Term = SplitBlockAndInsertIfThen(OffsetInRange, CI, false); - IRBuilder<> ThenB(Term); - - // Now that we know that the offset is in range and aligned, load the - // appropriate bit from the bitset. - Value *Bit = createBitSetTest(ThenB, BSI, BAI, BitOffset); - - // The value we want is 0 if we came directly from the initial block - // (having failed the range or alignment checks), or the loaded bit if - // we came from the block in which we loaded it. - B.SetInsertPoint(CI); - PHINode *P = B.CreatePHI(Int1Ty, 2); - P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB); - P->addIncoming(Bit, ThenB.GetInsertBlock()); - return P; -} - -/// Given a disjoint set of bitsets and globals, layout the globals, build the -/// bit sets and lower the llvm.bitset.test calls. -void LowerBitSets::buildBitSetsFromGlobalVariables( - ArrayRef BitSets, ArrayRef Globals) { - // Build a new global with the combined contents of the referenced globals. - // This global is a struct whose even-indexed elements contain the original - // contents of the referenced globals and whose odd-indexed elements contain - // any padding required to align the next element to the next power of 2. - std::vector GlobalInits; - const DataLayout &DL = M->getDataLayout(); - for (GlobalVariable *G : Globals) { - GlobalInits.push_back(G->getInitializer()); - uint64_t InitSize = DL.getTypeAllocSize(G->getValueType()); - - // Compute the amount of padding required. - uint64_t Padding = NextPowerOf2(InitSize - 1) - InitSize; - - // Cap at 128 was found experimentally to have a good data/instruction - // overhead tradeoff. - if (Padding > 128) - Padding = alignTo(InitSize, 128) - InitSize; - - GlobalInits.push_back( - ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding))); - } - if (!GlobalInits.empty()) - GlobalInits.pop_back(); - Constant *NewInit = ConstantStruct::getAnon(M->getContext(), GlobalInits); - auto *CombinedGlobal = - new GlobalVariable(*M, NewInit->getType(), /*isConstant=*/true, - GlobalValue::PrivateLinkage, NewInit); - - StructType *NewTy = cast(NewInit->getType()); - const StructLayout *CombinedGlobalLayout = DL.getStructLayout(NewTy); - - // Compute the offsets of the original globals within the new global. - DenseMap GlobalLayout; - for (unsigned I = 0; I != Globals.size(); ++I) - // Multiply by 2 to account for padding elements. - GlobalLayout[Globals[I]] = CombinedGlobalLayout->getElementOffset(I * 2); - - lowerBitSetCalls(BitSets, CombinedGlobal, GlobalLayout); - - // Build aliases pointing to offsets into the combined global for each - // global from which we built the combined global, and replace references - // to the original globals with references to the aliases. - for (unsigned I = 0; I != Globals.size(); ++I) { - // Multiply by 2 to account for padding elements. - Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0), - ConstantInt::get(Int32Ty, I * 2)}; - Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr( - NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs); - if (LinkerSubsectionsViaSymbols) { - Globals[I]->replaceAllUsesWith(CombinedGlobalElemPtr); - } else { - assert(Globals[I]->getType()->getAddressSpace() == 0); - GlobalAlias *GAlias = GlobalAlias::create(NewTy->getElementType(I * 2), 0, - Globals[I]->getLinkage(), "", - CombinedGlobalElemPtr, M); - GAlias->setVisibility(Globals[I]->getVisibility()); - GAlias->takeName(Globals[I]); - Globals[I]->replaceAllUsesWith(GAlias); - } - Globals[I]->eraseFromParent(); - } -} - -void LowerBitSets::lowerBitSetCalls( - ArrayRef BitSets, Constant *CombinedGlobalAddr, - const DenseMap &GlobalLayout) { - Constant *CombinedGlobalIntAddr = - ConstantExpr::getPtrToInt(CombinedGlobalAddr, IntPtrTy); - - // For each bitset in this disjoint set... - for (Metadata *BS : BitSets) { - // Build the bitset. - BitSetInfo BSI = buildBitSet(BS, GlobalLayout); - DEBUG({ - if (auto BSS = dyn_cast(BS)) - dbgs() << BSS->getString() << ": "; - else - dbgs() << ": "; - BSI.print(dbgs()); - }); - - ByteArrayInfo *BAI = nullptr; - - // Lower each call to llvm.bitset.test for this bitset. - for (CallInst *CI : BitSetTestCallSites[BS]) { - ++NumBitSetCallsLowered; - Value *Lowered = - lowerBitSetCall(CI, BSI, BAI, CombinedGlobalIntAddr, GlobalLayout); - CI->replaceAllUsesWith(Lowered); - CI->eraseFromParent(); - } - } -} - -void LowerBitSets::verifyBitSetMDNode(MDNode *Op) { - if (Op->getNumOperands() != 3) - report_fatal_error( - "All operands of llvm.bitsets metadata must have 3 elements"); - if (!Op->getOperand(1)) - return; - - auto OpConstMD = dyn_cast(Op->getOperand(1)); - if (!OpConstMD) - report_fatal_error("Bit set element must be a constant"); - auto OpGlobal = dyn_cast(OpConstMD->getValue()); - if (!OpGlobal) - return; - - if (OpGlobal->isThreadLocal()) - report_fatal_error("Bit set element may not be thread-local"); - if (isa(OpGlobal) && OpGlobal->hasSection()) - report_fatal_error( - "Bit set global var element may not have an explicit section"); - - if (isa(OpGlobal) && OpGlobal->isDeclarationForLinker()) - report_fatal_error("Bit set global var element must be a definition"); - - auto OffsetConstMD = dyn_cast(Op->getOperand(2)); - if (!OffsetConstMD) - report_fatal_error("Bit set element offset must be a constant"); - auto OffsetInt = dyn_cast(OffsetConstMD->getValue()); - if (!OffsetInt) - report_fatal_error("Bit set element offset must be an integer constant"); -} - -static const unsigned kX86JumpTableEntrySize = 8; - -unsigned LowerBitSets::getJumpTableEntrySize() { - if (Arch != Triple::x86 && Arch != Triple::x86_64) - report_fatal_error("Unsupported architecture for jump tables"); - - return kX86JumpTableEntrySize; -} - -// Create a constant representing a jump table entry for the target. This -// consists of an instruction sequence containing a relative branch to Dest. The -// constant will be laid out at address Src+(Len*Distance) where Len is the -// target-specific jump table entry size. -Constant *LowerBitSets::createJumpTableEntry(GlobalObject *Src, Function *Dest, - unsigned Distance) { - if (Arch != Triple::x86 && Arch != Triple::x86_64) - report_fatal_error("Unsupported architecture for jump tables"); - - const unsigned kJmpPCRel32Code = 0xe9; - const unsigned kInt3Code = 0xcc; - - ConstantInt *Jmp = ConstantInt::get(Int8Ty, kJmpPCRel32Code); - - // Build a constant representing the displacement between the constant's - // address and Dest. This will resolve to a PC32 relocation referring to Dest. - Constant *DestInt = ConstantExpr::getPtrToInt(Dest, IntPtrTy); - Constant *SrcInt = ConstantExpr::getPtrToInt(Src, IntPtrTy); - Constant *Disp = ConstantExpr::getSub(DestInt, SrcInt); - ConstantInt *DispOffset = - ConstantInt::get(IntPtrTy, Distance * kX86JumpTableEntrySize + 5); - Constant *OffsetedDisp = ConstantExpr::getSub(Disp, DispOffset); - OffsetedDisp = ConstantExpr::getTruncOrBitCast(OffsetedDisp, Int32Ty); - - ConstantInt *Int3 = ConstantInt::get(Int8Ty, kInt3Code); - - Constant *Fields[] = { - Jmp, OffsetedDisp, Int3, Int3, Int3, - }; - return ConstantStruct::getAnon(Fields, /*Packed=*/true); -} - -Type *LowerBitSets::getJumpTableEntryType() { - if (Arch != Triple::x86 && Arch != Triple::x86_64) - report_fatal_error("Unsupported architecture for jump tables"); - - return StructType::get(M->getContext(), - {Int8Ty, Int32Ty, Int8Ty, Int8Ty, Int8Ty}, - /*Packed=*/true); -} - -/// Given a disjoint set of bitsets and functions, build a jump table for the -/// functions, build the bit sets and lower the llvm.bitset.test calls. -void LowerBitSets::buildBitSetsFromFunctions(ArrayRef BitSets, - ArrayRef Functions) { - // Unlike the global bitset builder, the function bitset builder cannot - // re-arrange functions in a particular order and base its calculations on the - // layout of the functions' entry points, as we have no idea how large a - // particular function will end up being (the size could even depend on what - // this pass does!) Instead, we build a jump table, which is a block of code - // consisting of one branch instruction for each of the functions in the bit - // set that branches to the target function, and redirect any taken function - // addresses to the corresponding jump table entry. In the object file's - // symbol table, the symbols for the target functions also refer to the jump - // table entries, so that addresses taken outside the module will pass any - // verification done inside the module. - // - // In more concrete terms, suppose we have three functions f, g, h which are - // members of a single bitset, and a function foo that returns their - // addresses: - // - // f: - // mov 0, %eax - // ret - // - // g: - // mov 1, %eax - // ret - // - // h: - // mov 2, %eax - // ret - // - // foo: - // mov f, %eax - // mov g, %edx - // mov h, %ecx - // ret - // - // To create a jump table for these functions, we instruct the LLVM code - // generator to output a jump table in the .text section. This is done by - // representing the instructions in the jump table as an LLVM constant and - // placing them in a global variable in the .text section. The end result will - // (conceptually) look like this: - // - // f: - // jmp .Ltmp0 ; 5 bytes - // int3 ; 1 byte - // int3 ; 1 byte - // int3 ; 1 byte - // - // g: - // jmp .Ltmp1 ; 5 bytes - // int3 ; 1 byte - // int3 ; 1 byte - // int3 ; 1 byte - // - // h: - // jmp .Ltmp2 ; 5 bytes - // int3 ; 1 byte - // int3 ; 1 byte - // int3 ; 1 byte - // - // .Ltmp0: - // mov 0, %eax - // ret - // - // .Ltmp1: - // mov 1, %eax - // ret - // - // .Ltmp2: - // mov 2, %eax - // ret - // - // foo: - // mov f, %eax - // mov g, %edx - // mov h, %ecx - // ret - // - // Because the addresses of f, g, h are evenly spaced at a power of 2, in the - // normal case the check can be carried out using the same kind of simple - // arithmetic that we normally use for globals. - - assert(!Functions.empty()); - - // Build a simple layout based on the regular layout of jump tables. - DenseMap GlobalLayout; - unsigned EntrySize = getJumpTableEntrySize(); - for (unsigned I = 0; I != Functions.size(); ++I) - GlobalLayout[Functions[I]] = I * EntrySize; - - // Create a constant to hold the jump table. - ArrayType *JumpTableType = - ArrayType::get(getJumpTableEntryType(), Functions.size()); - auto JumpTable = new GlobalVariable(*M, JumpTableType, - /*isConstant=*/true, - GlobalValue::PrivateLinkage, nullptr); - JumpTable->setSection(ObjectFormat == Triple::MachO - ? "__TEXT,__text,regular,pure_instructions" - : ".text"); - lowerBitSetCalls(BitSets, JumpTable, GlobalLayout); - - // Build aliases pointing to offsets into the jump table, and replace - // references to the original functions with references to the aliases. - for (unsigned I = 0; I != Functions.size(); ++I) { - Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast( - ConstantExpr::getGetElementPtr( - JumpTableType, JumpTable, - ArrayRef{ConstantInt::get(IntPtrTy, 0), - ConstantInt::get(IntPtrTy, I)}), - Functions[I]->getType()); - if (LinkerSubsectionsViaSymbols || Functions[I]->isDeclarationForLinker()) { - Functions[I]->replaceAllUsesWith(CombinedGlobalElemPtr); - } else { - assert(Functions[I]->getType()->getAddressSpace() == 0); - GlobalAlias *GAlias = GlobalAlias::create(Functions[I]->getValueType(), 0, - Functions[I]->getLinkage(), "", - CombinedGlobalElemPtr, M); - GAlias->setVisibility(Functions[I]->getVisibility()); - GAlias->takeName(Functions[I]); - Functions[I]->replaceAllUsesWith(GAlias); - } - if (!Functions[I]->isDeclarationForLinker()) - Functions[I]->setLinkage(GlobalValue::PrivateLinkage); - } - - // Build and set the jump table's initializer. - std::vector JumpTableEntries; - for (unsigned I = 0; I != Functions.size(); ++I) - JumpTableEntries.push_back( - createJumpTableEntry(JumpTable, Functions[I], I)); - JumpTable->setInitializer( - ConstantArray::get(JumpTableType, JumpTableEntries)); -} - -void LowerBitSets::buildBitSetsFromDisjointSet( - ArrayRef BitSets, ArrayRef Globals) { - llvm::DenseMap BitSetIndices; - llvm::DenseMap GlobalIndices; - for (unsigned I = 0; I != BitSets.size(); ++I) - BitSetIndices[BitSets[I]] = I; - for (unsigned I = 0; I != Globals.size(); ++I) - GlobalIndices[Globals[I]] = I; - - // For each bitset, build a set of indices that refer to globals referenced by - // the bitset. - std::vector> BitSetMembers(BitSets.size()); - if (BitSetNM) { - for (MDNode *Op : BitSetNM->operands()) { - // Op = { bitset name, global, offset } - if (!Op->getOperand(1)) - continue; - auto I = BitSetIndices.find(Op->getOperand(0)); - if (I == BitSetIndices.end()) - continue; - - auto OpGlobal = dyn_cast( - cast(Op->getOperand(1))->getValue()); - if (!OpGlobal) - continue; - BitSetMembers[I->second].insert(GlobalIndices[OpGlobal]); - } - } - - // Order the sets of indices by size. The GlobalLayoutBuilder works best - // when given small index sets first. - std::stable_sort( - BitSetMembers.begin(), BitSetMembers.end(), - [](const std::set &O1, const std::set &O2) { - return O1.size() < O2.size(); - }); - - // Create a GlobalLayoutBuilder and provide it with index sets as layout - // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as - // close together as possible. - GlobalLayoutBuilder GLB(Globals.size()); - for (auto &&MemSet : BitSetMembers) - GLB.addFragment(MemSet); - - // Build the bitsets from this disjoint set. - if (Globals.empty() || isa(Globals[0])) { - // Build a vector of global variables with the computed layout. - std::vector OrderedGVs(Globals.size()); - auto OGI = OrderedGVs.begin(); - for (auto &&F : GLB.Fragments) { - for (auto &&Offset : F) { - auto GV = dyn_cast(Globals[Offset]); - if (!GV) - report_fatal_error( - "Bit set may not contain both global variables and functions"); - *OGI++ = GV; - } - } - - buildBitSetsFromGlobalVariables(BitSets, OrderedGVs); - } else { - // Build a vector of functions with the computed layout. - std::vector OrderedFns(Globals.size()); - auto OFI = OrderedFns.begin(); - for (auto &&F : GLB.Fragments) { - for (auto &&Offset : F) { - auto Fn = dyn_cast(Globals[Offset]); - if (!Fn) - report_fatal_error( - "Bit set may not contain both global variables and functions"); - *OFI++ = Fn; - } - } - - buildBitSetsFromFunctions(BitSets, OrderedFns); - } -} - -/// Lower all bit sets in this module. -bool LowerBitSets::buildBitSets() { - Function *BitSetTestFunc = - M->getFunction(Intrinsic::getName(Intrinsic::bitset_test)); - if (!BitSetTestFunc || BitSetTestFunc->use_empty()) - return false; - - // Equivalence class set containing bitsets and the globals they reference. - // This is used to partition the set of bitsets in the module into disjoint - // sets. - typedef EquivalenceClasses> - GlobalClassesTy; - GlobalClassesTy GlobalClasses; - - // Verify the bitset metadata and build a mapping from bitset identifiers to - // their last observed index in BitSetNM. This will used later to - // deterministically order the list of bitset identifiers. - llvm::DenseMap BitSetIdIndices; - if (BitSetNM) { - for (unsigned I = 0, E = BitSetNM->getNumOperands(); I != E; ++I) { - MDNode *Op = BitSetNM->getOperand(I); - verifyBitSetMDNode(Op); - BitSetIdIndices[Op->getOperand(0)] = I; - } - } - - for (const Use &U : BitSetTestFunc->uses()) { - auto CI = cast(U.getUser()); - - auto BitSetMDVal = dyn_cast(CI->getArgOperand(1)); - if (!BitSetMDVal) - report_fatal_error( - "Second argument of llvm.bitset.test must be metadata"); - auto BitSet = BitSetMDVal->getMetadata(); - - // Add the call site to the list of call sites for this bit set. We also use - // BitSetTestCallSites to keep track of whether we have seen this bit set - // before. If we have, we don't need to re-add the referenced globals to the - // equivalence class. - std::pair>::iterator, - bool> Ins = - BitSetTestCallSites.insert( - std::make_pair(BitSet, std::vector())); - Ins.first->second.push_back(CI); - if (!Ins.second) - continue; - - // Add the bitset to the equivalence class. - GlobalClassesTy::iterator GCI = GlobalClasses.insert(BitSet); - GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI); - - if (!BitSetNM) - continue; - - // Add the referenced globals to the bitset's equivalence class. - for (MDNode *Op : BitSetNM->operands()) { - if (Op->getOperand(0) != BitSet || !Op->getOperand(1)) - continue; - - auto OpGlobal = dyn_cast( - cast(Op->getOperand(1))->getValue()); - if (!OpGlobal) - continue; - - CurSet = GlobalClasses.unionSets( - CurSet, GlobalClasses.findLeader(GlobalClasses.insert(OpGlobal))); - } - } - - if (GlobalClasses.empty()) - return false; - - // Build a list of disjoint sets ordered by their maximum BitSetNM index - // for determinism. - std::vector> Sets; - for (GlobalClassesTy::iterator I = GlobalClasses.begin(), - E = GlobalClasses.end(); - I != E; ++I) { - if (!I->isLeader()) continue; - ++NumBitSetDisjointSets; - - unsigned MaxIndex = 0; - for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I); - MI != GlobalClasses.member_end(); ++MI) { - if ((*MI).is()) - MaxIndex = std::max(MaxIndex, BitSetIdIndices[MI->get()]); - } - Sets.emplace_back(I, MaxIndex); - } - std::sort(Sets.begin(), Sets.end(), - [](const std::pair &S1, - const std::pair &S2) { - return S1.second < S2.second; - }); - - // For each disjoint set we found... - for (const auto &S : Sets) { - // Build the list of bitsets in this disjoint set. - std::vector BitSets; - std::vector Globals; - for (GlobalClassesTy::member_iterator MI = - GlobalClasses.member_begin(S.first); - MI != GlobalClasses.member_end(); ++MI) { - if ((*MI).is()) - BitSets.push_back(MI->get()); - else - Globals.push_back(MI->get()); - } - - // Order bitsets by BitSetNM index for determinism. This ordering is stable - // as there is a one-to-one mapping between metadata and indices. - std::sort(BitSets.begin(), BitSets.end(), [&](Metadata *M1, Metadata *M2) { - return BitSetIdIndices[M1] < BitSetIdIndices[M2]; - }); - - // Lower the bitsets in this disjoint set. - buildBitSetsFromDisjointSet(BitSets, Globals); - } - - allocateByteArrays(); - - return true; -} - -bool LowerBitSets::eraseBitSetMetadata() { - if (!BitSetNM) - return false; - - M->eraseNamedMetadata(BitSetNM); - return true; -} - -bool LowerBitSets::runOnModule(Module &M) { - if (skipModule(M)) - return false; - - bool Changed = buildBitSets(); - Changed |= eraseBitSetMetadata(); - return Changed; -} Index: llvm/trunk/lib/Transforms/IPO/LowerTypeTests.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/LowerTypeTests.cpp +++ llvm/trunk/lib/Transforms/IPO/LowerTypeTests.cpp @@ -0,0 +1,1016 @@ +//===-- LowerTypeTests.cpp - type metadata lowering pass ------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass lowers type metadata and calls to the llvm.type.test intrinsic. +// See http://llvm.org/docs/TypeMetadata.html for more information. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/IPO/LowerTypeTests.h" +#include "llvm/Transforms/IPO.h" +#include "llvm/ADT/EquivalenceClasses.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/Triple.h" +#include "llvm/IR/Constant.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/GlobalObject.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Intrinsics.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Operator.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/BasicBlockUtils.h" + +using namespace llvm; +using namespace lowertypetests; + +#define DEBUG_TYPE "lowertypetests" + +STATISTIC(ByteArraySizeBits, "Byte array size in bits"); +STATISTIC(ByteArraySizeBytes, "Byte array size in bytes"); +STATISTIC(NumByteArraysCreated, "Number of byte arrays created"); +STATISTIC(NumTypeTestCallsLowered, "Number of type test calls lowered"); +STATISTIC(NumTypeIdDisjointSets, "Number of disjoint sets of type identifiers"); + +static cl::opt AvoidReuse( + "lowertypetests-avoid-reuse", + cl::desc("Try to avoid reuse of byte array addresses using aliases"), + cl::Hidden, cl::init(true)); + +bool BitSetInfo::containsGlobalOffset(uint64_t Offset) const { + if (Offset < ByteOffset) + return false; + + if ((Offset - ByteOffset) % (uint64_t(1) << AlignLog2) != 0) + return false; + + uint64_t BitOffset = (Offset - ByteOffset) >> AlignLog2; + if (BitOffset >= BitSize) + return false; + + return Bits.count(BitOffset); +} + +bool BitSetInfo::containsValue( + const DataLayout &DL, + const DenseMap &GlobalLayout, Value *V, + uint64_t COffset) const { + if (auto GV = dyn_cast(V)) { + auto I = GlobalLayout.find(GV); + if (I == GlobalLayout.end()) + return false; + return containsGlobalOffset(I->second + COffset); + } + + if (auto GEP = dyn_cast(V)) { + APInt APOffset(DL.getPointerSizeInBits(0), 0); + bool Result = GEP->accumulateConstantOffset(DL, APOffset); + if (!Result) + return false; + COffset += APOffset.getZExtValue(); + return containsValue(DL, GlobalLayout, GEP->getPointerOperand(), + COffset); + } + + if (auto Op = dyn_cast(V)) { + if (Op->getOpcode() == Instruction::BitCast) + return containsValue(DL, GlobalLayout, Op->getOperand(0), COffset); + + if (Op->getOpcode() == Instruction::Select) + return containsValue(DL, GlobalLayout, Op->getOperand(1), COffset) && + containsValue(DL, GlobalLayout, Op->getOperand(2), COffset); + } + + return false; +} + +void BitSetInfo::print(raw_ostream &OS) const { + OS << "offset " << ByteOffset << " size " << BitSize << " align " + << (1 << AlignLog2); + + if (isAllOnes()) { + OS << " all-ones\n"; + return; + } + + OS << " { "; + for (uint64_t B : Bits) + OS << B << ' '; + OS << "}\n"; +} + +BitSetInfo BitSetBuilder::build() { + if (Min > Max) + Min = 0; + + // Normalize each offset against the minimum observed offset, and compute + // the bitwise OR of each of the offsets. The number of trailing zeros + // in the mask gives us the log2 of the alignment of all offsets, which + // allows us to compress the bitset by only storing one bit per aligned + // address. + uint64_t Mask = 0; + for (uint64_t &Offset : Offsets) { + Offset -= Min; + Mask |= Offset; + } + + BitSetInfo BSI; + BSI.ByteOffset = Min; + + BSI.AlignLog2 = 0; + if (Mask != 0) + BSI.AlignLog2 = countTrailingZeros(Mask, ZB_Undefined); + + // Build the compressed bitset while normalizing the offsets against the + // computed alignment. + BSI.BitSize = ((Max - Min) >> BSI.AlignLog2) + 1; + for (uint64_t Offset : Offsets) { + Offset >>= BSI.AlignLog2; + BSI.Bits.insert(Offset); + } + + return BSI; +} + +void GlobalLayoutBuilder::addFragment(const std::set &F) { + // Create a new fragment to hold the layout for F. + Fragments.emplace_back(); + std::vector &Fragment = Fragments.back(); + uint64_t FragmentIndex = Fragments.size() - 1; + + for (auto ObjIndex : F) { + uint64_t OldFragmentIndex = FragmentMap[ObjIndex]; + if (OldFragmentIndex == 0) { + // We haven't seen this object index before, so just add it to the current + // fragment. + Fragment.push_back(ObjIndex); + } else { + // This index belongs to an existing fragment. Copy the elements of the + // old fragment into this one and clear the old fragment. We don't update + // the fragment map just yet, this ensures that any further references to + // indices from the old fragment in this fragment do not insert any more + // indices. + std::vector &OldFragment = Fragments[OldFragmentIndex]; + Fragment.insert(Fragment.end(), OldFragment.begin(), OldFragment.end()); + OldFragment.clear(); + } + } + + // Update the fragment map to point our object indices to this fragment. + for (uint64_t ObjIndex : Fragment) + FragmentMap[ObjIndex] = FragmentIndex; +} + +void ByteArrayBuilder::allocate(const std::set &Bits, + uint64_t BitSize, uint64_t &AllocByteOffset, + uint8_t &AllocMask) { + // Find the smallest current allocation. + unsigned Bit = 0; + for (unsigned I = 1; I != BitsPerByte; ++I) + if (BitAllocs[I] < BitAllocs[Bit]) + Bit = I; + + AllocByteOffset = BitAllocs[Bit]; + + // Add our size to it. + unsigned ReqSize = AllocByteOffset + BitSize; + BitAllocs[Bit] = ReqSize; + if (Bytes.size() < ReqSize) + Bytes.resize(ReqSize); + + // Set our bits. + AllocMask = 1 << Bit; + for (uint64_t B : Bits) + Bytes[AllocByteOffset + B] |= AllocMask; +} + +namespace { + +struct ByteArrayInfo { + std::set Bits; + uint64_t BitSize; + GlobalVariable *ByteArray; + Constant *Mask; +}; + +struct LowerTypeTests : public ModulePass { + static char ID; + LowerTypeTests() : ModulePass(ID) { + initializeLowerTypeTestsPass(*PassRegistry::getPassRegistry()); + } + + Module *M; + + bool LinkerSubsectionsViaSymbols; + Triple::ArchType Arch; + Triple::ObjectFormatType ObjectFormat; + IntegerType *Int1Ty; + IntegerType *Int8Ty; + IntegerType *Int32Ty; + Type *Int32PtrTy; + IntegerType *Int64Ty; + IntegerType *IntPtrTy; + + // Mapping from type identifiers to the call sites that test them. + DenseMap> TypeTestCallSites; + + std::vector ByteArrayInfos; + + BitSetInfo + buildBitSet(Metadata *TypeId, + const DenseMap &GlobalLayout); + ByteArrayInfo *createByteArray(BitSetInfo &BSI); + void allocateByteArrays(); + Value *createBitSetTest(IRBuilder<> &B, BitSetInfo &BSI, ByteArrayInfo *&BAI, + Value *BitOffset); + void + lowerTypeTestCalls(ArrayRef TypeIds, Constant *CombinedGlobalAddr, + const DenseMap &GlobalLayout); + Value * + lowerBitSetCall(CallInst *CI, BitSetInfo &BSI, ByteArrayInfo *&BAI, + Constant *CombinedGlobal, + const DenseMap &GlobalLayout); + void buildBitSetsFromGlobalVariables(ArrayRef TypeIds, + ArrayRef Globals); + unsigned getJumpTableEntrySize(); + Type *getJumpTableEntryType(); + Constant *createJumpTableEntry(GlobalObject *Src, Function *Dest, + unsigned Distance); + void verifyTypeMDNode(GlobalObject *GO, MDNode *Type); + void buildBitSetsFromFunctions(ArrayRef TypeIds, + ArrayRef Functions); + void buildBitSetsFromDisjointSet(ArrayRef TypeIds, + ArrayRef Globals); + bool lower(); + + bool doInitialization(Module &M) override; + bool runOnModule(Module &M) override; +}; + +} // anonymous namespace + +INITIALIZE_PASS(LowerTypeTests, "lowertypetests", "Lower type metadata", false, + false) +char LowerTypeTests::ID = 0; + +ModulePass *llvm::createLowerTypeTestsPass() { return new LowerTypeTests; } + +bool LowerTypeTests::doInitialization(Module &Mod) { + M = &Mod; + const DataLayout &DL = Mod.getDataLayout(); + + Triple TargetTriple(M->getTargetTriple()); + LinkerSubsectionsViaSymbols = TargetTriple.isMacOSX(); + Arch = TargetTriple.getArch(); + ObjectFormat = TargetTriple.getObjectFormat(); + + Int1Ty = Type::getInt1Ty(M->getContext()); + Int8Ty = Type::getInt8Ty(M->getContext()); + Int32Ty = Type::getInt32Ty(M->getContext()); + Int32PtrTy = PointerType::getUnqual(Int32Ty); + Int64Ty = Type::getInt64Ty(M->getContext()); + IntPtrTy = DL.getIntPtrType(M->getContext(), 0); + + TypeTestCallSites.clear(); + + return false; +} + +/// Build a bit set for TypeId using the object layouts in +/// GlobalLayout. +BitSetInfo LowerTypeTests::buildBitSet( + Metadata *TypeId, + const DenseMap &GlobalLayout) { + BitSetBuilder BSB; + + // Compute the byte offset of each address associated with this type + // identifier. + SmallVector Types; + for (auto &GlobalAndOffset : GlobalLayout) { + Types.clear(); + GlobalAndOffset.first->getMetadata(LLVMContext::MD_type, Types); + for (MDNode *Type : Types) { + if (Type->getOperand(1) != TypeId) + continue; + uint64_t Offset = + cast(cast(Type->getOperand(0)) + ->getValue())->getZExtValue(); + BSB.addOffset(GlobalAndOffset.second + Offset); + } + } + + return BSB.build(); +} + +/// Build a test that bit BitOffset mod sizeof(Bits)*8 is set in +/// Bits. This pattern matches to the bt instruction on x86. +static Value *createMaskedBitTest(IRBuilder<> &B, Value *Bits, + Value *BitOffset) { + auto BitsType = cast(Bits->getType()); + unsigned BitWidth = BitsType->getBitWidth(); + + BitOffset = B.CreateZExtOrTrunc(BitOffset, BitsType); + Value *BitIndex = + B.CreateAnd(BitOffset, ConstantInt::get(BitsType, BitWidth - 1)); + Value *BitMask = B.CreateShl(ConstantInt::get(BitsType, 1), BitIndex); + Value *MaskedBits = B.CreateAnd(Bits, BitMask); + return B.CreateICmpNE(MaskedBits, ConstantInt::get(BitsType, 0)); +} + +ByteArrayInfo *LowerTypeTests::createByteArray(BitSetInfo &BSI) { + // Create globals to stand in for byte arrays and masks. These never actually + // get initialized, we RAUW and erase them later in allocateByteArrays() once + // we know the offset and mask to use. + auto ByteArrayGlobal = new GlobalVariable( + *M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr); + auto MaskGlobal = new GlobalVariable( + *M, Int8Ty, /*isConstant=*/true, GlobalValue::PrivateLinkage, nullptr); + + ByteArrayInfos.emplace_back(); + ByteArrayInfo *BAI = &ByteArrayInfos.back(); + + BAI->Bits = BSI.Bits; + BAI->BitSize = BSI.BitSize; + BAI->ByteArray = ByteArrayGlobal; + BAI->Mask = ConstantExpr::getPtrToInt(MaskGlobal, Int8Ty); + return BAI; +} + +void LowerTypeTests::allocateByteArrays() { + std::stable_sort(ByteArrayInfos.begin(), ByteArrayInfos.end(), + [](const ByteArrayInfo &BAI1, const ByteArrayInfo &BAI2) { + return BAI1.BitSize > BAI2.BitSize; + }); + + std::vector ByteArrayOffsets(ByteArrayInfos.size()); + + ByteArrayBuilder BAB; + for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) { + ByteArrayInfo *BAI = &ByteArrayInfos[I]; + + uint8_t Mask; + BAB.allocate(BAI->Bits, BAI->BitSize, ByteArrayOffsets[I], Mask); + + BAI->Mask->replaceAllUsesWith(ConstantInt::get(Int8Ty, Mask)); + cast(BAI->Mask->getOperand(0))->eraseFromParent(); + } + + Constant *ByteArrayConst = ConstantDataArray::get(M->getContext(), BAB.Bytes); + auto ByteArray = + new GlobalVariable(*M, ByteArrayConst->getType(), /*isConstant=*/true, + GlobalValue::PrivateLinkage, ByteArrayConst); + + for (unsigned I = 0; I != ByteArrayInfos.size(); ++I) { + ByteArrayInfo *BAI = &ByteArrayInfos[I]; + + Constant *Idxs[] = {ConstantInt::get(IntPtrTy, 0), + ConstantInt::get(IntPtrTy, ByteArrayOffsets[I])}; + Constant *GEP = ConstantExpr::getInBoundsGetElementPtr( + ByteArrayConst->getType(), ByteArray, Idxs); + + // Create an alias instead of RAUW'ing the gep directly. On x86 this ensures + // that the pc-relative displacement is folded into the lea instead of the + // test instruction getting another displacement. + if (LinkerSubsectionsViaSymbols) { + BAI->ByteArray->replaceAllUsesWith(GEP); + } else { + GlobalAlias *Alias = GlobalAlias::create( + Int8Ty, 0, GlobalValue::PrivateLinkage, "bits", GEP, M); + BAI->ByteArray->replaceAllUsesWith(Alias); + } + BAI->ByteArray->eraseFromParent(); + } + + ByteArraySizeBits = BAB.BitAllocs[0] + BAB.BitAllocs[1] + BAB.BitAllocs[2] + + BAB.BitAllocs[3] + BAB.BitAllocs[4] + BAB.BitAllocs[5] + + BAB.BitAllocs[6] + BAB.BitAllocs[7]; + ByteArraySizeBytes = BAB.Bytes.size(); +} + +/// Build a test that bit BitOffset is set in BSI, where +/// BitSetGlobal is a global containing the bits in BSI. +Value *LowerTypeTests::createBitSetTest(IRBuilder<> &B, BitSetInfo &BSI, + ByteArrayInfo *&BAI, Value *BitOffset) { + if (BSI.BitSize <= 64) { + // If the bit set is sufficiently small, we can avoid a load by bit testing + // a constant. + IntegerType *BitsTy; + if (BSI.BitSize <= 32) + BitsTy = Int32Ty; + else + BitsTy = Int64Ty; + + uint64_t Bits = 0; + for (auto Bit : BSI.Bits) + Bits |= uint64_t(1) << Bit; + Constant *BitsConst = ConstantInt::get(BitsTy, Bits); + return createMaskedBitTest(B, BitsConst, BitOffset); + } else { + if (!BAI) { + ++NumByteArraysCreated; + BAI = createByteArray(BSI); + } + + Constant *ByteArray = BAI->ByteArray; + Type *Ty = BAI->ByteArray->getValueType(); + if (!LinkerSubsectionsViaSymbols && AvoidReuse) { + // Each use of the byte array uses a different alias. This makes the + // backend less likely to reuse previously computed byte array addresses, + // improving the security of the CFI mechanism based on this pass. + ByteArray = GlobalAlias::create(BAI->ByteArray->getValueType(), 0, + GlobalValue::PrivateLinkage, "bits_use", + ByteArray, M); + } + + Value *ByteAddr = B.CreateGEP(Ty, ByteArray, BitOffset); + Value *Byte = B.CreateLoad(ByteAddr); + + Value *ByteAndMask = B.CreateAnd(Byte, BAI->Mask); + return B.CreateICmpNE(ByteAndMask, ConstantInt::get(Int8Ty, 0)); + } +} + +/// Lower a llvm.type.test call to its implementation. Returns the value to +/// replace the call with. +Value *LowerTypeTests::lowerBitSetCall( + CallInst *CI, BitSetInfo &BSI, ByteArrayInfo *&BAI, + Constant *CombinedGlobalIntAddr, + const DenseMap &GlobalLayout) { + Value *Ptr = CI->getArgOperand(0); + const DataLayout &DL = M->getDataLayout(); + + if (BSI.containsValue(DL, GlobalLayout, Ptr)) + return ConstantInt::getTrue(M->getContext()); + + Constant *OffsetedGlobalAsInt = ConstantExpr::getAdd( + CombinedGlobalIntAddr, ConstantInt::get(IntPtrTy, BSI.ByteOffset)); + + BasicBlock *InitialBB = CI->getParent(); + + IRBuilder<> B(CI); + + Value *PtrAsInt = B.CreatePtrToInt(Ptr, IntPtrTy); + + if (BSI.isSingleOffset()) + return B.CreateICmpEQ(PtrAsInt, OffsetedGlobalAsInt); + + Value *PtrOffset = B.CreateSub(PtrAsInt, OffsetedGlobalAsInt); + + Value *BitOffset; + if (BSI.AlignLog2 == 0) { + BitOffset = PtrOffset; + } else { + // We need to check that the offset both falls within our range and is + // suitably aligned. We can check both properties at the same time by + // performing a right rotate by log2(alignment) followed by an integer + // comparison against the bitset size. The rotate will move the lower + // order bits that need to be zero into the higher order bits of the + // result, causing the comparison to fail if they are nonzero. The rotate + // also conveniently gives us a bit offset to use during the load from + // the bitset. + Value *OffsetSHR = + B.CreateLShr(PtrOffset, ConstantInt::get(IntPtrTy, BSI.AlignLog2)); + Value *OffsetSHL = B.CreateShl( + PtrOffset, + ConstantInt::get(IntPtrTy, DL.getPointerSizeInBits(0) - BSI.AlignLog2)); + BitOffset = B.CreateOr(OffsetSHR, OffsetSHL); + } + + Constant *BitSizeConst = ConstantInt::get(IntPtrTy, BSI.BitSize); + Value *OffsetInRange = B.CreateICmpULT(BitOffset, BitSizeConst); + + // If the bit set is all ones, testing against it is unnecessary. + if (BSI.isAllOnes()) + return OffsetInRange; + + TerminatorInst *Term = SplitBlockAndInsertIfThen(OffsetInRange, CI, false); + IRBuilder<> ThenB(Term); + + // Now that we know that the offset is in range and aligned, load the + // appropriate bit from the bitset. + Value *Bit = createBitSetTest(ThenB, BSI, BAI, BitOffset); + + // The value we want is 0 if we came directly from the initial block + // (having failed the range or alignment checks), or the loaded bit if + // we came from the block in which we loaded it. + B.SetInsertPoint(CI); + PHINode *P = B.CreatePHI(Int1Ty, 2); + P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB); + P->addIncoming(Bit, ThenB.GetInsertBlock()); + return P; +} + +/// Given a disjoint set of type identifiers and globals, lay out the globals, +/// build the bit sets and lower the llvm.type.test calls. +void LowerTypeTests::buildBitSetsFromGlobalVariables( + ArrayRef TypeIds, ArrayRef Globals) { + // Build a new global with the combined contents of the referenced globals. + // This global is a struct whose even-indexed elements contain the original + // contents of the referenced globals and whose odd-indexed elements contain + // any padding required to align the next element to the next power of 2. + std::vector GlobalInits; + const DataLayout &DL = M->getDataLayout(); + for (GlobalVariable *G : Globals) { + GlobalInits.push_back(G->getInitializer()); + uint64_t InitSize = DL.getTypeAllocSize(G->getValueType()); + + // Compute the amount of padding required. + uint64_t Padding = NextPowerOf2(InitSize - 1) - InitSize; + + // Cap at 128 was found experimentally to have a good data/instruction + // overhead tradeoff. + if (Padding > 128) + Padding = alignTo(InitSize, 128) - InitSize; + + GlobalInits.push_back( + ConstantAggregateZero::get(ArrayType::get(Int8Ty, Padding))); + } + if (!GlobalInits.empty()) + GlobalInits.pop_back(); + Constant *NewInit = ConstantStruct::getAnon(M->getContext(), GlobalInits); + auto *CombinedGlobal = + new GlobalVariable(*M, NewInit->getType(), /*isConstant=*/true, + GlobalValue::PrivateLinkage, NewInit); + + StructType *NewTy = cast(NewInit->getType()); + const StructLayout *CombinedGlobalLayout = DL.getStructLayout(NewTy); + + // Compute the offsets of the original globals within the new global. + DenseMap GlobalLayout; + for (unsigned I = 0; I != Globals.size(); ++I) + // Multiply by 2 to account for padding elements. + GlobalLayout[Globals[I]] = CombinedGlobalLayout->getElementOffset(I * 2); + + lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout); + + // Build aliases pointing to offsets into the combined global for each + // global from which we built the combined global, and replace references + // to the original globals with references to the aliases. + for (unsigned I = 0; I != Globals.size(); ++I) { + // Multiply by 2 to account for padding elements. + Constant *CombinedGlobalIdxs[] = {ConstantInt::get(Int32Ty, 0), + ConstantInt::get(Int32Ty, I * 2)}; + Constant *CombinedGlobalElemPtr = ConstantExpr::getGetElementPtr( + NewInit->getType(), CombinedGlobal, CombinedGlobalIdxs); + if (LinkerSubsectionsViaSymbols) { + Globals[I]->replaceAllUsesWith(CombinedGlobalElemPtr); + } else { + assert(Globals[I]->getType()->getAddressSpace() == 0); + GlobalAlias *GAlias = GlobalAlias::create(NewTy->getElementType(I * 2), 0, + Globals[I]->getLinkage(), "", + CombinedGlobalElemPtr, M); + GAlias->setVisibility(Globals[I]->getVisibility()); + GAlias->takeName(Globals[I]); + Globals[I]->replaceAllUsesWith(GAlias); + } + Globals[I]->eraseFromParent(); + } +} + +void LowerTypeTests::lowerTypeTestCalls( + ArrayRef TypeIds, Constant *CombinedGlobalAddr, + const DenseMap &GlobalLayout) { + Constant *CombinedGlobalIntAddr = + ConstantExpr::getPtrToInt(CombinedGlobalAddr, IntPtrTy); + + // For each type identifier in this disjoint set... + for (Metadata *TypeId : TypeIds) { + // Build the bitset. + BitSetInfo BSI = buildBitSet(TypeId, GlobalLayout); + DEBUG({ + if (auto MDS = dyn_cast(TypeId)) + dbgs() << MDS->getString() << ": "; + else + dbgs() << ": "; + BSI.print(dbgs()); + }); + + ByteArrayInfo *BAI = nullptr; + + // Lower each call to llvm.type.test for this type identifier. + for (CallInst *CI : TypeTestCallSites[TypeId]) { + ++NumTypeTestCallsLowered; + Value *Lowered = + lowerBitSetCall(CI, BSI, BAI, CombinedGlobalIntAddr, GlobalLayout); + CI->replaceAllUsesWith(Lowered); + CI->eraseFromParent(); + } + } +} + +void LowerTypeTests::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) { + if (Type->getNumOperands() != 2) + report_fatal_error( + "All operands of type metadata must have 2 elements"); + + if (GO->isThreadLocal()) + report_fatal_error("Bit set element may not be thread-local"); + if (isa(GO) && GO->hasSection()) + report_fatal_error( + "A member of a type identifier may not have an explicit section"); + + if (isa(GO) && GO->isDeclarationForLinker()) + report_fatal_error( + "A global var member of a type identifier must be a definition"); + + auto OffsetConstMD = dyn_cast(Type->getOperand(0)); + if (!OffsetConstMD) + report_fatal_error("Type offset must be a constant"); + auto OffsetInt = dyn_cast(OffsetConstMD->getValue()); + if (!OffsetInt) + report_fatal_error("Type offset must be an integer constant"); +} + +static const unsigned kX86JumpTableEntrySize = 8; + +unsigned LowerTypeTests::getJumpTableEntrySize() { + if (Arch != Triple::x86 && Arch != Triple::x86_64) + report_fatal_error("Unsupported architecture for jump tables"); + + return kX86JumpTableEntrySize; +} + +// Create a constant representing a jump table entry for the target. This +// consists of an instruction sequence containing a relative branch to Dest. The +// constant will be laid out at address Src+(Len*Distance) where Len is the +// target-specific jump table entry size. +Constant *LowerTypeTests::createJumpTableEntry(GlobalObject *Src, + Function *Dest, + unsigned Distance) { + if (Arch != Triple::x86 && Arch != Triple::x86_64) + report_fatal_error("Unsupported architecture for jump tables"); + + const unsigned kJmpPCRel32Code = 0xe9; + const unsigned kInt3Code = 0xcc; + + ConstantInt *Jmp = ConstantInt::get(Int8Ty, kJmpPCRel32Code); + + // Build a constant representing the displacement between the constant's + // address and Dest. This will resolve to a PC32 relocation referring to Dest. + Constant *DestInt = ConstantExpr::getPtrToInt(Dest, IntPtrTy); + Constant *SrcInt = ConstantExpr::getPtrToInt(Src, IntPtrTy); + Constant *Disp = ConstantExpr::getSub(DestInt, SrcInt); + ConstantInt *DispOffset = + ConstantInt::get(IntPtrTy, Distance * kX86JumpTableEntrySize + 5); + Constant *OffsetedDisp = ConstantExpr::getSub(Disp, DispOffset); + OffsetedDisp = ConstantExpr::getTruncOrBitCast(OffsetedDisp, Int32Ty); + + ConstantInt *Int3 = ConstantInt::get(Int8Ty, kInt3Code); + + Constant *Fields[] = { + Jmp, OffsetedDisp, Int3, Int3, Int3, + }; + return ConstantStruct::getAnon(Fields, /*Packed=*/true); +} + +Type *LowerTypeTests::getJumpTableEntryType() { + if (Arch != Triple::x86 && Arch != Triple::x86_64) + report_fatal_error("Unsupported architecture for jump tables"); + + return StructType::get(M->getContext(), + {Int8Ty, Int32Ty, Int8Ty, Int8Ty, Int8Ty}, + /*Packed=*/true); +} + +/// Given a disjoint set of type identifiers and functions, build a jump table +/// for the functions, build the bit sets and lower the llvm.type.test calls. +void LowerTypeTests::buildBitSetsFromFunctions(ArrayRef TypeIds, + ArrayRef Functions) { + // Unlike the global bitset builder, the function bitset builder cannot + // re-arrange functions in a particular order and base its calculations on the + // layout of the functions' entry points, as we have no idea how large a + // particular function will end up being (the size could even depend on what + // this pass does!) Instead, we build a jump table, which is a block of code + // consisting of one branch instruction for each of the functions in the bit + // set that branches to the target function, and redirect any taken function + // addresses to the corresponding jump table entry. In the object file's + // symbol table, the symbols for the target functions also refer to the jump + // table entries, so that addresses taken outside the module will pass any + // verification done inside the module. + // + // In more concrete terms, suppose we have three functions f, g, h which are + // of the same type, and a function foo that returns their addresses: + // + // f: + // mov 0, %eax + // ret + // + // g: + // mov 1, %eax + // ret + // + // h: + // mov 2, %eax + // ret + // + // foo: + // mov f, %eax + // mov g, %edx + // mov h, %ecx + // ret + // + // To create a jump table for these functions, we instruct the LLVM code + // generator to output a jump table in the .text section. This is done by + // representing the instructions in the jump table as an LLVM constant and + // placing them in a global variable in the .text section. The end result will + // (conceptually) look like this: + // + // f: + // jmp .Ltmp0 ; 5 bytes + // int3 ; 1 byte + // int3 ; 1 byte + // int3 ; 1 byte + // + // g: + // jmp .Ltmp1 ; 5 bytes + // int3 ; 1 byte + // int3 ; 1 byte + // int3 ; 1 byte + // + // h: + // jmp .Ltmp2 ; 5 bytes + // int3 ; 1 byte + // int3 ; 1 byte + // int3 ; 1 byte + // + // .Ltmp0: + // mov 0, %eax + // ret + // + // .Ltmp1: + // mov 1, %eax + // ret + // + // .Ltmp2: + // mov 2, %eax + // ret + // + // foo: + // mov f, %eax + // mov g, %edx + // mov h, %ecx + // ret + // + // Because the addresses of f, g, h are evenly spaced at a power of 2, in the + // normal case the check can be carried out using the same kind of simple + // arithmetic that we normally use for globals. + + assert(!Functions.empty()); + + // Build a simple layout based on the regular layout of jump tables. + DenseMap GlobalLayout; + unsigned EntrySize = getJumpTableEntrySize(); + for (unsigned I = 0; I != Functions.size(); ++I) + GlobalLayout[Functions[I]] = I * EntrySize; + + // Create a constant to hold the jump table. + ArrayType *JumpTableType = + ArrayType::get(getJumpTableEntryType(), Functions.size()); + auto JumpTable = new GlobalVariable(*M, JumpTableType, + /*isConstant=*/true, + GlobalValue::PrivateLinkage, nullptr); + JumpTable->setSection(ObjectFormat == Triple::MachO + ? "__TEXT,__text,regular,pure_instructions" + : ".text"); + lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout); + + // Build aliases pointing to offsets into the jump table, and replace + // references to the original functions with references to the aliases. + for (unsigned I = 0; I != Functions.size(); ++I) { + Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast( + ConstantExpr::getGetElementPtr( + JumpTableType, JumpTable, + ArrayRef{ConstantInt::get(IntPtrTy, 0), + ConstantInt::get(IntPtrTy, I)}), + Functions[I]->getType()); + if (LinkerSubsectionsViaSymbols || Functions[I]->isDeclarationForLinker()) { + Functions[I]->replaceAllUsesWith(CombinedGlobalElemPtr); + } else { + assert(Functions[I]->getType()->getAddressSpace() == 0); + GlobalAlias *GAlias = GlobalAlias::create(Functions[I]->getValueType(), 0, + Functions[I]->getLinkage(), "", + CombinedGlobalElemPtr, M); + GAlias->setVisibility(Functions[I]->getVisibility()); + GAlias->takeName(Functions[I]); + Functions[I]->replaceAllUsesWith(GAlias); + } + if (!Functions[I]->isDeclarationForLinker()) + Functions[I]->setLinkage(GlobalValue::PrivateLinkage); + } + + // Build and set the jump table's initializer. + std::vector JumpTableEntries; + for (unsigned I = 0; I != Functions.size(); ++I) + JumpTableEntries.push_back( + createJumpTableEntry(JumpTable, Functions[I], I)); + JumpTable->setInitializer( + ConstantArray::get(JumpTableType, JumpTableEntries)); +} + +void LowerTypeTests::buildBitSetsFromDisjointSet( + ArrayRef TypeIds, ArrayRef Globals) { + llvm::DenseMap TypeIdIndices; + for (unsigned I = 0; I != TypeIds.size(); ++I) + TypeIdIndices[TypeIds[I]] = I; + + // For each type identifier, build a set of indices that refer to members of + // the type identifier. + std::vector> TypeMembers(TypeIds.size()); + SmallVector Types; + unsigned GlobalIndex = 0; + for (GlobalObject *GO : Globals) { + Types.clear(); + GO->getMetadata(LLVMContext::MD_type, Types); + for (MDNode *Type : Types) { + // Type = { offset, type identifier } + unsigned TypeIdIndex = TypeIdIndices[Type->getOperand(1)]; + TypeMembers[TypeIdIndex].insert(GlobalIndex); + } + GlobalIndex++; + } + + // Order the sets of indices by size. The GlobalLayoutBuilder works best + // when given small index sets first. + std::stable_sort( + TypeMembers.begin(), TypeMembers.end(), + [](const std::set &O1, const std::set &O2) { + return O1.size() < O2.size(); + }); + + // Create a GlobalLayoutBuilder and provide it with index sets as layout + // fragments. The GlobalLayoutBuilder tries to lay out members of fragments as + // close together as possible. + GlobalLayoutBuilder GLB(Globals.size()); + for (auto &&MemSet : TypeMembers) + GLB.addFragment(MemSet); + + // Build the bitsets from this disjoint set. + if (Globals.empty() || isa(Globals[0])) { + // Build a vector of global variables with the computed layout. + std::vector OrderedGVs(Globals.size()); + auto OGI = OrderedGVs.begin(); + for (auto &&F : GLB.Fragments) { + for (auto &&Offset : F) { + auto GV = dyn_cast(Globals[Offset]); + if (!GV) + report_fatal_error("Type identifier may not contain both global " + "variables and functions"); + *OGI++ = GV; + } + } + + buildBitSetsFromGlobalVariables(TypeIds, OrderedGVs); + } else { + // Build a vector of functions with the computed layout. + std::vector OrderedFns(Globals.size()); + auto OFI = OrderedFns.begin(); + for (auto &&F : GLB.Fragments) { + for (auto &&Offset : F) { + auto Fn = dyn_cast(Globals[Offset]); + if (!Fn) + report_fatal_error("Type identifier may not contain both global " + "variables and functions"); + *OFI++ = Fn; + } + } + + buildBitSetsFromFunctions(TypeIds, OrderedFns); + } +} + +/// Lower all type tests in this module. +bool LowerTypeTests::lower() { + Function *TypeTestFunc = + M->getFunction(Intrinsic::getName(Intrinsic::type_test)); + if (!TypeTestFunc || TypeTestFunc->use_empty()) + return false; + + // Equivalence class set containing type identifiers and the globals that + // reference them. This is used to partition the set of type identifiers in + // the module into disjoint sets. + typedef EquivalenceClasses> + GlobalClassesTy; + GlobalClassesTy GlobalClasses; + + // Verify the type metadata and build a mapping from type identifiers to their + // last observed index in the list of globals. This will be used later to + // deterministically order the list of type identifiers. + llvm::DenseMap TypeIdIndices; + unsigned I = 0; + SmallVector Types; + for (GlobalObject &GO : M->global_objects()) { + Types.clear(); + GO.getMetadata(LLVMContext::MD_type, Types); + for (MDNode *Type : Types) { + verifyTypeMDNode(&GO, Type); + TypeIdIndices[cast(Type)->getOperand(1)] = ++I; + } + } + + for (const Use &U : TypeTestFunc->uses()) { + auto CI = cast(U.getUser()); + + auto BitSetMDVal = dyn_cast(CI->getArgOperand(1)); + if (!BitSetMDVal) + report_fatal_error( + "Second argument of llvm.type.test must be metadata"); + auto BitSet = BitSetMDVal->getMetadata(); + + // Add the call site to the list of call sites for this type identifier. We + // also use TypeTestCallSites to keep track of whether we have seen this + // type identifier before. If we have, we don't need to re-add the + // referenced globals to the equivalence class. + std::pair>::iterator, bool> + Ins = TypeTestCallSites.insert( + std::make_pair(BitSet, std::vector())); + Ins.first->second.push_back(CI); + if (!Ins.second) + continue; + + // Add the type identifier to the equivalence class. + GlobalClassesTy::iterator GCI = GlobalClasses.insert(BitSet); + GlobalClassesTy::member_iterator CurSet = GlobalClasses.findLeader(GCI); + + // Add the referenced globals to the type identifier's equivalence class. + for (GlobalObject &GO : M->global_objects()) { + Types.clear(); + GO.getMetadata(LLVMContext::MD_type, Types); + for (MDNode *Type : Types) + if (Type->getOperand(1) == BitSet) + CurSet = GlobalClasses.unionSets( + CurSet, GlobalClasses.findLeader(GlobalClasses.insert(&GO))); + } + } + + if (GlobalClasses.empty()) + return false; + + // Build a list of disjoint sets ordered by their maximum global index for + // determinism. + std::vector> Sets; + for (GlobalClassesTy::iterator I = GlobalClasses.begin(), + E = GlobalClasses.end(); + I != E; ++I) { + if (!I->isLeader()) continue; + ++NumTypeIdDisjointSets; + + unsigned MaxIndex = 0; + for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I); + MI != GlobalClasses.member_end(); ++MI) { + if ((*MI).is()) + MaxIndex = std::max(MaxIndex, TypeIdIndices[MI->get()]); + } + Sets.emplace_back(I, MaxIndex); + } + std::sort(Sets.begin(), Sets.end(), + [](const std::pair &S1, + const std::pair &S2) { + return S1.second < S2.second; + }); + + // For each disjoint set we found... + for (const auto &S : Sets) { + // Build the list of type identifiers in this disjoint set. + std::vector TypeIds; + std::vector Globals; + for (GlobalClassesTy::member_iterator MI = + GlobalClasses.member_begin(S.first); + MI != GlobalClasses.member_end(); ++MI) { + if ((*MI).is()) + TypeIds.push_back(MI->get()); + else + Globals.push_back(MI->get()); + } + + // Order type identifiers by global index for determinism. This ordering is + // stable as there is a one-to-one mapping between metadata and indices. + std::sort(TypeIds.begin(), TypeIds.end(), [&](Metadata *M1, Metadata *M2) { + return TypeIdIndices[M1] < TypeIdIndices[M2]; + }); + + // Build bitsets for this disjoint set. + buildBitSetsFromDisjointSet(TypeIds, Globals); + } + + allocateByteArrays(); + + return true; +} + +bool LowerTypeTests::runOnModule(Module &M) { + if (skipModule(M)) + return false; + + return lower(); +} Index: llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp +++ llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -748,10 +748,10 @@ // in the current module. PM.add(createCrossDSOCFIPass()); - // Lower bit sets to globals. This pass supports Clang's control flow - // integrity mechanisms (-fsanitize=cfi*) and needs to run at link time if CFI - // is enabled. The pass does nothing if CFI is disabled. - PM.add(createLowerBitSetsPass()); + // Lower type metadata and the type.test intrinsic. This pass supports Clang's + // control flow integrity mechanisms (-fsanitize=cfi*) and needs to run at + // link time if CFI is enabled. The pass does nothing if CFI is disabled. + PM.add(createLowerTypeTestsPass()); if (OptLevel != 0) addLateLTOOptimizationPasses(PM); Index: llvm/trunk/lib/Transforms/IPO/WholeProgramDevirt.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/WholeProgramDevirt.cpp +++ llvm/trunk/lib/Transforms/IPO/WholeProgramDevirt.cpp @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// // // This pass implements whole program optimization of virtual calls in cases -// where we know (via bitset information) that the list of callee is fixed. This +// where we know (via !type metadata) that the list of callees is fixed. This // includes the following: // - Single implementation devirtualization: if a virtual call has a single // possible callee, replace all calls with a direct call to that callee. @@ -31,7 +31,7 @@ #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/MapVector.h" -#include "llvm/Analysis/BitSetUtils.h" +#include "llvm/Analysis/TypeMetadataUtils.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" @@ -89,8 +89,8 @@ // at MinByte. std::vector> Used; for (const VirtualCallTarget &Target : Targets) { - ArrayRef VTUsed = IsAfter ? Target.BS->Bits->After.BytesUsed - : Target.BS->Bits->Before.BytesUsed; + ArrayRef VTUsed = IsAfter ? Target.TM->Bits->After.BytesUsed + : Target.TM->Bits->Before.BytesUsed; uint64_t Offset = IsAfter ? MinByte - Target.minAfterBytes() : MinByte - Target.minBeforeBytes(); @@ -163,17 +163,17 @@ } } -VirtualCallTarget::VirtualCallTarget(Function *Fn, const BitSetInfo *BS) - : Fn(Fn), BS(BS), +VirtualCallTarget::VirtualCallTarget(Function *Fn, const TypeMemberInfo *TM) + : Fn(Fn), TM(TM), IsBigEndian(Fn->getParent()->getDataLayout().isBigEndian()) {} namespace { -// A slot in a set of virtual tables. The BitSetID identifies the set of virtual +// A slot in a set of virtual tables. The TypeID identifies the set of virtual // tables, and the ByteOffset is the offset in bytes from the address point to // the virtual function pointer. struct VTableSlot { - Metadata *BitSetID; + Metadata *TypeID; uint64_t ByteOffset; }; @@ -191,12 +191,12 @@ DenseMapInfo::getTombstoneKey()}; } static unsigned getHashValue(const VTableSlot &I) { - return DenseMapInfo::getHashValue(I.BitSetID) ^ + return DenseMapInfo::getHashValue(I.TypeID) ^ DenseMapInfo::getHashValue(I.ByteOffset); } static bool isEqual(const VTableSlot &LHS, const VTableSlot &RHS) { - return LHS.BitSetID == RHS.BitSetID && LHS.ByteOffset == RHS.ByteOffset; + return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset; } }; @@ -233,11 +233,13 @@ Int8PtrTy(Type::getInt8PtrTy(M.getContext())), Int32Ty(Type::getInt32Ty(M.getContext())) {} - void buildBitSets(std::vector &Bits, - DenseMap> &BitSets); - bool tryFindVirtualCallTargets(std::vector &TargetsForSlot, - const std::set &BitSetInfos, - uint64_t ByteOffset); + void buildTypeIdentifierMap( + std::vector &Bits, + DenseMap> &TypeIdMap); + bool + tryFindVirtualCallTargets(std::vector &TargetsForSlot, + const std::set &TypeMemberInfos, + uint64_t ByteOffset); bool trySingleImplDevirt(ArrayRef TargetsForSlot, MutableArrayRef CallSites); bool tryEvaluateFunctionsWithArgs( @@ -287,60 +289,55 @@ return PreservedAnalyses::none(); } -void DevirtModule::buildBitSets( +void DevirtModule::buildTypeIdentifierMap( std::vector &Bits, - DenseMap> &BitSets) { - NamedMDNode *BitSetNM = M.getNamedMetadata("llvm.bitsets"); - if (!BitSetNM) - return; - + DenseMap> &TypeIdMap) { DenseMap GVToBits; - Bits.reserve(BitSetNM->getNumOperands()); - for (auto Op : BitSetNM->operands()) { - auto OpConstMD = dyn_cast_or_null(Op->getOperand(1)); - if (!OpConstMD) - continue; - auto BitSetID = Op->getOperand(0).get(); - - Constant *OpConst = OpConstMD->getValue(); - if (auto GA = dyn_cast(OpConst)) - OpConst = GA->getAliasee(); - auto OpGlobal = dyn_cast(OpConst); - if (!OpGlobal) - continue; - - uint64_t Offset = - cast( - cast(Op->getOperand(2))->getValue()) - ->getZExtValue(); + Bits.reserve(M.getGlobalList().size()); + SmallVector Types; + for (GlobalVariable &GV : M.globals()) { + Types.clear(); + GV.getMetadata(LLVMContext::MD_type, Types); + if (Types.empty()) + continue; - VTableBits *&BitsPtr = GVToBits[OpGlobal]; + VTableBits *&BitsPtr = GVToBits[&GV]; if (!BitsPtr) { Bits.emplace_back(); - Bits.back().GV = OpGlobal; - Bits.back().ObjectSize = M.getDataLayout().getTypeAllocSize( - OpGlobal->getInitializer()->getType()); + Bits.back().GV = &GV; + Bits.back().ObjectSize = + M.getDataLayout().getTypeAllocSize(GV.getInitializer()->getType()); BitsPtr = &Bits.back(); } - BitSets[BitSetID].insert({BitsPtr, Offset}); + + for (MDNode *Type : Types) { + auto TypeID = Type->getOperand(1).get(); + + uint64_t Offset = + cast( + cast(Type->getOperand(0))->getValue()) + ->getZExtValue(); + + TypeIdMap[TypeID].insert({BitsPtr, Offset}); + } } } bool DevirtModule::tryFindVirtualCallTargets( std::vector &TargetsForSlot, - const std::set &BitSetInfos, uint64_t ByteOffset) { - for (const BitSetInfo &BS : BitSetInfos) { - if (!BS.Bits->GV->isConstant()) + const std::set &TypeMemberInfos, uint64_t ByteOffset) { + for (const TypeMemberInfo &TM : TypeMemberInfos) { + if (!TM.Bits->GV->isConstant()) return false; - auto Init = dyn_cast(BS.Bits->GV->getInitializer()); + auto Init = dyn_cast(TM.Bits->GV->getInitializer()); if (!Init) return false; ArrayType *VTableTy = Init->getType(); uint64_t ElemSize = M.getDataLayout().getTypeAllocSize(VTableTy->getElementType()); - uint64_t GlobalSlotOffset = BS.Offset + ByteOffset; + uint64_t GlobalSlotOffset = TM.Offset + ByteOffset; if (GlobalSlotOffset % ElemSize != 0) return false; @@ -357,7 +354,7 @@ if (Fn->getName() == "__cxa_pure_virtual") continue; - TargetsForSlot.push_back({Fn, &BS}); + TargetsForSlot.push_back({Fn, &TM}); } // Give up if we couldn't find any targets. @@ -430,24 +427,24 @@ MutableArrayRef CallSites) { // IsOne controls whether we look for a 0 or a 1. auto tryUniqueRetValOptFor = [&](bool IsOne) { - const BitSetInfo *UniqueBitSet = 0; + const TypeMemberInfo *UniqueMember = 0; for (const VirtualCallTarget &Target : TargetsForSlot) { if (Target.RetVal == (IsOne ? 1 : 0)) { - if (UniqueBitSet) + if (UniqueMember) return false; - UniqueBitSet = Target.BS; + UniqueMember = Target.TM; } } - // We should have found a unique bit set or bailed out by now. We already + // We should have found a unique member or bailed out by now. We already // checked for a uniform return value in tryUniformRetValOpt. - assert(UniqueBitSet); + assert(UniqueMember); // Replace each call with the comparison. for (auto &&Call : CallSites) { IRBuilder<> B(Call.CS.getInstruction()); - Value *OneAddr = B.CreateBitCast(UniqueBitSet->Bits->GV, Int8PtrTy); - OneAddr = B.CreateConstGEP1_64(OneAddr, UniqueBitSet->Offset); + Value *OneAddr = B.CreateBitCast(UniqueMember->Bits->GV, Int8PtrTy); + OneAddr = B.CreateConstGEP1_64(OneAddr, UniqueMember->Offset); Value *Cmp = B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE, Call.VTable, OneAddr); Call.replaceAndErase(Cmp); @@ -526,7 +523,8 @@ if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second)) continue; - // Find an allocation offset in bits in all vtables in the bitset. + // Find an allocation offset in bits in all vtables associated with the + // type. uint64_t AllocBefore = findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth); uint64_t AllocAfter = @@ -620,9 +618,9 @@ } bool DevirtModule::run() { - Function *BitSetTestFunc = - M.getFunction(Intrinsic::getName(Intrinsic::bitset_test)); - if (!BitSetTestFunc || BitSetTestFunc->use_empty()) + Function *TypeTestFunc = + M.getFunction(Intrinsic::getName(Intrinsic::type_test)); + if (!TypeTestFunc || TypeTestFunc->use_empty()) return false; Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume)); @@ -630,11 +628,12 @@ return false; // Find all virtual calls via a virtual table pointer %p under an assumption - // of the form llvm.assume(llvm.bitset.test(%p, %md)). This indicates that %p - // points to a vtable in the bitset %md. Group calls by (bitset, offset) pair - // (effectively the identity of the virtual function) and store to CallSlots. + // of the form llvm.assume(llvm.type.test(%p, %md)). This indicates that %p + // points to a member of the type identifier %md. Group calls by (type ID, + // offset) pair (effectively the identity of the virtual function) and store + // to CallSlots. DenseSet SeenPtrs; - for (auto I = BitSetTestFunc->use_begin(), E = BitSetTestFunc->use_end(); + for (auto I = TypeTestFunc->use_begin(), E = TypeTestFunc->use_end(); I != E;) { auto CI = dyn_cast(I->getUser()); ++I; @@ -650,18 +649,18 @@ // the vtable pointer before, as it may have been CSE'd with pointers from // other call sites, and we don't want to process call sites multiple times. if (!Assumes.empty()) { - Metadata *BitSet = + Metadata *TypeId = cast(CI->getArgOperand(1))->getMetadata(); Value *Ptr = CI->getArgOperand(0)->stripPointerCasts(); if (SeenPtrs.insert(Ptr).second) { for (DevirtCallSite Call : DevirtCalls) { - CallSlots[{BitSet, Call.Offset}].push_back( + CallSlots[{TypeId, Call.Offset}].push_back( {CI->getArgOperand(0), Call.CS}); } } } - // We no longer need the assumes or the bitset test. + // We no longer need the assumes or the type test. for (auto Assume : Assumes) Assume->eraseFromParent(); // We can't use RecursivelyDeleteTriviallyDeadInstructions here because we @@ -670,20 +669,21 @@ CI->eraseFromParent(); } - // Rebuild llvm.bitsets metadata into a map for easy lookup. + // Rebuild type metadata into a map for easy lookup. std::vector Bits; - DenseMap> BitSets; - buildBitSets(Bits, BitSets); - if (BitSets.empty()) + DenseMap> TypeIdMap; + buildTypeIdentifierMap(Bits, TypeIdMap); + if (TypeIdMap.empty()) return true; - // For each (bitset, offset) pair: + // For each (type, offset) pair: bool DidVirtualConstProp = false; for (auto &S : CallSlots) { - // Search each of the vtables in the bitset for the virtual function - // implementation at offset S.first.ByteOffset, and add to TargetsForSlot. + // Search each of the members of the type identifier for the virtual + // function implementation at offset S.first.ByteOffset, and add to + // TargetsForSlot. std::vector TargetsForSlot; - if (!tryFindVirtualCallTargets(TargetsForSlot, BitSets[S.first.BitSetID], + if (!tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID], S.first.ByteOffset)) continue; Index: llvm/trunk/test/Transforms/CrossDSOCFI/basic.ll =================================================================== --- llvm/trunk/test/Transforms/CrossDSOCFI/basic.ll +++ llvm/trunk/test/Transforms/CrossDSOCFI/basic.ll @@ -16,52 +16,48 @@ ; CHECK-NEXT: br label %[[EXIT]] ; CHECK: [[L1]]: -; CHECK-NEXT: call i1 @llvm.bitset.test(i8* %[[ADDR]], metadata i64 111) +; CHECK-NEXT: call i1 @llvm.type.test(i8* %[[ADDR]], metadata i64 111) ; CHECK-NEXT: br {{.*}} label %[[EXIT]], label %[[FAIL]] ; CHECK: [[L2]]: -; CHECK-NEXT: call i1 @llvm.bitset.test(i8* %[[ADDR]], metadata i64 222) +; CHECK-NEXT: call i1 @llvm.type.test(i8* %[[ADDR]], metadata i64 222) ; CHECK-NEXT: br {{.*}} label %[[EXIT]], label %[[FAIL]] ; CHECK: [[L3]]: -; CHECK-NEXT: call i1 @llvm.bitset.test(i8* %[[ADDR]], metadata i64 333) +; CHECK-NEXT: call i1 @llvm.type.test(i8* %[[ADDR]], metadata i64 333) ; CHECK-NEXT: br {{.*}} label %[[EXIT]], label %[[FAIL]] ; CHECK: [[L4]]: -; CHECK-NEXT: call i1 @llvm.bitset.test(i8* %[[ADDR]], metadata i64 444) +; CHECK-NEXT: call i1 @llvm.type.test(i8* %[[ADDR]], metadata i64 444) ; CHECK-NEXT: br {{.*}} label %[[EXIT]], label %[[FAIL]] target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" -@_ZTV1A = constant i8 0 -@_ZTI1A = constant i8 0 -@_ZTS1A = constant i8 0 -@_ZTV1B = constant i8 0 -@_ZTI1B = constant i8 0 -@_ZTS1B = constant i8 0 +@_ZTV1A = constant i8 0, !type !4, !type !5 +@_ZTV1B = constant i8 0, !type !4, !type !5, !type !6, !type !7 -define signext i8 @f11() { +define signext i8 @f11() !type !0 !type !1 { entry: ret i8 1 } -define signext i8 @f12() { +define signext i8 @f12() !type !0 !type !1 { entry: ret i8 2 } -define signext i8 @f13() { +define signext i8 @f13() !type !0 !type !1 { entry: ret i8 3 } -define i32 @f21() { +define i32 @f21() !type !2 !type !3 { entry: ret i32 4 } -define i32 @f22() { +define i32 @f22() !type !2 !type !3 { entry: ret i32 5 } @@ -71,23 +67,14 @@ ret void } -!llvm.bitsets = !{!0, !1, !2, !3, !4, !7, !8, !9, !10, !11, !12, !13, !14, !15} -!llvm.module.flags = !{!17} +!llvm.module.flags = !{!8} -!0 = !{!"_ZTSFcvE", i8 ()* @f11, i64 0} -!1 = !{i64 111, i8 ()* @f11, i64 0} -!2 = !{!"_ZTSFcvE", i8 ()* @f12, i64 0} -!3 = !{i64 111, i8 ()* @f12, i64 0} -!4 = !{!"_ZTSFcvE", i8 ()* @f13, i64 0} -!5 = !{i64 111, i8 ()* @f13, i64 0} -!6 = !{!"_ZTSFivE", i32 ()* @f21, i64 0} -!7 = !{i64 222, i32 ()* @f21, i64 0} -!8 = !{!"_ZTSFivE", i32 ()* @f22, i64 0} -!9 = !{i64 222, i32 ()* @f22, i64 0} -!10 = !{!"_ZTS1A", i8* @_ZTV1A, i64 16} -!11 = !{i64 333, i8* @_ZTV1A, i64 16} -!12 = !{!"_ZTS1A", i8* @_ZTV1B, i64 16} -!13 = !{i64 333, i8* @_ZTV1B, i64 16} -!14 = !{!"_ZTS1B", i8* @_ZTV1B, i64 16} -!15 = !{i64 444, i8* @_ZTV1B, i64 16} -!17= !{i32 4, !"Cross-DSO CFI", i32 1} +!0 = !{i64 0, !"_ZTSFcvE"} +!1 = !{i64 0, i64 111} +!2 = !{i64 0, !"_ZTSFivE"} +!3 = !{i64 0, i64 222} +!4 = !{i64 16, !"_ZTS1A"} +!5 = !{i64 16, i64 333} +!6 = !{i64 16, !"_ZTS1B"} +!7 = !{i64 16, i64 444} +!8 = !{i32 4, !"Cross-DSO CFI", i32 1} Index: llvm/trunk/test/Transforms/LowerBitSets/constant.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/constant.ll +++ llvm/trunk/test/Transforms/LowerBitSets/constant.ll @@ -1,34 +0,0 @@ -; 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], [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], [2 x i32]* @b, i32 0, i32 0) to i8*), metadata !"bitset1") - ret i1 %x -} Index: llvm/trunk/test/Transforms/LowerBitSets/function-ext.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/function-ext.ll +++ llvm/trunk/test/Transforms/LowerBitSets/function-ext.ll @@ -1,22 +0,0 @@ -; RUN: opt -S -lowerbitsets < %s | FileCheck %s - -; Tests that we correctly handle external references, including the case where -; all functions in a bitset are external references. - -target triple = "x86_64-unknown-linux-gnu" - -declare void @foo() - -; CHECK: @[[JT:.*]] = private constant [1 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @foo to i64), i64 ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text" - -define i1 @bar(i8* %ptr) { - ; CHECK: icmp eq i64 {{.*}}, ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64) - %p = call i1 @llvm.bitset.test(i8* %ptr, metadata !"void") - ret i1 %p -} - -declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - -!0 = !{!"void", void ()* @foo, i64 0} - -!llvm.bitsets = !{!0} Index: llvm/trunk/test/Transforms/LowerBitSets/function.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/function.ll +++ llvm/trunk/test/Transforms/LowerBitSets/function.ll @@ -1,35 +0,0 @@ -; RUN: opt -S -lowerbitsets < %s | FileCheck %s - -; Tests that we correctly create a jump table for bitsets containing 2 or more -; functions. - -target triple = "x86_64-unknown-linux-gnu" -target datalayout = "e-p:64:64" - -; CHECK: @[[JT:.*]] = private constant [2 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[FNAME:.*]] to i64), i64 ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>, <{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[GNAME:.*]] to i64), i64 ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 13) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text" - -; CHECK: @f = alias void (), bitcast ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to void ()*) -; CHECK: @g = alias void (), bitcast (<{ i8, i32, i8, i8, i8 }>* getelementptr inbounds ([2 x <{ i8, i32, i8, i8, i8 }>], [2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]], i64 0, i64 1) to void ()*) - -; CHECK: define private void @[[FNAME]]() { -define void @f() { - ret void -} - -; CHECK: define private void @[[GNAME]]() { -define void @g() { - ret void -} - -!0 = !{!"bitset1", void ()* @f, i32 0} -!1 = !{!"bitset1", void ()* @g, i32 0} - -!llvm.bitsets = !{ !0, !1 } - -declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - -define i1 @foo(i8* %p) { - ; CHECK: sub i64 {{.*}}, ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64) - %x = call i1 @llvm.bitset.test(i8* %p, metadata !"bitset1") - ret i1 %x -} Index: llvm/trunk/test/Transforms/LowerBitSets/layout.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/layout.ll +++ llvm/trunk/test/Transforms/LowerBitSets/layout.ll @@ -1,35 +0,0 @@ -; RUN: opt -S -lowerbitsets < %s | FileCheck %s - -target datalayout = "e-p:32:32" - -; Tests that this set of globals is laid out according to our layout algorithm -; (see GlobalLayoutBuilder in include/llvm/Transforms/IPO/LowerBitSets.h). -; The chosen layout in this case is a, e, b, d, c. - -; CHECK: private constant { i32, [0 x i8], i32, [0 x i8], i32, [0 x i8], i32, [0 x i8], i32 } { i32 1, [0 x i8] zeroinitializer, i32 5, [0 x i8] zeroinitializer, i32 2, [0 x i8] zeroinitializer, i32 4, [0 x i8] zeroinitializer, i32 3 } -@a = constant i32 1 -@b = constant i32 2 -@c = constant i32 3 -@d = constant i32 4 -@e = constant i32 5 - -!0 = !{!"bitset1", i32* @a, i32 0} -!1 = !{!"bitset1", i32* @b, i32 0} -!2 = !{!"bitset1", i32* @c, i32 0} - -!3 = !{!"bitset2", i32* @b, i32 0} -!4 = !{!"bitset2", i32* @d, i32 0} - -!5 = !{!"bitset3", i32* @a, i32 0} -!6 = !{!"bitset3", i32* @e, i32 0} - -!llvm.bitsets = !{ !0, !1, !2, !3, !4, !5, !6 } - -declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - -define void @foo() { - %x = call i1 @llvm.bitset.test(i8* undef, metadata !"bitset1") - %y = call i1 @llvm.bitset.test(i8* undef, metadata !"bitset2") - %z = call i1 @llvm.bitset.test(i8* undef, metadata !"bitset3") - ret void -} Index: llvm/trunk/test/Transforms/LowerBitSets/nonglobal.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/nonglobal.ll +++ llvm/trunk/test/Transforms/LowerBitSets/nonglobal.ll @@ -1,19 +0,0 @@ -; RUN: opt -S -lowerbitsets < %s | FileCheck %s - -target datalayout = "e-p:32:32" - -; CHECK-NOT: @b = alias -@a = constant i32 1 -@b = constant [2 x i32] [i32 2, i32 3] - -!0 = !{!"bitset1", i32* @a, i32 0} -!1 = !{!"bitset1", i32* bitcast ([2 x i32]* @b to i32*), i32 0} - -!llvm.bitsets = !{ !0, !1 } - -declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - -define i1 @foo(i8* %p) { - %x = call i1 @llvm.bitset.test(i8* %p, metadata !"bitset1") - ret i1 %x -} Index: llvm/trunk/test/Transforms/LowerBitSets/nonstring.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/nonstring.ll +++ llvm/trunk/test/Transforms/LowerBitSets/nonstring.ll @@ -1,34 +0,0 @@ -; RUN: opt -S -lowerbitsets < %s | FileCheck %s - -; Tests that non-string metadata nodes may be used as bitset identifiers. - -target datalayout = "e-p:32:32" - -; CHECK: @[[ANAME:.*]] = private constant { i32 } -; CHECK: @[[BNAME:.*]] = private constant { [2 x i32] } - -@a = constant i32 1 -@b = constant [2 x i32] [i32 2, i32 3] - -!0 = !{!2, i32* @a, i32 0} -!1 = !{!3, [2 x i32]* @b, i32 0} -!2 = distinct !{} -!3 = distinct !{} - -!llvm.bitsets = !{ !0, !1 } - -declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - -; CHECK-LABEL: @foo -define i1 @foo(i8* %p) { - ; CHECK: icmp eq i32 {{.*}}, ptrtoint ({ i32 }* @[[ANAME]] to i32) - %x = call i1 @llvm.bitset.test(i8* %p, metadata !2) - ret i1 %x -} - -; CHECK-LABEL: @bar -define i1 @bar(i8* %p) { - ; CHECK: icmp eq i32 {{.*}}, ptrtoint ({ [2 x i32] }* @[[BNAME]] to i32) - %x = call i1 @llvm.bitset.test(i8* %p, metadata !3) - ret i1 %x -} Index: llvm/trunk/test/Transforms/LowerBitSets/pr25902.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/pr25902.ll +++ llvm/trunk/test/Transforms/LowerBitSets/pr25902.ll @@ -1,21 +0,0 @@ -; PR25902: gold plugin crash. -; RUN: opt -mtriple=i686-pc -S -lowerbitsets < %s - -define void @f(void ()* %p) { -entry: - %a = bitcast void ()* %p to i8*, !nosanitize !1 - %b = call i1 @llvm.bitset.test(i8* %a, metadata !"_ZTSFvvE"), !nosanitize !1 - ret void -} - -define void @g() { -entry: - ret void -} - -declare i1 @llvm.bitset.test(i8*, metadata) - -!llvm.bitsets = !{!0} - -!0 = !{!"_ZTSFvvE", void ()* @g, i64 0} -!1 = !{} Index: llvm/trunk/test/Transforms/LowerBitSets/section.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/section.ll +++ llvm/trunk/test/Transforms/LowerBitSets/section.ll @@ -1,26 +0,0 @@ -; Test that functions with "section" attribute are accepted, and jumptables are -; emitted in ".text". - -; RUN: opt -S -lowerbitsets < %s | FileCheck %s - -target triple = "x86_64-unknown-linux-gnu" - -; CHECK: @[[A:.*]] = private constant {{.*}} section ".text" -; CHECK: @f = alias void (), bitcast ({{.*}}* @[[A]] to void ()*) -; CHECK: define private void {{.*}} section "xxx" - -define void @f() section "xxx" { -entry: - ret void -} - -define i1 @g() { -entry: - %0 = call i1 @llvm.bitset.test(i8* bitcast (void ()* @f to i8*), metadata !"_ZTSFvE") - ret i1 %0 -} - -declare i1 @llvm.bitset.test(i8*, metadata) nounwind readnone - -!llvm.bitsets = !{!0} -!0 = !{!"_ZTSFvE", void ()* @f, i64 0} Index: llvm/trunk/test/Transforms/LowerBitSets/simple.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/simple.ll +++ llvm/trunk/test/Transforms/LowerBitSets/simple.ll @@ -1,137 +0,0 @@ -; RUN: opt -S -lowerbitsets < %s | FileCheck %s -; RUN: opt -S -lowerbitsets -mtriple=x86_64-apple-macosx10.8.0 < %s | FileCheck -check-prefix=CHECK-DARWIN %s -; RUN: opt -S -O3 < %s | FileCheck -check-prefix=CHECK-NODISCARD %s - -target datalayout = "e-p:32:32" - -; CHECK: [[G:@[^ ]*]] = private constant { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] } { i32 1, [0 x i8] zeroinitializer, [63 x i32] zeroinitializer, [4 x i8] zeroinitializer, i32 3, [0 x i8] zeroinitializer, [2 x i32] [i32 4, i32 5] } -@a = constant i32 1 -@b = hidden constant [63 x i32] zeroinitializer -@c = protected constant i32 3 -@d = constant [2 x i32] [i32 4, i32 5] - -; CHECK: [[BA:@[^ ]*]] = private constant [68 x i8] c"\03\01\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\02\00\01" - -; Offset 0, 4 byte alignment -!0 = !{!"bitset1", i32* @a, i32 0} -; CHECK-NODISCARD-DAG: !{!"bitset1", i32* @a, i32 0} -!1 = !{!"bitset1", [63 x i32]* @b, i32 0} -; CHECK-NODISCARD-DAG: !{!"bitset1", [63 x i32]* @b, i32 0} -!2 = !{!"bitset1", [2 x i32]* @d, i32 4} -; CHECK-NODISCARD-DAG: !{!"bitset1", [2 x i32]* @d, i32 4} - -; Offset 4, 256 byte alignment -!3 = !{!"bitset2", [63 x i32]* @b, i32 0} -; CHECK-NODISCARD-DAG: !{!"bitset2", [63 x i32]* @b, i32 0} -!4 = !{!"bitset2", i32* @c, i32 0} -; CHECK-NODISCARD-DAG: !{!"bitset2", i32* @c, i32 0} - -; Entries whose second operand is null (the result of a global being DCE'd) -; should be ignored. -!5 = !{!"bitset2", null, i32 0} - -; Offset 0, 4 byte alignment -!6 = !{!"bitset3", i32* @a, i32 0} -; CHECK-NODISCARD-DAG: !{!"bitset3", i32* @a, i32 0} -!7 = !{!"bitset3", i32* @c, i32 0} -; CHECK-NODISCARD-DAG: !{!"bitset3", i32* @c, i32 0} - -!llvm.bitsets = !{ !0, !1, !2, !3, !4, !5, !6, !7 } - -; CHECK: @bits_use{{[0-9]*}} = private alias i8, i8* @bits{{[0-9]*}} -; CHECK: @bits_use.{{[0-9]*}} = private alias i8, i8* @bits{{[0-9]*}} -; CHECK: @bits_use.{{[0-9]*}} = private alias i8, i8* @bits{{[0-9]*}} - -; CHECK: @a = alias i32, getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 0) -; CHECK: @b = hidden alias [63 x i32], getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 2) -; CHECK: @c = protected alias i32, getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 4) -; CHECK: @d = alias [2 x i32], getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 6) - -; CHECK-DARWIN: @aptr = constant i32* getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G:@[^ ]*]], i32 0, i32 0) -@aptr = constant i32* @a - -; CHECK-DARWIN: @bptr = constant [63 x i32]* getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 2) -@bptr = constant [63 x i32]* @b - -; CHECK-DARWIN: @cptr = constant i32* getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 4) -@cptr = constant i32* @c - -; CHECK-DARWIN: @dptr = constant [2 x i32]* getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 6) -@dptr = constant [2 x i32]* @d - -; CHECK-DARWIN: [[G]] = private constant - -; CHECK: @bits{{[0-9]*}} = private alias i8, getelementptr inbounds ([68 x i8], [68 x i8]* [[BA]], i32 0, i32 0) -; CHECK: @bits.{{[0-9]*}} = private alias i8, getelementptr inbounds ([68 x i8], [68 x i8]* [[BA]], i32 0, i32 0) - -declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - -; CHECK: @foo(i32* [[A0:%[^ ]*]]) -define i1 @foo(i32* %p) { - ; CHECK-NOT: llvm.bitset.test - - ; 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: 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]], {{%[^ ]*}} ] - %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset1") - - ; CHECK-NOT: llvm.bitset.test - %y = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset1") - - ; CHECK: ret i1 [[R16]] - ret i1 %x -} - -; CHECK: @bar(i32* [[B0:%[^ ]*]]) -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]], add (i32 ptrtoint ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]] to i32), i32 4) - ; 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 - %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !"bitset2") - - ; 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: 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.bitset.test(i8* %pi8, metadata !"bitset3") - ; CHECK: ret i1 [[T16]] - ret i1 %x -} - -; CHECK-NOT: !llvm.bitsets Index: llvm/trunk/test/Transforms/LowerBitSets/single-offset.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/single-offset.ll +++ llvm/trunk/test/Transforms/LowerBitSets/single-offset.ll @@ -1,40 +0,0 @@ -; RUN: opt -S -lowerbitsets < %s | FileCheck %s - -target datalayout = "e-p:32:32" - -; CHECK: [[G:@[^ ]*]] = private constant { i32, [0 x i8], i32 } -@a = constant i32 1 -@b = constant i32 2 - -!0 = !{!"bitset1", i32* @a, i32 0} -!1 = !{!"bitset1", i32* @b, i32 0} -!2 = !{!"bitset2", i32* @a, i32 0} -!3 = !{!"bitset3", i32* @b, i32 0} - -!llvm.bitsets = !{ !0, !1, !2, !3 } - -declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - -; CHECK: @foo(i8* [[A0:%[^ ]*]]) -define i1 @foo(i8* %p) { - ; CHECK: [[R0:%[^ ]*]] = ptrtoint i8* [[A0]] to i32 - ; CHECK: [[R1:%[^ ]*]] = icmp eq i32 [[R0]], ptrtoint ({ i32, [0 x i8], i32 }* [[G]] to i32) - %x = call i1 @llvm.bitset.test(i8* %p, metadata !"bitset2") - ; CHECK: ret i1 [[R1]] - ret i1 %x -} - -; CHECK: @bar(i8* [[B0:%[^ ]*]]) -define i1 @bar(i8* %p) { - ; CHECK: [[S0:%[^ ]*]] = ptrtoint i8* [[B0]] to i32 - ; CHECK: [[S1:%[^ ]*]] = icmp eq i32 [[S0]], add (i32 ptrtoint ({ i32, [0 x i8], i32 }* [[G]] to i32), i32 4) - %x = call i1 @llvm.bitset.test(i8* %p, metadata !"bitset3") - ; CHECK: ret i1 [[S1]] - ret i1 %x -} - -; CHECK: @x( -define i1 @x(i8* %p) { - %x = call i1 @llvm.bitset.test(i8* %p, metadata !"bitset1") - ret i1 %x -} Index: llvm/trunk/test/Transforms/LowerBitSets/unnamed.ll =================================================================== --- llvm/trunk/test/Transforms/LowerBitSets/unnamed.ll +++ llvm/trunk/test/Transforms/LowerBitSets/unnamed.ll @@ -1,20 +0,0 @@ -; RUN: opt -S -lowerbitsets < %s | FileCheck %s - -target datalayout = "e-p:32:32" - -; CHECK: @{{[0-9]+}} = alias -; CHECK: @{{[0-9]+}} = alias -@0 = constant i32 1 -@1 = constant [2 x i32] [i32 2, i32 3] - -!0 = !{!"bitset1", i32* @0, i32 0} -!1 = !{!"bitset1", [2 x i32]* @1, i32 4} - -!llvm.bitsets = !{ !0, !1 } - -declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone - -define i1 @foo(i8* %p) { - %x = call i1 @llvm.bitset.test(i8* %p, metadata !"bitset1") - ret i1 %x -} Index: llvm/trunk/test/Transforms/LowerTypeTests/constant.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/constant.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/constant.ll @@ -0,0 +1,32 @@ +; RUN: opt -S -lowertypetests < %s | FileCheck %s + +target datalayout = "e-p:32:32" + +@a = constant i32 1, !type !0 +@b = constant [2 x i32] [i32 2, i32 3], !type !1 + +!0 = !{i32 0, !"typeid1"} +!1 = !{i32 4, !"typeid1"} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +; CHECK: @foo( +define i1 @foo() { + ; CHECK: ret i1 true + %x = call i1 @llvm.type.test(i8* bitcast (i32* @a to i8*), metadata !"typeid1") + ret i1 %x +} + +; CHECK: @bar( +define i1 @bar() { + ; CHECK: ret i1 true + %x = call i1 @llvm.type.test(i8* bitcast (i32* getelementptr ([2 x i32], [2 x i32]* @b, i32 0, i32 1) to i8*), metadata !"typeid1") + ret i1 %x +} + +; CHECK: @baz( +define i1 @baz() { + ; CHECK-NOT: ret i1 true + %x = call i1 @llvm.type.test(i8* bitcast (i32* getelementptr ([2 x i32], [2 x i32]* @b, i32 0, i32 0) to i8*), metadata !"typeid1") + ret i1 %x +} Index: llvm/trunk/test/Transforms/LowerTypeTests/function-ext.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/function-ext.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/function-ext.ll @@ -0,0 +1,20 @@ +; RUN: opt -S -lowertypetests < %s | FileCheck %s + +; Tests that we correctly handle external references, including the case where +; all functions in a bitset are external references. + +target triple = "x86_64-unknown-linux-gnu" + +declare !type !0 void @foo() + +; CHECK: @[[JT:.*]] = private constant [1 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @foo to i64), i64 ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text" + +define i1 @bar(i8* %ptr) { + ; CHECK: icmp eq i64 {{.*}}, ptrtoint ([1 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64) + %p = call i1 @llvm.type.test(i8* %ptr, metadata !"void") + ret i1 %p +} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +!0 = !{i64 0, !"void"} Index: llvm/trunk/test/Transforms/LowerTypeTests/function.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/function.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/function.ll @@ -0,0 +1,32 @@ +; RUN: opt -S -lowertypetests < %s | FileCheck %s + +; Tests that we correctly create a jump table for bitsets containing 2 or more +; functions. + +target triple = "x86_64-unknown-linux-gnu" +target datalayout = "e-p:64:64" + +; CHECK: @[[JT:.*]] = private constant [2 x <{ i8, i32, i8, i8, i8 }>] [<{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[FNAME:.*]] to i64), i64 ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 5) to i32), i8 -52, i8 -52, i8 -52 }>, <{ i8, i32, i8, i8, i8 }> <{ i8 -23, i32 trunc (i64 sub (i64 sub (i64 ptrtoint (void ()* @[[GNAME:.*]] to i64), i64 ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64)), i64 13) to i32), i8 -52, i8 -52, i8 -52 }>], section ".text" + +; CHECK: @f = alias void (), bitcast ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to void ()*) +; CHECK: @g = alias void (), bitcast (<{ i8, i32, i8, i8, i8 }>* getelementptr inbounds ([2 x <{ i8, i32, i8, i8, i8 }>], [2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]], i64 0, i64 1) to void ()*) + +; CHECK: define private void @[[FNAME]]() +define void @f() !type !0 { + ret void +} + +; CHECK: define private void @[[GNAME]]() +define void @g() !type !0 { + ret void +} + +!0 = !{i32 0, !"typeid1"} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +define i1 @foo(i8* %p) { + ; CHECK: sub i64 {{.*}}, ptrtoint ([2 x <{ i8, i32, i8, i8, i8 }>]* @[[JT]] to i64) + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1") + ret i1 %x +} Index: llvm/trunk/test/Transforms/LowerTypeTests/layout.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/layout.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/layout.ll @@ -0,0 +1,27 @@ +; RUN: opt -S -lowertypetests < %s | FileCheck %s + +target datalayout = "e-p:32:32" + +; Tests that this set of globals is laid out according to our layout algorithm +; (see GlobalLayoutBuilder in include/llvm/Transforms/IPO/LowerTypeTests.h). +; The chosen layout in this case is a, e, b, d, c. + +; CHECK: private constant { i32, [0 x i8], i32, [0 x i8], i32, [0 x i8], i32, [0 x i8], i32 } { i32 1, [0 x i8] zeroinitializer, i32 5, [0 x i8] zeroinitializer, i32 2, [0 x i8] zeroinitializer, i32 4, [0 x i8] zeroinitializer, i32 3 } +@a = constant i32 1, !type !0, !type !2 +@b = constant i32 2, !type !0, !type !1 +@c = constant i32 3, !type !0 +@d = constant i32 4, !type !1 +@e = constant i32 5, !type !2 + +!0 = !{i32 0, !"typeid1"} +!1 = !{i32 0, !"typeid2"} +!2 = !{i32 0, !"typeid3"} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +define void @foo() { + %x = call i1 @llvm.type.test(i8* undef, metadata !"typeid1") + %y = call i1 @llvm.type.test(i8* undef, metadata !"typeid2") + %z = call i1 @llvm.type.test(i8* undef, metadata !"typeid3") + ret void +} Index: llvm/trunk/test/Transforms/LowerTypeTests/nonstring.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/nonstring.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/nonstring.ll @@ -0,0 +1,32 @@ +; RUN: opt -S -lowertypetests < %s | FileCheck %s + +; Tests that non-string metadata nodes may be used as bitset identifiers. + +target datalayout = "e-p:32:32" + +; CHECK: @[[ANAME:.*]] = private constant { i32 } +; CHECK: @[[BNAME:.*]] = private constant { [2 x i32] } + +@a = constant i32 1, !type !0 +@b = constant [2 x i32] [i32 2, i32 3], !type !1 + +!0 = !{i32 0, !2} +!1 = !{i32 0, !3} +!2 = distinct !{} +!3 = distinct !{} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +; CHECK-LABEL: @foo +define i1 @foo(i8* %p) { + ; CHECK: icmp eq i32 {{.*}}, ptrtoint ({ i32 }* @[[ANAME]] to i32) + %x = call i1 @llvm.type.test(i8* %p, metadata !2) + ret i1 %x +} + +; CHECK-LABEL: @bar +define i1 @bar(i8* %p) { + ; CHECK: icmp eq i32 {{.*}}, ptrtoint ({ [2 x i32] }* @[[BNAME]] to i32) + %x = call i1 @llvm.type.test(i8* %p, metadata !3) + ret i1 %x +} Index: llvm/trunk/test/Transforms/LowerTypeTests/pr25902.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/pr25902.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/pr25902.ll @@ -0,0 +1,19 @@ +; PR25902: gold plugin crash. +; RUN: opt -mtriple=i686-pc -S -lowertypetests < %s + +define void @f(void ()* %p) { +entry: + %a = bitcast void ()* %p to i8*, !nosanitize !1 + %b = call i1 @llvm.type.test(i8* %a, metadata !"_ZTSFvvE"), !nosanitize !1 + ret void +} + +define void @g() !type !0 { +entry: + ret void +} + +declare i1 @llvm.type.test(i8*, metadata) + +!0 = !{i64 0, !"_ZTSFvvE"} +!1 = !{} Index: llvm/trunk/test/Transforms/LowerTypeTests/section.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/section.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/section.ll @@ -0,0 +1,25 @@ +; Test that functions with "section" attribute are accepted, and jumptables are +; emitted in ".text". + +; RUN: opt -S -lowertypetests < %s | FileCheck %s + +target triple = "x86_64-unknown-linux-gnu" + +; CHECK: @[[A:.*]] = private constant {{.*}} section ".text" +; CHECK: @f = alias void (), bitcast ({{.*}}* @[[A]] to void ()*) +; CHECK: define private void {{.*}} section "xxx" + +define void @f() section "xxx" !type !0 { +entry: + ret void +} + +define i1 @g() { +entry: + %0 = call i1 @llvm.type.test(i8* bitcast (void ()* @f to i8*), metadata !"_ZTSFvE") + ret i1 %0 +} + +declare i1 @llvm.type.test(i8*, metadata) nounwind readnone + +!0 = !{i64 0, !"_ZTSFvE"} Index: llvm/trunk/test/Transforms/LowerTypeTests/simple.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/simple.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/simple.ll @@ -0,0 +1,127 @@ +; RUN: opt -S -lowertypetests < %s | FileCheck %s +; RUN: opt -S -lowertypetests -mtriple=x86_64-apple-macosx10.8.0 < %s | FileCheck -check-prefix=CHECK-DARWIN %s +; RUN: opt -S -O3 < %s | FileCheck -check-prefix=CHECK-NODISCARD %s + +target datalayout = "e-p:32:32" + +; CHECK: [[G:@[^ ]*]] = private constant { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] } { i32 1, [0 x i8] zeroinitializer, [63 x i32] zeroinitializer, [4 x i8] zeroinitializer, i32 3, [0 x i8] zeroinitializer, [2 x i32] [i32 4, i32 5] } +@a = constant i32 1, !type !0, !type !2 +@b = hidden constant [63 x i32] zeroinitializer, !type !0, !type !1 +@c = protected constant i32 3, !type !1, !type !2 +@d = constant [2 x i32] [i32 4, i32 5], !type !3 + +; CHECK-NODISCARD: !type +; CHECK-NODISCARD: !type +; CHECK-NODISCARD: !type +; CHECK-NODISCARD: !type +; CHECK-NODISCARD: !type +; CHECK-NODISCARD: !type +; CHECK-NODISCARD: !type + +; CHECK: [[BA:@[^ ]*]] = private constant [68 x i8] c"\03\01\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\02\00\01" + +; Offset 0, 4 byte alignment +!0 = !{i32 0, !"typeid1"} +!3 = !{i32 4, !"typeid1"} + +; Offset 4, 256 byte alignment +!1 = !{i32 0, !"typeid2"} + +; Offset 0, 4 byte alignment +!2 = !{i32 0, !"typeid3"} + +; CHECK: @bits_use{{[0-9]*}} = private alias i8, i8* @bits{{[0-9]*}} +; CHECK: @bits_use.{{[0-9]*}} = private alias i8, i8* @bits{{[0-9]*}} +; CHECK: @bits_use.{{[0-9]*}} = private alias i8, i8* @bits{{[0-9]*}} + +; CHECK: @a = alias i32, getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 0) +; CHECK: @b = hidden alias [63 x i32], getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 2) +; CHECK: @c = protected alias i32, getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 4) +; CHECK: @d = alias [2 x i32], getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 6) + +; CHECK-DARWIN: @aptr = constant i32* getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G:@[^ ]*]], i32 0, i32 0) +@aptr = constant i32* @a + +; CHECK-DARWIN: @bptr = constant [63 x i32]* getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 2) +@bptr = constant [63 x i32]* @b + +; CHECK-DARWIN: @cptr = constant i32* getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 4) +@cptr = constant i32* @c + +; CHECK-DARWIN: @dptr = constant [2 x i32]* getelementptr inbounds ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }, { i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]], i32 0, i32 6) +@dptr = constant [2 x i32]* @d + +; CHECK-DARWIN: [[G]] = private constant + +; CHECK: @bits{{[0-9]*}} = private alias i8, getelementptr inbounds ([68 x i8], [68 x i8]* [[BA]], i32 0, i32 0) +; CHECK: @bits.{{[0-9]*}} = private alias i8, getelementptr inbounds ([68 x i8], [68 x i8]* [[BA]], i32 0, i32 0) + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +; CHECK: @foo(i32* [[A0:%[^ ]*]]) +define i1 @foo(i32* %p) { + ; CHECK-NOT: llvm.type.test + + ; 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: 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]], {{%[^ ]*}} ] + %x = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid1") + + ; CHECK-NOT: llvm.type.test + %y = call i1 @llvm.type.test(i8* %pi8, metadata !"typeid1") + + ; CHECK: ret i1 [[R16]] + ret i1 %x +} + +; CHECK: @bar(i32* [[B0:%[^ ]*]]) +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]], add (i32 ptrtoint ({ i32, [0 x i8], [63 x i32], [4 x i8], i32, [0 x i8], [2 x i32] }* [[G]] to i32), i32 4) + ; 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 + %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: 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 +} Index: llvm/trunk/test/Transforms/LowerTypeTests/single-offset.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/single-offset.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/single-offset.ll @@ -0,0 +1,37 @@ +; RUN: opt -S -lowertypetests < %s | FileCheck %s + +target datalayout = "e-p:32:32" + +; CHECK: [[G:@[^ ]*]] = private constant { i32, [0 x i8], i32 } +@a = constant i32 1, !type !0, !type !1 +@b = constant i32 2, !type !0, !type !2 + +!0 = !{i32 0, !"typeid1"} +!1 = !{i32 0, !"typeid2"} +!2 = !{i32 0, !"typeid3"} + +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone + +; CHECK: @foo(i8* [[A0:%[^ ]*]]) +define i1 @foo(i8* %p) { + ; CHECK: [[R0:%[^ ]*]] = ptrtoint i8* [[A0]] to i32 + ; CHECK: [[R1:%[^ ]*]] = icmp eq i32 [[R0]], ptrtoint ({ i32, [0 x i8], i32 }* [[G]] to i32) + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid2") + ; CHECK: ret i1 [[R1]] + ret i1 %x +} + +; CHECK: @bar(i8* [[B0:%[^ ]*]]) +define i1 @bar(i8* %p) { + ; CHECK: [[S0:%[^ ]*]] = ptrtoint i8* [[B0]] to i32 + ; CHECK: [[S1:%[^ ]*]] = icmp eq i32 [[S0]], add (i32 ptrtoint ({ i32, [0 x i8], i32 }* [[G]] to i32), i32 4) + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid3") + ; CHECK: ret i1 [[S1]] + ret i1 %x +} + +; CHECK: @x( +define i1 @x(i8* %p) { + %x = call i1 @llvm.type.test(i8* %p, metadata !"typeid1") + ret i1 %x +} Index: llvm/trunk/test/Transforms/LowerTypeTests/unnamed.ll =================================================================== --- llvm/trunk/test/Transforms/LowerTypeTests/unnamed.ll +++ llvm/trunk/test/Transforms/LowerTypeTests/unnamed.ll @@ -0,0 +1,18 @@ +; RUN: opt -S -lowertypetests < %s | FileCheck %s + +target datalayout = "e-p:32:32" + +; CHECK: @{{[0-9]+}} = alias +; CHECK: @{{[0-9]+}} = alias +@0 = constant i32 1, !type !0 +@1 = constant [2 x i32] [i32 2, i32 3], !type !1 + +!0 = !{i32 0, !"typeid1"} +!1 = !{i32 4, !"typeid1"} + +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") + ret i1 %x +} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/bad-read-from-vtable.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/bad-read-from-vtable.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/bad-read-from-vtable.ll @@ -3,7 +3,7 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt = global [2 x i8*] [i8* zeroinitializer, i8* bitcast (void (i8*)* @vf to i8*)] +@vt = global [2 x i8*] [i8* zeroinitializer, i8* bitcast (void (i8*)* @vf to i8*)], !type !0 define void @vf(i8* %this) { ret void @@ -14,7 +14,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr i8, i8* %vtablei8, i32 1 %fptrptr_casted = bitcast i8* %fptrptr to i8** @@ -30,7 +30,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr i8, i8* %vtablei8, i32 16 %fptrptr_casted = bitcast i8* %fptrptr to i8** @@ -46,7 +46,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr i8, i8* %vtablei8, i32 0 %fptrptr_casted = bitcast i8* %fptrptr to i8** @@ -57,8 +57,7 @@ ret void } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [2 x i8*]* @vt, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/constant-arg.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/constant-arg.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/constant-arg.ll @@ -9,10 +9,10 @@ ; CHECK: private constant { [8 x i8], [1 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\00\00\00\00\01", [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf4 to i8*)], [0 x i8] zeroinitializer } ; CHECK: private constant { [8 x i8], [1 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\00\00\00\00\02", [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf8 to i8*)], [0 x i8] zeroinitializer } -@vt1 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf1 to i8*)] -@vt2 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf2 to i8*)] -@vt4 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf4 to i8*)] -@vt8 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf8 to i8*)] +@vt1 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf1 to i8*)], !type !0 +@vt2 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf2 to i8*)], !type !0 +@vt4 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf4 to i8*)], !type !0 +@vt8 = constant [1 x i8*] [i8* bitcast (i1 (i8*, i32)* @vf8 to i8*)], !type !0 define i1 @vf1(i8* %this, i32 %arg) readnone { %and = and i32 %arg, 1 @@ -43,7 +43,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -59,7 +59,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -70,11 +70,7 @@ ret i1 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!2 = !{!"bitset", [1 x i8*]* @vt4, i32 0} -!3 = !{!"bitset", [1 x i8*]* @vt8, i32 0} -!llvm.bitsets = !{!0, !1, !2, !3} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/devirt-single-impl.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/devirt-single-impl.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/devirt-single-impl.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)] -@vt2 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)] +@vt1 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)], !type !0 +@vt2 = constant [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)], !type !0 define void @vf(i8* %this) { ret void @@ -15,7 +15,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -25,9 +25,7 @@ ret void } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0, !1} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/non-array-vtable.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/non-array-vtable.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/non-array-vtable.ll @@ -3,7 +3,7 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt = constant i8* bitcast (void (i8*)* @vf to i8*) +@vt = constant i8* bitcast (void (i8*)* @vf to i8*), !type !0 define void @vf(i8* %this) { ret void @@ -14,7 +14,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -24,8 +24,7 @@ ret void } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", i8** @vt, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/non-constant-vtable.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/non-constant-vtable.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/non-constant-vtable.ll @@ -3,7 +3,7 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt = global [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)] +@vt = global [1 x i8*] [i8* bitcast (void (i8*)* @vf to i8*)], !type !0 define void @vf(i8* %this) { ret void @@ -14,7 +14,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -24,8 +24,7 @@ ret void } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/uniform-retval-invoke.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/uniform-retval-invoke.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/uniform-retval-invoke.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf1 to i8*)] -@vt2 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf2 to i8*)] +@vt1 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf1 to i8*)], !type !0 +@vt2 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf2 to i8*)], !type !0 define i32 @vf1(i8* %this) readnone { ret i32 123 @@ -19,7 +19,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -37,9 +37,7 @@ ret i32 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0, !1} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/uniform-retval.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/uniform-retval.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/uniform-retval.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf1 to i8*)] -@vt2 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf2 to i8*)] +@vt1 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf1 to i8*)], !type !0 +@vt2 = constant [1 x i8*] [i8* bitcast (i32 (i8*)* @vf2 to i8*)], !type !0 define i32 @vf1(i8* %this) readnone { ret i32 123 @@ -19,7 +19,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -30,9 +30,7 @@ ret i32 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0, !1} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/unique-retval.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/unique-retval.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/unique-retval.ll @@ -3,10 +3,10 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf0 to i8*)] -@vt2 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf0 to i8*)] -@vt3 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf1 to i8*)] -@vt4 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf1 to i8*)] +@vt1 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf0 to i8*)], !type !0 +@vt2 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf0 to i8*)], !type !0, !type !1 +@vt3 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf1 to i8*)], !type !0, !type !1 +@vt4 = constant [1 x i8*] [i8* bitcast (i1 (i8*)* @vf1 to i8*)], !type !1 define i1 @vf0(i8* %this) readnone { ret i1 0 @@ -22,7 +22,7 @@ %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr ; CHECK: [[VT1:%[^ ]*]] = bitcast [1 x i8*]* {{.*}} to i8* %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset1") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid1") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -39,7 +39,7 @@ %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr ; CHECK: [[VT2:%[^ ]*]] = bitcast [1 x i8*]* {{.*}} to i8* %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset2") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid2") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -49,13 +49,8 @@ ret i1 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset1", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset1", [1 x i8*]* @vt2, i32 0} -!2 = !{!"bitset1", [1 x i8*]* @vt3, i32 0} -!3 = !{!"bitset2", [1 x i8*]* @vt2, i32 0} -!4 = !{!"bitset2", [1 x i8*]* @vt3, i32 0} -!5 = !{!"bitset2", [1 x i8*]* @vt4, i32 0} -!llvm.bitsets = !{!0, !1, !2, !3, !4, !5} +!0 = !{i32 0, !"typeid1"} +!1 = !{i32 0, !"typeid2"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-accesses-memory.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-accesses-memory.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-accesses-memory.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)] -@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)] +@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)], !type !0 +@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)], !type !0 define i32 @vf1(i8* %this, i32 %arg) { ret i32 %arg @@ -19,7 +19,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -29,9 +29,7 @@ ret i32 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-no-this.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-no-this.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-no-this.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = global [1 x i8*] [i8* bitcast (i32 ()* @vf1 to i8*)] -@vt2 = global [1 x i8*] [i8* bitcast (i32 ()* @vf2 to i8*)] +@vt1 = global [1 x i8*] [i8* bitcast (i32 ()* @vf1 to i8*)], !type !0 +@vt2 = global [1 x i8*] [i8* bitcast (i32 ()* @vf2 to i8*)], !type !0 define i32 @vf1() readnone { ret i32 1 @@ -19,7 +19,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -29,9 +29,7 @@ ret i32 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-non-constant-arg.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-non-constant-arg.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-non-constant-arg.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)] -@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)] +@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)], !type !0 +@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)], !type !0 define i32 @vf1(i8* %this, i32 %arg) readnone { ret i32 %arg @@ -19,7 +19,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -29,9 +29,7 @@ ret void } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-too-wide-ints.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-too-wide-ints.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-too-wide-ints.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = global [1 x i8*] [i8* bitcast (i128 (i8*, i128)* @vf1 to i8*)] -@vt2 = global [1 x i8*] [i8* bitcast (i128 (i8*, i128)* @vf2 to i8*)] +@vt1 = global [1 x i8*] [i8* bitcast (i128 (i8*, i128)* @vf1 to i8*)], !type !0 +@vt2 = global [1 x i8*] [i8* bitcast (i128 (i8*, i128)* @vf2 to i8*)], !type !0 define i128 @vf1(i8* %this, i128 %arg) readnone { ret i128 %arg @@ -19,7 +19,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -29,9 +29,7 @@ ret i128 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-type-mismatch.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-type-mismatch.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-type-mismatch.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)] -@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)] +@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1 to i8*)], !type !0 +@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2 to i8*)], !type !0 define i32 @vf1(i8* %this, i32 %arg) readnone { ret i32 %arg @@ -19,7 +19,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -34,7 +34,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -49,7 +49,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -59,9 +59,7 @@ ret i64 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-uses-this.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-uses-this.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/vcp-uses-this.ll @@ -3,8 +3,8 @@ target datalayout = "e-p:64:64" target triple = "x86_64-unknown-linux-gnu" -@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*)* @vf1 to i8*)] -@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*)* @vf2 to i8*)] +@vt1 = global [1 x i8*] [i8* bitcast (i32 (i8*)* @vf1 to i8*)], !type !0 +@vt2 = global [1 x i8*] [i8* bitcast (i32 (i8*)* @vf2 to i8*)], !type !0 define i32 @vf1(i8* %this) readnone { %this_int = ptrtoint i8* %this to i32 @@ -21,7 +21,7 @@ %vtableptr = bitcast i8* %obj to [1 x i8*]** %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr %vtablei8 = bitcast [1 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -31,9 +31,7 @@ ret i32 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [1 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [1 x i8*]* @vt2, i32 0} -!llvm.bitsets = !{!0} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/virtual-const-prop-begin.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/virtual-const-prop-begin.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/virtual-const-prop-begin.ll @@ -8,34 +8,34 @@ i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf1i32 to i8*) -], section "vt1sec" +], section "vt1sec", !type !0 ; CHECK: [[VT2DATA:@[^ ]*]] = private constant { [8 x i8], [3 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\02\02\00\00\00", [3 x i8*] [i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf2i32 to i8*)], [0 x i8] zeroinitializer }{{$}} @vt2 = constant [3 x i8*] [ i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf2i32 to i8*) -] +], !type !0 ; CHECK: [[VT3DATA:@[^ ]*]] = private constant { [8 x i8], [3 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\01\03\00\00\00", [3 x i8*] [i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf3i32 to i8*)], [0 x i8] zeroinitializer }{{$}} @vt3 = constant [3 x i8*] [ i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf3i32 to i8*) -] +], !type !0 ; CHECK: [[VT4DATA:@[^ ]*]] = private constant { [8 x i8], [3 x i8*], [0 x i8] } { [8 x i8] c"\00\00\00\02\04\00\00\00", [3 x i8*] [i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf4i32 to i8*)], [0 x i8] zeroinitializer }{{$}} @vt4 = constant [3 x i8*] [ i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf4i32 to i8*) -] +], !type !0 @vt5 = constant [3 x i8*] [ i8* bitcast (void ()* @__cxa_pure_virtual to i8*), i8* bitcast (void ()* @__cxa_pure_virtual to i8*), i8* bitcast (void ()* @__cxa_pure_virtual to i8*) -] +], !type !0 ; CHECK: @vt1 = alias [3 x i8*], getelementptr inbounds ({ [8 x i8], [3 x i8*], [0 x i8] }, { [8 x i8], [3 x i8*], [0 x i8] }* [[VT1DATA]], i32 0, i32 1) ; CHECK: @vt2 = alias [3 x i8*], getelementptr inbounds ({ [8 x i8], [3 x i8*], [0 x i8] }, { [8 x i8], [3 x i8*], [0 x i8] }* [[VT2DATA]], i32 0, i32 1) @@ -72,7 +72,7 @@ %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr ; CHECK: [[VT1:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8* %vtablei8 = bitcast [3 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -92,7 +92,7 @@ %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr ; CHECK: [[VT2:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8* %vtablei8 = bitcast [3 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 1 %fptr = load i8*, i8** %fptrptr @@ -112,7 +112,7 @@ %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr ; CHECK: [[VT3:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8* %vtablei8 = bitcast [3 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 2 %fptr = load i8*, i8** %fptrptr @@ -125,13 +125,8 @@ ret i32 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) declare void @__cxa_pure_virtual() -!0 = !{!"bitset", [3 x i8*]* @vt1, i32 0} -!1 = !{!"bitset", [3 x i8*]* @vt2, i32 0} -!2 = !{!"bitset", [3 x i8*]* @vt3, i32 0} -!3 = !{!"bitset", [3 x i8*]* @vt4, i32 0} -!4 = !{!"bitset", [3 x i8*]* @vt5, i32 0} -!llvm.bitsets = !{!0, !1, !2, !3, !4} +!0 = !{i32 0, !"typeid"} Index: llvm/trunk/test/Transforms/WholeProgramDevirt/virtual-const-prop-end.ll =================================================================== --- llvm/trunk/test/Transforms/WholeProgramDevirt/virtual-const-prop-end.ll +++ llvm/trunk/test/Transforms/WholeProgramDevirt/virtual-const-prop-end.ll @@ -9,14 +9,14 @@ i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf1i32 to i8*) -] +], !type !1 ; CHECK: [[VT2DATA:@[^ ]*]] = private constant { [0 x i8], [3 x i8*], [8 x i8] } { [0 x i8] zeroinitializer, [3 x i8*] [i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf2i32 to i8*)], [8 x i8] c"\02\00\00\00\02\00\00\00" } @vt2 = constant [3 x i8*] [ i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf2i32 to i8*) -] +], !type !0 ; CHECK: [[VT3DATA:@[^ ]*]] = private constant { [0 x i8], [4 x i8*], [8 x i8] } { [0 x i8] zeroinitializer, [4 x i8*] [i8* null, i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf3i32 to i8*)], [8 x i8] c"\03\00\00\00\01\00\00\00" } @vt3 = constant [4 x i8*] [ @@ -24,14 +24,14 @@ i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i32 (i8*)* @vf3i32 to i8*) -] +], !type !1 ; CHECK: [[VT4DATA:@[^ ]*]] = private constant { [0 x i8], [3 x i8*], [8 x i8] } { [0 x i8] zeroinitializer, [3 x i8*] [i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf4i32 to i8*)], [8 x i8] c"\04\00\00\00\02\00\00\00" } @vt4 = constant [3 x i8*] [ i8* bitcast (i1 (i8*)* @vf1i1 to i8*), i8* bitcast (i1 (i8*)* @vf0i1 to i8*), i8* bitcast (i32 (i8*)* @vf4i32 to i8*) -] +], !type !0 ; CHECK: @vt1 = alias [4 x i8*], getelementptr inbounds ({ [0 x i8], [4 x i8*], [8 x i8] }, { [0 x i8], [4 x i8*], [8 x i8] }* [[VT1DATA]], i32 0, i32 1) ; CHECK: @vt2 = alias [3 x i8*], getelementptr inbounds ({ [0 x i8], [3 x i8*], [8 x i8] }, { [0 x i8], [3 x i8*], [8 x i8] }* [[VT2DATA]], i32 0, i32 1) @@ -68,7 +68,7 @@ %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr ; CHECK: [[VT1:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8* %vtablei8 = bitcast [3 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 0 %fptr = load i8*, i8** %fptrptr @@ -88,7 +88,7 @@ %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr ; CHECK: [[VT2:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8* %vtablei8 = bitcast [3 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 1 %fptr = load i8*, i8** %fptrptr @@ -108,7 +108,7 @@ %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr ; CHECK: [[VT3:%[^ ]*]] = bitcast [3 x i8*]* {{.*}} to i8* %vtablei8 = bitcast [3 x i8*]* %vtable to i8* - %p = call i1 @llvm.bitset.test(i8* %vtablei8, metadata !"bitset") + %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid") call void @llvm.assume(i1 %p) %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 2 %fptr = load i8*, i8** %fptrptr @@ -121,11 +121,8 @@ ret i32 %result } -declare i1 @llvm.bitset.test(i8*, metadata) +declare i1 @llvm.type.test(i8*, metadata) declare void @llvm.assume(i1) -!0 = !{!"bitset", [4 x i8*]* @vt1, i32 8} -!1 = !{!"bitset", [3 x i8*]* @vt2, i32 0} -!2 = !{!"bitset", [4 x i8*]* @vt3, i32 8} -!3 = !{!"bitset", [3 x i8*]* @vt4, i32 0} -!llvm.bitsets = !{!0, !1, !2, !3} +!0 = !{i32 0, !"typeid"} +!1 = !{i32 8, !"typeid"} Index: llvm/trunk/test/tools/gold/X86/opt-level.ll =================================================================== --- llvm/trunk/test/tools/gold/X86/opt-level.ll +++ llvm/trunk/test/tools/gold/X86/opt-level.ll @@ -34,17 +34,18 @@ ret i32 %r } -define void @baz() { +define i1 @baz() { call void @foo() %c = call i32 @bar(i1 true) - ret void + %p = call i1 @llvm.type.test(i8* undef, metadata !"typeid1") + ret i1 %p } -@a = constant i32 1 +; CHECK-O0-NOT: !type +; CHECK-O1-NOT: !type +; CHECK-O2-NOT: !type +@a = constant i32 1, !type !0 -!0 = !{!"bitset1", i32* @a, i32 0} +!0 = !{i32 0, !"typeid1"} -; CHECK-O0-NOT: llvm.bitsets -; CHECK-O1-NOT: llvm.bitsets -; CHECK-O2-NOT: llvm.bitsets -!llvm.bitsets = !{ !0 } +declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone Index: llvm/trunk/unittests/Transforms/IPO/CMakeLists.txt =================================================================== --- llvm/trunk/unittests/Transforms/IPO/CMakeLists.txt +++ llvm/trunk/unittests/Transforms/IPO/CMakeLists.txt @@ -5,6 +5,6 @@ ) add_llvm_unittest(IPOTests - LowerBitSets.cpp + LowerTypeTests.cpp WholeProgramDevirt.cpp ) Index: llvm/trunk/unittests/Transforms/IPO/LowerBitSets.cpp =================================================================== --- llvm/trunk/unittests/Transforms/IPO/LowerBitSets.cpp +++ llvm/trunk/unittests/Transforms/IPO/LowerBitSets.cpp @@ -1,156 +0,0 @@ -//===- LowerBitSets.cpp - Unit tests for bitset lowering ------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/IPO/LowerBitSets.h" -#include "gtest/gtest.h" - -using namespace llvm; -using namespace lowerbitsets; - -TEST(LowerBitSets, BitSetBuilder) { - struct { - std::vector Offsets; - std::set Bits; - uint64_t ByteOffset; - uint64_t BitSize; - unsigned AlignLog2; - bool IsSingleOffset; - bool IsAllOnes; - } BSBTests[] = { - {{}, std::set{}, 0, 1, 0, false, false}, - {{0}, {0}, 0, 1, 0, true, true}, - {{4}, {0}, 4, 1, 0, true, true}, - {{37}, {0}, 37, 1, 0, true, true}, - {{0, 1}, {0, 1}, 0, 2, 0, false, true}, - {{0, 4}, {0, 1}, 0, 2, 2, false, true}, - {{0, uint64_t(1) << 33}, {0, 1}, 0, 2, 33, false, true}, - {{3, 7}, {0, 1}, 3, 2, 2, false, true}, - {{0, 1, 7}, {0, 1, 7}, 0, 8, 0, false, false}, - {{0, 2, 14}, {0, 1, 7}, 0, 8, 1, false, false}, - {{0, 1, 8}, {0, 1, 8}, 0, 9, 0, false, false}, - {{0, 2, 16}, {0, 1, 8}, 0, 9, 1, false, false}, - {{0, 1, 2, 3, 4, 5, 6, 7}, - {0, 1, 2, 3, 4, 5, 6, 7}, - 0, - 8, - 0, - false, - true}, - {{0, 1, 2, 3, 4, 5, 6, 7, 8}, - {0, 1, 2, 3, 4, 5, 6, 7, 8}, - 0, - 9, - 0, - false, - true}, - }; - - for (auto &&T : BSBTests) { - BitSetBuilder BSB; - for (auto Offset : T.Offsets) - BSB.addOffset(Offset); - - BitSetInfo BSI = BSB.build(); - - EXPECT_EQ(T.Bits, BSI.Bits); - EXPECT_EQ(T.ByteOffset, BSI.ByteOffset); - EXPECT_EQ(T.BitSize, BSI.BitSize); - EXPECT_EQ(T.AlignLog2, BSI.AlignLog2); - EXPECT_EQ(T.IsSingleOffset, BSI.isSingleOffset()); - EXPECT_EQ(T.IsAllOnes, BSI.isAllOnes()); - - for (auto Offset : T.Offsets) - EXPECT_TRUE(BSI.containsGlobalOffset(Offset)); - - auto I = T.Offsets.begin(); - for (uint64_t NonOffset = 0; NonOffset != 256; ++NonOffset) { - if (I != T.Offsets.end() && *I == NonOffset) { - ++I; - continue; - } - - EXPECT_FALSE(BSI.containsGlobalOffset(NonOffset)); - } - } -} - -TEST(LowerBitSets, GlobalLayoutBuilder) { - struct { - uint64_t NumObjects; - std::vector> Fragments; - std::vector WantLayout; - } GLBTests[] = { - {0, {}, {}}, - {4, {{0, 1}, {2, 3}}, {0, 1, 2, 3}}, - {3, {{0, 1}, {1, 2}}, {0, 1, 2}}, - {4, {{0, 1}, {1, 2}, {2, 3}}, {0, 1, 2, 3}}, - {4, {{0, 1}, {2, 3}, {1, 2}}, {0, 1, 2, 3}}, - {6, {{2, 5}, {0, 1, 2, 3, 4, 5}}, {0, 1, 2, 5, 3, 4}}, - }; - - for (auto &&T : GLBTests) { - GlobalLayoutBuilder GLB(T.NumObjects); - for (auto &&F : T.Fragments) - GLB.addFragment(F); - - std::vector ComputedLayout; - for (auto &&F : GLB.Fragments) - ComputedLayout.insert(ComputedLayout.end(), F.begin(), F.end()); - - EXPECT_EQ(T.WantLayout, ComputedLayout); - } -} - -TEST(LowerBitSets, ByteArrayBuilder) { - struct BABAlloc { - std::set Bits; - uint64_t BitSize; - uint64_t WantByteOffset; - uint8_t WantMask; - }; - - struct { - std::vector Allocs; - std::vector WantBytes; - } BABTests[] = { - {{{{0}, 1, 0, 1}, {{0}, 1, 0, 2}}, {3}}, - {{{{0}, 16, 0, 1}, - {{1}, 15, 0, 2}, - {{2}, 14, 0, 4}, - {{3}, 13, 0, 8}, - {{4}, 12, 0, 0x10}, - {{5}, 11, 0, 0x20}, - {{6}, 10, 0, 0x40}, - {{7}, 9, 0, 0x80}, - {{0}, 7, 9, 0x80}, - {{0}, 6, 10, 0x40}, - {{0}, 5, 11, 0x20}, - {{0}, 4, 12, 0x10}, - {{0}, 3, 13, 8}, - {{0}, 2, 14, 4}, - {{0}, 1, 15, 2}}, - {1, 2, 4, 8, 0x10, 0x20, 0x40, 0x80, 0, 0x80, 0x40, 0x20, 0x10, 8, 4, - 2}}, - }; - - for (auto &&T : BABTests) { - ByteArrayBuilder BABuilder; - - for (auto &&A : T.Allocs) { - uint64_t GotByteOffset; - uint8_t GotMask; - - BABuilder.allocate(A.Bits, A.BitSize, GotByteOffset, GotMask); - EXPECT_EQ(A.WantByteOffset, GotByteOffset); - EXPECT_EQ(A.WantMask, GotMask); - } - - EXPECT_EQ(T.WantBytes, BABuilder.Bytes); - } -} Index: llvm/trunk/unittests/Transforms/IPO/LowerTypeTests.cpp =================================================================== --- llvm/trunk/unittests/Transforms/IPO/LowerTypeTests.cpp +++ llvm/trunk/unittests/Transforms/IPO/LowerTypeTests.cpp @@ -0,0 +1,156 @@ +//===- LowerTypeTests.cpp - Unit tests for type test lowering -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/IPO/LowerTypeTests.h" +#include "gtest/gtest.h" + +using namespace llvm; +using namespace lowertypetests; + +TEST(LowerTypeTests, BitSetBuilder) { + struct { + std::vector Offsets; + std::set Bits; + uint64_t ByteOffset; + uint64_t BitSize; + unsigned AlignLog2; + bool IsSingleOffset; + bool IsAllOnes; + } BSBTests[] = { + {{}, std::set{}, 0, 1, 0, false, false}, + {{0}, {0}, 0, 1, 0, true, true}, + {{4}, {0}, 4, 1, 0, true, true}, + {{37}, {0}, 37, 1, 0, true, true}, + {{0, 1}, {0, 1}, 0, 2, 0, false, true}, + {{0, 4}, {0, 1}, 0, 2, 2, false, true}, + {{0, uint64_t(1) << 33}, {0, 1}, 0, 2, 33, false, true}, + {{3, 7}, {0, 1}, 3, 2, 2, false, true}, + {{0, 1, 7}, {0, 1, 7}, 0, 8, 0, false, false}, + {{0, 2, 14}, {0, 1, 7}, 0, 8, 1, false, false}, + {{0, 1, 8}, {0, 1, 8}, 0, 9, 0, false, false}, + {{0, 2, 16}, {0, 1, 8}, 0, 9, 1, false, false}, + {{0, 1, 2, 3, 4, 5, 6, 7}, + {0, 1, 2, 3, 4, 5, 6, 7}, + 0, + 8, + 0, + false, + true}, + {{0, 1, 2, 3, 4, 5, 6, 7, 8}, + {0, 1, 2, 3, 4, 5, 6, 7, 8}, + 0, + 9, + 0, + false, + true}, + }; + + for (auto &&T : BSBTests) { + BitSetBuilder BSB; + for (auto Offset : T.Offsets) + BSB.addOffset(Offset); + + BitSetInfo BSI = BSB.build(); + + EXPECT_EQ(T.Bits, BSI.Bits); + EXPECT_EQ(T.ByteOffset, BSI.ByteOffset); + EXPECT_EQ(T.BitSize, BSI.BitSize); + EXPECT_EQ(T.AlignLog2, BSI.AlignLog2); + EXPECT_EQ(T.IsSingleOffset, BSI.isSingleOffset()); + EXPECT_EQ(T.IsAllOnes, BSI.isAllOnes()); + + for (auto Offset : T.Offsets) + EXPECT_TRUE(BSI.containsGlobalOffset(Offset)); + + auto I = T.Offsets.begin(); + for (uint64_t NonOffset = 0; NonOffset != 256; ++NonOffset) { + if (I != T.Offsets.end() && *I == NonOffset) { + ++I; + continue; + } + + EXPECT_FALSE(BSI.containsGlobalOffset(NonOffset)); + } + } +} + +TEST(LowerTypeTests, GlobalLayoutBuilder) { + struct { + uint64_t NumObjects; + std::vector> Fragments; + std::vector WantLayout; + } GLBTests[] = { + {0, {}, {}}, + {4, {{0, 1}, {2, 3}}, {0, 1, 2, 3}}, + {3, {{0, 1}, {1, 2}}, {0, 1, 2}}, + {4, {{0, 1}, {1, 2}, {2, 3}}, {0, 1, 2, 3}}, + {4, {{0, 1}, {2, 3}, {1, 2}}, {0, 1, 2, 3}}, + {6, {{2, 5}, {0, 1, 2, 3, 4, 5}}, {0, 1, 2, 5, 3, 4}}, + }; + + for (auto &&T : GLBTests) { + GlobalLayoutBuilder GLB(T.NumObjects); + for (auto &&F : T.Fragments) + GLB.addFragment(F); + + std::vector ComputedLayout; + for (auto &&F : GLB.Fragments) + ComputedLayout.insert(ComputedLayout.end(), F.begin(), F.end()); + + EXPECT_EQ(T.WantLayout, ComputedLayout); + } +} + +TEST(LowerTypeTests, ByteArrayBuilder) { + struct BABAlloc { + std::set Bits; + uint64_t BitSize; + uint64_t WantByteOffset; + uint8_t WantMask; + }; + + struct { + std::vector Allocs; + std::vector WantBytes; + } BABTests[] = { + {{{{0}, 1, 0, 1}, {{0}, 1, 0, 2}}, {3}}, + {{{{0}, 16, 0, 1}, + {{1}, 15, 0, 2}, + {{2}, 14, 0, 4}, + {{3}, 13, 0, 8}, + {{4}, 12, 0, 0x10}, + {{5}, 11, 0, 0x20}, + {{6}, 10, 0, 0x40}, + {{7}, 9, 0, 0x80}, + {{0}, 7, 9, 0x80}, + {{0}, 6, 10, 0x40}, + {{0}, 5, 11, 0x20}, + {{0}, 4, 12, 0x10}, + {{0}, 3, 13, 8}, + {{0}, 2, 14, 4}, + {{0}, 1, 15, 2}}, + {1, 2, 4, 8, 0x10, 0x20, 0x40, 0x80, 0, 0x80, 0x40, 0x20, 0x10, 8, 4, + 2}}, + }; + + for (auto &&T : BABTests) { + ByteArrayBuilder BABuilder; + + for (auto &&A : T.Allocs) { + uint64_t GotByteOffset; + uint8_t GotMask; + + BABuilder.allocate(A.Bits, A.BitSize, GotByteOffset, GotMask); + EXPECT_EQ(A.WantByteOffset, GotByteOffset); + EXPECT_EQ(A.WantMask, GotMask); + } + + EXPECT_EQ(T.WantBytes, BABuilder.Bytes); + } +} Index: llvm/trunk/unittests/Transforms/IPO/WholeProgramDevirt.cpp =================================================================== --- llvm/trunk/unittests/Transforms/IPO/WholeProgramDevirt.cpp +++ llvm/trunk/unittests/Transforms/IPO/WholeProgramDevirt.cpp @@ -25,11 +25,11 @@ VT2.Before.BytesUsed = {1 << 1}; VT2.After.BytesUsed = {1 << 0}; - BitSetInfo BS1{&VT1, 0}; - BitSetInfo BS2{&VT2, 0}; + TypeMemberInfo TM1{&VT1, 0}; + TypeMemberInfo TM2{&VT2, 0}; VirtualCallTarget Targets[] = { - {&BS1, /*IsBigEndian=*/false}, - {&BS2, /*IsBigEndian=*/false}, + {&TM1, /*IsBigEndian=*/false}, + {&TM2, /*IsBigEndian=*/false}, }; EXPECT_EQ(2ull, findLowestOffset(Targets, /*IsAfter=*/false, 1)); @@ -38,15 +38,15 @@ EXPECT_EQ(8ull, findLowestOffset(Targets, /*IsAfter=*/false, 8)); EXPECT_EQ(72ull, findLowestOffset(Targets, /*IsAfter=*/true, 8)); - BS1.Offset = 4; + TM1.Offset = 4; EXPECT_EQ(33ull, findLowestOffset(Targets, /*IsAfter=*/false, 1)); EXPECT_EQ(65ull, findLowestOffset(Targets, /*IsAfter=*/true, 1)); EXPECT_EQ(40ull, findLowestOffset(Targets, /*IsAfter=*/false, 8)); EXPECT_EQ(72ull, findLowestOffset(Targets, /*IsAfter=*/true, 8)); - BS1.Offset = 8; - BS2.Offset = 8; + TM1.Offset = 8; + TM2.Offset = 8; EXPECT_EQ(66ull, findLowestOffset(Targets, /*IsAfter=*/false, 1)); EXPECT_EQ(2ull, findLowestOffset(Targets, /*IsAfter=*/true, 1)); @@ -66,15 +66,15 @@ VTableBits VT2; VT2.ObjectSize = 8; - BitSetInfo BS1{&VT1, 0}; - BitSetInfo BS2{&VT2, 0}; + TypeMemberInfo TM1{&VT1, 0}; + TypeMemberInfo TM2{&VT2, 0}; VirtualCallTarget Targets[] = { - {&BS1, /*IsBigEndian=*/false}, - {&BS2, /*IsBigEndian=*/false}, + {&TM1, /*IsBigEndian=*/false}, + {&TM2, /*IsBigEndian=*/false}, }; - BS1.Offset = 4; - BS2.Offset = 4; + TM1.Offset = 4; + TM2.Offset = 4; int64_t OffsetByte; uint64_t OffsetBit;