ScheduleDAGSDNodes.h revision 84fbac580941548a6ab1121ed3b0ffdc4e2bc080
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. 23983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// 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 /// 29983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman /// SDNodes with MVT::Flag 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: 3879ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAGSDNodes(MachineFunction &mf); 39343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 40343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAGSDNodes() {} 41343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 42343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// isPassiveNode - Return true if the node is a non-scheduled leaf. 43343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 44343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static bool isPassiveNode(SDNode *Node) { 45343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantSDNode>(Node)) return true; 46343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantFPSDNode>(Node)) return true; 47343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<RegisterSDNode>(Node)) return true; 48343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<GlobalAddressSDNode>(Node)) return true; 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<BasicBlockSDNode>(Node)) return true; 50343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<FrameIndexSDNode>(Node)) return true; 51343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantPoolSDNode>(Node)) return true; 52343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<JumpTableSDNode>(Node)) return true; 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ExternalSymbolSDNode>(Node)) return true; 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<MemOperandSDNode>(Node)) return true; 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Node->getOpcode() == ISD::EntryToken) return true; 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return false; 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 59343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// NewSUnit - Creates a new SUnit and return a ptr to it. 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *NewSUnit(SDNode *N) { 62983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman#ifndef NDEBUG 63d5b207baabf18c03656387aeac87e62b5bb3c12bBill Wendling const SUnit *Addr = 0; 645f7c41c9d091ad3ac9d0f5ebcf1ef9acd98e4e64Dan Gohman if (!SUnits.empty()) 65d5b207baabf18c03656387aeac87e62b5bb3c12bBill Wendling Addr = &SUnits[0]; 66983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman#endif 67343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 68d5b207baabf18c03656387aeac87e62b5bb3c12bBill Wendling assert((Addr == 0 || Addr == &SUnits[0]) && 69d5b207baabf18c03656387aeac87e62b5bb3c12bBill Wendling "SUnits std::vector reallocated on the fly!"); 70343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnits.back().OrigNode = &SUnits.back(); 71343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return &SUnits.back(); 72343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 73343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// Clone - Creates a clone of the specified SUnit. It does not copy the 75343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// predecessors / successors info nor the temporary scheduling states. 76343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *Clone(SUnit *N); 78343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 79343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual SelectionDAG *getDAG() { return DAG; } 80343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 81c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 82c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// are input. This SUnit graph is similar to the SelectionDAG, but 83c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// excludes nodes that aren't interesting to scheduling, and represents 84c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// flagged together nodes with a single SUnit. 85c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman virtual void BuildSchedGraph(); 86343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 87343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// ComputeLatency - Compute node latency. 88343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 89343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void ComputeLatency(SUnit *SU); 90343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 91343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// CountResults - The results of target nodes have register or immediate 92343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// operands first, then an optional chain, and optional flag operands 93343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// (which do not go into the machine instrs.) 94343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static unsigned CountResults(SDNode *Node); 95343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 96343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// CountOperands - The inputs to target nodes have any actual inputs first, 97343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// followed by special operands that describe memory references, then an 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// optional chain operand, then flag operands. Compute the number of 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// actual operands that will go into the resulting MachineInstr. 100343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static unsigned CountOperands(SDNode *Node); 101343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 102343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// ComputeMemOperandsEnd - Find the index one past the last 103343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// MemOperandSDNode operand 104343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static unsigned ComputeMemOperandsEnd(SDNode *Node); 105343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// EmitNode - Generate machine code for an node and needed dependencies. 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// VRBaseMap contains, for each already emitted node, the first virtual 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// register number for the results of the node. 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 110e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng void EmitNode(SDNode *Node, bool IsClone, bool HasClone, 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 112343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 113343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual MachineBasicBlock *EmitSchedule(); 114343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 115343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// Schedule - Order nodes according to selected style, filling 116343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// in the Sequence member. 117343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 118343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void Schedule() = 0; 119343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 120343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void dumpNode(const SUnit *SU) const; 121343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 122343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual std::string getGraphNodeLabel(const SUnit *SU) const; 123343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 124343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 126343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman private: 127343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// EmitSubregNode - Generate machine code for subreg nodes. 128343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 129343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman void EmitSubregNode(SDNode *Node, 130343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 131343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 132343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// getVR - Return the virtual register corresponding to the specified result 133343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// of the specified node. 134343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned getVR(SDValue Op, DenseMap<SDValue, unsigned> &VRBaseMap); 135343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 136343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// getDstOfCopyToRegUse - If the only use of the specified result number of 137343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// node is a CopyToReg, return its destination register. Return 0 otherwise. 138343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const; 139343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 140343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum, 141343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc *II, 142343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 143343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 144343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an 145343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// implicit physical register output. 146343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, 147e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng bool IsCloned, unsigned SrcReg, 148343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 149343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 150343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, 1515c3c5a4d9c21e73f7a0e11d77a85997c9f34f2baEvan Cheng const TargetInstrDesc &II, bool IsClone, 152e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng bool IsCloned, 153343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 154c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 155c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 156c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman void BuildSchedUnits(); 157c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman void AddSchedEdges(); 158343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman }; 159343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 160343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 161343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#endif 162