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,       //  ~
76   UOP_LogicNot      //  !
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 {
101   CAST_none = 0,
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;
111 const TIL_UnaryOpcode  UOP_Min  = UOP_Minus;
112 const TIL_UnaryOpcode  UOP_Max  = UOP_LogicNot;
113 const TIL_BinaryOpcode BOP_Min  = BOP_Add;
114 const TIL_BinaryOpcode BOP_Max  = BOP_LogicOr;
115 const TIL_CastOpcode   CAST_Min = CAST_none;
116 const TIL_CastOpcode   CAST_Max = CAST_toInt;
117 
118 /// Return the name of a unary opcode.
119 StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op);
120 
121 /// Return the name of a binary opcode.
122 StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op);
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,
134     BT_Bool,
135     BT_Int,
136     BT_Float,
137     BT_String,    // String literals
138     BT_Pointer,
139     BT_ValueRef
140   };
141 
142   enum SizeType : unsigned char {
143     ST_0 = 0,
144     ST_1,
145     ST_8,
146     ST_16,
147     ST_32,
148     ST_64,
149     ST_128
150   };
151 
152   inline static SizeType getSizeType(unsigned nbytes);
153 
154   template <class T>
155   inline static ValueType getValueType();
156 
ValueTypeValueType157   ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
158       : Base(B), Size(Sz), Signed(S), VectSize(VS)
159   { }
160 
161   BaseType      Base;
162   SizeType      Size;
163   bool          Signed;
164   unsigned char VectSize;  // 0 for scalar, otherwise num elements in vector
165 };
166 
167 
getSizeType(unsigned nbytes)168 inline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) {
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:
opcode()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   // }
new(size_t S,MemRegionRef & R)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).
id()289   unsigned id() const { return SExprID; }
290 
291   /// Returns the block, if this is an instruction in a basic block,
292   /// otherwise returns null.
block()293   BasicBlock* block() const { return Block; }
294 
295   /// Set the basic block and instruction ID for this expression.
setID(BasicBlock * B,unsigned id)296   void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
297 
298 protected:
SExpr(TIL_Opcode Op)299   SExpr(TIL_Opcode Op)
300     : Opcode(Op), Reserved(0), Flags(0), SExprID(0), Block(nullptr) {}
SExpr(const SExpr & E)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;
309   BasicBlock* Block;
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 {
isTrivial(const SExpr * E)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:
classof(const SExpr * E)347   static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
348 
349   enum VariableKind {
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)
SExpr(COP_Variable)356       : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr) {
357     Flags = VK_Let;
358   }
359   Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr)
SExpr(COP_Variable)360       : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
361         Definition(D), Cvdecl(Cvd) {
362     Flags = VK_Let;
363   }
Variable(const Variable & Vd,SExpr * D)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)
kind()370   VariableKind kind() const { return static_cast<VariableKind>(Flags); }
371 
372   /// Return the name of the variable, if any.
name()373   StringRef name() const { return Name; }
374 
375   /// Return the clang declaration for this variable, if any.
clangDecl()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.
definition()381   SExpr *definition() { return Definition; }
definition()382   const SExpr *definition() const { return Definition; }
383 
setName(StringRef S)384   void setName(StringRef S)    { Name = S;  }
setKind(VariableKind K)385   void setKind(VariableKind K) { Flags = K; }
setDefinition(SExpr * E)386   void setDefinition(SExpr *E) { Definition = E; }
setClangDecl(const clang::ValueDecl * VD)387   void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; }
388 
389   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Variable * E,C & Cmp)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:
classof(const SExpr * E)416   static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
417 
418   enum FutureStatus {
419     FS_pending,
420     FS_evaluating,
421     FS_done
422   };
423 
Future()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.
compute()431   virtual SExpr *compute() { return nullptr; }
432 
433   // Return the result of this future if it exists, otherwise return null.
maybeGetResult()434   SExpr *maybeGetResult() const {
435     return Result;
436   }
437 
438   // Return the result of this future; forcing it if necessary.
result()439   SExpr *result() {
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>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Future * E,C & Cmp)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:
classof(const SExpr * E)474   static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
475 
SExpr(COP_Undefined)476   Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
Undefined(const Undefined & U)477   Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
478 
479   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)480   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
481     return Vs.reduceUndefined(*this);
482   }
483 
484   template <class C>
compare(const Undefined * E,C & Cmp)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:
classof(const SExpr * E)497   static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
498 
Wildcard()499   Wildcard() : SExpr(COP_Wildcard) {}
Wildcard(const Wildcard & W)500   Wildcard(const Wildcard &W) : SExpr(W) {}
501 
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Wildcard * E,C & Cmp)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:
classof(const SExpr * E)518   static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
519 
Literal(const clang::Expr * C)520   Literal(const clang::Expr *C)
521      : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C)
522   { }
Literal(ValueType VT)523   Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {}
Literal(const Literal & L)524   Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {}
525 
526   // The clang expression for this literal.
clangExpr()527   const clang::Expr *clangExpr() const { return Cexpr; }
528 
valueType()529   ValueType valueType() const { return ValType; }
530 
as()531   template<class T> const LiteralT<T>& as() const {
532     return *static_cast<const LiteralT<T>*>(this);
533   }
as()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>
compare(const Literal * E,C & Cmp)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:
LiteralT(T Dat)556   LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { }
LiteralT(const LiteralT<T> & L)557   LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { }
558 
value()559   T  value() const { return Val;}
value()560   T& value() { return Val; }
561 
562 private:
563   T Val;
564 };
565 
566 
567 
568 template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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   }
614   case ValueType::BT_String:
615     return Vs.reduceLiteralT(as<StringRef>());
616   case ValueType::BT_Pointer:
617     return Vs.reduceLiteralT(as<void*>());
618   case ValueType::BT_ValueRef:
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:
classof(const SExpr * E)629   static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
630 
LiteralPtr(const clang::ValueDecl * D)631   LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
LiteralPtr(const LiteralPtr & R)632   LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {}
633 
634   // The clang declaration for the value that this pointer points to.
clangDecl()635   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
636 
637   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)638   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
639     return Vs.reduceLiteralPtr(*this);
640   }
641 
642   template <class C>
compare(const LiteralPtr * E,C & Cmp)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:
classof(const SExpr * E)657   static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
658 
Function(Variable * Vd,SExpr * Bd)659   Function(Variable *Vd, SExpr *Bd)
660       : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
661     Vd->setKind(Variable::VK_Fun);
662   }
Function(const Function & F,Variable * Vd,SExpr * Bd)663   Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
664       : SExpr(F), VarDecl(Vd), Body(Bd) {
665     Vd->setKind(Variable::VK_Fun);
666   }
667 
variableDecl()668   Variable *variableDecl()  { return VarDecl; }
variableDecl()669   const Variable *variableDecl() const { return VarDecl; }
670 
body()671   SExpr *body() { return Body; }
body()672   const SExpr *body() const { return Body; }
673 
674   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Function * E,C & Cmp)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:
classof(const SExpr * E)708   static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
709 
SFunction(Variable * Vd,SExpr * B)710   SFunction(Variable *Vd, SExpr *B)
711       : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
712     assert(Vd->Definition == nullptr);
713     Vd->setKind(Variable::VK_SFun);
714     Vd->Definition = this;
715   }
SFunction(const SFunction & F,Variable * Vd,SExpr * B)716   SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
717       : SExpr(F), VarDecl(Vd), Body(B) {
718     assert(Vd->Definition == nullptr);
719     Vd->setKind(Variable::VK_SFun);
720     Vd->Definition = this;
721   }
722 
variableDecl()723   Variable *variableDecl() { return VarDecl; }
variableDecl()724   const Variable *variableDecl() const { return VarDecl; }
725 
body()726   SExpr *body() { return Body; }
body()727   const SExpr *body() const { return Body; }
728 
729   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const SFunction * E,C & Cmp)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:
classof(const SExpr * E)758   static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
759 
Code(SExpr * T,SExpr * B)760   Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
Code(const Code & C,SExpr * T,SExpr * B)761   Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
762       : SExpr(C), ReturnType(T), Body(B) {}
763 
returnType()764   SExpr *returnType() { return ReturnType; }
returnType()765   const SExpr *returnType() const { return ReturnType; }
766 
body()767   SExpr *body() { return Body; }
body()768   const SExpr *body() const { return Body; }
769 
770   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Code * E,C & Cmp)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:
classof(const SExpr * E)794   static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
795 
Field(SExpr * R,SExpr * B)796   Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
Field(const Field & C,SExpr * R,SExpr * B)797   Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
798       : SExpr(C), Range(R), Body(B) {}
799 
range()800   SExpr *range() { return Range; }
range()801   const SExpr *range() const { return Range; }
802 
body()803   SExpr *body() { return Body; }
body()804   const SExpr *body() const { return Body; }
805 
806   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Field * E,C & Cmp)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:
classof(const SExpr * E)834   static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
835 
Apply(SExpr * F,SExpr * A)836   Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
Apply(const Apply & A,SExpr * F,SExpr * Ar)837   Apply(const Apply &A, SExpr *F, SExpr *Ar)  // rewrite constructor
838       : SExpr(A), Fun(F), Arg(Ar)
839   {}
840 
fun()841   SExpr *fun() { return Fun; }
fun()842   const SExpr *fun() const { return Fun; }
843 
arg()844   SExpr *arg() { return Arg; }
arg()845   const SExpr *arg() const { return Arg; }
846 
847   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Apply * E,C & Cmp)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:
classof(const SExpr * E)871   static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
872 
SExpr(COP_SApply)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
SExpr(A)875       : SExpr(A), Sfun(Sf), Arg(Ar) {}
876 
sfun()877   SExpr *sfun() { return Sfun; }
sfun()878   const SExpr *sfun() const { return Sfun; }
879 
arg()880   SExpr *arg() { return Arg ? Arg : Sfun; }
arg()881   const SExpr *arg() const { return Arg ? Arg : Sfun; }
882 
isDelegation()883   bool isDelegation() const { return Arg != nullptr; }
884 
885   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const SApply * E,C & Cmp)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:
classof(const SExpr * E)910   static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
911 
Project(SExpr * R,StringRef SName)912   Project(SExpr *R, StringRef SName)
913       : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr)
914   { }
Project(SExpr * R,const clang::ValueDecl * Cvd)915   Project(SExpr *R, const clang::ValueDecl *Cvd)
916       : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd)
917   { }
Project(const Project & P,SExpr * R)918   Project(const Project &P, SExpr *R)
919       : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl)
920   { }
921 
record()922   SExpr *record() { return Rec; }
record()923   const SExpr *record() const { return Rec; }
924 
clangDecl()925   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
926 
isArrow()927   bool isArrow() const { return (Flags & 0x01) != 0; }
setArrow(bool b)928   void setArrow(bool b) {
929     if (b) Flags |= 0x01;
930     else Flags &= 0xFFFE;
931   }
932 
slotName()933   StringRef slotName() const {
934     if (Cvdecl)
935       return Cvdecl->getName();
936     else
937       return SlotName;
938   }
939 
940   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Project * E,C & Cmp)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   StringRef 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:
classof(const SExpr * E)964   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
965 
966   Call(SExpr *T, const clang::CallExpr *Ce = nullptr)
SExpr(COP_Call)967       : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
Call(const Call & C,SExpr * T)968   Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
969 
target()970   SExpr *target() { return Target; }
target()971   const SExpr *target() const { return Target; }
972 
clangCallExpr()973   const clang::CallExpr *clangCallExpr() const { return Cexpr; }
974 
975   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Call * E,C & Cmp)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:
classof(const SExpr * E)995   static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
996 
997   enum AllocKind {
998     AK_Stack,
999     AK_Heap
1000   };
1001 
Alloc(SExpr * D,AllocKind K)1002   Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
Alloc(const Alloc & A,SExpr * Dt)1003   Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1004 
kind()1005   AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1006 
dataType()1007   SExpr *dataType() { return Dtype; }
dataType()1008   const SExpr *dataType() const { return Dtype; }
1009 
1010   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Alloc * E,C & Cmp)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:
classof(const SExpr * E)1032   static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1033 
Load(SExpr * P)1034   Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
Load(const Load & L,SExpr * P)1035   Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1036 
pointer()1037   SExpr *pointer() { return Ptr; }
pointer()1038   const SExpr *pointer() const { return Ptr; }
1039 
1040   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Load * E,C & Cmp)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:
classof(const SExpr * E)1060   static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1061 
Store(SExpr * P,SExpr * V)1062   Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
Store(const Store & S,SExpr * P,SExpr * V)1063   Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1064 
destination()1065   SExpr *destination() { return Dest; }  // Address to store to
destination()1066   const SExpr *destination() const { return Dest; }
1067 
source()1068   SExpr *source() { return Source; }     // Value to store
source()1069   const SExpr *source() const { return Source; }
1070 
1071   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Store * E,C & Cmp)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:
classof(const SExpr * E)1096   static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1097 
ArrayIndex(SExpr * A,SExpr * N)1098   ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
ArrayIndex(const ArrayIndex & E,SExpr * A,SExpr * N)1099   ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
1100     : SExpr(E), Array(A), Index(N) {}
1101 
array()1102   SExpr *array() { return Array; }
array()1103   const SExpr *array() const { return Array; }
1104 
index()1105   SExpr *index() { return Index; }
index()1106   const SExpr *index() const { return Index; }
1107 
1108   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const ArrayIndex * E,C & Cmp)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:
classof(const SExpr * E)1134   static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1135 
ArrayAdd(SExpr * A,SExpr * N)1136   ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
ArrayAdd(const ArrayAdd & E,SExpr * A,SExpr * N)1137   ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1138     : SExpr(E), Array(A), Index(N) {}
1139 
array()1140   SExpr *array() { return Array; }
array()1141   const SExpr *array() const { return Array; }
1142 
index()1143   SExpr *index() { return Index; }
index()1144   const SExpr *index() const { return Index; }
1145 
1146   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const ArrayAdd * E,C & Cmp)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:
classof(const SExpr * E)1171   static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1172 
UnaryOp(TIL_UnaryOpcode Op,SExpr * E)1173   UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1174     Flags = Op;
1175   }
UnaryOp(const UnaryOp & U,SExpr * E)1176   UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1177 
unaryOpcode()1178   TIL_UnaryOpcode unaryOpcode() const {
1179     return static_cast<TIL_UnaryOpcode>(Flags);
1180   }
1181 
expr()1182   SExpr *expr() { return Expr0; }
expr()1183   const SExpr *expr() const { return Expr0; }
1184 
1185   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const UnaryOp * E,C & Cmp)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:
classof(const SExpr * E)1209   static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1210 
BinaryOp(TIL_BinaryOpcode Op,SExpr * E0,SExpr * E1)1211   BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
1212       : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1213     Flags = Op;
1214   }
BinaryOp(const BinaryOp & B,SExpr * E0,SExpr * E1)1215   BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1216       : SExpr(B), Expr0(E0), Expr1(E1) {
1217     Flags = B.Flags;
1218   }
1219 
binaryOpcode()1220   TIL_BinaryOpcode binaryOpcode() const {
1221     return static_cast<TIL_BinaryOpcode>(Flags);
1222   }
1223 
expr0()1224   SExpr *expr0() { return Expr0; }
expr0()1225   const SExpr *expr0() const { return Expr0; }
1226 
expr1()1227   SExpr *expr1() { return Expr1; }
expr1()1228   const SExpr *expr1() const { return Expr1; }
1229 
1230   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const BinaryOp * E,C & Cmp)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:
classof(const SExpr * E)1260   static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1261 
Cast(TIL_CastOpcode Op,SExpr * E)1262   Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
Cast(const Cast & C,SExpr * E)1263   Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1264 
castOpcode()1265   TIL_CastOpcode castOpcode() const {
1266     return static_cast<TIL_CastOpcode>(Flags);
1267   }
1268 
expr()1269   SExpr *expr() { return Expr0; }
expr()1270   const SExpr *expr() const { return Expr0; }
1271 
1272   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Cast * E,C & Cmp)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:
1300   typedef SimpleArray<SExpr *> ValArray;
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 
classof(const SExpr * E)1311   static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1312 
Phi()1313   Phi()
1314     : SExpr(COP_Phi), Cvdecl(nullptr) {}
Phi(MemRegionRef A,unsigned Nvals)1315   Phi(MemRegionRef A, unsigned Nvals)
1316     : SExpr(COP_Phi), Values(A, Nvals), Cvdecl(nullptr)  {}
Phi(const Phi & P,ValArray && Vs)1317   Phi(const Phi &P, ValArray &&Vs)
1318     : SExpr(P), Values(std::move(Vs)), Cvdecl(nullptr) {}
1319 
values()1320   const ValArray &values() const { return Values; }
values()1321   ValArray &values() { return Values; }
1322 
status()1323   Status status() const { return static_cast<Status>(Flags); }
setStatus(Status s)1324   void setStatus(Status s) { Flags = s; }
1325 
1326   /// Return the clang declaration of the variable for this Phi node, if any.
clangDecl()1327   const clang::ValueDecl *clangDecl() const { return Cvdecl; }
1328 
1329   /// Set the clang variable associated with this Phi node.
setClangDecl(const clang::ValueDecl * Cvd)1330   void setClangDecl(const clang::ValueDecl *Cvd) { Cvdecl = Cvd; }
1331 
1332   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Phi * E,C & Cmp)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:
classof(const SExpr * E)1358   static bool classof(const SExpr *E) {
1359     return E->opcode() >= COP_Goto && E->opcode() <= COP_Return;
1360   }
1361 
1362 protected:
Terminator(TIL_Opcode Op)1363   Terminator(TIL_Opcode Op)  : SExpr(Op) {}
Terminator(const SExpr & E)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 
successors()1370   ArrayRef<BasicBlock*> successors() const {
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:
classof(const SExpr * E)1383   static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1384 
Goto(BasicBlock * B,unsigned I)1385   Goto(BasicBlock *B, unsigned I)
1386       : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
Goto(const Goto & G,BasicBlock * B,unsigned I)1387   Goto(const Goto &G, BasicBlock *B, unsigned I)
1388       : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1389 
targetBlock()1390   const BasicBlock *targetBlock() const { return TargetBlock; }
targetBlock()1391   BasicBlock *targetBlock() { return TargetBlock; }
1392 
1393   /// Returns the index into the
index()1394   unsigned index() const { return Index; }
1395 
1396   /// Return the list of basic blocks that this terminator can branch to.
successors()1397   ArrayRef<BasicBlock*> successors() {
1398     return TargetBlock;
1399   }
1400 
1401   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Goto * E,C & Cmp)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:
classof(const SExpr * E)1424   static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1425 
Branch(SExpr * C,BasicBlock * T,BasicBlock * E)1426   Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
1427       : Terminator(COP_Branch), Condition(C) {
1428     Branches[0] = T;
1429     Branches[1] = E;
1430   }
Branch(const Branch & Br,SExpr * C,BasicBlock * T,BasicBlock * E)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 
condition()1437   const SExpr *condition() const { return Condition; }
condition()1438   SExpr *condition() { return Condition; }
1439 
thenBlock()1440   const BasicBlock *thenBlock() const { return Branches[0]; }
thenBlock()1441   BasicBlock *thenBlock() { return Branches[0]; }
1442 
elseBlock()1443   const BasicBlock *elseBlock() const { return Branches[1]; }
elseBlock()1444   BasicBlock *elseBlock() { return Branches[1]; }
1445 
1446   /// Return the list of basic blocks that this terminator can branch to.
successors()1447   ArrayRef<BasicBlock*> successors() {
1448     return llvm::makeArrayRef(Branches);
1449   }
1450 
1451   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Branch * E,C & Cmp)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:
classof(const SExpr * E)1475   static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
1476 
Return(SExpr * Rval)1477   Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
Return(const Return & R,SExpr * Rval)1478   Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
1479 
1480   /// Return an empty list.
successors()1481   ArrayRef<BasicBlock*> successors() {
1482     return None;
1483   }
1484 
returnValue()1485   SExpr *returnValue() { return Retval; }
returnValue()1486   const SExpr *returnValue() const { return Retval; }
1487 
1488   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Return * E,C & Cmp)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 
successors()1504 inline ArrayRef<BasicBlock*> Terminator::successors() {
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:
1522   typedef SimpleArray<SExpr*>      InstrArray;
1523   typedef SimpleArray<BasicBlock*> BlockArray;
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 {
TopologyNodeTopologyNode1530     TopologyNode() : NodeID(0), SizeOfSubTree(0), Parent(nullptr) {}
1531 
isParentOfTopologyNode1532     bool isParentOf(const TopologyNode& OtherNode) {
1533       return OtherNode.NodeID > NodeID &&
1534              OtherNode.NodeID < NodeID + SizeOfSubTree;
1535     }
1536 
isParentOfOrEqualTopologyNode1537     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 
classof(const SExpr * E)1547   static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
1548 
BasicBlock(MemRegionRef A)1549   explicit BasicBlock(MemRegionRef A)
1550       : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),
1551         Visited(0), TermInstr(nullptr) {}
BasicBlock(BasicBlock & B,MemRegionRef A,InstrArray && As,InstrArray && Is,Terminator * T)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.
blockID()1558   int blockID() const { return BlockID; }
1559 
1560   /// Returns the number of predecessors.
numPredecessors()1561   size_t numPredecessors() const { return Predecessors.size(); }
numSuccessors()1562   size_t numSuccessors() const { return successors().size(); }
1563 
cfg()1564   const SCFG* cfg() const { return CFGPtr; }
cfg()1565   SCFG* cfg() { return CFGPtr; }
1566 
parent()1567   const BasicBlock *parent() const { return DominatorNode.Parent; }
parent()1568   BasicBlock *parent() { return DominatorNode.Parent; }
1569 
arguments()1570   const InstrArray &arguments() const { return Args; }
arguments()1571   InstrArray &arguments() { return Args; }
1572 
instructions()1573   InstrArray &instructions() { return Instrs; }
instructions()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.
predecessors()1579   BlockArray &predecessors() { return Predecessors; }
predecessors()1580   const BlockArray &predecessors() const { return Predecessors; }
1581 
successors()1582   ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); }
successors()1583   ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
1584 
terminator()1585   const Terminator *terminator() const { return TermInstr; }
terminator()1586   Terminator *terminator() { return TermInstr; }
1587 
setTerminator(Terminator * E)1588   void setTerminator(Terminator *E) { TermInstr = E; }
1589 
Dominates(const BasicBlock & Other)1590   bool Dominates(const BasicBlock &Other) {
1591     return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
1592   }
1593 
PostDominates(const BasicBlock & Other)1594   bool PostDominates(const BasicBlock &Other) {
1595     return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
1596   }
1597 
1598   /// Add a new argument.
addArgument(Phi * V)1599   void addArgument(Phi *V) {
1600     Args.reserveCheck(1, Arena);
1601     Args.push_back(V);
1602   }
1603   /// Add a new instruction.
addInstruction(SExpr * V)1604   void addInstruction(SExpr *V) {
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.
reserveArguments(unsigned Nargs)1613   void reserveArguments(unsigned Nargs)   { Args.reserve(Nargs, Arena); }
1614 
1615   // Reserve space for Nins instructions.
reserveInstructions(unsigned Nins)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.
findPredecessorIndex(const BasicBlock * BB)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>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const BasicBlock * E,C & Cmp)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:
1688   typedef SimpleArray<BasicBlock *> BlockArray;
1689   typedef BlockArray::iterator iterator;
1690   typedef BlockArray::const_iterator const_iterator;
1691 
classof(const SExpr * E)1692   static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1693 
SCFG(MemRegionRef A,unsigned Nblocks)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   }
SCFG(const SCFG & Cfg,BlockArray && Ba)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.
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.
normal()1717   bool normal() const { return Normal; }
1718 
begin()1719   iterator begin() { return Blocks.begin(); }
end()1720   iterator end() { return Blocks.end(); }
1721 
begin()1722   const_iterator begin() const { return cbegin(); }
end()1723   const_iterator end() const { return cend(); }
1724 
cbegin()1725   const_iterator cbegin() const { return Blocks.cbegin(); }
cend()1726   const_iterator cend() const { return Blocks.cend(); }
1727 
entry()1728   const BasicBlock *entry() const { return Entry; }
entry()1729   BasicBlock *entry() { return Entry; }
exit()1730   const BasicBlock *exit() const { return Exit; }
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();
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().
numInstructions()1740   unsigned numInstructions() { return NumInstructions; }
1741 
add(BasicBlock * BB)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 
setEntry(BasicBlock * BB)1749   void setEntry(BasicBlock *BB) { Entry = BB; }
setExit(BasicBlock * BB)1750   void setExit(BasicBlock *BB)  { Exit = BB;  }
1751 
1752   void computeNormalForm();
1753 
1754   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const SCFG * E,C & Cmp)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:
classof(const SExpr * E)1790   static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1791 
Identifier(StringRef Id)1792   Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { }
Identifier(const Identifier & I)1793   Identifier(const Identifier& I) : SExpr(I), Name(I.Name)  { }
1794 
name()1795   StringRef name() const { return Name; }
1796 
1797   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)1798   typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1799     return Vs.reduceIdentifier(*this);
1800   }
1801 
1802   template <class C>
compare(const Identifier * E,C & Cmp)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:
classof(const SExpr * E)1816   static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1817 
IfThenElse(SExpr * C,SExpr * T,SExpr * E)1818   IfThenElse(SExpr *C, SExpr *T, SExpr *E)
1819     : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E)
1820   { }
IfThenElse(const IfThenElse & I,SExpr * C,SExpr * T,SExpr * E)1821   IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
1822     : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E)
1823   { }
1824 
condition()1825   SExpr *condition() { return Condition; }   // Address to store to
condition()1826   const SExpr *condition() const { return Condition; }
1827 
thenExpr()1828   SExpr *thenExpr() { return ThenExpr; }     // Value to store
thenExpr()1829   const SExpr *thenExpr() const { return ThenExpr; }
1830 
elseExpr()1831   SExpr *elseExpr() { return ElseExpr; }     // Value to store
elseExpr()1832   const SExpr *elseExpr() const { return ElseExpr; }
1833 
1834   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const IfThenElse * E,C & Cmp)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:
classof(const SExpr * E)1864   static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1865 
Let(Variable * Vd,SExpr * Bd)1866   Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1867     Vd->setKind(Variable::VK_Let);
1868   }
Let(const Let & L,Variable * Vd,SExpr * Bd)1869   Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1870     Vd->setKind(Variable::VK_Let);
1871   }
1872 
variableDecl()1873   Variable *variableDecl()  { return VarDecl; }
variableDecl()1874   const Variable *variableDecl() const { return VarDecl; }
1875 
body()1876   SExpr *body() { return Body; }
body()1877   const SExpr *body() const { return Body; }
1878 
1879   template <class V>
traverse(V & Vs,typename V::R_Ctx Ctx)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>
compare(const Let * E,C & Cmp)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);
1910 SExpr* simplifyToCanonicalVal(SExpr *E);
1911 void simplifyIncompleteArg(til::Phi *Ph);
1912 
1913 
1914 } // end namespace til
1915 } // end namespace threadSafety
1916 } // end namespace clang
1917 
1918 #endif
1919