clang 17.0.0git
ThreadSafetyTIL.h
Go to the documentation of this file.
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"
51#include "clang/Basic/LLVM.h"
52#include "llvm/ADT/ArrayRef.h"
53#include "llvm/ADT/StringRef.h"
54#include "llvm/Support/Casting.h"
55#include "llvm/Support/raw_ostream.h"
56#include <algorithm>
57#include <cassert>
58#include <cstddef>
59#include <cstdint>
60#include <iterator>
61#include <optional>
62#include <string>
63#include <utility>
64
65namespace clang {
66
67class CallExpr;
68class Expr;
69class Stmt;
70
71namespace threadSafety {
72namespace til {
73
74class BasicBlock;
75
76/// Enum for the different distinct classes of SExpr
77enum TIL_Opcode : unsigned char {
78#define TIL_OPCODE_DEF(X) COP_##X,
79#include "ThreadSafetyOps.def"
80#undef TIL_OPCODE_DEF
81};
82
83/// Opcode for unary arithmetic operations.
84enum TIL_UnaryOpcode : unsigned char {
87 UOP_LogicNot // !
88};
89
90/// Opcode for binary arithmetic operations.
91enum TIL_BinaryOpcode : unsigned char {
92 BOP_Add, // +
93 BOP_Sub, // -
94 BOP_Mul, // *
95 BOP_Div, // /
96 BOP_Rem, // %
97 BOP_Shl, // <<
98 BOP_Shr, // >>
102 BOP_Eq, // ==
103 BOP_Neq, // !=
104 BOP_Lt, // <
105 BOP_Leq, // <=
106 BOP_Cmp, // <=>
107 BOP_LogicAnd, // && (no short-circuit)
108 BOP_LogicOr // || (no short-circuit)
110
111/// Opcode for cast operations.
112enum TIL_CastOpcode : unsigned char {
114
115 // Extend precision of numeric type
117
118 // Truncate precision of numeric type
120
121 // Convert to floating point type
123
124 // Convert to integer type
126
127 // Convert smart pointer to pointer (C++ only)
130
131const TIL_Opcode COP_Min = COP_Future;
132const TIL_Opcode COP_Max = COP_Branch;
139
140/// Return the name of a unary opcode.
142
143/// Return the name of a binary opcode.
145
146/// ValueTypes are data types that can actually be held in registers.
147/// All variables and expressions must have a value type.
148/// Pointer types are further subdivided into the various heap-allocated
149/// types, such as functions, records, etc.
150/// Structured types that are passed by value (e.g. complex numbers)
151/// require special handling; they use BT_ValueRef, and size ST_0.
152struct ValueType {
153 enum BaseType : unsigned char {
158 BT_String, // String literals
161 };
162
163 enum SizeType : unsigned char {
164 ST_0 = 0,
170 ST_128
171 };
172
173 ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
174 : Base(B), Size(Sz), Signed(S), VectSize(VS) {}
175
176 inline static SizeType getSizeType(unsigned nbytes);
177
178 template <class T>
179 inline static ValueType getValueType();
180
183 bool Signed;
184
185 // 0 for scalar, otherwise num elements in vector
186 unsigned char VectSize;
187};
188
190 switch (nbytes) {
191 case 1: return ST_8;
192 case 2: return ST_16;
193 case 4: return ST_32;
194 case 8: return ST_64;
195 case 16: return ST_128;
196 default: return ST_0;
197 }
198}
199
200template<>
201inline ValueType ValueType::getValueType<void>() {
202 return ValueType(BT_Void, ST_0, false, 0);
203}
204
205template<>
206inline ValueType ValueType::getValueType<bool>() {
207 return ValueType(BT_Bool, ST_1, false, 0);
208}
209
210template<>
211inline ValueType ValueType::getValueType<int8_t>() {
212 return ValueType(BT_Int, ST_8, true, 0);
213}
214
215template<>
216inline ValueType ValueType::getValueType<uint8_t>() {
217 return ValueType(BT_Int, ST_8, false, 0);
218}
219
220template<>
221inline ValueType ValueType::getValueType<int16_t>() {
222 return ValueType(BT_Int, ST_16, true, 0);
223}
224
225template<>
226inline ValueType ValueType::getValueType<uint16_t>() {
227 return ValueType(BT_Int, ST_16, false, 0);
228}
229
230template<>
231inline ValueType ValueType::getValueType<int32_t>() {
232 return ValueType(BT_Int, ST_32, true, 0);
233}
234
235template<>
236inline ValueType ValueType::getValueType<uint32_t>() {
237 return ValueType(BT_Int, ST_32, false, 0);
238}
239
240template<>
241inline ValueType ValueType::getValueType<int64_t>() {
242 return ValueType(BT_Int, ST_64, true, 0);
243}
244
245template<>
246inline ValueType ValueType::getValueType<uint64_t>() {
247 return ValueType(BT_Int, ST_64, false, 0);
248}
249
250template<>
251inline ValueType ValueType::getValueType<float>() {
252 return ValueType(BT_Float, ST_32, true, 0);
253}
254
255template<>
256inline ValueType ValueType::getValueType<double>() {
257 return ValueType(BT_Float, ST_64, true, 0);
258}
259
260template<>
261inline ValueType ValueType::getValueType<long double>() {
262 return ValueType(BT_Float, ST_128, true, 0);
263}
264
265template<>
266inline ValueType ValueType::getValueType<StringRef>() {
267 return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0);
268}
269
270template<>
271inline ValueType ValueType::getValueType<void*>() {
272 return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0);
273}
274
275/// Base class for AST nodes in the typed intermediate language.
276class SExpr {
277public:
278 SExpr() = delete;
279
280 TIL_Opcode opcode() const { return Opcode; }
281
282 // Subclasses of SExpr must define the following:
283 //
284 // This(const This& E, ...) {
285 // copy constructor: construct copy of E, with some additional arguments.
286 // }
287 //
288 // template <class V>
289 // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
290 // traverse all subexpressions, following the traversal/rewriter interface.
291 // }
292 //
293 // template <class C> typename C::CType compare(CType* E, C& Cmp) {
294 // compare all subexpressions, following the comparator interface
295 // }
296 void *operator new(size_t S, MemRegionRef &R) {
297 return ::operator new(S, R);
298 }
299
300 /// SExpr objects must be created in an arena.
301 void *operator new(size_t) = delete;
302
303 /// SExpr objects cannot be deleted.
304 // This declaration is public to workaround a gcc bug that breaks building
305 // with REQUIRES_EH=1.
306 void operator delete(void *) = delete;
307
308 /// Returns the instruction ID for this expression.
309 /// All basic block instructions have a unique ID (i.e. virtual register).
310 unsigned id() const { return SExprID; }
311
312 /// Returns the block, if this is an instruction in a basic block,
313 /// otherwise returns null.
314 BasicBlock *block() const { return Block; }
315
316 /// Set the basic block and instruction ID for this expression.
317 void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; }
318
319protected:
321 SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {}
322
324 unsigned char Reserved = 0;
325 unsigned short Flags = 0;
326 unsigned SExprID = 0;
327 BasicBlock *Block = nullptr;
328};
329
330// Contains various helper functions for SExprs.
331namespace ThreadSafetyTIL {
332
333inline bool isTrivial(const SExpr *E) {
334 TIL_Opcode Op = E->opcode();
335 return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr;
336}
337
338} // namespace ThreadSafetyTIL
339
340// Nodes which declare variables
341
342/// A named variable, e.g. "x".
343///
344/// There are two distinct places in which a Variable can appear in the AST.
345/// A variable declaration introduces a new variable, and can occur in 3 places:
346/// Let-expressions: (Let (x = t) u)
347/// Functions: (Function (x : t) u)
348/// Self-applicable functions (SFunction (x) t)
349///
350/// If a variable occurs in any other location, it is a reference to an existing
351/// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't
352/// allocate a separate AST node for variable references; a reference is just a
353/// pointer to the original declaration.
354class Variable : public SExpr {
355public:
357 /// Let-variable
359
360 /// Function parameter
362
363 /// SFunction (self) parameter
364 VK_SFun
365 };
366
367 Variable(StringRef s, SExpr *D = nullptr)
368 : SExpr(COP_Variable), Name(s), Definition(D) {
369 Flags = VK_Let;
370 }
371
372 Variable(SExpr *D, const ValueDecl *Cvd = nullptr)
373 : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"),
374 Definition(D), Cvdecl(Cvd) {
375 Flags = VK_Let;
376 }
377
378 Variable(const Variable &Vd, SExpr *D) // rewrite constructor
379 : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) {
380 Flags = Vd.kind();
381 }
382
383 static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; }
384
385 /// Return the kind of variable (let, function param, or self)
386 VariableKind kind() const { return static_cast<VariableKind>(Flags); }
387
388 /// Return the name of the variable, if any.
389 StringRef name() const { return Name; }
390
391 /// Return the clang declaration for this variable, if any.
392 const ValueDecl *clangDecl() const { return Cvdecl; }
393
394 /// Return the definition of the variable.
395 /// For let-vars, this is the setting expression.
396 /// For function and self parameters, it is the type of the variable.
397 SExpr *definition() { return Definition; }
398 const SExpr *definition() const { return Definition; }
399
400 void setName(StringRef S) { Name = S; }
401 void setKind(VariableKind K) { Flags = K; }
402 void setDefinition(SExpr *E) { Definition = E; }
403 void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; }
404
405 template <class V>
406 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
407 // This routine is only called for variable references.
408 return Vs.reduceVariableRef(this);
409 }
410
411 template <class C>
412 typename C::CType compare(const Variable* E, C& Cmp) const {
413 return Cmp.compareVariableRefs(this, E);
414 }
415
416private:
417 friend class BasicBlock;
418 friend class Function;
419 friend class Let;
420 friend class SFunction;
421
422 // The name of the variable.
423 StringRef Name;
424
425 // The TIL type or definition.
426 SExpr *Definition;
427
428 // The clang declaration for this variable.
429 const ValueDecl *Cvdecl = nullptr;
430};
431
432/// Placeholder for an expression that has not yet been created.
433/// Used to implement lazy copy and rewriting strategies.
434class Future : public SExpr {
435public:
439 FS_done
440 };
441
442 Future() : SExpr(COP_Future) {}
443 virtual ~Future() = delete;
444
445 static bool classof(const SExpr *E) { return E->opcode() == COP_Future; }
446
447 // A lazy rewriting strategy should subclass Future and override this method.
448 virtual SExpr *compute() { return nullptr; }
449
450 // Return the result of this future if it exists, otherwise return null.
451 SExpr *maybeGetResult() const { return Result; }
452
453 // Return the result of this future; forcing it if necessary.
455 switch (Status) {
456 case FS_pending:
457 return force();
458 case FS_evaluating:
459 return nullptr; // infinite loop; illegal recursion.
460 case FS_done:
461 return Result;
462 }
463 }
464
465 template <class V>
466 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
467 assert(Result && "Cannot traverse Future that has not been forced.");
468 return Vs.traverse(Result, Ctx);
469 }
470
471 template <class C>
472 typename C::CType compare(const Future* E, C& Cmp) const {
473 if (!Result || !E->Result)
474 return Cmp.comparePointers(this, E);
475 return Cmp.compare(Result, E->Result);
476 }
477
478private:
479 SExpr* force();
480
481 FutureStatus Status = FS_pending;
482 SExpr *Result = nullptr;
483};
484
485/// Placeholder for expressions that cannot be represented in the TIL.
486class Undefined : public SExpr {
487public:
488 Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {}
489 Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {}
490
491 static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; }
492
493 template <class V>
494 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
495 return Vs.reduceUndefined(*this);
496 }
497
498 template <class C>
499 typename C::CType compare(const Undefined* E, C& Cmp) const {
500 return Cmp.trueResult();
501 }
502
503private:
504 const Stmt *Cstmt;
505};
506
507/// Placeholder for a wildcard that matches any other expression.
508class Wildcard : public SExpr {
509public:
510 Wildcard() : SExpr(COP_Wildcard) {}
511 Wildcard(const Wildcard &) = default;
512
513 static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; }
514
515 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
516 return Vs.reduceWildcard(*this);
517 }
518
519 template <class C>
520 typename C::CType compare(const Wildcard* E, C& Cmp) const {
521 return Cmp.trueResult();
522 }
523};
524
525template <class T> class LiteralT;
526
527// Base class for literal values.
528class Literal : public SExpr {
529public:
530 Literal(const Expr *C)
531 : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) {}
532 Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT) {}
533 Literal(const Literal &) = default;
534
535 static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; }
536
537 // The clang expression for this literal.
538 const Expr *clangExpr() const { return Cexpr; }
539
540 ValueType valueType() const { return ValType; }
541
542 template<class T> const LiteralT<T>& as() const {
543 return *static_cast<const LiteralT<T>*>(this);
544 }
545 template<class T> LiteralT<T>& as() {
546 return *static_cast<LiteralT<T>*>(this);
547 }
548
549 template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx);
550
551 template <class C>
552 typename C::CType compare(const Literal* E, C& Cmp) const {
553 // TODO: defer actual comparison to LiteralT
554 return Cmp.trueResult();
555 }
556
557private:
558 const ValueType ValType;
559 const Expr *Cexpr = nullptr;
560};
561
562// Derived class for literal values, which stores the actual value.
563template<class T>
564class LiteralT : public Literal {
565public:
566 LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {}
567 LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {}
568
569 T value() const { return Val;}
570 T& value() { return Val; }
571
572private:
573 T Val;
574};
575
576template <class V>
577typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) {
578 if (Cexpr)
579 return Vs.reduceLiteral(*this);
580
581 switch (ValType.Base) {
583 break;
585 return Vs.reduceLiteralT(as<bool>());
586 case ValueType::BT_Int: {
587 switch (ValType.Size) {
588 case ValueType::ST_8:
589 if (ValType.Signed)
590 return Vs.reduceLiteralT(as<int8_t>());
591 else
592 return Vs.reduceLiteralT(as<uint8_t>());
593 case ValueType::ST_16:
594 if (ValType.Signed)
595 return Vs.reduceLiteralT(as<int16_t>());
596 else
597 return Vs.reduceLiteralT(as<uint16_t>());
598 case ValueType::ST_32:
599 if (ValType.Signed)
600 return Vs.reduceLiteralT(as<int32_t>());
601 else
602 return Vs.reduceLiteralT(as<uint32_t>());
603 case ValueType::ST_64:
604 if (ValType.Signed)
605 return Vs.reduceLiteralT(as<int64_t>());
606 else
607 return Vs.reduceLiteralT(as<uint64_t>());
608 default:
609 break;
610 }
611 }
612 case ValueType::BT_Float: {
613 switch (ValType.Size) {
614 case ValueType::ST_32:
615 return Vs.reduceLiteralT(as<float>());
616 case ValueType::ST_64:
617 return Vs.reduceLiteralT(as<double>());
618 default:
619 break;
620 }
621 }
623 return Vs.reduceLiteralT(as<StringRef>());
625 return Vs.reduceLiteralT(as<void*>());
627 break;
628 }
629 return Vs.reduceLiteral(*this);
630}
631
632/// A Literal pointer to an object allocated in memory.
633/// At compile time, pointer literals are represented by symbolic names.
634class LiteralPtr : public SExpr {
635public:
636 LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {}
637 LiteralPtr(const LiteralPtr &) = default;
638
639 static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; }
640
641 // The clang declaration for the value that this pointer points to.
642 const ValueDecl *clangDecl() const { return Cvdecl; }
643 void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; }
644
645 template <class V>
646 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
647 return Vs.reduceLiteralPtr(*this);
648 }
649
650 template <class C>
651 typename C::CType compare(const LiteralPtr* E, C& Cmp) const {
652 if (!Cvdecl || !E->Cvdecl)
653 return Cmp.comparePointers(this, E);
654 return Cmp.comparePointers(Cvdecl, E->Cvdecl);
655 }
656
657private:
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 })))
664class Function : public SExpr {
665public:
667 : SExpr(COP_Function), VarDecl(Vd), Body(Bd) {
669 }
670
671 Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor
672 : SExpr(F), VarDecl(Vd), Body(Bd) {
674 }
675
676 static bool classof(const SExpr *E) { return E->opcode() == COP_Function; }
677
679 const Variable *variableDecl() const { return VarDecl; }
680
681 SExpr *body() { return Body; }
682 const SExpr *body() const { return Body; }
683
684 template <class V>
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>
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
707private:
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.
715class SFunction : public SExpr {
716public:
718 : SExpr(COP_SFunction), VarDecl(Vd), Body(B) {
719 assert(Vd->Definition == nullptr);
721 Vd->Definition = this;
722 }
723
724 SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor
725 : SExpr(F), VarDecl(Vd), Body(B) {
726 assert(Vd->Definition == nullptr);
728 Vd->Definition = this;
729 }
730
731 static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; }
732
734 const Variable *variableDecl() const { return VarDecl; }
735
736 SExpr *body() { return Body; }
737 const SExpr *body() const { return Body; }
738
739 template <class V>
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>
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
759private:
761 SExpr* Body;
762};
763
764/// A block of code -- e.g. the body of a function.
765class Code : public SExpr {
766public:
767 Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {}
768 Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor
769 : SExpr(C), ReturnType(T), Body(B) {}
770
771 static bool classof(const SExpr *E) { return E->opcode() == COP_Code; }
772
773 SExpr *returnType() { return ReturnType; }
774 const SExpr *returnType() const { return ReturnType; }
775
776 SExpr *body() { return Body; }
777 const SExpr *body() const { return Body; }
778
779 template <class V>
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>
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
794private:
795 SExpr* ReturnType;
796 SExpr* Body;
797};
798
799/// A typed, writable location in memory
800class Field : public SExpr {
801public:
802 Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {}
803 Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor
804 : SExpr(C), Range(R), Body(B) {}
805
806 static bool classof(const SExpr *E) { return E->opcode() == COP_Field; }
807
808 SExpr *range() { return Range; }
809 const SExpr *range() const { return Range; }
810
811 SExpr *body() { return Body; }
812 const SExpr *body() const { return Body; }
813
814 template <class V>
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>
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
829private:
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.
839class Apply : public SExpr {
840public:
841 Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {}
842 Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor
843 : SExpr(A), Fun(F), Arg(Ar) {}
844
845 static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; }
846
847 SExpr *fun() { return Fun; }
848 const SExpr *fun() const { return Fun; }
849
850 SExpr *arg() { return Arg; }
851 const SExpr *arg() const { return Arg; }
852
853 template <class V>
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>
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
868private:
869 SExpr* Fun;
870 SExpr* Arg;
871};
872
873/// Apply a self-argument to a self-applicable function.
874class SApply : public SExpr {
875public:
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
878 : SExpr(A), Sfun(Sf), Arg(Ar) {}
879
880 static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; }
881
882 SExpr *sfun() { return Sfun; }
883 const SExpr *sfun() const { return Sfun; }
884
885 SExpr *arg() { return Arg ? Arg : Sfun; }
886 const SExpr *arg() const { return Arg ? Arg : Sfun; }
887
888 bool isDelegation() const { return Arg != nullptr; }
889
890 template <class V>
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>
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
906private:
907 SExpr* Sfun;
908 SExpr* Arg;
909};
910
911/// Project a named slot from a C++ struct or class.
912class Project : public SExpr {
913public:
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
919 static bool classof(const SExpr *E) { return E->opcode() == COP_Project; }
920
921 SExpr *record() { return Rec; }
922 const SExpr *record() const { return Rec; }
923
924 const ValueDecl *clangDecl() const { return Cvdecl; }
925
926 bool isArrow() const { return (Flags & 0x01) != 0; }
927
928 void setArrow(bool b) {
929 if (b) Flags |= 0x01;
930 else Flags &= 0xFFFE;
931 }
932
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>
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>
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
958private:
959 SExpr* Rec;
960 mutable std::optional<std::string> SlotName;
961 const ValueDecl *Cvdecl;
962};
963
964/// Call a function (after all arguments have been applied).
965class Call : public SExpr {
966public:
967 Call(SExpr *T, const CallExpr *Ce = nullptr)
968 : SExpr(COP_Call), Target(T), Cexpr(Ce) {}
969 Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {}
970
971 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
972
973 SExpr *target() { return Target; }
974 const SExpr *target() const { return Target; }
975
976 const CallExpr *clangCallExpr() const { return Cexpr; }
977
978 template <class V>
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>
985 typename C::CType compare(const Call* E, C& Cmp) const {
986 return Cmp.compare(target(), E->target());
987 }
988
989private:
990 SExpr* Target;
991 const CallExpr *Cexpr;
992};
993
994/// Allocate memory for a new value on the heap or stack.
995class Alloc : public SExpr {
996public:
999 AK_Heap
1001
1002 Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; }
1003 Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); }
1004
1005 static bool classof(const SExpr *E) { return E->opcode() == COP_Call; }
1006
1007 AllocKind kind() const { return static_cast<AllocKind>(Flags); }
1008
1009 SExpr *dataType() { return Dtype; }
1010 const SExpr *dataType() const { return Dtype; }
1011
1012 template <class V>
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>
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
1026private:
1027 SExpr* Dtype;
1028};
1029
1030/// Load a value from memory.
1031class Load : public SExpr {
1032public:
1033 Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {}
1034 Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {}
1035
1036 static bool classof(const SExpr *E) { return E->opcode() == COP_Load; }
1037
1038 SExpr *pointer() { return Ptr; }
1039 const SExpr *pointer() const { return Ptr; }
1040
1041 template <class V>
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>
1048 typename C::CType compare(const Load* E, C& Cmp) const {
1049 return Cmp.compare(pointer(), E->pointer());
1050 }
1051
1052private:
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.
1058class Store : public SExpr {
1059public:
1060 Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {}
1061 Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {}
1062
1063 static bool classof(const SExpr *E) { return E->opcode() == COP_Store; }
1064
1065 SExpr *destination() { return Dest; } // Address to store to
1066 const SExpr *destination() const { return Dest; }
1067
1068 SExpr *source() { return Source; } // Value to store
1069 const SExpr *source() const { return Source; }
1070
1071 template <class V>
1072 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1073 auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx));
1074 auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx));
1075 return Vs.reduceStore(*this, Np, Nv);
1076 }
1077
1078 template <class C>
1079 typename C::CType compare(const Store* E, C& Cmp) const {
1080 typename C::CType Ct = Cmp.compare(destination(), E->destination());
1081 if (Cmp.notTrue(Ct))
1082 return Ct;
1083 return Cmp.compare(source(), E->source());
1084 }
1085
1086private:
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.
1093class ArrayIndex : public SExpr {
1094public:
1095 ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {}
1097 : SExpr(E), Array(A), Index(N) {}
1098
1099 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; }
1100
1101 SExpr *array() { return Array; }
1102 const SExpr *array() const { return Array; }
1103
1104 SExpr *index() { return Index; }
1105 const SExpr *index() const { return Index; }
1106
1107 template <class V>
1108 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1109 auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx));
1110 auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx));
1111 return Vs.reduceArrayIndex(*this, Na, Ni);
1112 }
1113
1114 template <class C>
1115 typename C::CType compare(const ArrayIndex* E, C& Cmp) const {
1116 typename C::CType Ct = Cmp.compare(array(), E->array());
1117 if (Cmp.notTrue(Ct))
1118 return Ct;
1119 return Cmp.compare(index(), E->index());
1120 }
1121
1122private:
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.
1130class ArrayAdd : public SExpr {
1131public:
1132 ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {}
1133 ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
1134 : SExpr(E), Array(A), Index(N) {}
1135
1136 static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; }
1137
1138 SExpr *array() { return Array; }
1139 const SExpr *array() const { return Array; }
1140
1141 SExpr *index() { return Index; }
1142 const SExpr *index() const { return Index; }
1143
1144 template <class V>
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>
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
1159private:
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.
1166class UnaryOp : public SExpr {
1167public:
1168 UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) {
1169 Flags = Op;
1170 }
1171
1172 UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; }
1173
1174 static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; }
1175
1177 return static_cast<TIL_UnaryOpcode>(Flags);
1178 }
1179
1180 SExpr *expr() { return Expr0; }
1181 const SExpr *expr() const { return Expr0; }
1182
1183 template <class V>
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>
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
1198private:
1199 SExpr* Expr0;
1200};
1201
1202/// Simple arithmetic binary operations, e.g. +, -, etc.
1203/// These operations have no side effects.
1204class BinaryOp : public SExpr {
1205public:
1207 : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) {
1208 Flags = Op;
1209 }
1210
1211 BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
1212 : SExpr(B), Expr0(E0), Expr1(E1) {
1213 Flags = B.Flags;
1214 }
1215
1216 static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; }
1217
1219 return static_cast<TIL_BinaryOpcode>(Flags);
1220 }
1221
1222 SExpr *expr0() { return Expr0; }
1223 const SExpr *expr0() const { return Expr0; }
1224
1225 SExpr *expr1() { return Expr1; }
1226 const SExpr *expr1() const { return Expr1; }
1227
1228 template <class V>
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>
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
1247private:
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.
1255class Cast : public SExpr {
1256public:
1257 Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; }
1258 Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; }
1259
1260 static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; }
1261
1263 return static_cast<TIL_CastOpcode>(Flags);
1264 }
1265
1266 SExpr *expr() { return Expr0; }
1267 const SExpr *expr() const { return Expr0; }
1268
1269 template <class V>
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>
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
1284private:
1285 SExpr* Expr0;
1286};
1287
1288class 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.
1293class Phi : public SExpr {
1294public:
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
1305
1306 Phi() : SExpr(COP_Phi) {}
1307 Phi(MemRegionRef A, unsigned Nvals) : SExpr(COP_Phi), Values(A, Nvals) {}
1308 Phi(const Phi &P, ValArray &&Vs) : SExpr(P), Values(std::move(Vs)) {}
1309
1310 static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; }
1311
1312 const ValArray &values() const { return Values; }
1313 ValArray &values() { return Values; }
1314
1315 Status status() const { return static_cast<Status>(Flags); }
1316 void setStatus(Status s) { Flags = s; }
1317
1318 /// Return the clang declaration of the variable for this Phi node, if any.
1319 const ValueDecl *clangDecl() const { return Cvdecl; }
1320
1321 /// Set the clang variable associated with this Phi node.
1322 void setClangDecl(const ValueDecl *Cvd) { Cvdecl = Cvd; }
1323
1324 template <class V>
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>
1335 typename C::CType compare(const Phi *E, C &Cmp) const {
1336 // TODO: implement CFG comparisons
1337 return Cmp.comparePointers(this, E);
1338 }
1339
1340private:
1341 ValArray Values;
1342 const ValueDecl* Cvdecl = nullptr;
1343};
1344
1345/// Base class for basic block terminators: Branch, Goto, and Return.
1346class Terminator : public SExpr {
1347protected:
1349 Terminator(const SExpr &E) : SExpr(E) {}
1350
1351public:
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.
1358
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.
1369class Goto : public Terminator {
1370public:
1371 Goto(BasicBlock *B, unsigned I)
1372 : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1373 Goto(const Goto &G, BasicBlock *B, unsigned I)
1374 : Terminator(COP_Goto), TargetBlock(B), Index(I) {}
1375
1376 static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; }
1377
1378 const BasicBlock *targetBlock() const { return TargetBlock; }
1379 BasicBlock *targetBlock() { return TargetBlock; }
1380
1381 /// Returns the index into the
1382 unsigned index() const { return Index; }
1383
1384 /// Return the list of basic blocks that this terminator can branch to.
1385 ArrayRef<BasicBlock *> successors() { return TargetBlock; }
1386
1387 template <class V>
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>
1394 typename C::CType compare(const Goto *E, C &Cmp) const {
1395 // TODO: implement CFG comparisons
1396 return Cmp.comparePointers(this, E);
1397 }
1398
1399private:
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.
1407class Branch : public Terminator {
1408public:
1410 : Terminator(COP_Branch), Condition(C) {
1411 Branches[0] = T;
1412 Branches[1] = E;
1413 }
1414
1416 : Terminator(Br), Condition(C) {
1417 Branches[0] = T;
1418 Branches[1] = E;
1419 }
1420
1421 static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; }
1422
1423 const SExpr *condition() const { return Condition; }
1424 SExpr *condition() { return Condition; }
1425
1426 const BasicBlock *thenBlock() const { return Branches[0]; }
1427 BasicBlock *thenBlock() { return Branches[0]; }
1428
1429 const BasicBlock *elseBlock() const { return Branches[1]; }
1430 BasicBlock *elseBlock() { return Branches[1]; }
1431
1432 /// Return the list of basic blocks that this terminator can branch to.
1434
1435 template <class V>
1436 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1437 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1438 BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]);
1439 BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]);
1440 return Vs.reduceBranch(*this, Nc, Ntb, Nte);
1441 }
1442
1443 template <class C>
1444 typename C::CType compare(const Branch *E, C &Cmp) const {
1445 // TODO: implement CFG comparisons
1446 return Cmp.comparePointers(this, E);
1447 }
1448
1449private:
1450 SExpr *Condition;
1451 BasicBlock *Branches[2];
1452};
1453
1454/// Return from the enclosing function, passing the return value to the caller.
1455/// Only the exit block should end with a return statement.
1456class Return : public Terminator {
1457public:
1458 Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {}
1459 Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {}
1460
1461 static bool classof(const SExpr *E) { return E->opcode() == COP_Return; }
1462
1463 /// Return an empty list.
1464 ArrayRef<BasicBlock *> successors() { return std::nullopt; }
1465
1466 SExpr *returnValue() { return Retval; }
1467 const SExpr *returnValue() const { return Retval; }
1468
1469 template <class V>
1470 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1471 auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx));
1472 return Vs.reduceReturn(*this, Ne);
1473 }
1474
1475 template <class C>
1476 typename C::CType compare(const Return *E, C &Cmp) const {
1477 return Cmp.compare(Retval, E->Retval);
1478 }
1479
1480private:
1481 SExpr* Retval;
1482};
1483
1485 switch (opcode()) {
1486 case COP_Goto: return cast<Goto>(this)->successors();
1487 case COP_Branch: return cast<Branch>(this)->successors();
1488 case COP_Return: return cast<Return>(this)->successors();
1489 default:
1490 return std::nullopt;
1491 }
1492}
1493
1494/// A basic block is part of an SCFG. It can be treated as a function in
1495/// continuation passing style. A block consists of a sequence of phi nodes,
1496/// which are "arguments" to the function, followed by a sequence of
1497/// instructions. It ends with a Terminator, which is a Branch or Goto to
1498/// another basic block in the same SCFG.
1499class BasicBlock : public SExpr {
1500public:
1503
1504 // TopologyNodes are used to overlay tree structures on top of the CFG,
1505 // such as dominator and postdominator trees. Each block is assigned an
1506 // ID in the tree according to a depth-first search. Tree traversals are
1507 // always up, towards the parents.
1509 int NodeID = 0;
1510
1511 // Includes this node, so must be > 1.
1513
1514 // Pointer to parent.
1515 BasicBlock *Parent = nullptr;
1516
1517 TopologyNode() = default;
1518
1519 bool isParentOf(const TopologyNode& OtherNode) {
1520 return OtherNode.NodeID > NodeID &&
1521 OtherNode.NodeID < NodeID + SizeOfSubTree;
1522 }
1523
1524 bool isParentOfOrEqual(const TopologyNode& OtherNode) {
1525 return OtherNode.NodeID >= NodeID &&
1526 OtherNode.NodeID < NodeID + SizeOfSubTree;
1527 }
1528 };
1529
1531 : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false) {}
1533 Terminator *T)
1534 : SExpr(COP_BasicBlock), Arena(A), BlockID(0), Visited(false),
1535 Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {}
1536
1537 static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; }
1538
1539 /// Returns the block ID. Every block has a unique ID in the CFG.
1540 int blockID() const { return BlockID; }
1541
1542 /// Returns the number of predecessors.
1543 size_t numPredecessors() const { return Predecessors.size(); }
1544 size_t numSuccessors() const { return successors().size(); }
1545
1546 const SCFG* cfg() const { return CFGPtr; }
1547 SCFG* cfg() { return CFGPtr; }
1548
1549 const BasicBlock *parent() const { return DominatorNode.Parent; }
1550 BasicBlock *parent() { return DominatorNode.Parent; }
1551
1552 const InstrArray &arguments() const { return Args; }
1553 InstrArray &arguments() { return Args; }
1554
1555 InstrArray &instructions() { return Instrs; }
1556 const InstrArray &instructions() const { return Instrs; }
1557
1558 /// Returns a list of predecessors.
1559 /// The order of predecessors in the list is important; each phi node has
1560 /// exactly one argument for each precessor, in the same order.
1561 BlockArray &predecessors() { return Predecessors; }
1562 const BlockArray &predecessors() const { return Predecessors; }
1563
1565 ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); }
1566
1567 const Terminator *terminator() const { return TermInstr; }
1568 Terminator *terminator() { return TermInstr; }
1569
1570 void setTerminator(Terminator *E) { TermInstr = E; }
1571
1572 bool Dominates(const BasicBlock &Other) {
1573 return DominatorNode.isParentOfOrEqual(Other.DominatorNode);
1574 }
1575
1576 bool PostDominates(const BasicBlock &Other) {
1577 return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode);
1578 }
1579
1580 /// Add a new argument.
1582 Args.reserveCheck(1, Arena);
1583 Args.push_back(V);
1584 }
1585
1586 /// Add a new instruction.
1588 Instrs.reserveCheck(1, Arena);
1589 Instrs.push_back(V);
1590 }
1591
1592 // Add a new predecessor, and return the phi-node index for it.
1593 // Will add an argument to all phi-nodes, initialized to nullptr.
1594 unsigned addPredecessor(BasicBlock *Pred);
1595
1596 // Reserve space for Nargs arguments.
1597 void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); }
1598
1599 // Reserve space for Nins instructions.
1600 void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); }
1601
1602 // Reserve space for NumPreds predecessors, including space in phi nodes.
1603 void reservePredecessors(unsigned NumPreds);
1604
1605 /// Return the index of BB, or Predecessors.size if BB is not a predecessor.
1606 unsigned findPredecessorIndex(const BasicBlock *BB) const {
1607 auto I = llvm::find(Predecessors, BB);
1608 return std::distance(Predecessors.cbegin(), I);
1609 }
1610
1611 template <class V>
1612 typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) {
1613 typename V::template Container<SExpr*> Nas(Vs, Args.size());
1614 typename V::template Container<SExpr*> Nis(Vs, Instrs.size());
1615
1616 // Entering the basic block should do any scope initialization.
1617 Vs.enterBasicBlock(*this);
1618
1619 for (const auto *E : Args) {
1620 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1621 Nas.push_back(Ne);
1622 }
1623 for (const auto *E : Instrs) {
1624 auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx));
1625 Nis.push_back(Ne);
1626 }
1627 auto Nt = Vs.traverse(TermInstr, Ctx);
1628
1629 // Exiting the basic block should handle any scope cleanup.
1630 Vs.exitBasicBlock(*this);
1631
1632 return Vs.reduceBasicBlock(*this, Nas, Nis, Nt);
1633 }
1634
1635 template <class C>
1636 typename C::CType compare(const BasicBlock *E, C &Cmp) const {
1637 // TODO: implement CFG comparisons
1638 return Cmp.comparePointers(this, E);
1639 }
1640
1641private:
1642 friend class SCFG;
1643
1644 // assign unique ids to all instructions
1645 unsigned renumberInstrs(unsigned id);
1646
1647 unsigned topologicalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
1648 unsigned topologicalFinalSort(SimpleArray<BasicBlock *> &Blocks, unsigned ID);
1649 void computeDominator();
1650 void computePostDominator();
1651
1652 // The arena used to allocate this block.
1653 MemRegionRef Arena;
1654
1655 // The CFG that contains this block.
1656 SCFG *CFGPtr = nullptr;
1657
1658 // Unique ID for this BB in the containing CFG. IDs are in topological order.
1659 unsigned BlockID : 31;
1660
1661 // Bit to determine if a block has been visited during a traversal.
1662 bool Visited : 1;
1663
1664 // Predecessor blocks in the CFG.
1665 BlockArray Predecessors;
1666
1667 // Phi nodes. One argument per predecessor.
1668 InstrArray Args;
1669
1670 // Instructions.
1671 InstrArray Instrs;
1672
1673 // Terminating instruction.
1674 Terminator *TermInstr = nullptr;
1675
1676 // The dominator tree.
1677 TopologyNode DominatorNode;
1678
1679 // The post-dominator tree.
1680 TopologyNode PostDominatorNode;
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.
1686class SCFG : public SExpr {
1687public:
1691
1692 SCFG(MemRegionRef A, unsigned Nblocks)
1693 : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks) {
1694 Entry = new (A) BasicBlock(A);
1695 Exit = new (A) BasicBlock(A);
1696 auto *V = new (A) Phi();
1697 Exit->addArgument(V);
1698 Exit->setTerminator(new (A) Return(V));
1699 add(Entry);
1700 add(Exit);
1701 }
1702
1703 SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba
1704 : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)) {
1705 // TODO: set entry and exit!
1706 }
1707
1708 static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; }
1709
1710 /// Return true if this CFG is valid.
1711 bool valid() const { return Entry && Exit && Blocks.size() > 0; }
1712
1713 /// Return true if this CFG has been normalized.
1714 /// After normalization, blocks are in topological order, and block and
1715 /// instruction IDs have been assigned.
1716 bool normal() const { return Normal; }
1717
1718 iterator begin() { return Blocks.begin(); }
1719 iterator end() { return Blocks.end(); }
1720
1721 const_iterator begin() const { return cbegin(); }
1722 const_iterator end() const { return cend(); }
1723
1724 const_iterator cbegin() const { return Blocks.cbegin(); }
1725 const_iterator cend() const { return Blocks.cend(); }
1726
1727 const BasicBlock *entry() const { return Entry; }
1728 BasicBlock *entry() { return Entry; }
1729 const BasicBlock *exit() const { return Exit; }
1730 BasicBlock *exit() { return Exit; }
1731
1732 /// Return the number of blocks in the CFG.
1733 /// Block::blockID() will return a number less than numBlocks();
1734 size_t numBlocks() const { return Blocks.size(); }
1735
1736 /// Return the total number of instructions in the CFG.
1737 /// This is useful for building instruction side-tables;
1738 /// A call to SExpr::id() will return a number less than numInstructions().
1739 unsigned numInstructions() { return NumInstructions; }
1740
1741 inline void add(BasicBlock *BB) {
1742 assert(BB->CFGPtr == nullptr);
1743 BB->CFGPtr = this;
1744 Blocks.reserveCheck(1, Arena);
1745 Blocks.push_back(BB);
1746 }
1747
1748 void setEntry(BasicBlock *BB) { Entry = BB; }
1749 void setExit(BasicBlock *BB) { Exit = BB; }
1750
1751 void computeNormalForm();
1752
1753 template <class V>
1754 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1755 Vs.enterCFG(*this);
1756 typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size());
1757
1758 for (const auto *B : Blocks) {
1759 Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) );
1760 }
1761 Vs.exitCFG(*this);
1762 return Vs.reduceSCFG(*this, Bbs);
1763 }
1764
1765 template <class C>
1766 typename C::CType compare(const SCFG *E, C &Cmp) const {
1767 // TODO: implement CFG comparisons
1768 return Cmp.comparePointers(this, E);
1769 }
1770
1771private:
1772 // assign unique ids to all instructions
1773 void renumberInstrs();
1774
1775 MemRegionRef Arena;
1776 BlockArray Blocks;
1777 BasicBlock *Entry = nullptr;
1778 BasicBlock *Exit = nullptr;
1779 unsigned NumInstructions = 0;
1780 bool Normal = false;
1781};
1782
1783/// An identifier, e.g. 'foo' or 'x'.
1784/// This is a pseduo-term; it will be lowered to a variable or projection.
1785class Identifier : public SExpr {
1786public:
1787 Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) {}
1788 Identifier(const Identifier &) = default;
1789
1790 static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; }
1791
1792 StringRef name() const { return Name; }
1793
1794 template <class V>
1795 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1796 return Vs.reduceIdentifier(*this);
1797 }
1798
1799 template <class C>
1800 typename C::CType compare(const Identifier* E, C& Cmp) const {
1801 return Cmp.compareStrings(name(), E->name());
1802 }
1803
1804private:
1805 StringRef Name;
1806};
1807
1808/// An if-then-else expression.
1809/// This is a pseduo-term; it will be lowered to a branch in a CFG.
1810class IfThenElse : public SExpr {
1811public:
1813 : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) {}
1815 : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) {}
1816
1817 static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; }
1818
1819 SExpr *condition() { return Condition; } // Address to store to
1820 const SExpr *condition() const { return Condition; }
1821
1822 SExpr *thenExpr() { return ThenExpr; } // Value to store
1823 const SExpr *thenExpr() const { return ThenExpr; }
1824
1825 SExpr *elseExpr() { return ElseExpr; } // Value to store
1826 const SExpr *elseExpr() const { return ElseExpr; }
1827
1828 template <class V>
1829 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1830 auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx));
1831 auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx));
1832 auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx));
1833 return Vs.reduceIfThenElse(*this, Nc, Nt, Ne);
1834 }
1835
1836 template <class C>
1837 typename C::CType compare(const IfThenElse* E, C& Cmp) const {
1838 typename C::CType Ct = Cmp.compare(condition(), E->condition());
1839 if (Cmp.notTrue(Ct))
1840 return Ct;
1841 Ct = Cmp.compare(thenExpr(), E->thenExpr());
1842 if (Cmp.notTrue(Ct))
1843 return Ct;
1844 return Cmp.compare(elseExpr(), E->elseExpr());
1845 }
1846
1847private:
1848 SExpr* Condition;
1849 SExpr* ThenExpr;
1850 SExpr* ElseExpr;
1851};
1852
1853/// A let-expression, e.g. let x=t; u.
1854/// This is a pseduo-term; it will be lowered to instructions in a CFG.
1855class Let : public SExpr {
1856public:
1857 Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) {
1859 }
1860
1861 Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) {
1863 }
1864
1865 static bool classof(const SExpr *E) { return E->opcode() == COP_Let; }
1866
1868 const Variable *variableDecl() const { return VarDecl; }
1869
1870 SExpr *body() { return Body; }
1871 const SExpr *body() const { return Body; }
1872
1873 template <class V>
1874 typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) {
1875 // This is a variable declaration, so traverse the definition.
1876 auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx));
1877 // Tell the rewriter to enter the scope of the let variable.
1878 Variable *Nvd = Vs.enterScope(*VarDecl, E0);
1879 auto E1 = Vs.traverse(Body, Ctx);
1880 Vs.exitScope(*VarDecl);
1881 return Vs.reduceLet(*this, Nvd, E1);
1882 }
1883
1884 template <class C>
1885 typename C::CType compare(const Let* E, C& Cmp) const {
1886 typename C::CType Ct =
1887 Cmp.compare(VarDecl->definition(), E->VarDecl->definition());
1888 if (Cmp.notTrue(Ct))
1889 return Ct;
1890 Cmp.enterScope(variableDecl(), E->variableDecl());
1891 Ct = Cmp.compare(body(), E->body());
1892 Cmp.leaveScope();
1893 return Ct;
1894 }
1895
1896private:
1898 SExpr* Body;
1899};
1900
1901const SExpr *getCanonicalVal(const SExpr *E);
1902SExpr* simplifyToCanonicalVal(SExpr *E);
1904
1905} // namespace til
1906} // namespace threadSafety
1907
1908} // namespace clang
1909
1910#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H
#define V(N, I)
Definition: ASTContext.h:3217
int Id
Definition: ASTDiff.cpp:190
StringRef P
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.
static std::string getName(const CallEvent &Call)
__device__ __2f16 b
__device__ __2f16 float bool s
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2812
bool isIdentifier() const
Predicate functions for querying what type of name this is.
This represents one expression.
Definition: Expr.h:110
StringRef getName() const
Get the name of identifier for this declaration as a StringRef.
Definition: Decl.h:274
DeclarationName getDeclName() const
Get the actual, stored name of the declaration, which may be a special name.
Definition: Decl.h:313
virtual void printName(raw_ostream &OS, const PrintingPolicy &Policy) const
Pretty-print the unqualified name of this declaration.
Definition: Decl.cpp:1637
Stmt - This represents one statement.
Definition: Stmt.h:72
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:701
Represents a variable declaration or definition.
Definition: Decl.h:913
@ Definition
This declaration is definitely a definition.
Definition: Decl.h:1258
Allocate memory for a new value on the heap or stack.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
Alloc(const Alloc &A, SExpr *Dt)
C::CType compare(const Alloc *E, C &Cmp) const
Alloc(SExpr *D, AllocKind K)
const SExpr * dataType() const
Apply an argument to a function.
Apply(const Apply &A, SExpr *F, SExpr *Ar)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
C::CType compare(const Apply *E, C &Cmp) const
Pointer arithmetic, restricted to arrays only.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N)
C::CType compare(const ArrayAdd *E, C &Cmp) const
static bool classof(const SExpr *E)
If p is a reference to an array, then p[i] is a reference to the i'th element of the array.
ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N)
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
C::CType compare(const ArrayIndex *E, C &Cmp) const
A basic block is part of an SCFG.
unsigned addPredecessor(BasicBlock *Pred)
BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, Terminator *T)
int blockID() const
Returns the block ID. Every block has a unique ID in the CFG.
const InstrArray & arguments() const
const InstrArray & instructions() const
bool Dominates(const BasicBlock &Other)
const Terminator * terminator() const
const BlockArray & predecessors() const
ArrayRef< BasicBlock * > successors() const
C::CType compare(const BasicBlock *E, C &Cmp) const
ArrayRef< BasicBlock * > successors()
void addArgument(Phi *V)
Add a new argument.
size_t numPredecessors() const
Returns the number of predecessors.
bool PostDominates(const BasicBlock &Other)
V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
void reservePredecessors(unsigned NumPreds)
unsigned findPredecessorIndex(const BasicBlock *BB) const
Return the index of BB, or Predecessors.size if BB is not a predecessor.
BlockArray & predecessors()
Returns a list of predecessors.
const BasicBlock * parent() const
void addInstruction(SExpr *V)
Add a new instruction.
Simple arithmetic binary operations, e.g.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1)
static bool classof(const SExpr *E)
BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1)
TIL_BinaryOpcode binaryOpcode() const
C::CType compare(const BinaryOp *E, C &Cmp) const
A conditional branch to two other blocks.
Branch(SExpr *C, BasicBlock *T, BasicBlock *E)
const BasicBlock * elseBlock() const
C::CType compare(const Branch *E, C &Cmp) const
Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E)
ArrayRef< BasicBlock * > successors()
Return the list of basic blocks that this terminator can branch to.
static bool classof(const SExpr *E)
const BasicBlock * thenBlock() const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Call a function (after all arguments have been applied).
const SExpr * target() const
Call(const Call &C, SExpr *T)
Call(SExpr *T, const CallExpr *Ce=nullptr)
C::CType compare(const Call *E, C &Cmp) const
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const CallExpr * clangCallExpr() const
C::CType compare(const Cast *E, C &Cmp) const
Cast(TIL_CastOpcode Op, SExpr *E)
static bool classof(const SExpr *E)
Cast(const Cast &C, SExpr *E)
TIL_CastOpcode castOpcode() const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
A block of code – e.g. the body of a function.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
const SExpr * returnType() const
C::CType compare(const Code *E, C &Cmp) const
const SExpr * body() const
Code(const Code &C, SExpr *T, SExpr *B)
A typed, writable location in memory.
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
C::CType compare(const Field *E, C &Cmp) const
Field(const Field &C, SExpr *R, SExpr *B)
Function(const Function &F, Variable *Vd, SExpr *Bd)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const Variable * variableDecl() const
C::CType compare(const Function *E, C &Cmp) const
static bool classof(const SExpr *E)
Function(Variable *Vd, SExpr *Bd)
Placeholder for an expression that has not yet been created.
C::CType compare(const Future *E, C &Cmp) const
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Jump to another basic block.
Goto(const Goto &G, BasicBlock *B, unsigned I)
C::CType compare(const Goto *E, C &Cmp) const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Goto(BasicBlock *B, unsigned I)
unsigned index() const
Returns the index into the.
static bool classof(const SExpr *E)
ArrayRef< BasicBlock * > successors()
Return the list of basic blocks that this terminator can branch to.
const BasicBlock * targetBlock() const
C::CType compare(const Identifier *E, C &Cmp) const
Identifier(const Identifier &)=default
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
An if-then-else expression.
IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
C::CType compare(const IfThenElse *E, C &Cmp) const
static bool classof(const SExpr *E)
IfThenElse(SExpr *C, SExpr *T, SExpr *E)
A let-expression, e.g.
Let(const Let &L, Variable *Vd, SExpr *Bd)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const Variable * variableDecl() const
C::CType compare(const Let *E, C &Cmp) const
Let(Variable *Vd, SExpr *Bd)
static bool classof(const SExpr *E)
const SExpr * body() const
A Literal pointer to an object allocated in memory.
const ValueDecl * clangDecl() const
C::CType compare(const LiteralPtr *E, C &Cmp) const
LiteralPtr(const LiteralPtr &)=default
void setClangDecl(const ValueDecl *VD)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
LiteralT(const LiteralT< T > &L)
Literal(const Literal &)=default
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const LiteralT< T > & as() const
C::CType compare(const Literal *E, C &Cmp) const
Load a value from memory.
const SExpr * pointer() const
C::CType compare(const Load *E, C &Cmp) const
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Load(const Load &L, SExpr *P)
Phi Node, for code in SSA form.
SimpleArray< SExpr * > ValArray
static bool classof(const SExpr *E)
C::CType compare(const Phi *E, C &Cmp) const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const ValueDecl * clangDecl() const
Return the clang declaration of the variable for this Phi node, if any.
void setClangDecl(const ValueDecl *Cvd)
Set the clang variable associated with this Phi node.
Phi(MemRegionRef A, unsigned Nvals)
Phi(const Phi &P, ValArray &&Vs)
const ValArray & values() const
Project a named slot from a C++ struct or class.
const ValueDecl * clangDecl() const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
C::CType compare(const Project *E, C &Cmp) const
Project(SExpr *R, const ValueDecl *Cvd)
Return from the enclosing function, passing the return value to the caller.
Return(const Return &R, SExpr *Rval)
const SExpr * returnValue() const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
ArrayRef< BasicBlock * > successors()
Return an empty list.
static bool classof(const SExpr *E)
C::CType compare(const Return *E, C &Cmp) const
Apply a self-argument to a self-applicable function.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
SApply(SExpr *Sf, SExpr *A=nullptr)
C::CType compare(const SApply *E, C &Cmp) const
SApply(SApply &A, SExpr *Sf, SExpr *Ar=nullptr)
static bool classof(const SExpr *E)
An SCFG is a control-flow graph.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const BasicBlock * entry() const
C::CType compare(const SCFG *E, C &Cmp) const
bool normal() const
Return true if this CFG has been normalized.
static bool classof(const SExpr *E)
const_iterator begin() const
const_iterator end() const
const_iterator cend() const
const BasicBlock * exit() const
const_iterator cbegin() const
unsigned numInstructions()
Return the total number of instructions in the CFG.
size_t numBlocks() const
Return the number of blocks in the CFG.
bool valid() const
Return true if this CFG is valid.
SimpleArray< BasicBlock * > BlockArray
Base class for AST nodes in the typed intermediate language.
BasicBlock * block() const
Returns the block, if this is an instruction in a basic block, otherwise returns null.
void setID(BasicBlock *B, unsigned id)
Set the basic block and instruction ID for this expression.
unsigned id() const
Returns the instruction ID for this expression.
A self-applicable function.
static bool classof(const SExpr *E)
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
SFunction(Variable *Vd, SExpr *B)
SFunction(const SFunction &F, Variable *Vd, SExpr *B)
const Variable * variableDecl() const
C::CType compare(const SFunction *E, C &Cmp) const
void reserve(size_t Ncp, MemRegionRef A)
void reserveCheck(size_t N, MemRegionRef A)
Store a value to memory.
C::CType compare(const Store *E, C &Cmp) const
const SExpr * destination() const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
Store(const Store &S, SExpr *P, SExpr *V)
static bool classof(const SExpr *E)
Base class for basic block terminators: Branch, Goto, and Return.
ArrayRef< BasicBlock * > successors() const
static bool classof(const SExpr *E)
ArrayRef< BasicBlock * > successors()
Return the list of basic blocks that this terminator can branch to.
Simple arithmetic unary operations, e.g.
static bool classof(const SExpr *E)
UnaryOp(const UnaryOp &U, SExpr *E)
TIL_UnaryOpcode unaryOpcode() const
C::CType compare(const UnaryOp *E, C &Cmp) const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
UnaryOp(TIL_UnaryOpcode Op, SExpr *E)
Placeholder for expressions that cannot be represented in the TIL.
C::CType compare(const Undefined *E, C &Cmp) const
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
Variable(SExpr *D, const ValueDecl *Cvd=nullptr)
Variable(const Variable &Vd, SExpr *D)
C::CType compare(const Variable *E, C &Cmp) const
StringRef name() const
Return the name of the variable, if any.
static bool classof(const SExpr *E)
Variable(StringRef s, SExpr *D=nullptr)
SExpr * definition()
Return the definition of the variable.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
const ValueDecl * clangDecl() const
Return the clang declaration for this variable, if any.
void setClangDecl(const ValueDecl *VD)
@ VK_SFun
SFunction (self) parameter.
VariableKind kind() const
Return the kind of variable (let, function param, or self)
Placeholder for a wildcard that matches any other expression.
V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx)
static bool classof(const SExpr *E)
C::CType compare(const Wildcard *E, C &Cmp) const
Wildcard(const Wildcard &)=default
TIL_UnaryOpcode
Opcode for unary arithmetic operations.
const TIL_Opcode COP_Min
void simplifyIncompleteArg(til::Phi *Ph)
const TIL_Opcode COP_Max
const TIL_BinaryOpcode BOP_Min
const TIL_UnaryOpcode UOP_Min
StringRef getBinaryOpcodeString(TIL_BinaryOpcode Op)
Return the name of a binary opcode.
StringRef getUnaryOpcodeString(TIL_UnaryOpcode Op)
Return the name of a unary opcode.
TIL_CastOpcode
Opcode for cast operations.
const TIL_CastOpcode CAST_Max
TIL_BinaryOpcode
Opcode for binary arithmetic operations.
SExpr * simplifyToCanonicalVal(SExpr *E)
const TIL_BinaryOpcode BOP_Max
const TIL_CastOpcode CAST_Min
const TIL_UnaryOpcode UOP_Max
const SExpr * getCanonicalVal(const SExpr *E)
TIL_Opcode
Enum for the different distinct classes of SExpr.
@ C
Languages that the frontend can parse and compile.
Definition: Format.h:4657
__SIZE_TYPE__ size_t
The unsigned integer type of the result of the sizeof operator.
#define false
Definition: stdbool.h:22
bool isParentOf(const TopologyNode &OtherNode)
bool isParentOfOrEqual(const TopologyNode &OtherNode)
ValueTypes are data types that can actually be held in registers.
ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS)
static SizeType getSizeType(unsigned nbytes)