Home | History | Annotate | Download | only in compiler 
      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/frame-elider.h"
      6 
      7 #include "src/base/adapters.h"
      8 
      9 namespace v8 {
     10 namespace internal {
     11 namespace compiler {
     12 
     13 FrameElider::FrameElider(InstructionSequence* code) : code_(code) {}
     14 
     15 void FrameElider::Run() {
     16   MarkBlocks();
     17   PropagateMarks();
     18   MarkDeConstruction();
     19 }
     20 
     21 
     22 void FrameElider::MarkBlocks() {
     23   for (InstructionBlock* block : instruction_blocks()) {
     24     if (block->needs_frame()) continue;
     25     for (int i = block->code_start(); i < block->code_end(); ++i) {
     26       const Instruction* instr = InstructionAt(i);
     27       if (instr->IsCall() || instr->IsDeoptimizeCall() ||
     28           instr->arch_opcode() == ArchOpcode::kArchStackPointer ||
     29           instr->arch_opcode() == ArchOpcode::kArchFramePointer) {
     30         block->mark_needs_frame();
     31         break;
     32       }
     33     }
     34   }
     35 }
     36 
     37 
     38 void FrameElider::PropagateMarks() {
     39   while (PropagateInOrder() || PropagateReversed()) {
     40   }
     41 }
     42 
     43 
     44 void FrameElider::MarkDeConstruction() {
     45   for (InstructionBlock* block : instruction_blocks()) {
     46     if (block->needs_frame()) {
     47       // Special case: The start block needs a frame.
     48       if (block->predecessors().empty()) {
     49         block->mark_must_construct_frame();
     50       }
     51       // Find "frame -> no frame" transitions, inserting frame
     52       // deconstructions.
     53       for (RpoNumber& succ : block->successors()) {
     54         if (!InstructionBlockAt(succ)->needs_frame()) {
     55           DCHECK_EQ(1U, block->SuccessorCount());
     56           const Instruction* last =
     57               InstructionAt(block->last_instruction_index());
     58           if (last->IsThrow() || last->IsTailCall() ||
     59               last->IsDeoptimizeCall()) {
     60             // We need to keep the frame if we exit the block through any
     61             // of these.
     62             continue;
     63           }
     64           // The only cases when we need to deconstruct are ret and jump.
     65           DCHECK(last->IsRet() || last->IsJump());
     66           block->mark_must_deconstruct_frame();
     67         }
     68       }
     69     } else {
     70       // Find "no frame -> frame" transitions, inserting frame constructions.
     71       for (RpoNumber& succ : block->successors()) {
     72         if (InstructionBlockAt(succ)->needs_frame()) {
     73           DCHECK_NE(1U, block->SuccessorCount());
     74           InstructionBlockAt(succ)->mark_must_construct_frame();
     75         }
     76       }
     77     }
     78   }
     79 }
     80 
     81 
     82 bool FrameElider::PropagateInOrder() {
     83   bool changed = false;
     84   for (InstructionBlock* block : instruction_blocks()) {
     85     changed |= PropagateIntoBlock(block);
     86   }
     87   return changed;
     88 }
     89 
     90 
     91 bool FrameElider::PropagateReversed() {
     92   bool changed = false;
     93   for (InstructionBlock* block : base::Reversed(instruction_blocks())) {
     94     changed |= PropagateIntoBlock(block);
     95   }
     96   return changed;
     97 }
     98 
     99 
    100 bool FrameElider::PropagateIntoBlock(InstructionBlock* block) {
    101   // Already marked, nothing to do...
    102   if (block->needs_frame()) return false;
    103 
    104   // Never mark the dummy end node, otherwise we might incorrectly decide to
    105   // put frame deconstruction code there later,
    106   if (block->successors().empty()) return false;
    107 
    108   // Propagate towards the end ("downwards") if there is a predecessor needing
    109   // a frame, but don't "bleed" from deferred code to non-deferred code.
    110   for (RpoNumber& pred : block->predecessors()) {
    111     if (InstructionBlockAt(pred)->needs_frame() &&
    112         (!InstructionBlockAt(pred)->IsDeferred() || block->IsDeferred())) {
    113       block->mark_needs_frame();
    114       return true;
    115     }
    116   }
    117 
    118   // Propagate towards start ("upwards")
    119   bool need_frame_successors = false;
    120   if (block->SuccessorCount() == 1) {
    121     // For single successors, propagate the needs_frame information.
    122     need_frame_successors =
    123         InstructionBlockAt(block->successors()[0])->needs_frame();
    124   } else {
    125     // For multiple successors, each successor must only have a single
    126     // predecessor (because the graph is in edge-split form), so each successor
    127     // can independently create/dismantle a frame if needed. Given this
    128     // independent control, only propagate needs_frame if all non-deferred
    129     // blocks need a frame.
    130     for (RpoNumber& succ : block->successors()) {
    131       InstructionBlock* successor_block = InstructionBlockAt(succ);
    132       DCHECK_EQ(1, successor_block->PredecessorCount());
    133       if (!successor_block->IsDeferred()) {
    134         if (successor_block->needs_frame()) {
    135           need_frame_successors = true;
    136         } else {
    137           return false;
    138         }
    139       }
    140     }
    141   }
    142   if (need_frame_successors) {
    143     block->mark_needs_frame();
    144     return true;
    145   } else {
    146     return false;
    147   }
    148 }
    149 
    150 
    151 const InstructionBlocks& FrameElider::instruction_blocks() const {
    152   return code_->instruction_blocks();
    153 }
    154 
    155 
    156 InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const {
    157   return code_->InstructionBlockAt(rpo_number);
    158 }
    159 
    160 
    161 Instruction* FrameElider::InstructionAt(int index) const {
    162   return code_->InstructionAt(index);
    163 }
    164 
    165 }  // namespace compiler
    166 }  // namespace internal
    167 }  // namespace v8
    168