ScheduleDAGSDNodes.h revision 47ac0f0c7c39289f5970688154e385be22b7f293
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: 3847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman SelectionDAG *DAG; // DAG of the current basic block 3947ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 4079ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAGSDNodes(MachineFunction &mf); 41343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 42343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAGSDNodes() {} 43343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 4447ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman /// Run - perform scheduling. 4547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman /// 4647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman void Run(SelectionDAG *dag, MachineBasicBlock *bb, 4747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman MachineBasicBlock::iterator insertPos); 4847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// isPassiveNode - Return true if the node is a non-scheduled leaf. 50343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 51343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static bool isPassiveNode(SDNode *Node) { 52343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantSDNode>(Node)) return true; 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantFPSDNode>(Node)) return true; 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<RegisterSDNode>(Node)) return true; 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<GlobalAddressSDNode>(Node)) return true; 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<BasicBlockSDNode>(Node)) return true; 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<FrameIndexSDNode>(Node)) return true; 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantPoolSDNode>(Node)) return true; 59343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<JumpTableSDNode>(Node)) return true; 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ExternalSymbolSDNode>(Node)) return true; 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<MemOperandSDNode>(Node)) return true; 62343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Node->getOpcode() == ISD::EntryToken) return true; 63343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return false; 64343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 66343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// NewSUnit - Creates a new SUnit and return a ptr to it. 67343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 68343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *NewSUnit(SDNode *N) { 69983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman#ifndef NDEBUG 70d5b207baabf18c03656387aeac87e62b5bb3c12bBill Wendling const SUnit *Addr = 0; 715f7c41c9d091ad3ac9d0f5ebcf1ef9acd98e4e64Dan Gohman if (!SUnits.empty()) 72d5b207baabf18c03656387aeac87e62b5bb3c12bBill Wendling Addr = &SUnits[0]; 73983bbbaf361bed826e650e3615c008195782c8f9Dan Gohman#endif 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 75d5b207baabf18c03656387aeac87e62b5bb3c12bBill Wendling assert((Addr == 0 || Addr == &SUnits[0]) && 76d5b207baabf18c03656387aeac87e62b5bb3c12bBill Wendling "SUnits std::vector reallocated on the fly!"); 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnits.back().OrigNode = &SUnits.back(); 78343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return &SUnits.back(); 79343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 80343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 81343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// Clone - Creates a clone of the specified SUnit. It does not copy the 82343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// predecessors / successors info nor the temporary scheduling states. 83343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 84343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *Clone(SUnit *N); 85343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 86c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 87c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// are input. This SUnit graph is similar to the SelectionDAG, but 88c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// excludes nodes that aren't interesting to scheduling, and represents 89c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// flagged together nodes with a single SUnit. 90c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman virtual void BuildSchedGraph(); 91343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 92343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// ComputeLatency - Compute node latency. 93343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 94343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void ComputeLatency(SUnit *SU); 95343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 96343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// CountResults - The results of target nodes have register or immediate 97343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// operands first, then an optional chain, and optional flag operands 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// (which do not go into the machine instrs.) 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static unsigned CountResults(SDNode *Node); 100343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 101343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// CountOperands - The inputs to target nodes have any actual inputs first, 102343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// followed by special operands that describe memory references, then an 103343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// optional chain operand, then flag operands. Compute the number of 104343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// actual operands that will go into the resulting MachineInstr. 105343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static unsigned CountOperands(SDNode *Node); 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// ComputeMemOperandsEnd - Find the index one past the last 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// MemOperandSDNode operand 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static unsigned ComputeMemOperandsEnd(SDNode *Node); 110343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// EmitNode - Generate machine code for an node and needed dependencies. 112343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// VRBaseMap contains, for each already emitted node, the first virtual 113343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// register number for the results of the node. 114343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 115e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng void EmitNode(SDNode *Node, bool IsClone, bool HasClone, 116343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 117343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 118343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual MachineBasicBlock *EmitSchedule(); 119343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 120343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// Schedule - Order nodes according to selected style, filling 121343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// in the Sequence member. 122343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 123343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void Schedule() = 0; 124343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void dumpNode(const SUnit *SU) const; 126343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 127343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual std::string getGraphNodeLabel(const SUnit *SU) const; 128343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 129343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 130343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 131343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman private: 132343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// EmitSubregNode - Generate machine code for subreg nodes. 133343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 134343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman void EmitSubregNode(SDNode *Node, 135343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 136343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 137343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// getVR - Return the virtual register corresponding to the specified result 138343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// of the specified node. 139343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned getVR(SDValue Op, DenseMap<SDValue, unsigned> &VRBaseMap); 140343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 141343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// getDstOfCopyToRegUse - If the only use of the specified result number of 142343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// node is a CopyToReg, return its destination register. Return 0 otherwise. 143343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const; 144343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 145343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum, 146343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetInstrDesc *II, 147343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 148343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 149343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an 150343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// implicit physical register output. 151343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, 152e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng bool IsCloned, unsigned SrcReg, 153343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 154343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 155343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, 1565c3c5a4d9c21e73f7a0e11d77a85997c9f34f2baEvan Cheng const TargetInstrDesc &II, bool IsClone, 157e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng bool IsCloned, 158343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DenseMap<SDValue, unsigned> &VRBaseMap); 159c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman 160c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 161c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman void BuildSchedUnits(); 162c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman void AddSchedEdges(); 163343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman }; 164343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 165343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 166343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#endif 167