/*

 * 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

  if( (_method && _method->break_at_execute())

#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);

      }

    }

  }

# ifdef ENABLE_ZAP_DEAD_LOCALS

  if (ZapDeadCompiledLocals) {

    Insert_zap_nodes();

  }

# endif

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

}

# ifdef ENABLE_ZAP_DEAD_LOCALS

// In order to catch compiler oop-map bugs, we have implemented

// a debugging mode called ZapDeadCompilerLocals.

// This mode causes the compiler to insert a call to a runtime routine,

// "zap_dead_locals", right before each place in compiled code

// that could potentially be a gc-point (i.e., a safepoint or oop map point).

// The runtime routine checks that locations mapped as oops are really

// oops, that locations mapped as values do not look like oops,

// and that locations mapped as dead are not used later

// (by zapping them to an invalid address).

int Compile::_CompiledZap_count = 0;

void Compile::Insert_zap_nodes() {

  bool skip = false;

  // Dink with static counts because code code without the extra

  // runtime calls is MUCH faster for debugging purposes

       if ( CompileZapFirst  ==  0  ) ; // nothing special

  else if ( CompileZapFirst  >  CompiledZap_count() )  skip = true;

  else if ( CompileZapFirst  == CompiledZap_count() )

    warning("starting zap compilation after skipping");

       if ( CompileZapLast  ==  -1  ) ; // nothing special

  else if ( CompileZapLast  <   CompiledZap_count() )  skip = true;

  else if ( CompileZapLast  ==  CompiledZap_count() )

    warning("about to compile last zap");

  ++_CompiledZap_count; // counts skipped zaps, too

  if ( skip )  return;

  if ( _method == NULL )

    return; // no safepoints/oopmaps emitted for calls in stubs,so we don't care

  // Insert call to zap runtime stub before every node with an oop map

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

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

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

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

      // Determining if we should insert a zap-a-lot node in output.

      // We do that for all nodes that has oopmap info, except for calls

      // to allocation.  Calls to allocation passes in the old top-of-eden pointer

      // and expect the C code to reset it.  Hence, there can be no safepoints between

      // the inlined-allocation and the call to new_Java, etc.

      // We also cannot zap monitor calls, as they must hold the microlock

      // during the call to Zap, which also wants to grab the microlock.

      bool insert = n->is_MachSafePoint() && (n->as_MachSafePoint()->oop_map() != NULL);

      if ( insert ) { // it is MachSafePoint

        if ( !n->is_MachCall() ) {

          insert = false;

        } else if ( n->is_MachCall() ) {

          MachCallNode* call = n->as_MachCall();

          if (call->entry_point() == OptoRuntime::new_instance_Java() ||

              call->entry_point() == OptoRuntime::new_array_Java() ||

              call->entry_point() == OptoRuntime::multianewarray2_Java() ||

              call->entry_point() == OptoRuntime::multianewarray3_Java() ||

              call->entry_point() == OptoRuntime::multianewarray4_Java() ||

              call->entry_point() == OptoRuntime::multianewarray5_Java() ||

              call->entry_point() == OptoRuntime::slow_arraycopy_Java() ||

              call->entry_point() == OptoRuntime::complete_monitor_locking_Java()

              ) {

            insert = false;

          }

        }

        if (insert) {

          Node *zap = call_zap_node(n->as_MachSafePoint(), i);

          b->insert_node(zap, j);

          _cfg->map_node_to_block(zap, b);

          ++j;

        }

      }

    }

  }

}

Node* Compile::call_zap_node(MachSafePointNode* node_to_check, int block_no) {

  const TypeFunc *tf = OptoRuntime::zap_dead_locals_Type();

  CallStaticJavaNode* ideal_node =

    new CallStaticJavaNode( tf,

         OptoRuntime::zap_dead_locals_stub(_method->flags().is_native()),

                       "call zap dead locals stub", 0, TypePtr::BOTTOM);

  // We need to copy the OopMap from the site we're zapping at.

  // We have to make a copy, because the zap site might not be

  // a call site, and zap_dead is a call site.

  OopMap* clone = node_to_check->oop_map()->deep_copy();

  // Add the cloned OopMap to the zap node

  ideal_node->set_oop_map(clone);

  return _matcher->match_sfpt(ideal_node);

}

bool Compile::is_node_getting_a_safepoint( Node* n) {

  // This code duplicates the logic prior to the call of add_safepoint

  // below in this file.

  if( n->is_MachSafePoint() ) return true;

  return false;

}

# endif // ENABLE_ZAP_DEAD_LOCALS

// 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