X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=lib%2FCodeGen%2FMachineTraceMetrics.cpp;h=d9a6b68462eb962a8eed2df8a15b8273a8f04681;hb=3f45c27d19f4315437d493ed3c9429b57e2cc59c;hp=1bbf0ade6a5805fb09b2a303379968471966599f;hpb=846781235d0c027702e2c528a6660ec14ca8edcd;p=oota-llvm.git diff --git a/lib/CodeGen/MachineTraceMetrics.cpp b/lib/CodeGen/MachineTraceMetrics.cpp index 1bbf0ade6a5..d9a6b68462e 100644 --- a/lib/CodeGen/MachineTraceMetrics.cpp +++ b/lib/CodeGen/MachineTraceMetrics.cpp @@ -52,13 +52,12 @@ void MachineTraceMetrics::getAnalysisUsage(AnalysisUsage &AU) const { bool MachineTraceMetrics::runOnMachineFunction(MachineFunction &Func) { MF = &Func; - TII = MF->getTarget().getInstrInfo(); - TRI = MF->getTarget().getRegisterInfo(); + const TargetSubtargetInfo &ST = MF->getSubtarget(); + TII = ST.getInstrInfo(); + TRI = ST.getRegisterInfo(); MRI = &MF->getRegInfo(); Loops = &getAnalysis(); - const TargetSubtargetInfo &ST = - MF->getTarget().getSubtarget(); - SchedModel.init(*ST.getSchedModel(), &ST, TII); + SchedModel.init(ST.getSchedModel(), &ST, TII); BlockInfo.resize(MF->getNumBlockIDs()); ProcResourceCycles.resize(MF->getNumBlockIDs() * SchedModel.getNumProcResourceKinds()); @@ -135,8 +134,7 @@ MachineTraceMetrics::getProcResourceCycles(unsigned MBBNum) const { "getResources() must be called before getProcResourceCycles()"); unsigned PRKinds = SchedModel.getNumProcResourceKinds(); assert((MBBNum+1) * PRKinds <= ProcResourceCycles.size()); - return ArrayRef(ProcResourceCycles.data() + MBBNum * PRKinds, - PRKinds); + return makeArrayRef(ProcResourceCycles.data() + MBBNum * PRKinds, PRKinds); } @@ -256,8 +254,7 @@ MachineTraceMetrics::Ensemble:: getProcResourceDepths(unsigned MBBNum) const { unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); assert((MBBNum+1) * PRKinds <= ProcResourceDepths.size()); - return ArrayRef(ProcResourceDepths.data() + MBBNum * PRKinds, - PRKinds); + return makeArrayRef(ProcResourceDepths.data() + MBBNum * PRKinds, PRKinds); } /// Get an array of processor resource heights for MBB. Indexed by processor @@ -270,8 +267,7 @@ MachineTraceMetrics::Ensemble:: getProcResourceHeights(unsigned MBBNum) const { unsigned PRKinds = MTM.SchedModel.getNumProcResourceKinds(); assert((MBBNum+1) * PRKinds <= ProcResourceHeights.size()); - return ArrayRef(ProcResourceHeights.data() + MBBNum * PRKinds, - PRKinds); + return makeArrayRef(ProcResourceHeights.data() + MBBNum * PRKinds, PRKinds); } //===----------------------------------------------------------------------===// @@ -324,9 +320,7 @@ MinInstrCountEnsemble::pickTracePred(const MachineBasicBlock *MBB) { unsigned CurCount = MTM.getResources(MBB)->InstrCount; const MachineBasicBlock *Best = nullptr; unsigned BestDepth = 0; - for (MachineBasicBlock::const_pred_iterator - I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) { - const MachineBasicBlock *Pred = *I; + for (const MachineBasicBlock *Pred : MBB->predecessors()) { const MachineTraceMetrics::TraceBlockInfo *PredTBI = getDepthResources(Pred); // Ignore cycles that aren't natural loops. @@ -348,9 +342,7 @@ MinInstrCountEnsemble::pickTraceSucc(const MachineBasicBlock *MBB) { const MachineLoop *CurLoop = getLoopFor(MBB); const MachineBasicBlock *Best = nullptr; unsigned BestHeight = 0; - for (MachineBasicBlock::const_succ_iterator - I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { - const MachineBasicBlock *Succ = *I; + for (const MachineBasicBlock *Succ : MBB->successors()) { // Don't consider back-edges. if (CurLoop && Succ == CurLoop->getHeader()) continue; @@ -452,7 +444,7 @@ public: } // 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); + return LB.Visited.insert(To).second; } }; } @@ -467,13 +459,11 @@ void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { // Run an upwards post-order search for the trace start. Bounds.Downward = false; Bounds.Visited.clear(); - typedef ipo_ext_iterator UpwardPO; - for (UpwardPO I = ipo_ext_begin(MBB, Bounds), E = ipo_ext_end(MBB, Bounds); - I != E; ++I) { + for (auto I : inverse_post_order_ext(MBB, Bounds)) { DEBUG(dbgs() << " pred for BB#" << I->getNumber() << ": "); TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; // All the predecessors have been visited, pick the preferred one. - TBI.Pred = pickTracePred(*I); + TBI.Pred = pickTracePred(I); DEBUG({ if (TBI.Pred) dbgs() << "BB#" << TBI.Pred->getNumber() << '\n'; @@ -481,19 +471,17 @@ void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { dbgs() << "null\n"; }); // The trace leading to I is now known, compute the depth resources. - computeDepthResources(*I); + computeDepthResources(I); } // Run a downwards post-order search for the trace end. Bounds.Downward = true; Bounds.Visited.clear(); - typedef po_ext_iterator DownwardPO; - for (DownwardPO I = po_ext_begin(MBB, Bounds), E = po_ext_end(MBB, Bounds); - I != E; ++I) { + for (auto I : post_order_ext(MBB, Bounds)) { DEBUG(dbgs() << " succ for BB#" << I->getNumber() << ": "); TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; // All the successors have been visited, pick the preferred one. - TBI.Succ = pickTraceSucc(*I); + TBI.Succ = pickTraceSucc(I); DEBUG({ if (TBI.Succ) dbgs() << "BB#" << TBI.Succ->getNumber() << '\n'; @@ -501,7 +489,7 @@ void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { dbgs() << "null\n"; }); // The trace leaving I is now known, compute the height resources. - computeHeightResources(*I); + computeHeightResources(I); } } @@ -521,18 +509,17 @@ MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { << " height.\n"); // Find any MBB predecessors that have MBB as their preferred successor. // They are the only ones that need to be invalidated. - for (MachineBasicBlock::const_pred_iterator - I = MBB->pred_begin(), E = MBB->pred_end(); I != E; ++I) { - TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()]; + for (const MachineBasicBlock *Pred : MBB->predecessors()) { + TraceBlockInfo &TBI = BlockInfo[Pred->getNumber()]; if (!TBI.hasValidHeight()) continue; if (TBI.Succ == MBB) { TBI.invalidateHeight(); - WorkList.push_back(*I); + WorkList.push_back(Pred); continue; } // Verify that TBI.Succ is actually a *I successor. - assert((!TBI.Succ || (*I)->isSuccessor(TBI.Succ)) && "CFG changed"); + assert((!TBI.Succ || Pred->isSuccessor(TBI.Succ)) && "CFG changed"); } } while (!WorkList.empty()); } @@ -547,18 +534,17 @@ MachineTraceMetrics::Ensemble::invalidate(const MachineBasicBlock *BadMBB) { << " depth.\n"); // Find any MBB successors that have MBB as their preferred predecessor. // They are the only ones that need to be invalidated. - for (MachineBasicBlock::const_succ_iterator - I = MBB->succ_begin(), E = MBB->succ_end(); I != E; ++I) { - TraceBlockInfo &TBI = BlockInfo[(*I)->getNumber()]; + for (const MachineBasicBlock *Succ : MBB->successors()) { + TraceBlockInfo &TBI = BlockInfo[Succ->getNumber()]; if (!TBI.hasValidDepth()) continue; if (TBI.Pred == MBB) { TBI.invalidateDepth(); - WorkList.push_back(*I); + WorkList.push_back(Succ); continue; } // Verify that TBI.Pred is actually a *I predecessor. - assert((!TBI.Pred || (*I)->isPredecessor(TBI.Pred)) && "CFG changed"); + assert((!TBI.Pred || Succ->isPredecessor(TBI.Pred)) && "CFG changed"); } } while (!WorkList.empty()); } @@ -638,11 +624,17 @@ struct DataDep { static bool getDataDeps(const MachineInstr *UseMI, SmallVectorImpl &Deps, const MachineRegisterInfo *MRI) { + // Debug values should not be included in any calculations. + if (UseMI->isDebugValue()) + return false; + bool HasPhysRegs = false; - for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) { - if (!MO->isReg()) + for (MachineInstr::const_mop_iterator I = UseMI->operands_begin(), + E = UseMI->operands_end(); I != E; ++I) { + const MachineOperand &MO = *I; + if (!MO.isReg()) continue; - unsigned Reg = MO->getReg(); + unsigned Reg = MO.getReg(); if (!Reg) continue; if (TargetRegisterInfo::isPhysicalRegister(Reg)) { @@ -650,8 +642,8 @@ static bool getDataDeps(const MachineInstr *UseMI, continue; } // Collect virtual register reads. - if (MO->readsReg()) - Deps.push_back(DataDep(MRI, Reg, MO.getOperandNo())); + if (MO.readsReg()) + Deps.push_back(DataDep(MRI, Reg, UseMI->getOperandNo(I))); } return HasPhysRegs; } @@ -702,28 +694,30 @@ static void updatePhysDepsDownwards(const MachineInstr *UseMI, SmallVector Kills; SmallVector LiveDefOps; - for (ConstMIOperands MO(UseMI); MO.isValid(); ++MO) { - if (!MO->isReg()) + for (MachineInstr::const_mop_iterator MI = UseMI->operands_begin(), + ME = UseMI->operands_end(); MI != ME; ++MI) { + const MachineOperand &MO = *MI; + if (!MO.isReg()) continue; - unsigned Reg = MO->getReg(); + unsigned Reg = MO.getReg(); if (!TargetRegisterInfo::isPhysicalRegister(Reg)) continue; // Track live defs and kills for updating RegUnits. - if (MO->isDef()) { - if (MO->isDead()) + if (MO.isDef()) { + if (MO.isDead()) Kills.push_back(Reg); else - LiveDefOps.push_back(MO.getOperandNo()); - } else if (MO->isKill()) + LiveDefOps.push_back(UseMI->getOperandNo(MI)); + } else if (MO.isKill()) Kills.push_back(Reg); // Identify dependencies. - if (!MO->readsReg()) + if (!MO.readsReg()) continue; for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) { SparseSet::iterator I = RegUnits.find(*Units); if (I == RegUnits.end()) continue; - Deps.push_back(DataDep(I->MI, I->Op, MO.getOperandNo())); + Deps.push_back(DataDep(I->MI, I->Op, UseMI->getOperandNo(MI))); break; } } @@ -837,8 +831,7 @@ computeInstrDepths(const MachineBasicBlock *MBB) { // Filter and process dependencies, computing the earliest issue cycle. unsigned Cycle = 0; - for (unsigned i = 0, e = Deps.size(); i != e; ++i) { - const DataDep &Dep = Deps[i]; + for (const DataDep &Dep : Deps) { const TraceBlockInfo&DepTBI = BlockInfo[Dep.DefMI->getParent()->getNumber()]; // Ignore dependencies from outside the current trace. @@ -876,15 +869,18 @@ static unsigned updatePhysDepsUpwards(const MachineInstr *MI, unsigned Height, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI) { SmallVector ReadOps; - for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { - if (!MO->isReg()) + + for (MachineInstr::const_mop_iterator MOI = MI->operands_begin(), + MOE = MI->operands_end(); MOI != MOE; ++MOI) { + const MachineOperand &MO = *MOI; + if (!MO.isReg()) continue; - unsigned Reg = MO->getReg(); + unsigned Reg = MO.getReg(); if (!TargetRegisterInfo::isPhysicalRegister(Reg)) continue; - if (MO->readsReg()) - ReadOps.push_back(MO.getOperandNo()); - if (!MO->isDef()) + if (MO.readsReg()) + ReadOps.push_back(MI->getOperandNo(MOI)); + if (!MO.isDef()) continue; // This is a def of Reg. Remove corresponding entries from RegUnits, and // update MI Height to consider the physreg dependencies. @@ -897,7 +893,7 @@ static unsigned updatePhysDepsUpwards(const MachineInstr *MI, unsigned Height, // We may not know the UseMI of this dependency, if it came from the // live-in list. SchedModel can handle a NULL UseMI. DepHeight += SchedModel - .computeOperandLatency(MI, MO.getOperandNo(), I->MI, I->Op); + .computeOperandLatency(MI, MI->getOperandNo(MOI), I->MI, I->Op); } Height = std::max(Height, DepHeight); // This regunit is dead above MI. @@ -1004,8 +1000,7 @@ computeInstrHeights(const MachineBasicBlock *MBB) { // MBB is the highest precomputed block in the trace. if (MBB) { TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; - for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) { - LiveInReg LI = TBI.LiveIns[i]; + for (LiveInReg &LI : TBI.LiveIns) { if (TargetRegisterInfo::isVirtualRegister(LI.Reg)) { // For virtual registers, the def latency is included. unsigned &Height = Heights[MTM.MRI->getVRegDef(LI.Reg)]; @@ -1093,9 +1088,9 @@ computeInstrHeights(const MachineBasicBlock *MBB) { MTM.SchedModel, MTM.TII, MTM.TRI); // Update the required height of any virtual registers read by MI. - for (unsigned i = 0, e = Deps.size(); i != e; ++i) - if (pushDepHeight(Deps[i], MI, Cycle, Heights, MTM.SchedModel, MTM.TII)) - addLiveIns(Deps[i].DefMI, Deps[i].DefOp, Stack); + for (const DataDep &Dep : Deps) + if (pushDepHeight(Dep, MI, Cycle, Heights, MTM.SchedModel, MTM.TII)) + addLiveIns(Dep.DefMI, Dep.DefOp, Stack); InstrCycles &MICycles = Cycles[MI]; MICycles.Height = Cycle; @@ -1111,8 +1106,7 @@ computeInstrHeights(const MachineBasicBlock *MBB) { // Update virtual live-in heights. They were added by addLiveIns() with a 0 // height because the final height isn't known until now. DEBUG(dbgs() << "BB#" << MBB->getNumber() << " Live-ins:"); - for (unsigned i = 0, e = TBI.LiveIns.size(); i != e; ++i) { - LiveInReg &LIR = TBI.LiveIns[i]; + for (LiveInReg &LIR : TBI.LiveIns) { const MachineInstr *DefMI = MTM.MRI->getVRegDef(LIR.Reg); LIR.Height = Heights.lookup(DefMI); DEBUG(dbgs() << ' ' << PrintReg(LIR.Reg) << '@' << LIR.Height); @@ -1138,11 +1132,16 @@ computeInstrHeights(const MachineBasicBlock *MBB) { MachineTraceMetrics::Trace MachineTraceMetrics::Ensemble::getTrace(const MachineBasicBlock *MBB) { - // FIXME: Check cache tags, recompute as needed. - computeTrace(MBB); - computeInstrDepths(MBB); - computeInstrHeights(MBB); - return Trace(*this, BlockInfo[MBB->getNumber()]); + TraceBlockInfo &TBI = BlockInfo[MBB->getNumber()]; + + if (!TBI.hasValidDepth() || !TBI.hasValidHeight()) + computeTrace(MBB); + if (!TBI.HasValidInstrDepths) + computeInstrDepths(MBB); + if (!TBI.HasValidInstrHeights) + computeInstrHeights(MBB); + + return Trace(*this, TBI); } unsigned @@ -1169,6 +1168,7 @@ MachineTraceMetrics::Trace::getPHIDepth(const MachineInstr *PHI) const { return DepCycle; } +/// When bottom is set include instructions in current block in estimate. unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { // Find the limiting processor resource. // Numbers have been pre-scaled to be comparable. @@ -1185,7 +1185,9 @@ unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { // Convert to cycle count. PRMax = TE.MTM.getCycles(PRMax); + /// All instructions before current block unsigned Instrs = TBI.InstrDepth; + // plus instructions in current block if (Bottom) Instrs += TE.MTM.BlockInfo[getBlockNum()].InstrCount; if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) @@ -1194,44 +1196,71 @@ unsigned MachineTraceMetrics::Trace::getResourceDepth(bool Bottom) const { return std::max(Instrs, PRMax); } - -unsigned MachineTraceMetrics::Trace:: -getResourceLength(ArrayRef Extrablocks, - ArrayRef ExtraInstrs) const { +unsigned MachineTraceMetrics::Trace::getResourceLength( + ArrayRef Extrablocks, + ArrayRef ExtraInstrs, + ArrayRef RemoveInstrs) const { // Add up resources above and below the center block. ArrayRef PRDepths = TE.getProcResourceDepths(getBlockNum()); ArrayRef PRHeights = TE.getProcResourceHeights(getBlockNum()); unsigned PRMax = 0; - for (unsigned K = 0; K != PRDepths.size(); ++K) { - unsigned PRCycles = PRDepths[K] + PRHeights[K]; - for (unsigned I = 0; I != Extrablocks.size(); ++I) - PRCycles += TE.MTM.getProcResourceCycles(Extrablocks[I]->getNumber())[K]; - for (unsigned I = 0; I != ExtraInstrs.size(); ++I) { - const MCSchedClassDesc* SC = ExtraInstrs[I]; + + // Capture computing cycles from extra instructions + auto extraCycles = [this](ArrayRef Instrs, + unsigned ResourceIdx) + ->unsigned { + unsigned Cycles = 0; + for (const MCSchedClassDesc *SC : Instrs) { if (!SC->isValid()) continue; for (TargetSchedModel::ProcResIter - PI = TE.MTM.SchedModel.getWriteProcResBegin(SC), - PE = TE.MTM.SchedModel.getWriteProcResEnd(SC); PI != PE; ++PI) { - if (PI->ProcResourceIdx != K) + PI = TE.MTM.SchedModel.getWriteProcResBegin(SC), + PE = TE.MTM.SchedModel.getWriteProcResEnd(SC); + PI != PE; ++PI) { + if (PI->ProcResourceIdx != ResourceIdx) continue; - PRCycles += (PI->Cycles * TE.MTM.SchedModel.getResourceFactor(K)); + Cycles += + (PI->Cycles * TE.MTM.SchedModel.getResourceFactor(ResourceIdx)); } } + return Cycles; + }; + + for (unsigned K = 0; K != PRDepths.size(); ++K) { + unsigned PRCycles = PRDepths[K] + PRHeights[K]; + for (const MachineBasicBlock *MBB : Extrablocks) + PRCycles += TE.MTM.getProcResourceCycles(MBB->getNumber())[K]; + PRCycles += extraCycles(ExtraInstrs, K); + PRCycles -= extraCycles(RemoveInstrs, K); PRMax = std::max(PRMax, PRCycles); } // Convert to cycle count. PRMax = TE.MTM.getCycles(PRMax); + // Instrs: #instructions in current trace outside current block. unsigned Instrs = TBI.InstrDepth + TBI.InstrHeight; - for (unsigned i = 0, e = Extrablocks.size(); i != e; ++i) - Instrs += TE.MTM.getResources(Extrablocks[i])->InstrCount; + // Add instruction count from the extra blocks. + for (const MachineBasicBlock *MBB : Extrablocks) + Instrs += TE.MTM.getResources(MBB)->InstrCount; + Instrs += ExtraInstrs.size(); + Instrs -= RemoveInstrs.size(); if (unsigned IW = TE.MTM.SchedModel.getIssueWidth()) Instrs /= IW; // Assume issue width 1 without a schedule model. return std::max(Instrs, PRMax); } +bool MachineTraceMetrics::Trace::isDepInTrace(const MachineInstr *DefMI, + const MachineInstr *UseMI) const { + if (DefMI->getParent() == UseMI->getParent()) + return true; + + const TraceBlockInfo &DepTBI = TE.BlockInfo[DefMI->getParent()->getNumber()]; + const TraceBlockInfo &TBI = TE.BlockInfo[UseMI->getParent()->getNumber()]; + + return DepTBI.isUsefulDominator(TBI); +} + void MachineTraceMetrics::Ensemble::print(raw_ostream &OS) const { OS << getName() << " ensemble:\n"; for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {