Compiler Design · topic
Leaders, basic blocks and flow graphs, loops and dominators, the DAG of a block, common-subexpression and dead-code elimination, folding, copy propagation, strength reduction, peephole rules and register counts.
The leader rules and the partition of three-address code into basic blocks, flow-graph edges for fall-through and jumps, dominators, back edges and natural loops, worked on a ten-line loop that is drawn as a flow graph. Two solved past questions count blocks and the largest block, and the traps about jump lines versus jump targets. Every leader, edge and loop comes from a script.
A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.
![Flow graph of six basic blocks: B1 i = 1, s = 0; B2 if i greater than n goto B6; B3 t1 = 4 * i, t2 = a[t1], if t2 less than 0 goto B5; B4 s = s + t2; B5 i = i + 1, goto B2; B6 return s. Edges B1-B2, B2-B3, B2-B6, B3-B4, B3-B5, B4-B5 and the back edge B5-B2.](https://bywjbbkinjqiyalvzqfd.supabase.co/storage/v1/object/public/sheet-media/CD/CD-17/diagrams/CD-17.d01.webp)
The DAG of a basic block built by value numbering, drawn for a classic block and used for local common-subexpression and dead-code elimination. The local rewrites (constant folding and propagation, copy propagation, algebraic identities, strength reduction, dead code) applied in sequence to one block with a script check that the live results never change, peephole rules, and register and temporary counts: Ershov labels for an expression tree and the maximum number of live values in a straight-line block.
A partial preview of the top of the sheet. The full sheet is in the Compiler Design cheat sheet pack.
