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
OptionNameDirectory
-aa-evalExhaustive Alias Analysis Precision Evaluator
-anders-aaAndersen's Interprocedural Alias Analysis
-basicaaBasic Alias Analysis (default AA impl)
-basiccgBasic CallGraph Construction
-basicvnBasic Value Numbering (default GVN impl)
-callgraphPrint a call graph
-callsccPrint SCCs of the Call Graph
-cfgsccPrint SCCs of each function CFG
-count-aaCount Alias Analysis Query Responses
-debug-aaAA use debugger
-domfrontierDominance Frontier Construction
-domsetDominator Set Construction
-domtreeDominator Tree Construction
-etforestET Forest Construction
-externalfnconstantsPrint external fn callsites passed constants
-globalsmodref-aaSimple mod/ref analysis for globals
-idomImmediate Dominators Construction
-instcountCounts the various types of Instructions
-intervalsInterval Partition Construction
-load-vnLoad Value Numbering
-loopsNatural Loop Construction
-no-aaNo Alias Analysis (always returns 'may' alias)
-no-profileNo Profile Information
-postdomfrontierPost-Dominance Frontier Construction
-postdomsetPost-Dominator Set Construction
-postdomtreePost-Dominator Tree Construction
-postetforestPost-ET-Forest Construction
-postidomImmediate Post-Dominators Construction
-printPrint function to stderr
-print-alias-setsAlias Set Printer
-print-callgraphPrint Call Graph to 'dot' file
-print-cfgPrint CFG of function to 'dot' file
-print-cfg-onlyPrint CFG of function to 'dot' file (with no function bodies)
-printmPrint module to stderr
-printusedtypesFind Used Types
-profile-loaderLoad profile information from llvmprof.out
-scalar-evolutionScalar Evolution Analysis
-targetdataTarget Data Layout
TRANSFORM PASSES
OptionNameDirectory
-adceAggressive Dead Code Elimination
-argpromotionPromote 'by reference' arguments to scalars
-block-placementProfile Guided Basic Block Placement
-break-crit-edgesBreak Critical Edges in CFG
-ceeCorrelated Expression Elimination
-condpropConditional Propagation
-constmergeMerge Duplicate Global Constants
-constpropSimple constant propagation
-dceDead Code Elimination
-deadargelimDead Argument Elimination
-deadtypeelimDead Type Elimination
-dieDead Instruction Elimination
-dseDead Store Elimination
-gcseGlobal Common Subexpression Elimination
-globaldceDead Global Elimination
-globaloptGlobal Variable Optimizer
-indmemremIndirect Malloc and Free Removal
-indvarsCanonicalize Induction Variables
-inlineFunction Integration/Inlining
-insert-block-profilingInsert instrumentation for block profiling
-insert-edge-profilingInsert instrumentation for edge profiling
-insert-function-profilingInsert instrumentation for function profiling
-insert-null-profiling-rsMeasure profiling framework overhead
-insert-rs-profiling-frameworkInsert random sampling instrumentation framework
-instcombineCombine redundant instructions
-internalizeInternalize Global Symbols
-ipconstpropInterprocedural constant propagation
-ipsccpInterprocedural Sparse Conditional Constant Propagation
-lcssaLoop-Closed SSA Form Pass
-licmLoop Invariant Code Motion
-loop-extractExtract loops into new functions
-loop-extract-singleExtract at most one loop into a new function
-loop-reduceLoop Strength Reduction
-loop-unrollUnroll Loops
-loop-unswitchUnswitch Loops
-loopsimplifyCanonicalize Natural Loops
-lower-packedLower Packed Operations
-lowerallocsLower allocations from instructions to calls
-lowergcLower GC intrinsics, for GCless code generators
-lowerinvokeLower Invoke and Unwind
-lowerselectLower Selects To Branches
-lowersetjmpLower Set Jump
-lowerswitchLower SwitchInst's to branches
-mem2regPromote Memory to Register
-mergereturnUnify Function Exit Nodes
-predsimplifyPredicate Simplifier
-prune-ehRemove unused exception handling info
-raiseallocsRaise allocations from calls to instructions
-reassociateReassociate Expressions
-reg2memDemote Values to Memory
-scalarreplScalar Replacement of Aggregates
-sccpSparse Conditional Constant Propagation
-simplify-libcallsSimplify well-known library calls
-simplifycfgSimplify the CFG
-stripStrip all symbols from a module
-tailcallelimTail Call Elimination
-tailduplicateTail Duplication
UTILITY PASSES
OptionNameDirectory
-deadarghaX0rDead Argument Hacking (BUGPOINT ONLY)
-extract-blocksExtract Basic Blocks From Module (BUGPOINT ONLY)
-emitbytecodeBytecode Writer
-verifyModule 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.


Valid CSS! Valid HTML 4.01! Reid Spencer
LLVM Compiler Infrastructure
Last modified: $Date$