From 3c58ba8ea7ec097d69d7f7be5930a4a4d7405a18 Mon Sep 17 00:00:00 2001 From: Andrew Trick Date: Sat, 14 Jan 2012 02:17:18 +0000 Subject: [PATCH] misched: Initial code for building an MI level scheduling DAG git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@148174 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/MachineScheduler.cpp | 24 ++++---- lib/CodeGen/ScheduleDAG.cpp | 2 +- lib/CodeGen/ScheduleDAGInstrs.cpp | 94 ++++++++++++++++++++++++++++--- lib/CodeGen/ScheduleDAGInstrs.h | 14 ++++- 4 files changed, 113 insertions(+), 21 deletions(-) diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index e6ca0e847a3..df706cbec6d 100644 --- a/lib/CodeGen/MachineScheduler.cpp +++ b/lib/CodeGen/MachineScheduler.cpp @@ -214,22 +214,26 @@ bool MachineSchedulerPass::runOnMachineFunction(MachineFunction &mf) { // The next region starts above the previous region. Look backward in the // instruction stream until we find the nearest boundary. MachineBasicBlock::iterator I = RegionEnd; - for(;I != MBB->begin(); --I) { + for(;I != MBB->begin(); --I, --RemainingCount) { if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) break; } - if (I == RegionEnd || I == llvm::prior(RegionEnd)) { - // Skip empty or single instruction scheduling regions. + if (I == RegionEnd) { + // Skip empty scheduling regions. RegionEnd = llvm::prior(RegionEnd); + --RemainingCount; continue; } - DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() - << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: " - << *RegionEnd << " Remaining: " << RemainingCount << "\n"); - - // Inform ScheduleDAGInstrs of the region being scheduler. It calls back - // to our Schedule() method. - Scheduler->Run(MBB, I, RegionEnd, MBB->size()); + // Schedule regions with more than one instruction. + if (I != llvm::prior(RegionEnd)) { + DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName() + << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: " + << *RegionEnd << " Remaining: " << RemainingCount << "\n"); + + // Inform ScheduleDAGInstrs of the region being scheduled. It calls back + // to our Schedule() method. + Scheduler->Run(MBB, I, RegionEnd, MBB->size()); + } RegionEnd = I; } assert(RemainingCount == 0 && "Instruction count mismatch!"); diff --git a/lib/CodeGen/ScheduleDAG.cpp b/lib/CodeGen/ScheduleDAG.cpp index e829668b4c8..f92c72a47bc 100644 --- a/lib/CodeGen/ScheduleDAG.cpp +++ b/lib/CodeGen/ScheduleDAG.cpp @@ -321,7 +321,7 @@ void SUnit::dumpAll(const ScheduleDAG *G) const { dbgs() << " *"; dbgs() << ": Latency=" << I->getLatency(); if (I->isAssignedRegDep()) - dbgs() << " Reg=" << G->TRI->getName(I->getReg()); + dbgs() << " Reg=" << PrintReg(I->getReg()); dbgs() << "\n"; } } diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index 955fcc9f57b..b3349209a5d 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -166,8 +166,10 @@ void ScheduleDAGInstrs::AddSchedBarrierDeps() { unsigned Reg = MO.getReg(); if (Reg == 0) continue; - assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!"); - Uses[Reg].push_back(&ExitSU); + if (TRI->isPhysicalRegister(Reg)) + Uses[Reg].push_back(&ExitSU); + else + assert(!IsPostRA && "Virtual register encountered after regalloc."); } } else { // For others, e.g. fallthrough, conditional branch, assume the exit @@ -343,11 +345,73 @@ void ScheduleDAGInstrs::addPhysRegDeps(SUnit *SU, unsigned OperIdx) { } } -/// addVirtRegDeps - Add register dependencies (data, anti, and output) from -/// this SUnit to following instructions in the same scheduling region that -/// depend the virtual register referenced at OperIdx. -void ScheduleDAGInstrs::addVirtRegDeps(SUnit *SU, unsigned OperIdx) { - assert(false && "unimplemented"); +/// addVRegDefDeps - Add register output and data dependencies from this SUnit +/// to instructions that occur later in the same scheduling region if they read +/// from or write to the virtual register defined at OperIdx. +/// +/// TODO: Hoist loop induction variable increments. This has to be +/// reevaluated. Generally, IV scheduling should be done before coalescing. +void ScheduleDAGInstrs::addVRegDefDeps(SUnit *SU, unsigned OperIdx) { + const MachineInstr *MI = SU->getInstr(); + unsigned Reg = MI->getOperand(OperIdx).getReg(); + + const TargetSubtargetInfo &ST = TM.getSubtarget(); + + // Add output dependence to the next nearest def of this vreg. + // + // Unless this definition is dead, the output dependence should be + // transitively redundant with antidependencies from this definition's + // uses. We're conservative for now until we have a way to guarantee the uses + // are not eliminated sometime during scheduling. The output dependence edge + // is also useful if output latency exceeds def-use latency. + SUnit *DefSU = VRegDefs[Reg]; + if (DefSU && DefSU != SU && DefSU != &ExitSU) { + unsigned OutLatency = TII->getOutputLatency(InstrItins, MI, OperIdx, + DefSU->getInstr()); + DefSU->addPred(SDep(SU, SDep::Output, OutLatency, Reg)); + } + VRegDefs[Reg] = SU; + + // Add data dependence to any uses of this vreg before the next nearest def. + // + // TODO: Handle ExitSU properly. + // + // TODO: Data dependence could be handled more efficiently at the use-side. + std::vector &UseList = VRegUses[Reg]; + for (std::vector::const_iterator UI = UseList.begin(), + UE = UseList.end(); UI != UE; ++UI) { + SUnit *UseSU = *UI; + if (UseSU == SU) continue; + + // TODO: Handle "special" address latencies cleanly. + const SDep& dep = SDep(SU, SDep::Data, SU->Latency, Reg); + if (!UnitLatencies) { + // Adjust the dependence latency using operand def/use information, then + // allow the target to perform its own adjustments. + ComputeOperandLatency(SU, UseSU, const_cast(dep)); + ST.adjustSchedDependency(SU, UseSU, const_cast(dep)); + } + UseSU->addPred(dep); + } + UseList.clear(); +} + +/// addVRegUseDeps - Add register antidependencies from this SUnit to +/// instructions that occur later in the same scheduling region if they +/// write the virtual register referenced at OperIdx. +void ScheduleDAGInstrs::addVRegUseDeps(SUnit *SU, unsigned OperIdx) { + unsigned Reg = SU->getInstr()->getOperand(OperIdx).getReg(); + + // Add antidependence to the following def of the vreg it uses. + SUnit *DefSU = VRegDefs[Reg]; + if (DefSU && DefSU != SU) + DefSU->addPred(SDep(SU, SDep::Anti, 0, Reg)); + + // Add this SUnit to the use list of the vreg it uses. + // + // TODO: pinch the DAG before we see too many uses to avoid quadratic + // behavior. Limiting the scheduling window can accomplish the same thing. + VRegUses[Reg].push_back(SU); } void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { @@ -381,6 +445,15 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { assert(Defs[i].empty() && "Only BuildGraph should push/pop Defs"); } + // Reinitialize the large VReg vectors, while reusing the memory. + // + // Note: this can be an expensive part of DAG building. We may want to be more + // clever. Reevaluate after VRegUses goes away. + assert(VRegDefs.size() == 0 && VRegUses.size() == 0 && + "Only BuildSchedGraph should access VRegDefs/Uses"); + VRegDefs.resize(MF.getRegInfo().getNumVirtRegs()); + VRegUses.resize(MF.getRegInfo().getNumVirtRegs()); + // Walk the list of instructions, from bottom moving up. MachineInstr *PrevMI = NULL; for (MachineBasicBlock::iterator MII = InsertPos, MIE = Begin; @@ -420,7 +493,10 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { addPhysRegDeps(SU, j); else { assert(!IsPostRA && "Virtual register encountered!"); - addVirtRegDeps(SU, j); + if (MO.isDef()) + addVRegDefDeps(SU, j); + else + addVRegUseDeps(SU, j); } } @@ -578,6 +654,8 @@ void ScheduleDAGInstrs::BuildSchedGraph(AliasAnalysis *AA) { Defs[i].clear(); Uses[i].clear(); } + VRegDefs.clear(); + VRegUses.clear(); PendingLoads.clear(); } diff --git a/lib/CodeGen/ScheduleDAGInstrs.h b/lib/CodeGen/ScheduleDAGInstrs.h index 55da5c08181..17183644cc3 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.h +++ b/lib/CodeGen/ScheduleDAGInstrs.h @@ -20,6 +20,7 @@ #include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/Support/Compiler.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/ADT/IndexedMap.h" #include "llvm/ADT/SmallSet.h" #include @@ -107,7 +108,8 @@ namespace llvm { /// isPostRA flag indicates vregs cannot be present. bool IsPostRA; - /// UnitLatencies flag forces single-cycle data dependencies. + /// UnitLatencies (misnamed) flag avoids computing def-use latencies, using + /// the def-side latency only. bool UnitLatencies; /// Defs, Uses - Remember where defs and uses of each register are as we @@ -117,6 +119,13 @@ namespace llvm { std::vector > Defs; std::vector > Uses; + // Virtual register Defs and Uses. + // + // TODO: Eliminate VRegUses by creating SUnits in a prepass and looking up + // the live range's reaching def. + IndexedMap VRegDefs; + IndexedMap, VirtReg2IndexFunctor> VRegUses; + /// PendingLoads - Remember where unknown loads are after the most recent /// unknown store, as we iterate. As with Defs and Uses, this is here /// to minimize construction/destruction. @@ -211,7 +220,8 @@ namespace llvm { protected: void addPhysRegDeps(SUnit *SU, unsigned OperIdx); - void addVirtRegDeps(SUnit *SU, unsigned OperIdx); + void addVRegDefDeps(SUnit *SU, unsigned OperIdx); + void addVRegUseDeps(SUnit *SU, unsigned OperIdx); }; } -- 2.34.1