I just realized a Control-Flow Graph (CFG) is composed of basic blocks, which is a set of instructions. It is mentioned that you can still do stuff like dead code elimination and whatnot, with the CFG, but that seems like you'd be reaching into the basic block to figure that out. At that point you are dealing with individual instructions. But that's the domain of Data-Flow Graphs (DFG). Data-Flow Graphs are made of connections between individual instructions.

My question is, why not just always deal with individual instructions instead of the basic blocks. It seems like in the end you are using individual instructions anyways. Wondering the advantages a CFG has over a DFG, and vice versa.

  • $\begingroup$ Control flow graphs and data flow graphs just represent different things. Neither is an alternative of the other. $\endgroup$ – Derek Elkins left SE Apr 30 '18 at 2:33

A control-flow graph serves a different purpose than a data-flow graph. They aren't alternatives. A control-flow graph represents the flow of control: which instruction can follow another. A data-flow graph represents the flow of data: which instruction can read data that was created by another.

Perhaps you mean to ask why each vertex in a control-flow graph represents a basic block (a group of instructions) rather than a single instruction. That's an optimization. You could have each vertex represent a single instruction, but often you'll have a long sequence of consecutive instructions with no control-flow transfer, and they all have the same properties, so it is natural to collapse them into a single vertex. Also subsequent program analyses may be faster with this optimization; see Why is it better to do the data flow analysis in the basic blocks.


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.