* gcc.target/powerpc: New directory.

[official-gcc.git] / gcc / ipa-prop.c

/* 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, arg_type, formal_type;
  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
            {
                arg_type = TREE_TYPE (TREE_VALUE (arg));
                formal_type = TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num));
                if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
                    && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
                    && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
                                             TYPE_ATTRIBUTES (formal_type)))
                  {
                    ipa_callsite_param_set_type (cs, arg_num, FORMAL_IPATYPE);
                    ipa_callsite_param_set_info_type_formal (cs, arg_num, i);
                  }
                else
                  ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
            }
        }
      /* 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)
        {
          arg_type = TREE_TYPE (TREE_VALUE (arg));
          formal_type = TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num));
          if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
              && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
              && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
                                       TYPE_ATTRIBUTES (formal_type)))
            {
              ipa_callsite_param_set_type (cs, arg_num, CONST_IPATYPE);
              ipa_callsite_param_set_info_type (cs, arg_num, TREE_VALUE (arg));
            }
          else
            ipa_callsite_param_set_type (cs, arg_num, UNKNOWN_IPATYPE);
        }
      /* 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);
          arg_type = TREE_TYPE (DECL_INITIAL (cst_decl));
          formal_type =
            TREE_TYPE (TREE_TYPE (ipa_method_get_tree (cs->callee, arg_num)));
          if (TREE_CODE (DECL_INITIAL (cst_decl)) == INTEGER_CST
              || TREE_CODE (DECL_INITIAL (cst_decl)) == REAL_CST)
            {
              if (TYPE_NAME (arg_type) == TYPE_NAME (formal_type)
                  && TYPE_CONTEXT (arg_type) == TYPE_CONTEXT (formal_type)
                  && attribute_list_equal (TYPE_ATTRIBUTES (arg_type),
                                           TYPE_ATTRIBUTES (formal_type)))

                {
                  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);
            }
        }
      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);
        }
    }
}