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 59