Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
14 | pmbaty | 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 |