287 lines · cpp
1//===- bolt/Passes/HFSort.cpp - Cluster functions by hotness --------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Implementation of HFSort algorithm for function ordering:10// https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf11//12//===----------------------------------------------------------------------===//13 14#include "bolt/Passes/HFSort.h"15#include "llvm/Support/CommandLine.h"16#include "llvm/Support/Debug.h"17#include "llvm/Support/Format.h"18#include "llvm/Support/raw_ostream.h"19#include <unordered_set>20 21#define DEBUG_TYPE "hfsort"22 23namespace opts {24extern llvm::cl::opt<unsigned> Verbosity;25}26 27namespace llvm {28namespace bolt {29 30using NodeId = CallGraph::NodeId;31using Arc = CallGraph::Arc;32using Node = CallGraph::Node;33 34namespace {35 36// The number of pages to reserve for the functions with highest37// density (samples / size). The functions put in these pages are not38// considered for clustering.39constexpr uint32_t FrozenPages = 0;40 41// The minimum approximate probability of a callee being called from a42// particular arc to consider merging with the caller's cluster.43constexpr double MinArcProbability = 0.1;44 45// This is a factor to determine by how much a caller cluster is46// willing to degrade it's density by merging a callee.47constexpr int CallerDegradeFactor = 8;48 49} // namespace50 51////////////////////////////////////////////////////////////////////////////////52 53Cluster::Cluster(NodeId Id, const Node &Func)54 : Samples(Func.samples()), Size(Func.size()),55 Density((double)Samples / Size) {56 Targets.push_back(Id);57}58 59Cluster::Cluster(const std::vector<NodeId> &Nodes, const CallGraph &Cg) {60 Samples = 0;61 Size = 0;62 for (NodeId TargetId : Nodes) {63 Targets.push_back(TargetId);64 Samples += Cg.samples(TargetId);65 Size += Cg.size(TargetId);66 }67 Density = (double)Samples / Size;68}69 70std::string Cluster::toString() const {71 std::string Str;72 raw_string_ostream CS(Str);73 bool PrintComma = false;74 CS << "funcs = [";75 for (const NodeId &Target : Targets) {76 if (PrintComma)77 CS << ", ";78 CS << Target;79 PrintComma = true;80 }81 CS << "]";82 return CS.str();83}84 85namespace {86 87void freezeClusters(const CallGraph &Cg, std::vector<Cluster> &Clusters) {88 uint32_t TotalSize = 0;89 llvm::sort(Clusters, compareClustersDensity);90 for (Cluster &C : Clusters) {91 uint32_t NewSize = TotalSize + C.size();92 if (NewSize > FrozenPages * HugePageSize)93 break;94 C.freeze();95 TotalSize = NewSize;96 LLVM_DEBUG(NodeId Fid = C.target(0);97 dbgs() << format(98 "freezing cluster for func %d, size = %u, samples = %lu)\n",99 Fid, Cg.size(Fid), Cg.samples(Fid)););100 }101}102 103} // namespace104 105void Cluster::reverseTargets() { std::reverse(Targets.begin(), Targets.end()); }106 107void Cluster::merge(const Cluster &Other, const double Aw) {108 Targets.insert(Targets.end(), Other.Targets.begin(), Other.Targets.end());109 Size += Other.Size;110 Samples += Other.Samples;111 Density = (double)Samples / Size;112}113 114void Cluster::merge(const Cluster &Other,115 const std::vector<CallGraph::NodeId> &Targets_) {116 Targets = Targets_;117 Size += Other.Size;118 Samples += Other.Samples;119 Density = (double)Samples / Size;120}121 122void Cluster::clear() {123 Id = -1u;124 Size = 0;125 Samples = 0;126 Density = 0.0;127 Targets.clear();128 Frozen = false;129}130 131std::vector<Cluster> clusterize(const CallGraph &Cg) {132 std::vector<NodeId> SortedFuncs;133 134 // indexed by NodeId, keeps it's current cluster135 std::vector<Cluster *> FuncCluster(Cg.numNodes(), nullptr);136 std::vector<Cluster> Clusters;137 Clusters.reserve(Cg.numNodes());138 139 for (NodeId F = 0; F < Cg.numNodes(); F++) {140 if (Cg.samples(F) == 0)141 continue;142 Clusters.emplace_back(F, Cg.getNode(F));143 SortedFuncs.push_back(F);144 }145 146 freezeClusters(Cg, Clusters);147 148 // The size and order of Clusters is fixed until we reshuffle it immediately149 // before returning.150 for (Cluster &Cluster : Clusters)151 FuncCluster[Cluster.targets().front()] = &Cluster;152 153 llvm::sort(SortedFuncs, [&](const NodeId F1, const NodeId F2) {154 const CallGraph::Node &Func1 = Cg.getNode(F1);155 const CallGraph::Node &Func2 = Cg.getNode(F2);156 return Func1.samples() * Func2.size() > // TODO: is this correct?157 Func2.samples() * Func1.size();158 });159 160 // Process each function, and consider merging its cluster with the161 // one containing its most likely predecessor.162 for (const NodeId Fid : SortedFuncs) {163 Cluster *Cluster = FuncCluster[Fid];164 if (Cluster->frozen())165 continue;166 167 // Find best predecessor.168 NodeId BestPred = CallGraph::InvalidId;169 double BestProb = 0;170 171 for (const NodeId Src : Cg.predecessors(Fid)) {172 const Arc &Arc = *Cg.findArc(Src, Fid);173 if (BestPred == CallGraph::InvalidId ||174 Arc.normalizedWeight() > BestProb) {175 BestPred = Arc.src();176 BestProb = Arc.normalizedWeight();177 }178 }179 180 // Check if the merge is good for the callee.181 // Don't merge if the probability of getting to the callee from the182 // caller is too low.183 if (BestProb < MinArcProbability)184 continue;185 186 assert(BestPred != CallGraph::InvalidId);187 188 class Cluster *PredCluster = FuncCluster[BestPred];189 190 // Skip if no predCluster (predecessor w/ no samples), or if same191 // as cluster, of it's frozen.192 if (PredCluster == nullptr || PredCluster == Cluster ||193 PredCluster->frozen())194 continue;195 196 // Skip if merged cluster would be bigger than the threshold.197 if (Cluster->size() + PredCluster->size() > MaxClusterSize)198 continue;199 200 // Check if the merge is good for the caller.201 // Don't merge if the caller's density is significantly better202 // than the density resulting from the merge.203 const double NewDensity =204 ((double)PredCluster->samples() + Cluster->samples()) /205 (PredCluster->size() + Cluster->size());206 if (PredCluster->density() > NewDensity * CallerDegradeFactor) {207 continue;208 }209 210 LLVM_DEBUG(if (opts::Verbosity > 1) {211 dbgs() << format("merging %s -> %s: %u\n",212 PredCluster->toString().c_str(),213 Cluster->toString().c_str(), Cg.samples(Fid));214 });215 216 for (NodeId F : Cluster->targets())217 FuncCluster[F] = PredCluster;218 219 PredCluster->merge(*Cluster);220 Cluster->clear();221 }222 223 // Return the set of Clusters that are left, which are the ones that224 // didn't get merged (so their first func is its original func).225 std::vector<Cluster> SortedClusters;226 std::unordered_set<Cluster *> Visited;227 for (const NodeId Func : SortedFuncs) {228 Cluster *Cluster = FuncCluster[Func];229 if (!Cluster || Visited.count(Cluster) == 1 || Cluster->target(0) != Func)230 continue;231 232 SortedClusters.emplace_back(std::move(*Cluster));233 Visited.insert(Cluster);234 }235 236 llvm::sort(SortedClusters, compareClustersDensity);237 238 return SortedClusters;239}240 241std::vector<Cluster> randomClusters(const CallGraph &Cg) {242 std::vector<Cluster> Clusters;243 Clusters.reserve(Cg.numNodes());244 245 for (NodeId F = 0; F < Cg.numNodes(); F++) {246 if (Cg.samples(F) == 0)247 continue;248 Clusters.emplace_back(F, Cg.getNode(F));249 }250 251 llvm::sort(Clusters, [](const Cluster &A, const Cluster &B) {252 return A.size() < B.size();253 });254 255 auto pickMergeCluster = [&Clusters](const size_t Idx) {256 size_t MaxIdx = Idx + 1;257 258 while (MaxIdx < Clusters.size() &&259 Clusters[Idx].size() + Clusters[MaxIdx].size() <= MaxClusterSize)260 ++MaxIdx;261 262 if (MaxIdx - Idx > 1) {263 size_t MergeIdx = (std::rand() % (MaxIdx - Idx - 1)) + Idx + 1;264 assert(Clusters[MergeIdx].size() + Clusters[Idx].size() <=265 MaxClusterSize);266 return MergeIdx;267 }268 return Clusters.size();269 };270 271 size_t Idx = 0;272 while (Idx < Clusters.size()) {273 size_t MergeIdx = pickMergeCluster(Idx);274 if (MergeIdx == Clusters.size()) {275 ++Idx;276 } else {277 Clusters[Idx].merge(Clusters[MergeIdx]);278 Clusters.erase(Clusters.begin() + MergeIdx);279 }280 }281 282 return Clusters;283}284 285} // namespace bolt286} // namespace llvm287