hphp/runtime/vm/jit/check.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
  17 #include "hphp/runtime/vm/jit/check.h"
  18
  19 #include "hphp/runtime/vm/jit/analysis.h"
  20 #include "hphp/runtime/vm/jit/block.h"
  21 #include "hphp/runtime/vm/jit/cfg.h"
  22 #include "hphp/runtime/vm/jit/id-set.h"
  23 #include "hphp/runtime/vm/jit/ir-instruction.h"
  24 #include "hphp/runtime/vm/jit/ir-opcode.h"
  25 #include "hphp/runtime/vm/jit/ir-unit.h"
  26 #include "hphp/runtime/vm/jit/mc-generator.h"
  27 #include "hphp/runtime/vm/jit/state-vector.h"
  28 #include "hphp/runtime/vm/jit/phys-reg.h"
  29 #include "hphp/runtime/vm/jit/reg-alloc.h"
  30 #include "hphp/runtime/vm/jit/type.h"
  31
  32 #include <folly/Format.h>
  33
  34 #include <bitset>
  35 #include <iostream>
  36 #include <string>
  37 #include <unordered_set>
  38
  39 #include <boost/dynamic_bitset.hpp>
  40
  41 namespace HPHP { namespace jit {
  42
  43 namespace {
  44
  45 //////////////////////////////////////////////////////////////////////
  46
  47 TRACE_SET_MOD(hhir);
  48
  49 /*
  50  * Return the number of parameters required for this block.
  51  */
  52 DEBUG_ONLY static int numBlockParams(Block* b) {
  53   return b->empty() || b->front().op() != DefLabel ? 0 :
  54          b->front().numDsts();
  55 }
  56
  57 /*
  58  * Check one block for being well formed. Invariants verified:
  59  * 1. The block begins with an optional DefLabel, followed by an optional
  60  *    BeginCatch.
  61  * 2. DefLabel and BeginCatch may not appear anywhere in a block other than
  62  *    where specified in #1.
  63  * 3. If this block is a catch block, it must have at most one predecessor.
  64  * 4. The last instruction must be isBlockEnd() and the middle instructions
  65  *    must not be isBlockEnd().  Therefore, blocks cannot be empty.
  66  * 5. If the last instruction isTerminal(), block->next() must be null.
  67  * 6. Every instruction must have a catch block attached to it if and only if it
  68  *    has the MayRaiseError flag.
  69  * 7. Any path from this block to a Block that expects values must be
  70  *    from a Jmp instruciton.
  71  * 8. Every instruction's BCMarker must point to a valid bytecode instruction.
  72  */
  73 bool checkBlock(Block* b) {
  74   auto it = b->begin();
  75   auto end = b->end();
  76   always_assert(!b->empty());
  77
  78   // Invariant #1
  79   if (it->op() == DefLabel) {
  80     ++it;
  81   }
  82
  83   // Invariant #1
  84   if (it != end && it->op() == BeginCatch) {
  85     ++it;
  86   }
  87
  88   // Invariants #2, #4
  89   always_assert(it != end && b->back().isBlockEnd());
  90   --end;
  91   for (IRInstruction& inst : folly::range(it, end)) {
  92     always_assert(inst.op() != DefLabel);
  93     always_assert(inst.op() != BeginCatch);
  94     always_assert(!inst.isBlockEnd());
  95   }
  96   for (IRInstruction& inst : *b) {
  97     // Invariant #8
  98     always_assert(inst.marker().valid());
  99     always_assert(inst.block() == b);
 100     // Invariant #6
 101     always_assert_log(
 102       inst.mayRaiseError() == (inst.taken() && inst.taken()->isCatch()),
 103       [&]{ return inst.toString(); }
 104     );
 105   }
 106
 107   // Invariant #5
 108   always_assert(IMPLIES(b->back().isTerminal(), !b->next()));
 109
 110   // Invariant #7
 111   if (b->taken()) {
 112     // only Jmp can branch to a join block expecting values.
 113     IRInstruction* branch = &b->back();
 114     auto numArgs = branch->op() == Jmp ? branch->numSrcs() : 0;
 115     always_assert(numBlockParams(b->taken()) == numArgs);
 116   }
 117
 118   // Invariant #3
 119   if (b->isCatch()) {
 120     // keyed off a tca, so there needs to be exactly one
 121     always_assert(b->preds().size() <= 1);
 122   }
 123
 124   return true;
 125 }
 126
 127 }
 128
 129 //////////////////////////////////////////////////////////////////////
 130
 131 /*
 132  * Build the CFG, then the dominator tree, then use it to validate SSA.
 133  * 1. Each src must be defined by some other instruction, and each dst must
 134  *    be defined by the current instruction.
 135  * 2. Each src must be defined earlier in the same block or in a dominator.
 136  * 3. Each dst must not be previously defined.
 137  * 4. Treat tmps defined by DefConst as always defined.
 138  * 5. Each predecessor of a reachable block must be reachable (deleted
 139  *    blocks must not have out-edges to reachable blocks).
 140  * 6. The entry block must not have any predecessors.
 141  * 7. The entry block starts with a DefFP instruction.
 142  */
 143 bool checkCfg(const IRUnit& unit) {
 144   auto const blocks = rpoSortCfg(unit);
 145   auto const rpoIDs = numberBlocks(unit, blocks);
 146   auto reachable    = boost::dynamic_bitset<>(unit.numBlocks());
 147
 148   // Entry block can't have predecessors.
 149   always_assert(unit.entry()->numPreds() == 0);
 150
 151   // Entry block starts with DefFP
 152   always_assert(!unit.entry()->empty() &&
 153                 unit.entry()->begin()->op() == DefFP);
 154
 155   // Check valid successor/predecessor edges, and identify reachable blocks.
 156   for (Block* b : blocks) {
 157     reachable.set(b->id());
 158     auto checkEdge = [&] (const Edge* e) {
 159       always_assert(e->from() == b);
 160       for (auto& p : e->to()->preds()) if (&p == e) return;
 161       always_assert(false); // did not find edge.
 162     };
 163     checkBlock(b);
 164     if (auto e = b->nextEdge())  checkEdge(e);
 165     if (auto e = b->takenEdge()) checkEdge(e);
 166   }
 167   for (Block* b : blocks) {
 168     for (auto const& e : b->preds()) {
 169       always_assert(&e == e.inst()->takenEdge() || &e == e.inst()->nextEdge());
 170       always_assert(e.to() == b);
 171
 172       // Invariant #5
 173       always_assert_flog(reachable.test(e.from()->id()),
 174         "unreachable: B{}\n", e.from()->id());
 175     }
 176   }
 177
 178   auto defined_set = jit::sparse_idptr_set<SSATmp>{unit.numTmps()};
 179
 180   /*
 181    * Visit every instruction and make sure their sources are either defined in
 182    * a block that strictly dominates the block containing the instruction, or
 183    * defined earlier in the same block as the instruction.
 184    */
 185   auto const idoms = findDominators(unit, blocks, rpoIDs);
 186   for (auto& blk : blocks) {
 187     for (auto& inst : blk->instrs()) {
 188       for (auto src : inst.srcs()) {
 189         if (src->inst()->is(DefConst)) continue;
 190         auto const dom = findDefiningBlock(src, idoms);
 191         auto const locally_defined =
 192           src->inst()->block() == inst.block() && defined_set.contains(src);
 193         auto const strictly_dominates =
 194           src->inst()->block() != inst.block() &&
 195           dom && dominates(dom, inst.block(), idoms);
 196         always_assert_flog(
 197           locally_defined || strictly_dominates,
 198           "src '{}' in '{}' came from '{}', which is not a "
 199           "DefConst and is not defined at this use site",
 200           src->toString(), inst.toString(),
 201           src->inst()->toString()
 202         );
 203       }
 204       for (auto dst : inst.dsts()) defined_set.insert(dst);
 205     }
 206     defined_set.clear();
 207   }
 208
 209   /*
 210    * Check that each dst is defined only once.
 211    */
 212   defined_set.clear();
 213   for (auto& blk : blocks) {
 214     for (auto& inst : blk->instrs()) {
 215       for (auto dst : inst.dsts()) {
 216         always_assert_flog(
 217           !defined_set.contains(dst),
 218           "SSATmp ({}) was defined multiple times",
 219           dst->toString()
 220         );
 221         defined_set.insert(dst);
 222       }
 223     }
 224   }
 225
 226   return true;
 227 }
 228
 229 bool checkTmpsSpanningCalls(const IRUnit& unit) {
 230   auto ignoreSrc = [&](IRInstruction& inst, SSATmp* src) {
 231     /*
 232      * FramePtr/StkPtr-typed tmps may live across calls.
 233      *
 234      * Tmps defined by DefConst are always available and may be assigned to
 235      * registers if needed by the instructions using the const.
 236      */
 237     return src->isA(TStkPtr) ||
 238            src->isA(TFramePtr) ||
 239            src->inst()->is(DefConst);
 240   };
 241
 242   StateVector<Block,IdSet<SSATmp>> livein(unit, IdSet<SSATmp>());
 243   bool isValid = true;
 244   postorderWalk(unit, [&](Block* block) {
 245     auto& live = livein[block];
 246     if (auto taken = block->taken()) live = livein[taken];
 247     if (auto next  = block->next()) live |= livein[next];
 248     for (auto it = block->end(); it != block->begin();) {
 249       auto& inst = *--it;
 250       for (auto dst : inst.dsts()) {
 251         live.erase(dst);
 252       }
 253       if (isCallOp(inst.op())) {
 254         live.forEach([&](uint32_t tmp) {
 255           auto msg = folly::sformat("checkTmpsSpanningCalls failed\n"
 256                                     "  instruction: {}\n"
 257                                     "  src:         t{}\n"
 258                                     "\n"
 259                                     "Unit:\n"
 260                                     "{}\n",
 261                                     inst.toString(),
 262                                     tmp,
 263                                     show(unit));
 264           std::cerr << msg;
 265           FTRACE(1, "{}", msg);
 266           isValid = false;
 267         });
 268       }
 269       for (auto* src : inst.srcs()) {
 270         if (!ignoreSrc(inst, src)) live.add(src);
 271       }
 272     }
 273   });
 274
 275   return isValid;
 276 }
 277
 278 ///////////////////////////////////////////////////////////////////////////////
 279 // checkOperandTypes().
 280
 281 namespace {
 282
 283 /*
 284  * Return a union type containing all the types in the argument list.
 285  */
 286 Type buildUnion() {
 287   return TBottom;
 288 }
 289
 290 template<class... Args>
 291 Type buildUnion(Type t, Args... ts) {
 292   return t | buildUnion(ts...);
 293 }
 294
 295 }
 296
 297 /*
 298  * Runtime typechecking for IRInstruction operands.
 299  *
 300  * This is generated using the table in ir-opcode.h.  We instantiate
 301  * IR_OPCODES after defining all the various source forms to do type
 302  * assertions according to their form (see ir-opcode.h for documentation on
 303  * the notation).  The checkers appear in argument order, so each one
 304  * increments curSrc, and at the end we can check that the argument
 305  * count was also correct.
 306  */
 307 bool checkOperandTypes(const IRInstruction* inst, const IRUnit* unit) {
 308   int curSrc = 0;
 309
 310   auto bail = [&] (const std::string& msg) {
 311     FTRACE(1, "{}", msg);
 312     fprintf(stderr, "%s\n", msg.c_str());
 313
 314     always_assert_log(false, [&] { return msg; });
 315   };
 316
 317   if (opHasExtraData(inst->op()) != (bool)inst->rawExtra()) {
 318     bail(folly::format("opcode {} should{} have an ExtraData struct "
 319                        "but instruction {} does{}",
 320                        inst->op(),
 321                        opHasExtraData(inst->op()) ? "" : "n't",
 322                        *inst,
 323                        inst->rawExtra() ? "" : "n't").str());
 324   }
 325
 326   auto src = [&]() -> SSATmp* {
 327     if (curSrc < inst->numSrcs()) {
 328       return inst->src(curSrc);
 329     }
 330
 331     bail(folly::format(
 332       "Error: instruction had too few operands\n"
 333       "   instruction: {}\n",
 334         inst->toString()
 335       ).str()
 336     );
 337     not_reached();
 338   };
 339
 340   // If expected is not nullptr, it will be used. Otherwise, t.toString() will
 341   // be used as the expected string.
 342   auto check = [&] (bool cond, const Type t, const char* expected) {
 343     if (cond) return true;
 344
 345     std::string expectStr = expected ? expected : t.toString();
 346
 347     bail(folly::format(
 348       "Error: failed type check on operand {}\n"
 349       "   instruction: {}\n"
 350       "   was expecting: {}\n"
 351       "   received: {}\n",
 352         curSrc,
 353         inst->toString(),
 354         expectStr,
 355         inst->src(curSrc)->type().toString()
 356       ).str()
 357     );
 358     return true;
 359   };
 360
 361   auto checkNoArgs = [&]{
 362     if (inst->numSrcs() == 0) return true;
 363     bail(folly::format(
 364       "Error: instruction expected no operands\n"
 365       "   instruction: {}\n",
 366         inst->toString()
 367       ).str()
 368     );
 369     return true;
 370   };
 371
 372   auto countCheck = [&]{
 373     if (inst->numSrcs() == curSrc) return true;
 374     bail(folly::format(
 375       "Error: instruction had too many operands\n"
 376       "   instruction: {}\n"
 377       "   expected {} arguments\n",
 378         inst->toString(),
 379         curSrc
 380       ).str()
 381     );
 382     return true;
 383   };
 384
 385   auto checkDst = [&] (bool cond, const std::string& errorMessage) {
 386     if (cond) return true;
 387
 388     bail(folly::format("Error: failed type check on dest operand\n"
 389                        "   instruction: {}\n"
 390                        "   message: {}\n",
 391                        inst->toString(),
 392                        errorMessage).str());
 393     return true;
 394   };
 395
 396   auto requireTypeParam = [&] {
 397     checkDst(inst->hasTypeParam() || inst->is(DefConst),
 398              "Missing paramType for DParam instruction");
 399   };
 400
 401   auto requireTypeParamPtr = [&] (Ptr kind) {
 402     checkDst(inst->hasTypeParam(),
 403       "Missing paramType for DParamPtr instruction");
 404     if (inst->hasTypeParam()) {
 405       checkDst(inst->typeParam() <= TGen.ptr(kind),
 406                "Invalid paramType for DParamPtr instruction");
 407     }
 408   };
 409
 410   auto checkVariadic = [&] (Type super) {
 411     for (; curSrc < inst->numSrcs(); ++curSrc) {
 412       auto const valid = (inst->src(curSrc)->type() <= super);
 413       check(valid, Type(), nullptr);
 414     }
 415   };
 416
 417 #define IRT(name, ...) UNUSED static constexpr Type name = T##name;
 418 #define IRTP(name, ...) IRT(name)
 419   IR_TYPES
 420 #undef IRT
 421 #undef IRTP
 422
 423 #define NA            return checkNoArgs();
 424 #define S(...)        {                                   \
 425                         Type t = buildUnion(__VA_ARGS__); \
 426                         check(src()->isA(t), t, nullptr); \
 427                         ++curSrc;                         \
 428                       }
 429 #define AK(kind)      {                                                 \
 430                         Type t = Type::Array(ArrayData::k##kind##Kind); \
 431                         check(src()->isA(t), t, nullptr);               \
 432                         ++curSrc;                                       \
 433                       }
 434 #define C(T)          check(src()->hasConstVal(T) ||     \
 435                             src()->isA(TBottom),    \
 436                             Type(),                      \
 437                             "constant " #T);             \
 438                       ++curSrc;
 439 #define CStr          C(StaticStr)
 440 #define SVar(...)     checkVariadic(buildUnion(__VA_ARGS__));
 441 #define ND
 442 #define DMulti
 443 #define DSetElem
 444 #define D(...)
 445 #define DBuiltin
 446 #define DSubtract(src, t)checkDst(src < inst->numSrcs(),  \
 447                              "invalid src num");
 448 #define DofS(src)   checkDst(src < inst->numSrcs(),  \
 449                              "invalid src num");
 450 #define DRefineS(src) checkDst(src < inst->numSrcs(),  \
 451                                "invalid src num");     \
 452                       requireTypeParam();
 453 #define DParamMayRelax requireTypeParam();
 454 #define DParam         requireTypeParam();
 455 #define DParamPtr(k)   requireTypeParamPtr(Ptr::k);
 456 #define DUnboxPtr
 457 #define DBoxPtr
 458 #define DAllocObj
 459 #define DArrElem
 460 #define DArrPacked
 461 #define DCol
 462 #define DThis
 463 #define DCtx
 464 #define DCns
 465
 466 #define O(opcode, dstinfo, srcinfo, flags) \
 467   case opcode: dstinfo srcinfo countCheck(); return true;
 468
 469   switch (inst->op()) {
 470     IR_OPCODES
 471   default: always_assert(false);
 472   }
 473
 474 #undef O
 475
 476 #undef NA
 477 #undef S
 478 #undef AK
 479 #undef C
 480 #undef CStr
 481 #undef SVar
 482
 483 #undef ND
 484 #undef D
 485 #undef DBuiltin
 486 #undef DSubtract
 487 #undef DMulti
 488 #undef DSetElem
 489 #undef DofS
 490 #undef DRefineS
 491 #undef DParamMayRelax
 492 #undef DParam
 493 #undef DParamPtr
 494 #undef DUnboxPtr
 495 #undef DBoxPtr
 496 #undef DAllocObj
 497 #undef DArrElem
 498 #undef DArrPacked
 499 #undef DCol
 500 #undef DThis
 501 #undef DCtx
 502 #undef DCns
 503
 504   return true;
 505 }
 506
 507 bool checkEverything(const IRUnit& unit) {
 508   assertx(checkCfg(unit));
 509   assertx(checkTmpsSpanningCalls(unit));
 510   if (debug) {
 511     forEachInst(rpoSortCfg(unit), [&](IRInstruction* inst) {
 512       assertx(checkOperandTypes(inst, &unit));
 513     });
 514   }
 515   return true;
 516 }
 517
 518 //////////////////////////////////////////////////////////////////////
 519
 520 }}