X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FBlockFrequencyInfoImpl.h;h=6c101a63e128c77ad5e1af8e51e6c7cb28c10183;hb=00552e3875ee5f382db6c98286a241a7d0efe1b8;hp=85a299b6dddf639edf3a3d16075b56980a4b3afe;hpb=2cdee49937886d441fe736fe285ae84cc743f1c6;p=oota-llvm.git diff --git a/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/include/llvm/Analysis/BlockFrequencyInfoImpl.h index 85a299b6ddd..6c101a63e12 100644 --- a/include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ b/include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -196,23 +196,26 @@ public: struct LoopData { typedef SmallVector, 4> ExitMap; typedef SmallVector NodeList; - LoopData *Parent; ///< The parent loop. - bool IsPackaged; ///< Whether this has been packaged. - uint32_t NumHeaders; ///< Number of headers. - ExitMap Exits; ///< Successor edges (and weights). - NodeList Nodes; ///< Header and the members of the loop. - BlockMass BackedgeMass; ///< Mass returned to loop header. + typedef SmallVector HeaderMassList; + LoopData *Parent; ///< The parent loop. + bool IsPackaged; ///< Whether this has been packaged. + uint32_t NumHeaders; ///< Number of headers. + ExitMap Exits; ///< Successor edges (and weights). + NodeList Nodes; ///< Header and the members of the loop. + HeaderMassList BackedgeMass; ///< Mass returned to each loop header. BlockMass Mass; Scaled64 Scale; LoopData(LoopData *Parent, const BlockNode &Header) - : Parent(Parent), IsPackaged(false), NumHeaders(1), Nodes(1, Header) {} + : Parent(Parent), IsPackaged(false), NumHeaders(1), Nodes(1, Header), + BackedgeMass(1) {} template LoopData(LoopData *Parent, It1 FirstHeader, It1 LastHeader, It2 FirstOther, It2 LastOther) : Parent(Parent), IsPackaged(false), Nodes(FirstHeader, LastHeader) { NumHeaders = Nodes.size(); Nodes.insert(Nodes.end(), FirstOther, LastOther); + BackedgeMass.resize(NumHeaders); } bool isHeader(const BlockNode &Node) const { if (isIrreducible()) @@ -223,6 +226,14 @@ public: BlockNode getHeader() const { return Nodes[0]; } bool isIrreducible() const { return NumHeaders > 1; } + HeaderMassList::difference_type getHeaderIndex(const BlockNode &B) { + assert(isHeader(B) && "this is only valid on loop header blocks"); + if (isIrreducible()) + return std::lower_bound(Nodes.begin(), Nodes.begin() + NumHeaders, B) - + Nodes.begin(); + return 0; + } + NodeList::const_iterator members_begin() const { return Nodes.begin() + NumHeaders; } @@ -431,6 +442,16 @@ public: /// \brief Compute the loop scale for a loop. void computeLoopScale(LoopData &Loop); + /// Adjust the mass of all headers in an irreducible loop. + /// + /// Initially, irreducible loops are assumed to distribute their mass + /// equally among its headers. This can lead to wrong frequency estimates + /// since some headers may be executed more frequently than others. + /// + /// This adjusts header mass distribution so it matches the weights of + /// the backedges going into each of the loop headers. + void adjustLoopHeaderMass(LoopData &Loop); + /// \brief Package up a loop. void packageLoop(LoopData &Loop); @@ -695,6 +716,17 @@ void IrreducibleGraph::addEdges(const BlockNode &Node, /// - Distribute the mass accordingly, dithering to minimize mass loss, /// as described in \a distributeMass(). /// +/// In the case of irreducible loops, instead of a single loop header, +/// there will be several. The computation of backedge masses is similar +/// but instead of having a single backedge mass, there will be one +/// backedge per loop header. In these cases, each backedge will carry +/// a mass proportional to the edge weights along the corresponding +/// path. +/// +/// At the end of propagation, the full mass assigned to the loop will be +/// distributed among the loop headers proportionally according to the +/// mass flowing through their backedges. +/// /// Finally, calculate the loop scale from the accumulated backedge mass. /// /// 3. Distribute mass in the function (\a computeMassInFunction()). @@ -735,11 +767,6 @@ void IrreducibleGraph::addEdges(const BlockNode &Node, /// as sub-loops, rather than arbitrarily shoving the problematic /// blocks into the headers of the main irreducible SCC. /// -/// - Backedge frequencies are assumed to be evenly split between the -/// headers of a given irreducible SCC. Instead, we could track the -/// backedge mass separately for each header, and adjust their relative -/// frequencies. -/// /// - Entry frequencies are assumed to be evenly split between the /// headers of a given irreducible SCC, which is the only option if we /// need to compute mass in the SCC before its parent loop. Instead, @@ -846,7 +873,7 @@ template class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { /// /// \pre \a computeMassInLoop() has been called for each subloop of \c /// OuterLoop. - /// \pre \c Insert points at the the last loop successfully processed by \a + /// \pre \c Insert points at the last loop successfully processed by \a /// computeMassInLoop(). /// \pre \c OuterLoop has irreducible SCCs. void computeIrreducibleMass(LoopData *OuterLoop, @@ -878,8 +905,8 @@ template class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase { public: const FunctionT *getFunction() const { return F; } - void doFunction(const FunctionT *F, const BranchProbabilityInfoT *BPI, - const LoopInfoT *LI); + void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI, + const LoopInfoT &LI); BlockFrequencyInfoImpl() : BPI(nullptr), LI(nullptr), F(nullptr) {} using BlockFrequencyInfoImplBase::getEntryFreq; @@ -911,13 +938,13 @@ public: }; template -void BlockFrequencyInfoImpl::doFunction(const FunctionT *F, - const BranchProbabilityInfoT *BPI, - const LoopInfoT *LI) { +void BlockFrequencyInfoImpl::calculate(const FunctionT &F, + const BranchProbabilityInfoT &BPI, + const LoopInfoT &LI) { // Save the parameters. - this->BPI = BPI; - this->LI = LI; - this->F = F; + this->BPI = &BPI; + this->LI = &LI; + this->F = &F; // Clean up left-over data structures. BlockFrequencyInfoImplBase::clear(); @@ -925,8 +952,8 @@ void BlockFrequencyInfoImpl::doFunction(const FunctionT *F, Nodes.clear(); // Initialize. - DEBUG(dbgs() << "\nblock-frequency: " << F->getName() << "\n=================" - << std::string(F->getName().size(), '=') << "\n"); + DEBUG(dbgs() << "\nblock-frequency: " << F.getName() << "\n=================" + << std::string(F.getName().size(), '=') << "\n"); initializeRPOT(); initializeLoops(); @@ -1042,6 +1069,8 @@ bool BlockFrequencyInfoImpl::computeMassInLoop(LoopData &Loop) { for (const BlockNode &M : Loop.Nodes) if (!propagateMassToSuccessors(&Loop, M)) llvm_unreachable("unhandled irreducible control flow"); + + adjustLoopHeaderMass(Loop); } else { Working[Loop.getHeader().Index].getMass() = BlockMass::getFull(); if (!propagateMassToSuccessors(&Loop, Loop.getHeader()))