Coverage Report

Created: 2022-07-16 07:03

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