ScheduleDAGSDNodes.h revision 344779
1193323Sed//===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the ScheduleDAGSDNodes class, which implements 11193323Sed// scheduling for an SDNode-based dependency graph. 12193323Sed// 13193323Sed//===----------------------------------------------------------------------===// 14193323Sed 15280031Sdim#ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H 16280031Sdim#define LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H 17193323Sed 18314564Sdim#include "llvm/CodeGen/ISDOpcodes.h" 19249423Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 20193323Sed#include "llvm/CodeGen/ScheduleDAG.h" 21314564Sdim#include "llvm/CodeGen/SelectionDAGNodes.h" 22314564Sdim#include "llvm/Support/Casting.h" 23341825Sdim#include "llvm/Support/MachineValueType.h" 24314564Sdim#include <cassert> 25314564Sdim#include <string> 26314564Sdim#include <vector> 27193323Sed 28193323Sednamespace llvm { 29314564Sdim 30314564Sdimclass InstrItineraryData; 31314564Sdim 32193323Sed /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs. 33218893Sdim /// 34193323Sed /// Edges between SUnits are initially based on edges in the SelectionDAG, 35193323Sed /// and additional edges can be added by the schedulers as heuristics. 36193323Sed /// SDNodes such as Constants, Registers, and a few others that are not 37193323Sed /// interesting to schedulers are not allocated SUnits. 38193323Sed /// 39218893Sdim /// SDNodes with MVT::Glue operands are grouped along with the flagged 40193323Sed /// nodes into a single SUnit so that they are scheduled together. 41193323Sed /// 42193323Sed /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output 43193323Sed /// edges. Physical register dependence information is not carried in 44193323Sed /// the DAG and must be handled explicitly by schedulers. 45193323Sed /// 46193323Sed class ScheduleDAGSDNodes : public ScheduleDAG { 47193323Sed public: 48234353Sdim MachineBasicBlock *BB; 49193323Sed SelectionDAG *DAG; // DAG of the current basic block 50218893Sdim const InstrItineraryData *InstrItins; 51193323Sed 52234353Sdim /// The schedule. Null SUnit*'s represent noop instructions. 53234353Sdim std::vector<SUnit*> Sequence; 54234353Sdim 55193323Sed explicit ScheduleDAGSDNodes(MachineFunction &mf); 56193323Sed 57314564Sdim ~ScheduleDAGSDNodes() override = default; 58193323Sed 59193323Sed /// Run - perform scheduling. 60193323Sed /// 61234353Sdim void Run(SelectionDAG *dag, MachineBasicBlock *bb); 62193323Sed 63193323Sed /// isPassiveNode - Return true if the node is a non-scheduled leaf. 64193323Sed /// 65193323Sed static bool isPassiveNode(SDNode *Node) { 66193323Sed if (isa<ConstantSDNode>(Node)) return true; 67193323Sed if (isa<ConstantFPSDNode>(Node)) return true; 68193323Sed if (isa<RegisterSDNode>(Node)) return true; 69234353Sdim if (isa<RegisterMaskSDNode>(Node)) return true; 70193323Sed if (isa<GlobalAddressSDNode>(Node)) return true; 71193323Sed if (isa<BasicBlockSDNode>(Node)) return true; 72193323Sed if (isa<FrameIndexSDNode>(Node)) return true; 73193323Sed if (isa<ConstantPoolSDNode>(Node)) return true; 74239462Sdim if (isa<TargetIndexSDNode>(Node)) return true; 75193323Sed if (isa<JumpTableSDNode>(Node)) return true; 76193323Sed if (isa<ExternalSymbolSDNode>(Node)) return true; 77288943Sdim if (isa<MCSymbolSDNode>(Node)) return true; 78198892Srdivacky if (isa<BlockAddressSDNode>(Node)) return true; 79207618Srdivacky if (Node->getOpcode() == ISD::EntryToken || 80207618Srdivacky isa<MDNodeSDNode>(Node)) return true; 81193323Sed return false; 82193323Sed } 83193323Sed 84193323Sed /// NewSUnit - Creates a new SUnit and return a ptr to it. 85193323Sed /// 86234353Sdim SUnit *newSUnit(SDNode *N); 87193323Sed 88193323Sed /// Clone - Creates a clone of the specified SUnit. It does not copy the 89193323Sed /// predecessors / successors info nor the temporary scheduling states. 90193323Sed /// 91341825Sdim SUnit *Clone(SUnit *Old); 92218893Sdim 93193323Sed /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 94193323Sed /// are input. This SUnit graph is similar to the SelectionDAG, but 95193323Sed /// excludes nodes that aren't interesting to scheduling, and represents 96193323Sed /// flagged together nodes with a single SUnit. 97234353Sdim void BuildSchedGraph(AliasAnalysis *AA); 98193323Sed 99218893Sdim /// InitNumRegDefsLeft - Determine the # of regs defined by this node. 100218893Sdim /// 101218893Sdim void InitNumRegDefsLeft(SUnit *SU); 102218893Sdim 103234353Sdim /// computeLatency - Compute node latency. 104193323Sed /// 105234353Sdim virtual void computeLatency(SUnit *SU); 106193323Sed 107234353Sdim virtual void computeOperandLatency(SDNode *Def, SDNode *Use, 108208599Srdivacky unsigned OpIdx, SDep& dep) const; 109208599Srdivacky 110193323Sed /// Schedule - Order nodes according to selected style, filling 111193323Sed /// in the Sequence member. 112193323Sed /// 113193323Sed virtual void Schedule() = 0; 114193323Sed 115234353Sdim /// VerifyScheduledSequence - Verify that all SUnits are scheduled and 116234353Sdim /// consistent with the Sequence of scheduled instructions. 117234353Sdim void VerifyScheduledSequence(bool isBottomUp); 118234353Sdim 119234353Sdim /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock 120234353Sdim /// according to the order specified in Sequence. 121234353Sdim /// 122243830Sdim virtual MachineBasicBlock* 123243830Sdim EmitSchedule(MachineBasicBlock::iterator &InsertPos); 124234353Sdim 125344779Sdim void dumpNode(const SUnit &SU) const override; 126344779Sdim void dump() const override; 127234353Sdim void dumpSchedule() const; 128234353Sdim 129276479Sdim std::string getGraphNodeLabel(const SUnit *SU) const override; 130193323Sed 131276479Sdim std::string getDAGName() const override; 132234353Sdim 133193323Sed virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 134193323Sed 135218893Sdim /// RegDefIter - In place iteration over the values defined by an 136218893Sdim /// SUnit. This does not need copies of the iterator or any other STLisms. 137218893Sdim /// The iterator creates itself, rather than being provided by the SchedDAG. 138218893Sdim class RegDefIter { 139218893Sdim const ScheduleDAGSDNodes *SchedDAG; 140218893Sdim const SDNode *Node; 141218893Sdim unsigned DefIdx; 142218893Sdim unsigned NodeNumDefs; 143249423Sdim MVT ValueType; 144314564Sdim 145218893Sdim public: 146218893Sdim RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD); 147218893Sdim 148276479Sdim bool IsValid() const { return Node != nullptr; } 149218893Sdim 150249423Sdim MVT GetValue() const { 151218893Sdim assert(IsValid() && "bad iterator"); 152218893Sdim return ValueType; 153218893Sdim } 154218893Sdim 155224145Sdim const SDNode *GetNode() const { 156224145Sdim return Node; 157224145Sdim } 158224145Sdim 159224145Sdim unsigned GetIdx() const { 160224145Sdim return DefIdx-1; 161224145Sdim } 162224145Sdim 163218893Sdim void Advance(); 164314564Sdim 165218893Sdim private: 166218893Sdim void InitNodeNumDefs(); 167218893Sdim }; 168218893Sdim 169243830Sdim protected: 170243830Sdim /// ForceUnitLatencies - Return true if all scheduling edges should be given 171243830Sdim /// a latency value of one. The default is to return false; schedulers may 172243830Sdim /// override this as needed. 173243830Sdim virtual bool forceUnitLatencies() const { return false; } 174243830Sdim 175193323Sed private: 176202878Srdivacky /// ClusterNeighboringLoads - Cluster loads from "near" addresses into 177202878Srdivacky /// combined SUnits. 178210299Sed void ClusterNeighboringLoads(SDNode *Node); 179210299Sed /// ClusterNodes - Cluster certain nodes which should be scheduled together. 180210299Sed /// 181210299Sed void ClusterNodes(); 182202878Srdivacky 183193323Sed /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 184193323Sed void BuildSchedUnits(); 185193323Sed void AddSchedEdges(); 186234353Sdim 187234353Sdim void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, 188234353Sdim MachineBasicBlock::iterator InsertPos); 189193323Sed }; 190193323Sed 191314564Sdim} // end namespace llvm 192314564Sdim 193314564Sdim#endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H 194