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/base/adapters.h"
6 #include "src/compiler/frame-elider.h"
7 
8 namespace v8 {
9 namespace internal {
10 namespace compiler {
11 
FrameElider(InstructionSequence * code)12 FrameElider::FrameElider(InstructionSequence* code) : code_(code) {}
13 
Run()14 void FrameElider::Run() {
15   MarkBlocks();
16   PropagateMarks();
17   MarkDeConstruction();
18 }
19 
20 
MarkBlocks()21 void FrameElider::MarkBlocks() {
22   for (auto block : instruction_blocks()) {
23     if (block->needs_frame()) continue;
24     for (auto i = block->code_start(); i < block->code_end(); ++i) {
25       if (InstructionAt(i)->IsCall() ||
26           InstructionAt(i)->opcode() == ArchOpcode::kArchDeoptimize) {
27         block->mark_needs_frame();
28         break;
29       }
30     }
31   }
32 }
33 
34 
PropagateMarks()35 void FrameElider::PropagateMarks() {
36   while (PropagateInOrder() && PropagateReversed()) {
37   }
38 }
39 
40 
MarkDeConstruction()41 void FrameElider::MarkDeConstruction() {
42   for (auto 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 (auto succ : block->successors()) {
51         if (!InstructionBlockAt(succ)->needs_frame()) {
52           DCHECK_EQ(1U, block->SuccessorCount());
53           block->mark_must_deconstruct_frame();
54         }
55       }
56     } else {
57       // Find "no frame -> frame" transitions, inserting frame constructions.
58       for (auto succ : block->successors()) {
59         if (InstructionBlockAt(succ)->needs_frame()) {
60           DCHECK_NE(1U, block->SuccessorCount());
61           InstructionBlockAt(succ)->mark_must_construct_frame();
62         }
63       }
64     }
65   }
66 }
67 
68 
PropagateInOrder()69 bool FrameElider::PropagateInOrder() {
70   bool changed = false;
71   for (auto block : instruction_blocks()) {
72     changed |= PropagateIntoBlock(block);
73   }
74   return changed;
75 }
76 
77 
PropagateReversed()78 bool FrameElider::PropagateReversed() {
79   bool changed = false;
80   for (auto block : base::Reversed(instruction_blocks())) {
81     changed |= PropagateIntoBlock(block);
82   }
83   return changed;
84 }
85 
86 
PropagateIntoBlock(InstructionBlock * block)87 bool FrameElider::PropagateIntoBlock(InstructionBlock* block) {
88   // Already marked, nothing to do...
89   if (block->needs_frame()) return false;
90 
91   // Never mark the dummy end node, otherwise we might incorrectly decide to
92   // put frame deconstruction code there later,
93   if (block->successors().empty()) return false;
94 
95   // Propagate towards the end ("downwards") if there is a predecessor needing
96   // a frame, but don't "bleed" from deferred code to non-deferred code.
97   for (auto pred : block->predecessors()) {
98     if (InstructionBlockAt(pred)->needs_frame() &&
99         (!InstructionBlockAt(pred)->IsDeferred() || block->IsDeferred())) {
100       block->mark_needs_frame();
101       return true;
102     }
103   }
104 
105   // Propagate towards start ("upwards") if there are successors and all of
106   // them need a frame.
107   for (auto succ : block->successors()) {
108     if (!InstructionBlockAt(succ)->needs_frame()) return false;
109   }
110   block->mark_needs_frame();
111   return true;
112 }
113 
114 
instruction_blocks() const115 const InstructionBlocks& FrameElider::instruction_blocks() const {
116   return code_->instruction_blocks();
117 }
118 
119 
InstructionBlockAt(RpoNumber rpo_number) const120 InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const {
121   return code_->InstructionBlockAt(rpo_number);
122 }
123 
124 
InstructionAt(int index) const125 Instruction* FrameElider::InstructionAt(int index) const {
126   return code_->InstructionAt(index);
127 }
128 
129 }  // namespace compiler
130 }  // namespace internal
131 }  // namespace v8
132