16bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines//===- ThreadSafetyTIL.h ---------------------------------------*- C++ --*-===// 26bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 36bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// The LLVM Compiler Infrastructure 46bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 56bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// This file is distributed under the University of Illinois Open Source 66bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// License. See LICENSE.TXT in the llvm repository for details. 76bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 86bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines//===----------------------------------------------------------------------===// 96bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// This file defines a simple Typed Intermediate Language, or TIL, that is used 116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// by the thread safety analysis (See ThreadSafety.cpp). The TIL is intended 126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// to be largely independent of clang, in the hope that the analysis can be 136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// reused for other non-C++ languages. All dependencies on clang/llvm should 146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// go in ThreadSafetyUtil.h. 156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Thread safety analysis works by comparing mutex expressions, e.g. 176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// class A { Mutex mu; int dat GUARDED_BY(this->mu); } 196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// class B { A a; } 206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// void foo(B* b) { 226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// (*b).a.mu.lock(); // locks (*b).a.mu 236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// b->a.dat = 0; // substitute &b->a for 'this'; 246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// // requires lock on (&b->a)->mu 256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// (b->a.mu).unlock(); // unlocks (b->a.mu) 266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// } 276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// As illustrated by the above example, clang Exprs are not well-suited to 296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// represent mutex expressions directly, since there is no easy way to compare 306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Exprs for equivalence. The thread safety analysis thus lowers clang Exprs 316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// into a simple intermediate language (IL). The IL supports: 326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// (1) comparisons for semantic equality of expressions 346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// (2) SSA renaming of variables 356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// (3) wildcards and pattern matching over expressions 366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// (4) hash-based expression lookup 376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// The TIL is currently very experimental, is intended only for use within 396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// the thread safety analysis, and is subject to change without notice. 406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// After the API stabilizes and matures, it may be appropriate to make this 416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// more generally available to other analyses. 426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// UNDER CONSTRUCTION. USE AT YOUR OWN RISK. 446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// 456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines//===----------------------------------------------------------------------===// 466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 47176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H 48176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYTIL_H 496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// All clang include dependencies for this file must be put in 516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// ThreadSafetyUtil.h. 526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "ThreadSafetyUtil.h" 53c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines#include <algorithm> 546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include <cassert> 556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include <cstddef> 560e2c34f92f00628d48968dfea096d36381f494cbStephen Hines#include <stdint.h> 576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include <utility> 586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace clang { 616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace threadSafety { 626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace til { 636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 65176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Enum for the different distinct classes of SExpr 666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesenum TIL_Opcode { 676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#define TIL_OPCODE_DEF(X) COP_##X, 686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#include "ThreadSafetyOps.def" 696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#undef TIL_OPCODE_DEF 706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 72176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Opcode for unary arithmetic operations. 736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesenum TIL_UnaryOpcode : unsigned char { 746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines UOP_Minus, // - 756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines UOP_BitNot, // ~ 766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines UOP_LogicNot // ! 776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 79176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Opcode for binary arithmetic operations. 806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesenum TIL_BinaryOpcode : unsigned char { 81176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BOP_Add, // + 82176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BOP_Sub, // - 836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Mul, // * 846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Div, // / 856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Rem, // % 866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Shl, // << 876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Shr, // >> 886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_BitAnd, // & 896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_BitXor, // ^ 906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_BitOr, // | 916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Eq, // == 926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Neq, // != 936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Lt, // < 946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BOP_Leq, // <= 95176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BOP_LogicAnd, // && (no short-circuit) 96176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BOP_LogicOr // || (no short-circuit) 976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 99176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Opcode for cast operations. 1006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesenum TIL_CastOpcode : unsigned char { 1016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CAST_none = 0, 1026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CAST_extendNum, // extend precision of numeric type 1036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CAST_truncNum, // truncate precision of numeric type 1046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CAST_toFloat, // convert to floating point type 1056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CAST_toInt, // convert to integer type 106176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines CAST_objToPtr // convert smart pointer to pointer (C++ only) 1076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 1086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst TIL_Opcode COP_Min = COP_Future; 1106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst TIL_Opcode COP_Max = COP_Branch; 1116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst TIL_UnaryOpcode UOP_Min = UOP_Minus; 1126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst TIL_UnaryOpcode UOP_Max = UOP_LogicNot; 113176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesconst TIL_BinaryOpcode BOP_Min = BOP_Add; 1146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst TIL_BinaryOpcode BOP_Max = BOP_LogicOr; 1156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst TIL_CastOpcode CAST_Min = CAST_none; 1166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesconst TIL_CastOpcode CAST_Max = CAST_toInt; 1176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 118176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Return the name of a unary opcode. 1196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen HinesStringRef getUnaryOpcodeString(TIL_UnaryOpcode Op); 120176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 121176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Return the name of a binary opcode. 1226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen HinesStringRef getBinaryOpcodeString(TIL_BinaryOpcode Op); 1236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 125176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// ValueTypes are data types that can actually be held in registers. 126176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// All variables and expressions must have a value type. 127176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Pointer types are further subdivided into the various heap-allocated 128176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// types, such as functions, records, etc. 129176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Structured types that are passed by value (e.g. complex numbers) 130176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// require special handling; they use BT_ValueRef, and size ST_0. 1316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesstruct ValueType { 1326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines enum BaseType : unsigned char { 1336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BT_Void = 0, 1346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BT_Bool, 1356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BT_Int, 1366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BT_Float, 1376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BT_String, // String literals 1386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BT_Pointer, 1396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BT_ValueRef 1406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines }; 1416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines enum SizeType : unsigned char { 1436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ST_0 = 0, 1446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ST_1, 1456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ST_8, 1466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ST_16, 1476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ST_32, 1486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ST_64, 1496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ST_128 1506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines }; 1516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines inline static SizeType getSizeType(unsigned nbytes); 1536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines template <class T> 1556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines inline static ValueType getValueType(); 1566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ValueType(BaseType B, SizeType Sz, bool S, unsigned char VS) 1586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : Base(B), Size(Sz), Signed(S), VectSize(VS) 1596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines { } 1606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BaseType Base; 1626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SizeType Size; 1636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines bool Signed; 1646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines unsigned char VectSize; // 0 for scalar, otherwise num elements in vector 1656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 1666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType::SizeType ValueType::getSizeType(unsigned nbytes) { 1696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines switch (nbytes) { 1706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case 1: return ST_8; 1716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case 2: return ST_16; 1726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case 4: return ST_32; 1736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case 8: return ST_64; 1746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case 16: return ST_128; 1756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines default: return ST_0; 1766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 1786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 1816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<void>() { 1826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Void, ST_0, false, 0); 1836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 1846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 1866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<bool>() { 1876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Bool, ST_1, false, 0); 1886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 1896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 1916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<int8_t>() { 1926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Int, ST_8, true, 0); 1936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 1946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 1966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<uint8_t>() { 1976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Int, ST_8, false, 0); 1986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 1996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<int16_t>() { 2026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Int, ST_16, true, 0); 2036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<uint16_t>() { 2076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Int, ST_16, false, 0); 2086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<int32_t>() { 2126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Int, ST_32, true, 0); 2136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<uint32_t>() { 2176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Int, ST_32, false, 0); 2186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<int64_t>() { 2226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Int, ST_64, true, 0); 2236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<uint64_t>() { 2276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Int, ST_64, false, 0); 2286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<float>() { 2326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Float, ST_32, true, 0); 2336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<double>() { 2376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Float, ST_64, true, 0); 2386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<long double>() { 2426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Float, ST_128, true, 0); 2436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<StringRef>() { 247c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return ValueType(BT_String, getSizeType(sizeof(StringRef)), false, 0); 2486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<> 2516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesinline ValueType ValueType::getValueType<void*>() { 2526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ValueType(BT_Pointer, getSizeType(sizeof(void*)), false, 0); 2536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 2546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 256176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesclass BasicBlock; 257176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 2586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 259176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Base class for AST nodes in the typed intermediate language. 2606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass SExpr { 2616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 2626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } 2636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 2646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Subclasses of SExpr must define the following: 2656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // 2666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // This(const This& E, ...) { 2676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // copy constructor: construct copy of E, with some additional arguments. 2686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // } 2696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // 270c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // template <class V> 271c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 272c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // traverse all subexpressions, following the traversal/rewriter interface. 2736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // } 2746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // 2756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // template <class C> typename C::CType compare(CType* E, C& Cmp) { 2766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // compare all subexpressions, following the comparator interface 2776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // } 2786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void *operator new(size_t S, MemRegionRef &R) { 2796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return ::operator new(S, R); 2806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 2816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 282176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// SExpr objects cannot be deleted. 2836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // This declaration is public to workaround a gcc bug that breaks building 2846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // with REQUIRES_EH=1. 2850e2c34f92f00628d48968dfea096d36381f494cbStephen Hines void operator delete(void *) = delete; 2866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 287176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Returns the instruction ID for this expression. 288176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// All basic block instructions have a unique ID (i.e. virtual register). 289176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines unsigned id() const { return SExprID; } 290176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 291176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Returns the block, if this is an instruction in a basic block, 292176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// otherwise returns null. 293176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock* block() const { return Block; } 294176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 295176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Set the basic block and instruction ID for this expression. 296176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void setID(BasicBlock *B, unsigned id) { Block = B; SExprID = id; } 297176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 2986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprotected: 299176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr(TIL_Opcode Op) 300176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : Opcode(Op), Reserved(0), Flags(0), SExprID(0), Block(nullptr) {} 301176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr(const SExpr &E) 302176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : Opcode(E.Opcode), Reserved(0), Flags(E.Flags), SExprID(0), 303176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Block(nullptr) {} 3046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const unsigned char Opcode; 3066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines unsigned char Reserved; 3076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines unsigned short Flags; 308176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines unsigned SExprID; 309176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock* Block; 3106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 3120e2c34f92f00628d48968dfea096d36381f494cbStephen Hines SExpr() = delete; 3136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 314176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// SExpr objects must be created in an arena. 3150e2c34f92f00628d48968dfea096d36381f494cbStephen Hines void *operator new(size_t) = delete; 3166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 3176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Contains various helper functions for SExprs. 3206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesnamespace ThreadSafetyTIL { 3216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines inline bool isTrivial(const SExpr *E) { 3226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines unsigned Op = E->opcode(); 3236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; 3246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} 3266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Nodes which declare variables 3286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Function; 3296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass SFunction; 3306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Let; 3316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 333176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A named variable, e.g. "x". 334176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// 335176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// There are two distinct places in which a Variable can appear in the AST. 336176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A variable declaration introduces a new variable, and can occur in 3 places: 337176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Let-expressions: (Let (x = t) u) 338176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Functions: (Function (x : t) u) 339176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Self-applicable functions (SFunction (x) t) 340176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// 341176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// If a variable occurs in any other location, it is a reference to an existing 342176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// variable declaration -- e.g. 'x' in (x * y + z). To save space, we don't 343176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// allocate a separate AST node for variable references; a reference is just a 344176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// pointer to the original declaration. 3456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Variable : public SExpr { 3466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 3476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Variable; } 3486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 3496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines enum VariableKind { 350176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines VK_Let, ///< Let-variable 351176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines VK_Fun, ///< Function parameter 352176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines VK_SFun ///< SFunction (self) parameter 3536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines }; 3546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 355176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Variable(StringRef s, SExpr *D = nullptr) 356176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : SExpr(COP_Variable), Name(s), Definition(D), Cvdecl(nullptr) { 357176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Flags = VK_Let; 358176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 359176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Variable(SExpr *D, const clang::ValueDecl *Cvd = nullptr) 360176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : SExpr(COP_Variable), Name(Cvd ? Cvd->getName() : "_x"), 361176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Definition(D), Cvdecl(Cvd) { 362176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Flags = VK_Let; 363176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 364176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Variable(const Variable &Vd, SExpr *D) // rewrite constructor 365176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : SExpr(Vd), Name(Vd.Name), Definition(D), Cvdecl(Vd.Cvdecl) { 366176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Flags = Vd.kind(); 367176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 3686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 369176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the kind of variable (let, function param, or self) 3706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines VariableKind kind() const { return static_cast<VariableKind>(Flags); } 3716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 372176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the name of the variable, if any. 373176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines StringRef name() const { return Name; } 3746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 375176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the clang declaration for this variable, if any. 376176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const clang::ValueDecl *clangDecl() const { return Cvdecl; } 3776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 378176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the definition of the variable. 379176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// For let-vars, this is the setting expression. 380176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// For function and self parameters, it is the type of the variable. 381176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *definition() { return Definition; } 382176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *definition() const { return Definition; } 3836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 384176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void setName(StringRef S) { Name = S; } 3856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines void setKind(VariableKind K) { Flags = K; } 386176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void setDefinition(SExpr *E) { Definition = E; } 387176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void setClangDecl(const clang::ValueDecl *VD) { Cvdecl = VD; } 3886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 389c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 390c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 3916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // This routine is only called for variable references. 392c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceVariableRef(this); 3936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 395176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 396176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Variable* E, C& Cmp) const { 3976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compareVariableRefs(this, E); 3986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 3996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 4016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines friend class Function; 4026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines friend class SFunction; 4036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines friend class BasicBlock; 4046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines friend class Let; 4056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines StringRef Name; // The name of the variable. 407176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Definition; // The TIL type or definition 4086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const clang::ValueDecl *Cvdecl; // The clang declaration for this variable. 4096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 4106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 412176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Placeholder for an expression that has not yet been created. 413176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Used to implement lazy copy and rewriting strategies. 4146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Future : public SExpr { 4156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 4166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Future; } 4176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines enum FutureStatus { 4196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines FS_pending, 4206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines FS_evaluating, 4216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines FS_done 4226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines }; 4236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 424176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Future() : SExpr(COP_Future), Status(FS_pending), Result(nullptr) {} 425176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 4266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 4270e2c34f92f00628d48968dfea096d36381f494cbStephen Hines virtual ~Future() = delete; 4286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 429176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinespublic: 4306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // A lazy rewriting strategy should subclass Future and override this method. 431176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines virtual SExpr *compute() { return nullptr; } 4326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Return the result of this future if it exists, otherwise return null. 434176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *maybeGetResult() const { 4356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Result; 4366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 4376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Return the result of this future; forcing it if necessary. 4396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SExpr *result() { 4406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines switch (Status) { 4416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case FS_pending: 442176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return force(); 4436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case FS_evaluating: 4446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; // infinite loop; illegal recursion. 4456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines case FS_done: 4466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Result; 4476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 4486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 4496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 450c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 451c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 4526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(Result && "Cannot traverse Future that has not been forced."); 453c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.traverse(Result, Ctx); 4546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 4556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 456176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 457176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Future* E, C& Cmp) const { 4586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (!Result || !E->Result) 4596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.comparePointers(this, E); 4606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(Result, E->Result); 4616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 4626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 464176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* force(); 4656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines FutureStatus Status; 4676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SExpr *Result; 4686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 4696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 471176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Placeholder for expressions that cannot be represented in the TIL. 4726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Undefined : public SExpr { 4736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 4746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } 4756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Undefined(const clang::Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} 4776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} 4786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 479c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 480c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 481c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceUndefined(*this); 4826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 4836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 484176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 485176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Undefined* E, C& Cmp) const { 486176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Cmp.trueResult(); 4876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 4886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 4906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const clang::Stmt *Cstmt; 4916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 4926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 494176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Placeholder for a wildcard that matches any other expression. 4956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Wildcard : public SExpr { 4966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 4976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Wildcard; } 4986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 4996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Wildcard() : SExpr(COP_Wildcard) {} 5006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Wildcard(const Wildcard &W) : SExpr(W) {} 5016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 502c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 503c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceWildcard(*this); 5046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 5056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 506176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 507176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Wildcard* E, C& Cmp) const { 5086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.trueResult(); 5096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 5106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 5116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 513c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinestemplate <class T> class LiteralT; 514c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 5156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Base class for literal values. 5166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Literal : public SExpr { 5176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 5186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Literal; } 5196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Literal(const clang::Expr *C) 521c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines : SExpr(COP_Literal), ValType(ValueType::getValueType<void>()), Cexpr(C) 5226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines { } 523c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Literal(ValueType VT) : SExpr(COP_Literal), ValType(VT), Cexpr(nullptr) {} 5246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Literal(const Literal &L) : SExpr(L), ValType(L.ValType), Cexpr(L.Cexpr) {} 5256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // The clang expression for this literal. 5276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const clang::Expr *clangExpr() const { return Cexpr; } 5286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ValueType valueType() const { return ValType; } 5306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 531c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template<class T> const LiteralT<T>& as() const { 532c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return *static_cast<const LiteralT<T>*>(this); 533c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 534c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template<class T> LiteralT<T>& as() { 535c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return *static_cast<LiteralT<T>*>(this); 5366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 5376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 538c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx); 539c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 540176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 541176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Literal* E, C& Cmp) const { 542176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // TODO: defer actual comparison to LiteralT 543176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Cmp.trueResult(); 5446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 5456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 5476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const ValueType ValType; 5486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const clang::Expr *Cexpr; 5496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 5506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines// Derived class for literal values, which stores the actual value. 5536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinestemplate<class T> 5546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass LiteralT : public Literal { 5556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 5566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) { } 5576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) { } 5586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines T value() const { return Val;} 5606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines T& value() { return Val; } 5616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 5636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines T Val; 5646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 5656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 5666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 567c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 568c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinestemplate <class V> 569c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinestypename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { 570c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines if (Cexpr) 571c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteral(*this); 572c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 573c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines switch (ValType.Base) { 574c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::BT_Void: 575c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines break; 576c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::BT_Bool: 577c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<bool>()); 578c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::BT_Int: { 579c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines switch (ValType.Size) { 580c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::ST_8: 581c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines if (ValType.Signed) 582c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<int8_t>()); 583c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines else 584c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<uint8_t>()); 585c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::ST_16: 586c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines if (ValType.Signed) 587c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<int16_t>()); 588c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines else 589c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<uint16_t>()); 590c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::ST_32: 591c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines if (ValType.Signed) 592c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<int32_t>()); 593c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines else 594c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<uint32_t>()); 595c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::ST_64: 596c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines if (ValType.Signed) 597c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<int64_t>()); 598c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines else 599c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<uint64_t>()); 600c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines default: 601c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines break; 602c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 603c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 604c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::BT_Float: { 605c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines switch (ValType.Size) { 606c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::ST_32: 607c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<float>()); 608c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::ST_64: 609c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<double>()); 610c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines default: 611c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines break; 612c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 613c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 614c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::BT_String: 615c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<StringRef>()); 616c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::BT_Pointer: 617c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralT(as<void*>()); 618c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines case ValueType::BT_ValueRef: 619c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines break; 620c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 621c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteral(*this); 622c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines} 623c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 624c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 625176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A Literal pointer to an object allocated in memory. 626176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// At compile time, pointer literals are represented by symbolic names. 6276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass LiteralPtr : public SExpr { 6286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 6296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } 6306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 6316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LiteralPtr(const clang::ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} 6326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines LiteralPtr(const LiteralPtr &R) : SExpr(R), Cvdecl(R.Cvdecl) {} 6336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 6346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // The clang declaration for the value that this pointer points to. 6356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const clang::ValueDecl *clangDecl() const { return Cvdecl; } 6366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 637c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 638c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 639c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLiteralPtr(*this); 6406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 6416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 642176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 643176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const LiteralPtr* E, C& Cmp) const { 6446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.comparePointers(Cvdecl, E->Cvdecl); 6456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 6466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 6476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 6486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const clang::ValueDecl *Cvdecl; 6496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 6506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 6516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 652176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A function -- a.k.a. lambda abstraction. 653176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Functions with multiple arguments are created by currying, 654176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// e.g. (Function (x: Int) (Function (y: Int) (Code { return x + y }))) 6556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Function : public SExpr { 6566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 6576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Function; } 6586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 6596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Function(Variable *Vd, SExpr *Bd) 6606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(COP_Function), VarDecl(Vd), Body(Bd) { 6616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Vd->setKind(Variable::VK_Fun); 6626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 6636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Function(const Function &F, Variable *Vd, SExpr *Bd) // rewrite constructor 6646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(F), VarDecl(Vd), Body(Bd) { 6656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Vd->setKind(Variable::VK_Fun); 6666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 6676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 6686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Variable *variableDecl() { return VarDecl; } 6696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const Variable *variableDecl() const { return VarDecl; } 6706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 671176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *body() { return Body; } 672176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *body() const { return Body; } 6736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 674c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 675c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 6766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // This is a variable declaration, so traverse the definition. 677c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto E0 = Vs.traverse(VarDecl->Definition, Vs.typeCtx(Ctx)); 6786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Tell the rewriter to enter the scope of the function. 679c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Variable *Nvd = Vs.enterScope(*VarDecl, E0); 680c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 681c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Vs.exitScope(*VarDecl); 682c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceFunction(*this, Nvd, E1); 6836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 6846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 685176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 686176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Function* E, C& Cmp) const { 6876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = 6886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 6896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 6906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 6916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.enterScope(variableDecl(), E->variableDecl()); 6926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Ct = Cmp.compare(body(), E->body()); 6936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.leaveScope(); 6946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 6956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 6966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 6976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 6986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Variable *VarDecl; 699176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Body; 7006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 7016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 703176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A self-applicable function. 704176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A self-applicable function can be applied to itself. It's useful for 705176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// implementing objects and late binding. 7066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass SFunction : public SExpr { 7076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 7086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_SFunction; } 7096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SFunction(Variable *Vd, SExpr *B) 7116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(COP_SFunction), VarDecl(Vd), Body(B) { 7126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(Vd->Definition == nullptr); 7136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Vd->setKind(Variable::VK_SFun); 714176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Vd->Definition = this; 7156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 7166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SFunction(const SFunction &F, Variable *Vd, SExpr *B) // rewrite constructor 7176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(F), VarDecl(Vd), Body(B) { 7186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(Vd->Definition == nullptr); 7196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Vd->setKind(Variable::VK_SFun); 720176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Vd->Definition = this; 7216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 7226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Variable *variableDecl() { return VarDecl; } 7246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const Variable *variableDecl() const { return VarDecl; } 7256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 726176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *body() { return Body; } 727176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *body() const { return Body; } 7286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 729c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 730c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 7316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // A self-variable points to the SFunction itself. 7326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // A rewrite must introduce the variable with a null definition, and update 7336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // it after 'this' has been rewritten. 734c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Variable *Nvd = Vs.enterScope(*VarDecl, nullptr); 735c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto E1 = Vs.traverse(Body, Vs.declCtx(Ctx)); 736c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Vs.exitScope(*VarDecl); 7376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // A rewrite operation will call SFun constructor to set Vvd->Definition. 738c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceSFunction(*this, Nvd, E1); 7396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 7406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 741176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 742176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const SFunction* E, C& Cmp) const { 7436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.enterScope(variableDecl(), E->variableDecl()); 7446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(body(), E->body()); 7456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.leaveScope(); 7466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 7476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 7486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 7506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Variable *VarDecl; 751176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Body; 7526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 7536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 755176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A block of code -- e.g. the body of a function. 7566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Code : public SExpr { 7576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 7586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Code; } 7596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Code(SExpr *T, SExpr *B) : SExpr(COP_Code), ReturnType(T), Body(B) {} 7616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Code(const Code &C, SExpr *T, SExpr *B) // rewrite constructor 7626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(C), ReturnType(T), Body(B) {} 7636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 764176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *returnType() { return ReturnType; } 765176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *returnType() const { return ReturnType; } 7666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 767176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *body() { return Body; } 768176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *body() const { return Body; } 7696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 770c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 771c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 772c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nt = Vs.traverse(ReturnType, Vs.typeCtx(Ctx)); 773c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 774c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceCode(*this, Nt, Nb); 7756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 7766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 777176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 778176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Code* E, C& Cmp) const { 7796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(returnType(), E->returnType()); 7806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 7816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 7826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(body(), E->body()); 7836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 7846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 786176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* ReturnType; 787176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Body; 7886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 7896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 791176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A typed, writable location in memory 7926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Field : public SExpr { 7936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 7946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Field; } 7956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 7966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Field(SExpr *R, SExpr *B) : SExpr(COP_Field), Range(R), Body(B) {} 7976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Field(const Field &C, SExpr *R, SExpr *B) // rewrite constructor 7986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(C), Range(R), Body(B) {} 7996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 800176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *range() { return Range; } 801176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *range() const { return Range; } 8026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 803176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *body() { return Body; } 804176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *body() const { return Body; } 8056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 806c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 807c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 808c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nr = Vs.traverse(Range, Vs.typeCtx(Ctx)); 809c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nb = Vs.traverse(Body, Vs.lazyCtx(Ctx)); 810c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceField(*this, Nr, Nb); 8116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 8126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 813176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 814176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Field* E, C& Cmp) const { 8156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(range(), E->range()); 8166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 8176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 8186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(body(), E->body()); 8196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 8206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 8216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 822176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Range; 823176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Body; 8246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 8256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 8266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 827176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Apply an argument to a function. 828176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Note that this does not actually call the function. Functions are curried, 829176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// so this returns a closure in which the first parameter has been applied. 830176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Once all parameters have been applied, Call can be used to invoke the 831176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// function. 8326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Apply : public SExpr { 8336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 8346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Apply; } 8356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 8366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Apply(SExpr *F, SExpr *A) : SExpr(COP_Apply), Fun(F), Arg(A) {} 8376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Apply(const Apply &A, SExpr *F, SExpr *Ar) // rewrite constructor 8386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(A), Fun(F), Arg(Ar) 8396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines {} 8406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 841176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *fun() { return Fun; } 842176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *fun() const { return Fun; } 8436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 844176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *arg() { return Arg; } 845176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *arg() const { return Arg; } 8466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 847c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 848c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 849c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nf = Vs.traverse(Fun, Vs.subExprCtx(Ctx)); 850c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Na = Vs.traverse(Arg, Vs.subExprCtx(Ctx)); 851c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceApply(*this, Nf, Na); 8526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 8536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 854176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 855176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Apply* E, C& Cmp) const { 8566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(fun(), E->fun()); 8576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 8586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 8596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(arg(), E->arg()); 8606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 8616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 8626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 863176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Fun; 864176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Arg; 8656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 8666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 8676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 868176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Apply a self-argument to a self-applicable function. 8696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass SApply : public SExpr { 8706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 8716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_SApply; } 8726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 8736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SApply(SExpr *Sf, SExpr *A = nullptr) : SExpr(COP_SApply), Sfun(Sf), Arg(A) {} 8746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines SApply(SApply &A, SExpr *Sf, SExpr *Ar = nullptr) // rewrite constructor 8756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(A), Sfun(Sf), Arg(Ar) {} 8766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 877176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *sfun() { return Sfun; } 878176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *sfun() const { return Sfun; } 8796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 880176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *arg() { return Arg ? Arg : Sfun; } 881176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *arg() const { return Arg ? Arg : Sfun; } 8826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 883176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool isDelegation() const { return Arg != nullptr; } 8846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 885c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 886c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 887c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nf = Vs.traverse(Sfun, Vs.subExprCtx(Ctx)); 888176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename V::R_SExpr Na = Arg ? Vs.traverse(Arg, Vs.subExprCtx(Ctx)) 889c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines : nullptr; 890c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceSApply(*this, Nf, Na); 8916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 8926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 893176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 894176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const SApply* E, C& Cmp) const { 8956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(sfun(), E->sfun()); 8966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct) || (!arg() && !E->arg())) 8976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 8986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(arg(), E->arg()); 8996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 9006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 902176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Sfun; 903176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Arg; 9046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 9056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 907176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Project a named slot from a C++ struct or class. 9086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Project : public SExpr { 9096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 9106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Project; } 9116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Project(SExpr *R, StringRef SName) 9136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(COP_Project), Rec(R), SlotName(SName), Cvdecl(nullptr) 9146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines { } 915176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Project(SExpr *R, const clang::ValueDecl *Cvd) 9166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(COP_Project), Rec(R), SlotName(Cvd->getName()), Cvdecl(Cvd) 9176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines { } 9186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Project(const Project &P, SExpr *R) 9196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(P), Rec(R), SlotName(P.SlotName), Cvdecl(P.Cvdecl) 9206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines { } 9216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 922176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *record() { return Rec; } 923176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *record() const { return Rec; } 924176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 925176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const clang::ValueDecl *clangDecl() const { return Cvdecl; } 9266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 927176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool isArrow() const { return (Flags & 0x01) != 0; } 928176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void setArrow(bool b) { 929176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines if (b) Flags |= 0x01; 930176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines else Flags &= 0xFFFE; 931176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 9326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines StringRef slotName() const { 9346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cvdecl) 9356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cvdecl->getName(); 9366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines else 9376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return SlotName; 9386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 9396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 940c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 941c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 942c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nr = Vs.traverse(Rec, Vs.subExprCtx(Ctx)); 943c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceProject(*this, Nr); 9446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 9456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 946176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 947176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Project* E, C& Cmp) const { 9486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(record(), E->record()); 9496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 9506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 9516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.comparePointers(Cvdecl, E->Cvdecl); 9526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 9536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 955176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Rec; 9566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines StringRef SlotName; 957176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const clang::ValueDecl *Cvdecl; 9586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 9596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 961176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Call a function (after all arguments have been applied). 9626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Call : public SExpr { 9636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 9646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 9656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Call(SExpr *T, const clang::CallExpr *Ce = nullptr) 9676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(COP_Call), Target(T), Cexpr(Ce) {} 9686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Call(const Call &C, SExpr *T) : SExpr(C), Target(T), Cexpr(C.Cexpr) {} 9696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 970176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *target() { return Target; } 971176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *target() const { return Target; } 9726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const clang::CallExpr *clangCallExpr() const { return Cexpr; } 9746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 975c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 976c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 977c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nt = Vs.traverse(Target, Vs.subExprCtx(Ctx)); 978c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceCall(*this, Nt); 9796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 9806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 981176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 982176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Call* E, C& Cmp) const { 9836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(target(), E->target()); 9846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 9856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 987176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Target; 9886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const clang::CallExpr *Cexpr; 9896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 9906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 992176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Allocate memory for a new value on the heap or stack. 9936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Alloc : public SExpr { 9946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 9956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Call; } 9966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 9976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines enum AllocKind { 9986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines AK_Stack, 9996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines AK_Heap 10006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines }; 10016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Alloc(SExpr *D, AllocKind K) : SExpr(COP_Alloc), Dtype(D) { Flags = K; } 10036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Alloc(const Alloc &A, SExpr *Dt) : SExpr(A), Dtype(Dt) { Flags = A.kind(); } 10046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines AllocKind kind() const { return static_cast<AllocKind>(Flags); } 10066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1007176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *dataType() { return Dtype; } 1008176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *dataType() const { return Dtype; } 10096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1010c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1011c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1012c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nd = Vs.traverse(Dtype, Vs.declCtx(Ctx)); 1013c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceAlloc(*this, Nd); 10146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 10156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1016176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1017176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Alloc* E, C& Cmp) const { 10186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compareIntegers(kind(), E->kind()); 10196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 10206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 10216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(dataType(), E->dataType()); 10226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 10236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1025176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Dtype; 10266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 10276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1029176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Load a value from memory. 10306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Load : public SExpr { 10316bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 10326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Load; } 10336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Load(SExpr *P) : SExpr(COP_Load), Ptr(P) {} 10356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Load(const Load &L, SExpr *P) : SExpr(L), Ptr(P) {} 10366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1037176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *pointer() { return Ptr; } 1038176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *pointer() const { return Ptr; } 10396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1040c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1041c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1042c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Np = Vs.traverse(Ptr, Vs.subExprCtx(Ctx)); 1043c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLoad(*this, Np); 10446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 10456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1046176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1047176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Load* E, C& Cmp) const { 10486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(pointer(), E->pointer()); 10496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 10506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1052176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Ptr; 10536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 10546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1056176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Store a value to memory. 1057176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// The destination is a pointer to a field, the source is the value to store. 10586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Store : public SExpr { 10596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 10606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Store; } 10616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Store(SExpr *P, SExpr *V) : SExpr(COP_Store), Dest(P), Source(V) {} 10636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Store(const Store &S, SExpr *P, SExpr *V) : SExpr(S), Dest(P), Source(V) {} 10646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1065176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *destination() { return Dest; } // Address to store to 1066176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *destination() const { return Dest; } 10676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1068176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *source() { return Source; } // Value to store 1069176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *source() const { return Source; } 10706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1071c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1072c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1073c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Np = Vs.traverse(Dest, Vs.subExprCtx(Ctx)); 1074c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nv = Vs.traverse(Source, Vs.subExprCtx(Ctx)); 1075c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceStore(*this, Np, Nv); 10766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 10776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1078176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1079176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Store* E, C& Cmp) const { 10806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(destination(), E->destination()); 10816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 10826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 10836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(source(), E->source()); 10846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 10856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1087176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Dest; 1088176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Source; 10896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 10906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 10916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1092176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// If p is a reference to an array, then p[i] is a reference to the i'th 1093176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// element of the array. 1094c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinesclass ArrayIndex : public SExpr { 10956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 1096c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayIndex; } 10976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1098c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines ArrayIndex(SExpr *A, SExpr *N) : SExpr(COP_ArrayIndex), Array(A), Index(N) {} 1099c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines ArrayIndex(const ArrayIndex &E, SExpr *A, SExpr *N) 1100c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines : SExpr(E), Array(A), Index(N) {} 11016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1102176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *array() { return Array; } 1103176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *array() const { return Array; } 11046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1105176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *index() { return Index; } 1106176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *index() const { return Index; } 1107c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1108c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1109c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1110c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1111c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1112c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceArrayIndex(*this, Na, Ni); 11136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 11146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1115176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1116176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const ArrayIndex* E, C& Cmp) const { 1117c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename C::CType Ct = Cmp.compare(array(), E->array()); 1118c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines if (Cmp.notTrue(Ct)) 1119c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Ct; 1120c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Cmp.compare(index(), E->index()); 11216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 11226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 11236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1124176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Array; 1125176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Index; 11266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 11276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 11286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1129176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Pointer arithmetic, restricted to arrays only. 1130176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// If p is a reference to an array, then p + n, where n is an integer, is 1131176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// a reference to a subarray. 11326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass ArrayAdd : public SExpr { 11336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 11346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_ArrayAdd; } 11356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 11366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ArrayAdd(SExpr *A, SExpr *N) : SExpr(COP_ArrayAdd), Array(A), Index(N) {} 11376bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines ArrayAdd(const ArrayAdd &E, SExpr *A, SExpr *N) 11386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(E), Array(A), Index(N) {} 11396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1140176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *array() { return Array; } 1141176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *array() const { return Array; } 11426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1143176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *index() { return Index; } 1144176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *index() const { return Index; } 11456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1146c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1147c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1148c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Na = Vs.traverse(Array, Vs.subExprCtx(Ctx)); 1149c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Ni = Vs.traverse(Index, Vs.subExprCtx(Ctx)); 1150c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceArrayAdd(*this, Na, Ni); 11516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 11526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1153176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1154176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const ArrayAdd* E, C& Cmp) const { 11556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(array(), E->array()); 11566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 11576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 11586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(index(), E->index()); 11596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 11606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 11616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1162176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Array; 1163176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Index; 11646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 11656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 11666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1167176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Simple arithmetic unary operations, e.g. negate and not. 1168176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// These operations have no side-effects. 11696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass UnaryOp : public SExpr { 11706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 11716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_UnaryOp; } 11726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 11736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines UnaryOp(TIL_UnaryOpcode Op, SExpr *E) : SExpr(COP_UnaryOp), Expr0(E) { 11746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Flags = Op; 11756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 11766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines UnaryOp(const UnaryOp &U, SExpr *E) : SExpr(U), Expr0(E) { Flags = U.Flags; } 11776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 11786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines TIL_UnaryOpcode unaryOpcode() const { 11796bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return static_cast<TIL_UnaryOpcode>(Flags); 11806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 11816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1182176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *expr() { return Expr0; } 1183176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *expr() const { return Expr0; } 11846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1185c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1186c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1187c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1188c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceUnaryOp(*this, Ne); 11896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 11906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1191176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1192176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const UnaryOp* E, C& Cmp) const { 11936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = 11946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.compareIntegers(unaryOpcode(), E->unaryOpcode()); 11956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 11966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 11976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(expr(), E->expr()); 11986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 11996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1201176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Expr0; 12026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 12036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1205176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Simple arithmetic binary operations, e.g. +, -, etc. 1206176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// These operations have no side effects. 12076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass BinaryOp : public SExpr { 12086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 12096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_BinaryOp; } 12106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BinaryOp(TIL_BinaryOpcode Op, SExpr *E0, SExpr *E1) 12126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(COP_BinaryOp), Expr0(E0), Expr1(E1) { 12136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Flags = Op; 12146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 12156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines BinaryOp(const BinaryOp &B, SExpr *E0, SExpr *E1) 12166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(B), Expr0(E0), Expr1(E1) { 12176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Flags = B.Flags; 12186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 12196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines TIL_BinaryOpcode binaryOpcode() const { 12216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return static_cast<TIL_BinaryOpcode>(Flags); 12226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 12236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1224176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *expr0() { return Expr0; } 1225176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *expr0() const { return Expr0; } 12266bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1227176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *expr1() { return Expr1; } 1228176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *expr1() const { return Expr1; } 12296bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1230c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1231c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1232c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Ne0 = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1233c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Ne1 = Vs.traverse(Expr1, Vs.subExprCtx(Ctx)); 1234c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceBinaryOp(*this, Ne0, Ne1); 12356bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 12366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1237176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1238176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const BinaryOp* E, C& Cmp) const { 12396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = 12406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.compareIntegers(binaryOpcode(), E->binaryOpcode()); 12416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 12426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 12436bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Ct = Cmp.compare(expr0(), E->expr0()); 12446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 12456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 12466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(expr1(), E->expr1()); 12476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 12486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1250176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Expr0; 1251176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Expr1; 12526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 12536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1255176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Cast expressions. 1256176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Cast expressions are essentially unary operations, but we treat them 1257176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// as a distinct AST node because they only change the type of the result. 12586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Cast : public SExpr { 12596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 12606bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Cast; } 12616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cast(TIL_CastOpcode Op, SExpr *E) : SExpr(COP_Cast), Expr0(E) { Flags = Op; } 12636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cast(const Cast &C, SExpr *E) : SExpr(C), Expr0(E) { Flags = C.Flags; } 12646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines TIL_CastOpcode castOpcode() const { 12666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return static_cast<TIL_CastOpcode>(Flags); 12676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 12686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1269176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *expr() { return Expr0; } 1270176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *expr() const { return Expr0; } 12716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1272c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1273c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1274c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Ne = Vs.traverse(Expr0, Vs.subExprCtx(Ctx)); 1275c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceCast(*this, Ne); 12766bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 12776bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1278176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1279176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Cast* E, C& Cmp) const { 12806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = 12816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.compareIntegers(castOpcode(), E->castOpcode()); 12826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 12836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 12846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(expr(), E->expr()); 12856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 12866bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1288176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Expr0; 12896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 12906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1292c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinesclass SCFG; 12936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 12946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1295176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Phi Node, for code in SSA form. 1296176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Each Phi node has an array of possible values that it can take, 1297176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// depending on where control flow comes from. 1298c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinesclass Phi : public SExpr { 12996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 1300c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typedef SimpleArray<SExpr *> ValArray; 13016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1302c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // In minimal SSA form, all Phi nodes are MultiVal. 1303c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // During conversion to SSA, incomplete Phi nodes may be introduced, which 1304c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // are later determined to be SingleVal, and are thus redundant. 1305c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines enum Status { 1306c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines PH_MultiVal = 0, // Phi node has multiple distinct values. (Normal) 1307c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines PH_SingleVal, // Phi node has one distinct value, and can be eliminated 1308c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines PH_Incomplete // Phi node is incomplete 1309c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines }; 13106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1311c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Phi; } 13126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1313176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Phi() 1314176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : SExpr(COP_Phi), Cvdecl(nullptr) {} 1315176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Phi(MemRegionRef A, unsigned Nvals) 1316176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : SExpr(COP_Phi), Values(A, Nvals), Cvdecl(nullptr) {} 1317176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Phi(const Phi &P, ValArray &&Vs) 1318176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : SExpr(P), Values(std::move(Vs)), Cvdecl(nullptr) {} 13196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1320c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines const ValArray &values() const { return Values; } 1321c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines ValArray &values() { return Values; } 13226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1323c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Status status() const { return static_cast<Status>(Flags); } 1324c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines void setStatus(Status s) { Flags = s; } 13256bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1326176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the clang declaration of the variable for this Phi node, if any. 1327176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const clang::ValueDecl *clangDecl() const { return Cvdecl; } 1328176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1329176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Set the clang variable associated with this Phi node. 1330176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void setClangDecl(const clang::ValueDecl *Cvd) { Cvdecl = Cvd; } 1331176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1332c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1333c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1334c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::template Container<typename V::R_SExpr> 1335c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Nvs(Vs, Values.size()); 13366bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1337c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines for (auto *Val : Values) { 1338c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Nvs.push_back( Vs.traverse(Val, Vs.subExprCtx(Ctx)) ); 1339c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 1340c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reducePhi(*this, Nvs); 1341c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 13426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1343176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1344176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Phi *E, C &Cmp) const { 1345c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // TODO: implement CFG comparisons 13466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.comparePointers(this, E); 13476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 13486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 13496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1350c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines ValArray Values; 1351176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const clang::ValueDecl* Cvdecl; 1352176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines}; 1353176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1354176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1355176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Base class for basic block terminators: Branch, Goto, and Return. 1356176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesclass Terminator : public SExpr { 1357176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinespublic: 1358176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines static bool classof(const SExpr *E) { 1359176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return E->opcode() >= COP_Goto && E->opcode() <= COP_Return; 1360176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1361176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1362176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesprotected: 1363176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Terminator(TIL_Opcode Op) : SExpr(Op) {} 1364176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Terminator(const SExpr &E) : SExpr(E) {} 1365176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1366176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinespublic: 1367176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the list of basic blocks that this terminator can branch to. 1368176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ArrayRef<BasicBlock*> successors(); 1369176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1370176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ArrayRef<BasicBlock*> successors() const { 13710e2c34f92f00628d48968dfea096d36381f494cbStephen Hines return const_cast<Terminator*>(this)->successors(); 1372176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1373176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines}; 1374176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1375176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1376176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Jump to another basic block. 1377176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A goto instruction is essentially a tail-recursive call into another 1378176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// block. In addition to the block pointer, it specifies an index into the 1379176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// phi nodes of that block. The index can be used to retrieve the "arguments" 1380176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// of the call. 1381176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesclass Goto : public Terminator { 1382176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinespublic: 1383176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Goto; } 1384176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1385176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Goto(BasicBlock *B, unsigned I) 1386176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1387176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Goto(const Goto &G, BasicBlock *B, unsigned I) 1388176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : Terminator(COP_Goto), TargetBlock(B), Index(I) {} 1389176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1390176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const BasicBlock *targetBlock() const { return TargetBlock; } 1391176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *targetBlock() { return TargetBlock; } 1392176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1393176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Returns the index into the 1394176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines unsigned index() const { return Index; } 1395176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1396176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the list of basic blocks that this terminator can branch to. 1397176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ArrayRef<BasicBlock*> successors() { 139887d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar return TargetBlock; 1399176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1400176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1401176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class V> 1402176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1403176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *Ntb = Vs.reduceBasicBlockRef(TargetBlock); 1404176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Vs.reduceGoto(*this, Ntb); 1405176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1406176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1407176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1408176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Goto *E, C &Cmp) const { 1409176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // TODO: implement CFG comparisons 1410176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Cmp.comparePointers(this, E); 1411176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1412176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1413176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesprivate: 1414176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *TargetBlock; 1415176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines unsigned Index; 1416176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines}; 1417176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1418176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1419176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A conditional branch to two other blocks. 1420176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Note that unlike Goto, Branch does not have an index. The target blocks 1421176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// must be child-blocks, and cannot have Phi nodes. 1422176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesclass Branch : public Terminator { 1423176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinespublic: 1424176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Branch; } 1425176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1426176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Branch(SExpr *C, BasicBlock *T, BasicBlock *E) 1427176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : Terminator(COP_Branch), Condition(C) { 1428176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Branches[0] = T; 1429176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Branches[1] = E; 1430176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1431176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Branch(const Branch &Br, SExpr *C, BasicBlock *T, BasicBlock *E) 1432176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : Terminator(Br), Condition(C) { 1433176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Branches[0] = T; 1434176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Branches[1] = E; 1435176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1436176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1437176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *condition() const { return Condition; } 1438176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *condition() { return Condition; } 1439176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1440176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const BasicBlock *thenBlock() const { return Branches[0]; } 1441176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *thenBlock() { return Branches[0]; } 1442176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1443176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const BasicBlock *elseBlock() const { return Branches[1]; } 1444176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *elseBlock() { return Branches[1]; } 1445176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1446176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the list of basic blocks that this terminator can branch to. 1447176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ArrayRef<BasicBlock*> successors() { 144887d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar return llvm::makeArrayRef(Branches); 1449176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1450176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1451176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class V> 1452176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1453176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1454176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *Ntb = Vs.reduceBasicBlockRef(Branches[0]); 1455176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *Nte = Vs.reduceBasicBlockRef(Branches[1]); 1456176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Vs.reduceBranch(*this, Nc, Ntb, Nte); 1457176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1458176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1459176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1460176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Branch *E, C &Cmp) const { 1461176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // TODO: implement CFG comparisons 1462176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Cmp.comparePointers(this, E); 1463176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1464176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1465176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesprivate: 1466176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Condition; 1467176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *Branches[2]; 14686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 14696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 14706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1471176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Return from the enclosing function, passing the return value to the caller. 1472176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// Only the exit block should end with a return statement. 1473176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesclass Return : public Terminator { 1474176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinespublic: 1475176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } 1476176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1477176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Return(SExpr* Rval) : Terminator(COP_Return), Retval(Rval) {} 1478176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Return(const Return &R, SExpr* Rval) : Terminator(R), Retval(Rval) {} 1479176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1480176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return an empty list. 1481176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ArrayRef<BasicBlock*> successors() { 148287d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar return None; 1483176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1484176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1485176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *returnValue() { return Retval; } 1486176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *returnValue() const { return Retval; } 1487176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1488176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class V> 1489176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1490176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines auto Ne = Vs.traverse(Retval, Vs.subExprCtx(Ctx)); 1491176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Vs.reduceReturn(*this, Ne); 1492176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1493176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1494176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1495176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Return *E, C &Cmp) const { 1496176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return Cmp.compare(Retval, E->Retval); 1497176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1498176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1499176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesprivate: 1500176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Retval; 1501176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines}; 1502176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1503176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1504176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesinline ArrayRef<BasicBlock*> Terminator::successors() { 1505176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines switch (opcode()) { 1506176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines case COP_Goto: return cast<Goto>(this)->successors(); 1507176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines case COP_Branch: return cast<Branch>(this)->successors(); 1508176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines case COP_Return: return cast<Return>(this)->successors(); 1509176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines default: 151087d948ecccffea9e9e37d0d053b246e2d6d6c47bPirama Arumuga Nainar return None; 1511176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1512176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines} 1513176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1514176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1515176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A basic block is part of an SCFG. It can be treated as a function in 1516176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// continuation passing style. A block consists of a sequence of phi nodes, 1517176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// which are "arguments" to the function, followed by a sequence of 1518176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// instructions. It ends with a Terminator, which is a Branch or Goto to 1519176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// another basic block in the same SCFG. 1520c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinesclass BasicBlock : public SExpr { 15216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 1522176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typedef SimpleArray<SExpr*> InstrArray; 1523c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typedef SimpleArray<BasicBlock*> BlockArray; 1524c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1525176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // TopologyNodes are used to overlay tree structures on top of the CFG, 1526176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // such as dominator and postdominator trees. Each block is assigned an 1527176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // ID in the tree according to a depth-first search. Tree traversals are 1528176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // always up, towards the parents. 1529176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines struct TopologyNode { 1530176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines TopologyNode() : NodeID(0), SizeOfSubTree(0), Parent(nullptr) {} 1531176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1532176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool isParentOf(const TopologyNode& OtherNode) { 1533176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return OtherNode.NodeID > NodeID && 1534176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines OtherNode.NodeID < NodeID + SizeOfSubTree; 1535176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1536176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1537176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool isParentOfOrEqual(const TopologyNode& OtherNode) { 1538176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return OtherNode.NodeID >= NodeID && 1539176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines OtherNode.NodeID < NodeID + SizeOfSubTree; 1540176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1541176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1542176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines int NodeID; 1543176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines int SizeOfSubTree; // Includes this node, so must be > 1. 1544176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *Parent; // Pointer to parent. 1545176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines }; 1546176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1547c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_BasicBlock; } 1548c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1549176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines explicit BasicBlock(MemRegionRef A) 1550c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0), 1551176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Visited(0), TermInstr(nullptr) {} 1552176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock(BasicBlock &B, MemRegionRef A, InstrArray &&As, InstrArray &&Is, 1553176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Terminator *T) 1554176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines : SExpr(COP_BasicBlock), Arena(A), CFGPtr(nullptr), BlockID(0),Visited(0), 1555176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Args(std::move(As)), Instrs(std::move(Is)), TermInstr(T) {} 1556176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1557176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Returns the block ID. Every block has a unique ID in the CFG. 1558176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines int blockID() const { return BlockID; } 15596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1560176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Returns the number of predecessors. 1561176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines size_t numPredecessors() const { return Predecessors.size(); } 1562176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines size_t numSuccessors() const { return successors().size(); } 1563c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1564c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines const SCFG* cfg() const { return CFGPtr; } 1565c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines SCFG* cfg() { return CFGPtr; } 15666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1567176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const BasicBlock *parent() const { return DominatorNode.Parent; } 1568176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BasicBlock *parent() { return DominatorNode.Parent; } 15696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1570176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const InstrArray &arguments() const { return Args; } 1571176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines InstrArray &arguments() { return Args; } 15726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1573176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines InstrArray &instructions() { return Instrs; } 1574176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const InstrArray &instructions() const { return Instrs; } 15756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1576176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Returns a list of predecessors. 1577176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// The order of predecessors in the list is important; each phi node has 1578176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// exactly one argument for each precessor, in the same order. 1579c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines BlockArray &predecessors() { return Predecessors; } 1580176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const BlockArray &predecessors() const { return Predecessors; } 1581176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1582176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ArrayRef<BasicBlock*> successors() { return TermInstr->successors(); } 1583176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines ArrayRef<BasicBlock*> successors() const { return TermInstr->successors(); } 1584176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1585176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const Terminator *terminator() const { return TermInstr; } 1586176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Terminator *terminator() { return TermInstr; } 1587c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1588176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void setTerminator(Terminator *E) { TermInstr = E; } 15896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1590176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool Dominates(const BasicBlock &Other) { 1591176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return DominatorNode.isParentOfOrEqual(Other.DominatorNode); 1592176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 1593176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1594176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool PostDominates(const BasicBlock &Other) { 1595176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines return PostDominatorNode.isParentOfOrEqual(Other.PostDominatorNode); 1596176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines } 15976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1598176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Add a new argument. 1599176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void addArgument(Phi *V) { 1600c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Args.reserveCheck(1, Arena); 16016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Args.push_back(V); 16026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1603176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Add a new instruction. 1604176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void addInstruction(SExpr *V) { 1605c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Instrs.reserveCheck(1, Arena); 16066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Instrs.push_back(V); 16076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1608c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Add a new predecessor, and return the phi-node index for it. 1609c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Will add an argument to all phi-nodes, initialized to nullptr. 1610c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines unsigned addPredecessor(BasicBlock *Pred); 1611c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1612c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Reserve space for Nargs arguments. 1613c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines void reserveArguments(unsigned Nargs) { Args.reserve(Nargs, Arena); } 1614c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1615c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Reserve space for Nins instructions. 1616c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines void reserveInstructions(unsigned Nins) { Instrs.reserve(Nins, Arena); } 16176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1618c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Reserve space for NumPreds predecessors, including space in phi nodes. 1619c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines void reservePredecessors(unsigned NumPreds); 1620c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1621176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the index of BB, or Predecessors.size if BB is not a predecessor. 1622c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines unsigned findPredecessorIndex(const BasicBlock *BB) const { 1623c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto I = std::find(Predecessors.cbegin(), Predecessors.cend(), BB); 1624c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return std::distance(Predecessors.cbegin(), I); 1625c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 1626c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1627c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1628c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_BasicBlock traverse(V &Vs, typename V::R_Ctx Ctx) { 1629176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename V::template Container<SExpr*> Nas(Vs, Args.size()); 1630176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename V::template Container<SExpr*> Nis(Vs, Instrs.size()); 1631c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines 1632c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Entering the basic block should do any scope initialization. 1633c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Vs.enterBasicBlock(*this); 16346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1635176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines for (auto *E : Args) { 1636176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); 1637176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Nas.push_back(Ne); 16386bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1639176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines for (auto *E : Instrs) { 1640176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines auto Ne = Vs.traverse(E, Vs.subExprCtx(Ctx)); 1641176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Nis.push_back(Ne); 16426bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1643176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines auto Nt = Vs.traverse(TermInstr, Ctx); 16446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1645c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // Exiting the basic block should handle any scope cleanup. 1646c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Vs.exitBasicBlock(*this); 16476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1648c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceBasicBlock(*this, Nas, Nis, Nt); 16496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 16506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1651176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1652176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const BasicBlock *E, C &Cmp) const { 16536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // TODO: implement CFG comparisons 16546bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.comparePointers(this, E); 16556bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 16566bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 16576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 16586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines friend class SCFG; 16596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1660176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines int renumberInstrs(int id); // assign unique ids to all instructions 1661176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines int topologicalSort(SimpleArray<BasicBlock*>& Blocks, int ID); 1662176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines int topologicalFinalSort(SimpleArray<BasicBlock*>& Blocks, int ID); 1663176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void computeDominator(); 1664176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void computePostDominator(); 16656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1666176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesprivate: 1667176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines MemRegionRef Arena; // The arena used to allocate this block. 1668176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SCFG *CFGPtr; // The CFG that contains this block. 1669176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines int BlockID : 31; // unique id for this BB in the containing CFG. 1670176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // IDs are in topological order. 1671176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool Visited : 1; // Bit to determine if a block has been visited 1672176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // during a traversal. 1673176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines BlockArray Predecessors; // Predecessor blocks in the CFG. 1674176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines InstrArray Args; // Phi nodes. One argument per predecessor. 1675176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines InstrArray Instrs; // Instructions. 1676176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Terminator* TermInstr; // Terminating instruction 1677176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1678176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines TopologyNode DominatorNode; // The dominator tree 1679176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines TopologyNode PostDominatorNode; // The post-dominator tree 16806bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 16816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 16826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1683176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// An SCFG is a control-flow graph. It consists of a set of basic blocks, 1684176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// each of which terminates in a branch to another basic block. There is one 1685176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// entry point, and one exit point. 1686c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinesclass SCFG : public SExpr { 1687c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hinespublic: 1688c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typedef SimpleArray<BasicBlock *> BlockArray; 1689c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typedef BlockArray::iterator iterator; 1690c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typedef BlockArray::const_iterator const_iterator; 16916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1692c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_SCFG; } 16936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1694c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines SCFG(MemRegionRef A, unsigned Nblocks) 1695c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines : SExpr(COP_SCFG), Arena(A), Blocks(A, Nblocks), 1696176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) { 1697176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Entry = new (A) BasicBlock(A); 1698176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Exit = new (A) BasicBlock(A); 1699176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines auto *V = new (A) Phi(); 1700c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Exit->addArgument(V); 1701176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Exit->setTerminator(new (A) Return(V)); 1702c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines add(Entry); 1703c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines add(Exit); 1704c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 1705c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines SCFG(const SCFG &Cfg, BlockArray &&Ba) // steals memory from Ba 1706c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines : SExpr(COP_SCFG), Arena(Cfg.Arena), Blocks(std::move(Ba)), 1707176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines Entry(nullptr), Exit(nullptr), NumInstructions(0), Normal(false) { 1708c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines // TODO: set entry and exit! 1709c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 17106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1711176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return true if this CFG is valid. 1712176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool valid() const { return Entry && Exit && Blocks.size() > 0; } 1713176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1714176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return true if this CFG has been normalized. 1715176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// After normalization, blocks are in topological order, and block and 1716176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// instruction IDs have been assigned. 1717176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool normal() const { return Normal; } 1718176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1719c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines iterator begin() { return Blocks.begin(); } 1720c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines iterator end() { return Blocks.end(); } 17216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1722c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines const_iterator begin() const { return cbegin(); } 1723c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines const_iterator end() const { return cend(); } 17246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1725c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines const_iterator cbegin() const { return Blocks.cbegin(); } 1726c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines const_iterator cend() const { return Blocks.cend(); } 17276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1728c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines const BasicBlock *entry() const { return Entry; } 1729c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines BasicBlock *entry() { return Entry; } 1730c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines const BasicBlock *exit() const { return Exit; } 1731c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines BasicBlock *exit() { return Exit; } 17326bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1733176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the number of blocks in the CFG. 1734176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Block::blockID() will return a number less than numBlocks(); 1735176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines size_t numBlocks() const { return Blocks.size(); } 1736176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1737176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// Return the total number of instructions in the CFG. 1738176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// This is useful for building instruction side-tables; 1739176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines /// A call to SExpr::id() will return a number less than numInstructions(). 1740176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines unsigned numInstructions() { return NumInstructions; } 1741176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1742c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines inline void add(BasicBlock *BB) { 1743176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines assert(BB->CFGPtr == nullptr); 1744c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines BB->CFGPtr = this; 1745c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Blocks.reserveCheck(1, Arena); 1746c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Blocks.push_back(BB); 1747c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines } 17486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1749c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines void setEntry(BasicBlock *BB) { Entry = BB; } 1750c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines void setExit(BasicBlock *BB) { Exit = BB; } 17516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1752176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void computeNormalForm(); 17536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1754c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1755c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1756c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Vs.enterCFG(*this); 1757c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::template Container<BasicBlock *> Bbs(Vs, Blocks.size()); 1758176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1759c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines for (auto *B : Blocks) { 1760c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Bbs.push_back( B->traverse(Vs, Vs.subExprCtx(Ctx)) ); 17616bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 1762c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Vs.exitCFG(*this); 1763c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceSCFG(*this, Bbs); 17646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 17656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1766176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1767176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const SCFG *E, C &Cmp) const { 1768176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines // TODO: implement CFG comparisons 17696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.comparePointers(this, E); 17706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 17716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 17726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1773176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines void renumberInstrs(); // assign unique ids to all instructions 1774176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines 1775176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesprivate: 1776c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines MemRegionRef Arena; 1777c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines BlockArray Blocks; 1778c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines BasicBlock *Entry; 1779c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines BasicBlock *Exit; 1780176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines unsigned NumInstructions; 1781176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines bool Normal; 17826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 17836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 17846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 17856bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1786176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// An identifier, e.g. 'foo' or 'x'. 1787176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// This is a pseduo-term; it will be lowered to a variable or projection. 17886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Identifier : public SExpr { 17896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 17906bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Identifier; } 17916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 17926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Identifier(StringRef Id): SExpr(COP_Identifier), Name(Id) { } 17936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Identifier(const Identifier& I) : SExpr(I), Name(I.Name) { } 17946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 17956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines StringRef name() const { return Name; } 17966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1797c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1798c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1799c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceIdentifier(*this); 18006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 18016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1802176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1803176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Identifier* E, C& Cmp) const { 18046bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compareStrings(name(), E->name()); 18056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 18066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 18076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 18086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines StringRef Name; 18096bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 18106bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 18116bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1812176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// An if-then-else expression. 1813176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// This is a pseduo-term; it will be lowered to a branch in a CFG. 18146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass IfThenElse : public SExpr { 18156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 18166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_IfThenElse; } 18176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 18186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines IfThenElse(SExpr *C, SExpr *T, SExpr *E) 18196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(COP_IfThenElse), Condition(C), ThenExpr(T), ElseExpr(E) 18206bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines { } 18216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines IfThenElse(const IfThenElse &I, SExpr *C, SExpr *T, SExpr *E) 18226bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines : SExpr(I), Condition(C), ThenExpr(T), ElseExpr(E) 18236bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines { } 18246bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1825176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *condition() { return Condition; } // Address to store to 1826176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *condition() const { return Condition; } 18276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1828176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *thenExpr() { return ThenExpr; } // Value to store 1829176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *thenExpr() const { return ThenExpr; } 18306bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1831176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *elseExpr() { return ElseExpr; } // Value to store 1832176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *elseExpr() const { return ElseExpr; } 18336bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1834c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1835c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 1836c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nc = Vs.traverse(Condition, Vs.subExprCtx(Ctx)); 1837c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Nt = Vs.traverse(ThenExpr, Vs.subExprCtx(Ctx)); 1838c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto Ne = Vs.traverse(ElseExpr, Vs.subExprCtx(Ctx)); 1839c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceIfThenElse(*this, Nc, Nt, Ne); 18406bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 18416bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1842176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1843176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const IfThenElse* E, C& Cmp) const { 18446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = Cmp.compare(condition(), E->condition()); 18456bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 18466bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 18476bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Ct = Cmp.compare(thenExpr(), E->thenExpr()); 18486bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 18496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 18506bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Cmp.compare(elseExpr(), E->elseExpr()); 18516bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 18526bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 18536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 1854176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Condition; 1855176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* ThenExpr; 1856176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* ElseExpr; 18576bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 18586bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 18596bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1860176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// A let-expression, e.g. let x=t; u. 1861176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines/// This is a pseduo-term; it will be lowered to instructions in a CFG. 18626bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesclass Let : public SExpr { 18636bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinespublic: 18646bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines static bool classof(const SExpr *E) { return E->opcode() == COP_Let; } 18656bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 18666bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Let(Variable *Vd, SExpr *Bd) : SExpr(COP_Let), VarDecl(Vd), Body(Bd) { 18676bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Vd->setKind(Variable::VK_Let); 18686bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 18696bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Let(const Let &L, Variable *Vd, SExpr *Bd) : SExpr(L), VarDecl(Vd), Body(Bd) { 18706bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Vd->setKind(Variable::VK_Let); 18716bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 18726bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 18736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Variable *variableDecl() { return VarDecl; } 18746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const Variable *variableDecl() const { return VarDecl; } 18756bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1876176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr *body() { return Body; } 1877176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines const SExpr *body() const { return Body; } 18786bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1879c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines template <class V> 1880c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { 18816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // This is a variable declaration, so traverse the definition. 1882c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto E0 = Vs.traverse(VarDecl->Definition, Vs.subExprCtx(Ctx)); 18836bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines // Tell the rewriter to enter the scope of the let variable. 1884c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Variable *Nvd = Vs.enterScope(*VarDecl, E0); 1885c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines auto E1 = Vs.traverse(Body, Ctx); 1886c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines Vs.exitScope(*VarDecl); 1887c568f1e98938584c0ef0b12ae5018ff7d90a4072Stephen Hines return Vs.reduceLet(*this, Nvd, E1); 18886bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 18896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1890176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines template <class C> 1891176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines typename C::CType compare(const Let* E, C& Cmp) const { 18926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines typename C::CType Ct = 18936bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.compare(VarDecl->definition(), E->VarDecl->definition()); 18946bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (Cmp.notTrue(Ct)) 18956bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 18966bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.enterScope(variableDecl(), E->variableDecl()); 18976bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Ct = Cmp.compare(body(), E->body()); 18986bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Cmp.leaveScope(); 18996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return Ct; 19006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines } 19016bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 19026bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hinesprivate: 19036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines Variable *VarDecl; 1904176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines SExpr* Body; 19056bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines}; 19066bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 19076bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 19086bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1909176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesconst SExpr *getCanonicalVal(const SExpr *E); 1910176edba5311f6eff0cad2631449885ddf4fbc9eaStephen HinesSExpr* simplifyToCanonicalVal(SExpr *E); 1911176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hinesvoid simplifyIncompleteArg(til::Phi *Ph); 19126bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 19136bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 19146bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace til 19156bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace threadSafety 19166bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines} // end namespace clang 19176bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 1918176edba5311f6eff0cad2631449885ddf4fbc9eaStephen Hines#endif 1919