osprey/be/cg/gra_mon/gra_spill.cxx

Go to the documentation of this file.

/*
 * Copyright 2002, 2003, 2004, 2005, 2006 PathScale, Inc.  All Rights Reserved.
 */

/*

  Copyright (C) 2000, 2001 Silicon Graphics, Inc.  All Rights Reserved.

  This program is free software; you can redistribute it and/or modify it
  under the terms of version 2 of the GNU General Public License as
  published by the Free Software Foundation.

  This program is distributed in the hope that it would be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

  Further, this software is distributed without any warranty that it is
  free of the rightful claim of any third person regarding infringement 
  or the like.  Any license provided herein, whether implied or 
  otherwise, applies only to this software file.  Patent licenses, if 
  any, provided herein do not apply to combinations of this program with 
  other software, or any other product whatsoever.  

  You should have received a copy of the GNU General Public License along
  with this program; if not, write the Free Software Foundation, Inc., 59
  Temple Place - Suite 330, Boston MA 02111-1307, USA.

  Contact information:  Silicon Graphics, Inc., 1600 Amphitheatre Pky,
  Mountain View, CA 94043, or:

  http://www.sgi.com

  For further information regarding this notice, see:

  http://oss.sgi.com/projects/GenInfo/NoticeExplan

*/

//  gra_spill implementation
//
//  Description:
//
//      Interface sugar with the cg_spill package.
//

//  $Revision: 1.16 $
//  $Date: 05/12/05 08:59:10-08:00 $
//  $Author: bos@eng-24.pathscale.com $
//  $Source: /scratch/mee/2.4-65/kpro64-pending/be/cg/gra_mon/SCCS/s.gra_spill.cxx $

#ifdef USE_PCH
#include "cg_pch.h"
#endif // USE_PCH
#pragma hdrstop

#include "import.h"
#include "defs.h"
#include "errors.h"
#include "cgir.h"
#include "cg.h"
#include "bb.h"
#include "bb_list.h"
#include "cgexp.h"
#include "cg_flags.h"
#include "cg_spill.h"
#include "cg_region.h"
#include "whirl2ops.h"
#include "opt_alias_interface.h"

#include "gra_bb.h"
#include "gra_lrange.h"
#include "lrange_list.h"
#include "gra_loop.h"
#include "gra_region.h"
#include "gra_trace.h"
#ifdef TARG_IA64
#include "ipfec_options.h"
#include "cgexp_internals.h"
#endif
#ifdef KEY
#include "calls.h"    // for Saved_Callee_Saved_Regs
#include "cxx_template.h" // for STACK

extern STACK<SAVE_REG_LOC> Saved_Callee_Saved_Regs;
#endif

BOOL GRA_optimize_placement = TRUE;
  // Should GRA optimize the placement of spills/restores generated by
  // splitting.  Exported so it can be disabled from the command line.

static LRANGE_LIST* spilled_lranges;
static LUNIT*       lunits_with_spills_head;
static LRANGE*      split_lranges_head;
static BB_LIST*     region_entry_glue_bbs;
static BB_LIST*     region_exit_glue_bbs;
static float        freq_spill_count, freq_restore_count;
static INT32        spill_count, restore_count;
float               priority_count;
#ifdef TARG_IA64
static INT32        spill_count_all, spill_count_with_nat; // used for UNAT
static TN*          unat_tn;
static TN*          orig_lrange_tn;
static TN_MAP       tn_unat_map;
#endif


// Data structures and functions to manipulate a list
// of spill locations for Optimize_Placement.  It keeps
// track of spills after the initial movement optimization
// so that they can later be considered for deletion of they
// are no longer needed.  This list will have elements that
// are either LUNIT's or GRA_BB's.  The reason for this is
// that when we move a save or restore, we do not create an
// LUNIT for it (as the block is not part of the live range).
// Rather, we simply annotate the GRA_BB structure to indicate
// that it requires a store above or a load below (lunit's are
// always store below and load above).  We must perform all of
// the moves prior to deleting any spill operations because the
// moves may make saves/restores that initially appear to be
// useless to be required after another spill is moved (i.e.
// a load that appears to reach no use will be needed if a
// spill is moved into its path to the exit).
class SPILL_LIST {
friend SPILL_LIST *SPILL_LIST_Create_Lunit(LUNIT *lunit, MEM_POOL *mempool);
friend SPILL_LIST* SPILL_LIST_Create_Gbb(GRA_BB* gbb, MEM_POOL *mempool);
  LUNIT*             lunit;             // pointer to lunit for spill
  GRA_BB*            gbb;               // pointer to gra_bb for spill
  BOOL               split_live_in;     // post split liveness analysis
  BOOL               split_defreach_out;
  BOOL         load_below_sticks;
  SPILL_LIST*        next;              // next spill in list

  void Init(void) { lunit = NULL; gbb = NULL; split_live_in = FALSE;
        split_defreach_out = FALSE; load_below_sticks = FALSE;
        next = NULL; }
public:
  SPILL_LIST(void) {}
  ~SPILL_LIST(void) {}

  // access member functions
  LUNIT *Lunit(void)      { return lunit; }
  GRA_BB *Gbb(void)     { return gbb; }
  SPILL_LIST *Next(void)    { return next; }
  BOOL Split_Live_In(void)    { return split_live_in; }
  void Split_Live_In_Set(void)    { split_live_in = TRUE; }
  BOOL Split_Defreach_Out(void)   { return split_defreach_out; }
  void Split_Defreach_Out_Set(void) { split_defreach_out = TRUE; }
  BOOL Load_Below_Sticks(void)    { return load_below_sticks; }
  void Load_Below_Sticks_Set(void)  { load_below_sticks = TRUE; }

  // inlined member functions
  GRA_BB* Get_Gbb(void)     { return lunit ? lunit->Gbb() : gbb; }
    // We only set lunit or gbb on the node (not both) so that we can quickly 
    // tell whether it's a spill from a move, or not.  So, get gbb off of 
    // lunit if present.
  SPILL_LIST *Push(SPILL_LIST *new_sl)  { new_sl->next = this; return new_sl; }
    // push a new element on to the head of the list; return the new element.
};

// create a list element for an lunit.
inline SPILL_LIST *SPILL_LIST_Create_Lunit(LUNIT *lunit, MEM_POOL *mempool)
{
  SPILL_LIST *new_sl = TYPE_MEM_POOL_ALLOC(SPILL_LIST, mempool);
  new_sl->Init();
  new_sl->lunit = lunit;
  return(new_sl);
}

// create a list element for an gbb.
inline SPILL_LIST* SPILL_LIST_Create_Gbb(GRA_BB* gbb, MEM_POOL *mempool)
{
  SPILL_LIST *new_sl = TYPE_MEM_POOL_ALLOC(SPILL_LIST, mempool);
  new_sl->Init();
  new_sl->gbb = gbb;
  return(new_sl);
}


// list structure
inline void
Possibly_List_LUNIT(LUNIT* lunit)
//
//  Add <lunit> to lunits_with_spills_head if not already.
//
{
  if ( ! lunit->Spill_Listed() ) {
    lunit->Spill_Listed_Set();
    lunits_with_spills_head =
      lunits_with_spills_head->Spill_List_Push(lunit);
  }
}


inline void
Possibly_List_LRANGE( LRANGE* lrange )
//
//  Add <lunit> to lunits_with_spills_head if not already.
//
{
  if (! lrange->Split_Listed()) {
    lrange->Split_Listed_Set();
    split_lranges_head = split_lranges_head->Split_List_Push(lrange);
  }
}

#ifdef TARG_IA64
// Initial unat spill
static void 
UNAT_Spill_Initialize(void)
{
    LRANGE_LIST *l;
    TN *tn;
    INT unat_size = 64;

    spill_count_all = 0;
    spill_count_with_nat = 0;
    if (!IPFEC_Enable_Insert_UNAT || !IPFEC_Enable_Speculation) return;

    for ( l = spilled_lranges; l != NULL; l = LRANGE_LIST_rest(l)) {
        tn = LRANGE_LIST_first(l)->Tn();
        if (TN_is_float(tn)) continue; // float tn not in count

        if (TN_is_take_nat(tn))
           spill_count_with_nat++;
        spill_count_all++;
    }
    unat_tn = Build_Dedicated_TN(ISA_REGISTER_CLASS_application,(REGISTER)(REGISTER_MIN + 36),0);
    tn_unat_map = TN_MAP_Create();

    if (spill_count_all > unat_size && spill_count_with_nat > 1)
        DevWarn("Insert UNAT spill for spill count %d > %d. ", spill_count_all, unat_size);
    if (spill_count_with_nat >= 1)
        DevWarn("Insert UNAT spill for spill count with nat bit %d >= 1",spill_count_with_nat);
}

// Call after spill and restore
static void 
UNAT_Spill_Finish(void)
{
    TN_MAP_Delete(tn_unat_map);
}

// Determine need or not insert unat spill and 
// restore for each lrange;
static BOOL
Need_UNAT_Spill_Restore(TN *lrange_tn)
{
    int unat_size=64;

    if (!IPFEC_Enable_Insert_UNAT || !IPFEC_Enable_Speculation) return FALSE;

    if (lrange_tn != NULL) {
        if (lrange_tn == unat_tn) return TRUE;
        // lrange->tn should be nat bit possible;
        if  (!TN_is_take_nat(lrange_tn)) return FALSE;
        return spill_count_all>unat_size &&
               spill_count_with_nat > 1 ? TRUE : FALSE;
    }
    return FALSE;
}

//
//  Need insert unat spill and restore code
//  in entry and exit BB
BOOL
Need_UNAT_Entry_Exit(void) {
    if (!IPFEC_Enable_Insert_UNAT || !IPFEC_Enable_Speculation) return FALSE;
    return spill_count_with_nat>=1 ? TRUE : FALSE;
}

void
UNAT_Spill_OPS(TN *lrange_tn, ST *lrange_st, OPS *ops, CGSPILL_CLIENT client, BB *bb)
//
//  Insert ar.unat spill code  to op list
//
{
  ST *st = NULL;
  if (TN_is_float(lrange_tn)) return;

  TN* tn = unat_tn; 

  if (!Need_UNAT_Spill_Restore(lrange_tn)) return; 

  TN* spill_tn = Gen_Register_TN(ISA_REGISTER_CLASS_integer,8);
 
  OPS_Remove_All(ops);
  Expand_Copy(spill_tn, tn, MTYPE_I8, ops);
  for (OP* op = OPS_first(ops); op != NULL; op = OP_next(op))
  {
    OP_Change_Opcode(op, TOP_mov_f_ar_m);
    Reset_OP_copy(op);
  }
  // set TN map
  if (lrange_tn != tn)
      st = (ST *)TN_MAP_Get(tn_unat_map, orig_lrange_tn);
  else
      orig_lrange_tn = lrange_tn;
  if (st == NULL || lrange_tn==tn) {
      st = CGSPILL_Get_TN_Spill_Location(spill_tn,CGSPILL_GRA); 
      TN_MAP_Set(tn_unat_map, orig_lrange_tn, st);
  }
  CGSPILL_Store_To_Memory(spill_tn, st, ops, CGSPILL_GRA, bb);
}
void
UNAT_Restore_OPS(TN *lrange_tn, ST *lrange_st, OPS *ops, CGSPILL_CLIENT client, BB *bb)
//
//  Insert ar.unat restore code to op list
//
{
  if (TN_is_float(lrange_tn)) return;

  TN* tn = unat_tn;
  if (!Need_UNAT_Spill_Restore(lrange_tn)) return;

  TN* restore_tn = Gen_Register_TN(ISA_REGISTER_CLASS_integer,8);

  OPS_Remove_All(ops);
  Expand_Copy(tn, restore_tn, MTYPE_I8, ops);
  // replace mov by mov_t_ar
  for (OP* op = OPS_first(ops); op != NULL; op = OP_next(op))
  {
    OP_Change_Opcode(op, TOP_mov_t_ar_r_m);
    Reset_OP_copy(op);
  }             

  // insert tn restore
  if (lrange_tn == tn) {orig_lrange_tn = tn;}
  ST *st = (ST *)TN_MAP_Get(tn_unat_map, orig_lrange_tn);
  if (st == NULL) {
       st = CGSPILL_Get_TN_Spill_Location(restore_tn,CGSPILL_GRA);
       TN_MAP_Set(tn_unat_map, orig_lrange_tn, st);
  }
  OPS r_ops = OPS_EMPTY;
  CGSPILL_Load_From_Memory(restore_tn, st, &r_ops, CGSPILL_GRA, bb);
  OPS_Prepend_Ops(ops, &r_ops);
}     
#endif // TARG_IA64

inline void
Gen_Spill_Restore( TN* tn, ST* spill_loc, GRA_BB* gbb,
      void (*gen_fn)(TN*,ST*,OPS*,CGSPILL_CLIENT,BB*),
      void (*add_fn)(BB*,OPS*),
      void (*insert_fn)(TN*, BB*, OPS*),
      BOOL insert_flag)
//
//  Generate a spill or restore for <tn> using <spill_loc> in <gbb>.  The
//  <gen_fn> is one of CGSPILL_Store_To_Memory or CGSPILL_Load_From_Memory
//  depending whether a spill or restore is to be generated.  The <add_fn> is
//  one of CGSPILL_Append_Ops or CGSPILL_Prepend_Ops depending on whether the
//  new operations should be added to the top or bottom of <gbb>.
//
{
  OPS spill_ops = OPS_EMPTY;
  BB* bb        = gbb->Bb();

  Is_True(gbb->Region_Is_Complement(),
    ("Spilling TN%d in previously allocated region BB:%d",
      TN_number(tn), BB_id(bb)));

  Reset_BB_scheduled(bb);
  gen_fn(tn,spill_loc,&spill_ops, CGSPILL_GRA, bb);
  if (insert_flag &&
      (GRA_ensure_spill_proximity ||
       (CG_local_skip_equal != GRA_pu_num &&
  GRA_pu_num <= CG_local_skip_after &&
  GRA_pu_num >= CG_local_skip_before))) {
    insert_fn(tn, bb, &spill_ops);
  } else {
    add_fn(bb,&spill_ops);
  }
}

static void
TN_Spill_Below( TN* tn, ST* spill_loc, GRA_BB* gbb, BOOL insert_after )
//
//  Generate a save of <tn> to <spill_loc> at the bottom of <gbb>.
//
{
  freq_spill_count += gbb->Freq();
  ++spill_count;
#ifdef TARG_IA64
  if (insert_after) {
      Gen_Spill_Restore(tn,spill_loc,gbb,UNAT_Spill_OPS,
                        CGSPILL_Append_Ops,
                        CGSPILL_Insert_Ops_After_Last_Def,
                        insert_after); 
  }
#endif
  Gen_Spill_Restore(tn,spill_loc,gbb,CGSPILL_Store_To_Memory,
        CGSPILL_Append_Ops,
        CGSPILL_Insert_Ops_After_Last_Def,
        insert_after);
#ifdef TARG_IA64
  if (!insert_after) {
      Gen_Spill_Restore(tn,spill_loc,gbb,UNAT_Spill_OPS,
                        CGSPILL_Append_Ops,
                        CGSPILL_Insert_Ops_After_Last_Def,
                        insert_after); 
  }
#endif
}

static void
TN_Restore_Above( TN* tn, ST* spill_loc, GRA_BB* gbb, BOOL insert_before )
//
//  Generate a restore of <tn> from <spill_loc> at the top of <gbb>.
//
{
  
  freq_restore_count += gbb->Freq();
  ++restore_count;
#ifdef TARG_IA64
  if (insert_before) {
      Gen_Spill_Restore(tn,spill_loc,gbb,UNAT_Restore_OPS,
                CGSPILL_Prepend_Ops,
            CGSPILL_Insert_Ops_Before_First_Use,
            insert_before);
  }
#endif
  Gen_Spill_Restore(tn,spill_loc,gbb,CGSPILL_Load_From_Memory,
        CGSPILL_Prepend_Ops,
        CGSPILL_Insert_Ops_Before_First_Use,
        insert_before);
#ifdef TARG_IA64
  if (!insert_before) {
      Gen_Spill_Restore(tn,spill_loc,gbb,UNAT_Restore_OPS,
                CGSPILL_Prepend_Ops,
            CGSPILL_Insert_Ops_Before_First_Use,
            insert_before);
  }
#endif
}

static void
TN_Spill_Above( TN* tn, ST* spill_loc, GRA_BB* gbb )
//
//  Generate a save of <tn> to <spill_loc> at the bottom of <gbb>.
//
{
  freq_spill_count += gbb->Freq();
  ++spill_count;
#ifdef TARG_IA64
  Gen_Spill_Restore(tn,spill_loc,gbb,UNAT_Spill_OPS,
        CGSPILL_Prepend_Ops,
        CGSPILL_Insert_Ops_After_Last_Def,
        FALSE);
#endif
  Gen_Spill_Restore(tn,spill_loc,gbb,CGSPILL_Store_To_Memory,
        CGSPILL_Prepend_Ops,
        CGSPILL_Insert_Ops_After_Last_Def,
        FALSE);
}

static void
TN_Restore_Below( TN* tn, ST* spill_loc, GRA_BB* gbb )
//
//  Generate a restore of <tn> from <spill_loc> at the top of <gbb>.
//
{
  freq_restore_count += gbb->Freq();
  ++restore_count;
#ifdef TARG_IA64
  Gen_Spill_Restore(tn,spill_loc,gbb,UNAT_Restore_OPS,
        CGSPILL_Append_Ops,
        CGSPILL_Insert_Ops_Before_First_Use,
        FALSE);
#endif
  Gen_Spill_Restore(tn,spill_loc,gbb,CGSPILL_Load_From_Memory,
        CGSPILL_Append_Ops,
        CGSPILL_Insert_Ops_Before_First_Use,
        FALSE);
}

static void
LRANGE_Spill_Above( LRANGE* lrange, GRA_BB* gbb )
//
//  Add a spill of <lrange> at the top of <gbb>
//
{
  TN* tn        = lrange->Tn();
  TN* orig_tn   = lrange->Original_TN();
  ST* st        = CGSPILL_Get_TN_Spill_Location(orig_tn,CGSPILL_GRA);

#ifdef TARG_IA64
  orig_lrange_tn = orig_tn;
#endif
  TN_Spill_Above(tn,st,gbb);
}

static void
LRANGE_Restore_Below( LRANGE* lrange, GRA_BB* gbb )
//
//  Add a restore of <lrange> at the bottom of <gbb>
//
{
  TN* tn        = lrange->Tn();
  TN* orig_tn   = lrange->Original_TN();
  ST* st        = CGSPILL_Get_TN_Spill_Location(orig_tn,CGSPILL_GRA);

#ifdef TARG_IA64
  orig_lrange_tn = orig_tn;
#endif
  TN_Restore_Below(tn,st,gbb);
}

static void
LRANGE_Spill_Below( LRANGE* lrange, GRA_BB* gbb )
//
//  Add a spill of <lrange> at the top of <gbb>
//
{
  TN* tn        = lrange->Tn();
  TN* orig_tn   = lrange->Original_TN();
  ST* st        = CGSPILL_Get_TN_Spill_Location(orig_tn,CGSPILL_GRA);
  LUNIT *lunit  = NULL;
  
#ifdef TARG_IA64
  orig_lrange_tn = orig_tn;
#endif
  //
  // will insert after last def if there is a reference to the tn
  // in the block.
  //
  (void) lrange->Find_LUNIT_For_GBB(gbb, &lunit);

#ifdef KEY
  if (GRA_optimize_boundary ||
      gbb->Clobbers_Reg_Class(lrange->Rc())) {
    // Always spill after the last define.  If no such define, spill at the top
    // of the BB.
    TN_Spill_Below(tn,st,gbb,TRUE);
  } else
#endif
  TN_Spill_Below(tn,st,gbb,lunit && lunit->True_Reference());
}

static void
LRANGE_Restore_Above( LRANGE* lrange, GRA_BB* gbb )
//
//  Add a restore of <lrange> at the bottom of <gbb>
//
{
  TN* tn        = lrange->Tn();
  TN* orig_tn   = lrange->Original_TN();
  ST* st        = CGSPILL_Get_TN_Spill_Location(orig_tn,CGSPILL_GRA);
  LUNIT *lunit  = NULL;
  
#ifdef TARG_IA64  
  orig_lrange_tn = orig_tn;
#endif
  //
  // will insert before first use if there is a reference to the tn
  // in the block.
  //
  (void) lrange->Find_LUNIT_For_GBB(gbb, &lunit);

#ifdef KEY
  if (GRA_optimize_boundary ||
      gbb->Clobbers_Reg_Class(lrange->Rc())) {
    // Always restore before the first use.  If no such use, restore at the
    // bottom of the BB.
    TN_Restore_Above(tn,st,gbb,TRUE);
  } else
#endif
  TN_Restore_Above(tn,st,gbb,lunit && lunit->True_Reference());
}


static void
Spill_Homeable_TN(
    GRA_BB* gbb,
    TN*     orig_tn,
    TN*     new_tn,
    ST*     st,
    LUNIT*  lunit,
    LRANGE* lrange
)
// 
//  Spill tn with a home location.
//
{
  GRA_BB_OP_FORWARD_ITER iter;
  ALIAS_RESULT alias;
  BOOL aliased_store_seen = FALSE;
  BOOL need_store = FALSE; // whether homing store needed later in this BB
  BOOL homing_load_removed = FALSE;
  BOOL def_seen = FALSE;  // a def of the TN has been seen
  BOOL need_load = FALSE; // whether homing load needed at start of this BB

  GRA_Trace_Homing(orig_tn, gbb->Bb());

  for (iter.Init(gbb); ! iter.Done(); ) {
    INT i;
    OP* op = iter.Current();
    iter.Step();
    BOOL op_is_homing_store = FALSE;
    BOOL op_is_homing_load = FALSE;

    //
    // get aliasing information on any load or store.  if its to the
    // same location, then check to see if we need it.
    //
    if (OP_store(op) || OP_load(op)) {
      WN *wn = Get_WN_From_Memory_OP(op);
      if (wn != NULL) {
  alias = Aliased(Alias_Manager, TN_home(orig_tn), wn);
  if (alias == SAME_LOCATION) {

    //
    // we need the store if we've defined the TN previosly in
    // the block (we have to store somewhere since we've defined
    // the tn, and we'll need the store here in case we have a use of
    // the tn on the other side of a possibly aliased store).
    // we need the load if we've stored to a possibly aliased
    // memory location previously in the block, or the load is not
    // to the tn we're homing.  in this case, we assume that there is
    // a local use of this value.
    //
    INT st_op_num = TOP_Find_Operand_Use(OP_code(op), OU_storeval);
    if ((OP_store(op) && !need_store &&
         orig_tn == OP_opnd(op, st_op_num)) ||
        (OP_load(op) && !aliased_store_seen &&
         OP_result(op, 0) == orig_tn)) {
#ifdef KEY
      // Both OPs in a stlpd/sthpd pair have the same WN, yet the sthpd
      // should not be deleted.  The second of such pair is always marked
      // cond_def, so check for it.  Bug 10550.
      if (!OP_cond_def(op))
#endif
        {
    GRA_Trace_Home_Removal(orig_tn, gbb, op);
    BB_Remove_Op(gbb->Bb(), op);
    if (OP_load(op)) homing_load_removed = TRUE;
    continue;
        }
    } else if (OP_store(op)) {
      //
      // won't need to store at bottom of the block unless another
      // def of the tn is found
      //
#ifdef KEY  // Don't need store at bottom of BB only if the earlier store
      // stores the same TN.  Bug 9429.
            if (OP_opnd(op, st_op_num) == orig_tn) {
        need_store = FALSE;
        op_is_homing_store = TRUE;
            }
#else
      need_store = FALSE;
            if (OP_opnd(op, st_op_num) == orig_tn)
        op_is_homing_store = TRUE;
#endif
          } else if (OP_load(op) && OP_result(op, 0) == orig_tn) {
      op_is_homing_load = TRUE;
    }
  } else if (alias == POSSIBLY_ALIASED && OP_store(op)) {
    aliased_store_seen = TRUE;
  }
      } else {
  alias = NOT_ALIASED;
      }
    } else {
      alias = NOT_ALIASED;
    }

    // 
    // rename uses and any definitions or uses of the tn at this
    // op.
    //
    for ( i = OP_opnds(op) - 1; i >= 0; --i ) {
      if ( OP_opnd(op,i) == orig_tn) {
  //
  // homing stores don't count as exposed uses
  //
  if (!def_seen && !op_is_homing_store) {
    need_load = TRUE;
  }
  Set_OP_opnd(op, i, new_tn);
      }
    }
    for ( i = OP_results(op) - 1; i >= 0; --i ) {
      if ( OP_result(op,i) == orig_tn) {
  //
  // homing loads don't really redefine the tn
  //
  if (!op_is_homing_load) {
    need_store = TRUE;
#ifdef KEY
    if (OP_cond_def(op) && !def_seen)
      need_load = TRUE;
#endif
  }
  def_seen = TRUE;
  Set_OP_result(op, i, new_tn);
      }
    }
  }

  //
  // load if exposed use seen and the tn is live in, or a restore
  // at the top of the block is required by a split.  also restore
  // if we blew away a homing load that provided the definition of
  // the tn for a use (that is now exposed, but wasn't before).
  //
  if (need_load && (lunit->Restore_Above() ||
        gbb->Is_Live_In_LRANGE(lrange) ||
        homing_load_removed)) {
    TN_Restore_Above(new_tn,st,gbb,TRUE);
    gbb->Remove_Live_In_LRANGE(lrange);
  }
  if (need_store && (lunit->Spill_Below() ||
         gbb->Is_Live_Out_LRANGE(lrange))) {
    TN_Spill_Below(new_tn,st,gbb,TRUE);
    gbb->Remove_Live_Out_LRANGE(lrange);
  }
}

static TN*
Make_Dedicated_Save_TN(TN* save_tn, TN* dedicated_tn, ST* spill_st)
//
//  Create a dedicated TN like <dedicated_tn> with the save_tn properties
//  of <save_tn>.  This is so that we can spill and reload floating point
//  save_tn's, and the dwarf frame building code can still find the spills
//  of the callee saved registers.
//
{
  TN* new_tn = Dup_TN_Even_If_Dedicated(dedicated_tn);
  Set_TN_is_dedicated(new_tn);
  Set_TN_register_and_class(new_tn, TN_register_and_class(dedicated_tn));
  Set_TN_save_creg(new_tn, TN_save_creg(save_tn));
  Set_TN_spill(new_tn, spill_st);

  return(new_tn);
}
  
       
static void
Spill_Prolog_Epilog_Save_LUNIT(LRANGE* lrange, LUNIT* lunit, GRA_BB* gbb,
             ST* st)
//
//  We must not allow the save tn copies to remain if we spill in them
//  in the prolog and epilog blocks.  Previously, we had allowed lra to
//  get rid of them via copy preferencing.  This can't work reliably
//  for floats on the R10K.  The reason is that the copies are double
//  precision, and the architecture requires that the contents of the
//  source of the copy be a valid double precision value.  Obviously,
//  on procedure entry we can't know that, so we cannot take the risk
//  that lra's resecheduling pass will introduce a conflict that will
//  prevent the preference and leave the copy.  This isn't necessary for
//  integer registers (nor for register moves in general on most
//  architectures), and there are lots of special purpose integer registers
//  that we'd have to pussy foot around (gp, fp, etc ....) so we won't
//  deal with them.
//
{
  BB* bb = gbb->Bb();
  TN* tn = lrange->Tn();
  OP* op;
  OPS ops;

  if (lunit->Has_Exposed_Use() &&
      (lunit->Restore_Above() || gbb->Is_Live_In_LRANGE(lrange))) {

    //
    // Find the copy to the dedicated TN.
    //
    for (op = BB_first_op(bb); op != NULL; op = OP_next(op)) {
      if (OP_copy(op) && tn == CGTARG_Copy_Operand_TN(op)) {
  break;
      }
    }
    TN* new_tn = Make_Dedicated_Save_TN(tn, OP_result(op, 0), st); 
    CGSPILL_Load_From_Memory(new_tn, st, OPS_Init(&ops), CGSPILL_GRA, bb);
    freq_restore_count += gbb->Freq();
    ++restore_count;
    CGSPILL_Insert_Ops_Before(bb, op, &ops);
    BB_Remove_Op(bb, op);
    //
    // Rename in case some bizarre copy optimization has made another
    // use of the save tn (this happened with the return address in
    // an epilog block).
    //
    gbb->Rename_TN_References(tn, OP_result(op, 0));    
    gbb->Remove_Live_In_LRANGE(lrange); 
  }

  if (lunit->Has_Def() &&
      (lunit->Spill_Below() || gbb->Is_Live_Out_LRANGE(lrange))) {
    //
    // Find the copy from the dedicated TN.
    //
    for (op = BB_first_op(bb); op != NULL; op = OP_next(op)) {
      if (OP_copy(op) && tn == OP_result(op, 0)) {
  break;
      }
    }
    TN* new_tn = Make_Dedicated_Save_TN(tn, CGTARG_Copy_Operand_TN(op), st); 
    Set_TN_save_creg(new_tn, TN_save_creg(tn));
    CGSPILL_Store_To_Memory(new_tn, st, OPS_Init(&ops), CGSPILL_GRA, bb);
    freq_spill_count += gbb->Freq();
    ++spill_count;
    CGSPILL_Insert_Ops_After(bb, op, &ops);
    BB_Remove_Op(bb, op);

    //
    // Rename in case some bizarre copy optimization has made another
    // use of the save tn (this happened with the return address in
    // an epilog block).
    //
    gbb->Rename_TN_References(tn, CGTARG_Copy_Operand_TN(op));
    gbb->Remove_Live_Out_LRANGE(lrange);
  }
}


#ifdef TARG_IA64
extern INIT_USE_ONLY_GTN* GTN_USE_ONLY;
extern BOOL Search_Used_Only_Once_GTN (TN *find_tn,BB* def_bb);
#endif

static void
LUNIT_Spill(LUNIT* lunit)
//
//  Restore above, spill below, and localize LUNIT.
//
{
  if ( lunit->Has_Exposed_Use() || lunit->Has_Def() ) {
    LRANGE* lrange  = lunit->Lrange();
    GRA_BB* gbb     = lunit->Gbb();
    BB*     bb      = gbb->Bb();
    TN*     tn      = lrange->Tn();
    TN*     orig_tn = lrange->Original_TN();
    ST*     st      = CGSPILL_Get_TN_Spill_Location(orig_tn,CGSPILL_GRA);

#ifdef TARG_IA64
    // Record index of unat spill location for interface is fixed
    // This method is not very well.
    orig_lrange_tn = orig_tn;
#endif

#ifdef KEY
    if (BB_handler(bb) && BB_entry(bb) && TN_is_save_reg(orig_tn) &&
  lunit->Has_Def() && 
  (lunit->Spill_Below() || gbb->Is_Live_Out_LRANGE(lrange))) {
      // omit generating the save at handler entries
      TN*     ltn     = Dup_TN(tn);
      Set_TN_spill(ltn, st);
      gbb->Rename_TN_References(tn,ltn);    
      gbb->Remove_Live_Out_LRANGE(lrange);
      return;
    }

    // put saved location info in Saved_Callee_Saved_Regs for dwarf generation
    if (TN_is_save_reg(orig_tn) && BB_entry(bb)) {
      SAVE_REG_LOC sr;
      sr.user_allocated = FALSE;
      sr.temp = st;
      sr.ded_tn = Build_Dedicated_TN(TN_save_rclass(orig_tn), 
                   TN_save_reg(orig_tn), 0);
      Saved_Callee_Saved_Regs.Push(sr);
    }
#endif

    //
    // Spills of save tn's in prolog/epilog blocks handled specially.
    // Only deal with fp TNs.  There are too many special integer registers,
    // so it's not worth it.
    //
    if (!(TN_is_save_reg(orig_tn) && (BB_entry(bb) || BB_exit(bb)) &&
    TN_is_float(orig_tn))) {
      TN*     ltn     = Dup_TN(tn);

      Set_TN_spill(ltn, st);
      if (TN_is_gra_homeable(tn)) {
  Spill_Homeable_TN(gbb,tn,ltn,st,lunit,lrange);
  return;
      }

      gbb->Rename_TN_References(tn,ltn);    
#ifdef TARG_IA64  // zhc
      BOOL restore_above = FALSE;
      //
      //delete unecessary restore and spill during GRA
      //1:GTN which used only once and its def and use are in the same bb
      //  do not spill it if the bb is not a loop bb
      //2:If a used_only_once_GTN does not ld at the beginning,
      //  do not spill it at the end of bb
      //3::If 2 op have the same res_tn and guarded by disjoint predicates
      //   only set the flags of def for the tn ,Not set the flags of use.
      //
      if (lunit->Has_Exposed_Use() &&
    (lunit->Restore_Above() ||
     gbb->Is_Live_In_LRANGE(lrange))) {
           restore_above = TRUE;
  TN_Restore_Above(ltn,st,gbb,TRUE);
  gbb->Remove_Live_In_LRANGE(lrange);
      }

      if (lunit->Has_Def() &&
    (lunit->Spill_Below() ||
     gbb->Is_Live_Out_LRANGE(lrange))) {
              if ((!restore_above)&&(Search_Used_Only_Once_GTN(orig_tn,bb))) {
                 gbb->Remove_Live_Out_LRANGE(lrange);
                 return ;

              }
              if ((restore_above)&&Search_Used_Only_Once_GTN(orig_tn,bb)){
                 if (BB_nest_level(bb)==0) {
                    gbb->Remove_Live_Out_LRANGE(lrange);
                    return ;
                 }
              }
              TN_Spill_Below(ltn,st,gbb,TRUE);
              gbb->Remove_Live_Out_LRANGE(lrange);
#else // TARG_IA64
      if (lunit->Has_Exposed_Use() &&
    (lunit->Restore_Above() ||
     gbb->Is_Live_In_LRANGE(lrange))) {
  TN_Restore_Above(ltn,st,gbb,TRUE);
  gbb->Remove_Live_In_LRANGE(lrange);
      }

      if (lunit->Has_Def() &&
    (lunit->Spill_Below() ||
     gbb->Is_Live_Out_LRANGE(lrange))) {
  TN_Spill_Below(ltn,st,gbb,TRUE);
  gbb->Remove_Live_Out_LRANGE(lrange);
#endif // TARG_IA64
      }
    } else {
      Spill_Prolog_Epilog_Save_LUNIT(lrange, lunit, gbb, st);
    }
  }
}


static void
LRANGE_Spill( LRANGE* lrange )
//
//  Restore lrange at the top and spill it at the bottom of every block in
//  which it has a use.  [Only do the restores if it is live-in and the spills
//  if it is live out (and TODO: has a definition in the block)]
//
{
  LRANGE_LUNIT_ITER iter;

  if (lrange->No_Appearance()) 
    return; // no need to generate spill code

#ifdef TARG_X8664
  TN*     orig_tn = lrange->Original_TN();
  if (CG_push_pop_int_saved_regs && ! Gen_Frame_Pointer &&
      ! TN_is_float(orig_tn) && TN_is_save_reg(orig_tn)) {
    // put saved location info in Saved_Callee_Saved_Regs for dwarf generation
    SAVE_REG_LOC sr;
    sr.user_allocated = FALSE;
    sr.temp = NULL;
    sr.ded_tn = Build_Dedicated_TN(TN_save_rclass(orig_tn), 
           TN_save_reg(orig_tn), 0);
    Saved_Callee_Saved_Regs.Push(sr);
    // pretend it has been assigned its register to make LRA happy
    TN_Allocate_Register(orig_tn, TN_register(sr.ded_tn));
    return;
  }
#endif

  for (iter.Init(lrange); ! iter.Done(); iter.Step()) {
    LUNIT*  lunit = iter.Current();

    LUNIT_Spill(lunit);
  }
}

#ifdef TARG_IA64
void
Gen_UNAT_Spills_Entry_And_Exit_BB(void)
//
//  Generate ar.unat spill code in entry and exit bb
//
{

  BB_LIST *elist;
  BB *bb;
  OPS ops = OPS_EMPTY;
  TN *spill_tn, *restore_tn;

  // determine need or not
  if ( !Need_UNAT_Entry_Exit() ) return;
 
  // create dedicated tn for ar.unat;
  TN* tn = unat_tn;
   
  
  // at the entry blocks
  for (elist = Entry_BB_Head; elist; elist = BB_LIST_rest(elist)) {
    bb = BB_LIST_first(elist);
    UNAT_Spill_OPS(tn, NULL, &ops, CGSPILL_GRA, bb);

    // insert spill code
    CGSPILL_Prepend_Ops(bb, &ops);
    OPS_Remove_All(&ops);
  }


  // at the exit blocks
  for (elist = Exit_BB_Head; elist; elist = BB_LIST_rest(elist)) {
    bb = BB_LIST_first(elist);
    UNAT_Restore_OPS(tn, NULL, &ops, CGSPILL_GRA, bb);

    // insert tn restore
    CGSPILL_Append_Ops(bb, &ops);
    OPS_Remove_All(&ops);
  }
  
  // finish unat spill restore;
  UNAT_Spill_Finish();
}
#endif

static void
Identify_Initialize_Glue_Blocks(void)
//
//  Find the blocks that are exits and/or entries to previously allocated
//  regions.  On return the lists region_exit_glue_bbs and
//  region_entry_glue_bbs contain these blocks.
//
{
  BB* bb;
  BB* succ_bb;
  BB* pred_bb;

  region_entry_glue_bbs = NULL;
  region_exit_glue_bbs = NULL;

  for ( bb = REGION_First_BB; bb != NULL; bb = BB_next(bb) ) {
    GRA_BB* gbb = gbb_mgr.Get(bb);

    if ( gbb->Region_Is_Complement() ) {
      //
      // regions may not have entry or exit glue blocks if they
      // do not have any global tn's live in, or live out, respectively.
      // unique predecessor/successors of a complement block that are
      // part of a previously allocated region is not sufficient to
      // indicate a glue block.  the parent rid must be checked.
      //
      pred_bb = BB_Unique_Predecessor(bb);
      succ_bb = BB_Unique_Successor(bb);
      if (pred_bb != NULL && BB_rid(pred_bb) != NULL) {
  if (RID_parent(BB_rid(pred_bb)) == BB_rid(bb)) {
    region_exit_glue_bbs = BB_LIST_Push(bb,region_exit_glue_bbs,GRA_pool);
  }
      }
      if (succ_bb != NULL && BB_rid(succ_bb) != NULL) {
  if (RID_parent(BB_rid(succ_bb)) == BB_rid(bb)){
    region_entry_glue_bbs = BB_LIST_Push(bb,region_entry_glue_bbs,GRA_pool);
  }
      }
    }
  }
}

static BOOL
Complement_TN( const TN* tn )
//
//  Does <tn> correspond to a complement LRANGE?
//
{
  LRANGE* lrange = lrange_mgr.Get(tn);

  return lrange != NULL && lrange->Type() == LRANGE_TYPE_COMPLEMENT;
}

static BOOL
Region_TN( const TN* tn, const GRA_REGION* region )
//
//  Does <tn> correspond to a region LRANGE?  If so, return TRUE and assert
//  that it belogs to the given <region>.
//
{
  LRANGE* lrange = lrange_mgr.Get(tn);

  if ( lrange != NULL && lrange->Type() == LRANGE_TYPE_REGION ) {
    DevAssert(lrange->Region() == region,
              ("Unexpected source region in glue copy"));
    return TRUE;
  }

  return FALSE;
}

static BOOL
Uses_Region_TN( const OP* op, const GRA_REGION* region )
//
//  Does <op> have a region TN operand?  If so, return TRUE and assert that
//  it belongs to the given <region>.
//
{
  INT i;

  for ( i = OP_opnds(op) - 1; i >= 0; --i ) {
    if ( Region_TN(OP_opnd(op,i),region) )
      return TRUE;
  }

  return FALSE;
}

static void
Map_Operands( TN_MAP map, OP* op )
//
//  Set the value of each operand of <op> to be TRUE in <map>
//
{
  INT i;

  for ( i = OP_opnds(op) - 1; i >= 0; --i ) {
    TN* tn = OP_opnd(op,i);
#ifdef TARG_IA64
    if(TN_is_constant(tn)) continue;
#endif

    DevAssert(! Complement_TN(tn),("Complement TN%d in glue tree",
                                  TN_number(tn)));
    TN_MAP_Set(map,tn,(void*)TRUE);
  }
}

inline BOOL
Defines_Mapped_TN( TN_MAP map, OP* op )
//
//  Does <op> have a result that is mapped to TRUE in <map>?
//
{
  INT i;

  for ( i = OP_results(op) - 1; i >= 0; --i ) {
    if ( (BOOL)(INTPTR) TN_MAP_Get(map,OP_result(op,i)) ) return TRUE;
  }
  return FALSE;
}

static void
BB_Split_Exit_Glue( BB* bb )
//
//  Keep any OPs that read region TNs in <bb> first.  This should always be
//  save since these OPs were required to be first in the block on entry to
//  GRA and the intervening OPs must be loads inserted by GRA.  If any OP that
//  we move defines a complement TN, we'll rename that result to be a tmp and
//  then copy the tmp into the complement TN below the last glue copy.  The
//  only problem with this technique is that it relies upon being able to copy
//  the result of any OP that reads a region TN and writes a complement TN.
//  But I think that the SWP glue code maker always does a single operation
//  first whose result can then be copied.
//
{
  OP* op;
  OP* prev_op = (OP*) -1;   // Initialized to avoid bogus warning with ucode
  OPS glue_ops = OPS_EMPTY;
  OPS result_copy_ops = OPS_EMPTY;
  GRA_REGION* region = gbb_mgr.Get(BB_Unique_Predecessor(bb))->Region();
  TN_MAP map = TN_MAP_Create();

  for (op = BB_last_op(bb); op != NULL; op = prev_op ) {
    prev_op = OP_prev(op);

    if ( Uses_Region_TN(op,region) ) {
      INT i;
      BB_Remove_Op(bb,op);
      OPS_Prepend_Op(&glue_ops,op);
      Map_Operands(map,op);

      for ( i = OP_results(op) - 1; i >= 0; --i ) {
  TN *result = OP_result(op,i);
  if (   Complement_TN(result)
#ifdef TARG_IA64
            || TN_is_dedicated(result) && ! TN_is_zero(result )&& result != True_TN
#else
            || TN_is_dedicated(result) && ! TN_is_zero(result)
#endif
  ) {
          TN* tmp = Dup_TN_Even_If_Dedicated(result);

          Set_OP_result(op,i,tmp);
          Exp_COPY(result,tmp,&result_copy_ops);
  }
      }
    }
    else if ( Defines_Mapped_TN(map,op) ) {
      BB_Remove_Op(bb,op);
      OPS_Prepend_Op(&glue_ops,op);
      Map_Operands(map,op);
    }
  }

  CGSPILL_Prepend_Ops(bb,&result_copy_ops);
  CGSPILL_Prepend_Ops(bb,&glue_ops);
  TN_MAP_Delete(map);
}

static void
BB_Split_Entry_Glue( BB* bb )
//
//  Keep any OPs that write region TNs in <bb> last.  This should always be
//  safe since these OPs were required to be last in the block on entry to GRA
//  and so the intervening OPs must be spills inserted by GRA.  If any OP that
//  we move has a complement TN as an operand, we'll copy that TN to a local
//  TEMP just before the the first GLUE copy and rename the operand of the
//  glue copy.
//
{
  INT i, j;
  OP* op;
  OP* next_op = (OP*) -1;   // Avoid an incorrect warning with ucode
  OPS glue_ops = OPS_EMPTY;
  OPS operand_copy_ops = OPS_EMPTY;
  GRA_REGION* region = gbb_mgr.Get(BB_Unique_Successor(bb))->Region();

  for ( op = BB_first_op(bb); op != NULL; op = next_op ) {
    next_op = OP_next(op);
    for ( i = OP_results(op) - 1; i >= 0; --i ) {
      if ( Region_TN(OP_result(op,i),region) ) {
  BB_Remove_Op(bb,op);
  OPS_Append_Op(&glue_ops,op);

  // Check for operands which are complement TNs
  for ( i = OP_opnds(op) - 1; i >= 0; --i ) {
          TN* operand = OP_opnd(op,i);

          // If we find one, copy to a temp and rename
          // all references in op's operands.
          if (    Complement_TN(operand)
               || TN_is_dedicated(operand) && ! TN_is_zero(operand) && ! TN_is_true_pred(operand)
          ) {
            TN* tmp = Dup_TN_Even_If_Dedicated(operand);

            Exp_COPY(tmp,operand,&operand_copy_ops);

            for ( j = i ; j >= 0; --j ) {
              if ( OP_opnd(op,j) == operand )
                Set_OP_opnd(op,j,tmp);
            }
          }
  }
  break;
      }
    }
  }

  CGSPILL_Append_Ops(bb,&operand_copy_ops);
  CGSPILL_Append_Ops(bb,&glue_ops);
}

static void
Divide_Glue_Code(void)
//
//  Make sure all the references to region LRANGEs stay above any assignments
//  to complement LRANGEs in blocks that exit previously allocated regions.
//  Make sure all assignments to regions LRANGEs stay below any references to
//  complement LRANGEs.  This is required since we have allowed these
//  references to coexist in the same block.  But they really can interfere
//  and thus must be kept separated.  The solution is to copy all the region
//  TNs into TMPs at the top of region exit blocks and from temps at the
//  bottom of region entry blocks.  Then the original copy glue copy is
//  rewritten to use/assign the temp.
//
//  This also solves a second problem.  We potentially need to add loads above
//  region exit blocks and stores below region entry blocks.  But these may
//  contain complement references that use the same register as the glue
//  copies.  By dividing the glue code after these loads and stores have been
//  added, we'll span the loads and stores only with local TNs.
//
{
  BB_LIST* bb_list;

  for ( bb_list = region_exit_glue_bbs; bb_list != NULL;
                                        bb_list = BB_LIST_rest(bb_list)
  ) {
    BB* exit_glue_bb = BB_LIST_first(bb_list);

    BB_Split_Exit_Glue(exit_glue_bb);
  }

  for ( bb_list = region_entry_glue_bbs; bb_list != NULL;
                                         bb_list = BB_LIST_rest(bb_list)
  ) {
    BB* entry_glue_bb = BB_LIST_first(bb_list);

    BB_Split_Entry_Glue(entry_glue_bb);
  }
}

static void
Mark_Defreach_Out_Recur( LRANGE* lrange, GRA_BB* gbb )
//
//  Add <gbb> and any successors within <lrange> to the 1 set.
//
{
  GRA_BB_FLOW_NEIGHBOR_ITER iter;

  if ( ! gbb_mgr.One_Set_MemberP(gbb) ) {
    //
    // For homeable TNs, kill search if this block synchs the register
    // contents with the home location.
    //
    LUNIT* lunit;
    if (TN_is_gra_homeable(lrange->Tn()) &&
  lrange->Find_LUNIT_For_GBB(gbb, &lunit)) {
      if (lunit->Syncs_With_Home()) {
  return;
      }
    }

    gbb_mgr.One_Set_Union1(gbb);

    for (iter.Succs_Init(gbb); ! iter.Done(); iter.Step()) {
      GRA_BB* succ = iter.Current();

      if ( lrange->Contains_BB(succ) ) {
        Mark_Defreach_Out_Recur(lrange,succ);
      } else if ( succ->Spill_Above_Check(lrange) ) {
  //
  // if store moved here, want to mark it, but stop recursing
  // as we've exited the live range at this point and we only
  // want to mark block reachable by a def from within the live
  // range.
  //
  gbb_mgr.One_Set_Union1(succ);
      }
    }
  }
}



static void
Mark_Defreach_Out( LRANGE* lrange , SPILL_LIST *store_list)
//
//  Determine which block in <lrange> are reached by a definition.  Set the
//  Defreach property of any associated LUNITs.
//
{
  LRANGE_LUNIT_ITER iter;

  gbb_mgr.Clear_One_Set();

  //  DFS forward from blocks containing definitions, adding to 1 set.
  //
  for (iter.Init(lrange); ! iter.Done(); iter.Step()) {
    LUNIT* lunit = iter.Current();

    //
    // Ignore lunits whose definition originates from the home location.
    //
    if ( lunit->Has_Def() && !lunit->Def_From_Home() )
      Mark_Defreach_Out_Recur(lrange,lunit->Gbb());
  }

  //  Transfer property to appropriate Spill_List elements
  //
  for ( SPILL_LIST *sl = store_list;
       sl != NULL;
       sl = sl->Next()) {
    if ( gbb_mgr.One_Set_MemberP(sl->Get_Gbb())) {
      sl->Split_Defreach_Out_Set();
      if (sl->Lunit()) {
  // mark lunit too so its accessible when walking over the list of
  // all lunits (and not the spill list).
  sl->Lunit()->Split_Defreach_Out_Set();
      }
    }
  }
}


static BOOL
Local_Live_In( LUNIT* lunit )
//
//  Is the given <lunit> upward exposed in its block?  In order for this to be
//  so, it must be used above any definition in the block or spilled below the
//  block without being locally defined.  Notice the use of the Defreach_Out
//  property to optimize for removed spills.
//
{
  BB* bb = lunit->Gbb()->Bb();
  LRANGE* lrange = lunit->Lrange();
  TN* tn = lrange->Original_TN();

  return
    GTN_SET_MemberP(BB_live_use(bb),tn) ||
    (lunit->Split_Defreach_Out() &&
     lunit->Spill_Below() &&
     !lunit->Has_Def());
}

static void
Mark_Live_In_Recur( LRANGE* lrange, GRA_BB* gbb )
//
//  If <lrange> is live-in to <gbb>, add to the 1 set and visit all its
//  predecessors to propagate this property.
//
{
  GRA_BB_FLOW_NEIGHBOR_ITER iter;

  if (!gbb_mgr.One_Set_MemberP(gbb) &&
      (!GTN_SET_MemberP(BB_live_def(gbb->Bb()), lrange->Original_TN()) ||
  GTN_SET_MemberP(BB_live_use(gbb->Bb()), lrange->Original_TN()))) {
    gbb_mgr.One_Set_Union1(gbb);

    for (iter.Preds_Init(gbb); ! iter.Done(); iter.Step()) {
      GRA_BB* pred = iter.Current();

      if ( lrange->Contains_BB(pred) ||
    pred->Spill_Above_Check(lrange)) {
  //
  // must check spill above before checking for a restore
  // below as we want to recurse for a spill below, but we
  // won't if we have both a restore above and a spill below
  // in the same block (and we will get here via the restore
  // in that situation).
  //
        Mark_Live_In_Recur(lrange,pred);
      } else if ( pred->Restore_Below_Check(lrange) ) {
  //
  // want to indicate that restores moved out
  // are reached by uses below, but since they
  // are not in the live range, we do not continue
  // propagating the liveness upwards.
  //
  gbb_mgr.One_Set_Union1(pred);
      }
    }
  } else if ( gbb->Restore_Below_Check(lrange) ) {
    //
    // Case in which both spill above and restore below, but the
    // original TN was not live in to the block.  See comment above
    // about restores below.
    //
    gbb_mgr.One_Set_Union1(gbb);
  }
}

static void
Mark_Live_In( LRANGE* lrange, SPILL_LIST* load_list, SPILL_LIST* store_list )
//
//  Compute the "Live_In" property for each LUNIT in <lrange>.  Must be called
//  after Mark_Defreach_Out, because it relies on the "Defreach_Out" property
//  to determine whether a spill will actually happen.
//
{
  LRANGE_LUNIT_ITER iter;

  gbb_mgr.Clear_One_Set();

  // First set the GBB 1 set property for all the blocks with in LRANGE in
  // which <lrange> is actually live-in.
  //
  for (iter.Init(lrange); ! iter.Done(); iter.Step()) {
    LUNIT* lunit = iter.Current();

    if ( Local_Live_In(lunit) )
      Mark_Live_In_Recur(lrange,lunit->Gbb());
  }

  //
  // now, must consider those spill stores that were moved out of the
  // live range.
  //
  SPILL_LIST *sl;
  for (sl = store_list;  sl != NULL; sl = sl->Next()) {
    if (!sl->Lunit()) {
      Mark_Live_In_Recur(lrange, sl->Gbb());
    }
  }

  //  Now transfer the property to the spill list elements
  //
  for (sl = load_list;  sl != NULL; sl = sl->Next()) {
    if ( gbb_mgr.One_Set_MemberP(sl->Get_Gbb()) ) {
      sl->Split_Live_In_Set();
    }
    if (sl->Lunit()) {
      // mark lunit too so info is accessible if only walking list
      // of lunits.
      sl->Lunit()->Split_Live_In_Set();
    }
  }
}

static BOOL
Has_Successor_Not_In_LRANGE( GRA_BB* gbb, LRANGE* lrange,
           GRA_BB* exclude_succ = NULL)
//
//  Is there a successor of <gbb> which is not a member of <lrange>?
//
{
  GRA_BB_FLOW_NEIGHBOR_ITER iter;

  for (iter.Succs_Init(gbb); ! iter.Done(); iter.Step()) {
    GRA_BB* succ = iter.Current();

    if ( ! lrange->Contains_BB(succ) )
      return TRUE;

#ifdef KEY
    // If <lrange> is not live-in to <succ> and <succ> has OPs that can
    // clobber <lrange>'s register class, then the register can be unavailable
    // at the top of <succ>.
    if (succ->Clobbers_Reg_Class(lrange->Rc()) &&
  !succ->Is_Live_In_LRANGE(lrange)) {
      return TRUE;
    }

    if (GRA_optimize_boundary) {
      // If <succ> is a boundary BB where <lrange> is not live-in, then
      // <lrange>'s register could be used by another lrange at the beginning
      // of <succ>.  Without more info, consider <succ> to be a member of
      // another lrange.
      if (succ != exclude_succ) {
  LRANGE_BOUNDARY_BB *boundary_bb = lrange->Get_Boundary_Bb(succ->Bb());
  if (boundary_bb != NULL &&
      ! boundary_bb->Is_Live_In())
    return TRUE;
      }
    }
#endif
  }

  return FALSE;
}

#ifdef KEY
static BOOL
Reg_Used_Before_By_Other_TNs(LUNIT* lunit)
// Return TRUE if <lunit>'s register is used by other TNs between the start of
// the BB and the OP that uses <lunit>'s TN.
{
  OP *op;
  GRA_BB *gbb = lunit->Gbb();
  BB *bb = gbb->Bb();
  TN *tn = lunit->Lrange()->Tn();
  REGISTER reg = lunit->Lrange()->Reg();
  ISA_REGISTER_CLASS rc = TN_register_class(tn);

  for (op = BB_first_op(bb); op != NULL; op = OP_next(op)) {
#ifdef TARG_X8664
    // "Used" here means register is unavailable.  A register is unavailable if
    // it is clobbered.
    if ((rc == ISA_REGISTER_CLASS_x87 && OP_mmx(op)) ||
  (rc == ISA_REGISTER_CLASS_mmx && OP_x87(op)))
      return TRUE;
#endif

    // Check source operands.
    for (int i = OP_opnds(op) - 1; i >= 0; i--) {
      TN *opnd_tn = OP_opnd(op, i);
      // If this is <lunit>'s TN, then the register is not used by other TNs.
      if (opnd_tn == tn)
  return FALSE;
      LRANGE *lr = lrange_mgr.Get(opnd_tn);
      if (lr != NULL && lr->Allocated() && lr->Reg() == reg)
  return TRUE;
    }
    // Check result operands.
    for (int i = OP_results(op) - 1; i >= 0; i--) {
      TN *result_tn = OP_result(op, i);
      LRANGE *lr = lrange_mgr.Get(result_tn);
      if (lr != NULL && lr->Allocated() && lr->Reg() == reg)
  return TRUE;
    }
  }
  // <tn> does not appear in the BB, which means there is no OP that uses it.
  return FALSE;
}

static BOOL
Reg_Used_After_By_Other_TNs(LUNIT* lunit)
// Return TRUE if <lunit>'s register is used by other TNs between the OP that
// defines <lunit>'s TN and the end of the BB.
{
  OP *op;
  GRA_BB *gbb = lunit->Gbb();
  BB *bb = gbb->Bb();
  TN *tn = lunit->Lrange()->Tn();
  REGISTER reg = lunit->Lrange()->Reg();
  ISA_REGISTER_CLASS rc = TN_register_class(tn);

  for (op = BB_last_op(bb); op != NULL; op = OP_prev(op)) {
#ifdef TARG_X8664
    // "Used" here means register is unavailable.  A register is unavailable if
    // it is clobbered.
    if ((rc == ISA_REGISTER_CLASS_x87 && OP_mmx(op)) ||
  (rc == ISA_REGISTER_CLASS_mmx && OP_x87(op)))
      return TRUE;
#endif

    // Check result operands.
    for (int i = OP_results(op) - 1; i >= 0; i--) {
      TN *result_tn = OP_result(op, i);
      // If this is <lunit>'s TN, then the register is not used by other TNs.
      if (result_tn == tn)
  return FALSE;
      LRANGE *lr = lrange_mgr.Get(result_tn);
      if (lr != NULL && lr->Allocated() && lr->Reg() == reg)
  return TRUE;
    }
    // Check source operands.
    for (int i = OP_opnds(op) - 1; i >= 0; i--) {
      TN *opnd_tn = OP_opnd(op, i);
      LRANGE *lr = lrange_mgr.Get(opnd_tn);
      if (lr != NULL && lr->Allocated() && lr->Reg() == reg)
  return TRUE;
    }
  }
  // <tn> does not appear in the BB, which means there is no OP that defines
  // it.
  return FALSE;
}
#endif

static void
Move_Restore_Out_Of_Region( LUNIT* lunit )
// there should be a unique block acting as prolog
// to the region.  move the reload to the bottom of
// it
{
  GRA_BB *gbb_pred;
  GRA_BB *gbb = lunit->Gbb();
  BB *bb = BB_Unique_Predecessor(gbb->Bb());
  LRANGE* lrange = lunit->Lrange();
  
  DevAssert(bb != NULL,("Non-uniique region prolog.\n"));
  Is_True(BB_Unique_Successor(bb),
    ("Region prolog has multiple successors.\n"));
  gbb_pred = gbb_mgr.Get(bb);
  gbb_pred->Add_Live_Out_LRANGE(lrange);
  GRA_Trace_Place_LRANGE_GBB("load below",lrange,gbb_pred);
  gbb_pred->Restore_Below_Set(lrange);
  lunit->Gbb()->Add_Live_In_LRANGE(lrange);
  lunit->Restore_Above_Reset();
}

static BOOL
Move_Restore_Out_Of_LRANGE( LUNIT* lunit , SPILL_LIST** spill_list)
//
//  Decide whether we can and should move the reload of <lunit>'s LRANGE into
//  the bottom of the predecessor blocks that are not in the range.  Perform
//  the transformation if so.
//
//  The conditions for the transformation are:
//
//      1. There is a predecessor block in the LRANGE, and
//      2. All the predecessor blocks out of the LRANGE have one successor.
//
//  Condition 2 could be relaxed if we are willing to insert a new block as
//  the target of the predecessor.  Fred's feeling is that this will rarely be
//  worth it.  The limitation certainly simplifies things because we don't
//  have to worry about the placement of the new block.
//
//  The new block would be required because we will be moving the restore into
//  a live range that has been allocated the same register (if not we would
//  have included it in the split.)  On the other hand if the predecessor
//  has only one successor, then nothing allocated to the same register can
//  be live out of it anyway.
//
{
  BOOL do_move = FALSE;
  GRA_BB_FLOW_NEIGHBOR_ITER iter;
  LRANGE* lrange = lunit->Lrange();
  ISA_REGISTER_CLASS rc = lrange->Rc();
  REGISTER reg = lrange->Reg();
  BOOL callee_saves = REGISTER_SET_MemberP(REGISTER_CLASS_callee_saves(rc),reg);
  INT load_count = 0;

  if (!GRA_optimize_placement) {
    return FALSE;
  }

  // Check for suitability
  for (iter.Preds_Init(lunit->Gbb()); ! iter.Done(); iter.Step()) {
    GRA_BB* gbb = iter.Current();
    BB*     bb = gbb->Bb();

    if ( lrange->Contains_BB(gbb) ) {
      // Even though a pred is in our live range, we cannot trust it unless we
      // are live out of it or in a callee saves register.  Because a call at
      // the bottom of a block might trash.
      if (BB_call(bb) && ! gbb->Is_Live_Out_LRANGE(lrange) && ! callee_saves ) {
        return FALSE;
      }
#ifdef KEY
      // If <lrange> is not live-out from pred and pred has OPs that can
      // clobber <lrange>'s register class, then the register can be
      // unavailable at the bottom of pred.
      if (gbb->Clobbers_Reg_Class(rc) &&
    !gbb->Is_Live_Out_LRANGE(lrange)) {
  return FALSE;
      }

      if (GRA_optimize_boundary) {
  // If pred is a boundary BB, see if lrange is live-out of it.  If not,
  // the register might be used by another lrange.
  if (! lrange->Contains_Internal_BB(gbb)) {
    LRANGE_BOUNDARY_BB *boundary_bb = lrange->Get_Boundary_Bb(gbb->Bb());
    if (! boundary_bb->Is_Live_Out())
      return FALSE;
        }
      }
#endif
      do_move = TRUE;
    } else {
      // Small possible optimization -- check for callee saves.
      GRA_BB *exclude_succ = NULL;
#ifdef KEY
      if (GRA_optimize_boundary ||
    lunit->Gbb()->Clobbers_Reg_Class(rc)) {
  // When checking for succ not in lrange, don't check if the succ is the
  // current BB.  Reg_Used_Before_By_Other_TNs will decide if the
  // register is available in the current BB.
        exclude_succ = lunit->Gbb();
      }
#endif
      if (Has_Successor_Not_In_LRANGE(gbb,lrange,exclude_succ) || BB_call(bb))
  return FALSE;
      else if (BB_rid(bb) != BB_rid(lunit->Gbb()->Bb()))
  return FALSE;

      load_count++;
    }
  }

  if ( do_move == FALSE )
    return FALSE;

  if (load_count > 0 && OPT_Space) {
    // Don't increase spill count under opt space
    return FALSE;
  }

#ifdef KEY
  if (GRA_optimize_boundary ||
      lunit->Gbb()->Clobbers_Reg_Class(rc)) {
    // "Restore above" means to restore just before the first use of the TN in
    // the BB.  We can move the restore to a pred BB only if the register is
    // not used by other TNs between the start of the BB and the first use of
    // this TN.
    if (Reg_Used_Before_By_Other_TNs(lunit))
      return FALSE;
  }
#endif

  GRA_Trace_Place_LRANGE_GBB("moving load out",lrange,lunit->Gbb());

  // Move to predecessor out of the live range
  for (iter.Preds_Init(lunit->Gbb()); ! iter.Done(); iter.Step()) {
    GRA_BB* gbb = iter.Current();

    // Now live out of all predecessors:
    gbb->Add_Live_Out_LRANGE(lrange);

    if ( !lrange->Contains_BB(gbb) ) {
      GRA_Trace_Place_LRANGE_GBB("load below",lrange,gbb);
      gbb->Restore_Below_Set(lrange);
      SPILL_LIST *sl = SPILL_LIST_Create_Gbb(gbb,&MEM_local_nz_pool);
      *spill_list = (*spill_list)->Push(sl);
    }

  }

  // Fix up the block itself
  lunit->Gbb()->Add_Live_In_LRANGE(lrange);
  lunit->Restore_Above_Reset();
  return TRUE;
}

static BOOL
No_Successor_Has_Restore( SPILL_LIST *sl, LRANGE *lrange )
//
//  TRUE if for every successor s of <sl>
//
//      1.  s is in <lrange>, and
//      2.  there is no restore of LRANGE at the top of s
//
{
  GRA_BB_FLOW_NEIGHBOR_ITER iter;
  LUNIT *lunit = sl->Lunit();
  GRA_BB *curgbb = sl->Gbb();

  if ( lunit && lunit->Spill_Below_Sticks() ) {
    return FALSE;
  }
   
  //
  // can't remove spill above if there is a restore below, or
  // if the original tn is upwardly exposed in the block. since
  // we're spilling above, this block isn't in our live range (in
  // fact, it'll be on the border one of the other splits),
  // so an upwardly exposed use of the tn will necessitate a
  // load at the top of the block for the other live range.  this
  // is true regardless of whether or not the other live range is
  // spilled or not.
  //
  if (curgbb &&
      (curgbb->Restore_Below_Check(lrange) ||
       GTN_SET_MemberP(BB_live_use(curgbb->Bb()),
           lrange->Original_TN()))) {
    return FALSE;
  }

  for (iter.Succs_Init(sl->Get_Gbb()); ! iter.Done(); iter.Step()) {
    GRA_BB* gbb = iter.Current();

    if ( gbb_mgr.One_Set_MemberP(gbb) )
      return FALSE;
    else if ( ! lrange->Contains_BB(gbb) )
      return FALSE;
  }

  return TRUE;
}

static BOOL
Needs_Spill( LRANGE* lrange, GRA_BB* gbb )
//
//  Is a spill of <lrange> required on behalf of the given <gbb> which is the
//  direct successor of some block in <lrange>.
//
{
  LUNIT* lunit;

  if ( ! lrange->Contains_BB(gbb) )
    return TRUE;
  else if (    lrange->Find_LUNIT_For_GBB(gbb,&lunit)
            && lunit->Restore_Above()
  ) {
    return TRUE;
  }
  else
    return FALSE;
}

static BOOL
Has_Predecessor_Not_In_LRANGE( GRA_BB *gbb, LRANGE* lrange,
             GRA_BB *exclude_pred = NULL)
//
//  Is there a predecessor of <gbb> which is not a member of <lrange>?
//
{
  GRA_BB_FLOW_NEIGHBOR_ITER iter;
  REGISTER reg = lrange->Reg();
  ISA_REGISTER_CLASS rc = lrange->Rc();
  BOOL not_call_saved =
    ! REGISTER_SET_MemberP(REGISTER_CLASS_callee_saves(rc),reg);

  for (iter.Preds_Init(gbb); ! iter.Done(); iter.Step()) {
    GRA_BB* pred = iter.Current();

    if ( ! lrange->Contains_BB(pred) )
      return TRUE;
    if ( BB_call(pred->Bb()) && not_call_saved )
      return TRUE;
#ifdef KEY
    // If <lrange> is not live-out from <pred> and <pred> has OPs that can
    // clobber <lrange>'s register class, then the register can be unavailable
    // at the bottom of <pred>.
    if (pred->Clobbers_Reg_Class(lrange->Rc()) &&
  !pred->Is_Live_Out_LRANGE(lrange)) {
      return TRUE;
    }
    if (GRA_optimize_boundary) {
      // If <pred> is a boundary BB where <lrange> is not live-out, then
      // <lrange>'s register could be used by another lrange at the end of
      // <pred>.  Without more info, consider <pred> to be a member of another
      // lrange.
      if (pred != exclude_pred) {
  LRANGE_BOUNDARY_BB *boundary_bb = lrange->Get_Boundary_Bb(pred->Bb());
  if (boundary_bb != NULL &&
      ! boundary_bb->Is_Live_Out())
    return TRUE;
      }
    }
#endif
  }

  return FALSE;
}

static void
Add_To_Predecessor_Live_Out( GRA_BB* gbb, LRANGE* lrange )
//
//  Add <lrange> to the live-out's of all of <gbb>'s predecessors.
//
{
  GRA_BB_FLOW_NEIGHBOR_ITER iter;

  for (iter.Preds_Init(gbb); ! iter.Done(); iter.Step()) {
    GRA_BB* pred = iter.Current();

    pred->Add_Live_Out_LRANGE(lrange);
  }
}

static BOOL
Move_Spill_Out_Of_LRANGE( LUNIT* lunit , SPILL_LIST** spill_list)
//
//  Decide whether we can and should move the spill of <lunit>'s LRANGE into
//  the top of the successor blocks that are not in the range.  Perform
//  the transformation if so.
//
//  The conditions for the transformation are:
//
//      1. There is a successor block in the LRANGE, and
//      2. All the immediate predecessors of each successor
//         block outside the LRANGE are in <lunit>'s LRANGE.
//      3. <lunit> isn't marked as a sticky spill below.  This might happen
//         because it was created to move a store above a previously
//         allocated region.
//
//  For a discussion of condition 2, see Move_Restore_Out_Of_LRANGE.
//
{
  BOOL has_successor_not_needing_spill = FALSE;
  GRA_BB_FLOW_NEIGHBOR_ITER iter;
  LRANGE* lrange = lunit->Lrange();
  INT spill_count = 0;

  if (!GRA_optimize_placement) {
    return FALSE;
  }

  // Check for suitability

  if ( lunit->Spill_Below_Sticks() )
    return FALSE;

  for (iter.Succs_Init(lunit->Gbb()); ! iter.Done(); iter.Step()) {
    GRA_BB* gbb = iter.Current();

    GRA_BB *exclude_pred = NULL;
#ifdef KEY
    if (GRA_optimize_boundary ||
        lunit->Gbb()->Clobbers_Reg_Class(lrange->Rc())) {
      // When checking for pred not in lrange, don't check if the pred is the
      // current BB.  Reg_Used_After_By_Other_TNs will decide if the register
      // is available in the current BB.
      exclude_pred = lunit->Gbb();
    }
#endif

    if ( ! Needs_Spill(lrange,gbb) )
      has_successor_not_needing_spill = TRUE;
    else if ( Has_Predecessor_Not_In_LRANGE(gbb,lrange,exclude_pred) )
      return FALSE;
    else if ( BB_rid(gbb->Bb()) != BB_rid(lunit->Gbb()->Bb()))
      return FALSE;
    
    spill_count++;
  }

  if ( ! has_successor_not_needing_spill )
    return FALSE;

  if (spill_count > 1 && OPT_Space) {
    //
    // Don't increase spill count under OPT_Space.
    //
    return FALSE;
  }

#ifdef KEY
  if (GRA_optimize_boundary ||
      lunit->Gbb()->Clobbers_Reg_Class(lrange->Rc())) {
    // "Spill below" means to spill just after the last define of the TN in the
    // BB.  We can move the spill to a succ BB only if the register is not used
    // by other TNs between the last define of the TN and the end of the BB.
    if (Reg_Used_After_By_Other_TNs(lunit))
      return FALSE;
  }
#endif

  GRA_Trace_Place_LRANGE_GBB("moving store out",lrange,lunit->Gbb());

  // Move to successor out of the live range BBs
  for (iter.Succs_Init(lunit->Gbb()); ! iter.Done(); iter.Step()) {
    GRA_BB* gbb = iter.Current();

    if ( Needs_Spill(lrange,gbb) ) {
      GRA_Trace_Place_LRANGE_GBB("store above",lrange,gbb);
      gbb->Spill_Above_Set(lrange);
      gbb->Add_Live_In_LRANGE(lrange);
      Add_To_Predecessor_Live_Out(gbb,lrange);
      SPILL_LIST *sl = SPILL_LIST_Create_Gbb(gbb,&MEM_local_nz_pool);
      *spill_list = (*spill_list)->Push(sl);
    }
  }

  // Fix up the block itself
  lunit->Spill_Below_Reset();
  return TRUE;
}

static GRA_BB*
Region_Pre_Header( GRA_BB* gbb )
//
//  <gbb> is a block not in the complement region.  It is supposed to have a
//  unique entry block, which I think could be the first block in order above
//  the region.  Find this block and return it.
//  
{
  RID* rid = gbb->Region()->Rid();
  BB *bb;
  GRA_BB *result = NULL;

  if (rid != NULL) { 
    if (RID_type(rid) != RID_TYPE_swp) {
      bb = CGRIN_entry(RID_cginfo(rid));
      bb = BB_Unique_Predecessor(bb);
      if (bb != NULL) {
  result = gbb_mgr.Get(bb);
      }
    } else {
      //
      // swp regions don't have cginfo, so have to search
      //
      bb = gbb->Bb();
      do {
  bb = BB_prev(bb);
  DevAssert(bb != NULL,("Couldn't find region pre header for BB%d",
            BB_id(gbb->Bb())));
      }
      while (BB_rid(bb) == rid);

      result = gbb_mgr.Get(bb);
    }
    if (result && !result->Region_Is_Complement()) {
      result = NULL;
    }
  }

  return result;
}

static BOOL
Move_Spill_Code_Above_Region( LUNIT* lunit, BOOL move_restore,
           SPILL_LIST** spill_list )
//
//  we can't spill in regions due to the possibility of the
//  spill code requiring different registers (and lra won't
//  touch the code again, nor will other phases), so always
//  move spill code to the preheader if it winds up in the body
//  of the region.  it should mostly only end up in the entry
//  or exit blocks as a side effect of the placement of prolog
//  and epilog blocks (when they're shared, they sometimes force
//  live range splitting to put the entry/exit blocks on the border,
//  thus adding spill code to the region rather than the prolog/epilog).
//  in any case, we'll handle the spill code wherever it was added
//  as a safety feature.
//
{
  LUNIT  *ph_lunit;
  LRANGE *lrange = lunit->Lrange();
  GRA_BB *gbb    = lunit->Gbb();
  BB     *bb     = gbb->Bb();
  GRA_BB *ph_gbb = Region_Pre_Header(gbb);

  // no preheader.  must spill in region
  if (ph_gbb == NULL) {
    return FALSE;
  }

  GRA_Trace_Place_LRANGE_GBB("store below preheader of region",
                             lrange,ph_gbb);

  //
  // stores below are handled via lunits.  restores below are only
  // done via gbb's (typically they only occur if moving a restore
  // out of an lrange).  technically, the preheader should be part
  // of the lrange and thus there probably should be an lunit for
  // the load below, but it doesn't provide any real information 
  // at this point, so we'll just use the gbb restore below mechanism.
  //
  if (move_restore) {
    ph_gbb->Add_Live_Out_LRANGE(lrange);
    GRA_Trace_Place_LRANGE_GBB("load below",lrange,ph_gbb);
    ph_gbb->Restore_Below_Set(lrange);
    lunit->Gbb()->Add_Live_In_LRANGE(lrange);
    lunit->Restore_Above_Reset();

    // keep track of list of spill/reload sites.  this one isn't removable
    SPILL_LIST *ph_sl = SPILL_LIST_Create_Gbb(ph_gbb,&MEM_local_nz_pool);
    ph_sl->Load_Below_Sticks_Set();
    *spill_list = (*spill_list)->Push(ph_sl);
  } else {
    if ( ! lrange->Find_LUNIT_For_GBB(ph_gbb,&ph_lunit) )
      ph_lunit = LUNIT_Create(lrange,ph_gbb);

    // dunno why this is here.  the only possible thing i can see it doing
    // is ensuring that the spill is not removed (the flag gets used during
    // spill removal to indicate an interior load).  now, with things
    // reorganized, we can't set the flag this way (due to the live range
    // analysis code in between the spill movement and removal).  i don't
    // think this is useful anyway, since the "spill sticks" business should
    // ensure the retention of the store.  comment it out for now, and we'll
    // address it if it turns out to do something that i can't fathom.
    //
    // gbb_mgr.One_Set_Union1(lunit->Gbb());

    ph_lunit->Spill_Below_Set();
    Possibly_List_LUNIT(ph_lunit);
    ph_lunit->Spill_Below_Sticks_Set();
    lunit->Spill_Below_Reset();

    // keep track of list of spill/reload sites
    SPILL_LIST *ph_sl = SPILL_LIST_Create_Lunit(ph_lunit,&MEM_local_nz_pool);
    *spill_list = (*spill_list)->Push(ph_sl);
  }
  return TRUE;
}
  
static void
Check_Split_Borders(LRANGE *lr)
//
// check for legal spilling at a split live ranges
// border
//
{
}
    

static void
Optimize_Placement(void)
//
//  As per Fred Chow's algorithm:
//
//      1.  Identify restores that have predecessors BBs in the same live
//          range.  Move these into all the direct predecessor blocks NOT in
//          the LRANGE.
//
//      2.  Identify any spills with no successor blocks that have restores.
//          These no longer need to spill (because of 1).
//
//      3.  Identify spills that have successor BBs in the same live range.
//          Move these into all the direct successor blocks NOT in the
//          LRANGE.
//
//  Also, an easy and very important extension: delete spills that are not
//  reached by a definition in the LRANGE and loads that do not reach a use
//  (or a non-deleted spill).
//
//  The result of this function that each GRA_BB contains four lists:
//
//      LRANGEs to spill above
//      LUNITs to load above
//      LUNITs to spill below
//      LRANGEs to load below
//
//  There is now room for three further optimizations:
//
//      1.  Identify spill-loads of same register and replace the load with a
//          register transfer.
//      2.  Live analysis of spill locations allows us to remove dead spills
//      3.  Live analysis of spill locations allows us to color spill
//          locations
//
{
  LRANGE_SPLIT_LIST_ITER sl_iter;
  LRANGE_LUNIT_ITER iter;


  for (sl_iter.Init(split_lranges_head); ! sl_iter.Done(); sl_iter.Step()) {
    LRANGE* split_lrange = sl_iter.Current();
    BOOL    moved_reload = FALSE;
    SPILL_LIST* store_list_head = NULL;
    SPILL_LIST* load_list_head = NULL;

    if ( ! split_lrange->Spilled() ) {
      GRA_Trace_Place(0,"Placing spills/restores for TN%d...",
                        TN_number(split_lrange->Tn()));

      MEM_POOL_Push(&MEM_local_nz_pool);

      //
      // move spills/restores out of lranges.  continue until no
      // moves possible since moving a spill may enable moving
      // a restore and vice versa.
      //
      BOOL change;
      do {
  change = FALSE;
        for (iter.Init(split_lrange); ! iter.Done(); iter.Step()) {
    LUNIT* lunit = iter.Current();
    
    if ( lunit->Restore_Above() ) {
      if (lunit->Gbb()->Is_Region_Block(TRUE)) {
        //
        // if region entry, then move to its prolog block.
        // this must happen before any attempt to move the
        // restore.
        //
        Move_Spill_Code_Above_Region( lunit, TRUE, &load_list_head);
      } else if ( Move_Restore_Out_Of_LRANGE(lunit, &load_list_head) ) {
        moved_reload = TRUE;
        change = TRUE;
      } else {
        SPILL_LIST *sl =
    SPILL_LIST_Create_Lunit(lunit,&MEM_local_nz_pool);
        load_list_head = load_list_head->Push(sl);
      }
    }
    if ( lunit->Spill_Below() ) {
      if (lunit->Gbb()->Is_Region_Block(TRUE)) {
        // this must happen before any attempt to move the
        // store.
        if (!Move_Spill_Code_Above_Region(lunit,FALSE,&store_list_head)){
    GRA_Trace_Place_LRANGE_GBB("must store in region",split_lrange,
             lunit->Gbb());
    Possibly_List_LUNIT(lunit);
        }
      }
      else if ( ! Move_Spill_Out_Of_LRANGE(lunit, &store_list_head) ) {
        Is_True(lunit->Gbb()->Region_Is_Complement(),
          ("Trying to move spill out of region in wrong place.\n"));
        SPILL_LIST *sl = SPILL_LIST_Create_Lunit(lunit,
                   &MEM_local_nz_pool);
        store_list_head = store_list_head->Push(sl);
      } else {
        change = TRUE;
      }
    }
  }
      } while (change);

      //
      // perform minimal data flow analysis to determine what
      // loads and stores are still needed (we don't do a global
      // update of liveness after splitting).
      //
      Mark_Defreach_Out(split_lrange, store_list_head);
      Mark_Live_In(split_lrange, load_list_head, store_list_head);

      gbb_mgr.Clear_One_Set();

      //
      // remove unnecessary loads.
      //
      SPILL_LIST *sl;
      for (sl = load_list_head;
     sl != NULL;
     sl = sl->Next()) {
  GRA_BB *gbb = sl->Get_Gbb();
  LUNIT *lunit = sl->Lunit();

  if (!sl->Split_Live_In() &&
      !sl->Load_Below_Sticks() &&
      GRA_remove_spills) {
    GRA_Trace_Place_LRANGE_GBB("load unnecessary - no reaching use",
             split_lrange, gbb);
    if (lunit) {
      lunit->Restore_Above_Reset();
    } else {
      gbb->Restore_Below_Reset(split_lrange);
    }
  } else {
    GRA_Trace_Place_LRANGE_GBB("must load",split_lrange,gbb);
               
    // Mark is so that we can know later on whether an interior spill
    // is required:
    gbb_mgr.One_Set_Union1(gbb);
    if (lunit) {
            Possibly_List_LUNIT(lunit);
          }
        }
      }

      //
      // remove unnecessary stores
      //
      for (sl = store_list_head;
     sl != NULL;
     sl = sl->Next()) {
  GRA_BB *gbb = sl->Get_Gbb();
  LUNIT *lunit = sl->Lunit();

  if (!sl->Split_Defreach_Out() && GRA_remove_spills) {
    //
    // not reached by any definition in the live range, so no
    // need to place it in memory along this path.
    //
    GRA_Trace_Place_LRANGE_GBB("store unnecessary -- no reaching def",
             split_lrange, gbb);
    if (lunit) {
            lunit->Spill_Below_Reset();
    } else {
      gbb->Spill_Above_Reset(split_lrange);
          }

  } else if ( moved_reload && GRA_remove_spills &&
#ifdef KEY
       // No_Successor_Has_Restore assumes gbb is inside lrange.
       // It tests if all of gbb's succs are also inside lrange and
       // without restores.  If so, the spill in gbb is not needed.
       // If gbb is outside lrange, then the spill in gbb is always
       // needed.  Bug 6835.
       split_lrange->Contains_BB(gbb) &&
#endif
       No_Successor_Has_Restore(sl, split_lrange)) {
    //
    // no reload along path from this block, so no need to store
    //
    GRA_Trace_Place_LRANGE_GBB("store unnecessary -- no successor "
             "with restore",
             split_lrange, gbb);
    if (lunit) {
      lunit->Spill_Below_Reset();
    } else {
      gbb->Spill_Above_Reset(split_lrange);
          }

        } else {
    GRA_Trace_Place_LRANGE_GBB("must store",split_lrange,
             sl->Get_Gbb());
    if (lunit) {
      Possibly_List_LUNIT(lunit);
          }
  }
      }
      MEM_POOL_Pop(&MEM_local_nz_pool);
      if (GRA_Trace_Check_Splits()) {
  // do fairly time consuming check of borders to see
  // if we've gone a little wacky with our spill optimizations
  Check_Split_Borders(split_lrange);
      }
    }
  }
}

static void
Dumb_Placement(void)
//
// A dumb version that leaves the spills/restores just where splitting left
// them.  For debugging.
//
{
  LRANGE_SPLIT_LIST_ITER sl_iter;
  LRANGE_LUNIT_ITER iter;

  for (sl_iter.Init(split_lranges_head); ! sl_iter.Done(); sl_iter.Step()) {
    LRANGE* split_lrange = sl_iter.Current();

    if ( ! split_lrange->Spilled() ) {
      GRA_Trace_Place(0,"Placing spills/restores dumbly for TN%d...",
                        TN_number(split_lrange->Tn()));

      for (iter.Init(split_lrange); ! iter.Done(); iter.Step()) {
        LUNIT* lunit = iter.Current();

        if ( lunit->Restore_Above() ) {
          GRA_Trace_Place_LRANGE_GBB("must load",split_lrange,
                                                 lunit->Gbb());
          Possibly_List_LUNIT(lunit);
        }
      }

      for (iter.Init(split_lrange); ! iter.Done(); iter.Step()) {
        LUNIT* lunit = iter.Current();

        if ( lunit->Spill_Below() ) {
          GRA_Trace_Place_LRANGE_GBB("must store",split_lrange,
                                                  lunit->Gbb());
          Possibly_List_LUNIT(lunit);
        }
      }
    }
  }
}

static void
Gen_Restores_Above_And_Spills_Below(void)
//
//  Restore above / spill below LUNITs with either restores above or spills
//  below their blocks.and whose LRANGEs are not spilled.  Localize the TN
//  involved when we have to do both.
//
{
  LUNIT_SPILL_LIST_ITER iter;

  for (iter.Init(lunits_with_spills_head); ! iter.Done(); iter.Step()) {
    LUNIT* lunit = iter.Current();

    GRA_Trace_Split_LUNIT_Spill(lunit);

    if ( ! (lunit->Live_In() || lunit->Live_Out()) )
      LUNIT_Spill(lunit);
    else {
      if ( lunit->Restore_Above() )
        LRANGE_Restore_Above(lunit->Lrange(),lunit->Gbb());

      if ( lunit->Spill_Below() )
        LRANGE_Spill_Below(lunit->Lrange(),lunit->Gbb());
    }
  }
}

static void
Gen_Spills_Above_And_Restores_Below(void)
//
//  Generate the outer layer of spills above and restores below.
//
{
  BB* bb;

  for ( bb = REGION_First_BB; bb != NULL; bb = BB_next(bb) ) {
    GRA_BB* gbb = gbb_mgr.Get(bb);
    ISA_REGISTER_CLASS rc;

    lrange_mgr.Clear_One_Set();

    FOR_ALL_ISA_REGISTER_CLASS( rc ) {
      if (gbb->Spill_Above(rc)) {
  LRANGE_SUBUNIVERSE *su = gbb->Region()->Subuniverse(rc);
  LRANGE* lrange;
  for (lrange = LRANGE_SET_ChooseS(gbb->Spill_Above(rc), su);
       lrange != LRANGE_SET_CHOOSE_FAILURE;
       lrange = LRANGE_SET_Choose_NextS(gbb->Spill_Above(rc),
                lrange, su)) {
    if ( ! lrange_mgr.One_Set_MemberP(lrange) ) {
      LRANGE_Spill_Above(lrange,gbb);
      lrange_mgr.One_Set_Union1(lrange);
    }
  }
      }
    }

    lrange_mgr.Clear_One_Set();

    FOR_ALL_ISA_REGISTER_CLASS( rc ) {
      if (gbb->Restore_Below(rc)) {
  LRANGE_SUBUNIVERSE *su = gbb->Region()->Subuniverse(rc);
  LRANGE* lrange;
  for (lrange = LRANGE_SET_ChooseS(gbb->Restore_Below(rc), su);
       lrange != LRANGE_SET_CHOOSE_FAILURE;
       lrange=LRANGE_SET_Choose_NextS(gbb->Restore_Below(rc),
             lrange, su)){
    if ( ! lrange_mgr.One_Set_MemberP(lrange) ) {
      LRANGE_Restore_Below(lrange,gbb);
      lrange_mgr.One_Set_Union1(lrange);
    }
  }
      }
    }
  }
}

// Actually add the spills.
void
GRA_Spill(void)
{
  LRANGE_LIST *l;
  ISA_REGISTER_CLASS           rc;
  GRA_REGION_RC_NL_LRANGE_ITER iter;
  LUNIT_SPILL_LIST_ITER        lu_iter;
  GRA_REGION *region = gra_region_mgr.Complement_Region();

  GRA_Init_Trace_Memory();

  spill_count = restore_count = 0;
  freq_spill_count = freq_restore_count = 0.0F;

  Identify_Initialize_Glue_Blocks();

#ifdef TARG_IA64
  UNAT_Spill_Initialize();
#endif

  // Spill all the LUNITs with actual references in every live range with a
  // spill
  for ( l = spilled_lranges; l != NULL; l = LRANGE_LIST_rest(l) )
    LRANGE_Spill(LRANGE_LIST_first(l));

  // Collect the LRANGEs containing LUNITs with split spills or restores.
  //  Reinitialize the lunit_with_spills_listed set represented as a list and
  //  a LUNIT flag.
  //
  for (lu_iter.Init(lunits_with_spills_head); ! lu_iter.Done(); lu_iter.Step()){
    LUNIT* lunit = lu_iter.Current();

    lunit->Spill_Listed_Reset();
    Possibly_List_LRANGE(lunit->Lrange());
  }

  lunits_with_spills_head = NULL;

  Optimize_Placement();

  Gen_Restores_Above_And_Spills_Below();
  Divide_Glue_Code();
  Gen_Spills_Above_And_Restores_Below();

  // Make sure any spills (which always use the original TN for their spill
  // ST), find their way to any duplicates we create.
  FOR_ALL_ISA_REGISTER_CLASS( rc ) {
    for (iter.Init(region,rc); ! iter.Done(); iter.Step()) {
      LRANGE* lrange = iter.Current();

      Set_TN_spill(lrange->Tn(), TN_spill(lrange->Original_TN()));
    }
  }

  GRA_Trace_Spill_Stats(freq_restore_count,restore_count,freq_spill_count,
      spill_count, priority_count);
  GRA_Trace_Memory("GRA_Spill()");
}

// A restore of the given <lunit> is required at the top of its block.
void
GRA_Note_Restore_Above( LUNIT *lunit )
{
  LRANGE* lrange = lunit->Lrange();

  lunit->Restore_Above_Set();
  Possibly_List_LUNIT(lunit);
}

// A spill of the given <lunit> is required at the end of its block.
void
GRA_Note_Save_Below( LUNIT *lunit )
{
  lunit->Spill_Below_Set();
  Possibly_List_LUNIT(lunit);
}

// Use spills and restores to completely localize <lrange>, making it
// the LRA's problem.
void
GRA_Note_Spill( LRANGE* lrange )
{
  GRA_Trace_Color_LRANGE("Spilling",lrange);
  if ( lrange->Type() == LRANGE_TYPE_COMPLEMENT ) {
    spilled_lranges = LRANGE_LIST_Push(lrange,spilled_lranges,GRA_pool);
    lrange->Spilled_Set();
  }
  else {
    DevAssert(lrange->Type() == LRANGE_TYPE_LOCAL &&
        !lrange->Has_Wired_Register(),
              ("Spilling a LRANGE of unexpected type"));
  }
}

// Called at the start of GRA.
void
GRA_Spill_Initialize(void)
{
  spilled_lranges = NULL;
  split_lranges_head = NULL;
  lunits_with_spills_head = NULL;
}

// The save and restore of the predicate registers (needed just for the
// callee-saved ones) are always generated.  If we end up not using any
// of them, the save and restore are to be removed for performance reason.
// The integer TN involved needs to be fixed up so that GRA will not
// work on them.
void
GRA_Remove_Predicates_Save_Restore(void)
{
  BB_LIST *elist;
  BB *bb;
  OP* op;
  BOOL found = FALSE;
  // at the entry blocks
  for (elist = Entry_BB_Head; elist; elist = BB_LIST_rest(elist)) {
    found = FALSE;
    bb = BB_LIST_first(elist);
    for (op = BB_first_op(bb); op; op = OP_next(op)) {
      if (OP_save_predicates(op)) {
        TN *save_tn = OP_result(op,0);
  BB_Remove_Op(bb, op);
  found = TRUE;
        if (TN_is_global_reg(save_tn)) {
    LRANGE *lr = lrange_mgr.Get(save_tn);
    lr->No_Appearance_Set(); // mark it so it won't be assigned reg later
        }
  break;
      }
    }
// entry code is not generated for handler entry on IA64, in Generated_Entry()
#if !defined(TARG_IA64)
    Is_True(found || Exit_BB_Head == NULL, 
      ("cannot find predicate register save at entry.\n"));
#endif
    // if PU has no exit, dead store elimination earlier has removed it already
  }

  // at the exit blocks
  for (elist = Exit_BB_Head; elist; elist = BB_LIST_rest(elist)) {
    found = FALSE;
    bb = BB_LIST_first(elist);
    for (op = BB_last_op(bb); op; op = OP_prev(op)) {
      if (OP_restore_predicates(op)) {
  BB_Remove_Op(bb, op);
  found = TRUE;
  break;
      }
    }
// entry code is not generated for handler entry on IA64, in Generated_Entry()
#if !defined(TARG_IA64)
    Is_True(found, ("cannot find predicate register restore at exit.\n"));
#endif
  }
}

---