lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.h

   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