11e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick//===- ScheduleDAGILP.h - ILP metric for ScheduleDAGInstrs ------*- C++ -*-===// 21e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// 31e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// The LLVM Compiler Infrastructure 41e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// 51e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// This file is distributed under the University of Illinois Open Source 61e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// License. See LICENSE.TXT for details. 71e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// 81e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick//===----------------------------------------------------------------------===// 91e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// 101e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// Definition of an ILP metric for machine level instruction scheduling. 111e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick// 121e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick//===----------------------------------------------------------------------===// 131e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 14674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_CODEGEN_SCHEDULEDFS_H 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_CODEGEN_SCHEDULEDFS_H 161e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 178b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick#include "llvm/CodeGen/ScheduleDAG.h" 181e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick#include "llvm/Support/DataTypes.h" 191e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick#include <vector> 201e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 211e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Tricknamespace llvm { 221e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 231e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trickclass raw_ostream; 248b1496c922b6a21296f7d42172df45bf205d5419Andrew Trickclass IntEqClasses; 251e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trickclass ScheduleDAGInstrs; 261e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trickclass SUnit; 271e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 281e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick/// \brief Represent the ILP of the subDAG rooted at a DAG node. 298b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick/// 30bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick/// ILPValues summarize the DAG subtree rooted at each node. ILPValues are 31bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick/// valid for all nodes regardless of their subtree membership. 32bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick/// 338b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick/// When computed using bottom-up DFS, this metric assumes that the DAG is a 348b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick/// forest of trees with roots at the bottom of the schedule branching upward. 351e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trickstruct ILPValue { 361e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick unsigned InstrCount; 378b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// Length may either correspond to depth or height, depending on direction, 388b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// and cycles or nodes depending on context. 398b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned Length; 401e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 418b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick ILPValue(unsigned count, unsigned length): 428b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick InstrCount(count), Length(length) {} 431e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 441e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick // Order by the ILP metric's value. 451e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick bool operator<(ILPValue RHS) const { 468b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick return (uint64_t)InstrCount * RHS.Length 478b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick < (uint64_t)Length * RHS.InstrCount; 481e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick } 491e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick bool operator>(ILPValue RHS) const { 501e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick return RHS < *this; 511e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick } 521e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick bool operator<=(ILPValue RHS) const { 538b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick return (uint64_t)InstrCount * RHS.Length 548b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick <= (uint64_t)Length * RHS.InstrCount; 551e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick } 561e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick bool operator>=(ILPValue RHS) const { 571e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick return RHS <= *this; 581e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick } 591e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 601e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick void print(raw_ostream &OS) const; 611e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 621e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick void dump() const; 631e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick}; 641e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 658b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick/// \brief Compute the values of each DAG node for various metrics during DFS. 668b1496c922b6a21296f7d42172df45bf205d5419Andrew Trickclass SchedDFSResult { 678b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick friend class SchedDFSImpl; 688b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 69bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick static const unsigned InvalidSubtreeID = ~0u; 70bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick 718b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Per-SUnit data computed during DFS for various metrics. 72bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// 73bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// A node's SubtreeID is set to itself when it is visited to indicate that it 74bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// is the root of a subtree. Later it is set to its parent to indicate an 75bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// interior node. Finally, it is set to a representative subtree ID during 76bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// finalization. 778b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick struct NodeData { 788b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned InstrCount; 798b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned SubtreeID; 808b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 81988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {} 82988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick }; 83988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick 84988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick /// \brief Per-Subtree data computed during DFS. 85988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick struct TreeData { 86988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick unsigned ParentTreeID; 87988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick unsigned SubInstrCount; 88988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick 89988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {} 908b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick }; 918b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 928b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Record a connection between subtrees and the connection level. 938b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick struct Connection { 948b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned TreeID; 958b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned Level; 968b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 978b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {} 988b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick }; 998b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1001e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick bool IsBottomUp; 1018b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned SubtreeLimit; 1028b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// DFS results for each SUnit in this DAG. 103988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick std::vector<NodeData> DFSNodeData; 104988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick 105988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick // Store per-tree data indexed on tree ID, 106988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick SmallVector<TreeData, 16> DFSTreeData; 1078b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1088b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick // For each subtree discovered during DFS, record its connections to other 1098b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick // subtrees. 1108b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick std::vector<SmallVector<Connection, 4> > SubtreeConnections; 1118b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1128b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// Cache the current connection level of each subtree. 1138b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// This mutable array is updated during scheduling. 1148b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick std::vector<unsigned> SubtreeConnectLevels; 1151e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1161e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trickpublic: 1178b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick SchedDFSResult(bool IsBU, unsigned lim) 1188b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick : IsBottomUp(IsBU), SubtreeLimit(lim) {} 1198b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 120988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick /// \brief Get the node cutoff before subtrees are considered significant. 121988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick unsigned getSubtreeLimit() const { return SubtreeLimit; } 122988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick 123bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// \brief Return true if this DFSResult is uninitialized. 124bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// 125bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// resize() initializes DFSResult, while compute() populates it. 126988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick bool empty() const { return DFSNodeData.empty(); } 127bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick 1288b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Clear the results. 1298b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick void clear() { 130988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick DFSNodeData.clear(); 131988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick DFSTreeData.clear(); 1328b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick SubtreeConnections.clear(); 1338b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick SubtreeConnectLevels.clear(); 1348b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1351e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1361e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick /// \brief Initialize the result data with the size of the DAG. 1378b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick void resize(unsigned NumSUnits) { 138988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick DFSNodeData.resize(NumSUnits); 1398b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1401e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1418b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Compute various metrics for the DAG with given roots. 1424e1fb1894048455d49d62543b3f83672b27b0000Andrew Trick void compute(ArrayRef<SUnit> SUnits); 1431e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 144988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick /// \brief Get the number of instructions in the given subtree and its 145988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick /// children. 146988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick unsigned getNumInstrs(const SUnit *SU) const { 147988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick return DFSNodeData[SU->NodeNum].InstrCount; 148988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick } 149988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick 150988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick /// \brief Get the number of instructions in the given subtree not including 151988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick /// children. 152988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick unsigned getNumSubInstrs(unsigned SubtreeID) const { 153988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick return DFSTreeData[SubtreeID].SubInstrCount; 154988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick } 155988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick 1561e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick /// \brief Get the ILP value for a DAG node. 1578b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// 1588b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// A leaf node has an ILP of 1/1. 1596d28299b9dd3503a61ddffc64fe0201816445ab3Andrew Trick ILPValue getILP(const SUnit *SU) const { 160988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth()); 1618b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1628b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1638b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief The number of subtrees detected in this DAG. 1648b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); } 1658b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1668b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Get the ID of the subtree the given DAG node belongs to. 1674e1fb1894048455d49d62543b3f83672b27b0000Andrew Trick /// 1684e1fb1894048455d49d62543b3f83672b27b0000Andrew Trick /// For convenience, if DFSResults have not been computed yet, give everything 1694e1fb1894048455d49d62543b3f83672b27b0000Andrew Trick /// tree ID 0. 1706d28299b9dd3503a61ddffc64fe0201816445ab3Andrew Trick unsigned getSubtreeID(const SUnit *SU) const { 1714e1fb1894048455d49d62543b3f83672b27b0000Andrew Trick if (empty()) 1724e1fb1894048455d49d62543b3f83672b27b0000Andrew Trick return 0; 173988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick assert(SU->NodeNum < DFSNodeData.size() && "New Node"); 174988d06b0e574d8e50b043fd74dbf91c1dc403542Andrew Trick return DFSNodeData[SU->NodeNum].SubtreeID; 1758b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1768b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1778b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Get the connection level of a subtree. 1788b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// 1798b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// For bottom-up trees, the connection level is the latency depth (in cycles) 1808b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// of the deepest connection to another subtree. 1816d28299b9dd3503a61ddffc64fe0201816445ab3Andrew Trick unsigned getSubtreeLevel(unsigned SubtreeID) const { 1828b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick return SubtreeConnectLevels[SubtreeID]; 1838b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1848b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1858b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is 1868b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// initially scheduled. 1878b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick void scheduleTree(unsigned SubtreeID); 1881e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick}; 1891e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1901e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trickraw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val); 1911e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1921e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick} // namespace llvm 1931e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1941e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick#endif 195