/*

 * Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "c1/c1_Instruction.hpp"

#include "c1/c1_LinearScan.hpp"

#include "utilities/bitMap.inline.hpp"

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

// Allocation of FPU stack slots (Intel x86 only)

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

void LinearScan::allocate_fpu_stack() {

  // First compute which FPU registers are live at the start of each basic block

  // (To minimize the amount of work we have to do if we have to merge FPU stacks)

  if (ComputeExactFPURegisterUsage) {

    Interval* intervals_in_register, *intervals_in_memory;

    create_unhandled_lists(&intervals_in_register, &intervals_in_memory, is_in_fpu_register, NULL);

    // ignore memory intervals by overwriting intervals_in_memory

    // the dummy interval is needed to enforce the walker to walk until the given id:

    // without it, the walker stops when the unhandled-list is empty -> live information

    // beyond this point would be incorrect.

    Interval* dummy_interval = new Interval(any_reg);

    dummy_interval->add_range(max_jint - 2, max_jint - 1);

    dummy_interval->set_next(Interval::end());

    intervals_in_memory = dummy_interval;

    IntervalWalker iw(this, intervals_in_register, intervals_in_memory);

    const int num_blocks = block_count();

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

      BlockBegin* b = block_at(i);

      // register usage is only needed for merging stacks -> compute only

      // when more than one predecessor.

      // the block must not have any spill moves at the beginning (checked by assertions)

      // spill moves would use intervals that are marked as handled and so the usage bit

      // would been set incorrectly

      // NOTE: the check for number_of_preds > 1 is necessary. A block with only one

      //       predecessor may have spill moves at the begin of the block.

      //       If an interval ends at the current instruction id, it is not possible

      //       to decide if the register is live or not at the block begin -> the

      //       register information would be incorrect.

      if (b->number_of_preds() > 1) {

        int id = b->first_lir_instruction_id();

        BitMap regs(FrameMap::nof_fpu_regs);

        regs.clear();

        iw.walk_to(id);   // walk after the first instruction (always a label) of the block

        assert(iw.current_position() == id, "did not walk completely to id");

        // Only consider FPU values in registers

        Interval* interval = iw.active_first(fixedKind);

        while (interval != Interval::end()) {

          int reg = interval->assigned_reg();

          assert(reg >= pd_first_fpu_reg && reg <= pd_last_fpu_reg, "no fpu register");

          assert(interval->assigned_regHi() == -1, "must not have hi register (doubles stored in one register)");

          assert(interval->from() <= id && id < interval->to(), "interval out of range");

#ifndef PRODUCT

          if (TraceFPURegisterUsage) {

            tty->print("fpu reg %d is live because of ", reg - pd_first_fpu_reg); interval->print();

          }

#endif

          regs.set_bit(reg - pd_first_fpu_reg);

          interval = interval->next();

        }

        b->set_fpu_register_usage(regs);

#ifndef PRODUCT

        if (TraceFPURegisterUsage) {

          tty->print("FPU regs for block %d, LIR instr %d): ", b->block_id(), id); regs.print_on(tty); tty->print_cr("");

        }

#endif

      }

    }

  }

  FpuStackAllocator alloc(ir()->compilation(), this);

  _fpu_stack_allocator = &alloc;

  alloc.allocate();

  _fpu_stack_allocator = NULL;

}

FpuStackAllocator::FpuStackAllocator(Compilation* compilation, LinearScan* allocator)

  : _compilation(compilation)

  , _lir(NULL)

  , _pos(-1)

  , _allocator(allocator)

  , _sim(compilation)

  , _temp_sim(compilation)

{}

void FpuStackAllocator::allocate() {

  int num_blocks = allocator()->block_count();

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

    // Set up to process block

    BlockBegin* block = allocator()->block_at(i);

    intArray* fpu_stack_state = block->fpu_stack_state();

#ifndef PRODUCT

    if (TraceFPUStack) {

      tty->cr();

      tty->print_cr("------- Begin of new Block %d -------", block->block_id());

    }

#endif

    assert(fpu_stack_state != NULL ||

           block->end()->as_Base() != NULL ||

           block->is_set(BlockBegin::exception_entry_flag),

           "FPU stack state must be present due to linear-scan order for FPU stack allocation");

    // note: exception handler entries always start with an empty fpu stack

    //       because stack merging would be too complicated

    if (fpu_stack_state != NULL) {

      sim()->read_state(fpu_stack_state);

    } else {

      sim()->clear();

    }

#ifndef PRODUCT

    if (TraceFPUStack) {

      tty->print("Reading FPU state for block %d:", block->block_id());

      sim()->print();

      tty->cr();

    }

#endif

    allocate_block(block);

    CHECK_BAILOUT();

  }

}

void FpuStackAllocator::allocate_block(BlockBegin* block) {

  bool processed_merge = false;

  LIR_OpList* insts = block->lir()->instructions_list();

  set_lir(block->lir());

  set_pos(0);

  // Note: insts->length() may change during loop

  while (pos() < insts->length()) {

    LIR_Op* op = insts->at(pos());

    _debug_information_computed = false;

#ifndef PRODUCT

    if (TraceFPUStack) {

      op->print();

    }

    check_invalid_lir_op(op);

#endif

    LIR_OpBranch* branch = op->as_OpBranch();

    LIR_Op1* op1 = op->as_Op1();

    LIR_Op2* op2 = op->as_Op2();

    LIR_OpCall* opCall = op->as_OpCall();

    if (branch != NULL && branch->block() != NULL) {

      if (!processed_merge) {

        // propagate stack at first branch to a successor

        processed_merge = true;

        bool required_merge = merge_fpu_stack_with_successors(block);

        assert(!required_merge || branch->cond() == lir_cond_always, "splitting of critical edges should prevent FPU stack mismatches at cond branches");

      }

    } else if (op1 != NULL) {

      handle_op1(op1);

    } else if (op2 != NULL) {

      handle_op2(op2);

    } else if (opCall != NULL) {

      handle_opCall(opCall);

    }

    compute_debug_information(op);

    set_pos(1 + pos());

  }

  // Propagate stack when block does not end with branch

  if (!processed_merge) {

    merge_fpu_stack_with_successors(block);

  }

}

void FpuStackAllocator::compute_debug_information(LIR_Op* op) {

  if (!_debug_information_computed && op->id() != -1 && allocator()->has_info(op->id())) {

    visitor.visit(op);

    // exception handling

    if (allocator()->compilation()->has_exception_handlers()) {

      XHandlers* xhandlers = visitor.all_xhandler();

      int n = xhandlers->length();

      for (int k = 0; k < n; k++) {

        allocate_exception_handler(xhandlers->handler_at(k));

      }

    } else {

      assert(visitor.all_xhandler()->length() == 0, "missed exception handler");

    }

    // compute debug information

    int n = visitor.info_count();

    assert(n > 0, "should not visit operation otherwise");

    for (int j = 0; j < n; j++) {

      CodeEmitInfo* info = visitor.info_at(j);

      // Compute debug information

      allocator()->compute_debug_info(info, op->id());

    }

  }

  _debug_information_computed = true;

}

void FpuStackAllocator::allocate_exception_handler(XHandler* xhandler) {

  if (!sim()->is_empty()) {

    LIR_List* old_lir = lir();

    int old_pos = pos();

    intArray* old_state = sim()->write_state();

#ifndef PRODUCT

    if (TraceFPUStack) {

      tty->cr();

      tty->print_cr("------- begin of exception handler -------");

    }

#endif

    if (xhandler->entry_code() == NULL) {

      // need entry code to clear FPU stack

      LIR_List* entry_code = new LIR_List(_compilation);

      entry_code->jump(xhandler->entry_block());

      xhandler->set_entry_code(entry_code);

    }

    LIR_OpList* insts = xhandler->entry_code()->instructions_list();

    set_lir(xhandler->entry_code());

    set_pos(0);

    // Note: insts->length() may change during loop

    while (pos() < insts->length()) {

      LIR_Op* op = insts->at(pos());

#ifndef PRODUCT

      if (TraceFPUStack) {

        op->print();

      }

      check_invalid_lir_op(op);

#endif

      switch (op->code()) {

        case lir_move:

          assert(op->as_Op1() != NULL, "must be LIR_Op1");

          assert(pos() != insts->length() - 1, "must not be last operation");

          handle_op1((LIR_Op1*)op);

          break;

        case lir_branch:

          assert(op->as_OpBranch()->cond() == lir_cond_always, "must be unconditional branch");

          assert(pos() == insts->length() - 1, "must be last operation");

          // remove all remaining dead registers from FPU stack

          clear_fpu_stack(LIR_OprFact::illegalOpr);

          break;

        default:

          // other operations not allowed in exception entry code

          ShouldNotReachHere();

      }

      set_pos(pos() + 1);

    }

#ifndef PRODUCT

    if (TraceFPUStack) {

      tty->cr();

      tty->print_cr("------- end of exception handler -------");

    }

#endif

    set_lir(old_lir);

    set_pos(old_pos);

    sim()->read_state(old_state);

  }

}

int FpuStackAllocator::fpu_num(LIR_Opr opr) {

  assert(opr->is_fpu_register() && !opr->is_xmm_register(), "shouldn't call this otherwise");

  return opr->is_single_fpu() ? opr->fpu_regnr() : opr->fpu_regnrLo();

}

int FpuStackAllocator::tos_offset(LIR_Opr opr) {

  return sim()->offset_from_tos(fpu_num(opr));

}

LIR_Opr FpuStackAllocator::to_fpu_stack(LIR_Opr opr) {

  assert(opr->is_fpu_register() && !opr->is_xmm_register(), "shouldn't call this otherwise");

  int stack_offset = tos_offset(opr);

  if (opr->is_single_fpu()) {

    return LIR_OprFact::single_fpu(stack_offset)->make_fpu_stack_offset();

  } else {

    assert(opr->is_double_fpu(), "shouldn't call this otherwise");

    return LIR_OprFact::double_fpu(stack_offset)->make_fpu_stack_offset();

  }

}

LIR_Opr FpuStackAllocator::to_fpu_stack_top(LIR_Opr opr, bool dont_check_offset) {

  assert(opr->is_fpu_register() && !opr->is_xmm_register(), "shouldn't call this otherwise");

  assert(dont_check_offset || tos_offset(opr) == 0, "operand is not on stack top");

  int stack_offset = 0;

  if (opr->is_single_fpu()) {

    return LIR_OprFact::single_fpu(stack_offset)->make_fpu_stack_offset();

  } else {

    assert(opr->is_double_fpu(), "shouldn't call this otherwise");

    return LIR_OprFact::double_fpu(stack_offset)->make_fpu_stack_offset();

  }

}

void FpuStackAllocator::insert_op(LIR_Op* op) {

  lir()->insert_before(pos(), op);

  set_pos(1 + pos());

}

void FpuStackAllocator::insert_exchange(int offset) {

  if (offset > 0) {

    LIR_Op1* fxch_op = new LIR_Op1(lir_fxch, LIR_OprFact::intConst(offset), LIR_OprFact::illegalOpr);

    insert_op(fxch_op);

    sim()->swap(offset);

#ifndef PRODUCT

    if (TraceFPUStack) {

      tty->print("Exchanged register: %d         New state: ", sim()->get_slot(0)); sim()->print(); tty->cr();

    }

#endif

  }

}

void FpuStackAllocator::insert_exchange(LIR_Opr opr) {

  insert_exchange(tos_offset(opr));

}

void FpuStackAllocator::insert_free(int offset) {

  // move stack slot to the top of stack and then pop it

  insert_exchange(offset);

  LIR_Op* fpop = new LIR_Op0(lir_fpop_raw);

  insert_op(fpop);

  sim()->pop();

#ifndef PRODUCT

    if (TraceFPUStack) {

      tty->print("Inserted pop                   New state: "); sim()->print(); tty->cr();

    }

#endif

}

void FpuStackAllocator::insert_free_if_dead(LIR_Opr opr) {

  if (sim()->contains(fpu_num(opr))) {

    int res_slot = tos_offset(opr);

    insert_free(res_slot);

  }

}

void FpuStackAllocator::insert_free_if_dead(LIR_Opr opr, LIR_Opr ignore) {

  if (fpu_num(opr) != fpu_num(ignore) && sim()->contains(fpu_num(opr))) {

    int res_slot = tos_offset(opr);

    insert_free(res_slot);

  }

}

void FpuStackAllocator::insert_copy(LIR_Opr from, LIR_Opr to) {

  int offset = tos_offset(from);

  LIR_Op1* fld = new LIR_Op1(lir_fld, LIR_OprFact::intConst(offset), LIR_OprFact::illegalOpr);

  insert_op(fld);

  sim()->push(fpu_num(to));

#ifndef PRODUCT

  if (TraceFPUStack) {

    tty->print("Inserted copy (%d -> %d)         New state: ", fpu_num(from), fpu_num(to)); sim()->print(); tty->cr();

  }

#endif

}

void FpuStackAllocator::do_rename(LIR_Opr from, LIR_Opr to) {

  sim()->rename(fpu_num(from), fpu_num(to));

}

void FpuStackAllocator::do_push(LIR_Opr opr) {

  sim()->push(fpu_num(opr));

}

void FpuStackAllocator::pop_if_last_use(LIR_Op* op, LIR_Opr opr) {

  assert(op->fpu_pop_count() == 0, "fpu_pop_count alredy set");

  assert(tos_offset(opr) == 0, "can only pop stack top");

  if (opr->is_last_use()) {

    op->set_fpu_pop_count(1);

    sim()->pop();

  }

}

void FpuStackAllocator::pop_always(LIR_Op* op, LIR_Opr opr) {

  assert(op->fpu_pop_count() == 0, "fpu_pop_count alredy set");

  assert(tos_offset(opr) == 0, "can only pop stack top");

  op->set_fpu_pop_count(1);

  sim()->pop();

}

void FpuStackAllocator::clear_fpu_stack(LIR_Opr preserve) {

  int result_stack_size = (preserve->is_fpu_register() && !preserve->is_xmm_register() ? 1 : 0);

  while (sim()->stack_size() > result_stack_size) {

    assert(!sim()->slot_is_empty(0), "not allowed");

    if (result_stack_size == 0 || sim()->get_slot(0) != fpu_num(preserve)) {

      insert_free(0);

    } else {

      // move "preserve" to bottom of stack so that all other stack slots can be popped

      insert_exchange(sim()->stack_size() - 1);

    }

  }

}

void FpuStackAllocator::handle_op1(LIR_Op1* op1) {

  LIR_Opr in  = op1->in_opr();

  LIR_Opr res = op1->result_opr();

  LIR_Opr new_in  = in;  // new operands relative to the actual fpu stack top

  LIR_Opr new_res = res;

  // Note: this switch is processed for all LIR_Op1, regardless if they have FPU-arguments,

  //       so checks for is_float_kind() are necessary inside the cases

  switch (op1->code()) {

    case lir_return: {

      // FPU-Stack must only contain the (optional) fpu return value.

      // All remaining dead values are popped from the stack

      // If the input operand is a fpu-register, it is exchanged to the bottom of the stack

      clear_fpu_stack(in);

      if (in->is_fpu_register() && !in->is_xmm_register()) {

        new_in = to_fpu_stack_top(in);

      }

      break;

    }

    case lir_move: {

      if (in->is_fpu_register() && !in->is_xmm_register()) {

        if (res->is_xmm_register()) {

          // move from fpu register to xmm register (necessary for operations that

          // are not available in the SSE instruction set)

          insert_exchange(in);

          new_in = to_fpu_stack_top(in);

          pop_always(op1, in);

        } else if (res->is_fpu_register() && !res->is_xmm_register()) {

          // move from fpu-register to fpu-register:

          // * input and result register equal:

          //   nothing to do

          // * input register is last use:

          //   rename the input register to result register -> input register

          //   not present on fpu-stack afterwards

          // * input register not last use:

          //   duplicate input register to result register to preserve input

          //

          // Note: The LIR-Assembler does not produce any code for fpu register moves,

          //       so input and result stack index must be equal

          if (fpu_num(in) == fpu_num(res)) {

            // nothing to do

          } else if (in->is_last_use()) {

            insert_free_if_dead(res);//, in);

            do_rename(in, res);

          } else {

            insert_free_if_dead(res);

            insert_copy(in, res);

          }

          new_in = to_fpu_stack(res);

          new_res = new_in;

        } else {

          // move from fpu-register to memory

          // input operand must be on top of stack

          insert_exchange(in);

          // create debug information here because afterwards the register may have been popped

          compute_debug_information(op1);