ScheduleDFS.h revision bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097
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#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 611e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick void print(raw_ostream &OS) const; 621e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 631e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick void dump() const; 641e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick#endif 651e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick}; 661e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 678b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick/// \brief Compute the values of each DAG node for various metrics during DFS. 688b1496c922b6a21296f7d42172df45bf205d5419Andrew Trickclass SchedDFSResult { 698b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick friend class SchedDFSImpl; 708b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 71bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick static const unsigned InvalidSubtreeID = ~0u; 72bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick 738b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Per-SUnit data computed during DFS for various metrics. 74bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// 75bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// A node's SubtreeID is set to itself when it is visited to indicate that it 76bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// is the root of a subtree. Later it is set to its parent to indicate an 77bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// interior node. Finally, it is set to a representative subtree ID during 78bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// finalization. 798b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick struct NodeData { 808b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned InstrCount; 81bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick unsigned SubInstrCount; 828b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned SubtreeID; 838b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 84bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick NodeData(): InstrCount(0), SubInstrCount(0), SubtreeID(InvalidSubtreeID) {} 858b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick }; 868b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 878b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Record a connection between subtrees and the connection level. 888b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick struct Connection { 898b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned TreeID; 908b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned Level; 918b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 928b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {} 938b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick }; 948b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 951e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick bool IsBottomUp; 968b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned SubtreeLimit; 978b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// DFS results for each SUnit in this DAG. 988b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick std::vector<NodeData> DFSData; 998b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1008b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick // For each subtree discovered during DFS, record its connections to other 1018b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick // subtrees. 1028b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick std::vector<SmallVector<Connection, 4> > SubtreeConnections; 1038b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1048b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// Cache the current connection level of each subtree. 1058b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// This mutable array is updated during scheduling. 1068b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick std::vector<unsigned> SubtreeConnectLevels; 1071e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1081e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trickpublic: 1098b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick SchedDFSResult(bool IsBU, unsigned lim) 1108b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick : IsBottomUp(IsBU), SubtreeLimit(lim) {} 1118b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 112bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// \brief Return true if this DFSResult is uninitialized. 113bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// 114bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick /// resize() initializes DFSResult, while compute() populates it. 115bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick bool empty() const { return DFSData.empty(); } 116bfb8223e2b2a55c3ac6c73be0ac99bbce17cb097Andrew Trick 1178b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Clear the results. 1188b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick void clear() { 1198b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick DFSData.clear(); 1208b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick SubtreeConnections.clear(); 1218b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick SubtreeConnectLevels.clear(); 1228b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1231e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1241e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick /// \brief Initialize the result data with the size of the DAG. 1258b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick void resize(unsigned NumSUnits) { 1268b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick DFSData.resize(NumSUnits); 1278b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1281e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1298b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Compute various metrics for the DAG with given roots. 1308b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick void compute(ArrayRef<SUnit *> Roots); 1311e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1321e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick /// \brief Get the ILP value for a DAG node. 1338b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// 1348b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// A leaf node has an ILP of 1/1. 1356d28299b9dd3503a61ddffc64fe0201816445ab3Andrew Trick ILPValue getILP(const SUnit *SU) const { 1368b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick return ILPValue(DFSData[SU->NodeNum].InstrCount, 1 + SU->getDepth()); 1378b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1388b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1398b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief The number of subtrees detected in this DAG. 1408b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); } 1418b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1428b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Get the ID of the subtree the given DAG node belongs to. 1436d28299b9dd3503a61ddffc64fe0201816445ab3Andrew Trick unsigned getSubtreeID(const SUnit *SU) const { 1446d28299b9dd3503a61ddffc64fe0201816445ab3Andrew Trick assert(SU->NodeNum < DFSData.size() && "New Node"); 1458b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick return DFSData[SU->NodeNum].SubtreeID; 1468b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1478b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1488b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Get the connection level of a subtree. 1498b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// 1508b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// For bottom-up trees, the connection level is the latency depth (in cycles) 1518b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// of the deepest connection to another subtree. 1526d28299b9dd3503a61ddffc64fe0201816445ab3Andrew Trick unsigned getSubtreeLevel(unsigned SubtreeID) const { 1538b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick return SubtreeConnectLevels[SubtreeID]; 1548b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick } 1558b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick 1568b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// \brief Scheduler callback to update SubtreeConnectLevels when a tree is 1578b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick /// initially scheduled. 1588b1496c922b6a21296f7d42172df45bf205d5419Andrew Trick void scheduleTree(unsigned SubtreeID); 1591e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick}; 1601e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1611e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trickraw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val); 1621e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1631e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick} // namespace llvm 1641e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick 1651e94e98b0ec44c5b04eaa8c9e7fb6d7669b3cdeaAndrew Trick#endif 166