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 
33 // TBAAAccessKind - A kind of TBAA memory access descriptor.
34 enum class TBAAAccessKind : unsigned {
35   Ordinary,
36   MayAlias,
37   Incomplete,
38 };
39 
40 // TBAAAccessInfo - Describes a memory access in terms of TBAA.
41 struct 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.
116 class 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 
169 public:
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 
216 namespace llvm {
217 
218 template<> 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