ScheduleDAGSDNodes.h revision c76909abfec876c6b751d693ebd3df07df686aa0
1//===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the ScheduleDAGSDNodes class, which implements 11// scheduling for an SDNode-based dependency graph. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef SCHEDULEDAGSDNODES_H 16#define SCHEDULEDAGSDNODES_H 17 18#include "llvm/CodeGen/ScheduleDAG.h" 19#include "llvm/CodeGen/SelectionDAG.h" 20 21namespace llvm { 22 /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs. 23 /// 24 /// Edges between SUnits are initially based on edges in the SelectionDAG, 25 /// and additional edges can be added by the schedulers as heuristics. 26 /// SDNodes such as Constants, Registers, and a few others that are not 27 /// interesting to schedulers are not allocated SUnits. 28 /// 29 /// SDNodes with MVT::Flag operands are grouped along with the flagged 30 /// nodes into a single SUnit so that they are scheduled together. 31 /// 32 /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output 33 /// edges. Physical register dependence information is not carried in 34 /// the DAG and must be handled explicitly by schedulers. 35 /// 36 class ScheduleDAGSDNodes : public ScheduleDAG { 37 public: 38 SelectionDAG *DAG; // DAG of the current basic block 39 40 explicit ScheduleDAGSDNodes(MachineFunction &mf); 41 42 virtual ~ScheduleDAGSDNodes() {} 43 44 /// Run - perform scheduling. 45 /// 46 void Run(SelectionDAG *dag, MachineBasicBlock *bb, 47 MachineBasicBlock::iterator insertPos); 48 49 /// isPassiveNode - Return true if the node is a non-scheduled leaf. 50 /// 51 static bool isPassiveNode(SDNode *Node) { 52 if (isa<ConstantSDNode>(Node)) return true; 53 if (isa<ConstantFPSDNode>(Node)) return true; 54 if (isa<RegisterSDNode>(Node)) return true; 55 if (isa<GlobalAddressSDNode>(Node)) return true; 56 if (isa<BasicBlockSDNode>(Node)) return true; 57 if (isa<FrameIndexSDNode>(Node)) return true; 58 if (isa<ConstantPoolSDNode>(Node)) return true; 59 if (isa<JumpTableSDNode>(Node)) return true; 60 if (isa<ExternalSymbolSDNode>(Node)) return true; 61 if (Node->getOpcode() == ISD::EntryToken) return true; 62 return false; 63 } 64 65 /// NewSUnit - Creates a new SUnit and return a ptr to it. 66 /// 67 SUnit *NewSUnit(SDNode *N) { 68#ifndef NDEBUG 69 const SUnit *Addr = 0; 70 if (!SUnits.empty()) 71 Addr = &SUnits[0]; 72#endif 73 SUnits.push_back(SUnit(N, (unsigned)SUnits.size())); 74 assert((Addr == 0 || Addr == &SUnits[0]) && 75 "SUnits std::vector reallocated on the fly!"); 76 SUnits.back().OrigNode = &SUnits.back(); 77 return &SUnits.back(); 78 } 79 80 /// Clone - Creates a clone of the specified SUnit. It does not copy the 81 /// predecessors / successors info nor the temporary scheduling states. 82 /// 83 SUnit *Clone(SUnit *N); 84 85 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 86 /// are input. This SUnit graph is similar to the SelectionDAG, but 87 /// excludes nodes that aren't interesting to scheduling, and represents 88 /// flagged together nodes with a single SUnit. 89 virtual void BuildSchedGraph(); 90 91 /// ComputeLatency - Compute node latency. 92 /// 93 virtual void ComputeLatency(SUnit *SU); 94 95 /// CountResults - The results of target nodes have register or immediate 96 /// operands first, then an optional chain, and optional flag operands 97 /// (which do not go into the machine instrs.) 98 static unsigned CountResults(SDNode *Node); 99 100 /// CountOperands - The inputs to target nodes have any actual inputs first, 101 /// followed by an optional chain operand, then flag operands. Compute 102 /// the number of actual operands that will go into the resulting 103 /// MachineInstr. 104 static unsigned CountOperands(SDNode *Node); 105 106 /// EmitNode - Generate machine code for an node and needed dependencies. 107 /// VRBaseMap contains, for each already emitted node, the first virtual 108 /// register number for the results of the node. 109 /// 110 void EmitNode(SDNode *Node, bool IsClone, bool HasClone, 111 DenseMap<SDValue, unsigned> &VRBaseMap, 112 DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM); 113 114 virtual MachineBasicBlock * 115 EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM); 116 117 /// Schedule - Order nodes according to selected style, filling 118 /// in the Sequence member. 119 /// 120 virtual void Schedule() = 0; 121 122 virtual void dumpNode(const SUnit *SU) const; 123 124 virtual std::string getGraphNodeLabel(const SUnit *SU) const; 125 126 virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 127 128 private: 129 /// EmitSubregNode - Generate machine code for subreg nodes. 130 /// 131 void EmitSubregNode(SDNode *Node, 132 DenseMap<SDValue, unsigned> &VRBaseMap); 133 134 /// EmitCopyToRegClassNode - Generate machine code for COPY_TO_REGCLASS 135 /// nodes. 136 /// 137 void EmitCopyToRegClassNode(SDNode *Node, 138 DenseMap<SDValue, unsigned> &VRBaseMap); 139 140 /// getVR - Return the virtual register corresponding to the specified result 141 /// of the specified node. 142 unsigned getVR(SDValue Op, DenseMap<SDValue, unsigned> &VRBaseMap); 143 144 /// getDstOfCopyToRegUse - If the only use of the specified result number of 145 /// node is a CopyToReg, return its destination register. Return 0 otherwise. 146 unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const; 147 148 void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum, 149 const TargetInstrDesc *II, 150 DenseMap<SDValue, unsigned> &VRBaseMap); 151 152 /// AddRegisterOperand - Add the specified register as an operand to the 153 /// specified machine instr. Insert register copies if the register is 154 /// not in the required register class. 155 void AddRegisterOperand(MachineInstr *MI, SDValue Op, 156 unsigned IIOpNum, const TargetInstrDesc *II, 157 DenseMap<SDValue, unsigned> &VRBaseMap); 158 159 /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an 160 /// implicit physical register output. 161 void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone, 162 bool IsCloned, unsigned SrcReg, 163 DenseMap<SDValue, unsigned> &VRBaseMap); 164 165 void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI, 166 const TargetInstrDesc &II, bool IsClone, 167 bool IsCloned, 168 DenseMap<SDValue, unsigned> &VRBaseMap); 169 170 /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 171 void BuildSchedUnits(); 172 void AddSchedEdges(); 173 }; 174} 175 176#endif 177