//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "early-ifcvt"
+#define DEBUG_TYPE "machine-trace-metrics"
#include "MachineTraceMetrics.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
const MachineBasicBlock *Pred = *I;
const MachineTraceMetrics::TraceBlockInfo *PredTBI =
getDepthResources(Pred);
- assert(PredTBI && "Predecessor must be visited first");
+ // Ignore cycles that aren't natural loops.
+ if (!PredTBI)
+ continue;
// Pick the predecessor that would give this block the smallest InstrDepth.
unsigned Depth = PredTBI->InstrDepth + CurCount;
if (!Best || Depth < BestDepth)
continue;
const MachineTraceMetrics::TraceBlockInfo *SuccTBI =
getHeightResources(Succ);
- assert(SuccTBI && "Successor must be visited first");
+ // Ignore cycles that aren't natural loops.
+ if (!SuccTBI)
+ continue;
// Pick the successor that would give this block the smallest InstrHeight.
unsigned Height = SuccTBI->InstrHeight;
if (!Best || Height < BestHeight)
namespace {
struct LoopBounds {
MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> Blocks;
+ SmallPtrSet<const MachineBasicBlock*, 8> Visited;
const MachineLoopInfo *Loops;
bool Downward;
LoopBounds(MutableArrayRef<MachineTraceMetrics::TraceBlockInfo> blocks,
if (LB.Downward ? TBI.hasValidHeight() : TBI.hasValidDepth())
return false;
// From is null once when To is the trace center block.
- if (!From)
- return true;
- const MachineLoop *FromLoop = LB.Loops->getLoopFor(From);
- if (!FromLoop)
- return true;
- // Don't follow backedges, don't leave FromLoop when going upwards.
- if ((LB.Downward ? To : From) == FromLoop->getHeader())
- return false;
- // Don't leave FromLoop.
- if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To)))
- return false;
- // This is a new block. The PO traversal will compute height/depth
- // resources, causing us to reject new edges to To. This only works because
- // we reject back-edges, so the CFG is cycle-free.
- return true;
+ if (From) {
+ if (const MachineLoop *FromLoop = LB.Loops->getLoopFor(From)) {
+ // Don't follow backedges, don't leave FromLoop when going upwards.
+ if ((LB.Downward ? To : From) == FromLoop->getHeader())
+ return false;
+ // Don't leave FromLoop.
+ if (isExitingLoop(FromLoop, LB.Loops->getLoopFor(To)))
+ return false;
+ }
+ }
+ // To is a new block. Mark the block as visited in case the CFG has cycles
+ // that MachineLoopInfo didn't recognize as a natural loop.
+ return LB.Visited.insert(To);
}
};
}
// Run an upwards post-order search for the trace start.
Bounds.Downward = false;
+ Bounds.Visited.clear();
typedef ipo_ext_iterator<const MachineBasicBlock*, LoopBounds> UpwardPO;
for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds);
I != E; ++I) {
// Run a downwards post-order search for the trace end.
Bounds.Downward = true;
+ Bounds.Visited.clear();
typedef po_ext_iterator<const MachineBasicBlock*, LoopBounds> DownwardPO;
for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds);
I != E; ++I) {
TBI.CriticalPath = 0;
// Get dependencies from PHIs in the trace successor.
- if (TBI.Succ) {
- for (MachineBasicBlock::const_iterator
- I = TBI.Succ->begin(), E = TBI.Succ->end();
- I != E && !I->isPHI(); ++I) {
+ const MachineBasicBlock *Succ = TBI.Succ;
+ // If MBB is the last block in the trace, and it has a back-edge to the
+ // loop header, get loop-carried dependencies from PHIs in the header. For
+ // that purpose, pretend that all the loop header PHIs have height 0.
+ if (!Succ)
+ if (const MachineLoop *Loop = getLoopFor(MBB))
+ if (MBB->isSuccessor(Loop->getHeader()))
+ Succ = Loop->getHeader();
+
+ if (Succ) {
+ for (MachineBasicBlock::const_iterator I = Succ->begin(), E = Succ->end();
+ I != E && I->isPHI(); ++I) {
const MachineInstr *PHI = I;
Deps.clear();
getPHIDeps(PHI, Deps, MBB, MTM.MRI);
- if (!Deps.empty())
- if (pushDepHeight(Deps.front(), PHI, Cycles.lookup(PHI).Height,
- Heights, MTM.ItinData, MTM.TII))
+ if (!Deps.empty()) {
+ // Loop header PHI heights are all 0.
+ unsigned Height = TBI.Succ ? Cycles.lookup(PHI).Height : 0;
+ DEBUG(dbgs() << "pred\t" << Height << '\t' << *PHI);
+ if (pushDepHeight(Deps.front(), PHI, Height,
+ Heights, MTM.ItinData, MTM.TII))
addLiveIns(Deps.front().DefMI, Stack);
+ }
}
}
return getCriticalPath() - (Cyc.Depth + Cyc.Height);
}
+unsigned
+MachineTraceMetrics::Trace::getPHIDepth(const MachineInstr *PHI) const {
+ const MachineBasicBlock *MBB = TE.MTM.MF->getBlockNumbered(getBlockNum());
+ SmallVector<DataDep, 1> Deps;
+ getPHIDeps(PHI, Deps, MBB, TE.MTM.MRI);
+ assert(Deps.size() == 1 && "PHI doesn't have MBB as a predecessor");
+ DataDep &Dep = Deps.front();
+ unsigned DepCycle = getInstrCycles(Dep.DefMI).Depth;
+ // Add latency if DefMI is a real instruction. Transients get latency 0.
+ if (!Dep.DefMI->isTransient())
+ DepCycle += TE.MTM.TII->computeOperandLatency(TE.MTM.ItinData,
+ Dep.DefMI, Dep.DefOp,
+ PHI, Dep.UseOp,
+ /* FindMin = */ false);
+ return DepCycle;
+}
+
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
return Instrs;
}
+unsigned MachineTraceMetrics::Trace::
+getResourceLength(ArrayRef<const MachineBasicBlock*> Extrablocks) const {
+ unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight;
+ for (unsigned i = 0, e = Extrablocks.size(); i != e; ++i)
+ Instrs += TE.MTM.getResources(Extrablocks[i])->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) {