Coverage Report

Created: 2021-01-23 06:44

/Users/buildslave/jenkins/workspace/coverage/llvm-project/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
451k
  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.4k
  void *operator new(size_t S, MemRegionRef &R) {
298
20.4k
    return ::operator new(S, R);
299
20.4k
  }
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
5.12k
  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.4k
  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.17k
        Definition(D), Cvdecl(Cvd) {
376
2.17k
    Flags = VK_Let;
377
2.17k
  }
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
38.3k
  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.06k
  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.17k
  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
8.11k
  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
29.6k
  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
9.27k
  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
    // 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
    // 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.44k
  LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {
638
4.44k
    assert(D && "ValueDecl must not be null");
639
4.44k
  }
640
  LiteralPtr(const LiteralPtr &) = default;
641
642
32.3k
  static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
643
644
  // The clang declaration for the value that this pointer points to.
645
5.13k
  const ValueDecl *clangDecl() const { return Cvdecl; }
646
647
  template <class V>
648
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
649
    return Vs.reduceLiteralPtr(*this);
650
  }
651
652
  template <class C>
653
11.1k
  typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
654
11.1k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
655
11.1k
  }
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
653
1.22k
  typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
654
1.22k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
655
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
653
9.93k
  typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
654
9.93k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
655
9.93k
  }
656
657
private:
658
  const ValueDecl *Cvdecl;
659
};
660
661
/// A function -- a.k.a. lambda abstraction.
662
/// Functions with multiple arguments are created by currying,
663
/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y })))
664
class Function : public SExpr {
665
public:
666
  Function(Variable *Vd, SExpr *Bd)
667
0
      : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
668
0
    Vd->setKind(Variable::VK_Fun);
669
0
  }
670
671
  Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
672
0
      : SExpr(F), VarDecl(Vd), Body(Bd) {
673
0
    Vd->setKind(Variable::VK_Fun);
674
0
  }
675
676
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
677
678
0
  Variable *variableDecl()  { return VarDecl; }
679
0
  const Variable *variableDecl() const { return VarDecl; }
680
681
0
  SExpr *body() { return Body; }
682
0
  const SExpr *body() const { return Body; }
683
684
  template <class V>
685
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
686
    // This is a variable declaration, so traverse the definition.
687
    auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx));
688
    // Tell the rewriter to enter the scope of the function.
689
    Variable *Nvd = Vs.enterScope(*VarDecl, E0);
690
    auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
691
    Vs.exitScope(*VarDecl);
692
    return Vs.reduceFunction(*this, Nvd, E1);
693
  }
694
695
  template <class C>
696
0
  typename C::CType compare(const Function* E, C& Cmp) const {
697
0
    typename C::CType Ct =
698
0
      Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
699
0
    if (Cmp.notTrue(Ct))
700
0
      return Ct;
701
0
    Cmp.enterScope(variableDecl(), E->variableDecl());
702
0
    Ct = Cmp.compare(body(), E->body());
703
0
    Cmp.leaveScope();
704
0
    return Ct;
705
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
706
707
private:
708
  Variable *VarDecl;
709
  SExpr* Body;
710
};
711
712
/// A self-applicable function.
713
/// A self-applicable function can be applied to itself.  It's useful for
714
/// implementing objects and late binding.
715
class SFunction : public SExpr {
716
public:
717
  SFunction(Variable *Vd, SExpr *B)
718
0
      : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
719
0
    assert(Vd->Definition == nullptr);
720
0
    Vd->setKind(Variable::VK_SFun);
721
0
    Vd->Definition = this;
722
0
  }
723
724
  SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
725
0
      : SExpr(F), VarDecl(Vd), Body(B) {
726
0
    assert(Vd->Definition == nullptr);
727
0
    Vd->setKind(Variable::VK_SFun);
728
0
    Vd->Definition = this;
729
0
  }
730
731
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
732
733
0
  Variable *variableDecl() { return VarDecl; }
734
0
  const Variable *variableDecl() const { return VarDecl; }
735
736
0
  SExpr *body() { return Body; }
737
0
  const SExpr *body() const { return Body; }
738
739
  template <class V>
740
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
741
    // A self-variable points to the SFunction itself.
742
    // A rewrite must introduce the variable with a null definition, and update
743
    // it after 'this' has been rewritten.
744
    Variable *Nvd = Vs.enterScope(*VarDecl, nullptr);
745
    auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx));
746
    Vs.exitScope(*VarDecl);
747
    // A rewrite operation will call SFun constructor to set Vvd->Definition.
748
    return Vs.reduceSFunction(*this, Nvd, E1);
749
  }
750
751
  template <class C>
752
0
  typename C::CType compare(const SFunction* E, C& Cmp) const {
753
0
    Cmp.enterScope(variableDecl(), E->variableDecl());
754
0
    typename C::CType Ct = Cmp.compare(body(), E->body());
755
0
    Cmp.leaveScope();
756
0
    return Ct;
757
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
758
759
private:
760
  Variable *VarDecl;
761
  SExpr* Body;
762
};
763
764
/// A block of code -- e.g. the body of a function.
765
class Code : public SExpr {
766
public:
767
0
  Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
768
  Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
769
0
      : SExpr(C), ReturnType(T), Body(B) {}
770
771
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
772
773
0
  SExpr *returnType() { return ReturnType; }
774
0
  const SExpr *returnType() const { return ReturnType; }
775
776
0
  SExpr *body() { return Body; }
777
0
  const SExpr *body() const { return Body; }
778
779
  template <class V>
780
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
781
    auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx));
782
    auto Nb = Vs.traverse(Body,       Vs.lazyCtx(Ctx));
783
    return Vs.reduceCode(*this, Nt, Nb);
784
  }
785
786
  template <class C>
787
0
  typename C::CType compare(const Code* E, C& Cmp) const {
788
0
    typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
789
0
    if (Cmp.notTrue(Ct))
790
0
      return Ct;
791
0
    return Cmp.compare(body(), E->body());
792
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
793
794
private:
795
  SExpr* ReturnType;
796
  SExpr* Body;
797
};
798
799
/// A typed, writable location in memory
800
class Field : public SExpr {
801
public:
802
0
  Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
803
  Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
804
0
      : SExpr(C), Range(R), Body(B) {}
805
806
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
807
808
0
  SExpr *range() { return Range; }
809
0
  const SExpr *range() const { return Range; }
810
811
0
  SExpr *body() { return Body; }
812
0
  const SExpr *body() const { return Body; }
813
814
  template <class V>
815
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
816
    auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx));
817
    auto Nb = Vs.traverse(Body,  Vs.lazyCtx(Ctx));
818
    return Vs.reduceField(*this, Nr, Nb);
819
  }
820
821
  template <class C>
822
0
  typename C::CType compare(const Field* E, C& Cmp) const {
823
0
    typename C::CType Ct = Cmp.compare(range(), E->range());
824
0
    if (Cmp.notTrue(Ct))
825
0
      return Ct;
826
0
    return Cmp.compare(body(), E->body());
827
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
828
829
private:
830
  SExpr* Range;
831
  SExpr* Body;
832
};
833
834
/// Apply an argument to a function.
835
/// Note that this does not actually call the function.  Functions are curried,
836
/// so this returns a closure in which the first parameter has been applied.
837
/// Once all parameters have been applied, Call can be used to invoke the
838
/// function.
839
class Apply : public SExpr {
840
public:
841
200
  Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
842
  Apply(const Apply &A, SExpr *F, SExpr *Ar)  // rewrite constructor
843
0
      : SExpr(A), Fun(F), Arg(Ar) {}
844
845
2.71k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
846
847
0
  SExpr *fun() { return Fun; }
848
2.71k
  const SExpr *fun() const { return Fun; }
849
850
0
  SExpr *arg() { return Arg; }
851
2.04k
  const SExpr *arg() const { return Arg; }
852
853
  template <class V>
854
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
855
    auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx));
856
    auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx));
857
    return Vs.reduceApply(*this, Nf, Na);
858
  }
859
860
  template <class C>
861
1.33k
  typename C::CType compare(const Apply* E, C& Cmp) const {
862
1.33k
    typename C::CType Ct = Cmp.compare(fun(), E->fun());
863
1.33k
    if (Cmp.notTrue(Ct))
864
336
      return Ct;
865
1.00k
    return Cmp.compare(arg(), E->arg());
866
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
861
1.33k
  typename C::CType compare(const Apply* E, C& Cmp) const {
862
1.33k
    typename C::CType Ct = Cmp.compare(fun(), E->fun());
863
1.33k
    if (Cmp.notTrue(Ct))
864
336
      return Ct;
865
1.00k
    return Cmp.compare(arg(), E->arg());
866
1.00k
  }
867
868
private:
869
  SExpr* Fun;
870
  SExpr* Arg;
871
};
872
873
/// Apply a self-argument to a self-applicable function.
874
class SApply : public SExpr {
875
public:
876
6.30k
  SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {}
877
  SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor
878
0
      : SExpr(A), Sfun(Sf), Arg(Ar) {}
879
880
26.9k
  static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
881
882
0
  SExpr *sfun() { return Sfun; }
883
24.2k
  const SExpr *sfun() const { return Sfun; }
884
885
0
  SExpr *arg() { return Arg ? Arg : Sfun; }
886
28.1k
  const SExpr *arg() const { return Arg ? 
Arg0
: Sfun; }
887
888
2.67k
  bool isDelegation() const { return Arg != nullptr; }
889
890
  template <class V>
891
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
892
    auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx));
893
    typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx))
894
                                       : nullptr;
895
    return Vs.reduceSApply(*this, Nf, Na);
896
  }
897
898
  template <class C>
899
10.5k
  typename C::CType compare(const SApply* E, C& Cmp) const {
900
10.5k
    typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
901
10.5k
    if (Cmp.notTrue(Ct) || 
(9.39k
!arg()9.39k
&&
!E->arg()0
))
902
1.10k
      return Ct;
903
9.39k
    return Cmp.compare(arg(), E->arg());
904
9.39k
  }
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
899
1.03k
  typename C::CType compare(const SApply* E, C& Cmp) const {
900
1.03k
    typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
901
1.03k
    if (Cmp.notTrue(Ct) || 
(1.01k
!arg()1.01k
&&
!E->arg()0
))
902
16
      return Ct;
903
1.01k
    return Cmp.compare(arg(), E->arg());
904
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
899
9.47k
  typename C::CType compare(const SApply* E, C& Cmp) const {
900
9.47k
    typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
901
9.47k
    if (Cmp.notTrue(Ct) || 
(8.38k
!arg()8.38k
&&
!E->arg()0
))
902
1.09k
      return Ct;
903
8.38k
    return Cmp.compare(arg(), E->arg());
904
8.38k
  }
905
906
private:
907
  SExpr* Sfun;
908
  SExpr* Arg;
909
};
910
911
/// Project a named slot from a C++ struct or class.
912
class Project : public SExpr {
913
public:
914
  Project(SExpr *R, const ValueDecl *Cvd)
915
6.39k
      : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {
916
6.39k
    assert(Cvd && "ValueDecl must not be null");
917
6.39k
  }
918
919
33.8k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
920
921
0
  SExpr *record() { return Rec; }
922
25.0k
  const SExpr *record() const { return Rec; }
923
924
3.03k
  const ValueDecl *clangDecl() const { return Cvdecl; }
925
926
518
  bool isArrow() const { return (Flags & 0x01) != 0; }
927
928
786
  void setArrow(bool b) {
929
786
    if (b) Flags |= 0x01;
930
0
    else Flags &= 0xFFFE;
931
786
  }
932
933
2.67k
  StringRef slotName() const {
934
2.67k
    if (Cvdecl->getDeclName().isIdentifier())
935
2.67k
      return Cvdecl->getName();
936
0
    if (!SlotName) {
937
0
      SlotName = "";
938
0
      llvm::raw_string_ostream OS(*SlotName);
939
0
      Cvdecl->printName(OS);
940
0
    }
941
0
    return *SlotName;
942
0
  }
943
944
  template <class V>
945
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
946
    auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx));
947
    return Vs.reduceProject(*this, Nr);
948
  }
949
950
  template <class C>
951
10.6k
  typename C::CType compare(const Project* E, C& Cmp) const {
952
10.6k
    typename C::CType Ct = Cmp.compare(record(), E->record());
953
10.6k
    if (Cmp.notTrue(Ct))
954
1.10k
      return Ct;
955
9.54k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
956
9.54k
  }
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
951
1.03k
  typename C::CType compare(const Project* E, C& Cmp) const {
952
1.03k
    typename C::CType Ct = Cmp.compare(record(), E->record());
953
1.03k
    if (Cmp.notTrue(Ct))
954
16
      return Ct;
955
1.01k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
956
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
951
9.61k
  typename C::CType compare(const Project* E, C& Cmp) const {
952
9.61k
    typename C::CType Ct = Cmp.compare(record(), E->record());
953
9.61k
    if (Cmp.notTrue(Ct))
954
1.09k
      return Ct;
955
8.52k
    return Cmp.comparePointers(Cvdecl, E->Cvdecl);
956
8.52k
  }
957
958
private:
959
  SExpr* Rec;
960
  mutable llvm::Optional<std::string> SlotName;
961
  const ValueDecl *Cvdecl;
962
};
963
964
/// Call a function (after all arguments have been applied).
965
class Call : public SExpr {
966
public:
967
  Call(SExpr *T, const CallExpr *Ce = nullptr)
968
200
      : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
969
0
  Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
970
971
2.93k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
972
973
0
  SExpr *target() { return Target; }
974
2.93k
  const SExpr *target() const { return Target; }
975
976
0
  const CallExpr *clangCallExpr() const { return Cexpr; }
977
978
  template <class V>
979
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
980
    auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx));
981
    return Vs.reduceCall(*this, Nt);
982
  }
983
984
  template <class C>
985
1.44k
  typename C::CType compare(const Call* E, C& Cmp) const {
986
1.44k
    return Cmp.compare(target(), E->target());
987
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
985
1.44k
  typename C::CType compare(const Call* E, C& Cmp) const {
986
1.44k
    return Cmp.compare(target(), E->target());
987
1.44k
  }
988
989
private:
990
  SExpr* Target;
991
  const CallExpr *Cexpr;
992
};
993
994
/// Allocate memory for a new value on the heap or stack.
995
class Alloc : public SExpr {
996
public:
997
  enum AllocKind {
998
    AK_Stack,
999
    AK_Heap
1000
  };
1001
1002
0
  Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1003
0
  Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1004
1005
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1006
1007
0
  AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1008
1009
0
  SExpr *dataType() { return Dtype; }
1010
0
  const SExpr *dataType() const { return Dtype; }
1011
1012
  template <class V>
1013
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1014
    auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx));
1015
    return Vs.reduceAlloc(*this, Nd);
1016
  }
1017
1018
  template <class C>
1019
0
  typename C::CType compare(const Alloc* E, C& Cmp) const {
1020
0
    typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
1021
0
    if (Cmp.notTrue(Ct))
1022
0
      return Ct;
1023
0
    return Cmp.compare(dataType(), E->dataType());
1024
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
1025
1026
private:
1027
  SExpr* Dtype;
1028
};
1029
1030
/// Load a value from memory.
1031
class Load : public SExpr {
1032
public:
1033
0
  Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1034
0
  Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1035
1036
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1037
1038
0
  SExpr *pointer() { return Ptr; }
1039
0
  const SExpr *pointer() const { return Ptr; }
1040
1041
  template <class V>
1042
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1043
    auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx));
1044
    return Vs.reduceLoad(*this, Np);
1045
  }
1046
1047
  template <class C>
1048
0
  typename C::CType compare(const Load* E, C& Cmp) const {
1049
0
    return Cmp.compare(pointer(), E->pointer());
1050
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
1051
1052
private:
1053
  SExpr* Ptr;
1054
};
1055
1056
/// Store a value to memory.
1057
/// The destination is a pointer to a field, the source is the value to store.
1058
class Store : public SExpr {
1059
public:
1060
0
  Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
1061
0
  Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1062
1063
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1064
1065
0
  SExpr *destination() { return Dest; }  // Address to store to
1066
0
  const SExpr *destination() const { return Dest; }
1067
1068
0
  SExpr *source() { return Source; }     // Value to store
1069
0
  const SExpr *source() const { return Source; }
1070
1071
  template <class V>
1072
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1073
    auto Np = Vs.traverse(Dest,   Vs.subExprCtx(Ctx));
1074
    auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
1075
    return Vs.reduceStore(*this, Np, Nv);
1076
  }
1077
1078
  template <class C>
1079
0
  typename C::CType compare(const Store* E, C& Cmp) const {
1080
0
    typename C::CType Ct = Cmp.compare(destination(), E->destination());
1081
0
    if (Cmp.notTrue(Ct))
1082
0
      return Ct;
1083
0
    return Cmp.compare(source(), E->source());
1084
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
1085
1086
private:
1087
  SExpr* Dest;
1088
  SExpr* Source;
1089
};
1090
1091
/// If p is a reference to an array, then p[i] is a reference to the i'th
1092
/// element of the array.
1093
class ArrayIndex : public SExpr {
1094
public:
1095
48
  ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1096
  ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
1097
0
      : SExpr(E), Array(A), Index(N) {}
1098
1099
440
  static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1100
1101
0
  SExpr *array() { return Array; }
1102
440
  const SExpr *array() const { return Array; }
1103
1104
0
  SExpr *index() { return Index; }
1105
440
  const SExpr *index() const { return Index; }
1106
1107
  template <class V>
1108
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1109
    auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1110
    auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1111
    return Vs.reduceArrayIndex(*this, Na, Ni);
1112
  }
1113
1114
  template <class C>
1115
212
  typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1116
212
    typename C::CType Ct = Cmp.compare(array(), E->array());
1117
212
    if (Cmp.notTrue(Ct))
1118
0
      return Ct;
1119
212
    return Cmp.compare(index(), E->index());
1120
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
1115
212
  typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1116
212
    typename C::CType Ct = Cmp.compare(array(), E->array());
1117
212
    if (Cmp.notTrue(Ct))
1118
0
      return Ct;
1119
212
    return Cmp.compare(index(), E->index());
1120
212
  }
1121
1122
private:
1123
  SExpr* Array;
1124
  SExpr* Index;
1125
};
1126
1127
/// Pointer arithmetic, restricted to arrays only.
1128
/// If p is a reference to an array, then p + n, where n is an integer, is
1129
/// a reference to a subarray.
1130
class ArrayAdd : public SExpr {
1131
public:
1132
0
  ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1133
  ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1134
0
      : SExpr(E), Array(A), Index(N) {}
1135
1136
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1137
1138
0
  SExpr *array() { return Array; }
1139
0
  const SExpr *array() const { return Array; }
1140
1141
0
  SExpr *index() { return Index; }
1142
0
  const SExpr *index() const { return Index; }
1143
1144
  template <class V>
1145
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1146
    auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1147
    auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1148
    return Vs.reduceArrayAdd(*this, Na, Ni);
1149
  }
1150
1151
  template <class C>
1152
0
  typename C::CType compare(const ArrayAdd* E, C& Cmp) const {
1153
0
    typename C::CType Ct = Cmp.compare(array(), E->array());
1154
0
    if (Cmp.notTrue(Ct))
1155
0
      return Ct;
1156
0
    return Cmp.compare(index(), E->index());
1157
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
1158
1159
private:
1160
  SExpr* Array;
1161
  SExpr* Index;
1162
};
1163
1164
/// Simple arithmetic unary operations, e.g. negate and not.
1165
/// These operations have no side-effects.
1166
class UnaryOp : public SExpr {
1167
public:
1168
0
  UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1169
0
    Flags = Op;
1170
0
  }
1171
1172
0
  UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1173
1174
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1175
1176
0
  TIL_UnaryOpcode unaryOpcode() const {
1177
0
    return static_cast<TIL_UnaryOpcode>(Flags);
1178
0
  }
1179
1180
0
  SExpr *expr() { return Expr0; }
1181
0
  const SExpr *expr() const { return Expr0; }
1182
1183
  template <class V>
1184
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1185
    auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1186
    return Vs.reduceUnaryOp(*this, Ne);
1187
  }
1188
1189
  template <class C>
1190
0
  typename C::CType compare(const UnaryOp* E, C& Cmp) const {
1191
0
    typename C::CType Ct =
1192
0
      Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
1193
0
    if (Cmp.notTrue(Ct))
1194
0
      return Ct;
1195
0
    return Cmp.compare(expr(), E->expr());
1196
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
1197
1198
private:
1199
  SExpr* Expr0;
1200
};
1201
1202
/// Simple arithmetic binary operations, e.g. +, -, etc.
1203
/// These operations have no side effects.
1204
class BinaryOp : public SExpr {
1205
public:
1206
  BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
1207
36
      : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1208
36
    Flags = Op;
1209
36
  }
1210
1211
  BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1212
0
      : SExpr(B), Expr0(E0), Expr1(E1) {
1213
0
    Flags = B.Flags;
1214
0
  }
1215
1216
368
  static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1217
1218
368
  TIL_BinaryOpcode binaryOpcode() const {
1219
368
    return static_cast<TIL_BinaryOpcode>(Flags);
1220
368
  }
1221
1222
0
  SExpr *expr0() { return Expr0; }
1223
368
  const SExpr *expr0() const { return Expr0; }
1224
1225
0
  SExpr *expr1() { return Expr1; }
1226
368
  const SExpr *expr1() const { return Expr1; }
1227
1228
  template <class V>
1229
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1230
    auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1231
    auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx));
1232
    return Vs.reduceBinaryOp(*this, Ne0, Ne1);
1233
  }
1234
1235
  template <class C>
1236
180
  typename C::CType compare(const BinaryOp* E, C& Cmp) const {
1237
180
    typename C::CType Ct =
1238
180
      Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1239
180
    if (Cmp.notTrue(Ct))
1240
0
      return Ct;
1241
180
    Ct = Cmp.compare(expr0(), E->expr0());
1242
180
    if (Cmp.notTrue(Ct))
1243
0
      return Ct;
1244
180
    return Cmp.compare(expr1(), E->expr1());
1245
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
1236
180
  typename C::CType compare(const BinaryOp* E, C& Cmp) const {
1237
180
    typename C::CType Ct =
1238
180
      Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1239
180
    if (Cmp.notTrue(Ct))
1240
0
      return Ct;
1241
180
    Ct = Cmp.compare(expr0(), E->expr0());
1242
180
    if (Cmp.notTrue(Ct))
1243
0
      return Ct;
1244
180
    return Cmp.compare(expr1(), E->expr1());
1245
180
  }
1246
1247
private:
1248
  SExpr* Expr0;
1249
  SExpr* Expr1;
1250
};
1251
1252
/// Cast expressions.
1253
/// Cast expressions are essentially unary operations, but we treat them
1254
/// as a distinct AST node because they only change the type of the result.
1255
class Cast : public SExpr {
1256
public:
1257
424
  Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1258
0
  Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1259
1260
15.4k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1261
1262
1.20k
  TIL_CastOpcode castOpcode() const {
1263
1.20k
    return static_cast<TIL_CastOpcode>(Flags);
1264
1.20k
  }
1265
1266
0
  SExpr *expr() { return Expr0; }
1267
1.08k
  const SExpr *expr() const { return Expr0; }
1268
1269
  template <class V>
1270
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1271
    auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx));
1272
    return Vs.reduceCast(*this, Ne);
1273
  }
1274
1275
  template <class C>
1276
392
  typename C::CType compare(const Cast* E, C& Cmp) const {
1277
392
    typename C::CType Ct =
1278
392
      Cmp.compareIntegers(castOpcode(), E->castOpcode());
1279
392
    if (Cmp.notTrue(Ct))
1280
0
      return Ct;
1281
392
    return Cmp.compare(expr(), E->expr());
1282
392
  }
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
1276
392
  typename C::CType compare(const Cast* E, C& Cmp) const {
1277
392
    typename C::CType Ct =
1278
392
      Cmp.compareIntegers(castOpcode(), E->castOpcode());
1279
392
    if (Cmp.notTrue(Ct))
1280
0
      return Ct;
1281
392
    return Cmp.compare(expr(), E->expr());
1282
392
  }
1283
1284
private:
1285
  SExpr* Expr0;
1286
};
1287
1288
class SCFG;
1289
1290
/// Phi Node, for code in SSA form.
1291
/// Each Phi node has an array of possible values that it can take,
1292
/// depending on where control flow comes from.
1293
class Phi : public SExpr {
1294
public:
1295
  using ValArray = SimpleArray<SExpr *>;
1296
1297
  // In minimal SSA form, all Phi nodes are MultiVal.
1298
  // During conversion to SSA, incomplete Phi nodes may be introduced, which
1299
  // are later determined to be SingleVal, and are thus redundant.
1300
  enum Status {
1301
    PH_MultiVal = 0, // Phi node has multiple distinct values.  (Normal)
1302
    PH_SingleVal,    // Phi node has one distinct value, and can be eliminated
1303
    PH_Incomplete    // Phi node is incomplete
1304
  };
1305
1306
0
  Phi() : SExpr(COP_Phi) {}
1307
0
  Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals)  {}
1308
0
  Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
1309
1310
2.24k
  static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1311
1312
0
  const ValArray &values() const { return Values; }
1313
0
  ValArray &values() { return Values; }
1314
1315
0
  Status status() const { return static_cast<Status>(Flags); }
1316
0
  void setStatus(Status s) { Flags = s; }
1317
1318
  /// Return the clang declaration of the variable for this Phi node, if any.
1319
0
  const ValueDecl *clangDecl() const { return Cvdecl; }
1320
1321
  /// Set the clang variable associated with this Phi node.
1322
0
  void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; }
1323
1324
  template <class V>
1325
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1326
    typename V::template Container<typename V::R_SExpr>
1327
      Nvs(Vs, Values.size());
1328
1329
    for (const auto *Val : Values)
1330
      Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) );
1331
    return Vs.reducePhi(*this, Nvs);
1332
  }
1333
1334
  template <class C>
1335
0
  typename C::CType compare(const Phi *E, C &Cmp) const {
1336
    // TODO: implement CFG comparisons
1337
0
    return Cmp.comparePointers(this, E);
1338
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
1339
1340
private:
1341
  ValArray Values;
1342
  const ValueDecl* Cvdecl = nullptr;
1343
};
1344
1345
/// Base class for basic block terminators:  Branch, Goto, and Return.
1346
class Terminator : public SExpr {
1347
protected:
1348
0
  Terminator(TIL_Opcode Op) : SExpr(Op) {}
1349
0
  Terminator(const SExpr &E) : SExpr(E) {}
1350
1351
public:
1352
0
  static bool classof(const SExpr *E) {
1353
0
    return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
1354
0
  }
1355
1356
  /// Return the list of basic blocks that this terminator can branch to.
1357
  ArrayRef<BasicBlock *> successors();
1358
1359
0
  ArrayRef<BasicBlock *> successors() const {
1360
0
    return const_cast<Terminator*>(this)->successors();
1361
0
  }
1362
};
1363
1364
/// Jump to another basic block.
1365
/// A goto instruction is essentially a tail-recursive call into another
1366
/// block.  In addition to the block pointer, it specifies an index into the
1367
/// phi nodes of that block.  The index can be used to retrieve the "arguments"
1368
/// of the call.
1369
class Goto : public Terminator {
1370
public:
1371
  Goto(BasicBlock *B, unsigned I)
1372
0
      : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1373
  Goto(const Goto &G, BasicBlock *B, unsigned I)
1374
0
      : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1375
1376
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1377
1378
0
  const BasicBlock *targetBlock() const { return TargetBlock; }
1379
0
  BasicBlock *targetBlock() { return TargetBlock; }
1380
1381
  /// Returns the index into the
1382
0
  unsigned index() const { return Index; }
1383
1384
  /// Return the list of basic blocks that this terminator can branch to.
1385
0
  ArrayRef<BasicBlock *> successors() { return TargetBlock; }
1386
1387
  template <class V>
1388
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1389
    BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock);
1390
    return Vs.reduceGoto(*this, Ntb);
1391
  }
1392
1393
  template <class C>
1394
0
  typename C::CType compare(const Goto *E, C &Cmp) const {
1395
    // TODO: implement CFG comparisons
1396
0
    return Cmp.comparePointers(this, E);
1397
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
1398
1399
private:
1400
  BasicBlock *TargetBlock;
1401
  unsigned Index;
1402
};
1403
1404
/// A conditional branch to two other blocks.
1405
/// Note that unlike Goto, Branch does not have an index.  The target blocks
1406
/// must be child-blocks, and cannot have Phi nodes.
1407
class Branch : public Terminator {
1408
public:
1409
  Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
1410
0
      : Terminator(COP_Branch), Condition(C) {
1411
0
    Branches[0] = T;
1412
0
    Branches[1] = E;
1413
0
  }
1414
1415
  Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
1416
0
      : Terminator(Br), Condition(C) {
1417
0
    Branches[0] = T;
1418
0
    Branches[1] = E;
1419
0
  }
1420
1421
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1422
1423
0
  const SExpr *condition() const { return Condition; }
1424
0
  SExpr *condition() { return Condition; }
1425
1426
0
  const BasicBlock *thenBlock() const { return Branches[0]; }
1427
0
  BasicBlock *thenBlock() { return Branches[0]; }
1428
1429
0
  const BasicBlock *elseBlock() const { return Branches[1]; }
1430
0
  BasicBlock *elseBlock() { return Branches[1]; }
1431
1432
  /// Return the list of basic blocks that this terminator can branch to.
1433
0
  ArrayRef<BasicBlock*> successors() {
1434
0
    return llvm::makeArrayRef(Branches);
1435
0
  }
1436
1437
  template <class V>
1438
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1439
    auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1440
    BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]);
1441
    BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]);
1442
    return Vs.reduceBranch(*this, Nc, Ntb, Nte);
1443
  }
1444
1445
  template <class C>
1446
0
  typename C::CType compare(const Branch *E, C &Cmp) const {
1447
    // TODO: implement CFG comparisons
1448
0
    return Cmp.comparePointers(this, E);
1449
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
1450
1451
private:
1452
  SExpr *Condition;
1453
  BasicBlock *Branches[2];
1454
};
1455
1456
/// Return from the enclosing function, passing the return value to the caller.
1457
/// Only the exit block should end with a return statement.
1458
class Return : public Terminator {
1459
public:
1460
0
  Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
1461
0
  Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
1462
1463
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
1464
1465
  /// Return an empty list.
1466
0
  ArrayRef<BasicBlock *> successors() { return None; }
1467
1468
0
  SExpr *returnValue() { return Retval; }
1469
0
  const SExpr *returnValue() const { return Retval; }
1470
1471
  template <class V>
1472
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1473
    auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx));
1474
    return Vs.reduceReturn(*this, Ne);
1475
  }
1476
1477
  template <class C>
1478
0
  typename C::CType compare(const Return *E, C &Cmp) const {
1479
0
    return Cmp.compare(Retval, E->Retval);
1480
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
1481
1482
private:
1483
  SExpr* Retval;
1484
};
1485
1486
0
inline ArrayRef<BasicBlock*> Terminator::successors() {
1487
0
  switch (opcode()) {
1488
0
    case COP_Goto:   return cast<Goto>(this)->successors();
1489
0
    case COP_Branch: return cast<Branch>(this)->successors();
1490
0
    case COP_Return: return cast<Return>(this)->successors();
1491
0
    default:
1492
0
      return None;
1493
0
  }
1494
0
}
1495
1496
/// A basic block is part of an SCFG.  It can be treated as a function in
1497
/// continuation passing style.  A block consists of a sequence of phi nodes,
1498
/// which are "arguments" to the function, followed by a sequence of
1499
/// instructions.  It ends with a Terminator, which is a Branch or Goto to
1500
/// another basic block in the same SCFG.
1501
class BasicBlock : public SExpr {
1502
public:
1503
  using InstrArray = SimpleArray<SExpr *>;
1504
  using BlockArray = SimpleArray<BasicBlock *>;
1505
1506
  // TopologyNodes are used to overlay tree structures on top of the CFG,
1507
  // such as dominator and postdominator trees.  Each block is assigned an
1508
  // ID in the tree according to a depth-first search.  Tree traversals are
1509
  // always up, towards the parents.
1510
  struct TopologyNode {
1511
    int NodeID = 0;
1512
1513
    // Includes this node, so must be > 1.
1514
    int SizeOfSubTree = 0;
1515
1516
    // Pointer to parent.
1517
    BasicBlock *Parent = nullptr;
1518
1519
0
    TopologyNode() = default;
1520
1521
0
    bool isParentOf(const TopologyNode& OtherNode) {
1522
0
      return OtherNode.NodeID > NodeID &&
1523
0
             OtherNode.NodeID < NodeID + SizeOfSubTree;
1524
0
    }
1525
1526
0
    bool isParentOfOrEqual(const TopologyNode& OtherNode) {
1527
0
      return OtherNode.NodeID >= NodeID &&
1528
0
             OtherNode.NodeID < NodeID + SizeOfSubTree;
1529
0
    }
1530
  };
1531
1532
  explicit BasicBlock(MemRegionRef A)
1533
0
      : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {}
1534
  BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is,
1535
             Terminator *T)
1536
      : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false),
1537
0
        Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
1538
1539
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
1540
1541
  /// Returns the block ID.  Every block has a unique ID in the CFG.
1542
0
  int blockID() const { return BlockID; }
1543
1544
  /// Returns the number of predecessors.
1545
0
  size_t numPredecessors() const { return Predecessors.size(); }
1546
0
  size_t numSuccessors() const { return successors().size(); }
1547
1548
0
  const SCFG* cfg() const { return CFGPtr; }
1549
0
  SCFG* cfg() { return CFGPtr; }
1550
1551
0
  const BasicBlock *parent() const { return DominatorNode.Parent; }
1552
0
  BasicBlock *parent() { return DominatorNode.Parent; }
1553
1554
0
  const InstrArray &arguments() const { return Args; }
1555
0
  InstrArray &arguments() { return Args; }
1556
1557
0
  InstrArray &instructions() { return Instrs; }
1558
0
  const InstrArray &instructions() const { return Instrs; }
1559
1560
  /// Returns a list of predecessors.
1561
  /// The order of predecessors in the list is important; each phi node has
1562
  /// exactly one argument for each precessor, in the same order.
1563
0
  BlockArray &predecessors() { return Predecessors; }
1564
0
  const BlockArray &predecessors() const { return Predecessors; }
1565
1566
0
  ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
1567
0
  ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
1568
1569
0
  const Terminator *terminator() const { return TermInstr; }
1570
0
  Terminator *terminator() { return TermInstr; }
1571
1572
0
  void setTerminator(Terminator *E) { TermInstr = E; }
1573
1574
0
  bool Dominates(const BasicBlock &Other) {
1575
0
    return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
1576
0
  }
1577
1578
0
  bool PostDominates(const BasicBlock &Other) {
1579
0
    return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
1580
0
  }
1581
1582
  /// Add a new argument.
1583
0
  void addArgument(Phi *V) {
1584
0
    Args.reserveCheck(1, Arena);
1585
0
    Args.push_back(V);
1586
0
  }
1587
1588
  /// Add a new instruction.
1589
0
  void addInstruction(SExpr *V) {
1590
0
    Instrs.reserveCheck(1, Arena);
1591
0
    Instrs.push_back(V);
1592
0
  }
1593
1594
  // Add a new predecessor, and return the phi-node index for it.
1595
  // Will add an argument to all phi-nodes, initialized to nullptr.
1596
  unsigned addPredecessor(BasicBlock *Pred);
1597
1598
  // Reserve space for Nargs arguments.
1599
0
  void reserveArguments(unsigned Nargs)   { Args.reserve(Nargs, Arena); }
1600
1601
  // Reserve space for Nins instructions.
1602
0
  void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
1603
1604
  // Reserve space for NumPreds predecessors, including space in phi nodes.
1605
  void reservePredecessors(unsigned NumPreds);
1606
1607
  /// Return the index of BB, or Predecessors.size if BB is not a predecessor.
1608
0
  unsigned findPredecessorIndex(const BasicBlock *BB) const {
1609
0
    auto I = llvm::find(Predecessors, BB);
1610
0
    return std::distance(Predecessors.cbegin(), I);
1611
0
  }
1612
1613
  template <class V>
1614
  typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
1615
    typename V::template Container<SExpr*> Nas(Vs, Args.size());
1616
    typename V::template Container<SExpr*> Nis(Vs, Instrs.size());
1617
1618
    // Entering the basic block should do any scope initialization.
1619
    Vs.enterBasicBlock(*this);
1620
1621
    for (const auto *E : Args) {
1622
      auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1623
      Nas.push_back(Ne);
1624
    }
1625
    for (const auto *E : Instrs) {
1626
      auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1627
      Nis.push_back(Ne);
1628
    }
1629
    auto Nt = Vs.traverse(TermInstr, Ctx);
1630
1631
    // Exiting the basic block should handle any scope cleanup.
1632
    Vs.exitBasicBlock(*this);
1633
1634
    return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
1635
  }
1636
1637
  template <class C>
1638
0
  typename C::CType compare(const BasicBlock *E, C &Cmp) const {
1639
    // TODO: implement CFG comparisons
1640
0
    return Cmp.comparePointers(this, E);
1641
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
1642
1643
private:
1644
  friend class SCFG;
1645
1646
  // assign unique ids to all instructions
1647
  unsigned renumberInstrs(unsigned id);
1648
1649
  unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
1650
  unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
1651
  void computeDominator();
1652
  void computePostDominator();
1653
1654
  // The arena used to allocate this block.
1655
  MemRegionRef Arena;
1656
1657
  // The CFG that contains this block.
1658
  SCFG *CFGPtr = nullptr;
1659
1660
  // Unique ID for this BB in the containing CFG. IDs are in topological order.
1661
  unsigned BlockID : 31;
1662
1663
  // Bit to determine if a block has been visited during a traversal.
1664
  bool Visited : 1;
1665
1666
  // Predecessor blocks in the CFG.
1667
  BlockArray Predecessors;
1668
1669
  // Phi nodes. One argument per predecessor.
1670
  InstrArray Args;
1671
1672
  // Instructions.
1673
  InstrArray Instrs;
1674
1675
  // Terminating instruction.
1676
  Terminator *TermInstr = nullptr;
1677
1678
  // The dominator tree.
1679
  TopologyNode DominatorNode;
1680
1681
  // The post-dominator tree.
1682
  TopologyNode PostDominatorNode;
1683
};
1684
1685
/// An SCFG is a control-flow graph.  It consists of a set of basic blocks,
1686
/// each of which terminates in a branch to another basic block.  There is one
1687
/// entry point, and one exit point.
1688
class SCFG : public SExpr {
1689
public:
1690
  using BlockArray = SimpleArray<BasicBlock *>;
1691
  using iterator = BlockArray::iterator;
1692
  using const_iterator = BlockArray::const_iterator;
1693
1694
  SCFG(MemRegionRef A, unsigned Nblocks)
1695
0
      : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) {
1696
0
    Entry = new (A) BasicBlock(A);
1697
0
    Exit  = new (A) BasicBlock(A);
1698
0
    auto *V = new (A) Phi();
1699
0
    Exit->addArgument(V);
1700
0
    Exit->setTerminator(new (A) Return(V));
1701
0
    add(Entry);
1702
0
    add(Exit);
1703
0
  }
1704
1705
  SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1706
0
      : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) {
1707
0
    // TODO: set entry and exit!
1708
0
  }
1709
1710
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1711
1712
  /// Return true if this CFG is valid.
1713
0
  bool valid() const { return Entry && Exit && Blocks.size() > 0; }
1714
1715
  /// Return true if this CFG has been normalized.
1716
  /// After normalization, blocks are in topological order, and block and
1717
  /// instruction IDs have been assigned.
1718
0
  bool normal() const { return Normal; }
1719
1720
0
  iterator begin() { return Blocks.begin(); }
1721
0
  iterator end() { return Blocks.end(); }
1722
1723
0
  const_iterator begin() const { return cbegin(); }
1724
0
  const_iterator end() const { return cend(); }
1725
1726
0
  const_iterator cbegin() const { return Blocks.cbegin(); }
1727
0
  const_iterator cend() const { return Blocks.cend(); }
1728
1729
0
  const BasicBlock *entry() const { return Entry; }
1730
0
  BasicBlock *entry() { return Entry; }
1731
0
  const BasicBlock *exit() const { return Exit; }
1732
0
  BasicBlock *exit() { return Exit; }
1733
1734
  /// Return the number of blocks in the CFG.
1735
  /// Block::blockID() will return a number less than numBlocks();
1736
0
  size_t numBlocks() const { return Blocks.size(); }
1737
1738
  /// Return the total number of instructions in the CFG.
1739
  /// This is useful for building instruction side-tables;
1740
  /// A call to SExpr::id() will return a number less than numInstructions().
1741
0
  unsigned numInstructions() { return NumInstructions; }
1742
1743
0
  inline void add(BasicBlock *BB) {
1744
0
    assert(BB->CFGPtr == nullptr);
1745
0
    BB->CFGPtr = this;
1746
0
    Blocks.reserveCheck(1, Arena);
1747
0
    Blocks.push_back(BB);
1748
0
  }
1749
1750
0
  void setEntry(BasicBlock *BB) { Entry = BB; }
1751
0
  void setExit(BasicBlock *BB)  { Exit = BB;  }
1752
1753
  void computeNormalForm();
1754
1755
  template <class V>
1756
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1757
    Vs.enterCFG(*this);
1758
    typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
1759
1760
    for (const auto *B : Blocks) {
1761
      Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
1762
    }
1763
    Vs.exitCFG(*this);
1764
    return Vs.reduceSCFG(*this, Bbs);
1765
  }
1766
1767
  template <class C>
1768
0
  typename C::CType compare(const SCFG *E, C &Cmp) const {
1769
    // TODO: implement CFG comparisons
1770
0
    return Cmp.comparePointers(this, E);
1771
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
1772
1773
private:
1774
  // assign unique ids to all instructions
1775
  void renumberInstrs();
1776
1777
  MemRegionRef Arena;
1778
  BlockArray Blocks;
1779
  BasicBlock *Entry = nullptr;
1780
  BasicBlock *Exit = nullptr;
1781
  unsigned NumInstructions = 0;
1782
  bool Normal = false;
1783
};
1784
1785
/// An identifier, e.g. 'foo' or 'x'.
1786
/// This is a pseduo-term; it will be lowered to a variable or projection.
1787
class Identifier : public SExpr {
1788
public:
1789
0
  Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {}
1790
  Identifier(const Identifier &) = default;
1791
1792
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1793
1794
0
  StringRef name() const { return Name; }
1795
1796
  template <class V>
1797
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1798
    return Vs.reduceIdentifier(*this);
1799
  }
1800
1801
  template <class C>
1802
0
  typename C::CType compare(const Identifier* E, C& Cmp) const {
1803
0
    return Cmp.compareStrings(name(), E->name());
1804
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
1805
1806
private:
1807
  StringRef Name;
1808
};
1809
1810
/// An if-then-else expression.
1811
/// This is a pseduo-term; it will be lowered to a branch in a CFG.
1812
class IfThenElse : public SExpr {
1813
public:
1814
  IfThenElse(SExpr *C, SExpr *T, SExpr *E)
1815
24
      : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {}
1816
  IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
1817
0
      : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {}
1818
1819
224
  static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1820
1821
0
  SExpr *condition() { return Condition; }   // Address to store to
1822
224
  const SExpr *condition() const { return Condition; }
1823
1824
0
  SExpr *thenExpr() { return ThenExpr; }     // Value to store
1825
224
  const SExpr *thenExpr() const { return ThenExpr; }
1826
1827
0
  SExpr *elseExpr() { return ElseExpr; }     // Value to store
1828
216
  const SExpr *elseExpr() const { return ElseExpr; }
1829
1830
  template <class V>
1831
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1832
    auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1833
    auto Nt = Vs.traverse(ThenExpr,  Vs.subExprCtx(Ctx));
1834
    auto Ne = Vs.traverse(ElseExpr,  Vs.subExprCtx(Ctx));
1835
    return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
1836
  }
1837
1838
  template <class C>
1839
108
  typename C::CType compare(const IfThenElse* E, C& Cmp) const {
1840
108
    typename C::CType Ct = Cmp.compare(condition(), E->condition());
1841
108
    if (Cmp.notTrue(Ct))
1842
0
      return Ct;
1843
108
    Ct = Cmp.compare(thenExpr(), E->thenExpr());
1844
108
    if (Cmp.notTrue(Ct))
1845
4
      return Ct;
1846
104
    return Cmp.compare(elseExpr(), E->elseExpr());
1847
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
1839
108
  typename C::CType compare(const IfThenElse* E, C& Cmp) const {
1840
108
    typename C::CType Ct = Cmp.compare(condition(), E->condition());
1841
108
    if (Cmp.notTrue(Ct))
1842
0
      return Ct;
1843
108
    Ct = Cmp.compare(thenExpr(), E->thenExpr());
1844
108
    if (Cmp.notTrue(Ct))
1845
4
      return Ct;
1846
104
    return Cmp.compare(elseExpr(), E->elseExpr());
1847
104
  }
1848
1849
private:
1850
  SExpr* Condition;
1851
  SExpr* ThenExpr;
1852
  SExpr* ElseExpr;
1853
};
1854
1855
/// A let-expression,  e.g.  let x=t; u.
1856
/// This is a pseduo-term; it will be lowered to instructions in a CFG.
1857
class Let : public SExpr {
1858
public:
1859
0
  Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1860
0
    Vd->setKind(Variable::VK_Let);
1861
0
  }
1862
1863
0
  Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1864
0
    Vd->setKind(Variable::VK_Let);
1865
0
  }
1866
1867
0
  static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1868
1869
0
  Variable *variableDecl()  { return VarDecl; }
1870
0
  const Variable *variableDecl() const { return VarDecl; }
1871
1872
0
  SExpr *body() { return Body; }
1873
0
  const SExpr *body() const { return Body; }
1874
1875
  template <class V>
1876
  typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1877
    // This is a variable declaration, so traverse the definition.
1878
    auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
1879
    // Tell the rewriter to enter the scope of the let variable.
1880
    Variable *Nvd = Vs.enterScope(*VarDecl, E0);
1881
    auto E1 = Vs.traverse(Body, Ctx);
1882
    Vs.exitScope(*VarDecl);
1883
    return Vs.reduceLet(*this, Nvd, E1);
1884
  }
1885
1886
  template <class C>
1887
0
  typename C::CType compare(const Let* E, C& Cmp) const {
1888
0
    typename C::CType Ct =
1889
0
      Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
1890
0
    if (Cmp.notTrue(Ct))
1891
0
      return Ct;
1892
0
    Cmp.enterScope(variableDecl(), E->variableDecl());
1893
0
    Ct = Cmp.compare(body(), E->body());
1894
0
    Cmp.leaveScope();
1895
0
    return Ct;
1896
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
1897
1898
private:
1899
  Variable *VarDecl;
1900
  SExpr* Body;
1901
};
1902
1903
const SExpr *getCanonicalVal(const SExpr *E);
1904
SExpr* simplifyToCanonicalVal(SExpr *E);
1905
void simplifyIncompleteArg(til::Phi *Ph);
1906
1907
} // namespace til
1908
} // namespace threadSafety
1909
1910
} // namespace clang
1911
1912
#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H