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 (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 
PropagateMarks()37 void FrameElider::PropagateMarks() {
38   while (PropagateInOrder() || PropagateReversed()) {
39   }
40 }
41 
42 
MarkDeConstruction()43 void FrameElider::MarkDeConstruction() {
44   for (InstructionBlock* block : instruction_blocks()) {
45     if (block->needs_frame()) {
46       // Special case: The start block needs a frame.
47       if (block->predecessors().empty()) {
48         block->mark_must_construct_frame();
49       }
50       // Find "frame -> no frame" transitions, inserting frame
51       // deconstructions.
52       for (RpoNumber& succ : block->successors()) {
53         if (!InstructionBlockAt(succ)->needs_frame()) {
54           DCHECK_EQ(1U, block->SuccessorCount());
55           const Instruction* last =
56               InstructionAt(block->last_instruction_index());
57           if (last->IsThrow() || last->IsTailCall() ||
58               last->IsDeoptimizeCall()) {
59             // We need to keep the frame if we exit the block through any
60             // of these.
61             continue;
62           }
63           // The only cases when we need to deconstruct are ret and jump.
64           DCHECK(last->IsRet() || last->IsJump());
65           block->mark_must_deconstruct_frame();
66         }
67       }
68     } else {
69       // Find "no frame -> frame" transitions, inserting frame constructions.
70       for (RpoNumber& succ : block->successors()) {
71         if (InstructionBlockAt(succ)->needs_frame()) {
72           DCHECK_NE(1U, block->SuccessorCount());
73           InstructionBlockAt(succ)->mark_must_construct_frame();
74         }
75       }
76     }
77   }
78 }
79 
80 
PropagateInOrder()81 bool FrameElider::PropagateInOrder() {
82   bool changed = false;
83   for (InstructionBlock* block : instruction_blocks()) {
84     changed |= PropagateIntoBlock(block);
85   }
86   return changed;
87 }
88 
89 
PropagateReversed()90 bool FrameElider::PropagateReversed() {
91   bool changed = false;
92   for (InstructionBlock* block : base::Reversed(instruction_blocks())) {
93     changed |= PropagateIntoBlock(block);
94   }
95   return changed;
96 }
97 
98 
PropagateIntoBlock(InstructionBlock * block)99 bool FrameElider::PropagateIntoBlock(InstructionBlock* block) {
100   // Already marked, nothing to do...
101   if (block->needs_frame()) return false;
102 
103   // Never mark the dummy end node, otherwise we might incorrectly decide to
104   // put frame deconstruction code there later,
105   if (block->successors().empty()) return false;
106 
107   // Propagate towards the end ("downwards") if there is a predecessor needing
108   // a frame, but don't "bleed" from deferred code to non-deferred code.
109   for (RpoNumber& pred : block->predecessors()) {
110     if (InstructionBlockAt(pred)->needs_frame() &&
111         (!InstructionBlockAt(pred)->IsDeferred() || block->IsDeferred())) {
112       block->mark_needs_frame();
113       return true;
114     }
115   }
116 
117   // Propagate towards start ("upwards") if there are successors and all of
118   // them need a frame.
119   for (RpoNumber& succ : block->successors()) {
120     if (!InstructionBlockAt(succ)->needs_frame()) return false;
121   }
122   block->mark_needs_frame();
123   return true;
124 }
125 
126 
instruction_blocks() const127 const InstructionBlocks& FrameElider::instruction_blocks() const {
128   return code_->instruction_blocks();
129 }
130 
131 
InstructionBlockAt(RpoNumber rpo_number) const132 InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const {
133   return code_->InstructionBlockAt(rpo_number);
134 }
135 
136 
InstructionAt(int index) const137 Instruction* FrameElider::InstructionAt(int index) const {
138   return code_->InstructionAt(index);
139 }
140 
141 }  // namespace compiler
142 }  // namespace internal
143 }  // namespace v8
144