InlineSpiller.cpp

//===-------- InlineSpiller.cpp - Insert spills and restores inline -------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// The inline spiller modifies the machine function directly instead of
// inserting spills and restores in VirtRegMap.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "regalloc"
#include "Spiller.h"
#include "LiveRangeEdit.h"
#include "VirtRegMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/TinyPtrVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

STATISTIC(NumSpilledRanges,   "Number of spilled live ranges");
STATISTIC(NumSnippets,        "Number of spilled snippets");
STATISTIC(NumSpills,          "Number of spills inserted");
STATISTIC(NumSpillsRemoved,   "Number of spills removed");
STATISTIC(NumReloads,         "Number of reloads inserted");
STATISTIC(NumReloadsRemoved,  "Number of reloads removed");
STATISTIC(NumFolded,          "Number of folded stack accesses");
STATISTIC(NumFoldedLoads,     "Number of folded loads");
STATISTIC(NumRemats,          "Number of rematerialized defs for spilling");
STATISTIC(NumOmitReloadSpill, "Number of omitted spills of reloads");
STATISTIC(NumHoists,          "Number of hoisted spills");

namespace {
class InlineSpiller : public Spiller {
  MachineFunctionPass &Pass;
  MachineFunction &MF;
  LiveIntervals &LIS;
  LiveStacks &LSS;
  AliasAnalysis *AA;
  MachineDominatorTree &MDT;
  MachineLoopInfo &Loops;
  VirtRegMap &VRM;
  MachineFrameInfo &MFI;
  MachineRegisterInfo &MRI;
  const TargetInstrInfo &TII;
  const TargetRegisterInfo &TRI;

  // Variables that are valid during spill(), but used by multiple methods.
  LiveRangeEdit *Edit;
  LiveInterval *StackInt;
  int StackSlot;
  unsigned Original;

  // All registers to spill to StackSlot, including the main register.
  SmallVector<unsigned, 8> RegsToSpill;

  // All COPY instructions to/from snippets.
  // They are ignored since both operands refer to the same stack slot.
  SmallPtrSet<MachineInstr*, 8> SnippetCopies;

  // Values that failed to remat at some point.
  SmallPtrSet<VNInfo*, 8> UsedValues;

public:
  // Information about a value that was defined by a copy from a sibling
  // register.
  struct SibValueInfo {
    // True when all reaching defs were reloads: No spill is necessary.
    bool AllDefsAreReloads;

    // True when value is defined by an original PHI not from splitting.
    bool DefByOrigPHI;

    // The preferred register to spill.
    unsigned SpillReg;

    // The value of SpillReg that should be spilled.
    VNInfo *SpillVNI;

    // The block where SpillVNI should be spilled. Currently, this must be the
    // block containing SpillVNI->def.
    MachineBasicBlock *SpillMBB;

    // A defining instruction that is not a sibling copy or a reload, or NULL.
    // This can be used as a template for rematerialization.
    MachineInstr *DefMI;

    // List of values that depend on this one.  These values are actually the
    // same, but live range splitting has placed them in different registers,
    // or SSA update needed to insert PHI-defs to preserve SSA form.  This is
    // copies of the current value and phi-kills.  Usually only phi-kills cause
    // more than one dependent value.
    TinyPtrVector<VNInfo*> Deps;

    SibValueInfo(unsigned Reg, VNInfo *VNI)
      : AllDefsAreReloads(true), DefByOrigPHI(false),
        SpillReg(Reg), SpillVNI(VNI), SpillMBB(0), DefMI(0) {}

    // Returns true when a def has been found.
    bool hasDef() const { return DefByOrigPHI || DefMI; }
  };

private:
  // Values in RegsToSpill defined by sibling copies.
  typedef DenseMap<VNInfo*, SibValueInfo> SibValueMap;
  SibValueMap SibValues;

  // Dead defs generated during spilling.
  SmallVector<MachineInstr*, 8> DeadDefs;

  ~InlineSpiller() {}

public:
  InlineSpiller(MachineFunctionPass &pass,
                MachineFunction &mf,
                VirtRegMap &vrm)
    : Pass(pass),
      MF(mf),
      LIS(pass.getAnalysis<LiveIntervals>()),
      LSS(pass.getAnalysis<LiveStacks>()),
      AA(&pass.getAnalysis<AliasAnalysis>()),
      MDT(pass.getAnalysis<MachineDominatorTree>()),
      Loops(pass.getAnalysis<MachineLoopInfo>()),
      VRM(vrm),
      MFI(*mf.getFrameInfo()),
      MRI(mf.getRegInfo()),
      TII(*mf.getTarget().getInstrInfo()),
      TRI(*mf.getTarget().getRegisterInfo()) {}

  void spill(LiveRangeEdit &);

private:
  bool isSnippet(const LiveInterval &SnipLI);
  void collectRegsToSpill();

  bool isRegToSpill(unsigned Reg) {
    return std::find(RegsToSpill.begin(),
                     RegsToSpill.end(), Reg) != RegsToSpill.end();
  }

  bool isSibling(unsigned Reg);
  MachineInstr *traceSiblingValue(unsigned, VNInfo*, VNInfo*);
  void propagateSiblingValue(SibValueMap::iterator, VNInfo *VNI = 0);
  void analyzeSiblingValues();

  bool hoistSpill(LiveInterval &SpillLI, MachineInstr *CopyMI);
  void eliminateRedundantSpills(LiveInterval &LI, VNInfo *VNI);

  void markValueUsed(LiveInterval*, VNInfo*);
  bool reMaterializeFor(LiveInterval&, MachineBasicBlock::iterator MI);
  void reMaterializeAll();

  bool coalesceStackAccess(MachineInstr *MI, unsigned Reg);
  bool foldMemoryOperand(MachineBasicBlock::iterator MI,
                         const SmallVectorImpl<unsigned> &Ops,
                         MachineInstr *LoadMI = 0);
  void insertReload(LiveInterval &NewLI, SlotIndex,
                    MachineBasicBlock::iterator MI);
  void insertSpill(LiveInterval &NewLI, const LiveInterval &OldLI,
                   SlotIndex, MachineBasicBlock::iterator MI);

  void spillAroundUses(unsigned Reg);
  void spillAll();
};
}

namespace llvm {
Spiller *createInlineSpiller(MachineFunctionPass &pass,
                             MachineFunction &mf,
                             VirtRegMap &vrm) {
  return new InlineSpiller(pass, mf, vrm);
}
}

//===----------------------------------------------------------------------===//
//                                Snippets
//===----------------------------------------------------------------------===//

// When spilling a virtual register, we also spill any snippets it is connected
// to. The snippets are small live ranges that only have a single real use,
// leftovers from live range splitting. Spilling them enables memory operand
// folding or tightens the live range around the single use.
//
// This minimizes register pressure and maximizes the store-to-load distance for
// spill slots which can be important in tight loops.