1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
3 Contributed by Devang Patel <dpatel@apple.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass implements a tree level if-conversion of loops. Its
22 initial goal is to help the vectorizer to vectorize loops with
25 A short description of if-conversion:
27 o Decide if a loop is if-convertible or not.
28 o Walk all loop basic blocks in breadth first order (BFS order).
29 o Remove conditional statements (at the end of basic block)
30 and propagate condition into destination basic blocks'
32 o Replace modify expression with conditional modify expression
33 using current basic block's condition.
34 o Merge all basic blocks
35 o Replace phi nodes with conditional modify expr
36 o Merge all basic blocks into header
38 Sample transformation:
43 # i_23 = PHI <0(0), i_18(10)>;
46 if (j_15 > 41) goto <L1>; else goto <L17>;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
67 # i_23 = PHI <0(0), i_18(10)>;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
85 #include "coretypes.h"
88 #include "stor-layout.h"
90 #include "basic-block.h"
91 #include "gimple-pretty-print.h"
92 #include "tree-ssa-alias.h"
93 #include "internal-fn.h"
94 #include "gimple-fold.h"
95 #include "gimple-expr.h"
99 #include "gimple-iterator.h"
100 #include "gimplify-me.h"
101 #include "gimple-ssa.h"
102 #include "tree-cfg.h"
103 #include "tree-phinodes.h"
104 #include "ssa-iterators.h"
105 #include "stringpool.h"
106 #include "tree-ssanames.h"
107 #include "tree-into-ssa.h"
108 #include "tree-ssa.h"
110 #include "tree-chrec.h"
111 #include "tree-data-ref.h"
112 #include "tree-scalar-evolution.h"
113 #include "tree-ssa-loop-ivopts.h"
114 #include "tree-ssa-address.h"
115 #include "tree-pass.h"
120 /* List of basic blocks in if-conversion-suitable order. */
121 static basic_block
*ifc_bbs
;
123 /* Structure used to predicate basic blocks. This is attached to the
124 ->aux field of the BBs in the loop to be if-converted. */
125 typedef struct bb_predicate_s
{
127 /* The condition under which this basic block is executed. */
130 /* PREDICATE is gimplified, and the sequence of statements is
131 recorded here, in order to avoid the duplication of computations
132 that occur in previous conditions. See PR44483. */
133 gimple_seq predicate_gimplified_stmts
;
136 /* Returns true when the basic block BB has a predicate. */
139 bb_has_predicate (basic_block bb
)
141 return bb
->aux
!= NULL
;
144 /* Returns the gimplified predicate for basic block BB. */
147 bb_predicate (basic_block bb
)
149 return ((bb_predicate_p
) bb
->aux
)->predicate
;
152 /* Sets the gimplified predicate COND for basic block BB. */
155 set_bb_predicate (basic_block bb
, tree cond
)
157 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
158 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
159 || is_gimple_condexpr (cond
));
160 ((bb_predicate_p
) bb
->aux
)->predicate
= cond
;
163 /* Returns the sequence of statements of the gimplification of the
164 predicate for basic block BB. */
166 static inline gimple_seq
167 bb_predicate_gimplified_stmts (basic_block bb
)
169 return ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
;
172 /* Sets the sequence of statements STMTS of the gimplification of the
173 predicate for basic block BB. */
176 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
178 ((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
181 /* Adds the sequence of statements STMTS to the sequence of statements
182 of the predicate for basic block BB. */
185 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
188 (&(((bb_predicate_p
) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
191 /* Initializes to TRUE the predicate of basic block BB. */
194 init_bb_predicate (basic_block bb
)
196 bb
->aux
= XNEW (struct bb_predicate_s
);
197 set_bb_predicate_gimplified_stmts (bb
, NULL
);
198 set_bb_predicate (bb
, boolean_true_node
);
201 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
202 but don't actually free it. */
205 release_bb_predicate (basic_block bb
)
207 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
210 gimple_stmt_iterator i
;
212 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
213 free_stmt_operands (cfun
, gsi_stmt (i
));
214 set_bb_predicate_gimplified_stmts (bb
, NULL
);
218 /* Free the predicate of basic block BB. */
221 free_bb_predicate (basic_block bb
)
223 if (!bb_has_predicate (bb
))
226 release_bb_predicate (bb
);
231 /* Reinitialize predicate of BB with the true predicate. */
234 reset_bb_predicate (basic_block bb
)
236 if (!bb_has_predicate (bb
))
237 init_bb_predicate (bb
);
240 release_bb_predicate (bb
);
241 set_bb_predicate (bb
, boolean_true_node
);
245 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
246 the expression EXPR. Inserts the statement created for this
247 computation before GSI and leaves the iterator GSI at the same
251 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
253 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
254 gimple stmt
= gimple_build_assign (new_name
, expr
);
255 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
259 /* Return true when COND is a true predicate. */
262 is_true_predicate (tree cond
)
264 return (cond
== NULL_TREE
265 || cond
== boolean_true_node
266 || integer_onep (cond
));
269 /* Returns true when BB has a predicate that is not trivial: true or
273 is_predicated (basic_block bb
)
275 return !is_true_predicate (bb_predicate (bb
));
278 /* Parses the predicate COND and returns its comparison code and
279 operands OP0 and OP1. */
281 static enum tree_code
282 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
286 if (TREE_CODE (cond
) == SSA_NAME
287 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
289 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
291 *op0
= gimple_assign_rhs1 (s
);
292 *op1
= gimple_assign_rhs2 (s
);
293 return gimple_assign_rhs_code (s
);
296 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
298 tree op
= gimple_assign_rhs1 (s
);
299 tree type
= TREE_TYPE (op
);
300 enum tree_code code
= parse_predicate (op
, op0
, op1
);
302 return code
== ERROR_MARK
? ERROR_MARK
303 : invert_tree_comparison (code
, HONOR_NANS (TYPE_MODE (type
)));
309 if (TREE_CODE_CLASS (TREE_CODE (cond
)) == tcc_comparison
)
311 *op0
= TREE_OPERAND (cond
, 0);
312 *op1
= TREE_OPERAND (cond
, 1);
313 return TREE_CODE (cond
);
319 /* Returns the fold of predicate C1 OR C2 at location LOC. */
322 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
324 tree op1a
, op1b
, op2a
, op2b
;
325 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
326 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
328 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
330 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
336 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
339 /* Returns true if N is either a constant or a SSA_NAME. */
342 constant_or_ssa_name (tree n
)
344 switch (TREE_CODE (n
))
357 /* Returns either a COND_EXPR or the folded expression if the folded
358 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
359 a constant or a SSA_NAME. */
362 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
364 tree rhs1
, lhs1
, cond_expr
;
365 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
368 if (cond_expr
== NULL_TREE
)
369 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
371 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
373 if (constant_or_ssa_name (cond_expr
))
376 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
378 rhs1
= TREE_OPERAND (cond_expr
, 1);
379 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
380 if (constant_or_ssa_name (rhs1
))
381 return build1 (ABS_EXPR
, type
, rhs1
);
384 if (TREE_CODE (cond_expr
) == MIN_EXPR
385 || TREE_CODE (cond_expr
) == MAX_EXPR
)
387 lhs1
= TREE_OPERAND (cond_expr
, 0);
388 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
389 rhs1
= TREE_OPERAND (cond_expr
, 1);
390 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
391 if (constant_or_ssa_name (rhs1
)
392 && constant_or_ssa_name (lhs1
))
393 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
395 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
398 /* Add condition NC to the predicate list of basic block BB. LOOP is
399 the loop to be if-converted. */
402 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
406 if (is_true_predicate (nc
))
409 if (!is_predicated (bb
))
411 /* If dominance tells us this basic block is always executed, don't
412 record any predicates for it. */
413 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
420 bc
= bb_predicate (bb
);
421 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
422 if (is_true_predicate (bc
))
424 reset_bb_predicate (bb
);
429 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
430 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
431 tp
= &TREE_OPERAND (bc
, 0);
434 if (!is_gimple_condexpr (*tp
))
437 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
438 add_bb_predicate_gimplified_stmts (bb
, stmts
);
440 set_bb_predicate (bb
, bc
);
443 /* Add the condition COND to the previous condition PREV_COND, and add
444 this to the predicate list of the destination of edge E. LOOP is
445 the loop to be if-converted. */
448 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
449 tree prev_cond
, tree cond
)
451 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
454 if (!is_true_predicate (prev_cond
))
455 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
458 add_to_predicate_list (loop
, e
->dest
, cond
);
461 /* Return true if one of the successor edges of BB exits LOOP. */
464 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
469 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
470 if (loop_exit_edge_p (loop
, e
))
476 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
477 and it belongs to basic block BB.
479 PHI is not if-convertible if:
480 - it has more than 2 arguments.
482 When the flag_tree_loop_if_convert_stores is not set, PHI is not
484 - a virtual PHI is immediately used in another PHI node,
485 - there is a virtual PHI in a BB other than the loop->header. */
488 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gimple phi
,
489 bool any_mask_load_store
)
491 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
493 fprintf (dump_file
, "-------------------------\n");
494 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
497 if (bb
!= loop
->header
&& gimple_phi_num_args (phi
) != 2)
499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
500 fprintf (dump_file
, "More than two phi node args.\n");
504 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
507 /* When the flag_tree_loop_if_convert_stores is not set, check
508 that there are no memory writes in the branches of the loop to be
510 if (virtual_operand_p (gimple_phi_result (phi
)))
512 imm_use_iterator imm_iter
;
515 if (bb
!= loop
->header
)
517 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
518 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
522 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
524 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
)
526 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
527 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
536 /* Records the status of a data reference. This struct is attached to
537 each DR->aux field. */
540 /* -1 when not initialized, 0 when false, 1 when true. */
541 int written_at_least_once
;
543 /* -1 when not initialized, 0 when false, 1 when true. */
544 int rw_unconditionally
;
547 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
548 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
549 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
551 /* Returns true when the memory references of STMT are read or written
552 unconditionally. In other words, this function returns true when
553 for every data reference A in STMT there exist other accesses to
554 a data reference with the same base with predicates that add up (OR-up) to
555 the true predicate: this ensures that the data reference A is touched
556 (read or written) on every iteration of the if-converted loop. */
559 memrefs_read_or_written_unconditionally (gimple stmt
,
560 vec
<data_reference_p
> drs
)
563 data_reference_p a
, b
;
564 tree ca
= bb_predicate (gimple_bb (stmt
));
566 for (i
= 0; drs
.iterate (i
, &a
); i
++)
567 if (DR_STMT (a
) == stmt
)
570 int x
= DR_RW_UNCONDITIONALLY (a
);
578 for (j
= 0; drs
.iterate (j
, &b
); j
++)
580 tree ref_base_a
= DR_REF (a
);
581 tree ref_base_b
= DR_REF (b
);
583 if (DR_STMT (b
) == stmt
)
586 while (TREE_CODE (ref_base_a
) == COMPONENT_REF
587 || TREE_CODE (ref_base_a
) == IMAGPART_EXPR
588 || TREE_CODE (ref_base_a
) == REALPART_EXPR
)
589 ref_base_a
= TREE_OPERAND (ref_base_a
, 0);
591 while (TREE_CODE (ref_base_b
) == COMPONENT_REF
592 || TREE_CODE (ref_base_b
) == IMAGPART_EXPR
593 || TREE_CODE (ref_base_b
) == REALPART_EXPR
)
594 ref_base_b
= TREE_OPERAND (ref_base_b
, 0);
596 if (!operand_equal_p (ref_base_a
, ref_base_b
, 0))
598 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
600 if (DR_RW_UNCONDITIONALLY (b
) == 1
601 || is_true_predicate (cb
)
602 || is_true_predicate (ca
603 = fold_or_predicates (EXPR_LOCATION (cb
), ca
, cb
)))
605 DR_RW_UNCONDITIONALLY (a
) = 1;
606 DR_RW_UNCONDITIONALLY (b
) = 1;
615 DR_RW_UNCONDITIONALLY (a
) = 0;
623 /* Returns true when the memory references of STMT are unconditionally
624 written. In other words, this function returns true when for every
625 data reference A written in STMT, there exist other writes to the
626 same data reference with predicates that add up (OR-up) to the true
627 predicate: this ensures that the data reference A is written on
628 every iteration of the if-converted loop. */
631 write_memrefs_written_at_least_once (gimple stmt
,
632 vec
<data_reference_p
> drs
)
635 data_reference_p a
, b
;
636 tree ca
= bb_predicate (gimple_bb (stmt
));
638 for (i
= 0; drs
.iterate (i
, &a
); i
++)
639 if (DR_STMT (a
) == stmt
643 int x
= DR_WRITTEN_AT_LEAST_ONCE (a
);
651 for (j
= 0; drs
.iterate (j
, &b
); j
++)
652 if (DR_STMT (b
) != stmt
654 && same_data_refs_base_objects (a
, b
))
656 tree cb
= bb_predicate (gimple_bb (DR_STMT (b
)));
658 if (DR_WRITTEN_AT_LEAST_ONCE (b
) == 1
659 || is_true_predicate (cb
)
660 || is_true_predicate (ca
= fold_or_predicates (EXPR_LOCATION (cb
),
663 DR_WRITTEN_AT_LEAST_ONCE (a
) = 1;
664 DR_WRITTEN_AT_LEAST_ONCE (b
) = 1;
672 DR_WRITTEN_AT_LEAST_ONCE (a
) = 0;
680 /* Return true when the memory references of STMT won't trap in the
681 if-converted code. There are two things that we have to check for:
683 - writes to memory occur to writable memory: if-conversion of
684 memory writes transforms the conditional memory writes into
685 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
686 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
687 be executed at all in the original code, it may be a readonly
688 memory. To check that A is not const-qualified, we check that
689 there exists at least an unconditional write to A in the current
692 - reads or writes to memory are valid memory accesses for every
693 iteration. To check that the memory accesses are correctly formed
694 and that we are allowed to read and write in these locations, we
695 check that the memory accesses to be if-converted occur at every
696 iteration unconditionally. */
699 ifcvt_memrefs_wont_trap (gimple stmt
, vec
<data_reference_p
> refs
)
701 return write_memrefs_written_at_least_once (stmt
, refs
)
702 && memrefs_read_or_written_unconditionally (stmt
, refs
);
705 /* Wrapper around gimple_could_trap_p refined for the needs of the
706 if-conversion. Try to prove that the memory accesses of STMT could
707 not trap in the innermost loop containing STMT. */
710 ifcvt_could_trap_p (gimple stmt
, vec
<data_reference_p
> refs
)
712 if (gimple_vuse (stmt
)
713 && !gimple_could_trap_p_1 (stmt
, false, false)
714 && ifcvt_memrefs_wont_trap (stmt
, refs
))
717 return gimple_could_trap_p (stmt
);
720 /* Return true if STMT could be converted into a masked load or store
721 (conditional load or store based on a mask computed from bb predicate). */
724 ifcvt_can_use_mask_load_store (gimple stmt
)
727 enum machine_mode mode
;
728 basic_block bb
= gimple_bb (stmt
);
731 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
732 || bb
->loop_father
->dont_vectorize
733 || !gimple_assign_single_p (stmt
)
734 || gimple_has_volatile_ops (stmt
))
737 /* Check whether this is a load or store. */
738 lhs
= gimple_assign_lhs (stmt
);
739 if (gimple_store_p (stmt
))
741 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
746 else if (gimple_assign_load_p (stmt
))
749 ref
= gimple_assign_rhs1 (stmt
);
754 if (may_be_nonaddressable_p (ref
))
757 /* Mask should be integer mode of the same size as the load/store
759 mode
= TYPE_MODE (TREE_TYPE (lhs
));
760 if (int_mode_for_mode (mode
) == BLKmode
761 || VECTOR_MODE_P (mode
))
764 if (can_vec_mask_load_store_p (mode
, is_load
))
770 /* Return true when STMT is if-convertible.
772 GIMPLE_ASSIGN statement is not if-convertible if,
775 - LHS is not var decl. */
778 if_convertible_gimple_assign_stmt_p (gimple stmt
,
779 vec
<data_reference_p
> refs
,
780 bool *any_mask_load_store
)
782 tree lhs
= gimple_assign_lhs (stmt
);
785 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
787 fprintf (dump_file
, "-------------------------\n");
788 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
791 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
794 /* Some of these constrains might be too conservative. */
795 if (stmt_ends_bb_p (stmt
)
796 || gimple_has_volatile_ops (stmt
)
797 || (TREE_CODE (lhs
) == SSA_NAME
798 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
799 || gimple_has_side_effects (stmt
))
801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
802 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
806 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
807 in between if_convertible_loop_p and combine_blocks
808 we can perform loop versioning. */
809 gimple_set_plf (stmt
, GF_PLF_2
, false);
811 if (flag_tree_loop_if_convert_stores
)
813 if (ifcvt_could_trap_p (stmt
, refs
))
815 if (ifcvt_can_use_mask_load_store (stmt
))
817 gimple_set_plf (stmt
, GF_PLF_2
, true);
818 *any_mask_load_store
= true;
821 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
822 fprintf (dump_file
, "tree could trap...\n");
828 if (gimple_assign_rhs_could_trap_p (stmt
))
830 if (ifcvt_can_use_mask_load_store (stmt
))
832 gimple_set_plf (stmt
, GF_PLF_2
, true);
833 *any_mask_load_store
= true;
836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
837 fprintf (dump_file
, "tree could trap...\n");
841 bb
= gimple_bb (stmt
);
843 if (TREE_CODE (lhs
) != SSA_NAME
844 && bb
!= bb
->loop_father
->header
845 && !bb_with_exit_edge_p (bb
->loop_father
, bb
))
847 if (ifcvt_can_use_mask_load_store (stmt
))
849 gimple_set_plf (stmt
, GF_PLF_2
, true);
850 *any_mask_load_store
= true;
853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
855 fprintf (dump_file
, "LHS is not var\n");
856 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
864 /* Return true when STMT is if-convertible.
866 A statement is if-convertible if:
867 - it is an if-convertible GIMPLE_ASSIGN,
868 - it is a GIMPLE_LABEL or a GIMPLE_COND. */
871 if_convertible_stmt_p (gimple stmt
, vec
<data_reference_p
> refs
,
872 bool *any_mask_load_store
)
874 switch (gimple_code (stmt
))
882 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
883 any_mask_load_store
);
887 tree fndecl
= gimple_call_fndecl (stmt
);
890 int flags
= gimple_call_flags (stmt
);
891 if ((flags
& ECF_CONST
)
892 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
893 /* We can only vectorize some builtins at the moment,
894 so restrict if-conversion to those. */
895 && DECL_BUILT_IN (fndecl
))
902 /* Don't know what to do with 'em so don't do anything. */
903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
905 fprintf (dump_file
, "don't know what to do\n");
906 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
915 /* Return true when BB is if-convertible. This routine does not check
916 basic block's statements and phis.
918 A basic block is not if-convertible if:
919 - it is non-empty and it is after the exit block (in BFS order),
920 - it is after the exit block but before the latch,
921 - its edges are not normal.
923 EXIT_BB is the basic block containing the exit of the LOOP. BB is
927 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
933 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
935 if (EDGE_COUNT (bb
->preds
) > 2
936 || EDGE_COUNT (bb
->succs
) > 2)
941 if (bb
!= loop
->latch
)
943 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
944 fprintf (dump_file
, "basic block after exit bb but before latch\n");
947 else if (!empty_block_p (bb
))
949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
950 fprintf (dump_file
, "non empty basic block after exit bb\n");
953 else if (bb
== loop
->latch
955 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
958 fprintf (dump_file
, "latch is not dominated by exit_block\n");
963 /* Be less adventurous and handle only normal edges. */
964 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
965 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
967 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
968 fprintf (dump_file
, "Difficult to handle edges\n");
972 /* At least one incoming edge has to be non-critical as otherwise edge
973 predicates are not equal to basic-block predicates of the edge
975 if (EDGE_COUNT (bb
->preds
) > 1
976 && bb
!= loop
->header
)
979 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
980 if (EDGE_COUNT (e
->src
->succs
) == 1)
984 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
985 fprintf (dump_file
, "only critical predecessors\n");
993 /* Return true when all predecessor blocks of BB are visited. The
994 VISITED bitmap keeps track of the visited blocks. */
997 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1001 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1002 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1008 /* Get body of a LOOP in suitable order for if-conversion. It is
1009 caller's responsibility to deallocate basic block list.
1010 If-conversion suitable order is, breadth first sort (BFS) order
1011 with an additional constraint: select a block only if all its
1012 predecessors are already selected. */
1014 static basic_block
*
1015 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1017 basic_block
*blocks
, *blocks_in_bfs_order
;
1020 unsigned int index
= 0;
1021 unsigned int visited_count
= 0;
1023 gcc_assert (loop
->num_nodes
);
1024 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1026 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1027 visited
= BITMAP_ALLOC (NULL
);
1029 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1032 while (index
< loop
->num_nodes
)
1034 bb
= blocks_in_bfs_order
[index
];
1036 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1038 free (blocks_in_bfs_order
);
1039 BITMAP_FREE (visited
);
1044 if (!bitmap_bit_p (visited
, bb
->index
))
1046 if (pred_blocks_visited_p (bb
, &visited
)
1047 || bb
== loop
->header
)
1049 /* This block is now visited. */
1050 bitmap_set_bit (visited
, bb
->index
);
1051 blocks
[visited_count
++] = bb
;
1057 if (index
== loop
->num_nodes
1058 && visited_count
!= loop
->num_nodes
)
1062 free (blocks_in_bfs_order
);
1063 BITMAP_FREE (visited
);
1067 /* Returns true when the analysis of the predicates for all the basic
1068 blocks in LOOP succeeded.
1070 predicate_bbs first allocates the predicates of the basic blocks.
1071 These fields are then initialized with the tree expressions
1072 representing the predicates under which a basic block is executed
1073 in the LOOP. As the loop->header is executed at each iteration, it
1074 has the "true" predicate. Other statements executed under a
1075 condition are predicated with that condition, for example
1082 S1 will be predicated with "x", and
1083 S2 will be predicated with "!x". */
1086 predicate_bbs (loop_p loop
)
1090 for (i
= 0; i
< loop
->num_nodes
; i
++)
1091 init_bb_predicate (ifc_bbs
[i
]);
1093 for (i
= 0; i
< loop
->num_nodes
; i
++)
1095 basic_block bb
= ifc_bbs
[i
];
1099 /* The loop latch is always executed and has no extra conditions
1100 to be processed: skip it. */
1101 if (bb
== loop
->latch
)
1103 reset_bb_predicate (loop
->latch
);
1107 cond
= bb_predicate (bb
);
1108 stmt
= last_stmt (bb
);
1109 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1112 edge true_edge
, false_edge
;
1113 location_t loc
= gimple_location (stmt
);
1114 tree c
= fold_build2_loc (loc
, gimple_cond_code (stmt
),
1116 gimple_cond_lhs (stmt
),
1117 gimple_cond_rhs (stmt
));
1119 /* Add new condition into destination's predicate list. */
1120 extract_true_false_edges_from_block (gimple_bb (stmt
),
1121 &true_edge
, &false_edge
);
1123 /* If C is true, then TRUE_EDGE is taken. */
1124 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1127 /* If C is false, then FALSE_EDGE is taken. */
1128 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1130 add_to_dst_predicate_list (loop
, false_edge
,
1131 unshare_expr (cond
), c2
);
1136 /* If current bb has only one successor, then consider it as an
1137 unconditional goto. */
1138 if (single_succ_p (bb
))
1140 basic_block bb_n
= single_succ (bb
);
1142 /* The successor bb inherits the predicate of its
1143 predecessor. If there is no predicate in the predecessor
1144 bb, then consider the successor bb as always executed. */
1145 if (cond
== NULL_TREE
)
1146 cond
= boolean_true_node
;
1148 add_to_predicate_list (loop
, bb_n
, cond
);
1152 /* The loop header is always executed. */
1153 reset_bb_predicate (loop
->header
);
1154 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1155 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1158 /* Return true when LOOP is if-convertible. This is a helper function
1159 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1160 in if_convertible_loop_p. */
1163 if_convertible_loop_p_1 (struct loop
*loop
,
1164 vec
<loop_p
> *loop_nest
,
1165 vec
<data_reference_p
> *refs
,
1166 vec
<ddr_p
> *ddrs
, bool *any_mask_load_store
)
1170 basic_block exit_bb
= NULL
;
1172 /* Don't if-convert the loop when the data dependences cannot be
1173 computed: the loop won't be vectorized in that case. */
1174 res
= compute_data_dependences_for_loop (loop
, true, loop_nest
, refs
, ddrs
);
1178 calculate_dominance_info (CDI_DOMINATORS
);
1180 /* Allow statements that can be handled during if-conversion. */
1181 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1184 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1185 fprintf (dump_file
, "Irreducible loop\n");
1189 for (i
= 0; i
< loop
->num_nodes
; i
++)
1191 basic_block bb
= ifc_bbs
[i
];
1193 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1196 if (bb_with_exit_edge_p (loop
, bb
))
1200 for (i
= 0; i
< loop
->num_nodes
; i
++)
1202 basic_block bb
= ifc_bbs
[i
];
1203 gimple_stmt_iterator gsi
;
1205 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1206 switch (gimple_code (gsi_stmt (gsi
)))
1219 if (flag_tree_loop_if_convert_stores
)
1221 data_reference_p dr
;
1223 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1225 dr
->aux
= XNEW (struct ifc_dr
);
1226 DR_WRITTEN_AT_LEAST_ONCE (dr
) = -1;
1227 DR_RW_UNCONDITIONALLY (dr
) = -1;
1229 predicate_bbs (loop
);
1232 for (i
= 0; i
< loop
->num_nodes
; i
++)
1234 basic_block bb
= ifc_bbs
[i
];
1235 gimple_stmt_iterator itr
;
1237 /* Check the if-convertibility of statements in predicated BBs. */
1238 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1239 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1240 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1241 any_mask_load_store
))
1245 if (flag_tree_loop_if_convert_stores
)
1246 for (i
= 0; i
< loop
->num_nodes
; i
++)
1247 free_bb_predicate (ifc_bbs
[i
]);
1249 /* Checking PHIs needs to be done after stmts, as the fact whether there
1250 are any masked loads or stores affects the tests. */
1251 for (i
= 0; i
< loop
->num_nodes
; i
++)
1253 basic_block bb
= ifc_bbs
[i
];
1254 gimple_stmt_iterator itr
;
1256 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1257 if (!if_convertible_phi_p (loop
, bb
, gsi_stmt (itr
),
1258 *any_mask_load_store
))
1263 fprintf (dump_file
, "Applying if-conversion\n");
1268 /* Return true when LOOP is if-convertible.
1269 LOOP is if-convertible if:
1271 - it has two or more basic blocks,
1272 - it has only one exit,
1273 - loop header is not the exit edge,
1274 - if its basic blocks and phi nodes are if convertible. */
1277 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1282 vec
<data_reference_p
> refs
;
1285 /* Handle only innermost loop. */
1286 if (!loop
|| loop
->inner
)
1288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1289 fprintf (dump_file
, "not innermost loop\n");
1293 /* If only one block, no need for if-conversion. */
1294 if (loop
->num_nodes
<= 2)
1296 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1297 fprintf (dump_file
, "less than 2 basic blocks\n");
1301 /* More than one loop exit is too much to handle. */
1302 if (!single_exit (loop
))
1304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1305 fprintf (dump_file
, "multiple exits\n");
1309 /* If one of the loop header's edge is an exit edge then do not
1310 apply if-conversion. */
1311 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1312 if (loop_exit_edge_p (loop
, e
))
1317 auto_vec
<loop_p
, 3> loop_nest
;
1318 res
= if_convertible_loop_p_1 (loop
, &loop_nest
, &refs
, &ddrs
,
1319 any_mask_load_store
);
1321 if (flag_tree_loop_if_convert_stores
)
1323 data_reference_p dr
;
1326 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1330 free_data_refs (refs
);
1331 free_dependence_relations (ddrs
);
1335 /* Basic block BB has two predecessors. Using predecessor's bb
1336 predicate, set an appropriate condition COND for the PHI node
1337 replacement. Return the true block whose phi arguments are
1338 selected when cond is true. LOOP is the loop containing the
1339 if-converted region, GSI is the place to insert the code for the
1343 find_phi_replacement_condition (basic_block bb
, tree
*cond
,
1344 gimple_stmt_iterator
*gsi
)
1346 edge first_edge
, second_edge
;
1349 gcc_assert (EDGE_COUNT (bb
->preds
) == 2);
1350 first_edge
= EDGE_PRED (bb
, 0);
1351 second_edge
= EDGE_PRED (bb
, 1);
1353 /* Prefer an edge with a not negated predicate.
1354 ??? That's a very weak cost model. */
1355 tmp_cond
= bb_predicate (first_edge
->src
);
1356 gcc_assert (tmp_cond
);
1357 if (TREE_CODE (tmp_cond
) == TRUTH_NOT_EXPR
)
1361 tmp_edge
= first_edge
;
1362 first_edge
= second_edge
;
1363 second_edge
= tmp_edge
;
1366 /* Check if the edge we take the condition from is not critical.
1367 We know that at least one non-critical edge exists. */
1368 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1370 *cond
= bb_predicate (second_edge
->src
);
1372 if (TREE_CODE (*cond
) == TRUTH_NOT_EXPR
)
1373 *cond
= TREE_OPERAND (*cond
, 0);
1375 /* Select non loop header bb. */
1376 first_edge
= second_edge
;
1379 *cond
= bb_predicate (first_edge
->src
);
1381 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1382 *cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (*cond
),
1383 is_gimple_condexpr
, NULL_TREE
,
1384 true, GSI_SAME_STMT
);
1386 return first_edge
->src
;
1389 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1390 which is in predicated basic block.
1391 In fact, the following PHI pattern is searching:
1393 reduc_1 = PHI <..., reduc_2>
1397 reduc_2 = PHI <reduc_1, reduc_3>
1399 REDUC, OP0 and OP1 contain reduction stmt and its operands. */
1402 is_cond_scalar_reduction (gimple phi
, gimple
*reduc
,
1403 tree
*op0
, tree
*op1
)
1405 tree lhs
, r_op1
, r_op2
;
1408 gimple header_phi
= NULL
;
1409 enum tree_code reduction_op
;
1410 basic_block bb
= gimple_bb (phi
);
1411 struct loop
*loop
= bb
->loop_father
;
1412 edge latch_e
= loop_latch_edge (loop
);
1413 imm_use_iterator imm_iter
;
1414 use_operand_p use_p
;
1416 arg_0
= PHI_ARG_DEF (phi
, 0);
1417 arg_1
= PHI_ARG_DEF (phi
, 1);
1418 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1421 if (gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1424 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1425 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1427 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1430 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1431 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1435 if (gimple_bb (header_phi
) != loop
->header
)
1438 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1441 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1442 || gimple_has_volatile_ops (stmt
))
1445 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1448 if (!is_predicated (gimple_bb (stmt
)))
1451 /* Check that stmt-block is predecessor of phi-block. */
1452 if (EDGE_PRED (bb
, 0)->src
!= gimple_bb (stmt
)
1453 && EDGE_PRED (bb
, 1)->src
!= gimple_bb (stmt
))
1456 if (!has_single_use (lhs
))
1459 reduction_op
= gimple_assign_rhs_code (stmt
);
1460 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1462 r_op1
= gimple_assign_rhs1 (stmt
);
1463 r_op2
= gimple_assign_rhs2 (stmt
);
1465 /* Make R_OP1 to hold reduction variable. */
1466 if (r_op2
== PHI_RESULT (header_phi
)
1467 && reduction_op
== PLUS_EXPR
)
1473 else if (r_op1
!= PHI_RESULT (header_phi
))
1476 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1477 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1479 gimple use_stmt
= USE_STMT (use_p
);
1480 if (is_gimple_debug (use_stmt
))
1482 if (use_stmt
== stmt
)
1484 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1488 *op0
= r_op1
; *op1
= r_op2
;
1493 /* Converts conditional scalar reduction into unconditional form, e.g.
1495 if (_5 != 0) goto bb_5 else goto bb_6
1501 # res_2 = PHI <res_13(4), res_6(5)>
1504 will be converted into sequence
1505 _ifc__1 = _5 != 0 ? 1 : 0;
1506 res_2 = res_13 + _ifc__1;
1507 Argument SWAP tells that arguments of conditional expression should be
1509 Returns rhs of resulting PHI assignment. */
1512 convert_scalar_cond_reduction (gimple reduc
, gimple_stmt_iterator
*gsi
,
1513 tree cond
, tree op0
, tree op1
, bool swap
)
1515 gimple_stmt_iterator stmt_it
;
1518 tree rhs1
= gimple_assign_rhs1 (reduc
);
1519 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1521 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1523 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1525 fprintf (dump_file
, "Found cond scalar reduction.\n");
1526 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1529 /* Build cond expression using COND and constant operand
1530 of reduction rhs. */
1531 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1532 unshare_expr (cond
),
1536 /* Create assignment stmt and insert it at GSI. */
1537 new_assign
= gimple_build_assign (tmp
, c
);
1538 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1539 /* Build rhs for unconditional increment/decrement. */
1540 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1541 TREE_TYPE (rhs1
), op0
, tmp
);
1543 /* Delete original reduction stmt. */
1544 stmt_it
= gsi_for_stmt (reduc
);
1545 gsi_remove (&stmt_it
, true);
1546 release_defs (reduc
);
1550 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1551 This routine does not handle PHI nodes with more than two
1555 S1: A = PHI <x1(1), x2(5)>
1557 S2: A = cond ? x1 : x2;
1559 The generated code is inserted at GSI that points to the top of
1560 basic block's statement list. When COND is true, phi arg from
1561 TRUE_BB is selected. */
1564 predicate_scalar_phi (gimple phi
, tree cond
,
1565 basic_block true_bb
,
1566 gimple_stmt_iterator
*gsi
)
1570 tree rhs
, res
, arg
, scev
;
1572 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
1573 && gimple_phi_num_args (phi
) == 2);
1575 res
= gimple_phi_result (phi
);
1576 /* Do not handle virtual phi nodes. */
1577 if (virtual_operand_p (res
))
1580 bb
= gimple_bb (phi
);
1582 if ((arg
= degenerate_phi_result (phi
))
1583 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1585 && !chrec_contains_undetermined (scev
)
1587 && (arg
= gimple_phi_arg_def (phi
, 0))))
1595 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
1596 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1598 arg_0
= gimple_phi_arg_def (phi
, 1);
1599 arg_1
= gimple_phi_arg_def (phi
, 0);
1603 arg_0
= gimple_phi_arg_def (phi
, 0);
1604 arg_1
= gimple_phi_arg_def (phi
, 1);
1606 if (is_cond_scalar_reduction (phi
, &reduc
, &op0
, &op1
))
1607 /* Convert reduction stmt into vectorizable form. */
1608 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1609 true_bb
!= gimple_bb (reduc
));
1611 /* Build new RHS using selected condition and arguments. */
1612 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1616 new_stmt
= gimple_build_assign (res
, rhs
);
1617 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1618 update_stmt (new_stmt
);
1620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1622 fprintf (dump_file
, "new phi replacement stmt\n");
1623 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1627 /* Replaces in LOOP all the scalar phi nodes other than those in the
1628 LOOP->header block with conditional modify expressions. */
1631 predicate_all_scalar_phis (struct loop
*loop
)
1634 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1637 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1640 tree cond
= NULL_TREE
;
1641 gimple_stmt_iterator gsi
, phi_gsi
;
1642 basic_block true_bb
= NULL
;
1645 if (bb
== loop
->header
)
1648 phi_gsi
= gsi_start_phis (bb
);
1649 if (gsi_end_p (phi_gsi
))
1652 /* BB has two predecessors. Using predecessor's aux field, set
1653 appropriate condition for the PHI node replacement. */
1654 gsi
= gsi_after_labels (bb
);
1655 true_bb
= find_phi_replacement_condition (bb
, &cond
, &gsi
);
1657 while (!gsi_end_p (phi_gsi
))
1659 phi
= gsi_stmt (phi_gsi
);
1660 predicate_scalar_phi (phi
, cond
, true_bb
, &gsi
);
1661 release_phi_node (phi
);
1662 gsi_next (&phi_gsi
);
1665 set_phi_nodes (bb
, NULL
);
1669 /* Insert in each basic block of LOOP the statements produced by the
1670 gimplification of the predicates. */
1673 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1677 for (i
= 0; i
< loop
->num_nodes
; i
++)
1679 basic_block bb
= ifc_bbs
[i
];
1682 if (!is_predicated (bb
))
1684 /* Do not insert statements for a basic block that is not
1685 predicated. Also make sure that the predicate of the
1686 basic block is set to true. */
1687 reset_bb_predicate (bb
);
1691 stmts
= bb_predicate_gimplified_stmts (bb
);
1694 if (flag_tree_loop_if_convert_stores
1695 || any_mask_load_store
)
1697 /* Insert the predicate of the BB just after the label,
1698 as the if-conversion of memory writes will use this
1700 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1701 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1705 /* Insert the predicate of the BB at the end of the BB
1706 as this would reduce the register pressure: the only
1707 use of this predicate will be in successor BBs. */
1708 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1711 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1712 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1714 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1717 /* Once the sequence is code generated, set it to NULL. */
1718 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1723 /* Predicate each write to memory in LOOP.
1725 This function transforms control flow constructs containing memory
1728 | for (i = 0; i < N; i++)
1732 into the following form that does not contain control flow:
1734 | for (i = 0; i < N; i++)
1735 | A[i] = cond ? expr : A[i];
1737 The original CFG looks like this:
1744 | if (i < N) goto bb_5 else goto bb_2
1748 | cond = some_computation;
1749 | if (cond) goto bb_3 else goto bb_4
1761 insert_gimplified_predicates inserts the computation of the COND
1762 expression at the beginning of the destination basic block:
1769 | if (i < N) goto bb_5 else goto bb_2
1773 | cond = some_computation;
1774 | if (cond) goto bb_3 else goto bb_4
1778 | cond = some_computation;
1787 predicate_mem_writes is then predicating the memory write as follows:
1794 | if (i < N) goto bb_5 else goto bb_2
1798 | if (cond) goto bb_3 else goto bb_4
1802 | cond = some_computation;
1803 | A[i] = cond ? expr : A[i];
1811 and finally combine_blocks removes the basic block boundaries making
1812 the loop vectorizable:
1816 | if (i < N) goto bb_5 else goto bb_1
1820 | cond = some_computation;
1821 | A[i] = cond ? expr : A[i];
1822 | if (i < N) goto bb_5 else goto bb_4
1831 predicate_mem_writes (loop_p loop
)
1833 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
1835 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1837 gimple_stmt_iterator gsi
;
1838 basic_block bb
= ifc_bbs
[i
];
1839 tree cond
= bb_predicate (bb
);
1843 if (is_true_predicate (cond
))
1847 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1850 cond
= TREE_OPERAND (cond
, 0);
1853 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1854 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
1856 else if (gimple_plf (stmt
, GF_PLF_2
))
1858 tree lhs
= gimple_assign_lhs (stmt
);
1859 tree rhs
= gimple_assign_rhs1 (stmt
);
1860 tree ref
, addr
, ptr
, masktype
, mask_op0
, mask_op1
, mask
;
1862 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
1864 masktype
= build_nonstandard_integer_type (bitsize
, 1);
1865 mask_op0
= build_int_cst (masktype
, swap
? 0 : -1);
1866 mask_op1
= build_int_cst (masktype
, swap
? -1 : 0);
1867 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
1868 mark_addressable (ref
);
1869 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
1870 true, NULL_TREE
, true,
1872 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1873 is_gimple_condexpr
, NULL_TREE
,
1874 true, GSI_SAME_STMT
);
1875 mask
= fold_build_cond_expr (masktype
, unshare_expr (cond
),
1876 mask_op0
, mask_op1
);
1877 mask
= ifc_temp_var (masktype
, mask
, &gsi
);
1878 ptr
= build_int_cst (reference_alias_ptr_type (ref
), 0);
1879 /* Copy points-to info if possible. */
1880 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
1881 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
1883 if (TREE_CODE (lhs
) == SSA_NAME
)
1886 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
1888 gimple_call_set_lhs (new_stmt
, lhs
);
1892 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
1894 gsi_replace (&gsi
, new_stmt
, true);
1896 else if (gimple_vdef (stmt
))
1898 tree lhs
= gimple_assign_lhs (stmt
);
1899 tree rhs
= gimple_assign_rhs1 (stmt
);
1900 tree type
= TREE_TYPE (lhs
);
1902 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
1903 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
1910 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1911 is_gimple_condexpr
, NULL_TREE
,
1912 true, GSI_SAME_STMT
);
1913 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
1914 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
1920 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1921 other than the exit and latch of the LOOP. Also resets the
1922 GIMPLE_DEBUG information. */
1925 remove_conditions_and_labels (loop_p loop
)
1927 gimple_stmt_iterator gsi
;
1930 for (i
= 0; i
< loop
->num_nodes
; i
++)
1932 basic_block bb
= ifc_bbs
[i
];
1934 if (bb_with_exit_edge_p (loop
, bb
)
1935 || bb
== loop
->latch
)
1938 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1939 switch (gimple_code (gsi_stmt (gsi
)))
1943 gsi_remove (&gsi
, true);
1947 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
1948 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
1950 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
1951 update_stmt (gsi_stmt (gsi
));
1962 /* Combine all the basic blocks from LOOP into one or two super basic
1963 blocks. Replace PHI nodes with conditional modify expressions. */
1966 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
1968 basic_block bb
, exit_bb
, merge_target_bb
;
1969 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1974 predicate_bbs (loop
);
1975 remove_conditions_and_labels (loop
);
1976 insert_gimplified_predicates (loop
, any_mask_load_store
);
1977 predicate_all_scalar_phis (loop
);
1979 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
1980 predicate_mem_writes (loop
);
1982 /* Merge basic blocks: first remove all the edges in the loop,
1983 except for those from the exit block. */
1985 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
1988 free_bb_predicate (bb
);
1989 if (bb_with_exit_edge_p (loop
, bb
))
1991 gcc_assert (exit_bb
== NULL
);
1995 gcc_assert (exit_bb
!= loop
->latch
);
1997 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2001 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2003 if (e
->src
== exit_bb
)
2010 if (exit_bb
!= NULL
)
2012 if (exit_bb
!= loop
->header
)
2014 /* Connect this node to loop header. */
2015 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2016 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2019 /* Redirect non-exit edges to loop->latch. */
2020 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2022 if (!loop_exit_edge_p (loop
, e
))
2023 redirect_edge_and_branch (e
, loop
->latch
);
2025 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2029 /* If the loop does not have an exit, reconnect header and latch. */
2030 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2031 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2034 merge_target_bb
= loop
->header
;
2035 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2037 gimple_stmt_iterator gsi
;
2038 gimple_stmt_iterator last
;
2042 if (bb
== exit_bb
|| bb
== loop
->latch
)
2045 /* Make stmts member of loop->header. */
2046 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2047 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
2049 /* Update stmt list. */
2050 last
= gsi_last_bb (merge_target_bb
);
2051 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2052 set_bb_seq (bb
, NULL
);
2054 delete_basic_block (bb
);
2057 /* If possible, merge loop header to the block with the exit edge.
2058 This reduces the number of basic blocks to two, to please the
2059 vectorizer that handles only loops with two nodes. */
2061 && exit_bb
!= loop
->header
2062 && can_merge_blocks_p (loop
->header
, exit_bb
))
2063 merge_blocks (loop
->header
, exit_bb
);
2069 /* Version LOOP before if-converting it, the original loop
2070 will be then if-converted, the new copy of the loop will not,
2071 and the LOOP_VECTORIZED internal call will be guarding which
2072 loop to execute. The vectorizer pass will fold this
2073 internal call into either true or false. */
2076 version_loop_for_if_conversion (struct loop
*loop
)
2078 basic_block cond_bb
;
2079 tree cond
= make_ssa_name (boolean_type_node
, NULL
);
2080 struct loop
*new_loop
;
2082 gimple_stmt_iterator gsi
;
2084 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2085 build_int_cst (integer_type_node
, loop
->num
),
2087 gimple_call_set_lhs (g
, cond
);
2089 initialize_original_copy_tables ();
2090 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2091 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2092 REG_BR_PROB_BASE
, true);
2093 free_original_copy_tables ();
2094 if (new_loop
== NULL
)
2096 new_loop
->dont_vectorize
= true;
2097 new_loop
->force_vectorize
= false;
2098 gsi
= gsi_last_bb (cond_bb
);
2099 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2100 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2101 update_ssa (TODO_update_ssa
);
2105 /* If-convert LOOP when it is legal. For the moment this pass has no
2106 profitability analysis. Returns non-zero todo flags when something
2110 tree_if_conversion (struct loop
*loop
)
2112 unsigned int todo
= 0;
2114 bool any_mask_load_store
= false;
2116 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2117 || !dbg_cnt (if_conversion_tree
))
2120 if (any_mask_load_store
2121 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2122 || loop
->dont_vectorize
))
2125 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2128 /* Now all statements are if-convertible. Combine all the basic
2129 blocks into one huge basic block doing the if-conversion
2131 combine_blocks (loop
, any_mask_load_store
);
2133 todo
|= TODO_cleanup_cfg
;
2134 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2136 mark_virtual_operands_for_renaming (cfun
);
2137 todo
|= TODO_update_ssa_only_virtuals
;
2145 for (i
= 0; i
< loop
->num_nodes
; i
++)
2146 free_bb_predicate (ifc_bbs
[i
]);
2155 /* Tree if-conversion pass management. */
2159 const pass_data pass_data_if_conversion
=
2161 GIMPLE_PASS
, /* type */
2163 OPTGROUP_NONE
, /* optinfo_flags */
2164 true, /* has_execute */
2165 TV_NONE
, /* tv_id */
2166 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2167 0, /* properties_provided */
2168 0, /* properties_destroyed */
2169 0, /* todo_flags_start */
2170 0, /* todo_flags_finish */
2173 class pass_if_conversion
: public gimple_opt_pass
2176 pass_if_conversion (gcc::context
*ctxt
)
2177 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2180 /* opt_pass methods: */
2181 virtual bool gate (function
*);
2182 virtual unsigned int execute (function
*);
2184 }; // class pass_if_conversion
2187 pass_if_conversion::gate (function
*fun
)
2189 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2190 && flag_tree_loop_if_convert
!= 0)
2191 || flag_tree_loop_if_convert
== 1
2192 || flag_tree_loop_if_convert_stores
== 1);
2196 pass_if_conversion::execute (function
*fun
)
2201 if (number_of_loops (fun
) <= 1)
2204 FOR_EACH_LOOP (loop
, 0)
2205 if (flag_tree_loop_if_convert
== 1
2206 || flag_tree_loop_if_convert_stores
== 1
2207 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2208 && !loop
->dont_vectorize
))
2209 todo
|= tree_if_conversion (loop
);
2211 #ifdef ENABLE_CHECKING
2214 FOR_EACH_BB_FN (bb
, fun
)
2215 gcc_assert (!bb
->aux
);
2225 make_pass_if_conversion (gcc::context
*ctxt
)
2227 return new pass_if_conversion (ctxt
);