alias-analysis.h

/*
   +----------------------------------------------------------------------+
   | HipHop for PHP                                                       |
   +----------------------------------------------------------------------+
   | Copyright (c) 2010-2016 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_ALIAS_ANALYSIS_H_
#define incl_HPHP_ALIAS_ANALYSIS_H_

#include <bitset>
#include <string>
#include <cstdint>

#include "hphp/util/sparse-id-containers.h"
#include "hphp/runtime/vm/jit/containers.h"
#include "hphp/runtime/vm/jit/alias-class.h"
#include "hphp/runtime/vm/jit/cfg.h"

namespace HPHP { namespace jit {

struct IRUnit;

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

/*
 * Sets of abstract locations tracked by AliasAnalysis come in ALocBits.
 *
 * Right now we have a static maximum number of tracked locations---passes
 * using information from this module must be conservative about locations that
 * aren't assigned an id.  (E.g. via calls to may_alias in AliasAnalysis.)
 */
constexpr uint32_t kMaxTrackedALocs = 128;
using ALocBits = std::bitset<kMaxTrackedALocs>;

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

struct ALocMeta {
  uint32_t index;      // id assigned to this location
  ALocBits conflicts;  // flow-insensitive may-alias set, without self
};

/*
 * Information about various abstract locations an IR unit may be concerned
 * with.  See collect_aliases.
 */
struct AliasAnalysis {
  explicit AliasAnalysis(const IRUnit&);

  AliasAnalysis(const AliasAnalysis&) = delete;
  AliasAnalysis(AliasAnalysis&&) = default;
  AliasAnalysis& operator=(const AliasAnalysis&) = delete;
  AliasAnalysis& operator=(AliasAnalysis&&) = default;

  /*
   * Bidirectional map from alias classes to metadata about that abstract
   * memory location, primarily an assigned id.  There is also an inverse map
   * from id to the metadata structure.
   *
   * Two different alias classes in this map should not alias each other.  If
   * an alias class contains multiple locations (e.g., a range of stack slots,
   * multiple frame locals), we need to use multiple bits in this map.
   *
   * The keyed locations in this map take their canonical form.  You should use
   * canonicalize before doing lookups.
   */
  jit::hash_map<AliasClass,ALocMeta,AliasClass::Hash> locations;
  jit::vector<ALocMeta> locations_inv;

  /*
   * If an AStack covers multiple locations, it will have an entry in this
   * map. It is OK if not all locations covered by the AStack are tracked. We
   * only store the tracked subset here.
   */
  jit::hash_map<AliasClass,ALocBits,AliasClass::Hash> stack_ranges;

  /*
   * Similar to `stack_ranges', if an AFrame covers multiple locations, it will
   * have an entry in this map.
   */
  jit::hash_map<AliasClass,ALocBits,AliasClass::Hash> local_sets;

  /*
   * Short-hand to find an alias class in the locations map, or get folly::none
   * if the alias class wasn't assigned an ALocMeta structure.
   */
  folly::Optional<ALocMeta> find(AliasClass) const;

  /*
   * Several larger sets of locations, we have a set of all the ids assigned to
   * properties, elemIs, frame locals, etc.  This is used by may_alias below.
   */
  ALocBits all_props;
  ALocBits all_elemIs;
  ALocBits all_frame;
  ALocBits all_stack;
  ALocBits all_ref;
  ALocBits all_iterPos;
  ALocBits all_iterBase;

  /*
   * Return the number of distinct locations we're tracking by id
   */
  size_t count() const { return locations_inv.size(); }

  /*
   * Return a set of locations that we've assigned ids to that may alias a
   * given AliasClass.  Note that (as usual) memory locations we haven't
   * assigned bits to may still be affected, but this module only reports
   * effects on locations assigned bits.
   *
   * This function may conservatively return more bits than actually may
   * overlap `acls'.
   */
  ALocBits may_alias(AliasClass acls) const;

  /*
   * Return a set of locations that we've assigned ids to that are definitely
   * contained in `acls'.  This function may conservatively return a smaller
   * set of bits: every bit that is set in the returned ALocBits is contained
   * in `acls', but there may be locations contained in `acls' that don't have
   * a bit set in the returned vector. As a consequence of this, any caller of
   * expand() must produce correct (but potentially suboptimal) results if
   * expand is hardcoded to always return an empty bitset.
   *
   * This should generally be used with AliasClasses that are exhaustive,
   * must-style information.  That is, AliasClasses that should be interpreted
   * as referring to every point they contain.  Right now, the primary example
   * of that sort of AliasClasses is the class of locations in `kills' sets in
   * certain memory effects structs: these sets indicate every location inside
   * the class is affected.
   *
   * Right now, this function will work for specific AliasClasses we've
   * assigned ids---for larger classes, it only supports stack ranges observed
   * during alias collection, AFrameAny, and some cases of unions of those---if
   * you need more to work, the implementation will need some improvements.
   */
  ALocBits expand(AliasClass acls) const;

  /*
   * Sets of alias classes that are used by expand().
   */
  jit::hash_map<AliasClass,ALocBits,AliasClass::Hash> stk_expand_map;

  /*
   * Map from frame SSATmp ids to the location bits for all of the frame's
   * locals.
   */
  jit::sparse_idptr_map<SSATmp,ALocBits> per_frame_bits;
};

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

/*
 * Perform a flow-insensitive analysis on the supplied blocks, collecting
 * possibly distinct abstract memory locations that are explicitly referenced,
 * and assigning them ids and may-alias sets.  Only certain types of locations
 * are assigned ids, based on whether it maps to an AliasClass that that passes
 * can currently plausibly optimize (because it is sufficiently concrete).
 *
 * Note: it is fine to continue to reuse one AliasAnalysis structure after
 * mutating the IR, because the information it contains is both
 * flow-insensitive and conservative.  That is: if you change the IR to
 * reference new abstract memory locations, the fact that AliasAnalysis didn't
 * know about it won't invalidate the things it knows about (and the general
 * may_alias function will still work on the new location).  Similarly,
 * removing references to locations or changing control flow won't invalidate
 * anything.
 */
AliasAnalysis collect_aliases(const IRUnit&, const BlockList&);

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

/*
 * Produce summary information for debug printing.
 */
std::string show(const AliasAnalysis&);
std::string show(ALocBits);

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

}}

#endif