ScheduleDAGSDNodes.h revision 302ef834e0a2fd03e4b435079a9fa6c1e1cdc23b
1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson//===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===// 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert// 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// The LLVM Compiler Infrastructure 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// This file is distributed under the University of Illinois Open Source 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// License. See LICENSE.TXT for details. 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson//===----------------------------------------------------------------------===// 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// This file implements the ScheduleDAGSDNodes class, which implements 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// scheduling for an SDNode-based dependency graph. 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson// 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson//===----------------------------------------------------------------------===// 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson#ifndef SCHEDULEDAGSDNODES_H 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson#define SCHEDULEDAGSDNODES_H 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson#include "llvm/CodeGen/ScheduleDAG.h" 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson#include "llvm/CodeGen/SelectionDAG.h" 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonnamespace llvm { 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs. 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// Edges between SUnits are initially based on edges in the SelectionDAG, 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// and additional edges can be added by the schedulers as heuristics. 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// SDNodes such as Constants, Registers, and a few others that are not 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// interesting to schedulers are not allocated SUnits. 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// SDNodes with MVT::Flag operands are grouped along with the flagged 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// nodes into a single SUnit so that they are scheduled together. 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// edges. Physical register dependence information is not carried in 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// the DAG and must be handled explicitly by schedulers. 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson class ScheduleDAGSDNodes : public ScheduleDAG { 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public: 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SelectionDAG *DAG; // DAG of the current basic block 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson explicit ScheduleDAGSDNodes(MachineFunction &mf); 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson virtual ~ScheduleDAGSDNodes() {} 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// Run - perform scheduling. 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson void Run(SelectionDAG *dag, MachineBasicBlock *bb, 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson MachineBasicBlock::iterator insertPos); 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// isPassiveNode - Return true if the node is a non-scheduled leaf. 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson static bool isPassiveNode(SDNode *Node) { 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (isa<ConstantSDNode>(Node)) return true; 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<ConstantFPSDNode>(Node)) return true; 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<RegisterSDNode>(Node)) return true; 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<GlobalAddressSDNode>(Node)) return true; 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<BasicBlockSDNode>(Node)) return true; 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<FrameIndexSDNode>(Node)) return true; 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<ConstantPoolSDNode>(Node)) return true; 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<JumpTableSDNode>(Node)) return true; 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<ExternalSymbolSDNode>(Node)) return true; 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (isa<BlockAddressSDNode>(Node)) return true; 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (Node->getOpcode() == ISD::EntryToken || 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson isa<MDNodeSDNode>(Node)) return true; 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// NewSUnit - Creates a new SUnit and return a ptr to it. 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SUnit *NewSUnit(SDNode *N); 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// Clone - Creates a clone of the specified SUnit. It does not copy the 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// predecessors / successors info nor the temporary scheduling states. 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SUnit *Clone(SUnit *N); 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// are input. This SUnit graph is similar to the SelectionDAG, but 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// excludes nodes that aren't interesting to scheduling, and represents 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// flagged together nodes with a single SUnit. 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson virtual void BuildSchedGraph(AliasAnalysis *AA); 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// ComputeLatency - Compute node latency. 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson virtual void ComputeLatency(SUnit *SU); 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// ComputeOperandLatency - Override dependence edge latency using 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// operand use/def information 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /// 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use, 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SDep& dep) const { } 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert virtual void ComputeOperandLatency(SDNode *Def, SDNode *Use, 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert unsigned OpIdx, SDep& dep) const; 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert virtual MachineBasicBlock *EmitSchedule(); 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// Schedule - Order nodes according to selected style, filling 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// in the Sequence member. 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert virtual void Schedule() = 0; 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert virtual void dumpNode(const SUnit *SU) const; 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert virtual std::string getGraphNodeLabel(const SUnit *SU) const; 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private: 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// ClusterNeighboringLoads - Cluster loads from "near" addresses into 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// combined SUnits. 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert void ClusterNeighboringLoads(SDNode *Node); 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// ClusterNodes - Cluster certain nodes which should be scheduled together. 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert void ClusterNodes(); 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert void BuildSchedUnits(); 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson void AddSchedEdges(); 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert#endif 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson