1b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru//===- ThreadSafetyCommon.h ------------------------------------*- C++ --*-===// 2b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho// The LLVM Compiler Infrastructure 4b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 5b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// This file is distributed under the University of Illinois Open Source 6b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// License. See LICENSE.TXT for details. 7b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 8b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru//===----------------------------------------------------------------------===// 9b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 10b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// Parts of thread safety analysis that are not specific to thread safety 11b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// itself have been factored into classes here, where they can be potentially 12b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// used by other analyses. Currently these include: 13b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 14b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// * Generalize clang CFG visitors. 15b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// * Conversion of the clang CFG to SSA form. 16b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// * Translation of clang Exprs to TIL SExprs 17b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 18b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. 19b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 20b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru//===----------------------------------------------------------------------===// 21b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 22b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#ifndef LLVM_CLANG_THREAD_SAFETY_COMMON_H 2350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho#define LLVM_CLANG_THREAD_SAFETY_COMMON_H 24b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 25b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "clang/Analysis/Analyses/PostOrderCFGView.h" 26b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "clang/Analysis/Analyses/ThreadSafetyTIL.h" 27b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "clang/Analysis/AnalysisContext.h" 28b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "clang/Basic/OperatorKinds.h" 29b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 30b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include <memory> 31b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include <vector> 32b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 33b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 3450294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehonamespace clang { 3550294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehonamespace threadSafety { 3650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 3750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho// This class defines the interface of a clang CFG Visitor. 38b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// CFGWalker will invoke the following methods. 39b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// Note that methods are not virtual; the visitor is templatized. 40b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruclass CFGVisitor { 41b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Enter the CFG for Decl D, and perform any initial setup operations. 42b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} 43b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 44b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Enter a CFGBlock. 45b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void enterCFGBlock(const CFGBlock *B) {} 46b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 47b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Returns true if this visitor implements handlePredecessor 48b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru bool visitPredecessors() { return true; } 49b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 50b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process a predecessor edge. 51b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void handlePredecessor(const CFGBlock *Pred) {} 52b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 53b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process a successor back edge to a previously visited block. 54b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void handlePredecessorBackEdge(const CFGBlock *Pred) {} 55b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 56b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Called just before processing statements. 57b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void enterCFGBlockBody(const CFGBlock *B) {} 58b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 59b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process an ordinary statement. 60b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void handleStatement(const Stmt *S) {} 61b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 62b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process a destructor call 63b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} 64b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 65b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Called after all statements have been handled. 66b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void exitCFGBlockBody(const CFGBlock *B) {} 67b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 68b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Return true 69b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru bool visitSuccessors() { return true; } 70b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 71b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process a successor edge. 72b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void handleSuccessor(const CFGBlock *Succ) {} 73b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 74b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process a successor back edge to a previously visited block. 75b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void handleSuccessorBackEdge(const CFGBlock *Succ) {} 76b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 77b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Leave a CFGBlock. 78b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void exitCFGBlock(const CFGBlock *B) {} 79b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 80b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Leave the CFG, and perform any final cleanup operations. 81b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void exitCFG(const CFGBlock *Last) {} 82b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}; 83b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 84b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 85b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// Walks the clang CFG, and invokes methods on a given CFGVisitor. 86b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruclass CFGWalker { 87b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querupublic: 88b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGWalker() : CFGraph(nullptr), ACtx(nullptr), SortedGraph(nullptr) {} 89b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 90b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Initialize the CFGWalker. This setup only needs to be done once, even 91b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // if there are multiple passes over the CFG. 92b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru bool init(AnalysisDeclContext &AC) { 93b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ACtx = &AC; 94b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGraph = AC.getCFG(); 95b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!CFGraph) 96b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return false; 97b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 98b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Ignore anonymous functions. 99b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!dyn_cast_or_null<NamedDecl>(AC.getDecl())) 100b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return false; 101b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 102b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 103b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!SortedGraph) 104b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return false; 105b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 106b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return true; 107b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 108b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 109b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Traverse the CFG, calling methods on V as appropriate. 110b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru template <class Visitor> 111b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void walk(Visitor &V) { 112b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 113b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 114b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry()); 115b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 116b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (const auto *CurrBlock : *SortedGraph) { 117b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru VisitedBlocks.insert(CurrBlock); 118b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 119b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.enterCFGBlock(CurrBlock); 120b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 121b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process predecessors, handling back edges last 122b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (V.visitPredecessors()) { 123b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SmallVector<CFGBlock*, 4> BackEdges; 124b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process successors 125b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(), 126b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SE = CurrBlock->pred_end(); 127b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SI != SE; ++SI) { 128b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (*SI == nullptr) 129b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru continue; 130b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 131b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!VisitedBlocks.alreadySet(*SI)) { 132b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BackEdges.push_back(*SI); 133b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru continue; 134b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 135b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.handlePredecessor(*SI); 136b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 137b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 138b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (auto *Blk : BackEdges) 139b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.handlePredecessorBackEdge(Blk); 140b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 141b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 142b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.enterCFGBlockBody(CurrBlock); 143b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 144b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process statements 1456d5deb12725f146643d443090dfa11b206df528aJean-Baptiste Queru for (const auto &BI : *CurrBlock) { 146b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru switch (BI.getKind()) { 147b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case CFGElement::Statement: { 148b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.handleStatement(BI.castAs<CFGStmt>().getStmt()); 149b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru break; 150b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 151b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case CFGElement::AutomaticObjectDtor: { 152b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); 153b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( 154b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AD.getDestructorDecl(ACtx->getASTContext())); 155b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); 156b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.handleDestructorCall(VD, DD); 157b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru break; 158b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 159b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru default: 160b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru break; 161b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 162b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 163b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 164b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.exitCFGBlockBody(CurrBlock); 165b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 166b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process successors, handling back edges first. 167b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (V.visitSuccessors()) { 168b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SmallVector<CFGBlock*, 8> ForwardEdges; 169b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 170b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Process successors 171b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 172b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SE = CurrBlock->succ_end(); 173b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SI != SE; ++SI) { 174b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (*SI == nullptr) 175b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru continue; 176b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 177b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!VisitedBlocks.alreadySet(*SI)) { 178b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ForwardEdges.push_back(*SI); 179b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru continue; 180b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 181b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.handleSuccessorBackEdge(*SI); 182b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 183b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 184b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (auto *Blk : ForwardEdges) 185b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.handleSuccessor(Blk); 186b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 187b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 188b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.exitCFGBlock(CurrBlock); 189b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 190b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru V.exitCFG(&CFGraph->getExit()); 191b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 192b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 193b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const CFG *getGraph() const { return CFGraph; } 194b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFG *getGraph() { return CFGraph; } 195b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 196b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const NamedDecl *getDecl() const { 197b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return dyn_cast<NamedDecl>(ACtx->getDecl()); 198b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 199b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 200b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const PostOrderCFGView *getSortedGraph() const { return SortedGraph; } 201b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 202b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruprivate: 203b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFG *CFGraph; 204b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AnalysisDeclContext *ACtx; 205b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru PostOrderCFGView *SortedGraph; 206b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}; 207b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 208b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 209b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// Translate clang::Expr to til::SExpr. 210b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruclass SExprBuilder { 211b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querupublic: 212b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// \brief Encapsulates the lexical context of a function call. The lexical 213b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// context includes the arguments to the call, including the implicit object 214b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// argument. When an attribute containing a mutex expression is attached to 215b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// a method, the expression may refer to formal parameters of the method. 216b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// Actual arguments must be substituted for formal parameters to derive 217b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// the appropriate mutex expression in the lexical context where the function 218b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// is called. PrevCtx holds the context in which the arguments themselves 219b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// should be evaluated; multiple calling contexts can be chained together 220b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// by the lock_returned attribute. 221b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru struct CallingContext { 222b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const NamedDecl *AttrDecl; // The decl to which the attr is attached. 223b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const Expr *SelfArg; // Implicit object argument -- e.g. 'this' 224b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru unsigned NumArgs; // Number of funArgs 225b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const Expr *const *FunArgs; // Function arguments 226b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Prev; // The previous context; or 0 if none. 227b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru bool SelfArrow; // is Self referred to with -> or .? 228b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 22950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CallingContext(const NamedDecl *D = nullptr, const Expr *S = nullptr, 230b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru unsigned N = 0, const Expr *const *A = nullptr, 231b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *P = nullptr) 232b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), Prev(P), 233b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SelfArrow(false) 234b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru {} 235b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru }; 236b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 237b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SExprBuilder(til::MemRegionRef A) 238b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr), 239b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CurrentBlockInfo(nullptr) { 240b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // FIXME: we don't always have a self-variable. 241b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SelfVar = new (Arena) til::Variable(nullptr); 242b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SelfVar->setKind(til::Variable::VK_SFun); 243b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 244b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 245b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Translate a clang statement or expression to a TIL expression. 246b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Also performs substitution of variables; Ctx provides the context. 247b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Dispatches on the type of S. 248b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translate(const Stmt *S, CallingContext *Ctx); 249b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SCFG *buildCFG(CFGWalker &Walker); 250b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 251b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *lookupStmt(const Stmt *S); 252b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 253b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::BasicBlock *lookupBlock(const CFGBlock *B) { 254b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return BlockMap[B->getBlockID()]; 255b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 256b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 257b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const til::SCFG *getCFG() const { return Scfg; } 258b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SCFG *getCFG() { return Scfg; } 259b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 260b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruprivate: 261b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, 262b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx) ; 263b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); 264b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx); 26550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx); 266b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, 267b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx); 268b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, 269b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx); 270b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateUnaryOperator(const UnaryOperator *UO, 271b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx); 272b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op, 273b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const BinaryOperator *BO, 274b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx, bool Reverse = false); 27550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op, 276b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const BinaryOperator *BO, 277b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx, bool Assign = false); 278b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateBinaryOperator(const BinaryOperator *BO, 279b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx); 280b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx); 281b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E, 282b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx); 283b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateConditionalOperator(const ConditionalOperator *C, 284b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CallingContext *Ctx); 285b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateBinaryConditionalOperator( 286b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const BinaryConditionalOperator *C, CallingContext *Ctx); 287b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 288b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); 289b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 290b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Map from statements in the clang CFG to SExprs in the til::SCFG. 291b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap; 292b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 293b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Map from clang local variables to indices in a LVarDefinitionMap. 294b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap; 295b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 296b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Map from local variable indices to SSA variables (or constants). 297b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair; 298b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap; 299b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 300b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru struct BlockInfo { 301b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LVarDefinitionMap ExitMap; 302b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru bool HasBackEdges; 303b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru unsigned UnprocessedSuccessors; // Successors yet to be processed 304b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru unsigned ProcessedPredecessors; // Predecessors already processed 305b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 306b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BlockInfo() 307b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru : HasBackEdges(false), UnprocessedSuccessors(0), 308b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ProcessedPredecessors(0) {} 309b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BlockInfo(BlockInfo &&RHS) 31050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho : ExitMap(std::move(RHS.ExitMap)), 31150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho HasBackEdges(RHS.HasBackEdges), 31250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho UnprocessedSuccessors(RHS.UnprocessedSuccessors), 31350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho ProcessedPredecessors(RHS.ProcessedPredecessors) {} 31450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 31550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho BlockInfo &operator=(BlockInfo &&RHS) { 31650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (this != &RHS) { 31750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho ExitMap = std::move(RHS.ExitMap); 31850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho HasBackEdges = RHS.HasBackEdges; 319b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru UnprocessedSuccessors = RHS.UnprocessedSuccessors; 320b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ProcessedPredecessors = RHS.ProcessedPredecessors; 32150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 32250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return *this; 32350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 32450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 32550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho private: 32650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho BlockInfo(const BlockInfo &) LLVM_DELETED_FUNCTION; 32750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void operator=(const BlockInfo &) LLVM_DELETED_FUNCTION; 32850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho }; 32950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 330b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // We implement the CFGVisitor API 331b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru friend class CFGWalker; 33250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 33350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); 33450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void enterCFGBlock(const CFGBlock *B); 33550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho bool visitPredecessors() { return true; } 33650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void handlePredecessor(const CFGBlock *Pred); 33750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void handlePredecessorBackEdge(const CFGBlock *Pred); 33850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void enterCFGBlockBody(const CFGBlock *B); 33950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void handleStatement(const Stmt *S); 34050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD); 341b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void exitCFGBlockBody(const CFGBlock *B); 342b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru bool visitSuccessors() { return true; } 34350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void handleSuccessor(const CFGBlock *Succ); 34450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void handleSuccessorBackEdge(const CFGBlock *Succ); 34550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void exitCFGBlock(const CFGBlock *B); 34650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void exitCFG(const CFGBlock *Last); 34750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 34850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void insertStmt(const Stmt *S, til::SExpr *E) { 34950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho SMap.insert(std::make_pair(S, E)); 35050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 35150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); 352b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 353b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *addStatement(til::SExpr *E, const Stmt *S, 354b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const ValueDecl *VD = nullptr); 355b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *lookupVarDecl(const ValueDecl *VD); 356b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E); 357b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E); 358b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 359b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E); 360b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void mergeEntryMap(LVarDefinitionMap Map); 361b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void mergeEntryMapBackEdge(); 362b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void mergePhiNodesBackEdge(const CFGBlock *Blk); 363b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 364b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruprivate: 365b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::MemRegionRef Arena; 366b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::Variable *SelfVar; // Variable to use for 'this'. May be null. 367b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru til::SCFG *Scfg; 368b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 369b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru StatementMap SMap; // Map from Stmt to TIL Variables 370b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LVarIndexMap LVarIdxMap; // Indices of clang local vars. 371b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs. 372b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru std::vector<BlockInfo> BBInfo; // Extra information per BB. 373b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Indexed by clang BlockID. 374b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru std::unique_ptr<SExprBuilder::CallingContext> CallCtx; // Root calling context 375b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 376b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LVarDefinitionMap CurrentLVarMap; 377b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru std::vector<til::Variable*> CurrentArguments; 378b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru std::vector<til::Variable*> CurrentInstructions; 379b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru std::vector<til::Variable*> IncompleteArgs; 38050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho til::BasicBlock *CurrentBB; 381b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BlockInfo *CurrentBlockInfo; 382b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}; 383b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 384b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 385b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// Dump an SCFG to llvm::errs(). 386b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruvoid printSCFG(CFGWalker &Walker); 387b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 38850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 389b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} // end namespace threadSafety 390b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 391b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} // end namespace clang 392b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 393b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H 394b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru