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     2141228 : FrameElider::FrameElider(InstructionSequence* code) : code_(code) {}
      14             : 
      15     2141196 : void FrameElider::Run() {
      16     2141196 :   MarkBlocks();
      17     2141454 :   PropagateMarks();
      18     2141420 :   MarkDeConstruction();
      19     2141488 : }
      20             : 
      21     2141222 : void FrameElider::MarkBlocks() {
      22    85041141 :   for (InstructionBlock* block : instruction_blocks()) {
      23    19440931 :     if (block->needs_frame()) continue;
      24    90953996 :     for (int i = block->code_start(); i < block->code_end(); ++i) {
      25    31386197 :       const Instruction* instr = InstructionAt(i);
      26    61207234 :       if (instr->IsCall() || instr->IsDeoptimizeCall() ||
      27    61026580 :           instr->arch_opcode() == ArchOpcode::kArchStackPointer ||
      28             :           instr->arch_opcode() == ArchOpcode::kArchFramePointer) {
      29             :         block->mark_needs_frame();
      30             :         break;
      31             :       }
      32             :     }
      33             :   }
      34     2141438 : }
      35             : 
      36     2141312 : void FrameElider::PropagateMarks() {
      37     2141312 :   while (PropagateInOrder() || PropagateReversed()) {
      38             :   }
      39     2141370 : }
      40             : 
      41     2141514 : void FrameElider::MarkDeConstruction() {
      42    26505869 :   for (InstructionBlock* block : instruction_blocks()) {
      43    19441374 :     if (block->needs_frame()) {
      44             :       // Special case: The start block needs a frame.
      45    16708936 :       if (block->predecessors().empty()) {
      46             :         block->mark_must_construct_frame();
      47             :       }
      48             :       // Find "frame -> no frame" transitions, inserting frame
      49             :       // deconstructions.
      50    55861320 :       for (RpoNumber& succ : block->successors()) {
      51    22443338 :         if (!InstructionBlockAt(succ)->needs_frame()) {
      52             :           DCHECK_EQ(1U, block->SuccessorCount());
      53             :           const Instruction* last =
      54     2781472 :               InstructionAt(block->last_instruction_index());
      55     7806825 :           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     6302182 :       for (RpoNumber& succ : block->successors()) {
      69      837306 :         if (InstructionBlockAt(succ)->needs_frame()) {
      70             :           DCHECK_NE(1U, block->SuccessorCount());
      71             :           InstructionBlockAt(succ)->mark_must_construct_frame();
      72             :         }
      73             :       }
      74             :     }
      75             :   }
      76     2141509 : }
      77             : 
      78     2769814 : bool FrameElider::PropagateInOrder() {
      79             :   bool changed = false;
      80    42524617 :   for (InstructionBlock* block : instruction_blocks()) {
      81    36984848 :     changed |= PropagateIntoBlock(block);
      82             :   }
      83     2769955 :   return changed;
      84             : }
      85             : 
      86     2141460 : bool FrameElider::PropagateReversed() {
      87             :   bool changed = false;
      88    41024083 :   for (InstructionBlock* block : base::Reversed(instruction_blocks())) {
      89    19441286 :     changed |= PropagateIntoBlock(block);
      90             :   }
      91     2141511 :   return changed;
      92             : }
      93             : 
      94    58849890 : bool FrameElider::PropagateIntoBlock(InstructionBlock* block) {
      95             :   // Already marked, nothing to do...
      96    56426088 :   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    18021764 :   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    28454828 :   for (RpoNumber& pred : block->predecessors()) {
     105    38640206 :     if (InstructionBlockAt(pred)->needs_frame() &&
     106    13942153 :         (!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     1780474 :   if (block->SuccessorCount() == 1) {
     115             :     // For single successors, propagate the needs_frame information.
     116             :     need_frame_successors =
     117     1020678 :         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     1026468 :     for (RpoNumber& succ : block->successors()) {
     125     1656344 :       InstructionBlock* successor_block = InstructionBlockAt(succ);
     126             :       DCHECK_EQ(1, successor_block->PredecessorCount());
     127      951764 :       if (!successor_block->IsDeferred()) {
     128      704580 :         if (successor_block->needs_frame()) {
     129             :           need_frame_successors = true;
     130             :         } else {
     131             :           return false;
     132             :         }
     133             :       }
     134             :     }
     135             :   }
     136     1095382 :   if (need_frame_successors) {
     137             :     block->mark_needs_frame();
     138       25200 :     return true;
     139             :   } else {
     140             :     return false;
     141             :   }
     142             : }
     143             : 
     144           0 : const InstructionBlocks& FrameElider::instruction_blocks() const {
     145     9194010 :   return code_->instruction_blocks();
     146             : }
     147             : 
     148           0 : InstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const {
     149    50401017 :   return code_->InstructionBlockAt(rpo_number);
     150             : }
     151             : 
     152    34167643 : Instruction* FrameElider::InstructionAt(int index) const {
     153    68335321 :   return code_->InstructionAt(index);
     154             : }
     155             : 
     156             : }  // namespace compiler
     157             : }  // namespace internal
     158      178779 : }  // namespace v8