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