ICompiler

ICompiler

This wiki page documents the LLVM-based idempotent-code-generating compiler developed in the Vertical Research Group at UW-Madison.

Related Publications

M. de Kruijf and K. Sankaralingam. Idempotent Code Generation: Implementation, Analysis, and Evaluation. (Slides: pptx, pdf)
CGO '13: Code Generation and Optimization, 2013.

M. de Kruijf. Compiler Construction of Idempotent Regions and Applications in Architecture Design. (Slides: pptx, pdf)
PhD Thesis, University of Wisconsin-Madison, 2012.

M. de Kruijf, K. Sankaralingam, and S. Jha. Static Analysis and Compiler Design for Idempotent Processing. (Slides: pptx, pdf)
PLDI '12: Programming Language Design and Implementation, 2012.

J. Menon, M. de Kruijf, K. Sankaralingam, and S. Jha. iGPU: Exception Support and Speculative Execution on GPUs. (Slides: pptx)
ISCA '12: International Symposium on Computer Architecture, 2012.

M. de Kruijf, and K. Sankaralingam. Idempotent Processor Architecture. (Slides: pptx, pdf)
MICRO '11: International Symposium on Microarchitecture, 2011.

Source Code

The compiler source code, a fork from the LLVM HEAD (circa 02/2012), is available at http://github.com/mdekruijf/llvm:

Setup and Usage

The following instructions describe how to build idempotence-compiled binaries for x86 and ARM using the LLVM DragonEgg plug-in for GCC. The instructions assume a 64 bit x86 Linux host system.

1. Download the GitHub source code using Git and switch to the idempotence-extensions branch.

$ git clone https://github.com/mdekruijf/llvm.git
$ cd llvm
$ git checkout idempotence-extensions

2. Follow the LLVM Getting Started instructions for configuring and building the LLVM branch for your environment. Here is what you might do:

$ mkdir ../obj
$ cd ../obj
$ ../llvm/configure --prefix=[llvm install path]
$ make -j4 && make install -j4

3. Download and install GCC (I used GCC 4.6.1). Then use SVN to check-out LLVM DragonEgg (with the revision number corresponding with the point of the fork from LLVM) and build it setting the GCC variable to your installed gcc binary's path:

$ svn co http://llvm.org/svn/llvm-project/dragonegg/trunk ../dragonegg -r 149259
$ cd ../dragonegg
$ GCC=[gcc install path] LLVM_CONFIG=[llvm install path]/bin/llvm-config make

4. [OPTIONAL] To set up a version of GCC to cross-compile for ARM, repeat step 3 following the instructions in this thread. Be sure to apply the patch from the thread before building DragonEgg (ignore the fact that the patch doesn't apply cleanly on one file; it is harmless).

5. While you are free to manually compile programs through GCC using Dragon Egg and then feed bytecode through the LLVM toolchain, this handy shell script will do it all for you. It works as a drop-in GCC replacement for compiling SPEC 2006, Parboil, and a subset of the PARSEC benchmark suites. From this point on I will assume you have downloaded it and are going to use it. I will also assume you perform the recommended action of renaming it to idriver.sh for clarity (this wiki prohibits uploading files with a .sh extension).

$ mkdir ../idriver
$ cd ../idriver
$ wget http://www.cs.wisc.edu/vertical/wiki/uploads/ICompiler/ICompiler/idriver
$ mv idriver idriver.sh
$ chmod +x idriver.sh

6. Modify the idriver.sh file with your own values for the variables LLVM (your LLVM installation directory), x86_GCC (your gcc installation directory), and X86_DRAGONEGG (your dragonegg directory). For cross-compiling to ARM, do the same for ARM_DRAGONEGG and ARM_GCC_CROSS. You can also turn off debug output in the script by setting "__debug_lvl=0" and/or make other edits. You compile source code using idriver just as you would using gcc, e.g.:

$ idriver.sh /tmp/foo.c -o /tmp/foo

7. idriver.sh takes a number of idempotence-specific options:

  • --idempotence-construction=[none|size|speed|branch]:
    • none: Do not identify or mark boundaries between idempotent regions (default).
    • size: Identify and mark the boundaries between maximally-sized semantically idempotent regions.
    • speed: Insert boundaries sub-dividing regions to minimize register pressure.
    • branch: Insert boundaries sub-dividing regions to minimize branch misprediction re-execution costs.
  • --idempotence-preservation=[none|icf|vcf]:
    • none: Do not preserve the semantic idempotence of identified regions (default).
    • icf: Preserve the semantic idempotence of identified regions assuming invariable control flow on re-execution.
    • vcf: Preserve the semantic idempotence of identified regions assuming variable control flow on re-execution.
  • --idempotence-pressure-threshold=[1-10]:
    • For --idempotence-construction=speed, identify the threshold value that should be used to minimize pressure (default=5).
  • --idempotence-verify:
    • Run idempotence verification as part of the MachineVerifier pass (default=false).

Overview of Internal Operation

The vast majority of changes and additions to the LLVM source tree occur in the lib/CodeGen and include/llvm/CodeGen directories.

Core New Files

  • MemoryIdempotenceAnalysis[.h|.cpp]: This is an IR-level analysis pass that identifies the boundaries between semantically idempotent regions.
  • ConstructIdempotentRegions[.h|.cpp]: This is an IR-level transformation pass that simply reads the analysis results from MemoryIdempotenceAnalysis and inserts intrinsic instructions to mark the boundaries between regions.
  • MachineIdempotentRegions[.h|.cpp]: This is a machine-level analysis pass that exposes a machine-level idempotent region data structure and iterator structures used by other passes.
  • PatchMachineIdempotentRegions.cpp: This pass takes the IR-level idempotent region construction out of SSA form and prepares it for register allocation. It performs a number of tasks that are documented in the source code.
  • IdempotenceShadowIntervals[.h|.cpp]: This pass computes the shadow intervals of virtual registers. A shadow interval is the interval over which a virtual register must not be overwritten to preserve semantic idempotence.

Miscellaneous New Files

  • DivideMachineIdempotentRegions.cpp: This pass performs the work of --idempotence-construction=speed immediately prior to register allocation.
  • IdempotenceOptions[.h|.cpp]: Support for the different idempotence-specific flags.
  • IdempotenceUtils[.h|.cpp]: Miscellaneous utility functions.

Pass Structure (x86)

As output by llc -debug-pass=Structure:

[...]
Idempotence Analysis
Idempotent Region Construction
[...]
X86 DAG->DAG Instruction Selection [INTRINSICS LOWERED]
[...]
Peephole Optimizations
X86 Maximal Stack Alignment Check
Machine Idempotent Regions
Patch Machine Idempotent Regions
Verify generated machine code [CHECKS IDEMPOTENCE INVARIANTS]
Remove unreachable machine basic blocks
Live Variable Analysis
Eliminate PHI nodes for register allocation
Two-Address instruction pass
Process Implicit Definitions
Slot index numbering
Live Interval Analysis
Debug Variable Analysis
Machine Idempotent Regions
Idempotence Shadow Interval Analysis
Calculate spill weights
Divide Machine Idempotent Regions
Simple Register Coalescing [USES SHADOW INTERVALS]
Calculate spill weights
Live Stack Slot Analysis
Virtual Register Map
Bundle Machine CFG Edges
Spill Code Placement Analysis
Greedy Register Allocator [USES SHADOW INTERVALS]
Verify generated machine code [CHECKS IDEMPOTENCE INVARIANTS]
Stack Slot Coloring [USES SHADOW INTERVALS]
Verify generated machine code [CHECKS IDEMPOTENCE INVARIANTS]
X86 FP Stackifier
Verify generated machine code [CHECKS IDEMPOTENCE INVARIANTS]
Prolog/Epilog Insertion & Frame Finalization
Verify generated machine code [CHECKS IDEMPOTENCE INVARIANTS]
Control Flow Optimizer
[...]

For more information, please see the source code documentation and/or supporting documentation in the form of publications (see top of page).

Acknowledging LLVM

Without LLVM, this research product would not have been possible. Although the source code modifications to LLVM are relatively small (less than 5000 LOC), they are the product of multiple iterations and overhauls as concepts were refined and the LLVM back-end infrastructure improved. In the spirit of paying things forward, we hope this work relieves others of the burden of re-invention as well.