// Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#include "vm/globals.h"  // Needed here to get TARGET_ARCH_XXX.

#include "vm/flow_graph_compiler.h"

#include "vm/cha.h"
#include "vm/dart_entry.h"
#include "vm/debugger.h"
#include "vm/deopt_instructions.h"
#include "vm/flow_graph_allocator.h"
#include "vm/il_printer.h"
#include "vm/intrinsifier.h"
#include "vm/locations.h"
#include "vm/longjump.h"
#include "vm/object_store.h"
#include "vm/parser.h"
#include "vm/stub_code.h"
#include "vm/symbols.h"

namespace dart {

DEFINE_FLAG(bool, print_scopes, false, "Print scopes of local variables.");
DECLARE_FLAG(bool, code_comments);
DECLARE_FLAG(bool, enable_type_checks);
DECLARE_FLAG(bool, intrinsify);
DECLARE_FLAG(bool, propagate_ic_data);
DECLARE_FLAG(bool, report_usage_count);
DECLARE_FLAG(int, optimization_counter_threshold);
DECLARE_FLAG(bool, use_cha);


// Assign locations to incoming arguments, i.e., values pushed above spill slots
// with PushArgument.  Recursively allocates from outermost to innermost
// environment.
void CompilerDeoptInfo::AllocateIncomingParametersRecursive(
    Environment* env,
    intptr_t* stack_height) {
  if (env == NULL) return;
  AllocateIncomingParametersRecursive(env->outer(), stack_height);
  for (Environment::ShallowIterator it(env); !it.Done(); it.Advance()) {
    if (it.CurrentLocation().IsInvalid() &&
        it.CurrentValue()->definition()->IsPushArgument()) {
      it.SetCurrentLocation(Location::StackSlot((*stack_height)++));
    }
  }
}


void CompilerDeoptInfo::EmitMaterializations(Environment* env,
                                             DeoptInfoBuilder* builder) {
  for (Environment::DeepIterator it(env); !it.Done(); it.Advance()) {
    if (it.CurrentLocation().IsInvalid()) {
      MaterializeObjectInstr* mat =
          it.CurrentValue()->definition()->AsMaterializeObject();
      ASSERT(mat != NULL);
      builder->AddMaterialization(mat);
    }
  }
}


FlowGraphCompiler::FlowGraphCompiler(Assembler* assembler,
                                     const FlowGraph& flow_graph,
                                     bool is_optimizing)
    : assembler_(assembler),
      parsed_function_(flow_graph.parsed_function()),
      flow_graph_(flow_graph),
      block_order_(flow_graph.reverse_postorder()),
      current_block_(NULL),
      exception_handlers_list_(NULL),
      pc_descriptors_list_(NULL),
      stackmap_table_builder_(
          is_optimizing ? new StackmapTableBuilder() : NULL),
      block_info_(block_order_.length()),
      deopt_infos_(),
      static_calls_target_table_(GrowableObjectArray::ZoneHandle(
          GrowableObjectArray::New())),
      is_optimizing_(is_optimizing),
      may_reoptimize_(false),
      double_class_(Class::ZoneHandle(
          Isolate::Current()->object_store()->double_class())),
      float32x4_class_(Class::ZoneHandle(
          Isolate::Current()->object_store()->float32x4_class())),
      uint32x4_class_(Class::ZoneHandle(
          Isolate::Current()->object_store()->uint32x4_class())),
      parallel_move_resolver_(this),
      pending_deoptimization_env_(NULL) {
  ASSERT(assembler != NULL);
}


bool FlowGraphCompiler::HasFinally() const {
  return parsed_function().function().has_finally();
}


void FlowGraphCompiler::InitCompiler() {
  pc_descriptors_list_ = new DescriptorList(64);
  exception_handlers_list_ = new ExceptionHandlerList();
  block_info_.Clear();
  bool is_leaf = !parsed_function().function().IsClosureFunction() &&
                 is_optimizing();
  for (int i = 0; i < block_order_.length(); ++i) {
    block_info_.Add(new BlockInfo());
    if (is_optimizing()) {
      BlockEntryInstr* entry = block_order_[i];
      for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
        Instruction* current = it.Current();
        const ICData* ic_data = NULL;
        if (current->IsBranch()) {
          current = current->AsBranch()->comparison();
        }
        // In optimized code, ICData is always set in the instructions.
        if (current->IsInstanceCall()) {
          ic_data = current->AsInstanceCall()->ic_data();
          ASSERT(ic_data != NULL);
        } else if (current->IsRelationalOp()) {
          ic_data = current->AsRelationalOp()->ic_data();
          ASSERT(ic_data != NULL);
        } else if (current->IsEqualityCompare()) {
          ic_data = current->AsEqualityCompare()->ic_data();
          ASSERT(ic_data != NULL);
        }
        if ((ic_data != NULL) && (ic_data->NumberOfChecks() == 0)) {
          may_reoptimize_ = true;
          break;
        }
        if (is_leaf && !current->IsCheckStackOverflow()) {
          // Note that we do no care if the code contains instructions that
          // can deoptimize.
          LocationSummary* locs = current->locs();
          if ((locs != NULL) && locs->can_call()) {
            is_leaf = false;
          }
        }
      }
    }
  }
  if (is_leaf) {
    // Remove check stack overflow at entry.
    CheckStackOverflowInstr* check = flow_graph_.graph_entry()->normal_entry()
        ->next()->AsCheckStackOverflow();
    ASSERT(check != NULL);
    check->RemoveFromGraph();
  }
}


bool FlowGraphCompiler::CanOptimize() {
  return !FLAG_report_usage_count &&
         (FLAG_optimization_counter_threshold >= 0);
}


bool FlowGraphCompiler::CanOptimizeFunction() const {
  return CanOptimize() && !parsed_function().function().HasBreakpoint();
}


static bool IsEmptyBlock(BlockEntryInstr* block) {
  return !block->HasParallelMove() &&
         block->next()->IsGoto() &&
         !block->next()->AsGoto()->HasParallelMove();
}


void FlowGraphCompiler::CompactBlock(BlockEntryInstr* block) {
  BlockInfo* block_info = block_info_[block->postorder_number()];

  if (block_info->is_marked()) {
    return;
  }
  block_info->mark();

  if (IsEmptyBlock(block)) {
    BlockEntryInstr* target = block->next()->AsGoto()->successor();
    CompactBlock(target);
    block_info->set_jump_label(GetJumpLabel(target));
  }
}


void FlowGraphCompiler::CompactBlocks() {
  Label* fallthrough_label = NULL;
  for (intptr_t i = block_order().length() - 1; i >= 1; --i) {
    BlockEntryInstr* block = block_order()[i];

    // Unoptimized code must emit all possible deoptimization points.
    if (is_optimizing()) {
      CompactBlock(block);
    }

    if (!WasCompacted(block)) {
      BlockInfo* block_info = block_info_[block->postorder_number()];
      block_info->set_fallthrough_label(fallthrough_label);
      fallthrough_label = GetJumpLabel(block);
    }
  }

  ASSERT(block_order()[0]->IsGraphEntry());
  BlockInfo* block_info = block_info_[block_order()[0]->postorder_number()];
  block_info->set_fallthrough_label(fallthrough_label);
}


void FlowGraphCompiler::VisitBlocks() {
  CompactBlocks();

  for (intptr_t i = 0; i < block_order().length(); ++i) {
    // Compile the block entry.
    BlockEntryInstr* entry = block_order()[i];
    assembler()->Comment("B%"Pd"", entry->block_id());
    set_current_block(entry);

    if (WasCompacted(entry)) {
      continue;
    }

    entry->EmitNativeCode(this);
    // Compile all successors until an exit, branch, or a block entry.
    for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
      Instruction* instr = it.Current();
      if (FLAG_code_comments) EmitComment(instr);
      if (instr->IsParallelMove()) {
        parallel_move_resolver_.EmitNativeCode(instr->AsParallelMove());
      } else {
        ASSERT(instr->locs() != NULL);
        EmitInstructionPrologue(instr);
        ASSERT(pending_deoptimization_env_ == NULL);
        pending_deoptimization_env_ = instr->env();
        instr->EmitNativeCode(this);
        pending_deoptimization_env_ = NULL;
        EmitInstructionEpilogue(instr);
      }
    }
  }
  set_current_block(NULL);
}


void FlowGraphCompiler::Bailout(const char* reason) {
  const char* kFormat = "FlowGraphCompiler Bailout: %s %s.";
  const char* function_name = parsed_function().function().ToCString();
  intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
  char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
  OS::SNPrint(chars, len, kFormat, function_name, reason);
  const Error& error = Error::Handle(
      LanguageError::New(String::Handle(String::New(chars))));
  Isolate::Current()->long_jump_base()->Jump(1, error);
}


intptr_t FlowGraphCompiler::StackSize() const {
  if (is_optimizing_) {
    return flow_graph_.graph_entry()->spill_slot_count();
  } else {
    return parsed_function_.num_stack_locals() +
        parsed_function_.num_copied_params();
  }
}


Label* FlowGraphCompiler::GetJumpLabel(
    BlockEntryInstr* block_entry) const {
  const intptr_t block_index = block_entry->postorder_number();
  return block_info_[block_index]->jump_label();
}


bool FlowGraphCompiler::WasCompacted(
    BlockEntryInstr* block_entry) const {
  const intptr_t block_index = block_entry->postorder_number();
  return block_info_[block_index]->WasCompacted();
}


bool FlowGraphCompiler::CanFallThroughTo(BlockEntryInstr* block_entry) const {
  const intptr_t current_index = current_block()->postorder_number();
  Label* fallthrough_label = block_info_[current_index]->fallthrough_label();
  return fallthrough_label == GetJumpLabel(block_entry);
}


void FlowGraphCompiler::AddSlowPathCode(SlowPathCode* code) {
  slow_path_code_.Add(code);
}


void FlowGraphCompiler::GenerateDeferredCode() {
  for (intptr_t i = 0; i < slow_path_code_.length(); i++) {
    slow_path_code_[i]->EmitNativeCode(this);
  }
  for (intptr_t i = 0; i < deopt_infos_.length(); i++) {
    deopt_infos_[i]->GenerateCode(this, i);
  }
}


void FlowGraphCompiler::AddExceptionHandler(intptr_t try_index,
                                            intptr_t outer_try_index,
                                            intptr_t pc_offset,
                                            const Array& handler_types) {
  exception_handlers_list_->AddHandler(try_index,
                                       outer_try_index,
                                       pc_offset,
                                       handler_types);
}


// Uses current pc position and try-index.
void FlowGraphCompiler::AddCurrentDescriptor(PcDescriptors::Kind kind,
                                             intptr_t deopt_id,
                                             intptr_t token_pos) {
  pc_descriptors_list()->AddDescriptor(kind,
                                       assembler()->CodeSize(),
                                       deopt_id,
                                       token_pos,
                                       CurrentTryIndex());
}


void FlowGraphCompiler::AddStaticCallTarget(const Function& func) {
  ASSERT(Code::kSCallTableEntryLength == 3);
  ASSERT(Code::kSCallTableOffsetEntry == 0);
  static_calls_target_table_.Add(
      Smi::Handle(Smi::New(assembler()->CodeSize())));
  ASSERT(Code::kSCallTableFunctionEntry == 1);
  static_calls_target_table_.Add(func);
  ASSERT(Code::kSCallTableCodeEntry == 2);
  static_calls_target_table_.Add(Code::Handle());
}


void FlowGraphCompiler::AddDeoptIndexAtCall(intptr_t deopt_id,
                                            intptr_t token_pos) {
  ASSERT(is_optimizing());
  CompilerDeoptInfo* info =
      new CompilerDeoptInfo(deopt_id,
                            kDeoptAtCall,
                            pending_deoptimization_env_);
  info->set_pc_offset(assembler()->CodeSize());
  deopt_infos_.Add(info);
}


void FlowGraphCompiler::RecordSafepoint(LocationSummary* locs) {
  if (is_optimizing()) {
    BitmapBuilder* bitmap = locs->stack_bitmap();
    ASSERT(bitmap != NULL);
    ASSERT(bitmap->Length() <= StackSize());
    // Pad the bitmap out to describe all the spill slots.
    bitmap->SetLength(StackSize());

    // Mark the bits in the stack map in the same order we push registers in
    // slow path code (see FlowGraphCompiler::SaveLiveRegisters).
    //
    // Slow path code can have registers at the safepoint.
    if (!locs->always_calls()) {
      RegisterSet* regs = locs->live_registers();
      if (regs->fpu_regs_count() > 0) {
        // Denote FPU registers with 0 bits in the stackmap.  Based on the
        // assumption that there are normally few live FPU registers, this
        // encoding is simpler and roughly as compact as storing a separate
        // count of FPU registers.
        //
        // FPU registers have the highest register number at the highest
        // address (i.e., first in the stackmap).
        const intptr_t kFpuRegisterSpillFactor =
            kFpuRegisterSize / kWordSize;
        for (intptr_t i = kNumberOfFpuRegisters - 1; i >= 0; --i) {
          FpuRegister reg = static_cast<FpuRegister>(i);
          if (regs->ContainsFpuRegister(reg)) {
            for (intptr_t j = 0; j < kFpuRegisterSpillFactor; ++j) {
              bitmap->Set(bitmap->Length(), false);
            }
          }
        }
      }
      // General purpose registers have the lowest register number at the
      // highest address (i.e., first in the stackmap).
      for (intptr_t i = 0; i < kNumberOfCpuRegisters; ++i) {
        Register reg = static_cast<Register>(i);
        if (locs->live_registers()->ContainsRegister(reg)) {
          bitmap->Set(bitmap->Length(), true);
        }
      }
    }

    intptr_t register_bit_count = bitmap->Length() - StackSize();
    stackmap_table_builder_->AddEntry(assembler()->CodeSize(),
                                      bitmap,
                                      register_bit_count);
  }
}


Label* FlowGraphCompiler::AddDeoptStub(intptr_t deopt_id,
                                       DeoptReasonId reason) {
  ASSERT(is_optimizing_);
  CompilerDeoptInfoWithStub* stub =
      new CompilerDeoptInfoWithStub(deopt_id,
                                    reason,
                                    pending_deoptimization_env_);
  deopt_infos_.Add(stub);
  return stub->entry_label();
}


void FlowGraphCompiler::FinalizeExceptionHandlers(const Code& code) {
  ASSERT(exception_handlers_list_ != NULL);
  const ExceptionHandlers& handlers = ExceptionHandlers::Handle(
      exception_handlers_list_->FinalizeExceptionHandlers(code.EntryPoint()));
  code.set_exception_handlers(handlers);
}


void FlowGraphCompiler::FinalizePcDescriptors(const Code& code) {
  ASSERT(pc_descriptors_list_ != NULL);
  const PcDescriptors& descriptors = PcDescriptors::Handle(
      pc_descriptors_list_->FinalizePcDescriptors(code.EntryPoint()));
  if (!is_optimizing_) descriptors.Verify(parsed_function_.function());
  code.set_pc_descriptors(descriptors);
}


void FlowGraphCompiler::FinalizeDeoptInfo(const Code& code) {
  // For functions with optional arguments, all incoming arguments are copied
  // to spill slots. The deoptimization environment does not track them.
  const Function& function = parsed_function().function();
  const intptr_t incoming_arg_count =
      function.HasOptionalParameters() ? 0 : function.num_fixed_parameters();
  DeoptInfoBuilder builder(incoming_arg_count);

  const Array& array =
      Array::Handle(Array::New(DeoptTable::SizeFor(deopt_infos_.length()),
                               Heap::kOld));
  Smi& offset = Smi::Handle();
  DeoptInfo& info = DeoptInfo::Handle();
  Smi& reason = Smi::Handle();
  for (intptr_t i = 0; i < deopt_infos_.length(); i++) {
    offset = Smi::New(deopt_infos_[i]->pc_offset());
    info = deopt_infos_[i]->CreateDeoptInfo(this, &builder);
    reason = Smi::New(deopt_infos_[i]->reason());
    DeoptTable::SetEntry(array, i, offset, info, reason);
  }
  code.set_deopt_info_array(array);
  const Array& object_array =
      Array::Handle(Array::MakeArray(builder.object_table()));
  ASSERT(code.object_table() == Array::null());
  code.set_object_table(object_array);
}


void FlowGraphCompiler::FinalizeStackmaps(const Code& code) {
  if (stackmap_table_builder_ == NULL) {
    // The unoptimizing compiler has no stack maps.
    code.set_stackmaps(Array::Handle());
  } else {
    // Finalize the stack map array and add it to the code object.
    ASSERT(is_optimizing());
    code.set_stackmaps(
        Array::Handle(stackmap_table_builder_->FinalizeStackmaps(code)));
  }
}


void FlowGraphCompiler::FinalizeVarDescriptors(const Code& code) {
  const LocalVarDescriptors& var_descs = LocalVarDescriptors::Handle(
          parsed_function_.node_sequence()->scope()->GetVarDescriptors(
              parsed_function_.function()));
  code.set_var_descriptors(var_descs);
}


void FlowGraphCompiler::FinalizeComments(const Code& code) {
  code.set_comments(assembler()->GetCodeComments());
}


void FlowGraphCompiler::FinalizeStaticCallTargetsTable(const Code& code) {
  ASSERT(code.static_calls_target_table() == Array::null());
  code.set_static_calls_target_table(
      Array::Handle(Array::MakeArray(static_calls_target_table_)));
}


// Returns 'true' if code generation for this function is complete, i.e.,
// no fall-through to regular code is needed.
bool FlowGraphCompiler::TryIntrinsify() {
  if (!CanOptimizeFunction()) return false;
  // Intrinsification skips arguments checks, therefore disable if in checked
  // mode.
  if (FLAG_intrinsify && !FLAG_enable_type_checks) {
    if (parsed_function().function().kind() == RawFunction::kImplicitGetter) {
      // An implicit getter must have a specific AST structure.
      const SequenceNode& sequence_node = *parsed_function().node_sequence();
      ASSERT(sequence_node.length() == 1);
      ASSERT(sequence_node.NodeAt(0)->IsReturnNode());
      const ReturnNode& return_node = *sequence_node.NodeAt(0)->AsReturnNode();
      ASSERT(return_node.value()->IsLoadInstanceFieldNode());
      const LoadInstanceFieldNode& load_node =
          *return_node.value()->AsLoadInstanceFieldNode();
      GenerateInlinedGetter(load_node.field().Offset());
      return true;
    }
    if (parsed_function().function().kind() == RawFunction::kImplicitSetter) {
      // An implicit setter must have a specific AST structure.
      // Sequence node has one store node and one return NULL node.
      const SequenceNode& sequence_node = *parsed_function().node_sequence();
      ASSERT(sequence_node.length() == 2);
      ASSERT(sequence_node.NodeAt(0)->IsStoreInstanceFieldNode());
      ASSERT(sequence_node.NodeAt(1)->IsReturnNode());
      const StoreInstanceFieldNode& store_node =
          *sequence_node.NodeAt(0)->AsStoreInstanceFieldNode();
      if (store_node.field().guarded_cid() == kDynamicCid) {
        GenerateInlinedSetter(store_node.field().Offset());
        return true;
      }
    }
  }
  // Even if an intrinsified version of the function was successfully
  // generated, it may fall through to the non-intrinsified method body.
  return Intrinsifier::Intrinsify(parsed_function().function(), assembler());
}


void FlowGraphCompiler::GenerateInstanceCall(
    intptr_t deopt_id,
    intptr_t token_pos,
    intptr_t argument_count,
    const Array& argument_names,
    LocationSummary* locs,
    const ICData& ic_data) {
  ASSERT(!ic_data.IsNull());
  ASSERT(FLAG_propagate_ic_data || (ic_data.NumberOfChecks() == 0));
  const Array& arguments_descriptor =
      Array::ZoneHandle(ArgumentsDescriptor::New(argument_count,
                                                 argument_names));
  uword label_address = 0;
  if (is_optimizing() && (ic_data.NumberOfChecks() == 0)) {
    if (ic_data.is_closure_call()) {
      // This IC call may be closure call only.
      label_address = StubCode::ClosureCallInlineCacheEntryPoint();
      ExternalLabel target_label("InlineCache", label_address);
      EmitInstanceCall(&target_label,
                       ICData::ZoneHandle(ic_data.AsUnaryClassChecks()),
                       arguments_descriptor, argument_count,
                       deopt_id, token_pos, locs);
      return;
    }
    // Emit IC call that will count and thus may need reoptimization at
    // function entry.
    ASSERT(!is_optimizing() || may_reoptimize());
    switch (ic_data.num_args_tested()) {
      case 1:
        label_address = StubCode::OneArgOptimizedCheckInlineCacheEntryPoint();
        break;
      case 2:
        label_address = StubCode::TwoArgsOptimizedCheckInlineCacheEntryPoint();
        break;
      case 3:
        label_address =
            StubCode::ThreeArgsOptimizedCheckInlineCacheEntryPoint();
        break;
      default:
        UNIMPLEMENTED();
    }
    ExternalLabel target_label("InlineCache", label_address);
    EmitOptimizedInstanceCall(&target_label, ic_data, arguments_descriptor,
                              argument_count, deopt_id, token_pos, locs);
    return;
  }

  if (is_optimizing()) {
    EmitMegamorphicInstanceCall(ic_data, arguments_descriptor, argument_count,
                                deopt_id, token_pos, locs);
    return;
  }

  switch (ic_data.num_args_tested()) {
    case 1:
      label_address = StubCode::OneArgCheckInlineCacheEntryPoint();
      break;
    case 2:
      label_address = StubCode::TwoArgsCheckInlineCacheEntryPoint();
      break;
    case 3:
      label_address = StubCode::ThreeArgsCheckInlineCacheEntryPoint();
      break;
    default:
      UNIMPLEMENTED();
  }
  ExternalLabel target_label("InlineCache", label_address);
  EmitInstanceCall(&target_label, ic_data, arguments_descriptor, argument_count,
                   deopt_id, token_pos, locs);
}


void FlowGraphCompiler::GenerateStaticCall(intptr_t deopt_id,
                                           intptr_t token_pos,
                                           const Function& function,
                                           intptr_t argument_count,
                                           const Array& argument_names,
                                           LocationSummary* locs) {
  const Array& arguments_descriptor =
      Array::ZoneHandle(ArgumentsDescriptor::New(argument_count,
                                                 argument_names));
  EmitStaticCall(function, arguments_descriptor, argument_count,
                 deopt_id, token_pos, locs);
}


void FlowGraphCompiler::GenerateNumberTypeCheck(Register kClassIdReg,
                                                const AbstractType& type,
                                                Label* is_instance_lbl,
                                                Label* is_not_instance_lbl) {
  assembler()->Comment("NumberTypeCheck");
  GrowableArray<intptr_t> args;
  if (type.IsNumberType()) {
    args.Add(kDoubleCid);
    args.Add(kMintCid);
    args.Add(kBigintCid);
  } else if (type.IsIntType()) {
    args.Add(kMintCid);
    args.Add(kBigintCid);
  } else if (type.IsDoubleType()) {
    args.Add(kDoubleCid);
  }
  CheckClassIds(kClassIdReg, args, is_instance_lbl, is_not_instance_lbl);
}


void FlowGraphCompiler::GenerateStringTypeCheck(Register kClassIdReg,
                                                Label* is_instance_lbl,
                                                Label* is_not_instance_lbl) {
  assembler()->Comment("StringTypeCheck");
  GrowableArray<intptr_t> args;
  args.Add(kOneByteStringCid);
  args.Add(kTwoByteStringCid);
  args.Add(kExternalOneByteStringCid);
  args.Add(kExternalTwoByteStringCid);
  CheckClassIds(kClassIdReg, args, is_instance_lbl, is_not_instance_lbl);
}


void FlowGraphCompiler::GenerateListTypeCheck(Register kClassIdReg,
                                              Label* is_instance_lbl) {
  assembler()->Comment("ListTypeCheck");
  Label unknown;
  GrowableArray<intptr_t> args;
  args.Add(kArrayCid);
  args.Add(kGrowableObjectArrayCid);
  args.Add(kImmutableArrayCid);
  CheckClassIds(kClassIdReg, args, is_instance_lbl, &unknown);
  assembler()->Bind(&unknown);
}


void FlowGraphCompiler::EmitComment(Instruction* instr) {
  char buffer[256];
  BufferFormatter f(buffer, sizeof(buffer));
  instr->PrintTo(&f);
  assembler()->Comment("%s", buffer);
}


// Allocate a register that is not explicitly blocked.
static Register AllocateFreeRegister(bool* blocked_registers) {
  for (intptr_t regno = 0; regno < kNumberOfCpuRegisters; regno++) {
    if (!blocked_registers[regno]) {
      blocked_registers[regno] = true;
      return static_cast<Register>(regno);
    }
  }
  UNREACHABLE();
  return kNoRegister;
}


void FlowGraphCompiler::AllocateRegistersLocally(Instruction* instr) {
  ASSERT(!is_optimizing());

  LocationSummary* locs = instr->locs();

  bool blocked_registers[kNumberOfCpuRegisters];

  // Mark all available registers free.
  for (intptr_t i = 0; i < kNumberOfCpuRegisters; i++) {
    blocked_registers[i] = false;
  }

  // Mark all fixed input, temp and output registers as used.
  for (intptr_t i = 0; i < locs->input_count(); i++) {
    Location loc = locs->in(i);
    if (loc.IsRegister()) {
      // Check that a register is not specified twice in the summary.
      ASSERT(!blocked_registers[loc.reg()]);
      blocked_registers[loc.reg()] = true;
    }
  }

  for (intptr_t i = 0; i < locs->temp_count(); i++) {
    Location loc = locs->temp(i);
    if (loc.IsRegister()) {
      // Check that a register is not specified twice in the summary.
      ASSERT(!blocked_registers[loc.reg()]);
      blocked_registers[loc.reg()] = true;
    }
  }

  if (locs->out().IsRegister()) {
    // Fixed output registers are allowed to overlap with
    // temps and inputs.
    blocked_registers[locs->out().reg()] = true;
  }

  // Do not allocate known registers.
  blocked_registers[CTX] = true;
  blocked_registers[SPREG] = true;
  blocked_registers[FPREG] = true;
  if (TMP != kNoRegister) {
    blocked_registers[TMP] = true;
  }
  if (PP != kNoRegister) {
    blocked_registers[PP] = true;
  }

  // Block all non-free registers.
  for (intptr_t i = 0; i < kFirstFreeCpuRegister; i++) {
    blocked_registers[i] = true;
  }
  for (intptr_t i = kLastFreeCpuRegister + 1; i < kNumberOfCpuRegisters; i++) {
    blocked_registers[i] = true;
  }

  // Allocate all unallocated input locations.
  const bool should_pop = !instr->IsPushArgument() && !instr->IsPushTemp();
  for (intptr_t i = locs->input_count() - 1; i >= 0; i--) {
    Location loc = locs->in(i);
    Register reg = kNoRegister;
    if (loc.IsRegister()) {
      reg = loc.reg();
    } else if (loc.IsUnallocated() || loc.IsConstant()) {
      ASSERT(loc.IsConstant() ||
             ((loc.policy() == Location::kRequiresRegister) ||
              (loc.policy() == Location::kWritableRegister) ||
              (loc.policy() == Location::kAny)));
      reg = AllocateFreeRegister(blocked_registers);
      locs->set_in(i, Location::RegisterLocation(reg));
    }
    ASSERT(reg != kNoRegister);

    // Inputs are consumed from the simulated frame. In case of a call argument
    // we leave it until the call instruction.
    if (should_pop) {
      assembler()->PopRegister(reg);
    }
  }

  // Allocate all unallocated temp locations.
  for (intptr_t i = 0; i < locs->temp_count(); i++) {
    Location loc = locs->temp(i);
    if (loc.IsUnallocated()) {
      ASSERT(loc.policy() == Location::kRequiresRegister);
      loc = Location::RegisterLocation(
        AllocateFreeRegister(blocked_registers));
      locs->set_temp(i, loc);
    }
  }

  Location result_location = locs->out();
  if (result_location.IsUnallocated()) {
    switch (result_location.policy()) {
      case Location::kAny:
      case Location::kPrefersRegister:
      case Location::kRequiresRegister:
      case Location::kWritableRegister:
        result_location = Location::RegisterLocation(
            AllocateFreeRegister(blocked_registers));
        break;
      case Location::kSameAsFirstInput:
        result_location = locs->in(0);
        break;
      case Location::kRequiresFpuRegister:
        UNREACHABLE();
        break;
    }
    locs->set_out(result_location);
  }
}


ParallelMoveResolver::ParallelMoveResolver(FlowGraphCompiler* compiler)
    : compiler_(compiler), moves_(32) {}


void ParallelMoveResolver::EmitNativeCode(ParallelMoveInstr* parallel_move) {
  ASSERT(moves_.is_empty());
  // Build up a worklist of moves.
  BuildInitialMoveList(parallel_move);

  for (int i = 0; i < moves_.length(); ++i) {
    const MoveOperands& move = *moves_[i];
    // Skip constants to perform them last.  They don't block other moves
    // and skipping such moves with register destinations keeps those
    // registers free for the whole algorithm.
    if (!move.IsEliminated() && !move.src().IsConstant()) PerformMove(i);
  }

  // Perform the moves with constant sources.
  for (int i = 0; i < moves_.length(); ++i) {
    const MoveOperands& move = *moves_[i];
    if (!move.IsEliminated()) {
      ASSERT(move.src().IsConstant());
      EmitMove(i);
    }
  }

  moves_.Clear();
}


void ParallelMoveResolver::BuildInitialMoveList(
    ParallelMoveInstr* parallel_move) {
  // Perform a linear sweep of the moves to add them to the initial list of
  // moves to perform, ignoring any move that is redundant (the source is
  // the same as the destination, the destination is ignored and
  // unallocated, or the move was already eliminated).
  for (int i = 0; i < parallel_move->NumMoves(); i++) {
    MoveOperands* move = parallel_move->MoveOperandsAt(i);
    if (!move->IsRedundant()) moves_.Add(move);
  }
}


void ParallelMoveResolver::PerformMove(int index) {
  // Each call to this function performs a move and deletes it from the move
  // graph.  We first recursively perform any move blocking this one.  We
  // mark a move as "pending" on entry to PerformMove in order to detect
  // cycles in the move graph.  We use operand swaps to resolve cycles,
  // which means that a call to PerformMove could change any source operand
  // in the move graph.

  ASSERT(!moves_[index]->IsPending());
  ASSERT(!moves_[index]->IsRedundant());

  // Clear this move's destination to indicate a pending move.  The actual
  // destination is saved in a stack-allocated local.  Recursion may allow
  // multiple moves to be pending.
  ASSERT(!moves_[index]->src().IsInvalid());
  Location destination = moves_[index]->MarkPending();

  // Perform a depth-first traversal of the move graph to resolve
  // dependencies.  Any unperformed, unpending move with a source the same
  // as this one's destination blocks this one so recursively perform all
  // such moves.
  for (int i = 0; i < moves_.length(); ++i) {
    const MoveOperands& other_move = *moves_[i];
    if (other_move.Blocks(destination) && !other_move.IsPending()) {
      // Though PerformMove can change any source operand in the move graph,
      // this call cannot create a blocking move via a swap (this loop does
      // not miss any).  Assume there is a non-blocking move with source A
      // and this move is blocked on source B and there is a swap of A and
      // B.  Then A and B must be involved in the same cycle (or they would
      // not be swapped).  Since this move's destination is B and there is
      // only a single incoming edge to an operand, this move must also be
      // involved in the same cycle.  In that case, the blocking move will
      // be created but will be "pending" when we return from PerformMove.
      PerformMove(i);
    }
  }

  // We are about to resolve this move and don't need it marked as
  // pending, so restore its destination.
  moves_[index]->ClearPending(destination);

  // This move's source may have changed due to swaps to resolve cycles and
  // so it may now be the last move in the cycle.  If so remove it.
  if (moves_[index]->src().Equals(destination)) {
    moves_[index]->Eliminate();
    return;
  }

  // The move may be blocked on a (at most one) pending move, in which case
  // we have a cycle.  Search for such a blocking move and perform a swap to
  // resolve it.
  for (int i = 0; i < moves_.length(); ++i) {
    const MoveOperands& other_move = *moves_[i];
    if (other_move.Blocks(destination)) {
      ASSERT(other_move.IsPending());
      EmitSwap(index);
      return;
    }
  }

  // This move is not blocked.
  EmitMove(index);
}


bool ParallelMoveResolver::IsScratchLocation(Location loc) {
  for (int i = 0; i < moves_.length(); ++i) {
    if (moves_[i]->Blocks(loc)) {
      return false;
    }
  }

  for (int i = 0; i < moves_.length(); ++i) {
    if (moves_[i]->dest().Equals(loc)) {
      return true;
    }
  }

  return false;
}


intptr_t ParallelMoveResolver::AllocateScratchRegister(Location::Kind kind,
                                                       intptr_t blocked,
                                                       intptr_t register_count,
                                                       bool* spilled) {
  intptr_t scratch = -1;
  for (intptr_t reg = 0; reg < register_count; reg++) {
    if ((blocked != reg) &&
        IsScratchLocation(Location::MachineRegisterLocation(kind, reg))) {
      scratch = reg;
      break;
    }
  }

  if (scratch == -1) {
    *spilled = true;
    for (intptr_t reg = 0; reg < register_count; reg++) {
      if (blocked != reg) {
        scratch = reg;
      }
    }
  } else {
    *spilled = false;
  }

  return scratch;
}


ParallelMoveResolver::ScratchFpuRegisterScope::ScratchFpuRegisterScope(
    ParallelMoveResolver* resolver, FpuRegister blocked)
    : resolver_(resolver),
      reg_(kNoFpuRegister),
      spilled_(false) {
  reg_ = static_cast<FpuRegister>(
      resolver_->AllocateScratchRegister(Location::kFpuRegister,
                                         blocked,
                                         kNumberOfFpuRegisters,
                                         &spilled_));

  if (spilled_) {
    resolver->SpillFpuScratch(reg_);
  }
}


ParallelMoveResolver::ScratchFpuRegisterScope::~ScratchFpuRegisterScope() {
  if (spilled_) {
    resolver_->RestoreFpuScratch(reg_);
  }
}


ParallelMoveResolver::ScratchRegisterScope::ScratchRegisterScope(
    ParallelMoveResolver* resolver, Register blocked)
    : resolver_(resolver),
      reg_(kNoRegister),
      spilled_(false) {
  reg_ = static_cast<Register>(
      resolver_->AllocateScratchRegister(Location::kRegister,
                                         blocked,
                                         kNumberOfCpuRegisters,
                                         &spilled_));

  if (spilled_) {
    resolver->SpillScratch(reg_);
  }
}


ParallelMoveResolver::ScratchRegisterScope::~ScratchRegisterScope() {
  if (spilled_) {
    resolver_->RestoreScratch(reg_);
  }
}


intptr_t FlowGraphCompiler::ElementSizeFor(intptr_t cid) {
  if (RawObject::IsExternalTypedDataClassId(cid)) {
    return ExternalTypedData::ElementSizeInBytes(cid);
  } else if (RawObject::IsTypedDataClassId(cid)) {
    return TypedData::ElementSizeInBytes(cid);
  }
  switch (cid) {
    case kArrayCid:
    case kImmutableArrayCid:
      return Array::kBytesPerElement;
    case kOneByteStringCid:
      return OneByteString::kBytesPerElement;
    case kTwoByteStringCid:
      return TwoByteString::kBytesPerElement;
    default:
      UNIMPLEMENTED();
      return 0;
  }
}


intptr_t FlowGraphCompiler::DataOffsetFor(intptr_t cid) {
  if (RawObject::IsExternalTypedDataClassId(cid)) {
    // Elements start at offset 0 of the external data.
    return 0;
  }
  if (RawObject::IsTypedDataClassId(cid)) {
    return TypedData::data_offset();
  }
  switch (cid) {
    case kArrayCid:
    case kImmutableArrayCid:
      return Array::data_offset();
    case kOneByteStringCid:
      return OneByteString::data_offset();
    case kTwoByteStringCid:
      return TwoByteString::data_offset();
    default:
      UNIMPLEMENTED();
      return Array::data_offset();
  }
}


// Returns true if checking against this type is a direct class id comparison.
bool FlowGraphCompiler::TypeCheckAsClassEquality(const AbstractType& type) {
  ASSERT(type.IsFinalized() && !type.IsMalformed());
  // Requires CHA, which can be applied in optimized code only,
  if (!FLAG_use_cha || !is_optimizing()) return false;
  if (!type.IsInstantiated()) return false;
  const Class& type_class = Class::Handle(type.type_class());
  // Signature classes have different type checking rules.
  if (type_class.IsSignatureClass()) return false;
  // Could be an interface check?
  if (type_class.is_implemented()) return false;
  const intptr_t type_cid = type_class.id();
  if (CHA::HasSubclasses(type_cid)) return false;
  if (type_class.HasTypeArguments()) {
    // Only raw types can be directly compared, thus disregarding type
    // arguments.
    const AbstractTypeArguments& type_arguments =
        AbstractTypeArguments::Handle(type.arguments());
    const bool is_raw_type = type_arguments.IsNull() ||
        type_arguments.IsRaw(type_arguments.Length());
    return is_raw_type;
  }
  return true;
}


static int HighestCountFirst(const CidTarget* a, const CidTarget* b) {
  // Negative if 'a' should sort before 'b'.
  return b->count - a->count;
}


// Returns 'sorted' array in decreasing count order.
// The expected number of elements to sort is less than 10.
void FlowGraphCompiler::SortICDataByCount(const ICData& ic_data,
                                          GrowableArray<CidTarget>* sorted) {
  ASSERT(ic_data.num_args_tested() == 1);
  const intptr_t len = ic_data.NumberOfChecks();
  sorted->Clear();

  for (int i = 0; i < len; i++) {
    sorted->Add(CidTarget(ic_data.GetReceiverClassIdAt(i),
                          &Function::ZoneHandle(ic_data.GetTargetAt(i)),
                          ic_data.GetCountAt(i)));
  }
  sorted->Sort(HighestCountFirst);
}

}  // namespace dart