From 4ef10867499aa146cd819c78d8d37a8353d4f0ff Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Mon, 23 Jan 2006 07:01:07 +0000 Subject: [PATCH] Factor out more instruction scheduler code to the base class. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@25532 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/ScheduleDAG.h | 67 +++- lib/CodeGen/SelectionDAG/ScheduleDAG.cpp | 240 +++++++++++- .../SelectionDAG/ScheduleDAGSimple.cpp | 369 ++---------------- lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 30 +- 4 files changed, 364 insertions(+), 342 deletions(-) diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 37f33a1a2fc..41c4872773c 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -35,6 +35,14 @@ namespace llvm { typedef std::vector::iterator NIIterator; + // Scheduling heuristics + enum SchedHeuristics { + noScheduling, + simpleScheduling, + simpleNoItinScheduling + }; + + //===--------------------------------------------------------------------===// /// /// Node group - This struct is used to manage flagged node groups. @@ -45,7 +53,7 @@ namespace llvm { NodeInfo *Dominator; // Node with highest latency unsigned Latency; // Total latency of the group int Pending; // Number of visits pending before - // adding to order + // adding to order public: // Ctor. @@ -76,7 +84,6 @@ namespace llvm { } static void Add(NodeInfo *D, NodeInfo *U); - static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U); }; //===--------------------------------------------------------------------===// @@ -232,6 +239,7 @@ namespace llvm { class ScheduleDAG { public: + SchedHeuristics Heuristic; // Scheduling heuristic SelectionDAG &DAG; // DAG of the current basic block MachineBasicBlock *BB; // Current basic block const TargetMachine &TM; // Target processor @@ -240,10 +248,15 @@ namespace llvm { SSARegMap *RegMap; // Virtual/real register map MachineConstantPool *ConstPool; // Target constant pool std::map Map; // Map nodes to info + unsigned NodeCount; // Number of nodes in DAG + bool HasGroups; // True if there are any groups + NodeInfo *Info; // Info for nodes being scheduled + NIVector Ordering; // Emit ordering of nodes - ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, + ScheduleDAG(SchedHeuristics hstc, SelectionDAG &dag, MachineBasicBlock *bb, const TargetMachine &tm) - : DAG(dag), BB(bb), TM(tm) {} + : Heuristic(hstc), DAG(dag), BB(bb), TM(tm), + NodeCount(0), HasGroups(false), Info(NULL) {} virtual ~ScheduleDAG() {}; @@ -263,25 +276,61 @@ namespace llvm { return NI->VRBase + Op.ResNo; } + /// isPassiveNode - Return true if the node is a non-scheduled leaf. + /// + bool isPassiveNode(SDNode *Node) { + if (isa(Node)) return true; + if (isa(Node)) return true; + if (isa(Node)) return true; + if (isa(Node)) return true; + if (isa(Node)) return true; + if (isa(Node)) return true; + if (isa(Node)) return true; + return false; + } + + /// EmitNode - Generate machine code for an node and needed dependencies. + /// void EmitNode(NodeInfo *NI); + /// EmitAll - Emit all nodes in schedule sorted order. + /// + void EmitAll(); + + /// Schedule - Order nodes according to selected style. + /// virtual void Schedule() {}; - virtual void print(std::ostream &O) const {}; + /// printNI - Print node info. + /// + void printNI(std::ostream &O, NodeInfo *NI) const; + + /// printChanges - Hilight changes in order caused by scheduling. + /// + void printChanges(unsigned Index) const; + + /// print - Print ordering to specified output stream. + /// + void print(std::ostream &O) const; void dump(const char *tag) const; void dump() const; private: - unsigned CreateVirtualRegisters(MachineInstr *MI, - unsigned NumResults, - const TargetInstrDescriptor &II); + /// PrepareNodeInfo - Set up the basic minimum node info for scheduling. + /// + void PrepareNodeInfo(); + + /// IdentifyGroups - Put flagged nodes into groups. + /// + void IdentifyGroups(); }; /// createSimpleDAGScheduler - This creates a simple two pass instruction /// scheduler. - ScheduleDAG* createSimpleDAGScheduler(SelectionDAG &DAG, + ScheduleDAG* createSimpleDAGScheduler(SchedHeuristics Heuristic, + SelectionDAG &DAG, MachineBasicBlock *BB); } diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp index 9c1f1a8d636..0a4a1ac3f75 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp @@ -51,11 +51,51 @@ static unsigned CountOperands(SDNode *Node) { return N; } -/// CreateVirtualRegisters - Add result register values for things that are -/// defined by this instruction. -unsigned ScheduleDAG::CreateVirtualRegisters(MachineInstr *MI, - unsigned NumResults, - const TargetInstrDescriptor &II) { +/// PrepareNodeInfo - Set up the basic minimum node info for scheduling. +/// +void ScheduleDAG::PrepareNodeInfo() { + // Allocate node information + Info = new NodeInfo[NodeCount]; + + unsigned i = 0; + for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), + E = DAG.allnodes_end(); I != E; ++I, ++i) { + // Fast reference to node schedule info + NodeInfo* NI = &Info[i]; + // Set up map + Map[I] = NI; + // Set node + NI->Node = I; + // Set pending visit count + NI->setPending(I->use_size()); + } +} + +/// IdentifyGroups - Put flagged nodes into groups. +/// +void ScheduleDAG::IdentifyGroups() { + for (unsigned i = 0, N = NodeCount; i < N; i++) { + NodeInfo* NI = &Info[i]; + SDNode *Node = NI->Node; + + // For each operand (in reverse to only look at flags) + for (unsigned N = Node->getNumOperands(); 0 < N--;) { + // Get operand + SDOperand Op = Node->getOperand(N); + // No more flags to walk + if (Op.getValueType() != MVT::Flag) break; + // Add to node group + NodeGroup::Add(getNI(Op.Val), NI); + // Let evryone else know + HasGroups = true; + } + } +} + +static unsigned CreateVirtualRegisters(MachineInstr *MI, + unsigned NumResults, + SSARegMap *RegMap, + const TargetInstrDescriptor &II) { // Create the result registers for this node and add the result regs to // the machine instruction. const TargetOperandInfo *OpInfo = II.OpInfo; @@ -114,7 +154,7 @@ void ScheduleDAG::EmitNode(NodeInfo *NI) { // Otherwise, create new virtual registers. if (NumResults && VRBase == 0) - VRBase = CreateVirtualRegisters(MI, NumResults, II); + VRBase = CreateVirtualRegisters(MI, NumResults, RegMap, II); // Emit all of the actual operands of this instruction, adding them to the // instruction as appropriate. @@ -250,6 +290,112 @@ void ScheduleDAG::EmitNode(NodeInfo *NI) { NI->VRBase = VRBase; } +/// EmitAll - Emit all nodes in schedule sorted order. +/// +void ScheduleDAG::EmitAll() { + // For each node in the ordering + for (unsigned i = 0, N = Ordering.size(); i < N; i++) { + // Get the scheduling info + NodeInfo *NI = Ordering[i]; + if (NI->isInGroup()) { + NodeGroupIterator NGI(Ordering[i]); + while (NodeInfo *NI = NGI.next()) EmitNode(NI); + } else { + EmitNode(NI); + } + } +} + +/// isFlagDefiner - Returns true if the node defines a flag result. +static bool isFlagDefiner(SDNode *A) { + unsigned N = A->getNumValues(); + return N && A->getValueType(N - 1) == MVT::Flag; +} + +/// isFlagUser - Returns true if the node uses a flag result. +/// +static bool isFlagUser(SDNode *A) { + unsigned N = A->getNumOperands(); + return N && A->getOperand(N - 1).getValueType() == MVT::Flag; +} + +/// printNI - Print node info. +/// +void ScheduleDAG::printNI(std::ostream &O, NodeInfo *NI) const { +#ifndef NDEBUG + SDNode *Node = NI->Node; + O << " " + << std::hex << Node << std::dec + << ", Lat=" << NI->Latency + << ", Slot=" << NI->Slot + << ", ARITY=(" << Node->getNumOperands() << "," + << Node->getNumValues() << ")" + << " " << Node->getOperationName(&DAG); + if (isFlagDefiner(Node)) O << "<#"; + if (isFlagUser(Node)) O << ">#"; +#endif +} + +/// printChanges - Hilight changes in order caused by scheduling. +/// +void ScheduleDAG::printChanges(unsigned Index) const { +#ifndef NDEBUG + // Get the ordered node count + unsigned N = Ordering.size(); + // Determine if any changes + unsigned i = 0; + for (; i < N; i++) { + NodeInfo *NI = Ordering[i]; + if (NI->Preorder != i) break; + } + + if (i < N) { + std::cerr << Index << ". New Ordering\n"; + + for (i = 0; i < N; i++) { + NodeInfo *NI = Ordering[i]; + std::cerr << " " << NI->Preorder << ". "; + printNI(std::cerr, NI); + std::cerr << "\n"; + if (NI->isGroupDominator()) { + NodeGroup *Group = NI->Group; + for (NIIterator NII = Group->group_begin(), E = Group->group_end(); + NII != E; NII++) { + std::cerr << " "; + printNI(std::cerr, *NII); + std::cerr << "\n"; + } + } + } + } else { + std::cerr << Index << ". No Changes\n"; + } +#endif +} + +/// print - Print ordering to specified output stream. +/// +void ScheduleDAG::print(std::ostream &O) const { +#ifndef NDEBUG + using namespace std; + O << "Ordering\n"; + for (unsigned i = 0, N = Ordering.size(); i < N; i++) { + NodeInfo *NI = Ordering[i]; + printNI(O, NI); + O << "\n"; + if (NI->isGroupDominator()) { + NodeGroup *Group = NI->Group; + for (NIIterator NII = Group->group_begin(), E = Group->group_end(); + NII != E; NII++) { + O << " "; + printNI(O, *NII); + O << "\n"; + } + } + } +#endif +} + void ScheduleDAG::dump(const char *tag) const { std::cerr << tag; dump(); } @@ -265,6 +411,88 @@ MachineBasicBlock *ScheduleDAG::Run() { MRI = TM.getRegisterInfo(); RegMap = BB->getParent()->getSSARegMap(); ConstPool = BB->getParent()->getConstantPool(); + + // Number the nodes + NodeCount = std::distance(DAG.allnodes_begin(), DAG.allnodes_end()); + // Set up minimum info for scheduling + PrepareNodeInfo(); + // Construct node groups for flagged nodes + IdentifyGroups(); + Schedule(); return BB; } + + +/// CountInternalUses - Returns the number of edges between the two nodes. +/// +static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U) { + unsigned N = 0; + for (unsigned M = U->Node->getNumOperands(); 0 < M--;) { + SDOperand Op = U->Node->getOperand(M); + if (Op.Val == D->Node) N++; + } + + return N; +} + +//===----------------------------------------------------------------------===// +/// Add - Adds a definer and user pair to a node group. +/// +void NodeGroup::Add(NodeInfo *D, NodeInfo *U) { + // Get current groups + NodeGroup *DGroup = D->Group; + NodeGroup *UGroup = U->Group; + // If both are members of groups + if (DGroup && UGroup) { + // There may have been another edge connecting + if (DGroup == UGroup) return; + // Add the pending users count + DGroup->addPending(UGroup->getPending()); + // For each member of the users group + NodeGroupIterator UNGI(U); + while (NodeInfo *UNI = UNGI.next() ) { + // Change the group + UNI->Group = DGroup; + // For each member of the definers group + NodeGroupIterator DNGI(D); + while (NodeInfo *DNI = DNGI.next() ) { + // Remove internal edges + DGroup->addPending(-CountInternalUses(DNI, UNI)); + } + } + // Merge the two lists + DGroup->group_insert(DGroup->group_end(), + UGroup->group_begin(), UGroup->group_end()); + } else if (DGroup) { + // Make user member of definers group + U->Group = DGroup; + // Add users uses to definers group pending + DGroup->addPending(U->Node->use_size()); + // For each member of the definers group + NodeGroupIterator DNGI(D); + while (NodeInfo *DNI = DNGI.next() ) { + // Remove internal edges + DGroup->addPending(-CountInternalUses(DNI, U)); + } + DGroup->group_push_back(U); + } else if (UGroup) { + // Make definer member of users group + D->Group = UGroup; + // Add definers uses to users group pending + UGroup->addPending(D->Node->use_size()); + // For each member of the users group + NodeGroupIterator UNGI(U); + while (NodeInfo *UNI = UNGI.next() ) { + // Remove internal edges + UGroup->addPending(-CountInternalUses(D, UNI)); + } + UGroup->group_insert(UGroup->group_begin(), D); + } else { + D->Group = U->Group = DGroup = new NodeGroup(); + DGroup->addPending(D->Node->use_size() + U->Node->use_size() - + CountInternalUses(D, U)); + DGroup->group_push_back(D); + DGroup->group_push_back(U); + } +} diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp index b22eae499a9..97d2602ba5b 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSimple.cpp @@ -21,32 +21,8 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include -#include -#include using namespace llvm; -namespace { - // Style of scheduling to use. - enum ScheduleChoices { - noScheduling, - simpleScheduling, - simpleNoItinScheduling - }; -} // namespace - -cl::opt ScheduleStyle("sched", - cl::desc("Choose scheduling style"), - cl::init(noScheduling), - cl::values( - clEnumValN(noScheduling, "none", - "Trivial emission with no analysis"), - clEnumValN(simpleScheduling, "simple", - "Minimize critical path and maximize processor utilization"), - clEnumValN(simpleNoItinScheduling, "simple-noitin", - "Same as simple except using generic latency"), - clEnumValEnd)); - - namespace { //===----------------------------------------------------------------------===// /// @@ -212,10 +188,6 @@ public: /// class ScheduleDAGSimple : public ScheduleDAG { private: - unsigned NodeCount; // Number of nodes in DAG - bool HasGroups; // True if there are any groups - NodeInfo *Info; // Info for nodes being scheduled - NIVector Ordering; // Emit ordering of nodes ResourceTally Tally; // Resource usage tally unsigned NSlots; // Total latency static const unsigned NotFound = ~0U; // Search marker @@ -223,10 +195,9 @@ private: public: // Ctor. - ScheduleDAGSimple(SelectionDAG &dag, MachineBasicBlock *bb, - const TargetMachine &tm) - : ScheduleDAG(dag, bb, tm), - NodeCount(0), HasGroups(false), Info(NULL), Tally(), NSlots(0) { + ScheduleDAGSimple(SchedHeuristics hstc, SelectionDAG &dag, + MachineBasicBlock *bb, const TargetMachine &tm) + : ScheduleDAG(hstc, dag, bb, tm), Tally(), NSlots(0) { assert(&TII && "Target doesn't provide instr info?"); assert(&MRI && "Target doesn't provide register info?"); } @@ -234,29 +205,18 @@ public: virtual ~ScheduleDAGSimple() {}; private: - static bool isFlagDefiner(SDNode *A); - static bool isFlagUser(SDNode *A); static bool isDefiner(NodeInfo *A, NodeInfo *B); - static bool isPassiveNode(SDNode *Node); void IncludeNode(NodeInfo *NI); void VisitAll(); void Schedule(); - void IdentifyGroups(); void GatherSchedulingInfo(); void FakeGroupDominators(); - void PrepareNodeInfo(); bool isStrongDependency(NodeInfo *A, NodeInfo *B); bool isWeakDependency(NodeInfo *A, NodeInfo *B); void ScheduleBackward(); void ScheduleForward(); - void EmitAll(); - - void printChanges(unsigned Index); - void printSI(std::ostream &O, NodeInfo *NI) const; - void print(std::ostream &O) const; }; - //===----------------------------------------------------------------------===// /// Special case itineraries. /// @@ -275,103 +235,12 @@ static InstrStage IntStage = { 2, RSInteger }; static InstrStage FloatStage = { 3, RSFloat }; //===----------------------------------------------------------------------===// - -//===----------------------------------------------------------------------===// - } // namespace //===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===// -/// Add - Adds a definer and user pair to a node group. -/// -void NodeGroup::Add(NodeInfo *D, NodeInfo *U) { - // Get current groups - NodeGroup *DGroup = D->Group; - NodeGroup *UGroup = U->Group; - // If both are members of groups - if (DGroup && UGroup) { - // There may have been another edge connecting - if (DGroup == UGroup) return; - // Add the pending users count - DGroup->addPending(UGroup->getPending()); - // For each member of the users group - NodeGroupIterator UNGI(U); - while (NodeInfo *UNI = UNGI.next() ) { - // Change the group - UNI->Group = DGroup; - // For each member of the definers group - NodeGroupIterator DNGI(D); - while (NodeInfo *DNI = DNGI.next() ) { - // Remove internal edges - DGroup->addPending(-CountInternalUses(DNI, UNI)); - } - } - // Merge the two lists - DGroup->group_insert(DGroup->group_end(), - UGroup->group_begin(), UGroup->group_end()); - } else if (DGroup) { - // Make user member of definers group - U->Group = DGroup; - // Add users uses to definers group pending - DGroup->addPending(U->Node->use_size()); - // For each member of the definers group - NodeGroupIterator DNGI(D); - while (NodeInfo *DNI = DNGI.next() ) { - // Remove internal edges - DGroup->addPending(-CountInternalUses(DNI, U)); - } - DGroup->group_push_back(U); - } else if (UGroup) { - // Make definer member of users group - D->Group = UGroup; - // Add definers uses to users group pending - UGroup->addPending(D->Node->use_size()); - // For each member of the users group - NodeGroupIterator UNGI(U); - while (NodeInfo *UNI = UNGI.next() ) { - // Remove internal edges - UGroup->addPending(-CountInternalUses(D, UNI)); - } - UGroup->group_insert(UGroup->group_begin(), D); - } else { - D->Group = U->Group = DGroup = new NodeGroup(); - DGroup->addPending(D->Node->use_size() + U->Node->use_size() - - CountInternalUses(D, U)); - DGroup->group_push_back(D); - DGroup->group_push_back(U); - } -} - -/// CountInternalUses - Returns the number of edges between the two nodes. -/// -unsigned NodeGroup::CountInternalUses(NodeInfo *D, NodeInfo *U) { - unsigned N = 0; - for (unsigned M = U->Node->getNumOperands(); 0 < M--;) { - SDOperand Op = U->Node->getOperand(M); - if (Op.Val == D->Node) N++; - } - - return N; -} -//===----------------------------------------------------------------------===// - - -//===----------------------------------------------------------------------===// -/// isFlagDefiner - Returns true if the node defines a flag result. -bool ScheduleDAGSimple::isFlagDefiner(SDNode *A) { - unsigned N = A->getNumValues(); - return N && A->getValueType(N - 1) == MVT::Flag; -} - -/// isFlagUser - Returns true if the node uses a flag result. -/// -bool ScheduleDAGSimple::isFlagUser(SDNode *A) { - unsigned N = A->getNumOperands(); - return N && A->getOperand(N - 1).getValueType() == MVT::Flag; -} - /// isDefiner - Return true if node A is a definer for B. /// bool ScheduleDAGSimple::isDefiner(NodeInfo *A, NodeInfo *B) { @@ -391,19 +260,6 @@ bool ScheduleDAGSimple::isDefiner(NodeInfo *A, NodeInfo *B) { return false; } -/// isPassiveNode - Return true if the node is a non-scheduled leaf. -/// -bool ScheduleDAGSimple::isPassiveNode(SDNode *Node) { - if (isa(Node)) return true; - if (isa(Node)) return true; - if (isa(Node)) return true; - if (isa(Node)) return true; - if (isa(Node)) return true; - if (isa(Node)) return true; - if (isa(Node)) return true; - return false; -} - /// IncludeNode - Add node to NodeInfo vector. /// void ScheduleDAGSimple::IncludeNode(NodeInfo *NI) { @@ -432,62 +288,6 @@ void ScheduleDAGSimple::IncludeNode(NodeInfo *NI) { NI->setPending(Count); } -/// VisitAll - Visit each node breadth-wise to produce an initial ordering. -/// Note that the ordering in the Nodes vector is reversed. -void ScheduleDAGSimple::VisitAll() { - // Add first element to list - NodeInfo *NI = getNI(DAG.getRoot().Val); - if (NI->isInGroup()) { - Ordering.push_back(NI->Group->getDominator()); - } else { - Ordering.push_back(NI); - } - - // Iterate through all nodes that have been added - for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies - // Visit all operands - NodeGroupOpIterator NGI(Ordering[i]); - while (!NGI.isEnd()) { - // Get next operand - SDOperand Op = NGI.next(); - // Get node - SDNode *Node = Op.Val; - // Ignore passive nodes - if (isPassiveNode(Node)) continue; - // Check out node - IncludeNode(getNI(Node)); - } - } - - // Add entry node last (IncludeNode filters entry nodes) - if (DAG.getEntryNode().Val != DAG.getRoot().Val) - Ordering.push_back(getNI(DAG.getEntryNode().Val)); - - // Reverse the order - std::reverse(Ordering.begin(), Ordering.end()); -} - -/// IdentifyGroups - Put flagged nodes into groups. -/// -void ScheduleDAGSimple::IdentifyGroups() { - for (unsigned i = 0, N = NodeCount; i < N; i++) { - NodeInfo* NI = &Info[i]; - SDNode *Node = NI->Node; - - // For each operand (in reverse to only look at flags) - for (unsigned N = Node->getNumOperands(); 0 < N--;) { - // Get operand - SDOperand Op = Node->getOperand(N); - // No more flags to walk - if (Op.getValueType() != MVT::Flag) break; - // Add to node group - NodeGroup::Add(getNI(Op.Val), NI); - // Let evryone else know - HasGroups = true; - } - } -} - /// GatherSchedulingInfo - Get latency and resource information about each node. /// void ScheduleDAGSimple::GatherSchedulingInfo() { @@ -501,7 +301,7 @@ void ScheduleDAGSimple::GatherSchedulingInfo() { SDNode *Node = NI->Node; // If there are itineraries and it is a machine instruction - if (InstrItins.isEmpty() || ScheduleStyle == simpleNoItinScheduling) { + if (InstrItins.isEmpty() || Heuristic == simpleNoItinScheduling) { // If machine opcode if (Node->isTargetOpcode()) { // Get return type to guess which processing unit @@ -572,6 +372,41 @@ void ScheduleDAGSimple::GatherSchedulingInfo() { } } +/// VisitAll - Visit each node breadth-wise to produce an initial ordering. +/// Note that the ordering in the Nodes vector is reversed. +void ScheduleDAGSimple::VisitAll() { + // Add first element to list + NodeInfo *NI = getNI(DAG.getRoot().Val); + if (NI->isInGroup()) { + Ordering.push_back(NI->Group->getDominator()); + } else { + Ordering.push_back(NI); + } + + // Iterate through all nodes that have been added + for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies + // Visit all operands + NodeGroupOpIterator NGI(Ordering[i]); + while (!NGI.isEnd()) { + // Get next operand + SDOperand Op = NGI.next(); + // Get node + SDNode *Node = Op.Val; + // Ignore passive nodes + if (isPassiveNode(Node)) continue; + // Check out node + IncludeNode(getNI(Node)); + } + } + + // Add entry node last (IncludeNode filters entry nodes) + if (DAG.getEntryNode().Val != DAG.getRoot().Val) + Ordering.push_back(getNI(DAG.getEntryNode().Val)); + + // Reverse the order + std::reverse(Ordering.begin(), Ordering.end()); +} + /// FakeGroupDominators - Set dominators for non-scheduling. /// void ScheduleDAGSimple::FakeGroupDominators() { @@ -588,26 +423,6 @@ void ScheduleDAGSimple::FakeGroupDominators() { } } -/// PrepareNodeInfo - Set up the basic minimum node info for scheduling. -/// -void ScheduleDAGSimple::PrepareNodeInfo() { - // Allocate node information - Info = new NodeInfo[NodeCount]; - - unsigned i = 0; - for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(), - E = DAG.allnodes_end(); I != E; ++I, ++i) { - // Fast reference to node schedule info - NodeInfo* NI = &Info[i]; - // Set up map - Map[I] = NI; - // Set node - NI->Node = I; - // Set pending visit count - NI->setPending(I->use_size()); - } -} - /// isStrongDependency - Return true if node A has results used by node B. /// I.E., B must wait for latency of A. bool ScheduleDAGSimple::isStrongDependency(NodeInfo *A, NodeInfo *B) { @@ -742,34 +557,11 @@ void ScheduleDAGSimple::ScheduleForward() { } } -/// EmitAll - Emit all nodes in schedule sorted order. -/// -void ScheduleDAGSimple::EmitAll() { - // For each node in the ordering - for (unsigned i = 0, N = Ordering.size(); i < N; i++) { - // Get the scheduling info - NodeInfo *NI = Ordering[i]; - if (NI->isInGroup()) { - NodeGroupIterator NGI(Ordering[i]); - while (NodeInfo *NI = NGI.next()) EmitNode(NI); - } else { - EmitNode(NI); - } - } -} - /// Schedule - Order nodes according to selected style. /// void ScheduleDAGSimple::Schedule() { - // Number the nodes - NodeCount = std::distance(DAG.allnodes_begin(), DAG.allnodes_end()); // Test to see if scheduling should occur - bool ShouldSchedule = NodeCount > 3 && ScheduleStyle != noScheduling; - // Set up minimum info for scheduling - PrepareNodeInfo(); - // Construct node groups for flagged nodes - IdentifyGroups(); - + bool ShouldSchedule = NodeCount > 3 && Heuristic != noScheduling; // Don't waste time if is only entry and return if (ShouldSchedule) { // Get latency and resource requirements @@ -806,86 +598,11 @@ void ScheduleDAGSimple::Schedule() { EmitAll(); } -/// printChanges - Hilight changes in order caused by scheduling. -/// -void ScheduleDAGSimple::printChanges(unsigned Index) { -#ifndef NDEBUG - // Get the ordered node count - unsigned N = Ordering.size(); - // Determine if any changes - unsigned i = 0; - for (; i < N; i++) { - NodeInfo *NI = Ordering[i]; - if (NI->Preorder != i) break; - } - - if (i < N) { - std::cerr << Index << ". New Ordering\n"; - - for (i = 0; i < N; i++) { - NodeInfo *NI = Ordering[i]; - std::cerr << " " << NI->Preorder << ". "; - printSI(std::cerr, NI); - std::cerr << "\n"; - if (NI->isGroupDominator()) { - NodeGroup *Group = NI->Group; - for (NIIterator NII = Group->group_begin(), E = Group->group_end(); - NII != E; NII++) { - std::cerr << " "; - printSI(std::cerr, *NII); - std::cerr << "\n"; - } - } - } - } else { - std::cerr << Index << ". No Changes\n"; - } -#endif -} - -/// printSI - Print schedule info. -/// -void ScheduleDAGSimple::printSI(std::ostream &O, NodeInfo *NI) const { -#ifndef NDEBUG - SDNode *Node = NI->Node; - O << " " - << std::hex << Node << std::dec - << ", Lat=" << NI->Latency - << ", Slot=" << NI->Slot - << ", ARITY=(" << Node->getNumOperands() << "," - << Node->getNumValues() << ")" - << " " << Node->getOperationName(&DAG); - if (isFlagDefiner(Node)) O << "<#"; - if (isFlagUser(Node)) O << ">#"; -#endif -} - -/// print - Print ordering to specified output stream. -/// -void ScheduleDAGSimple::print(std::ostream &O) const { -#ifndef NDEBUG - using namespace std; - O << "Ordering\n"; - for (unsigned i = 0, N = Ordering.size(); i < N; i++) { - NodeInfo *NI = Ordering[i]; - printSI(O, NI); - O << "\n"; - if (NI->isGroupDominator()) { - NodeGroup *Group = NI->Group; - for (NIIterator NII = Group->group_begin(), E = Group->group_end(); - NII != E; NII++) { - O << " "; - printSI(O, *NII); - O << "\n"; - } - } - } -#endif -} /// createSimpleDAGScheduler - This creates a simple two pass instruction /// scheduler. -llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(SelectionDAG &DAG, +llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(SchedHeuristics Heuristic, + SelectionDAG &DAG, MachineBasicBlock *BB) { - return new ScheduleDAGSimple(DAG, BB, DAG.getTarget()); + return new ScheduleDAGSimple(Heuristic, DAG, BB, DAG.getTarget()); } diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 7e20f091b22..aa410bd0a6b 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -54,6 +54,25 @@ static const bool ViewISelDAGs = 0; static const bool ViewSchedDAGs = 0; #endif +namespace { + cl::opt + ISHeuristic( + "sched", + cl::desc("Choose scheduling style"), + cl::init(noScheduling), + cl::values( + clEnumValN(noScheduling, "none", + "No scheduling: breath first sequencing"), + clEnumValN(simpleScheduling, "simple", + "Simple two pass scheduling: minimize critical path " + "and maximize processor utilization"), + clEnumValN(simpleNoItinScheduling, "simple-noitin", + "Simple two pass scheduling: Same as simple " + "except using generic latency"), + clEnumValEnd)); +} // namespace + + namespace llvm { //===--------------------------------------------------------------------===// /// FunctionLoweringInfo - This contains information that is global to a @@ -1747,6 +1766,15 @@ void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, /// target node in the graph. void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) { if (ViewSchedDAGs) DAG.viewGraph(); - ScheduleDAG *SL = createSimpleDAGScheduler(DAG, BB); + ScheduleDAG *SL = NULL; + + switch (ISHeuristic) { + default: assert(0 && "Unrecognized scheduling heuristic"); + case noScheduling: + case simpleScheduling: + case simpleNoItinScheduling: + SL = createSimpleDAGScheduler(ISHeuristic, DAG, BB); + break; + } BB = SL->Run(); } -- 2.34.1