CSE2410 Fall 2014 Bounce

// Copyright 2006-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 "bootstrapper.h"

#include "codegen-inl.h"

#include "debug.h"

#include "parser.h"

#include "register-allocator-inl.h"

#include "runtime.h"

#include "scopes.h"

namespace v8 { namespace internal {

#define __ masm_->

// -------------------------------------------------------------------------

// CodeGenState implementation.

CodeGenState::CodeGenState(CodeGenerator* owner)

    : owner_(owner),

      typeof_state_(NOT_INSIDE_TYPEOF),

      true_target_(NULL),

      false_target_(NULL),

      previous_(NULL) {

  owner_->set_state(this);

}

CodeGenState::CodeGenState(CodeGenerator* owner,

                           TypeofState typeof_state,

                           JumpTarget* true_target,

                           JumpTarget* false_target)

    : owner_(owner),

      typeof_state_(typeof_state),

      true_target_(true_target),

      false_target_(false_target),

      previous_(owner->state()) {

  owner_->set_state(this);

}

CodeGenState::~CodeGenState() {

  ASSERT(owner_->state() == this);

  owner_->set_state(previous_);

}

// -------------------------------------------------------------------------

// CodeGenerator implementation

CodeGenerator::CodeGenerator(int buffer_size, Handle<Script> script,

                             bool is_eval)

    : is_eval_(is_eval),

      script_(script),

      deferred_(8),

      masm_(new MacroAssembler(NULL, buffer_size)),

      scope_(NULL),

      frame_(NULL),

      allocator_(NULL),

      cc_reg_(al),

      state_(NULL),

      function_return_is_shadowed_(false),

      in_spilled_code_(false) {

}

// Calling conventions:

// fp: caller's frame pointer

// sp: stack pointer

// r1: called JS function

// cp: callee's context

void CodeGenerator::GenCode(FunctionLiteral* fun) {

  ZoneList<Statement*>* body = fun->body();

  // Initialize state.

  ASSERT(scope_ == NULL);

  scope_ = fun->scope();

  ASSERT(allocator_ == NULL);

  RegisterAllocator register_allocator(this);

  allocator_ = &register_allocator;

  ASSERT(frame_ == NULL);

  frame_ = new VirtualFrame(this);

  cc_reg_ = al;

  set_in_spilled_code(false);

  {

    CodeGenState state(this);

    // Entry:

    // Stack: receiver, arguments

    // lr: return address

    // fp: caller's frame pointer

    // sp: stack pointer

    // r1: called JS function

    // cp: callee's context

    allocator_->Initialize();

    frame_->Enter();

    // tos: code slot

#ifdef DEBUG

    if (strlen(FLAG_stop_at) > 0 &&

        fun->name()->IsEqualTo(CStrVector(FLAG_stop_at))) {

      frame_->SpillAll();

      __ stop("stop-at");

    }

#endif

    // Allocate space for locals and initialize them.

    frame_->AllocateStackSlots(scope_->num_stack_slots());

    // Initialize the function return target after the locals are set

    // up, because it needs the expected frame height from the frame.

    function_return_.Initialize(this, JumpTarget::BIDIRECTIONAL);

    function_return_is_shadowed_ = false;

    VirtualFrame::SpilledScope spilled_scope(this);

    if (scope_->num_heap_slots() > 0) {

      // Allocate local context.

      // Get outer context and create a new context based on it.

      __ ldr(r0, frame_->Function());

      frame_->EmitPush(r0);

      frame_->CallRuntime(Runtime::kNewContext, 1);  // r0 holds the result

      if (kDebug) {

        JumpTarget verified_true(this);

        __ cmp(r0, Operand(cp));

        verified_true.Branch(eq);

        __ stop("NewContext: r0 is expected to be the same as cp");

        verified_true.Bind();

      }

      // Update context local.

      __ str(cp, frame_->Context());

    }

    // TODO(1241774): Improve this code:

    // 1) only needed if we have a context

    // 2) no need to recompute context ptr every single time

    // 3) don't copy parameter operand code from SlotOperand!

    {

      Comment cmnt2(masm_, "[ copy context parameters into .context");

      // Note that iteration order is relevant here! If we have the same

      // parameter twice (e.g., function (x, y, x)), and that parameter

      // needs to be copied into the context, it must be the last argument

      // passed to the parameter that needs to be copied. This is a rare

      // case so we don't check for it, instead we rely on the copying

      // order: such a parameter is copied repeatedly into the same

      // context location and thus the last value is what is seen inside

      // the function.

      for (int i = 0; i < scope_->num_parameters(); i++) {

        Variable* par = scope_->parameter(i);

        Slot* slot = par->slot();

        if (slot != NULL && slot->type() == Slot::CONTEXT) {

          ASSERT(!scope_->is_global_scope());  // no parameters in global scope

          __ ldr(r1, frame_->ParameterAt(i));

          // Loads r2 with context; used below in RecordWrite.

          __ str(r1, SlotOperand(slot, r2));

          // Load the offset into r3.

          int slot_offset =

              FixedArray::kHeaderSize + slot->index() * kPointerSize;

          __ mov(r3, Operand(slot_offset));

          __ RecordWrite(r2, r3, r1);

        }

      }

    }

    // Store the arguments object.  This must happen after context

    // initialization because the arguments object may be stored in the

    // context.

    if (scope_->arguments() != NULL) {

      ASSERT(scope_->arguments_shadow() != NULL);

      Comment cmnt(masm_, "[ allocate arguments object");

      { Reference shadow_ref(this, scope_->arguments_shadow());

        { Reference arguments_ref(this, scope_->arguments());

          ArgumentsAccessStub stub(ArgumentsAccessStub::NEW_OBJECT);

          __ ldr(r2, frame_->Function());

          // The receiver is below the arguments, the return address,

          // and the frame pointer on the stack.

          const int kReceiverDisplacement = 2 + scope_->num_parameters();

          __ add(r1, fp, Operand(kReceiverDisplacement * kPointerSize));

          __ mov(r0, Operand(Smi::FromInt(scope_->num_parameters())));

          frame_->Adjust(3);

          __ stm(db_w, sp, r0.bit() | r1.bit() | r2.bit());

          frame_->CallStub(&stub, 3);

          frame_->EmitPush(r0);

          arguments_ref.SetValue(NOT_CONST_INIT);

        }

        shadow_ref.SetValue(NOT_CONST_INIT);

      }

      frame_->Drop();  // Value is no longer needed.

    }

    // Generate code to 'execute' declarations and initialize functions

    // (source elements). In case of an illegal redeclaration we need to

    // handle that instead of processing the declarations.

    if (scope_->HasIllegalRedeclaration()) {

      Comment cmnt(masm_, "[ illegal redeclarations");

      scope_->VisitIllegalRedeclaration(this);

    } else {

      Comment cmnt(masm_, "[ declarations");

      ProcessDeclarations(scope_->declarations());

      // Bail out if a stack-overflow exception occurred when processing

      // declarations.

      if (HasStackOverflow()) return;

    }

    if (FLAG_trace) {

      frame_->CallRuntime(Runtime::kTraceEnter, 0);

      // Ignore the return value.

    }

    CheckStack();

    // Compile the body of the function in a vanilla state. Don't

    // bother compiling all the code if the scope has an illegal

    // redeclaration.

    if (!scope_->HasIllegalRedeclaration()) {

      Comment cmnt(masm_, "[ function body");

#ifdef DEBUG

      bool is_builtin = Bootstrapper::IsActive();

      bool should_trace =

          is_builtin ? FLAG_trace_builtin_calls : FLAG_trace_calls;

      if (should_trace) {

        frame_->CallRuntime(Runtime::kDebugTrace, 0);

        // Ignore the return value.

      }

#endif

      VisitStatementsAndSpill(body);

    }

  }

  // Generate the return sequence if necessary.

  if (frame_ != NULL || function_return_.is_linked()) {

    // exit

    // r0: result

    // sp: stack pointer

    // fp: frame pointer

    // pp: parameter pointer

    // cp: callee's context

    __ mov(r0, Operand(Factory::undefined_value()));

    function_return_.Bind();

    if (FLAG_trace) {

      // Push the return value on the stack as the parameter.

      // Runtime::TraceExit returns the parameter as it is.

      frame_->EmitPush(r0);

      frame_->CallRuntime(Runtime::kTraceExit, 1);

    }

    // Tear down the frame which will restore the caller's frame pointer and

    // the link register.

    frame_->Exit();

    __ add(sp, sp, Operand((scope_->num_parameters() + 1) * kPointerSize));

    __ mov(pc, lr);

  }

  // Code generation state must be reset.

  ASSERT(!has_cc());

  ASSERT(state_ == NULL);

  ASSERT(!function_return_is_shadowed_);

  function_return_.Unuse();

  DeleteFrame();

  // Process any deferred code using the register allocator.

  if (HasStackOverflow()) {

    ClearDeferred();

  } else {

    ProcessDeferred();

  }

  allocator_ = NULL;

  scope_ = NULL;

}

MemOperand CodeGenerator::SlotOperand(Slot* slot, Register tmp) {

  // Currently, this assertion will fail if we try to assign to

  // a constant variable that is constant because it is read-only

  // (such as the variable referring to a named function expression).

  // We need to implement assignments to read-only variables.

  // Ideally, we should do this during AST generation (by converting

  // such assignments into expression statements); however, in general

  // we may not be able to make the decision until past AST generation,

  // that is when the entire program is known.

  ASSERT(slot != NULL);

  int index = slot->index();

  switch (slot->type()) {

    case Slot::PARAMETER:

      return frame_->ParameterAt(index);

    case Slot::LOCAL:

      return frame_->LocalAt(index);

    case Slot::CONTEXT: {

      // Follow the context chain if necessary.

      ASSERT(!tmp.is(cp));  // do not overwrite context register

      Register context = cp;

      int chain_length = scope()->ContextChainLength(slot->var()->scope());

      for (int i = 0; i < chain_length; i++) {

        // Load the closure.

        // (All contexts, even 'with' contexts, have a closure,

        // and it is the same for all contexts inside a function.

        // There is no need to go to the function context first.)

        __ ldr(tmp, ContextOperand(context, Context::CLOSURE_INDEX));

        // Load the function context (which is the incoming, outer context).

        __ ldr(tmp, FieldMemOperand(tmp, JSFunction::kContextOffset));

        context = tmp;

      }

      // We may have a 'with' context now. Get the function context.

      // (In fact this mov may never be the needed, since the scope analysis

      // may not permit a direct context access in this case and thus we are

      // always at a function context. However it is safe to dereference be-

      // cause the function context of a function context is itself. Before

      // deleting this mov we should try to create a counter-example first,

      // though...)

      __ ldr(tmp, ContextOperand(context, Context::FCONTEXT_INDEX));

      return ContextOperand(tmp, index);

    }

    default:

      UNREACHABLE();

      return MemOperand(r0, 0);

  }

}

MemOperand CodeGenerator::ContextSlotOperandCheckExtensions(

    Slot* slot,

    Register tmp,

    Register tmp2,

    JumpTarget* slow) {

  ASSERT(slot->type() == Slot::CONTEXT);

  Register context = cp;

  for (Scope* s = scope(); s != slot->var()->scope(); s = s->outer_scope()) {

    if (s->num_heap_slots() > 0) {

      if (s->calls_eval()) {

        // Check that extension is NULL.

        __ ldr(tmp2, ContextOperand(context, Context::EXTENSION_INDEX));

        __ tst(tmp2, tmp2);

        slow->Branch(ne);

      }

      __ ldr(tmp, ContextOperand(context, Context::CLOSURE_INDEX));

      __ ldr(tmp, FieldMemOperand(tmp, JSFunction::kContextOffset));

      context = tmp;

    }

  }

  // Check that last extension is NULL.

  __ ldr(tmp2, ContextOperand(context, Context::EXTENSION_INDEX));

  __ tst(tmp2, tmp2);

  slow->Branch(ne);

  __ ldr(tmp, ContextOperand(context, Context::FCONTEXT_INDEX));

  return ContextOperand(tmp, slot->index());

}

void CodeGenerator::LoadConditionAndSpill(Expression* expression,

                                          TypeofState typeof_state,

                                          JumpTarget* true_target,

                                          JumpTarget* false_target,

                                          bool force_control) {

  ASSERT(in_spilled_code());

  set_in_spilled_code(false);

  LoadCondition(expression, typeof_state, true_target, false_target,

                force_control);

  if (frame_ != NULL) {

    frame_->SpillAll();

  }

  set_in_spilled_code(true);

}

// Loads a value on TOS. If it is a boolean value, the result may have been

// (partially) translated into branches, or it may have set the condition

// code register. If force_cc is set, the value is forced to set the

// condition code register and no value is pushed. If the condition code

// register was set, has_cc() is true and cc_reg_ contains the condition to

// test for 'true'.

void CodeGenerator::LoadCondition(Expression* x,

                                  TypeofState typeof_state,

                                  JumpTarget* true_target,

                                  JumpTarget* false_target,

                                  bool force_cc) {

  ASSERT(!in_spilled_code());

  ASSERT(!has_cc());

  int original_height = frame_->height();

  { CodeGenState new_state(this, typeof_state, true_target, false_target);

    Visit(x);

    // If we hit a stack overflow, we may not have actually visited

    // the expression.  In that case, we ensure that we have a

    // valid-looking frame state because we will continue to generate

    // code as we unwind the C++ stack.

    //

    // It's possible to have both a stack overflow and a valid frame

    // state (eg, a subexpression overflowed, visiting it returned

    // with a dummied frame state, and visiting this expression

    // returned with a normal-looking state).

    if (HasStackOverflow() &&

        has_valid_frame() &&

        !has_cc() &&

        frame_->height() == original_height) {

      true_target->Jump();

    }

  }

  if (force_cc && frame_ != NULL && !has_cc()) {

    // Convert the TOS value to a boolean in the condition code register.

    ToBoolean(true_target, false_target);

  }

  ASSERT(!force_cc || !has_valid_frame() || has_cc());

  ASSERT(!has_valid_frame() ||

         (has_cc() && frame_->height() == original_height) ||

         (!has_cc() && frame_->height() == original_height + 1));

}

void CodeGenerator::LoadAndSpill(Expression* expression,

                                 TypeofState typeof_state) {

  ASSERT(in_spilled_code());

  set_in_spilled_code(false);

  Load(expression, typeof_state);

  frame_->SpillAll();

  set_in_spilled_code(true);

}

void CodeGenerator::Load(Expression* x, TypeofState typeof_state) {

#ifdef DEBUG

  int original_height = frame_->height();

#endif

  ASSERT(!in_spilled_code());

  JumpTarget true_target(this);

  JumpTarget false_target(this);

  LoadCondition(x, typeof_state, &true_target, &false_target, false);

  if (has_cc()) {

    // Convert cc_reg_ into a boolean value.

    JumpTarget loaded(this);

    JumpTarget materialize_true(this);

    materialize_true.Branch(cc_reg_);

    __ mov(r0, Operand(Factory::false_value()));

    frame_->EmitPush(r0);

    loaded.Jump();

    materialize_true.Bind();

    __ mov(r0, Operand(Factory::true_value()));

    frame_->EmitPush(r0);

    loaded.Bind();

    cc_reg_ = al;

  }

  if (true_target.is_linked() || false_target.is_linked()) {

    // We have at least one condition value that has been "translated"

    // into a branch, thus it needs to be loaded explicitly.

    JumpTarget loaded(this);

    if (frame_ != NULL) {

      loaded.Jump();  // Don't lose the current TOS.

    }

    bool both = true_target.is_linked() && false_target.is_linked();

    // Load "true" if necessary.

    if (true_target.is_linked()) {

      true_target.Bind();

      __ mov(r0, Operand(Factory::true_value()));

      frame_->EmitPush(r0);

    }

    // If both "true" and "false" need to be loaded jump across the code for

    // "false".

    if (both) {

      loaded.Jump();

    }

    // Load "false" if necessary.

    if (false_target.is_linked()) {

      false_target.Bind();

      __ mov(r0, Operand(Factory::false_value()));

      frame_->EmitPush(r0);

    }

    // A value is loaded on all paths reaching this point.

    loaded.Bind();

  }

  ASSERT(has_valid_frame());

  ASSERT(!has_cc());

  ASSERT(frame_->height() == original_height + 1);

}

void CodeGenerator::LoadGlobal() {

  VirtualFrame::SpilledScope spilled_scope(this);

  __ ldr(r0, GlobalObject());

  frame_->EmitPush(r0);

}

void CodeGenerator::LoadGlobalReceiver(Register scratch) {

  VirtualFrame::SpilledScope spilled_scope(this);

  __ ldr(scratch, ContextOperand(cp, Context::GLOBAL_INDEX));

  __ ldr(scratch,

         FieldMemOperand(scratch, GlobalObject::kGlobalReceiverOffset));

  frame_->EmitPush(scratch);

}

// TODO(1241834): Get rid of this function in favor of just using Load, now

// that we have the INSIDE_TYPEOF typeof state. => Need to handle global

// variables w/o reference errors elsewhere.

void CodeGenerator::LoadTypeofExpression(Expression* x) {

  VirtualFrame::SpilledScope spilled_scope(this);

  Variable* variable = x->AsVariableProxy()->AsVariable();

  if (variable != NULL && !variable->is_this() && variable->is_global()) {

    // NOTE: This is somewhat nasty. We force the compiler to load

    // the variable as if through '<global>.<variable>' to make sure we

    // do not get reference errors.

    Slot global(variable, Slot::CONTEXT, Context::GLOBAL_INDEX);

    Literal key(variable->name());

    // TODO(1241834): Fetch the position from the variable instead of using

    // no position.

    Property property(&global, &key, RelocInfo::kNoPosition);

    LoadAndSpill(&property);

  } else {

    LoadAndSpill(x, INSIDE_TYPEOF);

  }

}

Reference::Reference(CodeGenerator* cgen, Expression* expression)

    : cgen_(cgen), expression_(expression), type_(ILLEGAL) {

  cgen->LoadReference(this);

}

Reference::~Reference() {

  cgen_->UnloadReference(this);

}

void CodeGenerator::LoadReference(Reference* ref) {

  VirtualFrame::SpilledScope spilled_scope(this);

  Comment cmnt(masm_, "[ LoadReference");

  Expression* e = ref->expression();

  Property* property = e->AsProperty();

  Variable* var = e->AsVariableProxy()->AsVariable();

  if (property != NULL) {

    // The expression is either a property or a variable proxy that rewrites

    // to a property.

    LoadAndSpill(property->obj());

    // We use a named reference if the key is a literal symbol, unless it is

    // a string that can be legally parsed as an integer.  This is because

    // otherwise we will not get into the slow case code that handles [] on

    // String objects.

    Literal* literal = property->key()->AsLiteral();

    uint32_t dummy;

    if (literal != NULL &&

        literal->handle()->IsSymbol() &&

        !String::cast(*(literal->handle()))->AsArrayIndex(&dummy)) {

      ref->set_type(Reference::NAMED);

    } else {

      LoadAndSpill(property->key());

      ref->set_type(Reference::KEYED);

    }

  } else if (var != NULL) {

    // The expression is a variable proxy that does not rewrite to a

    // property.  Global variables are treated as named property references.

    if (var->is_global()) {

      LoadGlobal();

      ref->set_type(Reference::NAMED);

    } else {

      ASSERT(var->slot() != NULL);

      ref->set_type(Reference::SLOT);

    }

  } else {

    // Anything else is a runtime error.

    LoadAndSpill(e);

    frame_->CallRuntime(Runtime::kThrowReferenceError, 1);

  }

}

void CodeGenerator::UnloadReference(Reference* ref) {

  VirtualFrame::SpilledScope spilled_scope(this);

  // Pop a reference from the stack while preserving TOS.

  Comment cmnt(masm_, "[ UnloadReference");

  int size = ref->size();

  if (size > 0) {

    frame_->EmitPop(r0);

    frame_->Drop(size);

    frame_->EmitPush(r0);

  }

}

// ECMA-262, section 9.2, page 30: ToBoolean(). Convert the given

// register to a boolean in the condition code register. The code

// may jump to 'false_target' in case the register converts to 'false'.

void CodeGenerator::ToBoolean(JumpTarget* true_target,

                              JumpTarget* false_target) {

  VirtualFrame::SpilledScope spilled_scope(this);

  // Note: The generated code snippet does not change stack variables.

  //       Only the condition code should be set.

  frame_->EmitPop(r0);

  // Fast case checks

  // Check if the value is 'false'.

  __ cmp(r0, Operand(Factory::false_value()));

  false_target->Branch(eq);

  // Check if the value is 'true'.

  __ cmp(r0, Operand(Factory::true_value()));

  true_target->Branch(eq);

  // Check if the value is 'undefined'.

  __ cmp(r0, Operand(Factory::undefined_value()));

  false_target->Branch(eq);

  // Check if the value is a smi.

  __ cmp(r0, Operand(Smi::FromInt(0)));

  false_target->Branch(eq);

  __ tst(r0, Operand(kSmiTagMask));

  true_target->Branch(eq);

  // Slow case: call the runtime.

  frame_->EmitPush(r0);

  frame_->CallRuntime(Runtime::kToBool, 1);

  // Convert the result (r0) to a condition code.

  __ cmp(r0, Operand(Factory::false_value()));

  cc_reg_ = ne;

}

class GetPropertyStub : public CodeStub {

 public:

  GetPropertyStub() { }

 private:

  Major MajorKey() { return GetProperty; }

  int MinorKey() { return 0; }

  void Generate(MacroAssembler* masm);

};

class SetPropertyStub : public CodeStub {

 public:

  SetPropertyStub() { }

 private:

  Major MajorKey() { return SetProperty; }

  int MinorKey() { return 0; }

  void Generate(MacroAssembler* masm);

};

class GenericBinaryOpStub : public CodeStub {

 public:

  explicit GenericBinaryOpStub(Token::Value op) : op_(op) { }

 private:

  Token::Value op_;

  Major MajorKey() { return GenericBinaryOp; }

  int MinorKey() { return static_cast<int>(op_); }

  void Generate(MacroAssembler* masm);

  const char* GetName() {

    switch (op_) {

      case Token::ADD: return "GenericBinaryOpStub_ADD";

      case Token::SUB: return "GenericBinaryOpStub_SUB";

      case Token::MUL: return "GenericBinaryOpStub_MUL";

      case Token::DIV: return "GenericBinaryOpStub_DIV";

      case Token::BIT_OR: return "GenericBinaryOpStub_BIT_OR";

      case Token::BIT_AND: return "GenericBinaryOpStub_BIT_AND";

      case Token::BIT_XOR: return "GenericBinaryOpStub_BIT_XOR";

      case Token::SAR: return "GenericBinaryOpStub_SAR";

      case Token::SHL: return "GenericBinaryOpStub_SHL";

      case Token::SHR: return "GenericBinaryOpStub_SHR";

      default:         return "GenericBinaryOpStub";

    }

  }

#ifdef DEBUG

  void Print() { PrintF("GenericBinaryOpStub (%s)\n", Token::String(op_)); }

#endif

};

void CodeGenerator::GenericBinaryOperation(Token::Value op) {

  VirtualFrame::SpilledScope spilled_scope(this);

  // sp[0] : y

  // sp[1] : x

  // result : r0

  // Stub is entered with a call: 'return address' is in lr.

  switch (op) {

    case Token::ADD:  // fall through.

    case Token::SUB:  // fall through.

    case Token::MUL:

    case Token::BIT_OR:

    case Token::BIT_AND:

    case Token::BIT_XOR:

    case Token::SHL:

    case Token::SHR:

    case Token::SAR: {

      frame_->EmitPop(r0);  // r0 : y

      frame_->EmitPop(r1);  // r1 : x

      GenericBinaryOpStub stub(op);

      frame_->CallStub(&stub, 0);

      break;

    }

    case Token::DIV: {

      Result arg_count = allocator_->Allocate(r0);

      ASSERT(arg_count.is_valid());

      __ mov(arg_count.reg(), Operand(1));

      frame_->InvokeBuiltin(Builtins::DIV, CALL_JS, &arg_count, 2);

      break;

    }

    case Token::MOD: {

      Result arg_count = allocator_->Allocate(r0);

      ASSERT(arg_count.is_valid());

      __ mov(arg_count.reg(), Operand(1));

      frame_->InvokeBuiltin(Builtins::MOD, CALL_JS, &arg_count, 2);

      break;

    }

    case Token::COMMA:

      frame_->EmitPop(r0);

      // simply discard left value

      frame_->Drop();

      break;

    default:

      // Other cases should have been handled before this point.

      UNREACHABLE();

      break;

  }

}

class DeferredInlineSmiOperation: public DeferredCode {

 public:

  DeferredInlineSmiOperation(CodeGenerator* generator,

                             Token::Value op,

                             int value,

                             bool reversed)

      : DeferredCode(generator),

        op_(op),

        value_(value),

        reversed_(reversed) {

    set_comment("[ DeferredInlinedSmiOperation");

  }

  virtual void Generate();

 private:

  Token::Value op_;

  int value_;

  bool reversed_;

};

void DeferredInlineSmiOperation::Generate() {

  enter()->Bind();

  VirtualFrame::SpilledScope spilled_scope(generator());

  switch (op_) {

    case Token::ADD: {

      if (reversed_) {

        // revert optimistic add

        __ sub(r0, r0, Operand(Smi::FromInt(value_)));

        __ mov(r1, Operand(Smi::FromInt(value_)));

      } else {

        // revert optimistic add

        __ sub(r1, r0, Operand(Smi::FromInt(value_)));

        __ mov(r0, Operand(Smi::FromInt(value_)));

      }

      break;

    }

    case Token::SUB: {

      if (reversed_) {

        // revert optimistic sub

        __ rsb(r0, r0, Operand(Smi::FromInt(value_)));

        __ mov(r1, Operand(Smi::FromInt(value_)));

      } else {

        __ add(r1, r0, Operand(Smi::FromInt(value_)));

        __ mov(r0, Operand(Smi::FromInt(value_)));

      }

      break;

    }

    case Token::BIT_OR:

    case Token::BIT_XOR:

    case Token::BIT_AND: {

      if (reversed_) {

        __ mov(r1, Operand(Smi::FromInt(value_)));

      } else {

        __ mov(r1, Operand(r0));

        __ mov(r0, Operand(Smi::FromInt(value_)));

      }

      break;

    }

    case Token::SHL:

    case Token::SHR:

    case Token::SAR: {

      if (!reversed_) {

        __ mov(r1, Operand(r0));

        __ mov(r0, Operand(Smi::FromInt(value_)));

      } else {

        UNREACHABLE();  // should have been handled in SmiOperation

      }

      break;

    }

    default:

      // other cases should have been handled before this point.

      UNREACHABLE();

      break;

  }

  GenericBinaryOpStub igostub(op_);

  Result arg0 = generator()->allocator()->Allocate(r1);

  ASSERT(arg0.is_valid());

  Result arg1 = generator()->allocator()->Allocate(r0);

  ASSERT(arg1.is_valid());

  generator()->frame()->CallStub(&igostub, &arg0, &arg1);

  exit_.Jump();

}

void CodeGenerator::SmiOperation(Token::Value op,

                                 Handle<Object> value,

                                 bool reversed) {

  VirtualFrame::SpilledScope spilled_scope(this);

  // NOTE: This is an attempt to inline (a bit) more of the code for

  // some possible smi operations (like + and -) when (at least) one

  // of the operands is a literal smi. With this optimization, the

  // performance of the system is increased by ~15%, and the generated

  // code size is increased by ~1% (measured on a combination of

  // different benchmarks).

  // sp[0] : operand

  int int_value = Smi::cast(*value)->value();

  JumpTarget exit(this);

  frame_->EmitPop(r0);

  switch (op) {

    case Token::ADD: {

      DeferredCode* deferred =

        new DeferredInlineSmiOperation(this, op, int_value, reversed);

      __ add(r0, r0, Operand(value), SetCC);

      deferred->enter()->Branch(vs);

      __ tst(r0, Operand(kSmiTagMask));

      deferred->enter()->Branch(ne);

      deferred->BindExit();

      break;

    }

    case Token::SUB: {

      DeferredCode* deferred =

        new DeferredInlineSmiOperation(this, op, int_value, reversed);

      if (!reversed) {

        __ sub(r0, r0, Operand(value), SetCC);

      } else {

        __ rsb(r0, r0, Operand(value), SetCC);

      }

      deferred->enter()->Branch(vs);

      __ tst(r0, Operand(kSmiTagMask));

      deferred->enter()->Branch(ne);

      deferred->BindExit();

      break;

    }

    case Token::BIT_OR:

    case Token::BIT_XOR:

    case Token::BIT_AND: {

      DeferredCode* deferred =

        new DeferredInlineSmiOperation(this, op, int_value, reversed);

      __ tst(r0, Operand(kSmiTagMask));

      deferred->enter()->Branch(ne);

      switch (op) {

        case Token::BIT_OR:  __ orr(r0, r0, Operand(value)); break;

        case Token::BIT_XOR: __ eor(r0, r0, Operand(value)); break;

        case Token::BIT_AND: __ and_(r0, r0, Operand(value)); break;

        default: UNREACHABLE();

      }

      deferred->BindExit();

      break;

    }

    case Token::SHL:

    case Token::SHR:

    case Token::SAR: {

      if (reversed) {

        __ mov(ip, Operand(value));

        frame_->EmitPush(ip);

        frame_->EmitPush(r0);

        GenericBinaryOperation(op);

      } else {

        int shift_value = int_value & 0x1f;  // least significant 5 bits

        DeferredCode* deferred =

          new DeferredInlineSmiOperation(this, op, shift_value, false);

        __ tst(r0, Operand(kSmiTagMask));

        deferred->enter()->Branch(ne);

        __ mov(r2, Operand(r0, ASR, kSmiTagSize));  // remove tags

        switch (op) {

          case Token::SHL: {

            __ mov(r2, Operand(r2, LSL, shift_value));

            // check that the *unsigned* result fits in a smi

            __ add(r3, r2, Operand(0x40000000), SetCC);

            deferred->enter()->Branch(mi);

            break;

          }

          case Token::SHR: {

            // LSR by immediate 0 means shifting 32 bits.

            if (shift_value != 0) {

              __ mov(r2, Operand(r2, LSR, shift_value));

            }

            // check that the *unsigned* result fits in a smi

            // neither of the two high-order bits can be set:

            // - 0x80000000: high bit would be lost when smi tagging

            // - 0x40000000: this number would convert to negative when

            // smi tagging these two cases can only happen with shifts

            // by 0 or 1 when handed a valid smi

            __ and_(r3, r2, Operand(0xc0000000), SetCC);

            deferred->enter()->Branch(ne);

            break;

          }

          case Token::SAR: {

            if (shift_value != 0) {

              // ASR by immediate 0 means shifting 32 bits.

              __ mov(r2, Operand(r2, ASR, shift_value));

            }

            break;

          }

          default: UNREACHABLE();

        }

        __ mov(r0, Operand(r2, LSL, kSmiTagSize));

        deferred->BindExit();

      }

      break;

    }

    default:

      if (!reversed) {

        frame_->EmitPush(r0);

        __ mov(r0, Operand(value));

        frame_->EmitPush(r0);

      } else {

        __ mov(ip, Operand(value));

        frame_->EmitPush(ip);

        frame_->EmitPush(r0);

      }

      GenericBinaryOperation(op);

      break;

  }

  exit.Bind();

}

void CodeGenerator::Comparison(Condition cc, bool strict) {

  VirtualFrame::SpilledScope spilled_scope(this);

  // sp[0] : y

  // sp[1] : x

  // result : cc register

  // Strict only makes sense for equality comparisons.

  ASSERT(!strict || cc == eq);

  JumpTarget exit(this);

  JumpTarget smi(this);

  // Implement '>' and '<=' by reversal to obtain ECMA-262 conversion order.

  if (cc == gt || cc == le) {

    cc = ReverseCondition(cc);

    frame_->EmitPop(r1);

    frame_->EmitPop(r0);

  } else {

    frame_->EmitPop(r0);

    frame_->EmitPop(r1);

  }

  __ orr(r2, r0, Operand(r1));

  __ tst(r2, Operand(kSmiTagMask));

  smi.Branch(eq);

  // Perform non-smi comparison by runtime call.

  frame_->EmitPush(r1);

  // Figure out which native to call and setup the arguments.

  Builtins::JavaScript native;

  int arg_count = 1;

  if (cc == eq) {

    native = strict ? Builtins::STRICT_EQUALS : Builtins::EQUALS;

  } else {

    native = Builtins::COMPARE;

    int ncr;  // NaN compare result

    if (cc == lt || cc == le) {

      ncr = GREATER;

    } else {

      ASSERT(cc == gt || cc == ge);  // remaining cases

      ncr = LESS;

    }

    frame_->EmitPush(r0);

    arg_count++;

    __ mov(r0, Operand(Smi::FromInt(ncr)));

  }

  // Call the native; it returns -1 (less), 0 (equal), or 1 (greater)

  // tagged as a small integer.

  frame_->EmitPush(r0);

  Result arg_count_register = allocator_->Allocate(r0);

  ASSERT(arg_count_register.is_valid());

  __ mov(arg_count_register.reg(), Operand(arg_count));

  Result result = frame_->InvokeBuiltin(native,

                                        CALL_JS,

                                        &arg_count_register,

                                        arg_count + 1);

  __ cmp(result.reg(), Operand(0));

  result.Unuse();

  exit.Jump();

  // test smi equality by pointer comparison.

  smi.Bind();

  __ cmp(r1, Operand(r0));

  exit.Bind();

  cc_reg_ = cc;

}

class CallFunctionStub: public CodeStub {

 public:

  explicit CallFunctionStub(int argc) : argc_(argc) {}

  void Generate(MacroAssembler* masm);

 private:

  int argc_;

#if defined(DEBUG)

  void Print() { PrintF("CallFunctionStub (argc %d)\n", argc_); }

#endif  // defined(DEBUG)

  Major MajorKey() { return CallFunction; }

  int MinorKey() { return argc_; }

};

// Call the function on the stack with the given arguments.

void CodeGenerator::CallWithArguments(ZoneList<Expression*>* args,

                                         int position) {

  VirtualFrame::SpilledScope spilled_scope(this);

  // Push the arguments ("left-to-right") on the stack.

  int arg_count = args->length();

  for (int i = 0; i < arg_count; i++) {

    LoadAndSpill(args->at(i));

  }

  // Record the position for debugging purposes.

  CodeForSourcePosition(position);

  // Use the shared code stub to call the function.

  CallFunctionStub call_function(arg_count);

  frame_->CallStub(&call_function, arg_count + 1);

  // Restore context and pop function from the stack.

  __ ldr(cp, frame_->Context());

  frame_->Drop();  // discard the TOS

}

void CodeGenerator::Branch(bool if_true, JumpTarget* target) {

  VirtualFrame::SpilledScope spilled_scope(this);

  ASSERT(has_cc());

  Condition cc = if_true ? cc_reg_ : NegateCondition(cc_reg_);

  target->Branch(cc);

  cc_reg_ = al;

}

void CodeGenerator::CheckStack() {

  VirtualFrame::SpilledScope spilled_scope(this);

  if (FLAG_check_stack) {

    Comment cmnt(masm_, "[ check stack");

    StackCheckStub stub;

    frame_->CallStub(&stub, 0);

  }

}

void CodeGenerator::VisitAndSpill(Statement* statement) {

  ASSERT(in_spilled_code());

  set_in_spilled_code(false);

  Visit(statement);

  if (frame_ != NULL) {

    frame_->SpillAll();

    }

  set_in_spilled_code(true);

}

void CodeGenerator::VisitStatementsAndSpill(ZoneList<Statement*>* statements) {

  ASSERT(in_spilled_code());

  set_in_spilled_code(false);

  VisitStatements(statements);

  if (frame_ != NULL) {

    frame_->SpillAll();

  }

  set_in_spilled_code(true);

}

void CodeGenerator::VisitStatements(ZoneList<Statement*>* statements) {

#ifdef DEBUG

  int original_height = frame_->height();

#endif

  VirtualFrame::SpilledScope spilled_scope(this);

  for (int i = 0; frame_ != NULL && i < statements->length(); i++) {

    VisitAndSpill(statements->at(i));

  }

  ASSERT(!has_valid_frame() || frame_->height() == original_height);

}

void CodeGenerator::VisitBlock(Block* node) {

#ifdef DEBUG

  int original_height = frame_->height();

#endif

  VirtualFrame::SpilledScope spilled_scope(this);

  Comment cmnt(masm_, "[ Block");

  CodeForStatementPosition(node);

  node->break_target()->Initialize(this);

  VisitStatementsAndSpill(node->statements());

  if (node->break_target()->is_linked()) {

    node->break_target()->Bind();

  }

  node->break_target()->Unuse();

  ASSERT(!has_valid_frame() || frame_->height() == original_height);

}

void CodeGenerator::DeclareGlobals(Handle<FixedArray> pairs) {

  VirtualFrame::SpilledScope spilled_scope(this);

  __ mov(r0, Operand(pairs));

  frame_->EmitPush(r0);

  frame_->EmitPush(cp);

  __ mov(r0, Operand(Smi::FromInt(is_eval() ? 1 : 0)));

  frame_->EmitPush(r0);

  frame_->CallRuntime(Runtime::kDeclareGlobals, 3);

  // The result is discarded.

}

void CodeGenerator::VisitDeclaration(Declaration* node) {

#ifdef DEBUG

  int original_height = frame_->height();

#endif

  VirtualFrame::SpilledScope spilled_scope(this);

  Comment cmnt(masm_, "[ Declaration");

  CodeForStatementPosition(node);

  Variable* var = node->proxy()->var();

  ASSERT(var != NULL);  // must have been resolved

  Slot* slot = var->slot();

  // If it was not possible to allocate the variable at compile time,

  // we need to "declare" it at runtime to make sure it actually

  // exists in the local context.

  if (slot != NULL && slot->type() == Slot::LOOKUP) {

    // Variables with a "LOOKUP" slot were introduced as non-locals

    // during variable resolution and must have mode DYNAMIC.

    ASSERT(var->is_dynamic());

    // For now, just do a runtime call.

    frame_->EmitPush(cp);

    __ mov(r0, Operand(var->name()));

    frame_->EmitPush(r0);

    // Declaration nodes are always declared in only two modes.

    ASSERT(node->mode() == Variable::VAR || node->mode() == Variable::CONST);

    PropertyAttributes attr = node->mode() == Variable::VAR ? NONE : READ_ONLY;

    __ mov(r0, Operand(Smi::FromInt(attr)));

    frame_->EmitPush(r0);

    // Push initial value, if any.

    // Note: For variables we must not push an initial value (such as

    // 'undefined') because we may have a (legal) redeclaration and we

    // must not destroy the current value.

    if (node->mode() == Variable::CONST) {

      __ mov(r0, Operand(Factory::the_hole_value()));

      frame_->EmitPush(r0);

    } else if (node->fun() != NULL) {

      LoadAndSpill(node->fun());

    } else {

      __ mov(r0, Operand(0));  // no initial value!

      frame_->EmitPush(r0);

    }

    frame_->CallRuntime(Runtime::kDeclareContextSlot, 4);

    // Ignore the return value (declarations are statements).

    ASSERT(frame_->height() == original_height);

    return;

  }

  ASSERT(!var->is_global());

  // If we have a function or a constant, we need to initialize the variable.

  Expression* val = NULL;

  if (node->mode() == Variable::CONST) {

    val = new Literal(Factory::the_hole_value());

  } else {

    val = node->fun();  // NULL if we don't have a function

  }

  if (val != NULL) {

    {

      // Set initial value.

      Reference target(this, node->proxy());

      LoadAndSpill(val);

      target.SetValue(NOT_CONST_INIT);

      // The reference is removed from the stack (preserving TOS) when

      // it goes out of scope.

    }

    // Get rid of the assigned value (declarations are statements).

    frame_->Drop();

  }

  ASSERT(frame_->height() == original_height);

}

void CodeGenerator::VisitExpressionStatement(ExpressionStatement* node) {

#ifdef DEBUG

  int original_height = frame_->height();

#endif

  VirtualFrame::SpilledScope spilled_scope(this);

  Comment cmnt(masm_, "[ ExpressionStatement");

  CodeForStatementPosition(node);

  Expression* expression = node->expression();

  expression->MarkAsStatement();

  LoadAndSpill(expression);

  frame_->Drop();

  ASSERT(frame_->height() == original_height);

}

void CodeGenerator::VisitEmptyStatement(EmptyStatement* node) {

#ifdef DEBUG

  int original_height = frame_->height();

#endif

  VirtualFrame::SpilledScope spilled_scope(this);

  Comment cmnt(masm_, "// EmptyStatement");

  CodeForStatementPosition(node);

  // nothing to do

  ASSERT(frame_->height() == original_height);

}

void CodeGenerator::VisitIfStatement(IfStatement* node) {

#ifdef DEBUG

  int original_height = frame_->height();

#endif

  VirtualFrame::SpilledScope spilled_scope(this);

  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(this);

  if (has_then_stm && has_else_stm) {

    Comment cmnt(masm_, "[ IfThenElse");

    JumpTarget then(this);

    JumpTarget else_(this);

    // if (cond)

    LoadConditionAndSpill(node->condition(), NOT_INSIDE_TYPEOF,

                          &then, &else_, true);

    if (frame_ != NULL) {

      Branch(false, &else_);

    }

    // then

    if (frame_ != NULL || then.is_linked()) {

      then.Bind();

      VisitAndSpill(node->then_statement());

    }

    if (frame_ != NULL) {

      exit.Jump();

    }

    // else

    if (else_.is_linked()) {

      else_.Bind();

      VisitAndSpill(node->else_statement());

    }

  } else if (has_then_stm) {

    Comment cmnt(masm_, "[ IfThen");

    ASSERT(!has_else_stm);

    JumpTarget then(this);

    // if (cond)

    LoadConditionAndSpill(node->condition(), NOT_INSIDE_TYPEOF,

                          &then, &exit, true);

    if (frame_ != NULL) {

      Branch(false, &exit);

    }

    // then

    if (frame_ != NULL || then.is_linked()) {

      then.Bind();

      VisitAndSpill(node->then_statement());

    }

  } else if (has_else_stm) {

    Comment cmnt(masm_, "[ IfElse");

    ASSERT(!has_then_stm);

    JumpTarget else_(this);

    // if (!cond)

    LoadConditionAndSpill(node->condition(), NOT_INSIDE_TYPEOF,

                          &exit, &else_, true);

    if (frame_ != NULL) {

      Branch(true, &exit);

    }

    // else

    if (frame_ != NULL || else_.is_linked()) {

      else_.Bind();

      VisitAndSpill(node->else_statement());

    }

  } else {

    Comment cmnt(masm_, "[ If");

    ASSERT(!has_then_stm && !has_else_stm);

    // if (cond)

    LoadConditionAndSpill(node->condition(), NOT_INSIDE_TYPEOF,

                          &exit, &exit, false);

    if (frame_ != NULL) {

      if (has_cc()) {

        cc_reg_ = al;

      } else {

        frame_->Drop();

      }

    }

  }

  // end

  if (exit.is_linked()) {

    exit.Bind();

  }

  ASSERT(!has_valid_frame() || frame_->height() == original_height);

}

void CodeGenerator::VisitContinueStatement(ContinueStatement* node) {

  VirtualFrame::SpilledScope spilled_scope(this);

  Comment cmnt(masm_, "[ ContinueStatement");

  CodeForStatementPosition(node);

  node->target()->continue_target()->Jump();

}

void CodeGenerator::VisitBreakStatement(BreakStatement* node) {

  VirtualFrame::SpilledScope spilled_scope(this);

  Comment cmnt(masm_, "[ BreakStatement");

  CodeForStatementPosition(node);

  node->target()->break_target()->Jump();

}

void CodeGenerator::VisitReturnStatement(ReturnStatement* node) {

  VirtualFrame::SpilledScope spilled_scope(this);

  Comment cmnt(masm_, "[ ReturnStatement");

  if (function_return_is_shadowed_) {