3 ms·
> it basically represents control flow as a gigantic DAG Control flow is not a DAG.
by moonchild 4y ago
> it basically represents control flow as a gigantic DAG
Control flow is not a DAG.
- 3836293648 4y agoPretty sure they mean the AST is a DAG
- pshirshov 4y agoWell, why?
- AshamedCaptain 4y agoDirected _Acyclic_ Graph. Control flow graph has loops.
- pshirshov 4y agoThis guy builds a compiler. I guess he added some limitations into his model so his CF can be represented as a DAG. I have a compiler which represents its CF as a DAG.
- tick_tock_tick 4y agoFor it to be a DAG you'd have the solve the halting program wouldn't you?
- remram 4y agoNo. Knowing whether programs end in finite time (dependent on input) doesn't mean all programs end or that all programs end in constant time. The halting problem is also not considered unsolved (though P=NP is unsolved).
- spatulon 4y agoYou're not wrong. I guess they're just trying to say that LLVM's control-flow graph is implemented as individually heap-allocated objects for nodes, and pointers for edges. (I haven't looked at the LLVM code, but that sounds plausible). Even if those allocations are fast on Linux/Mac, I wonder whether there are other downsides of that representation, for example in terms of performance issues from cache misses when walking the graph. Could you do better, e.g. with a bump allocator instead of malloc? But who knows, maybe graph algorithms are just inherently cache-unfriendly, no matter the representation.