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/MachineBasicBlock.h" 19 #include "llvm/CodeGen/ScheduleDAG.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 MachineBasicBlock *BB; 39 SelectionDAG *DAG; // DAG of the current basic block 40 const InstrItineraryData *InstrItins; 41 42 /// The schedule. Null SUnit*'s represent noop instructions. 43 std::vector<SUnit*> Sequence; 44 45 explicit ScheduleDAGSDNodes(MachineFunction &mf); 46 ~ScheduleDAGSDNodes()47 virtual ~ScheduleDAGSDNodes() {} 48 49 /// Run - perform scheduling. 50 /// 51 void Run(SelectionDAG *dag, MachineBasicBlock *bb); 52 53 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 54 /// isPassiveNode(SDNode * Node)55 static bool isPassiveNode(SDNode *Node) { 56 if (isa<ConstantSDNode>(Node)) return true; 57 if (isa<ConstantFPSDNode>(Node)) return true; 58 if (isa<RegisterSDNode>(Node)) return true; 59 if (isa<RegisterMaskSDNode>(Node)) return true; 60 if (isa<GlobalAddressSDNode>(Node)) return true; 61 if (isa<BasicBlockSDNode>(Node)) return true; 62 if (isa<FrameIndexSDNode>(Node)) return true; 63 if (isa<ConstantPoolSDNode>(Node)) return true; 64 if (isa<TargetIndexSDNode>(Node)) return true; 65 if (isa<JumpTableSDNode>(Node)) return true; 66 if (isa<ExternalSymbolSDNode>(Node)) return true; 67 if (isa<BlockAddressSDNode>(Node)) return true; 68 if (Node->getOpcode() == ISD::EntryToken || 69 isa<MDNodeSDNode>(Node)) return true; 70 return false; 71 } 72 73 /// NewSUnit - Creates a new SUnit and return a ptr to it. 74 /// 75 SUnit *newSUnit(SDNode *N); 76 77 /// Clone - Creates a clone of the specified SUnit. It does not copy the 78 /// predecessors / successors info nor the temporary scheduling states. 79 /// 80 SUnit *Clone(SUnit *N); 81 82 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 83 /// are input. This SUnit graph is similar to the SelectionDAG, but 84 /// excludes nodes that aren't interesting to scheduling, and represents 85 /// flagged together nodes with a single SUnit. 86 void BuildSchedGraph(AliasAnalysis *AA); 87 88 /// InitVRegCycleFlag - Set isVRegCycle if this node's single use is 89 /// CopyToReg and its only active data operands are CopyFromReg within a 90 /// single block loop. 91 /// 92 void InitVRegCycleFlag(SUnit *SU); 93 94 /// InitNumRegDefsLeft - Determine the # of regs defined by this node. 95 /// 96 void InitNumRegDefsLeft(SUnit *SU); 97 98 /// computeLatency - Compute node latency. 99 /// 100 virtual void computeLatency(SUnit *SU); 101 102 virtual void computeOperandLatency(SDNode *Def, SDNode *Use, 103 unsigned OpIdx, SDep& dep) const; 104 105 /// Schedule - Order nodes according to selected style, filling 106 /// in the Sequence member. 107 /// 108 virtual void Schedule() = 0; 109 110 /// VerifyScheduledSequence - Verify that all SUnits are scheduled and 111 /// consistent with the Sequence of scheduled instructions. 112 void VerifyScheduledSequence(bool isBottomUp); 113 114 /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock 115 /// according to the order specified in Sequence. 116 /// 117 virtual MachineBasicBlock* 118 EmitSchedule(MachineBasicBlock::iterator &InsertPos); 119 120 void dumpNode(const SUnit *SU) const override; 121 122 void dumpSchedule() const; 123 124 std::string getGraphNodeLabel(const SUnit *SU) const override; 125 126 std::string getDAGName() const override; 127 128 virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 129 130 /// RegDefIter - In place iteration over the values defined by an 131 /// SUnit. This does not need copies of the iterator or any other STLisms. 132 /// The iterator creates itself, rather than being provided by the SchedDAG. 133 class RegDefIter { 134 const ScheduleDAGSDNodes *SchedDAG; 135 const SDNode *Node; 136 unsigned DefIdx; 137 unsigned NodeNumDefs; 138 MVT ValueType; 139 public: 140 RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD); 141 IsValid()142 bool IsValid() const { return Node != nullptr; } 143 GetValue()144 MVT GetValue() const { 145 assert(IsValid() && "bad iterator"); 146 return ValueType; 147 } 148 GetNode()149 const SDNode *GetNode() const { 150 return Node; 151 } 152 GetIdx()153 unsigned GetIdx() const { 154 return DefIdx-1; 155 } 156 157 void Advance(); 158 private: 159 void InitNodeNumDefs(); 160 }; 161 162 protected: 163 /// ForceUnitLatencies - Return true if all scheduling edges should be given 164 /// a latency value of one. The default is to return false; schedulers may 165 /// override this as needed. forceUnitLatencies()166 virtual bool forceUnitLatencies() const { return false; } 167 168 private: 169 /// ClusterNeighboringLoads - Cluster loads from "near" addresses into 170 /// combined SUnits. 171 void ClusterNeighboringLoads(SDNode *Node); 172 /// ClusterNodes - Cluster certain nodes which should be scheduled together. 173 /// 174 void ClusterNodes(); 175 176 /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 177 void BuildSchedUnits(); 178 void AddSchedEdges(); 179 180 void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, 181 MachineBasicBlock::iterator InsertPos); 182 }; 183 } 184 185 #endif 186