X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=e90bceb7be50f656df299c28f8adcd97ad7fd9ba;hb=3cc6243ddfdba3ad64035b919c88b09773a60880;hp=17938d784a11d6ce0d712cac7ce93e931c1d9480;hpb=713a98dee8ab07a3066d1707a07648d27dd0c19c;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index 17938d784a1..e90bceb7be5 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Evan Cheng 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. // //===----------------------------------------------------------------------===// // @@ -15,24 +15,28 @@ #ifndef LLVM_CODEGEN_SCHEDULEDAG_H #define LLVM_CODEGEN_SCHEDULEDAG_H +#include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/SelectionDAG.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; class MachineModuleInfo; + class MachineRegisterInfo; class MachineInstr; - class MRegisterInfo; + class TargetRegisterInfo; + class ScheduleDAG; class SelectionDAG; class SelectionDAGISel; - class SSARegMap; class TargetInstrInfo; - class TargetInstrDescriptor; + class TargetInstrDesc; + class TargetLowering; class TargetMachine; + class TargetRegisterClass; /// HazardRecognizer - This determines whether or not an instruction can be /// issued this cycle, and whether or not a noop needs to be inserted to handle @@ -54,44 +58,46 @@ 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, /// cost of the depdenency, etc. struct SDep { - SUnit *Dep; // Dependent - either a predecessor or a successor. - bool isCtrl; // True iff it's a control dependency. - unsigned PhyReg; // If non-zero, this dep is a phy register dependency. - int Cost; // Cost of the dependency. - SDep(SUnit *d, bool c, unsigned r, int t) - : Dep(d), isCtrl(c), PhyReg(r), Cost(t) {} + SUnit *Dep; // Dependent - either a predecessor or a successor. + unsigned Reg; // If non-zero, this dep is a phy register dependency. + int Cost; // Cost of the dependency. + bool isCtrl : 1; // True iff it's a control dependency. + bool isSpecial : 1; // True iff it's a special ctrl dep added during sched. + SDep(SUnit *d, unsigned r, int t, bool c, bool s) + : Dep(d), Reg(r), Cost(t), isCtrl(c), isSpecial(s) {} }; /// 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. + 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. @@ -103,54 +109,139 @@ namespace llvm { typedef SmallVector::const_iterator const_pred_iterator; typedef SmallVector::const_iterator const_succ_iterator; - short NumPreds; // # of preds. - short NumSuccs; // # of sucss. + unsigned NodeNum; // Entry # of node in the node vector. + unsigned NodeQueueId; // Queue id of node. + unsigned short Latency; // Node latency. + short NumPreds; // # of non-control preds. + short NumSuccs; // # of non-control sucss. short NumPredsLeft; // # of preds not scheduled. short NumSuccsLeft; // # of succs not scheduled. - short NumChainPredsLeft; // # of chain preds not scheduled. - short NumChainSuccsLeft; // # of chain succs not scheduled. bool isTwoAddress : 1; // Is a two-address instruction. bool isCommutable : 1; // Is a commutable instruction. + bool hasPhysRegDefs : 1; // Has physreg defs that are being used. bool isPending : 1; // True once pending. bool isAvailable : 1; // True once available. bool isScheduled : 1; // True once scheduled. - unsigned short Latency; // Node latency. unsigned CycleBound; // Upper/lower cycle to be scheduled at. unsigned Cycle; // Once scheduled, the cycle of the op. unsigned Depth; // Node depth; unsigned Height; // Node height; - unsigned NodeNum; // Entry # of node in the node vector. + 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), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), - NumChainPredsLeft(0), NumChainSuccsLeft(0), - isTwoAddress(false), isCommutable(false), + : 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), - Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0), - NodeNum(nodenum) {} - + 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, unsigned PhyReg = 0, int Cost = 1) { - for (unsigned i = 0, e = Preds.size(); i != e; ++i) - if (Preds[i].Dep == N && Preds[i].isCtrl == isCtrl) + bool addPred(SUnit *N, bool isCtrl, bool isSpecial, + unsigned PhyReg = 0, int Cost = 1) { + 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; - Preds.push_back(SDep(N, isCtrl, PhyReg, Cost)); + Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial)); + N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial)); + if (!isCtrl) { + ++NumPreds; + ++N->NumSuccs; + } + if (!N->isScheduled) + ++NumPredsLeft; + if (!isScheduled) + ++N->NumSuccsLeft; return true; } - /// addSucc - This adds the specified node as a succ of the current node if - /// not already. This returns true if this is a new succ. - bool addSucc(SUnit *N, bool isCtrl, unsigned PhyReg = 0, int Cost = 1) { - for (unsigned i = 0, e = Succs.size(); i != e; ++i) - if (Succs[i].Dep == N && Succs[i].isCtrl == isCtrl) - return false; - Succs.push_back(SDep(N, isCtrl, PhyReg, Cost)); - return true; + bool removePred(SUnit *N, bool isCtrl, bool isSpecial) { + for (SmallVector::iterator I = Preds.begin(), E = Preds.end(); + I != E; ++I) + if (I->Dep == N && I->isCtrl == isCtrl && I->isSpecial == isSpecial) { + bool FoundSucc = false; + for (SmallVector::iterator II = N->Succs.begin(), + EE = N->Succs.end(); II != EE; ++II) + if (II->Dep == this && + II->isCtrl == isCtrl && II->isSpecial == isSpecial) { + FoundSucc = true; + N->Succs.erase(II); + break; + } + assert(FoundSucc && "Mismatching preds / succs lists!"); + Preds.erase(I); + if (!isCtrl) { + --NumPreds; + --N->NumSuccs; + } + if (!N->isScheduled) + --NumPredsLeft; + if (!isScheduled) + --N->NumSuccsLeft; + return true; + } + return false; + } + + bool isPred(SUnit *N) { + for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) + if (Preds[i].Dep == N) + return true; + return false; } - void dump(const SelectionDAG *G) const; - void dumpAll(const SelectionDAG *G) const; + bool isSucc(SUnit *N) { + for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) + if (Succs[i].Dep == N) + return true; + return false; + } + + void dump(const ScheduleDAG *G) const; + void dumpAll(const ScheduleDAG *G) const; }; //===--------------------------------------------------------------------===// @@ -165,40 +256,47 @@ 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; - + + virtual unsigned size() const = 0; virtual bool empty() const = 0; virtual void push(SUnit *U) = 0; virtual void push_all(const std::vector &Nodes) = 0; virtual SUnit *pop() = 0; + 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 *) {} }; 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 - const MRegisterInfo *MRI; // Target processor register info - SSARegMap *RegMap; // Virtual/real register map + const TargetRegisterInfo *TRI; // Target processor register info + TargetLowering *TLI; // Target lowering info + MachineFunction *MF; // Machine function + MachineRegisterInfo &MRI; // Virtual/real register map MachineConstantPool *ConstPool; // Target constant pool std::vector Sequence; // The schedule. Null SUnit*'s // represent noop instructions. - DenseMap SUnitMap; // SDNode to SUnit mapping (n -> 1). std::vector SUnits; // The scheduling units. - SmallSet CommuteSet; // Nodes the should be commuted. + SmallSet CommuteSet; // Nodes that should be commuted. - ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, - const TargetMachine &tm) - : DAG(dag), BB(bb), TM(tm) {} + ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, + const TargetMachine &tm); virtual ~ScheduleDAG() {} @@ -209,12 +307,13 @@ namespace llvm { /// Run - perform scheduling. /// - MachineBasicBlock *Run(); + void Run(); /// isPassiveNode - Return true if the node is a non-scheduled leaf. /// static 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; @@ -222,21 +321,40 @@ namespace llvm { if (isa(Node)) return true; 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(); } + /// Clone - Creates a clone of the specified SUnit. It does not copy the + /// predecessors / successors info nor the temporary scheduling states. + SUnit *Clone(SUnit *N); + /// 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 BuildSchedUnits(); + /// ComputeLatency - Compute node latency. + /// + void ComputeLatency(SUnit *SU); + /// CalculateDepths, CalculateHeights - Calculate node depth / height. /// void CalculateDepths(); @@ -247,90 +365,126 @@ namespace llvm { /// (which do not go into the machine instrs.) static unsigned CountResults(SDNode *Node); - /// 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. + /// CountOperands - The inputs to target nodes have any actual inputs first, + /// followed by special operands that describe memory references, then an + /// optional chain operand, then flag operands. Compute the number of + /// actual operands that will go into the resulting MachineInstr. static unsigned CountOperands(SDNode *Node); + /// ComputeMemOperandsEnd - Find the index one past the last + /// MemOperandSDNode operand + static unsigned ComputeMemOperandsEnd(SDNode *Node); + /// EmitNode - Generate machine code for an node and needed dependencies. /// VRBaseMap contains, for each already emitted node, the first virtual /// register number for the results of the node. /// - void EmitNode(SDNode *Node, DenseMap &VRBaseMap); + void EmitNode(SDNode *Node, bool IsClone, + DenseMap &VRBaseMap); /// EmitNoop - Emit a noop instruction. /// void EmitNoop(); - /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an - /// implicit physical register output. - void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned SrcReg, - DenseMap &VRBaseMap); - - void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, - const TargetInstrDescriptor &II, - DenseMap &VRBaseMap); - - 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); - - void AddOperand(MachineInstr *MI, SDOperand Op, unsigned IIOpNum, - const TargetInstrDescriptor *II, - DenseMap &VRBaseMap); - }; + DenseMap &VRBaseMap); - /// createBFS_DAGScheduler - This creates a simple breadth first instruction - /// scheduler. - ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); + /// getVR - Return the virtual register corresponding to the specified result + /// of the specified node. + unsigned getVR(SDValue Op, DenseMap &VRBaseMap); - /// createSimpleDAGScheduler - This creates a simple two pass instruction - /// scheduler using instruction itinerary. - ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); + /// 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; - /// createNoItinsDAGScheduler - This creates a simple two pass instruction - /// scheduler without using instruction itinerary. - ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); + void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum, + const TargetInstrDesc *II, + 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, bool IsClone, + unsigned SrcReg, + DenseMap &VRBaseMap); + + void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, + const TargetInstrDesc &II, + 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 + /// if possible. + void EmitLiveInCopy(MachineBasicBlock *MBB, + MachineBasicBlock::iterator &InsertPos, + unsigned VirtReg, unsigned PhysReg, + const TargetRegisterClass *RC, + DenseMap &CopyRegMap); + + /// EmitLiveInCopies - 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. + 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; @@ -364,12 +518,13 @@ 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; } const SUnit *getNode() const { return Node; } bool isCtrlDep() const { return Node->Preds[Operand].isCtrl; } + bool isSpecialDep() const { return Node->Preds[Operand].isSpecial; } }; template <> struct GraphTraits {