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