X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSelectionDAG%2FScheduleDAG.cpp;h=f506b3ebfba4c0f4de846874c02e8801799739ab;hb=534bcfb270d25d2a29759d19981443fee7260e94;hp=3ad59d77ee40b7ebc31472abcde9829be4137b47;hpb=f65d917f71690dfc0e10f8d8d7672f3c2a84837e;p=oota-llvm.git diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp index 3ad59d77ee4..f506b3ebfba 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp @@ -1,9 +1,9 @@ -//===-- ScheduleDAG.cpp - Implement a trivial DAG scheduler ---------------===// +//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// // // The LLVM Compiler Infrastructure // -// This file was developed by James M. Laskey and is distributed under the -// University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -13,1149 +13,700 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "sched" +#define DEBUG_TYPE "pre-RA-sched" +#include "llvm/Type.h" +#include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineFunction.h" -#include "llvm/CodeGen/SelectionDAGISel.h" -#include "llvm/CodeGen/SelectionDAG.h" -#include "llvm/CodeGen/SSARegMap.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Target/TargetData.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetInstrItineraries.h" #include "llvm/Target/TargetLowering.h" -#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" -#include -#include -#include +#include "llvm/Support/MathExtras.h" 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)); - - -#ifndef NDEBUG -static cl::opt -ViewDAGs("view-sched-dags", cl::Hidden, - cl::desc("Pop up a window to show sched dags as they are processed")); -#else -static const bool ViewDAGs = 0; -#endif - -namespace { -//===----------------------------------------------------------------------===// -/// -/// BitsIterator - Provides iteration through individual bits in a bit vector. -/// -template -class BitsIterator { -private: - T Bits; // Bits left to iterate through +ScheduleDAG::ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, + const TargetMachine &tm) + : DAG(dag), BB(bb), TM(tm), RegInfo(BB->getParent()->getRegInfo()) { + TII = TM.getInstrInfo(); + MRI = TM.getRegisterInfo(); + ConstPool = BB->getParent()->getConstantPool(); +} -public: - /// Ctor. - BitsIterator(T Initial) : Bits(Initial) {} - - /// Next - Returns the next bit set or zero if exhausted. - inline T Next() { - // Get the rightmost bit set - T Result = Bits & -Bits; - // Remove from rest - Bits &= ~Result; - // Return single bit or zero - return Result; +/// CheckForPhysRegDependency - Check if the dependency between def and use of +/// a specified operand is a physical register dependency. If so, returns the +/// register and the cost of copying the register. +static void CheckForPhysRegDependency(SDNode *Def, SDNode *Use, unsigned Op, + const MRegisterInfo *MRI, + const TargetInstrInfo *TII, + unsigned &PhysReg, int &Cost) { + if (Op != 2 || Use->getOpcode() != ISD::CopyToReg) + return; + + unsigned Reg = cast(Use->getOperand(1))->getReg(); + if (MRegisterInfo::isVirtualRegister(Reg)) + return; + + unsigned ResNo = Use->getOperand(2).ResNo; + if (Def->isTargetOpcode()) { + const TargetInstrDescriptor &II = TII->get(Def->getTargetOpcode()); + if (ResNo >= II.numDefs && + II.ImplicitDefs[ResNo - II.numDefs] == Reg) { + PhysReg = Reg; + const TargetRegisterClass *RC = + MRI->getPhysicalRegisterRegClass(Def->getValueType(ResNo), Reg); + Cost = RC->getCopyCost(); + } } -}; - -//===----------------------------------------------------------------------===// +} +SUnit *ScheduleDAG::Clone(SUnit *Old) { + SUnit *SU = NewSUnit(Old->Node); + for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) + SU->FlaggedNodes.push_back(SU->FlaggedNodes[i]); + SU->InstanceNo = SUnitMap[Old->Node].size(); + SU->Latency = Old->Latency; + SU->isTwoAddress = Old->isTwoAddress; + SU->isCommutable = Old->isCommutable; + SU->hasPhysRegDefs = Old->hasPhysRegDefs; + SUnitMap[Old->Node].push_back(SU); + return SU; +} -//===----------------------------------------------------------------------===// -/// -/// ResourceTally - Manages the use of resources over time intervals. Each -/// item (slot) in the tally vector represents the resources used at a given -/// moment. A bit set to 1 indicates that a resource is in use, otherwise -/// available. An assumption is made that the tally is large enough to schedule -/// all current instructions (asserts otherwise.) -/// -template -class ResourceTally { -private: - std::vector Tally; // Resources used per slot - typedef typename std::vector::iterator Iter; - // Tally iterator + +/// BuildSchedUnits - Build SUnits from the selection dag that we are input. +/// This SUnit graph is similar to the SelectionDAG, but represents flagged +/// together nodes with a single SUnit. +void ScheduleDAG::BuildSchedUnits() { + // Reserve entries in the vector for each of the SUnits we are creating. This + // ensure that reallocation of the vector won't happen, so SUnit*'s won't get + // invalidated. + SUnits.reserve(std::distance(DAG.allnodes_begin(), DAG.allnodes_end())); - /// SlotsAvailable - Returns true if all units are available. - /// - bool SlotsAvailable(Iter Begin, unsigned N, unsigned ResourceSet, - unsigned &Resource) { - assert(N && "Must check availability with N != 0"); - // Determine end of interval - Iter End = Begin + N; - assert(End <= Tally.end() && "Tally is not large enough for schedule"); + for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(), + E = DAG.allnodes_end(); NI != E; ++NI) { + if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. + continue; + + // If this node has already been processed, stop now. + if (SUnitMap[NI].size()) continue; + + SUnit *NodeSUnit = NewSUnit(NI); - // Iterate thru each resource - BitsIterator Resources(ResourceSet & ~*Begin); - while (unsigned Res = Resources.Next()) { - // Check if resource is available for next N slots - Iter Interval = End; + // See if anything is flagged to this node, if so, add them to flagged + // nodes. Nodes can have at most one flag input and one flag output. Flags + // are required the be the last operand and result of a node. + + // Scan up, adding flagged preds to FlaggedNodes. + SDNode *N = NI; + if (N->getNumOperands() && + N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { do { - Interval--; - if (*Interval & Res) break; - } while (Interval != Begin); + N = N->getOperand(N->getNumOperands()-1).Val; + NodeSUnit->FlaggedNodes.push_back(N); + SUnitMap[N].push_back(NodeSUnit); + } while (N->getNumOperands() && + N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag); + std::reverse(NodeSUnit->FlaggedNodes.begin(), + NodeSUnit->FlaggedNodes.end()); + } + + // Scan down, adding this node and any flagged succs to FlaggedNodes if they + // have a user of the flag operand. + N = NI; + while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { + SDOperand FlagVal(N, N->getNumValues()-1); - // If available for N - if (Interval == Begin) { - // Success - Resource = Res; - return true; - } + // There are either zero or one users of the Flag result. + bool HasFlagUse = false; + for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); + UI != E; ++UI) + if (FlagVal.isOperand(*UI)) { + HasFlagUse = true; + NodeSUnit->FlaggedNodes.push_back(N); + SUnitMap[N].push_back(NodeSUnit); + N = *UI; + break; + } + if (!HasFlagUse) break; } - // No luck - Resource = 0; - return false; - } - - /// RetrySlot - Finds a good candidate slot to retry search. - Iter RetrySlot(Iter Begin, unsigned N, unsigned ResourceSet) { - assert(N && "Must check availability with N != 0"); - // Determine end of interval - Iter End = Begin + N; - assert(End <= Tally.end() && "Tally is not large enough for schedule"); - - while (Begin != End--) { - // Clear units in use - ResourceSet &= ~*End; - // If no units left then we should go no further - if (!ResourceSet) return End + 1; - } - // Made it all the way through - return Begin; - } - - /// FindAndReserveStages - Return true if the stages can be completed. If - /// so mark as busy. - bool FindAndReserveStages(Iter Begin, - InstrStage *Stage, InstrStage *StageEnd) { - // If at last stage then we're done - if (Stage == StageEnd) return true; - // Get number of cycles for current stage - unsigned N = Stage->Cycles; - // Check to see if N slots are available, if not fail - unsigned Resource; - if (!SlotsAvailable(Begin, N, Stage->Units, Resource)) return false; - // Check to see if remaining stages are available, if not fail - if (!FindAndReserveStages(Begin + N, Stage + 1, StageEnd)) return false; - // Reserve resource - Reserve(Begin, N, Resource); - // Success - return true; - } + // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node. + // Update the SUnit + NodeSUnit->Node = N; + SUnitMap[N].push_back(NodeSUnit); - /// Reserve - Mark busy (set) the specified N slots. - void Reserve(Iter Begin, unsigned N, unsigned Resource) { - // Determine end of interval - Iter End = Begin + N; - assert(End <= Tally.end() && "Tally is not large enough for schedule"); - - // Set resource bit in each slot - for (; Begin < End; Begin++) - *Begin |= Resource; + ComputeLatency(NodeSUnit); } - - /// FindSlots - Starting from Begin, locate consecutive slots where all stages - /// can be completed. Returns the address of first slot. - Iter FindSlots(Iter Begin, InstrStage *StageBegin, InstrStage *StageEnd) { - // Track position - Iter Cursor = Begin; + + // Pass 2: add the preds, succs, etc. + for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { + SUnit *SU = &SUnits[su]; + SDNode *MainNode = SU->Node; - // Try all possible slots forward - while (true) { - // Try at cursor, if successful return position. - if (FindAndReserveStages(Cursor, StageBegin, StageEnd)) return Cursor; - // Locate a better position - Cursor = RetrySlot(Cursor + 1, StageBegin->Cycles, StageBegin->Units); + if (MainNode->isTargetOpcode()) { + unsigned Opc = MainNode->getTargetOpcode(); + const TargetInstrDescriptor &TID = TII->get(Opc); + for (unsigned i = 0; i != TID.numOperands; ++i) { + if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { + SU->isTwoAddress = true; + break; + } + } + if (TID.Flags & M_COMMUTABLE) + SU->isCommutable = true; } - } - -public: - /// Initialize - Resize and zero the tally to the specified number of time - /// slots. - inline void Initialize(unsigned N) { - Tally.assign(N, 0); // Initialize tally to all zeros. - } - - // FindAndReserve - Locate an ideal slot for the specified stages and mark - // as busy. - unsigned FindAndReserve(unsigned Slot, InstrStage *StageBegin, - InstrStage *StageEnd) { - // Where to begin - Iter Begin = Tally.begin() + Slot; - // Find a free slot - Iter Where = FindSlots(Begin, StageBegin, StageEnd); - // Distance is slot number - unsigned Final = Where - Tally.begin(); - return Final; - } - -}; -//===----------------------------------------------------------------------===// - -// Forward -class NodeInfo; -typedef NodeInfo *NodeInfoPtr; -typedef std::vector NIVector; -typedef std::vector::iterator NIIterator; - -//===----------------------------------------------------------------------===// -/// -/// Node group - This struct is used to manage flagged node groups. -/// -class NodeGroup { -private: - NIVector Members; // Group member nodes - NodeInfo *Dominator; // Node with highest latency - unsigned Latency; // Total latency of the group - int Pending; // Number of visits pending before - // adding to order - -public: - // Ctor. - NodeGroup() : Dominator(NULL), Pending(0) {} - - // Accessors - inline void setDominator(NodeInfo *D) { Dominator = D; } - inline NodeInfo *getDominator() { return Dominator; } - inline void setLatency(unsigned L) { Latency = L; } - inline unsigned getLatency() { return Latency; } - inline int getPending() const { return Pending; } - inline void setPending(int P) { Pending = P; } - inline int addPending(int I) { return Pending += I; } - - // Pass thru - inline bool group_empty() { return Members.empty(); } - inline NIIterator group_begin() { return Members.begin(); } - inline NIIterator group_end() { return Members.end(); } - inline void group_push_back(const NodeInfoPtr &NI) { Members.push_back(NI); } - inline NIIterator group_insert(NIIterator Pos, const NodeInfoPtr &NI) { - return Members.insert(Pos, NI); - } - inline void group_insert(NIIterator Pos, NIIterator First, NIIterator Last) { - Members.insert(Pos, First, Last); - } - - static void Add(NodeInfo *D, NodeInfo *U); - static unsigned CountInternalUses(NodeInfo *D, NodeInfo *U); -}; -//===----------------------------------------------------------------------===// - - -//===----------------------------------------------------------------------===// -/// -/// NodeInfo - This struct tracks information used to schedule the a node. -/// -class NodeInfo { -private: - int Pending; // Number of visits pending before - // adding to order -public: - SDNode *Node; // DAG node - InstrStage *StageBegin; // First stage in itinerary - InstrStage *StageEnd; // Last+1 stage in itinerary - unsigned Latency; // Total cycles to complete instruction - bool IsCall : 1; // Is function call - bool IsLoad : 1; // Is memory load - bool IsStore : 1; // Is memory store - unsigned Slot; // Node's time slot - NodeGroup *Group; // Grouping information - unsigned VRBase; // Virtual register base -#ifndef NDEBUG - unsigned Preorder; // Index before scheduling -#endif - - // Ctor. - NodeInfo(SDNode *N = NULL) - : Pending(0) - , Node(N) - , StageBegin(NULL) - , StageEnd(NULL) - , Latency(0) - , IsCall(false) - , Slot(0) - , Group(NULL) - , VRBase(0) -#ifndef NDEBUG - , Preorder(0) -#endif - {} - - // Accessors - inline bool isInGroup() const { - assert(!Group || !Group->group_empty() && "Group with no members"); - return Group != NULL; - } - inline bool isGroupDominator() const { - return isInGroup() && Group->getDominator() == this; - } - inline int getPending() const { - return Group ? Group->getPending() : Pending; - } - inline void setPending(int P) { - if (Group) Group->setPending(P); - else Pending = P; - } - inline int addPending(int I) { - if (Group) return Group->addPending(I); - else return Pending += I; - } -}; -//===----------------------------------------------------------------------===// - - -//===----------------------------------------------------------------------===// -/// -/// NodeGroupIterator - Iterates over all the nodes indicated by the node info. -/// If the node is in a group then iterate over the members of the group, -/// otherwise just the node info. -/// -class NodeGroupIterator { -private: - NodeInfo *NI; // Node info - NIIterator NGI; // Node group iterator - NIIterator NGE; // Node group iterator end - -public: - // Ctor. - NodeGroupIterator(NodeInfo *N) : NI(N) { - // If the node is in a group then set up the group iterator. Otherwise - // the group iterators will trip first time out. - if (N->isInGroup()) { - // get Group - NodeGroup *Group = NI->Group; - NGI = Group->group_begin(); - NGE = Group->group_end(); - // Prevent this node from being used (will be in members list - NI = NULL; + + // Find all predecessors and successors of the group. + // Temporarily add N to make code simpler. + SU->FlaggedNodes.push_back(MainNode); + + for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) { + SDNode *N = SU->FlaggedNodes[n]; + if (N->isTargetOpcode() && + TII->getImplicitDefs(N->getTargetOpcode()) && + CountResults(N) > (unsigned)TII->getNumDefs(N->getTargetOpcode())) + SU->hasPhysRegDefs = true; + + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { + SDNode *OpN = N->getOperand(i).Val; + if (isPassiveNode(OpN)) continue; // Not scheduled. + SUnit *OpSU = SUnitMap[OpN].front(); + assert(OpSU && "Node has no SUnit!"); + if (OpSU == SU) continue; // In the same group. + + MVT::ValueType OpVT = N->getOperand(i).getValueType(); + assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); + bool isChain = OpVT == MVT::Other; + + unsigned PhysReg = 0; + int Cost = 1; + // Determine if this is a physical register dependency. + CheckForPhysRegDependency(OpN, N, i, MRI, TII, PhysReg, Cost); + SU->addPred(OpSU, isChain, false, PhysReg, Cost); + } } + + // Remove MainNode from FlaggedNodes again. + SU->FlaggedNodes.pop_back(); } - /// next - Return the next node info, otherwise NULL. - /// - NodeInfo *next() { - // If members list - if (NGI != NGE) return *NGI++; - // Use node as the result (may be NULL) - NodeInfo *Result = NI; - // Only use once - NI = NULL; - // Return node or NULL - return Result; - } -}; -//===----------------------------------------------------------------------===// - + return; +} -//===----------------------------------------------------------------------===// -/// -/// NodeGroupOpIterator - Iterates over all the operands of a node. If the node -/// is a member of a group, this iterates over all the operands of all the -/// members of the group. -/// -class NodeGroupOpIterator { -private: - NodeInfo *NI; // Node containing operands - NodeGroupIterator GI; // Node group iterator - SDNode::op_iterator OI; // Operand iterator - SDNode::op_iterator OE; // Operand iterator end +void ScheduleDAG::ComputeLatency(SUnit *SU) { + const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); - /// CheckNode - Test if node has more operands. If not get the next node - /// skipping over nodes that have no operands. - void CheckNode() { - // Only if operands are exhausted first - while (OI == OE) { - // Get next node info - NodeInfo *NI = GI.next(); - // Exit if nodes are exhausted - if (!NI) return; - // Get node itself - SDNode *Node = NI->Node; - // Set up the operand iterators - OI = Node->op_begin(); - OE = Node->op_end(); + // Compute the latency for the node. We use the sum of the latencies for + // all nodes flagged together into this SUnit. + if (InstrItins.isEmpty()) { + // No latency information. + SU->Latency = 1; + } else { + SU->Latency = 0; + if (SU->Node->isTargetOpcode()) { + unsigned SchedClass = TII->getSchedClass(SU->Node->getTargetOpcode()); + InstrStage *S = InstrItins.begin(SchedClass); + InstrStage *E = InstrItins.end(SchedClass); + for (; S != E; ++S) + SU->Latency += S->Cycles; } - } - -public: - // Ctor. - NodeGroupOpIterator(NodeInfo *N) - : NI(N), GI(N), OI(SDNode::op_iterator()), OE(SDNode::op_iterator()) {} - - /// isEnd - Returns true when not more operands are available. - /// - inline bool isEnd() { CheckNode(); return OI == OE; } - - /// next - Returns the next available operand. - /// - inline SDOperand next() { - assert(OI != OE && "Not checking for end of NodeGroupOpIterator correctly"); - return *OI++; - } -}; -//===----------------------------------------------------------------------===// - - -//===----------------------------------------------------------------------===// -/// -/// SimpleSched - Simple two pass scheduler. -/// -class SimpleSched { -private: - MachineBasicBlock *BB; // Current basic block - SelectionDAG &DAG; // DAG of the current basic block - const TargetMachine &TM; // Target processor - const TargetInstrInfo &TII; // Target instruction information - const MRegisterInfo &MRI; // Target processor register information - SSARegMap *RegMap; // Virtual/real register map - MachineConstantPool *ConstPool; // Target constant pool - unsigned NodeCount; // Number of nodes in DAG - bool HasGroups; // True if there are any groups - NodeInfo *Info; // Info for nodes being scheduled - std::map Map; // Map nodes to info - NIVector Ordering; // Emit ordering of nodes - ResourceTally Tally; // Resource usage tally - unsigned NSlots; // Total latency - static const unsigned NotFound = ~0U; // Search marker - -public: - - // Ctor. - SimpleSched(SelectionDAG &D, MachineBasicBlock *bb) - : BB(bb), DAG(D), TM(D.getTarget()), TII(*TM.getInstrInfo()), - MRI(*TM.getRegisterInfo()), RegMap(BB->getParent()->getSSARegMap()), - ConstPool(BB->getParent()->getConstantPool()), - NodeCount(0), HasGroups(false), Info(NULL), Map(), Tally(), NSlots(0) { - assert(&TII && "Target doesn't provide instr info?"); - assert(&MRI && "Target doesn't provide register info?"); - } - - // Run - perform scheduling. - MachineBasicBlock *Run() { - Schedule(); - return BB; - } - -private: - /// getNI - Returns the node info for the specified node. - /// - inline NodeInfo *getNI(SDNode *Node) { return Map[Node]; } - - /// getVR - Returns the virtual register number of the node. - /// - inline unsigned getVR(SDOperand Op) { - NodeInfo *NI = getNI(Op.Val); - assert(NI->VRBase != 0 && "Node emitted out of order - late"); - return NI->VRBase + Op.ResNo; - } - - 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 EmitNode(NodeInfo *NI); - static unsigned CountResults(SDNode *Node); - static unsigned CountOperands(SDNode *Node); - unsigned CreateVirtualRegisters(MachineInstr *MI, - unsigned NumResults, - const TargetInstrDescriptor &II); - - void printChanges(unsigned Index); - void printSI(std::ostream &O, NodeInfo *NI) const; - void print(std::ostream &O) const; - inline void dump(const char *tag) const { std::cerr << tag; dump(); } - void dump() const; -}; - - -//===----------------------------------------------------------------------===// -/// Special case itineraries. -/// -enum { - CallLatency = 40, // To push calls back in time - - RSInteger = 0xC0000000, // Two integer units - RSFloat = 0x30000000, // Two float units - RSLoadStore = 0x0C000000, // Two load store units - RSBranch = 0x02000000 // One branch unit -}; -static InstrStage CallStage = { CallLatency, RSBranch }; -static InstrStage LoadStage = { 5, RSLoadStore }; -static InstrStage StoreStage = { 2, RSLoadStore }; -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)); + for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) { + SDNode *FNode = SU->FlaggedNodes[i]; + if (FNode->isTargetOpcode()) { + unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode()); + InstrStage *S = InstrItins.begin(SchedClass); + InstrStage *E = InstrItins.end(SchedClass); + for (; S != E; ++S) + SU->Latency += S->Cycles; } } - // 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++; +void ScheduleDAG::CalculateDepths() { + std::vector > WorkList; + for (unsigned i = 0, e = SUnits.size(); i != e; ++i) + if (SUnits[i].Preds.size() == 0) + WorkList.push_back(std::make_pair(&SUnits[i], 0U)); + + while (!WorkList.empty()) { + SUnit *SU = WorkList.back().first; + unsigned Depth = WorkList.back().second; + WorkList.pop_back(); + if (SU->Depth == 0 || Depth > SU->Depth) { + SU->Depth = Depth; + for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); + I != E; ++I) + WorkList.push_back(std::make_pair(I->Dep, Depth+1)); + } } - - return N; } -//===----------------------------------------------------------------------===// - -//===----------------------------------------------------------------------===// -/// isFlagDefiner - Returns true if the node defines a flag result. -bool SimpleSched::isFlagDefiner(SDNode *A) { - unsigned N = A->getNumValues(); - return N && A->getValueType(N - 1) == MVT::Flag; +void ScheduleDAG::CalculateHeights() { + std::vector > WorkList; + SUnit *Root = SUnitMap[DAG.getRoot().Val].front(); + WorkList.push_back(std::make_pair(Root, 0U)); + + while (!WorkList.empty()) { + SUnit *SU = WorkList.back().first; + unsigned Height = WorkList.back().second; + WorkList.pop_back(); + if (SU->Height == 0 || Height > SU->Height) { + SU->Height = Height; + for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); + I != E; ++I) + WorkList.push_back(std::make_pair(I->Dep, Height+1)); + } + } } -/// isFlagUser - Returns true if the node uses a flag result. -/// -bool SimpleSched::isFlagUser(SDNode *A) { - unsigned N = A->getNumOperands(); - return N && A->getOperand(N - 1).getValueType() == MVT::Flag; +/// CountResults - The results of target nodes have register or immediate +/// operands first, then an optional chain, and optional flag operands (which do +/// not go into the machine instrs.) +unsigned ScheduleDAG::CountResults(SDNode *Node) { + unsigned N = Node->getNumValues(); + while (N && Node->getValueType(N - 1) == MVT::Flag) + --N; + if (N && Node->getValueType(N - 1) == MVT::Other) + --N; // Skip over chain result. + return N; } -/// isDefiner - Return true if node A is a definer for B. -/// -bool SimpleSched::isDefiner(NodeInfo *A, NodeInfo *B) { - // While there are A nodes - NodeGroupIterator NII(A); - while (NodeInfo *NI = NII.next()) { - // Extract node - SDNode *Node = NI->Node; - // While there operands in nodes of B - NodeGroupOpIterator NGOI(B); - while (!NGOI.isEnd()) { - SDOperand Op = NGOI.next(); - // If node from A defines a node in B - if (Node == Op.Val) return true; - } - } - return false; +/// CountOperands The inputs to target nodes have any actual inputs first, +/// followed by an optional chain operand, then flag operands. Compute the +/// number of actual operands that will go into the machine instr. +unsigned ScheduleDAG::CountOperands(SDNode *Node) { + unsigned N = Node->getNumOperands(); + while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) + --N; + if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) + --N; // Ignore chain if it exists. + return N; } -/// isPassiveNode - Return true if the node is a non-scheduled leaf. -/// -bool SimpleSched::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; +static const TargetRegisterClass *getInstrOperandRegClass( + const MRegisterInfo *MRI, + const TargetInstrInfo *TII, + const TargetInstrDescriptor *II, + unsigned Op) { + if (Op >= II->numOperands) { + assert((II->Flags & M_VARIABLE_OPS)&& "Invalid operand # of instruction"); + return NULL; + } + const TargetOperandInfo &toi = II->OpInfo[Op]; + return (toi.Flags & M_LOOK_UP_PTR_REG_CLASS) + ? TII->getPointerRegClass() : MRI->getRegClass(toi.RegClass); } -/// IncludeNode - Add node to NodeInfo vector. -/// -void SimpleSched::IncludeNode(NodeInfo *NI) { - // Get node - SDNode *Node = NI->Node; - // Ignore entry node - if (Node->getOpcode() == ISD::EntryToken) return; - // Check current count for node - int Count = NI->getPending(); - // If the node is already in list - if (Count < 0) return; - // Decrement count to indicate a visit - Count--; - // If count has gone to zero then add node to list - if (!Count) { - // Add node - if (NI->isInGroup()) { - Ordering.push_back(NI->Group->getDominator()); +void ScheduleDAG::EmitCopyFromReg(SDNode *Node, unsigned ResNo, + unsigned InstanceNo, unsigned SrcReg, + DenseMap &VRBaseMap) { + unsigned VRBase = 0; + if (MRegisterInfo::isVirtualRegister(SrcReg)) { + // Just use the input register directly! + if (InstanceNo > 0) + VRBaseMap.erase(SDOperand(Node, ResNo)); + bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo),SrcReg)); + assert(isNew && "Node emitted out of order - early"); + return; + } + + // If the node is only used by a CopyToReg and the dest reg is a vreg, use + // the CopyToReg'd destination register instead of creating a new vreg. + bool MatchReg = true; + for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); + UI != E; ++UI) { + SDNode *Use = *UI; + bool Match = true; + if (Use->getOpcode() == ISD::CopyToReg && + Use->getOperand(2).Val == Node && + Use->getOperand(2).ResNo == ResNo) { + unsigned DestReg = cast(Use->getOperand(1))->getReg(); + if (MRegisterInfo::isVirtualRegister(DestReg)) { + VRBase = DestReg; + Match = false; + } else if (DestReg != SrcReg) + Match = false; } else { - Ordering.push_back(NI); + for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) { + SDOperand Op = Use->getOperand(i); + if (Op.Val != Node || Op.ResNo != ResNo) + continue; + MVT::ValueType VT = Node->getValueType(Op.ResNo); + if (VT != MVT::Other && VT != MVT::Flag) + Match = false; + } } - // indicate node has been added - Count--; + MatchReg &= Match; + if (VRBase) + break; } - // Mark as visited with new count - 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 SimpleSched::VisitAll() { - // Add first element to list - NodeInfo *NI = getNI(DAG.getRoot().Val); - if (NI->isInGroup()) { - Ordering.push_back(NI->Group->getDominator()); + const TargetRegisterClass *TRC = 0; + // Figure out the register class to create for the destreg. + if (VRBase) + TRC = RegInfo.getRegClass(VRBase); + else + TRC = MRI->getPhysicalRegisterRegClass(Node->getValueType(ResNo), SrcReg); + + // If all uses are reading from the src physical register and copying the + // register is either impossible or very expensive, then don't create a copy. + if (MatchReg && TRC->getCopyCost() < 0) { + VRBase = SrcReg; } else { - Ordering.push_back(NI); + // Create the reg, emit the copy. + VRBase = RegInfo.createVirtualRegister(TRC); + MRI->copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC, TRC); } - // 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()); + if (InstanceNo > 0) + VRBaseMap.erase(SDOperand(Node, ResNo)); + bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,ResNo), VRBase)); + assert(isNew && "Node emitted out of order - early"); } -/// IdentifyGroups - Put flagged nodes into groups. -/// -void SimpleSched::IdentifyGroups() { - for (unsigned i = 0, N = NodeCount; i < N; i++) { - NodeInfo* NI = &Info[i]; - SDNode *Node = NI->Node; +void ScheduleDAG::CreateVirtualRegisters(SDNode *Node, + MachineInstr *MI, + const TargetInstrDescriptor &II, + DenseMap &VRBaseMap) { + for (unsigned i = 0; i < II.numDefs; ++i) { + // If the specific node value is only used by a CopyToReg and the dest reg + // is a vreg, use the CopyToReg'd destination register instead of creating + // a new vreg. + unsigned VRBase = 0; + for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); + UI != E; ++UI) { + SDNode *Use = *UI; + if (Use->getOpcode() == ISD::CopyToReg && + Use->getOperand(2).Val == Node && + Use->getOperand(2).ResNo == i) { + unsigned Reg = cast(Use->getOperand(1))->getReg(); + if (MRegisterInfo::isVirtualRegister(Reg)) { + VRBase = Reg; + MI->addOperand(MachineOperand::CreateReg(Reg, true)); + break; + } + } + } - // 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; + // Create the result registers for this node and add the result regs to + // the machine instruction. + if (VRBase == 0) { + const TargetRegisterClass *RC = getInstrOperandRegClass(MRI, TII, &II, i); + assert(RC && "Isn't a register operand!"); + VRBase = RegInfo.createVirtualRegister(RC); + MI->addOperand(MachineOperand::CreateReg(VRBase, true)); } + + bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,i), VRBase)); + assert(isNew && "Node emitted out of order - early"); } } -/// GatherSchedulingInfo - Get latency and resource information about each node. -/// -void SimpleSched::GatherSchedulingInfo() { - // Get instruction itineraries for the target - const InstrItineraryData InstrItins = TM.getInstrItineraryData(); - - // For each node - for (unsigned i = 0, N = NodeCount; i < N; i++) { - // Get node info - NodeInfo* NI = &Info[i]; - SDNode *Node = NI->Node; - - // If there are itineraries and it is a machine instruction - if (InstrItins.isEmpty() || ScheduleStyle == simpleNoItinScheduling) { - // If machine opcode - if (Node->isTargetOpcode()) { - // Get return type to guess which processing unit - MVT::ValueType VT = Node->getValueType(0); - // Get machine opcode - MachineOpCode TOpc = Node->getTargetOpcode(); - NI->IsCall = TII.isCall(TOpc); - NI->IsLoad = TII.isLoad(TOpc); - NI->IsStore = TII.isStore(TOpc); +/// getVR - Return the virtual register corresponding to the specified result +/// of the specified node. +static unsigned getVR(SDOperand Op, DenseMap &VRBaseMap) { + DenseMap::iterator I = VRBaseMap.find(Op); + assert(I != VRBaseMap.end() && "Node emitted out of order - late"); + return I->second; +} - if (TII.isLoad(TOpc)) NI->StageBegin = &LoadStage; - else if (TII.isStore(TOpc)) NI->StageBegin = &StoreStage; - else if (MVT::isInteger(VT)) NI->StageBegin = &IntStage; - else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage; - if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1; - } - } else if (Node->isTargetOpcode()) { - // get machine opcode - MachineOpCode TOpc = Node->getTargetOpcode(); - // Check to see if it is a call - NI->IsCall = TII.isCall(TOpc); - // Get itinerary stages for instruction - unsigned II = TII.getSchedClass(TOpc); - NI->StageBegin = InstrItins.begin(II); - NI->StageEnd = InstrItins.end(II); - } - - // One slot for the instruction itself - NI->Latency = 1; + +/// AddOperand - Add the specified operand to the specified machine instr. II +/// specifies the instruction information for the node, and IIOpNum is the +/// operand number (in the II) that we are adding. IIOpNum and II are used for +/// assertions only. +void ScheduleDAG::AddOperand(MachineInstr *MI, SDOperand Op, + unsigned IIOpNum, + const TargetInstrDescriptor *II, + DenseMap &VRBaseMap) { + if (Op.isTargetOpcode()) { + // Note that this case is redundant with the final else block, but we + // include it because it is the most common and it makes the logic + // simpler here. + assert(Op.getValueType() != MVT::Other && + Op.getValueType() != MVT::Flag && + "Chain and flag operands should occur at end of operand list!"); - // Add long latency for a call to push it back in time - if (NI->IsCall) NI->Latency += CallLatency; + // Get/emit the operand. + unsigned VReg = getVR(Op, VRBaseMap); + const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); + bool isOptDef = (IIOpNum < TID->numOperands) + ? (TID->OpInfo[IIOpNum].Flags & M_OPTIONAL_DEF_OPERAND) : false; + MI->addOperand(MachineOperand::CreateReg(VReg, isOptDef)); - // Sum up all the latencies - for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd; - Stage != E; Stage++) { - NI->Latency += Stage->Cycles; + // Verify that it is right. + assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?"); + if (II) { + const TargetRegisterClass *RC = + getInstrOperandRegClass(MRI, TII, II, IIOpNum); + assert(RC && "Don't have operand info for this instruction!"); + const TargetRegisterClass *VRC = RegInfo.getRegClass(VReg); + if (VRC != RC) { + cerr << "Register class of operand and regclass of use don't agree!\n"; +#ifndef NDEBUG + cerr << "Operand = " << IIOpNum << "\n"; + cerr << "Op->Val = "; Op.Val->dump(&DAG); cerr << "\n"; + cerr << "MI = "; MI->print(cerr); + cerr << "VReg = " << VReg << "\n"; + cerr << "VReg RegClass size = " << VRC->getSize() + << ", align = " << VRC->getAlignment() << "\n"; + cerr << "Expected RegClass size = " << RC->getSize() + << ", align = " << RC->getAlignment() << "\n"; +#endif + cerr << "Fatal error, aborting.\n"; + abort(); + } } - - // Sum up all the latencies for max tally size - NSlots += NI->Latency; - } - - // Unify metrics if in a group - if (HasGroups) { - for (unsigned i = 0, N = NodeCount; i < N; i++) { - NodeInfo* NI = &Info[i]; - - if (NI->isInGroup()) { - NodeGroup *Group = NI->Group; - - if (!Group->getDominator()) { - NIIterator NGI = Group->group_begin(), NGE = Group->group_end(); - NodeInfo *Dominator = *NGI; - unsigned Latency = 0; - - for (NGI++; NGI != NGE; NGI++) { - NodeInfo* NGNI = *NGI; - Latency += NGNI->Latency; - if (Dominator->Latency < NGNI->Latency) Dominator = NGNI; - } - - Dominator->Latency = Latency; - Group->setDominator(Dominator); - } + } else if (ConstantSDNode *C = dyn_cast(Op)) { + MI->addOperand(MachineOperand::CreateImm(C->getValue())); + } else if (RegisterSDNode *R = dyn_cast(Op)) { + MI->addOperand(MachineOperand::CreateReg(R->getReg(), false)); + } else if (GlobalAddressSDNode *TGA = dyn_cast(Op)) { + MI->addOperand(MachineOperand::CreateGA(TGA->getGlobal(),TGA->getOffset())); + } else if (BasicBlockSDNode *BB = dyn_cast(Op)) { + MI->addOperand(MachineOperand::CreateMBB(BB->getBasicBlock())); + } else if (FrameIndexSDNode *FI = dyn_cast(Op)) { + MI->addOperand(MachineOperand::CreateFI(FI->getIndex())); + } else if (JumpTableSDNode *JT = dyn_cast(Op)) { + MI->addOperand(MachineOperand::CreateJTI(JT->getIndex())); + } else if (ConstantPoolSDNode *CP = dyn_cast(Op)) { + int Offset = CP->getOffset(); + unsigned Align = CP->getAlignment(); + const Type *Type = CP->getType(); + // MachineConstantPool wants an explicit alignment. + if (Align == 0) { + Align = TM.getTargetData()->getPreferredTypeAlignmentShift(Type); + if (Align == 0) { + // Alignment of vector types. FIXME! + Align = TM.getTargetData()->getABITypeSize(Type); + Align = Log2_64(Align); } } - } -} - -/// FakeGroupDominators - Set dominators for non-scheduling. -/// -void SimpleSched::FakeGroupDominators() { - for (unsigned i = 0, N = NodeCount; i < N; i++) { - NodeInfo* NI = &Info[i]; - if (NI->isInGroup()) { - NodeGroup *Group = NI->Group; - - if (!Group->getDominator()) { - Group->setDominator(NI); - } + unsigned Idx; + if (CP->isMachineConstantPoolEntry()) + Idx = ConstPool->getConstantPoolIndex(CP->getMachineCPVal(), Align); + else + Idx = ConstPool->getConstantPoolIndex(CP->getConstVal(), Align); + MI->addOperand(MachineOperand::CreateCPI(Idx, Offset)); + } else if (ExternalSymbolSDNode *ES = dyn_cast(Op)) { + MI->addOperand(MachineOperand::CreateES(ES->getSymbol())); + } else { + assert(Op.getValueType() != MVT::Other && + Op.getValueType() != MVT::Flag && + "Chain and flag operands should occur at end of operand list!"); + unsigned VReg = getVR(Op, VRBaseMap); + MI->addOperand(MachineOperand::CreateReg(VReg, false)); + + // Verify that it is right. + assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?"); + if (II) { + const TargetRegisterClass *RC = + getInstrOperandRegClass(MRI, TII, II, IIOpNum); + assert(RC && "Don't have operand info for this instruction!"); + assert(RegInfo.getRegClass(VReg) == RC && + "Register class of operand and regclass of use don't agree!"); } } + } -/// PrepareNodeInfo - Set up the basic minimum node info for scheduling. -/// -void SimpleSched::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 SimpleSched::isStrongDependency(NodeInfo *A, NodeInfo *B) { - // If A defines for B then it's a strong dependency or - // if a load follows a store (may be dependent but why take a chance.) - return isDefiner(A, B) || (A->IsStore && B->IsLoad); +// Returns the Register Class of a subregister +static const TargetRegisterClass *getSubRegisterRegClass( + const TargetRegisterClass *TRC, + unsigned SubIdx) { + // Pick the register class of the subregister + MRegisterInfo::regclass_iterator I = TRC->subregclasses_begin() + SubIdx-1; + assert(I < TRC->subregclasses_end() && + "Invalid subregister index for register class"); + return *I; } -/// isWeakDependency Return true if node A produces a result that will -/// conflict with operands of B. It is assumed that we have called -/// isStrongDependency prior. -bool SimpleSched::isWeakDependency(NodeInfo *A, NodeInfo *B) { - // TODO check for conflicting real registers and aliases -#if 0 // FIXME - Since we are in SSA form and not checking register aliasing - return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A); -#else - return A->Node->getOpcode() == ISD::EntryToken; -#endif +static const TargetRegisterClass *getSuperregRegisterClass( + const TargetRegisterClass *TRC, + unsigned SubIdx, + MVT::ValueType VT) { + // Pick the register class of the superegister for this type + for (MRegisterInfo::regclass_iterator I = TRC->superregclasses_begin(), + E = TRC->superregclasses_end(); I != E; ++I) + if ((*I)->hasType(VT) && getSubRegisterRegClass(*I, SubIdx) == TRC) + return *I; + assert(false && "Couldn't find the register class"); + return 0; } -/// ScheduleBackward - Schedule instructions so that any long latency -/// instructions and the critical path get pushed back in time. Time is run in -/// reverse to allow code reuse of the Tally and eliminate the overhead of -/// biasing every slot indices against NSlots. -void SimpleSched::ScheduleBackward() { - // Size and clear the resource tally - Tally.Initialize(NSlots); - // Get number of nodes to schedule - unsigned N = Ordering.size(); - - // For each node being scheduled - for (unsigned i = N; 0 < i--;) { - NodeInfo *NI = Ordering[i]; - // Track insertion - unsigned Slot = NotFound; - - // Compare against those previously scheduled nodes - unsigned j = i + 1; - for (; j < N; j++) { - // Get following instruction - NodeInfo *Other = Ordering[j]; - - // Check dependency against previously inserted nodes - if (isStrongDependency(NI, Other)) { - Slot = Other->Slot + Other->Latency; - break; - } else if (isWeakDependency(NI, Other)) { - Slot = Other->Slot; - break; +/// EmitSubregNode - Generate machine code for subreg nodes. +/// +void ScheduleDAG::EmitSubregNode(SDNode *Node, + DenseMap &VRBaseMap) { + unsigned VRBase = 0; + unsigned Opc = Node->getTargetOpcode(); + if (Opc == TargetInstrInfo::EXTRACT_SUBREG) { + // If the node is only used by a CopyToReg and the dest reg is a vreg, use + // the CopyToReg'd destination register instead of creating a new vreg. + for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); + UI != E; ++UI) { + SDNode *Use = *UI; + if (Use->getOpcode() == ISD::CopyToReg && + Use->getOperand(2).Val == Node) { + unsigned DestReg = cast(Use->getOperand(1))->getReg(); + if (MRegisterInfo::isVirtualRegister(DestReg)) { + VRBase = DestReg; + break; + } } } - // If independent of others (or first entry) - if (Slot == NotFound) Slot = 0; + unsigned SubIdx = cast(Node->getOperand(1))->getValue(); -#if 0 // FIXME - measure later - // Find a slot where the needed resources are available - if (NI->StageBegin != NI->StageEnd) - Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd); -#endif - - // Set node slot - NI->Slot = Slot; + // TODO: If the node is a use of a CopyFromReg from a physical register + // fold the extract into the copy now + + // Create the extract_subreg machine instruction. + MachineInstr *MI = + new MachineInstr(BB, TII->get(TargetInstrInfo::EXTRACT_SUBREG)); + + // Figure out the register class to create for the destreg. + unsigned VReg = getVR(Node->getOperand(0), VRBaseMap); + const TargetRegisterClass *TRC = RegInfo.getRegClass(VReg); + const TargetRegisterClass *SRC = getSubRegisterRegClass(TRC, SubIdx); + + if (VRBase) { + // Grab the destination register + const TargetRegisterClass *DRC = 0; + DRC = RegInfo.getRegClass(VRBase); + assert(SRC == DRC && + "Source subregister and destination must have the same class"); + } else { + // Create the reg + VRBase = RegInfo.createVirtualRegister(SRC); + } - // Insert sort based on slot - j = i + 1; - for (; j < N; j++) { - // Get following instruction - NodeInfo *Other = Ordering[j]; - // Should we look further (remember slots are in reverse time) - if (Slot >= Other->Slot) break; - // Shuffle other into ordering - Ordering[j - 1] = Other; + // Add def, source, and subreg index + MI->addOperand(MachineOperand::CreateReg(VRBase, true)); + AddOperand(MI, Node->getOperand(0), 0, 0, VRBaseMap); + MI->addOperand(MachineOperand::CreateImm(SubIdx)); + + } else if (Opc == TargetInstrInfo::INSERT_SUBREG) { + assert((Node->getNumOperands() == 2 || Node->getNumOperands() == 3) && + "Malformed insert_subreg node"); + bool isUndefInput = (Node->getNumOperands() == 2); + unsigned SubReg = 0; + unsigned SubIdx = 0; + + if (isUndefInput) { + SubReg = getVR(Node->getOperand(0), VRBaseMap); + SubIdx = cast(Node->getOperand(1))->getValue(); + } else { + SubReg = getVR(Node->getOperand(1), VRBaseMap); + SubIdx = cast(Node->getOperand(2))->getValue(); } - // Insert node in proper slot - if (j != i + 1) Ordering[j - 1] = NI; - } -} - -/// ScheduleForward - Schedule instructions to maximize packing. -/// -void SimpleSched::ScheduleForward() { - // Size and clear the resource tally - Tally.Initialize(NSlots); - // Get number of nodes to schedule - unsigned N = Ordering.size(); - - // For each node being scheduled - for (unsigned i = 0; i < N; i++) { - NodeInfo *NI = Ordering[i]; - // Track insertion - unsigned Slot = NotFound; - // Compare against those previously scheduled nodes - unsigned j = i; - for (; 0 < j--;) { - // Get following instruction - NodeInfo *Other = Ordering[j]; - - // Check dependency against previously inserted nodes - if (isStrongDependency(Other, NI)) { - Slot = Other->Slot + Other->Latency; - break; - } else if (Other->IsCall || isWeakDependency(Other, NI)) { - Slot = Other->Slot; - break; + // TODO: Add tracking info to MachineRegisterInfo of which vregs are subregs + // to allow coalescing in the allocator + + // If the node is only used by a CopyToReg and the dest reg is a vreg, use + // the CopyToReg'd destination register instead of creating a new vreg. + // If the CopyToReg'd destination register is physical, then fold the + // insert into the copy + for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); + UI != E; ++UI) { + SDNode *Use = *UI; + if (Use->getOpcode() == ISD::CopyToReg && + Use->getOperand(2).Val == Node) { + unsigned DestReg = cast(Use->getOperand(1))->getReg(); + if (MRegisterInfo::isVirtualRegister(DestReg)) { + VRBase = DestReg; + break; + } } } - // If independent of others (or first entry) - if (Slot == NotFound) Slot = 0; - - // Find a slot where the needed resources are available - if (NI->StageBegin != NI->StageEnd) - Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd); + // Create the insert_subreg machine instruction. + MachineInstr *MI = + new MachineInstr(BB, TII->get(TargetInstrInfo::INSERT_SUBREG)); - // Set node slot - NI->Slot = Slot; - - // Insert sort based on slot - j = i; - for (; 0 < j--;) { - // Get prior instruction - NodeInfo *Other = Ordering[j]; - // Should we look further - if (Slot >= Other->Slot) break; - // Shuffle other into ordering - Ordering[j + 1] = Other; - } - // Insert node in proper slot - if (j != i) Ordering[j + 1] = NI; - } -} - -/// EmitAll - Emit all nodes in schedule sorted order. -/// -void SimpleSched::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); + // Figure out the register class to create for the destreg. + const TargetRegisterClass *TRC = 0; + if (VRBase) { + TRC = RegInfo.getRegClass(VRBase); } else { - EmitNode(NI); + TRC = getSuperregRegisterClass(RegInfo.getRegClass(SubReg), SubIdx, + Node->getValueType(0)); + assert(TRC && "Couldn't determine register class for insert_subreg"); + VRBase = RegInfo.createVirtualRegister(TRC); // Create the reg } - } -} - -/// CountResults - The results of target nodes have register or immediate -/// operands first, then an optional chain, and optional flag operands (which do -/// not go into the machine instrs.) -unsigned SimpleSched::CountResults(SDNode *Node) { - unsigned N = Node->getNumValues(); - while (N && Node->getValueType(N - 1) == MVT::Flag) - --N; - if (N && Node->getValueType(N - 1) == MVT::Other) - --N; // Skip over chain result. - return N; -} - -/// CountOperands The inputs to target nodes have any actual inputs first, -/// followed by an optional chain operand, then flag operands. Compute the -/// number of actual operands that will go into the machine instr. -unsigned SimpleSched::CountOperands(SDNode *Node) { - unsigned N = Node->getNumOperands(); - while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag) - --N; - if (N && Node->getOperand(N - 1).getValueType() == MVT::Other) - --N; // Ignore chain if it exists. - return N; -} - -/// CreateVirtualRegisters - Add result register values for things that are -/// defined by this instruction. -unsigned SimpleSched::CreateVirtualRegisters(MachineInstr *MI, - unsigned NumResults, - const TargetInstrDescriptor &II) { - // Create the result registers for this node and add the result regs to - // the machine instruction. - const TargetOperandInfo *OpInfo = II.OpInfo; - unsigned ResultReg = RegMap->createVirtualRegister(OpInfo[0].RegClass); - MI->addRegOperand(ResultReg, MachineOperand::Def); - for (unsigned i = 1; i != NumResults; ++i) { - assert(OpInfo[i].RegClass && "Isn't a register operand!"); - MI->addRegOperand(RegMap->createVirtualRegister(OpInfo[i].RegClass), - MachineOperand::Def); - } - return ResultReg; + + MI->addOperand(MachineOperand::CreateReg(VRBase, true)); + AddOperand(MI, Node->getOperand(0), 0, 0, VRBaseMap); + if (!isUndefInput) + AddOperand(MI, Node->getOperand(1), 0, 0, VRBaseMap); + MI->addOperand(MachineOperand::CreateImm(SubIdx)); + } else + assert(0 && "Node is not a subreg insert or extract"); + + bool isNew = VRBaseMap.insert(std::make_pair(SDOperand(Node,0), VRBase)); + assert(isNew && "Node emitted out of order - early"); } /// EmitNode - Generate machine code for an node and needed dependencies. /// -void SimpleSched::EmitNode(NodeInfo *NI) { - unsigned VRBase = 0; // First virtual register for node - SDNode *Node = NI->Node; - +void ScheduleDAG::EmitNode(SDNode *Node, unsigned InstanceNo, + DenseMap &VRBaseMap) { // If machine instruction if (Node->isTargetOpcode()) { unsigned Opc = Node->getTargetOpcode(); - const TargetInstrDescriptor &II = TII.get(Opc); + + // Handle subreg insert/extract specially + if (Opc == TargetInstrInfo::EXTRACT_SUBREG || + Opc == TargetInstrInfo::INSERT_SUBREG) { + EmitSubregNode(Node, VRBaseMap); + return; + } + + const TargetInstrDescriptor &II = TII->get(Opc); unsigned NumResults = CountResults(Node); unsigned NodeOperands = CountOperands(Node); unsigned NumMIOperands = NodeOperands + NumResults; + bool HasPhysRegOuts = (NumResults > II.numDefs) && II.ImplicitDefs; #ifndef NDEBUG - assert((unsigned(II.numOperands) == NumMIOperands || II.numOperands == -1)&& + assert((unsigned(II.numOperands) == NumMIOperands || + HasPhysRegOuts || (II.Flags & M_VARIABLE_OPS)) && "#operands for dag node doesn't match .td file!"); #endif // Create the new machine instruction. - MachineInstr *MI = new MachineInstr(Opc, NumMIOperands, true, true); + MachineInstr *MI = new MachineInstr(II); // Add result register values for things that are defined by this // instruction. - - // If the node is only used by a CopyToReg and the dest reg is a vreg, use - // the CopyToReg'd destination register instead of creating a new vreg. - if (NumResults == 1) { - for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); - UI != E; ++UI) { - SDNode *Use = *UI; - if (Use->getOpcode() == ISD::CopyToReg && - Use->getOperand(2).Val == Node) { - unsigned Reg = cast(Use->getOperand(1))->getReg(); - if (MRegisterInfo::isVirtualRegister(Reg)) { - VRBase = Reg; - MI->addRegOperand(Reg, MachineOperand::Def); - break; - } - } - } - } - - // Otherwise, create new virtual registers. - if (NumResults && VRBase == 0) - VRBase = CreateVirtualRegisters(MI, NumResults, II); + if (NumResults) + CreateVirtualRegisters(Node, MI, II, VRBaseMap); // Emit all of the actual operands of this instruction, adding them to the // instruction as appropriate. - for (unsigned i = 0; i != NodeOperands; ++i) { - if (Node->getOperand(i).isTargetOpcode()) { - // Note that this case is redundant with the final else block, but we - // include it because it is the most common and it makes the logic - // simpler here. - assert(Node->getOperand(i).getValueType() != MVT::Other && - Node->getOperand(i).getValueType() != MVT::Flag && - "Chain and flag operands should occur at end of operand list!"); - - // Get/emit the operand. - unsigned VReg = getVR(Node->getOperand(i)); - MI->addRegOperand(VReg, MachineOperand::Use); - - // Verify that it is right. - assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?"); - assert(II.OpInfo[i+NumResults].RegClass && - "Don't have operand info for this instruction!"); - assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass && - "Register class of operand and regclass of use don't agree!"); - } else if (ConstantSDNode *C = - dyn_cast(Node->getOperand(i))) { - MI->addZeroExtImm64Operand(C->getValue()); - } else if (RegisterSDNode*R = - dyn_cast(Node->getOperand(i))) { - MI->addRegOperand(R->getReg(), MachineOperand::Use); - } else if (GlobalAddressSDNode *TGA = - dyn_cast(Node->getOperand(i))) { - MI->addGlobalAddressOperand(TGA->getGlobal(), false, TGA->getOffset()); - } else if (BasicBlockSDNode *BB = - dyn_cast(Node->getOperand(i))) { - MI->addMachineBasicBlockOperand(BB->getBasicBlock()); - } else if (FrameIndexSDNode *FI = - dyn_cast(Node->getOperand(i))) { - MI->addFrameIndexOperand(FI->getIndex()); - } else if (ConstantPoolSDNode *CP = - dyn_cast(Node->getOperand(i))) { - unsigned Idx = ConstPool->getConstantPoolIndex(CP->get()); - MI->addConstantPoolIndexOperand(Idx); - } else if (ExternalSymbolSDNode *ES = - dyn_cast(Node->getOperand(i))) { - MI->addExternalSymbolOperand(ES->getSymbol(), false); - } else { - assert(Node->getOperand(i).getValueType() != MVT::Other && - Node->getOperand(i).getValueType() != MVT::Flag && - "Chain and flag operands should occur at end of operand list!"); - unsigned VReg = getVR(Node->getOperand(i)); - MI->addRegOperand(VReg, MachineOperand::Use); - - // Verify that it is right. - assert(MRegisterInfo::isVirtualRegister(VReg) && "Not a vreg?"); - assert(II.OpInfo[i+NumResults].RegClass && - "Don't have operand info for this instruction!"); - assert(RegMap->getRegClass(VReg) == II.OpInfo[i+NumResults].RegClass && - "Register class of operand and regclass of use don't agree!"); + for (unsigned i = 0; i != NodeOperands; ++i) + AddOperand(MI, Node->getOperand(i), i+II.numDefs, &II, VRBaseMap); + + // Commute node if it has been determined to be profitable. + if (CommuteSet.count(Node)) { + MachineInstr *NewMI = TII->commuteInstruction(MI); + if (NewMI == 0) + DOUT << "Sched: COMMUTING FAILED!\n"; + else { + DOUT << "Sched: COMMUTED TO: " << *NewMI; + if (MI != NewMI) { + delete MI; + MI = NewMI; + } } } - + // Now that we have emitted all operands, emit this instruction itself. if ((II.Flags & M_USES_CUSTOM_DAG_SCHED_INSERTION) == 0) { BB->insert(BB->end(), MI); @@ -1164,210 +715,261 @@ void SimpleSched::EmitNode(NodeInfo *NI) { // taking some custom action. BB = DAG.getTargetLoweringInfo().InsertAtEndOfBasicBlock(MI, BB); } + + // Additional results must be an physical register def. + if (HasPhysRegOuts) { + for (unsigned i = II.numDefs; i < NumResults; ++i) { + unsigned Reg = II.ImplicitDefs[i - II.numDefs]; + if (Node->hasAnyUseOfValue(i)) + EmitCopyFromReg(Node, i, InstanceNo, Reg, VRBaseMap); + } + } } else { switch (Node->getOpcode()) { default: - Node->dump(); +#ifndef NDEBUG + Node->dump(&DAG); +#endif assert(0 && "This target-independent node should have been selected!"); case ISD::EntryToken: // fall thru case ISD::TokenFactor: + case ISD::LABEL: break; case ISD::CopyToReg: { - unsigned InReg = getVR(Node->getOperand(2)); + unsigned InReg; + if (RegisterSDNode *R = dyn_cast(Node->getOperand(2))) + InReg = R->getReg(); + else + InReg = getVR(Node->getOperand(2), VRBaseMap); unsigned DestReg = cast(Node->getOperand(1))->getReg(); - if (InReg != DestReg) // Coallesced away the copy? - MRI.copyRegToReg(*BB, BB->end(), DestReg, InReg, - RegMap->getRegClass(InReg)); + if (InReg != DestReg) {// Coalesced away the copy? + const TargetRegisterClass *TRC = 0; + // Get the target register class + if (MRegisterInfo::isVirtualRegister(InReg)) + TRC = RegInfo.getRegClass(InReg); + else + TRC = + MRI->getPhysicalRegisterRegClass(Node->getOperand(2).getValueType(), + InReg); + MRI->copyRegToReg(*BB, BB->end(), DestReg, InReg, TRC, TRC); + } break; } case ISD::CopyFromReg: { unsigned SrcReg = cast(Node->getOperand(1))->getReg(); - if (MRegisterInfo::isVirtualRegister(SrcReg)) { - VRBase = SrcReg; // Just use the input register directly! - break; - } - - // If the node is only used by a CopyToReg and the dest reg is a vreg, use - // the CopyToReg'd destination register instead of creating a new vreg. - for (SDNode::use_iterator UI = Node->use_begin(), E = Node->use_end(); - UI != E; ++UI) { - SDNode *Use = *UI; - if (Use->getOpcode() == ISD::CopyToReg && - Use->getOperand(2).Val == Node) { - unsigned DestReg = cast(Use->getOperand(1))->getReg(); - if (MRegisterInfo::isVirtualRegister(DestReg)) { - VRBase = DestReg; - break; + EmitCopyFromReg(Node, 0, InstanceNo, SrcReg, VRBaseMap); + break; + } + case ISD::INLINEASM: { + unsigned NumOps = Node->getNumOperands(); + if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag) + --NumOps; // Ignore the flag operand. + + // Create the inline asm machine instruction. + MachineInstr *MI = + new MachineInstr(BB, TII->get(TargetInstrInfo::INLINEASM)); + + // Add the asm string as an external symbol operand. + const char *AsmStr = + cast(Node->getOperand(1))->getSymbol(); + MI->addOperand(MachineOperand::CreateES(AsmStr)); + + // Add all of the operand registers to the instruction. + for (unsigned i = 2; i != NumOps;) { + unsigned Flags = cast(Node->getOperand(i))->getValue(); + unsigned NumVals = Flags >> 3; + + MI->addOperand(MachineOperand::CreateImm(Flags)); + ++i; // Skip the ID value. + + switch (Flags & 7) { + default: assert(0 && "Bad flags!"); + case 1: // Use of register. + for (; NumVals; --NumVals, ++i) { + unsigned Reg = cast(Node->getOperand(i))->getReg(); + MI->addOperand(MachineOperand::CreateReg(Reg, false)); } - } - } - - // Figure out the register class to create for the destreg. - const TargetRegisterClass *TRC = 0; - if (VRBase) { - TRC = RegMap->getRegClass(VRBase); - } else { - - // Pick the register class of the right type that contains this physreg. - for (MRegisterInfo::regclass_iterator I = MRI.regclass_begin(), - E = MRI.regclass_end(); I != E; ++I) - if ((*I)->hasType(Node->getValueType(0)) && - (*I)->contains(SrcReg)) { - TRC = *I; - break; + break; + case 2: // Def of register. + for (; NumVals; --NumVals, ++i) { + unsigned Reg = cast(Node->getOperand(i))->getReg(); + MI->addOperand(MachineOperand::CreateReg(Reg, true)); } - assert(TRC && "Couldn't find register class for reg copy!"); - - // Create the reg, emit the copy. - VRBase = RegMap->createVirtualRegister(TRC); + break; + case 3: { // Immediate. + for (; NumVals; --NumVals, ++i) { + if (ConstantSDNode *CS = + dyn_cast(Node->getOperand(i))) { + MI->addOperand(MachineOperand::CreateImm(CS->getValue())); + } else if (GlobalAddressSDNode *GA = + dyn_cast(Node->getOperand(i))) { + MI->addOperand(MachineOperand::CreateGA(GA->getGlobal(), + GA->getOffset())); + } else { + BasicBlockSDNode *BB =cast(Node->getOperand(i)); + MI->addOperand(MachineOperand::CreateMBB(BB->getBasicBlock())); + } + } + break; + } + case 4: // Addressing mode. + // The addressing mode has been selected, just add all of the + // operands to the machine instruction. + for (; NumVals; --NumVals, ++i) + AddOperand(MI, Node->getOperand(i), 0, 0, VRBaseMap); + break; + } } - MRI.copyRegToReg(*BB, BB->end(), VRBase, SrcReg, TRC); break; } } } - - assert(NI->VRBase == 0 && "Node emitted out of order - early"); - NI->VRBase = VRBase; } -/// Schedule - Order nodes according to selected style. -/// -void SimpleSched::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(); +void ScheduleDAG::EmitNoop() { + TII->insertNoop(*BB, BB->end()); +} - // Don't waste time if is only entry and return - if (ShouldSchedule) { - // Get latency and resource requirements - GatherSchedulingInfo(); - } else if (HasGroups) { - // Make sure all the groups have dominators - FakeGroupDominators(); +void ScheduleDAG::EmitCrossRCCopy(SUnit *SU, DenseMap &VRBaseMap) { + for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); + I != E; ++I) { + if (I->isCtrl) continue; // ignore chain preds + if (!I->Dep->Node) { + // Copy to physical register. + DenseMap::iterator VRI = VRBaseMap.find(I->Dep); + assert(VRI != VRBaseMap.end() && "Node emitted out of order - late"); + // Find the destination physical register. + unsigned Reg = 0; + for (SUnit::const_succ_iterator II = SU->Succs.begin(), + EE = SU->Succs.end(); II != EE; ++II) { + if (I->Reg) { + Reg = I->Reg; + break; + } + } + assert(I->Reg && "Unknown physical register!"); + MRI->copyRegToReg(*BB, BB->end(), Reg, VRI->second, + SU->CopyDstRC, SU->CopySrcRC); + } else { + // Copy from physical register. + assert(I->Reg && "Unknown physical register!"); + unsigned VRBase = RegInfo.createVirtualRegister(SU->CopyDstRC); + bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)); + assert(isNew && "Node emitted out of order - early"); + MRI->copyRegToReg(*BB, BB->end(), VRBase, I->Reg, + SU->CopyDstRC, SU->CopySrcRC); + } + break; } +} - // Breadth first walk of DAG - VisitAll(); - -#ifndef NDEBUG - static unsigned Count = 0; - Count++; - for (unsigned i = 0, N = Ordering.size(); i < N; i++) { - NodeInfo *NI = Ordering[i]; - NI->Preorder = i; - } -#endif - - // Don't waste time if is only entry and return - if (ShouldSchedule) { - // Push back long instructions and critical path - ScheduleBackward(); - - // Pack instructions to maximize resource utilization - ScheduleForward(); +/// EmitSchedule - Emit the machine code in scheduled order. +void ScheduleDAG::EmitSchedule() { + // If this is the first basic block in the function, and if it has live ins + // that need to be copied into vregs, emit the copies into the top of the + // block before emitting the code for the block. + MachineFunction &MF = DAG.getMachineFunction(); + if (&MF.front() == BB) { + for (MachineRegisterInfo::livein_iterator LI = RegInfo.livein_begin(), + E = RegInfo.livein_end(); LI != E; ++LI) + if (LI->second) { + const TargetRegisterClass *RC = RegInfo.getRegClass(LI->second); + MRI->copyRegToReg(*MF.begin(), MF.begin()->end(), LI->second, + LI->first, RC, RC); + } } - DEBUG(printChanges(Count)); - // Emit in scheduled order - EmitAll(); + // Finally, emit the code for all of the scheduled instructions. + DenseMap VRBaseMap; + DenseMap CopyVRBaseMap; + for (unsigned i = 0, e = Sequence.size(); i != e; i++) { + if (SUnit *SU = Sequence[i]) { + for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; ++j) + EmitNode(SU->FlaggedNodes[j], SU->InstanceNo, VRBaseMap); + if (SU->Node) + EmitNode(SU->Node, SU->InstanceNo, VRBaseMap); + else + EmitCrossRCCopy(SU, CopyVRBaseMap); + } else { + // Null SUnit* is a noop. + EmitNoop(); + } + } } -/// printChanges - Hilight changes in order caused by scheduling. -/// -void SimpleSched::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; +/// dump - dump the schedule. +void ScheduleDAG::dumpSchedule() const { + for (unsigned i = 0, e = Sequence.size(); i != e; i++) { + if (SUnit *SU = Sequence[i]) + SU->dump(&DAG); + else + cerr << "**** NOOP ****\n"; } - - 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. + +/// Run - perform scheduling. /// -void SimpleSched::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 +MachineBasicBlock *ScheduleDAG::Run() { + Schedule(); + return BB; } -/// print - Print ordering to specified output stream. -/// -void SimpleSched::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"; - } +/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or +/// a group of nodes flagged together. +void SUnit::dump(const SelectionDAG *G) const { + cerr << "SU(" << NodeNum << "): "; + if (Node) + Node->dump(G); + else + cerr << "CROSS RC COPY "; + cerr << "\n"; + if (FlaggedNodes.size() != 0) { + for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) { + cerr << " "; + FlaggedNodes[i]->dump(G); + cerr << "\n"; } } -#endif } -/// dump - Print ordering to std::cerr. -/// -void SimpleSched::dump() const { - print(std::cerr); -} -//===----------------------------------------------------------------------===// - - -//===----------------------------------------------------------------------===// -/// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each -/// target node in the graph. -void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &SD) { - if (ViewDAGs) SD.viewGraph(); - BB = SimpleSched(SD, BB).Run(); +void SUnit::dumpAll(const SelectionDAG *G) const { + dump(G); + + cerr << " # preds left : " << NumPredsLeft << "\n"; + cerr << " # succs left : " << NumSuccsLeft << "\n"; + cerr << " Latency : " << Latency << "\n"; + cerr << " Depth : " << Depth << "\n"; + cerr << " Height : " << Height << "\n"; + + if (Preds.size() != 0) { + cerr << " Predecessors:\n"; + for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); + I != E; ++I) { + if (I->isCtrl) + cerr << " ch #"; + else + cerr << " val #"; + cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; + if (I->isSpecial) + cerr << " *"; + cerr << "\n"; + } + } + if (Succs.size() != 0) { + cerr << " Successors:\n"; + for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); + I != E; ++I) { + if (I->isCtrl) + cerr << " ch #"; + else + cerr << " val #"; + cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; + if (I->isSpecial) + cerr << " *"; + cerr << "\n"; + } + } + cerr << "\n"; }