INTERMEDIATE LANGUAGES (Chapter 8) - Throughout the course I have been emphasizing modularity for your compiler + Each changeable design decision goes in its own module + Such decisions often revolve around the representation of data + Interface should be relatively immune to change when internals change + Interface should be easy for others to use and understand - Because compilers are hard to write, it is advantageous if the components can be reused to implement new compilers. Modularity helps. + Lexer and parser generators (lex, CUP/yacc) + Architecture module can be replaced for new machine, allowing whole front-end to be reused (decision about target changes) + Architecture module can be moved to work with a new front-end (e.g., C) + Can probably reuse ST for different front ends, although it depends on nature of scoping. - Issue of optimization in code generation makes this more important + Majority of compiler can be optimizer + Would like to be able to reuse optimizer on different machines + But isn't performance all about exploiting quirks of architecture? + Yes and No, many optimizations are concerned with stylistic uses of language constructs that permit an improved instruction sequence + An architecture-indepedent optimizer finds these and exploits them + However, whether an ``optimization'' is a win may depend on features of the architecture - Architecture module helps in this regard (but is not enough) + Front- and back- ends are separate + Big jump from Oberon to assembler, basically do instruction selection, instruction ordering, register allocation all at once + Optimizations require multiple passes over the code; current approach allows just one pass + For doing optimizations, we need a module that is neither, otherwise we have to write a new optimizer every time we retarget to a new source or target language, and an optimizer can be most of a compiler, and is the most complicated code. +-------+ | main | +-------+ | start V +-------+ | parse | +-------+ --------------+ / | \ \ / | \ \ v | v v +-------+ | +-------+ +-------+ | lex | | |type ch| |codegen| +-------+ | +-------+ +-------+ | | / | \ V / | +> +-------+ / | |sym tab| <-+ | +-------+ | \ | v V +-------+ | arch. + +-------+ - Idea: have an intermediate language (IL) that is neither PL nor machine + Separates issues of PL, target, and PL/target opt. + Allows spanning PL-target semantic gap in two steps - brings code down a level, but still not machine - maybe resolves computation ordering, instruction choices - not machine quirks, register issues, stack details + Once have IL code, can traverse multiple times to optimize, so not restricted to get right during one-pass parse + Should be independent of either so can be reused with any front-end or back-end + Should be suitable for language and machine independent optimization (more on this later) + Should be easy for a computer to manipulate + Should not be too difficult to translate from PL to IL, IL to machine (note that these translations are just like PL --> machine translation) (OPTIMIZER NOT SHOWN, BUT WOULD BE ON IL) +-------+ | main |----------------+ +-------+ \ | start \ V \ +-------+ \ | parse | \ +-------+ ---------------+ \ / | \ \ \ invoke after parse / | \ \ \ and IL build/opt v | v b| v +-------+ | +-------+ u| +-------+ | lex | | |type ch| i| |codegen| +-------+ | +-------+ l| +-------+ | | d| /use | | | V v | | | ++=====++ | \ V /-|| IL || | > +-------+ / ++=====++ | |sym tab| / | +-------+ <+ +-----------+ \ / v v +-------+ | arch. + +-------+ - Although the IL is only a small part of the compiler, it plays a big role + By separating front-end and back-end, can develop each to be better suited to own roles. Code gen is no longer constrained by single STO rule, and load-load-compute-store. Easier to write each independently. + By building optimizer on top of IL instead of code gen, can reuse the optimizer as well. It can be the largest and most complex component + Parser and lexer are automatically generated from declarative descriptions. + This is the ultimate in modularity. We have taken a responsibility shared by parser and code generator and separated them. - Alternatives for IL representation: + Parse tree or abstract syntax tree, like I've been drawing all quarter - trivial to construct during parsing - retains some high-level structure so can find stylized uses - easy for computer to manipulate - expression trees are special, elegant case (no side-effects in tree) - parse tree less preferable because it leaves in junk, biased to parser x := (y + b * c) + (w + b * c) := / \ x + / \ / \ + + / \ / \ y * w * / \ / \ b c b c + Pseudo-assembly (called 3-address code) - ``close'' to target machine (structure, ops), yet independent + 3 address structure (result and two operands) is compatible with many architectures - uses infinite number of ``registers'' (temps), sometimes many types + variables and registers not distinguished, generally - easy to generate, manipulate - allows lower-level level optimizations, but is not tedious + reveals gotos + can expose ``byte'' addressing (good for optimizations) + a[i] for int array requires t1 = r * i + generally hides stack and frame pointers, globals vs. locals - regularity of instructions simplifies manipulation by computer x := (y + b * c) + (w + b * c) t1 := b * c t2 := y + t1 t3 := b * c t4 := w + t3 t5 := t2 + t4 x := t5 - perhaps special instructions for call, return, params - Array references are operations, too: x[i + 2] --> t1 = i + 2 t2 = x[t1] + My preference is 3-address code - syntax tree is very close to PL - parsing issue resolved - scoping - might require extension (many features) to handle many languages - 3-address code resolves more, but not all - parsing - scoping - assembly normal-form - instruction ordering - *not* register allocation, though + Neither of these is particularly good at capturing control flow - jumps are non-local, requires searching for target - could add pointers from jump instruction in 3-AC; easy for computer - similarly for if-while in syntax tree + One such approach is to use Control Flow Graphs and Basic Blocks - BB's are sequences of instructions (or lists of expression trees) that have no jumps in or out of them - CFG connects up BB's with pointers to model control flow if x < y then x := y + z else y := x + z ... t1 := x < y if !t1 goto L1 x := y + z goto L2 L1: y := x + z L2: ... +--------------+ |t1 := x < y | |if t1 |----+ +--------------+ | | | | True | V | False +--------------+ | +--|x := y + z | | | +--------------+ | | | | +--------------+ | | |y := x + z |<---+ | +--------------+ | | | v | +--------------+ +->|... | +--------------+ - Trivial to identify jump-free sequences of code, req. of many opts - can traverse as in a graph alg. - CFG has minimal number of nodes, lowering cost of polynomial traversal/search algorithms