1014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Copyright 2015 the V8 project authors. All rights reserved. 2014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// found in the LICENSE file. 4014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 5014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/compiler/frame-elider.h" 6014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch#include "src/base/adapters.h" 862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch 9014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace v8 { 10014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace internal { 11014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace compiler { 12014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 13014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochFrameElider::FrameElider(InstructionSequence* code) : code_(code) {} 14014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 15014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid FrameElider::Run() { 16014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch MarkBlocks(); 17014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PropagateMarks(); 18014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch MarkDeConstruction(); 19014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 20014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 21014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 22014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid FrameElider::MarkBlocks() { 233b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (InstructionBlock* block : instruction_blocks()) { 24014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block->needs_frame()) continue; 253b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (int i = block->code_start(); i < block->code_end(); ++i) { 263b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch const Instruction* instr = InstructionAt(i); 273b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch if (instr->IsCall() || instr->IsDeoptimizeCall() || 28c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch instr->arch_opcode() == ArchOpcode::kArchStackPointer || 29c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch instr->arch_opcode() == ArchOpcode::kArchFramePointer) { 30014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->mark_needs_frame(); 31014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch break; 32014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 33014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 34014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 35014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 36014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 37014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 38014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid FrameElider::PropagateMarks() { 393b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch while (PropagateInOrder() || PropagateReversed()) { 40014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 41014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 42014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 43014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 44014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochvoid FrameElider::MarkDeConstruction() { 453b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (InstructionBlock* block : instruction_blocks()) { 46014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block->needs_frame()) { 47014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Special case: The start block needs a frame. 48014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block->predecessors().empty()) { 49014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->mark_must_construct_frame(); 50014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 51014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Find "frame -> no frame" transitions, inserting frame 52014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // deconstructions. 533b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (RpoNumber& succ : block->successors()) { 54014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (!InstructionBlockAt(succ)->needs_frame()) { 55014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_EQ(1U, block->SuccessorCount()); 563b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch const Instruction* last = 573b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch InstructionAt(block->last_instruction_index()); 583b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch if (last->IsThrow() || last->IsTailCall() || 593b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch last->IsDeoptimizeCall()) { 603b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // We need to keep the frame if we exit the block through any 613b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // of these. 623b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch continue; 633b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch } 643b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch // The only cases when we need to deconstruct are ret and jump. 653b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch DCHECK(last->IsRet() || last->IsJump()); 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->mark_must_deconstruct_frame(); 67014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 68014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 69014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } else { 70014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Find "no frame -> frame" transitions, inserting frame constructions. 713b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (RpoNumber& succ : block->successors()) { 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (InstructionBlockAt(succ)->needs_frame()) { 73014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK_NE(1U, block->SuccessorCount()); 74014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch InstructionBlockAt(succ)->mark_must_construct_frame(); 75014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 76014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 77014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 78014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 79014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 80014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 81014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 82014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochbool FrameElider::PropagateInOrder() { 83014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool changed = false; 843b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (InstructionBlock* block : instruction_blocks()) { 85014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch changed |= PropagateIntoBlock(block); 86014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 87014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return changed; 88014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 89014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 90014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 91014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochbool FrameElider::PropagateReversed() { 92014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool changed = false; 933b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (InstructionBlock* block : base::Reversed(instruction_blocks())) { 94014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch changed |= PropagateIntoBlock(block); 95014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 96014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return changed; 97014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 98014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 99014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 100014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochbool FrameElider::PropagateIntoBlock(InstructionBlock* block) { 101014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Already marked, nothing to do... 102014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block->needs_frame()) return false; 103014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 104014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Never mark the dummy end node, otherwise we might incorrectly decide to 105014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // put frame deconstruction code there later, 106014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (block->successors().empty()) return false; 107014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 108014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Propagate towards the end ("downwards") if there is a predecessor needing 109014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // a frame, but don't "bleed" from deferred code to non-deferred code. 1103b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch for (RpoNumber& pred : block->predecessors()) { 111014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch if (InstructionBlockAt(pred)->needs_frame() && 112014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch (!InstructionBlockAt(pred)->IsDeferred() || block->IsDeferred())) { 113014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch block->mark_needs_frame(); 114014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return true; 115014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 116014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 117014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 11862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // Propagate towards start ("upwards") 11962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch bool need_frame_successors = false; 12062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (block->SuccessorCount() == 1) { 12162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // For single successors, propagate the needs_frame information. 12262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch need_frame_successors = 12362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch InstructionBlockAt(block->successors()[0])->needs_frame(); 12462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } else { 12562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // For multiple successors, each successor must only have a single 12662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // predecessor (because the graph is in edge-split form), so each successor 12762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // can independently create/dismantle a frame if needed. Given this 12862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // independent control, only propagate needs_frame if all non-deferred 12962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch // blocks need a frame. 13062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch for (RpoNumber& succ : block->successors()) { 13162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch InstructionBlock* successor_block = InstructionBlockAt(succ); 13262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch DCHECK_EQ(1, successor_block->PredecessorCount()); 13362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (!successor_block->IsDeferred()) { 13462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (successor_block->needs_frame()) { 13562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch need_frame_successors = true; 13662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } else { 13762ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return false; 13862ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 13962ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 14062ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 14162ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } 14262ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch if (need_frame_successors) { 14362ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch block->mark_needs_frame(); 14462ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return true; 14562ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch } else { 14662ed631aa0ff23db68a47fd423efa9c019ff2c9eBen Murdoch return false; 147014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 148014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 149014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 150014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 151014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochconst InstructionBlocks& FrameElider::instruction_blocks() const { 152014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return code_->instruction_blocks(); 153014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 154014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 155014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 156014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochInstructionBlock* FrameElider::InstructionBlockAt(RpoNumber rpo_number) const { 157014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return code_->InstructionBlockAt(rpo_number); 158014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 159014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 160014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 161014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben MurdochInstruction* FrameElider::InstructionAt(int index) const { 162014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return code_->InstructionAt(index); 163014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} 164014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 165014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace compiler 166014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 167014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 168