LocalTypeData.h

//===--- LocalTypeData.h - Dominance-scoped type data -----------*- C++ -*-===//
//
// 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 defines types relating to the local caching of type data,
//  such as type metadata, value witness tables, and protocol witness tables.
//
//  Type data may be cached concretely, meaning that it was already fully
//  computed, or abstractly, meaning that we remember how to recreate it
//  but haven't actually done so yet.
//
//  Type data may be cached at different points within a function.
//  Some of these points may not dominate all possible use sites.
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_IRGEN_LOCALTYPEDATA_H
#define SWIFT_IRGEN_LOCALTYPEDATA_H

#include "LocalTypeDataKind.h"
#include "DominancePoint.h"
#include "MetadataPath.h"
#include "MetadataRequest.h"
#include "swift/AST/Type.h"
#include "llvm/ADT/STLExtras.h"
#include <utility>

namespace swift {
  class TypeBase;

namespace irgen {
  class DynamicMetadataRequest;
  class MetadataResponse;
  class FulfillmentMap;
  enum IsExact_t : bool;

/// A cache of local type data.
///
/// Basic design considerations:
///
///   - We want to be able to efficiently look up a key and find something.
///     Generally this will find something from the entry block.  We shouldn't
///     have to scan all the dominating points first.
///
///   - We don't expect to have multiple definitions for a key very often.
///     Therefore, given a collision, it should be okay to scan a list and
///     ask whether each is acceptable.
class LocalTypeDataCache {
public:
  static LocalTypeDataKey getKey(CanType type, LocalTypeDataKind index) {
    return LocalTypeDataKey{ type, index };
  }

private:
  struct CacheEntry {
    enum class Kind {
      Concrete, Abstract
    };

    DominancePoint DefinitionPoint;

  private:
    enum { KindMask = 0x1, ConditionalMask = 0x2 };
    llvm::PointerIntPair<CacheEntry*, 2, unsigned> NextAndFlags;

  public:
    Kind getKind() const {
      return Kind(NextAndFlags.getInt() & KindMask);
    }
    CacheEntry *getNext() const { return NextAndFlags.getPointer(); }
    void setNext(CacheEntry *next) { NextAndFlags.setPointer(next); }

    /// Return the abstract cost of evaluating this cache entry.
    OperationCost cost() const;

    /// Return the abstract cost of evaluating this cache entry.
    OperationCost costForRequest(LocalTypeDataKey key,
                                 DynamicMetadataRequest request) const;

    /// Return whether following the metadata path immediately produces
    /// a value that's statically known to satisfy the given request, or
    /// whether a separate dynamic check is required.
    bool immediatelySatisfies(LocalTypeDataKey key,
                              DynamicMetadataRequest request) const;

    /// Destruct and deallocate this cache entry.
    void erase() const;

    bool isConditional() const {
      return NextAndFlags.getInt() & ConditionalMask;
    }

  protected:
    CacheEntry(Kind kind, DominancePoint point, bool isConditional)
        : DefinitionPoint(point),
          NextAndFlags(nullptr,
                       unsigned(kind) | (isConditional ? ConditionalMask : 0)) {
    }
    ~CacheEntry() = default;
  };

  /// A concrete entry in the cache, which directly stores the desired value.
  struct ConcreteCacheEntry : CacheEntry {
    MetadataResponse Value;

    ConcreteCacheEntry(DominancePoint point, bool isConditional,
                       MetadataResponse value)
      : CacheEntry(Kind::Concrete, point, isConditional), Value(value) {}

    OperationCost cost() const { return OperationCost::Free; }
    OperationCost costForRequest(LocalTypeDataKey key,
                                 DynamicMetadataRequest request) const;

    bool immediatelySatisfies(LocalTypeDataKey key,
                              DynamicMetadataRequest request) const;

    static bool classof(const CacheEntry *entry) {
      return entry->getKind() == Kind::Concrete;
    }
  };

  /// A source of concrete data from which abstract cache entries can be
  /// derived.
  class AbstractSource {
  public:
    enum class Kind {
      TypeMetadata,
      ProtocolWitnessTable,
    };
  private:
    CanType Type;
    void *Conformance;
    MetadataResponse Value;

  public:
    explicit AbstractSource(CanType type, ProtocolConformanceRef conformance,
                            llvm::Value *value)
      : Type(type), Conformance(conformance.getOpaqueValue()),
        Value(MetadataResponse::forComplete(value)) {
      assert(Conformance != nullptr);
    }
    explicit AbstractSource(CanType type, MetadataResponse value)
      : Type(type), Conformance(nullptr), Value(value) {}

    Kind getKind() const {
      return (Conformance ? Kind::ProtocolWitnessTable : Kind::TypeMetadata);
    }

    CanType getType() const {
      return Type;
    }
    ProtocolConformanceRef getProtocolConformance() const {
      assert(Conformance && "not a protocol conformance");
      return ProtocolConformanceRef::getFromOpaqueValue(Conformance);
    }
    MetadataResponse getValue() const {
      return Value;
    }
  };

  /// An abstract entry in the cache, which requires some amount of
  /// non-trivial evaluation to derive the desired value.
  struct AbstractCacheEntry : CacheEntry {
    unsigned SourceIndex;
    unsigned State;
    MetadataPath Path;

    AbstractCacheEntry(DominancePoint point, bool isConditional,
                       unsigned sourceIndex, MetadataPath &&path,
                       MetadataState state)
      : CacheEntry(Kind::Abstract, point, isConditional),
        SourceIndex(sourceIndex), State(unsigned(state)),
        Path(std::move(path)) {}

    MetadataResponse follow(IRGenFunction &IGF, AbstractSource &source,
                            DynamicMetadataRequest request) const;

    /// Return the natural state of the metadata that would be produced
    /// by just following the path.  If the path ends in calling a type
    /// metadata accessor, it's okay to use MetadataState::Complete here
    /// because it's just as cheap to produce that as anything else.
    /// But if the path ends in just loading type metadata from somewhere,
    /// this should be the presumed state of that type metadata so that
    /// the costing accurately includes the cost of dynamically checking
    /// the state of that metadata.
    MetadataState getState() const {
      return MetadataState(State);
    }

    OperationCost cost() const { return Path.cost(); }
    OperationCost costForRequest(LocalTypeDataKey key,
                                 DynamicMetadataRequest request) const;

    bool immediatelySatisfies(LocalTypeDataKey key,
                              DynamicMetadataRequest request) const;

    static bool classof(const CacheEntry *entry) {
      return entry->getKind() == Kind::Abstract;
    }
  };

  /// The linked list of cache entries corresponding to a particular key.
  struct CacheEntryChain {
    CacheEntry *Root;

    explicit CacheEntryChain(CacheEntry *root = nullptr) : Root(root) {}

    CacheEntryChain(const CacheEntryChain &other) = delete;
    CacheEntryChain &operator=(const CacheEntryChain &other) = delete;

    CacheEntryChain(CacheEntryChain &&other) : Root(other.Root) {
      other.Root = nullptr;
    }
    CacheEntryChain &operator=(CacheEntryChain &&other) {
      Root = other.Root;
      other.Root = nullptr;
      return *this;
    }

    void push_front(CacheEntry *entry) {
      entry->setNext(Root);
      Root = entry;
    }

    void eraseEntry(CacheEntry *prev, CacheEntry *entry) {
      if (prev) {
        assert(prev->getNext() == entry);
        prev->setNext(entry->getNext());
      } else {
        assert(Root == entry);
        Root = entry->getNext();
      }
      entry->erase();
    }

    /// Delete the linked list.
    ~CacheEntryChain() {
      auto next = Root;
      while (next) {
        auto cur = next;
        next = cur->getNext();
        cur->erase();
      }
    }
  };

  llvm::DenseMap<LocalTypeDataKey, CacheEntryChain> Map;

  std::vector<AbstractSource> AbstractSources;

  void addAbstractForFulfillments(IRGenFunction &IGF,
                                  FulfillmentMap &&fulfillments,
                            llvm::function_ref<AbstractSource()> createSource);


public:
  LocalTypeDataCache() = default;
  LocalTypeDataCache(const LocalTypeDataCache &other) = delete;
  LocalTypeDataCache &operator=(const LocalTypeDataCache &other) = delete;

  /// Load the value from cache if possible.  This may require emitting
  /// code if the value is cached abstractly.
  MetadataResponse tryGet(IRGenFunction &IGF, LocalTypeDataKey key,
                          bool allowAbstract, DynamicMetadataRequest request);

  /// Add a new concrete entry to the cache at the given definition point.
  void addConcrete(DominancePoint point, bool isConditional,
                   LocalTypeDataKey key, MetadataResponse value) {
    key = key.getCachingKey();

    assert((key.Kind.isAnyTypeMetadata() ||
            value.isStaticallyKnownComplete()) &&
           "only type metadata can be added in a non-complete state");
    auto newEntry = new ConcreteCacheEntry(point, isConditional, value);
    Map[key].push_front(newEntry);
  }

  /// Add entries based on what can be fulfilled from the given type metadata.
  void addAbstractForTypeMetadata(IRGenFunction &IGF, CanType type,
                                  IsExact_t isExact, MetadataResponse value);

  void dump() const;

  // Private details for ConditionalDominanceScope.
  void eraseConditional(ArrayRef<LocalTypeDataKey> keys);
};

}
}

#endif