LLVM's Analysis and Transform Passes

1. Introduction
2. Analysis Passes
3. Transform Passes
4. Utility Passes

Written by Reid Spencer

Introduction

This document serves as a high level summary of the optimization features that LLVM provides. Optimizations are implemented as Passes that traverse some portion of a program to either collect information or transform the program. THe table below divides the passes that LLVM provides into three categories. Analysis passes compute information that other passes can use or for debugging or program visualization purposes. Transform passes can use (or invalidate) the analysis passes. Transform passes all mutate the program in some way. Utility passes provides ome utility but don't otherwise fit categorization. For example passes to extract functions to bytecode or write a module to bytecode are neither analysis nor transform passes.

The table below provides a quick summary of each pass and links to the more complete pass description later in the document.

ANALYSIS PASSES
Option | Name | Directory
--- | --- | ---
-aa-eval | Exhaustive Alias Analysis Precision Evaluator
-anders-aa | Andersen's Interprocedural Alias Analysis
-basicaa | Basic Alias Analysis (default AA impl)
-basiccg | Basic CallGraph Construction
-basicvn | Basic Value Numbering (default GVN impl)
-callgraph | Print a call graph
-callscc | Print SCCs of the Call Graph
-cfgscc | Print SCCs of each function CFG
-count-aa | Count Alias Analysis Query Responses
-debug-aa | AA use debugger
-domfrontier | Dominance Frontier Construction
-domset | Dominator Set Construction
-domtree | Dominator Tree Construction
-etforest | ET Forest Construction
-externalfnconstants | Print external fn callsites passed constants
-globalsmodref-aa | Simple mod/ref analysis for globals
-idom | Immediate Dominators Construction
-instcount | Counts the various types of Instructions
-intervals | Interval Partition Construction
-load-vn | Load Value Numbering
-loops | Natural Loop Construction
-no-aa | No Alias Analysis (always returns 'may' alias)
-no-profile | No Profile Information
-postdomfrontier | Post-Dominance Frontier Construction
-postdomset | Post-Dominator Set Construction
-postdomtree | Post-Dominator Tree Construction
-postetforest | Post-ET-Forest Construction
-postidom | Immediate Post-Dominators Construction
-print | Print function to stderr
-print-alias-sets | Alias Set Printer
-print-callgraph | Print Call Graph to 'dot' file
-print-cfg | Print CFG of function to 'dot' file
-print-cfg-only | Print CFG of function to 'dot' file (with no function bodies)
-printm | Print module to stderr
-printusedtypes | Find Used Types
-profile-loader | Load profile information from llvmprof.out
-scalar-evolution | Scalar Evolution Analysis
-targetdata | Target Data Layout
TRANSFORM PASSES
Option | Name | Directory
-adce | Aggressive Dead Code Elimination
-argpromotion | Promote 'by reference' arguments to scalars
-block-placement | Profile Guided Basic Block Placement
-break-crit-edges | Break Critical Edges in CFG
-cee | Correlated Expression Elimination
-condprop | Conditional Propagation
-constmerge | Merge Duplicate Global Constants
-constprop | Simple constant propagation
-dce | Dead Code Elimination
-deadargelim | Dead Argument Elimination
-deadtypeelim | Dead Type Elimination
-die | Dead Instruction Elimination
-dse | Dead Store Elimination
-gcse | Global Common Subexpression Elimination
-globaldce | Dead Global Elimination
-globalopt | Global Variable Optimizer
-indmemrem | Indirect Malloc and Free Removal
-indvars | Canonicalize Induction Variables
-inline | Function Integration/Inlining
-insert-block-profiling | Insert instrumentation for block profiling
-insert-edge-profiling | Insert instrumentation for edge profiling
-insert-function-profiling | Insert instrumentation for function profiling
-insert-null-profiling-rs | Measure profiling framework overhead
-insert-rs-profiling-framework | Insert random sampling instrumentation framework
-instcombine | Combine redundant instructions
-internalize | Internalize Global Symbols
-ipconstprop | Interprocedural constant propagation
-ipsccp | Interprocedural Sparse Conditional Constant Propagation
-lcssa | Loop-Closed SSA Form Pass
-licm | Loop Invariant Code Motion
-loop-extract | Extract loops into new functions
-loop-extract-single | Extract at most one loop into a new function
-loop-reduce | Loop Strength Reduction
-loop-unroll | Unroll Loops
-loop-unswitch | Unswitch Loops
-loopsimplify | Canonicalize Natural Loops
-lower-packed | Lower Packed Operations
-lowerallocs | Lower allocations from instructions to calls
-lowergc | Lower GC intrinsics, for GCless code generators
-lowerinvoke | Lower Invoke and Unwind
-lowerselect | Lower Selects To Branches
-lowersetjmp | Lower Set Jump
-lowerswitch | Lower SwitchInst's to branches
-mem2reg | Promote Memory to Register
-mergereturn | Unify Function Exit Nodes
-predsimplify | Predicate Simplifier
-prune-eh | Remove unused exception handling info
-raiseallocs | Raise allocations from calls to instructions
-reassociate | Reassociate Expressions
-reg2mem | Demote Values to Memory
-scalarrepl | Scalar Replacement of Aggregates
-sccp | Sparse Conditional Constant Propagation
-simplify-libcalls | Simplify well-known library calls
-simplifycfg | Simplify the CFG
-strip | Strip all symbols from a module
-tailcallelim | Tail Call Elimination
-tailduplicate | Tail Duplication
UTILITY PASSES
Option | Name | Directory
-deadarghaX0r | Dead Argument Hacking (BUGPOINT ONLY)
-extract-blocks | Extract Basic Blocks From Module (BUGPOINT ONLY)
-emitbytecode | Bytecode Writer
-verify | Module Verifier

Analysis Passes

This section describes the LLVM Analysis Passes.

Exhaustive Alias Analysis Precision Evaluator

Yet to be written.

Andersen's Interprocedural Alias Analysis

Yet to be written.

Basic Alias Analysis

Yet to be written.

Basic Call Graph Construction

Yet to be written.

Basic Value Numbering

Yet to be written.

Print Call Graph

Yet to be written.

Print SCCs of the Call Graph

Yet to be written.

Print SCCs of each Function Control Flow Graph

Yet to be written.

Count Alias Analysis Query Responses

Yet to be written.

Alias Analysis Usage Debugger

Yet to be written.

Dominance Frontier Construction

Yet to be written.

Dominator Set Construction

Yet to be written.

Dominator Tree Construction

Yet to be written.

ET Forest Construction

Yet to be written.

Basic Value Numbering

Yet to be written.

Print external fn callsites passed constants

Yet to be written.

Simple mod/ref analysis for globals

Yet to be written.

Immediate Dominators Construction

Yet to be written.

Counts the various types of Instructions

Yet to be written.

Interval Partition Construction

Yet to be written.

Load Value Numbering

Yet to be written.

Natural Loop Construction

Yet to be written.

No Alias Analysis (always returns 'may' alias)

Yet to be written.

No Profile Information

Yet to be written.

Post-Dominance Frontier Construction

Yet to be written.

Post-Dominator Set Construction

Yet to be written.

Post-Dominator Tree Construction

Yet to be written.

Post-ET-Forest Construction

Yet to be written.

Immediate Post-Dominators Construction

Yet to be written.

Print function to stderr

Yet to be written.

Alias Set Printer

Yet to be written.

Print Call Graph to 'dot' file

Yet to be written.

Print CFG of function to 'dot' file

Yet to be written.

Print CFG of function to 'dot' file (with no function bodies)

Yet to be written.

Print module to stderr

Yet to be written.

Find Used Types

Yet to be written.

Load profile information from llvmprof.out

Yet to be written.

Scalar Evolution Analysis

Yet to be written.

Target Data Layout

Yet to be written.

Transform Passes

This section describes the LLVM Transform Passes.

Aggressive Dead Code Elimination

ADCE aggressively tries to eliminate code. This pass is similar to DCE but it assumes that values are dead until proven otherwise. This is similar to SCCP, except applied to the liveness of values.

Promote 'by reference' arguments to scalars

Yet to be written.

Profile Guided Basic Block Placement

This pass implements a very simple profile guided basic block placement algorithm. The idea is to put frequently executed blocks together at the start of the function, and hopefully increase the number of fall-through conditional branches. If there is no profile information for a particular function, this pass basically orders blocks in depth-first order.

The algorithm implemented here is basically "Algo1" from "Profile Guided Code Positioning" by Pettis and Hansen, except that it uses basic block counts instead of edge counts. This could be improved in many ways, but is very simple for now.

Basically we "place" the entry block, then loop over all successors in a DFO, placing the most frequently executed successor until we run out of blocks. Did we mention that this was extremely simplistic? This is also much slower than it could be. When it becomes important, this pass will be rewritten to use a better algorithm, and then we can worry about efficiency.

Break Critical Edges in CFG

Yet to be written.

Correlated Expression Elimination

Correlated Expression Elimination propagates information from conditional branches to blocks dominated by destinations of the branch. It propagates information from the condition check itself into the body of the branch, allowing transformations like these for example:

        if (i == 7)
          ... 4*i;  // constant propagation

        M = i+1; N = j+1;
        if (i == j)
          X = M-N;  // = M-M == 0;

This is called Correlated Expression Elimination because we eliminate or simplify expressions that are correlated with the direction of a branch. In this way we use static information to give us some information about the dynamic value of a variable.

Conditional Propagation

This pass propagates information about conditional expressions through the program, allowing it to eliminate conditional branches in some cases.

Merge Duplicate Global Constants

Yet to be written.

Constant Propagation

This file implements constant propagation and merging. It looks for instructions involving only constant operands and replaces them with a constant value instead of an instruction. For example:

    add i32 1, 2

becomes

    i32 3

NOTE: this pass has a habit of making definitions be dead. It is a good idea to to run a DIE (Dead Instruction Elimination) pass sometime after running this pass.

Dead Code Elimination

Yet to be written.

Dead Argument Elimination

Yet to be written.

Dead Type Elimination

Yet to be written.

Dead Instruction Elimination

Yet to be written.

Dead Store Elimination

Yet to be written.

Global Common Subexpression Elimination

Yet to be written.

Dead Global Elimination

Yet to be written.

Global Variable Optimizer

Yet to be written.

Indirect Malloc and Free Removal

Yet to be written.

Canonicalize Induction Variables

Yet to be written.

Function Integration/Inlining

Yet to be written.

Insert instrumentation for block profiling

Yet to be written.

Insert instrumentation for edge profiling

Yet to be written.

Insert instrumentation for function profiling

Yet to be written.

Measure profiling framework overhead

Yet to be written.

Insert random sampling instrumentation framework

Yet to be written.

Combine redundant instructions

Yet to be written.

Internalize Global Symbols

Yet to be written.

Interprocedural constant propagation

Yet to be written.

Interprocedural Sparse Conditional Constant Propagation

Yet to be written.

Loop-Closed SSA Form Pass

Yet to be written.

Loop Invariant Code Motion

Yet to be written.

Extract loops into new functions

Yet to be written.

Extract at most one loop into a new function

Yet to be written.

Loop Strength Reduction

Yet to be written.

Unroll Loops

Yet to be written.

Unswitch Loops

Yet to be written.

Canonicalize Natural Loops

Yet to be written.

Lower Packed Operations

Yet to be written.

Lower allocations from instructions to calls

Yet to be written.

Lower GC intrinsics, for GCless code generators

Yet to be written.

Lower Invoke and Unwind

Yet to be written.

Lower Selects To Branches

Yet to be written.

Lower Set Jump

Yet to be written.

Lower SwitchInst's to branches

Yet to be written.

Promote Memory to Register

Yet to be written.

Unify Function Exit Nodes

Yet to be written.

Predicate Simplifier

Yet to be written.

Remove unused exception handling info

Yet to be written.

Raise allocations from calls to instructions

Yet to be written.

Reassociate Expressions

Yet to be written.

Demote Values to Memory

Yet to be written.

Scalar Replacement of Aggregates

Yet to be written.

Sparse Conditional Constant Propagation

Yet to be written.

Simplify well-known library calls

Yet to be written.

Simplify the CFG

Yet to be written.

Strip all symbols from a module

Yet to be written.

Tail Call Elimination

Yet to be written.

Tail Duplication

Yet to be written.

Utility Passes

This section describes the LLVM Utility Passes.

Dead Argument Hacking (BUGPOINT ONLY)

Yet to be written.

Extract Basic Blocks From Module (BUGPOINT ONLY)

Yet to be written.

Bytecode Writer

Yet to be written.

Module Verifier

Yet to be written.