hphp/runtime/vm/jit/alias-analysis.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #ifndef incl_HPHP_ALIAS_ANALYSIS_H_
  17 #define incl_HPHP_ALIAS_ANALYSIS_H_
  18
  19 #include <bitset>
  20 #include <string>
  21 #include <cstdint>
  22
  23 #include "hphp/runtime/vm/jit/containers.h"
  24 #include "hphp/runtime/vm/jit/alias-class.h"
  25 #include "hphp/runtime/vm/jit/cfg.h"
  26
  27 #include "hphp/util/sparse-id-containers.h"
  28
  29 namespace HPHP { namespace jit {
  30
  31 struct IRUnit;
  32
  33 //////////////////////////////////////////////////////////////////////
  34
  35 /*
  36  * Sets of abstract locations tracked by AliasAnalysis come in ALocBits.
  37  *
  38  * Right now we have a static maximum number of tracked locations---passes
  39  * using information from this module must be conservative about locations that
  40  * aren't assigned an id.  (E.g. via calls to may_alias in AliasAnalysis.)
  41  */
  42 constexpr uint32_t kMaxTrackedALocs = 256;
  43 using ALocBits = std::bitset<kMaxTrackedALocs>;
  44
  45 //////////////////////////////////////////////////////////////////////
  46
  47 struct ALocMeta {
  48   uint32_t index;      // id assigned to this location
  49   ALocBits conflicts;  // flow-insensitive may-alias set, without self
  50 };
  51
  52 /*
  53  * Information about various abstract locations an IR unit may be concerned
  54  * with.  See collect_aliases.
  55  */
  56 struct AliasAnalysis {
  57   explicit AliasAnalysis(const IRUnit&);
  58
  59   AliasAnalysis(const AliasAnalysis&) = delete;
  60   AliasAnalysis(AliasAnalysis&&) = default;
  61   AliasAnalysis& operator=(const AliasAnalysis&) = delete;
  62   AliasAnalysis& operator=(AliasAnalysis&&) = default;
  63
  64   /*
  65    * Bidirectional map from alias classes to metadata about that abstract
  66    * memory location, primarily an assigned id.  There is also an inverse map
  67    * from id to the metadata structure.
  68    *
  69    * Two different alias classes in this map should not alias each other.  If
  70    * an alias class contains multiple locations (e.g., a range of stack slots,
  71    * multiple frame locals), we need to use multiple bits in this map.
  72    *
  73    * The keyed locations in this map take their canonical form.  You should use
  74    * canonicalize before doing lookups.
  75    */
  76   jit::hash_map<AliasClass,ALocMeta,AliasClass::Hash> locations;
  77   jit::vector<ALocMeta> locations_inv;
  78
  79   using LocationMap = jit::hash_map<AliasClass,ALocBits,AliasClass::Hash>;
  80
  81   /*
  82    * If an AStack covers multiple locations, it will have an entry in this
  83    * map. It is OK if not all locations covered by the AStack are tracked. We
  84    * only store the tracked subset here.
  85    */
  86   LocationMap stack_ranges;
  87
  88   /*
  89    * Similar to `stack_ranges', if an AFrame covers multiple locations, it will
  90    * have an entry in this map.
  91    */
  92   LocationMap local_sets;
  93
  94   /*
  95    * Similar to `stack_ranges', if an AClsRefSlot covers multiple locations, it
  96    * will have an entry in this map.
  97    */
  98   LocationMap clsref_sets;
  99
 100   /*
 101    * Short-hand to find an alias class in the locations map, or get folly::none
 102    * if the alias class wasn't assigned an ALocMeta structure.
 103    */
 104   folly::Optional<ALocMeta> find(AliasClass) const;
 105
 106   /*
 107    * Several larger sets of locations, we have a set of all the ids assigned to
 108    * properties, elemIs, frame locals, etc.  This is used by may_alias below.
 109    */
 110   ALocBits all_props;
 111   ALocBits all_elemIs;
 112   ALocBits all_frame;
 113   ALocBits all_stack;
 114   ALocBits all_clsRefSlot;
 115   ALocBits all_rds;
 116   ALocBits all_ref;
 117   ALocBits all_iterPos;
 118   ALocBits all_iterBase;
 119   ALocBits all_cufIterFunc;
 120   ALocBits all_cufIterCtx;
 121   ALocBits all_cufIterInvName;
 122   ALocBits all_cufIterDynamic;
 123
 124   /*
 125    * Return the number of distinct locations we're tracking by id
 126    */
 127   size_t count() const { return locations_inv.size(); }
 128
 129   /*
 130    * Return a set of locations that we've assigned ids to that may alias a
 131    * given AliasClass.  Note that (as usual) memory locations we haven't
 132    * assigned bits to may still be affected, but this module only reports
 133    * effects on locations assigned bits.
 134    *
 135    * This function may conservatively return more bits than actually may
 136    * overlap `acls'.
 137    */
 138   ALocBits may_alias(AliasClass acls) const;
 139
 140   /*
 141    * Return a set of locations that we've assigned ids to that are definitely
 142    * contained in `acls'.  This function may conservatively return a smaller
 143    * set of bits: every bit that is set in the returned ALocBits is contained
 144    * in `acls', but there may be locations contained in `acls' that don't have
 145    * a bit set in the returned vector. As a consequence of this, any caller of
 146    * expand() must produce correct (but potentially suboptimal) results if
 147    * expand is hardcoded to always return an empty bitset.
 148    *
 149    * This should generally be used with AliasClasses that are exhaustive,
 150    * must-style information.  That is, AliasClasses that should be interpreted
 151    * as referring to every point they contain.  Right now, the primary example
 152    * of that sort of AliasClasses is the class of locations in `kills' sets in
 153    * certain memory effects structs: these sets indicate every location inside
 154    * the class is affected.
 155    *
 156    * Right now, this function will work for specific AliasClasses we've
 157    * assigned ids---for larger classes, it only supports stack ranges observed
 158    * during alias collection, AFrameAny, and some cases of unions of those---if
 159    * you need more to work, the implementation will need some improvements.
 160    */
 161   ALocBits expand(AliasClass acls) const;
 162
 163   /*
 164    * Sets of alias classes that are used by expand().
 165    */
 166   jit::hash_map<AliasClass,ALocBits,AliasClass::Hash> stk_expand_map;
 167 };
 168
 169 //////////////////////////////////////////////////////////////////////
 170
 171 /*
 172  * Perform a flow-insensitive analysis on the supplied blocks, collecting
 173  * possibly distinct abstract memory locations that are explicitly referenced,
 174  * and assigning them ids and may-alias sets.  Only certain types of locations
 175  * are assigned ids, based on whether it maps to an AliasClass that that passes
 176  * can currently plausibly optimize (because it is sufficiently concrete).
 177  *
 178  * Note: it is fine to continue to reuse one AliasAnalysis structure after
 179  * mutating the IR, because the information it contains is both
 180  * flow-insensitive and conservative.  That is: if you change the IR to
 181  * reference new abstract memory locations, the fact that AliasAnalysis didn't
 182  * know about it won't invalidate the things it knows about (and the general
 183  * may_alias function will still work on the new location).  Similarly,
 184  * removing references to locations or changing control flow won't invalidate
 185  * anything.
 186  */
 187 AliasAnalysis collect_aliases(const IRUnit&, const BlockList&);
 188
 189 //////////////////////////////////////////////////////////////////////
 190
 191 /*
 192  * Produce summary information for debug printing.
 193  */
 194 std::string show(const AliasAnalysis&);
 195 std::string show(ALocBits);
 196
 197 //////////////////////////////////////////////////////////////////////
 198
 199 }}
 200
 201 #endif