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_bit_p (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             bitmap_set_bit (seen, e->src->index);
 211           }
 212       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 213         {
 214           if (is_gimple_debug (gsi_stmt (bsi)))
 215             continue;
 216           if (walk_stmt_load_store_addr_ops
 217               (gsi_stmt (bsi), non_ssa_vars, test_nonssa_use,
 218                test_nonssa_use, test_nonssa_use))
 219             {
 220               ok = false;
 221               goto done;
 222             }
 223         }
 224       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 225         {
 226           if (walk_stmt_load_store_addr_ops
 227               (gsi_stmt (bsi), non_ssa_vars, test_nonssa_use,
 228                test_nonssa_use, test_nonssa_use))
 229             {
 230               ok = false;
 231               goto done;
 232             }
 233         }
 234       FOR_EACH_EDGE (e, ei, bb->succs)
 235         {
 236           if (e->dest != return_bb)
 237             continue;
 238           for (bsi = gsi_start_phis (return_bb); !gsi_end_p (bsi);
 239                gsi_next (&bsi))
 240             {
 241               gimple stmt = gsi_stmt (bsi);
 242               tree op = gimple_phi_arg_def (stmt, e->dest_idx);
 243
 244               if (!is_gimple_reg (gimple_phi_result (stmt)))
 245                 continue;
 246               if (TREE_CODE (op) != SSA_NAME
 247                   && test_nonssa_use (stmt, op, non_ssa_vars))
 248                 {
 249                   ok = false;
 250                   goto done;
 251                 }
 252             }
 253         }
 254     }
 255 done:
 256   BITMAP_FREE (seen);
 257   VEC_free (basic_block, heap, worklist);
 258   return ok;
 259 }
 260
 261 /* We found an split_point CURRENT.  NON_SSA_VARS is bitmap of all non ssa
 262    variables used and RETURN_BB is return basic block.
 263    See if we can split function here.  */
 264
 265 static void
 266 consider_split (struct split_point *current, bitmap non_ssa_vars,
 267                 basic_block return_bb)
 268 {
 269   tree parm;
 270   unsigned int num_args = 0;
 271   unsigned int call_overhead;
 272   edge e;
 273   edge_iterator ei;
 274   gimple_stmt_iterator bsi;
 275   unsigned int i;
 276   int incomming_freq = 0;
 277   tree retval;
 278
 279   if (dump_file && (dump_flags & TDF_DETAILS))
 280     dump_split_point (dump_file, current);
 281
 282   FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
 283     if (!bitmap_bit_p (current->split_bbs, e->src->index))
 284       incomming_freq += EDGE_FREQUENCY (e);
 285
 286   /* Do not split when we would end up calling function anyway.  */
 287   if (incomming_freq
 288       >= (ENTRY_BLOCK_PTR->frequency
 289           * PARAM_VALUE (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY) / 100))
 290     {
 291       if (dump_file && (dump_flags & TDF_DETAILS))
 292         fprintf (dump_file,
 293                  "  Refused: incomming frequency is too large.\n");
 294       return;
 295     }
 296
 297   if (!current->header_size)
 298     {
 299       if (dump_file && (dump_flags & TDF_DETAILS))
 300         fprintf (dump_file, "  Refused: header empty\n");
 301       gcc_unreachable ();
 302       return;
 303     }
 304
 305   /* Verify that PHI args on entry are either virutal or all their operands
 306      incomming from header are the same.  */
 307   for (bsi = gsi_start_phis (current->entry_bb); !gsi_end_p (bsi); gsi_next (&bsi))
 308     {
 309       gimple stmt = gsi_stmt (bsi);
 310       tree val = NULL;
 311
 312       if (!is_gimple_reg (gimple_phi_result (stmt)))
 313         continue;
 314       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 315         {
 316           edge e = gimple_phi_arg_edge (stmt, i);
 317           if (!bitmap_bit_p (current->split_bbs, e->src->index))
 318             {
 319               tree edge_val = gimple_phi_arg_def (stmt, i);
 320               if (val && edge_val != val)
 321                 {
 322                   if (dump_file && (dump_flags & TDF_DETAILS))
 323                     fprintf (dump_file,
 324                              "  Refused: entry BB has PHI with multiple variants\n");
 325                   return;
 326                 }
 327               val = edge_val;
 328             }
 329         }
 330     }
 331
 332
 333   /* See what argument we will pass to the split function and compute
 334      call overhead.  */
 335   call_overhead = eni_size_weights.call_cost;
 336   for (parm = DECL_ARGUMENTS (current_function_decl); parm;
 337        parm = DECL_CHAIN (parm))
 338     {
 339       if (!is_gimple_reg (parm))
 340         {
 341           if (bitmap_bit_p (non_ssa_vars, DECL_UID (parm)))
 342             {
 343               if (dump_file && (dump_flags & TDF_DETAILS))
 344                 fprintf (dump_file,
 345                          "  Refused: need to pass non-ssa param values\n");
 346               return;
 347             }
 348         }
 349       else if (gimple_default_def (cfun, parm)
 350                && bitmap_bit_p (current->ssa_names_to_pass,
 351                                 SSA_NAME_VERSION (gimple_default_def
 352                                                   (cfun, parm))))
 353         {
 354           if (!VOID_TYPE_P (TREE_TYPE (parm)))
 355             call_overhead += estimate_move_cost (TREE_TYPE (parm));
 356           num_args++;
 357         }
 358     }
 359   if (!VOID_TYPE_P (TREE_TYPE (current_function_decl)))
 360     call_overhead += estimate_move_cost (TREE_TYPE (current_function_decl));
 361
 362   if (current->split_size <= call_overhead)
 363     {
 364       if (dump_file && (dump_flags & TDF_DETAILS))
 365         fprintf (dump_file,
 366                  "  Refused: split size is smaller than call overhead\n");
 367       return;
 368     }
 369   if (current->header_size + call_overhead
 370       >= (unsigned int)(DECL_DECLARED_INLINE_P (current_function_decl)
 371                         ? MAX_INLINE_INSNS_SINGLE
 372                         : MAX_INLINE_INSNS_AUTO))
 373     {
 374       if (dump_file && (dump_flags & TDF_DETAILS))
 375         fprintf (dump_file,
 376                  "  Refused: header size is too large for inline candidate\n");
 377       return;
 378     }
 379
 380   /* FIXME: we currently can pass only SSA function parameters to the split
 381      arguments.  Once parm_adjustment infrastructure is supported by cloning,
 382      we can pass more than that.  */
 383   if (num_args != bitmap_count_bits (current->ssa_names_to_pass))
 384     {
 385
 386       if (dump_file && (dump_flags & TDF_DETAILS))
 387         fprintf (dump_file,
 388                  "  Refused: need to pass non-param values\n");
 389       return;
 390     }
 391
 392   /* When there are non-ssa vars used in the split region, see if they
 393      are used in the header region.  If so, reject the split.
 394      FIXME: we can use nested function support to access both.  */
 395   if (!bitmap_empty_p (non_ssa_vars)
 396       && !verify_non_ssa_vars (current, non_ssa_vars, return_bb))
 397     {
 398       if (dump_file && (dump_flags & TDF_DETAILS))
 399         fprintf (dump_file,
 400                  "  Refused: split part has non-ssa uses\n");
 401       return;
 402     }
 403   if (dump_file && (dump_flags & TDF_DETAILS))
 404     fprintf (dump_file, "  Accepted!\n");
 405
 406   /* See if retval used by return bb is computed by header or split part.
 407      When it is computed by split part, we need to produce return statement
 408      in the split part and add code to header to pass it around.
 409
 410      This is bit tricky to test:
 411        1) When there is no return_bb or no return value, we always pass
 412           value around.
 413        2) Invariants are always computed by caller.
 414        3) For SSA we need to look if defining statement is in header or split part
 415        4) For non-SSA we need to look where the var is computed. */
 416   retval = find_retval (return_bb);
 417   if (!retval)
 418     current->split_part_set_retval = true;
 419   else if (is_gimple_min_invariant (retval))
 420     current->split_part_set_retval = false;
 421   /* Special case is value returned by reference we record as if it was non-ssa
 422      set to result_decl.  */
 423   else if (TREE_CODE (retval) == SSA_NAME
 424            && TREE_CODE (SSA_NAME_VAR (retval)) == RESULT_DECL
 425            && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
 426     current->split_part_set_retval
 427        = bitmap_bit_p (non_ssa_vars, DECL_UID (SSA_NAME_VAR (retval)));
 428   else if (TREE_CODE (retval) == SSA_NAME)
 429     current->split_part_set_retval
 430       = (!SSA_NAME_IS_DEFAULT_DEF (retval)
 431          && (bitmap_bit_p (current->split_bbs,
 432                           gimple_bb (SSA_NAME_DEF_STMT (retval))->index)
 433              || gimple_bb (SSA_NAME_DEF_STMT (retval)) == return_bb));
 434   else if (TREE_CODE (retval) == PARM_DECL)
 435     current->split_part_set_retval = false;
 436   else if (TREE_CODE (retval) == VAR_DECL
 437            || TREE_CODE (retval) == RESULT_DECL)
 438     current->split_part_set_retval
 439       = bitmap_bit_p (non_ssa_vars, DECL_UID (retval));
 440   else
 441     current->split_part_set_retval = true;
 442
 443   /* At the moment chose split point with lowest frequency and that leaves
 444      out smallest size of header.
 445      In future we might re-consider this heuristics.  */
 446   if (!best_split_point.split_bbs
 447       || best_split_point.entry_bb->frequency > current->entry_bb->frequency
 448       || (best_split_point.entry_bb->frequency == current->entry_bb->frequency
 449           && best_split_point.split_size < current->split_size))
 450
 451     {
 452       if (dump_file && (dump_flags & TDF_DETAILS))
 453         fprintf (dump_file, "  New best split point!\n");
 454       if (best_split_point.ssa_names_to_pass)
 455         {
 456           BITMAP_FREE (best_split_point.ssa_names_to_pass);
 457           BITMAP_FREE (best_split_point.split_bbs);
 458         }
 459       best_split_point = *current;
 460       best_split_point.ssa_names_to_pass = BITMAP_ALLOC (NULL);
 461       bitmap_copy (best_split_point.ssa_names_to_pass,
 462                    current->ssa_names_to_pass);
 463       best_split_point.split_bbs = BITMAP_ALLOC (NULL);
 464       bitmap_copy (best_split_point.split_bbs, current->split_bbs);
 465     }
 466 }
 467
 468 /* Return basic block containing RETURN statement.  We allow basic blocks
 469    of the form:
 470    <retval> = tmp_var;
 471    return <retval>
 472    but return_bb can not be more complex than this.
 473    If nothing is found, return EXIT_BLOCK_PTR.
 474
 475    When there are multiple RETURN statement, chose one with return value,
 476    since that one is more likely shared by multiple code paths.
 477
 478    Return BB is special, because for function splitting it is the only
 479    basic block that is duplicated in between header and split part of the
 480    function.
 481
 482    TODO: We might support multiple return blocks.  */
 483
 484 static basic_block
 485 find_return_bb (void)
 486 {
 487   edge e;
 488   edge_iterator ei;
 489   basic_block return_bb = EXIT_BLOCK_PTR;
 490
 491   if (EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 1)
 492     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 493       {
 494         gimple_stmt_iterator bsi;
 495         bool found_return = false;
 496         tree retval = NULL_TREE;
 497
 498         for (bsi = gsi_last_bb (e->src); !gsi_end_p (bsi); gsi_prev (&bsi))
 499           {
 500             gimple stmt = gsi_stmt (bsi);
 501             if (gimple_code (stmt) == GIMPLE_LABEL
 502                 || is_gimple_debug (stmt))
 503               ;
 504             else if (gimple_code (stmt) == GIMPLE_ASSIGN
 505                      && found_return
 506                      && gimple_assign_single_p (stmt)
 507                      && (auto_var_in_fn_p (gimple_assign_rhs1 (stmt),
 508                                            current_function_decl)
 509                          || is_gimple_min_invariant
 510                               (gimple_assign_rhs1 (stmt)))
 511                      && retval == gimple_assign_lhs (stmt))
 512               ;
 513             else if (gimple_code (stmt) == GIMPLE_RETURN)
 514               {
 515                 found_return = true;
 516                 retval = gimple_return_retval (stmt);
 517               }
 518             else
 519               break;
 520           }
 521         if (gsi_end_p (bsi) && found_return)
 522           {
 523             if (retval)
 524               return e->src;
 525             else
 526               return_bb = e->src;
 527           }
 528       }
 529   return return_bb;
 530 }
 531
 532 /* Given return basicblock RETURN_BB, see where return value is really
 533    stored.  */
 534 static tree
 535 find_retval (basic_block return_bb)
 536 {
 537   gimple_stmt_iterator bsi;
 538   for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
 539     if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
 540       return gimple_return_retval (gsi_stmt (bsi));
 541     else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN)
 542       return gimple_assign_rhs1 (gsi_stmt (bsi));
 543   return NULL;
 544 }
 545
 546 /* Callback for walk_stmt_load_store_addr_ops.  If T is non-ssa automatic
 547    variable, mark it as used in bitmap passed via DATA.
 548    Return true when access to T prevents splitting the function.  */
 549
 550 static bool
 551 mark_nonssa_use (gimple stmt ATTRIBUTE_UNUSED, tree t,
 552                  void *data ATTRIBUTE_UNUSED)
 553 {
 554   t = get_base_address (t);
 555
 556   if (!t || is_gimple_reg (t))
 557     return false;
 558
 559   /* At present we can't pass non-SSA arguments to split function.
 560      FIXME: this can be relaxed by passing references to arguments.  */
 561   if (TREE_CODE (t) == PARM_DECL)
 562     {
 563       if (dump_file && (dump_flags & TDF_DETAILS))
 564         fprintf (dump_file, "Can not split use of non-ssa function parameter.\n");
 565       return true;
 566     }
 567
 568   if ((TREE_CODE (t) == VAR_DECL && auto_var_in_fn_p (t, current_function_decl))
 569       || (TREE_CODE (t) == RESULT_DECL))
 570     bitmap_set_bit ((bitmap)data, DECL_UID (t));
 571
 572   /* For DECL_BY_REFERENCE, the return value is actually pointer.  We want to pretend
 573      that the value pointed to is actual result decl.  */
 574   if (t && (TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
 575       && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
 576       && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
 577       && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
 578     return bitmap_bit_p ((bitmap)data, DECL_UID (DECL_RESULT (current_function_decl)));
 579   return false;
 580 }
 581
 582 /* Compute local properties of basic block BB we collect when looking for
 583    split points.  We look for ssa defs and store them in SET_SSA_NAMES,
 584    for ssa uses and store them in USED_SSA_NAMES and for any non-SSA automatic
 585    vars stored in NON_SSA_VARS.
 586
 587    When BB has edge to RETURN_BB, collect uses in RETURN_BB too.
 588
 589    Return false when BB contains something that prevents it from being put into
 590    split function.  */
 591
 592 static bool
 593 visit_bb (basic_block bb, basic_block return_bb,
 594           bitmap set_ssa_names, bitmap used_ssa_names,
 595           bitmap non_ssa_vars)
 596 {
 597   gimple_stmt_iterator bsi;
 598   edge e;
 599   edge_iterator ei;
 600   bool can_split = true;
 601
 602   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 603     {
 604       gimple stmt = gsi_stmt (bsi);
 605       tree op;
 606       ssa_op_iter iter;
 607       tree decl;
 608
 609       if (is_gimple_debug (stmt))
 610         continue;
 611
 612       /* FIXME: We can split regions containing EH.  We can not however
 613          split RESX, EH_DISPATCH and EH_POINTER referring to same region
 614          into different partitions.  This would require tracking of
 615          EH regions and checking in consider_split_point if they
 616          are not used elsewhere.  */
 617       if (gimple_code (stmt) == GIMPLE_RESX
 618           && stmt_can_throw_external (stmt))
 619         {
 620           if (dump_file && (dump_flags & TDF_DETAILS))
 621             fprintf (dump_file, "Can not split external resx.\n");
 622           can_split = false;
 623         }
 624       if (gimple_code (stmt) == GIMPLE_EH_DISPATCH)
 625         {
 626           if (dump_file && (dump_flags & TDF_DETAILS))
 627             fprintf (dump_file, "Can not split eh dispatch.\n");
 628           can_split = false;
 629         }
 630
 631       /* Check builtins that prevent splitting.  */
 632       if (gimple_code (stmt) == GIMPLE_CALL
 633           && (decl = gimple_call_fndecl (stmt)) != NULL_TREE
 634           && DECL_BUILT_IN (decl)
 635           && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
 636         switch (DECL_FUNCTION_CODE (decl))
 637           {
 638           /* FIXME: once we will allow passing non-parm values to split part,
 639              we need to be sure to handle correct builtin_stack_save and
 640              builtin_stack_restore.  At the moment we are safe; there is no
 641              way to store builtin_stack_save result in non-SSA variable
 642              since all calls to those are compiler generated.  */
 643           case BUILT_IN_APPLY:
 644           case BUILT_IN_VA_START:
 645             if (dump_file && (dump_flags & TDF_DETAILS))
 646               fprintf (dump_file, "Can not split builtin_apply and va_start.\n");
 647             can_split = false;
 648             break;
 649           case BUILT_IN_EH_POINTER:
 650             if (dump_file && (dump_flags & TDF_DETAILS))
 651               fprintf (dump_file, "Can not split builtin_eh_pointer.\n");
 652             can_split = false;
 653             break;
 654           default:
 655             break;
 656           }
 657
 658       FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
 659         bitmap_set_bit (set_ssa_names, SSA_NAME_VERSION (op));
 660       FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
 661         bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
 662       can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
 663                                                    mark_nonssa_use,
 664                                                    mark_nonssa_use,
 665                                                    mark_nonssa_use);
 666     }
 667   for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 668     {
 669       gimple stmt = gsi_stmt (bsi);
 670       unsigned int i;
 671
 672       if (is_gimple_debug (stmt))
 673         continue;
 674       if (!is_gimple_reg (gimple_phi_result (stmt)))
 675         continue;
 676       bitmap_set_bit (set_ssa_names,
 677                       SSA_NAME_VERSION (gimple_phi_result (stmt)));
 678       for (i = 0; i < gimple_phi_num_args (stmt); i++)
 679         {
 680           tree op = gimple_phi_arg_def (stmt, i);
 681           if (TREE_CODE (op) == SSA_NAME)
 682             bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
 683         }
 684       can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
 685                                                    mark_nonssa_use,
 686                                                    mark_nonssa_use,
 687                                                    mark_nonssa_use);
 688     }
 689   /* Record also uses comming from PHI operand in return BB.  */
 690   FOR_EACH_EDGE (e, ei, bb->succs)
 691     if (e->dest == return_bb)
 692       {
 693         for (bsi = gsi_start_phis (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
 694           {
 695             gimple stmt = gsi_stmt (bsi);
 696             tree op = gimple_phi_arg_def (stmt, e->dest_idx);
 697
 698             if (is_gimple_debug (stmt))
 699               continue;
 700             if (!is_gimple_reg (gimple_phi_result (stmt)))
 701               continue;
 702             if (TREE_CODE (op) == SSA_NAME)
 703               bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
 704             else
 705               can_split &= !mark_nonssa_use (stmt, op, non_ssa_vars);
 706           }
 707       }
 708   return can_split;
 709 }
 710
 711 /* Stack entry for recursive DFS walk in find_split_point.  */
 712
 713 typedef struct
 714 {
 715   /* Basic block we are examining.  */
 716   basic_block bb;
 717
 718   /* SSA names set and used by the BB and all BBs reachable
 719      from it via DFS walk.  */
 720   bitmap set_ssa_names, used_ssa_names;
 721   bitmap non_ssa_vars;
 722
 723   /* All BBS visited from this BB via DFS walk.  */
 724   bitmap bbs_visited;
 725
 726   /* Last examined edge in DFS walk.  Since we walk unoriented graph,
 727      the value is up to sum of incomming and outgoing edges of BB.  */
 728   unsigned int edge_num;
 729
 730   /* Stack entry index of earliest BB reachable from current BB
 731      or any BB visited later in DFS valk.  */
 732   int earliest;
 733
 734   /* Overall time and size of all BBs reached from this BB in DFS walk.  */
 735   int overall_time, overall_size;
 736
 737   /* When false we can not split on this BB.  */
 738   bool can_split;
 739 } stack_entry;
 740 DEF_VEC_O(stack_entry);
 741 DEF_VEC_ALLOC_O(stack_entry,heap);
 742
 743
 744 /* Find all articulations and call consider_split on them.
 745    OVERALL_TIME and OVERALL_SIZE is time and size of the function.
 746
 747    We perform basic algorithm for finding an articulation in a graph
 748    created from CFG by considering it to be an unoriented graph.
 749
 750    The articulation is discovered via DFS walk. We collect earliest
 751    basic block on stack that is reachable via backward edge.  Articulation
 752    is any basic block such that there is no backward edge bypassing it.
 753    To reduce stack usage we maintain heap allocated stack in STACK vector.
 754    AUX pointer of BB is set to index it appears in the stack or -1 once
 755    it is visited and popped off the stack.
 756
 757    The algorithm finds articulation after visiting the whole component
 758    reachable by it.  This makes it convenient to collect information about
 759    the component used by consider_split.  */
 760
 761 static void
 762 find_split_points (int overall_time, int overall_size)
 763 {
 764   stack_entry first;
 765   VEC(stack_entry, heap) *stack = NULL;
 766   basic_block bb;
 767   basic_block return_bb = find_return_bb ();
 768   struct split_point current;
 769
 770   current.header_time = overall_time;
 771   current.header_size = overall_size;
 772   current.split_time = 0;
 773   current.split_size = 0;
 774   current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
 775
 776   first.bb = ENTRY_BLOCK_PTR;
 777   first.edge_num = 0;
 778   first.overall_time = 0;
 779   first.overall_size = 0;
 780   first.earliest = INT_MAX;
 781   first.set_ssa_names = 0;
 782   first.used_ssa_names = 0;
 783   first.bbs_visited = 0;
 784   VEC_safe_push (stack_entry, heap, stack, &first);
 785   ENTRY_BLOCK_PTR->aux = (void *)(intptr_t)-1;
 786
 787   while (!VEC_empty (stack_entry, stack))
 788     {
 789       stack_entry *entry = VEC_last (stack_entry, stack);
 790
 791       /* We are walking an acyclic graph, so edge_num counts
 792          succ and pred edges together.  However when considering
 793          articulation, we want to have processed everything reachable
 794          from articulation but nothing that reaches into it.  */
 795       if (entry->edge_num == EDGE_COUNT (entry->bb->succs)
 796           && entry->bb != ENTRY_BLOCK_PTR)
 797         {
 798           int pos = VEC_length (stack_entry, stack);
 799           entry->can_split &= visit_bb (entry->bb, return_bb,
 800                                         entry->set_ssa_names,
 801                                         entry->used_ssa_names,
 802                                         entry->non_ssa_vars);
 803           if (pos <= entry->earliest && !entry->can_split
 804               && dump_file && (dump_flags & TDF_DETAILS))
 805             fprintf (dump_file,
 806                      "found articulation at bb %i but can not split\n",
 807                      entry->bb->index);
 808           if (pos <= entry->earliest && entry->can_split)
 809              {
 810                if (dump_file && (dump_flags & TDF_DETAILS))
 811                  fprintf (dump_file, "found articulation at bb %i\n",
 812                           entry->bb->index);
 813                current.entry_bb = entry->bb;
 814                current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
 815                bitmap_and_compl (current.ssa_names_to_pass,
 816                                  entry->used_ssa_names, entry->set_ssa_names);
 817                current.header_time = overall_time - entry->overall_time;
 818                current.header_size = overall_size - entry->overall_size;
 819                current.split_time = entry->overall_time;
 820                current.split_size = entry->overall_size;
 821                current.split_bbs = entry->bbs_visited;
 822                consider_split (&current, entry->non_ssa_vars, return_bb);
 823                BITMAP_FREE (current.ssa_names_to_pass);
 824              }
 825         }
 826       /* Do actual DFS walk.  */
 827       if (entry->edge_num
 828           < (EDGE_COUNT (entry->bb->succs)
 829              + EDGE_COUNT (entry->bb->preds)))
 830         {
 831           edge e;
 832           basic_block dest;
 833           if (entry->edge_num < EDGE_COUNT (entry->bb->succs))
 834             {
 835               e = EDGE_SUCC (entry->bb, entry->edge_num);
 836               dest = e->dest;
 837             }
 838           else
 839             {
 840               e = EDGE_PRED (entry->bb, entry->edge_num
 841                              - EDGE_COUNT (entry->bb->succs));
 842               dest = e->src;
 843             }
 844
 845           entry->edge_num++;
 846
 847           /* New BB to visit, push it to the stack.  */
 848           if (dest != return_bb && dest != EXIT_BLOCK_PTR
 849               && !dest->aux)
 850             {
 851               stack_entry new_entry;
 852
 853               new_entry.bb = dest;
 854               new_entry.edge_num = 0;
 855               new_entry.overall_time
 856                  = VEC_index (bb_info, bb_info_vec, dest->index)->time;
 857               new_entry.overall_size
 858                  = VEC_index (bb_info, bb_info_vec, dest->index)->size;
 859               new_entry.earliest = INT_MAX;
 860               new_entry.set_ssa_names = BITMAP_ALLOC (NULL);
 861               new_entry.used_ssa_names = BITMAP_ALLOC (NULL);
 862               new_entry.bbs_visited = BITMAP_ALLOC (NULL);
 863               new_entry.non_ssa_vars = BITMAP_ALLOC (NULL);
 864               new_entry.can_split = true;
 865               bitmap_set_bit (new_entry.bbs_visited, dest->index);
 866               VEC_safe_push (stack_entry, heap, stack, &new_entry);
 867               dest->aux = (void *)(intptr_t)VEC_length (stack_entry, stack);
 868             }
 869           /* Back edge found, record the earliest point.  */
 870           else if ((intptr_t)dest->aux > 0
 871                    && (intptr_t)dest->aux < entry->earliest)
 872             entry->earliest = (intptr_t)dest->aux;
 873         }
 874       /* We are done with examing the edges. pop off the value from stack and
 875          merge stuff we cummulate during the walk.  */
 876       else if (entry->bb != ENTRY_BLOCK_PTR)
 877         {
 878           stack_entry *prev = VEC_index (stack_entry, stack,
 879                                          VEC_length (stack_entry, stack) - 2);
 880
 881           entry->bb->aux = (void *)(intptr_t)-1;
 882           prev->can_split &= entry->can_split;
 883           if (prev->set_ssa_names)
 884             {
 885               bitmap_ior_into (prev->set_ssa_names, entry->set_ssa_names);
 886               bitmap_ior_into (prev->used_ssa_names, entry->used_ssa_names);
 887               bitmap_ior_into (prev->bbs_visited, entry->bbs_visited);
 888               bitmap_ior_into (prev->non_ssa_vars, entry->non_ssa_vars);
 889             }
 890           if (prev->earliest > entry->earliest)
 891             prev->earliest = entry->earliest;
 892           prev->overall_time += entry->overall_time;
 893           prev->overall_size += entry->overall_size;
 894           BITMAP_FREE (entry->set_ssa_names);
 895           BITMAP_FREE (entry->used_ssa_names);
 896           BITMAP_FREE (entry->bbs_visited);
 897           BITMAP_FREE (entry->non_ssa_vars);
 898           VEC_pop (stack_entry, stack);
 899         }
 900       else
 901         VEC_pop (stack_entry, stack);
 902     }
 903   ENTRY_BLOCK_PTR->aux = NULL;
 904   FOR_EACH_BB (bb)
 905     bb->aux = NULL;
 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_sym_for_renaming (SSA_NAME_VAR (PHI_RESULT (stmt)));
 997           gsi_remove (&gsi, false);
 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 };