From ad0f78ace25ebc5a9597c189b0a797331f350fea Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 5 Mar 2006 22:45:01 +0000 Subject: [PATCH] Add basic hazard recognizer support. noop insertion isn't complete yet though. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@26558 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp | 119 ++++++++++++++++--- 1 file changed, 104 insertions(+), 15 deletions(-) diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index 447beffcc33..79206365f3d 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -160,6 +160,52 @@ struct ls_rr_sort : public std::binary_function { } }; + +/// HazardRecognizer - This determines whether or not an instruction can be +/// issued this cycle, and whether or not a noop needs to be inserted to handle +/// the hazard. +namespace { + class HazardRecognizer { + public: + virtual ~HazardRecognizer() {} + + enum HazardType { + NoHazard, // This instruction can be emitted at this cycle. + Hazard, // This instruction can't be emitted at this cycle. + NoopHazard, // This instruction can't be emitted, and needs noops. + }; + + /// getHazardType - Return the hazard type of emitting this node. There are + /// three possible results. Either: + /// * NoHazard: it is legal to issue this instruction on this cycle. + /// * Hazard: issuing this instruction would stall the machine. If some + /// other instruction is available, issue it first. + /// * NoopHazard: issuing this instruction would break the program. If + /// some other instruction can be issued, do so, otherwise issue a noop. + virtual HazardType getHazardType(SDNode *Node) { + return NoHazard; + } + + /// EmitInstruction - This callback is invoked when an instruction is + /// emitted, to advance the hazard state. + virtual void EmitInstruction(SDNode *Node) { + } + + /// AdvanceCycle - This callback is invoked when no instructions can be + /// issued on this cycle without a hazard. This should increment the + /// internal state of the hazard recognizer so that previously "Hazard" + /// instructions will now not be hazards. + virtual void AdvanceCycle() { + } + + /// EmitNoop - This callback is invoked when a noop was added to the + /// instruction stream. + virtual void EmitNoop() { + } + }; +} + + /// ScheduleDAGList - List scheduler. class ScheduleDAGList : public ScheduleDAG { private: @@ -176,14 +222,21 @@ private: /// it is top-down. bool isBottomUp; + /// HazardRec - The hazard recognizer to use. + HazardRecognizer *HazardRec; + typedef std::priority_queue, ls_rr_sort> AvailableQueueTy; public: ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb, - const TargetMachine &tm, bool isbottomup) + const TargetMachine &tm, bool isbottomup, + HazardRecognizer *HR = 0) : ScheduleDAG(listSchedulingBURR, dag, bb, tm), - CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL), isBottomUp(isbottomup) {} + CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL), isBottomUp(isbottomup) { + if (HR == 0) HR = new HazardRecognizer(); + HazardRec = HR; + } ~ScheduleDAGList() { SUnit *SU = HeadSUnit; @@ -192,6 +245,8 @@ public: delete SU; SU = NextSU; } + + delete HazardRec; } void Schedule(); @@ -411,7 +466,8 @@ void ScheduleDAGList::ListScheduleTopDown() { // Emit the entry node first. SUnit *Entry = SUnitMap[DAG.getEntryNode().Val]; ScheduleNodeTopDown(Available, Entry); - + HazardRec->EmitInstruction(Entry->Node); + // All leaves to Available queue. for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) { // It is available if it has no predecessors. @@ -423,23 +479,46 @@ void ScheduleDAGList::ListScheduleTopDown() { // priority. If it is not ready put it back. Schedule the node. std::vector NotReady; while (!Available.empty()) { - SUnit *CurrNode = Available.top(); - Available.pop(); - - // FIXME: when priorities make sense, reenable this. - while (0 && !isReady(CurrNode, CurrCycle)) { - NotReady.push_back(CurrNode); - CurrNode = Available.top(); - Available.pop(); - } + SUnit *FoundNode = 0; + bool HasNoopHazards = false; + do { + SUnit *CurrNode = Available.top(); + Available.pop(); + HazardRecognizer::HazardType HT = + HazardRec->getHazardType(CurrNode->Node); + if (HT == HazardRecognizer::NoHazard) { + FoundNode = CurrNode; + break; + } + + // Remember if this is a noop hazard. + HasNoopHazards |= HT == HazardRecognizer::NoopHazard; + + NotReady.push_back(CurrNode); + } while (!Available.empty()); + // Add the nodes that aren't ready back onto the available list. while (!NotReady.empty()) { Available.push(NotReady.back()); NotReady.pop_back(); } - - ScheduleNodeTopDown(Available, CurrNode); + + // If we found a node to schedule, do it now. + if (FoundNode) { + ScheduleNodeTopDown(Available, FoundNode); + HazardRec->EmitInstruction(FoundNode->Node); + } else if (!HasNoopHazards) { + // Otherwise, we have a pipeline stall, but no other problem, just advance + // the current cycle and try again. + HazardRec->AdvanceCycle(); + } else { + // Otherwise, we have no instructions to issue and we have instructions + // that will fault if we don't do this right. This is the case for + // processors without pipeline interlocks and other cases. + HazardRec->EmitNoop(); + // FIXME: Add a noop to the schedule!! + } } #ifndef NDEBUG @@ -651,10 +730,20 @@ llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG, return new ScheduleDAGList(DAG, BB, DAG.getTarget(), true); } +/// G5HazardRecognizer - A hazard recognizer for the PowerPC G5 processor. +/// FIXME: Implement +/// FIXME: Move to the PowerPC backend. +class G5HazardRecognizer : public HazardRecognizer { +public: + G5HazardRecognizer() {} +}; + + /// createTDG5ListDAGScheduler - This creates a top-down list scheduler for /// the PowerPC G5. FIXME: pull the priority function out into the PPC /// backend! ScheduleDAG* llvm::createTDG5ListDAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB) { - return new ScheduleDAGList(DAG, BB, DAG.getTarget(), false); + return new ScheduleDAGList(DAG, BB, DAG.getTarget(), false, + new G5HazardRecognizer()); } -- 2.34.1