/*

 * Copyright (c) 2000, 2018, 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 "libadt/vectset.hpp"

#include "memory/allocation.inline.hpp"

#include "memory/resourceArea.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/c2compiler.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/chaitin.hpp"

#include "opto/loopnode.hpp"

#include "opto/machnode.hpp"

//------------------------------Split--------------------------------------

// Walk the graph in RPO and for each lrg which spills, propagate reaching

// definitions.  During propagation, split the live range around regions of

// High Register Pressure (HRP).  If a Def is in a region of Low Register

// Pressure (LRP), it will not get spilled until we encounter a region of

// HRP between it and one of its uses.  We will spill at the transition

// point between LRP and HRP.  Uses in the HRP region will use the spilled

// Def.  The first Use outside the HRP region will generate a SpillCopy to

// hoist the live range back up into a register, and all subsequent uses

// will use that new Def until another HRP region is encountered.  Defs in

// HRP regions will get trailing SpillCopies to push the LRG down into the

// stack immediately.

//

// As a side effect, unlink from (hence make dead) coalesced copies.

//

static const char out_of_nodes[] = "out of nodes during split";

//------------------------------get_spillcopy_wide-----------------------------

// Get a SpillCopy node with wide-enough masks.  Use the 'wide-mask', the

// wide ideal-register spill-mask if possible.  If the 'wide-mask' does

// not cover the input (or output), use the input (or output) mask instead.

Node *PhaseChaitin::get_spillcopy_wide(MachSpillCopyNode::SpillType spill_type, Node *def, Node *use, uint uidx) {

  // If ideal reg doesn't exist we've got a bad schedule happening

  // that is forcing us to spill something that isn't spillable.

  // Bail rather than abort

  uint ireg = def->ideal_reg();

  if (ireg == 0 || ireg == Op_RegFlags) {

    assert(false, "attempted to spill a non-spillable item: %d: %s <- %d: %s, ireg = %u, spill_type: %s",

           def->_idx, def->Name(), use->_idx, use->Name(), ireg,

           MachSpillCopyNode::spill_type(spill_type));

    C->record_method_not_compilable("attempted to spill a non-spillable item");

    return NULL;

  }

  if (C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {

    return NULL;

  }

  const RegMask *i_mask = &def->out_RegMask();

  const RegMask *w_mask = C->matcher()->idealreg2spillmask[ireg];

  const RegMask *o_mask = use ? &use->in_RegMask(uidx) : w_mask;

  const RegMask *w_i_mask = w_mask->overlap( *i_mask ) ? w_mask : i_mask;

  const RegMask *w_o_mask;

  int num_regs = RegMask::num_registers(ireg);

  bool is_vect = RegMask::is_vector(ireg);

  if( w_mask->overlap( *o_mask ) && // Overlap AND

      (num_regs == 1  // Single use or aligned

        || is_vect    // or vector

        || (!is_vect && o_mask->is_aligned_pairs())) ) {

    assert(!is_vect || o_mask->is_aligned_sets(num_regs), "vectors are aligned");

    // Don't come here for mis-aligned doubles

    w_o_mask = w_mask;

  } else {                      // wide ideal mask does not overlap with o_mask

    // Mis-aligned doubles come here and XMM->FPR moves on x86.

    w_o_mask = o_mask;          // Must target desired registers

    // Does the ideal-reg-mask overlap with o_mask?  I.e., can I use

    // a reg-reg move or do I need a trip across register classes

    // (and thus through memory)?

    if( !C->matcher()->idealreg2regmask[ireg]->overlap( *o_mask) && o_mask->is_UP() )

      // Here we assume a trip through memory is required.

      w_i_mask = &C->FIRST_STACK_mask();

  }

  return new MachSpillCopyNode(spill_type, def, *w_i_mask, *w_o_mask );

}

//------------------------------insert_proj------------------------------------

// Insert the spill at chosen location.  Skip over any intervening Proj's or

// Phis.  Skip over a CatchNode and projs, inserting in the fall-through block

// instead.  Update high-pressure indices.  Create a new live range.

void PhaseChaitin::insert_proj( Block *b, uint i, Node *spill, uint maxlrg ) {

  // Skip intervening ProjNodes.  Do not insert between a ProjNode and

  // its definer.

  while( i < b->number_of_nodes() &&

         (b->get_node(i)->is_Proj() ||

          b->get_node(i)->is_Phi() ) )

    i++;

  // Do not insert between a call and his Catch

  if( b->get_node(i)->is_Catch() ) {

    // Put the instruction at the top of the fall-thru block.

    // Find the fall-thru projection

    while( 1 ) {

      const CatchProjNode *cp = b->get_node(++i)->as_CatchProj();

      if( cp->_con == CatchProjNode::fall_through_index )

        break;

    }

    int sidx = i - b->end_idx()-1;

    b = b->_succs[sidx];        // Switch to successor block

    i = 1;                      // Right at start of block

  }

  b->insert_node(spill, i);    // Insert node in block

  _cfg.map_node_to_block(spill,  b); // Update node->block mapping to reflect

  // Adjust the point where we go hi-pressure

  if( i <= b->_ihrp_index ) b->_ihrp_index++;

  if( i <= b->_fhrp_index ) b->_fhrp_index++;

  // Assign a new Live Range Number to the SpillCopy and grow

  // the node->live range mapping.

  new_lrg(spill,maxlrg);

}

//------------------------------split_DEF--------------------------------------

// There are four categories of Split; UP/DOWN x DEF/USE

// Only three of these really occur as DOWN/USE will always color

// Any Split with a DEF cannot CISC-Spill now.  Thus we need

// two helper routines, one for Split DEFS (insert after instruction),

// one for Split USES (insert before instruction).  DEF insertion

// happens inside Split, where the Leaveblock array is updated.

uint PhaseChaitin::split_DEF( Node *def, Block *b, int loc, uint maxlrg, Node **Reachblock, Node **debug_defs, GrowableArray<uint> splits, int slidx ) {

#ifdef ASSERT

  // Increment the counter for this lrg

  splits.at_put(slidx, splits.at(slidx)+1);

#endif

  // If we are spilling the memory op for an implicit null check, at the

  // null check location (ie - null check is in HRP block) we need to do

  // the null-check first, then spill-down in the following block.

  // (The implicit_null_check function ensures the use is also dominated

  // by the branch-not-taken block.)

  Node *be = b->end();

  if( be->is_MachNullCheck() && be->in(1) == def && def == b->get_node(loc)) {

    // Spill goes in the branch-not-taken block

    b = b->_succs[b->get_node(b->end_idx()+1)->Opcode() == Op_IfTrue];

    loc = 0;                    // Just past the Region

  }

  assert( loc >= 0, "must insert past block head" );

  // Get a def-side SpillCopy

  Node *spill = get_spillcopy_wide(MachSpillCopyNode::Definition, def, NULL, 0);

  // Did we fail to split?, then bail

  if (!spill) {

    return 0;

  }

  // Insert the spill at chosen location

  insert_proj( b, loc+1, spill, maxlrg++);

  // Insert new node into Reaches array

  Reachblock[slidx] = spill;

  // Update debug list of reaching down definitions by adding this one

  debug_defs[slidx] = spill;

  // return updated count of live ranges

  return maxlrg;

}

//------------------------------split_USE--------------------------------------

// Splits at uses can involve redeffing the LRG, so no CISC Spilling there.

// Debug uses want to know if def is already stack enabled.

uint PhaseChaitin::split_USE(MachSpillCopyNode::SpillType spill_type, Node *def, Block *b, Node *use, uint useidx, uint maxlrg, bool def_down, bool cisc_sp, GrowableArray<uint> splits, int slidx ) {

#ifdef ASSERT

  // Increment the counter for this lrg

  splits.at_put(slidx, splits.at(slidx)+1);

#endif

  // Some setup stuff for handling debug node uses

  JVMState* jvms = use->jvms();

  uint debug_start = jvms ? jvms->debug_start() : 999999;

  uint debug_end   = jvms ? jvms->debug_end()   : 999999;

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

  // Check for use of debug info

  if (useidx >= debug_start && useidx < debug_end) {

    // Actually it's perfectly legal for constant debug info to appear

    // just unlikely.  In this case the optimizer left a ConI of a 4

    // as both inputs to a Phi with only a debug use.  It's a single-def

    // live range of a rematerializable value.  The live range spills,

    // rematerializes and now the ConI directly feeds into the debug info.

    // assert(!def->is_Con(), "constant debug info already constructed directly");

    // Special split handling for Debug Info

    // If DEF is DOWN, just hook the edge and return

    // If DEF is UP, Split it DOWN for this USE.

    if( def->is_Mach() ) {

      if( def_down ) {

        // DEF is DOWN, so connect USE directly to the DEF

        use->set_req(useidx, def);

      } else {

        // Block and index where the use occurs.

        Block *b = _cfg.get_block_for_node(use);

        // Put the clone just prior to use

        int bindex = b->find_node(use);

        // DEF is UP, so must copy it DOWN and hook in USE

        // Insert SpillCopy before the USE, which uses DEF as its input,

        // and defs a new live range, which is used by this node.

        Node *spill = get_spillcopy_wide(spill_type, def,use,useidx);

        // did we fail to split?

        if (!spill) {

          // Bail

          return 0;

        }

        // insert into basic block

        insert_proj( b, bindex, spill, maxlrg++ );

        // Use the new split

        use->set_req(useidx,spill);

      }

      // No further split handling needed for this use

      return maxlrg;

    }  // End special splitting for debug info live range

  }  // If debug info

  // CISC-SPILLING

  // Finally, check to see if USE is CISC-Spillable, and if so,

  // gather_lrg_masks will add the flags bit to its mask, and

  // no use side copy is needed.  This frees up the live range

  // register choices without causing copy coalescing, etc.

  if( UseCISCSpill && cisc_sp ) {

    int inp = use->cisc_operand();

    if( inp != AdlcVMDeps::Not_cisc_spillable )

      // Convert operand number to edge index number

      inp = use->as_Mach()->operand_index(inp);

    if( inp == (int)useidx ) {

      use->set_req(useidx, def);

#ifndef PRODUCT

      if( TraceCISCSpill ) {

        tty->print("  set_split: ");

        use->dump();

      }

#endif

      return maxlrg;

    }

  }

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

  // Insert a Copy before the use

  // Block and index where the use occurs.

  int bindex;

  // Phi input spill-copys belong at the end of the prior block

  if( use->is_Phi() ) {

    b = _cfg.get_block_for_node(b->pred(useidx));

    bindex = b->end_idx();

  } else {

    // Put the clone just prior to use

    bindex = b->find_node(use);

  }

  Node *spill = get_spillcopy_wide(spill_type, def, use, useidx );

  if( !spill ) return 0;        // Bailed out

  // Insert SpillCopy before the USE, which uses the reaching DEF as

  // its input, and defs a new live range, which is used by this node.

  insert_proj( b, bindex, spill, maxlrg++ );

  // Use the spill/clone

  use->set_req(useidx,spill);

  // return updated live range count

  return maxlrg;

}

//------------------------------clone_node----------------------------

// Clone node with anti dependence check.

Node* clone_node(Node* def, Block *b, Compile* C) {

  if (def->needs_anti_dependence_check()) {

#ifdef ASSERT

    if (PrintOpto && WizardMode) {

      tty->print_cr("RA attempts to clone node with anti_dependence:");

      def->dump(-1); tty->cr();

      tty->print_cr("into block:");

      b->dump();

    }

#endif

    if (C->subsume_loads() == true && !C->failing()) {

      // Retry with subsume_loads == false

      // If this is the first failure, the sentinel string will "stick"

      // to the Compile object, and the C2Compiler will see it and retry.

      C->record_failure(C2Compiler::retry_no_subsuming_loads());

    } else {

      // Bailout without retry

      C->record_method_not_compilable("RA Split failed: attempt to clone node with anti_dependence");

    }

    return 0;

  }

  return def->clone();

}

//------------------------------split_Rematerialize----------------------------

// Clone a local copy of the def.

Node *PhaseChaitin::split_Rematerialize(Node *def, Block *b, uint insidx, uint &maxlrg,

                                        GrowableArray<uint> splits, int slidx, uint *lrg2reach,

                                        Node **Reachblock, bool walkThru) {

  // The input live ranges will be stretched to the site of the new

  // instruction.  They might be stretched past a def and will thus

  // have the old and new values of the same live range alive at the

  // same time - a definite no-no.  Split out private copies of

  // the inputs.

  if (def->req() > 1) {

    for (uint i = 1; i < def->req(); i++) {

      Node *in = def->in(i);

      uint lidx = _lrg_map.live_range_id(in);

      // We do not need this for live ranges that are only defined once.

      // However, this is not true for spill copies that are added in this

      // Split() pass, since they might get coalesced later on in this pass.

      if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).is_singledef()) {

        continue;

      }

      Block *b_def = _cfg.get_block_for_node(def);

      int idx_def = b_def->find_node(def);

      // Cannot spill Op_RegFlags.

      Node *in_spill;

      if (in->ideal_reg() != Op_RegFlags) {

        in_spill = get_spillcopy_wide(MachSpillCopyNode::InputToRematerialization, in, def, i);

        if (!in_spill) { return 0; } // Bailed out

        insert_proj(b_def, idx_def, in_spill, maxlrg++);

        if (b_def == b) {

          insidx++;

        }

        def->set_req(i, in_spill);

      } else {

        // The 'in' defines a flag register. Flag registers can not be spilled.

        // Register allocation handles live ranges with flag registers

        // by rematerializing the def (in this case 'in'). Thus, this is not

        // critical if the input can be rematerialized, too.

        if (!in->rematerialize()) {

          assert(false, "Can not rematerialize %d: %s. Prolongs RegFlags live"

                 " range and defining node %d: %s may not be rematerialized.",

                 def->_idx, def->Name(), in->_idx, in->Name());

          C->record_method_not_compilable("attempted to spill a non-spillable item with RegFlags input");

          return 0; // Bailed out

        }

      }

    }

  }

  Node *spill = clone_node(def, b, C);

  if (spill == NULL || C->check_node_count(NodeLimitFudgeFactor, out_of_nodes)) {

    // Check when generating nodes

    return 0;

  }

  // See if any inputs are currently being spilled, and take the

  // latest copy of spilled inputs.

  if( spill->req() > 1 ) {

    for( uint i = 1; i < spill->req(); i++ ) {

      Node *in = spill->in(i);

      uint lidx = _lrg_map.find_id(in);

      // Walk backwards thru spill copy node intermediates

      if (walkThru) {

        while (in->is_SpillCopy() && lidx >= _lrg_map.max_lrg_id()) {

          in = in->in(1);

          lidx = _lrg_map.find_id(in);

        }

        if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).is_multidef()) {

          // walkThru found a multidef LRG, which is unsafe to use, so

          // just keep the original def used in the clone.

          in = spill->in(i);

          lidx = _lrg_map.find_id(in);

        }

      }

      if (lidx < _lrg_map.max_lrg_id() && lrgs(lidx).reg() >= LRG::SPILL_REG) {

        Node *rdef = Reachblock[lrg2reach[lidx]];

        if (rdef) {

          spill->set_req(i, rdef);

        }

      }

    }

  }

  assert( spill->out_RegMask().is_UP(), "rematerialize to a reg" );

  // Rematerialized op is def->spilled+1

  set_was_spilled(spill);

  if( _spilled_once.test(def->_idx) )

    set_was_spilled(spill);

  insert_proj( b, insidx, spill, maxlrg++ );

#ifdef ASSERT

  // Increment the counter for this lrg

  splits.at_put(slidx, splits.at(slidx)+1);

#endif

  // See if the cloned def kills any flags, and copy those kills as well

  uint i = insidx+1;

  int found_projs = clone_projs( b, i, def, spill, maxlrg);

  if (found_projs > 0) {

    // Adjust the point where we go hi-pressure

    if (i <= b->_ihrp_index) {

      b->_ihrp_index += found_projs;

    }

    if (i <= b->_fhrp_index) {

      b->_fhrp_index += found_projs;

    }

  }

  return spill;

}

//------------------------------is_high_pressure-------------------------------

// Function to compute whether or not this live range is "high pressure"

// in this block - whether it spills eagerly or not.

bool PhaseChaitin::is_high_pressure( Block *b, LRG *lrg, uint insidx ) {

  if( lrg->_was_spilled1 ) return true;

  // Forced spilling due to conflict?  Then split only at binding uses

  // or defs, not for supposed capacity problems.

  // CNC - Turned off 7/8/99, causes too much spilling

  // if( lrg->_is_bound ) return false;

  // Use float pressure numbers for vectors.

  bool is_float_or_vector = lrg->_is_float || lrg->_is_vector;

  // Not yet reached the high-pressure cutoff point, so low pressure

  uint hrp_idx = is_float_or_vector ? b->_fhrp_index : b->_ihrp_index;

  if( insidx < hrp_idx ) return false;

  // Register pressure for the block as a whole depends on reg class

  int block_pres = is_float_or_vector ? b->_freg_pressure : b->_reg_pressure;

  // Bound live ranges will split at the binding points first;

  // Intermediate splits should assume the live range's register set

  // got "freed up" and that num_regs will become INT_PRESSURE.

  int bound_pres = is_float_or_vector ? FLOATPRESSURE : INTPRESSURE;

  // Effective register pressure limit.

  int lrg_pres = (lrg->get_invalid_mask_size() > lrg->num_regs())

    ? (lrg->get_invalid_mask_size() >> (lrg->num_regs()-1)) : bound_pres;

  // High pressure if block pressure requires more register freedom

  // than live range has.

  return block_pres >= lrg_pres;

}

//------------------------------prompt_use---------------------------------

// True if lidx is used before any real register is def'd in the block

bool PhaseChaitin::prompt_use( Block *b, uint lidx ) {

  if (lrgs(lidx)._was_spilled2) {

    return false;

  }

  // Scan block for 1st use.

  for( uint i = 1; i <= b->end_idx(); i++ ) {

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

    // Ignore PHI use, these can be up or down

    if (n->is_Phi()) {

      continue;

    }

    for (uint j = 1; j < n->req(); j++) {

      if (_lrg_map.find_id(n->in(j)) == lidx) {

        return true;          // Found 1st use!

      }

    }

    if (n->out_RegMask().is_NotEmpty()) {

      return false;

    }

  }

  return false;

}

//------------------------------Split--------------------------------------

//----------Split Routine----------

// ***** NEW SPLITTING HEURISTIC *****

// DEFS: If the DEF is in a High Register Pressure(HRP) Block, split there.

//        Else, no split unless there is a HRP block between a DEF and

//        one of its uses, and then split at the HRP block.

//

// USES: If USE is in HRP, split at use to leave main LRG on stack.

//       Else, hoist LRG back up to register only (ie - split is also DEF)

// We will compute a new maxlrg as we go

uint PhaseChaitin::Split(uint maxlrg, ResourceArea* split_arena) {

  Compile::TracePhase tp("regAllocSplit", &timers[_t_regAllocSplit]);

  // Free thread local resources used by this method on exit.

  ResourceMark rm(split_arena);

  uint                 bidx, pidx, slidx, insidx, inpidx, twoidx;

  uint                 non_phi = 1, spill_cnt = 0;

  Node                *n1, *n2, *n3;

  Node_List           *defs,*phis;

  bool                *UPblock;

  bool                 u1, u2, u3;

  Block               *b, *pred;

  PhiNode             *phi;

  GrowableArray<uint>  lidxs(split_arena, maxlrg, 0, 0);

  // Array of counters to count splits per live range

  GrowableArray<uint>  splits(split_arena, maxlrg, 0, 0);