SwiftShader Documentation

This document serves as a collection of test cases and observations regarding optimization failures in the LLVM/Clang toolchain (specifically when using clang -emit-llvm-bc | opt -O3). It highlights scenarios where the compiler fails to perform expected algebraic simplifications, folding, or instruction combining.

Key categories of optimization issues identified include:

• Algebraic Simplification & Folding: Failure to combine bitwise operations (e.g., (b << 31) | (b << 30)) or fold logical expressions (e.g., (a&&b) || (a&&!b) into a).
• Integer Arithmetic: Failure to optimize signed/unsigned arithmetic with known properties like Non-Standard/Non-Associative (nsw) behavior (e.g., (x - 10) < 0 not becoming x <= 9).
• Store Sinking: Failure to move partially dead stores out of loops (DSE - Dead Store Elimination) or sink loads/stores into conditional blocks to avoid redundant memory traffic.
• Load PRE (Partial Redundancy Elimination): Failure to hoist loads out of critical edges or common blocks to reduce redundant memory access.
• Scalar PRE: Failure to hoist computations (like multiplications) out of conditional branches to reduce code size and redundant work.

This document outlines various optimization opportunities and patterns for the LLVM Target backend, focusing on instruction selection, DAG combining, and code simplification. Key areas for improvement include:

• Instruction Sinking: Moving computations (like PIC base computations or argument loads) from the entry block into specific blocks where they are actually used to avoid unnecessary work on early-out paths.
• Instruction Combining: Converting sequences like load + fabs + store into integer operations to leverage faster read/modify/write instructions on specific architectures (e.g., X86).
• DAG Combiner Improvements: Combining small, fragmented loads into single larger loads when profitable.
• Loop Unrolling: Implementing partial unrolling to eliminate redundant checks (e.g., bitwise operations) within the loop body, potentially reducing code size.
• Strength Reduction: Merging library call simplifications, such as converting memcpy(a, b, strlen(b)) into strcpy where safe.
• Bitwise and Arithmetic Simplifications:
  • Optimizing bitwise patterns (e.g., i | (i<<8) | (i<<16) | (i<<24)) into more efficient forms like multiplications or iterative shifts.
  • Simplifying divisibility checks (n % 3 == 0) into multiplicative inverse comparisons.
  • Combining multiple bitwise checks into a single operation (e.g., ((a & mask) != 0) || ((b & mask) != 0) into ((a | b) & mask) != 0).

This document serves as a collection of technical notes and TODOs for improving the PowerPC-specific code generation in the LLVM backend. It identifies several areas where code quality (specifically instruction selection and scheduling) can be improved to match or exceed GCC's performance.

Key areas for improvement include:

• Prolog/Epilog Optimization: Implementing lmw/stmw passes similar to ARM's load/store optimizer.
• Constant Pool Management: Improving how constant pools are handled in PIC (Position Independent Code) mode by materializing base addresses into registers to avoid repeated lis instructions.
• Loop Optimization: Improving loop structures (e.g., using bdnz instead of bdz) and strength-reducing remainder/division operations.
• Register Spilling: Optimizing the handling of the Link Register (LR) to avoid unnecessary stack spills by using GPRs instead.
• Instruction Fusion: Implementing infrastructure to recognize and schedule instruction fusion opportunities introduced in ISA 2.06 and 2.07.
• Floating Point Comparisons: Reducing the sequence of mfcr, rlwinm, and or instructions into more efficient single-instruction patterns.

Subzero is designed as a fast code generator for the Portable Native Client (PNaCl) project, intended to replace or augment the LLVM-based translator. Its primary goals are:

• Translation Speed: Target a 10x improvement over LLVM. The goal is to translate .pexe files at a rate comparable to download speeds (e.g., ~6 MB/sec on high-end workstations).
• Code Quality: Aim to meet or exceed LLVM's -O0 quality, with a stretch goal of approaching LLVM's -O2 quality.
• Binary Size: Target a 10x reduction in translator size (aiming for ~1 MB) compared to the ~10 MB pnacl-llc binary. This is achieved via MINIMAL builds that compile out unnecessary features.
• Memory Footprint: Maintain a stable memory footprint proportional to the largest input function size, rather than the total .pexe file size, to prevent OOM (Out-of-Memory) issues on constrained devices.
• Multithreaded Scalability: Support concurrent translation of different functions with deterministic output (functions and data must always appear in the same order).

Reactor is an embedded language for C++ designed to generate specialized processing routines (called Routines) in a WYSIWYG fashion. It allows developers to write code that looks like standard C/C++ but is actually recorded as an intermediate form to be compiled by a JIT.

Key Features:

• Simplified Syntax: Uses C++ operator overloading to avoid the verbosity of direct LLVM API calls. For example, instead of complex LLVM Value creation, you can use standard operators.
• Type System: Reactor types use the same names as C types but start with a capital letter (e.g., Float, Int32).
• Control Flow: Implements C-like counterparts such as If(), Else, and For(,,).
• Specialization: Allows for highly efficient code by specializing routines for the exact state and shaders used in a draw call. For example, x = addOrSub ? x + y : x - y; results in only one specific operation being generated in the final code.

IDs are used to reference values within a module.

• Syntax: An ID begins with % followed by a name consisting of letters, numbers, or underscores (e.g., %main, %void, %fnMain).
• ID Definition: Occurs when an instruction generates a <result-id> (e.g., %void = OpTypeVoid).
• ID Usage: Occurs when an existing ID is passed as an operand to an instruction (e.g., %3 = OpFunction %1 None %2).
• Internal Numbers: The assembler assigns a unique internal number to every ID. The disassembler typically generates IDs using decimal numbers greater than 0.

          OpCapability Shader
          OpMemoryModel Logical Simple
          OpEntryPoint GLCompute %main "main"
          OpExecutionMode %main LocalSize 64 64 1
  %void = OpTypeVoid
%fnMain = OpTypeFunction %void
  %main = OpFunction %void None %fnMain
%lbMain = OpLabel
          OpReturn
          OpFunctionEnd