1 | // Copyright 2015 the V8 project authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. |
4 | |
5 | #include "src/compiler/backend/frame-elider.h" |
6 | |
7 | #include "src/base/adapters.h" |
8 | |
9 | namespace v8 { |
10 | namespace internal { |
11 | namespace compiler { |
12 | |
13 | FrameElider::FrameElider(InstructionSequence* code) : code_(code) {} |
14 | |
15 | void FrameElider::Run() { |
16 | MarkBlocks(); |
17 | PropagateMarks(); |
18 | MarkDeConstruction(); |
19 | } |
20 | |
21 | void FrameElider::MarkBlocks() { |
22 | for (InstructionBlock* block : instruction_blocks()) { |
23 | if (block->needs_frame()) continue; |
24 | for (int i = block->code_start(); i < block->code_end(); ++i) { |
25 | const Instruction* instr = InstructionAt(i); |
26 | if (instr->IsCall() || instr->IsDeoptimizeCall() || |
27 | instr->arch_opcode() == ArchOpcode::kArchStackPointer || |
28 | instr->arch_opcode() == ArchOpcode::kArchFramePointer) { |
29 | block->mark_needs_frame(); |
30 | break; |
31 | } |
32 | } |
33 | } |
34 | } |
35 | |
36 | void FrameElider::PropagateMarks() { |
37 | while (PropagateInOrder() || PropagateReversed()) { |
38 | } |
39 | } |
40 | |
41 | void FrameElider::MarkDeConstruction() { |
42 | for (InstructionBlock* block : instruction_blocks()) { |
43 | if (block->needs_frame()) { |
44 | // Special case: The start block needs a frame. |
45 | if (block->predecessors().empty()) { |
46 | block->mark_must_construct_frame(); |
47 | } |
48 | // Find "frame -> no frame" transitions, inserting frame |
49 | // deconstructions. |
50 | for (RpoNumber& succ : block->successors()) { |
51 | if (!InstructionBlockAt(succ)->needs_frame()) { |
52 | DCHECK_EQ(1U, block->SuccessorCount()); |
53 | const Instruction* last = |
54 | InstructionAt(block->last_instruction_index()); |
55 | if (last->IsThrow() || last->IsTailCall() || |
56 | last->IsDeoptimizeCall()) { |
57 | // We need to keep the frame if we exit the block through any |
58 | // of these. |
59 | continue; |
60 | } |
61 | // The only cases when we need to deconstruct are ret and jump. |
62 | DCHECK(last->IsRet() || last->IsJump()); |
63 | block->mark_must_deconstruct_frame(); |
64 | } |
65 | } |
66 | } else { |
67 | // Find "no frame -> frame" transitions, inserting frame constructions. |
68 | for (RpoNumber& succ : block->successors()) { |
69 | if (InstructionBlockAt(succ)->needs_frame()) { |
70 | DCHECK_NE(1U, block->SuccessorCount()); |
71 | InstructionBlockAt(succ)->mark_must_construct_frame(); |
72 | } |
73 | } |
74 | } |
75 | } |
76 | } |
77 | |
78 | bool FrameElider::PropagateInOrder() { |
79 | bool changed = false; |
80 | for (InstructionBlock* block : instruction_blocks()) { |
81 | changed |= PropagateIntoBlock(block); |
82 | } |
83 | return changed; |
84 | } |
85 | |
86 | bool FrameElider::PropagateReversed() { |
87 | bool changed = false; |
88 | for (InstructionBlock* block : base::Reversed(instruction_blocks())) { |
89 | changed |= PropagateIntoBlock(block); |
90 | } |
91 | return changed; |
92 | } |
93 | |
94 | bool FrameElider::PropagateIntoBlock(InstructionBlock* block) { |
95 | // Already marked, nothing to do... |
96 | if (block->needs_frame()) return false; |
97 | |
98 | // Never mark the dummy end node, otherwise we might incorrectly decide to |
99 | // put frame deconstruction code there later, |
100 | if (block->successors().empty()) return false; |
101 | |
102 | // Propagate towards the end ("downwards") if there is a predecessor needing |
103 | // a frame, but don't "bleed" from deferred code to non-deferred code. |
104 | for (RpoNumber& pred : block->predecessors()) { |
105 | if (InstructionBlockAt(pred)->needs_frame() && |
106 | (!InstructionBlockAt(pred)->IsDeferred() || block->IsDeferred())) { |
107 | block->mark_needs_frame(); |
108 | return true; |
109 | } |
110 | } |
111 | |
112 | // Propagate towards start ("upwards") |
113 | bool need_frame_successors = false; |
114 | if (block->SuccessorCount() == 1) { |
115 | // For single successors, propagate the needs_frame information. |
116 | need_frame_successors = |
117 | InstructionBlockAt(block->successors()[0])->needs_frame(); |
118 | } else { |
119 | // For multiple successors, each successor must only have a single |
120 | // predecessor (because the graph is in edge-split form), so each successor |
121 | // can independently create/dismantle a frame if needed. Given this |
122 | // independent control, only propagate needs_frame if all non-deferred |
123 | // blocks need a frame. |
124 | for (RpoNumber& succ : block->successors()) { |
125 | InstructionBlock* successor_block = InstructionBlockAt(succ); |
126 | DCHECK_EQ(1, successor_block->PredecessorCount()); |
127 | if (!successor_block->IsDeferred()) { |
128 | if (successor_block->needs_frame()) { |
129 | need_frame_successors = true; |
130 | } else { |
131 | return false; |
132 | } |
133 | } |
134 | } |
135 | } |
136 | if (need_frame_successors) { |
137 | block->mark_needs_frame(); |
138 | return true; |
139 | } else { |
140 | return false; |
141 | } |
142 | } |
143 | |
144 | const InstructionBlocks& FrameElider::instruction_blocks() const { |
145 | return code_->instruction_blocks(); |
146 | } |
147 | |
148 | InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const { |
149 | return code_->InstructionBlockAt(rpo_number); |
150 | } |
151 | |
152 | Instruction* FrameElider::InstructionAt(int index) const { |
153 | return code_->InstructionAt(index); |
154 | } |
155 | |
156 | } // namespace compiler |
157 | } // namespace internal |
158 | } // namespace v8 |
159 | |