hphp/hhbbc/interp-state.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_HHBBC_INTERP_STATE_H_
  17 #define incl_HHBBC_INTERP_STATE_H_
  18
  19 #include <vector>
  20 #include <string>
  21 #include <map>
  22
  23 #include <boost/variant.hpp>
  24
  25 #include <folly/Optional.h>
  26
  27 #include "hphp/hhbbc/index.h"
  28 #include "hphp/hhbbc/misc.h"
  29 #include "hphp/hhbbc/type-system.h"
  30 #include "hphp/hhbbc/bc.h"
  31
  32 namespace HPHP { namespace HHBBC {
  33
  34 //////////////////////////////////////////////////////////////////////
  35
  36 struct ClassAnalysis;
  37
  38 //////////////////////////////////////////////////////////////////////
  39
  40 /*
  41  * Types of a FPI regions.  (What sort of function call is being
  42  * made.)
  43  */
  44 enum class FPIKind {
  45   Unknown,     // Nothing is known.
  46   CallableArr, // May be an ObjMeth or a ClsMeth.
  47   Func,        // Definitely a non-member function.
  48   Ctor,        // Definitely a constructor for an object.
  49   ObjMeth,     // Definitely a method on an object (possibly __call).
  50   ClsMeth,     // Definitely a static method on a class (possibly__callStatic).
  51   ObjInvoke,   // Closure invoke or __invoke on an object.
  52 };
  53
  54 /*
  55  * Information about a pre-live ActRec.  Part of state tracked in
  56  * State.
  57  */
  58 struct ActRec {
  59   explicit ActRec(FPIKind kind,
  60                   folly::Optional<res::Class> c = folly::none,
  61                   folly::Optional<res::Func> f = folly::none,
  62                   folly::Optional<res::Func> f2 = folly::none)
  63     : kind(kind)
  64     , cls(std::move(c))
  65     , func(std::move(f))
  66     , fallbackFunc(std::move(f2))
  67   {}
  68
  69   FPIKind kind;
  70   folly::Optional<res::Class> cls;
  71   folly::Optional<res::Func> func;
  72   // Possible fallback func if we cannot determine which will be called.
  73   folly::Optional<res::Func> fallbackFunc;
  74 };
  75
  76 /*
  77  * State of an iterator in the program.
  78  */
  79 struct UnknownIter {};
  80 struct TrackedIter { std::pair<Type,Type> kv; };
  81 using Iter = boost::variant< UnknownIter
  82                            , TrackedIter
  83                            >;
  84
  85 /*
  86  * Tag indicating what sort of thing contains the current member base.
  87  *
  88  * The base is always the unboxed version of the type, and its
  89  * location could be inside of a Ref.  So, for example, a base with
  90  * BaseLoc::Frame could be located inside of a Ref that is pointed
  91  * to by the Frame.  (We may want to distinguish these two cases at
  92  * some point if we start trying to track real information about
  93  * Refs, but not yet.)
  94  */
  95 enum class BaseLoc {
  96   /*
  97    * Base is in a number of possible places after an Elem op.  It
  98    * cannot possibly be in an object property (although it certainly
  99    * may alias one).  See miElem for details.  Not all post-elem ops
 100    * use this location (see LocalArrChain).
 101    *
 102    * If it is definitely in an array, the locTy in the Base will be
 103    * a subtype of TArr.
 104    */
 105   PostElem,
 106
 107   /*
 108    * Base is in possible locations after a Prop op.  This means it
 109    * possibly lives in a property on an object, but possibly not
 110    * (e.g. it could be a null in tvScratch).  See miProp for
 111    * details.
 112    *
 113    * If it is definitely known to be a property in an object, the
 114    * locTy in the Base will be a subtype of TObj.
 115    */
 116   PostProp,
 117
 118   /*
 119    * Known to be a static property on an object.  This is only
 120    * possible as an initial base.
 121    */
 122   StaticObjProp,
 123
 124   /*
 125    * The base is inside of a local that contains a specialized array
 126    * type, and the arrayChain is non-empty.
 127    *
 128    * When the location is set to this, the chain will continue as
 129    * long as we keep staying inside specialized array types.  If it
 130    * moves to something like a ?Arr type, we must leave the chain
 131    * when the base moves.
 132    */
 133   LocalArrChain,
 134
 135   /*
 136    * Known to be contained in the current frame as a local, as the
 137    * frame $this, by the evaluation stack, or inside $GLOBALS.  Only
 138    * possible as initial bases.
 139    */
 140   Frame,
 141   FrameThis,
 142   EvalStack,
 143   Global,
 144
 145   /*
 146    * If we've execute an operation that's known to fatal, we use
 147    * this BaseLoc.
 148    */
 149   Fataled,
 150 };
 151
 152 /*
 153  * Information about the current member base's type and location.
 154  */
 155 struct Base {
 156   Type type;
 157   BaseLoc loc;
 158
 159   /*
 160    * We also need to track effects of intermediate dims on the type
 161    * of the base.  So we have a type, name, and possibly associated
 162    * local for the base's container.
 163    *
 164    * For StaticObjProp, locName this is the name of the property if
 165    * known, or nullptr, and locTy is the type of the class
 166    * containing the static property.
 167    *
 168    * Similarly, if loc is PostProp, locName is the name of the
 169    * property if it was known, and locTy gives as much information
 170    * about the object type it is in.  (If we actually *know* it is
 171    * in an object, locTy will be a subtype of TObj.)
 172    */
 173   Type locTy;
 174   SString locName;
 175   LocalId local;
 176 };
 177
 178 // An element on the eval stack
 179 struct StackElem {
 180   Type type;
 181   // A local which is known to have an equivalent value to this stack value.
 182   LocalId equivLocal;
 183
 184   bool operator==(const StackElem& other) const {
 185     return type == other.type && equivLocal == other.equivLocal;
 186   }
 187 };
 188
 189 /*
 190  * A program state at a position in a php::Block.
 191  *
 192  * The `initialized' flag indicates whether the state knows anything.  All
 193  * other fields are invalid if a state is not initialized, and notably, after
 194  * all analysis has run, any blocks that still don't have initialized input
 195  * states are not reachable.
 196  *
 197  * The `unreachable' flag means we've produced this state from analysis, but
 198  * the program cannot reach this program position.  This flag has two uses:
 199  *
 200  *    o It allows us to determine arbitrary mid-block positions where code
 201  *      becomes unreachable, and eliminate that code in optimize.cpp.
 202  *
 203  *    o HHBC invariants can complicate removing unreachable code in FPI
 204  *      regions---see the rules in bytecode.specification.  Inside FPI regions,
 205  *      we still do abstract interpretation of the unreachable code, but this
 206  *      flag is used when merging states to allow the interpreter to analyze
 207  *      blocks that are unreachable without pessimizing states for reachable
 208  *      blocks that would've been their successors.
 209  *
 210  * One other note: having the interpreter visit blocks when they are
 211  * unreachable still potentially merges types into object properties that
 212  * aren't possible at runtime.  We're only doing this to handle FPI regions for
 213  * now, but it's not ideal.
 214  *
 215  */
 216 struct State {
 217   bool initialized = false;
 218   bool unreachable = false;
 219   bool thisAvailable = false;
 220   std::vector<Type> locals;
 221   std::vector<Iter> iters;
 222   std::vector<StackElem> stack;
 223   std::vector<ActRec> fpiStack;
 224
 225   /*
 226    * The current member base. Updated as we move through bytecodes representing
 227    * the operation.
 228    */
 229   Base base;
 230
 231   /*
 232    * Chains of member operations on array elements will all affect the type of
 233    * something further back in the member instruction.  Currently this is just
 234    * used for locals.  This vector tracks the base,key type pair that was used
 235    * at each stage.  See irgen-minstr.cpp:resolveArrayChain().
 236    */
 237   std::vector<std::pair<Type,Type>> arrayChain;
 238
 239   /*
 240    * Mapping of a local to another local which is known to have an equivalent
 241    * value.
 242    */
 243   std::vector<LocalId> equivLocals;
 244 };
 245
 246 /*
 247  * States are EqualityComparable (provided they are in-states for the
 248  * same block).
 249  */
 250 bool operator==(const ActRec&, const ActRec&);
 251 bool operator!=(const ActRec&, const ActRec&);
 252 bool operator==(const State&, const State&);
 253 bool operator!=(const State&, const State&);
 254
 255 /*
 256  * Return a copy of a State without copying either the evaluation
 257  * stack or FPI stack.
 258  */
 259 State without_stacks(const State&);
 260
 261 //////////////////////////////////////////////////////////////////////
 262
 263 /*
 264  * PropertiesInfo packages the PropState for private instance and
 265  * static properties, which is cross-block information collected in
 266  * CollectedInfo.
 267  *
 268  * During analysis the ClassAnalysis* is available and the PropState is
 269  * retrieved from there. However during optimization the ClassAnalysis is
 270  * not available and the PropState has to be retrieved off the Class in
 271  * the Index. In that case cls is nullptr and the PropState fields are
 272  * populated.
 273  */
 274 struct PropertiesInfo {
 275   PropertiesInfo(const Index&, Context, ClassAnalysis*);
 276
 277   PropState& privateProperties();
 278   PropState& privateStatics();
 279   const PropState& privateProperties() const;
 280   const PropState& privateStatics() const;
 281
 282 private:
 283   ClassAnalysis* const m_cls;
 284   PropState m_privateProperties;
 285   PropState m_privateStatics;
 286 };
 287
 288 //////////////////////////////////////////////////////////////////////
 289
 290 /*
 291  * Map from closure classes to types for each of their used vars.
 292  * Shows up in a few different interpreter structures.
 293  */
 294 using ClosureUseVarMap = std::map<
 295   borrowed_ptr<php::Class>,
 296   std::vector<Type>
 297 >;
 298
 299 /*
 300  * Merge the types in the vector as possible use vars for the closure
 301  * `clo' into the destination map.
 302  */
 303 void merge_closure_use_vars_into(ClosureUseVarMap& dst,
 304                                  borrowed_ptr<php::Class> clo,
 305                                  std::vector<Type>);
 306
 307 //////////////////////////////////////////////////////////////////////
 308
 309 /*
 310  * Area used for writing down any information that is collected across
 311  * a series of step operations (possibly cross block).
 312  */
 313 struct CollectedInfo {
 314   explicit CollectedInfo(const Index& index,
 315                          Context ctx,
 316                          ClassAnalysis* cls,
 317                          PublicSPropIndexer* publicStatics)
 318     : props{index, ctx, cls}
 319     , publicStatics{publicStatics}
 320     , mayUseVV{false}
 321   {}
 322
 323   ClosureUseVarMap closureUseTypes;
 324   PropertiesInfo props;
 325   PublicSPropIndexer* const publicStatics;
 326   bool mayUseVV;
 327 };
 328
 329 //////////////////////////////////////////////////////////////////////
 330
 331 /*
 332  * State merging functions, based on the union_of operation for types.
 333  *
 334  * These return true if the destination state changed.
 335  */
 336 bool merge_into(ActRec&, const ActRec&);
 337 bool merge_into(State&, const State&);
 338
 339 /*
 340  * State merging functions, based on the widening_union operation.
 341  * See analyze.cpp for details on when this is needed.
 342  */
 343 bool widen_into(PropState&, const PropState&);
 344 bool widen_into(State&, const State&);
 345
 346 //////////////////////////////////////////////////////////////////////
 347
 348 /*
 349  * Functions to show various aspects of interpreter state as strings.
 350  */
 351 std::string show(const ActRec& a);
 352 std::string property_state_string(const PropertiesInfo&);
 353 std::string state_string(const php::Func&, const State&);
 354
 355 //////////////////////////////////////////////////////////////////////
 356
 357 }}
 358
 359 #endif