hphp/runtime/vm/jit/check.cpp

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