Compilers and Compilation Study Guide pt3

Overview of Compilation Stages

• The compilation process is a multi-step routine that transforms source code into a final executable or assembly language.

• For many compilers, the final result of the compilation process is assembly code, which must subsequently be processed through an assembler to produce machine code.

• The standard stages of compilation include:

  • Lexical Analysis (Scanner): The first phase, which reads source code characters and groups them into lexemes/tokens.

  • Syntax Analysis (Parser): Organizes tokens into a hierarchical structure, usually a parse tree.

  • Semantic Analysis: Checks the input for well-defined meaning.

    • Does Lexical & Syntax analysis together before moving to intermediate code because of the differences in CPUs which could cause issues in code generation.

  • Intermediate Code Generation: Produces a machine-independent representation of the program.

  • Machine-Independent Code Improvement (Optional): Optimizes the internal representation.

  • Target Code Generation: Translates the optimized intermediate code into the target machine's language (assembly or binary).

  • Machine-Specific Code Improvement (Optional): Fine-tunes the target code based on specific processor architecture.

Semantic Analysis

• Definition and Input: A semantic analyzer receives its input from the syntax analysis phase in the form of a parse tree and a symbol table.

• Primary Purpose: The core objective is to determine if the input has a well-defined meaning. While a program might be syntactically correct (properly structured), it may still be semantically nonsensical.

• Practical Focus: In real-world applications, semantic analyzers focus primarily on:

  • Type Checking: Verifying that operators are applied to compatible data types.

  • Type Coercion: Handling automatic type conversions based on established type rules.

• Type Coercion Definition: This is the automatic conversion of a datum from one data type to another within an expression. It occurs because the datum is stored as one data type, but its specific context (such as an arithmetic operation) requires a different data type.

Functions of the Semantic Phase

• Semantic Error Detection: Checking phrases for logical errors related to types. For example, in a C program, a declaration such as $int\,x = 10.5;$ should be flagged as a semantic error because a floating-point literal is being assigned to an integer.

• Consistency Tracking: The phase keeps track of the types of identifiers and expressions to verify their usage remains consistent throughout the program.

• Symbol Table Maintenance: The analyzer maintains the symbol table, which acts as a repository for information about every identifier. This includes:

  • Identifier Type (e.g., $int$, $char$, $float$).

  • Scope (the specific portion of the program where the identifier is valid).

• Rule Enforcement: The semantic analyzer enforces several critical rules using the symbol table:

  • Ensuring every identifier is declared before it is used.

  • Ensuring no identifier is used in an inappropriate context (e.g., adding a string to an integer).

  • Verifying that function calls have the correct number and type of arguments.

• Dynamic Semantics (Run-time Checks): Certain rules are checked during the execution of the program, including:

  • Verifying that an array subscript expression lies within the defined bounds of the array.

  • Ensuring variables are never used in an expression unless they have been assigned a value.

The Symbol Table

• Construction: The symbol table is built and maintained by the semantic analyzer.

• Mapping functionality: It maps each identifier to all information known about it, such as internal structure and scope.

• Primary Purpose: To provide quick and uniform access to all identifier attributes throughout the compilation process.

• Relationship to Semantic Analysis: By utilizing the symbol table, the semantic analyzer can effectively enforce the wide variety of language-specific rules listed above.

Intermediate Code Generation (ICG)

• Definition: The ICG phase produces a program in a different language that exists at an intermediate level—situated between the high-level source code and the low-level machine code.

• Advantage of Machine-Independence: This level allows a significant portion of the compiler to be machine-independent. Sometimes, intermediate languages take the form of assembly languages.

• Flexibility Benefits: A single lexical analyzer and parser can be utilized to generate code for multiple machines. This is achieved by providing different "back-ends" that translate the common intermediate language into machine-specific assembly.

• Role in Interpretation: Intermediate code is used in interpretation, where it is executed directly rather than being translated into binary code for storage.

• Types of Intermediate Representations (IR):

  • Structured: Graph-based or tree-based (e.g., Abstract Syntax Trees).

  • Flat, Tuple-based: Generally three-address code, also known as quadruples.

  • Flat, Stack-based: Instructions based on a stack architecture.

  • Hybrid: Any combination of the above three formats.

Code Generation

• Architecture Dependency: Code generation is strictly dependent on the architecture of the target machine.

• Required Knowledge: The process requires comprehensive knowledge of the target computer's instructions and addressing modes.

• Resource Management: A major aspect of code generation is the efficient initialization of machine resources. This involves assumptions regarding:

  • Instruction types available on the target machine.

  • Commutative properties of operators (e.g., $a + b = b + a$) to optimize expression evaluation.

  • Proper usage of syntax for syntax-directed translation.

• Inputs to the Code Generator:

  • Intermediate Code (Tuples, quadruples, triples, postfix notation, syntax trees, etc.).

  • Symbol Table data.

Error Handling and Types

• General Protocol: Upon detecting an error in any phase, the compiler must:

  • Report the error in a helpful and descriptive way.

  • Correct the error if possible.

  • Continue processing to identify further errors in the code.

• Syntax Errors: Errors appearing within the program text. This includes:

  • Lexical Error: A mistake in a lexeme, such as typing $esle$ instead of $else$ or missing quotes in a literal string.

  • Grammatical Error: A violation of the language's formal rules.

• Semantic Errors: Mistakes concerning the meaning of a program construct.

  • Type Errors: Occur when an operator is applied to an incorrect argument type or number of arguments.

• Logical Errors: Occur when a poorly conceived program is executed; the logic does not yield the intended result.

• Run-time Errors: These are errors that can only be detected while the program is actually running (e.g., division by zero or array out-of-bounds).

Compiler Optimization Fundamentals

• Compiler Structures:

  • Basic Compiler: High-level language (HLL) $\rightarrow$ Front End $\rightarrow$ Intermediate Representation (IR) $\rightarrow$ Code Generator $\rightarrow$ Low-level language (LLL).

  • Optimizing Compiler: HLL $\rightarrow$ Front End $\rightarrow$ IR $\rightarrow$ Optimizer $\rightarrow$ Improved IR $\rightarrow$ Code Generator $\rightarrow$ LLL.

• Control Flow Graph (CFG): This is how the compiler "sees" the program. It consists of Basic Blocks, which are groups of consecutive instructions with a single entry point and a single exit point.

• Requirements for Optimization:

  • Preserve Correctness: Optimization must not change the program's output. The speed of an incorrect program is irrelevant.

  • Improve Performance on Average: While most optimizations help, optimized code might occasionally perform worse than original code due to specific architectural quirks.

  • Worth the Effort: Implementation cost versus gain. For example, it is not worth one person-year of work and a doubling of compilation time for a mere $0.1\%$ improvement in speed.

• General Goals: To make programs smaller, faster, or both. It targets speed, memory usage, and the program footprint.

• Methodology:

  • Rearranging computations for better efficiency.

  • Eliminating redundancies.

Optimization Constraints and Transformations

• Key Limitations:

  • The underlying algorithm is not changed; an inefficient algorithm remains inefficient.

  • It cannot fully utilize every nuance of every instruction set.

  • Optimizations must be conservative: when in doubt about a run-time condition, the compiler must not optimize in a way that could break the program.

• Local Transformations: Applied over small segments (basic blocks). These provide limited benefits at a low cost.

• Global Transformations: Applied over larger segments like loops or function bodies. This requires extensive Control Flow Analysis and Data Flow Analysis.

Examples of Low-Level Arithmetic Ops vs. High-Level C

• Example Case: Let $n$ be a $uint32\_t$ stored in Register $\%0$ (LLVM) or $\%rdi$ (Assembly).

• Multiplication by 8:

  • C: $uint32\_t\,x = n \times 8;$

  • LLVM IR: $\%2 = shl\,nsw\,i32\,\%0, 3$ (Shift Left).

  • Assembly: $leal\,(,\%rdi,8), \%eax$.

• Multiplication by 15:

  • C: $uint32\_t\,y = n \times 15;$

  • LLVM IR: $\%3 = mul\,nsw\,i32\,\%0, 15$.

  • Assembly (Optimized): Uses a sequence of $leal$ instructions to avoid slow multiply instructions.

• Division by 71:

  • C: $uint32\_t\,z = n / 71;$

  • LLVM IR: $\%4 = udiv\,i32\,\%0, 71$.

  • Assembly: Replaces division with a high-precision multiplication ($imulq$) and shift ($shrq$) because division is very expensive.

Comparison of Assembly Instructions

• To move the hexadecimal value $41h$ (decimal $65$) into a register across systems:

  • Motorola 6800/68HC11: $LDAA\,\#\$41$

  • Intel x86: $mov\,al, 41h$

  • Motorola 680x0: $move.b\,\#\$41, D0$

  • PIC16xx: $movlw\,0x41$

  • Motorola 56000: $move\,\#\$0041, A$

  • Intel 80960: $lda\,0x41, r4$

Optimization and System Performance

• Performance Equation: $Execution\_time = num\_instructions \times CPI$

• Improving Performance:

  • Decrease Cycles Per Instruction (CPI) by scheduling instructions to avoid dependencies and improving cache/memory locality.

  • Decrease the number of instructions by targeting special/new instructions.

• Role of the Programmer: Selection of the best algorithm (Big-O savings are usually more important than constant factor optimizations). Redundant smashing of code into unreadable blocks should be avoided.

Specific Machine-Independent Optimizations

• Constant Propagation (CP): Replacing variables with known constants when possible.

• Constant Folding (CF): Evaluating expressions containing constants at compile time (e.g., $n = 5 + 3$ becomes $n = 8$).

• Common Sub-expression Elimination (CSE): Computing a given expression only once and reusing the result if variables haven't changed.

• Dead Code Elimination (DCE): Removing code that can be identified as never executing (e.g., $if(false)$ blocks).

• Loop Invariant Code Motion (LICM): Moving code that does not change within a loop out of that loop to save millions of executions.

• Strength Reduction: Replacing expensive operations (multiplication) with cheaper ones (addition or bit shifts). Example: $y = x \times 2$ becomes $y = x + x$.

• Function Inlining: Replacing a function call with the actual code of the function body. This eliminates call/return overhead but can increase code size.

Specific Machine-Dependent Optimizations

• Instruction Scheduling: Reordering instructions to keep the processor pipeline full.

• Loop Unrolling: Reducing loop overhead by repeating the loop body multiple times within a single iteration, thus reducing the number of condition tests and increments.

GCC Optimization Levels

• -g: Includes debug information, no optimization.

• -O0: The default level; no optimization.

• -O1: Performs basic optimizations that do not take a long time (CP, CF, CSE, DCE, LICM, and small inlining).

• -O2: Performs more aggressive scheduling and takes longer to optimize.

• -O3: Makes space/speed trade-offs, enabling loop unrolling and more aggressive inlining.

• -Os: Optimizes for size.

• Evaluation Command: To see enabled optimizers at O3 vs O2:

  • gcc\,helloworld.c\,-Q\,-O3\,--help=optimizers > /tmp/03-opts

  • gcc\,helloworld.c\,-Q\,-O2\,--help=optimizers > /tmp/02-opts

  • $diff\,/tmp/02-opts\,/tmp/03-opts | grep\,enabled$