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