X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FCodeGen%2FScheduleDAG.h;h=0c393a0628ac2606a86b86f748d8e0dfc033ffbf;hb=94d7a5f8156e62532870fbaf197377b34e52ff2a;hp=ad44b246261a466de11c7d17f88221bc5ff268a0;hpb=a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5b;p=oota-llvm.git diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index ad44b246261..0c393a0628a 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,6 +15,7 @@ #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" @@ -24,15 +25,18 @@ namespace llvm { struct InstrStage; struct SUnit; class MachineConstantPool; + class MachineFunction; class MachineModuleInfo; + class MachineRegisterInfo; class MachineInstr; - class MRegisterInfo; + class TargetRegisterInfo; 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,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, @@ -93,8 +94,8 @@ namespace llvm { struct SUnit { SDNode *Node; // Representative node. SmallVector FlaggedNodes;// All nodes flagged to Node. - unsigned InstanceNo; // Instance#. One SDNode can be multiple - // SUnit due to cloning. + 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. @@ -107,16 +108,15 @@ 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 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 hasImplicitDefs : 1; // Has implicit physical reg defs. + 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. @@ -124,38 +124,35 @@ namespace llvm { 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), Latency(0), + : Node(node), OrigNode(0), NodeNum(nodenum), NodeQueueId(0), Latency(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), - NumChainPredsLeft(0), NumChainSuccsLeft(0), - isTwoAddress(false), isCommutable(false), hasImplicitDefs(false), + isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), isPending(false), isAvailable(false), isScheduled(false), - CycleBound(0), Cycle(0), Depth(0), Height(0) {} + 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 = 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; Preds.push_back(SDep(N, PhyReg, Cost, isCtrl, isSpecial)); N->Succs.push_back(SDep(this, PhyReg, Cost, isCtrl, isSpecial)); - if (isCtrl) { - if (!N->isScheduled) - ++NumChainPredsLeft; - if (!isScheduled) - ++N->NumChainSuccsLeft; - } else { + if (!isCtrl) { ++NumPreds; ++N->NumSuccs; - if (!N->isScheduled) - ++NumPredsLeft; - if (!isScheduled) - ++N->NumSuccsLeft; } + if (!N->isScheduled) + ++NumPredsLeft; + if (!isScheduled) + ++N->NumSuccsLeft; return true; } @@ -174,33 +171,28 @@ namespace llvm { } assert(FoundSucc && "Mismatching preds / succs lists!"); Preds.erase(I); - if (isCtrl) { - if (!N->isScheduled) - --NumChainPredsLeft; - if (!isScheduled) - --NumChainSuccsLeft; - } else { + if (!isCtrl) { --NumPreds; --N->NumSuccs; - if (!N->isScheduled) - --NumPredsLeft; - if (!isScheduled) - --N->NumSuccsLeft; } + if (!N->isScheduled) + --NumPredsLeft; + if (!isScheduled) + --N->NumSuccsLeft; return true; } return false; } 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; @@ -222,8 +214,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; @@ -240,9 +231,9 @@ namespace llvm { /// 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 ScheduledNode(SUnit *) {} - virtual void UnscheduledNode(SUnit *Node) {} + virtual void UnscheduledNode(SUnit *) {} }; class ScheduleDAG { @@ -251,19 +242,18 @@ namespace llvm { 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 -> n). 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) {} + const TargetMachine &tm); virtual ~ScheduleDAG() {} @@ -280,6 +270,7 @@ namespace llvm { /// 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; @@ -287,13 +278,16 @@ 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(); } @@ -306,6 +300,10 @@ namespace llvm { /// together nodes with a single SUnit. void BuildSchedUnits(); + /// ComputeLatency - Compute node latency. + /// + void ComputeLatency(SUnit *SU); + /// CalculateDepths, CalculateHeights - Calculate node depth / height. /// void CalculateDepths(); @@ -316,32 +314,27 @@ 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, unsigned InstNo, + 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 InstNo, - unsigned SrcReg, - DenseMap &VRBaseMap); - - void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, - const TargetInstrDescriptor &II, - DenseMap &VRBaseMap); - void EmitSchedule(); void dumpSchedule() const; @@ -355,29 +348,47 @@ namespace llvm { /// void EmitSubregNode(SDNode *Node, DenseMap &VRBaseMap); + + /// getVR - Return the virtual register corresponding to the specified result + /// of the specified node. + unsigned getVR(SDOperand 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, - const TargetInstrDescriptor *II, + const TargetInstrDesc *II, DenseMap &VRBaseMap); - }; - /// createBFS_DAGScheduler - This creates a simple breadth first instruction - /// scheduler. - ScheduleDAG *createBFS_DAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); - - /// createSimpleDAGScheduler - This creates a simple two pass instruction - /// scheduler using instruction itinerary. - ScheduleDAG* createSimpleDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); + 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); - /// createNoItinsDAGScheduler - This creates a simple two pass instruction - /// scheduler without using instruction itinerary. - ScheduleDAG* createNoItinsDAGScheduler(SelectionDAGISel *IS, - SelectionDAG *DAG, - MachineBasicBlock *BB); + /// 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); + }; /// createBURRListDAGScheduler - This creates a bottom up register usage /// reduction list scheduler. @@ -435,12 +446,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 {