LLVM  17.0.0git
CodeLayout.h
Go to the documentation of this file.
1 //===- CodeLayout.h - Code layout/placement algorithms ---------*- 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 /// \file
10 /// Declares methods and data structures for code layout algorithms.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_TRANSFORMS_UTILS_CODELAYOUT_H
15 #define LLVM_TRANSFORMS_UTILS_CODELAYOUT_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 
19 #include <vector>
20 
21 namespace llvm {
22 
23 using EdgeT = std::pair<uint64_t, uint64_t>;
24 using EdgeCountT = std::pair<EdgeT, uint64_t>;
25 
26 /// Find a layout of nodes (basic blocks) of a given CFG optimizing jump
27 /// locality and thus processor I-cache utilization. This is achieved via
28 /// increasing the number of fall-through jumps and co-locating frequently
29 /// executed nodes together.
30 /// The nodes are assumed to be indexed by integers from [0, |V|) so that the
31 /// current order is the identity permutation.
32 /// \p NodeSizes: The sizes of the nodes (in bytes).
33 /// \p NodeCounts: The execution counts of the nodes in the profile.
34 /// \p EdgeCounts: The execution counts of every edge (jump) in the profile. The
35 /// map also defines the edges in CFG and should include 0-count edges.
36 /// \returns The best block order found.
37 std::vector<uint64_t>
38 applyExtTspLayout(const std::vector<uint64_t> &NodeSizes,
39  const std::vector<uint64_t> &NodeCounts,
40  const std::vector<EdgeCountT> &EdgeCounts);
41 
42 /// Estimate the "quality" of a given node order in CFG. The higher the score,
43 /// the better the order is. The score is designed to reflect the locality of
44 /// the given order, which is anti-correlated with the number of I-cache misses
45 /// in a typical execution of the function.
46 double calcExtTspScore(const std::vector<uint64_t> &Order,
47  const std::vector<uint64_t> &NodeSizes,
48  const std::vector<uint64_t> &NodeCounts,
49  const std::vector<EdgeCountT> &EdgeCounts);
50 
51 /// Estimate the "quality" of the current node order in CFG.
52 double calcExtTspScore(const std::vector<uint64_t> &NodeSizes,
53  const std::vector<uint64_t> &NodeCounts,
54  const std::vector<EdgeCountT> &EdgeCounts);
55 
56 } // end namespace llvm
57 
58 #endif // LLVM_TRANSFORMS_UTILS_CODELAYOUT_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
DenseMap.h
llvm::EdgeCountT
std::pair< EdgeT, uint64_t > EdgeCountT
Definition: CodeLayout.h:24
llvm::applyExtTspLayout
std::vector< uint64_t > applyExtTspLayout(const std::vector< uint64_t > &NodeSizes, const std::vector< uint64_t > &NodeCounts, const std::vector< EdgeCountT > &EdgeCounts)
Find a layout of nodes (basic blocks) of a given CFG optimizing jump locality and thus processor I-ca...
llvm::EdgeT
std::pair< uint64_t, uint64_t > EdgeT
Definition: CodeLayout.h:23
llvm::calcExtTspScore
double calcExtTspScore(const std::vector< uint64_t > &Order, const std::vector< uint64_t > &NodeSizes, const std::vector< uint64_t > &NodeCounts, const std::vector< EdgeCountT > &EdgeCounts)
Estimate the "quality" of a given node order in CFG.