X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=e90bceb7be50f656df299c28f8adcd97ad7fd9ba;hb=3cc6243ddfdba3ad64035b919c88b09773a60880;hp=ebc21a164ba634bc3493abaa330de2639440edd5;hpb=89bf0a6b05c8c353890c88ed1c10dec96a9a7bd8;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index ebc21a164ba..e90bceb7be5 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -17,13 +17,11 @@ #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/SelectionDAG.h" -#include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallSet.h" namespace llvm { - struct InstrStage; struct SUnit; class MachineConstantPool; class MachineFunction; @@ -31,6 +29,7 @@ namespace llvm { class MachineRegisterInfo; class MachineInstr; class TargetRegisterInfo; + class ScheduleDAG; class SelectionDAG; class SelectionDAGISel; class TargetInstrInfo; @@ -59,26 +58,23 @@ namespace llvm { /// other instruction is available, issue it first. /// * NoopHazard: issuing this instruction would break the program. If /// some other instruction can be issued, do so, otherwise issue a noop. - virtual HazardType getHazardType(SDNode *Node) { + virtual HazardType getHazardType(SDNode *) { return NoHazard; } /// EmitInstruction - This callback is invoked when an instruction is /// emitted, to advance the hazard state. - virtual void EmitInstruction(SDNode *Node) { - } + virtual void EmitInstruction(SDNode *) {} /// AdvanceCycle - This callback is invoked when no instructions can be /// issued on this cycle without a hazard. This should increment the /// internal state of the hazard recognizer so that previously "Hazard" /// instructions will now not be hazards. - virtual void AdvanceCycle() { - } + virtual void AdvanceCycle() {} /// EmitNoop - This callback is invoked when a noop was added to the /// instruction stream. - virtual void EmitNoop() { - } + virtual void EmitNoop() {} }; /// SDep - Scheduling dependency. It keeps track of dependent nodes, @@ -96,10 +92,12 @@ namespace llvm { /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or /// a group of nodes flagged together. struct SUnit { + private: SDNode *Node; // Representative node. - SmallVector FlaggedNodes;// All nodes flagged to Node. - unsigned InstanceNo; // Instance#. One SDNode can be multiple - // SUnit due to cloning. + MachineInstr *Instr; // Alternatively, a MachineInstr. + public: + SUnit *OrigNode; // If not this, the node from which + // this node was cloned. // Preds/Succs - The SUnits before/after us in the graph. The boolean value // is true if the edge is a token chain edge, false if it is a value edge. @@ -112,9 +110,10 @@ namespace llvm { typedef SmallVector::const_iterator const_succ_iterator; unsigned NodeNum; // Entry # of node in the node vector. + unsigned NodeQueueId; // Queue id of node. unsigned short Latency; // Node latency. - short NumPreds; // # of preds. - short NumSuccs; // # of sucss. + short NumPreds; // # of non-control preds. + short NumSuccs; // # of non-control sucss. short NumPredsLeft; // # of preds not scheduled. short NumSuccsLeft; // # of succs not scheduled. bool isTwoAddress : 1; // Is a two-address instruction. @@ -130,19 +129,59 @@ namespace llvm { const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. const TargetRegisterClass *CopySrcRC; + /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent + /// an SDNode and any nodes flagged to it. SUnit(SDNode *node, unsigned nodenum) - : Node(node), InstanceNo(0), NodeNum(nodenum), Latency(0), - NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), + : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), NodeQueueId(0), + Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), + isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), + isPending(false), isAvailable(false), isScheduled(false), + CycleBound(0), Cycle(0), Depth(0), Height(0), + CopyDstRC(NULL), CopySrcRC(NULL) {} + + /// SUnit - Construct an SUnit for post-regalloc scheduling to represent + /// a MachineInstr. + SUnit(MachineInstr *instr, unsigned nodenum) + : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), NodeQueueId(0), + Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), isPending(false), isAvailable(false), isScheduled(false), CycleBound(0), Cycle(0), Depth(0), Height(0), CopyDstRC(NULL), CopySrcRC(NULL) {} + /// setNode - Assign the representative SDNode for this SUnit. + /// This may be used during pre-regalloc scheduling. + void setNode(SDNode *N) { + assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); + Node = N; + } + + /// getNode - Return the representative SDNode for this SUnit. + /// This may be used during pre-regalloc scheduling. + SDNode *getNode() const { + assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); + return Node; + } + + /// setInstr - Assign the instruction for the SUnit. + /// This may be used during post-regalloc scheduling. + void setInstr(MachineInstr *MI) { + assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); + Instr = MI; + } + + /// getInstr - Return the representative MachineInstr for this SUnit. + /// This may be used during post-regalloc scheduling. + MachineInstr *getInstr() const { + assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); + return Instr; + } + /// addPred - This adds the specified node as a pred of the current node if /// not already. This returns true if this is a new pred. bool addPred(SUnit *N, bool isCtrl, bool isSpecial, unsigned PhyReg = 0, int Cost = 1) { - for (unsigned i = 0, e = Preds.size(); i != e; ++i) + for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) if (Preds[i].Dep == N && Preds[i].isCtrl == isCtrl && Preds[i].isSpecial == isSpecial) return false; @@ -188,21 +227,21 @@ namespace llvm { } bool isPred(SUnit *N) { - for (unsigned i = 0, e = Preds.size(); i != e; ++i) + for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) if (Preds[i].Dep == N) return true; return false; } bool isSucc(SUnit *N) { - for (unsigned i = 0, e = Succs.size(); i != e; ++i) + for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) if (Succs[i].Dep == N) return true; return false; } - void dump(const SelectionDAG *G) const; - void dumpAll(const SelectionDAG *G) const; + void dump(const ScheduleDAG *G) const; + void dumpAll(const ScheduleDAG *G) const; }; //===--------------------------------------------------------------------===// @@ -217,8 +256,7 @@ namespace llvm { public: virtual ~SchedulingPriorityQueue() {} - virtual void initNodes(DenseMap > &SUMap, - std::vector &SUnits) = 0; + virtual void initNodes(std::vector &SUnits) = 0; virtual void addNode(const SUnit *SU) = 0; virtual void updateNode(const SUnit *SU) = 0; virtual void releaseState() = 0; @@ -233,16 +271,17 @@ namespace llvm { virtual void remove(SUnit *SU) = 0; /// ScheduledNode - As each node is scheduled, this method is invoked. This - /// allows the priority function to adjust the priority of node that have - /// already been emitted. - virtual void ScheduledNode(SUnit *Node) {} + /// allows the priority function to adjust the priority of related + /// unscheduled nodes, for example. + /// + virtual void ScheduledNode(SUnit *) {} - virtual void UnscheduledNode(SUnit *Node) {} + virtual void UnscheduledNode(SUnit *) {} }; class ScheduleDAG { public: - SelectionDAG &DAG; // DAG of the current basic block + SelectionDAG *DAG; // DAG of the current basic block MachineBasicBlock *BB; // Current basic block const TargetMachine &TM; // Target processor const TargetInstrInfo *TII; // Target instruction information @@ -253,12 +292,10 @@ namespace llvm { MachineConstantPool *ConstPool; // Target constant pool std::vector Sequence; // The schedule. Null SUnit*'s // represent noop instructions. - DenseMap > SUnitMap; - // SDNode to SUnit mapping (n -> n). std::vector SUnits; // The scheduling units. SmallSet CommuteSet; // Nodes that should be commuted. - ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, + ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, const TargetMachine &tm); virtual ~ScheduleDAG() {} @@ -270,7 +307,7 @@ namespace llvm { /// Run - perform scheduling. /// - MachineBasicBlock *Run(); + void Run(); /// isPassiveNode - Return true if the node is a non-scheduled leaf. /// @@ -285,13 +322,23 @@ namespace llvm { if (isa(Node)) return true; if (isa(Node)) return true; if (isa(Node)) return true; + if (Node->getOpcode() == ISD::EntryToken) return true; return false; } /// NewSUnit - Creates a new SUnit and return a ptr to it. /// SUnit *NewSUnit(SDNode *N) { - SUnits.push_back(SUnit(N, SUnits.size())); + SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); + SUnits.back().OrigNode = &SUnits.back(); + return &SUnits.back(); + } + + /// NewSUnit - Creates a new SUnit and return a ptr to it. + /// + SUnit *NewSUnit(MachineInstr *MI) { + SUnits.push_back(SUnit(MI, (unsigned)SUnits.size())); + SUnits.back().OrigNode = &SUnits.back(); return &SUnits.back(); } @@ -332,52 +379,52 @@ namespace llvm { /// VRBaseMap contains, for each already emitted node, the first virtual /// register number for the results of the node. /// - void EmitNode(SDNode *Node, unsigned InstNo, - DenseMap &VRBaseMap); + void EmitNode(SDNode *Node, bool IsClone, + DenseMap &VRBaseMap); /// EmitNoop - Emit a noop instruction. /// void EmitNoop(); - void EmitSchedule(); + MachineBasicBlock *EmitSchedule(); void dumpSchedule() const; - /// Schedule - Order nodes according to selected style. + /// Schedule - Order nodes according to selected style, filling + /// in the Sequence member. /// - virtual void Schedule() {} + virtual void Schedule() = 0; private: /// EmitSubregNode - Generate machine code for subreg nodes. /// void EmitSubregNode(SDNode *Node, - DenseMap &VRBaseMap); + DenseMap &VRBaseMap); /// getVR - Return the virtual register corresponding to the specified result /// of the specified node. - unsigned getVR(SDOperand Op, DenseMap &VRBaseMap); + unsigned getVR(SDValue Op, DenseMap &VRBaseMap); /// getDstOfCopyToRegUse - If the only use of the specified result number of /// node is a CopyToReg, return its destination register. Return 0 otherwise. unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const; - void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, + void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum, const TargetInstrDesc *II, - DenseMap &VRBaseMap); - + DenseMap &VRBaseMap); void AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO); void EmitCrossRCCopy(SUnit *SU, DenseMap &VRBaseMap); /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an /// implicit physical register output. - void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned InstNo, + void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, unsigned SrcReg, - DenseMap &VRBaseMap); + DenseMap &VRBaseMap); void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, const TargetInstrDesc &II, - DenseMap &VRBaseMap); + DenseMap &VRBaseMap); /// EmitLiveInCopy - Emit a copy for a live in physical register. If the /// physical register has only a single copy use, then coalesced the copy @@ -392,31 +439,52 @@ namespace llvm { /// and if it has live ins that need to be copied into vregs, emit the /// copies into the top of the block. void EmitLiveInCopies(MachineBasicBlock *MBB); + + /// BuildSchedUnitsFromMBB - Build SUnits from the MachineBasicBlock. + /// This SUnit graph is similar to the pre-regalloc SUnit graph, but represents + /// MachineInstrs directly instead of SDNodes. + void BuildSchedUnitsFromMBB(); }; /// createBURRListDAGScheduler - This creates a bottom up register usage /// reduction list scheduler. ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB); + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); /// createTDRRListDAGScheduler - This creates a top down register usage /// reduction list scheduler. ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB); + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); /// createTDListDAGScheduler - This creates a top-down list scheduler with /// a hazard recognizer. ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB); + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); + /// createFastDAGScheduler - This creates a "fast" scheduler. + /// + ScheduleDAG *createFastDAGScheduler(SelectionDAGISel *IS, + SelectionDAG *DAG, + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); + /// createDefaultScheduler - This creates an instruction scheduler appropriate /// for the target. ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, SelectionDAG *DAG, - MachineBasicBlock *BB); + const TargetMachine *TM, + MachineBasicBlock *BB, + bool Fast); class SUnitIterator : public forward_iterator { SUnit *Node; @@ -450,7 +518,7 @@ namespace llvm { static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } static SUnitIterator end (SUnit *N) { - return SUnitIterator(N, N->Preds.size()); + return SUnitIterator(N, (unsigned)N->Preds.size()); } unsigned getOperand() const { return Operand; }