1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2016 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"
91 #include "tree-pass.h"
94 #include "optabs-query.h"
95 #include "gimple-pretty-print.h"
97 #include "fold-const.h"
98 #include "stor-layout.h"
99 #include "gimple-fold.h"
100 #include "gimplify.h"
101 #include "gimple-iterator.h"
102 #include "gimplify-me.h"
103 #include "tree-cfg.h"
104 #include "tree-into-ssa.h"
105 #include "tree-ssa.h"
107 #include "tree-data-ref.h"
108 #include "tree-scalar-evolution.h"
109 #include "tree-ssa-loop-ivopts.h"
110 #include "tree-ssa-address.h"
112 #include "tree-hash-traits.h"
114 #include "builtins.h"
117 /* Hash for struct innermost_loop_behavior. It depends on the user to
120 struct innermost_loop_behavior_hash
: nofree_ptr_hash
<innermost_loop_behavior
>
122 static inline hashval_t
hash (const value_type
&);
123 static inline bool equal (const value_type
&,
124 const compare_type
&);
128 innermost_loop_behavior_hash::hash (const value_type
&e
)
132 hash
= iterative_hash_expr (e
->base_address
, 0);
133 hash
= iterative_hash_expr (e
->offset
, hash
);
134 hash
= iterative_hash_expr (e
->init
, hash
);
135 return iterative_hash_expr (e
->step
, hash
);
139 innermost_loop_behavior_hash::equal (const value_type
&e1
,
140 const compare_type
&e2
)
142 if ((e1
->base_address
&& !e2
->base_address
)
143 || (!e1
->base_address
&& e2
->base_address
)
144 || (!e1
->offset
&& e2
->offset
)
145 || (e1
->offset
&& !e2
->offset
)
146 || (!e1
->init
&& e2
->init
)
147 || (e1
->init
&& !e2
->init
)
148 || (!e1
->step
&& e2
->step
)
149 || (e1
->step
&& !e2
->step
))
152 if (e1
->base_address
&& e2
->base_address
153 && !operand_equal_p (e1
->base_address
, e2
->base_address
, 0))
155 if (e1
->offset
&& e2
->offset
156 && !operand_equal_p (e1
->offset
, e2
->offset
, 0))
158 if (e1
->init
&& e2
->init
159 && !operand_equal_p (e1
->init
, e2
->init
, 0))
161 if (e1
->step
&& e2
->step
162 && !operand_equal_p (e1
->step
, e2
->step
, 0))
168 /* List of basic blocks in if-conversion-suitable order. */
169 static basic_block
*ifc_bbs
;
171 /* Apply more aggressive (extended) if-conversion if true. */
172 static bool aggressive_if_conv
;
174 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
175 static hash_map
<innermost_loop_behavior_hash
,
176 data_reference_p
> *innermost_DR_map
;
178 /* Hash table to store <base reference, DR> pairs. */
179 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
181 /* Structure used to predicate basic blocks. This is attached to the
182 ->aux field of the BBs in the loop to be if-converted. */
183 struct bb_predicate
{
185 /* The condition under which this basic block is executed. */
188 /* PREDICATE is gimplified, and the sequence of statements is
189 recorded here, in order to avoid the duplication of computations
190 that occur in previous conditions. See PR44483. */
191 gimple_seq predicate_gimplified_stmts
;
194 /* Returns true when the basic block BB has a predicate. */
197 bb_has_predicate (basic_block bb
)
199 return bb
->aux
!= NULL
;
202 /* Returns the gimplified predicate for basic block BB. */
205 bb_predicate (basic_block bb
)
207 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
210 /* Sets the gimplified predicate COND for basic block BB. */
213 set_bb_predicate (basic_block bb
, tree cond
)
215 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
216 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
217 || is_gimple_condexpr (cond
));
218 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
221 /* Returns the sequence of statements of the gimplification of the
222 predicate for basic block BB. */
224 static inline gimple_seq
225 bb_predicate_gimplified_stmts (basic_block bb
)
227 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
230 /* Sets the sequence of statements STMTS of the gimplification of the
231 predicate for basic block BB. */
234 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
236 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
239 /* Adds the sequence of statements STMTS to the sequence of statements
240 of the predicate for basic block BB. */
243 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
246 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
249 /* Initializes to TRUE the predicate of basic block BB. */
252 init_bb_predicate (basic_block bb
)
254 bb
->aux
= XNEW (struct bb_predicate
);
255 set_bb_predicate_gimplified_stmts (bb
, NULL
);
256 set_bb_predicate (bb
, boolean_true_node
);
259 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
260 but don't actually free it. */
263 release_bb_predicate (basic_block bb
)
265 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
268 gimple_stmt_iterator i
;
270 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
271 free_stmt_operands (cfun
, gsi_stmt (i
));
272 set_bb_predicate_gimplified_stmts (bb
, NULL
);
276 /* Free the predicate of basic block BB. */
279 free_bb_predicate (basic_block bb
)
281 if (!bb_has_predicate (bb
))
284 release_bb_predicate (bb
);
289 /* Reinitialize predicate of BB with the true predicate. */
292 reset_bb_predicate (basic_block bb
)
294 if (!bb_has_predicate (bb
))
295 init_bb_predicate (bb
);
298 release_bb_predicate (bb
);
299 set_bb_predicate (bb
, boolean_true_node
);
303 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
304 the expression EXPR. Inserts the statement created for this
305 computation before GSI and leaves the iterator GSI at the same
309 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
311 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
312 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
313 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
317 /* Return true when COND is a false predicate. */
320 is_false_predicate (tree cond
)
322 return (cond
!= NULL_TREE
323 && (cond
== boolean_false_node
324 || integer_zerop (cond
)));
327 /* Return true when COND is a true predicate. */
330 is_true_predicate (tree cond
)
332 return (cond
== NULL_TREE
333 || cond
== boolean_true_node
334 || integer_onep (cond
));
337 /* Returns true when BB has a predicate that is not trivial: true or
341 is_predicated (basic_block bb
)
343 return !is_true_predicate (bb_predicate (bb
));
346 /* Parses the predicate COND and returns its comparison code and
347 operands OP0 and OP1. */
349 static enum tree_code
350 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
354 if (TREE_CODE (cond
) == SSA_NAME
355 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
357 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
359 *op0
= gimple_assign_rhs1 (s
);
360 *op1
= gimple_assign_rhs2 (s
);
361 return gimple_assign_rhs_code (s
);
364 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
366 tree op
= gimple_assign_rhs1 (s
);
367 tree type
= TREE_TYPE (op
);
368 enum tree_code code
= parse_predicate (op
, op0
, op1
);
370 return code
== ERROR_MARK
? ERROR_MARK
371 : invert_tree_comparison (code
, HONOR_NANS (type
));
377 if (COMPARISON_CLASS_P (cond
))
379 *op0
= TREE_OPERAND (cond
, 0);
380 *op1
= TREE_OPERAND (cond
, 1);
381 return TREE_CODE (cond
);
387 /* Returns the fold of predicate C1 OR C2 at location LOC. */
390 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
392 tree op1a
, op1b
, op2a
, op2b
;
393 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
394 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
396 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
398 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
404 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
407 /* Returns true if N is either a constant or a SSA_NAME. */
410 constant_or_ssa_name (tree n
)
412 switch (TREE_CODE (n
))
425 /* Returns either a COND_EXPR or the folded expression if the folded
426 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
427 a constant or a SSA_NAME. */
430 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
432 tree rhs1
, lhs1
, cond_expr
;
434 /* If COND is comparison r != 0 and r has boolean type, convert COND
435 to SSA_NAME to accept by vect bool pattern. */
436 if (TREE_CODE (cond
) == NE_EXPR
)
438 tree op0
= TREE_OPERAND (cond
, 0);
439 tree op1
= TREE_OPERAND (cond
, 1);
440 if (TREE_CODE (op0
) == SSA_NAME
441 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
442 && (integer_zerop (op1
)))
445 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
448 if (cond_expr
== NULL_TREE
)
449 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
451 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
453 if (constant_or_ssa_name (cond_expr
))
456 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
458 rhs1
= TREE_OPERAND (cond_expr
, 1);
459 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
460 if (constant_or_ssa_name (rhs1
))
461 return build1 (ABS_EXPR
, type
, rhs1
);
464 if (TREE_CODE (cond_expr
) == MIN_EXPR
465 || TREE_CODE (cond_expr
) == MAX_EXPR
)
467 lhs1
= TREE_OPERAND (cond_expr
, 0);
468 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
469 rhs1
= TREE_OPERAND (cond_expr
, 1);
470 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
471 if (constant_or_ssa_name (rhs1
)
472 && constant_or_ssa_name (lhs1
))
473 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
475 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
478 /* Add condition NC to the predicate list of basic block BB. LOOP is
479 the loop to be if-converted. Use predicate of cd-equivalent block
480 for join bb if it exists: we call basic blocks bb1 and bb2
481 cd-equivalent if they are executed under the same condition. */
484 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
489 if (is_true_predicate (nc
))
492 /* If dominance tells us this basic block is always executed,
493 don't record any predicates for it. */
494 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
497 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
498 /* We use notion of cd equivalence to get simpler predicate for
499 join block, e.g. if join block has 2 predecessors with predicates
500 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
501 p1 & p2 | p1 & !p2. */
502 if (dom_bb
!= loop
->header
503 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
505 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
506 bc
= bb_predicate (dom_bb
);
507 if (!is_true_predicate (bc
))
508 set_bb_predicate (bb
, bc
);
510 gcc_assert (is_true_predicate (bb_predicate (bb
)));
511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
512 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
513 dom_bb
->index
, bb
->index
);
517 if (!is_predicated (bb
))
521 bc
= bb_predicate (bb
);
522 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
523 if (is_true_predicate (bc
))
525 reset_bb_predicate (bb
);
530 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
531 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
532 tp
= &TREE_OPERAND (bc
, 0);
535 if (!is_gimple_condexpr (*tp
))
538 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
539 add_bb_predicate_gimplified_stmts (bb
, stmts
);
541 set_bb_predicate (bb
, bc
);
544 /* Add the condition COND to the previous condition PREV_COND, and add
545 this to the predicate list of the destination of edge E. LOOP is
546 the loop to be if-converted. */
549 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
550 tree prev_cond
, tree cond
)
552 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
555 if (!is_true_predicate (prev_cond
))
556 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
559 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
560 add_to_predicate_list (loop
, e
->dest
, cond
);
563 /* Return true if one of the successor edges of BB exits LOOP. */
566 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
571 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
572 if (loop_exit_edge_p (loop
, e
))
578 /* Given PHI which has more than two arguments, this function checks if
579 it's if-convertible by degenerating its arguments. Specifically, if
580 below two conditions are satisfied:
582 1) Number of PHI arguments with different values equals to 2 and one
583 argument has the only occurrence.
584 2) The edge corresponding to the unique argument isn't critical edge.
586 Such PHI can be handled as PHIs have only two arguments. For example,
589 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
591 can be transformed into:
593 res = (predicate of e3) ? A_2 : A_1;
595 Return TRUE if it is the case, FALSE otherwise. */
598 phi_convertible_by_degenerating_args (gphi
*phi
)
601 tree arg
, t1
= NULL
, t2
= NULL
;
602 unsigned int i
, i1
= 0, i2
= 0, n1
= 0, n2
= 0;
603 unsigned int num_args
= gimple_phi_num_args (phi
);
605 gcc_assert (num_args
> 2);
607 for (i
= 0; i
< num_args
; i
++)
609 arg
= gimple_phi_arg_def (phi
, i
);
610 if (t1
== NULL
|| operand_equal_p (t1
, arg
, 0))
616 else if (t2
== NULL
|| operand_equal_p (t2
, arg
, 0))
626 if (n1
!= 1 && n2
!= 1)
629 /* Check if the edge corresponding to the unique arg is critical. */
630 e
= gimple_phi_arg_edge (phi
, (n1
== 1) ? i1
: i2
);
631 if (EDGE_COUNT (e
->src
->succs
) > 1)
637 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
638 and it belongs to basic block BB.
640 PHI is not if-convertible if:
641 - it has more than 2 arguments.
643 When the aggressive_if_conv is set, PHI can have more than
647 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
)
649 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
651 fprintf (dump_file
, "-------------------------\n");
652 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
655 if (bb
!= loop
->header
)
657 if (gimple_phi_num_args (phi
) > 2
658 && !aggressive_if_conv
659 && !phi_convertible_by_degenerating_args (phi
))
661 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
662 fprintf (dump_file
, "Phi can't be predicated by single cond.\n");
670 /* Records the status of a data reference. This struct is attached to
671 each DR->aux field. */
674 bool rw_unconditionally
;
675 bool w_unconditionally
;
676 bool written_at_least_once
;
680 tree base_w_predicate
;
683 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
684 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
685 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
686 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
688 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
689 HASH tables. While storing them in HASH table, it checks if the
690 reference is unconditionally read or written and stores that as a flag
691 information. For base reference it checks if it is written atlest once
692 unconditionally and stores it as flag information along with DR.
693 In other words for every data reference A in STMT there exist other
694 accesses to a data reference with the same base with predicates that
695 add up (OR-up) to the true predicate: this ensures that the data
696 reference A is touched (read or written) on every iteration of the
697 if-converted loop. */
699 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
702 data_reference_p
*master_dr
, *base_master_dr
;
703 tree base_ref
= DR_BASE_OBJECT (a
);
704 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
705 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
708 master_dr
= &innermost_DR_map
->get_or_insert (innermost
, &exist1
);
714 IFC_DR (*master_dr
)->w_predicate
715 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
716 IFC_DR (*master_dr
)->w_predicate
);
717 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
718 DR_W_UNCONDITIONALLY (*master_dr
) = true;
720 IFC_DR (*master_dr
)->rw_predicate
721 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
722 IFC_DR (*master_dr
)->rw_predicate
);
723 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
724 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
728 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
731 IFC_DR (*base_master_dr
)->base_w_predicate
732 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
733 IFC_DR (*base_master_dr
)->base_w_predicate
);
734 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
735 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
739 /* Return true when the memory references of STMT won't trap in the
740 if-converted code. There are two things that we have to check for:
742 - writes to memory occur to writable memory: if-conversion of
743 memory writes transforms the conditional memory writes into
744 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
745 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
746 be executed at all in the original code, it may be a readonly
747 memory. To check that A is not const-qualified, we check that
748 there exists at least an unconditional write to A in the current
751 - reads or writes to memory are valid memory accesses for every
752 iteration. To check that the memory accesses are correctly formed
753 and that we are allowed to read and write in these locations, we
754 check that the memory accesses to be if-converted occur at every
755 iteration unconditionally.
757 Returns true for the memory reference in STMT, same memory reference
758 is read or written unconditionally atleast once and the base memory
759 reference is written unconditionally once. This is to check reference
760 will not write fault. Also retuns true if the memory reference is
761 unconditionally read once then we are conditionally writing to memory
762 which is defined as read and write and is bound to the definition
765 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
767 data_reference_p
*master_dr
, *base_master_dr
;
768 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
770 tree base
= DR_BASE_OBJECT (a
);
771 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
773 gcc_assert (DR_STMT (a
) == stmt
);
774 gcc_assert (DR_BASE_ADDRESS (a
) || DR_OFFSET (a
)
775 || DR_INIT (a
) || DR_STEP (a
));
777 master_dr
= innermost_DR_map
->get (innermost
);
778 gcc_assert (master_dr
!= NULL
);
780 base_master_dr
= baseref_DR_map
->get (base
);
782 /* If a is unconditionally written to it doesn't trap. */
783 if (DR_W_UNCONDITIONALLY (*master_dr
))
786 /* If a is unconditionally accessed then ... */
787 if (DR_RW_UNCONDITIONALLY (*master_dr
))
789 /* an unconditional read won't trap. */
793 /* an unconditionaly write won't trap if the base is written
794 to unconditionally. */
796 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
797 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
800 /* or the base is know to be not readonly. */
801 tree base_tree
= get_base_address (DR_REF (a
));
802 if (DECL_P (base_tree
)
803 && decl_binds_to_current_def_p (base_tree
)
804 && ! TREE_READONLY (base_tree
))
805 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
811 /* Return true if STMT could be converted into a masked load or store
812 (conditional load or store based on a mask computed from bb predicate). */
815 ifcvt_can_use_mask_load_store (gimple
*stmt
)
819 basic_block bb
= gimple_bb (stmt
);
822 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
823 || bb
->loop_father
->dont_vectorize
824 || !gimple_assign_single_p (stmt
)
825 || gimple_has_volatile_ops (stmt
))
828 /* Check whether this is a load or store. */
829 lhs
= gimple_assign_lhs (stmt
);
830 if (gimple_store_p (stmt
))
832 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
837 else if (gimple_assign_load_p (stmt
))
840 ref
= gimple_assign_rhs1 (stmt
);
845 if (may_be_nonaddressable_p (ref
))
848 /* Mask should be integer mode of the same size as the load/store
850 mode
= TYPE_MODE (TREE_TYPE (lhs
));
851 if (int_mode_for_mode (mode
) == BLKmode
852 || VECTOR_MODE_P (mode
))
855 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
861 /* Return true when STMT is if-convertible.
863 GIMPLE_ASSIGN statement is not if-convertible if,
866 - LHS is not var decl. */
869 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
870 vec
<data_reference_p
> refs
,
871 bool *any_mask_load_store
)
873 tree lhs
= gimple_assign_lhs (stmt
);
875 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
877 fprintf (dump_file
, "-------------------------\n");
878 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
881 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
884 /* Some of these constrains might be too conservative. */
885 if (stmt_ends_bb_p (stmt
)
886 || gimple_has_volatile_ops (stmt
)
887 || (TREE_CODE (lhs
) == SSA_NAME
888 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
889 || gimple_has_side_effects (stmt
))
891 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
892 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
896 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
897 in between if_convertible_loop_p and combine_blocks
898 we can perform loop versioning. */
899 gimple_set_plf (stmt
, GF_PLF_2
, false);
901 if ((! gimple_vuse (stmt
)
902 || gimple_could_trap_p_1 (stmt
, false, false)
903 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
904 && gimple_could_trap_p (stmt
))
906 if (ifcvt_can_use_mask_load_store (stmt
))
908 gimple_set_plf (stmt
, GF_PLF_2
, true);
909 *any_mask_load_store
= true;
912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
913 fprintf (dump_file
, "tree could trap...\n");
917 /* When if-converting stores force versioning, likewise if we
918 ended up generating store data races. */
919 if (gimple_vdef (stmt
))
920 *any_mask_load_store
= true;
925 /* Return true when STMT is if-convertible.
927 A statement is if-convertible if:
928 - it is an if-convertible GIMPLE_ASSIGN,
929 - it is a GIMPLE_LABEL or a GIMPLE_COND,
930 - it is builtins call. */
933 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
,
934 bool *any_mask_load_store
)
936 switch (gimple_code (stmt
))
944 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
945 any_mask_load_store
);
949 tree fndecl
= gimple_call_fndecl (stmt
);
952 int flags
= gimple_call_flags (stmt
);
953 if ((flags
& ECF_CONST
)
954 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
955 /* We can only vectorize some builtins at the moment,
956 so restrict if-conversion to those. */
957 && DECL_BUILT_IN (fndecl
))
964 /* Don't know what to do with 'em so don't do anything. */
965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
967 fprintf (dump_file
, "don't know what to do\n");
968 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
977 /* Assumes that BB has more than 1 predecessors.
978 Returns false if at least one successor is not on critical edge
979 and true otherwise. */
982 all_preds_critical_p (basic_block bb
)
987 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
988 if (EDGE_COUNT (e
->src
->succs
) == 1)
993 /* Returns true if at least one successor in on critical edge. */
995 has_pred_critical_p (basic_block bb
)
1000 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1001 if (EDGE_COUNT (e
->src
->succs
) > 1)
1006 /* Return true when BB is if-convertible. This routine does not check
1007 basic block's statements and phis.
1009 A basic block is not if-convertible if:
1010 - it is non-empty and it is after the exit block (in BFS order),
1011 - it is after the exit block but before the latch,
1012 - its edges are not normal.
1014 Last restriction is valid if aggressive_if_conv is false.
1016 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1020 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
1025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1026 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1028 if (EDGE_COUNT (bb
->succs
) > 2)
1033 if (bb
!= loop
->latch
)
1035 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1036 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1039 else if (!empty_block_p (bb
))
1041 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1042 fprintf (dump_file
, "non empty basic block after exit bb\n");
1045 else if (bb
== loop
->latch
1047 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1050 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1055 /* Be less adventurous and handle only normal edges. */
1056 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1057 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1059 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1060 fprintf (dump_file
, "Difficult to handle edges\n");
1064 /* At least one incoming edge has to be non-critical as otherwise edge
1065 predicates are not equal to basic-block predicates of the edge
1066 source. This check is skipped if aggressive_if_conv is true. */
1067 if (!aggressive_if_conv
1068 && EDGE_COUNT (bb
->preds
) > 1
1069 && bb
!= loop
->header
1070 && all_preds_critical_p (bb
))
1072 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1073 fprintf (dump_file
, "only critical predecessors\n");
1080 /* Return true when all predecessor blocks of BB are visited. The
1081 VISITED bitmap keeps track of the visited blocks. */
1084 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1088 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1089 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1095 /* Get body of a LOOP in suitable order for if-conversion. It is
1096 caller's responsibility to deallocate basic block list.
1097 If-conversion suitable order is, breadth first sort (BFS) order
1098 with an additional constraint: select a block only if all its
1099 predecessors are already selected. */
1101 static basic_block
*
1102 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1104 basic_block
*blocks
, *blocks_in_bfs_order
;
1107 unsigned int index
= 0;
1108 unsigned int visited_count
= 0;
1110 gcc_assert (loop
->num_nodes
);
1111 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1113 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1114 visited
= BITMAP_ALLOC (NULL
);
1116 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1119 while (index
< loop
->num_nodes
)
1121 bb
= blocks_in_bfs_order
[index
];
1123 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1125 free (blocks_in_bfs_order
);
1126 BITMAP_FREE (visited
);
1131 if (!bitmap_bit_p (visited
, bb
->index
))
1133 if (pred_blocks_visited_p (bb
, &visited
)
1134 || bb
== loop
->header
)
1136 /* This block is now visited. */
1137 bitmap_set_bit (visited
, bb
->index
);
1138 blocks
[visited_count
++] = bb
;
1144 if (index
== loop
->num_nodes
1145 && visited_count
!= loop
->num_nodes
)
1149 free (blocks_in_bfs_order
);
1150 BITMAP_FREE (visited
);
1154 /* Returns true when the analysis of the predicates for all the basic
1155 blocks in LOOP succeeded.
1157 predicate_bbs first allocates the predicates of the basic blocks.
1158 These fields are then initialized with the tree expressions
1159 representing the predicates under which a basic block is executed
1160 in the LOOP. As the loop->header is executed at each iteration, it
1161 has the "true" predicate. Other statements executed under a
1162 condition are predicated with that condition, for example
1169 S1 will be predicated with "x", and
1170 S2 will be predicated with "!x". */
1173 predicate_bbs (loop_p loop
)
1177 for (i
= 0; i
< loop
->num_nodes
; i
++)
1178 init_bb_predicate (ifc_bbs
[i
]);
1180 for (i
= 0; i
< loop
->num_nodes
; i
++)
1182 basic_block bb
= ifc_bbs
[i
];
1186 /* The loop latch and loop exit block are always executed and
1187 have no extra conditions to be processed: skip them. */
1188 if (bb
== loop
->latch
1189 || bb_with_exit_edge_p (loop
, bb
))
1191 reset_bb_predicate (bb
);
1195 cond
= bb_predicate (bb
);
1196 stmt
= last_stmt (bb
);
1197 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1200 edge true_edge
, false_edge
;
1201 location_t loc
= gimple_location (stmt
);
1202 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1204 gimple_cond_lhs (stmt
),
1205 gimple_cond_rhs (stmt
));
1207 /* Add new condition into destination's predicate list. */
1208 extract_true_false_edges_from_block (gimple_bb (stmt
),
1209 &true_edge
, &false_edge
);
1211 /* If C is true, then TRUE_EDGE is taken. */
1212 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1215 /* If C is false, then FALSE_EDGE is taken. */
1216 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1218 add_to_dst_predicate_list (loop
, false_edge
,
1219 unshare_expr (cond
), c2
);
1224 /* If current bb has only one successor, then consider it as an
1225 unconditional goto. */
1226 if (single_succ_p (bb
))
1228 basic_block bb_n
= single_succ (bb
);
1230 /* The successor bb inherits the predicate of its
1231 predecessor. If there is no predicate in the predecessor
1232 bb, then consider the successor bb as always executed. */
1233 if (cond
== NULL_TREE
)
1234 cond
= boolean_true_node
;
1236 add_to_predicate_list (loop
, bb_n
, cond
);
1240 /* The loop header is always executed. */
1241 reset_bb_predicate (loop
->header
);
1242 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1243 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1246 /* Return true when LOOP is if-convertible. This is a helper function
1247 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1248 in if_convertible_loop_p. */
1251 if_convertible_loop_p_1 (struct loop
*loop
,
1252 vec
<data_reference_p
> *refs
,
1253 bool *any_mask_load_store
)
1256 basic_block exit_bb
= NULL
;
1258 if (find_data_references_in_loop (loop
, refs
) == chrec_dont_know
)
1261 calculate_dominance_info (CDI_DOMINATORS
);
1262 calculate_dominance_info (CDI_POST_DOMINATORS
);
1264 /* Allow statements that can be handled during if-conversion. */
1265 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1269 fprintf (dump_file
, "Irreducible loop\n");
1273 for (i
= 0; i
< loop
->num_nodes
; i
++)
1275 basic_block bb
= ifc_bbs
[i
];
1277 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1280 if (bb_with_exit_edge_p (loop
, bb
))
1284 for (i
= 0; i
< loop
->num_nodes
; i
++)
1286 basic_block bb
= ifc_bbs
[i
];
1287 gimple_stmt_iterator gsi
;
1289 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1290 switch (gimple_code (gsi_stmt (gsi
)))
1297 gimple_set_uid (gsi_stmt (gsi
), 0);
1304 data_reference_p dr
;
1307 = new hash_map
<innermost_loop_behavior_hash
, data_reference_p
>;
1308 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1310 predicate_bbs (loop
);
1312 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1314 tree ref
= DR_REF (dr
);
1316 dr
->aux
= XNEW (struct ifc_dr
);
1317 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1318 DR_RW_UNCONDITIONALLY (dr
) = false;
1319 DR_W_UNCONDITIONALLY (dr
) = false;
1320 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1321 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1322 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1323 if (gimple_uid (DR_STMT (dr
)) == 0)
1324 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1326 /* If DR doesn't have innermost loop behavior or it's a compound
1327 memory reference, we synthesize its innermost loop behavior
1329 if (TREE_CODE (ref
) == COMPONENT_REF
1330 || TREE_CODE (ref
) == IMAGPART_EXPR
1331 || TREE_CODE (ref
) == REALPART_EXPR
1332 || !(DR_BASE_ADDRESS (dr
) || DR_OFFSET (dr
)
1333 || DR_INIT (dr
) || DR_STEP (dr
)))
1335 while (TREE_CODE (ref
) == COMPONENT_REF
1336 || TREE_CODE (ref
) == IMAGPART_EXPR
1337 || TREE_CODE (ref
) == REALPART_EXPR
)
1338 ref
= TREE_OPERAND (ref
, 0);
1340 DR_BASE_ADDRESS (dr
) = ref
;
1341 DR_OFFSET (dr
) = NULL
;
1342 DR_INIT (dr
) = NULL
;
1343 DR_STEP (dr
) = NULL
;
1344 DR_ALIGNED_TO (dr
) = NULL
;
1346 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1349 for (i
= 0; i
< loop
->num_nodes
; i
++)
1351 basic_block bb
= ifc_bbs
[i
];
1352 gimple_stmt_iterator itr
;
1354 /* Check the if-convertibility of statements in predicated BBs. */
1355 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1356 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1357 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1358 any_mask_load_store
))
1362 for (i
= 0; i
< loop
->num_nodes
; i
++)
1363 free_bb_predicate (ifc_bbs
[i
]);
1365 /* Checking PHIs needs to be done after stmts, as the fact whether there
1366 are any masked loads or stores affects the tests. */
1367 for (i
= 0; i
< loop
->num_nodes
; i
++)
1369 basic_block bb
= ifc_bbs
[i
];
1372 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1373 if (!if_convertible_phi_p (loop
, bb
, itr
.phi ()))
1378 fprintf (dump_file
, "Applying if-conversion\n");
1383 /* Return true when LOOP is if-convertible.
1384 LOOP is if-convertible if:
1386 - it has two or more basic blocks,
1387 - it has only one exit,
1388 - loop header is not the exit edge,
1389 - if its basic blocks and phi nodes are if convertible. */
1392 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1397 vec
<data_reference_p
> refs
;
1399 /* Handle only innermost loop. */
1400 if (!loop
|| loop
->inner
)
1402 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1403 fprintf (dump_file
, "not innermost loop\n");
1407 /* If only one block, no need for if-conversion. */
1408 if (loop
->num_nodes
<= 2)
1410 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1411 fprintf (dump_file
, "less than 2 basic blocks\n");
1415 /* More than one loop exit is too much to handle. */
1416 if (!single_exit (loop
))
1418 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1419 fprintf (dump_file
, "multiple exits\n");
1423 /* If one of the loop header's edge is an exit edge then do not
1424 apply if-conversion. */
1425 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1426 if (loop_exit_edge_p (loop
, e
))
1430 res
= if_convertible_loop_p_1 (loop
, &refs
, any_mask_load_store
);
1432 data_reference_p dr
;
1434 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1437 free_data_refs (refs
);
1439 delete innermost_DR_map
;
1440 innermost_DR_map
= NULL
;
1442 delete baseref_DR_map
;
1443 baseref_DR_map
= NULL
;
1448 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1449 which is in predicated basic block.
1450 In fact, the following PHI pattern is searching:
1452 reduc_1 = PHI <..., reduc_2>
1456 reduc_2 = PHI <reduc_1, reduc_3>
1458 ARG_0 and ARG_1 are correspondent PHI arguments.
1459 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1460 EXTENDED is true if PHI has > 2 arguments. */
1463 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1464 tree
*op0
, tree
*op1
, bool extended
)
1466 tree lhs
, r_op1
, r_op2
;
1468 gimple
*header_phi
= NULL
;
1469 enum tree_code reduction_op
;
1470 basic_block bb
= gimple_bb (phi
);
1471 struct loop
*loop
= bb
->loop_father
;
1472 edge latch_e
= loop_latch_edge (loop
);
1473 imm_use_iterator imm_iter
;
1474 use_operand_p use_p
;
1477 bool result
= false;
1478 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1481 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1484 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1485 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1487 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1490 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1491 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1495 if (gimple_bb (header_phi
) != loop
->header
)
1498 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1501 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1502 || gimple_has_volatile_ops (stmt
))
1505 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1508 if (!is_predicated (gimple_bb (stmt
)))
1511 /* Check that stmt-block is predecessor of phi-block. */
1512 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1521 if (!has_single_use (lhs
))
1524 reduction_op
= gimple_assign_rhs_code (stmt
);
1525 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1527 r_op1
= gimple_assign_rhs1 (stmt
);
1528 r_op2
= gimple_assign_rhs2 (stmt
);
1530 /* Make R_OP1 to hold reduction variable. */
1531 if (r_op2
== PHI_RESULT (header_phi
)
1532 && reduction_op
== PLUS_EXPR
)
1533 std::swap (r_op1
, r_op2
);
1534 else if (r_op1
!= PHI_RESULT (header_phi
))
1537 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1538 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1540 gimple
*use_stmt
= USE_STMT (use_p
);
1541 if (is_gimple_debug (use_stmt
))
1543 if (use_stmt
== stmt
)
1545 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1549 *op0
= r_op1
; *op1
= r_op2
;
1554 /* Converts conditional scalar reduction into unconditional form, e.g.
1556 if (_5 != 0) goto bb_5 else goto bb_6
1562 # res_2 = PHI <res_13(4), res_6(5)>
1565 will be converted into sequence
1566 _ifc__1 = _5 != 0 ? 1 : 0;
1567 res_2 = res_13 + _ifc__1;
1568 Argument SWAP tells that arguments of conditional expression should be
1570 Returns rhs of resulting PHI assignment. */
1573 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1574 tree cond
, tree op0
, tree op1
, bool swap
)
1576 gimple_stmt_iterator stmt_it
;
1579 tree rhs1
= gimple_assign_rhs1 (reduc
);
1580 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1582 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1584 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1586 fprintf (dump_file
, "Found cond scalar reduction.\n");
1587 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1590 /* Build cond expression using COND and constant operand
1591 of reduction rhs. */
1592 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1593 unshare_expr (cond
),
1597 /* Create assignment stmt and insert it at GSI. */
1598 new_assign
= gimple_build_assign (tmp
, c
);
1599 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1600 /* Build rhs for unconditional increment/decrement. */
1601 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1602 TREE_TYPE (rhs1
), op0
, tmp
);
1604 /* Delete original reduction stmt. */
1605 stmt_it
= gsi_for_stmt (reduc
);
1606 gsi_remove (&stmt_it
, true);
1607 release_defs (reduc
);
1611 /* Produce condition for all occurrences of ARG in PHI node. */
1614 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1615 gimple_stmt_iterator
*gsi
)
1619 tree cond
= NULL_TREE
;
1623 len
= occur
->length ();
1624 gcc_assert (len
> 0);
1625 for (i
= 0; i
< len
; i
++)
1627 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1628 c
= bb_predicate (e
->src
);
1629 if (is_true_predicate (c
))
1631 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1632 is_gimple_condexpr
, NULL_TREE
,
1633 true, GSI_SAME_STMT
);
1634 if (cond
!= NULL_TREE
)
1636 /* Must build OR expression. */
1637 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1638 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1639 is_gimple_condexpr
, NULL_TREE
,
1640 true, GSI_SAME_STMT
);
1645 gcc_assert (cond
!= NULL_TREE
);
1649 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1650 This routine can handle PHI nodes with more than two arguments.
1653 S1: A = PHI <x1(1), x2(5)>
1655 S2: A = cond ? x1 : x2;
1657 The generated code is inserted at GSI that points to the top of
1658 basic block's statement list.
1659 If PHI node has more than two arguments a chain of conditional
1660 expression is produced. */
1664 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1666 gimple
*new_stmt
= NULL
, *reduc
;
1667 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1669 unsigned int index0
;
1670 unsigned int max
, args_len
;
1675 res
= gimple_phi_result (phi
);
1676 if (virtual_operand_p (res
))
1679 if ((rhs
= degenerate_phi_result (phi
))
1680 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1682 && !chrec_contains_undetermined (scev
)
1684 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1688 fprintf (dump_file
, "Degenerate phi!\n");
1689 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1691 new_stmt
= gimple_build_assign (res
, rhs
);
1692 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1693 update_stmt (new_stmt
);
1697 bb
= gimple_bb (phi
);
1698 if (EDGE_COUNT (bb
->preds
) == 2)
1700 /* Predicate ordinary PHI node with 2 arguments. */
1701 edge first_edge
, second_edge
;
1702 basic_block true_bb
;
1703 first_edge
= EDGE_PRED (bb
, 0);
1704 second_edge
= EDGE_PRED (bb
, 1);
1705 cond
= bb_predicate (first_edge
->src
);
1706 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1707 std::swap (first_edge
, second_edge
);
1708 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1710 cond
= bb_predicate (second_edge
->src
);
1711 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1712 cond
= TREE_OPERAND (cond
, 0);
1714 first_edge
= second_edge
;
1717 cond
= bb_predicate (first_edge
->src
);
1718 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1719 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1720 is_gimple_condexpr
, NULL_TREE
,
1721 true, GSI_SAME_STMT
);
1722 true_bb
= first_edge
->src
;
1723 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1725 arg0
= gimple_phi_arg_def (phi
, 1);
1726 arg1
= gimple_phi_arg_def (phi
, 0);
1730 arg0
= gimple_phi_arg_def (phi
, 0);
1731 arg1
= gimple_phi_arg_def (phi
, 1);
1733 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1735 /* Convert reduction stmt into vectorizable form. */
1736 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1737 true_bb
!= gimple_bb (reduc
));
1739 /* Build new RHS using selected condition and arguments. */
1740 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1742 new_stmt
= gimple_build_assign (res
, rhs
);
1743 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1744 update_stmt (new_stmt
);
1746 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1748 fprintf (dump_file
, "new phi replacement stmt\n");
1749 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1754 /* Create hashmap for PHI node which contain vector of argument indexes
1755 having the same value. */
1757 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1758 unsigned int num_args
= gimple_phi_num_args (phi
);
1760 /* Vector of different PHI argument values. */
1761 auto_vec
<tree
> args (num_args
);
1763 /* Compute phi_arg_map. */
1764 for (i
= 0; i
< num_args
; i
++)
1768 arg
= gimple_phi_arg_def (phi
, i
);
1769 if (!phi_arg_map
.get (arg
))
1770 args
.quick_push (arg
);
1771 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1774 /* Determine element with max number of occurrences. */
1777 args_len
= args
.length ();
1778 for (i
= 0; i
< args_len
; i
++)
1781 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1788 /* Put element with max number of occurences to the end of ARGS. */
1789 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1790 std::swap (args
[args_len
- 1], args
[max_ind
]);
1792 /* Handle one special case when number of arguments with different values
1793 is equal 2 and one argument has the only occurrence. Such PHI can be
1794 handled as if would have only 2 arguments. */
1795 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1798 indexes
= phi_arg_map
.get (args
[0]);
1799 index0
= (*indexes
)[0];
1802 e
= gimple_phi_arg_edge (phi
, index0
);
1803 cond
= bb_predicate (e
->src
);
1804 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1807 cond
= TREE_OPERAND (cond
, 0);
1809 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1810 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1811 is_gimple_condexpr
, NULL_TREE
,
1812 true, GSI_SAME_STMT
);
1813 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1815 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1819 /* Convert reduction stmt into vectorizable form. */
1820 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1822 new_stmt
= gimple_build_assign (res
, rhs
);
1823 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1824 update_stmt (new_stmt
);
1830 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1833 for (i
= 0; i
< args_len
; i
++)
1836 indexes
= phi_arg_map
.get (args
[i
]);
1837 if (i
!= args_len
- 1)
1838 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1841 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1842 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1844 new_stmt
= gimple_build_assign (lhs
, rhs
);
1845 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1846 update_stmt (new_stmt
);
1851 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1853 fprintf (dump_file
, "new extended phi replacement stmt\n");
1854 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1858 /* Replaces in LOOP all the scalar phi nodes other than those in the
1859 LOOP->header block with conditional modify expressions. */
1862 predicate_all_scalar_phis (struct loop
*loop
)
1865 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1868 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1871 gimple_stmt_iterator gsi
;
1872 gphi_iterator phi_gsi
;
1875 if (bb
== loop
->header
)
1878 phi_gsi
= gsi_start_phis (bb
);
1879 if (gsi_end_p (phi_gsi
))
1882 gsi
= gsi_after_labels (bb
);
1883 while (!gsi_end_p (phi_gsi
))
1885 phi
= phi_gsi
.phi ();
1886 predicate_scalar_phi (phi
, &gsi
);
1887 release_phi_node (phi
);
1888 gsi_next (&phi_gsi
);
1891 set_phi_nodes (bb
, NULL
);
1895 /* Insert in each basic block of LOOP the statements produced by the
1896 gimplification of the predicates. */
1899 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1903 for (i
= 0; i
< loop
->num_nodes
; i
++)
1905 basic_block bb
= ifc_bbs
[i
];
1907 if (!is_predicated (bb
))
1908 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1909 if (!is_predicated (bb
))
1911 /* Do not insert statements for a basic block that is not
1912 predicated. Also make sure that the predicate of the
1913 basic block is set to true. */
1914 reset_bb_predicate (bb
);
1918 stmts
= bb_predicate_gimplified_stmts (bb
);
1921 if (any_mask_load_store
)
1923 /* Insert the predicate of the BB just after the label,
1924 as the if-conversion of memory writes will use this
1926 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1927 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1931 /* Insert the predicate of the BB at the end of the BB
1932 as this would reduce the register pressure: the only
1933 use of this predicate will be in successor BBs. */
1934 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1937 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1938 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1940 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1943 /* Once the sequence is code generated, set it to NULL. */
1944 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1949 /* Helper function for predicate_mem_writes. Returns index of existent
1950 mask if it was created for given SIZE and -1 otherwise. */
1953 mask_exists (int size
, vec
<int> vec
)
1957 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1963 /* Predicate each write to memory in LOOP.
1965 This function transforms control flow constructs containing memory
1968 | for (i = 0; i < N; i++)
1972 into the following form that does not contain control flow:
1974 | for (i = 0; i < N; i++)
1975 | A[i] = cond ? expr : A[i];
1977 The original CFG looks like this:
1984 | if (i < N) goto bb_5 else goto bb_2
1988 | cond = some_computation;
1989 | if (cond) goto bb_3 else goto bb_4
2001 insert_gimplified_predicates inserts the computation of the COND
2002 expression at the beginning of the destination basic block:
2009 | if (i < N) goto bb_5 else goto bb_2
2013 | cond = some_computation;
2014 | if (cond) goto bb_3 else goto bb_4
2018 | cond = some_computation;
2027 predicate_mem_writes is then predicating the memory write as follows:
2034 | if (i < N) goto bb_5 else goto bb_2
2038 | if (cond) goto bb_3 else goto bb_4
2042 | cond = some_computation;
2043 | A[i] = cond ? expr : A[i];
2051 and finally combine_blocks removes the basic block boundaries making
2052 the loop vectorizable:
2056 | if (i < N) goto bb_5 else goto bb_1
2060 | cond = some_computation;
2061 | A[i] = cond ? expr : A[i];
2062 | if (i < N) goto bb_5 else goto bb_4
2071 predicate_mem_writes (loop_p loop
)
2073 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2074 auto_vec
<int, 1> vect_sizes
;
2075 auto_vec
<tree
, 1> vect_masks
;
2077 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2079 gimple_stmt_iterator gsi
;
2080 basic_block bb
= ifc_bbs
[i
];
2081 tree cond
= bb_predicate (bb
);
2086 if (is_true_predicate (cond
) || is_false_predicate (cond
))
2090 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2093 cond
= TREE_OPERAND (cond
, 0);
2096 vect_sizes
.truncate (0);
2097 vect_masks
.truncate (0);
2099 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2100 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2102 else if (gimple_plf (stmt
, GF_PLF_2
))
2104 tree lhs
= gimple_assign_lhs (stmt
);
2105 tree rhs
= gimple_assign_rhs1 (stmt
);
2106 tree ref
, addr
, ptr
, mask
;
2108 gimple_seq stmts
= NULL
;
2109 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2110 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2111 mark_addressable (ref
);
2112 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2113 true, NULL_TREE
, true,
2115 if (!vect_sizes
.is_empty ()
2116 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2117 /* Use created mask. */
2118 mask
= vect_masks
[index
];
2121 if (COMPARISON_CLASS_P (cond
))
2122 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2124 TREE_OPERAND (cond
, 0),
2125 TREE_OPERAND (cond
, 1));
2128 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2135 = constant_boolean_node (true, TREE_TYPE (mask
));
2136 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2137 TREE_TYPE (mask
), mask
, true_val
);
2139 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2141 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2142 /* Save mask and its size for further use. */
2143 vect_sizes
.safe_push (bitsize
);
2144 vect_masks
.safe_push (mask
);
2146 ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2147 get_object_alignment (ref
));
2148 /* Copy points-to info if possible. */
2149 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2150 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2152 if (TREE_CODE (lhs
) == SSA_NAME
)
2155 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2157 gimple_call_set_lhs (new_stmt
, lhs
);
2161 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2163 gsi_replace (&gsi
, new_stmt
, true);
2165 else if (gimple_vdef (stmt
))
2167 tree lhs
= gimple_assign_lhs (stmt
);
2168 tree rhs
= gimple_assign_rhs1 (stmt
);
2169 tree type
= TREE_TYPE (lhs
);
2171 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2172 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2174 std::swap (lhs
, rhs
);
2175 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2176 is_gimple_condexpr
, NULL_TREE
,
2177 true, GSI_SAME_STMT
);
2178 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2179 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2185 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2186 other than the exit and latch of the LOOP. Also resets the
2187 GIMPLE_DEBUG information. */
2190 remove_conditions_and_labels (loop_p loop
)
2192 gimple_stmt_iterator gsi
;
2195 for (i
= 0; i
< loop
->num_nodes
; i
++)
2197 basic_block bb
= ifc_bbs
[i
];
2199 if (bb_with_exit_edge_p (loop
, bb
)
2200 || bb
== loop
->latch
)
2203 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2204 switch (gimple_code (gsi_stmt (gsi
)))
2208 gsi_remove (&gsi
, true);
2212 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2213 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2215 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2216 update_stmt (gsi_stmt (gsi
));
2227 /* Combine all the basic blocks from LOOP into one or two super basic
2228 blocks. Replace PHI nodes with conditional modify expressions. */
2231 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2233 basic_block bb
, exit_bb
, merge_target_bb
;
2234 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2239 predicate_bbs (loop
);
2240 remove_conditions_and_labels (loop
);
2241 insert_gimplified_predicates (loop
, any_mask_load_store
);
2242 predicate_all_scalar_phis (loop
);
2244 if (any_mask_load_store
)
2245 predicate_mem_writes (loop
);
2247 /* Merge basic blocks: first remove all the edges in the loop,
2248 except for those from the exit block. */
2250 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2251 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2254 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2255 free_bb_predicate (bb
);
2256 if (bb_with_exit_edge_p (loop
, bb
))
2258 gcc_assert (exit_bb
== NULL
);
2262 gcc_assert (exit_bb
!= loop
->latch
);
2264 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2268 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2270 if (e
->src
== exit_bb
)
2277 if (exit_bb
!= NULL
)
2279 if (exit_bb
!= loop
->header
)
2281 /* Connect this node to loop header. */
2282 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2283 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2286 /* Redirect non-exit edges to loop->latch. */
2287 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2289 if (!loop_exit_edge_p (loop
, e
))
2290 redirect_edge_and_branch (e
, loop
->latch
);
2292 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2296 /* If the loop does not have an exit, reconnect header and latch. */
2297 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2298 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2301 merge_target_bb
= loop
->header
;
2302 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2304 gimple_stmt_iterator gsi
;
2305 gimple_stmt_iterator last
;
2309 if (bb
== exit_bb
|| bb
== loop
->latch
)
2312 /* Make stmts member of loop->header and clear range info from all stmts
2313 in BB which is now no longer executed conditional on a predicate we
2314 could have derived it from. */
2315 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2317 gimple
*stmt
= gsi_stmt (gsi
);
2318 gimple_set_bb (stmt
, merge_target_bb
);
2323 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2324 reset_flow_sensitive_info (op
);
2328 /* Update stmt list. */
2329 last
= gsi_last_bb (merge_target_bb
);
2330 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2331 set_bb_seq (bb
, NULL
);
2333 delete_basic_block (bb
);
2336 /* If possible, merge loop header to the block with the exit edge.
2337 This reduces the number of basic blocks to two, to please the
2338 vectorizer that handles only loops with two nodes. */
2340 && exit_bb
!= loop
->header
2341 && can_merge_blocks_p (loop
->header
, exit_bb
))
2342 merge_blocks (loop
->header
, exit_bb
);
2349 /* Version LOOP before if-converting it; the original loop
2350 will be if-converted, the new copy of the loop will not,
2351 and the LOOP_VECTORIZED internal call will be guarding which
2352 loop to execute. The vectorizer pass will fold this
2353 internal call into either true or false. */
2356 version_loop_for_if_conversion (struct loop
*loop
)
2358 basic_block cond_bb
;
2359 tree cond
= make_ssa_name (boolean_type_node
);
2360 struct loop
*new_loop
;
2362 gimple_stmt_iterator gsi
;
2364 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2365 build_int_cst (integer_type_node
, loop
->num
),
2367 gimple_call_set_lhs (g
, cond
);
2369 initialize_original_copy_tables ();
2370 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2371 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2372 REG_BR_PROB_BASE
, true);
2373 free_original_copy_tables ();
2374 if (new_loop
== NULL
)
2376 new_loop
->dont_vectorize
= true;
2377 new_loop
->force_vectorize
= false;
2378 gsi
= gsi_last_bb (cond_bb
);
2379 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2380 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2381 update_ssa (TODO_update_ssa
);
2385 /* Performs splitting of critical edges if aggressive_if_conv is true.
2386 Returns false if loop won't be if converted and true otherwise. */
2389 ifcvt_split_critical_edges (struct loop
*loop
)
2393 unsigned int num
= loop
->num_nodes
;
2403 if (!single_exit (loop
))
2406 body
= get_loop_body (loop
);
2407 for (i
= 0; i
< num
; i
++)
2410 if (bb
== loop
->latch
2411 || bb_with_exit_edge_p (loop
, bb
))
2413 stmt
= last_stmt (bb
);
2414 /* Skip basic blocks not ending with conditional branch. */
2415 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2417 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2418 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2425 /* Assumes that lhs of DEF_STMT have multiple uses.
2426 Delete one use by (1) creation of copy DEF_STMT with
2427 unique lhs; (2) change original use of lhs in one
2428 use statement with newly created lhs. */
2431 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2436 gimple_stmt_iterator gsi
;
2437 use_operand_p use_p
;
2438 imm_use_iterator imm_iter
;
2440 var
= gimple_assign_lhs (def_stmt
);
2441 copy_stmt
= gimple_copy (def_stmt
);
2442 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2443 gimple_assign_set_lhs (copy_stmt
, lhs
);
2444 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2445 /* Insert copy of DEF_STMT. */
2446 gsi
= gsi_for_stmt (def_stmt
);
2447 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2448 /* Change use of var to lhs in use_stmt. */
2449 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2451 fprintf (dump_file
, "Change use of var ");
2452 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2453 fprintf (dump_file
, " to ");
2454 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2455 fprintf (dump_file
, "\n");
2457 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2459 if (USE_STMT (use_p
) != use_stmt
)
2461 SET_USE (use_p
, lhs
);
2466 /* Traverse bool pattern recursively starting from VAR.
2467 Save its def and use statements to defuse_list if VAR does
2468 not have single use. */
2471 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2475 enum tree_code code
;
2478 def_stmt
= SSA_NAME_DEF_STMT (var
);
2479 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2481 if (!has_single_use (var
))
2483 /* Put def and use stmts into defuse_list. */
2484 defuse_list
->safe_push (def_stmt
);
2485 defuse_list
->safe_push (use_stmt
);
2486 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2488 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2489 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2492 rhs1
= gimple_assign_rhs1 (def_stmt
);
2493 code
= gimple_assign_rhs_code (def_stmt
);
2497 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2500 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2501 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2502 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2504 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2507 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2512 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2513 rhs2
= gimple_assign_rhs2 (def_stmt
);
2514 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2522 /* Returns true if STMT can be a root of bool pattern applied
2526 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2528 enum tree_code code
;
2531 code
= gimple_assign_rhs_code (stmt
);
2532 if (CONVERT_EXPR_CODE_P (code
))
2534 lhs
= gimple_assign_lhs (stmt
);
2535 rhs
= gimple_assign_rhs1 (stmt
);
2536 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2538 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2542 else if (code
== COND_EXPR
)
2544 rhs
= gimple_assign_rhs1 (stmt
);
2545 if (TREE_CODE (rhs
) != SSA_NAME
)
2552 /* Traverse all statements in BB which correspond to loop header to
2553 find out all statements which can start bool pattern applied by
2554 vectorizer and convert multiple uses in it to conform pattern
2555 restrictions. Such case can occur if the same predicate is used both
2556 for phi node conversion and load/store mask. */
2559 ifcvt_repair_bool_pattern (basic_block bb
)
2563 gimple_stmt_iterator gsi
;
2564 vec
<gimple
*> defuse_list
= vNULL
;
2565 vec
<gimple
*> pattern_roots
= vNULL
;
2570 /* Collect all root pattern statements. */
2571 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2573 stmt
= gsi_stmt (gsi
);
2574 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2576 if (!stmt_is_root_of_bool_pattern (stmt
))
2578 pattern_roots
.safe_push (stmt
);
2581 if (pattern_roots
.is_empty ())
2584 /* Split all statements with multiple uses iteratively since splitting
2585 may create new multiple uses. */
2590 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2592 rhs
= gimple_assign_rhs1 (stmt
);
2593 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2594 while (defuse_list
.length () > 0)
2597 gimple
*def_stmt
, *use_stmt
;
2598 use_stmt
= defuse_list
.pop ();
2599 def_stmt
= defuse_list
.pop ();
2600 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2605 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2606 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2610 /* Delete redundant statements produced by predication which prevents
2611 loop vectorization. */
2614 ifcvt_local_dce (basic_block bb
)
2619 gimple_stmt_iterator gsi
;
2620 auto_vec
<gimple
*> worklist
;
2621 enum gimple_code code
;
2622 use_operand_p use_p
;
2623 imm_use_iterator imm_iter
;
2625 worklist
.create (64);
2626 /* Consider all phi as live statements. */
2627 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2629 phi
= gsi_stmt (gsi
);
2630 gimple_set_plf (phi
, GF_PLF_2
, true);
2631 worklist
.safe_push (phi
);
2633 /* Consider load/store statements, CALL and COND as live. */
2634 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2636 stmt
= gsi_stmt (gsi
);
2637 if (gimple_store_p (stmt
)
2638 || gimple_assign_load_p (stmt
)
2639 || is_gimple_debug (stmt
))
2641 gimple_set_plf (stmt
, GF_PLF_2
, true);
2642 worklist
.safe_push (stmt
);
2645 code
= gimple_code (stmt
);
2646 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2648 gimple_set_plf (stmt
, GF_PLF_2
, true);
2649 worklist
.safe_push (stmt
);
2652 gimple_set_plf (stmt
, GF_PLF_2
, false);
2654 if (code
== GIMPLE_ASSIGN
)
2656 tree lhs
= gimple_assign_lhs (stmt
);
2657 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2659 stmt1
= USE_STMT (use_p
);
2660 if (gimple_bb (stmt1
) != bb
)
2662 gimple_set_plf (stmt
, GF_PLF_2
, true);
2663 worklist
.safe_push (stmt
);
2669 /* Propagate liveness through arguments of live stmt. */
2670 while (worklist
.length () > 0)
2673 use_operand_p use_p
;
2676 stmt
= worklist
.pop ();
2677 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2679 use
= USE_FROM_PTR (use_p
);
2680 if (TREE_CODE (use
) != SSA_NAME
)
2682 stmt1
= SSA_NAME_DEF_STMT (use
);
2683 if (gimple_bb (stmt1
) != bb
2684 || gimple_plf (stmt1
, GF_PLF_2
))
2686 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2687 worklist
.safe_push (stmt1
);
2690 /* Delete dead statements. */
2691 gsi
= gsi_start_bb (bb
);
2692 while (!gsi_end_p (gsi
))
2694 stmt
= gsi_stmt (gsi
);
2695 if (gimple_plf (stmt
, GF_PLF_2
))
2700 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2702 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2703 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2705 gsi_remove (&gsi
, true);
2706 release_defs (stmt
);
2710 /* If-convert LOOP when it is legal. For the moment this pass has no
2711 profitability analysis. Returns non-zero todo flags when something
2715 tree_if_conversion (struct loop
*loop
)
2717 unsigned int todo
= 0;
2719 bool any_mask_load_store
= false;
2721 /* Set up aggressive if-conversion for loops marked with simd pragma. */
2722 aggressive_if_conv
= loop
->force_vectorize
;
2723 /* Check either outer loop was marked with simd pragma. */
2724 if (!aggressive_if_conv
)
2726 struct loop
*outer_loop
= loop_outer (loop
);
2727 if (outer_loop
&& outer_loop
->force_vectorize
)
2728 aggressive_if_conv
= true;
2731 if (aggressive_if_conv
)
2732 if (!ifcvt_split_critical_edges (loop
))
2735 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2736 || !dbg_cnt (if_conversion_tree
))
2739 if (any_mask_load_store
2740 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2741 || loop
->dont_vectorize
))
2744 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2747 /* Now all statements are if-convertible. Combine all the basic
2748 blocks into one huge basic block doing the if-conversion
2750 combine_blocks (loop
, any_mask_load_store
);
2752 /* Delete dead predicate computations and repair tree correspondent
2753 to bool pattern to delete multiple uses of predicates. */
2754 if (aggressive_if_conv
)
2756 ifcvt_local_dce (loop
->header
);
2757 ifcvt_repair_bool_pattern (loop
->header
);
2760 todo
|= TODO_cleanup_cfg
;
2761 mark_virtual_operands_for_renaming (cfun
);
2762 todo
|= TODO_update_ssa_only_virtuals
;
2769 for (i
= 0; i
< loop
->num_nodes
; i
++)
2770 free_bb_predicate (ifc_bbs
[i
]);
2775 free_dominance_info (CDI_POST_DOMINATORS
);
2780 /* Tree if-conversion pass management. */
2784 const pass_data pass_data_if_conversion
=
2786 GIMPLE_PASS
, /* type */
2788 OPTGROUP_NONE
, /* optinfo_flags */
2789 TV_NONE
, /* tv_id */
2790 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2791 0, /* properties_provided */
2792 0, /* properties_destroyed */
2793 0, /* todo_flags_start */
2794 0, /* todo_flags_finish */
2797 class pass_if_conversion
: public gimple_opt_pass
2800 pass_if_conversion (gcc::context
*ctxt
)
2801 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2804 /* opt_pass methods: */
2805 virtual bool gate (function
*);
2806 virtual unsigned int execute (function
*);
2808 }; // class pass_if_conversion
2811 pass_if_conversion::gate (function
*fun
)
2813 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2814 && flag_tree_loop_if_convert
!= 0)
2815 || flag_tree_loop_if_convert
== 1
2816 || flag_tree_loop_if_convert_stores
== 1);
2820 pass_if_conversion::execute (function
*fun
)
2825 if (number_of_loops (fun
) <= 1)
2828 FOR_EACH_LOOP (loop
, 0)
2829 if (flag_tree_loop_if_convert
== 1
2830 || flag_tree_loop_if_convert_stores
== 1
2831 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2832 && !loop
->dont_vectorize
))
2833 todo
|= tree_if_conversion (loop
);
2838 FOR_EACH_BB_FN (bb
, fun
)
2839 gcc_assert (!bb
->aux
);
2848 make_pass_if_conversion (gcc::context
*ctxt
)
2850 return new pass_if_conversion (ctxt
);