blob: eb53bad64701ff924f8fe3e3a89bdb63034f30ff [file] [log] [blame]
//===--- SILConstants.h - SIL constant representation -----------*- C++ -*-===//
// This source file is part of the open source project
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
// See for license information
// See for the list of Swift project authors
// This defines an interface to represent SIL level structured constants in a
// memory efficient way.
#include "swift/AST/SubstitutionMap.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SIL/SILValue.h"
#include "llvm/Support/CommandLine.h"
namespace swift {
class SingleValueInstruction;
class SILValue;
class SILBuilder;
class SerializedSILLoader;
struct AggregateSymbolicValue;
struct SymbolicArrayStorage;
struct DerivedAddressValue;
struct EnumWithPayloadSymbolicValue;
struct SymbolicValueMemoryObject;
struct UnknownSymbolicValue;
struct SymbolicClosure;
extern llvm::cl::opt<unsigned> ConstExprLimit;
/// An abstract class that exposes functions for allocating symbolic values.
/// The implementors of this class have to determine where to allocate them and
/// and manage the lifetime of the allocated symbolic values.
class SymbolicValueAllocator {
virtual ~SymbolicValueAllocator() {}
/// Allocate raw bytes.
/// \param byteSize number of bytes to allocate.
/// \param alignment alignment for the allocated bytes.
virtual void *allocate(unsigned long byteSize, unsigned alignment) = 0;
/// Allocate storage for a given number of elements of a specific type
/// provided as a template parameter. Precondition: \c T must have an
/// accesible zero argument constructor.
/// \param numElts number of elements of the type to allocate.
template <typename T> T *allocate(unsigned numElts) {
T *res = (T *)allocate(sizeof(T) * numElts, alignof(T));
for (unsigned i = 0; i != numElts; ++i)
new (res + i) T();
return res;
/// A class that allocates symbolic values in a local bump allocator. The
/// lifetime of the bump allocator is same as the lifetime of \c this object.
class SymbolicValueBumpAllocator : public SymbolicValueAllocator {
llvm::BumpPtrAllocator bumpAllocator;
SymbolicValueBumpAllocator() {}
~SymbolicValueBumpAllocator() {}
void *allocate(unsigned long byteSize, unsigned alignment) override {
return bumpAllocator.Allocate(byteSize, alignment);
/// When we fail to constant fold a value, this captures a reason why,
/// allowing the caller to produce a specific diagnostic. The "Unknown"
/// SymbolicValue representation also includes a pointer to the SILNode in
/// question that was problematic.
class UnknownReason {
enum UnknownKind {
// TODO: Eliminate the default kind, by making classifications for each
// failure mode.
/// The constant expression was too big. This is reported on a random
/// instruction within the constexpr that triggered the issue.
/// A control flow loop was found.
/// Integer overflow detected.
/// Trap detected. Traps will a message as a payload.
/// An operation was applied over operands whose symbolic values were
/// constants but were not valid for the operation.
/// Encountered an instruction not supported by the interpreter.
/// Encountered a function call whose arguments are not constants.
/// Encountered a function call where the body of the called function is
/// not available.
/// Attempted to load from/store into a SIL value that was not tracked by
/// the interpreter.
/// Encountered a checked cast operation whose result cannot be evaluated
/// to a constant.
/// Attempted to find a concrete protocol conformance for a witness method
/// and failed.
/// Attempted to determine the SIL function of a witness method and failed.
/// The value of a top-level variable cannot be determined to be a constant.
/// This is only relevant in the backward evaluation mode, which is used by
/// #assert.
/// A top-level value has multiple writers. This is only relevant in the
/// non-flow-sensitive evaluation mode, which is used by #assert.
/// Indicates the return value of an instruction that was not evaluated
/// during interpretation.
/// Indicates that the value was possibly modified by an instruction
/// that was not evaluated during the interpretation.
UnknownKind kind;
// Auxiliary information for different unknown kinds.
union {
SILFunction *function; // For CalleeImplementationUnknown
const char *trapMessage; // For Trap.
unsigned argumentIndex; // For CallArgumentUnknown
} payload;
UnknownKind getKind() { return kind; }
static bool isUnknownKindWithPayload(UnknownKind kind) {
switch (kind) {
case UnknownKind::CalleeImplementationUnknown:
case UnknownKind::Trap:
case UnknownKind::CallArgumentUnknown:
return true;
return false;
static UnknownReason create(UnknownKind kind) {
UnknownReason reason;
reason.kind = kind;
return reason;
static UnknownReason createCalleeImplementationUnknown(SILFunction *callee) {
UnknownReason reason;
reason.kind = UnknownKind::CalleeImplementationUnknown;
reason.payload.function = callee;
return reason;
SILFunction *getCalleeWithoutImplmentation() {
assert(kind == UnknownKind::CalleeImplementationUnknown);
return payload.function;
static UnknownReason createTrap(StringRef message,
SymbolicValueAllocator &allocator) {
// Copy and null terminate the string.
size_t size = message.size();
char *messagePtr = allocator.allocate<char>(size + 1);
std::uninitialized_copy(message.begin(), message.end(), messagePtr);
messagePtr[size] = '\0';
UnknownReason reason;
reason.kind = UnknownKind::Trap;
reason.payload.trapMessage = messagePtr;
return reason;
const char *getTrapMessage() {
assert(kind == UnknownKind::Trap);
return payload.trapMessage;
static UnknownReason createCallArgumentUnknown(unsigned argIndex) {
UnknownReason reason;
reason.kind = UnknownKind::CallArgumentUnknown;
reason.payload.argumentIndex = argIndex;
return reason;
unsigned getArgumentIndex() {
assert(kind == UnknownKind::CallArgumentUnknown);
return payload.argumentIndex;
/// This is the symbolic value tracked for each SILValue in a scope. We
/// support multiple representational forms for the constant node in order to
/// avoid pointless memory bloat + copying. This is intended to be a
/// light-weight POD type we can put in hash tables and pass around by-value.
/// Internally, this value has multiple ways to represent the same sorts of
/// symbolic values (e.g. to save memory). It provides a simpler public
/// interface though.
class SymbolicValue {
enum RepresentationKind {
/// This value is an alloc stack that has not (yet) been initialized
/// by flow-sensitive analysis.
/// This symbolic value cannot be determined, carries multiple values
/// (i.e., varies dynamically at the top level), or is of some type that
/// we cannot analyze and propagate (e.g. NSObject).
/// This value is known to be a metatype reference. The type is stored
/// in the "metatype" member.
/// This value is known to be a function reference, e.g. through
/// function_ref directly, or a devirtualized method reference.
/// This value is represented with a bump-pointer allocated APInt.
/// This value is represented with an inline integer representation.
/// This value is represented with a bump-pointer allocated char array
/// representing a UTF-8 encoded string.
/// This value is a struct or tuple of constants. This is tracked by the
/// "aggregate" member of the value union.
/// This value is an enum with no payload.
/// This value is an enum with a payload.
/// This represents the address of a memory object.
/// This represents an index *into* a memory object.
/// This represents the internal storage of an array.
/// This represents an array.
/// This represents a closure.
union {
/// When the value is Unknown, this contains information about the
/// unfoldable part of the computation.
UnknownSymbolicValue *unknown;
/// This is always a SILType with an object category. This is the value
/// of the underlying instance type, not the MetatypeType.
TypeBase *metatype;
SILFunction *function;
/// When this SymbolicValue is of "Integer" kind, this pointer stores
/// the words of the APInt value it holds.
uint64_t *integer;
/// This holds the bits of an integer for an inline representation.
uint64_t integerInline;
/// When this SymbolicValue is of "String" kind, this pointer stores
/// information about the StringRef value it holds.
const char *string;
/// When this SymbolicValue is of "Aggregate" kind, this pointer stores
/// information about the aggregate elements, its type and count.
const AggregateSymbolicValue *aggregate;
/// When this SymbolicValue is of "Enum" kind, this pointer stores
/// information about the enum case type.
EnumElementDecl *enumVal;
/// When this SymbolicValue is of "EnumWithPayload" kind, this pointer
/// stores information about the enum case type and its payload.
EnumWithPayloadSymbolicValue *enumValWithPayload;
/// When the representationKind is "DirectAddress", this pointer is the
/// memory object referenced.
SymbolicValueMemoryObject *directAddress;
/// When this SymbolicValue is of "DerivedAddress" kind, this pointer stores
/// information about the memory object and access path of the access.
DerivedAddressValue *derivedAddress;
// The following two fields are for representing an Array.
// In Swift, an array is a non-trivial struct that stores a reference to an
// internal storage: _ContiguousArrayStorage. Though arrays have value
// semantics in Swift, it is not the case in SIL. In SIL, an array can be
// mutated by taking the address of the internal storage i.e., through a
// shared, mutable pointer to the internal storage of the array. In fact,
// this is how an array initialization is lowered in SIL. Therefore, the
// symbolic representation of an array is an addressable "memory cell"
// (i.e., a SymbolicValueMemoryObject) containing the array storage. The
// array storage is modeled by the type: SymbolicArrayStorage. This
// representation of the array enables obtaining the address of the internal
// storage and modifying the array through that address. Array operations
// such as `append` that mutate an array must clone the internal storage of
// the array, following the semantics of the Swift implementation of those
// operations.
/// Representation of array storage (RK_ArrayStorage). SymbolicArrayStorage
/// is a container for a sequence of symbolic values.
SymbolicArrayStorage *arrayStorage;
/// When this symbolic value is of an "Array" kind, this stores a memory
/// object that contains a SymbolicArrayStorage value.
SymbolicValueMemoryObject *array;
/// When this symbolic value is of "Closure" kind, store a pointer to the
/// symbolic representation of the closure.
SymbolicClosure *closure;
} value;
RepresentationKind representationKind : 8;
union {
/// This is the number of bits in an RK_Integer or RK_IntegerInline
/// representation, which makes the number of entries in the list derivable.
unsigned integerBitwidth;
/// This is the number of bytes for an RK_String representation.
unsigned stringNumBytes;
} auxInfo;
/// This enum is used to indicate the sort of value held by a SymbolicValue
/// independent of its concrete representation. This is the public
/// interface to SymbolicValue.
enum Kind {
/// This is a value that isn't a constant.
/// This is a known metatype value.
/// This is a function, represented as a SILFunction.
/// This is an integer constant.
/// String values may have SIL type of Builtin.RawPointer or Builtin.Word
/// type.
/// This can be an array, struct, tuple, etc.
/// This is an enum without payload.
/// This is an enum with payload (formally known as "associated value").
/// This value represents the address of, or into, a memory object.
/// This represents an internal array storage.
/// This represents an array value.
/// This represents a closure.
/// These values are generally only seen internally to the system, external
/// clients shouldn't have to deal with them.
/// For constant values, return the type classification of this value.
Kind getKind() const;
/// Return true if this represents a constant value.
bool isConstant() const {
auto kind = getKind();
return kind != Unknown && kind != UninitMemory;
static SymbolicValue getUnknown(SILNode *node, UnknownReason reason,
llvm::ArrayRef<SourceLoc> callStack,
SymbolicValueAllocator &allocator);
/// Return true if this represents an unknown result.
bool isUnknown() const { return getKind() == Unknown; }
/// Return the call stack for an unknown result.
ArrayRef<SourceLoc> getUnknownCallStack() const;
/// Return the node that triggered an unknown result.
SILNode *getUnknownNode() const;
/// Return the reason an unknown result was generated.
UnknownReason getUnknownReason() const;
static SymbolicValue getUninitMemory() {
SymbolicValue result;
result.representationKind = RK_UninitMemory;
return result;
static SymbolicValue getMetatype(CanType type) {
SymbolicValue result;
result.representationKind = RK_Metatype;
result.value.metatype = type.getPointer();
return result;
CanType getMetatypeValue() const {
assert(representationKind == RK_Metatype);
return CanType(value.metatype);
static SymbolicValue getFunction(SILFunction *fn) {
assert(fn && "Function cannot be null");
SymbolicValue result;
result.representationKind = RK_Function;
result.value.function = fn;
return result;
SILFunction *getFunctionValue() const {
assert(getKind() == Function);
return value.function;
static SymbolicValue getInteger(int64_t value, unsigned bitWidth);
static SymbolicValue getInteger(const APInt &value,
SymbolicValueAllocator &allocator);
APInt getIntegerValue() const;
unsigned getIntegerValueBitWidth() const;
/// Returns a SymbolicValue representing a UTF-8 encoded string.
static SymbolicValue getString(StringRef string,
SymbolicValueAllocator &allocator);
/// Returns the UTF-8 encoded string underlying a SymbolicValue.
StringRef getStringValue() const;
/// This returns an aggregate value with the specified elements in it. This
/// copies the member values into the specified Allocator.
static SymbolicValue getAggregate(ArrayRef<SymbolicValue> members,
Type aggregateType,
SymbolicValueAllocator &allocator);
ArrayRef<SymbolicValue> getAggregateMembers() const;
/// Return the type of this aggregate symbolic value.
Type getAggregateType() const;
/// This returns a constant Symbolic value for the enum case in `decl`, which
/// must not have an associated value.
static SymbolicValue getEnum(EnumElementDecl *decl) {
SymbolicValue result;
result.representationKind = RK_Enum;
result.value.enumVal = decl;
return result;
/// `payload` must be a constant.
static SymbolicValue getEnumWithPayload(EnumElementDecl *decl,
SymbolicValue payload,
SymbolicValueAllocator &allocator);
EnumElementDecl *getEnumValue() const;
SymbolicValue getEnumPayloadValue() const;
/// Return a symbolic value that represents the address of a memory object.
static SymbolicValue getAddress(SymbolicValueMemoryObject *memoryObject) {
SymbolicValue result;
result.representationKind = RK_DirectAddress;
result.value.directAddress = memoryObject;
return result;
/// Return a symbolic value that represents the address of a memory object
/// indexed by a path.
static SymbolicValue getAddress(SymbolicValueMemoryObject *memoryObject,
ArrayRef<unsigned> indices,
SymbolicValueAllocator &allocator);
/// Return the memory object of this reference along with any access path
/// indices involved.
SymbolicValueMemoryObject *
getAddressValue(SmallVectorImpl<unsigned> &accessPath) const;
/// Return just the memory object for an address value.
SymbolicValueMemoryObject *getAddressValueMemoryObject() const;
/// Create a symbolic array storage containing \c elements.
static SymbolicValue
getSymbolicArrayStorage(ArrayRef<SymbolicValue> elements, CanType elementType,
SymbolicValueAllocator &allocator);
/// Create a symbolic array using the given symbolic array storage, which
/// contains the array elements.
static SymbolicValue getArray(Type arrayType, SymbolicValue arrayStorage,
SymbolicValueAllocator &allocator);
/// Return the elements stored in this SymbolicValue of "ArrayStorage" kind.
ArrayRef<SymbolicValue> getStoredElements(CanType &elementType) const;
/// Return the symbolic value representing the internal storage of this array.
SymbolicValue getStorageOfArray() const;
/// Return the symbolic value representing the address of the element of this
/// array at the given \c index. The return value is a derived address whose
/// base is the memory object \c value.array (which contains the array
/// storage) and whose accesspath is \c index.
SymbolicValue getAddressOfArrayElement(SymbolicValueAllocator &allocator,
unsigned index) const;
/// Return the type of this array symbolic value.
Type getArrayType() const;
/// Create and return a symbolic value that represents a closure.
/// \param target SILFunction corresponding the target of the closure.
/// \param capturedArguments an array consisting of SILValues of captured
/// arguments along with their symbolic values when available.
/// \param allocator the allocator to use for storing the contents of this
/// symbolic value.
static SymbolicValue makeClosure(
SILFunction *target,
ArrayRef<std::pair<SILValue, Optional<SymbolicValue>>> capturedArguments,
SubstitutionMap substMap, SingleValueInstruction *closureInst,
SymbolicValueAllocator &allocator);
SymbolicClosure *getClosure() const {
assert(getKind() == Closure);
return value.closure;
// Helpers
/// Dig through single element aggregates, return the ultimate thing inside of
/// it. This is useful when dealing with integers and floats, because they
/// are often wrapped in single-element struct wrappers.
SymbolicValue lookThroughSingleElementAggregates() const;
/// Given that this is an 'Unknown' value, emit diagnostic notes providing
/// context about what the problem is. If there is no location for some
/// reason, we fall back to using the specified location.
void emitUnknownDiagnosticNotes(SILLocation fallbackLoc);
bool isUnknownDueToUnevaluatedInstructions();
/// Clone this SymbolicValue into the specified Allocator and return the new
/// version. This only works for valid constants.
SymbolicValue cloneInto(SymbolicValueAllocator &allocator) const;
void print(llvm::raw_ostream &os, unsigned indent = 0) const;
void dump() const;
static_assert(sizeof(SymbolicValue) == 2 * sizeof(uint64_t),
"SymbolicValue should stay small");
"SymbolicValue should stay trivial");
inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, SymbolicValue val) {
return os;
/// This is a representation of a memory object referred to by an address.
/// Memory objects may be mutated over their lifetime, but their overall type
/// remains the same.
struct SymbolicValueMemoryObject {
Type getType() const { return type; }
SymbolicValue getValue() const { return value; }
void setValue(SymbolicValue newValue) {
assert((newValue.getKind() != SymbolicValue::Aggregate ||
newValue.getAggregateType()->isEqual(type)) &&
"Memory object type does not match the type of the symbolic value");
value = newValue;
/// Create a new memory object whose overall type is as specified.
static SymbolicValueMemoryObject *create(Type type, SymbolicValue value,
SymbolicValueAllocator &allocator);
/// Given that this memory object contains an aggregate value like
/// {{1, 2}, 3}, and given an access path like [0,1], return the indexed
/// element, e.g. "2" in this case.
/// Returns uninit memory if the access path points at or into uninit memory.
/// Precondition: The access path must be valid for this memory object's type.
SymbolicValue getIndexedElement(ArrayRef<unsigned> accessPath);
/// Given that this memory object contains an aggregate value like
/// {{1, 2}, 3}, given an access path like [0,1], and given a new element like
/// "4", set the indexed element to the specified scalar, producing {{1, 4},
/// 3} in this case.
/// Precondition: The access path must be valid for this memory object's type.
void setIndexedElement(ArrayRef<unsigned> accessPath,
SymbolicValue newElement,
SymbolicValueAllocator &allocator);
const Type type;
SymbolicValue value;
SymbolicValueMemoryObject(Type type, SymbolicValue value)
: type(type), value(value) {}
SymbolicValueMemoryObject(const SymbolicValueMemoryObject &) = delete;
void operator=(const SymbolicValueMemoryObject &) = delete;
using SymbolicClosureArgument = std::pair<SILValue, Optional<SymbolicValue>>;
/// Representation of a symbolic closure. A symbolic closure consists of a
/// SILFunction and an array of SIL values, corresponding to the captured
/// arguments, and (optional) symbolic values representing the constant values
/// of the captured arguments. The symbolic values are optional as it is not
/// necessary for every captured argument to be a constant, which enables
/// representing closures whose captured arguments are not compile-time
/// constants.
struct SymbolicClosure final
: private llvm::TrailingObjects<SymbolicClosure, SymbolicClosureArgument> {
friend class llvm::TrailingObjects<SymbolicClosure, SymbolicClosureArgument>;
SILFunction *target;
// The number of SIL values captured by the closure.
unsigned numCaptures;
// True iff there exists a captured argument whose constant value is not
// known.
bool hasNonConstantCaptures = true;
// A substitution map that partially maps the generic paramters of the
// applied function to the generic arguments of passed to the call.
SubstitutionMap substitutionMap;
// The closure instruction such as partial apply that resulted in this
// symbolic value. This is tracked to obtain SILType and other SIL-level
// information of the symbolic closure.
SingleValueInstruction *closureInst;
SymbolicClosure() = delete;
SymbolicClosure(const SymbolicClosure &) = delete;
SymbolicClosure(SILFunction *callee, unsigned numArguments,
SubstitutionMap substMap, SingleValueInstruction *inst,
bool nonConstantCaptures)
: target(callee), numCaptures(numArguments),
hasNonConstantCaptures(nonConstantCaptures), substitutionMap(substMap),
closureInst(inst) {}
static SymbolicClosure *create(SILFunction *callee,
ArrayRef<SymbolicClosureArgument> args,
SubstitutionMap substMap,
SingleValueInstruction *closureInst,
SymbolicValueAllocator &allocator);
ArrayRef<SymbolicClosureArgument> getCaptures() const {
return {getTrailingObjects<SymbolicClosureArgument>(), numCaptures};
// This is used by the llvm::TrailingObjects base class.
size_t numTrailingObjects(OverloadToken<SymbolicClosureArgument>) const {
return numCaptures;
SILFunction *getTarget() {
return target;
SingleValueInstruction *getClosureInst() { return closureInst; }
SILType getClosureType() { return closureInst->getType(); }
SubstitutionMap getCallSubstitutionMap() { return substitutionMap; }
bool hasOnlyConstantCaptures() { return !hasNonConstantCaptures; }
} // end namespace swift