ThreadSafetyCommon.cpp revision 6bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89
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 37namespace clang { 38namespace threadSafety { 39 40// From ThreadSafetyUtil.h 41std::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 63namespace til { 64 65// Return true if E is a variable that points to an incomplete Phi node. 66static 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 77typedef SExprBuilder::CallingContext CallingContext; 78 79 80til::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 88til::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. 97til::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 165til::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 190til::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 200til::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 208til::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 220til::SExpr *SExprBuilder::translateCXXMemberCallExpr( 221 const CXXMemberCallExpr *ME, CallingContext *Ctx) { 222 return translateCallExpr(cast<CallExpr>(ME), Ctx); 223} 224 225 226til::SExpr *SExprBuilder::translateCXXOperatorCallExpr( 227 const CXXOperatorCallExpr *OCE, CallingContext *Ctx) { 228 return translateCallExpr(cast<CallExpr>(OCE), Ctx); 229} 230 231 232til::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 267til::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 279til::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 306til::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 352til::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 382til::SExpr * 383SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E, 384 CallingContext *Ctx) { 385 til::SExpr *E0 = translate(E->getBase(), Ctx); 386 til::SExpr *E1 = translate(E->getIdx(), Ctx); 387 auto *AA = new (Arena) til::ArrayAdd(E0, E1); 388 return new (Arena) til::ArrayFirst(AA); 389} 390 391 392til::SExpr * 393SExprBuilder::translateConditionalOperator(const ConditionalOperator *C, 394 CallingContext *Ctx) { 395 return new (Arena) til::Undefined(C); 396} 397 398 399til::SExpr *SExprBuilder::translateBinaryConditionalOperator( 400 const BinaryConditionalOperator *C, CallingContext *Ctx) { 401 return new (Arena) til::Undefined(C); 402} 403 404 405til::SExpr * 406SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) { 407 DeclGroupRef DGrp = S->getDeclGroup(); 408 for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { 409 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) { 410 Expr *E = VD->getInit(); 411 til::SExpr* SE = translate(E, Ctx); 412 413 // Add local variables with trivial type to the variable map 414 QualType T = VD->getType(); 415 if (T.isTrivialType(VD->getASTContext())) { 416 return addVarDecl(VD, SE); 417 } 418 else { 419 // TODO: add alloca 420 } 421 } 422 } 423 return nullptr; 424} 425 426 427 428// If (E) is non-trivial, then add it to the current basic block, and 429// update the statement map so that S refers to E. Returns a new variable 430// that refers to E. 431// If E is trivial returns E. 432til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S, 433 const ValueDecl *VD) { 434 if (!E) 435 return nullptr; 436 if (til::ThreadSafetyTIL::isTrivial(E)) 437 return E; 438 439 til::Variable *V = new (Arena) til::Variable(E, VD); 440 CurrentInstructions.push_back(V); 441 if (S) 442 insertStmt(S, V); 443 return V; 444} 445 446 447// Returns the current value of VD, if known, and nullptr otherwise. 448til::SExpr *SExprBuilder::lookupVarDecl(const ValueDecl *VD) { 449 auto It = LVarIdxMap.find(VD); 450 if (It != LVarIdxMap.end()) { 451 assert(CurrentLVarMap[It->second].first == VD); 452 return CurrentLVarMap[It->second].second; 453 } 454 return nullptr; 455} 456 457 458// if E is a til::Variable, update its clangDecl. 459inline void maybeUpdateVD(til::SExpr *E, const ValueDecl *VD) { 460 if (!E) 461 return; 462 if (til::Variable *V = dyn_cast<til::Variable>(E)) { 463 if (!V->clangDecl()) 464 V->setClangDecl(VD); 465 } 466} 467 468// Adds a new variable declaration. 469til::SExpr *SExprBuilder::addVarDecl(const ValueDecl *VD, til::SExpr *E) { 470 maybeUpdateVD(E, VD); 471 LVarIdxMap.insert(std::make_pair(VD, CurrentLVarMap.size())); 472 CurrentLVarMap.makeWritable(); 473 CurrentLVarMap.push_back(std::make_pair(VD, E)); 474 return E; 475} 476 477 478// Updates a current variable declaration. (E.g. by assignment) 479til::SExpr *SExprBuilder::updateVarDecl(const ValueDecl *VD, til::SExpr *E) { 480 maybeUpdateVD(E, VD); 481 auto It = LVarIdxMap.find(VD); 482 if (It == LVarIdxMap.end()) { 483 til::SExpr *Ptr = new (Arena) til::LiteralPtr(VD); 484 til::SExpr *St = new (Arena) til::Store(Ptr, E); 485 return St; 486 } 487 CurrentLVarMap.makeWritable(); 488 CurrentLVarMap.elem(It->second).second = E; 489 return E; 490} 491 492 493// Make a Phi node in the current block for the i^th variable in CurrentVarMap. 494// If E != null, sets Phi[CurrentBlockInfo->ArgIndex] = E. 495// If E == null, this is a backedge and will be set later. 496void SExprBuilder::makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E) { 497 unsigned ArgIndex = CurrentBlockInfo->ProcessedPredecessors; 498 assert(ArgIndex > 0 && ArgIndex < NPreds); 499 500 til::Variable *V = dyn_cast<til::Variable>(CurrentLVarMap[i].second); 501 if (V && V->getBlockID() == CurrentBB->blockID()) { 502 // We already have a Phi node in the current block, 503 // so just add the new variable to the Phi node. 504 til::Phi *Ph = dyn_cast<til::Phi>(V->definition()); 505 assert(Ph && "Expecting Phi node."); 506 if (E) 507 Ph->values()[ArgIndex] = E; 508 return; 509 } 510 511 // Make a new phi node: phi(..., E) 512 // All phi args up to the current index are set to the current value. 513 til::SExpr *CurrE = CurrentLVarMap[i].second; 514 til::Phi *Ph = new (Arena) til::Phi(Arena, NPreds); 515 Ph->values().setValues(NPreds, nullptr); 516 for (unsigned PIdx = 0; PIdx < ArgIndex; ++PIdx) 517 Ph->values()[PIdx] = CurrE; 518 if (E) 519 Ph->values()[ArgIndex] = E; 520 // If E is from a back-edge, or either E or CurrE are incomplete, then 521 // mark this node as incomplete; we may need to remove it later. 522 if (!E || isIncompleteVar(E) || isIncompleteVar(CurrE)) { 523 Ph->setStatus(til::Phi::PH_Incomplete); 524 } 525 526 // Add Phi node to current block, and update CurrentLVarMap[i] 527 auto *Var = new (Arena) til::Variable(Ph, CurrentLVarMap[i].first); 528 CurrentArguments.push_back(Var); 529 if (Ph->status() == til::Phi::PH_Incomplete) 530 IncompleteArgs.push_back(Var); 531 532 CurrentLVarMap.makeWritable(); 533 CurrentLVarMap.elem(i).second = Var; 534} 535 536 537// Merge values from Map into the current variable map. 538// This will construct Phi nodes in the current basic block as necessary. 539void SExprBuilder::mergeEntryMap(LVarDefinitionMap Map) { 540 assert(CurrentBlockInfo && "Not processing a block!"); 541 542 if (!CurrentLVarMap.valid()) { 543 // Steal Map, using copy-on-write. 544 CurrentLVarMap = std::move(Map); 545 return; 546 } 547 if (CurrentLVarMap.sameAs(Map)) 548 return; // Easy merge: maps from different predecessors are unchanged. 549 550 unsigned NPreds = CurrentBB->numPredecessors(); 551 unsigned ESz = CurrentLVarMap.size(); 552 unsigned MSz = Map.size(); 553 unsigned Sz = std::min(ESz, MSz); 554 555 for (unsigned i=0; i<Sz; ++i) { 556 if (CurrentLVarMap[i].first != Map[i].first) { 557 // We've reached the end of variables in common. 558 CurrentLVarMap.makeWritable(); 559 CurrentLVarMap.downsize(i); 560 break; 561 } 562 if (CurrentLVarMap[i].second != Map[i].second) 563 makePhiNodeVar(i, NPreds, Map[i].second); 564 } 565 if (ESz > MSz) { 566 CurrentLVarMap.makeWritable(); 567 CurrentLVarMap.downsize(Map.size()); 568 } 569} 570 571 572// Merge a back edge into the current variable map. 573// This will create phi nodes for all variables in the variable map. 574void SExprBuilder::mergeEntryMapBackEdge() { 575 // We don't have definitions for variables on the backedge, because we 576 // haven't gotten that far in the CFG. Thus, when encountering a back edge, 577 // we conservatively create Phi nodes for all variables. Unnecessary Phi 578 // nodes will be marked as incomplete, and stripped out at the end. 579 // 580 // An Phi node is unnecessary if it only refers to itself and one other 581 // variable, e.g. x = Phi(y, y, x) can be reduced to x = y. 582 583 assert(CurrentBlockInfo && "Not processing a block!"); 584 585 if (CurrentBlockInfo->HasBackEdges) 586 return; 587 CurrentBlockInfo->HasBackEdges = true; 588 589 CurrentLVarMap.makeWritable(); 590 unsigned Sz = CurrentLVarMap.size(); 591 unsigned NPreds = CurrentBB->numPredecessors(); 592 593 for (unsigned i=0; i < Sz; ++i) { 594 makePhiNodeVar(i, NPreds, nullptr); 595 } 596} 597 598 599// Update the phi nodes that were initially created for a back edge 600// once the variable definitions have been computed. 601// I.e., merge the current variable map into the phi nodes for Blk. 602void SExprBuilder::mergePhiNodesBackEdge(const CFGBlock *Blk) { 603 til::BasicBlock *BB = lookupBlock(Blk); 604 unsigned ArgIndex = BBInfo[Blk->getBlockID()].ProcessedPredecessors; 605 assert(ArgIndex > 0 && ArgIndex < BB->numPredecessors()); 606 607 for (til::Variable *V : BB->arguments()) { 608 til::Phi *Ph = dyn_cast_or_null<til::Phi>(V->definition()); 609 assert(Ph && "Expecting Phi Node."); 610 assert(Ph->values()[ArgIndex] == nullptr && "Wrong index for back edge."); 611 assert(V->clangDecl() && "No local variable for Phi node."); 612 613 til::SExpr *E = lookupVarDecl(V->clangDecl()); 614 assert(E && "Couldn't find local variable for Phi node."); 615 616 Ph->values()[ArgIndex] = E; 617 } 618} 619 620void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D, 621 const CFGBlock *First) { 622 // Perform initial setup operations. 623 unsigned NBlocks = Cfg->getNumBlockIDs(); 624 Scfg = new (Arena) til::SCFG(Arena, NBlocks); 625 626 // allocate all basic blocks immediately, to handle forward references. 627 BBInfo.resize(NBlocks); 628 BlockMap.resize(NBlocks, nullptr); 629 // create map from clang blockID to til::BasicBlocks 630 for (auto *B : *Cfg) { 631 auto *BB = new (Arena) til::BasicBlock(Arena, 0, 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 654void SExprBuilder::enterCFGBlock(const CFGBlock *B) { 655 // Intialize TIL basic block and add it to the CFG. 656 CurrentBB = lookupBlock(B); 657 CurrentBB->setNumPredecessors(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 668void SExprBuilder::handlePredecessor(const CFGBlock *Pred) { 669 // Compute CurrentLVarMap on entry from ExitMaps of predecessors 670 671 BlockInfo *PredInfo = &BBInfo[Pred->getBlockID()]; 672 assert(PredInfo->UnprocessedSuccessors > 0); 673 674 if (--PredInfo->UnprocessedSuccessors == 0) 675 mergeEntryMap(std::move(PredInfo->ExitMap)); 676 else 677 mergeEntryMap(PredInfo->ExitMap.clone()); 678 679 ++CurrentBlockInfo->ProcessedPredecessors; 680} 681 682 683void SExprBuilder::handlePredecessorBackEdge(const CFGBlock *Pred) { 684 mergeEntryMapBackEdge(); 685} 686 687 688void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) { 689 // The merge*() methods have created arguments. 690 // Push those arguments onto the basic block. 691 CurrentBB->arguments().reserve( 692 static_cast<unsigned>(CurrentArguments.size()), Arena); 693 for (auto *V : CurrentArguments) 694 CurrentBB->addArgument(V); 695} 696 697 698void SExprBuilder::handleStatement(const Stmt *S) { 699 til::SExpr *E = translate(S, CallCtx.get()); 700 addStatement(E, S); 701} 702 703 704void SExprBuilder::handleDestructorCall(const VarDecl *VD, 705 const CXXDestructorDecl *DD) { 706 til::SExpr *Sf = new (Arena) til::LiteralPtr(VD); 707 til::SExpr *Dr = new (Arena) til::LiteralPtr(DD); 708 til::SExpr *Ap = new (Arena) til::Apply(Dr, Sf); 709 til::SExpr *E = new (Arena) til::Call(Ap); 710 addStatement(E, nullptr); 711} 712 713 714 715void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) { 716 CurrentBB->instructions().reserve( 717 static_cast<unsigned>(CurrentInstructions.size()), Arena); 718 for (auto *V : CurrentInstructions) 719 CurrentBB->addInstruction(V); 720 721 // Create an appropriate terminator 722 unsigned N = B->succ_size(); 723 auto It = B->succ_begin(); 724 if (N == 1) { 725 til::BasicBlock *BB = *It ? lookupBlock(*It) : nullptr; 726 // TODO: set index 727 til::SExpr *Tm = new (Arena) til::Goto(BB, 0); 728 CurrentBB->setTerminator(Tm); 729 } 730 else if (N == 2) { 731 til::SExpr *C = translate(B->getTerminatorCondition(true), CallCtx.get()); 732 til::BasicBlock *BB1 = *It ? lookupBlock(*It) : nullptr; 733 ++It; 734 til::BasicBlock *BB2 = *It ? lookupBlock(*It) : nullptr; 735 // TODO: set conditional, set index 736 til::SExpr *Tm = new (Arena) til::Branch(C, BB1, BB2); 737 CurrentBB->setTerminator(Tm); 738 } 739} 740 741 742void SExprBuilder::handleSuccessor(const CFGBlock *Succ) { 743 ++CurrentBlockInfo->UnprocessedSuccessors; 744} 745 746 747void SExprBuilder::handleSuccessorBackEdge(const CFGBlock *Succ) { 748 mergePhiNodesBackEdge(Succ); 749 ++BBInfo[Succ->getBlockID()].ProcessedPredecessors; 750} 751 752 753void SExprBuilder::exitCFGBlock(const CFGBlock *B) { 754 CurrentArguments.clear(); 755 CurrentInstructions.clear(); 756 CurrentBlockInfo->ExitMap = std::move(CurrentLVarMap); 757 CurrentBB = nullptr; 758 CurrentBlockInfo = nullptr; 759} 760 761 762void SExprBuilder::exitCFG(const CFGBlock *Last) { 763 for (auto *V : IncompleteArgs) { 764 til::Phi *Ph = dyn_cast<til::Phi>(V->definition()); 765 if (Ph && Ph->status() == til::Phi::PH_Incomplete) 766 simplifyIncompleteArg(V, Ph); 767 } 768 769 CurrentArguments.clear(); 770 CurrentInstructions.clear(); 771 IncompleteArgs.clear(); 772} 773 774 775 776class TILPrinter : public til::PrettyPrinter<TILPrinter, llvm::raw_ostream> {}; 777 778 779void printSCFG(CFGWalker &Walker) { 780 llvm::BumpPtrAllocator Bpa; 781 til::MemRegionRef Arena(&Bpa); 782 SExprBuilder builder(Arena); 783 til::SCFG *Cfg = builder.buildCFG(Walker); 784 TILPrinter::print(Cfg, llvm::errs()); 785} 786 787 788 789} // end namespace threadSafety 790 791} // end namespace clang 792