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 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
579 and it belongs to basic block BB.
581 PHI is not if-convertible if:
582 - it has more than 2 arguments.
584 When we didn't see if-convertible stores, PHI is not
586 - a virtual PHI is immediately used in another PHI node,
587 - there is a virtual PHI in a BB other than the loop->header.
588 When the aggressive_if_conv is set, PHI can have more than
592 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
,
593 bool any_mask_load_store
)
595 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
597 fprintf (dump_file
, "-------------------------\n");
598 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
601 if (bb
!= loop
->header
)
603 if (gimple_phi_num_args (phi
) != 2
604 && !aggressive_if_conv
)
606 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
607 fprintf (dump_file
, "More than two phi node args.\n");
612 if (any_mask_load_store
)
615 /* When there were no if-convertible stores, check
616 that there are no memory writes in the branches of the loop to be
618 if (virtual_operand_p (gimple_phi_result (phi
)))
620 imm_use_iterator imm_iter
;
623 if (bb
!= loop
->header
)
625 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
626 fprintf (dump_file
, "Virtual phi not on loop->header.\n");
630 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, gimple_phi_result (phi
))
632 if (gimple_code (USE_STMT (use_p
)) == GIMPLE_PHI
633 && USE_STMT (use_p
) != phi
)
635 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
636 fprintf (dump_file
, "Difficult to handle this virtual phi.\n");
645 /* Records the status of a data reference. This struct is attached to
646 each DR->aux field. */
649 bool rw_unconditionally
;
650 bool w_unconditionally
;
651 bool written_at_least_once
;
655 tree base_w_predicate
;
658 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
659 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
660 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
661 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
663 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
664 HASH tables. While storing them in HASH table, it checks if the
665 reference is unconditionally read or written and stores that as a flag
666 information. For base reference it checks if it is written atlest once
667 unconditionally and stores it as flag information along with DR.
668 In other words for every data reference A in STMT there exist other
669 accesses to a data reference with the same base with predicates that
670 add up (OR-up) to the true predicate: this ensures that the data
671 reference A is touched (read or written) on every iteration of the
672 if-converted loop. */
674 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
677 data_reference_p
*master_dr
, *base_master_dr
;
678 tree base_ref
= DR_BASE_OBJECT (a
);
679 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
680 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
683 master_dr
= &innermost_DR_map
->get_or_insert (innermost
, &exist1
);
689 IFC_DR (*master_dr
)->w_predicate
690 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
691 IFC_DR (*master_dr
)->w_predicate
);
692 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
693 DR_W_UNCONDITIONALLY (*master_dr
) = true;
695 IFC_DR (*master_dr
)->rw_predicate
696 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
697 IFC_DR (*master_dr
)->rw_predicate
);
698 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
699 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
703 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
706 IFC_DR (*base_master_dr
)->base_w_predicate
707 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
708 IFC_DR (*base_master_dr
)->base_w_predicate
);
709 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
710 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
714 /* Return true when the memory references of STMT won't trap in the
715 if-converted code. There are two things that we have to check for:
717 - writes to memory occur to writable memory: if-conversion of
718 memory writes transforms the conditional memory writes into
719 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
720 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
721 be executed at all in the original code, it may be a readonly
722 memory. To check that A is not const-qualified, we check that
723 there exists at least an unconditional write to A in the current
726 - reads or writes to memory are valid memory accesses for every
727 iteration. To check that the memory accesses are correctly formed
728 and that we are allowed to read and write in these locations, we
729 check that the memory accesses to be if-converted occur at every
730 iteration unconditionally.
732 Returns true for the memory reference in STMT, same memory reference
733 is read or written unconditionally atleast once and the base memory
734 reference is written unconditionally once. This is to check reference
735 will not write fault. Also retuns true if the memory reference is
736 unconditionally read once then we are conditionally writing to memory
737 which is defined as read and write and is bound to the definition
740 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
742 data_reference_p
*master_dr
, *base_master_dr
;
743 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
745 tree base
= DR_BASE_OBJECT (a
);
746 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
748 gcc_assert (DR_STMT (a
) == stmt
);
749 gcc_assert (DR_BASE_ADDRESS (a
) || DR_OFFSET (a
)
750 || DR_INIT (a
) || DR_STEP (a
));
752 master_dr
= innermost_DR_map
->get (innermost
);
753 gcc_assert (master_dr
!= NULL
);
755 base_master_dr
= baseref_DR_map
->get (base
);
757 /* If a is unconditionally written to it doesn't trap. */
758 if (DR_W_UNCONDITIONALLY (*master_dr
))
761 /* If a is unconditionally accessed then ... */
762 if (DR_RW_UNCONDITIONALLY (*master_dr
))
764 /* an unconditional read won't trap. */
768 /* an unconditionaly write won't trap if the base is written
769 to unconditionally. */
771 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
772 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
775 /* or the base is know to be not readonly. */
776 tree base_tree
= get_base_address (DR_REF (a
));
777 if (DECL_P (base_tree
)
778 && decl_binds_to_current_def_p (base_tree
)
779 && ! TREE_READONLY (base_tree
))
780 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
786 /* Return true if STMT could be converted into a masked load or store
787 (conditional load or store based on a mask computed from bb predicate). */
790 ifcvt_can_use_mask_load_store (gimple
*stmt
)
794 basic_block bb
= gimple_bb (stmt
);
797 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
798 || bb
->loop_father
->dont_vectorize
799 || !gimple_assign_single_p (stmt
)
800 || gimple_has_volatile_ops (stmt
))
803 /* Check whether this is a load or store. */
804 lhs
= gimple_assign_lhs (stmt
);
805 if (gimple_store_p (stmt
))
807 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
812 else if (gimple_assign_load_p (stmt
))
815 ref
= gimple_assign_rhs1 (stmt
);
820 if (may_be_nonaddressable_p (ref
))
823 /* Mask should be integer mode of the same size as the load/store
825 mode
= TYPE_MODE (TREE_TYPE (lhs
));
826 if (int_mode_for_mode (mode
) == BLKmode
827 || VECTOR_MODE_P (mode
))
830 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
836 /* Return true when STMT is if-convertible.
838 GIMPLE_ASSIGN statement is not if-convertible if,
841 - LHS is not var decl. */
844 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
845 vec
<data_reference_p
> refs
,
846 bool *any_mask_load_store
)
848 tree lhs
= gimple_assign_lhs (stmt
);
850 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
852 fprintf (dump_file
, "-------------------------\n");
853 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
856 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
859 /* Some of these constrains might be too conservative. */
860 if (stmt_ends_bb_p (stmt
)
861 || gimple_has_volatile_ops (stmt
)
862 || (TREE_CODE (lhs
) == SSA_NAME
863 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
864 || gimple_has_side_effects (stmt
))
866 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
867 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
871 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
872 in between if_convertible_loop_p and combine_blocks
873 we can perform loop versioning. */
874 gimple_set_plf (stmt
, GF_PLF_2
, false);
876 if ((! gimple_vuse (stmt
)
877 || gimple_could_trap_p_1 (stmt
, false, false)
878 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
879 && gimple_could_trap_p (stmt
))
881 if (ifcvt_can_use_mask_load_store (stmt
))
883 gimple_set_plf (stmt
, GF_PLF_2
, true);
884 *any_mask_load_store
= true;
887 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
888 fprintf (dump_file
, "tree could trap...\n");
892 /* When if-converting stores force versioning, likewise if we
893 ended up generating store data races. */
894 if (gimple_vdef (stmt
))
895 *any_mask_load_store
= true;
900 /* Return true when STMT is if-convertible.
902 A statement is if-convertible if:
903 - it is an if-convertible GIMPLE_ASSIGN,
904 - it is a GIMPLE_LABEL or a GIMPLE_COND,
905 - it is builtins call. */
908 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
,
909 bool *any_mask_load_store
)
911 switch (gimple_code (stmt
))
919 return if_convertible_gimple_assign_stmt_p (stmt
, refs
,
920 any_mask_load_store
);
924 tree fndecl
= gimple_call_fndecl (stmt
);
927 int flags
= gimple_call_flags (stmt
);
928 if ((flags
& ECF_CONST
)
929 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
930 /* We can only vectorize some builtins at the moment,
931 so restrict if-conversion to those. */
932 && DECL_BUILT_IN (fndecl
))
939 /* Don't know what to do with 'em so don't do anything. */
940 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
942 fprintf (dump_file
, "don't know what to do\n");
943 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
952 /* Assumes that BB has more than 1 predecessors.
953 Returns false if at least one successor is not on critical edge
954 and true otherwise. */
957 all_preds_critical_p (basic_block bb
)
962 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
963 if (EDGE_COUNT (e
->src
->succs
) == 1)
968 /* Returns true if at least one successor in on critical edge. */
970 has_pred_critical_p (basic_block bb
)
975 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
976 if (EDGE_COUNT (e
->src
->succs
) > 1)
981 /* Return true when BB is if-convertible. This routine does not check
982 basic block's statements and phis.
984 A basic block is not if-convertible if:
985 - it is non-empty and it is after the exit block (in BFS order),
986 - it is after the exit block but before the latch,
987 - its edges are not normal.
989 Last restriction is valid if aggressive_if_conv is false.
991 EXIT_BB is the basic block containing the exit of the LOOP. BB is
995 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
1000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1001 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1003 if (EDGE_COUNT (bb
->succs
) > 2)
1006 if (EDGE_COUNT (bb
->preds
) > 2
1007 && !aggressive_if_conv
)
1012 if (bb
!= loop
->latch
)
1014 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1015 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1018 else if (!empty_block_p (bb
))
1020 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1021 fprintf (dump_file
, "non empty basic block after exit bb\n");
1024 else if (bb
== loop
->latch
1026 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1028 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1029 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1034 /* Be less adventurous and handle only normal edges. */
1035 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1036 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1038 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1039 fprintf (dump_file
, "Difficult to handle edges\n");
1043 /* At least one incoming edge has to be non-critical as otherwise edge
1044 predicates are not equal to basic-block predicates of the edge
1045 source. This check is skipped if aggressive_if_conv is true. */
1046 if (!aggressive_if_conv
1047 && EDGE_COUNT (bb
->preds
) > 1
1048 && bb
!= loop
->header
1049 && all_preds_critical_p (bb
))
1051 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1052 fprintf (dump_file
, "only critical predecessors\n");
1059 /* Return true when all predecessor blocks of BB are visited. The
1060 VISITED bitmap keeps track of the visited blocks. */
1063 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1067 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1068 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1074 /* Get body of a LOOP in suitable order for if-conversion. It is
1075 caller's responsibility to deallocate basic block list.
1076 If-conversion suitable order is, breadth first sort (BFS) order
1077 with an additional constraint: select a block only if all its
1078 predecessors are already selected. */
1080 static basic_block
*
1081 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1083 basic_block
*blocks
, *blocks_in_bfs_order
;
1086 unsigned int index
= 0;
1087 unsigned int visited_count
= 0;
1089 gcc_assert (loop
->num_nodes
);
1090 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1092 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1093 visited
= BITMAP_ALLOC (NULL
);
1095 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1098 while (index
< loop
->num_nodes
)
1100 bb
= blocks_in_bfs_order
[index
];
1102 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1104 free (blocks_in_bfs_order
);
1105 BITMAP_FREE (visited
);
1110 if (!bitmap_bit_p (visited
, bb
->index
))
1112 if (pred_blocks_visited_p (bb
, &visited
)
1113 || bb
== loop
->header
)
1115 /* This block is now visited. */
1116 bitmap_set_bit (visited
, bb
->index
);
1117 blocks
[visited_count
++] = bb
;
1123 if (index
== loop
->num_nodes
1124 && visited_count
!= loop
->num_nodes
)
1128 free (blocks_in_bfs_order
);
1129 BITMAP_FREE (visited
);
1133 /* Returns true when the analysis of the predicates for all the basic
1134 blocks in LOOP succeeded.
1136 predicate_bbs first allocates the predicates of the basic blocks.
1137 These fields are then initialized with the tree expressions
1138 representing the predicates under which a basic block is executed
1139 in the LOOP. As the loop->header is executed at each iteration, it
1140 has the "true" predicate. Other statements executed under a
1141 condition are predicated with that condition, for example
1148 S1 will be predicated with "x", and
1149 S2 will be predicated with "!x". */
1152 predicate_bbs (loop_p loop
)
1156 for (i
= 0; i
< loop
->num_nodes
; i
++)
1157 init_bb_predicate (ifc_bbs
[i
]);
1159 for (i
= 0; i
< loop
->num_nodes
; i
++)
1161 basic_block bb
= ifc_bbs
[i
];
1165 /* The loop latch and loop exit block are always executed and
1166 have no extra conditions to be processed: skip them. */
1167 if (bb
== loop
->latch
1168 || bb_with_exit_edge_p (loop
, bb
))
1170 reset_bb_predicate (bb
);
1174 cond
= bb_predicate (bb
);
1175 stmt
= last_stmt (bb
);
1176 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1179 edge true_edge
, false_edge
;
1180 location_t loc
= gimple_location (stmt
);
1181 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1183 gimple_cond_lhs (stmt
),
1184 gimple_cond_rhs (stmt
));
1186 /* Add new condition into destination's predicate list. */
1187 extract_true_false_edges_from_block (gimple_bb (stmt
),
1188 &true_edge
, &false_edge
);
1190 /* If C is true, then TRUE_EDGE is taken. */
1191 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1194 /* If C is false, then FALSE_EDGE is taken. */
1195 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1197 add_to_dst_predicate_list (loop
, false_edge
,
1198 unshare_expr (cond
), c2
);
1203 /* If current bb has only one successor, then consider it as an
1204 unconditional goto. */
1205 if (single_succ_p (bb
))
1207 basic_block bb_n
= single_succ (bb
);
1209 /* The successor bb inherits the predicate of its
1210 predecessor. If there is no predicate in the predecessor
1211 bb, then consider the successor bb as always executed. */
1212 if (cond
== NULL_TREE
)
1213 cond
= boolean_true_node
;
1215 add_to_predicate_list (loop
, bb_n
, cond
);
1219 /* The loop header is always executed. */
1220 reset_bb_predicate (loop
->header
);
1221 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1222 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1225 /* Return true when LOOP is if-convertible. This is a helper function
1226 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1227 in if_convertible_loop_p. */
1230 if_convertible_loop_p_1 (struct loop
*loop
,
1231 vec
<data_reference_p
> *refs
,
1232 bool *any_mask_load_store
)
1235 basic_block exit_bb
= NULL
;
1237 if (find_data_references_in_loop (loop
, refs
) == chrec_dont_know
)
1240 calculate_dominance_info (CDI_DOMINATORS
);
1241 calculate_dominance_info (CDI_POST_DOMINATORS
);
1243 /* Allow statements that can be handled during if-conversion. */
1244 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1247 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1248 fprintf (dump_file
, "Irreducible loop\n");
1252 for (i
= 0; i
< loop
->num_nodes
; i
++)
1254 basic_block bb
= ifc_bbs
[i
];
1256 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1259 if (bb_with_exit_edge_p (loop
, bb
))
1263 for (i
= 0; i
< loop
->num_nodes
; i
++)
1265 basic_block bb
= ifc_bbs
[i
];
1266 gimple_stmt_iterator gsi
;
1268 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1269 switch (gimple_code (gsi_stmt (gsi
)))
1276 gimple_set_uid (gsi_stmt (gsi
), 0);
1283 data_reference_p dr
;
1286 = new hash_map
<innermost_loop_behavior_hash
, data_reference_p
>;
1287 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1289 predicate_bbs (loop
);
1291 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1293 tree ref
= DR_REF (dr
);
1295 dr
->aux
= XNEW (struct ifc_dr
);
1296 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1297 DR_RW_UNCONDITIONALLY (dr
) = false;
1298 DR_W_UNCONDITIONALLY (dr
) = false;
1299 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1300 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1301 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1302 if (gimple_uid (DR_STMT (dr
)) == 0)
1303 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1305 /* If DR doesn't have innermost loop behavior or it's a compound
1306 memory reference, we synthesize its innermost loop behavior
1308 if (TREE_CODE (ref
) == COMPONENT_REF
1309 || TREE_CODE (ref
) == IMAGPART_EXPR
1310 || TREE_CODE (ref
) == REALPART_EXPR
1311 || !(DR_BASE_ADDRESS (dr
) || DR_OFFSET (dr
)
1312 || DR_INIT (dr
) || DR_STEP (dr
)))
1314 while (TREE_CODE (ref
) == COMPONENT_REF
1315 || TREE_CODE (ref
) == IMAGPART_EXPR
1316 || TREE_CODE (ref
) == REALPART_EXPR
)
1317 ref
= TREE_OPERAND (ref
, 0);
1319 DR_BASE_ADDRESS (dr
) = ref
;
1320 DR_OFFSET (dr
) = NULL
;
1321 DR_INIT (dr
) = NULL
;
1322 DR_STEP (dr
) = NULL
;
1323 DR_ALIGNED_TO (dr
) = NULL
;
1325 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1328 for (i
= 0; i
< loop
->num_nodes
; i
++)
1330 basic_block bb
= ifc_bbs
[i
];
1331 gimple_stmt_iterator itr
;
1333 /* Check the if-convertibility of statements in predicated BBs. */
1334 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1335 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1336 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
,
1337 any_mask_load_store
))
1341 for (i
= 0; i
< loop
->num_nodes
; i
++)
1342 free_bb_predicate (ifc_bbs
[i
]);
1344 /* Checking PHIs needs to be done after stmts, as the fact whether there
1345 are any masked loads or stores affects the tests. */
1346 for (i
= 0; i
< loop
->num_nodes
; i
++)
1348 basic_block bb
= ifc_bbs
[i
];
1351 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1352 if (!if_convertible_phi_p (loop
, bb
, itr
.phi (),
1353 *any_mask_load_store
))
1358 fprintf (dump_file
, "Applying if-conversion\n");
1363 /* Return true when LOOP is if-convertible.
1364 LOOP is if-convertible if:
1366 - it has two or more basic blocks,
1367 - it has only one exit,
1368 - loop header is not the exit edge,
1369 - if its basic blocks and phi nodes are if convertible. */
1372 if_convertible_loop_p (struct loop
*loop
, bool *any_mask_load_store
)
1377 vec
<data_reference_p
> refs
;
1379 /* Handle only innermost loop. */
1380 if (!loop
|| loop
->inner
)
1382 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1383 fprintf (dump_file
, "not innermost loop\n");
1387 /* If only one block, no need for if-conversion. */
1388 if (loop
->num_nodes
<= 2)
1390 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1391 fprintf (dump_file
, "less than 2 basic blocks\n");
1395 /* More than one loop exit is too much to handle. */
1396 if (!single_exit (loop
))
1398 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1399 fprintf (dump_file
, "multiple exits\n");
1403 /* If one of the loop header's edge is an exit edge then do not
1404 apply if-conversion. */
1405 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1406 if (loop_exit_edge_p (loop
, e
))
1410 res
= if_convertible_loop_p_1 (loop
, &refs
, any_mask_load_store
);
1412 data_reference_p dr
;
1414 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1417 free_data_refs (refs
);
1419 delete innermost_DR_map
;
1420 innermost_DR_map
= NULL
;
1422 delete baseref_DR_map
;
1423 baseref_DR_map
= NULL
;
1428 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1429 which is in predicated basic block.
1430 In fact, the following PHI pattern is searching:
1432 reduc_1 = PHI <..., reduc_2>
1436 reduc_2 = PHI <reduc_1, reduc_3>
1438 ARG_0 and ARG_1 are correspondent PHI arguments.
1439 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1440 EXTENDED is true if PHI has > 2 arguments. */
1443 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1444 tree
*op0
, tree
*op1
, bool extended
)
1446 tree lhs
, r_op1
, r_op2
;
1448 gimple
*header_phi
= NULL
;
1449 enum tree_code reduction_op
;
1450 basic_block bb
= gimple_bb (phi
);
1451 struct loop
*loop
= bb
->loop_father
;
1452 edge latch_e
= loop_latch_edge (loop
);
1453 imm_use_iterator imm_iter
;
1454 use_operand_p use_p
;
1457 bool result
= false;
1458 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1461 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1464 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1465 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1467 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1470 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1471 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1475 if (gimple_bb (header_phi
) != loop
->header
)
1478 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1481 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1482 || gimple_has_volatile_ops (stmt
))
1485 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1488 if (!is_predicated (gimple_bb (stmt
)))
1491 /* Check that stmt-block is predecessor of phi-block. */
1492 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1501 if (!has_single_use (lhs
))
1504 reduction_op
= gimple_assign_rhs_code (stmt
);
1505 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1507 r_op1
= gimple_assign_rhs1 (stmt
);
1508 r_op2
= gimple_assign_rhs2 (stmt
);
1510 /* Make R_OP1 to hold reduction variable. */
1511 if (r_op2
== PHI_RESULT (header_phi
)
1512 && reduction_op
== PLUS_EXPR
)
1513 std::swap (r_op1
, r_op2
);
1514 else if (r_op1
!= PHI_RESULT (header_phi
))
1517 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1518 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1520 gimple
*use_stmt
= USE_STMT (use_p
);
1521 if (is_gimple_debug (use_stmt
))
1523 if (use_stmt
== stmt
)
1525 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1529 *op0
= r_op1
; *op1
= r_op2
;
1534 /* Converts conditional scalar reduction into unconditional form, e.g.
1536 if (_5 != 0) goto bb_5 else goto bb_6
1542 # res_2 = PHI <res_13(4), res_6(5)>
1545 will be converted into sequence
1546 _ifc__1 = _5 != 0 ? 1 : 0;
1547 res_2 = res_13 + _ifc__1;
1548 Argument SWAP tells that arguments of conditional expression should be
1550 Returns rhs of resulting PHI assignment. */
1553 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1554 tree cond
, tree op0
, tree op1
, bool swap
)
1556 gimple_stmt_iterator stmt_it
;
1559 tree rhs1
= gimple_assign_rhs1 (reduc
);
1560 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1562 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1564 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1566 fprintf (dump_file
, "Found cond scalar reduction.\n");
1567 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1570 /* Build cond expression using COND and constant operand
1571 of reduction rhs. */
1572 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1573 unshare_expr (cond
),
1577 /* Create assignment stmt and insert it at GSI. */
1578 new_assign
= gimple_build_assign (tmp
, c
);
1579 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1580 /* Build rhs for unconditional increment/decrement. */
1581 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1582 TREE_TYPE (rhs1
), op0
, tmp
);
1584 /* Delete original reduction stmt. */
1585 stmt_it
= gsi_for_stmt (reduc
);
1586 gsi_remove (&stmt_it
, true);
1587 release_defs (reduc
);
1591 /* Produce condition for all occurrences of ARG in PHI node. */
1594 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1595 gimple_stmt_iterator
*gsi
)
1599 tree cond
= NULL_TREE
;
1603 len
= occur
->length ();
1604 gcc_assert (len
> 0);
1605 for (i
= 0; i
< len
; i
++)
1607 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1608 c
= bb_predicate (e
->src
);
1609 if (is_true_predicate (c
))
1611 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1612 is_gimple_condexpr
, NULL_TREE
,
1613 true, GSI_SAME_STMT
);
1614 if (cond
!= NULL_TREE
)
1616 /* Must build OR expression. */
1617 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1618 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1619 is_gimple_condexpr
, NULL_TREE
,
1620 true, GSI_SAME_STMT
);
1625 gcc_assert (cond
!= NULL_TREE
);
1629 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1630 This routine can handle PHI nodes with more than two arguments.
1633 S1: A = PHI <x1(1), x2(5)>
1635 S2: A = cond ? x1 : x2;
1637 The generated code is inserted at GSI that points to the top of
1638 basic block's statement list.
1639 If PHI node has more than two arguments a chain of conditional
1640 expression is produced. */
1644 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1646 gimple
*new_stmt
= NULL
, *reduc
;
1647 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1649 unsigned int index0
;
1650 unsigned int max
, args_len
;
1655 res
= gimple_phi_result (phi
);
1656 if (virtual_operand_p (res
))
1659 if ((rhs
= degenerate_phi_result (phi
))
1660 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1662 && !chrec_contains_undetermined (scev
)
1664 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1666 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1668 fprintf (dump_file
, "Degenerate phi!\n");
1669 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1671 new_stmt
= gimple_build_assign (res
, rhs
);
1672 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1673 update_stmt (new_stmt
);
1677 bb
= gimple_bb (phi
);
1678 if (EDGE_COUNT (bb
->preds
) == 2)
1680 /* Predicate ordinary PHI node with 2 arguments. */
1681 edge first_edge
, second_edge
;
1682 basic_block true_bb
;
1683 first_edge
= EDGE_PRED (bb
, 0);
1684 second_edge
= EDGE_PRED (bb
, 1);
1685 cond
= bb_predicate (first_edge
->src
);
1686 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1687 std::swap (first_edge
, second_edge
);
1688 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1690 cond
= bb_predicate (second_edge
->src
);
1691 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1692 cond
= TREE_OPERAND (cond
, 0);
1694 first_edge
= second_edge
;
1697 cond
= bb_predicate (first_edge
->src
);
1698 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1699 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1700 is_gimple_condexpr
, NULL_TREE
,
1701 true, GSI_SAME_STMT
);
1702 true_bb
= first_edge
->src
;
1703 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1705 arg0
= gimple_phi_arg_def (phi
, 1);
1706 arg1
= gimple_phi_arg_def (phi
, 0);
1710 arg0
= gimple_phi_arg_def (phi
, 0);
1711 arg1
= gimple_phi_arg_def (phi
, 1);
1713 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1715 /* Convert reduction stmt into vectorizable form. */
1716 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1717 true_bb
!= gimple_bb (reduc
));
1719 /* Build new RHS using selected condition and arguments. */
1720 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1722 new_stmt
= gimple_build_assign (res
, rhs
);
1723 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1724 update_stmt (new_stmt
);
1726 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1728 fprintf (dump_file
, "new phi replacement stmt\n");
1729 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1734 /* Create hashmap for PHI node which contain vector of argument indexes
1735 having the same value. */
1737 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1738 unsigned int num_args
= gimple_phi_num_args (phi
);
1740 /* Vector of different PHI argument values. */
1741 auto_vec
<tree
> args (num_args
);
1743 /* Compute phi_arg_map. */
1744 for (i
= 0; i
< num_args
; i
++)
1748 arg
= gimple_phi_arg_def (phi
, i
);
1749 if (!phi_arg_map
.get (arg
))
1750 args
.quick_push (arg
);
1751 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1754 /* Determine element with max number of occurrences. */
1757 args_len
= args
.length ();
1758 for (i
= 0; i
< args_len
; i
++)
1761 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1768 /* Put element with max number of occurences to the end of ARGS. */
1769 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1770 std::swap (args
[args_len
- 1], args
[max_ind
]);
1772 /* Handle one special case when number of arguments with different values
1773 is equal 2 and one argument has the only occurrence. Such PHI can be
1774 handled as if would have only 2 arguments. */
1775 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1778 indexes
= phi_arg_map
.get (args
[0]);
1779 index0
= (*indexes
)[0];
1782 e
= gimple_phi_arg_edge (phi
, index0
);
1783 cond
= bb_predicate (e
->src
);
1784 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1787 cond
= TREE_OPERAND (cond
, 0);
1789 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1790 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1791 is_gimple_condexpr
, NULL_TREE
,
1792 true, GSI_SAME_STMT
);
1793 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1795 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1799 /* Convert reduction stmt into vectorizable form. */
1800 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1802 new_stmt
= gimple_build_assign (res
, rhs
);
1803 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1804 update_stmt (new_stmt
);
1810 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1813 for (i
= 0; i
< args_len
; i
++)
1816 indexes
= phi_arg_map
.get (args
[i
]);
1817 if (i
!= args_len
- 1)
1818 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1821 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1822 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1824 new_stmt
= gimple_build_assign (lhs
, rhs
);
1825 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1826 update_stmt (new_stmt
);
1831 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1833 fprintf (dump_file
, "new extended phi replacement stmt\n");
1834 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1838 /* Replaces in LOOP all the scalar phi nodes other than those in the
1839 LOOP->header block with conditional modify expressions. */
1842 predicate_all_scalar_phis (struct loop
*loop
)
1845 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1848 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1851 gimple_stmt_iterator gsi
;
1852 gphi_iterator phi_gsi
;
1855 if (bb
== loop
->header
)
1858 if (EDGE_COUNT (bb
->preds
) == 1)
1861 phi_gsi
= gsi_start_phis (bb
);
1862 if (gsi_end_p (phi_gsi
))
1865 gsi
= gsi_after_labels (bb
);
1866 while (!gsi_end_p (phi_gsi
))
1868 phi
= phi_gsi
.phi ();
1869 predicate_scalar_phi (phi
, &gsi
);
1870 release_phi_node (phi
);
1871 gsi_next (&phi_gsi
);
1874 set_phi_nodes (bb
, NULL
);
1878 /* Insert in each basic block of LOOP the statements produced by the
1879 gimplification of the predicates. */
1882 insert_gimplified_predicates (loop_p loop
, bool any_mask_load_store
)
1886 for (i
= 0; i
< loop
->num_nodes
; i
++)
1888 basic_block bb
= ifc_bbs
[i
];
1890 if (!is_predicated (bb
))
1891 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1892 if (!is_predicated (bb
))
1894 /* Do not insert statements for a basic block that is not
1895 predicated. Also make sure that the predicate of the
1896 basic block is set to true. */
1897 reset_bb_predicate (bb
);
1901 stmts
= bb_predicate_gimplified_stmts (bb
);
1904 if (any_mask_load_store
)
1906 /* Insert the predicate of the BB just after the label,
1907 as the if-conversion of memory writes will use this
1909 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1910 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1914 /* Insert the predicate of the BB at the end of the BB
1915 as this would reduce the register pressure: the only
1916 use of this predicate will be in successor BBs. */
1917 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1920 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1921 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1923 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1926 /* Once the sequence is code generated, set it to NULL. */
1927 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1932 /* Helper function for predicate_mem_writes. Returns index of existent
1933 mask if it was created for given SIZE and -1 otherwise. */
1936 mask_exists (int size
, vec
<int> vec
)
1940 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1946 /* Predicate each write to memory in LOOP.
1948 This function transforms control flow constructs containing memory
1951 | for (i = 0; i < N; i++)
1955 into the following form that does not contain control flow:
1957 | for (i = 0; i < N; i++)
1958 | A[i] = cond ? expr : A[i];
1960 The original CFG looks like this:
1967 | if (i < N) goto bb_5 else goto bb_2
1971 | cond = some_computation;
1972 | if (cond) goto bb_3 else goto bb_4
1984 insert_gimplified_predicates inserts the computation of the COND
1985 expression at the beginning of the destination basic block:
1992 | if (i < N) goto bb_5 else goto bb_2
1996 | cond = some_computation;
1997 | if (cond) goto bb_3 else goto bb_4
2001 | cond = some_computation;
2010 predicate_mem_writes is then predicating the memory write as follows:
2017 | if (i < N) goto bb_5 else goto bb_2
2021 | if (cond) goto bb_3 else goto bb_4
2025 | cond = some_computation;
2026 | A[i] = cond ? expr : A[i];
2034 and finally combine_blocks removes the basic block boundaries making
2035 the loop vectorizable:
2039 | if (i < N) goto bb_5 else goto bb_1
2043 | cond = some_computation;
2044 | A[i] = cond ? expr : A[i];
2045 | if (i < N) goto bb_5 else goto bb_4
2054 predicate_mem_writes (loop_p loop
)
2056 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2057 auto_vec
<int, 1> vect_sizes
;
2058 auto_vec
<tree
, 1> vect_masks
;
2060 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2062 gimple_stmt_iterator gsi
;
2063 basic_block bb
= ifc_bbs
[i
];
2064 tree cond
= bb_predicate (bb
);
2069 if (is_true_predicate (cond
) || is_false_predicate (cond
))
2073 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2076 cond
= TREE_OPERAND (cond
, 0);
2079 vect_sizes
.truncate (0);
2080 vect_masks
.truncate (0);
2082 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2083 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2085 else if (gimple_plf (stmt
, GF_PLF_2
))
2087 tree lhs
= gimple_assign_lhs (stmt
);
2088 tree rhs
= gimple_assign_rhs1 (stmt
);
2089 tree ref
, addr
, ptr
, mask
;
2091 gimple_seq stmts
= NULL
;
2092 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2093 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2094 mark_addressable (ref
);
2095 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2096 true, NULL_TREE
, true,
2098 if (!vect_sizes
.is_empty ()
2099 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2100 /* Use created mask. */
2101 mask
= vect_masks
[index
];
2104 if (COMPARISON_CLASS_P (cond
))
2105 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2107 TREE_OPERAND (cond
, 0),
2108 TREE_OPERAND (cond
, 1));
2111 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2118 = constant_boolean_node (true, TREE_TYPE (mask
));
2119 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2120 TREE_TYPE (mask
), mask
, true_val
);
2122 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2124 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2125 /* Save mask and its size for further use. */
2126 vect_sizes
.safe_push (bitsize
);
2127 vect_masks
.safe_push (mask
);
2129 ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2130 get_object_alignment (ref
));
2131 /* Copy points-to info if possible. */
2132 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2133 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2135 if (TREE_CODE (lhs
) == SSA_NAME
)
2138 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2140 gimple_call_set_lhs (new_stmt
, lhs
);
2144 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2146 gsi_replace (&gsi
, new_stmt
, true);
2148 else if (gimple_vdef (stmt
))
2150 tree lhs
= gimple_assign_lhs (stmt
);
2151 tree rhs
= gimple_assign_rhs1 (stmt
);
2152 tree type
= TREE_TYPE (lhs
);
2154 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2155 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2157 std::swap (lhs
, rhs
);
2158 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2159 is_gimple_condexpr
, NULL_TREE
,
2160 true, GSI_SAME_STMT
);
2161 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2162 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2168 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2169 other than the exit and latch of the LOOP. Also resets the
2170 GIMPLE_DEBUG information. */
2173 remove_conditions_and_labels (loop_p loop
)
2175 gimple_stmt_iterator gsi
;
2178 for (i
= 0; i
< loop
->num_nodes
; i
++)
2180 basic_block bb
= ifc_bbs
[i
];
2182 if (bb_with_exit_edge_p (loop
, bb
)
2183 || bb
== loop
->latch
)
2186 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2187 switch (gimple_code (gsi_stmt (gsi
)))
2191 gsi_remove (&gsi
, true);
2195 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2196 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2198 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2199 update_stmt (gsi_stmt (gsi
));
2210 /* Combine all the basic blocks from LOOP into one or two super basic
2211 blocks. Replace PHI nodes with conditional modify expressions. */
2214 combine_blocks (struct loop
*loop
, bool any_mask_load_store
)
2216 basic_block bb
, exit_bb
, merge_target_bb
;
2217 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2222 predicate_bbs (loop
);
2223 remove_conditions_and_labels (loop
);
2224 insert_gimplified_predicates (loop
, any_mask_load_store
);
2225 predicate_all_scalar_phis (loop
);
2227 if (any_mask_load_store
)
2228 predicate_mem_writes (loop
);
2230 /* Merge basic blocks: first remove all the edges in the loop,
2231 except for those from the exit block. */
2233 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2234 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2237 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2238 free_bb_predicate (bb
);
2239 if (bb_with_exit_edge_p (loop
, bb
))
2241 gcc_assert (exit_bb
== NULL
);
2245 gcc_assert (exit_bb
!= loop
->latch
);
2247 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2251 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2253 if (e
->src
== exit_bb
)
2260 if (exit_bb
!= NULL
)
2262 if (exit_bb
!= loop
->header
)
2264 /* Connect this node to loop header. */
2265 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2266 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2269 /* Redirect non-exit edges to loop->latch. */
2270 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2272 if (!loop_exit_edge_p (loop
, e
))
2273 redirect_edge_and_branch (e
, loop
->latch
);
2275 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2279 /* If the loop does not have an exit, reconnect header and latch. */
2280 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2281 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2284 merge_target_bb
= loop
->header
;
2285 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2287 gimple_stmt_iterator gsi
;
2288 gimple_stmt_iterator last
;
2292 if (bb
== exit_bb
|| bb
== loop
->latch
)
2295 /* Make stmts member of loop->header and clear range info from all stmts
2296 in BB which is now no longer executed conditional on a predicate we
2297 could have derived it from. */
2298 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2300 gimple
*stmt
= gsi_stmt (gsi
);
2301 gimple_set_bb (stmt
, merge_target_bb
);
2306 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2307 reset_flow_sensitive_info (op
);
2311 /* Update stmt list. */
2312 last
= gsi_last_bb (merge_target_bb
);
2313 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2314 set_bb_seq (bb
, NULL
);
2316 delete_basic_block (bb
);
2319 /* If possible, merge loop header to the block with the exit edge.
2320 This reduces the number of basic blocks to two, to please the
2321 vectorizer that handles only loops with two nodes. */
2323 && exit_bb
!= loop
->header
2324 && can_merge_blocks_p (loop
->header
, exit_bb
))
2325 merge_blocks (loop
->header
, exit_bb
);
2332 /* Version LOOP before if-converting it; the original loop
2333 will be if-converted, the new copy of the loop will not,
2334 and the LOOP_VECTORIZED internal call will be guarding which
2335 loop to execute. The vectorizer pass will fold this
2336 internal call into either true or false. */
2339 version_loop_for_if_conversion (struct loop
*loop
)
2341 basic_block cond_bb
;
2342 tree cond
= make_ssa_name (boolean_type_node
);
2343 struct loop
*new_loop
;
2345 gimple_stmt_iterator gsi
;
2347 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2348 build_int_cst (integer_type_node
, loop
->num
),
2350 gimple_call_set_lhs (g
, cond
);
2352 initialize_original_copy_tables ();
2353 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2354 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2355 REG_BR_PROB_BASE
, true);
2356 free_original_copy_tables ();
2357 if (new_loop
== NULL
)
2359 new_loop
->dont_vectorize
= true;
2360 new_loop
->force_vectorize
= false;
2361 gsi
= gsi_last_bb (cond_bb
);
2362 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2363 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2364 update_ssa (TODO_update_ssa
);
2368 /* Performs splitting of critical edges if aggressive_if_conv is true.
2369 Returns false if loop won't be if converted and true otherwise. */
2372 ifcvt_split_critical_edges (struct loop
*loop
)
2376 unsigned int num
= loop
->num_nodes
;
2386 if (!single_exit (loop
))
2389 body
= get_loop_body (loop
);
2390 for (i
= 0; i
< num
; i
++)
2393 if (bb
== loop
->latch
2394 || bb_with_exit_edge_p (loop
, bb
))
2396 stmt
= last_stmt (bb
);
2397 /* Skip basic blocks not ending with conditional branch. */
2398 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2400 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2401 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2408 /* Assumes that lhs of DEF_STMT have multiple uses.
2409 Delete one use by (1) creation of copy DEF_STMT with
2410 unique lhs; (2) change original use of lhs in one
2411 use statement with newly created lhs. */
2414 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2419 gimple_stmt_iterator gsi
;
2420 use_operand_p use_p
;
2421 imm_use_iterator imm_iter
;
2423 var
= gimple_assign_lhs (def_stmt
);
2424 copy_stmt
= gimple_copy (def_stmt
);
2425 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2426 gimple_assign_set_lhs (copy_stmt
, lhs
);
2427 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2428 /* Insert copy of DEF_STMT. */
2429 gsi
= gsi_for_stmt (def_stmt
);
2430 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2431 /* Change use of var to lhs in use_stmt. */
2432 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2434 fprintf (dump_file
, "Change use of var ");
2435 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2436 fprintf (dump_file
, " to ");
2437 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2438 fprintf (dump_file
, "\n");
2440 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2442 if (USE_STMT (use_p
) != use_stmt
)
2444 SET_USE (use_p
, lhs
);
2449 /* Traverse bool pattern recursively starting from VAR.
2450 Save its def and use statements to defuse_list if VAR does
2451 not have single use. */
2454 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2458 enum tree_code code
;
2461 def_stmt
= SSA_NAME_DEF_STMT (var
);
2462 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2464 if (!has_single_use (var
))
2466 /* Put def and use stmts into defuse_list. */
2467 defuse_list
->safe_push (def_stmt
);
2468 defuse_list
->safe_push (use_stmt
);
2469 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2471 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2472 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2475 rhs1
= gimple_assign_rhs1 (def_stmt
);
2476 code
= gimple_assign_rhs_code (def_stmt
);
2480 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2483 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2484 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2485 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2487 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2490 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2495 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2496 rhs2
= gimple_assign_rhs2 (def_stmt
);
2497 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2505 /* Returns true if STMT can be a root of bool pattern applied
2509 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2511 enum tree_code code
;
2514 code
= gimple_assign_rhs_code (stmt
);
2515 if (CONVERT_EXPR_CODE_P (code
))
2517 lhs
= gimple_assign_lhs (stmt
);
2518 rhs
= gimple_assign_rhs1 (stmt
);
2519 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2521 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2525 else if (code
== COND_EXPR
)
2527 rhs
= gimple_assign_rhs1 (stmt
);
2528 if (TREE_CODE (rhs
) != SSA_NAME
)
2535 /* Traverse all statements in BB which correspond to loop header to
2536 find out all statements which can start bool pattern applied by
2537 vectorizer and convert multiple uses in it to conform pattern
2538 restrictions. Such case can occur if the same predicate is used both
2539 for phi node conversion and load/store mask. */
2542 ifcvt_repair_bool_pattern (basic_block bb
)
2546 gimple_stmt_iterator gsi
;
2547 vec
<gimple
*> defuse_list
= vNULL
;
2548 vec
<gimple
*> pattern_roots
= vNULL
;
2553 /* Collect all root pattern statements. */
2554 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2556 stmt
= gsi_stmt (gsi
);
2557 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2559 if (!stmt_is_root_of_bool_pattern (stmt
))
2561 pattern_roots
.safe_push (stmt
);
2564 if (pattern_roots
.is_empty ())
2567 /* Split all statements with multiple uses iteratively since splitting
2568 may create new multiple uses. */
2573 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2575 rhs
= gimple_assign_rhs1 (stmt
);
2576 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2577 while (defuse_list
.length () > 0)
2580 gimple
*def_stmt
, *use_stmt
;
2581 use_stmt
= defuse_list
.pop ();
2582 def_stmt
= defuse_list
.pop ();
2583 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2588 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2589 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2593 /* Delete redundant statements produced by predication which prevents
2594 loop vectorization. */
2597 ifcvt_local_dce (basic_block bb
)
2602 gimple_stmt_iterator gsi
;
2603 auto_vec
<gimple
*> worklist
;
2604 enum gimple_code code
;
2605 use_operand_p use_p
;
2606 imm_use_iterator imm_iter
;
2608 worklist
.create (64);
2609 /* Consider all phi as live statements. */
2610 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2612 phi
= gsi_stmt (gsi
);
2613 gimple_set_plf (phi
, GF_PLF_2
, true);
2614 worklist
.safe_push (phi
);
2616 /* Consider load/store statements, CALL and COND as live. */
2617 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2619 stmt
= gsi_stmt (gsi
);
2620 if (gimple_store_p (stmt
)
2621 || gimple_assign_load_p (stmt
)
2622 || is_gimple_debug (stmt
))
2624 gimple_set_plf (stmt
, GF_PLF_2
, true);
2625 worklist
.safe_push (stmt
);
2628 code
= gimple_code (stmt
);
2629 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2631 gimple_set_plf (stmt
, GF_PLF_2
, true);
2632 worklist
.safe_push (stmt
);
2635 gimple_set_plf (stmt
, GF_PLF_2
, false);
2637 if (code
== GIMPLE_ASSIGN
)
2639 tree lhs
= gimple_assign_lhs (stmt
);
2640 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2642 stmt1
= USE_STMT (use_p
);
2643 if (gimple_bb (stmt1
) != bb
)
2645 gimple_set_plf (stmt
, GF_PLF_2
, true);
2646 worklist
.safe_push (stmt
);
2652 /* Propagate liveness through arguments of live stmt. */
2653 while (worklist
.length () > 0)
2656 use_operand_p use_p
;
2659 stmt
= worklist
.pop ();
2660 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2662 use
= USE_FROM_PTR (use_p
);
2663 if (TREE_CODE (use
) != SSA_NAME
)
2665 stmt1
= SSA_NAME_DEF_STMT (use
);
2666 if (gimple_bb (stmt1
) != bb
2667 || gimple_plf (stmt1
, GF_PLF_2
))
2669 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2670 worklist
.safe_push (stmt1
);
2673 /* Delete dead statements. */
2674 gsi
= gsi_start_bb (bb
);
2675 while (!gsi_end_p (gsi
))
2677 stmt
= gsi_stmt (gsi
);
2678 if (gimple_plf (stmt
, GF_PLF_2
))
2683 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2685 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2686 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2688 gsi_remove (&gsi
, true);
2689 release_defs (stmt
);
2693 /* If-convert LOOP when it is legal. For the moment this pass has no
2694 profitability analysis. Returns non-zero todo flags when something
2698 tree_if_conversion (struct loop
*loop
)
2700 unsigned int todo
= 0;
2702 bool any_mask_load_store
= false;
2704 /* Set up aggressive if-conversion for loops marked with simd pragma. */
2705 aggressive_if_conv
= loop
->force_vectorize
;
2706 /* Check either outer loop was marked with simd pragma. */
2707 if (!aggressive_if_conv
)
2709 struct loop
*outer_loop
= loop_outer (loop
);
2710 if (outer_loop
&& outer_loop
->force_vectorize
)
2711 aggressive_if_conv
= true;
2714 if (aggressive_if_conv
)
2715 if (!ifcvt_split_critical_edges (loop
))
2718 if (!if_convertible_loop_p (loop
, &any_mask_load_store
)
2719 || !dbg_cnt (if_conversion_tree
))
2722 if (any_mask_load_store
2723 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2724 || loop
->dont_vectorize
))
2727 if (any_mask_load_store
&& !version_loop_for_if_conversion (loop
))
2730 /* Now all statements are if-convertible. Combine all the basic
2731 blocks into one huge basic block doing the if-conversion
2733 combine_blocks (loop
, any_mask_load_store
);
2735 /* Delete dead predicate computations and repair tree correspondent
2736 to bool pattern to delete multiple uses of predicates. */
2737 if (aggressive_if_conv
)
2739 ifcvt_local_dce (loop
->header
);
2740 ifcvt_repair_bool_pattern (loop
->header
);
2743 todo
|= TODO_cleanup_cfg
;
2744 if (any_mask_load_store
)
2746 mark_virtual_operands_for_renaming (cfun
);
2747 todo
|= TODO_update_ssa_only_virtuals
;
2755 for (i
= 0; i
< loop
->num_nodes
; i
++)
2756 free_bb_predicate (ifc_bbs
[i
]);
2761 free_dominance_info (CDI_POST_DOMINATORS
);
2766 /* Tree if-conversion pass management. */
2770 const pass_data pass_data_if_conversion
=
2772 GIMPLE_PASS
, /* type */
2774 OPTGROUP_NONE
, /* optinfo_flags */
2775 TV_NONE
, /* tv_id */
2776 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2777 0, /* properties_provided */
2778 0, /* properties_destroyed */
2779 0, /* todo_flags_start */
2780 0, /* todo_flags_finish */
2783 class pass_if_conversion
: public gimple_opt_pass
2786 pass_if_conversion (gcc::context
*ctxt
)
2787 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2790 /* opt_pass methods: */
2791 virtual bool gate (function
*);
2792 virtual unsigned int execute (function
*);
2794 }; // class pass_if_conversion
2797 pass_if_conversion::gate (function
*fun
)
2799 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2800 && flag_tree_loop_if_convert
!= 0)
2801 || flag_tree_loop_if_convert
== 1
2802 || flag_tree_loop_if_convert_stores
== 1);
2806 pass_if_conversion::execute (function
*fun
)
2811 if (number_of_loops (fun
) <= 1)
2814 FOR_EACH_LOOP (loop
, 0)
2815 if (flag_tree_loop_if_convert
== 1
2816 || flag_tree_loop_if_convert_stores
== 1
2817 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2818 && !loop
->dont_vectorize
))
2819 todo
|= tree_if_conversion (loop
);
2824 FOR_EACH_BB_FN (bb
, fun
)
2825 gcc_assert (!bb
->aux
);
2834 make_pass_if_conversion (gcc::context
*ctxt
)
2836 return new pass_if_conversion (ctxt
);