| //===--- LayoutConstraint.cpp - Layout constraints types and APIs ---------===// |
| // |
| // This source file is part of the Swift.org 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 https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements APIs for layout constraints. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "swift/AST/ASTContext.h" |
| #include "swift/AST/Decl.h" |
| #include "swift/AST/Types.h" |
| |
| namespace swift { |
| |
| /// This helper function is typically used by the parser to |
| /// map a type name to a corresponding layout constraint if possible. |
| LayoutConstraint getLayoutConstraint(Identifier ID, ASTContext &Ctx) { |
| if (ID == Ctx.Id_TrivialLayout) |
| return LayoutConstraint::getLayoutConstraint( |
| LayoutConstraintKind::TrivialOfExactSize, 0, 0, Ctx); |
| |
| if (ID == Ctx.Id_TrivialAtMostLayout) |
| return LayoutConstraint::getLayoutConstraint( |
| LayoutConstraintKind::TrivialOfAtMostSize, 0, 0, Ctx); |
| |
| if (ID == Ctx.Id_RefCountedObjectLayout) |
| return LayoutConstraint::getLayoutConstraint( |
| LayoutConstraintKind::RefCountedObject, Ctx); |
| |
| if (ID == Ctx.Id_NativeRefCountedObjectLayout) |
| return LayoutConstraint::getLayoutConstraint( |
| LayoutConstraintKind::NativeRefCountedObject, Ctx); |
| |
| if (ID == Ctx.Id_ClassLayout) |
| return LayoutConstraint::getLayoutConstraint( |
| LayoutConstraintKind::Class, Ctx); |
| |
| if (ID == Ctx.Id_NativeClassLayout) |
| return LayoutConstraint::getLayoutConstraint( |
| LayoutConstraintKind::NativeClass, Ctx); |
| |
| return LayoutConstraint::getLayoutConstraint( |
| LayoutConstraintKind::UnknownLayout, Ctx); |
| } |
| |
| StringRef LayoutConstraintInfo::getName() const { |
| return getName(getKind()); |
| } |
| |
| StringRef LayoutConstraintInfo::getName(LayoutConstraintKind Kind) { |
| switch (Kind) { |
| case LayoutConstraintKind::UnknownLayout: |
| return "_UnknownLayout"; |
| case LayoutConstraintKind::Class: |
| return "AnyObject"; |
| case LayoutConstraintKind::NativeClass: |
| return "_NativeClass"; |
| case LayoutConstraintKind::RefCountedObject: |
| return "_RefCountedObject"; |
| case LayoutConstraintKind::NativeRefCountedObject: |
| return "_NativeRefCountedObject"; |
| case LayoutConstraintKind::Trivial: |
| return "_Trivial"; |
| case LayoutConstraintKind::TrivialOfAtMostSize: |
| return "_TrivialAtMost"; |
| case LayoutConstraintKind::TrivialOfExactSize: |
| return "_Trivial"; |
| } |
| |
| llvm_unreachable("Unhandled LayoutConstraintKind in switch."); |
| } |
| |
| /// Uniquing for the LayoutConstraintInfo. |
| void LayoutConstraintInfo::Profile(llvm::FoldingSetNodeID &ID, |
| LayoutConstraintKind Kind, |
| unsigned SizeInBits, |
| unsigned Alignment) { |
| ID.AddInteger((unsigned)Kind); |
| ID.AddInteger(SizeInBits); |
| ID.AddInteger(Alignment); |
| } |
| |
| bool LayoutConstraintInfo::isKnownLayout(LayoutConstraintKind Kind) { |
| return Kind != LayoutConstraintKind::UnknownLayout; |
| } |
| |
| bool LayoutConstraintInfo::isFixedSizeTrivial(LayoutConstraintKind Kind) { |
| return Kind == LayoutConstraintKind::TrivialOfExactSize; |
| } |
| |
| bool LayoutConstraintInfo::isKnownSizeTrivial(LayoutConstraintKind Kind) { |
| return Kind > LayoutConstraintKind::UnknownLayout && |
| Kind < LayoutConstraintKind::Trivial; |
| } |
| |
| bool LayoutConstraintInfo::isAddressOnlyTrivial(LayoutConstraintKind Kind) { |
| return Kind == LayoutConstraintKind::Trivial; |
| } |
| |
| bool LayoutConstraintInfo::isTrivial(LayoutConstraintKind Kind) { |
| return Kind > LayoutConstraintKind::UnknownLayout && |
| Kind <= LayoutConstraintKind::Trivial; |
| } |
| |
| bool LayoutConstraintInfo::isRefCountedObject(LayoutConstraintKind Kind) { |
| return Kind == LayoutConstraintKind::RefCountedObject; |
| } |
| |
| bool LayoutConstraintInfo::isNativeRefCountedObject(LayoutConstraintKind Kind) { |
| return Kind == LayoutConstraintKind::NativeRefCountedObject; |
| } |
| |
| bool LayoutConstraintInfo::isAnyRefCountedObject(LayoutConstraintKind Kind) { |
| return isRefCountedObject(Kind) || isNativeRefCountedObject(Kind); |
| } |
| |
| bool LayoutConstraintInfo::isClass(LayoutConstraintKind Kind) { |
| return Kind == LayoutConstraintKind::Class || |
| Kind == LayoutConstraintKind::NativeClass; |
| } |
| |
| bool LayoutConstraintInfo::isNativeClass(LayoutConstraintKind Kind) { |
| return Kind == LayoutConstraintKind::NativeClass; |
| } |
| |
| bool LayoutConstraintInfo::isRefCounted(LayoutConstraintKind Kind) { |
| return isAnyRefCountedObject(Kind) || isClass(Kind); |
| } |
| |
| bool LayoutConstraintInfo::isNativeRefCounted(LayoutConstraintKind Kind) { |
| return Kind == LayoutConstraintKind::NativeRefCountedObject || |
| Kind == LayoutConstraintKind::NativeClass; |
| } |
| |
| void *LayoutConstraintInfo::operator new(size_t bytes, const ASTContext &ctx, |
| AllocationArena arena, |
| unsigned alignment) { |
| return ctx.Allocate(bytes, alignment, arena); |
| } |
| |
| SourceRange LayoutConstraintLoc::getSourceRange() const { return getLoc(); } |
| |
| #define MERGE_LOOKUP(lhs, rhs) \ |
| mergeTable[int(lhs)][int(rhs)] |
| |
| // Shortcut for spelling the whole enumerator. |
| #define E(X) LayoutConstraintKind::X |
| #define MERGE_CONFLICT LayoutConstraintKind::UnknownLayout |
| |
| /// This is a 2-D table defining the merging rules for layout constraints. |
| /// It is indexed by means of LayoutConstraintKind. |
| /// mergeTable[i][j] tells the kind of a layout constraint is the result |
| /// of merging layout constraints of kinds 'i' and 'j'. |
| /// |
| /// Some of the properties of the merge table, where C is any type of layout |
| /// constraint: |
| /// UnknownLayout x C -> C |
| /// C x UnknownLayout -> C |
| /// C x C -> C |
| /// mergeTable[i][j] == mergeTable[j][i], i.e. the table is symmetric. |
| /// mergeTable[i][j] == UnknownLayout if merging layout constraints of kinds i |
| /// and j would result in a conflict. |
| static LayoutConstraintKind mergeTable[unsigned(E(LastLayout)) + |
| 1][unsigned(E(LastLayout)) + 1] = { |
| // Initialize the row for UnknownLayout. |
| {E(/* UnknownLayout */ UnknownLayout), |
| E(/* TrivialOfExactSize */ TrivialOfExactSize), |
| E(/* TrivialOfAtMostSize */ TrivialOfAtMostSize), E(/* Trivial */ Trivial), |
| E(/* Class */ Class), E(/* NativeClass */ NativeClass), |
| E(/* RefCountedObject*/ RefCountedObject), |
| E(/* NativeRefCountedObject */ NativeRefCountedObject)}, |
| |
| // Initialize the row for TrivialOfExactSize. |
| {E(/* UnknownLayout */ TrivialOfExactSize), |
| E(/* TrivialOfExactSize */ TrivialOfExactSize), MERGE_CONFLICT, |
| E(/* Trivial */ TrivialOfExactSize), MERGE_CONFLICT, MERGE_CONFLICT, |
| MERGE_CONFLICT, MERGE_CONFLICT}, |
| |
| // Initialize the row for TrivialOfAtMostSize. |
| {E(/* UnknownLayout */ TrivialOfAtMostSize), MERGE_CONFLICT, |
| E(/* TrivialOfAtMostSize */ TrivialOfAtMostSize), |
| E(/* Trivial */ TrivialOfAtMostSize), MERGE_CONFLICT, MERGE_CONFLICT, |
| MERGE_CONFLICT, MERGE_CONFLICT}, |
| |
| // Initialize the row for Trivial. |
| {E(/* UnknownLayout */ Trivial), |
| E(/* TrivialOfExactSize */ TrivialOfExactSize), |
| E(/* TrivialOfAtMostSize */ TrivialOfAtMostSize), E(/* Trivial */ Trivial), |
| MERGE_CONFLICT, MERGE_CONFLICT, MERGE_CONFLICT, MERGE_CONFLICT}, |
| |
| // Initialize the row for Class. |
| {E(/* UnknownLayout*/ Class), MERGE_CONFLICT, MERGE_CONFLICT, |
| MERGE_CONFLICT, E(/* Class */ Class), E(/* NativeClass */ NativeClass), |
| E(/* RefCountedObject */ Class), |
| E(/* NativeRefCountedObject */ NativeClass)}, |
| |
| // Initialize the row for NativeClass. |
| {E(/* UnknownLayout */ NativeClass), MERGE_CONFLICT, MERGE_CONFLICT, |
| MERGE_CONFLICT, E(/* Class */ NativeClass), |
| E(/* NativeClass */ NativeClass), E(/* RefCountedObject */ NativeClass), |
| E(/* NativeRefCountedObject */ NativeClass)}, |
| |
| // Initialize the row for RefCountedObject. |
| {E(/* UnknownLayout */ RefCountedObject), MERGE_CONFLICT, MERGE_CONFLICT, |
| MERGE_CONFLICT, E(/* Class */ Class), E(/* NativeClass */ NativeClass), |
| E(/* RefCountedObject */ RefCountedObject), |
| E(/* NativeRefCountedObject */ NativeRefCountedObject)}, |
| |
| // Initialize the row for NativeRefCountedObject. |
| {E(/* UnknownLayout */ NativeRefCountedObject), MERGE_CONFLICT, |
| MERGE_CONFLICT, MERGE_CONFLICT, E(/* Class */ NativeClass), |
| E(/* NativeClass */ NativeClass), |
| E(/* RefCountedObject */ NativeRefCountedObject), |
| E(/* NativeRefCountedObject*/ NativeRefCountedObject)}, |
| }; |
| |
| #undef E |
| |
| // Fixed-size trivial constraint can be combined with AtMostSize trivial |
| // constraint into a fixed-size trivial constraint, if |
| // fixed_size_layout.size <= at_most_size_layout.size and |
| // their alignment requirements are not contradicting. |
| // |
| // Only merges if LHS would become the result of the merge. |
| static LayoutConstraint |
| mergeKnownSizeTrivialConstraints(LayoutConstraint LHS, LayoutConstraint RHS) { |
| assert(LHS->isKnownSizeTrivial() && RHS->isKnownSizeTrivial()); |
| |
| // LHS should be fixed-size. |
| if (!LHS->isFixedSizeTrivial()) |
| return LayoutConstraint::getUnknownLayout(); |
| |
| // RHS should be at-most-size. |
| if (RHS->isFixedSizeTrivial()) |
| return LayoutConstraint::getUnknownLayout(); |
| |
| // Check that sizes are compatible, i.e. |
| // fixed_size_layout.size <= at_most_size_layout.size |
| if (LHS->getMaxTrivialSizeInBits() > RHS->getMaxTrivialSizeInBits()) |
| return LayoutConstraint::getUnknownLayout(); |
| |
| // Check alignments |
| |
| // Quick exit if at_most_size_layout does not care about the alignment. |
| if (!RHS->getAlignmentInBits()) |
| return LHS; |
| |
| // Check if fixed_size_layout.alignment is a multiple of |
| // at_most_size_layout.alignment. |
| if (LHS->getAlignmentInBits() && |
| LHS->getAlignmentInBits() % RHS->getAlignmentInBits() == 0) |
| return LHS; |
| |
| return LayoutConstraint::getUnknownLayout(); |
| } |
| |
| LayoutConstraint |
| LayoutConstraint::merge(LayoutConstraint Other) { |
| auto Self = *this; |
| |
| // If both constraints are the same, they are always equal. |
| if (Self == Other) |
| return Self; |
| |
| // TrivialOfExactSize and TrivialOfAtMostSize are a special case, |
| // because not only their kind, but their parameters need to be compared as |
| // well. |
| if (Self->isKnownSizeTrivial() && Other->isKnownSizeTrivial()) { |
| // If we got here, it means that the Self == Other check above has failed. |
| // And that could only happen if either the kinds are different or |
| // size/alignment parameters are different. |
| |
| // Try to merge fixed-size constraint with an at-most-size constraint, |
| // if possible. |
| LayoutConstraint MergedKnownSizeTrivial; |
| MergedKnownSizeTrivial = mergeKnownSizeTrivialConstraints(Self, Other); |
| if (MergedKnownSizeTrivial->isKnownLayout()) |
| return MergedKnownSizeTrivial; |
| |
| MergedKnownSizeTrivial = mergeKnownSizeTrivialConstraints(Other, Self); |
| if (MergedKnownSizeTrivial->isKnownLayout()) |
| return MergedKnownSizeTrivial; |
| |
| return LayoutConstraint::getUnknownLayout(); |
| } |
| |
| // Lookup in the mergeTable if this combination of layouts can be merged. |
| auto mergeKind = MERGE_LOOKUP(Self->getKind(), Other->getKind()); |
| // The merge table should be symmetric. |
| assert(mergeKind == MERGE_LOOKUP(Other->getKind(), Self->getKind())); |
| |
| // Merge is not possible, report a conflict. |
| if (mergeKind == LayoutConstraintKind::UnknownLayout) |
| return LayoutConstraint::getUnknownLayout(); |
| |
| if (Self->getKind() == mergeKind) |
| return Self; |
| |
| if (Other->getKind() == mergeKind) |
| return Other; |
| |
| // The result of the merge is not equal to any of the input constraints, e.g. |
| // Class x NativeRefCountedObject -> NativeClass. |
| return LayoutConstraint::getLayoutConstraint(mergeKind); |
| } |
| |
| LayoutConstraint |
| LayoutConstraint::getLayoutConstraint(LayoutConstraintKind Kind) { |
| assert(!LayoutConstraintInfo::isKnownSizeTrivial(Kind)); |
| switch(Kind) { |
| case LayoutConstraintKind::Trivial: |
| return LayoutConstraint(&LayoutConstraintInfo::TrivialConstraintInfo); |
| case LayoutConstraintKind::NativeClass: |
| return LayoutConstraint(&LayoutConstraintInfo::NativeClassConstraintInfo); |
| case LayoutConstraintKind::Class: |
| return LayoutConstraint(&LayoutConstraintInfo::ClassConstraintInfo); |
| case LayoutConstraintKind::NativeRefCountedObject: |
| return LayoutConstraint( |
| &LayoutConstraintInfo::NativeRefCountedObjectConstraintInfo); |
| case LayoutConstraintKind::RefCountedObject: |
| return LayoutConstraint( |
| &LayoutConstraintInfo::RefCountedObjectConstraintInfo); |
| case LayoutConstraintKind::UnknownLayout: |
| return LayoutConstraint(&LayoutConstraintInfo::UnknownLayoutConstraintInfo); |
| case LayoutConstraintKind::TrivialOfAtMostSize: |
| case LayoutConstraintKind::TrivialOfExactSize: |
| llvm_unreachable("Wrong layout constraint kind"); |
| } |
| } |
| |
| LayoutConstraint LayoutConstraint::getUnknownLayout() { |
| return LayoutConstraint(&LayoutConstraintInfo::UnknownLayoutConstraintInfo); |
| } |
| |
| LayoutConstraintInfo LayoutConstraintInfo::UnknownLayoutConstraintInfo; |
| |
| LayoutConstraintInfo LayoutConstraintInfo::RefCountedObjectConstraintInfo( |
| LayoutConstraintKind::RefCountedObject); |
| |
| LayoutConstraintInfo LayoutConstraintInfo::NativeRefCountedObjectConstraintInfo( |
| LayoutConstraintKind::NativeRefCountedObject); |
| |
| LayoutConstraintInfo LayoutConstraintInfo::ClassConstraintInfo( |
| LayoutConstraintKind::Class); |
| |
| LayoutConstraintInfo LayoutConstraintInfo::NativeClassConstraintInfo( |
| LayoutConstraintKind::NativeClass); |
| |
| LayoutConstraintInfo LayoutConstraintInfo::TrivialConstraintInfo( |
| LayoutConstraintKind::Trivial); |
| |
| } // end namespace swift |