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/iterator.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
MarkBlocks()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::kArchStackPointerGreaterThan ||
28 instr->arch_opcode() == ArchOpcode::kArchFramePointer) {
29 block->mark_needs_frame();
30 break;
31 }
32 }
33 }
34 }
35
PropagateMarks()36 void FrameElider::PropagateMarks() {
37 while (PropagateInOrder() || PropagateReversed()) {
38 }
39 }
40
MarkDeConstruction()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
PropagateInOrder()78 bool FrameElider::PropagateInOrder() {
79 bool changed = false;
80 for (InstructionBlock* block : instruction_blocks()) {
81 changed |= PropagateIntoBlock(block);
82 }
83 return changed;
84 }
85
PropagateReversed()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
PropagateIntoBlock(InstructionBlock * block)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
instruction_blocks() const144 const InstructionBlocks& FrameElider::instruction_blocks() const {
145 return code_->instruction_blocks();
146 }
147
InstructionBlockAt(RpoNumber rpo_number) const148 InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const {
149 return code_->InstructionBlockAt(rpo_number);
150 }
151
InstructionAt(int index) const152 Instruction* FrameElider::InstructionAt(int index) const {
153 return code_->InstructionAt(index);
154 }
155
156 } // namespace compiler
157 } // namespace internal
158 } // namespace v8
159