1dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===- BlockFrequencyImplInfo.cpp - Block Frequency Info Implementation ---===// 2dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 3dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// The LLVM Compiler Infrastructure 4dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 5dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// This file is distributed under the University of Illinois Open Source 6dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// License. See LICENSE.TXT for details. 7dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 8dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 9dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 10dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// Loops should be simplified before this analysis. 11dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 12dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 13dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 14dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Analysis/BlockFrequencyInfoImpl.h" 15dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/ADT/SCCIterator.h" 16dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Support/raw_ostream.h" 17dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include <deque> 18dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 19dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesusing namespace llvm; 20dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesusing namespace llvm::bfi_detail; 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 22dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "block-freq" 23dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 24dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 25dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 26dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// BlockMass implementation. 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 29cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesScaledNumber<uint64_t> BlockMass::toScaled() const { 30dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (isFull()) 31cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return ScaledNumber<uint64_t>(1, 0); 32cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return ScaledNumber<uint64_t>(getMass() + 1, -64); 33dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid BlockMass::dump() const { print(dbgs()); } 36dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic char getHexDigit(int N) { 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(N < 16); 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (N < 10) 40dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return '0' + N; 41dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return 'a' + N - 10; 42dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 43dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesraw_ostream &BlockMass::print(raw_ostream &OS) const { 44dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (int Digits = 0; Digits < 16; ++Digits) 45dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines OS << getHexDigit(Mass >> (60 - Digits * 4) & 0xf); 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return OS; 47dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 48dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// BlockFrequencyInfoImpl implementation. 52dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines// 53dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===----------------------------------------------------------------------===// 54dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesnamespace { 55dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 56dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestypedef BlockFrequencyInfoImplBase::BlockNode BlockNode; 57dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestypedef BlockFrequencyInfoImplBase::Distribution Distribution; 58dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestypedef BlockFrequencyInfoImplBase::Distribution::WeightList WeightList; 59cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinestypedef BlockFrequencyInfoImplBase::Scaled64 Scaled64; 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestypedef BlockFrequencyInfoImplBase::LoopData LoopData; 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestypedef BlockFrequencyInfoImplBase::Weight Weight; 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestypedef BlockFrequencyInfoImplBase::FrequencyData FrequencyData; 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 64dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Dithering mass distributer. 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// This class splits up a single mass into portions by weight, dithering to 67dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// spread out error. No mass is lost. The dithering precision depends on the 68dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// precision of the product of \a BlockMass and \a BranchProbability. 69dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 70dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// The distribution algorithm follows. 71dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 72dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 1. Initialize by saving the sum of the weights in \a RemWeight and the 73dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// mass to distribute in \a RemMass. 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 75dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 2. For each portion: 76dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 77dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 1. Construct a branch probability, P, as the portion's weight divided 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// by the current value of \a RemWeight. 79dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 2. Calculate the portion's mass as \a RemMass times P. 80dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 3. Update \a RemWeight and \a RemMass at each portion by subtracting 81dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// the current portion's weight and mass. 82dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstruct DitheringDistributer { 83dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint32_t RemWeight; 84dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockMass RemMass; 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 86dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DitheringDistributer(Distribution &Dist, const BlockMass &Mass); 87dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 88dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockMass takeMass(uint32_t Weight); 89dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines}; 90dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 91dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 92dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesDitheringDistributer::DitheringDistributer(Distribution &Dist, 93dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BlockMass &Mass) { 94dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Dist.normalize(); 95dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RemWeight = Dist.Total; 96dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RemMass = Mass; 97dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 99dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockMass DitheringDistributer::takeMass(uint32_t Weight) { 100dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Weight && "invalid weight"); 101dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Weight <= RemWeight); 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockMass Mass = RemMass * BranchProbability(Weight, RemWeight); 103dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 104dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Decrement totals (dither). 105dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RemWeight -= Weight; 106dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RemMass -= Mass; 107dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Mass; 108dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 109dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 110dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid Distribution::add(const BlockNode &Node, uint64_t Amount, 111dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weight::DistType Type) { 112dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Amount && "invalid weight of 0"); 113dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint64_t NewTotal = Total + Amount; 114dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 115dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Check for overflow. It should be impossible to overflow twice. 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool IsOverflow = NewTotal < Total; 117dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(!(DidOverflow && IsOverflow) && "unexpected repeated overflow"); 118dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DidOverflow |= IsOverflow; 119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Update the total. 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Total = NewTotal; 122dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 123dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Save the weight. 124dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weight W; 125dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines W.TargetNode = Node; 126dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines W.Amount = Amount; 127dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines W.Type = Type; 128dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weights.push_back(W); 129dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 130dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 131dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void combineWeight(Weight &W, const Weight &OtherW) { 132dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(OtherW.TargetNode.isValid()); 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!W.Amount) { 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines W = OtherW; 135dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 137dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(W.Type == OtherW.Type); 138dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(W.TargetNode == OtherW.TargetNode); 139dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(W.Amount < W.Amount + OtherW.Amount && "Unexpected overflow"); 140dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines W.Amount += OtherW.Amount; 141dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void combineWeightsBySorting(WeightList &Weights) { 143dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Sort so edges to the same node are adjacent. 144dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Weights.begin(), Weights.end(), 145dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines [](const Weight &L, 146dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const Weight &R) { return L.TargetNode < R.TargetNode; }); 147dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 148dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Combine adjacent edges. 149dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines WeightList::iterator O = Weights.begin(); 150dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (WeightList::const_iterator I = O, L = O, E = Weights.end(); I != E; 151dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++O, (I = L)) { 152dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines *O = *I; 153dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 154dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Find the adjacent weights to the same node. 155dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (++L; L != E && I->TargetNode == L->TargetNode; ++L) 156dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines combineWeight(*O, *L); 157dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 159dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Erase extra entries. 160dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weights.erase(O, Weights.end()); 161dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 162dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void combineWeightsByHashing(WeightList &Weights) { 164dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Collect weights into a DenseMap. 165dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef DenseMap<BlockNode::IndexType, Weight> HashTable; 166dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines HashTable Combined(NextPowerOf2(2 * Weights.size())); 167dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const Weight &W : Weights) 168dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines combineWeight(Combined[W.TargetNode.Index], W); 169dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 170dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Check whether anything changed. 171dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Weights.size() == Combined.size()) 172dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 174dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Fill in the new weights. 175dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weights.clear(); 176dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weights.reserve(Combined.size()); 177dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &I : Combined) 178dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weights.push_back(I.second); 179dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 180dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void combineWeights(WeightList &Weights) { 181dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Use a hash table for many successors to keep this linear. 182dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Weights.size() > 128) { 183dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines combineWeightsByHashing(Weights); 184dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 185dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 186dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 187dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines combineWeightsBySorting(Weights); 188dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 189dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic uint64_t shiftRightAndRound(uint64_t N, int Shift) { 190dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Shift >= 0); 191dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Shift < 64); 192dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Shift) 193dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return N; 194dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return (N >> Shift) + (UINT64_C(1) & N >> (Shift - 1)); 195dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 196dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid Distribution::normalize() { 197dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Early exit for termination nodes. 198dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Weights.empty()) 199dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 200dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 201dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Only bother if there are multiple successors. 202dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Weights.size() > 1) 203dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines combineWeights(Weights); 204dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 205dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Early exit when combined into a single successor. 206dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Weights.size() == 1) { 207dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Total = 1; 208dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weights.front().Amount = 1; 209dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 210dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 211dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 212dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Determine how much to shift right so that the total fits into 32-bits. 213dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // 214dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If we shift at all, shift by 1 extra. Otherwise, the lower limit of 1 215dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // for each weight can cause a 32-bit overflow. 216dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines int Shift = 0; 217dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (DidOverflow) 218dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Shift = 33; 219dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines else if (Total > UINT32_MAX) 220dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Shift = 33 - countLeadingZeros(Total); 221dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 222dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Early exit if nothing needs to be scaled. 223dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Shift) 224dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 225dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 226dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Recompute the total through accumulation (rather than shifting it) so that 227dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // it's accurate after shifting. 228dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Total = 0; 229dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 230dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Sum the weights to each node and shift right if necessary. 231dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (Weight &W : Weights) { 232dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Scale down below UINT32_MAX. Since Shift is larger than necessary, we 233dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // can round here without concern about overflow. 234dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(W.TargetNode.isValid()); 235dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines W.Amount = std::max(UINT64_C(1), shiftRightAndRound(W.Amount, Shift)); 236dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(W.Amount <= UINT32_MAX); 237dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 238dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Update the total. 239dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Total += W.Amount; 240dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 241dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Total <= UINT32_MAX); 242dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 243dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid BlockFrequencyInfoImplBase::clear() { 245dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Swap with a default-constructed std::vector, since std::vector<>::clear() 246dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // does not actually clear heap storage. 247dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::vector<FrequencyData>().swap(Freqs); 248dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::vector<WorkingData>().swap(Working); 249dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Loops.clear(); 250dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 251dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 252dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Clear all memory not needed downstream. 253dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 254dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Releases all memory not used downstream. In particular, saves Freqs. 255dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void cleanup(BlockFrequencyInfoImplBase &BFI) { 256dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::vector<FrequencyData> SavedFreqs(std::move(BFI.Freqs)); 257dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BFI.clear(); 258dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BFI.Freqs = std::move(SavedFreqs); 259dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 260dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 261dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool BlockFrequencyInfoImplBase::addToDist(Distribution &Dist, 262dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const LoopData *OuterLoop, 263dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BlockNode &Pred, 264dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BlockNode &Succ, 265dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines uint64_t Weight) { 266dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Weight) 267dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Weight = 1; 268dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 269dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto isLoopHeader = [&OuterLoop](const BlockNode &Node) { 270dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return OuterLoop && OuterLoop->isHeader(Node); 271dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines }; 272dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 273dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockNode Resolved = Working[Succ.Index].getResolvedNode(); 274dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 275dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#ifndef NDEBUG 276dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto debugSuccessor = [&](const char *Type) { 277dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << " =>" 278dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << " [" << Type << "] weight = " << Weight; 279dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!isLoopHeader(Resolved)) 280dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << ", succ = " << getBlockName(Succ); 281dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Resolved != Succ) 282dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << ", resolved = " << getBlockName(Resolved); 283dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << "\n"; 284dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines }; 285dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (void)debugSuccessor; 286dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#endif 287dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 288dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (isLoopHeader(Resolved)) { 289dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(debugSuccessor("backedge")); 290dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Dist.addBackedge(OuterLoop->getHeader(), Weight); 291dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return true; 292dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 293dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 294dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Working[Resolved.Index].getContainingLoop() != OuterLoop) { 295dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(debugSuccessor(" exit ")); 296dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Dist.addExit(Resolved, Weight); 297dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return true; 298dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 299dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 300dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Resolved < Pred) { 301dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!isLoopHeader(Pred)) { 302dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If OuterLoop is an irreducible loop, we can't actually handle this. 303dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert((!OuterLoop || !OuterLoop->isIrreducible()) && 304dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "unhandled irreducible control flow"); 305dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 306dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Irreducible backedge. Abort. 307dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(debugSuccessor("abort!!!")); 308dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 309dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 310dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 311dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If "Pred" is a loop header, then this isn't really a backedge; rather, 312dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // OuterLoop must be irreducible. These false backedges can come only from 313dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // secondary loop headers. 314dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(OuterLoop && OuterLoop->isIrreducible() && !isLoopHeader(Resolved) && 315dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines "unhandled irreducible control flow"); 316dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 317dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 318dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(debugSuccessor(" local ")); 319dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Dist.addLocal(Resolved, Weight); 320dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return true; 321dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 322dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 323dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool BlockFrequencyInfoImplBase::addLoopSuccessorsToDist( 324dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist) { 325dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Copy the exit map into Dist. 326dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &I : Loop.Exits) 327dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!addToDist(Dist, OuterLoop, Loop.getHeader(), I.first, 328dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines I.second.getMass())) 329dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Irreducible backedge. 330dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 331dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 332dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return true; 333dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 334dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 335dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Get the maximum allowed loop scale. 336dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 337dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Gives the maximum number of estimated iterations allowed for a loop. Very 338dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// large numbers cause problems downstream (even within 64-bits). 339cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesstatic Scaled64 getMaxLoopScale() { return Scaled64(1, 12); } 340dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 341dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Compute the loop scale for a loop. 342dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid BlockFrequencyInfoImplBase::computeLoopScale(LoopData &Loop) { 343dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Compute loop scale. 344dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << "compute-loop-scale: " << getLoopName(Loop) << "\n"); 345dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 346dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // LoopScale == 1 / ExitMass 347dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // ExitMass == HeadMass - BackedgeMass 348dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockMass ExitMass = BlockMass::getFull() - Loop.BackedgeMass; 349dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 350dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Block scale stores the inverse of the scale. 351cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Loop.Scale = ExitMass.toScaled().inverse(); 352dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 353dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " - exit-mass = " << ExitMass << " (" << BlockMass::getFull() 354dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << " - " << Loop.BackedgeMass << ")\n" 355dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << " - scale = " << Loop.Scale << "\n"); 356dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 357dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Loop.Scale > getMaxLoopScale()) { 358dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Loop.Scale = getMaxLoopScale(); 359dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " - reduced-to-max-scale: " << getMaxLoopScale() << "\n"); 360dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 361dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 362dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 363dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Package up a loop. 364dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid BlockFrequencyInfoImplBase::packageLoop(LoopData &Loop) { 365dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << "packaging-loop: " << getLoopName(Loop) << "\n"); 366dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 367dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Clear the subloop exits to prevent quadratic memory usage. 368dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const BlockNode &M : Loop.Nodes) { 369dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (auto *Loop = Working[M.Index].getPackagedLoop()) 370dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Loop->Exits.clear(); 371dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " - node: " << getBlockName(M.Index) << "\n"); 372dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 373dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Loop.IsPackaged = true; 374dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 375dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 376dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid BlockFrequencyInfoImplBase::distributeMass(const BlockNode &Source, 377dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LoopData *OuterLoop, 378dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Distribution &Dist) { 379dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockMass Mass = Working[Source.Index].getMass(); 380dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " => mass: " << Mass << "\n"); 381dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 382dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Distribute mass to successors as laid out in Dist. 383dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DitheringDistributer D(Dist, Mass); 384dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 385dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#ifndef NDEBUG 386dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto debugAssign = [&](const BlockNode &T, const BlockMass &M, 387dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const char *Desc) { 388dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << " => assign " << M << " (" << D.RemMass << ")"; 389dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Desc) 390dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << " [" << Desc << "]"; 391dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (T.isValid()) 392dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << " to " << getBlockName(T); 393dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines dbgs() << "\n"; 394dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines }; 395dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines (void)debugAssign; 396dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#endif 397dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 398dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const Weight &W : Dist.Weights) { 399dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Check for a local edge (non-backedge and non-exit). 400dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockMass Taken = D.takeMass(W.Amount); 401dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (W.Type == Weight::Local) { 402dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Working[W.TargetNode.Index].getMass() += Taken; 403dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(debugAssign(W.TargetNode, Taken, nullptr)); 404dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 405dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 406dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 407dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Backedges and exits only make sense if we're processing a loop. 408dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(OuterLoop && "backedge or exit outside of loop"); 409dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 410dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Check for a backedge. 411dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (W.Type == Weight::Backedge) { 412dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines OuterLoop->BackedgeMass += Taken; 413dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(debugAssign(BlockNode(), Taken, "back")); 414dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 415dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 416dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 417dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // This must be an exit. 418dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(W.Type == Weight::Exit); 419dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines OuterLoop->Exits.push_back(std::make_pair(W.TargetNode, Taken)); 420dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(debugAssign(W.TargetNode, Taken, "exit")); 421dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 422dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 423dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 424dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void convertFloatingToInteger(BlockFrequencyInfoImplBase &BFI, 425cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const Scaled64 &Min, const Scaled64 &Max) { 426dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Scale the Factor to a size that creates integers. Ideally, integers would 427dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // be scaled so that Max == UINT64_MAX so that they can be best 428dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // differentiated. However, the register allocator currently deals poorly 429dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // with large numbers. Instead, push Min up a little from 1 to give some 430dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // room to differentiate small, unequal numbers. 431dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // 432cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // TODO: fix issues downstream so that ScalingFactor can be 433cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Scaled64(1,64)/Max. 434cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Scaled64 ScalingFactor = Min.inverse(); 435dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if ((Max / Min).lg() < 60) 436dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ScalingFactor <<= 3; 437dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Translate the floats to integers. 439dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << "float-to-int: min = " << Min << ", max = " << Max 440dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << ", factor = " << ScalingFactor << "\n"); 441dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (size_t Index = 0; Index < BFI.Freqs.size(); ++Index) { 442cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Scaled64 Scaled = BFI.Freqs[Index].Scaled * ScalingFactor; 443dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BFI.Freqs[Index].Integer = std::max(UINT64_C(1), Scaled.toInt<uint64_t>()); 444dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " - " << BFI.getBlockName(Index) << ": float = " 445cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines << BFI.Freqs[Index].Scaled << ", scaled = " << Scaled 446dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << ", int = " << BFI.Freqs[Index].Integer << "\n"); 447dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 448dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 449dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 450dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Unwrap a loop package. 451dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 452dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Visits all the members of a loop, adjusting their BlockData according to 453dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// the loop's pseudo-node. 454dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void unwrapLoop(BlockFrequencyInfoImplBase &BFI, LoopData &Loop) { 455dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << "unwrap-loop-package: " << BFI.getLoopName(Loop) 456dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << ": mass = " << Loop.Mass << ", scale = " << Loop.Scale 457dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << "\n"); 458cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Loop.Scale *= Loop.Mass.toScaled(); 459dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Loop.IsPackaged = false; 460dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " => combined-scale = " << Loop.Scale << "\n"); 461dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 462dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Propagate the head scale through the loop. Since members are visited in 463dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // RPO, the head scale will be updated by the loop scale first, and then the 464dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // final head scale will be used for updated the rest of the members. 465dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const BlockNode &N : Loop.Nodes) { 466dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const auto &Working = BFI.Working[N.Index]; 467cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Scaled64 &F = Working.isAPackage() ? Working.getPackagedLoop()->Scale 468cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : BFI.Freqs[N.Index].Scaled; 469cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Scaled64 New = Loop.Scale * F; 470dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " - " << BFI.getBlockName(N) << ": " << F << " => " << New 471dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines << "\n"); 472dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines F = New; 473dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 474dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 475dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 476dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid BlockFrequencyInfoImplBase::unwrapLoops() { 477dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Set initial frequencies from loop-local masses. 478dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (size_t Index = 0; Index < Working.size(); ++Index) 479cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Freqs[Index].Scaled = Working[Index].Mass.toScaled(); 480dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 481dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (LoopData &Loop : Loops) 482dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines unwrapLoop(*this, Loop); 483dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 484dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 485dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid BlockFrequencyInfoImplBase::finalizeMetrics() { 486dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Unwrap loop packages in reverse post-order, tracking min and max 487dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // frequencies. 488cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines auto Min = Scaled64::getLargest(); 489cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines auto Max = Scaled64::getZero(); 490dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (size_t Index = 0; Index < Working.size(); ++Index) { 491dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Update min/max scale. 492cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Min = std::min(Min, Freqs[Index].Scaled); 493cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Max = std::max(Max, Freqs[Index].Scaled); 494dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 495dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 496dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Convert to integers. 497dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines convertFloatingToInteger(*this, Min, Max); 498dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 499dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Clean up data structures. 500dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines cleanup(*this); 501dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 502dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Print out the final stats. 503dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dump()); 504dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 505dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 506dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequency 507dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequencyInfoImplBase::getBlockFreq(const BlockNode &Node) const { 508dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Node.isValid()) 509dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return 0; 510dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return Freqs[Node.Index].Integer; 511dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 512cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesScaled64 513dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequencyInfoImplBase::getFloatingBlockFreq(const BlockNode &Node) const { 514dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Node.isValid()) 515cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Scaled64::getZero(); 516cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Freqs[Node.Index].Scaled; 517dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 518dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 519dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstd::string 520dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequencyInfoImplBase::getBlockName(const BlockNode &Node) const { 521dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return std::string(); 522dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 523dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstd::string 524dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequencyInfoImplBase::getLoopName(const LoopData &Loop) const { 525dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return getBlockName(Loop.getHeader()) + (Loop.isIrreducible() ? "**" : "*"); 526dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 527dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 528dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesraw_ostream & 529dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequencyInfoImplBase::printBlockFreq(raw_ostream &OS, 530dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BlockNode &Node) const { 531dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return OS << getFloatingBlockFreq(Node); 532dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 533dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 534dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesraw_ostream & 535dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequencyInfoImplBase::printBlockFreq(raw_ostream &OS, 536dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BlockFrequency &Freq) const { 537cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Scaled64 Block(Freq.getFrequency(), 0); 538cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Scaled64 Entry(getEntryFreq(), 0); 539dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 540dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return OS << Block / Entry; 541dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 542dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 543dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid IrreducibleGraph::addNodesInLoop(const BFIBase::LoopData &OuterLoop) { 544dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Start = OuterLoop.getHeader(); 545dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Nodes.reserve(OuterLoop.Nodes.size()); 546dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto N : OuterLoop.Nodes) 547dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines addNode(N); 548dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines indexNodes(); 549dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 550dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid IrreducibleGraph::addNodesInFunction() { 551dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Start = 0; 552dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (uint32_t Index = 0; Index < BFI.Working.size(); ++Index) 553dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!BFI.Working[Index].isPackaged()) 554dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines addNode(Index); 555dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines indexNodes(); 556dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 557dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid IrreducibleGraph::indexNodes() { 558dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto &I : Nodes) 559dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Lookup[I.Node.Index] = &I; 560dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 561dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid IrreducibleGraph::addEdge(IrrNode &Irr, const BlockNode &Succ, 562dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BFIBase::LoopData *OuterLoop) { 563dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (OuterLoop && OuterLoop->isHeader(Succ)) 564dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 565dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto L = Lookup.find(Succ.Index); 566dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (L == Lookup.end()) 567dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 568dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IrrNode &SuccIrr = *L->second; 569dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Irr.Edges.push_back(&SuccIrr); 570dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SuccIrr.Edges.push_front(&Irr); 571dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ++SuccIrr.NumIn; 572dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 573dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 574dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesnamespace llvm { 575dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinestemplate <> struct GraphTraits<IrreducibleGraph> { 576dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef bfi_detail::IrreducibleGraph GraphT; 577dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 578dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef const GraphT::IrrNode NodeType; 579dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef GraphT::IrrNode::iterator ChildIteratorType; 580dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 581dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static const NodeType *getEntryNode(const GraphT &G) { 582dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return G.StartIrr; 583dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 584dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static ChildIteratorType child_begin(NodeType *N) { return N->succ_begin(); } 585dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines static ChildIteratorType child_end(NodeType *N) { return N->succ_end(); } 586dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines}; 587dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 588dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 589dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// \brief Find extra irreducible headers. 590dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// 591dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Find entry blocks and other blocks with backedges, which exist when \c G 592dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// contains irreducible sub-SCCs. 593dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void findIrreducibleHeaders( 594dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const BlockFrequencyInfoImplBase &BFI, 595dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const IrreducibleGraph &G, 596dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const std::vector<const IrreducibleGraph::IrrNode *> &SCC, 597dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LoopData::NodeList &Headers, LoopData::NodeList &Others) { 598dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Map from nodes in the SCC to whether it's an entry block. 599dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallDenseMap<const IrreducibleGraph::IrrNode *, bool, 8> InSCC; 600dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 601dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // InSCC also acts the set of nodes in the graph. Seed it. 602dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto *I : SCC) 603dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines InSCC[I] = false; 604dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 605dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto I = InSCC.begin(), E = InSCC.end(); I != E; ++I) { 606dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto &Irr = *I->first; 607dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto *P : make_range(Irr.pred_begin(), Irr.pred_end())) { 608dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (InSCC.count(P)) 609dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 610dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 611dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // This is an entry block. 612dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines I->second = true; 613dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Headers.push_back(Irr.Node); 614dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " => entry = " << BFI.getBlockName(Irr.Node) << "\n"); 615dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 616dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 617dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 618dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(Headers.size() >= 2 && "Should be irreducible"); 619dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Headers.size() == InSCC.size()) { 620dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Every block is a header. 621dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Headers.begin(), Headers.end()); 622dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return; 623dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 624dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 625dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Look for extra headers from irreducible sub-SCCs. 626dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &I : InSCC) { 627dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Entry blocks are already headers. 628dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (I.second) 629dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 630dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 631dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto &Irr = *I.first; 632dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto *P : make_range(Irr.pred_begin(), Irr.pred_end())) { 633dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Skip forward edges. 634dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (P->Node < Irr.Node) 635dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 636dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 637dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Skip predecessors from entry blocks. These can have inverted 638dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // ordering. 639dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (InSCC.lookup(P)) 640dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 641dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 642dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Store the extra header. 643dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Headers.push_back(Irr.Node); 644dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " => extra = " << BFI.getBlockName(Irr.Node) << "\n"); 645dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 646dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 647dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Headers.back() == Irr.Node) 648dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Added this as a header. 649dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 650dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 651dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // This is not a header. 652dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Others.push_back(Irr.Node); 653dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " => other = " << BFI.getBlockName(Irr.Node) << "\n"); 654dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 655dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Headers.begin(), Headers.end()); 656dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::sort(Others.begin(), Others.end()); 657dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 658dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 659dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void createIrreducibleLoop( 660dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BlockFrequencyInfoImplBase &BFI, const IrreducibleGraph &G, 661dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LoopData *OuterLoop, std::list<LoopData>::iterator Insert, 662dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const std::vector<const IrreducibleGraph::IrrNode *> &SCC) { 663dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Translate the SCC into RPO. 664dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DEBUG(dbgs() << " - found-scc\n"); 665dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 666dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LoopData::NodeList Headers; 667dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LoopData::NodeList Others; 668dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines findIrreducibleHeaders(BFI, G, SCC, Headers, Others); 669dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 670dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto Loop = BFI.Loops.emplace(Insert, OuterLoop, Headers.begin(), 671dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Headers.end(), Others.begin(), Others.end()); 672dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 673dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Update loop hierarchy. 674dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &N : Loop->Nodes) 675dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (BFI.Working[N.Index].isLoopHeader()) 676dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BFI.Working[N.Index].Loop->Parent = &*Loop; 677dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines else 678dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BFI.Working[N.Index].Loop = &*Loop; 679dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 680dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 681dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesiterator_range<std::list<LoopData>::iterator> 682dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequencyInfoImplBase::analyzeIrreducible( 683dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const IrreducibleGraph &G, LoopData *OuterLoop, 684dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::list<LoopData>::iterator Insert) { 685dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert((OuterLoop == nullptr) == (Insert == Loops.begin())); 686dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto Prev = OuterLoop ? std::prev(Insert) : Loops.end(); 687dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 688dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto I = scc_begin(G); !I.isAtEnd(); ++I) { 689dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (I->size() < 2) 690dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines continue; 691dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 692dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Translate the SCC into RPO. 693dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines createIrreducibleLoop(*this, G, OuterLoop, Insert, *I); 694dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 695dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 696dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (OuterLoop) 697dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return make_range(std::next(Prev), Insert); 698dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return make_range(Loops.begin(), Insert); 699dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 700dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 701dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid 702dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesBlockFrequencyInfoImplBase::updateLoopWithIrreducible(LoopData &OuterLoop) { 703dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines OuterLoop.Exits.clear(); 704dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines OuterLoop.BackedgeMass = BlockMass::getEmpty(); 705dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto O = OuterLoop.Nodes.begin() + 1; 706dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (auto I = O, E = OuterLoop.Nodes.end(); I != E; ++I) 707dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Working[I->Index].isPackaged()) 708dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines *O++ = *I; 709dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines OuterLoop.Nodes.erase(O, OuterLoop.Nodes.end()); 710dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 711