StructLayout.h

//===--- StructLayout.h - Structure layout ----------------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file defines some routines that are useful for performing
// structure layout.
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_IRGEN_STRUCTLAYOUT_H
#define SWIFT_IRGEN_STRUCTLAYOUT_H

#include "llvm/ADT/ArrayRef.h"
#include "swift/Basic/ClusteredBitVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Twine.h"
#include "IRGen.h"

namespace llvm {
  class Constant;
  class StructType;
  class Type;
  class Value;
}

namespace swift {
namespace irgen {
  class Address;
  class IRGenFunction;
  class IRGenModule;
  class TypeInfo;

/// An algorithm for laying out a structure.
enum class LayoutStrategy {
  /// Compute an optimal layout;  there are no constraints at all.
  Optimal,

  /// The 'universal' strategy: all modules must agree on the layout.
  Universal
};

/// The kind of object being laid out.
enum class LayoutKind {
  /// A non-heap object does not require a heap header.
  NonHeapObject,

  /// A heap object is destined to be allocated on the heap and must
  /// be emitted with the standard heap header.
  HeapObject,
};

class NonFixedOffsetsImpl;

/// The type to pass around for non-fixed offsets.
typedef Optional<NonFixedOffsetsImpl*> NonFixedOffsets;

/// An abstract class for determining non-fixed offsets.
class NonFixedOffsetsImpl {
protected:
  virtual ~NonFixedOffsetsImpl() = default;
public:
  /// Return the offset (in bytes, as a size_t) of the element with
  /// the given index.
  virtual llvm::Value *getOffsetForIndex(IRGenFunction &IGF,
                                         unsigned index) = 0;

  operator NonFixedOffsets() { return NonFixedOffsets(this); }
};

/// An element layout is the layout for a single element of some sort
/// of aggregate structure.
class ElementLayout {
public:
  enum class Kind {
    /// The element is known to require no storage in the aggregate.
    Empty,

    /// The element can be positioned at a fixed offset within the
    /// aggregate.
    Fixed,

    /// The element cannot be positioned at a fixed offset within the
    /// aggregate.
    NonFixed,

    /// The element is an object lacking a fixed size but located at
    /// offset zero.  This is necessary because LLVM forbids even a
    /// 'gep 0' on an unsized type.
    InitialNonFixedSize
  };

private:
  enum : unsigned { IncompleteKind  = 4 };

  /// The swift type information for this element.
  const TypeInfo *Type;

  /// The offset in bytes from the start of the struct.
  unsigned ByteOffset;

  /// The index of this element, either in the LLVM struct (if fixed)
  /// or in the non-fixed elements array (if non-fixed).
  unsigned Index : 28;

  /// Whether this element is known to be POD in the local resilience
  /// domain.
  unsigned IsPOD : 1;

  /// The kind of layout performed for this element.
  unsigned TheKind : 3;

  explicit ElementLayout(const TypeInfo &type)
    : Type(&type), TheKind(IncompleteKind) {}

  bool isCompleted() const {
    return (TheKind != IncompleteKind);
  }

public:
  static ElementLayout getIncomplete(const TypeInfo &type) {
    return ElementLayout(type);
  }

  void completeFrom(const ElementLayout &other) {
    assert(!isCompleted());
    TheKind = other.TheKind;
    IsPOD = other.IsPOD;
    ByteOffset = other.ByteOffset;
    Index = other.Index;
  }

  void completeEmpty(IsPOD_t isPOD, Size byteOffset) {
    TheKind = unsigned(Kind::Empty);
    IsPOD = unsigned(isPOD);
    // We still want to give empty fields an offset for use by things like
    // ObjC ivar emission. We use the first field in a class layout as the
    // instanceStart.
    ByteOffset = byteOffset.getValue();
    Index = 0; // make a complete write of the bitfield
  }

  void completeInitialNonFixedSize(IsPOD_t isPOD) {
    TheKind = unsigned(Kind::InitialNonFixedSize);
    IsPOD = unsigned(isPOD);
    Index = 0; // make a complete write of the bitfield
  }

  void completeFixed(IsPOD_t isPOD, Size byteOffset, unsigned structIndex) {
    TheKind = unsigned(Kind::Fixed);
    IsPOD = unsigned(isPOD);
    ByteOffset = byteOffset.getValue();
    Index = structIndex;

    assert(getByteOffset() == byteOffset);
  }

  /// Complete this element layout with a non-fixed offset.
  ///
  /// \param nonFixedElementIndex - the index into the elements array
  void completeNonFixed(IsPOD_t isPOD, unsigned nonFixedElementIndex) {
    TheKind = unsigned(Kind::NonFixed);
    IsPOD = unsigned(isPOD);
    Index = nonFixedElementIndex;
  }

  const TypeInfo &getType() const { return *Type; }

  Kind getKind() const {
    assert(isCompleted());
    return Kind(TheKind);
  }

  /// Is this element known to be empty?
  bool isEmpty() const {
    return getKind() == Kind::Empty;
  }

  /// Is this element known to be POD?
  IsPOD_t isPOD() const {
    assert(isCompleted());
    return IsPOD_t(IsPOD);
  }

  /// Given that this element has a fixed offset, return that offset in bytes.
  Size getByteOffset() const {
    assert(isCompleted() &&
           (getKind() == Kind::Fixed || getKind() == Kind::Empty));
    return Size(ByteOffset);
  }

  /// Given that this element has a fixed offset, return the index in
  /// the LLVM struct.
  unsigned getStructIndex() const {
    assert(isCompleted() && getKind() == Kind::Fixed);
    return Index;
  }

  /// Given that this element does not have a fixed offset, return its
  /// index in the nonfixed-elements array.
  unsigned getNonFixedElementIndex() const {
    assert(isCompleted() && getKind() == Kind::NonFixed);
    return Index;
  }

  Address project(IRGenFunction &IGF, Address addr,
                  NonFixedOffsets offsets,
                  const llvm::Twine &suffix = "") const;
};

/// A class for building a structure layout.
class StructLayoutBuilder {
protected:
  IRGenModule &IGM;
private:
  SmallVector<llvm::Type*, 8> StructFields;
  Size CurSize = Size(0);
  Alignment CurAlignment = Alignment(1);
  SpareBitVector CurSpareBits;
  unsigned NextNonFixedOffsetIndex = 0;
  bool IsFixedLayout = true;
  IsPOD_t IsKnownPOD = IsPOD;
  IsBitwiseTakable_t IsKnownBitwiseTakable = IsBitwiseTakable;
  IsFixedSize_t IsKnownAlwaysFixedSize = IsFixedSize;
public:
  StructLayoutBuilder(IRGenModule &IGM) : IGM(IGM) {}

  /// Add a swift heap header to the layout.  This must be the first
  /// call to the layout.
  void addHeapHeader();

  /// Add a number of fields to the layout.  The field layouts need
  /// only have the TypeInfo set; the rest will be filled out.
  ///
  /// Returns true if the fields may have increased the storage
  /// requirements of the layout.
  bool addFields(llvm::MutableArrayRef<ElementLayout> fields,
                 LayoutStrategy strategy);

  /// Return whether the layout is known to be empty.
  bool empty() const { return IsFixedLayout && CurSize == Size(0); }

  /// Return the current set of fields.
  ArrayRef<llvm::Type *> getStructFields() const { return StructFields; }

  /// Return whether the structure has a fixed-size layout.
  bool isFixedLayout() const { return IsFixedLayout; }

  /// Return whether the structure is known to be POD in the local
  /// resilience scope.
  IsPOD_t isPOD() const { return IsKnownPOD; }

  /// Return whether the structure is known to be bitwise-takable in the local
  /// resilience scope.
  IsBitwiseTakable_t isBitwiseTakable() const {
    return IsKnownBitwiseTakable;
  }

  /// Return whether the structure is known to be fixed-size in all
  /// resilience scopes.
  IsFixedSize_t isAlwaysFixedSize() const {
    return IsKnownAlwaysFixedSize;
  }

  /// Return the size of the structure built so far.
  Size getSize() const { return CurSize; }

  /// Return the alignment of the structure built so far.
  Alignment getAlignment() const { return CurAlignment; }
  
  /// Return the spare bit mask of the structure built so far.
  const SpareBitVector &getSpareBits() const { return CurSpareBits; }

  /// Return the spare bit mask of the structure built so far.
  SpareBitVector &getSpareBits() { return CurSpareBits; }

  /// Build the current elements as a new anonymous struct type.
  llvm::StructType *getAsAnonStruct() const;

  /// Build the current elements as a new anonymous struct type.
  void setAsBodyOfStruct(llvm::StructType *type) const;

private:
  void addFixedSizeElement(ElementLayout &elt);
  void addNonFixedSizeElement(ElementLayout &elt);
  void addEmptyElement(ElementLayout &elt);

  void addElementAtFixedOffset(ElementLayout &elt);
  void addElementAtNonFixedOffset(ElementLayout &elt);
  void addNonFixedSizeElementAtOffsetZero(ElementLayout &elt);
};

/// Apply layout attributes such as @_alignment to the layout properties of a
/// type, diagnosing any problems with them.
void applyLayoutAttributes(IRGenModule &IGM,
                           CanType ty,
                           bool isFixedLayout,
                           /*inout*/ Alignment &alignment);

/// A struct layout is the result of laying out a complete structure.
class StructLayout {
  /// The statically-known minimum bound on the alignment.
  Alignment MinimumAlign;

  /// The statically-known minimum bound on the size.
  Size MinimumSize;
  
  /// The statically-known spare bit mask.
  SpareBitVector SpareBits;

  /// Whether this layout is fixed in size.  If so, the size and
  /// alignment are exact.
  bool IsFixedLayout;

  IsPOD_t IsKnownPOD;
  IsBitwiseTakable_t IsKnownBitwiseTakable;
  IsFixedSize_t IsKnownAlwaysFixedSize = IsFixedSize;
  
  CanType ASTTy;
  llvm::Type *Ty;
  SmallVector<ElementLayout, 8> Elements;

public:
  /// Create a structure layout.
  ///
  /// \param strategy - how much leeway the algorithm has to rearrange
  ///   and combine the storage of fields
  /// \param kind - the kind of layout to perform, including whether the
  ///   layout must include the reference-counting header
  /// \param typeToFill - if present, must be an opaque type whose body
  ///   will be filled with this layout
  StructLayout(IRGenModule &IGM, CanType astTy,
               LayoutKind kind, LayoutStrategy strategy,
               ArrayRef<const TypeInfo *> fields,
               llvm::StructType *typeToFill = 0);

  /// Create a structure layout from a builder.
  StructLayout(const StructLayoutBuilder &builder,
               CanType astTy,
               llvm::Type *type,
               ArrayRef<ElementLayout> elements)
    : MinimumAlign(builder.getAlignment()),
      MinimumSize(builder.getSize()),
      SpareBits(builder.getSpareBits()),
      IsFixedLayout(builder.isFixedLayout()),
      IsKnownPOD(builder.isPOD()),
      IsKnownBitwiseTakable(builder.isBitwiseTakable()),
      IsKnownAlwaysFixedSize(builder.isAlwaysFixedSize()),
      ASTTy(astTy),
      Ty(type),
      Elements(elements.begin(), elements.end()) {}

  /// Return the element layouts.  This is parallel to the fields
  /// passed in the constructor.
  ArrayRef<ElementLayout> getElements() const { return Elements; }
  const ElementLayout &getElement(unsigned i) const { return Elements[i]; }
  
  llvm::Type *getType() const { return Ty; }
  Size getSize() const { return MinimumSize; }
  Alignment getAlignment() const { return MinimumAlign; }
  const SpareBitVector &getSpareBits() const { return SpareBits; }
  SpareBitVector &getSpareBits() { return SpareBits; }
  bool isKnownEmpty() const { return isFixedLayout() && MinimumSize.isZero(); }
  IsPOD_t isPOD() const { return IsKnownPOD; }
  IsBitwiseTakable_t isBitwiseTakable() const {
    return IsKnownBitwiseTakable;
  }
  IsFixedSize_t isAlwaysFixedSize() const {
    return IsKnownAlwaysFixedSize;
  }

  bool isFixedLayout() const { return IsFixedLayout; }
  llvm::Constant *emitSize(IRGenModule &IGM) const;
  llvm::Constant *emitAlignMask(IRGenModule &IGM) const;

  /// Bitcast the given pointer to this type.
  Address emitCastTo(IRGenFunction &IGF, llvm::Value *ptr,
                     const llvm::Twine &name = "") const;
};

Size getHeapHeaderSize(IRGenModule &IGM);

void addHeapHeaderToLayout(IRGenModule &IGM, Size &size, Alignment &align,
                           SmallVectorImpl<llvm::Type*> &fieldTypes);

/// Different policies for accessing a physical field.
enum class FieldAccess : uint8_t {
  /// Instance variable offsets are constant.
  ConstantDirect,
  
  /// Instance variable offsets must be loaded from "direct offset"
  /// global variables.
  NonConstantDirect,
  
  /// Instance variable offsets are kept in fields in metadata, but
  /// the offsets of those fields within the metadata are constant.
  ConstantIndirect,
  
  /// Instance variable offsets are kept in fields in metadata, and
  /// the offsets of those fields within the metadata must be loaded
  /// from "indirect offset" global variables.
  NonConstantIndirect
};

struct ClassLayout {
  /// Lazily-initialized array of all fragile stored properties in the class
  /// (including superclass stored properties).
  ArrayRef<VarDecl*> AllStoredProperties;
  /// Lazily-initialized array of all fragile stored properties inherited from
  /// superclasses.
  ArrayRef<VarDecl*> InheritedStoredProperties;
  /// Lazily-initialized array of all field access methods.
  ArrayRef<FieldAccess> AllFieldAccesses;
  /// Does the class metadata require dynamic initialization.
  bool MetadataRequiresDynamicInitialization;

  unsigned getFieldIndex(VarDecl *field) const {
    // FIXME: This is algorithmically terrible.
    auto found = std::find(AllStoredProperties.begin(),
                           AllStoredProperties.end(), field);
    assert(found != AllStoredProperties.end() && "didn't find field in type?!");
    return found - AllStoredProperties.begin();
  }
};

} // end namespace irgen
} // end namespace swift

#endif