1e5dd7070Spatrick //===- ThreadSafetyCommon.cpp ---------------------------------------------===//
2e5dd7070Spatrick //
3e5dd7070Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4e5dd7070Spatrick // See https://llvm.org/LICENSE.txt for license information.
5e5dd7070Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6e5dd7070Spatrick //
7e5dd7070Spatrick //===----------------------------------------------------------------------===//
8e5dd7070Spatrick //
9e5dd7070Spatrick // Implementation of the interfaces declared in ThreadSafetyCommon.h
10e5dd7070Spatrick //
11e5dd7070Spatrick //===----------------------------------------------------------------------===//
12e5dd7070Spatrick
13e5dd7070Spatrick #include "clang/Analysis/Analyses/ThreadSafetyCommon.h"
14e5dd7070Spatrick #include "clang/AST/Attr.h"
15e5dd7070Spatrick #include "clang/AST/Decl.h"
16e5dd7070Spatrick #include "clang/AST/DeclCXX.h"
17e5dd7070Spatrick #include "clang/AST/DeclGroup.h"
18e5dd7070Spatrick #include "clang/AST/DeclObjC.h"
19e5dd7070Spatrick #include "clang/AST/Expr.h"
20e5dd7070Spatrick #include "clang/AST/ExprCXX.h"
21e5dd7070Spatrick #include "clang/AST/OperationKinds.h"
22e5dd7070Spatrick #include "clang/AST/Stmt.h"
23e5dd7070Spatrick #include "clang/AST/Type.h"
24e5dd7070Spatrick #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
25e5dd7070Spatrick #include "clang/Analysis/CFG.h"
26e5dd7070Spatrick #include "clang/Basic/LLVM.h"
27e5dd7070Spatrick #include "clang/Basic/OperatorKinds.h"
28e5dd7070Spatrick #include "clang/Basic/Specifiers.h"
29a9ac8606Spatrick #include "llvm/ADT/StringExtras.h"
30e5dd7070Spatrick #include "llvm/ADT/StringRef.h"
31e5dd7070Spatrick #include "llvm/Support/Casting.h"
32e5dd7070Spatrick #include <algorithm>
33e5dd7070Spatrick #include <cassert>
34e5dd7070Spatrick #include <string>
35e5dd7070Spatrick #include <utility>
36e5dd7070Spatrick
37e5dd7070Spatrick using namespace clang;
38e5dd7070Spatrick using namespace threadSafety;
39e5dd7070Spatrick
40e5dd7070Spatrick // From ThreadSafetyUtil.h
getSourceLiteralString(const Expr * CE)41e5dd7070Spatrick std::string threadSafety::getSourceLiteralString(const Expr *CE) {
42e5dd7070Spatrick switch (CE->getStmtClass()) {
43e5dd7070Spatrick case Stmt::IntegerLiteralClass:
44a9ac8606Spatrick return toString(cast<IntegerLiteral>(CE)->getValue(), 10, true);
45e5dd7070Spatrick case Stmt::StringLiteralClass: {
46e5dd7070Spatrick std::string ret("\"");
47e5dd7070Spatrick ret += cast<StringLiteral>(CE)->getString();
48e5dd7070Spatrick ret += "\"";
49e5dd7070Spatrick return ret;
50e5dd7070Spatrick }
51e5dd7070Spatrick case Stmt::CharacterLiteralClass:
52e5dd7070Spatrick case Stmt::CXXNullPtrLiteralExprClass:
53e5dd7070Spatrick case Stmt::GNUNullExprClass:
54e5dd7070Spatrick case Stmt::CXXBoolLiteralExprClass:
55e5dd7070Spatrick case Stmt::FloatingLiteralClass:
56e5dd7070Spatrick case Stmt::ImaginaryLiteralClass:
57e5dd7070Spatrick case Stmt::ObjCStringLiteralClass:
58e5dd7070Spatrick default:
59e5dd7070Spatrick return "#lit";
60e5dd7070Spatrick }
61e5dd7070Spatrick }
62e5dd7070Spatrick
63e5dd7070Spatrick // Return true if E is a variable that points to an incomplete Phi node.
isIncompletePhi(const til::SExpr * E)64e5dd7070Spatrick static bool isIncompletePhi(const til::SExpr *E) {
65e5dd7070Spatrick if (const auto *Ph = dyn_cast<til::Phi>(E))
66e5dd7070Spatrick return Ph->status() == til::Phi::PH_Incomplete;
67e5dd7070Spatrick return false;
68e5dd7070Spatrick }
69e5dd7070Spatrick
70e5dd7070Spatrick using CallingContext = SExprBuilder::CallingContext;
71e5dd7070Spatrick
lookupStmt(const Stmt * S)72e5dd7070Spatrick til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) {
73e5dd7070Spatrick auto It = SMap.find(S);
74e5dd7070Spatrick if (It != SMap.end())
75e5dd7070Spatrick return It->second;
76e5dd7070Spatrick return nullptr;
77e5dd7070Spatrick }
78e5dd7070Spatrick
buildCFG(CFGWalker & Walker)79e5dd7070Spatrick til::SCFG *SExprBuilder::buildCFG(CFGWalker &Walker) {
80e5dd7070Spatrick Walker.walk(*this);
81e5dd7070Spatrick return Scfg;
82e5dd7070Spatrick }
83e5dd7070Spatrick
isCalleeArrow(const Expr * E)84e5dd7070Spatrick static bool isCalleeArrow(const Expr *E) {
85e5dd7070Spatrick const auto *ME = dyn_cast<MemberExpr>(E->IgnoreParenCasts());
86e5dd7070Spatrick return ME ? ME->isArrow() : false;
87e5dd7070Spatrick }
88e5dd7070Spatrick
ClassifyDiagnostic(const CapabilityAttr * A)89*12c85518Srobert static StringRef ClassifyDiagnostic(const CapabilityAttr *A) {
90*12c85518Srobert return A->getName();
91*12c85518Srobert }
92*12c85518Srobert
ClassifyDiagnostic(QualType VDT)93*12c85518Srobert static StringRef ClassifyDiagnostic(QualType VDT) {
94*12c85518Srobert // We need to look at the declaration of the type of the value to determine
95*12c85518Srobert // which it is. The type should either be a record or a typedef, or a pointer
96*12c85518Srobert // or reference thereof.
97*12c85518Srobert if (const auto *RT = VDT->getAs<RecordType>()) {
98*12c85518Srobert if (const auto *RD = RT->getDecl())
99*12c85518Srobert if (const auto *CA = RD->getAttr<CapabilityAttr>())
100*12c85518Srobert return ClassifyDiagnostic(CA);
101*12c85518Srobert } else if (const auto *TT = VDT->getAs<TypedefType>()) {
102*12c85518Srobert if (const auto *TD = TT->getDecl())
103*12c85518Srobert if (const auto *CA = TD->getAttr<CapabilityAttr>())
104*12c85518Srobert return ClassifyDiagnostic(CA);
105*12c85518Srobert } else if (VDT->isPointerType() || VDT->isReferenceType())
106*12c85518Srobert return ClassifyDiagnostic(VDT->getPointeeType());
107*12c85518Srobert
108*12c85518Srobert return "mutex";
109*12c85518Srobert }
110*12c85518Srobert
111e5dd7070Spatrick /// Translate a clang expression in an attribute to a til::SExpr.
112e5dd7070Spatrick /// Constructs the context from D, DeclExp, and SelfDecl.
113e5dd7070Spatrick ///
114e5dd7070Spatrick /// \param AttrExp The expression to translate.
115e5dd7070Spatrick /// \param D The declaration to which the attribute is attached.
116e5dd7070Spatrick /// \param DeclExp An expression involving the Decl to which the attribute
117e5dd7070Spatrick /// is attached. E.g. the call to a function.
118*12c85518Srobert /// \param Self S-expression to substitute for a \ref CXXThisExpr.
translateAttrExpr(const Expr * AttrExp,const NamedDecl * D,const Expr * DeclExp,til::SExpr * Self)119e5dd7070Spatrick CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp,
120e5dd7070Spatrick const NamedDecl *D,
121e5dd7070Spatrick const Expr *DeclExp,
122*12c85518Srobert til::SExpr *Self) {
123e5dd7070Spatrick // If we are processing a raw attribute expression, with no substitutions.
124*12c85518Srobert if (!DeclExp && !Self)
125e5dd7070Spatrick return translateAttrExpr(AttrExp, nullptr);
126e5dd7070Spatrick
127e5dd7070Spatrick CallingContext Ctx(nullptr, D);
128e5dd7070Spatrick
129e5dd7070Spatrick // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute
130e5dd7070Spatrick // for formal parameters when we call buildMutexID later.
131*12c85518Srobert if (!DeclExp)
132*12c85518Srobert /* We'll use Self. */;
133*12c85518Srobert else if (const auto *ME = dyn_cast<MemberExpr>(DeclExp)) {
134e5dd7070Spatrick Ctx.SelfArg = ME->getBase();
135e5dd7070Spatrick Ctx.SelfArrow = ME->isArrow();
136e5dd7070Spatrick } else if (const auto *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) {
137e5dd7070Spatrick Ctx.SelfArg = CE->getImplicitObjectArgument();
138e5dd7070Spatrick Ctx.SelfArrow = isCalleeArrow(CE->getCallee());
139e5dd7070Spatrick Ctx.NumArgs = CE->getNumArgs();
140e5dd7070Spatrick Ctx.FunArgs = CE->getArgs();
141e5dd7070Spatrick } else if (const auto *CE = dyn_cast<CallExpr>(DeclExp)) {
142e5dd7070Spatrick Ctx.NumArgs = CE->getNumArgs();
143e5dd7070Spatrick Ctx.FunArgs = CE->getArgs();
144e5dd7070Spatrick } else if (const auto *CE = dyn_cast<CXXConstructExpr>(DeclExp)) {
145e5dd7070Spatrick Ctx.SelfArg = nullptr; // Will be set below
146e5dd7070Spatrick Ctx.NumArgs = CE->getNumArgs();
147e5dd7070Spatrick Ctx.FunArgs = CE->getArgs();
148e5dd7070Spatrick }
149e5dd7070Spatrick
150*12c85518Srobert if (Self) {
151*12c85518Srobert assert(!Ctx.SelfArg && "Ambiguous self argument");
152*12c85518Srobert Ctx.SelfArg = Self;
153e5dd7070Spatrick
154e5dd7070Spatrick // If the attribute has no arguments, then assume the argument is "this".
155e5dd7070Spatrick if (!AttrExp)
156*12c85518Srobert return CapabilityExpr(
157*12c85518Srobert Self, ClassifyDiagnostic(cast<CXXMethodDecl>(D)->getThisObjectType()),
158*12c85518Srobert false);
159e5dd7070Spatrick else // For most attributes.
160e5dd7070Spatrick return translateAttrExpr(AttrExp, &Ctx);
161e5dd7070Spatrick }
162e5dd7070Spatrick
163e5dd7070Spatrick // If the attribute has no arguments, then assume the argument is "this".
164e5dd7070Spatrick if (!AttrExp)
165*12c85518Srobert return translateAttrExpr(cast<const Expr *>(Ctx.SelfArg), nullptr);
166e5dd7070Spatrick else // For most attributes.
167e5dd7070Spatrick return translateAttrExpr(AttrExp, &Ctx);
168e5dd7070Spatrick }
169e5dd7070Spatrick
170e5dd7070Spatrick /// Translate a clang expression in an attribute to a til::SExpr.
171e5dd7070Spatrick // This assumes a CallingContext has already been created.
translateAttrExpr(const Expr * AttrExp,CallingContext * Ctx)172e5dd7070Spatrick CapabilityExpr SExprBuilder::translateAttrExpr(const Expr *AttrExp,
173e5dd7070Spatrick CallingContext *Ctx) {
174e5dd7070Spatrick if (!AttrExp)
175*12c85518Srobert return CapabilityExpr();
176e5dd7070Spatrick
177e5dd7070Spatrick if (const auto* SLit = dyn_cast<StringLiteral>(AttrExp)) {
178e5dd7070Spatrick if (SLit->getString() == StringRef("*"))
179e5dd7070Spatrick // The "*" expr is a universal lock, which essentially turns off
180e5dd7070Spatrick // checks until it is removed from the lockset.
181*12c85518Srobert return CapabilityExpr(new (Arena) til::Wildcard(), StringRef("wildcard"),
182*12c85518Srobert false);
183e5dd7070Spatrick else
184e5dd7070Spatrick // Ignore other string literals for now.
185*12c85518Srobert return CapabilityExpr();
186e5dd7070Spatrick }
187e5dd7070Spatrick
188e5dd7070Spatrick bool Neg = false;
189e5dd7070Spatrick if (const auto *OE = dyn_cast<CXXOperatorCallExpr>(AttrExp)) {
190e5dd7070Spatrick if (OE->getOperator() == OO_Exclaim) {
191e5dd7070Spatrick Neg = true;
192e5dd7070Spatrick AttrExp = OE->getArg(0);
193e5dd7070Spatrick }
194e5dd7070Spatrick }
195e5dd7070Spatrick else if (const auto *UO = dyn_cast<UnaryOperator>(AttrExp)) {
196e5dd7070Spatrick if (UO->getOpcode() == UO_LNot) {
197e5dd7070Spatrick Neg = true;
198e5dd7070Spatrick AttrExp = UO->getSubExpr();
199e5dd7070Spatrick }
200e5dd7070Spatrick }
201e5dd7070Spatrick
202e5dd7070Spatrick til::SExpr *E = translate(AttrExp, Ctx);
203e5dd7070Spatrick
204e5dd7070Spatrick // Trap mutex expressions like nullptr, or 0.
205e5dd7070Spatrick // Any literal value is nonsense.
206e5dd7070Spatrick if (!E || isa<til::Literal>(E))
207*12c85518Srobert return CapabilityExpr();
208*12c85518Srobert
209*12c85518Srobert StringRef Kind = ClassifyDiagnostic(AttrExp->getType());
210e5dd7070Spatrick
211e5dd7070Spatrick // Hack to deal with smart pointers -- strip off top-level pointer casts.
212a9ac8606Spatrick if (const auto *CE = dyn_cast<til::Cast>(E)) {
213e5dd7070Spatrick if (CE->castOpcode() == til::CAST_objToPtr)
214*12c85518Srobert return CapabilityExpr(CE->expr(), Kind, Neg);
215e5dd7070Spatrick }
216*12c85518Srobert return CapabilityExpr(E, Kind, Neg);
217*12c85518Srobert }
218*12c85518Srobert
createVariable(const VarDecl * VD)219*12c85518Srobert til::LiteralPtr *SExprBuilder::createVariable(const VarDecl *VD) {
220*12c85518Srobert return new (Arena) til::LiteralPtr(VD);
221*12c85518Srobert }
222*12c85518Srobert
223*12c85518Srobert std::pair<til::LiteralPtr *, StringRef>
createThisPlaceholder(const Expr * Exp)224*12c85518Srobert SExprBuilder::createThisPlaceholder(const Expr *Exp) {
225*12c85518Srobert return {new (Arena) til::LiteralPtr(nullptr),
226*12c85518Srobert ClassifyDiagnostic(Exp->getType())};
227e5dd7070Spatrick }
228e5dd7070Spatrick
229e5dd7070Spatrick // Translate a clang statement or expression to a TIL expression.
230e5dd7070Spatrick // Also performs substitution of variables; Ctx provides the context.
231e5dd7070Spatrick // Dispatches on the type of S.
translate(const Stmt * S,CallingContext * Ctx)232e5dd7070Spatrick til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) {
233e5dd7070Spatrick if (!S)
234e5dd7070Spatrick return nullptr;
235e5dd7070Spatrick
236e5dd7070Spatrick // Check if S has already been translated and cached.
237e5dd7070Spatrick // This handles the lookup of SSA names for DeclRefExprs here.
238e5dd7070Spatrick if (til::SExpr *E = lookupStmt(S))
239e5dd7070Spatrick return E;
240e5dd7070Spatrick
241e5dd7070Spatrick switch (S->getStmtClass()) {
242e5dd7070Spatrick case Stmt::DeclRefExprClass:
243e5dd7070Spatrick return translateDeclRefExpr(cast<DeclRefExpr>(S), Ctx);
244e5dd7070Spatrick case Stmt::CXXThisExprClass:
245e5dd7070Spatrick return translateCXXThisExpr(cast<CXXThisExpr>(S), Ctx);
246e5dd7070Spatrick case Stmt::MemberExprClass:
247e5dd7070Spatrick return translateMemberExpr(cast<MemberExpr>(S), Ctx);
248e5dd7070Spatrick case Stmt::ObjCIvarRefExprClass:
249e5dd7070Spatrick return translateObjCIVarRefExpr(cast<ObjCIvarRefExpr>(S), Ctx);
250e5dd7070Spatrick case Stmt::CallExprClass:
251e5dd7070Spatrick return translateCallExpr(cast<CallExpr>(S), Ctx);
252e5dd7070Spatrick case Stmt::CXXMemberCallExprClass:
253e5dd7070Spatrick return translateCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), Ctx);
254e5dd7070Spatrick case Stmt::CXXOperatorCallExprClass:
255e5dd7070Spatrick return translateCXXOperatorCallExpr(cast<CXXOperatorCallExpr>(S), Ctx);
256e5dd7070Spatrick case Stmt::UnaryOperatorClass:
257e5dd7070Spatrick return translateUnaryOperator(cast<UnaryOperator>(S), Ctx);
258e5dd7070Spatrick case Stmt::BinaryOperatorClass:
259e5dd7070Spatrick case Stmt::CompoundAssignOperatorClass:
260e5dd7070Spatrick return translateBinaryOperator(cast<BinaryOperator>(S), Ctx);
261e5dd7070Spatrick
262e5dd7070Spatrick case Stmt::ArraySubscriptExprClass:
263e5dd7070Spatrick return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx);
264e5dd7070Spatrick case Stmt::ConditionalOperatorClass:
265e5dd7070Spatrick return translateAbstractConditionalOperator(
266e5dd7070Spatrick cast<ConditionalOperator>(S), Ctx);
267e5dd7070Spatrick case Stmt::BinaryConditionalOperatorClass:
268e5dd7070Spatrick return translateAbstractConditionalOperator(
269e5dd7070Spatrick cast<BinaryConditionalOperator>(S), Ctx);
270e5dd7070Spatrick
271e5dd7070Spatrick // We treat these as no-ops
272e5dd7070Spatrick case Stmt::ConstantExprClass:
273e5dd7070Spatrick return translate(cast<ConstantExpr>(S)->getSubExpr(), Ctx);
274e5dd7070Spatrick case Stmt::ParenExprClass:
275e5dd7070Spatrick return translate(cast<ParenExpr>(S)->getSubExpr(), Ctx);
276e5dd7070Spatrick case Stmt::ExprWithCleanupsClass:
277e5dd7070Spatrick return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx);
278e5dd7070Spatrick case Stmt::CXXBindTemporaryExprClass:
279e5dd7070Spatrick return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx);
280e5dd7070Spatrick case Stmt::MaterializeTemporaryExprClass:
281e5dd7070Spatrick return translate(cast<MaterializeTemporaryExpr>(S)->getSubExpr(), Ctx);
282e5dd7070Spatrick
283e5dd7070Spatrick // Collect all literals
284e5dd7070Spatrick case Stmt::CharacterLiteralClass:
285e5dd7070Spatrick case Stmt::CXXNullPtrLiteralExprClass:
286e5dd7070Spatrick case Stmt::GNUNullExprClass:
287e5dd7070Spatrick case Stmt::CXXBoolLiteralExprClass:
288e5dd7070Spatrick case Stmt::FloatingLiteralClass:
289e5dd7070Spatrick case Stmt::ImaginaryLiteralClass:
290e5dd7070Spatrick case Stmt::IntegerLiteralClass:
291e5dd7070Spatrick case Stmt::StringLiteralClass:
292e5dd7070Spatrick case Stmt::ObjCStringLiteralClass:
293e5dd7070Spatrick return new (Arena) til::Literal(cast<Expr>(S));
294e5dd7070Spatrick
295e5dd7070Spatrick case Stmt::DeclStmtClass:
296e5dd7070Spatrick return translateDeclStmt(cast<DeclStmt>(S), Ctx);
297e5dd7070Spatrick default:
298e5dd7070Spatrick break;
299e5dd7070Spatrick }
300e5dd7070Spatrick if (const auto *CE = dyn_cast<CastExpr>(S))
301e5dd7070Spatrick return translateCastExpr(CE, Ctx);
302e5dd7070Spatrick
303e5dd7070Spatrick return new (Arena) til::Undefined(S);
304e5dd7070Spatrick }
305e5dd7070Spatrick
translateDeclRefExpr(const DeclRefExpr * DRE,CallingContext * Ctx)306e5dd7070Spatrick til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE,
307e5dd7070Spatrick CallingContext *Ctx) {
308e5dd7070Spatrick const auto *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl());
309e5dd7070Spatrick
310e5dd7070Spatrick // Function parameters require substitution and/or renaming.
311a9ac8606Spatrick if (const auto *PV = dyn_cast<ParmVarDecl>(VD)) {
312e5dd7070Spatrick unsigned I = PV->getFunctionScopeIndex();
313e5dd7070Spatrick const DeclContext *D = PV->getDeclContext();
314e5dd7070Spatrick if (Ctx && Ctx->FunArgs) {
315e5dd7070Spatrick const Decl *Canonical = Ctx->AttrDecl->getCanonicalDecl();
316e5dd7070Spatrick if (isa<FunctionDecl>(D)
317e5dd7070Spatrick ? (cast<FunctionDecl>(D)->getCanonicalDecl() == Canonical)
318e5dd7070Spatrick : (cast<ObjCMethodDecl>(D)->getCanonicalDecl() == Canonical)) {
319e5dd7070Spatrick // Substitute call arguments for references to function parameters
320e5dd7070Spatrick assert(I < Ctx->NumArgs);
321e5dd7070Spatrick return translate(Ctx->FunArgs[I], Ctx->Prev);
322e5dd7070Spatrick }
323e5dd7070Spatrick }
324e5dd7070Spatrick // Map the param back to the param of the original function declaration
325e5dd7070Spatrick // for consistent comparisons.
326e5dd7070Spatrick VD = isa<FunctionDecl>(D)
327e5dd7070Spatrick ? cast<FunctionDecl>(D)->getCanonicalDecl()->getParamDecl(I)
328e5dd7070Spatrick : cast<ObjCMethodDecl>(D)->getCanonicalDecl()->getParamDecl(I);
329e5dd7070Spatrick }
330e5dd7070Spatrick
331e5dd7070Spatrick // For non-local variables, treat it as a reference to a named object.
332e5dd7070Spatrick return new (Arena) til::LiteralPtr(VD);
333e5dd7070Spatrick }
334e5dd7070Spatrick
translateCXXThisExpr(const CXXThisExpr * TE,CallingContext * Ctx)335e5dd7070Spatrick til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE,
336e5dd7070Spatrick CallingContext *Ctx) {
337e5dd7070Spatrick // Substitute for 'this'
338*12c85518Srobert if (Ctx && Ctx->SelfArg) {
339*12c85518Srobert if (const auto *SelfArg = dyn_cast<const Expr *>(Ctx->SelfArg))
340*12c85518Srobert return translate(SelfArg, Ctx->Prev);
341*12c85518Srobert else
342*12c85518Srobert return cast<til::SExpr *>(Ctx->SelfArg);
343*12c85518Srobert }
344e5dd7070Spatrick assert(SelfVar && "We have no variable for 'this'!");
345e5dd7070Spatrick return SelfVar;
346e5dd7070Spatrick }
347e5dd7070Spatrick
getValueDeclFromSExpr(const til::SExpr * E)348e5dd7070Spatrick static const ValueDecl *getValueDeclFromSExpr(const til::SExpr *E) {
349e5dd7070Spatrick if (const auto *V = dyn_cast<til::Variable>(E))
350e5dd7070Spatrick return V->clangDecl();
351e5dd7070Spatrick if (const auto *Ph = dyn_cast<til::Phi>(E))
352e5dd7070Spatrick return Ph->clangDecl();
353e5dd7070Spatrick if (const auto *P = dyn_cast<til::Project>(E))
354e5dd7070Spatrick return P->clangDecl();
355e5dd7070Spatrick if (const auto *L = dyn_cast<til::LiteralPtr>(E))
356e5dd7070Spatrick return L->clangDecl();
357e5dd7070Spatrick return nullptr;
358e5dd7070Spatrick }
359e5dd7070Spatrick
hasAnyPointerType(const til::SExpr * E)360e5dd7070Spatrick static bool hasAnyPointerType(const til::SExpr *E) {
361e5dd7070Spatrick auto *VD = getValueDeclFromSExpr(E);
362e5dd7070Spatrick if (VD && VD->getType()->isAnyPointerType())
363e5dd7070Spatrick return true;
364e5dd7070Spatrick if (const auto *C = dyn_cast<til::Cast>(E))
365e5dd7070Spatrick return C->castOpcode() == til::CAST_objToPtr;
366e5dd7070Spatrick
367e5dd7070Spatrick return false;
368e5dd7070Spatrick }
369e5dd7070Spatrick
370e5dd7070Spatrick // Grab the very first declaration of virtual method D
getFirstVirtualDecl(const CXXMethodDecl * D)371e5dd7070Spatrick static const CXXMethodDecl *getFirstVirtualDecl(const CXXMethodDecl *D) {
372e5dd7070Spatrick while (true) {
373e5dd7070Spatrick D = D->getCanonicalDecl();
374e5dd7070Spatrick auto OverriddenMethods = D->overridden_methods();
375e5dd7070Spatrick if (OverriddenMethods.begin() == OverriddenMethods.end())
376e5dd7070Spatrick return D; // Method does not override anything
377e5dd7070Spatrick // FIXME: this does not work with multiple inheritance.
378e5dd7070Spatrick D = *OverriddenMethods.begin();
379e5dd7070Spatrick }
380e5dd7070Spatrick return nullptr;
381e5dd7070Spatrick }
382e5dd7070Spatrick
translateMemberExpr(const MemberExpr * ME,CallingContext * Ctx)383e5dd7070Spatrick til::SExpr *SExprBuilder::translateMemberExpr(const MemberExpr *ME,
384e5dd7070Spatrick CallingContext *Ctx) {
385e5dd7070Spatrick til::SExpr *BE = translate(ME->getBase(), Ctx);
386e5dd7070Spatrick til::SExpr *E = new (Arena) til::SApply(BE);
387e5dd7070Spatrick
388e5dd7070Spatrick const auto *D = cast<ValueDecl>(ME->getMemberDecl()->getCanonicalDecl());
389e5dd7070Spatrick if (const auto *VD = dyn_cast<CXXMethodDecl>(D))
390e5dd7070Spatrick D = getFirstVirtualDecl(VD);
391e5dd7070Spatrick
392e5dd7070Spatrick til::Project *P = new (Arena) til::Project(E, D);
393e5dd7070Spatrick if (hasAnyPointerType(BE))
394e5dd7070Spatrick P->setArrow(true);
395e5dd7070Spatrick return P;
396e5dd7070Spatrick }
397e5dd7070Spatrick
translateObjCIVarRefExpr(const ObjCIvarRefExpr * IVRE,CallingContext * Ctx)398e5dd7070Spatrick til::SExpr *SExprBuilder::translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE,
399e5dd7070Spatrick CallingContext *Ctx) {
400e5dd7070Spatrick til::SExpr *BE = translate(IVRE->getBase(), Ctx);
401e5dd7070Spatrick til::SExpr *E = new (Arena) til::SApply(BE);
402e5dd7070Spatrick
403e5dd7070Spatrick const auto *D = cast<ObjCIvarDecl>(IVRE->getDecl()->getCanonicalDecl());
404e5dd7070Spatrick
405e5dd7070Spatrick til::Project *P = new (Arena) til::Project(E, D);
406e5dd7070Spatrick if (hasAnyPointerType(BE))
407e5dd7070Spatrick P->setArrow(true);
408e5dd7070Spatrick return P;
409e5dd7070Spatrick }
410e5dd7070Spatrick
translateCallExpr(const CallExpr * CE,CallingContext * Ctx,const Expr * SelfE)411e5dd7070Spatrick til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE,
412e5dd7070Spatrick CallingContext *Ctx,
413e5dd7070Spatrick const Expr *SelfE) {
414e5dd7070Spatrick if (CapabilityExprMode) {
415e5dd7070Spatrick // Handle LOCK_RETURNED
416e5dd7070Spatrick if (const FunctionDecl *FD = CE->getDirectCallee()) {
417e5dd7070Spatrick FD = FD->getMostRecentDecl();
418e5dd7070Spatrick if (LockReturnedAttr *At = FD->getAttr<LockReturnedAttr>()) {
419e5dd7070Spatrick CallingContext LRCallCtx(Ctx);
420e5dd7070Spatrick LRCallCtx.AttrDecl = CE->getDirectCallee();
421e5dd7070Spatrick LRCallCtx.SelfArg = SelfE;
422e5dd7070Spatrick LRCallCtx.NumArgs = CE->getNumArgs();
423e5dd7070Spatrick LRCallCtx.FunArgs = CE->getArgs();
424e5dd7070Spatrick return const_cast<til::SExpr *>(
425e5dd7070Spatrick translateAttrExpr(At->getArg(), &LRCallCtx).sexpr());
426e5dd7070Spatrick }
427e5dd7070Spatrick }
428e5dd7070Spatrick }
429e5dd7070Spatrick
430e5dd7070Spatrick til::SExpr *E = translate(CE->getCallee(), Ctx);
431e5dd7070Spatrick for (const auto *Arg : CE->arguments()) {
432e5dd7070Spatrick til::SExpr *A = translate(Arg, Ctx);
433e5dd7070Spatrick E = new (Arena) til::Apply(E, A);
434e5dd7070Spatrick }
435e5dd7070Spatrick return new (Arena) til::Call(E, CE);
436e5dd7070Spatrick }
437e5dd7070Spatrick
translateCXXMemberCallExpr(const CXXMemberCallExpr * ME,CallingContext * Ctx)438e5dd7070Spatrick til::SExpr *SExprBuilder::translateCXXMemberCallExpr(
439e5dd7070Spatrick const CXXMemberCallExpr *ME, CallingContext *Ctx) {
440e5dd7070Spatrick if (CapabilityExprMode) {
441e5dd7070Spatrick // Ignore calls to get() on smart pointers.
442e5dd7070Spatrick if (ME->getMethodDecl()->getNameAsString() == "get" &&
443e5dd7070Spatrick ME->getNumArgs() == 0) {
444e5dd7070Spatrick auto *E = translate(ME->getImplicitObjectArgument(), Ctx);
445e5dd7070Spatrick return new (Arena) til::Cast(til::CAST_objToPtr, E);
446e5dd7070Spatrick // return E;
447e5dd7070Spatrick }
448e5dd7070Spatrick }
449e5dd7070Spatrick return translateCallExpr(cast<CallExpr>(ME), Ctx,
450e5dd7070Spatrick ME->getImplicitObjectArgument());
451e5dd7070Spatrick }
452e5dd7070Spatrick
translateCXXOperatorCallExpr(const CXXOperatorCallExpr * OCE,CallingContext * Ctx)453e5dd7070Spatrick til::SExpr *SExprBuilder::translateCXXOperatorCallExpr(
454e5dd7070Spatrick const CXXOperatorCallExpr *OCE, CallingContext *Ctx) {
455e5dd7070Spatrick if (CapabilityExprMode) {
456e5dd7070Spatrick // Ignore operator * and operator -> on smart pointers.
457e5dd7070Spatrick OverloadedOperatorKind k = OCE->getOperator();
458e5dd7070Spatrick if (k == OO_Star || k == OO_Arrow) {
459e5dd7070Spatrick auto *E = translate(OCE->getArg(0), Ctx);
460e5dd7070Spatrick return new (Arena) til::Cast(til::CAST_objToPtr, E);
461e5dd7070Spatrick // return E;
462e5dd7070Spatrick }
463e5dd7070Spatrick }
464e5dd7070Spatrick return translateCallExpr(cast<CallExpr>(OCE), Ctx);
465e5dd7070Spatrick }
466e5dd7070Spatrick
translateUnaryOperator(const UnaryOperator * UO,CallingContext * Ctx)467e5dd7070Spatrick til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO,
468e5dd7070Spatrick CallingContext *Ctx) {
469e5dd7070Spatrick switch (UO->getOpcode()) {
470e5dd7070Spatrick case UO_PostInc:
471e5dd7070Spatrick case UO_PostDec:
472e5dd7070Spatrick case UO_PreInc:
473e5dd7070Spatrick case UO_PreDec:
474e5dd7070Spatrick return new (Arena) til::Undefined(UO);
475e5dd7070Spatrick
476e5dd7070Spatrick case UO_AddrOf:
477e5dd7070Spatrick if (CapabilityExprMode) {
478e5dd7070Spatrick // interpret &Graph::mu_ as an existential.
479e5dd7070Spatrick if (const auto *DRE = dyn_cast<DeclRefExpr>(UO->getSubExpr())) {
480e5dd7070Spatrick if (DRE->getDecl()->isCXXInstanceMember()) {
481e5dd7070Spatrick // This is a pointer-to-member expression, e.g. &MyClass::mu_.
482e5dd7070Spatrick // We interpret this syntax specially, as a wildcard.
483e5dd7070Spatrick auto *W = new (Arena) til::Wildcard();
484e5dd7070Spatrick return new (Arena) til::Project(W, DRE->getDecl());
485e5dd7070Spatrick }
486e5dd7070Spatrick }
487e5dd7070Spatrick }
488e5dd7070Spatrick // otherwise, & is a no-op
489e5dd7070Spatrick return translate(UO->getSubExpr(), Ctx);
490e5dd7070Spatrick
491e5dd7070Spatrick // We treat these as no-ops
492e5dd7070Spatrick case UO_Deref:
493e5dd7070Spatrick case UO_Plus:
494e5dd7070Spatrick return translate(UO->getSubExpr(), Ctx);
495e5dd7070Spatrick
496e5dd7070Spatrick case UO_Minus:
497e5dd7070Spatrick return new (Arena)
498e5dd7070Spatrick til::UnaryOp(til::UOP_Minus, translate(UO->getSubExpr(), Ctx));
499e5dd7070Spatrick case UO_Not:
500e5dd7070Spatrick return new (Arena)
501e5dd7070Spatrick til::UnaryOp(til::UOP_BitNot, translate(UO->getSubExpr(), Ctx));
502e5dd7070Spatrick case UO_LNot:
503e5dd7070Spatrick return new (Arena)
504e5dd7070Spatrick til::UnaryOp(til::UOP_LogicNot, translate(UO->getSubExpr(), Ctx));
505e5dd7070Spatrick
506e5dd7070Spatrick // Currently unsupported
507e5dd7070Spatrick case UO_Real:
508e5dd7070Spatrick case UO_Imag:
509e5dd7070Spatrick case UO_Extension:
510e5dd7070Spatrick case UO_Coawait:
511e5dd7070Spatrick return new (Arena) til::Undefined(UO);
512e5dd7070Spatrick }
513e5dd7070Spatrick return new (Arena) til::Undefined(UO);
514e5dd7070Spatrick }
515e5dd7070Spatrick
translateBinOp(til::TIL_BinaryOpcode Op,const BinaryOperator * BO,CallingContext * Ctx,bool Reverse)516e5dd7070Spatrick til::SExpr *SExprBuilder::translateBinOp(til::TIL_BinaryOpcode Op,
517e5dd7070Spatrick const BinaryOperator *BO,
518e5dd7070Spatrick CallingContext *Ctx, bool Reverse) {
519e5dd7070Spatrick til::SExpr *E0 = translate(BO->getLHS(), Ctx);
520e5dd7070Spatrick til::SExpr *E1 = translate(BO->getRHS(), Ctx);
521e5dd7070Spatrick if (Reverse)
522e5dd7070Spatrick return new (Arena) til::BinaryOp(Op, E1, E0);
523e5dd7070Spatrick else
524e5dd7070Spatrick return new (Arena) til::BinaryOp(Op, E0, E1);
525e5dd7070Spatrick }
526e5dd7070Spatrick
translateBinAssign(til::TIL_BinaryOpcode Op,const BinaryOperator * BO,CallingContext * Ctx,bool Assign)527e5dd7070Spatrick til::SExpr *SExprBuilder::translateBinAssign(til::TIL_BinaryOpcode Op,
528e5dd7070Spatrick const BinaryOperator *BO,
529e5dd7070Spatrick CallingContext *Ctx,
530e5dd7070Spatrick bool Assign) {
531e5dd7070Spatrick const Expr *LHS = BO->getLHS();
532e5dd7070Spatrick const Expr *RHS = BO->getRHS();
533e5dd7070Spatrick til::SExpr *E0 = translate(LHS, Ctx);
534e5dd7070Spatrick til::SExpr *E1 = translate(RHS, Ctx);
535e5dd7070Spatrick
536e5dd7070Spatrick const ValueDecl *VD = nullptr;
537e5dd7070Spatrick til::SExpr *CV = nullptr;
538e5dd7070Spatrick if (const auto *DRE = dyn_cast<DeclRefExpr>(LHS)) {
539e5dd7070Spatrick VD = DRE->getDecl();
540e5dd7070Spatrick CV = lookupVarDecl(VD);
541e5dd7070Spatrick }
542e5dd7070Spatrick
543e5dd7070Spatrick if (!Assign) {
544e5dd7070Spatrick til::SExpr *Arg = CV ? CV : new (Arena) til::Load(E0);
545e5dd7070Spatrick E1 = new (Arena) til::BinaryOp(Op, Arg, E1);
546e5dd7070Spatrick E1 = addStatement(E1, nullptr, VD);
547e5dd7070Spatrick }
548e5dd7070Spatrick if (VD && CV)
549e5dd7070Spatrick return updateVarDecl(VD, E1);
550e5dd7070Spatrick return new (Arena) til::Store(E0, E1);
551e5dd7070Spatrick }
552e5dd7070Spatrick
translateBinaryOperator(const BinaryOperator * BO,CallingContext * Ctx)553e5dd7070Spatrick til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO,
554e5dd7070Spatrick CallingContext *Ctx) {
555e5dd7070Spatrick switch (BO->getOpcode()) {
556e5dd7070Spatrick case BO_PtrMemD:
557e5dd7070Spatrick case BO_PtrMemI:
558e5dd7070Spatrick return new (Arena) til::Undefined(BO);
559e5dd7070Spatrick
560e5dd7070Spatrick case BO_Mul: return translateBinOp(til::BOP_Mul, BO, Ctx);
561e5dd7070Spatrick case BO_Div: return translateBinOp(til::BOP_Div, BO, Ctx);
562e5dd7070Spatrick case BO_Rem: return translateBinOp(til::BOP_Rem, BO, Ctx);
563e5dd7070Spatrick case BO_Add: return translateBinOp(til::BOP_Add, BO, Ctx);
564e5dd7070Spatrick case BO_Sub: return translateBinOp(til::BOP_Sub, BO, Ctx);
565e5dd7070Spatrick case BO_Shl: return translateBinOp(til::BOP_Shl, BO, Ctx);
566e5dd7070Spatrick case BO_Shr: return translateBinOp(til::BOP_Shr, BO, Ctx);
567e5dd7070Spatrick case BO_LT: return translateBinOp(til::BOP_Lt, BO, Ctx);
568e5dd7070Spatrick case BO_GT: return translateBinOp(til::BOP_Lt, BO, Ctx, true);
569e5dd7070Spatrick case BO_LE: return translateBinOp(til::BOP_Leq, BO, Ctx);
570e5dd7070Spatrick case BO_GE: return translateBinOp(til::BOP_Leq, BO, Ctx, true);
571e5dd7070Spatrick case BO_EQ: return translateBinOp(til::BOP_Eq, BO, Ctx);
572e5dd7070Spatrick case BO_NE: return translateBinOp(til::BOP_Neq, BO, Ctx);
573e5dd7070Spatrick case BO_Cmp: return translateBinOp(til::BOP_Cmp, BO, Ctx);
574e5dd7070Spatrick case BO_And: return translateBinOp(til::BOP_BitAnd, BO, Ctx);
575e5dd7070Spatrick case BO_Xor: return translateBinOp(til::BOP_BitXor, BO, Ctx);
576e5dd7070Spatrick case BO_Or: return translateBinOp(til::BOP_BitOr, BO, Ctx);
577e5dd7070Spatrick case BO_LAnd: return translateBinOp(til::BOP_LogicAnd, BO, Ctx);
578e5dd7070Spatrick case BO_LOr: return translateBinOp(til::BOP_LogicOr, BO, Ctx);
579e5dd7070Spatrick
580e5dd7070Spatrick case BO_Assign: return translateBinAssign(til::BOP_Eq, BO, Ctx, true);
581e5dd7070Spatrick case BO_MulAssign: return translateBinAssign(til::BOP_Mul, BO, Ctx);
582e5dd7070Spatrick case BO_DivAssign: return translateBinAssign(til::BOP_Div, BO, Ctx);
583e5dd7070Spatrick case BO_RemAssign: return translateBinAssign(til::BOP_Rem, BO, Ctx);
584e5dd7070Spatrick case BO_AddAssign: return translateBinAssign(til::BOP_Add, BO, Ctx);
585e5dd7070Spatrick case BO_SubAssign: return translateBinAssign(til::BOP_Sub, BO, Ctx);
586e5dd7070Spatrick case BO_ShlAssign: return translateBinAssign(til::BOP_Shl, BO, Ctx);
587e5dd7070Spatrick case BO_ShrAssign: return translateBinAssign(til::BOP_Shr, BO, Ctx);
588e5dd7070Spatrick case BO_AndAssign: return translateBinAssign(til::BOP_BitAnd, BO, Ctx);
589e5dd7070Spatrick case BO_XorAssign: return translateBinAssign(til::BOP_BitXor, BO, Ctx);
590e5dd7070Spatrick case BO_OrAssign: return translateBinAssign(til::BOP_BitOr, BO, Ctx);
591e5dd7070Spatrick
592e5dd7070Spatrick case BO_Comma:
593e5dd7070Spatrick // The clang CFG should have already processed both sides.
594e5dd7070Spatrick return translate(BO->getRHS(), Ctx);
595e5dd7070Spatrick }
596e5dd7070Spatrick return new (Arena) til::Undefined(BO);
597e5dd7070Spatrick }
598e5dd7070Spatrick
translateCastExpr(const CastExpr * CE,CallingContext * Ctx)599e5dd7070Spatrick til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE,
600e5dd7070Spatrick CallingContext *Ctx) {
601e5dd7070Spatrick CastKind K = CE->getCastKind();
602e5dd7070Spatrick switch (K) {
603e5dd7070Spatrick case CK_LValueToRValue: {
604e5dd7070Spatrick if (const auto *DRE = dyn_cast<DeclRefExpr>(CE->getSubExpr())) {
605e5dd7070Spatrick til::SExpr *E0 = lookupVarDecl(DRE->getDecl());
606e5dd7070Spatrick if (E0)
607e5dd7070Spatrick return E0;
608e5dd7070Spatrick }
609e5dd7070Spatrick til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
610e5dd7070Spatrick return E0;
611e5dd7070Spatrick // FIXME!! -- get Load working properly
612e5dd7070Spatrick // return new (Arena) til::Load(E0);
613e5dd7070Spatrick }
614e5dd7070Spatrick case CK_NoOp:
615e5dd7070Spatrick case CK_DerivedToBase:
616e5dd7070Spatrick case CK_UncheckedDerivedToBase:
617e5dd7070Spatrick case CK_ArrayToPointerDecay:
618e5dd7070Spatrick case CK_FunctionToPointerDecay: {
619e5dd7070Spatrick til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
620e5dd7070Spatrick return E0;
621e5dd7070Spatrick }
622e5dd7070Spatrick default: {
623e5dd7070Spatrick // FIXME: handle different kinds of casts.
624e5dd7070Spatrick til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
625e5dd7070Spatrick if (CapabilityExprMode)
626e5dd7070Spatrick return E0;
627e5dd7070Spatrick return new (Arena) til::Cast(til::CAST_none, E0);
628e5dd7070Spatrick }
629e5dd7070Spatrick }
630e5dd7070Spatrick }
631e5dd7070Spatrick
632e5dd7070Spatrick til::SExpr *
translateArraySubscriptExpr(const ArraySubscriptExpr * E,CallingContext * Ctx)633e5dd7070Spatrick SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E,
634e5dd7070Spatrick CallingContext *Ctx) {
635e5dd7070Spatrick til::SExpr *E0 = translate(E->getBase(), Ctx);
636e5dd7070Spatrick til::SExpr *E1 = translate(E->getIdx(), Ctx);
637e5dd7070Spatrick return new (Arena) til::ArrayIndex(E0, E1);
638e5dd7070Spatrick }
639e5dd7070Spatrick
640e5dd7070Spatrick til::SExpr *
translateAbstractConditionalOperator(const AbstractConditionalOperator * CO,CallingContext * Ctx)641e5dd7070Spatrick SExprBuilder::translateAbstractConditionalOperator(
642e5dd7070Spatrick const AbstractConditionalOperator *CO, CallingContext *Ctx) {
643e5dd7070Spatrick auto *C = translate(CO->getCond(), Ctx);
644e5dd7070Spatrick auto *T = translate(CO->getTrueExpr(), Ctx);
645e5dd7070Spatrick auto *E = translate(CO->getFalseExpr(), Ctx);
646e5dd7070Spatrick return new (Arena) til::IfThenElse(C, T, E);
647e5dd7070Spatrick }
648e5dd7070Spatrick
649e5dd7070Spatrick til::SExpr *
translateDeclStmt(const DeclStmt * S,CallingContext * Ctx)650e5dd7070Spatrick SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) {
651e5dd7070Spatrick DeclGroupRef DGrp = S->getDeclGroup();
652*12c85518Srobert for (auto *I : DGrp) {
653e5dd7070Spatrick if (auto *VD = dyn_cast_or_null<VarDecl>(I)) {
654e5dd7070Spatrick Expr *E = VD->getInit();
655e5dd7070Spatrick til::SExpr* SE = translate(E, Ctx);
656e5dd7070Spatrick
657e5dd7070Spatrick // Add local variables with trivial type to the variable map
658e5dd7070Spatrick QualType T = VD->getType();
659e5dd7070Spatrick if (T.isTrivialType(VD->getASTContext()))
660e5dd7070Spatrick return addVarDecl(VD, SE);
661e5dd7070Spatrick else {
662e5dd7070Spatrick // TODO: add alloca
663e5dd7070Spatrick }
664e5dd7070Spatrick }
665e5dd7070Spatrick }
666e5dd7070Spatrick return nullptr;
667e5dd7070Spatrick }
668e5dd7070Spatrick
669e5dd7070Spatrick // If (E) is non-trivial, then add it to the current basic block, and
670e5dd7070Spatrick // update the statement map so that S refers to E. Returns a new variable
671e5dd7070Spatrick // that refers to E.
672e5dd7070Spatrick // If E is trivial returns E.
addStatement(til::SExpr * E,const Stmt * S,const ValueDecl * VD)673e5dd7070Spatrick til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S,
674e5dd7070Spatrick const ValueDecl *VD) {
675e5dd7070Spatrick if (!E || !CurrentBB || E->block() || til::ThreadSafetyTIL::isTrivial(E))
676e5dd7070Spatrick return E;
677e5dd7070Spatrick if (VD)
678e5dd7070Spatrick E = new (Arena) til::Variable(E, VD);
679e5dd7070Spatrick CurrentInstructions.push_back(E);
680e5dd7070Spatrick if (S)
681e5dd7070Spatrick insertStmt(S, E);
682e5dd7070Spatrick return E;
683e5dd7070Spatrick }
684e5dd7070Spatrick
685e5dd7070Spatrick // Returns the current value of VD, if known, and nullptr otherwise.
lookupVarDecl(const ValueDecl * VD)686e5dd7070Spatrick til::SExpr *SExprBuilder::lookupVarDecl(const ValueDecl *VD) {
687e5dd7070Spatrick auto It = LVarIdxMap.find(VD);
688e5dd7070Spatrick if (It != LVarIdxMap.end()) {
689e5dd7070Spatrick assert(CurrentLVarMap[It->second].first == VD);
690e5dd7070Spatrick return CurrentLVarMap[It->second].second;
691e5dd7070Spatrick }
692e5dd7070Spatrick return nullptr;
693e5dd7070Spatrick }
694e5dd7070Spatrick
695e5dd7070Spatrick // if E is a til::Variable, update its clangDecl.
maybeUpdateVD(til::SExpr * E,const ValueDecl * VD)696e5dd7070Spatrick static void maybeUpdateVD(til::SExpr *E, const ValueDecl *VD) {
697e5dd7070Spatrick if (!E)
698e5dd7070Spatrick return;
699e5dd7070Spatrick if (auto *V = dyn_cast<til::Variable>(E)) {
700e5dd7070Spatrick if (!V->clangDecl())
701e5dd7070Spatrick V->setClangDecl(VD);
702e5dd7070Spatrick }
703e5dd7070Spatrick }
704e5dd7070Spatrick
705e5dd7070Spatrick // Adds a new variable declaration.
addVarDecl(const ValueDecl * VD,til::SExpr * E)706e5dd7070Spatrick til::SExpr *SExprBuilder::addVarDecl(const ValueDecl *VD, til::SExpr *E) {
707e5dd7070Spatrick maybeUpdateVD(E, VD);
708e5dd7070Spatrick LVarIdxMap.insert(std::make_pair(VD, CurrentLVarMap.size()));
709e5dd7070Spatrick CurrentLVarMap.makeWritable();
710e5dd7070Spatrick CurrentLVarMap.push_back(std::make_pair(VD, E));
711e5dd7070Spatrick return E;
712e5dd7070Spatrick }
713e5dd7070Spatrick
714e5dd7070Spatrick // Updates a current variable declaration. (E.g. by assignment)
updateVarDecl(const ValueDecl * VD,til::SExpr * E)715e5dd7070Spatrick til::SExpr *SExprBuilder::updateVarDecl(const ValueDecl *VD, til::SExpr *E) {
716e5dd7070Spatrick maybeUpdateVD(E, VD);
717e5dd7070Spatrick auto It = LVarIdxMap.find(VD);
718e5dd7070Spatrick if (It == LVarIdxMap.end()) {
719e5dd7070Spatrick til::SExpr *Ptr = new (Arena) til::LiteralPtr(VD);
720e5dd7070Spatrick til::SExpr *St = new (Arena) til::Store(Ptr, E);
721e5dd7070Spatrick return St;
722e5dd7070Spatrick }
723e5dd7070Spatrick CurrentLVarMap.makeWritable();
724e5dd7070Spatrick CurrentLVarMap.elem(It->second).second = E;
725e5dd7070Spatrick return E;
726e5dd7070Spatrick }
727e5dd7070Spatrick
728e5dd7070Spatrick // Make a Phi node in the current block for the i^th variable in CurrentVarMap.
729e5dd7070Spatrick // If E != null, sets Phi[CurrentBlockInfo->ArgIndex] = E.
730e5dd7070Spatrick // If E == null, this is a backedge and will be set later.
makePhiNodeVar(unsigned i,unsigned NPreds,til::SExpr * E)731e5dd7070Spatrick void SExprBuilder::makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E) {
732e5dd7070Spatrick unsigned ArgIndex = CurrentBlockInfo->ProcessedPredecessors;
733e5dd7070Spatrick assert(ArgIndex > 0 && ArgIndex < NPreds);
734e5dd7070Spatrick
735e5dd7070Spatrick til::SExpr *CurrE = CurrentLVarMap[i].second;
736e5dd7070Spatrick if (CurrE->block() == CurrentBB) {
737e5dd7070Spatrick // We already have a Phi node in the current block,
738e5dd7070Spatrick // so just add the new variable to the Phi node.
739e5dd7070Spatrick auto *Ph = dyn_cast<til::Phi>(CurrE);
740e5dd7070Spatrick assert(Ph && "Expecting Phi node.");
741e5dd7070Spatrick if (E)
742e5dd7070Spatrick Ph->values()[ArgIndex] = E;
743e5dd7070Spatrick return;
744e5dd7070Spatrick }
745e5dd7070Spatrick
746e5dd7070Spatrick // Make a new phi node: phi(..., E)
747e5dd7070Spatrick // All phi args up to the current index are set to the current value.
748e5dd7070Spatrick til::Phi *Ph = new (Arena) til::Phi(Arena, NPreds);
749e5dd7070Spatrick Ph->values().setValues(NPreds, nullptr);
750e5dd7070Spatrick for (unsigned PIdx = 0; PIdx < ArgIndex; ++PIdx)
751e5dd7070Spatrick Ph->values()[PIdx] = CurrE;
752e5dd7070Spatrick if (E)
753e5dd7070Spatrick Ph->values()[ArgIndex] = E;
754e5dd7070Spatrick Ph->setClangDecl(CurrentLVarMap[i].first);
755e5dd7070Spatrick // If E is from a back-edge, or either E or CurrE are incomplete, then
756e5dd7070Spatrick // mark this node as incomplete; we may need to remove it later.
757e5dd7070Spatrick if (!E || isIncompletePhi(E) || isIncompletePhi(CurrE))
758e5dd7070Spatrick Ph->setStatus(til::Phi::PH_Incomplete);
759e5dd7070Spatrick
760e5dd7070Spatrick // Add Phi node to current block, and update CurrentLVarMap[i]
761e5dd7070Spatrick CurrentArguments.push_back(Ph);
762e5dd7070Spatrick if (Ph->status() == til::Phi::PH_Incomplete)
763e5dd7070Spatrick IncompleteArgs.push_back(Ph);
764e5dd7070Spatrick
765e5dd7070Spatrick CurrentLVarMap.makeWritable();
766e5dd7070Spatrick CurrentLVarMap.elem(i).second = Ph;
767e5dd7070Spatrick }
768e5dd7070Spatrick
769e5dd7070Spatrick // Merge values from Map into the current variable map.
770e5dd7070Spatrick // This will construct Phi nodes in the current basic block as necessary.
mergeEntryMap(LVarDefinitionMap Map)771e5dd7070Spatrick void SExprBuilder::mergeEntryMap(LVarDefinitionMap Map) {
772e5dd7070Spatrick assert(CurrentBlockInfo && "Not processing a block!");
773e5dd7070Spatrick
774e5dd7070Spatrick if (!CurrentLVarMap.valid()) {
775e5dd7070Spatrick // Steal Map, using copy-on-write.
776e5dd7070Spatrick CurrentLVarMap = std::move(Map);
777e5dd7070Spatrick return;
778e5dd7070Spatrick }
779e5dd7070Spatrick if (CurrentLVarMap.sameAs(Map))
780e5dd7070Spatrick return; // Easy merge: maps from different predecessors are unchanged.
781e5dd7070Spatrick
782e5dd7070Spatrick unsigned NPreds = CurrentBB->numPredecessors();
783e5dd7070Spatrick unsigned ESz = CurrentLVarMap.size();
784e5dd7070Spatrick unsigned MSz = Map.size();
785e5dd7070Spatrick unsigned Sz = std::min(ESz, MSz);
786e5dd7070Spatrick
787e5dd7070Spatrick for (unsigned i = 0; i < Sz; ++i) {
788e5dd7070Spatrick if (CurrentLVarMap[i].first != Map[i].first) {
789e5dd7070Spatrick // We've reached the end of variables in common.
790e5dd7070Spatrick CurrentLVarMap.makeWritable();
791e5dd7070Spatrick CurrentLVarMap.downsize(i);
792e5dd7070Spatrick break;
793e5dd7070Spatrick }
794e5dd7070Spatrick if (CurrentLVarMap[i].second != Map[i].second)
795e5dd7070Spatrick makePhiNodeVar(i, NPreds, Map[i].second);
796e5dd7070Spatrick }
797e5dd7070Spatrick if (ESz > MSz) {
798e5dd7070Spatrick CurrentLVarMap.makeWritable();
799e5dd7070Spatrick CurrentLVarMap.downsize(Map.size());
800e5dd7070Spatrick }
801e5dd7070Spatrick }
802e5dd7070Spatrick
803e5dd7070Spatrick // Merge a back edge into the current variable map.
804e5dd7070Spatrick // This will create phi nodes for all variables in the variable map.
mergeEntryMapBackEdge()805e5dd7070Spatrick void SExprBuilder::mergeEntryMapBackEdge() {
806e5dd7070Spatrick // We don't have definitions for variables on the backedge, because we
807e5dd7070Spatrick // haven't gotten that far in the CFG. Thus, when encountering a back edge,
808e5dd7070Spatrick // we conservatively create Phi nodes for all variables. Unnecessary Phi
809e5dd7070Spatrick // nodes will be marked as incomplete, and stripped out at the end.
810e5dd7070Spatrick //
811e5dd7070Spatrick // An Phi node is unnecessary if it only refers to itself and one other
812e5dd7070Spatrick // variable, e.g. x = Phi(y, y, x) can be reduced to x = y.
813e5dd7070Spatrick
814e5dd7070Spatrick assert(CurrentBlockInfo && "Not processing a block!");
815e5dd7070Spatrick
816e5dd7070Spatrick if (CurrentBlockInfo->HasBackEdges)
817e5dd7070Spatrick return;
818e5dd7070Spatrick CurrentBlockInfo->HasBackEdges = true;
819e5dd7070Spatrick
820e5dd7070Spatrick CurrentLVarMap.makeWritable();
821e5dd7070Spatrick unsigned Sz = CurrentLVarMap.size();
822e5dd7070Spatrick unsigned NPreds = CurrentBB->numPredecessors();
823e5dd7070Spatrick
824e5dd7070Spatrick for (unsigned i = 0; i < Sz; ++i)
825e5dd7070Spatrick makePhiNodeVar(i, NPreds, nullptr);
826e5dd7070Spatrick }
827e5dd7070Spatrick
828e5dd7070Spatrick // Update the phi nodes that were initially created for a back edge
829e5dd7070Spatrick // once the variable definitions have been computed.
830e5dd7070Spatrick // I.e., merge the current variable map into the phi nodes for Blk.
mergePhiNodesBackEdge(const CFGBlock * Blk)831e5dd7070Spatrick void SExprBuilder::mergePhiNodesBackEdge(const CFGBlock *Blk) {
832e5dd7070Spatrick til::BasicBlock *BB = lookupBlock(Blk);
833e5dd7070Spatrick unsigned ArgIndex = BBInfo[Blk->getBlockID()].ProcessedPredecessors;
834e5dd7070Spatrick assert(ArgIndex > 0 && ArgIndex < BB->numPredecessors());
835e5dd7070Spatrick
836e5dd7070Spatrick for (til::SExpr *PE : BB->arguments()) {
837e5dd7070Spatrick auto *Ph = dyn_cast_or_null<til::Phi>(PE);
838e5dd7070Spatrick assert(Ph && "Expecting Phi Node.");
839e5dd7070Spatrick assert(Ph->values()[ArgIndex] == nullptr && "Wrong index for back edge.");
840e5dd7070Spatrick
841e5dd7070Spatrick til::SExpr *E = lookupVarDecl(Ph->clangDecl());
842e5dd7070Spatrick assert(E && "Couldn't find local variable for Phi node.");
843e5dd7070Spatrick Ph->values()[ArgIndex] = E;
844e5dd7070Spatrick }
845e5dd7070Spatrick }
846e5dd7070Spatrick
enterCFG(CFG * Cfg,const NamedDecl * D,const CFGBlock * First)847e5dd7070Spatrick void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D,
848e5dd7070Spatrick const CFGBlock *First) {
849e5dd7070Spatrick // Perform initial setup operations.
850e5dd7070Spatrick unsigned NBlocks = Cfg->getNumBlockIDs();
851e5dd7070Spatrick Scfg = new (Arena) til::SCFG(Arena, NBlocks);
852e5dd7070Spatrick
853e5dd7070Spatrick // allocate all basic blocks immediately, to handle forward references.
854e5dd7070Spatrick BBInfo.resize(NBlocks);
855e5dd7070Spatrick BlockMap.resize(NBlocks, nullptr);
856e5dd7070Spatrick // create map from clang blockID to til::BasicBlocks
857e5dd7070Spatrick for (auto *B : *Cfg) {
858e5dd7070Spatrick auto *BB = new (Arena) til::BasicBlock(Arena);
859e5dd7070Spatrick BB->reserveInstructions(B->size());
860e5dd7070Spatrick BlockMap[B->getBlockID()] = BB;
861e5dd7070Spatrick }
862e5dd7070Spatrick
863e5dd7070Spatrick CurrentBB = lookupBlock(&Cfg->getEntry());
864e5dd7070Spatrick auto Parms = isa<ObjCMethodDecl>(D) ? cast<ObjCMethodDecl>(D)->parameters()
865e5dd7070Spatrick : cast<FunctionDecl>(D)->parameters();
866e5dd7070Spatrick for (auto *Pm : Parms) {
867e5dd7070Spatrick QualType T = Pm->getType();
868e5dd7070Spatrick if (!T.isTrivialType(Pm->getASTContext()))
869e5dd7070Spatrick continue;
870e5dd7070Spatrick
871e5dd7070Spatrick // Add parameters to local variable map.
872e5dd7070Spatrick // FIXME: right now we emulate params with loads; that should be fixed.
873e5dd7070Spatrick til::SExpr *Lp = new (Arena) til::LiteralPtr(Pm);
874e5dd7070Spatrick til::SExpr *Ld = new (Arena) til::Load(Lp);
875e5dd7070Spatrick til::SExpr *V = addStatement(Ld, nullptr, Pm);
876e5dd7070Spatrick addVarDecl(Pm, V);
877e5dd7070Spatrick }
878e5dd7070Spatrick }
879e5dd7070Spatrick
enterCFGBlock(const CFGBlock * B)880e5dd7070Spatrick void SExprBuilder::enterCFGBlock(const CFGBlock *B) {
881e5dd7070Spatrick // Initialize TIL basic block and add it to the CFG.
882e5dd7070Spatrick CurrentBB = lookupBlock(B);
883e5dd7070Spatrick CurrentBB->reservePredecessors(B->pred_size());
884e5dd7070Spatrick Scfg->add(CurrentBB);
885e5dd7070Spatrick
886e5dd7070Spatrick CurrentBlockInfo = &BBInfo[B->getBlockID()];
887e5dd7070Spatrick
888e5dd7070Spatrick // CurrentLVarMap is moved to ExitMap on block exit.
889e5dd7070Spatrick // FIXME: the entry block will hold function parameters.
890e5dd7070Spatrick // assert(!CurrentLVarMap.valid() && "CurrentLVarMap already initialized.");
891e5dd7070Spatrick }
892e5dd7070Spatrick
handlePredecessor(const CFGBlock * Pred)893e5dd7070Spatrick void SExprBuilder::handlePredecessor(const CFGBlock *Pred) {
894e5dd7070Spatrick // Compute CurrentLVarMap on entry from ExitMaps of predecessors
895e5dd7070Spatrick
896e5dd7070Spatrick CurrentBB->addPredecessor(BlockMap[Pred->getBlockID()]);
897e5dd7070Spatrick BlockInfo *PredInfo = &BBInfo[Pred->getBlockID()];
898e5dd7070Spatrick assert(PredInfo->UnprocessedSuccessors > 0);
899e5dd7070Spatrick
900e5dd7070Spatrick if (--PredInfo->UnprocessedSuccessors == 0)
901e5dd7070Spatrick mergeEntryMap(std::move(PredInfo->ExitMap));
902e5dd7070Spatrick else
903e5dd7070Spatrick mergeEntryMap(PredInfo->ExitMap.clone());
904e5dd7070Spatrick
905e5dd7070Spatrick ++CurrentBlockInfo->ProcessedPredecessors;
906e5dd7070Spatrick }
907e5dd7070Spatrick
handlePredecessorBackEdge(const CFGBlock * Pred)908e5dd7070Spatrick void SExprBuilder::handlePredecessorBackEdge(const CFGBlock *Pred) {
909e5dd7070Spatrick mergeEntryMapBackEdge();
910e5dd7070Spatrick }
911e5dd7070Spatrick
enterCFGBlockBody(const CFGBlock * B)912e5dd7070Spatrick void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) {
913e5dd7070Spatrick // The merge*() methods have created arguments.
914e5dd7070Spatrick // Push those arguments onto the basic block.
915e5dd7070Spatrick CurrentBB->arguments().reserve(
916e5dd7070Spatrick static_cast<unsigned>(CurrentArguments.size()), Arena);
917e5dd7070Spatrick for (auto *A : CurrentArguments)
918e5dd7070Spatrick CurrentBB->addArgument(A);
919e5dd7070Spatrick }
920e5dd7070Spatrick
handleStatement(const Stmt * S)921e5dd7070Spatrick void SExprBuilder::handleStatement(const Stmt *S) {
922e5dd7070Spatrick til::SExpr *E = translate(S, nullptr);
923e5dd7070Spatrick addStatement(E, S);
924e5dd7070Spatrick }
925e5dd7070Spatrick
handleDestructorCall(const VarDecl * VD,const CXXDestructorDecl * DD)926e5dd7070Spatrick void SExprBuilder::handleDestructorCall(const VarDecl *VD,
927e5dd7070Spatrick const CXXDestructorDecl *DD) {
928e5dd7070Spatrick til::SExpr *Sf = new (Arena) til::LiteralPtr(VD);
929e5dd7070Spatrick til::SExpr *Dr = new (Arena) til::LiteralPtr(DD);
930e5dd7070Spatrick til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf);
931e5dd7070Spatrick til::SExpr *E = new (Arena) til::Call(Ap);
932e5dd7070Spatrick addStatement(E, nullptr);
933e5dd7070Spatrick }
934e5dd7070Spatrick
exitCFGBlockBody(const CFGBlock * B)935e5dd7070Spatrick void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) {
936e5dd7070Spatrick CurrentBB->instructions().reserve(
937e5dd7070Spatrick static_cast<unsigned>(CurrentInstructions.size()), Arena);
938e5dd7070Spatrick for (auto *V : CurrentInstructions)
939e5dd7070Spatrick CurrentBB->addInstruction(V);
940e5dd7070Spatrick
941e5dd7070Spatrick // Create an appropriate terminator
942e5dd7070Spatrick unsigned N = B->succ_size();
943e5dd7070Spatrick auto It = B->succ_begin();
944e5dd7070Spatrick if (N == 1) {
945e5dd7070Spatrick til::BasicBlock *BB = *It ? lookupBlock(*It) : nullptr;
946e5dd7070Spatrick // TODO: set index
947e5dd7070Spatrick unsigned Idx = BB ? BB->findPredecessorIndex(CurrentBB) : 0;
948e5dd7070Spatrick auto *Tm = new (Arena) til::Goto(BB, Idx);
949e5dd7070Spatrick CurrentBB->setTerminator(Tm);
950e5dd7070Spatrick }
951e5dd7070Spatrick else if (N == 2) {
952e5dd7070Spatrick til::SExpr *C = translate(B->getTerminatorCondition(true), nullptr);
953e5dd7070Spatrick til::BasicBlock *BB1 = *It ? lookupBlock(*It) : nullptr;
954e5dd7070Spatrick ++It;
955e5dd7070Spatrick til::BasicBlock *BB2 = *It ? lookupBlock(*It) : nullptr;
956e5dd7070Spatrick // FIXME: make sure these aren't critical edges.
957e5dd7070Spatrick auto *Tm = new (Arena) til::Branch(C, BB1, BB2);
958e5dd7070Spatrick CurrentBB->setTerminator(Tm);
959e5dd7070Spatrick }
960e5dd7070Spatrick }
961e5dd7070Spatrick
handleSuccessor(const CFGBlock * Succ)962e5dd7070Spatrick void SExprBuilder::handleSuccessor(const CFGBlock *Succ) {
963e5dd7070Spatrick ++CurrentBlockInfo->UnprocessedSuccessors;
964e5dd7070Spatrick }
965e5dd7070Spatrick
handleSuccessorBackEdge(const CFGBlock * Succ)966e5dd7070Spatrick void SExprBuilder::handleSuccessorBackEdge(const CFGBlock *Succ) {
967e5dd7070Spatrick mergePhiNodesBackEdge(Succ);
968e5dd7070Spatrick ++BBInfo[Succ->getBlockID()].ProcessedPredecessors;
969e5dd7070Spatrick }
970e5dd7070Spatrick
exitCFGBlock(const CFGBlock * B)971e5dd7070Spatrick void SExprBuilder::exitCFGBlock(const CFGBlock *B) {
972e5dd7070Spatrick CurrentArguments.clear();
973e5dd7070Spatrick CurrentInstructions.clear();
974e5dd7070Spatrick CurrentBlockInfo->ExitMap = std::move(CurrentLVarMap);
975e5dd7070Spatrick CurrentBB = nullptr;
976e5dd7070Spatrick CurrentBlockInfo = nullptr;
977e5dd7070Spatrick }
978e5dd7070Spatrick
exitCFG(const CFGBlock * Last)979e5dd7070Spatrick void SExprBuilder::exitCFG(const CFGBlock *Last) {
980e5dd7070Spatrick for (auto *Ph : IncompleteArgs) {
981e5dd7070Spatrick if (Ph->status() == til::Phi::PH_Incomplete)
982e5dd7070Spatrick simplifyIncompleteArg(Ph);
983e5dd7070Spatrick }
984e5dd7070Spatrick
985e5dd7070Spatrick CurrentArguments.clear();
986e5dd7070Spatrick CurrentInstructions.clear();
987e5dd7070Spatrick IncompleteArgs.clear();
988e5dd7070Spatrick }
989e5dd7070Spatrick
990e5dd7070Spatrick /*
991e5dd7070Spatrick namespace {
992e5dd7070Spatrick
993e5dd7070Spatrick class TILPrinter :
994e5dd7070Spatrick public til::PrettyPrinter<TILPrinter, llvm::raw_ostream> {};
995e5dd7070Spatrick
996e5dd7070Spatrick } // namespace
997e5dd7070Spatrick
998e5dd7070Spatrick namespace clang {
999e5dd7070Spatrick namespace threadSafety {
1000e5dd7070Spatrick
1001e5dd7070Spatrick void printSCFG(CFGWalker &Walker) {
1002e5dd7070Spatrick llvm::BumpPtrAllocator Bpa;
1003e5dd7070Spatrick til::MemRegionRef Arena(&Bpa);
1004e5dd7070Spatrick SExprBuilder SxBuilder(Arena);
1005e5dd7070Spatrick til::SCFG *Scfg = SxBuilder.buildCFG(Walker);
1006e5dd7070Spatrick TILPrinter::print(Scfg, llvm::errs());
1007e5dd7070Spatrick }
1008e5dd7070Spatrick
1009e5dd7070Spatrick } // namespace threadSafety
1010e5dd7070Spatrick } // namespace clang
1011e5dd7070Spatrick */
1012