216 lines · cpp
1//===- bolt/Passes/PettisAndHansen.cpp ------------------------------------===//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// The file implements Pettis and Hansen code-layout algorithm.10//11//===----------------------------------------------------------------------===//12 13#include "bolt/Passes/HFSort.h"14#include "llvm/Support/Debug.h"15#include "llvm/Support/Format.h"16#include "llvm/Support/raw_ostream.h"17#include <set>18#include <unordered_map>19 20#define DEBUG_TYPE "hfsort"21 22namespace llvm {23namespace bolt {24 25using NodeId = CallGraph::NodeId;26using Arc = CallGraph::Arc;27using Node = CallGraph::Node;28 29namespace {30class ClusterArc {31public:32 ClusterArc(Cluster *Ca, Cluster *Cb, double W = 0)33 : C1(std::min(Ca, Cb)), C2(std::max(Ca, Cb)), Weight(W) {}34 35 friend bool operator==(const ClusterArc &Lhs, const ClusterArc &Rhs) {36 return Lhs.C1 == Rhs.C1 && Lhs.C2 == Rhs.C2;37 }38 39 Cluster *const C1;40 Cluster *const C2;41 mutable double Weight;42};43 44class ClusterArcHash {45public:46 int64_t operator()(const ClusterArc &Arc) const {47 std::hash<int64_t> Hasher;48 return hashCombine(Hasher(int64_t(Arc.C1)), int64_t(Arc.C2));49 }50};51 52using ClusterArcSet = std::unordered_set<ClusterArc, ClusterArcHash>;53 54void orderFuncs(const CallGraph &Cg, Cluster *C1, Cluster *C2) {55 NodeId C1head = C1->targets().front();56 NodeId C1tail = C1->targets().back();57 NodeId C2head = C2->targets().front();58 NodeId C2tail = C2->targets().back();59 60 double C1headC2head = 0;61 double C1headC2tail = 0;62 double C1tailC2head = 0;63 double C1tailC2tail = 0;64 65 for (const Arc &Arc : Cg.arcs()) {66 if ((Arc.src() == C1head && Arc.dst() == C2head) ||67 (Arc.dst() == C1head && Arc.src() == C2head))68 C1headC2head += Arc.weight();69 else if ((Arc.src() == C1head && Arc.dst() == C2tail) ||70 (Arc.dst() == C1head && Arc.src() == C2tail))71 C1headC2tail += Arc.weight();72 else if ((Arc.src() == C1tail && Arc.dst() == C2head) ||73 (Arc.dst() == C1tail && Arc.src() == C2head))74 C1tailC2head += Arc.weight();75 else if ((Arc.src() == C1tail && Arc.dst() == C2tail) ||76 (Arc.dst() == C1tail && Arc.src() == C2tail))77 C1tailC2tail += Arc.weight();78 }79 80 const double Max = std::max(std::max(C1headC2head, C1headC2tail),81 std::max(C1tailC2head, C1tailC2tail));82 83 if (C1headC2head == Max) {84 // flip C185 C1->reverseTargets();86 } else if (C1headC2tail == Max) {87 // flip C1 C288 C1->reverseTargets();89 C2->reverseTargets();90 } else if (C1tailC2tail == Max) {91 // flip C292 C2->reverseTargets();93 }94}95} // namespace96 97std::vector<Cluster> pettisAndHansen(const CallGraph &Cg) {98 // indexed by NodeId, keeps its current cluster99 std::vector<Cluster *> FuncCluster(Cg.numNodes(), nullptr);100 std::vector<Cluster> Clusters;101 std::vector<NodeId> Funcs;102 103 Clusters.reserve(Cg.numNodes());104 105 for (NodeId F = 0; F < Cg.numNodes(); F++) {106 if (Cg.samples(F) == 0)107 continue;108 Clusters.emplace_back(F, Cg.getNode(F));109 FuncCluster[F] = &Clusters.back();110 Funcs.push_back(F);111 }112 113 ClusterArcSet Carcs;114 115 auto insertOrInc = [&](Cluster *C1, Cluster *C2, double Weight) {116 auto Res = Carcs.emplace(C1, C2, Weight);117 if (!Res.second)118 Res.first->Weight += Weight;119 };120 121 // Create a std::vector of cluster arcs122 123 for (const Arc &Arc : Cg.arcs()) {124 if (Arc.weight() == 0)125 continue;126 127 Cluster *const S = FuncCluster[Arc.src()];128 Cluster *const D = FuncCluster[Arc.dst()];129 130 // ignore if s or d is nullptr131 132 if (S == nullptr || D == nullptr)133 continue;134 135 // ignore self-edges136 137 if (S == D)138 continue;139 140 insertOrInc(S, D, Arc.weight());141 }142 143 // Find an arc with max weight and merge its nodes144 145 while (!Carcs.empty()) {146 auto Maxpos = llvm::max_element(147 Carcs, [&](const ClusterArc &Carc1, const ClusterArc &Carc2) {148 return Carc1.Weight < Carc2.Weight;149 });150 151 ClusterArc Max = *Maxpos;152 Carcs.erase(Maxpos);153 154 Cluster *const C1 = Max.C1;155 Cluster *const C2 = Max.C2;156 157 if (C1->size() + C2->size() > MaxClusterSize)158 continue;159 160 if (C1->frozen() || C2->frozen())161 continue;162 163 // order functions and merge cluster164 165 orderFuncs(Cg, C1, C2);166 167 LLVM_DEBUG(dbgs() << format("merging %s -> %s: %.1f\n",168 C2->toString().c_str(), C1->toString().c_str(),169 Max.Weight));170 171 // update carcs: merge C1arcs to C2arcs172 173 std::unordered_map<ClusterArc, Cluster *, ClusterArcHash> C2arcs;174 for (const ClusterArc &Carc : Carcs) {175 if (Carc.C1 == C2)176 C2arcs.emplace(Carc, Carc.C2);177 if (Carc.C2 == C2)178 C2arcs.emplace(Carc, Carc.C1);179 }180 181 for (auto It : C2arcs) {182 Cluster *const C = It.second;183 ClusterArc const C2arc = It.first;184 185 insertOrInc(C, C1, C2arc.Weight);186 Carcs.erase(C2arc);187 }188 189 // update FuncCluster190 191 for (NodeId F : C2->targets())192 FuncCluster[F] = C1;193 194 C1->merge(*C2, Max.Weight);195 C2->clear();196 }197 198 // Return the set of Clusters that are left, which are the ones that199 // didn't get merged.200 201 std::set<Cluster *> LiveClusters;202 std::vector<Cluster> OutClusters;203 204 for (NodeId Fid : Funcs)205 LiveClusters.insert(FuncCluster[Fid]);206 for (Cluster *C : LiveClusters)207 OutClusters.push_back(std::move(*C));208 209 llvm::sort(OutClusters, compareClustersDensity);210 211 return OutClusters;212}213 214} // namespace bolt215} // namespace llvm216