/*

 * Copyright 2000-2009 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_reg_split.cpp.incl"

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

  int ireg = def->ideal_reg();

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

    assert(false, "attempted to spill a non-spillable item");

    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;

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

      ((ireg != Op_RegL && ireg != Op_RegD // Single use or aligned

#ifdef _LP64

        && ireg != Op_RegP

#endif

         ) || o_mask->is_aligned_Pairs()) ) {

    // 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 (C) MachSpillCopyNode( 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->_nodes.size() &&

         (b->_nodes[i]->is_Proj() ||

          b->_nodes[i]->is_Phi() ) )

    i++;

  // Do not insert between a call and his Catch

  if( b->_nodes[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->_nodes[++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->_nodes.insert(i,spill);    // Insert node in block

  _cfg._bbs.map(spill->_idx,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->_nodes[loc] ) {

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

    b = b->_succs[b->_nodes[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(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( 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._bbs[use->_idx];

        // 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(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._bbs[b->pred(useidx)->_idx];

    bindex = b->end_idx();

  } else {

    // Put the clone just prior to use

    bindex = b->find_node(use);

  }

  Node *spill = get_spillcopy_wide( 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;

}

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

      // Check for single-def (LRG cannot redefined)

      uint lidx = n2lidx(in);

      if( lidx >= _maxlrg ) continue; // Value is a recent spill-copy

      if (lrgs(lidx).is_singledef()) continue;

      Block *b_def = _cfg._bbs[def->_idx];

      int idx_def = b_def->find_node(def);

      Node *in_spill = get_spillcopy_wide( 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);

    }

  }

  Node *spill = def->clone();

  if (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 = Find_id(in);

      // Walk backwards thru spill copy node intermediates

      if (walkThru) {

        while ( in->is_SpillCopy() && lidx >= _maxlrg ) {

          in = in->in(1);

          lidx = Find_id(in);

        }

        if (lidx < _maxlrg && 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 = Find_id(in);

        }

      }

      if( lidx < _maxlrg && 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;

  if( clone_projs( b, i, def, spill, maxlrg ) ) {

    // Adjust the point where we go hi-pressure

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

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

  }

  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;

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

  uint hrp_idx = lrg->_is_float ? 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 = lrg->_is_float ? 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 = lrg->_is_float ? 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->_nodes[i];

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

    if( n->is_Phi() ) continue;

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

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

  NOT_PRODUCT( Compile::TracePhase t3("regAllocSplit", &_t_regAllocSplit, TimeCompiler); )

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

  uint                 non_phi = 1, spill_cnt = 0;

  Node               **Reachblock;

  Node                *n1, *n2, *n3;

  Node_List           *defs,*phis;

  bool                *UPblock;

  bool                 u1, u2, u3;

  Block               *b, *pred;

  PhiNode             *phi;

  GrowableArray<uint>  lidxs;

  // Array of counters to count splits per live range

  GrowableArray<uint>  splits;

  //----------Setup Code----------

  // Create a convenient mapping from lrg numbers to reaches/leaves indices

  uint *lrg2reach = NEW_RESOURCE_ARRAY( uint, _maxlrg );

  // Keep track of DEFS & Phis for later passes

  defs = new Node_List();

  phis = new Node_List();

  // Gather info on which LRG's are spilling, and build maps

  for( bidx = 1; bidx < _maxlrg; bidx++ ) {

    if( lrgs(bidx).alive() && lrgs(bidx).reg() >= LRG::SPILL_REG ) {

      assert(!lrgs(bidx).mask().is_AllStack(),"AllStack should color");

      lrg2reach[bidx] = spill_cnt;

      spill_cnt++;

      lidxs.append(bidx);

#ifdef ASSERT

      // Initialize the split counts to zero

      splits.append(0);

#endif

#ifndef PRODUCT

      if( PrintOpto && WizardMode && lrgs(bidx)._was_spilled1 )

        tty->print_cr("Warning, 2nd spill of L%d",bidx);

#endif

    }

  }

  // Create side arrays for propagating reaching defs info.

  // Each block needs a node pointer for each spilling live range for the

  // Def which is live into the block.  Phi nodes handle multiple input

  // Defs by querying the output of their predecessor blocks and resolving

  // them to a single Def at the phi.  The pointer is updated for each

  // Def in the block, and then becomes the output for the block when

  // processing of the block is complete.  We also need to track whether

  // a Def is UP or DOWN.  UP means that it should get a register (ie -

  // it is always in LRP regions), and DOWN means that it is probably

  // on the stack (ie - it crosses HRP regions).

  Node ***Reaches     = NEW_RESOURCE_ARRAY( Node**, _cfg._num_blocks+1 );

  bool  **UP          = NEW_RESOURCE_ARRAY( bool*, _cfg._num_blocks+1 );

  Node  **debug_defs  = NEW_RESOURCE_ARRAY( Node*, spill_cnt );

  VectorSet **UP_entry= NEW_RESOURCE_ARRAY( VectorSet*, spill_cnt );

  // Initialize Reaches & UP

  for( bidx = 0; bidx < _cfg._num_blocks+1; bidx++ ) {

    Reaches[bidx]     = NEW_RESOURCE_ARRAY( Node*, spill_cnt );

    UP[bidx]          = NEW_RESOURCE_ARRAY( bool, spill_cnt );

    Node **Reachblock = Reaches[bidx];

    bool *UPblock     = UP[bidx];

    for( slidx = 0; slidx < spill_cnt; slidx++ ) {

      UPblock[slidx] = true;     // Assume they start in registers

      Reachblock[slidx] = NULL;  // Assume that no def is present

    }

  }

  // Initialize to array of empty vectorsets

  for( slidx = 0; slidx < spill_cnt; slidx++ )

    UP_entry[slidx] = new VectorSet(Thread::current()->resource_area());

  //----------PASS 1----------

  //----------Propagation & Node Insertion Code----------

  // Walk the Blocks in RPO for DEF & USE info

  for( bidx = 0; bidx < _cfg._num_blocks; bidx++ ) {

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

      return 0;

    }

    b  = _cfg._blocks[bidx];

    // Reaches & UP arrays for this block

    Reachblock = Reaches[b->_pre_order];

    UPblock    = UP[b->_pre_order];

    // Reset counter of start of non-Phi nodes in block

    non_phi = 1;

    //----------Block Entry Handling----------

    // Check for need to insert a new phi

    // Cycle through this block's predecessors, collecting Reaches

    // info for each spilled LRG.  If they are identical, no phi is

    // needed.  If they differ, check for a phi, and insert if missing,

    // or update edges if present.  Set current block's Reaches set to

    // be either the phi's or the reaching def, as appropriate.

    // If no Phi is needed, check if the LRG needs to spill on entry

    // to the block due to HRP.

    for( slidx = 0; slidx < spill_cnt; slidx++ ) {

      // Grab the live range number

      uint lidx = lidxs.at(slidx);

      // Do not bother splitting or putting in Phis for single-def

      // rematerialized live ranges.  This happens alot to constants

      // with long live ranges.

      if( lrgs(lidx).is_singledef() &&

          lrgs(lidx)._def->rematerialize() ) {

        // reset the Reaches & UP entries

        Reachblock[slidx] = lrgs(lidx)._def;

        UPblock[slidx] = true;

        // Record following instruction in case 'n' rematerializes and

        // kills flags

        Block *pred1 = _cfg._bbs[b->pred(1)->_idx];

        continue;

      }