search for: bitsets

Hi all, I would like to propose a mechanism that allows IR modules to co-operatively build a pointer set corresponding to addresses within a given set of globals. The specific use case I have in mind is to provide a mechanism for a C++ program to efficiently verify (at each call site) that a vtable pointer is in the set of valid vtable pointers for the class or its derived classes. One way of

...an identifier for the bitset (in this case, the mangled name of the class) and a pointer into a global (in this case, a valid vtable pointer). For example, this class hierarchy: class A { virtual void f(); }; class B : A { virtual void f(); }; class C : A { virtual void f(); }; would have these bitsets: !llvm.bitsets = !{!0, !1, !2, !3, !4} !0 = !{!"1A", i8* getelementptr inbounds ([3 x i8*]* @_ZTV1A, i32 0, i32 2)} !1 = !{!"1A", i8* getelementptr inbounds ([3 x i8*]* @_ZTV1B, i32 0, i32 2)} !2 = !{!"1A", i8* getelementptr inbounds ([3 x i8*]* @_ZTV1C, i32 0, i32 2...

I would start from using module-level metadata. An IR extension might be a good idea once we show that - the proposed indirect call protection mechanism is efficient and useful, and - there are other use cases for the IR extension. --kcc On Wed, Jan 28, 2015 at 2:57 AM, Sean Silva <chisophugis at gmail.com> wrote: > Is there any way to accomplish this that doesn't require

...e, the mangled name of the class) and a pointer into a global > (in this case, a valid vtable pointer). > > For example, this class hierarchy: > > class A { virtual void f(); }; > class B : A { virtual void f(); }; > class C : A { virtual void f(); }; > > would have these bitsets: > > !llvm.bitsets = !{!0, !1, !2, !3, !4} > > !0 = !{!"1A", i8* getelementptr inbounds ([3 x i8*]* @_ZTV1A, i32 0, i32 > 2)} > !1 = !{!"1A", i8* getelementptr inbounds ([3 x i8*]* @_ZTV1B, i32 0, i32 > 2)} > !2 = !{!"1A", i8* getelementptr inbo...

So, bitset would be a property that means : globals with the same name will append on a string of bits in the order in which they appear, and it's the job of the front end to make sure the correct order is followed in every unit, so that linking does the right job in every corner case? Could that be used for efficient global boolean flags, like LLVM's options? Even if you don't need

There are two 64-bit bitmasks maintained in AttributeImpl.h<https://sdocc.itg.ti.com/ui#file:review=11893/version=393846>: - AvailableFunctionAttrs is part of the AttributeListImpl class, and - AvailableAttrs is part of the AttributeSetNode class Both of these assume that the number of available enum attributes is limited to 64. In fact, a static_assert in

...could use as a basis. Therefore I'd like to ask two questions: 1) logical vectors: Bit storage (small) and capable of bit operations? The Java application relies on BitSet(s) for efficiency reasons. Arrays of logical values cost far too much memory (in the 2nd level heap etc.) while chunks of BitSets easily fit into the first processor cache. Moreover the Bit operations or, xor, and, andnot, cardinality, clone, flip, equals, intersects are much faster done for BitSets than equivalent functions written for logical arrays. Is there any equivalent for BitSet in R? The vector type "logical&quo...

...B { virtual void f(), g(); }; class E : B, C { virtual void g(), h(); }; vtables: A = { &A::rtti, &A::f }; B = { &B::rtti, &B::g }; C = { &C::rtti, &C::h }; D = { &D::rtti, &D::f, &D::rtti, &D::g }; E = { &E::rtti, &E::g, &E::rtti, &E::h }; bitsets (assuming layout A,B,C,D,E): A = { 0,1,0,0,0,0,0,1,0,0,0,0,0,0 } B = { 0,0,0,1,0,0,0,0,0,1,0,1,0,0 } C = { 0,0,0,0,0,1,0,0,0,0,0,1,0,1 } D = { 0,0,0,0,0,0,0,1,0,0,0,0,0,0 } E = { 0,0,0,0,0,0,0,0,0,0,0,1,0,0 } Note that because of the existence of class C, we must leave a gap in the bitset for A b...

Hi Peter, Please forgive if this is an obvious question, but how reasonable is it for this approach to work when not all translation units are available to be rebuilt with the new information? I'm very interested in what you're proposing here. Jim Sent from my iPhone > On Jan 27, 2015, at 1:07 PM, Peter Collingbourne <peter at pcc.me.uk> wrote: > > Hi all, > > I

Trying to summarize all opinions expressed here: Peter is proposing an initial implementation that would only work with LTO. Folks seem put off by this implementation affecting IR without having proven itself, and having shortcomings (as Jim pointed out). Kostya proposed going through metadata (and Chris kind of did too by mentioning tbaa), but Peter points out that this will make the

...most likely works without any other optimizer changes, because I have a work-in-progress patch that implements the Clang side of this, and have successfully applied it to a large C++ codebase and found real bugs in that codebase.) Regarding codegen, I haven't implemented support in codegen for bitsets yet, the intrinsic is completely handled by the pass. I can't imagine the changes being very intrusive though. We can easily add a check that no bitset stuff makes it through to codegen for the moment. > The fact that this affects semantics and will only work with LTO and not native linkers...

On 29 Jan 2015 11:36, "Sean Silva" <chisophugis at gmail.com> wrote: > > > > On Thu, Jan 29, 2015 at 12:53 AM, Renato Golin <renato.golin at linaro.org> wrote: >> >> So, bitset would be a property that means : globals with the same name will append on a string of bits in the order in which they appear, and it's the job of the front end to make sure

...er into a global > > (in this case, a valid vtable pointer). > > > > For example, this class hierarchy: > > > > class A { virtual void f(); }; > > class B : A { virtual void f(); }; > > class C : A { virtual void f(); }; > > > > would have these bitsets: > > > > !llvm.bitsets = !{!0, !1, !2, !3, !4} > > > > !0 = !{!"1A", i8* getelementptr inbounds ([3 x i8*]* @_ZTV1A, i32 0, i32 > > 2)} > > !1 = !{!"1A", i8* getelementptr inbounds ([3 x i8*]* @_ZTV1B, i32 0, i32 > > 2)} > > !2 = !...

On Thu, Jan 29, 2015 at 02:22:48PM -0800, Peter Collingbourne wrote: > I've been working on a patch that implements the bitset attribute and bitset > lowering pass. I'll see if I can send it out later today. http://reviews.llvm.org/D7288 Thanks, -- Peter

...s in the following way: 1. Rename the metadata to "type metadata". This new name reflects how the metadata is currently being used (i.e. to represent type information for CFI and vtable opt). 2. Attach metadata directly to the globals that it pertains to, rather than using the "llvm.bitsets" global metadata node as we are doing now. This would be done using the newly introduced capability to attach metadata to global variables (r271348 and r271358). Passes which manipulate globals can easily copy metadata between globals with the GlobalObject::copyMetadata function, which would b...

...pop %rbx 255a8fa: c3 retq ==LLVM IR-level design== Given a class name, how can we determine the closed set of derived classes and possible function pointers for a call site? As it turns out the IR already has a way of expressing this information: bitsets [1], which are already being used to implement CFI. We can encode the information for devirtualization by combining the @llvm.bitset.test and @llvm.assume intrinsics. %vtable = load i8**, i8*** %obj %p = call i1 @llvm.bitset.test(%vtable, “Base”) call void @llvm.assume(i1 %p) ; %vtable is assumed...

> On Jan 29, 2015, at 6:50 PM, Peter Collingbourne <peter at pcc.me.uk> wrote: > > On Thu, Jan 29, 2015 at 02:22:48PM -0800, Peter Collingbourne wrote: >> I've been working on a patch that implements the bitset attribute and bitset >> lowering pass. I'll see if I can send it out later today. > > http://reviews.llvm.org/D7288

On Tue, Feb 03, 2015 at 04:03:45PM -0800, Sean Silva wrote: > One other thing: if this can be used for control-flow integrity, I assume > it has to have good knowledge of the available indirect call targets. Could > we also use this information for devirtualization? I would expect so. If a bitset contains only one element, we should be able to teach the lowering pass to simply test that

...} b.union(a) equal to {MD1} Our flow-sensitive method is divided into 2 step: 1. Iterative solve flow-equation to compute POINT-TO for each stmt. 2. According to POINT-TO info, compute MayDef BITSET and MayUse BITSET for each stmt. So, I have an question, after step 2 each stmt should own two BITSETs to record MayDef and MayUse. Is that right or necessary?  How to describe both MayDef, MayUse info if just have a single BITSET in each stmt? --- 13年3月21日，周四, Daniel Berlin <dberlin at dberlin.org> 写道： > 发件人: Daniel Berlin <dberlin at dberlin.org> > 主题: Re: [LLVMdev] How to des...

...r flow-sensitive method is divided into 2 step: > 1. Iterative solve flow-equation to compute POINT-TO for each stmt. > 2. According to POINT-TO info, compute MayDef BITSET and MayUse BITSET for each stmt. > > So, I have an question, after step 2 each stmt should own two BITSETs to record MayDef and MayUse. > Is that right or necessary? It's fine, it's not strictly necessary, but it's not bad or harmful. > How to describe both MayDef, MayUse info if just have a single BITSET in each stmt? Cut the universe in half. Assuming 64 bit ids: bits 1-922337203...