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