1//===--- CodeGenTBAA.h - TBAA information for LLVM CodeGen ------*- 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 is the code that manages TBAA information and defines the TBAA policy
10// for the optimizer to use.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CLANG_LIB_CODEGEN_CODEGENTBAA_H
15#define LLVM_CLANG_LIB_CODEGEN_CODEGENTBAA_H
16
17#include "clang/AST/Type.h"
18#include "clang/Basic/LLVM.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/IR/MDBuilder.h"
21#include "llvm/IR/Metadata.h"
22
23namespace clang {
24  class ASTContext;
25  class CodeGenOptions;
26  class LangOptions;
27  class MangleContext;
28  class QualType;
29  class Type;
30
31namespace CodeGen {
32
33// TBAAAccessKind - A kind of TBAA memory access descriptor.
34enum class TBAAAccessKind : unsigned {
35  Ordinary,
36  MayAlias,
37  Incomplete,
38};
39
40// TBAAAccessInfo - Describes a memory access in terms of TBAA.
41struct TBAAAccessInfo {
42  TBAAAccessInfo(TBAAAccessKind Kind, llvm::MDNode *BaseType,
43                 llvm::MDNode *AccessType, uint64_t Offset, uint64_t Size)
44    : Kind(Kind), BaseType(BaseType), AccessType(AccessType),
45      Offset(Offset), Size(Size)
46  {}
47
48  TBAAAccessInfo(llvm::MDNode *BaseType, llvm::MDNode *AccessType,
49                 uint64_t Offset, uint64_t Size)
50    : TBAAAccessInfo(TBAAAccessKind::Ordinary, BaseType, AccessType,
51                     Offset, Size)
52  {}
53
54  explicit TBAAAccessInfo(llvm::MDNode *AccessType, uint64_t Size)
55    : TBAAAccessInfo(/* BaseType= */ nullptr, AccessType, /* Offset= */ 0, Size)
56  {}
57
58  TBAAAccessInfo()
59    : TBAAAccessInfo(/* AccessType= */ nullptr, /* Size= */ 0)
60  {}
61
62  static TBAAAccessInfo getMayAliasInfo() {
63    return TBAAAccessInfo(TBAAAccessKind::MayAlias,
64                          /* BaseType= */ nullptr, /* AccessType= */ nullptr,
65                          /* Offset= */ 0, /* Size= */ 0);
66  }
67
68  bool isMayAlias() const { return Kind == TBAAAccessKind::MayAlias; }
69
70  static TBAAAccessInfo getIncompleteInfo() {
71    return TBAAAccessInfo(TBAAAccessKind::Incomplete,
72                          /* BaseType= */ nullptr, /* AccessType= */ nullptr,
73                          /* Offset= */ 0, /* Size= */ 0);
74  }
75
76  bool isIncomplete() const { return Kind == TBAAAccessKind::Incomplete; }
77
78  bool operator==(const TBAAAccessInfo &Other) const {
79    return Kind == Other.Kind &&
80           BaseType == Other.BaseType &&
81           AccessType == Other.AccessType &&
82           Offset == Other.Offset &&
83           Size == Other.Size;
84  }
85
86  bool operator!=(const TBAAAccessInfo &Other) const {
87    return !(*this == Other);
88  }
89
90  explicit operator bool() const {
91    return *this != TBAAAccessInfo();
92  }
93
94  /// Kind - The kind of the access descriptor.
95  TBAAAccessKind Kind;
96
97  /// BaseType - The base/leading access type. May be null if this access
98  /// descriptor represents an access that is not considered to be an access
99  /// to an aggregate or union member.
100  llvm::MDNode *BaseType;
101
102  /// AccessType - The final access type. May be null if there is no TBAA
103  /// information available about this access.
104  llvm::MDNode *AccessType;
105
106  /// Offset - The byte offset of the final access within the base one. Must be
107  /// zero if the base access type is not specified.
108  uint64_t Offset;
109
110  /// Size - The size of access, in bytes.
111  uint64_t Size;
112};
113
114/// CodeGenTBAA - This class organizes the cross-module state that is used
115/// while lowering AST types to LLVM types.
116class CodeGenTBAA {
117  ASTContext &Context;
118  llvm::Module &Module;
119  const CodeGenOptions &CodeGenOpts;
120  const LangOptions &Features;
121  MangleContext &MContext;
122
123  // MDHelper - Helper for creating metadata.
124  llvm::MDBuilder MDHelper;
125
126  /// MetadataCache - This maps clang::Types to scalar llvm::MDNodes describing
127  /// them.
128  llvm::DenseMap<const Type *, llvm::MDNode *> MetadataCache;
129  /// This maps clang::Types to a base access type in the type DAG.
130  llvm::DenseMap<const Type *, llvm::MDNode *> BaseTypeMetadataCache;
131  /// This maps TBAA access descriptors to tag nodes.
132  llvm::DenseMap<TBAAAccessInfo, llvm::MDNode *> AccessTagMetadataCache;
133
134  /// StructMetadataCache - This maps clang::Types to llvm::MDNodes describing
135  /// them for struct assignments.
136  llvm::DenseMap<const Type *, llvm::MDNode *> StructMetadataCache;
137
138  llvm::MDNode *Root;
139  llvm::MDNode *Char;
140
141  /// getRoot - This is the mdnode for the root of the metadata type graph
142  /// for this translation unit.
143  llvm::MDNode *getRoot();
144
145  /// getChar - This is the mdnode for "char", which is special, and any types
146  /// considered to be equivalent to it.
147  llvm::MDNode *getChar();
148
149  /// CollectFields - Collect information about the fields of a type for
150  /// !tbaa.struct metadata formation. Return false for an unsupported type.
151  bool CollectFields(uint64_t BaseOffset,
152                     QualType Ty,
153                     SmallVectorImpl<llvm::MDBuilder::TBAAStructField> &Fields,
154                     bool MayAlias);
155
156  /// createScalarTypeNode - A wrapper function to create a metadata node
157  /// describing a scalar type.
158  llvm::MDNode *createScalarTypeNode(StringRef Name, llvm::MDNode *Parent,
159                                     uint64_t Size);
160
161  /// getTypeInfoHelper - An internal helper function to generate metadata used
162  /// to describe accesses to objects of the given type.
163  llvm::MDNode *getTypeInfoHelper(const Type *Ty);
164
165  /// getBaseTypeInfoHelper - An internal helper function to generate metadata
166  /// used to describe accesses to objects of the given base type.
167  llvm::MDNode *getBaseTypeInfoHelper(const Type *Ty);
168
169public:
170  CodeGenTBAA(ASTContext &Ctx, llvm::Module &M, const CodeGenOptions &CGO,
171              const LangOptions &Features, MangleContext &MContext);
172  ~CodeGenTBAA();
173
174  /// getTypeInfo - Get metadata used to describe accesses to objects of the
175  /// given type.
176  llvm::MDNode *getTypeInfo(QualType QTy);
177
178  /// getAccessInfo - Get TBAA information that describes an access to
179  /// an object of the given type.
180  TBAAAccessInfo getAccessInfo(QualType AccessType);
181
182  /// getVTablePtrAccessInfo - Get the TBAA information that describes an
183  /// access to a virtual table pointer.
184  TBAAAccessInfo getVTablePtrAccessInfo(llvm::Type *VTablePtrType);
185
186  /// getTBAAStructInfo - Get the TBAAStruct MDNode to be used for a memcpy of
187  /// the given type.
188  llvm::MDNode *getTBAAStructInfo(QualType QTy);
189
190  /// getBaseTypeInfo - Get metadata that describes the given base access type.
191  /// Return null if the type is not suitable for use in TBAA access tags.
192  llvm::MDNode *getBaseTypeInfo(QualType QTy);
193
194  /// getAccessTagInfo - Get TBAA tag for a given memory access.
195  llvm::MDNode *getAccessTagInfo(TBAAAccessInfo Info);
196
197  /// mergeTBAAInfoForCast - Get merged TBAA information for the purpose of
198  /// type casts.
199  TBAAAccessInfo mergeTBAAInfoForCast(TBAAAccessInfo SourceInfo,
200                                      TBAAAccessInfo TargetInfo);
201
202  /// mergeTBAAInfoForConditionalOperator - Get merged TBAA information for the
203  /// purpose of conditional operator.
204  TBAAAccessInfo mergeTBAAInfoForConditionalOperator(TBAAAccessInfo InfoA,
205                                                     TBAAAccessInfo InfoB);
206
207  /// mergeTBAAInfoForMemoryTransfer - Get merged TBAA information for the
208  /// purpose of memory transfer calls.
209  TBAAAccessInfo mergeTBAAInfoForMemoryTransfer(TBAAAccessInfo DestInfo,
210                                                TBAAAccessInfo SrcInfo);
211};
212
213}  // end namespace CodeGen
214}  // end namespace clang
215
216namespace llvm {
217
218template<> struct DenseMapInfo<clang::CodeGen::TBAAAccessInfo> {
219  static clang::CodeGen::TBAAAccessInfo getEmptyKey() {
220    unsigned UnsignedKey = DenseMapInfo<unsigned>::getEmptyKey();
221    return clang::CodeGen::TBAAAccessInfo(
222      static_cast<clang::CodeGen::TBAAAccessKind>(UnsignedKey),
223      DenseMapInfo<MDNode *>::getEmptyKey(),
224      DenseMapInfo<MDNode *>::getEmptyKey(),
225      DenseMapInfo<uint64_t>::getEmptyKey(),
226      DenseMapInfo<uint64_t>::getEmptyKey());
227  }
228
229  static clang::CodeGen::TBAAAccessInfo getTombstoneKey() {
230    unsigned UnsignedKey = DenseMapInfo<unsigned>::getTombstoneKey();
231    return clang::CodeGen::TBAAAccessInfo(
232      static_cast<clang::CodeGen::TBAAAccessKind>(UnsignedKey),
233      DenseMapInfo<MDNode *>::getTombstoneKey(),
234      DenseMapInfo<MDNode *>::getTombstoneKey(),
235      DenseMapInfo<uint64_t>::getTombstoneKey(),
236      DenseMapInfo<uint64_t>::getTombstoneKey());
237  }
238
239  static unsigned getHashValue(const clang::CodeGen::TBAAAccessInfo &Val) {
240    auto KindValue = static_cast<unsigned>(Val.Kind);
241    return DenseMapInfo<unsigned>::getHashValue(KindValue) ^
242           DenseMapInfo<MDNode *>::getHashValue(Val.BaseType) ^
243           DenseMapInfo<MDNode *>::getHashValue(Val.AccessType) ^
244           DenseMapInfo<uint64_t>::getHashValue(Val.Offset) ^
245           DenseMapInfo<uint64_t>::getHashValue(Val.Size);
246  }
247
248  static bool isEqual(const clang::CodeGen::TBAAAccessInfo &LHS,
249                      const clang::CodeGen::TBAAAccessInfo &RHS) {
250    return LHS == RHS;
251  }
252};
253
254}  // end namespace llvm
255
256#endif
257