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 15193323Sed#ifndef SCHEDULEDAGSDNODES_H 16193323Sed#define SCHEDULEDAGSDNODES_H 17193323Sed 18249423Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 19193323Sed#include "llvm/CodeGen/ScheduleDAG.h" 20193323Sed 21193323Sednamespace llvm { 22193323Sed /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs. 23218893Sdim /// 24193323Sed /// Edges between SUnits are initially based on edges in the SelectionDAG, 25193323Sed /// and additional edges can be added by the schedulers as heuristics. 26193323Sed /// SDNodes such as Constants, Registers, and a few others that are not 27193323Sed /// interesting to schedulers are not allocated SUnits. 28193323Sed /// 29218893Sdim /// SDNodes with MVT::Glue operands are grouped along with the flagged 30193323Sed /// nodes into a single SUnit so that they are scheduled together. 31193323Sed /// 32193323Sed /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output 33193323Sed /// edges. Physical register dependence information is not carried in 34193323Sed /// the DAG and must be handled explicitly by schedulers. 35193323Sed /// 36193323Sed class ScheduleDAGSDNodes : public ScheduleDAG { 37193323Sed public: 38234353Sdim MachineBasicBlock *BB; 39193323Sed SelectionDAG *DAG; // DAG of the current basic block 40218893Sdim const InstrItineraryData *InstrItins; 41193323Sed 42234353Sdim /// The schedule. Null SUnit*'s represent noop instructions. 43234353Sdim std::vector<SUnit*> Sequence; 44234353Sdim 45193323Sed explicit ScheduleDAGSDNodes(MachineFunction &mf); 46193323Sed 47193323Sed virtual ~ScheduleDAGSDNodes() {} 48193323Sed 49193323Sed /// Run - perform scheduling. 50193323Sed /// 51234353Sdim void Run(SelectionDAG *dag, MachineBasicBlock *bb); 52193323Sed 53193323Sed /// isPassiveNode - Return true if the node is a non-scheduled leaf. 54193323Sed /// 55193323Sed static bool isPassiveNode(SDNode *Node) { 56193323Sed if (isa<ConstantSDNode>(Node)) return true; 57193323Sed if (isa<ConstantFPSDNode>(Node)) return true; 58193323Sed if (isa<RegisterSDNode>(Node)) return true; 59234353Sdim if (isa<RegisterMaskSDNode>(Node)) return true; 60193323Sed if (isa<GlobalAddressSDNode>(Node)) return true; 61193323Sed if (isa<BasicBlockSDNode>(Node)) return true; 62193323Sed if (isa<FrameIndexSDNode>(Node)) return true; 63193323Sed if (isa<ConstantPoolSDNode>(Node)) return true; 64239462Sdim if (isa<TargetIndexSDNode>(Node)) return true; 65193323Sed if (isa<JumpTableSDNode>(Node)) return true; 66193323Sed if (isa<ExternalSymbolSDNode>(Node)) return true; 67198892Srdivacky if (isa<BlockAddressSDNode>(Node)) return true; 68207618Srdivacky if (Node->getOpcode() == ISD::EntryToken || 69207618Srdivacky isa<MDNodeSDNode>(Node)) return true; 70193323Sed return false; 71193323Sed } 72193323Sed 73193323Sed /// NewSUnit - Creates a new SUnit and return a ptr to it. 74193323Sed /// 75234353Sdim SUnit *newSUnit(SDNode *N); 76193323Sed 77193323Sed /// Clone - Creates a clone of the specified SUnit. It does not copy the 78193323Sed /// predecessors / successors info nor the temporary scheduling states. 79193323Sed /// 80193323Sed SUnit *Clone(SUnit *N); 81218893Sdim 82193323Sed /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 83193323Sed /// are input. This SUnit graph is similar to the SelectionDAG, but 84193323Sed /// excludes nodes that aren't interesting to scheduling, and represents 85193323Sed /// flagged together nodes with a single SUnit. 86234353Sdim void BuildSchedGraph(AliasAnalysis *AA); 87193323Sed 88221345Sdim /// InitVRegCycleFlag - Set isVRegCycle if this node's single use is 89221345Sdim /// CopyToReg and its only active data operands are CopyFromReg within a 90221345Sdim /// single block loop. 91221345Sdim /// 92221345Sdim void InitVRegCycleFlag(SUnit *SU); 93221345Sdim 94218893Sdim /// InitNumRegDefsLeft - Determine the # of regs defined by this node. 95218893Sdim /// 96218893Sdim void InitNumRegDefsLeft(SUnit *SU); 97218893Sdim 98234353Sdim /// computeLatency - Compute node latency. 99193323Sed /// 100234353Sdim virtual void computeLatency(SUnit *SU); 101193323Sed 102234353Sdim virtual void computeOperandLatency(SDNode *Def, SDNode *Use, 103208599Srdivacky unsigned OpIdx, SDep& dep) const; 104208599Srdivacky 105193323Sed /// Schedule - Order nodes according to selected style, filling 106193323Sed /// in the Sequence member. 107193323Sed /// 108193323Sed virtual void Schedule() = 0; 109193323Sed 110234353Sdim /// VerifyScheduledSequence - Verify that all SUnits are scheduled and 111234353Sdim /// consistent with the Sequence of scheduled instructions. 112234353Sdim void VerifyScheduledSequence(bool isBottomUp); 113234353Sdim 114234353Sdim /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock 115234353Sdim /// according to the order specified in Sequence. 116234353Sdim /// 117243830Sdim virtual MachineBasicBlock* 118243830Sdim EmitSchedule(MachineBasicBlock::iterator &InsertPos); 119234353Sdim 120193323Sed virtual void dumpNode(const SUnit *SU) const; 121193323Sed 122234353Sdim void dumpSchedule() const; 123234353Sdim 124193323Sed virtual std::string getGraphNodeLabel(const SUnit *SU) const; 125193323Sed 126234353Sdim virtual std::string getDAGName() const; 127234353Sdim 128193323Sed virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 129193323Sed 130218893Sdim /// RegDefIter - In place iteration over the values defined by an 131218893Sdim /// SUnit. This does not need copies of the iterator or any other STLisms. 132218893Sdim /// The iterator creates itself, rather than being provided by the SchedDAG. 133218893Sdim class RegDefIter { 134218893Sdim const ScheduleDAGSDNodes *SchedDAG; 135218893Sdim const SDNode *Node; 136218893Sdim unsigned DefIdx; 137218893Sdim unsigned NodeNumDefs; 138249423Sdim MVT ValueType; 139218893Sdim public: 140218893Sdim RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD); 141218893Sdim 142218893Sdim bool IsValid() const { return Node != NULL; } 143218893Sdim 144249423Sdim MVT GetValue() const { 145218893Sdim assert(IsValid() && "bad iterator"); 146218893Sdim return ValueType; 147218893Sdim } 148218893Sdim 149224145Sdim const SDNode *GetNode() const { 150224145Sdim return Node; 151224145Sdim } 152224145Sdim 153224145Sdim unsigned GetIdx() const { 154224145Sdim return DefIdx-1; 155224145Sdim } 156224145Sdim 157218893Sdim void Advance(); 158218893Sdim private: 159218893Sdim void InitNodeNumDefs(); 160218893Sdim }; 161218893Sdim 162243830Sdim protected: 163243830Sdim /// ForceUnitLatencies - Return true if all scheduling edges should be given 164243830Sdim /// a latency value of one. The default is to return false; schedulers may 165243830Sdim /// override this as needed. 166243830Sdim virtual bool forceUnitLatencies() const { return false; } 167243830Sdim 168193323Sed private: 169202878Srdivacky /// ClusterNeighboringLoads - Cluster loads from "near" addresses into 170202878Srdivacky /// combined SUnits. 171210299Sed void ClusterNeighboringLoads(SDNode *Node); 172210299Sed /// ClusterNodes - Cluster certain nodes which should be scheduled together. 173210299Sed /// 174210299Sed void ClusterNodes(); 175202878Srdivacky 176193323Sed /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 177193323Sed void BuildSchedUnits(); 178193323Sed void AddSchedEdges(); 179234353Sdim 180234353Sdim void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, 181234353Sdim MachineBasicBlock::iterator InsertPos); 182193323Sed }; 183193323Sed} 184193323Sed 185193323Sed#endif 186