1 //== MemRegion.cpp - Abstract memory regions for static analysis --*- 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 file defines MemRegion and its subclasses. MemRegion defines a
11 // partially-typed abstraction of memory useful for path-sensitive dataflow
12 // analyses.
13 //
14 //===----------------------------------------------------------------------===//
15
16 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
18 #include "clang/Analysis/AnalysisContext.h"
19 #include "clang/Analysis/Support/BumpVector.h"
20 #include "clang/AST/CharUnits.h"
21 #include "clang/AST/DeclObjC.h"
22 #include "clang/AST/RecordLayout.h"
23 #include "clang/Basic/SourceManager.h"
24 #include "llvm/Support/raw_ostream.h"
25
26 using namespace clang;
27 using namespace ento;
28
29 //===----------------------------------------------------------------------===//
30 // MemRegion Construction.
31 //===----------------------------------------------------------------------===//
32
33 template<typename RegionTy> struct MemRegionManagerTrait;
34
35 template <typename RegionTy, typename A1>
getRegion(const A1 a1)36 RegionTy* MemRegionManager::getRegion(const A1 a1) {
37
38 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
39 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1);
40
41 llvm::FoldingSetNodeID ID;
42 RegionTy::ProfileRegion(ID, a1, superRegion);
43 void *InsertPos;
44 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
45 InsertPos));
46
47 if (!R) {
48 R = (RegionTy*) A.Allocate<RegionTy>();
49 new (R) RegionTy(a1, superRegion);
50 Regions.InsertNode(R, InsertPos);
51 }
52
53 return R;
54 }
55
56 template <typename RegionTy, typename A1>
getSubRegion(const A1 a1,const MemRegion * superRegion)57 RegionTy* MemRegionManager::getSubRegion(const A1 a1,
58 const MemRegion *superRegion) {
59 llvm::FoldingSetNodeID ID;
60 RegionTy::ProfileRegion(ID, a1, superRegion);
61 void *InsertPos;
62 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
63 InsertPos));
64
65 if (!R) {
66 R = (RegionTy*) A.Allocate<RegionTy>();
67 new (R) RegionTy(a1, superRegion);
68 Regions.InsertNode(R, InsertPos);
69 }
70
71 return R;
72 }
73
74 template <typename RegionTy, typename A1, typename A2>
getRegion(const A1 a1,const A2 a2)75 RegionTy* MemRegionManager::getRegion(const A1 a1, const A2 a2) {
76
77 const typename MemRegionManagerTrait<RegionTy>::SuperRegionTy *superRegion =
78 MemRegionManagerTrait<RegionTy>::getSuperRegion(*this, a1, a2);
79
80 llvm::FoldingSetNodeID ID;
81 RegionTy::ProfileRegion(ID, a1, a2, superRegion);
82 void *InsertPos;
83 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
84 InsertPos));
85
86 if (!R) {
87 R = (RegionTy*) A.Allocate<RegionTy>();
88 new (R) RegionTy(a1, a2, superRegion);
89 Regions.InsertNode(R, InsertPos);
90 }
91
92 return R;
93 }
94
95 template <typename RegionTy, typename A1, typename A2>
getSubRegion(const A1 a1,const A2 a2,const MemRegion * superRegion)96 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2,
97 const MemRegion *superRegion) {
98
99 llvm::FoldingSetNodeID ID;
100 RegionTy::ProfileRegion(ID, a1, a2, superRegion);
101 void *InsertPos;
102 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
103 InsertPos));
104
105 if (!R) {
106 R = (RegionTy*) A.Allocate<RegionTy>();
107 new (R) RegionTy(a1, a2, superRegion);
108 Regions.InsertNode(R, InsertPos);
109 }
110
111 return R;
112 }
113
114 template <typename RegionTy, typename A1, typename A2, typename A3>
getSubRegion(const A1 a1,const A2 a2,const A3 a3,const MemRegion * superRegion)115 RegionTy* MemRegionManager::getSubRegion(const A1 a1, const A2 a2, const A3 a3,
116 const MemRegion *superRegion) {
117
118 llvm::FoldingSetNodeID ID;
119 RegionTy::ProfileRegion(ID, a1, a2, a3, superRegion);
120 void *InsertPos;
121 RegionTy* R = cast_or_null<RegionTy>(Regions.FindNodeOrInsertPos(ID,
122 InsertPos));
123
124 if (!R) {
125 R = (RegionTy*) A.Allocate<RegionTy>();
126 new (R) RegionTy(a1, a2, a3, superRegion);
127 Regions.InsertNode(R, InsertPos);
128 }
129
130 return R;
131 }
132
133 //===----------------------------------------------------------------------===//
134 // Object destruction.
135 //===----------------------------------------------------------------------===//
136
~MemRegion()137 MemRegion::~MemRegion() {}
138
~MemRegionManager()139 MemRegionManager::~MemRegionManager() {
140 // All regions and their data are BumpPtrAllocated. No need to call
141 // their destructors.
142 }
143
144 //===----------------------------------------------------------------------===//
145 // Basic methods.
146 //===----------------------------------------------------------------------===//
147
isSubRegionOf(const MemRegion * R) const148 bool SubRegion::isSubRegionOf(const MemRegion* R) const {
149 const MemRegion* r = getSuperRegion();
150 while (r != 0) {
151 if (r == R)
152 return true;
153 if (const SubRegion* sr = dyn_cast<SubRegion>(r))
154 r = sr->getSuperRegion();
155 else
156 break;
157 }
158 return false;
159 }
160
getMemRegionManager() const161 MemRegionManager* SubRegion::getMemRegionManager() const {
162 const SubRegion* r = this;
163 do {
164 const MemRegion *superRegion = r->getSuperRegion();
165 if (const SubRegion *sr = dyn_cast<SubRegion>(superRegion)) {
166 r = sr;
167 continue;
168 }
169 return superRegion->getMemRegionManager();
170 } while (1);
171 }
172
getStackFrame() const173 const StackFrameContext *VarRegion::getStackFrame() const {
174 const StackSpaceRegion *SSR = dyn_cast<StackSpaceRegion>(getMemorySpace());
175 return SSR ? SSR->getStackFrame() : NULL;
176 }
177
178 //===----------------------------------------------------------------------===//
179 // Region extents.
180 //===----------------------------------------------------------------------===//
181
getExtent(SValBuilder & svalBuilder) const182 DefinedOrUnknownSVal DeclRegion::getExtent(SValBuilder &svalBuilder) const {
183 ASTContext &Ctx = svalBuilder.getContext();
184 QualType T = getDesugaredValueType(Ctx);
185
186 if (isa<VariableArrayType>(T))
187 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
188 if (isa<IncompleteArrayType>(T))
189 return UnknownVal();
190
191 CharUnits size = Ctx.getTypeSizeInChars(T);
192 QualType sizeTy = svalBuilder.getArrayIndexType();
193 return svalBuilder.makeIntVal(size.getQuantity(), sizeTy);
194 }
195
getExtent(SValBuilder & svalBuilder) const196 DefinedOrUnknownSVal FieldRegion::getExtent(SValBuilder &svalBuilder) const {
197 DefinedOrUnknownSVal Extent = DeclRegion::getExtent(svalBuilder);
198
199 // A zero-length array at the end of a struct often stands for dynamically-
200 // allocated extra memory.
201 if (Extent.isZeroConstant()) {
202 QualType T = getDesugaredValueType(svalBuilder.getContext());
203
204 if (isa<ConstantArrayType>(T))
205 return UnknownVal();
206 }
207
208 return Extent;
209 }
210
getExtent(SValBuilder & svalBuilder) const211 DefinedOrUnknownSVal AllocaRegion::getExtent(SValBuilder &svalBuilder) const {
212 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
213 }
214
getExtent(SValBuilder & svalBuilder) const215 DefinedOrUnknownSVal SymbolicRegion::getExtent(SValBuilder &svalBuilder) const {
216 return nonloc::SymbolVal(svalBuilder.getSymbolManager().getExtentSymbol(this));
217 }
218
getExtent(SValBuilder & svalBuilder) const219 DefinedOrUnknownSVal StringRegion::getExtent(SValBuilder &svalBuilder) const {
220 return svalBuilder.makeIntVal(getStringLiteral()->getByteLength()+1,
221 svalBuilder.getArrayIndexType());
222 }
223
ObjCIvarRegion(const ObjCIvarDecl * ivd,const MemRegion * sReg)224 ObjCIvarRegion::ObjCIvarRegion(const ObjCIvarDecl *ivd, const MemRegion* sReg)
225 : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
226
getDecl() const227 const ObjCIvarDecl *ObjCIvarRegion::getDecl() const {
228 return cast<ObjCIvarDecl>(D);
229 }
230
getValueType() const231 QualType ObjCIvarRegion::getValueType() const {
232 return getDecl()->getType();
233 }
234
getValueType() const235 QualType CXXBaseObjectRegion::getValueType() const {
236 return QualType(decl->getTypeForDecl(), 0);
237 }
238
239 //===----------------------------------------------------------------------===//
240 // FoldingSet profiling.
241 //===----------------------------------------------------------------------===//
242
Profile(llvm::FoldingSetNodeID & ID) const243 void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const {
244 ID.AddInteger((unsigned)getKind());
245 }
246
Profile(llvm::FoldingSetNodeID & ID) const247 void StackSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
248 ID.AddInteger((unsigned)getKind());
249 ID.AddPointer(getStackFrame());
250 }
251
Profile(llvm::FoldingSetNodeID & ID) const252 void StaticGlobalSpaceRegion::Profile(llvm::FoldingSetNodeID &ID) const {
253 ID.AddInteger((unsigned)getKind());
254 ID.AddPointer(getCodeRegion());
255 }
256
ProfileRegion(llvm::FoldingSetNodeID & ID,const StringLiteral * Str,const MemRegion * superRegion)257 void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
258 const StringLiteral* Str,
259 const MemRegion* superRegion) {
260 ID.AddInteger((unsigned) StringRegionKind);
261 ID.AddPointer(Str);
262 ID.AddPointer(superRegion);
263 }
264
ProfileRegion(llvm::FoldingSetNodeID & ID,const ObjCStringLiteral * Str,const MemRegion * superRegion)265 void ObjCStringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
266 const ObjCStringLiteral* Str,
267 const MemRegion* superRegion) {
268 ID.AddInteger((unsigned) ObjCStringRegionKind);
269 ID.AddPointer(Str);
270 ID.AddPointer(superRegion);
271 }
272
ProfileRegion(llvm::FoldingSetNodeID & ID,const Expr * Ex,unsigned cnt,const MemRegion *)273 void AllocaRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
274 const Expr *Ex, unsigned cnt,
275 const MemRegion *) {
276 ID.AddInteger((unsigned) AllocaRegionKind);
277 ID.AddPointer(Ex);
278 ID.AddInteger(cnt);
279 }
280
Profile(llvm::FoldingSetNodeID & ID) const281 void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
282 ProfileRegion(ID, Ex, Cnt, superRegion);
283 }
284
Profile(llvm::FoldingSetNodeID & ID) const285 void CompoundLiteralRegion::Profile(llvm::FoldingSetNodeID& ID) const {
286 CompoundLiteralRegion::ProfileRegion(ID, CL, superRegion);
287 }
288
ProfileRegion(llvm::FoldingSetNodeID & ID,const CompoundLiteralExpr * CL,const MemRegion * superRegion)289 void CompoundLiteralRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
290 const CompoundLiteralExpr *CL,
291 const MemRegion* superRegion) {
292 ID.AddInteger((unsigned) CompoundLiteralRegionKind);
293 ID.AddPointer(CL);
294 ID.AddPointer(superRegion);
295 }
296
ProfileRegion(llvm::FoldingSetNodeID & ID,const PointerType * PT,const MemRegion * sRegion)297 void CXXThisRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
298 const PointerType *PT,
299 const MemRegion *sRegion) {
300 ID.AddInteger((unsigned) CXXThisRegionKind);
301 ID.AddPointer(PT);
302 ID.AddPointer(sRegion);
303 }
304
Profile(llvm::FoldingSetNodeID & ID) const305 void CXXThisRegion::Profile(llvm::FoldingSetNodeID &ID) const {
306 CXXThisRegion::ProfileRegion(ID, ThisPointerTy, superRegion);
307 }
308
ProfileRegion(llvm::FoldingSetNodeID & ID,const ObjCIvarDecl * ivd,const MemRegion * superRegion)309 void ObjCIvarRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
310 const ObjCIvarDecl *ivd,
311 const MemRegion* superRegion) {
312 DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
313 }
314
ProfileRegion(llvm::FoldingSetNodeID & ID,const Decl * D,const MemRegion * superRegion,Kind k)315 void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl *D,
316 const MemRegion* superRegion, Kind k) {
317 ID.AddInteger((unsigned) k);
318 ID.AddPointer(D);
319 ID.AddPointer(superRegion);
320 }
321
Profile(llvm::FoldingSetNodeID & ID) const322 void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const {
323 DeclRegion::ProfileRegion(ID, D, superRegion, getKind());
324 }
325
Profile(llvm::FoldingSetNodeID & ID) const326 void VarRegion::Profile(llvm::FoldingSetNodeID &ID) const {
327 VarRegion::ProfileRegion(ID, getDecl(), superRegion);
328 }
329
ProfileRegion(llvm::FoldingSetNodeID & ID,SymbolRef sym,const MemRegion * sreg)330 void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym,
331 const MemRegion *sreg) {
332 ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind);
333 ID.Add(sym);
334 ID.AddPointer(sreg);
335 }
336
Profile(llvm::FoldingSetNodeID & ID) const337 void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const {
338 SymbolicRegion::ProfileRegion(ID, sym, getSuperRegion());
339 }
340
ProfileRegion(llvm::FoldingSetNodeID & ID,QualType ElementType,SVal Idx,const MemRegion * superRegion)341 void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
342 QualType ElementType, SVal Idx,
343 const MemRegion* superRegion) {
344 ID.AddInteger(MemRegion::ElementRegionKind);
345 ID.Add(ElementType);
346 ID.AddPointer(superRegion);
347 Idx.Profile(ID);
348 }
349
Profile(llvm::FoldingSetNodeID & ID) const350 void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const {
351 ElementRegion::ProfileRegion(ID, ElementType, Index, superRegion);
352 }
353
ProfileRegion(llvm::FoldingSetNodeID & ID,const FunctionDecl * FD,const MemRegion *)354 void FunctionTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
355 const FunctionDecl *FD,
356 const MemRegion*) {
357 ID.AddInteger(MemRegion::FunctionTextRegionKind);
358 ID.AddPointer(FD);
359 }
360
Profile(llvm::FoldingSetNodeID & ID) const361 void FunctionTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
362 FunctionTextRegion::ProfileRegion(ID, FD, superRegion);
363 }
364
ProfileRegion(llvm::FoldingSetNodeID & ID,const BlockDecl * BD,CanQualType,const AnalysisDeclContext * AC,const MemRegion *)365 void BlockTextRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
366 const BlockDecl *BD, CanQualType,
367 const AnalysisDeclContext *AC,
368 const MemRegion*) {
369 ID.AddInteger(MemRegion::BlockTextRegionKind);
370 ID.AddPointer(BD);
371 }
372
Profile(llvm::FoldingSetNodeID & ID) const373 void BlockTextRegion::Profile(llvm::FoldingSetNodeID& ID) const {
374 BlockTextRegion::ProfileRegion(ID, BD, locTy, AC, superRegion);
375 }
376
ProfileRegion(llvm::FoldingSetNodeID & ID,const BlockTextRegion * BC,const LocationContext * LC,const MemRegion * sReg)377 void BlockDataRegion::ProfileRegion(llvm::FoldingSetNodeID& ID,
378 const BlockTextRegion *BC,
379 const LocationContext *LC,
380 const MemRegion *sReg) {
381 ID.AddInteger(MemRegion::BlockDataRegionKind);
382 ID.AddPointer(BC);
383 ID.AddPointer(LC);
384 ID.AddPointer(sReg);
385 }
386
Profile(llvm::FoldingSetNodeID & ID) const387 void BlockDataRegion::Profile(llvm::FoldingSetNodeID& ID) const {
388 BlockDataRegion::ProfileRegion(ID, BC, LC, getSuperRegion());
389 }
390
ProfileRegion(llvm::FoldingSetNodeID & ID,Expr const * Ex,const MemRegion * sReg)391 void CXXTempObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
392 Expr const *Ex,
393 const MemRegion *sReg) {
394 ID.AddPointer(Ex);
395 ID.AddPointer(sReg);
396 }
397
Profile(llvm::FoldingSetNodeID & ID) const398 void CXXTempObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
399 ProfileRegion(ID, Ex, getSuperRegion());
400 }
401
ProfileRegion(llvm::FoldingSetNodeID & ID,const CXXRecordDecl * decl,const MemRegion * sReg)402 void CXXBaseObjectRegion::ProfileRegion(llvm::FoldingSetNodeID &ID,
403 const CXXRecordDecl *decl,
404 const MemRegion *sReg) {
405 ID.AddPointer(decl);
406 ID.AddPointer(sReg);
407 }
408
Profile(llvm::FoldingSetNodeID & ID) const409 void CXXBaseObjectRegion::Profile(llvm::FoldingSetNodeID &ID) const {
410 ProfileRegion(ID, decl, superRegion);
411 }
412
413 //===----------------------------------------------------------------------===//
414 // Region anchors.
415 //===----------------------------------------------------------------------===//
416
anchor()417 void GlobalsSpaceRegion::anchor() { }
anchor()418 void HeapSpaceRegion::anchor() { }
anchor()419 void UnknownSpaceRegion::anchor() { }
anchor()420 void StackLocalsSpaceRegion::anchor() { }
anchor()421 void StackArgumentsSpaceRegion::anchor() { }
anchor()422 void TypedRegion::anchor() { }
anchor()423 void TypedValueRegion::anchor() { }
anchor()424 void CodeTextRegion::anchor() { }
anchor()425 void SubRegion::anchor() { }
426
427 //===----------------------------------------------------------------------===//
428 // Region pretty-printing.
429 //===----------------------------------------------------------------------===//
430
dump() const431 void MemRegion::dump() const {
432 dumpToStream(llvm::errs());
433 }
434
getString() const435 std::string MemRegion::getString() const {
436 std::string s;
437 llvm::raw_string_ostream os(s);
438 dumpToStream(os);
439 return os.str();
440 }
441
dumpToStream(raw_ostream & os) const442 void MemRegion::dumpToStream(raw_ostream &os) const {
443 os << "<Unknown Region>";
444 }
445
dumpToStream(raw_ostream & os) const446 void AllocaRegion::dumpToStream(raw_ostream &os) const {
447 os << "alloca{" << (void*) Ex << ',' << Cnt << '}';
448 }
449
dumpToStream(raw_ostream & os) const450 void FunctionTextRegion::dumpToStream(raw_ostream &os) const {
451 os << "code{" << getDecl()->getDeclName().getAsString() << '}';
452 }
453
dumpToStream(raw_ostream & os) const454 void BlockTextRegion::dumpToStream(raw_ostream &os) const {
455 os << "block_code{" << (void*) this << '}';
456 }
457
dumpToStream(raw_ostream & os) const458 void BlockDataRegion::dumpToStream(raw_ostream &os) const {
459 os << "block_data{" << BC << '}';
460 }
461
dumpToStream(raw_ostream & os) const462 void CompoundLiteralRegion::dumpToStream(raw_ostream &os) const {
463 // FIXME: More elaborate pretty-printing.
464 os << "{ " << (void*) CL << " }";
465 }
466
dumpToStream(raw_ostream & os) const467 void CXXTempObjectRegion::dumpToStream(raw_ostream &os) const {
468 os << "temp_object{" << getValueType().getAsString() << ','
469 << (void*) Ex << '}';
470 }
471
dumpToStream(raw_ostream & os) const472 void CXXBaseObjectRegion::dumpToStream(raw_ostream &os) const {
473 os << "base " << decl->getName();
474 }
475
dumpToStream(raw_ostream & os) const476 void CXXThisRegion::dumpToStream(raw_ostream &os) const {
477 os << "this";
478 }
479
dumpToStream(raw_ostream & os) const480 void ElementRegion::dumpToStream(raw_ostream &os) const {
481 os << "element{" << superRegion << ','
482 << Index << ',' << getElementType().getAsString() << '}';
483 }
484
dumpToStream(raw_ostream & os) const485 void FieldRegion::dumpToStream(raw_ostream &os) const {
486 os << superRegion << "->" << *getDecl();
487 }
488
dumpToStream(raw_ostream & os) const489 void ObjCIvarRegion::dumpToStream(raw_ostream &os) const {
490 os << "ivar{" << superRegion << ',' << *getDecl() << '}';
491 }
492
dumpToStream(raw_ostream & os) const493 void StringRegion::dumpToStream(raw_ostream &os) const {
494 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
495 }
496
dumpToStream(raw_ostream & os) const497 void ObjCStringRegion::dumpToStream(raw_ostream &os) const {
498 Str->printPretty(os, 0, PrintingPolicy(getContext().getLangOpts()));
499 }
500
dumpToStream(raw_ostream & os) const501 void SymbolicRegion::dumpToStream(raw_ostream &os) const {
502 os << "SymRegion{" << sym << '}';
503 }
504
dumpToStream(raw_ostream & os) const505 void VarRegion::dumpToStream(raw_ostream &os) const {
506 os << *cast<VarDecl>(D);
507 }
508
dump() const509 void RegionRawOffset::dump() const {
510 dumpToStream(llvm::errs());
511 }
512
dumpToStream(raw_ostream & os) const513 void RegionRawOffset::dumpToStream(raw_ostream &os) const {
514 os << "raw_offset{" << getRegion() << ',' << getOffset().getQuantity() << '}';
515 }
516
dumpToStream(raw_ostream & os) const517 void StaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
518 os << "StaticGlobalsMemSpace{" << CR << '}';
519 }
520
dumpToStream(raw_ostream & os) const521 void NonStaticGlobalSpaceRegion::dumpToStream(raw_ostream &os) const {
522 os << "NonStaticGlobalSpaceRegion";
523 }
524
dumpToStream(raw_ostream & os) const525 void GlobalInternalSpaceRegion::dumpToStream(raw_ostream &os) const {
526 os << "GlobalInternalSpaceRegion";
527 }
528
dumpToStream(raw_ostream & os) const529 void GlobalSystemSpaceRegion::dumpToStream(raw_ostream &os) const {
530 os << "GlobalSystemSpaceRegion";
531 }
532
dumpToStream(raw_ostream & os) const533 void GlobalImmutableSpaceRegion::dumpToStream(raw_ostream &os) const {
534 os << "GlobalImmutableSpaceRegion";
535 }
536
dumpPretty(raw_ostream & os) const537 void MemRegion::dumpPretty(raw_ostream &os) const {
538 return;
539 }
540
dumpPretty(raw_ostream & os) const541 void VarRegion::dumpPretty(raw_ostream &os) const {
542 os << getDecl()->getName();
543 }
544
dumpPretty(raw_ostream & os) const545 void FieldRegion::dumpPretty(raw_ostream &os) const {
546 superRegion->dumpPretty(os);
547 os << "->" << getDecl();
548 }
549
550 //===----------------------------------------------------------------------===//
551 // MemRegionManager methods.
552 //===----------------------------------------------------------------------===//
553
554 template <typename REG>
LazyAllocate(REG * & region)555 const REG *MemRegionManager::LazyAllocate(REG*& region) {
556 if (!region) {
557 region = (REG*) A.Allocate<REG>();
558 new (region) REG(this);
559 }
560
561 return region;
562 }
563
564 template <typename REG, typename ARG>
LazyAllocate(REG * & region,ARG a)565 const REG *MemRegionManager::LazyAllocate(REG*& region, ARG a) {
566 if (!region) {
567 region = (REG*) A.Allocate<REG>();
568 new (region) REG(this, a);
569 }
570
571 return region;
572 }
573
574 const StackLocalsSpaceRegion*
getStackLocalsRegion(const StackFrameContext * STC)575 MemRegionManager::getStackLocalsRegion(const StackFrameContext *STC) {
576 assert(STC);
577 StackLocalsSpaceRegion *&R = StackLocalsSpaceRegions[STC];
578
579 if (R)
580 return R;
581
582 R = A.Allocate<StackLocalsSpaceRegion>();
583 new (R) StackLocalsSpaceRegion(this, STC);
584 return R;
585 }
586
587 const StackArgumentsSpaceRegion *
getStackArgumentsRegion(const StackFrameContext * STC)588 MemRegionManager::getStackArgumentsRegion(const StackFrameContext *STC) {
589 assert(STC);
590 StackArgumentsSpaceRegion *&R = StackArgumentsSpaceRegions[STC];
591
592 if (R)
593 return R;
594
595 R = A.Allocate<StackArgumentsSpaceRegion>();
596 new (R) StackArgumentsSpaceRegion(this, STC);
597 return R;
598 }
599
600 const GlobalsSpaceRegion
getGlobalsRegion(MemRegion::Kind K,const CodeTextRegion * CR)601 *MemRegionManager::getGlobalsRegion(MemRegion::Kind K,
602 const CodeTextRegion *CR) {
603 if (!CR) {
604 if (K == MemRegion::GlobalSystemSpaceRegionKind)
605 return LazyAllocate(SystemGlobals);
606 if (K == MemRegion::GlobalImmutableSpaceRegionKind)
607 return LazyAllocate(ImmutableGlobals);
608 assert(K == MemRegion::GlobalInternalSpaceRegionKind);
609 return LazyAllocate(InternalGlobals);
610 }
611
612 assert(K == MemRegion::StaticGlobalSpaceRegionKind);
613 StaticGlobalSpaceRegion *&R = StaticsGlobalSpaceRegions[CR];
614 if (R)
615 return R;
616
617 R = A.Allocate<StaticGlobalSpaceRegion>();
618 new (R) StaticGlobalSpaceRegion(this, CR);
619 return R;
620 }
621
getHeapRegion()622 const HeapSpaceRegion *MemRegionManager::getHeapRegion() {
623 return LazyAllocate(heap);
624 }
625
getUnknownRegion()626 const MemSpaceRegion *MemRegionManager::getUnknownRegion() {
627 return LazyAllocate(unknown);
628 }
629
getCodeRegion()630 const MemSpaceRegion *MemRegionManager::getCodeRegion() {
631 return LazyAllocate(code);
632 }
633
634 //===----------------------------------------------------------------------===//
635 // Constructing regions.
636 //===----------------------------------------------------------------------===//
getStringRegion(const StringLiteral * Str)637 const StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str){
638 return getSubRegion<StringRegion>(Str, getGlobalsRegion());
639 }
640
641 const ObjCStringRegion *
getObjCStringRegion(const ObjCStringLiteral * Str)642 MemRegionManager::getObjCStringRegion(const ObjCStringLiteral* Str){
643 return getSubRegion<ObjCStringRegion>(Str, getGlobalsRegion());
644 }
645
getVarRegion(const VarDecl * D,const LocationContext * LC)646 const VarRegion* MemRegionManager::getVarRegion(const VarDecl *D,
647 const LocationContext *LC) {
648 const MemRegion *sReg = 0;
649
650 if (D->hasGlobalStorage() && !D->isStaticLocal()) {
651
652 // First handle the globals defined in system headers.
653 if (C.getSourceManager().isInSystemHeader(D->getLocation())) {
654 // Whitelist the system globals which often DO GET modified, assume the
655 // rest are immutable.
656 if (D->getName().find("errno") != StringRef::npos)
657 sReg = getGlobalsRegion(MemRegion::GlobalSystemSpaceRegionKind);
658 else
659 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
660
661 // Treat other globals as GlobalInternal unless they are constants.
662 } else {
663 QualType GQT = D->getType();
664 const Type *GT = GQT.getTypePtrOrNull();
665 // TODO: We could walk the complex types here and see if everything is
666 // constified.
667 if (GT && GQT.isConstQualified() && GT->isArithmeticType())
668 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
669 else
670 sReg = getGlobalsRegion();
671 }
672
673 // Finally handle static locals.
674 } else {
675 // FIXME: Once we implement scope handling, we will need to properly lookup
676 // 'D' to the proper LocationContext.
677 const DeclContext *DC = D->getDeclContext();
678 const StackFrameContext *STC = LC->getStackFrameForDeclContext(DC);
679
680 if (!STC)
681 sReg = getUnknownRegion();
682 else {
683 if (D->hasLocalStorage()) {
684 sReg = isa<ParmVarDecl>(D) || isa<ImplicitParamDecl>(D)
685 ? static_cast<const MemRegion*>(getStackArgumentsRegion(STC))
686 : static_cast<const MemRegion*>(getStackLocalsRegion(STC));
687 }
688 else {
689 assert(D->isStaticLocal());
690 const Decl *D = STC->getDecl();
691 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D))
692 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
693 getFunctionTextRegion(FD));
694 else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) {
695 const BlockTextRegion *BTR =
696 getBlockTextRegion(BD,
697 C.getCanonicalType(BD->getSignatureAsWritten()->getType()),
698 STC->getAnalysisDeclContext());
699 sReg = getGlobalsRegion(MemRegion::StaticGlobalSpaceRegionKind,
700 BTR);
701 }
702 else {
703 // FIXME: For ObjC-methods, we need a new CodeTextRegion. For now
704 // just use the main global memspace.
705 sReg = getGlobalsRegion();
706 }
707 }
708 }
709 }
710
711 return getSubRegion<VarRegion>(D, sReg);
712 }
713
getVarRegion(const VarDecl * D,const MemRegion * superR)714 const VarRegion *MemRegionManager::getVarRegion(const VarDecl *D,
715 const MemRegion *superR) {
716 return getSubRegion<VarRegion>(D, superR);
717 }
718
719 const BlockDataRegion *
getBlockDataRegion(const BlockTextRegion * BC,const LocationContext * LC)720 MemRegionManager::getBlockDataRegion(const BlockTextRegion *BC,
721 const LocationContext *LC) {
722 const MemRegion *sReg = 0;
723 const BlockDecl *BD = BC->getDecl();
724 if (!BD->hasCaptures()) {
725 // This handles 'static' blocks.
726 sReg = getGlobalsRegion(MemRegion::GlobalImmutableSpaceRegionKind);
727 }
728 else {
729 if (LC) {
730 // FIXME: Once we implement scope handling, we want the parent region
731 // to be the scope.
732 const StackFrameContext *STC = LC->getCurrentStackFrame();
733 assert(STC);
734 sReg = getStackLocalsRegion(STC);
735 }
736 else {
737 // We allow 'LC' to be NULL for cases where want BlockDataRegions
738 // without context-sensitivity.
739 sReg = getUnknownRegion();
740 }
741 }
742
743 return getSubRegion<BlockDataRegion>(BC, LC, sReg);
744 }
745
746 const CompoundLiteralRegion*
getCompoundLiteralRegion(const CompoundLiteralExpr * CL,const LocationContext * LC)747 MemRegionManager::getCompoundLiteralRegion(const CompoundLiteralExpr *CL,
748 const LocationContext *LC) {
749
750 const MemRegion *sReg = 0;
751
752 if (CL->isFileScope())
753 sReg = getGlobalsRegion();
754 else {
755 const StackFrameContext *STC = LC->getCurrentStackFrame();
756 assert(STC);
757 sReg = getStackLocalsRegion(STC);
758 }
759
760 return getSubRegion<CompoundLiteralRegion>(CL, sReg);
761 }
762
763 const ElementRegion*
getElementRegion(QualType elementType,NonLoc Idx,const MemRegion * superRegion,ASTContext & Ctx)764 MemRegionManager::getElementRegion(QualType elementType, NonLoc Idx,
765 const MemRegion* superRegion,
766 ASTContext &Ctx){
767
768 QualType T = Ctx.getCanonicalType(elementType).getUnqualifiedType();
769
770 llvm::FoldingSetNodeID ID;
771 ElementRegion::ProfileRegion(ID, T, Idx, superRegion);
772
773 void *InsertPos;
774 MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
775 ElementRegion* R = cast_or_null<ElementRegion>(data);
776
777 if (!R) {
778 R = (ElementRegion*) A.Allocate<ElementRegion>();
779 new (R) ElementRegion(T, Idx, superRegion);
780 Regions.InsertNode(R, InsertPos);
781 }
782
783 return R;
784 }
785
786 const FunctionTextRegion *
getFunctionTextRegion(const FunctionDecl * FD)787 MemRegionManager::getFunctionTextRegion(const FunctionDecl *FD) {
788 return getSubRegion<FunctionTextRegion>(FD, getCodeRegion());
789 }
790
791 const BlockTextRegion *
getBlockTextRegion(const BlockDecl * BD,CanQualType locTy,AnalysisDeclContext * AC)792 MemRegionManager::getBlockTextRegion(const BlockDecl *BD, CanQualType locTy,
793 AnalysisDeclContext *AC) {
794 return getSubRegion<BlockTextRegion>(BD, locTy, AC, getCodeRegion());
795 }
796
797
798 /// getSymbolicRegion - Retrieve or create a "symbolic" memory region.
getSymbolicRegion(SymbolRef sym)799 const SymbolicRegion *MemRegionManager::getSymbolicRegion(SymbolRef sym) {
800 return getSubRegion<SymbolicRegion>(sym, getUnknownRegion());
801 }
802
803 const FieldRegion*
getFieldRegion(const FieldDecl * d,const MemRegion * superRegion)804 MemRegionManager::getFieldRegion(const FieldDecl *d,
805 const MemRegion* superRegion){
806 return getSubRegion<FieldRegion>(d, superRegion);
807 }
808
809 const ObjCIvarRegion*
getObjCIvarRegion(const ObjCIvarDecl * d,const MemRegion * superRegion)810 MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl *d,
811 const MemRegion* superRegion) {
812 return getSubRegion<ObjCIvarRegion>(d, superRegion);
813 }
814
815 const CXXTempObjectRegion*
getCXXTempObjectRegion(Expr const * E,LocationContext const * LC)816 MemRegionManager::getCXXTempObjectRegion(Expr const *E,
817 LocationContext const *LC) {
818 const StackFrameContext *SFC = LC->getCurrentStackFrame();
819 assert(SFC);
820 return getSubRegion<CXXTempObjectRegion>(E, getStackLocalsRegion(SFC));
821 }
822
823 const CXXBaseObjectRegion *
getCXXBaseObjectRegion(const CXXRecordDecl * decl,const MemRegion * superRegion)824 MemRegionManager::getCXXBaseObjectRegion(const CXXRecordDecl *decl,
825 const MemRegion *superRegion) {
826 return getSubRegion<CXXBaseObjectRegion>(decl, superRegion);
827 }
828
829 const CXXThisRegion*
getCXXThisRegion(QualType thisPointerTy,const LocationContext * LC)830 MemRegionManager::getCXXThisRegion(QualType thisPointerTy,
831 const LocationContext *LC) {
832 const StackFrameContext *STC = LC->getCurrentStackFrame();
833 assert(STC);
834 const PointerType *PT = thisPointerTy->getAs<PointerType>();
835 assert(PT);
836 return getSubRegion<CXXThisRegion>(PT, getStackArgumentsRegion(STC));
837 }
838
839 const AllocaRegion*
getAllocaRegion(const Expr * E,unsigned cnt,const LocationContext * LC)840 MemRegionManager::getAllocaRegion(const Expr *E, unsigned cnt,
841 const LocationContext *LC) {
842 const StackFrameContext *STC = LC->getCurrentStackFrame();
843 assert(STC);
844 return getSubRegion<AllocaRegion>(E, cnt, getStackLocalsRegion(STC));
845 }
846
getMemorySpace() const847 const MemSpaceRegion *MemRegion::getMemorySpace() const {
848 const MemRegion *R = this;
849 const SubRegion* SR = dyn_cast<SubRegion>(this);
850
851 while (SR) {
852 R = SR->getSuperRegion();
853 SR = dyn_cast<SubRegion>(R);
854 }
855
856 return dyn_cast<MemSpaceRegion>(R);
857 }
858
hasStackStorage() const859 bool MemRegion::hasStackStorage() const {
860 return isa<StackSpaceRegion>(getMemorySpace());
861 }
862
hasStackNonParametersStorage() const863 bool MemRegion::hasStackNonParametersStorage() const {
864 return isa<StackLocalsSpaceRegion>(getMemorySpace());
865 }
866
hasStackParametersStorage() const867 bool MemRegion::hasStackParametersStorage() const {
868 return isa<StackArgumentsSpaceRegion>(getMemorySpace());
869 }
870
hasGlobalsOrParametersStorage() const871 bool MemRegion::hasGlobalsOrParametersStorage() const {
872 const MemSpaceRegion *MS = getMemorySpace();
873 return isa<StackArgumentsSpaceRegion>(MS) ||
874 isa<GlobalsSpaceRegion>(MS);
875 }
876
877 // getBaseRegion strips away all elements and fields, and get the base region
878 // of them.
getBaseRegion() const879 const MemRegion *MemRegion::getBaseRegion() const {
880 const MemRegion *R = this;
881 while (true) {
882 switch (R->getKind()) {
883 case MemRegion::ElementRegionKind:
884 case MemRegion::FieldRegionKind:
885 case MemRegion::ObjCIvarRegionKind:
886 case MemRegion::CXXBaseObjectRegionKind:
887 R = cast<SubRegion>(R)->getSuperRegion();
888 continue;
889 default:
890 break;
891 }
892 break;
893 }
894 return R;
895 }
896
897 //===----------------------------------------------------------------------===//
898 // View handling.
899 //===----------------------------------------------------------------------===//
900
StripCasts() const901 const MemRegion *MemRegion::StripCasts() const {
902 const MemRegion *R = this;
903 while (true) {
904 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
905 // FIXME: generalize. Essentially we want to strip away ElementRegions
906 // that were layered on a symbolic region because of casts. We only
907 // want to strip away ElementRegions, however, where the index is 0.
908 SVal index = ER->getIndex();
909 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
910 if (CI->getValue().getSExtValue() == 0) {
911 R = ER->getSuperRegion();
912 continue;
913 }
914 }
915 }
916 break;
917 }
918 return R;
919 }
920
921 // FIXME: Merge with the implementation of the same method in Store.cpp
IsCompleteType(ASTContext & Ctx,QualType Ty)922 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
923 if (const RecordType *RT = Ty->getAs<RecordType>()) {
924 const RecordDecl *D = RT->getDecl();
925 if (!D->getDefinition())
926 return false;
927 }
928
929 return true;
930 }
931
getAsArrayOffset() const932 RegionRawOffset ElementRegion::getAsArrayOffset() const {
933 CharUnits offset = CharUnits::Zero();
934 const ElementRegion *ER = this;
935 const MemRegion *superR = NULL;
936 ASTContext &C = getContext();
937
938 // FIXME: Handle multi-dimensional arrays.
939
940 while (ER) {
941 superR = ER->getSuperRegion();
942
943 // FIXME: generalize to symbolic offsets.
944 SVal index = ER->getIndex();
945 if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
946 // Update the offset.
947 int64_t i = CI->getValue().getSExtValue();
948
949 if (i != 0) {
950 QualType elemType = ER->getElementType();
951
952 // If we are pointing to an incomplete type, go no further.
953 if (!IsCompleteType(C, elemType)) {
954 superR = ER;
955 break;
956 }
957
958 CharUnits size = C.getTypeSizeInChars(elemType);
959 offset += (i * size);
960 }
961
962 // Go to the next ElementRegion (if any).
963 ER = dyn_cast<ElementRegion>(superR);
964 continue;
965 }
966
967 return NULL;
968 }
969
970 assert(superR && "super region cannot be NULL");
971 return RegionRawOffset(superR, offset);
972 }
973
getAsOffset() const974 RegionOffset MemRegion::getAsOffset() const {
975 const MemRegion *R = this;
976 int64_t Offset = 0;
977
978 while (1) {
979 switch (R->getKind()) {
980 default:
981 return RegionOffset(0);
982 case SymbolicRegionKind:
983 case AllocaRegionKind:
984 case CompoundLiteralRegionKind:
985 case CXXThisRegionKind:
986 case StringRegionKind:
987 case VarRegionKind:
988 case CXXTempObjectRegionKind:
989 goto Finish;
990 case ElementRegionKind: {
991 const ElementRegion *ER = cast<ElementRegion>(R);
992 QualType EleTy = ER->getValueType();
993
994 if (!IsCompleteType(getContext(), EleTy))
995 return RegionOffset(0);
996
997 SVal Index = ER->getIndex();
998 if (const nonloc::ConcreteInt *CI=dyn_cast<nonloc::ConcreteInt>(&Index)) {
999 int64_t i = CI->getValue().getSExtValue();
1000 CharUnits Size = getContext().getTypeSizeInChars(EleTy);
1001 Offset += i * Size.getQuantity() * 8;
1002 } else {
1003 // We cannot compute offset for non-concrete index.
1004 return RegionOffset(0);
1005 }
1006 R = ER->getSuperRegion();
1007 break;
1008 }
1009 case FieldRegionKind: {
1010 const FieldRegion *FR = cast<FieldRegion>(R);
1011 const RecordDecl *RD = FR->getDecl()->getParent();
1012 if (!RD->isCompleteDefinition())
1013 // We cannot compute offset for incomplete type.
1014 return RegionOffset(0);
1015 // Get the field number.
1016 unsigned idx = 0;
1017 for (RecordDecl::field_iterator FI = RD->field_begin(),
1018 FE = RD->field_end(); FI != FE; ++FI, ++idx)
1019 if (FR->getDecl() == *FI)
1020 break;
1021
1022 const ASTRecordLayout &Layout = getContext().getASTRecordLayout(RD);
1023 // This is offset in bits.
1024 Offset += Layout.getFieldOffset(idx);
1025 R = FR->getSuperRegion();
1026 break;
1027 }
1028 }
1029 }
1030
1031 Finish:
1032 return RegionOffset(R, Offset);
1033 }
1034
1035 //===----------------------------------------------------------------------===//
1036 // BlockDataRegion
1037 //===----------------------------------------------------------------------===//
1038
LazyInitializeReferencedVars()1039 void BlockDataRegion::LazyInitializeReferencedVars() {
1040 if (ReferencedVars)
1041 return;
1042
1043 AnalysisDeclContext *AC = getCodeRegion()->getAnalysisDeclContext();
1044 AnalysisDeclContext::referenced_decls_iterator I, E;
1045 llvm::tie(I, E) = AC->getReferencedBlockVars(BC->getDecl());
1046
1047 if (I == E) {
1048 ReferencedVars = (void*) 0x1;
1049 return;
1050 }
1051
1052 MemRegionManager &MemMgr = *getMemRegionManager();
1053 llvm::BumpPtrAllocator &A = MemMgr.getAllocator();
1054 BumpVectorContext BC(A);
1055
1056 typedef BumpVector<const MemRegion*> VarVec;
1057 VarVec *BV = (VarVec*) A.Allocate<VarVec>();
1058 new (BV) VarVec(BC, E - I);
1059
1060 for ( ; I != E; ++I) {
1061 const VarDecl *VD = *I;
1062 const VarRegion *VR = 0;
1063
1064 if (!VD->getAttr<BlocksAttr>() && VD->hasLocalStorage())
1065 VR = MemMgr.getVarRegion(VD, this);
1066 else {
1067 if (LC)
1068 VR = MemMgr.getVarRegion(VD, LC);
1069 else {
1070 VR = MemMgr.getVarRegion(VD, MemMgr.getUnknownRegion());
1071 }
1072 }
1073
1074 assert(VR);
1075 BV->push_back(VR, BC);
1076 }
1077
1078 ReferencedVars = BV;
1079 }
1080
1081 BlockDataRegion::referenced_vars_iterator
referenced_vars_begin() const1082 BlockDataRegion::referenced_vars_begin() const {
1083 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1084
1085 BumpVector<const MemRegion*> *Vec =
1086 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1087
1088 return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ?
1089 NULL : Vec->begin());
1090 }
1091
1092 BlockDataRegion::referenced_vars_iterator
referenced_vars_end() const1093 BlockDataRegion::referenced_vars_end() const {
1094 const_cast<BlockDataRegion*>(this)->LazyInitializeReferencedVars();
1095
1096 BumpVector<const MemRegion*> *Vec =
1097 static_cast<BumpVector<const MemRegion*>*>(ReferencedVars);
1098
1099 return BlockDataRegion::referenced_vars_iterator(Vec == (void*) 0x1 ?
1100 NULL : Vec->end());
1101 }
1102