Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 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 "llvm/Support/raw_ostream.h" |
| 17 | #include "clang/Analysis/PathSensitive/MemRegion.h" |
| 18 | |
| 19 | using namespace clang; |
| 20 | |
| 21 | |
| 22 | MemRegion::~MemRegion() {} |
| 23 | |
| 24 | void MemSpaceRegion::Profile(llvm::FoldingSetNodeID& ID) const { |
| 25 | ID.AddInteger((unsigned)getKind()); |
| 26 | } |
| 27 | |
Zhongxing Xu | e9f4e54 | 2008-10-25 14:13:41 +0000 | [diff] [blame] | 28 | void StringRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, |
| 29 | const StringLiteral* Str, |
| 30 | const MemRegion* superRegion) { |
| 31 | ID.AddInteger((unsigned) StringRegionKind); |
| 32 | ID.AddPointer(Str); |
| 33 | ID.AddPointer(superRegion); |
| 34 | } |
| 35 | |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 36 | void AnonTypedRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, QualType T, |
| 37 | const MemRegion* superRegion) { |
| 38 | ID.AddInteger((unsigned) AnonTypedRegionKind); |
| 39 | ID.Add(T); |
| 40 | ID.AddPointer(superRegion); |
| 41 | } |
| 42 | |
Zhongxing Xu | 1789275 | 2008-10-08 02:50:44 +0000 | [diff] [blame] | 43 | void AnonPointeeRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, |
| 44 | const VarDecl* VD, QualType T, |
| 45 | const MemRegion* superRegion) { |
| 46 | ID.AddInteger((unsigned) AnonPointeeRegionKind); |
| 47 | ID.Add(T); |
| 48 | ID.AddPointer(VD); |
| 49 | ID.AddPointer(superRegion); |
| 50 | } |
| 51 | |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 52 | void AnonTypedRegion::Profile(llvm::FoldingSetNodeID& ID) const { |
| 53 | AnonTypedRegion::ProfileRegion(ID, T, superRegion); |
| 54 | } |
| 55 | |
| 56 | void DeclRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D, |
| 57 | const MemRegion* superRegion, Kind k) { |
| 58 | ID.AddInteger((unsigned) k); |
| 59 | ID.AddPointer(D); |
| 60 | ID.AddPointer(superRegion); |
| 61 | } |
| 62 | |
| 63 | void DeclRegion::Profile(llvm::FoldingSetNodeID& ID) const { |
| 64 | DeclRegion::ProfileRegion(ID, D, superRegion, getKind()); |
| 65 | } |
| 66 | |
Ted Kremenek | 993f1c7 | 2008-10-17 20:28:54 +0000 | [diff] [blame] | 67 | void SymbolicRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolID sym) { |
| 68 | ID.AddInteger((unsigned) MemRegion::SymbolicRegionKind); |
| 69 | ID.AddInteger(sym.getNumber()); |
| 70 | } |
| 71 | |
| 72 | void SymbolicRegion::Profile(llvm::FoldingSetNodeID& ID) const { |
| 73 | SymbolicRegion::ProfileRegion(ID, sym); |
| 74 | } |
| 75 | |
Zhongxing Xu | 511191c | 2008-10-21 05:27:10 +0000 | [diff] [blame] | 76 | void ElementRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, SVal Idx, |
| 77 | const MemRegion* superRegion) { |
| 78 | ID.AddInteger(MemRegion::ElementRegionKind); |
| 79 | ID.AddPointer(superRegion); |
| 80 | Idx.Profile(ID); |
| 81 | } |
| 82 | |
| 83 | void ElementRegion::Profile(llvm::FoldingSetNodeID& ID) const { |
| 84 | ElementRegion::ProfileRegion(ID, Index, superRegion); |
| 85 | } |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 86 | //===----------------------------------------------------------------------===// |
| 87 | // Region pretty-printing. |
| 88 | //===----------------------------------------------------------------------===// |
| 89 | |
| 90 | std::string MemRegion::getString() const { |
| 91 | std::string s; |
| 92 | llvm::raw_string_ostream os(s); |
| 93 | print(os); |
| 94 | return os.str(); |
| 95 | } |
| 96 | |
| 97 | void MemRegion::print(llvm::raw_ostream& os) const { |
| 98 | os << "<Unknown Region>"; |
| 99 | } |
| 100 | |
| 101 | void VarRegion::print(llvm::raw_ostream& os) const { |
| 102 | os << cast<VarDecl>(D)->getName(); |
| 103 | } |
| 104 | |
Ted Kremenek | 993f1c7 | 2008-10-17 20:28:54 +0000 | [diff] [blame] | 105 | void SymbolicRegion::print(llvm::raw_ostream& os) const { |
| 106 | os << "$" << sym.getNumber(); |
| 107 | } |
| 108 | |
Ted Kremenek | 4bd1eef | 2008-10-17 21:05:44 +0000 | [diff] [blame] | 109 | void FieldRegion::print(llvm::raw_ostream& os) const { |
| 110 | superRegion->print(os); |
| 111 | os << "->" << getDecl()->getName(); |
| 112 | } |
| 113 | |
Zhongxing Xu | b21ff77 | 2008-10-24 06:30:07 +0000 | [diff] [blame] | 114 | void ElementRegion::print(llvm::raw_ostream& os) const { |
| 115 | superRegion->print(os); |
| 116 | os << '['; Index.print(os); os << ']'; |
| 117 | } |
| 118 | |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 119 | //===----------------------------------------------------------------------===// |
| 120 | // MemRegionManager methods. |
| 121 | //===----------------------------------------------------------------------===// |
| 122 | |
| 123 | MemSpaceRegion* MemRegionManager::LazyAllocate(MemSpaceRegion*& region) { |
| 124 | |
| 125 | if (!region) { |
| 126 | region = (MemSpaceRegion*) A.Allocate<MemSpaceRegion>(); |
| 127 | new (region) MemSpaceRegion(); |
| 128 | } |
| 129 | |
| 130 | return region; |
| 131 | } |
| 132 | |
| 133 | MemSpaceRegion* MemRegionManager::getStackRegion() { |
| 134 | return LazyAllocate(stack); |
| 135 | } |
| 136 | |
| 137 | MemSpaceRegion* MemRegionManager::getGlobalsRegion() { |
| 138 | return LazyAllocate(globals); |
| 139 | } |
| 140 | |
| 141 | MemSpaceRegion* MemRegionManager::getHeapRegion() { |
| 142 | return LazyAllocate(heap); |
| 143 | } |
| 144 | |
Zhongxing Xu | 1789275 | 2008-10-08 02:50:44 +0000 | [diff] [blame] | 145 | MemSpaceRegion* MemRegionManager::getUnknownRegion() { |
| 146 | return LazyAllocate(unknown); |
| 147 | } |
| 148 | |
Zhongxing Xu | e9f4e54 | 2008-10-25 14:13:41 +0000 | [diff] [blame] | 149 | StringRegion* MemRegionManager::getStringRegion(const StringLiteral* Str) { |
| 150 | llvm::FoldingSetNodeID ID; |
| 151 | MemSpaceRegion* GlobalsR = getGlobalsRegion(); |
| 152 | |
| 153 | StringRegion::ProfileRegion(ID, Str, GlobalsR); |
| 154 | |
| 155 | void* InsertPos; |
| 156 | MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); |
| 157 | StringRegion* R = cast_or_null<StringRegion>(data); |
| 158 | |
| 159 | if (!R) { |
| 160 | R = (StringRegion*) A.Allocate<StringRegion>(); |
| 161 | new (R) StringRegion(Str, GlobalsR); |
| 162 | Regions.InsertNode(R, InsertPos); |
| 163 | } |
| 164 | |
| 165 | return R; |
| 166 | } |
| 167 | |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 168 | VarRegion* MemRegionManager::getVarRegion(const VarDecl* d, |
Ted Kremenek | 993f1c7 | 2008-10-17 20:28:54 +0000 | [diff] [blame] | 169 | const MemRegion* superRegion) { |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 170 | llvm::FoldingSetNodeID ID; |
| 171 | DeclRegion::ProfileRegion(ID, d, superRegion, MemRegion::VarRegionKind); |
| 172 | |
| 173 | void* InsertPos; |
| 174 | MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); |
| 175 | VarRegion* R = cast_or_null<VarRegion>(data); |
| 176 | |
| 177 | if (!R) { |
| 178 | R = (VarRegion*) A.Allocate<VarRegion>(); |
| 179 | new (R) VarRegion(d, superRegion); |
| 180 | Regions.InsertNode(R, InsertPos); |
| 181 | } |
| 182 | |
| 183 | return R; |
| 184 | } |
| 185 | |
Zhongxing Xu | 511191c | 2008-10-21 05:27:10 +0000 | [diff] [blame] | 186 | ElementRegion* MemRegionManager::getElementRegion(SVal Idx, |
| 187 | const MemRegion* superRegion){ |
| 188 | llvm::FoldingSetNodeID ID; |
| 189 | ElementRegion::ProfileRegion(ID, Idx, superRegion); |
| 190 | |
| 191 | void* InsertPos; |
| 192 | MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); |
| 193 | ElementRegion* R = cast_or_null<ElementRegion>(data); |
| 194 | |
| 195 | if (!R) { |
| 196 | R = (ElementRegion*) A.Allocate<ElementRegion>(); |
| 197 | new (R) ElementRegion(Idx, superRegion); |
| 198 | Regions.InsertNode(R, InsertPos); |
| 199 | } |
| 200 | |
| 201 | return R; |
| 202 | } |
| 203 | |
Ted Kremenek | 993f1c7 | 2008-10-17 20:28:54 +0000 | [diff] [blame] | 204 | /// getSymbolicRegion - Retrieve or create a "symbolic" memory region. |
| 205 | SymbolicRegion* MemRegionManager::getSymbolicRegion(const SymbolID sym) { |
| 206 | |
| 207 | llvm::FoldingSetNodeID ID; |
| 208 | SymbolicRegion::ProfileRegion(ID, sym); |
| 209 | |
| 210 | void* InsertPos; |
| 211 | MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); |
| 212 | SymbolicRegion* R = cast_or_null<SymbolicRegion>(data); |
| 213 | |
| 214 | if (!R) { |
| 215 | R = (SymbolicRegion*) A.Allocate<SymbolicRegion>(); |
| 216 | new (R) SymbolicRegion(sym); |
| 217 | Regions.InsertNode(R, InsertPos); |
| 218 | } |
| 219 | |
| 220 | return R; |
| 221 | } |
| 222 | |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 223 | FieldRegion* MemRegionManager::getFieldRegion(const FieldDecl* d, |
Ted Kremenek | 993f1c7 | 2008-10-17 20:28:54 +0000 | [diff] [blame] | 224 | const MemRegion* superRegion) { |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 225 | llvm::FoldingSetNodeID ID; |
| 226 | DeclRegion::ProfileRegion(ID, d, superRegion, MemRegion::FieldRegionKind); |
| 227 | |
| 228 | void* InsertPos; |
| 229 | MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); |
| 230 | FieldRegion* R = cast_or_null<FieldRegion>(data); |
| 231 | |
| 232 | if (!R) { |
| 233 | R = (FieldRegion*) A.Allocate<FieldRegion>(); |
| 234 | new (R) FieldRegion(d, superRegion); |
| 235 | Regions.InsertNode(R, InsertPos); |
| 236 | } |
| 237 | |
| 238 | return R; |
| 239 | } |
| 240 | |
Ted Kremenek | 993f1c7 | 2008-10-17 20:28:54 +0000 | [diff] [blame] | 241 | ObjCIvarRegion* |
| 242 | MemRegionManager::getObjCIvarRegion(const ObjCIvarDecl* d, |
| 243 | const MemRegion* superRegion) { |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 244 | llvm::FoldingSetNodeID ID; |
| 245 | DeclRegion::ProfileRegion(ID, d, superRegion, MemRegion::ObjCIvarRegionKind); |
| 246 | |
| 247 | void* InsertPos; |
| 248 | MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); |
| 249 | ObjCIvarRegion* R = cast_or_null<ObjCIvarRegion>(data); |
| 250 | |
| 251 | if (!R) { |
Zhongxing Xu | 722c288 | 2008-10-06 03:03:33 +0000 | [diff] [blame] | 252 | R = (ObjCIvarRegion*) A.Allocate<ObjCIvarRegion>(); |
| 253 | new (R) ObjCIvarRegion(d, superRegion); |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 254 | Regions.InsertNode(R, InsertPos); |
| 255 | } |
| 256 | |
| 257 | return R; |
| 258 | } |
| 259 | |
Ted Kremenek | a7f1b9e | 2008-10-24 20:30:08 +0000 | [diff] [blame] | 260 | ObjCObjectRegion* |
| 261 | MemRegionManager::getObjCObjectRegion(const ObjCInterfaceDecl* d, |
| 262 | const MemRegion* superRegion) { |
| 263 | llvm::FoldingSetNodeID ID; |
| 264 | DeclRegion::ProfileRegion(ID, d, superRegion, |
| 265 | MemRegion::ObjCObjectRegionKind); |
| 266 | |
| 267 | void* InsertPos; |
| 268 | MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); |
| 269 | ObjCObjectRegion* R = cast_or_null<ObjCObjectRegion>(data); |
| 270 | |
| 271 | if (!R) { |
| 272 | R = (ObjCObjectRegion*) A.Allocate<ObjCObjectRegion>(); |
| 273 | new (R) ObjCObjectRegion(d, superRegion); |
| 274 | Regions.InsertNode(R, InsertPos); |
| 275 | } |
| 276 | |
| 277 | return R; |
| 278 | } |
| 279 | |
| 280 | |
Zhongxing Xu | 1789275 | 2008-10-08 02:50:44 +0000 | [diff] [blame] | 281 | AnonPointeeRegion* MemRegionManager::getAnonPointeeRegion(const VarDecl* d) { |
| 282 | llvm::FoldingSetNodeID ID; |
| 283 | QualType T = d->getType(); |
| 284 | QualType PointeeType = cast<PointerType>(T.getTypePtr())->getPointeeType(); |
| 285 | MemRegion* superRegion = getUnknownRegion(); |
| 286 | |
| 287 | AnonPointeeRegion::ProfileRegion(ID, d, PointeeType, superRegion); |
| 288 | |
| 289 | void* InsertPos; |
| 290 | MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos); |
| 291 | AnonPointeeRegion* R = cast_or_null<AnonPointeeRegion>(data); |
| 292 | |
| 293 | if (!R) { |
| 294 | R = (AnonPointeeRegion*) A.Allocate<AnonPointeeRegion>(); |
| 295 | new (R) AnonPointeeRegion(d, PointeeType, superRegion); |
| 296 | Regions.InsertNode(R, InsertPos); |
| 297 | } |
| 298 | |
| 299 | return R; |
| 300 | } |
| 301 | |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 302 | bool MemRegionManager::hasStackStorage(const MemRegion* R) { |
Ted Kremenek | 993f1c7 | 2008-10-17 20:28:54 +0000 | [diff] [blame] | 303 | const SubRegion* SR = dyn_cast<SubRegion>(R); |
| 304 | |
| 305 | // Only subregions can have stack storage. |
| 306 | if (!SR) |
| 307 | return false; |
| 308 | |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 309 | MemSpaceRegion* S = getStackRegion(); |
| 310 | |
Ted Kremenek | 993f1c7 | 2008-10-17 20:28:54 +0000 | [diff] [blame] | 311 | while (SR) { |
| 312 | R = SR->getSuperRegion(); |
| 313 | if (R == S) |
| 314 | return true; |
| 315 | |
| 316 | SR = dyn_cast<SubRegion>(R); |
Ted Kremenek | 9e24049 | 2008-10-04 05:50:14 +0000 | [diff] [blame] | 317 | } |
| 318 | |
| 319 | return false; |
| 320 | } |