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