text: /*
     +----------------------------------------------------------------------+
     | HipHop for PHP                                                       |
     +----------------------------------------------------------------------+
     | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
     +----------------------------------------------------------------------+
     | This source file is subject to version 3.01 of the PHP license,      |
     | that is bundled with this package in the file LICENSE, and is        |
     | available through the world-wide-web at the following url:           |
     | http://www.php.net/license/3_01.txt                                  |
     | If you did not receive a copy of the PHP license and are unable to   |
     | obtain it through the world-wide-web, please send a note to          |
     | license@php.net so we can mail you a copy immediately.               |
     +----------------------------------------------------------------------+
  */
  #include "hphp/runtime/vm/jit/opt.h"
  
  #include <iterator>
  #include <string>
  
  #include <folly/Format.h>
  #include <folly/Optional.h>
  #include <folly/ScopeGuard.h>
  
  #include "hphp/util/bisector.h"
  #include "hphp/util/bitset-utils.h"
  #include "hphp/util/dataflow-worklist.h"
  #include "hphp/util/match.h"
  #include "hphp/util/trace.h"
  
  #include "hphp/runtime/vm/jit/alias-analysis.h"
  #include "hphp/runtime/vm/jit/cfg.h"
  #include "hphp/runtime/vm/jit/containers.h"
  #include "hphp/runtime/vm/jit/ir-unit.h"
  #include "hphp/runtime/vm/jit/memory-effects.h"
  #include "hphp/runtime/vm/jit/mutation.h"
  #include "hphp/runtime/vm/jit/pass-tracer.h"
  #include "hphp/runtime/vm/jit/state-vector.h"
  #include "hphp/runtime/vm/jit/timer.h"
  
  /*
    This implements partial-redundancy elimination for stores.
  
    The basic algorithm follows Morel & Renvoise "Global Optimization by
    Suppression of Partial Redundancies".  That paper talks about redundancy of
    expressions, so we have to "reverse" everything to apply it to stores
    (Anticipated <=> Available, In <=> Out).
  
    Some general terminology:
      - A store to a location L is /available/ at code position P if it has
        happened on all paths to P, and there is no interference (loads or
        other stores) of L between those stores and P.
      - A store to a location L is /anticipated/ at code position P if it occurs
        between P and any subsequent use of L.
  
    There are two forms of (non)-transparency for stores.  A (possible) use of
    the result of a candidate store prevents the candidate from being moved past
    the use, and also prevents the candidate from being killed by a later store.
    This is very similar to transparency of expressions.  But in addition, a
    possibly interfering store following a candidate store prevents the candidate
    from moving past the store, but does not prevent the candidate from being
    killed by a later store.  We represent these two criteria via alteredAnt and
    alteredAvl (see below).
  
    This also affects local availabilty; a store may not be available in the
    sense that it can be moved to the end of the block (because of a possible
    conflicting write), but it may still be available in the sense that it can be
    killed by a later store.  We split this out into AvlLoc (can be moved to the
    end), and DelLoc (can be deleted if it's anticipated out).
  
    Finally, we make some simplifications to the CONST term in M & R to
    reduce the number of bitvectors involved, and reduce the bidirectionality
    of the data flow equations.
  
    The final equations are:
  
    Local bitvectors (contents of BlockAnalysis), per block B:
      antLoc[L]     : There exists a store to L in B which is anticipated at the
                      start of B---and thus can be moved there, without changing
                      the meaning of the program.
      avlLoc[L]     : There exists a store to L in B which is available at the
                      end of B---and thus can be moved there, without changing
                      the meaning of the program.
      delLoc[L]     : There exists a store to L in B which could be killed if it
                      would be redundant at the end of B (even though it may not
                      be legal to move it there).
  
      alteredAnt[L] : B contains a possible use of L.  This prevents a store to L
                      from being killed by an otherwise-redundant store in a
                      later block.  (It also prevents stores from being moved
                      forward through this block.)
      alteredAvl[L] : B contains a possible use or store of L.  This prevents a
                      store to L from being moved through this block, but stores
                      might still be allowed to be eliminated due to redundancy
                      with later stores (unless, of course, alteredAnt[L] holds).
  
    Global bitvectors:
      Anticipated: (backward walk, initial 1s except in exit blocks)
      AntIn = AntLoc | (AntOut & ~alteredAnt);
      AntOut = Product(succs, AntIn(s))
  
      Partially Anticipated: (backward walk, initial 0s)
      PAntIn = AntLoc | (PAntOut & ~alteredAnt)
      PAntOut = Union(succs, PAntIn(s))
  
      Available: (forward walk, initial 1s except in entry block)
      AvlIn = Product(preds, AvlOut(p))
      AvlOut = AvlLoc | (AvlIn & ~alteredAvl);
  
      Placement Possible: (forward walk, initialized to AvlIn except entry, and
                           AvlOut except exit block)
      PPIn = Product(preds, PPOut(p))
      PPOut = PAntOut & (AvlLoc | (PPIn & ~alteredAvl)) &
              Product(succs, PPIn(s) | AntIn(s))
  
        Roughly speaking, at any given block, we're interested in the stores that
        are PAntOut, because they're redundant on at least one path from this
        block to the exit of the region.  We can place a store at the end of a
        block if it's AvlLoc (by definition) or if it's PPIn and "transparent" to
        the block; but since we're actually going to be inserting at the start of
        blocks, there's no point marking a block PPOut unless the store is PPIn
        or it's redundant in each of the following blocks.
  
        Note that we could use 1s instead of AvlIn/AvlOut, but convergence would
        be slower, and we would still need to deal with stores where the
        bitvectors say they're available, but we can't construct a suitable
        store).
  
      Insert = PPIn & ~AntIn & (~PPOut | alteredAvl);
        We want to insert if it's possible, and the store is not redundant, and we
        can't push the store any later.
  
      Delete = (AntOut & DelLoc) | (PPOut & AvlLoc);
        AntOut & DelLoc means it's redundant; we'll just kill it.
        PPOut => PPIn | AntIn in each successor, meaning that for each successor
        (recursively) we can either push the store into that successor, or it's
        redundant there.
  */
  
  namespace HPHP { namespace jit {
  
  TRACE_SET_MOD(hhir_store);
  
  namespace {
  
  //////////////////////////////////////////////////////////////////////
  
  using PostOrderId = uint32_t;
  
  /*
    TrackedStore is used to keep track of which stores are available at
    the beginning and end of each Block.
    Its value can be
      - Unseen (either there is no store available, or we
        haven't processed it yet),
      - Instruction, in which case it holds a pointer to the
        store which is available there,
      - Phi..Phi+kMaxTrackedAlocs, in which case it holds a pointer to the
        Block where the phi would have to be inserted, or
      - Bad which means that although stores are available on all
        paths to this point they're not compatible in some way
        (usually SpillFrame vs StStk).
  
      - Pending and Processed are used while building phis to handle
        cycles of phis.
  
    For the Phi case, we just need to ensure that we can differentiate
    Phis in the same block for different ALocations; this is just used
    for the hash() and same() methods for the spillFrameMap.
  */
  struct TrackedStore {
    enum Kind : int16_t {
      Unseen,
      Instruction,
      Phi,
      Bad = Phi + kMaxTrackedALocs,
      Pending,
      Processed,
    };
  
    TrackedStore() = default;
    TrackedStore(const TrackedStore&) = default;
    explicit TrackedStore(IRInstruction* i) { m_ptr.set(Instruction, i); }
    explicit TrackedStore(Block* b, uint32_t id) {
      m_ptr.set(static_cast<Kind>(Phi + id), b);
    }
  
    static TrackedStore BadVal() { TrackedStore s; s.setBad(); return s; }
    const IRInstruction* instruction() const {
      return kind() == Instruction ?
        static_cast<const IRInstruction*>(m_ptr.ptr()) : nullptr;
    }
    IRInstruction* instruction() {
      return kind() == Instruction ?
        static_cast<IRInstruction*>(m_ptr.ptr()) : nullptr;
    }
    const Block* block() const {
      return isPhi() ? static_cast<const Block*>(m_ptr.ptr()) : nullptr;
    }
    Block* block() {
      return isPhi() ? static_cast<Block*>(m_ptr.ptr()) : nullptr;
    }
    Block* pending() {
      return kind() == Pending ? static_cast<Block*>(m_ptr.ptr()) : nullptr;
    }
    const Block* pending() const {
      return kind() == Pending ? static_cast<const Block*>(m_ptr.ptr()) : nullptr;
    }
    IRInstruction* processed() {
      return kind() == Processed ?
        static_cast<IRInstruction*>(m_ptr.ptr()) : nullptr;
    }
    const IRInstruction* processed() const {
      return kind() == Processed ?
        static_cast<const IRInstruction*>(m_ptr.ptr()) : nullptr;
    }
    bool isUnseen() const {
      return kind() == Unseen;
    }
    bool isBad() const {
      return kind() == Bad;
    }
    bool isPhi() const {
      return kind() >= Phi && kind() < Bad;
    }
    void set(IRInstruction* inst) { m_ptr.set(Instruction, inst); }
    void set(Block* block, uint32_t id) {
      m_ptr.set(static_cast<Kind>(Phi + id), block);
    }
    void setPending(Block* block) { m_ptr.set(Pending, block); }
    void setProcessed(IRInstruction* inst) { m_ptr.set(Processed, inst); }
    void reset() { m_ptr.set(Unseen, nullptr); }
    void setBad() { m_ptr.set(Bad, nullptr); }
    bool same(const TrackedStore& other) const {
      return kind() == other.kind() && m_ptr.ptr() == other.m_ptr.ptr();
    }
    friend DEBUG_ONLY bool operator>=(const TrackedStore& a,
                                      const TrackedStore& b) {
      return a.kind() >= b.kind();
    }
    size_t hash() const {
      return m_ptr.tag() + intptr_t(m_ptr.ptr());
    }
    std::string toString() const {
      if (isUnseen()) return "Unseen";
      if (isBad()) return "Bad";
      char* type;
      if (instruction()) type = "Inst";
      else if (isPhi()) type = "Phi";
      else if (pending()) type = "Pending";
      else if (processed()) type = "Processed";
      else type = "XXX";
      return folly::sformat("{}:0x{:x}",type, uintptr_t(m_ptr.ptr()));
    }
   private:
    Kind kind() const { return m_ptr.tag(); }
    CompactTaggedPtr<void, Kind> m_ptr;
  };
  
  struct StoreKey {
    enum Where { In, Out };
    StoreKey(uint32_t id, Where w, uint32_t aId) :
        blkId(id), where(w), alocId(aId) {}
    StoreKey(const Block* blk, Where w, uint32_t aId) :
        blkId(blk->id()), where(w), alocId(aId) {}
    StoreKey(const Block& blk, Where w, uint32_t aId) :
        blkId(blk.id()), where(w), alocId(aId) {}
  
    uint32_t blkId;
    Where    where;
    uint32_t alocId;
  };
  
  struct StoreKeyHashCmp {
    size_t operator()(const StoreKey& k) const {
      return (k.blkId * 2 + (int)k.where) * kMaxTrackedALocs + k.alocId;
    }
    size_t operator()(const StoreKey& k1, const StoreKey& k2) const {
      return
        k1.blkId == k2.blkId &&
        k1.where == k2.where &&
        k1.alocId == k2.alocId;
    }
    static uint32_t size(uint32_t numBlocks) {
      return (numBlocks + 1) * 2 * kMaxTrackedALocs;
    }
  };
  
  using MovableStoreMap = hphp_hash_map<StoreKey, TrackedStore,
                                        StoreKeyHashCmp, StoreKeyHashCmp>;
  
  struct TrackedStoreHashCmp {
    size_t operator()(const TrackedStore& ts) const {
      return ts.hash();
    }
    bool operator()(const TrackedStore& ts1, const TrackedStore& ts2) const {
      return ts1.same(ts2);
    }
  };
  
  using SpillFrameMap = hphp_hash_map<TrackedStore, ALocBits,
                                      TrackedStoreHashCmp, TrackedStoreHashCmp>;
  
  struct BlockState {
    PostOrderId id;
    ALocBits antIn;
    ALocBits antOut;
    ALocBits pAntIn;
    ALocBits pAntOut;
    ALocBits ppIn;
    ALocBits ppOut;
  };
  
  // Environment for the whole optimization pass.
  struct Global {
    explicit Global(IRUnit& unit)
      : unit(unit)
      , poBlockList(poSortCfg(unit))
      , ainfo(collect_aliases(unit, poBlockList))
      , blockStates(unit, BlockState{})
      , seenStores(unit, 0)
    {}
  
    IRUnit& unit;
    BlockList poBlockList;
    AliasAnalysis ainfo;
  
    // We keep an entry for each tracked SpillFrame in this map, so we
    // can check its ALocBits
    SpillFrameMap spillFrameMap;
    MovableStoreMap trackedStoreMap;
    // Block states are indexed by block->id().  These are only meaningful after
    // we do dataflow.
    StateVector<Block,BlockState> blockStates;
    jit::vector<IRInstruction*> reStores;
    // Used to prevent cycles in find_candidate_store
    StateVector<Block,uint32_t> seenStores;
    uint32_t seenStoreId{0};
    bool needsReflow{false};
  };
  
  // Block-local environment.
  struct Local {
    explicit Local(Global& global)
      : global(global)
    {}
  
    Global& global;
  
    ALocBits antLoc;     // Copied to BlockAnalysis::antLoc
    ALocBits mayLoad;    // Things that may be read in the block
    ALocBits mayStore;   // Things that may be written in the block
    ALocBits avlLoc;     // Copied to BlockAnalysis::avlLoc
    ALocBits delLoc;     // Copied to BlockAnalysis::delLoc
  
    ALocBits reStores;
  
    bool containsCall{false}; // If there's a Call instruction in this block
  };
  
  //////////////////////////////////////////////////////////////////////
  
  using jit::show;
  
  const char* show(StoreKey::Where w) {
    switch (w) {
      case StoreKey::In:  return "In";
      case StoreKey::Out: return "Out";
    }
    not_reached();
  }
  
  std::string show(TrackedStore ts) {
    if (ts.isUnseen()) return "U";
    if (ts.isBad()) return "B";
    if (auto i = ts.instruction()) return folly::sformat("I{}", i->id());
    if (auto i = ts.processed()) return folly::sformat("I*{}", i->id());
    if (auto b = ts.block()) return folly::sformat("P{}", b->id());
    if (auto b = ts.pending()) return folly::sformat("P*{}", b->id());
    not_reached();
  }
  
  bool srcsCanSpanCall(const IRInstruction& inst) {
    for (auto i = inst.numSrcs(); i--; ) {
      auto const src = inst.src(i);
      if (!src->isA(TStkPtr) &&
          !src->isA(TFramePtr) &&
          !src->inst()->is(DefConst)) return false;
    }
    return true;
  }
  
  const ALocBits* findSpillFrame(Global& genv, const TrackedStore& ts) {
    auto it = genv.spillFrameMap.find(ts);
    if (it == genv.spillFrameMap.end()) return nullptr;
    return &it->second;
  }
  
  void set_movable_store(Local& env, uint32_t bit, IRInstruction& inst) {
    env.global.trackedStoreMap[
      StoreKey { inst.block(), StoreKey::Out, bit }].set(&inst);
  }
  
  void set_movable_spill_frame(Local& env, const ALocBits& bits,
                               IRInstruction& inst) {
    TrackedStore ts { &inst };
    bitset_for_each_set(
      bits,
      [&](uint32_t i) {
        env.global.trackedStoreMap[
          StoreKey { inst.block(), StoreKey::Out, i }] = ts;
      }
    );
    env.global.spillFrameMap[ts] = bits;
  }
  
  bool isDead(Local& env, int bit) {
    return env.antLoc[bit];
  }
  
  bool isDeadSet(Local& env, const ALocBits& bits) {
    return (~env.antLoc & bits).none();
  }
  
  bool removeDead(Local& env, IRInstruction& inst, bool trash) {
    BISECTOR(store_delete);
    if (!store_delete.go()) return false;
  
    FTRACE(4, "      dead (removed)\n");
  
    IRInstruction* dbgInst = nullptr;
    if (trash && RuntimeOption::EvalHHIRGenerateAsserts) {
      switch (inst.op()) {
      case StStk:
        dbgInst = env.global.unit.gen(
          DbgTrashStk,
          inst.bcctx(),
          IRSPRelOffsetData { inst.extra<StStk>()->offset },
          inst.src(0)
        );
        break;
      case SpillFrame:
        dbgInst = env.global.unit.gen(
          DbgTrashFrame,
          inst.bcctx(),
          IRSPRelOffsetData { inst.extra<SpillFrame>()->spOffset },
          inst.src(0)
        );
        break;
      case StMem:
        dbgInst = env.global.unit.gen(DbgTrashMem, inst.bcctx(), inst.src(0));
        break;
      default:
        dbgInst = nullptr;
        break;
      }
    }
  
    auto block = inst.block();
    auto pos = block->erase(&inst);
    if (dbgInst) {
      block->insert(pos, dbgInst);
      return false;
    }
    return true;
  }
  
  void addLoadSet(Local& env, const ALocBits& bits) {
    FTRACE(4, "           load: {}\n", show(bits));
    env.mayLoad |= bits;
    env.antLoc &= ~bits;
  }
  
  void addAllLoad(Local& env) {
    FTRACE(4, "           load: -1\n");
    env.mayLoad.set();
    env.antLoc.reset();
  }
  
  void mustStore(Local& env, int bit) {
    FTRACE(4, "      mustStore: {}\n", bit);
    if (!env.antLoc[bit] &&
        !env.mayLoad[bit]) {
      env.delLoc[bit] = 1;
    }
    env.antLoc[bit] = 1;
    env.mayStore[bit] = 0;
    env.reStores[bit] = 0;
  }
  
  void mustStoreSet(Local& env, const ALocBits& bits) {
    FTRACE(4, "      mustStore: {}\n", show(bits));
    env.delLoc |= bits & ~(env.antLoc | env.mayLoad);
    env.antLoc |= bits;
    env.mayStore &= ~bits;
    env.reStores &= ~bits;
  }
  
  void killSet(Local& env, const ALocBits& bits) {
    FTRACE(4, "           kill: {}\n", show(bits));
    env.mayLoad &= ~bits;
    mustStoreSet(env, bits);
  }
  
  //////////////////////////////////////////////////////////////////////
  
  void load(Local& env, AliasClass acls) {
    addLoadSet(env, env.global.ainfo.may_alias(canonicalize(acls)));
  }
  
  void mayStore(Local& env, AliasClass acls) {
    auto const canon = canonicalize(acls);
    auto const mayStore = env.global.ainfo.may_alias(canon);
    FTRACE(4, "       mayStore: {}\n", show(mayStore));
    env.mayStore |= mayStore;
    env.reStores &= ~mayStore;
  }
  
  void kill(Local& env, AliasClass acls) {
    auto const canon = canonicalize(acls);
    killSet(env, env.global.ainfo.expand(canon));
  }
  
  //////////////////////////////////////////////////////////////////////
  
  folly::Optional<uint32_t> pure_store_bit(Local& env, AliasClass acls) {
    if (auto const meta = env.global.ainfo.find(canonicalize(acls))) {
      return meta->index;
    }
    return folly::none;
  }
  
  void visit(Local& env, IRInstruction& inst) {
    auto const effects = memory_effects(inst);
    FTRACE(3, "    {}\n"
              "      {}\n",
              inst.toString(),
              show(effects));
  
    match<void>(
      effects,
      [&] (IrrelevantEffects) {
        switch (inst.op()) {
        case AssertLoc:
          load(env, AFrame { inst.src(0), inst.extra<AssertLoc>()->locId });
          return;
        case AssertStk:
          load(env, AStack { inst.src(0), inst.extra<AssertStk>()->offset, 1 });
          return;
        default:
          return;
        }
      },
      [&] (UnknownEffects)    { addAllLoad(env); env.mayStore.set(); },
      [&] (PureLoad l) {
        if (auto bit = pure_store_bit(env, l.src)) {
          if (env.reStores[*bit]) {
            auto const st = memory_effects(*env.global.reStores[*bit]);
            auto const pst = boost::get<PureStore>(&st);
            if (pst && pst->value && pst->value == inst.dst()) {
              FTRACE(4, "Killing self-store: {}\n",
                     env.global.reStores[*bit]->toString());
              removeDead(env, *env.global.reStores[*bit], false);
              env.reStores[*bit] = 0;
            }
          }
        }
        load(env, l.src);
      },
      [&] (GeneralEffects l)  {
        load(env, l.loads);
        mayStore(env, l.stores);
        kill(env, l.kills);
      },
  
      [&] (ReturnEffects l) {
        // Return from the main function.  Locations other than the frame and
        // stack (e.g. object properties and whatnot) are always live on a
        // function return---so mark everything read before we start killing
        // things.
        addAllLoad(env);
        killSet(env, env.global.ainfo.all_frame);
        killSet(env, env.global.ainfo.all_clsRefClsSlot);
        killSet(env, env.global.ainfo.all_clsRefTSSlot);
        kill(env, l.kills);
      },
  
      [&] (ExitEffects l) {
        load(env, l.live);
        kill(env, l.kills);
      },
  
      /*
       * Call instructions can potentially read any heap location, but we can be
       * more precise about everything else.
       */
      [&] (CallEffects l) {
        env.containsCall = true;
  
        load(env, AHeapAny);
  
        load(env, l.locals);
        if (l.writes_locals) mayStore(env, AFrameAny);
  
        load(env, l.stack);
        kill(env, l.kills);
      },
  
      [&] (PureStore l) {
        if (auto bit = pure_store_bit(env, l.dst)) {
          if (isDead(env, *bit)) {
            if (!removeDead(env, inst, true)) {
              mayStore(env, l.dst);
              mustStore(env, *bit);
            }
            return;
          }
          if (!env.antLoc[*bit] &&
              !env.mayLoad[*bit] &&
              !env.mayStore[*bit] &&
              (!env.containsCall ||
               srcsCanSpanCall(inst))) {
            env.avlLoc[*bit] = 1;
            set_movable_store(env, *bit, inst);
          }
          mayStore(env, l.dst);
          mustStore(env, *bit);
          if (!l.value || l.value->inst()->block() != inst.block()) return;
          auto const le = memory_effects(*l.value->inst());
          auto pl = boost::get<PureLoad>(&le);
          if (!pl) return;
          auto lbit = pure_store_bit(env, pl->src);
          if (!lbit || *lbit != *bit) return;
          /*
           * The source of the store is a load from the same address, which is
           * also in this block. If there's no interference, we can kill this
           * store. We won't know until we see the load though.
           */
          if (env.global.reStores.size() <= *bit) {
            env.global.reStores.resize(*bit + 1);
          }
          env.global.reStores[*bit] = &inst;
          env.reStores[*bit] = 1;
          return;
        }
        mayStore(env, l.dst);
      },
  
      [&] (PureSpillFrame l) {
        auto const it = env.global.ainfo.stack_ranges.find(canonicalize(l.stk));
        if (it != end(env.global.ainfo.stack_ranges)) {
          // If all the bits corresponding to the stack range are dead, we can
          // eliminate this instruction.  We can also count all of them as
          // redefined.
          if (isDeadSet(env, it->second)) {
            if (removeDead(env, inst, true)) return;
          } else {
            auto avlLoc = it->second & ~(env.antLoc | env.mayLoad |
                                         env.mayStore);
            if (avlLoc == it->second &&
                (!env.containsCall ||
                 srcsCanSpanCall(inst))) {
              set_movable_spill_frame(env, avlLoc, inst);
              env.avlLoc |= avlLoc;
            }
          }
          mayStore(env, l.stk);
          mustStoreSet(env, it->second);
          return;
        }
        mayStore(env, l.stk);
      }
    );
  }
  
  void block_visit(Local& env, Block* block) {
    FTRACE(2, "  visiting B{}\n", block->id());
    assertx(!block->instrs().empty());
  
    auto prev = std::prev(block->instrs().end());
    for (;;) {
      auto it = prev;
      if (it != block->instrs().begin()) {
        prev = std::prev(it);
        visit(env, *it);
      } else {
        visit(env, *it);
        break;
      }
    }
  }
  
  //////////////////////////////////////////////////////////////////////
  
  struct BlockAnalysis {
    ALocBits antLoc;
    ALocBits alteredAnt;
    ALocBits alteredAvl;
    ALocBits avlLoc;
    ALocBits delLoc;
    bool containsCall;
  };
  
  BlockAnalysis analyze_block(Global& genv, Block* block) {
    auto env = Local { genv };
    env.antLoc.reset(); // During this first analysis pass, we need to pretend
                        // none of the stores is anticipated (because we don't yet
                        // know). We may still remove some stores during this
                        // visit if they are locally proven dead, however.
    block_visit(env, block);
    return BlockAnalysis {
      env.antLoc,
      env.mayLoad,
      // Note that we unset must-store bits in env.mayStore, so including
      // env.antLoc and env.delLoc is required for correctness here.
      env.mayLoad | env.mayStore | env.antLoc | env.delLoc,
      env.avlLoc,
      env.delLoc,
      env.containsCall
    };
  }
  
  void find_all_stores(Global& genv, Block* blk, uint32_t id,
                       jit::vector<IRInstruction*>& stores,
                       jit::hash_set<void*>& seen) {
    ITRACE(7, "find_all_stores: {} B{}\n", id, blk->id());
    Trace::Indent _i;
    blk->forEachPred(
      [&](Block* pred) {
        if (!seen.insert(pred).second) {
          ITRACE(7, "find_all_stores: {} B{} skipping pred B{}\n",
                 id, blk->id(), pred->id());
          return;
        }
        ITRACE(7, "find_all_stores: {} B{} processing pred B{}\n",
               id, blk->id(), pred->id());
        auto& pst =
          genv.trackedStoreMap[StoreKey { pred, StoreKey::Out, id }];
        IRInstruction* inst;
        if ((inst = pst.instruction()) != nullptr ||
            (inst = pst.processed()) != nullptr) {
          if (seen.insert(inst).second) {
            ITRACE(7, "find_all_stores: {} B{} pred B{}: adding {}\n",
                   id, blk->id(), pred->id(), inst->toString());
            stores.push_back(inst);
          } else {
            ITRACE(7, "find_all_stores: {} B{} pred B{}: dropping {}\n",
                   id, blk->id(), pred->id(), inst->toString());
          }
          return;
        }
        Block* b;
        if ((b = pst.block()) != nullptr ||
            (b = pst.pending()) != nullptr) {
          if (b != pred && seen.count(b)) {
            ITRACE(7,
                   "find_all_stores: {} B{} pred B{} previously processed B{}\n",
                   id, blk->id(), pred->id(), b->id());
            return;
          }
          ITRACE(7, "find_all_stores: {} B{} pred B{} recur to B{}\n",
                 id, blk->id(), pred->id(), b->id());
          return find_all_stores(genv, b, id, stores, seen);
        }
        always_assert(false);
      }
    );
  }
  
  IRInstruction* resolve_ts(Global& genv, Block* blk,
                            StoreKey::Where w, uint32_t id,
                            const ALocBits** sfp = nullptr);
  
  void resolve_cycle(Global& genv, TrackedStore& ts, Block* blk, uint32_t id) {
    genv.needsReflow = true;
    jit::vector<IRInstruction*> stores;
    jit::hash_set<void*> seen;
    // find all the stores, so we can determine
    // whether a phi is actually required for each
    // src (also, we need a candidate store to clone)
  
    seen.insert(blk);
  
    ITRACE(7, "resolve_cycle - store id {}:\n", id);
    Trace::Indent _i;
  
    find_all_stores(genv, blk, id, stores, seen);
    always_assert(stores.size() > 0);
    if (Trace::moduleEnabled(TRACEMOD, 7)) {
      for (auto const DEBUG_ONLY st : stores) {
        ITRACE(7, "  - {}\n", st->toString());
      }
    }
    auto const cand = stores[0];
    if (stores.size() == 1) {
      ts.set(cand);
      return;
    }
    jit::vector<uint32_t> srcsToPhi;
    for (uint32_t i = 0; i < cand->numSrcs(); i++) {
      SSATmp* prev = nullptr;
      for (auto const st : stores) {
        auto const si = st->src(i);
        if (prev && prev != si) {
          srcsToPhi.push_back(i);
          break;
        }
        prev = si;
      }
    }
    if (!srcsToPhi.size()) {
      // the various stores all had the same inputs
      // so nothing to do.
      ts.set(cand);
      return;
    }
    bool needsProcessed = false;
    auto const inst = genv.unit.clone(cand);
    for (auto i : srcsToPhi) {
      auto t = TBottom;
      for (auto const st : stores) {
        t |= st->src(i)->type();
      }
      if (t.admitsSingleVal()) {
        inst->setSrc(i, genv.unit.cns(t));
        continue;
      }
      needsProcessed = true;
      // create a Mov; we'll use its dst as the src of the store, and
      // when we eventually create the phi, we'll set its dst as the src
      // of the Mov (this allows us to avoid creating a new phi if
      // there's already a suitable one there). We also set the Mov's
      // src to be its dst, so that we can identify it as needing to be
      // fixed up in resolve_flat.
      auto mv = genv.unit.gen(Mov, blk->front().bcctx(), cand->src(i));
      blk->prepend(mv);
      inst->setSrc(i, mv->dst());
      mv->setSrc(0, mv->dst());
      mv->dst()->setType(t);
      ITRACE(7, "  + created {} for {}\n", mv->toString(), inst->toString());
    }
    if (needsProcessed) {
      ts.setProcessed(inst);
    } else {
      ts.set(inst);
    }
  }
  
  IRInstruction* resolve_flat(Global& genv, Block* blk, uint32_t id,
                              TrackedStore& ts) {
    ts.setPending(blk);
  
    jit::vector<IRInstruction*> stores;
    blk->forEachPred([&](Block* pred) {
        stores.push_back(resolve_ts(genv, pred, StoreKey::Out, id));
      });
    always_assert(stores.size() > 0);
    if (auto const rep = ts.instruction()) {
      ITRACE(7, "resolve_flat: returning {}\n", rep->toString());
      return rep;
    }
  
    auto const cand = stores[0];
    if (stores.size() == 1) return cand;
    assertx(blk->numPreds() == stores.size());
    auto& preds = blk->preds();
    jit::vector<SSATmp*> newSrcs;
    jit::vector<uint32_t> srcsToPhi;
    for (uint32_t i = 0; i < cand->numSrcs(); i++) {
      bool same = true;
      SSATmp* temp = nullptr;
      jit::hash_map<Block*, SSATmp*> phiInputs;
      uint32_t j = 0;
      for (auto const& edge : preds) {
        auto const st = stores[j++];
        auto si = st->src(i);
        if (!si->inst()->is(DefConst) && si->type().admitsSingleVal()) {
          si = genv.unit.cns(si->type());
        }
        phiInputs[edge.from()] = si;
        if (temp == nullptr) temp = si;
        if (si != temp) same = false;
      }
      if (!same) {
        srcsToPhi.push_back(i);
        newSrcs.push_back(insertPhi(genv.unit, blk, phiInputs));
      } else if (ts.processed()) {
        // even if we don't need a phi, resolve_cycle might have thought
        // we did; if so, we still need to fix up the input.
        auto const mv = ts.processed()->src(i)->inst();
        if (mv->is(Mov) && mv->src(0) == mv->dst()) {
          srcsToPhi.push_back(i);
          newSrcs.push_back(temp);
        }
      }
    }
  
    if (auto rep = ts.processed()) {
      if (Trace::moduleEnabled(TRACEMOD, 7)) {
        ITRACE(7, "resolve_flat: fixing {}\n", rep->toString());
        for (auto const DEBUG_ONLY st : stores) {
          ITRACE(7, "    - {}\n", st->toString());
        }
      }
      // the replacement was constructed during the recursive
      // walk. Just need to hook up the new phis.
      for (uint32_t ix = 0; ix < srcsToPhi.size(); ix++) {
        auto i = srcsToPhi[ix];
        auto src = rep->src(i);
        auto mv = src->inst();
        always_assert(mv->is(Mov) && mv->src(0) == mv->dst());
        mv->setSrc(0, newSrcs[ix]);
        retypeDests(mv, &genv.unit);
      }
      return rep;
    }
  
    auto rep = genv.unit.clone(cand);
    for (uint32_t ix = 0; ix < srcsToPhi.size(); ix++) {
      auto i = srcsToPhi[ix];
      rep->setSrc(i, newSrcs[ix]);
    }
  
    return rep;
  }
  
  IRInstruction* resolve_ts(Global& genv, Block* blk,
                            StoreKey::Where w, uint32_t id,
                            const ALocBits** sfp) {
    auto& ts = genv.trackedStoreMap[StoreKey { blk, w, id }];
    auto sf = findSpillFrame(genv, ts);
    if (sfp) *sfp = sf;
  
    ITRACE(7, "resolve_ts: B{}:{} store:{} ts:{}\n",
           blk->id(), show(w), id, show(ts));
    Trace::Indent _i;
  
    if (ts.pending()) {
      always_assert(ts.pending() == blk);
      resolve_cycle(genv, ts, blk, id);
      assertx(ts.instruction() || ts.processed());
    }
  
    if (auto inst = ts.instruction()) {
      ITRACE(7, "-> inst: {}\n", inst->toString());
      return inst;
    }
    if (auto inst = ts.processed()) {
      ITRACE(7, "-> proc: {}\n", inst->toString());
      return inst;
    }
  
    always_assert(ts.block());
    if (w != StoreKey::In || blk != ts.block()) {
      ITRACE(7, "direct recur: B{}:{} -> B{}:In\n",
             blk->id(), show(w), ts.block()->id());
      ts.set(resolve_ts(genv, ts.block(), StoreKey::In, id));
    } else {
      ts.set(resolve_flat(genv, blk, id, ts));
    }
    auto const rep = ts.instruction();
  
    if (sf) genv.spillFrameMap[ts] = *sf;
    ITRACE(7, "-> {} (resolve_ts B{}, store {})\n",
           rep->toString(), blk->id(), id);
    return rep;
  }
  
  void optimize_block_pre(Global& genv, Block* block,
                          const jit::vector<BlockAnalysis>& blockAnalysis) {
    auto& state = genv.blockStates[block];
    auto const& transfer = blockAnalysis[state.id];
    auto insertBits = state.ppIn & ~state.antIn &
      (~state.ppOut | transfer.alteredAvl);
    auto const deleteBits =
        (state.antOut & transfer.delLoc) | (state.ppOut & transfer.avlLoc);
  
    if (deleteBits.any()) {
      FTRACE(1,
             "Optimize B{}:\n"
             "  Delete: {}\n",
             block->id(),
             show(deleteBits));
  
      auto env = Local { genv };
      env.antLoc = deleteBits;
      block_visit(env, block);
    }
    if (insertBits.any()) {
      // warning: if you turn off any stores using this bisector, you
      // need to disable the corresponding deletes (or simpler, all
      // deletes) using store_delete.
      BISECTOR(store_insert);
      FTRACE(1,
             "Optimize B{}:\n"
             "  Insert: {}\n",
             block->id(),
             show(insertBits));
  
      bitset_for_each_set(
        insertBits,
        [&](size_t i){
          if (!store_insert.go()) return;
          const ALocBits* sf = nullptr;
          auto const cinst = resolve_ts(genv, block, StoreKey::In, i, &sf);
          if (sf) {
            always_assert((state.ppIn & *sf) == *sf);
            insertBits &= ~*sf;
          }
          FTRACE(1, " Inserting store {}: {}\n", i, cinst->toString());
          auto const inst = genv.unit.clone(cinst);
          block->prepend(inst);
        }
      );
    }
  }
  
  void optimize_block(Global& genv, Block* block) {
    auto& state = genv.blockStates[block];
    auto env = Local { genv };
    FTRACE(1,
           "Optimize B{}:\n"
           "  antOut: {}\n",
           block->id(),
           show(state.antOut));
    env.antLoc = state.antOut;
    block_visit(env, block);
  }
  
  enum class Direction { Forward, Backward };
  template <Direction dir, typename IFunc, typename UFunc, typename RFunc>
  void compute_dataflow(Global& genv,
                        const jit::vector<BlockAnalysis>& blockAnalysis,
                        IFunc init,
                        UFunc update,
                        RFunc reschedule) {
    using sorter = typename std::conditional<dir == Direction::Forward,
                                             std::less<PostOrderId>,
                                             std::greater<PostOrderId>>::type;
  
    auto incompleteQ =
      dataflow_worklist<PostOrderId, sorter>(genv.unit.numBlocks());
  
    for (auto poId = uint32_t{0}; poId < genv.poBlockList.size(); ++poId) {
      auto const blk = genv.poBlockList[poId];
      auto& state = genv.blockStates[blk];
      init(blk, state);
      incompleteQ.push(poId);
    }
  
    while (!incompleteQ.empty()) {
      auto const poId = incompleteQ.pop();
      auto const blk  = genv.poBlockList[poId];
  
      auto& state          = genv.blockStates[blk];
      auto const& transfer = blockAnalysis[poId];
      assertx(state.id == poId);
  
      if (!update(blk, transfer, state)) continue;
  
      /*
       * Update the predecessors / successors if things change
       */
      auto doblock = [&] (Block* other) {
        FTRACE(4, "   -> {}\n", other->id());
        auto& otherState = genv.blockStates[other];
  
        if (reschedule(state, otherState, incompleteQ)) {
          incompleteQ.push(otherState.id);
        }
      };
      if (dir == Direction::Forward) {
        blk->forEachSucc(doblock);
      } else {
        blk->forEachPred(doblock);
      }
    }
  }
  
  /*
   * Iterate on the antIn/antOut states until we reach a fixed point.
   */
  void compute_anticipated(Global& genv,
                           const jit::vector<BlockAnalysis>& blockAnalysis) {
    FTRACE(4, "Iterating Anticipated\n");
    compute_dataflow<Direction::Backward>(
      genv, blockAnalysis,
      /*
       * Important note: every block starts with a full antOut set,
       * including blocks that are exiting the region.  When an HHIR
       * region is exited, there's always some instruction we can use
       * to indicate via memory_effects what may be read (e.g.
       * EndCatch, RetCtrl, ReqBindJmp, etc).  When we start iterating,
       * we'll appropriately mark things as read based on these.
       */
      [](Block*, BlockState& state) { state.antOut.set(); },
      [](Block* blk, const BlockAnalysis& transfer, BlockState& state) {
        state.antIn = transfer.antLoc |
          (state.antOut & ~transfer.alteredAnt);
        state.pAntIn = transfer.antLoc |
          (state.pAntOut & ~transfer.alteredAnt);
        FTRACE(4,
               "  block B{}\n"
               "    antIn   : {}\n"
               "    pAntIn  : {}\n"
               "    antLoc  : {}\n"
               "    altered : {}\n"
               "    antOut  : {}\n"
               "    pAntOut : {}\n",
               blk->id(),
               show(state.antIn),
               show(state.pAntIn),
               show(transfer.antLoc),
               show(transfer.alteredAnt),
               show(state.antOut),
               show(state.pAntOut));
        return true;
      },
      [](const BlockState& state, BlockState& pred,
         dataflow_worklist<PostOrderId>&) {
        auto const oldAntOut = pred.antOut;
        auto const oldPAntOut = pred.pAntOut;
        pred.antOut &= state.antIn;
        pred.pAntOut |= state.pAntIn;
        return pred.antOut != oldAntOut || pred.pAntOut != oldPAntOut;
      });
  }
  
  TrackedStore find_candidate_store_helper(Global& genv, TrackedStore ts,
                                           uint32_t id) {
    auto block = ts.block();
    assertx(block);
    TrackedStore ret;
    if (genv.seenStores[block] == genv.seenStoreId) return ret;
  
    // look for a candidate in the immediate predecessors
    block->forEachPred([&](Block* pred) {
        if (ret.isBad() || ret.instruction()) return;
        auto const pred_ts =
          genv.trackedStoreMap[StoreKey { pred, StoreKey::Out, id }];
        if (pred_ts.isBad() || pred_ts.instruction()) {
          ret = pred_ts;
          return;
        }
      });
  
    if (ret.isBad() || ret.instruction()) return ret;
  
    genv.seenStores[block] = genv.seenStoreId;
    // recursively search the predecessors
    block->forEachPred([&](Block* pred) {
        if (ret.isBad() || ret.instruction()) return;
        auto const pred_ts =
          genv.trackedStoreMap[StoreKey { pred, StoreKey::Out, id }];
        if (!pred_ts.block()) {
          always_assert_flog(pred_ts.isUnseen(),
                             "pred_ts: {}", pred_ts.toString());
          return;
        }
        ret = find_candidate_store_helper(genv, pred_ts, id);
      });
  
    return ret;
  }
  
  /*
   * Find a candidate store instruction; any one will do, because
   * compatibility between stores is transitive.
   */
  TrackedStore find_candidate_store(Global& genv, TrackedStore ts, uint32_t id) {
    if (!ts.block()) return ts;
    genv.seenStoreId++;
    return find_candidate_store_helper(genv, ts, id);
  }
  
  TrackedStore combine_ts(Global& genv, uint32_t id,
                          TrackedStore s1,
                          TrackedStore s2, Block* succ) {
    if (s1.same(s2)) return s1;
    if (s1.isUnseen() || s2.isBad()) return s2;
    if (s2.isUnseen() || s1.isBad()) return s1;
  
    enum class Compat { Same, Compat, Bad };
    auto compat = [](TrackedStore store1, TrackedStore store2) {
      auto i1 = store1.instruction();
      auto i2 = store2.instruction();
      assertx(i1 && i2);
      if (i1->op() != i2->op()) return Compat::Bad;
      if (i1->numSrcs() != i2->numSrcs()) return Compat::Bad;
      for (auto i = i1->numSrcs(); i--; ) {
        if (i1->src(i) != i2->src(i)) return Compat::Compat;
      }
      return Compat::Same;
    };
  
    auto sf1 = findSpillFrame(genv, s1);
    auto sf2 = findSpillFrame(genv, s2);
  
    // t7621182 Don't merge different spillframes for now,
    // because code-gen doesn't handle phi'ing an Obj and a
    // Cls.
    if (sf1 || sf2) {
      // we already know they aren't the same
      return TrackedStore::BadVal();
    }
  
    if (!sf1 != !sf2 || (sf1 && *sf1 != *sf2)) {
      // They need to both be spill frames affecting
      // the same addresses, or both not be spill frames.
      return TrackedStore::BadVal();
    }
  
    auto trackedBlock = [&]() {
      auto ret = TrackedStore(succ, id);
      if (sf1) genv.spillFrameMap[ret] = *sf1;
      return ret;
    };
  
    if (s1.block() || s2.block()) {
      auto c1 = find_candidate_store(genv, s1, id);
      auto c2 = find_candidate_store(genv, s2, id);
      if (c1.instruction() && c2.instruction() &&
          compat(c1, c2) != Compat::Bad) {
        return trackedBlock();
      }
      return TrackedStore::BadVal();
    }
  
    switch (compat(s1, s2)) {
      case Compat::Same:   return s1;
      case Compat::Compat: return trackedBlock();
      case Compat::Bad:    break;
    }
    return TrackedStore::BadVal();
  }
  
  /*
   * Compute a TrackedStore for succ by merging its preds.
   */
  TrackedStore recompute_ts(Global& genv, uint32_t id, Block* succ) {
    TrackedStore ret;
    succ->forEachPred([&](Block* pred) {
        auto const ts =
          genv.trackedStoreMap[StoreKey { pred, StoreKey::Out, id }];
        ret = combine_ts(genv, id, ts, ret, succ);
      });
    return ret;
  }
  
  /*
   * Compute a starting point for ppIn/ppOut based on global availability.
   * At the same time, compute exactly which stores are available at each
   * point. This is essentially the bitvector implementation of global
   * availability, but disallowing the cases where we can't find/create
   * a suitable store.
   */
  void compute_available_stores(
    Global& genv, const jit::vector<BlockAnalysis>& blockAnalysis) {
  
    FTRACE(4, "\nIterating Available Stores\n");
    compute_dataflow<Direction::Forward>(
      genv, blockAnalysis,
      [](Block* blk, BlockState& state) {
        if (blk->numPreds()) state.ppIn.set();
      },
      [&](Block* blk, const BlockAnalysis& transfer, BlockState& state) {
        state.ppOut = transfer.avlLoc | (state.ppIn & ~transfer.alteredAvl);
        auto propagate = state.ppOut & ~transfer.avlLoc;
        bitset_for_each_set(
          propagate,
          [&](uint32_t i) {
            auto const& tsIn =
              genv.trackedStoreMap[StoreKey { blk, StoreKey::In, i }];
            auto& tsOut =
              genv.trackedStoreMap[StoreKey { blk, StoreKey::Out, i }];
            assertx(!tsIn.isUnseen());
  
            // Prevent tmps from spanning calls by not propagating tracked stores
            // thru any block which contains a call. The exception is if the store
            // only uses constants as those do not create a problem.
            if (transfer.containsCall &&
                (!tsIn.instruction() || !srcsCanSpanCall(*tsIn.instruction()))) {
              tsOut.setBad();
            } else {
              tsOut = tsIn;
            }
  
            if (tsOut.isBad()) {
              state.ppOut[i] = false;
            } else if (auto sf = findSpillFrame(genv, tsIn)) {
              if ((propagate & *sf) != *sf) {
                state.ppOut &= ~*sf;
              }
            }
          }
        );
        auto showv DEBUG_ONLY = [&] (StoreKey::Where w, const ALocBits& pp) {
          std::string r;
          bitset_for_each_set(
            pp,
            [&](uint32_t i) {
              auto& ts = genv.trackedStoreMap[StoreKey { blk, w, i}];
              folly::format(&r, " {}:{}", i, show(ts));
            }
          );
          return r;
        };
        FTRACE(4,
               "  block B{}\n"
               "    ppIn     : {}\n"
               "    ppInV    : {}\n"
               "    avlLoc   : {}\n"
               "    altered  : {}\n"
               "    ppOut    : {}\n"
               "    ppOutV   : {}\n",
               blk->id(),
               show(state.ppIn),
               showv(StoreKey::In, state.ppIn),
               show(transfer.avlLoc),
               show(transfer.alteredAvl),
               show(state.ppOut),
               showv(StoreKey::Out, state.ppOut));
        return true;
      },
      [&](const BlockState& state, BlockState& succState,
          dataflow_worklist<PostOrderId, std::less<PostOrderId>>&) {
        auto const oldPpIn = succState.ppIn;
        succState.ppIn &= state.ppOut;
        bool changed = succState.ppIn != oldPpIn;
        auto blk = genv.poBlockList[state.id];
        auto succ = genv.poBlockList[succState.id];
        bitset_for_each_set(
          succState.ppIn,
          [&](uint32_t i) {
            auto& ts =
              genv.trackedStoreMap[StoreKey { blk, StoreKey::Out, i }];
            auto& tsSucc =
              genv.trackedStoreMap[StoreKey { succ, StoreKey::In, i }];
            auto sf = findSpillFrame(genv, ts);
            if (sf) {
              if ((succState.ppIn & *sf) != *sf) {
                changed = true;
                tsSucc.setBad();
                succState.ppIn &= ~*sf;
                return;
              }
            }
            auto tsNew = succ->numPreds() == 1 ? ts : recompute_ts(genv, i, succ);
            if (!tsNew.same(tsSucc)) {
              changed = true;
              assertx(tsNew >= tsSucc);
              tsSucc = tsNew;
              if (tsSucc.isBad()) {
                if (sf) {
                  succState.ppIn &= ~*sf;
                } else {
                  succState.ppIn[i] = false;
                }
              }
            }
          }
        );
        return changed;
      });
  }
  
  /*
   * Iterate on the ppIn/ppOut states until we reach a fixed point.
   */
  void compute_placement_possible(
    Global& genv, const jit::vector<BlockAnalysis>& blockAnalysis) {
  
    compute_available_stores(genv, blockAnalysis);
  
    FTRACE(4, "\nIterating Placement Possible\n");
    compute_dataflow<Direction::Forward>(
      genv, blockAnalysis,
      [](Block* blk, BlockState& state) {
        if (!blk->numPreds()) state.ppIn.reset();
        if (!blk->numSuccs()) state.ppOut.reset();
      },
      [&](Block* blk, const BlockAnalysis& transfer, BlockState& state) {
        auto trace = [&] () {
          FTRACE(4,
                 "  block B{}\n"
                 "    ppIn :  {}\n"
                 "    avlLoc: {}\n"
                 "    altLoc: {}\n"
                 "    ppOut:  {}\n",
                 blk->id(),
                 show(state.ppIn),
                 show(transfer.avlLoc),
                 show(transfer.alteredAvl),
                 show(state.ppOut));
        };
  
        if (!blk->numSuccs()) {
          trace();
          // ppOut is empty for a block with no succs (since placement
          // is definitely not possible in any of its successors), and
          // its initialized to empty, so nothing to do.
          //
          // Note that this is not just an optimization - the update
          // below would produce the wrong results.
          return false;
        }
  
        state.ppOut = transfer.avlLoc | (state.ppIn & ~transfer.alteredAvl);
        auto restrictBits = state.pAntOut;
  
        blk->forEachSucc([&] (Block* succ) {
            auto const& succState = genv.blockStates[succ];
            restrictBits &= succState.ppIn | succState.antIn;
          });
  
        auto bitsToClear = state.ppOut & ~restrictBits;
        // ensure that if we clear any spill frame bits, we clear
        // them all.
        if (bitsToClear.any()) {
          bitset_for_each_set(
            bitsToClear,
            [&](uint32_t i) {
              auto const ts =
                genv.trackedStoreMap[StoreKey { blk, StoreKey::Out, i }];
              if (auto sf = findSpillFrame(genv, ts)) {
                restrictBits &= ~*sf;
              }
            }
          );
          state.ppOut &= restrictBits;
        }
        trace();
        return true;
      },
      [&](const BlockState& state, BlockState& succState,
          dataflow_worklist<PostOrderId, std::less<PostOrderId>>& incompleteQ) {
        auto const oldPPIn = succState.ppIn;
        succState.ppIn &= state.ppOut;
  
        if (succState.ppIn == oldPPIn) return false;
        FTRACE(4, "   reprocessing succ {}\n",
               genv.poBlockList[succState.id]->id());
        auto const ssppa = succState.ppIn | succState.antIn;
        if (ssppa != (oldPPIn | succState.antIn)) {
          // this change might affect this successor's
          // predecessors; reschedule them if necessary
          auto succ = genv.poBlockList[succState.id];
          auto blk = genv.poBlockList[state.id];
          succ->forEachPred([&] (Block* pred) {
              if (pred == blk) return; // can't be affected
              auto const& psState = genv.blockStates[pred];
              if ((psState.ppOut & ssppa) != psState.ppOut) {
                FTRACE(4, "   reprocessing succ's pred {}\n", pred->id());
                incompleteQ.push(psState.id);
              }
            });
        }
        return true;
      });
  }
  
  //////////////////////////////////////////////////////////////////////
  
  }
  
  void optimizeStores(IRUnit& unit) {
    PassTracer tracer{&unit, Trace::hhir_store, "optimizeStores"};
    Timer t(Timer::optimize_stores, unit.logEntry().get_pointer());
  
    // This isn't required for correctness, but it may allow removing stores that
    // otherwise we would leave alone.
    splitCriticalEdges(unit);
  
    /*
     * Global state for this pass, visible while processing any block.
     */
    auto genv = Global { unit };
    auto const& poBlockList = genv.poBlockList;
    if (genv.ainfo.locations.size() == 0) {
      FTRACE(1, "no memory accesses to possibly optimize\n");
      return;
    }
    FTRACE(1, "\nLocations:\n{}\n", show(genv.ainfo));
  
    /*
     * Initialize the block state structures.
     */
    for (auto poId = uint32_t{0}; poId < poBlockList.size(); ++poId) {
      genv.blockStates[poBlockList[poId]].id = poId;
    }
  
    /*
     * Analyze each block to compute its transfer function.
     *
     * The blockAnalysis vector is indexed by post order id.
     */
    auto const blockAnalysis = [&] () -> jit::vector<BlockAnalysis> {
      auto ret = jit::vector<BlockAnalysis>{};
      ret.reserve(unit.numBlocks());
      for (auto id = uint32_t{0}; id < poBlockList.size(); ++id) {
        ret.push_back(analyze_block(genv, poBlockList[id]));
      }
      return ret;
    }();
  
    FTRACE(2, "\nTransfer functions:\n{}\n",
      [&]() -> std::string {
        auto ret = std::string{};
        for (auto poId = uint32_t{0}; poId < poBlockList.size(); ++poId) {
          auto& analysis = blockAnalysis[poId];
          folly::format(
            &ret,
            " B{}\n"
            "   antLoc    : {}\n"
            "   alteredAnt: {}\n"
            "   alteredAvl: {}\n"
            "   avlLoc    : {}\n"
            "   delLoc    : {}\n",
            poBlockList[poId]->id(),
            show(analysis.antLoc),
            show(analysis.alteredAnt),
            show(analysis.alteredAvl),
            show(analysis.avlLoc),
            show(analysis.delLoc)
          );
        }
        return ret;
      }()
    );
  
    compute_anticipated(genv, blockAnalysis);
  
    if (!RuntimeOption::EvalHHIRStorePRE) {
      /*
       * We've reached a fixed point.
       * Delete redundant stores
       */
      FTRACE(2, "\nFixed point:\n{}\n",
             [&]() -> std::string {
               auto ret = std::string{};
               for (auto poId = uint32_t{0}; poId < poBlockList.size(); ++poId) {
                 auto const blk = poBlockList[poId];
                 auto const& state = genv.blockStates[blk];
                 folly::format(
                   &ret,
                   " B{: <3}: antOut {}\n",
                   blk->id(), show(state.antOut)
                 );
               }
               return ret;
             }()
            );
      for (auto& block : poBlockList) {
        optimize_block(genv, block);
      }
      return;
    }
  
    compute_placement_possible(genv, blockAnalysis);
  
    for (auto& block : poBlockList) {
      optimize_block_pre(genv, block, blockAnalysis);
    }
    if (genv.needsReflow) {
      reflowTypes(genv.unit);
    }
  }
  
  //////////////////////////////////////////////////////////////////////
  
  }}
  