LLVM API Documentation

RegAllocLinearScan.cpp File Reference

#include "VirtRegMap.h"
#include "VirtRegRewriter.h"
#include "Spiller.h"
#include "llvm/Function.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterCoalescer.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <set>
#include <queue>
#include <memory>
#include <cmath>

Include dependency graph for RegAllocLinearScan.cpp:

Go to the source code of this file.

Defines

#define DEBUG_TYPE   "regalloc"

Functions

 STATISTIC (NumIters,"Number of iterations performed")
 STATISTIC (NumBacktracks,"Number of times we had to backtrack")
 STATISTIC (NumCoalesce,"Number of copies coalesced")
 STATISTIC (NumDowngrade,"Number of registers downgraded")
static
RALinScan::IntervalPtrs::iterator 
FindIntervalInVector (RALinScan::IntervalPtrs &IP, LiveInterval *LI)
static void RevertVectorIteratorsTo (RALinScan::IntervalPtrs &V, unsigned Point)
static void addStackInterval (LiveInterval *cur, LiveStacks *ls_, LiveIntervals *li_, MachineRegisterInfo *mri_, VirtRegMap &vrm_)
static float getConflictWeight (LiveInterval *cur, unsigned Reg, LiveIntervals *li_, MachineRegisterInfo *mri_, const MachineLoopInfo *loopInfo)
static bool weightsAreClose (float w1, float w2)
FunctionPass * llvm::createLinearScanRegisterAllocator ()

Variables

static cl::opt< bool > NewHeuristic ("new-spilling-heuristic", cl::desc("Use new spilling heuristic"), cl::init(false), cl::Hidden)
static cl::opt< bool > PreSplitIntervals ("pre-alloc-split", cl::desc("Pre-register allocation live interval splitting"), cl::init(false), cl::Hidden)
static cl::opt< bool > NewSpillFramework ("new-spill-framework", cl::desc("New spilling framework"), cl::init(false), cl::Hidden)
static RegisterRegAlloc linearscanRegAlloc ("linearscan","linear scan register allocator", createLinearScanRegisterAllocator)
static RegisterPass< RALinScan > X ("linearscan-regalloc","Linear Scan Register Allocator")


Define Documentation

#define DEBUG_TYPE   "regalloc"

Definition at line 14 of file RegAllocLinearScan.cpp.


Function Documentation

static void addStackInterval ( LiveInterval *  cur,
LiveStacks *  ls_,
LiveIntervals *  li_,
MachineRegisterInfo *  mri_,
VirtRegMap &  vrm_ 
) [static]

static RALinScan::IntervalPtrs::iterator FindIntervalInVector ( RALinScan::IntervalPtrs &  IP,
LiveInterval *  LI 
) [static]

static float getConflictWeight ( LiveInterval *  cur,
unsigned  Reg,
LiveIntervals *  li_,
MachineRegisterInfo *  mri_,
const MachineLoopInfo *  loopInfo 
) [static]

getConflictWeight - Return the number of conflicts between cur live interval and defs and uses of Reg weighted by loop depthes.

Definition at line 743 of file RegAllocLinearScan.cpp.

References E, llvm::LiveIntervals::getInstructionIndex(), llvm::MachineLoopInfo::getLoopDepth(), llvm::MachineInstr::getParent(), llvm::LiveInterval::liveAt(), MI, llvm::MachineRegisterInfo::reg_begin(), and llvm::MachineRegisterInfo::reg_end().

static void RevertVectorIteratorsTo ( RALinScan::IntervalPtrs &  V,
unsigned  Point 
) [static]

Definition at line 707 of file RegAllocLinearScan.cpp.

References llvm::SmallVectorImpl< T >::size().

STATISTIC ( NumDowngrade  ,
"Number of registers downgraded"   
)

STATISTIC ( NumCoalesce  ,
"Number of copies coalesced"   
)

STATISTIC ( NumBacktracks  ,
"Number of times we had to backtrack"   
)

STATISTIC ( NumIters  ,
"Number of iterations performed"   
)

static bool weightsAreClose ( float  w1,
float  w2 
) [static]

Definition at line 831 of file RegAllocLinearScan.cpp.

References NewHeuristic.


Variable Documentation

IntervalPtrs active_

active_ - Intervals that are currently being processed, and which have a live range active for the current point.

Definition at line 120 of file RegAllocLinearScan.cpp.

Definition at line 105 of file RegAllocLinearScan.cpp.

Definition at line 94 of file RegAllocLinearScan.cpp.

Definition at line 98 of file RegAllocLinearScan.cpp.

IntervalPtrs fixed_

fixed_ - Intervals that correspond to machine registers.

Definition at line 116 of file RegAllocLinearScan.cpp.

std::vector<LiveInterval*> handled_

handled_ - Intervals are added to the handled_ set in the order of their start value. This is uses for backtracking.

Definition at line 112 of file RegAllocLinearScan.cpp.

char ID [static]

Definition at line 75 of file RegAllocLinearScan.cpp.

IntervalPtrs inactive_

inactive_ - Intervals that are currently being processed, but which have a hold at the current point.

Definition at line 124 of file RegAllocLinearScan.cpp.

Definition at line 106 of file RegAllocLinearScan.cpp.

RegisterRegAlloc linearscanRegAlloc("linearscan","linear scan register allocator", createLinearScanRegisterAllocator) [static]

Definition at line 108 of file RegAllocLinearScan.cpp.

Definition at line 107 of file RegAllocLinearScan.cpp.

Definition at line 100 of file RegAllocLinearScan.cpp.

Definition at line 101 of file RegAllocLinearScan.cpp.

cl::opt<bool> NewHeuristic("new-spilling-heuristic", cl::desc("Use new spilling heuristic"), cl::init(false), cl::Hidden) [static]

Referenced by weightsAreClose().

cl::opt<bool> NewSpillFramework("new-spill-framework", cl::desc("New spilling framework"), cl::init(false), cl::Hidden) [static]

Definition at line 90 of file RegAllocLinearScan.cpp.

Definition at line 85 of file RegAllocLinearScan.cpp.

cl::opt<bool> PreSplitIntervals("pre-alloc-split", cl::desc("Pre-register allocation live interval splitting"), cl::init(false), cl::Hidden) [static]

regUse_ - Tracks register usage.

Definition at line 132 of file RegAllocLinearScan.cpp.

Definition at line 133 of file RegAllocLinearScan.cpp.

RelatedRegClasses - This structure is built the first time a function is compiled, and keeps track of which register classes have registers that belong to multiple classes or have aliases that are in other classes.

Definition at line 84 of file RegAllocLinearScan.cpp.

std::auto_ptr<VirtRegRewriter> rewriter_

Definition at line 138 of file RegAllocLinearScan.cpp.

std::auto_ptr<Spiller> spiller_

Definition at line 140 of file RegAllocLinearScan.cpp.

Definition at line 104 of file RegAllocLinearScan.cpp.

Definition at line 102 of file RegAllocLinearScan.cpp.

Definition at line 103 of file RegAllocLinearScan.cpp.

IntervalHeap unhandled_

Definition at line 129 of file RegAllocLinearScan.cpp.

vrm_ - Tracks register assignments.

Definition at line 136 of file RegAllocLinearScan.cpp.

RegisterPass<RALinScan> X("linearscan-regalloc","Linear Scan Register Allocator") [static]