1 //===- bolt/Passes/HFSort.h - Cluster functions by hotness ------*- C++ -*-===//
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 // Implementation of HFSort algorithm for function ordering:
10 // https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf
11 //
12 // Cluster functions by hotness. There are three clustering algorithms:
13 // 1. clusterize
14 // 2. pettisAndHansen
15 // 3. randomClusters
16 //
17 //===----------------------------------------------------------------------===//
18
19 #ifndef BOLT_PASSES_HFSORT_H
20 #define BOLT_PASSES_HFSORT_H
21
22 #include "bolt/Core/CallGraph.h"
23
24 #include <string>
25 #include <vector>
26
27 namespace llvm {
28 namespace bolt {
29
30 class Cluster {
31 public:
32 Cluster(CallGraph::NodeId Id, const CallGraph::Node &F);
33 Cluster(const std::vector<CallGraph::NodeId> &Nodes, const CallGraph &Cg);
34
35 std::string toString() const;
density()36 double density() const { return Density; }
samples()37 uint64_t samples() const { return Samples; }
size()38 uint32_t size() const { return Size; }
frozen()39 bool frozen() const { return Frozen; }
freeze()40 void freeze() { Frozen = true; }
41 void merge(const Cluster &Other, const double Aw = 0);
42 void merge(const Cluster &Other,
43 const std::vector<CallGraph::NodeId> &Targets_);
44 void clear();
numTargets()45 size_t numTargets() const { return Targets.size(); }
targets()46 const std::vector<CallGraph::NodeId> &targets() const { return Targets; }
target(size_t N)47 CallGraph::NodeId target(size_t N) const { return Targets[N]; }
48 void reverseTargets();
hasId()49 bool hasId() const { return Id != -1u; }
setId(uint32_t NewId)50 void setId(uint32_t NewId) {
51 assert(!hasId());
52 Id = NewId;
53 }
id()54 uint32_t id() const {
55 assert(hasId());
56 return Id;
57 }
58
59 private:
60 uint32_t Id{-1u};
61 std::vector<CallGraph::NodeId> Targets;
62 uint64_t Samples{0};
63 uint32_t Size{0};
64 double Density{0.0};
65 bool Frozen{false}; // not a candidate for merging
66 };
67
68 // Maximum size of a cluster, in bytes.
69 constexpr uint32_t MaxClusterSize = 1 << 20;
70
71 // Size of a huge page in bytes.
72 constexpr uint32_t HugePageSize = 2 << 20;
73
compareClustersDensity(const Cluster & C1,const Cluster & C2)74 inline bool compareClustersDensity(const Cluster &C1, const Cluster &C2) {
75 return C1.density() > C2.density();
76 }
77
78 /*
79 * Cluster functions in order to minimize call distance.
80 */
81 std::vector<Cluster> clusterize(const CallGraph &Cg);
82
83 /*
84 * Pettis-Hansen code layout algorithm
85 * reference: K. Pettis and R. C. Hansen, "Profile Guided Code Positioning",
86 * PLDI '90
87 */
88 std::vector<Cluster> pettisAndHansen(const CallGraph &Cg);
89
90 /* Group functions into clusters randomly. */
91 std::vector<Cluster> randomClusters(const CallGraph &Cg);
92
93 } // end namespace bolt
94 } // end namespace llvm
95
96 #endif // BOLT_PASSES_HFSORT_H
97