/*
   +----------------------------------------------------------------------+
   | HipHop for PHP                                                       |
   +----------------------------------------------------------------------+
   | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   +----------------------------------------------------------------------+
   | This source file is subject to version 3.01 of the PHP license,      |
   | that is bundled with this package in the file LICENSE, and is        |
   | available through the world-wide-web at the following url:           |
   | http://www.php.net/license/3_01.txt                                  |
   | If you did not receive a copy of the PHP license and are unable to   |
   | obtain it through the world-wide-web, please send a note to          |
   | license@php.net so we can mail you a copy immediately.               |
   +----------------------------------------------------------------------+
*/

#ifndef incl_HPHP_JIT_REGION_SELECTION_H_
#define incl_HPHP_JIT_REGION_SELECTION_H_

#include <memory>
#include <utility>
#include <vector>
#include <string>

#include <boost/container/flat_map.hpp>

#include <folly/Format.h>
#include <folly/Hash.h>
#include <folly/Optional.h>

#include "hphp/runtime/vm/jit/containers.h"
#include "hphp/runtime/vm/jit/location.h"
#include "hphp/runtime/vm/jit/stack-offsets.h"
#include "hphp/runtime/vm/jit/type.h"
#include "hphp/runtime/vm/jit/types.h"

#include "hphp/runtime/vm/func.h"
#include "hphp/runtime/vm/resumable.h"
#include "hphp/runtime/vm/srckey.h"

namespace HPHP { namespace jit {

struct ProfData;
struct TransCFG;

//////////////////////////////////////////////////////////////////////

enum class PGORegionMode {
  Hottrace, // Select a long region, using profile counters to guide the trace
  Hotblock, // Select a single block
  HotCFG,   // Select arbitrary CFG using profile counters to prune cold paths
  WholeCFG, // Select the entire CFG that has been profiled
};

//////////////////////////////////////////////////////////////////////

/*
 * RegionDesc is a description of a code region.  This includes the
 * list of blocks in the region, and also the list of control-flow
 * arcs within the region.
 *
 * It consists of a list of unique SrcKey ranges, with type
 * annotations that may come from profiling or other sources.
 *
 * The first block is the entry point, and the remaining blocks must
 * be sorted in a reverse post order.
 */
struct RegionDesc {
  struct Block;
  struct Arc;
  struct TypedLocation;
  struct GuardedLocation;
  using BlockPtr = std::shared_ptr<Block>;
  using BlockId = TransID;
  // BlockId Encoding:
  //   - Non-negative numbers are blocks that correspond
  //     to the start of a TransProfile translation, and therefore can
  //     be used to index into ProfData.
  //   - Negative numbers are used for other blocks, which correspond
  //     to blocks created by inlining and which don't correspond to
  //     the beginning of a profiling translation.
  using BlockIdSet = boost::container::flat_set<BlockId>;
  using BlockIdVec = std::vector<BlockId>;
  using BlockVec = std::vector<BlockPtr>;

  bool              empty() const;
  SrcKey            start() const;
  BlockPtr          entry() const;
  const BlockVec&   blocks() const;
  BlockPtr          block(BlockId id) const;
  const BlockIdSet& succs(BlockId id) const;
  const BlockIdSet& preds(BlockId id) const;
  bool              isExit(BlockId id) const;

  /*
   * Returns the set of blocks that got merged into block `id' by
   * guard relaxation.
   */
  const BlockIdSet& merged(BlockId id) const;

  const BlockIdSet* incoming() const;
  void incoming(BlockIdSet&& ids);

  /*
   * Modify this RegionDesc so that its list of blocks is sorted in a reverse
   * post order.
   */
  void sortBlocks();

  /*
   * Returns the last BC offset in the region that corresponds to the
   * function where the region starts.  This will normally be the offset
   * of the last instruction in the last block, except if the function
   * ends with an inlined call.  In this case, the offset of the
   * corresponding FCall* in the function that starts the region is
   * returned.
   *
   * Note that the notion of "last BC offset" only makes sense for
   * regions that are linear traces.
   */
  SrcKey            lastSrcKey() const;

  /*
   * Returns the profile count associated with block `bid'.  In case other
   * blocks have been merged into this block, the returned count includes the
   * counts of these other blocks as well.
   */
  int64_t           blockProfCount(BlockId bid) const;

  Block*            addBlock(SrcKey sk, int length, FPInvOffset spOffset);
  void              addBlock(BlockPtr newBlock);
  void              replaceBlock(BlockId bid, BlockPtr newBlock);
  void              deleteBlock(BlockId bid);
  BlockVec::iterator deleteBlock(RegionDesc::BlockVec::iterator it);
  void              renumberBlock(BlockId oldId, BlockId newId);
  void              addArc(BlockId src, BlockId dst);
  void              removeArc(BlockId src, BlockId dst);
  void              addMerged(BlockId fromId, BlockId intoId);
  folly::Optional<BlockId> prevRetrans(BlockId id) const;
  folly::Optional<BlockId> nextRetrans(BlockId id) const;
  void              clearPrevRetrans(BlockId id);
  void              clearNextRetrans(BlockId id);
  void              setNextRetrans(BlockId id, BlockId next);
  void              append(const RegionDesc&  other);
  void              prepend(const RegionDesc& other);
  void              chainRetransBlocks();
  uint32_t          instrSize() const;
  std::string       toString() const;

  const std::vector<Type>& inlineInputTypes() const {
    return m_inlineInputTypes;
  }
  Type inlineCtxType() const { return m_inlineCtxType; }

  void setInlineContext(Type ctx, const std::vector<Type>& args) {
    m_inlineCtxType = ctx;
    m_inlineInputTypes = args;
  }

  template<class Work>
  void              forEachArc(Work w) const;

private:
  struct BlockData {
    BlockPtr                 block;
    BlockIdSet               preds;
    BlockIdSet               succs;
    BlockIdSet               merged; // other blocks that got merged into this
    BlockId                  prevRetransId{kInvalidTransID};
    BlockId                  nextRetransId{kInvalidTransID};
    bool                     hasIncoming{false};
    explicit BlockData(BlockPtr b = nullptr) : block(b) {}
  };

  bool       hasBlock(BlockId id) const;
  BlockData& data(BlockId id);
  const BlockData& data(BlockId id) const {
    return const_cast<RegionDesc*>(this)->data(id);
  }
  void       copyBlocksFrom(const RegionDesc& other,
                            BlockVec::iterator where);
  void       copyArcsFrom(const RegionDesc& other);
  void       postOrderSort(RegionDesc::BlockId     bid,
                           RegionDesc::BlockIdSet& visited,
                           RegionDesc::BlockIdVec& outVec);

  std::vector<BlockPtr>             m_blocks;
  hphp_hash_map<BlockId, BlockData> m_data;

  // For regions selected for inlining, track the types of input arguments
  std::vector<Type> m_inlineInputTypes;
  Type m_inlineCtxType;
};

using RegionDescPtr = std::shared_ptr<RegionDesc>;
using RegionVec = std::vector<RegionDescPtr>;
using RegionSet = hphp_hash_set<
  RegionDescPtr,
  smart_pointer_hash<RegionDescPtr>
>;

struct RegionDesc::Arc {
  BlockId src;
  BlockId dst;
};

/*
 * A type for somewhere in the middle of or start of a region.
 *
 * All types annotated in the RegionDesc are things that need to be guarded on
 * or checked and then side-exited on. Types from ahead-of-time static analysis
 * are encoded in the bytecode stream.
 */
struct RegionDesc::TypedLocation {
  Location location;
  Type type;
};

inline bool operator==(const RegionDesc::TypedLocation& a,
                       const RegionDesc::TypedLocation& b) {
  return a.location == b.location && a.type == b.type;
}

/*
 * Information about a location that is guarded in a RegionDesc.
 * Includes the type and the DataTypeCategory.
 */
struct RegionDesc::GuardedLocation {
  Location location;
  Type type;
  DataTypeCategory category;
};

inline bool operator==(const RegionDesc::GuardedLocation& a,
                       const RegionDesc::GuardedLocation& b) {
  return a.location == b.location &&
         a.type     == b.type     &&
         a.category == b.category;
}

/*
 * PostConditions are known type information for locals and stack
 * locations at the end of profiling translation.
 *
 * These are kept for blocks that end a profiling translation in order
 * to enable better region selection.  This information is used to
 * prevent profiling translations with incompatible types from being
 * stitched together in a larger, optimizing translation.
 *
 * The PostConditions are kept in two distinct sets:
 *
 *   - the 'changed' set includes locations that may have been
 *     modified by the corresponding translation;
 *
 *   - the 'refined' set includes locations that are not modified but
 *     that some information is learned about them during the
 *     corresponding translation, typically due to type checks or
 *     asserts.
 */
using TypedLocations = std::vector<RegionDesc::TypedLocation>;

struct PostConditions {
  TypedLocations changed;
  TypedLocations refined;
};

/*
 * A basic block in the region, with type predictions for conditions
 * at various execution points, including at entry to the block.
 */
struct RegionDesc::Block {
  using TypedLocVec   = jit::vector<TypedLocation>;
  using GuardedLocVec = jit::vector<GuardedLocation>;
  using KnownFuncMap  = boost::container::flat_map<SrcKey,const Func*>;

  Block(BlockId id, const Func* func, ResumeMode resumeMode, bool hasThis,
        Offset start, int length, FPInvOffset initSpOff);

  Block& operator=(const Block&) = delete;

  /*
   * Accessors for the func, unit, length (in HHBC instructions), and
   * starting SrcKey of this Block.
   */
  BlockId     id()                const { return m_id; }
  const Unit* unit()              const { return m_func->unit(); }
  const Func* func()              const { return m_func; }
  SrcKey      start()             const {
    return SrcKey { m_func, m_start, m_resumeMode, m_hasThis };
  }
  SrcKey      last()              const {
    return SrcKey { m_func, m_last, m_resumeMode, m_hasThis };
  }
  int         length()            const { return m_length; }
  bool        empty()             const { return length() == 0; }
  bool        contains(SrcKey sk) const;
  FPInvOffset initialSpOffset()   const { return m_initialSpOffset; }
  TransID     profTransID()       const { return m_profTransID; }

  void setID(BlockId id)                  { m_id = id; }
  void setProfTransID(TransID ptid)       { m_profTransID = ptid; }
  void setInitialSpOffset(FPInvOffset sp) { m_initialSpOffset = sp; }

  /*
   * Increase the length of the Block by 1.
   */
  void addInstruction();

  /*
   * Remove all instructions after sk from the block.
   */
  void truncateAfter(SrcKey sk);

  /*
   * Add a predicted type to this block.  Multiple calls to this method should
   * be made in sorted order of the TypeLocation parameter.
   */
  void addPredicted(TypedLocation);

  /*
   * Add a precondition type to this block. Preconditions have no effects on
   * correctness, but entering a block with a known type that violates a
   * precondition is likely to result in a side exit after little to no
   * forward progress.
   */
  void addPreCondition(const GuardedLocation&);

  /*
   * Update the statically known Func*. It remains active until another is
   * specified, so pass nullptr to indicate that there is no longer a known
   * Func*.
   */
  void setKnownFunc(SrcKey, const Func*);

  /*
   * Set the post-conditions for this Block.
   */
  void setPostConds(const PostConditions&);

  /*
   * Clears the block's type pre-conditions.
   */
  void clearPreConditions();

  /*
   * The following getters return references to the metadata maps holding the
   * information added using the add* and set* methods above. The best way to
   * iterate over the information is using a MapWalker, since they're all
   * backed by a sorted map.
   */
  const TypedLocVec&    typePredictions()   const { return m_typePredictions;  }
  const GuardedLocVec&  typePreConditions() const { return m_typePreConditions;}
  const KnownFuncMap&   knownFuncs()        const { return m_knownFuncs;       }
  const PostConditions& postConds()         const { return m_postConds;        }

private:
  void checkInstructions() const;
  void checkInstruction(Op op) const;
  void checkMetadata() const;

private:
  BlockId          m_id;
  const Func*      m_func;
  const ResumeMode m_resumeMode;
  const bool       m_hasThis;
  const Offset     m_start;
  Offset           m_last;
  int              m_length;
  FPInvOffset      m_initialSpOffset;
  TransID          m_profTransID;
  TypedLocVec      m_typePredictions;
  GuardedLocVec    m_typePreConditions;
  KnownFuncMap     m_knownFuncs;
  PostConditions   m_postConds;
};

//////////////////////////////////////////////////////////////////////

/*
 * Information about the context in which we are selecting a region.
 *
 * Right now this is a source location, plus information about the
 * live types that we need to be compiling for.  There is no
 * implication that the region selected will necessarily specialize
 * for those types.
 */
struct RegionContext {
  struct LiveType;

  RegionContext(const Func* f, Offset bcOff, FPInvOffset spOff,
                ResumeMode rm, bool ht) :
      func(f), bcOffset(bcOff), spOffset(spOff), resumeMode(rm), hasThis(ht) {}

  const Func* func;
  Offset bcOffset;
  FPInvOffset spOffset;
  ResumeMode resumeMode;
  bool hasThis;
  jit::vector<LiveType> liveTypes;
};

/*
 * Live information about the type of a local or stack slot.
 */
struct RegionContext::LiveType {
  Location location;
  Type type;
};

//////////////////////////////////////////////////////////////////////

template<class Work> inline
void RegionDesc::forEachArc(Work w) const {
  for (auto& src : m_blocks) {
    auto srcId = src->id();
    for (auto dstId : succs(srcId)) {
      w(srcId, dstId);
    }
  }
}

//////////////////////////////////////////////////////////////////////

/*
 * Select a compilation region corresponding to the given context.
 * The shape of the region selected is controlled by
 * RuntimeOption::EvalJitRegionSelector.
 *
 * This function may return nullptr.
 *
 * For now this is hooked up in mcgen::translateWork, and
 * returning nullptr causes it to use the current level 0 tracelet
 * analyzer.  Eventually we'd like this to completely replace analyze.
 */
RegionDescPtr selectRegion(const RegionContext& context, TransKind kind);

/*
 * Select a compilation region based on profiling information.  This
 * is used in JitPGO mode.  Argument transId specifies the profiling
 * translation that triggered the profiling-based region selection.
 */
RegionDescPtr selectHotRegion(TransID transId);

/*
 * Select a compilation region as long as possible using the given context.
 * The region will be broken before the first instruction that attempts to
 * consume an input with an insufficiently precise type, or after most control
 * flow instructions.  This uses roughly the same heuristics as the old
 * analyze() framework.
 *
 * May return a null region if the given RegionContext doesn't have enough
 * information to translate at least one instruction.
 *
 * The `allowInlining' flag should be disabled when we are selecting a tracelet
 * whose shape will be analyzed by the inlining decider.
 */
RegionDescPtr selectTracelet(const RegionContext& ctx, TransKind kind,
                             int32_t maxBCInstrs, bool inlining = false);

struct HotTransContext {
  TransID tid;
  TransCFG* cfg;
  const ProfData* profData;
  int32_t maxBCInstrs;
  bool inlining{false};
  std::vector<Type>* inputTypes{nullptr};
};

/*
 * Select the hottest trace with the given context (starting at ctx.tid).
 */
RegionDescPtr selectHotTrace(HotTransContext& ctx);

/*
 * Create a region with the given context ctx (starting at ctx.tid) that
 * includes as much of the TransCFG as possible (in "wholecfg" mode), but that
 * can be pruned to eliminate cold/unlikely code as well (in "hotcfg" mode).
 * Returns in *truncated whether or not the region had to be truncated due to
 * the maximum bytecode limit.
 */
RegionDescPtr selectHotCFG(HotTransContext& ctx, bool* truncated = nullptr);

/*
 * Checks whether the type predictions at the beginning of block
 * satisfy the post-conditions in prevPostConds.
 */
bool preCondsAreSatisfied(const RegionDesc::BlockPtr& block,
                          const TypedLocations& prevPostConds);

/*
 * This function returns true for control-flow bytecode instructions that
 * are not supported in the middle of a region yet.
 */
bool breaksRegion(SrcKey sk);

/*
 * Creates regions covering all existing profile translations for func.
 */
RegionVec regionizeFunc(const Func* func, std::string& transCFGAnnot);

/*
 * Optimize the guards of `region' based on profiling data.
 *
 * The `region' must have its retranslation blocks already chained.
 */
void optimizeProfiledGuards(RegionDesc& region, const ProfData& profData);

/*
 * Optimize the guards of `region', optionally in `simple' mode (where
 * guards are only relaxed if they can be relaxed all the way to TGen).
 */
void optimizeGuards(RegionDesc& region, bool simple);

/*
 * Returns the PGO region selector to be used for the given `func'.
 * This depends on the value of RuntimeOption::EvalJitPGORegionSelector
 * and the given `func'.
 */
PGORegionMode pgoRegionMode(const Func& func);

/*
 * Functions to map BlockIds to the TransIDs used when the block was
 * profiled.
 */
bool    hasTransID(RegionDesc::BlockId blockId);
TransID getTransID(RegionDesc::BlockId blockId);

/*
 * Checks if the given region is well-formed.
 */
bool check(const RegionDesc& region, std::string& error);

/*
 * Debug stringification for various things.
 */
std::string show(RegionDesc::TypedLocation);
std::string show(const RegionDesc::GuardedLocation&);
std::string show(const RegionDesc::Block::GuardedLocVec&);
std::string show(const PostConditions&);
std::string show(RegionContext::LiveType);
std::string show(const RegionContext&);
std::string show(const RegionDesc::Block&);
std::string show(const RegionDesc&);

//////////////////////////////////////////////////////////////////////

}}

#endif
