path: root/lib/CodeGen/RegAllocLinearScan.cpp

//===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a linear scan register allocator.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "regalloc"
#include "PhysRegTracker.h"
#include "VirtRegMap.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/Compiler.h"
#include <algorithm>
#include <set>
#include <queue>
#include <memory>
#include <cmath>
using namespace llvm;

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 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 RegisterRegAlloc
linearscanRegAlloc("linearscan", "linear scan register allocator",
                   createLinearScanRegisterAllocator);

namespace {
  struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass {
    static char ID;
    RALinScan() : MachineFunctionPass(&ID) {}

    typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
    typedef SmallVector<IntervalPtr, 32> IntervalPtrs;
  private:
    /// 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.
    EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
    DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;

    // NextReloadMap - For each register in the map, it maps to the another
    // register which