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