hphp/runtime/vm/jit/simplify.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2015 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/simplify.h"
  18
  19 #include <limits>
  20 #include <sstream>
  21 #include <type_traits>
  22
  23 #include "hphp/util/overflow.h"
  24 #include "hphp/util/trace.h"
  25
  26 #include "hphp/runtime/base/array-data-defs.h"
  27 #include "hphp/runtime/base/comparisons.h"
  28 #include "hphp/runtime/base/repo-auth-type-array.h"
  29 #include "hphp/runtime/base/type-conversions.h"
  30 #include "hphp/runtime/ext/collections/ext_collections-idl.h"
  31 #include "hphp/runtime/vm/hhbc.h"
  32 #include "hphp/runtime/vm/jit/analysis.h"
  33 #include "hphp/runtime/vm/jit/containers.h"
  34 #include "hphp/runtime/vm/jit/guard-relaxation.h"
  35 #include "hphp/runtime/vm/jit/ir-builder.h"
  36 #include "hphp/runtime/vm/jit/minstr-effects.h"
  37 #include "hphp/runtime/vm/jit/punt.h"
  38 #include "hphp/runtime/vm/jit/type.h"
  39 #include "hphp/runtime/vm/runtime.h"
  40
  41 namespace HPHP { namespace jit {
  42
  43 TRACE_SET_MOD(simplify);
  44
  45 //////////////////////////////////////////////////////////////////////
  46
  47 namespace {
  48
  49 //////////////////////////////////////////////////////////////////////
  50
  51 const StaticString s_Array("Array");
  52 const StaticString s_isEmpty("isEmpty");
  53 const StaticString s_count("count");
  54 const StaticString s_1("1");
  55 const StaticString s_empty("");
  56 const StaticString s_invoke("__invoke");
  57 const StaticString s_isFinished("isFinished");
  58 const StaticString s_isSucceeded("isSucceeded");
  59 const StaticString s_isFailed("isFailed");
  60 const StaticString s_WaitHandle("HH\\WaitHandle");
  61
  62 //////////////////////////////////////////////////////////////////////
  63
  64 struct State {
  65   IRUnit& unit;
  66   const bool typesMightRelax;
  67
  68   // The current instruction being simplified is always at insts.top(). This
  69   // has to be a stack instead of just a pointer because simplify is reentrant.
  70   jit::stack<const IRInstruction*> insts;
  71   jit::vector<IRInstruction*> newInsts;
  72 };
  73
  74 //////////////////////////////////////////////////////////////////////
  75
  76 SSATmp* simplifyWork(State&, const IRInstruction*);
  77
  78 bool mightRelax(State& env, SSATmp* tmp) {
  79   if (!env.typesMightRelax) return false;
  80   return jit::typeMightRelax(tmp);
  81 }
  82
  83 template<class... Args>
  84 SSATmp* cns(State& env, Args&&... cns) {
  85   return env.unit.cns(std::forward<Args>(cns)...);
  86 }
  87
  88 template<class... Args>
  89 SSATmp* gen(State& env, Opcode op, BCMarker marker, Args&&... args) {
  90   return makeInstruction(
  91     [&] (IRInstruction* inst) -> SSATmp* {
  92       auto prevNewCount = env.newInsts.size();
  93       auto newDest = simplifyWork(env, inst);
  94
  95       // If any simplification happened to this instruction, drop it. We have to
  96       // check that nothing was added to newInsts because that's the only way
  97       // we can tell simplification happened to a no-dest instruction.
  98       if (newDest || env.newInsts.size() != prevNewCount) {
  99         return newDest;
 100       } else {
 101         assertx(inst->isTransient());
 102         inst = env.unit.clone(inst);
 103         env.newInsts.push_back(inst);
 104
 105         return inst->dst(0);
 106       }
 107     },
 108     op,
 109     marker,
 110     std::forward<Args>(args)...
 111   );
 112 }
 113
 114 template<class... Args>
 115 SSATmp* gen(State& env, Opcode op, Args&&... args) {
 116   assertx(!env.insts.empty());
 117   return gen(env, op, env.insts.top()->marker(), std::forward<Args>(args)...);
 118 }
 119
 120 bool arrayKindNeedsVsize(const ArrayData::ArrayKind kind) {
 121   switch (kind) {
 122     case ArrayData::kPackedKind:
 123     case ArrayData::kStructKind:
 124     case ArrayData::kMixedKind:
 125     case ArrayData::kEmptyKind:
 126     case ArrayData::kApcKind:
 127       return false;
 128     default:
 129       return true;
 130   }
 131 }
 132
 133 //////////////////////////////////////////////////////////////////////
 134
 135 /*
 136  * Simplifier rules are not allowed to add new uses to SSATmps that aren't
 137  * known to be available.  All the sources to the original instruction must
 138  * be available, and non-reference counted values reachable through the
 139  * source chain are also always available.  Anything else requires more
 140  * complicated analysis than belongs in the simplifier right now.
 141  */
 142 DEBUG_ONLY bool validate(const State& env,
 143                          SSATmp* newDst,
 144                          const IRInstruction* origInst) {
 145   auto known_available = [&] (SSATmp* src) -> bool {
 146     if (!src->type().maybe(TCounted)) return true;
 147     for (auto& oldSrc : origInst->srcs()) {
 148       if (oldSrc == src) return true;
 149     }
 150     return false;
 151   };
 152
 153   // Return early for the no-simplification case.
 154   if (env.newInsts.empty() && !newDst) {
 155     return true;
 156   }
 157
 158   const IRInstruction* last = nullptr;
 159
 160   if (!env.newInsts.empty()) {
 161     for (size_t i = 0, n = env.newInsts.size(); i < n; ++i) {
 162       auto newInst = env.newInsts[i];
 163
 164       for (auto& src : newInst->srcs()) {
 165         always_assert_flog(
 166           known_available(src),
 167           "A simplification rule produced an instruction that used a value "
 168           "that wasn't known to be available:\n"
 169           "  original inst: {}\n"
 170           "  new inst:      {}\n"
 171           "  src:           {}\n",
 172           origInst->toString(),
 173           newInst->toString(),
 174           src->toString()
 175         );
 176       }
 177
 178       if (i == n - 1) {
 179         last = newInst;
 180         continue;
 181       }
 182
 183       always_assert_flog(
 184         !newInst->isBlockEnd(),
 185         "Block-ending instruction produced in the middle of a simplified "
 186         "instruction stream:\n"
 187         "  original inst: {}\n"
 188         "  new inst:      {}\n",
 189         origInst->toString(),
 190         newInst->toString()
 191       );
 192     }
 193   }
 194
 195   if (newDst) {
 196     const bool available = known_available(newDst) ||
 197       std::any_of(env.newInsts.begin(), env.newInsts.end(),
 198                   [&] (IRInstruction* inst) { return newDst == inst->dst(); });
 199
 200     always_assert_flog(
 201       available,
 202       "Simplifier produced a new destination that wasn't known to be "
 203       "available:\n"
 204       "  original inst: {}\n"
 205       "  new dst:       {}\n",
 206       origInst->toString(),
 207       newDst->toString()
 208     );
 209   }
 210
 211   if (!last) return true;
 212
 213   auto assert_last = [&] (bool cond, const char* msg) {
 214     always_assert_flog(
 215       cond,
 216       "{}:\n"
 217       "  original inst: {}\n"
 218       "  last new inst: {}\n",
 219       msg,
 220       origInst->toString(),
 221       last->toString()
 222     );
 223   };
 224
 225   assert_last(
 226     !origInst->naryDst(),
 227     "Nontrivial simplification returned for instruction with NaryDest"
 228   );
 229
 230   assert_last(
 231     origInst->hasDst() == (bool)newDst,
 232     "HasDest mismatch between input and output"
 233   );
 234
 235   assert_last(
 236     IMPLIES(last->isBlockEnd(), origInst->isBlockEnd()),
 237     "Block-end instruction produced for simplification of non-block-end "
 238     "instruction"
 239   );
 240
 241   if (last->hasEdges()) {
 242     assert_last(
 243       origInst->hasEdges(),
 244       "Instruction with edges produced for simplification of edge-free "
 245       "instruction"
 246     );
 247
 248     assert_last(
 249       IMPLIES(last->next(), last->next() == origInst->next() ||
 250                             last->next() == origInst->taken()),
 251       "Last instruction of simplified stream has next edge not reachable from "
 252       "the input instruction"
 253     );
 254
 255     assert_last(
 256       IMPLIES(last->taken(), last->taken() == origInst->next() ||
 257                              last->taken() == origInst->taken()),
 258       "Last instruction of simplified stream has taken edge not reachable "
 259       "from the input instruction"
 260     );
 261   }
 262
 263   return true;
 264 }
 265
 266 //////////////////////////////////////////////////////////////////////
 267
 268 /*
 269  * Individual simplification routines return nullptr if they don't want to
 270  * change anything, or they can call gen any number of times to produce a
 271  * different IR sequence, returning the thing gen'd that should be used as the
 272  * value of the simplified instruction sequence.
 273  */
 274
 275 SSATmp* mergeBranchDests(State& env, const IRInstruction* inst) {
 276   // Replace a conditional branch with a Jmp if both branches go to the same
 277   // block. Only work if the instruction does not have side effect.
 278   // JmpZero/JmpNZero is handled separately.
 279   assertx(inst->is(CheckTypeMem,
 280                    CheckLoc,
 281                    CheckStk,
 282                    CheckInit,
 283                    CheckInitMem,
 284                    CheckInitProps,
 285                    CheckInitSProps,
 286                    CheckPackedArrayBounds,
 287                    CheckStaticLocInit,
 288                    CheckRefInner,
 289                    CheckCtxThis));
 290   if (inst->next() != nullptr && inst->next() == inst->taken()) {
 291     return gen(env, Jmp, inst->next());
 292   }
 293   return nullptr;
 294 }
 295
 296 SSATmp* simplifyCheckCtxThis(State& env, const IRInstruction* inst) {
 297   auto const func = inst->marker().func();
 298   auto const srcTy = inst->src(0)->type();
 299   if (srcTy <= TObj) return gen(env, Nop);
 300   if (!func->mayHaveThis() || !srcTy.maybe(TObj)) {
 301     return gen(env, Jmp, inst->taken());
 302   }
 303   return mergeBranchDests(env, inst);
 304 }
 305
 306 SSATmp* simplifyCastCtxThis(State& env, const IRInstruction* inst) {
 307   if (inst->src(0)->type() <= TObj) return inst->src(0);
 308   return nullptr;
 309 }
 310
 311 SSATmp* simplifyLdClsCtx(State& env, const IRInstruction* inst) {
 312   SSATmp* ctx = inst->src(0);
 313   if (ctx->hasConstVal(TCctx)) {
 314     return cns(env, ctx->cctxVal().cls());
 315   }
 316   Type ctxType = ctx->type();
 317   if (ctxType <= TObj) {
 318     // this pointer... load its class ptr
 319     return gen(env, LdObjClass, ctx);
 320   }
 321   if (ctxType <= TCctx) {
 322     return gen(env, LdClsCctx, ctx);
 323   }
 324   return nullptr;
 325 }
 326
 327 SSATmp* simplifyLdObjClass(State& env, const IRInstruction* inst) {
 328   auto const ty = inst->src(0)->type();
 329
 330   if (mightRelax(env, inst->src(0)) || !(ty < TObj)) return nullptr;
 331
 332   if (auto const exact = ty.clsSpec().exactCls()) return cns(env, exact);
 333   return nullptr;
 334 }
 335
 336 SSATmp* simplifyLdObjInvoke(State& env, const IRInstruction* inst) {
 337   auto const src = inst->src(0);
 338   if (!src->hasConstVal()) return nullptr;
 339
 340   auto const cls = src->clsVal();
 341   if (!rds::isPersistentHandle(cls->classHandle())) return nullptr;
 342
 343   auto const meth = cls->getCachedInvoke();
 344   return meth == nullptr ? nullptr : cns(env, meth);
 345 }
 346
 347 SSATmp* simplifyGetCtxFwdCall(State& env, const IRInstruction* inst) {
 348   auto const srcCtx = inst->src(0);
 349   if (srcCtx->isA(TCctx)) return srcCtx;
 350   return nullptr;
 351 }
 352
 353 SSATmp* simplifyConvClsToCctx(State& env, const IRInstruction* inst) {
 354   auto* srcInst = inst->src(0)->inst();
 355   if (srcInst->is(LdClsCctx)) return srcInst->src(0);
 356   return nullptr;
 357 }
 358
 359 SSATmp* simplifyMov(State& env, const IRInstruction* inst) {
 360   return inst->src(0);
 361 }
 362
 363 SSATmp* simplifyAbsDbl(State& env, const IRInstruction* inst) {
 364   auto const src = inst->src(0);
 365   if (src->hasConstVal()) return cns(env, fabs(src->dblVal()));
 366   return nullptr;
 367 }
 368
 369 template<class Oper>
 370 SSATmp* constImpl(State& env, SSATmp* src1, SSATmp* src2, Oper op) {
 371   // don't canonicalize to the right, OP might not be commutative
 372   if (!src1->hasConstVal() || !src2->hasConstVal()) return nullptr;
 373
 374   auto both = [&](Type ty) { return src1->type() <= ty && src2->type() <= ty; };
 375
 376   if (both(TBool)) return cns(env, op(src1->boolVal(), src2->boolVal()));
 377   if (both(TInt))  return cns(env, op(src1->intVal(), src2->intVal()));
 378   if (both(TDbl))  return cns(env, op(src1->dblVal(), src2->dblVal()));
 379   return nullptr;
 380 }
 381
 382 template<class Oper>
 383 SSATmp* commutativeImpl(State& env,
 384                         SSATmp* src1,
 385                         SSATmp* src2,
 386                         Opcode opcode,
 387                         Oper op) {
 388   if (auto simp = constImpl(env, src1, src2, op)) return simp;
 389
 390   // Canonicalize constants to the right.
 391   if (src1->hasConstVal() && src2->type().hasConstVal()) {
 392     return gen(env, opcode, src2, src1);
 393   }
 394
 395   // Only handle integer operations for now.
 396   if (!src1->isA(TInt) || !src2->isA(TInt)) return nullptr;
 397
 398   auto const inst1 = src1->inst();
 399   auto const inst2 = src2->inst();
 400   if (inst1->op() == opcode && inst1->src(1)->hasConstVal()) {
 401     // (X + C1) + C2 --> X + C3
 402     if (src2->hasConstVal()) {
 403       int64_t right = inst1->src(1)->intVal();
 404       right = op(right, src2->intVal());
 405       return gen(env, opcode, inst1->src(0), cns(env, right));
 406     }
 407     // (X + C1) + (Y + C2) --> X + Y + C3
 408     if (inst2->op() == opcode && inst2->src(1)->hasConstVal()) {
 409       int64_t right = inst1->src(1)->intVal();
 410       right = op(right, inst2->src(1)->intVal());
 411       SSATmp* left = gen(env, opcode, inst1->src(0), inst2->src(0));
 412       return gen(env, opcode, left, cns(env, right));
 413     }
 414   }
 415   return nullptr;
 416 }
 417
 418 /*
 419  * Assumes that outop is commutative, don't use with subtract!
 420  *
 421  * Assumes that the values we're going to add new uses to are not reference
 422  * counted.  (I.e. this is a distributive FooInt opcode.)
 423  */
 424 template<class OutOper, class InOper>
 425 SSATmp* distributiveImpl(State& env,
 426                          SSATmp* src1,
 427                          SSATmp* src2,
 428                          Opcode outcode,
 429                          Opcode incode,
 430                          OutOper outop,
 431                          InOper inop) {
 432   if (auto simp = commutativeImpl(env, src1, src2, outcode, outop)) {
 433     return simp;
 434   }
 435
 436   auto const inst1 = src1->inst();
 437   auto const inst2 = src2->inst();
 438   auto const op1 = inst1->op();
 439   auto const op2 = inst2->op();
 440   // all combinations of X * Y + X * Z --> X * (Y + Z)
 441   if (op1 == incode && op2 == incode) {
 442     if (inst1->src(0) == inst2->src(0)) {
 443       SSATmp* fold = gen(env, outcode, inst1->src(1), inst2->src(1));
 444       return gen(env, incode, inst1->src(0), fold);
 445     }
 446     if (inst1->src(0) == inst2->src(1)) {
 447       SSATmp* fold = gen(env, outcode, inst1->src(1), inst2->src(0));
 448       return gen(env, incode, inst1->src(0), fold);
 449     }
 450     if (inst1->src(1) == inst2->src(0)) {
 451       SSATmp* fold = gen(env, outcode, inst1->src(0), inst2->src(1));
 452       return gen(env, incode, inst1->src(1), fold);
 453     }
 454     if (inst1->src(1) == inst2->src(1)) {
 455       SSATmp* fold = gen(env, outcode, inst1->src(0), inst2->src(0));
 456       return gen(env, incode, inst1->src(1), fold);
 457     }
 458   }
 459   return nullptr;
 460 }
 461
 462 SSATmp* simplifyAddInt(State& env, const IRInstruction* inst) {
 463   auto const src1 = inst->src(0);
 464   auto const src2 = inst->src(1);
 465
 466   auto add = std::plus<int64_t>();
 467   auto mul = std::multiplies<int64_t>();
 468   if (auto simp = distributiveImpl(env, src1, src2, AddInt,
 469                                    MulInt, add, mul)) {
 470     return simp;
 471   }
 472   if (src2->hasConstVal()) {
 473     int64_t src2Val = src2->intVal();
 474     // X + 0 --> X
 475     if (src2Val == 0) return src1;
 476
 477     // X + -C --> X - C
 478     // Weird, but can show up as a result of other simplifications. Don't need
 479     // to check for C == INT_MIN, simplifySubInt already checks.
 480     if (src2Val < 0) return gen(env, SubInt, src1, cns(env, -src2Val));
 481   }
 482   // X + (0 - Y) --> X - Y
 483   auto inst2 = src2->inst();
 484   if (inst2->op() == SubInt) {
 485     SSATmp* src = inst2->src(0);
 486     if (src->hasConstVal() && src->intVal() == 0) {
 487       return gen(env, SubInt, src1, inst2->src(1));
 488     }
 489   }
 490   auto inst1 = src1->inst();
 491
 492   // (X - C1) + ...
 493   if (inst1->op() == SubInt && inst1->src(1)->hasConstVal()) {
 494     auto x = inst1->src(0);
 495     auto c1 = inst1->src(1);
 496
 497     // (X - C1) + C2 --> X + (C2 - C1)
 498     if (src2->hasConstVal()) {
 499       auto rhs = gen(env, SubInt, cns(env, src2->intVal()), c1);
 500       return gen(env, AddInt, x, rhs);
 501     }
 502
 503     // (X - C1) + (Y +/- C2)
 504     if ((inst2->op() == AddInt || inst2->op() == SubInt) &&
 505         inst2->src(1)->hasConstVal()) {
 506       auto y = inst2->src(0);
 507       auto c2 = inst2->src(1);
 508       SSATmp* rhs = nullptr;
 509       if (inst2->op() == SubInt) {
 510         // (X - C1) + (Y - C2) --> X + Y + (-C1 - C2)
 511         rhs = gen(env, SubInt, gen(env, SubInt, cns(env, 0), c1), c2);
 512       } else {
 513         // (X - C1) + (Y + C2) --> X + Y + (C2 - C1)
 514         rhs = gen(env, SubInt, c2, c1);
 515       }
 516       auto lhs = gen(env, AddInt, x, y);
 517       return gen(env, AddInt, lhs, rhs);
 518     }
 519     // (X - C1) + (Y + C2) --> X + Y + (C2 - C1)
 520     if (inst2->op() == AddInt && inst2->src(1)->hasConstVal()) {
 521       auto y = inst2->src(0);
 522       auto c2 = inst2->src(1);
 523
 524       auto lhs = gen(env, AddInt, x, y);
 525       auto rhs = gen(env, SubInt, c2, c1);
 526       return gen(env, AddInt, lhs, rhs);
 527     }
 528   }
 529
 530   return nullptr;
 531 }
 532
 533 SSATmp* simplifyAddIntO(State& env, const IRInstruction* inst) {
 534   auto const src1 = inst->src(0);
 535   auto const src2 = inst->src(1);
 536   if (src1->hasConstVal() && src2->hasConstVal()) {
 537     int64_t a = src1->intVal();
 538     int64_t b = src2->intVal();
 539     return add_overflow(a, b)
 540       ? cns(env, double(a) + double(b))
 541       : cns(env, a + b);
 542   }
 543   return nullptr;
 544 }
 545
 546 SSATmp* simplifySubInt(State& env, const IRInstruction* inst) {
 547   auto const src1 = inst->src(0);
 548   auto const src2 = inst->src(1);
 549
 550   auto sub = std::minus<int64_t>();
 551   if (auto simp = constImpl(env, src1, src2, sub)) return simp;
 552
 553   // X - X --> 0
 554   if (src1 == src2) return cns(env, 0);
 555
 556   if (src2->hasConstVal()) {
 557     int64_t src2Val = src2->intVal();
 558     // X - 0 --> X
 559     if (src2Val == 0) return src1;
 560
 561     // X - -C --> X + C
 562     // Need to check for C == INT_MIN, otherwise we'd infinite loop as
 563     // X + -C would send us back here.
 564     auto const min = std::numeric_limits<int64_t>::min();
 565     if (src2Val > min && src2Val < 0) {
 566       return gen(env, AddInt, src1, cns(env, -src2Val));
 567     }
 568   }
 569   // X - (0 - Y) --> X + Y
 570   auto inst2 = src2->inst();
 571   if (inst2->op() == SubInt) {
 572     SSATmp* src = inst2->src(0);
 573     if (src->hasConstVal(0)) return gen(env, AddInt, src1, inst2->src(1));
 574   }
 575   return nullptr;
 576 }
 577
 578 SSATmp* simplifySubIntO(State& env, const IRInstruction* inst) {
 579   auto const src1 = inst->src(0);
 580   auto const src2 = inst->src(1);
 581   if (src1->hasConstVal() && src2->hasConstVal()) {
 582     int64_t a = src1->intVal();
 583     int64_t b = src2->intVal();
 584     return sub_overflow(a, b)
 585       ? cns(env, double(a) - double(b))
 586       : cns(env, a - b);
 587   }
 588   return nullptr;
 589 }
 590
 591 SSATmp* simplifyMulInt(State& env, const IRInstruction* inst) {
 592   auto const src1 = inst->src(0);
 593   auto const src2 = inst->src(1);
 594
 595   auto mul = std::multiplies<int64_t>();
 596   if (auto simp = commutativeImpl(env, src1, src2, MulInt, mul)) return simp;
 597
 598   if (!src2->hasConstVal()) return nullptr;
 599
 600   int64_t rhs = src2->intVal();
 601
 602   // X * (-1) --> -X
 603   if (rhs == -1) return gen(env, SubInt, cns(env, 0), src1);
 604   // X * 0 --> 0
 605   if (rhs == 0) return cns(env, 0);
 606   // X * 1 --> X
 607   if (rhs == 1) return src1;
 608   // X * 2 --> X + X
 609   if (rhs == 2) return gen(env, AddInt, src1, src1);
 610
 611   auto isPowTwo = [](int64_t a) {
 612     return a > 0 && folly::isPowTwo<uint64_t>(a);
 613   };
 614   auto log2 = [](int64_t a) {
 615     assertx(a > 0);
 616     return folly::findLastSet<uint64_t>(a) - 1;
 617   };
 618
 619   // X * 2^C --> X << C
 620   if (isPowTwo(rhs)) return gen(env, Shl, src1, cns(env, log2(rhs)));
 621
 622   // X * (2^C + 1) --> ((X << C) + X)
 623   if (isPowTwo(rhs - 1)) {
 624     auto lhs = gen(env, Shl, src1, cns(env, log2(rhs - 1)));
 625     return gen(env, AddInt, lhs, src1);
 626   }
 627   // X * (2^C - 1) --> ((X << C) - X)
 628   if (isPowTwo(rhs + 1)) {
 629     auto lhs = gen(env, Shl, src1, cns(env, log2(rhs + 1)));
 630     return gen(env, SubInt, lhs, src1);
 631   }
 632
 633   return nullptr;
 634 }
 635
 636 SSATmp* simplifyAddDbl(State& env, const IRInstruction* inst) {
 637   return constImpl(env, inst->src(0), inst->src(1), std::plus<double>());
 638 }
 639
 640 SSATmp* simplifySubDbl(State& env, const IRInstruction* inst) {
 641   return constImpl(env, inst->src(0), inst->src(1), std::minus<double>());
 642 }
 643
 644 SSATmp* simplifyMulDbl(State& env, const IRInstruction* inst) {
 645   return constImpl(env, inst->src(0), inst->src(1), std::multiplies<double>());
 646 }
 647
 648 SSATmp* simplifyMulIntO(State& env, const IRInstruction* inst) {
 649   auto const src1 = inst->src(0);
 650   auto const src2 = inst->src(1);
 651   if (src1->hasConstVal() && src2->hasConstVal()) {
 652     int64_t a = src1->intVal();
 653     int64_t b = src2->intVal();
 654     return mul_overflow(a, b)
 655       ? cns(env, double(a) * double(b))
 656       : cns(env, a * b);
 657   }
 658   return nullptr;
 659 }
 660
 661 SSATmp* simplifyMod(State& env, const IRInstruction* inst) {
 662   auto const src1 = inst->src(0);
 663   auto const src2 = inst->src(1);
 664
 665   if (!src2->hasConstVal()) return nullptr;
 666
 667   auto const src2Val = src2->intVal();
 668   if (src2Val == 0 || src2Val == -1) {
 669     // Undefined behavior, so we might as well constant propagate whatever we
 670     // want. If we're being asked to simplify this, it better be dynamically
 671     // unreachable code.
 672     return cns(env, 0);
 673   }
 674
 675   if (src1->hasConstVal()) return cns(env, src1->intVal() % src2Val);
 676   // X % 1 --> 0
 677   if (src2Val == 1) return cns(env, 0);
 678
 679   return nullptr;
 680 }
 681
 682 SSATmp* simplifyDivDbl(State& env, const IRInstruction* inst) {
 683   auto src1 = inst->src(0);
 684   auto src2 = inst->src(1);
 685
 686   if (!src2->hasConstVal()) return nullptr;
 687
 688   // not supporting integers (#2570625)
 689   double src2Val = src2->dblVal();
 690
 691   // X / 0 -> bool(false)
 692   if (src2Val == 0.0) {
 693     // Ideally we'd generate a RaiseWarning and return false here, but we need
 694     // a catch trace for that and we can't make a catch trace here.
 695     return nullptr;
 696   }
 697
 698   // statically compute X / Y
 699   return src1->hasConstVal() ? cns(env, src1->dblVal() / src2Val) : nullptr;
 700 }
 701
 702 SSATmp* simplifyAndInt(State& env, const IRInstruction* inst) {
 703   auto const src1 = inst->src(0);
 704   auto const src2 = inst->src(1);
 705   auto bit_and = [](int64_t a, int64_t b) { return a & b; };
 706   auto bit_or = [](int64_t a, int64_t b) { return a | b; };
 707   auto simp = distributiveImpl(env, src1, src2, AndInt, OrInt,
 708                                bit_and, bit_or);
 709   if (simp != nullptr) {
 710     return simp;
 711   }
 712   // X & X --> X
 713   if (src1 == src2) {
 714     return src1;
 715   }
 716   if (src2->hasConstVal()) {
 717     // X & 0 --> 0
 718     if (src2->intVal() == 0) {
 719       return cns(env, 0);
 720     }
 721     // X & (~0) --> X
 722     if (src2->intVal() == ~0L) {
 723       return src1;
 724     }
 725   }
 726   return nullptr;
 727 }
 728
 729 SSATmp* simplifyOrInt(State& env, const IRInstruction* inst) {
 730   auto const src1 = inst->src(0);
 731   auto const src2 = inst->src(1);
 732
 733   auto bit_and = [](int64_t a, int64_t b) { return a & b; };
 734   auto bit_or = [](int64_t a, int64_t b) { return a | b; };
 735   auto simp = distributiveImpl(env, src1, src2, OrInt, AndInt,
 736                                                 bit_or, bit_and);
 737   if (simp != nullptr) {
 738     return simp;
 739   }
 740   // X | X --> X
 741   if (src1 == src2) {
 742     return src1;
 743   }
 744   if (src2->hasConstVal()) {
 745     // X | 0 --> X
 746     if (src2->intVal() == 0) {
 747       return src1;
 748     }
 749     // X | (~0) --> ~0
 750     if (src2->intVal() == ~uint64_t(0)) {
 751       return cns(env, ~uint64_t(0));
 752     }
 753   }
 754   return nullptr;
 755 }
 756
 757 SSATmp* simplifyXorInt(State& env, const IRInstruction* inst) {
 758   auto const src1 = inst->src(0);
 759   auto const src2 = inst->src(1);
 760   auto bitxor = [](int64_t a, int64_t b) { return a ^ b; };
 761   if (auto simp = commutativeImpl(env, src1, src2, XorInt, bitxor)) {
 762     return simp;
 763   }
 764   // X ^ X --> 0
 765   if (src1 == src2) return cns(env, 0);
 766   // X ^ 0 --> X
 767   if (src2->hasConstVal(0)) return src1;
 768   return nullptr;
 769 }
 770
 771 SSATmp* xorTrueImpl(State& env, SSATmp* src) {
 772   auto const inst = src->inst();
 773   auto const op = inst->op();
 774
 775   // !(X cmp Y) --> X opposite_cmp Y
 776   if (auto negated = negateCmpOp(op)) {
 777     auto const s0 = inst->src(0);
 778     auto const s1 = inst->src(1);
 779     // We can't add new uses to reference counted types without a more
 780     // advanced availability analysis.
 781     if (!s0->type().maybe(TCounted) && !s1->type().maybe(TCounted)) {
 782       return gen(env, *negated, s0, s1);
 783     }
 784     return nullptr;
 785   }
 786
 787   switch (op) {
 788     // !!X --> X
 789     case XorBool:
 790       if (inst->src(1)->hasConstVal(true)) {
 791         // This is safe to add a new use to because inst->src(0) is a bool.
 792         assertx(inst->src(0)->isA(TBool));
 793         return inst->src(0);
 794       }
 795       return nullptr;
 796     case InstanceOfBitmask:
 797     case NInstanceOfBitmask:
 798       // This is safe because instanceofs don't take reference counted
 799       // arguments.
 800       assertx(!inst->src(0)->type().maybe(TCounted) &&
 801               !inst->src(1)->type().maybe(TCounted));
 802       return gen(
 803         env,
 804         (op == InstanceOfBitmask) ?
 805         NInstanceOfBitmask :
 806         InstanceOfBitmask,
 807         inst->src(0),
 808         inst->src(1)
 809       );
 810     default:
 811       break;
 812   }
 813
 814   return nullptr;
 815 }
 816
 817 SSATmp* simplifyXorBool(State& env, const IRInstruction* inst) {
 818   auto const src1 = inst->src(0);
 819   auto const src2 = inst->src(1);
 820
 821   // Both constants.
 822   if (src1->hasConstVal() && src2->hasConstVal()) {
 823     return cns(env, bool(src1->boolVal() ^ src2->boolVal()));
 824   }
 825
 826   // Canonicalize constants to the right.
 827   if (src1->hasConstVal() && !src2->hasConstVal()) {
 828     return gen(env, XorBool, src2, src1);
 829   }
 830
 831   // X^0 => X
 832   if (src2->hasConstVal(false)) return src1;
 833
 834   // X^1 => simplify "not" logic
 835   if (src2->hasConstVal(true)) return xorTrueImpl(env, src1);
 836   return nullptr;
 837 }
 838
 839 template<class Oper>
 840 SSATmp* shiftImpl(State& env, const IRInstruction* inst, Oper op) {
 841   auto const src1 = inst->src(0);
 842   auto const src2 = inst->src(1);
 843
 844   if (src1->hasConstVal()) {
 845     if (src1->intVal() == 0) {
 846       return cns(env, 0);
 847     }
 848
 849     if (src2->hasConstVal()) {
 850       return cns(env, op(src1->intVal(), src2->intVal()));
 851     }
 852   }
 853
 854   if (src2->hasConstVal() && src2->intVal() == 0) {
 855     return src1;
 856   }
 857
 858   return nullptr;
 859 }
 860
 861 SSATmp* simplifyShl(State& env, const IRInstruction* inst) {
 862   return shiftImpl(env, inst, [] (int64_t a, int64_t b) { return a << b; });
 863 }
 864
 865 SSATmp* simplifyShr(State& env, const IRInstruction* inst) {
 866   return shiftImpl(env, inst, [] (int64_t a, int64_t b) { return a >> b; });
 867 }
 868
 869 // This function isn't meant to perform the actual comparison at
 870 // compile-time. Instead, it performs the matching comparison against a
 871 // primitive type (usually bool).
 872 template<class T, class U>
 873 static bool cmpOp(Opcode opc, T a, U b) {
 874   switch (opc) {
 875   case GtBool:
 876   case GtInt:
 877   case GtStr:
 878   case GtStrInt:
 879   case GtObj:
 880   case GtArr:
 881   case GtRes: return a > b;
 882   case GteBool:
 883   case GteInt:
 884   case GteStr:
 885   case GteStrInt:
 886   case GteObj:
 887   case GteArr:
 888   case GteRes: return a >= b;
 889   case LtBool:
 890   case LtInt:
 891   case LtStr:
 892   case LtStrInt:
 893   case LtObj:
 894   case LtArr:
 895   case LtRes: return a < b;
 896   case LteBool:
 897   case LteInt:
 898   case LteStr:
 899   case LteStrInt:
 900   case LteObj:
 901   case LteArr:
 902   case LteRes: return a <= b;
 903   case SameStr:
 904   case SameObj:
 905   case SameArr:
 906   case EqBool:
 907   case EqInt:
 908   case EqStr:
 909   case EqStrInt:
 910   case EqObj:
 911   case EqArr:
 912   case EqRes: return a == b;
 913   case NSameStr:
 914   case NSameObj:
 915   case NSameArr:
 916   case NeqBool:
 917   case NeqInt:
 918   case NeqStr:
 919   case NeqStrInt:
 920   case NeqObj:
 921   case NeqArr:
 922   case NeqRes: return a != b;
 923   default:
 924     always_assert(false);
 925   }
 926 }
 927
 928 SSATmp* cmpBoolImpl(State& env,
 929                     Opcode opc,
 930                     const IRInstruction* const inst,
 931                     SSATmp* left,
 932                     SSATmp* right) {
 933   assertx(left->type() <= TBool);
 934   assertx(right->type() <= TBool);
 935
 936   auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
 937     return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
 938   };
 939
 940   // Identity optimization
 941   if (left == right) {
 942     return cns(env, cmpOp(opc, true, true));
 943   }
 944
 945   if (left->hasConstVal()) {
 946     // If both operands are constants, constant-fold them. Otherwise, move the
 947     // constant over to the right.
 948     if (right->hasConstVal()) {
 949       return cns(env, cmpOp(opc, left->boolVal(), right->boolVal()));
 950     } else {
 951       auto newOpc = [](Opcode opc) {
 952         switch (opc) {
 953           case GtBool:  return LtBool;
 954           case GteBool: return LteBool;
 955           case LtBool:  return GtBool;
 956           case LteBool: return GteBool;
 957           case EqBool:  return EqBool;
 958           case NeqBool: return NeqBool;
 959           default: always_assert(false);
 960         }
 961       }(opc);
 962       return newInst(newOpc, right, left);
 963     }
 964   }
 965
 966   if (right->hasConstVal()) {
 967     bool b = right->boolVal();
 968
 969     // The result of the comparison might be independent of the truth
 970     // value of the LHS. If so, then simplify.
 971     if (cmpOp(opc, false, b) == cmpOp(opc, true, b)) {
 972       return cns(env, cmpOp(opc, false, b));
 973     }
 974
 975     // There are only two distinct booleans - false and true (0 and 1).
 976     // From above, we know that (0 OP b) != (1 OP b).
 977     // Hence exactly one of (0 OP b) and (1 OP b) is true.
 978     // Hence there is exactly one boolean value of "left" that results in the
 979     // overall expression being true.
 980     // Hence we may check for equality with that boolean.
 981     if (opc != EqBool) {
 982       return newInst(EqBool, left, cns(env, !cmpOp(opc, false, b)));
 983     }
 984
 985     // If we reach here, this is an equality comparison against a
 986     // constant. Testing for equality with true simplifies to just the left
 987     // operand, while equality with false is the negation of the left operand
 988     // (equivalent to XORing with true).
 989     return b ? left : newInst(XorBool, left, cns(env, true));
 990   }
 991
 992   return nullptr;
 993 }
 994
 995 SSATmp* cmpIntImpl(State& env,
 996                    Opcode opc,
 997                    const IRInstruction* const inst,
 998                    SSATmp* left,
 999                    SSATmp* right) {
1000   assertx(left->type() <= TInt);
1001   assertx(right->type() <= TInt);
1002
1003   auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
1004     return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
1005   };
1006
1007   // Identity optimization
1008   if (left == right) {
1009     return cns(env, cmpOp(opc, true, true));
1010   }
1011
1012   if (left->hasConstVal()) {
1013     // If both operands are constants, constant-fold them. Otherwise, move the
1014     // constant over to the right.
1015     if (right->hasConstVal()) {
1016       return cns(env, cmpOp(opc, left->intVal(), right->intVal()));
1017     } else {
1018       auto newOpc = [](Opcode opc) {
1019         switch (opc) {
1020           case GtInt:  return LtInt;
1021           case GteInt: return LteInt;
1022           case LtInt:  return GtInt;
1023           case LteInt: return GteInt;
1024           case EqInt:  return EqInt;
1025           case NeqInt: return NeqInt;
1026           default: always_assert(false);
1027         }
1028       }(opc);
1029       return newInst(newOpc, right, left);
1030     }
1031   }
1032
1033   return nullptr;
1034 }
1035
1036 SSATmp* cmpStrImpl(State& env,
1037                    Opcode opc,
1038                    const IRInstruction* const inst,
1039                    SSATmp* left,
1040                    SSATmp* right) {
1041   assertx(left->type() <= TStr);
1042   assertx(right->type() <= TStr);
1043
1044   auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
1045     return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
1046   };
1047
1048   // Identity optimization
1049   if (left == right) {
1050     return cns(env, cmpOp(opc, true, true));
1051   }
1052
1053   if (left->hasConstVal()) {
1054     // If both operands are constants, constant-fold them. Otherwise, move the
1055     // constant over to the right.
1056     if (right->hasConstVal()) {
1057       if (opc == SameStr || opc == NSameStr) {
1058         return cns(
1059           env,
1060           cmpOp(opc, left->strVal()->same(right->strVal()), true)
1061         );
1062       } else {
1063         return cns(
1064           env,
1065           cmpOp(opc, left->strVal()->compare(right->strVal()), 0)
1066         );
1067       }
1068     } else {
1069       auto newOpc = [](Opcode opc) {
1070         switch (opc) {
1071           case GtStr:    return LtStr;
1072           case GteStr:   return LteStr;
1073           case LtStr:    return GtStr;
1074           case LteStr:   return GteStr;
1075           case EqStr:    return EqStr;
1076           case NeqStr:   return NeqStr;
1077           case SameStr:  return SameStr;
1078           case NSameStr: return NSameStr;
1079           default: always_assert(false);
1080         }
1081       }(opc);
1082       return newInst(newOpc, right, left);
1083     }
1084   }
1085
1086   // Comparisons against the empty string can be optimized to checks on the
1087   // string length.
1088   if (right->hasConstVal() && right->strVal()->empty()) {
1089     switch (opc) {
1090       case EqStr:
1091       case SameStr:
1092       case LteStr: return newInst(EqInt, gen(env, LdStrLen, left), cns(env, 0));
1093       case NeqStr:
1094       case NSameStr:
1095       case GtStr: return newInst(NeqInt, gen(env, LdStrLen, left), cns(env, 0));
1096       case LtStr: return cns(env, false);
1097       case GteStr: return cns(env, true);
1098       default: always_assert(false);
1099     }
1100   }
1101
1102   return nullptr;
1103 }
1104
1105 SSATmp* cmpStrIntImpl(State& env,
1106                       Opcode opc,
1107                       const IRInstruction* const inst,
1108                       SSATmp* left,
1109                       SSATmp* right) {
1110   assertx(left->type() <= TStr);
1111   assertx(right->type() <= TInt);
1112
1113   auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
1114     return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
1115   };
1116
1117   // If the string operand has a constant value, convert it to the appropriate
1118   // numeric and lower to a numeric comparison.
1119   if (left->hasConstVal()) {
1120     int64_t si;
1121     double sd;
1122     auto type =
1123       left->strVal()->isNumericWithVal(si, sd, true /* allow errors */);
1124     if (type == KindOfDouble) {
1125       auto dblOpc = [](Opcode opc) {
1126         switch (opc) {
1127           case GtStrInt:  return GtDbl;
1128           case GteStrInt: return GteDbl;
1129           case LtStrInt:  return LtDbl;
1130           case LteStrInt: return LteDbl;
1131           case EqStrInt:  return EqDbl;
1132           case NeqStrInt: return NeqDbl;
1133           default: always_assert(false);
1134         }
1135       }(opc);
1136       return newInst(
1137         dblOpc,
1138         cns(env, sd),
1139         gen(env, ConvIntToDbl, right)
1140       );
1141     } else {
1142       auto intOpc = [](Opcode opc) {
1143         switch (opc) {
1144           case GtStrInt:  return GtInt;
1145           case GteStrInt: return GteInt;
1146           case LtStrInt:  return LtInt;
1147           case LteStrInt: return LteInt;
1148           case EqStrInt:  return EqInt;
1149           case NeqStrInt: return NeqInt;
1150           default: always_assert(false);
1151         }
1152       }(opc);
1153       return newInst(
1154         intOpc,
1155         cns(env, type == KindOfNull ? (int64_t)0 : si),
1156         right
1157       );
1158     }
1159   }
1160
1161   return nullptr;
1162 }
1163
1164 SSATmp* cmpObjImpl(State& env,
1165                    Opcode opc,
1166                    const IRInstruction* const inst,
1167                    SSATmp* left,
1168                    SSATmp* right) {
1169   assertx(left->type() <= TObj);
1170   assertx(right->type() <= TObj);
1171
1172   // Identity optimization. Object comparisons can produce arbitrary
1173   // side-effects, so we can only eliminate the comparison if its checking for
1174   // sameness.
1175   if ((opc == SameObj || opc == NSameObj) && left == right) {
1176     return cns(env, cmpOp(opc, true, true));
1177   }
1178
1179   return nullptr;
1180 }
1181
1182 SSATmp* cmpArrImpl(State& env,
1183                    Opcode opc,
1184                    const IRInstruction* const inst,
1185                    SSATmp* left,
1186                    SSATmp* right) {
1187   assertx(left->type() <= TArr);
1188   assertx(right->type() <= TArr);
1189
1190   // Identity optimization. Array comparisons can produce arbitrary
1191   // side-effects, so we can only eliminate the comparison if its checking for
1192   // sameness.
1193   if ((opc == SameArr || opc == NSameArr) && left == right) {
1194     return cns(env, cmpOp(opc, true, true));
1195   }
1196
1197   return nullptr;
1198 }
1199
1200
1201 SSATmp* cmpResImpl(State& env,
1202                    Opcode opc,
1203                    const IRInstruction* const inst,
1204                    SSATmp* left,
1205                    SSATmp* right) {
1206   assertx(left->type() <= TRes);
1207   assertx(right->type() <= TRes);
1208
1209   // Identity optimization.
1210   if (left == right) {
1211     return cns(env, cmpOp(opc, true, true));
1212   }
1213
1214   return nullptr;
1215 }
1216
1217 #define X(name, type)                                                   \
1218   SSATmp* simplify##name(State& env, const IRInstruction* i) {          \
1219     return cmp##type##Impl(env, i->op(), i, i->src(0), i->src(1));      \
1220   }
1221
1222 X(GtBool, Bool)
1223 X(GteBool, Bool)
1224 X(LtBool, Bool)
1225 X(LteBool, Bool)
1226 X(EqBool, Bool)
1227 X(NeqBool, Bool)
1228
1229 X(GtInt, Int)
1230 X(GteInt, Int)
1231 X(LtInt, Int)
1232 X(LteInt, Int)
1233 X(EqInt, Int)
1234 X(NeqInt, Int)
1235
1236 X(GtStr, Str)
1237 X(GteStr, Str)
1238 X(LtStr, Str)
1239 X(LteStr, Str)
1240 X(EqStr, Str)
1241 X(NeqStr, Str)
1242 X(SameStr, Str)
1243 X(NSameStr, Str)
1244
1245 X(GtStrInt, StrInt)
1246 X(GteStrInt, StrInt)
1247 X(LtStrInt, StrInt)
1248 X(LteStrInt, StrInt)
1249 X(EqStrInt, StrInt)
1250 X(NeqStrInt, StrInt)
1251
1252 X(GtObj, Obj)
1253 X(GteObj, Obj)
1254 X(LtObj, Obj)
1255 X(LteObj, Obj)
1256 X(EqObj, Obj)
1257 X(NeqObj, Obj)
1258 X(SameObj, Obj)
1259 X(NSameObj, Obj)
1260
1261 X(GtArr, Arr)
1262 X(GteArr, Arr)
1263 X(LtArr, Arr)
1264 X(LteArr, Arr)
1265 X(EqArr, Arr)
1266 X(NeqArr, Arr)
1267 X(SameArr, Arr)
1268 X(NSameArr, Arr)
1269
1270 X(GtRes, Res)
1271 X(GteRes, Res)
1272 X(LtRes, Res)
1273 X(LteRes, Res)
1274 X(EqRes, Res)
1275 X(NeqRes, Res)
1276
1277 #undef X
1278
1279 SSATmp* simplifyCmpBool(State& env, const IRInstruction* inst) {
1280   auto const left = inst->src(0);
1281   auto const right = inst->src(1);
1282   assertx(left->type() <= TBool);
1283   assertx(right->type() <= TBool);
1284   if (left->hasConstVal() && right->hasConstVal()) {
1285     return cns(env, HPHP::compare(left->boolVal(), right->boolVal()));
1286   }
1287   return nullptr;
1288 }
1289
1290 SSATmp* simplifyCmpInt(State& env, const IRInstruction* inst) {
1291   auto const left = inst->src(0);
1292   auto const right = inst->src(1);
1293   assertx(left->type() <= TInt);
1294   assertx(right->type() <= TInt);
1295   if (left->hasConstVal() && right->hasConstVal()) {
1296     return cns(env, HPHP::compare(left->intVal(), right->intVal()));
1297   }
1298   return nullptr;
1299 }
1300
1301 SSATmp* simplifyCmpStr(State& env, const IRInstruction* inst) {
1302   auto const left = inst->src(0);
1303   auto const right = inst->src(1);
1304
1305   assertx(left->type() <= TStr);
1306   assertx(right->type() <= TStr);
1307
1308   auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
1309     return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
1310   };
1311
1312   if (left->hasConstVal()) {
1313     if (right->hasConstVal()) {
1314       return cns(env, HPHP::compare(left->strVal(), right->strVal()));
1315     } else if (left->strVal()->empty()) {
1316       // Comparisons against the empty string can be optimized to a comparison
1317       // on the string length.
1318       return newInst(CmpInt, cns(env, 0), gen(env, LdStrLen, right));
1319     }
1320   } else if (right->hasConstVal() && right->strVal()->empty()) {
1321     return newInst(CmpInt, gen(env, LdStrLen, left), cns(env, 0));
1322   }
1323
1324   return nullptr;
1325 }
1326
1327 SSATmp* simplifyCmpStrInt(State& env, const IRInstruction* inst) {
1328   auto const left = inst->src(0);
1329   auto const right = inst->src(1);
1330
1331   assertx(left->type() <= TStr);
1332   assertx(right->type() <= TInt);
1333
1334   auto newInst = [&](Opcode op, SSATmp* src1, SSATmp* src2) {
1335     return gen(env, op, inst ? inst->taken() : (Block*)nullptr, src1, src2);
1336   };
1337
1338   // If the string operand has a constant value, convert it to the appropriate
1339   // numeric and lower to a numeric comparison.
1340   if (left->hasConstVal()) {
1341     int64_t si;
1342     double sd;
1343     auto type =
1344       left->strVal()->isNumericWithVal(si, sd, true /* allow errors */);
1345     if (type == KindOfDouble) {
1346       return newInst(
1347         CmpDbl,
1348         cns(env, sd),
1349         gen(env, ConvIntToDbl, right)
1350       );
1351     } else {
1352       return newInst(
1353         CmpInt,
1354         cns(env, type == KindOfNull ? (int64_t)0 : si),
1355         right
1356       );
1357     }
1358   }
1359
1360   return nullptr;
1361 }
1362
1363 SSATmp* simplifyCmpRes(State& env, const IRInstruction* inst) {
1364   auto const left = inst->src(0);
1365   auto const right = inst->src(1);
1366   assertx(left->type() <= TRes);
1367   assertx(right->type() <= TRes);
1368   return (left == right) ? cns(env, 0) : nullptr;
1369 }
1370
1371 SSATmp* isTypeImpl(State& env, const IRInstruction* inst) {
1372   bool const trueSense = inst->op() == IsType;
1373   auto const type      = inst->typeParam();
1374   auto const src       = inst->src(0);
1375   auto const srcType   = src->type();
1376
1377   // If mightRelax(src) returns true, we can't generally depend on the src's
1378   // type. However, we always constrain the input to this opcode with at least
1379   // DataTypeSpecific, so we only have to skip the optimization if the
1380   // typeParam is specialized.
1381   if (mightRelax(env, src) && type.isSpecialized()) return nullptr;
1382
1383   // Testing for StaticStr will make you miss out on CountedStr, and vice versa,
1384   // and similarly for arrays. PHP treats both types of string the same, so if
1385   // the distinction matters to you here, be careful.
1386   assertx(IMPLIES(type <= TStr, type == TStr));
1387   assertx(IMPLIES(type <= TArr, type == TArr));
1388
1389   // The types are disjoint; the result must be false.
1390   if (!srcType.maybe(type)) {
1391     return cns(env, !trueSense);
1392   }
1393
1394   // The src type is a subtype of the tested type; the result must be true.
1395   if (srcType <= type) {
1396     return cns(env, trueSense);
1397   }
1398
1399   // At this point, either the tested type is a subtype of the src type, or they
1400   // are non-disjoint but neither is a subtype of the other. We can't simplify
1401   // this away.
1402   return nullptr;
1403 }
1404
1405 SSATmp* simplifyInstanceOf(State& env, const IRInstruction* inst) {
1406   auto const src1 = inst->src(0);
1407   auto const src2 = inst->src(1);
1408
1409   if (src2->isA(TNullptr)) return cns(env, false);
1410
1411   if (!src1->hasConstVal() || !src2->hasConstVal()) return nullptr;
1412
1413   return cns(env, src1->clsVal()->classof(src2->clsVal()));
1414 }
1415
1416 SSATmp* simplifyExtendsClass(State& env, const IRInstruction* i) {
1417   return simplifyInstanceOf(env, i);
1418 }
1419
1420 SSATmp* simplifyInstanceOfIface(State& env, const IRInstruction* inst) {
1421   auto const src1 = inst->src(0);
1422   auto const src2 = inst->src(1);
1423
1424   if (!src1->hasConstVal() || !src2->hasConstVal()) return nullptr;
1425
1426   return cns(env, src1->clsVal()->ifaceofDirect(src2->strVal()));
1427 }
1428
1429 SSATmp* simplifyIsType(State& env, const IRInstruction* i) {
1430   return isTypeImpl(env, i);
1431 }
1432
1433 SSATmp* simplifyIsNType(State& env, const IRInstruction* i) {
1434   return isTypeImpl(env, i);
1435 }
1436
1437 SSATmp* simplifyIsScalarType(State& env, const IRInstruction* inst) {
1438   auto const src = inst->src(0);
1439   if (src->type().isKnownDataType()) {
1440     return cns(env, src->isA(TInt | TDbl | TStr | TBool));
1441   }
1442   return nullptr;
1443 }
1444
1445 SSATmp* simplifyConcatStrStr(State& env, const IRInstruction* inst) {
1446   auto const src1 = inst->src(0);
1447   auto const src2 = inst->src(1);
1448   if (src1->hasConstVal(TStaticStr) &&
1449       src2->hasConstVal(TStaticStr)) {
1450     auto const str1 = const_cast<StringData*>(src1->strVal());
1451     auto const str2 = const_cast<StringData*>(src2->strVal());
1452     auto const sval = String::attach(concat_ss(str1, str2));
1453     return cns(env, makeStaticString(sval.get()));
1454   }
1455
1456   return nullptr;
1457 }
1458
1459 SSATmp* convToArrImpl(State& env, const IRInstruction* inst) {
1460   auto const src = inst->src(0);
1461   if (src->hasConstVal()) {
1462     Array arr = Array::Create(src->variantVal());
1463     return cns(env, ArrayData::GetScalarArray(arr.get()));
1464   }
1465   return nullptr;
1466 }
1467
1468 SSATmp* simplifyConvBoolToArr(State& env, const IRInstruction* inst) {
1469   return convToArrImpl(env, inst);
1470 }
1471
1472 SSATmp* simplifyConvIntToArr(State& env, const IRInstruction* inst) {
1473   return convToArrImpl(env, inst);
1474 }
1475
1476 SSATmp* simplifyConvDblToArr(State& env, const IRInstruction* inst) {
1477   return convToArrImpl(env, inst);
1478 }
1479
1480 SSATmp* simplifyConvStrToArr(State& env, const IRInstruction* inst) {
1481   return convToArrImpl(env, inst);
1482 }
1483
1484 SSATmp* simplifyConvArrToBool(State& env, const IRInstruction* inst) {
1485   auto const src = inst->src(0);
1486   auto const kind = src->type().arrSpec().kind();
1487   if (src->isA(TStaticArr) || (kind && !arrayKindNeedsVsize(*kind))) {
1488     return gen(env, ConvIntToBool, gen(env, CountArrayFast, src));
1489   }
1490   return nullptr;
1491 }
1492
1493 SSATmp* simplifyConvDblToBool(State& env, const IRInstruction* inst) {
1494   auto const src = inst->src(0);
1495   if (src->hasConstVal()) {
1496     bool const bval = src->dblVal();
1497     return cns(env, bval);
1498   }
1499   return nullptr;
1500 }
1501
1502 SSATmp* simplifyConvIntToBool(State& env, const IRInstruction* inst) {
1503   auto const src = inst->src(0);
1504   if (src->hasConstVal()) {
1505     bool const bval = src->intVal();
1506     return cns(env, bval);
1507   }
1508   return nullptr;
1509 }
1510
1511 SSATmp* simplifyConvStrToBool(State& env, const IRInstruction* inst) {
1512   auto const src = inst->src(0);
1513   if (src->hasConstVal()) {
1514     // only the strings "", and "0" convert to false, all other strings
1515     // are converted to true
1516     auto const str = src->strVal();
1517     return cns(env, !str->empty() && !str->isZero());
1518   }
1519   return nullptr;
1520 }
1521
1522 SSATmp* simplifyConvArrToDbl(State& env, const IRInstruction* inst) {
1523   auto const src = inst->src(0);
1524   if (src->hasConstVal()) {
1525     if (src->arrVal()->empty()) {
1526       return cns(env, 0.0);
1527     }
1528   }
1529   return nullptr;
1530 }
1531
1532 SSATmp* simplifyConvBoolToDbl(State& env, const IRInstruction* inst) {
1533   auto const src = inst->src(0);
1534   if (src->hasConstVal()) {
1535     double const dval = src->boolVal();
1536     return cns(env, dval);
1537   }
1538   return nullptr;
1539 }
1540
1541 SSATmp* simplifyConvIntToDbl(State& env, const IRInstruction* inst) {
1542   auto const src = inst->src(0);
1543   if (src->hasConstVal()) {
1544     double const dval = src->intVal();
1545     return cns(env, dval);
1546   }
1547   if (src->inst()->is(ConvBoolToInt)) {
1548     // This is safe, because the bool src is not reference counted.
1549     return gen(env, ConvBoolToDbl, src->inst()->src(0));
1550   }
1551   return nullptr;
1552 }
1553
1554 SSATmp* simplifyConvStrToDbl(State& env, const IRInstruction* inst) {
1555   auto const src = inst->src(0);
1556   return src->hasConstVal() ? cns(env, src->strVal()->toDouble()) : nullptr;
1557 }
1558
1559 SSATmp* simplifyConvArrToInt(State& env, const IRInstruction* inst) {
1560   auto const src = inst->src(0);
1561   if (src->hasConstVal()) {
1562     if (src->arrVal()->empty()) return cns(env, 0);
1563     return cns(env, 1);
1564   }
1565   return nullptr;
1566 }
1567
1568 SSATmp* simplifyConvBoolToInt(State& env, const IRInstruction* inst) {
1569   auto const src = inst->src(0);
1570   if (src->hasConstVal()) return cns(env, static_cast<int>(src->boolVal()));
1571   return nullptr;
1572 }
1573
1574 SSATmp* simplifyConvDblToInt(State& env, const IRInstruction* inst) {
1575   auto const src = inst->src(0);
1576   if (src->hasConstVal()) return cns(env, toInt64(src->dblVal()));
1577   return nullptr;
1578 }
1579
1580 SSATmp* simplifyConvStrToInt(State& env, const IRInstruction* inst) {
1581   auto const src = inst->src(0);
1582   return src->hasConstVal() ? cns(env, src->strVal()->toInt64()) : nullptr;
1583 }
1584
1585 SSATmp* simplifyConvBoolToStr(State& env, const IRInstruction* inst) {
1586   auto const src = inst->src(0);
1587   if (src->hasConstVal()) {
1588     if (src->boolVal()) return cns(env, s_1.get());
1589     return cns(env, s_empty.get());
1590   }
1591   return nullptr;
1592 }
1593
1594 SSATmp* simplifyConvDblToStr(State& env, const IRInstruction* inst) {
1595   auto const src = inst->src(0);
1596   if (src->hasConstVal()) {
1597     auto dblStr = String::attach(buildStringData(src->dblVal()));
1598     return cns(env, makeStaticString(dblStr));
1599   }
1600   return nullptr;
1601 }
1602
1603 SSATmp* simplifyConvIntToStr(State& env, const IRInstruction* inst) {
1604   auto const src = inst->src(0);
1605   if (src->hasConstVal()) {
1606     return cns(env,
1607       makeStaticString(folly::to<std::string>(src->intVal()))
1608     );
1609   }
1610   return nullptr;
1611 }
1612
1613 SSATmp* simplifyConvCellToBool(State& env, const IRInstruction* inst) {
1614   auto const src     = inst->src(0);
1615   auto const srcType = src->type();
1616
1617   if (srcType <= TBool) return src;
1618   if (srcType <= TNull) return cns(env, false);
1619   if (srcType <= TArr)  return gen(env, ConvArrToBool, src);
1620   if (srcType <= TDbl)  return gen(env, ConvDblToBool, src);
1621   if (srcType <= TInt)  return gen(env, ConvIntToBool, src);
1622   if (srcType <= TStr)  return gen(env, ConvStrToBool, src);
1623   if (srcType <= TObj) {
1624     if (auto cls = srcType.clsSpec().cls()) {
1625       // We need to exclude interfaces like ConstSet.  For now, just
1626       // skip anything that's an interface.
1627       if (!(cls->attrs() & AttrInterface)) {
1628         // t3429711 we should test cls->m_ODAttr
1629         // here, but currently it doesnt have all
1630         // the flags set.
1631         if (!cls->instanceCtor()) {
1632           return cns(env, true);
1633         }
1634       }
1635     }
1636     return gen(env, ConvObjToBool, src);
1637   }
1638   if (srcType <= TRes)  return cns(env, true);
1639
1640   return nullptr;
1641 }
1642
1643 SSATmp* simplifyConvCellToStr(State& env, const IRInstruction* inst) {
1644   auto const src        = inst->src(0);
1645   auto const srcType    = src->type();
1646   auto const catchTrace = inst->taken();
1647
1648   if (srcType <= TBool)   return gen(env, ConvBoolToStr, src);
1649   if (srcType <= TNull)   return cns(env, s_empty.get());
1650   if (srcType <= TArr)  {
1651     gen(env, RaiseNotice, catchTrace,
1652         cns(env, makeStaticString("Array to string conversion")));
1653     return cns(env, s_Array.get());
1654   }
1655   if (srcType <= TDbl)    return gen(env, ConvDblToStr, src);
1656   if (srcType <= TInt)    return gen(env, ConvIntToStr, src);
1657   if (srcType <= TStr) {
1658     gen(env, IncRef, src);
1659     return src;
1660   }
1661   if (srcType <= TObj)    return gen(env, ConvObjToStr, catchTrace, src);
1662   if (srcType <= TRes)    return gen(env, ConvResToStr, catchTrace, src);
1663
1664   return nullptr;
1665 }
1666
1667 SSATmp* simplifyConvCellToInt(State& env, const IRInstruction* inst) {
1668   auto const src      = inst->src(0);
1669   auto const srcType  = src->type();
1670
1671   if (srcType <= TInt)  return src;
1672   if (srcType <= TNull) return cns(env, 0);
1673   if (srcType <= TArr)  return gen(env, ConvArrToInt, src);
1674   if (srcType <= TBool) return gen(env, ConvBoolToInt, src);
1675   if (srcType <= TDbl)  return gen(env, ConvDblToInt, src);
1676   if (srcType <= TStr)  return gen(env, ConvStrToInt, src);
1677   if (srcType <= TObj)  return gen(env, ConvObjToInt, inst->taken(), src);
1678   if (srcType <= TRes)  return gen(env, ConvResToInt, src);
1679
1680   return nullptr;
1681 }
1682
1683 SSATmp* simplifyConvCellToDbl(State& env, const IRInstruction* inst) {
1684   auto const src      = inst->src(0);
1685   auto const srcType  = src->type();
1686
1687   if (srcType <= TDbl)  return src;
1688   if (srcType <= TNull) return cns(env, 0.0);
1689   if (srcType <= TArr)  return gen(env, ConvArrToDbl, src);
1690   if (srcType <= TBool) return gen(env, ConvBoolToDbl, src);
1691   if (srcType <= TInt)  return gen(env, ConvIntToDbl, src);
1692   if (srcType <= TStr)  return gen(env, ConvStrToDbl, src);
1693   if (srcType <= TObj)  return gen(env, ConvObjToDbl, inst->taken(), src);
1694   if (srcType <= TRes)  return gen(env, ConvResToDbl, src);
1695
1696   return nullptr;
1697 }
1698
1699 SSATmp* simplifyConvObjToBool(State& env, const IRInstruction* inst) {
1700   auto const ty = inst->src(0)->type();
1701
1702   if (!typeMightRelax(inst->src(0)) &&
1703       ty < TObj &&
1704       ty.clsSpec().cls() &&
1705       ty.clsSpec().cls()->isCollectionClass()) {
1706     return gen(env, ColIsNEmpty, inst->src(0));
1707   }
1708   return nullptr;
1709 }
1710
1711 SSATmp* simplifyConvCellToObj(State& env, const IRInstruction* inst) {
1712   if (inst->src(0)->isA(TObj)) return inst->src(0);
1713   return nullptr;
1714 }
1715
1716 SSATmp* simplifyCoerceCellToBool(State& env, const IRInstruction* inst) {
1717   auto const src     = inst->src(0);
1718   auto const srcType = src->type();
1719
1720   if (srcType.subtypeOfAny(TBool, TNull, TDbl,
1721                            TInt, TStr)) {
1722     return gen(env, ConvCellToBool, src);
1723   }
1724
1725   // We actually know that any other type will fail causing us to side exit
1726   // but there's no easy way to optimize for that
1727
1728   return nullptr;
1729 }
1730
1731 SSATmp* simplifyCoerceCellToInt(State& env, const IRInstruction* inst) {
1732   auto const src      = inst->src(0);
1733   auto const srcType  = src->type();
1734
1735   if (srcType.subtypeOfAny(TInt, TBool, TNull, TDbl,
1736                            TBool)) {
1737     return gen(env, ConvCellToInt, inst->taken(), src);
1738   }
1739
1740   if (srcType <= TStr) return gen(env, CoerceStrToInt, inst->taken(),
1741                                        *inst->extra<CoerceCellToInt>(), src);
1742
1743   // We actually know that any other type will fail causing us to side exit
1744   // but there's no easy way to optimize for that
1745
1746   return nullptr;
1747 }
1748
1749 SSATmp* simplifyCoerceCellToDbl(State& env, const IRInstruction* inst) {
1750   auto const src      = inst->src(0);
1751   auto const srcType  = src->type();
1752
1753   if (srcType.subtypeOfAny(TInt, TBool, TNull, TDbl,
1754                            TBool)) {
1755     return gen(env, ConvCellToDbl, inst->taken(), src);
1756   }
1757
1758   if (srcType <= TStr) return gen(env, CoerceStrToDbl, inst->taken(),
1759                                        *inst->extra<CoerceCellToDbl>(), src);
1760
1761   // We actually know that any other type will fail causing us to side exit
1762   // but there's no easy way to optimize for that
1763
1764   return nullptr;
1765 }
1766
1767 SSATmp* roundImpl(State& env, const IRInstruction* inst, double (*op)(double)) {
1768   auto const src  = inst->src(0);
1769
1770   if (src->hasConstVal()) {
1771     return cns(env, op(src->dblVal()));
1772   }
1773
1774   auto srcInst = src->inst();
1775   if (srcInst->op() == ConvIntToDbl || srcInst->op() == ConvBoolToDbl) {
1776     return src;
1777   }
1778
1779   return nullptr;
1780 }
1781
1782 SSATmp* simplifyFloor(State& env, const IRInstruction* inst) {
1783   return roundImpl(env, inst, floor);
1784 }
1785
1786 SSATmp* simplifyCeil(State& env, const IRInstruction* inst) {
1787   return roundImpl(env, inst, ceil);
1788 }
1789
1790 SSATmp* simplifyUnboxPtr(State& env, const IRInstruction* inst) {
1791   if (inst->src(0)->isA(TPtrToCell)) {
1792     return inst->src(0);
1793   }
1794   return nullptr;
1795 }
1796
1797 SSATmp* simplifyBoxPtr(State& env, const IRInstruction* inst) {
1798   if (inst->src(0)->isA(TPtrToBoxedCell)) {
1799     return inst->src(0);
1800   }
1801   return nullptr;
1802 }
1803
1804 SSATmp* simplifyCheckInit(State& env, const IRInstruction* inst) {
1805   auto const srcType = inst->src(0)->type();
1806   assertx(!srcType.maybe(TPtrToGen));
1807   assertx(inst->taken());
1808   if (!srcType.maybe(TUninit)) return gen(env, Nop);
1809   return mergeBranchDests(env, inst);
1810 }
1811
1812 SSATmp* simplifyCheckInitMem(State& env, const IRInstruction* inst) {
1813   return mergeBranchDests(env, inst);
1814 }
1815
1816 SSATmp* simplifyCheckInitProps(State& env, const IRInstruction* inst) {
1817   return mergeBranchDests(env, inst);
1818 }
1819
1820 SSATmp* simplifyCheckInitSProps(State& env, const IRInstruction* inst) {
1821   return mergeBranchDests(env, inst);
1822 }
1823
1824 SSATmp* simplifyInitObjProps(State& env, const IRInstruction* inst) {
1825   auto const cls = inst->extra<InitObjProps>()->cls;
1826   if (cls->getODAttrs() == 0 && cls->numDeclProperties() == 0) {
1827     return gen(env, Nop);
1828   }
1829   return nullptr;
1830 }
1831
1832 SSATmp* simplifyCheckType(State& env, const IRInstruction* inst) {
1833   auto const typeParam = inst->typeParam();
1834   auto const srcType = inst->src(0)->type();
1835
1836   if (!srcType.maybe(typeParam) || inst->next() == inst->taken()) {
1837     /*
1838      * Convert the check into a Jmp.  The dest of the CheckType (which would've
1839      * been Bottom) is now never going to be defined, so we return a Bottom.
1840      */
1841     gen(env, Jmp, inst->taken());
1842     return cns(env, TBottom);
1843   }
1844
1845   auto const newType = srcType & typeParam;
1846   if (srcType <= newType) {
1847     // The type of the src is the same or more refined than type, so the guard
1848     // is unnecessary.
1849     return inst->src(0);
1850   }
1851
1852   return nullptr;
1853 }
1854
1855 SSATmp* simplifyCheckTypeMem(State& env, const IRInstruction* inst) {
1856   if (inst->next() == inst->taken() ||
1857       inst->typeParam() == TBottom) {
1858     return gen(env, Jmp, inst->taken());
1859   }
1860
1861   return nullptr;
1862 }
1863
1864 SSATmp* simplifyAssertType(State& env, const IRInstruction* inst) {
1865   auto const src = inst->src(0);
1866
1867   return canSimplifyAssertType(inst, src->type(), mightRelax(env, src))
1868     ? src
1869     : nullptr;
1870 }
1871
1872 SSATmp* simplifyCheckLoc(State& env, const IRInstruction* inst) {
1873   return mergeBranchDests(env, inst);
1874 }
1875
1876 SSATmp* simplifyCheckStk(State& env, const IRInstruction* inst) {
1877   return mergeBranchDests(env, inst);
1878 }
1879
1880 SSATmp* simplifyCheckStaticLocInit(State& env, const IRInstruction* inst) {
1881   return mergeBranchDests(env, inst);
1882 }
1883
1884 SSATmp* simplifyCheckRefInner(State& env, const IRInstruction* inst) {
1885   // Ref inner cells are at worst InitCell, so don't bother checking for that.
1886   if (TInitCell <= inst->typeParam()) {
1887     return gen(env, Nop);
1888   }
1889   return mergeBranchDests(env, inst);
1890 }
1891
1892 SSATmp* simplifyDefLabel(State& env, const IRInstruction* inst) {
1893   if (inst->numDsts() == 0) {
1894     return gen(env, Nop);
1895   }
1896   return nullptr;
1897 }
1898
1899 SSATmp* decRefImpl(State& env, const IRInstruction* inst) {
1900   auto const src = inst->src(0);
1901   if (!mightRelax(env, src) && !src->type().maybe(TCounted)) {
1902     return gen(env, Nop);
1903   }
1904   return nullptr;
1905 }
1906
1907 SSATmp* simplifyDecRef(State& env, const IRInstruction* inst) {
1908   return decRefImpl(env, inst);
1909 }
1910
1911 SSATmp* simplifyDecRefNZ(State& env, const IRInstruction* inst) {
1912   return decRefImpl(env, inst);
1913 }
1914
1915 SSATmp* simplifyIncRef(State& env, const IRInstruction* inst) {
1916   auto const src = inst->src(0);
1917   if (!mightRelax(env, src) && !src->type().maybe(TCounted)) {
1918     return gen(env, Nop);
1919   }
1920   return nullptr;
1921 }
1922
1923 SSATmp* simplifyIncRefCtx(State& env, const IRInstruction* inst) {
1924   auto const ctx = inst->src(0);
1925   if (ctx->isA(TObj)) {
1926     return gen(env, IncRef, ctx);
1927   } else if (!mightRelax(env, ctx) && !ctx->type().maybe(TCounted)) {
1928     return gen(env, Nop);
1929   }
1930
1931   return nullptr;
1932 }
1933
1934 SSATmp* condJmpImpl(State& env, const IRInstruction* inst) {
1935   assertx(inst->is(JmpZero, JmpNZero));
1936   // Both ways go to the same block.
1937   if (inst->taken() == inst->next()) {
1938     assertx(inst->taken() != nullptr);
1939     return gen(env, Jmp, inst->taken());
1940   }
1941
1942   auto const src = inst->src(0);
1943   auto const srcInst = src->inst();
1944
1945   // Constant propagate.
1946   if (src->hasConstVal()) {
1947     bool val = src->isA(TBool) ? src->boolVal()
1948                                : static_cast<bool>(src->intVal());
1949     if (val == inst->is(JmpNZero)) {
1950       // always taken
1951       assertx(inst->taken());
1952       return gen(env, Jmp, inst->taken());
1953     }
1954     // Never taken. Since simplify() is also run when building the IR,
1955     // inst->next() could be nullptr at this moment.
1956     return gen(env, Nop);
1957   }
1958
1959   auto absorb = [&](){
1960     return gen(env, inst->op(), inst->taken(), srcInst->src(0));
1961   };
1962   auto absorbOpp = [&](){
1963     return gen(env,
1964                inst->op() == JmpZero ? JmpNZero : JmpZero,
1965                inst->taken(),
1966                srcInst->src(0)
1967               );
1968   };
1969
1970   // Absorb negations.
1971   if (srcInst->is(XorBool) && srcInst->src(1)->hasConstVal(true)) {
1972     return absorbOpp();
1973   }
1974
1975   // Absorb ConvIntToBool.
1976   if (srcInst->is(ConvIntToBool)) {
1977     return absorb();
1978   }
1979
1980   // Absorb boolean comparisons.
1981   if (srcInst->is(EqBool) && srcInst->src(1)->hasConstVal()) {
1982     return srcInst->src(1)->boolVal() ? absorb() : absorbOpp();
1983   }
1984   if (srcInst->is(NeqBool) && srcInst->src(1)->hasConstVal()) {
1985     return srcInst->src(1)->boolVal() ? absorbOpp() : absorb();
1986   }
1987
1988   // Absorb integer comparisons against constant zero.
1989   if (srcInst->is(EqInt) && srcInst->src(1)->hasConstVal(0)) {
1990     return absorbOpp();
1991   }
1992   if (srcInst->is(NeqInt) && srcInst->src(1)->hasConstVal(0)) {
1993     return absorb();
1994   }
1995
1996   return nullptr;
1997 }
1998
1999 SSATmp* simplifyJmpZero(State& env, const IRInstruction* i) {
2000   return condJmpImpl(env, i);
2001 }
2002
2003 SSATmp* simplifyJmpNZero(State& env, const IRInstruction* i) {
2004   return condJmpImpl(env, i);
2005 }
2006
2007
2008 SSATmp* simplifyAssertNonNull(State& env, const IRInstruction* inst) {
2009   if (!inst->src(0)->type().maybe(TNullptr)) {
2010     return inst->src(0);
2011   }
2012   return nullptr;
2013 }
2014
2015 SSATmp* simplifyCheckPackedArrayBounds(State& env, const IRInstruction* inst) {
2016   auto const array = inst->src(0);
2017   auto const idx   = inst->src(1);
2018   if (!idx->hasConstVal()) return mergeBranchDests(env, inst);
2019
2020   auto const idxVal = idx->intVal();
2021   switch (packedArrayBoundsStaticCheck(array->type(), idxVal)) {
2022   case PackedBounds::In:       return gen(env, Nop);
2023   case PackedBounds::Out:      return gen(env, Jmp, inst->taken());
2024   case PackedBounds::Unknown:  break;
2025   }
2026
2027   return mergeBranchDests(env, inst);
2028 }
2029
2030 SSATmp* arrIntKeyImpl(State& env, const IRInstruction* inst) {
2031   auto const arr = inst->src(0);
2032   auto const idx = inst->src(1);
2033   assertx(arr->hasConstVal(TArr));
2034   if (!idx->hasConstVal()) return nullptr;
2035   auto const value = arr->arrVal()->nvGet(idx->intVal());
2036   return value ? cns(env, *value) : nullptr;
2037 }
2038
2039 SSATmp* arrStrKeyImpl(State& env, const IRInstruction* inst) {
2040   auto const arr = inst->src(0);
2041   auto const idx = inst->src(1);
2042   assertx(arr->hasConstVal(TArr));
2043   if (!idx->hasConstVal()) return nullptr;
2044   auto const value = [&] {
2045     int64_t val;
2046     if (idx->strVal()->isStrictlyInteger(val)) {
2047       return arr->arrVal()->nvGet(val);
2048     }
2049     return arr->arrVal()->nvGet(idx->strVal());
2050   }();
2051   return value ? cns(env, *value) : nullptr;
2052 }
2053
2054 SSATmp* simplifyArrayGet(State& env, const IRInstruction* inst) {
2055   if (inst->src(0)->hasConstVal()) {
2056     if (inst->src(1)->type() <= TInt) return arrIntKeyImpl(env, inst);
2057     if (inst->src(1)->type() <= TStr) return arrStrKeyImpl(env, inst);
2058   }
2059   return nullptr;
2060 }
2061
2062 SSATmp* simplifyCount(State& env, const IRInstruction* inst) {
2063   auto const val = inst->src(0);
2064   auto const ty = val->type();
2065
2066   if (ty <= TNull) return cns(env, 0);
2067
2068   auto const oneTy = TBool | TInt | TDbl | TStr | TRes;
2069   if (ty <= oneTy) return cns(env, 1);
2070
2071   if (ty <= TArr) return gen(env, CountArray, val);
2072
2073   if (ty < TObj) {
2074     auto const cls = ty.clsSpec().cls();
2075     if (!mightRelax(env, val) && cls != nullptr && cls->isCollectionClass()) {
2076       return gen(env, CountCollection, val);
2077     }
2078   }
2079   return nullptr;
2080 }
2081
2082 SSATmp* simplifyCountArrayFast(State& env, const IRInstruction* inst) {
2083   auto const src = inst->src(0);
2084   if (inst->src(0)->hasConstVal(TArr)) return cns(env, src->arrVal()->size());
2085   auto const arrSpec = src->type().arrSpec();
2086   auto const at = arrSpec.type();
2087   if (!at) return nullptr;
2088   using A = RepoAuthType::Array;
2089   switch (at->tag()) {
2090   case A::Tag::Packed:
2091     if (at->emptiness() == A::Empty::No) {
2092       return cns(env, at->size());
2093     }
2094     break;
2095   case A::Tag::PackedN:
2096     break;
2097   }
2098   return nullptr;
2099 }
2100
2101 SSATmp* simplifyCountArray(State& env, const IRInstruction* inst) {
2102   auto const src = inst->src(0);
2103   auto const ty = src->type();
2104
2105   if (src->hasConstVal()) return cns(env, src->arrVal()->size());
2106
2107   auto const kind = ty.arrSpec().kind();
2108
2109   if (kind && !mightRelax(env, src) && !arrayKindNeedsVsize(*kind))
2110     return gen(env, CountArrayFast, src);
2111   else
2112     return nullptr;
2113 }
2114
2115 SSATmp* simplifyLdClsName(State& env, const IRInstruction* inst) {
2116   auto const src = inst->src(0);
2117   return src->hasConstVal(TCls) ? cns(env, src->clsVal()->name()) : nullptr;
2118 }
2119
2120 SSATmp* simplifyLdStrLen(State& env, const IRInstruction* inst) {
2121   auto const src = inst->src(0);
2122   return src->hasConstVal(TStr) ? cns(env, src->strVal()->size()) : nullptr;
2123 }
2124
2125 SSATmp* simplifyCallBuiltin(State& env, const IRInstruction* inst) {
2126   auto const callee = inst->extra<CallBuiltin>()->callee;
2127   auto const args = inst->srcs();
2128
2129
2130   bool const arg2IsCollection = args.size() == 3 &&
2131     args[2]->isA(TObj) &&
2132     args[2]->type().clsSpec() &&
2133     args[2]->type().clsSpec().cls()->isCollectionClass() &&
2134     !mightRelax(env, args[2]);
2135
2136   if (arg2IsCollection) {
2137     if (callee->name()->isame(s_isEmpty.get())) {
2138       FTRACE(3, "simplifying collection: {}\n", callee->name()->data());
2139       return gen(env, ColIsEmpty, args[2]);
2140     }
2141     if (callee->name()->isame(s_count.get())) {
2142       FTRACE(3, "simplifying collection: {}\n", callee->name()->data());
2143       return gen(env, CountCollection, args[2]);
2144     }
2145   }
2146
2147   bool const arg2IsWaitHandle = !arg2IsCollection &&
2148     args.size() == 3 &&
2149     args[2]->isA(TObj) &&
2150     args[2]->type().clsSpec() &&
2151     args[2]->type().clsSpec().cls()->classof(c_WaitHandle::classof()) &&
2152     !mightRelax(env, args[2]);
2153
2154   if (arg2IsWaitHandle) {
2155     const auto genState = [&] (Opcode op, int64_t whstate) -> SSATmp* {
2156       // these methods all spring from the base class
2157       assert(callee->cls()->name()->isame(s_WaitHandle.get()));
2158       const auto state = gen(env, LdWHState, args[2]);
2159       return gen(env, op, state, cns(env, whstate));
2160     };
2161     const auto methName = callee->name();
2162     if (methName->isame(s_isFinished.get())) {
2163       return genState(LteInt, int64_t{c_WaitHandle::STATE_FAILED});
2164     }
2165     if (methName->isame(s_isSucceeded.get())) {
2166       return genState(EqInt, int64_t{c_WaitHandle::STATE_SUCCEEDED});
2167     }
2168     if (methName->isame(s_isFailed.get())) {
2169       return genState(EqInt, int64_t{c_WaitHandle::STATE_FAILED});
2170     }
2171   }
2172
2173   return nullptr;
2174 }
2175
2176 SSATmp* simplifyIsWaitHandle(State& env, const IRInstruction* inst) {
2177   if (mightRelax(env, inst->src(0))) return nullptr;
2178
2179   bool baseIsWaitHandle = inst->src(0)->isA(TObj) &&
2180     inst->src(0)->type().clsSpec() &&
2181     inst->src(0)->type().clsSpec().cls()->classof(c_WaitHandle::classof());
2182   if (baseIsWaitHandle) {
2183     return cns(env, true);
2184   }
2185   return nullptr;
2186 }
2187
2188 SSATmp* simplifyIsCol(State& env, const IRInstruction* inst) {
2189   auto const ty = inst->src(0)->type();
2190
2191   if (!typeMightRelax(inst->src(0)) &&
2192       ty < TObj &&
2193       ty.clsSpec().cls()) {
2194     return cns(env, ty.clsSpec().cls()->isCollectionClass());
2195   }
2196   return nullptr;
2197 }
2198
2199 SSATmp* simplifyHasToString(State& env, const IRInstruction* inst) {
2200   auto const src = inst->src(0);
2201
2202   if (!mightRelax(env, src) &&
2203       src->isA(TObj) &&
2204       src->type().clsSpec()) {
2205     return cns(
2206       env,
2207       src->type().clsSpec().cls()->getToString() != nullptr
2208     );
2209   }
2210   return nullptr;
2211 }
2212
2213 SSATmp* simplifyOrdStr(State& env, const IRInstruction* inst) {
2214   const auto src = inst->src(0);
2215   if (src->hasConstVal(TStr)) {
2216     // a static string is passed in, resolve with a constant.
2217     unsigned char first = src->strVal()->data()[0];
2218     return cns(env, int64_t{first});
2219   }
2220   return nullptr;
2221 }
2222
2223 SSATmp* ldImpl(State& env, const IRInstruction* inst) {
2224   if (env.typesMightRelax) return nullptr;
2225
2226   auto const t = inst->typeParam();
2227
2228   return t.hasConstVal() ||
2229          t.subtypeOfAny(TUninit, TInitNull, TNullptr)
2230     ? cns(env, t)
2231     : nullptr;
2232 }
2233
2234 SSATmp* simplifyLdLoc(State& env, const IRInstruction* inst) {
2235   return ldImpl(env, inst);
2236 }
2237
2238 SSATmp* simplifyLdStk(State& env, const IRInstruction* inst) {
2239   return ldImpl(env, inst);
2240 }
2241
2242 SSATmp* simplifyJmpSwitchDest(State& env, const IRInstruction* inst) {
2243   auto const index = inst->src(0);
2244   if (!index->hasConstVal(TInt)) return nullptr;
2245
2246   auto indexVal = index->intVal();
2247   auto const sp = inst->src(1);
2248   auto const fp = inst->src(2);
2249   auto const& extra = *inst->extra<JmpSwitchDest>();
2250
2251   if (indexVal < 0 || indexVal >= extra.cases) {
2252     // Instruction is unreachable.
2253     return gen(env, Halt);
2254   }
2255
2256   auto const newExtra = ReqBindJmpData{extra.targets[indexVal], extra.invSPOff,
2257                                        extra.irSPOff, TransFlags{}};
2258   return gen(env, ReqBindJmp, newExtra, sp, fp);
2259 }
2260
2261 SSATmp* simplifyCheckRange(State& env, const IRInstruction* inst) {
2262   auto val = inst->src(0);
2263   auto limit = inst->src(1);
2264
2265   // CheckRange returns (0 <= val < limit).
2266   if (val->hasConstVal(TInt)) {
2267     if (val->intVal() < 0) return cns(env, false);
2268
2269     if (limit->hasConstVal(TInt)) {
2270       return cns(env, val->intVal() < limit->intVal());
2271     }
2272   }
2273
2274   if (limit->hasConstVal(TInt) && limit->intVal() <= 0) return cns(env, false);
2275
2276   return nullptr;
2277 }
2278
2279 //////////////////////////////////////////////////////////////////////
2280
2281 SSATmp* simplifyWork(State& env, const IRInstruction* inst) {
2282   env.insts.push(inst);
2283   SCOPE_EXIT {
2284     assertx(env.insts.top() == inst);
2285     env.insts.pop();
2286   };
2287
2288 #define X(x) case x: return simplify##x(env, inst);
2289   switch (inst->op()) {
2290   X(Shl)
2291   X(Shr)
2292   X(AbsDbl)
2293   X(AssertNonNull)
2294   X(BoxPtr)
2295   X(CallBuiltin)
2296   X(Ceil)
2297   X(CheckInit)
2298   X(CheckInitMem)
2299   X(CheckInitProps)
2300   X(CheckInitSProps)
2301   X(CheckLoc)
2302   X(CheckRefInner)
2303   X(CheckStk)
2304   X(CheckStaticLocInit)
2305   X(CheckType)
2306   X(CheckTypeMem)
2307   X(AssertType)
2308   X(CheckPackedArrayBounds)
2309   X(CoerceCellToBool)
2310   X(CoerceCellToDbl)
2311   X(CoerceCellToInt)
2312   X(ConcatStrStr)
2313   X(ConvArrToBool)
2314   X(ConvArrToDbl)
2315   X(ConvArrToInt)
2316   X(ConvBoolToArr)
2317   X(ConvBoolToDbl)
2318   X(ConvBoolToInt)
2319   X(ConvBoolToStr)
2320   X(ConvCellToBool)
2321   X(ConvCellToDbl)
2322   X(ConvCellToInt)
2323   X(ConvCellToObj)
2324   X(ConvCellToStr)
2325   X(ConvClsToCctx)
2326   X(ConvDblToArr)
2327   X(ConvDblToBool)
2328   X(ConvDblToInt)
2329   X(ConvDblToStr)
2330   X(ConvIntToArr)
2331   X(ConvIntToBool)
2332   X(ConvIntToDbl)
2333   X(ConvIntToStr)
2334   X(ConvObjToBool)
2335   X(ConvStrToArr)
2336   X(ConvStrToBool)
2337   X(ConvStrToDbl)
2338   X(ConvStrToInt)
2339   X(Count)
2340   X(CountArray)
2341   X(CountArrayFast)
2342   X(DecRef)
2343   X(DecRefNZ)
2344   X(DefLabel)
2345   X(DivDbl)
2346   X(ExtendsClass)
2347   X(Floor)
2348   X(GetCtxFwdCall)
2349   X(IncRef)
2350   X(IncRefCtx)
2351   X(InitObjProps)
2352   X(InstanceOf)
2353   X(InstanceOfIface)
2354   X(IsNType)
2355   X(IsScalarType)
2356   X(IsType)
2357   X(IsWaitHandle)
2358   X(IsCol)
2359   X(HasToString)
2360   X(LdClsCtx)
2361   X(LdClsName)
2362   X(LdStrLen)
2363   X(CheckCtxThis)
2364   X(CastCtxThis)
2365   X(LdObjClass)
2366   X(LdObjInvoke)
2367   X(Mov)
2368   X(UnboxPtr)
2369   X(JmpZero)
2370   X(JmpNZero)
2371   X(OrInt)
2372   X(AddInt)
2373   X(SubInt)
2374   X(MulInt)
2375   X(AddDbl)
2376   X(SubDbl)
2377   X(MulDbl)
2378   X(Mod)
2379   X(AndInt)
2380   X(XorInt)
2381   X(XorBool)
2382   X(AddIntO)
2383   X(SubIntO)
2384   X(MulIntO)
2385   X(GtBool)
2386   X(GteBool)
2387   X(LtBool)
2388   X(LteBool)
2389   X(EqBool)
2390   X(NeqBool)
2391   X(CmpBool)
2392   X(GtInt)
2393   X(GteInt)
2394   X(LtInt)
2395   X(LteInt)
2396   X(EqInt)
2397   X(NeqInt)
2398   X(CmpInt)
2399   X(GtStr)
2400   X(GteStr)
2401   X(LtStr)
2402   X(LteStr)
2403   X(EqStr)
2404   X(NeqStr)
2405   X(SameStr)
2406   X(NSameStr)
2407   X(CmpStr)
2408   X(GtStrInt)
2409   X(GteStrInt)
2410   X(LtStrInt)
2411   X(LteStrInt)
2412   X(EqStrInt)
2413   X(NeqStrInt)
2414   X(CmpStrInt)
2415   X(GtObj)
2416   X(GteObj)
2417   X(LtObj)
2418   X(LteObj)
2419   X(EqObj)
2420   X(NeqObj)
2421   X(SameObj)
2422   X(NSameObj)
2423   X(GtArr)
2424   X(GteArr)
2425   X(LtArr)
2426   X(LteArr)
2427   X(EqArr)
2428   X(NeqArr)
2429   X(SameArr)
2430   X(NSameArr)
2431   X(GtRes)
2432   X(GteRes)
2433   X(LtRes)
2434   X(LteRes)
2435   X(EqRes)
2436   X(NeqRes)
2437   X(CmpRes)
2438   X(ArrayGet)
2439   X(OrdStr)
2440   X(LdLoc)
2441   X(LdStk)
2442   X(JmpSwitchDest)
2443   X(CheckRange)
2444   default: break;
2445   }
2446 #undef X
2447   return nullptr;
2448 }
2449
2450 //////////////////////////////////////////////////////////////////////
2451
2452 }
2453
2454 //////////////////////////////////////////////////////////////////////
2455
2456 bool canSimplifyAssertType(const IRInstruction* inst,
2457                            const Type srcType,
2458                            bool srcMightRelax) {
2459   assert(inst->is(AssertType, AssertLoc, AssertStk));
2460
2461   auto const typeParam = inst->typeParam();
2462
2463   if (!srcType.maybe(typeParam)) {
2464     // If both types are boxed, this is okay and even expected as a means to
2465     // update the hint for the inner type.
2466     if (srcType <= TBoxedCell &&
2467         typeParam <= TBoxedCell) {
2468       return false;
2469     }
2470
2471     // We got external information (probably from static analysis) that
2472     // conflicts with what we've built up so far.  There's no reasonable way to
2473     // continue here: we can't properly fatal the request because we can't make
2474     // a catch trace or SpillStack without IRGS, and we can't punt on
2475     // just this instruction because we might not be in the initial translation
2476     // phase, and we can't just plow on forward since we'll probably generate
2477     // malformed IR.  Since this case is very rare, just punt on the whole
2478     // trace so it gets interpreted.
2479     TRACE_PUNT("Invalid AssertTypeOp");
2480   }
2481
2482   // Asserting in these situations doesn't add any information.
2483   if (typeParam == TCls && srcType <= TCls) return true;
2484   if (typeParam == TGen && srcType <= TGen) return true;
2485
2486   auto const newType = srcType & typeParam;
2487
2488   if (srcType <= newType) {
2489     // The src type is at least as good as the new type.  Eliminate this
2490     // AssertType if the src type won't relax.  We do this to avoid eliminating
2491     // apparently redundant assert opcodes that may become useful after prior
2492     // guards are relaxed.
2493     if (!srcMightRelax) return true;
2494
2495     if (srcType < newType) {
2496       // This can happen because of limitations in how Toperator& handles
2497       // specialized types: sometimes it returns a Type that's wider than it
2498       // needs to be.  It shouldn't affect correctness but it can cause us to
2499       // miss out on some perf.
2500       FTRACE_MOD(Trace::hhir, 1,
2501                  "Suboptimal AssertTypeOp: refineType({}, {}) -> {} in {}\n",
2502                  srcType, typeParam, newType, *inst);
2503
2504       // We don't currently support intersecting RepoAuthType::Arrays
2505       // (t4473238), so we might be here because srcType and typeParam have
2506       // different RATArrays.  If that's the case, and if typeParam provides no
2507       // other useful information, we can unconditionally eliminate this
2508       // instruction: RATArrays never come from guards so we can't miss out on
2509       // anything by doing so.
2510       if (srcType < TArr &&
2511           srcType.arrSpec().type() &&
2512           typeParam < TArr &&
2513           typeParam.arrSpec().type() &&
2514           !typeParam.arrSpec().kind()) {
2515         return true;
2516       }
2517     }
2518   }
2519
2520   return false;
2521 }
2522
2523 //////////////////////////////////////////////////////////////////////
2524
2525 SimplifyResult simplify(IRUnit& unit,
2526                         const IRInstruction* origInst,
2527                         bool typesMightRelax) {
2528   auto env = State { unit, typesMightRelax };
2529   auto const newDst = simplifyWork(env, origInst);
2530
2531   assertx(validate(env, newDst, origInst));
2532
2533   return SimplifyResult { std::move(env.newInsts), newDst };
2534 }
2535
2536 void simplify(IRUnit& unit, IRInstruction* origInst) {
2537   assertx(!origInst->isTransient());
2538
2539   copyProp(origInst);
2540   auto res = simplify(unit, origInst, false);
2541
2542   // No simplification occurred; nothing to do.
2543   if (res.instrs.empty() && !res.dst) return;
2544
2545   FTRACE(1, "simplifying: {}\n", origInst->toString());
2546
2547   if (origInst->isBlockEnd()) {
2548     auto const next = origInst->block()->next();
2549
2550     if (res.instrs.empty() || !res.instrs.back()->isBlockEnd()) {
2551       // Our block-end instruction was eliminated (most likely a Jmp* converted
2552       // to a Nop).  Replace it with a Jmp to the next block.
2553       res.instrs.push_back(unit.gen(Jmp, origInst->marker(), next));
2554     }
2555
2556     auto last = res.instrs.back();
2557     assertx(last->isBlockEnd());
2558
2559     if (!last->isTerminal() && !last->next()) {
2560       // We converted the block-end instruction to a different one.  Set its
2561       // next block appropriately.
2562       last->setNext(next);
2563     }
2564   }
2565
2566   size_t out_size = 0;
2567   bool need_mov = res.dst;
2568   IRInstruction* last = nullptr;
2569
2570   for (auto inst : res.instrs) {
2571     if (inst->is(Nop)) continue;
2572
2573     ++out_size;
2574     last = inst;
2575
2576     if (res.dst && res.dst == inst->dst()) {
2577       // One of the new instructions produced the new dst.  Since we're going
2578       // to drop `origInst', just use origInst->dst() instead.
2579       inst->setDst(origInst->dst());
2580       inst->dst()->setInstruction(inst);
2581       need_mov = false;
2582     }
2583   }
2584
2585   auto const block = origInst->block();
2586   auto const pos = ++block->iteratorTo(origInst);
2587
2588   if (need_mov) {
2589     /*
2590      * In `killed_edge_defining' we have the case that an instruction defining
2591      * a temp on an edge (like CheckType) determined it can never define that
2592      * tmp.  In this situation we just Nop out the instruction and leave the
2593      * old tmp dangling.  The reason this is ok is that one of the following
2594      * two things are happening:
2595      *
2596      *    o The old next() block is becoming unreachable.  It's ok not to make
2597      *      a new definition of this tmp, because the code running simplify is
2598      *      going to have to track unreachable blocks and avoid looking at
2599      *      them.  It will also have to remove unreachable blocks when it's
2600      *      finished to maintain IR invariants (e.g. through DCE::Minimal),
2601      *      which will mean the uses of the no-longer-defined tmp will go away.
2602      *
2603      *    o The old next() block is still reachable (e.g. if we're removing a
2604      *      CheckType because it had next == taken).  But in this case, the
2605      *      next() edge must have been a critical edge, and therefore nothing
2606      *      could have any use of the old destination of the CheckType, or the
2607      *      program would already not have been in SSA, because it was only
2608      *      defined in blocks dominated by the next edge.
2609      */
2610     auto const killed_edge_defining = res.dst->type() <= TBottom &&
2611       origInst->isBlockEnd();
2612     if (killed_edge_defining) {
2613       origInst->convertToNop();
2614     } else {
2615       unit.replace(origInst, Mov, res.dst);
2616       // Force the existing dst type to match that of `res.dst'.
2617       origInst->dst()->setType(res.dst->type());
2618     }
2619   } else {
2620     if (out_size == 1) {
2621       assertx(origInst->dst() == last->dst());
2622       FTRACE(1, "    {}\n", last->toString());
2623
2624       // We only have a single instruction, so just become it.
2625       origInst->become(unit, last);
2626
2627       // Make sure to reset our dst's inst pointer, if we have one.  (It may
2628       // have been set to `last'.
2629       if (origInst->dst()) {
2630         origInst->dst()->setInstruction(origInst);
2631       }
2632
2633       // And we also need to kill `last', to update preds.
2634       last->convertToNop();
2635       return;
2636     }
2637
2638     origInst->convertToNop();
2639   }
2640
2641   FTRACE(1, "    {}\n", origInst->toString());
2642
2643   for (auto const inst : res.instrs) {
2644     if (inst->is(Nop)) continue;
2645     block->insert(pos, inst);
2646     FTRACE(1, "    {}\n", inst->toString());
2647   }
2648 }
2649
2650 //////////////////////////////////////////////////////////////////////
2651
2652 void simplifyPass(IRUnit& unit) {
2653   auto reachable = boost::dynamic_bitset<>(unit.numBlocks());
2654   reachable.set(unit.entry()->id());
2655
2656   for (auto block : rpoSortCfg(unit)) {
2657     if (!reachable.test(block->id())) continue;
2658
2659     for (auto& inst : *block) simplify(unit, &inst);
2660
2661     if (auto const b = block->next())  reachable.set(b->id());
2662     if (auto const b = block->taken()) reachable.set(b->id());
2663   }
2664 }
2665
2666 //////////////////////////////////////////////////////////////////////
2667
2668 void copyProp(IRInstruction* inst) {
2669   for (uint32_t i = 0; i < inst->numSrcs(); i++) {
2670     auto tmp     = inst->src(i);
2671     auto srcInst = tmp->inst();
2672
2673     if (srcInst->is(Mov)) {
2674       inst->setSrc(i, srcInst->src(0));
2675     }
2676
2677     // We're assuming that all of our src instructions have already been
2678     // copyPropped.
2679     assertx(!inst->src(i)->inst()->is(Mov));
2680   }
2681 }
2682
2683 PackedBounds packedArrayBoundsStaticCheck(Type arrayType, int64_t idxVal) {
2684   if (idxVal < 0 || idxVal > PackedArray::MaxSize) return PackedBounds::Out;
2685
2686   if (arrayType.hasConstVal()) {
2687     return idxVal < arrayType.arrVal()->size()
2688       ? PackedBounds::In
2689       : PackedBounds::Out;
2690   }
2691
2692   auto const at = arrayType.arrSpec().type();
2693   if (!at) return PackedBounds::Unknown;
2694
2695   using A = RepoAuthType::Array;
2696   switch (at->tag()) {
2697   case A::Tag::Packed:
2698     if (idxVal < at->size() && at->emptiness() == A::Empty::No) {
2699       return PackedBounds::In;
2700     }
2701     // fallthrough
2702   case A::Tag::PackedN:
2703     if (idxVal == 0 && at->emptiness() == A::Empty::No) {
2704       return PackedBounds::In;
2705     }
2706   }
2707   return PackedBounds::Unknown;
2708 }
2709
2710 Type packedArrayElemType(SSATmp* arr, SSATmp* idx) {
2711   assertx(arr->isA(TArr) &&
2712           arr->type().arrSpec().kind() == ArrayData::kPackedKind &&
2713           idx->isA(TInt));
2714
2715   if (arr->hasConstVal() && idx->hasConstVal()) {
2716     auto const idxVal = idx->intVal();
2717     if (idxVal >= 0 && idxVal < arr->arrVal()->size()) {
2718       return Type(arr->arrVal()->nvGet(idxVal)->m_type);
2719     }
2720     return TInitNull;
2721   }
2722
2723   Type t = arr->isA(TStaticArr) ? TInitCell : TGen;
2724
2725   auto const at = arr->type().arrSpec().type();
2726   if (!at) return t;
2727
2728   switch (at->tag()) {
2729     case RepoAuthType::Array::Tag::Packed:
2730     {
2731       if (idx->hasConstVal(TInt)) {
2732         auto const idxVal = idx->intVal();
2733         if (idxVal >= 0 && idxVal < at->size()) {
2734           return typeFromRAT(at->packedElem(idxVal)) & t;
2735         }
2736         return TInitNull;
2737       }
2738       Type elemType = TBottom;
2739       for (uint32_t i = 0; i < at->size(); ++i) {
2740         elemType |= typeFromRAT(at->packedElem(i));
2741       }
2742       return elemType & t;
2743     }
2744     case RepoAuthType::Array::Tag::PackedN:
2745       return typeFromRAT(at->elemType()) & t;
2746   }
2747   not_reached();
2748 }
2749
2750 //////////////////////////////////////////////////////////////////////
2751
2752 }}