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 public:
147   CodeGenTBAA(ASTContext &Ctx, llvm::LLVMContext &VMContext,
148               const CodeGenOptions &CGO,
149               const LangOptions &Features,
150               MangleContext &MContext);
151   ~CodeGenTBAA();
152 
153   /// getTypeInfo - Get metadata used to describe accesses to objects of the
154   /// given type.
155   llvm::MDNode *getTypeInfo(QualType QTy);
156 
157   /// getVTablePtrAccessInfo - Get the TBAA information that describes an
158   /// access to a virtual table pointer.
159   TBAAAccessInfo getVTablePtrAccessInfo();
160 
161   /// getTBAAStructInfo - Get the TBAAStruct MDNode to be used for a memcpy of
162   /// the given type.
163   llvm::MDNode *getTBAAStructInfo(QualType QTy);
164 
165   /// getBaseTypeInfo - Get metadata that describes the given base access type.
166   /// Return null if the type is not suitable for use in TBAA access tags.
167   llvm::MDNode *getBaseTypeInfo(QualType QTy);
168 
169   /// getAccessTagInfo - Get TBAA tag for a given memory access.
170   llvm::MDNode *getAccessTagInfo(TBAAAccessInfo Info);
171 
172   /// mergeTBAAInfoForCast - Get merged TBAA information for the purpose of
173   /// type casts.
174   TBAAAccessInfo mergeTBAAInfoForCast(TBAAAccessInfo SourceInfo,
175                                       TBAAAccessInfo TargetInfo);
176 
177   /// mergeTBAAInfoForConditionalOperator - Get merged TBAA information for the
178   /// purpose of conditional operator.
179   TBAAAccessInfo mergeTBAAInfoForConditionalOperator(TBAAAccessInfo InfoA,
180                                                      TBAAAccessInfo InfoB);
181 };
182 
183 }  // end namespace CodeGen
184 }  // end namespace clang
185 
186 namespace llvm {
187 
188 template<> struct DenseMapInfo<clang::CodeGen::TBAAAccessInfo> {
189   static clang::CodeGen::TBAAAccessInfo getEmptyKey() {
190     unsigned UnsignedKey = DenseMapInfo<unsigned>::getEmptyKey();
191     return clang::CodeGen::TBAAAccessInfo(
192       static_cast<clang::CodeGen::TBAAAccessKind>(UnsignedKey),
193       DenseMapInfo<MDNode *>::getEmptyKey(),
194       DenseMapInfo<MDNode *>::getEmptyKey(),
195       DenseMapInfo<uint64_t>::getEmptyKey());
196   }
197 
198   static clang::CodeGen::TBAAAccessInfo getTombstoneKey() {
199     unsigned UnsignedKey = DenseMapInfo<unsigned>::getTombstoneKey();
200     return clang::CodeGen::TBAAAccessInfo(
201       static_cast<clang::CodeGen::TBAAAccessKind>(UnsignedKey),
202       DenseMapInfo<MDNode *>::getTombstoneKey(),
203       DenseMapInfo<MDNode *>::getTombstoneKey(),
204       DenseMapInfo<uint64_t>::getTombstoneKey());
205   }
206 
207   static unsigned getHashValue(const clang::CodeGen::TBAAAccessInfo &Val) {
208     auto KindValue = static_cast<unsigned>(Val.Kind);
209     return DenseMapInfo<unsigned>::getHashValue(KindValue) ^
210            DenseMapInfo<MDNode *>::getHashValue(Val.BaseType) ^
211            DenseMapInfo<MDNode *>::getHashValue(Val.AccessType) ^
212            DenseMapInfo<uint64_t>::getHashValue(Val.Offset);
213   }
214 
215   static bool isEqual(const clang::CodeGen::TBAAAccessInfo &LHS,
216                       const clang::CodeGen::TBAAAccessInfo &RHS) {
217     return LHS == RHS;
218   }
219 };
220 
221 }  // end namespace llvm
222 
223 #endif
224