path: root/lib/CodeGen/StackColoring.cpp

//===-- StackColoring.cpp -------------------------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass implements the stack-coloring optimization that looks for
// lifetime markers machine instructions (LIFESTART_BEGIN and LIFESTART_END),
// which represent the possible lifetime of stack slots. It attempts to
// merge disjoint stack slots and reduce the used stack space.
// NOTE: This pass is not StackSlotColoring, which optimizes spill slots.
//
// TODO: In the future we plan to improve stack coloring in the following ways:
// 1. Allow merging multiple small slots into a single larger slot at different
//    offsets.
// 2. Merge this pass with StackSlotColoring and allow merging of allocas with
//    spill slots.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "stackcoloring"
#include "llvm/CodeGen/Passes.h"
#include "MachineTraceMetrics.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SlotIndexes.h"
#include "llvm/DebugInfo.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Module.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegisterInfo.h"

using namespace llvm;

static cl::opt<bool>
DisableColoring("no-stack-coloring",
        cl::init(false), cl::Hidden,
        cl::desc("Disable stack coloring"));

/// The user may write code that uses allocas outside of the declared lifetime
/// zone. This can happen when the user returns a reference to a local
/// data-structure. We can detect these cases and decide not to optimize the
/// code. If this flag is enabled, we try to save the user.
static cl::opt<bool>
ProtectFromEscapedAllocas("protect-from-escaped-allocas",
        cl::init(false), cl::Hidden,
        cl::desc("Do not optimize lifetime zones that are broken"));

STATISTIC(NumMarkerSeen,  "Number of lifetime markers found.");
STATISTIC(StackSpaceSaved, "Number of bytes saved due to merging slots.");
STATISTIC(StackSlotMerged, "Number of stack slot merged.");
STATISTIC(EscapedAllocas,
          "Number of allocas that escaped the lifetime region");

//===----------------------------------------------------------------------===//
//                           StackColoring Pass
//===----------------------------------------------------------------------===//

namespace {
/// StackColoring - A machine pass for merging disjoint stack allocations,
/// marked by the LIFETIME_START and LIFETIME_END pseudo instructions.
class StackColoring : public MachineFunctionPass {
  MachineFrameInfo *MFI;
  MachineFunction *MF;

  /// A class representing liveness information for a single basic block.
  /// Each bit in the BitVector represents the liveness property
  /// for a different stack slot.
  struct BlockLifetimeInfo {
    /// Which slots BEGINs in each basic block.
    BitVector Begin;
    /// Which slots ENDs in each basic block.
    BitVector End;
    /// Which slots are marked as LIVE_IN, coming into each basic block.
    BitVector LiveIn;
    /// Which slots are marked as LIVE_OUT, coming out of each basic block.
    BitVector LiveOut;
  };

  /// Maps active slots (per bit) for each basic block.
  DenseMap<MachineBasicBlock*, BlockLifetimeInfo> BlockLiveness;

  /// Maps serial numbers to basic blocks.
  DenseMap<MachineBasicBlock*, int> BasicBlocks;
  /// Maps basic blocks to a serial number.
  SmallVector<MachineBasicBlock*, 8> BasicBlockNumbering;

  /// Maps liveness intervals for each slot.
  SmallVector<LiveInterval*, 16> Intervals;
  /// VNInfo is used for the construction of LiveIntervals.
  VNInfo::Allocator VNInfoAllocator;
  /// SlotIndex analysis object.
  SlotIndexes *Indexes;

  /// The list of lifetime markers found. These markers are to be removed
  /// once the coloring is done.
  SmallVector<MachineInstr*, 8> Markers;

  /// SlotSizeSorter - A Sort utility for arranging stack slots according
  /// to their size.
  struct SlotSizeSorter {
    MachineFrameInfo *MFI;
    SlotSizeSorter(MachineFrameInfo *mfi) : MFI(mfi) { }
    bool operator()(int LHS, int RHS) {
      // We use -1 to denote a uninteresting slot. Place these slots at the end.
      if (LHS == -1) return false;
      if (RHS == -1) return true;
      // Sort according to size.
      return MFI->getObjectSize(LHS) > MFI->getObjectSize(RHS);
  }
};

public:
  static char ID;
  StackColoring() : MachineFunctionPass(ID) {
    initializeStackColoringPass(*PassRegistry::getPassRegistry());
  }
  void getAnalysisUsage(AnalysisUsage &AU) const;
  bool runOnMachineFunction(MachineFunction &MF);

private:
  /// Debug.
  void dump();

  /// Removes all of the lifetime marker instructions from the function.
  /// \returns true if any markers were removed.
  bool removeAllMarkers();

  /// Scan the machine function and find all of the lifetime markers.
  /// Record the findings in the BEGIN and END vectors.
  /// \returns the number of markers found.
  unsigned collectMarkers(unsigned NumSlot);

  /// Perform the dataflow calculation and calculate the lifetime for each of
  /// the slots, based on the BEGIN/END vectors. Set the LifetimeLIVE_IN and
  /// LifetimeLIVE_OUT maps that represent which stack slots are live coming
  /// in and out blocks.
  void calculateLocalLiveness();

  /// Construct the LiveIntervals for the slots.
  void calculateLiveIntervals(unsigned NumSlots);

  /// Go over the machine function and change instructions which use stack
  /// slots to use the joint slots.
  void remapInstructions(DenseMap<int, int> &SlotRemap);

  /// The input program may contain intructions which are not inside lifetime
  /// markers. This can happen due to a bug in the compiler or due to a bug in
  /// user code (for example, returning a reference to a local variable).
  /// This procedure checks all of the instructions in the function and
  /// invalidates lifetime ranges which do not contain all of the instructions
  /// which access that frame slot.
  void removeInvalidSlotRanges();

  /// Map entries which point to other entries to their destination.
  ///   A->B->C becomes A->C.
   void expungeSlotMap(DenseMap<int, int> &SlotRemap, unsigned NumSlots);
};
} // end anonymous namespace

char StackColoring::ID = 0;
char &llvm::StackColoringID = StackColoring::ID;

INITIALIZE_PASS_BEGIN(StackColoring,
                   "stack-coloring", "Merge disjoint stack slots", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
INITIALIZE_PASS_END(StackColoring,
                   "stack-coloring", "Merge disjoint stack slots", false, false)

void StackColoring::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addRequired<MachineDominatorTree>();
  AU.addPreserved<MachineDominatorTree>();
  AU.addRequired<SlotIndexes>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

void StackColoring::dump() {
  for (df_iterator<MachineFunction*> FI = df_begin(MF), FE = df_end(MF);
       FI != FE; ++FI) {
    unsigned Num = BasicBlocks[*FI];
    DEBUG(dbgs()<<"Inspecting block #"<<Num<<" ["<<FI->getName()<<"]\n");
    Num = 0;
    DEBUG(dbgs()<<"BEGIN  : {");
    for (unsigned i=0; i < BlockLiveness[*FI].Begin.size(); ++i)
      DEBUG(dbgs()<<BlockLiveness[*FI].Begin.test</