1 //===- llvm/Analysis/MemoryProfileInfo.h - memory profile info ---*- 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 // This file contains utilities to analyze memory profile information. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_ANALYSIS_MEMORYPROFILEINFO_H 14 #define LLVM_ANALYSIS_MEMORYPROFILEINFO_H 15 16 #include "llvm/IR/Constants.h" 17 #include "llvm/IR/InstrTypes.h" 18 #include "llvm/IR/Metadata.h" 19 #include "llvm/IR/Module.h" 20 #include <map> 21 22 namespace llvm { 23 namespace memprof { 24 25 // Allocation type assigned to an allocation reached by a given context. 26 // More can be added but initially this is just noncold and cold. 27 // Values should be powers of two so that they can be ORed, in particular to 28 // track allocations that have different behavior with different calling 29 // contexts. 30 enum class AllocationType : uint8_t { None = 0, NotCold = 1, Cold = 2 }; 31 32 /// Return the allocation type for a given set of memory profile values. 33 AllocationType getAllocType(uint64_t MaxAccessCount, uint64_t MinSize, 34 uint64_t MinLifetime); 35 36 /// Build callstack metadata from the provided list of call stack ids. Returns 37 /// the resulting metadata node. 38 MDNode *buildCallstackMetadata(ArrayRef<uint64_t> CallStack, LLVMContext &Ctx); 39 40 /// Returns the stack node from an MIB metadata node. 41 MDNode *getMIBStackNode(const MDNode *MIB); 42 43 /// Returns the allocation type from an MIB metadata node. 44 AllocationType getMIBAllocType(const MDNode *MIB); 45 46 /// Class to build a trie of call stack contexts for a particular profiled 47 /// allocation call, along with their associated allocation types. 48 /// The allocation will be at the root of the trie, which is then used to 49 /// compute the minimum lists of context ids needed to associate a call context 50 /// with a single allocation type. 51 class CallStackTrie { 52 private: 53 struct CallStackTrieNode { 54 // Allocation types for call context sharing the context prefix at this 55 // node. 56 uint8_t AllocTypes; 57 // Map of caller stack id to the corresponding child Trie node. 58 std::map<uint64_t, CallStackTrieNode *> Callers; 59 CallStackTrieNode(AllocationType Type) 60 : AllocTypes(static_cast<uint8_t>(Type)) {} 61 }; 62 63 // The node for the allocation at the root. 64 CallStackTrieNode *Alloc; 65 // The allocation's leaf stack id. 66 uint64_t AllocStackId; 67 68 void deleteTrieNode(CallStackTrieNode *Node) { 69 if (!Node) 70 return; 71 for (auto C : Node->Callers) 72 deleteTrieNode(C.second); 73 delete Node; 74 } 75 76 // Recursive helper to trim contexts and create metadata nodes. 77 bool buildMIBNodes(CallStackTrieNode *Node, LLVMContext &Ctx, 78 std::vector<uint64_t> &MIBCallStack, 79 std::vector<Metadata *> &MIBNodes, 80 bool CalleeHasAmbiguousCallerContext); 81 82 public: 83 CallStackTrie() : Alloc(nullptr), AllocStackId(0) {} 84 ~CallStackTrie() { deleteTrieNode(Alloc); } 85 86 bool empty() const { return Alloc == nullptr; } 87 88 /// Add a call stack context with the given allocation type to the Trie. 89 /// The context is represented by the list of stack ids (computed during 90 /// matching via a debug location hash), expected to be in order from the 91 /// allocation call down to the bottom of the call stack (i.e. callee to 92 /// caller order). 93 void addCallStack(AllocationType AllocType, ArrayRef<uint64_t> StackIds); 94 95 /// Add the call stack context along with its allocation type from the MIB 96 /// metadata to the Trie. 97 void addCallStack(MDNode *MIB); 98 99 /// Build and attach the minimal necessary MIB metadata. If the alloc has a 100 /// single allocation type, add a function attribute instead. The reason for 101 /// adding an attribute in this case is that it matches how the behavior for 102 /// allocation calls will be communicated to lib call simplification after 103 /// cloning or another optimization to distinguish the allocation types, 104 /// which is lower overhead and more direct than maintaining this metadata. 105 /// Returns true if memprof metadata attached, false if not (attribute added). 106 bool buildAndAttachMIBMetadata(CallBase *CI); 107 }; 108 109 } // end namespace memprof 110 } // end namespace llvm 111 112 #endif 113