#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/iterator_range.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/raw_ostream.h"
#include <string>
#include <vector>
+#include <list>
#define DEBUG_TYPE "block-freq"
struct LoopData {
typedef SmallVector<std::pair<BlockNode, BlockMass>, 4> ExitMap;
typedef SmallVector<BlockNode, 4> MemberList;
- BlockNode Header; ///< Header.
+ LoopData *Parent; ///< The parent loop.
bool IsPackaged; ///< Whether this has been packaged.
ExitMap Exits; ///< Successor edges (and weights).
- MemberList Members; ///< Members of the loop.
+ MemberList Nodes; ///< Header and the members of the loop.
BlockMass BackedgeMass; ///< Mass returned to loop header.
BlockMass Mass;
Float Scale;
- LoopData(const BlockNode &Header) : Header(Header), IsPackaged(false) {}
+ LoopData(LoopData *Parent, const BlockNode &Header)
+ : Parent(Parent), IsPackaged(false), Nodes(1, Header) {}
+ bool isHeader(const BlockNode &Node) const { return Node == Nodes[0]; }
+ BlockNode getHeader() const { return Nodes[0]; }
+
+ MemberList::const_iterator members_begin() const {
+ return Nodes.begin() + 1;
+ }
+ MemberList::const_iterator members_end() const { return Nodes.end(); }
+ iterator_range<MemberList::const_iterator> members() const {
+ return make_range(members_begin(), members_end());
+ }
};
/// \brief Index of loop information.
struct WorkingData {
- LoopData *Loop; ///< The loop this block is the header of.
- BlockNode ContainingLoop; ///< The block whose loop this block is inside.
- bool IsPackaged; ///< Has ContainingLoop been packaged up?
- BlockMass Mass; ///< Mass distribution from the entry block.
+ BlockNode Node; ///< This node.
+ LoopData *Loop; ///< The loop this block is inside.
+ BlockMass Mass; ///< Mass distribution from the entry block.
- WorkingData() : Loop(nullptr), IsPackaged(false) {}
+ WorkingData(const BlockNode &Node) : Node(Node), Loop(nullptr) {}
- bool hasLoopHeader() const { return ContainingLoop.isValid(); }
- bool isLoopHeader() const { return Loop; }
+ 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 Has this block's loop been packaged up?
- bool isAPackage() const { return Loop && Loop->IsPackaged; }
+ /// \brief Has ContainingLoop been packaged up?
+ bool isPackaged() const {
+ auto *ContainingLoop = getContainingLoop();
+ return ContainingLoop && ContainingLoop->IsPackaged;
+ }
+ /// \brief Has Loop been packaged up?
+ bool isAPackage() const { return isLoopHeader() && Loop->IsPackaged; }
};
/// \brief Unscaled probability weight.
/// \brief Loop data: see initializeLoops().
std::vector<WorkingData> Working;
- /// \brief Indexed information about packaged loops.
- std::vector<std::unique_ptr<LoopData>> PackagedLoops;
+ /// \brief Indexed information about loops.
+ std::list<LoopData> Loops;
/// \brief Add all edges out of a packaged loop to the distribution.
///
/// Adds all edges from LocalLoopHead to Dist. Calls addToDist() to add each
/// successor edge.
- void addLoopSuccessorsToDist(const BlockNode &LoopHead,
- const BlockNode &LocalLoopHead,
+ void addLoopSuccessorsToDist(const LoopData *OuterLoop, LoopData &Loop,
Distribution &Dist);
/// \brief Add an edge to the distribution.
/// 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).
- void addToDist(Distribution &Dist, const BlockNode &LoopHead,
+ void addToDist(Distribution &Dist, const LoopData *OuterLoop,
const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight);
LoopData &getLoopPackage(const BlockNode &Head) {
assert(Head.Index < Working.size());
- assert(Working[Head.Index].Loop != nullptr);
+ assert(Working[Head.Index].isLoopHeader());
return *Working[Head.Index].Loop;
}
/// \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 PackagedLoops.
+ /// backedges and exits are stored in its entry in Loops.
///
/// Mass is distributed in parallel from two copies of the source mass.
///
/// 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, const BlockNode &LoopHead,
+ void distributeMass(const BlockNode &Source, LoopData *OuterLoop,
Distribution &Dist);
/// \brief Compute the loop scale for a loop.
- void computeLoopScale(const BlockNode &LoopHead);
+ void computeLoopScale(LoopData &Loop);
/// \brief Package up a loop.
- void packageLoop(const BlockNode &LoopHead);
+ void packageLoop(LoopData &Loop);
/// \brief Finalize frequency metrics.
///
void initializeLoops();
void runOnFunction(const FunctionT *F);
- void propagateMassToSuccessors(const BlockNode &LoopHead,
- const BlockNode &Node);
+ void propagateMassToSuccessors(LoopData *OuterLoop, const BlockNode &Node);
void computeMassInLoops();
- void computeMassInLoop(const BlockNode &LoopHead);
+ void computeMassInLoop(LoopData &Loop);
void computeMassInFunction();
std::string getBlockName(const BlockNode &Node) const override {
Nodes[*I] = Node;
}
- Working.resize(RPOT.size());
+ Working.reserve(RPOT.size());
+ for (size_t Index = 0; Index < RPOT.size(); ++Index)
+ Working.emplace_back(Index);
Freqs.resize(RPOT.size());
}
return;
// Visit loops top down and assign them an index.
- std::deque<const LoopT *> Q;
- Q.insert(Q.end(), LI->begin(), LI->end());
+ std::deque<std::pair<const LoopT *, LoopData *>> Q;
+ for (const LoopT *L : *LI)
+ Q.emplace_back(L, nullptr);
while (!Q.empty()) {
- const LoopT *Loop = Q.front();
+ const LoopT *Loop = Q.front().first;
+ LoopData *Parent = Q.front().second;
Q.pop_front();
- Q.insert(Q.end(), Loop->begin(), Loop->end());
- // Save the order this loop was visited.
BlockNode Header = getNode(Loop->getHeader());
assert(Header.isValid());
- PackagedLoops.emplace_back(new LoopData(Header));
- Working[Header.Index].Loop = PackagedLoops.back().get();
+ Loops.emplace_back(Parent, Header);
+ Working[Header.Index].Loop = &Loops.back();
DEBUG(dbgs() << " - loop = " << getBlockName(Header) << "\n");
+
+ for (const LoopT *L : *Loop)
+ Q.emplace_back(L, &Loops.back());
}
// Visit nodes in reverse post-order and add them to their deepest containing
// loop.
for (size_t Index = 0; Index < RPOT.size(); ++Index) {
+ // Loop headers have already been mostly mapped.
+ if (Working[Index].isLoopHeader()) {
+ LoopData *ContainingLoop = Working[Index].getContainingLoop();
+ if (ContainingLoop)
+ ContainingLoop->Nodes.push_back(Index);
+ continue;
+ }
+
const LoopT *Loop = LI->getLoopFor(RPOT[Index]);
if (!Loop)
continue;
- // If this is a loop header, find its parent loop (if any).
- if (Working[Index].isLoopHeader())
- if (!(Loop = Loop->getParentLoop()))
- continue;
-
// Add this node to its containing loop's member list.
BlockNode Header = getNode(Loop->getHeader());
assert(Header.isValid());
const auto &HeaderData = Working[Header.Index];
assert(HeaderData.isLoopHeader());
- Working[Index].ContainingLoop = Header;
- HeaderData.Loop->Members.push_back(Index);
+ Working[Index].Loop = HeaderData.Loop;
+ HeaderData.Loop->Nodes.push_back(Index);
DEBUG(dbgs() << " - loop = " << getBlockName(Header)
<< ": member = " << getBlockName(Index) << "\n");
}
template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInLoops() {
// Visit loops with the deepest first, and the top-level loops last.
- for (const auto &L : make_range(PackagedLoops.rbegin(), PackagedLoops.rend()))
- computeMassInLoop(L->Header);
+ for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; ++L)
+ computeMassInLoop(*L);
}
template <class BT>
-void BlockFrequencyInfoImpl<BT>::computeMassInLoop(const BlockNode &LoopHead) {
+void BlockFrequencyInfoImpl<BT>::computeMassInLoop(LoopData &Loop) {
// Compute mass in loop.
- DEBUG(dbgs() << "compute-mass-in-loop: " << getBlockName(LoopHead) << "\n");
+ DEBUG(dbgs() << "compute-mass-in-loop: " << getBlockName(Loop.getHeader())
+ << "\n");
- Working[LoopHead.Index].Mass = BlockMass::getFull();
- propagateMassToSuccessors(LoopHead, LoopHead);
+ Working[Loop.getHeader().Index].Mass = BlockMass::getFull();
+ propagateMassToSuccessors(&Loop, Loop.getHeader());
- for (const BlockNode &M : getLoopPackage(LoopHead).Members)
- propagateMassToSuccessors(LoopHead, M);
+ for (const BlockNode &M : Loop.members())
+ propagateMassToSuccessors(&Loop, M);
- computeLoopScale(LoopHead);
- packageLoop(LoopHead);
+ computeLoopScale(Loop);
+ packageLoop(Loop);
}
template <class BT> void BlockFrequencyInfoImpl<BT>::computeMassInFunction() {
if (Working[Node.Index].hasLoopHeader())
continue;
- propagateMassToSuccessors(BlockNode(), Node);
+ propagateMassToSuccessors(nullptr, Node);
}
}
template <class BT>
void
-BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(const BlockNode &LoopHead,
+BlockFrequencyInfoImpl<BT>::propagateMassToSuccessors(LoopData *OuterLoop,
const BlockNode &Node) {
DEBUG(dbgs() << " - node: " << getBlockName(Node) << "\n");
// Calculate probability for successors.
Distribution Dist;
- if (Node != LoopHead && Working[Node.Index].isLoopHeader())
- addLoopSuccessorsToDist(LoopHead, Node, Dist);
+ if (Working[Node.Index].isLoopHeader() &&
+ Working[Node.Index].Loop != OuterLoop)
+ addLoopSuccessorsToDist(OuterLoop, *Working[Node.Index].Loop, Dist);
else {
const BlockT *BB = getBlock(Node);
for (auto SI = Successor::child_begin(BB), SE = Successor::child_end(BB);
SI != SE; ++SI)
// Do not dereference SI, or getEdgeWeight() is linear in the number of
// successors.
- addToDist(Dist, LoopHead, Node, getNode(*SI), BPI->getEdgeWeight(BB, SI));
+ addToDist(Dist, OuterLoop, Node, getNode(*SI),
+ BPI->getEdgeWeight(BB, SI));
}
// Distribute mass to successors, saving exit and backedge data in the
// loop header.
- distributeMass(Node, LoopHead, Dist);
+ distributeMass(Node, OuterLoop, Dist);
}
template <class BT>
projects / oota-llvm.git / blobdiff