clang 24.0.0git
ThreadSafetyCommon.cpp
Go to the documentation of this file.
1//===- ThreadSafetyCommon.cpp ---------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Implementation of the interfaces declared in ThreadSafetyCommon.h
10//
11//===----------------------------------------------------------------------===//
12
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"
22#include "clang/AST/Stmt.h"
23#include "clang/AST/Type.h"
25#include "clang/Analysis/CFG.h"
26#include "clang/Basic/LLVM.h"
29#include "llvm/ADT/ScopeExit.h"
30#include "llvm/ADT/StringExtras.h"
31#include "llvm/ADT/StringRef.h"
32#include <algorithm>
33#include <cassert>
34#include <string>
35#include <utility>
36
37using namespace clang;
38using namespace threadSafety;
39
40// From ThreadSafetyUtil.h
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// Return true if E is a variable that points to an incomplete Phi node.
64static 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
70static constexpr std::pair<StringRef, bool> ClassifyCapabilityFallback{
71 /*Kind=*/StringRef("mutex"),
72 /*Reentrant=*/false};
73
74// Returns pair (Kind, Reentrant).
75static std::pair<StringRef, bool> classifyCapability(const TypeDecl &TD) {
76 if (const auto *CA = TD.getAttr<CapabilityAttr>())
77 return {CA->getName(), TD.hasAttr<ReentrantCapabilityAttr>()};
78
80}
81
82// Returns pair (Kind, Reentrant).
83static std::pair<StringRef, bool> classifyCapability(QualType QT) {
84 // We need to look at the declaration of the type of the value to determine
85 // which it is. The type should either be a record or a typedef, or a pointer
86 // or reference thereof.
87 if (const auto *RD = QT->getAsRecordDecl())
88 return classifyCapability(*RD);
89 if (const auto *TT = QT->getAs<TypedefType>())
90 return classifyCapability(*TT->getDecl());
93
95}
96
98 const auto &[Kind, Reentrant] = classifyCapability(QT);
99 *this = CapabilityExpr(E, Kind, Neg, Reentrant);
100}
101
103
104til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) { return SMap.lookup(S); }
105
107 Walker.walk(*this);
108 return Scfg;
109}
110
111/// If CE calls through a function pointer field D, return the member access
112/// through which the field was reached; its base is the implicit object
113/// ('this') for the attributes on the field.
115 const NamedDecl *D) {
116 if (!isa<FieldDecl>(D))
117 return nullptr;
118 // Look through the operators that CallExpr::getCalleeDecl looks through
119 // when it finds D, e.g. in `(*dev->lock)()`.
120 const Expr *Callee = CE->getCallee()->IgnoreParenCasts();
121 while (const auto *UO = dyn_cast<UnaryOperator>(Callee)) {
122 if (UO->getOpcode() != UO_Deref && UO->getOpcode() != UO_AddrOf &&
123 UO->getOpcode() != UO_Plus)
124 break;
125 Callee = UO->getSubExpr()->IgnoreParenCasts();
126 }
127 return dyn_cast<MemberExpr>(Callee);
128}
129
130/// Translate a clang expression in an attribute to a til::SExpr.
131/// Constructs the context from D, DeclExp, and SelfDecl.
132///
133/// \param AttrExp The expression to translate.
134/// \param D The declaration to which the attribute is attached.
135/// \param DeclExp An expression involving the Decl to which the attribute
136/// is attached. E.g. the call to a function.
137/// \param Self S-expression to substitute for a \ref CXXThisExpr in a call,
138/// or argument to a cleanup function.
140 const NamedDecl *D,
141 const Expr *DeclExp,
142 til::SExpr *Self) {
143 // If we are processing a raw attribute expression, with no substitutions.
144 if (!DeclExp && !Self)
145 return translateAttrExpr(AttrExp, nullptr);
146
147 CallingContext Ctx(nullptr, D);
148
149 // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute
150 // for formal parameters when we call buildMutexID later.
151 if (!DeclExp)
152 /* We'll use Self. */;
153 else if (const auto *ME = dyn_cast<MemberExpr>(DeclExp)) {
154 Ctx.SelfArg = ME->getBase();
155 } else if (const auto *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) {
156 Ctx.SelfArg = CE->getImplicitObjectArgument();
157 Ctx.NumArgs = CE->getNumArgs();
158 Ctx.FunArgs = CE->getArgs();
159 } else if (const auto *CE = dyn_cast<CallExpr>(DeclExp)) {
160 // Calls to operators that are members need to be treated like member calls.
162 Ctx.SelfArg = CE->getArg(0);
163 Ctx.NumArgs = CE->getNumArgs() - 1;
164 Ctx.FunArgs = CE->getArgs() + 1;
165 } else {
166 if (const MemberExpr *ME = getFunPtrFieldCallee(CE, D))
167 Ctx.SelfArg = ME->getBase();
168 Ctx.NumArgs = CE->getNumArgs();
169 Ctx.FunArgs = CE->getArgs();
170 }
171 } else if (const auto *CE = dyn_cast<CXXConstructExpr>(DeclExp)) {
172 Ctx.SelfArg = nullptr; // Will be set below
173 Ctx.NumArgs = CE->getNumArgs();
174 Ctx.FunArgs = CE->getArgs();
175 }
176
177 // Usually we want to substitute the self-argument for "this", but lambdas
178 // are an exception: "this" on or in a lambda call operator doesn't refer
179 // to the lambda, but to captured "this" in the context it was created in.
180 // This can happen for operator calls and member calls, so fix it up here.
181 if (const auto *CMD = dyn_cast<CXXMethodDecl>(D))
182 if (CMD->getParent()->isLambda())
183 Ctx.SelfArg = nullptr;
184
185 if (Self) {
186 assert(!Ctx.SelfArg && "Ambiguous self argument");
187 assert(isa<FunctionDecl>(D) && "Self argument requires function");
188 if (isa<CXXMethodDecl>(D))
189 Ctx.SelfArg = Self;
190 else
191 Ctx.FunArgs = Self;
192
193 // If the attribute has no arguments, then assume the argument is "this".
194 if (!AttrExp)
195 return CapabilityExpr(
196 Self, cast<CXXMethodDecl>(D)->getFunctionObjectParameterType(),
197 false);
198 else // For most attributes.
199 return translateAttrExpr(AttrExp, &Ctx);
200 }
201
202 // If the attribute has no arguments, then assume the argument is "this".
203 // SelfArg may be null for non-method callees (e.g. function pointers).
204 if (!AttrExp) {
205 if (!Ctx.SelfArg)
206 return CapabilityExpr();
207 return translateAttrExpr(cast<const Expr *>(Ctx.SelfArg), nullptr);
208 }
209
210 // For most attributes.
211 return translateAttrExpr(AttrExp, &Ctx);
212}
213
214/// Translate a clang expression in an attribute to a til::SExpr.
215// This assumes a CallingContext has already been created.
217 CallingContext *Ctx) {
218 if (!AttrExp)
219 return CapabilityExpr();
220
221 if (const auto* SLit = dyn_cast<StringLiteral>(AttrExp)) {
222 if (SLit->getString() == "*")
223 // The "*" expr is a universal lock, which essentially turns off
224 // checks until it is removed from the lockset.
225 return CapabilityExpr(new (Arena) til::Wildcard(), StringRef("wildcard"),
226 /*Neg=*/false, /*Reentrant=*/false);
227 else
228 // Ignore other string literals for now.
229 return CapabilityExpr();
230 }
231
232 bool Neg = false;
233 if (const auto *OE = dyn_cast<CXXOperatorCallExpr>(AttrExp)) {
234 if (OE->getOperator() == OO_Exclaim) {
235 Neg = true;
236 AttrExp = OE->getArg(0);
237 }
238 }
239 else if (const auto *UO = dyn_cast<UnaryOperator>(AttrExp)) {
240 if (UO->getOpcode() == UO_LNot) {
241 Neg = true;
242 AttrExp = UO->getSubExpr()->IgnoreImplicit();
243 }
244 }
245
246 const til::SExpr *E = translate(AttrExp, Ctx);
247
248 // Trap mutex expressions like nullptr, or 0.
249 // Any literal value is nonsense.
250 if (!E || isa<til::Literal>(E))
251 return CapabilityExpr();
252
253 // Hack to deal with smart pointers -- strip off top-level pointer casts.
254 if (const auto *CE = dyn_cast<til::Cast>(E)) {
255 if (CE->castOpcode() == til::CAST_objToPtr)
256 E = CE->expr();
257 }
258 return CapabilityExpr(E, AttrExp->getType(), Neg);
259}
260
262 CallingContext *Ctx) {
263 assert(VD);
264
265 // General recursion guard for x = f(x). If we are already in the process of
266 // defining VD, use its pre-assignment value to break the cycle.
267 if (VarsBeingTranslated.contains(VD->getCanonicalDecl()))
268 return new (Arena) til::LiteralPtr(VD);
269
270 // The closure captures state that is updated to correctly translate chains of
271 // aliases. Restore it when we are done with recursive translation.
272 llvm::scope_exit Cleanup([&, RestoreClosure = VarsBeingTranslated.empty()
273 ? LookupLocalVarExpr
274 : nullptr] {
275 VarsBeingTranslated.erase(VD->getCanonicalDecl());
276 if (VarsBeingTranslated.empty())
277 LookupLocalVarExpr = RestoreClosure;
278 });
279 VarsBeingTranslated.insert(VD->getCanonicalDecl());
280
281 QualType Ty = VD->getType();
282 if (!VD->isStaticLocal() && Ty->isPointerType()) {
283 // Substitute local variable aliases with a canonical definition.
284 if (LookupLocalVarExpr) {
285 // Attempt to resolve an alias through the more complex local variable map
286 // lookup. This will fail with complex control-flow graphs (where we
287 // revert to no alias resolution to retain stable variable names).
288 if (const Expr *E = LookupLocalVarExpr(VD)) {
289 til::SExpr *Result = translate(E, Ctx);
290 // Unsupported expression (such as heap allocations) will be undefined;
291 // rather than failing here, we simply revert to the pointer being the
292 // canonical variable.
294 return Result;
295 }
296 }
297 }
298
299 return new (Arena) til::LiteralPtr(VD);
300}
301
302// Translate a clang statement or expression to a TIL expression.
303// Also performs substitution of variables; Ctx provides the context.
304// Dispatches on the type of S.
306 if (!S)
307 return nullptr;
308
309 // Check if S has already been translated and cached.
310 // This handles the lookup of SSA names for DeclRefExprs here.
311 if (til::SExpr *E = lookupStmt(S))
312 return E;
313
314 switch (S->getStmtClass()) {
315 case Stmt::DeclRefExprClass:
316 return translateDeclRefExpr(cast<DeclRefExpr>(S), Ctx);
317 case Stmt::CXXThisExprClass:
318 return translateCXXThisExpr(cast<CXXThisExpr>(S), Ctx);
319 case Stmt::MemberExprClass:
320 return translateMemberExpr(cast<MemberExpr>(S), Ctx);
321 case Stmt::ObjCIvarRefExprClass:
322 return translateObjCIVarRefExpr(cast<ObjCIvarRefExpr>(S), Ctx);
323 case Stmt::CallExprClass:
324 return translateCallExpr(cast<CallExpr>(S), Ctx);
325 case Stmt::CXXMemberCallExprClass:
326 return translateCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), Ctx);
327 case Stmt::CXXOperatorCallExprClass:
328 return translateCXXOperatorCallExpr(cast<CXXOperatorCallExpr>(S), Ctx);
329 case Stmt::UnaryOperatorClass:
330 return translateUnaryOperator(cast<UnaryOperator>(S), Ctx);
331 case Stmt::BinaryOperatorClass:
332 case Stmt::CompoundAssignOperatorClass:
333 return translateBinaryOperator(cast<BinaryOperator>(S), Ctx);
334
335 case Stmt::ArraySubscriptExprClass:
336 return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx);
337 case Stmt::ConditionalOperatorClass:
338 return translateAbstractConditionalOperator(
340 case Stmt::BinaryConditionalOperatorClass:
341 return translateAbstractConditionalOperator(
343
344 // We treat these as no-ops
345 case Stmt::ConstantExprClass:
346 return translate(cast<ConstantExpr>(S)->getSubExpr(), Ctx);
347 case Stmt::ParenExprClass:
348 return translate(cast<ParenExpr>(S)->getSubExpr(), Ctx);
349 case Stmt::ExprWithCleanupsClass:
350 return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx);
351 case Stmt::CXXBindTemporaryExprClass:
352 return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx);
353 case Stmt::MaterializeTemporaryExprClass:
354 return translate(cast<MaterializeTemporaryExpr>(S)->getSubExpr(), Ctx);
355
356 // Collect all literals
357 case Stmt::CharacterLiteralClass:
358 return new (Arena)
360 case Stmt::CXXNullPtrLiteralExprClass:
361 case Stmt::GNUNullExprClass:
362 return new (Arena) til::LiteralT(nullptr);
363 case Stmt::CXXBoolLiteralExprClass:
364 return new (Arena) til::LiteralT(cast<CXXBoolLiteralExpr>(S)->getValue());
365 case Stmt::IntegerLiteralClass: {
366 const auto *IL = cast<IntegerLiteral>(S);
367 const auto *BT = cast<BuiltinType>(IL->getType());
368 const llvm::APInt &Value = IL->getValue();
369 if (BT->isSignedInteger())
370 return new (Arena) til::LiteralT(Value.getSExtValue());
371 else if (BT->isUnsignedInteger())
372 return new (Arena) til::LiteralT(Value.getZExtValue());
373 else
374 llvm_unreachable("Invalid integer type");
375 }
376 case Stmt::StringLiteralClass:
377 return new (Arena) til::LiteralT(cast<StringLiteral>(S)->getBytes());
378 case Stmt::ObjCStringLiteralClass:
379 return new (Arena)
380 til::LiteralT(cast<ObjCStringLiteral>(S)->getString()->getBytes());
381
382 case Stmt::DeclStmtClass:
383 return translateDeclStmt(cast<DeclStmt>(S), Ctx);
384 case Stmt::StmtExprClass:
385 return translateStmtExpr(cast<StmtExpr>(S), Ctx);
386 default:
387 break;
388 }
389 if (const auto *CE = dyn_cast<CastExpr>(S))
390 return translateCastExpr(CE, Ctx);
391
392 return new (Arena) til::Undefined(S);
393}
394
395/// Helper to extract the canonical parameter declaration from a function or
396/// function pointer. This unwraps pointer and reference types to reach the
397/// underlying function prototype.
398static const ParmVarDecl *getCanonicalParamDecl(const Decl *D, unsigned I) {
399 if (const auto *FD = dyn_cast<FunctionDecl>(D))
400 return FD->getCanonicalDecl()->getParamDecl(I);
401 if (const auto *MD = dyn_cast<ObjCMethodDecl>(D))
402 return MD->getCanonicalDecl()->getParamDecl(I);
403 return nullptr;
404}
405
407 if (const auto *V = dyn_cast<til::Variable>(E))
408 return V->clangDecl();
409 if (const auto *Ph = dyn_cast<til::Phi>(E))
410 return Ph->clangDecl();
411 if (const auto *P = dyn_cast<til::Project>(E))
412 return P->clangDecl();
413 if (const auto *L = dyn_cast<til::LiteralPtr>(E))
414 return L->clangDecl();
415 return nullptr;
416}
417
418// The type of the object, pointer or array that E denotes, where the TIL
419// records one; null otherwise.
421 if (auto *VD = getValueDeclFromSExpr(E))
422 return VD->getType();
423 // A decayed array, or a smart pointer, is its operand.
424 if (const auto *C = dyn_cast<til::Cast>(E))
425 return getSExprType(C->expr());
426 if (const auto *AI = dyn_cast<til::ArrayIndex>(E)) {
427 QualType T = getSExprType(AI->array());
428 if (T.isNull())
429 return T;
430 if (const auto *AT = T->getAsArrayTypeUnsafe())
431 return AT->getElementType();
432 return T->getPointeeType();
433 }
434 if (const auto *C = dyn_cast<til::Call>(E))
435 if (const CallExpr *CE = C->clangCallExpr())
436 return CE->getType();
437 return QualType();
438}
439
440// Whether E denotes a pointer to an object rather than the object itself, so
441// that its member is spelled `p->mu`, not `p.mu`. Since `&` and `*` are no-ops
442// in the TIL, this is decided by the translated base, not by the source.
443static bool hasAnyPointerType(const til::SExpr *E) {
444 if (const auto *C = dyn_cast<til::Cast>(E))
445 return C->castOpcode() == til::CAST_objToPtr;
446 // A member reached through arithmetic is reached through a pointer; an
447 // overloaded operator is a Call.
448 if (isa<til::BinaryOp>(E))
449 return true;
451 return !T.isNull() && T->isAnyPointerType();
452}
453
454til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE,
455 CallingContext *Ctx) {
456 const auto *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl());
457
458 // Function parameters require substitution and/or renaming.
459 if (const auto *PV = dyn_cast<ParmVarDecl>(VD)) {
460 unsigned I = PV->getFunctionScopeIndex();
461 const DeclContext *D = PV->getDeclContext();
462 if (Ctx && Ctx->FunArgs) {
463 const Decl *Canonical = Ctx->AttrDecl->getCanonicalDecl();
464 bool Match = false;
465 if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
466 Match = (FD->getCanonicalDecl() == Canonical);
467 } else if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
468 Match = (MD->getCanonicalDecl() == Canonical);
469 } else if (D->isTranslationUnit()) {
470 // Sema temporarily creates every parameter in the translation unit
471 // itself and moves it to its function once there is one. Thus, the
472 // parameters of a prototype nested in a declarator's type, such as a
473 // function pointer's, have no function and stay there. An attribute on
474 // the declarator can only name one of those, from its own type or a
475 // redeclaration's. When the declarator is itself a parameter, its
476 // attribute may also name a sibling parameter, which is no deeper
477 // than it is; only one nested deeper is of its own prototype.
478 const auto *AttrPV = dyn_cast<ParmVarDecl>(Ctx->AttrDecl);
479 Match = !AttrPV ||
480 PV->getFunctionScopeDepth() > AttrPV->getFunctionScopeDepth();
481 } else {
482 llvm_unreachable("ParmVarDecl does not belong to current declaration");
483 }
484
485 if (Match) {
486 // Substitute call arguments for references to function parameters
487 if (const Expr *const *FunArgs =
488 dyn_cast<const Expr *const *>(Ctx->FunArgs)) {
489 assert(I < Ctx->NumArgs);
490 return translate(FunArgs[I], Ctx->Prev);
491 }
492
493 assert(I == 0);
494 return cast<til::SExpr *>(Ctx->FunArgs);
495 }
496 }
497 // Map the param back to the param of the original function declaration
498 // for consistent comparisons.
499 if (const auto *PVD = getCanonicalParamDecl(cast<Decl>(D), I))
500 VD = PVD;
501 }
502
503 if (const auto *VarD = dyn_cast<VarDecl>(VD))
504 return translateVariable(VarD, Ctx);
505
506 // A member named through anonymous structs/unions is an IndirectFieldDecl;
507 // name it by its field.
508 const auto *IFD = dyn_cast<IndirectFieldDecl>(VD);
509 if (IFD)
510 VD = IFD->getAnonField();
511
512 // FIXME: A FieldDecl reached via a DeclRefExpr should ideally be modelled as
513 // a MemberExpr with an artificial self in the AST (e.g. ImplicitThisExpr as a
514 // C equivalent of CXXThisExpr). Until such AST support is available, project
515 // the field on the current SelfArg, so implicit member references in C and in
516 // parameter attributes are not lost.
517 if (const auto *FD = dyn_cast<FieldDecl>(VD); FD && Ctx && Ctx->SelfArg) {
518 // Sema lowers a non-member IndirectFieldDecl, from a namespace- or
519 // block-scope anonymous union, to a MemberExpr chain rooted at its VarDecl.
520 assert((!IFD || !IFD->getVarDecl()) &&
521 "non-member IndirectFieldDecl should be a MemberExpr");
522 bool Found;
523 const auto *Owner =
524 cast<FieldDecl>(IFD ? IFD->chain().front() : FD)->getParent();
525 til::SExpr *E = translateFieldOwner(Owner, Ctx, Found);
526 // Project each anonymous member of the chain in turn.
527 if (IFD)
528 for (const NamedDecl *ND : IFD->chain().drop_back())
529 E = translateProject(E, cast<FieldDecl>(ND));
530 til::Project *P = translateProject(E, FD);
531 // Say whose field this is when self does not have it.
532 P->setQualified(!Found);
533 return P;
534 }
535
536 // For non-local variables, treat it as a reference to a named object.
537 return new (Arena) til::LiteralPtr(VD);
538}
539
540/// Translate the object owning \p Owner's field that an attribute names without
541/// a base expression. Normally that is the self argument, the object whose
542/// member carries the attribute. But a field of an enclosing record may be
543/// named from a nested one, anonymous or named, so walk out of the subobject
544/// accesses reaching self (members, array elements, `*`, and `&` back from a
545/// pointer to the object it points to) to the nearest object of type \p Owner,
546/// or derived from it. A pointer member's pointee is not part of the object, so
547/// the walk stops at one. Keep self if there is none, and clear \p Found.
548til::SExpr *SExprBuilder::translateFieldOwner(const RecordDecl *Owner,
549 CallingContext *Ctx,
550 bool &Found) {
551 // An already translated self has no type to check; take it as the owner.
552 Found = true;
553 const auto *SelfArg = dyn_cast_if_present<const Expr *>(Ctx->SelfArg);
554 if (!SelfArg)
555 return translateCXXThisExpr(nullptr, Ctx);
556 Found = false;
557 for (const Expr *E = SelfArg;;) {
558 // Up to casts, E is either the object or a pointer to it. An array of
559 // objects, left by stripping its decay to a pointer, is its element.
560 const Expr *Inner = E->IgnoreParenImpCasts();
561 QualType T = Inner->getType();
562 bool Pointer = T->isAnyPointerType();
563 if (Pointer)
564 T = T->getPointeeType();
565 else if (const auto *AT = T->getAsArrayTypeUnsafe())
566 T = AT->getElementType();
567 if (const auto *RD = T->getAsRecordDecl()) {
568 if (declaresSameEntity(RD, Owner)) {
569 SelfArg = E;
570 Found = true;
571 break;
572 }
573 const auto *CRD = dyn_cast<CXXRecordDecl>(RD);
574 const auto *COwner = dyn_cast<CXXRecordDecl>(Owner);
575 if (CRD && COwner && CRD->hasDefinition() && !CRD->isDependentType() &&
576 CRD->isDerivedFrom(COwner)) {
577 SelfArg = E;
578 Found = true;
579 break;
580 }
581 }
582 const auto *UO = dyn_cast<UnaryOperator>(Inner);
583 if (Pointer) {
584 // Only the address of an object leads back to it.
585 if (!UO || UO->getOpcode() != UO_AddrOf)
586 break;
587 E = UO->getSubExpr();
588 } else if (const auto *ME = dyn_cast<MemberExpr>(Inner)) {
589 E = ME->getBase();
590 } else if (const auto *ASE = dyn_cast<ArraySubscriptExpr>(Inner)) {
591 E = ASE->getBase();
592 } else if (UO && UO->getOpcode() == UO_Deref) {
593 E = UO->getSubExpr();
594 } else {
595 break;
596 }
597 }
598 return translate(SelfArg, Ctx->Prev);
599}
600
601til::Project *SExprBuilder::translateProject(til::SExpr *BE,
602 const ValueDecl *D) {
603 til::SExpr *E = new (Arena) til::SApply(BE);
604 til::Project *P = new (Arena) til::Project(E, D);
605 if (hasAnyPointerType(BE))
606 P->setArrow(true);
607 return P;
608}
609
610til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE,
611 CallingContext *Ctx) {
612 // Substitute for 'this'
613 if (Ctx && Ctx->SelfArg) {
614 if (const auto *SelfArg = dyn_cast<const Expr *>(Ctx->SelfArg))
615 return translate(SelfArg, Ctx->Prev);
616 else
617 return cast<til::SExpr *>(Ctx->SelfArg);
618 }
619 assert(SelfVar && "We have no variable for 'this'!");
620 return SelfVar;
621}
622
623// Grab the very first declaration of virtual method D
625 while (true) {
626 D = D->getCanonicalDecl();
627 auto OverriddenMethods = D->overridden_methods();
628 if (OverriddenMethods.begin() == OverriddenMethods.end())
629 return D; // Method does not override anything
630 // FIXME: this does not work with multiple inheritance.
631 D = *OverriddenMethods.begin();
632 }
633 return nullptr;
634}
635
636til::SExpr *SExprBuilder::translateMemberExpr(const MemberExpr *ME,
637 CallingContext *Ctx) {
638 til::SExpr *BE = translate(ME->getBase(), Ctx);
639
640 const auto *D = cast<ValueDecl>(ME->getMemberDecl()->getCanonicalDecl());
641 if (const auto *VD = dyn_cast<CXXMethodDecl>(D))
642 D = getFirstVirtualDecl(VD);
643
644 return translateProject(BE, D);
645}
646
647til::SExpr *SExprBuilder::translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE,
648 CallingContext *Ctx) {
649 til::SExpr *BE = translate(IVRE->getBase(), Ctx);
650 const auto *D = cast<ObjCIvarDecl>(IVRE->getDecl()->getCanonicalDecl());
651 return translateProject(BE, D);
652}
653
654til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE,
655 CallingContext *Ctx,
656 const Expr *SelfE) {
657 if (CapabilityExprMode) {
658 // Handle LOCK_RETURNED, on a function or a function pointer.
659 if (const auto *D = dyn_cast_or_null<NamedDecl>(CE->getCalleeDecl())) {
660 const NamedDecl *AttrD = D;
661 if (const auto *FD = dyn_cast<FunctionDecl>(D))
662 AttrD = FD->getMostRecentDecl();
663 if (const auto *At = AttrD->getAttr<LockReturnedAttr>()) {
664 CallingContext LRCallCtx(Ctx);
665 LRCallCtx.AttrDecl = D;
666 LRCallCtx.SelfArg = SelfE;
667 if (!SelfE)
668 if (const MemberExpr *ME = getFunPtrFieldCallee(CE, D))
669 LRCallCtx.SelfArg = ME->getBase();
670 LRCallCtx.NumArgs = CE->getNumArgs();
671 LRCallCtx.FunArgs = CE->getArgs();
672 return const_cast<til::SExpr *>(
673 translateAttrExpr(At->getArg(), &LRCallCtx).sexpr());
674 }
675 }
676 }
677
678 til::SExpr *E = translate(CE->getCallee(), Ctx);
679 // Explicitly propagate Undefined, when the callee couldn't be analyzed.
680 if (isa<til::Undefined>(E))
681 return E;
682 for (const auto *Arg : CE->arguments()) {
683 til::SExpr *A = translate(Arg, Ctx);
684 E = new (Arena) til::Apply(E, A);
685 }
686 return new (Arena) til::Call(E, CE);
687}
688
689til::SExpr *SExprBuilder::translateCXXMemberCallExpr(
690 const CXXMemberCallExpr *ME, CallingContext *Ctx) {
691 if (CapabilityExprMode) {
692 // Ignore calls to get() on smart pointers. A call through a pointer to
693 // member function has no method declaration.
694 const CXXMethodDecl *MD = ME->getMethodDecl();
695 if (ME->getNumArgs() == 0 && MD && MD->getIdentifier() &&
696 MD->getIdentifier()->isStr("get")) {
697 auto *E = translate(ME->getImplicitObjectArgument(), Ctx);
698 return new (Arena) til::Cast(til::CAST_objToPtr, E);
699 // return E;
700 }
701 }
702 return translateCallExpr(cast<CallExpr>(ME), Ctx,
704}
705
706til::SExpr *SExprBuilder::translateCXXOperatorCallExpr(
707 const CXXOperatorCallExpr *OCE, CallingContext *Ctx) {
708 if (CapabilityExprMode) {
709 // Ignore operator * and operator -> on smart pointers.
711 if (k == OO_Star || k == OO_Arrow) {
712 auto *E = translate(OCE->getArg(0), Ctx);
713 return new (Arena) til::Cast(til::CAST_objToPtr, E);
714 // return E;
715 }
716 }
717 return translateCallExpr(cast<CallExpr>(OCE), Ctx);
718}
719
720til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO,
721 CallingContext *Ctx) {
722 switch (UO->getOpcode()) {
723 case UO_PostInc:
724 case UO_PostDec:
725 case UO_PreInc:
726 case UO_PreDec:
727 return new (Arena) til::Undefined(UO);
728
729 case UO_AddrOf:
730 if (CapabilityExprMode) {
731 // interpret &Graph::mu_ as an existential.
732 if (const auto *DRE = dyn_cast<DeclRefExpr>(UO->getSubExpr())) {
733 if (DRE->getDecl()->isCXXInstanceMember()) {
734 // This is a pointer-to-member expression, e.g. &MyClass::mu_.
735 // We interpret this syntax specially, as a wildcard.
736 // Name a member of an anonymous struct/union by its field, as a
737 // projection of it does.
738 const ValueDecl *D = DRE->getDecl();
739 if (const auto *IFD = dyn_cast<IndirectFieldDecl>(D))
740 D = IFD->getAnonField();
741 auto *W = new (Arena) til::Wildcard();
742 return new (Arena) til::Project(W, D);
743 }
744 }
745 }
746 // otherwise, & is a no-op
747 return translate(UO->getSubExpr(), Ctx);
748
749 // We treat these as no-ops
750 case UO_Deref:
751 case UO_Plus:
752 return translate(UO->getSubExpr(), Ctx);
753
754 case UO_Minus:
755 return new (Arena)
756 til::UnaryOp(til::UOP_Minus, translate(UO->getSubExpr(), Ctx));
757 case UO_Not:
758 return new (Arena)
759 til::UnaryOp(til::UOP_BitNot, translate(UO->getSubExpr(), Ctx));
760 case UO_LNot:
761 return new (Arena)
762 til::UnaryOp(til::UOP_LogicNot, translate(UO->getSubExpr(), Ctx));
763
764 // Currently unsupported
765 case UO_Real:
766 case UO_Imag:
767 case UO_Extension:
768 case UO_Coawait:
769 return new (Arena) til::Undefined(UO);
770 }
771 return new (Arena) til::Undefined(UO);
772}
773
774til::SExpr *SExprBuilder::translateBinOp(til::TIL_BinaryOpcode Op,
775 const BinaryOperator *BO,
776 CallingContext *Ctx, bool Reverse) {
777 til::SExpr *E0 = translate(BO->getLHS(), Ctx);
778 til::SExpr *E1 = translate(BO->getRHS(), Ctx);
779 if (Reverse)
780 return new (Arena) til::BinaryOp(Op, E1, E0);
781 else
782 return new (Arena) til::BinaryOp(Op, E0, E1);
783}
784
785til::SExpr *SExprBuilder::translateBinAssign(til::TIL_BinaryOpcode Op,
786 const BinaryOperator *BO,
787 CallingContext *Ctx,
788 bool Assign) {
789 const Expr *LHS = BO->getLHS();
790 const Expr *RHS = BO->getRHS();
791 til::SExpr *E0 = translate(LHS, Ctx);
792 til::SExpr *E1 = translate(RHS, Ctx);
793
794 const ValueDecl *VD = nullptr;
795 til::SExpr *CV = nullptr;
796 if (const auto *DRE = dyn_cast<DeclRefExpr>(LHS)) {
797 VD = DRE->getDecl();
798 CV = lookupVarDecl(VD);
799 }
800
801 if (!Assign) {
802 til::SExpr *Arg = CV ? CV : new (Arena) til::Load(E0);
803 E1 = new (Arena) til::BinaryOp(Op, Arg, E1);
804 E1 = addStatement(E1, nullptr, VD);
805 }
806 if (VD && CV)
807 return updateVarDecl(VD, E1);
808 return new (Arena) til::Store(E0, E1);
809}
810
811til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO,
812 CallingContext *Ctx) {
813 switch (BO->getOpcode()) {
814 case BO_PtrMemD:
815 case BO_PtrMemI:
816 return new (Arena) til::Undefined(BO);
817
818 case BO_Mul: return translateBinOp(til::BOP_Mul, BO, Ctx);
819 case BO_Div: return translateBinOp(til::BOP_Div, BO, Ctx);
820 case BO_Rem: return translateBinOp(til::BOP_Rem, BO, Ctx);
821 case BO_Add: return translateBinOp(til::BOP_Add, BO, Ctx);
822 case BO_Sub: return translateBinOp(til::BOP_Sub, BO, Ctx);
823 case BO_Shl: return translateBinOp(til::BOP_Shl, BO, Ctx);
824 case BO_Shr: return translateBinOp(til::BOP_Shr, BO, Ctx);
825 case BO_LT: return translateBinOp(til::BOP_Lt, BO, Ctx);
826 case BO_GT: return translateBinOp(til::BOP_Lt, BO, Ctx, true);
827 case BO_LE: return translateBinOp(til::BOP_Leq, BO, Ctx);
828 case BO_GE: return translateBinOp(til::BOP_Leq, BO, Ctx, true);
829 case BO_EQ: return translateBinOp(til::BOP_Eq, BO, Ctx);
830 case BO_NE: return translateBinOp(til::BOP_Neq, BO, Ctx);
831 case BO_Cmp: return translateBinOp(til::BOP_Cmp, BO, Ctx);
832 case BO_And: return translateBinOp(til::BOP_BitAnd, BO, Ctx);
833 case BO_Xor: return translateBinOp(til::BOP_BitXor, BO, Ctx);
834 case BO_Or: return translateBinOp(til::BOP_BitOr, BO, Ctx);
835 case BO_LAnd: return translateBinOp(til::BOP_LogicAnd, BO, Ctx);
836 case BO_LOr: return translateBinOp(til::BOP_LogicOr, BO, Ctx);
837
838 case BO_Assign: return translateBinAssign(til::BOP_Eq, BO, Ctx, true);
839 case BO_MulAssign: return translateBinAssign(til::BOP_Mul, BO, Ctx);
840 case BO_DivAssign: return translateBinAssign(til::BOP_Div, BO, Ctx);
841 case BO_RemAssign: return translateBinAssign(til::BOP_Rem, BO, Ctx);
842 case BO_AddAssign: return translateBinAssign(til::BOP_Add, BO, Ctx);
843 case BO_SubAssign: return translateBinAssign(til::BOP_Sub, BO, Ctx);
844 case BO_ShlAssign: return translateBinAssign(til::BOP_Shl, BO, Ctx);
845 case BO_ShrAssign: return translateBinAssign(til::BOP_Shr, BO, Ctx);
846 case BO_AndAssign: return translateBinAssign(til::BOP_BitAnd, BO, Ctx);
847 case BO_XorAssign: return translateBinAssign(til::BOP_BitXor, BO, Ctx);
848 case BO_OrAssign: return translateBinAssign(til::BOP_BitOr, BO, Ctx);
849
850 case BO_Comma:
851 // The clang CFG should have already processed both sides.
852 return translate(BO->getRHS(), Ctx);
853 }
854 return new (Arena) til::Undefined(BO);
855}
856
857til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE,
858 CallingContext *Ctx) {
859 CastKind K = CE->getCastKind();
860 switch (K) {
861 case CK_LValueToRValue: {
862 if (const auto *DRE = dyn_cast<DeclRefExpr>(CE->getSubExpr())) {
863 til::SExpr *E0 = lookupVarDecl(DRE->getDecl());
864 if (E0)
865 return E0;
866 }
867 til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
868 return E0;
869 // FIXME!! -- get Load working properly
870 // return new (Arena) til::Load(E0);
871 }
872 case CK_ArrayToPointerDecay:
873 // Keep the decay, so that a member of an element is spelled as reached
874 // through the pointer, `arr->mu`, unlike one of the array, `arr[0].mu`.
875 return new (Arena)
876 til::Cast(til::CAST_objToPtr, translate(CE->getSubExpr(), Ctx));
877 case CK_NoOp:
878 case CK_DerivedToBase:
879 case CK_UncheckedDerivedToBase:
880 case CK_FunctionToPointerDecay: {
881 til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
882 return E0;
883 }
884 default: {
885 // FIXME: handle different kinds of casts.
886 til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
887 if (CapabilityExprMode)
888 return E0;
889 return new (Arena) til::Cast(til::CAST_none, E0);
890 }
891 }
892}
893
895SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E,
896 CallingContext *Ctx) {
897 til::SExpr *E0 = translate(E->getBase(), Ctx);
898 til::SExpr *E1 = translate(E->getIdx(), Ctx);
899 return new (Arena) til::ArrayIndex(E0, E1);
900}
901
903SExprBuilder::translateAbstractConditionalOperator(
904 const AbstractConditionalOperator *CO, CallingContext *Ctx) {
905 auto *C = translate(CO->getCond(), Ctx);
906 auto *T = translate(CO->getTrueExpr(), Ctx);
907 auto *E = translate(CO->getFalseExpr(), Ctx);
908 return new (Arena) til::IfThenElse(C, T, E);
909}
910
912SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) {
913 DeclGroupRef DGrp = S->getDeclGroup();
914 for (auto *I : DGrp) {
915 if (auto *VD = dyn_cast_or_null<VarDecl>(I)) {
916 Expr *E = VD->getInit();
917 til::SExpr* SE = translate(E, Ctx);
918
919 // Add local variables with trivial type to the variable map
920 QualType T = VD->getType();
921 if (T.isTrivialType(VD->getASTContext()))
922 return addVarDecl(VD, SE);
923 else {
924 // TODO: add alloca
925 }
926 }
927 }
928 return nullptr;
929}
930
931til::SExpr *SExprBuilder::translateStmtExpr(const StmtExpr *SE,
932 CallingContext *Ctx) {
933 // The value of a statement expression is the value of the last statement,
934 // which must be an expression.
935 const CompoundStmt *CS = SE->getSubStmt();
936 return CS->body_empty() ? new (Arena) til::Undefined(SE)
937 : translate(CS->body_back(), Ctx);
938}
939
940// If (E) is non-trivial, then add it to the current basic block, and
941// update the statement map so that S refers to E. Returns a new variable
942// that refers to E.
943// If E is trivial returns E.
944til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S,
945 const ValueDecl *VD) {
946 if (!E || !CurrentBB || E->block() || til::ThreadSafetyTIL::isTrivial(E))
947 return E;
948 if (VD)
949 E = new (Arena) til::Variable(E, VD);
950 CurrentInstructions.push_back(E);
951 if (S)
952 insertStmt(S, E);
953 return E;
954}
955
956// Returns the current value of VD, if known, and nullptr otherwise.
957til::SExpr *SExprBuilder::lookupVarDecl(const ValueDecl *VD) {
958 auto It = LVarIdxMap.find(VD);
959 if (It != LVarIdxMap.end()) {
960 assert(CurrentLVarMap[It->second].first == VD);
961 return CurrentLVarMap[It->second].second;
962 }
963 return nullptr;
964}
965
966// if E is a til::Variable, update its clangDecl.
967static void maybeUpdateVD(til::SExpr *E, const ValueDecl *VD) {
968 if (!E)
969 return;
970 if (auto *V = dyn_cast<til::Variable>(E)) {
971 if (!V->clangDecl())
972 V->setClangDecl(VD);
973 }
974}
975
976// Adds a new variable declaration.
977til::SExpr *SExprBuilder::addVarDecl(const ValueDecl *VD, til::SExpr *E) {
978 maybeUpdateVD(E, VD);
979 LVarIdxMap.insert(std::make_pair(VD, CurrentLVarMap.size()));
980 CurrentLVarMap.makeWritable();
981 CurrentLVarMap.push_back(std::make_pair(VD, E));
982 return E;
983}
984
985// Updates a current variable declaration. (E.g. by assignment)
986til::SExpr *SExprBuilder::updateVarDecl(const ValueDecl *VD, til::SExpr *E) {
987 maybeUpdateVD(E, VD);
988 auto It = LVarIdxMap.find(VD);
989 if (It == LVarIdxMap.end()) {
990 til::SExpr *Ptr = new (Arena) til::LiteralPtr(VD);
991 til::SExpr *St = new (Arena) til::Store(Ptr, E);
992 return St;
993 }
994 CurrentLVarMap.makeWritable();
995 CurrentLVarMap.elem(It->second).second = E;
996 return E;
997}
998
999// Make a Phi node in the current block for the i^th variable in CurrentVarMap.
1000// If E != null, sets Phi[CurrentBlockInfo->ArgIndex] = E.
1001// If E == null, this is a backedge and will be set later.
1002void SExprBuilder::makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E) {
1003 unsigned ArgIndex = CurrentBlockInfo->ProcessedPredecessors;
1004 assert(ArgIndex > 0 && ArgIndex < NPreds);
1005
1006 til::SExpr *CurrE = CurrentLVarMap[i].second;
1007 if (CurrE->block() == CurrentBB) {
1008 // We already have a Phi node in the current block,
1009 // so just add the new variable to the Phi node.
1010 auto *Ph = dyn_cast<til::Phi>(CurrE);
1011 assert(Ph && "Expecting Phi node.");
1012 if (E)
1013 Ph->values()[ArgIndex] = E;
1014 return;
1015 }
1016
1017 // Make a new phi node: phi(..., E)
1018 // All phi args up to the current index are set to the current value.
1019 til::Phi *Ph = new (Arena) til::Phi(Arena, NPreds);
1020 Ph->values().setValues(NPreds, nullptr);
1021 for (unsigned PIdx = 0; PIdx < ArgIndex; ++PIdx)
1022 Ph->values()[PIdx] = CurrE;
1023 if (E)
1024 Ph->values()[ArgIndex] = E;
1025 Ph->setClangDecl(CurrentLVarMap[i].first);
1026 // If E is from a back-edge, or either E or CurrE are incomplete, then
1027 // mark this node as incomplete; we may need to remove it later.
1028 if (!E || isIncompletePhi(E) || isIncompletePhi(CurrE))
1030
1031 // Add Phi node to current block, and update CurrentLVarMap[i]
1032 CurrentArguments.push_back(Ph);
1033 if (Ph->status() == til::Phi::PH_Incomplete)
1034 IncompleteArgs.push_back(Ph);
1035
1036 CurrentLVarMap.makeWritable();
1037 CurrentLVarMap.elem(i).second = Ph;
1038}
1039
1040// Merge values from Map into the current variable map.
1041// This will construct Phi nodes in the current basic block as necessary.
1042void SExprBuilder::mergeEntryMap(LVarDefinitionMap Map) {
1043 assert(CurrentBlockInfo && "Not processing a block!");
1044
1045 if (!CurrentLVarMap.valid()) {
1046 // Steal Map, using copy-on-write.
1047 CurrentLVarMap = std::move(Map);
1048 return;
1049 }
1050 if (CurrentLVarMap.sameAs(Map))
1051 return; // Easy merge: maps from different predecessors are unchanged.
1052
1053 unsigned NPreds = CurrentBB->numPredecessors();
1054 unsigned ESz = CurrentLVarMap.size();
1055 unsigned MSz = Map.size();
1056 unsigned Sz = std::min(ESz, MSz);
1057
1058 for (unsigned i = 0; i < Sz; ++i) {
1059 if (CurrentLVarMap[i].first != Map[i].first) {
1060 // We've reached the end of variables in common.
1061 CurrentLVarMap.makeWritable();
1062 CurrentLVarMap.downsize(i);
1063 break;
1064 }
1065 if (CurrentLVarMap[i].second != Map[i].second)
1066 makePhiNodeVar(i, NPreds, Map[i].second);
1067 }
1068 if (ESz > MSz) {
1069 CurrentLVarMap.makeWritable();
1070 CurrentLVarMap.downsize(Map.size());
1071 }
1072}
1073
1074// Merge a back edge into the current variable map.
1075// This will create phi nodes for all variables in the variable map.
1076void SExprBuilder::mergeEntryMapBackEdge() {
1077 // We don't have definitions for variables on the backedge, because we
1078 // haven't gotten that far in the CFG. Thus, when encountering a back edge,
1079 // we conservatively create Phi nodes for all variables. Unnecessary Phi
1080 // nodes will be marked as incomplete, and stripped out at the end.
1081 //
1082 // An Phi node is unnecessary if it only refers to itself and one other
1083 // variable, e.g. x = Phi(y, y, x) can be reduced to x = y.
1084
1085 assert(CurrentBlockInfo && "Not processing a block!");
1086
1087 if (CurrentBlockInfo->HasBackEdges)
1088 return;
1089 CurrentBlockInfo->HasBackEdges = true;
1090
1091 CurrentLVarMap.makeWritable();
1092 unsigned Sz = CurrentLVarMap.size();
1093 unsigned NPreds = CurrentBB->numPredecessors();
1094
1095 for (unsigned i = 0; i < Sz; ++i)
1096 makePhiNodeVar(i, NPreds, nullptr);
1097}
1098
1099// Update the phi nodes that were initially created for a back edge
1100// once the variable definitions have been computed.
1101// I.e., merge the current variable map into the phi nodes for Blk.
1102void SExprBuilder::mergePhiNodesBackEdge(const CFGBlock *Blk) {
1103 til::BasicBlock *BB = lookupBlock(Blk);
1104 unsigned ArgIndex = BBInfo[Blk->getBlockID()].ProcessedPredecessors;
1105 assert(ArgIndex > 0 && ArgIndex < BB->numPredecessors());
1106
1107 for (til::SExpr *PE : BB->arguments()) {
1108 auto *Ph = dyn_cast_or_null<til::Phi>(PE);
1109 assert(Ph && "Expecting Phi Node.");
1110 assert(Ph->values()[ArgIndex] == nullptr && "Wrong index for back edge.");
1111
1112 til::SExpr *E = lookupVarDecl(Ph->clangDecl());
1113 assert(E && "Couldn't find local variable for Phi node.");
1114 Ph->values()[ArgIndex] = E;
1115 }
1116}
1117
1118void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D,
1119 const CFGBlock *First) {
1120 // Perform initial setup operations.
1121 unsigned NBlocks = Cfg->getNumBlockIDs();
1122 Scfg = new (Arena) til::SCFG(Arena, NBlocks);
1123
1124 // allocate all basic blocks immediately, to handle forward references.
1125 BBInfo.resize(NBlocks);
1126 BlockMap.resize(NBlocks, nullptr);
1127 // create map from clang blockID to til::BasicBlocks
1128 for (auto *B : *Cfg) {
1129 auto *BB = new (Arena) til::BasicBlock(Arena);
1130 BB->reserveInstructions(B->size());
1131 BlockMap[B->getBlockID()] = BB;
1132 }
1133
1134 CurrentBB = lookupBlock(&Cfg->getEntry());
1135 auto Parms = isa<ObjCMethodDecl>(D) ? cast<ObjCMethodDecl>(D)->parameters()
1136 : cast<FunctionDecl>(D)->parameters();
1137 for (auto *Pm : Parms) {
1138 QualType T = Pm->getType();
1139 if (!T.isTrivialType(Pm->getASTContext()))
1140 continue;
1141
1142 // Add parameters to local variable map.
1143 // FIXME: right now we emulate params with loads; that should be fixed.
1144 til::SExpr *Lp = new (Arena) til::LiteralPtr(Pm);
1145 til::SExpr *Ld = new (Arena) til::Load(Lp);
1146 til::SExpr *V = addStatement(Ld, nullptr, Pm);
1147 addVarDecl(Pm, V);
1148 }
1149}
1150
1151void SExprBuilder::enterCFGBlock(const CFGBlock *B) {
1152 // Initialize TIL basic block and add it to the CFG.
1153 CurrentBB = lookupBlock(B);
1154 CurrentBB->reservePredecessors(B->pred_size());
1155 Scfg->add(CurrentBB);
1156
1157 CurrentBlockInfo = &BBInfo[B->getBlockID()];
1158
1159 // CurrentLVarMap is moved to ExitMap on block exit.
1160 // FIXME: the entry block will hold function parameters.
1161 // assert(!CurrentLVarMap.valid() && "CurrentLVarMap already initialized.");
1162}
1163
1164void SExprBuilder::handlePredecessor(const CFGBlock *Pred) {
1165 // Compute CurrentLVarMap on entry from ExitMaps of predecessors
1166
1167 CurrentBB->addPredecessor(BlockMap[Pred->getBlockID()]);
1168 BlockInfo *PredInfo = &BBInfo[Pred->getBlockID()];
1169 assert(PredInfo->UnprocessedSuccessors > 0);
1170
1171 if (--PredInfo->UnprocessedSuccessors == 0)
1172 mergeEntryMap(std::move(PredInfo->ExitMap));
1173 else
1174 mergeEntryMap(PredInfo->ExitMap.clone());
1175
1176 ++CurrentBlockInfo->ProcessedPredecessors;
1177}
1178
1179void SExprBuilder::handlePredecessorBackEdge(const CFGBlock *Pred) {
1180 mergeEntryMapBackEdge();
1181}
1182
1183void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) {
1184 // The merge*() methods have created arguments.
1185 // Push those arguments onto the basic block.
1186 CurrentBB->arguments().reserve(
1187 static_cast<unsigned>(CurrentArguments.size()), Arena);
1188 for (auto *A : CurrentArguments)
1189 CurrentBB->addArgument(A);
1190}
1191
1192void SExprBuilder::handleStatement(const Stmt *S) {
1193 til::SExpr *E = translate(S, nullptr);
1194 addStatement(E, S);
1195}
1196
1197void SExprBuilder::handleDestructorCall(const VarDecl *VD,
1198 const CXXDestructorDecl *DD) {
1199 til::SExpr *Sf = new (Arena) til::LiteralPtr(VD);
1200 til::SExpr *Dr = new (Arena) til::LiteralPtr(DD);
1201 til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf);
1202 til::SExpr *E = new (Arena) til::Call(Ap);
1203 addStatement(E, nullptr);
1204}
1205
1206void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) {
1207 CurrentBB->instructions().reserve(
1208 static_cast<unsigned>(CurrentInstructions.size()), Arena);
1209 for (auto *V : CurrentInstructions)
1210 CurrentBB->addInstruction(V);
1211
1212 // Create an appropriate terminator
1213 unsigned N = B->succ_size();
1214 auto It = B->succ_begin();
1215 if (N == 1) {
1216 til::BasicBlock *BB = *It ? lookupBlock(*It) : nullptr;
1217 // TODO: set index
1218 unsigned Idx = BB ? BB->findPredecessorIndex(CurrentBB) : 0;
1219 auto *Tm = new (Arena) til::Goto(BB, Idx);
1220 CurrentBB->setTerminator(Tm);
1221 }
1222 else if (N == 2) {
1223 til::SExpr *C = translate(B->getTerminatorCondition(true), nullptr);
1224 til::BasicBlock *BB1 = *It ? lookupBlock(*It) : nullptr;
1225 ++It;
1226 til::BasicBlock *BB2 = *It ? lookupBlock(*It) : nullptr;
1227 // FIXME: make sure these aren't critical edges.
1228 auto *Tm = new (Arena) til::Branch(C, BB1, BB2);
1229 CurrentBB->setTerminator(Tm);
1230 }
1231}
1232
1233void SExprBuilder::handleSuccessor(const CFGBlock *Succ) {
1234 ++CurrentBlockInfo->UnprocessedSuccessors;
1235}
1236
1237void SExprBuilder::handleSuccessorBackEdge(const CFGBlock *Succ) {
1238 mergePhiNodesBackEdge(Succ);
1239 ++BBInfo[Succ->getBlockID()].ProcessedPredecessors;
1240}
1241
1242void SExprBuilder::exitCFGBlock(const CFGBlock *B) {
1243 CurrentArguments.clear();
1244 CurrentInstructions.clear();
1245 CurrentBlockInfo->ExitMap = std::move(CurrentLVarMap);
1246 CurrentBB = nullptr;
1247 CurrentBlockInfo = nullptr;
1248}
1249
1250void SExprBuilder::exitCFG(const CFGBlock *Last) {
1251 for (auto *Ph : IncompleteArgs) {
1252 if (Ph->status() == til::Phi::PH_Incomplete)
1254 }
1255
1256 CurrentArguments.clear();
1257 CurrentInstructions.clear();
1258 IncompleteArgs.clear();
1259}
1260
1261#ifndef NDEBUG
1262namespace {
1263
1264class TILPrinter :
1265 public til::PrettyPrinter<TILPrinter, llvm::raw_ostream> {};
1266
1267} // namespace
1268
1269namespace clang {
1270namespace threadSafety {
1271
1272void printSCFG(CFGWalker &Walker) {
1273 llvm::BumpPtrAllocator Bpa;
1274 til::MemRegionRef Arena(&Bpa);
1275 SExprBuilder SxBuilder(Arena);
1276 til::SCFG *Scfg = SxBuilder.buildCFG(Walker);
1277 TILPrinter::print(Scfg, llvm::errs());
1278}
1279
1280} // namespace threadSafety
1281} // namespace clang
1282#endif // NDEBUG
#define V(N, I)
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
Defines the clang::Expr interface and subclasses for C++ expressions.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.
Defines an enumeration for C++ overloaded operators.
static std::string toString(const clang::SanitizerSet &Sanitizers)
Produce a string containing comma-separated names of sanitizers in Sanitizers set.
Defines various enumerations that describe declaration and type specifiers.
static bool isIncompletePhi(const til::SExpr *E)
static const MemberExpr * getFunPtrFieldCallee(const CallExpr *CE, const NamedDecl *D)
If CE calls through a function pointer field D, return the member access through which the field was ...
SExprBuilder::CallingContext CallingContext
static const ParmVarDecl * getCanonicalParamDecl(const Decl *D, unsigned I)
Helper to extract the canonical parameter declaration from a function or function pointer.
static QualType getSExprType(const til::SExpr *E)
static const ValueDecl * getValueDeclFromSExpr(const til::SExpr *E)
static void maybeUpdateVD(til::SExpr *E, const ValueDecl *VD)
static bool hasAnyPointerType(const til::SExpr *E)
static const CXXMethodDecl * getFirstVirtualDecl(const CXXMethodDecl *D)
static std::pair< StringRef, bool > classifyCapability(const TypeDecl &TD)
static constexpr std::pair< StringRef, bool > ClassifyCapabilityFallback
C Language Family Type Representation.
Expr * getCond() const
getCond - Return the expression representing the condition for the ?
Definition Expr.h:4600
Expr * getTrueExpr() const
getTrueExpr - Return the subexpression representing the value of the expression if the condition eval...
Definition Expr.h:4606
Expr * getFalseExpr() const
getFalseExpr - Return the subexpression representing the value of the expression if the condition eva...
Definition Expr.h:4612
Expr * getLHS() const
Definition Expr.h:4157
Expr * getRHS() const
Definition Expr.h:4159
Opcode getOpcode() const
Definition Expr.h:4152
succ_iterator succ_begin()
Definition CFG.h:1045
unsigned pred_size() const
Definition CFG.h:1066
const Stmt * getTerminatorCondition(bool StripParens=true) const
Definition CFG.cpp:6534
unsigned getBlockID() const
Definition CFG.h:1177
unsigned succ_size() const
Definition CFG.h:1063
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
Definition CFG.h:1487
CXXMethodDecl * getMethodDecl() const
Retrieve the declaration of the called method.
Definition ExprCXX.cpp:773
Expr * getImplicitObjectArgument() const
Retrieve the implicit object argument for the member call.
Definition ExprCXX.cpp:754
Represents a static or instance method of a struct/union/class.
Definition DeclCXX.h:2153
overridden_method_range overridden_methods() const
Definition DeclCXX.cpp:2828
CXXMethodDecl * getCanonicalDecl() override
Retrieves the "canonical" declaration of the given declaration.
Definition DeclCXX.h:2266
OverloadedOperatorKind getOperator() const
Returns the kind of overloaded operator that this expression refers to.
Definition ExprCXX.h:116
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition Expr.h:3012
Expr * getArg(unsigned Arg)
getArg - Return the specified argument.
Definition Expr.h:3216
Expr * getCallee()
Definition Expr.h:3159
unsigned getNumArgs() const
getNumArgs - Return the number of actual arguments to this call.
Definition Expr.h:3203
Expr ** getArgs()
Retrieve the call arguments.
Definition Expr.h:3206
arg_range arguments()
Definition Expr.h:3264
Decl * getCalleeDecl()
Definition Expr.h:3189
CastKind getCastKind() const
Definition Expr.h:3789
Expr * getSubExpr()
Definition Expr.h:3795
bool body_empty() const
Definition Stmt.h:1795
Stmt * body_back()
Definition Stmt.h:1819
bool isTranslationUnit() const
Definition DeclBase.h:2204
ValueDecl * getDecl()
Definition Expr.h:1383
const DeclGroupRef getDeclGroup() const
Definition Stmt.h:1660
Decl - This represents one declaration (or definition), e.g.
Definition DeclBase.h:86
T * getAttr() const
Definition DeclBase.h:582
ASTContext & getASTContext() const LLVM_READONLY
Definition DeclBase.cpp:550
bool hasAttr() const
Definition DeclBase.h:586
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Definition DeclBase.h:996
This represents one expression.
Definition Expr.h:114
Expr * IgnoreParenCasts() LLVM_READONLY
Skip past any parentheses and casts which might surround this expression until reaching a fixed point...
Definition Expr.cpp:3134
Expr * IgnoreImplicit() LLVM_READONLY
Skip past any implicit AST nodes which might surround this expression until reaching a fixed point.
Definition Expr.cpp:3117
QualType getType() const
Definition Expr.h:146
bool isStr(const char(&Str)[StrLen]) const
Return true if this is the identifier for the specified string.
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition Expr.h:3433
ValueDecl * getMemberDecl() const
Retrieve the member declaration to which this expression refers.
Definition Expr.h:3516
Expr * getBase() const
Definition Expr.h:3510
This represents a decl that may have a name.
Definition Decl.h:276
IdentifierInfo * getIdentifier() const
Get the identifier that names this declaration, if there is one.
Definition Decl.h:297
NamedDecl * getMostRecentDecl()
Definition Decl.h:503
bool isCXXInstanceMember() const
Determine whether the given declaration is an instance member of a C++ class.
Definition Decl.cpp:1977
ObjCIvarDecl * getCanonicalDecl() override
Retrieves the canonical declaration of this field.
Definition DeclObjC.h:1997
ObjCIvarDecl * getDecl()
Definition ExprObjC.h:611
const Expr * getBase() const
Definition ExprObjC.h:615
Represents a parameter to a function.
Definition Decl.h:1832
A (possibly-)qualified type.
Definition TypeBase.h:938
CompoundStmt * getSubStmt()
Definition Expr.h:4681
Stmt - This represents one statement.
Definition Stmt.h:85
StmtClass getStmtClass() const
Definition Stmt.h:1504
Represents a declaration of a type.
Definition Decl.h:3696
RecordDecl * getAsRecordDecl() const
Retrieves the RecordDecl this type refers to.
Definition Type.h:41
bool isPointerType() const
Definition TypeBase.h:8815
QualType getPointeeType() const
If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.
Definition Type.cpp:885
const ArrayType * getAsArrayTypeUnsafe() const
A variant of getAs<> for array types which silently discards qualifiers from the outermost type.
Definition TypeBase.h:9484
bool isPointerOrReferenceType() const
Definition TypeBase.h:8819
bool isAnyPointerType() const
Definition TypeBase.h:8823
const T * getAs() const
Member-template getAs<specific type>'.
Definition TypeBase.h:9431
Expr * getSubExpr() const
Definition Expr.h:2354
Opcode getOpcode() const
Definition Expr.h:2349
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition Decl.h:714
QualType getType() const
Definition Decl.h:725
Represents a variable declaration or definition.
Definition Decl.h:934
VarDecl * getCanonicalDecl() override
Retrieves the "canonical" declaration of the given declaration.
Definition Decl.cpp:2238
bool isStaticLocal() const
Returns true if a variable with function scope is a static local variable.
Definition Decl.h:1216
CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, const Expr *DeclExp, til::SExpr *Self=nullptr)
Translate a clang expression in an attribute to a til::SExpr.
til::SExpr * translate(const Stmt *S, CallingContext *Ctx)
til::SExpr * lookupStmt(const Stmt *S)
til::SCFG * buildCFG(CFGWalker &Walker)
til::SExpr * translateVariable(const VarDecl *VD, CallingContext *Ctx)
til::BasicBlock * lookupBlock(const CFGBlock *B)
const InstrArray & arguments() const
unsigned findPredecessorIndex(const BasicBlock *BB) const
Return the index of BB, or Predecessors.size if BB is not a predecessor.
A Literal pointer to an object allocated in memory.
const ValueDecl * clangDecl() const
Return the clang declaration of the variable for this Phi node, if any.
void setClangDecl(const ValueDecl *Cvd)
Set the clang variable associated with this Phi node.
const ValArray & values() const
Project a named slot from a C++ struct or class.
An SCFG is a control-flow graph.
Base class for AST nodes in the typed intermediate language.
BasicBlock * block() const
Returns the block, if this is an instruction in a basic block, otherwise returns null.
void setValues(unsigned Sz, const T &C)
Placeholder for expressions that cannot be represented in the TIL.
Placeholder for a wildcard that matches any other expression.
std::variant< struct RequiresDecl, struct HeaderDecl, struct UmbrellaDirDecl, struct ModuleDecl, struct ExcludeDecl, struct ExportDecl, struct ExportAsDecl, struct ExternModuleDecl, struct UseDecl, struct LinkDecl, struct ConfigMacrosDecl, struct ConflictDecl > Decl
All declarations that can appear in a module declaration.
void simplifyIncompleteArg(til::Phi *Ph)
TIL_BinaryOpcode
Opcode for binary arithmetic operations.
void printSCFG(CFGWalker &Walker)
std::string getSourceLiteralString(const Expr *CE)
Top level wrappers for InstallAPI frontend operations.
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
@ Match
This is not an overload because the signature exactly matches an existing declaration.
Definition Sema.h:824
bool isa(CodeGen::Address addr)
Definition Address.h:330
@ Self
'self' clause, allowed on Compute and Combined Constructs, plus 'update'.
nullptr
This class represents a compute construct, representing a 'Kind' of ‘parallel’, 'serial',...
@ Result
The result type of a method or function.
Definition TypeBase.h:906
const FunctionProtoType * T
CastKind
CastKind - The kind of operation required for a conversion.
bool declaresSameEntity(const Decl *D1, const Decl *D2)
Determine whether two declarations declare the same entity.
Definition DeclBase.h:1306
U cast(CodeGen::Address addr)
Definition Address.h:327
Encapsulates the lexical context of a function call.
llvm::PointerUnion< const Expr *const *, til::SExpr * > FunArgs
llvm::PointerUnion< const Expr *, til::SExpr * > SelfArg