3 ms·
Wild tangent. I've got a gist of what a basic block is due to online discussions. I know it is roughly a list of instructions and that jumps are the boundaries
by dragontamer 3y ago
Wild tangent.
I've got a gist of what a basic block is due to online discussions. I know it is roughly a list of instructions and that jumps are the boundaries.
But I'm looking to understand it on a more fundamental level.
I'm guessing the subject is SSA / single static assignment and compiler theory? Just wanna ask publicly if I'm on the right track, and if I'm following this discussion correctly.
- rwmj 3y agoIt's definitely a fundamental concept of compiler theory. Wikipedia has a reasonable description: https://en.wikipedia.org/wiki/Basic_block https://en.wikipedia.org/wiki/Basic_block
- pm215 3y agoIt's not specific to SSA, though SSA assumes it's working with basic blocks (as do a lot of compiler algorithms). And yeah, writeups of compiler theory (and compiler practice) are where to go for more detailed discussion. The core idea I think is that control flow complicates the kinds of analysis a lot of optimisation and other compiler passes need to do; so by first breaking the input into pieces which have very restricted possible flows of control ("only entered at the top, only exited at the bottom" is the classic definition) then: 1. You can get quite a long way with optimisations that only work within a basic block, and the restriction to within-a-BB simplifies things a lot because it can entirely ignore control flow 2. Analysis that only cares about control flow can work on a graph of BBs and ignore the individual-statement/instruction details, because the BB graph captures all the detail of what can branch where
- mhh__ 3y agoRead the book "Engineering a compiler" if you want to get a medium-hard but nicely written intro to basically all of the basics. Skip the bit about parsing, it doesn't matter for what you want to learn.