2013-11-21 Edward Smith-Rowland <3dw4rd@verizon.net>
[official-gcc.git] / gcc / ipa-split.c
blob2e8a062da6b59ffa3bf8fe53d38aa45bf8895558
1 /* Function splitting pass
2 Copyright (C) 2010-2013 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka <jh@suse.cz>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* The purpose of this pass is to split function bodies to improve
22 inlining. I.e. for function of the form:
24 func (...)
26 if (cheap_test)
27 something_small
28 else
29 something_big
32 Produce:
34 func.part (...)
36 something_big
39 func (...)
41 if (cheap_test)
42 something_small
43 else
44 func.part (...);
47 When func becomes inlinable and when cheap_test is often true, inlining func,
48 but not fund.part leads to performance improvement similar as inlining
49 original func while the code size growth is smaller.
51 The pass is organized in three stages:
52 1) Collect local info about basic block into BB_INFO structure and
53 compute function body estimated size and time.
54 2) Via DFS walk find all possible basic blocks where we can split
55 and chose best one.
56 3) If split point is found, split at the specified BB by creating a clone
57 and updating function to call it.
59 The decisions what functions to split are in execute_split_functions
60 and consider_split.
62 There are several possible future improvements for this pass including:
64 1) Splitting to break up large functions
65 2) Splitting to reduce stack frame usage
66 3) Allow split part of function to use values computed in the header part.
67 The values needs to be passed to split function, perhaps via same
68 interface as for nested functions or as argument.
69 4) Support for simple rematerialization. I.e. when split part use
70 value computed in header from function parameter in very cheap way, we
71 can just recompute it.
72 5) Support splitting of nested functions.
73 6) Support non-SSA arguments.
74 7) There is nothing preventing us from producing multiple parts of single function
75 when needed or splitting also the parts. */
77 #include "config.h"
78 #include "system.h"
79 #include "coretypes.h"
80 #include "tree.h"
81 #include "gimple.h"
82 #include "stringpool.h"
83 #include "expr.h"
84 #include "calls.h"
85 #include "gimplify.h"
86 #include "gimple-iterator.h"
87 #include "gimplify-me.h"
88 #include "gimple-walk.h"
89 #include "target.h"
90 #include "ipa-prop.h"
91 #include "gimple-ssa.h"
92 #include "tree-cfg.h"
93 #include "tree-phinodes.h"
94 #include "ssa-iterators.h"
95 #include "stringpool.h"
96 #include "tree-ssanames.h"
97 #include "tree-into-ssa.h"
98 #include "tree-dfa.h"
99 #include "tree-pass.h"
100 #include "flags.h"
101 #include "diagnostic.h"
102 #include "tree-dump.h"
103 #include "tree-inline.h"
104 #include "params.h"
105 #include "gimple-pretty-print.h"
106 #include "ipa-inline.h"
107 #include "cfgloop.h"
109 /* Per basic block info. */
111 typedef struct
113 unsigned int size;
114 unsigned int time;
115 } bb_info;
117 static vec<bb_info> bb_info_vec;
119 /* Description of split point. */
121 struct split_point
123 /* Size of the partitions. */
124 unsigned int header_time, header_size, split_time, split_size;
126 /* SSA names that need to be passed into spit function. */
127 bitmap ssa_names_to_pass;
129 /* Basic block where we split (that will become entry point of new function. */
130 basic_block entry_bb;
132 /* Basic blocks we are splitting away. */
133 bitmap split_bbs;
135 /* True when return value is computed on split part and thus it needs
136 to be returned. */
137 bool split_part_set_retval;
140 /* Best split point found. */
142 struct split_point best_split_point;
144 /* Set of basic blocks that are not allowed to dominate a split point. */
146 static bitmap forbidden_dominators;
148 static tree find_retval (basic_block return_bb);
150 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
151 variable, check it if it is present in bitmap passed via DATA. */
153 static bool
154 test_nonssa_use (gimple stmt ATTRIBUTE_UNUSED, tree t, void *data)
156 t = get_base_address (t);
158 if (!t || is_gimple_reg (t))
159 return false;
161 if (TREE_CODE (t) == PARM_DECL
162 || (TREE_CODE (t) == VAR_DECL
163 && auto_var_in_fn_p (t, current_function_decl))
164 || TREE_CODE (t) == RESULT_DECL
165 || TREE_CODE (t) == LABEL_DECL)
166 return bitmap_bit_p ((bitmap)data, DECL_UID (t));
168 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
169 to pretend that the value pointed to is actual result decl. */
170 if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
171 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
172 && SSA_NAME_VAR (TREE_OPERAND (t, 0))
173 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
174 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
175 return
176 bitmap_bit_p ((bitmap)data,
177 DECL_UID (DECL_RESULT (current_function_decl)));
179 return false;
182 /* Dump split point CURRENT. */
184 static void
185 dump_split_point (FILE * file, struct split_point *current)
187 fprintf (file,
188 "Split point at BB %i\n"
189 " header time: %i header size: %i\n"
190 " split time: %i split size: %i\n bbs: ",
191 current->entry_bb->index, current->header_time,
192 current->header_size, current->split_time, current->split_size);
193 dump_bitmap (file, current->split_bbs);
194 fprintf (file, " SSA names to pass: ");
195 dump_bitmap (file, current->ssa_names_to_pass);
198 /* Look for all BBs in header that might lead to the split part and verify
199 that they are not defining any non-SSA var used by the split part.
200 Parameters are the same as for consider_split. */
202 static bool
203 verify_non_ssa_vars (struct split_point *current, bitmap non_ssa_vars,
204 basic_block return_bb)
206 bitmap seen = BITMAP_ALLOC (NULL);
207 vec<basic_block> worklist = vNULL;
208 edge e;
209 edge_iterator ei;
210 bool ok = true;
212 FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
213 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
214 && !bitmap_bit_p (current->split_bbs, e->src->index))
216 worklist.safe_push (e->src);
217 bitmap_set_bit (seen, e->src->index);
220 while (!worklist.is_empty ())
222 gimple_stmt_iterator bsi;
223 basic_block bb = worklist.pop ();
225 FOR_EACH_EDGE (e, ei, bb->preds)
226 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
227 && bitmap_set_bit (seen, e->src->index))
229 gcc_checking_assert (!bitmap_bit_p (current->split_bbs,
230 e->src->index));
231 worklist.safe_push (e->src);
233 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
235 gimple stmt = gsi_stmt (bsi);
236 if (is_gimple_debug (stmt))
237 continue;
238 if (walk_stmt_load_store_addr_ops
239 (stmt, non_ssa_vars, test_nonssa_use, test_nonssa_use,
240 test_nonssa_use))
242 ok = false;
243 goto done;
245 if (gimple_code (stmt) == GIMPLE_LABEL
246 && test_nonssa_use (stmt, gimple_label_label (stmt),
247 non_ssa_vars))
249 ok = false;
250 goto done;
253 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
255 if (walk_stmt_load_store_addr_ops
256 (gsi_stmt (bsi), non_ssa_vars, test_nonssa_use, test_nonssa_use,
257 test_nonssa_use))
259 ok = false;
260 goto done;
263 FOR_EACH_EDGE (e, ei, bb->succs)
265 if (e->dest != return_bb)
266 continue;
267 for (bsi = gsi_start_phis (return_bb); !gsi_end_p (bsi);
268 gsi_next (&bsi))
270 gimple stmt = gsi_stmt (bsi);
271 tree op = gimple_phi_arg_def (stmt, e->dest_idx);
273 if (virtual_operand_p (gimple_phi_result (stmt)))
274 continue;
275 if (TREE_CODE (op) != SSA_NAME
276 && test_nonssa_use (stmt, op, non_ssa_vars))
278 ok = false;
279 goto done;
284 done:
285 BITMAP_FREE (seen);
286 worklist.release ();
287 return ok;
290 /* If STMT is a call, check the callee against a list of forbidden
291 predicate functions. If a match is found, look for uses of the
292 call result in condition statements that compare against zero.
293 For each such use, find the block targeted by the condition
294 statement for the nonzero result, and set the bit for this block
295 in the forbidden dominators bitmap. The purpose of this is to avoid
296 selecting a split point where we are likely to lose the chance
297 to optimize away an unused function call. */
299 static void
300 check_forbidden_calls (gimple stmt)
302 imm_use_iterator use_iter;
303 use_operand_p use_p;
304 tree lhs;
306 /* At the moment, __builtin_constant_p is the only forbidden
307 predicate function call (see PR49642). */
308 if (!gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
309 return;
311 lhs = gimple_call_lhs (stmt);
313 if (!lhs || TREE_CODE (lhs) != SSA_NAME)
314 return;
316 FOR_EACH_IMM_USE_FAST (use_p, use_iter, lhs)
318 tree op1;
319 basic_block use_bb, forbidden_bb;
320 enum tree_code code;
321 edge true_edge, false_edge;
322 gimple use_stmt = USE_STMT (use_p);
324 if (gimple_code (use_stmt) != GIMPLE_COND)
325 continue;
327 /* Assuming canonical form for GIMPLE_COND here, with constant
328 in second position. */
329 op1 = gimple_cond_rhs (use_stmt);
330 code = gimple_cond_code (use_stmt);
331 use_bb = gimple_bb (use_stmt);
333 extract_true_false_edges_from_block (use_bb, &true_edge, &false_edge);
335 /* We're only interested in comparisons that distinguish
336 unambiguously from zero. */
337 if (!integer_zerop (op1) || code == LE_EXPR || code == GE_EXPR)
338 continue;
340 if (code == EQ_EXPR)
341 forbidden_bb = false_edge->dest;
342 else
343 forbidden_bb = true_edge->dest;
345 bitmap_set_bit (forbidden_dominators, forbidden_bb->index);
349 /* If BB is dominated by any block in the forbidden dominators set,
350 return TRUE; else FALSE. */
352 static bool
353 dominated_by_forbidden (basic_block bb)
355 unsigned dom_bb;
356 bitmap_iterator bi;
358 EXECUTE_IF_SET_IN_BITMAP (forbidden_dominators, 1, dom_bb, bi)
360 if (dominated_by_p (CDI_DOMINATORS, bb, BASIC_BLOCK (dom_bb)))
361 return true;
364 return false;
367 /* We found an split_point CURRENT. NON_SSA_VARS is bitmap of all non ssa
368 variables used and RETURN_BB is return basic block.
369 See if we can split function here. */
371 static void
372 consider_split (struct split_point *current, bitmap non_ssa_vars,
373 basic_block return_bb)
375 tree parm;
376 unsigned int num_args = 0;
377 unsigned int call_overhead;
378 edge e;
379 edge_iterator ei;
380 gimple_stmt_iterator bsi;
381 unsigned int i;
382 int incoming_freq = 0;
383 tree retval;
384 bool back_edge = false;
386 if (dump_file && (dump_flags & TDF_DETAILS))
387 dump_split_point (dump_file, current);
389 FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
391 if (e->flags & EDGE_DFS_BACK)
392 back_edge = true;
393 if (!bitmap_bit_p (current->split_bbs, e->src->index))
394 incoming_freq += EDGE_FREQUENCY (e);
397 /* Do not split when we would end up calling function anyway. */
398 if (incoming_freq
399 >= (ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency
400 * PARAM_VALUE (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY) / 100))
402 /* When profile is guessed, we can not expect it to give us
403 realistic estimate on likelyness of function taking the
404 complex path. As a special case, when tail of the function is
405 a loop, enable splitting since inlining code skipping the loop
406 is likely noticeable win. */
407 if (back_edge
408 && profile_status != PROFILE_READ
409 && incoming_freq < ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency)
411 if (dump_file && (dump_flags & TDF_DETAILS))
412 fprintf (dump_file,
413 " Split before loop, accepting despite low frequencies %i %i.\n",
414 incoming_freq,
415 ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency);
417 else
419 if (dump_file && (dump_flags & TDF_DETAILS))
420 fprintf (dump_file,
421 " Refused: incoming frequency is too large.\n");
422 return;
426 if (!current->header_size)
428 if (dump_file && (dump_flags & TDF_DETAILS))
429 fprintf (dump_file, " Refused: header empty\n");
430 return;
433 /* Verify that PHI args on entry are either virtual or all their operands
434 incoming from header are the same. */
435 for (bsi = gsi_start_phis (current->entry_bb); !gsi_end_p (bsi); gsi_next (&bsi))
437 gimple stmt = gsi_stmt (bsi);
438 tree val = NULL;
440 if (virtual_operand_p (gimple_phi_result (stmt)))
441 continue;
442 for (i = 0; i < gimple_phi_num_args (stmt); i++)
444 edge e = gimple_phi_arg_edge (stmt, i);
445 if (!bitmap_bit_p (current->split_bbs, e->src->index))
447 tree edge_val = gimple_phi_arg_def (stmt, i);
448 if (val && edge_val != val)
450 if (dump_file && (dump_flags & TDF_DETAILS))
451 fprintf (dump_file,
452 " Refused: entry BB has PHI with multiple variants\n");
453 return;
455 val = edge_val;
461 /* See what argument we will pass to the split function and compute
462 call overhead. */
463 call_overhead = eni_size_weights.call_cost;
464 for (parm = DECL_ARGUMENTS (current_function_decl); parm;
465 parm = DECL_CHAIN (parm))
467 if (!is_gimple_reg (parm))
469 if (bitmap_bit_p (non_ssa_vars, DECL_UID (parm)))
471 if (dump_file && (dump_flags & TDF_DETAILS))
472 fprintf (dump_file,
473 " Refused: need to pass non-ssa param values\n");
474 return;
477 else
479 tree ddef = ssa_default_def (cfun, parm);
480 if (ddef
481 && bitmap_bit_p (current->ssa_names_to_pass,
482 SSA_NAME_VERSION (ddef)))
484 if (!VOID_TYPE_P (TREE_TYPE (parm)))
485 call_overhead += estimate_move_cost (TREE_TYPE (parm));
486 num_args++;
490 if (!VOID_TYPE_P (TREE_TYPE (current_function_decl)))
491 call_overhead += estimate_move_cost (TREE_TYPE (current_function_decl));
493 if (current->split_size <= call_overhead)
495 if (dump_file && (dump_flags & TDF_DETAILS))
496 fprintf (dump_file,
497 " Refused: split size is smaller than call overhead\n");
498 return;
500 if (current->header_size + call_overhead
501 >= (unsigned int)(DECL_DECLARED_INLINE_P (current_function_decl)
502 ? MAX_INLINE_INSNS_SINGLE
503 : MAX_INLINE_INSNS_AUTO))
505 if (dump_file && (dump_flags & TDF_DETAILS))
506 fprintf (dump_file,
507 " Refused: header size is too large for inline candidate\n");
508 return;
511 /* FIXME: we currently can pass only SSA function parameters to the split
512 arguments. Once parm_adjustment infrastructure is supported by cloning,
513 we can pass more than that. */
514 if (num_args != bitmap_count_bits (current->ssa_names_to_pass))
517 if (dump_file && (dump_flags & TDF_DETAILS))
518 fprintf (dump_file,
519 " Refused: need to pass non-param values\n");
520 return;
523 /* When there are non-ssa vars used in the split region, see if they
524 are used in the header region. If so, reject the split.
525 FIXME: we can use nested function support to access both. */
526 if (!bitmap_empty_p (non_ssa_vars)
527 && !verify_non_ssa_vars (current, non_ssa_vars, return_bb))
529 if (dump_file && (dump_flags & TDF_DETAILS))
530 fprintf (dump_file,
531 " Refused: split part has non-ssa uses\n");
532 return;
535 /* If the split point is dominated by a forbidden block, reject
536 the split. */
537 if (!bitmap_empty_p (forbidden_dominators)
538 && dominated_by_forbidden (current->entry_bb))
540 if (dump_file && (dump_flags & TDF_DETAILS))
541 fprintf (dump_file,
542 " Refused: split point dominated by forbidden block\n");
543 return;
546 /* See if retval used by return bb is computed by header or split part.
547 When it is computed by split part, we need to produce return statement
548 in the split part and add code to header to pass it around.
550 This is bit tricky to test:
551 1) When there is no return_bb or no return value, we always pass
552 value around.
553 2) Invariants are always computed by caller.
554 3) For SSA we need to look if defining statement is in header or split part
555 4) For non-SSA we need to look where the var is computed. */
556 retval = find_retval (return_bb);
557 if (!retval)
558 current->split_part_set_retval = true;
559 else if (is_gimple_min_invariant (retval))
560 current->split_part_set_retval = false;
561 /* Special case is value returned by reference we record as if it was non-ssa
562 set to result_decl. */
563 else if (TREE_CODE (retval) == SSA_NAME
564 && SSA_NAME_VAR (retval)
565 && TREE_CODE (SSA_NAME_VAR (retval)) == RESULT_DECL
566 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
567 current->split_part_set_retval
568 = bitmap_bit_p (non_ssa_vars, DECL_UID (SSA_NAME_VAR (retval)));
569 else if (TREE_CODE (retval) == SSA_NAME)
570 current->split_part_set_retval
571 = (!SSA_NAME_IS_DEFAULT_DEF (retval)
572 && (bitmap_bit_p (current->split_bbs,
573 gimple_bb (SSA_NAME_DEF_STMT (retval))->index)
574 || gimple_bb (SSA_NAME_DEF_STMT (retval)) == return_bb));
575 else if (TREE_CODE (retval) == PARM_DECL)
576 current->split_part_set_retval = false;
577 else if (TREE_CODE (retval) == VAR_DECL
578 || TREE_CODE (retval) == RESULT_DECL)
579 current->split_part_set_retval
580 = bitmap_bit_p (non_ssa_vars, DECL_UID (retval));
581 else
582 current->split_part_set_retval = true;
584 /* split_function fixes up at most one PHI non-virtual PHI node in return_bb,
585 for the return value. If there are other PHIs, give up. */
586 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
588 gimple_stmt_iterator psi;
590 for (psi = gsi_start_phis (return_bb); !gsi_end_p (psi); gsi_next (&psi))
591 if (!virtual_operand_p (gimple_phi_result (gsi_stmt (psi)))
592 && !(retval
593 && current->split_part_set_retval
594 && TREE_CODE (retval) == SSA_NAME
595 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))
596 && SSA_NAME_DEF_STMT (retval) == gsi_stmt (psi)))
598 if (dump_file && (dump_flags & TDF_DETAILS))
599 fprintf (dump_file,
600 " Refused: return bb has extra PHIs\n");
601 return;
605 if (dump_file && (dump_flags & TDF_DETAILS))
606 fprintf (dump_file, " Accepted!\n");
608 /* At the moment chose split point with lowest frequency and that leaves
609 out smallest size of header.
610 In future we might re-consider this heuristics. */
611 if (!best_split_point.split_bbs
612 || best_split_point.entry_bb->frequency > current->entry_bb->frequency
613 || (best_split_point.entry_bb->frequency == current->entry_bb->frequency
614 && best_split_point.split_size < current->split_size))
617 if (dump_file && (dump_flags & TDF_DETAILS))
618 fprintf (dump_file, " New best split point!\n");
619 if (best_split_point.ssa_names_to_pass)
621 BITMAP_FREE (best_split_point.ssa_names_to_pass);
622 BITMAP_FREE (best_split_point.split_bbs);
624 best_split_point = *current;
625 best_split_point.ssa_names_to_pass = BITMAP_ALLOC (NULL);
626 bitmap_copy (best_split_point.ssa_names_to_pass,
627 current->ssa_names_to_pass);
628 best_split_point.split_bbs = BITMAP_ALLOC (NULL);
629 bitmap_copy (best_split_point.split_bbs, current->split_bbs);
633 /* Return basic block containing RETURN statement. We allow basic blocks
634 of the form:
635 <retval> = tmp_var;
636 return <retval>
637 but return_bb can not be more complex than this.
638 If nothing is found, return the exit block.
640 When there are multiple RETURN statement, chose one with return value,
641 since that one is more likely shared by multiple code paths.
643 Return BB is special, because for function splitting it is the only
644 basic block that is duplicated in between header and split part of the
645 function.
647 TODO: We might support multiple return blocks. */
649 static basic_block
650 find_return_bb (void)
652 edge e;
653 basic_block return_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
654 gimple_stmt_iterator bsi;
655 bool found_return = false;
656 tree retval = NULL_TREE;
658 if (!single_pred_p (EXIT_BLOCK_PTR_FOR_FN (cfun)))
659 return return_bb;
661 e = single_pred_edge (EXIT_BLOCK_PTR_FOR_FN (cfun));
662 for (bsi = gsi_last_bb (e->src); !gsi_end_p (bsi); gsi_prev (&bsi))
664 gimple stmt = gsi_stmt (bsi);
665 if (gimple_code (stmt) == GIMPLE_LABEL
666 || is_gimple_debug (stmt)
667 || gimple_clobber_p (stmt))
669 else if (gimple_code (stmt) == GIMPLE_ASSIGN
670 && found_return
671 && gimple_assign_single_p (stmt)
672 && (auto_var_in_fn_p (gimple_assign_rhs1 (stmt),
673 current_function_decl)
674 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
675 && retval == gimple_assign_lhs (stmt))
677 else if (gimple_code (stmt) == GIMPLE_RETURN)
679 found_return = true;
680 retval = gimple_return_retval (stmt);
682 else
683 break;
685 if (gsi_end_p (bsi) && found_return)
686 return_bb = e->src;
688 return return_bb;
691 /* Given return basic block RETURN_BB, see where return value is really
692 stored. */
693 static tree
694 find_retval (basic_block return_bb)
696 gimple_stmt_iterator bsi;
697 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
698 if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
699 return gimple_return_retval (gsi_stmt (bsi));
700 else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN
701 && !gimple_clobber_p (gsi_stmt (bsi)))
702 return gimple_assign_rhs1 (gsi_stmt (bsi));
703 return NULL;
706 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
707 variable, mark it as used in bitmap passed via DATA.
708 Return true when access to T prevents splitting the function. */
710 static bool
711 mark_nonssa_use (gimple stmt ATTRIBUTE_UNUSED, tree t, void *data)
713 t = get_base_address (t);
715 if (!t || is_gimple_reg (t))
716 return false;
718 /* At present we can't pass non-SSA arguments to split function.
719 FIXME: this can be relaxed by passing references to arguments. */
720 if (TREE_CODE (t) == PARM_DECL)
722 if (dump_file && (dump_flags & TDF_DETAILS))
723 fprintf (dump_file,
724 "Cannot split: use of non-ssa function parameter.\n");
725 return true;
728 if ((TREE_CODE (t) == VAR_DECL
729 && auto_var_in_fn_p (t, current_function_decl))
730 || TREE_CODE (t) == RESULT_DECL
731 || TREE_CODE (t) == LABEL_DECL)
732 bitmap_set_bit ((bitmap)data, DECL_UID (t));
734 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
735 to pretend that the value pointed to is actual result decl. */
736 if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
737 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
738 && SSA_NAME_VAR (TREE_OPERAND (t, 0))
739 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
740 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
741 return
742 bitmap_bit_p ((bitmap)data,
743 DECL_UID (DECL_RESULT (current_function_decl)));
745 return false;
748 /* Compute local properties of basic block BB we collect when looking for
749 split points. We look for ssa defs and store them in SET_SSA_NAMES,
750 for ssa uses and store them in USED_SSA_NAMES and for any non-SSA automatic
751 vars stored in NON_SSA_VARS.
753 When BB has edge to RETURN_BB, collect uses in RETURN_BB too.
755 Return false when BB contains something that prevents it from being put into
756 split function. */
758 static bool
759 visit_bb (basic_block bb, basic_block return_bb,
760 bitmap set_ssa_names, bitmap used_ssa_names,
761 bitmap non_ssa_vars)
763 gimple_stmt_iterator bsi;
764 edge e;
765 edge_iterator ei;
766 bool can_split = true;
768 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
770 gimple stmt = gsi_stmt (bsi);
771 tree op;
772 ssa_op_iter iter;
773 tree decl;
775 if (is_gimple_debug (stmt))
776 continue;
778 if (gimple_clobber_p (stmt))
779 continue;
781 /* FIXME: We can split regions containing EH. We can not however
782 split RESX, EH_DISPATCH and EH_POINTER referring to same region
783 into different partitions. This would require tracking of
784 EH regions and checking in consider_split_point if they
785 are not used elsewhere. */
786 if (gimple_code (stmt) == GIMPLE_RESX)
788 if (dump_file && (dump_flags & TDF_DETAILS))
789 fprintf (dump_file, "Cannot split: resx.\n");
790 can_split = false;
792 if (gimple_code (stmt) == GIMPLE_EH_DISPATCH)
794 if (dump_file && (dump_flags & TDF_DETAILS))
795 fprintf (dump_file, "Cannot split: eh dispatch.\n");
796 can_split = false;
799 /* Check builtins that prevent splitting. */
800 if (gimple_code (stmt) == GIMPLE_CALL
801 && (decl = gimple_call_fndecl (stmt)) != NULL_TREE
802 && DECL_BUILT_IN (decl)
803 && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
804 switch (DECL_FUNCTION_CODE (decl))
806 /* FIXME: once we will allow passing non-parm values to split part,
807 we need to be sure to handle correct builtin_stack_save and
808 builtin_stack_restore. At the moment we are safe; there is no
809 way to store builtin_stack_save result in non-SSA variable
810 since all calls to those are compiler generated. */
811 case BUILT_IN_APPLY:
812 case BUILT_IN_APPLY_ARGS:
813 case BUILT_IN_VA_START:
814 if (dump_file && (dump_flags & TDF_DETAILS))
815 fprintf (dump_file,
816 "Cannot split: builtin_apply and va_start.\n");
817 can_split = false;
818 break;
819 case BUILT_IN_EH_POINTER:
820 if (dump_file && (dump_flags & TDF_DETAILS))
821 fprintf (dump_file, "Cannot split: builtin_eh_pointer.\n");
822 can_split = false;
823 break;
824 default:
825 break;
828 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
829 bitmap_set_bit (set_ssa_names, SSA_NAME_VERSION (op));
830 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
831 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
832 can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
833 mark_nonssa_use,
834 mark_nonssa_use,
835 mark_nonssa_use);
837 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
839 gimple stmt = gsi_stmt (bsi);
840 unsigned int i;
842 if (virtual_operand_p (gimple_phi_result (stmt)))
843 continue;
844 bitmap_set_bit (set_ssa_names,
845 SSA_NAME_VERSION (gimple_phi_result (stmt)));
846 for (i = 0; i < gimple_phi_num_args (stmt); i++)
848 tree op = gimple_phi_arg_def (stmt, i);
849 if (TREE_CODE (op) == SSA_NAME)
850 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
852 can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
853 mark_nonssa_use,
854 mark_nonssa_use,
855 mark_nonssa_use);
857 /* Record also uses coming from PHI operand in return BB. */
858 FOR_EACH_EDGE (e, ei, bb->succs)
859 if (e->dest == return_bb)
861 for (bsi = gsi_start_phis (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
863 gimple stmt = gsi_stmt (bsi);
864 tree op = gimple_phi_arg_def (stmt, e->dest_idx);
866 if (virtual_operand_p (gimple_phi_result (stmt)))
867 continue;
868 if (TREE_CODE (op) == SSA_NAME)
869 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
870 else
871 can_split &= !mark_nonssa_use (stmt, op, non_ssa_vars);
874 return can_split;
877 /* Stack entry for recursive DFS walk in find_split_point. */
879 typedef struct
881 /* Basic block we are examining. */
882 basic_block bb;
884 /* SSA names set and used by the BB and all BBs reachable
885 from it via DFS walk. */
886 bitmap set_ssa_names, used_ssa_names;
887 bitmap non_ssa_vars;
889 /* All BBS visited from this BB via DFS walk. */
890 bitmap bbs_visited;
892 /* Last examined edge in DFS walk. Since we walk unoriented graph,
893 the value is up to sum of incoming and outgoing edges of BB. */
894 unsigned int edge_num;
896 /* Stack entry index of earliest BB reachable from current BB
897 or any BB visited later in DFS walk. */
898 int earliest;
900 /* Overall time and size of all BBs reached from this BB in DFS walk. */
901 int overall_time, overall_size;
903 /* When false we can not split on this BB. */
904 bool can_split;
905 } stack_entry;
908 /* Find all articulations and call consider_split on them.
909 OVERALL_TIME and OVERALL_SIZE is time and size of the function.
911 We perform basic algorithm for finding an articulation in a graph
912 created from CFG by considering it to be an unoriented graph.
914 The articulation is discovered via DFS walk. We collect earliest
915 basic block on stack that is reachable via backward edge. Articulation
916 is any basic block such that there is no backward edge bypassing it.
917 To reduce stack usage we maintain heap allocated stack in STACK vector.
918 AUX pointer of BB is set to index it appears in the stack or -1 once
919 it is visited and popped off the stack.
921 The algorithm finds articulation after visiting the whole component
922 reachable by it. This makes it convenient to collect information about
923 the component used by consider_split. */
925 static void
926 find_split_points (int overall_time, int overall_size)
928 stack_entry first;
929 vec<stack_entry> stack = vNULL;
930 basic_block bb;
931 basic_block return_bb = find_return_bb ();
932 struct split_point current;
934 current.header_time = overall_time;
935 current.header_size = overall_size;
936 current.split_time = 0;
937 current.split_size = 0;
938 current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
940 first.bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
941 first.edge_num = 0;
942 first.overall_time = 0;
943 first.overall_size = 0;
944 first.earliest = INT_MAX;
945 first.set_ssa_names = 0;
946 first.used_ssa_names = 0;
947 first.bbs_visited = 0;
948 stack.safe_push (first);
949 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(intptr_t)-1;
951 while (!stack.is_empty ())
953 stack_entry *entry = &stack.last ();
955 /* We are walking an acyclic graph, so edge_num counts
956 succ and pred edges together. However when considering
957 articulation, we want to have processed everything reachable
958 from articulation but nothing that reaches into it. */
959 if (entry->edge_num == EDGE_COUNT (entry->bb->succs)
960 && entry->bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
962 int pos = stack.length ();
963 entry->can_split &= visit_bb (entry->bb, return_bb,
964 entry->set_ssa_names,
965 entry->used_ssa_names,
966 entry->non_ssa_vars);
967 if (pos <= entry->earliest && !entry->can_split
968 && dump_file && (dump_flags & TDF_DETAILS))
969 fprintf (dump_file,
970 "found articulation at bb %i but can not split\n",
971 entry->bb->index);
972 if (pos <= entry->earliest && entry->can_split)
974 if (dump_file && (dump_flags & TDF_DETAILS))
975 fprintf (dump_file, "found articulation at bb %i\n",
976 entry->bb->index);
977 current.entry_bb = entry->bb;
978 current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
979 bitmap_and_compl (current.ssa_names_to_pass,
980 entry->used_ssa_names, entry->set_ssa_names);
981 current.header_time = overall_time - entry->overall_time;
982 current.header_size = overall_size - entry->overall_size;
983 current.split_time = entry->overall_time;
984 current.split_size = entry->overall_size;
985 current.split_bbs = entry->bbs_visited;
986 consider_split (&current, entry->non_ssa_vars, return_bb);
987 BITMAP_FREE (current.ssa_names_to_pass);
990 /* Do actual DFS walk. */
991 if (entry->edge_num
992 < (EDGE_COUNT (entry->bb->succs)
993 + EDGE_COUNT (entry->bb->preds)))
995 edge e;
996 basic_block dest;
997 if (entry->edge_num < EDGE_COUNT (entry->bb->succs))
999 e = EDGE_SUCC (entry->bb, entry->edge_num);
1000 dest = e->dest;
1002 else
1004 e = EDGE_PRED (entry->bb, entry->edge_num
1005 - EDGE_COUNT (entry->bb->succs));
1006 dest = e->src;
1009 entry->edge_num++;
1011 /* New BB to visit, push it to the stack. */
1012 if (dest != return_bb && dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1013 && !dest->aux)
1015 stack_entry new_entry;
1017 new_entry.bb = dest;
1018 new_entry.edge_num = 0;
1019 new_entry.overall_time
1020 = bb_info_vec[dest->index].time;
1021 new_entry.overall_size
1022 = bb_info_vec[dest->index].size;
1023 new_entry.earliest = INT_MAX;
1024 new_entry.set_ssa_names = BITMAP_ALLOC (NULL);
1025 new_entry.used_ssa_names = BITMAP_ALLOC (NULL);
1026 new_entry.bbs_visited = BITMAP_ALLOC (NULL);
1027 new_entry.non_ssa_vars = BITMAP_ALLOC (NULL);
1028 new_entry.can_split = true;
1029 bitmap_set_bit (new_entry.bbs_visited, dest->index);
1030 stack.safe_push (new_entry);
1031 dest->aux = (void *)(intptr_t)stack.length ();
1033 /* Back edge found, record the earliest point. */
1034 else if ((intptr_t)dest->aux > 0
1035 && (intptr_t)dest->aux < entry->earliest)
1036 entry->earliest = (intptr_t)dest->aux;
1038 /* We are done with examining the edges. Pop off the value from stack
1039 and merge stuff we accumulate during the walk. */
1040 else if (entry->bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1042 stack_entry *prev = &stack[stack.length () - 2];
1044 entry->bb->aux = (void *)(intptr_t)-1;
1045 prev->can_split &= entry->can_split;
1046 if (prev->set_ssa_names)
1048 bitmap_ior_into (prev->set_ssa_names, entry->set_ssa_names);
1049 bitmap_ior_into (prev->used_ssa_names, entry->used_ssa_names);
1050 bitmap_ior_into (prev->bbs_visited, entry->bbs_visited);
1051 bitmap_ior_into (prev->non_ssa_vars, entry->non_ssa_vars);
1053 if (prev->earliest > entry->earliest)
1054 prev->earliest = entry->earliest;
1055 prev->overall_time += entry->overall_time;
1056 prev->overall_size += entry->overall_size;
1057 BITMAP_FREE (entry->set_ssa_names);
1058 BITMAP_FREE (entry->used_ssa_names);
1059 BITMAP_FREE (entry->bbs_visited);
1060 BITMAP_FREE (entry->non_ssa_vars);
1061 stack.pop ();
1063 else
1064 stack.pop ();
1066 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = NULL;
1067 FOR_EACH_BB (bb)
1068 bb->aux = NULL;
1069 stack.release ();
1070 BITMAP_FREE (current.ssa_names_to_pass);
1073 /* Split function at SPLIT_POINT. */
1075 static void
1076 split_function (struct split_point *split_point)
1078 vec<tree> args_to_pass = vNULL;
1079 bitmap args_to_skip;
1080 tree parm;
1081 int num = 0;
1082 struct cgraph_node *node, *cur_node = cgraph_get_node (current_function_decl);
1083 basic_block return_bb = find_return_bb ();
1084 basic_block call_bb;
1085 gimple_stmt_iterator gsi;
1086 gimple call;
1087 edge e;
1088 edge_iterator ei;
1089 tree retval = NULL, real_retval = NULL;
1090 bool split_part_return_p = false;
1091 gimple last_stmt = NULL;
1092 unsigned int i;
1093 tree arg, ddef;
1094 vec<tree, va_gc> **debug_args = NULL;
1096 if (dump_file)
1098 fprintf (dump_file, "\n\nSplitting function at:\n");
1099 dump_split_point (dump_file, split_point);
1102 if (cur_node->local.can_change_signature)
1103 args_to_skip = BITMAP_ALLOC (NULL);
1104 else
1105 args_to_skip = NULL;
1107 /* Collect the parameters of new function and args_to_skip bitmap. */
1108 for (parm = DECL_ARGUMENTS (current_function_decl);
1109 parm; parm = DECL_CHAIN (parm), num++)
1110 if (args_to_skip
1111 && (!is_gimple_reg (parm)
1112 || (ddef = ssa_default_def (cfun, parm)) == NULL_TREE
1113 || !bitmap_bit_p (split_point->ssa_names_to_pass,
1114 SSA_NAME_VERSION (ddef))))
1115 bitmap_set_bit (args_to_skip, num);
1116 else
1118 /* This parm might not have been used up to now, but is going to be
1119 used, hence register it. */
1120 if (is_gimple_reg (parm))
1121 arg = get_or_create_ssa_default_def (cfun, parm);
1122 else
1123 arg = parm;
1125 if (!useless_type_conversion_p (DECL_ARG_TYPE (parm), TREE_TYPE (arg)))
1126 arg = fold_convert (DECL_ARG_TYPE (parm), arg);
1127 args_to_pass.safe_push (arg);
1130 /* See if the split function will return. */
1131 FOR_EACH_EDGE (e, ei, return_bb->preds)
1132 if (bitmap_bit_p (split_point->split_bbs, e->src->index))
1133 break;
1134 if (e)
1135 split_part_return_p = true;
1137 /* Add return block to what will become the split function.
1138 We do not return; no return block is needed. */
1139 if (!split_part_return_p)
1141 /* We have no return block, so nothing is needed. */
1142 else if (return_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1144 /* When we do not want to return value, we need to construct
1145 new return block with empty return statement.
1146 FIXME: Once we are able to change return type, we should change function
1147 to return void instead of just outputting function with undefined return
1148 value. For structures this affects quality of codegen. */
1149 else if (!split_point->split_part_set_retval
1150 && find_retval (return_bb))
1152 bool redirected = true;
1153 basic_block new_return_bb = create_basic_block (NULL, 0, return_bb);
1154 gimple_stmt_iterator gsi = gsi_start_bb (new_return_bb);
1155 gsi_insert_after (&gsi, gimple_build_return (NULL), GSI_NEW_STMT);
1156 while (redirected)
1158 redirected = false;
1159 FOR_EACH_EDGE (e, ei, return_bb->preds)
1160 if (bitmap_bit_p (split_point->split_bbs, e->src->index))
1162 new_return_bb->count += e->count;
1163 new_return_bb->frequency += EDGE_FREQUENCY (e);
1164 redirect_edge_and_branch (e, new_return_bb);
1165 redirected = true;
1166 break;
1169 e = make_edge (new_return_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
1170 e->probability = REG_BR_PROB_BASE;
1171 e->count = new_return_bb->count;
1172 if (current_loops)
1173 add_bb_to_loop (new_return_bb, current_loops->tree_root);
1174 bitmap_set_bit (split_point->split_bbs, new_return_bb->index);
1176 /* When we pass around the value, use existing return block. */
1177 else
1178 bitmap_set_bit (split_point->split_bbs, return_bb->index);
1180 /* If RETURN_BB has virtual operand PHIs, they must be removed and the
1181 virtual operand marked for renaming as we change the CFG in a way that
1182 tree-inline is not able to compensate for.
1184 Note this can happen whether or not we have a return value. If we have
1185 a return value, then RETURN_BB may have PHIs for real operands too. */
1186 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1188 bool phi_p = false;
1189 for (gsi = gsi_start_phis (return_bb); !gsi_end_p (gsi);)
1191 gimple stmt = gsi_stmt (gsi);
1192 if (!virtual_operand_p (gimple_phi_result (stmt)))
1194 gsi_next (&gsi);
1195 continue;
1197 mark_virtual_phi_result_for_renaming (stmt);
1198 remove_phi_node (&gsi, true);
1199 phi_p = true;
1201 /* In reality we have to rename the reaching definition of the
1202 virtual operand at return_bb as we will eventually release it
1203 when we remove the code region we outlined.
1204 So we have to rename all immediate virtual uses of that region
1205 if we didn't see a PHI definition yet. */
1206 /* ??? In real reality we want to set the reaching vdef of the
1207 entry of the SESE region as the vuse of the call and the reaching
1208 vdef of the exit of the SESE region as the vdef of the call. */
1209 if (!phi_p)
1210 for (gsi = gsi_start_bb (return_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1212 gimple stmt = gsi_stmt (gsi);
1213 if (gimple_vuse (stmt))
1215 gimple_set_vuse (stmt, NULL_TREE);
1216 update_stmt (stmt);
1218 if (gimple_vdef (stmt))
1219 break;
1223 /* Now create the actual clone. */
1224 rebuild_cgraph_edges ();
1225 node = cgraph_function_versioning (cur_node, vNULL,
1226 NULL,
1227 args_to_skip,
1228 !split_part_return_p,
1229 split_point->split_bbs,
1230 split_point->entry_bb, "part");
1231 /* For usual cloning it is enough to clear builtin only when signature
1232 changes. For partial inlining we however can not expect the part
1233 of builtin implementation to have same semantic as the whole. */
1234 if (DECL_BUILT_IN (node->decl))
1236 DECL_BUILT_IN_CLASS (node->decl) = NOT_BUILT_IN;
1237 DECL_FUNCTION_CODE (node->decl) = (enum built_in_function) 0;
1239 /* If the original function is declared inline, there is no point in issuing
1240 a warning for the non-inlinable part. */
1241 DECL_NO_INLINE_WARNING_P (node->decl) = 1;
1242 cgraph_node_remove_callees (cur_node);
1243 ipa_remove_all_references (&cur_node->ref_list);
1244 if (!split_part_return_p)
1245 TREE_THIS_VOLATILE (node->decl) = 1;
1246 if (dump_file)
1247 dump_function_to_file (node->decl, dump_file, dump_flags);
1249 /* Create the basic block we place call into. It is the entry basic block
1250 split after last label. */
1251 call_bb = split_point->entry_bb;
1252 for (gsi = gsi_start_bb (call_bb); !gsi_end_p (gsi);)
1253 if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
1255 last_stmt = gsi_stmt (gsi);
1256 gsi_next (&gsi);
1258 else
1259 break;
1260 e = split_block (split_point->entry_bb, last_stmt);
1261 remove_edge (e);
1263 /* Produce the call statement. */
1264 gsi = gsi_last_bb (call_bb);
1265 FOR_EACH_VEC_ELT (args_to_pass, i, arg)
1266 if (!is_gimple_val (arg))
1268 arg = force_gimple_operand_gsi (&gsi, arg, true, NULL_TREE,
1269 false, GSI_CONTINUE_LINKING);
1270 args_to_pass[i] = arg;
1272 call = gimple_build_call_vec (node->decl, args_to_pass);
1273 gimple_set_block (call, DECL_INITIAL (current_function_decl));
1274 args_to_pass.release ();
1276 /* For optimized away parameters, add on the caller side
1277 before the call
1278 DEBUG D#X => parm_Y(D)
1279 stmts and associate D#X with parm in decl_debug_args_lookup
1280 vector to say for debug info that if parameter parm had been passed,
1281 it would have value parm_Y(D). */
1282 if (args_to_skip)
1283 for (parm = DECL_ARGUMENTS (current_function_decl), num = 0;
1284 parm; parm = DECL_CHAIN (parm), num++)
1285 if (bitmap_bit_p (args_to_skip, num)
1286 && is_gimple_reg (parm))
1288 tree ddecl;
1289 gimple def_temp;
1291 /* This needs to be done even without MAY_HAVE_DEBUG_STMTS,
1292 otherwise if it didn't exist before, we'd end up with
1293 different SSA_NAME_VERSIONs between -g and -g0. */
1294 arg = get_or_create_ssa_default_def (cfun, parm);
1295 if (!MAY_HAVE_DEBUG_STMTS)
1296 continue;
1298 if (debug_args == NULL)
1299 debug_args = decl_debug_args_insert (node->decl);
1300 ddecl = make_node (DEBUG_EXPR_DECL);
1301 DECL_ARTIFICIAL (ddecl) = 1;
1302 TREE_TYPE (ddecl) = TREE_TYPE (parm);
1303 DECL_MODE (ddecl) = DECL_MODE (parm);
1304 vec_safe_push (*debug_args, DECL_ORIGIN (parm));
1305 vec_safe_push (*debug_args, ddecl);
1306 def_temp = gimple_build_debug_bind (ddecl, unshare_expr (arg),
1307 call);
1308 gsi_insert_after (&gsi, def_temp, GSI_NEW_STMT);
1310 /* And on the callee side, add
1311 DEBUG D#Y s=> parm
1312 DEBUG var => D#Y
1313 stmts to the first bb where var is a VAR_DECL created for the
1314 optimized away parameter in DECL_INITIAL block. This hints
1315 in the debug info that var (whole DECL_ORIGIN is the parm PARM_DECL)
1316 is optimized away, but could be looked up at the call site
1317 as value of D#X there. */
1318 if (debug_args != NULL)
1320 unsigned int i;
1321 tree var, vexpr;
1322 gimple_stmt_iterator cgsi;
1323 gimple def_temp;
1325 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1326 var = BLOCK_VARS (DECL_INITIAL (node->decl));
1327 i = vec_safe_length (*debug_args);
1328 cgsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1331 i -= 2;
1332 while (var != NULL_TREE
1333 && DECL_ABSTRACT_ORIGIN (var) != (**debug_args)[i])
1334 var = TREE_CHAIN (var);
1335 if (var == NULL_TREE)
1336 break;
1337 vexpr = make_node (DEBUG_EXPR_DECL);
1338 parm = (**debug_args)[i];
1339 DECL_ARTIFICIAL (vexpr) = 1;
1340 TREE_TYPE (vexpr) = TREE_TYPE (parm);
1341 DECL_MODE (vexpr) = DECL_MODE (parm);
1342 def_temp = gimple_build_debug_source_bind (vexpr, parm,
1343 NULL);
1344 gsi_insert_before (&cgsi, def_temp, GSI_SAME_STMT);
1345 def_temp = gimple_build_debug_bind (var, vexpr, NULL);
1346 gsi_insert_before (&cgsi, def_temp, GSI_SAME_STMT);
1348 while (i);
1349 pop_cfun ();
1352 /* We avoid address being taken on any variable used by split part,
1353 so return slot optimization is always possible. Moreover this is
1354 required to make DECL_BY_REFERENCE work. */
1355 if (aggregate_value_p (DECL_RESULT (current_function_decl),
1356 TREE_TYPE (current_function_decl))
1357 && (!is_gimple_reg_type (TREE_TYPE (DECL_RESULT (current_function_decl)))
1358 || DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))))
1359 gimple_call_set_return_slot_opt (call, true);
1361 /* Update return value. This is bit tricky. When we do not return,
1362 do nothing. When we return we might need to update return_bb
1363 or produce a new return statement. */
1364 if (!split_part_return_p)
1365 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1366 else
1368 e = make_edge (call_bb, return_bb,
1369 return_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1370 ? 0 : EDGE_FALLTHRU);
1371 e->count = call_bb->count;
1372 e->probability = REG_BR_PROB_BASE;
1374 /* If there is return basic block, see what value we need to store
1375 return value into and put call just before it. */
1376 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1378 real_retval = retval = find_retval (return_bb);
1380 if (real_retval && split_point->split_part_set_retval)
1382 gimple_stmt_iterator psi;
1384 /* See if we need new SSA_NAME for the result.
1385 When DECL_BY_REFERENCE is true, retval is actually pointer to
1386 return value and it is constant in whole function. */
1387 if (TREE_CODE (retval) == SSA_NAME
1388 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1390 retval = copy_ssa_name (retval, call);
1392 /* See if there is PHI defining return value. */
1393 for (psi = gsi_start_phis (return_bb);
1394 !gsi_end_p (psi); gsi_next (&psi))
1395 if (!virtual_operand_p (gimple_phi_result (gsi_stmt (psi))))
1396 break;
1398 /* When there is PHI, just update its value. */
1399 if (TREE_CODE (retval) == SSA_NAME
1400 && !gsi_end_p (psi))
1401 add_phi_arg (gsi_stmt (psi), retval, e, UNKNOWN_LOCATION);
1402 /* Otherwise update the return BB itself.
1403 find_return_bb allows at most one assignment to return value,
1404 so update first statement. */
1405 else
1407 gimple_stmt_iterator bsi;
1408 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi);
1409 gsi_next (&bsi))
1410 if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
1412 gimple_return_set_retval (gsi_stmt (bsi), retval);
1413 break;
1415 else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN
1416 && !gimple_clobber_p (gsi_stmt (bsi)))
1418 gimple_assign_set_rhs1 (gsi_stmt (bsi), retval);
1419 break;
1421 update_stmt (gsi_stmt (bsi));
1424 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1426 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1427 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1429 else
1431 tree restype;
1432 restype = TREE_TYPE (DECL_RESULT (current_function_decl));
1433 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1434 if (!useless_type_conversion_p (TREE_TYPE (retval), restype))
1436 gimple cpy;
1437 tree tem = create_tmp_reg (restype, NULL);
1438 tem = make_ssa_name (tem, call);
1439 cpy = gimple_build_assign_with_ops (NOP_EXPR, retval,
1440 tem, NULL_TREE);
1441 gsi_insert_after (&gsi, cpy, GSI_NEW_STMT);
1442 retval = tem;
1444 gimple_call_set_lhs (call, retval);
1445 update_stmt (call);
1448 else
1449 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1451 /* We don't use return block (there is either no return in function or
1452 multiple of them). So create new basic block with return statement.
1454 else
1456 gimple ret;
1457 if (split_point->split_part_set_retval
1458 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl))))
1460 retval = DECL_RESULT (current_function_decl);
1462 /* We use temporary register to hold value when aggregate_value_p
1463 is false. Similarly for DECL_BY_REFERENCE we must avoid extra
1464 copy. */
1465 if (!aggregate_value_p (retval, TREE_TYPE (current_function_decl))
1466 && !DECL_BY_REFERENCE (retval))
1467 retval = create_tmp_reg (TREE_TYPE (retval), NULL);
1468 if (is_gimple_reg (retval))
1470 /* When returning by reference, there is only one SSA name
1471 assigned to RESULT_DECL (that is pointer to return value).
1472 Look it up or create new one if it is missing. */
1473 if (DECL_BY_REFERENCE (retval))
1474 retval = get_or_create_ssa_default_def (cfun, retval);
1475 /* Otherwise produce new SSA name for return value. */
1476 else
1477 retval = make_ssa_name (retval, call);
1479 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1480 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1481 else
1482 gimple_call_set_lhs (call, retval);
1484 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1485 ret = gimple_build_return (retval);
1486 gsi_insert_after (&gsi, ret, GSI_NEW_STMT);
1489 free_dominance_info (CDI_DOMINATORS);
1490 free_dominance_info (CDI_POST_DOMINATORS);
1491 compute_inline_parameters (node, true);
1494 /* Execute function splitting pass. */
1496 static unsigned int
1497 execute_split_functions (void)
1499 gimple_stmt_iterator bsi;
1500 basic_block bb;
1501 int overall_time = 0, overall_size = 0;
1502 int todo = 0;
1503 struct cgraph_node *node = cgraph_get_node (current_function_decl);
1505 if (flags_from_decl_or_type (current_function_decl)
1506 & (ECF_NORETURN|ECF_MALLOC))
1508 if (dump_file)
1509 fprintf (dump_file, "Not splitting: noreturn/malloc function.\n");
1510 return 0;
1512 if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
1514 if (dump_file)
1515 fprintf (dump_file, "Not splitting: main function.\n");
1516 return 0;
1518 /* This can be relaxed; function might become inlinable after splitting
1519 away the uninlinable part. */
1520 if (inline_edge_summary_vec.exists ()
1521 && !inline_summary (node)->inlinable)
1523 if (dump_file)
1524 fprintf (dump_file, "Not splitting: not inlinable.\n");
1525 return 0;
1527 if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
1529 if (dump_file)
1530 fprintf (dump_file, "Not splitting: disregarding inline limits.\n");
1531 return 0;
1533 /* This can be relaxed; most of versioning tests actually prevents
1534 a duplication. */
1535 if (!tree_versionable_function_p (current_function_decl))
1537 if (dump_file)
1538 fprintf (dump_file, "Not splitting: not versionable.\n");
1539 return 0;
1541 /* FIXME: we could support this. */
1542 if (DECL_STRUCT_FUNCTION (current_function_decl)->static_chain_decl)
1544 if (dump_file)
1545 fprintf (dump_file, "Not splitting: nested function.\n");
1546 return 0;
1549 /* See if it makes sense to try to split.
1550 It makes sense to split if we inline, that is if we have direct calls to
1551 handle or direct calls are possibly going to appear as result of indirect
1552 inlining or LTO. Also handle -fprofile-generate as LTO to allow non-LTO
1553 training for LTO -fprofile-use build.
1555 Note that we are not completely conservative about disqualifying functions
1556 called once. It is possible that the caller is called more then once and
1557 then inlining would still benefit. */
1558 if ((!node->callers
1559 /* Local functions called once will be completely inlined most of time. */
1560 || (!node->callers->next_caller && node->local.local))
1561 && !node->address_taken
1562 && (!flag_lto || !node->externally_visible))
1564 if (dump_file)
1565 fprintf (dump_file, "Not splitting: not called directly "
1566 "or called once.\n");
1567 return 0;
1570 /* FIXME: We can actually split if splitting reduces call overhead. */
1571 if (!flag_inline_small_functions
1572 && !DECL_DECLARED_INLINE_P (current_function_decl))
1574 if (dump_file)
1575 fprintf (dump_file, "Not splitting: not autoinlining and function"
1576 " is not inline.\n");
1577 return 0;
1580 /* We enforce splitting after loop headers when profile info is not
1581 available. */
1582 if (profile_status != PROFILE_READ)
1583 mark_dfs_back_edges ();
1585 /* Initialize bitmap to track forbidden calls. */
1586 forbidden_dominators = BITMAP_ALLOC (NULL);
1587 calculate_dominance_info (CDI_DOMINATORS);
1589 /* Compute local info about basic blocks and determine function size/time. */
1590 bb_info_vec.safe_grow_cleared (last_basic_block + 1);
1591 memset (&best_split_point, 0, sizeof (best_split_point));
1592 FOR_EACH_BB (bb)
1594 int time = 0;
1595 int size = 0;
1596 int freq = compute_call_stmt_bb_frequency (current_function_decl, bb);
1598 if (dump_file && (dump_flags & TDF_DETAILS))
1599 fprintf (dump_file, "Basic block %i\n", bb->index);
1601 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1603 int this_time, this_size;
1604 gimple stmt = gsi_stmt (bsi);
1606 this_size = estimate_num_insns (stmt, &eni_size_weights);
1607 this_time = estimate_num_insns (stmt, &eni_time_weights) * freq;
1608 size += this_size;
1609 time += this_time;
1610 check_forbidden_calls (stmt);
1612 if (dump_file && (dump_flags & TDF_DETAILS))
1614 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1615 freq, this_size, this_time);
1616 print_gimple_stmt (dump_file, stmt, 0, 0);
1619 overall_time += time;
1620 overall_size += size;
1621 bb_info_vec[bb->index].time = time;
1622 bb_info_vec[bb->index].size = size;
1624 find_split_points (overall_time, overall_size);
1625 if (best_split_point.split_bbs)
1627 split_function (&best_split_point);
1628 BITMAP_FREE (best_split_point.ssa_names_to_pass);
1629 BITMAP_FREE (best_split_point.split_bbs);
1630 todo = TODO_update_ssa | TODO_cleanup_cfg;
1632 BITMAP_FREE (forbidden_dominators);
1633 bb_info_vec.release ();
1634 return todo;
1637 /* Gate function splitting pass. When doing profile feedback, we want
1638 to execute the pass after profiling is read. So disable one in
1639 early optimization. */
1641 static bool
1642 gate_split_functions (void)
1644 return (flag_partial_inlining
1645 && !profile_arc_flag && !flag_branch_probabilities);
1648 namespace {
1650 const pass_data pass_data_split_functions =
1652 GIMPLE_PASS, /* type */
1653 "fnsplit", /* name */
1654 OPTGROUP_NONE, /* optinfo_flags */
1655 true, /* has_gate */
1656 true, /* has_execute */
1657 TV_IPA_FNSPLIT, /* tv_id */
1658 PROP_cfg, /* properties_required */
1659 0, /* properties_provided */
1660 0, /* properties_destroyed */
1661 0, /* todo_flags_start */
1662 TODO_verify_all, /* todo_flags_finish */
1665 class pass_split_functions : public gimple_opt_pass
1667 public:
1668 pass_split_functions (gcc::context *ctxt)
1669 : gimple_opt_pass (pass_data_split_functions, ctxt)
1672 /* opt_pass methods: */
1673 bool gate () { return gate_split_functions (); }
1674 unsigned int execute () { return execute_split_functions (); }
1676 }; // class pass_split_functions
1678 } // anon namespace
1680 gimple_opt_pass *
1681 make_pass_split_functions (gcc::context *ctxt)
1683 return new pass_split_functions (ctxt);
1686 /* Gate feedback driven function splitting pass.
1687 We don't need to split when profiling at all, we are producing
1688 lousy code anyway. */
1690 static bool
1691 gate_feedback_split_functions (void)
1693 return (flag_partial_inlining
1694 && flag_branch_probabilities);
1697 /* Execute function splitting pass. */
1699 static unsigned int
1700 execute_feedback_split_functions (void)
1702 unsigned int retval = execute_split_functions ();
1703 if (retval)
1704 retval |= TODO_rebuild_cgraph_edges;
1705 return retval;
1708 namespace {
1710 const pass_data pass_data_feedback_split_functions =
1712 GIMPLE_PASS, /* type */
1713 "feedback_fnsplit", /* name */
1714 OPTGROUP_NONE, /* optinfo_flags */
1715 true, /* has_gate */
1716 true, /* has_execute */
1717 TV_IPA_FNSPLIT, /* tv_id */
1718 PROP_cfg, /* properties_required */
1719 0, /* properties_provided */
1720 0, /* properties_destroyed */
1721 0, /* todo_flags_start */
1722 TODO_verify_all, /* todo_flags_finish */
1725 class pass_feedback_split_functions : public gimple_opt_pass
1727 public:
1728 pass_feedback_split_functions (gcc::context *ctxt)
1729 : gimple_opt_pass (pass_data_feedback_split_functions, ctxt)
1732 /* opt_pass methods: */
1733 bool gate () { return gate_feedback_split_functions (); }
1734 unsigned int execute () { return execute_feedback_split_functions (); }
1736 }; // class pass_feedback_split_functions
1738 } // anon namespace
1740 gimple_opt_pass *
1741 make_pass_feedback_split_functions (gcc::context *ctxt)
1743 return new pass_feedback_split_functions (ctxt);