Cloning function for accurate pta

[hotpeperoncino]

At first callsite of MUSTALIAS, PSNodes say that p points to "q" and "y" because of no function cloning so pta cannot distingulish each other.

void foo(int**a, int*b){

        *a = b;

}


void main(){

        int *p,q,*x,y;
        foo(&p,&q);
    MUSTALIAS(p,&q);
        foo(&x,&y);
    MUSTALIAS(x,&y);
    NOALIAS(x,&q);
    NOALIAS(p,&y);

        *p = 100;

}

[mchalupa]

Hi,

yes, that's correct. The pointer analysis in dg does not support context-sensitivity. Should I understand this as a feature request? However, at this moment I do not have much time that I could devote to this, so feel free to extend dg as you wish! :)

[hotpeperoncino]

I see. I understand your situation.

[hotpeperoncino]

If building subgraph always, do you think it can emulate cloning function ? In LLVMDependenchGraph.cpp,

LLVMDependenceGraph *
LLVMDependenceGraph::buildSubgraph(LLVMNode *node, llvm::Function *callFunc)
{
    using namespace llvm;

    LLVMBBlock *BB;

    // if we don't have this subgraph constructed, construct it
    // else just add call edge
    LLVMDependenceGraph *&subgraph = constructedFunctions[callFunc];
    if (!subgraph) {  <-- removing this condition to turn it on always.

[mchalupa]

I would not do that for at least two reasons:

1. without this condition the graph's size can grow exponentially
2. with recursive functions the graph building procedure would not halt

Moreover, doing it here would not change anything for the pointer analysis. To achieve context-sensitivity in PTA, you would need to clone the subgraphs in PointerSubgraph (https://github.com/mchalupa/dg/blob/master/src/llvm/analysis/PointsTo/PointerSubgraph.cpp#L612), but even then you need to solve the two issues mentioned above. You would also need to fix somehow the mapping from llvm values to PSNode's, because at this moment there is not information about the call-site.

[hotpeperoncino]

Thank you for your comment. how about using "CloneFunction" provided by llvm ? is it better idea ? I'd like to know which is easier implementation -- cloning information in dg or cloning function at llvm side.

[mchalupa]

Cloning functions at LLVM side is definitely easier. You can also use opt -inline

[hotpeperoncino]

Thanks. I'd investigate further at the point of view.

[hotpeperoncino]

I tried to use "opt -inline" in order to estimate result of context-sensitivety support. As result, i could get best score in AAs which I've looked into.

[mchalupa]

Great. I'm glad to hear that. That sounds like it could be worth to look into adding some sort of (partial) context sensitivity to dg's pointer analysis :)

[mchalupa]

See also #86