gcc/ipa-split.c

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