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-exception
6 //
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 
22 namespace llvm {
23 namespace bolt {
24 
25 using NodeId = CallGraph::NodeId;
26 using Arc = CallGraph::Arc;
27 using Node = CallGraph::Node;
28 
29 namespace {
30 class ClusterArc {
31 public:
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 
44 class ClusterArcHash {
45 public:
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 
52 using ClusterArcSet = std::unordered_set<ClusterArc, ClusterArcHash>;
53 
54 void 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 C1
85     C1->reverseTargets();
86   } else if (C1headC2tail == Max) {
87     // flip C1 C2
88     C1->reverseTargets();
89     C2->reverseTargets();
90   } else if (C1tailC2tail == Max) {
91     // flip C2
92     C2->reverseTargets();
93   }
94 }
95 } // namespace
96 
97 std::vector<Cluster> pettisAndHansen(const CallGraph &Cg) {
98   // indexed by NodeId, keeps its current cluster
99   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 arcs
122 
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 nullptr
131 
132     if (S == nullptr || D == nullptr)
133       continue;
134 
135     // ignore self-edges
136 
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 nodes
144 
145   while (!Carcs.empty()) {
146     auto Maxpos =
147         std::max_element(Carcs.begin(), Carcs.end(),
148                          [&](const ClusterArc &Carc1, const ClusterArc &Carc2) {
149                            return Carc1.Weight < Carc2.Weight;
150                          });
151 
152     ClusterArc Max = *Maxpos;
153     Carcs.erase(Maxpos);
154 
155     Cluster *const C1 = Max.C1;
156     Cluster *const C2 = Max.C2;
157 
158     if (C1->size() + C2->size() > MaxClusterSize)
159       continue;
160 
161     if (C1->frozen() || C2->frozen())
162       continue;
163 
164     // order functions and merge cluster
165 
166     orderFuncs(Cg, C1, C2);
167 
168     LLVM_DEBUG(dbgs() << format("merging %s -> %s: %.1f\n",
169                                 C2->toString().c_str(), C1->toString().c_str(),
170                                 Max.Weight));
171 
172     // update carcs: merge C1arcs to C2arcs
173 
174     std::unordered_map<ClusterArc, Cluster *, ClusterArcHash> C2arcs;
175     for (const ClusterArc &Carc : Carcs) {
176       if (Carc.C1 == C2)
177         C2arcs.emplace(Carc, Carc.C2);
178       if (Carc.C2 == C2)
179         C2arcs.emplace(Carc, Carc.C1);
180     }
181 
182     for (auto It : C2arcs) {
183       Cluster *const C = It.second;
184       ClusterArc const C2arc = It.first;
185 
186       insertOrInc(C, C1, C2arc.Weight);
187       Carcs.erase(C2arc);
188     }
189 
190     // update FuncCluster
191 
192     for (NodeId F : C2->targets())
193       FuncCluster[F] = C1;
194 
195     C1->merge(*C2, Max.Weight);
196     C2->clear();
197   }
198 
199   // Return the set of Clusters that are left, which are the ones that
200   // didn't get merged.
201 
202   std::set<Cluster *> LiveClusters;
203   std::vector<Cluster> OutClusters;
204 
205   for (NodeId Fid : Funcs)
206     LiveClusters.insert(FuncCluster[Fid]);
207   for (Cluster *C : LiveClusters)
208     OutClusters.push_back(std::move(*C));
209 
210   llvm::sort(OutClusters, compareClustersDensity);
211 
212   return OutClusters;
213 }
214 
215 } // namespace bolt
216 } // namespace llvm
217