Compiler organization

• Discuss how a compiler is organized into stages: parser (generates AST), semantic analysis (generates typed-AST), IR-generation (generates IR), optimizer (generates IR), codegen-and-opt (generates executable)
• Discuss the different optimization levels of a compiler and what phases/passes are enabled at each level. Discuss the evaluation criteria of an optimization (payoff [indirect,direct], generality, simplicity [ease-of-implementation]). e.g., O1 usually includes those optimiztions that score high on all three criteria. Oz optimizes for code size. Discuss examples of optimizations and characterize them, e.g., loop unrolling, pop-count.
• Discuss how a compiler's optimizer is organized into algorithmic passes, each pass takes an IR-program and outputs an IR-program. While the IR constructs used before a pass may be different from the IR constructs used after a pass, the IR is usually the union of all such constructs. e.g., vectorization instructions do not appear in unoptimized IR, while compiling C programs.
• The organization into passes allows flexibility of rearranging the passes. However, it is usually preferred to organize the passes in a certain order, e.g., loop unrolling should occur earlier in the pipeline.
• Discuss different source languages and their different optimization needs, and thus the need for multiple IRs within a compiler:
  • SQL: need query optimizer that figures out table data structure, join algorithm, e.g., hashtable, natural-vs.-hash-join, etc. Generates a query plan at the end, which is usually compiled to a source language like C/C++, but is best compiled (in mature pipelines) directly to IR like LLVM-IR (as the latter preserves higher-level constructs, e.g., vectorization).
  • OCaml: need memory management optimizer, e.g., do not keep objects if they are no longer used.
  • PyTorch/TensorFlow: need tensor layout, parallelism, and data transfer optimizer.
• A machine has a finite register file and memory, and an execution loop that keeps executing one instruction after another.
• Some opcodes in a machine are present because they are easy for a human to understand and code in a high-level language too, e.g., add/sub... e.g., it is possible for a machine to have instructions that set a bit in register, in which case, a single addition operation will become a sequence of instructions to implement, say a ripple-carry adder.
• Some opcodes are midway between human understanding and fast execution, e.g., vector addition/subtraction/...
• Some opcodes are highly specialized, e.g., compute the sha1 hash of a memory region, or scatter and gather bytes from a memory
• The IR usually needs to be rich enough to support all these different opcodes during code generation. Discuss how even compilers for languages like C/C++ include Machine-IR for machine-dependent optimizations, e.g., if the IR generates an opcode for popcnt, but the architecture does not support it, then inefficient code will get generated.
• A successful paradigm for IR design is three-address code, discussed next

Intermediate Language

• A language between the source and the target
• Provides an intermediate level of abstraction
  • More details than the source
  • Fewer details than the target
• Provides an intermediate level of abstraction
  • e.g., the source language has no notion of registers, the IR may have a notion of registers.
  • Why are we using it? Just experience. Some compilers, in fact, choose to have multiple IRs, and thus multiple lowerings.
    • Intuition: make some decisions upfront (source to IR); hopefully these decisions do not make much difference to optimization opportunity, but simplifies reasoning about the final code generation (as the abstraction level is much closer to the target).
    • An IR would usually always loose some information (information that the compiler developer considers extraneous to optimization opportunity). e.g., loop structure converted to gotos. Ideally the abstraction lowering should not loose much information (should not preclude optimization opportunity!).

The design of an IR is an art --- hard to say that this is the best possible IR which will allow the best code generation/optimization. We will consider IR which resembles high-level assembly

• Uses register names, but has an unlimited number
• Uses control structures like assembly language
• Uses opcodes but some are higher-level
  • e.g., push translates to several assembly instructions
  • Most opcodes correspond directly to assembly opcodes

Each instruction is of the form

x = y op z
x = op y

• y and z are registers and constants
• Common form of IR
• This particular IR is also called three-address code

The expression x + y*z is translated

• t1 = y * z
• t2 = x + t1

IR code generation is very similar to assembly code generation. But use any number or IR registers to hold intermediate results.

igen(e, t)

• code to compute the value of expression e in register t.

Example:

igen(e1+e2, t) =
  igen(e1, t1)  //t1 is a fresh register
  igen(e2, t2)  //t2 is a fresh register
  t = t1 + t2

Homework: write igen for control-flow constructs like if-then, if-then-else, while, and for loops.

LLVM IR is an example of IR. It resembles three-address code, but with usually higher-level opcodes than assembly.

• IR designer's dilemma example: how high-level should the opcodes be? Too low-level may preclude optimization opportunity (assembly opcodes may be higher-level than IR opcodes, e.g., vector instructions). High-level IR opcodes make the IR design large and bulky (starts looking almost like a CISC ISA). Big problem with IR: needs to be designed for all possible ISAs (makes the design decisions even harder). Typical design choice: support as many opcodes as necessary for all the common optimizations on all the common ISAs.
• The same IR may be used for multiple high-level programming languages. e.g., LLVM may be the target for both C and Java programs. Can again increase the complexity of LLVM IR, because we need to try and retain high-level semantics of all supported languages (making them too low-level for simplicity would preclude optimization).
• Yet, if one can design an IR successfully, it is all perhaps worth the effort. Do all the hard work related to optimization once and reap the benefits everywhere (for all languages, and for all ISAs).

Discuss the reasons for the context being a hardware optimization language: its generality, its complexity (having to worry about hardware), the applicability of ideas to other higher-level optimization stages.

Discuss the history of GCC and LLVM IR. The IR design is so central to compiler development that the whole compiler infrastructure is named after LLVM.