Subversion Repositories openrisc

/* Rewrite a program in Normal form into SSA.

   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010

   Free Software Foundation, Inc.

   Contributed by Diego Novillo <dnovillo@redhat.com>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; either version 3, or (at your option)

any later version.

GCC 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 for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "flags.h"

#include "rtl.h"

#include "tm_p.h"

#include "langhooks.h"

#include "hard-reg-set.h"

#include "basic-block.h"

#include "output.h"

#include "expr.h"

#include "function.h"

#include "diagnostic.h"

#include "bitmap.h"

#include "tree-flow.h"

#include "gimple.h"

#include "tree-inline.h"

#include "varray.h"

#include "timevar.h"

#include "hashtab.h"

#include "tree-dump.h"

#include "tree-pass.h"

#include "cfgloop.h"

#include "domwalk.h"

#include "ggc.h"

#include "params.h"

#include "vecprim.h"

/* This file builds the SSA form for a function as described in:

   R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently

   Computing Static Single Assignment Form and the Control Dependence

   Graph. ACM Transactions on Programming Languages and Systems,

   13(4):451-490, October 1991.  */

/* Structure to map a variable VAR to the set of blocks that contain

   definitions for VAR.  */

struct def_blocks_d

{

  /* The variable.  */

  tree var;

  /* Blocks that contain definitions of VAR.  Bit I will be set if the

     Ith block contains a definition of VAR.  */

  bitmap def_blocks;

  /* Blocks that contain a PHI node for VAR.  */

  bitmap phi_blocks;

  /* Blocks where VAR is live-on-entry.  Similar semantics as

     DEF_BLOCKS.  */

  bitmap livein_blocks;

};

/* Each entry in DEF_BLOCKS contains an element of type STRUCT

   DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the

   basic blocks where VAR is defined (assigned a new value).  It also

   contains a bitmap of all the blocks where VAR is live-on-entry

   (i.e., there is a use of VAR in block B without a preceding

   definition in B).  The live-on-entry information is used when

   computing PHI pruning heuristics.  */

static htab_t def_blocks;

/* Stack of trees used to restore the global currdefs to its original

   state after completing rewriting of a block and its dominator

   children.  Its elements have the following properties:

   - An SSA_NAME (N) indicates that the current definition of the

     underlying variable should be set to the given SSA_NAME.  If the

     symbol associated with the SSA_NAME is not a GIMPLE register, the

     next slot in the stack must be a _DECL node (SYM).  In this case,

     the name N in the previous slot is the current reaching

     definition for SYM.

   - A _DECL node indicates that the underlying variable has no

     current definition.

   - A NULL node at the top entry is used to mark the last slot

     associated with the current block.  */

static VEC(tree,heap) *block_defs_stack;

/* Set of existing SSA names being replaced by update_ssa.  */

static sbitmap old_ssa_names;

/* Set of new SSA names being added by update_ssa.  Note that both

   NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of

   the operations done on them are presence tests.  */

static sbitmap new_ssa_names;

sbitmap interesting_blocks;

/* Set of SSA names that have been marked to be released after they

   were registered in the replacement table.  They will be finally

   released after we finish updating the SSA web.  */

static bitmap names_to_release;

static VEC(gimple_vec, heap) *phis_to_rewrite;

/* The bitmap of non-NULL elements of PHIS_TO_REWRITE.  */

static bitmap blocks_with_phis_to_rewrite;

/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES.  These sets need

   to grow as the callers to register_new_name_mapping will typically

   create new names on the fly.  FIXME.  Currently set to 1/3 to avoid

   frequent reallocations but still need to find a reasonable growth

   strategy.  */

#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))

/* Tuple used to represent replacement mappings.  */

struct repl_map_d

{

  tree name;

  bitmap set;

};

/* NEW -> OLD_SET replacement table.  If we are replacing several

   existing SSA names O_1, O_2, ..., O_j with a new name N_i,

   then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }.  */

static htab_t repl_tbl;

/* The function the SSA updating data structures have been initialized for.

   NULL if they need to be initialized by register_new_name_mapping.  */

static struct function *update_ssa_initialized_fn = NULL;

/* Statistics kept by update_ssa to use in the virtual mapping

   heuristic.  If the number of virtual mappings is beyond certain

   threshold, the updater will switch from using the mappings into

   renaming the virtual symbols from scratch.  In some cases, the

   large number of name mappings for virtual names causes significant

   slowdowns in the PHI insertion code.  */

struct update_ssa_stats_d

{

  unsigned num_virtual_mappings;

  unsigned num_total_mappings;

  bitmap virtual_symbols;

  unsigned num_virtual_symbols;

};

static struct update_ssa_stats_d update_ssa_stats;

/* Global data to attach to the main dominator walk structure.  */

struct mark_def_sites_global_data

{

  /* This bitmap contains the variables which are set before they

     are used in a basic block.  */

  bitmap kills;

};

/* Information stored for SSA names.  */

struct ssa_name_info

{

  /* The current reaching definition replacing this SSA name.  */

  tree current_def;

  /* This field indicates whether or not the variable may need PHI nodes.

     See the enum's definition for more detailed information about the

     states.  */

  ENUM_BITFIELD (need_phi_state) need_phi_state : 2;

  /* Age of this record (so that info_for_ssa_name table can be cleared

     quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields

     are assumed to be null.  */

  unsigned age;

};

/* The information associated with names.  */

typedef struct ssa_name_info *ssa_name_info_p;

DEF_VEC_P (ssa_name_info_p);

DEF_VEC_ALLOC_P (ssa_name_info_p, heap);

static VEC(ssa_name_info_p, heap) *info_for_ssa_name;

static unsigned current_info_for_ssa_name_age;

/* The set of blocks affected by update_ssa.  */

static bitmap blocks_to_update;

/* The main entry point to the SSA renamer (rewrite_blocks) may be

   called several times to do different, but related, tasks.

   Initially, we need it to rename the whole program into SSA form.

   At other times, we may need it to only rename into SSA newly

   exposed symbols.  Finally, we can also call it to incrementally fix

   an already built SSA web.  */

enum rewrite_mode {

    /* Convert the whole function into SSA form.  */

    REWRITE_ALL,

    /* Incrementally update the SSA web by replacing existing SSA

       names with new ones.  See update_ssa for details.  */

    REWRITE_UPDATE

};

/* Prototypes for debugging functions.  */

extern void dump_tree_ssa (FILE *);

extern void debug_tree_ssa (void);

extern void debug_def_blocks (void);

extern void dump_tree_ssa_stats (FILE *);

extern void debug_tree_ssa_stats (void);

extern void dump_update_ssa (FILE *);

extern void debug_update_ssa (void);

extern void dump_names_replaced_by (FILE *, tree);

extern void debug_names_replaced_by (tree);

extern void dump_def_blocks (FILE *);

extern void debug_def_blocks (void);

extern void dump_defs_stack (FILE *, int);

extern void debug_defs_stack (int);

extern void dump_currdefs (FILE *);

extern void debug_currdefs (void);

/* Return true if STMT needs to be rewritten.  When renaming a subset

   of the variables, not all statements will be processed.  This is

   decided in mark_def_sites.  */

static inline bool

rewrite_uses_p (gimple stmt)

{

  return gimple_visited_p (stmt);

}

/* Set the rewrite marker on STMT to the value given by REWRITE_P.  */

static inline void

set_rewrite_uses (gimple stmt, bool rewrite_p)

{

  gimple_set_visited (stmt, rewrite_p);

}

/* Return true if the DEFs created by statement STMT should be

   registered when marking new definition sites.  This is slightly

   different than rewrite_uses_p: it's used by update_ssa to

   distinguish statements that need to have both uses and defs

   processed from those that only need to have their defs processed.

   Statements that define new SSA names only need to have their defs

   registered, but they don't need to have their uses renamed.  */

static inline bool

register_defs_p (gimple stmt)

{

  return gimple_plf (stmt, GF_PLF_1) != 0;

}

/* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered.  */

static inline void

set_register_defs (gimple stmt, bool register_defs_p)

{

  gimple_set_plf (stmt, GF_PLF_1, register_defs_p);

}

/* Get the information associated with NAME.  */

static inline ssa_name_info_p

get_ssa_name_ann (tree name)

{

  unsigned ver = SSA_NAME_VERSION (name);

  unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);

  struct ssa_name_info *info;

  if (ver >= len)

    {

      unsigned new_len = num_ssa_names;

      VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);

      while (len++ < new_len)

        {

          struct ssa_name_info *info = XCNEW (struct ssa_name_info);

          info->age = current_info_for_ssa_name_age;

          VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);

        }

    }

  info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);

  if (info->age < current_info_for_ssa_name_age)

    {

      info->need_phi_state = NEED_PHI_STATE_UNKNOWN;

      info->current_def = NULL_TREE;

      info->age = current_info_for_ssa_name_age;

    }

  return info;

}

/* Clears info for SSA names.  */

static void

clear_ssa_name_info (void)

{

  current_info_for_ssa_name_age++;

}

/* Get phi_state field for VAR.  */

static inline enum need_phi_state

get_phi_state (tree var)

{

  if (TREE_CODE (var) == SSA_NAME)

    return get_ssa_name_ann (var)->need_phi_state;

  else

    return var_ann (var)->need_phi_state;

}

/* Sets phi_state field for VAR to STATE.  */

static inline void

set_phi_state (tree var, enum need_phi_state state)

{

  if (TREE_CODE (var) == SSA_NAME)

    get_ssa_name_ann (var)->need_phi_state = state;

  else

    var_ann (var)->need_phi_state = state;

}

/* Return the current definition for VAR.  */

tree

get_current_def (tree var)

{

  if (TREE_CODE (var) == SSA_NAME)

    return get_ssa_name_ann (var)->current_def;

  else

    return var_ann (var)->current_def;

}

/* Sets current definition of VAR to DEF.  */

void

set_current_def (tree var, tree def)

{

  if (TREE_CODE (var) == SSA_NAME)

    get_ssa_name_ann (var)->current_def = def;

  else

    var_ann (var)->current_def = def;

}

/* Compute global livein information given the set of blocks where

   an object is locally live at the start of the block (LIVEIN)

   and the set of blocks where the object is defined (DEF_BLOCKS).

   Note: This routine augments the existing local livein information

   to include global livein (i.e., it modifies the underlying bitmap

   for LIVEIN).  */

void

compute_global_livein (bitmap livein ATTRIBUTE_UNUSED, bitmap def_blocks ATTRIBUTE_UNUSED)

{

  basic_block bb, *worklist, *tos;

  unsigned i;

  bitmap_iterator bi;

  tos = worklist

    = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));

  EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)

    *tos++ = BASIC_BLOCK (i);

  /* Iterate until the worklist is empty.  */

  while (tos != worklist)

    {

      edge e;

      edge_iterator ei;

      /* Pull a block off the worklist.  */

      bb = *--tos;

      /* For each predecessor block.  */

      FOR_EACH_EDGE (e, ei, bb->preds)

        {

          basic_block pred = e->src;

          int pred_index = pred->index;

          /* None of this is necessary for the entry block.  */

          if (pred != ENTRY_BLOCK_PTR

              && ! bitmap_bit_p (livein, pred_index)

              && ! bitmap_bit_p (def_blocks, pred_index))

            {

              *tos++ = pred;

              bitmap_set_bit (livein, pred_index);

            }

        }

    }

  free (worklist);

}

/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for

   all statements in basic block BB.  */

static void

initialize_flags_in_bb (basic_block bb)

{

  gimple stmt;

  gimple_stmt_iterator gsi;

  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))

    {

      gimple phi = gsi_stmt (gsi);

      set_rewrite_uses (phi, false);

      set_register_defs (phi, false);

    }

  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))

    {

      stmt = gsi_stmt (gsi);

      /* We are going to use the operand cache API, such as

         SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST.  The operand

         cache for each statement should be up-to-date.  */

      gcc_assert (!gimple_modified_p (stmt));

      set_rewrite_uses (stmt, false);

      set_register_defs (stmt, false);

    }

}

/* Mark block BB as interesting for update_ssa.  */

static void

mark_block_for_update (basic_block bb)

{

  gcc_assert (blocks_to_update != NULL);

  if (bitmap_bit_p (blocks_to_update, bb->index))

    return;

  bitmap_set_bit (blocks_to_update, bb->index);

  initialize_flags_in_bb (bb);

}

/* Return the set of blocks where variable VAR is defined and the blocks

   where VAR is live on entry (livein).  If no entry is found in

   DEF_BLOCKS, a new one is created and returned.  */

static inline struct def_blocks_d *

get_def_blocks_for (tree var)

{

  struct def_blocks_d db, *db_p;

  void **slot;

  db.var = var;

  slot = htab_find_slot (def_blocks, (void *) &db, INSERT);

  if (*slot == NULL)

    {

      db_p = XNEW (struct def_blocks_d);

      db_p->var = var;

      db_p->def_blocks = BITMAP_ALLOC (NULL);

      db_p->phi_blocks = BITMAP_ALLOC (NULL);

      db_p->livein_blocks = BITMAP_ALLOC (NULL);

      *slot = (void *) db_p;

    }

  else

    db_p = (struct def_blocks_d *) *slot;

  return db_p;

}

/* Mark block BB as the definition site for variable VAR.  PHI_P is true if

   VAR is defined by a PHI node.  */

static void

set_def_block (tree var, basic_block bb, bool phi_p)

{

  struct def_blocks_d *db_p;

  enum need_phi_state state;

  state = get_phi_state (var);

  db_p = get_def_blocks_for (var);

  /* Set the bit corresponding to the block where VAR is defined.  */

  bitmap_set_bit (db_p->def_blocks, bb->index);

  if (phi_p)

    bitmap_set_bit (db_p->phi_blocks, bb->index);

  /* Keep track of whether or not we may need to insert PHI nodes.

     If we are in the UNKNOWN state, then this is the first definition

     of VAR.  Additionally, we have not seen any uses of VAR yet, so

     we do not need a PHI node for this variable at this time (i.e.,

     transition to NEED_PHI_STATE_NO).

     If we are in any other state, then we either have multiple definitions

     of this variable occurring in different blocks or we saw a use of the

     variable which was not dominated by the block containing the

     definition(s).  In this case we may need a PHI node, so enter

     state NEED_PHI_STATE_MAYBE.  */

  if (state == NEED_PHI_STATE_UNKNOWN)

    set_phi_state (var, NEED_PHI_STATE_NO);

  else

    set_phi_state (var, NEED_PHI_STATE_MAYBE);

}

/* Mark block BB as having VAR live at the entry to BB.  */

static void

set_livein_block (tree var, basic_block bb)

{

  struct def_blocks_d *db_p;

  enum need_phi_state state = get_phi_state (var);

  db_p = get_def_blocks_for (var);

  /* Set the bit corresponding to the block where VAR is live in.  */

  bitmap_set_bit (db_p->livein_blocks, bb->index);

  /* Keep track of whether or not we may need to insert PHI nodes.

     If we reach here in NEED_PHI_STATE_NO, see if this use is dominated

     by the single block containing the definition(s) of this variable.  If

     it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to

     NEED_PHI_STATE_MAYBE.  */

  if (state == NEED_PHI_STATE_NO)

    {

      int def_block_index = bitmap_first_set_bit (db_p->def_blocks);

      if (def_block_index == -1

          || ! dominated_by_p (CDI_DOMINATORS, bb,

                               BASIC_BLOCK (def_block_index)))

        set_phi_state (var, NEED_PHI_STATE_MAYBE);

    }

  else

    set_phi_state (var, NEED_PHI_STATE_MAYBE);

}

/* Return true if symbol SYM is marked for renaming.  */

static inline bool

symbol_marked_for_renaming (tree sym)

{

  return bitmap_bit_p (SYMS_TO_RENAME (cfun), DECL_UID (sym));

}

/* Return true if NAME is in OLD_SSA_NAMES.  */

static inline bool

is_old_name (tree name)

{

  unsigned ver = SSA_NAME_VERSION (name);

  if (!new_ssa_names)

    return false;

  return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);

}

/* Return true if NAME is in NEW_SSA_NAMES.  */

static inline bool

is_new_name (tree name)

{

  unsigned ver = SSA_NAME_VERSION (name);

  if (!new_ssa_names)

    return false;

  return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);

}

/* Hashing and equality functions for REPL_TBL.  */

static hashval_t

repl_map_hash (const void *p)

{

  return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);

}

static int

repl_map_eq (const void *p1, const void *p2)

{

  return ((const struct repl_map_d *)p1)->name

         == ((const struct repl_map_d *)p2)->name;

}

static void

repl_map_free (void *p)

{

  BITMAP_FREE (((struct repl_map_d *)p)->set);

  free (p);

}

/* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET).  */

static inline bitmap

names_replaced_by (tree new_tree)

{

  struct repl_map_d m;

  void **slot;

  m.name = new_tree;

  slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);

  /* If N was not registered in the replacement table, return NULL.  */

  if (slot == NULL || *slot == NULL)

    return NULL;

  return ((struct repl_map_d *) *slot)->set;

}

/* Add OLD to REPL_TBL[NEW_TREE].SET.  */

static inline void

add_to_repl_tbl (tree new_tree, tree old)

{

  struct repl_map_d m, *mp;

  void **slot;

  m.name = new_tree;

  slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);

  if (*slot == NULL)

    {

      mp = XNEW (struct repl_map_d);

      mp->name = new_tree;

      mp->set = BITMAP_ALLOC (NULL);

      *slot = (void *) mp;

    }

  else

    mp = (struct repl_map_d *) *slot;

  bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));

}

/* Add a new mapping NEW_TREE -> OLD REPL_TBL.  Every entry N_i in REPL_TBL

   represents the set of names O_1 ... O_j replaced by N_i.  This is

   used by update_ssa and its helpers to introduce new SSA names in an

   already formed SSA web.  */

static void

add_new_name_mapping (tree new_tree, tree old)

{

  timevar_push (TV_TREE_SSA_INCREMENTAL);

  /* OLD and NEW_TREE must be different SSA names for the same symbol.  */

  gcc_assert (new_tree != old && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));

  /* If this mapping is for virtual names, we will need to update

     virtual operands.  If this is a mapping for .MEM, then we gather

     the symbols associated with each name.  */

  if (!is_gimple_reg (new_tree))

    {

      tree sym;

      update_ssa_stats.num_virtual_mappings++;

      update_ssa_stats.num_virtual_symbols++;

      /* Keep counts of virtual mappings and symbols to use in the

         virtual mapping heuristic.  If we have large numbers of

         virtual mappings for a relatively low number of symbols, it

         will make more sense to rename the symbols from scratch.

         Otherwise, the insertion of PHI nodes for each of the old

         names in these mappings will be very slow.  */

      sym = SSA_NAME_VAR (new_tree);

      bitmap_set_bit (update_ssa_stats.virtual_symbols, DECL_UID (sym));

    }

  /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our

     caller may have created new names since the set was created.  */

  if (new_ssa_names->n_bits <= num_ssa_names - 1)

    {

      unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;

      new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);

      old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);

    }

  /* Update the REPL_TBL table.  */

  add_to_repl_tbl (new_tree, old);

  /* If OLD had already been registered as a new name, then all the

     names that OLD replaces should also be replaced by NEW_TREE.  */

  if (is_new_name (old))

    bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));

  /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,

     respectively.  */

  SET_BIT (new_ssa_names, SSA_NAME_VERSION (new_tree));

  SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));

  /* Update mapping counter to use in the virtual mapping heuristic.  */

  update_ssa_stats.num_total_mappings++;

  timevar_pop (TV_TREE_SSA_INCREMENTAL);

}

/* Call back for walk_dominator_tree used to collect definition sites

   for every variable in the function.  For every statement S in block

   BB:

   1- Variables defined by S in the DEFS of S are marked in the bitmap

      KILLS.

   2- If S uses a variable VAR and there is no preceding kill of VAR,

      then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.

   This information is used to determine which variables are live

   across block boundaries to reduce the number of PHI nodes

   we create.  */

static void

mark_def_sites (basic_block bb, gimple stmt, bitmap kills)

{

  tree def;

  use_operand_p use_p;

  ssa_op_iter iter;

  /* Since this is the first time that we rewrite the program into SSA

     form, force an operand scan on every statement.  */

  update_stmt (stmt);

  gcc_assert (blocks_to_update == NULL);

  set_register_defs (stmt, false);

  set_rewrite_uses (stmt, false);

  if (is_gimple_debug (stmt))