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