1 //===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the ScheduleDAGSDNodes class, which implements 11 // scheduling for an SDNode-based dependency graph. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef SCHEDULEDAGSDNODES_H 16 #define SCHEDULEDAGSDNODES_H 17 18 #include "llvm/CodeGen/ScheduleDAG.h" 19 #include "llvm/CodeGen/SelectionDAG.h" 20 21 namespace llvm { 22 /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs. 23 /// 24 /// Edges between SUnits are initially based on edges in the SelectionDAG, 25 /// and additional edges can be added by the schedulers as heuristics. 26 /// SDNodes such as Constants, Registers, and a few others that are not 27 /// interesting to schedulers are not allocated SUnits. 28 /// 29 /// SDNodes with MVT::Glue operands are grouped along with the flagged 30 /// nodes into a single SUnit so that they are scheduled together. 31 /// 32 /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output 33 /// edges. Physical register dependence information is not carried in 34 /// the DAG and must be handled explicitly by schedulers. 35 /// 36 class ScheduleDAGSDNodes : public ScheduleDAG { 37 public: 38 SelectionDAG *DAG; // DAG of the current basic block 39 const InstrItineraryData *InstrItins; 40 41 explicit ScheduleDAGSDNodes(MachineFunction &mf); 42 ~ScheduleDAGSDNodes()43 virtual ~ScheduleDAGSDNodes() {} 44 45 /// Run - perform scheduling. 46 /// 47 void Run(SelectionDAG *dag, MachineBasicBlock *bb, 48 MachineBasicBlock::iterator insertPos); 49 50 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 51 /// isPassiveNode(SDNode * Node)52 static bool isPassiveNode(SDNode *Node) { 53 if (isa<ConstantSDNode>(Node)) return true; 54 if (isa<ConstantFPSDNode>(Node)) return true; 55 if (isa<RegisterSDNode>(Node)) return true; 56 if (isa<GlobalAddressSDNode>(Node)) return true; 57 if (isa<BasicBlockSDNode>(Node)) return true; 58 if (isa<FrameIndexSDNode>(Node)) return true; 59 if (isa<ConstantPoolSDNode>(Node)) return true; 60 if (isa<JumpTableSDNode>(Node)) return true; 61 if (isa<ExternalSymbolSDNode>(Node)) return true; 62 if (isa<BlockAddressSDNode>(Node)) return true; 63 if (Node->getOpcode() == ISD::EntryToken || 64 isa<MDNodeSDNode>(Node)) return true; 65 return false; 66 } 67 68 /// NewSUnit - Creates a new SUnit and return a ptr to it. 69 /// 70 SUnit *NewSUnit(SDNode *N); 71 72 /// Clone - Creates a clone of the specified SUnit. It does not copy the 73 /// predecessors / successors info nor the temporary scheduling states. 74 /// 75 SUnit *Clone(SUnit *N); 76 77 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 78 /// are input. This SUnit graph is similar to the SelectionDAG, but 79 /// excludes nodes that aren't interesting to scheduling, and represents 80 /// flagged together nodes with a single SUnit. 81 virtual void BuildSchedGraph(AliasAnalysis *AA); 82 83 /// InitVRegCycleFlag - Set isVRegCycle if this node's single use is 84 /// CopyToReg and its only active data operands are CopyFromReg within a 85 /// single block loop. 86 /// 87 void InitVRegCycleFlag(SUnit *SU); 88 89 /// InitNumRegDefsLeft - Determine the # of regs defined by this node. 90 /// 91 void InitNumRegDefsLeft(SUnit *SU); 92 93 /// ComputeLatency - Compute node latency. 94 /// 95 virtual void ComputeLatency(SUnit *SU); 96 97 /// ComputeOperandLatency - Override dependence edge latency using 98 /// operand use/def information 99 /// ComputeOperandLatency(SUnit * Def,SUnit * Use,SDep & dep)100 virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use, 101 SDep& dep) const { } 102 103 virtual void ComputeOperandLatency(SDNode *Def, SDNode *Use, 104 unsigned OpIdx, SDep& dep) const; 105 106 virtual MachineBasicBlock *EmitSchedule(); 107 108 /// Schedule - Order nodes according to selected style, filling 109 /// in the Sequence member. 110 /// 111 virtual void Schedule() = 0; 112 113 virtual void dumpNode(const SUnit *SU) const; 114 115 virtual std::string getGraphNodeLabel(const SUnit *SU) const; 116 117 virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 118 119 /// RegDefIter - In place iteration over the values defined by an 120 /// SUnit. This does not need copies of the iterator or any other STLisms. 121 /// The iterator creates itself, rather than being provided by the SchedDAG. 122 class RegDefIter { 123 const ScheduleDAGSDNodes *SchedDAG; 124 const SDNode *Node; 125 unsigned DefIdx; 126 unsigned NodeNumDefs; 127 EVT ValueType; 128 public: 129 RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD); 130 IsValid()131 bool IsValid() const { return Node != NULL; } 132 GetValue()133 EVT GetValue() const { 134 assert(IsValid() && "bad iterator"); 135 return ValueType; 136 } 137 GetNode()138 const SDNode *GetNode() const { 139 return Node; 140 } 141 GetIdx()142 unsigned GetIdx() const { 143 return DefIdx-1; 144 } 145 146 void Advance(); 147 private: 148 void InitNodeNumDefs(); 149 }; 150 151 private: 152 /// ClusterNeighboringLoads - Cluster loads from "near" addresses into 153 /// combined SUnits. 154 void ClusterNeighboringLoads(SDNode *Node); 155 /// ClusterNodes - Cluster certain nodes which should be scheduled together. 156 /// 157 void ClusterNodes(); 158 159 /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 160 void BuildSchedUnits(); 161 void AddSchedEdges(); 162 }; 163 } 164 165 #endif 166