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