/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef jit_OptimizationTracking_h
#define jit_OptimizationTracking_h

#include "mozilla/Maybe.h"

#include "jit/CompactBuffer.h"
#include "jit/CompileInfo.h"
#include "jit/JitAllocPolicy.h"
#include "js/TrackedOptimizationInfo.h"
#include "vm/TypeInference.h"

namespace js {

namespace jit {

struct NativeToTrackedOptimizations;

class OptimizationAttempt
{
    JS::TrackedStrategy strategy_;
    JS::TrackedOutcome outcome_;

  public:
    OptimizationAttempt(JS::TrackedStrategy strategy, JS::TrackedOutcome outcome)
      : strategy_(strategy),
        outcome_(outcome)
    { }

    void setOutcome(JS::TrackedOutcome outcome) { outcome_ = outcome; }
    bool succeeded() const { return outcome_ >= JS::TrackedOutcome::GenericSuccess; }
    bool failed() const { return outcome_ < JS::TrackedOutcome::GenericSuccess; }
    JS::TrackedStrategy strategy() const { return strategy_; }
    JS::TrackedOutcome outcome() const { return outcome_; }

    bool operator ==(const OptimizationAttempt& other) const {
        return strategy_ == other.strategy_ && outcome_ == other.outcome_;
    }
    bool operator !=(const OptimizationAttempt& other) const {
        return strategy_ != other.strategy_ || outcome_ != other.outcome_;
    }
    HashNumber hash() const {
        return (HashNumber(strategy_) << 8) + HashNumber(outcome_);
    }

    void writeCompact(CompactBufferWriter& writer) const;
};

typedef Vector<OptimizationAttempt, 4, JitAllocPolicy> TempOptimizationAttemptsVector;
typedef Vector<TypeSet::Type, 1, JitAllocPolicy> TempTypeList;

class UniqueTrackedTypes;

class OptimizationTypeInfo
{
    JS::TrackedTypeSite site_;
    MIRType mirType_;
    TempTypeList types_;

  public:
    OptimizationTypeInfo(OptimizationTypeInfo&& other)
      : site_(other.site_),
        mirType_(other.mirType_),
        types_(mozilla::Move(other.types_))
    { }

    OptimizationTypeInfo(TempAllocator& alloc, JS::TrackedTypeSite site, MIRType mirType)
      : site_(site),
        mirType_(mirType),
        types_(alloc)
    { }

    MOZ_MUST_USE bool trackTypeSet(TemporaryTypeSet* typeSet);
    MOZ_MUST_USE bool trackType(TypeSet::Type type);

    JS::TrackedTypeSite site() const { return site_; }
    MIRType mirType() const { return mirType_; }
    const TempTypeList& types() const { return types_; }

    bool operator ==(const OptimizationTypeInfo& other) const;
    bool operator !=(const OptimizationTypeInfo& other) const;

    HashNumber hash() const;

    MOZ_MUST_USE bool writeCompact(JSContext* cx, CompactBufferWriter& writer,
                                   UniqueTrackedTypes& uniqueTypes) const;
};

typedef Vector<OptimizationTypeInfo, 1, JitAllocPolicy> TempOptimizationTypeInfoVector;

// Tracks the optimization attempts made at a bytecode location.
class TrackedOptimizations : public TempObject
{
    friend class UniqueTrackedOptimizations;
    TempOptimizationTypeInfoVector types_;
    TempOptimizationAttemptsVector attempts_;
    uint32_t currentAttempt_;

  public:
    explicit TrackedOptimizations(TempAllocator& alloc)
      : types_(alloc),
        attempts_(alloc),
        currentAttempt_(UINT32_MAX)
    { }

    void clear() {
        types_.clear();
        attempts_.clear();
        currentAttempt_ = UINT32_MAX;
    }

    MOZ_MUST_USE bool trackTypeInfo(OptimizationTypeInfo&& ty);

    MOZ_MUST_USE bool trackAttempt(JS::TrackedStrategy strategy);
    void amendAttempt(uint32_t index);
    void trackOutcome(JS::TrackedOutcome outcome);
    void trackSuccess();

    bool matchTypes(const TempOptimizationTypeInfoVector& other) const;
    bool matchAttempts(const TempOptimizationAttemptsVector& other) const;

    void spew() const;
};

// Assigns each unique sequence of optimization attempts an index; outputs a
// compact table.
class UniqueTrackedOptimizations
{
  public:
    struct SortEntry
    {
        const TempOptimizationTypeInfoVector* types;
        const TempOptimizationAttemptsVector* attempts;
        uint32_t frequency;
    };
    typedef Vector<SortEntry, 4> SortedVector;

  private:
    struct Key
    {
        const TempOptimizationTypeInfoVector* types;
        const TempOptimizationAttemptsVector* attempts;

        typedef Key Lookup;
        static HashNumber hash(const Lookup& lookup);
        static bool match(const Key& key, const Lookup& lookup);
        static void rekey(Key& key, const Key& newKey) {
            key = newKey;
        }
    };

    struct Entry
    {
        uint8_t index;
        uint32_t frequency;
    };

    // Map of unique (TempOptimizationTypeInfoVector,
    // TempOptimizationAttemptsVector) pairs to indices.
    typedef HashMap<Key, Entry, Key> AttemptsMap;
    AttemptsMap map_;

    // TempOptimizationAttemptsVectors sorted by frequency.
    SortedVector sorted_;

  public:
    explicit UniqueTrackedOptimizations(JSContext* cx)
      : map_(cx),
        sorted_(cx)
    { }

    MOZ_MUST_USE bool init() { return map_.init(); }
    MOZ_MUST_USE bool add(const TrackedOptimizations* optimizations);

    MOZ_MUST_USE bool sortByFrequency(JSContext* cx);
    bool sorted() const { return !sorted_.empty(); }
    uint32_t count() const { MOZ_ASSERT(sorted()); return sorted_.length(); }
    const SortedVector& sortedVector() const { MOZ_ASSERT(sorted()); return sorted_; }
    uint8_t indexOf(const TrackedOptimizations* optimizations) const;
};

// A compact table of tracked optimization information. Pictorially,
//
//    +------------------------------------------------+
//    |  Region 1                                      |  |
//    |------------------------------------------------|  |
//    |  Region 2                                      |  |
//    |------------------------------------------------|  |-- PayloadR of list-of-list of
//    |               ...                              |  |   range triples (see below)
//    |------------------------------------------------|  |
//    |  Region M                                      |  |
//    +================================================+ <- IonTrackedOptimizationsRegionTable
//    | uint32_t numRegions_ = M                       |  |
//    +------------------------------------------------+  |
//    | Region 1                                       |  |
//    |   uint32_t regionOffset = size(PayloadR)       |  |
//    +------------------------------------------------+  |-- Table
//    |   ...                                          |  |
//    +------------------------------------------------+  |
//    | Region M                                       |  |
//    |   uint32_t regionOffset                        |  |
//    +================================================+
//    |  Optimization type info 1                      |  |
//    |------------------------------------------------|  |
//    |  Optimization type info 2                      |  |-- PayloadT of list of
//    |------------------------------------------------|  |   OptimizationTypeInfo in
//    |               ...                              |  |   order of decreasing frequency
//    |------------------------------------------------|  |
//    |  Optimization type info N                      |  |
//    +================================================+ <- IonTrackedOptimizationsTypesTable
//    | uint32_t numEntries_ = N                       |  |
//    +------------------------------------------------+  |
//    | Optimization type info 1                       |  |
//    |   uint32_t entryOffset = size(PayloadT)        |  |
//    +------------------------------------------------+  |-- Table
//    |   ...                                          |  |
//    +------------------------------------------------+  |
//    | Optimization type info N                       |  |
//    |   uint32_t entryOffset                         |  |
//    +================================================+
//    |  Optimization attempts 1                       |  |
//    |------------------------------------------------|  |
//    |  Optimization attempts 2                       |  |-- PayloadA of list of
//    |------------------------------------------------|  |   OptimizationAttempts in
//    |               ...                              |  |   order of decreasing frequency
//    |------------------------------------------------|  |
//    |  Optimization attempts N                       |  |
//    +================================================+ <- IonTrackedOptimizationsAttemptsTable
//    | uint32_t numEntries_ = N                       |  |
//    +------------------------------------------------+  |
//    | Optimization attempts 1                        |  |
//    |   uint32_t entryOffset = size(PayloadA)        |  |
//    +------------------------------------------------+  |-- Table
//    |   ...                                          |  |
//    +------------------------------------------------+  |
//    | Optimization attempts N                        |  |
//    |   uint32_t entryOffset                         |  |
//    +------------------------------------------------+
//
// Abstractly, each region in the PayloadR section is a list of triples of the
// following, in order of ascending startOffset:
//
//     (startOffset, endOffset, optimization attempts index)
//
// The range of [startOffset, endOffset) is the native machine code offsets
// for which the optimization attempts referred to by the index applies.
//
// Concretely, each region starts with a header of:
//
//     { startOffset : 32, endOffset : 32 }
//
// followed by an (endOffset, index) pair, then by delta-encoded variants
// triples described below.
//
// Each list of type infos in the PayloadT section is a list of triples:
//
//     (kind, MIR type, type set)
//
// The type set is separately in another vector, and what is encoded instead
// is the (offset, length) pair needed to index into that vector.
//
// Each list of optimization attempts in the PayloadA section is a list of
// pairs:
//
//     (strategy, outcome)
//
// Both tail tables for PayloadR and PayloadA use reverse offsets from the
// table pointers.

class IonTrackedOptimizationsRegion
{
    const uint8_t* start_;
    const uint8_t* end_;

    // Unpacked state.
    uint32_t startOffset_;
    uint32_t endOffset_;
    const uint8_t* rangesStart_;

    void unpackHeader();

  public:
    IonTrackedOptimizationsRegion(const uint8_t* start, const uint8_t* end)
      : start_(start), end_(end),
        startOffset_(0), endOffset_(0), rangesStart_(nullptr)
    {
        MOZ_ASSERT(start < end);
        unpackHeader();
    }

    // Offsets for the entire range that this region covers.
    //
    // This, as well as the offsets for the deltas, is open at the ending
    // address: [startOffset, endOffset).
    uint32_t startOffset() const { return startOffset_; }
    uint32_t endOffset() const { return endOffset_; }

    class RangeIterator
    {
        const uint8_t* cur_;
        const uint8_t* start_;
        const uint8_t* end_;

        uint32_t firstStartOffset_;
        uint32_t prevEndOffset_;

      public:
        RangeIterator(const uint8_t* start, const uint8_t* end, uint32_t startOffset)
          : cur_(start), start_(start), end_(end),
            firstStartOffset_(startOffset), prevEndOffset_(0)
        { }

        bool more() const { return cur_ < end_; }
        void readNext(uint32_t* startOffset, uint32_t* endOffset, uint8_t* index);
    };

    RangeIterator ranges() const { return RangeIterator(rangesStart_, end_, startOffset_); }

    // Find the index of tracked optimization info (e.g., type info and
    // attempts) at a native code offset.
    mozilla::Maybe<uint8_t> findIndex(uint32_t offset, uint32_t* entryOffsetOut) const;

    // For the variants below, S stands for startDelta, L for length, and I
    // for index. These were automatically generated from training on the
    // Octane benchmark.
    //
    // byte 1    byte 0
    // SSSS-SSSL LLLL-LII0
    //     startDelta max 127, length max 63, index max 3

    static const uint32_t ENC1_MASK = 0x1;
    static const uint32_t ENC1_MASK_VAL = 0x0;

    static const uint32_t ENC1_START_DELTA_MAX = 0x7f;
    static const uint32_t ENC1_START_DELTA_SHIFT = 9;

    static const uint32_t ENC1_LENGTH_MAX = 0x3f;
    static const uint32_t ENC1_LENGTH_SHIFT = 3;

    static const uint32_t ENC1_INDEX_MAX = 0x3;
    static const uint32_t ENC1_INDEX_SHIFT = 1;

    // byte 2    byte 1    byte 0
    // SSSS-SSSS SSSS-LLLL LLII-II01
    //     startDelta max 4095, length max 63, index max 15

    static const uint32_t ENC2_MASK = 0x3;
    static const uint32_t ENC2_MASK_VAL = 0x1;

    static const uint32_t ENC2_START_DELTA_MAX = 0xfff;
    static const uint32_t ENC2_START_DELTA_SHIFT = 12;

    static const uint32_t ENC2_LENGTH_MAX = 0x3f;
    static const uint32_t ENC2_LENGTH_SHIFT = 6;

    static const uint32_t ENC2_INDEX_MAX = 0xf;
    static const uint32_t ENC2_INDEX_SHIFT = 2;

    // byte 3    byte 2    byte 1    byte 0
    // SSSS-SSSS SSSL-LLLL LLLL-LIII IIII-I011
    //     startDelta max 2047, length max 1023, index max 255

    static const uint32_t ENC3_MASK = 0x7;
    static const uint32_t ENC3_MASK_VAL = 0x3;

    static const uint32_t ENC3_START_DELTA_MAX = 0x7ff;
    static const uint32_t ENC3_START_DELTA_SHIFT = 21;

    static const uint32_t ENC3_LENGTH_MAX = 0x3ff;
    static const uint32_t ENC3_LENGTH_SHIFT = 11;

    static const uint32_t ENC3_INDEX_MAX = 0xff;
    static const uint32_t ENC3_INDEX_SHIFT = 3;

    // byte 4    byte 3    byte 2    byte 1    byte 0
    // SSSS-SSSS SSSS-SSSL LLLL-LLLL LLLL-LIII IIII-I111
    //     startDelta max 32767, length max 16383, index max 255

    static const uint32_t ENC4_MASK = 0x7;
    static const uint32_t ENC4_MASK_VAL = 0x7;

    static const uint32_t ENC4_START_DELTA_MAX = 0x7fff;
    static const uint32_t ENC4_START_DELTA_SHIFT = 25;

    static const uint32_t ENC4_LENGTH_MAX = 0x3fff;
    static const uint32_t ENC4_LENGTH_SHIFT = 11;

    static const uint32_t ENC4_INDEX_MAX = 0xff;
    static const uint32_t ENC4_INDEX_SHIFT = 3;

    static bool IsDeltaEncodeable(uint32_t startDelta, uint32_t length) {
        MOZ_ASSERT(length != 0);
        return startDelta <= ENC4_START_DELTA_MAX && length <= ENC4_LENGTH_MAX;
    }

    static const uint32_t MAX_RUN_LENGTH = 100;

    static uint32_t ExpectedRunLength(const NativeToTrackedOptimizations* start,
                                      const NativeToTrackedOptimizations* end);

    static void ReadDelta(CompactBufferReader& reader, uint32_t* startDelta, uint32_t* length,
                          uint8_t* index);
    static void WriteDelta(CompactBufferWriter& writer, uint32_t startDelta, uint32_t length,
                           uint8_t index);
    static MOZ_MUST_USE bool WriteRun(CompactBufferWriter& writer,
                                      const NativeToTrackedOptimizations* start,
                                      const NativeToTrackedOptimizations* end,
                                      const UniqueTrackedOptimizations& unique);
};

class IonTrackedOptimizationsAttempts
{
    const uint8_t* start_;
    const uint8_t* end_;

  public:
    IonTrackedOptimizationsAttempts(const uint8_t* start, const uint8_t* end)
      : start_(start), end_(end)
    {
        // Cannot be empty.
        MOZ_ASSERT(start < end);
    }

    void forEach(JS::ForEachTrackedOptimizationAttemptOp& op);
};

struct IonTrackedTypeWithAddendum
{
    TypeSet::Type type;

    enum HasAddendum {
        HasNothing,
        HasAllocationSite,
        HasConstructor
    };
    HasAddendum hasAddendum;

    // If type is a type object and is tied to a site, the script and pc are
    // resolved early and stored below. This is done to avoid accessing the
    // compartment during profiling time.
    union {
        struct {
            JSScript* script;
            uint32_t offset;
        };
        JSFunction* constructor;
    };

    explicit IonTrackedTypeWithAddendum(TypeSet::Type type)
      : type(type),
        hasAddendum(HasNothing)
    { }

    IonTrackedTypeWithAddendum(TypeSet::Type type, JSScript* script, uint32_t offset)
      : type(type),
        hasAddendum(HasAllocationSite),
        script(script),
        offset(offset)
    { }

    IonTrackedTypeWithAddendum(TypeSet::Type type, JSFunction* constructor)
      : type(type),
        hasAddendum(HasConstructor),
        constructor(constructor)
    { }

    bool hasAllocationSite() const { return hasAddendum == HasAllocationSite; }
    bool hasConstructor() const { return hasAddendum == HasConstructor; }
};

typedef Vector<IonTrackedTypeWithAddendum, 1, SystemAllocPolicy> IonTrackedTypeVector;

class IonTrackedOptimizationsTypeInfo
{
    const uint8_t* start_;
    const uint8_t* end_;

  public:
    IonTrackedOptimizationsTypeInfo(const uint8_t* start, const uint8_t* end)
      : start_(start), end_(end)
    {
        // Can be empty; i.e., no type info was tracked.
    }

    bool empty() const { return start_ == end_; }

    // Unlike IonTrackedOptimizationAttempts,
    // JS::ForEachTrackedOptimizationTypeInfoOp cannot be used directly. The
    // internal API needs to deal with engine-internal data structures (e.g.,
    // TypeSet::Type) directly.
    //
    // An adapter is provided below.
    struct ForEachOp
    {
        virtual void readType(const IonTrackedTypeWithAddendum& tracked) = 0;
        virtual void operator()(JS::TrackedTypeSite site, MIRType mirType) = 0;
    };

    class ForEachOpAdapter : public ForEachOp
    {
        JS::ForEachTrackedOptimizationTypeInfoOp& op_;

      public:
        explicit ForEachOpAdapter(JS::ForEachTrackedOptimizationTypeInfoOp& op)
          : op_(op)
        { }

        void readType(const IonTrackedTypeWithAddendum& tracked) override;
        void operator()(JS::TrackedTypeSite site, MIRType mirType) override;
    };

    void forEach(ForEachOp& op, const IonTrackedTypeVector* allTypes);
};

template <class Entry>
class IonTrackedOptimizationsOffsetsTable
{
    uint32_t padding_;
    uint32_t numEntries_;
    uint32_t entryOffsets_[1];

  protected:
    const uint8_t* payloadEnd() const {
        return (uint8_t*)(this) - padding_;
    }

  public:
    uint32_t numEntries() const { return numEntries_; }
    uint32_t entryOffset(uint32_t index) const {
        MOZ_ASSERT(index < numEntries());
        return entryOffsets_[index];
    }

    Entry entry(uint32_t index) const {
        const uint8_t* start = payloadEnd() - entryOffset(index);
        const uint8_t* end = payloadEnd();
        if (index < numEntries() - 1)
            end -= entryOffset(index + 1);
        return Entry(start, end);
    }
};

class IonTrackedOptimizationsRegionTable
  : public IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsRegion>
{
  public:
    mozilla::Maybe<IonTrackedOptimizationsRegion> findRegion(uint32_t offset) const;

    const uint8_t* payloadStart() const { return payloadEnd() - entryOffset(0); }
};

typedef IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsAttempts>
    IonTrackedOptimizationsAttemptsTable;

typedef IonTrackedOptimizationsOffsetsTable<IonTrackedOptimizationsTypeInfo>
    IonTrackedOptimizationsTypesTable;

MOZ_MUST_USE bool
WriteIonTrackedOptimizationsTable(JSContext* cx, CompactBufferWriter& writer,
                                  const NativeToTrackedOptimizations* start,
                                  const NativeToTrackedOptimizations* end,
                                  const UniqueTrackedOptimizations& unique,
                                  uint32_t* numRegions, uint32_t* regionTableOffsetp,
                                  uint32_t* typesTableOffsetp, uint32_t* attemptsTableOffsetp,
                                  IonTrackedTypeVector* allTypes);

} // namespace jit
} // namespace js

#endif // jit_OptimizationTracking_h