hphp/compiler/analysis/alias_manager.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 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
  17 #ifndef incl_HPHP_ALIAS_MANAGER_H_
  18 #define incl_HPHP_ALIAS_MANAGER_H_
  19
  20 #include "hphp/compiler/expression/expression.h"
  21 #include <map>
  22 #include <set>
  23 #include <vector>
  24
  25 namespace HPHP {
  26 ///////////////////////////////////////////////////////////////////////////////
  27
  28 DECLARE_BOOST_TYPES(MethodStatement);
  29 DECLARE_BOOST_TYPES(SimpleVariable);
  30 DECLARE_BOOST_TYPES(ListAssignment);
  31 DECLARE_BOOST_TYPES(ArrayElementExpression);
  32
  33 class ControlFlowGraph;
  34
  35 class BucketMapEntry {
  36  public:
  37   BucketMapEntry() : m_num(0), m_next(0) {}
  38  public:
  39   ExpressionPtr find(ExpressionPtr e);
  40   void add(ExpressionPtr e);
  41   void clear();
  42   void beginScope();
  43   void endScope();
  44   void resetScope();
  45   void pop_back() { m_exprs.pop_back(); }
  46   ExpressionPtr back() { return m_exprs.back(); }
  47   ExpressionPtrList::iterator begin() { return m_exprs.begin(); }
  48   ExpressionPtrList::iterator end() { return m_exprs.end(); }
  49   ExpressionPtrList::reverse_iterator rbegin() { return m_exprs.rbegin(); }
  50   ExpressionPtrList::reverse_iterator rend() { return m_exprs.rend(); }
  51   bool isLast(ExpressionPtr e) { return *rbegin() == e; }
  52   bool isSubLast(ExpressionPtr e);
  53   size_t size() { return m_num; }
  54   void stash(size_t from, ExpressionPtrList &to);
  55   void import(ExpressionPtrList &from);
  56   void erase(ExpressionPtrList::reverse_iterator rit,
  57              ExpressionPtrList::reverse_iterator &end) {
  58     // the base of a reverse iterator points one beyond
  59     // the element the reverse iterator points to, so
  60     // decrement it...
  61     ExpressionPtrList::iterator it(--rit.base());
  62     // erasing an element /can/ invalidate the end
  63     // reverse_iterator, so fix it if necessary
  64     if (end.base() == it) end = rit;
  65     m_exprs.erase(it);
  66     // rit is still valid, and now (magically) points at
  67     // the next element... no need to return a new iterator.
  68     m_num--;
  69   }
  70   BucketMapEntry *next() const { return m_next; }
  71   void link(BucketMapEntry *&tail) {
  72     if (!m_next) {
  73       if (tail) {
  74         m_next = tail->m_next;
  75         tail->m_next = this;
  76       } else {
  77         m_next = this;
  78       }
  79       tail = this;
  80     }
  81   }
  82  private:
  83   ExpressionPtrList     m_exprs;
  84   std::vector<size_t>   m_stack;
  85   size_t                m_num;
  86   BucketMapEntry        *m_next;
  87 };
  88
  89 class AliasManager {
  90  public:
  91   enum { SameAccess, SameLValueAccess, InterfAccess,
  92     DisjointAccess, NotAccess };
  93
  94   explicit AliasManager(int opt);
  95   ~AliasManager();
  96
  97   void clear();
  98   void beginScope();
  99   void endScope();
 100   void resetScope();
 101   bool insertForDict(ExpressionPtr e);
 102   ExpressionPtr getCanonical(ExpressionPtr e);
 103
 104   void gatherInfo(AnalysisResultConstPtr ar, MethodStatementPtr m);
 105   int optimize(AnalysisResultConstPtr ar, MethodStatementPtr s);
 106   void finalSetup(AnalysisResultConstPtr ar, MethodStatementPtr m);
 107   int copyProp(MethodStatementPtr m);
 108
 109   void setChanged() {
 110     if (!m_noAdd) {
 111       m_changes++;
 112       m_scope->addUpdates(BlockScope::UseKindCaller);
 113     }
 114   }
 115
 116   static bool parseOptimizations(const std::string &optimizations,
 117                                  std::string &errs);
 118
 119   ControlFlowGraph *graph() { return m_graph; }
 120   int checkAnyInterf(ExpressionPtr rv, ExpressionPtr e, bool &isLoad,
 121                      int &depth, int &effects, bool forLval = false);
 122   bool hasWildRefs() const { return m_wildRefs; }
 123   bool couldBeAliased(SimpleVariablePtr sv);
 124
 125   AnalysisResultConstPtr getAnalysisResult() { return m_arp; }
 126  private:
 127
 128   int findInterf0(
 129     ExpressionPtr rv, bool isLoad,
 130     ExpressionPtr &rep,
 131     ExpressionPtrList::reverse_iterator begin,
 132     ExpressionPtrList::reverse_iterator end,
 133     int *flags = 0,
 134     bool allowLval = false, bool forLval = false,
 135     int depth = 0, int min_depth = 0,
 136     int max_depth = 0);
 137
 138   void setCanonPtrForArrayCSE(
 139       ExpressionPtr e,
 140       ExpressionPtr rep);
 141
 142   void doFinal(MethodStatementPtr m);
 143   enum { MaxBuckets = 0x10000 };
 144   enum { FallThrough, CondBranch, Branch, Converge };
 145   enum { NoCopyProp = 1, NoDeadStore = 2 };
 146   struct CondStackElem {
 147     explicit CondStackElem(size_t s = 0) : m_size(s), m_exprs() {}
 148     size_t              m_size;
 149     ExpressionPtrList   m_exprs;
 150   };
 151
 152   void performReferencedAndNeededAnalysis(MethodStatementPtr m);
 153   void insertTypeAssertions(AnalysisResultConstPtr ar, MethodStatementPtr m);
 154   void removeTypeAssertions(AnalysisResultConstPtr ar, MethodStatementPtr m);
 155
 156   typedef std::set<std::string> StringSet;
 157
 158   class LoopInfo {
 159   public:
 160     explicit LoopInfo(StatementPtr s);
 161
 162     StatementPtr m_stmt;
 163     StatementPtrVec m_inner;
 164     bool m_valid;
 165     StringSet m_candidates;
 166     StringSet m_excluded;
 167   };
 168
 169   typedef hphp_hash_map<unsigned, BucketMapEntry> BucketMap;
 170   typedef std::vector<CondStackElem> CondStack;
 171   typedef std::vector<LoopInfo> LoopInfoVec;
 172
 173   void mergeScope();
 174
 175   static void clearHelper(BucketMap::value_type &it);
 176   static void beginScopeHelper(BucketMap::value_type &it);
 177   static void endScopeHelper(BucketMap::value_type &it);
 178   static void resetScopeHelper(BucketMap::value_type &it);
 179
 180   void add(BucketMapEntry &em, ExpressionPtr e);
 181
 182   void dumpAccessChain();
 183   int testAccesses(ExpressionPtr e1, ExpressionPtr e2, bool forLval = false);
 184   void cleanRefs(ExpressionPtr rv,
 185                  ExpressionPtrList::reverse_iterator it,
 186                  ExpressionPtrList::reverse_iterator &end,
 187                  int depth);
 188   void cleanInterf(ExpressionPtr rv,
 189                    ExpressionPtrList::reverse_iterator it,
 190                    ExpressionPtrList::reverse_iterator &end,
 191                    int depth);
 192   void killLocals();
 193   bool okToKill(ExpressionPtr ep, bool killRef);
 194   int checkInterf(ExpressionPtr rv, ExpressionPtr e, bool &isLoad,
 195                   int &depth, int &effects, bool forLval = false);
 196   int findInterf(ExpressionPtr rv, bool isLoad, ExpressionPtr &rep,
 197                  int *flags = 0, bool allowLval = false);
 198   void applyAssign(ExpressionPtr lhs, ExpressionPtr rhs);
 199   void processAccessChain(ExpressionPtr e);
 200   void processAccessChainLA(ListAssignmentPtr e);
 201
 202   void canonicalizeKid(ConstructPtr e, ExpressionPtr kid, int i);
 203   int canonicalizeKid(ConstructPtr e, ConstructPtr kid, int i);
 204   ExpressionPtr canonicalizeNode(ExpressionPtr e, bool doAccessChains = false);
 205   ExpressionPtr canonicalizeNonNull(ExpressionPtr e);
 206   ExpressionPtr canonicalizeRecurNonNull(ExpressionPtr e);
 207   ExpressionPtr canonicalizeRecur(ExpressionPtr e);
 208   StatementPtr canonicalizeRecur(StatementPtr e, int &ret);
 209
 210   void invalidateChainRoots(StatementPtr s);
 211   void nullSafeDisableCSE(StatementPtr parent, ExpressionPtr kid);
 212   void disableCSE(StatementPtr s);
 213   void createCFG(MethodStatementPtr m);
 214   void deleteCFG();
 215
 216   int collectAliasInfoRecur(ConstructPtr cs, bool unused);
 217   void pushStringScope(StatementPtr s);
 218   void popStringScope(StatementPtr s);
 219   void stringOptsRecur(StatementPtr s);
 220   void stringOptsRecur(ExpressionPtr s, bool ok);
 221
 222   void beginInExpression(StatementPtr parent, ExpressionPtr kid);
 223   void endInExpression(StatementPtr requestor);
 224   bool isInExpression() const {
 225     assert((m_exprIdx >=  0 && m_exprParent) ||
 226            (m_exprIdx == -1 && !m_exprParent));
 227     return m_exprIdx != -1;
 228   }
 229
 230   /**
 231    * Take e and walk down the expression chain, marking all
 232    * interferences as "altered". It is assumed that e is
 233    * a store (has modifications)
 234    */
 235   void markAllLocalExprAltered(ExpressionPtr e);
 236
 237   BucketMapEntry            m_accessList;
 238   BucketMap                 m_bucketMap;
 239   BucketMapEntry            *m_bucketList;
 240
 241   CondStack                 m_stack;
 242
 243   unsigned                  m_nextID;
 244
 245   int                       m_changes;
 246   int                       m_replaced;
 247   bool                      m_wildRefs;
 248
 249   AnalysisResultConstPtr    m_arp;
 250   VariableTablePtr          m_variables;
 251
 252   LoopInfoVec               m_loopInfo;
 253
 254   std::string               m_returnVar;
 255   int                       m_nrvoFix;
 256
 257   int                       m_inCall;
 258   bool                      m_inlineAsExpr;
 259   bool                      m_noAdd;
 260   bool                      m_preOpt;
 261   bool                      m_postOpt;
 262   bool                      m_cleared;
 263   bool                      m_inPseudoMain;
 264   bool                      m_genAttrs;
 265   bool                      m_hasDeadStore;
 266   bool                      m_hasChainRoot;
 267   bool                      m_hasTypeAssertions;
 268   BlockScopeRawPtr          m_scope;
 269
 270   ControlFlowGraph          *m_graph;
 271   std::map<std::string,int> m_gidMap;
 272   std::map<std::string,SimpleVariablePtr> m_objMap;
 273
 274   ExpressionPtr             m_expr;
 275   int                       m_exprIdx;
 276   StatementPtr              m_exprParent;
 277   ExpressionPtrVec          m_exprBeginStack;
 278 };
 279
 280 ///////////////////////////////////////////////////////////////////////////////
 281 }
 282 #endif // incl_HPHP_ALIAS_MANAGER_H_