DOCSEARCHbyAlgolia
Submit Docs

SLOTHY: Assembly Superoptimization via Constraint Solving

repository·main·Indexed 43 days ago

https://github.com/slothy-optimizer/slothy

An assembly-level superoptimizer that uses constraint solving to automate instruction scheduling, register allocation, and software pipelining. SLOTHY produces semantically-equivalent optimized assembly using the same instructions and data flow to minimize CPU pipeline stalls while maintaining developer control over instruction selection. It supports features such as register renaming, address offset fixup, and integration with LLVM Machine Code Analyzer (llvm-mca) for performance evaluation.

Tokens
10.6K
Snippets
30
Records
46
Agent score
56%

What's inside SLOTHY

  1. Supported Architectures and Microarchitectures in SLOTHY

    main

    SLOTHY provides experimental support for specific instruction set architectures (ISAs) and microarchitectures. Use these models to guide your assembly optimization tasks.

    Supported Architectures

    • Armv8.1-M: Primarily focused on Helium SIMD instructions.
    • AArch64: Supports scalar and Neon instructions (currently incomplete).

    Supported Microarchitectures

    • Cortex-M55: Based on Armv8.1-M with Helium support.
    • Cortex-M85: Based on Armv8.1-M with Helium support.
    • Cortex-A55: Based on AArch64. This model is noted as being largely complete and accurate.
    • Cortex-A72: Based on AArch64.

  2. What is SLOTHY and how does it work?

    main

    SLOTHY (Super Lazy Optimization of Tricky Handwritten assemblY) is an assembly-level superoptimizer designed to automate microarchitecture-specific optimizations. It focuses on three primary tasks:

    1. Instruction scheduling
    2. Register allocation
    3. Software pipelining (periodic loop interleaving)

    Mental Model

    Instead of writing highly optimized, microarchitecture-specific assembly, developers write 'clean' assembly that emphasizes the logic of the computation. SLOTHY then acts as a constraint solver frontend. It converts the input source into a data flow graph and builds a constraint model capturing valid instruction schedulings, register renamings, and periodic loop interleavings. This model is passed to an external solver (currently Google OR-Tools) to find an optimal satisfying assignment, which is then converted back into the final optimized code.

    Performance Expectations

    • < 50 instructions: Optimized in seconds to minutes.
    • Up to 150 instructions: Optimized in minutes to hours.
    • Larger kernels: May require specific heuristics.

  3. Understand SLOTHY output and instruction gaps

    main

    When viewing optimized assembly output, SLOTHY may include // gap comments.

    • // gap: Represents an unused issue slot in the CPU pipeline. For example, on a dual-issue CPU like the Cortex-A55, if the Neon pipeline can only issue one 128-bit instruction per cycle, a // gap will appear after each instruction because the second issue slot cannot be filled by another 128-bit Neon instruction.
    • Register Renaming: SLOTHY may rename registers (e.g., changing v24 to v13) to eliminate false dependencies, allowing independent computation streams to be interleaved more effectively.
    • Visual Representation: In some outputs, comments next to instructions (e.g., // ...*...) provide a visual representation of how instructions have been rescheduled relative to the original source.

  4. Enable software pipelining in SLOTHY

    main

    Software pipelining improves loop scheduling by interleaving instructions from different iterations. This allows SLOTHY to move instructions (like high-latency loads) to earlier or later iterations to hide stalls.

    To use this feature:

    1. Enable it via slothy.config.sw_pipelining.enabled = True.
    2. Use slothy.optimize_loop("label") where "label" is the start of the loop. SLOTHY will automatically detect the loop termination (e.g., a cbnz instruction pointing back to the label).
    3. Optionally configure preamble and postamble optimization using slothy.config.sw_pipelining.optimize_preamble and slothy.config.sw_pipelining.optimize_postamble. Setting these to False prevents SLOTHY from generating extra code for the first and last iterations, which can simplify the output for testing purposes.
    slothy.load_source_from_file("path/to/loop.s")

# Enable software pipelining
slothy.config.sw_pipelining.enabled = True

# Optional: Disable preamble/postamble optimization to simplify output
slothy.config.sw_pipelining.optimize_preamble = False
slothy.config.sw_pipelining.optimize_postamble = False

# Optimize the loop starting at the 'start' label
slothy.optimize_loop("start")

slothy.write_source_to_file("opt/optimized_loop.s")

  5. How SLOTHY optimizes assembly code

    main

    SLOTHY optimizes assembly by re-scheduling instructions to minimize CPU pipeline stalls. The process follows these steps:

    1. Internal Binary Search: Performs a search to find the minimal number of stalls possible for the given code and microarchitecture model.
    2. Constraint Solving: Invokes an external constraint solver (like OR-Tools CP-SAT) to find a valid instruction traversal that meets the stall objective.
    3. Transformation: Converts the optimized traversal of the Data Flow Graph (DFG) back into assembly code.
    4. Self-check: Verifies the optimization by transforming the output assembly back into a DFG and ensuring it is isomorphic to the input DFG (preserving semantics).

    Note on Determinism: Because SLOTHY uses a constraint solver, running the same optimization multiple times may produce different valid instruction schedules, provided they all achieve the same minimal number of stalls.

  6. Configure SLOTHY constraints for register allocation

    main

    When performing a preliminary pass to resolve symbolic registers into architectural registers (especially before using the splitting heuristic), you can restrict SLOTHY's optimization scope to make the problem manageable.

    Set the following in slothy.config.constraints:

    • functional_only = True: Disables microarchitectural constraints (like pipeline stalls).
    • allow_reordering = False: Disables instruction reordering constraints.

    This configuration forces SLOTHY to focus solely on finding a valid register allocation for the entire block of code.

  7. Understand address offset fixup in software pipelining

    main

    When SLOTHY performs software pipelining, it may reorder instructions relative to those that modify address registers (e.g., str q10, [x0], #4*16).

    To maintain correctness, SLOTHY performs address offset fixup: it automatically adjusts the immediate offsets in instructions (like ldr) that were moved across an address-modifying instruction. This ensures that even if a load is moved to a different iteration or position, it still accesses the correct memory location relative to the updated register value.

  8. Understand the scope of SLOTHY optimization

    main

    SLOTHY is a fixed-instruction super-optimizer, not a peephole optimizer. It does not perform instruction selection. Instead, it optimizes the following aspects of a given instruction sequence:

    • Register allocation
    • Instruction scheduling
    • Software pipelining

    It is the responsibility of the user or an upstream tool to map the workload to the target architecture before using SLOTHY. Because it focuses on optimization after instruction selection, it can be used in conjunction with other superoptimizers like souper or CryptOpt.

  9. How SLOTHY works: Fixed instruction superoptimization

    main

    SLOTHY is a fixed instruction superoptimizer. Unlike synthesizing superoptimizers that generate new instructions, SLOTHY takes existing assembly as input and produces semantically-equivalent optimized assembly using the same instructions and data flow. This ensures developer control over instruction selection, which is critical for performance and security (e.g., avoiding variable-time instructions in cryptography).

    SLOTHY performs three primary optimization tasks:

    1. Instruction Re-scheduling: Reorders instructions to hide latencies and maximize execution unit utilization.
    2. Register Renaming: Renames registers to enable better scheduling.
    3. Software Pipelining: Performs periodic loop interleaving.

    The Optimization Process:

    1. Lifting: The input assembly is lifted into a Data-Flow Graph (DFG) representing instruction dependencies.
    2. Constraint Generation: The DFG and microarchitectural details are converted into constraints.
    3. Solving: An external constraint solver (e.g., Google OR-tools) finds a traversal/lowering of the DFG that minimizes pipeline stalls. A valid solution assigns an execution index to each instruction and selects appropriate registers for outputs.

  11. Manual build requirements for SLOTHY artifact

    main

    If building locally without Docker, you must manage dependencies manually. The primary dependency is Google OR-Tools.

    To maintain a single source of truth for the SLOTHY repository across the test suites, use symlinks instead of git submodule for the following directory structure:

    * artifact
* |-- pqmx
*     |-- submodules
*         |-- slothy # symlink to slothy repository
* |-- pqax
*     |-- submodules
*         |-- slothy # symlink to slothy repository
* |-- slothy

  12. Reproduce, test, and benchmark paper results

    main
    For detailed instructions on how to reproduce the optimizations, validate functional correctness via tests, or evaluate performance on development boards as described in the CHES 2024 paper, refer to the specific guide located at slothy/paper/README.md within the SLOTHY repository or the artifact directory.