1 /* If-conversion for vectorizer.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Devang Patel <dpatel@apple.com>
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 /* This pass implements a tree level if-conversion of loops. Its
23 initial goal is to help the vectorizer to vectorize loops with
26 A short description of if-conversion:
28 o Decide if a loop is if-convertible or not.
29 o Walk all loop basic blocks in breadth first order (BFS order).
30 o Remove conditional statements (at the end of basic block)
31 and propagate condition into destination basic blocks'
33 o Replace modify expression with conditional modify expression
34 using current basic block's condition.
35 o Merge all basic blocks
36 o Replace phi nodes with conditional modify expr
37 o Merge all basic blocks into header
39 Sample transformation:
44 # i_23 = PHI <0(0), i_18(10)>;
47 if (j_15 > 41) goto <L1>; else goto <L17>;
54 # iftmp.2_4 = PHI <0(8), 42(2)>;
58 if (i_18 <= 15) goto <L19>; else goto <L18>;
68 # i_23 = PHI <0(0), i_18(10)>;
73 iftmp.2_4 = j_15 > 41 ? 42 : 0;
76 if (i_18 <= 15) goto <L19>; else goto <L18>;
86 #include "coretypes.h"
91 #include "basic-block.h"
92 #include "diagnostic.h"
93 #include "tree-pretty-print.h"
94 #include "gimple-pretty-print.h"
95 #include "tree-flow.h"
96 #include "tree-dump.h"
98 #include "tree-chrec.h"
99 #include "tree-data-ref.h"
100 #include "tree-scalar-evolution.h"
101 #include "tree-pass.h"
103 /* List of basic blocks in if-conversion-suitable order. */
104 static basic_block
*ifc_bbs
;
106 /* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
107 to the new variable. */
110 ifc_temp_var (tree type
, tree exp
)
112 const char *name
= "_ifc_";
116 /* Create new temporary variable. */
117 var
= create_tmp_var (type
, name
);
118 add_referenced_var (var
);
120 /* Build new statement to assign EXP to new variable. */
121 stmt
= gimple_build_assign (var
, exp
);
123 /* Get SSA name for the new variable and set make new statement
124 its definition statement. */
125 new_name
= make_ssa_name (var
, stmt
);
126 gimple_assign_set_lhs (stmt
, new_name
);
127 SSA_NAME_DEF_STMT (new_name
) = stmt
;
133 /* Add condition NEW_COND to the predicate list of basic block BB. */
136 add_to_predicate_list (basic_block bb
, tree new_cond
)
138 tree cond
= (tree
) bb
->aux
;
141 cond
= fold_build2_loc (EXPR_LOCATION (cond
),
142 TRUTH_OR_EXPR
, boolean_type_node
,
143 unshare_expr (cond
), new_cond
);
150 /* Add the condition COND to the previous condition PREV_COND, and add this
151 to the predicate list of the destination of edge E. GSI is the
152 place where the gimplification of the resulting condition should
153 output code. LOOP is the loop to be if-converted. */
156 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
157 tree prev_cond
, tree cond
,
158 gimple_stmt_iterator
*gsi
)
160 tree new_cond
= NULL_TREE
;
162 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
165 if (prev_cond
== boolean_true_node
|| !prev_cond
)
166 new_cond
= unshare_expr (cond
);
170 gimple tmp_stmt
= NULL
;
172 prev_cond
= force_gimple_operand_gsi (gsi
, unshare_expr (prev_cond
),
173 true, NULL
, true, GSI_SAME_STMT
);
175 cond
= force_gimple_operand_gsi (gsi
, unshare_expr (cond
),
176 true, NULL
, true, GSI_SAME_STMT
);
178 /* Add the condition COND to the e->aux field. In case the edge
179 destination is a PHI node, this condition will be added to
180 the block predicate to construct a complete condition. */
183 tmp
= build2 (TRUTH_AND_EXPR
, boolean_type_node
,
184 unshare_expr (prev_cond
), cond
);
185 tmp_stmt
= ifc_temp_var (boolean_type_node
, tmp
);
186 gsi_insert_before (gsi
, tmp_stmt
, GSI_SAME_STMT
);
187 new_cond
= gimple_assign_lhs (tmp_stmt
);
190 add_to_predicate_list (e
->dest
, new_cond
);
194 /* Return true if one of the successor edges of BB exits LOOP. */
197 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
202 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
203 if (loop_exit_edge_p (loop
, e
))
209 /* STMT is a GIMPLE_COND. Update two destination's predicate list.
210 Otherwise update the exit condition of LOOP appropriately. GSI
211 points to the statement STMT. */
214 tree_if_convert_cond_stmt (struct loop
*loop
, gimple stmt
, tree cond
,
215 gimple_stmt_iterator
*gsi
)
218 edge true_edge
, false_edge
;
219 location_t loc
= gimple_location (stmt
);
220 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
), boolean_type_node
,
221 gimple_cond_lhs (stmt
), gimple_cond_rhs (stmt
));
223 extract_true_false_edges_from_block (gimple_bb (stmt
),
224 &true_edge
, &false_edge
);
226 /* Add new condition into destination's predicate list. */
228 /* If C is true, then TRUE_EDGE is taken. */
229 add_to_dst_predicate_list (loop
, true_edge
, cond
, c
, gsi
);
231 /* If C is false, then FALSE_EDGE is taken. */
232 c2
= invert_truthvalue_loc (loc
, unshare_expr (c
));
233 add_to_dst_predicate_list (loop
, false_edge
, cond
, c2
, gsi
);
236 /* If-convert stmt T which is part of LOOP.
238 For conditional expressions, add a condition in the destination
239 basic block's predicate list. GSI points to the statement T. */
242 tree_if_convert_stmt (struct loop
*loop
, gimple t
, tree cond
,
243 gimple_stmt_iterator
*gsi
)
245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
247 fprintf (dump_file
, "------if-convert stmt\n");
248 print_gimple_stmt (dump_file
, t
, 0, TDF_SLIM
);
249 print_generic_stmt (dump_file
, cond
, TDF_SLIM
);
252 switch (gimple_code (t
))
254 /* Labels are harmless here. */
259 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
260 if (gimple_debug_bind_p (gsi_stmt (*gsi
)))
262 gimple_debug_bind_reset_value (gsi_stmt (*gsi
));
263 update_stmt (gsi_stmt (*gsi
));
268 /* This GIMPLE_ASSIGN is killing previous value of LHS. Appropriate
269 value will be selected by PHI node based on condition. It is possible
270 that before this transformation, PHI nodes was selecting default
271 value and now it will use this new value. This is OK because it does
272 not change the validity of the program. */
276 tree_if_convert_cond_stmt (loop
, t
, cond
, gsi
);
287 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
288 and it belongs to basic block BB.
290 PHI is not if-convertible if:
291 - it has more than 2 arguments,
292 - virtual PHI is immediately used in another PHI node,
293 - virtual PHI on BB other than header. */
296 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gimple phi
)
298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
300 fprintf (dump_file
, "-------------------------\n");
301 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
304 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
306 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
307 fprintf (dump_file
, "More than two phi node args.\n");
311 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi
))))
313 imm_use_iterator imm_iter
;
316 if (bb
!= loop
->header
)
318 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
319 fprintf (dump_file
, "Virtual phi not on loop header.\n");
322 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
324 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
327 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
336 /* Return true when STMT is if-convertible.
338 GIMPLE_ASSIGN statement is not if-convertible if,
341 - LHS is not var decl.
343 GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
346 if_convertible_gimple_assign_stmt_p (struct loop
*loop
, basic_block bb
,
349 tree lhs
= gimple_assign_lhs (stmt
);
351 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
353 fprintf (dump_file
, "-------------------------\n");
354 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
357 /* Some of these constrains might be too conservative. */
358 if (stmt_ends_bb_p (stmt
)
359 || gimple_has_volatile_ops (stmt
)
360 || (TREE_CODE (lhs
) == SSA_NAME
361 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
362 || gimple_has_side_effects (stmt
))
364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
365 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
369 /* See if it needs speculative loading or not. */
370 if (bb
!= loop
->header
371 && gimple_assign_rhs_could_trap_p (stmt
))
373 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
374 fprintf (dump_file
, "tree could trap...\n");
378 if (TREE_CODE (lhs
) != SSA_NAME
379 && bb
!= loop
->header
380 && !bb_with_exit_edge_p (loop
, bb
))
382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
384 fprintf (dump_file
, "LHS is not var\n");
385 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
393 /* Return true when STMT is if-convertible.
395 A statement is if-convertible if:
396 - it is an if-convertible GIMPLE_ASSGIN,
397 - it is a GIMPLE_LABEL or a GIMPLE_COND.
399 STMT is inside BB, which is inside loop LOOP. */
402 if_convertible_stmt_p (struct loop
*loop
, basic_block bb
, gimple stmt
)
404 switch (gimple_code (stmt
))
412 return if_convertible_gimple_assign_stmt_p (loop
, bb
, stmt
);
415 /* Don't know what to do with 'em so don't do anything. */
416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
418 fprintf (dump_file
, "don't know what to do\n");
419 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
428 /* Return true when BB is if-convertible. This routine does not check
429 basic block's statements and phis.
431 A basic block is not if-convertible if:
432 - it is non-empty and it is after the exit block (in BFS order),
433 - it is after the exit block but before the latch,
434 - its edges are not normal.
436 EXIT_BB is the basic block containing the exit of the LOOP. BB is
440 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
445 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
446 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
448 if (EDGE_COUNT (bb
->preds
) > 2
449 || EDGE_COUNT (bb
->succs
) > 2)
454 if (bb
!= loop
->latch
)
456 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
457 fprintf (dump_file
, "basic block after exit bb but before latch\n");
460 else if (!empty_block_p (bb
))
462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
463 fprintf (dump_file
, "non empty basic block after exit bb\n");
466 else if (bb
== loop
->latch
468 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
471 fprintf (dump_file
, "latch is not dominated by exit_block\n");
476 /* Be less adventurous and handle only normal edges. */
477 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
479 (EDGE_ABNORMAL_CALL
| EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
481 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
482 fprintf (dump_file
, "Difficult to handle edges\n");
489 /* Return true when all predecessor blocks of BB are visited. The
490 VISITED bitmap keeps track of the visited blocks. */
493 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
497 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
498 if (!bitmap_bit_p (*visited
, e
->src
->index
))
504 /* Get body of a LOOP in suitable order for if-conversion. It is
505 caller's responsibility to deallocate basic block list.
506 If-conversion suitable order is, breadth first sort (BFS) order
507 with an additional constraint: select a block only if all its
508 predecessors are already selected. */
511 get_loop_body_in_if_conv_order (const struct loop
*loop
)
513 basic_block
*blocks
, *blocks_in_bfs_order
;
516 unsigned int index
= 0;
517 unsigned int visited_count
= 0;
519 gcc_assert (loop
->num_nodes
);
520 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
522 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
523 visited
= BITMAP_ALLOC (NULL
);
525 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
528 while (index
< loop
->num_nodes
)
530 bb
= blocks_in_bfs_order
[index
];
532 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
534 free (blocks_in_bfs_order
);
535 BITMAP_FREE (visited
);
540 if (!bitmap_bit_p (visited
, bb
->index
))
542 if (pred_blocks_visited_p (bb
, &visited
)
543 || bb
== loop
->header
)
545 /* This block is now visited. */
546 bitmap_set_bit (visited
, bb
->index
);
547 blocks
[visited_count
++] = bb
;
553 if (index
== loop
->num_nodes
554 && visited_count
!= loop
->num_nodes
)
558 free (blocks_in_bfs_order
);
559 BITMAP_FREE (visited
);
563 /* Return true when LOOP is if-convertible.
564 LOOP is if-convertible if:
566 - it has two or more basic blocks,
567 - it has only one exit,
568 - loop header is not the exit edge,
569 - if its basic blocks and phi nodes are if convertible. */
572 if_convertible_loop_p (struct loop
*loop
)
575 gimple_stmt_iterator itr
;
579 basic_block exit_bb
= NULL
;
581 /* Handle only innermost loop. */
582 if (!loop
|| loop
->inner
)
584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
585 fprintf (dump_file
, "not innermost loop\n");
589 /* If only one block, no need for if-conversion. */
590 if (loop
->num_nodes
<= 2)
592 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
593 fprintf (dump_file
, "less than 2 basic blocks\n");
597 /* More than one loop exit is too much to handle. */
598 if (!single_exit (loop
))
600 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
601 fprintf (dump_file
, "multiple exits\n");
605 /* ??? Check target's vector conditional operation support for vectorizer. */
607 /* If one of the loop header's edge is exit edge then do not apply
609 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
611 if (loop_exit_edge_p (loop
, e
))
615 /* Don't if-convert the loop when the data dependences cannot be
616 computed: the loop won't be vectorized in that case. */
618 VEC (data_reference_p
, heap
) *refs
= VEC_alloc (data_reference_p
, heap
, 5);
619 VEC (ddr_p
, heap
) *ddrs
= VEC_alloc (ddr_p
, heap
, 25);
620 bool res
= compute_data_dependences_for_loop (loop
, true, &refs
, &ddrs
);
622 free_data_refs (refs
);
623 free_dependence_relations (ddrs
);
629 calculate_dominance_info (CDI_DOMINATORS
);
631 /* Allow statements that can be handled during if-conversion. */
632 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
635 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
636 fprintf (dump_file
, "Irreducible loop\n");
640 for (i
= 0; i
< loop
->num_nodes
; i
++)
644 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
647 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
648 if (!if_convertible_stmt_p (loop
, bb
, gsi_stmt (itr
)))
651 itr
= gsi_start_phis (bb
);
653 if (!gsi_end_p (itr
))
654 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
657 for (; !gsi_end_p (itr
); gsi_next (&itr
))
658 if (!if_convertible_phi_p (loop
, bb
, gsi_stmt (itr
)))
661 if (bb_with_exit_edge_p (loop
, bb
))
666 fprintf (dump_file
, "Applying if-conversion\n");
671 /* During if-conversion, the bb->aux field is used to hold a predicate
672 list. This function cleans for all the basic blocks in the given
673 LOOP their predicate list. It also cleans up the e->aux field of
674 all the successor edges: e->aux is used to hold the true and false
675 conditions for conditional expressions. */
678 clean_predicate_lists (struct loop
*loop
)
685 bb
= get_loop_body (loop
);
686 for (i
= 0; i
< loop
->num_nodes
; i
++)
689 FOR_EACH_EDGE (e
, ei
, bb
[i
]->succs
)
695 /* Basic block BB has two predecessors. Using predecessor's bb->aux
696 field, set appropriate condition COND for the PHI node replacement.
697 Return true block whose phi arguments are selected when cond is
698 true. LOOP is the loop containing the if-converted region, GSI is
699 the place to insert the code for the if-conversion. */
702 find_phi_replacement_condition (struct loop
*loop
,
703 basic_block bb
, tree
*cond
,
704 gimple_stmt_iterator
*gsi
)
706 edge first_edge
, second_edge
;
709 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
710 first_edge
= EDGE_PRED (bb
, 0);
711 second_edge
= EDGE_PRED (bb
, 1);
713 /* Use condition based on following criteria:
719 S2 is preferred over S1. Make 'b' first_bb and use its condition.
721 2) Do not make loop header first_bb.
724 S1: x = !(c == d)? a : b;
729 S3: x = (c == d) ? b : a;
731 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
734 4) If pred B is dominated by pred A then use pred B's condition.
737 /* Select condition that is not TRUTH_NOT_EXPR. */
738 tmp_cond
= (tree
) (first_edge
->src
)->aux
;
739 gcc_assert (tmp_cond
);
741 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
745 tmp_edge
= first_edge
;
746 first_edge
= second_edge
;
747 second_edge
= tmp_edge
;
750 /* Check if FIRST_BB is loop header or not and make sure that
751 FIRST_BB does not dominate SECOND_BB. */
752 if (first_edge
->src
== loop
->header
753 || dominated_by_p (CDI_DOMINATORS
,
754 second_edge
->src
, first_edge
->src
))
756 *cond
= (tree
) (second_edge
->src
)->aux
;
758 /* If there is a condition on an incoming edge, add it to the
759 incoming bb predicate. */
760 if (second_edge
->aux
)
761 *cond
= build2 (TRUTH_AND_EXPR
, boolean_type_node
,
762 *cond
, (tree
) second_edge
->aux
);
764 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
765 *cond
= invert_truthvalue (*cond
);
767 /* Select non loop header bb. */
768 first_edge
= second_edge
;
772 *cond
= (tree
) (first_edge
->src
)->aux
;
774 /* If there is a condition on an incoming edge, add it to the
775 incoming bb predicate. */
777 *cond
= build2 (TRUTH_AND_EXPR
, boolean_type_node
,
778 *cond
, (tree
) first_edge
->aux
);
781 /* Gimplify the condition: the vectorizer prefers to have gimple
782 values as conditions. Various targets use different means to
783 communicate conditions in vector compare operations. Using a
784 gimple value allows the compiler to emit vector compare and
785 select RTL without exposing compare's result. */
786 *cond
= force_gimple_operand_gsi (gsi
, unshare_expr (*cond
),
788 true, GSI_SAME_STMT
);
789 if (!is_gimple_reg (*cond
) && !is_gimple_condexpr (*cond
))
793 new_stmt
= ifc_temp_var (TREE_TYPE (*cond
), unshare_expr (*cond
));
794 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
795 *cond
= gimple_assign_lhs (new_stmt
);
800 return first_edge
->src
;
803 /* Replace PHI node with conditional modify expr using COND. This
804 routine does not handle PHI nodes with more than two arguments.
807 S1: A = PHI <x1(1), x2(5)
809 S2: A = cond ? x1 : x2;
811 The generated code is inserted at GSI that points to the top of
812 basic block's statement list. When COND is true, phi arg from
813 TRUE_BB is selected. */
816 replace_phi_with_cond_gimple_assign_stmt (gimple phi
, tree cond
,
818 gimple_stmt_iterator
*gsi
)
825 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
826 && gimple_phi_num_args (phi
) == 2);
828 bb
= gimple_bb (phi
);
830 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
831 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
833 arg_0
= gimple_phi_arg_def (phi
, 1);
834 arg_1
= gimple_phi_arg_def (phi
, 0);
838 arg_0
= gimple_phi_arg_def (phi
, 0);
839 arg_1
= gimple_phi_arg_def (phi
, 1);
842 /* Build new RHS using selected condition and arguments. */
843 rhs
= build3 (COND_EXPR
, TREE_TYPE (PHI_RESULT (phi
)),
844 unshare_expr (cond
), unshare_expr (arg_0
),
845 unshare_expr (arg_1
));
847 new_stmt
= gimple_build_assign (unshare_expr (PHI_RESULT (phi
)), rhs
);
848 SSA_NAME_DEF_STMT (gimple_phi_result (phi
)) = new_stmt
;
849 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
850 update_stmt (new_stmt
);
852 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
854 fprintf (dump_file
, "new phi replacement stmt\n");
855 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
859 /* Process phi nodes for the given LOOP. Replace phi nodes with
860 conditional modify expressions. */
863 process_phi_nodes (struct loop
*loop
)
866 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
869 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
872 tree cond
= NULL_TREE
;
873 gimple_stmt_iterator gsi
, phi_gsi
;
874 basic_block true_bb
= NULL
;
877 if (bb
== loop
->header
)
880 phi_gsi
= gsi_start_phis (bb
);
881 gsi
= gsi_after_labels (bb
);
883 /* BB has two predecessors. Using predecessor's aux field, set
884 appropriate condition for the PHI node replacement. */
885 if (!gsi_end_p (phi_gsi
))
886 true_bb
= find_phi_replacement_condition (loop
, bb
, &cond
, &gsi
);
888 while (!gsi_end_p (phi_gsi
))
890 phi
= gsi_stmt (phi_gsi
);
891 replace_phi_with_cond_gimple_assign_stmt (phi
, cond
, true_bb
, &gsi
);
892 release_phi_node (phi
);
895 set_phi_nodes (bb
, NULL
);
899 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
900 other than the exit and latch of the LOOP. */
903 remove_conditions_and_labels (loop_p loop
)
905 gimple_stmt_iterator gsi
;
908 for (i
= 0; i
< loop
->num_nodes
; i
++)
910 basic_block bb
= ifc_bbs
[i
];
912 if (bb_with_exit_edge_p (loop
, bb
)
913 || bb
== loop
->latch
)
916 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
917 if (gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
918 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_LABEL
)
919 gsi_remove (&gsi
, true);
925 /* Combine all the basic blocks from LOOP into one or two super basic
926 blocks. Replace PHI nodes with conditional modify expressions. */
929 combine_blocks (struct loop
*loop
)
931 basic_block bb
, exit_bb
, merge_target_bb
;
932 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
937 remove_conditions_and_labels (loop
);
939 /* Process phi nodes to prepare blocks for merge. */
940 process_phi_nodes (loop
);
942 /* Merge basic blocks: first remove all the edges in the loop,
943 except for those from the exit block. */
945 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
948 if (bb_with_exit_edge_p (loop
, bb
))
954 gcc_assert (exit_bb
!= loop
->latch
);
956 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
960 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
962 if (e
->src
== exit_bb
)
971 if (exit_bb
!= loop
->header
)
973 /* Connect this node to loop header. */
974 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
975 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
978 /* Redirect non-exit edges to loop->latch. */
979 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
981 if (!loop_exit_edge_p (loop
, e
))
982 redirect_edge_and_branch (e
, loop
->latch
);
984 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
988 /* If the loop does not have an exit, reconnect header and latch. */
989 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
990 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
993 merge_target_bb
= loop
->header
;
994 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
996 gimple_stmt_iterator gsi
;
997 gimple_stmt_iterator last
;
1001 if (bb
== exit_bb
|| bb
== loop
->latch
)
1004 /* Make stmts member of loop->header. */
1005 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1006 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
1008 /* Update stmt list. */
1009 last
= gsi_last_bb (merge_target_bb
);
1010 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
1011 set_bb_seq (bb
, NULL
);
1013 delete_basic_block (bb
);
1016 /* If possible, merge loop header to the block with the exit edge.
1017 This reduces the number of basic blocks to two, to please the
1018 vectorizer that handles only loops with two nodes.
1020 FIXME: Call cleanup_tree_cfg. */
1022 && exit_bb
!= loop
->header
1023 && can_merge_blocks_p (loop
->header
, exit_bb
))
1024 merge_blocks (loop
->header
, exit_bb
);
1027 /* If-convert LOOP when it is legal. For the moment this pass has no
1028 profitability analysis. */
1031 tree_if_conversion (struct loop
*loop
)
1033 gimple_stmt_iterator itr
;
1038 /* If-conversion is not appropriate for all loops. First, check if
1039 the loop is if-convertible. */
1040 if (!if_convertible_loop_p (loop
))
1042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1043 fprintf (dump_file
, "-------------------------\n");
1052 for (i
= 0; i
< loop
->num_nodes
; i
++)
1054 basic_block bb
= ifc_bbs
[i
];
1055 tree cond
= (tree
) bb
->aux
;
1057 /* Predicate basic block(s) with the condition expressions
1058 leading to their execution. */
1059 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); /* empty */)
1061 gimple t
= gsi_stmt (itr
);
1062 cond
= tree_if_convert_stmt (loop
, t
, cond
, &itr
);
1063 if (!gsi_end_p (itr
))
1067 /* If current bb has only one successor, then consider it as an
1068 unconditional goto. */
1069 if (single_succ_p (bb
))
1071 basic_block bb_n
= single_succ (bb
);
1073 /* The successor bb inherits the predicate of its
1074 predecessor. If there is no predicate in the predecessor
1075 bb, then consider the successor bb as always executed. */
1076 if (cond
== NULL_TREE
)
1077 cond
= boolean_true_node
;
1079 add_to_predicate_list (bb_n
, cond
);
1083 /* Now, all statements are if-converted and basic blocks are
1084 annotated appropriately. Combine all the basic blocks into one
1085 huge basic block. */
1086 combine_blocks (loop
);
1089 clean_predicate_lists (loop
);
1094 /* Tree if-conversion pass management. */
1097 main_tree_if_conversion (void)
1102 if (number_of_loops () <= 1)
1105 FOR_EACH_LOOP (li
, loop
, 0)
1106 tree_if_conversion (loop
);
1112 gate_tree_if_conversion (void)
1114 return flag_tree_vectorize
!= 0;
1117 struct gimple_opt_pass pass_if_conversion
=
1122 gate_tree_if_conversion
, /* gate */
1123 main_tree_if_conversion
, /* execute */
1126 0, /* static_pass_number */
1127 TV_NONE
, /* tv_id */
1128 PROP_cfg
| PROP_ssa
, /* properties_required */
1129 0, /* properties_provided */
1130 0, /* properties_destroyed */
1131 0, /* todo_flags_start */
1132 TODO_dump_func
| TODO_verify_stmts
| TODO_verify_flow
1133 /* todo_flags_finish */