clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ThreadSafetyCommon.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model static -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libclangAnalysis/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libclangAnalysis/../../../llvm/clang/include -I /usr/src/gnu/usr.bin/clang/libclangAnalysis/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libclangAnalysis/../include -I /usr/src/gnu/usr.bin/clang/libclangAnalysis/obj -I /usr/src/gnu/usr.bin/clang/libclangAnalysis/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libclangAnalysis/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -stack-protector 2 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libclangAnalysis/../../../llvm/clang/lib/Analysis/ThreadSafetyCommon.cpp
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | #include "clang/Analysis/Analyses/ThreadSafetyCommon.h" |
14 | #include "clang/AST/Attr.h" |
15 | #include "clang/AST/Decl.h" |
16 | #include "clang/AST/DeclCXX.h" |
17 | #include "clang/AST/DeclGroup.h" |
18 | #include "clang/AST/DeclObjC.h" |
19 | #include "clang/AST/Expr.h" |
20 | #include "clang/AST/ExprCXX.h" |
21 | #include "clang/AST/OperationKinds.h" |
22 | #include "clang/AST/Stmt.h" |
23 | #include "clang/AST/Type.h" |
24 | #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" |
25 | #include "clang/Analysis/CFG.h" |
26 | #include "clang/Basic/LLVM.h" |
27 | #include "clang/Basic/OperatorKinds.h" |
28 | #include "clang/Basic/Specifiers.h" |
29 | #include "llvm/ADT/StringExtras.h" |
30 | #include "llvm/ADT/StringRef.h" |
31 | #include "llvm/Support/Casting.h" |
32 | #include <algorithm> |
33 | #include <cassert> |
34 | #include <string> |
35 | #include <utility> |
36 | |
37 | using namespace clang; |
38 | using namespace threadSafety; |
39 | |
40 | |
41 | std::string threadSafety::getSourceLiteralString(const Expr *CE) { |
42 | switch (CE->getStmtClass()) { |
43 | case Stmt::IntegerLiteralClass: |
44 | return toString(cast<IntegerLiteral>(CE)->getValue(), 10, true); |
45 | case Stmt::StringLiteralClass: { |
46 | std::string ret("\""); |
47 | ret += cast<StringLiteral>(CE)->getString(); |
48 | ret += "\""; |
49 | return ret; |
50 | } |
51 | case Stmt::CharacterLiteralClass: |
52 | case Stmt::CXXNullPtrLiteralExprClass: |
53 | case Stmt::GNUNullExprClass: |
54 | case Stmt::CXXBoolLiteralExprClass: |
55 | case Stmt::FloatingLiteralClass: |
56 | case Stmt::ImaginaryLiteralClass: |
57 | case Stmt::ObjCStringLiteralClass: |
58 | default: |
59 | return "#lit"; |
60 | } |
61 | } |
62 | |
63 | |
64 | static bool isIncompletePhi(const til::SExpr *E) { |
65 | if (const auto *Ph = dyn_cast<til::Phi>(E)) |
66 | return Ph->status() == til::Phi::PH_Incomplete; |
67 | return false; |
68 | } |
69 | |
70 | using CallingContext = SExprBuilder::CallingContext; |
71 | |
72 | til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) { |
73 | auto It = SMap.find(S); |
74 | if (It != SMap.end()) |
75 | return It->second; |
76 | return nullptr; |
77 | } |
78 | |
79 | til::SCFG *SExprBuilder::buildCFG(CFGWalker &Walker) { |
80 | Walker.walk(*this); |
| 1 | Calling 'CFGWalker::walk' | |
|
81 | return Scfg; |
82 | } |
83 | |
84 | static bool isCalleeArrow(const Expr *E) { |
85 | const auto *ME = dyn_cast<MemberExpr>(E->IgnoreParenCasts()); |
86 | return ME ? ME->isArrow() : false; |
87 | } |
88 | |
89 | |
90 | |
91 | |
92 | |
93 | |
94 | |
95 | |
96 | CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp, |
97 | const NamedDecl *D, |
98 | const Expr *DeclExp, |
99 | VarDecl *SelfDecl) { |
100 | |
101 | if (!DeclExp) |
102 | return translateAttrExpr(AttrExp, nullptr); |
103 | |
104 | CallingContext Ctx(nullptr, D); |
105 | |
106 | |
107 | |
108 | if (const auto *ME = dyn_cast<MemberExpr>(DeclExp)) { |
109 | Ctx.SelfArg = ME->getBase(); |
110 | Ctx.SelfArrow = ME->isArrow(); |
111 | } else if (const auto *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) { |
112 | Ctx.SelfArg = CE->getImplicitObjectArgument(); |
113 | Ctx.SelfArrow = isCalleeArrow(CE->getCallee()); |
114 | Ctx.NumArgs = CE->getNumArgs(); |
115 | Ctx.FunArgs = CE->getArgs(); |
116 | } else if (const auto *CE = dyn_cast<CallExpr>(DeclExp)) { |
117 | Ctx.NumArgs = CE->getNumArgs(); |
118 | Ctx.FunArgs = CE->getArgs(); |
119 | } else if (const auto *CE = dyn_cast<CXXConstructExpr>(DeclExp)) { |
120 | Ctx.SelfArg = nullptr; |
121 | Ctx.NumArgs = CE->getNumArgs(); |
122 | Ctx.FunArgs = CE->getArgs(); |
123 | } else if (D && isa<CXXDestructorDecl>(D)) { |
124 | |
125 | Ctx.SelfArg = DeclExp; |
126 | } |
127 | |
128 | |
129 | |
130 | if (SelfDecl && !Ctx.SelfArg) { |
131 | DeclRefExpr SelfDRE(SelfDecl->getASTContext(), SelfDecl, false, |
132 | SelfDecl->getType(), VK_LValue, |
133 | SelfDecl->getLocation()); |
134 | Ctx.SelfArg = &SelfDRE; |
135 | |
136 | |
137 | if (!AttrExp) |
138 | return translateAttrExpr(Ctx.SelfArg, nullptr); |
139 | else |
140 | return translateAttrExpr(AttrExp, &Ctx); |
141 | } |
142 | |
143 | |
144 | if (!AttrExp) |
145 | return translateAttrExpr(Ctx.SelfArg, nullptr); |
146 | else |
147 | return translateAttrExpr(AttrExp, &Ctx); |
148 | } |
149 | |
150 | |
151 | |
152 | CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp, |
153 | CallingContext *Ctx) { |
154 | if (!AttrExp) |
155 | return CapabilityExpr(nullptr, false); |
156 | |
157 | if (const auto* SLit = dyn_cast<StringLiteral>(AttrExp)) { |
158 | if (SLit->getString() == StringRef("*")) |
159 | |
160 | |
161 | return CapabilityExpr(new (Arena) til::Wildcard(), false); |
162 | else |
163 | |
164 | return CapabilityExpr(nullptr, false); |
165 | } |
166 | |
167 | bool Neg = false; |
168 | if (const auto *OE = dyn_cast<CXXOperatorCallExpr>(AttrExp)) { |
169 | if (OE->getOperator() == OO_Exclaim) { |
170 | Neg = true; |
171 | AttrExp = OE->getArg(0); |
172 | } |
173 | } |
174 | else if (const auto *UO = dyn_cast<UnaryOperator>(AttrExp)) { |
175 | if (UO->getOpcode() == UO_LNot) { |
176 | Neg = true; |
177 | AttrExp = UO->getSubExpr(); |
178 | } |
179 | } |
180 | |
181 | til::SExpr *E = translate(AttrExp, Ctx); |
182 | |
183 | |
184 | |
185 | if (!E || isa<til::Literal>(E)) |
186 | return CapabilityExpr(nullptr, false); |
187 | |
188 | |
189 | if (const auto *CE = dyn_cast<til::Cast>(E)) { |
190 | if (CE->castOpcode() == til::CAST_objToPtr) |
191 | return CapabilityExpr(CE->expr(), Neg); |
192 | } |
193 | return CapabilityExpr(E, Neg); |
194 | } |
195 | |
196 | |
197 | |
198 | |
199 | til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) { |
200 | if (!S) |
201 | return nullptr; |
202 | |
203 | |
204 | |
205 | if (til::SExpr *E = lookupStmt(S)) |
206 | return E; |
207 | |
208 | switch (S->getStmtClass()) { |
209 | case Stmt::DeclRefExprClass: |
210 | return translateDeclRefExpr(cast<DeclRefExpr>(S), Ctx); |
211 | case Stmt::CXXThisExprClass: |
212 | return translateCXXThisExpr(cast<CXXThisExpr>(S), Ctx); |
213 | case Stmt::MemberExprClass: |
214 | return translateMemberExpr(cast<MemberExpr>(S), Ctx); |
215 | case Stmt::ObjCIvarRefExprClass: |
216 | return translateObjCIVarRefExpr(cast<ObjCIvarRefExpr>(S), Ctx); |
217 | case Stmt::CallExprClass: |
218 | return translateCallExpr(cast<CallExpr>(S), Ctx); |
219 | case Stmt::CXXMemberCallExprClass: |
220 | return translateCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), Ctx); |
221 | case Stmt::CXXOperatorCallExprClass: |
222 | return translateCXXOperatorCallExpr(cast<CXXOperatorCallExpr>(S), Ctx); |
223 | case Stmt::UnaryOperatorClass: |
224 | return translateUnaryOperator(cast<UnaryOperator>(S), Ctx); |
225 | case Stmt::BinaryOperatorClass: |
226 | case Stmt::CompoundAssignOperatorClass: |
227 | return translateBinaryOperator(cast<BinaryOperator>(S), Ctx); |
228 | |
229 | case Stmt::ArraySubscriptExprClass: |
230 | return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx); |
231 | case Stmt::ConditionalOperatorClass: |
232 | return translateAbstractConditionalOperator( |
233 | cast<ConditionalOperator>(S), Ctx); |
234 | case Stmt::BinaryConditionalOperatorClass: |
235 | return translateAbstractConditionalOperator( |
236 | cast<BinaryConditionalOperator>(S), Ctx); |
237 | |
238 | |
239 | case Stmt::ConstantExprClass: |
240 | return translate(cast<ConstantExpr>(S)->getSubExpr(), Ctx); |
241 | case Stmt::ParenExprClass: |
242 | return translate(cast<ParenExpr>(S)->getSubExpr(), Ctx); |
243 | case Stmt::ExprWithCleanupsClass: |
244 | return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx); |
245 | case Stmt::CXXBindTemporaryExprClass: |
246 | return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx); |
247 | case Stmt::MaterializeTemporaryExprClass: |
248 | return translate(cast<MaterializeTemporaryExpr>(S)->getSubExpr(), Ctx); |
249 | |
250 | |
251 | case Stmt::CharacterLiteralClass: |
252 | case Stmt::CXXNullPtrLiteralExprClass: |
253 | case Stmt::GNUNullExprClass: |
254 | case Stmt::CXXBoolLiteralExprClass: |
255 | case Stmt::FloatingLiteralClass: |
256 | case Stmt::ImaginaryLiteralClass: |
257 | case Stmt::IntegerLiteralClass: |
258 | case Stmt::StringLiteralClass: |
259 | case Stmt::ObjCStringLiteralClass: |
260 | return new (Arena) til::Literal(cast<Expr>(S)); |
261 | |
262 | case Stmt::DeclStmtClass: |
263 | return translateDeclStmt(cast<DeclStmt>(S), Ctx); |
264 | default: |
265 | break; |
266 | } |
267 | if (const auto *CE = dyn_cast<CastExpr>(S)) |
268 | return translateCastExpr(CE, Ctx); |
269 | |
270 | return new (Arena) til::Undefined(S); |
271 | } |
272 | |
273 | til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE, |
274 | CallingContext *Ctx) { |
275 | const auto *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl()); |
276 | |
277 | |
278 | if (const auto *PV = dyn_cast<ParmVarDecl>(VD)) { |
279 | unsigned I = PV->getFunctionScopeIndex(); |
280 | const DeclContext *D = PV->getDeclContext(); |
281 | if (Ctx && Ctx->FunArgs) { |
282 | const Decl *Canonical = Ctx->AttrDecl->getCanonicalDecl(); |
283 | if (isa<FunctionDecl>(D) |
284 | ? (cast<FunctionDecl>(D)->getCanonicalDecl() == Canonical) |
285 | : (cast<ObjCMethodDecl>(D)->getCanonicalDecl() == Canonical)) { |
286 | |
287 | assert(I < Ctx->NumArgs); |
288 | return translate(Ctx->FunArgs[I], Ctx->Prev); |
289 | } |
290 | } |
291 | |
292 | |
293 | VD = isa<FunctionDecl>(D) |
294 | ? cast<FunctionDecl>(D)->getCanonicalDecl()->getParamDecl(I) |
295 | : cast<ObjCMethodDecl>(D)->getCanonicalDecl()->getParamDecl(I); |
296 | } |
297 | |
298 | |
299 | return new (Arena) til::LiteralPtr(VD); |
300 | } |
301 | |
302 | til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE, |
303 | CallingContext *Ctx) { |
304 | |
305 | if (Ctx && Ctx->SelfArg) |
306 | return translate(Ctx->SelfArg, Ctx->Prev); |
307 | assert(SelfVar && "We have no variable for 'this'!"); |
308 | return SelfVar; |
309 | } |
310 | |
311 | static const ValueDecl *getValueDeclFromSExpr(const til::SExpr *E) { |
312 | if (const auto *V = dyn_cast<til::Variable>(E)) |
313 | return V->clangDecl(); |
314 | if (const auto *Ph = dyn_cast<til::Phi>(E)) |
315 | return Ph->clangDecl(); |
316 | if (const auto *P = dyn_cast<til::Project>(E)) |
317 | return P->clangDecl(); |
318 | if (const auto *L = dyn_cast<til::LiteralPtr>(E)) |
319 | return L->clangDecl(); |
320 | return nullptr; |
321 | } |
322 | |
323 | static bool hasAnyPointerType(const til::SExpr *E) { |
324 | auto *VD = getValueDeclFromSExpr(E); |
325 | if (VD && VD->getType()->isAnyPointerType()) |
326 | return true; |
327 | if (const auto *C = dyn_cast<til::Cast>(E)) |
328 | return C->castOpcode() == til::CAST_objToPtr; |
329 | |
330 | return false; |
331 | } |
332 | |
333 | |
334 | static const CXXMethodDecl *getFirstVirtualDecl(const CXXMethodDecl *D) { |
335 | while (true) { |
336 | D = D->getCanonicalDecl(); |
337 | auto OverriddenMethods = D->overridden_methods(); |
338 | if (OverriddenMethods.begin() == OverriddenMethods.end()) |
339 | return D; |
340 | |
341 | D = *OverriddenMethods.begin(); |
342 | } |
343 | return nullptr; |
344 | } |
345 | |
346 | til::SExpr *SExprBuilder::translateMemberExpr(const MemberExpr *ME, |
347 | CallingContext *Ctx) { |
348 | til::SExpr *BE = translate(ME->getBase(), Ctx); |
349 | til::SExpr *E = new (Arena) til::SApply(BE); |
350 | |
351 | const auto *D = cast<ValueDecl>(ME->getMemberDecl()->getCanonicalDecl()); |
352 | if (const auto *VD = dyn_cast<CXXMethodDecl>(D)) |
353 | D = getFirstVirtualDecl(VD); |
354 | |
355 | til::Project *P = new (Arena) til::Project(E, D); |
356 | if (hasAnyPointerType(BE)) |
357 | P->setArrow(true); |
358 | return P; |
359 | } |
360 | |
361 | til::SExpr *SExprBuilder::translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE, |
362 | CallingContext *Ctx) { |
363 | til::SExpr *BE = translate(IVRE->getBase(), Ctx); |
364 | til::SExpr *E = new (Arena) til::SApply(BE); |
365 | |
366 | const auto *D = cast<ObjCIvarDecl>(IVRE->getDecl()->getCanonicalDecl()); |
367 | |
368 | til::Project *P = new (Arena) til::Project(E, D); |
369 | if (hasAnyPointerType(BE)) |
370 | P->setArrow(true); |
371 | return P; |
372 | } |
373 | |
374 | til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE, |
375 | CallingContext *Ctx, |
376 | const Expr *SelfE) { |
377 | if (CapabilityExprMode) { |
378 | |
379 | if (const FunctionDecl *FD = CE->getDirectCallee()) { |
380 | FD = FD->getMostRecentDecl(); |
381 | if (LockReturnedAttr *At = FD->getAttr<LockReturnedAttr>()) { |
382 | CallingContext LRCallCtx(Ctx); |
383 | LRCallCtx.AttrDecl = CE->getDirectCallee(); |
384 | LRCallCtx.SelfArg = SelfE; |
385 | LRCallCtx.NumArgs = CE->getNumArgs(); |
386 | LRCallCtx.FunArgs = CE->getArgs(); |
387 | return const_cast<til::SExpr *>( |
388 | translateAttrExpr(At->getArg(), &LRCallCtx).sexpr()); |
389 | } |
390 | } |
391 | } |
392 | |
393 | til::SExpr *E = translate(CE->getCallee(), Ctx); |
394 | for (const auto *Arg : CE->arguments()) { |
395 | til::SExpr *A = translate(Arg, Ctx); |
396 | E = new (Arena) til::Apply(E, A); |
397 | } |
398 | return new (Arena) til::Call(E, CE); |
399 | } |
400 | |
401 | til::SExpr *SExprBuilder::translateCXXMemberCallExpr( |
402 | const CXXMemberCallExpr *ME, CallingContext *Ctx) { |
403 | if (CapabilityExprMode) { |
404 | |
405 | if (ME->getMethodDecl()->getNameAsString() == "get" && |
406 | ME->getNumArgs() == 0) { |
407 | auto *E = translate(ME->getImplicitObjectArgument(), Ctx); |
408 | return new (Arena) til::Cast(til::CAST_objToPtr, E); |
409 | |
410 | } |
411 | } |
412 | return translateCallExpr(cast<CallExpr>(ME), Ctx, |
413 | ME->getImplicitObjectArgument()); |
414 | } |
415 | |
416 | til::SExpr *SExprBuilder::translateCXXOperatorCallExpr( |
417 | const CXXOperatorCallExpr *OCE, CallingContext *Ctx) { |
418 | if (CapabilityExprMode) { |
419 | |
420 | OverloadedOperatorKind k = OCE->getOperator(); |
421 | if (k == OO_Star || k == OO_Arrow) { |
422 | auto *E = translate(OCE->getArg(0), Ctx); |
423 | return new (Arena) til::Cast(til::CAST_objToPtr, E); |
424 | |
425 | } |
426 | } |
427 | return translateCallExpr(cast<CallExpr>(OCE), Ctx); |
428 | } |
429 | |
430 | til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO, |
431 | CallingContext *Ctx) { |
432 | switch (UO->getOpcode()) { |
433 | case UO_PostInc: |
434 | case UO_PostDec: |
435 | case UO_PreInc: |
436 | case UO_PreDec: |
437 | return new (Arena) til::Undefined(UO); |
438 | |
439 | case UO_AddrOf: |
440 | if (CapabilityExprMode) { |
441 | |
442 | if (const auto *DRE = dyn_cast<DeclRefExpr>(UO->getSubExpr())) { |
443 | if (DRE->getDecl()->isCXXInstanceMember()) { |
444 | |
445 | |
446 | auto *W = new (Arena) til::Wildcard(); |
447 | return new (Arena) til::Project(W, DRE->getDecl()); |
448 | } |
449 | } |
450 | } |
451 | |
452 | return translate(UO->getSubExpr(), Ctx); |
453 | |
454 | |
455 | case UO_Deref: |
456 | case UO_Plus: |
457 | return translate(UO->getSubExpr(), Ctx); |
458 | |
459 | case UO_Minus: |
460 | return new (Arena) |
461 | til::UnaryOp(til::UOP_Minus, translate(UO->getSubExpr(), Ctx)); |
462 | case UO_Not: |
463 | return new (Arena) |
464 | til::UnaryOp(til::UOP_BitNot, translate(UO->getSubExpr(), Ctx)); |
465 | case UO_LNot: |
466 | return new (Arena) |
467 | til::UnaryOp(til::UOP_LogicNot, translate(UO->getSubExpr(), Ctx)); |
468 | |
469 | |
470 | case UO_Real: |
471 | case UO_Imag: |
472 | case UO_Extension: |
473 | case UO_Coawait: |
474 | return new (Arena) til::Undefined(UO); |
475 | } |
476 | return new (Arena) til::Undefined(UO); |
477 | } |
478 | |
479 | til::SExpr *SExprBuilder::translateBinOp(til::TIL_BinaryOpcode Op, |
480 | const BinaryOperator *BO, |
481 | CallingContext *Ctx, bool Reverse) { |
482 | til::SExpr *E0 = translate(BO->getLHS(), Ctx); |
483 | til::SExpr *E1 = translate(BO->getRHS(), Ctx); |
484 | if (Reverse) |
485 | return new (Arena) til::BinaryOp(Op, E1, E0); |
486 | else |
487 | return new (Arena) til::BinaryOp(Op, E0, E1); |
488 | } |
489 | |
490 | til::SExpr *SExprBuilder::translateBinAssign(til::TIL_BinaryOpcode Op, |
491 | const BinaryOperator *BO, |
492 | CallingContext *Ctx, |
493 | bool Assign) { |
494 | const Expr *LHS = BO->getLHS(); |
495 | const Expr *RHS = BO->getRHS(); |
496 | til::SExpr *E0 = translate(LHS, Ctx); |
497 | til::SExpr *E1 = translate(RHS, Ctx); |
498 | |
499 | const ValueDecl *VD = nullptr; |
500 | til::SExpr *CV = nullptr; |
501 | if (const auto *DRE = dyn_cast<DeclRefExpr>(LHS)) { |
502 | VD = DRE->getDecl(); |
503 | CV = lookupVarDecl(VD); |
504 | } |
505 | |
506 | if (!Assign) { |
507 | til::SExpr *Arg = CV ? CV : new (Arena) til::Load(E0); |
508 | E1 = new (Arena) til::BinaryOp(Op, Arg, E1); |
509 | E1 = addStatement(E1, nullptr, VD); |
510 | } |
511 | if (VD && CV) |
512 | return updateVarDecl(VD, E1); |
513 | return new (Arena) til::Store(E0, E1); |
514 | } |
515 | |
516 | til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO, |
517 | CallingContext *Ctx) { |
518 | switch (BO->getOpcode()) { |
519 | case BO_PtrMemD: |
520 | case BO_PtrMemI: |
521 | return new (Arena) til::Undefined(BO); |
522 | |
523 | case BO_Mul: return translateBinOp(til::BOP_Mul, BO, Ctx); |
524 | case BO_Div: return translateBinOp(til::BOP_Div, BO, Ctx); |
525 | case BO_Rem: return translateBinOp(til::BOP_Rem, BO, Ctx); |
526 | case BO_Add: return translateBinOp(til::BOP_Add, BO, Ctx); |
527 | case BO_Sub: return translateBinOp(til::BOP_Sub, BO, Ctx); |
528 | case BO_Shl: return translateBinOp(til::BOP_Shl, BO, Ctx); |
529 | case BO_Shr: return translateBinOp(til::BOP_Shr, BO, Ctx); |
530 | case BO_LT: return translateBinOp(til::BOP_Lt, BO, Ctx); |
531 | case BO_GT: return translateBinOp(til::BOP_Lt, BO, Ctx, true); |
532 | case BO_LE: return translateBinOp(til::BOP_Leq, BO, Ctx); |
533 | case BO_GE: return translateBinOp(til::BOP_Leq, BO, Ctx, true); |
534 | case BO_EQ: return translateBinOp(til::BOP_Eq, BO, Ctx); |
535 | case BO_NE: return translateBinOp(til::BOP_Neq, BO, Ctx); |
536 | case BO_Cmp: return translateBinOp(til::BOP_Cmp, BO, Ctx); |
537 | case BO_And: return translateBinOp(til::BOP_BitAnd, BO, Ctx); |
538 | case BO_Xor: return translateBinOp(til::BOP_BitXor, BO, Ctx); |
539 | case BO_Or: return translateBinOp(til::BOP_BitOr, BO, Ctx); |
540 | case BO_LAnd: return translateBinOp(til::BOP_LogicAnd, BO, Ctx); |
541 | case BO_LOr: return translateBinOp(til::BOP_LogicOr, BO, Ctx); |
542 | |
543 | case BO_Assign: return translateBinAssign(til::BOP_Eq, BO, Ctx, true); |
544 | case BO_MulAssign: return translateBinAssign(til::BOP_Mul, BO, Ctx); |
545 | case BO_DivAssign: return translateBinAssign(til::BOP_Div, BO, Ctx); |
546 | case BO_RemAssign: return translateBinAssign(til::BOP_Rem, BO, Ctx); |
547 | case BO_AddAssign: return translateBinAssign(til::BOP_Add, BO, Ctx); |
548 | case BO_SubAssign: return translateBinAssign(til::BOP_Sub, BO, Ctx); |
549 | case BO_ShlAssign: return translateBinAssign(til::BOP_Shl, BO, Ctx); |
550 | case BO_ShrAssign: return translateBinAssign(til::BOP_Shr, BO, Ctx); |
551 | case BO_AndAssign: return translateBinAssign(til::BOP_BitAnd, BO, Ctx); |
552 | case BO_XorAssign: return translateBinAssign(til::BOP_BitXor, BO, Ctx); |
553 | case BO_OrAssign: return translateBinAssign(til::BOP_BitOr, BO, Ctx); |
554 | |
555 | case BO_Comma: |
556 | |
557 | return translate(BO->getRHS(), Ctx); |
558 | } |
559 | return new (Arena) til::Undefined(BO); |
560 | } |
561 | |
562 | til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE, |
563 | CallingContext *Ctx) { |
564 | CastKind K = CE->getCastKind(); |
565 | switch (K) { |
566 | case CK_LValueToRValue: { |
567 | if (const auto *DRE = dyn_cast<DeclRefExpr>(CE->getSubExpr())) { |
568 | til::SExpr *E0 = lookupVarDecl(DRE->getDecl()); |
569 | if (E0) |
570 | return E0; |
571 | } |
572 | til::SExpr *E0 = translate(CE->getSubExpr(), Ctx); |
573 | return E0; |
574 | |
575 | |
576 | } |
577 | case CK_NoOp: |
578 | case CK_DerivedToBase: |
579 | case CK_UncheckedDerivedToBase: |
580 | case CK_ArrayToPointerDecay: |
581 | case CK_FunctionToPointerDecay: { |
582 | til::SExpr *E0 = translate(CE->getSubExpr(), Ctx); |
583 | return E0; |
584 | } |
585 | default: { |
586 | |
587 | til::SExpr *E0 = translate(CE->getSubExpr(), Ctx); |
588 | if (CapabilityExprMode) |
589 | return E0; |
590 | return new (Arena) til::Cast(til::CAST_none, E0); |
591 | } |
592 | } |
593 | } |
594 | |
595 | til::SExpr * |
596 | SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E, |
597 | CallingContext *Ctx) { |
598 | til::SExpr *E0 = translate(E->getBase(), Ctx); |
599 | til::SExpr *E1 = translate(E->getIdx(), Ctx); |
600 | return new (Arena) til::ArrayIndex(E0, E1); |
601 | } |
602 | |
603 | til::SExpr * |
604 | SExprBuilder::translateAbstractConditionalOperator( |
605 | const AbstractConditionalOperator *CO, CallingContext *Ctx) { |
606 | auto *C = translate(CO->getCond(), Ctx); |
607 | auto *T = translate(CO->getTrueExpr(), Ctx); |
608 | auto *E = translate(CO->getFalseExpr(), Ctx); |
609 | return new (Arena) til::IfThenElse(C, T, E); |
610 | } |
611 | |
612 | til::SExpr * |
613 | SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) { |
614 | DeclGroupRef DGrp = S->getDeclGroup(); |
615 | for (auto I : DGrp) { |
616 | if (auto *VD = dyn_cast_or_null<VarDecl>(I)) { |
617 | Expr *E = VD->getInit(); |
618 | til::SExpr* SE = translate(E, Ctx); |
619 | |
620 | |
621 | QualType T = VD->getType(); |
622 | if (T.isTrivialType(VD->getASTContext())) |
623 | return addVarDecl(VD, SE); |
624 | else { |
625 | |
626 | } |
627 | } |
628 | } |
629 | return nullptr; |
630 | } |
631 | |
632 | |
633 | |
634 | |
635 | |
636 | til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S, |
637 | const ValueDecl *VD) { |
638 | if (!E || !CurrentBB || E->block() || til::ThreadSafetyTIL::isTrivial(E)) |
639 | return E; |
640 | if (VD) |
641 | E = new (Arena) til::Variable(E, VD); |
642 | CurrentInstructions.push_back(E); |
643 | if (S) |
644 | insertStmt(S, E); |
645 | return E; |
646 | } |
647 | |
648 | |
649 | til::SExpr *SExprBuilder::lookupVarDecl(const ValueDecl *VD) { |
650 | auto It = LVarIdxMap.find(VD); |
651 | if (It != LVarIdxMap.end()) { |
652 | assert(CurrentLVarMap[It->second].first == VD); |
653 | return CurrentLVarMap[It->second].second; |
654 | } |
655 | return nullptr; |
656 | } |
657 | |
658 | |
659 | static void maybeUpdateVD(til::SExpr *E, const ValueDecl *VD) { |
660 | if (!E) |
661 | return; |
662 | if (auto *V = dyn_cast<til::Variable>(E)) { |
663 | if (!V->clangDecl()) |
664 | V->setClangDecl(VD); |
665 | } |
666 | } |
667 | |
668 | |
669 | til::SExpr *SExprBuilder::addVarDecl(const ValueDecl *VD, til::SExpr *E) { |
670 | maybeUpdateVD(E, VD); |
671 | LVarIdxMap.insert(std::make_pair(VD, CurrentLVarMap.size())); |
672 | CurrentLVarMap.makeWritable(); |
673 | CurrentLVarMap.push_back(std::make_pair(VD, E)); |
674 | return E; |
675 | } |
676 | |
677 | |
678 | til::SExpr *SExprBuilder::updateVarDecl(const ValueDecl *VD, til::SExpr *E) { |
679 | maybeUpdateVD(E, VD); |
680 | auto It = LVarIdxMap.find(VD); |
681 | if (It == LVarIdxMap.end()) { |
682 | til::SExpr *Ptr = new (Arena) til::LiteralPtr(VD); |
683 | til::SExpr *St = new (Arena) til::Store(Ptr, E); |
684 | return St; |
685 | } |
686 | CurrentLVarMap.makeWritable(); |
687 | CurrentLVarMap.elem(It->second).second = E; |
688 | return E; |
689 | } |
690 | |
691 | |
692 | |
693 | |
694 | void SExprBuilder::makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E) { |
695 | unsigned ArgIndex = CurrentBlockInfo->ProcessedPredecessors; |
696 | assert(ArgIndex > 0 && ArgIndex < NPreds); |
697 | |
698 | til::SExpr *CurrE = CurrentLVarMap[i].second; |
699 | if (CurrE->block() == CurrentBB) { |
| 24 | | Assuming the condition is true | |
|
| |
700 | |
701 | |
702 | auto *Ph = dyn_cast<til::Phi>(CurrE); |
| 26 | | Assuming 'CurrE' is not a 'Phi' | |
|
| 27 | | 'Ph' initialized to a null pointer value | |
|
703 | assert(Ph && "Expecting Phi node."); |
704 | if (E) |
| 28 | | Assuming 'E' is non-null | |
|
| |
705 | Ph->values()[ArgIndex] = E; |
| 30 | | Called C++ object pointer is null |
|
706 | return; |
707 | } |
708 | |
709 | |
710 | |
711 | til::Phi *Ph = new (Arena) til::Phi(Arena, NPreds); |
712 | Ph->values().setValues(NPreds, nullptr); |
713 | for (unsigned PIdx = 0; PIdx < ArgIndex; ++PIdx) |
714 | Ph->values()[PIdx] = CurrE; |
715 | if (E) |
716 | Ph->values()[ArgIndex] = E; |
717 | Ph->setClangDecl(CurrentLVarMap[i].first); |
718 | |
719 | |
720 | if (!E || isIncompletePhi(E) || isIncompletePhi(CurrE)) |
721 | Ph->setStatus(til::Phi::PH_Incomplete); |
722 | |
723 | |
724 | CurrentArguments.push_back(Ph); |
725 | if (Ph->status() == til::Phi::PH_Incomplete) |
726 | IncompleteArgs.push_back(Ph); |
727 | |
728 | CurrentLVarMap.makeWritable(); |
729 | CurrentLVarMap.elem(i).second = Ph; |
730 | } |
731 | |
732 | |
733 | |
734 | void SExprBuilder::mergeEntryMap(LVarDefinitionMap Map) { |
735 | assert(CurrentBlockInfo && "Not processing a block!"); |
736 | |
737 | if (!CurrentLVarMap.valid()) { |
| 13 | | Assuming the condition is false | |
|
| |
738 | |
739 | CurrentLVarMap = std::move(Map); |
740 | return; |
741 | } |
742 | if (CurrentLVarMap.sameAs(Map)) |
| 15 | | Assuming the condition is false | |
|
| |
743 | return; |
744 | |
745 | unsigned NPreds = CurrentBB->numPredecessors(); |
746 | unsigned ESz = CurrentLVarMap.size(); |
747 | unsigned MSz = Map.size(); |
748 | unsigned Sz = std::min(ESz, MSz); |
749 | |
750 | for (unsigned i = 0; i < Sz; ++i) { |
| |
| 18 | | Loop condition is true. Entering loop body | |
|
751 | if (CurrentLVarMap[i].first != Map[i].first) { |
| 19 | | Assuming 'CurrentLVarMap[i].first' is equal to 'Map[i].first' | |
|
| |
752 | |
753 | CurrentLVarMap.makeWritable(); |
754 | CurrentLVarMap.downsize(i); |
755 | break; |
756 | } |
757 | if (CurrentLVarMap[i].second != Map[i].second) |
| 21 | | Assuming 'CurrentLVarMap[i].second' is not equal to 'Map[i].second' | |
|
| |
758 | makePhiNodeVar(i, NPreds, Map[i].second); |
| 23 | | Calling 'SExprBuilder::makePhiNodeVar' | |
|
759 | } |
760 | if (ESz > MSz) { |
761 | CurrentLVarMap.makeWritable(); |
762 | CurrentLVarMap.downsize(Map.size()); |
763 | } |
764 | } |
765 | |
766 | |
767 | |
768 | void SExprBuilder::mergeEntryMapBackEdge() { |
769 | |
770 | |
771 | |
772 | |
773 | |
774 | |
775 | |
776 | |
777 | assert(CurrentBlockInfo && "Not processing a block!"); |
778 | |
779 | if (CurrentBlockInfo->HasBackEdges) |
780 | return; |
781 | CurrentBlockInfo->HasBackEdges = true; |
782 | |
783 | CurrentLVarMap.makeWritable(); |
784 | unsigned Sz = CurrentLVarMap.size(); |
785 | unsigned NPreds = CurrentBB->numPredecessors(); |
786 | |
787 | for (unsigned i = 0; i < Sz; ++i) |
788 | makePhiNodeVar(i, NPreds, nullptr); |
789 | } |
790 | |
791 | |
792 | |
793 | |
794 | void SExprBuilder::mergePhiNodesBackEdge(const CFGBlock *Blk) { |
795 | til::BasicBlock *BB = lookupBlock(Blk); |
796 | unsigned ArgIndex = BBInfo[Blk->getBlockID()].ProcessedPredecessors; |
797 | assert(ArgIndex > 0 && ArgIndex < BB->numPredecessors()); |
798 | |
799 | for (til::SExpr *PE : BB->arguments()) { |
800 | auto *Ph = dyn_cast_or_null<til::Phi>(PE); |
801 | assert(Ph && "Expecting Phi Node."); |
802 | assert(Ph->values()[ArgIndex] == nullptr && "Wrong index for back edge."); |
803 | |
804 | til::SExpr *E = lookupVarDecl(Ph->clangDecl()); |
805 | assert(E && "Couldn't find local variable for Phi node."); |
806 | Ph->values()[ArgIndex] = E; |
807 | } |
808 | } |
809 | |
810 | void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D, |
811 | const CFGBlock *First) { |
812 | |
813 | unsigned NBlocks = Cfg->getNumBlockIDs(); |
814 | Scfg = new (Arena) til::SCFG(Arena, NBlocks); |
815 | |
816 | |
817 | BBInfo.resize(NBlocks); |
818 | BlockMap.resize(NBlocks, nullptr); |
819 | |
820 | for (auto *B : *Cfg) { |
821 | auto *BB = new (Arena) til::BasicBlock(Arena); |
822 | BB->reserveInstructions(B->size()); |
823 | BlockMap[B->getBlockID()] = BB; |
824 | } |
825 | |
826 | CurrentBB = lookupBlock(&Cfg->getEntry()); |
827 | auto Parms = isa<ObjCMethodDecl>(D) ? cast<ObjCMethodDecl>(D)->parameters() |
828 | : cast<FunctionDecl>(D)->parameters(); |
829 | for (auto *Pm : Parms) { |
830 | QualType T = Pm->getType(); |
831 | if (!T.isTrivialType(Pm->getASTContext())) |
832 | continue; |
833 | |
834 | |
835 | |
836 | til::SExpr *Lp = new (Arena) til::LiteralPtr(Pm); |
837 | til::SExpr *Ld = new (Arena) til::Load(Lp); |
838 | til::SExpr *V = addStatement(Ld, nullptr, Pm); |
839 | addVarDecl(Pm, V); |
840 | } |
841 | } |
842 | |
843 | void SExprBuilder::enterCFGBlock(const CFGBlock *B) { |
844 | |
845 | CurrentBB = lookupBlock(B); |
846 | CurrentBB->reservePredecessors(B->pred_size()); |
847 | Scfg->add(CurrentBB); |
848 | |
849 | CurrentBlockInfo = &BBInfo[B->getBlockID()]; |
850 | |
851 | |
852 | |
853 | |
854 | } |
855 | |
856 | void SExprBuilder::handlePredecessor(const CFGBlock *Pred) { |
857 | |
858 | |
859 | CurrentBB->addPredecessor(BlockMap[Pred->getBlockID()]); |
860 | BlockInfo *PredInfo = &BBInfo[Pred->getBlockID()]; |
861 | assert(PredInfo->UnprocessedSuccessors > 0); |
862 | |
863 | if (--PredInfo->UnprocessedSuccessors == 0) |
| 10 | | Assuming the condition is false | |
|
| |
864 | mergeEntryMap(std::move(PredInfo->ExitMap)); |
865 | else |
866 | mergeEntryMap(PredInfo->ExitMap.clone()); |
| 12 | | Calling 'SExprBuilder::mergeEntryMap' | |
|
867 | |
868 | ++CurrentBlockInfo->ProcessedPredecessors; |
869 | } |
870 | |
871 | void SExprBuilder::handlePredecessorBackEdge(const CFGBlock *Pred) { |
872 | mergeEntryMapBackEdge(); |
873 | } |
874 | |
875 | void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) { |
876 | |
877 | |
878 | CurrentBB->arguments().reserve( |
879 | static_cast<unsigned>(CurrentArguments.size()), Arena); |
880 | for (auto *A : CurrentArguments) |
881 | CurrentBB->addArgument(A); |
882 | } |
883 | |
884 | void SExprBuilder::handleStatement(const Stmt *S) { |
885 | til::SExpr *E = translate(S, nullptr); |
886 | addStatement(E, S); |
887 | } |
888 | |
889 | void SExprBuilder::handleDestructorCall(const VarDecl *VD, |
890 | const CXXDestructorDecl *DD) { |
891 | til::SExpr *Sf = new (Arena) til::LiteralPtr(VD); |
892 | til::SExpr *Dr = new (Arena) til::LiteralPtr(DD); |
893 | til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf); |
894 | til::SExpr *E = new (Arena) til::Call(Ap); |
895 | addStatement(E, nullptr); |
896 | } |
897 | |
898 | void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) { |
899 | CurrentBB->instructions().reserve( |
900 | static_cast<unsigned>(CurrentInstructions.size()), Arena); |
901 | for (auto *V : CurrentInstructions) |
902 | CurrentBB->addInstruction(V); |
903 | |
904 | |
905 | unsigned N = B->succ_size(); |
906 | auto It = B->succ_begin(); |
907 | if (N == 1) { |
908 | til::BasicBlock *BB = *It ? lookupBlock(*It) : nullptr; |
909 | |
910 | unsigned Idx = BB ? BB->findPredecessorIndex(CurrentBB) : 0; |
911 | auto *Tm = new (Arena) til::Goto(BB, Idx); |
912 | CurrentBB->setTerminator(Tm); |
913 | } |
914 | else if (N == 2) { |
915 | til::SExpr *C = translate(B->getTerminatorCondition(true), nullptr); |
916 | til::BasicBlock *BB1 = *It ? lookupBlock(*It) : nullptr; |
917 | ++It; |
918 | til::BasicBlock *BB2 = *It ? lookupBlock(*It) : nullptr; |
919 | |
920 | auto *Tm = new (Arena) til::Branch(C, BB1, BB2); |
921 | CurrentBB->setTerminator(Tm); |
922 | } |
923 | } |
924 | |
925 | void SExprBuilder::handleSuccessor(const CFGBlock *Succ) { |
926 | ++CurrentBlockInfo->UnprocessedSuccessors; |
927 | } |
928 | |
929 | void SExprBuilder::handleSuccessorBackEdge(const CFGBlock *Succ) { |
930 | mergePhiNodesBackEdge(Succ); |
931 | ++BBInfo[Succ->getBlockID()].ProcessedPredecessors; |
932 | } |
933 | |
934 | void SExprBuilder::exitCFGBlock(const CFGBlock *B) { |
935 | CurrentArguments.clear(); |
936 | CurrentInstructions.clear(); |
937 | CurrentBlockInfo->ExitMap = std::move(CurrentLVarMap); |
938 | CurrentBB = nullptr; |
939 | CurrentBlockInfo = nullptr; |
940 | } |
941 | |
942 | void SExprBuilder::exitCFG(const CFGBlock *Last) { |
943 | for (auto *Ph : IncompleteArgs) { |
944 | if (Ph->status() == til::Phi::PH_Incomplete) |
945 | simplifyIncompleteArg(Ph); |
946 | } |
947 | |
948 | CurrentArguments.clear(); |
949 | CurrentInstructions.clear(); |
950 | IncompleteArgs.clear(); |
951 | } |
952 | |
953 | |
954 | |
955 | |
956 | |
957 | |
958 | |
959 | |
960 | |
961 | |
962 | |
963 | |
964 | |
965 | |
966 | |
967 | |
968 | |
969 | |
970 | |
971 | |
972 | |
973 | |
974 | |
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H |
22 | #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H |
23 | |
24 | #include "clang/AST/Decl.h" |
25 | #include "clang/Analysis/Analyses/PostOrderCFGView.h" |
26 | #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" |
27 | #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" |
28 | #include "clang/Analysis/Analyses/ThreadSafetyUtil.h" |
29 | #include "clang/Analysis/AnalysisDeclContext.h" |
30 | #include "clang/Analysis/CFG.h" |
31 | #include "clang/Basic/LLVM.h" |
32 | #include "llvm/ADT/DenseMap.h" |
33 | #include "llvm/ADT/SmallVector.h" |
34 | #include "llvm/Support/Casting.h" |
35 | #include <sstream> |
36 | #include <string> |
37 | #include <utility> |
38 | #include <vector> |
39 | |
40 | namespace clang { |
41 | |
42 | class AbstractConditionalOperator; |
43 | class ArraySubscriptExpr; |
44 | class BinaryOperator; |
45 | class CallExpr; |
46 | class CastExpr; |
47 | class CXXDestructorDecl; |
48 | class CXXMemberCallExpr; |
49 | class CXXOperatorCallExpr; |
50 | class CXXThisExpr; |
51 | class DeclRefExpr; |
52 | class DeclStmt; |
53 | class Expr; |
54 | class MemberExpr; |
55 | class Stmt; |
56 | class UnaryOperator; |
57 | |
58 | namespace threadSafety { |
59 | |
60 | |
61 | namespace sx { |
62 | |
63 | inline bool equals(const til::SExpr *E1, const til::SExpr *E2) { |
64 | return til::EqualsComparator::compareExprs(E1, E2); |
65 | } |
66 | |
67 | inline bool matches(const til::SExpr *E1, const til::SExpr *E2) { |
68 | |
69 | |
70 | |
71 | if (isa<til::Wildcard>(E1)) |
72 | return isa<til::Wildcard>(E2); |
73 | if (isa<til::Wildcard>(E2)) |
74 | return isa<til::Wildcard>(E1); |
75 | |
76 | return til::MatchComparator::compareExprs(E1, E2); |
77 | } |
78 | |
79 | inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) { |
80 | const auto *PE1 = dyn_cast_or_null<til::Project>(E1); |
81 | if (!PE1) |
82 | return false; |
83 | const auto *PE2 = dyn_cast_or_null<til::Project>(E2); |
84 | if (!PE2) |
85 | return false; |
86 | return PE1->clangDecl() == PE2->clangDecl(); |
87 | } |
88 | |
89 | inline std::string toString(const til::SExpr *E) { |
90 | std::stringstream ss; |
91 | til::StdPrinter::print(E, ss); |
92 | return ss.str(); |
93 | } |
94 | |
95 | } |
96 | |
97 | |
98 | |
99 | |
100 | class CFGVisitor { |
101 | |
102 | void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} |
103 | |
104 | |
105 | void enterCFGBlock(const CFGBlock *B) {} |
106 | |
107 | |
108 | bool visitPredecessors() { return true; } |
109 | |
110 | |
111 | void handlePredecessor(const CFGBlock *Pred) {} |
112 | |
113 | |
114 | void handlePredecessorBackEdge(const CFGBlock *Pred) {} |
115 | |
116 | |
117 | void enterCFGBlockBody(const CFGBlock *B) {} |
118 | |
119 | |
120 | void handleStatement(const Stmt *S) {} |
121 | |
122 | |
123 | void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} |
124 | |
125 | |
126 | void exitCFGBlockBody(const CFGBlock *B) {} |
127 | |
128 | |
129 | bool visitSuccessors() { return true; } |
130 | |
131 | |
132 | void handleSuccessor(const CFGBlock *Succ) {} |
133 | |
134 | |
135 | void handleSuccessorBackEdge(const CFGBlock *Succ) {} |
136 | |
137 | |
138 | void exitCFGBlock(const CFGBlock *B) {} |
139 | |
140 | |
141 | void exitCFG(const CFGBlock *Last) {} |
142 | }; |
143 | |
144 | |
145 | class CFGWalker { |
146 | public: |
147 | CFGWalker() = default; |
148 | |
149 | |
150 | |
151 | bool init(AnalysisDeclContext &AC) { |
152 | ACtx = &AC; |
153 | CFGraph = AC.getCFG(); |
154 | if (!CFGraph) |
155 | return false; |
156 | |
157 | |
158 | if (!dyn_cast_or_null<NamedDecl>(AC.getDecl())) |
159 | return false; |
160 | |
161 | SortedGraph = AC.getAnalysis<PostOrderCFGView>(); |
162 | if (!SortedGraph) |
163 | return false; |
164 | |
165 | return true; |
166 | } |
167 | |
168 | |
169 | template <class Visitor> |
170 | void walk(Visitor &V) { |
171 | PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); |
172 | |
173 | V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry()); |
174 | |
175 | for (const auto *CurrBlock : *SortedGraph) { |
176 | VisitedBlocks.insert(CurrBlock); |
177 | |
178 | V.enterCFGBlock(CurrBlock); |
179 | |
180 | |
181 | if (V.visitPredecessors()) { |
| |
182 | SmallVector<CFGBlock*, 4> BackEdges; |
183 | |
184 | for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(), |
| 4 | | Loop condition is true. Entering loop body | |
|
185 | SE = CurrBlock->pred_end(); |
186 | SI != SE; ++SI) { |
| 3 | | Assuming 'SI' is not equal to 'SE' | |
|
187 | if (*SI == nullptr) |
| 5 | | Assuming the condition is false | |
|
| |
188 | continue; |
189 | |
190 | if (!VisitedBlocks.alreadySet(*SI)) { |
| 7 | | Assuming the condition is false | |
|
| |
191 | BackEdges.push_back(*SI); |
192 | continue; |
193 | } |
194 | V.handlePredecessor(*SI); |
| 9 | | Calling 'SExprBuilder::handlePredecessor' | |
|
195 | } |
196 | |
197 | for (auto *Blk : BackEdges) |
198 | V.handlePredecessorBackEdge(Blk); |
199 | } |
200 | |
201 | V.enterCFGBlockBody(CurrBlock); |
202 | |
203 | |
204 | for (const auto &BI : *CurrBlock) { |
205 | switch (BI.getKind()) { |
206 | case CFGElement::Statement: |
207 | V.handleStatement(BI.castAs<CFGStmt>().getStmt()); |
208 | break; |
209 | |
210 | case CFGElement::AutomaticObjectDtor: { |
211 | CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); |
212 | auto *DD = const_cast<CXXDestructorDecl *>( |
213 | AD.getDestructorDecl(ACtx->getASTContext())); |
214 | auto *VD = const_cast<VarDecl *>(AD.getVarDecl()); |
215 | V.handleDestructorCall(VD, DD); |
216 | break; |
217 | } |
218 | default: |
219 | break; |
220 | } |
221 | } |
222 | |
223 | V.exitCFGBlockBody(CurrBlock); |
224 | |
225 | |
226 | if (V.visitSuccessors()) { |
227 | SmallVector<CFGBlock*, 8> ForwardEdges; |
228 | |
229 | |
230 | for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), |
231 | SE = CurrBlock->succ_end(); |
232 | SI != SE; ++SI) { |
233 | if (*SI == nullptr) |
234 | continue; |
235 | |
236 | if (!VisitedBlocks.alreadySet(*SI)) { |
237 | ForwardEdges.push_back(*SI); |
238 | continue; |
239 | } |
240 | V.handleSuccessorBackEdge(*SI); |
241 | } |
242 | |
243 | for (auto *Blk : ForwardEdges) |
244 | V.handleSuccessor(Blk); |
245 | } |
246 | |
247 | V.exitCFGBlock(CurrBlock); |
248 | } |
249 | V.exitCFG(&CFGraph->getExit()); |
250 | } |
251 | |
252 | const CFG *getGraph() const { return CFGraph; } |
253 | CFG *getGraph() { return CFGraph; } |
254 | |
255 | const NamedDecl *getDecl() const { |
256 | return dyn_cast<NamedDecl>(ACtx->getDecl()); |
257 | } |
258 | |
259 | const PostOrderCFGView *getSortedGraph() const { return SortedGraph; } |
260 | |
261 | private: |
262 | CFG *CFGraph = nullptr; |
263 | AnalysisDeclContext *ACtx = nullptr; |
264 | PostOrderCFGView *SortedGraph = nullptr; |
265 | }; |
266 | |
267 | |
268 | |
269 | |
270 | class CapabilityExpr { |
271 | private: |
272 | |
273 | const til::SExpr* CapExpr; |
274 | |
275 | |
276 | bool Negated; |
277 | |
278 | public: |
279 | CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {} |
280 | |
281 | const til::SExpr* sexpr() const { return CapExpr; } |
282 | bool negative() const { return Negated; } |
283 | |
284 | CapabilityExpr operator!() const { |
285 | return CapabilityExpr(CapExpr, !Negated); |
286 | } |
287 | |
288 | bool equals(const CapabilityExpr &other) const { |
289 | return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr); |
290 | } |
291 | |
292 | bool matches(const CapabilityExpr &other) const { |
293 | return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr); |
294 | } |
295 | |
296 | bool matchesUniv(const CapabilityExpr &CapE) const { |
297 | return isUniversal() || matches(CapE); |
298 | } |
299 | |
300 | bool partiallyMatches(const CapabilityExpr &other) const { |
301 | return (Negated == other.Negated) && |
302 | sx::partiallyMatches(CapExpr, other.CapExpr); |
303 | } |
304 | |
305 | const ValueDecl* valueDecl() const { |
306 | if (Negated || CapExpr == nullptr) |
307 | return nullptr; |
308 | if (const auto *P = dyn_cast<til::Project>(CapExpr)) |
309 | return P->clangDecl(); |
310 | if (const auto *P = dyn_cast<til::LiteralPtr>(CapExpr)) |
311 | return P->clangDecl(); |
312 | return nullptr; |
313 | } |
314 | |
315 | std::string toString() const { |
316 | if (Negated) |
317 | return "!" + sx::toString(CapExpr); |
318 | return sx::toString(CapExpr); |
319 | } |
320 | |
321 | bool shouldIgnore() const { return CapExpr == nullptr; } |
322 | |
323 | bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); } |
324 | |
325 | bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); } |
326 | }; |
327 | |
328 | |
329 | class SExprBuilder { |
330 | public: |
331 | |
332 | |
333 | |
334 | |
335 | |
336 | |
337 | |
338 | |
339 | |
340 | struct CallingContext { |
341 | |
342 | CallingContext *Prev; |
343 | |
344 | |
345 | const NamedDecl *AttrDecl; |
346 | |
347 | |
348 | const Expr *SelfArg = nullptr; |
349 | |
350 | |
351 | unsigned NumArgs = 0; |
352 | |
353 | |
354 | const Expr *const *FunArgs = nullptr; |
355 | |
356 | |
357 | bool SelfArrow = false; |
358 | |
359 | CallingContext(CallingContext *P, const NamedDecl *D = nullptr) |
360 | : Prev(P), AttrDecl(D) {} |
361 | }; |
362 | |
363 | SExprBuilder(til::MemRegionRef A) : Arena(A) { |
364 | |
365 | SelfVar = new (Arena) til::Variable(nullptr); |
366 | SelfVar->setKind(til::Variable::VK_SFun); |
367 | } |
368 | |
369 | |
370 | |
371 | CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, |
372 | const Expr *DeclExp, VarDecl *SelfD=nullptr); |
373 | |
374 | CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); |
375 | |
376 | |
377 | |
378 | |
379 | til::SExpr *translate(const Stmt *S, CallingContext *Ctx); |
380 | til::SCFG *buildCFG(CFGWalker &Walker); |
381 | |
382 | til::SExpr *lookupStmt(const Stmt *S); |
383 | |
384 | til::BasicBlock *lookupBlock(const CFGBlock *B) { |
385 | return BlockMap[B->getBlockID()]; |
386 | } |
387 | |
388 | const til::SCFG *getCFG() const { return Scfg; } |
389 | til::SCFG *getCFG() { return Scfg; } |
390 | |
391 | private: |
392 | |
393 | friend class CFGWalker; |
394 | |
395 | til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, |
396 | CallingContext *Ctx) ; |
397 | til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); |
398 | til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx); |
399 | til::SExpr *translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE, |
400 | CallingContext *Ctx); |
401 | til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx, |
402 | const Expr *SelfE = nullptr); |
403 | til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, |
404 | CallingContext *Ctx); |
405 | til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, |
406 | CallingContext *Ctx); |
407 | til::SExpr *translateUnaryOperator(const UnaryOperator *UO, |
408 | CallingContext *Ctx); |
409 | til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op, |
410 | const BinaryOperator *BO, |
411 | CallingContext *Ctx, bool Reverse = false); |
412 | til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op, |
413 | const BinaryOperator *BO, |
414 | CallingContext *Ctx, bool Assign = false); |
415 | til::SExpr *translateBinaryOperator(const BinaryOperator *BO, |
416 | CallingContext *Ctx); |
417 | til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx); |
418 | til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E, |
419 | CallingContext *Ctx); |
420 | til::SExpr *translateAbstractConditionalOperator( |
421 | const AbstractConditionalOperator *C, CallingContext *Ctx); |
422 | |
423 | til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); |
424 | |
425 | |
426 | using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>; |
427 | |
428 | |
429 | using LVarIndexMap = llvm::DenseMap<const ValueDecl *, unsigned>; |
430 | |
431 | |
432 | using NameVarPair = std::pair<const ValueDecl *, til::SExpr *>; |
433 | using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>; |
434 | |
435 | struct BlockInfo { |
436 | LVarDefinitionMap ExitMap; |
437 | bool HasBackEdges = false; |
438 | |
439 | |
440 | unsigned UnprocessedSuccessors = 0; |
441 | |
442 | |
443 | unsigned ProcessedPredecessors = 0; |
444 | |
445 | BlockInfo() = default; |
446 | BlockInfo(BlockInfo &&) = default; |
447 | BlockInfo &operator=(BlockInfo &&) = default; |
448 | }; |
449 | |
450 | void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); |
451 | void enterCFGBlock(const CFGBlock *B); |
452 | bool visitPredecessors() { return true; } |
453 | void handlePredecessor(const CFGBlock *Pred); |
454 | void handlePredecessorBackEdge(const CFGBlock *Pred); |
455 | void enterCFGBlockBody(const CFGBlock *B); |
456 | void handleStatement(const Stmt *S); |
457 | void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD); |
458 | void exitCFGBlockBody(const CFGBlock *B); |
459 | bool visitSuccessors() { return true; } |
460 | void handleSuccessor(const CFGBlock *Succ); |
461 | void handleSuccessorBackEdge(const CFGBlock *Succ); |
462 | void exitCFGBlock(const CFGBlock *B); |
463 | void exitCFG(const CFGBlock *Last); |
464 | |
465 | void insertStmt(const Stmt *S, til::SExpr *E) { |
466 | SMap.insert(std::make_pair(S, E)); |
467 | } |
468 | |
469 | til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); |
470 | |
471 | til::SExpr *addStatement(til::SExpr *E, const Stmt *S, |
472 | const ValueDecl *VD = nullptr); |
473 | til::SExpr *lookupVarDecl(const ValueDecl *VD); |
474 | til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E); |
475 | til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E); |
476 | |
477 | void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E); |
478 | void mergeEntryMap(LVarDefinitionMap Map); |
479 | void mergeEntryMapBackEdge(); |
480 | void mergePhiNodesBackEdge(const CFGBlock *Blk); |
481 | |
482 | private: |
483 | |
484 | |
485 | static const bool CapabilityExprMode = true; |
486 | |
487 | til::MemRegionRef Arena; |
488 | |
489 | |
490 | til::Variable *SelfVar = nullptr; |
491 | |
492 | til::SCFG *Scfg = nullptr; |
493 | |
494 | |
495 | StatementMap SMap; |
496 | |
497 | |
498 | LVarIndexMap LVarIdxMap; |
499 | |
500 | |
501 | std::vector<til::BasicBlock *> BlockMap; |
502 | |
503 | |
504 | std::vector<BlockInfo> BBInfo; |
505 | |
506 | LVarDefinitionMap CurrentLVarMap; |
507 | std::vector<til::Phi *> CurrentArguments; |
508 | std::vector<til::SExpr *> CurrentInstructions; |
509 | std::vector<til::Phi *> IncompleteArgs; |
510 | til::BasicBlock *CurrentBB = nullptr; |
511 | BlockInfo *CurrentBlockInfo = nullptr; |
512 | }; |
513 | |
514 | |
515 | void printSCFG(CFGWalker &Walker); |
516 | |
517 | } |
518 | } |
519 | |
520 | #endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H |