Line data    Source code

       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/adapters.h"
       8             : 
       9             : namespace v8 {
      10             : namespace internal {
      11             : namespace compiler {
      12             : 
      13     2640089 : FrameElider::FrameElider(InstructionSequence* code) : code_(code) {}
      14             : 
      15     2640353 : void FrameElider::Run() {
      16     2640353 :   MarkBlocks();
      17     2641655 :   PropagateMarks();
      18     2642847 :   MarkDeConstruction();
      19     2642924 : }
      20             : 
      21     2641891 : void FrameElider::MarkBlocks() {
      22    23111100 :   for (InstructionBlock* block : instruction_blocks()) {
      23    20469500 :     if (block->needs_frame()) continue;
      24    76385068 :     for (int i = block->code_start(); i < block->code_end(); ++i) {
      25             :       const Instruction* instr = InstructionAt(i);
      26    62234931 :       if (instr->IsCall() || instr->IsDeoptimizeCall() ||
      27    62057159 :           instr->arch_opcode() == ArchOpcode::kArchStackPointer ||
      28             :           instr->arch_opcode() == ArchOpcode::kArchFramePointer) {
      29             :         block->mark_needs_frame();
      30             :         break;
      31             :       }
      32             :     }
      33             :   }
      34     2641600 : }
      35             : 
      36     2641288 : void FrameElider::PropagateMarks() {
      37     3385232 :   while (PropagateInOrder() || PropagateReversed()) {
      38             :   }
      39     2642857 : }
      40             : 
      41     2646017 : void FrameElider::MarkDeConstruction() {
      42    23123295 :   for (InstructionBlock* block : instruction_blocks()) {
      43    20480359 :     if (block->needs_frame()) {
      44             :       // Special case: The start block needs a frame.
      45    17200876 :       if (block->predecessors().empty()) {
      46             :         block->mark_must_construct_frame();
      47             :       }
      48             :       // Find "frame -> no frame" transitions, inserting frame
      49             :       // deconstructions.
      50    40117154 :       for (RpoNumber& succ : block->successors()) {
      51    22916031 :         if (!InstructionBlockAt(succ)->needs_frame()) {
      52             :           DCHECK_EQ(1U, block->SuccessorCount());
      53             :           const Instruction* last =
      54             :               InstructionAt(block->last_instruction_index());
      55     9568174 :           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     4183505 :       for (RpoNumber& succ : block->successors()) {
      69      904022 :         if (InstructionBlockAt(succ)->needs_frame()) {
      70             :           DCHECK_NE(1U, block->SuccessorCount());
      71             :           InstructionBlockAt(succ)->mark_must_construct_frame();
      72             :         }
      73             :       }
      74             :     }
      75             :   }
      76     2642936 : }
      77             : 
      78     3385312 : bool FrameElider::PropagateInOrder() {
      79             :   bool changed = false;
      80    41393162 :   for (InstructionBlock* block : instruction_blocks()) {
      81    38007269 :     changed |= PropagateIntoBlock(block);
      82             :   }
      83     3385893 :   return changed;
      84             : }
      85             : 
      86     2642682 : bool FrameElider::PropagateReversed() {
      87             :   bool changed = false;
      88    23119331 :   for (InstructionBlock* block : base::Reversed(instruction_blocks())) {
      89    20476535 :     changed |= PropagateIntoBlock(block);
      90             :   }
      91     2642796 :   return changed;
      92             : }
      93             : 
      94    58481781 : bool FrameElider::PropagateIntoBlock(InstructionBlock* block) {
      95             :   // Already marked, nothing to do...
      96    58481781 :   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    18943419 :   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    15297879 :   for (RpoNumber& pred : block->predecessors()) {
     105    38066522 :     if (InstructionBlockAt(pred)->needs_frame() &&
     106     2323032 :         (!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     1888522 :   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     1069444 :     for (RpoNumber& succ : block->successors()) {
     125             :       InstructionBlock* successor_block = InstructionBlockAt(succ);
     126             :       DCHECK_EQ(1, successor_block->PredecessorCount());
     127     1000564 :       if (!successor_block->IsDeferred()) {
     128      757068 :         if (successor_block->needs_frame()) {
     129             :           need_frame_successors = true;
     130             :         } else {
     131             :           return false;
     132             :         }
     133             :       }
     134             :     }
     135             :   }
     136     1150382 :   if (need_frame_successors) {
     137             :     block->mark_needs_frame();
     138       24528 :     return true;
     139             :   } else {
     140             :     return false;
     141             :   }
     142             : }
     143             : 
     144           0 : const InstructionBlocks& FrameElider::instruction_blocks() const {
     145    11315902 :   return code_->instruction_blocks();
     146             : }
     147             : 
     148           0 : InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const {
     149    50645856 :   return code_->InstructionBlockAt(rpo_number);
     150             : }
     151             : 
     152           0 : Instruction* FrameElider::InstructionAt(int index) const {
     153    31950605 :   return code_->InstructionAt(index);
     154             : }
     155             : 
     156             : }  // namespace compiler
     157             : }  // namespace internal
     158      121996 : }  // namespace v8