js/src/jit/MIRGraph.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef jit_MIRGraph_h
   8 #define jit_MIRGraph_h
   9
  10 // This file declares the data structures used to build a control-flow graph
  11 // containing MIR.
  12
  13 #include "jit/CompileInfo.h"
  14 #include "jit/FixedList.h"
  15 #include "jit/InlineScriptTree.h"
  16 #include "jit/JitAllocPolicy.h"
  17 #include "jit/MIR.h"
  18
  19 namespace js {
  20 namespace jit {
  21
  22 class MBasicBlock;
  23 class MIRGraph;
  24 class MStart;
  25
  26 class MDefinitionIterator;
  27
  28 using MInstructionIterator = InlineListIterator<MInstruction>;
  29 using MInstructionReverseIterator = InlineListReverseIterator<MInstruction>;
  30 using MPhiIterator = InlineListIterator<MPhi>;
  31
  32 #ifdef DEBUG
  33 typedef InlineForwardListIterator<MResumePoint> MResumePointIterator;
  34 #endif
  35
  36 class LBlock;
  37
  38 class MBasicBlock : public TempObject, public InlineListNode<MBasicBlock> {
  39  public:
  40   enum Kind {
  41     NORMAL,
  42     PENDING_LOOP_HEADER,
  43     LOOP_HEADER,
  44     SPLIT_EDGE,
  45     FAKE_LOOP_PRED,
  46     INTERNAL,
  47     DEAD
  48   };
  49
  50  private:
  51   MBasicBlock(MIRGraph& graph, const CompileInfo& info, BytecodeSite* site,
  52               Kind kind);
  53   [[nodiscard]] bool init();
  54   void copySlots(MBasicBlock* from);
  55   [[nodiscard]] bool inherit(TempAllocator& alloc, size_t stackDepth,
  56                              MBasicBlock* maybePred, uint32_t popped);
  57
  58   // This block cannot be reached by any means.
  59   bool unreachable_ = false;
  60
  61   // This block will unconditionally bail out.
  62   bool alwaysBails_ = false;
  63
  64   // Will be used for branch hinting in wasm.
  65   wasm::BranchHint branchHint_ = wasm::BranchHint::Invalid;
  66
  67   // Pushes a copy of a local variable or argument.
  68   void pushVariable(uint32_t slot) { push(slots_[slot]); }
  69
  70   // Sets a variable slot to the top of the stack, correctly creating copies
  71   // as needed.
  72   void setVariable(uint32_t slot) {
  73     MOZ_ASSERT(stackPosition_ > info_.firstStackSlot());
  74     setSlot(slot, slots_[stackPosition_ - 1]);
  75   }
  76
  77   enum ReferencesType {
  78     RefType_None = 0,
  79
  80     // Assert that the instruction is unused.
  81     RefType_AssertNoUses = 1 << 0,
  82
  83     // Discard the operands of the resume point / instructions if the
  84     // following flag are given too.
  85     RefType_DiscardOperands = 1 << 1,
  86     RefType_DiscardResumePoint = 1 << 2,
  87     RefType_DiscardInstruction = 1 << 3,
  88
  89     // Discard operands of the instruction and its resume point.
  90     RefType_DefaultNoAssert = RefType_DiscardOperands |
  91                               RefType_DiscardResumePoint |
  92                               RefType_DiscardInstruction,
  93
  94     // Discard everything and assert that the instruction is not used.
  95     RefType_Default = RefType_AssertNoUses | RefType_DefaultNoAssert,
  96
  97     // Discard resume point operands only, without discarding the operands
  98     // of the current instruction.  Asserts that the instruction is unused.
  99     RefType_IgnoreOperands = RefType_AssertNoUses | RefType_DiscardOperands |
 100                              RefType_DiscardResumePoint
 101   };
 102
 103   void discardResumePoint(MResumePoint* rp,
 104                           ReferencesType refType = RefType_Default);
 105   void removeResumePoint(MResumePoint* rp);
 106
 107   // Remove all references to an instruction such that it can be removed from
 108   // the list of instruction, without keeping any dangling pointer to it. This
 109   // includes the operands of the instruction, and the resume point if
 110   // present.
 111   void prepareForDiscard(MInstruction* ins,
 112                          ReferencesType refType = RefType_Default);
 113
 114  public:
 115   ///////////////////////////////////////////////////////
 116   ////////// BEGIN GRAPH BUILDING INSTRUCTIONS //////////
 117   ///////////////////////////////////////////////////////
 118
 119   // Creates a new basic block for a MIR generator. If |pred| is not nullptr,
 120   // its slots and stack depth are initialized from |pred|.
 121   static MBasicBlock* New(MIRGraph& graph, size_t stackDepth,
 122                           const CompileInfo& info, MBasicBlock* maybePred,
 123                           BytecodeSite* site, Kind kind);
 124   static MBasicBlock* New(MIRGraph& graph, const CompileInfo& info,
 125                           MBasicBlock* pred, Kind kind);
 126   static MBasicBlock* NewPopN(MIRGraph& graph, const CompileInfo& info,
 127                               MBasicBlock* pred, BytecodeSite* site, Kind kind,
 128                               uint32_t popn);
 129   static MBasicBlock* NewPendingLoopHeader(MIRGraph& graph,
 130                                            const CompileInfo& info,
 131                                            MBasicBlock* pred,
 132                                            BytecodeSite* site);
 133   static MBasicBlock* NewSplitEdge(MIRGraph& graph, MBasicBlock* pred,
 134                                    size_t predEdgeIdx, MBasicBlock* succ);
 135   static MBasicBlock* NewFakeLoopPredecessor(MIRGraph& graph,
 136                                              MBasicBlock* header);
 137
 138   // Create a new basic block for internal control flow not present in the
 139   // original CFG.
 140   static MBasicBlock* NewInternal(MIRGraph& graph, MBasicBlock* orig,
 141                                   MResumePoint* activeResumePoint);
 142
 143   bool dominates(const MBasicBlock* other) const {
 144     return other->domIndex() - domIndex() < numDominated();
 145   }
 146
 147   void setId(uint32_t id) { id_ = id; }
 148
 149   // Mark this block (and only this block) as unreachable.
 150   void setUnreachable() {
 151     MOZ_ASSERT(!unreachable_);
 152     setUnreachableUnchecked();
 153   }
 154   void setUnreachableUnchecked() { unreachable_ = true; }
 155   bool unreachable() const { return unreachable_; }
 156
 157   void setAlwaysBails() { alwaysBails_ = true; }
 158   bool alwaysBails() const { return alwaysBails_; }
 159
 160   // Move the definition to the top of the stack.
 161   void pick(int32_t depth);
 162
 163   // Move the top of the stack definition under the depth-th stack value.
 164   void unpick(int32_t depth);
 165
 166   // Exchange 2 stack slots at the defined depth
 167   void swapAt(int32_t depth);
 168
 169   // Note: most of the methods below are hot. Do not un-inline them without
 170   // measuring the impact.
 171
 172   // Gets the instruction associated with various slot types.
 173   MDefinition* peek(int32_t depth) {
 174     MOZ_ASSERT(depth < 0);
 175     MOZ_ASSERT(stackPosition_ + depth >= info_.firstStackSlot());
 176     return peekUnchecked(depth);
 177   }
 178
 179   MDefinition* peekUnchecked(int32_t depth) {
 180     MOZ_ASSERT(depth < 0);
 181     return getSlot(stackPosition_ + depth);
 182   }
 183
 184   MDefinition* environmentChain();
 185   MDefinition* argumentsObject();
 186
 187   // Increase the number of slots available
 188   [[nodiscard]] bool increaseSlots(size_t num);
 189   [[nodiscard]] bool ensureHasSlots(size_t num);
 190
 191   // Initializes a slot value; must not be called for normal stack
 192   // operations, as it will not create new SSA names for copies.
 193   void initSlot(uint32_t slot, MDefinition* ins) {
 194     slots_[slot] = ins;
 195     if (entryResumePoint()) {
 196       entryResumePoint()->initOperand(slot, ins);
 197     }
 198   }
 199
 200   // Sets the instruction associated with various slot types. The
 201   // instruction must lie at the top of the stack.
 202   void setLocal(uint32_t local) { setVariable(info_.localSlot(local)); }
 203   void setArg(uint32_t arg) { setVariable(info_.argSlot(arg)); }
 204   void setSlot(uint32_t slot, MDefinition* ins) { slots_[slot] = ins; }
 205
 206   // Tracks an instruction as being pushed onto the operand stack.
 207   void push(MDefinition* ins) {
 208     MOZ_ASSERT(stackPosition_ < nslots());
 209     slots_[stackPosition_++] = ins;
 210   }
 211   void pushArg(uint32_t arg) { pushVariable(info_.argSlot(arg)); }
 212   void pushArgUnchecked(uint32_t arg) {
 213     pushVariable(info_.argSlotUnchecked(arg));
 214   }
 215   void pushLocal(uint32_t local) { pushVariable(info_.localSlot(local)); }
 216   void pushSlot(uint32_t slot) { pushVariable(slot); }
 217   void setEnvironmentChain(MDefinition* ins);
 218   void setArgumentsObject(MDefinition* ins);
 219
 220   // Returns the top of the stack, then decrements the virtual stack pointer.
 221   MDefinition* pop() {
 222     MOZ_ASSERT(stackPosition_ > info_.firstStackSlot());
 223     return slots_[--stackPosition_];
 224   }
 225   void popn(uint32_t n) {
 226     MOZ_ASSERT(stackPosition_ - n >= info_.firstStackSlot());
 227     MOZ_ASSERT(stackPosition_ >= stackPosition_ - n);
 228     stackPosition_ -= n;
 229   }
 230
 231   // Adds an instruction to this block's instruction list.
 232   inline void add(MInstruction* ins);
 233
 234   // Marks the last instruction of the block; no further instructions
 235   // can be added.
 236   void end(MControlInstruction* ins) {
 237     MOZ_ASSERT(!hasLastIns());  // Existing control instructions should be
 238                                 // removed first.
 239     MOZ_ASSERT(ins);
 240     add(ins);
 241   }
 242
 243   // Adds a phi instruction, but does not set successorWithPhis.
 244   void addPhi(MPhi* phi);
 245
 246   // Adds a resume point to this block.
 247   void addResumePoint(MResumePoint* resume) {
 248 #ifdef DEBUG
 249     resumePoints_.pushFront(resume);
 250 #endif
 251   }
 252
 253   // Discard pre-allocated resume point.
 254   void discardPreAllocatedResumePoint(MResumePoint* resume) {
 255     MOZ_ASSERT(!resume->instruction());
 256     discardResumePoint(resume);
 257   }
 258
 259   // Adds a predecessor. Every predecessor must have the same exit stack
 260   // depth as the entry state to this block. Adding a predecessor
 261   // automatically creates phi nodes and rewrites uses as needed.
 262   [[nodiscard]] bool addPredecessor(TempAllocator& alloc, MBasicBlock* pred);
 263   [[nodiscard]] bool addPredecessorPopN(TempAllocator& alloc, MBasicBlock* pred,
 264                                         uint32_t popped);
 265
 266   // Add a predecessor which won't introduce any new phis to this block.
 267   // This may be called after the contents of this block have been built.
 268   [[nodiscard]] bool addPredecessorSameInputsAs(MBasicBlock* pred,
 269                                                 MBasicBlock* existingPred);
 270
 271   // Stranger utilities used for inlining.
 272   [[nodiscard]] bool addPredecessorWithoutPhis(MBasicBlock* pred);
 273   void inheritSlots(MBasicBlock* parent);
 274   [[nodiscard]] bool initEntrySlots(TempAllocator& alloc);
 275
 276   // Replaces an edge for a given block with a new block. This is
 277   // used for critical edge splitting.
 278   //
 279   // Note: If successorWithPhis is set, you must not be replacing it.
 280   void replacePredecessor(MBasicBlock* old, MBasicBlock* split);
 281   void replaceSuccessor(size_t pos, MBasicBlock* split);
 282
 283   // Removes `pred` from the predecessor list. If this block defines phis,
 284   // removes the entry for `pred` and updates the indices of later entries.
 285   // This may introduce redundant phis if the new block has fewer
 286   // than two predecessors.
 287   void removePredecessor(MBasicBlock* pred);
 288
 289   // A version of removePredecessor which expects that phi operands to
 290   // |pred| have already been removed.
 291   void removePredecessorWithoutPhiOperands(MBasicBlock* pred, size_t predIndex);
 292
 293   // Resets all the dominator info so that it can be recomputed.
 294   void clearDominatorInfo();
 295
 296   // Sets a back edge. This places phi nodes and rewrites instructions within
 297   // the current loop as necessary.
 298   [[nodiscard]] bool setBackedge(MBasicBlock* block);
 299   [[nodiscard]] bool setBackedgeWasm(MBasicBlock* block, size_t paramCount);
 300
 301   // Resets a LOOP_HEADER block to a NORMAL block.  This is needed when
 302   // optimizations remove the backedge.
 303   void clearLoopHeader();
 304
 305   // Sets a block to a LOOP_HEADER block, with newBackedge as its backedge.
 306   // This is needed when optimizations remove the normal entry to a loop
 307   // with multiple entries.
 308   void setLoopHeader(MBasicBlock* newBackedge);
 309
 310   // Propagates backedge slots into phis operands of the loop header.
 311   [[nodiscard]] bool inheritPhisFromBackedge(MBasicBlock* backedge);
 312
 313   void insertBefore(MInstruction* at, MInstruction* ins);
 314   void insertAfter(MInstruction* at, MInstruction* ins);
 315
 316   void insertAtEnd(MInstruction* ins);
 317
 318   // Move an instruction. Movement may cross block boundaries.
 319   void moveBefore(MInstruction* at, MInstruction* ins);
 320
 321   enum IgnoreTop { IgnoreNone = 0, IgnoreRecover = 1 << 0 };
 322
 323   // Locate the top of the |block|, where it is safe to insert a new
 324   // instruction.
 325   MInstruction* safeInsertTop(MDefinition* ins = nullptr,
 326                               IgnoreTop ignore = IgnoreNone);
 327
 328   // Removes an instruction with the intention to discard it.
 329   void discard(MInstruction* ins);
 330   void discardLastIns();
 331   void discardAllInstructions();
 332   void discardAllInstructionsStartingAt(MInstructionIterator iter);
 333   void discardAllPhis();
 334   void discardAllResumePoints(bool discardEntry = true);
 335   void clear();
 336
 337   // Splits this block in two at a given instruction, inserting a new control
 338   // flow diamond with |ins| in the slow path, |fastpath| in the other, and
 339   // |condition| determining which path to take.
 340   bool wrapInstructionInFastpath(MInstruction* ins, MInstruction* fastpath,
 341                                  MInstruction* condition);
 342
 343   void moveOuterResumePointTo(MBasicBlock* dest);
 344
 345   // Move an instruction from this block to a block that has not yet been
 346   // terminated.
 347   void moveToNewBlock(MInstruction* ins, MBasicBlock* dst);
 348
 349   // Same as |void discard(MInstruction* ins)| but assuming that
 350   // all operands are already discarded.
 351   void discardIgnoreOperands(MInstruction* ins);
 352
 353   // Discards a phi instruction and updates predecessor successorWithPhis.
 354   void discardPhi(MPhi* phi);
 355
 356   // Some instruction which are guarding against some MIRType value, or
 357   // against a type expectation should be considered as removing a potenatial
 358   // branch where the guard does not hold.  We need to register such
 359   // instructions in order to do destructive optimizations correctly, such as
 360   // Range Analysis.
 361   void flagOperandsOfPrunedBranches(MInstruction* ins);
 362
 363   // Mark this block as having been removed from the graph.
 364   void markAsDead() {
 365     MOZ_ASSERT(kind_ != DEAD);
 366     kind_ = DEAD;
 367   }
 368
 369   ///////////////////////////////////////////////////////
 370   /////////// END GRAPH BUILDING INSTRUCTIONS ///////////
 371   ///////////////////////////////////////////////////////
 372
 373   MIRGraph& graph() { return graph_; }
 374   const CompileInfo& info() const { return info_; }
 375   jsbytecode* pc() const { return trackedSite_->pc(); }
 376   jsbytecode* entryPC() const { return entryResumePoint()->pc(); }
 377   uint32_t nslots() const { return slots_.length(); }
 378   uint32_t id() const { return id_; }
 379   uint32_t numPredecessors() const { return predecessors_.length(); }
 380
 381   bool branchHintingUnlikely() const {
 382     return branchHint_ == wasm::BranchHint::Unlikely;
 383   }
 384   bool branchHintingLikely() const {
 385     return branchHint_ == wasm::BranchHint::Likely;
 386   }
 387
 388   void setBranchHinting(wasm::BranchHint value) { branchHint_ = value; }
 389
 390   uint32_t domIndex() const {
 391     MOZ_ASSERT(!isDead());
 392     return domIndex_;
 393   }
 394   void setDomIndex(uint32_t d) { domIndex_ = d; }
 395
 396   MBasicBlock* getPredecessor(uint32_t i) const { return predecessors_[i]; }
 397   size_t indexForPredecessor(MBasicBlock* block) const {
 398     // This should only be called before critical edge splitting.
 399     MOZ_ASSERT(!block->successorWithPhis());
 400
 401     for (size_t i = 0; i < predecessors_.length(); i++) {
 402       if (predecessors_[i] == block) {
 403         return i;
 404       }
 405     }
 406     MOZ_CRASH();
 407   }
 408   bool hasAnyIns() const { return !instructions_.empty(); }
 409   bool hasLastIns() const {
 410     return hasAnyIns() && instructions_.rbegin()->isControlInstruction();
 411   }
 412   MControlInstruction* lastIns() const {
 413     MOZ_ASSERT(hasLastIns());
 414     return instructions_.rbegin()->toControlInstruction();
 415   }
 416   // Find or allocate an optimized out constant.
 417   MConstant* optimizedOutConstant(TempAllocator& alloc);
 418   MPhiIterator phisBegin() const { return phis_.begin(); }
 419   MPhiIterator phisBegin(MPhi* at) const { return phis_.begin(at); }
 420   MPhiIterator phisEnd() const { return phis_.end(); }
 421   bool phisEmpty() const { return phis_.empty(); }
 422 #ifdef DEBUG
 423   MResumePointIterator resumePointsBegin() const {
 424     return resumePoints_.begin();
 425   }
 426   MResumePointIterator resumePointsEnd() const { return resumePoints_.end(); }
 427   bool resumePointsEmpty() const { return resumePoints_.empty(); }
 428 #endif
 429   MInstructionIterator begin() { return instructions_.begin(); }
 430   MInstructionIterator begin(MInstruction* at) {
 431     MOZ_ASSERT(at->block() == this);
 432     return instructions_.begin(at);
 433   }
 434   MInstructionIterator end() { return instructions_.end(); }
 435   MInstructionReverseIterator rbegin() { return instructions_.rbegin(); }
 436   MInstructionReverseIterator rbegin(MInstruction* at) {
 437     MOZ_ASSERT(at->block() == this);
 438     return instructions_.rbegin(at);
 439   }
 440   MInstructionReverseIterator rend() { return instructions_.rend(); }
 441
 442   bool isLoopHeader() const { return kind_ == LOOP_HEADER; }
 443   bool isPendingLoopHeader() const { return kind_ == PENDING_LOOP_HEADER; }
 444
 445   bool hasUniqueBackedge() const {
 446     MOZ_ASSERT(isLoopHeader());
 447     MOZ_ASSERT(numPredecessors() >= 1);
 448     if (numPredecessors() == 1 || numPredecessors() == 2) {
 449       return true;
 450     }
 451     if (numPredecessors() == 3) {
 452       // fixup block added by NewFakeLoopPredecessor
 453       return getPredecessor(1)->numPredecessors() == 0;
 454     }
 455     return false;
 456   }
 457   MBasicBlock* backedge() const {
 458     MOZ_ASSERT(hasUniqueBackedge());
 459     return getPredecessor(numPredecessors() - 1);
 460   }
 461   MBasicBlock* loopHeaderOfBackedge() const {
 462     MOZ_ASSERT(isLoopBackedge());
 463     return getSuccessor(numSuccessors() - 1);
 464   }
 465   MBasicBlock* loopPredecessor() const {
 466     MOZ_ASSERT(isLoopHeader());
 467     return getPredecessor(0);
 468   }
 469   bool isLoopBackedge() const {
 470     if (!numSuccessors()) {
 471       return false;
 472     }
 473     MBasicBlock* lastSuccessor = getSuccessor(numSuccessors() - 1);
 474     return lastSuccessor->isLoopHeader() &&
 475            lastSuccessor->hasUniqueBackedge() &&
 476            lastSuccessor->backedge() == this;
 477   }
 478   bool isSplitEdge() const { return kind_ == SPLIT_EDGE; }
 479   bool isDead() const { return kind_ == DEAD; }
 480   bool isFakeLoopPred() const { return kind_ == FAKE_LOOP_PRED; }
 481
 482   uint32_t stackDepth() const { return stackPosition_; }
 483   bool isMarked() const { return mark_; }
 484   void mark() {
 485     MOZ_ASSERT(!mark_, "Marking already-marked block");
 486     markUnchecked();
 487   }
 488   void markUnchecked() { mark_ = true; }
 489   void unmark() {
 490     MOZ_ASSERT(mark_, "Unarking unmarked block");
 491     unmarkUnchecked();
 492   }
 493   void unmarkUnchecked() { mark_ = false; }
 494
 495   MBasicBlock* immediateDominator() const { return immediateDominator_; }
 496
 497   void setImmediateDominator(MBasicBlock* dom) { immediateDominator_ = dom; }
 498
 499   MTest* immediateDominatorBranch(BranchDirection* pdirection);
 500
 501   size_t numImmediatelyDominatedBlocks() const {
 502     return immediatelyDominated_.length();
 503   }
 504
 505   MBasicBlock* getImmediatelyDominatedBlock(size_t i) const {
 506     return immediatelyDominated_[i];
 507   }
 508
 509   MBasicBlock** immediatelyDominatedBlocksBegin() {
 510     return immediatelyDominated_.begin();
 511   }
 512
 513   MBasicBlock** immediatelyDominatedBlocksEnd() {
 514     return immediatelyDominated_.end();
 515   }
 516
 517   // Return the number of blocks dominated by this block. All blocks
 518   // dominate at least themselves, so this will always be non-zero.
 519   size_t numDominated() const {
 520     MOZ_ASSERT(numDominated_ != 0);
 521     return numDominated_;
 522   }
 523
 524   void addNumDominated(size_t n) { numDominated_ += n; }
 525
 526   // Add |child| to this block's immediately-dominated set.
 527   bool addImmediatelyDominatedBlock(MBasicBlock* child);
 528
 529   // Remove |child| from this block's immediately-dominated set.
 530   void removeImmediatelyDominatedBlock(MBasicBlock* child);
 531
 532   // This function retrieves the internal instruction associated with a
 533   // slot, and should not be used for normal stack operations. It is an
 534   // internal helper that is also used to enhance spew.
 535   MDefinition* getSlot(uint32_t index) {
 536     MOZ_ASSERT(index < stackPosition_);
 537     return slots_[index];
 538   }
 539
 540   MResumePoint* entryResumePoint() const { return entryResumePoint_; }
 541   void setEntryResumePoint(MResumePoint* rp) { entryResumePoint_ = rp; }
 542   void clearEntryResumePoint() {
 543     discardResumePoint(entryResumePoint_);
 544     entryResumePoint_ = nullptr;
 545   }
 546   MResumePoint* outerResumePoint() const { return outerResumePoint_; }
 547   void setOuterResumePoint(MResumePoint* outer) {
 548     MOZ_ASSERT(!outerResumePoint_);
 549     outerResumePoint_ = outer;
 550   }
 551   void clearOuterResumePoint() {
 552     discardResumePoint(outerResumePoint_);
 553     outerResumePoint_ = nullptr;
 554   }
 555   MResumePoint* callerResumePoint() const { return callerResumePoint_; }
 556   void setCallerResumePoint(MResumePoint* caller) {
 557     callerResumePoint_ = caller;
 558   }
 559
 560   LBlock* lir() const { return lir_; }
 561   void assignLir(LBlock* lir) {
 562     MOZ_ASSERT(!lir_);
 563     lir_ = lir;
 564   }
 565
 566   MBasicBlock* successorWithPhis() const { return successorWithPhis_; }
 567   uint32_t positionInPhiSuccessor() const {
 568     MOZ_ASSERT(successorWithPhis());
 569     return positionInPhiSuccessor_;
 570   }
 571   void setSuccessorWithPhis(MBasicBlock* successor, uint32_t id) {
 572     successorWithPhis_ = successor;
 573     positionInPhiSuccessor_ = id;
 574   }
 575   void clearSuccessorWithPhis() { successorWithPhis_ = nullptr; }
 576   size_t numSuccessors() const {
 577     MOZ_ASSERT(lastIns());
 578     return lastIns()->numSuccessors();
 579   }
 580   MBasicBlock* getSuccessor(size_t index) const {
 581     MOZ_ASSERT(lastIns());
 582     return lastIns()->getSuccessor(index);
 583   }
 584   MBasicBlock* getSingleSuccessor() const {
 585     MOZ_ASSERT(numSuccessors() == 1);
 586     return getSuccessor(0);
 587   }
 588   size_t getSuccessorIndex(MBasicBlock*) const;
 589   size_t getPredecessorIndex(MBasicBlock*) const;
 590
 591   void setLoopDepth(uint32_t loopDepth) { loopDepth_ = loopDepth; }
 592   uint32_t loopDepth() const { return loopDepth_; }
 593
 594   void dumpStack(GenericPrinter& out);
 595   void dumpStack();
 596
 597   void dump(GenericPrinter& out);
 598   void dump();
 599
 600   void updateTrackedSite(BytecodeSite* site) {
 601     MOZ_ASSERT(site->tree() == trackedSite_->tree());
 602     trackedSite_ = site;
 603   }
 604   BytecodeSite* trackedSite() const { return trackedSite_; }
 605   InlineScriptTree* trackedTree() const { return trackedSite_->tree(); }
 606
 607   // Find the previous resume point that would be used if this instruction
 608   // bails out.
 609   MResumePoint* activeResumePoint(MInstruction* ins);
 610
 611  private:
 612   MIRGraph& graph_;
 613   const CompileInfo& info_;  // Each block originates from a particular script.
 614   InlineList<MInstruction> instructions_;
 615   Vector<MBasicBlock*, 1, JitAllocPolicy> predecessors_;
 616   InlineList<MPhi> phis_;
 617   FixedList<MDefinition*> slots_;
 618   uint32_t stackPosition_;
 619   uint32_t id_;
 620   uint32_t domIndex_;  // Index in the dominator tree.
 621   uint32_t numDominated_;
 622   LBlock* lir_;
 623
 624   // Copy of a dominator block's outerResumePoint_ which holds the state of
 625   // caller frame at the time of the call. If not null, this implies that this
 626   // basic block corresponds to an inlined script.
 627   MResumePoint* callerResumePoint_;
 628
 629   // Resume point holding baseline-like frame for the PC corresponding to the
 630   // entry of this basic block.
 631   MResumePoint* entryResumePoint_;
 632
 633   // Resume point holding baseline-like frame for the PC corresponding to the
 634   // beginning of the call-site which is being inlined after this block.
 635   MResumePoint* outerResumePoint_;
 636
 637 #ifdef DEBUG
 638   // Unordered list used to verify that all the resume points which are
 639   // registered are correctly removed when a basic block is removed.
 640   InlineForwardList<MResumePoint> resumePoints_;
 641 #endif
 642
 643   MBasicBlock* successorWithPhis_;
 644   uint32_t positionInPhiSuccessor_;
 645   uint32_t loopDepth_;
 646   Kind kind_ : 8;
 647
 648   // Utility mark for traversal algorithms.
 649   bool mark_;
 650
 651   Vector<MBasicBlock*, 1, JitAllocPolicy> immediatelyDominated_;
 652   MBasicBlock* immediateDominator_;
 653
 654   // Track bailouts by storing the current pc in MIR instruction added at
 655   // this cycle. This is also used for tracking calls and optimizations when
 656   // profiling.
 657   BytecodeSite* trackedSite_;
 658 };
 659
 660 using MBasicBlockIterator = InlineListIterator<MBasicBlock>;
 661 using ReversePostorderIterator = InlineListIterator<MBasicBlock>;
 662 using PostorderIterator = InlineListReverseIterator<MBasicBlock>;
 663
 664 typedef Vector<MBasicBlock*, 1, JitAllocPolicy> MIRGraphReturns;
 665
 666 class MIRGraph {
 667   InlineList<MBasicBlock> blocks_;
 668   TempAllocator* alloc_;
 669   MIRGraphReturns* returnAccumulator_;
 670   uint32_t blockIdGen_;
 671   uint32_t idGen_;
 672   MBasicBlock* osrBlock_;
 673
 674   size_t numBlocks_;
 675   bool hasTryBlock_;
 676
 677   InlineList<MPhi> phiFreeList_;
 678   size_t phiFreeListLength_;
 679
 680  public:
 681   explicit MIRGraph(TempAllocator* alloc)
 682       : alloc_(alloc),
 683         returnAccumulator_(nullptr),
 684         blockIdGen_(0),
 685         idGen_(0),
 686         osrBlock_(nullptr),
 687         numBlocks_(0),
 688         hasTryBlock_(false),
 689         phiFreeListLength_(0) {}
 690
 691   TempAllocator& alloc() const { return *alloc_; }
 692
 693   void addBlock(MBasicBlock* block);
 694   void insertBlockAfter(MBasicBlock* at, MBasicBlock* block);
 695   void insertBlockBefore(MBasicBlock* at, MBasicBlock* block);
 696
 697   void unmarkBlocks();
 698
 699   void setReturnAccumulator(MIRGraphReturns* accum) {
 700     returnAccumulator_ = accum;
 701   }
 702   MIRGraphReturns* returnAccumulator() const { return returnAccumulator_; }
 703
 704   [[nodiscard]] bool addReturn(MBasicBlock* returnBlock) {
 705     if (!returnAccumulator_) {
 706       return true;
 707     }
 708
 709     return returnAccumulator_->append(returnBlock);
 710   }
 711
 712   MBasicBlock* entryBlock() { return *blocks_.begin(); }
 713   MBasicBlockIterator begin() { return blocks_.begin(); }
 714   MBasicBlockIterator begin(MBasicBlock* at) { return blocks_.begin(at); }
 715   MBasicBlockIterator end() { return blocks_.end(); }
 716   PostorderIterator poBegin() { return blocks_.rbegin(); }
 717   PostorderIterator poBegin(MBasicBlock* at) { return blocks_.rbegin(at); }
 718   PostorderIterator poEnd() { return blocks_.rend(); }
 719   ReversePostorderIterator rpoBegin() { return blocks_.begin(); }
 720   ReversePostorderIterator rpoBegin(MBasicBlock* at) {
 721     return blocks_.begin(at);
 722   }
 723   ReversePostorderIterator rpoEnd() { return blocks_.end(); }
 724   void removeBlock(MBasicBlock* block);
 725   void moveBlockToEnd(MBasicBlock* block) {
 726     blocks_.remove(block);
 727     MOZ_ASSERT_IF(!blocks_.empty(), block->id());
 728     blocks_.pushBack(block);
 729   }
 730   void moveBlockBefore(MBasicBlock* at, MBasicBlock* block) {
 731     MOZ_ASSERT(block->id());
 732     blocks_.remove(block);
 733     blocks_.insertBefore(at, block);
 734   }
 735   void moveBlockAfter(MBasicBlock* at, MBasicBlock* block) {
 736     MOZ_ASSERT(block->id());
 737     blocks_.remove(block);
 738     blocks_.insertAfter(at, block);
 739   }
 740   size_t numBlocks() const { return numBlocks_; }
 741   uint32_t numBlockIds() const { return blockIdGen_; }
 742   void allocDefinitionId(MDefinition* ins) { ins->setId(idGen_++); }
 743   uint32_t getNumInstructionIds() { return idGen_; }
 744   MResumePoint* entryResumePoint() { return entryBlock()->entryResumePoint(); }
 745
 746   void setOsrBlock(MBasicBlock* osrBlock) {
 747     MOZ_ASSERT(!osrBlock_);
 748     osrBlock_ = osrBlock;
 749   }
 750   MBasicBlock* osrBlock() const { return osrBlock_; }
 751
 752   MBasicBlock* osrPreHeaderBlock() const {
 753     return osrBlock() ? osrBlock()->getSingleSuccessor() : nullptr;
 754   }
 755
 756   bool hasTryBlock() const { return hasTryBlock_; }
 757   void setHasTryBlock() { hasTryBlock_ = true; }
 758
 759   void dump(GenericPrinter& out);
 760   void dump();
 761
 762   void addPhiToFreeList(MPhi* phi) {
 763     phiFreeList_.pushBack(phi);
 764     phiFreeListLength_++;
 765   }
 766   size_t phiFreeListLength() const { return phiFreeListLength_; }
 767   MPhi* takePhiFromFreeList() {
 768     MOZ_ASSERT(phiFreeListLength_ > 0);
 769     phiFreeListLength_--;
 770     return phiFreeList_.popBack();
 771   }
 772
 773   void removeFakeLoopPredecessors();
 774
 775 #ifdef DEBUG
 776   // Dominators can't be built after we remove fake loop predecessors.
 777  private:
 778   bool canBuildDominators_ = true;
 779
 780  public:
 781   bool canBuildDominators() const { return canBuildDominators_; }
 782 #endif
 783 };
 784
 785 class MDefinitionIterator {
 786   friend class MBasicBlock;
 787   friend class MNodeIterator;
 788
 789  private:
 790   MBasicBlock* block_;
 791   MPhiIterator phiIter_;
 792   MInstructionIterator iter_;
 793
 794   bool atPhi() const { return phiIter_ != block_->phisEnd(); }
 795
 796   MDefinition* getIns() {
 797     if (atPhi()) {
 798       return *phiIter_;
 799     }
 800     return *iter_;
 801   }
 802
 803   bool more() const { return atPhi() || (*iter_) != block_->lastIns(); }
 804
 805  public:
 806   explicit MDefinitionIterator(MBasicBlock* block)
 807       : block_(block), phiIter_(block->phisBegin()), iter_(block->begin()) {}
 808
 809   MDefinitionIterator operator++() {
 810     MOZ_ASSERT(more());
 811     if (atPhi()) {
 812       ++phiIter_;
 813     } else {
 814       ++iter_;
 815     }
 816     return *this;
 817   }
 818
 819   MDefinitionIterator operator++(int) {
 820     MDefinitionIterator old(*this);
 821     operator++();
 822     return old;
 823   }
 824
 825   explicit operator bool() const { return more(); }
 826
 827   MDefinition* operator*() { return getIns(); }
 828
 829   MDefinition* operator->() { return getIns(); }
 830 };
 831
 832 // Iterates on all resume points, phis, and instructions of a MBasicBlock.
 833 // Resume points are visited as long as they have not been discarded.
 834 class MNodeIterator {
 835  private:
 836   // If this is non-null, the resume point that we will visit next (unless
 837   // it has been discarded). Initialized to the entry resume point.
 838   // Otherwise, resume point of the most recently visited instruction.
 839   MResumePoint* resumePoint_;
 840
 841   mozilla::DebugOnly<MInstruction*> lastInstruction_ = nullptr;
 842
 843   // Definition iterator which is one step ahead when visiting resume points.
 844   // This is in order to avoid incrementing the iterator while it is settled
 845   // on a discarded instruction.
 846   MDefinitionIterator defIter_;
 847
 848   MBasicBlock* block() const { return defIter_.block_; }
 849
 850   bool atResumePoint() const {
 851     MOZ_ASSERT_IF(lastInstruction_ && !lastInstruction_->isDiscarded(),
 852                   lastInstruction_->resumePoint() == resumePoint_);
 853     return resumePoint_ && !resumePoint_->isDiscarded();
 854   }
 855
 856   MNode* getNode() {
 857     if (atResumePoint()) {
 858       return resumePoint_;
 859     }
 860     return *defIter_;
 861   }
 862
 863   void next() {
 864     if (!atResumePoint()) {
 865       if (defIter_->isInstruction()) {
 866         resumePoint_ = defIter_->toInstruction()->resumePoint();
 867         lastInstruction_ = defIter_->toInstruction();
 868       }
 869       defIter_++;
 870     } else {
 871       resumePoint_ = nullptr;
 872       lastInstruction_ = nullptr;
 873     }
 874   }
 875
 876   bool more() const { return defIter_ || atResumePoint(); }
 877
 878  public:
 879   explicit MNodeIterator(MBasicBlock* block)
 880       : resumePoint_(block->entryResumePoint()), defIter_(block) {
 881     MOZ_ASSERT(bool(block->entryResumePoint()) == atResumePoint());
 882   }
 883
 884   MNodeIterator operator++(int) {
 885     MNodeIterator old(*this);
 886     if (more()) {
 887       next();
 888     }
 889     return old;
 890   }
 891
 892   explicit operator bool() const { return more(); }
 893
 894   MNode* operator*() { return getNode(); }
 895
 896   MNode* operator->() { return getNode(); }
 897 };
 898
 899 void MBasicBlock::add(MInstruction* ins) {
 900   MOZ_ASSERT(!hasLastIns());
 901   ins->setInstructionBlock(this, trackedSite_);
 902   graph().allocDefinitionId(ins);
 903   instructions_.pushBack(ins);
 904 }
 905
 906 }  // namespace jit
 907 }  // namespace js
 908
 909 #endif /* jit_MIRGraph_h */