ThreadSafetyCommon.cpp 32 KB

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