Subversion Repositories scarts

/* Callgraph based intraprocedural optimizations.

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

   Contributed by Jan Hubicka

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.  */

/* This module implements main driver of compilation process as well as

   few basic intraprocedural optimizers.

   The main scope of this file is to act as an interface in between

   tree based frontends and the backend (and middle end)

   The front-end is supposed to use following functionality:

    - cgraph_finalize_function

      This function is called once front-end has parsed whole body of function

      and it is certain that the function body nor the declaration will change.

      (There is one exception needed for implementing GCC extern inline function.)

    - cgraph_varpool_finalize_variable

      This function has same behavior as the above but is used for static

      variables.

    - cgraph_finalize_compilation_unit

      This function is called once compilation unit is finalized and it will

      no longer change.

      In the unit-at-a-time the call-graph construction and local function

      analysis takes place here.  Bodies of unreachable functions are released

      to conserve memory usage.

      ???  The compilation unit in this point of view should be compilation

      unit as defined by the language - for instance C frontend allows multiple

      compilation units to be parsed at once and it should call function each

      time parsing is done so we save memory.

    - cgraph_optimize

      In this unit-at-a-time compilation the intra procedural analysis takes

      place here.  In particular the static functions whose address is never

      taken are marked as local.  Backend can then use this information to

      modify calling conventions, do better inlining or similar optimizations.

    - cgraph_assemble_pending_functions

    - cgraph_varpool_assemble_pending_variables

      In non-unit-at-a-time mode these functions can be used to force compilation

      of functions or variables that are known to be needed at given stage

      of compilation

    - cgraph_mark_needed_node

    - cgraph_varpool_mark_needed_node

      When function or variable is referenced by some hidden way (for instance

      via assembly code and marked by attribute "used"), the call-graph data structure

      must be updated accordingly by this function.

    - analyze_expr callback

      This function is responsible for lowering tree nodes not understood by

      generic code into understandable ones or alternatively marking

      callgraph and varpool nodes referenced by the as needed.

      ??? On the tree-ssa genericizing should take place here and we will avoid

      need for these hooks (replacing them by genericizing hook)

    - expand_function callback

      This function is used to expand function and pass it into RTL back-end.

      Front-end should not make any assumptions about when this function can be

      called.  In particular cgraph_assemble_pending_functions,

      cgraph_varpool_assemble_pending_variables, cgraph_finalize_function,

      cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily

      previously finalized functions to be expanded.

    We implement two compilation modes.

      - unit-at-a-time:  In this mode analyzing of all functions is deferred

        to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.

        In cgraph_finalize_compilation_unit the reachable functions are

        analyzed.  During analysis the call-graph edges from reachable

        functions are constructed and their destinations are marked as

        reachable.  References to functions and variables are discovered too

        and variables found to be needed output to the assembly file.  Via

        mark_referenced call in assemble_variable functions referenced by

        static variables are noticed too.

        The intra-procedural information is produced and its existence

        indicated by global_info_ready.  Once this flag is set it is impossible

        to change function from !reachable to reachable and thus

        assemble_variable no longer call mark_referenced.

        Finally the call-graph is topologically sorted and all reachable functions

        that has not been completely inlined or are not external are output.

        ??? It is possible that reference to function or variable is optimized

        out.  We can not deal with this nicely because topological order is not

        suitable for it.  For tree-ssa we may consider another pass doing

        optimization and re-discovering reachable functions.

        ??? Reorganize code so variables are output very last and only if they

        really has been referenced by produced code, so we catch more cases

        where reference has been optimized out.

      - non-unit-at-a-time

        All functions are variables are output as early as possible to conserve

        memory consumption.  This may or may not result in less memory used but

        it is still needed for some legacy code that rely on particular ordering

        of things output from the compiler.

        Varpool data structures are not used and variables are output directly.

        Functions are output early using call of

        cgraph_assemble_pending_function from cgraph_finalize_function.  The

        decision on whether function is needed is made more conservative so

        uninlininable static functions are needed too.  During the call-graph

        construction the edge destinations are not marked as reachable and it

        is completely relied upn assemble_variable to mark them.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "tree.h"

#include "rtl.h"

#include "tree-flow.h"

#include "tree-inline.h"

#include "langhooks.h"

#include "pointer-set.h"

#include "toplev.h"

#include "flags.h"

#include "ggc.h"

#include "debug.h"

#include "target.h"

#include "cgraph.h"

#include "diagnostic.h"

#include "timevar.h"

#include "params.h"

#include "fibheap.h"

#include "c-common.h"

#include "intl.h"

#include "function.h"

#include "ipa-prop.h"

#include "tree-gimple.h"

#include "tree-pass.h"

#include "output.h"

static void cgraph_expand_all_functions (void);

static void cgraph_mark_functions_to_output (void);

static void cgraph_expand_function (struct cgraph_node *);

static tree record_reference (tree *, int *, void *);

static void cgraph_analyze_function (struct cgraph_node *node);

/* Records tree nodes seen in record_reference.  Simply using

   walk_tree_without_duplicates doesn't guarantee each node is visited

   once because it gets a new htab upon each recursive call from

   record_reference itself.  */

static struct pointer_set_t *visited_nodes;

static FILE *cgraph_dump_file;

/* Determine if function DECL is needed.  That is, visible to something

   either outside this translation unit, something magic in the system

   configury, or (if not doing unit-at-a-time) to something we havn't

   seen yet.  */

static bool

decide_is_function_needed (struct cgraph_node *node, tree decl)

{

  tree origin;

  if (MAIN_NAME_P (DECL_NAME (decl))

      && TREE_PUBLIC (decl))

    {

      node->local.externally_visible = true;

      return true;

    }

  /* If the user told us it is used, then it must be so.  */

  if (node->local.externally_visible

      || lookup_attribute ("used", DECL_ATTRIBUTES (decl)))

    return true;

  /* ??? If the assembler name is set by hand, it is possible to assemble

     the name later after finalizing the function and the fact is noticed

     in assemble_name then.  This is arguably a bug.  */

  if (DECL_ASSEMBLER_NAME_SET_P (decl)

      && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))

    return true;

  /* If we decided it was needed before, but at the time we didn't have

     the body of the function available, then it's still needed.  We have

     to go back and re-check its dependencies now.  */

  if (node->needed)

    return true;

  /* Externally visible functions must be output.  The exception is

     COMDAT functions that must be output only when they are needed.  */

  if ((TREE_PUBLIC (decl) && !flag_whole_program)

      && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))

    return true;

  /* Constructors and destructors are reachable from the runtime by

     some mechanism.  */

  if (DECL_STATIC_CONSTRUCTOR (decl) || DECL_STATIC_DESTRUCTOR (decl))

    return true;

  if (flag_unit_at_a_time)

    return false;

  /* If not doing unit at a time, then we'll only defer this function

     if its marked for inlining.  Otherwise we want to emit it now.  */

  /* "extern inline" functions are never output locally.  */

  if (DECL_EXTERNAL (decl))

    return false;

  /* Nested functions of extern inline function shall not be emit unless

     we inlined the origin.  */

  for (origin = decl_function_context (decl); origin;

       origin = decl_function_context (origin))

    if (DECL_EXTERNAL (origin))

      return false;

  /* We want to emit COMDAT functions only when absolutely necessary.  */

  if (DECL_COMDAT (decl))

    return false;

  if (!DECL_INLINE (decl)

      || (!node->local.disregard_inline_limits

          /* When declared inline, defer even the uninlinable functions.

             This allows them to be eliminated when unused.  */

          && !DECL_DECLARED_INLINE_P (decl)

          && (!node->local.inlinable || !cgraph_default_inline_p (node, NULL))))

    return true;

  return false;

}

/* Walk the decls we marked as necessary and see if they reference new

   variables or functions and add them into the worklists.  */

static bool

cgraph_varpool_analyze_pending_decls (void)

{

  bool changed = false;

  timevar_push (TV_CGRAPH);

  while (cgraph_varpool_first_unanalyzed_node)

    {

      tree decl = cgraph_varpool_first_unanalyzed_node->decl;

      cgraph_varpool_first_unanalyzed_node->analyzed = true;

      cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed;

      if (DECL_INITIAL (decl))

        {

          visited_nodes = pointer_set_create ();

          walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes);

          pointer_set_destroy (visited_nodes);

          visited_nodes = NULL;

        }

      changed = true;

    }

  timevar_pop (TV_CGRAPH);

  return changed;

}

/* Optimization of function bodies might've rendered some variables as

   unnecessary so we want to avoid these from being compiled.

   This is done by pruning the queue and keeping only the variables that

   really appear needed (ie they are either externally visible or referenced

   by compiled function). Re-doing the reachability analysis on variables

   brings back the remaining variables referenced by these.  */

static void

cgraph_varpool_remove_unreferenced_decls (void)

{

  struct cgraph_varpool_node *next, *node = cgraph_varpool_nodes_queue;

  cgraph_varpool_reset_queue ();

  if (errorcount || sorrycount)

    return;

  while (node)

    {

      tree decl = node->decl;

      next = node->next_needed;

      node->needed = 0;

      if (node->finalized

          && ((DECL_ASSEMBLER_NAME_SET_P (decl)

               && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))

              || node->force_output

              || decide_is_variable_needed (node, decl)

              /* ??? Cgraph does not yet rule the world with an iron hand,

                 and does not control the emission of debug information.

                 After a variable has its DECL_RTL set, we must assume that

                 it may be referenced by the debug information, and we can

                 no longer elide it.  */

              || DECL_RTL_SET_P (decl)))

        cgraph_varpool_mark_needed_node (node);

      node = next;

    }

  /* Make sure we mark alias targets as used targets.  */

  finish_aliases_1 ();

  cgraph_varpool_analyze_pending_decls ();

}

/* When not doing unit-at-a-time, output all functions enqueued.

   Return true when such a functions were found.  */

bool

cgraph_assemble_pending_functions (void)

{

  bool output = false;

  if (flag_unit_at_a_time)

    return false;

  while (cgraph_nodes_queue)

    {

      struct cgraph_node *n = cgraph_nodes_queue;

      cgraph_nodes_queue = cgraph_nodes_queue->next_needed;

      n->next_needed = NULL;

      if (!n->global.inlined_to

          && !n->alias

          && !DECL_EXTERNAL (n->decl))

        {

          cgraph_expand_function (n);

          output = true;

        }

    }

  return output;

}

/* As an GCC extension we allow redefinition of the function.  The

   semantics when both copies of bodies differ is not well defined.

   We replace the old body with new body so in unit at a time mode

   we always use new body, while in normal mode we may end up with

   old body inlined into some functions and new body expanded and

   inlined in others.

   ??? It may make more sense to use one body for inlining and other

   body for expanding the function but this is difficult to do.  */

static void

cgraph_reset_node (struct cgraph_node *node)

{

  /* If node->output is set, then this is a unit-at-a-time compilation

     and we have already begun whole-unit analysis.  This is *not*

     testing for whether we've already emitted the function.  That

     case can be sort-of legitimately seen with real function

     redefinition errors.  I would argue that the front end should

     never present us with such a case, but don't enforce that for now.  */

  gcc_assert (!node->output);

  /* Reset our data structures so we can analyze the function again.  */

  memset (&node->local, 0, sizeof (node->local));

  memset (&node->global, 0, sizeof (node->global));

  memset (&node->rtl, 0, sizeof (node->rtl));

  node->analyzed = false;

  node->local.redefined_extern_inline = true;

  node->local.finalized = false;

  if (!flag_unit_at_a_time)

    {

      struct cgraph_node *n;

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

        if (n->global.inlined_to == node)

          cgraph_remove_node (n);

    }

  cgraph_node_remove_callees (node);

  /* We may need to re-queue the node for assembling in case

     we already proceeded it and ignored as not needed.  */

  if (node->reachable && !flag_unit_at_a_time)

    {

      struct cgraph_node *n;

      for (n = cgraph_nodes_queue; n; n = n->next_needed)

        if (n == node)

          break;

      if (!n)

        node->reachable = 0;

    }

}

/* DECL has been parsed.  Take it, queue it, compile it at the whim of the

   logic in effect.  If NESTED is true, then our caller cannot stand to have

   the garbage collector run at the moment.  We would need to either create

   a new GC context, or just not compile right now.  */

void

cgraph_finalize_function (tree decl, bool nested)

{

  struct cgraph_node *node = cgraph_node (decl);

  if (node->local.finalized)

    cgraph_reset_node (node);

  notice_global_symbol (decl);

  node->decl = decl;

  node->local.finalized = true;

  node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;

  if (node->nested)

    lower_nested_functions (decl);

  gcc_assert (!node->nested);

  /* If not unit at a time, then we need to create the call graph

     now, so that called functions can be queued and emitted now.  */

  if (!flag_unit_at_a_time)

    {

      cgraph_analyze_function (node);

      cgraph_decide_inlining_incrementally (node, false);

    }

  if (decide_is_function_needed (node, decl))

    cgraph_mark_needed_node (node);

  /* Since we reclaim unreachable nodes at the end of every language

     level unit, we need to be conservative about possible entry points

     there.  */

  if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl)))

    cgraph_mark_reachable_node (node);

  /* If not unit at a time, go ahead and emit everything we've found

     to be reachable at this time.  */

  if (!nested)

    {

      if (!cgraph_assemble_pending_functions ())

        ggc_collect ();

    }

  /* If we've not yet emitted decl, tell the debug info about it.  */

  if (!TREE_ASM_WRITTEN (decl))

    (*debug_hooks->deferred_inline_function) (decl);

  /* Possibly warn about unused parameters.  */

  if (warn_unused_parameter)

    do_warn_unused_parameter (decl);

}

void

cgraph_lower_function (struct cgraph_node *node)

{

  if (node->lowered)

    return;

  tree_lowering_passes (node->decl);

  node->lowered = true;

}

/* Walk tree and record all calls.  Called via walk_tree.  */

static tree

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

{

  tree t = *tp;

  switch (TREE_CODE (t))

    {

    case VAR_DECL:

      /* ??? Really, we should mark this decl as *potentially* referenced

         by this function and re-examine whether the decl is actually used

         after rtl has been generated.  */

      if (TREE_STATIC (t) || DECL_EXTERNAL (t))

        {

          cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));

          if (lang_hooks.callgraph.analyze_expr)

            return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees,

                                                      data);

        }

      break;

    case FDESC_EXPR:

    case ADDR_EXPR:

      if (flag_unit_at_a_time)

        {

          /* Record dereferences to the functions.  This makes the

             functions reachable unconditionally.  */

          tree decl = TREE_OPERAND (*tp, 0);

          if (TREE_CODE (decl) == FUNCTION_DECL)

            cgraph_mark_needed_node (cgraph_node (decl));

        }

      break;

    default:

      /* Save some cycles by not walking types and declaration as we

         won't find anything useful there anyway.  */

      if (IS_TYPE_OR_DECL_P (*tp))

        {

          *walk_subtrees = 0;

          break;

        }

      if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)

        return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees, data);

      break;

    }

  return NULL;

}

/* Create cgraph edges for function calls inside BODY from NODE.  */

static void

cgraph_create_edges (struct cgraph_node *node, tree body)

{

  basic_block bb;

  struct function *this_cfun = DECL_STRUCT_FUNCTION (body);

  block_stmt_iterator bsi;

  tree step;

  visited_nodes = pointer_set_create ();

  /* Reach the trees by walking over the CFG, and note the

     enclosing basic-blocks in the call edges.  */

  FOR_EACH_BB_FN (bb, this_cfun)

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

      {

        tree stmt = bsi_stmt (bsi);

        tree call = get_call_expr_in (stmt);

        tree decl;

        if (call && (decl = get_callee_fndecl (call)))

          {

            cgraph_create_edge (node, cgraph_node (decl), stmt,

                                bb->count,

                                bb->loop_depth);

            walk_tree (&TREE_OPERAND (call, 1),

                       record_reference, node, visited_nodes);

            if (TREE_CODE (stmt) == MODIFY_EXPR)

              walk_tree (&TREE_OPERAND (stmt, 0),

                         record_reference, node, visited_nodes);

          }

        else

          walk_tree (bsi_stmt_ptr (bsi), record_reference, node, visited_nodes);

      }

  /* Look for initializers of constant variables and private statics.  */

  for (step = DECL_STRUCT_FUNCTION (body)->unexpanded_var_list;

       step;

       step = TREE_CHAIN (step))

    {

      tree decl = TREE_VALUE (step);

      if (TREE_CODE (decl) == VAR_DECL

          && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))

          && flag_unit_at_a_time)

        cgraph_varpool_finalize_decl (decl);

      else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl))

        walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes);

    }

  pointer_set_destroy (visited_nodes);

  visited_nodes = NULL;

}

/* Give initial reasons why inlining would fail.  Those gets

   either NULLified or usually overwritten by more precise reason

   later.  */

static void

initialize_inline_failed (struct cgraph_node *node)

{

  struct cgraph_edge *e;

  for (e = node->callers; e; e = e->next_caller)

    {

      gcc_assert (!e->callee->global.inlined_to);

      gcc_assert (e->inline_failed);

      if (node->local.redefined_extern_inline)

        e->inline_failed = N_("redefined extern inline functions are not "

                           "considered for inlining");

      else if (!node->local.inlinable)

        e->inline_failed = N_("function not inlinable");

      else

        e->inline_failed = N_("function not considered for inlining");

    }

}

/* Rebuild call edges from current function after a passes not aware

   of cgraph updating.  */

static void

rebuild_cgraph_edges (void)

{

  basic_block bb;

  struct cgraph_node *node = cgraph_node (current_function_decl);

  block_stmt_iterator bsi;

  cgraph_node_remove_callees (node);

  node->count = ENTRY_BLOCK_PTR->count;

  FOR_EACH_BB (bb)

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

      {

        tree stmt = bsi_stmt (bsi);

        tree call = get_call_expr_in (stmt);

        tree decl;

        if (call && (decl = get_callee_fndecl (call)))

          cgraph_create_edge (node, cgraph_node (decl), stmt,

                              bb->count,

                              bb->loop_depth);

      }

  initialize_inline_failed (node);

  gcc_assert (!node->global.inlined_to);

}

struct tree_opt_pass pass_rebuild_cgraph_edges =

{

  NULL,                                 /* name */

  NULL,                                 /* gate */

  rebuild_cgraph_edges,                 /* execute */

  NULL,                                 /* sub */

  NULL,                                 /* next */

  0,                                     /* static_pass_number */

  0,                                     /* tv_id */

  PROP_cfg,                             /* properties_required */

  0,                                     /* properties_provided */

  0,                                     /* properties_destroyed */

  0,                                     /* todo_flags_start */

  0,                                     /* todo_flags_finish */

};

/* Verify cgraph nodes of given cgraph node.  */

void

verify_cgraph_node (struct cgraph_node *node)

{

  struct cgraph_edge *e;

  struct cgraph_node *main_clone;

  struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);

  basic_block this_block;

  block_stmt_iterator bsi;

  bool error_found = false;

  timevar_push (TV_CGRAPH_VERIFY);

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

    if (e->aux)

      {

        error ("aux field set for edge %s->%s",

               cgraph_node_name (e->caller), cgraph_node_name (e->callee));

        error_found = true;

      }

  if (node->count < 0)

    {

      error ("Execution count is negative");

      error_found = true;

    }

  for (e = node->callers; e; e = e->next_caller)

    {

      if (e->count < 0)

        {

          error ("caller edge count is negative");

          error_found = true;

        }

      if (!e->inline_failed)

        {

          if (node->global.inlined_to

              != (e->caller->global.inlined_to

                  ? e->caller->global.inlined_to : e->caller))

            {

              error ("inlined_to pointer is wrong");

              error_found = true;

            }

          if (node->callers->next_caller)

            {

              error ("multiple inline callers");

              error_found = true;

            }

        }

      else

        if (node->global.inlined_to)

          {

            error ("inlined_to pointer set for noninline callers");

            error_found = true;

          }

    }

  if (!node->callers && node->global.inlined_to)

    {

      error ("inlined_to pointer is set but no predecesors found");

      error_found = true;

    }

  if (node->global.inlined_to == node)

    {

      error ("inlined_to pointer refers to itself");

      error_found = true;

    }

  for (main_clone = cgraph_node (node->decl); main_clone;

       main_clone = main_clone->next_clone)

    if (main_clone == node)

      break;

  if (!node)

    {

      error ("node not found in DECL_ASSEMBLER_NAME hash");

      error_found = true;

    }

  if (node->analyzed

      && DECL_SAVED_TREE (node->decl) && !TREE_ASM_WRITTEN (node->decl)

      && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to))

    {

      if (this_cfun->cfg)

        {

          /* The nodes we're interested in are never shared, so walk

             the tree ignoring duplicates.  */