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 "tree-pretty-print.h"
93 #include "gimple-pretty-print.h"
94 #include "tree-flow.h"
95 #include "tree-dump.h"
97 #include "tree-chrec.h"
98 #include "tree-data-ref.h"
99 #include "tree-scalar-evolution.h"
100 #include "tree-pass.h"
102 /* List of basic blocks in if-conversion-suitable order. */
103 static basic_block
*ifc_bbs
;
105 /* Structure used to predicate basic blocks. This is attached to the
106 ->aux field of the BBs in the loop to be if-converted. */
107 typedef struct bb_predicate_s
{
109 /* The condition under which this basic block is executed. */
112 /* PREDICATE is gimplified, and the sequence of statements is
113 recorded here, in order to avoid the duplication of computations
114 that occur in previous conditions. See PR44483. */
115 gimple_seq predicate_gimplified_stmts
;
118 /* Returns true when the basic block BB has a predicate. */
121 bb_has_predicate (basic_block bb
)
123 return bb
->aux
!= NULL
;
126 /* Returns the gimplified predicate for basic block BB. */
129 bb_predicate (basic_block bb
)
131 return ((bb_predicate_p
) bb
->aux
)->predicate
;
134 /* Sets the gimplified predicate COND for basic block BB. */
137 set_bb_predicate (basic_block bb
, tree cond
)
139 ((bb_predicate_p
) bb
->aux
)->predicate
= cond
;
142 /* Returns the sequence of statements of the gimplification of the
143 predicate for basic block BB. */
145 static inline gimple_seq
146 bb_predicate_gimplified_stmts (basic_block bb
)
148 return ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
;
151 /* Sets the sequence of statements STMTS of the gimplification of the
152 predicate for basic block BB. */
155 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
157 ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
160 /* Adds the sequence of statements STMTS to the sequence of statements
161 of the predicate for basic block BB. */
164 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
167 (&(((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
170 /* Initializes to TRUE the predicate of basic block BB. */
173 init_bb_predicate (basic_block bb
)
175 bb
->aux
= XNEW (struct bb_predicate_s
);
176 set_bb_predicate_gimplified_stmts (bb
, NULL
);
177 set_bb_predicate (bb
, NULL_TREE
);
180 /* Free the predicate of basic block BB. */
183 free_bb_predicate (basic_block bb
)
187 if (!bb_has_predicate (bb
))
190 /* Release the SSA_NAMEs created for the gimplification of the
192 stmts
= bb_predicate_gimplified_stmts (bb
);
195 gimple_stmt_iterator i
;
197 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
198 free_stmt_operands (gsi_stmt (i
));
205 /* Create a new temp variable of type TYPE. Add GIMPLE_ASSIGN to assign EXP
206 to the new variable. */
209 ifc_temp_var (tree type
, tree exp
)
211 const char *name
= "_ifc_";
215 /* Create new temporary variable. */
216 var
= create_tmp_var (type
, name
);
217 add_referenced_var (var
);
219 /* Build new statement to assign EXP to new variable. */
220 stmt
= gimple_build_assign (var
, exp
);
222 /* Get SSA name for the new variable and set make new statement
223 its definition statement. */
224 new_name
= make_ssa_name (var
, stmt
);
225 gimple_assign_set_lhs (stmt
, new_name
);
226 SSA_NAME_DEF_STMT (new_name
) = stmt
;
232 /* Return true when COND is a true predicate. */
235 is_true_predicate (tree cond
)
237 return (cond
== NULL_TREE
238 || cond
== boolean_true_node
239 || integer_onep (cond
));
242 /* Returns true when BB has a predicate that is not trivial: true or
246 is_predicated (basic_block bb
)
248 return !is_true_predicate (bb_predicate (bb
));
251 /* Add condition NEW_COND to the predicate list of basic block BB. */
254 add_to_predicate_list (basic_block bb
, tree new_cond
)
256 tree cond
= bb_predicate (bb
);
258 set_bb_predicate (bb
, is_true_predicate (cond
) ? new_cond
:
259 fold_build2_loc (EXPR_LOCATION (cond
),
260 TRUTH_OR_EXPR
, boolean_type_node
,
264 /* Add the condition COND to the previous condition PREV_COND, and add
265 this to the predicate list of the destination of edge E. LOOP is
266 the loop to be if-converted. */
269 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
270 tree prev_cond
, tree cond
)
272 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
275 if (!is_true_predicate (prev_cond
))
276 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
279 add_to_predicate_list (e
->dest
, cond
);
282 /* Return true if one of the successor edges of BB exits LOOP. */
285 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
290 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
291 if (loop_exit_edge_p (loop
, e
))
297 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
298 and it belongs to basic block BB.
300 PHI is not if-convertible if:
301 - it has more than 2 arguments,
302 - virtual PHI is immediately used in another PHI node,
303 - virtual PHI on BB other than header. */
306 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gimple phi
)
308 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
310 fprintf (dump_file
, "-------------------------\n");
311 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
314 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
316 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
317 fprintf (dump_file
, "More than two phi node args.\n");
321 if (!is_gimple_reg (SSA_NAME_VAR (gimple_phi_result (phi
))))
323 imm_use_iterator imm_iter
;
326 if (bb
!= loop
->header
)
328 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
329 fprintf (dump_file
, "Virtual phi not on loop header.\n");
332 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
334 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
337 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
346 /* Return true when STMT is if-convertible.
348 GIMPLE_ASSIGN statement is not if-convertible if,
351 - LHS is not var decl.
353 GIMPLE_ASSIGN is part of block BB, which is inside loop LOOP. */
356 if_convertible_gimple_assign_stmt_p (struct loop
*loop
, basic_block bb
,
359 tree lhs
= gimple_assign_lhs (stmt
);
361 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
363 fprintf (dump_file
, "-------------------------\n");
364 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
367 /* Some of these constrains might be too conservative. */
368 if (stmt_ends_bb_p (stmt
)
369 || gimple_has_volatile_ops (stmt
)
370 || (TREE_CODE (lhs
) == SSA_NAME
371 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
372 || gimple_has_side_effects (stmt
))
374 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
375 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
379 if (gimple_assign_rhs_could_trap_p (stmt
))
381 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
382 fprintf (dump_file
, "tree could trap...\n");
386 if (TREE_CODE (lhs
) != SSA_NAME
387 && bb
!= loop
->header
388 && !bb_with_exit_edge_p (loop
, bb
))
390 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
392 fprintf (dump_file
, "LHS is not var\n");
393 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
401 /* Return true when STMT is if-convertible.
403 A statement is if-convertible if:
404 - it is an if-convertible GIMPLE_ASSGIN,
405 - it is a GIMPLE_LABEL or a GIMPLE_COND.
407 STMT is inside BB, which is inside loop LOOP. */
410 if_convertible_stmt_p (struct loop
*loop
, basic_block bb
, gimple stmt
)
412 switch (gimple_code (stmt
))
420 return if_convertible_gimple_assign_stmt_p (loop
, bb
, stmt
);
423 /* Don't know what to do with 'em so don't do anything. */
424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
426 fprintf (dump_file
, "don't know what to do\n");
427 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
436 /* Return true when BB is if-convertible. This routine does not check
437 basic block's statements and phis.
439 A basic block is not if-convertible if:
440 - it is non-empty and it is after the exit block (in BFS order),
441 - it is after the exit block but before the latch,
442 - its edges are not normal.
444 EXIT_BB is the basic block containing the exit of the LOOP. BB is
448 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
453 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
454 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
456 if (EDGE_COUNT (bb
->preds
) > 2
457 || EDGE_COUNT (bb
->succs
) > 2)
462 if (bb
!= loop
->latch
)
464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
465 fprintf (dump_file
, "basic block after exit bb but before latch\n");
468 else if (!empty_block_p (bb
))
470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
471 fprintf (dump_file
, "non empty basic block after exit bb\n");
474 else if (bb
== loop
->latch
476 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
478 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
479 fprintf (dump_file
, "latch is not dominated by exit_block\n");
484 /* Be less adventurous and handle only normal edges. */
485 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
487 (EDGE_ABNORMAL_CALL
| EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
489 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
490 fprintf (dump_file
, "Difficult to handle edges\n");
497 /* Return true when all predecessor blocks of BB are visited. The
498 VISITED bitmap keeps track of the visited blocks. */
501 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
505 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
506 if (!bitmap_bit_p (*visited
, e
->src
->index
))
512 /* Get body of a LOOP in suitable order for if-conversion. It is
513 caller's responsibility to deallocate basic block list.
514 If-conversion suitable order is, breadth first sort (BFS) order
515 with an additional constraint: select a block only if all its
516 predecessors are already selected. */
519 get_loop_body_in_if_conv_order (const struct loop
*loop
)
521 basic_block
*blocks
, *blocks_in_bfs_order
;
524 unsigned int index
= 0;
525 unsigned int visited_count
= 0;
527 gcc_assert (loop
->num_nodes
);
528 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
530 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
531 visited
= BITMAP_ALLOC (NULL
);
533 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
536 while (index
< loop
->num_nodes
)
538 bb
= blocks_in_bfs_order
[index
];
540 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
542 free (blocks_in_bfs_order
);
543 BITMAP_FREE (visited
);
548 if (!bitmap_bit_p (visited
, bb
->index
))
550 if (pred_blocks_visited_p (bb
, &visited
)
551 || bb
== loop
->header
)
553 /* This block is now visited. */
554 bitmap_set_bit (visited
, bb
->index
);
555 blocks
[visited_count
++] = bb
;
561 if (index
== loop
->num_nodes
562 && visited_count
!= loop
->num_nodes
)
566 free (blocks_in_bfs_order
);
567 BITMAP_FREE (visited
);
571 /* Returns true when the analysis of the predicates for all the basic
572 blocks in LOOP succeeded.
574 predicate_bbs first allocates the predicates of the basic blocks.
575 These fields are then initialized with the tree expressions
576 representing the predicates under which a basic block is executed
577 in the LOOP. As the loop->header is executed at each iteration, it
578 has the "true" predicate. Other statements executed under a
579 condition are predicated with that condition, for example
586 S1 will be predicated with "x", and
587 S2 will be predicated with "!x". */
590 predicate_bbs (loop_p loop
)
594 for (i
= 0; i
< loop
->num_nodes
; i
++)
595 init_bb_predicate (ifc_bbs
[i
]);
597 for (i
= 0; i
< loop
->num_nodes
; i
++)
599 basic_block bb
= ifc_bbs
[i
];
601 gimple_stmt_iterator itr
;
603 /* The loop latch is always executed and has no extra conditions
604 to be processed: skip it. */
605 if (bb
== loop
->latch
)
607 set_bb_predicate (loop
->latch
, boolean_true_node
);
608 set_bb_predicate_gimplified_stmts (loop
->latch
, NULL
);
612 cond
= bb_predicate (bb
);
614 && bb
!= loop
->header
)
618 cond
= force_gimple_operand (cond
, &stmts
, true, NULL_TREE
);
619 add_bb_predicate_gimplified_stmts (bb
, stmts
);
622 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
624 gimple stmt
= gsi_stmt (itr
);
626 switch (gimple_code (stmt
))
637 edge true_edge
, false_edge
;
638 location_t loc
= gimple_location (stmt
);
639 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
),
641 gimple_cond_lhs (stmt
),
642 gimple_cond_rhs (stmt
));
644 /* Add new condition into destination's predicate list. */
645 extract_true_false_edges_from_block (gimple_bb (stmt
),
646 &true_edge
, &false_edge
);
648 /* If C is true, then TRUE_EDGE is taken. */
649 add_to_dst_predicate_list (loop
, true_edge
, cond
, c
);
651 /* If C is false, then FALSE_EDGE is taken. */
652 c2
= invert_truthvalue_loc (loc
, unshare_expr (c
));
653 add_to_dst_predicate_list (loop
, false_edge
, cond
, c2
);
660 /* Not handled yet in if-conversion. */
665 /* If current bb has only one successor, then consider it as an
666 unconditional goto. */
667 if (single_succ_p (bb
))
669 basic_block bb_n
= single_succ (bb
);
671 /* The successor bb inherits the predicate of its
672 predecessor. If there is no predicate in the predecessor
673 bb, then consider the successor bb as always executed. */
674 if (cond
== NULL_TREE
)
675 cond
= boolean_true_node
;
677 add_to_predicate_list (bb_n
, cond
);
681 /* The loop header is always executed. */
682 set_bb_predicate (loop
->header
, boolean_true_node
);
683 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
684 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
689 /* Return true when LOOP is if-convertible.
690 LOOP is if-convertible if:
692 - it has two or more basic blocks,
693 - it has only one exit,
694 - loop header is not the exit edge,
695 - if its basic blocks and phi nodes are if convertible. */
698 if_convertible_loop_p (struct loop
*loop
)
703 basic_block exit_bb
= NULL
;
705 /* Handle only innermost loop. */
706 if (!loop
|| loop
->inner
)
708 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
709 fprintf (dump_file
, "not innermost loop\n");
713 /* If only one block, no need for if-conversion. */
714 if (loop
->num_nodes
<= 2)
716 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
717 fprintf (dump_file
, "less than 2 basic blocks\n");
721 /* More than one loop exit is too much to handle. */
722 if (!single_exit (loop
))
724 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
725 fprintf (dump_file
, "multiple exits\n");
729 /* ??? Check target's vector conditional operation support for vectorizer. */
731 /* If one of the loop header's edge is exit edge then do not apply
733 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
735 if (loop_exit_edge_p (loop
, e
))
739 /* Don't if-convert the loop when the data dependences cannot be
740 computed: the loop won't be vectorized in that case. */
742 VEC (data_reference_p
, heap
) *refs
= VEC_alloc (data_reference_p
, heap
, 5);
743 VEC (ddr_p
, heap
) *ddrs
= VEC_alloc (ddr_p
, heap
, 25);
744 bool res
= compute_data_dependences_for_loop (loop
, true, &refs
, &ddrs
);
746 free_data_refs (refs
);
747 free_dependence_relations (ddrs
);
753 calculate_dominance_info (CDI_DOMINATORS
);
755 /* Allow statements that can be handled during if-conversion. */
756 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
759 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
760 fprintf (dump_file
, "Irreducible loop\n");
764 for (i
= 0; i
< loop
->num_nodes
; i
++)
766 basic_block bb
= ifc_bbs
[i
];
768 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
771 if (bb_with_exit_edge_p (loop
, bb
))
775 if (!predicate_bbs (loop
))
778 for (i
= 0; i
< loop
->num_nodes
; i
++)
780 basic_block bb
= ifc_bbs
[i
];
781 gimple_stmt_iterator itr
;
783 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
784 if (!if_convertible_phi_p (loop
, bb
, gsi_stmt (itr
)))
787 /* For non predicated BBs, don't check their statements. */
788 if (!is_predicated (bb
))
791 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
792 if (!if_convertible_stmt_p (loop
, bb
, gsi_stmt (itr
)))
797 fprintf (dump_file
, "Applying if-conversion\n");
802 /* Basic block BB has two predecessors. Using predecessor's bb
803 predicate, set an appropriate condition COND for the PHI node
804 replacement. Return the true block whose phi arguments are
805 selected when cond is true. LOOP is the loop containing the
806 if-converted region, GSI is the place to insert the code for the
810 find_phi_replacement_condition (struct loop
*loop
,
811 basic_block bb
, tree
*cond
,
812 gimple_stmt_iterator
*gsi
)
814 edge first_edge
, second_edge
;
817 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
818 first_edge
= EDGE_PRED (bb
, 0);
819 second_edge
= EDGE_PRED (bb
, 1);
821 /* Use condition based on following criteria:
827 S2 is preferred over S1. Make 'b' first_bb and use its condition.
829 2) Do not make loop header first_bb.
832 S1: x = !(c == d)? a : b;
837 S3: x = (c == d) ? b : a;
839 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
842 4) If pred B is dominated by pred A then use pred B's condition.
845 /* Select condition that is not TRUTH_NOT_EXPR. */
846 tmp_cond
= bb_predicate (first_edge
->src
);
847 gcc_assert (tmp_cond
);
849 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
853 tmp_edge
= first_edge
;
854 first_edge
= second_edge
;
855 second_edge
= tmp_edge
;
858 /* Check if FIRST_BB is loop header or not and make sure that
859 FIRST_BB does not dominate SECOND_BB. */
860 if (first_edge
->src
== loop
->header
861 || dominated_by_p (CDI_DOMINATORS
,
862 second_edge
->src
, first_edge
->src
))
864 *cond
= bb_predicate (second_edge
->src
);
866 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
867 *cond
= invert_truthvalue (*cond
);
869 /* Select non loop header bb. */
870 first_edge
= second_edge
;
873 *cond
= bb_predicate (first_edge
->src
);
875 /* Gimplify the condition: the vectorizer prefers to have gimple
876 values as conditions. Various targets use different means to
877 communicate conditions in vector compare operations. Using a
878 gimple value allows the compiler to emit vector compare and
879 select RTL without exposing compare's result. */
880 *cond
= force_gimple_operand_gsi (gsi
, unshare_expr (*cond
),
882 true, GSI_SAME_STMT
);
883 if (!is_gimple_reg (*cond
) && !is_gimple_condexpr (*cond
))
887 new_stmt
= ifc_temp_var (TREE_TYPE (*cond
), unshare_expr (*cond
));
888 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
889 *cond
= gimple_assign_lhs (new_stmt
);
894 return first_edge
->src
;
897 /* Replace PHI node with conditional modify expr using COND. This
898 routine does not handle PHI nodes with more than two arguments.
901 S1: A = PHI <x1(1), x2(5)
903 S2: A = cond ? x1 : x2;
905 The generated code is inserted at GSI that points to the top of
906 basic block's statement list. When COND is true, phi arg from
907 TRUE_BB is selected. */
910 replace_phi_with_cond_gimple_assign_stmt (gimple phi
, tree cond
,
912 gimple_stmt_iterator
*gsi
)
919 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
920 && gimple_phi_num_args (phi
) == 2);
922 bb
= gimple_bb (phi
);
924 arg
= degenerate_phi_result (phi
);
930 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
931 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
933 arg_0
= gimple_phi_arg_def (phi
, 1);
934 arg_1
= gimple_phi_arg_def (phi
, 0);
938 arg_0
= gimple_phi_arg_def (phi
, 0);
939 arg_1
= gimple_phi_arg_def (phi
, 1);
942 /* Build new RHS using selected condition and arguments. */
943 rhs
= build3 (COND_EXPR
, TREE_TYPE (PHI_RESULT (phi
)),
944 unshare_expr (cond
), arg_0
, arg_1
);
947 new_stmt
= gimple_build_assign (PHI_RESULT (phi
), rhs
);
948 SSA_NAME_DEF_STMT (gimple_phi_result (phi
)) = new_stmt
;
949 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
950 update_stmt (new_stmt
);
952 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
954 fprintf (dump_file
, "new phi replacement stmt\n");
955 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
959 /* Replaces in LOOP all the phi nodes other than those in the
960 LOOP->header block with conditional modify expressions. */
963 ifconvert_phi_nodes (struct loop
*loop
)
966 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
969 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
972 tree cond
= NULL_TREE
;
973 gimple_stmt_iterator gsi
, phi_gsi
;
974 basic_block true_bb
= NULL
;
977 if (bb
== loop
->header
)
980 phi_gsi
= gsi_start_phis (bb
);
981 if (gsi_end_p (phi_gsi
))
984 /* BB has two predecessors. Using predecessor's aux field, set
985 appropriate condition for the PHI node replacement. */
986 gsi
= gsi_after_labels (bb
);
987 true_bb
= find_phi_replacement_condition (loop
, bb
, &cond
, &gsi
);
989 while (!gsi_end_p (phi_gsi
))
991 phi
= gsi_stmt (phi_gsi
);
992 replace_phi_with_cond_gimple_assign_stmt (phi
, cond
, true_bb
, &gsi
);
993 release_phi_node (phi
);
997 set_phi_nodes (bb
, NULL
);
1001 /* Insert in each basic block of LOOP the statements produced by the
1002 gimplification of the predicates. */
1005 insert_gimplified_predicates (loop_p loop
)
1009 for (i
= 0; i
< loop
->num_nodes
; i
++)
1011 basic_block bb
= ifc_bbs
[i
];
1012 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
1016 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1019 || gimple_code (gsi_stmt (gsi
)) == GIMPLE_COND
)
1020 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1022 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1024 /* Once the sequence is code generated, set it to NULL. */
1025 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1030 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1031 other than the exit and latch of the LOOP. Also resets the
1032 GIMPLE_DEBUG information. */
1035 remove_conditions_and_labels (loop_p loop
)
1037 gimple_stmt_iterator gsi
;
1040 for (i
= 0; i
< loop
->num_nodes
; i
++)
1042 basic_block bb
= ifc_bbs
[i
];
1044 if (bb_with_exit_edge_p (loop
, bb
)
1045 || bb
== loop
->latch
)
1048 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1049 switch (gimple_code (gsi_stmt (gsi
)))
1053 gsi_remove (&gsi
, true);
1057 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
1058 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
1060 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
1061 update_stmt (gsi_stmt (gsi
));
1072 /* Combine all the basic blocks from LOOP into one or two super basic
1073 blocks. Replace PHI nodes with conditional modify expressions. */
1076 combine_blocks (struct loop
*loop
)
1078 basic_block bb
, exit_bb
, merge_target_bb
;
1079 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1084 remove_conditions_and_labels (loop
);
1085 insert_gimplified_predicates (loop
);
1086 ifconvert_phi_nodes (loop
);
1088 /* Merge basic blocks: first remove all the edges in the loop,
1089 except for those from the exit block. */
1091 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
1094 if (bb_with_exit_edge_p (loop
, bb
))
1100 gcc_assert (exit_bb
!= loop
->latch
);
1102 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1106 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
1108 if (e
->src
== exit_bb
)
1115 if (exit_bb
!= NULL
)
1117 if (exit_bb
!= loop
->header
)
1119 /* Connect this node to loop header. */
1120 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
1121 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
1124 /* Redirect non-exit edges to loop->latch. */
1125 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
1127 if (!loop_exit_edge_p (loop
, e
))
1128 redirect_edge_and_branch (e
, loop
->latch
);
1130 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
1134 /* If the loop does not have an exit, reconnect header and latch. */
1135 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
1136 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
1139 merge_target_bb
= loop
->header
;
1140 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1142 gimple_stmt_iterator gsi
;
1143 gimple_stmt_iterator last
;
1147 if (bb
== exit_bb
|| bb
== loop
->latch
)
1150 /* Make stmts member of loop->header. */
1151 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1152 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
1154 /* Update stmt list. */
1155 last
= gsi_last_bb (merge_target_bb
);
1156 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
1157 set_bb_seq (bb
, NULL
);
1159 delete_basic_block (bb
);
1162 /* If possible, merge loop header to the block with the exit edge.
1163 This reduces the number of basic blocks to two, to please the
1164 vectorizer that handles only loops with two nodes.
1166 FIXME: Call cleanup_tree_cfg. */
1168 && exit_bb
!= loop
->header
1169 && can_merge_blocks_p (loop
->header
, exit_bb
))
1170 merge_blocks (loop
->header
, exit_bb
);
1173 /* If-convert LOOP when it is legal. For the moment this pass has no
1174 profitability analysis. */
1177 tree_if_conversion (struct loop
*loop
)
1181 if (!if_convertible_loop_p (loop
))
1184 /* Now all statements are if-convertible. Combine all the basic
1185 blocks into one huge basic block doing the if-conversion
1187 combine_blocks (loop
);
1194 for (i
= 0; i
< loop
->num_nodes
; i
++)
1195 free_bb_predicate (ifc_bbs
[i
]);
1202 /* Tree if-conversion pass management. */
1205 main_tree_if_conversion (void)
1210 if (number_of_loops () <= 1)
1213 FOR_EACH_LOOP (li
, loop
, 0)
1214 tree_if_conversion (loop
);
1220 gate_tree_if_conversion (void)
1222 return flag_tree_vectorize
!= 0;
1225 struct gimple_opt_pass pass_if_conversion
=
1230 gate_tree_if_conversion
, /* gate */
1231 main_tree_if_conversion
, /* execute */
1234 0, /* static_pass_number */
1235 TV_NONE
, /* tv_id */
1236 PROP_cfg
| PROP_ssa
, /* properties_required */
1237 0, /* properties_provided */
1238 0, /* properties_destroyed */
1239 0, /* todo_flags_start */
1240 TODO_dump_func
| TODO_verify_stmts
| TODO_verify_flow
1241 /* todo_flags_finish */