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