From 539e93120cdbb66f651fc55a810416f3175adc8f Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Fri, 13 Dec 2013 18:37:03 +0000 Subject: Liveness Analysis Pass git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197254 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/CMakeLists.txt | 1 + lib/CodeGen/CodeGen.cpp | 1 + lib/CodeGen/MachineInstr.cpp | 7 +- lib/CodeGen/Passes.cpp | 5 + lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 6 ++ lib/CodeGen/StackMapLivenessAnalysis.cpp | 128 +++++++++++++++++++++++ lib/CodeGen/StackMaps.cpp | 117 ++++++++++++++++++--- 7 files changed, 252 insertions(+), 13 deletions(-) create mode 100644 lib/CodeGen/StackMapLivenessAnalysis.cpp (limited to 'lib') 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 << ""; break; + case MachineOperand::MO_RegisterLiveOut: + OS << ""; + 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 DisableCGP("disable-cgp", cl::Hidden, cl::desc("Disable Codegen Prepare")); static cl::opt DisableCopyProp("disable-copyprop", cl::Hidden, cl::desc("Disable Copy Propagation pass")); +static cl::opt EnableStackMapLiveness("enable-stackmap-liveness", + cl::Hidden, cl::desc("Enable StackMap Liveness Analysis Pass")); static cl::opt PrintLSR("print-lsr-output", cl::Hidden, cl::desc("Print LLVM IR produced by the loop-reduce pass")); static cl::opt 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(); +} + +/// 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::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 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(); -- cgit v1.2.3