CSCE 434 Lecture 7
« previous | Monday, September 9, 2013 | next »
If someone's going to blow something up, haven't they already forfeited their intelligence?
Back End
Abstract Syntax Tree often used as IL.
The back end takes the IL as input and outputs machine code (or another lower level language)
Two parts:
- Instruction selection for each AST operation (ISA-level specificity)
- Register Allocation (Compiler selects these for you)
Automation has been less successful here (no "flex" or "bison" for back-end generation)
Pattern Matching is key in generation and recognition:
- ad hoc
- tree patterns
- string patterns
- dynamic programming
Register Allocation
- Values have to be in register when used, but
- there are fewer registers than variables.
- Optimal allocation is NP-Complete.
Tangent
Execution time is mainly I/O blocking: fetch instruction, fetch data
Writing compact code is very important because we want it to fit well in instruction cache
GPUs (formerly vector machines) are very efficient with performing the exact same operations on a large set of data.
Optimization
Between front-end and back-end.
Performs transformations on the IL to output a better IL.
For Next Time
- Patterson book about computer architecture.
- Associative Cache