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 795
