ScheduleDAGSDNodes.h revision 77b4b13c2a525faf646a6784b24692cf0459b75e
184fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman//===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===// 2343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 3343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// The LLVM Compiler Infrastructure 4343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 5343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file is distributed under the University of Illinois Open Source 6343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// License. See LICENSE.TXT for details. 7343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 8343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 9343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 10343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file implements the ScheduleDAGSDNodes class, which implements 11343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// scheduling for an SDNode-based dependency graph. 12343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 13343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 14343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 1584fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman#ifndef SCHEDULEDAGSDNODES_H 1684fbac580941548a6ab1121ed3b0ffdc4e2bc080Dan Gohman#define SCHEDULEDAGSDNODES_H 17343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 18343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/ScheduleDAG.h" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/SelectionDAG.h" 20343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 21343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmannamespace llvm { 22983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs. 2392e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// 24983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// Edges between SUnits are initially based on edges in the SelectionDAG, 25983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// and additional edges can be added by the schedulers as heuristics. 26983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// SDNodes such as Constants, Registers, and a few others that are not 27983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// interesting to schedulers are not allocated SUnits. 28983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// 29f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner /// SDNodes with MVT::Glue operands are grouped along with the flagged 30983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// nodes into a single SUnit so that they are scheduled together. 31983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// 32983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output 33983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// edges. Physical register dependence information is not carried in 34983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// the DAG and must be handled explicitly by schedulers. 35983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// 36343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman class ScheduleDAGSDNodes : public ScheduleDAG { 37343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman public: 3847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman SelectionDAG *DAG; // DAG of the current basic block 393ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng const InstrItineraryData *InstrItins; 4047ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 4179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAGSDNodes(MachineFunction &mf); 42343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 43343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAGSDNodes() {} 44343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 4547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman /// Run - perform scheduling. 4647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman /// 4747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman void Run(SelectionDAG *dag, MachineBasicBlock *bb, 4847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman MachineBasicBlock::iterator insertPos); 4947ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 50343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// isPassiveNode - Return true if the node is a non-scheduled leaf. 51343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 52343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static bool isPassiveNode(SDNode *Node) { 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantSDNode>(Node)) return true; 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantFPSDNode>(Node)) return true; 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<RegisterSDNode>(Node)) return true; 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<GlobalAddressSDNode>(Node)) return true; 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<BasicBlockSDNode>(Node)) return true; 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<FrameIndexSDNode>(Node)) return true; 59343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantPoolSDNode>(Node)) return true; 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<JumpTableSDNode>(Node)) return true; 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ExternalSymbolSDNode>(Node)) return true; 628c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman if (isa<BlockAddressSDNode>(Node)) return true; 63decc2671516e6c52ee2f29f7746f8d02753845eaChris Lattner if (Node->getOpcode() == ISD::EntryToken || 64decc2671516e6c52ee2f29f7746f8d02753845eaChris Lattner isa<MDNodeSDNode>(Node)) return true; 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return false; 66343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 67343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 68343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// NewSUnit - Creates a new SUnit and return a ptr to it. 69343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 701cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SUnit *NewSUnit(SDNode *N); 71343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 72343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// Clone - Creates a clone of the specified SUnit. It does not copy the 73343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// predecessors / successors info nor the temporary scheduling states. 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 75343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *Clone(SUnit *N); 7692e946630d5f9bb092853b93501387dd216899b9Andrew Trick 77c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 78c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// are input. This SUnit graph is similar to the SelectionDAG, but 79c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// excludes nodes that aren't interesting to scheduling, and represents 80c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// flagged together nodes with a single SUnit. 8198976e4dcd18adbbe676048c0069e67346eb4adeDan Gohman virtual void BuildSchedGraph(AliasAnalysis *AA); 82343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 8354699765064842fd08d1466adc93453660bc2a85Andrew Trick /// InitVRegCycleFlag - Set isVRegCycle if this node's single use is 8454699765064842fd08d1466adc93453660bc2a85Andrew Trick /// CopyToReg and its only active data operands are CopyFromReg within a 8554699765064842fd08d1466adc93453660bc2a85Andrew Trick /// single block loop. 8654699765064842fd08d1466adc93453660bc2a85Andrew Trick /// 8754699765064842fd08d1466adc93453660bc2a85Andrew Trick void InitVRegCycleFlag(SUnit *SU); 8854699765064842fd08d1466adc93453660bc2a85Andrew Trick 8992e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// InitNumRegDefsLeft - Determine the # of regs defined by this node. 9092e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// 9192e946630d5f9bb092853b93501387dd216899b9Andrew Trick void InitNumRegDefsLeft(SUnit *SU); 9292e946630d5f9bb092853b93501387dd216899b9Andrew Trick 93343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// ComputeLatency - Compute node latency. 94343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 95343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void ComputeLatency(SUnit *SU); 96343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 9715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng /// ComputeOperandLatency - Override dependence edge latency using 9815a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng /// operand use/def information 9915a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng /// 10015a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng virtual void ComputeOperandLatency(SUnit *Def, SUnit *Use, 10115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng SDep& dep) const { } 10215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 10315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng virtual void ComputeOperandLatency(SDNode *Def, SDNode *Use, 10415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned OpIdx, SDep& dep) const; 10515a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 106af1d8ca44a18f304f207e209b3bdb94b590f86ffDan Gohman virtual MachineBasicBlock *EmitSchedule(); 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// Schedule - Order nodes according to selected style, filling 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// in the Sequence member. 110343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void Schedule() = 0; 112343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 113343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void dumpNode(const SUnit *SU) const; 114343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 115343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual std::string getGraphNodeLabel(const SUnit *SU) const; 116343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 117343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 118343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 11992e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// RegDefIter - In place iteration over the values defined by an 12092e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// SUnit. This does not need copies of the iterator or any other STLisms. 12192e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// The iterator creates itself, rather than being provided by the SchedDAG. 12292e946630d5f9bb092853b93501387dd216899b9Andrew Trick class RegDefIter { 12392e946630d5f9bb092853b93501387dd216899b9Andrew Trick const ScheduleDAGSDNodes *SchedDAG; 12492e946630d5f9bb092853b93501387dd216899b9Andrew Trick const SDNode *Node; 12592e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned DefIdx; 12692e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned NodeNumDefs; 12792e946630d5f9bb092853b93501387dd216899b9Andrew Trick EVT ValueType; 12892e946630d5f9bb092853b93501387dd216899b9Andrew Trick public: 12992e946630d5f9bb092853b93501387dd216899b9Andrew Trick RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD); 13092e946630d5f9bb092853b93501387dd216899b9Andrew Trick 13192e946630d5f9bb092853b93501387dd216899b9Andrew Trick bool IsValid() const { return Node != NULL; } 13292e946630d5f9bb092853b93501387dd216899b9Andrew Trick 13392e946630d5f9bb092853b93501387dd216899b9Andrew Trick EVT GetValue() const { 13492e946630d5f9bb092853b93501387dd216899b9Andrew Trick assert(IsValid() && "bad iterator"); 13592e946630d5f9bb092853b93501387dd216899b9Andrew Trick return ValueType; 13692e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 13792e946630d5f9bb092853b93501387dd216899b9Andrew Trick 13877b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson const SDNode *GetNode() const { 13977b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson return Node; 14077b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson } 14177b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson 14277b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson unsigned GetIdx() const { 14377b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson return DefIdx; 14477b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson } 14577b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson 14692e946630d5f9bb092853b93501387dd216899b9Andrew Trick void Advance(); 14792e946630d5f9bb092853b93501387dd216899b9Andrew Trick private: 14892e946630d5f9bb092853b93501387dd216899b9Andrew Trick void InitNodeNumDefs(); 14992e946630d5f9bb092853b93501387dd216899b9Andrew Trick }; 15092e946630d5f9bb092853b93501387dd216899b9Andrew Trick 151343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman private: 152c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng /// ClusterNeighboringLoads - Cluster loads from "near" addresses into 153c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng /// combined SUnits. 154302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng void ClusterNeighboringLoads(SDNode *Node); 155302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng /// ClusterNodes - Cluster certain nodes which should be scheduled together. 156302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng /// 157302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng void ClusterNodes(); 158c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 159c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 160c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman void BuildSchedUnits(); 161c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman void AddSchedEdges(); 162343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman }; 163343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 164343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 165343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#endif 166