| // Copyright 2009 the V8 project authors. All rights reserved. |
| // Redistribution and use in source and binary forms, with or without |
| // modification, are permitted provided that the following conditions are |
| // met: |
| // |
| // * Redistributions of source code must retain the above copyright |
| // notice, this list of conditions and the following disclaimer. |
| // * Redistributions in binary form must reproduce the above |
| // copyright notice, this list of conditions and the following |
| // disclaimer in the documentation and/or other materials provided |
| // with the distribution. |
| // * Neither the name of Google Inc. nor the names of its |
| // contributors may be used to endorse or promote products derived |
| // from this software without specific prior written permission. |
| // |
| // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| #include "v8.h" |
| |
| #include "codegen.h" |
| #include "jump-target.h" |
| |
| namespace v8 { namespace internal { |
| |
| // ------------------------------------------------------------------------- |
| // JumpTarget implementation. |
| |
| JumpTarget::JumpTarget(CodeGenerator* cgen, Directionality direction) |
| : cgen_(cgen), |
| direction_(direction), |
| reaching_frames_(0), |
| merge_labels_(0), |
| entry_frame_(NULL), |
| is_bound_(false), |
| is_linked_(false) { |
| ASSERT(cgen != NULL); |
| masm_ = cgen->masm(); |
| } |
| |
| |
| JumpTarget::JumpTarget() |
| : cgen_(NULL), |
| masm_(NULL), |
| direction_(FORWARD_ONLY), |
| reaching_frames_(0), |
| merge_labels_(0), |
| entry_frame_(NULL), |
| is_bound_(false), |
| is_linked_(false) { |
| } |
| |
| |
| void JumpTarget::Initialize(CodeGenerator* cgen, Directionality direction) { |
| ASSERT(cgen != NULL); |
| ASSERT(cgen_ == NULL); |
| cgen_ = cgen; |
| masm_ = cgen->masm(); |
| direction_ = direction; |
| } |
| |
| |
| void JumpTarget::Unuse() { |
| // We should not deallocate jump targets that have unresolved jumps |
| // to them. In the event of a compile-time stack overflow or an |
| // unitialized jump target, we don't care. |
| ASSERT(!is_linked() || cgen_ == NULL || cgen_->HasStackOverflow()); |
| for (int i = 0; i < reaching_frames_.length(); i++) { |
| delete reaching_frames_[i]; |
| } |
| delete entry_frame_; |
| |
| Reset(); |
| } |
| |
| |
| void JumpTarget::Reset() { |
| reaching_frames_.Clear(); |
| merge_labels_.Clear(); |
| entry_frame_ = NULL; |
| entry_label_.Unuse(); |
| is_bound_ = false; |
| is_linked_ = false; |
| } |
| |
| |
| FrameElement* JumpTarget::Combine(FrameElement* left, FrameElement* right) { |
| // Given a pair of non-null frame element pointers, return one of |
| // them as an entry frame candidate or null if they are |
| // incompatible. |
| |
| // If either is invalid, the result is. |
| if (!left->is_valid()) return left; |
| if (!right->is_valid()) return right; |
| |
| // If they have the same value, the result is the same. (Exception: |
| // bidirectional frames cannot have constants or copies.) If either |
| // is unsynced, the result is. |
| if (left->is_memory() && right->is_memory()) return left; |
| |
| if (left->is_register() && right->is_register() && |
| left->reg().is(right->reg())) { |
| if (!left->is_synced()) { |
| return left; |
| } else { |
| return right; |
| } |
| } |
| |
| if (direction_ == FORWARD_ONLY && |
| left->is_constant() && |
| right->is_constant() && |
| left->handle().is_identical_to(right->handle())) { |
| if (!left->is_synced()) { |
| return left; |
| } else { |
| return right; |
| } |
| } |
| |
| if (direction_ == FORWARD_ONLY && |
| left->is_copy() && |
| right->is_copy() && |
| left->index() == right->index()) { |
| if (!left->is_synced()) { |
| return left; |
| } else { |
| return right; |
| } |
| } |
| |
| // Otherwise they are incompatible and we will reallocate them. |
| return NULL; |
| } |
| |
| |
| void JumpTarget::ComputeEntryFrame(int mergable_elements) { |
| // Given: a collection of frames reaching by forward CFG edges |
| // (including the code generator's current frame) and the |
| // directionality of the block. Compute: an entry frame for the |
| // block. |
| |
| // Choose an initial frame, either the code generator's current |
| // frame if there is one, or the first reaching frame if not. |
| VirtualFrame* initial_frame = cgen_->frame(); |
| int start_index = 0; // Begin iteration with the 1st reaching frame. |
| if (initial_frame == NULL) { |
| initial_frame = reaching_frames_[0]; |
| start_index = 1; // Begin iteration with the 2nd reaching frame. |
| } |
| |
| // A list of pointers to frame elements in the entry frame. NULL |
| // indicates that the element has not yet been determined. |
| int length = initial_frame->elements_.length(); |
| List<FrameElement*> elements(length); |
| |
| // Convert the number of mergable elements (counted from the top |
| // down) to a frame high-water mark (counted from the bottom up). |
| // Elements strictly above the high-water index will be mergable in |
| // entry frames for bidirectional jump targets. |
| int high_water_mark = (mergable_elements == kAllElements) |
| ? VirtualFrame::kIllegalIndex // All frame indices are above this. |
| : length - mergable_elements - 1; // Top index if m_e == 0. |
| |
| // Initially populate the list of elements based on the initial |
| // frame. |
| for (int i = 0; i < length; i++) { |
| FrameElement element = initial_frame->elements_[i]; |
| // We do not allow copies or constants in bidirectional frames. |
| if (direction_ == BIDIRECTIONAL && |
| i > high_water_mark && |
| (element.is_constant() || element.is_copy())) { |
| elements.Add(NULL); |
| } else { |
| elements.Add(&initial_frame->elements_[i]); |
| } |
| } |
| |
| // Compute elements based on the other reaching frames. |
| if (start_index < reaching_frames_.length()) { |
| for (int i = 0; i < length; i++) { |
| for (int j = start_index; j < reaching_frames_.length(); j++) { |
| FrameElement* element = elements[i]; |
| |
| // Element computation is monotonic: new information will not |
| // change our decision about undetermined or invalid elements. |
| if (element == NULL || !element->is_valid()) break; |
| |
| elements[i] = Combine(element, &reaching_frames_[j]->elements_[i]); |
| } |
| } |
| } |
| |
| // Compute the registers already reserved by values in the frame. |
| // Count the reserved registers to avoid using them. |
| RegisterFile frame_registers = RegisterAllocator::Reserved(); |
| for (int i = 0; i < length; i++) { |
| FrameElement* element = elements[i]; |
| if (element != NULL && element->is_register()) { |
| frame_registers.Use(element->reg()); |
| } |
| } |
| |
| // Build the new frame. The frame already has memory elements for |
| // the parameters (including the receiver) and the return address. |
| // We will fill it up with memory elements. |
| entry_frame_ = new VirtualFrame(cgen_); |
| while (entry_frame_->elements_.length() < length) { |
| entry_frame_->elements_.Add(FrameElement::MemoryElement()); |
| } |
| |
| |
| // Copy the already-determined frame elements to the entry frame, |
| // and allocate any still-undetermined frame elements to registers |
| // or memory, from the top down. |
| for (int i = length - 1; i >= 0; i--) { |
| if (elements[i] == NULL) { |
| // If the value is synced on all frames, put it in memory. This |
| // costs nothing at the merge code but will incur a |
| // memory-to-register move when the value is needed later. |
| bool is_synced = initial_frame->elements_[i].is_synced(); |
| int j = start_index; |
| while (is_synced && j < reaching_frames_.length()) { |
| is_synced = reaching_frames_[j]->elements_[i].is_synced(); |
| j++; |
| } |
| // There is nothing to be done if the elements are all synced. |
| // It is already recorded as a memory element. |
| if (is_synced) continue; |
| |
| // Choose an available register. Prefer ones that the element |
| // is already occupying on some reaching frame. |
| RegisterFile candidate_registers; |
| int max_count = kMinInt; |
| int best_reg_code = no_reg.code_; |
| |
| // Consider the initial frame. |
| FrameElement element = initial_frame->elements_[i]; |
| if (element.is_register() && |
| !frame_registers.is_used(element.reg())) { |
| candidate_registers.Use(element.reg()); |
| max_count = 1; |
| best_reg_code = element.reg().code(); |
| } |
| // Consider the other frames. |
| for (int j = start_index; j < reaching_frames_.length(); j++) { |
| element = reaching_frames_[j]->elements_[i]; |
| if (element.is_register() && |
| !frame_registers.is_used(element.reg())) { |
| candidate_registers.Use(element.reg()); |
| if (candidate_registers.count(element.reg()) > max_count) { |
| max_count = candidate_registers.count(element.reg()); |
| best_reg_code = element.reg().code(); |
| } |
| } |
| } |
| // If there was no preferred choice consider any free register. |
| if (best_reg_code == no_reg.code_) { |
| for (int j = 0; j < kNumRegisters; j++) { |
| if (!frame_registers.is_used(j)) { |
| best_reg_code = j; |
| break; |
| } |
| } |
| } |
| |
| // If there was a register choice, use it. If not do nothing |
| // (the element is already recorded as in memory) |
| if (best_reg_code != no_reg.code_) { |
| Register reg = { best_reg_code }; |
| frame_registers.Use(reg); |
| entry_frame_->elements_[i] = |
| FrameElement::RegisterElement(reg, |
| FrameElement::NOT_SYNCED); |
| } |
| } else { |
| // The element is already determined. |
| entry_frame_->elements_[i] = *elements[i]; |
| } |
| } |
| |
| // Fill in the other fields of the entry frame. |
| entry_frame_->local_count_ = initial_frame->local_count_; |
| entry_frame_->frame_pointer_ = initial_frame->frame_pointer_; |
| |
| // The stack pointer is at the highest synced element or the base of |
| // the expression stack. |
| int stack_pointer = length - 1; |
| while (stack_pointer >= entry_frame_->expression_base_index() && |
| !entry_frame_->elements_[stack_pointer].is_synced()) { |
| stack_pointer--; |
| } |
| entry_frame_->stack_pointer_ = stack_pointer; |
| |
| // Unuse the reserved registers---they do not actually appear in |
| // the entry frame. |
| RegisterAllocator::UnuseReserved(&frame_registers); |
| entry_frame_->frame_registers_ = frame_registers; |
| } |
| |
| |
| void JumpTarget::Jump(Result* arg) { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->has_valid_frame()); |
| |
| cgen_->frame()->Push(arg); |
| Jump(); |
| } |
| |
| |
| void JumpTarget::Jump(Result* arg0, Result* arg1) { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->has_valid_frame()); |
| |
| cgen_->frame()->Push(arg0); |
| cgen_->frame()->Push(arg1); |
| Jump(); |
| } |
| |
| |
| void JumpTarget::Jump(Result* arg0, Result* arg1, Result* arg2) { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->has_valid_frame()); |
| |
| cgen_->frame()->Push(arg0); |
| cgen_->frame()->Push(arg1); |
| cgen_->frame()->Push(arg2); |
| Jump(); |
| } |
| |
| |
| #ifdef DEBUG |
| #define DECLARE_ARGCHECK_VARS(name) \ |
| Result::Type name##_type = name->type(); \ |
| Register name##_reg = name->is_register() ? name->reg() : no_reg |
| |
| #define ASSERT_ARGCHECK(name) \ |
| ASSERT(name->type() == name##_type); \ |
| ASSERT(!name->is_register() || name->reg().is(name##_reg)) |
| |
| #else |
| #define DECLARE_ARGCHECK_VARS(name) do {} while (false) |
| |
| #define ASSERT_ARGCHECK(name) do {} while (false) |
| #endif |
| |
| void JumpTarget::Branch(Condition cc, Result* arg, Hint hint) { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->has_valid_frame()); |
| |
| // We want to check that non-frame registers at the call site stay in |
| // the same registers on the fall-through branch. |
| DECLARE_ARGCHECK_VARS(arg); |
| |
| cgen_->frame()->Push(arg); |
| Branch(cc, hint); |
| *arg = cgen_->frame()->Pop(); |
| |
| ASSERT_ARGCHECK(arg); |
| } |
| |
| |
| void JumpTarget::Branch(Condition cc, Result* arg0, Result* arg1, Hint hint) { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->frame() != NULL); |
| |
| // We want to check that non-frame registers at the call site stay in |
| // the same registers on the fall-through branch. |
| DECLARE_ARGCHECK_VARS(arg0); |
| DECLARE_ARGCHECK_VARS(arg1); |
| |
| cgen_->frame()->Push(arg0); |
| cgen_->frame()->Push(arg1); |
| Branch(cc, hint); |
| *arg1 = cgen_->frame()->Pop(); |
| *arg0 = cgen_->frame()->Pop(); |
| |
| ASSERT_ARGCHECK(arg0); |
| ASSERT_ARGCHECK(arg1); |
| } |
| |
| |
| void JumpTarget::Branch(Condition cc, |
| Result* arg0, |
| Result* arg1, |
| Result* arg2, |
| Hint hint) { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->frame() != NULL); |
| |
| // We want to check that non-frame registers at the call site stay in |
| // the same registers on the fall-through branch. |
| DECLARE_ARGCHECK_VARS(arg0); |
| DECLARE_ARGCHECK_VARS(arg1); |
| DECLARE_ARGCHECK_VARS(arg2); |
| |
| cgen_->frame()->Push(arg0); |
| cgen_->frame()->Push(arg1); |
| cgen_->frame()->Push(arg2); |
| Branch(cc, hint); |
| *arg2 = cgen_->frame()->Pop(); |
| *arg1 = cgen_->frame()->Pop(); |
| *arg0 = cgen_->frame()->Pop(); |
| |
| ASSERT_ARGCHECK(arg0); |
| ASSERT_ARGCHECK(arg1); |
| ASSERT_ARGCHECK(arg2); |
| } |
| |
| |
| void JumpTarget::Branch(Condition cc, |
| Result* arg0, |
| Result* arg1, |
| Result* arg2, |
| Result* arg3, |
| Hint hint) { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->frame() != NULL); |
| |
| // We want to check that non-frame registers at the call site stay in |
| // the same registers on the fall-through branch. |
| DECLARE_ARGCHECK_VARS(arg0); |
| DECLARE_ARGCHECK_VARS(arg1); |
| DECLARE_ARGCHECK_VARS(arg2); |
| DECLARE_ARGCHECK_VARS(arg3); |
| |
| cgen_->frame()->Push(arg0); |
| cgen_->frame()->Push(arg1); |
| cgen_->frame()->Push(arg2); |
| cgen_->frame()->Push(arg3); |
| Branch(cc, hint); |
| *arg3 = cgen_->frame()->Pop(); |
| *arg2 = cgen_->frame()->Pop(); |
| *arg1 = cgen_->frame()->Pop(); |
| *arg0 = cgen_->frame()->Pop(); |
| |
| ASSERT_ARGCHECK(arg0); |
| ASSERT_ARGCHECK(arg1); |
| ASSERT_ARGCHECK(arg2); |
| ASSERT_ARGCHECK(arg3); |
| } |
| |
| #undef DECLARE_ARGCHECK_VARS |
| #undef ASSERT_ARGCHECK |
| |
| |
| void JumpTarget::Bind(Result* arg, int mergable_elements) { |
| ASSERT(cgen_ != NULL); |
| |
| if (cgen_->has_valid_frame()) { |
| cgen_->frame()->Push(arg); |
| } |
| Bind(mergable_elements); |
| *arg = cgen_->frame()->Pop(); |
| } |
| |
| |
| void JumpTarget::Bind(Result* arg0, Result* arg1, int mergable_elements) { |
| ASSERT(cgen_ != NULL); |
| |
| if (cgen_->has_valid_frame()) { |
| cgen_->frame()->Push(arg0); |
| cgen_->frame()->Push(arg1); |
| } |
| Bind(mergable_elements); |
| *arg1 = cgen_->frame()->Pop(); |
| *arg0 = cgen_->frame()->Pop(); |
| } |
| |
| |
| void JumpTarget::Bind(Result* arg0, |
| Result* arg1, |
| Result* arg2, |
| int mergable_elements) { |
| ASSERT(cgen_ != NULL); |
| |
| if (cgen_->has_valid_frame()) { |
| cgen_->frame()->Push(arg0); |
| cgen_->frame()->Push(arg1); |
| cgen_->frame()->Push(arg2); |
| } |
| Bind(mergable_elements); |
| *arg2 = cgen_->frame()->Pop(); |
| *arg1 = cgen_->frame()->Pop(); |
| *arg0 = cgen_->frame()->Pop(); |
| } |
| |
| |
| void JumpTarget::Bind(Result* arg0, |
| Result* arg1, |
| Result* arg2, |
| Result* arg3, |
| int mergable_elements) { |
| ASSERT(cgen_ != NULL); |
| |
| if (cgen_->has_valid_frame()) { |
| cgen_->frame()->Push(arg0); |
| cgen_->frame()->Push(arg1); |
| cgen_->frame()->Push(arg2); |
| cgen_->frame()->Push(arg3); |
| } |
| Bind(mergable_elements); |
| *arg3 = cgen_->frame()->Pop(); |
| *arg2 = cgen_->frame()->Pop(); |
| *arg1 = cgen_->frame()->Pop(); |
| *arg0 = cgen_->frame()->Pop(); |
| } |
| |
| |
| void JumpTarget::AddReachingFrame(VirtualFrame* frame) { |
| ASSERT(reaching_frames_.length() == merge_labels_.length()); |
| Label fresh; |
| merge_labels_.Add(fresh); |
| reaching_frames_.Add(frame); |
| } |
| |
| |
| // ------------------------------------------------------------------------- |
| // BreakTarget implementation. |
| |
| void BreakTarget::Initialize(CodeGenerator* cgen, Directionality direction) { |
| JumpTarget::Initialize(cgen, direction); |
| ASSERT(cgen_->has_valid_frame()); |
| expected_height_ = cgen_->frame()->height(); |
| } |
| |
| |
| void BreakTarget::CopyTo(BreakTarget* destination) { |
| ASSERT(destination != NULL); |
| destination->cgen_ = cgen_; |
| destination->masm_ = masm_; |
| destination->direction_ = direction_; |
| destination->reaching_frames_.Clear(); |
| destination->merge_labels_.Clear(); |
| ASSERT(reaching_frames_.length() == merge_labels_.length()); |
| for (int i = 0; i < reaching_frames_.length(); i++) { |
| destination->reaching_frames_.Add(reaching_frames_[i]); |
| destination->merge_labels_.Add(merge_labels_[i]); |
| } |
| destination->entry_frame_ = entry_frame_; |
| destination->entry_label_ = entry_label_; |
| destination->is_bound_ = is_bound_; |
| destination->is_linked_ = is_linked_; |
| destination->expected_height_ = expected_height_; |
| } |
| |
| |
| void BreakTarget::Jump() { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->has_valid_frame()); |
| |
| // This is a break target so drop leftover statement state from the |
| // frame before merging. |
| cgen_->frame()->ForgetElements(cgen_->frame()->height() - expected_height_); |
| JumpTarget::Jump(); |
| } |
| |
| |
| void BreakTarget::Branch(Condition cc, Hint hint) { |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->has_valid_frame()); |
| |
| int count = cgen_->frame()->height() - expected_height_; |
| if (count > 0) { |
| // We negate and branch here rather than using |
| // JumpTarget::Branch's negate and branch. This gives us a hook |
| // to remove statement state from the frame. |
| JumpTarget fall_through(cgen_); |
| // Branch to fall through will not negate, because it is a |
| // forward-only target. |
| fall_through.Branch(NegateCondition(cc), NegateHint(hint)); |
| Jump(); // May emit merge code here. |
| fall_through.Bind(); |
| } else { |
| JumpTarget::Branch(cc, hint); |
| } |
| } |
| |
| |
| void BreakTarget::Bind(int mergable_elements) { |
| #ifdef DEBUG |
| ASSERT(mergable_elements == kAllElements); |
| ASSERT(cgen_ != NULL); |
| for (int i = 0; i < reaching_frames_.length(); i++) { |
| ASSERT(reaching_frames_[i]->height() == expected_height_); |
| } |
| #endif |
| |
| // This is a break target so drop leftover statement state from the |
| // frame before merging. |
| if (cgen_->has_valid_frame()) { |
| int count = cgen_->frame()->height() - expected_height_; |
| cgen_->frame()->ForgetElements(count); |
| } |
| JumpTarget::Bind(mergable_elements); |
| } |
| |
| |
| // ------------------------------------------------------------------------- |
| // ShadowTarget implementation. |
| |
| ShadowTarget::ShadowTarget(BreakTarget* shadowed) { |
| ASSERT(shadowed != NULL); |
| other_target_ = shadowed; |
| |
| #ifdef DEBUG |
| is_shadowing_ = true; |
| #endif |
| // While shadowing this shadow target saves the state of the original. |
| shadowed->CopyTo(this); |
| |
| // The original's state is reset. We do not Unuse it because that |
| // would delete the expected frame and assert that the target is not |
| // linked. |
| shadowed->Reset(); |
| ASSERT(cgen_ != NULL); |
| ASSERT(cgen_->has_valid_frame()); |
| shadowed->set_expected_height(cgen_->frame()->height()); |
| |
| // Setting the code generator to null prevents the shadow target from |
| // being used until shadowing stops. |
| cgen_ = NULL; |
| masm_ = NULL; |
| } |
| |
| |
| void ShadowTarget::StopShadowing() { |
| ASSERT(is_shadowing_); |
| |
| // This target does not have a valid code generator yet. |
| cgen_ = other_target_->code_generator(); |
| ASSERT(cgen_ != NULL); |
| masm_ = cgen_->masm(); |
| |
| // The states of this target, which was shadowed, and the original |
| // target, which was shadowing, are swapped. |
| BreakTarget temp; |
| other_target_->CopyTo(&temp); |
| CopyTo(other_target_); |
| temp.CopyTo(this); |
| temp.Reset(); // So the destructor does not deallocate virtual frames. |
| |
| #ifdef DEBUG |
| is_shadowing_ = false; |
| #endif |
| } |
| |
| |
| } } // namespace v8::internal |