clang  10.0.0svn
ThreadSafetyTIL.h
Go to the documentation of this file.
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"
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, // ~
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, // >>
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 {
115 
116  // Extend precision of numeric type
118 
119  // Truncate precision of numeric type
121 
122  // Convert to floating point type
124 
125  // Convert to integer type
127 
128  // Convert smart pointer to pointer (C++ only)
130 };
131 
132 const TIL_Opcode COP_Min = COP_Future;
133 const TIL_Opcode COP_Max = COP_Branch;
140 
141 /// Return the name of a unary opcode.
143 
144 /// Return the name of a binary opcode.
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,
159  BT_String, // String literals
162  };
163 
164  enum SizeType : unsigned char {
165  ST_0 = 0,
172  };
173 
174  ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
175  : 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 
184  bool Signed;
185 
186  // 0 for scalar, otherwise num elements in vector
187  unsigned char VectSize;
188 };
189 
191  switch (nbytes) {
192  case 1: return ST_8;
193  case 2: return ST_16;
194  case 4: return ST_32;
195  case 8: return ST_64;
196  case 16: return ST_128;
197  default: return ST_0;
198  }
199 }
200 
201 template<>
202 inline ValueType ValueType::getValueType<void>() {
203  return ValueType(BT_Void, ST_0, false, 0);
204 }
205 
206 template<>
207 inline ValueType ValueType::getValueType<bool>() {
208  return ValueType(BT_Bool, ST_1, false, 0);
209 }
210 
211 template<>
212 inline ValueType ValueType::getValueType<int8_t>() {
213  return ValueType(BT_Int, ST_8, true, 0);
214 }
215 
216 template<>
217 inline ValueType ValueType::getValueType<uint8_t>() {
218  return ValueType(BT_Int, ST_8, false, 0);
219 }
220 
221 template<>
222 inline ValueType ValueType::getValueType<int16_t>() {
223  return ValueType(BT_Int, ST_16, true, 0);
224 }
225 
226 template<>
227 inline ValueType ValueType::getValueType<uint16_t>() {
228  return ValueType(BT_Int, ST_16, false, 0);
229 }
230 
231 template<>
232 inline ValueType ValueType::getValueType<int32_t>() {
233  return ValueType(BT_Int, ST_32, true, 0);
234 }
235 
236 template<>
237 inline ValueType ValueType::getValueType<uint32_t>() {
238  return ValueType(BT_Int, ST_32, false, 0);
239 }
240 
241 template<>
242 inline ValueType ValueType::getValueType<int64_t>() {
243  return ValueType(BT_Int, ST_64, true, 0);
244 }
245 
246 template<>
247 inline ValueType ValueType::getValueType<uint64_t>() {
248  return ValueType(BT_Int, ST_64, false, 0);
249 }
250 
251 template<>
252 inline ValueType ValueType::getValueType<float>() {
253  return ValueType(BT_Float, ST_32, true, 0);
254 }
255 
256 template<>
257 inline ValueType ValueType::getValueType<double>() {
258  return ValueType(BT_Float, ST_64, true, 0);
259 }
260 
261 template<>
262 inline ValueType ValueType::getValueType<long double>() {
263  return ValueType(BT_Float, ST_128, true, 0);
264 }
265 
266 template<>
267 inline ValueType ValueType::getValueType<StringRef>() {
268  return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
269 }
270 
271 template<>
272 inline ValueType ValueType::getValueType<void*>() {
273  return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
274 }
275 
276 /// Base class for AST nodes in the typed intermediate language.
277 class SExpr {
278 public:
279  SExpr() = delete;
280 
281  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  void *operator new(size_t S, MemRegionRef &R) {
298  return ::operator new(S, R);
299  }
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  unsigned id() const { return SExprID; }
312 
313  /// Returns the block, if this is an instruction in a basic block,
314  /// otherwise returns null.
315  BasicBlock *block() const { return Block; }
316 
317  /// Set the basic block and instruction ID for this expression.
318  void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
319 
320 protected:
321  SExpr(TIL_Opcode Op) : Opcode(Op) {}
322  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 inline bool isTrivial(const SExpr *E) {
335  unsigned Op = E->opcode();
336  return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
337 }
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:
358  /// Let-variable
360 
361  /// Function parameter
363 
364  /// SFunction (self) parameter
365  VK_SFun
366  };
367 
368  Variable(StringRef s, SExpr *D = nullptr)
369  : SExpr(COP_Variable), Name(s), Definition(D) {
370  Flags = VK_Let;
371  }
372 
373  Variable(SExpr *D, const ValueDecl *Cvd = nullptr)
374  : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
375  Definition(D), Cvdecl(Cvd) {
376  Flags = VK_Let;
377  }
378 
379  Variable(const Variable &Vd, SExpr *D) // rewrite constructor
380  : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
381  Flags = Vd.kind();
382  }
383 
384  static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
385 
386  /// Return the kind of variable (let, function param, or self)
387  VariableKind kind() const { return static_cast<VariableKind>(Flags); }
388 
389  /// Return the name of the variable, if any.
390  StringRef name() const { return Name; }
391 
392  /// Return the clang declaration for this variable, if any.
393  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  SExpr *definition() { return Definition; }
399  const SExpr *definition() const { return Definition; }
400 
401  void setName(StringRef S) { Name = S; }
402  void setKind(VariableKind K) { Flags = K; }
403  void setDefinition(SExpr *E) { Definition = E; }
404  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  typename C::CType compare(const Variable* E, C& Cmp) const {
414  return Cmp.compareVariableRefs(this, E);
415  }
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:
440  FS_done
441  };
442 
443  Future() : SExpr(COP_Future) {}
444  virtual ~Future() = delete;
445 
446  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  virtual SExpr *compute() { return nullptr; }
450 
451  // Return the result of this future if it exists, otherwise return null.
452  SExpr *maybeGetResult() const { return Result; }
453 
454  // Return the result of this future; forcing it if necessary.
456  switch (Status) {
457  case FS_pending:
458  return force();
459  case FS_evaluating:
460  return nullptr; // infinite loop; illegal recursion.
461  case FS_done:
462  return Result;
463  }
464  }
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  typename C::CType compare(const Future* E, C& Cmp) const {
474  if (!Result || !E->Result)
475  return Cmp.comparePointers(this, E);
476  return Cmp.compare(Result, E->Result);
477  }
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  Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
490  Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
491 
492  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  typename C::CType compare(const Undefined* E, C& Cmp) const {
501  return Cmp.trueResult();
502  }
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  Wildcard() : SExpr(COP_Wildcard) {}
512  Wildcard(const Wildcard &) = default;
513 
514  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  typename C::CType compare(const Wildcard* E, C& Cmp) const {
522  return Cmp.trueResult();
523  }
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  : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {}
533  Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {}
534  Literal(const Literal &) = default;
535 
536  static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
537 
538  // The clang expression for this literal.
539  const Expr *clangExpr() const { return Cexpr; }
540 
541  ValueType valueType() const { return ValType; }
542 
543  template<class T> const LiteralT<T>& as() const {
544  return *static_cast<const LiteralT<T>*>(this);
545  }
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  typename C::CType compare(const Literal* E, C& Cmp) const {
554  // TODO: defer actual comparison to LiteralT
555  return Cmp.trueResult();
556  }
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  T value() const { return Val;}
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  }
624  return Vs.reduceLiteralT(as<StringRef>());
626  return Vs.reduceLiteralT(as<void*>());
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  LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
638  LiteralPtr(const LiteralPtr &) = default;
639 
640  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  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  typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
652  return Cmp.comparePointers(Cvdecl, E->Cvdecl);
653  }
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:
665  : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
667  }
668 
669  Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
670  : SExpr(F), VarDecl(Vd), Body(Bd) {
672  }
673 
674  static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
675 
677  const Variable *variableDecl() const { return VarDecl; }
678 
679  SExpr *body() { return Body; }
680  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  typename C::CType compare(const Function* E, C& Cmp) const {
695  typename C::CType Ct =
696  Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
697  if (Cmp.notTrue(Ct))
698  return Ct;
699  Cmp.enterScope(variableDecl(), E->variableDecl());
700  Ct = Cmp.compare(body(), E->body());
701  Cmp.leaveScope();
702  return Ct;
703  }
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:
716  : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
717  assert(Vd->Definition == nullptr);
719  Vd->Definition = this;
720  }
721 
722  SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
723  : SExpr(F), VarDecl(Vd), Body(B) {
724  assert(Vd->Definition == nullptr);
726  Vd->Definition = this;
727  }
728 
729  static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
730 
732  const Variable *variableDecl() const { return VarDecl; }
733 
734  SExpr *body() { return Body; }
735  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  typename C::CType compare(const SFunction* E, C& Cmp) const {
751  Cmp.enterScope(variableDecl(), E->variableDecl());
752  typename C::CType Ct = Cmp.compare(body(), E->body());
753  Cmp.leaveScope();
754  return Ct;
755  }
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  Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
766  Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
767  : SExpr(C), ReturnType(T), Body(B) {}
768 
769  static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
770 
771  SExpr *returnType() { return ReturnType; }
772  const SExpr *returnType() const { return ReturnType; }
773 
774  SExpr *body() { return Body; }
775  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  typename C::CType compare(const Code* E, C& Cmp) const {
786  typename C::CType Ct = Cmp.compare(returnType(), E->returnType());
787  if (Cmp.notTrue(Ct))
788  return Ct;
789  return Cmp.compare(body(), E->body());
790  }
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  Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
801  Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
802  : SExpr(C), Range(R), Body(B) {}
803 
804  static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
805 
806  SExpr *range() { return Range; }
807  const SExpr *range() const { return Range; }
808 
809  SExpr *body() { return Body; }
810  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  typename C::CType compare(const Field* E, C& Cmp) const {
821  typename C::CType Ct = Cmp.compare(range(), E->range());
822  if (Cmp.notTrue(Ct))
823  return Ct;
824  return Cmp.compare(body(), E->body());
825  }
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  Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
840  Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor
841  : SExpr(A), Fun(F), Arg(Ar) {}
842 
843  static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
844 
845  SExpr *fun() { return Fun; }
846  const SExpr *fun() const { return Fun; }
847 
848  SExpr *arg() { return Arg; }
849  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  typename C::CType compare(const Apply* E, C& Cmp) const {
860  typename C::CType Ct = Cmp.compare(fun(), E->fun());
861  if (Cmp.notTrue(Ct))
862  return Ct;
863  return Cmp.compare(arg(), E->arg());
864  }
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  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  : SExpr(A), Sfun(Sf), Arg(Ar) {}
877 
878  static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
879 
880  SExpr *sfun() { return Sfun; }
881  const SExpr *sfun() const { return Sfun; }
882 
883  SExpr *arg() { return Arg ? Arg : Sfun; }
884  const SExpr *arg() const { return Arg ? Arg : Sfun; }
885 
886  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  typename C::CType compare(const SApply* E, C& Cmp) const {
898  typename C::CType Ct = Cmp.compare(sfun(), E->sfun());
899  if (Cmp.notTrue(Ct) || (!arg() && !E->arg()))
900  return Ct;
901  return Cmp.compare(arg(), E->arg());
902  }
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  : SExpr(COP_Project), Rec(R), Cvdecl(Cvd) {
914  assert(Cvd && "ValueDecl must not be null");
915  }
916 
917  static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
918 
919  SExpr *record() { return Rec; }
920  const SExpr *record() const { return Rec; }
921 
922  const ValueDecl *clangDecl() const { return Cvdecl; }
923 
924  bool isArrow() const { return (Flags & 0x01) != 0; }
925 
926  void setArrow(bool b) {
927  if (b) Flags |= 0x01;
928  else Flags &= 0xFFFE;
929  }
930 
931  StringRef slotName() const {
932  if (Cvdecl->getDeclName().isIdentifier())
933  return Cvdecl->getName();
934  if (!SlotName) {
935  SlotName = "";
936  llvm::raw_string_ostream OS(*SlotName);
937  Cvdecl->printName(OS);
938  }
939  return *SlotName;
940  }
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  typename C::CType compare(const Project* E, C& Cmp) const {
950  typename C::CType Ct = Cmp.compare(record(), E->record());
951  if (Cmp.notTrue(Ct))
952  return Ct;
953  return Cmp.comparePointers(Cvdecl, E->Cvdecl);
954  }
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  : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
967  Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
968 
969  static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
970 
971  SExpr *target() { return Target; }
972  const SExpr *target() const { return Target; }
973 
974  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  typename C::CType compare(const Call* E, C& Cmp) const {
984  return Cmp.compare(target(), E->target());
985  }
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 {
997  AK_Heap
998  };
999 
1000  Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1001  Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1002 
1003  static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1004 
1005  AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1006 
1007  SExpr *dataType() { return Dtype; }
1008  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  typename C::CType compare(const Alloc* E, C& Cmp) const {
1018  typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind());
1019  if (Cmp.notTrue(Ct))
1020  return Ct;
1021  return Cmp.compare(dataType(), E->dataType());
1022  }
1023 
1024 private:
1025  SExpr* Dtype;
1026 };
1027 
1028 /// Load a value from memory.
1029 class Load : public SExpr {
1030 public:
1031  Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1032  Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1033 
1034  static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1035 
1036  SExpr *pointer() { return Ptr; }
1037  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  typename C::CType compare(const Load* E, C& Cmp) const {
1047  return Cmp.compare(pointer(), E->pointer());
1048  }
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  Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
1059  Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1060 
1061  static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1062 
1063  SExpr *destination() { return Dest; } // Address to store to
1064  const SExpr *destination() const { return Dest; }
1065 
1066  SExpr *source() { return Source; } // Value to store
1067  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  typename C::CType compare(const Store* E, C& Cmp) const {
1078  typename C::CType Ct = Cmp.compare(destination(), E->destination());
1079  if (Cmp.notTrue(Ct))
1080  return Ct;
1081  return Cmp.compare(source(), E->source());
1082  }
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  ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1094  ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
1095  : SExpr(E), Array(A), Index(N) {}
1096 
1097  static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1098 
1099  SExpr *array() { return Array; }
1100  const SExpr *array() const { return Array; }
1101 
1102  SExpr *index() { return Index; }
1103  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  typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1114  typename C::CType Ct = Cmp.compare(array(), E->array());
1115  if (Cmp.notTrue(Ct))
1116  return Ct;
1117  return Cmp.compare(index(), E->index());
1118  }
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  ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1131  ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1132  : SExpr(E), Array(A), Index(N) {}
1133 
1134  static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1135 
1136  SExpr *array() { return Array; }
1137  const SExpr *array() const { return Array; }
1138 
1139  SExpr *index() { return Index; }
1140  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  typename C::CType compare(const ArrayAdd* E, C& Cmp) const {
1151  typename C::CType Ct = Cmp.compare(array(), E->array());
1152  if (Cmp.notTrue(Ct))
1153  return Ct;
1154  return Cmp.compare(index(), E->index());
1155  }
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  UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1167  Flags = Op;
1168  }
1169 
1170  UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1171 
1172  static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1173 
1175  return static_cast<TIL_UnaryOpcode>(Flags);
1176  }
1177 
1178  SExpr *expr() { return Expr0; }
1179  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  typename C::CType compare(const UnaryOp* E, C& Cmp) const {
1189  typename C::CType Ct =
1190  Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode());
1191  if (Cmp.notTrue(Ct))
1192  return Ct;
1193  return Cmp.compare(expr(), E->expr());
1194  }
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:
1205  : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1206  Flags = Op;
1207  }
1208 
1209  BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1210  : SExpr(B), Expr0(E0), Expr1(E1) {
1211  Flags = B.Flags;
1212  }
1213 
1214  static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1215 
1217  return static_cast<TIL_BinaryOpcode>(Flags);
1218  }
1219 
1220  SExpr *expr0() { return Expr0; }
1221  const SExpr *expr0() const { return Expr0; }
1222 
1223  SExpr *expr1() { return Expr1; }
1224  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  typename C::CType compare(const BinaryOp* E, C& Cmp) const {
1235  typename C::CType Ct =
1236  Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode());
1237  if (Cmp.notTrue(Ct))
1238  return Ct;
1239  Ct = Cmp.compare(expr0(), E->expr0());
1240  if (Cmp.notTrue(Ct))
1241  return Ct;
1242  return Cmp.compare(expr1(), E->expr1());
1243  }
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  Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1256  Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1257 
1258  static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1259 
1261  return static_cast<TIL_CastOpcode>(Flags);
1262  }
1263 
1264  SExpr *expr() { return Expr0; }
1265  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  typename C::CType compare(const Cast* E, C& Cmp) const {
1275  typename C::CType Ct =
1276  Cmp.compareIntegers(castOpcode(), E->castOpcode());
1277  if (Cmp.notTrue(Ct))
1278  return Ct;
1279  return Cmp.compare(expr(), E->expr());
1280  }
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:
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  Phi() : SExpr(COP_Phi) {}
1305  Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
1306  Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
1307 
1308  static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1309 
1310  const ValArray &values() const { return Values; }
1311  ValArray &values() { return Values; }
1312 
1313  Status status() const { return static_cast<Status>(Flags); }
1314  void setStatus(Status s) { Flags = s; }
1315 
1316  /// Return the clang declaration of the variable for this Phi node, if any.
1317  const ValueDecl *clangDecl() const { return Cvdecl; }
1318 
1319  /// Set the clang variable associated with this Phi node.
1320  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  typename C::CType compare(const Phi *E, C &Cmp) const {
1334  // TODO: implement CFG comparisons
1335  return Cmp.comparePointers(this, E);
1336  }
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:
1347  Terminator(const SExpr &E) : SExpr(E) {}
1348 
1349 public:
1350  static bool classof(const SExpr *E) {
1351  return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
1352  }
1353 
1354  /// Return the list of basic blocks that this terminator can branch to.
1355  ArrayRef<BasicBlock *> successors();
1356 
1358  return const_cast<Terminator*>(this)->successors();
1359  }
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  : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1371  Goto(const Goto &G, BasicBlock *B, unsigned I)
1372  : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1373 
1374  static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1375 
1376  const BasicBlock *targetBlock() const { return TargetBlock; }
1377  BasicBlock *targetBlock() { return TargetBlock; }
1378 
1379  /// Returns the index into the
1380  unsigned index() const { return Index; }
1381 
1382  /// Return the list of basic blocks that this terminator can branch to.
1383  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  typename C::CType compare(const Goto *E, C &Cmp) const {
1393  // TODO: implement CFG comparisons
1394  return Cmp.comparePointers(this, E);
1395  }
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:
1408  : Terminator(COP_Branch), Condition(C) {
1409  Branches[0] = T;
1410  Branches[1] = E;
1411  }
1412 
1413  Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
1414  : Terminator(Br), Condition(C) {
1415  Branches[0] = T;
1416  Branches[1] = E;
1417  }
1418 
1419  static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1420 
1421  const SExpr *condition() const { return Condition; }
1422  SExpr *condition() { return Condition; }
1423 
1424  const BasicBlock *thenBlock() const { return Branches[0]; }
1425  BasicBlock *thenBlock() { return Branches[0]; }
1426 
1427  const BasicBlock *elseBlock() const { return Branches[1]; }
1428  BasicBlock *elseBlock() { return Branches[1]; }
1429 
1430  /// Return the list of basic blocks that this terminator can branch to.
1432  return llvm::makeArrayRef(Branches);
1433  }
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  typename C::CType compare(const Branch *E, C &Cmp) const {
1445  // TODO: implement CFG comparisons
1446  return Cmp.comparePointers(this, E);
1447  }
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  Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
1459  Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
1460 
1461  static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
1462 
1463  /// Return an empty list.
1465 
1466  SExpr *returnValue() { return Retval; }
1467  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  typename C::CType compare(const Return *E, C &Cmp) const {
1477  return Cmp.compare(Retval, E->Retval);
1478  }
1479 
1480 private:
1481  SExpr* Retval;
1482 };
1483 
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:
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  TopologyNode() = default;
1518 
1519  bool isParentOf(const TopologyNode& OtherNode) {
1520  return OtherNode.NodeID > NodeID &&
1521  OtherNode.NodeID < NodeID + SizeOfSubTree;
1522  }
1523 
1524  bool isParentOfOrEqual(const TopologyNode& OtherNode) {
1525  return OtherNode.NodeID >= NodeID &&
1526  OtherNode.NodeID < NodeID + SizeOfSubTree;
1527  }
1528  };
1529 
1531  : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {}
1533  Terminator *T)
1534  : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false),
1535  Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
1536 
1537  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  int blockID() const { return BlockID; }
1541 
1542  /// Returns the number of predecessors.
1543  size_t numPredecessors() const { return Predecessors.size(); }
1544  size_t numSuccessors() const { return successors().size(); }
1545 
1546  const SCFG* cfg() const { return CFGPtr; }
1547  SCFG* cfg() { return CFGPtr; }
1548 
1549  const BasicBlock *parent() const { return DominatorNode.Parent; }
1550  BasicBlock *parent() { return DominatorNode.Parent; }
1551 
1552  const InstrArray &arguments() const { return Args; }
1553  InstrArray &arguments() { return Args; }
1554 
1555  InstrArray &instructions() { return Instrs; }
1556  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  BlockArray &predecessors() { return Predecessors; }
1562  const BlockArray &predecessors() const { return Predecessors; }
1563 
1564  ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
1565  ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
1566 
1567  const Terminator *terminator() const { return TermInstr; }
1568  Terminator *terminator() { return TermInstr; }
1569 
1570  void setTerminator(Terminator *E) { TermInstr = E; }
1571 
1572  bool Dominates(const BasicBlock &Other) {
1573  return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
1574  }
1575 
1576  bool PostDominates(const BasicBlock &Other) {
1577  return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
1578  }
1579 
1580  /// Add a new argument.
1581  void addArgument(Phi *V) {
1582  Args.reserveCheck(1, Arena);
1583  Args.push_back(V);
1584  }
1585 
1586  /// Add a new instruction.
1588  Instrs.reserveCheck(1, Arena);
1589  Instrs.push_back(V);
1590  }
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  void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); }
1598 
1599  // Reserve space for Nins instructions.
1600  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  unsigned findPredecessorIndex(const BasicBlock *BB) const {
1607  auto I = llvm::find(Predecessors, BB);
1608  return std::distance(Predecessors.cbegin(), I);
1609  }
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  typename C::CType compare(const BasicBlock *E, C &Cmp) const {
1637  // TODO: implement CFG comparisons
1638  return Cmp.comparePointers(this, E);
1639  }
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:
1691 
1692  SCFG(MemRegionRef A, unsigned Nblocks)
1693  : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) {
1694  Entry = new (A) BasicBlock(A);
1695  Exit = new (A) BasicBlock(A);
1696  auto *V = new (A) Phi();
1697  Exit->addArgument(V);
1698  Exit->setTerminator(new (A) Return(V));
1699  add(Entry);
1700  add(Exit);
1701  }
1702 
1703  SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1704  : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) {
1705  // TODO: set entry and exit!
1706  }
1707 
1708  static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1709 
1710  /// Return true if this CFG is valid.
1711  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  bool normal() const { return Normal; }
1717 
1718  iterator begin() { return Blocks.begin(); }
1719  iterator end() { return Blocks.end(); }
1720 
1721  const_iterator begin() const { return cbegin(); }
1722  const_iterator end() const { return cend(); }
1723 
1724  const_iterator cbegin() const { return Blocks.cbegin(); }
1725  const_iterator cend() const { return Blocks.cend(); }
1726 
1727  const BasicBlock *entry() const { return Entry; }
1728  BasicBlock *entry() { return Entry; }
1729  const BasicBlock *exit() const { return Exit; }
1730  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  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  unsigned numInstructions() { return NumInstructions; }
1740 
1741  inline void add(BasicBlock *BB) {
1742  assert(BB->CFGPtr == nullptr);
1743  BB->CFGPtr = this;
1744  Blocks.reserveCheck(1, Arena);
1745  Blocks.push_back(BB);
1746  }
1747 
1748  void setEntry(BasicBlock *BB) { Entry = BB; }
1749  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  typename C::CType compare(const SCFG *E, C &Cmp) const {
1767  // TODO: implement CFG comparisons
1768  return Cmp.comparePointers(this, E);
1769  }
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  Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {}
1788  Identifier(const Identifier &) = default;
1789 
1790  static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1791 
1792  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  typename C::CType compare(const Identifier* E, C& Cmp) const {
1801  return Cmp.compareStrings(name(), E->name());
1802  }
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:
1813  : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {}
1814  IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
1815  : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {}
1816 
1817  static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1818 
1819  SExpr *condition() { return Condition; } // Address to store to
1820  const SExpr *condition() const { return Condition; }
1821 
1822  SExpr *thenExpr() { return ThenExpr; } // Value to store
1823  const SExpr *thenExpr() const { return ThenExpr; }
1824 
1825  SExpr *elseExpr() { return ElseExpr; } // Value to store
1826  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  typename C::CType compare(const IfThenElse* E, C& Cmp) const {
1838  typename C::CType Ct = Cmp.compare(condition(), E->condition());
1839  if (Cmp.notTrue(Ct))
1840  return Ct;
1841  Ct = Cmp.compare(thenExpr(), E->thenExpr());
1842  if (Cmp.notTrue(Ct))
1843  return Ct;
1844  return Cmp.compare(elseExpr(), E->elseExpr());
1845  }
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  Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1859  }
1860 
1861  Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1863  }
1864 
1865  static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1866 
1868  const Variable *variableDecl() const { return VarDecl; }
1869 
1870  SExpr *body() { return Body; }
1871  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  typename C::CType compare(const Let* E, C& Cmp) const {
1886  typename C::CType Ct =
1887  Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
1888  if (Cmp.notTrue(Ct))
1889  return Ct;
1890  Cmp.enterScope(variableDecl(), E->variableDecl());
1891  Ct = Cmp.compare(body(), E->body());
1892  Cmp.leaveScope();
1893  return Ct;
1894  }
1895 
1896 private:
1897  Variable *VarDecl;
1898  SExpr* Body;
1899 };
1900 
1901 const SExpr *getCanonicalVal(const SExpr *E);
1904 
1905 } // namespace til
1906 } // namespace threadSafety
1907 
1908 } // namespace clang
1909 
1910 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
VariableKind kind() const
Return the kind of variable (let, function param, or self)
const Variable * variableDecl() const
V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Simple arithmetic unary operations, e.g.
UnaryOp(const UnaryOp &U, SExpr *E)
const BlockArray & predecessors() const
Apply a self-argument to a self-applicable function.
unsigned index() const
Returns the index into the.
StringRef Identifier
Definition: Format.cpp:1756
ArrayRef< BasicBlock * > successors()
Pointer arithmetic, restricted to arrays only.
TIL_BinaryOpcode binaryOpcode() const
C::CType compare(const Load *E, C &Cmp) const
static bool classof(const SExpr *E)
const Terminator * terminator() const
StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op)
Return the name of a binary opcode.
Variable(SExpr *D, const ValueDecl *Cvd=nullptr)
A typed, writable location in memory.
A conditional branch to two other blocks.
C::CType compare(const BasicBlock *E, C &Cmp) const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
ValueTypes are data types that can actually be held in registers.
C::CType compare(const Identifier *E, C &Cmp) const
C::CType compare(const ArrayIndex *E, C &Cmp) const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
C::CType compare(const SApply *E, C &Cmp) const
const TIL_Opcode COP_Max
Stmt - This represents one statement.
Definition: Stmt.h:66
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
BlockArray & predecessors()
Returns a list of predecessors.
C::CType compare(const Variable *E, C &Cmp) const
void setID(BasicBlock *B, unsigned id)
Set the basic block and instruction ID for this expression.
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
UnaryOp(TIL_UnaryOpcode Op, SExpr *E)
static bool classof(const SExpr *E)
const TIL_BinaryOpcode BOP_Min
bool isParentOf(const TopologyNode &OtherNode)
StringRef P
static bool classof(const SExpr *E)
SFunction(const SFunction &F, Variable *Vd, SExpr *B)
Cast(const Cast &C, SExpr *E)
const BasicBlock * entry() const
static bool classof(const SExpr *E)
RangeSelector name(std::string ID)
Given a node with a "name", (like NamedDecl, DeclRefExpr or CxxCtorInitializer) selects the name&#39;s to...
Function(Variable *Vd, SExpr *Bd)
float __ovld __cnfn distance(float p0, float p1)
Returns the distance between p0 and p1.
BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, Terminator *T)
SExpr * simplifyToCanonicalVal(SExpr *E)
ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
const SExpr * target() const
Represents a variable declaration or definition.
Definition: Decl.h:812
Variable(StringRef s, SExpr *D=nullptr)
const TIL_UnaryOpcode UOP_Max
const internal::VariadicDynCastAllOfMatcher< Stmt, Expr > expr
Matches expressions.
StringRef name() const
Return the name of the variable, if any.
void setClangDecl(const ValueDecl *VD)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
RangeSelector range(RangeSelector Begin, RangeSelector End)
Selects from the start of Begin and to the end of End.
const SExpr * body() const
const_iterator end() const
size_t numPredecessors() const
Returns the number of predecessors.
If p is a reference to an array, then p[i] is a reference to the i&#39;th element of the array...
unsigned numInstructions()
Return the total number of instructions in the CFG.
SCFG(MemRegionRef A, unsigned Nblocks)
const SExpr * returnType() const
static bool classof(const SExpr *E)
BlockArray::const_iterator const_iterator
const InstrArray & instructions() const
Phi(const Phi &P, ValArray &&Vs)
unsigned id() const
Returns the instruction ID for this expression.
Project a named slot from a C++ struct or class.
ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
C::CType compare(const Wildcard *E, C &Cmp) const
const ValueDecl * clangDecl() const
Return the clang declaration of the variable for this Phi node, if any.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const_iterator cend() const
static bool classof(const SExpr *E)
Definition: Format.h:2327
SApply(SApply &A, SExpr *Sf, SExpr *Ar=nullptr)
const SExpr * pointer() const
C::CType compare(const UnaryOp *E, C &Cmp) const
C::CType compare(const Cast *E, C &Cmp) const
C::CType compare(const Apply *E, C &Cmp) const
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.
Definition: opencl-c-base.h:40
This declaration is definitely a definition.
Definition: Decl.h:1152
Cast(TIL_CastOpcode Op, SExpr *E)
static bool classof(const SExpr *E)
const LiteralT< T > & as() const
Base class for basic block terminators: Branch, Goto, and Return.
Let(Variable *Vd, SExpr *Bd)
BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
unsigned findPredecessorIndex(const BasicBlock *BB) const
Return the index of BB, or Predecessors.size if BB is not a predecessor.
static bool classof(const SExpr *E)
static bool classof(const SExpr *E)
static bool classof(const SExpr *E)
ArrayRef< BasicBlock * > successors()
Return the list of basic blocks that this terminator can branch to.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Return(const Return &R, SExpr *Rval)
C::CType compare(const Return *E, C &Cmp) const
A basic block is part of an SCFG.
const_iterator begin() const
void setClangDecl(const ValueDecl *Cvd)
Set the clang variable associated with this Phi node.
const ValueDecl * clangDecl() const
Placeholder for expressions that cannot be represented in the TIL.
ArrayRef< BasicBlock * > successors()
Return an empty list.
A self-applicable function.
NodeId Parent
Definition: ASTDiff.cpp:191
void addInstruction(SExpr *V)
Add a new instruction.
static bool classof(const SExpr *E)
An SCFG is a control-flow graph.
TIL_Opcode
Enum for the different distinct classes of SExpr.
Goto(const Goto &G, BasicBlock *B, unsigned I)
C::CType compare(const Call *E, C &Cmp) const
Field(const Field &C, SExpr *R, SExpr *B)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
bool isParentOfOrEqual(const TopologyNode &OtherNode)
void addArgument(Phi *V)
Add a new argument.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Apply an argument to a function.
C::CType compare(const Project *E, C &Cmp) const
StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op)
Return the name of a unary opcode.
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:636
This represents one expression.
Definition: Expr.h:108
int Id
Definition: ASTDiff.cpp:190
TIL_UnaryOpcode unaryOpcode() const
#define V(N, I)
Definition: ASTContext.h:2913
static bool classof(const SExpr *E)
C::CType compare(const Branch *E, C &Cmp) const
C::CType compare(const Alloc *E, C &Cmp) const
const Variable * variableDecl() const
static bool classof(const SExpr *E)
Call(SExpr *T, const CallExpr *Ce=nullptr)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
static bool classof(const SExpr *E)
ArrayRef< BasicBlock * > successors()
Return the list of basic blocks that this terminator can branch to.
Jump to another basic block.
const SExpr * body() const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Return from the enclosing function, passing the return value to the caller.
IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
bool normal() const
Return true if this CFG has been normalized.
static bool classof(const SExpr *E)
C::CType compare(const Store *E, C &Cmp) const
const_iterator cbegin() const
const SExpr * destination() const
Let(const Let &L, Variable *Vd, SExpr *Bd)
bool PostDominates(const BasicBlock &Other)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
bool Dominates(const BasicBlock &Other)
C::CType compare(const ArrayAdd *E, C &Cmp) const
TIL_BinaryOpcode
Opcode for binary arithmetic operations.
#define false
Definition: stdbool.h:17
Call(const Call &C, SExpr *T)
static bool classof(const SExpr *E)
static SizeType getSizeType(unsigned nbytes)
C::CType compare(const IfThenElse *E, C &Cmp) const
const TIL_BinaryOpcode BOP_Max
const BasicBlock * parent() const
Project(SExpr *R, const ValueDecl *Cvd)
static bool classof(const SExpr *E)
const ValArray & values() const
TIL_UnaryOpcode
Opcode for unary arithmetic operations.
const SExpr * getCanonicalVal(const SExpr *E)
const TIL_UnaryOpcode UOP_Min
C::CType compare(const Field *E, C &Cmp) const
const TIL_CastOpcode CAST_Max
const Variable * variableDecl() const
Function(const Function &F, Variable *Vd, SExpr *Bd)
static bool classof(const SExpr *E)
const ValueDecl * clangDecl() const
Return the clang declaration for this variable, if any.
Phi(MemRegionRef A, unsigned Nvals)
C::CType compare(const Phi *E, C &Cmp) const
Placeholder for a wildcard that matches any other expression.
TIL_CastOpcode
Opcode for cast operations.
static bool classof(const SExpr *E)
C::CType compare(const LiteralPtr *E, C &Cmp) const
ArrayRef< BasicBlock * > successors() const
LiteralT(const LiteralT< T > &L)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Variable(const Variable &Vd, SExpr *D)
SFunction(Variable *Vd, SExpr *B)
const InstrArray & arguments() const
const BasicBlock * thenBlock() const
const BasicBlock * targetBlock() const
Load a value from memory.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Dataflow Directional Tag Classes.
Allocate memory for a new value on the heap or stack.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static std::string getName(const CallEvent &Call)
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
ArrayRef< BasicBlock * > successors() const
An if-then-else expression.
const CallExpr * clangCallExpr() const
const BasicBlock * exit() const
C::CType compare(const SCFG *E, C &Cmp) const
SApply(SExpr *Sf, SExpr *A=nullptr)
BasicBlock * block() const
Returns the block, if this is an instruction in a basic block, otherwise returns null.
Goto(BasicBlock *B, unsigned I)
const SExpr * dataType() const
ArrayRef< BasicBlock * > successors()
Return the list of basic blocks that this terminator can branch to.
static bool classof(const SExpr *E)
const BasicBlock * elseBlock() const
A let-expression, e.g.
C::CType compare(const Literal *E, C &Cmp) const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
IfThenElse(SExpr *C, SExpr *T, SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
Phi Node, for code in SSA form.
bool valid() const
Return true if this CFG is valid.
Simple arithmetic binary operations, e.g.
static bool classof(const SExpr *E)
BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
A block of code – e.g. the body of a function.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const ValueDecl * clangDecl() const
C::CType compare(const Goto *E, C &Cmp) const
C::CType compare(const Let *E, C &Cmp) const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
TIL_CastOpcode castOpcode() const
SExpr * definition()
Return the definition of the variable.
Alloc(const Alloc &A, SExpr *Dt)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
size_t numBlocks() const
Return the number of blocks in the CFG.
SCFG(const SCFG &Cfg, BlockArray &&Ba)
static bool isTrivial(ASTContext &Ctx, const Expr *E)
Checks if the expression is constant or does not have non-trivial function calls. ...
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
static bool classof(const SExpr *E)
void simplifyIncompleteArg(til::Phi *Ph)
int blockID() const
Returns the block ID. Every block has a unique ID in the CFG.
C::CType compare(const BinaryOp *E, C &Cmp) const
unsigned kind
All of the diagnostics that can be emitted by the frontend.
Definition: DiagnosticIDs.h:60
C::CType compare(const SFunction *E, C &Cmp) const
Store a value to memory.
Code(const Code &C, SExpr *T, SExpr *B)
C::CType compare(const Future *E, C &Cmp) const
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2516
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Store(const Store &S, SExpr *P, SExpr *V)
Placeholder for an expression that has not yet been created.
C::CType compare(const Function *E, C &Cmp) const
C::CType compare(const Undefined *E, C &Cmp) const
Load(const Load &L, SExpr *P)
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Base class for AST nodes in the typed intermediate language.
A Literal pointer to an object allocated in memory.
C::CType compare(const Code *E, C &Cmp) const
Call a function (after all arguments have been applied).
Alloc(SExpr *D, AllocKind K)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const TIL_Opcode COP_Min
const SExpr * returnValue() const
static bool classof(const SExpr *E)
const TIL_CastOpcode CAST_Min
Apply(const Apply &A, SExpr *F, SExpr *Ar)
Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)