1 //===---- llvm/CodeGen/ScheduleDAGSDNodes.h - SDNode Scheduling -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the ScheduleDAGSDNodes class, which implements
11 // scheduling for an SDNode-based dependency graph.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_SCHEDULEDAGSDNODES_H
16 #define LLVM_CODEGEN_SCHEDULEDAGSDNODES_H
18 #include "llvm/CodeGen/ScheduleDAG.h"
19 #include "llvm/CodeGen/SelectionDAG.h"
22 /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
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.
29 /// SDNodes with MVT::Flag operands are grouped along with the flagged
30 /// nodes into a single SUnit so that they are scheduled together.
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.
36 class ScheduleDAGSDNodes : public ScheduleDAG {
38 explicit ScheduleDAGSDNodes(MachineFunction &mf);
40 virtual ~ScheduleDAGSDNodes() {}
42 /// isPassiveNode - Return true if the node is a non-scheduled leaf.
44 static bool isPassiveNode(SDNode *Node) {
45 if (isa<ConstantSDNode>(Node)) return true;
46 if (isa<ConstantFPSDNode>(Node)) return true;
47 if (isa<RegisterSDNode>(Node)) return true;
48 if (isa<GlobalAddressSDNode>(Node)) return true;
49 if (isa<BasicBlockSDNode>(Node)) return true;
50 if (isa<FrameIndexSDNode>(Node)) return true;
51 if (isa<ConstantPoolSDNode>(Node)) return true;
52 if (isa<JumpTableSDNode>(Node)) return true;
53 if (isa<ExternalSymbolSDNode>(Node)) return true;
54 if (isa<MemOperandSDNode>(Node)) return true;
55 if (Node->getOpcode() == ISD::EntryToken) return true;
59 /// NewSUnit - Creates a new SUnit and return a ptr to it.
61 SUnit *NewSUnit(SDNode *N) {
63 const SUnit *Addr = 0;
64 if (SUnits.size() > 0)
67 SUnits.push_back(SUnit(N, (unsigned)SUnits.size()));
68 assert((Addr == 0 || Addr == &SUnits[0]) &&
69 "SUnits std::vector reallocated on the fly!");
70 SUnits.back().OrigNode = &SUnits.back();
71 return &SUnits.back();
74 /// Clone - Creates a clone of the specified SUnit. It does not copy the
75 /// predecessors / successors info nor the temporary scheduling states.
77 SUnit *Clone(SUnit *N);
79 virtual SelectionDAG *getDAG() { return DAG; }
81 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
82 /// are input. This SUnit graph is similar to the SelectionDAG, but
83 /// excludes nodes that aren't interesting to scheduling, and represents
84 /// flagged together nodes with a single SUnit.
85 virtual void BuildSchedGraph();
87 /// ComputeLatency - Compute node latency.
89 virtual void ComputeLatency(SUnit *SU);
91 /// CountResults - The results of target nodes have register or immediate
92 /// operands first, then an optional chain, and optional flag operands
93 /// (which do not go into the machine instrs.)
94 static unsigned CountResults(SDNode *Node);
96 /// CountOperands - The inputs to target nodes have any actual inputs first,
97 /// followed by special operands that describe memory references, then an
98 /// optional chain operand, then flag operands. Compute the number of
99 /// actual operands that will go into the resulting MachineInstr.
100 static unsigned CountOperands(SDNode *Node);
102 /// ComputeMemOperandsEnd - Find the index one past the last
103 /// MemOperandSDNode operand
104 static unsigned ComputeMemOperandsEnd(SDNode *Node);
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.
110 void EmitNode(SDNode *Node, bool IsClone, bool HasClone,
111 DenseMap<SDValue, unsigned> &VRBaseMap);
113 virtual MachineBasicBlock *EmitSchedule();
115 /// Schedule - Order nodes according to selected style, filling
116 /// in the Sequence member.
118 virtual void Schedule() = 0;
120 virtual void dumpNode(const SUnit *SU) const;
122 virtual std::string getGraphNodeLabel(const SUnit *SU) const;
124 virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const;
127 /// EmitSubregNode - Generate machine code for subreg nodes.
129 void EmitSubregNode(SDNode *Node,
130 DenseMap<SDValue, unsigned> &VRBaseMap);
132 /// getVR - Return the virtual register corresponding to the specified result
133 /// of the specified node.
134 unsigned getVR(SDValue Op, DenseMap<SDValue, unsigned> &VRBaseMap);
136 /// getDstOfCopyToRegUse - If the only use of the specified result number of
137 /// node is a CopyToReg, return its destination register. Return 0 otherwise.
138 unsigned getDstOfOnlyCopyToRegUse(SDNode *Node, unsigned ResNo) const;
140 void AddOperand(MachineInstr *MI, SDValue Op, unsigned IIOpNum,
141 const TargetInstrDesc *II,
142 DenseMap<SDValue, unsigned> &VRBaseMap);
144 /// EmitCopyFromReg - Generate machine code for an CopyFromReg node or an
145 /// implicit physical register output.
146 void EmitCopyFromReg(SDNode *Node, unsigned ResNo, bool IsClone,
147 bool IsCloned, unsigned SrcReg,
148 DenseMap<SDValue, unsigned> &VRBaseMap);
150 void CreateVirtualRegisters(SDNode *Node, MachineInstr *MI,
151 const TargetInstrDesc &II, bool IsClone,
153 DenseMap<SDValue, unsigned> &VRBaseMap);
155 /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph.
156 void BuildSchedUnits();
157 void AddSchedEdges();