Coverage Report

Created: 2019-02-20 07:29

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