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 57