hphp/runtime/vm/jit/phi.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2016 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 #include "hphp/runtime/vm/jit/extra-data.h"
  18 #include "hphp/runtime/vm/jit/ir-instruction.h"
  19 #include "hphp/runtime/vm/jit/ir-unit.h"
  20 #include "hphp/runtime/vm/jit/mutation.h"
  21 #include "hphp/runtime/vm/jit/pass-tracer.h"
  22 #include "hphp/runtime/vm/jit/simplify.h"
  23
  24 #include "hphp/util/trace.h"
  25
  26 #include <folly/Optional.h>
  27
  28 #include <iterator>
  29
  30 namespace HPHP { namespace jit {
  31
  32 TRACE_SET_MOD(hhir_phi);
  33
  34 namespace {
  35
  36 /*
  37  * If every value in values is equivalent and safe to sink through a phi,
  38  * return a model instruction to be copied. Otherwise, return nullptr.
  39  *
  40  * Currently only supports a very limited set of instructions to simplify the
  41  * decision for when it's safe to clone/sink them:
  42  * - No memory effects (read or write).
  43  * - One SSATmp src, which must be either a constant or the globally-available
  44      FramePtr/StkPtr.
  45  */
  46 const IRInstruction* findSinkablePhiSrc(
  47   const jit::flat_set<SSATmp*>& values
  48 ) {
  49   const IRInstruction* inst = nullptr;
  50
  51   for (auto val : values) {
  52     if (!val->inst()->is(LdLocAddr, LdStkAddr, LdMIStateAddr)) {
  53       return nullptr;
  54     }
  55     assertx(val->inst()->numSrcs() == 1);
  56
  57     if (inst == nullptr) {
  58       inst = val->inst();
  59       continue;
  60     }
  61
  62     auto newInst = val->inst();
  63     if (newInst->op() != inst->op() ||
  64         newInst->hasExtra() != inst->hasExtra() ||
  65         (newInst->hasExtra() &&
  66          !equalsExtra(newInst->op(), newInst->rawExtra(), inst->rawExtra())) ||
  67         newInst->src(0) != inst->src(0)) {
  68       return nullptr;
  69     }
  70   }
  71
  72   return inst;
  73 }
  74
  75 }
  76
  77 /*
  78  * Perform a few simple optimizations on DefLabels:
  79  * - If a phi's dest has a type that represents a constant value, replace the
  80  *   phi with a Mov from a DefConst (to be copy-propagated by a later pass).
  81  * - If the preds provide only one unique value other than the dest of the phi
  82      itself, replace the phi with a Mov of that unique value.
  83  * - If all preds provide an equivalent value, insert a copy of the instruction
  84  *   defining that value after the DefLabel, replacing the phi. This is only
  85  *   done for a limited whitelist of instructions that are safe and cheap to
  86  *   sink.
  87  */
  88 void optimizePhis(IRUnit& unit) {
  89   auto changed = false;
  90   PassTracer pt{&unit, TRACEMOD, "optimizePhis", &changed};
  91
  92   bool repeat;
  93   jit::flat_set<SSATmp*> values;
  94   auto processBlock = [&](Block* b) {
  95     auto& label = b->front();
  96     if (!label.is(DefLabel)) return;
  97
  98     for (unsigned i = 0; i < label.numDsts(); ++i) {
  99       values.clear();
 100       b->forEachSrc(i, [&](IRInstruction* jmp, SSATmp*) {
 101         copyProp(jmp);
 102         values.insert(jmp->src(i));
 103       });
 104
 105       auto const phiDest = label.dst(i);
 106       IRInstruction* newInst = nullptr;
 107       if (phiDest->hasConstVal() ||
 108           phiDest->type().subtypeOfAny(TUninit, TInitNull, TNullptr)) {
 109         newInst =
 110           unit.gen(phiDest, Mov, label.marker(), unit.cns(phiDest->type()));
 111       } else if (values.size() == 1 ||
 112                  (values.size() == 2 && values.count(phiDest))) {
 113         values.erase(phiDest);
 114         // This is safe without any extra dominator checks because we know that
 115         // there are no preds that don't have the value available.
 116         newInst = unit.gen(phiDest, Mov, label.marker(), *values.begin());
 117       } else if (auto sinkInst = findSinkablePhiSrc(values)) {
 118         // As long as DefInlineFP exists, FramePtr SSATmps aren't truly
 119         // SSA. We have to make sure the live FramePtr at the point of the
 120         // DefLabel is the same as the one from the LdLocAddr, if that's the
 121         // instruction we're trying to sink.
 122         if (sinkInst->is(LdLocAddr) &&
 123             sinkInst->marker().fp() != label.marker().fp()) {
 124           continue;
 125         }
 126         newInst = unit.clone(sinkInst, phiDest);
 127         newInst->marker() = label.marker();
 128       }
 129
 130       if (newInst != nullptr) {
 131         deletePhiDest(&label, i);
 132         b->insert(std::next(b->iteratorTo(&label)), newInst);
 133         changed = repeat = true;
 134       }
 135     }
 136
 137     if (label.numDsts() == 0) b->erase(&label);
 138   };
 139
 140   do {
 141     repeat = false;
 142     postorderWalk(unit, processBlock);
 143   } while (repeat);
 144 }
 145
 146 }}