[Homework 4] how to handle join of callgraph in worklist algorithm

[KunJeong]

The worklist algorithm in Lecture 6 joins all memory states that can happen after a transition to current label w.

However, since the transfer function of our ThriLLVM analyzer returns a pair (callgraph, (location, memory) list), so it seems like we may need to join the returned callgraphs as well. Is this necessary? Or can we just take the current callgraph and transition according to that? Thank you.

[KunJeong]

Update: there seems to be no "current callgraph" that we can obtain in a fashion similar to m_old, since callgraph is stored in neither Table nor Worklist. But the recursive function run takes the callgraph as a parameter, so maybe this can be used..? In general, I am very confused about how the callgraph should be treated during the run function.

[KihongHeo]

Hi. Callgraph is computed in a flow-insensitive way. That means you don't have to differentiate different instances of call graph per each label, but it is enough to have a single global view of call graph.

During the run function, you can just keep accumulate call information in calligraph and pass it to the next run as you keep accumulating table. So no partitioning is required for call graph.

[KunJeong]

Okay, but even if it is flow-insensitive, doesn't that mean that we don't need to partition but still need some logic to join the resulting callgraphs? Or by accumulation do you mean that I should pass the result of transfer to the next call to transfer (in the same iteration)? In that case, I think the order would affect the calculation quite a lot..

[KihongHeo]

I mean the latter. You can pass the newly updated callgraph to the next recursive call of transfer. I don't understand why the order matter. We can discuss during the lecture today.

[KunJeong]

I think I've understood (finally). Since we are going to reach the "complete" callgraph at some point, the minor details and order don't matter as long as we don't lose information. One last question. How can one prove that the worklist algorithm is sufficient to construct a complete callgraph? It's somewhat untrivial to me since the worklist algorithm is specifically constructed to reach fixed point in the memory table.

[KihongHeo]

Nice to hear that and your new question is also very good. The call graph you are computing actually does not have anything new. Conceptually, it is just a subset of the memory table. Once you compute the memory table, you can reconstruct the corresponding call graph (i.e., call edges and call sites) by scanning the memory table for all label. So, we didn't talk about call-graph in the lecture slides at all.

But in the homework, I recommend you additionally compute call-graph because it is useful in practice (related to the quiz).

[KunJeong]

I see. Thanks!