1 //===- BlockFrequencyImplInfo.cpp - Block Frequency Info Implementation ---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Loops should be simplified before this analysis.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/GraphTraits.h"
18 #include "llvm/ADT/None.h"
19 #include "llvm/ADT/SCCIterator.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/Support/BlockFrequency.h"
22 #include "llvm/Support/BranchProbability.h"
23 #include "llvm/Support/Compiler.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/ScaledNumber.h"
26 #include "llvm/Support/MathExtras.h"
27 #include "llvm/Support/raw_ostream.h"
39 using namespace llvm::bfi_detail;
41 #define DEBUG_TYPE "block-freq"
43 ScaledNumber<uint64_t> BlockMass::toScaled() const {
45 return ScaledNumber<uint64_t>(1, 0);
46 return ScaledNumber<uint64_t>(getMass() + 1, -64);
49 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
50 LLVM_DUMP_METHOD void BlockMass::dump() const { print(dbgs()); }
53 static char getHexDigit(int N) {
60 raw_ostream &BlockMass::print(raw_ostream &OS) const {
61 for (int Digits = 0; Digits < 16; ++Digits)
62 OS << getHexDigit(Mass >> (60 - Digits * 4) & 0xf);
68 using BlockNode = BlockFrequencyInfoImplBase::BlockNode;
69 using Distribution = BlockFrequencyInfoImplBase::Distribution;
70 using WeightList = BlockFrequencyInfoImplBase::Distribution::WeightList;
71 using Scaled64 = BlockFrequencyInfoImplBase::Scaled64;
72 using LoopData = BlockFrequencyInfoImplBase::LoopData;
73 using Weight = BlockFrequencyInfoImplBase::Weight;
74 using FrequencyData = BlockFrequencyInfoImplBase::FrequencyData;
76 /// \brief Dithering mass distributer.
78 /// This class splits up a single mass into portions by weight, dithering to
79 /// spread out error. No mass is lost. The dithering precision depends on the
80 /// precision of the product of \a BlockMass and \a BranchProbability.
82 /// The distribution algorithm follows.
84 /// 1. Initialize by saving the sum of the weights in \a RemWeight and the
85 /// mass to distribute in \a RemMass.
87 /// 2. For each portion:
89 /// 1. Construct a branch probability, P, as the portion's weight divided
90 /// by the current value of \a RemWeight.
91 /// 2. Calculate the portion's mass as \a RemMass times P.
92 /// 3. Update \a RemWeight and \a RemMass at each portion by subtracting
93 /// the current portion's weight and mass.
94 struct DitheringDistributer {
98 DitheringDistributer(Distribution &Dist, const BlockMass &Mass);
100 BlockMass takeMass(uint32_t Weight);
103 } // end anonymous namespace
105 DitheringDistributer::DitheringDistributer(Distribution &Dist,
106 const BlockMass &Mass) {
108 RemWeight = Dist.Total;
112 BlockMass DitheringDistributer::takeMass(uint32_t Weight) {
113 assert(Weight && "invalid weight");
114 assert(Weight <= RemWeight);
115 BlockMass Mass = RemMass * BranchProbability(Weight, RemWeight);
117 // Decrement totals (dither).
123 void Distribution::add(const BlockNode &Node, uint64_t Amount,
124 Weight::DistType Type) {
125 assert(Amount && "invalid weight of 0");
126 uint64_t NewTotal = Total + Amount;
128 // Check for overflow. It should be impossible to overflow twice.
129 bool IsOverflow = NewTotal < Total;
130 assert(!(DidOverflow && IsOverflow) && "unexpected repeated overflow");
131 DidOverflow |= IsOverflow;
137 Weights.push_back(Weight(Type, Node, Amount));
140 static void combineWeight(Weight &W, const Weight &OtherW) {
141 assert(OtherW.TargetNode.isValid());
146 assert(W.Type == OtherW.Type);
147 assert(W.TargetNode == OtherW.TargetNode);
148 assert(OtherW.Amount && "Expected non-zero weight");
149 if (W.Amount > W.Amount + OtherW.Amount)
150 // Saturate on overflow.
151 W.Amount = UINT64_MAX;
153 W.Amount += OtherW.Amount;
156 static void combineWeightsBySorting(WeightList &Weights) {
157 // Sort so edges to the same node are adjacent.
158 std::sort(Weights.begin(), Weights.end(),
160 const Weight &R) { return L.TargetNode < R.TargetNode; });
162 // Combine adjacent edges.
163 WeightList::iterator O = Weights.begin();
164 for (WeightList::const_iterator I = O, L = O, E = Weights.end(); I != E;
168 // Find the adjacent weights to the same node.
169 for (++L; L != E && I->TargetNode == L->TargetNode; ++L)
170 combineWeight(*O, *L);
173 // Erase extra entries.
174 Weights.erase(O, Weights.end());
177 static void combineWeightsByHashing(WeightList &Weights) {
178 // Collect weights into a DenseMap.
179 using HashTable = DenseMap<BlockNode::IndexType, Weight>;
181 HashTable Combined(NextPowerOf2(2 * Weights.size()));
182 for (const Weight &W : Weights)
183 combineWeight(Combined[W.TargetNode.Index], W);
185 // Check whether anything changed.
186 if (Weights.size() == Combined.size())
189 // Fill in the new weights.
191 Weights.reserve(Combined.size());
192 for (const auto &I : Combined)
193 Weights.push_back(I.second);
196 static void combineWeights(WeightList &Weights) {
197 // Use a hash table for many successors to keep this linear.
198 if (Weights.size() > 128) {
199 combineWeightsByHashing(Weights);
203 combineWeightsBySorting(Weights);
206 static uint64_t shiftRightAndRound(uint64_t N, int Shift) {
211 return (N >> Shift) + (UINT64_C(1) & N >> (Shift - 1));
214 void Distribution::normalize() {
215 // Early exit for termination nodes.
219 // Only bother if there are multiple successors.
220 if (Weights.size() > 1)
221 combineWeights(Weights);
223 // Early exit when combined into a single successor.
224 if (Weights.size() == 1) {
226 Weights.front().Amount = 1;
230 // Determine how much to shift right so that the total fits into 32-bits.
232 // If we shift at all, shift by 1 extra. Otherwise, the lower limit of 1
233 // for each weight can cause a 32-bit overflow.
237 else if (Total > UINT32_MAX)
238 Shift = 33 - countLeadingZeros(Total);
240 // Early exit if nothing needs to be scaled.
242 // If we didn't overflow then combineWeights() shouldn't have changed the
243 // sum of the weights, but let's double-check.
244 assert(Total == std::accumulate(Weights.begin(), Weights.end(), UINT64_C(0),
245 [](uint64_t Sum, const Weight &W) {
246 return Sum + W.Amount;
248 "Expected total to be correct");
252 // Recompute the total through accumulation (rather than shifting it) so that
253 // it's accurate after shifting and any changes combineWeights() made above.
256 // Sum the weights to each node and shift right if necessary.
257 for (Weight &W : Weights) {
258 // Scale down below UINT32_MAX. Since Shift is larger than necessary, we
259 // can round here without concern about overflow.
260 assert(W.TargetNode.isValid());
261 W.Amount = std::max(UINT64_C(1), shiftRightAndRound(W.Amount, Shift));
262 assert(W.Amount <= UINT32_MAX);
267 assert(Total <= UINT32_MAX);
270 void BlockFrequencyInfoImplBase::clear() {
271 // Swap with a default-constructed std::vector, since std::vector<>::clear()
272 // does not actually clear heap storage.
273 std::vector<FrequencyData>().swap(Freqs);
274 IsIrrLoopHeader.clear();
275 std::vector<WorkingData>().swap(Working);
279 /// \brief Clear all memory not needed downstream.
281 /// Releases all memory not used downstream. In particular, saves Freqs.
282 static void cleanup(BlockFrequencyInfoImplBase &BFI) {
283 std::vector<FrequencyData> SavedFreqs(std::move(BFI.Freqs));
284 SparseBitVector<> SavedIsIrrLoopHeader(std::move(BFI.IsIrrLoopHeader));
286 BFI.Freqs = std::move(SavedFreqs);
287 BFI.IsIrrLoopHeader = std::move(SavedIsIrrLoopHeader);
290 bool BlockFrequencyInfoImplBase::addToDist(Distribution &Dist,
291 const LoopData *OuterLoop,
292 const BlockNode &Pred,
293 const BlockNode &Succ,
298 auto isLoopHeader = [&OuterLoop](const BlockNode &Node) {
299 return OuterLoop && OuterLoop->isHeader(Node);
302 BlockNode Resolved = Working[Succ.Index].getResolvedNode();
305 auto debugSuccessor = [&](const char *Type) {
307 << " [" << Type << "] weight = " << Weight;
308 if (!isLoopHeader(Resolved))
309 dbgs() << ", succ = " << getBlockName(Succ);
310 if (Resolved != Succ)
311 dbgs() << ", resolved = " << getBlockName(Resolved);
314 (void)debugSuccessor;
317 if (isLoopHeader(Resolved)) {
318 DEBUG(debugSuccessor("backedge"));
319 Dist.addBackedge(Resolved, Weight);
323 if (Working[Resolved.Index].getContainingLoop() != OuterLoop) {
324 DEBUG(debugSuccessor(" exit "));
325 Dist.addExit(Resolved, Weight);
329 if (Resolved < Pred) {
330 if (!isLoopHeader(Pred)) {
331 // If OuterLoop is an irreducible loop, we can't actually handle this.
332 assert((!OuterLoop || !OuterLoop->isIrreducible()) &&
333 "unhandled irreducible control flow");
335 // Irreducible backedge. Abort.
336 DEBUG(debugSuccessor("abort!!!"));
340 // If "Pred" is a loop header, then this isn't really a backedge; rather,
341 // OuterLoop must be irreducible. These false backedges can come only from
342 // secondary loop headers.
343 assert(OuterLoop && OuterLoop->isIrreducible() && !isLoopHeader(Resolved) &&
344 "unhandled irreducible control flow");
347 DEBUG(debugSuccessor(" local "));
348 Dist.addLocal(Resolved, Weight);
352 bool BlockFrequencyInfoImplBase::addLoopSuccessorsToDist(
353 const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist) {
354 // Copy the exit map into Dist.
355 for (const auto &I : Loop.Exits)
356 if (!addToDist(Dist, OuterLoop, Loop.getHeader(), I.first,
358 // Irreducible backedge.
364 /// \brief Compute the loop scale for a loop.
365 void BlockFrequencyInfoImplBase::computeLoopScale(LoopData &Loop) {
366 // Compute loop scale.
367 DEBUG(dbgs() << "compute-loop-scale: " << getLoopName(Loop) << "\n");
369 // Infinite loops need special handling. If we give the back edge an infinite
370 // mass, they may saturate all the other scales in the function down to 1,
371 // making all the other region temperatures look exactly the same. Choose an
372 // arbitrary scale to avoid these issues.
374 // FIXME: An alternate way would be to select a symbolic scale which is later
375 // replaced to be the maximum of all computed scales plus 1. This would
376 // appropriately describe the loop as having a large scale, without skewing
377 // the final frequency computation.
378 const Scaled64 InfiniteLoopScale(1, 12);
380 // LoopScale == 1 / ExitMass
381 // ExitMass == HeadMass - BackedgeMass
382 BlockMass TotalBackedgeMass;
383 for (auto &Mass : Loop.BackedgeMass)
384 TotalBackedgeMass += Mass;
385 BlockMass ExitMass = BlockMass::getFull() - TotalBackedgeMass;
387 // Block scale stores the inverse of the scale. If this is an infinite loop,
388 // its exit mass will be zero. In this case, use an arbitrary scale for the
391 ExitMass.isEmpty() ? InfiniteLoopScale : ExitMass.toScaled().inverse();
393 DEBUG(dbgs() << " - exit-mass = " << ExitMass << " (" << BlockMass::getFull()
394 << " - " << TotalBackedgeMass << ")\n"
395 << " - scale = " << Loop.Scale << "\n");
398 /// \brief Package up a loop.
399 void BlockFrequencyInfoImplBase::packageLoop(LoopData &Loop) {
400 DEBUG(dbgs() << "packaging-loop: " << getLoopName(Loop) << "\n");
402 // Clear the subloop exits to prevent quadratic memory usage.
403 for (const BlockNode &M : Loop.Nodes) {
404 if (auto *Loop = Working[M.Index].getPackagedLoop())
406 DEBUG(dbgs() << " - node: " << getBlockName(M.Index) << "\n");
408 Loop.IsPackaged = true;
412 static void debugAssign(const BlockFrequencyInfoImplBase &BFI,
413 const DitheringDistributer &D, const BlockNode &T,
414 const BlockMass &M, const char *Desc) {
415 dbgs() << " => assign " << M << " (" << D.RemMass << ")";
417 dbgs() << " [" << Desc << "]";
419 dbgs() << " to " << BFI.getBlockName(T);
424 void BlockFrequencyInfoImplBase::distributeMass(const BlockNode &Source,
426 Distribution &Dist) {
427 BlockMass Mass = Working[Source.Index].getMass();
428 DEBUG(dbgs() << " => mass: " << Mass << "\n");
430 // Distribute mass to successors as laid out in Dist.
431 DitheringDistributer D(Dist, Mass);
433 for (const Weight &W : Dist.Weights) {
434 // Check for a local edge (non-backedge and non-exit).
435 BlockMass Taken = D.takeMass(W.Amount);
436 if (W.Type == Weight::Local) {
437 Working[W.TargetNode.Index].getMass() += Taken;
438 DEBUG(debugAssign(*this, D, W.TargetNode, Taken, nullptr));
442 // Backedges and exits only make sense if we're processing a loop.
443 assert(OuterLoop && "backedge or exit outside of loop");
445 // Check for a backedge.
446 if (W.Type == Weight::Backedge) {
447 OuterLoop->BackedgeMass[OuterLoop->getHeaderIndex(W.TargetNode)] += Taken;
448 DEBUG(debugAssign(*this, D, W.TargetNode, Taken, "back"));
452 // This must be an exit.
453 assert(W.Type == Weight::Exit);
454 OuterLoop->Exits.push_back(std::make_pair(W.TargetNode, Taken));
455 DEBUG(debugAssign(*this, D, W.TargetNode, Taken, "exit"));
459 static void convertFloatingToInteger(BlockFrequencyInfoImplBase &BFI,
460 const Scaled64 &Min, const Scaled64 &Max) {
461 // Scale the Factor to a size that creates integers. Ideally, integers would
462 // be scaled so that Max == UINT64_MAX so that they can be best
463 // differentiated. However, in the presence of large frequency values, small
464 // frequencies are scaled down to 1, making it impossible to differentiate
465 // small, unequal numbers. When the spread between Min and Max frequencies
466 // fits well within MaxBits, we make the scale be at least 8.
467 const unsigned MaxBits = 64;
468 const unsigned SpreadBits = (Max / Min).lg();
469 Scaled64 ScalingFactor;
470 if (SpreadBits <= MaxBits - 3) {
471 // If the values are small enough, make the scaling factor at least 8 to
472 // allow distinguishing small values.
473 ScalingFactor = Min.inverse();
476 // If the values need more than MaxBits to be represented, saturate small
477 // frequency values down to 1 by using a scaling factor that benefits large
479 ScalingFactor = Scaled64(1, MaxBits) / Max;
482 // Translate the floats to integers.
483 DEBUG(dbgs() << "float-to-int: min = " << Min << ", max = " << Max
484 << ", factor = " << ScalingFactor << "\n");
485 for (size_t Index = 0; Index < BFI.Freqs.size(); ++Index) {
486 Scaled64 Scaled = BFI.Freqs[Index].Scaled * ScalingFactor;
487 BFI.Freqs[Index].Integer = std::max(UINT64_C(1), Scaled.toInt<uint64_t>());
488 DEBUG(dbgs() << " - " << BFI.getBlockName(Index) << ": float = "
489 << BFI.Freqs[Index].Scaled << ", scaled = " << Scaled
490 << ", int = " << BFI.Freqs[Index].Integer << "\n");
494 /// \brief Unwrap a loop package.
496 /// Visits all the members of a loop, adjusting their BlockData according to
497 /// the loop's pseudo-node.
498 static void unwrapLoop(BlockFrequencyInfoImplBase &BFI, LoopData &Loop) {
499 DEBUG(dbgs() << "unwrap-loop-package: " << BFI.getLoopName(Loop)
500 << ": mass = " << Loop.Mass << ", scale = " << Loop.Scale
502 Loop.Scale *= Loop.Mass.toScaled();
503 Loop.IsPackaged = false;
504 DEBUG(dbgs() << " => combined-scale = " << Loop.Scale << "\n");
506 // Propagate the head scale through the loop. Since members are visited in
507 // RPO, the head scale will be updated by the loop scale first, and then the
508 // final head scale will be used for updated the rest of the members.
509 for (const BlockNode &N : Loop.Nodes) {
510 const auto &Working = BFI.Working[N.Index];
511 Scaled64 &F = Working.isAPackage() ? Working.getPackagedLoop()->Scale
512 : BFI.Freqs[N.Index].Scaled;
513 Scaled64 New = Loop.Scale * F;
514 DEBUG(dbgs() << " - " << BFI.getBlockName(N) << ": " << F << " => " << New
520 void BlockFrequencyInfoImplBase::unwrapLoops() {
521 // Set initial frequencies from loop-local masses.
522 for (size_t Index = 0; Index < Working.size(); ++Index)
523 Freqs[Index].Scaled = Working[Index].Mass.toScaled();
525 for (LoopData &Loop : Loops)
526 unwrapLoop(*this, Loop);
529 void BlockFrequencyInfoImplBase::finalizeMetrics() {
530 // Unwrap loop packages in reverse post-order, tracking min and max
532 auto Min = Scaled64::getLargest();
533 auto Max = Scaled64::getZero();
534 for (size_t Index = 0; Index < Working.size(); ++Index) {
535 // Update min/max scale.
536 Min = std::min(Min, Freqs[Index].Scaled);
537 Max = std::max(Max, Freqs[Index].Scaled);
540 // Convert to integers.
541 convertFloatingToInteger(*this, Min, Max);
543 // Clean up data structures.
546 // Print out the final stats.
551 BlockFrequencyInfoImplBase::getBlockFreq(const BlockNode &Node) const {
554 return Freqs[Node.Index].Integer;
558 BlockFrequencyInfoImplBase::getBlockProfileCount(const Function &F,
559 const BlockNode &Node) const {
560 return getProfileCountFromFreq(F, getBlockFreq(Node).getFrequency());
564 BlockFrequencyInfoImplBase::getProfileCountFromFreq(const Function &F,
565 uint64_t Freq) const {
566 auto EntryCount = F.getEntryCount();
569 // Use 128 bit APInt to do the arithmetic to avoid overflow.
570 APInt BlockCount(128, EntryCount.getValue());
571 APInt BlockFreq(128, Freq);
572 APInt EntryFreq(128, getEntryFreq());
573 BlockCount *= BlockFreq;
574 BlockCount = BlockCount.udiv(EntryFreq);
575 return BlockCount.getLimitedValue();
579 BlockFrequencyInfoImplBase::isIrrLoopHeader(const BlockNode &Node) {
582 return IsIrrLoopHeader.test(Node.Index);
586 BlockFrequencyInfoImplBase::getFloatingBlockFreq(const BlockNode &Node) const {
588 return Scaled64::getZero();
589 return Freqs[Node.Index].Scaled;
592 void BlockFrequencyInfoImplBase::setBlockFreq(const BlockNode &Node,
594 assert(Node.isValid() && "Expected valid node");
595 assert(Node.Index < Freqs.size() && "Expected legal index");
596 Freqs[Node.Index].Integer = Freq;
600 BlockFrequencyInfoImplBase::getBlockName(const BlockNode &Node) const {
605 BlockFrequencyInfoImplBase::getLoopName(const LoopData &Loop) const {
606 return getBlockName(Loop.getHeader()) + (Loop.isIrreducible() ? "**" : "*");
610 BlockFrequencyInfoImplBase::printBlockFreq(raw_ostream &OS,
611 const BlockNode &Node) const {
612 return OS << getFloatingBlockFreq(Node);
616 BlockFrequencyInfoImplBase::printBlockFreq(raw_ostream &OS,
617 const BlockFrequency &Freq) const {
618 Scaled64 Block(Freq.getFrequency(), 0);
619 Scaled64 Entry(getEntryFreq(), 0);
621 return OS << Block / Entry;
624 void IrreducibleGraph::addNodesInLoop(const BFIBase::LoopData &OuterLoop) {
625 Start = OuterLoop.getHeader();
626 Nodes.reserve(OuterLoop.Nodes.size());
627 for (auto N : OuterLoop.Nodes)
632 void IrreducibleGraph::addNodesInFunction() {
634 for (uint32_t Index = 0; Index < BFI.Working.size(); ++Index)
635 if (!BFI.Working[Index].isPackaged())
640 void IrreducibleGraph::indexNodes() {
641 for (auto &I : Nodes)
642 Lookup[I.Node.Index] = &I;
645 void IrreducibleGraph::addEdge(IrrNode &Irr, const BlockNode &Succ,
646 const BFIBase::LoopData *OuterLoop) {
647 if (OuterLoop && OuterLoop->isHeader(Succ))
649 auto L = Lookup.find(Succ.Index);
650 if (L == Lookup.end())
652 IrrNode &SuccIrr = *L->second;
653 Irr.Edges.push_back(&SuccIrr);
654 SuccIrr.Edges.push_front(&Irr);
660 template <> struct GraphTraits<IrreducibleGraph> {
661 using GraphT = bfi_detail::IrreducibleGraph;
662 using NodeRef = const GraphT::IrrNode *;
663 using ChildIteratorType = GraphT::IrrNode::iterator;
665 static NodeRef getEntryNode(const GraphT &G) { return G.StartIrr; }
666 static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
667 static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
670 } // end namespace llvm
672 /// \brief Find extra irreducible headers.
674 /// Find entry blocks and other blocks with backedges, which exist when \c G
675 /// contains irreducible sub-SCCs.
676 static void findIrreducibleHeaders(
677 const BlockFrequencyInfoImplBase &BFI,
678 const IrreducibleGraph &G,
679 const std::vector<const IrreducibleGraph::IrrNode *> &SCC,
680 LoopData::NodeList &Headers, LoopData::NodeList &Others) {
681 // Map from nodes in the SCC to whether it's an entry block.
682 SmallDenseMap<const IrreducibleGraph::IrrNode *, bool, 8> InSCC;
684 // InSCC also acts the set of nodes in the graph. Seed it.
685 for (const auto *I : SCC)
688 for (auto I = InSCC.begin(), E = InSCC.end(); I != E; ++I) {
689 auto &Irr = *I->first;
690 for (const auto *P : make_range(Irr.pred_begin(), Irr.pred_end())) {
694 // This is an entry block.
696 Headers.push_back(Irr.Node);
697 DEBUG(dbgs() << " => entry = " << BFI.getBlockName(Irr.Node) << "\n");
701 assert(Headers.size() >= 2 &&
702 "Expected irreducible CFG; -loop-info is likely invalid");
703 if (Headers.size() == InSCC.size()) {
704 // Every block is a header.
705 std::sort(Headers.begin(), Headers.end());
709 // Look for extra headers from irreducible sub-SCCs.
710 for (const auto &I : InSCC) {
711 // Entry blocks are already headers.
715 auto &Irr = *I.first;
716 for (const auto *P : make_range(Irr.pred_begin(), Irr.pred_end())) {
717 // Skip forward edges.
718 if (P->Node < Irr.Node)
721 // Skip predecessors from entry blocks. These can have inverted
726 // Store the extra header.
727 Headers.push_back(Irr.Node);
728 DEBUG(dbgs() << " => extra = " << BFI.getBlockName(Irr.Node) << "\n");
731 if (Headers.back() == Irr.Node)
732 // Added this as a header.
735 // This is not a header.
736 Others.push_back(Irr.Node);
737 DEBUG(dbgs() << " => other = " << BFI.getBlockName(Irr.Node) << "\n");
739 std::sort(Headers.begin(), Headers.end());
740 std::sort(Others.begin(), Others.end());
743 static void createIrreducibleLoop(
744 BlockFrequencyInfoImplBase &BFI, const IrreducibleGraph &G,
745 LoopData *OuterLoop, std::list<LoopData>::iterator Insert,
746 const std::vector<const IrreducibleGraph::IrrNode *> &SCC) {
747 // Translate the SCC into RPO.
748 DEBUG(dbgs() << " - found-scc\n");
750 LoopData::NodeList Headers;
751 LoopData::NodeList Others;
752 findIrreducibleHeaders(BFI, G, SCC, Headers, Others);
754 auto Loop = BFI.Loops.emplace(Insert, OuterLoop, Headers.begin(),
755 Headers.end(), Others.begin(), Others.end());
757 // Update loop hierarchy.
758 for (const auto &N : Loop->Nodes)
759 if (BFI.Working[N.Index].isLoopHeader())
760 BFI.Working[N.Index].Loop->Parent = &*Loop;
762 BFI.Working[N.Index].Loop = &*Loop;
765 iterator_range<std::list<LoopData>::iterator>
766 BlockFrequencyInfoImplBase::analyzeIrreducible(
767 const IrreducibleGraph &G, LoopData *OuterLoop,
768 std::list<LoopData>::iterator Insert) {
769 assert((OuterLoop == nullptr) == (Insert == Loops.begin()));
770 auto Prev = OuterLoop ? std::prev(Insert) : Loops.end();
772 for (auto I = scc_begin(G); !I.isAtEnd(); ++I) {
776 // Translate the SCC into RPO.
777 createIrreducibleLoop(*this, G, OuterLoop, Insert, *I);
781 return make_range(std::next(Prev), Insert);
782 return make_range(Loops.begin(), Insert);
786 BlockFrequencyInfoImplBase::updateLoopWithIrreducible(LoopData &OuterLoop) {
787 OuterLoop.Exits.clear();
788 for (auto &Mass : OuterLoop.BackedgeMass)
789 Mass = BlockMass::getEmpty();
790 auto O = OuterLoop.Nodes.begin() + 1;
791 for (auto I = O, E = OuterLoop.Nodes.end(); I != E; ++I)
792 if (!Working[I->Index].isPackaged())
794 OuterLoop.Nodes.erase(O, OuterLoop.Nodes.end());
797 void BlockFrequencyInfoImplBase::adjustLoopHeaderMass(LoopData &Loop) {
798 assert(Loop.isIrreducible() && "this only makes sense on irreducible loops");
800 // Since the loop has more than one header block, the mass flowing back into
801 // each header will be different. Adjust the mass in each header loop to
802 // reflect the masses flowing through back edges.
804 // To do this, we distribute the initial mass using the backedge masses
805 // as weights for the distribution.
806 BlockMass LoopMass = BlockMass::getFull();
809 DEBUG(dbgs() << "adjust-loop-header-mass:\n");
810 for (uint32_t H = 0; H < Loop.NumHeaders; ++H) {
811 auto &HeaderNode = Loop.Nodes[H];
812 auto &BackedgeMass = Loop.BackedgeMass[Loop.getHeaderIndex(HeaderNode)];
813 DEBUG(dbgs() << " - Add back edge mass for node "
814 << getBlockName(HeaderNode) << ": " << BackedgeMass << "\n");
815 if (BackedgeMass.getMass() > 0)
816 Dist.addLocal(HeaderNode, BackedgeMass.getMass());
818 DEBUG(dbgs() << " Nothing added. Back edge mass is zero\n");
821 DitheringDistributer D(Dist, LoopMass);
823 DEBUG(dbgs() << " Distribute loop mass " << LoopMass
824 << " to headers using above weights\n");
825 for (const Weight &W : Dist.Weights) {
826 BlockMass Taken = D.takeMass(W.Amount);
827 assert(W.Type == Weight::Local && "all weights should be local");
828 Working[W.TargetNode.Index].getMass() = Taken;
829 DEBUG(debugAssign(*this, D, W.TargetNode, Taken, nullptr));
833 void BlockFrequencyInfoImplBase::distributeIrrLoopHeaderMass(Distribution &Dist) {
834 BlockMass LoopMass = BlockMass::getFull();
835 DitheringDistributer D(Dist, LoopMass);
836 for (const Weight &W : Dist.Weights) {
837 BlockMass Taken = D.takeMass(W.Amount);
838 assert(W.Type == Weight::Local && "all weights should be local");
839 Working[W.TargetNode.Index].getMass() = Taken;
840 DEBUG(debugAssign(*this, D, W.TargetNode, Taken, nullptr));