WorkingData(const BlockNode &Node) : Node(Node), Loop(nullptr) {}
bool isLoopHeader() const { return Loop && Loop->isHeader(Node); }
- bool hasLoopHeader() const { return isLoopHeader() ? Loop->Parent : Loop; }
LoopData *getContainingLoop() const {
return isLoopHeader() ? Loop->Parent : Loop;
}
- BlockNode getContainingHeader() const {
- auto *ContainingLoop = getContainingLoop();
- if (ContainingLoop)
- return ContainingLoop->getHeader();
- return BlockNode();
+
+ /// \brief Resolve a node to its representative.
+ ///
+ /// Get the node currently representing Node, which could be a containing
+ /// loop.
+ ///
+ /// This function should only be called when distributing mass. As long as
+ /// there are no irreducilbe edges to Node, then it will have complexity
+ /// O(1) in this context.
+ ///
+ /// In general, the complexity is O(L), where L is the number of loop
+ /// headers Node has been packaged into. Since this method is called in
+ /// the context of distributing mass, L will be the number of loop headers
+ /// an early exit edge jumps out of.
+ BlockNode getResolvedNode() const {
+ auto L = getPackagedLoop();
+ return L ? L->getHeader() : Node;
+ }
+ LoopData *getPackagedLoop() const {
+ if (!Loop || !Loop->IsPackaged)
+ return nullptr;
+ auto L = Loop;
+ while (L->Parent && L->Parent->IsPackaged)
+ L = L->Parent;
+ return L;
}
+ /// \brief Get the appropriate mass for a node.
+ ///
+ /// Get appropriate mass for Node. If Node is a loop-header (whose loop
+ /// has been packaged), returns the mass of its pseudo-node. If it's a
+ /// node inside a packaged loop, it returns the loop's mass.
+ BlockMass &getMass() { return isAPackage() ? Loop->Mass : Mass; }
+
/// \brief Has ContainingLoop been packaged up?
- bool isPackaged() const {
- auto *ContainingLoop = getContainingLoop();
- return ContainingLoop && ContainingLoop->IsPackaged;
- }
+ bool isPackaged() const { return getResolvedNode() != Node; }
/// \brief Has Loop been packaged up?
bool isAPackage() const { return isLoopHeader() && Loop->IsPackaged; }
};
/// This class collates the successor edge weights for later processing.
///
/// \a DidOverflow indicates whether \a Total did overflow while adding to
- /// the distribution. It should never overflow twice. There's no flag for
- /// whether \a ForwardTotal overflows, since when \a Total exceeds 32-bits
- /// they both get re-computed during \a normalize().
+ /// the distribution. It should never overflow twice.
struct Distribution {
typedef SmallVector<Weight, 4> WeightList;
WeightList Weights; ///< Individual successor weights.
uint64_t Total; ///< Sum of all weights.
bool DidOverflow; ///< Whether \a Total did overflow.
- uint32_t ForwardTotal; ///< Total excluding backedges.
- Distribution() : Total(0), DidOverflow(false), ForwardTotal(0) {}
+ Distribution() : Total(0), DidOverflow(false) {}
void addLocal(const BlockNode &Node, uint64_t Amount) {
add(Node, Amount, Weight::Local);
}
/// \brief Add an edge to the distribution.
///
/// Adds an edge to Succ to Dist. If \c LoopHead.isValid(), then whether the
- /// edge is forward/exit/backedge is in the context of LoopHead. Otherwise,
- /// every edge should be a forward edge (since all the loops are packaged
- /// up).
+ /// edge is local/exit/backedge is in the context of LoopHead. Otherwise,
+ /// every edge should be a local edge (since all the loops are packaged up).
void addToDist(Distribution &Dist, const LoopData *OuterLoop,
const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight);
return *Working[Head.Index].Loop;
}
- /// \brief Get a possibly packaged node.
- ///
- /// Get the node currently representing Node, which could be a containing
- /// loop.
- ///
- /// This function should only be called when distributing mass. As long as
- /// there are no irreducilbe edges to Node, then it will have complexity O(1)
- /// in this context.
- ///
- /// In general, the complexity is O(L), where L is the number of loop headers
- /// Node has been packaged into. Since this method is called in the context
- /// of distributing mass, L will be the number of loop headers an early exit
- /// edge jumps out of.
- BlockNode getPackagedNode(const BlockNode &Node) {
- assert(Node.isValid());
- if (!Working[Node.Index].isPackaged())
- return Node;
- if (!Working[Node.Index].isAPackage())
- return Node;
- return getPackagedNode(Working[Node.Index].getContainingHeader());
- }
-
/// \brief Distribute mass according to a distribution.
///
/// Distributes the mass in Source according to Dist. If LoopHead.isValid(),
/// backedges and exits are stored in its entry in Loops.
///
/// Mass is distributed in parallel from two copies of the source mass.
- ///
- /// The first mass (forward) represents the distribution of mass through the
- /// local DAG. This distribution should lose mass at loop exits and ignore
- /// backedges.
- ///
- /// The second mass (general) represents the behavior of the loop in the
- /// global context. In a given distribution from the head, how much mass
- /// exits, and to where? How much mass returns to the loop head?
- ///
- /// The forward mass should be split up between local successors and exits,
- /// but only actually distributed to the local successors. The general mass
- /// should be split up between all three types of successors, but distributed
- /// only to exits and backedges.
void distributeMass(const BlockNode &Source, LoopData *OuterLoop,
Distribution &Dist);
/// in \a LoopData::Exits. Otherwise, fetch it from
/// BranchProbabilityInfo.
///
-/// - Each successor is categorized as \a Weight::Local, a normal
-/// forward edge within the current loop, \a Weight::Backedge, a
-/// backedge to the loop header, or \a Weight::Exit, any successor
-/// outside the loop. The weight, the successor, and its category
-/// are stored in \a Distribution. There can be multiple edges to
-/// each successor.
+/// - Each successor is categorized as \a Weight::Local, a local edge
+/// within the current loop, \a Weight::Backedge, a backedge to the
+/// loop header, or \a Weight::Exit, any successor outside the loop.
+/// The weight, the successor, and its category are stored in \a
+/// Distribution. There can be multiple edges to each successor.
///
/// - Normalize the distribution: scale weights down so that their sum
/// is 32-bits, and coalesce multiple edges to the same node.
///
/// - Distribute the mass accordingly, dithering to minimize mass loss,
-/// as described in \a distributeMass(). Mass is distributed in
-/// parallel in two ways: forward, and general. Local successors
-/// take their mass from the forward mass, while exit and backedge
-/// successors take their mass from the general mass. Additionally,
-/// exit edges use up (ignored) mass from the forward mass, and local
-/// edges use up (ignored) mass from the general distribution.
+/// as described in \a distributeMass().
///
/// Finally, calculate the loop scale from the accumulated backedge mass.
///
return RPOT[Node.Index];
}
+ /// \brief Run (and save) a post-order traversal.
+ ///
+ /// Saves a reverse post-order traversal of all the nodes in \a F.
void initializeRPOT();
+
+ /// \brief Initialize loop data.
+ ///
+ /// Build up \a Loops using \a LoopInfo. \a LoopInfo gives us a mapping from
+ /// each block to the deepest loop it's in, but we need the inverse. For each
+ /// loop, we store in reverse post-order its "immediate" members, defined as
+ /// the header, the headers of immediate sub-loops, and all other blocks in
+ /// the loop that are not in sub-loops.
void initializeLoops();
- void runOnFunction(const FunctionT *F);
+ /// \brief Propagate to a block's successors.
+ ///
+ /// In the context of distributing mass through \c OuterLoop, divide the mass
+ /// currently assigned to \c Node between its successors.
void propagateMassToSuccessors(LoopData *OuterLoop, const BlockNode &Node);
- void computeMassInLoops();
+
+ /// \brief Compute mass in a particular loop.
+ ///
+ /// Assign mass to \c Loop's header, and then for each block in \c Loop in
+ /// reverse post-order, distribute mass to its successors. Only visits nodes
+ /// that have not been packaged into sub-loops.
+ ///
+ /// \pre \a computeMassInLoop() has been called for each subloop of \c Loop.
void computeMassInLoop(LoopData &Loop);
+
+ /// \brief Compute mass in all loops.
+ ///
+ /// For each loop bottom-up, call \a computeMassInLoop().
+ void computeMassInLoops();
+
+ /// \brief Compute mass in the top-level function.
+ ///
+ /// Assign mass to the entry block, and then for each block in reverse
+ /// post-order, distribute mass to its successors. Skips nodes that have
+ /// been packaged into loops.
+ ///
+ /// \pre \a computeMassInLoops() has been called.
void computeMassInFunction();
std::string getBlockName(const BlockNode &Node) const override {
void doFunction(const FunctionT *F, const BranchProbabilityInfoT *BPI,
const LoopInfoT *LI);
- BlockFrequencyInfoImpl() : BPI(0), LI(0), F(0) {}
+ BlockFrequencyInfoImpl() : BPI(nullptr), LI(nullptr), F(nullptr) {}
using BlockFrequencyInfoImplBase::getEntryFreq;
BlockFrequency getBlockFreq(const BlockT *BB) const {
DEBUG(dbgs() << "compute-mass-in-loop: " << getBlockName(Loop.getHeader())
<< "\n");
- Working[Loop.getHeader().Index].Mass = BlockMass::getFull();
+ Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
propagateMassToSuccessors(&Loop, Loop.getHeader());
for (const BlockNode &M : Loop.members())
assert(!Working.empty() && "no blocks in function");
assert(!Working[0].isLoopHeader() && "entry block is a loop header");
- Working[0].Mass = BlockMass::getFull();
+ Working[0].getMass() = BlockMass::getFull();
for (rpot_iterator I = rpot_begin(), IE = rpot_end(); I != IE; ++I) {
// Check for nodes that have been packaged.
BlockNode Node = getNode(I);
- if (Working[Node.Index].hasLoopHeader())
+ if (Working[Node.Index].isPackaged())
continue;
propagateMassToSuccessors(nullptr, Node);
DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n");
// Calculate probability for successors.
Distribution Dist;
- if (Working[Node.Index].isLoopHeader() &&
- Working[Node.Index].Loop != OuterLoop)
- addLoopSuccessorsToDist(OuterLoop, *Working[Node.Index].Loop, Dist);
- else {
+ if (auto *Loop = Working[Node.Index].getPackagedLoop()) {
+ assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop");
+ addLoopSuccessorsToDist(OuterLoop, *Loop, Dist);
+ } else {
const BlockT *BB = getBlock(Node);
for (auto SI = Successor::child_begin(BB), SE = Successor::child_end(BB);
SI != SE; ++SI)