Skip to content

Lecture No. 04

Dated: 13-03-2025

The CISC (Complex Instruction Set Computer) provided a rich instruction set and addressing modes but this made the compiler's job of outputting efficient machine code harder.
The RISC architecture simplified this problem.

Register Allocation

Registers provide a very important role for providing high speed access to the operands for computation because memory accessing these operands is a lot more slower. The back end1 tries to keep these operands in the registers for use but it has to manage the limitations of resources such as number of registers which are already in use and are not available to it (such as the program counter) or the registers themselves are very small etc.
Optimal register allocation is NP-Complete.

Instruction Scheduling

Modern processors have multiple functional units. The back end1 needs to schedule instructions to avoid hardware stalls and interlocks. The generated code should use all functional units productively. Optimal scheduling is NP-Complete in nearly all cases.

Three Pass Compiler

cs606_e_4_1.svg

Topology for a three pass compiler

The middle end is also called the optimizer and as the name suggests, its task is to optimize the intermediate representation by reducing the resource consumption.

  • Space
  • Time
  • Power

Typical transformations performed by the optimizer are

  • Discover & propagate some constant value
  • Move a computation to a less frequently executed place
  • Specialize some computation based on context
  • Discover a redundant computation & remove it
  • Remove useless or unreachable code
  • Encode an idiom in some particularly efficient form

Role of Runtime System

The program code runs as a process in the operating system. The compiler needs the knowledge of the runtime system to make effective use of the runtime environment and machine resources.
The problems which need to be addressed in this context are

  • Memory management
  • Allocate and de-allocate memory
  • Garbage collection
  • Run-time type checking
  • Error / exception processing
  • Interface to OS - I/O
  • Support for parallelism
  • Parallel threads
  • Communication and synchronization

References

  1. Read more about back end. ↩↩