Chapter 15, 17.1 and 17.2 from Scott

Compilation

Intermediate code generation motivated by the fact that code improvements can be done more easily on non-hierarchical structures such as AST. Nodes are grouped into basic blocks, and then a control flow graph is created.

A basic block is a maximal length set of instructions that should execute sequentially at runtime. No branches in or out; starts as the target of a jump and ends with a jump. Operations are instructions for idealized machine with infinite virtual registers.

Machine Independent Code Improvement

These are transformations on the control flow graph.

  • Local code improvements removes redundancy within a block
  • Global code improvements identifies and removes a variety of redundancies between blocks within a subroutine. E.g., within a loop, an expression that is computed only once need not be recomputed again
  • Loop improvements

Target code generation

String together basic blocks into a linear sequence. Then, blocks must be translated into the instruction set of the machine.

Machine specific code improvement

  • Register allocation- map the unlimited virtual registers onto the bounded set of registers available in the target machine. May need additional loads/stores to multiplex 1 real register for 2 virtual registers
  • Instruction scheduling- pipelining. When doing concurrent programming, can alter the program in unintended ways.
  • Code improvement

Intermediate forms

Link between front and back end of compilers

  • trees or DAGs- reflect structure of the language, can be specified by attribute grammars
  • stack-based- compact and simple
  • 3-address instructions

Research is being done to develop higher-level intermediate forms to get better portability on different architectures (e.g., GPU and CPU)

Compilers that have back ends for different target architectures do as much work as possible on a high or medium level IF.

Address space organization

Assemblers, linkers, and loaders typically operate on a pair of related file formats

  • relocatable object code
  • executable object code

Relocatable object code is acceptable as input to a linker. Executable object code is acceptable as input to a loader. A relocatable object file includes an import table, which IDs instructions that refer to named locations whose addresses are unknown, but are presumed to lie in other files yet to be linked to this one. It also has a relocation table, which IDs instructions that refer to locations within the current file, but that must be modified at link time to reflect the offset of the current file within the final, executable program, as well as an export table, which lists names/addresses of locations in current file that may be referred to in other files. Imported and exported names are external symbols.

Compilers generally generate assembly language that must subsequently be processed by an assembler to create object file.

Linking

For separate compilation, need to be able to compile fragments of a program together. A static linker does its work prior to program execution and produces an executable. A dynamic linker does it work after the program has been loaded into memory.

Involves two tasks; relocation and resolution of external references.

Peephole Optimization

Slide a several-instruction-sized window over the code in a basic block. Use heuristics to match patterns in suboptimal sequences of instructions. For e.g., many redundant loads and stores can be eliminated.