LLVM API Documentation
00001 //===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the ScheduleDAGSDNodes class, which implements 00011 // scheduling for an SDNode-based dependency graph. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #ifndef SCHEDULEDAGSDNODES_H 00016 #define SCHEDULEDAGSDNODES_H 00017 00018 #include "llvm/CodeGen/ScheduleDAG.h" 00019 #include "llvm/CodeGen/SelectionDAG.h" 00020 00021 namespace llvm { 00022 /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs. 00023 /// 00024 /// Edges between SUnits are initially based on edges in the SelectionDAG, 00025 /// and additional edges can be added by the schedulers as heuristics. 00026 /// SDNodes such as Constants, Registers, and a few others that are not 00027 /// interesting to schedulers are not allocated SUnits. 00028 /// 00029 /// SDNodes with MVT::Flag operands are grouped along with the flagged 00030 /// nodes into a single SUnit so that they are scheduled together. 00031 /// 00032 /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output 00033 /// edges. Physical register dependence information is not carried in 00034 /// the DAG and must be handled explicitly by schedulers. 00035 /// 00036 class ScheduleDAGSDNodes : public ScheduleDAG { 00037 public: 00038 SelectionDAG *DAG; // DAG of the current basic block 00039 00040 explicit ScheduleDAGSDNodes(MachineFunction &mf); 00041 00042 virtual ~ScheduleDAGSDNodes() {} 00043 00044 /// Run - perform scheduling. 00045 /// 00046 void Run(SelectionDAG *dag, MachineBasicBlock *bb, 00047 MachineBasicBlock::iterator insertPos); 00048 00049 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 00050 /// 00051 static bool isPassiveNode(SDNode *Node) { 00052 if (isa<ConstantSDNode>(Node)) return true; 00053 if (isa<ConstantFPSDNode>(Node)) return true; 00054 if (isa<RegisterSDNode>(Node)) return true; 00055 if (isa<GlobalAddressSDNode>(Node)) return true; 00056 if (isa<BasicBlockSDNode>(Node)) return true; 00057 if (isa<FrameIndexSDNode>(Node)) return true; 00058 if (isa<ConstantPoolSDNode>(Node)) return true; 00059 if (isa<JumpTableSDNode>(Node)) return true; 00060 if (isa<ExternalSymbolSDNode>(Node)) return true; 00061 if (isa<MemOperandSDNode>(Node)) return true; 00062 if (Node->getOpcode() == ISD::EntryToken) return true; 00063 return false; 00064 } 00065 00066 /// NewSUnit - Creates a new SUnit and return a ptr to it. 00067 /// 00068 SUnit *NewSUnit(SDNode *N) { 00069 #ifndef NDEBUG 00070 const SUnit *Addr = 0; 00071 if (!SUnits.empty()) 00072 Addr = &SUnits[0]; 00073 #endif 00074 SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 00075 assert((Addr == 0 || Addr == &SUnits[0]) && 00076 "SUnits std::vector reallocated on the fly!"); 00077 SUnits.back().OrigNode = &SUnits.back(); 00078 return &SUnits.back(); 00079 } 00080 00081 /// Clone - Creates a clone of the specified SUnit. It does not copy the 00082 /// predecessors / successors info nor the temporary scheduling states. 00083 /// 00084 SUnit *Clone(SUnit *N); 00085 00086 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 00087 /// are input. This SUnit graph is similar to the SelectionDAG, but 00088 /// excludes nodes that aren't interesting to scheduling, and represents 00089 /// flagged together nodes with a single SUnit. 00090 virtual void BuildSchedGraph(); 00091 00092 /// ComputeLatency - Compute node latency. 00093 /// 00094 virtual void ComputeLatency(SUnit *SU); 00095 00096 /// CountResults - The results of target nodes have register or immediate 00097 /// operands first, then an optional chain, and optional flag operands 00098 /// (which do not go into the machine instrs.) 00099 static unsigned CountResults(SDNode *Node); 00100 00101 /// CountOperands - The inputs to target nodes have any actual inputs first, 00102 /// followed by special operands that describe memory references, then an 00103 /// optional chain operand, then flag operands. Compute the number of 00104 /// actual operands that will go into the resulting MachineInstr. 00105 static unsigned CountOperands(SDNode *Node); 00106 00107 /// ComputeMemOperandsEnd - Find the index one past the last 00108 /// MemOperandSDNode operand 00109 static unsigned ComputeMemOperandsEnd(SDNode *Node); 00110 00111 /// EmitNode - Generate machine code for an node and needed dependencies. 00112 /// VRBaseMap contains, for each already emitted node, the first virtual 00113 /// register number for the results of the node. 00114 /// 00115 void EmitNode(SDNode *Node, bool IsClone, bool HasClone, 00116 DenseMap<SDValue, unsigned> &VRBaseMap); 00117 00118 virtual MachineBasicBlock *EmitSchedule(); 00119 00120 /// Schedule - Order nodes according to selected style, filling 00121 /// in the Sequence member. 00122 /// 00123 virtual void Schedule() = 0; 00124 00125 virtual void dumpNode(const SUnit *SU) const; 00126 00127 virtual std::string getGraphNodeLabel(const SUnit *SU) const; 00128 00129 virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 00130 00131 private: 00132 /// EmitSubregNode - Generate machine code for subreg nodes. 00133 /// 00134 void EmitSubregNode(SDNode *Node, 00135 DenseMap<SDValue, unsigned> &VRBaseMap); 00136 00137 /// EmitCopyToRegClassNode - Generate machine code for COPY_TO_REGCLASS 00138 /// nodes. 00139 /// 00140 void EmitCopyToRegClassNode(SDNode *Node, 00141 DenseMap<SDValue, unsigned> &VRBaseMap); 00142 00143 /// getVR - Return the virtual register corresponding to the specified result 00144 /// of the specified node. 00145 unsigned getVR(SDValue Op, DenseMap<SDValue, unsigned> &VRBaseMap); 00146 00147 /// getDstOfCopyToRegUse - If the only use of the specified result number of 00148 /// node is a CopyToReg, return its destination register. Return 0 otherwise. 00149 unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const; 00150 00151 void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum, 00152 const TargetInstrDesc *II, 00153 DenseMap<SDValue, unsigned> &VRBaseMap); 00154 00155 /// AddRegisterOperand - Add the specified register as an operand to the 00156 /// specified machine instr. Insert register copies if the register is 00157 /// not in the required register class. 00158 void AddRegisterOperand(MachineInstr *MI, SDValue Op, 00159 unsigned IIOpNum, const TargetInstrDesc *II, 00160 DenseMap<SDValue, unsigned> &VRBaseMap); 00161 00162 /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an 00163 /// implicit physical register output. 00164 void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, 00165 bool IsCloned, unsigned SrcReg, 00166 DenseMap<SDValue, unsigned> &VRBaseMap); 00167 00168 void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, 00169 const TargetInstrDesc &II, bool IsClone, 00170 bool IsCloned, 00171 DenseMap<SDValue, unsigned> &VRBaseMap); 00172 00173 /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 00174 void BuildSchedUnits(); 00175 void AddSchedEdges(); 00176 }; 00177 } 00178 00179 #endif