Subversion Repositories openrisc

/* Callgraph based interprocedural optimizations.

/* Callgraph based interprocedural optimizations.

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

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

   Contributed by Jan Hubicka

   Contributed by Jan Hubicka

This file is part of GCC.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

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

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 3, or (at your option) any later

Software Foundation; either version 3, or (at your option) any later

version.

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

for more details.

You should have received a copy of the GNU General Public License

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

<http://www.gnu.org/licenses/>.  */

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

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

   few basic interprocedural optimizers.

   few basic interprocedural optimizers.

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

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

   tree based frontends and the backend (and middle end)

   tree based frontends and the backend (and middle end)

   The front-end is supposed to use following functionality:

   The front-end is supposed to use following functionality:

    - cgraph_finalize_function

    - cgraph_finalize_function

      This function is called once front-end has parsed whole body of 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.

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

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

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

    - cgraph_varpool_finalize_variable

    - cgraph_varpool_finalize_variable

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

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

      variables.

      variables.

    - cgraph_finalize_compilation_unit

    - cgraph_finalize_compilation_unit

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

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

      no longer change.

      no longer change.

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

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

      analysis takes place here.  Bodies of unreachable functions are released

      analysis takes place here.  Bodies of unreachable functions are released

      to conserve memory usage.

      to conserve memory usage.

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

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

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

      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

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

      time parsing is done so we save memory.

      time parsing is done so we save memory.

    - cgraph_optimize

    - cgraph_optimize

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

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

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

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

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

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

      modify calling conventions, do better inlining or similar optimizations.

      modify calling conventions, do better inlining or similar optimizations.

    - cgraph_assemble_pending_functions

    - cgraph_assemble_pending_functions

    - cgraph_varpool_assemble_pending_variables

    - cgraph_varpool_assemble_pending_variables

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

      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 functions or variables that are known to be needed at given stage

      of compilation

      of compilation

    - cgraph_mark_needed_node

    - cgraph_mark_needed_node

    - cgraph_varpool_mark_needed_node

    - cgraph_varpool_mark_needed_node

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

      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

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

      must be updated accordingly by this function.

      must be updated accordingly by this function.

    - analyze_expr callback

    - analyze_expr callback

      This function is responsible for lowering tree nodes not understood by

      This function is responsible for lowering tree nodes not understood by

      generic code into understandable ones or alternatively marking

      generic code into understandable ones or alternatively marking

      callgraph and varpool nodes referenced by the as needed.

      callgraph and varpool nodes referenced by the as needed.

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

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

      need for these hooks (replacing them by genericizing hook)

      need for these hooks (replacing them by genericizing hook)

    - expand_function callback

    - expand_function callback

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

      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

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

      called.  In particular cgraph_assemble_pending_functions,

      called.  In particular cgraph_assemble_pending_functions,

      cgraph_varpool_assemble_pending_variables, cgraph_finalize_function,

      cgraph_varpool_assemble_pending_variables, cgraph_finalize_function,

      cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily

      cgraph_varpool_finalize_function, cgraph_optimize can cause arbitrarily

      previously finalized functions to be expanded.

      previously finalized functions to be expanded.

    We implement two compilation modes.

    We implement two compilation modes.

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

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

        to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.

        to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.

        In cgraph_finalize_compilation_unit the reachable functions are

        In cgraph_finalize_compilation_unit the reachable functions are

        analyzed.  During analysis the call-graph edges from reachable

        analyzed.  During analysis the call-graph edges from reachable

        functions are constructed and their destinations are marked as

        functions are constructed and their destinations are marked as

        reachable.  References to functions and variables are discovered too

        reachable.  References to functions and variables are discovered too

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

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

        mark_referenced call in assemble_variable functions referenced by

        mark_referenced call in assemble_variable functions referenced by

        static variables are noticed too.

        static variables are noticed too.

        The intra-procedural information is produced and its existence

        The intra-procedural information is produced and its existence

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

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

        to change function from !reachable to reachable and thus

        to change function from !reachable to reachable and thus

        assemble_variable no longer call mark_referenced.

        assemble_variable no longer call mark_referenced.

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

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

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

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

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

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

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

        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

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

        optimization and re-discovering reachable functions.

        optimization and re-discovering reachable functions.

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

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

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

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

        where reference has been optimized out.

        where reference has been optimized out.

      - non-unit-at-a-time

      - non-unit-at-a-time

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

        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

        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

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

        of things output from the compiler.

        of things output from the compiler.

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

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

        Functions are output early using call of

        Functions are output early using call of

        cgraph_assemble_pending_function from cgraph_finalize_function.  The

        cgraph_assemble_pending_function from cgraph_finalize_function.  The

        decision on whether function is needed is made more conservative so

        decision on whether function is needed is made more conservative so

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

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

        construction the edge destinations are not marked as reachable and it

        construction the edge destinations are not marked as reachable and it

        is completely relied upn assemble_variable to mark them.  */

        is completely relied upn assemble_variable to mark them.  */

#include "config.h"

#include "config.h"

#include "system.h"

#include "system.h"

#include "coretypes.h"

#include "coretypes.h"

#include "tm.h"

#include "tm.h"

#include "tree.h"

#include "tree.h"

#include "rtl.h"

#include "rtl.h"

#include "tree-flow.h"

#include "tree-flow.h"

#include "tree-inline.h"

#include "tree-inline.h"

#include "langhooks.h"

#include "langhooks.h"

#include "pointer-set.h"

#include "pointer-set.h"

#include "toplev.h"

#include "toplev.h"

#include "flags.h"

#include "flags.h"

#include "ggc.h"

#include "ggc.h"

#include "debug.h"

#include "debug.h"

#include "target.h"

#include "target.h"

#include "cgraph.h"

#include "cgraph.h"

#include "diagnostic.h"

#include "diagnostic.h"

#include "timevar.h"

#include "timevar.h"

#include "params.h"

#include "params.h"

#include "fibheap.h"

#include "fibheap.h"

#include "c-common.h"

#include "c-common.h"

#include "intl.h"

#include "intl.h"

#include "function.h"

#include "function.h"

#include "ipa-prop.h"

#include "ipa-prop.h"

#include "tree-gimple.h"

#include "tree-gimple.h"

#include "tree-pass.h"

#include "tree-pass.h"

#include "output.h"

#include "output.h"

static void cgraph_expand_all_functions (void);

static void cgraph_expand_all_functions (void);

static void cgraph_mark_functions_to_output (void);

static void cgraph_mark_functions_to_output (void);

static void cgraph_expand_function (struct cgraph_node *);

static void cgraph_expand_function (struct cgraph_node *);

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

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

static void cgraph_output_pending_asms (void);

static void cgraph_output_pending_asms (void);

static void cgraph_increase_alignment (void);

static void cgraph_increase_alignment (void);

/* Lists all assembled variables to be sent to debugger output later on.  */

/* Lists all assembled variables to be sent to debugger output later on.  */

static GTY(()) struct cgraph_varpool_node *cgraph_varpool_assembled_nodes_queue;

static GTY(()) struct cgraph_varpool_node *cgraph_varpool_assembled_nodes_queue;

/* Records tree nodes seen in record_reference.  Simply using

/* Records tree nodes seen in record_reference.  Simply using

   walk_tree_without_duplicates doesn't guarantee each node is visited

   walk_tree_without_duplicates doesn't guarantee each node is visited

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

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

   record_reference itself.  */

   record_reference itself.  */

static struct pointer_set_t *visited_nodes;

static struct pointer_set_t *visited_nodes;

static FILE *cgraph_dump_file;

static FILE *cgraph_dump_file;

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

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

   either outside this translation unit, something magic in the system

   either outside this translation unit, something magic in the system

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

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

   seen yet.  */

   seen yet.  */

static bool

static bool

decide_is_function_needed (struct cgraph_node *node, tree decl)

decide_is_function_needed (struct cgraph_node *node, tree decl)

{

{

  tree origin;

  tree origin;

  if (MAIN_NAME_P (DECL_NAME (decl))

  if (MAIN_NAME_P (DECL_NAME (decl))

      && TREE_PUBLIC (decl))

      && TREE_PUBLIC (decl))

    {

    {

      node->local.externally_visible = true;

      node->local.externally_visible = true;

      return true;

      return true;

    }

    }

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

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

  if (node->local.externally_visible)

  if (node->local.externally_visible)

    return true;

    return true;

  if (!flag_unit_at_a_time && lookup_attribute ("used", DECL_ATTRIBUTES (decl)))

  if (!flag_unit_at_a_time && lookup_attribute ("used", DECL_ATTRIBUTES (decl)))

    return true;

    return true;

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

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

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

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

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

  if (DECL_ASSEMBLER_NAME_SET_P (decl)

  if (DECL_ASSEMBLER_NAME_SET_P (decl)

      && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))

      && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))

    return true;

    return true;

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

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

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

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

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

  if (node->needed)

  if (node->needed)

    return true;

    return true;

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

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

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

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

     When not optimizing, also output the static functions. (see

     When not optimizing, also output the static functions. (see

     PR24561), but don't do so for always_inline functions, functions

     PR24561), but don't do so for always_inline functions, functions

     declared inline and nested functions.  These was optimized out

     declared inline and nested functions.  These was optimized out

     in the original implementation and it is unclear whether we want

     in the original implementation and it is unclear whether we want

     to change the behavior here.  */

     to change the behavior here.  */

  if (((TREE_PUBLIC (decl)

  if (((TREE_PUBLIC (decl)

        || (!optimize && !node->local.disregard_inline_limits

        || (!optimize && !node->local.disregard_inline_limits

            && !DECL_DECLARED_INLINE_P (decl)

            && !DECL_DECLARED_INLINE_P (decl)

            && !node->origin))

            && !node->origin))

      && !flag_whole_program)

      && !flag_whole_program)

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

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

    return true;

    return true;

  /* Constructors and destructors are reachable from the runtime by

  /* Constructors and destructors are reachable from the runtime by

     some mechanism.  */

     some mechanism.  */

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

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

    return true;

    return true;

  if (flag_unit_at_a_time)

  if (flag_unit_at_a_time)

    return false;

    return false;

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

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

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

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

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

  if (DECL_EXTERNAL (decl))

  if (DECL_EXTERNAL (decl))

    return false;

    return false;

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

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

     we inlined the origin.  */

     we inlined the origin.  */

  for (origin = decl_function_context (decl); origin;

  for (origin = decl_function_context (decl); origin;

       origin = decl_function_context (origin))

       origin = decl_function_context (origin))

    if (DECL_EXTERNAL (origin))

    if (DECL_EXTERNAL (origin))

      return false;

      return false;

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

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

  if (DECL_COMDAT (decl))

  if (DECL_COMDAT (decl))

    return false;

    return false;

  if (!DECL_INLINE (decl)

  if (!DECL_INLINE (decl)

      || (!node->local.disregard_inline_limits

      || (!node->local.disregard_inline_limits

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

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

             This allows them to be eliminated when unused.  */

             This allows them to be eliminated when unused.  */

          && !DECL_DECLARED_INLINE_P (decl)

          && !DECL_DECLARED_INLINE_P (decl)

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

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

    return true;

    return true;

  return false;

  return false;

}

}

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

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

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

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

static bool

static bool

cgraph_varpool_analyze_pending_decls (void)

cgraph_varpool_analyze_pending_decls (void)

{

{

  bool changed = false;

  bool changed = false;

  timevar_push (TV_CGRAPH);

  timevar_push (TV_CGRAPH);

  while (cgraph_varpool_first_unanalyzed_node)

  while (cgraph_varpool_first_unanalyzed_node)

    {

    {

      tree decl = cgraph_varpool_first_unanalyzed_node->decl;

      tree decl = cgraph_varpool_first_unanalyzed_node->decl;

      cgraph_varpool_first_unanalyzed_node->analyzed = true;

      cgraph_varpool_first_unanalyzed_node->analyzed = true;

      cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed;

      cgraph_varpool_first_unanalyzed_node = cgraph_varpool_first_unanalyzed_node->next_needed;

      /* Compute the alignment early so function body expanders are

      /* Compute the alignment early so function body expanders are

         already informed about increased alignment.  */

         already informed about increased alignment.  */

      align_variable (decl, 0);

      align_variable (decl, 0);

      if (DECL_INITIAL (decl))

      if (DECL_INITIAL (decl))

        {

        {

          visited_nodes = pointer_set_create ();

          visited_nodes = pointer_set_create ();

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

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

          pointer_set_destroy (visited_nodes);

          pointer_set_destroy (visited_nodes);

          visited_nodes = NULL;

          visited_nodes = NULL;

        }

        }

      changed = true;

      changed = true;

    }

    }

  timevar_pop (TV_CGRAPH);

  timevar_pop (TV_CGRAPH);

  return changed;

  return changed;

}

}

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

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

   unnecessary so we want to avoid these from being compiled.

   unnecessary so we want to avoid these from being compiled.

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

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

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

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

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

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

   brings back the remaining variables referenced by these.  */

   brings back the remaining variables referenced by these.  */

static void

static void

cgraph_varpool_remove_unreferenced_decls (void)

cgraph_varpool_remove_unreferenced_decls (void)

{

{

  struct cgraph_varpool_node *next, *node = cgraph_varpool_nodes_queue;

  struct cgraph_varpool_node *next, *node = cgraph_varpool_nodes_queue;

  cgraph_varpool_reset_queue ();

  cgraph_varpool_reset_queue ();

  if (errorcount || sorrycount)

  if (errorcount || sorrycount)

    return;

    return;

  while (node)

  while (node)

    {

    {

      tree decl = node->decl;

      tree decl = node->decl;

      next = node->next_needed;

      next = node->next_needed;

      node->needed = 0;

      node->needed = 0;

      if (node->finalized

      if (node->finalized

          && ((DECL_ASSEMBLER_NAME_SET_P (decl)

          && ((DECL_ASSEMBLER_NAME_SET_P (decl)

               && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))

               && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))

              || node->force_output

              || node->force_output

              || decide_is_variable_needed (node, decl)

              || decide_is_variable_needed (node, decl)

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

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

                 and does not control the emission of debug information.

                 and does not control the emission of debug information.

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

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

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

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

                 no longer elide it.  */

                 no longer elide it.  */

              || DECL_RTL_SET_P (decl)))

              || DECL_RTL_SET_P (decl)))

        cgraph_varpool_mark_needed_node (node);

        cgraph_varpool_mark_needed_node (node);

      node = next;

      node = next;

    }

    }

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

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

  finish_aliases_1 ();

  finish_aliases_1 ();

  cgraph_varpool_analyze_pending_decls ();

  cgraph_varpool_analyze_pending_decls ();

}

}

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

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

   Return true when such a functions were found.  */

   Return true when such a functions were found.  */

bool

bool

cgraph_assemble_pending_functions (void)

cgraph_assemble_pending_functions (void)

{

{

  bool output = false;

  bool output = false;

  if (flag_unit_at_a_time)

  if (flag_unit_at_a_time)

    return false;

    return false;

  cgraph_output_pending_asms ();

  cgraph_output_pending_asms ();

  while (cgraph_nodes_queue)

  while (cgraph_nodes_queue)

    {

    {

      struct cgraph_node *n = cgraph_nodes_queue;

      struct cgraph_node *n = cgraph_nodes_queue;

      cgraph_nodes_queue = cgraph_nodes_queue->next_needed;

      cgraph_nodes_queue = cgraph_nodes_queue->next_needed;

      n->next_needed = NULL;

      n->next_needed = NULL;

      if (!n->global.inlined_to

      if (!n->global.inlined_to

          && !n->alias

          && !n->alias

          && !DECL_EXTERNAL (n->decl))

          && !DECL_EXTERNAL (n->decl))

        {

        {

          cgraph_expand_function (n);

          cgraph_expand_function (n);

          output = true;

          output = true;

        }

        }

    }

    }

  /* Process CGRAPH_EXPAND_QUEUE, these are functions created during

  /* Process CGRAPH_EXPAND_QUEUE, these are functions created during

     the expansion process.  Note that this queue may grow as its

     the expansion process.  Note that this queue may grow as its

     being processed, as the new functions may generate new ones.  */

     being processed, as the new functions may generate new ones.  */

  while (cgraph_expand_queue)

  while (cgraph_expand_queue)

    {

    {

      struct cgraph_node *n = cgraph_expand_queue;

      struct cgraph_node *n = cgraph_expand_queue;

      cgraph_expand_queue = cgraph_expand_queue->next_needed;

      cgraph_expand_queue = cgraph_expand_queue->next_needed;

      n->next_needed = NULL;

      n->next_needed = NULL;

      cgraph_finalize_function (n->decl, false);

      cgraph_finalize_function (n->decl, false);

      output = true;

      output = true;

    }

    }

  return output;

  return output;

}

}

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

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

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

   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 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

   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

   old body inlined into some functions and new body expanded and

   inlined in others.

   inlined in others.

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

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

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

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

static void

static void

cgraph_reset_node (struct cgraph_node *node)

cgraph_reset_node (struct cgraph_node *node)

{

{

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

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

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

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

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

     case can be sort-of legitimately seen with real function

     case can be sort-of legitimately seen with real function

     redefinition errors.  I would argue that the front end should

     redefinition errors.  I would argue that the front end should

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

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

  gcc_assert (!node->output);

  gcc_assert (!node->output);

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

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

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

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

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

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

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

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

  node->analyzed = false;

  node->analyzed = false;

  node->local.redefined_extern_inline = true;

  node->local.redefined_extern_inline = true;

  node->local.finalized = false;

  node->local.finalized = false;

  if (!flag_unit_at_a_time)

  if (!flag_unit_at_a_time)

    {

    {

      struct cgraph_node *n, *next;

      struct cgraph_node *n, *next;

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

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

        {

        {

          next = n->next;

          next = n->next;

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

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

            cgraph_remove_node (n);

            cgraph_remove_node (n);

        }

        }

    }

    }

  cgraph_node_remove_callees (node);

  cgraph_node_remove_callees (node);

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

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

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

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

  if (node->reachable && !flag_unit_at_a_time)

  if (node->reachable && !flag_unit_at_a_time)

    {

    {

      struct cgraph_node *n;

      struct cgraph_node *n;

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

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

        if (n == node)

        if (n == node)

          break;

          break;

      if (!n)

      if (!n)

        node->reachable = 0;

        node->reachable = 0;

    }

    }

}

}

static void

static void

cgraph_lower_function (struct cgraph_node *node)

cgraph_lower_function (struct cgraph_node *node)

{

{

  if (node->lowered)

  if (node->lowered)

    return;

    return;

  tree_lowering_passes (node->decl);

  tree_lowering_passes (node->decl);

  node->lowered = true;

  node->lowered = true;

}

}

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

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

   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

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

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

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

void

void

cgraph_finalize_function (tree decl, bool nested)

cgraph_finalize_function (tree decl, bool nested)

{

{

  struct cgraph_node *node = cgraph_node (decl);

  struct cgraph_node *node = cgraph_node (decl);

  if (node->local.finalized)

  if (node->local.finalized)

    cgraph_reset_node (node);

    cgraph_reset_node (node);

  notice_global_symbol (decl);

  notice_global_symbol (decl);

  node->decl = decl;

  node->decl = decl;

  node->local.finalized = true;

  node->local.finalized = true;

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

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

  if (node->nested)

  if (node->nested)

    lower_nested_functions (decl);

    lower_nested_functions (decl);

  gcc_assert (!node->nested);

  gcc_assert (!node->nested);

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

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

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

  if (!flag_unit_at_a_time)

  if (!flag_unit_at_a_time)

    {

    {

      cgraph_analyze_function (node);

      cgraph_analyze_function (node);

      cgraph_decide_inlining_incrementally (node, false);

      cgraph_decide_inlining_incrementally (node, false);

    }

    }

  if (decide_is_function_needed (node, decl))

  if (decide_is_function_needed (node, decl))

    cgraph_mark_needed_node (node);

    cgraph_mark_needed_node (node);

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

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

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

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

     there.  */

     there.  */

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

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

    cgraph_mark_reachable_node (node);

    cgraph_mark_reachable_node (node);

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

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

     to be reachable at this time.  */

     to be reachable at this time.  */

  if (!nested)

  if (!nested)

    {

    {

      if (!cgraph_assemble_pending_functions ())

      if (!cgraph_assemble_pending_functions ())

        ggc_collect ();

        ggc_collect ();

    }

    }

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

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

  if (!TREE_ASM_WRITTEN (decl))

  if (!TREE_ASM_WRITTEN (decl))

    (*debug_hooks->deferred_inline_function) (decl);

    (*debug_hooks->deferred_inline_function) (decl);

  /* Possibly warn about unused parameters.  */

  /* Possibly warn about unused parameters.  */

  if (warn_unused_parameter)

  if (warn_unused_parameter)

    do_warn_unused_parameter (decl);

    do_warn_unused_parameter (decl);

}

}

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

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

static tree

static tree

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

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

{

{

  tree t = *tp;

  tree t = *tp;

  switch (TREE_CODE (t))

  switch (TREE_CODE (t))

    {

    {

    case VAR_DECL:

    case VAR_DECL:

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

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

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

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

         after rtl has been generated.  */

         after rtl has been generated.  */

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

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

        {

        {

          cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));

          cgraph_varpool_mark_needed_node (cgraph_varpool_node (t));

          if (lang_hooks.callgraph.analyze_expr)

          if (lang_hooks.callgraph.analyze_expr)

            return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees,

            return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees,

                                                      data);

                                                      data);

        }

        }

      break;

      break;

    case FDESC_EXPR:

    case FDESC_EXPR:

    case ADDR_EXPR:

    case ADDR_EXPR:

      if (flag_unit_at_a_time)

      if (flag_unit_at_a_time)

        {

        {

          /* Record dereferences to the functions.  This makes the

          /* Record dereferences to the functions.  This makes the

             functions reachable unconditionally.  */

             functions reachable unconditionally.  */

          tree decl = TREE_OPERAND (*tp, 0);

          tree decl = TREE_OPERAND (*tp, 0);

          if (TREE_CODE (decl) == FUNCTION_DECL)

          if (TREE_CODE (decl) == FUNCTION_DECL)

            cgraph_mark_needed_node (cgraph_node (decl));

            cgraph_mark_needed_node (cgraph_node (decl));

        }

        }

      break;

      break;

    default:

    default:

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

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

         won't find anything useful there anyway.  */

         won't find anything useful there anyway.  */

      if (IS_TYPE_OR_DECL_P (*tp))

      if (IS_TYPE_OR_DECL_P (*tp))

        {

        {

          *walk_subtrees = 0;

          *walk_subtrees = 0;

          break;

          break;

        }

        }

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

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

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

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

      break;

      break;

    }

    }

  return NULL;

  return NULL;

}

}

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

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

static void

static void

cgraph_create_edges (struct cgraph_node *node, tree body)

cgraph_create_edges (struct cgraph_node *node, tree body)

{

{

  basic_block bb;

  basic_block bb;

  struct function *this_cfun = DECL_STRUCT_FUNCTION (body);

  struct function *this_cfun = DECL_STRUCT_FUNCTION (body);

  block_stmt_iterator bsi;

  block_stmt_iterator bsi;

  tree step;

  tree step;

  visited_nodes = pointer_set_create ();

  visited_nodes = pointer_set_create ();

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

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

     enclosing basic-blocks in the call edges.  */

     enclosing basic-blocks in the call edges.  */

  FOR_EACH_BB_FN (bb, this_cfun)

  FOR_EACH_BB_FN (bb, this_cfun)

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

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

      {

      {

        tree stmt = bsi_stmt (bsi);

        tree stmt = bsi_stmt (bsi);

        tree call = get_call_expr_in (stmt);

        tree call = get_call_expr_in (stmt);

        tree decl;

        tree decl;

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

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

          {

          {

            cgraph_create_edge (node, cgraph_node (decl), stmt,

            cgraph_create_edge (node, cgraph_node (decl), stmt,

                                bb->count,

                                bb->count,

                                bb->loop_depth);

                                bb->loop_depth);

            walk_tree (&TREE_OPERAND (call, 1),

            walk_tree (&TREE_OPERAND (call, 1),

                       record_reference, node, visited_nodes);

                       record_reference, node, visited_nodes);

            if (TREE_CODE (stmt) == MODIFY_EXPR)

            if (TREE_CODE (stmt) == MODIFY_EXPR)

              walk_tree (&TREE_OPERAND (stmt, 0),

              walk_tree (&TREE_OPERAND (stmt, 0),

                         record_reference, node, visited_nodes);

                         record_reference, node, visited_nodes);

          }

          }

        else

        else

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

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

      }

      }

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

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

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

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

       step;

       step;

       step = TREE_CHAIN (step))

       step = TREE_CHAIN (step))

    {

    {

      tree decl = TREE_VALUE (step);

      tree decl = TREE_VALUE (step);

      if (TREE_CODE (decl) == VAR_DECL

      if (TREE_CODE (decl) == VAR_DECL

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

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

          && flag_unit_at_a_time)

          && flag_unit_at_a_time)

        cgraph_varpool_finalize_decl (decl);

        cgraph_varpool_finalize_decl (decl);

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

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

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

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

    }

    }

  pointer_set_destroy (visited_nodes);

  pointer_set_destroy (visited_nodes);

  visited_nodes = NULL;

  visited_nodes = NULL;

}

}

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

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

   either NULLified or usually overwritten by more precise reason

   either NULLified or usually overwritten by more precise reason

   later.  */

   later.  */

static void

static void