Subversion Repositories openrisc

/* Function splitting pass

   Copyright (C) 2010, 2011, 2012

   Free Software Foundation, Inc.

   Contributed by Jan Hubicka  <jh@suse.cz>

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

/* The purpose of this pass is to split function bodies to improve

   inlining.  I.e. for function of the form:

   func (...)

     {

       if (cheap_test)

         something_small

       else

         something_big

     }

   Produce:

   func.part (...)

     {

        something_big

     }

   func (...)

     {

       if (cheap_test)

         something_small

       else

         func.part (...);

     }

   When func becomes inlinable and when cheap_test is often true, inlining func,

   but not fund.part leads to performance improvement similar as inlining

   original func while the code size growth is smaller.

   The pass is organized in three stages:

   1) Collect local info about basic block into BB_INFO structure and

      compute function body estimated size and time.

   2) Via DFS walk find all possible basic blocks where we can split

      and chose best one.

   3) If split point is found, split at the specified BB by creating a clone

      and updating function to call it.

   The decisions what functions to split are in execute_split_functions

   and consider_split.

   There are several possible future improvements for this pass including:

   1) Splitting to break up large functions

   2) Splitting to reduce stack frame usage

   3) Allow split part of function to use values computed in the header part.

      The values needs to be passed to split function, perhaps via same

      interface as for nested functions or as argument.

   4) Support for simple rematerialization.  I.e. when split part use

      value computed in header from function parameter in very cheap way, we

      can just recompute it.

   5) Support splitting of nested functions.

   6) Support non-SSA arguments.

   7) There is nothing preventing us from producing multiple parts of single function

      when needed or splitting also the parts.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tree.h"

#include "target.h"

#include "cgraph.h"

#include "ipa-prop.h"

#include "tree-flow.h"

#include "tree-pass.h"

#include "flags.h"

#include "timevar.h"

#include "diagnostic.h"

#include "tree-dump.h"

#include "tree-inline.h"

#include "fibheap.h"

#include "params.h"

#include "gimple-pretty-print.h"

#include "ipa-inline.h"

/* Per basic block info.  */

typedef struct

{

  unsigned int size;

  unsigned int time;

} bb_info;

DEF_VEC_O(bb_info);

DEF_VEC_ALLOC_O(bb_info,heap);

static VEC(bb_info, heap) *bb_info_vec;

/* Description of split point.  */

struct split_point

{

  /* Size of the partitions.  */

  unsigned int header_time, header_size, split_time, split_size;

  /* SSA names that need to be passed into spit function.  */

  bitmap ssa_names_to_pass;

  /* Basic block where we split (that will become entry point of new function.  */

  basic_block entry_bb;

  /* Basic blocks we are splitting away.  */

  bitmap split_bbs;

  /* True when return value is computed on split part and thus it needs

     to be returned.  */

  bool split_part_set_retval;

};

/* Best split point found.  */

struct split_point best_split_point;

/* Set of basic blocks that are not allowed to dominate a split point.  */

static bitmap forbidden_dominators;

static tree find_retval (basic_block return_bb);

/* Callback for walk_stmt_load_store_addr_ops.  If T is non-SSA automatic

   variable, check it if it is present in bitmap passed via DATA.  */

static bool

test_nonssa_use (gimple stmt ATTRIBUTE_UNUSED, tree t, void *data)

{

  t = get_base_address (t);

  if (!t || is_gimple_reg (t))

    return false;

  if (TREE_CODE (t) == PARM_DECL

      || (TREE_CODE (t) == VAR_DECL

          && auto_var_in_fn_p (t, current_function_decl))

      || TREE_CODE (t) == RESULT_DECL

      || TREE_CODE (t) == LABEL_DECL)

    return bitmap_bit_p ((bitmap)data, DECL_UID (t));

  /* For DECL_BY_REFERENCE, the return value is actually a pointer.  We want

     to pretend that the value pointed to is actual result decl.  */

  if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))

      && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME

      && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL

      && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))

    return

      bitmap_bit_p ((bitmap)data,

                    DECL_UID (DECL_RESULT (current_function_decl)));

  return false;

}

/* Dump split point CURRENT.  */

static void

dump_split_point (FILE * file, struct split_point *current)

{

  fprintf (file,

           "Split point at BB %i\n"

           "  header time: %i header size: %i\n"

           "  split time: %i split size: %i\n  bbs: ",

           current->entry_bb->index, current->header_time,

           current->header_size, current->split_time, current->split_size);

  dump_bitmap (file, current->split_bbs);

  fprintf (file, "  SSA names to pass: ");

  dump_bitmap (file, current->ssa_names_to_pass);

}

/* Look for all BBs in header that might lead to the split part and verify

   that they are not defining any non-SSA var used by the split part.

   Parameters are the same as for consider_split.  */

static bool

verify_non_ssa_vars (struct split_point *current, bitmap non_ssa_vars,

                     basic_block return_bb)

{

  bitmap seen = BITMAP_ALLOC (NULL);

  VEC (basic_block,heap) *worklist = NULL;

  edge e;

  edge_iterator ei;

  bool ok = true;

  FOR_EACH_EDGE (e, ei, current->entry_bb->preds)

    if (e->src != ENTRY_BLOCK_PTR

        && !bitmap_bit_p (current->split_bbs, e->src->index))

      {

        VEC_safe_push (basic_block, heap, worklist, e->src);

        bitmap_set_bit (seen, e->src->index);

      }

  while (!VEC_empty (basic_block, worklist))

    {

      gimple_stmt_iterator bsi;

      basic_block bb = VEC_pop (basic_block, worklist);

      FOR_EACH_EDGE (e, ei, bb->preds)

        if (e->src != ENTRY_BLOCK_PTR

            && bitmap_set_bit (seen, e->src->index))

          {

            gcc_checking_assert (!bitmap_bit_p (current->split_bbs,

                                                e->src->index));

            VEC_safe_push (basic_block, heap, worklist, e->src);

          }

      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))

        {

          gimple stmt = gsi_stmt (bsi);

          if (is_gimple_debug (stmt))

            continue;

          if (walk_stmt_load_store_addr_ops

              (stmt, non_ssa_vars, test_nonssa_use, test_nonssa_use,

               test_nonssa_use))

            {

              ok = false;

              goto done;

            }

          if (gimple_code (stmt) == GIMPLE_LABEL

              && test_nonssa_use (stmt, gimple_label_label (stmt),

                                  non_ssa_vars))

          {

            ok = false;

            goto done;

          }

        }

      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))

        {

          if (walk_stmt_load_store_addr_ops

              (gsi_stmt (bsi), non_ssa_vars, test_nonssa_use, test_nonssa_use,

               test_nonssa_use))

            {

              ok = false;

              goto done;

            }

        }

      FOR_EACH_EDGE (e, ei, bb->succs)

        {

          if (e->dest != return_bb)

            continue;

          for (bsi = gsi_start_phis (return_bb); !gsi_end_p (bsi);

               gsi_next (&bsi))

            {

              gimple stmt = gsi_stmt (bsi);

              tree op = gimple_phi_arg_def (stmt, e->dest_idx);

              if (!is_gimple_reg (gimple_phi_result (stmt)))

                continue;

              if (TREE_CODE (op) != SSA_NAME

                  && test_nonssa_use (stmt, op, non_ssa_vars))

                {

                  ok = false;

                  goto done;

                }

            }

        }

    }

done:

  BITMAP_FREE (seen);

  VEC_free (basic_block, heap, worklist);

  return ok;

}

/* If STMT is a call, check the callee against a list of forbidden

   predicate functions.  If a match is found, look for uses of the

   call result in condition statements that compare against zero.

   For each such use, find the block targeted by the condition

   statement for the nonzero result, and set the bit for this block

   in the forbidden dominators bitmap.  The purpose of this is to avoid

   selecting a split point where we are likely to lose the chance

   to optimize away an unused function call.  */

static void

check_forbidden_calls (gimple stmt)

{

  imm_use_iterator use_iter;

  use_operand_p use_p;

  tree lhs;

  /* At the moment, __builtin_constant_p is the only forbidden

     predicate function call (see PR49642).  */

  if (!gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))

    return;

  lhs = gimple_call_lhs (stmt);

  if (!lhs || TREE_CODE (lhs) != SSA_NAME)

    return;

  FOR_EACH_IMM_USE_FAST (use_p, use_iter, lhs)

    {

      tree op1;

      basic_block use_bb, forbidden_bb;

      enum tree_code code;

      edge true_edge, false_edge;

      gimple use_stmt = USE_STMT (use_p);

      if (gimple_code (use_stmt) != GIMPLE_COND)

        continue;

      /* Assuming canonical form for GIMPLE_COND here, with constant

         in second position.  */

      op1 = gimple_cond_rhs (use_stmt);

      code = gimple_cond_code (use_stmt);

      use_bb = gimple_bb (use_stmt);

      extract_true_false_edges_from_block (use_bb, &true_edge, &false_edge);

      /* We're only interested in comparisons that distinguish

         unambiguously from zero.  */

      if (!integer_zerop (op1) || code == LE_EXPR || code == GE_EXPR)

        continue;

      if (code == EQ_EXPR)

        forbidden_bb = false_edge->dest;

      else

        forbidden_bb = true_edge->dest;

      bitmap_set_bit (forbidden_dominators, forbidden_bb->index);

    }

}

/* If BB is dominated by any block in the forbidden dominators set,

   return TRUE; else FALSE.  */

static bool

dominated_by_forbidden (basic_block bb)

{

  unsigned dom_bb;

  bitmap_iterator bi;

  EXECUTE_IF_SET_IN_BITMAP (forbidden_dominators, 1, dom_bb, bi)

    {

      if (dominated_by_p (CDI_DOMINATORS, bb, BASIC_BLOCK (dom_bb)))

        return true;

    }

  return false;

}

/* We found an split_point CURRENT.  NON_SSA_VARS is bitmap of all non ssa

   variables used and RETURN_BB is return basic block.

   See if we can split function here.  */

static void

consider_split (struct split_point *current, bitmap non_ssa_vars,

                basic_block return_bb)

{

  tree parm;

  unsigned int num_args = 0;

  unsigned int call_overhead;

  edge e;

  edge_iterator ei;

  gimple_stmt_iterator bsi;

  unsigned int i;

  int incoming_freq = 0;

  tree retval;

  if (dump_file && (dump_flags & TDF_DETAILS))

    dump_split_point (dump_file, current);

  FOR_EACH_EDGE (e, ei, current->entry_bb->preds)

    if (!bitmap_bit_p (current->split_bbs, e->src->index))

      incoming_freq += EDGE_FREQUENCY (e);

  /* Do not split when we would end up calling function anyway.  */

  if (incoming_freq

      >= (ENTRY_BLOCK_PTR->frequency

          * PARAM_VALUE (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY) / 100))

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file,

                 "  Refused: incoming frequency is too large.\n");

      return;

    }

  if (!current->header_size)

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file, "  Refused: header empty\n");

      return;

    }

  /* Verify that PHI args on entry are either virtual or all their operands

     incoming from header are the same.  */

  for (bsi = gsi_start_phis (current->entry_bb); !gsi_end_p (bsi); gsi_next (&bsi))

    {

      gimple stmt = gsi_stmt (bsi);

      tree val = NULL;

      if (!is_gimple_reg (gimple_phi_result (stmt)))

        continue;

      for (i = 0; i < gimple_phi_num_args (stmt); i++)

        {

          edge e = gimple_phi_arg_edge (stmt, i);

          if (!bitmap_bit_p (current->split_bbs, e->src->index))

            {

              tree edge_val = gimple_phi_arg_def (stmt, i);

              if (val && edge_val != val)

                {

                  if (dump_file && (dump_flags & TDF_DETAILS))

                    fprintf (dump_file,

                             "  Refused: entry BB has PHI with multiple variants\n");

                  return;

                }

              val = edge_val;

            }

        }

    }

  /* See what argument we will pass to the split function and compute

     call overhead.  */

  call_overhead = eni_size_weights.call_cost;

  for (parm = DECL_ARGUMENTS (current_function_decl); parm;

       parm = DECL_CHAIN (parm))

    {

      if (!is_gimple_reg (parm))

        {

          if (bitmap_bit_p (non_ssa_vars, DECL_UID (parm)))

            {

              if (dump_file && (dump_flags & TDF_DETAILS))

                fprintf (dump_file,

                         "  Refused: need to pass non-ssa param values\n");

              return;

            }

        }

      else if (gimple_default_def (cfun, parm)

               && bitmap_bit_p (current->ssa_names_to_pass,

                                SSA_NAME_VERSION (gimple_default_def

                                                  (cfun, parm))))

        {

          if (!VOID_TYPE_P (TREE_TYPE (parm)))

            call_overhead += estimate_move_cost (TREE_TYPE (parm));

          num_args++;

        }

    }

  if (!VOID_TYPE_P (TREE_TYPE (current_function_decl)))

    call_overhead += estimate_move_cost (TREE_TYPE (current_function_decl));

  if (current->split_size <= call_overhead)

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file,

                 "  Refused: split size is smaller than call overhead\n");

      return;

    }

  if (current->header_size + call_overhead

      >= (unsigned int)(DECL_DECLARED_INLINE_P (current_function_decl)

                        ? MAX_INLINE_INSNS_SINGLE

                        : MAX_INLINE_INSNS_AUTO))

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file,

                 "  Refused: header size is too large for inline candidate\n");

      return;

    }

  /* FIXME: we currently can pass only SSA function parameters to the split

     arguments.  Once parm_adjustment infrastructure is supported by cloning,

     we can pass more than that.  */

  if (num_args != bitmap_count_bits (current->ssa_names_to_pass))

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file,

                 "  Refused: need to pass non-param values\n");

      return;

    }

  /* When there are non-ssa vars used in the split region, see if they

     are used in the header region.  If so, reject the split.

     FIXME: we can use nested function support to access both.  */

  if (!bitmap_empty_p (non_ssa_vars)

      && !verify_non_ssa_vars (current, non_ssa_vars, return_bb))

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file,

                 "  Refused: split part has non-ssa uses\n");

      return;

    }

  /* If the split point is dominated by a forbidden block, reject

     the split.  */

  if (!bitmap_empty_p (forbidden_dominators)

      && dominated_by_forbidden (current->entry_bb))

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file,

                 "  Refused: split point dominated by forbidden block\n");

      return;

    }

  /* See if retval used by return bb is computed by header or split part.

     When it is computed by split part, we need to produce return statement

     in the split part and add code to header to pass it around.

     This is bit tricky to test:

       1) When there is no return_bb or no return value, we always pass

          value around.

       2) Invariants are always computed by caller.

       3) For SSA we need to look if defining statement is in header or split part

       4) For non-SSA we need to look where the var is computed. */

  retval = find_retval (return_bb);

  if (!retval)

    current->split_part_set_retval = true;

  else if (is_gimple_min_invariant (retval))

    current->split_part_set_retval = false;

  /* Special case is value returned by reference we record as if it was non-ssa

     set to result_decl.  */

  else if (TREE_CODE (retval) == SSA_NAME

           && TREE_CODE (SSA_NAME_VAR (retval)) == RESULT_DECL

           && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))

    current->split_part_set_retval

       = bitmap_bit_p (non_ssa_vars, DECL_UID (SSA_NAME_VAR (retval)));

  else if (TREE_CODE (retval) == SSA_NAME)

    current->split_part_set_retval

      = (!SSA_NAME_IS_DEFAULT_DEF (retval)

         && (bitmap_bit_p (current->split_bbs,

                          gimple_bb (SSA_NAME_DEF_STMT (retval))->index)

             || gimple_bb (SSA_NAME_DEF_STMT (retval)) == return_bb));

  else if (TREE_CODE (retval) == PARM_DECL)

    current->split_part_set_retval = false;

  else if (TREE_CODE (retval) == VAR_DECL

           || TREE_CODE (retval) == RESULT_DECL)

    current->split_part_set_retval

      = bitmap_bit_p (non_ssa_vars, DECL_UID (retval));

  else

    current->split_part_set_retval = true;

  /* split_function fixes up at most one PHI non-virtual PHI node in return_bb,

     for the return value.  If there are other PHIs, give up.  */

  if (return_bb != EXIT_BLOCK_PTR)

    {

      gimple_stmt_iterator psi;

      for (psi = gsi_start_phis (return_bb); !gsi_end_p (psi); gsi_next (&psi))

        if (is_gimple_reg (gimple_phi_result (gsi_stmt (psi)))

            && !(retval

                 && current->split_part_set_retval

                 && TREE_CODE (retval) == SSA_NAME

                 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))

                 && SSA_NAME_DEF_STMT (retval) == gsi_stmt (psi)))

          {

            if (dump_file && (dump_flags & TDF_DETAILS))

              fprintf (dump_file,

                       "  Refused: return bb has extra PHIs\n");

            return;

          }

    }

  if (dump_file && (dump_flags & TDF_DETAILS))

    fprintf (dump_file, "  Accepted!\n");

  /* At the moment chose split point with lowest frequency and that leaves

     out smallest size of header.

     In future we might re-consider this heuristics.  */

  if (!best_split_point.split_bbs

      || best_split_point.entry_bb->frequency > current->entry_bb->frequency

      || (best_split_point.entry_bb->frequency == current->entry_bb->frequency

          && best_split_point.split_size < current->split_size))

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file, "  New best split point!\n");

      if (best_split_point.ssa_names_to_pass)

        {

          BITMAP_FREE (best_split_point.ssa_names_to_pass);

          BITMAP_FREE (best_split_point.split_bbs);

        }

      best_split_point = *current;

      best_split_point.ssa_names_to_pass = BITMAP_ALLOC (NULL);

      bitmap_copy (best_split_point.ssa_names_to_pass,

                   current->ssa_names_to_pass);

      best_split_point.split_bbs = BITMAP_ALLOC (NULL);

      bitmap_copy (best_split_point.split_bbs, current->split_bbs);

    }

}

/* Return basic block containing RETURN statement.  We allow basic blocks

   of the form:

   <retval> = tmp_var;

   return <retval>

   but return_bb can not be more complex than this.

   If nothing is found, return EXIT_BLOCK_PTR.

   When there are multiple RETURN statement, chose one with return value,

   since that one is more likely shared by multiple code paths.

   Return BB is special, because for function splitting it is the only

   basic block that is duplicated in between header and split part of the

   function.

   TODO: We might support multiple return blocks.  */

static basic_block

find_return_bb (void)

{

  edge e;

  basic_block return_bb = EXIT_BLOCK_PTR;

  gimple_stmt_iterator bsi;

  bool found_return = false;

  tree retval = NULL_TREE;

  if (!single_pred_p (EXIT_BLOCK_PTR))

    return return_bb;

  e = single_pred_edge (EXIT_BLOCK_PTR);

  for (bsi = gsi_last_bb (e->src); !gsi_end_p (bsi); gsi_prev (&bsi))

    {

      gimple stmt = gsi_stmt (bsi);

      if (gimple_code (stmt) == GIMPLE_LABEL

          || is_gimple_debug (stmt)

          || gimple_clobber_p (stmt))

        ;

      else if (gimple_code (stmt) == GIMPLE_ASSIGN

               && found_return

               && gimple_assign_single_p (stmt)

               && (auto_var_in_fn_p (gimple_assign_rhs1 (stmt),

                                     current_function_decl)

                   || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))

               && retval == gimple_assign_lhs (stmt))

        ;

      else if (gimple_code (stmt) == GIMPLE_RETURN)

        {

          found_return = true;

          retval = gimple_return_retval (stmt);

        }

      else

        break;

    }

  if (gsi_end_p (bsi) && found_return)

    return_bb = e->src;

  return return_bb;

}

/* Given return basic block RETURN_BB, see where return value is really

   stored.  */

static tree

find_retval (basic_block return_bb)

{

  gimple_stmt_iterator bsi;

  for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))

    if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)

      return gimple_return_retval (gsi_stmt (bsi));

    else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN

             && !gimple_clobber_p (gsi_stmt (bsi)))

      return gimple_assign_rhs1 (gsi_stmt (bsi));

  return NULL;

}

/* Callback for walk_stmt_load_store_addr_ops.  If T is non-SSA automatic

   variable, mark it as used in bitmap passed via DATA.

   Return true when access to T prevents splitting the function.  */

static bool

mark_nonssa_use (gimple stmt ATTRIBUTE_UNUSED, tree t, void *data)

{

  t = get_base_address (t);

  if (!t || is_gimple_reg (t))

    return false;

  /* At present we can't pass non-SSA arguments to split function.

     FIXME: this can be relaxed by passing references to arguments.  */

  if (TREE_CODE (t) == PARM_DECL)

    {

      if (dump_file && (dump_flags & TDF_DETAILS))

        fprintf (dump_file,

                 "Cannot split: use of non-ssa function parameter.\n");

      return true;

    }

  if ((TREE_CODE (t) == VAR_DECL

       && auto_var_in_fn_p (t, current_function_decl))

      || TREE_CODE (t) == RESULT_DECL

      || TREE_CODE (t) == LABEL_DECL)

    bitmap_set_bit ((bitmap)data, DECL_UID (t));

  /* For DECL_BY_REFERENCE, the return value is actually a pointer.  We want

     to pretend that the value pointed to is actual result decl.  */

  if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))

      && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME

      && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL