gcc/ipa-split.c

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