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 struct loop
*loop
= gimple_bb (phi
)->loop_father
;
1411 edge latch_e
= loop_latch_edge (loop
);
1412 imm_use_iterator imm_iter
;
1413 use_operand_p use_p
;
1415 arg_0
= PHI_ARG_DEF (phi
, 0);
1416 arg_1
= PHI_ARG_DEF (phi
, 1);
1417 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1420 if (gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1423 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1424 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1426 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1429 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1430 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1434 if (gimple_bb (header_phi
) != loop
->header
)
1437 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1440 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1441 || gimple_has_volatile_ops (stmt
))
1444 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1447 if (!is_predicated (gimple_bb (stmt
)))
1450 if (!has_single_use (lhs
))
1453 reduction_op
= gimple_assign_rhs_code (stmt
);
1454 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1456 r_op1
= gimple_assign_rhs1 (stmt
);
1457 r_op2
= gimple_assign_rhs2 (stmt
);
1459 /* Make R_OP1 to hold reduction variable. */
1460 if (r_op2
== PHI_RESULT (header_phi
)
1461 && reduction_op
== PLUS_EXPR
)
1467 else if (r_op1
!= PHI_RESULT (header_phi
))
1470 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1471 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1473 gimple use_stmt
= USE_STMT (use_p
);
1474 if (is_gimple_debug (use_stmt
))
1476 if (use_stmt
== stmt
)
1478 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1482 *op0
= r_op1
; *op1
= r_op2
;
1487 /* Converts conditional scalar reduction into unconditional form, e.g.
1489 if (_5 != 0) goto bb_5 else goto bb_6
1495 # res_2 = PHI <res_13(4), res_6(5)>
1498 will be converted into sequence
1499 _ifc__1 = _5 != 0 ? 1 : 0;
1500 res_2 = res_13 + _ifc__1;
1501 Argument SWAP tells that arguments of conditional expression should be
1503 Returns rhs of resulting PHI assignment. */
1506 convert_scalar_cond_reduction (gimple reduc
, gimple_stmt_iterator
*gsi
,
1507 tree cond
, tree op0
, tree op1
, bool swap
)
1509 gimple_stmt_iterator stmt_it
;
1512 tree rhs1
= gimple_assign_rhs1 (reduc
);
1513 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1515 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1517 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1519 fprintf (dump_file
, "Found cond scalar reduction.\n");
1520 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1523 /* Build cond expression using COND and constant operand
1524 of reduction rhs. */
1525 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1526 unshare_expr (cond
),
1530 /* Create assignment stmt and insert it at GSI. */
1531 new_assign
= gimple_build_assign (tmp
, c
);
1532 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1533 /* Build rhs for unconditional increment/decrement. */
1534 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1535 TREE_TYPE (rhs1
), op0
, tmp
);
1537 /* Delete original reduction stmt. */
1538 stmt_it
= gsi_for_stmt (reduc
);
1539 gsi_remove (&stmt_it
, true);
1540 release_defs (reduc
);
1544 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1545 This routine does not handle PHI nodes with more than two
1549 S1: A = PHI <x1(1), x2(5)>
1551 S2: A = cond ? x1 : x2;
1553 The generated code is inserted at GSI that points to the top of
1554 basic block's statement list. When COND is true, phi arg from
1555 TRUE_BB is selected. */
1558 predicate_scalar_phi (gimple phi
, tree cond
,
1559 basic_block true_bb
,
1560 gimple_stmt_iterator
*gsi
)
1564 tree rhs
, res
, arg
, scev
;
1566 gcc_assert (gimple_code (phi
) == GIMPLE_PHI
1567 && gimple_phi_num_args (phi
) == 2);
1569 res
= gimple_phi_result (phi
);
1570 /* Do not handle virtual phi nodes. */
1571 if (virtual_operand_p (res
))
1574 bb
= gimple_bb (phi
);
1576 if ((arg
= degenerate_phi_result (phi
))
1577 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1579 && !chrec_contains_undetermined (scev
)
1581 && (arg
= gimple_phi_arg_def (phi
, 0))))
1589 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
1590 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1592 arg_0
= gimple_phi_arg_def (phi
, 1);
1593 arg_1
= gimple_phi_arg_def (phi
, 0);
1597 arg_0
= gimple_phi_arg_def (phi
, 0);
1598 arg_1
= gimple_phi_arg_def (phi
, 1);
1600 if (is_cond_scalar_reduction (phi
, &reduc
, &op0
, &op1
))
1601 /* Convert reduction stmt into vectorizable form. */
1602 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1603 true_bb
!= gimple_bb (reduc
));
1605 /* Build new RHS using selected condition and arguments. */
1606 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1610 new_stmt
= gimple_build_assign (res
, rhs
);
1611 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1612 update_stmt (new_stmt
);
1614 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1616 fprintf (dump_file
, "new phi replacement stmt\n");
1617 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1621 /* Replaces in LOOP all the scalar phi nodes other than those in the
1622 LOOP->header block with conditional modify expressions. */
1625 predicate_all_scalar_phis (struct loop
*loop
)
1628 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1631 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1634 tree cond
= NULL_TREE
;
1635 gimple_stmt_iterator gsi
, phi_gsi
;
1636 basic_block true_bb
= NULL
;
1639 if (bb
== loop
->header
)
1642 phi_gsi
= gsi_start_phis (bb
);
1643 if (gsi_end_p (phi_gsi
))
1646 /* BB has two predecessors. Using predecessor's aux field, set
1647 appropriate condition for the PHI node replacement. */
1648 gsi
= gsi_after_labels (bb
);
1649 true_bb
= find_phi_replacement_condition (bb
, &cond
, &gsi
);
1651 while (!gsi_end_p (phi_gsi
))
1653 phi
= gsi_stmt (phi_gsi
);
1654 predicate_scalar_phi (phi
, cond
, true_bb
, &gsi
);
1655 release_phi_node (phi
);
1656 gsi_next (&phi_gsi
);
1659 set_phi_nodes (bb
, NULL
);
1663 /* Insert in each basic block of LOOP the statements produced by the
1664 gimplification of the predicates. */
1667 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1671 for (i
= 0; i
< loop
->num_nodes
; i
++)
1673 basic_block bb
= ifc_bbs
[i
];
1676 if (!is_predicated (bb
))
1678 /* Do not insert statements for a basic block that is not
1679 predicated. Also make sure that the predicate of the
1680 basic block is set to true. */
1681 reset_bb_predicate (bb
);
1685 stmts
= bb_predicate_gimplified_stmts (bb
);
1688 if (flag_tree_loop_if_convert_stores
1689 || any_mask_load_store
)
1691 /* Insert the predicate of the BB just after the label,
1692 as the if-conversion of memory writes will use this
1694 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1695 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1699 /* Insert the predicate of the BB at the end of the BB
1700 as this would reduce the register pressure: the only
1701 use of this predicate will be in successor BBs. */
1702 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1705 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1706 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1708 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1711 /* Once the sequence is code generated, set it to NULL. */
1712 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1717 /* Predicate each write to memory in LOOP.
1719 This function transforms control flow constructs containing memory
1722 | for (i = 0; i < N; i++)
1726 into the following form that does not contain control flow:
1728 | for (i = 0; i < N; i++)
1729 | A[i] = cond ? expr : A[i];
1731 The original CFG looks like this:
1738 | if (i < N) goto bb_5 else goto bb_2
1742 | cond = some_computation;
1743 | if (cond) goto bb_3 else goto bb_4
1755 insert_gimplified_predicates inserts the computation of the COND
1756 expression at the beginning of the destination basic block:
1763 | if (i < N) goto bb_5 else goto bb_2
1767 | cond = some_computation;
1768 | if (cond) goto bb_3 else goto bb_4
1772 | cond = some_computation;
1781 predicate_mem_writes is then predicating the memory write as follows:
1788 | if (i < N) goto bb_5 else goto bb_2
1792 | if (cond) goto bb_3 else goto bb_4
1796 | cond = some_computation;
1797 | A[i] = cond ? expr : A[i];
1805 and finally combine_blocks removes the basic block boundaries making
1806 the loop vectorizable:
1810 | if (i < N) goto bb_5 else goto bb_1
1814 | cond = some_computation;
1815 | A[i] = cond ? expr : A[i];
1816 | if (i < N) goto bb_5 else goto bb_4
1825 predicate_mem_writes (loop_p loop
)
1827 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
1829 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1831 gimple_stmt_iterator gsi
;
1832 basic_block bb
= ifc_bbs
[i
];
1833 tree cond
= bb_predicate (bb
);
1837 if (is_true_predicate (cond
))
1841 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1844 cond
= TREE_OPERAND (cond
, 0);
1847 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1848 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
1850 else if (gimple_plf (stmt
, GF_PLF_2
))
1852 tree lhs
= gimple_assign_lhs (stmt
);
1853 tree rhs
= gimple_assign_rhs1 (stmt
);
1854 tree ref
, addr
, ptr
, masktype
, mask_op0
, mask_op1
, mask
;
1856 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
1858 masktype
= build_nonstandard_integer_type (bitsize
, 1);
1859 mask_op0
= build_int_cst (masktype
, swap
? 0 : -1);
1860 mask_op1
= build_int_cst (masktype
, swap
? -1 : 0);
1861 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
1862 mark_addressable (ref
);
1863 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
1864 true, NULL_TREE
, true,
1866 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1867 is_gimple_condexpr
, NULL_TREE
,
1868 true, GSI_SAME_STMT
);
1869 mask
= fold_build_cond_expr (masktype
, unshare_expr (cond
),
1870 mask_op0
, mask_op1
);
1871 mask
= ifc_temp_var (masktype
, mask
, &gsi
);
1872 ptr
= build_int_cst (reference_alias_ptr_type (ref
), 0);
1873 /* Copy points-to info if possible. */
1874 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
1875 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
1877 if (TREE_CODE (lhs
) == SSA_NAME
)
1880 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
1882 gimple_call_set_lhs (new_stmt
, lhs
);
1886 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
1888 gsi_replace (&gsi
, new_stmt
, true);
1890 else if (gimple_vdef (stmt
))
1892 tree lhs
= gimple_assign_lhs (stmt
);
1893 tree rhs
= gimple_assign_rhs1 (stmt
);
1894 tree type
= TREE_TYPE (lhs
);
1896 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
1897 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
1904 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
1905 is_gimple_condexpr
, NULL_TREE
,
1906 true, GSI_SAME_STMT
);
1907 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
1908 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
1914 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1915 other than the exit and latch of the LOOP. Also resets the
1916 GIMPLE_DEBUG information. */
1919 remove_conditions_and_labels (loop_p loop
)
1921 gimple_stmt_iterator gsi
;
1924 for (i
= 0; i
< loop
->num_nodes
; i
++)
1926 basic_block bb
= ifc_bbs
[i
];
1928 if (bb_with_exit_edge_p (loop
, bb
)
1929 || bb
== loop
->latch
)
1932 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
1933 switch (gimple_code (gsi_stmt (gsi
)))
1937 gsi_remove (&gsi
, true);
1941 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
1942 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
1944 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
1945 update_stmt (gsi_stmt (gsi
));
1956 /* Combine all the basic blocks from LOOP into one or two super basic
1957 blocks. Replace PHI nodes with conditional modify expressions. */
1960 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
1962 basic_block bb
, exit_bb
, merge_target_bb
;
1963 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1968 predicate_bbs (loop
);
1969 remove_conditions_and_labels (loop
);
1970 insert_gimplified_predicates (loop
, any_mask_load_store
);
1971 predicate_all_scalar_phis (loop
);
1973 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
1974 predicate_mem_writes (loop
);
1976 /* Merge basic blocks: first remove all the edges in the loop,
1977 except for those from the exit block. */
1979 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
1982 free_bb_predicate (bb
);
1983 if (bb_with_exit_edge_p (loop
, bb
))
1985 gcc_assert (exit_bb
== NULL
);
1989 gcc_assert (exit_bb
!= loop
->latch
);
1991 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1995 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
1997 if (e
->src
== exit_bb
)
2004 if (exit_bb
!= NULL
)
2006 if (exit_bb
!= loop
->header
)
2008 /* Connect this node to loop header. */
2009 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2010 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2013 /* Redirect non-exit edges to loop->latch. */
2014 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2016 if (!loop_exit_edge_p (loop
, e
))
2017 redirect_edge_and_branch (e
, loop
->latch
);
2019 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2023 /* If the loop does not have an exit, reconnect header and latch. */
2024 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2025 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2028 merge_target_bb
= loop
->header
;
2029 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2031 gimple_stmt_iterator gsi
;
2032 gimple_stmt_iterator last
;
2036 if (bb
== exit_bb
|| bb
== loop
->latch
)
2039 /* Make stmts member of loop->header. */
2040 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2041 gimple_set_bb (gsi_stmt (gsi
), merge_target_bb
);
2043 /* Update stmt list. */
2044 last
= gsi_last_bb (merge_target_bb
);
2045 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2046 set_bb_seq (bb
, NULL
);
2048 delete_basic_block (bb
);
2051 /* If possible, merge loop header to the block with the exit edge.
2052 This reduces the number of basic blocks to two, to please the
2053 vectorizer that handles only loops with two nodes. */
2055 && exit_bb
!= loop
->header
2056 && can_merge_blocks_p (loop
->header
, exit_bb
))
2057 merge_blocks (loop
->header
, exit_bb
);
2063 /* Version LOOP before if-converting it, the original loop
2064 will be then if-converted, the new copy of the loop will not,
2065 and the LOOP_VECTORIZED internal call will be guarding which
2066 loop to execute. The vectorizer pass will fold this
2067 internal call into either true or false. */
2070 version_loop_for_if_conversion (struct loop
*loop
)
2072 basic_block cond_bb
;
2073 tree cond
= make_ssa_name (boolean_type_node
, NULL
);
2074 struct loop
*new_loop
;
2076 gimple_stmt_iterator gsi
;
2078 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2079 build_int_cst (integer_type_node
, loop
->num
),
2081 gimple_call_set_lhs (g
, cond
);
2083 initialize_original_copy_tables ();
2084 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2085 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2086 REG_BR_PROB_BASE
, true);
2087 free_original_copy_tables ();
2088 if (new_loop
== NULL
)
2090 new_loop
->dont_vectorize
= true;
2091 new_loop
->force_vectorize
= false;
2092 gsi
= gsi_last_bb (cond_bb
);
2093 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2094 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2095 update_ssa (TODO_update_ssa
);
2099 /* If-convert LOOP when it is legal. For the moment this pass has no
2100 profitability analysis. Returns non-zero todo flags when something
2104 tree_if_conversion (struct loop
*loop
)
2106 unsigned int todo
= 0;
2108 bool any_mask_load_store
= false;
2110 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2111 || !dbg_cnt (if_conversion_tree
))
2114 if (any_mask_load_store
2115 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2116 || loop
->dont_vectorize
))
2119 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2122 /* Now all statements are if-convertible. Combine all the basic
2123 blocks into one huge basic block doing the if-conversion
2125 combine_blocks (loop
, any_mask_load_store
);
2127 todo
|= TODO_cleanup_cfg
;
2128 if (flag_tree_loop_if_convert_stores
|| any_mask_load_store
)
2130 mark_virtual_operands_for_renaming (cfun
);
2131 todo
|= TODO_update_ssa_only_virtuals
;
2139 for (i
= 0; i
< loop
->num_nodes
; i
++)
2140 free_bb_predicate (ifc_bbs
[i
]);
2149 /* Tree if-conversion pass management. */
2153 const pass_data pass_data_if_conversion
=
2155 GIMPLE_PASS
, /* type */
2157 OPTGROUP_NONE
, /* optinfo_flags */
2158 true, /* has_execute */
2159 TV_NONE
, /* tv_id */
2160 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2161 0, /* properties_provided */
2162 0, /* properties_destroyed */
2163 0, /* todo_flags_start */
2164 0, /* todo_flags_finish */
2167 class pass_if_conversion
: public gimple_opt_pass
2170 pass_if_conversion (gcc::context
*ctxt
)
2171 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2174 /* opt_pass methods: */
2175 virtual bool gate (function
*);
2176 virtual unsigned int execute (function
*);
2178 }; // class pass_if_conversion
2181 pass_if_conversion::gate (function
*fun
)
2183 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2184 && flag_tree_loop_if_convert
!= 0)
2185 || flag_tree_loop_if_convert
== 1
2186 || flag_tree_loop_if_convert_stores
== 1);
2190 pass_if_conversion::execute (function
*fun
)
2195 if (number_of_loops (fun
) <= 1)
2198 FOR_EACH_LOOP (loop
, 0)
2199 if (flag_tree_loop_if_convert
== 1
2200 || flag_tree_loop_if_convert_stores
== 1
2201 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2202 && !loop
->dont_vectorize
))
2203 todo
|= tree_if_conversion (loop
);
2205 #ifdef ENABLE_CHECKING
2208 FOR_EACH_BB_FN (bb
, fun
)
2209 gcc_assert (!bb
->aux
);
2219 make_pass_if_conversion (gcc::context
*ctxt
)
2221 return new pass_if_conversion (ctxt
);