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