1087 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// Implementation of the interfaces declared in ThreadSafetyCommon.h10//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/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.h41std::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// 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 79 return ClassifyCapabilityFallback;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 determine85 // which it is. The type should either be a record or a typedef, or a pointer86 // 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());91 if (QT->isPointerOrReferenceType())92 return classifyCapability(QT->getPointeeType());93 94 return ClassifyCapabilityFallback;95}96 97CapabilityExpr::CapabilityExpr(const til::SExpr *E, QualType QT, bool Neg) {98 const auto &[Kind, Reentrant] = classifyCapability(QT);99 *this = CapabilityExpr(E, Kind, Neg, Reentrant);100}101 102using CallingContext = SExprBuilder::CallingContext;103 104til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) { return SMap.lookup(S); }105 106til::SCFG *SExprBuilder::buildCFG(CFGWalker &Walker) {107 Walker.walk(*this);108 return Scfg;109}110 111static bool isCalleeArrow(const Expr *E) {112 const auto *ME = dyn_cast<MemberExpr>(E->IgnoreParenCasts());113 return ME ? ME->isArrow() : false;114}115 116/// Translate a clang expression in an attribute to a til::SExpr.117/// Constructs the context from D, DeclExp, and SelfDecl.118///119/// \param AttrExp The expression to translate.120/// \param D The declaration to which the attribute is attached.121/// \param DeclExp An expression involving the Decl to which the attribute122/// is attached. E.g. the call to a function.123/// \param Self S-expression to substitute for a \ref CXXThisExpr in a call,124/// or argument to a cleanup function.125CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp,126 const NamedDecl *D,127 const Expr *DeclExp,128 til::SExpr *Self) {129 // If we are processing a raw attribute expression, with no substitutions.130 if (!DeclExp && !Self)131 return translateAttrExpr(AttrExp, nullptr);132 133 CallingContext Ctx(nullptr, D);134 135 // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute136 // for formal parameters when we call buildMutexID later.137 if (!DeclExp)138 /* We'll use Self. */;139 else if (const auto *ME = dyn_cast<MemberExpr>(DeclExp)) {140 Ctx.SelfArg = ME->getBase();141 Ctx.SelfArrow = ME->isArrow();142 } else if (const auto *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) {143 Ctx.SelfArg = CE->getImplicitObjectArgument();144 Ctx.SelfArrow = isCalleeArrow(CE->getCallee());145 Ctx.NumArgs = CE->getNumArgs();146 Ctx.FunArgs = CE->getArgs();147 } else if (const auto *CE = dyn_cast<CallExpr>(DeclExp)) {148 // Calls to operators that are members need to be treated like member calls.149 if (isa<CXXOperatorCallExpr>(CE) && isa<CXXMethodDecl>(D)) {150 Ctx.SelfArg = CE->getArg(0);151 Ctx.SelfArrow = false;152 Ctx.NumArgs = CE->getNumArgs() - 1;153 Ctx.FunArgs = CE->getArgs() + 1;154 } else {155 Ctx.NumArgs = CE->getNumArgs();156 Ctx.FunArgs = CE->getArgs();157 }158 } else if (const auto *CE = dyn_cast<CXXConstructExpr>(DeclExp)) {159 Ctx.SelfArg = nullptr; // Will be set below160 Ctx.NumArgs = CE->getNumArgs();161 Ctx.FunArgs = CE->getArgs();162 }163 164 // Usually we want to substitute the self-argument for "this", but lambdas165 // are an exception: "this" on or in a lambda call operator doesn't refer166 // to the lambda, but to captured "this" in the context it was created in.167 // This can happen for operator calls and member calls, so fix it up here.168 if (const auto *CMD = dyn_cast<CXXMethodDecl>(D))169 if (CMD->getParent()->isLambda())170 Ctx.SelfArg = nullptr;171 172 if (Self) {173 assert(!Ctx.SelfArg && "Ambiguous self argument");174 assert(isa<FunctionDecl>(D) && "Self argument requires function");175 if (isa<CXXMethodDecl>(D))176 Ctx.SelfArg = Self;177 else178 Ctx.FunArgs = Self;179 180 // If the attribute has no arguments, then assume the argument is "this".181 if (!AttrExp)182 return CapabilityExpr(183 Self, cast<CXXMethodDecl>(D)->getFunctionObjectParameterType(),184 false);185 else // For most attributes.186 return translateAttrExpr(AttrExp, &Ctx);187 }188 189 // If the attribute has no arguments, then assume the argument is "this".190 if (!AttrExp)191 return translateAttrExpr(cast<const Expr *>(Ctx.SelfArg), nullptr);192 else // For most attributes.193 return translateAttrExpr(AttrExp, &Ctx);194}195 196/// Translate a clang expression in an attribute to a til::SExpr.197// This assumes a CallingContext has already been created.198CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp,199 CallingContext *Ctx) {200 if (!AttrExp)201 return CapabilityExpr();202 203 if (const auto* SLit = dyn_cast<StringLiteral>(AttrExp)) {204 if (SLit->getString() == "*")205 // The "*" expr is a universal lock, which essentially turns off206 // checks until it is removed from the lockset.207 return CapabilityExpr(new (Arena) til::Wildcard(), StringRef("wildcard"),208 /*Neg=*/false, /*Reentrant=*/false);209 else210 // Ignore other string literals for now.211 return CapabilityExpr();212 }213 214 bool Neg = false;215 if (const auto *OE = dyn_cast<CXXOperatorCallExpr>(AttrExp)) {216 if (OE->getOperator() == OO_Exclaim) {217 Neg = true;218 AttrExp = OE->getArg(0);219 }220 }221 else if (const auto *UO = dyn_cast<UnaryOperator>(AttrExp)) {222 if (UO->getOpcode() == UO_LNot) {223 Neg = true;224 AttrExp = UO->getSubExpr()->IgnoreImplicit();225 }226 }227 228 const til::SExpr *E = translate(AttrExp, Ctx);229 230 // Trap mutex expressions like nullptr, or 0.231 // Any literal value is nonsense.232 if (!E || isa<til::Literal>(E))233 return CapabilityExpr();234 235 // Hack to deal with smart pointers -- strip off top-level pointer casts.236 if (const auto *CE = dyn_cast<til::Cast>(E)) {237 if (CE->castOpcode() == til::CAST_objToPtr)238 E = CE->expr();239 }240 return CapabilityExpr(E, AttrExp->getType(), Neg);241}242 243til::SExpr *SExprBuilder::translateVariable(const VarDecl *VD,244 CallingContext *Ctx) {245 assert(VD);246 247 // General recursion guard for x = f(x). If we are already in the process of248 // defining VD, use its pre-assignment value to break the cycle.249 if (VarsBeingTranslated.contains(VD->getCanonicalDecl()))250 return new (Arena) til::LiteralPtr(VD);251 252 // The closure captures state that is updated to correctly translate chains of253 // aliases. Restore it when we are done with recursive translation.254 auto Cleanup = llvm::make_scope_exit(255 [&, RestoreClosure =256 VarsBeingTranslated.empty() ? LookupLocalVarExpr : nullptr] {257 VarsBeingTranslated.erase(VD->getCanonicalDecl());258 if (VarsBeingTranslated.empty())259 LookupLocalVarExpr = RestoreClosure;260 });261 VarsBeingTranslated.insert(VD->getCanonicalDecl());262 263 QualType Ty = VD->getType();264 if (!VD->isStaticLocal() && Ty->isPointerType()) {265 // Substitute local variable aliases with a canonical definition.266 if (LookupLocalVarExpr) {267 // Attempt to resolve an alias through the more complex local variable map268 // lookup. This will fail with complex control-flow graphs (where we269 // revert to no alias resolution to retain stable variable names).270 if (const Expr *E = LookupLocalVarExpr(VD)) {271 til::SExpr *Result = translate(E, Ctx);272 // Unsupported expression (such as heap allocations) will be undefined;273 // rather than failing here, we simply revert to the pointer being the274 // canonical variable.275 if (Result && !isa<til::Undefined>(Result))276 return Result;277 }278 }279 }280 281 return new (Arena) til::LiteralPtr(VD);282}283 284// Translate a clang statement or expression to a TIL expression.285// Also performs substitution of variables; Ctx provides the context.286// Dispatches on the type of S.287til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) {288 if (!S)289 return nullptr;290 291 // Check if S has already been translated and cached.292 // This handles the lookup of SSA names for DeclRefExprs here.293 if (til::SExpr *E = lookupStmt(S))294 return E;295 296 switch (S->getStmtClass()) {297 case Stmt::DeclRefExprClass:298 return translateDeclRefExpr(cast<DeclRefExpr>(S), Ctx);299 case Stmt::CXXThisExprClass:300 return translateCXXThisExpr(cast<CXXThisExpr>(S), Ctx);301 case Stmt::MemberExprClass:302 return translateMemberExpr(cast<MemberExpr>(S), Ctx);303 case Stmt::ObjCIvarRefExprClass:304 return translateObjCIVarRefExpr(cast<ObjCIvarRefExpr>(S), Ctx);305 case Stmt::CallExprClass:306 return translateCallExpr(cast<CallExpr>(S), Ctx);307 case Stmt::CXXMemberCallExprClass:308 return translateCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), Ctx);309 case Stmt::CXXOperatorCallExprClass:310 return translateCXXOperatorCallExpr(cast<CXXOperatorCallExpr>(S), Ctx);311 case Stmt::UnaryOperatorClass:312 return translateUnaryOperator(cast<UnaryOperator>(S), Ctx);313 case Stmt::BinaryOperatorClass:314 case Stmt::CompoundAssignOperatorClass:315 return translateBinaryOperator(cast<BinaryOperator>(S), Ctx);316 317 case Stmt::ArraySubscriptExprClass:318 return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx);319 case Stmt::ConditionalOperatorClass:320 return translateAbstractConditionalOperator(321 cast<ConditionalOperator>(S), Ctx);322 case Stmt::BinaryConditionalOperatorClass:323 return translateAbstractConditionalOperator(324 cast<BinaryConditionalOperator>(S), Ctx);325 326 // We treat these as no-ops327 case Stmt::ConstantExprClass:328 return translate(cast<ConstantExpr>(S)->getSubExpr(), Ctx);329 case Stmt::ParenExprClass:330 return translate(cast<ParenExpr>(S)->getSubExpr(), Ctx);331 case Stmt::ExprWithCleanupsClass:332 return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx);333 case Stmt::CXXBindTemporaryExprClass:334 return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx);335 case Stmt::MaterializeTemporaryExprClass:336 return translate(cast<MaterializeTemporaryExpr>(S)->getSubExpr(), Ctx);337 338 // Collect all literals339 case Stmt::CharacterLiteralClass:340 case Stmt::CXXNullPtrLiteralExprClass:341 case Stmt::GNUNullExprClass:342 case Stmt::CXXBoolLiteralExprClass:343 case Stmt::FloatingLiteralClass:344 case Stmt::ImaginaryLiteralClass:345 case Stmt::IntegerLiteralClass:346 case Stmt::StringLiteralClass:347 case Stmt::ObjCStringLiteralClass:348 return new (Arena) til::Literal(cast<Expr>(S));349 350 case Stmt::DeclStmtClass:351 return translateDeclStmt(cast<DeclStmt>(S), Ctx);352 case Stmt::StmtExprClass:353 return translateStmtExpr(cast<StmtExpr>(S), Ctx);354 default:355 break;356 }357 if (const auto *CE = dyn_cast<CastExpr>(S))358 return translateCastExpr(CE, Ctx);359 360 return new (Arena) til::Undefined(S);361}362 363til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE,364 CallingContext *Ctx) {365 const auto *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl());366 367 // Function parameters require substitution and/or renaming.368 if (const auto *PV = dyn_cast<ParmVarDecl>(VD)) {369 unsigned I = PV->getFunctionScopeIndex();370 const DeclContext *D = PV->getDeclContext();371 if (Ctx && Ctx->FunArgs) {372 const Decl *Canonical = Ctx->AttrDecl->getCanonicalDecl();373 if (isa<FunctionDecl>(D)374 ? (cast<FunctionDecl>(D)->getCanonicalDecl() == Canonical)375 : (cast<ObjCMethodDecl>(D)->getCanonicalDecl() == Canonical)) {376 // Substitute call arguments for references to function parameters377 if (const Expr *const *FunArgs =378 dyn_cast<const Expr *const *>(Ctx->FunArgs)) {379 assert(I < Ctx->NumArgs);380 return translate(FunArgs[I], Ctx->Prev);381 }382 383 assert(I == 0);384 return cast<til::SExpr *>(Ctx->FunArgs);385 }386 }387 // Map the param back to the param of the original function declaration388 // for consistent comparisons.389 VD = isa<FunctionDecl>(D)390 ? cast<FunctionDecl>(D)->getCanonicalDecl()->getParamDecl(I)391 : cast<ObjCMethodDecl>(D)->getCanonicalDecl()->getParamDecl(I);392 }393 394 if (const auto *VarD = dyn_cast<VarDecl>(VD))395 return translateVariable(VarD, Ctx);396 397 // For non-local variables, treat it as a reference to a named object.398 return new (Arena) til::LiteralPtr(VD);399}400 401til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE,402 CallingContext *Ctx) {403 // Substitute for 'this'404 if (Ctx && Ctx->SelfArg) {405 if (const auto *SelfArg = dyn_cast<const Expr *>(Ctx->SelfArg))406 return translate(SelfArg, Ctx->Prev);407 else408 return cast<til::SExpr *>(Ctx->SelfArg);409 }410 assert(SelfVar && "We have no variable for 'this'!");411 return SelfVar;412}413 414static const ValueDecl *getValueDeclFromSExpr(const til::SExpr *E) {415 if (const auto *V = dyn_cast<til::Variable>(E))416 return V->clangDecl();417 if (const auto *Ph = dyn_cast<til::Phi>(E))418 return Ph->clangDecl();419 if (const auto *P = dyn_cast<til::Project>(E))420 return P->clangDecl();421 if (const auto *L = dyn_cast<til::LiteralPtr>(E))422 return L->clangDecl();423 return nullptr;424}425 426static bool hasAnyPointerType(const til::SExpr *E) {427 auto *VD = getValueDeclFromSExpr(E);428 if (VD && VD->getType()->isAnyPointerType())429 return true;430 if (const auto *C = dyn_cast<til::Cast>(E))431 return C->castOpcode() == til::CAST_objToPtr;432 433 return false;434}435 436// Grab the very first declaration of virtual method D437static const CXXMethodDecl *getFirstVirtualDecl(const CXXMethodDecl *D) {438 while (true) {439 D = D->getCanonicalDecl();440 auto OverriddenMethods = D->overridden_methods();441 if (OverriddenMethods.begin() == OverriddenMethods.end())442 return D; // Method does not override anything443 // FIXME: this does not work with multiple inheritance.444 D = *OverriddenMethods.begin();445 }446 return nullptr;447}448 449til::SExpr *SExprBuilder::translateMemberExpr(const MemberExpr *ME,450 CallingContext *Ctx) {451 til::SExpr *BE = translate(ME->getBase(), Ctx);452 til::SExpr *E = new (Arena) til::SApply(BE);453 454 const auto *D = cast<ValueDecl>(ME->getMemberDecl()->getCanonicalDecl());455 if (const auto *VD = dyn_cast<CXXMethodDecl>(D))456 D = getFirstVirtualDecl(VD);457 458 til::Project *P = new (Arena) til::Project(E, D);459 if (hasAnyPointerType(BE))460 P->setArrow(true);461 return P;462}463 464til::SExpr *SExprBuilder::translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE,465 CallingContext *Ctx) {466 til::SExpr *BE = translate(IVRE->getBase(), Ctx);467 til::SExpr *E = new (Arena) til::SApply(BE);468 469 const auto *D = cast<ObjCIvarDecl>(IVRE->getDecl()->getCanonicalDecl());470 471 til::Project *P = new (Arena) til::Project(E, D);472 if (hasAnyPointerType(BE))473 P->setArrow(true);474 return P;475}476 477til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE,478 CallingContext *Ctx,479 const Expr *SelfE) {480 if (CapabilityExprMode) {481 // Handle LOCK_RETURNED482 if (const FunctionDecl *FD = CE->getDirectCallee()) {483 FD = FD->getMostRecentDecl();484 if (LockReturnedAttr *At = FD->getAttr<LockReturnedAttr>()) {485 CallingContext LRCallCtx(Ctx);486 LRCallCtx.AttrDecl = CE->getDirectCallee();487 LRCallCtx.SelfArg = SelfE;488 LRCallCtx.NumArgs = CE->getNumArgs();489 LRCallCtx.FunArgs = CE->getArgs();490 return const_cast<til::SExpr *>(491 translateAttrExpr(At->getArg(), &LRCallCtx).sexpr());492 }493 }494 }495 496 til::SExpr *E = translate(CE->getCallee(), Ctx);497 for (const auto *Arg : CE->arguments()) {498 til::SExpr *A = translate(Arg, Ctx);499 E = new (Arena) til::Apply(E, A);500 }501 return new (Arena) til::Call(E, CE);502}503 504til::SExpr *SExprBuilder::translateCXXMemberCallExpr(505 const CXXMemberCallExpr *ME, CallingContext *Ctx) {506 if (CapabilityExprMode) {507 // Ignore calls to get() on smart pointers.508 if (ME->getMethodDecl()->getNameAsString() == "get" &&509 ME->getNumArgs() == 0) {510 auto *E = translate(ME->getImplicitObjectArgument(), Ctx);511 return new (Arena) til::Cast(til::CAST_objToPtr, E);512 // return E;513 }514 }515 return translateCallExpr(cast<CallExpr>(ME), Ctx,516 ME->getImplicitObjectArgument());517}518 519til::SExpr *SExprBuilder::translateCXXOperatorCallExpr(520 const CXXOperatorCallExpr *OCE, CallingContext *Ctx) {521 if (CapabilityExprMode) {522 // Ignore operator * and operator -> on smart pointers.523 OverloadedOperatorKind k = OCE->getOperator();524 if (k == OO_Star || k == OO_Arrow) {525 auto *E = translate(OCE->getArg(0), Ctx);526 return new (Arena) til::Cast(til::CAST_objToPtr, E);527 // return E;528 }529 }530 return translateCallExpr(cast<CallExpr>(OCE), Ctx);531}532 533til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO,534 CallingContext *Ctx) {535 switch (UO->getOpcode()) {536 case UO_PostInc:537 case UO_PostDec:538 case UO_PreInc:539 case UO_PreDec:540 return new (Arena) til::Undefined(UO);541 542 case UO_AddrOf:543 if (CapabilityExprMode) {544 // interpret &Graph::mu_ as an existential.545 if (const auto *DRE = dyn_cast<DeclRefExpr>(UO->getSubExpr())) {546 if (DRE->getDecl()->isCXXInstanceMember()) {547 // This is a pointer-to-member expression, e.g. &MyClass::mu_.548 // We interpret this syntax specially, as a wildcard.549 auto *W = new (Arena) til::Wildcard();550 return new (Arena) til::Project(W, DRE->getDecl());551 }552 }553 }554 // otherwise, & is a no-op555 return translate(UO->getSubExpr(), Ctx);556 557 // We treat these as no-ops558 case UO_Deref:559 case UO_Plus:560 return translate(UO->getSubExpr(), Ctx);561 562 case UO_Minus:563 return new (Arena)564 til::UnaryOp(til::UOP_Minus, translate(UO->getSubExpr(), Ctx));565 case UO_Not:566 return new (Arena)567 til::UnaryOp(til::UOP_BitNot, translate(UO->getSubExpr(), Ctx));568 case UO_LNot:569 return new (Arena)570 til::UnaryOp(til::UOP_LogicNot, translate(UO->getSubExpr(), Ctx));571 572 // Currently unsupported573 case UO_Real:574 case UO_Imag:575 case UO_Extension:576 case UO_Coawait:577 return new (Arena) til::Undefined(UO);578 }579 return new (Arena) til::Undefined(UO);580}581 582til::SExpr *SExprBuilder::translateBinOp(til::TIL_BinaryOpcode Op,583 const BinaryOperator *BO,584 CallingContext *Ctx, bool Reverse) {585 til::SExpr *E0 = translate(BO->getLHS(), Ctx);586 til::SExpr *E1 = translate(BO->getRHS(), Ctx);587 if (Reverse)588 return new (Arena) til::BinaryOp(Op, E1, E0);589 else590 return new (Arena) til::BinaryOp(Op, E0, E1);591}592 593til::SExpr *SExprBuilder::translateBinAssign(til::TIL_BinaryOpcode Op,594 const BinaryOperator *BO,595 CallingContext *Ctx,596 bool Assign) {597 const Expr *LHS = BO->getLHS();598 const Expr *RHS = BO->getRHS();599 til::SExpr *E0 = translate(LHS, Ctx);600 til::SExpr *E1 = translate(RHS, Ctx);601 602 const ValueDecl *VD = nullptr;603 til::SExpr *CV = nullptr;604 if (const auto *DRE = dyn_cast<DeclRefExpr>(LHS)) {605 VD = DRE->getDecl();606 CV = lookupVarDecl(VD);607 }608 609 if (!Assign) {610 til::SExpr *Arg = CV ? CV : new (Arena) til::Load(E0);611 E1 = new (Arena) til::BinaryOp(Op, Arg, E1);612 E1 = addStatement(E1, nullptr, VD);613 }614 if (VD && CV)615 return updateVarDecl(VD, E1);616 return new (Arena) til::Store(E0, E1);617}618 619til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO,620 CallingContext *Ctx) {621 switch (BO->getOpcode()) {622 case BO_PtrMemD:623 case BO_PtrMemI:624 return new (Arena) til::Undefined(BO);625 626 case BO_Mul: return translateBinOp(til::BOP_Mul, BO, Ctx);627 case BO_Div: return translateBinOp(til::BOP_Div, BO, Ctx);628 case BO_Rem: return translateBinOp(til::BOP_Rem, BO, Ctx);629 case BO_Add: return translateBinOp(til::BOP_Add, BO, Ctx);630 case BO_Sub: return translateBinOp(til::BOP_Sub, BO, Ctx);631 case BO_Shl: return translateBinOp(til::BOP_Shl, BO, Ctx);632 case BO_Shr: return translateBinOp(til::BOP_Shr, BO, Ctx);633 case BO_LT: return translateBinOp(til::BOP_Lt, BO, Ctx);634 case BO_GT: return translateBinOp(til::BOP_Lt, BO, Ctx, true);635 case BO_LE: return translateBinOp(til::BOP_Leq, BO, Ctx);636 case BO_GE: return translateBinOp(til::BOP_Leq, BO, Ctx, true);637 case BO_EQ: return translateBinOp(til::BOP_Eq, BO, Ctx);638 case BO_NE: return translateBinOp(til::BOP_Neq, BO, Ctx);639 case BO_Cmp: return translateBinOp(til::BOP_Cmp, BO, Ctx);640 case BO_And: return translateBinOp(til::BOP_BitAnd, BO, Ctx);641 case BO_Xor: return translateBinOp(til::BOP_BitXor, BO, Ctx);642 case BO_Or: return translateBinOp(til::BOP_BitOr, BO, Ctx);643 case BO_LAnd: return translateBinOp(til::BOP_LogicAnd, BO, Ctx);644 case BO_LOr: return translateBinOp(til::BOP_LogicOr, BO, Ctx);645 646 case BO_Assign: return translateBinAssign(til::BOP_Eq, BO, Ctx, true);647 case BO_MulAssign: return translateBinAssign(til::BOP_Mul, BO, Ctx);648 case BO_DivAssign: return translateBinAssign(til::BOP_Div, BO, Ctx);649 case BO_RemAssign: return translateBinAssign(til::BOP_Rem, BO, Ctx);650 case BO_AddAssign: return translateBinAssign(til::BOP_Add, BO, Ctx);651 case BO_SubAssign: return translateBinAssign(til::BOP_Sub, BO, Ctx);652 case BO_ShlAssign: return translateBinAssign(til::BOP_Shl, BO, Ctx);653 case BO_ShrAssign: return translateBinAssign(til::BOP_Shr, BO, Ctx);654 case BO_AndAssign: return translateBinAssign(til::BOP_BitAnd, BO, Ctx);655 case BO_XorAssign: return translateBinAssign(til::BOP_BitXor, BO, Ctx);656 case BO_OrAssign: return translateBinAssign(til::BOP_BitOr, BO, Ctx);657 658 case BO_Comma:659 // The clang CFG should have already processed both sides.660 return translate(BO->getRHS(), Ctx);661 }662 return new (Arena) til::Undefined(BO);663}664 665til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE,666 CallingContext *Ctx) {667 CastKind K = CE->getCastKind();668 switch (K) {669 case CK_LValueToRValue: {670 if (const auto *DRE = dyn_cast<DeclRefExpr>(CE->getSubExpr())) {671 til::SExpr *E0 = lookupVarDecl(DRE->getDecl());672 if (E0)673 return E0;674 }675 til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);676 return E0;677 // FIXME!! -- get Load working properly678 // return new (Arena) til::Load(E0);679 }680 case CK_NoOp:681 case CK_DerivedToBase:682 case CK_UncheckedDerivedToBase:683 case CK_ArrayToPointerDecay:684 case CK_FunctionToPointerDecay: {685 til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);686 return E0;687 }688 default: {689 // FIXME: handle different kinds of casts.690 til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);691 if (CapabilityExprMode)692 return E0;693 return new (Arena) til::Cast(til::CAST_none, E0);694 }695 }696}697 698til::SExpr *699SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E,700 CallingContext *Ctx) {701 til::SExpr *E0 = translate(E->getBase(), Ctx);702 til::SExpr *E1 = translate(E->getIdx(), Ctx);703 return new (Arena) til::ArrayIndex(E0, E1);704}705 706til::SExpr *707SExprBuilder::translateAbstractConditionalOperator(708 const AbstractConditionalOperator *CO, CallingContext *Ctx) {709 auto *C = translate(CO->getCond(), Ctx);710 auto *T = translate(CO->getTrueExpr(), Ctx);711 auto *E = translate(CO->getFalseExpr(), Ctx);712 return new (Arena) til::IfThenElse(C, T, E);713}714 715til::SExpr *716SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) {717 DeclGroupRef DGrp = S->getDeclGroup();718 for (auto *I : DGrp) {719 if (auto *VD = dyn_cast_or_null<VarDecl>(I)) {720 Expr *E = VD->getInit();721 til::SExpr* SE = translate(E, Ctx);722 723 // Add local variables with trivial type to the variable map724 QualType T = VD->getType();725 if (T.isTrivialType(VD->getASTContext()))726 return addVarDecl(VD, SE);727 else {728 // TODO: add alloca729 }730 }731 }732 return nullptr;733}734 735til::SExpr *SExprBuilder::translateStmtExpr(const StmtExpr *SE,736 CallingContext *Ctx) {737 // The value of a statement expression is the value of the last statement,738 // which must be an expression.739 const CompoundStmt *CS = SE->getSubStmt();740 return CS->body_empty() ? new (Arena) til::Undefined(SE)741 : translate(CS->body_back(), Ctx);742}743 744// If (E) is non-trivial, then add it to the current basic block, and745// update the statement map so that S refers to E. Returns a new variable746// that refers to E.747// If E is trivial returns E.748til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S,749 const ValueDecl *VD) {750 if (!E || !CurrentBB || E->block() || til::ThreadSafetyTIL::isTrivial(E))751 return E;752 if (VD)753 E = new (Arena) til::Variable(E, VD);754 CurrentInstructions.push_back(E);755 if (S)756 insertStmt(S, E);757 return E;758}759 760// Returns the current value of VD, if known, and nullptr otherwise.761til::SExpr *SExprBuilder::lookupVarDecl(const ValueDecl *VD) {762 auto It = LVarIdxMap.find(VD);763 if (It != LVarIdxMap.end()) {764 assert(CurrentLVarMap[It->second].first == VD);765 return CurrentLVarMap[It->second].second;766 }767 return nullptr;768}769 770// if E is a til::Variable, update its clangDecl.771static void maybeUpdateVD(til::SExpr *E, const ValueDecl *VD) {772 if (!E)773 return;774 if (auto *V = dyn_cast<til::Variable>(E)) {775 if (!V->clangDecl())776 V->setClangDecl(VD);777 }778}779 780// Adds a new variable declaration.781til::SExpr *SExprBuilder::addVarDecl(const ValueDecl *VD, til::SExpr *E) {782 maybeUpdateVD(E, VD);783 LVarIdxMap.insert(std::make_pair(VD, CurrentLVarMap.size()));784 CurrentLVarMap.makeWritable();785 CurrentLVarMap.push_back(std::make_pair(VD, E));786 return E;787}788 789// Updates a current variable declaration. (E.g. by assignment)790til::SExpr *SExprBuilder::updateVarDecl(const ValueDecl *VD, til::SExpr *E) {791 maybeUpdateVD(E, VD);792 auto It = LVarIdxMap.find(VD);793 if (It == LVarIdxMap.end()) {794 til::SExpr *Ptr = new (Arena) til::LiteralPtr(VD);795 til::SExpr *St = new (Arena) til::Store(Ptr, E);796 return St;797 }798 CurrentLVarMap.makeWritable();799 CurrentLVarMap.elem(It->second).second = E;800 return E;801}802 803// Make a Phi node in the current block for the i^th variable in CurrentVarMap.804// If E != null, sets Phi[CurrentBlockInfo->ArgIndex] = E.805// If E == null, this is a backedge and will be set later.806void SExprBuilder::makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E) {807 unsigned ArgIndex = CurrentBlockInfo->ProcessedPredecessors;808 assert(ArgIndex > 0 && ArgIndex < NPreds);809 810 til::SExpr *CurrE = CurrentLVarMap[i].second;811 if (CurrE->block() == CurrentBB) {812 // We already have a Phi node in the current block,813 // so just add the new variable to the Phi node.814 auto *Ph = dyn_cast<til::Phi>(CurrE);815 assert(Ph && "Expecting Phi node.");816 if (E)817 Ph->values()[ArgIndex] = E;818 return;819 }820 821 // Make a new phi node: phi(..., E)822 // All phi args up to the current index are set to the current value.823 til::Phi *Ph = new (Arena) til::Phi(Arena, NPreds);824 Ph->values().setValues(NPreds, nullptr);825 for (unsigned PIdx = 0; PIdx < ArgIndex; ++PIdx)826 Ph->values()[PIdx] = CurrE;827 if (E)828 Ph->values()[ArgIndex] = E;829 Ph->setClangDecl(CurrentLVarMap[i].first);830 // If E is from a back-edge, or either E or CurrE are incomplete, then831 // mark this node as incomplete; we may need to remove it later.832 if (!E || isIncompletePhi(E) || isIncompletePhi(CurrE))833 Ph->setStatus(til::Phi::PH_Incomplete);834 835 // Add Phi node to current block, and update CurrentLVarMap[i]836 CurrentArguments.push_back(Ph);837 if (Ph->status() == til::Phi::PH_Incomplete)838 IncompleteArgs.push_back(Ph);839 840 CurrentLVarMap.makeWritable();841 CurrentLVarMap.elem(i).second = Ph;842}843 844// Merge values from Map into the current variable map.845// This will construct Phi nodes in the current basic block as necessary.846void SExprBuilder::mergeEntryMap(LVarDefinitionMap Map) {847 assert(CurrentBlockInfo && "Not processing a block!");848 849 if (!CurrentLVarMap.valid()) {850 // Steal Map, using copy-on-write.851 CurrentLVarMap = std::move(Map);852 return;853 }854 if (CurrentLVarMap.sameAs(Map))855 return; // Easy merge: maps from different predecessors are unchanged.856 857 unsigned NPreds = CurrentBB->numPredecessors();858 unsigned ESz = CurrentLVarMap.size();859 unsigned MSz = Map.size();860 unsigned Sz = std::min(ESz, MSz);861 862 for (unsigned i = 0; i < Sz; ++i) {863 if (CurrentLVarMap[i].first != Map[i].first) {864 // We've reached the end of variables in common.865 CurrentLVarMap.makeWritable();866 CurrentLVarMap.downsize(i);867 break;868 }869 if (CurrentLVarMap[i].second != Map[i].second)870 makePhiNodeVar(i, NPreds, Map[i].second);871 }872 if (ESz > MSz) {873 CurrentLVarMap.makeWritable();874 CurrentLVarMap.downsize(Map.size());875 }876}877 878// Merge a back edge into the current variable map.879// This will create phi nodes for all variables in the variable map.880void SExprBuilder::mergeEntryMapBackEdge() {881 // We don't have definitions for variables on the backedge, because we882 // haven't gotten that far in the CFG. Thus, when encountering a back edge,883 // we conservatively create Phi nodes for all variables. Unnecessary Phi884 // nodes will be marked as incomplete, and stripped out at the end.885 //886 // An Phi node is unnecessary if it only refers to itself and one other887 // variable, e.g. x = Phi(y, y, x) can be reduced to x = y.888 889 assert(CurrentBlockInfo && "Not processing a block!");890 891 if (CurrentBlockInfo->HasBackEdges)892 return;893 CurrentBlockInfo->HasBackEdges = true;894 895 CurrentLVarMap.makeWritable();896 unsigned Sz = CurrentLVarMap.size();897 unsigned NPreds = CurrentBB->numPredecessors();898 899 for (unsigned i = 0; i < Sz; ++i)900 makePhiNodeVar(i, NPreds, nullptr);901}902 903// Update the phi nodes that were initially created for a back edge904// once the variable definitions have been computed.905// I.e., merge the current variable map into the phi nodes for Blk.906void SExprBuilder::mergePhiNodesBackEdge(const CFGBlock *Blk) {907 til::BasicBlock *BB = lookupBlock(Blk);908 unsigned ArgIndex = BBInfo[Blk->getBlockID()].ProcessedPredecessors;909 assert(ArgIndex > 0 && ArgIndex < BB->numPredecessors());910 911 for (til::SExpr *PE : BB->arguments()) {912 auto *Ph = dyn_cast_or_null<til::Phi>(PE);913 assert(Ph && "Expecting Phi Node.");914 assert(Ph->values()[ArgIndex] == nullptr && "Wrong index for back edge.");915 916 til::SExpr *E = lookupVarDecl(Ph->clangDecl());917 assert(E && "Couldn't find local variable for Phi node.");918 Ph->values()[ArgIndex] = E;919 }920}921 922void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D,923 const CFGBlock *First) {924 // Perform initial setup operations.925 unsigned NBlocks = Cfg->getNumBlockIDs();926 Scfg = new (Arena) til::SCFG(Arena, NBlocks);927 928 // allocate all basic blocks immediately, to handle forward references.929 BBInfo.resize(NBlocks);930 BlockMap.resize(NBlocks, nullptr);931 // create map from clang blockID to til::BasicBlocks932 for (auto *B : *Cfg) {933 auto *BB = new (Arena) til::BasicBlock(Arena);934 BB->reserveInstructions(B->size());935 BlockMap[B->getBlockID()] = BB;936 }937 938 CurrentBB = lookupBlock(&Cfg->getEntry());939 auto Parms = isa<ObjCMethodDecl>(D) ? cast<ObjCMethodDecl>(D)->parameters()940 : cast<FunctionDecl>(D)->parameters();941 for (auto *Pm : Parms) {942 QualType T = Pm->getType();943 if (!T.isTrivialType(Pm->getASTContext()))944 continue;945 946 // Add parameters to local variable map.947 // FIXME: right now we emulate params with loads; that should be fixed.948 til::SExpr *Lp = new (Arena) til::LiteralPtr(Pm);949 til::SExpr *Ld = new (Arena) til::Load(Lp);950 til::SExpr *V = addStatement(Ld, nullptr, Pm);951 addVarDecl(Pm, V);952 }953}954 955void SExprBuilder::enterCFGBlock(const CFGBlock *B) {956 // Initialize TIL basic block and add it to the CFG.957 CurrentBB = lookupBlock(B);958 CurrentBB->reservePredecessors(B->pred_size());959 Scfg->add(CurrentBB);960 961 CurrentBlockInfo = &BBInfo[B->getBlockID()];962 963 // CurrentLVarMap is moved to ExitMap on block exit.964 // FIXME: the entry block will hold function parameters.965 // assert(!CurrentLVarMap.valid() && "CurrentLVarMap already initialized.");966}967 968void SExprBuilder::handlePredecessor(const CFGBlock *Pred) {969 // Compute CurrentLVarMap on entry from ExitMaps of predecessors970 971 CurrentBB->addPredecessor(BlockMap[Pred->getBlockID()]);972 BlockInfo *PredInfo = &BBInfo[Pred->getBlockID()];973 assert(PredInfo->UnprocessedSuccessors > 0);974 975 if (--PredInfo->UnprocessedSuccessors == 0)976 mergeEntryMap(std::move(PredInfo->ExitMap));977 else978 mergeEntryMap(PredInfo->ExitMap.clone());979 980 ++CurrentBlockInfo->ProcessedPredecessors;981}982 983void SExprBuilder::handlePredecessorBackEdge(const CFGBlock *Pred) {984 mergeEntryMapBackEdge();985}986 987void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) {988 // The merge*() methods have created arguments.989 // Push those arguments onto the basic block.990 CurrentBB->arguments().reserve(991 static_cast<unsigned>(CurrentArguments.size()), Arena);992 for (auto *A : CurrentArguments)993 CurrentBB->addArgument(A);994}995 996void SExprBuilder::handleStatement(const Stmt *S) {997 til::SExpr *E = translate(S, nullptr);998 addStatement(E, S);999}1000 1001void SExprBuilder::handleDestructorCall(const VarDecl *VD,1002 const CXXDestructorDecl *DD) {1003 til::SExpr *Sf = new (Arena) til::LiteralPtr(VD);1004 til::SExpr *Dr = new (Arena) til::LiteralPtr(DD);1005 til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf);1006 til::SExpr *E = new (Arena) til::Call(Ap);1007 addStatement(E, nullptr);1008}1009 1010void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) {1011 CurrentBB->instructions().reserve(1012 static_cast<unsigned>(CurrentInstructions.size()), Arena);1013 for (auto *V : CurrentInstructions)1014 CurrentBB->addInstruction(V);1015 1016 // Create an appropriate terminator1017 unsigned N = B->succ_size();1018 auto It = B->succ_begin();1019 if (N == 1) {1020 til::BasicBlock *BB = *It ? lookupBlock(*It) : nullptr;1021 // TODO: set index1022 unsigned Idx = BB ? BB->findPredecessorIndex(CurrentBB) : 0;1023 auto *Tm = new (Arena) til::Goto(BB, Idx);1024 CurrentBB->setTerminator(Tm);1025 }1026 else if (N == 2) {1027 til::SExpr *C = translate(B->getTerminatorCondition(true), nullptr);1028 til::BasicBlock *BB1 = *It ? lookupBlock(*It) : nullptr;1029 ++It;1030 til::BasicBlock *BB2 = *It ? lookupBlock(*It) : nullptr;1031 // FIXME: make sure these aren't critical edges.1032 auto *Tm = new (Arena) til::Branch(C, BB1, BB2);1033 CurrentBB->setTerminator(Tm);1034 }1035}1036 1037void SExprBuilder::handleSuccessor(const CFGBlock *Succ) {1038 ++CurrentBlockInfo->UnprocessedSuccessors;1039}1040 1041void SExprBuilder::handleSuccessorBackEdge(const CFGBlock *Succ) {1042 mergePhiNodesBackEdge(Succ);1043 ++BBInfo[Succ->getBlockID()].ProcessedPredecessors;1044}1045 1046void SExprBuilder::exitCFGBlock(const CFGBlock *B) {1047 CurrentArguments.clear();1048 CurrentInstructions.clear();1049 CurrentBlockInfo->ExitMap = std::move(CurrentLVarMap);1050 CurrentBB = nullptr;1051 CurrentBlockInfo = nullptr;1052}1053 1054void SExprBuilder::exitCFG(const CFGBlock *Last) {1055 for (auto *Ph : IncompleteArgs) {1056 if (Ph->status() == til::Phi::PH_Incomplete)1057 simplifyIncompleteArg(Ph);1058 }1059 1060 CurrentArguments.clear();1061 CurrentInstructions.clear();1062 IncompleteArgs.clear();1063}1064 1065#ifndef NDEBUG1066namespace {1067 1068class TILPrinter :1069 public til::PrettyPrinter<TILPrinter, llvm::raw_ostream> {};1070 1071} // namespace1072 1073namespace clang {1074namespace threadSafety {1075 1076void printSCFG(CFGWalker &Walker) {1077 llvm::BumpPtrAllocator Bpa;1078 til::MemRegionRef Arena(&Bpa);1079 SExprBuilder SxBuilder(Arena);1080 til::SCFG *Scfg = SxBuilder.buildCFG(Walker);1081 TILPrinter::print(Scfg, llvm::errs());1082}1083 1084} // namespace threadSafety1085} // namespace clang1086#endif // NDEBUG1087