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