Subversion Repositories openrisc

/* Liveness for SSA trees.

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

   Free Software Foundation, Inc.

   Contributed by Andrew MacLeod <amacleod@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 "tree-pretty-print.h"

#include "gimple-pretty-print.h"

#include "bitmap.h"

#include "tree-flow.h"

#include "tree-dump.h"

#include "tree-ssa-live.h"

#include "diagnostic-core.h"

#include "debug.h"

#include "flags.h"

#include "gimple.h"

#ifdef ENABLE_CHECKING

static void  verify_live_on_entry (tree_live_info_p);

#endif

/* VARMAP maintains a mapping from SSA version number to real variables.

   All SSA_NAMES are divided into partitions.  Initially each ssa_name is the

   only member of it's own partition.  Coalescing will attempt to group any

   ssa_names which occur in a copy or in a PHI node into the same partition.

   At the end of out-of-ssa, each partition becomes a "real" variable and is

   rewritten as a compiler variable.

   The var_map data structure is used to manage these partitions.  It allows

   partitions to be combined, and determines which partition belongs to what

   ssa_name or variable, and vice versa.  */

/* This routine will initialize the basevar fields of MAP.  */

static void

var_map_base_init (var_map map)

{

  int x, num_part, num;

  tree var;

  var_ann_t ann;

  num = 0;

  num_part = num_var_partitions (map);

  /* If a base table already exists, clear it, otherwise create it.  */

  if (map->partition_to_base_index != NULL)

    {

      free (map->partition_to_base_index);

      VEC_truncate (tree, map->basevars, 0);

    }

  else

    map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10)));

  map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part);

  /* Build the base variable list, and point partitions at their bases.  */

  for (x = 0; x < num_part; x++)

    {

      var = partition_to_var (map, x);

      if (TREE_CODE (var) == SSA_NAME)

         var = SSA_NAME_VAR (var);

      ann = var_ann (var);

      /* If base variable hasn't been seen, set it up.  */

      if (!ann->base_var_processed)

        {

          ann->base_var_processed = 1;

          VAR_ANN_BASE_INDEX (ann) = num++;

          VEC_safe_push (tree, heap, map->basevars, var);

        }

      map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann);

    }

  map->num_basevars = num;

  /* Now clear the processed bit.  */

  for (x = 0; x < num; x++)

    {

       var = VEC_index (tree, map->basevars, x);

       var_ann (var)->base_var_processed = 0;

    }

#ifdef ENABLE_CHECKING

  for (x = 0; x < num_part; x++)

    {

      tree var2;

      var = SSA_NAME_VAR (partition_to_var (map, x));

      var2 = VEC_index (tree, map->basevars, basevar_index (map, x));

      gcc_assert (var == var2);

    }

#endif

}

/* Remove the base table in MAP.  */

static void

var_map_base_fini (var_map map)

{

  /* Free the basevar info if it is present.  */

  if (map->partition_to_base_index != NULL)

    {

      VEC_free (tree, heap, map->basevars);

      free (map->partition_to_base_index);

      map->partition_to_base_index = NULL;

      map->num_basevars = 0;

    }

}

/* Create a variable partition map of SIZE, initialize and return it.  */

var_map

init_var_map (int size)

{

  var_map map;

  map = (var_map) xmalloc (sizeof (struct _var_map));

  map->var_partition = partition_new (size);

  map->partition_to_view = NULL;

  map->view_to_partition = NULL;

  map->num_partitions = size;

  map->partition_size = size;

  map->num_basevars = 0;

  map->partition_to_base_index = NULL;

  map->basevars = NULL;

  return map;

}

/* Free memory associated with MAP.  */

void

delete_var_map (var_map map)

{

  var_map_base_fini (map);

  partition_delete (map->var_partition);

  free (map->partition_to_view);

  free (map->view_to_partition);

  free (map);

}

/* This function will combine the partitions in MAP for VAR1 and VAR2.  It

   Returns the partition which represents the new partition.  If the two

   partitions cannot be combined, NO_PARTITION is returned.  */

int

var_union (var_map map, tree var1, tree var2)

{

  int p1, p2, p3;

  gcc_assert (TREE_CODE (var1) == SSA_NAME);

  gcc_assert (TREE_CODE (var2) == SSA_NAME);

  /* This is independent of partition_to_view. If partition_to_view is

     on, then whichever one of these partitions is absorbed will never have a

     dereference into the partition_to_view array any more.  */

  p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));

  p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));

  gcc_assert (p1 != NO_PARTITION);

  gcc_assert (p2 != NO_PARTITION);

  if (p1 == p2)

    p3 = p1;

  else

    p3 = partition_union (map->var_partition, p1, p2);

  if (map->partition_to_view)

    p3 = map->partition_to_view[p3];

  return p3;

}

/* Compress the partition numbers in MAP such that they fall in the range

   0..(num_partitions-1) instead of wherever they turned out during

   the partitioning exercise.  This removes any references to unused

   partitions, thereby allowing bitmaps and other vectors to be much

   denser.

   This is implemented such that compaction doesn't affect partitioning.

   Ie., once partitions are created and possibly merged, running one

   or more different kind of compaction will not affect the partitions

   themselves.  Their index might change, but all the same variables will

   still be members of the same partition group.  This allows work on reduced

   sets, and no loss of information when a larger set is later desired.

   In particular, coalescing can work on partitions which have 2 or more

   definitions, and then 'recompact' later to include all the single

   definitions for assignment to program variables.  */

/* Set MAP back to the initial state of having no partition view.  Return a

   bitmap which has a bit set for each partition number which is in use in the

   varmap.  */

static bitmap

partition_view_init (var_map map)

{

  bitmap used;

  int tmp;

  unsigned int x;

  used = BITMAP_ALLOC (NULL);

  /* Already in a view? Abandon the old one.  */

  if (map->partition_to_view)

    {

      free (map->partition_to_view);

      map->partition_to_view = NULL;

    }

  if (map->view_to_partition)

    {

      free (map->view_to_partition);

      map->view_to_partition = NULL;

    }

  /* Find out which partitions are actually referenced.  */

  for (x = 0; x < map->partition_size; x++)

    {

      tmp = partition_find (map->var_partition, x);

      if (ssa_name (tmp) != NULL_TREE && is_gimple_reg (ssa_name (tmp))

          && (!has_zero_uses (ssa_name (tmp))

              || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp))))

        bitmap_set_bit (used, tmp);

    }

  map->num_partitions = map->partition_size;

  return used;

}

/* This routine will finalize the view data for MAP based on the partitions

   set in SELECTED.  This is either the same bitmap returned from

   partition_view_init, or a trimmed down version if some of those partitions

   were not desired in this view.  SELECTED is freed before returning.  */

static void

partition_view_fini (var_map map, bitmap selected)

{

  bitmap_iterator bi;

  unsigned count, i, x, limit;

  gcc_assert (selected);

  count = bitmap_count_bits (selected);

  limit = map->partition_size;

  /* If its a one-to-one ratio, we don't need any view compaction.  */

  if (count < limit)

    {

      map->partition_to_view = (int *)xmalloc (limit * sizeof (int));

      memset (map->partition_to_view, 0xff, (limit * sizeof (int)));

      map->view_to_partition = (int *)xmalloc (count * sizeof (int));

      i = 0;

      /* Give each selected partition an index.  */

      EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi)

        {

          map->partition_to_view[x] = i;

          map->view_to_partition[i] = x;

          i++;

        }

      gcc_assert (i == count);

      map->num_partitions = i;

    }

  BITMAP_FREE (selected);

}

/* Create a partition view which includes all the used partitions in MAP.  If

   WANT_BASES is true, create the base variable map as well.  */

extern void

partition_view_normal (var_map map, bool want_bases)

{

  bitmap used;

  used = partition_view_init (map);

  partition_view_fini (map, used);

  if (want_bases)

    var_map_base_init (map);

  else

    var_map_base_fini (map);

}

/* Create a partition view in MAP which includes just partitions which occur in

   the bitmap ONLY. If WANT_BASES is true, create the base variable map

   as well.  */

extern void

partition_view_bitmap (var_map map, bitmap only, bool want_bases)

{

  bitmap used;

  bitmap new_partitions = BITMAP_ALLOC (NULL);

  unsigned x, p;

  bitmap_iterator bi;

  used = partition_view_init (map);

  EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi)

    {

      p = partition_find (map->var_partition, x);

      gcc_assert (bitmap_bit_p (used, p));

      bitmap_set_bit (new_partitions, p);

    }

  partition_view_fini (map, new_partitions);

  BITMAP_FREE (used);

  if (want_bases)

    var_map_base_init (map);

  else

    var_map_base_fini (map);

}

static inline void mark_all_vars_used (tree *, void *data);

/* Helper function for mark_all_vars_used, called via walk_tree.  */

static tree

mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data)

{

  tree t = *tp;

  enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t));

  tree b;

  if (TREE_CODE (t) == SSA_NAME)

    t = SSA_NAME_VAR (t);

  if (IS_EXPR_CODE_CLASS (c)

      && (b = TREE_BLOCK (t)) != NULL)

    TREE_USED (b) = true;

  /* Ignore TMR_OFFSET and TMR_STEP for TARGET_MEM_REFS, as those

     fields do not contain vars.  */

  if (TREE_CODE (t) == TARGET_MEM_REF)

    {

      mark_all_vars_used (&TMR_BASE (t), data);

      mark_all_vars_used (&TMR_INDEX (t), data);

      mark_all_vars_used (&TMR_INDEX2 (t), data);

      *walk_subtrees = 0;

      return NULL;

    }

  /* Only need to mark VAR_DECLS; parameters and return results are not

     eliminated as unused.  */

  if (TREE_CODE (t) == VAR_DECL)

    {

      if (data != NULL && bitmap_clear_bit ((bitmap) data, DECL_UID (t))

          && DECL_CONTEXT (t) == current_function_decl)

        mark_all_vars_used (&DECL_INITIAL (t), data);

      set_is_used (t);

    }

  /* remove_unused_scope_block_p requires information about labels

     which are not DECL_IGNORED_P to tell if they might be used in the IL.  */

  if (TREE_CODE (t) == LABEL_DECL)

    /* Although the TREE_USED values that the frontend uses would be

       acceptable (albeit slightly over-conservative) for our purposes,

       init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we

       must re-compute it here.  */

    TREE_USED (t) = 1;

  if (IS_TYPE_OR_DECL_P (t))

    *walk_subtrees = 0;

  return NULL;

}

/* Mark the scope block SCOPE and its subblocks unused when they can be

   possibly eliminated if dead.  */

static void

mark_scope_block_unused (tree scope)

{

  tree t;

  TREE_USED (scope) = false;

  if (!(*debug_hooks->ignore_block) (scope))

    TREE_USED (scope) = true;

  for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))

    mark_scope_block_unused (t);

}

/* Look if the block is dead (by possibly eliminating its dead subblocks)

   and return true if so.

   Block is declared dead if:

     1) No statements are associated with it.

     2) Declares no live variables

     3) All subblocks are dead

        or there is precisely one subblocks and the block

        has same abstract origin as outer block and declares

        no variables, so it is pure wrapper.

   When we are not outputting full debug info, we also eliminate dead variables

   out of scope blocks to let them to be recycled by GGC and to save copying work

   done by the inliner.  */

static bool

remove_unused_scope_block_p (tree scope)

{

  tree *t, *next;

  bool unused = !TREE_USED (scope);

  int nsubblocks = 0;

  for (t = &BLOCK_VARS (scope); *t; t = next)

    {

      next = &DECL_CHAIN (*t);

      /* Debug info of nested function refers to the block of the

         function.  We might stil call it even if all statements

         of function it was nested into was elliminated.

         TODO: We can actually look into cgraph to see if function

         will be output to file.  */

      if (TREE_CODE (*t) == FUNCTION_DECL)

        unused = false;

      /* If a decl has a value expr, we need to instantiate it

         regardless of debug info generation, to avoid codegen

         differences in memory overlap tests.  update_equiv_regs() may

         indirectly call validate_equiv_mem() to test whether a

         SET_DEST overlaps with others, and if the value expr changes

         by virtual register instantiation, we may get end up with

         different results.  */

      else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t))

        unused = false;

      /* Remove everything we don't generate debug info for.

         Don't remove larger vars though, because BLOCK_VARS are

         used also during expansion to determine which variables

         might share stack space.  */

      else if (DECL_IGNORED_P (*t) && is_gimple_reg (*t))

        {

          *t = DECL_CHAIN (*t);

          next = t;

        }

      /* When we are outputting debug info, we usually want to output

         info about optimized-out variables in the scope blocks.

         Exception are the scope blocks not containing any instructions

         at all so user can't get into the scopes at first place.  */

      else if (var_ann (*t) != NULL && is_used_p (*t))

        unused = false;

      else if (TREE_CODE (*t) == LABEL_DECL && TREE_USED (*t))

        /* For labels that are still used in the IL, the decision to

           preserve them must not depend DEBUG_INFO_LEVEL, otherwise we

           risk having different ordering in debug vs.  non-debug builds

           during inlining or versioning.

           A label appearing here (we have already checked DECL_IGNORED_P)

           should not be used in the IL unless it has been explicitly used

           before, so we use TREE_USED as an approximation.  */

        /* In principle, we should do the same here as for the debug case

           below, however, when debugging, there might be additional nested

           levels that keep an upper level with a label live, so we have to

           force this block to be considered used, too.  */

        unused = false;

      /* When we are not doing full debug info, we however can keep around

         only the used variables for cfgexpand's memory packing saving quite

         a lot of memory.

         For sake of -g3, we keep around those vars but we don't count this as

         use of block, so innermost block with no used vars and no instructions

         can be considered dead.  We only want to keep around blocks user can

         breakpoint into and ask about value of optimized out variables.

         Similarly we need to keep around types at least until all

         variables of all nested blocks are gone.  We track no

         information on whether given type is used or not, so we have

         to keep them even when not emitting debug information,

         otherwise we may end up remapping variables and their (local)

         types in different orders depending on whether debug

         information is being generated.  */

      else if (TREE_CODE (*t) == TYPE_DECL

               || debug_info_level == DINFO_LEVEL_NORMAL

               || debug_info_level == DINFO_LEVEL_VERBOSE)

        ;

      else

        {

          *t = DECL_CHAIN (*t);

          next = t;

        }

    }

  for (t = &BLOCK_SUBBLOCKS (scope); *t ;)

    if (remove_unused_scope_block_p (*t))

      {

        if (BLOCK_SUBBLOCKS (*t))

          {

            tree next = BLOCK_CHAIN (*t);

            tree supercontext = BLOCK_SUPERCONTEXT (*t);

            *t = BLOCK_SUBBLOCKS (*t);

            while (BLOCK_CHAIN (*t))

              {

                BLOCK_SUPERCONTEXT (*t) = supercontext;

                t = &BLOCK_CHAIN (*t);

              }

            BLOCK_CHAIN (*t) = next;

            BLOCK_SUPERCONTEXT (*t) = supercontext;

            t = &BLOCK_CHAIN (*t);

            nsubblocks ++;

          }

        else

          *t = BLOCK_CHAIN (*t);

      }

    else

      {

        t = &BLOCK_CHAIN (*t);

        nsubblocks ++;

      }

   if (!unused)

     ;

   /* Outer scope is always used.  */

   else if (!BLOCK_SUPERCONTEXT (scope)

            || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL)

     unused = false;

   /* Innermost blocks with no live variables nor statements can be always

      eliminated.  */

   else if (!nsubblocks)

     ;

   /* For terse debug info we can eliminate info on unused variables.  */

   else if (debug_info_level == DINFO_LEVEL_NONE

            || debug_info_level == DINFO_LEVEL_TERSE)

     {

       /* Even for -g0/-g1 don't prune outer scopes from artificial

          functions, otherwise diagnostics using tree_nonartificial_location

          will not be emitted properly.  */

       if (inlined_function_outer_scope_p (scope))

         {

           tree ao = scope;

           while (ao

                  && TREE_CODE (ao) == BLOCK

                  && BLOCK_ABSTRACT_ORIGIN (ao) != ao)

             ao = BLOCK_ABSTRACT_ORIGIN (ao);

           if (ao

               && TREE_CODE (ao) == FUNCTION_DECL

               && DECL_DECLARED_INLINE_P (ao)

               && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao)))

             unused = false;

         }

     }

   else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope))

     unused = false;

   /* See if this block is important for representation of inlined function.

      Inlined functions are always represented by block with

      block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION

      set...  */

   else if (inlined_function_outer_scope_p (scope))

     unused = false;

   else

   /* Verfify that only blocks with source location set

      are entry points to the inlined functions.  */

     gcc_assert (BLOCK_SOURCE_LOCATION (scope) == UNKNOWN_LOCATION);

   TREE_USED (scope) = !unused;

   return unused;

}

/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be

   eliminated during the tree->rtl conversion process.  */

static inline void

mark_all_vars_used (tree *expr_p, void *data)

{

  walk_tree (expr_p, mark_all_vars_used_1, data, NULL);

}

/* Dump scope blocks starting at SCOPE to FILE.  INDENT is the

   indentation level and FLAGS is as in print_generic_expr.  */

static void

dump_scope_block (FILE *file, int indent, tree scope, int flags)

{

  tree var, t;

  unsigned int i;

  fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope),

           TREE_USED (scope) ? "" : " (unused)",

           BLOCK_ABSTRACT (scope) ? " (abstract)": "");

  if (BLOCK_SOURCE_LOCATION (scope) != UNKNOWN_LOCATION)

    {

      expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope));

      fprintf (file, " %s:%i", s.file, s.line);

    }

  if (BLOCK_ABSTRACT_ORIGIN (scope))

    {

      tree origin = block_ultimate_origin (scope);

      if (origin)

        {

          fprintf (file, " Originating from :");

          if (DECL_P (origin))

            print_generic_decl (file, origin, flags);

          else

            fprintf (file, "#%i", BLOCK_NUMBER (origin));

        }

    }

  fprintf (file, " \n");

  for (var = BLOCK_VARS (scope); var; var = DECL_CHAIN (var))

    {

      bool used = false;

      if (var_ann (var))

        used = is_used_p (var);

      fprintf (file, "%*s", indent, "");

      print_generic_decl (file, var, flags);

      fprintf (file, "%s\n", used ? "" : " (unused)");

    }

  for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++)

    {

      fprintf (file, "%*s",indent, "");

      print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i),

                          flags);

      fprintf (file, " (nonlocalized)\n");

    }

  for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t))

    dump_scope_block (file, indent + 2, t, flags);

  fprintf (file, "\n%*s}\n",indent, "");

}

/* Dump the tree of lexical scopes starting at SCOPE to stderr.  FLAGS

   is as in print_generic_expr.  */

DEBUG_FUNCTION void

debug_scope_block (tree scope, int flags)

{

  dump_scope_block (stderr, 0, scope, flags);

}

/* Dump the tree of lexical scopes of current_function_decl to FILE.

   FLAGS is as in print_generic_expr.  */

void

dump_scope_blocks (FILE *file, int flags)

{

  dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags);

}

/* Dump the tree of lexical scopes of current_function_decl to stderr.

   FLAGS is as in print_generic_expr.  */

DEBUG_FUNCTION void

debug_scope_blocks (int flags)

{

  dump_scope_blocks (stderr, flags);

}

/* Remove local variables that are not referenced in the IL.  */

void

remove_unused_locals (void)

{

  basic_block bb;

  tree var, t;

  referenced_var_iterator rvi;

  bitmap global_unused_vars = NULL;

  unsigned srcidx, dstidx, num;

  bool have_local_clobbers = false;

  /* Removing declarations from lexical blocks when not optimizing is

     not only a waste of time, it actually causes differences in stack

     layout.  */

  if (!optimize)

    return;

  timevar_push (TV_REMOVE_UNUSED);

  mark_scope_block_unused (DECL_INITIAL (current_function_decl));

  /* Assume all locals are unused.  */

  FOR_EACH_REFERENCED_VAR (cfun, t, rvi)

    clear_is_used (t);

  /* Walk the CFG marking all referenced symbols.  */

  FOR_EACH_BB (bb)

    {

      gimple_stmt_iterator gsi;