path: root/include/llvm/CodeGen/LiveIntervalAnalysis.h

//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the LiveInterval analysis pass.  Given some numbering of
// each the machine instructions (in this implemention depth-first order) an
// interval [i, j) is said to be a live interval for register v if there is no
// instruction with number j' > j such that v is live at j' and there is no
// instruction with number i' < i such that v is live at i'. In this
// implementation intervals can have holes, i.e. an interval might look like
// [1,20), [50,65), [1000,1001).
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H

#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Allocator.h"
#include <cmath>

namespace llvm {

  class AliasAnalysis;
  class LiveVariables;
  class MachineLoopInfo;
  class TargetRegisterInfo;
  class MachineRegisterInfo;
  class TargetInstrInfo;
  class TargetRegisterClass;
  class VirtRegMap;
  typedef std::pair<unsigned, MachineBasicBlock*> IdxMBBPair;

  inline bool operator<(unsigned V, const IdxMBBPair &IM) {
    return V < IM.first;
  }

  inline bool operator<(const IdxMBBPair &IM, unsigned V) {
    return IM.first < V;
  }

  struct Idx2MBBCompare {
    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const {
      return LHS.first < RHS.first;
    }
  };
  
  class LiveIntervals : public MachineFunctionPass {
    MachineFunction* mf_;
    MachineRegisterInfo* mri_;
    const TargetMachine* tm_;
    const TargetRegisterInfo* tri_;
    const TargetInstrInfo* tii_;
    AliasAnalysis *aa_;
    LiveVariables* lv_;

    /// Special pool allocator for VNInfo's (LiveInterval val#).
    ///
    BumpPtrAllocator VNInfoAllocator;

    /// MBB2IdxMap - The indexes of the first and last instructions in the
    /// specified basic block.
    std::vector<std::pair<unsigned, unsigned> > MBB2IdxMap;

    /// Idx2MBBMap - Sorted list of pairs of index of first instruction
    /// and MBB id.
    std::vector<IdxMBBPair> Idx2MBBMap;

    /// FunctionSize - The number of instructions present in the function
    uint64_t FunctionSize;

    typedef DenseMap<const MachineInstr*, unsigned> Mi2IndexMap;
    Mi2IndexMap mi2iMap_;

    typedef std::vector<MachineInstr*> Index2MiMap;
    Index2MiMap i2miMap_;

    typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
    Reg2IntervalMap r2iMap_;

    DenseMap<MachineBasicBlock*, unsigned> terminatorGaps;

    BitVector allocatableRegs_;

    std::vector<MachineInstr*> ClonedMIs;

    typedef LiveInterval::InstrSlots InstrSlots;

  public:
    static char ID; // Pass identification, replacement for typeid
    LiveIntervals() : MachineFunctionPass(&ID) {}

    static unsigned getBaseIndex(unsigned index) {
      return index - (index % InstrSlots::NUM);
    }
    static unsigned getBoundaryIndex(unsigned index) {
      return getBaseIndex(index + InstrSlots::NUM - 1);
    }
    static unsigned getLoadIndex(unsigned index) {
      return getBaseIndex(index) + InstrSlots::LOAD;
    }
    static unsigned getUseIndex(unsigned index) {
      return getBaseIndex(index) + InstrSlots::USE;
    }
    static unsigned getDefIndex(unsigned index) {
      return getBaseIndex(index) + InstrSlots::DEF;
    }
    static unsigned getStoreIndex(unsigned index) {
      return getBaseIndex(index) + InstrSlots::STORE;
    }

    static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
      return (isDef + isUse) * powf(10.0F, (float)loopDepth);
    }

    typedef Reg2IntervalMap::iterator iterator;
    typedef Reg2IntervalMap::const_iterator const_iterator;
    const_iterator begin() const { return r2iMap_.begin(); }
    const_iterator end() const { return r2iMap_.end(); }
    iterator begin() { return r2iMap_.begin(); }
    iterator end() { return r2iMap_.end(); }
    unsigned getNumIntervals() const { return (unsigned)r2iMap_.size(); }

    LiveInterval &getInterval(unsigned reg) {
      Reg2IntervalMap::iterator I = r2iMap_.find(reg);
      assert(I != r2iMap_.end() && "Interval does not exist for register");
      return *I->second;
    }

    const LiveInterval &getInterval(unsigned reg) const {
      Reg2IntervalMap::const_iterator I = r2iMap_.find(reg);
      assert(I != r2iMap_.end() && "Interval does not exist for register");
      return *I->second;
    }

    bool hasInterval(unsigned reg) const {
      return r2iMap_.count(reg);
    }

    /// getMBBStartIdx - Return the base index of the first instruction in the
    /// specified MachineBasicBlock.
    unsigned getMBBStartIdx(MachineBasicBlock *MBB) const {
      return getMBBStartIdx(MBB->getNumber());
    }
    unsigned getMBBStartIdx(unsigned MBBNo) const {
      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
      return MBB2IdxMap[MBBNo].first;
    }

    /// getMBBEndIdx - Return the store index of the last instruction in the
    /// specified MachineBasicBlock.
    unsigned getMBBEndIdx(MachineBasicBlock *MBB) const {
      return getMBBEndIdx(MBB->getNumber());
    }
    unsigned getMBBEndIdx(unsigned MBBNo) const {
      assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!");
      return MBB2IdxMap[MBBNo].second;
    }

    /// getScaledIntervalSize - get the size of an interval in "units,"
    /// where every function is composed of one thousand units.  This
    /// measure scales properly with empty index slots in the function.
    double getScaledIntervalSize(LiveInterval& I) {
      return (1000.0 / InstrSlots::NUM * I.getSize()) / i2miMap_.size();
    }
    
    /// getApproximateInstructionCount - computes an estimate of the number
    /// of instructions in a given LiveInterval.
    unsigned getApproximateInstructionCount(LiveInterval& I) {
      double IntervalPercentage = getScaledIntervalSize(I) / 1000.0;
      return (unsigned)(IntervalPercentage * FunctionSize);
    }

    /// getMBBFromIndex - given an index in any instruction of an
    /// MBB return a pointer the MBB
    MachineBasicBlock* getMBBFromIndex(unsigned index) const {
      std::vector<IdxMBBPair>::const_iterator I =
        std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), index);
      // Take the pair containing the index
      std::vector<IdxMBBPair>::const_iterator J =
        ((I != Idx2MBBMap.end() && I->first > index) ||
         (I == Idx2MBBMap.end() && Idx2MBBMap.size()>0)) ? (I-1): I;

      assert(J != Idx2MBBMap.end() && J->first < index+1 &&
             index <= getMBBEndIdx(J->second) &&
             "index does not correspond to an MBB");
      return J->second;
    }

    /// getInstructionIndex - returns the base index of instr
    unsigned getInstructionIndex(const MachineInstr