/usr/include/llvm-3.9/llvm/CodeGen/ScheduleDFS.h is in llvm-3.9-dev 1:3.9.1-19ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 | //===- ScheduleDAGILP.h - ILP metric for ScheduleDAGInstrs ------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Definition of an ILP metric for machine level instruction scheduling.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_SCHEDULEDFS_H
#define LLVM_CODEGEN_SCHEDULEDFS_H
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/Support/DataTypes.h"
#include <vector>
namespace llvm {
class raw_ostream;
class IntEqClasses;
class ScheduleDAGInstrs;
class SUnit;
/// \brief Represent the ILP of the subDAG rooted at a DAG node.
///
/// ILPValues summarize the DAG subtree rooted at each node. ILPValues are
/// valid for all nodes regardless of their subtree membership.
///
/// When computed using bottom-up DFS, this metric assumes that the DAG is a
/// forest of trees with roots at the bottom of the schedule branching upward.
struct ILPValue {
unsigned InstrCount;
/// Length may either correspond to depth or height, depending on direction,
/// and cycles or nodes depending on context.
unsigned Length;
ILPValue(unsigned count, unsigned length):
InstrCount(count), Length(length) {}
// Order by the ILP metric's value.
bool operator<(ILPValue RHS) const {
return (uint64_t)InstrCount * RHS.Length
< (uint64_t)Length * RHS.InstrCount;
}
bool operator>(ILPValue RHS) const {
return RHS < *this;
}
bool operator<=(ILPValue RHS) const {
return (uint64_t)InstrCount * RHS.Length
<= (uint64_t)Length * RHS.InstrCount;
}
bool operator>=(ILPValue RHS) const {
return RHS <= *this;
}
void print(raw_ostream &OS) const;
void dump() const;
};
/// \brief Compute the values of each DAG node for various metrics during DFS.
class SchedDFSResult {
friend class SchedDFSImpl;
static const unsigned InvalidSubtreeID = ~0u;
/// \brief Per-SUnit data computed during DFS for various metrics.
///
/// A node's SubtreeID is set to itself when it is visited to indicate that it
/// is the root of a subtree. Later it is set to its parent to indicate an
/// interior node. Finally, it is set to a representative subtree ID during
/// finalization.
struct NodeData {
unsigned InstrCount;
unsigned SubtreeID;
NodeData(): InstrCount(0), SubtreeID(InvalidSubtreeID) {}
};
/// \brief Per-Subtree data computed during DFS.
struct TreeData {
unsigned ParentTreeID;
unsigned SubInstrCount;
TreeData(): ParentTreeID(InvalidSubtreeID), SubInstrCount(0) {}
};
/// \brief Record a connection between subtrees and the connection level.
struct Connection {
unsigned TreeID;
unsigned Level;
Connection(unsigned tree, unsigned level): TreeID(tree), Level(level) {}
};
bool IsBottomUp;
unsigned SubtreeLimit;
/// DFS results for each SUnit in this DAG.
std::vector<NodeData> DFSNodeData;
// Store per-tree data indexed on tree ID,
SmallVector<TreeData, 16> DFSTreeData;
// For each subtree discovered during DFS, record its connections to other
// subtrees.
std::vector<SmallVector<Connection, 4> > SubtreeConnections;
/// Cache the current connection level of each subtree.
/// This mutable array is updated during scheduling.
std::vector<unsigned> SubtreeConnectLevels;
public:
SchedDFSResult(bool IsBU, unsigned lim)
: IsBottomUp(IsBU), SubtreeLimit(lim) {}
/// \brief Get the node cutoff before subtrees are considered significant.
unsigned getSubtreeLimit() const { return SubtreeLimit; }
/// \brief Return true if this DFSResult is uninitialized.
///
/// resize() initializes DFSResult, while compute() populates it.
bool empty() const { return DFSNodeData.empty(); }
/// \brief Clear the results.
void clear() {
DFSNodeData.clear();
DFSTreeData.clear();
SubtreeConnections.clear();
SubtreeConnectLevels.clear();
}
/// \brief Initialize the result data with the size of the DAG.
void resize(unsigned NumSUnits) {
DFSNodeData.resize(NumSUnits);
}
/// \brief Compute various metrics for the DAG with given roots.
void compute(ArrayRef<SUnit> SUnits);
/// \brief Get the number of instructions in the given subtree and its
/// children.
unsigned getNumInstrs(const SUnit *SU) const {
return DFSNodeData[SU->NodeNum].InstrCount;
}
/// \brief Get the number of instructions in the given subtree not including
/// children.
unsigned getNumSubInstrs(unsigned SubtreeID) const {
return DFSTreeData[SubtreeID].SubInstrCount;
}
/// \brief Get the ILP value for a DAG node.
///
/// A leaf node has an ILP of 1/1.
ILPValue getILP(const SUnit *SU) const {
return ILPValue(DFSNodeData[SU->NodeNum].InstrCount, 1 + SU->getDepth());
}
/// \brief The number of subtrees detected in this DAG.
unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); }
/// \brief Get the ID of the subtree the given DAG node belongs to.
///
/// For convenience, if DFSResults have not been computed yet, give everything
/// tree ID 0.
unsigned getSubtreeID(const SUnit *SU) const {
if (empty())
return 0;
assert(SU->NodeNum < DFSNodeData.size() && "New Node");
return DFSNodeData[SU->NodeNum].SubtreeID;
}
/// \brief Get the connection level of a subtree.
///
/// For bottom-up trees, the connection level is the latency depth (in cycles)
/// of the deepest connection to another subtree.
unsigned getSubtreeLevel(unsigned SubtreeID) const {
return SubtreeConnectLevels[SubtreeID];
}
/// \brief Scheduler callback to update SubtreeConnectLevels when a tree is
/// initially scheduled.
void scheduleTree(unsigned SubtreeID);
};
raw_ostream &operator<<(raw_ostream &OS, const ILPValue &Val);
} // namespace llvm
#endif
|