Subversion Repositories openrisc_me

/* Callgraph based interprocedural optimizations.

   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010

   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 3, 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 COPYING3.  If not see

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

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

   few basic interprocedural 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.)

    - 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 (source level) compilation unit is finalized

      and it will no longer change.

      In the the call-graph construction and local function

      analysis takes place here.  Bodies of unreachable functions are released

      to conserve memory usage.

      The function can be called multiple times when multiple source level

      compilation units are combined (such as in C frontend)

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

    - varpool_mark_needed_node

      When function or variable is referenced by some hidden way the call-graph

      data structure must be updated accordingly by this function.

      There should be little need to call this function and all the references

      should be made explicit to cgraph code.  At present these functions are

      used by C++ frontend to explicitly mark the keyed methods.

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

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

#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 "intl.h"

#include "function.h"

#include "ipa-prop.h"

#include "gimple.h"

#include "tree-iterator.h"

#include "tree-pass.h"

#include "tree-dump.h"

#include "output.h"

#include "coverage.h"

#include "plugin.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 void cgraph_output_pending_asms (void);

static void cgraph_analyze_function (struct cgraph_node *);

static FILE *cgraph_dump_file;

/* A vector of FUNCTION_DECLs declared as static constructors.  */

static GTY (()) VEC(tree, gc) *static_ctors;

/* A vector of FUNCTION_DECLs declared as static destructors.  */

static GTY (()) VEC(tree, gc) *static_dtors;

/* Used for vtable lookup in thunk adjusting.  */

static GTY (()) tree vtable_entry_type;

/* When target does not have ctors and dtors, we call all constructor

   and destructor by special initialization/destruction function

   recognized by collect2.

   When we are going to build this function, collect all constructors and

   destructors and turn them into normal functions.  */

static void

record_cdtor_fn (tree fndecl)

{

  struct cgraph_node *node;

  if (targetm.have_ctors_dtors

      || (!DECL_STATIC_CONSTRUCTOR (fndecl)

          && !DECL_STATIC_DESTRUCTOR (fndecl)))

    return;

  if (DECL_STATIC_CONSTRUCTOR (fndecl))

    {

      VEC_safe_push (tree, gc, static_ctors, fndecl);

      DECL_STATIC_CONSTRUCTOR (fndecl) = 0;

    }

  if (DECL_STATIC_DESTRUCTOR (fndecl))

    {

      VEC_safe_push (tree, gc, static_dtors, fndecl);

      DECL_STATIC_DESTRUCTOR (fndecl) = 0;

    }

  node = cgraph_node (fndecl);

  node->local.disregard_inline_limits = 1;

  cgraph_mark_reachable_node (node);

}

/* Define global constructors/destructor functions for the CDTORS, of

   which they are LEN.  The CDTORS are sorted by initialization

   priority.  If CTOR_P is true, these are constructors; otherwise,

   they are destructors.  */

static void

build_cdtor (bool ctor_p, tree *cdtors, size_t len)

{

  size_t i;

  i = 0;

  while (i < len)

    {

      tree body;

      tree fn;

      priority_type priority;

      priority = 0;

      body = NULL_TREE;

      /* Find the next batch of constructors/destructors with the same

         initialization priority.  */

      do

        {

          priority_type p;

          fn = cdtors[i];

          p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);

          if (!body)

            priority = p;

          else if (p != priority)

            break;

          append_to_statement_list (build_function_call_expr (UNKNOWN_LOCATION,

                                                              fn, 0),

                                    &body);

          ++i;

        }

      while (i < len);

      gcc_assert (body != NULL_TREE);

      /* Generate a function to call all the function of like

         priority.  */

      cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);

    }

}

/* Comparison function for qsort.  P1 and P2 are actually of type

   "tree *" and point to static constructors.  DECL_INIT_PRIORITY is

   used to determine the sort order.  */

static int

compare_ctor (const void *p1, const void *p2)

{

  tree f1;

  tree f2;

  int priority1;

  int priority2;

  f1 = *(const tree *)p1;

  f2 = *(const tree *)p2;

  priority1 = DECL_INIT_PRIORITY (f1);

  priority2 = DECL_INIT_PRIORITY (f2);

  if (priority1 < priority2)

    return -1;

  else if (priority1 > priority2)

    return 1;

  else

    /* Ensure a stable sort.  */

    return (const tree *)p1 - (const tree *)p2;

}

/* Comparison function for qsort.  P1 and P2 are actually of type

   "tree *" and point to static destructors.  DECL_FINI_PRIORITY is

   used to determine the sort order.  */

static int

compare_dtor (const void *p1, const void *p2)

{

  tree f1;

  tree f2;

  int priority1;

  int priority2;

  f1 = *(const tree *)p1;

  f2 = *(const tree *)p2;

  priority1 = DECL_FINI_PRIORITY (f1);

  priority2 = DECL_FINI_PRIORITY (f2);

  if (priority1 < priority2)

    return -1;

  else if (priority1 > priority2)

    return 1;

  else

    /* Ensure a stable sort.  */

    return (const tree *)p1 - (const tree *)p2;

}

/* Generate functions to call static constructors and destructors

   for targets that do not support .ctors/.dtors sections.  These

   functions have magic names which are detected by collect2.  */

static void

cgraph_build_cdtor_fns (void)

{

  if (!VEC_empty (tree, static_ctors))

    {

      gcc_assert (!targetm.have_ctors_dtors);

      qsort (VEC_address (tree, static_ctors),

             VEC_length (tree, static_ctors),

             sizeof (tree),

             compare_ctor);

      build_cdtor (/*ctor_p=*/true,

                   VEC_address (tree, static_ctors),

                   VEC_length (tree, static_ctors));

      VEC_truncate (tree, static_ctors, 0);

    }

  if (!VEC_empty (tree, static_dtors))

    {

      gcc_assert (!targetm.have_ctors_dtors);

      qsort (VEC_address (tree, static_dtors),

             VEC_length (tree, static_dtors),

             sizeof (tree),

             compare_dtor);

      build_cdtor (/*ctor_p=*/false,

                   VEC_address (tree, static_dtors),

                   VEC_length (tree, static_dtors));

      VEC_truncate (tree, static_dtors, 0);

    }

}

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

   either outside this translation unit, something magic in the system

   configury.  */

bool

cgraph_decide_is_function_needed (struct cgraph_node *node, tree decl)

{

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

  if (node->local.externally_visible)

    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;

  /* With -fkeep-inline-functions we are keeping all inline functions except

     for extern inline ones.  */

  if (flag_keep_inline_functions

      && DECL_DECLARED_INLINE_P (decl)

      && !DECL_EXTERNAL (decl)

      && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (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.

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

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

     declared inline and nested functions.  These was optimized out

     in the original implementation and it is unclear whether we want

     to change the behavior here.  */

  if (((TREE_PUBLIC (decl)

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

            && !DECL_DECLARED_INLINE_P (decl)

            && !node->origin))

       && !flag_whole_program

       && !flag_lto

       && !flag_whopr)

      && !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;

  return false;

}

/* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these

   functions into callgraph in a way so they look like ordinary reachable

   functions inserted into callgraph already at construction time.  */

bool

cgraph_process_new_functions (void)

{

  bool output = false;

  tree fndecl;

  struct cgraph_node *node;

  /*  Note that this queue may grow as its being processed, as the new

      functions may generate new ones.  */

  while (cgraph_new_nodes)

    {

      node = cgraph_new_nodes;

      fndecl = node->decl;

      cgraph_new_nodes = cgraph_new_nodes->next_needed;

      switch (cgraph_state)

        {

        case CGRAPH_STATE_CONSTRUCTION:

          /* At construction time we just need to finalize function and move

             it into reachable functions list.  */

          node->next_needed = NULL;

          cgraph_finalize_function (fndecl, false);

          cgraph_mark_reachable_node (node);

          output = true;

          break;

        case CGRAPH_STATE_IPA:

        case CGRAPH_STATE_IPA_SSA:

          /* When IPA optimization already started, do all essential

             transformations that has been already performed on the whole

             cgraph but not on this function.  */

          gimple_register_cfg_hooks ();

          if (!node->analyzed)

            cgraph_analyze_function (node);

          push_cfun (DECL_STRUCT_FUNCTION (fndecl));

          current_function_decl = fndecl;

          compute_inline_parameters (node);

          if ((cgraph_state == CGRAPH_STATE_IPA_SSA

              && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))

              /* When not optimizing, be sure we run early local passes anyway

                 to expand OMP.  */

              || !optimize)

            execute_pass_list (pass_early_local_passes.pass.sub);

          free_dominance_info (CDI_POST_DOMINATORS);

          free_dominance_info (CDI_DOMINATORS);

          pop_cfun ();

          current_function_decl = NULL;

          break;

        case CGRAPH_STATE_EXPANSION:

          /* Functions created during expansion shall be compiled

             directly.  */

          node->process = 0;

          cgraph_expand_function (node);

          break;

        default:

          gcc_unreachable ();

          break;

        }

      cgraph_call_function_insertion_hooks (node);

    }

  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->process is set, then 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->process);

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

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

     a re-declaration in IMA mode.  */

  if (node->reachable)

    {

      struct cgraph_node *n;

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

        if (n == node)

          break;

      if (!n)

        node->reachable = 0;

    }

}

static void

cgraph_lower_function (struct cgraph_node *node)

{

  if (node->lowered)

    return;

  if (node->nested)

    lower_nested_functions (node->decl);

  gcc_assert (!node->nested);

  tree_lowering_passes (node->decl);

  node->lowered = true;

}

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

  node->pid = cgraph_max_pid ++;

  notice_global_symbol (decl);

  node->local.finalized = true;

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

  node->finalized_by_frontend = true;

  record_cdtor_fn (node->decl);

  if (cgraph_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 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);

  if (!nested)

    ggc_collect ();

}

/* C99 extern inline keywords allow changing of declaration after function

   has been finalized.  We need to re-decide if we want to mark the function as

   needed then.   */

void

cgraph_mark_if_needed (tree decl)

{

  struct cgraph_node *node = cgraph_node (decl);

  if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))

    cgraph_mark_needed_node (node);

}

/* Return TRUE if NODE2 is equivalent to NODE or its clone.  */

static bool

clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)

{

  while (node != node2 && node2)

    node2 = node2->clone_of;

  return node2 != NULL;

}

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

void

verify_cgraph_node (struct cgraph_node *node)

{

  struct cgraph_edge *e;

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

  struct function *saved_cfun = cfun;

  basic_block this_block;

  gimple_stmt_iterator gsi;

  bool error_found = false;

  if (errorcount || sorrycount)

    return;

  timevar_push (TV_CGRAPH_VERIFY);

  /* debug_generic_stmt needs correct cfun */

  set_cfun (this_cfun);

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

    if (e->aux)

      {

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

               identifier_to_locale (cgraph_node_name (e->caller)),

               identifier_to_locale (cgraph_node_name (e->callee)));

        error_found = true;

      }

  if (node->count < 0)

    {

      error ("Execution count is negative");

      error_found = true;

    }

  if (node->global.inlined_to && node->local.externally_visible)

    {

      error ("Externally visible inline clone");

      error_found = true;

    }

  if (node->global.inlined_to && node->address_taken)

    {

      error ("Inline clone with address taken");

      error_found = true;

    }

  if (node->global.inlined_to && node->needed)

    {

      error ("Inline clone is needed");

      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->frequency < 0)

        {

          error ("caller edge frequency is negative");

          error_found = true;

        }

      if (e->frequency > CGRAPH_FREQ_MAX)

        {

          error ("caller edge frequency is too large");

          error_found = true;

        }

      if (gimple_has_body_p (e->caller->decl)

          && !e->caller->global.inlined_to

          && (e->frequency

              != compute_call_stmt_bb_frequency (e->caller->decl,

                                                 gimple_bb (e->call_stmt))))

        {

          error ("caller edge frequency %i does not match BB freqency %i",

                 e->frequency,

                 compute_call_stmt_bb_frequency (e->caller->decl,

                                                 gimple_bb (e->call_stmt)));

          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 predecessors found");

      error_found = true;

    }

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

    {

      error ("inlined_to pointer refers to itself");

      error_found = true;

    }

  if (!cgraph_node (node->decl))

    {

      error ("node not found in cgraph_hash");

      error_found = true;

    }

  if (node->clone_of)

    {

      struct cgraph_node *n;

      for (n = node->clone_of->clones; n; n = n->next_sibling_clone)

        if (n == node)

          break;

      if (!n)

        {

          error ("node has wrong clone_of");

          error_found = true;

        }

    }

  if (node->clones)

    {

      struct cgraph_node *n;

      for (n = node->clones; n; n = n->next_sibling_clone)

        if (n->clone_of != node)

          break;

      if (n)

        {

          error ("node has wrong clone list");

          error_found = true;

        }

    }

  if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)

    {

       error ("node is in clone list but it is not clone");

       error_found = true;

    }

  if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)

    {

      error ("node has wrong prev_clone pointer");

      error_found = true;

    }

  if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)

    {

      error ("double linked list of clones corrupted");

      error_found = true;

    }

  if (node->same_comdat_group)

    {

      struct cgraph_node *n = node->same_comdat_group;