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