diff options
Diffstat (limited to 'release_23/include/llvm/CodeGen/ScheduleDAG.h')
| -rw-r--r-- | release_23/include/llvm/CodeGen/ScheduleDAG.h | 487 |
1 files changed, 0 insertions, 487 deletions
diff --git a/release_23/include/llvm/CodeGen/ScheduleDAG.h b/release_23/include/llvm/CodeGen/ScheduleDAG.h deleted file mode 100644 index d49c7db6fde6..000000000000 --- a/release_23/include/llvm/CodeGen/ScheduleDAG.h +++ /dev/null @@ -1,487 +0,0 @@ -//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the ScheduleDAG class, which is used as the common -// base class for SelectionDAG-based instruction scheduler. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_SCHEDULEDAG_H -#define LLVM_CODEGEN_SCHEDULEDAG_H - -#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; - class MachineModuleInfo; - class MachineRegisterInfo; - class MachineInstr; - class TargetRegisterInfo; - class SelectionDAG; - class SelectionDAGISel; - class TargetInstrInfo; - 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 - /// the hazard. - class HazardRecognizer { - public: - virtual ~HazardRecognizer(); - - enum HazardType { - NoHazard, // This instruction can be emitted at this cycle. - Hazard, // This instruction can't be emitted at this cycle. - NoopHazard // This instruction can't be emitted, and needs noops. - }; - - /// getHazardType - Return the hazard type of emitting this node. There are - /// three possible results. Either: - /// * NoHazard: it is legal to issue this instruction on this cycle. - /// * Hazard: issuing this instruction would stall the machine. If some - /// other instruction is available, issue it first. - /// * NoopHazard: issuing this instruction would break the program. If - /// some other instruction can be issued, do so, otherwise issue a noop. - virtual HazardType getHazardType(SDNode *Node) { - return NoHazard; - } - - /// EmitInstruction - This callback is invoked when an instruction is - /// emitted, to advance the hazard state. - virtual void EmitInstruction(SDNode *Node) { - } - - /// AdvanceCycle - This callback is invoked when no instructions can be - /// issued on this cycle without a hazard. This should increment the - /// internal state of the hazard recognizer so that previously "Hazard" - /// instructions will now not be hazards. - virtual void AdvanceCycle() { - } - - /// EmitNoop - This callback is invoked when a noop was added to the - /// instruction stream. - virtual void EmitNoop() { - } - }; - - /// 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. - 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 { - SDNode *Node; // Representative node. - SmallVector<SDNode*,4> FlaggedNodes;// All nodes flagged to Node. - unsigned InstanceNo; // Instance#. One SDNode can be multiple - // SUnit due to cloning. - - // 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. - SmallVector<SDep, 4> Preds; // All sunit predecessors. - SmallVector<SDep, 4> Succs; // All sunit successors. - - typedef SmallVector<SDep, 4>::iterator pred_iterator; - typedef SmallVector<SDep, 4>::iterator succ_iterator; - typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; - typedef SmallVector<SDep, 4>::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 NumPredsLeft; // # of preds not scheduled. - short NumSuccsLeft; // # of 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 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; - const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. - const TargetRegisterClass *CopySrcRC; - - SUnit(SDNode *node, unsigned nodenum) - : Node(node), InstanceNo(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) {} - - /// 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 = (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, 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; - } - - bool removePred(SUnit *N, bool isCtrl, bool isSpecial) { - for (SmallVector<SDep, 4>::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<SDep, 4>::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; - } - - 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 SelectionDAG *G) const; - void dumpAll(const SelectionDAG *G) const; - }; - - //===--------------------------------------------------------------------===// - /// SchedulingPriorityQueue - This interface is used to plug different - /// priorities computation algorithms into the list scheduler. It implements - /// the interface of a standard priority queue, where nodes are inserted in - /// arbitrary order and returned in priority order. The computation of the - /// priority and the representation of the queue are totally up to the - /// implementation to decide. - /// - class SchedulingPriorityQueue { - public: - virtual ~SchedulingPriorityQueue() {} - - virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &SUMap, - std::vector<SUnit> &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<SUnit *> &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) {} - - virtual void UnscheduledNode(SUnit *Node) {} - }; - - class ScheduleDAG { - public: - 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 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<SUnit*> Sequence; // The schedule. Null SUnit*'s - // represent noop instructions. - DenseMap<SDNode*, std::vector<SUnit*> > SUnitMap; - // SDNode to SUnit mapping (n -> n). - std::vector<SUnit> SUnits; // The scheduling units. - SmallSet<SDNode*, 16> CommuteSet; // Nodes that should be commuted. - - ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, - const TargetMachine &tm); - - virtual ~ScheduleDAG() {} - - /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered - /// using 'dot'. - /// - void viewGraph(); - - /// Run - perform scheduling. - /// - MachineBasicBlock *Run(); - - /// isPassiveNode - Return true if the node is a non-scheduled leaf. - /// - static bool isPassiveNode(SDNode *Node) { - if (isa<ConstantSDNode>(Node)) return true; - if (isa<ConstantFPSDNode>(Node)) return true; - if (isa<RegisterSDNode>(Node)) return true; - if (isa<GlobalAddressSDNode>(Node)) return true; - if (isa<BasicBlockSDNode>(Node)) return true; - if (isa<FrameIndexSDNode>(Node)) return true; - if (isa<ConstantPoolSDNode>(Node)) return true; - if (isa<JumpTableSDNode>(Node)) return true; - if (isa<ExternalSymbolSDNode>(Node)) return true; - if (isa<MemOperandSDNode>(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, (unsigned)SUnits.size())); - 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(); - void CalculateHeights(); - - /// 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.) - static unsigned CountResults(SDNode *Node); - - /// 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, unsigned InstNo, - DenseMap<SDOperand, unsigned> &VRBaseMap); - - /// EmitNoop - Emit a noop instruction. - /// - void EmitNoop(); - - void EmitSchedule(); - - void dumpSchedule() const; - - /// Schedule - Order nodes according to selected style. - /// - virtual void Schedule() {} - - private: - /// EmitSubregNode - Generate machine code for subreg nodes. - /// - void EmitSubregNode(SDNode *Node, - DenseMap<SDOperand, unsigned> &VRBaseMap); - - /// getVR - Return the virtual register corresponding to the specified result - /// of the specified node. - unsigned getVR(SDOperand Op, DenseMap<SDOperand, unsigned> &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, - const TargetInstrDesc *II, - DenseMap<SDOperand, unsigned> &VRBaseMap); - - void AddMemOperand(MachineInstr *MI, const MachineMemOperand &MO); - - void EmitCrossRCCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); - - /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an - /// implicit physical register output. - void EmitCopyFromReg(SDNode *Node, unsigned ResNo, unsigned InstNo, - unsigned SrcReg, - DenseMap<SDOperand, unsigned> &VRBaseMap); - - void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, - const TargetInstrDesc &II, - DenseMap<SDOperand, unsigned> &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<MachineInstr*, unsigned> &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); - }; - - /// createBURRListDAGScheduler - This creates a bottom up register usage - /// reduction list scheduler. - ScheduleDAG* createBURRListDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); - - /// createTDRRListDAGScheduler - This creates a top down register usage - /// reduction list scheduler. - ScheduleDAG* createTDRRListDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); - - /// createTDListDAGScheduler - This creates a top-down list scheduler with - /// a hazard recognizer. - ScheduleDAG* createTDListDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); - - /// createDefaultScheduler - This creates an instruction scheduler appropriate - /// for the target. - ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); - - class SUnitIterator : public forward_iterator<SUnit, ptrdiff_t> { - SUnit *Node; - unsigned Operand; - - SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} - public: - bool operator==(const SUnitIterator& x) const { - return Operand == x.Operand; - } - bool operator!=(const SUnitIterator& x) const { return !operator==(x); } - - const SUnitIterator &operator=(const SUnitIterator &I) { - assert(I.Node == Node && "Cannot assign iterators to two different nodes!"); - Operand = I.Operand; - return *this; - } - - pointer operator*() const { - return Node->Preds[Operand].Dep; - } - pointer operator->() const { return operator*(); } - - SUnitIterator& operator++() { // Preincrement - ++Operand; - return *this; - } - SUnitIterator operator++(int) { // Postincrement - SUnitIterator tmp = *this; ++*this; return tmp; - } - - static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } - static SUnitIterator end (SUnit *N) { - 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<SUnit*> { - typedef SUnit NodeType; - typedef SUnitIterator ChildIteratorType; - static inline NodeType *getEntryNode(SUnit *N) { return N; } - static inline ChildIteratorType child_begin(NodeType *N) { - return SUnitIterator::begin(N); - } - static inline ChildIteratorType child_end(NodeType *N) { - return SUnitIterator::end(N); - } - }; - - template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { - typedef std::vector<SUnit>::iterator nodes_iterator; - static nodes_iterator nodes_begin(ScheduleDAG *G) { - return G->SUnits.begin(); - } - static nodes_iterator nodes_end(ScheduleDAG *G) { - return G->SUnits.end(); - } - }; -} - -#endif |