gcc/ipa-split.c

   1 /* Function splitting pass
   2    Copyright (C) 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Jan Hubicka  <jh@suse.cz>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* The purpose of this pass is to split function bodies to improve
  23    inlining.  I.e. for function of the form:
  24
  25    func (...)
  26      {
  27        if (cheap_test)
  28          something_small
  29        else
  30          something_big
  31      }
  32
  33    Produce:
  34
  35    func.part (...)
  36      {
  37         something_big
  38      }
  39
  40    func (...)
  41      {
  42        if (cheap_test)
  43          something_small
  44        else
  45          func.part (...);
  46      }
  47
  48    When func becomes inlinable and when cheap_test is often true, inlining func,
  49    but not fund.part leads to performance imrovement similar as inlining
  50    original func while the code size growth is smaller.
  51
  52    The pass is organized in three stages:
  53    1) Collect local info about basic block into BB_INFO structure and
  54       compute function body estimated size and time.
  55    2) Via DFS walk find all possible basic blocks where we can split
  56       and chose best one.
  57    3) If split point is found, split at the specified BB by creating a clone
  58       and updating function to call it.
  59
  60    The decisions what functions to split are in execute_split_functions
  61    and consider_split.
  62
  63    There are several possible future improvements for this pass including:
  64
  65    1) Splitting to break up large functions
  66    2) Splitting to reduce stack frame usage
  67    3) Allow split part of function to use values computed in the header part.
  68       The values needs to be passed to split function, perhaps via same
  69       interface as for nested functions or as argument.
  70    4) Support for simple rematerialization.  I.e. when split part use
  71       value computed in header from function parameter in very cheap way, we
  72       can just recompute it.
  73    5) Support splitting of nested functions.
  74    6) Support non-SSA arguments.
  75    7) There is nothing preventing us from producing multiple parts of single function
  76       when needed or splitting also the parts.  */
  77
  78 #include "config.h"
  79 #include "system.h"
  80 #include "coretypes.h"
  81 #include "tree.h"
  82 #include "target.h"
  83 #include "cgraph.h"
  84 #include "ipa-prop.h"
  85 #include "tree-flow.h"
  86 #include "tree-pass.h"
  87 #include "flags.h"
  88 #include "timevar.h"
  89 #include "diagnostic.h"
  90 #include "tree-dump.h"
  91 #include "tree-inline.h"
  92 #include "fibheap.h"
  93 #include "params.h"
  94 #include "gimple-pretty-print.h"
  95
  96 /* Per basic block info.  */
  97
  98 typedef struct
  99 {
 100   unsigned int size;
 101   unsigned int time;
 102 } bb_info;
 103 DEF_VEC_O(bb_info);
 104 DEF_VEC_ALLOC_O(bb_info,heap);
 105
 106 static VEC(bb_info, heap) *bb_info_vec;
 107
 108 /* Description of split point.  */
 109
 110 struct split_point
 111 {
 112   /* Size of the partitions.  */
 113   unsigned int header_time, header_size, split_time, split_size;
 114
 115   /* SSA names that need to be passed into spit funciton.  */
 116   bitmap ssa_names_to_pass;
 117
 118   /* Basic block where we split (that will become entry point of new function.  */
 119   basic_block entry_bb;
 120
 121   /* Basic blocks we are splitting away.  */
 122   bitmap split_bbs;
 123
 124   /* True when return value is computed on split part and thus it needs
 125      to be returned.  */
 126   bool split_part_set_retval;
 127 };
 128
 129 /* Best split point found.  */
 130
 131 struct split_point best_split_point;
 132
 133 static tree find_retval (basic_block return_bb);
 134
 135 /* Callback for walk_stmt_load_store_addr_ops.  If T is non-ssa automatic
 136    variable, check it if it is present in bitmap passed via DATA.  */
 137
 138 static bool
 139 test_nonssa_use (gimple stmt ATTRIBUTE_UNUSED, tree t,
 140                  void *data ATTRIBUTE_UNUSED)
 141 {
 142   t = get_base_address (t);
 143
 144   if (t && !is_gimple_reg (t)
 145       && ((TREE_CODE (t) == VAR_DECL
 146           && auto_var_in_fn_p (t, current_function_decl))
 147           || (TREE_CODE (t) == RESULT_DECL)
 148           || (TREE_CODE (t) == PARM_DECL)))
 149     return bitmap_bit_p ((bitmap)data, DECL_UID (t));
 150
 151   /* For DECL_BY_REFERENCE, the return value is actually pointer.  We want to pretend
 152      that the value pointed to is actual result decl.  */
 153   if (t && (TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
 154       && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
 155       && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
 156       && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
 157     return bitmap_bit_p ((bitmap)data, DECL_UID (DECL_RESULT (current_function_decl)));
 158   return false;
 159 }
 160
 161 /* Dump split point CURRENT.  */
 162
 163 static void
 164 dump_split_point (FILE * file, struct split_point *current)
 165 {
 166   fprintf (file,
 167            "Split point at BB %i header time:%i header size: %i"
 168            " split time: %i split size: %i\n  bbs: ",
 169            current->entry_bb->index, current->header_time,
 170            current->header_size, current->split_time, current->split_size);
 171   dump_bitmap (file, current->split_bbs);
 172   fprintf (file, "  SSA names to pass: ");
 173   dump_bitmap (file, current->ssa_names_to_pass);
 174 }
 175
 176 /* Look for all BBs in header that might lead to split part and verify that
 177    they are not defining any of SSA vars used by split part.
 178    Parameters are the same as for consider_split.  */
 179
 180 static bool
 181 verify_non_ssa_vars (struct split_point *current, bitmap non_ssa_vars,
 182                      basic_block return_bb)
 183 {
 184   bitmap seen = BITMAP_ALLOC (NULL);
 185   VEC (basic_block,heap) *worklist = NULL;
 186   edge e;
 187   edge_iterator ei;
 188   bool ok = true;
 189
 190   FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
 191     if (e->src != ENTRY_BLOCK_PTR
 192         && !bitmap_bit_p (current->split_bbs, e->src->index))
 193       {
 194         VEC_safe_push (basic_block, heap, worklist, e->src);
 195         bitmap_set_bit (seen, e->src->index);
 196       }
 197
 198   while (!VEC_empty (basic_block, worklist))
 199     {
 200       gimple_stmt_iterator bsi;
 201       basic_block bb = VEC_pop (basic_block, worklist);
 202
 203       FOR_EACH_EDGE (e, ei, bb->preds)
 204         if (e->src != ENTRY_BLOCK_PTR
 205             && bitmap_set_bit (seen, e->src->index))
 206           {
 207             gcc_checking_assert (!bitmap_bit_p (current->split_bbs,
 208                                                 e->src->index));
 209             VEC_safe_push (basic_block, heap, worklist, e->src);
 210           }
 211       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 212         {
 213           if (is_gimple_debug (gsi_stmt (bsi)))
 214             continue;
 215           if (walk_stmt_load_store_addr_ops
 216               (gsi_stmt (bsi), non_ssa_vars, test_nonssa_use,
 217                test_nonssa_use, test_nonssa_use))
 218             {
 219               ok = false;
 220               goto done;
 221             }
 222         }
 223       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 224         {
 225           if (walk_stmt_load_store_addr_ops
 226               (gsi_stmt (bsi), non_ssa_vars, test_nonssa_use,
 227                test_nonssa_use, test_nonssa_use))
 228             {
 229               ok = false;
 230               goto done;
 231             }
 232         }
 233       FOR_EACH_EDGE (e, ei, bb->succs)
 234         {
 235           if (e->dest != return_bb)
 236             continue;
 237           for (bsi = gsi_start_phis (return_bb); !gsi_end_p (bsi);
 238                gsi_next (&bsi))
 239             {
 240               gimple stmt = gsi_stmt (bsi);
 241               tree op = gimple_phi_arg_def (stmt, e->dest_idx);
 242
 243               if (!is_gimple_reg (gimple_phi_result (stmt)))
 244                 continue;
 245               if (TREE_CODE (op) != SSA_NAME
 246                   && test_nonssa_use (stmt, op, non_ssa_vars))
 247                 {
 248                   ok = false;
 249                   goto done;
 250                 }
 251             }
 252         }
 253     }
 254 done:
 255   BITMAP_FREE (seen);
 256   VEC_free (basic_block, heap, worklist);
 257   return ok;
 258 }
 259
 260 /* We found an split_point CURRENT.  NON_SSA_VARS is bitmap of all non ssa
 261    variables used and RETURN_BB is return basic block.
 262    See if we can split function here.  */
 263
 264 static void
 265 consider_split (struct split_point *current, bitmap non_ssa_vars,
 266                 basic_block return_bb)
 267 {
 268   tree parm;
 269   unsigned int num_args = 0;
 270   unsigned int call_overhead;
 271   edge e;
 272   edge_iterator ei;
 273   gimple_stmt_iterator bsi;
 274   unsigned int i;
 275   int incomming_freq = 0;
 276   tree retval;
 277
 278   if (dump_file && (dump_flags & TDF_DETAILS))
 279     dump_split_point (dump_file, current);
 280
 281   FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
 282     if (!bitmap_bit_p (current->split_bbs, e->src->index))
 283       incomming_freq += EDGE_FREQUENCY (e);
 284
 285   /* Do not split when we would end up calling function anyway.  */
 286   if (incomming_freq
 287       >= (ENTRY_BLOCK_PTR->frequency
 288           * PARAM_VALUE (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY) / 100))
 289     {
 290       if (dump_file && (dump_flags & TDF_DETAILS))
 291         fprintf (dump_file,
 292                  "  Refused: incomming frequency is too large.\n");
 293       return;
 294     }
 295
 296   if (!current->header_size)
 297     {
 298       if (dump_file && (dump_flags & TDF_DETAILS))
 299         fprintf (dump_file, "  Refused: header empty\n");
 300       gcc_unreachable ();
 301       return;
 302     }
 303
 304   /* Verify that PHI args on entry are either virutal or all their operands
 305      incomming from header are the same.  */
 306   for (bsi = gsi_start_phis (current->entry_bb); !gsi_end_p (bsi); gsi_next (&bsi))
 307     {
 308       gimple stmt = gsi_stmt (bsi);
 309       tree val = NULL;
 310
 311       if (!is_gimple_reg (gimple_phi_result (stmt)))
 312         continue;
 313       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 314         {
 315           edge e = gimple_phi_arg_edge (stmt, i);
 316           if (!bitmap_bit_p (current->split_bbs, e->src->index))
 317             {
 318               tree edge_val = gimple_phi_arg_def (stmt, i);
 319               if (val && edge_val != val)
 320                 {
 321                   if (dump_file && (dump_flags & TDF_DETAILS))
 322                     fprintf (dump_file,
 323                              "  Refused: entry BB has PHI with multiple variants\n");
 324                   return;
 325                 }
 326               val = edge_val;
 327             }
 328         }
 329     }
 330
 331
 332   /* See what argument we will pass to the split function and compute
 333      call overhead.  */
 334   call_overhead = eni_size_weights.call_cost;
 335   for (parm = DECL_ARGUMENTS (current_function_decl); parm;
 336        parm = DECL_CHAIN (parm))
 337     {
 338       if (!is_gimple_reg (parm))
 339         {
 340           if (bitmap_bit_p (non_ssa_vars, DECL_UID (parm)))
 341             {
 342               if (dump_file && (dump_flags & TDF_DETAILS))
 343                 fprintf (dump_file,
 344                          "  Refused: need to pass non-ssa param values\n");
 345               return;
 346             }
 347         }
 348       else if (gimple_default_def (cfun, parm)
 349                && bitmap_bit_p (current->ssa_names_to_pass,
 350                                 SSA_NAME_VERSION (gimple_default_def
 351                                                   (cfun, parm))))
 352         {
 353           if (!VOID_TYPE_P (TREE_TYPE (parm)))
 354             call_overhead += estimate_move_cost (TREE_TYPE (parm));
 355           num_args++;
 356         }
 357     }
 358   if (!VOID_TYPE_P (TREE_TYPE (current_function_decl)))
 359     call_overhead += estimate_move_cost (TREE_TYPE (current_function_decl));
 360
 361   if (current->split_size <= call_overhead)
 362     {
 363       if (dump_file && (dump_flags & TDF_DETAILS))
 364         fprintf (dump_file,
 365                  "  Refused: split size is smaller than call overhead\n");
 366       return;
 367     }
 368   if (current->header_size + call_overhead
 369       >= (unsigned int)(DECL_DECLARED_INLINE_P (current_function_decl)
 370                         ? MAX_INLINE_INSNS_SINGLE
 371                         : MAX_INLINE_INSNS_AUTO))
 372     {
 373       if (dump_file && (dump_flags & TDF_DETAILS))
 374         fprintf (dump_file,
 375                  "  Refused: header size is too large for inline candidate\n");
 376       return;
 377     }
 378
 379   /* FIXME: we currently can pass only SSA function parameters to the split
 380      arguments.  Once parm_adjustment infrastructure is supported by cloning,
 381      we can pass more than that.  */
 382   if (num_args != bitmap_count_bits (current->ssa_names_to_pass))
 383     {
 384
 385       if (dump_file && (dump_flags & TDF_DETAILS))
 386         fprintf (dump_file,
 387                  "  Refused: need to pass non-param values\n");
 388       return;
 389     }
 390
 391   /* When there are non-ssa vars used in the split region, see if they
 392      are used in the header region.  If so, reject the split.
 393      FIXME: we can use nested function support to access both.  */
 394   if (!bitmap_empty_p (non_ssa_vars)
 395       && !verify_non_ssa_vars (current, non_ssa_vars, return_bb))
 396     {
 397       if (dump_file && (dump_flags & TDF_DETAILS))
 398         fprintf (dump_file,
 399                  "  Refused: split part has non-ssa uses\n");
 400       return;
 401     }
 402   if (dump_file && (dump_flags & TDF_DETAILS))
 403     fprintf (dump_file, "  Accepted!\n");
 404
 405   /* See if retval used by return bb is computed by header or split part.
 406      When it is computed by split part, we need to produce return statement
 407      in the split part and add code to header to pass it around.
 408
 409      This is bit tricky to test:
 410        1) When there is no return_bb or no return value, we always pass
 411           value around.
 412        2) Invariants are always computed by caller.
 413        3) For SSA we need to look if defining statement is in header or split part
 414        4) For non-SSA we need to look where the var is computed. */
 415   retval = find_retval (return_bb);
 416   if (!retval)
 417     current->split_part_set_retval = true;
 418   else if (is_gimple_min_invariant (retval))
 419     current->split_part_set_retval = false;
 420   /* Special case is value returned by reference we record as if it was non-ssa
 421      set to result_decl.  */
 422   else if (TREE_CODE (retval) == SSA_NAME
 423            && TREE_CODE (SSA_NAME_VAR (retval)) == RESULT_DECL
 424            && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
 425     current->split_part_set_retval
 426        = bitmap_bit_p (non_ssa_vars, DECL_UID (SSA_NAME_VAR (retval)));
 427   else if (TREE_CODE (retval) == SSA_NAME)
 428     current->split_part_set_retval
 429       = (!SSA_NAME_IS_DEFAULT_DEF (retval)
 430          && (bitmap_bit_p (current->split_bbs,
 431                           gimple_bb (SSA_NAME_DEF_STMT (retval))->index)
 432              || gimple_bb (SSA_NAME_DEF_STMT (retval)) == return_bb));
 433   else if (TREE_CODE (retval) == PARM_DECL)
 434     current->split_part_set_retval = false;
 435   else if (TREE_CODE (retval) == VAR_DECL
 436            || TREE_CODE (retval) == RESULT_DECL)
 437     current->split_part_set_retval
 438       = bitmap_bit_p (non_ssa_vars, DECL_UID (retval));
 439   else
 440     current->split_part_set_retval = true;
 441
 442   /* At the moment chose split point with lowest frequency and that leaves
 443      out smallest size of header.
 444      In future we might re-consider this heuristics.  */
 445   if (!best_split_point.split_bbs
 446       || best_split_point.entry_bb->frequency > current->entry_bb->frequency
 447       || (best_split_point.entry_bb->frequency == current->entry_bb->frequency
 448           && best_split_point.split_size < current->split_size))
 449
 450     {
 451       if (dump_file && (dump_flags & TDF_DETAILS))
 452         fprintf (dump_file, "  New best split point!\n");
 453       if (best_split_point.ssa_names_to_pass)
 454         {
 455           BITMAP_FREE (best_split_point.ssa_names_to_pass);
 456           BITMAP_FREE (best_split_point.split_bbs);
 457         }
 458       best_split_point = *current;
 459       best_split_point.ssa_names_to_pass = BITMAP_ALLOC (NULL);
 460       bitmap_copy (best_split_point.ssa_names_to_pass,
 461                    current->ssa_names_to_pass);
 462       best_split_point.split_bbs = BITMAP_ALLOC (NULL);
 463       bitmap_copy (best_split_point.split_bbs, current->split_bbs);
 464     }
 465 }
 466
 467 /* Return basic block containing RETURN statement.  We allow basic blocks
 468    of the form:
 469    <retval> = tmp_var;
 470    return <retval>
 471    but return_bb can not be more complex than this.
 472    If nothing is found, return EXIT_BLOCK_PTR.
 473
 474    When there are multiple RETURN statement, chose one with return value,
 475    since that one is more likely shared by multiple code paths.
 476
 477    Return BB is special, because for function splitting it is the only
 478    basic block that is duplicated in between header and split part of the
 479    function.
 480
 481    TODO: We might support multiple return blocks.  */
 482
 483 static basic_block
 484 find_return_bb (void)
 485 {
 486   edge e;
 487   edge_iterator ei;
 488   basic_block return_bb = EXIT_BLOCK_PTR;
 489
 490   if (EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 1)
 491     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 492       {
 493         gimple_stmt_iterator bsi;
 494         bool found_return = false;
 495         tree retval = NULL_TREE;
 496
 497         for (bsi = gsi_last_bb (e->src); !gsi_end_p (bsi); gsi_prev (&bsi))
 498           {
 499             gimple stmt = gsi_stmt (bsi);
 500             if (gimple_code (stmt) == GIMPLE_LABEL
 501                 || is_gimple_debug (stmt))
 502               ;
 503             else if (gimple_code (stmt) == GIMPLE_ASSIGN
 504                      && found_return
 505                      && gimple_assign_single_p (stmt)
 506                      && (auto_var_in_fn_p (gimple_assign_rhs1 (stmt),
 507                                            current_function_decl)
 508                          || is_gimple_min_invariant
 509                               (gimple_assign_rhs1 (stmt)))
 510                      && retval == gimple_assign_lhs (stmt))
 511               ;
 512             else if (gimple_code (stmt) == GIMPLE_RETURN)
 513               {
 514                 found_return = true;
 515                 retval = gimple_return_retval (stmt);
 516               }
 517             else
 518               break;
 519           }
 520         if (gsi_end_p (bsi) && found_return)
 521           {
 522             if (retval)
 523               return e->src;
 524             else
 525               return_bb = e->src;
 526           }
 527       }
 528   return return_bb;
 529 }
 530
 531 /* Given return basicblock RETURN_BB, see where return value is really
 532    stored.  */
 533 static tree
 534 find_retval (basic_block return_bb)
 535 {
 536   gimple_stmt_iterator bsi;
 537   for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
 538     if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
 539       return gimple_return_retval (gsi_stmt (bsi));
 540     else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN)
 541       return gimple_assign_rhs1 (gsi_stmt (bsi));
 542   return NULL;
 543 }
 544
 545 /* Callback for walk_stmt_load_store_addr_ops.  If T is non-ssa automatic
 546    variable, mark it as used in bitmap passed via DATA.
 547    Return true when access to T prevents splitting the function.  */
 548
 549 static bool
 550 mark_nonssa_use (gimple stmt ATTRIBUTE_UNUSED, tree t,
 551                  void *data ATTRIBUTE_UNUSED)
 552 {
 553   t = get_base_address (t);
 554
 555   if (!t || is_gimple_reg (t))
 556     return false;
 557
 558   /* At present we can't pass non-SSA arguments to split function.
 559      FIXME: this can be relaxed by passing references to arguments.  */
 560   if (TREE_CODE (t) == PARM_DECL)
 561     {
 562       if (dump_file && (dump_flags & TDF_DETAILS))
 563         fprintf (dump_file, "Can not split use of non-ssa function parameter.\n");
 564       return true;
 565     }
 566
 567   if ((TREE_CODE (t) == VAR_DECL && auto_var_in_fn_p (t, current_function_decl))
 568       || (TREE_CODE (t) == RESULT_DECL))
 569     bitmap_set_bit ((bitmap)data, DECL_UID (t));
 570
 571   /* For DECL_BY_REFERENCE, the return value is actually pointer.  We want to pretend
 572      that the value pointed to is actual result decl.  */
 573   if (t && (TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
 574       && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
 575       && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
 576       && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
 577     return bitmap_bit_p ((bitmap)data, DECL_UID (DECL_RESULT (current_function_decl)));
 578   return false;
 579 }
 580
 581 /* Compute local properties of basic block BB we collect when looking for
 582    split points.  We look for ssa defs and store them in SET_SSA_NAMES,
 583    for ssa uses and store them in USED_SSA_NAMES and for any non-SSA automatic
 584    vars stored in NON_SSA_VARS.
 585
 586    When BB has edge to RETURN_BB, collect uses in RETURN_BB too.
 587
 588    Return false when BB contains something that prevents it from being put into
 589    split function.  */
 590
 591 static bool
 592 visit_bb (basic_block bb, basic_block return_bb,
 593           bitmap set_ssa_names, bitmap used_ssa_names,
 594           bitmap non_ssa_vars)
 595 {
 596   gimple_stmt_iterator bsi;
 597   edge e;
 598   edge_iterator ei;
 599   bool can_split = true;
 600
 601   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 602     {
 603       gimple stmt = gsi_stmt (bsi);
 604       tree op;
 605       ssa_op_iter iter;
 606       tree decl;
 607
 608       if (is_gimple_debug (stmt))
 609         continue;
 610
 611       /* FIXME: We can split regions containing EH.  We can not however
 612          split RESX, EH_DISPATCH and EH_POINTER referring to same region
 613          into different partitions.  This would require tracking of
 614          EH regions and checking in consider_split_point if they
 615          are not used elsewhere.  */
 616       if (gimple_code (stmt) == GIMPLE_RESX
 617           && stmt_can_throw_external (stmt))
 618         {
 619           if (dump_file && (dump_flags & TDF_DETAILS))
 620             fprintf (dump_file, "Can not split external resx.\n");
 621           can_split = false;
 622         }
 623       if (gimple_code (stmt) == GIMPLE_EH_DISPATCH)
 624         {
 625           if (dump_file && (dump_flags & TDF_DETAILS))
 626             fprintf (dump_file, "Can not split eh dispatch.\n");
 627           can_split = false;
 628         }
 629
 630       /* Check builtins that prevent splitting.  */
 631       if (gimple_code (stmt) == GIMPLE_CALL
 632           && (decl = gimple_call_fndecl (stmt)) != NULL_TREE
 633           && DECL_BUILT_IN (decl)
 634           && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
 635         switch (DECL_FUNCTION_CODE (decl))
 636           {
 637           /* FIXME: once we will allow passing non-parm values to split part,
 638              we need to be sure to handle correct builtin_stack_save and
 639              builtin_stack_restore.  At the moment we are safe; there is no
 640              way to store builtin_stack_save result in non-SSA variable
 641              since all calls to those are compiler generated.  */
 642           case BUILT_IN_APPLY:
 643           case BUILT_IN_VA_START:
 644             if (dump_file && (dump_flags & TDF_DETAILS))
 645               fprintf (dump_file, "Can not split builtin_apply and va_start.\n");
 646             can_split = false;
 647             break;
 648           case BUILT_IN_EH_POINTER:
 649             if (dump_file && (dump_flags & TDF_DETAILS))
 650               fprintf (dump_file, "Can not split builtin_eh_pointer.\n");
 651             can_split = false;
 652             break;
 653           default:
 654             break;
 655           }
 656
 657       FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
 658         bitmap_set_bit (set_ssa_names, SSA_NAME_VERSION (op));
 659       FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
 660         bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
 661       can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
 662                                                    mark_nonssa_use,
 663                                                    mark_nonssa_use,
 664                                                    mark_nonssa_use);
 665     }
 666   for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 667     {
 668       gimple stmt = gsi_stmt (bsi);
 669       unsigned int i;
 670
 671       if (is_gimple_debug (stmt))
 672         continue;
 673       if (!is_gimple_reg (gimple_phi_result (stmt)))
 674         continue;
 675       bitmap_set_bit (set_ssa_names,
 676                       SSA_NAME_VERSION (gimple_phi_result (stmt)));
 677       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 678         {
 679           tree op = gimple_phi_arg_def (stmt, i);
 680           if (TREE_CODE (op) == SSA_NAME)
 681             bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
 682         }
 683       can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
 684                                                    mark_nonssa_use,
 685                                                    mark_nonssa_use,
 686                                                    mark_nonssa_use);
 687     }
 688   /* Record also uses comming from PHI operand in return BB.  */
 689   FOR_EACH_EDGE (e, ei, bb->succs)
 690     if (e->dest == return_bb)
 691       {
 692         for (bsi = gsi_start_phis (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
 693           {
 694             gimple stmt = gsi_stmt (bsi);
 695             tree op = gimple_phi_arg_def (stmt, e->dest_idx);
 696
 697             if (is_gimple_debug (stmt))
 698               continue;
 699             if (!is_gimple_reg (gimple_phi_result (stmt)))
 700               continue;
 701             if (TREE_CODE (op) == SSA_NAME)
 702               bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
 703             else
 704               can_split &= !mark_nonssa_use (stmt, op, non_ssa_vars);
 705           }
 706       }
 707   return can_split;
 708 }
 709
 710 /* Stack entry for recursive DFS walk in find_split_point.  */
 711
 712 typedef struct
 713 {
 714   /* Basic block we are examining.  */
 715   basic_block bb;
 716
 717   /* SSA names set and used by the BB and all BBs reachable
 718      from it via DFS walk.  */
 719   bitmap set_ssa_names, used_ssa_names;
 720   bitmap non_ssa_vars;
 721
 722   /* All BBS visited from this BB via DFS walk.  */
 723   bitmap bbs_visited;
 724
 725   /* Last examined edge in DFS walk.  Since we walk unoriented graph,
 726      the value is up to sum of incomming and outgoing edges of BB.  */
 727   unsigned int edge_num;
 728
 729   /* Stack entry index of earliest BB reachable from current BB
 730      or any BB visited later in DFS valk.  */
 731   int earliest;
 732
 733   /* Overall time and size of all BBs reached from this BB in DFS walk.  */
 734   int overall_time, overall_size;
 735
 736   /* When false we can not split on this BB.  */
 737   bool can_split;
 738 } stack_entry;
 739 DEF_VEC_O(stack_entry);
 740 DEF_VEC_ALLOC_O(stack_entry,heap);
 741
 742
 743 /* Find all articulations and call consider_split on them.
 744    OVERALL_TIME and OVERALL_SIZE is time and size of the function.
 745
 746    We perform basic algorithm for finding an articulation in a graph
 747    created from CFG by considering it to be an unoriented graph.
 748
 749    The articulation is discovered via DFS walk. We collect earliest
 750    basic block on stack that is reachable via backward edge.  Articulation
 751    is any basic block such that there is no backward edge bypassing it.
 752    To reduce stack usage we maintain heap allocated stack in STACK vector.
 753    AUX pointer of BB is set to index it appears in the stack or -1 once
 754    it is visited and popped off the stack.
 755
 756    The algorithm finds articulation after visiting the whole component
 757    reachable by it.  This makes it convenient to collect information about
 758    the component used by consider_split.  */
 759
 760 static void
 761 find_split_points (int overall_time, int overall_size)
 762 {
 763   stack_entry first;
 764   VEC(stack_entry, heap) *stack = NULL;
 765   basic_block bb;
 766   basic_block return_bb = find_return_bb ();
 767   struct split_point current;
 768
 769   current.header_time = overall_time;
 770   current.header_size = overall_size;
 771   current.split_time = 0;
 772   current.split_size = 0;
 773   current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
 774
 775   first.bb = ENTRY_BLOCK_PTR;
 776   first.edge_num = 0;
 777   first.overall_time = 0;
 778   first.overall_size = 0;
 779   first.earliest = INT_MAX;
 780   first.set_ssa_names = 0;
 781   first.used_ssa_names = 0;
 782   first.bbs_visited = 0;
 783   VEC_safe_push (stack_entry, heap, stack, &first);
 784   ENTRY_BLOCK_PTR->aux = (void *)(intptr_t)-1;
 785
 786   while (!VEC_empty (stack_entry, stack))
 787     {
 788       stack_entry *entry = VEC_last (stack_entry, stack);
 789
 790       /* We are walking an acyclic graph, so edge_num counts
 791          succ and pred edges together.  However when considering
 792          articulation, we want to have processed everything reachable
 793          from articulation but nothing that reaches into it.  */
 794       if (entry->edge_num == EDGE_COUNT (entry->bb->succs)
 795           && entry->bb != ENTRY_BLOCK_PTR)
 796         {
 797           int pos = VEC_length (stack_entry, stack);
 798           entry->can_split &= visit_bb (entry->bb, return_bb,
 799                                         entry->set_ssa_names,
 800                                         entry->used_ssa_names,
 801                                         entry->non_ssa_vars);
 802           if (pos <= entry->earliest && !entry->can_split
 803               && dump_file && (dump_flags & TDF_DETAILS))
 804             fprintf (dump_file,
 805                      "found articulation at bb %i but can not split\n",
 806                      entry->bb->index);
 807           if (pos <= entry->earliest && entry->can_split)
 808              {
 809                if (dump_file && (dump_flags & TDF_DETAILS))
 810                  fprintf (dump_file, "found articulation at bb %i\n",
 811                           entry->bb->index);
 812                current.entry_bb = entry->bb;
 813                current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
 814                bitmap_and_compl (current.ssa_names_to_pass,
 815                                  entry->used_ssa_names, entry->set_ssa_names);
 816                current.header_time = overall_time - entry->overall_time;
 817                current.header_size = overall_size - entry->overall_size;
 818                current.split_time = entry->overall_time;
 819                current.split_size = entry->overall_size;
 820                current.split_bbs = entry->bbs_visited;
 821                consider_split (&current, entry->non_ssa_vars, return_bb);
 822                BITMAP_FREE (current.ssa_names_to_pass);
 823              }
 824         }
 825       /* Do actual DFS walk.  */
 826       if (entry->edge_num
 827           < (EDGE_COUNT (entry->bb->succs)
 828              + EDGE_COUNT (entry->bb->preds)))
 829         {
 830           edge e;
 831           basic_block dest;
 832           if (entry->edge_num < EDGE_COUNT (entry->bb->succs))
 833             {
 834               e = EDGE_SUCC (entry->bb, entry->edge_num);
 835               dest = e->dest;
 836             }
 837           else
 838             {
 839               e = EDGE_PRED (entry->bb, entry->edge_num
 840                              - EDGE_COUNT (entry->bb->succs));
 841               dest = e->src;
 842             }
 843
 844           entry->edge_num++;
 845
 846           /* New BB to visit, push it to the stack.  */
 847           if (dest != return_bb && dest != EXIT_BLOCK_PTR
 848               && !dest->aux)
 849             {
 850               stack_entry new_entry;
 851
 852               new_entry.bb = dest;
 853               new_entry.edge_num = 0;
 854               new_entry.overall_time
 855                  = VEC_index (bb_info, bb_info_vec, dest->index)->time;
 856               new_entry.overall_size
 857                  = VEC_index (bb_info, bb_info_vec, dest->index)->size;
 858               new_entry.earliest = INT_MAX;
 859               new_entry.set_ssa_names = BITMAP_ALLOC (NULL);
 860               new_entry.used_ssa_names = BITMAP_ALLOC (NULL);
 861               new_entry.bbs_visited = BITMAP_ALLOC (NULL);
 862               new_entry.non_ssa_vars = BITMAP_ALLOC (NULL);
 863               new_entry.can_split = true;
 864               bitmap_set_bit (new_entry.bbs_visited, dest->index);
 865               VEC_safe_push (stack_entry, heap, stack, &new_entry);
 866               dest->aux = (void *)(intptr_t)VEC_length (stack_entry, stack);
 867             }
 868           /* Back edge found, record the earliest point.  */
 869           else if ((intptr_t)dest->aux > 0
 870                    && (intptr_t)dest->aux < entry->earliest)
 871             entry->earliest = (intptr_t)dest->aux;
 872         }
 873       /* We are done with examing the edges. pop off the value from stack and
 874          merge stuff we cummulate during the walk.  */
 875       else if (entry->bb != ENTRY_BLOCK_PTR)
 876         {
 877           stack_entry *prev = VEC_index (stack_entry, stack,
 878                                          VEC_length (stack_entry, stack) - 2);
 879
 880           entry->bb->aux = (void *)(intptr_t)-1;
 881           prev->can_split &= entry->can_split;
 882           if (prev->set_ssa_names)
 883             {
 884               bitmap_ior_into (prev->set_ssa_names, entry->set_ssa_names);
 885               bitmap_ior_into (prev->used_ssa_names, entry->used_ssa_names);
 886               bitmap_ior_into (prev->bbs_visited, entry->bbs_visited);
 887               bitmap_ior_into (prev->non_ssa_vars, entry->non_ssa_vars);
 888             }
 889           if (prev->earliest > entry->earliest)
 890             prev->earliest = entry->earliest;
 891           prev->overall_time += entry->overall_time;
 892           prev->overall_size += entry->overall_size;
 893           BITMAP_FREE (entry->set_ssa_names);
 894           BITMAP_FREE (entry->used_ssa_names);
 895           BITMAP_FREE (entry->bbs_visited);
 896           BITMAP_FREE (entry->non_ssa_vars);
 897           VEC_pop (stack_entry, stack);
 898         }
 899       else
 900         VEC_pop (stack_entry, stack);
 901     }
 902   ENTRY_BLOCK_PTR->aux = NULL;
 903   FOR_EACH_BB (bb)
 904     bb->aux = NULL;
 905   VEC_free (stack_entry, heap, stack);
 906   BITMAP_FREE (current.ssa_names_to_pass);
 907 }
 908
 909 /* Split function at SPLIT_POINT.  */
 910
 911 static void
 912 split_function (struct split_point *split_point)
 913 {
 914   VEC (tree, heap) *args_to_pass = NULL;
 915   bitmap args_to_skip = BITMAP_ALLOC (NULL);
 916   tree parm;
 917   int num = 0;
 918   struct cgraph_node *node;
 919   basic_block return_bb = find_return_bb ();
 920   basic_block call_bb;
 921   gimple_stmt_iterator gsi;
 922   gimple call;
 923   edge e;
 924   edge_iterator ei;
 925   tree retval = NULL, real_retval = NULL;
 926   bool split_part_return_p = false;
 927   gimple last_stmt = NULL;
 928
 929   if (dump_file)
 930     {
 931       fprintf (dump_file, "\n\nSplitting function at:\n");
 932       dump_split_point (dump_file, split_point);
 933     }
 934
 935   /* Collect the parameters of new function and args_to_skip bitmap.  */
 936   for (parm = DECL_ARGUMENTS (current_function_decl);
 937        parm; parm = DECL_CHAIN (parm), num++)
 938     if (!is_gimple_reg (parm)
 939         || !gimple_default_def (cfun, parm)
 940         || !bitmap_bit_p (split_point->ssa_names_to_pass,
 941                           SSA_NAME_VERSION (gimple_default_def (cfun, parm))))
 942       bitmap_set_bit (args_to_skip, num);
 943     else
 944       VEC_safe_push (tree, heap, args_to_pass, gimple_default_def (cfun, parm));
 945
 946   /* See if the split function will return.  */
 947   FOR_EACH_EDGE (e, ei, return_bb->preds)
 948     if (bitmap_bit_p (split_point->split_bbs, e->src->index))
 949       break;
 950   if (e)
 951     split_part_return_p = true;
 952
 953   /* Add return block to what will become the split function.
 954      We do not return; no return block is needed.  */
 955   if (!split_part_return_p)
 956     ;
 957   /* We have no return block, so nothing is needed.  */
 958   else if (return_bb == EXIT_BLOCK_PTR)
 959     ;
 960   /* When we do not want to return value, we need to construct
 961      new return block with empty return statement.
 962      FIXME: Once we are able to change return type, we should change function
 963      to return void instead of just outputting function with undefined return
 964      value.  For structures this affects quality of codegen.  */
 965   else if (!split_point->split_part_set_retval
 966            && find_retval (return_bb))
 967     {
 968       bool redirected = true;
 969       basic_block new_return_bb = create_basic_block (NULL, 0, return_bb);
 970       gimple_stmt_iterator gsi = gsi_start_bb (new_return_bb);
 971       gsi_insert_after (&gsi, gimple_build_return (NULL), GSI_NEW_STMT);
 972       while (redirected)
 973         {
 974           redirected = false;
 975           FOR_EACH_EDGE (e, ei, return_bb->preds)
 976             if (bitmap_bit_p (split_point->split_bbs, e->src->index))
 977               {
 978                 new_return_bb->count += e->count;
 979                 new_return_bb->frequency += EDGE_FREQUENCY (e);
 980                 redirect_edge_and_branch (e, new_return_bb);
 981                 redirected = true;
 982                 break;
 983               }
 984         }
 985       e = make_edge (new_return_bb, EXIT_BLOCK_PTR, 0);
 986       e->probability = REG_BR_PROB_BASE;
 987       e->count = new_return_bb->count;
 988       bitmap_set_bit (split_point->split_bbs, new_return_bb->index);
 989       /* We change CFG in a way tree-inline is not able to compensate on while
 990          updating PHIs.  There are only virtuals in return_bb, so recompute
 991          them.  */
 992       for (gsi = gsi_start_phis (return_bb); !gsi_end_p (gsi);)
 993         {
 994           gimple stmt = gsi_stmt (gsi);
 995           gcc_assert (!is_gimple_reg (gimple_phi_result (stmt)));
 996           mark_virtual_phi_result_for_renaming (stmt);
 997           remove_phi_node (&gsi, true);
 998         }
 999     }
1000   /* When we pass aorund the value, use existing return block.  */
1001   else
1002     bitmap_set_bit (split_point->split_bbs, return_bb->index);
1003
1004   /* Now create the actual clone.  */
1005   rebuild_cgraph_edges ();
1006   node = cgraph_function_versioning (cgraph_node (current_function_decl),
1007                                      NULL, NULL,
1008                                      args_to_skip,
1009                                      split_point->split_bbs,
1010                                      split_point->entry_bb, "part");
1011   /* For usual cloning it is enough to clear builtin only when signature
1012      changes.  For partial inlining we however can not expect the part
1013      of builtin implementation to have same semantic as the whole.  */
1014   if (DECL_BUILT_IN (node->decl))
1015     {
1016       DECL_BUILT_IN_CLASS (node->decl) = NOT_BUILT_IN;
1017       DECL_FUNCTION_CODE (node->decl) = (enum built_in_function) 0;
1018     }
1019   cgraph_node_remove_callees (cgraph_node (current_function_decl));
1020   if (!split_part_return_p)
1021     TREE_THIS_VOLATILE (node->decl) = 1;
1022   if (dump_file)
1023     dump_function_to_file (node->decl, dump_file, dump_flags);
1024
1025   /* Create the basic block we place call into.  It is the entry basic block
1026      split after last label.  */
1027   call_bb = split_point->entry_bb;
1028   for (gsi = gsi_start_bb (call_bb); !gsi_end_p (gsi);)
1029     if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
1030       {
1031         last_stmt = gsi_stmt (gsi);
1032         gsi_next (&gsi);
1033       }
1034     else
1035       break;
1036   e = split_block (split_point->entry_bb, last_stmt);
1037   remove_edge (e);
1038
1039   /* Produce the call statement.  */
1040   gsi = gsi_last_bb (call_bb);
1041   call = gimple_build_call_vec (node->decl, args_to_pass);
1042   gimple_set_block (call, DECL_INITIAL (current_function_decl));
1043
1044   /* We avoid address being taken on any variable used by split part,
1045      so return slot optimization is always possible.  Moreover this is
1046      required to make DECL_BY_REFERENCE work.  */
1047   if (aggregate_value_p (DECL_RESULT (current_function_decl),
1048                          TREE_TYPE (current_function_decl)))
1049     gimple_call_set_return_slot_opt (call, true);
1050
1051   /* Update return value.  This is bit tricky.  When we do not return,
1052      do nothing.  When we return we might need to update return_bb
1053      or produce a new return statement.  */
1054   if (!split_part_return_p)
1055     gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1056   else
1057     {
1058       e = make_edge (call_bb, return_bb,
1059                      return_bb == EXIT_BLOCK_PTR ? 0 : EDGE_FALLTHRU);
1060       e->count = call_bb->count;
1061       e->probability = REG_BR_PROB_BASE;
1062
1063       /* If there is return basic block, see what value we need to store
1064          return value into and put call just before it.  */
1065       if (return_bb != EXIT_BLOCK_PTR)
1066         {
1067           real_retval = retval = find_retval (return_bb);
1068
1069           if (real_retval && split_point->split_part_set_retval)
1070             {
1071               gimple_stmt_iterator psi;
1072
1073               /* See if we need new SSA_NAME for the result.
1074                  When DECL_BY_REFERENCE is true, retval is actually pointer to
1075                  return value and it is constant in whole function.  */
1076               if (TREE_CODE (retval) == SSA_NAME
1077                   && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1078                 {
1079                   retval = make_ssa_name (SSA_NAME_VAR (retval), call);
1080
1081                   /* See if there is PHI defining return value.  */
1082                   for (psi = gsi_start_phis (return_bb);
1083                        !gsi_end_p (psi); gsi_next (&psi))
1084                     if (is_gimple_reg (gimple_phi_result (gsi_stmt (psi))))
1085                       break;
1086
1087                   /* When there is PHI, just update its value.  */
1088                   if (TREE_CODE (retval) == SSA_NAME
1089                       && !gsi_end_p (psi))
1090                     add_phi_arg (gsi_stmt (psi), retval, e, UNKNOWN_LOCATION);
1091                   /* Otherwise update the return BB itself.
1092                      find_return_bb allows at most one assignment to return value,
1093                      so update first statement.  */
1094                   else
1095                     {
1096                       gimple_stmt_iterator bsi;
1097                       for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi);
1098                            gsi_next (&bsi))
1099                         if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
1100                           {
1101                             gimple_return_set_retval (gsi_stmt (bsi), retval);
1102                             break;
1103                           }
1104                         else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN)
1105                           {
1106                             gimple_assign_set_rhs1 (gsi_stmt (bsi), retval);
1107                             break;
1108                           }
1109                       update_stmt (gsi_stmt (bsi));
1110                     }
1111                 }
1112               if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1113                 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1114               else
1115                 gimple_call_set_lhs (call, retval);
1116             }
1117           gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1118         }
1119       /* We don't use return block (there is either no return in function or
1120          multiple of them).  So create new basic block with return statement.
1121          */
1122       else
1123         {
1124           gimple ret;
1125           if (split_point->split_part_set_retval
1126               && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl))))
1127             {
1128               retval = DECL_RESULT (current_function_decl);
1129
1130               /* We use temporary register to hold value when aggregate_value_p
1131                  is false.  Similarly for DECL_BY_REFERENCE we must avoid extra
1132                  copy.  */
1133               if (!aggregate_value_p (retval, TREE_TYPE (current_function_decl))
1134                   && !DECL_BY_REFERENCE (retval))
1135                 retval = create_tmp_reg (TREE_TYPE (retval), NULL);
1136               if (is_gimple_reg (retval))
1137                 {
1138                   /* When returning by reference, there is only one SSA name
1139                      assigned to RESULT_DECL (that is pointer to return value).
1140                      Look it up or create new one if it is missing.  */
1141                   if (DECL_BY_REFERENCE (retval))
1142                     {
1143                       tree retval_name;
1144                       if ((retval_name = gimple_default_def (cfun, retval))
1145                           != NULL)
1146                         retval = retval_name;
1147                       else
1148                         {
1149                           retval_name = make_ssa_name (retval,
1150                                                        gimple_build_nop ());
1151                           set_default_def (retval, retval_name);
1152                           retval = retval_name;
1153                         }
1154                     }
1155                   /* Otherwise produce new SSA name for return value.  */
1156                   else
1157                     retval = make_ssa_name (retval, call);
1158                 }
1159               if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1160                 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1161               else
1162                 gimple_call_set_lhs (call, retval);
1163             }
1164           gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1165           ret = gimple_build_return (retval);
1166           gsi_insert_after (&gsi, ret, GSI_NEW_STMT);
1167         }
1168     }
1169   free_dominance_info (CDI_DOMINATORS);
1170   free_dominance_info (CDI_POST_DOMINATORS);
1171   compute_inline_parameters (node);
1172 }
1173
1174 /* Execute function splitting pass.  */
1175
1176 static unsigned int
1177 execute_split_functions (void)
1178 {
1179   gimple_stmt_iterator bsi;
1180   basic_block bb;
1181   int overall_time = 0, overall_size = 0;
1182   int todo = 0;
1183   struct cgraph_node *node = cgraph_node (current_function_decl);
1184
1185   if (flags_from_decl_or_type (current_function_decl) & ECF_NORETURN)
1186     {
1187       if (dump_file)
1188         fprintf (dump_file, "Not splitting: noreturn function.\n");
1189       return 0;
1190     }
1191   if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
1192     {
1193       if (dump_file)
1194         fprintf (dump_file, "Not splitting: main function.\n");
1195       return 0;
1196     }
1197   /* This can be relaxed; function might become inlinable after splitting
1198      away the uninlinable part.  */
1199   if (!node->local.inlinable)
1200     {
1201       if (dump_file)
1202         fprintf (dump_file, "Not splitting: not inlinable.\n");
1203       return 0;
1204     }
1205   if (node->local.disregard_inline_limits)
1206     {
1207       if (dump_file)
1208         fprintf (dump_file, "Not splitting: disregading inline limits.\n");
1209       return 0;
1210     }
1211   /* This can be relaxed; most of versioning tests actually prevents
1212      a duplication.  */
1213   if (!tree_versionable_function_p (current_function_decl))
1214     {
1215       if (dump_file)
1216         fprintf (dump_file, "Not splitting: not versionable.\n");
1217       return 0;
1218     }
1219   /* FIXME: we could support this.  */
1220   if (DECL_STRUCT_FUNCTION (current_function_decl)->static_chain_decl)
1221     {
1222       if (dump_file)
1223         fprintf (dump_file, "Not splitting: nested function.\n");
1224       return 0;
1225     }
1226
1227   /* See if it makes sense to try to split.
1228      It makes sense to split if we inline, that is if we have direct calls to
1229      handle or direct calls are possibly going to appear as result of indirect
1230      inlining or LTO.
1231      Note that we are not completely conservative about disqualifying functions
1232      called once.  It is possible that the caller is called more then once and
1233      then inlining would still benefit.  */
1234   if ((!node->callers || !node->callers->next_caller)
1235       && !node->address_taken
1236       && ((!flag_lto && !flag_whopr) || !node->local.externally_visible))
1237     {
1238       if (dump_file)
1239         fprintf (dump_file, "Not splitting: not called directly "
1240                  "or called once.\n");
1241       return 0;
1242     }
1243
1244   /* FIXME: We can actually split if splitting reduces call overhead.  */
1245   if (!flag_inline_small_functions
1246       && !DECL_DECLARED_INLINE_P (current_function_decl))
1247     {
1248       if (dump_file)
1249         fprintf (dump_file, "Not splitting: not autoinlining and function"
1250                  " is not inline.\n");
1251       return 0;
1252     }
1253
1254   /* Compute local info about basic blocks and determine function size/time.  */
1255   VEC_safe_grow_cleared (bb_info, heap, bb_info_vec, last_basic_block + 1);
1256   memset (&best_split_point, 0, sizeof (best_split_point));
1257   FOR_EACH_BB (bb)
1258     {
1259       int time = 0;
1260       int size = 0;
1261       int freq = compute_call_stmt_bb_frequency (current_function_decl, bb);
1262
1263       if (dump_file && (dump_flags & TDF_DETAILS))
1264         fprintf (dump_file, "Basic block %i\n", bb->index);
1265
1266       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1267         {
1268           int this_time, this_size;
1269           gimple stmt = gsi_stmt (bsi);
1270
1271           this_size = estimate_num_insns (stmt, &eni_size_weights);
1272           this_time = estimate_num_insns (stmt, &eni_time_weights) * freq;
1273           size += this_size;
1274           time += this_time;
1275
1276           if (dump_file && (dump_flags & TDF_DETAILS))
1277             {
1278               fprintf (dump_file, "  freq:%6i size:%3i time:%3i ",
1279                        freq, this_size, this_time);
1280               print_gimple_stmt (dump_file, stmt, 0, 0);
1281             }
1282         }
1283       overall_time += time;
1284       overall_size += size;
1285       VEC_index (bb_info, bb_info_vec, bb->index)->time = time;
1286       VEC_index (bb_info, bb_info_vec, bb->index)->size = size;
1287     }
1288   find_split_points (overall_time, overall_size);
1289   if (best_split_point.split_bbs)
1290     {
1291       split_function (&best_split_point);
1292       BITMAP_FREE (best_split_point.ssa_names_to_pass);
1293       BITMAP_FREE (best_split_point.split_bbs);
1294       todo = TODO_update_ssa | TODO_cleanup_cfg;
1295     }
1296   VEC_free (bb_info, heap, bb_info_vec);
1297   bb_info_vec = NULL;
1298   return todo;
1299 }
1300
1301 static bool
1302 gate_split_functions (void)
1303 {
1304   return flag_partial_inlining;
1305 }
1306
1307 struct gimple_opt_pass pass_split_functions =
1308 {
1309  {
1310   GIMPLE_PASS,
1311   "fnsplit",                            /* name */
1312   gate_split_functions,                 /* gate */
1313   execute_split_functions,              /* execute */
1314   NULL,                                 /* sub */
1315   NULL,                                 /* next */
1316   0,                                    /* static_pass_number */
1317   TV_IPA_FNSPLIT,                       /* tv_id */
1318   PROP_cfg,                             /* properties_required */
1319   0,                                    /* properties_provided */
1320   0,                                    /* properties_destroyed */
1321   0,                                    /* todo_flags_start */
1322   TODO_dump_func                        /* todo_flags_finish */
1323  }
1324 };