/*

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

#include "code/debugInfo.hpp"

#include "code/debugInfoRec.hpp"

#include "compiler/compileBroker.hpp"

#include "compiler/oopMap.hpp"

#include "memory/allocation.inline.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/locknode.hpp"

#include "opto/machnode.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"

extern uint size_java_to_interp();

extern uint reloc_java_to_interp();

extern uint size_exception_handler();

extern uint size_deopt_handler();

#ifndef PRODUCT

#define DEBUG_ARG(x) , x

#else

#define DEBUG_ARG(x)

#endif

extern int emit_exception_handler(CodeBuffer &cbuf);

extern int emit_deopt_handler(CodeBuffer &cbuf);

//------------------------------Output-----------------------------------------

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

void Compile::Output() {

  // RootNode goes

  assert( _cfg->_broot->_nodes.size() == 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_Array& bbs = _cfg->_bbs;

  Block *entry = _cfg->_blocks[1];

  Block *broot = _cfg->_broot;

  const StartNode *start = entry->_nodes[0]->as_Start();

  // Replace StartNode with prolog

  MachPrologNode *prolog = new (this) MachPrologNode();

  entry->_nodes.map( 0, prolog );

  bbs.map( prolog->_idx, entry );

  bbs.map( start->_idx, NULL ); // 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 (this) MachBreakpointNode() );

    }

  } else {

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

      // Insert unvalidated entry point

      _cfg->insert( broot, 0, new (this) 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 (this) MachBreakpointNode() );

  }

  // Insert epilogs before every return

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

    Block *b = _cfg->_blocks[i];

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

      Node *m = b->end();

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

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

        b->add_inst( epilog );

        bbs.map(epilog->_idx, b);

        //_regalloc->set_bad(epilog->_idx); // Already initialized this way.

      }

    }

  }

# ifdef ENABLE_ZAP_DEAD_LOCALS

  if ( ZapDeadCompiledLocals )  Insert_zap_nodes();

# endif

  ScheduleAndBundle();

#ifndef PRODUCT

  if (trace_opto_output()) {

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

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

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

      Block *bb = _cfg->_blocks[i];

      for (uint j = 0; j < bb->_nodes.size(); j++) {

        Node *n = bb->_nodes[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();

}

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.

  return (stub_function() == NULL &&

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

}

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->_num_blocks; i++ ) {

    Block *b = _cfg->_blocks[i];

    for ( uint j = 0;  j < b->_nodes.size();  ++j ) {

      Node *n = b->_nodes[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->_nodes.insert( j, zap );

          _cfg->_bbs.map( zap->_idx, 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 (this, tf->domain()->cnt()) 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);

}

//------------------------------is_node_getting_a_safepoint--------------------

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

// 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->_num_blocks-1;

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

      Block *b = _cfg->_blocks[i];

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

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

        uint sum_size = 0;

        uint inst_cnt = NumberOfLoopInstrToAlign;

        inst_cnt = b->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 = b;

        while( inst_cnt > 0 &&

               i < last_block &&

               !_cfg->_blocks[i+1]->has_loop_alignment() &&

               !nb->has_successor(b) ) {

          i++;

          nb = _cfg->_blocks[i];

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

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

        b->set_first_inst_size(sum_size);

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

    } // for( i <= last_block )

  } // if( MaxLoopPad < OptoLoopAlignment-1 )

}

//----------------------Shorten_branches---------------------------------------

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

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

void Compile::Shorten_branches(Label *labels, int& code_size, int& reloc_size, int& stub_size) {

  // fill in the nop array for bundling computations

  MachNode *_nop_list[Bundle::_nop_count];

  Bundle::initialize_nops(_nop_list, this);

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

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

  uint *jmp_end    = NEW_RESOURCE_ARRAY(uint,_cfg->_num_blocks);

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

  DEBUG_ONLY( uint *jmp_target = NEW_RESOURCE_ARRAY(uint,_cfg->_num_blocks); )

  DEBUG_ONLY( uint *jmp_rule = NEW_RESOURCE_ARRAY(uint,_cfg->_num_blocks); )

  blk_starts[0]    = 0;

  // 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_end and reloc_size information.  The second performs

  // short branch substitution using the pessimistic sizing.  The

  // third inserts nops where needed.

  Node *nj; // tmp

  // Step one, perform a pessimistic sizing pass.

  uint i;

  uint min_offset_from_last_call = 1;  // init to a positive value

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

  for( i=0; i<_cfg->_num_blocks; i++ ) { // For all blocks

    Block *b = _cfg->_blocks[i];

    // Sum all instruction sizes to compute block size

    uint last_inst = b->_nodes.size();

    uint blk_size = 0;

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

      nj = b->_nodes[j];

      uint inst_size = nj->size(_regalloc);

      blk_size += inst_size;

      // 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() ) {

          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  += size_java_to_interp();

            reloc_size += reloc_java_to_interp();

          }

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

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

          // nop to disambiguate the two safepoints.

          if (min_offset_from_last_call == 0) {

            blk_size += nop_size;

          }

        }

      }

      min_offset_from_last_call += inst_size;

      // Remember end of call offset

      if (nj->is_MachCall() && nj->as_MachCall()->is_safepoint_node()) {

        min_offset_from_last_call = 0;

      }

    }

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

    // end of jump in jmp_end, rather than the absolute end 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_end[i] = blk_size;

    DEBUG_ONLY( jmp_target[i] = 0; )

    // 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<_cfg->_num_blocks-1 ) {

      Block *nb = _cfg->_blocks[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()), "");

        blk_size += 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.

  // Note: this will only get the long branches within short branch

  //   range. Another pass might detect more branches that became

  //   candidates because the shortening in the first pass exposed

  //   more opportunities. Unfortunately, this would require

  //   recomputing the starting and ending positions for the blocks

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

    Block *b = _cfg->_blocks[i];

    int j;

    // Find the branch; ignore trailing NOPs.

    for( j = b->_nodes.size()-1; j>=0; j-- ) {

      nj = b->_nodes[j];

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

        break;

    }

    if (j >= 0) {

      if( nj->is_Mach() && nj->as_Mach()->may_be_short_branch() ) {

        MachNode *mach = nj->as_Mach();

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

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

        uintptr_t target = blk_starts[bnum];

        if( mach->is_pc_relative() ) {

          int offset = target-(blk_starts[i] + jmp_end[i]);

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

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

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

            b->_nodes.map(j, replacement);

            mach->subsume_by(replacement);

            // Update the jmp_end size to save time in our

            // next pass.

            jmp_end[i] -= (mach->size(_regalloc) - replacement->size(_regalloc));

            DEBUG_ONLY( jmp_target[i] = bnum; );

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

          }

        } else {

#ifndef PRODUCT

          mach->dump(3);

#endif

          Unimplemented();

        }

      }

    }

  }

  // Compute the size of first NumberOfLoopInstrToAlign instructions at head

  // of a loop. It is used to determine the padding for loop alignment.

  compute_loop_first_inst_sizes();

  // Step 3, compute the offsets of all the labels

  uint last_call_adr = max_uint;

  for( i=0; i<_cfg->_num_blocks; i++ ) { // For all blocks

    // copy the offset of the beginning to the corresponding label

    assert(labels[i].is_unused(), "cannot patch at this point");

    labels[i].bind_loc(blk_starts[i], CodeBuffer::SECT_INSTS);

    // insert padding for any instructions that need it

    Block *b = _cfg->_blocks[i];

    uint last_inst = b->_nodes.size();

    uint adr = blk_starts[i];

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

      nj = b->_nodes[j];

      if( nj->is_Mach() ) {

        int padding = nj->as_Mach()->compute_padding(adr);

        // If call/safepoint are adjacent insert a nop (5010568)

        if (padding == 0 && nj->is_MachSafePoint() && !nj->is_MachCall() &&

            adr == last_call_adr ) {

          padding = nop_size;

        }

        if(padding > 0) {

          assert((padding % nop_size) == 0, "padding is not a multiple of NOP size");

          int nops_cnt = padding / nop_size;

          MachNode *nop = new (this) MachNopNode(nops_cnt);

          b->_nodes.insert(j++, nop);

          _cfg->_bbs.map( nop->_idx, b );

          adr += padding;

          last_inst++;

        }

      }

      adr += nj->size(_regalloc);

      // Remember end of call offset

      if (nj->is_MachCall() && nj->as_MachCall()->is_safepoint_node()) {

        last_call_adr = adr;

      }

    }

    if ( i != _cfg->_num_blocks-1) {

      // Get the size of the block

      uint blk_size = adr - blk_starts[i];

      // When the next block is the top of a loop, we may insert pad NOP

      // instructions.

      Block *nb = _cfg->_blocks[i+1];

      int current_offset = blk_starts[i] + blk_size;