hphp/runtime/vm/jit/analysis.cpp

   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 #include "hphp/runtime/vm/jit/analysis.h"
  17
  18 #include "hphp/util/assertions.h"
  19 #include "hphp/runtime/vm/jit/ssa-tmp.h"
  20 #include "hphp/runtime/vm/jit/ir-instruction.h"
  21 #include "hphp/runtime/vm/jit/block.h"
  22 #include "hphp/runtime/vm/jit/id-set.h"
  23
  24 namespace HPHP { namespace jit {
  25
  26 //////////////////////////////////////////////////////////////////////
  27
  28 const SSATmp* canonical(const SSATmp* val) {
  29   return canonical(const_cast<SSATmp*>(val));
  30 }
  31
  32 SSATmp* canonical(SSATmp* value) {
  33   if (value == nullptr) return nullptr;
  34
  35   auto inst = value->inst();
  36
  37   while (inst->isPassthrough()) {
  38     value = inst->getPassthroughValue();
  39     inst = value->inst();
  40   }
  41   return value;
  42 }
  43
  44 //////////////////////////////////////////////////////////////////////
  45
  46 Block* findDefiningBlock(const SSATmp* t, const IdomVector& idoms) {
  47   assertx(!t->inst()->is(DefConst));
  48   auto const srcInst = t->inst();
  49
  50   if (srcInst->hasEdges()) {
  51     auto const next = srcInst->next();
  52     UNUSED auto const taken = srcInst->taken();
  53     always_assert_flog(
  54       next && taken,
  55       "hasEdges instruction defining a dst had no edges:\n  {}\n",
  56       srcInst->toString()
  57     );
  58     for (const auto& arc : next->preds()) {
  59       auto pred = arc.from();
  60       if (pred != srcInst->block() && !dominates(next, pred, idoms)) {
  61         return nullptr;
  62       }
  63     }
  64     return next;
  65   }
  66
  67   return srcInst->block();
  68 }
  69
  70 //////////////////////////////////////////////////////////////////////
  71
  72 bool is_tmp_usable(const IdomVector& idoms,
  73                    const SSATmp* tmp,
  74                    const Block* where) {
  75   if (tmp->inst()->is(DefConst)) return true;
  76   auto const definingBlock = findDefiningBlock(tmp, idoms);
  77   if (!definingBlock) return false;
  78   return dominates(definingBlock, where, idoms);
  79 }
  80
  81 //////////////////////////////////////////////////////////////////////
  82
  83 SSATmp* least_common_ancestor(SSATmp* s1, SSATmp* s2) {
  84   if (s1 == s2) return s1;
  85   if (s1 == nullptr || s2 == nullptr) return nullptr;
  86
  87   IdSet<SSATmp> seen;
  88
  89   auto const step = [] (SSATmp* v) {
  90     assertx(v != nullptr);
  91     return v->inst()->isPassthrough() ?
  92       v->inst()->getPassthroughValue() :
  93       nullptr;
  94   };
  95
  96   auto const process = [&] (SSATmp*& v) {
  97     if (v == nullptr) return false;
  98     if (seen[v]) return true;
  99     seen.add(v);
 100     v = step(v);
 101     return false;
 102   };
 103
 104   while (s1 != nullptr || s2 != nullptr) {
 105     if (process(s1)) return s1;
 106     if (process(s2)) return s2;
 107   }
 108
 109   return nullptr;
 110 }
 111
 112 //////////////////////////////////////////////////////////////////////
 113
 114 }}