PR middle-end/66633
[official-gcc.git] / gcc / ipa-split.c
blob13d9a6447e5248a03bdb2b8ea0faeafbf94dd918
1 /* Function splitting pass
2 Copyright (C) 2010-2015 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 "alias.h"
81 #include "symtab.h"
82 #include "options.h"
83 #include "tree.h"
84 #include "fold-const.h"
85 #include "predict.h"
86 #include "tm.h"
87 #include "hard-reg-set.h"
88 #include "function.h"
89 #include "dominance.h"
90 #include "cfg.h"
91 #include "cfganal.h"
92 #include "basic-block.h"
93 #include "tree-ssa-alias.h"
94 #include "internal-fn.h"
95 #include "gimple-expr.h"
96 #include "gimple.h"
97 #include "stringpool.h"
98 #include "rtl.h"
99 #include "flags.h"
100 #include "insn-config.h"
101 #include "expmed.h"
102 #include "dojump.h"
103 #include "explow.h"
104 #include "calls.h"
105 #include "emit-rtl.h"
106 #include "varasm.h"
107 #include "stmt.h"
108 #include "expr.h"
109 #include "gimplify.h"
110 #include "gimple-iterator.h"
111 #include "gimplify-me.h"
112 #include "gimple-walk.h"
113 #include "target.h"
114 #include "cgraph.h"
115 #include "alloc-pool.h"
116 #include "symbol-summary.h"
117 #include "ipa-prop.h"
118 #include "gimple-ssa.h"
119 #include "tree-cfg.h"
120 #include "tree-phinodes.h"
121 #include "ssa-iterators.h"
122 #include "tree-ssanames.h"
123 #include "tree-into-ssa.h"
124 #include "tree-dfa.h"
125 #include "tree-pass.h"
126 #include "diagnostic.h"
127 #include "tree-dump.h"
128 #include "tree-inline.h"
129 #include "params.h"
130 #include "gimple-pretty-print.h"
131 #include "ipa-inline.h"
132 #include "cfgloop.h"
133 #include "tree-chkp.h"
135 /* Per basic block info. */
137 typedef struct
139 unsigned int size;
140 unsigned int time;
141 } split_bb_info;
143 static vec<split_bb_info> bb_info_vec;
145 /* Description of split point. */
147 struct split_point
149 /* Size of the partitions. */
150 unsigned int header_time, header_size, split_time, split_size;
152 /* SSA names that need to be passed into spit function. */
153 bitmap ssa_names_to_pass;
155 /* Basic block where we split (that will become entry point of new function. */
156 basic_block entry_bb;
158 /* Basic blocks we are splitting away. */
159 bitmap split_bbs;
161 /* True when return value is computed on split part and thus it needs
162 to be returned. */
163 bool split_part_set_retval;
166 /* Best split point found. */
168 struct split_point best_split_point;
170 /* Set of basic blocks that are not allowed to dominate a split point. */
172 static bitmap forbidden_dominators;
174 static tree find_retval (basic_block return_bb);
175 static tree find_retbnd (basic_block return_bb);
177 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
178 variable, check it if it is present in bitmap passed via DATA. */
180 static bool
181 test_nonssa_use (gimple, tree t, tree, void *data)
183 t = get_base_address (t);
185 if (!t || is_gimple_reg (t))
186 return false;
188 if (TREE_CODE (t) == PARM_DECL
189 || (TREE_CODE (t) == VAR_DECL
190 && auto_var_in_fn_p (t, current_function_decl))
191 || TREE_CODE (t) == RESULT_DECL
192 /* Normal labels are part of CFG and will be handled gratefuly.
193 Forced labels however can be used directly by statements and
194 need to stay in one partition along with their uses. */
195 || (TREE_CODE (t) == LABEL_DECL
196 && FORCED_LABEL (t)))
197 return bitmap_bit_p ((bitmap)data, DECL_UID (t));
199 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
200 to pretend that the value pointed to is actual result decl. */
201 if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
202 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
203 && SSA_NAME_VAR (TREE_OPERAND (t, 0))
204 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
205 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
206 return
207 bitmap_bit_p ((bitmap)data,
208 DECL_UID (DECL_RESULT (current_function_decl)));
210 return false;
213 /* Dump split point CURRENT. */
215 static void
216 dump_split_point (FILE * file, struct split_point *current)
218 fprintf (file,
219 "Split point at BB %i\n"
220 " header time: %i header size: %i\n"
221 " split time: %i split size: %i\n bbs: ",
222 current->entry_bb->index, current->header_time,
223 current->header_size, current->split_time, current->split_size);
224 dump_bitmap (file, current->split_bbs);
225 fprintf (file, " SSA names to pass: ");
226 dump_bitmap (file, current->ssa_names_to_pass);
229 /* Look for all BBs in header that might lead to the split part and verify
230 that they are not defining any non-SSA var used by the split part.
231 Parameters are the same as for consider_split. */
233 static bool
234 verify_non_ssa_vars (struct split_point *current, bitmap non_ssa_vars,
235 basic_block return_bb)
237 bitmap seen = BITMAP_ALLOC (NULL);
238 vec<basic_block> worklist = vNULL;
239 edge e;
240 edge_iterator ei;
241 bool ok = true;
242 basic_block bb;
244 FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
245 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
246 && !bitmap_bit_p (current->split_bbs, e->src->index))
248 worklist.safe_push (e->src);
249 bitmap_set_bit (seen, e->src->index);
252 while (!worklist.is_empty ())
254 bb = worklist.pop ();
255 FOR_EACH_EDGE (e, ei, bb->preds)
256 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
257 && bitmap_set_bit (seen, e->src->index))
259 gcc_checking_assert (!bitmap_bit_p (current->split_bbs,
260 e->src->index));
261 worklist.safe_push (e->src);
263 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
264 gsi_next (&bsi))
266 gimple stmt = gsi_stmt (bsi);
267 if (is_gimple_debug (stmt))
268 continue;
269 if (walk_stmt_load_store_addr_ops
270 (stmt, non_ssa_vars, test_nonssa_use, test_nonssa_use,
271 test_nonssa_use))
273 ok = false;
274 goto done;
276 if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
277 if (test_nonssa_use (stmt, gimple_label_label (label_stmt),
278 NULL_TREE, non_ssa_vars))
280 ok = false;
281 goto done;
284 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
285 gsi_next (&bsi))
287 if (walk_stmt_load_store_addr_ops
288 (gsi_stmt (bsi), non_ssa_vars, test_nonssa_use, test_nonssa_use,
289 test_nonssa_use))
291 ok = false;
292 goto done;
295 FOR_EACH_EDGE (e, ei, bb->succs)
297 if (e->dest != return_bb)
298 continue;
299 for (gphi_iterator bsi = gsi_start_phis (return_bb);
300 !gsi_end_p (bsi);
301 gsi_next (&bsi))
303 gphi *stmt = bsi.phi ();
304 tree op = gimple_phi_arg_def (stmt, e->dest_idx);
306 if (virtual_operand_p (gimple_phi_result (stmt)))
307 continue;
308 if (TREE_CODE (op) != SSA_NAME
309 && test_nonssa_use (stmt, op, op, non_ssa_vars))
311 ok = false;
312 goto done;
318 /* Verify that the rest of function does not define any label
319 used by the split part. */
320 FOR_EACH_BB_FN (bb, cfun)
321 if (!bitmap_bit_p (current->split_bbs, bb->index)
322 && !bitmap_bit_p (seen, bb->index))
324 gimple_stmt_iterator bsi;
325 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
326 if (glabel *label_stmt = dyn_cast <glabel *> (gsi_stmt (bsi)))
328 if (test_nonssa_use (label_stmt,
329 gimple_label_label (label_stmt),
330 NULL_TREE, non_ssa_vars))
332 ok = false;
333 goto done;
336 else
337 break;
340 done:
341 BITMAP_FREE (seen);
342 worklist.release ();
343 return ok;
346 /* If STMT is a call, check the callee against a list of forbidden
347 predicate functions. If a match is found, look for uses of the
348 call result in condition statements that compare against zero.
349 For each such use, find the block targeted by the condition
350 statement for the nonzero result, and set the bit for this block
351 in the forbidden dominators bitmap. The purpose of this is to avoid
352 selecting a split point where we are likely to lose the chance
353 to optimize away an unused function call. */
355 static void
356 check_forbidden_calls (gimple stmt)
358 imm_use_iterator use_iter;
359 use_operand_p use_p;
360 tree lhs;
362 /* At the moment, __builtin_constant_p is the only forbidden
363 predicate function call (see PR49642). */
364 if (!gimple_call_builtin_p (stmt, BUILT_IN_CONSTANT_P))
365 return;
367 lhs = gimple_call_lhs (stmt);
369 if (!lhs || TREE_CODE (lhs) != SSA_NAME)
370 return;
372 FOR_EACH_IMM_USE_FAST (use_p, use_iter, lhs)
374 tree op1;
375 basic_block use_bb, forbidden_bb;
376 enum tree_code code;
377 edge true_edge, false_edge;
378 gcond *use_stmt;
380 use_stmt = dyn_cast <gcond *> (USE_STMT (use_p));
381 if (!use_stmt)
382 continue;
384 /* Assuming canonical form for GIMPLE_COND here, with constant
385 in second position. */
386 op1 = gimple_cond_rhs (use_stmt);
387 code = gimple_cond_code (use_stmt);
388 use_bb = gimple_bb (use_stmt);
390 extract_true_false_edges_from_block (use_bb, &true_edge, &false_edge);
392 /* We're only interested in comparisons that distinguish
393 unambiguously from zero. */
394 if (!integer_zerop (op1) || code == LE_EXPR || code == GE_EXPR)
395 continue;
397 if (code == EQ_EXPR)
398 forbidden_bb = false_edge->dest;
399 else
400 forbidden_bb = true_edge->dest;
402 bitmap_set_bit (forbidden_dominators, forbidden_bb->index);
406 /* If BB is dominated by any block in the forbidden dominators set,
407 return TRUE; else FALSE. */
409 static bool
410 dominated_by_forbidden (basic_block bb)
412 unsigned dom_bb;
413 bitmap_iterator bi;
415 EXECUTE_IF_SET_IN_BITMAP (forbidden_dominators, 1, dom_bb, bi)
417 if (dominated_by_p (CDI_DOMINATORS, bb,
418 BASIC_BLOCK_FOR_FN (cfun, dom_bb)))
419 return true;
422 return false;
425 /* For give split point CURRENT and return block RETURN_BB return 1
426 if ssa name VAL is set by split part and 0 otherwise. */
427 static bool
428 split_part_set_ssa_name_p (tree val, struct split_point *current,
429 basic_block return_bb)
431 if (TREE_CODE (val) != SSA_NAME)
432 return false;
434 return (!SSA_NAME_IS_DEFAULT_DEF (val)
435 && (bitmap_bit_p (current->split_bbs,
436 gimple_bb (SSA_NAME_DEF_STMT (val))->index)
437 || gimple_bb (SSA_NAME_DEF_STMT (val)) == return_bb));
440 /* We found an split_point CURRENT. NON_SSA_VARS is bitmap of all non ssa
441 variables used and RETURN_BB is return basic block.
442 See if we can split function here. */
444 static void
445 consider_split (struct split_point *current, bitmap non_ssa_vars,
446 basic_block return_bb)
448 tree parm;
449 unsigned int num_args = 0;
450 unsigned int call_overhead;
451 edge e;
452 edge_iterator ei;
453 gphi_iterator bsi;
454 unsigned int i;
455 int incoming_freq = 0;
456 tree retval;
457 tree retbnd;
458 bool back_edge = false;
460 if (dump_file && (dump_flags & TDF_DETAILS))
461 dump_split_point (dump_file, current);
463 FOR_EACH_EDGE (e, ei, current->entry_bb->preds)
465 if (e->flags & EDGE_DFS_BACK)
466 back_edge = true;
467 if (!bitmap_bit_p (current->split_bbs, e->src->index))
468 incoming_freq += EDGE_FREQUENCY (e);
471 /* Do not split when we would end up calling function anyway. */
472 if (incoming_freq
473 >= (ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency
474 * PARAM_VALUE (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY) / 100))
476 /* When profile is guessed, we can not expect it to give us
477 realistic estimate on likelyness of function taking the
478 complex path. As a special case, when tail of the function is
479 a loop, enable splitting since inlining code skipping the loop
480 is likely noticeable win. */
481 if (back_edge
482 && profile_status_for_fn (cfun) != PROFILE_READ
483 && incoming_freq < ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency)
485 if (dump_file && (dump_flags & TDF_DETAILS))
486 fprintf (dump_file,
487 " Split before loop, accepting despite low frequencies %i %i.\n",
488 incoming_freq,
489 ENTRY_BLOCK_PTR_FOR_FN (cfun)->frequency);
491 else
493 if (dump_file && (dump_flags & TDF_DETAILS))
494 fprintf (dump_file,
495 " Refused: incoming frequency is too large.\n");
496 return;
500 if (!current->header_size)
502 if (dump_file && (dump_flags & TDF_DETAILS))
503 fprintf (dump_file, " Refused: header empty\n");
504 return;
507 /* Verify that PHI args on entry are either virtual or all their operands
508 incoming from header are the same. */
509 for (bsi = gsi_start_phis (current->entry_bb); !gsi_end_p (bsi); gsi_next (&bsi))
511 gphi *stmt = bsi.phi ();
512 tree val = NULL;
514 if (virtual_operand_p (gimple_phi_result (stmt)))
515 continue;
516 for (i = 0; i < gimple_phi_num_args (stmt); i++)
518 edge e = gimple_phi_arg_edge (stmt, i);
519 if (!bitmap_bit_p (current->split_bbs, e->src->index))
521 tree edge_val = gimple_phi_arg_def (stmt, i);
522 if (val && edge_val != val)
524 if (dump_file && (dump_flags & TDF_DETAILS))
525 fprintf (dump_file,
526 " Refused: entry BB has PHI with multiple variants\n");
527 return;
529 val = edge_val;
535 /* See what argument we will pass to the split function and compute
536 call overhead. */
537 call_overhead = eni_size_weights.call_cost;
538 for (parm = DECL_ARGUMENTS (current_function_decl); parm;
539 parm = DECL_CHAIN (parm))
541 if (!is_gimple_reg (parm))
543 if (bitmap_bit_p (non_ssa_vars, DECL_UID (parm)))
545 if (dump_file && (dump_flags & TDF_DETAILS))
546 fprintf (dump_file,
547 " Refused: need to pass non-ssa param values\n");
548 return;
551 else
553 tree ddef = ssa_default_def (cfun, parm);
554 if (ddef
555 && bitmap_bit_p (current->ssa_names_to_pass,
556 SSA_NAME_VERSION (ddef)))
558 if (!VOID_TYPE_P (TREE_TYPE (parm)))
559 call_overhead += estimate_move_cost (TREE_TYPE (parm), false);
560 num_args++;
564 if (!VOID_TYPE_P (TREE_TYPE (current_function_decl)))
565 call_overhead += estimate_move_cost (TREE_TYPE (current_function_decl),
566 false);
568 if (current->split_size <= call_overhead)
570 if (dump_file && (dump_flags & TDF_DETAILS))
571 fprintf (dump_file,
572 " Refused: split size is smaller than call overhead\n");
573 return;
575 if (current->header_size + call_overhead
576 >= (unsigned int)(DECL_DECLARED_INLINE_P (current_function_decl)
577 ? MAX_INLINE_INSNS_SINGLE
578 : MAX_INLINE_INSNS_AUTO))
580 if (dump_file && (dump_flags & TDF_DETAILS))
581 fprintf (dump_file,
582 " Refused: header size is too large for inline candidate\n");
583 return;
586 /* Splitting functions brings the target out of comdat group; this will
587 lead to code duplication if the function is reused by other unit.
588 Limit this duplication. This is consistent with limit in tree-sra.c
589 FIXME: with LTO we ought to be able to do better! */
590 if (DECL_ONE_ONLY (current_function_decl)
591 && current->split_size >= (unsigned int) MAX_INLINE_INSNS_AUTO)
593 if (dump_file && (dump_flags & TDF_DETAILS))
594 fprintf (dump_file,
595 " Refused: function is COMDAT and tail is too large\n");
596 return;
598 /* For comdat functions also reject very small tails; those will likely get
599 inlined back and we do not want to risk the duplication overhead.
600 FIXME: with LTO we ought to be able to do better! */
601 if (DECL_ONE_ONLY (current_function_decl)
602 && current->split_size
603 <= (unsigned int) PARAM_VALUE (PARAM_EARLY_INLINING_INSNS) / 2)
605 if (dump_file && (dump_flags & TDF_DETAILS))
606 fprintf (dump_file,
607 " Refused: function is COMDAT and tail is too small\n");
608 return;
611 /* FIXME: we currently can pass only SSA function parameters to the split
612 arguments. Once parm_adjustment infrastructure is supported by cloning,
613 we can pass more than that. */
614 if (num_args != bitmap_count_bits (current->ssa_names_to_pass))
617 if (dump_file && (dump_flags & TDF_DETAILS))
618 fprintf (dump_file,
619 " Refused: need to pass non-param values\n");
620 return;
623 /* When there are non-ssa vars used in the split region, see if they
624 are used in the header region. If so, reject the split.
625 FIXME: we can use nested function support to access both. */
626 if (!bitmap_empty_p (non_ssa_vars)
627 && !verify_non_ssa_vars (current, non_ssa_vars, return_bb))
629 if (dump_file && (dump_flags & TDF_DETAILS))
630 fprintf (dump_file,
631 " Refused: split part has non-ssa uses\n");
632 return;
635 /* If the split point is dominated by a forbidden block, reject
636 the split. */
637 if (!bitmap_empty_p (forbidden_dominators)
638 && dominated_by_forbidden (current->entry_bb))
640 if (dump_file && (dump_flags & TDF_DETAILS))
641 fprintf (dump_file,
642 " Refused: split point dominated by forbidden block\n");
643 return;
646 /* See if retval used by return bb is computed by header or split part.
647 When it is computed by split part, we need to produce return statement
648 in the split part and add code to header to pass it around.
650 This is bit tricky to test:
651 1) When there is no return_bb or no return value, we always pass
652 value around.
653 2) Invariants are always computed by caller.
654 3) For SSA we need to look if defining statement is in header or split part
655 4) For non-SSA we need to look where the var is computed. */
656 retval = find_retval (return_bb);
657 if (!retval)
658 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 (TREE_CODE (retval) == VAR_DECL
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 frequency 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.entry_bb->frequency > current->entry_bb->frequency
733 || (best_split_point.entry_bb->frequency == current->entry_bb->frequency
734 && best_split_point.split_size < current->split_size))
737 if (dump_file && (dump_flags & TDF_DETAILS))
738 fprintf (dump_file, " New best split point!\n");
739 if (best_split_point.ssa_names_to_pass)
741 BITMAP_FREE (best_split_point.ssa_names_to_pass);
742 BITMAP_FREE (best_split_point.split_bbs);
744 best_split_point = *current;
745 best_split_point.ssa_names_to_pass = BITMAP_ALLOC (NULL);
746 bitmap_copy (best_split_point.ssa_names_to_pass,
747 current->ssa_names_to_pass);
748 best_split_point.split_bbs = BITMAP_ALLOC (NULL);
749 bitmap_copy (best_split_point.split_bbs, current->split_bbs);
753 /* Return basic block containing RETURN statement. We allow basic blocks
754 of the form:
755 <retval> = tmp_var;
756 return <retval>
757 but return_bb can not be more complex than this (except for
758 -fsanitize=thread we allow TSAN_FUNC_EXIT () internal call in there).
759 If nothing is found, return the exit block.
761 When there are multiple RETURN statement, chose one with return value,
762 since that one is more likely shared by multiple code paths.
764 Return BB is special, because for function splitting it is the only
765 basic block that is duplicated in between header and split part of the
766 function.
768 TODO: We might support multiple return blocks. */
770 static basic_block
771 find_return_bb (void)
773 edge e;
774 basic_block return_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
775 gimple_stmt_iterator bsi;
776 bool found_return = false;
777 tree retval = NULL_TREE;
779 if (!single_pred_p (EXIT_BLOCK_PTR_FOR_FN (cfun)))
780 return return_bb;
782 e = single_pred_edge (EXIT_BLOCK_PTR_FOR_FN (cfun));
783 for (bsi = gsi_last_bb (e->src); !gsi_end_p (bsi); gsi_prev (&bsi))
785 gimple stmt = gsi_stmt (bsi);
786 if (gimple_code (stmt) == GIMPLE_LABEL
787 || is_gimple_debug (stmt)
788 || gimple_clobber_p (stmt))
790 else if (gimple_code (stmt) == GIMPLE_ASSIGN
791 && found_return
792 && gimple_assign_single_p (stmt)
793 && (auto_var_in_fn_p (gimple_assign_rhs1 (stmt),
794 current_function_decl)
795 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
796 && retval == gimple_assign_lhs (stmt))
798 else if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
800 found_return = true;
801 retval = gimple_return_retval (return_stmt);
803 /* For -fsanitize=thread, allow also TSAN_FUNC_EXIT () in the return
804 bb. */
805 else if ((flag_sanitize & SANITIZE_THREAD)
806 && is_gimple_call (stmt)
807 && gimple_call_internal_p (stmt)
808 && gimple_call_internal_fn (stmt) == IFN_TSAN_FUNC_EXIT)
810 else
811 break;
813 if (gsi_end_p (bsi) && found_return)
814 return_bb = e->src;
816 return return_bb;
819 /* Given return basic block RETURN_BB, see where return value is really
820 stored. */
821 static tree
822 find_retval (basic_block return_bb)
824 gimple_stmt_iterator bsi;
825 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi); gsi_next (&bsi))
826 if (greturn *return_stmt = dyn_cast <greturn *> (gsi_stmt (bsi)))
827 return gimple_return_retval (return_stmt);
828 else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN
829 && !gimple_clobber_p (gsi_stmt (bsi)))
830 return gimple_assign_rhs1 (gsi_stmt (bsi));
831 return NULL;
834 /* Given return basic block RETURN_BB, see where return bounds are really
835 stored. */
836 static tree
837 find_retbnd (basic_block return_bb)
839 gimple_stmt_iterator bsi;
840 for (bsi = gsi_last_bb (return_bb); !gsi_end_p (bsi); gsi_prev (&bsi))
841 if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
842 return gimple_return_retbnd (gsi_stmt (bsi));
843 return NULL;
846 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
847 variable, mark it as used in bitmap passed via DATA.
848 Return true when access to T prevents splitting the function. */
850 static bool
851 mark_nonssa_use (gimple, tree t, tree, void *data)
853 t = get_base_address (t);
855 if (!t || is_gimple_reg (t))
856 return false;
858 /* At present we can't pass non-SSA arguments to split function.
859 FIXME: this can be relaxed by passing references to arguments. */
860 if (TREE_CODE (t) == PARM_DECL)
862 if (dump_file && (dump_flags & TDF_DETAILS))
863 fprintf (dump_file,
864 "Cannot split: use of non-ssa function parameter.\n");
865 return true;
868 if ((TREE_CODE (t) == VAR_DECL
869 && auto_var_in_fn_p (t, current_function_decl))
870 || TREE_CODE (t) == RESULT_DECL
871 || (TREE_CODE (t) == LABEL_DECL
872 && FORCED_LABEL (t)))
873 bitmap_set_bit ((bitmap)data, DECL_UID (t));
875 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
876 to pretend that the value pointed to is actual result decl. */
877 if ((TREE_CODE (t) == MEM_REF || INDIRECT_REF_P (t))
878 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
879 && SSA_NAME_VAR (TREE_OPERAND (t, 0))
880 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t, 0))) == RESULT_DECL
881 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
882 return
883 bitmap_bit_p ((bitmap)data,
884 DECL_UID (DECL_RESULT (current_function_decl)));
886 return false;
889 /* Compute local properties of basic block BB we collect when looking for
890 split points. We look for ssa defs and store them in SET_SSA_NAMES,
891 for ssa uses and store them in USED_SSA_NAMES and for any non-SSA automatic
892 vars stored in NON_SSA_VARS.
894 When BB has edge to RETURN_BB, collect uses in RETURN_BB too.
896 Return false when BB contains something that prevents it from being put into
897 split function. */
899 static bool
900 visit_bb (basic_block bb, basic_block return_bb,
901 bitmap set_ssa_names, bitmap used_ssa_names,
902 bitmap non_ssa_vars)
904 edge e;
905 edge_iterator ei;
906 bool can_split = true;
908 for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
909 gsi_next (&bsi))
911 gimple stmt = gsi_stmt (bsi);
912 tree op;
913 ssa_op_iter iter;
914 tree decl;
916 if (is_gimple_debug (stmt))
917 continue;
919 if (gimple_clobber_p (stmt))
920 continue;
922 /* FIXME: We can split regions containing EH. We can not however
923 split RESX, EH_DISPATCH and EH_POINTER referring to same region
924 into different partitions. This would require tracking of
925 EH regions and checking in consider_split_point if they
926 are not used elsewhere. */
927 if (gimple_code (stmt) == GIMPLE_RESX)
929 if (dump_file && (dump_flags & TDF_DETAILS))
930 fprintf (dump_file, "Cannot split: resx.\n");
931 can_split = false;
933 if (gimple_code (stmt) == GIMPLE_EH_DISPATCH)
935 if (dump_file && (dump_flags & TDF_DETAILS))
936 fprintf (dump_file, "Cannot split: eh dispatch.\n");
937 can_split = false;
940 /* Check builtins that prevent splitting. */
941 if (gimple_code (stmt) == GIMPLE_CALL
942 && (decl = gimple_call_fndecl (stmt)) != NULL_TREE
943 && DECL_BUILT_IN (decl)
944 && DECL_BUILT_IN_CLASS (decl) == BUILT_IN_NORMAL)
945 switch (DECL_FUNCTION_CODE (decl))
947 /* FIXME: once we will allow passing non-parm values to split part,
948 we need to be sure to handle correct builtin_stack_save and
949 builtin_stack_restore. At the moment we are safe; there is no
950 way to store builtin_stack_save result in non-SSA variable
951 since all calls to those are compiler generated. */
952 case BUILT_IN_APPLY:
953 case BUILT_IN_APPLY_ARGS:
954 case BUILT_IN_VA_START:
955 if (dump_file && (dump_flags & TDF_DETAILS))
956 fprintf (dump_file,
957 "Cannot split: builtin_apply and va_start.\n");
958 can_split = false;
959 break;
960 case BUILT_IN_EH_POINTER:
961 if (dump_file && (dump_flags & TDF_DETAILS))
962 fprintf (dump_file, "Cannot split: builtin_eh_pointer.\n");
963 can_split = false;
964 break;
965 default:
966 break;
969 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
970 bitmap_set_bit (set_ssa_names, SSA_NAME_VERSION (op));
971 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
972 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
973 can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
974 mark_nonssa_use,
975 mark_nonssa_use,
976 mark_nonssa_use);
978 for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
979 gsi_next (&bsi))
981 gphi *stmt = bsi.phi ();
982 unsigned int i;
984 if (virtual_operand_p (gimple_phi_result (stmt)))
985 continue;
986 bitmap_set_bit (set_ssa_names,
987 SSA_NAME_VERSION (gimple_phi_result (stmt)));
988 for (i = 0; i < gimple_phi_num_args (stmt); i++)
990 tree op = gimple_phi_arg_def (stmt, i);
991 if (TREE_CODE (op) == SSA_NAME)
992 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
994 can_split &= !walk_stmt_load_store_addr_ops (stmt, non_ssa_vars,
995 mark_nonssa_use,
996 mark_nonssa_use,
997 mark_nonssa_use);
999 /* Record also uses coming from PHI operand in return BB. */
1000 FOR_EACH_EDGE (e, ei, bb->succs)
1001 if (e->dest == return_bb)
1003 for (gphi_iterator bsi = gsi_start_phis (return_bb);
1004 !gsi_end_p (bsi);
1005 gsi_next (&bsi))
1007 gphi *stmt = bsi.phi ();
1008 tree op = gimple_phi_arg_def (stmt, e->dest_idx);
1010 if (virtual_operand_p (gimple_phi_result (stmt)))
1011 continue;
1012 if (TREE_CODE (op) == SSA_NAME)
1013 bitmap_set_bit (used_ssa_names, SSA_NAME_VERSION (op));
1014 else
1015 can_split &= !mark_nonssa_use (stmt, op, op, non_ssa_vars);
1018 return can_split;
1021 /* Stack entry for recursive DFS walk in find_split_point. */
1023 typedef struct
1025 /* Basic block we are examining. */
1026 basic_block bb;
1028 /* SSA names set and used by the BB and all BBs reachable
1029 from it via DFS walk. */
1030 bitmap set_ssa_names, used_ssa_names;
1031 bitmap non_ssa_vars;
1033 /* All BBS visited from this BB via DFS walk. */
1034 bitmap bbs_visited;
1036 /* Last examined edge in DFS walk. Since we walk unoriented graph,
1037 the value is up to sum of incoming and outgoing edges of BB. */
1038 unsigned int edge_num;
1040 /* Stack entry index of earliest BB reachable from current BB
1041 or any BB visited later in DFS walk. */
1042 int earliest;
1044 /* Overall time and size of all BBs reached from this BB in DFS walk. */
1045 int overall_time, overall_size;
1047 /* When false we can not split on this BB. */
1048 bool can_split;
1049 } stack_entry;
1052 /* Find all articulations and call consider_split on them.
1053 OVERALL_TIME and OVERALL_SIZE is time and size of the function.
1055 We perform basic algorithm for finding an articulation in a graph
1056 created from CFG by considering it to be an unoriented graph.
1058 The articulation is discovered via DFS walk. We collect earliest
1059 basic block on stack that is reachable via backward edge. Articulation
1060 is any basic block such that there is no backward edge bypassing it.
1061 To reduce stack usage we maintain heap allocated stack in STACK vector.
1062 AUX pointer of BB is set to index it appears in the stack or -1 once
1063 it is visited and popped off the stack.
1065 The algorithm finds articulation after visiting the whole component
1066 reachable by it. This makes it convenient to collect information about
1067 the component used by consider_split. */
1069 static void
1070 find_split_points (basic_block return_bb, int overall_time, int overall_size)
1072 stack_entry first;
1073 vec<stack_entry> stack = vNULL;
1074 basic_block bb;
1075 struct split_point current;
1077 current.header_time = overall_time;
1078 current.header_size = overall_size;
1079 current.split_time = 0;
1080 current.split_size = 0;
1081 current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
1083 first.bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
1084 first.edge_num = 0;
1085 first.overall_time = 0;
1086 first.overall_size = 0;
1087 first.earliest = INT_MAX;
1088 first.set_ssa_names = 0;
1089 first.used_ssa_names = 0;
1090 first.non_ssa_vars = 0;
1091 first.bbs_visited = 0;
1092 first.can_split = false;
1093 stack.safe_push (first);
1094 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = (void *)(intptr_t)-1;
1096 while (!stack.is_empty ())
1098 stack_entry *entry = &stack.last ();
1100 /* We are walking an acyclic graph, so edge_num counts
1101 succ and pred edges together. However when considering
1102 articulation, we want to have processed everything reachable
1103 from articulation but nothing that reaches into it. */
1104 if (entry->edge_num == EDGE_COUNT (entry->bb->succs)
1105 && entry->bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1107 int pos = stack.length ();
1108 entry->can_split &= visit_bb (entry->bb, return_bb,
1109 entry->set_ssa_names,
1110 entry->used_ssa_names,
1111 entry->non_ssa_vars);
1112 if (pos <= entry->earliest && !entry->can_split
1113 && dump_file && (dump_flags & TDF_DETAILS))
1114 fprintf (dump_file,
1115 "found articulation at bb %i but can not split\n",
1116 entry->bb->index);
1117 if (pos <= entry->earliest && entry->can_split)
1119 if (dump_file && (dump_flags & TDF_DETAILS))
1120 fprintf (dump_file, "found articulation at bb %i\n",
1121 entry->bb->index);
1122 current.entry_bb = entry->bb;
1123 current.ssa_names_to_pass = BITMAP_ALLOC (NULL);
1124 bitmap_and_compl (current.ssa_names_to_pass,
1125 entry->used_ssa_names, entry->set_ssa_names);
1126 current.header_time = overall_time - entry->overall_time;
1127 current.header_size = overall_size - entry->overall_size;
1128 current.split_time = entry->overall_time;
1129 current.split_size = entry->overall_size;
1130 current.split_bbs = entry->bbs_visited;
1131 consider_split (&current, entry->non_ssa_vars, return_bb);
1132 BITMAP_FREE (current.ssa_names_to_pass);
1135 /* Do actual DFS walk. */
1136 if (entry->edge_num
1137 < (EDGE_COUNT (entry->bb->succs)
1138 + EDGE_COUNT (entry->bb->preds)))
1140 edge e;
1141 basic_block dest;
1142 if (entry->edge_num < EDGE_COUNT (entry->bb->succs))
1144 e = EDGE_SUCC (entry->bb, entry->edge_num);
1145 dest = e->dest;
1147 else
1149 e = EDGE_PRED (entry->bb, entry->edge_num
1150 - EDGE_COUNT (entry->bb->succs));
1151 dest = e->src;
1154 entry->edge_num++;
1156 /* New BB to visit, push it to the stack. */
1157 if (dest != return_bb && dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1158 && !dest->aux)
1160 stack_entry new_entry;
1162 new_entry.bb = dest;
1163 new_entry.edge_num = 0;
1164 new_entry.overall_time
1165 = bb_info_vec[dest->index].time;
1166 new_entry.overall_size
1167 = bb_info_vec[dest->index].size;
1168 new_entry.earliest = INT_MAX;
1169 new_entry.set_ssa_names = BITMAP_ALLOC (NULL);
1170 new_entry.used_ssa_names = BITMAP_ALLOC (NULL);
1171 new_entry.bbs_visited = BITMAP_ALLOC (NULL);
1172 new_entry.non_ssa_vars = BITMAP_ALLOC (NULL);
1173 new_entry.can_split = true;
1174 bitmap_set_bit (new_entry.bbs_visited, dest->index);
1175 stack.safe_push (new_entry);
1176 dest->aux = (void *)(intptr_t)stack.length ();
1178 /* Back edge found, record the earliest point. */
1179 else if ((intptr_t)dest->aux > 0
1180 && (intptr_t)dest->aux < entry->earliest)
1181 entry->earliest = (intptr_t)dest->aux;
1183 /* We are done with examining the edges. Pop off the value from stack
1184 and merge stuff we accumulate during the walk. */
1185 else if (entry->bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1187 stack_entry *prev = &stack[stack.length () - 2];
1189 entry->bb->aux = (void *)(intptr_t)-1;
1190 prev->can_split &= entry->can_split;
1191 if (prev->set_ssa_names)
1193 bitmap_ior_into (prev->set_ssa_names, entry->set_ssa_names);
1194 bitmap_ior_into (prev->used_ssa_names, entry->used_ssa_names);
1195 bitmap_ior_into (prev->bbs_visited, entry->bbs_visited);
1196 bitmap_ior_into (prev->non_ssa_vars, entry->non_ssa_vars);
1198 if (prev->earliest > entry->earliest)
1199 prev->earliest = entry->earliest;
1200 prev->overall_time += entry->overall_time;
1201 prev->overall_size += entry->overall_size;
1202 BITMAP_FREE (entry->set_ssa_names);
1203 BITMAP_FREE (entry->used_ssa_names);
1204 BITMAP_FREE (entry->bbs_visited);
1205 BITMAP_FREE (entry->non_ssa_vars);
1206 stack.pop ();
1208 else
1209 stack.pop ();
1211 ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux = NULL;
1212 FOR_EACH_BB_FN (bb, cfun)
1213 bb->aux = NULL;
1214 stack.release ();
1215 BITMAP_FREE (current.ssa_names_to_pass);
1218 /* Split function at SPLIT_POINT. */
1220 static void
1221 split_function (basic_block return_bb, struct split_point *split_point,
1222 bool add_tsan_func_exit)
1224 vec<tree> args_to_pass = vNULL;
1225 bitmap args_to_skip;
1226 tree parm;
1227 int num = 0;
1228 cgraph_node *node, *cur_node = cgraph_node::get (current_function_decl);
1229 basic_block call_bb;
1230 gcall *call, *tsan_func_exit_call = NULL;
1231 edge e;
1232 edge_iterator ei;
1233 tree retval = NULL, real_retval = NULL, retbnd = NULL;
1234 bool split_part_return_p = false;
1235 bool with_bounds = chkp_function_instrumented_p (current_function_decl);
1236 gimple last_stmt = NULL;
1237 unsigned int i;
1238 tree arg, ddef;
1239 vec<tree, va_gc> **debug_args = NULL;
1241 if (dump_file)
1243 fprintf (dump_file, "\n\nSplitting function at:\n");
1244 dump_split_point (dump_file, split_point);
1247 if (cur_node->local.can_change_signature)
1248 args_to_skip = BITMAP_ALLOC (NULL);
1249 else
1250 args_to_skip = NULL;
1252 /* Collect the parameters of new function and args_to_skip bitmap. */
1253 for (parm = DECL_ARGUMENTS (current_function_decl);
1254 parm; parm = DECL_CHAIN (parm), num++)
1255 if (args_to_skip
1256 && (!is_gimple_reg (parm)
1257 || (ddef = ssa_default_def (cfun, parm)) == NULL_TREE
1258 || !bitmap_bit_p (split_point->ssa_names_to_pass,
1259 SSA_NAME_VERSION (ddef))))
1260 bitmap_set_bit (args_to_skip, num);
1261 else
1263 /* This parm might not have been used up to now, but is going to be
1264 used, hence register it. */
1265 if (is_gimple_reg (parm))
1266 arg = get_or_create_ssa_default_def (cfun, parm);
1267 else
1268 arg = parm;
1270 if (!useless_type_conversion_p (DECL_ARG_TYPE (parm), TREE_TYPE (arg)))
1271 arg = fold_convert (DECL_ARG_TYPE (parm), arg);
1272 args_to_pass.safe_push (arg);
1275 /* See if the split function will return. */
1276 FOR_EACH_EDGE (e, ei, return_bb->preds)
1277 if (bitmap_bit_p (split_point->split_bbs, e->src->index))
1278 break;
1279 if (e)
1280 split_part_return_p = true;
1282 /* Add return block to what will become the split function.
1283 We do not return; no return block is needed. */
1284 if (!split_part_return_p)
1286 /* We have no return block, so nothing is needed. */
1287 else if (return_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1289 /* When we do not want to return value, we need to construct
1290 new return block with empty return statement.
1291 FIXME: Once we are able to change return type, we should change function
1292 to return void instead of just outputting function with undefined return
1293 value. For structures this affects quality of codegen. */
1294 else if (!split_point->split_part_set_retval
1295 && find_retval (return_bb))
1297 bool redirected = true;
1298 basic_block new_return_bb = create_basic_block (NULL, 0, return_bb);
1299 gimple_stmt_iterator gsi = gsi_start_bb (new_return_bb);
1300 gsi_insert_after (&gsi, gimple_build_return (NULL), GSI_NEW_STMT);
1301 while (redirected)
1303 redirected = false;
1304 FOR_EACH_EDGE (e, ei, return_bb->preds)
1305 if (bitmap_bit_p (split_point->split_bbs, e->src->index))
1307 new_return_bb->count += e->count;
1308 new_return_bb->frequency += EDGE_FREQUENCY (e);
1309 redirect_edge_and_branch (e, new_return_bb);
1310 redirected = true;
1311 break;
1314 e = make_edge (new_return_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
1315 e->probability = REG_BR_PROB_BASE;
1316 e->count = new_return_bb->count;
1317 add_bb_to_loop (new_return_bb, current_loops->tree_root);
1318 bitmap_set_bit (split_point->split_bbs, new_return_bb->index);
1320 /* When we pass around the value, use existing return block. */
1321 else
1322 bitmap_set_bit (split_point->split_bbs, return_bb->index);
1324 /* If RETURN_BB has virtual operand PHIs, they must be removed and the
1325 virtual operand marked for renaming as we change the CFG in a way that
1326 tree-inline is not able to compensate for.
1328 Note this can happen whether or not we have a return value. If we have
1329 a return value, then RETURN_BB may have PHIs for real operands too. */
1330 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1332 bool phi_p = false;
1333 for (gphi_iterator gsi = gsi_start_phis (return_bb);
1334 !gsi_end_p (gsi);)
1336 gphi *stmt = gsi.phi ();
1337 if (!virtual_operand_p (gimple_phi_result (stmt)))
1339 gsi_next (&gsi);
1340 continue;
1342 mark_virtual_phi_result_for_renaming (stmt);
1343 remove_phi_node (&gsi, true);
1344 phi_p = true;
1346 /* In reality we have to rename the reaching definition of the
1347 virtual operand at return_bb as we will eventually release it
1348 when we remove the code region we outlined.
1349 So we have to rename all immediate virtual uses of that region
1350 if we didn't see a PHI definition yet. */
1351 /* ??? In real reality we want to set the reaching vdef of the
1352 entry of the SESE region as the vuse of the call and the reaching
1353 vdef of the exit of the SESE region as the vdef of the call. */
1354 if (!phi_p)
1355 for (gimple_stmt_iterator gsi = gsi_start_bb (return_bb);
1356 !gsi_end_p (gsi);
1357 gsi_next (&gsi))
1359 gimple stmt = gsi_stmt (gsi);
1360 if (gimple_vuse (stmt))
1362 gimple_set_vuse (stmt, NULL_TREE);
1363 update_stmt (stmt);
1365 if (gimple_vdef (stmt))
1366 break;
1370 /* Now create the actual clone. */
1371 cgraph_edge::rebuild_edges ();
1372 node = cur_node->create_version_clone_with_body
1373 (vNULL, NULL, args_to_skip, !split_part_return_p, split_point->split_bbs,
1374 split_point->entry_bb, "part");
1376 node->split_part = true;
1378 /* Let's take a time profile for splitted function. */
1379 node->tp_first_run = cur_node->tp_first_run + 1;
1381 /* For usual cloning it is enough to clear builtin only when signature
1382 changes. For partial inlining we however can not expect the part
1383 of builtin implementation to have same semantic as the whole. */
1384 if (DECL_BUILT_IN (node->decl))
1386 DECL_BUILT_IN_CLASS (node->decl) = NOT_BUILT_IN;
1387 DECL_FUNCTION_CODE (node->decl) = (enum built_in_function) 0;
1390 /* If the original function is instrumented then it's
1391 part is also instrumented. */
1392 if (with_bounds)
1393 chkp_function_mark_instrumented (node->decl);
1395 /* If the original function is declared inline, there is no point in issuing
1396 a warning for the non-inlinable part. */
1397 DECL_NO_INLINE_WARNING_P (node->decl) = 1;
1398 cur_node->remove_callees ();
1399 cur_node->remove_all_references ();
1400 if (!split_part_return_p)
1401 TREE_THIS_VOLATILE (node->decl) = 1;
1402 if (dump_file)
1403 dump_function_to_file (node->decl, dump_file, dump_flags);
1405 /* Create the basic block we place call into. It is the entry basic block
1406 split after last label. */
1407 call_bb = split_point->entry_bb;
1408 for (gimple_stmt_iterator gsi = gsi_start_bb (call_bb); !gsi_end_p (gsi);)
1409 if (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL)
1411 last_stmt = gsi_stmt (gsi);
1412 gsi_next (&gsi);
1414 else
1415 break;
1416 e = split_block (split_point->entry_bb, last_stmt);
1417 remove_edge (e);
1419 /* Produce the call statement. */
1420 gimple_stmt_iterator gsi = gsi_last_bb (call_bb);
1421 FOR_EACH_VEC_ELT (args_to_pass, i, arg)
1422 if (!is_gimple_val (arg))
1424 arg = force_gimple_operand_gsi (&gsi, arg, true, NULL_TREE,
1425 false, GSI_CONTINUE_LINKING);
1426 args_to_pass[i] = arg;
1428 call = gimple_build_call_vec (node->decl, args_to_pass);
1429 gimple_call_set_with_bounds (call, with_bounds);
1430 gimple_set_block (call, DECL_INITIAL (current_function_decl));
1431 args_to_pass.release ();
1433 /* For optimized away parameters, add on the caller side
1434 before the call
1435 DEBUG D#X => parm_Y(D)
1436 stmts and associate D#X with parm in decl_debug_args_lookup
1437 vector to say for debug info that if parameter parm had been passed,
1438 it would have value parm_Y(D). */
1439 if (args_to_skip)
1440 for (parm = DECL_ARGUMENTS (current_function_decl), num = 0;
1441 parm; parm = DECL_CHAIN (parm), num++)
1442 if (bitmap_bit_p (args_to_skip, num)
1443 && is_gimple_reg (parm))
1445 tree ddecl;
1446 gimple def_temp;
1448 /* This needs to be done even without MAY_HAVE_DEBUG_STMTS,
1449 otherwise if it didn't exist before, we'd end up with
1450 different SSA_NAME_VERSIONs between -g and -g0. */
1451 arg = get_or_create_ssa_default_def (cfun, parm);
1452 if (!MAY_HAVE_DEBUG_STMTS)
1453 continue;
1455 if (debug_args == NULL)
1456 debug_args = decl_debug_args_insert (node->decl);
1457 ddecl = make_node (DEBUG_EXPR_DECL);
1458 DECL_ARTIFICIAL (ddecl) = 1;
1459 TREE_TYPE (ddecl) = TREE_TYPE (parm);
1460 DECL_MODE (ddecl) = DECL_MODE (parm);
1461 vec_safe_push (*debug_args, DECL_ORIGIN (parm));
1462 vec_safe_push (*debug_args, ddecl);
1463 def_temp = gimple_build_debug_bind (ddecl, unshare_expr (arg),
1464 call);
1465 gsi_insert_after (&gsi, def_temp, GSI_NEW_STMT);
1467 /* And on the callee side, add
1468 DEBUG D#Y s=> parm
1469 DEBUG var => D#Y
1470 stmts to the first bb where var is a VAR_DECL created for the
1471 optimized away parameter in DECL_INITIAL block. This hints
1472 in the debug info that var (whole DECL_ORIGIN is the parm PARM_DECL)
1473 is optimized away, but could be looked up at the call site
1474 as value of D#X there. */
1475 if (debug_args != NULL)
1477 unsigned int i;
1478 tree var, vexpr;
1479 gimple_stmt_iterator cgsi;
1480 gimple def_temp;
1482 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1483 var = BLOCK_VARS (DECL_INITIAL (node->decl));
1484 i = vec_safe_length (*debug_args);
1485 cgsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
1488 i -= 2;
1489 while (var != NULL_TREE
1490 && DECL_ABSTRACT_ORIGIN (var) != (**debug_args)[i])
1491 var = TREE_CHAIN (var);
1492 if (var == NULL_TREE)
1493 break;
1494 vexpr = make_node (DEBUG_EXPR_DECL);
1495 parm = (**debug_args)[i];
1496 DECL_ARTIFICIAL (vexpr) = 1;
1497 TREE_TYPE (vexpr) = TREE_TYPE (parm);
1498 DECL_MODE (vexpr) = DECL_MODE (parm);
1499 def_temp = gimple_build_debug_source_bind (vexpr, parm,
1500 NULL);
1501 gsi_insert_before (&cgsi, def_temp, GSI_SAME_STMT);
1502 def_temp = gimple_build_debug_bind (var, vexpr, NULL);
1503 gsi_insert_before (&cgsi, def_temp, GSI_SAME_STMT);
1505 while (i);
1506 pop_cfun ();
1509 /* We avoid address being taken on any variable used by split part,
1510 so return slot optimization is always possible. Moreover this is
1511 required to make DECL_BY_REFERENCE work. */
1512 if (aggregate_value_p (DECL_RESULT (current_function_decl),
1513 TREE_TYPE (current_function_decl))
1514 && (!is_gimple_reg_type (TREE_TYPE (DECL_RESULT (current_function_decl)))
1515 || DECL_BY_REFERENCE (DECL_RESULT (current_function_decl))))
1516 gimple_call_set_return_slot_opt (call, true);
1518 if (add_tsan_func_exit)
1519 tsan_func_exit_call = gimple_build_call_internal (IFN_TSAN_FUNC_EXIT, 0);
1521 /* Update return value. This is bit tricky. When we do not return,
1522 do nothing. When we return we might need to update return_bb
1523 or produce a new return statement. */
1524 if (!split_part_return_p)
1526 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1527 if (tsan_func_exit_call)
1528 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1530 else
1532 e = make_edge (call_bb, return_bb,
1533 return_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1534 ? 0 : EDGE_FALLTHRU);
1535 e->count = call_bb->count;
1536 e->probability = REG_BR_PROB_BASE;
1538 /* If there is return basic block, see what value we need to store
1539 return value into and put call just before it. */
1540 if (return_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1542 real_retval = retval = find_retval (return_bb);
1543 retbnd = find_retbnd (return_bb);
1545 if (real_retval && split_point->split_part_set_retval)
1547 gphi_iterator psi;
1549 /* See if we need new SSA_NAME for the result.
1550 When DECL_BY_REFERENCE is true, retval is actually pointer to
1551 return value and it is constant in whole function. */
1552 if (TREE_CODE (retval) == SSA_NAME
1553 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1555 retval = copy_ssa_name (retval, call);
1557 /* See if there is PHI defining return value. */
1558 for (psi = gsi_start_phis (return_bb);
1559 !gsi_end_p (psi); gsi_next (&psi))
1560 if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
1561 break;
1563 /* When there is PHI, just update its value. */
1564 if (TREE_CODE (retval) == SSA_NAME
1565 && !gsi_end_p (psi))
1566 add_phi_arg (psi.phi (), retval, e, UNKNOWN_LOCATION);
1567 /* Otherwise update the return BB itself.
1568 find_return_bb allows at most one assignment to return value,
1569 so update first statement. */
1570 else
1572 gimple_stmt_iterator bsi;
1573 for (bsi = gsi_start_bb (return_bb); !gsi_end_p (bsi);
1574 gsi_next (&bsi))
1575 if (greturn *return_stmt
1576 = dyn_cast <greturn *> (gsi_stmt (bsi)))
1578 gimple_return_set_retval (return_stmt, retval);
1579 break;
1581 else if (gimple_code (gsi_stmt (bsi)) == GIMPLE_ASSIGN
1582 && !gimple_clobber_p (gsi_stmt (bsi)))
1584 gimple_assign_set_rhs1 (gsi_stmt (bsi), retval);
1585 break;
1587 update_stmt (gsi_stmt (bsi));
1590 /* Replace retbnd with new one. */
1591 if (retbnd)
1593 gimple_stmt_iterator bsi;
1594 for (bsi = gsi_last_bb (return_bb); !gsi_end_p (bsi);
1595 gsi_prev (&bsi))
1596 if (gimple_code (gsi_stmt (bsi)) == GIMPLE_RETURN)
1598 retbnd = copy_ssa_name (retbnd, call);
1599 gimple_return_set_retbnd (gsi_stmt (bsi), retbnd);
1600 update_stmt (gsi_stmt (bsi));
1601 break;
1605 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1607 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1608 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1610 else
1612 tree restype;
1613 restype = TREE_TYPE (DECL_RESULT (current_function_decl));
1614 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1615 if (!useless_type_conversion_p (TREE_TYPE (retval), restype))
1617 gimple cpy;
1618 tree tem = create_tmp_reg (restype);
1619 tem = make_ssa_name (tem, call);
1620 cpy = gimple_build_assign (retval, NOP_EXPR, tem);
1621 gsi_insert_after (&gsi, cpy, GSI_NEW_STMT);
1622 retval = tem;
1624 /* Build bndret call to obtain returned bounds. */
1625 if (retbnd)
1626 chkp_insert_retbnd_call (retbnd, retval, &gsi);
1627 gimple_call_set_lhs (call, retval);
1628 update_stmt (call);
1631 else
1632 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1633 if (tsan_func_exit_call)
1634 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1636 /* We don't use return block (there is either no return in function or
1637 multiple of them). So create new basic block with return statement.
1639 else
1641 greturn *ret;
1642 if (split_point->split_part_set_retval
1643 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl))))
1645 retval = DECL_RESULT (current_function_decl);
1647 if (chkp_function_instrumented_p (current_function_decl)
1648 && BOUNDED_P (retval))
1649 retbnd = create_tmp_reg (pointer_bounds_type_node);
1651 /* We use temporary register to hold value when aggregate_value_p
1652 is false. Similarly for DECL_BY_REFERENCE we must avoid extra
1653 copy. */
1654 if (!aggregate_value_p (retval, TREE_TYPE (current_function_decl))
1655 && !DECL_BY_REFERENCE (retval))
1656 retval = create_tmp_reg (TREE_TYPE (retval));
1657 if (is_gimple_reg (retval))
1659 /* When returning by reference, there is only one SSA name
1660 assigned to RESULT_DECL (that is pointer to return value).
1661 Look it up or create new one if it is missing. */
1662 if (DECL_BY_REFERENCE (retval))
1663 retval = get_or_create_ssa_default_def (cfun, retval);
1664 /* Otherwise produce new SSA name for return value. */
1665 else
1666 retval = make_ssa_name (retval, call);
1668 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl)))
1669 gimple_call_set_lhs (call, build_simple_mem_ref (retval));
1670 else
1671 gimple_call_set_lhs (call, retval);
1673 gsi_insert_after (&gsi, call, GSI_NEW_STMT);
1674 /* Build bndret call to obtain returned bounds. */
1675 if (retbnd)
1676 chkp_insert_retbnd_call (retbnd, retval, &gsi);
1677 if (tsan_func_exit_call)
1678 gsi_insert_after (&gsi, tsan_func_exit_call, GSI_NEW_STMT);
1679 ret = gimple_build_return (retval);
1680 gsi_insert_after (&gsi, ret, GSI_NEW_STMT);
1683 free_dominance_info (CDI_DOMINATORS);
1684 free_dominance_info (CDI_POST_DOMINATORS);
1685 compute_inline_parameters (node, true);
1688 /* Execute function splitting pass. */
1690 static unsigned int
1691 execute_split_functions (void)
1693 gimple_stmt_iterator bsi;
1694 basic_block bb;
1695 int overall_time = 0, overall_size = 0;
1696 int todo = 0;
1697 struct cgraph_node *node = cgraph_node::get (current_function_decl);
1699 if (flags_from_decl_or_type (current_function_decl)
1700 & (ECF_NORETURN|ECF_MALLOC))
1702 if (dump_file)
1703 fprintf (dump_file, "Not splitting: noreturn/malloc function.\n");
1704 return 0;
1706 if (MAIN_NAME_P (DECL_NAME (current_function_decl)))
1708 if (dump_file)
1709 fprintf (dump_file, "Not splitting: main function.\n");
1710 return 0;
1712 /* This can be relaxed; function might become inlinable after splitting
1713 away the uninlinable part. */
1714 if (inline_edge_summary_vec.exists ()
1715 && !inline_summaries->get (node)->inlinable)
1717 if (dump_file)
1718 fprintf (dump_file, "Not splitting: not inlinable.\n");
1719 return 0;
1721 if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
1723 if (dump_file)
1724 fprintf (dump_file, "Not splitting: disregarding inline limits.\n");
1725 return 0;
1727 /* This can be relaxed; most of versioning tests actually prevents
1728 a duplication. */
1729 if (!tree_versionable_function_p (current_function_decl))
1731 if (dump_file)
1732 fprintf (dump_file, "Not splitting: not versionable.\n");
1733 return 0;
1735 /* FIXME: we could support this. */
1736 if (DECL_STRUCT_FUNCTION (current_function_decl)->static_chain_decl)
1738 if (dump_file)
1739 fprintf (dump_file, "Not splitting: nested function.\n");
1740 return 0;
1743 /* See if it makes sense to try to split.
1744 It makes sense to split if we inline, that is if we have direct calls to
1745 handle or direct calls are possibly going to appear as result of indirect
1746 inlining or LTO. Also handle -fprofile-generate as LTO to allow non-LTO
1747 training for LTO -fprofile-use build.
1749 Note that we are not completely conservative about disqualifying functions
1750 called once. It is possible that the caller is called more then once and
1751 then inlining would still benefit. */
1752 if ((!node->callers
1753 /* Local functions called once will be completely inlined most of time. */
1754 || (!node->callers->next_caller && node->local.local))
1755 && !node->address_taken
1756 && !node->has_aliases_p ()
1757 && (!flag_lto || !node->externally_visible))
1759 if (dump_file)
1760 fprintf (dump_file, "Not splitting: not called directly "
1761 "or called once.\n");
1762 return 0;
1765 /* FIXME: We can actually split if splitting reduces call overhead. */
1766 if (!flag_inline_small_functions
1767 && !DECL_DECLARED_INLINE_P (current_function_decl))
1769 if (dump_file)
1770 fprintf (dump_file, "Not splitting: not autoinlining and function"
1771 " is not inline.\n");
1772 return 0;
1775 /* We enforce splitting after loop headers when profile info is not
1776 available. */
1777 if (profile_status_for_fn (cfun) != PROFILE_READ)
1778 mark_dfs_back_edges ();
1780 /* Initialize bitmap to track forbidden calls. */
1781 forbidden_dominators = BITMAP_ALLOC (NULL);
1782 calculate_dominance_info (CDI_DOMINATORS);
1784 /* Compute local info about basic blocks and determine function size/time. */
1785 bb_info_vec.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
1786 memset (&best_split_point, 0, sizeof (best_split_point));
1787 basic_block return_bb = find_return_bb ();
1788 int tsan_exit_found = -1;
1789 FOR_EACH_BB_FN (bb, cfun)
1791 int time = 0;
1792 int size = 0;
1793 int freq = compute_call_stmt_bb_frequency (current_function_decl, bb);
1795 if (dump_file && (dump_flags & TDF_DETAILS))
1796 fprintf (dump_file, "Basic block %i\n", bb->index);
1798 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
1800 int this_time, this_size;
1801 gimple stmt = gsi_stmt (bsi);
1803 this_size = estimate_num_insns (stmt, &eni_size_weights);
1804 this_time = estimate_num_insns (stmt, &eni_time_weights) * freq;
1805 size += this_size;
1806 time += this_time;
1807 check_forbidden_calls (stmt);
1809 if (dump_file && (dump_flags & TDF_DETAILS))
1811 fprintf (dump_file, " freq:%6i size:%3i time:%3i ",
1812 freq, this_size, this_time);
1813 print_gimple_stmt (dump_file, stmt, 0, 0);
1816 if ((flag_sanitize & SANITIZE_THREAD)
1817 && is_gimple_call (stmt)
1818 && gimple_call_internal_p (stmt)
1819 && gimple_call_internal_fn (stmt) == IFN_TSAN_FUNC_EXIT)
1821 /* We handle TSAN_FUNC_EXIT for splitting either in the
1822 return_bb, or in its immediate predecessors. */
1823 if ((bb != return_bb && !find_edge (bb, return_bb))
1824 || (tsan_exit_found != -1
1825 && tsan_exit_found != (bb != return_bb)))
1827 if (dump_file)
1828 fprintf (dump_file, "Not splitting: TSAN_FUNC_EXIT"
1829 " in unexpected basic block.\n");
1830 BITMAP_FREE (forbidden_dominators);
1831 bb_info_vec.release ();
1832 return 0;
1834 tsan_exit_found = bb != return_bb;
1837 overall_time += time;
1838 overall_size += size;
1839 bb_info_vec[bb->index].time = time;
1840 bb_info_vec[bb->index].size = size;
1842 find_split_points (return_bb, overall_time, overall_size);
1843 if (best_split_point.split_bbs)
1845 split_function (return_bb, &best_split_point, tsan_exit_found == 1);
1846 BITMAP_FREE (best_split_point.ssa_names_to_pass);
1847 BITMAP_FREE (best_split_point.split_bbs);
1848 todo = TODO_update_ssa | TODO_cleanup_cfg;
1850 BITMAP_FREE (forbidden_dominators);
1851 bb_info_vec.release ();
1852 return todo;
1855 namespace {
1857 const pass_data pass_data_split_functions =
1859 GIMPLE_PASS, /* type */
1860 "fnsplit", /* name */
1861 OPTGROUP_NONE, /* optinfo_flags */
1862 TV_IPA_FNSPLIT, /* tv_id */
1863 PROP_cfg, /* properties_required */
1864 0, /* properties_provided */
1865 0, /* properties_destroyed */
1866 0, /* todo_flags_start */
1867 0, /* todo_flags_finish */
1870 class pass_split_functions : public gimple_opt_pass
1872 public:
1873 pass_split_functions (gcc::context *ctxt)
1874 : gimple_opt_pass (pass_data_split_functions, ctxt)
1877 /* opt_pass methods: */
1878 virtual bool gate (function *);
1879 virtual unsigned int execute (function *)
1881 return execute_split_functions ();
1884 }; // class pass_split_functions
1886 bool
1887 pass_split_functions::gate (function *)
1889 /* When doing profile feedback, we want to execute the pass after profiling
1890 is read. So disable one in early optimization. */
1891 return (flag_partial_inlining
1892 && !profile_arc_flag && !flag_branch_probabilities);
1895 } // anon namespace
1897 gimple_opt_pass *
1898 make_pass_split_functions (gcc::context *ctxt)
1900 return new pass_split_functions (ctxt);
1903 /* Execute function splitting pass. */
1905 static unsigned int
1906 execute_feedback_split_functions (void)
1908 unsigned int retval = execute_split_functions ();
1909 if (retval)
1910 retval |= TODO_rebuild_cgraph_edges;
1911 return retval;
1914 namespace {
1916 const pass_data pass_data_feedback_split_functions =
1918 GIMPLE_PASS, /* type */
1919 "feedback_fnsplit", /* name */
1920 OPTGROUP_NONE, /* optinfo_flags */
1921 TV_IPA_FNSPLIT, /* tv_id */
1922 PROP_cfg, /* properties_required */
1923 0, /* properties_provided */
1924 0, /* properties_destroyed */
1925 0, /* todo_flags_start */
1926 0, /* todo_flags_finish */
1929 class pass_feedback_split_functions : public gimple_opt_pass
1931 public:
1932 pass_feedback_split_functions (gcc::context *ctxt)
1933 : gimple_opt_pass (pass_data_feedback_split_functions, ctxt)
1936 /* opt_pass methods: */
1937 virtual bool gate (function *);
1938 virtual unsigned int execute (function *)
1940 return execute_feedback_split_functions ();
1943 }; // class pass_feedback_split_functions
1945 bool
1946 pass_feedback_split_functions::gate (function *)
1948 /* We don't need to split when profiling at all, we are producing
1949 lousy code anyway. */
1950 return (flag_partial_inlining
1951 && flag_branch_probabilities);
1954 } // anon namespace
1956 gimple_opt_pass *
1957 make_pass_feedback_split_functions (gcc::context *ctxt)
1959 return new pass_feedback_split_functions (ctxt);