/*

 * Copyright (c) 1998, 2014, 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 "asm/assembler.inline.hpp"

#include "code/compiledIC.hpp"

#include "code/debugInfo.hpp"

#include "code/debugInfoRec.hpp"

#include "compiler/compileBroker.hpp"

#include "compiler/oopMap.hpp"

#include "memory/allocation.inline.hpp"

#include "opto/ad.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/locknode.hpp"

#include "opto/machnode.hpp"

#include "opto/optoreg.hpp"

#include "opto/output.hpp"

#include "opto/regalloc.hpp"

#include "opto/runtime.hpp"

#include "opto/subnode.hpp"

#include "opto/type.hpp"

#include "runtime/handles.inline.hpp"

#include "utilities/xmlstream.hpp"

#ifndef PRODUCT

#define DEBUG_ARG(x) , x

#else

#define DEBUG_ARG(x)

#endif

// Convert Nodes to instruction bits and pass off to the VM

void Compile::Output() {

  // RootNode goes

  assert( _cfg->get_root_block()->number_of_nodes() == 0, "" );

  // The number of new nodes (mostly MachNop) is proportional to

  // the number of java calls and inner loops which are aligned.

  if ( C->check_node_count((NodeLimitFudgeFactor + C->java_calls()*3 +

                            C->inner_loops()*(OptoLoopAlignment-1)),

                           "out of nodes before code generation" ) ) {

    return;

  }

  // Make sure I can find the Start Node

  Block *entry = _cfg->get_block(1);

  Block *broot = _cfg->get_root_block();

  const StartNode *start = entry->head()->as_Start();

  // Replace StartNode with prolog

  MachPrologNode *prolog = new MachPrologNode();

  entry->map_node(prolog, 0);

  _cfg->map_node_to_block(prolog, entry);

  _cfg->unmap_node_from_block(start); // start is no longer in any block

  // Virtual methods need an unverified entry point

  if( is_osr_compilation() ) {

    if( PoisonOSREntry ) {

      // TODO: Should use a ShouldNotReachHereNode...

      _cfg->insert( broot, 0, new MachBreakpointNode() );

    }

  } else {

    if( _method && !_method->flags().is_static() ) {

      // Insert unvalidated entry point

      _cfg->insert( broot, 0, new MachUEPNode() );

    }

  }

  // Break before main entry point

#ifndef PRODUCT

    ||(OptoBreakpoint && is_method_compilation())

    ||(OptoBreakpointOSR && is_osr_compilation())

    ||(OptoBreakpointC2R && !_method)

#endif

    ) {

    // checking for _method means that OptoBreakpoint does not apply to

    // runtime stubs or frame converters

    _cfg->insert( entry, 1, new MachBreakpointNode() );

  }

  // Insert epilogs before every return

  for (uint i = 0; i < _cfg->number_of_blocks(); i++) {

    Block* block = _cfg->get_block(i);

    if (!block->is_connector() && block->non_connector_successor(0) == _cfg->get_root_block()) { // Found a program exit point?

      Node* m = block->end();

      if (m->is_Mach() && m->as_Mach()->ideal_Opcode() != Op_Halt) {

        MachEpilogNode* epilog = new MachEpilogNode(m->as_Mach()->ideal_Opcode() == Op_Return);

        block->add_inst(epilog);

        _cfg->map_node_to_block(epilog, block);

      }

    }

  }

  uint* blk_starts = NEW_RESOURCE_ARRAY(uint, _cfg->number_of_blocks() + 1);

  blk_starts[0] = 0;

  // Initialize code buffer and process short branches.

  CodeBuffer* cb = init_buffer(blk_starts);

  if (cb == NULL || failing()) {

    return;

  }

  ScheduleAndBundle();

#ifndef PRODUCT

  if (trace_opto_output()) {

    tty->print("\n---- After ScheduleAndBundle ----\n");

    for (uint i = 0; i < _cfg->number_of_blocks(); i++) {

      tty->print("\nBB#%03d:\n", i);

      Block* block = _cfg->get_block(i);

      for (uint j = 0; j < block->number_of_nodes(); j++) {

        Node* n = block->get_node(j);

        OptoReg::Name reg = _regalloc->get_reg_first(n);

        tty->print(" %-6s ", reg >= 0 && reg < REG_COUNT ? Matcher::regName[reg] : "");

        n->dump();

      }

    }

  }

#endif

  if (failing()) {

    return;

  }

  BuildOopMaps();

  if (failing())  {

    return;

  }

  fill_buffer(cb, blk_starts);

}

bool Compile::need_stack_bang(int frame_size_in_bytes) const {

  // Determine if we need to generate a stack overflow check.

  // Do it if the method is not a stub function and

  // has java calls or has frame size > vm_page_size/8.

  // The debug VM checks that deoptimization doesn't trigger an

  // unexpected stack overflow (compiled method stack banging should

  // guarantee it doesn't happen) so we always need the stack bang in

  // a debug VM.

  return (UseStackBanging && stub_function() == NULL &&

          (has_java_calls() || frame_size_in_bytes > os::vm_page_size()>>3

           DEBUG_ONLY(|| true)));

}

bool Compile::need_register_stack_bang() const {

  // Determine if we need to generate a register stack overflow check.

  // This is only used on architectures which have split register

  // and memory stacks (ie. IA64).

  // Bang if the method is not a stub function and has java calls

  return (stub_function() == NULL && has_java_calls());

}

// Compute the size of first NumberOfLoopInstrToAlign instructions at the top

// of a loop. When aligning a loop we need to provide enough instructions

// in cpu's fetch buffer to feed decoders. The loop alignment could be

// avoided if we have enough instructions in fetch buffer at the head of a loop.

// By default, the size is set to 999999 by Block's constructor so that

// a loop will be aligned if the size is not reset here.

//

// Note: Mach instructions could contain several HW instructions

// so the size is estimated only.

//

void Compile::compute_loop_first_inst_sizes() {

  // The next condition is used to gate the loop alignment optimization.

  // Don't aligned a loop if there are enough instructions at the head of a loop

  // or alignment padding is larger then MaxLoopPad. By default, MaxLoopPad

  // is equal to OptoLoopAlignment-1 except on new Intel cpus, where it is

  // equal to 11 bytes which is the largest address NOP instruction.

  if (MaxLoopPad < OptoLoopAlignment - 1) {

    uint last_block = _cfg->number_of_blocks() - 1;

    for (uint i = 1; i <= last_block; i++) {

      Block* block = _cfg->get_block(i);

      // Check the first loop's block which requires an alignment.

      if (block->loop_alignment() > (uint)relocInfo::addr_unit()) {

        uint sum_size = 0;

        uint inst_cnt = NumberOfLoopInstrToAlign;

        inst_cnt = block->compute_first_inst_size(sum_size, inst_cnt, _regalloc);

        // Check subsequent fallthrough blocks if the loop's first

        // block(s) does not have enough instructions.

        Block *nb = block;

        while(inst_cnt > 0 &&

              i < last_block &&

              !_cfg->get_block(i + 1)->has_loop_alignment() &&

              !nb->has_successor(block)) {

          i++;

          nb = _cfg->get_block(i);

          inst_cnt  = nb->compute_first_inst_size(sum_size, inst_cnt, _regalloc);

        } // while( inst_cnt > 0 && i < last_block  )

        block->set_first_inst_size(sum_size);

      } // f( b->head()->is_Loop() )

    } // for( i <= last_block )

  } // if( MaxLoopPad < OptoLoopAlignment-1 )

}

// The architecture description provides short branch variants for some long

// branch instructions. Replace eligible long branches with short branches.

void Compile::shorten_branches(uint* blk_starts, int& code_size, int& reloc_size, int& stub_size) {

  // Compute size of each block, method size, and relocation information size

  uint nblocks  = _cfg->number_of_blocks();

  uint*      jmp_offset = NEW_RESOURCE_ARRAY(uint,nblocks);

  uint*      jmp_size   = NEW_RESOURCE_ARRAY(uint,nblocks);

  int*       jmp_nidx   = NEW_RESOURCE_ARRAY(int ,nblocks);

  // Collect worst case block paddings

  int* block_worst_case_pad = NEW_RESOURCE_ARRAY(int, nblocks);

  memset(block_worst_case_pad, 0, nblocks * sizeof(int));

  DEBUG_ONLY( uint *jmp_target = NEW_RESOURCE_ARRAY(uint,nblocks); )

  DEBUG_ONLY( uint *jmp_rule = NEW_RESOURCE_ARRAY(uint,nblocks); )

  bool has_short_branch_candidate = false;

  // Initialize the sizes to 0

  code_size  = 0;          // Size in bytes of generated code

  stub_size  = 0;          // Size in bytes of all stub entries

  // Size in bytes of all relocation entries, including those in local stubs.

  // Start with 2-bytes of reloc info for the unvalidated entry point

  reloc_size = 1;          // Number of relocation entries

  // Make three passes.  The first computes pessimistic blk_starts,

  // relative jmp_offset and reloc_size information.  The second performs

  // short branch substitution using the pessimistic sizing.  The

  // third inserts nops where needed.

  // Step one, perform a pessimistic sizing pass.

  uint last_call_adr = max_juint;

  uint last_avoid_back_to_back_adr = max_juint;

  uint nop_size = (new MachNopNode())->size(_regalloc);

  for (uint i = 0; i < nblocks; i++) { // For all blocks

    Block* block = _cfg->get_block(i);

    // During short branch replacement, we store the relative (to blk_starts)

    // offset of jump in jmp_offset, rather than the absolute offset of jump.

    // This is so that we do not need to recompute sizes of all nodes when

    // we compute correct blk_starts in our next sizing pass.

    jmp_offset[i] = 0;

    jmp_size[i]   = 0;

    jmp_nidx[i]   = -1;

    DEBUG_ONLY( jmp_target[i] = 0; )

    DEBUG_ONLY( jmp_rule[i]   = 0; )

    // Sum all instruction sizes to compute block size

    uint last_inst = block->number_of_nodes();

    uint blk_size = 0;

    for (uint j = 0; j < last_inst; j++) {

      Node* nj = block->get_node(j);

      // Handle machine instruction nodes

      if (nj->is_Mach()) {

        MachNode *mach = nj->as_Mach();

        blk_size += (mach->alignment_required() - 1) * relocInfo::addr_unit(); // assume worst case padding

        reloc_size += mach->reloc();

        if (mach->is_MachCall()) {

          // add size information for trampoline stub

          // class CallStubImpl is platform-specific and defined in the *.ad files.

          stub_size  += CallStubImpl::size_call_trampoline();

          reloc_size += CallStubImpl::reloc_call_trampoline();

          MachCallNode *mcall = mach->as_MachCall();

          // This destination address is NOT PC-relative

          mcall->method_set((intptr_t)mcall->entry_point());

          if (mcall->is_MachCallJava() && mcall->as_MachCallJava()->_method) {

            stub_size  += CompiledStaticCall::to_interp_stub_size();

            reloc_size += CompiledStaticCall::reloc_to_interp_stub();

          }

        } else if (mach->is_MachSafePoint()) {

          // If call/safepoint are adjacent, account for possible

          // nop to disambiguate the two safepoints.

          // ScheduleAndBundle() can rearrange nodes in a block,

          // check for all offsets inside this block.

          if (last_call_adr >= blk_starts[i]) {

            blk_size += nop_size;

          }

        }

        if (mach->avoid_back_to_back(MachNode::AVOID_BEFORE)) {

          // Nop is inserted between "avoid back to back" instructions.

          // ScheduleAndBundle() can rearrange nodes in a block,

          // check for all offsets inside this block.

          if (last_avoid_back_to_back_adr >= blk_starts[i]) {

            blk_size += nop_size;

          }

        }

        if (mach->may_be_short_branch()) {

          if (!nj->is_MachBranch()) {

#ifndef PRODUCT

            nj->dump(3);

#endif

            Unimplemented();

          }

          assert(jmp_nidx[i] == -1, "block should have only one branch");

          jmp_offset[i] = blk_size;

          jmp_size[i]   = nj->size(_regalloc);

          jmp_nidx[i]   = j;

          has_short_branch_candidate = true;

        }

      }

      blk_size += nj->size(_regalloc);

      // Remember end of call offset

      if (nj->is_MachCall() && !nj->is_MachCallLeaf()) {

        last_call_adr = blk_starts[i]+blk_size;

      }

      // Remember end of avoid_back_to_back offset

      if (nj->is_Mach() && nj->as_Mach()->avoid_back_to_back(MachNode::AVOID_AFTER)) {

        last_avoid_back_to_back_adr = blk_starts[i]+blk_size;

      }

    }

    // When the next block starts a loop, we may insert pad NOP

    // instructions.  Since we cannot know our future alignment,

    // assume the worst.

    if (i < nblocks - 1) {

      Block* nb = _cfg->get_block(i + 1);

      int max_loop_pad = nb->code_alignment()-relocInfo::addr_unit();

      if (max_loop_pad > 0) {

        assert(is_power_of_2(max_loop_pad+relocInfo::addr_unit()), "");

        // Adjust last_call_adr and/or last_avoid_back_to_back_adr.

        // If either is the last instruction in this block, bump by

        // max_loop_pad in lock-step with blk_size, so sizing

        // calculations in subsequent blocks still can conservatively

        // detect that it may the last instruction in this block.

        if (last_call_adr == blk_starts[i]+blk_size) {

          last_call_adr += max_loop_pad;

        }

        if (last_avoid_back_to_back_adr == blk_starts[i]+blk_size) {

          last_avoid_back_to_back_adr += max_loop_pad;

        }

        blk_size += max_loop_pad;

        block_worst_case_pad[i + 1] = max_loop_pad;

      }

    }

    // Save block size; update total method size

    blk_starts[i+1] = blk_starts[i]+blk_size;

  }

  // Step two, replace eligible long jumps.

  bool progress = true;

  uint last_may_be_short_branch_adr = max_juint;

  while (has_short_branch_candidate && progress) {

    progress = false;

    has_short_branch_candidate = false;

    int adjust_block_start = 0;

    for (uint i = 0; i < nblocks; i++) {

      Block* block = _cfg->get_block(i);

      int idx = jmp_nidx[i];

      MachNode* mach = (idx == -1) ? NULL: block->get_node(idx)->as_Mach();

      if (mach != NULL && mach->may_be_short_branch()) {

#ifdef ASSERT

        assert(jmp_size[i] > 0 && mach->is_MachBranch(), "sanity");

        int j;

        // Find the branch; ignore trailing NOPs.

        for (j = block->number_of_nodes()-1; j>=0; j--) {

          Node* n = block->get_node(j);

          if (!n->is_Mach() || n->as_Mach()->ideal_Opcode() != Op_Con)

            break;

        }

        assert(j >= 0 && j == idx && block->get_node(j) == (Node*)mach, "sanity");

#endif

        int br_size = jmp_size[i];

        int br_offs = blk_starts[i] + jmp_offset[i];

        // This requires the TRUE branch target be in succs[0]

        uint bnum = block->non_connector_successor(0)->_pre_order;

        int offset = blk_starts[bnum] - br_offs;

        if (bnum > i) { // adjust following block's offset

          offset -= adjust_block_start;

        }

        // This block can be a loop header, account for the padding

        // in the previous block.

        int block_padding = block_worst_case_pad[i];

        assert(i == 0 || block_padding == 0 || br_offs >= block_padding, "Should have at least a padding on top");

        // In the following code a nop could be inserted before

        // the branch which will increase the backward distance.

        bool needs_padding = ((uint)(br_offs - block_padding) == last_may_be_short_branch_adr);

        assert(!needs_padding || jmp_offset[i] == 0, "padding only branches at the beginning of block");

        if (needs_padding && offset <= 0)

          offset -= nop_size;

        if (_matcher->is_short_branch_offset(mach->rule(), br_size, offset)) {

          // We've got a winner.  Replace this branch.

          MachNode* replacement = mach->as_MachBranch()->short_branch_version();

          // Update the jmp_size.

          int new_size = replacement->size(_regalloc);

          int diff     = br_size - new_size;

          assert(diff >= (int)nop_size, "short_branch size should be smaller");

          // Conservatively take into account padding between

          // avoid_back_to_back branches. Previous branch could be

          // converted into avoid_back_to_back branch during next

          // rounds.

          if (needs_padding && replacement->avoid_back_to_back(MachNode::AVOID_BEFORE)) {

            jmp_offset[i] += nop_size;

            diff -= nop_size;

          }

          adjust_block_start += diff;

          block->map_node(replacement, idx);

          mach->subsume_by(replacement, C);

          mach = replacement;

          progress = true;

          jmp_size[i] = new_size;

          DEBUG_ONLY( jmp_target[i] = bnum; );

          DEBUG_ONLY( jmp_rule[i] = mach->rule(); );

        } else {

          // The jump distance is not short, try again during next iteration.

          has_short_branch_candidate = true;

        }

      } // (mach->may_be_short_branch())

      if (mach != NULL && (mach->may_be_short_branch() ||

                           mach->avoid_back_to_back(MachNode::AVOID_AFTER))) {

        last_may_be_short_branch_adr = blk_starts[i] + jmp_offset[i] + jmp_size[i];

      }

      blk_starts[i+1] -= adjust_block_start;

    }

  }

#ifdef ASSERT

  for (uint i = 0; i < nblocks; i++) { // For all blocks

    if (jmp_target[i] != 0) {

      int br_size = jmp_size[i];

      int offset = blk_starts[jmp_target[i]]-(blk_starts[i] + jmp_offset[i]);

      if (!_matcher->is_short_branch_offset(jmp_rule[i], br_size, offset)) {

        tty->print_cr("target (%d) - jmp_offset(%d) = offset (%d), jump_size(%d), jmp_block B%d, target_block B%d", blk_starts[jmp_target[i]], blk_starts[i] + jmp_offset[i], offset, br_size, i, jmp_target[i]);

      }

      assert(_matcher->is_short_branch_offset(jmp_rule[i], br_size, offset), "Displacement too large for short jmp");

    }

  }

#endif

  // Step 3, compute the offsets of all blocks, will be done in fill_buffer()

  // after ScheduleAndBundle().

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

  // Compute size for code buffer

  code_size = blk_starts[nblocks];

  // Relocation records

  reloc_size += 1;              // Relo entry for exception handler

  // Adjust reloc_size to number of record of relocation info

  // Min is 2 bytes, max is probably 6 or 8, with a tax up to 25% for

  // a relocation index.

  // The CodeBuffer will expand the locs array if this estimate is too low.

  reloc_size *= 10 / sizeof(relocInfo);

}

//------------------------------FillLocArray-----------------------------------

// Create a bit of debug info and append it to the array.  The mapping is from

// Java local or expression stack to constant, register or stack-slot.  For

// doubles, insert 2 mappings and return 1 (to tell the caller that the next

// entry has been taken care of and caller should skip it).

static LocationValue *new_loc_value( PhaseRegAlloc *ra, OptoReg::Name regnum, Location::Type l_type ) {

  // This should never have accepted Bad before

  assert(OptoReg::is_valid(regnum), "location must be valid");

  return (OptoReg::is_reg(regnum))

    ? new LocationValue(Location::new_reg_loc(l_type, OptoReg::as_VMReg(regnum)) )

    : new LocationValue(Location::new_stk_loc(l_type,  ra->reg2offset(regnum)));

}

ObjectValue*

Compile::sv_for_node_id(GrowableArray<ScopeValue*> *objs, int id) {

  for (int i = 0; i < objs->length(); i++) {