Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h
Line
Count
Source (jump to first uncovered line)
1
//===- ThreadSafetyTIL.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
// This file defines a simple Typed Intermediate Language, or TIL, that is used
10
// by the thread safety analysis (See ThreadSafety.cpp).  The TIL is intended
11
// to be largely independent of clang, in the hope that the analysis can be
12
// reused for other non-C++ languages.  All dependencies on clang/llvm should
13
// go in ThreadSafetyUtil.h.
14
//
15
// Thread safety analysis works by comparing mutex expressions, e.g.
16
//
17
// class A { Mutex mu; int dat GUARDED_BY(this->mu); }
18
// class B { A a; }
19
//
20
// void foo(B* b) {
21
//   (*b).a.mu.lock();     // locks (*b).a.mu
22
//   b->a.dat = 0;         // substitute &b->a for 'this';
23
//                         // requires lock on (&b->a)->mu
24
//   (b->a.mu).unlock();   // unlocks (b->a.mu)
25
// }
26
//
27
// As illustrated by the above example, clang Exprs are not well-suited to
28
// represent mutex expressions directly, since there is no easy way to compare
29
// Exprs for equivalence.  The thread safety analysis thus lowers clang Exprs
30
// into a simple intermediate language (IL).  The IL supports:
31
//
32
// (1) comparisons for semantic equality of expressions
33
// (2) SSA renaming of variables
34
// (3) wildcards and pattern matching over expressions
35
// (4) hash-based expression lookup
36
//
37
// The TIL is currently very experimental, is intended only for use within
38
// the thread safety analysis, and is subject to change without notice.
39
// After the API stabilizes and matures, it may be appropriate to make this
40
// more generally available to other analyses.
41
//
42
// UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
43
//
44
//===----------------------------------------------------------------------===//
45
46
#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
47
#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
48
49
#include "clang/AST/Decl.h"
50
#include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
51
#include "clang/Basic/LLVM.h"
52
#include "llvm/ADT/ArrayRef.h"
53
#include "llvm/ADT/None.h"
54
#include "llvm/ADT/Optional.h"
55
#include "llvm/ADT/StringRef.h"
56
#include "llvm/Support/Casting.h"
57
#include "llvm/Support/raw_ostream.h"
58
#include <algorithm>
59
#include <cassert>
60
#include <cstddef>
61
#include <cstdint>
62
#include <iterator>
63
#include <string>
64
#include <utility>
65
66
namespace clang {
67
68
class CallExpr;
69
class Expr;
70
class Stmt;
71
72
namespace threadSafety {
73
namespace til {
74
75
class BasicBlock;
76
77
/// Enum for the different distinct classes of SExpr
78
enum TIL_Opcode {
79
#define TIL_OPCODE_DEF(X) COP_##X,
80
#include "ThreadSafetyOps.def"
81
#undef TIL_OPCODE_DEF
82
};
83
84
/// Opcode for unary arithmetic operations.
85
enum TIL_UnaryOpcode : unsigned char {
86
  UOP_Minus,        //  -
87
  UOP_BitNot,       //  ~
88
  UOP_LogicNot      //  !
89
};
90
91
/// Opcode for binary arithmetic operations.
92
enum TIL_BinaryOpcode : unsigned char {
93
  BOP_Add,          //  +
94
  BOP_Sub,          //  -
95
  BOP_Mul,          //  *
96
  BOP_Div,          //  /
97
  BOP_Rem,          //  %
98
  BOP_Shl,          //  <<
99
  BOP_Shr,          //  >>
100
  BOP_BitAnd,       //  &
101
  BOP_BitXor,       //  ^
102
  BOP_BitOr,        //  |
103
  BOP_Eq,           //  ==
104
  BOP_Neq,          //  !=
105
  BOP_Lt,           //  <
106
  BOP_Leq,          //  <=
107
  BOP_Cmp,          //  <=>
108
  BOP_LogicAnd,     //  &&  (no short-circuit)
109
  BOP_LogicOr       //  ||  (no short-circuit)
110
};
111
112
/// Opcode for cast operations.
113
enum TIL_CastOpcode : unsigned char {
114
  CAST_none = 0,
115
116
  // Extend precision of numeric type
117
  CAST_extendNum,
118
119
  // Truncate precision of numeric type
120
  CAST_truncNum,
121
122
  // Convert to floating point type
123
  CAST_toFloat,
124
125
  // Convert to integer type
126
  CAST_toInt,
127
128
  // Convert smart pointer to pointer (C++ only)
129
  CAST_objToPtr
130
};
131
132
const TIL_Opcode       COP_Min  = COP_Future;
133
const TIL_Opcode       COP_Max  = COP_Branch;
134
const TIL_UnaryOpcode  UOP_Min  = UOP_Minus;
135
const TIL_UnaryOpcode  UOP_Max  = UOP_LogicNot;
136
const TIL_BinaryOpcode BOP_Min  = BOP_Add;
137
const TIL_BinaryOpcode BOP_Max  = BOP_LogicOr;
138
const TIL_CastOpcode   CAST_Min = CAST_none;
139
const TIL_CastOpcode   CAST_Max = CAST_toInt;
140
141
/// Return the name of a unary opcode.
142
StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
143
144
/// Return the name of a binary opcode.
145
StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
146
147
/// ValueTypes are data types that can actually be held in registers.
148
/// All variables and expressions must have a value type.
149
/// Pointer types are further subdivided into the various heap-allocated
150
/// types, such as functions, records, etc.
151
/// Structured types that are passed by value (e.g. complex numbers)
152
/// require special handling; they use BT_ValueRef, and size ST_0.
153
struct ValueType {
154
  enum BaseType : unsigned char {
155
    BT_Void = 0,
156
    BT_Bool,
157
    BT_Int,
158
    BT_Float,
159
    BT_String,    // String literals
160
    BT_Pointer,
161
    BT_ValueRef
162
  };
163
164
  enum SizeType : unsigned char {
165
    ST_0 = 0,
166
    ST_1,
167
    ST_8,
168
    ST_16,
169
    ST_32,
170
    ST_64,
171
    ST_128
172
  };
173
174
  ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
175
72
      : Base(B), Size(Sz), Signed(S), VectSize(VS) {}
176
177
  inline static SizeType getSizeType(unsigned nbytes);
178
179
  template <class T>
180
  inline static ValueType getValueType();
181
182
  BaseType Base;
183
  SizeType Size;
184
  bool Signed;
185
186
  // 0 for scalar, otherwise num elements in vector
187
  unsigned char VectSize;
188
};
189
190
0
inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
191
0
  switch (nbytes) {
192
0
    case 1: return ST_8;
193
0
    case 2: return ST_16;
194
0
    case 4: return ST_32;
195
0
    case 8: return ST_64;
196
0
    case 16: return ST_128;
197
0
    default: return ST_0;
198
0
  }
199
0
}
200
201
template<>
202
72
inline ValueType ValueType::getValueType<void>() {
203
72
  return ValueType(BT_Void, ST_0, false, 0);
204
72
}
205
206
template<>
207
0
inline ValueType ValueType::getValueType<bool>() {
208
0
  return ValueType(BT_Bool, ST_1, false, 0);
209
0
}
210
211
template<>
212
0
inline ValueType ValueType::getValueType<int8_t>() {
213
0
  return ValueType(BT_Int, ST_8, true, 0);
214
0
}
215
216
template<>
217
0
inline ValueType ValueType::getValueType<uint8_t>() {
218
0
  return ValueType(BT_Int, ST_8, false, 0);
219
0
}
220
221
template<>
222
0
inline ValueType ValueType::getValueType<int16_t>() {
223
0
  return ValueType(BT_Int, ST_16, true, 0);
224
0
}
225
226
template<>
227
0
inline ValueType ValueType::getValueType<uint16_t>() {
228
0
  return ValueType(BT_Int, ST_16, false, 0);
229
0
}
230
231
template<>
232
0
inline ValueType ValueType::getValueType<int32_t>() {
233
0
  return ValueType(BT_Int, ST_32, true, 0);
234
0
}
235
236
template<>
237
0
inline ValueType ValueType::getValueType<uint32_t>() {
238
0
  return ValueType(BT_Int, ST_32, false, 0);
239
0
}
240
241
template<>
242
0
inline ValueType ValueType::getValueType<int64_t>() {
243
0
  return ValueType(BT_Int, ST_64, true, 0);
244
0
}
245
246
template<>
247
0
inline ValueType ValueType::getValueType<uint64_t>() {
248
0
  return ValueType(BT_Int, ST_64, false, 0);
249
0
}
250
251
template<>
252
0
inline ValueType ValueType::getValueType<float>() {
253
0
  return ValueType(BT_Float, ST_32, true, 0);
254
0
}
255
256
template<>
257
0
inline ValueType ValueType::getValueType<double>() {
258
0
  return ValueType(BT_Float, ST_64, true, 0);
259
0
}
260
261
template<>
262
0
inline ValueType ValueType::getValueType<long double>() {
263
0
  return ValueType(BT_Float, ST_128, true, 0);
264
0
}
265
266
template<>
267
0
inline ValueType ValueType::getValueType<StringRef>() {
268
0
  return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
269
0
}
270
271
template<>
272
0
inline ValueType ValueType::getValueType<void*>() {
273
0
  return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
274
0
}
275
276
/// Base class for AST nodes in the typed intermediate language.
277
class SExpr {
278
public:
279
  SExpr() = delete;
280
281
322k
  TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); }
282
283
  // Subclasses of SExpr must define the following:
284
  //
285
  // This(const This& E, ...) {
286
  //   copy constructor: construct copy of E, with some additional arguments.
287
  // }
288
  //
289
  // template <class V>
290
  // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
291
  //   traverse all subexpressions, following the traversal/rewriter interface.
292
  // }
293
  //
294
  // template <class C> typename C::CType compare(CType* E, C& Cmp) {
295
  //   compare all subexpressions, following the comparator interface
296
  // }
297
20.1k
  void *operator new(size_t S, MemRegionRef &R) {
298
20.1k
    return ::operator new(S, R);
299
20.1k
  }
300
301
  /// SExpr objects must be created in an arena.
302
  void *operator new(size_t) = delete;
303
304
  /// SExpr objects cannot be deleted.
305
  // This declaration is public to workaround a gcc bug that breaks building
306
  // with REQUIRES_EH=1.
307
  void operator delete(void *) = delete;
308
309
  /// Returns the instruction ID for this expression.
310
  /// All basic block instructions have a unique ID (i.e. virtual register).
311
0
  unsigned id() const { return SExprID; }
312
313
  /// Returns the block, if this is an instruction in a basic block,
314
  /// otherwise returns null.
315
4.23k
  BasicBlock *block() const { return Block; }
316
317
  /// Set the basic block and instruction ID for this expression.
318
0
  void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
319
320
protected:
321
20.1k
  SExpr(TIL_Opcode Op) : Opcode(Op) {}
322
0
  SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {}
323
324
  const unsigned char Opcode;
325
  unsigned char Reserved = 0;
326
  unsigned short Flags = 0;
327
  unsigned SExprID = 0;
328
  BasicBlock *Block = nullptr;
329
};
330
331
// Contains various helper functions for SExprs.
332
namespace ThreadSafetyTIL {
333
334
0
inline bool isTrivial(const SExpr *E) {
335
0
  unsigned Op = E->opcode();
336
0
  return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
337
0
}
338
339
} // namespace ThreadSafetyTIL
340
341
// Nodes which declare variables
342
343
/// A named variable, e.g. "x".
344
///
345
/// There are two distinct places in which a Variable can appear in the AST.
346
/// A variable declaration introduces a new variable, and can occur in 3 places:
347
///   Let-expressions:           (Let (x = t) u)
348
///   Functions:                 (Function (x : t) u)
349
///   Self-applicable functions  (SFunction (x) t)
350
///
351
/// If a variable occurs in any other location, it is a reference to an existing
352
/// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
353
/// allocate a separate AST node for variable references; a reference is just a
354
/// pointer to the original declaration.
355
class Variable : public SExpr {
356
public:
357
  enum VariableKind {
358
    /// Let-variable
359
    VK_Let,
360
361
    /// Function parameter
362
    VK_Fun,
363
364
    /// SFunction (self) parameter
365
    VK_SFun
366
  };
367
368
  Variable(StringRef s, SExpr *D = nullptr)
369
0
      : SExpr(COP_Variable), Name(s), Definition(D) {
370
0
    Flags = VK_Let;
371
0
  }
372
373
  Variable(SExpr *D, const ValueDecl *Cvd = nullptr)
374
      : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
375
2.14k
        Definition(D), Cvdecl(Cvd) {
376
2.14k
    Flags = VK_Let;
377
2.14k
  }
378
379
  Variable(const Variable &Vd, SExpr *D)  // rewrite constructor
380
0
      : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
381
0
    Flags = Vd.kind();
382
0
  }
383
384
8.94k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
385
386
  /// Return the kind of variable (let, function param, or self)
387
2.16k
  VariableKind kind() const { return static_cast<VariableKind>(Flags); }
388
389
  /// Return the name of the variable, if any.
390
0
  StringRef name() const { return Name; }
391
392
  /// Return the clang declaration for this variable, if any.
393
4.05k
  const ValueDecl *clangDecl() const { return Cvdecl; }
394
395
  /// Return the definition of the variable.
396
  /// For let-vars, this is the setting expression.
397
  /// For function and self parameters, it is the type of the variable.
398
0
  SExpr *definition() { return Definition; }
399
0
  const SExpr *definition() const { return Definition; }
400
401
0
  void setName(StringRef S)    { Name = S;  }
402
2.14k
  void setKind(VariableKind K) { Flags = K; }
403
0
  void setDefinition(SExpr *E) { Definition = E; }
404
0
  void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; }
405
406
  template <class V>
407
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
408
    // This routine is only called for variable references.
409
    return Vs.reduceVariableRef(this);
410
  }
411
412
  template <class C>
413
11.5k
  typename C::CType compare(const Variable* E, C& Cmp) const {
414
11.5k
    return Cmp.compareVariableRefs(this, E);
415
11.5k
  }
clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Variable::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Variable const*, clang::threadSafety::til::EqualsComparator&) const
Line
Count
Source
413
832
  typename C::CType compare(const Variable* E, C& Cmp) const {
414
832
    return Cmp.compareVariableRefs(this, E);
415
832
  }
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Variable::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Variable const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
413
10.7k
  typename C::CType compare(const Variable* E, C& Cmp) const {
414
10.7k
    return Cmp.compareVariableRefs(this, E);
415
10.7k
  }
416
417
private:
418
  friend class BasicBlock;
419
  friend class Function;
420
  friend class Let;
421
  friend class SFunction;
422
423
  // The name of the variable.
424
  StringRef Name;
425
426
  // The TIL type or definition.
427
  SExpr *Definition;
428
429
  // The clang declaration for this variable.
430
  const ValueDecl *Cvdecl = nullptr;
431
};
432
433
/// Placeholder for an expression that has not yet been created.
434
/// Used to implement lazy copy and rewriting strategies.
435
class Future : public SExpr {
436
public:
437
  enum FutureStatus {
438
    FS_pending,
439
    FS_evaluating,
440
    FS_done
441
  };
442
443
0
  Future() : SExpr(COP_Future) {}
444
  virtual ~Future() = delete;
445
446
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
447
448
  // A lazy rewriting strategy should subclass Future and override this method.
449
0
  virtual SExpr *compute() { return nullptr; }
450
451
  // Return the result of this future if it exists, otherwise return null.
452
0
  SExpr *maybeGetResult() const { return Result; }
453
454
  // Return the result of this future; forcing it if necessary.
455
0
  SExpr *result() {
456
0
    switch (Status) {
457
0
    case FS_pending:
458
0
      return force();
459
0
    case FS_evaluating:
460
0
      return nullptr; // infinite loop; illegal recursion.
461
0
    case FS_done:
462
0
      return Result;
463
0
    }
464
0
  }
465
466
  template <class V>
467
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
468
    assert(Result && "Cannot traverse Future that has not been forced.");
469
    return Vs.traverse(Result, Ctx);
470
  }
471
472
  template <class C>
473
0
  typename C::CType compare(const Future* E, C& Cmp) const {
474
0
    if (!Result || !E->Result)
475
0
      return Cmp.comparePointers(this, E);
476
0
    return Cmp.compare(Result, E->Result);
477
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Future::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Future const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Future::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Future const*, clang::threadSafety::til::MatchComparator&) const
478
479
private:
480
  SExpr* force();
481
482
  FutureStatus Status = FS_pending;
483
  SExpr *Result = nullptr;
484
};
485
486
/// Placeholder for expressions that cannot be represented in the TIL.
487
class Undefined : public SExpr {
488
public:
489
28
  Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
490
0
  Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
491
492
7.88k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
493
494
  template <class V>
495
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
496
    return Vs.reduceUndefined(*this);
497
  }
498
499
  template <class C>
500
36
  typename C::CType compare(const Undefined* E, C& Cmp) const {
501
36
    return Cmp.trueResult();
502
36
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Undefined::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Undefined const*, clang::threadSafety::til::EqualsComparator&) const
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Undefined::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Undefined const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
500
36
  typename C::CType compare(const Undefined* E, C& Cmp) const {
501
36
    return Cmp.trueResult();
502
36
  }
503
504
private:
505
  const Stmt *Cstmt;
506
};
507
508
/// Placeholder for a wildcard that matches any other expression.
509
class Wildcard : public SExpr {
510
public:
511
148
  Wildcard() : SExpr(COP_Wildcard) {}
512
  Wildcard(const Wildcard &) = default;
513
514
28.3k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
515
516
  template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
517
    return Vs.reduceWildcard(*this);
518
  }
519
520
  template <class C>
521
0
  typename C::CType compare(const Wildcard* E, C& Cmp) const {
522
0
    return Cmp.trueResult();
523
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Wildcard::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Wildcard const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Wildcard::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Wildcard const*, clang::threadSafety::til::MatchComparator&) const
524
};
525
526
template <class T> class LiteralT;
527
528
// Base class for literal values.
529
class Literal : public SExpr {
530
public:
531
  Literal(const Expr *C)
532
72
     : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {}
533
0
  Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {}
534
  Literal(const Literal &) = default;
535
536
8.35k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
537
538
  // The clang expression for this literal.
539
24
  const Expr *clangExpr() const { return Cexpr; }
540
541
0
  ValueType valueType() const { return ValType; }
542
543
0
  template<class T> const LiteralT<T>& as() const {
544
0
    return *static_cast<const LiteralT<T>*>(this);
545
0
  }
Unexecuted instantiation: clang::threadSafety::til::LiteralT<bool> const& clang::threadSafety::til::Literal::as<bool>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<signed char> const& clang::threadSafety::til::Literal::as<signed char>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned char> const& clang::threadSafety::til::Literal::as<unsigned char>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<short> const& clang::threadSafety::til::Literal::as<short>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned short> const& clang::threadSafety::til::Literal::as<unsigned short>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<int> const& clang::threadSafety::til::Literal::as<int>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned int> const& clang::threadSafety::til::Literal::as<unsigned int>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<long long> const& clang::threadSafety::til::Literal::as<long long>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned long long> const& clang::threadSafety::til::Literal::as<unsigned long long>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<float> const& clang::threadSafety::til::Literal::as<float>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<double> const& clang::threadSafety::til::Literal::as<double>() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<llvm::StringRef> const& clang::threadSafety::til::Literal::as<llvm::StringRef>() const
546
  template<class T> LiteralT<T>& as() {
547
    return *static_cast<LiteralT<T>*>(this);
548
  }
549
550
  template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
551
552
  template <class C>
553
356
  typename C::CType compare(const Literal* E, C& Cmp) const {
554
356
    // TODO: defer actual comparison to LiteralT
555
356
    return Cmp.trueResult();
556
356
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Literal::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Literal const*, clang::threadSafety::til::EqualsComparator&) const
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Literal::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Literal const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
553
356
  typename C::CType compare(const Literal* E, C& Cmp) const {
554
356
    // TODO: defer actual comparison to LiteralT
555
356
    return Cmp.trueResult();
556
356
  }
557
558
private:
559
  const ValueType ValType;
560
  const Expr *Cexpr = nullptr;
561
};
562
563
// Derived class for literal values, which stores the actual value.
564
template<class T>
565
class LiteralT : public Literal {
566
public:
567
  LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {}
568
  LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {}
569
570
0
  T value() const { return Val;}
Unexecuted instantiation: clang::threadSafety::til::LiteralT<bool>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<signed char>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned char>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<short>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned short>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<int>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned int>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<long long>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<unsigned long long>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<float>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<double>::value() const
Unexecuted instantiation: clang::threadSafety::til::LiteralT<llvm::StringRef>::value() const
571
  T& value() { return Val; }
572
573
private:
574
  T Val;
575
};
576
577
template <class V>
578
typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
579
  if (Cexpr)
580
    return Vs.reduceLiteral(*this);
581
582
  switch (ValType.Base) {
583
  case ValueType::BT_Void:
584
    break;
585
  case ValueType::BT_Bool:
586
    return Vs.reduceLiteralT(as<bool>());
587
  case ValueType::BT_Int: {
588
    switch (ValType.Size) {
589
    case ValueType::ST_8:
590
      if (ValType.Signed)
591
        return Vs.reduceLiteralT(as<int8_t>());
592
      else
593
        return Vs.reduceLiteralT(as<uint8_t>());
594
    case ValueType::ST_16:
595
      if (ValType.Signed)
596
        return Vs.reduceLiteralT(as<int16_t>());
597
      else
598
        return Vs.reduceLiteralT(as<uint16_t>());
599
    case ValueType::ST_32:
600
      if (ValType.Signed)
601
        return Vs.reduceLiteralT(as<int32_t>());
602
      else
603
        return Vs.reduceLiteralT(as<uint32_t>());
604
    case ValueType::ST_64:
605
      if (ValType.Signed)
606
        return Vs.reduceLiteralT(as<int64_t>());
607
      else
608
        return Vs.reduceLiteralT(as<uint64_t>());
609
    default:
610
      break;
611
    }
612
  }
613
  case ValueType::BT_Float: {
614
    switch (ValType.Size) {
615
    case ValueType::ST_32:
616
      return Vs.reduceLiteralT(as<float>());
617
    case ValueType::ST_64:
618
      return Vs.reduceLiteralT(as<double>());
619
    default:
620
      break;
621
    }
622
  }
623
  case ValueType::BT_String:
624
    return Vs.reduceLiteralT(as<StringRef>());
625
  case ValueType::BT_Pointer:
626
    return Vs.reduceLiteralT(as<void*>());
627
  case ValueType::BT_ValueRef:
628
    break;
629
  }
630
  return Vs.reduceLiteral(*this);
631
}
632
633
/// A Literal pointer to an object allocated in memory.
634
/// At compile time, pointer literals are represented by symbolic names.
635
class LiteralPtr : public SExpr {
636
public:
637
4.25k
  LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
638
  LiteralPtr(const LiteralPtr &) = default;
639
640
2.85k
  static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
641
642
  // The clang declaration for the value that this pointer points to.
643
3.39k
  const ValueDecl *clangDecl() const { return Cvdecl; }
644
645
  template <class V>
646
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
647
    return Vs.reduceLiteralPtr(*this);
648
  }
649
650
  template <class C>
651
10.6k
  typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
652
10.6k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
653
10.6k
  }
clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::LiteralPtr::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::LiteralPtr const*, clang::threadSafety::til::EqualsComparator&) const
Line
Count
Source
651
1.22k
  typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
652
1.22k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
653
1.22k
  }
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::LiteralPtr::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::LiteralPtr const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
651
9.39k
  typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
652
9.39k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
653
9.39k
  }
654
655
private:
656
  const ValueDecl *Cvdecl;
657
};
658
659
/// A function -- a.k.a. lambda abstraction.
660
/// Functions with multiple arguments are created by currying,
661
/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y })))
662
class Function : public SExpr {
663
public:
664
  Function(Variable *Vd, SExpr *Bd)
665
0
      : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
666
0
    Vd->setKind(Variable::VK_Fun);
667
0
  }
668
669
  Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
670
0
      : SExpr(F), VarDecl(Vd), Body(Bd) {
671
0
    Vd->setKind(Variable::VK_Fun);
672
0
  }
673
674
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
675
676
0
  Variable *variableDecl()  { return VarDecl; }
677
0
  const Variable *variableDecl() const { return VarDecl; }
678
679
0
  SExpr *body() { return Body; }
680
0
  const SExpr *body() const { return Body; }
681
682
  template <class V>
683
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
684
    // This is a variable declaration, so traverse the definition.
685
    auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
686
    // Tell the rewriter to enter the scope of the function.
687
    Variable *Nvd = Vs.enterScope(*VarDecl, E0);
688
    auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
689
    Vs.exitScope(*VarDecl);
690
    return Vs.reduceFunction(*this, Nvd, E1);
691
  }
692
693
  template <class C>
694
0
  typename C::CType compare(const Function* E, C& Cmp) const {
695
0
    typename C::CType Ct =
696
0
      Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
697
0
    if (Cmp.notTrue(Ct))
698
0
      return Ct;
699
0
    Cmp.enterScope(variableDecl(), E->variableDecl());
700
0
    Ct = Cmp.compare(body(), E->body());
701
0
    Cmp.leaveScope();
702
0
    return Ct;
703
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Function::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Function const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Function::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Function const*, clang::threadSafety::til::MatchComparator&) const
704
705
private:
706
  Variable *VarDecl;
707
  SExpr* Body;
708
};
709
710
/// A self-applicable function.
711
/// A self-applicable function can be applied to itself.  It's useful for
712
/// implementing objects and late binding.
713
class SFunction : public SExpr {
714
public:
715
  SFunction(Variable *Vd, SExpr *B)
716
0
      : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
717
0
    assert(Vd->Definition == nullptr);
718
0
    Vd->setKind(Variable::VK_SFun);
719
0
    Vd->Definition = this;
720
0
  }
721
722
  SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
723
0
      : SExpr(F), VarDecl(Vd), Body(B) {
724
0
    assert(Vd->Definition == nullptr);
725
0
    Vd->setKind(Variable::VK_SFun);
726
0
    Vd->Definition = this;
727
0
  }
728
729
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
730
731
0
  Variable *variableDecl() { return VarDecl; }
732
0
  const Variable *variableDecl() const { return VarDecl; }
733
734
0
  SExpr *body() { return Body; }
735
0
  const SExpr *body() const { return Body; }
736
737
  template <class V>
738
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
739
    // A self-variable points to the SFunction itself.
740
    // A rewrite must introduce the variable with a null definition, and update
741
    // it after 'this' has been rewritten.
742
    Variable *Nvd = Vs.enterScope(*VarDecl, nullptr);
743
    auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
744
    Vs.exitScope(*VarDecl);
745
    // A rewrite operation will call SFun constructor to set Vvd->Definition.
746
    return Vs.reduceSFunction(*this, Nvd, E1);
747
  }
748
749
  template <class C>
750
0
  typename C::CType compare(const SFunction* E, C& Cmp) const {
751
0
    Cmp.enterScope(variableDecl(), E->variableDecl());
752
0
    typename C::CType Ct = Cmp.compare(body(), E->body());
753
0
    Cmp.leaveScope();
754
0
    return Ct;
755
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::SFunction::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::SFunction const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::SFunction::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::SFunction const*, clang::threadSafety::til::MatchComparator&) const
756
757
private:
758
  Variable *VarDecl;
759
  SExpr* Body;
760
};
761
762
/// A block of code -- e.g. the body of a function.
763
class Code : public SExpr {
764
public:
765
0
  Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
766
  Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
767
0
      : SExpr(C), ReturnType(T), Body(B) {}
768
769
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
770
771
0
  SExpr *returnType() { return ReturnType; }
772
0
  const SExpr *returnType() const { return ReturnType; }
773
774
0
  SExpr *body() { return Body; }
775
0
  const SExpr *body() const { return Body; }
776
777
  template <class V>
778
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
779
    auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
780
    auto Nb = Vs.traverse(Body,       Vs.lazyCtx(Ctx));
781
    return Vs.reduceCode(*this, Nt, Nb);
782
  }
783
784
  template <class C>
785
0
  typename C::CType compare(const Code* E, C& Cmp) const {
786
0
    typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
787
0
    if (Cmp.notTrue(Ct))
788
0
      return Ct;
789
0
    return Cmp.compare(body(), E->body());
790
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Code::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Code const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Code::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Code const*, clang::threadSafety::til::MatchComparator&) const
791
792
private:
793
  SExpr* ReturnType;
794
  SExpr* Body;
795
};
796
797
/// A typed, writable location in memory
798
class Field : public SExpr {
799
public:
800
0
  Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
801
  Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
802
0
      : SExpr(C), Range(R), Body(B) {}
803
804
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
805
806
0
  SExpr *range() { return Range; }
807
0
  const SExpr *range() const { return Range; }
808
809
0
  SExpr *body() { return Body; }
810
0
  const SExpr *body() const { return Body; }
811
812
  template <class V>
813
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
814
    auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
815
    auto Nb = Vs.traverse(Body,  Vs.lazyCtx(Ctx));
816
    return Vs.reduceField(*this, Nr, Nb);
817
  }
818
819
  template <class C>
820
0
  typename C::CType compare(const Field* E, C& Cmp) const {
821
0
    typename C::CType Ct = Cmp.compare(range(), E->range());
822
0
    if (Cmp.notTrue(Ct))
823
0
      return Ct;
824
0
    return Cmp.compare(body(), E->body());
825
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Field::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Field const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Field::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Field const*, clang::threadSafety::til::MatchComparator&) const
826
827
private:
828
  SExpr* Range;
829
  SExpr* Body;
830
};
831
832
/// Apply an argument to a function.
833
/// Note that this does not actually call the function.  Functions are curried,
834
/// so this returns a closure in which the first parameter has been applied.
835
/// Once all parameters have been applied, Call can be used to invoke the
836
/// function.
837
class Apply : public SExpr {
838
public:
839
200
  Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
840
  Apply(const Apply &A, SExpr *F, SExpr *Ar)  // rewrite constructor
841
0
      : SExpr(A), Fun(F), Arg(Ar) {}
842
843
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
844
845
0
  SExpr *fun() { return Fun; }
846
2.71k
  const SExpr *fun() const { return Fun; }
847
848
0
  SExpr *arg() { return Arg; }
849
2.04k
  const SExpr *arg() const { return Arg; }
850
851
  template <class V>
852
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
853
    auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
854
    auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
855
    return Vs.reduceApply(*this, Nf, Na);
856
  }
857
858
  template <class C>
859
1.33k
  typename C::CType compare(const Apply* E, C& Cmp) const {
860
1.33k
    typename C::CType Ct = Cmp.compare(fun(), E->fun());
861
1.33k
    if (Cmp.notTrue(Ct))
862
336
      return Ct;
863
1.00k
    return Cmp.compare(arg(), E->arg());
864
1.00k
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Apply::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Apply const*, clang::threadSafety::til::EqualsComparator&) const
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Apply::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Apply const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
859
1.33k
  typename C::CType compare(const Apply* E, C& Cmp) const {
860
1.33k
    typename C::CType Ct = Cmp.compare(fun(), E->fun());
861
1.33k
    if (Cmp.notTrue(Ct))
862
336
      return Ct;
863
1.00k
    return Cmp.compare(arg(), E->arg());
864
1.00k
  }
865
866
private:
867
  SExpr* Fun;
868
  SExpr* Arg;
869
};
870
871
/// Apply a self-argument to a self-applicable function.
872
class SApply : public SExpr {
873
public:
874
6.27k
  SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
875
  SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
876
0
      : SExpr(A), Sfun(Sf), Arg(Ar) {}
877
878
2.69k
  static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
879
880
0
  SExpr *sfun() { return Sfun; }
881
23.8k
  const SExpr *sfun() const { return Sfun; }
882
883
0
  SExpr *arg() { return Arg ? Arg : Sfun; }
884
27.8k
  const SExpr *arg() const { return Arg ? 
Arg0
: Sfun; }
885
886
2.67k
  bool isDelegation() const { return Arg != nullptr; }
887
888
  template <class V>
889
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
890
    auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
891
    typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
892
                                       : nullptr;
893
    return Vs.reduceSApply(*this, Nf, Na);
894
  }
895
896
  template <class C>
897
10.3k
  typename C::CType compare(const SApply* E, C& Cmp) const {
898
10.3k
    typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
899
10.3k
    if (Cmp.notTrue(Ct) || 
(9.28k
!arg()9.28k
&&
!E->arg()0
))
900
1.06k
      return Ct;
901
9.28k
    return Cmp.compare(arg(), E->arg());
902
9.28k
  }
clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::SApply::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::SApply const*, clang::threadSafety::til::EqualsComparator&) const
Line
Count
Source
897
1.03k
  typename C::CType compare(const SApply* E, C& Cmp) const {
898
1.03k
    typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
899
1.03k
    if (Cmp.notTrue(Ct) || 
(1.01k
!arg()1.01k
&&
!E->arg()0
))
900
16
      return Ct;
901
1.01k
    return Cmp.compare(arg(), E->arg());
902
1.01k
  }
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::SApply::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::SApply const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
897
9.30k
  typename C::CType compare(const SApply* E, C& Cmp) const {
898
9.30k
    typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
899
9.30k
    if (Cmp.notTrue(Ct) || 
(8.26k
!arg()8.26k
&&
!E->arg()0
))
900
1.04k
      return Ct;
901
8.26k
    return Cmp.compare(arg(), E->arg());
902
8.26k
  }
903
904
private:
905
  SExpr* Sfun;
906
  SExpr* Arg;
907
};
908
909
/// Project a named slot from a C++ struct or class.
910
class Project : public SExpr {
911
public:
912
  Project(SExpr *R, const ValueDecl *Cvd)
913
6.35k
      : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {
914
6.35k
    assert(Cvd && "ValueDecl must not be null");
915
6.35k
  }
916
917
6.13k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
918
919
0
  SExpr *record() { return Rec; }
920
24.7k
  const SExpr *record() const { return Rec; }
921
922
3.01k
  const ValueDecl *clangDecl() const { return Cvdecl; }
923
924
518
  bool isArrow() const { return (Flags & 0x01) != 0; }
925
926
754
  void setArrow(bool b) {
927
754
    if (b) Flags |= 0x01;
928
0
    else Flags &= 0xFFFE;
929
754
  }
930
931
2.67k
  StringRef slotName() const {
932
2.67k
    if (Cvdecl->getDeclName().isIdentifier())
933
2.67k
      return Cvdecl->getName();
934
0
    if (!SlotName) {
935
0
      SlotName = "";
936
0
      llvm::raw_string_ostream OS(*SlotName);
937
0
      Cvdecl->printName(OS);
938
0
    }
939
0
    return *SlotName;
940
0
  }
941
942
  template <class V>
943
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
944
    auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
945
    return Vs.reduceProject(*this, Nr);
946
  }
947
948
  template <class C>
949
10.4k
  typename C::CType compare(const Project* E, C& Cmp) const {
950
10.4k
    typename C::CType Ct = Cmp.compare(record(), E->record());
951
10.4k
    if (Cmp.notTrue(Ct))
952
1.06k
      return Ct;
953
9.42k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
954
9.42k
  }
clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Project::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Project const*, clang::threadSafety::til::EqualsComparator&) const
Line
Count
Source
949
1.03k
  typename C::CType compare(const Project* E, C& Cmp) const {
950
1.03k
    typename C::CType Ct = Cmp.compare(record(), E->record());
951
1.03k
    if (Cmp.notTrue(Ct))
952
16
      return Ct;
953
1.01k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
954
1.01k
  }
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Project::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Project const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
949
9.45k
  typename C::CType compare(const Project* E, C& Cmp) const {
950
9.45k
    typename C::CType Ct = Cmp.compare(record(), E->record());
951
9.45k
    if (Cmp.notTrue(Ct))
952
1.04k
      return Ct;
953
8.40k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
954
8.40k
  }
955
956
private:
957
  SExpr* Rec;
958
  mutable llvm::Optional<std::string> SlotName;
959
  const ValueDecl *Cvdecl;
960
};
961
962
/// Call a function (after all arguments have been applied).
963
class Call : public SExpr {
964
public:
965
  Call(SExpr *T, const CallExpr *Ce = nullptr)
966
200
      : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
967
0
  Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
968
969
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
970
971
0
  SExpr *target() { return Target; }
972
2.93k
  const SExpr *target() const { return Target; }
973
974
0
  const CallExpr *clangCallExpr() const { return Cexpr; }
975
976
  template <class V>
977
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
978
    auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
979
    return Vs.reduceCall(*this, Nt);
980
  }
981
982
  template <class C>
983
1.44k
  typename C::CType compare(const Call* E, C& Cmp) const {
984
1.44k
    return Cmp.compare(target(), E->target());
985
1.44k
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Call::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Call const*, clang::threadSafety::til::EqualsComparator&) const
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Call::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Call const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
983
1.44k
  typename C::CType compare(const Call* E, C& Cmp) const {
984
1.44k
    return Cmp.compare(target(), E->target());
985
1.44k
  }
986
987
private:
988
  SExpr* Target;
989
  const CallExpr *Cexpr;
990
};
991
992
/// Allocate memory for a new value on the heap or stack.
993
class Alloc : public SExpr {
994
public:
995
  enum AllocKind {
996
    AK_Stack,
997
    AK_Heap
998
  };
999
1000
0
  Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1001
0
  Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1002
1003
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1004
1005
0
  AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1006
1007
0
  SExpr *dataType() { return Dtype; }
1008
0
  const SExpr *dataType() const { return Dtype; }
1009
1010
  template <class V>
1011
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1012
    auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
1013
    return Vs.reduceAlloc(*this, Nd);
1014
  }
1015
1016
  template <class C>
1017
0
  typename C::CType compare(const Alloc* E, C& Cmp) const {
1018
0
    typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
1019
0
    if (Cmp.notTrue(Ct))
1020
0
      return Ct;
1021
0
    return Cmp.compare(dataType(), E->dataType());
1022
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Alloc::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Alloc const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Alloc::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Alloc const*, clang::threadSafety::til::MatchComparator&) const
1023
1024
private:
1025
  SExpr* Dtype;
1026
};
1027
1028
/// Load a value from memory.
1029
class Load : public SExpr {
1030
public:
1031
0
  Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1032
0
  Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1033
1034
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1035
1036
0
  SExpr *pointer() { return Ptr; }
1037
0
  const SExpr *pointer() const { return Ptr; }
1038
1039
  template <class V>
1040
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1041
    auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
1042
    return Vs.reduceLoad(*this, Np);
1043
  }
1044
1045
  template <class C>
1046
0
  typename C::CType compare(const Load* E, C& Cmp) const {
1047
0
    return Cmp.compare(pointer(), E->pointer());
1048
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Load::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Load const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Load::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Load const*, clang::threadSafety::til::MatchComparator&) const
1049
1050
private:
1051
  SExpr* Ptr;
1052
};
1053
1054
/// Store a value to memory.
1055
/// The destination is a pointer to a field, the source is the value to store.
1056
class Store : public SExpr {
1057
public:
1058
0
  Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
1059
0
  Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1060
1061
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1062
1063
0
  SExpr *destination() { return Dest; }  // Address to store to
1064
0
  const SExpr *destination() const { return Dest; }
1065
1066
0
  SExpr *source() { return Source; }     // Value to store
1067
0
  const SExpr *source() const { return Source; }
1068
1069
  template <class V>
1070
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1071
    auto Np = Vs.traverse(Dest,   Vs.subExprCtx(Ctx));
1072
    auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
1073
    return Vs.reduceStore(*this, Np, Nv);
1074
  }
1075
1076
  template <class C>
1077
0
  typename C::CType compare(const Store* E, C& Cmp) const {
1078
0
    typename C::CType Ct = Cmp.compare(destination(), E->destination());
1079
0
    if (Cmp.notTrue(Ct))
1080
0
      return Ct;
1081
0
    return Cmp.compare(source(), E->source());
1082
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Store::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Store const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Store::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Store const*, clang::threadSafety::til::MatchComparator&) const
1083
1084
private:
1085
  SExpr* Dest;
1086
  SExpr* Source;
1087
};
1088
1089
/// If p is a reference to an array, then p[i] is a reference to the i'th
1090
/// element of the array.
1091
class ArrayIndex : public SExpr {
1092
public:
1093
48
  ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1094
  ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
1095
0
      : SExpr(E), Array(A), Index(N) {}
1096
1097
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1098
1099
0
  SExpr *array() { return Array; }
1100
440
  const SExpr *array() const { return Array; }
1101
1102
0
  SExpr *index() { return Index; }
1103
440
  const SExpr *index() const { return Index; }
1104
1105
  template <class V>
1106
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1107
    auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1108
    auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1109
    return Vs.reduceArrayIndex(*this, Na, Ni);
1110
  }
1111
1112
  template <class C>
1113
212
  typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1114
212
    typename C::CType Ct = Cmp.compare(array(), E->array());
1115
212
    if (Cmp.notTrue(Ct))
1116
0
      return Ct;
1117
212
    return Cmp.compare(index(), E->index());
1118
212
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::ArrayIndex::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::ArrayIndex const*, clang::threadSafety::til::EqualsComparator&) const
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::ArrayIndex::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::ArrayIndex const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
1113
212
  typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1114
212
    typename C::CType Ct = Cmp.compare(array(), E->array());
1115
212
    if (Cmp.notTrue(Ct))
1116
0
      return Ct;
1117
212
    return Cmp.compare(index(), E->index());
1118
212
  }
1119
1120
private:
1121
  SExpr* Array;
1122
  SExpr* Index;
1123
};
1124
1125
/// Pointer arithmetic, restricted to arrays only.
1126
/// If p is a reference to an array, then p + n, where n is an integer, is
1127
/// a reference to a subarray.
1128
class ArrayAdd : public SExpr {
1129
public:
1130
0
  ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1131
  ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1132
0
      : SExpr(E), Array(A), Index(N) {}
1133
1134
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1135
1136
0
  SExpr *array() { return Array; }
1137
0
  const SExpr *array() const { return Array; }
1138
1139
0
  SExpr *index() { return Index; }
1140
0
  const SExpr *index() const { return Index; }
1141
1142
  template <class V>
1143
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1144
    auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1145
    auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1146
    return Vs.reduceArrayAdd(*this, Na, Ni);
1147
  }
1148
1149
  template <class C>
1150
0
  typename C::CType compare(const ArrayAdd* E, C& Cmp) const {
1151
0
    typename C::CType Ct = Cmp.compare(array(), E->array());
1152
0
    if (Cmp.notTrue(Ct))
1153
0
      return Ct;
1154
0
    return Cmp.compare(index(), E->index());
1155
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::ArrayAdd::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::ArrayAdd const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::ArrayAdd::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::ArrayAdd const*, clang::threadSafety::til::MatchComparator&) const
1156
1157
private:
1158
  SExpr* Array;
1159
  SExpr* Index;
1160
};
1161
1162
/// Simple arithmetic unary operations, e.g. negate and not.
1163
/// These operations have no side-effects.
1164
class UnaryOp : public SExpr {
1165
public:
1166
0
  UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1167
0
    Flags = Op;
1168
0
  }
1169
1170
0
  UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1171
1172
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1173
1174
0
  TIL_UnaryOpcode unaryOpcode() const {
1175
0
    return static_cast<TIL_UnaryOpcode>(Flags);
1176
0
  }
1177
1178
0
  SExpr *expr() { return Expr0; }
1179
0
  const SExpr *expr() const { return Expr0; }
1180
1181
  template <class V>
1182
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1183
    auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1184
    return Vs.reduceUnaryOp(*this, Ne);
1185
  }
1186
1187
  template <class C>
1188
0
  typename C::CType compare(const UnaryOp* E, C& Cmp) const {
1189
0
    typename C::CType Ct =
1190
0
      Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
1191
0
    if (Cmp.notTrue(Ct))
1192
0
      return Ct;
1193
0
    return Cmp.compare(expr(), E->expr());
1194
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::UnaryOp::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::UnaryOp const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::UnaryOp::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::UnaryOp const*, clang::threadSafety::til::MatchComparator&) const
1195
1196
private:
1197
  SExpr* Expr0;
1198
};
1199
1200
/// Simple arithmetic binary operations, e.g. +, -, etc.
1201
/// These operations have no side effects.
1202
class BinaryOp : public SExpr {
1203
public:
1204
  BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
1205
36
      : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1206
36
    Flags = Op;
1207
36
  }
1208
1209
  BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1210
0
      : SExpr(B), Expr0(E0), Expr1(E1) {
1211
0
    Flags = B.Flags;
1212
0
  }
1213
1214
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1215
1216
368
  TIL_BinaryOpcode binaryOpcode() const {
1217
368
    return static_cast<TIL_BinaryOpcode>(Flags);
1218
368
  }
1219
1220
0
  SExpr *expr0() { return Expr0; }
1221
368
  const SExpr *expr0() const { return Expr0; }
1222
1223
0
  SExpr *expr1() { return Expr1; }
1224
368
  const SExpr *expr1() const { return Expr1; }
1225
1226
  template <class V>
1227
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1228
    auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1229
    auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
1230
    return Vs.reduceBinaryOp(*this, Ne0, Ne1);
1231
  }
1232
1233
  template <class C>
1234
180
  typename C::CType compare(const BinaryOp* E, C& Cmp) const {
1235
180
    typename C::CType Ct =
1236
180
      Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1237
180
    if (Cmp.notTrue(Ct))
1238
0
      return Ct;
1239
180
    Ct = Cmp.compare(expr0(), E->expr0());
1240
180
    if (Cmp.notTrue(Ct))
1241
0
      return Ct;
1242
180
    return Cmp.compare(expr1(), E->expr1());
1243
180
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::BinaryOp::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::BinaryOp const*, clang::threadSafety::til::EqualsComparator&) const
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::BinaryOp::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::BinaryOp const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
1234
180
  typename C::CType compare(const BinaryOp* E, C& Cmp) const {
1235
180
    typename C::CType Ct =
1236
180
      Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1237
180
    if (Cmp.notTrue(Ct))
1238
0
      return Ct;
1239
180
    Ct = Cmp.compare(expr0(), E->expr0());
1240
180
    if (Cmp.notTrue(Ct))
1241
0
      return Ct;
1242
180
    return Cmp.compare(expr1(), E->expr1());
1243
180
  }
1244
1245
private:
1246
  SExpr* Expr0;
1247
  SExpr* Expr1;
1248
};
1249
1250
/// Cast expressions.
1251
/// Cast expressions are essentially unary operations, but we treat them
1252
/// as a distinct AST node because they only change the type of the result.
1253
class Cast : public SExpr {
1254
public:
1255
392
  Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1256
0
  Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1257
1258
13.9k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1259
1260
888
  TIL_CastOpcode castOpcode() const {
1261
888
    return static_cast<TIL_CastOpcode>(Flags);
1262
888
  }
1263
1264
0
  SExpr *expr() { return Expr0; }
1265
792
  const SExpr *expr() const { return Expr0; }
1266
1267
  template <class V>
1268
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1269
    auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1270
    return Vs.reduceCast(*this, Ne);
1271
  }
1272
1273
  template <class C>
1274
248
  typename C::CType compare(const Cast* E, C& Cmp) const {
1275
248
    typename C::CType Ct =
1276
248
      Cmp.compareIntegers(castOpcode(), E->castOpcode());
1277
248
    if (Cmp.notTrue(Ct))
1278
0
      return Ct;
1279
248
    return Cmp.compare(expr(), E->expr());
1280
248
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Cast::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Cast const*, clang::threadSafety::til::EqualsComparator&) const
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Cast::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Cast const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
1274
248
  typename C::CType compare(const Cast* E, C& Cmp) const {
1275
248
    typename C::CType Ct =
1276
248
      Cmp.compareIntegers(castOpcode(), E->castOpcode());
1277
248
    if (Cmp.notTrue(Ct))
1278
0
      return Ct;
1279
248
    return Cmp.compare(expr(), E->expr());
1280
248
  }
1281
1282
private:
1283
  SExpr* Expr0;
1284
};
1285
1286
class SCFG;
1287
1288
/// Phi Node, for code in SSA form.
1289
/// Each Phi node has an array of possible values that it can take,
1290
/// depending on where control flow comes from.
1291
class Phi : public SExpr {
1292
public:
1293
  using ValArray = SimpleArray<SExpr *>;
1294
1295
  // In minimal SSA form, all Phi nodes are MultiVal.
1296
  // During conversion to SSA, incomplete Phi nodes may be introduced, which
1297
  // are later determined to be SingleVal, and are thus redundant.
1298
  enum Status {
1299
    PH_MultiVal = 0, // Phi node has multiple distinct values.  (Normal)
1300
    PH_SingleVal,    // Phi node has one distinct value, and can be eliminated
1301
    PH_Incomplete    // Phi node is incomplete
1302
  };
1303
1304
0
  Phi() : SExpr(COP_Phi) {}
1305
0
  Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals)  {}
1306
0
  Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
1307
1308
2.21k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1309
1310
0
  const ValArray &values() const { return Values; }
1311
0
  ValArray &values() { return Values; }
1312
1313
0
  Status status() const { return static_cast<Status>(Flags); }
1314
0
  void setStatus(Status s) { Flags = s; }
1315
1316
  /// Return the clang declaration of the variable for this Phi node, if any.
1317
0
  const ValueDecl *clangDecl() const { return Cvdecl; }
1318
1319
  /// Set the clang variable associated with this Phi node.
1320
0
  void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; }
1321
1322
  template <class V>
1323
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1324
    typename V::template Container<typename V::R_SExpr>
1325
      Nvs(Vs, Values.size());
1326
1327
    for (const auto *Val : Values)
1328
      Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
1329
    return Vs.reducePhi(*this, Nvs);
1330
  }
1331
1332
  template <class C>
1333
0
  typename C::CType compare(const Phi *E, C &Cmp) const {
1334
0
    // TODO: implement CFG comparisons
1335
0
    return Cmp.comparePointers(this, E);
1336
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Phi::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Phi const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Phi::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Phi const*, clang::threadSafety::til::MatchComparator&) const
1337
1338
private:
1339
  ValArray Values;
1340
  const ValueDecl* Cvdecl = nullptr;
1341
};
1342
1343
/// Base class for basic block terminators:  Branch, Goto, and Return.
1344
class Terminator : public SExpr {
1345
protected:
1346
0
  Terminator(TIL_Opcode Op) : SExpr(Op) {}
1347
0
  Terminator(const SExpr &E) : SExpr(E) {}
1348
1349
public:
1350
0
  static bool classof(const SExpr *E) {
1351
0
    return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
1352
0
  }
1353
1354
  /// Return the list of basic blocks that this terminator can branch to.
1355
  ArrayRef<BasicBlock *> successors();
1356
1357
0
  ArrayRef<BasicBlock *> successors() const {
1358
0
    return const_cast<Terminator*>(this)->successors();
1359
0
  }
1360
};
1361
1362
/// Jump to another basic block.
1363
/// A goto instruction is essentially a tail-recursive call into another
1364
/// block.  In addition to the block pointer, it specifies an index into the
1365
/// phi nodes of that block.  The index can be used to retrieve the "arguments"
1366
/// of the call.
1367
class Goto : public Terminator {
1368
public:
1369
  Goto(BasicBlock *B, unsigned I)
1370
0
      : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1371
  Goto(const Goto &G, BasicBlock *B, unsigned I)
1372
0
      : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1373
1374
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1375
1376
0
  const BasicBlock *targetBlock() const { return TargetBlock; }
1377
0
  BasicBlock *targetBlock() { return TargetBlock; }
1378
1379
  /// Returns the index into the
1380
0
  unsigned index() const { return Index; }
1381
1382
  /// Return the list of basic blocks that this terminator can branch to.
1383
0
  ArrayRef<BasicBlock *> successors() { return TargetBlock; }
1384
1385
  template <class V>
1386
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1387
    BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
1388
    return Vs.reduceGoto(*this, Ntb);
1389
  }
1390
1391
  template <class C>
1392
0
  typename C::CType compare(const Goto *E, C &Cmp) const {
1393
0
    // TODO: implement CFG comparisons
1394
0
    return Cmp.comparePointers(this, E);
1395
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Goto::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Goto const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Goto::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Goto const*, clang::threadSafety::til::MatchComparator&) const
1396
1397
private:
1398
  BasicBlock *TargetBlock;
1399
  unsigned Index;
1400
};
1401
1402
/// A conditional branch to two other blocks.
1403
/// Note that unlike Goto, Branch does not have an index.  The target blocks
1404
/// must be child-blocks, and cannot have Phi nodes.
1405
class Branch : public Terminator {
1406
public:
1407
  Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
1408
0
      : Terminator(COP_Branch), Condition(C) {
1409
0
    Branches[0] = T;
1410
0
    Branches[1] = E;
1411
0
  }
1412
1413
  Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
1414
0
      : Terminator(Br), Condition(C) {
1415
0
    Branches[0] = T;
1416
0
    Branches[1] = E;
1417
0
  }
1418
1419
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1420
1421
0
  const SExpr *condition() const { return Condition; }
1422
0
  SExpr *condition() { return Condition; }
1423
1424
0
  const BasicBlock *thenBlock() const { return Branches[0]; }
1425
0
  BasicBlock *thenBlock() { return Branches[0]; }
1426
1427
0
  const BasicBlock *elseBlock() const { return Branches[1]; }
1428
0
  BasicBlock *elseBlock() { return Branches[1]; }
1429
1430
  /// Return the list of basic blocks that this terminator can branch to.
1431
0
  ArrayRef<BasicBlock*> successors() {
1432
0
    return llvm::makeArrayRef(Branches);
1433
0
  }
1434
1435
  template <class V>
1436
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1437
    auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1438
    BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]);
1439
    BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]);
1440
    return Vs.reduceBranch(*this, Nc, Ntb, Nte);
1441
  }
1442
1443
  template <class C>
1444
0
  typename C::CType compare(const Branch *E, C &Cmp) const {
1445
0
    // TODO: implement CFG comparisons
1446
0
    return Cmp.comparePointers(this, E);
1447
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Branch::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Branch const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Branch::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Branch const*, clang::threadSafety::til::MatchComparator&) const
1448
1449
private:
1450
  SExpr *Condition;
1451
  BasicBlock *Branches[2];
1452
};
1453
1454
/// Return from the enclosing function, passing the return value to the caller.
1455
/// Only the exit block should end with a return statement.
1456
class Return : public Terminator {
1457
public:
1458
0
  Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
1459
0
  Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
1460
1461
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
1462
1463
  /// Return an empty list.
1464
0
  ArrayRef<BasicBlock *> successors() { return None; }
1465
1466
0
  SExpr *returnValue() { return Retval; }
1467
0
  const SExpr *returnValue() const { return Retval; }
1468
1469
  template <class V>
1470
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1471
    auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx));
1472
    return Vs.reduceReturn(*this, Ne);
1473
  }
1474
1475
  template <class C>
1476
0
  typename C::CType compare(const Return *E, C &Cmp) const {
1477
0
    return Cmp.compare(Retval, E->Retval);
1478
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Return::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Return const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Return::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Return const*, clang::threadSafety::til::MatchComparator&) const
1479
1480
private:
1481
  SExpr* Retval;
1482
};
1483
1484
inline ArrayRef<BasicBlock*> Terminator::successors() {
1485
  switch (opcode()) {
1486
    case COP_Goto:   return cast<Goto>(this)->successors();
1487
    case COP_Branch: return cast<Branch>(this)->successors();
1488
    case COP_Return: return cast<Return>(this)->successors();
1489
    default:
1490
      return None;
1491
  }
1492
}
1493
1494
/// A basic block is part of an SCFG.  It can be treated as a function in
1495
/// continuation passing style.  A block consists of a sequence of phi nodes,
1496
/// which are "arguments" to the function, followed by a sequence of
1497
/// instructions.  It ends with a Terminator, which is a Branch or Goto to
1498
/// another basic block in the same SCFG.
1499
class BasicBlock : public SExpr {
1500
public:
1501
  using InstrArray = SimpleArray<SExpr *>;
1502
  using BlockArray = SimpleArray<BasicBlock *>;
1503
1504
  // TopologyNodes are used to overlay tree structures on top of the CFG,
1505
  // such as dominator and postdominator trees.  Each block is assigned an
1506
  // ID in the tree according to a depth-first search.  Tree traversals are
1507
  // always up, towards the parents.
1508
  struct TopologyNode {
1509
    int NodeID = 0;
1510
1511
    // Includes this node, so must be > 1.
1512
    int SizeOfSubTree = 0;
1513
1514
    // Pointer to parent.
1515
    BasicBlock *Parent = nullptr;
1516
1517
0
    TopologyNode() = default;
1518
1519
0
    bool isParentOf(const TopologyNode& OtherNode) {
1520
0
      return OtherNode.NodeID > NodeID &&
1521
0
             OtherNode.NodeID < NodeID + SizeOfSubTree;
1522
0
    }
1523
1524
0
    bool isParentOfOrEqual(const TopologyNode& OtherNode) {
1525
0
      return OtherNode.NodeID >= NodeID &&
1526
0
             OtherNode.NodeID < NodeID + SizeOfSubTree;
1527
0
    }
1528
  };
1529
1530
  explicit BasicBlock(MemRegionRef A)
1531
0
      : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {}
1532
  BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is,
1533
             Terminator *T)
1534
      : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false),
1535
0
        Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
1536
1537
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
1538
1539
  /// Returns the block ID.  Every block has a unique ID in the CFG.
1540
0
  int blockID() const { return BlockID; }
1541
1542
  /// Returns the number of predecessors.
1543
0
  size_t numPredecessors() const { return Predecessors.size(); }
1544
0
  size_t numSuccessors() const { return successors().size(); }
1545
1546
0
  const SCFG* cfg() const { return CFGPtr; }
1547
0
  SCFG* cfg() { return CFGPtr; }
1548
1549
0
  const BasicBlock *parent() const { return DominatorNode.Parent; }
1550
0
  BasicBlock *parent() { return DominatorNode.Parent; }
1551
1552
0
  const InstrArray &arguments() const { return Args; }
1553
0
  InstrArray &arguments() { return Args; }
1554
1555
0
  InstrArray &instructions() { return Instrs; }
1556
0
  const InstrArray &instructions() const { return Instrs; }
1557
1558
  /// Returns a list of predecessors.
1559
  /// The order of predecessors in the list is important; each phi node has
1560
  /// exactly one argument for each precessor, in the same order.
1561
0
  BlockArray &predecessors() { return Predecessors; }
1562
0
  const BlockArray &predecessors() const { return Predecessors; }
1563
1564
0
  ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
1565
0
  ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
1566
1567
0
  const Terminator *terminator() const { return TermInstr; }
1568
0
  Terminator *terminator() { return TermInstr; }
1569
1570
0
  void setTerminator(Terminator *E) { TermInstr = E; }
1571
1572
0
  bool Dominates(const BasicBlock &Other) {
1573
0
    return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
1574
0
  }
1575
1576
0
  bool PostDominates(const BasicBlock &Other) {
1577
0
    return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
1578
0
  }
1579
1580
  /// Add a new argument.
1581
0
  void addArgument(Phi *V) {
1582
0
    Args.reserveCheck(1, Arena);
1583
0
    Args.push_back(V);
1584
0
  }
1585
1586
  /// Add a new instruction.
1587
0
  void addInstruction(SExpr *V) {
1588
0
    Instrs.reserveCheck(1, Arena);
1589
0
    Instrs.push_back(V);
1590
0
  }
1591
1592
  // Add a new predecessor, and return the phi-node index for it.
1593
  // Will add an argument to all phi-nodes, initialized to nullptr.
1594
  unsigned addPredecessor(BasicBlock *Pred);
1595
1596
  // Reserve space for Nargs arguments.
1597
0
  void reserveArguments(unsigned Nargs)   { Args.reserve(Nargs, Arena); }
1598
1599
  // Reserve space for Nins instructions.
1600
0
  void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
1601
1602
  // Reserve space for NumPreds predecessors, including space in phi nodes.
1603
  void reservePredecessors(unsigned NumPreds);
1604
1605
  /// Return the index of BB, or Predecessors.size if BB is not a predecessor.
1606
0
  unsigned findPredecessorIndex(const BasicBlock *BB) const {
1607
0
    auto I = llvm::find(Predecessors, BB);
1608
0
    return std::distance(Predecessors.cbegin(), I);
1609
0
  }
1610
1611
  template <class V>
1612
  typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
1613
    typename V::template Container<SExpr*> Nas(Vs, Args.size());
1614
    typename V::template Container<SExpr*> Nis(Vs, Instrs.size());
1615
1616
    // Entering the basic block should do any scope initialization.
1617
    Vs.enterBasicBlock(*this);
1618
1619
    for (const auto *E : Args) {
1620
      auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1621
      Nas.push_back(Ne);
1622
    }
1623
    for (const auto *E : Instrs) {
1624
      auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1625
      Nis.push_back(Ne);
1626
    }
1627
    auto Nt = Vs.traverse(TermInstr, Ctx);
1628
1629
    // Exiting the basic block should handle any scope cleanup.
1630
    Vs.exitBasicBlock(*this);
1631
1632
    return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
1633
  }
1634
1635
  template <class C>
1636
0
  typename C::CType compare(const BasicBlock *E, C &Cmp) const {
1637
0
    // TODO: implement CFG comparisons
1638
0
    return Cmp.comparePointers(this, E);
1639
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::BasicBlock::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::BasicBlock const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::BasicBlock::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::BasicBlock const*, clang::threadSafety::til::MatchComparator&) const
1640
1641
private:
1642
  friend class SCFG;
1643
1644
  // assign unique ids to all instructions
1645
  unsigned renumberInstrs(unsigned id);
1646
1647
  unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
1648
  unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
1649
  void computeDominator();
1650
  void computePostDominator();
1651
1652
  // The arena used to allocate this block.
1653
  MemRegionRef Arena;
1654
1655
  // The CFG that contains this block.
1656
  SCFG *CFGPtr = nullptr;
1657
1658
  // Unique ID for this BB in the containing CFG. IDs are in topological order.
1659
  unsigned BlockID : 31;
1660
1661
  // Bit to determine if a block has been visited during a traversal.
1662
  bool Visited : 1;
1663
1664
  // Predecessor blocks in the CFG.
1665
  BlockArray Predecessors;
1666
1667
  // Phi nodes. One argument per predecessor.
1668
  InstrArray Args;
1669
1670
  // Instructions.
1671
  InstrArray Instrs;
1672
1673
  // Terminating instruction.
1674
  Terminator *TermInstr = nullptr;
1675
1676
  // The dominator tree.
1677
  TopologyNode DominatorNode;
1678
1679
  // The post-dominator tree.
1680
  TopologyNode PostDominatorNode;
1681
};
1682
1683
/// An SCFG is a control-flow graph.  It consists of a set of basic blocks,
1684
/// each of which terminates in a branch to another basic block.  There is one
1685
/// entry point, and one exit point.
1686
class SCFG : public SExpr {
1687
public:
1688
  using BlockArray = SimpleArray<BasicBlock *>;
1689
  using iterator = BlockArray::iterator;
1690
  using const_iterator = BlockArray::const_iterator;
1691
1692
  SCFG(MemRegionRef A, unsigned Nblocks)
1693
0
      : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) {
1694
0
    Entry = new (A) BasicBlock(A);
1695
0
    Exit  = new (A) BasicBlock(A);
1696
0
    auto *V = new (A) Phi();
1697
0
    Exit->addArgument(V);
1698
0
    Exit->setTerminator(new (A) Return(V));
1699
0
    add(Entry);
1700
0
    add(Exit);
1701
0
  }
1702
1703
  SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1704
0
      : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) {
1705
0
    // TODO: set entry and exit!
1706
0
  }
1707
1708
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1709
1710
  /// Return true if this CFG is valid.
1711
0
  bool valid() const { return Entry && Exit && Blocks.size() > 0; }
1712
1713
  /// Return true if this CFG has been normalized.
1714
  /// After normalization, blocks are in topological order, and block and
1715
  /// instruction IDs have been assigned.
1716
0
  bool normal() const { return Normal; }
1717
1718
0
  iterator begin() { return Blocks.begin(); }
1719
0
  iterator end() { return Blocks.end(); }
1720
1721
0
  const_iterator begin() const { return cbegin(); }
1722
0
  const_iterator end() const { return cend(); }
1723
1724
0
  const_iterator cbegin() const { return Blocks.cbegin(); }
1725
0
  const_iterator cend() const { return Blocks.cend(); }
1726
1727
0
  const BasicBlock *entry() const { return Entry; }
1728
0
  BasicBlock *entry() { return Entry; }
1729
0
  const BasicBlock *exit() const { return Exit; }
1730
0
  BasicBlock *exit() { return Exit; }
1731
1732
  /// Return the number of blocks in the CFG.
1733
  /// Block::blockID() will return a number less than numBlocks();
1734
0
  size_t numBlocks() const { return Blocks.size(); }
1735
1736
  /// Return the total number of instructions in the CFG.
1737
  /// This is useful for building instruction side-tables;
1738
  /// A call to SExpr::id() will return a number less than numInstructions().
1739
0
  unsigned numInstructions() { return NumInstructions; }
1740
1741
0
  inline void add(BasicBlock *BB) {
1742
0
    assert(BB->CFGPtr == nullptr);
1743
0
    BB->CFGPtr = this;
1744
0
    Blocks.reserveCheck(1, Arena);
1745
0
    Blocks.push_back(BB);
1746
0
  }
1747
1748
0
  void setEntry(BasicBlock *BB) { Entry = BB; }
1749
0
  void setExit(BasicBlock *BB)  { Exit = BB;  }
1750
1751
  void computeNormalForm();
1752
1753
  template <class V>
1754
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1755
    Vs.enterCFG(*this);
1756
    typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
1757
1758
    for (const auto *B : Blocks) {
1759
      Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
1760
    }
1761
    Vs.exitCFG(*this);
1762
    return Vs.reduceSCFG(*this, Bbs);
1763
  }
1764
1765
  template <class C>
1766
0
  typename C::CType compare(const SCFG *E, C &Cmp) const {
1767
0
    // TODO: implement CFG comparisons
1768
0
    return Cmp.comparePointers(this, E);
1769
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::SCFG::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::SCFG const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::SCFG::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::SCFG const*, clang::threadSafety::til::MatchComparator&) const
1770
1771
private:
1772
  // assign unique ids to all instructions
1773
  void renumberInstrs();
1774
1775
  MemRegionRef Arena;
1776
  BlockArray Blocks;
1777
  BasicBlock *Entry = nullptr;
1778
  BasicBlock *Exit = nullptr;
1779
  unsigned NumInstructions = 0;
1780
  bool Normal = false;
1781
};
1782
1783
/// An identifier, e.g. 'foo' or 'x'.
1784
/// This is a pseduo-term; it will be lowered to a variable or projection.
1785
class Identifier : public SExpr {
1786
public:
1787
0
  Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {}
1788
  Identifier(const Identifier &) = default;
1789
1790
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1791
1792
0
  StringRef name() const { return Name; }
1793
1794
  template <class V>
1795
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1796
    return Vs.reduceIdentifier(*this);
1797
  }
1798
1799
  template <class C>
1800
0
  typename C::CType compare(const Identifier* E, C& Cmp) const {
1801
0
    return Cmp.compareStrings(name(), E->name());
1802
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Identifier::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Identifier const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Identifier::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Identifier const*, clang::threadSafety::til::MatchComparator&) const
1803
1804
private:
1805
  StringRef Name;
1806
};
1807
1808
/// An if-then-else expression.
1809
/// This is a pseduo-term; it will be lowered to a branch in a CFG.
1810
class IfThenElse : public SExpr {
1811
public:
1812
  IfThenElse(SExpr *C, SExpr *T, SExpr *E)
1813
24
      : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {}
1814
  IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
1815
0
      : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {}
1816
1817
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1818
1819
0
  SExpr *condition() { return Condition; }   // Address to store to
1820
224
  const SExpr *condition() const { return Condition; }
1821
1822
0
  SExpr *thenExpr() { return ThenExpr; }     // Value to store
1823
224
  const SExpr *thenExpr() const { return ThenExpr; }
1824
1825
0
  SExpr *elseExpr() { return ElseExpr; }     // Value to store
1826
216
  const SExpr *elseExpr() const { return ElseExpr; }
1827
1828
  template <class V>
1829
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1830
    auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1831
    auto Nt = Vs.traverse(ThenExpr,  Vs.subExprCtx(Ctx));
1832
    auto Ne = Vs.traverse(ElseExpr,  Vs.subExprCtx(Ctx));
1833
    return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
1834
  }
1835
1836
  template <class C>
1837
108
  typename C::CType compare(const IfThenElse* E, C& Cmp) const {
1838
108
    typename C::CType Ct = Cmp.compare(condition(), E->condition());
1839
108
    if (Cmp.notTrue(Ct))
1840
0
      return Ct;
1841
108
    Ct = Cmp.compare(thenExpr(), E->thenExpr());
1842
108
    if (Cmp.notTrue(Ct))
1843
4
      return Ct;
1844
104
    return Cmp.compare(elseExpr(), E->elseExpr());
1845
104
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::IfThenElse::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::IfThenElse const*, clang::threadSafety::til::EqualsComparator&) const
clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::IfThenElse::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::IfThenElse const*, clang::threadSafety::til::MatchComparator&) const
Line
Count
Source
1837
108
  typename C::CType compare(const IfThenElse* E, C& Cmp) const {
1838
108
    typename C::CType Ct = Cmp.compare(condition(), E->condition());
1839
108
    if (Cmp.notTrue(Ct))
1840
0
      return Ct;
1841
108
    Ct = Cmp.compare(thenExpr(), E->thenExpr());
1842
108
    if (Cmp.notTrue(Ct))
1843
4
      return Ct;
1844
104
    return Cmp.compare(elseExpr(), E->elseExpr());
1845
104
  }
1846
1847
private:
1848
  SExpr* Condition;
1849
  SExpr* ThenExpr;
1850
  SExpr* ElseExpr;
1851
};
1852
1853
/// A let-expression,  e.g.  let x=t; u.
1854
/// This is a pseduo-term; it will be lowered to instructions in a CFG.
1855
class Let : public SExpr {
1856
public:
1857
0
  Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1858
0
    Vd->setKind(Variable::VK_Let);
1859
0
  }
1860
1861
0
  Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1862
0
    Vd->setKind(Variable::VK_Let);
1863
0
  }
1864
1865
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1866
1867
0
  Variable *variableDecl()  { return VarDecl; }
1868
0
  const Variable *variableDecl() const { return VarDecl; }
1869
1870
0
  SExpr *body() { return Body; }
1871
0
  const SExpr *body() const { return Body; }
1872
1873
  template <class V>
1874
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1875
    // This is a variable declaration, so traverse the definition.
1876
    auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
1877
    // Tell the rewriter to enter the scope of the let variable.
1878
    Variable *Nvd = Vs.enterScope(*VarDecl, E0);
1879
    auto E1 = Vs.traverse(Body, Ctx);
1880
    Vs.exitScope(*VarDecl);
1881
    return Vs.reduceLet(*this, Nvd, E1);
1882
  }
1883
1884
  template <class C>
1885
0
  typename C::CType compare(const Let* E, C& Cmp) const {
1886
0
    typename C::CType Ct =
1887
0
      Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
1888
0
    if (Cmp.notTrue(Ct))
1889
0
      return Ct;
1890
0
    Cmp.enterScope(variableDecl(), E->variableDecl());
1891
0
    Ct = Cmp.compare(body(), E->body());
1892
0
    Cmp.leaveScope();
1893
0
    return Ct;
1894
0
  }
Unexecuted instantiation: clang::threadSafety::til::EqualsComparator::CType clang::threadSafety::til::Let::compare<clang::threadSafety::til::EqualsComparator>(clang::threadSafety::til::Let const*, clang::threadSafety::til::EqualsComparator&) const
Unexecuted instantiation: clang::threadSafety::til::MatchComparator::CType clang::threadSafety::til::Let::compare<clang::threadSafety::til::MatchComparator>(clang::threadSafety::til::Let const*, clang::threadSafety::til::MatchComparator&) const
1895
1896
private:
1897
  Variable *VarDecl;
1898
  SExpr* Body;
1899
};
1900
1901
const SExpr *getCanonicalVal(const SExpr *E);
1902
SExpr* simplifyToCanonicalVal(SExpr *E);
1903
void simplifyIncompleteArg(til::Phi *Ph);
1904
1905
} // namespace til
1906
} // namespace threadSafety
1907
1908
} // namespace clang
1909
1910
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H