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
9namespace v8 {
10namespace internal {
11namespace compiler {
12
13FrameElider::FrameElider(InstructionSequence* code) : code_(code) {}
14
15void FrameElider::Run() {
16  MarkBlocks();
17  PropagateMarks();
18  MarkDeConstruction();
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::kArchStackPointerGreaterThan ||
28          instr->arch_opcode() == ArchOpcode::kArchFramePointer) {
29        block->mark_needs_frame();
30        break;
31      }
32    }
33  }
34}
35
36void FrameElider::PropagateMarks() {
37  while (PropagateInOrder() || PropagateReversed()) {
38  }
39}
40
41void 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
78bool FrameElider::PropagateInOrder() {
79  bool changed = false;
80  for (InstructionBlock* block : instruction_blocks()) {
81    changed |= PropagateIntoBlock(block);
82  }
83  return changed;
84}
85
86bool FrameElider::PropagateReversed() {
87  bool changed = false;
88  for (InstructionBlock* block : base::Reversed(instruction_blocks())) {
89    changed |= PropagateIntoBlock(block);
90  }
91  return changed;
92}
93
94bool 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
144const InstructionBlocks& FrameElider::instruction_blocks() const {
145  return code_->instruction_blocks();
146}
147
148InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const {
149  return code_->InstructionBlockAt(rpo_number);
150}
151
152Instruction* FrameElider::InstructionAt(int index) const {
153  return code_->InstructionAt(index);
154}
155
156}  // namespace compiler
157}  // namespace internal
158}  // namespace v8
159