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