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 18751bc8d4c9ee4298449fed264571ffc162852e06Jakub Staszak#include "llvm/CodeGen/MachineBasicBlock.h" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/ScheduleDAG.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: 3847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick MachineBasicBlock *BB; 3947ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman SelectionDAG *DAG; // DAG of the current basic block 403ef1c8759a20167457eb7fd82ebcaffe7ccaa1d1Evan Cheng const InstrItineraryData *InstrItins; 4147ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 4247c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// The schedule. Null SUnit*'s represent noop instructions. 4347c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick std::vector<SUnit*> Sequence; 4447c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 4579ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAGSDNodes(MachineFunction &mf); 46343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 47343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAGSDNodes() {} 48343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 4947ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman /// Run - perform scheduling. 5047ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman /// 5147c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick void Run(SelectionDAG *dag, MachineBasicBlock *bb); 5247ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// isPassiveNode - Return true if the node is a non-scheduled leaf. 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman static bool isPassiveNode(SDNode *Node) { 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantSDNode>(Node)) return true; 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantFPSDNode>(Node)) return true; 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<RegisterSDNode>(Node)) return true; 599cf37e8b48732fccd4c301ed51aafed7074bd84eJakob Stoklund Olesen if (isa<RegisterMaskSDNode>(Node)) return true; 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<GlobalAddressSDNode>(Node)) return true; 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<BasicBlockSDNode>(Node)) return true; 62343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<FrameIndexSDNode>(Node)) return true; 63343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ConstantPoolSDNode>(Node)) return true; 6474500bdba3eae36a1a8a17d8bad0b971b9c212ecJakob Stoklund Olesen if (isa<TargetIndexSDNode>(Node)) return true; 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<JumpTableSDNode>(Node)) return true; 66343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (isa<ExternalSymbolSDNode>(Node)) return true; 678c2b52552c90f39e4b2fed43e309e599e742b6acDan Gohman if (isa<BlockAddressSDNode>(Node)) return true; 68decc2671516e6c52ee2f29f7746f8d02753845eaChris Lattner if (Node->getOpcode() == ISD::EntryToken || 69decc2671516e6c52ee2f29f7746f8d02753845eaChris Lattner isa<MDNodeSDNode>(Node)) return true; 70343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman return false; 71343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 72343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 73343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// NewSUnit - Creates a new SUnit and return a ptr to it. 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 75953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick SUnit *newSUnit(SDNode *N); 76343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// Clone - Creates a clone of the specified SUnit. It does not copy the 78343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// predecessors / successors info nor the temporary scheduling states. 79343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 80343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *Clone(SUnit *N); 8192e946630d5f9bb092853b93501387dd216899b9Andrew Trick 82c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// BuildSchedGraph - Build the SUnit graph from the selection dag that we 83c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// are input. This SUnit graph is similar to the SelectionDAG, but 84c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// excludes nodes that aren't interesting to scheduling, and represents 85c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// flagged together nodes with a single SUnit. 86084e179f090f9a47bdf66f49775a125f4a2a8a8cAndrew Trick void BuildSchedGraph(AliasAnalysis *AA); 87343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 8854699765064842fd08d1466adc93453660bc2a85Andrew Trick /// InitVRegCycleFlag - Set isVRegCycle if this node's single use is 8954699765064842fd08d1466adc93453660bc2a85Andrew Trick /// CopyToReg and its only active data operands are CopyFromReg within a 9054699765064842fd08d1466adc93453660bc2a85Andrew Trick /// single block loop. 9154699765064842fd08d1466adc93453660bc2a85Andrew Trick /// 9254699765064842fd08d1466adc93453660bc2a85Andrew Trick void InitVRegCycleFlag(SUnit *SU); 9354699765064842fd08d1466adc93453660bc2a85Andrew Trick 9492e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// InitNumRegDefsLeft - Determine the # of regs defined by this node. 9592e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// 9692e946630d5f9bb092853b93501387dd216899b9Andrew Trick void InitNumRegDefsLeft(SUnit *SU); 9792e946630d5f9bb092853b93501387dd216899b9Andrew Trick 98953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// computeLatency - Compute node latency. 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 100953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void computeLatency(SUnit *SU); 101343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 102953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void computeOperandLatency(SDNode *Def, SDNode *Use, 10315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned OpIdx, SDep& dep) const; 10415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 105343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// Schedule - Order nodes according to selected style, filling 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// in the Sequence member. 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void Schedule() = 0; 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 1104c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick /// VerifyScheduledSequence - Verify that all SUnits are scheduled and 1114c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick /// consistent with the Sequence of scheduled instructions. 1124c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick void VerifyScheduledSequence(bool isBottomUp); 1134c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick 11484b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock 11584b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick /// according to the order specified in Sequence. 11684b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick /// 117d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng virtual MachineBasicBlock* 118d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng EmitSchedule(MachineBasicBlock::iterator &InsertPos); 11984b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick 120343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void dumpNode(const SUnit *SU) const; 121343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 12273ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick void dumpSchedule() const; 12373ba69b6843f7f23345b1e8745cb328952cae0d8Andrew Trick 124343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual std::string getGraphNodeLabel(const SUnit *SU) const; 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 12656b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick virtual std::string getDAGName() const; 12756b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick 128343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const; 129343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 13092e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// RegDefIter - In place iteration over the values defined by an 13192e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// SUnit. This does not need copies of the iterator or any other STLisms. 13292e946630d5f9bb092853b93501387dd216899b9Andrew Trick /// The iterator creates itself, rather than being provided by the SchedDAG. 13392e946630d5f9bb092853b93501387dd216899b9Andrew Trick class RegDefIter { 13492e946630d5f9bb092853b93501387dd216899b9Andrew Trick const ScheduleDAGSDNodes *SchedDAG; 13592e946630d5f9bb092853b93501387dd216899b9Andrew Trick const SDNode *Node; 13692e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned DefIdx; 13792e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned NodeNumDefs; 138860e7cdab9d5eceda5ac52ae0ddfb4bdab0067f2Patrik Hagglund MVT ValueType; 13992e946630d5f9bb092853b93501387dd216899b9Andrew Trick public: 14092e946630d5f9bb092853b93501387dd216899b9Andrew Trick RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD); 14192e946630d5f9bb092853b93501387dd216899b9Andrew Trick 14292e946630d5f9bb092853b93501387dd216899b9Andrew Trick bool IsValid() const { return Node != NULL; } 14392e946630d5f9bb092853b93501387dd216899b9Andrew Trick 144860e7cdab9d5eceda5ac52ae0ddfb4bdab0067f2Patrik Hagglund MVT GetValue() const { 14592e946630d5f9bb092853b93501387dd216899b9Andrew Trick assert(IsValid() && "bad iterator"); 14692e946630d5f9bb092853b93501387dd216899b9Andrew Trick return ValueType; 14792e946630d5f9bb092853b93501387dd216899b9Andrew Trick } 14892e946630d5f9bb092853b93501387dd216899b9Andrew Trick 14977b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson const SDNode *GetNode() const { 15077b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson return Node; 15177b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson } 15277b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson 15377b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson unsigned GetIdx() const { 154702110159a53481227b01fed81fa4eec0ad3cc46Owen Anderson return DefIdx-1; 15577b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson } 15677b4b13c2a525faf646a6784b24692cf0459b75eOwen Anderson 15792e946630d5f9bb092853b93501387dd216899b9Andrew Trick void Advance(); 15892e946630d5f9bb092853b93501387dd216899b9Andrew Trick private: 15992e946630d5f9bb092853b93501387dd216899b9Andrew Trick void InitNodeNumDefs(); 16092e946630d5f9bb092853b93501387dd216899b9Andrew Trick }; 16192e946630d5f9bb092853b93501387dd216899b9Andrew Trick 162a98f600a64b7b70754df58926ce8d60feeb9ce29Andrew Trick protected: 163a98f600a64b7b70754df58926ce8d60feeb9ce29Andrew Trick /// ForceUnitLatencies - Return true if all scheduling edges should be given 164a98f600a64b7b70754df58926ce8d60feeb9ce29Andrew Trick /// a latency value of one. The default is to return false; schedulers may 165a98f600a64b7b70754df58926ce8d60feeb9ce29Andrew Trick /// override this as needed. 166a98f600a64b7b70754df58926ce8d60feeb9ce29Andrew Trick virtual bool forceUnitLatencies() const { return false; } 167a98f600a64b7b70754df58926ce8d60feeb9ce29Andrew Trick 168343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman private: 169c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng /// ClusterNeighboringLoads - Cluster loads from "near" addresses into 170c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng /// combined SUnits. 171302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng void ClusterNeighboringLoads(SDNode *Node); 172302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng /// ClusterNodes - Cluster certain nodes which should be scheduled together. 173302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng /// 174302ef834e0a2fd03e4b435079a9fa6c1e1cdc23bEvan Cheng void ClusterNodes(); 175c589e03865bb31da70e0037d5c32fdaaa5f79f24Evan Cheng 176c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph. 177c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman void BuildSchedUnits(); 178c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman void AddSchedEdges(); 17984b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick 18084b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap, 18184b454d1a270a5d685e01686ed15e68c44b0b56aAndrew Trick MachineBasicBlock::iterator InsertPos); 182343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman }; 183343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 184343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 185343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#endif 186