1 //===--- FunctionId.h - Sample profile function object ----------*- 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 ///
11 /// Defines FunctionId class.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_PROFILEDATA_FUNCTIONID_H
16 #define LLVM_PROFILEDATA_FUNCTIONID_H
17 
18 #include "llvm/ADT/DenseMapInfo.h"
19 #include "llvm/ADT/Hashing.h"
20 #include "llvm/ADT/StringRef.h"
21 #include "llvm/Support/MD5.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include <cstdint>
24 
25 namespace llvm {
26 namespace sampleprof {
27 
28 /// This class represents a function that is read from a sample profile. It
29 /// comes with two forms: a string or a hash code. The latter form is the 64-bit
30 /// MD5 of the function name for efficient storage supported by ExtBinary
31 /// profile format, and when reading the profile, this class can represent it
32 /// without converting it to a string first.
33 /// When representing a hash code, we utilize the LengthOrHashCode field to
34 /// store it, and Name is set to null. When representing a string, it is same as
35 /// StringRef.
36 class FunctionId {
37 
38   const char *Data = nullptr;
39 
40   // Use uint64_t instead of size_t so that it can also hold a MD5 value on
41   // 32-bit system.
42   uint64_t LengthOrHashCode = 0;
43 
44   /// Extension to memcmp to handle hash code representation. If both are hash
45   /// values, Lhs and Rhs are both null, function returns 0 (and needs an extra
46   /// comparison using getIntValue). If only one is hash code, it is considered
47   /// less than the StringRef one. Otherwise perform normal string comparison.
compareMemory(const char * Lhs,const char * Rhs,uint64_t Length)48   static int compareMemory(const char *Lhs, const char *Rhs, uint64_t Length) {
49     if (Lhs == Rhs)
50       return 0;
51     if (!Lhs)
52       return -1;
53     if (!Rhs)
54       return 1;
55     return ::memcmp(Lhs, Rhs, (size_t)Length);
56   }
57 
58 public:
59   FunctionId() = default;
60 
61   /// Constructor from a StringRef.
FunctionId(StringRef Str)62   explicit FunctionId(StringRef Str)
63       : Data(Str.data()), LengthOrHashCode(Str.size()) {
64   }
65 
66   /// Constructor from a hash code.
FunctionId(uint64_t HashCode)67   explicit FunctionId(uint64_t HashCode)
68       : LengthOrHashCode(HashCode) {
69     assert(HashCode != 0);
70   }
71 
72   /// Check for equality. Similar to StringRef::equals, but will also cover for
73   /// the case where one or both are hash codes. Comparing their int values are
74   /// sufficient. A hash code FunctionId is considered not equal to a StringRef
75   /// FunctionId regardless of actual contents.
equals(const FunctionId & Other)76   bool equals(const FunctionId &Other) const {
77     return LengthOrHashCode == Other.LengthOrHashCode &&
78            compareMemory(Data, Other.Data, LengthOrHashCode) == 0;
79   }
80 
81   /// Total order comparison. If both FunctionId are StringRef, this is the same
82   /// as StringRef::compare. If one of them is StringRef, it is considered
83   /// greater than the hash code FunctionId. Otherwise this is the the same
84   /// as comparing their int values.
compare(const FunctionId & Other)85   int compare(const FunctionId &Other) const {
86     auto Res = compareMemory(
87         Data, Other.Data, std::min(LengthOrHashCode, Other.LengthOrHashCode));
88     if (Res != 0)
89       return Res;
90     if (LengthOrHashCode == Other.LengthOrHashCode)
91       return 0;
92     return LengthOrHashCode < Other.LengthOrHashCode ? -1 : 1;
93   }
94 
95   /// Convert to a string, usually for output purpose. Use caution on return
96   /// value's lifetime when converting to StringRef.
str()97   std::string str() const {
98     if (Data)
99       return std::string(Data, LengthOrHashCode);
100     if (LengthOrHashCode != 0)
101       return std::to_string(LengthOrHashCode);
102     return std::string();
103   }
104 
105   /// Convert to StringRef. This is only allowed when it is known this object is
106   /// representing a StringRef, not a hash code. Calling this function on a hash
107   /// code is considered an error.
stringRef()108   StringRef stringRef() const {
109     if (Data)
110       return StringRef(Data, LengthOrHashCode);
111     assert(LengthOrHashCode == 0 &&
112            "Cannot convert MD5 FunctionId to StringRef");
113     return StringRef();
114   }
115 
116   friend raw_ostream &operator<<(raw_ostream &OS, const FunctionId &Obj);
117 
118   /// Get hash code of this object. Returns this object's hash code if it is
119   /// already representing one, otherwise returns the MD5 of its string content.
120   /// Note that it is not the same as std::hash because we want to keep the
121   /// consistency that the same sample profile function in string form or MD5
122   /// form has the same hash code.
getHashCode()123   uint64_t getHashCode() const {
124     if (Data)
125       return MD5Hash(StringRef(Data, LengthOrHashCode));
126     return LengthOrHashCode;
127   }
128 
empty()129   bool empty() const { return LengthOrHashCode == 0; }
130 
131   /// Check if this object represents a StringRef, or a hash code.
isStringRef()132   bool isStringRef() const { return Data != nullptr; }
133 };
134 
135 inline bool operator==(const FunctionId &LHS, const FunctionId &RHS) {
136   return LHS.equals(RHS);
137 }
138 
139 inline bool operator!=(const FunctionId &LHS, const FunctionId &RHS) {
140   return !LHS.equals(RHS);
141 }
142 
143 inline bool operator<(const FunctionId &LHS, const FunctionId &RHS) {
144   return LHS.compare(RHS) < 0;
145 }
146 
147 inline bool operator<=(const FunctionId &LHS, const FunctionId &RHS) {
148   return LHS.compare(RHS) <= 0;
149 }
150 
151 inline bool operator>(const FunctionId &LHS, const FunctionId &RHS) {
152   return LHS.compare(RHS) > 0;
153 }
154 
155 inline bool operator>=(const FunctionId &LHS, const FunctionId &RHS) {
156   return LHS.compare(RHS) >= 0;
157 }
158 
159 inline raw_ostream &operator<<(raw_ostream &OS, const FunctionId &Obj) {
160   if (Obj.Data)
161     return OS << StringRef(Obj.Data, Obj.LengthOrHashCode);
162   if (Obj.LengthOrHashCode != 0)
163     return OS << Obj.LengthOrHashCode;
164   return OS;
165 }
166 
MD5Hash(const FunctionId & Obj)167 inline uint64_t MD5Hash(const FunctionId &Obj) {
168   return Obj.getHashCode();
169 }
170 
hash_value(const FunctionId & Obj)171 inline uint64_t hash_value(const FunctionId &Obj) {
172   return Obj.getHashCode();
173 }
174 
175 } // end namespace sampleprof
176 
177 /// Template specialization for FunctionId so that it can be used in LLVM map
178 /// containers.
179 template <> struct DenseMapInfo<sampleprof::FunctionId, void> {
180 
181   static inline sampleprof::FunctionId getEmptyKey() {
182     return sampleprof::FunctionId(~0ULL);
183   }
184 
185   static inline sampleprof::FunctionId getTombstoneKey() {
186     return sampleprof::FunctionId(~1ULL);
187   }
188 
189   static unsigned getHashValue(const sampleprof::FunctionId &Val) {
190     return Val.getHashCode();
191   }
192 
193   static bool isEqual(const sampleprof::FunctionId &LHS,
194                       const sampleprof::FunctionId &RHS) {
195     return LHS == RHS;
196   }
197 };
198 
199 } // end namespace llvm
200 
201 namespace std {
202 
203 /// Template specialization for FunctionId so that it can be used in STL
204 /// containers.
205 template <> struct hash<llvm::sampleprof::FunctionId> {
206   size_t operator()(const llvm::sampleprof::FunctionId &Val) const {
207     return Val.getHashCode();
208   }
209 };
210 
211 } // end namespace std
212 
213 #endif // LLVM_PROFILEDATA_FUNCTIONID_H
214