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