hphp/runtime/vm/jit/gvn.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16 #include "hphp/runtime/vm/jit/opt.h"
  17
  18 #include "hphp/runtime/vm/jit/analysis.h"
  19 #include "hphp/runtime/vm/jit/block.h"
  20 #include "hphp/runtime/vm/jit/cfg.h"
  21 #include "hphp/runtime/vm/jit/containers.h"
  22 #include "hphp/runtime/vm/jit/ir-instruction.h"
  23 #include "hphp/runtime/vm/jit/ssa-tmp.h"
  24 #include "hphp/runtime/vm/jit/state-vector.h"
  25 #include "hphp/runtime/vm/jit/pass-tracer.h"
  26 #include "hphp/runtime/vm/jit/timer.h"
  27
  28 #include "hphp/util/dataflow-worklist.h"
  29
  30 #include <sstream>
  31 #include <folly/small_vector.h>
  32
  33 namespace HPHP { namespace jit {
  34
  35 TRACE_SET_MOD(hhir_gvn);
  36
  37 //////////////////////////////////////////////////////////////////////
  38
  39 namespace {
  40
  41 struct ValueNumberMetadata {
  42   SSATmp* key;
  43   SSATmp* value;
  44 };
  45
  46 using ValueNumberTable = StateVector<SSATmp, ValueNumberMetadata>;
  47 using DstIndex = int32_t;
  48
  49 struct CongruenceHasher {
  50   using KeyType = std::pair<IRInstruction*, DstIndex>;
  51
  52   explicit CongruenceHasher(const ValueNumberTable& globalTable)
  53     : m_globalTable(&globalTable)
  54   {
  55   }
  56
  57   size_t hashSharedImpl(IRInstruction* inst, size_t result) const {
  58     if (inst->hasExtra()) {
  59       result = folly::hash::hash_128_to_64(
  60         result,
  61         hashExtra(inst->op(), inst->rawExtra())
  62       );
  63     }
  64
  65     if (inst->hasTypeParam()) {
  66       result = folly::hash::hash_128_to_64(result, inst->typeParam().hash());
  67     }
  68
  69     return result;
  70   }
  71
  72   size_t hashSrcs(KeyType key, size_t result) const {
  73     auto& table = *m_globalTable;
  74     auto inst = key.first;
  75     for (uint32_t i = 0; i < inst->numSrcs(); ++i) {
  76       auto src = canonical(inst->src(i));
  77       assertx(table[src].value);
  78       result = folly::hash::hash_128_to_64(
  79         result,
  80         reinterpret_cast<size_t>(table[src].value)
  81       );
  82     }
  83     return result;
  84   }
  85
  86   size_t operator()(KeyType key) const {
  87     auto inst = key.first;
  88
  89     // Note: this doesn't take commutativity or associativity into account, but
  90     // it might be nice to do so for the opcodes where it makes sense.
  91     size_t result = static_cast<size_t>(inst->op());
  92     result = hashSrcs(key, result);
  93     return hashSharedImpl(inst, result);
  94   }
  95
  96 private:
  97   const ValueNumberTable* m_globalTable;
  98 };
  99
 100 struct CongruenceComparator {
 101   using KeyType = std::pair<IRInstruction*, DstIndex>;
 102
 103   explicit CongruenceComparator(const ValueNumberTable& globalTable)
 104     : m_globalTable(&globalTable)
 105   {
 106   }
 107
 108   bool compareSrcs(KeyType keyA, KeyType keyB) const {
 109     auto& table = *m_globalTable;
 110     auto instA = keyA.first;
 111     auto instB = keyB.first;
 112
 113     for (uint32_t i = 0; i < instA->numSrcs(); ++i) {
 114       auto srcA = canonical(instA->src(i));
 115       auto srcB = canonical(instB->src(i));
 116       assertx(table[srcA].value);
 117       assertx(table[srcB].value);
 118       if (table[srcA].value != table[srcB].value) return false;
 119     }
 120
 121     return true;
 122   }
 123
 124   bool operator()(KeyType keyA, KeyType keyB) const {
 125     auto instA = keyA.first;
 126     auto instB = keyB.first;
 127
 128     // Note: this doesn't take commutativity or associativity into account, but
 129     // it might be nice to do so for the opcodes where it makes sense.
 130     if (instA->op() != instB->op()) return false;
 131     if (instA->numSrcs() != instB->numSrcs()) return false;
 132     if (instA->hasTypeParam() != instB->hasTypeParam()) return false;
 133     if (instA->hasTypeParam() && instA->typeParam() != instB->typeParam()) {
 134       return false;
 135     }
 136
 137     if (instA->hasExtra()) {
 138       assertx(instB->hasExtra());
 139       if (!equalsExtra(instA->op(), instA->rawExtra(), instB->rawExtra())) {
 140         return false;
 141       }
 142     }
 143
 144     if (!compareSrcs(keyA, keyB)) {
 145       return false;
 146     }
 147
 148     return true;
 149   }
 150
 151 private:
 152   const ValueNumberTable* m_globalTable;
 153 };
 154
 155 using NameTable = jit::hash_map<
 156   std::pair<IRInstruction*, DstIndex>, SSATmp*,
 157   CongruenceHasher,
 158   CongruenceComparator
 159 >;
 160
 161 struct GVNState {
 162   ValueNumberTable* localTable{nullptr};
 163   ValueNumberTable* globalTable{nullptr};
 164   NameTable* nameTable{nullptr};
 165 };
 166
 167 bool supportsGVN(const IRInstruction* inst) {
 168   switch (inst->op()) {
 169   case AssertType:
 170   case AbsDbl:
 171   case AddInt:
 172   case SubInt:
 173   case MulInt:
 174   case AndInt:
 175   case AddDbl:
 176   case SubDbl:
 177   case MulDbl:
 178   case DivDbl:
 179   case DivInt:
 180   case Mod:
 181   case Sqrt:
 182   case OrInt:
 183   case XorInt:
 184   case Shl:
 185   case Shr:
 186   case Floor:
 187   case Ceil:
 188   case AddIntO:
 189   case SubIntO:
 190   case MulIntO:
 191   case XorBool:
 192   case ConvBoolToArr:
 193   case ConvDblToArr:
 194   case ConvIntToArr:
 195   case ConvDblToBool:
 196   case ConvIntToBool:
 197   case ConvBoolToDbl:
 198   case ConvIntToDbl:
 199   case ConvBoolToInt:
 200   case ConvDblToInt:
 201   case ConvClsToCctx:
 202   case DblAsBits:
 203   case GtInt:
 204   case GteInt:
 205   case LtInt:
 206   case LteInt:
 207   case EqInt:
 208   case NeqInt:
 209   case CmpInt:
 210   case GtDbl:
 211   case GteDbl:
 212   case LtDbl:
 213   case LteDbl:
 214   case EqDbl:
 215   case NeqDbl:
 216   case CmpDbl:
 217   case GtStr:
 218   case GteStr:
 219   case LtStr:
 220   case LteStr:
 221   case EqStr:
 222   case NeqStr:
 223   case SameStr:
 224   case NSameStr:
 225   case CmpStr:
 226   case GtStrInt:
 227   case GteStrInt:
 228   case LtStrInt:
 229   case LteStrInt:
 230   case EqStrInt:
 231   case NeqStrInt:
 232   case CmpStrInt:
 233   case GtBool:
 234   case GteBool:
 235   case LtBool:
 236   case LteBool:
 237   case EqBool:
 238   case NeqBool:
 239   case CmpBool:
 240   case SameObj:
 241   case NSameObj:
 242   case SameVec:
 243   case NSameVec:
 244   case SameDict:
 245   case NSameDict:
 246   case EqKeyset:
 247   case NeqKeyset:
 248   case SameKeyset:
 249   case NSameKeyset:
 250   case GtRes:
 251   case GteRes:
 252   case LtRes:
 253   case LteRes:
 254   case EqRes:
 255   case NeqRes:
 256   case CmpRes:
 257   case EqCls:
 258   case EqFunc:
 259   case EqStrPtr:
 260   case InstanceOf:
 261   case InstanceOfIface:
 262   case InstanceOfIfaceVtable:
 263   case ExtendsClass:
 264   case InstanceOfBitmask:
 265   case NInstanceOfBitmask:
 266   case InterfaceSupportsArr:
 267   case InterfaceSupportsVec:
 268   case InterfaceSupportsDict:
 269   case InterfaceSupportsKeyset:
 270   case InterfaceSupportsStr:
 271   case InterfaceSupportsInt:
 272   case InterfaceSupportsDbl:
 273   case HasToString:
 274   case IsType:
 275   case IsNType:
 276   case IsWaitHandle:
 277   case IsCol:
 278   case IsDVArray:
 279   case LdRDSAddr:
 280   case LdCtx:
 281   case LdCctx:
 282   case LdClsCtx:
 283   case LdClsCctx:
 284   case LdClsCtor:
 285   case DefConst:
 286   case DefCls:
 287   case LdCls:
 288   case LdClsCached:
 289   case LdClsInitData:
 290   case LdClsFromClsMeth:
 291   case LdSmashableFunc:
 292   case LdFuncFromClsMeth:
 293   case LdFuncVecLen:
 294   case LdClsMethod:
 295   case LdIfaceMethod:
 296   case LdPropAddr:
 297   case LdClsPropAddrOrNull:
 298   case LdClsPropAddrOrRaise:
 299   case LdObjClass:
 300   case LdClsName:
 301   case LdARNumParams:
 302   case Mov:
 303   case LdContActRec:
 304   case LdAFWHActRec:
 305   case LdPackedArrayDataElemAddr:
 306   case OrdStr:
 307   case ChrInt:
 308   case CheckRange:
 309   case CountArrayFast:
 310   case CountVec:
 311   case CountDict:
 312   case CountShape:
 313   case CountKeyset:
 314   case Select:
 315   case StrictlyIntegerConv:
 316   case LookupSPropSlot:
 317   case ConvPtrToLval:
 318     return true;
 319
 320   case SameArr:
 321   case NSameArr:
 322     return !RuntimeOption::EvalHackArrCompatDVCmpNotices;
 323
 324   default:
 325     return false;
 326   }
 327 }
 328
 329 void initWithInstruction(IRInstruction* inst, ValueNumberTable& table) {
 330   // Each SSATmp starts out as the canonical name for itself.
 331   for (auto dst : inst->dsts()) {
 332     table[dst] = ValueNumberMetadata { dst, dst };
 333   }
 334
 335   for (auto src : inst->srcs()) {
 336     table[src] = ValueNumberMetadata { src, src };
 337   }
 338 }
 339
 340 bool visitInstruction(
 341   GVNState& env,
 342   IRInstruction* inst
 343 ) {
 344   auto& globalTable = *env.globalTable;
 345   auto& localTable = *env.localTable;
 346   auto& nameTable = *env.nameTable;
 347
 348   if (isCallOp(inst->op())) nameTable.clear();
 349
 350   if (!supportsGVN(inst)) return false;
 351
 352   bool changed = false;
 353   for (auto dstIdx = 0; dstIdx < inst->numDsts(); ++dstIdx) {
 354     auto dst = inst->dst(dstIdx);
 355     assertx(dst);
 356
 357     auto result = nameTable.emplace(std::make_pair(inst, dstIdx), dst);
 358     SSATmp* temp = result.second ? dst : result.first->second;
 359     assertx(temp);
 360
 361     assertx(globalTable[dst].value);
 362     if (temp != globalTable[dst].value) {
 363       localTable[dst] = ValueNumberMetadata { dst, temp };
 364       FTRACE(1,
 365         "instruction {}\n"
 366         "updated value number for dst to dst of {}\n",
 367         *inst,
 368         *temp->inst()
 369       );
 370       changed = true;
 371     }
 372   }
 373   return changed;
 374 }
 375
 376 bool visitBlock(
 377   GVNState& env,
 378   Block* block
 379 ) {
 380   bool changed = false;
 381   for (auto& inst : *block) {
 382     changed = visitInstruction(env, &inst) || changed;
 383   }
 384   return changed;
 385 }
 386
 387 void applyLocalUpdates(ValueNumberTable& local, ValueNumberTable& global) {
 388   for (auto metadata : local) {
 389     if (!metadata.key) continue;
 390     global[metadata.key] = metadata;
 391   }
 392 }
 393
 394 void runAnalysis(
 395   GVNState& env,
 396   const IRUnit& unit,
 397   const BlockList& blocks
 398 ) {
 399   for (auto block : blocks) {
 400     for (auto& inst : *block) {
 401       initWithInstruction(&inst, *env.globalTable);
 402     }
 403   }
 404
 405   bool changed = true;
 406   while (changed) {
 407     // We need a temporary table of updates which we apply after running this
 408     // iteration of the fixed point. If we change the global ValueNumberTable
 409     // during the pass, the hash values of the SSATmps will change which is
 410     // apparently a no-no for unordered_map.
 411     ValueNumberTable localTable(unit, ValueNumberMetadata{});
 412     env.localTable = &localTable;
 413     SCOPE_EXIT { env.localTable = nullptr; };
 414     {
 415       CongruenceHasher hash(*env.globalTable);
 416       CongruenceComparator pred(*env.globalTable);
 417       NameTable nameTable(0, hash, pred);
 418       env.nameTable = &nameTable;
 419       SCOPE_EXIT { env.nameTable = nullptr; };
 420
 421       changed = false;
 422       for (auto block : blocks) {
 423         changed = visitBlock(env, block) || changed;
 424       }
 425     }
 426     applyLocalUpdates(localTable, *env.globalTable);
 427   }
 428 }
 429
 430 /*
 431  * When gvn replaces an instruction that produces a refcount, we need
 432  * to IncRef the replacement value. Its not enough to IncRef it where
 433  * the replacement occurs (where a refcount would originally have been
 434  * produced), because the replacement value might not survive that
 435  * long. Instead, we need to IncRef it right after the canonical
 436  * instruction. However, in general there will be paths from the
 437  * canonical instruction that don't reach the replaced instruction, so
 438  * we'll need to insert DecRefs on those paths.
 439  *
 440  * As an example, given:
 441  *
 442  *        +------+
 443  *        | Orig |
 444  *        +------+
 445  *           |\
 446  *           | \
 447  *           |  \    +-----+
 448  *           |   --->|exit1|
 449  *           |       +-----+
 450  *           v
 451  *        +------+
 452  *        | Rep1 |
 453  *        +------+
 454  *           |\
 455  *           | \
 456  *           |  \    +-----+
 457  *           |   --->|exit2|
 458  *           |       +-----+
 459  *           v
 460  *        +------+
 461  *        | Rep2 |
 462  *        +------+
 463  *
 464  * Where Orig is a PRc instruction, and Rep1 and Rep2 are identical
 465  * instructions that are going to be replaced, we need to insert an
 466  * IncRef after Orig (to ensure its dst lives until Rep1), a DecRef at
 467  * exit1 (to keep the RefCounts balanced), an IncRef after Rep1 (to
 468  * ensure Orig's dst lives until Rep2), and a DecRef in exit2 (to keep
 469  * the RefCounts balanced).
 470  *
 471  * We do this by computing Availability, Anticipability and
 472  * Partial-Anticipability of the candidate instructions (Orig, Rep1
 473  * and Rep2 in the example). After each candidate instruction we
 474  * insert an IncRef if a candidate is Partially-Anticipated-out. If a
 475  * candidate is Available-in and not Partially-Anticipated-in, we
 476  * insert a DecRef if its Partially-Anticipated out of all
 477  * predecessors. This could fail to insert DecRefs if we don't split
 478  * critical edges - but in that case there simply wouldn't be anywhere
 479  * to insert the DecRef.
 480  */
 481 constexpr uint32_t kMaxTrackedPrcs = 64;
 482
 483 struct PrcState {
 484   using Bits = std::bitset<kMaxTrackedPrcs>;
 485
 486   uint32_t rpoId;
 487
 488   /* local is the set of candidates in this block */
 489   Bits local;
 490   /* antIn = local | antOut */
 491   Bits antIn;
 492   /* pantIn = local | pantOut */
 493   Bits pantIn;
 494   /* antOut = Intersection<succs>(antIn) (empty if numSucc==0) */
 495   Bits antOut;
 496   /* pantOut = Union<succs>(pantIn) */
 497   Bits pantOut;
 498   /* avlIn = Intersection<preds>(avlOut) (empty if numPred==0) */
 499   Bits avlIn;
 500   /* avlOut = local | avlIn */
 501   Bits avlOut;
 502 };
 503
 504 std::string show(const PrcState::Bits& bits) {
 505   std::ostringstream out;
 506   if (bits.none()) {
 507     return "0";
 508   }
 509   if (bits.all()) {
 510     return "-1";
 511   }
 512   out << bits;
 513   return out.str();
 514 }
 515
 516 std::string show(const PrcState& state) {
 517   return folly::sformat(
 518     "   antIn   : {}\n"
 519     "   pantIn  : {}\n"
 520     "   avlIn   : {}\n"
 521     "   local   : {}\n"
 522     "   antOut  : {}\n"
 523     "   pantOut : {}\n"
 524     "   avlOut  : {}\n",
 525     show(state.antIn),
 526     show(state.pantIn),
 527     show(state.avlIn),
 528     show(state.local),
 529     show(state.antOut),
 530     show(state.pantOut),
 531     show(state.avlOut));
 532 }
 533
 534 struct PrcEnv {
 535   PrcEnv(IRUnit& unit, const BlockList& rpoBlocks) :
 536       unit{unit}, rpoBlocks{rpoBlocks} {}
 537
 538   IRUnit& unit;
 539   const BlockList& rpoBlocks;
 540   // The first element of each inner vector is the canonical SSATmp
 541   // and the remainder are the SSATmps that will be replaced.
 542   std::vector<std::vector<SSATmp*>> insertMap;
 543   std::vector<PrcState> states;
 544 };
 545
 546 void insertIncRefs(PrcEnv& env) {
 547   auto antQ =
 548     dataflow_worklist<uint32_t, std::less<uint32_t>>(env.rpoBlocks.size());
 549   auto avlQ =
 550     dataflow_worklist<uint32_t, std::greater<uint32_t>>(env.rpoBlocks.size());
 551
 552   env.states.resize(env.unit.numBlocks());
 553   for (uint32_t i = 0; i < env.rpoBlocks.size(); i++) {
 554     auto blk = env.rpoBlocks[i];
 555     auto& state = env.states[blk->id()];
 556     state.rpoId = i;
 557     if (blk->numSuccs()) state.antOut.set();
 558     if (blk->numPreds()) state.avlIn.set();
 559     antQ.push(i);
 560     avlQ.push(i);
 561   }
 562
 563   auto id = 0;
 564   for (auto& v : env.insertMap) {
 565     for (auto const tmp : v) {
 566       auto const blk = tmp->inst()->block();
 567       auto& state = env.states[blk->id()];
 568       if (!state.local.test(id)) {
 569         state.local.set(id);
 570         continue;
 571       }
 572     }
 573     id++;
 574   }
 575
 576   using Bits = PrcState::Bits;
 577   // compute anticipated
 578   do {
 579     auto const blk = env.rpoBlocks[antQ.pop()];
 580     auto& state = env.states[blk->id()];
 581     state.antIn = state.antOut | state.local;
 582     state.pantIn = state.pantOut | state.local;
 583     blk->forEachPred(
 584       [&] (Block* b) {
 585         auto& s = env.states[b->id()];
 586         auto const antOut = s.antOut & state.antIn;
 587         auto const pantOut = s.pantOut | state.pantIn;
 588         if (antOut != s.antOut || pantOut != s.pantOut) {
 589           s.antOut = antOut;
 590           s.pantOut = pantOut;
 591           antQ.push(s.rpoId);
 592         }
 593       }
 594     );
 595   } while (!antQ.empty());
 596
 597   // compute available
 598   do {
 599     auto const blk = env.rpoBlocks[avlQ.pop()];
 600     auto& state = env.states[blk->id()];
 601     state.avlOut = state.avlIn | state.local;
 602     blk->forEachSucc(
 603       [&] (Block* b) {
 604         auto& s = env.states[b->id()];
 605         auto const avlIn = s.avlIn & state.avlOut;
 606         if (avlIn != s.avlIn) {
 607           s.avlIn = avlIn;
 608           avlQ.push(s.rpoId);
 609         }
 610       });
 611   } while (!avlQ.empty());
 612
 613   for (auto blk : env.rpoBlocks) {
 614     auto& state = env.states[blk->id()];
 615     FTRACE(4,
 616            "InsertIncDecs: Blk(B{}) <- {}\n"
 617            "{}"
 618            "  ->{}\n",
 619            blk->id(),
 620            [&] {
 621              std::string ret;
 622              blk->forEachPred([&] (Block* pred) {
 623                  folly::format(&ret, " B{}", pred->id());
 624                });
 625              return ret;
 626            }(),
 627            show(state),
 628            [&] {
 629              std::string ret;
 630              blk->forEachSucc([&] (Block* succ) {
 631                  folly::format(&ret, " B{}", succ->id());
 632                });
 633              return ret;
 634            }());
 635
 636     auto inc = state.local;
 637     for (auto inc_id = 0; inc.any(); inc >>= 1, inc_id++) {
 638       if (inc.test(0)) {
 639         auto const& tmps = env.insertMap[inc_id];
 640         auto insert = [&] (IRInstruction* inst) {
 641           FTRACE(3, "Inserting IncRef into B{}\n", blk->id());
 642           auto const iter = std::next(blk->iteratorTo(inst));
 643           blk->insert(iter, env.unit.gen(IncRef, inst->bcctx(), tmps[0]));
 644         };
 645         SSATmp* last = nullptr;
 646         // Insert an IncRef after every candidate in this block except
 647         // the last one (since we know for all but the last that its
 648         // successor is anticipated). Note that entries in tmps from
 649         // the same block are guaranteed to be in program order.
 650         for (auto const tmp : tmps) {
 651           if (tmp->inst()->block() != blk) continue;
 652           if (last) insert(last->inst());
 653           last = tmp;
 654         }
 655         // If it's partially anticipated out, insert an inc after the
 656         // last one too.
 657         always_assert(last);
 658         if (state.pantOut.test(inc_id)) insert(last->inst());
 659       }
 660     }
 661     auto dec = state.avlIn & ~state.pantIn;
 662     if (dec.any()) {
 663       blk->forEachPred(
 664         [&] (Block* pred) {
 665           auto& pstate = env.states[pred->id()];
 666           dec &= pstate.pantOut;
 667         });
 668
 669       for (auto dec_id = 0; dec.any(); dec >>= 1, dec_id++) {
 670         if (dec.test(0)) {
 671           FTRACE(3, "Inserting DecRef into B{}\n", blk->id());
 672           auto const tmp = env.insertMap[dec_id][0];
 673           blk->prepend(env.unit.gen(DecRef, tmp->inst()->bcctx(),
 674                                     DecRefData{}, tmp));
 675         }
 676       }
 677     }
 678   }
 679 }
 680
 681 using ActionMap = jit::fast_map<SSATmp*, std::vector<SSATmp*>>;
 682
 683 void tryReplaceInstruction(
 684   IRUnit& unit,
 685   const IdomVector& idoms,
 686   IRInstruction* inst,
 687   ValueNumberTable& table,
 688   ActionMap& actionMap
 689 ) {
 690   if (inst->hasDst()) {
 691     auto const dst = inst->dst();
 692     auto const valueNumber = table[dst].value;
 693     if (valueNumber &&
 694         valueNumber != dst &&
 695         is_tmp_usable(idoms, valueNumber, inst->block())) {
 696       if (inst->producesReference()) {
 697         auto& v = actionMap[valueNumber];
 698         if (!v.size()) v.push_back(valueNumber);
 699         v.push_back(dst);
 700       }
 701       if (!(valueNumber->type() <= dst->type())) {
 702         FTRACE(1,
 703                "replacing {} with AssertType({})\n",
 704                inst->toString(),
 705                dst->type().toString()
 706               );
 707         unit.replace(inst, AssertType, dst->type(), valueNumber);
 708       }
 709     }
 710   }
 711
 712   for (uint32_t i = 0; i < inst->numSrcs(); ++i) {
 713     auto s = inst->src(i);
 714     auto valueNumber = table[s].value;
 715     if (valueNumber == s) continue;
 716     if (!valueNumber) continue;
 717     if (!is_tmp_usable(idoms, valueNumber, inst->block())) continue;
 718
 719     // If the replacement is at least as refined as the source type,
 720     // just substitute it directly
 721     if (valueNumber->type() <= s->type()) {
 722       FTRACE(1,
 723              "instruction {}\n"
 724              "replacing src {} with dst of {}\n",
 725              *inst,
 726              i,
 727              *valueNumber->inst()
 728             );
 729       inst->setSrc(i, valueNumber);
 730     }
 731   }
 732 }
 733
 734 void replaceRedundantComputations(
 735   IRUnit& unit,
 736   const IdomVector& idoms,
 737   const BlockList& blocks,
 738   ValueNumberTable& table
 739 ) {
 740   ActionMap actionMap;
 741   for (auto block : blocks) {
 742     for (auto& inst : *block) {
 743       tryReplaceInstruction(unit, idoms, &inst, table, actionMap);
 744     }
 745   }
 746   if (actionMap.empty()) return;
 747   PrcEnv env(unit, blocks);
 748   for (auto& elm : actionMap) {
 749     if (env.insertMap.size() == kMaxTrackedPrcs) {
 750       // This pretty much doesn't happen; when it does, we might be
 751       // over-increffing here - but thats not a big deal.
 752       auto const newTmp = elm.second[0];
 753       auto const block = newTmp->inst()->block();
 754       auto const iter = std::next(block->iteratorTo(newTmp->inst()));
 755       for (auto i = 1; i < elm.second.size(); i++) {
 756         block->insert(iter, unit.gen(IncRef, newTmp->inst()->bcctx(), newTmp));
 757       }
 758       continue;
 759     }
 760     env.insertMap.push_back(std::move(elm.second));
 761   }
 762   insertIncRefs(env);
 763 }
 764
 765 } // namespace
 766
 767 /////////////////////////////////////////////////////////////////////////
 768
 769 void gvn(IRUnit& unit) {
 770   PassTracer tracer{&unit, Trace::hhir_gvn, "gvn"};
 771   Timer t(Timer::optimize_gvn, unit.logEntry().get_pointer());
 772   splitCriticalEdges(unit);
 773
 774   GVNState state;
 775   auto const rpoBlocks = rpoSortCfg(unit);
 776   auto const idoms = findDominators(
 777     unit,
 778     rpoBlocks,
 779     numberBlocks(unit, rpoBlocks)
 780   );
 781
 782   ValueNumberTable globalTable(unit, ValueNumberMetadata{});
 783   state.globalTable = &globalTable;
 784
 785   // This is an implementation of the RPO version of the global value numbering
 786   // algorithm presented in the 1996 paper "SCC-based Value Numbering" by
 787   // Cooper and Simpson.
 788   runAnalysis(state, unit, rpoBlocks);
 789   replaceRedundantComputations(unit, idoms, rpoBlocks, globalTable);
 790   state.globalTable = nullptr;
 791 }
 792
 793 }}