Daily bump.
[official-gcc.git] / gcc / ipa-split.c
blobb03ae02924aab68df6bac2a921e5ddb066698dfb
1 /* Function splitting pass
2 Copyright (C) 2010-2018 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 "backend.h"
81 #include "rtl.h"
82 #include "tree.h"
83 #include "gimple.h"
84 #include "cfghooks.h"
85 #include "alloc-pool.h"
86 #include "tree-pass.h"
87 #include "ssa.h"
88 #include "cgraph.h"
89 #include "diagnostic.h"
90 #include "fold-const.h"
91 #include "cfganal.h"
92 #include "calls.h"
93 #include "gimplify.h"
94 #include "gimple-iterator.h"
95 #include "gimplify-me.h"
96 #include "gimple-walk.h"
97 #include "symbol-summary.h"
98 #include "ipa-prop.h"
99 #include "tree-cfg.h"
100 #include "tree-into-ssa.h"
101 #include "tree-dfa.h"
102 #include "tree-inline.h"
103 #include "params.h"
104 #include "gimple-pretty-print.h"
105 #include "ipa-fnsummary.h"
106 #include "cfgloop.h"
107 #include "tree-chkp.h"
109 /* Per basic block info. */
111 struct split_bb_info
113 unsigned int size;
114 sreal time;
117 static vec<split_bb_info> bb_info_vec;
119 /* Description of split point. */
121 struct split_point
123 /* Size of the partitions. */
124 sreal header_time, split_time;
125 unsigned int header_size, split_size;
127 /* SSA names that need to be passed into spit function. */
128 bitmap ssa_names_to_pass;
130 /* Basic block where we split (that will become entry point of new function. */
131 basic_block entry_bb;
133 /* Count for entering the split part.
134 This is not count of the entry_bb because it may be in loop. */
135 profile_count count;
137 /* Basic blocks we are splitting away. */
138 bitmap split_bbs;
140 /* True when return value is computed on split part and thus it needs
141 to be returned. */
142 bool split_part_set_retval;
145 /* Best split point found. */
147 struct split_point best_split_point;
149 /* Set of basic blocks that are not allowed to dominate a split point. */
151 static bitmap forbidden_dominators;
153 static tree find_retval (basic_block return_bb);
154 static tree find_retbnd (basic_block return_bb);
156 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
157 variable, check it if it is present in bitmap passed via DATA. */
159 static bool
160 test_nonssa_use (gimple *, tree t, tree, void *data)
162 t = get_base_address (t);
164 if (!t || is_gimple_reg (t))
165 return false;
167 if (TREE_CODE (t) == PARM_DECL
168 || (VAR_P (t)
169 && auto_var_in_fn_p (t, current_function_decl))
170 || TREE_CODE (t) == RESULT_DECL
171 /* Normal labels are part of CFG and will be handled gratefuly.
172 Forced labels however can be used directly by statements and
173 need to stay in one partition along with their uses. */
174 || (TREE_CODE (t) == LABEL_DECL
175 && FORCED_LABEL (t)))
176 return bitmap_bit_p ((bitmap)data, DECL_UID (t));
178 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
179 to pretend that the value pointed to is actual result decl. */
180 if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
181 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
182 && SSA_NAME_VAR (TREE_OPERAND (t, 0))
183 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
184 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
185 return
186 bitmap_bit_p ((bitmap)data,
187 DECL_UID (DECL_RESULT (current_function_decl)));
189 return false;
192 /* Dump split point CURRENT. */
194 static void
195 dump_split_point (FILE * file, struct split_point *current)
197 fprintf (file,
198 "Split point at BB %i\n"
199 " header time: %f header size: %i\n"
200 " split time: %f split size: %i\n bbs: ",
201 current->entry_bb->index, current->header_time.to_double (),
202 current->header_size, current->split_time.to_double (),
203 current->split_size);
204 dump_bitmap (file, current->split_bbs);
205 fprintf (file, " SSA names to pass: ");
206 dump_bitmap (file, current->ssa_names_to_pass);
209 /* Look for all BBs in header that might lead to the split part and verify
210 that they are not defining any non-SSA var used by the split part.
211 Parameters are the same as for consider_split. */
213 static bool
214 verify_non_ssa_vars (struct split_point *current, bitmap non_ssa_vars,
215 basic_block return_bb)
217 bitmap seen = BITMAP_ALLOC (NULL);
218 vec<basic_block> worklist = vNULL;
219 edge e;
220 edge_iterator ei;
221 bool ok = true;
222 basic_block bb;
224 FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
225 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
226 && !bitmap_bit_p (current->split_bbs, e->src->index))
228 worklist.safe_push (e->src);
229 bitmap_set_bit (seen, e->src->index);
232 while (!worklist.is_empty ())
234 bb = worklist.pop ();
235 FOR_EACH_EDGE (e, ei, bb->preds)
236 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
237 && bitmap_set_bit (seen, e->src->index))
239 gcc_checking_assert (!bitmap_bit_p (current->split_bbs,
240 e->src->index));
241 worklist.safe_push (e->src);
243 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
244 gsi_next (&bsi))
246 gimple *stmt = gsi_stmt (bsi);
247 if (is_gimple_debug (stmt))
248 continue;
249 if (walk_stmt_load_store_addr_ops
250 (stmt, non_ssa_vars, test_nonssa_use, test_nonssa_use,
251 test_nonssa_use))
253 ok = false;
254 goto done;
256 if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
257 if (test_nonssa_use (stmt, gimple_label_label (label_stmt),
258 NULL_TREE, non_ssa_vars))
260 ok = false;
261 goto done;
264 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
265 gsi_next (&bsi))
267 if (walk_stmt_load_store_addr_ops
268 (gsi_stmt (bsi), non_ssa_vars, test_nonssa_use, test_nonssa_use,
269 test_nonssa_use))
271 ok = false;
272 goto done;
275 FOR_EACH_EDGE (e, ei, bb->succs)
277 if (e->dest != return_bb)
278 continue;
279 for (gphi_iterator bsi = gsi_start_phis (return_bb);
280 !gsi_end_p (bsi);
281 gsi_next (&bsi))
283 gphi *stmt = bsi.phi ();
284 tree op = gimple_phi_arg_def (stmt, e->dest_idx);
286 if (virtual_operand_p (gimple_phi_result (stmt)))
287 continue;
288 if (TREE_CODE (op) != SSA_NAME
289 && test_nonssa_use (stmt, op, op, non_ssa_vars))
291 ok = false;
292 goto done;
298 /* Verify that the rest of function does not define any label
299 used by the split part. */
300 FOR_EACH_BB_FN (bb, cfun)
301 if (!bitmap_bit_p (current->split_bbs, bb->index)
302 && !bitmap_bit_p (seen, bb->index))
304 gimple_stmt_iterator bsi;
305 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
306 if (glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (bsi)))
308 if (test_nonssa_use (label_stmt,
309 gimple_label_label (label_stmt),
310 NULL_TREE, non_ssa_vars))
312 ok = false;
313 goto done;
316 else
317 break;
320 done:
321 BITMAP_FREE (seen);
322 worklist.release ();
323 return ok;
326 /* If STMT is a call, check the callee against a list of forbidden
327 predicate functions. If a match is found, look for uses of the
328 call result in condition statements that compare against zero.
329 For each such use, find the block targeted by the condition
330 statement for the nonzero result, and set the bit for this block
331 in the forbidden dominators bitmap. The purpose of this is to avoid
332 selecting a split point where we are likely to lose the chance
333 to optimize away an unused function call. */
335 static void
336 check_forbidden_calls (gimple *stmt)
338 imm_use_iterator use_iter;
339 use_operand_p use_p;
340 tree lhs;
342 /* At the moment, __builtin_constant_p is the only forbidden
343 predicate function call (see PR49642). */
344 if (!gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
345 return;
347 lhs = gimple_call_lhs (stmt);
349 if (!lhs || TREE_CODE (lhs) != SSA_NAME)
350 return;
352 FOR_EACH_IMM_USE_FAST (use_p, use_iter, lhs)
354 tree op1;
355 basic_block use_bb, forbidden_bb;
356 enum tree_code code;
357 edge true_edge, false_edge;
358 gcond *use_stmt;
360 use_stmt = dyn_cast <gcond *> (USE_STMT (use_p));
361 if (!use_stmt)
362 continue;
364 /* Assuming canonical form for GIMPLE_COND here, with constant
365 in second position. */
366 op1 = gimple_cond_rhs (use_stmt);
367 code = gimple_cond_code (use_stmt);
368 use_bb = gimple_bb (use_stmt);
370 extract_true_false_edges_from_block (use_bb, &true_edge, &false_edge);
372 /* We're only interested in comparisons that distinguish
373 unambiguously from zero. */
374 if (!integer_zerop (op1) || code == LE_EXPR || code == GE_EXPR)
375 continue;
377 if (code == EQ_EXPR)
378 forbidden_bb = false_edge->dest;
379 else
380 forbidden_bb = true_edge->dest;
382 bitmap_set_bit (forbidden_dominators, forbidden_bb->index);
386 /* If BB is dominated by any block in the forbidden dominators set,
387 return TRUE; else FALSE. */
389 static bool
390 dominated_by_forbidden (basic_block bb)
392 unsigned dom_bb;
393 bitmap_iterator bi;
395 EXECUTE_IF_SET_IN_BITMAP (forbidden_dominators, 1, dom_bb, bi)
397 if (dominated_by_p (CDI_DOMINATORS, bb,
398 BASIC_BLOCK_FOR_FN (cfun, dom_bb)))
399 return true;
402 return false;
405 /* For give split point CURRENT and return block RETURN_BB return 1
406 if ssa name VAL is set by split part and 0 otherwise. */
407 static bool
408 split_part_set_ssa_name_p (tree val, struct split_point *current,
409 basic_block return_bb)
411 if (TREE_CODE (val) != SSA_NAME)
412 return false;
414 return (!SSA_NAME_IS_DEFAULT_DEF (val)
415 && (bitmap_bit_p (current->split_bbs,
416 gimple_bb (SSA_NAME_DEF_STMT (val))->index)
417 || gimple_bb (SSA_NAME_DEF_STMT (val)) == return_bb));
420 /* We found an split_point CURRENT. NON_SSA_VARS is bitmap of all non ssa
421 variables used and RETURN_BB is return basic block.
422 See if we can split function here. */
424 static void
425 consider_split (struct split_point *current, bitmap non_ssa_vars,
426 basic_block return_bb)
428 tree parm;
429 unsigned int num_args = 0;
430 unsigned int call_overhead;
431 edge e;
432 edge_iterator ei;
433 gphi_iterator bsi;
434 unsigned int i;
435 tree retval;
436 tree retbnd;
437 bool back_edge = false;
439 if (dump_file && (dump_flags & TDF_DETAILS))
440 dump_split_point (dump_file, current);
442 current->count = profile_count::zero ();
443 FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
445 if (e->flags & EDGE_DFS_BACK)
446 back_edge = true;
447 if (!bitmap_bit_p (current->split_bbs, e->src->index))
448 current->count += e->count ();
451 /* Do not split when we would end up calling function anyway.
452 Compares are three state, use !(...<...) to also give up when outcome
453 is unknown. */
454 if (!(current->count
455 < (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.apply_scale
456 (PARAM_VALUE (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY), 100))))
458 /* When profile is guessed, we can not expect it to give us
459 realistic estimate on likelyness of function taking the
460 complex path. As a special case, when tail of the function is
461 a loop, enable splitting since inlining code skipping the loop
462 is likely noticeable win. */
463 if (back_edge
464 && profile_status_for_fn (cfun) != PROFILE_READ
465 && current->count
466 < ENTRY_BLOCK_PTR_FOR_FN (cfun)->count)
468 if (dump_file && (dump_flags & TDF_DETAILS))
470 fprintf (dump_file,
471 " Split before loop, accepting despite low counts");
472 current->count.dump (dump_file);
473 fprintf (dump_file, " ");
474 ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.dump (dump_file);
477 else
479 if (dump_file && (dump_flags & TDF_DETAILS))
480 fprintf (dump_file,
481 " Refused: incoming frequency is too large.\n");
482 return;
486 if (!current->header_size)
488 if (dump_file && (dump_flags & TDF_DETAILS))
489 fprintf (dump_file, " Refused: header empty\n");
490 return;
493 /* Verify that PHI args on entry are either virtual or all their operands
494 incoming from header are the same. */
495 for (bsi = gsi_start_phis (current->entry_bb); !gsi_end_p (bsi); gsi_next (&bsi))
497 gphi *stmt = bsi.phi ();
498 tree val = NULL;
500 if (virtual_operand_p (gimple_phi_result (stmt)))
501 continue;
502 for (i = 0; i < gimple_phi_num_args (stmt); i++)
504 edge e = gimple_phi_arg_edge (stmt, i);
505 if (!bitmap_bit_p (current->split_bbs, e->src->index))
507 tree edge_val = gimple_phi_arg_def (stmt, i);
508 if (val && edge_val != val)
510 if (dump_file && (dump_flags & TDF_DETAILS))
511 fprintf (dump_file,
512 " Refused: entry BB has PHI with multiple variants\n");
513 return;
515 val = edge_val;
521 /* See what argument we will pass to the split function and compute
522 call overhead. */
523 call_overhead = eni_size_weights.call_cost;
524 for (parm = DECL_ARGUMENTS (current_function_decl); parm;
525 parm = DECL_CHAIN (parm))
527 if (!is_gimple_reg (parm))
529 if (bitmap_bit_p (non_ssa_vars, DECL_UID (parm)))
531 if (dump_file && (dump_flags & TDF_DETAILS))
532 fprintf (dump_file,
533 " Refused: need to pass non-ssa param values\n");
534 return;
537 else
539 tree ddef = ssa_default_def (cfun, parm);
540 if (ddef
541 && bitmap_bit_p (current->ssa_names_to_pass,
542 SSA_NAME_VERSION (ddef)))
544 if (!VOID_TYPE_P (TREE_TYPE (parm)))
545 call_overhead += estimate_move_cost (TREE_TYPE (parm), false);
546 num_args++;
550 if (!VOID_TYPE_P (TREE_TYPE (current_function_decl)))
551 call_overhead += estimate_move_cost (TREE_TYPE (current_function_decl),
552 false);
554 if (current->split_size <= call_overhead)
556 if (dump_file && (dump_flags & TDF_DETAILS))
557 fprintf (dump_file,
558 " Refused: split size is smaller than call overhead\n");
559 return;
561 /* FIXME: The logic here is not very precise, because inliner does use
562 inline predicates to reduce function body size. We add 10 to anticipate
563 that. Next stage1 we should try to be more meaningful here. */
564 if (current->header_size + call_overhead
565 >= (unsigned int)(DECL_DECLARED_INLINE_P (current_function_decl)
566 ? MAX_INLINE_INSNS_SINGLE
567 : MAX_INLINE_INSNS_AUTO) + 10)
569 if (dump_file && (dump_flags & TDF_DETAILS))
570 fprintf (dump_file,
571 " Refused: header size is too large for inline candidate\n");
572 return;
575 /* Splitting functions brings the target out of comdat group; this will
576 lead to code duplication if the function is reused by other unit.
577 Limit this duplication. This is consistent with limit in tree-sra.c
578 FIXME: with LTO we ought to be able to do better! */
579 if (DECL_ONE_ONLY (current_function_decl)
580 && current->split_size >= (unsigned int) MAX_INLINE_INSNS_AUTO + 10)
582 if (dump_file && (dump_flags & TDF_DETAILS))
583 fprintf (dump_file,
584 " Refused: function is COMDAT and tail is too large\n");
585 return;
587 /* For comdat functions also reject very small tails; those will likely get
588 inlined back and we do not want to risk the duplication overhead.
589 FIXME: with LTO we ought to be able to do better! */
590 if (DECL_ONE_ONLY (current_function_decl)
591 && current->split_size
592 <= (unsigned int) PARAM_VALUE (PARAM_EARLY_INLINING_INSNS) / 2)
594 if (dump_file && (dump_flags & TDF_DETAILS))
595 fprintf (dump_file,
596 " Refused: function is COMDAT and tail is too small\n");
597 return;
600 /* FIXME: we currently can pass only SSA function parameters to the split
601 arguments. Once parm_adjustment infrastructure is supported by cloning,
602 we can pass more than that. */
603 if (num_args != bitmap_count_bits (current->ssa_names_to_pass))
606 if (dump_file && (dump_flags & TDF_DETAILS))
607 fprintf (dump_file,
608 " Refused: need to pass non-param values\n");
609 return;
612 /* When there are non-ssa vars used in the split region, see if they
613 are used in the header region. If so, reject the split.
614 FIXME: we can use nested function support to access both. */
615 if (!bitmap_empty_p (non_ssa_vars)
616 && !verify_non_ssa_vars (current, non_ssa_vars, return_bb))
618 if (dump_file && (dump_flags & TDF_DETAILS))
619 fprintf (dump_file,
620 " Refused: split part has non-ssa uses\n");
621 return;
624 /* If the split point is dominated by a forbidden block, reject
625 the split. */
626 if (!bitmap_empty_p (forbidden_dominators)
627 && dominated_by_forbidden (current->entry_bb))
629 if (dump_file && (dump_flags & TDF_DETAILS))
630 fprintf (dump_file,
631 " Refused: split point dominated by forbidden block\n");
632 return;
635 /* See if retval used by return bb is computed by header or split part.
636 When it is computed by split part, we need to produce return statement
637 in the split part and add code to header to pass it around.
639 This is bit tricky to test:
640 1) When there is no return_bb or no return value, we always pass
641 value around.
642 2) Invariants are always computed by caller.
643 3) For SSA we need to look if defining statement is in header or split part
644 4) For non-SSA we need to look where the var is computed. */
645 retval = find_retval (return_bb);
646 if (!retval)
648 /* If there is a return_bb with no return value in function returning
649 value by reference, also make the split part return void, otherwise
650 we expansion would try to create a non-POD temporary, which is
651 invalid. */
652 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
653 && DECL_RESULT (current_function_decl)
654 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
655 current->split_part_set_retval = false;
656 else
657 current->split_part_set_retval = true;
659 else if (is_gimple_min_invariant (retval))
660 current->split_part_set_retval = false;
661 /* Special case is value returned by reference we record as if it was non-ssa
662 set to result_decl. */
663 else if (TREE_CODE (retval) == SSA_NAME
664 && SSA_NAME_VAR (retval)
665 && TREE_CODE (SSA_NAME_VAR (retval)) == RESULT_DECL
666 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
667 current->split_part_set_retval
668 = bitmap_bit_p (non_ssa_vars, DECL_UID (SSA_NAME_VAR (retval)));
669 else if (TREE_CODE (retval) == SSA_NAME)
670 current->split_part_set_retval
671 = split_part_set_ssa_name_p (retval, current, return_bb);
672 else if (TREE_CODE (retval) == PARM_DECL)
673 current->split_part_set_retval = false;
674 else if (VAR_P (retval)
675 || TREE_CODE (retval) == RESULT_DECL)
676 current->split_part_set_retval
677 = bitmap_bit_p (non_ssa_vars, DECL_UID (retval));
678 else
679 current->split_part_set_retval = true;
681 /* See if retbnd used by return bb is computed by header or split part. */
682 retbnd = find_retbnd (return_bb);
683 if (retbnd)
685 bool split_part_set_retbnd
686 = split_part_set_ssa_name_p (retbnd, current, return_bb);
688 /* If we have both return value and bounds then keep their definitions
689 in a single function. We use SSA names to link returned bounds and
690 value and therefore do not handle cases when result is passed by
691 reference (which should not be our case anyway since bounds are
692 returned for pointers only). */
693 if ((DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))
694 && current->split_part_set_retval)
695 || split_part_set_retbnd != current->split_part_set_retval)
697 if (dump_file && (dump_flags & TDF_DETAILS))
698 fprintf (dump_file,
699 " Refused: split point splits return value and bounds\n");
700 return;
704 /* split_function fixes up at most one PHI non-virtual PHI node in return_bb,
705 for the return value. If there are other PHIs, give up. */
706 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
708 gphi_iterator psi;
710 for (psi = gsi_start_phis (return_bb); !gsi_end_p (psi); gsi_next (&psi))
711 if (!virtual_operand_p (gimple_phi_result (psi.phi ()))
712 && !(retval
713 && current->split_part_set_retval
714 && TREE_CODE (retval) == SSA_NAME
715 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))
716 && SSA_NAME_DEF_STMT (retval) == psi.phi ()))
718 if (dump_file && (dump_flags & TDF_DETAILS))
719 fprintf (dump_file,
720 " Refused: return bb has extra PHIs\n");
721 return;
725 if (dump_file && (dump_flags & TDF_DETAILS))
726 fprintf (dump_file, " Accepted!\n");
728 /* At the moment chose split point with lowest count and that leaves
729 out smallest size of header.
730 In future we might re-consider this heuristics. */
731 if (!best_split_point.split_bbs
732 || best_split_point.count
733 > current->count
734 || (best_split_point.count == current->count
735 && best_split_point.split_size < current->split_size))
738 if (dump_file && (dump_flags & TDF_DETAILS))
739 fprintf (dump_file, " New best split point!\n");
740 if (best_split_point.ssa_names_to_pass)
742 BITMAP_FREE (best_split_point.ssa_names_to_pass);
743 BITMAP_FREE (best_split_point.split_bbs);
745 best_split_point = *current;
746 best_split_point.ssa_names_to_pass = BITMAP_ALLOC (NULL);
747 bitmap_copy (best_split_point.ssa_names_to_pass,
748 current->ssa_names_to_pass);
749 best_split_point.split_bbs = BITMAP_ALLOC (NULL);
750 bitmap_copy (best_split_point.split_bbs, current->split_bbs);
754 /* Return basic block containing RETURN statement. We allow basic blocks
755 of the form:
756 <retval> = tmp_var;
757 return <retval>
758 but return_bb can not be more complex than this (except for
759 -fsanitize=thread we allow TSAN_FUNC_EXIT () internal call in there).
760 If nothing is found, return the exit block.
762 When there are multiple RETURN statement, chose one with return value,
763 since that one is more likely shared by multiple code paths.
765 Return BB is special, because for function splitting it is the only
766 basic block that is duplicated in between header and split part of the
767 function.
769 TODO: We might support multiple return blocks. */
771 static basic_block
772 find_return_bb (void)
774 edge e;
775 basic_block return_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
776 gimple_stmt_iterator bsi;
777 bool found_return = false;
778 tree retval = NULL_TREE;
780 if (!single_pred_p (EXIT_BLOCK_PTR_FOR_FN (cfun)))
781 return return_bb;
783 e = single_pred_edge (EXIT_BLOCK_PTR_FOR_FN (cfun));
784 for (bsi = gsi_last_bb (e->src); !gsi_end_p (bsi); gsi_prev (&bsi))
786 gimple *stmt = gsi_stmt (bsi);
787 if (gimple_code (stmt) == GIMPLE_LABEL
788 || is_gimple_debug (stmt)
789 || gimple_clobber_p (stmt))
791 else if (gimple_code (stmt) == GIMPLE_ASSIGN
792 && found_return
793 && gimple_assign_single_p (stmt)
794 && (auto_var_in_fn_p (gimple_assign_rhs1 (stmt),
795 current_function_decl)
796 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
797 && retval == gimple_assign_lhs (stmt))
799 else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
801 found_return = true;
802 retval = gimple_return_retval (return_stmt);
804 /* For -fsanitize=thread, allow also TSAN_FUNC_EXIT () in the return
805 bb. */
806 else if ((flag_sanitize & SANITIZE_THREAD)
807 && gimple_call_internal_p (stmt, IFN_TSAN_FUNC_EXIT))
809 else
810 break;
812 if (gsi_end_p (bsi) && found_return)
813 return_bb = e->src;
815 return return_bb;
818 /* Given return basic block RETURN_BB, see where return value is really
819 stored. */
820 static tree
821 find_retval (basic_block return_bb)
823 gimple_stmt_iterator bsi;
824 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
825 if (greturn *return_stmt = dyn_cast <greturn *> (gsi_stmt (bsi)))
826 return gimple_return_retval (return_stmt);
827 else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN
828 && !gimple_clobber_p (gsi_stmt (bsi)))
829 return gimple_assign_rhs1 (gsi_stmt (bsi));
830 return NULL;
833 /* Given return basic block RETURN_BB, see where return bounds are really
834 stored. */
835 static tree
836 find_retbnd (basic_block return_bb)
838 gimple_stmt_iterator bsi;
839 for (bsi = gsi_last_bb (return_bb); !gsi_end_p (bsi); gsi_prev (&bsi))
840 if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
841 return gimple_return_retbnd (gsi_stmt (bsi));
842 return NULL;
845 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
846 variable, mark it as used in bitmap passed via DATA.
847 Return true when access to T prevents splitting the function. */
849 static bool
850 mark_nonssa_use (gimple *, tree t, tree, void *data)
852 t = get_base_address (t);
854 if (!t || is_gimple_reg (t))
855 return false;
857 /* At present we can't pass non-SSA arguments to split function.
858 FIXME: this can be relaxed by passing references to arguments. */
859 if (TREE_CODE (t) == PARM_DECL)
861 if (dump_file && (dump_flags & TDF_DETAILS))
862 fprintf (dump_file,
863 "Cannot split: use of non-ssa function parameter.\n");
864 return true;
867 if ((VAR_P (t) && auto_var_in_fn_p (t, current_function_decl))
868 || TREE_CODE (t) == RESULT_DECL
869 || (TREE_CODE (t) == LABEL_DECL && FORCED_LABEL (t)))
870 bitmap_set_bit ((bitmap)data, DECL_UID (t));
872 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
873 to pretend that the value pointed to is actual result decl. */
874 if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
875 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
876 && SSA_NAME_VAR (TREE_OPERAND (t, 0))
877 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
878 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
879 return
880 bitmap_bit_p ((bitmap)data,
881 DECL_UID (DECL_RESULT (current_function_decl)));
883 return false;
886 /* Compute local properties of basic block BB we collect when looking for
887 split points. We look for ssa defs and store them in SET_SSA_NAMES,
888 for ssa uses and store them in USED_SSA_NAMES and for any non-SSA automatic
889 vars stored in NON_SSA_VARS.
891 When BB has edge to RETURN_BB, collect uses in RETURN_BB too.
893 Return false when BB contains something that prevents it from being put into
894 split function. */
896 static bool
897 visit_bb (basic_block bb, basic_block return_bb,
898 bitmap set_ssa_names, bitmap used_ssa_names,
899 bitmap non_ssa_vars)
901 edge e;
902 edge_iterator ei;
903 bool can_split = true;
905 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
906 gsi_next (&bsi))
908 gimple *stmt = gsi_stmt (bsi);
909 tree op;
910 ssa_op_iter iter;
911 tree decl;
913 if (is_gimple_debug (stmt))
914 continue;
916 if (gimple_clobber_p (stmt))
917 continue;
919 /* FIXME: We can split regions containing EH. We can not however
920 split RESX, EH_DISPATCH and EH_POINTER referring to same region
921 into different partitions. This would require tracking of
922 EH regions and checking in consider_split_point if they
923 are not used elsewhere. */
924 if (gimple_code (stmt) == GIMPLE_RESX)
926 if (dump_file && (dump_flags & TDF_DETAILS))
927 fprintf (dump_file, "Cannot split: resx.\n");
928 can_split = false;
930 if (gimple_code (stmt) == GIMPLE_EH_DISPATCH)
932 if (dump_file && (dump_flags & TDF_DETAILS))
933 fprintf (dump_file, "Cannot split: eh dispatch.\n");
934 can_split = false;
937 /* Check builtins that prevent splitting. */
938 if (gimple_code (stmt) == GIMPLE_CALL
939 && (decl = gimple_call_fndecl (stmt)) != NULL_TREE
940 && DECL_BUILT_IN (decl)
941 && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
942 switch (DECL_FUNCTION_CODE (decl))
944 /* FIXME: once we will allow passing non-parm values to split part,
945 we need to be sure to handle correct builtin_stack_save and
946 builtin_stack_restore. At the moment we are safe; there is no
947 way to store builtin_stack_save result in non-SSA variable
948 since all calls to those are compiler generated. */
949 case BUILT_IN_APPLY:
950 case BUILT_IN_APPLY_ARGS:
951 case BUILT_IN_VA_START:
952 if (dump_file && (dump_flags & TDF_DETAILS))
953 fprintf (dump_file,
954 "Cannot split: builtin_apply and va_start.\n");
955 can_split = false;
956 break;
957 case BUILT_IN_EH_POINTER:
958 if (dump_file && (dump_flags & TDF_DETAILS))
959 fprintf (dump_file, "Cannot split: builtin_eh_pointer.\n");
960 can_split = false;
961 break;
962 default:
963 break;
966 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
967 bitmap_set_bit (set_ssa_names, SSA_NAME_VERSION (op));
968 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
969 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
970 can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
971 mark_nonssa_use,
972 mark_nonssa_use,
973 mark_nonssa_use);
975 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
976 gsi_next (&bsi))
978 gphi *stmt = bsi.phi ();
979 unsigned int i;
981 if (virtual_operand_p (gimple_phi_result (stmt)))
982 continue;
983 bitmap_set_bit (set_ssa_names,
984 SSA_NAME_VERSION (gimple_phi_result (stmt)));
985 for (i = 0; i < gimple_phi_num_args (stmt); i++)
987 tree op = gimple_phi_arg_def (stmt, i);
988 if (TREE_CODE (op) == SSA_NAME)
989 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
991 can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
992 mark_nonssa_use,
993 mark_nonssa_use,
994 mark_nonssa_use);
996 /* Record also uses coming from PHI operand in return BB. */
997 FOR_EACH_EDGE (e, ei, bb->succs)
998 if (e->dest == return_bb)
1000 for (gphi_iterator bsi = gsi_start_phis (return_bb);
1001 !gsi_end_p (bsi);
1002 gsi_next (&bsi))
1004 gphi *stmt = bsi.phi ();
1005 tree op = gimple_phi_arg_def (stmt, e->dest_idx);
1007 if (virtual_operand_p (gimple_phi_result (stmt)))
1008 continue;
1009 if (TREE_CODE (op) == SSA_NAME)
1010 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
1011 else
1012 can_split &= !mark_nonssa_use (stmt, op, op, non_ssa_vars);
1015 return can_split;
1018 /* Stack entry for recursive DFS walk in find_split_point. */
1020 struct stack_entry
1022 /* Basic block we are examining. */
1023 basic_block bb;
1025 /* SSA names set and used by the BB and all BBs reachable
1026 from it via DFS walk. */
1027 bitmap set_ssa_names, used_ssa_names;
1028 bitmap non_ssa_vars;
1030 /* All BBS visited from this BB via DFS walk. */
1031 bitmap bbs_visited;
1033 /* Last examined edge in DFS walk. Since we walk unoriented graph,
1034 the value is up to sum of incoming and outgoing edges of BB. */
1035 unsigned int edge_num;
1037 /* Stack entry index of earliest BB reachable from current BB
1038 or any BB visited later in DFS walk. */
1039 int earliest;
1041 /* Overall time and size of all BBs reached from this BB in DFS walk. */
1042 sreal overall_time;
1043 int overall_size;
1045 /* When false we can not split on this BB. */
1046 bool can_split;
1050 /* Find all articulations and call consider_split on them.
1051 OVERALL_TIME and OVERALL_SIZE is time and size of the function.
1053 We perform basic algorithm for finding an articulation in a graph
1054 created from CFG by considering it to be an unoriented graph.
1056 The articulation is discovered via DFS walk. We collect earliest
1057 basic block on stack that is reachable via backward edge. Articulation
1058 is any basic block such that there is no backward edge bypassing it.
1059 To reduce stack usage we maintain heap allocated stack in STACK vector.
1060 AUX pointer of BB is set to index it appears in the stack or -1 once
1061 it is visited and popped off the stack.
1063 The algorithm finds articulation after visiting the whole component
1064 reachable by it. This makes it convenient to collect information about
1065 the component used by consider_split. */
1067 static void
1068 find_split_points (basic_block return_bb, sreal overall_time, int overall_size)
1070 stack_entry first;
1071 vec<stack_entry> stack = vNULL;
1072 basic_block bb;
1073 struct split_point current;
1075 current.header_time = overall_time;
1076 current.header_size = overall_size;
1077 current.split_time = 0;
1078 current.split_size = 0;
1079 current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
1081 first.bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1082 first.edge_num = 0;
1083 first.overall_time = 0;
1084 first.overall_size = 0;
1085 first.earliest = INT_MAX;
1086 first.set_ssa_names = 0;
1087 first.used_ssa_names = 0;
1088 first.non_ssa_vars = 0;
1089 first.bbs_visited = 0;
1090 first.can_split = false;
1091 stack.safe_push (first);
1092 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(intptr_t)-1;
1094 while (!stack.is_empty ())
1096 stack_entry *entry = &stack.last ();
1098 /* We are walking an acyclic graph, so edge_num counts
1099 succ and pred edges together. However when considering
1100 articulation, we want to have processed everything reachable
1101 from articulation but nothing that reaches into it. */
1102 if (entry->edge_num == EDGE_COUNT (entry->bb->succs)
1103 && entry->bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1105 int pos = stack.length ();
1106 entry->can_split &= visit_bb (entry->bb, return_bb,
1107 entry->set_ssa_names,
1108 entry->used_ssa_names,
1109 entry->non_ssa_vars);
1110 if (pos <= entry->earliest && !entry->can_split
1111 && dump_file && (dump_flags & TDF_DETAILS))
1112 fprintf (dump_file,
1113 "found articulation at bb %i but can not split\n",
1114 entry->bb->index);
1115 if (pos <= entry->earliest && entry->can_split)
1117 if (dump_file && (dump_flags & TDF_DETAILS))
1118 fprintf (dump_file, "found articulation at bb %i\n",
1119 entry->bb->index);
1120 current.entry_bb = entry->bb;
1121 current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
1122 bitmap_and_compl (current.ssa_names_to_pass,
1123 entry->used_ssa_names, entry->set_ssa_names);
1124 current.header_time = overall_time - entry->overall_time;
1125 current.header_size = overall_size - entry->overall_size;
1126 current.split_time = entry->overall_time;
1127 current.split_size = entry->overall_size;
1128 current.split_bbs = entry->bbs_visited;
1129 consider_split (&current, entry->non_ssa_vars, return_bb);
1130 BITMAP_FREE (current.ssa_names_to_pass);
1133 /* Do actual DFS walk. */
1134 if (entry->edge_num
1135 < (EDGE_COUNT (entry->bb->succs)
1136 + EDGE_COUNT (entry->bb->preds)))
1138 edge e;
1139 basic_block dest;
1140 if (entry->edge_num < EDGE_COUNT (entry->bb->succs))
1142 e = EDGE_SUCC (entry->bb, entry->edge_num);
1143 dest = e->dest;
1145 else
1147 e = EDGE_PRED (entry->bb, entry->edge_num
1148 - EDGE_COUNT (entry->bb->succs));
1149 dest = e->src;
1152 entry->edge_num++;
1154 /* New BB to visit, push it to the stack. */
1155 if (dest != return_bb && dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1156 && !dest->aux)
1158 stack_entry new_entry;
1160 new_entry.bb = dest;
1161 new_entry.edge_num = 0;
1162 new_entry.overall_time
1163 = bb_info_vec[dest->index].time;
1164 new_entry.overall_size
1165 = bb_info_vec[dest->index].size;
1166 new_entry.earliest = INT_MAX;
1167 new_entry.set_ssa_names = BITMAP_ALLOC (NULL);
1168 new_entry.used_ssa_names = BITMAP_ALLOC (NULL);
1169 new_entry.bbs_visited = BITMAP_ALLOC (NULL);
1170 new_entry.non_ssa_vars = BITMAP_ALLOC (NULL);
1171 new_entry.can_split = true;
1172 bitmap_set_bit (new_entry.bbs_visited, dest->index);
1173 stack.safe_push (new_entry);
1174 dest->aux = (void *)(intptr_t)stack.length ();
1176 /* Back edge found, record the earliest point. */
1177 else if ((intptr_t)dest->aux > 0
1178 && (intptr_t)dest->aux < entry->earliest)
1179 entry->earliest = (intptr_t)dest->aux;
1181 /* We are done with examining the edges. Pop off the value from stack
1182 and merge stuff we accumulate during the walk. */
1183 else if (entry->bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1185 stack_entry *prev = &stack[stack.length () - 2];
1187 entry->bb->aux = (void *)(intptr_t)-1;
1188 prev->can_split &= entry->can_split;
1189 if (prev->set_ssa_names)
1191 bitmap_ior_into (prev->set_ssa_names, entry->set_ssa_names);
1192 bitmap_ior_into (prev->used_ssa_names, entry->used_ssa_names);
1193 bitmap_ior_into (prev->bbs_visited, entry->bbs_visited);
1194 bitmap_ior_into (prev->non_ssa_vars, entry->non_ssa_vars);
1196 if (prev->earliest > entry->earliest)
1197 prev->earliest = entry->earliest;
1198 prev->overall_time += entry->overall_time;
1199 prev->overall_size += entry->overall_size;
1200 BITMAP_FREE (entry->set_ssa_names);
1201 BITMAP_FREE (entry->used_ssa_names);
1202 BITMAP_FREE (entry->bbs_visited);
1203 BITMAP_FREE (entry->non_ssa_vars);
1204 stack.pop ();
1206 else
1207 stack.pop ();
1209 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = NULL;
1210 FOR_EACH_BB_FN (bb, cfun)
1211 bb->aux = NULL;
1212 stack.release ();
1213 BITMAP_FREE (current.ssa_names_to_pass);
1216 /* Split function at SPLIT_POINT. */
1218 static void
1219 split_function (basic_block return_bb, struct split_point *split_point,
1220 bool add_tsan_func_exit)
1222 vec<tree> args_to_pass = vNULL;
1223 bitmap args_to_skip;
1224 tree parm;
1225 int num = 0;
1226 cgraph_node *node, *cur_node = cgraph_node::get (current_function_decl);
1227 basic_block call_bb;
1228 gcall *call, *tsan_func_exit_call = NULL;
1229 edge e;
1230 edge_iterator ei;
1231 tree retval = NULL, real_retval = NULL, retbnd = NULL;
1232 bool with_bounds = chkp_function_instrumented_p (current_function_decl);
1233 gimple *last_stmt = NULL;
1234 unsigned int i;
1235 tree arg, ddef;
1237 if (dump_file)
1239 fprintf (dump_file, "\n\nSplitting function at:\n");
1240 dump_split_point (dump_file, split_point);
1243 if (cur_node->local.can_change_signature)
1244 args_to_skip = BITMAP_ALLOC (NULL);
1245 else
1246 args_to_skip = NULL;
1248 /* Collect the parameters of new function and args_to_skip bitmap. */
1249 for (parm = DECL_ARGUMENTS (current_function_decl);
1250 parm; parm = DECL_CHAIN (parm), num++)
1251 if (args_to_skip
1252 && (!is_gimple_reg (parm)
1253 || (ddef = ssa_default_def (cfun, parm)) == NULL_TREE
1254 || !bitmap_bit_p (split_point->ssa_names_to_pass,
1255 SSA_NAME_VERSION (ddef))))
1256 bitmap_set_bit (args_to_skip, num);
1257 else
1259 /* This parm might not have been used up to now, but is going to be
1260 used, hence register it. */
1261 if (is_gimple_reg (parm))
1262 arg = get_or_create_ssa_default_def (cfun, parm);
1263 else
1264 arg = parm;
1266 if (!useless_type_conversion_p (DECL_ARG_TYPE (parm), TREE_TYPE (arg)))
1267 arg = fold_convert (DECL_ARG_TYPE (parm), arg);
1268 args_to_pass.safe_push (arg);
1271 /* See if the split function will return. */
1272 bool split_part_return_p = false;
1273 FOR_EACH_EDGE (e, ei, return_bb->preds)
1275 if (bitmap_bit_p (split_point->split_bbs, e->src->index))
1276 split_part_return_p = true;
1279 /* Add return block to what will become the split function.
1280 We do not return; no return block is needed. */
1281 if (!split_part_return_p)
1283 /* We have no return block, so nothing is needed. */
1284 else if (return_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1286 /* When we do not want to return value, we need to construct
1287 new return block with empty return statement.
1288 FIXME: Once we are able to change return type, we should change function
1289 to return void instead of just outputting function with undefined return
1290 value. For structures this affects quality of codegen. */
1291 else if ((retval = find_retval (return_bb))
1292 && !split_point->split_part_set_retval)
1294 bool redirected = true;
1295 basic_block new_return_bb = create_basic_block (NULL, 0, return_bb);
1296 gimple_stmt_iterator gsi = gsi_start_bb (new_return_bb);
1297 gsi_insert_after (&gsi, gimple_build_return (NULL), GSI_NEW_STMT);
1298 new_return_bb->count = profile_count::zero ();
1299 while (redirected)
1301 redirected = false;
1302 FOR_EACH_EDGE (e, ei, return_bb->preds)
1303 if (bitmap_bit_p (split_point->split_bbs, e->src->index))
1305 new_return_bb->count += e->count ();
1306 redirect_edge_and_branch (e, new_return_bb);
1307 redirected = true;
1308 break;
1311 e = make_single_succ_edge (new_return_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
1312 add_bb_to_loop (new_return_bb, current_loops->tree_root);
1313 bitmap_set_bit (split_point->split_bbs, new_return_bb->index);
1314 retbnd = find_retbnd (return_bb);
1316 /* When we pass around the value, use existing return block. */
1317 else
1319 bitmap_set_bit (split_point->split_bbs, return_bb->index);
1320 retbnd = find_retbnd (return_bb);
1323 /* If RETURN_BB has virtual operand PHIs, they must be removed and the
1324 virtual operand marked for renaming as we change the CFG in a way that
1325 tree-inline is not able to compensate for.
1327 Note this can happen whether or not we have a return value. If we have
1328 a return value, then RETURN_BB may have PHIs for real operands too. */
1329 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1331 bool phi_p = false;
1332 for (gphi_iterator gsi = gsi_start_phis (return_bb);
1333 !gsi_end_p (gsi);)
1335 gphi *stmt = gsi.phi ();
1336 if (!virtual_operand_p (gimple_phi_result (stmt)))
1338 gsi_next (&gsi);
1339 continue;
1341 mark_virtual_phi_result_for_renaming (stmt);
1342 remove_phi_node (&gsi, true);
1343 phi_p = true;
1345 /* In reality we have to rename the reaching definition of the
1346 virtual operand at return_bb as we will eventually release it
1347 when we remove the code region we outlined.
1348 So we have to rename all immediate virtual uses of that region
1349 if we didn't see a PHI definition yet. */
1350 /* ??? In real reality we want to set the reaching vdef of the
1351 entry of the SESE region as the vuse of the call and the reaching
1352 vdef of the exit of the SESE region as the vdef of the call. */
1353 if (!phi_p)
1354 for (gimple_stmt_iterator gsi = gsi_start_bb (return_bb);
1355 !gsi_end_p (gsi);
1356 gsi_next (&gsi))
1358 gimple *stmt = gsi_stmt (gsi);
1359 if (gimple_vuse (stmt))
1361 gimple_set_vuse (stmt, NULL_TREE);
1362 update_stmt (stmt);
1364 if (gimple_vdef (stmt))
1365 break;
1369 /* Now create the actual clone. */
1370 cgraph_edge::rebuild_edges ();
1371 node = cur_node->create_version_clone_with_body
1372 (vNULL, NULL, args_to_skip,
1373 !split_part_return_p || !split_point->split_part_set_retval,
1374 split_point->split_bbs, split_point->entry_bb, "part");
1376 node->split_part = true;
1378 if (cur_node->same_comdat_group)
1380 /* TODO: call is versionable if we make sure that all
1381 callers are inside of a comdat group. */
1382 cur_node->calls_comdat_local = 1;
1383 node->add_to_same_comdat_group (cur_node);
1387 /* Let's take a time profile for splitted function. */
1388 node->tp_first_run = cur_node->tp_first_run + 1;
1390 /* For usual cloning it is enough to clear builtin only when signature
1391 changes. For partial inlining we however can not expect the part
1392 of builtin implementation to have same semantic as the whole. */
1393 if (DECL_BUILT_IN (node->decl))
1395 DECL_BUILT_IN_CLASS (node->decl) = NOT_BUILT_IN;
1396 DECL_FUNCTION_CODE (node->decl) = (enum built_in_function) 0;
1399 /* If return_bb contains any clobbers that refer to SSA_NAMEs
1400 set in the split part, remove them. Also reset debug stmts that
1401 refer to SSA_NAMEs set in the split part. */
1402 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1404 gimple_stmt_iterator gsi = gsi_start_bb (return_bb);
1405 while (!gsi_end_p (gsi))
1407 tree op;
1408 ssa_op_iter iter;
1409 gimple *stmt = gsi_stmt (gsi);
1410 bool remove = false;
1411 if (gimple_clobber_p (stmt) || is_gimple_debug (stmt))
1412 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
1414 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (op));
1415 if (op != retval
1416 && bb
1417 && bb != return_bb
1418 && bitmap_bit_p (split_point->split_bbs, bb->index))
1420 if (is_gimple_debug (stmt))
1422 gimple_debug_bind_reset_value (stmt);
1423 update_stmt (stmt);
1425 else
1426 remove = true;
1427 break;
1430 if (remove)
1431 gsi_remove (&gsi, true);
1432 else
1433 gsi_next (&gsi);
1437 /* If the original function is instrumented then it's
1438 part is also instrumented. */
1439 if (with_bounds)
1440 chkp_function_mark_instrumented (node->decl);
1442 /* If the original function is declared inline, there is no point in issuing
1443 a warning for the non-inlinable part. */
1444 DECL_NO_INLINE_WARNING_P (node->decl) = 1;
1445 cur_node->remove_callees ();
1446 cur_node->remove_all_references ();
1447 if (!split_part_return_p)
1448 TREE_THIS_VOLATILE (node->decl) = 1;
1449 if (dump_file)
1450 dump_function_to_file (node->decl, dump_file, dump_flags);
1452 /* Create the basic block we place call into. It is the entry basic block
1453 split after last label. */
1454 call_bb = split_point->entry_bb;
1455 for (gimple_stmt_iterator gsi = gsi_start_bb (call_bb); !gsi_end_p (gsi);)
1456 if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
1458 last_stmt = gsi_stmt (gsi);
1459 gsi_next (&gsi);
1461 else
1462 break;
1463 call_bb->count = split_point->count;
1464 e = split_block (split_point->entry_bb, last_stmt);
1465 remove_edge (e);
1467 /* Produce the call statement. */
1468 gimple_stmt_iterator gsi = gsi_last_bb (call_bb);
1469 FOR_EACH_VEC_ELT (args_to_pass, i, arg)
1470 if (!is_gimple_val (arg))
1472 arg = force_gimple_operand_gsi (&gsi, arg, true, NULL_TREE,
1473 false, GSI_CONTINUE_LINKING);
1474 args_to_pass[i] = arg;
1476 call = gimple_build_call_vec (node->decl, args_to_pass);
1477 gimple_call_set_with_bounds (call, with_bounds);
1478 gimple_set_block (call, DECL_INITIAL (current_function_decl));
1479 args_to_pass.release ();
1481 /* For optimized away parameters, add on the caller side
1482 before the call
1483 DEBUG D#X => parm_Y(D)
1484 stmts and associate D#X with parm in decl_debug_args_lookup
1485 vector to say for debug info that if parameter parm had been passed,
1486 it would have value parm_Y(D). */
1487 if (args_to_skip)
1489 vec<tree, va_gc> **debug_args = NULL;
1490 unsigned i = 0, len = 0;
1491 if (MAY_HAVE_DEBUG_BIND_STMTS)
1493 debug_args = decl_debug_args_lookup (node->decl);
1494 if (debug_args)
1495 len = vec_safe_length (*debug_args);
1497 for (parm = DECL_ARGUMENTS (current_function_decl), num = 0;
1498 parm; parm = DECL_CHAIN (parm), num++)
1499 if (bitmap_bit_p (args_to_skip, num) && is_gimple_reg (parm))
1501 tree ddecl;
1502 gimple *def_temp;
1504 /* This needs to be done even without
1505 MAY_HAVE_DEBUG_BIND_STMTS, otherwise if it didn't exist
1506 before, we'd end up with different SSA_NAME_VERSIONs
1507 between -g and -g0. */
1508 arg = get_or_create_ssa_default_def (cfun, parm);
1509 if (!MAY_HAVE_DEBUG_BIND_STMTS || debug_args == NULL)
1510 continue;
1512 while (i < len && (**debug_args)[i] != DECL_ORIGIN (parm))
1513 i += 2;
1514 if (i >= len)
1515 continue;
1516 ddecl = (**debug_args)[i + 1];
1517 def_temp
1518 = gimple_build_debug_bind (ddecl, unshare_expr (arg), call);
1519 gsi_insert_after (&gsi, def_temp, GSI_NEW_STMT);
1523 /* We avoid address being taken on any variable used by split part,
1524 so return slot optimization is always possible. Moreover this is
1525 required to make DECL_BY_REFERENCE work. */
1526 if (aggregate_value_p (DECL_RESULT (current_function_decl),
1527 TREE_TYPE (current_function_decl))
1528 && (!is_gimple_reg_type (TREE_TYPE (DECL_RESULT (current_function_decl)))
1529 || DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))))
1530 gimple_call_set_return_slot_opt (call, true);
1532 if (add_tsan_func_exit)
1533 tsan_func_exit_call = gimple_build_call_internal (IFN_TSAN_FUNC_EXIT, 0);
1535 /* Update return value. This is bit tricky. When we do not return,
1536 do nothing. When we return we might need to update return_bb
1537 or produce a new return statement. */
1538 if (!split_part_return_p)
1540 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1541 if (tsan_func_exit_call)
1542 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1544 else
1546 e = make_single_succ_edge (call_bb, return_bb,
1547 return_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1548 ? 0 : EDGE_FALLTHRU);
1550 /* If there is return basic block, see what value we need to store
1551 return value into and put call just before it. */
1552 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1554 real_retval = retval;
1555 if (real_retval && split_point->split_part_set_retval)
1557 gphi_iterator psi;
1559 /* See if we need new SSA_NAME for the result.
1560 When DECL_BY_REFERENCE is true, retval is actually pointer to
1561 return value and it is constant in whole function. */
1562 if (TREE_CODE (retval) == SSA_NAME
1563 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1565 retval = copy_ssa_name (retval, call);
1567 /* See if there is PHI defining return value. */
1568 for (psi = gsi_start_phis (return_bb);
1569 !gsi_end_p (psi); gsi_next (&psi))
1570 if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
1571 break;
1573 /* When there is PHI, just update its value. */
1574 if (TREE_CODE (retval) == SSA_NAME
1575 && !gsi_end_p (psi))
1576 add_phi_arg (psi.phi (), retval, e, UNKNOWN_LOCATION);
1577 /* Otherwise update the return BB itself.
1578 find_return_bb allows at most one assignment to return value,
1579 so update first statement. */
1580 else
1582 gimple_stmt_iterator bsi;
1583 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi);
1584 gsi_next (&bsi))
1585 if (greturn *return_stmt
1586 = dyn_cast <greturn *> (gsi_stmt (bsi)))
1588 gimple_return_set_retval (return_stmt, retval);
1589 break;
1591 else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN
1592 && !gimple_clobber_p (gsi_stmt (bsi)))
1594 gimple_assign_set_rhs1 (gsi_stmt (bsi), retval);
1595 break;
1597 update_stmt (gsi_stmt (bsi));
1598 /* Also adjust clobbers and debug stmts in return_bb. */
1599 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi);
1600 gsi_next (&bsi))
1602 gimple *stmt = gsi_stmt (bsi);
1603 if (gimple_clobber_p (stmt)
1604 || is_gimple_debug (stmt))
1606 ssa_op_iter iter;
1607 use_operand_p use_p;
1608 bool update = false;
1609 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1610 SSA_OP_USE)
1611 if (USE_FROM_PTR (use_p) == real_retval)
1613 SET_USE (use_p, retval);
1614 update = true;
1616 if (update)
1617 update_stmt (stmt);
1622 /* Replace retbnd with new one. */
1623 if (retbnd)
1625 gimple_stmt_iterator bsi;
1626 for (bsi = gsi_last_bb (return_bb); !gsi_end_p (bsi);
1627 gsi_prev (&bsi))
1628 if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
1630 retbnd = copy_ssa_name (retbnd, call);
1631 gimple_return_set_retbnd (gsi_stmt (bsi), retbnd);
1632 update_stmt (gsi_stmt (bsi));
1633 break;
1637 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1639 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1640 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1642 else
1644 tree restype;
1645 restype = TREE_TYPE (DECL_RESULT (current_function_decl));
1646 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1647 if (!useless_type_conversion_p (TREE_TYPE (retval), restype))
1649 gimple *cpy;
1650 tree tem = create_tmp_reg (restype);
1651 tem = make_ssa_name (tem, call);
1652 cpy = gimple_build_assign (retval, NOP_EXPR, tem);
1653 gsi_insert_after (&gsi, cpy, GSI_NEW_STMT);
1654 retval = tem;
1656 /* Build bndret call to obtain returned bounds. */
1657 if (retbnd)
1658 chkp_insert_retbnd_call (retbnd, retval, &gsi);
1659 gimple_call_set_lhs (call, retval);
1660 update_stmt (call);
1663 else
1664 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1665 if (tsan_func_exit_call)
1666 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1668 /* We don't use return block (there is either no return in function or
1669 multiple of them). So create new basic block with return statement.
1671 else
1673 greturn *ret;
1674 if (split_point->split_part_set_retval
1675 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl))))
1677 retval = DECL_RESULT (current_function_decl);
1679 if (chkp_function_instrumented_p (current_function_decl)
1680 && BOUNDED_P (retval))
1681 retbnd = create_tmp_reg (pointer_bounds_type_node);
1683 /* We use temporary register to hold value when aggregate_value_p
1684 is false. Similarly for DECL_BY_REFERENCE we must avoid extra
1685 copy. */
1686 if (!aggregate_value_p (retval, TREE_TYPE (current_function_decl))
1687 && !DECL_BY_REFERENCE (retval))
1688 retval = create_tmp_reg (TREE_TYPE (retval));
1689 if (is_gimple_reg (retval))
1691 /* When returning by reference, there is only one SSA name
1692 assigned to RESULT_DECL (that is pointer to return value).
1693 Look it up or create new one if it is missing. */
1694 if (DECL_BY_REFERENCE (retval))
1695 retval = get_or_create_ssa_default_def (cfun, retval);
1696 /* Otherwise produce new SSA name for return value. */
1697 else
1698 retval = make_ssa_name (retval, call);
1700 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1701 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1702 else
1703 gimple_call_set_lhs (call, retval);
1704 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1706 else
1708 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1709 if (retval
1710 && is_gimple_reg_type (TREE_TYPE (retval))
1711 && !is_gimple_val (retval))
1713 gassign *g
1714 = gimple_build_assign (make_ssa_name (TREE_TYPE (retval)),
1715 retval);
1716 retval = gimple_assign_lhs (g);
1717 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
1720 /* Build bndret call to obtain returned bounds. */
1721 if (retbnd)
1722 chkp_insert_retbnd_call (retbnd, retval, &gsi);
1723 if (tsan_func_exit_call)
1724 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1725 ret = gimple_build_return (retval);
1726 gsi_insert_after (&gsi, ret, GSI_NEW_STMT);
1729 free_dominance_info (CDI_DOMINATORS);
1730 free_dominance_info (CDI_POST_DOMINATORS);
1731 compute_fn_summary (node, true);
1734 /* Execute function splitting pass. */
1736 static unsigned int
1737 execute_split_functions (void)
1739 gimple_stmt_iterator bsi;
1740 basic_block bb;
1741 sreal overall_time = 0;
1742 int overall_size = 0;
1743 int todo = 0;
1744 struct cgraph_node *node = cgraph_node::get (current_function_decl);
1746 if (flags_from_decl_or_type (current_function_decl)
1747 & (ECF_NORETURN|ECF_MALLOC))
1749 if (dump_file)
1750 fprintf (dump_file, "Not splitting: noreturn/malloc function.\n");
1751 return 0;
1753 if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
1755 if (dump_file)
1756 fprintf (dump_file, "Not splitting: main function.\n");
1757 return 0;
1759 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
1761 if (dump_file)
1762 fprintf (dump_file, "Not splitting: function is unlikely executed.\n");
1763 return 0;
1765 /* This can be relaxed; function might become inlinable after splitting
1766 away the uninlinable part. */
1767 if (ipa_fn_summaries
1768 && !ipa_fn_summaries->get (node)->inlinable)
1770 if (dump_file)
1771 fprintf (dump_file, "Not splitting: not inlinable.\n");
1772 return 0;
1774 if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
1776 if (dump_file)
1777 fprintf (dump_file, "Not splitting: disregarding inline limits.\n");
1778 return 0;
1780 /* This can be relaxed; most of versioning tests actually prevents
1781 a duplication. */
1782 if (!tree_versionable_function_p (current_function_decl))
1784 if (dump_file)
1785 fprintf (dump_file, "Not splitting: not versionable.\n");
1786 return 0;
1788 /* FIXME: we could support this. */
1789 if (DECL_STRUCT_FUNCTION (current_function_decl)->static_chain_decl)
1791 if (dump_file)
1792 fprintf (dump_file, "Not splitting: nested function.\n");
1793 return 0;
1796 /* See if it makes sense to try to split.
1797 It makes sense to split if we inline, that is if we have direct calls to
1798 handle or direct calls are possibly going to appear as result of indirect
1799 inlining or LTO. Also handle -fprofile-generate as LTO to allow non-LTO
1800 training for LTO -fprofile-use build.
1802 Note that we are not completely conservative about disqualifying functions
1803 called once. It is possible that the caller is called more then once and
1804 then inlining would still benefit. */
1805 if ((!node->callers
1806 /* Local functions called once will be completely inlined most of time. */
1807 || (!node->callers->next_caller && node->local.local))
1808 && !node->address_taken
1809 && !node->has_aliases_p ()
1810 && (!flag_lto || !node->externally_visible))
1812 if (dump_file)
1813 fprintf (dump_file, "Not splitting: not called directly "
1814 "or called once.\n");
1815 return 0;
1818 /* FIXME: We can actually split if splitting reduces call overhead. */
1819 if (!flag_inline_small_functions
1820 && !DECL_DECLARED_INLINE_P (current_function_decl))
1822 if (dump_file)
1823 fprintf (dump_file, "Not splitting: not autoinlining and function"
1824 " is not inline.\n");
1825 return 0;
1828 /* We enforce splitting after loop headers when profile info is not
1829 available. */
1830 if (profile_status_for_fn (cfun) != PROFILE_READ)
1831 mark_dfs_back_edges ();
1833 /* Initialize bitmap to track forbidden calls. */
1834 forbidden_dominators = BITMAP_ALLOC (NULL);
1835 calculate_dominance_info (CDI_DOMINATORS);
1837 /* Compute local info about basic blocks and determine function size/time. */
1838 bb_info_vec.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1839 best_split_point.split_bbs = NULL;
1840 basic_block return_bb = find_return_bb ();
1841 int tsan_exit_found = -1;
1842 FOR_EACH_BB_FN (bb, cfun)
1844 sreal time = 0;
1845 int size = 0;
1846 sreal freq = bb->count.to_sreal_scale
1847 (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count);
1849 if (dump_file && (dump_flags & TDF_DETAILS))
1850 fprintf (dump_file, "Basic block %i\n", bb->index);
1852 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1854 sreal this_time;
1855 int this_size;
1856 gimple *stmt = gsi_stmt (bsi);
1858 this_size = estimate_num_insns (stmt, &eni_size_weights);
1859 this_time = (sreal)estimate_num_insns (stmt, &eni_time_weights)
1860 * freq;
1861 size += this_size;
1862 time += this_time;
1863 check_forbidden_calls (stmt);
1865 if (dump_file && (dump_flags & TDF_DETAILS))
1867 fprintf (dump_file, " freq:%4.2f size:%3i time:%4.2f ",
1868 freq.to_double (), this_size, this_time.to_double ());
1869 print_gimple_stmt (dump_file, stmt, 0);
1872 if ((flag_sanitize & SANITIZE_THREAD)
1873 && gimple_call_internal_p (stmt, IFN_TSAN_FUNC_EXIT))
1875 /* We handle TSAN_FUNC_EXIT for splitting either in the
1876 return_bb, or in its immediate predecessors. */
1877 if ((bb != return_bb && !find_edge (bb, return_bb))
1878 || (tsan_exit_found != -1
1879 && tsan_exit_found != (bb != return_bb)))
1881 if (dump_file)
1882 fprintf (dump_file, "Not splitting: TSAN_FUNC_EXIT"
1883 " in unexpected basic block.\n");
1884 BITMAP_FREE (forbidden_dominators);
1885 bb_info_vec.release ();
1886 return 0;
1888 tsan_exit_found = bb != return_bb;
1891 overall_time += time;
1892 overall_size += size;
1893 bb_info_vec[bb->index].time = time;
1894 bb_info_vec[bb->index].size = size;
1896 find_split_points (return_bb, overall_time, overall_size);
1897 if (best_split_point.split_bbs)
1899 split_function (return_bb, &best_split_point, tsan_exit_found == 1);
1900 BITMAP_FREE (best_split_point.ssa_names_to_pass);
1901 BITMAP_FREE (best_split_point.split_bbs);
1902 todo = TODO_update_ssa | TODO_cleanup_cfg;
1904 BITMAP_FREE (forbidden_dominators);
1905 bb_info_vec.release ();
1906 return todo;
1909 namespace {
1911 const pass_data pass_data_split_functions =
1913 GIMPLE_PASS, /* type */
1914 "fnsplit", /* name */
1915 OPTGROUP_NONE, /* optinfo_flags */
1916 TV_IPA_FNSPLIT, /* tv_id */
1917 PROP_cfg, /* properties_required */
1918 0, /* properties_provided */
1919 0, /* properties_destroyed */
1920 0, /* todo_flags_start */
1921 0, /* todo_flags_finish */
1924 class pass_split_functions : public gimple_opt_pass
1926 public:
1927 pass_split_functions (gcc::context *ctxt)
1928 : gimple_opt_pass (pass_data_split_functions, ctxt)
1931 /* opt_pass methods: */
1932 virtual bool gate (function *);
1933 virtual unsigned int execute (function *)
1935 return execute_split_functions ();
1938 }; // class pass_split_functions
1940 bool
1941 pass_split_functions::gate (function *)
1943 /* When doing profile feedback, we want to execute the pass after profiling
1944 is read. So disable one in early optimization. */
1945 return (flag_partial_inlining
1946 && !profile_arc_flag && !flag_branch_probabilities);
1949 } // anon namespace
1951 gimple_opt_pass *
1952 make_pass_split_functions (gcc::context *ctxt)
1954 return new pass_split_functions (ctxt);
1957 /* Execute function splitting pass. */
1959 static unsigned int
1960 execute_feedback_split_functions (void)
1962 unsigned int retval = execute_split_functions ();
1963 if (retval)
1964 retval |= TODO_rebuild_cgraph_edges;
1965 return retval;
1968 namespace {
1970 const pass_data pass_data_feedback_split_functions =
1972 GIMPLE_PASS, /* type */
1973 "feedback_fnsplit", /* name */
1974 OPTGROUP_NONE, /* optinfo_flags */
1975 TV_IPA_FNSPLIT, /* tv_id */
1976 PROP_cfg, /* properties_required */
1977 0, /* properties_provided */
1978 0, /* properties_destroyed */
1979 0, /* todo_flags_start */
1980 0, /* todo_flags_finish */
1983 class pass_feedback_split_functions : public gimple_opt_pass
1985 public:
1986 pass_feedback_split_functions (gcc::context *ctxt)
1987 : gimple_opt_pass (pass_data_feedback_split_functions, ctxt)
1990 /* opt_pass methods: */
1991 virtual bool gate (function *);
1992 virtual unsigned int execute (function *)
1994 return execute_feedback_split_functions ();
1997 }; // class pass_feedback_split_functions
1999 bool
2000 pass_feedback_split_functions::gate (function *)
2002 /* We don't need to split when profiling at all, we are producing
2003 lousy code anyway. */
2004 return (flag_partial_inlining
2005 && flag_branch_probabilities);
2008 } // anon namespace
2010 gimple_opt_pass *
2011 make_pass_feedback_split_functions (gcc::context *ctxt)
2013 return new pass_feedback_split_functions (ctxt);