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