* cgraphclones.c (cgraph_edge::clone): Rename gcov_count to prof_count.
[official-gcc.git] / gcc / ipa-split.c
blob7ebd51554e5694c2651c563c99f0f63a0633b389
1 /* Function splitting pass
2 Copyright (C) 2010-2017 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 if (current->header_size + call_overhead
562 >= (unsigned int)(DECL_DECLARED_INLINE_P (current_function_decl)
563 ? MAX_INLINE_INSNS_SINGLE
564 : MAX_INLINE_INSNS_AUTO))
566 if (dump_file && (dump_flags & TDF_DETAILS))
567 fprintf (dump_file,
568 " Refused: header size is too large for inline candidate\n");
569 return;
572 /* Splitting functions brings the target out of comdat group; this will
573 lead to code duplication if the function is reused by other unit.
574 Limit this duplication. This is consistent with limit in tree-sra.c
575 FIXME: with LTO we ought to be able to do better! */
576 if (DECL_ONE_ONLY (current_function_decl)
577 && current->split_size >= (unsigned int) MAX_INLINE_INSNS_AUTO)
579 if (dump_file && (dump_flags & TDF_DETAILS))
580 fprintf (dump_file,
581 " Refused: function is COMDAT and tail is too large\n");
582 return;
584 /* For comdat functions also reject very small tails; those will likely get
585 inlined back and we do not want to risk the duplication overhead.
586 FIXME: with LTO we ought to be able to do better! */
587 if (DECL_ONE_ONLY (current_function_decl)
588 && current->split_size
589 <= (unsigned int) PARAM_VALUE (PARAM_EARLY_INLINING_INSNS) / 2)
591 if (dump_file && (dump_flags & TDF_DETAILS))
592 fprintf (dump_file,
593 " Refused: function is COMDAT and tail is too small\n");
594 return;
597 /* FIXME: we currently can pass only SSA function parameters to the split
598 arguments. Once parm_adjustment infrastructure is supported by cloning,
599 we can pass more than that. */
600 if (num_args != bitmap_count_bits (current->ssa_names_to_pass))
603 if (dump_file && (dump_flags & TDF_DETAILS))
604 fprintf (dump_file,
605 " Refused: need to pass non-param values\n");
606 return;
609 /* When there are non-ssa vars used in the split region, see if they
610 are used in the header region. If so, reject the split.
611 FIXME: we can use nested function support to access both. */
612 if (!bitmap_empty_p (non_ssa_vars)
613 && !verify_non_ssa_vars (current, non_ssa_vars, return_bb))
615 if (dump_file && (dump_flags & TDF_DETAILS))
616 fprintf (dump_file,
617 " Refused: split part has non-ssa uses\n");
618 return;
621 /* If the split point is dominated by a forbidden block, reject
622 the split. */
623 if (!bitmap_empty_p (forbidden_dominators)
624 && dominated_by_forbidden (current->entry_bb))
626 if (dump_file && (dump_flags & TDF_DETAILS))
627 fprintf (dump_file,
628 " Refused: split point dominated by forbidden block\n");
629 return;
632 /* See if retval used by return bb is computed by header or split part.
633 When it is computed by split part, we need to produce return statement
634 in the split part and add code to header to pass it around.
636 This is bit tricky to test:
637 1) When there is no return_bb or no return value, we always pass
638 value around.
639 2) Invariants are always computed by caller.
640 3) For SSA we need to look if defining statement is in header or split part
641 4) For non-SSA we need to look where the var is computed. */
642 retval = find_retval (return_bb);
643 if (!retval)
645 /* If there is a return_bb with no return value in function returning
646 value by reference, also make the split part return void, otherwise
647 we expansion would try to create a non-POD temporary, which is
648 invalid. */
649 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
650 && DECL_RESULT (current_function_decl)
651 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
652 current->split_part_set_retval = false;
653 else
654 current->split_part_set_retval = true;
656 else if (is_gimple_min_invariant (retval))
657 current->split_part_set_retval = false;
658 /* Special case is value returned by reference we record as if it was non-ssa
659 set to result_decl. */
660 else if (TREE_CODE (retval) == SSA_NAME
661 && SSA_NAME_VAR (retval)
662 && TREE_CODE (SSA_NAME_VAR (retval)) == RESULT_DECL
663 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
664 current->split_part_set_retval
665 = bitmap_bit_p (non_ssa_vars, DECL_UID (SSA_NAME_VAR (retval)));
666 else if (TREE_CODE (retval) == SSA_NAME)
667 current->split_part_set_retval
668 = split_part_set_ssa_name_p (retval, current, return_bb);
669 else if (TREE_CODE (retval) == PARM_DECL)
670 current->split_part_set_retval = false;
671 else if (VAR_P (retval)
672 || TREE_CODE (retval) == RESULT_DECL)
673 current->split_part_set_retval
674 = bitmap_bit_p (non_ssa_vars, DECL_UID (retval));
675 else
676 current->split_part_set_retval = true;
678 /* See if retbnd used by return bb is computed by header or split part. */
679 retbnd = find_retbnd (return_bb);
680 if (retbnd)
682 bool split_part_set_retbnd
683 = split_part_set_ssa_name_p (retbnd, current, return_bb);
685 /* If we have both return value and bounds then keep their definitions
686 in a single function. We use SSA names to link returned bounds and
687 value and therefore do not handle cases when result is passed by
688 reference (which should not be our case anyway since bounds are
689 returned for pointers only). */
690 if ((DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))
691 && current->split_part_set_retval)
692 || split_part_set_retbnd != current->split_part_set_retval)
694 if (dump_file && (dump_flags & TDF_DETAILS))
695 fprintf (dump_file,
696 " Refused: split point splits return value and bounds\n");
697 return;
701 /* split_function fixes up at most one PHI non-virtual PHI node in return_bb,
702 for the return value. If there are other PHIs, give up. */
703 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
705 gphi_iterator psi;
707 for (psi = gsi_start_phis (return_bb); !gsi_end_p (psi); gsi_next (&psi))
708 if (!virtual_operand_p (gimple_phi_result (psi.phi ()))
709 && !(retval
710 && current->split_part_set_retval
711 && TREE_CODE (retval) == SSA_NAME
712 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))
713 && SSA_NAME_DEF_STMT (retval) == psi.phi ()))
715 if (dump_file && (dump_flags & TDF_DETAILS))
716 fprintf (dump_file,
717 " Refused: return bb has extra PHIs\n");
718 return;
722 if (dump_file && (dump_flags & TDF_DETAILS))
723 fprintf (dump_file, " Accepted!\n");
725 /* At the moment chose split point with lowest count and that leaves
726 out smallest size of header.
727 In future we might re-consider this heuristics. */
728 if (!best_split_point.split_bbs
729 || best_split_point.count
730 > current->count
731 || (best_split_point.count == current->count
732 && best_split_point.split_size < current->split_size))
735 if (dump_file && (dump_flags & TDF_DETAILS))
736 fprintf (dump_file, " New best split point!\n");
737 if (best_split_point.ssa_names_to_pass)
739 BITMAP_FREE (best_split_point.ssa_names_to_pass);
740 BITMAP_FREE (best_split_point.split_bbs);
742 best_split_point = *current;
743 best_split_point.ssa_names_to_pass = BITMAP_ALLOC (NULL);
744 bitmap_copy (best_split_point.ssa_names_to_pass,
745 current->ssa_names_to_pass);
746 best_split_point.split_bbs = BITMAP_ALLOC (NULL);
747 bitmap_copy (best_split_point.split_bbs, current->split_bbs);
751 /* Return basic block containing RETURN statement. We allow basic blocks
752 of the form:
753 <retval> = tmp_var;
754 return <retval>
755 but return_bb can not be more complex than this (except for
756 -fsanitize=thread we allow TSAN_FUNC_EXIT () internal call in there).
757 If nothing is found, return the exit block.
759 When there are multiple RETURN statement, chose one with return value,
760 since that one is more likely shared by multiple code paths.
762 Return BB is special, because for function splitting it is the only
763 basic block that is duplicated in between header and split part of the
764 function.
766 TODO: We might support multiple return blocks. */
768 static basic_block
769 find_return_bb (void)
771 edge e;
772 basic_block return_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
773 gimple_stmt_iterator bsi;
774 bool found_return = false;
775 tree retval = NULL_TREE;
777 if (!single_pred_p (EXIT_BLOCK_PTR_FOR_FN (cfun)))
778 return return_bb;
780 e = single_pred_edge (EXIT_BLOCK_PTR_FOR_FN (cfun));
781 for (bsi = gsi_last_bb (e->src); !gsi_end_p (bsi); gsi_prev (&bsi))
783 gimple *stmt = gsi_stmt (bsi);
784 if (gimple_code (stmt) == GIMPLE_LABEL
785 || is_gimple_debug (stmt)
786 || gimple_clobber_p (stmt))
788 else if (gimple_code (stmt) == GIMPLE_ASSIGN
789 && found_return
790 && gimple_assign_single_p (stmt)
791 && (auto_var_in_fn_p (gimple_assign_rhs1 (stmt),
792 current_function_decl)
793 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
794 && retval == gimple_assign_lhs (stmt))
796 else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
798 found_return = true;
799 retval = gimple_return_retval (return_stmt);
801 /* For -fsanitize=thread, allow also TSAN_FUNC_EXIT () in the return
802 bb. */
803 else if ((flag_sanitize & SANITIZE_THREAD)
804 && gimple_call_internal_p (stmt, IFN_TSAN_FUNC_EXIT))
806 else
807 break;
809 if (gsi_end_p (bsi) && found_return)
810 return_bb = e->src;
812 return return_bb;
815 /* Given return basic block RETURN_BB, see where return value is really
816 stored. */
817 static tree
818 find_retval (basic_block return_bb)
820 gimple_stmt_iterator bsi;
821 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
822 if (greturn *return_stmt = dyn_cast <greturn *> (gsi_stmt (bsi)))
823 return gimple_return_retval (return_stmt);
824 else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN
825 && !gimple_clobber_p (gsi_stmt (bsi)))
826 return gimple_assign_rhs1 (gsi_stmt (bsi));
827 return NULL;
830 /* Given return basic block RETURN_BB, see where return bounds are really
831 stored. */
832 static tree
833 find_retbnd (basic_block return_bb)
835 gimple_stmt_iterator bsi;
836 for (bsi = gsi_last_bb (return_bb); !gsi_end_p (bsi); gsi_prev (&bsi))
837 if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
838 return gimple_return_retbnd (gsi_stmt (bsi));
839 return NULL;
842 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
843 variable, mark it as used in bitmap passed via DATA.
844 Return true when access to T prevents splitting the function. */
846 static bool
847 mark_nonssa_use (gimple *, tree t, tree, void *data)
849 t = get_base_address (t);
851 if (!t || is_gimple_reg (t))
852 return false;
854 /* At present we can't pass non-SSA arguments to split function.
855 FIXME: this can be relaxed by passing references to arguments. */
856 if (TREE_CODE (t) == PARM_DECL)
858 if (dump_file && (dump_flags & TDF_DETAILS))
859 fprintf (dump_file,
860 "Cannot split: use of non-ssa function parameter.\n");
861 return true;
864 if ((VAR_P (t) && auto_var_in_fn_p (t, current_function_decl))
865 || TREE_CODE (t) == RESULT_DECL
866 || (TREE_CODE (t) == LABEL_DECL && FORCED_LABEL (t)))
867 bitmap_set_bit ((bitmap)data, DECL_UID (t));
869 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
870 to pretend that the value pointed to is actual result decl. */
871 if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
872 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
873 && SSA_NAME_VAR (TREE_OPERAND (t, 0))
874 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
875 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
876 return
877 bitmap_bit_p ((bitmap)data,
878 DECL_UID (DECL_RESULT (current_function_decl)));
880 return false;
883 /* Compute local properties of basic block BB we collect when looking for
884 split points. We look for ssa defs and store them in SET_SSA_NAMES,
885 for ssa uses and store them in USED_SSA_NAMES and for any non-SSA automatic
886 vars stored in NON_SSA_VARS.
888 When BB has edge to RETURN_BB, collect uses in RETURN_BB too.
890 Return false when BB contains something that prevents it from being put into
891 split function. */
893 static bool
894 visit_bb (basic_block bb, basic_block return_bb,
895 bitmap set_ssa_names, bitmap used_ssa_names,
896 bitmap non_ssa_vars)
898 edge e;
899 edge_iterator ei;
900 bool can_split = true;
902 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
903 gsi_next (&bsi))
905 gimple *stmt = gsi_stmt (bsi);
906 tree op;
907 ssa_op_iter iter;
908 tree decl;
910 if (is_gimple_debug (stmt))
911 continue;
913 if (gimple_clobber_p (stmt))
914 continue;
916 /* FIXME: We can split regions containing EH. We can not however
917 split RESX, EH_DISPATCH and EH_POINTER referring to same region
918 into different partitions. This would require tracking of
919 EH regions and checking in consider_split_point if they
920 are not used elsewhere. */
921 if (gimple_code (stmt) == GIMPLE_RESX)
923 if (dump_file && (dump_flags & TDF_DETAILS))
924 fprintf (dump_file, "Cannot split: resx.\n");
925 can_split = false;
927 if (gimple_code (stmt) == GIMPLE_EH_DISPATCH)
929 if (dump_file && (dump_flags & TDF_DETAILS))
930 fprintf (dump_file, "Cannot split: eh dispatch.\n");
931 can_split = false;
934 /* Check builtins that prevent splitting. */
935 if (gimple_code (stmt) == GIMPLE_CALL
936 && (decl = gimple_call_fndecl (stmt)) != NULL_TREE
937 && DECL_BUILT_IN (decl)
938 && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
939 switch (DECL_FUNCTION_CODE (decl))
941 /* FIXME: once we will allow passing non-parm values to split part,
942 we need to be sure to handle correct builtin_stack_save and
943 builtin_stack_restore. At the moment we are safe; there is no
944 way to store builtin_stack_save result in non-SSA variable
945 since all calls to those are compiler generated. */
946 case BUILT_IN_APPLY:
947 case BUILT_IN_APPLY_ARGS:
948 case BUILT_IN_VA_START:
949 if (dump_file && (dump_flags & TDF_DETAILS))
950 fprintf (dump_file,
951 "Cannot split: builtin_apply and va_start.\n");
952 can_split = false;
953 break;
954 case BUILT_IN_EH_POINTER:
955 if (dump_file && (dump_flags & TDF_DETAILS))
956 fprintf (dump_file, "Cannot split: builtin_eh_pointer.\n");
957 can_split = false;
958 break;
959 default:
960 break;
963 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
964 bitmap_set_bit (set_ssa_names, SSA_NAME_VERSION (op));
965 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
966 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
967 can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
968 mark_nonssa_use,
969 mark_nonssa_use,
970 mark_nonssa_use);
972 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
973 gsi_next (&bsi))
975 gphi *stmt = bsi.phi ();
976 unsigned int i;
978 if (virtual_operand_p (gimple_phi_result (stmt)))
979 continue;
980 bitmap_set_bit (set_ssa_names,
981 SSA_NAME_VERSION (gimple_phi_result (stmt)));
982 for (i = 0; i < gimple_phi_num_args (stmt); i++)
984 tree op = gimple_phi_arg_def (stmt, i);
985 if (TREE_CODE (op) == SSA_NAME)
986 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
988 can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
989 mark_nonssa_use,
990 mark_nonssa_use,
991 mark_nonssa_use);
993 /* Record also uses coming from PHI operand in return BB. */
994 FOR_EACH_EDGE (e, ei, bb->succs)
995 if (e->dest == return_bb)
997 for (gphi_iterator bsi = gsi_start_phis (return_bb);
998 !gsi_end_p (bsi);
999 gsi_next (&bsi))
1001 gphi *stmt = bsi.phi ();
1002 tree op = gimple_phi_arg_def (stmt, e->dest_idx);
1004 if (virtual_operand_p (gimple_phi_result (stmt)))
1005 continue;
1006 if (TREE_CODE (op) == SSA_NAME)
1007 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
1008 else
1009 can_split &= !mark_nonssa_use (stmt, op, op, non_ssa_vars);
1012 return can_split;
1015 /* Stack entry for recursive DFS walk in find_split_point. */
1017 struct stack_entry
1019 /* Basic block we are examining. */
1020 basic_block bb;
1022 /* SSA names set and used by the BB and all BBs reachable
1023 from it via DFS walk. */
1024 bitmap set_ssa_names, used_ssa_names;
1025 bitmap non_ssa_vars;
1027 /* All BBS visited from this BB via DFS walk. */
1028 bitmap bbs_visited;
1030 /* Last examined edge in DFS walk. Since we walk unoriented graph,
1031 the value is up to sum of incoming and outgoing edges of BB. */
1032 unsigned int edge_num;
1034 /* Stack entry index of earliest BB reachable from current BB
1035 or any BB visited later in DFS walk. */
1036 int earliest;
1038 /* Overall time and size of all BBs reached from this BB in DFS walk. */
1039 sreal overall_time;
1040 int overall_size;
1042 /* When false we can not split on this BB. */
1043 bool can_split;
1047 /* Find all articulations and call consider_split on them.
1048 OVERALL_TIME and OVERALL_SIZE is time and size of the function.
1050 We perform basic algorithm for finding an articulation in a graph
1051 created from CFG by considering it to be an unoriented graph.
1053 The articulation is discovered via DFS walk. We collect earliest
1054 basic block on stack that is reachable via backward edge. Articulation
1055 is any basic block such that there is no backward edge bypassing it.
1056 To reduce stack usage we maintain heap allocated stack in STACK vector.
1057 AUX pointer of BB is set to index it appears in the stack or -1 once
1058 it is visited and popped off the stack.
1060 The algorithm finds articulation after visiting the whole component
1061 reachable by it. This makes it convenient to collect information about
1062 the component used by consider_split. */
1064 static void
1065 find_split_points (basic_block return_bb, sreal overall_time, int overall_size)
1067 stack_entry first;
1068 vec<stack_entry> stack = vNULL;
1069 basic_block bb;
1070 struct split_point current;
1072 current.header_time = overall_time;
1073 current.header_size = overall_size;
1074 current.split_time = 0;
1075 current.split_size = 0;
1076 current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
1078 first.bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1079 first.edge_num = 0;
1080 first.overall_time = 0;
1081 first.overall_size = 0;
1082 first.earliest = INT_MAX;
1083 first.set_ssa_names = 0;
1084 first.used_ssa_names = 0;
1085 first.non_ssa_vars = 0;
1086 first.bbs_visited = 0;
1087 first.can_split = false;
1088 stack.safe_push (first);
1089 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(intptr_t)-1;
1091 while (!stack.is_empty ())
1093 stack_entry *entry = &stack.last ();
1095 /* We are walking an acyclic graph, so edge_num counts
1096 succ and pred edges together. However when considering
1097 articulation, we want to have processed everything reachable
1098 from articulation but nothing that reaches into it. */
1099 if (entry->edge_num == EDGE_COUNT (entry->bb->succs)
1100 && entry->bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1102 int pos = stack.length ();
1103 entry->can_split &= visit_bb (entry->bb, return_bb,
1104 entry->set_ssa_names,
1105 entry->used_ssa_names,
1106 entry->non_ssa_vars);
1107 if (pos <= entry->earliest && !entry->can_split
1108 && dump_file && (dump_flags & TDF_DETAILS))
1109 fprintf (dump_file,
1110 "found articulation at bb %i but can not split\n",
1111 entry->bb->index);
1112 if (pos <= entry->earliest && entry->can_split)
1114 if (dump_file && (dump_flags & TDF_DETAILS))
1115 fprintf (dump_file, "found articulation at bb %i\n",
1116 entry->bb->index);
1117 current.entry_bb = entry->bb;
1118 current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
1119 bitmap_and_compl (current.ssa_names_to_pass,
1120 entry->used_ssa_names, entry->set_ssa_names);
1121 current.header_time = overall_time - entry->overall_time;
1122 current.header_size = overall_size - entry->overall_size;
1123 current.split_time = entry->overall_time;
1124 current.split_size = entry->overall_size;
1125 current.split_bbs = entry->bbs_visited;
1126 consider_split (&current, entry->non_ssa_vars, return_bb);
1127 BITMAP_FREE (current.ssa_names_to_pass);
1130 /* Do actual DFS walk. */
1131 if (entry->edge_num
1132 < (EDGE_COUNT (entry->bb->succs)
1133 + EDGE_COUNT (entry->bb->preds)))
1135 edge e;
1136 basic_block dest;
1137 if (entry->edge_num < EDGE_COUNT (entry->bb->succs))
1139 e = EDGE_SUCC (entry->bb, entry->edge_num);
1140 dest = e->dest;
1142 else
1144 e = EDGE_PRED (entry->bb, entry->edge_num
1145 - EDGE_COUNT (entry->bb->succs));
1146 dest = e->src;
1149 entry->edge_num++;
1151 /* New BB to visit, push it to the stack. */
1152 if (dest != return_bb && dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1153 && !dest->aux)
1155 stack_entry new_entry;
1157 new_entry.bb = dest;
1158 new_entry.edge_num = 0;
1159 new_entry.overall_time
1160 = bb_info_vec[dest->index].time;
1161 new_entry.overall_size
1162 = bb_info_vec[dest->index].size;
1163 new_entry.earliest = INT_MAX;
1164 new_entry.set_ssa_names = BITMAP_ALLOC (NULL);
1165 new_entry.used_ssa_names = BITMAP_ALLOC (NULL);
1166 new_entry.bbs_visited = BITMAP_ALLOC (NULL);
1167 new_entry.non_ssa_vars = BITMAP_ALLOC (NULL);
1168 new_entry.can_split = true;
1169 bitmap_set_bit (new_entry.bbs_visited, dest->index);
1170 stack.safe_push (new_entry);
1171 dest->aux = (void *)(intptr_t)stack.length ();
1173 /* Back edge found, record the earliest point. */
1174 else if ((intptr_t)dest->aux > 0
1175 && (intptr_t)dest->aux < entry->earliest)
1176 entry->earliest = (intptr_t)dest->aux;
1178 /* We are done with examining the edges. Pop off the value from stack
1179 and merge stuff we accumulate during the walk. */
1180 else if (entry->bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1182 stack_entry *prev = &stack[stack.length () - 2];
1184 entry->bb->aux = (void *)(intptr_t)-1;
1185 prev->can_split &= entry->can_split;
1186 if (prev->set_ssa_names)
1188 bitmap_ior_into (prev->set_ssa_names, entry->set_ssa_names);
1189 bitmap_ior_into (prev->used_ssa_names, entry->used_ssa_names);
1190 bitmap_ior_into (prev->bbs_visited, entry->bbs_visited);
1191 bitmap_ior_into (prev->non_ssa_vars, entry->non_ssa_vars);
1193 if (prev->earliest > entry->earliest)
1194 prev->earliest = entry->earliest;
1195 prev->overall_time += entry->overall_time;
1196 prev->overall_size += entry->overall_size;
1197 BITMAP_FREE (entry->set_ssa_names);
1198 BITMAP_FREE (entry->used_ssa_names);
1199 BITMAP_FREE (entry->bbs_visited);
1200 BITMAP_FREE (entry->non_ssa_vars);
1201 stack.pop ();
1203 else
1204 stack.pop ();
1206 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = NULL;
1207 FOR_EACH_BB_FN (bb, cfun)
1208 bb->aux = NULL;
1209 stack.release ();
1210 BITMAP_FREE (current.ssa_names_to_pass);
1213 /* Split function at SPLIT_POINT. */
1215 static void
1216 split_function (basic_block return_bb, struct split_point *split_point,
1217 bool add_tsan_func_exit)
1219 vec<tree> args_to_pass = vNULL;
1220 bitmap args_to_skip;
1221 tree parm;
1222 int num = 0;
1223 cgraph_node *node, *cur_node = cgraph_node::get (current_function_decl);
1224 basic_block call_bb;
1225 gcall *call, *tsan_func_exit_call = NULL;
1226 edge e;
1227 edge_iterator ei;
1228 tree retval = NULL, real_retval = NULL, retbnd = NULL;
1229 bool with_bounds = chkp_function_instrumented_p (current_function_decl);
1230 gimple *last_stmt = NULL;
1231 unsigned int i;
1232 tree arg, ddef;
1234 if (dump_file)
1236 fprintf (dump_file, "\n\nSplitting function at:\n");
1237 dump_split_point (dump_file, split_point);
1240 if (cur_node->local.can_change_signature)
1241 args_to_skip = BITMAP_ALLOC (NULL);
1242 else
1243 args_to_skip = NULL;
1245 /* Collect the parameters of new function and args_to_skip bitmap. */
1246 for (parm = DECL_ARGUMENTS (current_function_decl);
1247 parm; parm = DECL_CHAIN (parm), num++)
1248 if (args_to_skip
1249 && (!is_gimple_reg (parm)
1250 || (ddef = ssa_default_def (cfun, parm)) == NULL_TREE
1251 || !bitmap_bit_p (split_point->ssa_names_to_pass,
1252 SSA_NAME_VERSION (ddef))))
1253 bitmap_set_bit (args_to_skip, num);
1254 else
1256 /* This parm might not have been used up to now, but is going to be
1257 used, hence register it. */
1258 if (is_gimple_reg (parm))
1259 arg = get_or_create_ssa_default_def (cfun, parm);
1260 else
1261 arg = parm;
1263 if (!useless_type_conversion_p (DECL_ARG_TYPE (parm), TREE_TYPE (arg)))
1264 arg = fold_convert (DECL_ARG_TYPE (parm), arg);
1265 args_to_pass.safe_push (arg);
1268 /* See if the split function will return. */
1269 bool split_part_return_p = false;
1270 FOR_EACH_EDGE (e, ei, return_bb->preds)
1272 if (bitmap_bit_p (split_point->split_bbs, e->src->index))
1273 split_part_return_p = true;
1276 /* Add return block to what will become the split function.
1277 We do not return; no return block is needed. */
1278 if (!split_part_return_p)
1280 /* We have no return block, so nothing is needed. */
1281 else if (return_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1283 /* When we do not want to return value, we need to construct
1284 new return block with empty return statement.
1285 FIXME: Once we are able to change return type, we should change function
1286 to return void instead of just outputting function with undefined return
1287 value. For structures this affects quality of codegen. */
1288 else if ((retval = find_retval (return_bb))
1289 && !split_point->split_part_set_retval)
1291 bool redirected = true;
1292 basic_block new_return_bb = create_basic_block (NULL, 0, return_bb);
1293 gimple_stmt_iterator gsi = gsi_start_bb (new_return_bb);
1294 gsi_insert_after (&gsi, gimple_build_return (NULL), GSI_NEW_STMT);
1295 new_return_bb->count = profile_count::zero ();
1296 while (redirected)
1298 redirected = false;
1299 FOR_EACH_EDGE (e, ei, return_bb->preds)
1300 if (bitmap_bit_p (split_point->split_bbs, e->src->index))
1302 new_return_bb->count += e->count ();
1303 redirect_edge_and_branch (e, new_return_bb);
1304 redirected = true;
1305 break;
1308 e = make_single_succ_edge (new_return_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
1309 add_bb_to_loop (new_return_bb, current_loops->tree_root);
1310 bitmap_set_bit (split_point->split_bbs, new_return_bb->index);
1311 retbnd = find_retbnd (return_bb);
1313 /* When we pass around the value, use existing return block. */
1314 else
1316 bitmap_set_bit (split_point->split_bbs, return_bb->index);
1317 retbnd = find_retbnd (return_bb);
1320 /* If RETURN_BB has virtual operand PHIs, they must be removed and the
1321 virtual operand marked for renaming as we change the CFG in a way that
1322 tree-inline is not able to compensate for.
1324 Note this can happen whether or not we have a return value. If we have
1325 a return value, then RETURN_BB may have PHIs for real operands too. */
1326 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1328 bool phi_p = false;
1329 for (gphi_iterator gsi = gsi_start_phis (return_bb);
1330 !gsi_end_p (gsi);)
1332 gphi *stmt = gsi.phi ();
1333 if (!virtual_operand_p (gimple_phi_result (stmt)))
1335 gsi_next (&gsi);
1336 continue;
1338 mark_virtual_phi_result_for_renaming (stmt);
1339 remove_phi_node (&gsi, true);
1340 phi_p = true;
1342 /* In reality we have to rename the reaching definition of the
1343 virtual operand at return_bb as we will eventually release it
1344 when we remove the code region we outlined.
1345 So we have to rename all immediate virtual uses of that region
1346 if we didn't see a PHI definition yet. */
1347 /* ??? In real reality we want to set the reaching vdef of the
1348 entry of the SESE region as the vuse of the call and the reaching
1349 vdef of the exit of the SESE region as the vdef of the call. */
1350 if (!phi_p)
1351 for (gimple_stmt_iterator gsi = gsi_start_bb (return_bb);
1352 !gsi_end_p (gsi);
1353 gsi_next (&gsi))
1355 gimple *stmt = gsi_stmt (gsi);
1356 if (gimple_vuse (stmt))
1358 gimple_set_vuse (stmt, NULL_TREE);
1359 update_stmt (stmt);
1361 if (gimple_vdef (stmt))
1362 break;
1366 /* Now create the actual clone. */
1367 cgraph_edge::rebuild_edges ();
1368 node = cur_node->create_version_clone_with_body
1369 (vNULL, NULL, args_to_skip,
1370 !split_part_return_p || !split_point->split_part_set_retval,
1371 split_point->split_bbs, split_point->entry_bb, "part");
1373 node->split_part = true;
1375 if (cur_node->same_comdat_group)
1377 /* TODO: call is versionable if we make sure that all
1378 callers are inside of a comdat group. */
1379 cur_node->calls_comdat_local = 1;
1380 node->add_to_same_comdat_group (cur_node);
1384 /* Let's take a time profile for splitted function. */
1385 node->tp_first_run = cur_node->tp_first_run + 1;
1387 /* For usual cloning it is enough to clear builtin only when signature
1388 changes. For partial inlining we however can not expect the part
1389 of builtin implementation to have same semantic as the whole. */
1390 if (DECL_BUILT_IN (node->decl))
1392 DECL_BUILT_IN_CLASS (node->decl) = NOT_BUILT_IN;
1393 DECL_FUNCTION_CODE (node->decl) = (enum built_in_function) 0;
1396 /* If return_bb contains any clobbers that refer to SSA_NAMEs
1397 set in the split part, remove them. Also reset debug stmts that
1398 refer to SSA_NAMEs set in the split part. */
1399 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1401 gimple_stmt_iterator gsi = gsi_start_bb (return_bb);
1402 while (!gsi_end_p (gsi))
1404 tree op;
1405 ssa_op_iter iter;
1406 gimple *stmt = gsi_stmt (gsi);
1407 bool remove = false;
1408 if (gimple_clobber_p (stmt) || is_gimple_debug (stmt))
1409 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
1411 basic_block bb = gimple_bb (SSA_NAME_DEF_STMT (op));
1412 if (op != retval
1413 && bb
1414 && bb != return_bb
1415 && bitmap_bit_p (split_point->split_bbs, bb->index))
1417 if (is_gimple_debug (stmt))
1419 gimple_debug_bind_reset_value (stmt);
1420 update_stmt (stmt);
1422 else
1423 remove = true;
1424 break;
1427 if (remove)
1428 gsi_remove (&gsi, true);
1429 else
1430 gsi_next (&gsi);
1434 /* If the original function is instrumented then it's
1435 part is also instrumented. */
1436 if (with_bounds)
1437 chkp_function_mark_instrumented (node->decl);
1439 /* If the original function is declared inline, there is no point in issuing
1440 a warning for the non-inlinable part. */
1441 DECL_NO_INLINE_WARNING_P (node->decl) = 1;
1442 cur_node->remove_callees ();
1443 cur_node->remove_all_references ();
1444 if (!split_part_return_p)
1445 TREE_THIS_VOLATILE (node->decl) = 1;
1446 if (dump_file)
1447 dump_function_to_file (node->decl, dump_file, dump_flags);
1449 /* Create the basic block we place call into. It is the entry basic block
1450 split after last label. */
1451 call_bb = split_point->entry_bb;
1452 for (gimple_stmt_iterator gsi = gsi_start_bb (call_bb); !gsi_end_p (gsi);)
1453 if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
1455 last_stmt = gsi_stmt (gsi);
1456 gsi_next (&gsi);
1458 else
1459 break;
1460 call_bb->count = split_point->count;
1461 e = split_block (split_point->entry_bb, last_stmt);
1462 remove_edge (e);
1464 /* Produce the call statement. */
1465 gimple_stmt_iterator gsi = gsi_last_bb (call_bb);
1466 FOR_EACH_VEC_ELT (args_to_pass, i, arg)
1467 if (!is_gimple_val (arg))
1469 arg = force_gimple_operand_gsi (&gsi, arg, true, NULL_TREE,
1470 false, GSI_CONTINUE_LINKING);
1471 args_to_pass[i] = arg;
1473 call = gimple_build_call_vec (node->decl, args_to_pass);
1474 gimple_call_set_with_bounds (call, with_bounds);
1475 gimple_set_block (call, DECL_INITIAL (current_function_decl));
1476 args_to_pass.release ();
1478 /* For optimized away parameters, add on the caller side
1479 before the call
1480 DEBUG D#X => parm_Y(D)
1481 stmts and associate D#X with parm in decl_debug_args_lookup
1482 vector to say for debug info that if parameter parm had been passed,
1483 it would have value parm_Y(D). */
1484 if (args_to_skip)
1486 vec<tree, va_gc> **debug_args = NULL;
1487 unsigned i = 0, len = 0;
1488 if (MAY_HAVE_DEBUG_STMTS)
1490 debug_args = decl_debug_args_lookup (node->decl);
1491 if (debug_args)
1492 len = vec_safe_length (*debug_args);
1494 for (parm = DECL_ARGUMENTS (current_function_decl), num = 0;
1495 parm; parm = DECL_CHAIN (parm), num++)
1496 if (bitmap_bit_p (args_to_skip, num) && is_gimple_reg (parm))
1498 tree ddecl;
1499 gimple *def_temp;
1501 /* This needs to be done even without MAY_HAVE_DEBUG_STMTS,
1502 otherwise if it didn't exist before, we'd end up with
1503 different SSA_NAME_VERSIONs between -g and -g0. */
1504 arg = get_or_create_ssa_default_def (cfun, parm);
1505 if (!MAY_HAVE_DEBUG_STMTS || debug_args == NULL)
1506 continue;
1508 while (i < len && (**debug_args)[i] != DECL_ORIGIN (parm))
1509 i += 2;
1510 if (i >= len)
1511 continue;
1512 ddecl = (**debug_args)[i + 1];
1513 def_temp
1514 = gimple_build_debug_bind (ddecl, unshare_expr (arg), call);
1515 gsi_insert_after (&gsi, def_temp, GSI_NEW_STMT);
1519 /* We avoid address being taken on any variable used by split part,
1520 so return slot optimization is always possible. Moreover this is
1521 required to make DECL_BY_REFERENCE work. */
1522 if (aggregate_value_p (DECL_RESULT (current_function_decl),
1523 TREE_TYPE (current_function_decl))
1524 && (!is_gimple_reg_type (TREE_TYPE (DECL_RESULT (current_function_decl)))
1525 || DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))))
1526 gimple_call_set_return_slot_opt (call, true);
1528 if (add_tsan_func_exit)
1529 tsan_func_exit_call = gimple_build_call_internal (IFN_TSAN_FUNC_EXIT, 0);
1531 /* Update return value. This is bit tricky. When we do not return,
1532 do nothing. When we return we might need to update return_bb
1533 or produce a new return statement. */
1534 if (!split_part_return_p)
1536 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1537 if (tsan_func_exit_call)
1538 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1540 else
1542 e = make_single_succ_edge (call_bb, return_bb,
1543 return_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1544 ? 0 : EDGE_FALLTHRU);
1546 /* If there is return basic block, see what value we need to store
1547 return value into and put call just before it. */
1548 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1550 real_retval = retval;
1551 if (real_retval && split_point->split_part_set_retval)
1553 gphi_iterator psi;
1555 /* See if we need new SSA_NAME for the result.
1556 When DECL_BY_REFERENCE is true, retval is actually pointer to
1557 return value and it is constant in whole function. */
1558 if (TREE_CODE (retval) == SSA_NAME
1559 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1561 retval = copy_ssa_name (retval, call);
1563 /* See if there is PHI defining return value. */
1564 for (psi = gsi_start_phis (return_bb);
1565 !gsi_end_p (psi); gsi_next (&psi))
1566 if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
1567 break;
1569 /* When there is PHI, just update its value. */
1570 if (TREE_CODE (retval) == SSA_NAME
1571 && !gsi_end_p (psi))
1572 add_phi_arg (psi.phi (), retval, e, UNKNOWN_LOCATION);
1573 /* Otherwise update the return BB itself.
1574 find_return_bb allows at most one assignment to return value,
1575 so update first statement. */
1576 else
1578 gimple_stmt_iterator bsi;
1579 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi);
1580 gsi_next (&bsi))
1581 if (greturn *return_stmt
1582 = dyn_cast <greturn *> (gsi_stmt (bsi)))
1584 gimple_return_set_retval (return_stmt, retval);
1585 break;
1587 else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN
1588 && !gimple_clobber_p (gsi_stmt (bsi)))
1590 gimple_assign_set_rhs1 (gsi_stmt (bsi), retval);
1591 break;
1593 update_stmt (gsi_stmt (bsi));
1594 /* Also adjust clobbers and debug stmts in return_bb. */
1595 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi);
1596 gsi_next (&bsi))
1598 gimple *stmt = gsi_stmt (bsi);
1599 if (gimple_clobber_p (stmt)
1600 || is_gimple_debug (stmt))
1602 ssa_op_iter iter;
1603 use_operand_p use_p;
1604 bool update = false;
1605 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1606 SSA_OP_USE)
1607 if (USE_FROM_PTR (use_p) == real_retval)
1609 SET_USE (use_p, retval);
1610 update = true;
1612 if (update)
1613 update_stmt (stmt);
1618 /* Replace retbnd with new one. */
1619 if (retbnd)
1621 gimple_stmt_iterator bsi;
1622 for (bsi = gsi_last_bb (return_bb); !gsi_end_p (bsi);
1623 gsi_prev (&bsi))
1624 if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
1626 retbnd = copy_ssa_name (retbnd, call);
1627 gimple_return_set_retbnd (gsi_stmt (bsi), retbnd);
1628 update_stmt (gsi_stmt (bsi));
1629 break;
1633 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1635 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1636 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1638 else
1640 tree restype;
1641 restype = TREE_TYPE (DECL_RESULT (current_function_decl));
1642 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1643 if (!useless_type_conversion_p (TREE_TYPE (retval), restype))
1645 gimple *cpy;
1646 tree tem = create_tmp_reg (restype);
1647 tem = make_ssa_name (tem, call);
1648 cpy = gimple_build_assign (retval, NOP_EXPR, tem);
1649 gsi_insert_after (&gsi, cpy, GSI_NEW_STMT);
1650 retval = tem;
1652 /* Build bndret call to obtain returned bounds. */
1653 if (retbnd)
1654 chkp_insert_retbnd_call (retbnd, retval, &gsi);
1655 gimple_call_set_lhs (call, retval);
1656 update_stmt (call);
1659 else
1660 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1661 if (tsan_func_exit_call)
1662 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1664 /* We don't use return block (there is either no return in function or
1665 multiple of them). So create new basic block with return statement.
1667 else
1669 greturn *ret;
1670 if (split_point->split_part_set_retval
1671 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl))))
1673 retval = DECL_RESULT (current_function_decl);
1675 if (chkp_function_instrumented_p (current_function_decl)
1676 && BOUNDED_P (retval))
1677 retbnd = create_tmp_reg (pointer_bounds_type_node);
1679 /* We use temporary register to hold value when aggregate_value_p
1680 is false. Similarly for DECL_BY_REFERENCE we must avoid extra
1681 copy. */
1682 if (!aggregate_value_p (retval, TREE_TYPE (current_function_decl))
1683 && !DECL_BY_REFERENCE (retval))
1684 retval = create_tmp_reg (TREE_TYPE (retval));
1685 if (is_gimple_reg (retval))
1687 /* When returning by reference, there is only one SSA name
1688 assigned to RESULT_DECL (that is pointer to return value).
1689 Look it up or create new one if it is missing. */
1690 if (DECL_BY_REFERENCE (retval))
1691 retval = get_or_create_ssa_default_def (cfun, retval);
1692 /* Otherwise produce new SSA name for return value. */
1693 else
1694 retval = make_ssa_name (retval, call);
1696 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1697 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1698 else
1699 gimple_call_set_lhs (call, retval);
1700 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1702 else
1704 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1705 if (retval
1706 && is_gimple_reg_type (TREE_TYPE (retval))
1707 && !is_gimple_val (retval))
1709 gassign *g
1710 = gimple_build_assign (make_ssa_name (TREE_TYPE (retval)),
1711 retval);
1712 retval = gimple_assign_lhs (g);
1713 gsi_insert_after (&gsi, g, GSI_NEW_STMT);
1716 /* Build bndret call to obtain returned bounds. */
1717 if (retbnd)
1718 chkp_insert_retbnd_call (retbnd, retval, &gsi);
1719 if (tsan_func_exit_call)
1720 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1721 ret = gimple_build_return (retval);
1722 gsi_insert_after (&gsi, ret, GSI_NEW_STMT);
1725 free_dominance_info (CDI_DOMINATORS);
1726 free_dominance_info (CDI_POST_DOMINATORS);
1727 compute_fn_summary (node, true);
1730 /* Execute function splitting pass. */
1732 static unsigned int
1733 execute_split_functions (void)
1735 gimple_stmt_iterator bsi;
1736 basic_block bb;
1737 sreal overall_time = 0;
1738 int overall_size = 0;
1739 int todo = 0;
1740 struct cgraph_node *node = cgraph_node::get (current_function_decl);
1742 if (flags_from_decl_or_type (current_function_decl)
1743 & (ECF_NORETURN|ECF_MALLOC))
1745 if (dump_file)
1746 fprintf (dump_file, "Not splitting: noreturn/malloc function.\n");
1747 return 0;
1749 if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
1751 if (dump_file)
1752 fprintf (dump_file, "Not splitting: main function.\n");
1753 return 0;
1755 if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
1757 if (dump_file)
1758 fprintf (dump_file, "Not splitting: function is unlikely executed.\n");
1759 return 0;
1761 /* This can be relaxed; function might become inlinable after splitting
1762 away the uninlinable part. */
1763 if (ipa_fn_summaries
1764 && !ipa_fn_summaries->get (node)->inlinable)
1766 if (dump_file)
1767 fprintf (dump_file, "Not splitting: not inlinable.\n");
1768 return 0;
1770 if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
1772 if (dump_file)
1773 fprintf (dump_file, "Not splitting: disregarding inline limits.\n");
1774 return 0;
1776 /* This can be relaxed; most of versioning tests actually prevents
1777 a duplication. */
1778 if (!tree_versionable_function_p (current_function_decl))
1780 if (dump_file)
1781 fprintf (dump_file, "Not splitting: not versionable.\n");
1782 return 0;
1784 /* FIXME: we could support this. */
1785 if (DECL_STRUCT_FUNCTION (current_function_decl)->static_chain_decl)
1787 if (dump_file)
1788 fprintf (dump_file, "Not splitting: nested function.\n");
1789 return 0;
1792 /* See if it makes sense to try to split.
1793 It makes sense to split if we inline, that is if we have direct calls to
1794 handle or direct calls are possibly going to appear as result of indirect
1795 inlining or LTO. Also handle -fprofile-generate as LTO to allow non-LTO
1796 training for LTO -fprofile-use build.
1798 Note that we are not completely conservative about disqualifying functions
1799 called once. It is possible that the caller is called more then once and
1800 then inlining would still benefit. */
1801 if ((!node->callers
1802 /* Local functions called once will be completely inlined most of time. */
1803 || (!node->callers->next_caller && node->local.local))
1804 && !node->address_taken
1805 && !node->has_aliases_p ()
1806 && (!flag_lto || !node->externally_visible))
1808 if (dump_file)
1809 fprintf (dump_file, "Not splitting: not called directly "
1810 "or called once.\n");
1811 return 0;
1814 /* FIXME: We can actually split if splitting reduces call overhead. */
1815 if (!flag_inline_small_functions
1816 && !DECL_DECLARED_INLINE_P (current_function_decl))
1818 if (dump_file)
1819 fprintf (dump_file, "Not splitting: not autoinlining and function"
1820 " is not inline.\n");
1821 return 0;
1824 /* We enforce splitting after loop headers when profile info is not
1825 available. */
1826 if (profile_status_for_fn (cfun) != PROFILE_READ)
1827 mark_dfs_back_edges ();
1829 /* Initialize bitmap to track forbidden calls. */
1830 forbidden_dominators = BITMAP_ALLOC (NULL);
1831 calculate_dominance_info (CDI_DOMINATORS);
1833 /* Compute local info about basic blocks and determine function size/time. */
1834 bb_info_vec.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1835 best_split_point.split_bbs = NULL;
1836 basic_block return_bb = find_return_bb ();
1837 int tsan_exit_found = -1;
1838 FOR_EACH_BB_FN (bb, cfun)
1840 sreal time = 0;
1841 int size = 0;
1842 sreal freq = bb->count.to_sreal_scale
1843 (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count);
1845 if (dump_file && (dump_flags & TDF_DETAILS))
1846 fprintf (dump_file, "Basic block %i\n", bb->index);
1848 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1850 sreal this_time;
1851 int this_size;
1852 gimple *stmt = gsi_stmt (bsi);
1854 this_size = estimate_num_insns (stmt, &eni_size_weights);
1855 this_time = (sreal)estimate_num_insns (stmt, &eni_time_weights)
1856 * freq;
1857 size += this_size;
1858 time += this_time;
1859 check_forbidden_calls (stmt);
1861 if (dump_file && (dump_flags & TDF_DETAILS))
1863 fprintf (dump_file, " freq:%4.2f size:%3i time:%4.2f ",
1864 freq.to_double (), this_size, this_time.to_double ());
1865 print_gimple_stmt (dump_file, stmt, 0);
1868 if ((flag_sanitize & SANITIZE_THREAD)
1869 && gimple_call_internal_p (stmt, IFN_TSAN_FUNC_EXIT))
1871 /* We handle TSAN_FUNC_EXIT for splitting either in the
1872 return_bb, or in its immediate predecessors. */
1873 if ((bb != return_bb && !find_edge (bb, return_bb))
1874 || (tsan_exit_found != -1
1875 && tsan_exit_found != (bb != return_bb)))
1877 if (dump_file)
1878 fprintf (dump_file, "Not splitting: TSAN_FUNC_EXIT"
1879 " in unexpected basic block.\n");
1880 BITMAP_FREE (forbidden_dominators);
1881 bb_info_vec.release ();
1882 return 0;
1884 tsan_exit_found = bb != return_bb;
1887 overall_time += time;
1888 overall_size += size;
1889 bb_info_vec[bb->index].time = time;
1890 bb_info_vec[bb->index].size = size;
1892 find_split_points (return_bb, overall_time, overall_size);
1893 if (best_split_point.split_bbs)
1895 split_function (return_bb, &best_split_point, tsan_exit_found == 1);
1896 BITMAP_FREE (best_split_point.ssa_names_to_pass);
1897 BITMAP_FREE (best_split_point.split_bbs);
1898 todo = TODO_update_ssa | TODO_cleanup_cfg;
1900 BITMAP_FREE (forbidden_dominators);
1901 bb_info_vec.release ();
1902 return todo;
1905 namespace {
1907 const pass_data pass_data_split_functions =
1909 GIMPLE_PASS, /* type */
1910 "fnsplit", /* name */
1911 OPTGROUP_NONE, /* optinfo_flags */
1912 TV_IPA_FNSPLIT, /* tv_id */
1913 PROP_cfg, /* properties_required */
1914 0, /* properties_provided */
1915 0, /* properties_destroyed */
1916 0, /* todo_flags_start */
1917 0, /* todo_flags_finish */
1920 class pass_split_functions : public gimple_opt_pass
1922 public:
1923 pass_split_functions (gcc::context *ctxt)
1924 : gimple_opt_pass (pass_data_split_functions, ctxt)
1927 /* opt_pass methods: */
1928 virtual bool gate (function *);
1929 virtual unsigned int execute (function *)
1931 return execute_split_functions ();
1934 }; // class pass_split_functions
1936 bool
1937 pass_split_functions::gate (function *)
1939 /* When doing profile feedback, we want to execute the pass after profiling
1940 is read. So disable one in early optimization. */
1941 return (flag_partial_inlining
1942 && !profile_arc_flag && !flag_branch_probabilities);
1945 } // anon namespace
1947 gimple_opt_pass *
1948 make_pass_split_functions (gcc::context *ctxt)
1950 return new pass_split_functions (ctxt);
1953 /* Execute function splitting pass. */
1955 static unsigned int
1956 execute_feedback_split_functions (void)
1958 unsigned int retval = execute_split_functions ();
1959 if (retval)
1960 retval |= TODO_rebuild_cgraph_edges;
1961 return retval;
1964 namespace {
1966 const pass_data pass_data_feedback_split_functions =
1968 GIMPLE_PASS, /* type */
1969 "feedback_fnsplit", /* name */
1970 OPTGROUP_NONE, /* optinfo_flags */
1971 TV_IPA_FNSPLIT, /* tv_id */
1972 PROP_cfg, /* properties_required */
1973 0, /* properties_provided */
1974 0, /* properties_destroyed */
1975 0, /* todo_flags_start */
1976 0, /* todo_flags_finish */
1979 class pass_feedback_split_functions : public gimple_opt_pass
1981 public:
1982 pass_feedback_split_functions (gcc::context *ctxt)
1983 : gimple_opt_pass (pass_data_feedback_split_functions, ctxt)
1986 /* opt_pass methods: */
1987 virtual bool gate (function *);
1988 virtual unsigned int execute (function *)
1990 return execute_feedback_split_functions ();
1993 }; // class pass_feedback_split_functions
1995 bool
1996 pass_feedback_split_functions::gate (function *)
1998 /* We don't need to split when profiling at all, we are producing
1999 lousy code anyway. */
2000 return (flag_partial_inlining
2001 && flag_branch_probabilities);
2004 } // anon namespace
2006 gimple_opt_pass *
2007 make_pass_feedback_split_functions (gcc::context *ctxt)
2009 return new pass_feedback_split_functions (ctxt);