Svadev mailing list

[Andreas Wilhelm <andreas.wilhelm AT gmx.com>]

Hello John,

On Mar 14, 2013, at 10:24 PM, John Criswell <criswell AT illinois.edu> wrote:

On 3/12/13 1:28 PM, Andreas Wilhelm wrote:

Hi John,

thank you, I integrated the DSNodeEquivs pass into my application.

Unfortunately most (all but one) store instructions have a pointer operand which is said to be 1. inomplete, 2. external and 3. unkonwn. I ran the pass after some other  optimization passes.

For example look at the push() function of following code snippet:

struct Node {

  int value;

  struct Node* next;

  Node( int _value ) : value(_value), next(NULL) {}

};

class ThreadSafeStack {

  struct Node* top;

  pthread_mutex_t mutex;

  unsigned stack_size;

public:

  ThreadSafeStack( ) : top(NULL), stack_size(0) {

    pthread_mutex_init( &mutex, NULL );

  }

  int push( int value ) {

    int tmp;

    pthread_mutex_lock ( &mutex );

      struct Node *node = new struct Node( value );

      node->next = top;

      top = node;

      stack_size++;

      tmp = stack_size;

    pthread_mutex_unlock ( &mutex );

    return tmp;

  }

Here is the produced ir code:

define internal fastcc i32 @_ZN4lock15ThreadSafeStack4pushEi(%"class.lock::ThreadSafeStack"* nocapture %this, i32 %value) uwtable noinline align 2 {

entry:

  %mutex = getelementptr inbounds %"class.lock::ThreadSafeStack"* %this, i64 0, i32 1, !dbg !6879

  tail call fastcc void @pthread_mutex_lock(%union.pthread_mutex_t* %mutex) nounwind, !dbg !6879

  %call3 = tail call noalias i8* @_Znwm(i64 16), !dbg !6881

  %0 = bitcast i8* %call3 to %"struct.lock::Node"*, !dbg !6881

  %value.i.i = bitcast i8* %call3 to i32*, !dbg !6882

  store i32 %value, i32* %value.i.i, align 4, !dbg !6882

  call void @klee_thread_preempt(i32 0)

  %next.i.i = getelementptr inbounds i8* %call3, i64 8, !dbg !6882

  %1 = bitcast i8* %next.i.i to %"struct.lock::Node"**, !dbg !6882

  store %"struct.lock::Node"* null, %"struct.lock::Node"** %1, align 8, !dbg !6882

  call void @klee_thread_preempt(i32 0)

  %top = getelementptr inbounds %"class.lock::ThreadSafeStack"* %this, i64 0, i32 0, !dbg !6884

  %2 = load %"struct.lock::Node"** %top, align 8, !dbg !6884

  store %"struct.lock::Node"* %2, %"struct.lock::Node"** %1, align 8, !dbg !6884

  call void @klee_thread_preempt(i32 0)

Every store instruction has an operand which is 1. inomplete, 2. external and 3. unkonwn. So my pass inserts the @klee_thread_preempt calls after each store.

I'm now wondering whether this is okay (DSA is not able to find it) or if there's a bug anywhere?

It depends on what the rest of the function does, but as far as I can see:

1) It may be correct that  %2 points to an incomplete DSNode.  It is loaded from %this, which is a parameter to the function.  It might become complete in the TD pass if you're running within libLTO, but there's a known issue with DSA where it sometimes cannot determine that the this pointer of C++ classes is complete.

2) The pointers in the other stores look like they should be complete because they are derived from %call3 (which is a memory allocation).  It shouldn't be incomplete, external, or unknown.

Just to make sure we're on the same page, are you getting the DSNodes for these pointers from the TDDataStructures pass?

I get the DSNodes from the DSNodeEquivs pass (which uses TDDataStructures). I played with the pass execution order, now I consider 4 store instructions with following results:

  store i32 %value, i32* %value.i.i, align 4, !dbg !6341: incomplete(1) external(0) unknown(1)

  store %"struct.lockfree::Node"* null, %"struct.lockfree::Node"** %1, align 8, !dbg !6341: incomplete(1) external(0) unknown(1)

  store %"struct.lockfree::Node"* %2, %"struct.lockfree::Node"** %1, align 8, !dbg !6343: incomplete(1) external(0) unknown(1)

  store %"struct.lockfree::Node"* %2, %"struct.lockfree::Node"** %top, align 8, !dbg !6341: incomplete(1) external(0) unknown(1)

As far as I can see, the first instruction shouldn't be incomplete nor unknown.

I'm assuming the provided LLVM assembly is a snippet.  Can you provide a reduced but complete bitcode file?

Of course, see out.bc in the attachments.

Best regards,

Andreas

Attachment: out.bc
Description: Binary data

-- John T.

Best regards,

Andreas

On Mar 11, 2013, at 7:44 PM, John Criswell <criswell AT illinois.edu> wrote:

On 3/11/13 11:22 AM, Andreas Wilhelm wrote:

Hello,

I'm working on a thread-safety-analyzer (based on LLVM 3.1/klee/Cloud9). Therefore I need a way to identify store instructions in function X, that modify memory locations which are read by a set of other functions Y,Z... At the moment I'm doing the following:

I assume what you're doing is looking for a store in the current function and then examining other functions to see if they access the same memory object as the store.  Is this correct?

If so, then there are several issues with your code:

  EQTDDataStructures &DS = getAnalysis<EQTDDataStructures>();

I would use TDDataStructures so that you can use the DSNodeEquivs pass more easily.

  for (inst_iterator iIt = inst_begin(*funcA); iIt != inst_end(*funcA); ++iIt) {

    if (isa<StoreInst>( *iIt )) {

      StoreInst &inst = cast<StoreInst>( *iIt );

As an FYI, you can replace the above with if (StoreInst * SI = dyn_cast<StoreInst>(*iIt)) instead of using isa<> and cast<>.

      bool ref = false;

      for (fSetIterator fItB = set.begin(); fItB != set.end() && !ref; ++fItB) {

        if (fItB->second == funcA)

          continue;

        DSGraph *graph = DS.getDSGraph( *fItB->second );

        if (graph->hasNodeForValue( inst.getValueOperand() )) {

This is incorrect.  What you're doing above is asking whether another function has a DSNode for the specific SSA virtual register belonging to the store instruction in the original function.  It is possible (and likely) that the other functions have different SSA virtual registers that point to the same abstract memory location.

What you need to do is iterate over the instructions in the other functions, and for each instruction, see if any of its operands have DSNodes that represent the same abstract memory location as the pointer used in the StoreInst of the original function.  The logic should look something like this:

Value * PtrOperand = inst.getPointerOperand();
DSNode * D = DSNode of inst.getPointerOperand();
for (all instructions in other functions) {
    for (all operands of the instruction) {
        if (operand has DSNode D2) {
            if (DSNodes D or D2 are marked Incomplete, Unknown, or External)
                assume DSNodes D and D2 represent same memory;
            else
                Determine if DSNodes D and D2 refer to same memory location
        }
    }
}


Now, the only question left is how to determine whether two DSNodes from two different functions refer to the same abstract memory location?  The answer is to use the DSNodeEquivs pass.

What would be the best / easiest way to solve my problem?

The easiest way to solve this problem is to use the DSNodeEquiv pass.  This pass uses the TDDataStructures graphs and computes equivalence classes for DSNodes that refer to the same abstract memory location in different functions.  You basically call DSNodeEquivs::getMemberForValue() on two SSA virtual registers that you want to know the aliasing behavior of; if getMemberForValue() returns the same DSNode for both values, then they can point to the same abstract memory location.

-- John T.

Kind regards,

Andreas

_______________________________________________
svadev mailing list
svadev AT cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/svadev