From 4f6a4a83392af3e23c4dadbae3d42e21a4f47223 Mon Sep 17 00:00:00 2001 From: "whesse@chromium.org" Date: Mon, 22 Jun 2009 08:08:47 +0000 Subject: [PATCH] X64 implementation: if-then-else Review URL: http://codereview.chromium.org/141030 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@2229 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/x64/assembler-x64.cc | 13 -- src/x64/codegen-x64.cc | 204 +++++++++++++++++++-- src/x64/jump-target-x64.cc | 341 +++++++++++++++++++++++++++++++++++ src/x64/virtual-frame-x64.cc | 4 + src/x64/virtual-frame-x64.h | 7 +- 5 files changed, 531 insertions(+), 38 deletions(-) diff --git a/src/x64/assembler-x64.cc b/src/x64/assembler-x64.cc index 55d228ff8..d4ffb20b1 100644 --- a/src/x64/assembler-x64.cc +++ b/src/x64/assembler-x64.cc @@ -1886,17 +1886,4 @@ void CallIC::GenerateNormal(MacroAssembler* a, int b) { UNIMPLEMENTED(); } -void JumpTarget::DoBind() { - // UNIMPLEMENTED(); -} - -void JumpTarget::DoBranch(Condition a, Hint b) { - UNIMPLEMENTED(); -} - -void JumpTarget::DoJump() { - UNIMPLEMENTED(); -} - - } } // namespace v8::internal diff --git a/src/x64/codegen-x64.cc b/src/x64/codegen-x64.cc index 3f9d5411a..6ba120f33 100644 --- a/src/x64/codegen-x64.cc +++ b/src/x64/codegen-x64.cc @@ -103,14 +103,38 @@ void CodeGenerator::DeclareGlobals(Handle a) { void CodeGenerator::TestCodeGenerator() { // Compile a function from a string, and run it. + + // Set flags appropriately for this stage of implementation. + // TODO(X64): Make ic and lazy compilation work, and stop disabling them. + // These settings stick - remove them when we don't want them anymore. +#ifdef DEBUG + FLAG_print_builtin_source = true; + FLAG_print_builtin_ast = true; +#endif + FLAG_use_ic = false; + FLAG_lazy = false; + Handle test_function = Compiler::Compile( Factory::NewStringFromAscii(CStrVector( - "39;" + "// Put all code in anonymous function to avoid global scope.\n" "(function(){" - "function foo(x, y){var w; y = x; x = w; w = y; y = x; return w;};" - "function bar(x, y, zee){return zee;};" - "foo(2,3);" - "return foo(bar(foo(1,3), 42, 47), foo( -25.3, 2));" + " function test_if_then_else(x, y, z){" + " if (x) {" + " x = y;" + " } else {" + " x = z;" + " }" + " return x;" + " }" + " function test_local_variables(x, y){" + " var w; y = x; x = w; w = y; y = x; return w;" + " };" + " test_local_variables(2,3);" + " function test_nesting_calls(x, y, zee){return zee;};" + " test_local_variables(" + " test_nesting_calls(test_local_variables(1,3), 42, 47)," + " test_local_variables(-25.3, 2));" + " return test_if_then_else(1, 47, 39);" "})()")), Factory::NewStringFromAscii(CStrVector("CodeGeneratorTestScript")), 0, @@ -417,10 +441,104 @@ void CodeGenerator::VisitEmptyStatement(EmptyStatement* a) { UNIMPLEMENTED(); } -void CodeGenerator::VisitIfStatement(IfStatement* a) { - UNIMPLEMENTED(); + +void CodeGenerator::VisitIfStatement(IfStatement* node) { + ASSERT(!in_spilled_code()); + Comment cmnt(masm_, "[ IfStatement"); + // Generate different code depending on which parts of the if statement + // are present or not. + bool has_then_stm = node->HasThenStatement(); + bool has_else_stm = node->HasElseStatement(); + + CodeForStatementPosition(node); + JumpTarget exit; + if (has_then_stm && has_else_stm) { + JumpTarget then; + JumpTarget else_; + ControlDestination dest(&then, &else_, true); + LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &dest, true); + + if (dest.false_was_fall_through()) { + // The else target was bound, so we compile the else part first. + Visit(node->else_statement()); + + // We may have dangling jumps to the then part. + if (then.is_linked()) { + if (has_valid_frame()) exit.Jump(); + then.Bind(); + Visit(node->then_statement()); + } + } else { + // The then target was bound, so we compile the then part first. + Visit(node->then_statement()); + + if (else_.is_linked()) { + if (has_valid_frame()) exit.Jump(); + else_.Bind(); + Visit(node->else_statement()); + } + } + + } else if (has_then_stm) { + ASSERT(!has_else_stm); + JumpTarget then; + ControlDestination dest(&then, &exit, true); + LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &dest, true); + + if (dest.false_was_fall_through()) { + // The exit label was bound. We may have dangling jumps to the + // then part. + if (then.is_linked()) { + exit.Unuse(); + exit.Jump(); + then.Bind(); + Visit(node->then_statement()); + } + } else { + // The then label was bound. + Visit(node->then_statement()); + } + + } else if (has_else_stm) { + ASSERT(!has_then_stm); + JumpTarget else_; + ControlDestination dest(&exit, &else_, false); + LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &dest, true); + + if (dest.true_was_fall_through()) { + // The exit label was bound. We may have dangling jumps to the + // else part. + if (else_.is_linked()) { + exit.Unuse(); + exit.Jump(); + else_.Bind(); + Visit(node->else_statement()); + } + } else { + // The else label was bound. + Visit(node->else_statement()); + } + + } else { + ASSERT(!has_then_stm && !has_else_stm); + // We only care about the condition's side effects (not its value + // or control flow effect). LoadCondition is called without + // forcing control flow. + ControlDestination dest(&exit, &exit, true); + LoadCondition(node->condition(), NOT_INSIDE_TYPEOF, &dest, false); + if (!dest.is_used()) { + // We got a value on the frame rather than (or in addition to) + // control flow. + frame_->Drop(); + } + } + + if (exit.is_linked()) { + exit.Bind(); + } } + void CodeGenerator::VisitContinueStatement(ContinueStatement* a) { UNIMPLEMENTED(); } @@ -993,7 +1111,7 @@ void CodeGenerator::LoadCondition(Expression* x, if (force_control && !dest->is_used()) { // Convert the TOS value into flow to the control destination. // TODO(X64): Make control flow to control destinations work. - // ToBoolean(dest); + ToBoolean(dest); } ASSERT(!(force_control && !dest->is_used())); @@ -1001,6 +1119,64 @@ void CodeGenerator::LoadCondition(Expression* x, } +class ToBooleanStub: public CodeStub { + public: + ToBooleanStub() { } + + void Generate(MacroAssembler* masm); + + private: + Major MajorKey() { return ToBoolean; } + int MinorKey() { return 0; } +}; + + +// ECMA-262, section 9.2, page 30: ToBoolean(). Pop the top of stack and +// convert it to a boolean in the condition code register or jump to +// 'false_target'/'true_target' as appropriate. +void CodeGenerator::ToBoolean(ControlDestination* dest) { + Comment cmnt(masm_, "[ ToBoolean"); + + // The value to convert should be popped from the frame. + Result value = frame_->Pop(); + value.ToRegister(); + // Fast case checks. + + // 'false' => false. + __ movq(kScratchRegister, Factory::false_value(), RelocInfo::EMBEDDED_OBJECT); + __ cmpq(value.reg(), kScratchRegister); + dest->false_target()->Branch(equal); + + // 'true' => true. + __ movq(kScratchRegister, Factory::true_value(), RelocInfo::EMBEDDED_OBJECT); + __ cmpq(value.reg(), kScratchRegister); + dest->true_target()->Branch(equal); + + // 'undefined' => false. + __ movq(kScratchRegister, + Factory::undefined_value(), + RelocInfo::EMBEDDED_OBJECT); + __ cmpq(value.reg(), kScratchRegister); + dest->false_target()->Branch(equal); + + // Smi => false iff zero. + ASSERT(kSmiTag == 0); + __ testq(value.reg(), value.reg()); + dest->false_target()->Branch(zero); + __ testq(value.reg(), Immediate(kSmiTagMask)); + dest->true_target()->Branch(zero); + + // Call the stub for all other cases. + frame_->Push(&value); // Undo the Pop() from above. + ToBooleanStub stub; + Result temp = frame_->CallStub(&stub, 1); + // Convert the result to a condition code. + __ testq(temp.reg(), temp.reg()); + temp.Unuse(); + dest->Split(not_equal); +} + + void CodeGenerator::LoadUnsafeSmi(Register target, Handle value) { UNIMPLEMENTED(); // TODO(X64): Implement security policy for loads of smis. @@ -1526,18 +1702,6 @@ void CodeGenerator::LoadGlobalReceiver() { // Stub classes have public member named masm, not masm_. #define __ ACCESS_MASM(masm) -class ToBooleanStub: public CodeStub { - public: - ToBooleanStub() { } - - void Generate(MacroAssembler* masm); - - private: - Major MajorKey() { return ToBoolean; } - int MinorKey() { return 0; } -}; - - void ToBooleanStub::Generate(MacroAssembler* masm) { Label false_result, true_result, not_string; __ movq(rax, Operand(rsp, 1 * kPointerSize)); diff --git a/src/x64/jump-target-x64.cc b/src/x64/jump-target-x64.cc index 209aa2d30..b804044ec 100644 --- a/src/x64/jump-target-x64.cc +++ b/src/x64/jump-target-x64.cc @@ -25,3 +25,344 @@ // (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-inl.h" +#include "jump-target-inl.h" +#include "register-allocator-inl.h" + +namespace v8 { +namespace internal { + +// ------------------------------------------------------------------------- +// JumpTarget implementation. + +#define __ ACCESS_MASM(cgen()->masm()) + +void JumpTarget::DoJump() { + ASSERT(cgen()->has_valid_frame()); + // Live non-frame registers are not allowed at unconditional jumps + // because we have no way of invalidating the corresponding results + // which are still live in the C++ code. + ASSERT(cgen()->HasValidEntryRegisters()); + + if (is_bound()) { + // Backward jump. There is an expected frame to merge to. + ASSERT(direction_ == BIDIRECTIONAL); + cgen()->frame()->PrepareMergeTo(entry_frame_); + cgen()->frame()->MergeTo(entry_frame_); + cgen()->DeleteFrame(); + __ jmp(&entry_label_); + } else if (entry_frame_ != NULL) { + // Forward jump with a preconfigured entry frame. Assert the + // current frame matches the expected one and jump to the block. + ASSERT(cgen()->frame()->Equals(entry_frame_)); + cgen()->DeleteFrame(); + __ jmp(&entry_label_); + } else { + // Forward jump. Remember the current frame and emit a jump to + // its merge code. + AddReachingFrame(cgen()->frame()); + RegisterFile empty; + cgen()->SetFrame(NULL, &empty); + __ jmp(&merge_labels_.last()); + } +} + + +void JumpTarget::DoBranch(Condition cc, Hint b) { + ASSERT(cgen() != NULL); + ASSERT(cgen()->has_valid_frame()); + + if (is_bound()) { + ASSERT(direction_ == BIDIRECTIONAL); + // Backward branch. We have an expected frame to merge to on the + // backward edge. + + // Swap the current frame for a copy (we do the swapping to get + // the off-frame registers off the fall through) to use for the + // branch. + VirtualFrame* fall_through_frame = cgen()->frame(); + VirtualFrame* branch_frame = new VirtualFrame(fall_through_frame); + RegisterFile non_frame_registers; + cgen()->SetFrame(branch_frame, &non_frame_registers); + + // Check if we can avoid merge code. + cgen()->frame()->PrepareMergeTo(entry_frame_); + if (cgen()->frame()->Equals(entry_frame_)) { + // Branch right in to the block. + cgen()->DeleteFrame(); + __ j(cc, &entry_label_); + cgen()->SetFrame(fall_through_frame, &non_frame_registers); + return; + } + + // Check if we can reuse existing merge code. + for (int i = 0; i < reaching_frames_.length(); i++) { + if (reaching_frames_[i] != NULL && + cgen()->frame()->Equals(reaching_frames_[i])) { + // Branch to the merge code. + cgen()->DeleteFrame(); + __ j(cc, &merge_labels_[i]); + cgen()->SetFrame(fall_through_frame, &non_frame_registers); + return; + } + } + + // To emit the merge code here, we negate the condition and branch + // around the merge code on the fall through path. + Label original_fall_through; + __ j(NegateCondition(cc), &original_fall_through); + cgen()->frame()->MergeTo(entry_frame_); + cgen()->DeleteFrame(); + __ jmp(&entry_label_); + cgen()->SetFrame(fall_through_frame, &non_frame_registers); + __ bind(&original_fall_through); + + } else if (entry_frame_ != NULL) { + // Forward branch with a preconfigured entry frame. Assert the + // current frame matches the expected one and branch to the block. + ASSERT(cgen()->frame()->Equals(entry_frame_)); + // Explicitly use the macro assembler instead of __ as forward + // branches are expected to be a fixed size (no inserted + // coverage-checking instructions please). This is used in + // Reference::GetValue. + cgen()->masm()->j(cc, &entry_label_); + + } else { + // Forward branch. A copy of the current frame is remembered and + // a branch to the merge code is emitted. Explicitly use the + // macro assembler instead of __ as forward branches are expected + // to be a fixed size (no inserted coverage-checking instructions + // please). This is used in Reference::GetValue. + AddReachingFrame(new VirtualFrame(cgen()->frame())); + cgen()->masm()->j(cc, &merge_labels_.last()); + } +} + + +void JumpTarget::Call() { + // Call is used to push the address of the catch block on the stack as + // a return address when compiling try/catch and try/finally. We + // fully spill the frame before making the call. The expected frame + // at the label (which should be the only one) is the spilled current + // frame plus an in-memory return address. The "fall-through" frame + // at the return site is the spilled current frame. + ASSERT(cgen() != NULL); + ASSERT(cgen()->has_valid_frame()); + // There are no non-frame references across the call. + ASSERT(cgen()->HasValidEntryRegisters()); + ASSERT(!is_linked()); + + cgen()->frame()->SpillAll(); + VirtualFrame* target_frame = new VirtualFrame(cgen()->frame()); + target_frame->Adjust(1); + // We do not expect a call with a preconfigured entry frame. + ASSERT(entry_frame_ == NULL); + AddReachingFrame(target_frame); + __ call(&merge_labels_.last()); +} + + +void JumpTarget::DoBind() { + ASSERT(cgen() != NULL); + ASSERT(!is_bound()); + + // Live non-frame registers are not allowed at the start of a basic + // block. + ASSERT(!cgen()->has_valid_frame() || cgen()->HasValidEntryRegisters()); + + // Fast case: the jump target was manually configured with an entry + // frame to use. + if (entry_frame_ != NULL) { + // Assert no reaching frames to deal with. + ASSERT(reaching_frames_.is_empty()); + ASSERT(!cgen()->has_valid_frame()); + + RegisterFile empty; + if (direction_ == BIDIRECTIONAL) { + // Copy the entry frame so the original can be used for a + // possible backward jump. + cgen()->SetFrame(new VirtualFrame(entry_frame_), &empty); + } else { + // Take ownership of the entry frame. + cgen()->SetFrame(entry_frame_, &empty); + entry_frame_ = NULL; + } + __ bind(&entry_label_); + return; + } + + if (!is_linked()) { + ASSERT(cgen()->has_valid_frame()); + if (direction_ == FORWARD_ONLY) { + // Fast case: no forward jumps and no possible backward jumps. + // The stack pointer can be floating above the top of the + // virtual frame before the bind. Afterward, it should not. + VirtualFrame* frame = cgen()->frame(); + int difference = frame->stack_pointer_ - (frame->element_count() - 1); + if (difference > 0) { + frame->stack_pointer_ -= difference; + __ addq(rsp, Immediate(difference * kPointerSize)); + } + } else { + ASSERT(direction_ == BIDIRECTIONAL); + // Fast case: no forward jumps, possible backward ones. Remove + // constants and copies above the watermark on the fall-through + // frame and use it as the entry frame. + cgen()->frame()->MakeMergable(); + entry_frame_ = new VirtualFrame(cgen()->frame()); + } + __ bind(&entry_label_); + return; + } + + if (direction_ == FORWARD_ONLY && + !cgen()->has_valid_frame() && + reaching_frames_.length() == 1) { + // Fast case: no fall-through, a single forward jump, and no + // possible backward jumps. Pick up the only reaching frame, take + // ownership of it, and use it for the block about to be emitted. + VirtualFrame* frame = reaching_frames_[0]; + RegisterFile empty; + cgen()->SetFrame(frame, &empty); + reaching_frames_[0] = NULL; + __ bind(&merge_labels_[0]); + + // The stack pointer can be floating above the top of the + // virtual frame before the bind. Afterward, it should not. + int difference = frame->stack_pointer_ - (frame->element_count() - 1); + if (difference > 0) { + frame->stack_pointer_ -= difference; + __ addq(rsp, Immediate(difference * kPointerSize)); + } + + __ bind(&entry_label_); + return; + } + + // If there is a current frame, record it as the fall-through. It + // is owned by the reaching frames for now. + bool had_fall_through = false; + if (cgen()->has_valid_frame()) { + had_fall_through = true; + AddReachingFrame(cgen()->frame()); // Return value ignored. + RegisterFile empty; + cgen()->SetFrame(NULL, &empty); + } + + // Compute the frame to use for entry to the block. + ComputeEntryFrame(); + + // Some moves required to merge to an expected frame require purely + // frame state changes, and do not require any code generation. + // Perform those first to increase the possibility of finding equal + // frames below. + for (int i = 0; i < reaching_frames_.length(); i++) { + if (reaching_frames_[i] != NULL) { + reaching_frames_[i]->PrepareMergeTo(entry_frame_); + } + } + + if (is_linked()) { + // There were forward jumps. Handle merging the reaching frames + // to the entry frame. + + // Loop over the (non-null) reaching frames and process any that + // need merge code. Iterate backwards through the list to handle + // the fall-through frame first. Set frames that will be + // processed after 'i' to NULL if we want to avoid processing + // them. + for (int i = reaching_frames_.length() - 1; i >= 0; i--) { + VirtualFrame* frame = reaching_frames_[i]; + + if (frame != NULL) { + // Does the frame (probably) need merge code? + if (!frame->Equals(entry_frame_)) { + // We could have a valid frame as the fall through to the + // binding site or as the fall through from a previous merge + // code block. Jump around the code we are about to + // generate. + if (cgen()->has_valid_frame()) { + cgen()->DeleteFrame(); + __ jmp(&entry_label_); + } + // Pick up the frame for this block. Assume ownership if + // there cannot be backward jumps. + RegisterFile empty; + if (direction_ == BIDIRECTIONAL) { + cgen()->SetFrame(new VirtualFrame(frame), &empty); + } else { + cgen()->SetFrame(frame, &empty); + reaching_frames_[i] = NULL; + } + __ bind(&merge_labels_[i]); + + // Loop over the remaining (non-null) reaching frames, + // looking for any that can share merge code with this one. + for (int j = 0; j < i; j++) { + VirtualFrame* other = reaching_frames_[j]; + if (other != NULL && other->Equals(cgen()->frame())) { + // Set the reaching frame element to null to avoid + // processing it later, and then bind its entry label. + reaching_frames_[j] = NULL; + __ bind(&merge_labels_[j]); + } + } + + // Emit the merge code. + cgen()->frame()->MergeTo(entry_frame_); + } else if (i == reaching_frames_.length() - 1 && had_fall_through) { + // If this is the fall through frame, and it didn't need + // merge code, we need to pick up the frame so we can jump + // around subsequent merge blocks if necessary. + RegisterFile empty; + cgen()->SetFrame(frame, &empty); + reaching_frames_[i] = NULL; + } + } + } + + // The code generator may not have a current frame if there was no + // fall through and none of the reaching frames needed merging. + // In that case, clone the entry frame as the current frame. + if (!cgen()->has_valid_frame()) { + RegisterFile empty; + cgen()->SetFrame(new VirtualFrame(entry_frame_), &empty); + } + + // There may be unprocessed reaching frames that did not need + // merge code. They will have unbound merge labels. Bind their + // merge labels to be the same as the entry label and deallocate + // them. + for (int i = 0; i < reaching_frames_.length(); i++) { + if (!merge_labels_[i].is_bound()) { + reaching_frames_[i] = NULL; + __ bind(&merge_labels_[i]); + } + } + + // There are non-NULL reaching frames with bound labels for each + // merge block, but only on backward targets. + } else { + // There were no forward jumps. There must be a current frame and + // this must be a bidirectional target. + ASSERT(reaching_frames_.length() == 1); + ASSERT(reaching_frames_[0] != NULL); + ASSERT(direction_ == BIDIRECTIONAL); + + // Use a copy of the reaching frame so the original can be saved + // for possible reuse as a backward merge block. + RegisterFile empty; + cgen()->SetFrame(new VirtualFrame(reaching_frames_[0]), &empty); + __ bind(&merge_labels_[0]); + cgen()->frame()->MergeTo(entry_frame_); + } + + __ bind(&entry_label_); +} + +#undef __ + + +} } // namespace v8::internal diff --git a/src/x64/virtual-frame-x64.cc b/src/x64/virtual-frame-x64.cc index 609540b72..ee54e4d3a 100644 --- a/src/x64/virtual-frame-x64.cc +++ b/src/x64/virtual-frame-x64.cc @@ -392,6 +392,10 @@ void VirtualFrame::StoreToFrameSlotAt(int index) { } +void VirtualFrame::MakeMergable() { + // UNIMPLEMENTED(); +} + void VirtualFrame::MergeTo(VirtualFrame* a) { UNIMPLEMENTED(); } diff --git a/src/x64/virtual-frame-x64.h b/src/x64/virtual-frame-x64.h index 2d3bf3022..d0aa26ff1 100644 --- a/src/x64/virtual-frame-x64.h +++ b/src/x64/virtual-frame-x64.h @@ -153,11 +153,8 @@ class VirtualFrame : public ZoneObject { void SyncRange(int begin, int end); // Make this frame so that an arbitrary frame of the same height can - // be merged to it. Copies and constants are removed from the - // topmost mergable_elements elements of the frame. A - // mergable_elements of JumpTarget::kAllElements indicates constants - // and copies are should be removed from the entire frame. - void MakeMergable(int mergable_elements); + // be merged to it. Copies and constants are removed from the frame. + void MakeMergable(); // Prepare this virtual frame for merging to an expected frame by // performing some state changes that do not require generating -- 2.34.1