Subversion Repositories scarts

/* Interprocedural analyses.

   Copyright (C) 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 "tree.h"

#include "langhooks.h"

#include "ggc.h"

#include "target.h"

#include "cgraph.h"

#include "ipa-prop.h"

#include "tree-flow.h"

#include "tree-pass.h"

#include "flags.h"

#include "timevar.h"

/* This file contains interfaces that can be used for various IPA

   optimizations:

   - ipa_methodlist interface - It is used to create and handle a temporary

   worklist used in  the propagation stage of IPCP. (can be used for more

   IPA optimizations).

   - ipa_callsite interface - for each callsite this interface creates and

   handles ipa_edge structure associated with it.

   - ipa_method interface - for each method this interface creates and

   handles ipa_node structure associated with it.  */

/* ipa_methodlist interface.  */

/* Create a new worklist node.  */

static inline ipa_methodlist_p

ipa_create_methodlist_node (void)

{

  return (ipa_methodlist_p) xcalloc (1, sizeof (struct ipa_methodlist));

}

/* Return true if worklist WL is empty.  */

bool

ipa_methodlist_not_empty (ipa_methodlist_p wl)

{

  return (wl != NULL);

}

/* Return the method in worklist element WL.  */

static inline struct cgraph_node *

ipa_methodlist_method (ipa_methodlist_p wl)

{

  return wl->method_p;

}

/* Make worklist element WL point to method MT in the callgraph.  */

static inline void

ipa_methodlist_method_set (ipa_methodlist_p wl, struct cgraph_node *mt)

{

  wl->method_p = mt;

}

/* Return the next element in the worklist following worklist

   element WL.  */

static inline ipa_methodlist_p

ipa_methodlist_next_method (ipa_methodlist_p wl)

{

  return wl->next_method;

}

/* Set worklist element WL1 to point to worklist element WL2.  */

static inline void

ipa_methodlist_next_method_set (ipa_methodlist_p wl1, ipa_methodlist_p wl2)

{

  wl1->next_method = wl2;

}

/* Initialize worklist to contain all methods.  */

ipa_methodlist_p

ipa_methodlist_init (void)

{

  struct cgraph_node *node;

  ipa_methodlist_p wl;

  wl = NULL;

  for (node = cgraph_nodes; node; node = node->next)

    ipa_add_method (&wl, node);

  return wl;

}

/* Add method MT to the worklist. Set worklist element WL

   to point to MT.  */

void

ipa_add_method (ipa_methodlist_p * wl, struct cgraph_node *mt)

{

  ipa_methodlist_p temp;

  temp = ipa_create_methodlist_node ();

  ipa_methodlist_method_set (temp, mt);

  ipa_methodlist_next_method_set (temp, *wl);

  *wl = temp;

}

/* Remove a method from the worklist. WL points to the first

   element in the list, which is removed.  */

struct cgraph_node *

ipa_remove_method (ipa_methodlist_p * wl)

{

  ipa_methodlist_p first;

  struct cgraph_node *return_method;

  first = *wl;

  *wl = ipa_methodlist_next_method (*wl);

  return_method = ipa_methodlist_method (first);

  free (first);

  return return_method;

}

/* ipa_method interface.  */

/* Return number of formals of method MT.  */

int

ipa_method_formal_count (struct cgraph_node *mt)

{

  return IPA_NODE_REF (mt)->ipa_arg_num;

}

/* Set number of formals of method MT to I.  */

void

ipa_method_formal_count_set (struct cgraph_node *mt, int i)

{

  IPA_NODE_REF (mt)->ipa_arg_num = i;

}

/* Return whether I-th formal of MT is modified in MT.  */

static inline bool

ipa_method_is_modified (struct cgraph_node *mt, int i)

{

  return IPA_NODE_REF (mt)->ipa_mod[i];

}

/* Return the tree of I-th formal of MT.  */

tree

ipa_method_get_tree (struct cgraph_node *mt, int i)

{

  return IPA_NODE_REF (mt)->ipa_param_tree[i];

}

/* Create tree map structure for MT.  */

static inline void

ipa_method_tree_map_create (struct cgraph_node *mt)

{

  IPA_NODE_REF (mt)->ipa_param_tree =

    xcalloc (ipa_method_formal_count (mt), sizeof (tree));

}

/* Create modify structure for MT.  */

static inline void

ipa_method_modify_create (struct cgraph_node *mt)

{

  ((struct ipa_node *) mt->aux)->ipa_mod =

    xcalloc (ipa_method_formal_count (mt), sizeof (bool));

}

/* Set modify of I-th formal of MT to VAL.  */

static inline void

ipa_method_modify_set (struct cgraph_node *mt, int i, bool val)

{

  IPA_NODE_REF (mt)->ipa_mod[i] = val;

}

/* Return index of the formal whose tree is PTREE in method MT.  */

static int

ipa_method_tree_map (struct cgraph_node *mt, tree ptree)

{

  int i, count;

  count = ipa_method_formal_count (mt);

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

    if (IPA_NODE_REF (mt)->ipa_param_tree[i] == ptree)

      return i;

  return -1;

}

/* Insert the formal trees to the ipa_param_tree array in method MT.  */

void

ipa_method_compute_tree_map (struct cgraph_node *mt)

{

  tree fndecl;

  tree fnargs;

  tree parm;

  int param_num;

  ipa_method_tree_map_create (mt);

  fndecl = mt->decl;

  fnargs = DECL_ARGUMENTS (fndecl);

  param_num = 0;

  for (parm = fnargs; parm; parm = TREE_CHAIN (parm))

    {

      IPA_NODE_REF (mt)->ipa_param_tree[param_num] = parm;

      param_num++;

    }

}

/* Count number of formals in MT. Insert the result to the

   ipa_node.  */

void

ipa_method_formal_compute_count (struct cgraph_node *mt)

{

  tree fndecl;

  tree fnargs;

  tree parm;

  int param_num;

  fndecl = mt->decl;

  fnargs = DECL_ARGUMENTS (fndecl);

  param_num = 0;

  for (parm = fnargs; parm; parm = TREE_CHAIN (parm))

    param_num++;

  ipa_method_formal_count_set (mt, param_num);

}

/* Check STMT to detect whether a formal is modified within MT,

   the appropriate entry is updated in the ipa_mod array of ipa_node

   (associated with MT).  */

static void

ipa_method_modify_stmt (struct cgraph_node *mt, tree stmt)

{

  int i, j;

  switch (TREE_CODE (stmt))

    {

    case MODIFY_EXPR:

      if (TREE_CODE (TREE_OPERAND (stmt, 0)) == PARM_DECL)

        {

          i = ipa_method_tree_map (mt, TREE_OPERAND (stmt, 0));

          if (i >= 0)

            ipa_method_modify_set (mt, i, true);

        }

      break;

    case ASM_EXPR:

      /* Asm code could modify any of the parameters.  */

      for (j = 0; j < ipa_method_formal_count (mt); j++)

        ipa_method_modify_set (mt, j, true);

      break;

    default:

      break;

    }

}

/* Initialize ipa_mod array of MT.  */

static void

ipa_method_modify_init (struct cgraph_node *mt)

{

  int i, count;

  ipa_method_modify_create (mt);

  count = ipa_method_formal_count (mt);

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

    ipa_method_modify_set (mt, i, false);

}

/* The modify computation driver for MT. Compute which formal arguments

   of method MT are locally modified.  Formals may be modified in MT

   if their address is taken, or if

   they appear on the left hand side of an assignment.  */

void

ipa_method_compute_modify (struct cgraph_node *mt)

{

  tree decl;

  tree body;

  int j, count;

  basic_block bb;

  struct function *func;

  block_stmt_iterator bsi;

  tree stmt, parm_tree;

  ipa_method_modify_init (mt);

  decl = mt->decl;

  count = ipa_method_formal_count (mt);

  /* ??? Handle pending sizes case. Set all parameters

     of the method to be modified.  */

  if (DECL_UNINLINABLE (decl))

    {

      for (j = 0; j < count; j++)

        ipa_method_modify_set (mt, j, true);

      return;

    }

  /* Formals whose address is taken are considered modified.  */

  for (j = 0; j < count; j++)

    {

      parm_tree = ipa_method_get_tree (mt, j);

      if (TREE_ADDRESSABLE (parm_tree))

        ipa_method_modify_set (mt, j, true);

    }

  body = DECL_SAVED_TREE (decl);

  if (body != NULL)

    {

      func = DECL_STRUCT_FUNCTION (decl);

      FOR_EACH_BB_FN (bb, func)

      {

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

          {

            stmt = bsi_stmt (bsi);

            ipa_method_modify_stmt (mt, stmt);

          }

      }

    }

}

/* ipa_callsite interface.  */

/* Return number of arguments in callsite CS.  */

int

ipa_callsite_param_count (struct cgraph_edge *cs)

{

  return IPA_EDGE_REF (cs)->ipa_param_num;

}

/* Set number of arguments in callsite CS to I.  */

void

ipa_callsite_param_count_set (struct cgraph_edge *cs, int i)

{

  IPA_EDGE_REF (cs)->ipa_param_num = i;

}

/* Return the jump function (ipa_jump_func struct) for argument I of

   callsite CS.  */

struct ipa_jump_func *

ipa_callsite_param (struct cgraph_edge *cs, int i)

{

  return &(IPA_EDGE_REF (cs)->ipa_param_map[i]);

}

/* return the callee (cgraph_node) of callsite CS.  */

struct cgraph_node *

ipa_callsite_callee (struct cgraph_edge *cs)

{

  return cs->callee;

}

/* Set field 'type' of jump function (ipa_jump_func struct) of argument I

   in callsite CS.  */

static inline void

ipa_callsite_param_set_type (struct cgraph_edge *cs, int i,

                             enum jump_func_type type1)

{

  IPA_EDGE_REF (cs)->ipa_param_map[i].type = type1;

}

/* Set FORMAL as 'info_type' field of jump function (ipa_jump_func struct)

   of argument I of callsite CS.  */

static inline void

ipa_callsite_param_set_info_type_formal (struct cgraph_edge *cs, int i,

                                         unsigned int formal)

{

  ipa_callsite_param (cs, i)->info_type.formal_id = formal;

}

/* Set int-valued INFO_TYPE1 as 'info_type' field of

   jump function (ipa_jump_func struct) of argument I of callsite CS.  */

static inline void

ipa_callsite_param_set_info_type (struct cgraph_edge *cs, int i, tree info_type1)

{

  ipa_callsite_param (cs, i)->info_type.value = info_type1;

}

/* Allocate space for callsite CS.  */

static inline void

ipa_callsite_param_map_create (struct cgraph_edge *cs)

{

  IPA_EDGE_REF (cs)->ipa_param_map =

    xcalloc (ipa_callsite_param_count (cs), sizeof (struct ipa_jump_func));

}

/* Return the call expr tree related to callsite CS.  */

static inline tree

ipa_callsite_tree (struct cgraph_edge *cs)

{

  return cs->call_stmt;

}

/* Return the caller (cgraph_node) of CS.  */

static inline struct cgraph_node *

ipa_callsite_caller (struct cgraph_edge *cs)

{

  return cs->caller;

}

/* Count number of arguments callsite CS has and store it in

   ipa_edge structure corresponding to this callsite.  */

void

ipa_callsite_compute_count (struct cgraph_edge *cs)

{

  tree call_tree;

  tree arg;

  int arg_num;

  call_tree = get_call_expr_in (ipa_callsite_tree (cs));

  gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);

  arg = TREE_OPERAND (call_tree, 1);

  arg_num = 0;

  for (; arg != NULL_TREE; arg = TREE_CHAIN (arg))

    arg_num++;

  ipa_callsite_param_count_set (cs, arg_num);

}

/* Compute jump function for all arguments of callsite CS

   and insert the information in the ipa_param_map array

   in the ipa_edge corresponding to this callsite. (Explanation

   on jump functions is in ipa-prop.h).  */

void

ipa_callsite_compute_param (struct cgraph_edge *cs)

{

  tree call_tree;

  tree arg, cst_decl;

  int arg_num;

  int i;

  struct cgraph_node *mt;

  if (ipa_callsite_param_count (cs) == 0)

    return;

  ipa_callsite_param_map_create (cs);

  call_tree = get_call_expr_in (ipa_callsite_tree (cs));

  gcc_assert (TREE_CODE (call_tree) == CALL_EXPR);

  arg = TREE_OPERAND (call_tree, 1);

  arg_num = 0;

  for (; arg != NULL_TREE; arg = TREE_CHAIN (arg))

    {

      /* If the formal parameter was passed as argument, we store

         FORMAL_IPATYPE and its index in the caller as the jump function

         of this argument.  */

      if (TREE_CODE (TREE_VALUE (arg)) == PARM_DECL)

        {

          mt = ipa_callsite_caller (cs);

          i = ipa_method_tree_map (mt, TREE_VALUE (arg));

          if (i < 0 || ipa_method_is_modified (mt, i))

            ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);

          else

            {

              ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE);

              ipa_callsite_param_set_info_type_formal (cs, arg_num, i);

            }

        }

      /* If a constant value was passed as argument,

         we store CONST_IPATYPE and its value as the jump function

         of this argument.  */

      else if (TREE_CODE (TREE_VALUE (arg)) == INTEGER_CST

               || TREE_CODE (TREE_VALUE (arg)) == REAL_CST)

        {

          ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE);

          ipa_callsite_param_set_info_type (cs, arg_num,

                                            TREE_VALUE (arg));

        }

      /* This is for the case of Fortran. If the address of a const_decl

         was passed as argument then we store

         CONST_IPATYPE_REF/CONST_IPATYPE_REF and the constant

         value as the jump function corresponding to this argument.  */

      else if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR

               && TREE_CODE (TREE_OPERAND (TREE_VALUE (arg), 0)) ==

               CONST_DECL)

        {

          cst_decl = TREE_OPERAND (TREE_VALUE (arg), 0);

          if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST

              || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST)

            {

              ipa_callsite_param_set_type (cs, arg_num,

                                           CONST_IPATYPE_REF);

              ipa_callsite_param_set_info_type (cs, arg_num,

                                                DECL_INITIAL (cst_decl));

            }

        }

      else

        ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);

      arg_num++;

    }

}

/* Return type of jump function JF.  */

enum jump_func_type

get_type (struct ipa_jump_func *jf)

{

  return jf->type;

}

/* Return info type of jump function JF.  */

union parameter_info *

ipa_jf_get_info_type (struct ipa_jump_func *jf)

{

  return &(jf->info_type);

}

/* Allocate and initialize ipa_node structure.

   cgraph_node NODE points to the new allocated ipa_node.  */

void

ipa_node_create (struct cgraph_node *node)

{

  node->aux = xcalloc (1, sizeof (struct ipa_node));

}

/* Allocate and initialize ipa_node structure for all

   nodes in callgraph.  */

void

ipa_nodes_create (void)

{

  struct cgraph_node *node;

  for (node = cgraph_nodes; node; node = node->next)

    ipa_node_create (node);

}

/* Allocate and initialize ipa_edge structure.  */

void

ipa_edges_create (void)

{

  struct cgraph_node *node;

  struct cgraph_edge *cs;

  for (node = cgraph_nodes; node; node = node->next)

    for (cs = node->callees; cs; cs = cs->next_callee)

      cs->aux = xcalloc (1, sizeof (struct ipa_edge));

}

/* Free ipa_node structure.  */

void

ipa_nodes_free (void)

{

  struct cgraph_node *node;

  for (node = cgraph_nodes; node; node = node->next)

    {

      free (node->aux);

      node->aux = NULL;

    }

}

/* Free ipa_edge structure.  */

void

ipa_edges_free (void)

{

  struct cgraph_node *node;

  struct cgraph_edge *cs;

  for (node = cgraph_nodes; node; node = node->next)

    for (cs = node->callees; cs; cs = cs->next_callee)

      {

        free (cs->aux);

        cs->aux = NULL;

      }

}

/* Free ipa data structures of ipa_node and ipa_edge.  */

void

ipa_free (void)

{

  struct cgraph_node *node;

  struct cgraph_edge *cs;

  for (node = cgraph_nodes; node; node = node->next)

    {

      if (node->aux == NULL)

        continue;

      if (IPA_NODE_REF (node)->ipcp_cval)

        free (IPA_NODE_REF (node)->ipcp_cval);

      if (IPA_NODE_REF (node)->ipa_param_tree)

        free (IPA_NODE_REF (node)->ipa_param_tree);

      if (IPA_NODE_REF (node)->ipa_mod)

        free (IPA_NODE_REF (node)->ipa_mod);

      for (cs = node->callees; cs; cs = cs->next_callee)

        {

          if (cs->aux)

            if (IPA_EDGE_REF (cs)->ipa_param_map)

              free (IPA_EDGE_REF (cs)->ipa_param_map);

        }

    }

}

/* Print ipa_tree_map data structures of all methods in the

   callgraph to F.  */

void

ipa_method_tree_print (FILE * f)

{

  int i, count;

  tree temp;

  struct cgraph_node *node;

  fprintf (f, "\nPARAM TREE MAP PRINT\n");

  for (node = cgraph_nodes; node; node = node->next)

    {

      fprintf (f, "method  %s Trees :: \n", cgraph_node_name (node));

      count = ipa_method_formal_count (node);

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

        {

          temp = ipa_method_get_tree (node, i);

          if (TREE_CODE (temp) == PARM_DECL)

            fprintf (f, "  param [%d] : %s\n", i,

                     (*lang_hooks.decl_printable_name) (temp, 2));

        }

    }

}

/* Print ipa_modify data structures of all methods in the

   callgraph to F.  */

void

ipa_method_modify_print (FILE * f)

{

  int i, count;

  bool temp;

  struct cgraph_node *node;

  fprintf (f, "\nMODIFY PRINT\n");

  for (node = cgraph_nodes; node; node = node->next)

    {

      fprintf (f, "method  %s :: \n", cgraph_node_name (node));

      count = ipa_method_formal_count (node);

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

        {

          temp = ipa_method_is_modified (node, i);

          if (temp)

            fprintf (f, " param [%d] true \n", i);

          else

            fprintf (f, " param [%d] false \n", i);

        }

    }

}