Svadev mailing list

[John Criswell <criswell AT illinois.edu>]

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