ShrinkWrapping.cpp

//===-- ShrinkWrapping.cpp - Reduce spills/restores of callee-saved regs --===//
//
//                     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 shrink wrapping variant of prolog/epilog insertion:
// - Spills and restores of callee-saved registers (CSRs) are placed in the
//   machine CFG to tightly surround their uses so that execution paths that
//   do not use CSRs do not pay the spill/restore penalty.
//
// - Avoiding placment of spills/restores in loops: if a CSR is used inside a
//   loop the spills are placed in the loop preheader, and restores are
//   placed in the loop exit nodes (the successors of loop _exiting_ nodes).
//
// - Covering paths without CSR uses:
//   If a region in a CFG uses CSRs and has multiple entry and/or exit points,
//   the use info for the CSRs inside the region is propagated outward in the
//   CFG to ensure validity of the spill/restore placements. This decreases
//   the effectiveness of shrink wrapping but does not require edge splitting
//   in the machine CFG.
//
// This shrink wrapping implementation uses an iterative analysis to determine
// which basic blocks require spills and restores for CSRs.
//
// This pass uses MachineDominators and MachineLoopInfo. Loop information
// is used to prevent placement of callee-saved register spills/restores
// in the bodies of loops.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "shrink-wrap"

#include "PrologEpilogInserter.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include <sstream>

using namespace llvm;

STATISTIC(numSRReduced, "Number of CSR spills+restores reduced.");

// Shrink Wrapping:
static cl::opt<bool>
ShrinkWrapping("shrink-wrap",
               cl::desc("Shrink wrap callee-saved register spills/restores"));

// Shrink wrap only the specified function, a debugging aid.
static cl::opt<std::string>
ShrinkWrapFunc("shrink-wrap-func", cl::Hidden,
               cl::desc("Shrink wrap the specified function"),
               cl::value_desc("funcname"),
               cl::init(""));

// Debugging level for shrink wrapping.
enum ShrinkWrapDebugLevel {
  None, BasicInfo, Iterations, Details
};

static cl::opt<enum ShrinkWrapDebugLevel>
ShrinkWrapDebugging("shrink-wrap-dbg", cl::Hidden,
  cl::desc("Print shrink wrapping debugging information"),
  cl::values(
    clEnumVal(None      , "disable debug output"),
    clEnumVal(BasicInfo , "print basic DF sets"),
    clEnumVal(Iterations, "print SR sets for each iteration"),
    clEnumVal(Details   , "print all DF sets"),
    clEnumValEnd));


void PEI::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesCFG();
  if (ShrinkWrapping || ShrinkWrapFunc != "") {
    AU.addRequired<MachineLoopInfo>();
    AU.addRequired<MachineDominatorTree>();
  }
  AU.addPreserved<MachineLoopInfo>();
  AU.addPreserved<MachineDominatorTree>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

//===----------------------------------------------------------------------===//
//  ShrinkWrapping implementation
//===----------------------------------------------------------------------===//

// Convienences for dealing with machine loops.
MachineBasicBlock* PEI::getTopLevelLoopPreheader(MachineLoop* LP) {
  assert(LP && "Machine loop is NULL.");
  MachineBasicBlock* PHDR = LP->getLoopPreheader();
  MachineLoop* PLP = LP->getParentLoop();
  while (PLP) {
    PHDR = PLP->getLoopPreheader();
    PLP = PLP->getParentLoop();
  }
  return PHDR;
}

MachineLoop* PEI::getTopLevelLoopParent(MachineLoop *LP) {
  if (LP == 0)
    return 0;
  MachineLoop* PLP = LP->getParentLoop();
  while (PLP) {
    LP = PLP;
    PLP = PLP->getParentLoop();
  }
  return LP;
}

bool PEI::isReturnBlock(MachineBasicBlock* MBB) {
  return (MBB && !MBB->empty() && MBB->back().getDesc().isReturn());
}

// Initialize shrink wrapping DFA sets, called before iterations.
void PEI::clearAnticAvailSets() {
  AnticIn.clear();
  AnticOut.clear();
  AvailIn.clear();
  AvailOut.clear();
}

// Clear all sets constructed by shrink wrapping.
void PEI::clearAllSets() {
  ReturnBlocks.clear();
  clearAnticAvailSets();
  UsedCSRegs.clear();
  CSRUsed.clear();
  TLLoops.clear();
  CSRSave.clear();
  CSRRestore.clear();
}

// Initialize all shrink wrapping data.
void PEI::initShrinkWrappingInfo() {
  clearAllSets();
  EntryBlock = 0;
#ifndef NDEBUG
  HasFastExitPath = false;
#endif
  ShrinkWrapThisFunction = ShrinkWrapping;
  // DEBUG: enable or disable shrink wrapping for the current function
  // via --shrink-wrap-func=<funcname>.
#ifndef NDEBUG
  if (ShrinkWrapFunc != "") {
    std::string MFName = MF->getFunction()->getName();
    ShrinkWrapThisFunction = (MFName == ShrinkWrapFunc);
  }
#endif
}


/// placeCSRSpillsAndRestores - determine which MBBs of the function
/// need save, restore code for callee-saved registers by doing a DF analysis
/// similar to the one used in code motion (GVNPRE). This produces maps of MBBs
/// to sets of registers (CSRs) for saves and restores. MachineLoopInfo
/// is used to ensure that CSR save/restore code is not placed inside loops.
/// This function computes the maps of MBBs -> CSRs to spill and restore
/// in CSRSave, CSRRestore.
///
/// If shrink wrapping is not being performed, place all spills in
/// the entry block, all restores in return blocks. In this case,
/// CSRSave has a single mapping, CSRRestore has mappings for each
/// return block.
///
void PEI::placeCSRSpillsAndRestores(MachineFunction &Fn) {

  DEBUG(MF = &Fn);

  initShrinkWrappingInfo();

  DEBUG(if (ShrinkWrapThisFunction) {
      DOUT << "Place CSR spills/restores for "
           << MF->getFunction()->getName() << "\n";
    });

  if (calculateSets(Fn))
    placeSpillsAndRestores(Fn);
}

/// calcAnticInOut - calculate the anticipated in/out reg sets
/// for the given MBB by looking forward in the MCFG at MBB's
/// successors.
///
bool PEI::calcAnticInOut(MachineBasicBlock* MBB) {