1//===- ThreadSafetyCommon.h ------------------------------------*- 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// Parts of thread safety analysis that are not specific to thread safety 11// itself have been factored into classes here, where they can be potentially 12// used by other analyses. Currently these include: 13// 14// * Generalize clang CFG visitors. 15// * Conversion of the clang CFG to SSA form. 16// * Translation of clang Exprs to TIL SExprs 17// 18// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. 19// 20//===----------------------------------------------------------------------===// 21 22#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H 23#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H 24 25#include "clang/Analysis/Analyses/PostOrderCFGView.h" 26#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" 27#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" 28#include "clang/Analysis/AnalysisDeclContext.h" 29#include "clang/Basic/OperatorKinds.h" 30#include <memory> 31#include <ostream> 32#include <sstream> 33#include <vector> 34 35 36namespace clang { 37namespace threadSafety { 38 39 40// Various helper functions on til::SExpr 41namespace sx { 42 43inline bool equals(const til::SExpr *E1, const til::SExpr *E2) { 44 return til::EqualsComparator::compareExprs(E1, E2); 45} 46 47inline bool matches(const til::SExpr *E1, const til::SExpr *E2) { 48 // We treat a top-level wildcard as the "univsersal" lock. 49 // It matches everything for the purpose of checking locks, but not 50 // for unlocking them. 51 if (isa<til::Wildcard>(E1)) 52 return isa<til::Wildcard>(E2); 53 if (isa<til::Wildcard>(E2)) 54 return isa<til::Wildcard>(E1); 55 56 return til::MatchComparator::compareExprs(E1, E2); 57} 58 59inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) { 60 const auto *PE1 = dyn_cast_or_null<til::Project>(E1); 61 if (!PE1) 62 return false; 63 const auto *PE2 = dyn_cast_or_null<til::Project>(E2); 64 if (!PE2) 65 return false; 66 return PE1->clangDecl() == PE2->clangDecl(); 67} 68 69inline std::string toString(const til::SExpr *E) { 70 std::stringstream ss; 71 til::StdPrinter::print(E, ss); 72 return ss.str(); 73} 74 75} // end namespace sx 76 77 78 79// This class defines the interface of a clang CFG Visitor. 80// CFGWalker will invoke the following methods. 81// Note that methods are not virtual; the visitor is templatized. 82class CFGVisitor { 83 // Enter the CFG for Decl D, and perform any initial setup operations. 84 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} 85 86 // Enter a CFGBlock. 87 void enterCFGBlock(const CFGBlock *B) {} 88 89 // Returns true if this visitor implements handlePredecessor 90 bool visitPredecessors() { return true; } 91 92 // Process a predecessor edge. 93 void handlePredecessor(const CFGBlock *Pred) {} 94 95 // Process a successor back edge to a previously visited block. 96 void handlePredecessorBackEdge(const CFGBlock *Pred) {} 97 98 // Called just before processing statements. 99 void enterCFGBlockBody(const CFGBlock *B) {} 100 101 // Process an ordinary statement. 102 void handleStatement(const Stmt *S) {} 103 104 // Process a destructor call 105 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} 106 107 // Called after all statements have been handled. 108 void exitCFGBlockBody(const CFGBlock *B) {} 109 110 // Return true 111 bool visitSuccessors() { return true; } 112 113 // Process a successor edge. 114 void handleSuccessor(const CFGBlock *Succ) {} 115 116 // Process a successor back edge to a previously visited block. 117 void handleSuccessorBackEdge(const CFGBlock *Succ) {} 118 119 // Leave a CFGBlock. 120 void exitCFGBlock(const CFGBlock *B) {} 121 122 // Leave the CFG, and perform any final cleanup operations. 123 void exitCFG(const CFGBlock *Last) {} 124}; 125 126 127// Walks the clang CFG, and invokes methods on a given CFGVisitor. 128class CFGWalker { 129public: 130 CFGWalker() : CFGraph(nullptr), ACtx(nullptr), SortedGraph(nullptr) {} 131 132 // Initialize the CFGWalker. This setup only needs to be done once, even 133 // if there are multiple passes over the CFG. 134 bool init(AnalysisDeclContext &AC) { 135 ACtx = &AC; 136 CFGraph = AC.getCFG(); 137 if (!CFGraph) 138 return false; 139 140 // Ignore anonymous functions. 141 if (!dyn_cast_or_null<NamedDecl>(AC.getDecl())) 142 return false; 143 144 SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 145 if (!SortedGraph) 146 return false; 147 148 return true; 149 } 150 151 // Traverse the CFG, calling methods on V as appropriate. 152 template <class Visitor> 153 void walk(Visitor &V) { 154 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 155 156 V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry()); 157 158 for (const auto *CurrBlock : *SortedGraph) { 159 VisitedBlocks.insert(CurrBlock); 160 161 V.enterCFGBlock(CurrBlock); 162 163 // Process predecessors, handling back edges last 164 if (V.visitPredecessors()) { 165 SmallVector<CFGBlock*, 4> BackEdges; 166 // Process successors 167 for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(), 168 SE = CurrBlock->pred_end(); 169 SI != SE; ++SI) { 170 if (*SI == nullptr) 171 continue; 172 173 if (!VisitedBlocks.alreadySet(*SI)) { 174 BackEdges.push_back(*SI); 175 continue; 176 } 177 V.handlePredecessor(*SI); 178 } 179 180 for (auto *Blk : BackEdges) 181 V.handlePredecessorBackEdge(Blk); 182 } 183 184 V.enterCFGBlockBody(CurrBlock); 185 186 // Process statements 187 for (const auto &BI : *CurrBlock) { 188 switch (BI.getKind()) { 189 case CFGElement::Statement: { 190 V.handleStatement(BI.castAs<CFGStmt>().getStmt()); 191 break; 192 } 193 case CFGElement::AutomaticObjectDtor: { 194 CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); 195 CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( 196 AD.getDestructorDecl(ACtx->getASTContext())); 197 VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); 198 V.handleDestructorCall(VD, DD); 199 break; 200 } 201 default: 202 break; 203 } 204 } 205 206 V.exitCFGBlockBody(CurrBlock); 207 208 // Process successors, handling back edges first. 209 if (V.visitSuccessors()) { 210 SmallVector<CFGBlock*, 8> ForwardEdges; 211 212 // Process successors 213 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 214 SE = CurrBlock->succ_end(); 215 SI != SE; ++SI) { 216 if (*SI == nullptr) 217 continue; 218 219 if (!VisitedBlocks.alreadySet(*SI)) { 220 ForwardEdges.push_back(*SI); 221 continue; 222 } 223 V.handleSuccessorBackEdge(*SI); 224 } 225 226 for (auto *Blk : ForwardEdges) 227 V.handleSuccessor(Blk); 228 } 229 230 V.exitCFGBlock(CurrBlock); 231 } 232 V.exitCFG(&CFGraph->getExit()); 233 } 234 235 const CFG *getGraph() const { return CFGraph; } 236 CFG *getGraph() { return CFGraph; } 237 238 const NamedDecl *getDecl() const { 239 return dyn_cast<NamedDecl>(ACtx->getDecl()); 240 } 241 242 const PostOrderCFGView *getSortedGraph() const { return SortedGraph; } 243 244private: 245 CFG *CFGraph; 246 AnalysisDeclContext *ACtx; 247 PostOrderCFGView *SortedGraph; 248}; 249 250 251 252 253class CapabilityExpr { 254 // TODO: move this back into ThreadSafety.cpp 255 // This is specific to thread safety. It is here because 256 // translateAttrExpr needs it, but that should be moved too. 257 258private: 259 const til::SExpr* CapExpr; ///< The capability expression. 260 bool Negated; ///< True if this is a negative capability 261 262public: 263 CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {} 264 265 const til::SExpr* sexpr() const { return CapExpr; } 266 bool negative() const { return Negated; } 267 268 CapabilityExpr operator!() const { 269 return CapabilityExpr(CapExpr, !Negated); 270 } 271 272 bool equals(const CapabilityExpr &other) const { 273 return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr); 274 } 275 276 bool matches(const CapabilityExpr &other) const { 277 return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr); 278 } 279 280 bool matchesUniv(const CapabilityExpr &CapE) const { 281 return isUniversal() || matches(CapE); 282 } 283 284 bool partiallyMatches(const CapabilityExpr &other) const { 285 return (Negated == other.Negated) && 286 sx::partiallyMatches(CapExpr, other.CapExpr); 287 } 288 289 const ValueDecl* valueDecl() const { 290 if (Negated || CapExpr == nullptr) 291 return nullptr; 292 if (auto *P = dyn_cast<til::Project>(CapExpr)) 293 return P->clangDecl(); 294 if (auto *P = dyn_cast<til::LiteralPtr>(CapExpr)) 295 return P->clangDecl(); 296 return nullptr; 297 } 298 299 std::string toString() const { 300 if (Negated) 301 return "!" + sx::toString(CapExpr); 302 return sx::toString(CapExpr); 303 } 304 305 bool shouldIgnore() const { return CapExpr == nullptr; } 306 307 bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); } 308 309 bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); } 310}; 311 312 313 314// Translate clang::Expr to til::SExpr. 315class SExprBuilder { 316public: 317 /// \brief Encapsulates the lexical context of a function call. The lexical 318 /// context includes the arguments to the call, including the implicit object 319 /// argument. When an attribute containing a mutex expression is attached to 320 /// a method, the expression may refer to formal parameters of the method. 321 /// Actual arguments must be substituted for formal parameters to derive 322 /// the appropriate mutex expression in the lexical context where the function 323 /// is called. PrevCtx holds the context in which the arguments themselves 324 /// should be evaluated; multiple calling contexts can be chained together 325 /// by the lock_returned attribute. 326 struct CallingContext { 327 CallingContext *Prev; // The previous context; or 0 if none. 328 const NamedDecl *AttrDecl; // The decl to which the attr is attached. 329 const Expr *SelfArg; // Implicit object argument -- e.g. 'this' 330 unsigned NumArgs; // Number of funArgs 331 const Expr *const *FunArgs; // Function arguments 332 bool SelfArrow; // is Self referred to with -> or .? 333 334 CallingContext(CallingContext *P, const NamedDecl *D = nullptr) 335 : Prev(P), AttrDecl(D), SelfArg(nullptr), 336 NumArgs(0), FunArgs(nullptr), SelfArrow(false) 337 {} 338 }; 339 340 SExprBuilder(til::MemRegionRef A) 341 : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr), 342 CurrentBlockInfo(nullptr) { 343 // FIXME: we don't always have a self-variable. 344 SelfVar = new (Arena) til::Variable(nullptr); 345 SelfVar->setKind(til::Variable::VK_SFun); 346 } 347 348 // Translate a clang expression in an attribute to a til::SExpr. 349 // Constructs the context from D, DeclExp, and SelfDecl. 350 CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, 351 const Expr *DeclExp, VarDecl *SelfD=nullptr); 352 353 CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); 354 355 // Translate a clang statement or expression to a TIL expression. 356 // Also performs substitution of variables; Ctx provides the context. 357 // Dispatches on the type of S. 358 til::SExpr *translate(const Stmt *S, CallingContext *Ctx); 359 til::SCFG *buildCFG(CFGWalker &Walker); 360 361 til::SExpr *lookupStmt(const Stmt *S); 362 363 til::BasicBlock *lookupBlock(const CFGBlock *B) { 364 return BlockMap[B->getBlockID()]; 365 } 366 367 const til::SCFG *getCFG() const { return Scfg; } 368 til::SCFG *getCFG() { return Scfg; } 369 370private: 371 til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, 372 CallingContext *Ctx) ; 373 til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); 374 til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx); 375 til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx, 376 const Expr *SelfE = nullptr); 377 til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, 378 CallingContext *Ctx); 379 til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, 380 CallingContext *Ctx); 381 til::SExpr *translateUnaryOperator(const UnaryOperator *UO, 382 CallingContext *Ctx); 383 til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op, 384 const BinaryOperator *BO, 385 CallingContext *Ctx, bool Reverse = false); 386 til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op, 387 const BinaryOperator *BO, 388 CallingContext *Ctx, bool Assign = false); 389 til::SExpr *translateBinaryOperator(const BinaryOperator *BO, 390 CallingContext *Ctx); 391 til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx); 392 til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E, 393 CallingContext *Ctx); 394 til::SExpr *translateAbstractConditionalOperator( 395 const AbstractConditionalOperator *C, CallingContext *Ctx); 396 397 til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); 398 399 // Map from statements in the clang CFG to SExprs in the til::SCFG. 400 typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap; 401 402 // Map from clang local variables to indices in a LVarDefinitionMap. 403 typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap; 404 405 // Map from local variable indices to SSA variables (or constants). 406 typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair; 407 typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap; 408 409 struct BlockInfo { 410 LVarDefinitionMap ExitMap; 411 bool HasBackEdges; 412 unsigned UnprocessedSuccessors; // Successors yet to be processed 413 unsigned ProcessedPredecessors; // Predecessors already processed 414 415 BlockInfo() 416 : HasBackEdges(false), UnprocessedSuccessors(0), 417 ProcessedPredecessors(0) {} 418 BlockInfo(BlockInfo &&) = default; 419 BlockInfo &operator=(BlockInfo &&) = default; 420 }; 421 422 // We implement the CFGVisitor API 423 friend class CFGWalker; 424 425 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); 426 void enterCFGBlock(const CFGBlock *B); 427 bool visitPredecessors() { return true; } 428 void handlePredecessor(const CFGBlock *Pred); 429 void handlePredecessorBackEdge(const CFGBlock *Pred); 430 void enterCFGBlockBody(const CFGBlock *B); 431 void handleStatement(const Stmt *S); 432 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD); 433 void exitCFGBlockBody(const CFGBlock *B); 434 bool visitSuccessors() { return true; } 435 void handleSuccessor(const CFGBlock *Succ); 436 void handleSuccessorBackEdge(const CFGBlock *Succ); 437 void exitCFGBlock(const CFGBlock *B); 438 void exitCFG(const CFGBlock *Last); 439 440 void insertStmt(const Stmt *S, til::SExpr *E) { 441 SMap.insert(std::make_pair(S, E)); 442 } 443 til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); 444 445 til::SExpr *addStatement(til::SExpr *E, const Stmt *S, 446 const ValueDecl *VD = nullptr); 447 til::SExpr *lookupVarDecl(const ValueDecl *VD); 448 til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E); 449 til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E); 450 451 void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E); 452 void mergeEntryMap(LVarDefinitionMap Map); 453 void mergeEntryMapBackEdge(); 454 void mergePhiNodesBackEdge(const CFGBlock *Blk); 455 456private: 457 // Set to true when parsing capability expressions, which get translated 458 // inaccurately in order to hack around smart pointers etc. 459 static const bool CapabilityExprMode = true; 460 461 til::MemRegionRef Arena; 462 til::Variable *SelfVar; // Variable to use for 'this'. May be null. 463 464 til::SCFG *Scfg; 465 StatementMap SMap; // Map from Stmt to TIL Variables 466 LVarIndexMap LVarIdxMap; // Indices of clang local vars. 467 std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs. 468 std::vector<BlockInfo> BBInfo; // Extra information per BB. 469 // Indexed by clang BlockID. 470 471 LVarDefinitionMap CurrentLVarMap; 472 std::vector<til::Phi*> CurrentArguments; 473 std::vector<til::SExpr*> CurrentInstructions; 474 std::vector<til::Phi*> IncompleteArgs; 475 til::BasicBlock *CurrentBB; 476 BlockInfo *CurrentBlockInfo; 477}; 478 479 480// Dump an SCFG to llvm::errs(). 481void printSCFG(CFGWalker &Walker); 482 483 484} // end namespace threadSafety 485 486} // end namespace clang 487 488#endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H 489