gcc/ipa-split.c

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