Subversion Repositories scarts

/* Miscellaneous SSA utility functions.

   Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.

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 2, 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 COPYING.  If not, write to

the Free Software Foundation, 51 Franklin Street, Fifth Floor,

Boston, MA 02110-1301, USA.  */

#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 "ggc.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 "pointer-set.h"

#include "tree-flow.h"

#include "tree-gimple.h"

#include "tree-inline.h"

#include "varray.h"

#include "timevar.h"

#include "hashtab.h"

#include "tree-dump.h"

#include "tree-pass.h"

#include "toplev.h"

/* Remove the corresponding arguments from the PHI nodes in E's

   destination block and redirect it to DEST.  Return redirected edge.

   The list of removed arguments is stored in PENDING_STMT (e).  */

edge

ssa_redirect_edge (edge e, basic_block dest)

{

  tree phi;

  tree list = NULL, *last = &list;

  tree src, dst, node;

  /* Remove the appropriate PHI arguments in E's destination block.  */

  for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))

    {

      if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE)

        continue;

      src = PHI_ARG_DEF (phi, e->dest_idx);

      dst = PHI_RESULT (phi);

      node = build_tree_list (dst, src);

      *last = node;

      last = &TREE_CHAIN (node);

    }

  e = redirect_edge_succ_nodup (e, dest);

  PENDING_STMT (e) = list;

  return e;

}

/* Add PHI arguments queued in PENDINT_STMT list on edge E to edge

   E->dest.  */

void

flush_pending_stmts (edge e)

{

  tree phi, arg;

  if (!PENDING_STMT (e))

    return;

  for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);

       phi;

       phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg))

    {

      tree def = TREE_VALUE (arg);

      add_phi_arg (phi, def, e);

    }

  PENDING_STMT (e) = NULL;

}

/* Return true if SSA_NAME is malformed and mark it visited.

   IS_VIRTUAL is true if this SSA_NAME was found inside a virtual

      operand.  */

static bool

verify_ssa_name (tree ssa_name, bool is_virtual)

{

  if (TREE_CODE (ssa_name) != SSA_NAME)

    {

      error ("expected an SSA_NAME object");

      return true;

    }

  if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))

    {

      error ("type mismatch between an SSA_NAME and its symbol");

      return true;

    }

  if (SSA_NAME_IN_FREE_LIST (ssa_name))

    {

      error ("found an SSA_NAME that had been released into the free pool");

      return true;

    }

  if (is_virtual && is_gimple_reg (ssa_name))

    {

      error ("found a virtual definition for a GIMPLE register");

      return true;

    }

  if (!is_virtual && !is_gimple_reg (ssa_name))

    {

      error ("found a real definition for a non-register");

      return true;

    }

  if (is_virtual && var_ann (SSA_NAME_VAR (ssa_name))

      && get_subvars_for_var (SSA_NAME_VAR (ssa_name)) != NULL)

    {

      error ("found real variable when subvariables should have appeared");

      return true;

    }

  return false;

}

/* Return true if the definition of SSA_NAME at block BB is malformed.

   STMT is the statement where SSA_NAME is created.

   DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME

      version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,

      it means that the block in that array slot contains the

      definition of SSA_NAME.

   IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a

      V_MUST_DEF.  */

static bool

verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,

            tree stmt, bool is_virtual)

{

  if (verify_ssa_name (ssa_name, is_virtual))

    goto err;

  if (definition_block[SSA_NAME_VERSION (ssa_name)])

    {

      error ("SSA_NAME created in two different blocks %i and %i",

             definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);

      goto err;

    }

  definition_block[SSA_NAME_VERSION (ssa_name)] = bb;

  if (SSA_NAME_DEF_STMT (ssa_name) != stmt)

    {

      error ("SSA_NAME_DEF_STMT is wrong");

      fprintf (stderr, "Expected definition statement:\n");

      print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);

      fprintf (stderr, "\nActual definition statement:\n");

      print_generic_stmt (stderr, stmt, TDF_VOPS);

      goto err;

    }

  return false;

err:

  fprintf (stderr, "while verifying SSA_NAME ");

  print_generic_expr (stderr, ssa_name, 0);

  fprintf (stderr, " in statement\n");

  print_generic_stmt (stderr, stmt, TDF_VOPS);

  return true;

}

/* Return true if the use of SSA_NAME at statement STMT in block BB is

   malformed.

   DEF_BB is the block where SSA_NAME was found to be created.

   IDOM contains immediate dominator information for the flowgraph.

   CHECK_ABNORMAL is true if the caller wants to check whether this use

      is flowing through an abnormal edge (only used when checking PHI

      arguments).

   IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a

      V_MUST_DEF.

   If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names

     that are defined before STMT in basic block BB.  */

static bool

verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,

            tree stmt, bool check_abnormal, bool is_virtual,

            bitmap names_defined_in_bb)

{

  bool err = false;

  tree ssa_name = USE_FROM_PTR (use_p);

  err = verify_ssa_name (ssa_name, is_virtual);

  if (!TREE_VISITED (ssa_name))

    if (verify_imm_links (stderr, ssa_name))

      err = true;

  TREE_VISITED (ssa_name) = 1;

  if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))

      && default_def (SSA_NAME_VAR (ssa_name)) == ssa_name)

    ; /* Default definitions have empty statements.  Nothing to do.  */

  else if (!def_bb)

    {

      error ("missing definition");

      err = true;

    }

  else if (bb != def_bb

           && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))

    {

      error ("definition in block %i does not dominate use in block %i",

             def_bb->index, bb->index);

      err = true;

    }

  else if (bb == def_bb

           && names_defined_in_bb != NULL

           && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))

    {

      error ("definition in block %i follows the use", def_bb->index);

      err = true;

    }

  if (check_abnormal

      && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))

    {

      error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");

      err = true;

    }

  /* Make sure the use is in an appropriate list by checking the previous

     element to make sure it's the same.  */

  if (use_p->prev == NULL)

    {

      error ("no immediate_use list");

      err = true;

    }

  else

    {

      tree listvar ;

      if (use_p->prev->use == NULL)

        listvar = use_p->prev->stmt;

      else

        listvar = USE_FROM_PTR (use_p->prev);

      if (listvar != ssa_name)

        {

          error ("wrong immediate use list");

          err = true;

        }

    }

  if (err)

    {

      fprintf (stderr, "for SSA_NAME: ");

      print_generic_expr (stderr, ssa_name, TDF_VOPS);

      fprintf (stderr, " in statement:\n");

      print_generic_stmt (stderr, stmt, TDF_VOPS);

    }

  return err;

}

/* Return true if any of the arguments for PHI node PHI at block BB is

   malformed.

   DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version

      numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the

      block in that array slot contains the definition of SSA_NAME.  */

static bool

verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)

{

  edge e;

  bool err = false;

  unsigned i, phi_num_args = PHI_NUM_ARGS (phi);

  if (EDGE_COUNT (bb->preds) != phi_num_args)

    {

      error ("incoming edge count does not match number of PHI arguments");

      err = true;

      goto error;

    }

  for (i = 0; i < phi_num_args; i++)

    {

      use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i);

      tree op = USE_FROM_PTR (op_p);

      e = EDGE_PRED (bb, i);

      if (op == NULL_TREE)

        {

          error ("PHI argument is missing for edge %d->%d",

                 e->src->index,

                 e->dest->index);

          err = true;

          goto error;

        }

      if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))

        {

          error ("PHI argument is not SSA_NAME, or invariant");

          err = true;

        }

      if (TREE_CODE (op) == SSA_NAME)

        err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op_p,

                          phi, e->flags & EDGE_ABNORMAL,

                          !is_gimple_reg (PHI_RESULT (phi)),

                          NULL);

      if (e->dest != bb)

        {

          error ("wrong edge %d->%d for PHI argument",

                 e->src->index, e->dest->index);

          err = true;

        }

      if (err)

        {

          fprintf (stderr, "PHI argument\n");

          print_generic_stmt (stderr, op, TDF_VOPS);

          goto error;

        }

    }

error:

  if (err)

    {

      fprintf (stderr, "for PHI node\n");

      print_generic_stmt (stderr, phi, TDF_VOPS);

    }

  return err;

}

static void

verify_flow_insensitive_alias_info (void)

{

  tree var;

  bitmap visited = BITMAP_ALLOC (NULL);

  referenced_var_iterator rvi;

  FOR_EACH_REFERENCED_VAR (var, rvi)

    {

      size_t j;

      var_ann_t ann;

      varray_type may_aliases;

      ann = var_ann (var);

      may_aliases = ann->may_aliases;

      for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)

        {

          tree alias = VARRAY_TREE (may_aliases, j);

          bitmap_set_bit (visited, DECL_UID (alias));

          if (!may_be_aliased (alias))

            {

              error ("non-addressable variable inside an alias set");

              debug_variable (alias);

              goto err;

            }

        }

    }

  FOR_EACH_REFERENCED_VAR (var, rvi)

    {

      var_ann_t ann;

      ann = var_ann (var);

      if (ann->mem_tag_kind == NOT_A_TAG

          && ann->is_alias_tag

          && !bitmap_bit_p (visited, DECL_UID (var)))

        {

          error ("addressable variable that is an alias tag but is not in any alias set");

          goto err;

        }

    }

  BITMAP_FREE (visited);

  return;

err:

  debug_variable (var);

  internal_error ("verify_flow_insensitive_alias_info failed");

}

static void

verify_flow_sensitive_alias_info (void)

{

  size_t i;

  tree ptr;

  for (i = 1; i < num_ssa_names; i++)

    {

      tree var;

      var_ann_t ann;

      struct ptr_info_def *pi;

      ptr = ssa_name (i);

      if (!ptr)

        continue;

      /* We only care for pointers that are actually referenced in the

         program.  */

      if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))

        continue;

      /* RESULT_DECL is special.  If it's a GIMPLE register, then it

         is only written-to only once in the return statement.

         Otherwise, aggregate RESULT_DECLs may be written-to more than

         once in virtual operands.  */

      var = SSA_NAME_VAR (ptr);

      if (TREE_CODE (var) == RESULT_DECL

          && is_gimple_reg (ptr))

        continue;

      pi = SSA_NAME_PTR_INFO (ptr);

      if (pi == NULL)

        continue;

      ann = var_ann (var);

      if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)

        {

          error ("dereferenced pointers should have a name or a type tag");

          goto err;

        }

      if (pi->name_mem_tag

          && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))

        {

          error ("pointers with a memory tag, should have points-to sets");

          goto err;

        }

      if (pi->value_escapes_p

          && pi->name_mem_tag

          && !is_call_clobbered (pi->name_mem_tag))

        {

          error ("pointer escapes but its name tag is not call-clobbered");

          goto err;

        }

    }

  return;

err:

  debug_variable (ptr);

  internal_error ("verify_flow_sensitive_alias_info failed");

}

DEF_VEC_P (bitmap);

DEF_VEC_ALLOC_P (bitmap,heap);

/* Verify that all name tags have different points to sets.

   This algorithm takes advantage of the fact that every variable with the

   same name tag must have the same points-to set.

   So we check a single variable for each name tag, and verify that its

   points-to set is different from every other points-to set for other name

   tags.

   Additionally, given a pointer P_i with name tag NMT and type tag

   TMT, this function verified the alias set of TMT is a superset of

   the alias set of NMT.  */

static void

verify_name_tags (void)

{

  size_t i;

  size_t j;

  bitmap first, second;

  VEC(tree,heap) *name_tag_reps = NULL;

  VEC(bitmap,heap) *pt_vars_for_reps = NULL;

  bitmap type_aliases = BITMAP_ALLOC (NULL);

  /* First we compute the name tag representatives and their points-to sets.  */

  for (i = 0; i < num_ssa_names; i++)

    {

      struct ptr_info_def *pi;

      tree tmt, ptr = ssa_name (i);

      if (ptr == NULL_TREE)

        continue;

      pi = SSA_NAME_PTR_INFO (ptr);

      if (!TREE_VISITED (ptr)

          || !POINTER_TYPE_P (TREE_TYPE (ptr))

          || !pi

          || !pi->name_mem_tag

          || TREE_VISITED (pi->name_mem_tag))

        continue;

      TREE_VISITED (pi->name_mem_tag) = 1;

      if (pi->pt_vars == NULL)

        continue;

      VEC_safe_push (tree, heap, name_tag_reps, ptr);

      VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars);

      /* Verify that alias set of PTR's type tag is a superset of the

         alias set of PTR's name tag.  */

      tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;

      if (tmt)

        {

          size_t i;

          varray_type aliases = var_ann (tmt)->may_aliases;

          bitmap_clear (type_aliases);

          for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++)

            {

              tree alias = VARRAY_TREE (aliases, i);

              bitmap_set_bit (type_aliases, DECL_UID (alias));

            }

          /* When grouping, we may have added PTR's type tag into the

             alias set of PTR's name tag.  To prevent a false

             positive, pretend that TMT is in its own alias set.  */

          bitmap_set_bit (type_aliases, DECL_UID (tmt));

          if (bitmap_equal_p (type_aliases, pi->pt_vars))

            continue;

          if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars))

            {

              error ("alias set of a pointer's type tag should be a superset of the corresponding name tag");

              debug_variable (tmt);

              debug_variable (pi->name_mem_tag);

              goto err;

            }

        }

    }

  /* Now compare all the representative bitmaps with all other representative

     bitmaps, to verify that they are all different.  */

  for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)

    {

       for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)

         {

           if (bitmap_equal_p (first, second))

             {

               error ("two different pointers with identical points-to sets but different name tags");

               debug_variable (VEC_index (tree, name_tag_reps, j));

               goto err;

             }

         }

    }

  /* Lastly, clear out the visited flags.  */

  for (i = 0; i < num_ssa_names; i++)

    {

      if (ssa_name (i))

        {

          tree ptr = ssa_name (i);

          struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);

          if (!TREE_VISITED (ptr)

              || !POINTER_TYPE_P (TREE_TYPE (ptr))

              || !pi

              || !pi->name_mem_tag)

            continue;

          TREE_VISITED (pi->name_mem_tag) = 0;

        }

    }

  /* We do not have to free the bitmaps or trees in the vectors, as

     they are not owned by us.  */

  VEC_free (bitmap, heap, pt_vars_for_reps);

  VEC_free (tree, heap, name_tag_reps);

  BITMAP_FREE (type_aliases);

  return;

err:

  debug_variable (VEC_index (tree, name_tag_reps, i));

  internal_error ("verify_name_tags failed");

}

/* Verify the consistency of aliasing information.  */

static void

verify_alias_info (void)

{

  verify_flow_sensitive_alias_info ();

  verify_name_tags ();

  verify_flow_insensitive_alias_info ();

}

/* Verify common invariants in the SSA web.

   TODO: verify the variable annotations.  */

void

verify_ssa (bool check_modified_stmt)

{

  size_t i;

  basic_block bb;

  basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));

  ssa_op_iter iter;

  tree op;

  enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];

  bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);

  gcc_assert (!need_ssa_update_p ());

  verify_stmts ();

  timevar_push (TV_TREE_SSA_VERIFY);

  /* Keep track of SSA names present in the IL.  */

  for (i = 1; i < num_ssa_names; i++)

    {

      tree name = ssa_name (i);

      if (name)

        {

          tree stmt;

          TREE_VISITED (name) = 0;

          stmt = SSA_NAME_DEF_STMT (name);

          if (!IS_EMPTY_STMT (stmt))

            {

              basic_block bb = bb_for_stmt (stmt);

              verify_def (bb, definition_block,

                          name, stmt, !is_gimple_reg (name));

            }

        }

    }

  calculate_dominance_info (CDI_DOMINATORS);

  /* Now verify all the uses and make sure they agree with the definitions

     found in the previous pass.  */

  FOR_EACH_BB (bb)

    {

      edge e;

      tree phi;

      edge_iterator ei;

      block_stmt_iterator bsi;

      /* Make sure that all edges have a clear 'aux' field.  */

      FOR_EACH_EDGE (e, ei, bb->preds)

        {

          if (e->aux)

            {

              error ("AUX pointer initialized for edge %d->%d", e->src->index,

                      e->dest->index);

              goto err;

            }

        }

      /* Verify the arguments for every PHI node in the block.  */

      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))

        {

          if (verify_phi_args (phi, bb, definition_block))

            goto err;

          bitmap_set_bit (names_defined_in_bb,

                          SSA_NAME_VERSION (PHI_RESULT (phi)));

        }

      /* Now verify all the uses and vuses in every statement of the block.  */

      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))

        {

          tree stmt = bsi_stmt (bsi);

          use_operand_p use_p;

          if (check_modified_stmt && stmt_modified_p (stmt))

            {

              error ("stmt (%p) marked modified after optimization pass : ",

                     (void *)stmt);