lib/AST/LayoutConstraint.cpp - third_party/swift - Git at Google

 //===--- 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");
   }
   llvm_unreachable("unhandled 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
	//===--- 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");
	}
	llvm_unreachable("unhandled 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