1 //===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the ScheduleDAGSDNodes class, which implements 10 // scheduling for an SDNode-based dependency graph. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H 15 #define LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H 16 17 #include "llvm/CodeGen/ISDOpcodes.h" 18 #include "llvm/CodeGen/MachineBasicBlock.h" 19 #include "llvm/CodeGen/ScheduleDAG.h" 20 #include "llvm/CodeGen/SelectionDAGNodes.h" 21 #include "llvm/Support/Casting.h" 22 #include "llvm/Support/MachineValueType.h" 23 #include <cassert> 24 #include <string> 25 #include <vector> 26 27 namespace llvm { 28 29 class InstrItineraryData; 30 31 /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs. 32 /// 33 /// Edges between SUnits are initially based on edges in the SelectionDAG, 34 /// and additional edges can be added by the schedulers as heuristics. 35 /// SDNodes such as Constants, Registers, and a few others that are not 36 /// interesting to schedulers are not allocated SUnits. 37 /// 38 /// SDNodes with MVT::Glue operands are grouped along with the flagged 39 /// nodes into a single SUnit so that they are scheduled together. 40 /// 41 /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output 42 /// edges. Physical register dependence information is not carried in 43 /// the DAG and must be handled explicitly by schedulers. 44 /// 45 class ScheduleDAGSDNodes : public ScheduleDAG { 46 public: 47 MachineBasicBlock *BB; 48 SelectionDAG *DAG; // DAG of the current basic block 49 const InstrItineraryData *InstrItins; 50 51 /// The schedule. Null SUnit*'s represent noop instructions. 52 std::vector<SUnit*> Sequence; 53 54 explicit ScheduleDAGSDNodes(MachineFunction &mf); 55 56 ~ScheduleDAGSDNodes() override = default; 57 58 /// Run - perform scheduling. 59 /// 60 void Run(SelectionDAG *dag, MachineBasicBlock *bb); 61 62 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 63 /// 64 static bool isPassiveNode(SDNode *Node) { 65 if (isa<ConstantSDNode>(Node)) return true; 66 if (isa<ConstantFPSDNode>(Node)) return true; 67 if (isa<RegisterSDNode>(Node)) return true; 68 if (isa<RegisterMaskSDNode>(Node)) return true; 69 if (isa<GlobalAddressSDNode>(Node)) return true; 70 if (isa<BasicBlockSDNode>(Node)) return true; 71 if (isa<FrameIndexSDNode>(Node)) return true; 72 if (isa<ConstantPoolSDNode>(Node)) return true; 73 if (isa<TargetIndexSDNode>(Node)) return true; 74 if (isa<JumpTableSDNode>(Node)) return true; 75 if (isa<ExternalSymbolSDNode>(Node)) return true; 76 if (isa<MCSymbolSDNode>(Node)) return true; 77 if (isa<BlockAddressSDNode>(Node)) return true; 78 if (Node->getOpcode() == ISD::EntryToken || 79 isa<MDNodeSDNode>(Node)) return true; 80 return false; 81 } 82 83 /// NewSUnit - Creates a new SUnit and return a ptr to it. 84 /// 85 SUnit *newSUnit(SDNode *N); 86 87 /// Clone - Creates a clone of the specified SUnit. It does not copy the 88 /// predecessors / successors info nor the temporary scheduling states. 89 /// 90 SUnit *Clone(SUnit *Old); 91 92 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 93 /// are input. This SUnit graph is similar to the SelectionDAG, but 94 /// excludes nodes that aren't interesting to scheduling, and represents 95 /// flagged together nodes with a single SUnit. 96 void BuildSchedGraph(AliasAnalysis *AA); 97 98 /// InitNumRegDefsLeft - Determine the # of regs defined by this node. 99 /// 100 void InitNumRegDefsLeft(SUnit *SU); 101 102 /// computeLatency - Compute node latency. 103 /// 104 virtual void computeLatency(SUnit *SU); 105 106 virtual void computeOperandLatency(SDNode *Def, SDNode *Use, 107 unsigned OpIdx, SDep& dep) const; 108 109 /// Schedule - Order nodes according to selected style, filling 110 /// in the Sequence member. 111 /// 112 virtual void Schedule() = 0; 113 114 /// VerifyScheduledSequence - Verify that all SUnits are scheduled and 115 /// consistent with the Sequence of scheduled instructions. 116 void VerifyScheduledSequence(bool isBottomUp); 117 118 /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock 119 /// according to the order specified in Sequence. 120 /// 121 virtual MachineBasicBlock* 122 EmitSchedule(MachineBasicBlock::iterator &InsertPos); 123 124 void dumpNode(const SUnit &SU) const override; 125 void dump() const override; 126 void dumpSchedule() const; 127 128 std::string getGraphNodeLabel(const SUnit *SU) const override; 129 130 std::string getDAGName() const override; 131 132 virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 133 134 /// RegDefIter - In place iteration over the values defined by an 135 /// SUnit. This does not need copies of the iterator or any other STLisms. 136 /// The iterator creates itself, rather than being provided by the SchedDAG. 137 class RegDefIter { 138 const ScheduleDAGSDNodes *SchedDAG; 139 const SDNode *Node; 140 unsigned DefIdx; 141 unsigned NodeNumDefs; 142 MVT ValueType; 143 144 public: 145 RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD); 146 147 bool IsValid() const { return Node != nullptr; } 148 149 MVT GetValue() const { 150 assert(IsValid() && "bad iterator"); 151 return ValueType; 152 } 153 154 const SDNode *GetNode() const { 155 return Node; 156 } 157 158 unsigned GetIdx() const { 159 return DefIdx-1; 160 } 161 162 void Advance(); 163 164 private: 165 void InitNodeNumDefs(); 166 }; 167 168 protected: 169 /// ForceUnitLatencies - Return true if all scheduling edges should be given 170 /// a latency value of one. The default is to return false; schedulers may 171 /// override this as needed. 172 virtual bool forceUnitLatencies() const { return false; } 173 174 private: 175 /// ClusterNeighboringLoads - Cluster loads from "near" addresses into 176 /// combined SUnits. 177 void ClusterNeighboringLoads(SDNode *Node); 178 /// ClusterNodes - Cluster certain nodes which should be scheduled together. 179 /// 180 void ClusterNodes(); 181 182 /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 183 void BuildSchedUnits(); 184 void AddSchedEdges(); 185 186 void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, 187 MachineBasicBlock::iterator InsertPos); 188 }; 189 190 } // end namespace llvm 191 192 #endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H 193