Dynamic Structure Prefetching

This repository contains the Dynamic Structure Prefetching LLVM pass. This implements a compile-time method to prefetch elements of dynamic structures traversed within loops that may modify the structure itself.

Requirements

• CMake 3.10 or newer.
• An LLVM installation that provides CMake package files for find_package(LLVM CONFIG). The build has been verified with LLVM 16.0.0.
• clang and clang++ as the compiler toolchain. The project is verified to build with Clang 16.0.0, but other Clang versions may work as well.
• spdlog for optional logging. If it is not found, the pass builds with logging compiled out. You can also force that mode with -DDSP_ENABLE_SPDLOG=OFF.
• Depending on how LLVM is packaged on your system, CMake may also need LLVM's system dependencies such as terminfo, zlib, zstd, and libxml2.

Building the compiler pass

Suggested build sequence, adapt to fit your environment

CC=clang CXX=clang++ cmake -S . -B build -DCMAKE_INSTALL_PREFIX=<prefix>
cmake --build build --target install

Using the compiler pass

Using (applying) the compiler pass to compile and optimize source.c to an executable named binary consists of the following stages.

First, build the LLVM IR and apply initial optimizations.

clang -O3 -emit-llvm source.c -S -o ir.ll
opt -O3 ir.ll -S -o opt_ir.ll

Then, apply the compiler pass and optimize again.

opt -enable-new-pm=0 -unify-loop-exits -load path/to/libDynamicStructurePrefetchingPass.so --dynamicStructurePrefetchingPass -target-identification=heuristic opt_ir.ll -S -o pass_ir.ll
opt -O3 pass_ir.ll -S -o opt_pass_ir.ll

Flags for the compiler pass:

• -target-identification - Target identification method (heuristic (default), annotatedIR)
• -enable-debug-logging - Enable debug-level logging
• -dump-detailed-phi-failures - Emit detailed PHI state dump on validation failure

Finally, build the executable

clang -O3 opt_pass_ir.ll -o binary