summaryrefslogtreecommitdiffstats
path: root/js/src/jit/MIRGraph.h
blob: 18c0bf68a489b822d318056c4e4a9733cdbe8b5d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef jit_MIRGraph_h
#define jit_MIRGraph_h

// This file declares the data structures used to build a control-flow graph
// containing MIR.

#include "jit/CompileInfo.h"
#include "jit/FixedList.h"
#include "jit/InlineScriptTree.h"
#include "jit/JitAllocPolicy.h"
#include "jit/MIR.h"

namespace js {
namespace jit {

class MBasicBlock;
class MIRGraph;
class MStart;

class MDefinitionIterator;

using MInstructionIterator = InlineListIterator<MInstruction>;
using MInstructionReverseIterator = InlineListReverseIterator<MInstruction>;
using MPhiIterator = InlineListIterator<MPhi>;

#ifdef DEBUG
typedef InlineForwardListIterator<MResumePoint> MResumePointIterator;
#endif

class LBlock;

class MBasicBlock : public TempObject, public InlineListNode<MBasicBlock> {
 public:
  enum Kind {
    NORMAL,
    PENDING_LOOP_HEADER,
    LOOP_HEADER,
    SPLIT_EDGE,
    FAKE_LOOP_PRED,
    INTERNAL,
    DEAD
  };

 private:
  MBasicBlock(MIRGraph& graph, const CompileInfo& info, BytecodeSite* site,
              Kind kind);
  [[nodiscard]] bool init();
  void copySlots(MBasicBlock* from);
  [[nodiscard]] bool inherit(TempAllocator& alloc, size_t stackDepth,
                             MBasicBlock* maybePred, uint32_t popped);

  // This block cannot be reached by any means.
  bool unreachable_ = false;

  // This block will unconditionally bail out.
  bool alwaysBails_ = false;

  // Pushes a copy of a local variable or argument.
  void pushVariable(uint32_t slot) { push(slots_[slot]); }

  // Sets a variable slot to the top of the stack, correctly creating copies
  // as needed.
  void setVariable(uint32_t slot) {
    MOZ_ASSERT(stackPosition_ > info_.firstStackSlot());
    setSlot(slot, slots_[stackPosition_ - 1]);
  }

  enum ReferencesType {
    RefType_None = 0,

    // Assert that the instruction is unused.
    RefType_AssertNoUses = 1 << 0,

    // Discard the operands of the resume point / instructions if the
    // following flag are given too.
    RefType_DiscardOperands = 1 << 1,
    RefType_DiscardResumePoint = 1 << 2,
    RefType_DiscardInstruction = 1 << 3,

    // Discard operands of the instruction and its resume point.
    RefType_DefaultNoAssert = RefType_DiscardOperands |
                              RefType_DiscardResumePoint |
                              RefType_DiscardInstruction,

    // Discard everything and assert that the instruction is not used.
    RefType_Default = RefType_AssertNoUses | RefType_DefaultNoAssert,

    // Discard resume point operands only, without discarding the operands
    // of the current instruction.  Asserts that the instruction is unused.
    RefType_IgnoreOperands = RefType_AssertNoUses | RefType_DiscardOperands |
                             RefType_DiscardResumePoint
  };

  void discardResumePoint(MResumePoint* rp,
                          ReferencesType refType = RefType_Default);
  void removeResumePoint(MResumePoint* rp);

  // Remove all references to an instruction such that it can be removed from
  // the list of instruction, without keeping any dangling pointer to it. This
  // includes the operands of the instruction, and the resume point if
  // present.
  void prepareForDiscard(MInstruction* ins,
                         ReferencesType refType = RefType_Default);

 public:
  ///////////////////////////////////////////////////////
  ////////// BEGIN GRAPH BUILDING INSTRUCTIONS //////////
  ///////////////////////////////////////////////////////

  // Creates a new basic block for a MIR generator. If |pred| is not nullptr,
  // its slots and stack depth are initialized from |pred|.
  static MBasicBlock* New(MIRGraph& graph, size_t stackDepth,
                          const CompileInfo& info, MBasicBlock* maybePred,
                          BytecodeSite* site, Kind kind);
  static MBasicBlock* New(MIRGraph& graph, const CompileInfo& info,
                          MBasicBlock* pred, Kind kind);
  static MBasicBlock* NewPopN(MIRGraph& graph, const CompileInfo& info,
                              MBasicBlock* pred, BytecodeSite* site, Kind kind,
                              uint32_t popn);
  static MBasicBlock* NewPendingLoopHeader(MIRGraph& graph,
                                           const CompileInfo& info,
                                           MBasicBlock* pred,
                                           BytecodeSite* site);
  static MBasicBlock* NewSplitEdge(MIRGraph& graph, MBasicBlock* pred,
                                   size_t predEdgeIdx, MBasicBlock* succ);
  static MBasicBlock* NewFakeLoopPredecessor(MIRGraph& graph,
                                             MBasicBlock* header);

  // Create a new basic block for internal control flow not present in the
  // original CFG.
  static MBasicBlock* NewInternal(MIRGraph& graph, MBasicBlock* orig,
                                  MResumePoint* activeResumePoint);

  bool dominates(const MBasicBlock* other) const {
    return other->domIndex() - domIndex() < numDominated();
  }

  void setId(uint32_t id) { id_ = id; }

  // Mark this block (and only this block) as unreachable.
  void setUnreachable() {
    MOZ_ASSERT(!unreachable_);
    setUnreachableUnchecked();
  }
  void setUnreachableUnchecked() { unreachable_ = true; }
  bool unreachable() const { return unreachable_; }

  void setAlwaysBails() { alwaysBails_ = true; }
  bool alwaysBails() const { return alwaysBails_; }

  // Move the definition to the top of the stack.
  void pick(int32_t depth);

  // Move the top of the stack definition under the depth-th stack value.
  void unpick(int32_t depth);

  // Exchange 2 stack slots at the defined depth
  void swapAt(int32_t depth);

  // Note: most of the methods below are hot. Do not un-inline them without
  // measuring the impact.

  // Gets the instruction associated with various slot types.
  MDefinition* peek(int32_t depth) {
    MOZ_ASSERT(depth < 0);
    MOZ_ASSERT(stackPosition_ + depth >= info_.firstStackSlot());
    return peekUnchecked(depth);
  }

  MDefinition* peekUnchecked(int32_t depth) {
    MOZ_ASSERT(depth < 0);
    return getSlot(stackPosition_ + depth);
  }

  MDefinition* environmentChain();
  MDefinition* argumentsObject();

  // Increase the number of slots available
  [[nodiscard]] bool increaseSlots(size_t num);
  [[nodiscard]] bool ensureHasSlots(size_t num);

  // Initializes a slot value; must not be called for normal stack
  // operations, as it will not create new SSA names for copies.
  void initSlot(uint32_t slot, MDefinition* ins) {
    slots_[slot] = ins;
    if (entryResumePoint()) {
      entryResumePoint()->initOperand(slot, ins);
    }
  }

  // Sets the instruction associated with various slot types. The
  // instruction must lie at the top of the stack.
  void setLocal(uint32_t local) { setVariable(info_.localSlot(local)); }
  void setArg(uint32_t arg) { setVariable(info_.argSlot(arg)); }
  void setSlot(uint32_t slot, MDefinition* ins) { slots_[slot] = ins; }

  // Tracks an instruction as being pushed onto the operand stack.
  void push(MDefinition* ins) {
    MOZ_ASSERT(stackPosition_ < nslots());
    slots_[stackPosition_++] = ins;
  }
  void pushArg(uint32_t arg) { pushVariable(info_.argSlot(arg)); }
  void pushArgUnchecked(uint32_t arg) {
    pushVariable(info_.argSlotUnchecked(arg));
  }
  void pushLocal(uint32_t local) { pushVariable(info_.localSlot(local)); }
  void pushSlot(uint32_t slot) { pushVariable(slot); }
  void setEnvironmentChain(MDefinition* ins);
  void setArgumentsObject(MDefinition* ins);

  // Returns the top of the stack, then decrements the virtual stack pointer.
  MDefinition* pop() {
    MOZ_ASSERT(stackPosition_ > info_.firstStackSlot());
    return slots_[--stackPosition_];
  }
  void popn(uint32_t n) {
    MOZ_ASSERT(stackPosition_ - n >= info_.firstStackSlot());
    MOZ_ASSERT(stackPosition_ >= stackPosition_ - n);
    stackPosition_ -= n;
  }

  // Adds an instruction to this block's instruction list.
  inline void add(MInstruction* ins);

  // Marks the last instruction of the block; no further instructions
  // can be added.
  void end(MControlInstruction* ins) {
    MOZ_ASSERT(!hasLastIns());  // Existing control instructions should be
                                // removed first.
    MOZ_ASSERT(ins);
    add(ins);
  }

  // Adds a phi instruction, but does not set successorWithPhis.
  void addPhi(MPhi* phi);

  // Adds a resume point to this block.
  void addResumePoint(MResumePoint* resume) {
#ifdef DEBUG
    resumePoints_.pushFront(resume);
#endif
  }

  // Discard pre-allocated resume point.
  void discardPreAllocatedResumePoint(MResumePoint* resume) {
    MOZ_ASSERT(!resume->instruction());
    discardResumePoint(resume);
  }

  // Adds a predecessor. Every predecessor must have the same exit stack
  // depth as the entry state to this block. Adding a predecessor
  // automatically creates phi nodes and rewrites uses as needed.
  [[nodiscard]] bool addPredecessor(TempAllocator& alloc, MBasicBlock* pred);
  [[nodiscard]] bool addPredecessorPopN(TempAllocator& alloc, MBasicBlock* pred,
                                        uint32_t popped);

  // Add a predecessor which won't introduce any new phis to this block.
  // This may be called after the contents of this block have been built.
  [[nodiscard]] bool addPredecessorSameInputsAs(MBasicBlock* pred,
                                                MBasicBlock* existingPred);

  // Stranger utilities used for inlining.
  [[nodiscard]] bool addPredecessorWithoutPhis(MBasicBlock* pred);
  void inheritSlots(MBasicBlock* parent);
  [[nodiscard]] bool initEntrySlots(TempAllocator& alloc);

  // Replaces an edge for a given block with a new block. This is
  // used for critical edge splitting.
  //
  // Note: If successorWithPhis is set, you must not be replacing it.
  void replacePredecessor(MBasicBlock* old, MBasicBlock* split);
  void replaceSuccessor(size_t pos, MBasicBlock* split);

  // Removes `pred` from the predecessor list. If this block defines phis,
  // removes the entry for `pred` and updates the indices of later entries.
  // This may introduce redundant phis if the new block has fewer
  // than two predecessors.
  void removePredecessor(MBasicBlock* pred);

  // A version of removePredecessor which expects that phi operands to
  // |pred| have already been removed.
  void removePredecessorWithoutPhiOperands(MBasicBlock* pred, size_t predIndex);

  // Resets all the dominator info so that it can be recomputed.
  void clearDominatorInfo();

  // Sets a back edge. This places phi nodes and rewrites instructions within
  // the current loop as necessary.
  [[nodiscard]] bool setBackedge(MBasicBlock* block);
  [[nodiscard]] bool setBackedgeWasm(MBasicBlock* block, size_t paramCount);

  // Resets a LOOP_HEADER block to a NORMAL block.  This is needed when
  // optimizations remove the backedge.
  void clearLoopHeader();

  // Sets a block to a LOOP_HEADER block, with newBackedge as its backedge.
  // This is needed when optimizations remove the normal entry to a loop
  // with multiple entries.
  void setLoopHeader(MBasicBlock* newBackedge);

  // Propagates backedge slots into phis operands of the loop header.
  [[nodiscard]] bool inheritPhisFromBackedge(MBasicBlock* backedge);

  void insertBefore(MInstruction* at, MInstruction* ins);
  void insertAfter(MInstruction* at, MInstruction* ins);

  void insertAtEnd(MInstruction* ins);

  // Move an instruction. Movement may cross block boundaries.
  void moveBefore(MInstruction* at, MInstruction* ins);

  enum IgnoreTop { IgnoreNone = 0, IgnoreRecover = 1 << 0 };

  // Locate the top of the |block|, where it is safe to insert a new
  // instruction.
  MInstruction* safeInsertTop(MDefinition* ins = nullptr,
                              IgnoreTop ignore = IgnoreNone);

  // Removes an instruction with the intention to discard it.
  void discard(MInstruction* ins);
  void discardLastIns();
  void discardAllInstructions();
  void discardAllInstructionsStartingAt(MInstructionIterator iter);
  void discardAllPhis();
  void discardAllResumePoints(bool discardEntry = true);
  void clear();

  // Splits this block in two at a given instruction, inserting a new control
  // flow diamond with |ins| in the slow path, |fastpath| in the other, and
  // |condition| determining which path to take.
  bool wrapInstructionInFastpath(MInstruction* ins, MInstruction* fastpath,
                                 MInstruction* condition);

  void moveOuterResumePointTo(MBasicBlock* dest);

  // Move an instruction from this block to a block that has not yet been
  // terminated.
  void moveToNewBlock(MInstruction* ins, MBasicBlock* dst);

  // Same as |void discard(MInstruction* ins)| but assuming that
  // all operands are already discarded.
  void discardIgnoreOperands(MInstruction* ins);

  // Discards a phi instruction and updates predecessor successorWithPhis.
  void discardPhi(MPhi* phi);

  // Some instruction which are guarding against some MIRType value, or
  // against a type expectation should be considered as removing a potenatial
  // branch where the guard does not hold.  We need to register such
  // instructions in order to do destructive optimizations correctly, such as
  // Range Analysis.
  void flagOperandsOfPrunedBranches(MInstruction* ins);

  // Mark this block as having been removed from the graph.
  void markAsDead() {
    MOZ_ASSERT(kind_ != DEAD);
    kind_ = DEAD;
  }

  ///////////////////////////////////////////////////////
  /////////// END GRAPH BUILDING INSTRUCTIONS ///////////
  ///////////////////////////////////////////////////////

  MIRGraph& graph() { return graph_; }
  const CompileInfo& info() const { return info_; }
  jsbytecode* pc() const { return trackedSite_->pc(); }
  jsbytecode* entryPC() const { return entryResumePoint()->pc(); }
  uint32_t nslots() const { return slots_.length(); }
  uint32_t id() const { return id_; }
  uint32_t numPredecessors() const { return predecessors_.length(); }

  uint32_t domIndex() const {
    MOZ_ASSERT(!isDead());
    return domIndex_;
  }
  void setDomIndex(uint32_t d) { domIndex_ = d; }

  MBasicBlock* getPredecessor(uint32_t i) const { return predecessors_[i]; }
  size_t indexForPredecessor(MBasicBlock* block) const {
    // This should only be called before critical edge splitting.
    MOZ_ASSERT(!block->successorWithPhis());

    for (size_t i = 0; i < predecessors_.length(); i++) {
      if (predecessors_[i] == block) {
        return i;
      }
    }
    MOZ_CRASH();
  }
  bool hasAnyIns() const { return !instructions_.empty(); }
  bool hasLastIns() const {
    return hasAnyIns() && instructions_.rbegin()->isControlInstruction();
  }
  MControlInstruction* lastIns() const {
    MOZ_ASSERT(hasLastIns());
    return instructions_.rbegin()->toControlInstruction();
  }
  // Find or allocate an optimized out constant.
  MConstant* optimizedOutConstant(TempAllocator& alloc);
  MPhiIterator phisBegin() const { return phis_.begin(); }
  MPhiIterator phisBegin(MPhi* at) const { return phis_.begin(at); }
  MPhiIterator phisEnd() const { return phis_.end(); }
  bool phisEmpty() const { return phis_.empty(); }
#ifdef DEBUG
  MResumePointIterator resumePointsBegin() const {
    return resumePoints_.begin();
  }
  MResumePointIterator resumePointsEnd() const { return resumePoints_.end(); }
  bool resumePointsEmpty() const { return resumePoints_.empty(); }
#endif
  MInstructionIterator begin() { return instructions_.begin(); }
  MInstructionIterator begin(MInstruction* at) {
    MOZ_ASSERT(at->block() == this);
    return instructions_.begin(at);
  }
  MInstructionIterator end() { return instructions_.end(); }
  MInstructionReverseIterator rbegin() { return instructions_.rbegin(); }
  MInstructionReverseIterator rbegin(MInstruction* at) {
    MOZ_ASSERT(at->block() == this);
    return instructions_.rbegin(at);
  }
  MInstructionReverseIterator rend() { return instructions_.rend(); }

  bool isLoopHeader() const { return kind_ == LOOP_HEADER; }
  bool isPendingLoopHeader() const { return kind_ == PENDING_LOOP_HEADER; }

  bool hasUniqueBackedge() const {
    MOZ_ASSERT(isLoopHeader());
    MOZ_ASSERT(numPredecessors() >= 1);
    if (numPredecessors() == 1 || numPredecessors() == 2) {
      return true;
    }
    if (numPredecessors() == 3) {
      // fixup block added by NewFakeLoopPredecessor
      return getPredecessor(1)->numPredecessors() == 0;
    }
    return false;
  }
  MBasicBlock* backedge() const {
    MOZ_ASSERT(hasUniqueBackedge());
    return getPredecessor(numPredecessors() - 1);
  }
  MBasicBlock* loopHeaderOfBackedge() const {
    MOZ_ASSERT(isLoopBackedge());
    return getSuccessor(numSuccessors() - 1);
  }
  MBasicBlock* loopPredecessor() const {
    MOZ_ASSERT(isLoopHeader());
    return getPredecessor(0);
  }
  bool isLoopBackedge() const {
    if (!numSuccessors()) {
      return false;
    }
    MBasicBlock* lastSuccessor = getSuccessor(numSuccessors() - 1);
    return lastSuccessor->isLoopHeader() &&
           lastSuccessor->hasUniqueBackedge() &&
           lastSuccessor->backedge() == this;
  }
  bool isSplitEdge() const { return kind_ == SPLIT_EDGE; }
  bool isDead() const { return kind_ == DEAD; }
  bool isFakeLoopPred() const { return kind_ == FAKE_LOOP_PRED; }

  uint32_t stackDepth() const { return stackPosition_; }
  bool isMarked() const { return mark_; }
  void mark() {
    MOZ_ASSERT(!mark_, "Marking already-marked block");
    markUnchecked();
  }
  void markUnchecked() { mark_ = true; }
  void unmark() {
    MOZ_ASSERT(mark_, "Unarking unmarked block");
    unmarkUnchecked();
  }
  void unmarkUnchecked() { mark_ = false; }

  MBasicBlock* immediateDominator() const { return immediateDominator_; }

  void setImmediateDominator(MBasicBlock* dom) { immediateDominator_ = dom; }

  MTest* immediateDominatorBranch(BranchDirection* pdirection);

  size_t numImmediatelyDominatedBlocks() const {
    return immediatelyDominated_.length();
  }

  MBasicBlock* getImmediatelyDominatedBlock(size_t i) const {
    return immediatelyDominated_[i];
  }

  MBasicBlock** immediatelyDominatedBlocksBegin() {
    return immediatelyDominated_.begin();
  }

  MBasicBlock** immediatelyDominatedBlocksEnd() {
    return immediatelyDominated_.end();
  }

  // Return the number of blocks dominated by this block. All blocks
  // dominate at least themselves, so this will always be non-zero.
  size_t numDominated() const {
    MOZ_ASSERT(numDominated_ != 0);
    return numDominated_;
  }

  void addNumDominated(size_t n) { numDominated_ += n; }

  // Add |child| to this block's immediately-dominated set.
  bool addImmediatelyDominatedBlock(MBasicBlock* child);

  // Remove |child| from this block's immediately-dominated set.
  void removeImmediatelyDominatedBlock(MBasicBlock* child);

  // This function retrieves the internal instruction associated with a
  // slot, and should not be used for normal stack operations. It is an
  // internal helper that is also used to enhance spew.
  MDefinition* getSlot(uint32_t index) {
    MOZ_ASSERT(index < stackPosition_);
    return slots_[index];
  }

  MResumePoint* entryResumePoint() const { return entryResumePoint_; }
  void setEntryResumePoint(MResumePoint* rp) { entryResumePoint_ = rp; }
  void clearEntryResumePoint() {
    discardResumePoint(entryResumePoint_);
    entryResumePoint_ = nullptr;
  }
  MResumePoint* outerResumePoint() const { return outerResumePoint_; }
  void setOuterResumePoint(MResumePoint* outer) {
    MOZ_ASSERT(!outerResumePoint_);
    outerResumePoint_ = outer;
  }
  void clearOuterResumePoint() {
    discardResumePoint(outerResumePoint_);
    outerResumePoint_ = nullptr;
  }
  MResumePoint* callerResumePoint() const { return callerResumePoint_; }
  void setCallerResumePoint(MResumePoint* caller) {
    callerResumePoint_ = caller;
  }

  LBlock* lir() const { return lir_; }
  void assignLir(LBlock* lir) {
    MOZ_ASSERT(!lir_);
    lir_ = lir;
  }

  MBasicBlock* successorWithPhis() const { return successorWithPhis_; }
  uint32_t positionInPhiSuccessor() const {
    MOZ_ASSERT(successorWithPhis());
    return positionInPhiSuccessor_;
  }
  void setSuccessorWithPhis(MBasicBlock* successor, uint32_t id) {
    successorWithPhis_ = successor;
    positionInPhiSuccessor_ = id;
  }
  void clearSuccessorWithPhis() { successorWithPhis_ = nullptr; }
  size_t numSuccessors() const {
    MOZ_ASSERT(lastIns());
    return lastIns()->numSuccessors();
  }
  MBasicBlock* getSuccessor(size_t index) const {
    MOZ_ASSERT(lastIns());
    return lastIns()->getSuccessor(index);
  }
  MBasicBlock* getSingleSuccessor() const {
    MOZ_ASSERT(numSuccessors() == 1);
    return getSuccessor(0);
  }
  size_t getSuccessorIndex(MBasicBlock*) const;
  size_t getPredecessorIndex(MBasicBlock*) const;

  void setLoopDepth(uint32_t loopDepth) { loopDepth_ = loopDepth; }
  uint32_t loopDepth() const { return loopDepth_; }

  void dumpStack(GenericPrinter& out);
  void dumpStack();

  void dump(GenericPrinter& out);
  void dump();

  void updateTrackedSite(BytecodeSite* site) {
    MOZ_ASSERT(site->tree() == trackedSite_->tree());
    trackedSite_ = site;
  }
  BytecodeSite* trackedSite() const { return trackedSite_; }
  InlineScriptTree* trackedTree() const { return trackedSite_->tree(); }

  // Find the previous resume point that would be used if this instruction
  // bails out.
  MResumePoint* activeResumePoint(MInstruction* ins);

 private:
  MIRGraph& graph_;
  const CompileInfo& info_;  // Each block originates from a particular script.
  InlineList<MInstruction> instructions_;
  Vector<MBasicBlock*, 1, JitAllocPolicy> predecessors_;
  InlineList<MPhi> phis_;
  FixedList<MDefinition*> slots_;
  uint32_t stackPosition_;
  uint32_t id_;
  uint32_t domIndex_;  // Index in the dominator tree.
  uint32_t numDominated_;
  LBlock* lir_;

  // Copy of a dominator block's outerResumePoint_ which holds the state of
  // caller frame at the time of the call. If not null, this implies that this
  // basic block corresponds to an inlined script.
  MResumePoint* callerResumePoint_;

  // Resume point holding baseline-like frame for the PC corresponding to the
  // entry of this basic block.
  MResumePoint* entryResumePoint_;

  // Resume point holding baseline-like frame for the PC corresponding to the
  // beginning of the call-site which is being inlined after this block.
  MResumePoint* outerResumePoint_;

#ifdef DEBUG
  // Unordered list used to verify that all the resume points which are
  // registered are correctly removed when a basic block is removed.
  InlineForwardList<MResumePoint> resumePoints_;
#endif

  MBasicBlock* successorWithPhis_;
  uint32_t positionInPhiSuccessor_;
  uint32_t loopDepth_;
  Kind kind_ : 8;

  // Utility mark for traversal algorithms.
  bool mark_;

  Vector<MBasicBlock*, 1, JitAllocPolicy> immediatelyDominated_;
  MBasicBlock* immediateDominator_;

  // Track bailouts by storing the current pc in MIR instruction added at
  // this cycle. This is also used for tracking calls and optimizations when
  // profiling.
  BytecodeSite* trackedSite_;
};

using MBasicBlockIterator = InlineListIterator<MBasicBlock>;
using ReversePostorderIterator = InlineListIterator<MBasicBlock>;
using PostorderIterator = InlineListReverseIterator<MBasicBlock>;

typedef Vector<MBasicBlock*, 1, JitAllocPolicy> MIRGraphReturns;

class MIRGraph {
  InlineList<MBasicBlock> blocks_;
  TempAllocator* alloc_;
  MIRGraphReturns* returnAccumulator_;
  uint32_t blockIdGen_;
  uint32_t idGen_;
  MBasicBlock* osrBlock_;

  size_t numBlocks_;
  bool hasTryBlock_;

  InlineList<MPhi> phiFreeList_;
  size_t phiFreeListLength_;

 public:
  explicit MIRGraph(TempAllocator* alloc)
      : alloc_(alloc),
        returnAccumulator_(nullptr),
        blockIdGen_(0),
        idGen_(0),
        osrBlock_(nullptr),
        numBlocks_(0),
        hasTryBlock_(false),
        phiFreeListLength_(0) {}

  TempAllocator& alloc() const { return *alloc_; }

  void addBlock(MBasicBlock* block);
  void insertBlockAfter(MBasicBlock* at, MBasicBlock* block);
  void insertBlockBefore(MBasicBlock* at, MBasicBlock* block);

  void unmarkBlocks();

  void setReturnAccumulator(MIRGraphReturns* accum) {
    returnAccumulator_ = accum;
  }
  MIRGraphReturns* returnAccumulator() const { return returnAccumulator_; }

  [[nodiscard]] bool addReturn(MBasicBlock* returnBlock) {
    if (!returnAccumulator_) {
      return true;
    }

    return returnAccumulator_->append(returnBlock);
  }

  MBasicBlock* entryBlock() { return *blocks_.begin(); }
  MBasicBlockIterator begin() { return blocks_.begin(); }
  MBasicBlockIterator begin(MBasicBlock* at) { return blocks_.begin(at); }
  MBasicBlockIterator end() { return blocks_.end(); }
  PostorderIterator poBegin() { return blocks_.rbegin(); }
  PostorderIterator poBegin(MBasicBlock* at) { return blocks_.rbegin(at); }
  PostorderIterator poEnd() { return blocks_.rend(); }
  ReversePostorderIterator rpoBegin() { return blocks_.begin(); }
  ReversePostorderIterator rpoBegin(MBasicBlock* at) {
    return blocks_.begin(at);
  }
  ReversePostorderIterator rpoEnd() { return blocks_.end(); }
  void removeBlock(MBasicBlock* block);
  void moveBlockToEnd(MBasicBlock* block) {
    blocks_.remove(block);
    MOZ_ASSERT_IF(!blocks_.empty(), block->id());
    blocks_.pushBack(block);
  }
  void moveBlockBefore(MBasicBlock* at, MBasicBlock* block) {
    MOZ_ASSERT(block->id());
    blocks_.remove(block);
    blocks_.insertBefore(at, block);
  }
  void moveBlockAfter(MBasicBlock* at, MBasicBlock* block) {
    MOZ_ASSERT(block->id());
    blocks_.remove(block);
    blocks_.insertAfter(at, block);
  }
  size_t numBlocks() const { return numBlocks_; }
  uint32_t numBlockIds() const { return blockIdGen_; }
  void allocDefinitionId(MDefinition* ins) { ins->setId(idGen_++); }
  uint32_t getNumInstructionIds() { return idGen_; }
  MResumePoint* entryResumePoint() { return entryBlock()->entryResumePoint(); }

  void setOsrBlock(MBasicBlock* osrBlock) {
    MOZ_ASSERT(!osrBlock_);
    osrBlock_ = osrBlock;
  }
  MBasicBlock* osrBlock() const { return osrBlock_; }

  MBasicBlock* osrPreHeaderBlock() const {
    return osrBlock() ? osrBlock()->getSingleSuccessor() : nullptr;
  }

  bool hasTryBlock() const { return hasTryBlock_; }
  void setHasTryBlock() { hasTryBlock_ = true; }

  void dump(GenericPrinter& out);
  void dump();

  void addPhiToFreeList(MPhi* phi) {
    phiFreeList_.pushBack(phi);
    phiFreeListLength_++;
  }
  size_t phiFreeListLength() const { return phiFreeListLength_; }
  MPhi* takePhiFromFreeList() {
    MOZ_ASSERT(phiFreeListLength_ > 0);
    phiFreeListLength_--;
    return phiFreeList_.popBack();
  }

  void removeFakeLoopPredecessors();

#ifdef DEBUG
  // Dominators can't be built after we remove fake loop predecessors.
 private:
  bool canBuildDominators_ = true;

 public:
  bool canBuildDominators() const { return canBuildDominators_; }
#endif
};

class MDefinitionIterator {
  friend class MBasicBlock;
  friend class MNodeIterator;

 private:
  MBasicBlock* block_;
  MPhiIterator phiIter_;
  MInstructionIterator iter_;

  bool atPhi() const { return phiIter_ != block_->phisEnd(); }

  MDefinition* getIns() {
    if (atPhi()) {
      return *phiIter_;
    }
    return *iter_;
  }

  bool more() const { return atPhi() || (*iter_) != block_->lastIns(); }

 public:
  explicit MDefinitionIterator(MBasicBlock* block)
      : block_(block), phiIter_(block->phisBegin()), iter_(block->begin()) {}

  MDefinitionIterator operator++() {
    MOZ_ASSERT(more());
    if (atPhi()) {
      ++phiIter_;
    } else {
      ++iter_;
    }
    return *this;
  }

  MDefinitionIterator operator++(int) {
    MDefinitionIterator old(*this);
    operator++();
    return old;
  }

  explicit operator bool() const { return more(); }

  MDefinition* operator*() { return getIns(); }

  MDefinition* operator->() { return getIns(); }
};

// Iterates on all resume points, phis, and instructions of a MBasicBlock.
// Resume points are visited as long as they have not been discarded.
class MNodeIterator {
 private:
  // If this is non-null, the resume point that we will visit next (unless
  // it has been discarded). Initialized to the entry resume point.
  // Otherwise, resume point of the most recently visited instruction.
  MResumePoint* resumePoint_;

  mozilla::DebugOnly<MInstruction*> lastInstruction_ = nullptr;

  // Definition iterator which is one step ahead when visiting resume points.
  // This is in order to avoid incrementing the iterator while it is settled
  // on a discarded instruction.
  MDefinitionIterator defIter_;

  MBasicBlock* block() const { return defIter_.block_; }

  bool atResumePoint() const {
    MOZ_ASSERT_IF(lastInstruction_ && !lastInstruction_->isDiscarded(),
                  lastInstruction_->resumePoint() == resumePoint_);
    return resumePoint_ && !resumePoint_->isDiscarded();
  }

  MNode* getNode() {
    if (atResumePoint()) {
      return resumePoint_;
    }
    return *defIter_;
  }

  void next() {
    if (!atResumePoint()) {
      if (defIter_->isInstruction()) {
        resumePoint_ = defIter_->toInstruction()->resumePoint();
        lastInstruction_ = defIter_->toInstruction();
      }
      defIter_++;
    } else {
      resumePoint_ = nullptr;
      lastInstruction_ = nullptr;
    }
  }

  bool more() const { return defIter_ || atResumePoint(); }

 public:
  explicit MNodeIterator(MBasicBlock* block)
      : resumePoint_(block->entryResumePoint()), defIter_(block) {
    MOZ_ASSERT(bool(block->entryResumePoint()) == atResumePoint());
  }

  MNodeIterator operator++(int) {
    MNodeIterator old(*this);
    if (more()) {
      next();
    }
    return old;
  }

  explicit operator bool() const { return more(); }

  MNode* operator*() { return getNode(); }

  MNode* operator->() { return getNode(); }
};

void MBasicBlock::add(MInstruction* ins) {
  MOZ_ASSERT(!hasLastIns());
  ins->setInstructionBlock(this, trackedSite_);
  graph().allocDefinitionId(ins);
  instructions_.pushBack(ins);
}

}  // namespace jit
}  // namespace js

#endif /* jit_MIRGraph_h */