llvm/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/CodeGenTypes/MachineValueType.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,
 188                          SmallDenseMap<SUnit *, Register, 16> &VRBaseMap,
 189                          MachineBasicBlock::iterator InsertPos);
 190   };
 191
 192 } // end namespace llvm
 193
 194 #endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H