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