1 /* Function splitting pass
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <jh@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* The purpose of this pass is to split function bodies to improve
23 inlining. I.e. for function of the form:
48 When func becomes inlinable and when cheap_test is often true, inlining func,
49 but not fund.part leads to performance imrovement similar as inlining
50 original func while the code size growth is smaller.
52 The pass is organized in three stages:
53 1) Collect local info about basic block into BB_INFO structure and
54 compute function body estimated size and time.
55 2) Via DFS walk find all possible basic blocks where we can split
57 3) If split point is found, split at the specified BB by creating a clone
58 and updating function to call it.
60 The decisions what functions to split are in execute_split_functions
63 There are several possible future improvements for this pass including:
65 1) Splitting to break up large functions
66 2) Splitting to reduce stack frame usage
67 3) Allow split part of function to use values computed in the header part.
68 The values needs to be passed to split function, perhaps via same
69 interface as for nested functions or as argument.
70 4) Support for simple rematerialization. I.e. when split part use
71 value computed in header from function parameter in very cheap way, we
72 can just recompute it.
73 5) Support splitting of nested functions.
74 6) Support non-SSA arguments.
75 7) There is nothing preventing us from producing multiple parts of single function
76 when needed or splitting also the parts. */
80 #include "coretypes.h"
85 #include "tree-flow.h"
86 #include "tree-pass.h"
89 #include "diagnostic.h"
90 #include "tree-dump.h"
91 #include "tree-inline.h"
94 #include "gimple-pretty-print.h"
96 /* Per basic block info. */
104 DEF_VEC_ALLOC_O(bb_info
,heap
);
106 static VEC(bb_info
, heap
) *bb_info_vec
;
108 /* Description of split point. */
112 /* Size of the partitions. */
113 unsigned int header_time
, header_size
, split_time
, split_size
;
115 /* SSA names that need to be passed into spit funciton. */
116 bitmap ssa_names_to_pass
;
118 /* Basic block where we split (that will become entry point of new function. */
119 basic_block entry_bb
;
121 /* Basic blocks we are splitting away. */
124 /* True when return value is computed on split part and thus it needs
126 bool split_part_set_retval
;
129 /* Best split point found. */
131 struct split_point best_split_point
;
133 static tree
find_retval (basic_block return_bb
);
135 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
136 variable, check it if it is present in bitmap passed via DATA. */
139 test_nonssa_use (gimple stmt ATTRIBUTE_UNUSED
, tree t
, void *data
)
141 t
= get_base_address (t
);
143 if (!t
|| is_gimple_reg (t
))
146 if (TREE_CODE (t
) == PARM_DECL
147 || (TREE_CODE (t
) == VAR_DECL
148 && auto_var_in_fn_p (t
, current_function_decl
))
149 || TREE_CODE (t
) == RESULT_DECL
150 || TREE_CODE (t
) == LABEL_DECL
)
151 return bitmap_bit_p ((bitmap
)data
, DECL_UID (t
));
153 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
154 to pretend that the value pointed to is actual result decl. */
155 if ((TREE_CODE (t
) == MEM_REF
|| INDIRECT_REF_P (t
))
156 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
157 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t
, 0))) == RESULT_DECL
158 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl
)))
160 bitmap_bit_p ((bitmap
)data
,
161 DECL_UID (DECL_RESULT (current_function_decl
)));
166 /* Dump split point CURRENT. */
169 dump_split_point (FILE * file
, struct split_point
*current
)
172 "Split point at BB %i header time:%i header size: %i"
173 " split time: %i split size: %i\n bbs: ",
174 current
->entry_bb
->index
, current
->header_time
,
175 current
->header_size
, current
->split_time
, current
->split_size
);
176 dump_bitmap (file
, current
->split_bbs
);
177 fprintf (file
, " SSA names to pass: ");
178 dump_bitmap (file
, current
->ssa_names_to_pass
);
181 /* Look for all BBs in header that might lead to the split part and verify
182 that they are not defining any non-SSA var used by the split part.
183 Parameters are the same as for consider_split. */
186 verify_non_ssa_vars (struct split_point
*current
, bitmap non_ssa_vars
,
187 basic_block return_bb
)
189 bitmap seen
= BITMAP_ALLOC (NULL
);
190 VEC (basic_block
,heap
) *worklist
= NULL
;
195 FOR_EACH_EDGE (e
, ei
, current
->entry_bb
->preds
)
196 if (e
->src
!= ENTRY_BLOCK_PTR
197 && !bitmap_bit_p (current
->split_bbs
, e
->src
->index
))
199 VEC_safe_push (basic_block
, heap
, worklist
, e
->src
);
200 bitmap_set_bit (seen
, e
->src
->index
);
203 while (!VEC_empty (basic_block
, worklist
))
205 gimple_stmt_iterator bsi
;
206 basic_block bb
= VEC_pop (basic_block
, worklist
);
208 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
209 if (e
->src
!= ENTRY_BLOCK_PTR
210 && bitmap_set_bit (seen
, e
->src
->index
))
212 gcc_checking_assert (!bitmap_bit_p (current
->split_bbs
,
214 VEC_safe_push (basic_block
, heap
, worklist
, e
->src
);
216 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
218 gimple stmt
= gsi_stmt (bsi
);
219 if (is_gimple_debug (stmt
))
221 if (walk_stmt_load_store_addr_ops
222 (stmt
, non_ssa_vars
, test_nonssa_use
, test_nonssa_use
,
228 if (gimple_code (stmt
) == GIMPLE_LABEL
229 && test_nonssa_use (stmt
, gimple_label_label (stmt
),
236 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
238 if (walk_stmt_load_store_addr_ops
239 (gsi_stmt (bsi
), non_ssa_vars
, test_nonssa_use
, test_nonssa_use
,
246 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
248 if (e
->dest
!= return_bb
)
250 for (bsi
= gsi_start_phis (return_bb
); !gsi_end_p (bsi
);
253 gimple stmt
= gsi_stmt (bsi
);
254 tree op
= gimple_phi_arg_def (stmt
, e
->dest_idx
);
256 if (!is_gimple_reg (gimple_phi_result (stmt
)))
258 if (TREE_CODE (op
) != SSA_NAME
259 && test_nonssa_use (stmt
, op
, non_ssa_vars
))
269 VEC_free (basic_block
, heap
, worklist
);
273 /* We found an split_point CURRENT. NON_SSA_VARS is bitmap of all non ssa
274 variables used and RETURN_BB is return basic block.
275 See if we can split function here. */
278 consider_split (struct split_point
*current
, bitmap non_ssa_vars
,
279 basic_block return_bb
)
282 unsigned int num_args
= 0;
283 unsigned int call_overhead
;
286 gimple_stmt_iterator bsi
;
288 int incomming_freq
= 0;
291 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
292 dump_split_point (dump_file
, current
);
294 FOR_EACH_EDGE (e
, ei
, current
->entry_bb
->preds
)
295 if (!bitmap_bit_p (current
->split_bbs
, e
->src
->index
))
296 incomming_freq
+= EDGE_FREQUENCY (e
);
298 /* Do not split when we would end up calling function anyway. */
300 >= (ENTRY_BLOCK_PTR
->frequency
301 * PARAM_VALUE (PARAM_PARTIAL_INLINING_ENTRY_PROBABILITY
) / 100))
303 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
305 " Refused: incomming frequency is too large.\n");
309 if (!current
->header_size
)
311 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
312 fprintf (dump_file
, " Refused: header empty\n");
316 /* Verify that PHI args on entry are either virutal or all their operands
317 incomming from header are the same. */
318 for (bsi
= gsi_start_phis (current
->entry_bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
320 gimple stmt
= gsi_stmt (bsi
);
323 if (!is_gimple_reg (gimple_phi_result (stmt
)))
325 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
327 edge e
= gimple_phi_arg_edge (stmt
, i
);
328 if (!bitmap_bit_p (current
->split_bbs
, e
->src
->index
))
330 tree edge_val
= gimple_phi_arg_def (stmt
, i
);
331 if (val
&& edge_val
!= val
)
333 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
335 " Refused: entry BB has PHI with multiple variants\n");
344 /* See what argument we will pass to the split function and compute
346 call_overhead
= eni_size_weights
.call_cost
;
347 for (parm
= DECL_ARGUMENTS (current_function_decl
); parm
;
348 parm
= DECL_CHAIN (parm
))
350 if (!is_gimple_reg (parm
))
352 if (bitmap_bit_p (non_ssa_vars
, DECL_UID (parm
)))
354 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
356 " Refused: need to pass non-ssa param values\n");
360 else if (gimple_default_def (cfun
, parm
)
361 && bitmap_bit_p (current
->ssa_names_to_pass
,
362 SSA_NAME_VERSION (gimple_default_def
365 if (!VOID_TYPE_P (TREE_TYPE (parm
)))
366 call_overhead
+= estimate_move_cost (TREE_TYPE (parm
));
370 if (!VOID_TYPE_P (TREE_TYPE (current_function_decl
)))
371 call_overhead
+= estimate_move_cost (TREE_TYPE (current_function_decl
));
373 if (current
->split_size
<= call_overhead
)
375 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
377 " Refused: split size is smaller than call overhead\n");
380 if (current
->header_size
+ call_overhead
381 >= (unsigned int)(DECL_DECLARED_INLINE_P (current_function_decl
)
382 ? MAX_INLINE_INSNS_SINGLE
383 : MAX_INLINE_INSNS_AUTO
))
385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
387 " Refused: header size is too large for inline candidate\n");
391 /* FIXME: we currently can pass only SSA function parameters to the split
392 arguments. Once parm_adjustment infrastructure is supported by cloning,
393 we can pass more than that. */
394 if (num_args
!= bitmap_count_bits (current
->ssa_names_to_pass
))
397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
399 " Refused: need to pass non-param values\n");
403 /* When there are non-ssa vars used in the split region, see if they
404 are used in the header region. If so, reject the split.
405 FIXME: we can use nested function support to access both. */
406 if (!bitmap_empty_p (non_ssa_vars
)
407 && !verify_non_ssa_vars (current
, non_ssa_vars
, return_bb
))
409 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
411 " Refused: split part has non-ssa uses\n");
414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
415 fprintf (dump_file
, " Accepted!\n");
417 /* See if retval used by return bb is computed by header or split part.
418 When it is computed by split part, we need to produce return statement
419 in the split part and add code to header to pass it around.
421 This is bit tricky to test:
422 1) When there is no return_bb or no return value, we always pass
424 2) Invariants are always computed by caller.
425 3) For SSA we need to look if defining statement is in header or split part
426 4) For non-SSA we need to look where the var is computed. */
427 retval
= find_retval (return_bb
);
429 current
->split_part_set_retval
= true;
430 else if (is_gimple_min_invariant (retval
))
431 current
->split_part_set_retval
= false;
432 /* Special case is value returned by reference we record as if it was non-ssa
433 set to result_decl. */
434 else if (TREE_CODE (retval
) == SSA_NAME
435 && TREE_CODE (SSA_NAME_VAR (retval
)) == RESULT_DECL
436 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl
)))
437 current
->split_part_set_retval
438 = bitmap_bit_p (non_ssa_vars
, DECL_UID (SSA_NAME_VAR (retval
)));
439 else if (TREE_CODE (retval
) == SSA_NAME
)
440 current
->split_part_set_retval
441 = (!SSA_NAME_IS_DEFAULT_DEF (retval
)
442 && (bitmap_bit_p (current
->split_bbs
,
443 gimple_bb (SSA_NAME_DEF_STMT (retval
))->index
)
444 || gimple_bb (SSA_NAME_DEF_STMT (retval
)) == return_bb
));
445 else if (TREE_CODE (retval
) == PARM_DECL
)
446 current
->split_part_set_retval
= false;
447 else if (TREE_CODE (retval
) == VAR_DECL
448 || TREE_CODE (retval
) == RESULT_DECL
)
449 current
->split_part_set_retval
450 = bitmap_bit_p (non_ssa_vars
, DECL_UID (retval
));
452 current
->split_part_set_retval
= true;
454 /* At the moment chose split point with lowest frequency and that leaves
455 out smallest size of header.
456 In future we might re-consider this heuristics. */
457 if (!best_split_point
.split_bbs
458 || best_split_point
.entry_bb
->frequency
> current
->entry_bb
->frequency
459 || (best_split_point
.entry_bb
->frequency
== current
->entry_bb
->frequency
460 && best_split_point
.split_size
< current
->split_size
))
463 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
464 fprintf (dump_file
, " New best split point!\n");
465 if (best_split_point
.ssa_names_to_pass
)
467 BITMAP_FREE (best_split_point
.ssa_names_to_pass
);
468 BITMAP_FREE (best_split_point
.split_bbs
);
470 best_split_point
= *current
;
471 best_split_point
.ssa_names_to_pass
= BITMAP_ALLOC (NULL
);
472 bitmap_copy (best_split_point
.ssa_names_to_pass
,
473 current
->ssa_names_to_pass
);
474 best_split_point
.split_bbs
= BITMAP_ALLOC (NULL
);
475 bitmap_copy (best_split_point
.split_bbs
, current
->split_bbs
);
479 /* Return basic block containing RETURN statement. We allow basic blocks
483 but return_bb can not be more complex than this.
484 If nothing is found, return EXIT_BLOCK_PTR.
486 When there are multiple RETURN statement, chose one with return value,
487 since that one is more likely shared by multiple code paths.
489 Return BB is special, because for function splitting it is the only
490 basic block that is duplicated in between header and split part of the
493 TODO: We might support multiple return blocks. */
496 find_return_bb (void)
500 basic_block return_bb
= EXIT_BLOCK_PTR
;
502 if (EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) == 1)
503 FOR_EACH_EDGE (e
, ei
, EXIT_BLOCK_PTR
->preds
)
505 gimple_stmt_iterator bsi
;
506 bool found_return
= false;
507 tree retval
= NULL_TREE
;
509 for (bsi
= gsi_last_bb (e
->src
); !gsi_end_p (bsi
); gsi_prev (&bsi
))
511 gimple stmt
= gsi_stmt (bsi
);
512 if (gimple_code (stmt
) == GIMPLE_LABEL
513 || is_gimple_debug (stmt
))
515 else if (gimple_code (stmt
) == GIMPLE_ASSIGN
517 && gimple_assign_single_p (stmt
)
518 && (auto_var_in_fn_p (gimple_assign_rhs1 (stmt
),
519 current_function_decl
)
520 || is_gimple_min_invariant
521 (gimple_assign_rhs1 (stmt
)))
522 && retval
== gimple_assign_lhs (stmt
))
524 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
527 retval
= gimple_return_retval (stmt
);
532 if (gsi_end_p (bsi
) && found_return
)
543 /* Given return basicblock RETURN_BB, see where return value is really
546 find_retval (basic_block return_bb
)
548 gimple_stmt_iterator bsi
;
549 for (bsi
= gsi_start_bb (return_bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
550 if (gimple_code (gsi_stmt (bsi
)) == GIMPLE_RETURN
)
551 return gimple_return_retval (gsi_stmt (bsi
));
552 else if (gimple_code (gsi_stmt (bsi
)) == GIMPLE_ASSIGN
)
553 return gimple_assign_rhs1 (gsi_stmt (bsi
));
557 /* Callback for walk_stmt_load_store_addr_ops. If T is non-SSA automatic
558 variable, mark it as used in bitmap passed via DATA.
559 Return true when access to T prevents splitting the function. */
562 mark_nonssa_use (gimple stmt ATTRIBUTE_UNUSED
, tree t
, void *data
)
564 t
= get_base_address (t
);
566 if (!t
|| is_gimple_reg (t
))
569 /* At present we can't pass non-SSA arguments to split function.
570 FIXME: this can be relaxed by passing references to arguments. */
571 if (TREE_CODE (t
) == PARM_DECL
)
573 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
575 "Cannot split: use of non-ssa function parameter.\n");
579 if ((TREE_CODE (t
) == VAR_DECL
580 && auto_var_in_fn_p (t
, current_function_decl
))
581 || TREE_CODE (t
) == RESULT_DECL
582 || TREE_CODE (t
) == LABEL_DECL
)
583 bitmap_set_bit ((bitmap
)data
, DECL_UID (t
));
585 /* For DECL_BY_REFERENCE, the return value is actually a pointer. We want
586 to pretend that the value pointed to is actual result decl. */
587 if ((TREE_CODE (t
) == MEM_REF
|| INDIRECT_REF_P (t
))
588 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
589 && TREE_CODE (SSA_NAME_VAR (TREE_OPERAND (t
, 0))) == RESULT_DECL
590 && DECL_BY_REFERENCE (DECL_RESULT (current_function_decl
)))
592 bitmap_bit_p ((bitmap
)data
,
593 DECL_UID (DECL_RESULT (current_function_decl
)));
598 /* Compute local properties of basic block BB we collect when looking for
599 split points. We look for ssa defs and store them in SET_SSA_NAMES,
600 for ssa uses and store them in USED_SSA_NAMES and for any non-SSA automatic
601 vars stored in NON_SSA_VARS.
603 When BB has edge to RETURN_BB, collect uses in RETURN_BB too.
605 Return false when BB contains something that prevents it from being put into
609 visit_bb (basic_block bb
, basic_block return_bb
,
610 bitmap set_ssa_names
, bitmap used_ssa_names
,
613 gimple_stmt_iterator bsi
;
616 bool can_split
= true;
618 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
620 gimple stmt
= gsi_stmt (bsi
);
625 if (is_gimple_debug (stmt
))
628 /* FIXME: We can split regions containing EH. We can not however
629 split RESX, EH_DISPATCH and EH_POINTER referring to same region
630 into different partitions. This would require tracking of
631 EH regions and checking in consider_split_point if they
632 are not used elsewhere. */
633 if (gimple_code (stmt
) == GIMPLE_RESX
634 && stmt_can_throw_external (stmt
))
636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
637 fprintf (dump_file
, "Cannot split: external resx.\n");
640 if (gimple_code (stmt
) == GIMPLE_EH_DISPATCH
)
642 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
643 fprintf (dump_file
, "Cannot split: eh dispatch.\n");
647 /* Check builtins that prevent splitting. */
648 if (gimple_code (stmt
) == GIMPLE_CALL
649 && (decl
= gimple_call_fndecl (stmt
)) != NULL_TREE
650 && DECL_BUILT_IN (decl
)
651 && DECL_BUILT_IN_CLASS (decl
) == BUILT_IN_NORMAL
)
652 switch (DECL_FUNCTION_CODE (decl
))
654 /* FIXME: once we will allow passing non-parm values to split part,
655 we need to be sure to handle correct builtin_stack_save and
656 builtin_stack_restore. At the moment we are safe; there is no
657 way to store builtin_stack_save result in non-SSA variable
658 since all calls to those are compiler generated. */
660 case BUILT_IN_VA_START
:
661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
663 "Cannot split: builtin_apply and va_start.\n");
666 case BUILT_IN_EH_POINTER
:
667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
668 fprintf (dump_file
, "Cannot split: builtin_eh_pointer.\n");
675 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_DEF
)
676 bitmap_set_bit (set_ssa_names
, SSA_NAME_VERSION (op
));
677 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, iter
, SSA_OP_USE
)
678 bitmap_set_bit (used_ssa_names
, SSA_NAME_VERSION (op
));
679 can_split
&= !walk_stmt_load_store_addr_ops (stmt
, non_ssa_vars
,
684 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
686 gimple stmt
= gsi_stmt (bsi
);
689 if (is_gimple_debug (stmt
))
691 if (!is_gimple_reg (gimple_phi_result (stmt
)))
693 bitmap_set_bit (set_ssa_names
,
694 SSA_NAME_VERSION (gimple_phi_result (stmt
)));
695 for (i
= 0; i
< gimple_phi_num_args (stmt
); i
++)
697 tree op
= gimple_phi_arg_def (stmt
, i
);
698 if (TREE_CODE (op
) == SSA_NAME
)
699 bitmap_set_bit (used_ssa_names
, SSA_NAME_VERSION (op
));
701 can_split
&= !walk_stmt_load_store_addr_ops (stmt
, non_ssa_vars
,
706 /* Record also uses comming from PHI operand in return BB. */
707 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
708 if (e
->dest
== return_bb
)
710 for (bsi
= gsi_start_phis (return_bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
712 gimple stmt
= gsi_stmt (bsi
);
713 tree op
= gimple_phi_arg_def (stmt
, e
->dest_idx
);
715 if (is_gimple_debug (stmt
))
717 if (!is_gimple_reg (gimple_phi_result (stmt
)))
719 if (TREE_CODE (op
) == SSA_NAME
)
720 bitmap_set_bit (used_ssa_names
, SSA_NAME_VERSION (op
));
722 can_split
&= !mark_nonssa_use (stmt
, op
, non_ssa_vars
);
728 /* Stack entry for recursive DFS walk in find_split_point. */
732 /* Basic block we are examining. */
735 /* SSA names set and used by the BB and all BBs reachable
736 from it via DFS walk. */
737 bitmap set_ssa_names
, used_ssa_names
;
740 /* All BBS visited from this BB via DFS walk. */
743 /* Last examined edge in DFS walk. Since we walk unoriented graph,
744 the value is up to sum of incomming and outgoing edges of BB. */
745 unsigned int edge_num
;
747 /* Stack entry index of earliest BB reachable from current BB
748 or any BB visited later in DFS valk. */
751 /* Overall time and size of all BBs reached from this BB in DFS walk. */
752 int overall_time
, overall_size
;
754 /* When false we can not split on this BB. */
757 DEF_VEC_O(stack_entry
);
758 DEF_VEC_ALLOC_O(stack_entry
,heap
);
761 /* Find all articulations and call consider_split on them.
762 OVERALL_TIME and OVERALL_SIZE is time and size of the function.
764 We perform basic algorithm for finding an articulation in a graph
765 created from CFG by considering it to be an unoriented graph.
767 The articulation is discovered via DFS walk. We collect earliest
768 basic block on stack that is reachable via backward edge. Articulation
769 is any basic block such that there is no backward edge bypassing it.
770 To reduce stack usage we maintain heap allocated stack in STACK vector.
771 AUX pointer of BB is set to index it appears in the stack or -1 once
772 it is visited and popped off the stack.
774 The algorithm finds articulation after visiting the whole component
775 reachable by it. This makes it convenient to collect information about
776 the component used by consider_split. */
779 find_split_points (int overall_time
, int overall_size
)
782 VEC(stack_entry
, heap
) *stack
= NULL
;
784 basic_block return_bb
= find_return_bb ();
785 struct split_point current
;
787 current
.header_time
= overall_time
;
788 current
.header_size
= overall_size
;
789 current
.split_time
= 0;
790 current
.split_size
= 0;
791 current
.ssa_names_to_pass
= BITMAP_ALLOC (NULL
);
793 first
.bb
= ENTRY_BLOCK_PTR
;
795 first
.overall_time
= 0;
796 first
.overall_size
= 0;
797 first
.earliest
= INT_MAX
;
798 first
.set_ssa_names
= 0;
799 first
.used_ssa_names
= 0;
800 first
.bbs_visited
= 0;
801 VEC_safe_push (stack_entry
, heap
, stack
, &first
);
802 ENTRY_BLOCK_PTR
->aux
= (void *)(intptr_t)-1;
804 while (!VEC_empty (stack_entry
, stack
))
806 stack_entry
*entry
= VEC_last (stack_entry
, stack
);
808 /* We are walking an acyclic graph, so edge_num counts
809 succ and pred edges together. However when considering
810 articulation, we want to have processed everything reachable
811 from articulation but nothing that reaches into it. */
812 if (entry
->edge_num
== EDGE_COUNT (entry
->bb
->succs
)
813 && entry
->bb
!= ENTRY_BLOCK_PTR
)
815 int pos
= VEC_length (stack_entry
, stack
);
816 entry
->can_split
&= visit_bb (entry
->bb
, return_bb
,
817 entry
->set_ssa_names
,
818 entry
->used_ssa_names
,
819 entry
->non_ssa_vars
);
820 if (pos
<= entry
->earliest
&& !entry
->can_split
821 && dump_file
&& (dump_flags
& TDF_DETAILS
))
823 "found articulation at bb %i but can not split\n",
825 if (pos
<= entry
->earliest
&& entry
->can_split
)
827 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
828 fprintf (dump_file
, "found articulation at bb %i\n",
830 current
.entry_bb
= entry
->bb
;
831 current
.ssa_names_to_pass
= BITMAP_ALLOC (NULL
);
832 bitmap_and_compl (current
.ssa_names_to_pass
,
833 entry
->used_ssa_names
, entry
->set_ssa_names
);
834 current
.header_time
= overall_time
- entry
->overall_time
;
835 current
.header_size
= overall_size
- entry
->overall_size
;
836 current
.split_time
= entry
->overall_time
;
837 current
.split_size
= entry
->overall_size
;
838 current
.split_bbs
= entry
->bbs_visited
;
839 consider_split (¤t
, entry
->non_ssa_vars
, return_bb
);
840 BITMAP_FREE (current
.ssa_names_to_pass
);
843 /* Do actual DFS walk. */
845 < (EDGE_COUNT (entry
->bb
->succs
)
846 + EDGE_COUNT (entry
->bb
->preds
)))
850 if (entry
->edge_num
< EDGE_COUNT (entry
->bb
->succs
))
852 e
= EDGE_SUCC (entry
->bb
, entry
->edge_num
);
857 e
= EDGE_PRED (entry
->bb
, entry
->edge_num
858 - EDGE_COUNT (entry
->bb
->succs
));
864 /* New BB to visit, push it to the stack. */
865 if (dest
!= return_bb
&& dest
!= EXIT_BLOCK_PTR
868 stack_entry new_entry
;
871 new_entry
.edge_num
= 0;
872 new_entry
.overall_time
873 = VEC_index (bb_info
, bb_info_vec
, dest
->index
)->time
;
874 new_entry
.overall_size
875 = VEC_index (bb_info
, bb_info_vec
, dest
->index
)->size
;
876 new_entry
.earliest
= INT_MAX
;
877 new_entry
.set_ssa_names
= BITMAP_ALLOC (NULL
);
878 new_entry
.used_ssa_names
= BITMAP_ALLOC (NULL
);
879 new_entry
.bbs_visited
= BITMAP_ALLOC (NULL
);
880 new_entry
.non_ssa_vars
= BITMAP_ALLOC (NULL
);
881 new_entry
.can_split
= true;
882 bitmap_set_bit (new_entry
.bbs_visited
, dest
->index
);
883 VEC_safe_push (stack_entry
, heap
, stack
, &new_entry
);
884 dest
->aux
= (void *)(intptr_t)VEC_length (stack_entry
, stack
);
886 /* Back edge found, record the earliest point. */
887 else if ((intptr_t)dest
->aux
> 0
888 && (intptr_t)dest
->aux
< entry
->earliest
)
889 entry
->earliest
= (intptr_t)dest
->aux
;
891 /* We are done with examing the edges. pop off the value from stack and
892 merge stuff we cummulate during the walk. */
893 else if (entry
->bb
!= ENTRY_BLOCK_PTR
)
895 stack_entry
*prev
= VEC_index (stack_entry
, stack
,
896 VEC_length (stack_entry
, stack
) - 2);
898 entry
->bb
->aux
= (void *)(intptr_t)-1;
899 prev
->can_split
&= entry
->can_split
;
900 if (prev
->set_ssa_names
)
902 bitmap_ior_into (prev
->set_ssa_names
, entry
->set_ssa_names
);
903 bitmap_ior_into (prev
->used_ssa_names
, entry
->used_ssa_names
);
904 bitmap_ior_into (prev
->bbs_visited
, entry
->bbs_visited
);
905 bitmap_ior_into (prev
->non_ssa_vars
, entry
->non_ssa_vars
);
907 if (prev
->earliest
> entry
->earliest
)
908 prev
->earliest
= entry
->earliest
;
909 prev
->overall_time
+= entry
->overall_time
;
910 prev
->overall_size
+= entry
->overall_size
;
911 BITMAP_FREE (entry
->set_ssa_names
);
912 BITMAP_FREE (entry
->used_ssa_names
);
913 BITMAP_FREE (entry
->bbs_visited
);
914 BITMAP_FREE (entry
->non_ssa_vars
);
915 VEC_pop (stack_entry
, stack
);
918 VEC_pop (stack_entry
, stack
);
920 ENTRY_BLOCK_PTR
->aux
= NULL
;
923 VEC_free (stack_entry
, heap
, stack
);
924 BITMAP_FREE (current
.ssa_names_to_pass
);
927 /* Split function at SPLIT_POINT. */
930 split_function (struct split_point
*split_point
)
932 VEC (tree
, heap
) *args_to_pass
= NULL
;
933 bitmap args_to_skip
= BITMAP_ALLOC (NULL
);
936 struct cgraph_node
*node
;
937 basic_block return_bb
= find_return_bb ();
939 gimple_stmt_iterator gsi
;
943 tree retval
= NULL
, real_retval
= NULL
;
944 bool split_part_return_p
= false;
945 gimple last_stmt
= NULL
;
949 fprintf (dump_file
, "\n\nSplitting function at:\n");
950 dump_split_point (dump_file
, split_point
);
953 /* Collect the parameters of new function and args_to_skip bitmap. */
954 for (parm
= DECL_ARGUMENTS (current_function_decl
);
955 parm
; parm
= DECL_CHAIN (parm
), num
++)
956 if (!is_gimple_reg (parm
)
957 || !gimple_default_def (cfun
, parm
)
958 || !bitmap_bit_p (split_point
->ssa_names_to_pass
,
959 SSA_NAME_VERSION (gimple_default_def (cfun
, parm
))))
960 bitmap_set_bit (args_to_skip
, num
);
962 VEC_safe_push (tree
, heap
, args_to_pass
, gimple_default_def (cfun
, parm
));
964 /* See if the split function will return. */
965 FOR_EACH_EDGE (e
, ei
, return_bb
->preds
)
966 if (bitmap_bit_p (split_point
->split_bbs
, e
->src
->index
))
969 split_part_return_p
= true;
971 /* Add return block to what will become the split function.
972 We do not return; no return block is needed. */
973 if (!split_part_return_p
)
975 /* We have no return block, so nothing is needed. */
976 else if (return_bb
== EXIT_BLOCK_PTR
)
978 /* When we do not want to return value, we need to construct
979 new return block with empty return statement.
980 FIXME: Once we are able to change return type, we should change function
981 to return void instead of just outputting function with undefined return
982 value. For structures this affects quality of codegen. */
983 else if (!split_point
->split_part_set_retval
984 && find_retval (return_bb
))
986 bool redirected
= true;
987 basic_block new_return_bb
= create_basic_block (NULL
, 0, return_bb
);
988 gimple_stmt_iterator gsi
= gsi_start_bb (new_return_bb
);
989 gsi_insert_after (&gsi
, gimple_build_return (NULL
), GSI_NEW_STMT
);
993 FOR_EACH_EDGE (e
, ei
, return_bb
->preds
)
994 if (bitmap_bit_p (split_point
->split_bbs
, e
->src
->index
))
996 new_return_bb
->count
+= e
->count
;
997 new_return_bb
->frequency
+= EDGE_FREQUENCY (e
);
998 redirect_edge_and_branch (e
, new_return_bb
);
1003 e
= make_edge (new_return_bb
, EXIT_BLOCK_PTR
, 0);
1004 e
->probability
= REG_BR_PROB_BASE
;
1005 e
->count
= new_return_bb
->count
;
1006 bitmap_set_bit (split_point
->split_bbs
, new_return_bb
->index
);
1007 /* We change CFG in a way tree-inline is not able to compensate on while
1008 updating PHIs. There are only virtuals in return_bb, so recompute
1010 for (gsi
= gsi_start_phis (return_bb
); !gsi_end_p (gsi
);)
1012 gimple stmt
= gsi_stmt (gsi
);
1013 gcc_assert (!is_gimple_reg (gimple_phi_result (stmt
)));
1014 mark_virtual_phi_result_for_renaming (stmt
);
1015 remove_phi_node (&gsi
, true);
1018 /* When we pass aorund the value, use existing return block. */
1020 bitmap_set_bit (split_point
->split_bbs
, return_bb
->index
);
1022 /* Now create the actual clone. */
1023 rebuild_cgraph_edges ();
1024 node
= cgraph_function_versioning (cgraph_node (current_function_decl
),
1027 split_point
->split_bbs
,
1028 split_point
->entry_bb
, "part");
1029 /* For usual cloning it is enough to clear builtin only when signature
1030 changes. For partial inlining we however can not expect the part
1031 of builtin implementation to have same semantic as the whole. */
1032 if (DECL_BUILT_IN (node
->decl
))
1034 DECL_BUILT_IN_CLASS (node
->decl
) = NOT_BUILT_IN
;
1035 DECL_FUNCTION_CODE (node
->decl
) = (enum built_in_function
) 0;
1037 cgraph_node_remove_callees (cgraph_node (current_function_decl
));
1038 if (!split_part_return_p
)
1039 TREE_THIS_VOLATILE (node
->decl
) = 1;
1041 dump_function_to_file (node
->decl
, dump_file
, dump_flags
);
1043 /* Create the basic block we place call into. It is the entry basic block
1044 split after last label. */
1045 call_bb
= split_point
->entry_bb
;
1046 for (gsi
= gsi_start_bb (call_bb
); !gsi_end_p (gsi
);)
1047 if (gimple_code (gsi_stmt (gsi
)) == GIMPLE_LABEL
)
1049 last_stmt
= gsi_stmt (gsi
);
1054 e
= split_block (split_point
->entry_bb
, last_stmt
);
1057 /* Produce the call statement. */
1058 gsi
= gsi_last_bb (call_bb
);
1059 call
= gimple_build_call_vec (node
->decl
, args_to_pass
);
1060 gimple_set_block (call
, DECL_INITIAL (current_function_decl
));
1062 /* We avoid address being taken on any variable used by split part,
1063 so return slot optimization is always possible. Moreover this is
1064 required to make DECL_BY_REFERENCE work. */
1065 if (aggregate_value_p (DECL_RESULT (current_function_decl
),
1066 TREE_TYPE (current_function_decl
)))
1067 gimple_call_set_return_slot_opt (call
, true);
1069 /* Update return value. This is bit tricky. When we do not return,
1070 do nothing. When we return we might need to update return_bb
1071 or produce a new return statement. */
1072 if (!split_part_return_p
)
1073 gsi_insert_after (&gsi
, call
, GSI_NEW_STMT
);
1076 e
= make_edge (call_bb
, return_bb
,
1077 return_bb
== EXIT_BLOCK_PTR
? 0 : EDGE_FALLTHRU
);
1078 e
->count
= call_bb
->count
;
1079 e
->probability
= REG_BR_PROB_BASE
;
1081 /* If there is return basic block, see what value we need to store
1082 return value into and put call just before it. */
1083 if (return_bb
!= EXIT_BLOCK_PTR
)
1085 real_retval
= retval
= find_retval (return_bb
);
1087 if (real_retval
&& split_point
->split_part_set_retval
)
1089 gimple_stmt_iterator psi
;
1091 /* See if we need new SSA_NAME for the result.
1092 When DECL_BY_REFERENCE is true, retval is actually pointer to
1093 return value and it is constant in whole function. */
1094 if (TREE_CODE (retval
) == SSA_NAME
1095 && !DECL_BY_REFERENCE (DECL_RESULT (current_function_decl
)))
1097 retval
= make_ssa_name (SSA_NAME_VAR (retval
), call
);
1099 /* See if there is PHI defining return value. */
1100 for (psi
= gsi_start_phis (return_bb
);
1101 !gsi_end_p (psi
); gsi_next (&psi
))
1102 if (is_gimple_reg (gimple_phi_result (gsi_stmt (psi
))))
1105 /* When there is PHI, just update its value. */
1106 if (TREE_CODE (retval
) == SSA_NAME
1107 && !gsi_end_p (psi
))
1108 add_phi_arg (gsi_stmt (psi
), retval
, e
, UNKNOWN_LOCATION
);
1109 /* Otherwise update the return BB itself.
1110 find_return_bb allows at most one assignment to return value,
1111 so update first statement. */
1114 gimple_stmt_iterator bsi
;
1115 for (bsi
= gsi_start_bb (return_bb
); !gsi_end_p (bsi
);
1117 if (gimple_code (gsi_stmt (bsi
)) == GIMPLE_RETURN
)
1119 gimple_return_set_retval (gsi_stmt (bsi
), retval
);
1122 else if (gimple_code (gsi_stmt (bsi
)) == GIMPLE_ASSIGN
)
1124 gimple_assign_set_rhs1 (gsi_stmt (bsi
), retval
);
1127 update_stmt (gsi_stmt (bsi
));
1130 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl
)))
1131 gimple_call_set_lhs (call
, build_simple_mem_ref (retval
));
1133 gimple_call_set_lhs (call
, retval
);
1135 gsi_insert_after (&gsi
, call
, GSI_NEW_STMT
);
1137 /* We don't use return block (there is either no return in function or
1138 multiple of them). So create new basic block with return statement.
1143 if (split_point
->split_part_set_retval
1144 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl
))))
1146 retval
= DECL_RESULT (current_function_decl
);
1148 /* We use temporary register to hold value when aggregate_value_p
1149 is false. Similarly for DECL_BY_REFERENCE we must avoid extra
1151 if (!aggregate_value_p (retval
, TREE_TYPE (current_function_decl
))
1152 && !DECL_BY_REFERENCE (retval
))
1153 retval
= create_tmp_reg (TREE_TYPE (retval
), NULL
);
1154 if (is_gimple_reg (retval
))
1156 /* When returning by reference, there is only one SSA name
1157 assigned to RESULT_DECL (that is pointer to return value).
1158 Look it up or create new one if it is missing. */
1159 if (DECL_BY_REFERENCE (retval
))
1162 if ((retval_name
= gimple_default_def (cfun
, retval
))
1164 retval
= retval_name
;
1167 retval_name
= make_ssa_name (retval
,
1168 gimple_build_nop ());
1169 set_default_def (retval
, retval_name
);
1170 retval
= retval_name
;
1173 /* Otherwise produce new SSA name for return value. */
1175 retval
= make_ssa_name (retval
, call
);
1177 if (DECL_BY_REFERENCE (DECL_RESULT (current_function_decl
)))
1178 gimple_call_set_lhs (call
, build_simple_mem_ref (retval
));
1180 gimple_call_set_lhs (call
, retval
);
1182 gsi_insert_after (&gsi
, call
, GSI_NEW_STMT
);
1183 ret
= gimple_build_return (retval
);
1184 gsi_insert_after (&gsi
, ret
, GSI_NEW_STMT
);
1187 free_dominance_info (CDI_DOMINATORS
);
1188 free_dominance_info (CDI_POST_DOMINATORS
);
1189 compute_inline_parameters (node
);
1192 /* Execute function splitting pass. */
1195 execute_split_functions (void)
1197 gimple_stmt_iterator bsi
;
1199 int overall_time
= 0, overall_size
= 0;
1201 struct cgraph_node
*node
= cgraph_node (current_function_decl
);
1203 if (flags_from_decl_or_type (current_function_decl
) & ECF_NORETURN
)
1206 fprintf (dump_file
, "Not splitting: noreturn function.\n");
1209 if (MAIN_NAME_P (DECL_NAME (current_function_decl
)))
1212 fprintf (dump_file
, "Not splitting: main function.\n");
1215 /* This can be relaxed; function might become inlinable after splitting
1216 away the uninlinable part. */
1217 if (!node
->local
.inlinable
)
1220 fprintf (dump_file
, "Not splitting: not inlinable.\n");
1223 if (node
->local
.disregard_inline_limits
)
1226 fprintf (dump_file
, "Not splitting: disregading inline limits.\n");
1229 /* This can be relaxed; most of versioning tests actually prevents
1231 if (!tree_versionable_function_p (current_function_decl
))
1234 fprintf (dump_file
, "Not splitting: not versionable.\n");
1237 /* FIXME: we could support this. */
1238 if (DECL_STRUCT_FUNCTION (current_function_decl
)->static_chain_decl
)
1241 fprintf (dump_file
, "Not splitting: nested function.\n");
1245 /* See if it makes sense to try to split.
1246 It makes sense to split if we inline, that is if we have direct calls to
1247 handle or direct calls are possibly going to appear as result of indirect
1249 Note that we are not completely conservative about disqualifying functions
1250 called once. It is possible that the caller is called more then once and
1251 then inlining would still benefit. */
1252 if ((!node
->callers
|| !node
->callers
->next_caller
)
1253 && !node
->address_taken
1254 && ((!flag_lto
&& !flag_whopr
) || !node
->local
.externally_visible
))
1257 fprintf (dump_file
, "Not splitting: not called directly "
1258 "or called once.\n");
1262 /* FIXME: We can actually split if splitting reduces call overhead. */
1263 if (!flag_inline_small_functions
1264 && !DECL_DECLARED_INLINE_P (current_function_decl
))
1267 fprintf (dump_file
, "Not splitting: not autoinlining and function"
1268 " is not inline.\n");
1272 /* Compute local info about basic blocks and determine function size/time. */
1273 VEC_safe_grow_cleared (bb_info
, heap
, bb_info_vec
, last_basic_block
+ 1);
1274 memset (&best_split_point
, 0, sizeof (best_split_point
));
1279 int freq
= compute_call_stmt_bb_frequency (current_function_decl
, bb
);
1281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1282 fprintf (dump_file
, "Basic block %i\n", bb
->index
);
1284 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1286 int this_time
, this_size
;
1287 gimple stmt
= gsi_stmt (bsi
);
1289 this_size
= estimate_num_insns (stmt
, &eni_size_weights
);
1290 this_time
= estimate_num_insns (stmt
, &eni_time_weights
) * freq
;
1294 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1296 fprintf (dump_file
, " freq:%6i size:%3i time:%3i ",
1297 freq
, this_size
, this_time
);
1298 print_gimple_stmt (dump_file
, stmt
, 0, 0);
1301 overall_time
+= time
;
1302 overall_size
+= size
;
1303 VEC_index (bb_info
, bb_info_vec
, bb
->index
)->time
= time
;
1304 VEC_index (bb_info
, bb_info_vec
, bb
->index
)->size
= size
;
1306 find_split_points (overall_time
, overall_size
);
1307 if (best_split_point
.split_bbs
)
1309 split_function (&best_split_point
);
1310 BITMAP_FREE (best_split_point
.ssa_names_to_pass
);
1311 BITMAP_FREE (best_split_point
.split_bbs
);
1312 todo
= TODO_update_ssa
| TODO_cleanup_cfg
;
1314 VEC_free (bb_info
, heap
, bb_info_vec
);
1320 gate_split_functions (void)
1322 return flag_partial_inlining
;
1325 struct gimple_opt_pass pass_split_functions
=
1329 "fnsplit", /* name */
1330 gate_split_functions
, /* gate */
1331 execute_split_functions
, /* execute */
1334 0, /* static_pass_number */
1335 TV_IPA_FNSPLIT
, /* tv_id */
1336 PROP_cfg
, /* properties_required */
1337 0, /* properties_provided */
1338 0, /* properties_destroyed */
1339 0, /* todo_flags_start */
1340 TODO_dump_func
/* todo_flags_finish */