Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1 | //===- ThreadSafety.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 | // A intra-procedural analysis for thread safety (e.g. deadlocks and race |
| 11 | // conditions), based off of an annotation system. |
| 12 | // |
Caitlin Sadowski | 1990346 | 2011-09-14 20:05:09 +0000 | [diff] [blame] | 13 | // See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more |
| 14 | // information. |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 15 | // |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | |
| 18 | #include "clang/Analysis/Analyses/ThreadSafety.h" |
Benjamin Kramer | 2fa67ef | 2012-12-01 15:09:41 +0000 | [diff] [blame] | 19 | #include "clang/AST/Attr.h" |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 20 | #include "clang/AST/DeclCXX.h" |
| 21 | #include "clang/AST/ExprCXX.h" |
| 22 | #include "clang/AST/StmtCXX.h" |
| 23 | #include "clang/AST/StmtVisitor.h" |
Chandler Carruth | 55fc873 | 2012-12-04 09:13:33 +0000 | [diff] [blame] | 24 | #include "clang/Analysis/Analyses/PostOrderCFGView.h" |
| 25 | #include "clang/Analysis/AnalysisContext.h" |
| 26 | #include "clang/Analysis/CFG.h" |
| 27 | #include "clang/Analysis/CFGStmtMap.h" |
DeLesley Hutchins | 96fac6a | 2012-07-03 19:47:18 +0000 | [diff] [blame] | 28 | #include "clang/Basic/OperatorKinds.h" |
Benjamin Kramer | 2fa67ef | 2012-12-01 15:09:41 +0000 | [diff] [blame] | 29 | #include "clang/Basic/SourceLocation.h" |
| 30 | #include "clang/Basic/SourceManager.h" |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 31 | #include "llvm/ADT/BitVector.h" |
| 32 | #include "llvm/ADT/FoldingSet.h" |
| 33 | #include "llvm/ADT/ImmutableMap.h" |
| 34 | #include "llvm/ADT/PostOrderIterator.h" |
| 35 | #include "llvm/ADT/SmallVector.h" |
| 36 | #include "llvm/ADT/StringRef.h" |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 37 | #include "llvm/Support/raw_ostream.h" |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 38 | #include <algorithm> |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 39 | #include <utility> |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 40 | #include <vector> |
| 41 | |
| 42 | using namespace clang; |
| 43 | using namespace thread_safety; |
| 44 | |
Caitlin Sadowski | 1990346 | 2011-09-14 20:05:09 +0000 | [diff] [blame] | 45 | // Key method definition |
| 46 | ThreadSafetyHandler::~ThreadSafetyHandler() {} |
| 47 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 48 | namespace { |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 49 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 50 | /// SExpr implements a simple expression language that is used to store, |
| 51 | /// compare, and pretty-print C++ expressions. Unlike a clang Expr, a SExpr |
| 52 | /// does not capture surface syntax, and it does not distinguish between |
| 53 | /// C++ concepts, like pointers and references, that have no real semantic |
| 54 | /// differences. This simplicity allows SExprs to be meaningfully compared, |
| 55 | /// e.g. |
| 56 | /// (x) = x |
| 57 | /// (*this).foo = this->foo |
| 58 | /// *&a = a |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 59 | /// |
| 60 | /// Thread-safety analysis works by comparing lock expressions. Within the |
| 61 | /// body of a function, an expression such as "x->foo->bar.mu" will resolve to |
| 62 | /// a particular mutex object at run-time. Subsequent occurrences of the same |
| 63 | /// expression (where "same" means syntactic equality) will refer to the same |
| 64 | /// run-time object if three conditions hold: |
| 65 | /// (1) Local variables in the expression, such as "x" have not changed. |
| 66 | /// (2) Values on the heap that affect the expression have not changed. |
| 67 | /// (3) The expression involves only pure function calls. |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 68 | /// |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 69 | /// The current implementation assumes, but does not verify, that multiple uses |
| 70 | /// of the same lock expression satisfies these criteria. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 71 | class SExpr { |
| 72 | private: |
| 73 | enum ExprOp { |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 74 | EOP_Nop, ///< No-op |
| 75 | EOP_Wildcard, ///< Matches anything. |
| 76 | EOP_Universal, ///< Universal lock. |
| 77 | EOP_This, ///< This keyword. |
| 78 | EOP_NVar, ///< Named variable. |
| 79 | EOP_LVar, ///< Local variable. |
| 80 | EOP_Dot, ///< Field access |
| 81 | EOP_Call, ///< Function call |
| 82 | EOP_MCall, ///< Method call |
| 83 | EOP_Index, ///< Array index |
| 84 | EOP_Unary, ///< Unary operation |
| 85 | EOP_Binary, ///< Binary operation |
| 86 | EOP_Unknown ///< Catchall for everything else |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 87 | }; |
| 88 | |
| 89 | |
| 90 | class SExprNode { |
| 91 | private: |
Ted Kremenek | ad0fe03 | 2012-08-22 23:50:41 +0000 | [diff] [blame] | 92 | unsigned char Op; ///< Opcode of the root node |
| 93 | unsigned char Flags; ///< Additional opcode-specific data |
| 94 | unsigned short Sz; ///< Number of child nodes |
| 95 | const void* Data; ///< Additional opcode-specific data |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 96 | |
| 97 | public: |
| 98 | SExprNode(ExprOp O, unsigned F, const void* D) |
| 99 | : Op(static_cast<unsigned char>(O)), |
| 100 | Flags(static_cast<unsigned char>(F)), Sz(1), Data(D) |
| 101 | { } |
| 102 | |
| 103 | unsigned size() const { return Sz; } |
| 104 | void setSize(unsigned S) { Sz = S; } |
| 105 | |
| 106 | ExprOp kind() const { return static_cast<ExprOp>(Op); } |
| 107 | |
| 108 | const NamedDecl* getNamedDecl() const { |
| 109 | assert(Op == EOP_NVar || Op == EOP_LVar || Op == EOP_Dot); |
| 110 | return reinterpret_cast<const NamedDecl*>(Data); |
| 111 | } |
| 112 | |
| 113 | const NamedDecl* getFunctionDecl() const { |
| 114 | assert(Op == EOP_Call || Op == EOP_MCall); |
| 115 | return reinterpret_cast<const NamedDecl*>(Data); |
| 116 | } |
| 117 | |
| 118 | bool isArrow() const { return Op == EOP_Dot && Flags == 1; } |
| 119 | void setArrow(bool A) { Flags = A ? 1 : 0; } |
| 120 | |
| 121 | unsigned arity() const { |
| 122 | switch (Op) { |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 123 | case EOP_Nop: return 0; |
| 124 | case EOP_Wildcard: return 0; |
| 125 | case EOP_Universal: return 0; |
| 126 | case EOP_NVar: return 0; |
| 127 | case EOP_LVar: return 0; |
| 128 | case EOP_This: return 0; |
| 129 | case EOP_Dot: return 1; |
| 130 | case EOP_Call: return Flags+1; // First arg is function. |
| 131 | case EOP_MCall: return Flags+1; // First arg is implicit obj. |
| 132 | case EOP_Index: return 2; |
| 133 | case EOP_Unary: return 1; |
| 134 | case EOP_Binary: return 2; |
| 135 | case EOP_Unknown: return Flags; |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 136 | } |
| 137 | return 0; |
| 138 | } |
| 139 | |
| 140 | bool operator==(const SExprNode& Other) const { |
| 141 | // Ignore flags and size -- they don't matter. |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 142 | return (Op == Other.Op && |
| 143 | Data == Other.Data); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 144 | } |
| 145 | |
| 146 | bool operator!=(const SExprNode& Other) const { |
| 147 | return !(*this == Other); |
| 148 | } |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 149 | |
| 150 | bool matches(const SExprNode& Other) const { |
| 151 | return (*this == Other) || |
| 152 | (Op == EOP_Wildcard) || |
| 153 | (Other.Op == EOP_Wildcard); |
| 154 | } |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 155 | }; |
| 156 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 157 | |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 158 | /// \brief Encapsulates the lexical context of a function call. The lexical |
| 159 | /// context includes the arguments to the call, including the implicit object |
| 160 | /// argument. When an attribute containing a mutex expression is attached to |
| 161 | /// a method, the expression may refer to formal parameters of the method. |
| 162 | /// Actual arguments must be substituted for formal parameters to derive |
| 163 | /// the appropriate mutex expression in the lexical context where the function |
| 164 | /// is called. PrevCtx holds the context in which the arguments themselves |
| 165 | /// should be evaluated; multiple calling contexts can be chained together |
| 166 | /// by the lock_returned attribute. |
| 167 | struct CallingContext { |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 168 | const NamedDecl* AttrDecl; // The decl to which the attribute is attached. |
| 169 | const Expr* SelfArg; // Implicit object argument -- e.g. 'this' |
| 170 | bool SelfArrow; // is Self referred to with -> or .? |
| 171 | unsigned NumArgs; // Number of funArgs |
| 172 | const Expr* const* FunArgs; // Function arguments |
| 173 | CallingContext* PrevCtx; // The previous context; or 0 if none. |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 174 | |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 175 | CallingContext(const NamedDecl *D = 0, const Expr *S = 0, |
| 176 | unsigned N = 0, const Expr* const *A = 0, |
| 177 | CallingContext *P = 0) |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 178 | : AttrDecl(D), SelfArg(S), SelfArrow(false), |
| 179 | NumArgs(N), FunArgs(A), PrevCtx(P) |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 180 | { } |
| 181 | }; |
| 182 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 183 | typedef SmallVector<SExprNode, 4> NodeVector; |
| 184 | |
| 185 | private: |
| 186 | // A SExpr is a list of SExprNodes in prefix order. The Size field allows |
| 187 | // the list to be traversed as a tree. |
| 188 | NodeVector NodeVec; |
| 189 | |
| 190 | private: |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 191 | unsigned makeNop() { |
| 192 | NodeVec.push_back(SExprNode(EOP_Nop, 0, 0)); |
| 193 | return NodeVec.size()-1; |
| 194 | } |
| 195 | |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 196 | unsigned makeWildcard() { |
| 197 | NodeVec.push_back(SExprNode(EOP_Wildcard, 0, 0)); |
| 198 | return NodeVec.size()-1; |
| 199 | } |
| 200 | |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 201 | unsigned makeUniversal() { |
| 202 | NodeVec.push_back(SExprNode(EOP_Universal, 0, 0)); |
| 203 | return NodeVec.size()-1; |
| 204 | } |
| 205 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 206 | unsigned makeNamedVar(const NamedDecl *D) { |
| 207 | NodeVec.push_back(SExprNode(EOP_NVar, 0, D)); |
| 208 | return NodeVec.size()-1; |
| 209 | } |
| 210 | |
| 211 | unsigned makeLocalVar(const NamedDecl *D) { |
| 212 | NodeVec.push_back(SExprNode(EOP_LVar, 0, D)); |
| 213 | return NodeVec.size()-1; |
| 214 | } |
| 215 | |
| 216 | unsigned makeThis() { |
| 217 | NodeVec.push_back(SExprNode(EOP_This, 0, 0)); |
| 218 | return NodeVec.size()-1; |
| 219 | } |
| 220 | |
| 221 | unsigned makeDot(const NamedDecl *D, bool Arrow) { |
| 222 | NodeVec.push_back(SExprNode(EOP_Dot, Arrow ? 1 : 0, D)); |
| 223 | return NodeVec.size()-1; |
| 224 | } |
| 225 | |
| 226 | unsigned makeCall(unsigned NumArgs, const NamedDecl *D) { |
| 227 | NodeVec.push_back(SExprNode(EOP_Call, NumArgs, D)); |
| 228 | return NodeVec.size()-1; |
| 229 | } |
| 230 | |
DeLesley Hutchins | 186af2d | 2012-09-20 22:18:02 +0000 | [diff] [blame] | 231 | // Grab the very first declaration of virtual method D |
| 232 | const CXXMethodDecl* getFirstVirtualDecl(const CXXMethodDecl *D) { |
| 233 | while (true) { |
| 234 | D = D->getCanonicalDecl(); |
| 235 | CXXMethodDecl::method_iterator I = D->begin_overridden_methods(), |
| 236 | E = D->end_overridden_methods(); |
| 237 | if (I == E) |
| 238 | return D; // Method does not override anything |
| 239 | D = *I; // FIXME: this does not work with multiple inheritance. |
| 240 | } |
| 241 | return 0; |
| 242 | } |
| 243 | |
| 244 | unsigned makeMCall(unsigned NumArgs, const CXXMethodDecl *D) { |
| 245 | NodeVec.push_back(SExprNode(EOP_MCall, NumArgs, getFirstVirtualDecl(D))); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 246 | return NodeVec.size()-1; |
| 247 | } |
| 248 | |
| 249 | unsigned makeIndex() { |
| 250 | NodeVec.push_back(SExprNode(EOP_Index, 0, 0)); |
| 251 | return NodeVec.size()-1; |
| 252 | } |
| 253 | |
| 254 | unsigned makeUnary() { |
| 255 | NodeVec.push_back(SExprNode(EOP_Unary, 0, 0)); |
| 256 | return NodeVec.size()-1; |
| 257 | } |
| 258 | |
| 259 | unsigned makeBinary() { |
| 260 | NodeVec.push_back(SExprNode(EOP_Binary, 0, 0)); |
| 261 | return NodeVec.size()-1; |
| 262 | } |
| 263 | |
| 264 | unsigned makeUnknown(unsigned Arity) { |
| 265 | NodeVec.push_back(SExprNode(EOP_Unknown, Arity, 0)); |
| 266 | return NodeVec.size()-1; |
| 267 | } |
| 268 | |
| 269 | /// Build an SExpr from the given C++ expression. |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 270 | /// Recursive function that terminates on DeclRefExpr. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 271 | /// Note: this function merely creates a SExpr; it does not check to |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 272 | /// ensure that the original expression is a valid mutex expression. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 273 | /// |
| 274 | /// NDeref returns the number of Derefence and AddressOf operations |
| 275 | /// preceeding the Expr; this is used to decide whether to pretty-print |
| 276 | /// SExprs with . or ->. |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 277 | unsigned buildSExpr(const Expr *Exp, CallingContext* CallCtx, |
| 278 | int* NDeref = 0) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 279 | if (!Exp) |
| 280 | return 0; |
DeLesley Hutchins | f1ac637 | 2011-10-21 18:10:14 +0000 | [diff] [blame] | 281 | |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 282 | if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { |
| 283 | const NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); |
| 284 | const ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(ND); |
DeLesley Hutchins | e03b2b3 | 2012-01-20 23:24:41 +0000 | [diff] [blame] | 285 | if (PV) { |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 286 | const FunctionDecl *FD = |
DeLesley Hutchins | e03b2b3 | 2012-01-20 23:24:41 +0000 | [diff] [blame] | 287 | cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl(); |
| 288 | unsigned i = PV->getFunctionScopeIndex(); |
| 289 | |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 290 | if (CallCtx && CallCtx->FunArgs && |
| 291 | FD == CallCtx->AttrDecl->getCanonicalDecl()) { |
DeLesley Hutchins | e03b2b3 | 2012-01-20 23:24:41 +0000 | [diff] [blame] | 292 | // Substitute call arguments for references to function parameters |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 293 | assert(i < CallCtx->NumArgs); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 294 | return buildSExpr(CallCtx->FunArgs[i], CallCtx->PrevCtx, NDeref); |
DeLesley Hutchins | e03b2b3 | 2012-01-20 23:24:41 +0000 | [diff] [blame] | 295 | } |
| 296 | // Map the param back to the param of the original function declaration. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 297 | makeNamedVar(FD->getParamDecl(i)); |
| 298 | return 1; |
DeLesley Hutchins | e03b2b3 | 2012-01-20 23:24:41 +0000 | [diff] [blame] | 299 | } |
| 300 | // Not a function parameter -- just store the reference. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 301 | makeNamedVar(ND); |
| 302 | return 1; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 303 | } else if (isa<CXXThisExpr>(Exp)) { |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 304 | // Substitute parent for 'this' |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 305 | if (CallCtx && CallCtx->SelfArg) { |
| 306 | if (!CallCtx->SelfArrow && NDeref) |
| 307 | // 'this' is a pointer, but self is not, so need to take address. |
| 308 | --(*NDeref); |
| 309 | return buildSExpr(CallCtx->SelfArg, CallCtx->PrevCtx, NDeref); |
| 310 | } |
DeLesley Hutchins | 4bda3ec | 2012-02-16 17:03:24 +0000 | [diff] [blame] | 311 | else { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 312 | makeThis(); |
| 313 | return 1; |
DeLesley Hutchins | 4bda3ec | 2012-02-16 17:03:24 +0000 | [diff] [blame] | 314 | } |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 315 | } else if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { |
| 316 | const NamedDecl *ND = ME->getMemberDecl(); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 317 | int ImplicitDeref = ME->isArrow() ? 1 : 0; |
| 318 | unsigned Root = makeDot(ND, false); |
| 319 | unsigned Sz = buildSExpr(ME->getBase(), CallCtx, &ImplicitDeref); |
| 320 | NodeVec[Root].setArrow(ImplicitDeref > 0); |
| 321 | NodeVec[Root].setSize(Sz + 1); |
| 322 | return Sz + 1; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 323 | } else if (const CXXMemberCallExpr *CMCE = dyn_cast<CXXMemberCallExpr>(Exp)) { |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 324 | // When calling a function with a lock_returned attribute, replace |
| 325 | // the function call with the expression in lock_returned. |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 326 | const CXXMethodDecl* MD = |
DeLesley Hutchins | 5408153 | 2012-08-31 22:09:53 +0000 | [diff] [blame] | 327 | cast<CXXMethodDecl>(CMCE->getMethodDecl()->getMostRecentDecl()); |
| 328 | if (LockReturnedAttr* At = MD->getAttr<LockReturnedAttr>()) { |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 329 | CallingContext LRCallCtx(CMCE->getMethodDecl()); |
| 330 | LRCallCtx.SelfArg = CMCE->getImplicitObjectArgument(); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 331 | LRCallCtx.SelfArrow = |
| 332 | dyn_cast<MemberExpr>(CMCE->getCallee())->isArrow(); |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 333 | LRCallCtx.NumArgs = CMCE->getNumArgs(); |
| 334 | LRCallCtx.FunArgs = CMCE->getArgs(); |
| 335 | LRCallCtx.PrevCtx = CallCtx; |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 336 | return buildSExpr(At->getArg(), &LRCallCtx); |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 337 | } |
DeLesley Hutchins | 96fac6a | 2012-07-03 19:47:18 +0000 | [diff] [blame] | 338 | // Hack to treat smart pointers and iterators as pointers; |
| 339 | // ignore any method named get(). |
| 340 | if (CMCE->getMethodDecl()->getNameAsString() == "get" && |
| 341 | CMCE->getNumArgs() == 0) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 342 | if (NDeref && dyn_cast<MemberExpr>(CMCE->getCallee())->isArrow()) |
| 343 | ++(*NDeref); |
| 344 | return buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx, NDeref); |
DeLesley Hutchins | 96fac6a | 2012-07-03 19:47:18 +0000 | [diff] [blame] | 345 | } |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 346 | unsigned NumCallArgs = CMCE->getNumArgs(); |
DeLesley Hutchins | 186af2d | 2012-09-20 22:18:02 +0000 | [diff] [blame] | 347 | unsigned Root = makeMCall(NumCallArgs, CMCE->getMethodDecl()); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 348 | unsigned Sz = buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 349 | const Expr* const* CallArgs = CMCE->getArgs(); |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 350 | for (unsigned i = 0; i < NumCallArgs; ++i) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 351 | Sz += buildSExpr(CallArgs[i], CallCtx); |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 352 | } |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 353 | NodeVec[Root].setSize(Sz + 1); |
| 354 | return Sz + 1; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 355 | } else if (const CallExpr *CE = dyn_cast<CallExpr>(Exp)) { |
| 356 | const FunctionDecl* FD = |
DeLesley Hutchins | 5408153 | 2012-08-31 22:09:53 +0000 | [diff] [blame] | 357 | cast<FunctionDecl>(CE->getDirectCallee()->getMostRecentDecl()); |
| 358 | if (LockReturnedAttr* At = FD->getAttr<LockReturnedAttr>()) { |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 359 | CallingContext LRCallCtx(CE->getDirectCallee()); |
| 360 | LRCallCtx.NumArgs = CE->getNumArgs(); |
| 361 | LRCallCtx.FunArgs = CE->getArgs(); |
| 362 | LRCallCtx.PrevCtx = CallCtx; |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 363 | return buildSExpr(At->getArg(), &LRCallCtx); |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 364 | } |
DeLesley Hutchins | 96fac6a | 2012-07-03 19:47:18 +0000 | [diff] [blame] | 365 | // Treat smart pointers and iterators as pointers; |
| 366 | // ignore the * and -> operators. |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 367 | if (const CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(CE)) { |
DeLesley Hutchins | 96fac6a | 2012-07-03 19:47:18 +0000 | [diff] [blame] | 368 | OverloadedOperatorKind k = OE->getOperator(); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 369 | if (k == OO_Star) { |
| 370 | if (NDeref) ++(*NDeref); |
| 371 | return buildSExpr(OE->getArg(0), CallCtx, NDeref); |
| 372 | } |
| 373 | else if (k == OO_Arrow) { |
| 374 | return buildSExpr(OE->getArg(0), CallCtx, NDeref); |
DeLesley Hutchins | 96fac6a | 2012-07-03 19:47:18 +0000 | [diff] [blame] | 375 | } |
| 376 | } |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 377 | unsigned NumCallArgs = CE->getNumArgs(); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 378 | unsigned Root = makeCall(NumCallArgs, 0); |
| 379 | unsigned Sz = buildSExpr(CE->getCallee(), CallCtx); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 380 | const Expr* const* CallArgs = CE->getArgs(); |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 381 | for (unsigned i = 0; i < NumCallArgs; ++i) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 382 | Sz += buildSExpr(CallArgs[i], CallCtx); |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 383 | } |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 384 | NodeVec[Root].setSize(Sz+1); |
| 385 | return Sz+1; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 386 | } else if (const BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 387 | unsigned Root = makeBinary(); |
| 388 | unsigned Sz = buildSExpr(BOE->getLHS(), CallCtx); |
| 389 | Sz += buildSExpr(BOE->getRHS(), CallCtx); |
| 390 | NodeVec[Root].setSize(Sz); |
| 391 | return Sz; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 392 | } else if (const UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 393 | // Ignore & and * operators -- they're no-ops. |
| 394 | // However, we try to figure out whether the expression is a pointer, |
| 395 | // so we can use . and -> appropriately in error messages. |
| 396 | if (UOE->getOpcode() == UO_Deref) { |
| 397 | if (NDeref) ++(*NDeref); |
| 398 | return buildSExpr(UOE->getSubExpr(), CallCtx, NDeref); |
| 399 | } |
| 400 | if (UOE->getOpcode() == UO_AddrOf) { |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 401 | if (DeclRefExpr* DRE = dyn_cast<DeclRefExpr>(UOE->getSubExpr())) { |
| 402 | if (DRE->getDecl()->isCXXInstanceMember()) { |
| 403 | // This is a pointer-to-member expression, e.g. &MyClass::mu_. |
| 404 | // We interpret this syntax specially, as a wildcard. |
| 405 | unsigned Root = makeDot(DRE->getDecl(), false); |
| 406 | makeWildcard(); |
| 407 | NodeVec[Root].setSize(2); |
| 408 | return 2; |
| 409 | } |
| 410 | } |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 411 | if (NDeref) --(*NDeref); |
| 412 | return buildSExpr(UOE->getSubExpr(), CallCtx, NDeref); |
| 413 | } |
| 414 | unsigned Root = makeUnary(); |
| 415 | unsigned Sz = buildSExpr(UOE->getSubExpr(), CallCtx); |
| 416 | NodeVec[Root].setSize(Sz); |
| 417 | return Sz; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 418 | } else if (const ArraySubscriptExpr *ASE = |
| 419 | dyn_cast<ArraySubscriptExpr>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 420 | unsigned Root = makeIndex(); |
| 421 | unsigned Sz = buildSExpr(ASE->getBase(), CallCtx); |
| 422 | Sz += buildSExpr(ASE->getIdx(), CallCtx); |
| 423 | NodeVec[Root].setSize(Sz); |
| 424 | return Sz; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 425 | } else if (const AbstractConditionalOperator *CE = |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 426 | dyn_cast<AbstractConditionalOperator>(Exp)) { |
| 427 | unsigned Root = makeUnknown(3); |
| 428 | unsigned Sz = buildSExpr(CE->getCond(), CallCtx); |
| 429 | Sz += buildSExpr(CE->getTrueExpr(), CallCtx); |
| 430 | Sz += buildSExpr(CE->getFalseExpr(), CallCtx); |
| 431 | NodeVec[Root].setSize(Sz); |
| 432 | return Sz; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 433 | } else if (const ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 434 | unsigned Root = makeUnknown(3); |
| 435 | unsigned Sz = buildSExpr(CE->getCond(), CallCtx); |
| 436 | Sz += buildSExpr(CE->getLHS(), CallCtx); |
| 437 | Sz += buildSExpr(CE->getRHS(), CallCtx); |
| 438 | NodeVec[Root].setSize(Sz); |
| 439 | return Sz; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 440 | } else if (const CastExpr *CE = dyn_cast<CastExpr>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 441 | return buildSExpr(CE->getSubExpr(), CallCtx, NDeref); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 442 | } else if (const ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 443 | return buildSExpr(PE->getSubExpr(), CallCtx, NDeref); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 444 | } else if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 445 | return buildSExpr(EWC->getSubExpr(), CallCtx, NDeref); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 446 | } else if (const CXXBindTemporaryExpr *E = dyn_cast<CXXBindTemporaryExpr>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 447 | return buildSExpr(E->getSubExpr(), CallCtx, NDeref); |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 448 | } else if (isa<CharacterLiteral>(Exp) || |
DeLesley Hutchins | 9d6e7f3 | 2012-07-03 18:25:56 +0000 | [diff] [blame] | 449 | isa<CXXNullPtrLiteralExpr>(Exp) || |
| 450 | isa<GNUNullExpr>(Exp) || |
| 451 | isa<CXXBoolLiteralExpr>(Exp) || |
| 452 | isa<FloatingLiteral>(Exp) || |
| 453 | isa<ImaginaryLiteral>(Exp) || |
| 454 | isa<IntegerLiteral>(Exp) || |
| 455 | isa<StringLiteral>(Exp) || |
| 456 | isa<ObjCStringLiteral>(Exp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 457 | makeNop(); |
| 458 | return 1; // FIXME: Ignore literals for now |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 459 | } else { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 460 | makeNop(); |
| 461 | return 1; // Ignore. FIXME: mark as invalid expression? |
DeLesley Hutchins | 0d95dfc | 2012-03-02 23:36:05 +0000 | [diff] [blame] | 462 | } |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 463 | } |
| 464 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 465 | /// \brief Construct a SExpr from an expression. |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 466 | /// \param MutexExp The original mutex expression within an attribute |
| 467 | /// \param DeclExp An expression involving the Decl on which the attribute |
| 468 | /// occurs. |
| 469 | /// \param D The declaration to which the lock/unlock attribute is attached. |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 470 | void buildSExprFromExpr(const Expr *MutexExp, const Expr *DeclExp, |
| 471 | const NamedDecl *D, VarDecl *SelfDecl = 0) { |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 472 | CallingContext CallCtx(D); |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 473 | |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 474 | if (MutexExp) { |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 475 | if (const StringLiteral* SLit = dyn_cast<StringLiteral>(MutexExp)) { |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 476 | if (SLit->getString() == StringRef("*")) |
| 477 | // The "*" expr is a universal lock, which essentially turns off |
| 478 | // checks until it is removed from the lockset. |
| 479 | makeUniversal(); |
| 480 | else |
| 481 | // Ignore other string literals for now. |
| 482 | makeNop(); |
| 483 | return; |
| 484 | } |
DeLesley Hutchins | 4e4c157 | 2012-08-31 21:57:32 +0000 | [diff] [blame] | 485 | } |
| 486 | |
DeLesley Hutchins | f1ac637 | 2011-10-21 18:10:14 +0000 | [diff] [blame] | 487 | // If we are processing a raw attribute expression, with no substitutions. |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 488 | if (DeclExp == 0) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 489 | buildSExpr(MutexExp, 0); |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 490 | return; |
| 491 | } |
| 492 | |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 493 | // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 494 | // for formal parameters when we call buildMutexID later. |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 495 | if (const MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 496 | CallCtx.SelfArg = ME->getBase(); |
| 497 | CallCtx.SelfArrow = ME->isArrow(); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 498 | } else if (const CXXMemberCallExpr *CE = |
| 499 | dyn_cast<CXXMemberCallExpr>(DeclExp)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 500 | CallCtx.SelfArg = CE->getImplicitObjectArgument(); |
| 501 | CallCtx.SelfArrow = dyn_cast<MemberExpr>(CE->getCallee())->isArrow(); |
| 502 | CallCtx.NumArgs = CE->getNumArgs(); |
| 503 | CallCtx.FunArgs = CE->getArgs(); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 504 | } else if (const CallExpr *CE = |
| 505 | dyn_cast<CallExpr>(DeclExp)) { |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 506 | CallCtx.NumArgs = CE->getNumArgs(); |
| 507 | CallCtx.FunArgs = CE->getArgs(); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 508 | } else if (const CXXConstructExpr *CE = |
| 509 | dyn_cast<CXXConstructExpr>(DeclExp)) { |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 510 | CallCtx.SelfArg = 0; // Will be set below |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 511 | CallCtx.NumArgs = CE->getNumArgs(); |
| 512 | CallCtx.FunArgs = CE->getArgs(); |
DeLesley Hutchins | 6db51f7 | 2011-10-21 20:51:27 +0000 | [diff] [blame] | 513 | } else if (D && isa<CXXDestructorDecl>(D)) { |
| 514 | // There's no such thing as a "destructor call" in the AST. |
DeLesley Hutchins | f63797c | 2012-06-25 18:33:18 +0000 | [diff] [blame] | 515 | CallCtx.SelfArg = DeclExp; |
DeLesley Hutchins | 8121639 | 2011-10-17 21:38:02 +0000 | [diff] [blame] | 516 | } |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 517 | |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 518 | // Hack to handle constructors, where self cannot be recovered from |
| 519 | // the expression. |
| 520 | if (SelfDecl && !CallCtx.SelfArg) { |
| 521 | DeclRefExpr SelfDRE(SelfDecl, false, SelfDecl->getType(), VK_LValue, |
| 522 | SelfDecl->getLocation()); |
| 523 | CallCtx.SelfArg = &SelfDRE; |
| 524 | |
| 525 | // If the attribute has no arguments, then assume the argument is "this". |
| 526 | if (MutexExp == 0) |
| 527 | buildSExpr(CallCtx.SelfArg, 0); |
| 528 | else // For most attributes. |
| 529 | buildSExpr(MutexExp, &CallCtx); |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 530 | return; |
| 531 | } |
DeLesley Hutchins | 8121639 | 2011-10-17 21:38:02 +0000 | [diff] [blame] | 532 | |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 533 | // If the attribute has no arguments, then assume the argument is "this". |
| 534 | if (MutexExp == 0) |
| 535 | buildSExpr(CallCtx.SelfArg, 0); |
| 536 | else // For most attributes. |
| 537 | buildSExpr(MutexExp, &CallCtx); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 538 | } |
| 539 | |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 540 | /// \brief Get index of next sibling of node i. |
| 541 | unsigned getNextSibling(unsigned i) const { |
| 542 | return i + NodeVec[i].size(); |
| 543 | } |
| 544 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 545 | public: |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 546 | explicit SExpr(clang::Decl::EmptyShell e) { NodeVec.clear(); } |
DeLesley Hutchins | 1fa3c06 | 2011-12-08 20:23:06 +0000 | [diff] [blame] | 547 | |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 548 | /// \param MutexExp The original mutex expression within an attribute |
| 549 | /// \param DeclExp An expression involving the Decl on which the attribute |
| 550 | /// occurs. |
| 551 | /// \param D The declaration to which the lock/unlock attribute is attached. |
| 552 | /// Caller must check isValid() after construction. |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 553 | SExpr(const Expr* MutexExp, const Expr *DeclExp, const NamedDecl* D, |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 554 | VarDecl *SelfDecl=0) { |
| 555 | buildSExprFromExpr(MutexExp, DeclExp, D, SelfDecl); |
Caitlin Sadowski | 194418f | 2011-09-14 20:00:24 +0000 | [diff] [blame] | 556 | } |
| 557 | |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 558 | /// Return true if this is a valid decl sequence. |
| 559 | /// Caller must call this by hand after construction to handle errors. |
Caitlin Sadowski | 194418f | 2011-09-14 20:00:24 +0000 | [diff] [blame] | 560 | bool isValid() const { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 561 | return !NodeVec.empty(); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 562 | } |
| 563 | |
DeLesley Hutchins | 4e4c157 | 2012-08-31 21:57:32 +0000 | [diff] [blame] | 564 | bool shouldIgnore() const { |
| 565 | // Nop is a mutex that we have decided to deliberately ignore. |
| 566 | assert(NodeVec.size() > 0 && "Invalid Mutex"); |
| 567 | return NodeVec[0].kind() == EOP_Nop; |
| 568 | } |
| 569 | |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 570 | bool isUniversal() const { |
| 571 | assert(NodeVec.size() > 0 && "Invalid Mutex"); |
| 572 | return NodeVec[0].kind() == EOP_Universal; |
| 573 | } |
| 574 | |
DeLesley Hutchins | f1ac637 | 2011-10-21 18:10:14 +0000 | [diff] [blame] | 575 | /// Issue a warning about an invalid lock expression |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 576 | static void warnInvalidLock(ThreadSafetyHandler &Handler, |
| 577 | const Expr *MutexExp, |
| 578 | const Expr *DeclExp, const NamedDecl* D) { |
DeLesley Hutchins | f1ac637 | 2011-10-21 18:10:14 +0000 | [diff] [blame] | 579 | SourceLocation Loc; |
| 580 | if (DeclExp) |
| 581 | Loc = DeclExp->getExprLoc(); |
| 582 | |
| 583 | // FIXME: add a note about the attribute location in MutexExp or D |
| 584 | if (Loc.isValid()) |
| 585 | Handler.handleInvalidLockExp(Loc); |
| 586 | } |
| 587 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 588 | bool operator==(const SExpr &other) const { |
| 589 | return NodeVec == other.NodeVec; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 590 | } |
| 591 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 592 | bool operator!=(const SExpr &other) const { |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 593 | return !(*this == other); |
| 594 | } |
| 595 | |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 596 | bool matches(const SExpr &Other, unsigned i = 0, unsigned j = 0) const { |
| 597 | if (NodeVec[i].matches(Other.NodeVec[j])) { |
DeLesley Hutchins | f9ee0ba | 2012-09-11 23:04:49 +0000 | [diff] [blame] | 598 | unsigned ni = NodeVec[i].arity(); |
| 599 | unsigned nj = Other.NodeVec[j].arity(); |
| 600 | unsigned n = (ni < nj) ? ni : nj; |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 601 | bool Result = true; |
| 602 | unsigned ci = i+1; // first child of i |
| 603 | unsigned cj = j+1; // first child of j |
| 604 | for (unsigned k = 0; k < n; |
| 605 | ++k, ci=getNextSibling(ci), cj = Other.getNextSibling(cj)) { |
| 606 | Result = Result && matches(Other, ci, cj); |
| 607 | } |
| 608 | return Result; |
| 609 | } |
| 610 | return false; |
| 611 | } |
| 612 | |
DeLesley Hutchins | 3f0ec52 | 2012-09-10 19:58:23 +0000 | [diff] [blame] | 613 | // A partial match between a.mu and b.mu returns true a and b have the same |
| 614 | // type (and thus mu refers to the same mutex declaration), regardless of |
| 615 | // whether a and b are different objects or not. |
| 616 | bool partiallyMatches(const SExpr &Other) const { |
| 617 | if (NodeVec[0].kind() == EOP_Dot) |
| 618 | return NodeVec[0].matches(Other.NodeVec[0]); |
| 619 | return false; |
| 620 | } |
| 621 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 622 | /// \brief Pretty print a lock expression for use in error messages. |
| 623 | std::string toString(unsigned i = 0) const { |
Caitlin Sadowski | 194418f | 2011-09-14 20:00:24 +0000 | [diff] [blame] | 624 | assert(isValid()); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 625 | if (i >= NodeVec.size()) |
| 626 | return ""; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 627 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 628 | const SExprNode* N = &NodeVec[i]; |
| 629 | switch (N->kind()) { |
| 630 | case EOP_Nop: |
| 631 | return "_"; |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 632 | case EOP_Wildcard: |
| 633 | return "(?)"; |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 634 | case EOP_Universal: |
| 635 | return "*"; |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 636 | case EOP_This: |
| 637 | return "this"; |
| 638 | case EOP_NVar: |
| 639 | case EOP_LVar: { |
| 640 | return N->getNamedDecl()->getNameAsString(); |
| 641 | } |
| 642 | case EOP_Dot: { |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 643 | if (NodeVec[i+1].kind() == EOP_Wildcard) { |
| 644 | std::string S = "&"; |
| 645 | S += N->getNamedDecl()->getQualifiedNameAsString(); |
| 646 | return S; |
| 647 | } |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 648 | std::string FieldName = N->getNamedDecl()->getNameAsString(); |
| 649 | if (NodeVec[i+1].kind() == EOP_This) |
| 650 | return FieldName; |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 651 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 652 | std::string S = toString(i+1); |
| 653 | if (N->isArrow()) |
| 654 | return S + "->" + FieldName; |
| 655 | else |
| 656 | return S + "." + FieldName; |
| 657 | } |
| 658 | case EOP_Call: { |
| 659 | std::string S = toString(i+1) + "("; |
| 660 | unsigned NumArgs = N->arity()-1; |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 661 | unsigned ci = getNextSibling(i+1); |
| 662 | for (unsigned k=0; k<NumArgs; ++k, ci = getNextSibling(ci)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 663 | S += toString(ci); |
| 664 | if (k+1 < NumArgs) S += ","; |
| 665 | } |
| 666 | S += ")"; |
| 667 | return S; |
| 668 | } |
| 669 | case EOP_MCall: { |
| 670 | std::string S = ""; |
| 671 | if (NodeVec[i+1].kind() != EOP_This) |
| 672 | S = toString(i+1) + "."; |
| 673 | if (const NamedDecl *D = N->getFunctionDecl()) |
| 674 | S += D->getNameAsString() + "("; |
| 675 | else |
| 676 | S += "#("; |
| 677 | unsigned NumArgs = N->arity()-1; |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 678 | unsigned ci = getNextSibling(i+1); |
| 679 | for (unsigned k=0; k<NumArgs; ++k, ci = getNextSibling(ci)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 680 | S += toString(ci); |
| 681 | if (k+1 < NumArgs) S += ","; |
| 682 | } |
| 683 | S += ")"; |
| 684 | return S; |
| 685 | } |
| 686 | case EOP_Index: { |
| 687 | std::string S1 = toString(i+1); |
| 688 | std::string S2 = toString(i+1 + NodeVec[i+1].size()); |
| 689 | return S1 + "[" + S2 + "]"; |
| 690 | } |
| 691 | case EOP_Unary: { |
| 692 | std::string S = toString(i+1); |
| 693 | return "#" + S; |
| 694 | } |
| 695 | case EOP_Binary: { |
| 696 | std::string S1 = toString(i+1); |
| 697 | std::string S2 = toString(i+1 + NodeVec[i+1].size()); |
| 698 | return "(" + S1 + "#" + S2 + ")"; |
| 699 | } |
| 700 | case EOP_Unknown: { |
| 701 | unsigned NumChildren = N->arity(); |
| 702 | if (NumChildren == 0) |
| 703 | return "(...)"; |
| 704 | std::string S = "("; |
| 705 | unsigned ci = i+1; |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 706 | for (unsigned j = 0; j < NumChildren; ++j, ci = getNextSibling(ci)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 707 | S += toString(ci); |
| 708 | if (j+1 < NumChildren) S += "#"; |
| 709 | } |
| 710 | S += ")"; |
| 711 | return S; |
| 712 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 713 | } |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 714 | return ""; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 715 | } |
| 716 | }; |
| 717 | |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 718 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 719 | |
| 720 | /// \brief A short list of SExprs |
| 721 | class MutexIDList : public SmallVector<SExpr, 3> { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 722 | public: |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 723 | /// \brief Return true if the list contains the specified SExpr |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 724 | /// Performs a linear search, because these lists are almost always very small. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 725 | bool contains(const SExpr& M) { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 726 | for (iterator I=begin(),E=end(); I != E; ++I) |
| 727 | if ((*I) == M) return true; |
| 728 | return false; |
| 729 | } |
| 730 | |
| 731 | /// \brief Push M onto list, bud discard duplicates |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 732 | void push_back_nodup(const SExpr& M) { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 733 | if (!contains(M)) push_back(M); |
| 734 | } |
| 735 | }; |
| 736 | |
| 737 | |
| 738 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 739 | /// \brief This is a helper class that stores info about the most recent |
| 740 | /// accquire of a Lock. |
| 741 | /// |
| 742 | /// The main body of the analysis maps MutexIDs to LockDatas. |
| 743 | struct LockData { |
| 744 | SourceLocation AcquireLoc; |
| 745 | |
| 746 | /// \brief LKind stores whether a lock is held shared or exclusively. |
| 747 | /// Note that this analysis does not currently support either re-entrant |
| 748 | /// locking or lock "upgrading" and "downgrading" between exclusive and |
| 749 | /// shared. |
| 750 | /// |
| 751 | /// FIXME: add support for re-entrant locking and lock up/downgrading |
| 752 | LockKind LKind; |
DeLesley Hutchins | c99a5d8 | 2012-06-28 22:42:48 +0000 | [diff] [blame] | 753 | bool Managed; // for ScopedLockable objects |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 754 | SExpr UnderlyingMutex; // for ScopedLockable objects |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 755 | |
DeLesley Hutchins | c99a5d8 | 2012-06-28 22:42:48 +0000 | [diff] [blame] | 756 | LockData(SourceLocation AcquireLoc, LockKind LKind, bool M = false) |
| 757 | : AcquireLoc(AcquireLoc), LKind(LKind), Managed(M), |
| 758 | UnderlyingMutex(Decl::EmptyShell()) |
DeLesley Hutchins | 1fa3c06 | 2011-12-08 20:23:06 +0000 | [diff] [blame] | 759 | {} |
| 760 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 761 | LockData(SourceLocation AcquireLoc, LockKind LKind, const SExpr &Mu) |
DeLesley Hutchins | c99a5d8 | 2012-06-28 22:42:48 +0000 | [diff] [blame] | 762 | : AcquireLoc(AcquireLoc), LKind(LKind), Managed(false), |
| 763 | UnderlyingMutex(Mu) |
| 764 | {} |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 765 | |
| 766 | bool operator==(const LockData &other) const { |
| 767 | return AcquireLoc == other.AcquireLoc && LKind == other.LKind; |
| 768 | } |
| 769 | |
| 770 | bool operator!=(const LockData &other) const { |
| 771 | return !(*this == other); |
| 772 | } |
| 773 | |
| 774 | void Profile(llvm::FoldingSetNodeID &ID) const { |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 775 | ID.AddInteger(AcquireLoc.getRawEncoding()); |
| 776 | ID.AddInteger(LKind); |
| 777 | } |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 778 | |
| 779 | bool isAtLeast(LockKind LK) { |
| 780 | return (LK == LK_Shared) || (LKind == LK_Exclusive); |
| 781 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 782 | }; |
| 783 | |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 784 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 785 | /// \brief A FactEntry stores a single fact that is known at a particular point |
| 786 | /// in the program execution. Currently, this is information regarding a lock |
| 787 | /// that is held at that point. |
| 788 | struct FactEntry { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 789 | SExpr MutID; |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 790 | LockData LDat; |
| 791 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 792 | FactEntry(const SExpr& M, const LockData& L) |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 793 | : MutID(M), LDat(L) |
| 794 | { } |
| 795 | }; |
| 796 | |
| 797 | |
| 798 | typedef unsigned short FactID; |
| 799 | |
| 800 | /// \brief FactManager manages the memory for all facts that are created during |
| 801 | /// the analysis of a single routine. |
| 802 | class FactManager { |
| 803 | private: |
| 804 | std::vector<FactEntry> Facts; |
| 805 | |
| 806 | public: |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 807 | FactID newLock(const SExpr& M, const LockData& L) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 808 | Facts.push_back(FactEntry(M,L)); |
| 809 | return static_cast<unsigned short>(Facts.size() - 1); |
| 810 | } |
| 811 | |
| 812 | const FactEntry& operator[](FactID F) const { return Facts[F]; } |
| 813 | FactEntry& operator[](FactID F) { return Facts[F]; } |
| 814 | }; |
| 815 | |
| 816 | |
| 817 | /// \brief A FactSet is the set of facts that are known to be true at a |
| 818 | /// particular program point. FactSets must be small, because they are |
| 819 | /// frequently copied, and are thus implemented as a set of indices into a |
| 820 | /// table maintained by a FactManager. A typical FactSet only holds 1 or 2 |
| 821 | /// locks, so we can get away with doing a linear search for lookup. Note |
| 822 | /// that a hashtable or map is inappropriate in this case, because lookups |
| 823 | /// may involve partial pattern matches, rather than exact matches. |
| 824 | class FactSet { |
| 825 | private: |
| 826 | typedef SmallVector<FactID, 4> FactVec; |
| 827 | |
| 828 | FactVec FactIDs; |
| 829 | |
| 830 | public: |
| 831 | typedef FactVec::iterator iterator; |
| 832 | typedef FactVec::const_iterator const_iterator; |
| 833 | |
| 834 | iterator begin() { return FactIDs.begin(); } |
| 835 | const_iterator begin() const { return FactIDs.begin(); } |
| 836 | |
| 837 | iterator end() { return FactIDs.end(); } |
| 838 | const_iterator end() const { return FactIDs.end(); } |
| 839 | |
| 840 | bool isEmpty() const { return FactIDs.size() == 0; } |
| 841 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 842 | FactID addLock(FactManager& FM, const SExpr& M, const LockData& L) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 843 | FactID F = FM.newLock(M, L); |
| 844 | FactIDs.push_back(F); |
| 845 | return F; |
| 846 | } |
| 847 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 848 | bool removeLock(FactManager& FM, const SExpr& M) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 849 | unsigned n = FactIDs.size(); |
| 850 | if (n == 0) |
| 851 | return false; |
| 852 | |
| 853 | for (unsigned i = 0; i < n-1; ++i) { |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 854 | if (FM[FactIDs[i]].MutID.matches(M)) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 855 | FactIDs[i] = FactIDs[n-1]; |
| 856 | FactIDs.pop_back(); |
| 857 | return true; |
| 858 | } |
| 859 | } |
DeLesley Hutchins | ee2f032 | 2012-08-10 20:29:46 +0000 | [diff] [blame] | 860 | if (FM[FactIDs[n-1]].MutID.matches(M)) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 861 | FactIDs.pop_back(); |
| 862 | return true; |
| 863 | } |
| 864 | return false; |
| 865 | } |
| 866 | |
DeLesley Hutchins | 3f0ec52 | 2012-09-10 19:58:23 +0000 | [diff] [blame] | 867 | LockData* findLock(FactManager &FM, const SExpr &M) const { |
Chad Rosier | 2de4770 | 2012-09-07 18:44:15 +0000 | [diff] [blame] | 868 | for (const_iterator I = begin(), E = end(); I != E; ++I) { |
Chad Rosier | 589190b | 2012-09-07 19:49:55 +0000 | [diff] [blame] | 869 | const SExpr &Exp = FM[*I].MutID; |
Chad Rosier | 2de4770 | 2012-09-07 18:44:15 +0000 | [diff] [blame] | 870 | if (Exp.matches(M)) |
| 871 | return &FM[*I].LDat; |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 872 | } |
| 873 | return 0; |
| 874 | } |
| 875 | |
DeLesley Hutchins | 3f0ec52 | 2012-09-10 19:58:23 +0000 | [diff] [blame] | 876 | LockData* findLockUniv(FactManager &FM, const SExpr &M) const { |
Chad Rosier | 2de4770 | 2012-09-07 18:44:15 +0000 | [diff] [blame] | 877 | for (const_iterator I = begin(), E = end(); I != E; ++I) { |
Chad Rosier | 589190b | 2012-09-07 19:49:55 +0000 | [diff] [blame] | 878 | const SExpr &Exp = FM[*I].MutID; |
Chad Rosier | 2de4770 | 2012-09-07 18:44:15 +0000 | [diff] [blame] | 879 | if (Exp.matches(M) || Exp.isUniversal()) |
| 880 | return &FM[*I].LDat; |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 881 | } |
| 882 | return 0; |
| 883 | } |
DeLesley Hutchins | 3f0ec52 | 2012-09-10 19:58:23 +0000 | [diff] [blame] | 884 | |
| 885 | FactEntry* findPartialMatch(FactManager &FM, const SExpr &M) const { |
| 886 | for (const_iterator I=begin(), E=end(); I != E; ++I) { |
| 887 | const SExpr& Exp = FM[*I].MutID; |
| 888 | if (Exp.partiallyMatches(M)) return &FM[*I]; |
| 889 | } |
| 890 | return 0; |
| 891 | } |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 892 | }; |
| 893 | |
| 894 | |
| 895 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 896 | /// A Lockset maps each SExpr (defined above) to information about how it has |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 897 | /// been locked. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 898 | typedef llvm::ImmutableMap<SExpr, LockData> Lockset; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 899 | typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext; |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 900 | |
| 901 | class LocalVariableMap; |
| 902 | |
Richard Smith | 2e51562 | 2012-02-03 04:45:26 +0000 | [diff] [blame] | 903 | /// A side (entry or exit) of a CFG node. |
| 904 | enum CFGBlockSide { CBS_Entry, CBS_Exit }; |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 905 | |
| 906 | /// CFGBlockInfo is a struct which contains all the information that is |
| 907 | /// maintained for each block in the CFG. See LocalVariableMap for more |
| 908 | /// information about the contexts. |
| 909 | struct CFGBlockInfo { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 910 | FactSet EntrySet; // Lockset held at entry to block |
| 911 | FactSet ExitSet; // Lockset held at exit from block |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 912 | LocalVarContext EntryContext; // Context held at entry to block |
| 913 | LocalVarContext ExitContext; // Context held at exit from block |
Richard Smith | 2e51562 | 2012-02-03 04:45:26 +0000 | [diff] [blame] | 914 | SourceLocation EntryLoc; // Location of first statement in block |
| 915 | SourceLocation ExitLoc; // Location of last statement in block. |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 916 | unsigned EntryIndex; // Used to replay contexts later |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 917 | bool Reachable; // Is this block reachable? |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 918 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 919 | const FactSet &getSet(CFGBlockSide Side) const { |
Richard Smith | 2e51562 | 2012-02-03 04:45:26 +0000 | [diff] [blame] | 920 | return Side == CBS_Entry ? EntrySet : ExitSet; |
| 921 | } |
| 922 | SourceLocation getLocation(CFGBlockSide Side) const { |
| 923 | return Side == CBS_Entry ? EntryLoc : ExitLoc; |
| 924 | } |
| 925 | |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 926 | private: |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 927 | CFGBlockInfo(LocalVarContext EmptyCtx) |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 928 | : EntryContext(EmptyCtx), ExitContext(EmptyCtx), Reachable(false) |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 929 | { } |
| 930 | |
| 931 | public: |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 932 | static CFGBlockInfo getEmptyBlockInfo(LocalVariableMap &M); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 933 | }; |
| 934 | |
| 935 | |
| 936 | |
| 937 | // A LocalVariableMap maintains a map from local variables to their currently |
| 938 | // valid definitions. It provides SSA-like functionality when traversing the |
| 939 | // CFG. Like SSA, each definition or assignment to a variable is assigned a |
| 940 | // unique name (an integer), which acts as the SSA name for that definition. |
| 941 | // The total set of names is shared among all CFG basic blocks. |
| 942 | // Unlike SSA, we do not rewrite expressions to replace local variables declrefs |
| 943 | // with their SSA-names. Instead, we compute a Context for each point in the |
| 944 | // code, which maps local variables to the appropriate SSA-name. This map |
| 945 | // changes with each assignment. |
| 946 | // |
| 947 | // The map is computed in a single pass over the CFG. Subsequent analyses can |
| 948 | // then query the map to find the appropriate Context for a statement, and use |
| 949 | // that Context to look up the definitions of variables. |
| 950 | class LocalVariableMap { |
| 951 | public: |
| 952 | typedef LocalVarContext Context; |
| 953 | |
| 954 | /// A VarDefinition consists of an expression, representing the value of the |
| 955 | /// variable, along with the context in which that expression should be |
| 956 | /// interpreted. A reference VarDefinition does not itself contain this |
| 957 | /// information, but instead contains a pointer to a previous VarDefinition. |
| 958 | struct VarDefinition { |
| 959 | public: |
| 960 | friend class LocalVariableMap; |
| 961 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 962 | const NamedDecl *Dec; // The original declaration for this variable. |
| 963 | const Expr *Exp; // The expression for this variable, OR |
| 964 | unsigned Ref; // Reference to another VarDefinition |
| 965 | Context Ctx; // The map with which Exp should be interpreted. |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 966 | |
| 967 | bool isReference() { return !Exp; } |
| 968 | |
| 969 | private: |
| 970 | // Create ordinary variable definition |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 971 | VarDefinition(const NamedDecl *D, const Expr *E, Context C) |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 972 | : Dec(D), Exp(E), Ref(0), Ctx(C) |
| 973 | { } |
| 974 | |
| 975 | // Create reference to previous definition |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 976 | VarDefinition(const NamedDecl *D, unsigned R, Context C) |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 977 | : Dec(D), Exp(0), Ref(R), Ctx(C) |
| 978 | { } |
| 979 | }; |
| 980 | |
| 981 | private: |
| 982 | Context::Factory ContextFactory; |
| 983 | std::vector<VarDefinition> VarDefinitions; |
| 984 | std::vector<unsigned> CtxIndices; |
| 985 | std::vector<std::pair<Stmt*, Context> > SavedContexts; |
| 986 | |
| 987 | public: |
| 988 | LocalVariableMap() { |
| 989 | // index 0 is a placeholder for undefined variables (aka phi-nodes). |
| 990 | VarDefinitions.push_back(VarDefinition(0, 0u, getEmptyContext())); |
| 991 | } |
| 992 | |
| 993 | /// Look up a definition, within the given context. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 994 | const VarDefinition* lookup(const NamedDecl *D, Context Ctx) { |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 995 | const unsigned *i = Ctx.lookup(D); |
| 996 | if (!i) |
| 997 | return 0; |
| 998 | assert(*i < VarDefinitions.size()); |
| 999 | return &VarDefinitions[*i]; |
| 1000 | } |
| 1001 | |
| 1002 | /// Look up the definition for D within the given context. Returns |
DeLesley Hutchins | b4fa418 | 2012-01-06 19:16:50 +0000 | [diff] [blame] | 1003 | /// NULL if the expression is not statically known. If successful, also |
| 1004 | /// modifies Ctx to hold the context of the return Expr. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1005 | const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) { |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1006 | const unsigned *P = Ctx.lookup(D); |
| 1007 | if (!P) |
| 1008 | return 0; |
| 1009 | |
| 1010 | unsigned i = *P; |
| 1011 | while (i > 0) { |
DeLesley Hutchins | b4fa418 | 2012-01-06 19:16:50 +0000 | [diff] [blame] | 1012 | if (VarDefinitions[i].Exp) { |
| 1013 | Ctx = VarDefinitions[i].Ctx; |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1014 | return VarDefinitions[i].Exp; |
DeLesley Hutchins | b4fa418 | 2012-01-06 19:16:50 +0000 | [diff] [blame] | 1015 | } |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1016 | i = VarDefinitions[i].Ref; |
| 1017 | } |
| 1018 | return 0; |
| 1019 | } |
| 1020 | |
| 1021 | Context getEmptyContext() { return ContextFactory.getEmptyMap(); } |
| 1022 | |
| 1023 | /// Return the next context after processing S. This function is used by |
| 1024 | /// clients of the class to get the appropriate context when traversing the |
| 1025 | /// CFG. It must be called for every assignment or DeclStmt. |
| 1026 | Context getNextContext(unsigned &CtxIndex, Stmt *S, Context C) { |
| 1027 | if (SavedContexts[CtxIndex+1].first == S) { |
| 1028 | CtxIndex++; |
| 1029 | Context Result = SavedContexts[CtxIndex].second; |
| 1030 | return Result; |
| 1031 | } |
| 1032 | return C; |
| 1033 | } |
| 1034 | |
| 1035 | void dumpVarDefinitionName(unsigned i) { |
| 1036 | if (i == 0) { |
| 1037 | llvm::errs() << "Undefined"; |
| 1038 | return; |
| 1039 | } |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1040 | const NamedDecl *Dec = VarDefinitions[i].Dec; |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1041 | if (!Dec) { |
| 1042 | llvm::errs() << "<<NULL>>"; |
| 1043 | return; |
| 1044 | } |
| 1045 | Dec->printName(llvm::errs()); |
Roman Divacky | 31ba613 | 2012-09-06 15:59:27 +0000 | [diff] [blame] | 1046 | llvm::errs() << "." << i << " " << ((const void*) Dec); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1047 | } |
| 1048 | |
| 1049 | /// Dumps an ASCII representation of the variable map to llvm::errs() |
| 1050 | void dump() { |
| 1051 | for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) { |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1052 | const Expr *Exp = VarDefinitions[i].Exp; |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1053 | unsigned Ref = VarDefinitions[i].Ref; |
| 1054 | |
| 1055 | dumpVarDefinitionName(i); |
| 1056 | llvm::errs() << " = "; |
| 1057 | if (Exp) Exp->dump(); |
| 1058 | else { |
| 1059 | dumpVarDefinitionName(Ref); |
| 1060 | llvm::errs() << "\n"; |
| 1061 | } |
| 1062 | } |
| 1063 | } |
| 1064 | |
| 1065 | /// Dumps an ASCII representation of a Context to llvm::errs() |
| 1066 | void dumpContext(Context C) { |
| 1067 | for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1068 | const NamedDecl *D = I.getKey(); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1069 | D->printName(llvm::errs()); |
| 1070 | const unsigned *i = C.lookup(D); |
| 1071 | llvm::errs() << " -> "; |
| 1072 | dumpVarDefinitionName(*i); |
| 1073 | llvm::errs() << "\n"; |
| 1074 | } |
| 1075 | } |
| 1076 | |
| 1077 | /// Builds the variable map. |
| 1078 | void traverseCFG(CFG *CFGraph, PostOrderCFGView *SortedGraph, |
| 1079 | std::vector<CFGBlockInfo> &BlockInfo); |
| 1080 | |
| 1081 | protected: |
| 1082 | // Get the current context index |
| 1083 | unsigned getContextIndex() { return SavedContexts.size()-1; } |
| 1084 | |
| 1085 | // Save the current context for later replay |
| 1086 | void saveContext(Stmt *S, Context C) { |
| 1087 | SavedContexts.push_back(std::make_pair(S,C)); |
| 1088 | } |
| 1089 | |
| 1090 | // Adds a new definition to the given context, and returns a new context. |
| 1091 | // This method should be called when declaring a new variable. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1092 | Context addDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1093 | assert(!Ctx.contains(D)); |
| 1094 | unsigned newID = VarDefinitions.size(); |
| 1095 | Context NewCtx = ContextFactory.add(Ctx, D, newID); |
| 1096 | VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); |
| 1097 | return NewCtx; |
| 1098 | } |
| 1099 | |
| 1100 | // Add a new reference to an existing definition. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1101 | Context addReference(const NamedDecl *D, unsigned i, Context Ctx) { |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1102 | unsigned newID = VarDefinitions.size(); |
| 1103 | Context NewCtx = ContextFactory.add(Ctx, D, newID); |
| 1104 | VarDefinitions.push_back(VarDefinition(D, i, Ctx)); |
| 1105 | return NewCtx; |
| 1106 | } |
| 1107 | |
| 1108 | // Updates a definition only if that definition is already in the map. |
| 1109 | // This method should be called when assigning to an existing variable. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1110 | Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1111 | if (Ctx.contains(D)) { |
| 1112 | unsigned newID = VarDefinitions.size(); |
| 1113 | Context NewCtx = ContextFactory.remove(Ctx, D); |
| 1114 | NewCtx = ContextFactory.add(NewCtx, D, newID); |
| 1115 | VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); |
| 1116 | return NewCtx; |
| 1117 | } |
| 1118 | return Ctx; |
| 1119 | } |
| 1120 | |
| 1121 | // Removes a definition from the context, but keeps the variable name |
| 1122 | // as a valid variable. The index 0 is a placeholder for cleared definitions. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1123 | Context clearDefinition(const NamedDecl *D, Context Ctx) { |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1124 | Context NewCtx = Ctx; |
| 1125 | if (NewCtx.contains(D)) { |
| 1126 | NewCtx = ContextFactory.remove(NewCtx, D); |
| 1127 | NewCtx = ContextFactory.add(NewCtx, D, 0); |
| 1128 | } |
| 1129 | return NewCtx; |
| 1130 | } |
| 1131 | |
| 1132 | // Remove a definition entirely frmo the context. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1133 | Context removeDefinition(const NamedDecl *D, Context Ctx) { |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1134 | Context NewCtx = Ctx; |
| 1135 | if (NewCtx.contains(D)) { |
| 1136 | NewCtx = ContextFactory.remove(NewCtx, D); |
| 1137 | } |
| 1138 | return NewCtx; |
| 1139 | } |
| 1140 | |
| 1141 | Context intersectContexts(Context C1, Context C2); |
| 1142 | Context createReferenceContext(Context C); |
| 1143 | void intersectBackEdge(Context C1, Context C2); |
| 1144 | |
| 1145 | friend class VarMapBuilder; |
| 1146 | }; |
| 1147 | |
| 1148 | |
| 1149 | // This has to be defined after LocalVariableMap. |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1150 | CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(LocalVariableMap &M) { |
| 1151 | return CFGBlockInfo(M.getEmptyContext()); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1152 | } |
| 1153 | |
| 1154 | |
| 1155 | /// Visitor which builds a LocalVariableMap |
| 1156 | class VarMapBuilder : public StmtVisitor<VarMapBuilder> { |
| 1157 | public: |
| 1158 | LocalVariableMap* VMap; |
| 1159 | LocalVariableMap::Context Ctx; |
| 1160 | |
| 1161 | VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C) |
| 1162 | : VMap(VM), Ctx(C) {} |
| 1163 | |
| 1164 | void VisitDeclStmt(DeclStmt *S); |
| 1165 | void VisitBinaryOperator(BinaryOperator *BO); |
| 1166 | }; |
| 1167 | |
| 1168 | |
| 1169 | // Add new local variables to the variable map |
| 1170 | void VarMapBuilder::VisitDeclStmt(DeclStmt *S) { |
| 1171 | bool modifiedCtx = false; |
| 1172 | DeclGroupRef DGrp = S->getDeclGroup(); |
| 1173 | for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { |
| 1174 | if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) { |
| 1175 | Expr *E = VD->getInit(); |
| 1176 | |
| 1177 | // Add local variables with trivial type to the variable map |
| 1178 | QualType T = VD->getType(); |
| 1179 | if (T.isTrivialType(VD->getASTContext())) { |
| 1180 | Ctx = VMap->addDefinition(VD, E, Ctx); |
| 1181 | modifiedCtx = true; |
| 1182 | } |
| 1183 | } |
| 1184 | } |
| 1185 | if (modifiedCtx) |
| 1186 | VMap->saveContext(S, Ctx); |
| 1187 | } |
| 1188 | |
| 1189 | // Update local variable definitions in variable map |
| 1190 | void VarMapBuilder::VisitBinaryOperator(BinaryOperator *BO) { |
| 1191 | if (!BO->isAssignmentOp()) |
| 1192 | return; |
| 1193 | |
| 1194 | Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); |
| 1195 | |
| 1196 | // Update the variable map and current context. |
| 1197 | if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHSExp)) { |
| 1198 | ValueDecl *VDec = DRE->getDecl(); |
| 1199 | if (Ctx.lookup(VDec)) { |
| 1200 | if (BO->getOpcode() == BO_Assign) |
| 1201 | Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx); |
| 1202 | else |
| 1203 | // FIXME -- handle compound assignment operators |
| 1204 | Ctx = VMap->clearDefinition(VDec, Ctx); |
| 1205 | VMap->saveContext(BO, Ctx); |
| 1206 | } |
| 1207 | } |
| 1208 | } |
| 1209 | |
| 1210 | |
| 1211 | // Computes the intersection of two contexts. The intersection is the |
| 1212 | // set of variables which have the same definition in both contexts; |
| 1213 | // variables with different definitions are discarded. |
| 1214 | LocalVariableMap::Context |
| 1215 | LocalVariableMap::intersectContexts(Context C1, Context C2) { |
| 1216 | Context Result = C1; |
| 1217 | for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1218 | const NamedDecl *Dec = I.getKey(); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1219 | unsigned i1 = I.getData(); |
| 1220 | const unsigned *i2 = C2.lookup(Dec); |
| 1221 | if (!i2) // variable doesn't exist on second path |
| 1222 | Result = removeDefinition(Dec, Result); |
| 1223 | else if (*i2 != i1) // variable exists, but has different definition |
| 1224 | Result = clearDefinition(Dec, Result); |
| 1225 | } |
| 1226 | return Result; |
| 1227 | } |
| 1228 | |
| 1229 | // For every variable in C, create a new variable that refers to the |
| 1230 | // definition in C. Return a new context that contains these new variables. |
| 1231 | // (We use this for a naive implementation of SSA on loop back-edges.) |
| 1232 | LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) { |
| 1233 | Context Result = getEmptyContext(); |
| 1234 | for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1235 | const NamedDecl *Dec = I.getKey(); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1236 | unsigned i = I.getData(); |
| 1237 | Result = addReference(Dec, i, Result); |
| 1238 | } |
| 1239 | return Result; |
| 1240 | } |
| 1241 | |
| 1242 | // This routine also takes the intersection of C1 and C2, but it does so by |
| 1243 | // altering the VarDefinitions. C1 must be the result of an earlier call to |
| 1244 | // createReferenceContext. |
| 1245 | void LocalVariableMap::intersectBackEdge(Context C1, Context C2) { |
| 1246 | for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1247 | const NamedDecl *Dec = I.getKey(); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1248 | unsigned i1 = I.getData(); |
| 1249 | VarDefinition *VDef = &VarDefinitions[i1]; |
| 1250 | assert(VDef->isReference()); |
| 1251 | |
| 1252 | const unsigned *i2 = C2.lookup(Dec); |
| 1253 | if (!i2 || (*i2 != i1)) |
| 1254 | VDef->Ref = 0; // Mark this variable as undefined |
| 1255 | } |
| 1256 | } |
| 1257 | |
| 1258 | |
| 1259 | // Traverse the CFG in topological order, so all predecessors of a block |
| 1260 | // (excluding back-edges) are visited before the block itself. At |
| 1261 | // each point in the code, we calculate a Context, which holds the set of |
| 1262 | // variable definitions which are visible at that point in execution. |
| 1263 | // Visible variables are mapped to their definitions using an array that |
| 1264 | // contains all definitions. |
| 1265 | // |
| 1266 | // At join points in the CFG, the set is computed as the intersection of |
| 1267 | // the incoming sets along each edge, E.g. |
| 1268 | // |
| 1269 | // { Context | VarDefinitions } |
| 1270 | // int x = 0; { x -> x1 | x1 = 0 } |
| 1271 | // int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } |
| 1272 | // if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... } |
| 1273 | // else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... } |
| 1274 | // ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... } |
| 1275 | // |
| 1276 | // This is essentially a simpler and more naive version of the standard SSA |
| 1277 | // algorithm. Those definitions that remain in the intersection are from blocks |
| 1278 | // that strictly dominate the current block. We do not bother to insert proper |
| 1279 | // phi nodes, because they are not used in our analysis; instead, wherever |
| 1280 | // a phi node would be required, we simply remove that definition from the |
| 1281 | // context (E.g. x above). |
| 1282 | // |
| 1283 | // The initial traversal does not capture back-edges, so those need to be |
| 1284 | // handled on a separate pass. Whenever the first pass encounters an |
| 1285 | // incoming back edge, it duplicates the context, creating new definitions |
| 1286 | // that refer back to the originals. (These correspond to places where SSA |
| 1287 | // might have to insert a phi node.) On the second pass, these definitions are |
Sylvestre Ledru | bed28ac | 2012-07-23 08:59:39 +0000 | [diff] [blame] | 1288 | // set to NULL if the variable has changed on the back-edge (i.e. a phi |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1289 | // node was actually required.) E.g. |
| 1290 | // |
| 1291 | // { Context | VarDefinitions } |
| 1292 | // int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } |
| 1293 | // while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; } |
| 1294 | // x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... } |
| 1295 | // ... { y -> y1 | x3 = 2, x2 = 1, ... } |
| 1296 | // |
| 1297 | void LocalVariableMap::traverseCFG(CFG *CFGraph, |
| 1298 | PostOrderCFGView *SortedGraph, |
| 1299 | std::vector<CFGBlockInfo> &BlockInfo) { |
| 1300 | PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); |
| 1301 | |
| 1302 | CtxIndices.resize(CFGraph->getNumBlockIDs()); |
| 1303 | |
| 1304 | for (PostOrderCFGView::iterator I = SortedGraph->begin(), |
| 1305 | E = SortedGraph->end(); I!= E; ++I) { |
| 1306 | const CFGBlock *CurrBlock = *I; |
| 1307 | int CurrBlockID = CurrBlock->getBlockID(); |
| 1308 | CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; |
| 1309 | |
| 1310 | VisitedBlocks.insert(CurrBlock); |
| 1311 | |
| 1312 | // Calculate the entry context for the current block |
| 1313 | bool HasBackEdges = false; |
| 1314 | bool CtxInit = true; |
| 1315 | for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), |
| 1316 | PE = CurrBlock->pred_end(); PI != PE; ++PI) { |
| 1317 | // if *PI -> CurrBlock is a back edge, so skip it |
| 1318 | if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) { |
| 1319 | HasBackEdges = true; |
| 1320 | continue; |
| 1321 | } |
| 1322 | |
| 1323 | int PrevBlockID = (*PI)->getBlockID(); |
| 1324 | CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; |
| 1325 | |
| 1326 | if (CtxInit) { |
| 1327 | CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext; |
| 1328 | CtxInit = false; |
| 1329 | } |
| 1330 | else { |
| 1331 | CurrBlockInfo->EntryContext = |
| 1332 | intersectContexts(CurrBlockInfo->EntryContext, |
| 1333 | PrevBlockInfo->ExitContext); |
| 1334 | } |
| 1335 | } |
| 1336 | |
| 1337 | // Duplicate the context if we have back-edges, so we can call |
| 1338 | // intersectBackEdges later. |
| 1339 | if (HasBackEdges) |
| 1340 | CurrBlockInfo->EntryContext = |
| 1341 | createReferenceContext(CurrBlockInfo->EntryContext); |
| 1342 | |
| 1343 | // Create a starting context index for the current block |
| 1344 | saveContext(0, CurrBlockInfo->EntryContext); |
| 1345 | CurrBlockInfo->EntryIndex = getContextIndex(); |
| 1346 | |
| 1347 | // Visit all the statements in the basic block. |
| 1348 | VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext); |
| 1349 | for (CFGBlock::const_iterator BI = CurrBlock->begin(), |
| 1350 | BE = CurrBlock->end(); BI != BE; ++BI) { |
| 1351 | switch (BI->getKind()) { |
| 1352 | case CFGElement::Statement: { |
| 1353 | const CFGStmt *CS = cast<CFGStmt>(&*BI); |
| 1354 | VMapBuilder.Visit(const_cast<Stmt*>(CS->getStmt())); |
| 1355 | break; |
| 1356 | } |
| 1357 | default: |
| 1358 | break; |
| 1359 | } |
| 1360 | } |
| 1361 | CurrBlockInfo->ExitContext = VMapBuilder.Ctx; |
| 1362 | |
| 1363 | // Mark variables on back edges as "unknown" if they've been changed. |
| 1364 | for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), |
| 1365 | SE = CurrBlock->succ_end(); SI != SE; ++SI) { |
| 1366 | // if CurrBlock -> *SI is *not* a back edge |
| 1367 | if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) |
| 1368 | continue; |
| 1369 | |
| 1370 | CFGBlock *FirstLoopBlock = *SI; |
| 1371 | Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext; |
| 1372 | Context LoopEnd = CurrBlockInfo->ExitContext; |
| 1373 | intersectBackEdge(LoopBegin, LoopEnd); |
| 1374 | } |
| 1375 | } |
| 1376 | |
| 1377 | // Put an extra entry at the end of the indexed context array |
| 1378 | unsigned exitID = CFGraph->getExit().getBlockID(); |
| 1379 | saveContext(0, BlockInfo[exitID].ExitContext); |
| 1380 | } |
| 1381 | |
Richard Smith | 2e51562 | 2012-02-03 04:45:26 +0000 | [diff] [blame] | 1382 | /// Find the appropriate source locations to use when producing diagnostics for |
| 1383 | /// each block in the CFG. |
| 1384 | static void findBlockLocations(CFG *CFGraph, |
| 1385 | PostOrderCFGView *SortedGraph, |
| 1386 | std::vector<CFGBlockInfo> &BlockInfo) { |
| 1387 | for (PostOrderCFGView::iterator I = SortedGraph->begin(), |
| 1388 | E = SortedGraph->end(); I!= E; ++I) { |
| 1389 | const CFGBlock *CurrBlock = *I; |
| 1390 | CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()]; |
| 1391 | |
| 1392 | // Find the source location of the last statement in the block, if the |
| 1393 | // block is not empty. |
| 1394 | if (const Stmt *S = CurrBlock->getTerminator()) { |
| 1395 | CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getLocStart(); |
| 1396 | } else { |
| 1397 | for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(), |
| 1398 | BE = CurrBlock->rend(); BI != BE; ++BI) { |
| 1399 | // FIXME: Handle other CFGElement kinds. |
| 1400 | if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) { |
| 1401 | CurrBlockInfo->ExitLoc = CS->getStmt()->getLocStart(); |
| 1402 | break; |
| 1403 | } |
| 1404 | } |
| 1405 | } |
| 1406 | |
| 1407 | if (!CurrBlockInfo->ExitLoc.isInvalid()) { |
| 1408 | // This block contains at least one statement. Find the source location |
| 1409 | // of the first statement in the block. |
| 1410 | for (CFGBlock::const_iterator BI = CurrBlock->begin(), |
| 1411 | BE = CurrBlock->end(); BI != BE; ++BI) { |
| 1412 | // FIXME: Handle other CFGElement kinds. |
| 1413 | if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) { |
| 1414 | CurrBlockInfo->EntryLoc = CS->getStmt()->getLocStart(); |
| 1415 | break; |
| 1416 | } |
| 1417 | } |
| 1418 | } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() && |
| 1419 | CurrBlock != &CFGraph->getExit()) { |
| 1420 | // The block is empty, and has a single predecessor. Use its exit |
| 1421 | // location. |
| 1422 | CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = |
| 1423 | BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc; |
| 1424 | } |
| 1425 | } |
| 1426 | } |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1427 | |
| 1428 | /// \brief Class which implements the core thread safety analysis routines. |
| 1429 | class ThreadSafetyAnalyzer { |
| 1430 | friend class BuildLockset; |
| 1431 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1432 | ThreadSafetyHandler &Handler; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1433 | LocalVariableMap LocalVarMap; |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1434 | FactManager FactMan; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1435 | std::vector<CFGBlockInfo> BlockInfo; |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1436 | |
| 1437 | public: |
| 1438 | ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {} |
| 1439 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1440 | void addLock(FactSet &FSet, const SExpr &Mutex, const LockData &LDat); |
| 1441 | void removeLock(FactSet &FSet, const SExpr &Mutex, |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1442 | SourceLocation UnlockLoc, bool FullyRemove=false); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1443 | |
| 1444 | template <typename AttrType> |
| 1445 | void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp, |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 1446 | const NamedDecl *D, VarDecl *SelfDecl=0); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1447 | |
| 1448 | template <class AttrType> |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1449 | void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp, |
| 1450 | const NamedDecl *D, |
| 1451 | const CFGBlock *PredBlock, const CFGBlock *CurrBlock, |
| 1452 | Expr *BrE, bool Neg); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1453 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1454 | const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C, |
| 1455 | bool &Negate); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1456 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1457 | void getEdgeLockset(FactSet &Result, const FactSet &ExitSet, |
| 1458 | const CFGBlock* PredBlock, |
| 1459 | const CFGBlock *CurrBlock); |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 1460 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1461 | void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, |
| 1462 | SourceLocation JoinLoc, |
| 1463 | LockErrorKind LEK1, LockErrorKind LEK2, |
| 1464 | bool Modify=true); |
DeLesley Hutchins | 879a433 | 2012-07-02 22:16:54 +0000 | [diff] [blame] | 1465 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1466 | void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, |
| 1467 | SourceLocation JoinLoc, LockErrorKind LEK1, |
| 1468 | bool Modify=true) { |
| 1469 | intersectAndWarn(FSet1, FSet2, JoinLoc, LEK1, LEK1, Modify); |
DeLesley Hutchins | 879a433 | 2012-07-02 22:16:54 +0000 | [diff] [blame] | 1470 | } |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1471 | |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1472 | void runAnalysis(AnalysisDeclContext &AC); |
| 1473 | }; |
| 1474 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1475 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1476 | /// \brief Add a new lock to the lockset, warning if the lock is already there. |
| 1477 | /// \param Mutex -- the Mutex expression for the lock |
| 1478 | /// \param LDat -- the LockData for the lock |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1479 | void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const SExpr &Mutex, |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1480 | const LockData &LDat) { |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1481 | // FIXME: deal with acquired before/after annotations. |
| 1482 | // FIXME: Don't always warn when we have support for reentrant locks. |
DeLesley Hutchins | 4e4c157 | 2012-08-31 21:57:32 +0000 | [diff] [blame] | 1483 | if (Mutex.shouldIgnore()) |
| 1484 | return; |
| 1485 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1486 | if (FSet.findLock(FactMan, Mutex)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1487 | Handler.handleDoubleLock(Mutex.toString(), LDat.AcquireLoc); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1488 | } else { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1489 | FSet.addLock(FactMan, Mutex, LDat); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1490 | } |
| 1491 | } |
| 1492 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1493 | |
| 1494 | /// \brief Remove a lock from the lockset, warning if the lock is not there. |
Ted Kremenek | ad0fe03 | 2012-08-22 23:50:41 +0000 | [diff] [blame] | 1495 | /// \param Mutex The lock expression corresponding to the lock to be removed |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1496 | /// \param UnlockLoc The source location of the unlock (only used in error msg) |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1497 | void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1498 | const SExpr &Mutex, |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1499 | SourceLocation UnlockLoc, |
| 1500 | bool FullyRemove) { |
DeLesley Hutchins | 4e4c157 | 2012-08-31 21:57:32 +0000 | [diff] [blame] | 1501 | if (Mutex.shouldIgnore()) |
| 1502 | return; |
| 1503 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1504 | const LockData *LDat = FSet.findLock(FactMan, Mutex); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1505 | if (!LDat) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1506 | Handler.handleUnmatchedUnlock(Mutex.toString(), UnlockLoc); |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1507 | return; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1508 | } |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1509 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1510 | if (LDat->UnderlyingMutex.isValid()) { |
| 1511 | // This is scoped lockable object, which manages the real mutex. |
| 1512 | if (FullyRemove) { |
| 1513 | // We're destroying the managing object. |
| 1514 | // Remove the underlying mutex if it exists; but don't warn. |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1515 | if (FSet.findLock(FactMan, LDat->UnderlyingMutex)) |
| 1516 | FSet.removeLock(FactMan, LDat->UnderlyingMutex); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1517 | } else { |
| 1518 | // We're releasing the underlying mutex, but not destroying the |
| 1519 | // managing object. Warn on dual release. |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1520 | if (!FSet.findLock(FactMan, LDat->UnderlyingMutex)) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1521 | Handler.handleUnmatchedUnlock(LDat->UnderlyingMutex.toString(), |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1522 | UnlockLoc); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1523 | } |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1524 | FSet.removeLock(FactMan, LDat->UnderlyingMutex); |
| 1525 | return; |
DeLesley Hutchins | c99a5d8 | 2012-06-28 22:42:48 +0000 | [diff] [blame] | 1526 | } |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1527 | } |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1528 | FSet.removeLock(FactMan, Mutex); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1529 | } |
| 1530 | |
DeLesley Hutchins | c99a5d8 | 2012-06-28 22:42:48 +0000 | [diff] [blame] | 1531 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1532 | /// \brief Extract the list of mutexIDs from the attribute on an expression, |
| 1533 | /// and push them onto Mtxs, discarding any duplicates. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1534 | template <typename AttrType> |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1535 | void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 1536 | Expr *Exp, const NamedDecl *D, |
| 1537 | VarDecl *SelfDecl) { |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1538 | typedef typename AttrType::args_iterator iterator_type; |
| 1539 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1540 | if (Attr->args_size() == 0) { |
| 1541 | // The mutex held is the "this" object. |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 1542 | SExpr Mu(0, Exp, D, SelfDecl); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1543 | if (!Mu.isValid()) |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1544 | SExpr::warnInvalidLock(Handler, 0, Exp, D); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1545 | else |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1546 | Mtxs.push_back_nodup(Mu); |
| 1547 | return; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1548 | } |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1549 | |
| 1550 | for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 1551 | SExpr Mu(*I, Exp, D, SelfDecl); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1552 | if (!Mu.isValid()) |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1553 | SExpr::warnInvalidLock(Handler, *I, Exp, D); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1554 | else |
| 1555 | Mtxs.push_back_nodup(Mu); |
| 1556 | } |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1557 | } |
| 1558 | |
| 1559 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1560 | /// \brief Extract the list of mutexIDs from a trylock attribute. If the |
| 1561 | /// trylock applies to the given edge, then push them onto Mtxs, discarding |
| 1562 | /// any duplicates. |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1563 | template <class AttrType> |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1564 | void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, |
| 1565 | Expr *Exp, const NamedDecl *D, |
| 1566 | const CFGBlock *PredBlock, |
| 1567 | const CFGBlock *CurrBlock, |
| 1568 | Expr *BrE, bool Neg) { |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1569 | // Find out which branch has the lock |
| 1570 | bool branch = 0; |
| 1571 | if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) { |
| 1572 | branch = BLE->getValue(); |
| 1573 | } |
| 1574 | else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) { |
| 1575 | branch = ILE->getValue().getBoolValue(); |
| 1576 | } |
| 1577 | int branchnum = branch ? 0 : 1; |
| 1578 | if (Neg) branchnum = !branchnum; |
| 1579 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1580 | // If we've taken the trylock branch, then add the lock |
| 1581 | int i = 0; |
| 1582 | for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), |
| 1583 | SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { |
| 1584 | if (*SI == CurrBlock && i == branchnum) { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1585 | getMutexIDs(Mtxs, Attr, Exp, D); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1586 | } |
| 1587 | } |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1588 | } |
| 1589 | |
| 1590 | |
DeLesley Hutchins | 1310611 | 2012-07-10 21:47:55 +0000 | [diff] [blame] | 1591 | bool getStaticBooleanValue(Expr* E, bool& TCond) { |
| 1592 | if (isa<CXXNullPtrLiteralExpr>(E) || isa<GNUNullExpr>(E)) { |
| 1593 | TCond = false; |
| 1594 | return true; |
| 1595 | } else if (CXXBoolLiteralExpr *BLE = dyn_cast<CXXBoolLiteralExpr>(E)) { |
| 1596 | TCond = BLE->getValue(); |
| 1597 | return true; |
| 1598 | } else if (IntegerLiteral *ILE = dyn_cast<IntegerLiteral>(E)) { |
| 1599 | TCond = ILE->getValue().getBoolValue(); |
| 1600 | return true; |
| 1601 | } else if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E)) { |
| 1602 | return getStaticBooleanValue(CE->getSubExpr(), TCond); |
| 1603 | } |
| 1604 | return false; |
| 1605 | } |
| 1606 | |
| 1607 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1608 | // If Cond can be traced back to a function call, return the call expression. |
| 1609 | // The negate variable should be called with false, and will be set to true |
| 1610 | // if the function call is negated, e.g. if (!mu.tryLock(...)) |
| 1611 | const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond, |
| 1612 | LocalVarContext C, |
| 1613 | bool &Negate) { |
| 1614 | if (!Cond) |
| 1615 | return 0; |
| 1616 | |
| 1617 | if (const CallExpr *CallExp = dyn_cast<CallExpr>(Cond)) { |
| 1618 | return CallExp; |
| 1619 | } |
DeLesley Hutchins | 1310611 | 2012-07-10 21:47:55 +0000 | [diff] [blame] | 1620 | else if (const ParenExpr *PE = dyn_cast<ParenExpr>(Cond)) { |
| 1621 | return getTrylockCallExpr(PE->getSubExpr(), C, Negate); |
| 1622 | } |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1623 | else if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Cond)) { |
| 1624 | return getTrylockCallExpr(CE->getSubExpr(), C, Negate); |
| 1625 | } |
DeLesley Hutchins | fd0f11c | 2012-09-05 20:01:16 +0000 | [diff] [blame] | 1626 | else if (const ExprWithCleanups* EWC = dyn_cast<ExprWithCleanups>(Cond)) { |
| 1627 | return getTrylockCallExpr(EWC->getSubExpr(), C, Negate); |
| 1628 | } |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1629 | else if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Cond)) { |
| 1630 | const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C); |
| 1631 | return getTrylockCallExpr(E, C, Negate); |
| 1632 | } |
| 1633 | else if (const UnaryOperator *UOP = dyn_cast<UnaryOperator>(Cond)) { |
| 1634 | if (UOP->getOpcode() == UO_LNot) { |
| 1635 | Negate = !Negate; |
| 1636 | return getTrylockCallExpr(UOP->getSubExpr(), C, Negate); |
| 1637 | } |
DeLesley Hutchins | 1310611 | 2012-07-10 21:47:55 +0000 | [diff] [blame] | 1638 | return 0; |
| 1639 | } |
| 1640 | else if (const BinaryOperator *BOP = dyn_cast<BinaryOperator>(Cond)) { |
| 1641 | if (BOP->getOpcode() == BO_EQ || BOP->getOpcode() == BO_NE) { |
| 1642 | if (BOP->getOpcode() == BO_NE) |
| 1643 | Negate = !Negate; |
| 1644 | |
| 1645 | bool TCond = false; |
| 1646 | if (getStaticBooleanValue(BOP->getRHS(), TCond)) { |
| 1647 | if (!TCond) Negate = !Negate; |
| 1648 | return getTrylockCallExpr(BOP->getLHS(), C, Negate); |
| 1649 | } |
| 1650 | else if (getStaticBooleanValue(BOP->getLHS(), TCond)) { |
| 1651 | if (!TCond) Negate = !Negate; |
| 1652 | return getTrylockCallExpr(BOP->getRHS(), C, Negate); |
| 1653 | } |
| 1654 | return 0; |
| 1655 | } |
| 1656 | return 0; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1657 | } |
| 1658 | // FIXME -- handle && and || as well. |
DeLesley Hutchins | 1310611 | 2012-07-10 21:47:55 +0000 | [diff] [blame] | 1659 | return 0; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1660 | } |
| 1661 | |
| 1662 | |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 1663 | /// \brief Find the lockset that holds on the edge between PredBlock |
| 1664 | /// and CurrBlock. The edge set is the exit set of PredBlock (passed |
| 1665 | /// as the ExitSet parameter) plus any trylocks, which are conditionally held. |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1666 | void ThreadSafetyAnalyzer::getEdgeLockset(FactSet& Result, |
| 1667 | const FactSet &ExitSet, |
| 1668 | const CFGBlock *PredBlock, |
| 1669 | const CFGBlock *CurrBlock) { |
| 1670 | Result = ExitSet; |
| 1671 | |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 1672 | if (!PredBlock->getTerminatorCondition()) |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1673 | return; |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 1674 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1675 | bool Negate = false; |
| 1676 | const Stmt *Cond = PredBlock->getTerminatorCondition(); |
| 1677 | const CFGBlockInfo *PredBlockInfo = &BlockInfo[PredBlock->getBlockID()]; |
| 1678 | const LocalVarContext &LVarCtx = PredBlockInfo->ExitContext; |
| 1679 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1680 | CallExpr *Exp = |
| 1681 | const_cast<CallExpr*>(getTrylockCallExpr(Cond, LVarCtx, Negate)); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1682 | if (!Exp) |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1683 | return; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1684 | |
| 1685 | NamedDecl *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); |
| 1686 | if(!FunDecl || !FunDecl->hasAttrs()) |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1687 | return; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1688 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1689 | |
| 1690 | MutexIDList ExclusiveLocksToAdd; |
| 1691 | MutexIDList SharedLocksToAdd; |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1692 | |
| 1693 | // If the condition is a call to a Trylock function, then grab the attributes |
| 1694 | AttrVec &ArgAttrs = FunDecl->getAttrs(); |
| 1695 | for (unsigned i = 0; i < ArgAttrs.size(); ++i) { |
| 1696 | Attr *Attr = ArgAttrs[i]; |
| 1697 | switch (Attr->getKind()) { |
| 1698 | case attr::ExclusiveTrylockFunction: { |
| 1699 | ExclusiveTrylockFunctionAttr *A = |
| 1700 | cast<ExclusiveTrylockFunctionAttr>(Attr); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1701 | getMutexIDs(ExclusiveLocksToAdd, A, Exp, FunDecl, |
| 1702 | PredBlock, CurrBlock, A->getSuccessValue(), Negate); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1703 | break; |
| 1704 | } |
| 1705 | case attr::SharedTrylockFunction: { |
| 1706 | SharedTrylockFunctionAttr *A = |
| 1707 | cast<SharedTrylockFunctionAttr>(Attr); |
DeLesley Hutchins | 60ff198 | 2012-09-20 23:14:43 +0000 | [diff] [blame] | 1708 | getMutexIDs(SharedLocksToAdd, A, Exp, FunDecl, |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1709 | PredBlock, CurrBlock, A->getSuccessValue(), Negate); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1710 | break; |
| 1711 | } |
| 1712 | default: |
| 1713 | break; |
| 1714 | } |
| 1715 | } |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1716 | |
| 1717 | // Add and remove locks. |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1718 | SourceLocation Loc = Exp->getExprLoc(); |
| 1719 | for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1720 | addLock(Result, ExclusiveLocksToAdd[i], |
| 1721 | LockData(Loc, LK_Exclusive)); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1722 | } |
| 1723 | for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1724 | addLock(Result, SharedLocksToAdd[i], |
| 1725 | LockData(Loc, LK_Shared)); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1726 | } |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1727 | } |
| 1728 | |
| 1729 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1730 | /// \brief We use this class to visit different types of expressions in |
| 1731 | /// CFGBlocks, and build up the lockset. |
| 1732 | /// An expression may cause us to add or remove locks from the lockset, or else |
| 1733 | /// output error messages related to missing locks. |
| 1734 | /// FIXME: In future, we may be able to not inherit from a visitor. |
| 1735 | class BuildLockset : public StmtVisitor<BuildLockset> { |
DeLesley Hutchins | f1ac637 | 2011-10-21 18:10:14 +0000 | [diff] [blame] | 1736 | friend class ThreadSafetyAnalyzer; |
| 1737 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1738 | ThreadSafetyAnalyzer *Analyzer; |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1739 | FactSet FSet; |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1740 | LocalVariableMap::Context LVarCtx; |
| 1741 | unsigned CtxIndex; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1742 | |
| 1743 | // Helper functions |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1744 | const ValueDecl *getValueDecl(const Expr *Exp); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1745 | |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1746 | void warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, AccessKind AK, |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1747 | Expr *MutexExp, ProtectedOperationKind POK); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1748 | void warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, Expr *MutexExp); |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1749 | |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1750 | void checkAccess(const Expr *Exp, AccessKind AK); |
| 1751 | void checkPtAccess(const Expr *Exp, AccessKind AK); |
| 1752 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1753 | void handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD = 0); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1754 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1755 | public: |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1756 | BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info) |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1757 | : StmtVisitor<BuildLockset>(), |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1758 | Analyzer(Anlzr), |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1759 | FSet(Info.EntrySet), |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 1760 | LVarCtx(Info.EntryContext), |
| 1761 | CtxIndex(Info.EntryIndex) |
| 1762 | {} |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1763 | |
| 1764 | void VisitUnaryOperator(UnaryOperator *UO); |
| 1765 | void VisitBinaryOperator(BinaryOperator *BO); |
| 1766 | void VisitCastExpr(CastExpr *CE); |
DeLesley Hutchins | df49782 | 2011-12-29 00:56:48 +0000 | [diff] [blame] | 1767 | void VisitCallExpr(CallExpr *Exp); |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 1768 | void VisitCXXConstructExpr(CXXConstructExpr *Exp); |
DeLesley Hutchins | 1fa3c06 | 2011-12-08 20:23:06 +0000 | [diff] [blame] | 1769 | void VisitDeclStmt(DeclStmt *S); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1770 | }; |
| 1771 | |
DeLesley Hutchins | f1ac637 | 2011-10-21 18:10:14 +0000 | [diff] [blame] | 1772 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1773 | /// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1774 | const ValueDecl *BuildLockset::getValueDecl(const Expr *Exp) { |
| 1775 | if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Exp)) |
| 1776 | return getValueDecl(CE->getSubExpr()); |
| 1777 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1778 | if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp)) |
| 1779 | return DR->getDecl(); |
| 1780 | |
| 1781 | if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) |
| 1782 | return ME->getMemberDecl(); |
| 1783 | |
| 1784 | return 0; |
| 1785 | } |
| 1786 | |
| 1787 | /// \brief Warn if the LSet does not contain a lock sufficient to protect access |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 1788 | /// of at least the passed in AccessKind. |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1789 | void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1790 | AccessKind AK, Expr *MutexExp, |
| 1791 | ProtectedOperationKind POK) { |
| 1792 | LockKind LK = getLockKindFromAccessKind(AK); |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 1793 | |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1794 | SExpr Mutex(MutexExp, Exp, D); |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 1795 | if (!Mutex.isValid()) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1796 | SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D); |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 1797 | return; |
| 1798 | } else if (Mutex.shouldIgnore()) { |
| 1799 | return; |
| 1800 | } |
| 1801 | |
| 1802 | LockData* LDat = FSet.findLockUniv(Analyzer->FactMan, Mutex); |
DeLesley Hutchins | 3f0ec52 | 2012-09-10 19:58:23 +0000 | [diff] [blame] | 1803 | bool NoError = true; |
| 1804 | if (!LDat) { |
| 1805 | // No exact match found. Look for a partial match. |
| 1806 | FactEntry* FEntry = FSet.findPartialMatch(Analyzer->FactMan, Mutex); |
| 1807 | if (FEntry) { |
| 1808 | // Warn that there's no precise match. |
| 1809 | LDat = &FEntry->LDat; |
| 1810 | std::string PartMatchStr = FEntry->MutID.toString(); |
| 1811 | StringRef PartMatchName(PartMatchStr); |
| 1812 | Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, |
| 1813 | Exp->getExprLoc(), &PartMatchName); |
| 1814 | } else { |
| 1815 | // Warn that there's no match at all. |
| 1816 | Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, |
| 1817 | Exp->getExprLoc()); |
| 1818 | } |
| 1819 | NoError = false; |
| 1820 | } |
| 1821 | // Make sure the mutex we found is the right kind. |
| 1822 | if (NoError && LDat && !LDat->isAtLeast(LK)) |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 1823 | Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1824 | Exp->getExprLoc()); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1825 | } |
| 1826 | |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 1827 | /// \brief Warn if the LSet contains the given lock. |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1828 | void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr* Exp, |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 1829 | Expr *MutexExp) { |
| 1830 | SExpr Mutex(MutexExp, Exp, D); |
| 1831 | if (!Mutex.isValid()) { |
| 1832 | SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D); |
| 1833 | return; |
| 1834 | } |
| 1835 | |
| 1836 | LockData* LDat = FSet.findLock(Analyzer->FactMan, Mutex); |
DeLesley Hutchins | 5b280f2 | 2012-09-19 19:18:29 +0000 | [diff] [blame] | 1837 | if (LDat) { |
| 1838 | std::string DeclName = D->getNameAsString(); |
| 1839 | StringRef DeclNameSR (DeclName); |
| 1840 | Analyzer->Handler.handleFunExcludesLock(DeclNameSR, Mutex.toString(), |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 1841 | Exp->getExprLoc()); |
DeLesley Hutchins | 5b280f2 | 2012-09-19 19:18:29 +0000 | [diff] [blame] | 1842 | } |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 1843 | } |
| 1844 | |
| 1845 | |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1846 | /// \brief Checks guarded_by and pt_guarded_by attributes. |
| 1847 | /// Whenever we identify an access (read or write) to a DeclRefExpr that is |
| 1848 | /// marked with guarded_by, we must ensure the appropriate mutexes are held. |
| 1849 | /// Similarly, we check if the access is to an expression that dereferences |
| 1850 | /// a pointer marked with pt_guarded_by. |
| 1851 | void BuildLockset::checkAccess(const Expr *Exp, AccessKind AK) { |
| 1852 | Exp = Exp->IgnoreParenCasts(); |
| 1853 | |
| 1854 | if (const UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp)) { |
| 1855 | // For dereferences |
| 1856 | if (UO->getOpcode() == clang::UO_Deref) |
| 1857 | checkPtAccess(UO->getSubExpr(), AK); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1858 | return; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1859 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1860 | |
DeLesley Hutchins | 93699d2 | 2012-12-08 03:46:30 +0000 | [diff] [blame] | 1861 | if (Analyzer->Handler.issueBetaWarnings()) { |
| 1862 | if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { |
| 1863 | if (ME->isArrow()) |
| 1864 | checkPtAccess(ME->getBase(), AK); |
| 1865 | else |
| 1866 | checkAccess(ME->getBase(), AK); |
| 1867 | } |
| 1868 | } |
| 1869 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1870 | const ValueDecl *D = getValueDecl(Exp); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1871 | if (!D || !D->hasAttrs()) |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1872 | return; |
| 1873 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1874 | if (D->getAttr<GuardedVarAttr>() && FSet.isEmpty()) |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 1875 | Analyzer->Handler.handleNoMutexHeld(D, POK_VarAccess, AK, |
| 1876 | Exp->getExprLoc()); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1877 | |
| 1878 | const AttrVec &ArgAttrs = D->getAttrs(); |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1879 | for (unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1880 | if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i])) |
| 1881 | warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess); |
| 1882 | } |
| 1883 | |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 1884 | /// \brief Checks pt_guarded_by and pt_guarded_var attributes. |
| 1885 | void BuildLockset::checkPtAccess(const Expr *Exp, AccessKind AK) { |
| 1886 | Exp = Exp->IgnoreParenCasts(); |
| 1887 | |
| 1888 | const ValueDecl *D = getValueDecl(Exp); |
| 1889 | if (!D || !D->hasAttrs()) |
| 1890 | return; |
| 1891 | |
| 1892 | if (D->getAttr<PtGuardedVarAttr>() && FSet.isEmpty()) |
| 1893 | Analyzer->Handler.handleNoMutexHeld(D, POK_VarDereference, AK, |
| 1894 | Exp->getExprLoc()); |
| 1895 | |
| 1896 | const AttrVec &ArgAttrs = D->getAttrs(); |
| 1897 | for (unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) |
| 1898 | if (PtGuardedByAttr *GBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i])) |
| 1899 | warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarDereference); |
| 1900 | } |
| 1901 | |
| 1902 | |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 1903 | /// \brief Process a function call, method call, constructor call, |
| 1904 | /// or destructor call. This involves looking at the attributes on the |
| 1905 | /// corresponding function/method/constructor/destructor, issuing warnings, |
| 1906 | /// and updating the locksets accordingly. |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1907 | /// |
| 1908 | /// FIXME: For classes annotated with one of the guarded annotations, we need |
| 1909 | /// to treat const method calls as reads and non-const method calls as writes, |
| 1910 | /// and check that the appropriate locks are held. Non-const method calls with |
| 1911 | /// the same signature as const method calls can be also treated as reads. |
| 1912 | /// |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1913 | void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { |
| 1914 | const AttrVec &ArgAttrs = D->getAttrs(); |
| 1915 | MutexIDList ExclusiveLocksToAdd; |
| 1916 | MutexIDList SharedLocksToAdd; |
| 1917 | MutexIDList LocksToRemove; |
| 1918 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1919 | for(unsigned i = 0; i < ArgAttrs.size(); ++i) { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1920 | Attr *At = const_cast<Attr*>(ArgAttrs[i]); |
| 1921 | switch (At->getKind()) { |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1922 | // When we encounter an exclusive lock function, we need to add the lock |
| 1923 | // to our lockset with kind exclusive. |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 1924 | case attr::ExclusiveLockFunction: { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1925 | ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(At); |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 1926 | Analyzer->getMutexIDs(ExclusiveLocksToAdd, A, Exp, D, VD); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1927 | break; |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 1928 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1929 | |
| 1930 | // When we encounter a shared lock function, we need to add the lock |
| 1931 | // to our lockset with kind shared. |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 1932 | case attr::SharedLockFunction: { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1933 | SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(At); |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 1934 | Analyzer->getMutexIDs(SharedLocksToAdd, A, Exp, D, VD); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1935 | break; |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 1936 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1937 | |
| 1938 | // When we encounter an unlock function, we need to remove unlocked |
| 1939 | // mutexes from the lockset, and flag a warning if they are not there. |
| 1940 | case attr::UnlockFunction: { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1941 | UnlockFunctionAttr *A = cast<UnlockFunctionAttr>(At); |
DeLesley Hutchins | ef2388b | 2012-10-05 22:38:19 +0000 | [diff] [blame] | 1942 | Analyzer->getMutexIDs(LocksToRemove, A, Exp, D, VD); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1943 | break; |
| 1944 | } |
| 1945 | |
| 1946 | case attr::ExclusiveLocksRequired: { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1947 | ExclusiveLocksRequiredAttr *A = cast<ExclusiveLocksRequiredAttr>(At); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1948 | |
| 1949 | for (ExclusiveLocksRequiredAttr::args_iterator |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1950 | I = A->args_begin(), E = A->args_end(); I != E; ++I) |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1951 | warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall); |
| 1952 | break; |
| 1953 | } |
| 1954 | |
| 1955 | case attr::SharedLocksRequired: { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1956 | SharedLocksRequiredAttr *A = cast<SharedLocksRequiredAttr>(At); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1957 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1958 | for (SharedLocksRequiredAttr::args_iterator I = A->args_begin(), |
| 1959 | E = A->args_end(); I != E; ++I) |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1960 | warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall); |
| 1961 | break; |
| 1962 | } |
| 1963 | |
| 1964 | case attr::LocksExcluded: { |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1965 | LocksExcludedAttr *A = cast<LocksExcludedAttr>(At); |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 1966 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1967 | for (LocksExcludedAttr::args_iterator I = A->args_begin(), |
| 1968 | E = A->args_end(); I != E; ++I) { |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 1969 | warnIfMutexHeld(D, Exp, *I); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1970 | } |
| 1971 | break; |
| 1972 | } |
| 1973 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 1974 | // Ignore other (non thread-safety) attributes |
| 1975 | default: |
| 1976 | break; |
| 1977 | } |
| 1978 | } |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1979 | |
| 1980 | // Figure out if we're calling the constructor of scoped lockable class |
| 1981 | bool isScopedVar = false; |
| 1982 | if (VD) { |
| 1983 | if (const CXXConstructorDecl *CD = dyn_cast<const CXXConstructorDecl>(D)) { |
| 1984 | const CXXRecordDecl* PD = CD->getParent(); |
| 1985 | if (PD && PD->getAttr<ScopedLockableAttr>()) |
| 1986 | isScopedVar = true; |
| 1987 | } |
| 1988 | } |
| 1989 | |
| 1990 | // Add locks. |
| 1991 | SourceLocation Loc = Exp->getExprLoc(); |
| 1992 | for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1993 | Analyzer->addLock(FSet, ExclusiveLocksToAdd[i], |
| 1994 | LockData(Loc, LK_Exclusive, isScopedVar)); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1995 | } |
| 1996 | for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 1997 | Analyzer->addLock(FSet, SharedLocksToAdd[i], |
| 1998 | LockData(Loc, LK_Shared, isScopedVar)); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 1999 | } |
| 2000 | |
| 2001 | // Add the managing object as a dummy mutex, mapped to the underlying mutex. |
| 2002 | // FIXME -- this doesn't work if we acquire multiple locks. |
| 2003 | if (isScopedVar) { |
| 2004 | SourceLocation MLoc = VD->getLocation(); |
| 2005 | DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation()); |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 2006 | SExpr SMutex(&DRE, 0, 0); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2007 | |
| 2008 | for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2009 | Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Exclusive, |
| 2010 | ExclusiveLocksToAdd[i])); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2011 | } |
| 2012 | for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2013 | Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Shared, |
| 2014 | SharedLocksToAdd[i])); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2015 | } |
| 2016 | } |
| 2017 | |
| 2018 | // Remove locks. |
| 2019 | // FIXME -- should only fully remove if the attribute refers to 'this'. |
| 2020 | bool Dtor = isa<CXXDestructorDecl>(D); |
| 2021 | for (unsigned i=0,n=LocksToRemove.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2022 | Analyzer->removeLock(FSet, LocksToRemove[i], Loc, Dtor); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2023 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2024 | } |
| 2025 | |
DeLesley Hutchins | b4fa418 | 2012-01-06 19:16:50 +0000 | [diff] [blame] | 2026 | |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 2027 | /// \brief For unary operations which read and write a variable, we need to |
| 2028 | /// check whether we hold any required mutexes. Reads are checked in |
| 2029 | /// VisitCastExpr. |
| 2030 | void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { |
| 2031 | switch (UO->getOpcode()) { |
| 2032 | case clang::UO_PostDec: |
| 2033 | case clang::UO_PostInc: |
| 2034 | case clang::UO_PreDec: |
| 2035 | case clang::UO_PreInc: { |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 2036 | checkAccess(UO->getSubExpr(), AK_Written); |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 2037 | break; |
| 2038 | } |
| 2039 | default: |
| 2040 | break; |
| 2041 | } |
| 2042 | } |
| 2043 | |
| 2044 | /// For binary operations which assign to a variable (writes), we need to check |
| 2045 | /// whether we hold any required mutexes. |
| 2046 | /// FIXME: Deal with non-primitive types. |
| 2047 | void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { |
| 2048 | if (!BO->isAssignmentOp()) |
| 2049 | return; |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2050 | |
| 2051 | // adjust the context |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 2052 | LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2053 | |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 2054 | checkAccess(BO->getLHS(), AK_Written); |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 2055 | } |
| 2056 | |
| 2057 | /// Whenever we do an LValue to Rvalue cast, we are reading a variable and |
| 2058 | /// need to ensure we hold any required mutexes. |
| 2059 | /// FIXME: Deal with non-primitive types. |
| 2060 | void BuildLockset::VisitCastExpr(CastExpr *CE) { |
| 2061 | if (CE->getCastKind() != CK_LValueToRValue) |
| 2062 | return; |
DeLesley Hutchins | 47715cc | 2012-12-05 00:52:33 +0000 | [diff] [blame] | 2063 | checkAccess(CE->getSubExpr(), AK_Read); |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 2064 | } |
| 2065 | |
| 2066 | |
DeLesley Hutchins | df49782 | 2011-12-29 00:56:48 +0000 | [diff] [blame] | 2067 | void BuildLockset::VisitCallExpr(CallExpr *Exp) { |
DeLesley Hutchins | 91e2061 | 2012-12-05 01:20:45 +0000 | [diff] [blame] | 2068 | if (Analyzer->Handler.issueBetaWarnings()) { |
| 2069 | if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(Exp)) { |
| 2070 | MemberExpr *ME = dyn_cast<MemberExpr>(CE->getCallee()); |
| 2071 | // ME can be null when calling a method pointer |
| 2072 | CXXMethodDecl *MD = CE->getMethodDecl(); |
| 2073 | |
| 2074 | if (ME && MD) { |
| 2075 | if (ME->isArrow()) { |
| 2076 | if (MD->isConst()) { |
| 2077 | checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); |
| 2078 | } else { // FIXME -- should be AK_Written |
| 2079 | checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); |
| 2080 | } |
| 2081 | } else { |
| 2082 | if (MD->isConst()) |
| 2083 | checkAccess(CE->getImplicitObjectArgument(), AK_Read); |
| 2084 | else // FIXME -- should be AK_Written |
| 2085 | checkAccess(CE->getImplicitObjectArgument(), AK_Read); |
| 2086 | } |
| 2087 | } |
| 2088 | } else if (CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(Exp)) { |
| 2089 | switch (OE->getOperator()) { |
| 2090 | case OO_Equal: { |
| 2091 | const Expr *Target = OE->getArg(0); |
| 2092 | const Expr *Source = OE->getArg(1); |
| 2093 | checkAccess(Target, AK_Written); |
| 2094 | checkAccess(Source, AK_Read); |
| 2095 | break; |
| 2096 | } |
| 2097 | default: { |
| 2098 | const Expr *Source = OE->getArg(0); |
| 2099 | checkAccess(Source, AK_Read); |
| 2100 | break; |
| 2101 | } |
| 2102 | } |
| 2103 | } |
| 2104 | } |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 2105 | NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); |
| 2106 | if(!D || !D->hasAttrs()) |
| 2107 | return; |
| 2108 | handleCall(Exp, D); |
| 2109 | } |
| 2110 | |
| 2111 | void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) { |
DeLesley Hutchins | 91e2061 | 2012-12-05 01:20:45 +0000 | [diff] [blame] | 2112 | if (Analyzer->Handler.issueBetaWarnings()) { |
| 2113 | const CXXConstructorDecl *D = Exp->getConstructor(); |
| 2114 | if (D && D->isCopyConstructor()) { |
| 2115 | const Expr* Source = Exp->getArg(0); |
| 2116 | checkAccess(Source, AK_Read); |
| 2117 | } |
| 2118 | } |
DeLesley Hutchins | 1fa3c06 | 2011-12-08 20:23:06 +0000 | [diff] [blame] | 2119 | // FIXME -- only handles constructors in DeclStmt below. |
| 2120 | } |
| 2121 | |
| 2122 | void BuildLockset::VisitDeclStmt(DeclStmt *S) { |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2123 | // adjust the context |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 2124 | LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2125 | |
DeLesley Hutchins | 1fa3c06 | 2011-12-08 20:23:06 +0000 | [diff] [blame] | 2126 | DeclGroupRef DGrp = S->getDeclGroup(); |
| 2127 | for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { |
| 2128 | Decl *D = *I; |
| 2129 | if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) { |
| 2130 | Expr *E = VD->getInit(); |
DeLesley Hutchins | 9d6e7f3 | 2012-07-03 18:25:56 +0000 | [diff] [blame] | 2131 | // handle constructors that involve temporaries |
| 2132 | if (ExprWithCleanups *EWC = dyn_cast_or_null<ExprWithCleanups>(E)) |
| 2133 | E = EWC->getSubExpr(); |
| 2134 | |
DeLesley Hutchins | 1fa3c06 | 2011-12-08 20:23:06 +0000 | [diff] [blame] | 2135 | if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) { |
| 2136 | NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); |
| 2137 | if (!CtorD || !CtorD->hasAttrs()) |
| 2138 | return; |
| 2139 | handleCall(CE, CtorD, VD); |
| 2140 | } |
| 2141 | } |
| 2142 | } |
DeLesley Hutchins | e0eaa85 | 2011-10-21 18:06:53 +0000 | [diff] [blame] | 2143 | } |
| 2144 | |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 2145 | |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2146 | |
Caitlin Sadowski | 4e4bc75 | 2011-09-15 17:25:19 +0000 | [diff] [blame] | 2147 | /// \brief Compute the intersection of two locksets and issue warnings for any |
| 2148 | /// locks in the symmetric difference. |
| 2149 | /// |
| 2150 | /// This function is used at a merge point in the CFG when comparing the lockset |
| 2151 | /// of each branch being merged. For example, given the following sequence: |
| 2152 | /// A; if () then B; else C; D; we need to check that the lockset after B and C |
| 2153 | /// are the same. In the event of a difference, we use the intersection of these |
| 2154 | /// two locksets at the start of D. |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2155 | /// |
Ted Kremenek | ad0fe03 | 2012-08-22 23:50:41 +0000 | [diff] [blame] | 2156 | /// \param FSet1 The first lockset. |
| 2157 | /// \param FSet2 The second lockset. |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2158 | /// \param JoinLoc The location of the join point for error reporting |
DeLesley Hutchins | 879a433 | 2012-07-02 22:16:54 +0000 | [diff] [blame] | 2159 | /// \param LEK1 The error message to report if a mutex is missing from LSet1 |
| 2160 | /// \param LEK2 The error message to report if a mutex is missing from Lset2 |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2161 | void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1, |
| 2162 | const FactSet &FSet2, |
| 2163 | SourceLocation JoinLoc, |
| 2164 | LockErrorKind LEK1, |
| 2165 | LockErrorKind LEK2, |
| 2166 | bool Modify) { |
| 2167 | FactSet FSet1Orig = FSet1; |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2168 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2169 | for (FactSet::const_iterator I = FSet2.begin(), E = FSet2.end(); |
| 2170 | I != E; ++I) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 2171 | const SExpr &FSet2Mutex = FactMan[*I].MutID; |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2172 | const LockData &LDat2 = FactMan[*I].LDat; |
| 2173 | |
| 2174 | if (const LockData *LDat1 = FSet1.findLock(FactMan, FSet2Mutex)) { |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2175 | if (LDat1->LKind != LDat2.LKind) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 2176 | Handler.handleExclusiveAndShared(FSet2Mutex.toString(), |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2177 | LDat2.AcquireLoc, |
| 2178 | LDat1->AcquireLoc); |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2179 | if (Modify && LDat1->LKind != LK_Exclusive) { |
| 2180 | FSet1.removeLock(FactMan, FSet2Mutex); |
| 2181 | FSet1.addLock(FactMan, FSet2Mutex, LDat2); |
| 2182 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2183 | } |
| 2184 | } else { |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2185 | if (LDat2.UnderlyingMutex.isValid()) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2186 | if (FSet2.findLock(FactMan, LDat2.UnderlyingMutex)) { |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2187 | // If this is a scoped lock that manages another mutex, and if the |
| 2188 | // underlying mutex is still held, then warn about the underlying |
| 2189 | // mutex. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 2190 | Handler.handleMutexHeldEndOfScope(LDat2.UnderlyingMutex.toString(), |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2191 | LDat2.AcquireLoc, |
| 2192 | JoinLoc, LEK1); |
| 2193 | } |
| 2194 | } |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 2195 | else if (!LDat2.Managed && !FSet2Mutex.isUniversal()) |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 2196 | Handler.handleMutexHeldEndOfScope(FSet2Mutex.toString(), |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2197 | LDat2.AcquireLoc, |
DeLesley Hutchins | 879a433 | 2012-07-02 22:16:54 +0000 | [diff] [blame] | 2198 | JoinLoc, LEK1); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2199 | } |
| 2200 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2201 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2202 | for (FactSet::const_iterator I = FSet1.begin(), E = FSet1.end(); |
| 2203 | I != E; ++I) { |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 2204 | const SExpr &FSet1Mutex = FactMan[*I].MutID; |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2205 | const LockData &LDat1 = FactMan[*I].LDat; |
DeLesley Hutchins | c99a5d8 | 2012-06-28 22:42:48 +0000 | [diff] [blame] | 2206 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2207 | if (!FSet2.findLock(FactMan, FSet1Mutex)) { |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2208 | if (LDat1.UnderlyingMutex.isValid()) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2209 | if (FSet1Orig.findLock(FactMan, LDat1.UnderlyingMutex)) { |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2210 | // If this is a scoped lock that manages another mutex, and if the |
| 2211 | // underlying mutex is still held, then warn about the underlying |
| 2212 | // mutex. |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 2213 | Handler.handleMutexHeldEndOfScope(LDat1.UnderlyingMutex.toString(), |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2214 | LDat1.AcquireLoc, |
| 2215 | JoinLoc, LEK1); |
| 2216 | } |
| 2217 | } |
DeLesley Hutchins | 0b4db3e | 2012-09-07 17:34:53 +0000 | [diff] [blame] | 2218 | else if (!LDat1.Managed && !FSet1Mutex.isUniversal()) |
DeLesley Hutchins | a74b715 | 2012-08-10 20:19:55 +0000 | [diff] [blame] | 2219 | Handler.handleMutexHeldEndOfScope(FSet1Mutex.toString(), |
DeLesley Hutchins | bbe3341 | 2012-07-02 22:26:29 +0000 | [diff] [blame] | 2220 | LDat1.AcquireLoc, |
DeLesley Hutchins | 879a433 | 2012-07-02 22:16:54 +0000 | [diff] [blame] | 2221 | JoinLoc, LEK2); |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2222 | if (Modify) |
| 2223 | FSet1.removeLock(FactMan, FSet1Mutex); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2224 | } |
| 2225 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2226 | } |
| 2227 | |
Caitlin Sadowski | cb96751 | 2011-09-15 17:43:08 +0000 | [diff] [blame] | 2228 | |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2229 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2230 | /// \brief Check a function's CFG for thread-safety violations. |
| 2231 | /// |
| 2232 | /// We traverse the blocks in the CFG, compute the set of mutexes that are held |
| 2233 | /// at the end of each block, and issue warnings for thread safety violations. |
| 2234 | /// Each block in the CFG is traversed exactly once. |
Ted Kremenek | 1d26f48 | 2011-10-24 01:32:45 +0000 | [diff] [blame] | 2235 | void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2236 | CFG *CFGraph = AC.getCFG(); |
| 2237 | if (!CFGraph) return; |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 2238 | const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl()); |
| 2239 | |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2240 | // AC.dumpCFG(true); |
| 2241 | |
DeLesley Hutchins | 9f80a97 | 2011-10-17 21:33:35 +0000 | [diff] [blame] | 2242 | if (!D) |
| 2243 | return; // Ignore anonymous functions for now. |
| 2244 | if (D->getAttr<NoThreadSafetyAnalysisAttr>()) |
| 2245 | return; |
DeLesley Hutchins | 2f13bec | 2012-02-16 17:13:43 +0000 | [diff] [blame] | 2246 | // FIXME: Do something a bit more intelligent inside constructor and |
| 2247 | // destructor code. Constructors and destructors must assume unique access |
| 2248 | // to 'this', so checks on member variable access is disabled, but we should |
| 2249 | // still enable checks on other objects. |
| 2250 | if (isa<CXXConstructorDecl>(D)) |
| 2251 | return; // Don't check inside constructors. |
| 2252 | if (isa<CXXDestructorDecl>(D)) |
| 2253 | return; // Don't check inside destructors. |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2254 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 2255 | BlockInfo.resize(CFGraph->getNumBlockIDs(), |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2256 | CFGBlockInfo::getEmptyBlockInfo(LocalVarMap)); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2257 | |
| 2258 | // We need to explore the CFG via a "topological" ordering. |
| 2259 | // That way, we will be guaranteed to have information about required |
| 2260 | // predecessor locksets when exploring a new block. |
Ted Kremenek | 439ed16 | 2011-10-22 02:14:27 +0000 | [diff] [blame] | 2261 | PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>(); |
| 2262 | PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2263 | |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 2264 | // Mark entry block as reachable |
| 2265 | BlockInfo[CFGraph->getEntry().getBlockID()].Reachable = true; |
| 2266 | |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2267 | // Compute SSA names for local variables |
| 2268 | LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); |
| 2269 | |
Richard Smith | 2e51562 | 2012-02-03 04:45:26 +0000 | [diff] [blame] | 2270 | // Fill in source locations for all CFGBlocks. |
| 2271 | findBlockLocations(CFGraph, SortedGraph, BlockInfo); |
| 2272 | |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 2273 | // Add locks from exclusive_locks_required and shared_locks_required |
DeLesley Hutchins | 2f13bec | 2012-02-16 17:13:43 +0000 | [diff] [blame] | 2274 | // to initial lockset. Also turn off checking for lock and unlock functions. |
| 2275 | // FIXME: is there a more intelligent way to check lock/unlock functions? |
Ted Kremenek | 439ed16 | 2011-10-22 02:14:27 +0000 | [diff] [blame] | 2276 | if (!SortedGraph->empty() && D->hasAttrs()) { |
| 2277 | const CFGBlock *FirstBlock = *SortedGraph->begin(); |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2278 | FactSet &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; |
Caitlin Sadowski | cb96751 | 2011-09-15 17:43:08 +0000 | [diff] [blame] | 2279 | const AttrVec &ArgAttrs = D->getAttrs(); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2280 | |
| 2281 | MutexIDList ExclusiveLocksToAdd; |
| 2282 | MutexIDList SharedLocksToAdd; |
| 2283 | |
| 2284 | SourceLocation Loc = D->getLocation(); |
DeLesley Hutchins | 2f13bec | 2012-02-16 17:13:43 +0000 | [diff] [blame] | 2285 | for (unsigned i = 0; i < ArgAttrs.size(); ++i) { |
Caitlin Sadowski | cb96751 | 2011-09-15 17:43:08 +0000 | [diff] [blame] | 2286 | Attr *Attr = ArgAttrs[i]; |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2287 | Loc = Attr->getLocation(); |
| 2288 | if (ExclusiveLocksRequiredAttr *A |
| 2289 | = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) { |
| 2290 | getMutexIDs(ExclusiveLocksToAdd, A, (Expr*) 0, D); |
| 2291 | } else if (SharedLocksRequiredAttr *A |
| 2292 | = dyn_cast<SharedLocksRequiredAttr>(Attr)) { |
| 2293 | getMutexIDs(SharedLocksToAdd, A, (Expr*) 0, D); |
DeLesley Hutchins | 2f13bec | 2012-02-16 17:13:43 +0000 | [diff] [blame] | 2294 | } else if (isa<UnlockFunctionAttr>(Attr)) { |
| 2295 | // Don't try to check unlock functions for now |
| 2296 | return; |
| 2297 | } else if (isa<ExclusiveLockFunctionAttr>(Attr)) { |
| 2298 | // Don't try to check lock functions for now |
| 2299 | return; |
| 2300 | } else if (isa<SharedLockFunctionAttr>(Attr)) { |
| 2301 | // Don't try to check lock functions for now |
| 2302 | return; |
DeLesley Hutchins | 76f0a6e | 2012-07-02 21:59:24 +0000 | [diff] [blame] | 2303 | } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) { |
| 2304 | // Don't try to check trylock functions for now |
| 2305 | return; |
| 2306 | } else if (isa<SharedTrylockFunctionAttr>(Attr)) { |
| 2307 | // Don't try to check trylock functions for now |
| 2308 | return; |
Caitlin Sadowski | cb96751 | 2011-09-15 17:43:08 +0000 | [diff] [blame] | 2309 | } |
| 2310 | } |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2311 | |
| 2312 | // FIXME -- Loc can be wrong here. |
| 2313 | for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2314 | addLock(InitialLockset, ExclusiveLocksToAdd[i], |
| 2315 | LockData(Loc, LK_Exclusive)); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2316 | } |
| 2317 | for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2318 | addLock(InitialLockset, SharedLocksToAdd[i], |
| 2319 | LockData(Loc, LK_Shared)); |
DeLesley Hutchins | 5381c05 | 2012-07-05 21:16:29 +0000 | [diff] [blame] | 2320 | } |
Caitlin Sadowski | cb96751 | 2011-09-15 17:43:08 +0000 | [diff] [blame] | 2321 | } |
| 2322 | |
Ted Kremenek | 439ed16 | 2011-10-22 02:14:27 +0000 | [diff] [blame] | 2323 | for (PostOrderCFGView::iterator I = SortedGraph->begin(), |
| 2324 | E = SortedGraph->end(); I!= E; ++I) { |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2325 | const CFGBlock *CurrBlock = *I; |
| 2326 | int CurrBlockID = CurrBlock->getBlockID(); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2327 | CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2328 | |
| 2329 | // Use the default initial lockset in case there are no predecessors. |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2330 | VisitedBlocks.insert(CurrBlock); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2331 | |
| 2332 | // Iterate through the predecessor blocks and warn if the lockset for all |
| 2333 | // predecessors is not the same. We take the entry lockset of the current |
| 2334 | // block to be the intersection of all previous locksets. |
| 2335 | // FIXME: By keeping the intersection, we may output more errors in future |
| 2336 | // for a lock which is not in the intersection, but was in the union. We |
| 2337 | // may want to also keep the union in future. As an example, let's say |
| 2338 | // the intersection contains Mutex L, and the union contains L and M. |
| 2339 | // Later we unlock M. At this point, we would output an error because we |
| 2340 | // never locked M; although the real error is probably that we forgot to |
| 2341 | // lock M on all code paths. Conversely, let's say that later we lock M. |
| 2342 | // In this case, we should compare against the intersection instead of the |
| 2343 | // union because the real error is probably that we forgot to unlock M on |
| 2344 | // all code paths. |
| 2345 | bool LocksetInitialized = false; |
Richard Smith | aacde71 | 2012-02-03 03:30:07 +0000 | [diff] [blame] | 2346 | llvm::SmallVector<CFGBlock*, 8> SpecialBlocks; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2347 | for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), |
| 2348 | PE = CurrBlock->pred_end(); PI != PE; ++PI) { |
| 2349 | |
| 2350 | // if *PI -> CurrBlock is a back edge |
| 2351 | if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) |
| 2352 | continue; |
| 2353 | |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 2354 | int PrevBlockID = (*PI)->getBlockID(); |
| 2355 | CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; |
| 2356 | |
DeLesley Hutchins | 2a35be8 | 2012-03-02 22:02:58 +0000 | [diff] [blame] | 2357 | // Ignore edges from blocks that can't return. |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 2358 | if ((*PI)->hasNoReturnElement() || !PrevBlockInfo->Reachable) |
DeLesley Hutchins | 2a35be8 | 2012-03-02 22:02:58 +0000 | [diff] [blame] | 2359 | continue; |
| 2360 | |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 2361 | // Okay, we can reach this block from the entry. |
| 2362 | CurrBlockInfo->Reachable = true; |
| 2363 | |
Richard Smith | aacde71 | 2012-02-03 03:30:07 +0000 | [diff] [blame] | 2364 | // If the previous block ended in a 'continue' or 'break' statement, then |
| 2365 | // a difference in locksets is probably due to a bug in that block, rather |
| 2366 | // than in some other predecessor. In that case, keep the other |
| 2367 | // predecessor's lockset. |
| 2368 | if (const Stmt *Terminator = (*PI)->getTerminator()) { |
| 2369 | if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { |
| 2370 | SpecialBlocks.push_back(*PI); |
| 2371 | continue; |
| 2372 | } |
| 2373 | } |
| 2374 | |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 2375 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2376 | FactSet PrevLockset; |
| 2377 | getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, *PI, CurrBlock); |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2378 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2379 | if (!LocksetInitialized) { |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2380 | CurrBlockInfo->EntrySet = PrevLockset; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2381 | LocksetInitialized = true; |
| 2382 | } else { |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2383 | intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, |
| 2384 | CurrBlockInfo->EntryLoc, |
| 2385 | LEK_LockedSomePredecessors); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2386 | } |
| 2387 | } |
| 2388 | |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 2389 | // Skip rest of block if it's not reachable. |
| 2390 | if (!CurrBlockInfo->Reachable) |
| 2391 | continue; |
| 2392 | |
Richard Smith | aacde71 | 2012-02-03 03:30:07 +0000 | [diff] [blame] | 2393 | // Process continue and break blocks. Assume that the lockset for the |
| 2394 | // resulting block is unaffected by any discrepancies in them. |
| 2395 | for (unsigned SpecialI = 0, SpecialN = SpecialBlocks.size(); |
| 2396 | SpecialI < SpecialN; ++SpecialI) { |
| 2397 | CFGBlock *PrevBlock = SpecialBlocks[SpecialI]; |
| 2398 | int PrevBlockID = PrevBlock->getBlockID(); |
| 2399 | CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; |
| 2400 | |
| 2401 | if (!LocksetInitialized) { |
| 2402 | CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; |
| 2403 | LocksetInitialized = true; |
| 2404 | } else { |
| 2405 | // Determine whether this edge is a loop terminator for diagnostic |
| 2406 | // purposes. FIXME: A 'break' statement might be a loop terminator, but |
| 2407 | // it might also be part of a switch. Also, a subsequent destructor |
| 2408 | // might add to the lockset, in which case the real issue might be a |
| 2409 | // double lock on the other path. |
| 2410 | const Stmt *Terminator = PrevBlock->getTerminator(); |
| 2411 | bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); |
| 2412 | |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2413 | FactSet PrevLockset; |
| 2414 | getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, |
| 2415 | PrevBlock, CurrBlock); |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2416 | |
Richard Smith | aacde71 | 2012-02-03 03:30:07 +0000 | [diff] [blame] | 2417 | // Do not update EntrySet. |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2418 | intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, |
| 2419 | PrevBlockInfo->ExitLoc, |
Richard Smith | aacde71 | 2012-02-03 03:30:07 +0000 | [diff] [blame] | 2420 | IsLoop ? LEK_LockedSomeLoopIterations |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2421 | : LEK_LockedSomePredecessors, |
| 2422 | false); |
Richard Smith | aacde71 | 2012-02-03 03:30:07 +0000 | [diff] [blame] | 2423 | } |
| 2424 | } |
| 2425 | |
DeLesley Hutchins | 54c350a | 2012-04-19 16:48:43 +0000 | [diff] [blame] | 2426 | BuildLockset LocksetBuilder(this, *CurrBlockInfo); |
| 2427 | |
DeLesley Hutchins | b37d2b5 | 2012-01-06 18:36:09 +0000 | [diff] [blame] | 2428 | // Visit all the statements in the basic block. |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2429 | for (CFGBlock::const_iterator BI = CurrBlock->begin(), |
| 2430 | BE = CurrBlock->end(); BI != BE; ++BI) { |
DeLesley Hutchins | 6db51f7 | 2011-10-21 20:51:27 +0000 | [diff] [blame] | 2431 | switch (BI->getKind()) { |
| 2432 | case CFGElement::Statement: { |
| 2433 | const CFGStmt *CS = cast<CFGStmt>(&*BI); |
| 2434 | LocksetBuilder.Visit(const_cast<Stmt*>(CS->getStmt())); |
| 2435 | break; |
| 2436 | } |
| 2437 | // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. |
| 2438 | case CFGElement::AutomaticObjectDtor: { |
| 2439 | const CFGAutomaticObjDtor *AD = cast<CFGAutomaticObjDtor>(&*BI); |
| 2440 | CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( |
| 2441 | AD->getDestructorDecl(AC.getASTContext())); |
| 2442 | if (!DD->hasAttrs()) |
| 2443 | break; |
| 2444 | |
| 2445 | // Create a dummy expression, |
| 2446 | VarDecl *VD = const_cast<VarDecl*>(AD->getVarDecl()); |
John McCall | f4b88a4 | 2012-03-10 09:33:50 +0000 | [diff] [blame] | 2447 | DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, |
DeLesley Hutchins | 6db51f7 | 2011-10-21 20:51:27 +0000 | [diff] [blame] | 2448 | AD->getTriggerStmt()->getLocEnd()); |
| 2449 | LocksetBuilder.handleCall(&DRE, DD); |
| 2450 | break; |
| 2451 | } |
| 2452 | default: |
| 2453 | break; |
| 2454 | } |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2455 | } |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2456 | CurrBlockInfo->ExitSet = LocksetBuilder.FSet; |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2457 | |
| 2458 | // For every back edge from CurrBlock (the end of the loop) to another block |
| 2459 | // (FirstLoopBlock) we need to check that the Lockset of Block is equal to |
| 2460 | // the one held at the beginning of FirstLoopBlock. We can look up the |
| 2461 | // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. |
| 2462 | for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), |
| 2463 | SE = CurrBlock->succ_end(); SI != SE; ++SI) { |
| 2464 | |
| 2465 | // if CurrBlock -> *SI is *not* a back edge |
| 2466 | if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) |
| 2467 | continue; |
| 2468 | |
| 2469 | CFGBlock *FirstLoopBlock = *SI; |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2470 | CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()]; |
| 2471 | CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID]; |
| 2472 | intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, |
| 2473 | PreLoop->EntryLoc, |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2474 | LEK_LockedSomeLoopIterations, |
| 2475 | false); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2476 | } |
| 2477 | } |
| 2478 | |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2479 | CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()]; |
| 2480 | CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()]; |
Caitlin Sadowski | 1748b12 | 2011-09-16 00:35:54 +0000 | [diff] [blame] | 2481 | |
DeLesley Hutchins | d2f3882 | 2012-09-21 17:57:00 +0000 | [diff] [blame] | 2482 | // Skip the final check if the exit block is unreachable. |
| 2483 | if (!Final->Reachable) |
| 2484 | return; |
| 2485 | |
Caitlin Sadowski | 1748b12 | 2011-09-16 00:35:54 +0000 | [diff] [blame] | 2486 | // FIXME: Should we call this function for all blocks which exit the function? |
DeLesley Hutchins | 0da4414 | 2012-06-22 17:07:28 +0000 | [diff] [blame] | 2487 | intersectAndWarn(Initial->EntrySet, Final->ExitSet, |
| 2488 | Final->ExitLoc, |
DeLesley Hutchins | 879a433 | 2012-07-02 22:16:54 +0000 | [diff] [blame] | 2489 | LEK_LockedAtEndOfFunction, |
DeLesley Hutchins | a1fa471 | 2012-08-10 18:39:05 +0000 | [diff] [blame] | 2490 | LEK_NotLockedAtEndOfFunction, |
| 2491 | false); |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 2492 | } |
| 2493 | |
| 2494 | } // end anonymous namespace |
| 2495 | |
| 2496 | |
| 2497 | namespace clang { |
| 2498 | namespace thread_safety { |
| 2499 | |
| 2500 | /// \brief Check a function's CFG for thread-safety violations. |
| 2501 | /// |
| 2502 | /// We traverse the blocks in the CFG, compute the set of mutexes that are held |
| 2503 | /// at the end of each block, and issue warnings for thread safety violations. |
| 2504 | /// Each block in the CFG is traversed exactly once. |
Ted Kremenek | 1d26f48 | 2011-10-24 01:32:45 +0000 | [diff] [blame] | 2505 | void runThreadSafetyAnalysis(AnalysisDeclContext &AC, |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 2506 | ThreadSafetyHandler &Handler) { |
| 2507 | ThreadSafetyAnalyzer Analyzer(Handler); |
| 2508 | Analyzer.runAnalysis(AC); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2509 | } |
| 2510 | |
| 2511 | /// \brief Helper function that returns a LockKind required for the given level |
| 2512 | /// of access. |
| 2513 | LockKind getLockKindFromAccessKind(AccessKind AK) { |
| 2514 | switch (AK) { |
| 2515 | case AK_Read : |
| 2516 | return LK_Shared; |
| 2517 | case AK_Written : |
| 2518 | return LK_Exclusive; |
| 2519 | } |
Benjamin Kramer | afc5b15 | 2011-09-10 21:52:04 +0000 | [diff] [blame] | 2520 | llvm_unreachable("Unknown AccessKind"); |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2521 | } |
DeLesley Hutchins | a60448d | 2011-10-21 16:14:33 +0000 | [diff] [blame] | 2522 | |
Caitlin Sadowski | 402aa06 | 2011-09-09 16:11:56 +0000 | [diff] [blame] | 2523 | }} // end namespace clang::thread_safety |