3
$\begingroup$

I'm new to world of static analysis and am trying to build a new analysis of C programs for llvm compiler.

I've started with the build of the graph of the constraints of the program: The edges represent the flow of data through the program (according to the statements or function calls) and the nodes the run-time memory locations.

I'm wondering if for the labeling of the constraints I do need a symbol table with all the constraints and their labels. I found out that we can build a CFG on top of the LLVM by only parsing the LLVM IR.

for example, we could just have:

//Build list nodes without successors.
for (Function::iterator e = F.end() ; e != BB ; ++BB) {
    BI = BB->begin();
    for(BasicBlock::iterator BE = BB->end(); BI != BE; ++BI){
        Instruction * instruction = dyn_cast<Instruction>(BI);
        StaticAnalysis::ListNode* node = new StaticAnalysis::ListNode(counter++);
        node->inst = instruction;
        helper.insert(pair<Instruction*,StaticAnalysis::ListNode*>(instruction,node));
        CFGNodes.push_back(node);
    }
}

So, my question is: Would this be possible also for a flow graph? Or a symbol table is needed to construct one?

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! 1. "building the graph" - what graph? I think there's some context missing. What are you trying to achieve, and what algorithm are you using to do it? 2. "add the nodes straight on the graph" - sorry, I don't know what that means. 3. Also, we generally want you to ask one question per question. Three different questions is a bit much. And your 3rd question is far too broad for this site. Finally, we want you to do research before asking here and tell us in the question what research you've done. So, you might want to edit your question to address all of these points. $\endgroup$ – D.W. Apr 28 '15 at 8:51
  • $\begingroup$ @D.W. Thanks for the comment. Please, check updated post :) $\endgroup$ – eternalStudent Apr 29 '15 at 13:34
  • $\begingroup$ Please make clearer how this is not LLVM tool support (which is offtopic here) but a conceptual computer science question. $\endgroup$ – Raphael Apr 29 '15 at 15:08
  • $\begingroup$ @Raphael. It doesn't depend on LLVM. My question is general: do we have the need of a symbol table when building a label flow graph? Or we can just parse the program ? (I referred to LLVM in order to make clearer what I'm looking for) $\endgroup$ – eternalStudent Apr 29 '15 at 15:17
1
$\begingroup$

You want to build a graph where the vertices are the set of runtime locations in memory. Unfortunately, this isn't possible. The set of runtime locations can be an unbounded set.

For instance, consider code that creates a linked list to hold $n$ data items provided on the input; the number of memory locations is at least $n$, so if the data items are provided on the input, there is no upper bound on the number of memory locations. Or, consider code like

while (...) {
    char *p = malloc(..);
    ... do something with p ...
    free(p);
}

Each call to malloc() creates a new memory location, so the number of runtime memory locations is at least the number of iterations of the loop. There may be no fixed upper bound on the possible number of iterations of the loop.

Different static analysis techniques deal with this in different ways:

  • Data flow analysis typically deals with this by ignoring everything in the heap, and only trying to reason about local variables. In this way, you obtain a finite graph.

  • Points-to analysis deals with this using abstraction. It builds a points-to graph, where each node in the graph corresponds to a potentially unbounded number of runtime memory locations. At each node in the graph, we record facts that are known to be true for all of the runtime memory locations that correspond to that node. For instance, we might have one node per malloc() call site. In other words, we might have a single node for all runtime memory locations that are allocated by any of the calls to malloc() on line 79 (the first call to malloc() on that line, the second call to malloc() on that line, etc.; they're all merged into a single node).

You might want to spend some time reading up on how data flow analysis and points-to analysis work.

More generally, I suggest you ask a new question where you tell us what you're trying to achieve. Presumably the graph you were talking about was only a means to an end; what was the end goal? Presumably you wanted to build it only because you thought it'd help you with some task; what is it you really want to learn about the program? If you ask a new question telling us what your goal is (what you're trying to infer about the program), we might be able to suggest an appropriate static analysis technique that would be suitable for that goal.

$\endgroup$
  • $\begingroup$ Thanks for your answer. But I think there's a misunderstanding here: maybe I wasnt so clear with it: by saying 'runtime locations in mem' I had in mind of locks/barriers and not datas. $\endgroup$ – eternalStudent Apr 30 '15 at 10:58
  • $\begingroup$ @emma, nope, that wasn't clear at all: it wasn't mentioned anywhere in the question. Anyway, I suggest that you ask a new question, and specify what you are trying to do with your program analysis. $\endgroup$ – D.W. Apr 30 '15 at 19:57
  • $\begingroup$ Incidentally, @emma, the answer is still correct: there are still an unbounded number of runtime locations in memory (e.g., if you have locks as a field in an unbounded data structure stored on the heap, like a linked list) -- so the concepts in my answer still apply to your particular situation. $\endgroup$ – D.W. Jul 28 '15 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.