Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 : * vim: set ts=8 sts=4 et sw=4 tw=99:
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/FixedList.h"
14 : #include "jit/JitAllocPolicy.h"
15 : #include "jit/MIR.h"
16 :
17 : namespace js {
18 : namespace jit {
19 :
20 : class BytecodeAnalysis;
21 : class MBasicBlock;
22 : class MIRGraph;
23 : class MStart;
24 :
25 : class MDefinitionIterator;
26 :
27 : typedef InlineListIterator<MInstruction> MInstructionIterator;
28 : typedef InlineListReverseIterator<MInstruction> MInstructionReverseIterator;
29 : typedef InlineListIterator<MPhi> MPhiIterator;
30 :
31 : #ifdef DEBUG
32 : typedef InlineForwardListIterator<MResumePoint> MResumePointIterator;
33 : #endif
34 :
35 : class LBlock;
36 :
37 : class MBasicBlock : public TempObject, public InlineListNode<MBasicBlock>
38 : {
39 : public:
40 : enum Kind {
41 : NORMAL,
42 : PENDING_LOOP_HEADER,
43 : LOOP_HEADER,
44 : SPLIT_EDGE,
45 : DEAD
46 : };
47 :
48 : private:
49 : MBasicBlock(MIRGraph& graph, const CompileInfo& info, BytecodeSite* site, Kind kind);
50 : MOZ_MUST_USE bool init();
51 : void copySlots(MBasicBlock* from);
52 : MOZ_MUST_USE bool inherit(TempAllocator& alloc, BytecodeAnalysis* analysis, MBasicBlock* pred,
53 : uint32_t popped, unsigned stackPhiCount = 0);
54 : MOZ_MUST_USE bool inheritResumePoint(MBasicBlock* pred);
55 : void assertUsesAreNotWithin(MUseIterator use, MUseIterator end);
56 :
57 : // This block cannot be reached by any means.
58 : bool unreachable_;
59 :
60 : // Keeps track if the phis has been type specialized already.
61 : bool specialized_;
62 :
63 : // Pushes a copy of a local variable or argument.
64 : void pushVariable(uint32_t slot);
65 :
66 : // Sets a variable slot to the top of the stack, correctly creating copies
67 : // as needed.
68 : void setVariable(uint32_t slot);
69 :
70 : enum ReferencesType {
71 : RefType_None = 0,
72 :
73 : // Assert that the instruction is unused.
74 : RefType_AssertNoUses = 1 << 0,
75 :
76 : // Discard the operands of the resume point / instructions if the
77 : // following flag are given too.
78 : RefType_DiscardOperands = 1 << 1,
79 : RefType_DiscardResumePoint = 1 << 2,
80 : RefType_DiscardInstruction = 1 << 3,
81 :
82 : // Discard operands of the instruction and its resume point.
83 : RefType_DefaultNoAssert = RefType_DiscardOperands |
84 : RefType_DiscardResumePoint |
85 : RefType_DiscardInstruction,
86 :
87 : // Discard everything and assert that the instruction is not used.
88 : RefType_Default = RefType_AssertNoUses | RefType_DefaultNoAssert,
89 :
90 : // Discard resume point operands only, without discarding the operands
91 : // of the current instruction. Asserts that the instruction is unused.
92 : RefType_IgnoreOperands = RefType_AssertNoUses |
93 : RefType_DiscardOperands |
94 : RefType_DiscardResumePoint
95 : };
96 :
97 : void discardResumePoint(MResumePoint* rp, ReferencesType refType = RefType_Default);
98 :
99 : // Remove all references to an instruction such that it can be removed from
100 : // the list of instruction, without keeping any dangling pointer to it. This
101 : // includes the operands of the instruction, and the resume point if
102 : // present.
103 : void prepareForDiscard(MInstruction* ins, ReferencesType refType = RefType_Default);
104 :
105 : public:
106 : ///////////////////////////////////////////////////////
107 : ////////// BEGIN GRAPH BUILDING INSTRUCTIONS //////////
108 : ///////////////////////////////////////////////////////
109 :
110 : // Creates a new basic block for a MIR generator. If |pred| is not nullptr,
111 : // its slots and stack depth are initialized from |pred|.
112 : static MBasicBlock* New(MIRGraph& graph, BytecodeAnalysis* analysis, const CompileInfo& info,
113 : MBasicBlock* pred, BytecodeSite* site, Kind kind);
114 : static MBasicBlock* New(MIRGraph& graph, const CompileInfo& info, MBasicBlock* pred, Kind kind);
115 : static MBasicBlock* NewPopN(MIRGraph& graph, const CompileInfo& info,
116 : MBasicBlock* pred, BytecodeSite* site, Kind kind, uint32_t popn);
117 : static MBasicBlock* NewWithResumePoint(MIRGraph& graph, const CompileInfo& info,
118 : MBasicBlock* pred, BytecodeSite* site,
119 : MResumePoint* resumePoint);
120 : static MBasicBlock* NewPendingLoopHeader(MIRGraph& graph, const CompileInfo& info,
121 : MBasicBlock* pred, BytecodeSite* site,
122 : unsigned loopStateSlots);
123 : static MBasicBlock* NewSplitEdge(MIRGraph& graph, MBasicBlock* pred,
124 : size_t predEdgeIdx, MBasicBlock* succ);
125 :
126 274176 : bool dominates(const MBasicBlock* other) const {
127 274176 : return other->domIndex() - domIndex() < numDominated();
128 : }
129 :
130 8965 : void setId(uint32_t id) {
131 8965 : id_ = id;
132 8965 : }
133 :
134 : // Mark this block (and only this block) as unreachable.
135 70 : void setUnreachable() {
136 70 : MOZ_ASSERT(!unreachable_);
137 70 : setUnreachableUnchecked();
138 70 : }
139 70 : void setUnreachableUnchecked() {
140 70 : unreachable_ = true;
141 70 : }
142 5469 : bool unreachable() const {
143 5469 : return unreachable_;
144 : }
145 : // Move the definition to the top of the stack.
146 : void pick(int32_t depth);
147 :
148 : // Move the top of the stack definition under the depth-th stack value.
149 : void unpick(int32_t depth);
150 :
151 : // Exchange 2 stack slots at the defined depth
152 : void swapAt(int32_t depth);
153 :
154 : // Gets the instruction associated with various slot types.
155 : MDefinition* peek(int32_t depth);
156 :
157 : MDefinition* environmentChain();
158 : MDefinition* argumentsObject();
159 :
160 : // Increase the number of slots available
161 : MOZ_MUST_USE bool increaseSlots(size_t num);
162 : MOZ_MUST_USE bool ensureHasSlots(size_t num);
163 :
164 : // Initializes a slot value; must not be called for normal stack
165 : // operations, as it will not create new SSA names for copies.
166 : void initSlot(uint32_t index, MDefinition* ins);
167 :
168 : // Discard the slot at the given depth, lowering all slots above.
169 : void shimmySlots(int discardDepth);
170 :
171 : // In an OSR block, set all MOsrValues to use the MResumePoint attached to
172 : // the MStart.
173 : MOZ_MUST_USE bool linkOsrValues(MStart* start);
174 :
175 : // Sets the instruction associated with various slot types. The
176 : // instruction must lie at the top of the stack.
177 : void setLocal(uint32_t local);
178 : void setArg(uint32_t arg);
179 : void setSlot(uint32_t slot);
180 : void setSlot(uint32_t slot, MDefinition* ins);
181 :
182 : // Rewrites a slot directly, bypassing the stack transition. This should
183 : // not be used under most circumstances.
184 : void rewriteSlot(uint32_t slot, MDefinition* ins);
185 :
186 : // Rewrites a slot based on its depth (same as argument to peek()).
187 : void rewriteAtDepth(int32_t depth, MDefinition* ins);
188 :
189 : // Tracks an instruction as being pushed onto the operand stack.
190 : void push(MDefinition* ins);
191 : void pushArg(uint32_t arg);
192 : void pushLocal(uint32_t local);
193 : void pushSlot(uint32_t slot);
194 : void setEnvironmentChain(MDefinition* ins);
195 : void setArgumentsObject(MDefinition* ins);
196 :
197 : // Returns the top of the stack, then decrements the virtual stack pointer.
198 : MDefinition* pop();
199 : void popn(uint32_t n);
200 :
201 : // Adds an instruction to this block's instruction list.
202 : void add(MInstruction* ins);
203 :
204 : // Marks the last instruction of the block; no further instructions
205 : // can be added.
206 : void end(MControlInstruction* ins);
207 :
208 : // Adds a phi instruction, but does not set successorWithPhis.
209 : void addPhi(MPhi* phi);
210 :
211 : // Adds a resume point to this block.
212 8996 : void addResumePoint(MResumePoint* resume) {
213 : #ifdef DEBUG
214 8996 : resumePoints_.pushFront(resume);
215 : #endif
216 8996 : }
217 :
218 : // Discard pre-allocated resume point.
219 0 : void discardPreAllocatedResumePoint(MResumePoint* resume) {
220 0 : MOZ_ASSERT(!resume->instruction());
221 0 : discardResumePoint(resume);
222 0 : }
223 :
224 : // Adds a predecessor. Every predecessor must have the same exit stack
225 : // depth as the entry state to this block. Adding a predecessor
226 : // automatically creates phi nodes and rewrites uses as needed.
227 : MOZ_MUST_USE bool addPredecessor(TempAllocator& alloc, MBasicBlock* pred);
228 : MOZ_MUST_USE bool addPredecessorPopN(TempAllocator& alloc, MBasicBlock* pred, uint32_t popped);
229 :
230 : // Add a predecessor which won't introduce any new phis to this block.
231 : // This may be called after the contents of this block have been built.
232 : void addPredecessorSameInputsAs(MBasicBlock* pred, MBasicBlock* existingPred);
233 :
234 : // Stranger utilities used for inlining.
235 : MOZ_MUST_USE bool addPredecessorWithoutPhis(MBasicBlock* pred);
236 : void inheritSlots(MBasicBlock* parent);
237 : MOZ_MUST_USE bool initEntrySlots(TempAllocator& alloc);
238 :
239 : // Replaces an edge for a given block with a new block. This is
240 : // used for critical edge splitting.
241 : //
242 : // Note: If successorWithPhis is set, you must not be replacing it.
243 : void replacePredecessor(MBasicBlock* old, MBasicBlock* split);
244 : void replaceSuccessor(size_t pos, MBasicBlock* split);
245 :
246 : // Removes `pred` from the predecessor list. If this block defines phis,
247 : // removes the entry for `pred` and updates the indices of later entries.
248 : // This may introduce redundant phis if the new block has fewer
249 : // than two predecessors.
250 : void removePredecessor(MBasicBlock* pred);
251 :
252 : // A version of removePredecessor which expects that phi operands to
253 : // |pred| have already been removed.
254 : void removePredecessorWithoutPhiOperands(MBasicBlock* pred, size_t predIndex);
255 :
256 : // Resets all the dominator info so that it can be recomputed.
257 : void clearDominatorInfo();
258 :
259 : // Sets a back edge. This places phi nodes and rewrites instructions within
260 : // the current loop as necessary. If the backedge introduces new types for
261 : // phis at the loop header, returns a disabling abort.
262 : MOZ_MUST_USE AbortReason setBackedge(TempAllocator& alloc, MBasicBlock* block);
263 : MOZ_MUST_USE bool setBackedgeWasm(MBasicBlock* block);
264 :
265 : // Resets a LOOP_HEADER block to a NORMAL block. This is needed when
266 : // optimizations remove the backedge.
267 : void clearLoopHeader();
268 :
269 : // Sets a block to a LOOP_HEADER block, with newBackedge as its backedge.
270 : // This is needed when optimizations remove the normal entry to a loop
271 : // with multiple entries.
272 : void setLoopHeader(MBasicBlock* newBackedge);
273 :
274 : // Propagates phis placed in a loop header down to this successor block.
275 : void inheritPhis(MBasicBlock* header);
276 :
277 : // Propagates backedge slots into phis operands of the loop header.
278 : MOZ_MUST_USE bool inheritPhisFromBackedge(TempAllocator& alloc, MBasicBlock* backedge,
279 : bool* hadTypeChange);
280 :
281 : // Compute the types for phis in this block according to their inputs.
282 : MOZ_MUST_USE bool specializePhis(TempAllocator& alloc);
283 :
284 : void insertBefore(MInstruction* at, MInstruction* ins);
285 : void insertAfter(MInstruction* at, MInstruction* ins);
286 :
287 : void insertAtEnd(MInstruction* ins);
288 :
289 : // Add an instruction to this block, from elsewhere in the graph.
290 : void addFromElsewhere(MInstruction* ins);
291 :
292 : // Move an instruction. Movement may cross block boundaries.
293 : void moveBefore(MInstruction* at, MInstruction* ins);
294 :
295 : enum IgnoreTop {
296 : IgnoreNone = 0,
297 : IgnoreRecover = 1 << 0
298 : };
299 :
300 : // Locate the top of the |block|, where it is safe to insert a new
301 : // instruction.
302 : MInstruction* safeInsertTop(MDefinition* ins = nullptr, IgnoreTop ignore = IgnoreNone);
303 :
304 : // Removes an instruction with the intention to discard it.
305 : void discard(MInstruction* ins);
306 : void discardLastIns();
307 : void discardDef(MDefinition* def);
308 : void discardAllInstructions();
309 : void discardAllInstructionsStartingAt(MInstructionIterator iter);
310 : void discardAllPhiOperands();
311 : void discardAllPhis();
312 : void discardAllResumePoints(bool discardEntry = true);
313 : void clear();
314 :
315 : // Same as |void discard(MInstruction* ins)| but assuming that
316 : // all operands are already discarded.
317 : void discardIgnoreOperands(MInstruction* ins);
318 :
319 : // Discards a phi instruction and updates predecessor successorWithPhis.
320 : void discardPhi(MPhi* phi);
321 :
322 : // Some instruction which are guarding against some MIRType value, or
323 : // against a type expectation should be considered as removing a potenatial
324 : // branch where the guard does not hold. We need to register such
325 : // instructions in order to do destructive optimizations correctly, such as
326 : // Range Analysis.
327 : void flagOperandsOfPrunedBranches(MInstruction* ins);
328 :
329 : // Mark this block as having been removed from the graph.
330 392 : void markAsDead() {
331 392 : MOZ_ASSERT(kind_ != DEAD);
332 392 : kind_ = DEAD;
333 392 : }
334 :
335 : ///////////////////////////////////////////////////////
336 : /////////// END GRAPH BUILDING INSTRUCTIONS ///////////
337 : ///////////////////////////////////////////////////////
338 :
339 68551 : MIRGraph& graph() {
340 68551 : return graph_;
341 : }
342 18978 : const CompileInfo& info() const {
343 18978 : return info_;
344 : }
345 9727 : jsbytecode* pc() const {
346 9727 : return pc_;
347 : }
348 17274 : uint32_t nslots() const {
349 17274 : return slots_.length();
350 : }
351 135882 : uint32_t id() const {
352 135882 : return id_;
353 : }
354 153478 : uint32_t numPredecessors() const {
355 153478 : return predecessors_.length();
356 : }
357 :
358 548352 : uint32_t domIndex() const {
359 548352 : MOZ_ASSERT(!isDead());
360 548352 : return domIndex_;
361 : }
362 3750 : void setDomIndex(uint32_t d) {
363 3750 : domIndex_ = d;
364 3750 : }
365 :
366 104980 : MBasicBlock* getPredecessor(uint32_t i) const {
367 104980 : return predecessors_[i];
368 : }
369 59 : size_t indexForPredecessor(MBasicBlock* block) const {
370 : // This should only be called before critical edge splitting.
371 59 : MOZ_ASSERT(!block->successorWithPhis());
372 :
373 91 : for (size_t i = 0; i < predecessors_.length(); i++) {
374 91 : if (predecessors_[i] == block)
375 118 : return i;
376 : }
377 0 : MOZ_CRASH();
378 : }
379 539901 : bool hasAnyIns() const {
380 539901 : return !instructions_.empty();
381 : }
382 539862 : bool hasLastIns() const {
383 539862 : return hasAnyIns() && instructions_.rbegin()->isControlInstruction();
384 : }
385 514151 : MControlInstruction* lastIns() const {
386 514151 : MOZ_ASSERT(hasLastIns());
387 514154 : return instructions_.rbegin()->toControlInstruction();
388 : }
389 : // Find or allocate an optimized out constant.
390 : MConstant* optimizedOutConstant(TempAllocator& alloc);
391 58414 : MPhiIterator phisBegin() const {
392 58414 : return phis_.begin();
393 : }
394 : MPhiIterator phisBegin(MPhi* at) const {
395 : return phis_.begin(at);
396 : }
397 2116467 : MPhiIterator phisEnd() const {
398 2116467 : return phis_.end();
399 : }
400 19023 : bool phisEmpty() const {
401 19023 : return phis_.empty();
402 : }
403 : #ifdef DEBUG
404 15325 : MResumePointIterator resumePointsBegin() const {
405 15325 : return resumePoints_.begin();
406 : }
407 40378 : MResumePointIterator resumePointsEnd() const {
408 40378 : return resumePoints_.end();
409 : }
410 392 : bool resumePointsEmpty() const {
411 392 : return resumePoints_.empty();
412 : }
413 : #endif
414 62152 : MInstructionIterator begin() {
415 62152 : return instructions_.begin();
416 : }
417 14421 : MInstructionIterator begin(MInstruction* at) {
418 14421 : MOZ_ASSERT(at->block() == this);
419 14421 : return instructions_.begin(at);
420 : }
421 84423 : MInstructionIterator end() {
422 84423 : return instructions_.end();
423 : }
424 2419 : MInstructionReverseIterator rbegin() {
425 2419 : return instructions_.rbegin();
426 : }
427 684 : MInstructionReverseIterator rbegin(MInstruction* at) {
428 684 : MOZ_ASSERT(at->block() == this);
429 684 : return instructions_.rbegin(at);
430 : }
431 11424 : MInstructionReverseIterator rend() {
432 11424 : return instructions_.rend();
433 : }
434 17461 : bool isLoopHeader() const {
435 17461 : return kind_ == LOOP_HEADER;
436 : }
437 784 : bool hasUniqueBackedge() const {
438 784 : MOZ_ASSERT(isLoopHeader());
439 784 : MOZ_ASSERT(numPredecessors() >= 2);
440 784 : if (numPredecessors() == 2)
441 784 : return true;
442 0 : if (numPredecessors() == 3) // fixup block added by ValueNumbering phase.
443 0 : return getPredecessor(1)->numPredecessors() == 0;
444 0 : return false;
445 : }
446 564 : MBasicBlock* backedge() const {
447 564 : MOZ_ASSERT(hasUniqueBackedge());
448 564 : return getPredecessor(numPredecessors() - 1);
449 : }
450 30 : MBasicBlock* loopHeaderOfBackedge() const {
451 30 : MOZ_ASSERT(isLoopBackedge());
452 30 : return getSuccessor(numSuccessors() - 1);
453 : }
454 53 : MBasicBlock* loopPredecessor() const {
455 53 : MOZ_ASSERT(isLoopHeader());
456 53 : return getPredecessor(0);
457 : }
458 2493 : bool isLoopBackedge() const {
459 2493 : if (!numSuccessors())
460 183 : return false;
461 2310 : MBasicBlock* lastSuccessor = getSuccessor(numSuccessors() - 1);
462 2525 : return lastSuccessor->isLoopHeader() &&
463 2525 : lastSuccessor->hasUniqueBackedge() &&
464 2525 : lastSuccessor->backedge() == this;
465 : }
466 50 : bool isSplitEdge() const {
467 50 : return kind_ == SPLIT_EDGE;
468 : }
469 1047797 : bool isDead() const {
470 1047797 : return kind_ == DEAD;
471 : }
472 :
473 65601 : uint32_t stackDepth() const {
474 65601 : return stackPosition_;
475 : }
476 1 : void setStackDepth(uint32_t depth) {
477 1 : stackPosition_ = depth;
478 1 : }
479 38600 : bool isMarked() const {
480 38600 : return mark_;
481 : }
482 12424 : void mark() {
483 12424 : MOZ_ASSERT(!mark_, "Marking already-marked block");
484 12424 : markUnchecked();
485 12424 : }
486 12459 : void markUnchecked() {
487 12459 : mark_ = true;
488 12459 : }
489 12409 : void unmark() {
490 12409 : MOZ_ASSERT(mark_, "Unarking unmarked block");
491 12409 : unmarkUnchecked();
492 12409 : }
493 12409 : void unmarkUnchecked() {
494 12409 : mark_ = false;
495 12409 : }
496 :
497 45054 : MBasicBlock* immediateDominator() const {
498 45054 : return immediateDominator_;
499 : }
500 :
501 4132 : void setImmediateDominator(MBasicBlock* dom) {
502 4132 : immediateDominator_ = dom;
503 4132 : }
504 :
505 : MTest* immediateDominatorBranch(BranchDirection* pdirection);
506 :
507 26689 : size_t numImmediatelyDominatedBlocks() const {
508 26689 : return immediatelyDominated_.length();
509 : }
510 :
511 19209 : MBasicBlock* getImmediatelyDominatedBlock(size_t i) const {
512 19209 : return immediatelyDominated_[i];
513 : }
514 :
515 4153 : MBasicBlock** immediatelyDominatedBlocksBegin() {
516 4153 : return immediatelyDominated_.begin();
517 : }
518 :
519 4153 : MBasicBlock** immediatelyDominatedBlocksEnd() {
520 4153 : return immediatelyDominated_.end();
521 : }
522 :
523 : // Return the number of blocks dominated by this block. All blocks
524 : // dominate at least themselves, so this will always be non-zero.
525 302768 : size_t numDominated() const {
526 302768 : MOZ_ASSERT(numDominated_ != 0);
527 302768 : return numDominated_;
528 : }
529 :
530 7342 : void addNumDominated(size_t n) {
531 7342 : numDominated_ += n;
532 7342 : }
533 :
534 : // Add |child| to this block's immediately-dominated set.
535 : bool addImmediatelyDominatedBlock(MBasicBlock* child);
536 :
537 : // Remove |child| from this block's immediately-dominated set.
538 : void removeImmediatelyDominatedBlock(MBasicBlock* child);
539 :
540 : // This function retrieves the internal instruction associated with a
541 : // slot, and should not be used for normal stack operations. It is an
542 : // internal helper that is also used to enhance spew.
543 : MDefinition* getSlot(uint32_t index);
544 :
545 95266 : MResumePoint* entryResumePoint() const {
546 95266 : return entryResumePoint_;
547 : }
548 49 : void setEntryResumePoint(MResumePoint* rp) {
549 49 : entryResumePoint_ = rp;
550 49 : }
551 441 : void clearEntryResumePoint() {
552 441 : discardResumePoint(entryResumePoint_);
553 441 : entryResumePoint_ = nullptr;
554 441 : }
555 38541 : MResumePoint* outerResumePoint() const {
556 38541 : return outerResumePoint_;
557 : }
558 33 : void setOuterResumePoint(MResumePoint* outer) {
559 33 : MOZ_ASSERT(!outerResumePoint_);
560 33 : outerResumePoint_ = outer;
561 33 : }
562 9 : void clearOuterResumePoint() {
563 9 : discardResumePoint(outerResumePoint_);
564 9 : outerResumePoint_ = nullptr;
565 9 : }
566 4527 : MResumePoint* callerResumePoint() const {
567 4527 : return callerResumePoint_;
568 : }
569 67 : void setCallerResumePoint(MResumePoint* caller) {
570 67 : callerResumePoint_ = caller;
571 67 : }
572 733 : size_t numEntrySlots() const {
573 733 : return entryResumePoint()->stackDepth();
574 : }
575 733 : MDefinition* getEntrySlot(size_t i) const {
576 733 : MOZ_ASSERT(i < numEntrySlots());
577 733 : return entryResumePoint()->getOperand(i);
578 : }
579 :
580 25306 : LBlock* lir() const {
581 25306 : return lir_;
582 : }
583 403 : void assignLir(LBlock* lir) {
584 403 : MOZ_ASSERT(!lir_);
585 403 : lir_ = lir;
586 403 : }
587 :
588 14984 : MBasicBlock* successorWithPhis() const {
589 14984 : return successorWithPhis_;
590 : }
591 3212 : uint32_t positionInPhiSuccessor() const {
592 3212 : MOZ_ASSERT(successorWithPhis());
593 3212 : return positionInPhiSuccessor_;
594 : }
595 173 : void setSuccessorWithPhis(MBasicBlock* successor, uint32_t id) {
596 173 : successorWithPhis_ = successor;
597 173 : positionInPhiSuccessor_ = id;
598 173 : }
599 469 : void clearSuccessorWithPhis() {
600 469 : successorWithPhis_ = nullptr;
601 469 : }
602 : size_t numSuccessors() const;
603 : MBasicBlock* getSuccessor(size_t index) const;
604 : size_t getSuccessorIndex(MBasicBlock*) const;
605 : size_t getPredecessorIndex(MBasicBlock*) const;
606 :
607 6555 : void setLoopDepth(uint32_t loopDepth) {
608 6555 : loopDepth_ = loopDepth;
609 6555 : }
610 17 : uint32_t loopDepth() const {
611 17 : return loopDepth_;
612 : }
613 :
614 1 : bool strict() const {
615 1 : return info_.script()->strict();
616 : }
617 :
618 : void dumpStack(GenericPrinter& out);
619 : void dumpStack();
620 :
621 : void dump(GenericPrinter& out);
622 : void dump();
623 :
624 : // Hit count
625 : enum class HitState {
626 : // Not hit information is attached to this basic block.
627 : NotDefined,
628 :
629 : // The hit information is a raw counter. Note that due to inlining this
630 : // counter is not guaranteed to be consistent over the graph.
631 : Count,
632 :
633 : // The hit information is a frequency, which is a form of normalized
634 : // counter, where a hit-count can be compared against any previous block
635 : // in the graph.
636 : Frequency
637 : };
638 724 : HitState getHitState() const {
639 724 : return hitState_;
640 : }
641 924 : void setHitCount(uint64_t count) {
642 924 : hitCount_ = count;
643 924 : hitState_ = HitState::Count;
644 924 : }
645 693 : uint64_t getHitCount() const {
646 693 : MOZ_ASSERT(hitState_ == HitState::Count);
647 693 : return hitCount_;
648 : }
649 :
650 : // Track bailouts by storing the current pc in MIR instruction added at
651 : // this cycle. This is also used for tracking calls and optimizations when
652 : // profiling.
653 19119 : void updateTrackedSite(BytecodeSite* site) {
654 19119 : MOZ_ASSERT(site->tree() == trackedSite_->tree());
655 19119 : trackedSite_ = site;
656 19119 : }
657 12910 : BytecodeSite* trackedSite() const {
658 12910 : return trackedSite_;
659 : }
660 0 : jsbytecode* trackedPc() const {
661 0 : return trackedSite_ ? trackedSite_->pc() : nullptr;
662 : }
663 384 : InlineScriptTree* trackedTree() const {
664 384 : return trackedSite_ ? trackedSite_->tree() : nullptr;
665 : }
666 :
667 : // This class is used for reverting the graph within IonBuilder.
668 : class BackupPoint {
669 : friend MBasicBlock;
670 :
671 : MBasicBlock* current_;
672 : MInstruction* lastIns_;
673 : uint32_t stackPosition_;
674 : FixedList<MDefinition*> slots_;
675 : #ifdef DEBUG
676 : // The following fields should remain identical during IonBuilder
677 : // construction, these are used for assertions.
678 : MPhi* lastPhi_;
679 : uintptr_t predecessorsCheckSum_;
680 : HashNumber instructionsCheckSum_;
681 : uint32_t id_;
682 : MResumePoint* callerResumePoint_;
683 : MResumePoint* entryResumePoint_;
684 :
685 : size_t computePredecessorsCheckSum(MBasicBlock* block);
686 : HashNumber computeInstructionsCheckSum(MBasicBlock* block);
687 : #endif
688 : public:
689 : explicit BackupPoint(MBasicBlock* current);
690 : MOZ_MUST_USE bool init(TempAllocator& alloc);
691 : MBasicBlock* restore();
692 : };
693 :
694 : friend BackupPoint;
695 :
696 : private:
697 : MIRGraph& graph_;
698 : const CompileInfo& info_; // Each block originates from a particular script.
699 : InlineList<MInstruction> instructions_;
700 : Vector<MBasicBlock*, 1, JitAllocPolicy> predecessors_;
701 : InlineList<MPhi> phis_;
702 : FixedList<MDefinition*> slots_;
703 : uint32_t stackPosition_;
704 : uint32_t id_;
705 : uint32_t domIndex_; // Index in the dominator tree.
706 : uint32_t numDominated_;
707 : jsbytecode* pc_;
708 : LBlock* lir_;
709 :
710 : // Copy of a dominator block's outerResumePoint_ which holds the state of
711 : // caller frame at the time of the call. If not null, this implies that this
712 : // basic block corresponds to an inlined script.
713 : MResumePoint* callerResumePoint_;
714 :
715 : // Resume point holding baseline-like frame for the PC corresponding to the
716 : // entry of this basic block.
717 : MResumePoint* entryResumePoint_;
718 :
719 : // Resume point holding baseline-like frame for the PC corresponding to the
720 : // beginning of the call-site which is being inlined after this block.
721 : MResumePoint* outerResumePoint_;
722 :
723 : #ifdef DEBUG
724 : // Unordered list used to verify that all the resume points which are
725 : // registered are correctly removed when a basic block is removed.
726 : InlineForwardList<MResumePoint> resumePoints_;
727 : #endif
728 :
729 : MBasicBlock* successorWithPhis_;
730 : uint32_t positionInPhiSuccessor_;
731 : uint32_t loopDepth_;
732 : Kind kind_ : 8;
733 :
734 : // Utility mark for traversal algorithms.
735 : bool mark_;
736 :
737 : Vector<MBasicBlock*, 1, JitAllocPolicy> immediatelyDominated_;
738 : MBasicBlock* immediateDominator_;
739 :
740 : BytecodeSite* trackedSite_;
741 :
742 : // Record the number of times a block got visited. Note, due to inlined
743 : // scripts these numbers might not be continuous.
744 : uint64_t hitCount_;
745 : HitState hitState_;
746 :
747 : #if defined(JS_ION_PERF) || defined(DEBUG)
748 : unsigned lineno_;
749 : unsigned columnIndex_;
750 :
751 : public:
752 : void setLineno(unsigned l) { lineno_ = l; }
753 0 : unsigned lineno() const { return lineno_; }
754 : void setColumnIndex(unsigned c) { columnIndex_ = c; }
755 0 : unsigned columnIndex() const { return columnIndex_; }
756 : #endif
757 : };
758 :
759 : typedef InlineListIterator<MBasicBlock> MBasicBlockIterator;
760 : typedef InlineListIterator<MBasicBlock> ReversePostorderIterator;
761 : typedef InlineListReverseIterator<MBasicBlock> PostorderIterator;
762 :
763 : typedef Vector<MBasicBlock*, 1, JitAllocPolicy> MIRGraphReturns;
764 :
765 : class MIRGraph
766 : {
767 : InlineList<MBasicBlock> blocks_;
768 : TempAllocator* alloc_;
769 : MIRGraphReturns* returnAccumulator_;
770 : uint32_t blockIdGen_;
771 : uint32_t idGen_;
772 : MBasicBlock* osrBlock_;
773 :
774 : size_t numBlocks_;
775 : bool hasTryBlock_;
776 :
777 : InlineList<MPhi> phiFreeList_;
778 : size_t phiFreeListLength_;
779 :
780 : public:
781 146 : explicit MIRGraph(TempAllocator* alloc)
782 146 : : alloc_(alloc),
783 : returnAccumulator_(nullptr),
784 : blockIdGen_(0),
785 : idGen_(0),
786 : osrBlock_(nullptr),
787 : numBlocks_(0),
788 : hasTryBlock_(false),
789 146 : phiFreeListLength_(0)
790 146 : { }
791 :
792 41795 : TempAllocator& alloc() const {
793 41795 : return *alloc_;
794 : }
795 :
796 : void addBlock(MBasicBlock* block);
797 : void insertBlockAfter(MBasicBlock* at, MBasicBlock* block);
798 : void insertBlockBefore(MBasicBlock* at, MBasicBlock* block);
799 :
800 : void renumberBlocksAfter(MBasicBlock* at);
801 :
802 : void unmarkBlocks();
803 :
804 66 : void setReturnAccumulator(MIRGraphReturns* accum) {
805 66 : returnAccumulator_ = accum;
806 66 : }
807 33 : MIRGraphReturns* returnAccumulator() const {
808 33 : return returnAccumulator_;
809 : }
810 :
811 561 : MOZ_MUST_USE bool addReturn(MBasicBlock* returnBlock) {
812 561 : if (!returnAccumulator_)
813 500 : return true;
814 :
815 61 : return returnAccumulator_->append(returnBlock);
816 : }
817 :
818 4909 : MBasicBlock* entryBlock() {
819 4909 : return *blocks_.begin();
820 : }
821 889 : MBasicBlockIterator begin() {
822 889 : return blocks_.begin();
823 : }
824 5 : MBasicBlockIterator begin(MBasicBlock* at) {
825 5 : return blocks_.begin(at);
826 : }
827 40151 : MBasicBlockIterator end() {
828 40151 : return blocks_.end();
829 : }
830 534 : PostorderIterator poBegin() {
831 534 : return blocks_.rbegin();
832 : }
833 15 : PostorderIterator poBegin(MBasicBlock* at) {
834 15 : return blocks_.rbegin(at);
835 : }
836 17420 : PostorderIterator poEnd() {
837 17420 : return blocks_.rend();
838 : }
839 818 : ReversePostorderIterator rpoBegin() {
840 818 : return blocks_.begin();
841 : }
842 59 : ReversePostorderIterator rpoBegin(MBasicBlock* at) {
843 59 : return blocks_.begin(at);
844 : }
845 34901 : ReversePostorderIterator rpoEnd() {
846 34901 : return blocks_.end();
847 : }
848 : MOZ_MUST_USE bool removeSuccessorBlocks(MBasicBlock* block);
849 : void removeBlock(MBasicBlock* block);
850 : void removeBlockIncludingPhis(MBasicBlock* block);
851 4 : void moveBlockToEnd(MBasicBlock* block) {
852 4 : blocks_.remove(block);
853 4 : MOZ_ASSERT_IF(!blocks_.empty(), block->id());
854 4 : blocks_.pushBack(block);
855 4 : }
856 25 : void moveBlockBefore(MBasicBlock* at, MBasicBlock* block) {
857 25 : MOZ_ASSERT(block->id());
858 25 : blocks_.remove(block);
859 25 : blocks_.insertBefore(at, block);
860 25 : }
861 945 : void removeBlockFromList(MBasicBlock* block) {
862 945 : blocks_.remove(block);
863 945 : numBlocks_--;
864 945 : }
865 1039 : size_t numBlocks() const {
866 1039 : return numBlocks_;
867 : }
868 16 : uint32_t numBlockIds() const {
869 16 : return blockIdGen_;
870 : }
871 24336 : void allocDefinitionId(MDefinition* ins) {
872 24336 : ins->setId(idGen_++);
873 24336 : }
874 40 : uint32_t getNumInstructionIds() {
875 40 : return idGen_;
876 : }
877 278 : MResumePoint* entryResumePoint() {
878 278 : return entryBlock()->entryResumePoint();
879 : }
880 :
881 : void copyIds(const MIRGraph& other) {
882 : idGen_ = other.idGen_;
883 : blockIdGen_ = other.blockIdGen_;
884 : numBlocks_ = other.numBlocks_;
885 : }
886 :
887 4 : void setOsrBlock(MBasicBlock* osrBlock) {
888 4 : MOZ_ASSERT(!osrBlock_);
889 4 : osrBlock_ = osrBlock;
890 4 : }
891 33710 : MBasicBlock* osrBlock() {
892 33710 : return osrBlock_;
893 : }
894 :
895 16 : bool hasTryBlock() const {
896 16 : return hasTryBlock_;
897 : }
898 2 : void setHasTryBlock() {
899 2 : hasTryBlock_ = true;
900 2 : }
901 :
902 : void dump(GenericPrinter& out);
903 : void dump();
904 :
905 0 : void addPhiToFreeList(MPhi* phi) {
906 0 : phiFreeList_.pushBack(phi);
907 0 : phiFreeListLength_++;
908 0 : }
909 0 : size_t phiFreeListLength() const {
910 0 : return phiFreeListLength_;
911 : }
912 0 : MPhi* takePhiFromFreeList() {
913 0 : MOZ_ASSERT(phiFreeListLength_ > 0);
914 0 : phiFreeListLength_--;
915 0 : return phiFreeList_.popBack();
916 : }
917 : };
918 :
919 : class MDefinitionIterator
920 : {
921 : friend class MBasicBlock;
922 : friend class MNodeIterator;
923 :
924 : private:
925 : MBasicBlock* block_;
926 : MPhiIterator phiIter_;
927 : MInstructionIterator iter_;
928 :
929 2064824 : bool atPhi() const {
930 2064824 : return phiIter_ != block_->phisEnd();
931 : }
932 :
933 1819611 : MDefinition* getIns() {
934 1819611 : if (atPhi())
935 585256 : return *phiIter_;
936 1234417 : return *iter_;
937 : }
938 :
939 171777 : bool more() const {
940 171777 : return atPhi() || (*iter_) != block_->lastIns();
941 : }
942 :
943 : public:
944 21129 : explicit MDefinitionIterator(MBasicBlock* block)
945 21129 : : block_(block),
946 : phiIter_(block->phisBegin()),
947 21129 : iter_(block->begin())
948 21129 : { }
949 :
950 73781 : MDefinitionIterator operator ++() {
951 73781 : MOZ_ASSERT(more());
952 73773 : if (atPhi())
953 9542 : ++phiIter_;
954 : else
955 64232 : ++iter_;
956 73773 : return *this;
957 : }
958 :
959 73781 : MDefinitionIterator operator ++(int) {
960 73781 : MDefinitionIterator old(*this);
961 73781 : operator++ ();
962 73773 : return old;
963 : }
964 :
965 98006 : explicit operator bool() const {
966 98006 : return more();
967 : }
968 :
969 557069 : MDefinition* operator*() {
970 557069 : return getIns();
971 : }
972 :
973 1262710 : MDefinition* operator ->() {
974 1262710 : return getIns();
975 : }
976 : };
977 :
978 : // Iterates on all resume points, phis, and instructions of a MBasicBlock.
979 : // Resume points are visited as long as the instruction which holds it is not
980 : // discarded.
981 : class MNodeIterator
982 : {
983 : private:
984 : // Last instruction which holds a resume point. To handle the entry point
985 : // resume point, it is set to the last instruction, assuming that the last
986 : // instruction is not discarded before we visit it.
987 : MInstruction* last_;
988 :
989 : // Definition iterator which is one step ahead when visiting resume points.
990 : // This is in order to avoid incrementing the iterator while it is settled
991 : // on a discarded instruction.
992 : MDefinitionIterator defIter_;
993 :
994 1359 : MBasicBlock* block() const {
995 1359 : return defIter_.block_;
996 : }
997 :
998 6234 : bool atResumePoint() const {
999 6234 : return last_ && !last_->isDiscarded();
1000 : }
1001 :
1002 2716 : MNode* getNode() {
1003 2716 : if (!atResumePoint())
1004 2044 : return *defIter_;
1005 :
1006 : // We use the last instruction as a sentinelle to iterate over the entry
1007 : // resume point of the basic block, before even starting to iterate on
1008 : // the instruction list. Otherwise, the last_ corresponds to the
1009 : // previous instruction.
1010 672 : if (last_ != block()->lastIns())
1011 359 : return last_->resumePoint();
1012 313 : return block()->entryResumePoint();
1013 : }
1014 :
1015 2716 : void next() {
1016 2716 : if (!atResumePoint()) {
1017 2044 : if (defIter_->isInstruction() && defIter_->toInstruction()->resumePoint()) {
1018 : // In theory, we could but in practice this does not happen.
1019 374 : MOZ_ASSERT(*defIter_ != block()->lastIns());
1020 374 : last_ = defIter_->toInstruction();
1021 : }
1022 :
1023 2044 : defIter_++;
1024 : } else {
1025 672 : last_ = nullptr;
1026 : }
1027 2716 : }
1028 :
1029 5745 : bool more() const {
1030 5745 : return defIter_ || atResumePoint();
1031 : }
1032 :
1033 : public:
1034 313 : explicit MNodeIterator(MBasicBlock* block)
1035 313 : : last_(block->entryResumePoint() ? block->lastIns() : nullptr),
1036 313 : defIter_(block)
1037 : {
1038 313 : MOZ_ASSERT(bool(block->entryResumePoint()) == atResumePoint());
1039 :
1040 : // We use the last instruction to check for the entry resume point,
1041 : // assert that no control instruction has any resume point. If so, then
1042 : // we need to handle this case in this iterator.
1043 313 : MOZ_ASSERT(!block->lastIns()->resumePoint());
1044 313 : }
1045 :
1046 2716 : MNodeIterator operator ++(int) {
1047 2716 : MNodeIterator old(*this);
1048 2716 : if (more())
1049 2716 : next();
1050 2716 : return old;
1051 : }
1052 :
1053 3029 : explicit operator bool() const {
1054 3029 : return more();
1055 : }
1056 :
1057 2716 : MNode* operator*() {
1058 2716 : return getNode();
1059 : }
1060 :
1061 : MNode* operator ->() {
1062 : return getNode();
1063 : }
1064 :
1065 : };
1066 :
1067 : } // namespace jit
1068 : } // namespace js
1069 :
1070 : #endif /* jit_MIRGraph_h */
|
