gcc/ipa-split.c

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