contrib/llvm/tools/clang/lib/Analysis/ThreadSafetyCommon.cpp

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