Liveness Analysis Pass

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197254 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 252 insertions, 13 deletions

diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt
index 0beca0ceed..123d86f950 100644
--- a/lib/CodeGen/CMakeLists.txt
+++ b/lib/CodeGen/CMakeLists.txt
@@ -97,6 +97,7 @@ add_llvm_library(LLVMCodeGen
   StackColoring.cpp
   StackProtector.cpp
   StackSlotColoring.cpp
+  StackMapLivenessAnalysis.cpp
   StackMaps.cpp
   TailDuplication.cpp
   TargetFrameLoweringImpl.cpp
diff --git a/lib/CodeGen/CodeGen.cpp b/lib/CodeGen/CodeGen.cpp
index 7430c53b8d..30b40a12da 100644
--- a/lib/CodeGen/CodeGen.cpp
+++ b/lib/CodeGen/CodeGen.cpp
@@ -69,6 +69,7 @@ void llvm::initializeCodeGen(PassRegistry &Registry) {
   initializeVirtRegRewriterPass(Registry);
   initializeLowerIntrinsicsPass(Registry);
   initializeMachineFunctionPrinterPassPass(Registry);
+  initializeStackMapLivenessPass(Registry);
 }
 
 void LLVMInitializeCodeGen(LLVMPassRegistryRef R) {
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index 295b450a0f..34eeea2333 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -199,7 +199,8 @@ bool MachineOperand::isIdenticalTo(const MachineOperand &Other) const {
   case MachineOperand::MO_BlockAddress:
     return getBlockAddress() == Other.getBlockAddress() &&
            getOffset() == Other.getOffset();
-  case MO_RegisterMask:
+  case MachineOperand::MO_RegisterMask:
+  case MachineOperand::MO_RegisterLiveOut:
     return getRegMask() == Other.getRegMask();
   case MachineOperand::MO_MCSymbol:
     return getMCSymbol() == Other.getMCSymbol();
@@ -241,6 +242,7 @@ hash_code llvm::hash_value(const MachineOperand &MO) {
     return hash_combine(MO.getType(), MO.getTargetFlags(),
                         MO.getBlockAddress(), MO.getOffset());
   case MachineOperand::MO_RegisterMask:
+  case MachineOperand::MO_RegisterLiveOut:
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getRegMask());
   case MachineOperand::MO_Metadata:
     return hash_combine(MO.getType(), MO.getTargetFlags(), MO.getMetadata());
@@ -368,6 +370,9 @@ void MachineOperand::print(raw_ostream &OS, const TargetMachine *TM) const {
   case MachineOperand::MO_RegisterMask:
     OS << "<regmask>";
     break;
+  case MachineOperand::MO_RegisterLiveOut:
+    OS << "<regliveout>";
+    break;
   case MachineOperand::MO_Metadata:
     OS << '<';
     WriteAsOperand(OS, getMetadata(), /*PrintType=*/false);
diff --git a/lib/CodeGen/Passes.cpp b/lib/CodeGen/Passes.cpp
index db7021372b..e9f780cf13 100644
--- a/lib/CodeGen/Passes.cpp
+++ b/lib/CodeGen/Passes.cpp
@@ -69,6 +69,8 @@ static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
     cl::desc("Disable Codegen Prepare"));
 static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
     cl::desc("Disable Copy Propagation pass"));
+static cl::opt<bool> EnableStackMapLiveness("enable-stackmap-liveness",
+    cl::Hidden, cl::desc("Enable StackMap Liveness Analysis Pass"));
 static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
     cl::desc("Print LLVM IR produced by the loop-reduce pass"));
 static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
@@ -536,6 +538,9 @@ void TargetPassConfig::addMachinePasses() {
 
   if (addPreEmitPass())
     printAndVerify("After PreEmit passes");
+
+  if (EnableStackMapLiveness)
+    addPass(&StackMapLivenessID);
 }
 
 /// Add passes that optimize machine instructions in SSA form.
diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 08750cabed..90ac211a21 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -6886,6 +6886,9 @@ void SelectionDAGBuilder::visitStackmap(const CallInst &CI) {
   DAG.ReplaceAllUsesWith(Call, MN);
 
   DAG.DeleteNode(Call);
+
+  // Inform the Frame Information that we have a stackmap in this function.
+  FuncInfo.MF->getFrameInfo()->setHasStackMap();
 }
 
 /// \brief Lower llvm.experimental.patchpoint directly to its target opcode.
@@ -7025,6 +7028,9 @@ void SelectionDAGBuilder::visitPatchpoint(const CallInst &CI) {
   } else
     DAG.ReplaceAllUsesWith(Call, MN);
   DAG.DeleteNode(Call);
+
+  // Inform the Frame Information that we have a stackmap in this function.
+  FuncInfo.MF->getFrameInfo()->setHasStackMap();
 }
 
 /// TargetLowering::LowerCallTo - This is the default LowerCallTo
diff --git a/lib/CodeGen/StackMapLivenessAnalysis.cpp b/lib/CodeGen/StackMapLivenessAnalysis.cpp
new file mode 100644
index 0000000000..788b83416b
--- /dev/null
+++ b/lib/CodeGen/StackMapLivenessAnalysis.cpp
@@ -0,0 +1,128 @@
+//===-- StackMapLivenessAnalysis.cpp - StackMap live Out Analysis ----------===//
+//
+//                     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 StackMap Liveness analysis pass. The pass calculates
+// the liveness for each basic block in a function and attaches the register
+// live-out information to a stackmap or patchpoint intrinsic if present.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "stackmaps"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionAnalysis.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/StackMapLivenessAnalysis.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+
+STATISTIC(NumStackMapFuncVisited, "Number of functions visited");
+STATISTIC(NumStackMapFuncSkipped, "Number of functions skipped");
+STATISTIC(NumBBsVisited,          "Number of basic blocks visited");
+STATISTIC(NumBBsHaveNoStackmap,   "Number of basic blocks with no stackmap");
+STATISTIC(NumStackMaps,           "Number of StackMaps visited");
+
+char StackMapLiveness::ID = 0;
+char &llvm::StackMapLivenessID = StackMapLiveness::ID;
+INITIALIZE_PASS(StackMapLiveness, "stackmap-liveness",
+                "StackMap Liveness Analysis", false, false)
+
+/// Default construct and initialize the pass.
+StackMapLiveness::StackMapLiveness() : MachineFunctionPass(ID) {
+  initializeStackMapLivenessPass(*PassRegistry::getPassRegistry());
+}
+
+/// Tell the pass manager which passes we depend on and what information we
+/// preserve.
+void StackMapLiveness::getAnalysisUsage(AnalysisUsage &AU) const {
+  // We preserve all information.
+  AU.setPreservesAll();
+  AU.setPreservesCFG();
+  // Default dependencie for all MachineFunction passes.
+  AU.addRequired<MachineFunctionAnalysis>();
+}
+
+/// Calculate the liveness information for the given machine function.
+bool StackMapLiveness::runOnMachineFunction(MachineFunction &_MF) {
+  DEBUG(dbgs() << "********** COMPUTING STACKMAP LIVENESS: "
+               << _MF.getName() << " **********\n");
+  MF = &_MF;
+  TRI = MF->getTarget().getRegisterInfo();
+  ++NumStackMapFuncVisited;
+
+  // Skip this function if there are no stackmaps.
+  if (!MF->getFrameInfo()->hasStackMap()) {
+    ++NumStackMapFuncSkipped;
+    return false;
+  }
+  return calculateLiveness();
+}
+
+/// Performs the actual liveness calculation for the function.
+bool StackMapLiveness::calculateLiveness() {
+  bool HasChanged = false;
+  // For all basic blocks in the function.
+  for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
+       MBBI != MBBE; ++MBBI) {
+    DEBUG(dbgs() << "****** BB " << MBBI->getName() << " ******\n");
+    LiveRegs.init(TRI);
+    LiveRegs.addLiveOuts(MBBI);
+    bool HasStackMap = false;
+    // Reverse iterate over all instructions and add the current live register
+    // set to an instruction if we encounter a stackmap or patchpoint
+    // instruction.
+    for (MachineBasicBlock::reverse_iterator I = MBBI->rbegin(),
+         E = MBBI->rend(); I != E; ++I) {
+      if (I->getOpcode() == TargetOpcode::STACKMAP ||
+          I->getOpcode() == TargetOpcode::PATCHPOINT) {
+        addLiveOutSetToMI(*I);
+        HasChanged = true;
+        HasStackMap = true;
+        ++NumStackMaps;
+      }
+      LiveRegs.stepBackward(*I);
+    }
+    ++NumBBsVisited;
+    if (!HasStackMap)
+      ++NumBBsHaveNoStackmap;
+  }
+  return HasChanged;
+}
+
+/// Add the current register live set to the instruction.
+void StackMapLiveness::addLiveOutSetToMI(MachineInstr &MI) {
+  uint32_t *Mask = createRegisterMask();
+  MachineOperand MO = MachineOperand::CreateRegLiveOut(Mask);
+  MI.addOperand(*MF, MO);
+  DEBUG(dbgs() << "   " << MI);
+  DEBUG(printLiveOutSet(dbgs()));
+}
+
+/// Create a register mask and initialize it with the registers from the
+/// register live set.
+uint32_t *StackMapLiveness::createRegisterMask() const {
+  // The mask is owned and cleaned up by the Machine Function.
+  uint32_t *Mask = MF->allocateRegisterMask(TRI->getNumRegs());
+  for (LivePhysRegs::const_iterator RI = LiveRegs.begin(), RE = LiveRegs.end();
+       RI != RE; ++RI)
+    Mask[*RI / 32] |= 1U << (*RI % 32);
+  return Mask;
+}
+
+/// Print the current register live set for debugging.
+void StackMapLiveness::printLiveOutSet(raw_ostream &OS) const {
+  OS << "   Register live-out:";
+  for (LivePhysRegs::const_iterator RI = LiveRegs.begin(), RE = LiveRegs.end();
+       RI != RE; ++RI)
+    OS << " " << TRI->getName(*RI);
+  OS << "\n";
+}
diff --git a/lib/CodeGen/StackMaps.cpp b/lib/CodeGen/StackMaps.cpp
index bec3021423..892e4573b0 100644
--- a/lib/CodeGen/StackMaps.cpp
+++ b/lib/CodeGen/StackMaps.cpp
@@ -68,10 +68,10 @@ unsigned PatchPointOpers::getNextScratchIdx(unsigned StartIdx) const {
 
 std::pair<StackMaps::Location, MachineInstr::const_mop_iterator>
 StackMaps::parseOperand(MachineInstr::const_mop_iterator MOI,
-                        MachineInstr::const_mop_iterator MOE) {
+                        MachineInstr::const_mop_iterator MOE) const {
   const MachineOperand &MOP = *MOI;
-  assert(!MOP.isRegMask() && (!MOP.isReg() || !MOP.isImplicit()) &&
-         "Register mask and implicit operands should not be processed.");
+  assert((!MOP.isReg() || !MOP.isImplicit()) &&
+         "Implicit operands should not be processed.");
 
   if (MOP.isImm()) {
     // Verify anyregcc
@@ -106,6 +106,9 @@ StackMaps::parseOperand(MachineInstr::const_mop_iterator MOI,
     }
   }
 
+  if (MOP.isRegMask() || MOP.isRegLiveOut())
+    return std::make_pair(Location(), ++MOI);
+
   // Otherwise this is a reg operand. The physical register number will
   // ultimately be encoded as a DWARF regno. The stack map also records the size
   // of a spill slot that can hold the register content. (The runtime can
@@ -120,6 +123,66 @@ StackMaps::parseOperand(MachineInstr::const_mop_iterator MOI,
     Location(Location::Register, RC->getSize(), MOP.getReg(), 0), ++MOI);
 }
 
+/// Go up the super-register chain until we hit a valid dwarf register number.
+static short getDwarfRegNum(unsigned Reg, const MCRegisterInfo &MCRI,
+                               const TargetRegisterInfo *TRI) {
+  int RegNo = MCRI.getDwarfRegNum(Reg, false);
+  for (MCSuperRegIterator SR(Reg, TRI);
+       SR.isValid() && RegNo < 0; ++SR)
+    RegNo = TRI->getDwarfRegNum(*SR, false);
+
+  assert(RegNo >= 0 && "Invalid Dwarf register number.");
+  return (unsigned short) RegNo;
+}
+
+/// Create a live-out register record for the given register Reg.
+StackMaps::LiveOutReg
+StackMaps::createLiveOutReg(unsigned Reg, const MCRegisterInfo &MCRI,
+                            const TargetRegisterInfo *TRI) const {
+  unsigned RegNo = getDwarfRegNum(Reg, MCRI, TRI);
+  unsigned Size = TRI->getMinimalPhysRegClass(Reg)->getSize();
+  unsigned LLVMRegNo = MCRI.getLLVMRegNum(RegNo, false);
+  unsigned SubRegIdx = MCRI.getSubRegIndex(LLVMRegNo, Reg);
+  unsigned Offset = 0;
+  if (SubRegIdx)
+    Offset = MCRI.getSubRegIdxOffset(SubRegIdx) / 8;
+
+  return LiveOutReg(Reg, RegNo, Offset + Size);
+}
+
+/// Parse the register live-out mask and return a vector of live-out registers
+/// that need to be recorded in the stackmap.
+StackMaps::LiveOutVec
+StackMaps::parseRegisterLiveOutMask(const uint32_t *Mask) const {
+  assert(Mask && "No register mask specified");
+  const TargetRegisterInfo *TRI = AP.TM.getRegisterInfo();
+  MCContext &OutContext = AP.OutStreamer.getContext();
+  const MCRegisterInfo &MCRI = *OutContext.getRegisterInfo();
+  LiveOutVec LiveOuts;
+
+  for (unsigned Reg = 0, NumRegs = TRI->getNumRegs(); Reg != NumRegs; ++Reg)
+    if ((Mask[Reg / 32] >> Reg % 32) & 1)
+      LiveOuts.push_back(createLiveOutReg(Reg, MCRI, TRI));
+
+  std::sort(LiveOuts.begin(), LiveOuts.end());
+  for (LiveOutVec::iterator I = LiveOuts.begin(), E = LiveOuts.end();
+       I != E; ++I) {
+    if (!I->Reg)
+      continue;
+    for (LiveOutVec::iterator II = next(I); II != E; ++II) {
+      if (I->RegNo != II->RegNo)
+        break;
+      I->Size = std::max(I->Size, II->Size);
+      if (TRI->isSuperRegister(I->Reg, II->Reg))
+        I->Reg = II->Reg;
+      II->Reg = 0;
+    }
+  }
+  LiveOuts.erase(std::remove_if(LiveOuts.begin(), LiveOuts.end(),
+                                LiveOutReg::isInvalid), LiveOuts.end());
+  return LiveOuts;
+}
+
 void StackMaps::recordStackMapOpers(const MachineInstr &MI, uint32_t ID,
                                     MachineInstr::const_mop_iterator MOI,
                                     MachineInstr::const_mop_iterator MOE,
@@ -129,7 +192,8 @@ void StackMaps::recordStackMapOpers(const MachineInstr &MI, uint32_t ID,
   MCSymbol *MILabel = OutContext.CreateTempSymbol();
   AP.OutStreamer.EmitLabel(MILabel);
 
-  LocationVec CallsiteLocs;
+  LocationVec Locations;
+  LiveOutVec LiveOuts;
 
   if (recordResult) {
     std::pair<Location, MachineInstr::const_mop_iterator> ParseResult =
@@ -138,7 +202,7 @@ void StackMaps::recordStackMapOpers(const MachineInstr &MI, uint32_t ID,
     Location &Loc = ParseResult.first;
     assert(Loc.LocType == Location::Register &&
            "Stackmap return location must be a register.");
-    CallsiteLocs.push_back(Loc);
+    Locations.push_back(Loc);
   }
 
   while (MOI != MOE) {
@@ -151,7 +215,9 @@ void StackMaps::recordStackMapOpers(const MachineInstr &MI, uint32_t ID,
       Loc.Offset = ConstPool.getConstantIndex(Loc.Offset);
     }
 
-    CallsiteLocs.push_back(Loc);
+    // Skip the register mask and register live-out mask
+    if (Loc.LocType != Location::Unprocessed)
+      Locations.push_back(Loc);
   }
 
   const MCExpr *CSOffsetExpr = MCBinaryExpr::CreateSub(
@@ -159,21 +225,23 @@ void StackMaps::recordStackMapOpers(const MachineInstr &MI, uint32_t ID,
     MCSymbolRefExpr::Create(AP.CurrentFnSym, OutContext),
     OutContext);
 
-  CSInfos.push_back(CallsiteInfo(CSOffsetExpr, ID, CallsiteLocs));
+  if (MOI->isRegLiveOut())
+    LiveOuts = parseRegisterLiveOutMask(MOI->getRegLiveOut());
+
+  CSInfos.push_back(CallsiteInfo(CSOffsetExpr, ID, Locations, LiveOuts));
 }
 
 static MachineInstr::const_mop_iterator
 getStackMapEndMOP(MachineInstr::const_mop_iterator MOI,
                   MachineInstr::const_mop_iterator MOE) {
   for (; MOI != MOE; ++MOI)
-    if (MOI->isRegMask() || (MOI->isReg() && MOI->isImplicit()))
+    if (MOI->isRegLiveOut() || (MOI->isReg() && MOI->isImplicit()))
       break;
-
   return MOI;
 }
 
 void StackMaps::recordStackMap(const MachineInstr &MI) {
-  assert(MI.getOpcode() == TargetOpcode::STACKMAP && "exected stackmap");
+  assert(MI.getOpcode() == TargetOpcode::STACKMAP && "expected stackmap");
 
   int64_t ID = MI.getOperand(0).getImm();
   assert((int32_t)ID == ID && "Stack maps hold 32-bit IDs");
@@ -183,7 +251,7 @@ void StackMaps::recordStackMap(const MachineInstr &MI) {
 }
 
 void StackMaps::recordPatchPoint(const MachineInstr &MI) {
-  assert(MI.getOpcode() == TargetOpcode::PATCHPOINT && "exected stackmap");
+  assert(MI.getOpcode() == TargetOpcode::PATCHPOINT && "expected patchpoint");
 
   PatchPointOpers opers(&MI);
   int64_t ID = opers.getMetaOper(PatchPointOpers::IDPos).getImm();
@@ -222,6 +290,11 @@ void StackMaps::recordPatchPoint(const MachineInstr &MI) {
 ///     uint16 : Dwarf RegNum
 ///     int32  : Offset
 ///   }
+///   uint16 : NumLiveOuts
+///   LiveOuts[NumLiveOuts]
+///     uint16 : Dwarf RegNum
+///     uint8  : Reserved
+///     uint8  : Size in Bytes
 /// }
 ///
 /// Location Encoding, Type, Value:
@@ -274,6 +347,7 @@ void StackMaps::serializeToStackMapSection() {
 
     unsigned CallsiteID = CSII->ID;
     const LocationVec &CSLocs = CSII->Locations;
+    const LiveOutVec &LiveOuts = CSII->LiveOuts;
 
     DEBUG(dbgs() << WSMP << "callsite " << CallsiteID << "\n");
 
@@ -281,11 +355,12 @@ void StackMaps::serializeToStackMapSection() {
     // runtime than crash in case of in-process compilation. Currently, we do
     // simple overflow checks, but we may eventually communicate other
     // compilation errors this way.
-    if (CSLocs.size() > UINT16_MAX) {
+    if (CSLocs.size() > UINT16_MAX || LiveOuts.size() > UINT16_MAX) {
       AP.OutStreamer.EmitIntValue(UINT32_MAX, 4); // Invalid ID.
       AP.OutStreamer.EmitValue(CSII->CSOffsetExpr, 4);
       AP.OutStreamer.EmitIntValue(0, 2); // Reserved.
       AP.OutStreamer.EmitIntValue(0, 2); // 0 locations.
+      AP.OutStreamer.EmitIntValue(0, 2); // 0 live-out registers.
       continue;
     }
 
@@ -362,6 +437,24 @@ void StackMaps::serializeToStackMapSection() {
       AP.OutStreamer.EmitIntValue(RegNo, 2);
       AP.OutStreamer.EmitIntValue(Offset, 4);
     }
+
+    DEBUG(dbgs() << WSMP << "  has " << LiveOuts.size()
+                 << " live-out registers\n");
+
+    AP.OutStreamer.EmitIntValue(LiveOuts.size(), 2);
+
+    operIdx = 0;
+    for (LiveOutVec::const_iterator LI = LiveOuts.begin(), LE = LiveOuts.end();
+         LI != LE; ++LI, ++operIdx) {
+      DEBUG(dbgs() << WSMP << "  LO " << operIdx << ": "
+                   << MCRI.getName(LI->Reg)
+                   << "     [encoding: .short " << LI->RegNo
+                   << ", .byte 0, .byte " << LI->Size << "]\n");
+
+      AP.OutStreamer.EmitIntValue(LI->RegNo, 2);
+      AP.OutStreamer.EmitIntValue(0, 1);
+      AP.OutStreamer.EmitIntValue(LI->Size, 1);
+    }
   }
 
   AP.OutStreamer.AddBlankLine();