From 84ef6ba44394f983d985b02e328cbb2dd779e4b0 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Tue, 7 Aug 2012 18:02:19 +0000 Subject: [PATCH] Add trace accessor methods, implement primitive if-conversion heuristic. Compare the critical paths of the two traces through an if-conversion candidate. If the difference is larger than the branch brediction penalty, reject the if-conversion. If would never pay. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@161433 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/EarlyIfConversion.cpp | 22 +++++++++++--- lib/CodeGen/MachineTraceMetrics.cpp | 24 +++++++++++++++ lib/CodeGen/MachineTraceMetrics.h | 47 ++++++++++++++++++++++------- 3 files changed, 78 insertions(+), 15 deletions(-) diff --git a/lib/CodeGen/EarlyIfConversion.cpp b/lib/CodeGen/EarlyIfConversion.cpp index e49b9d3e18e..8adaa6dd0bf 100644 --- a/lib/CodeGen/EarlyIfConversion.cpp +++ b/lib/CodeGen/EarlyIfConversion.cpp @@ -601,10 +601,24 @@ void EarlyIfConverter::invalidateTraces() { bool EarlyIfConverter::shouldConvertIf() { if (!MinInstr) MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount); - DEBUG({ - dbgs() << MinInstr->getTrace(IfConv.Head); - MinInstr->print(dbgs()); - }); + + // MCSchedModel doesn't yet provide a misprediction penalty. + unsigned MispredictPenalty = 10; + + // Compare the critical path through TBB and FBB. If the difference is + // greater than the branch misprediction penalty, it would never pay to + // if-convert. The triangle/diamond topology guarantees that these traces + // have the same head and tail, so they can be compared. + MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.TBB); + MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.FBB); + DEBUG(dbgs() << "TBB: " << TBBTrace << "FBB: " << FBBTrace); + unsigned TBBCrit = TBBTrace.getCriticalPath(); + unsigned FBBCrit = FBBTrace.getCriticalPath(); + unsigned ExtraCrit = TBBCrit > FBBCrit ? TBBCrit-FBBCrit : FBBCrit-TBBCrit; + if (ExtraCrit >= MispredictPenalty) { + DEBUG(dbgs() << "Critical path difference too large.\n"); + return false; + } return true; } diff --git a/lib/CodeGen/MachineTraceMetrics.cpp b/lib/CodeGen/MachineTraceMetrics.cpp index 1c0894e15db..09b6e9c44f5 100644 --- a/lib/CodeGen/MachineTraceMetrics.cpp +++ b/lib/CodeGen/MachineTraceMetrics.cpp @@ -14,6 +14,7 @@ #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/MC/MCInstrItineraries.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Support/Debug.h" @@ -1017,6 +1018,29 @@ MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { return Trace(*this, BlockInfo[MBB->getNumber()]); } +unsigned +MachineTraceMetrics::Trace::getInstrSlack(const MachineInstr *MI) const { + assert(MI && "Not an instruction."); + assert(getBlockNum() == unsigned(MI->getParent()->getNumber()) && + "MI must be in the trace center block"); + InstrCycles Cyc = getInstrCycles(MI); + return getCriticalPath() - (Cyc.Depth + Cyc.Height); +} + +unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { + // For now, we compute the resource depth from instruction count / issue + // width. Eventually, we should compute resource depth per functional unit + // and return the max. + unsigned Instrs = TBI.InstrDepth; + if (Bottom) + Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount; + if (const MCSchedModel *Model = TE.MTM.ItinData->SchedModel) + if (Model->IssueWidth != 0) + return Instrs / Model->IssueWidth; + // Assume issue width 1 without a schedule model. + return Instrs; +} + void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { OS << getName() << " ensemble:\n"; for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) { diff --git a/lib/CodeGen/MachineTraceMetrics.h b/lib/CodeGen/MachineTraceMetrics.h index 33c2d959885..626b28b3227 100644 --- a/lib/CodeGen/MachineTraceMetrics.h +++ b/lib/CodeGen/MachineTraceMetrics.h @@ -188,6 +188,19 @@ public: void print(raw_ostream&) const; }; + /// InstrCycles represents the cycle height and depth of an instruction in a + /// trace. + struct InstrCycles { + /// Earliest issue cycle as determined by data dependencies and instruction + /// latencies from the beginning of the trace. Data dependencies from + /// before the trace are not included. + unsigned Depth; + + /// Minimum number of cycles from this instruction is issued to the of the + /// trace, as determined by data dependencies and instruction latencies. + unsigned Height; + }; + /// A trace represents a plausible sequence of executed basic blocks that /// passes through the current basic block one. The Trace class serves as a /// handle to internal cached data structures. @@ -195,6 +208,8 @@ public: Ensemble &TE; TraceBlockInfo &TBI; + unsigned getBlockNum() const { return &TBI - &TE.BlockInfo[0]; } + public: explicit Trace(Ensemble &te, TraceBlockInfo &tbi) : TE(te), TBI(tbi) {} void print(raw_ostream&) const; @@ -203,19 +218,29 @@ public: unsigned getInstrCount() const { return TBI.InstrDepth + TBI.InstrHeight; } - }; - /// InstrCycles represents the cycle height and depth of an instruction in a - /// trace. - struct InstrCycles { - /// Earliest issue cycle as determined by data dependencies and instruction - /// latencies from the beginning of the trace. Data dependencies from - /// before the trace are not included. - unsigned Depth; + /// Return the resource dpeth of the top/bottom of the trace center block. + /// This is the number of cycles required to execute all instructions from + /// the trace head to the trace center block. The resource depth only + /// considers execution resources, it ignores data dependencies. + /// When Bottom is set, instructions in the trace center block are included. + unsigned getResourceDepth(bool Bottom) const; + + /// Return the length of the (data dependency) critical path through the + /// trace. + unsigned getCriticalPath() const { return TBI.CriticalPath; } + + /// Return the depth and height of MI. The depth is only valid for + /// instructions in or above the trace center block. The height is only + /// valid for instructions in or below the trace center block. + InstrCycles getInstrCycles(const MachineInstr *MI) const { + return TE.Cycles.lookup(MI); + } - /// Minimum number of cycles from this instruction is issued to the of the - /// trace, as determined by data dependencies and instruction latencies. - unsigned Height; + /// Return the slack of MI. This is the number of cycles MI can be delayed + /// before the critical path becomes longer. + /// MI must be an instruction in the trace center block. + unsigned getInstrSlack(const MachineInstr *MI) const; }; /// A trace ensemble is a collection of traces selected using the same -- 2.34.1