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 /* Indicate if new load/store that needs to be predicated is introduced
118 during if conversion. */
119 static bool any_pred_load_store
;
121 /* Hash for struct innermost_loop_behavior. It depends on the user to
124 struct innermost_loop_behavior_hash
: nofree_ptr_hash
<innermost_loop_behavior
>
126 static inline hashval_t
hash (const value_type
&);
127 static inline bool equal (const value_type
&,
128 const compare_type
&);
132 innermost_loop_behavior_hash::hash (const value_type
&e
)
136 hash
= iterative_hash_expr (e
->base_address
, 0);
137 hash
= iterative_hash_expr (e
->offset
, hash
);
138 hash
= iterative_hash_expr (e
->init
, hash
);
139 return iterative_hash_expr (e
->step
, hash
);
143 innermost_loop_behavior_hash::equal (const value_type
&e1
,
144 const compare_type
&e2
)
146 if ((e1
->base_address
&& !e2
->base_address
)
147 || (!e1
->base_address
&& e2
->base_address
)
148 || (!e1
->offset
&& e2
->offset
)
149 || (e1
->offset
&& !e2
->offset
)
150 || (!e1
->init
&& e2
->init
)
151 || (e1
->init
&& !e2
->init
)
152 || (!e1
->step
&& e2
->step
)
153 || (e1
->step
&& !e2
->step
))
156 if (e1
->base_address
&& e2
->base_address
157 && !operand_equal_p (e1
->base_address
, e2
->base_address
, 0))
159 if (e1
->offset
&& e2
->offset
160 && !operand_equal_p (e1
->offset
, e2
->offset
, 0))
162 if (e1
->init
&& e2
->init
163 && !operand_equal_p (e1
->init
, e2
->init
, 0))
165 if (e1
->step
&& e2
->step
166 && !operand_equal_p (e1
->step
, e2
->step
, 0))
172 /* List of basic blocks in if-conversion-suitable order. */
173 static basic_block
*ifc_bbs
;
175 /* Apply more aggressive (extended) if-conversion if true. */
176 static bool aggressive_if_conv
;
178 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
179 static hash_map
<innermost_loop_behavior_hash
,
180 data_reference_p
> *innermost_DR_map
;
182 /* Hash table to store <base reference, DR> pairs. */
183 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
185 /* Structure used to predicate basic blocks. This is attached to the
186 ->aux field of the BBs in the loop to be if-converted. */
187 struct bb_predicate
{
189 /* The condition under which this basic block is executed. */
192 /* PREDICATE is gimplified, and the sequence of statements is
193 recorded here, in order to avoid the duplication of computations
194 that occur in previous conditions. See PR44483. */
195 gimple_seq predicate_gimplified_stmts
;
198 /* Returns true when the basic block BB has a predicate. */
201 bb_has_predicate (basic_block bb
)
203 return bb
->aux
!= NULL
;
206 /* Returns the gimplified predicate for basic block BB. */
209 bb_predicate (basic_block bb
)
211 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
214 /* Sets the gimplified predicate COND for basic block BB. */
217 set_bb_predicate (basic_block bb
, tree cond
)
219 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
220 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
221 || is_gimple_condexpr (cond
));
222 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
225 /* Returns the sequence of statements of the gimplification of the
226 predicate for basic block BB. */
228 static inline gimple_seq
229 bb_predicate_gimplified_stmts (basic_block bb
)
231 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
234 /* Sets the sequence of statements STMTS of the gimplification of the
235 predicate for basic block BB. */
238 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
240 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
243 /* Adds the sequence of statements STMTS to the sequence of statements
244 of the predicate for basic block BB. */
247 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
250 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
253 /* Initializes to TRUE the predicate of basic block BB. */
256 init_bb_predicate (basic_block bb
)
258 bb
->aux
= XNEW (struct bb_predicate
);
259 set_bb_predicate_gimplified_stmts (bb
, NULL
);
260 set_bb_predicate (bb
, boolean_true_node
);
263 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
264 but don't actually free it. */
267 release_bb_predicate (basic_block bb
)
269 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
272 gimple_stmt_iterator i
;
274 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
275 free_stmt_operands (cfun
, gsi_stmt (i
));
276 set_bb_predicate_gimplified_stmts (bb
, NULL
);
280 /* Free the predicate of basic block BB. */
283 free_bb_predicate (basic_block bb
)
285 if (!bb_has_predicate (bb
))
288 release_bb_predicate (bb
);
293 /* Reinitialize predicate of BB with the true predicate. */
296 reset_bb_predicate (basic_block bb
)
298 if (!bb_has_predicate (bb
))
299 init_bb_predicate (bb
);
302 release_bb_predicate (bb
);
303 set_bb_predicate (bb
, boolean_true_node
);
307 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
308 the expression EXPR. Inserts the statement created for this
309 computation before GSI and leaves the iterator GSI at the same
313 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
315 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
316 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
317 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
321 /* Return true when COND is a false predicate. */
324 is_false_predicate (tree cond
)
326 return (cond
!= NULL_TREE
327 && (cond
== boolean_false_node
328 || integer_zerop (cond
)));
331 /* Return true when COND is a true predicate. */
334 is_true_predicate (tree cond
)
336 return (cond
== NULL_TREE
337 || cond
== boolean_true_node
338 || integer_onep (cond
));
341 /* Returns true when BB has a predicate that is not trivial: true or
345 is_predicated (basic_block bb
)
347 return !is_true_predicate (bb_predicate (bb
));
350 /* Parses the predicate COND and returns its comparison code and
351 operands OP0 and OP1. */
353 static enum tree_code
354 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
358 if (TREE_CODE (cond
) == SSA_NAME
359 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
361 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
363 *op0
= gimple_assign_rhs1 (s
);
364 *op1
= gimple_assign_rhs2 (s
);
365 return gimple_assign_rhs_code (s
);
368 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
370 tree op
= gimple_assign_rhs1 (s
);
371 tree type
= TREE_TYPE (op
);
372 enum tree_code code
= parse_predicate (op
, op0
, op1
);
374 return code
== ERROR_MARK
? ERROR_MARK
375 : invert_tree_comparison (code
, HONOR_NANS (type
));
381 if (COMPARISON_CLASS_P (cond
))
383 *op0
= TREE_OPERAND (cond
, 0);
384 *op1
= TREE_OPERAND (cond
, 1);
385 return TREE_CODE (cond
);
391 /* Returns the fold of predicate C1 OR C2 at location LOC. */
394 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
396 tree op1a
, op1b
, op2a
, op2b
;
397 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
398 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
400 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
402 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
408 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
411 /* Returns true if N is either a constant or a SSA_NAME. */
414 constant_or_ssa_name (tree n
)
416 switch (TREE_CODE (n
))
429 /* Returns either a COND_EXPR or the folded expression if the folded
430 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
431 a constant or a SSA_NAME. */
434 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
436 tree rhs1
, lhs1
, cond_expr
;
438 /* If COND is comparison r != 0 and r has boolean type, convert COND
439 to SSA_NAME to accept by vect bool pattern. */
440 if (TREE_CODE (cond
) == NE_EXPR
)
442 tree op0
= TREE_OPERAND (cond
, 0);
443 tree op1
= TREE_OPERAND (cond
, 1);
444 if (TREE_CODE (op0
) == SSA_NAME
445 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
446 && (integer_zerop (op1
)))
449 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
,
452 if (cond_expr
== NULL_TREE
)
453 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
455 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
457 if (constant_or_ssa_name (cond_expr
))
460 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
462 rhs1
= TREE_OPERAND (cond_expr
, 1);
463 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
464 if (constant_or_ssa_name (rhs1
))
465 return build1 (ABS_EXPR
, type
, rhs1
);
468 if (TREE_CODE (cond_expr
) == MIN_EXPR
469 || TREE_CODE (cond_expr
) == MAX_EXPR
)
471 lhs1
= TREE_OPERAND (cond_expr
, 0);
472 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
473 rhs1
= TREE_OPERAND (cond_expr
, 1);
474 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
475 if (constant_or_ssa_name (rhs1
)
476 && constant_or_ssa_name (lhs1
))
477 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
479 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
482 /* Add condition NC to the predicate list of basic block BB. LOOP is
483 the loop to be if-converted. Use predicate of cd-equivalent block
484 for join bb if it exists: we call basic blocks bb1 and bb2
485 cd-equivalent if they are executed under the same condition. */
488 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
493 if (is_true_predicate (nc
))
496 /* If dominance tells us this basic block is always executed,
497 don't record any predicates for it. */
498 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
501 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
502 /* We use notion of cd equivalence to get simpler predicate for
503 join block, e.g. if join block has 2 predecessors with predicates
504 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
505 p1 & p2 | p1 & !p2. */
506 if (dom_bb
!= loop
->header
507 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
509 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
510 bc
= bb_predicate (dom_bb
);
511 if (!is_true_predicate (bc
))
512 set_bb_predicate (bb
, bc
);
514 gcc_assert (is_true_predicate (bb_predicate (bb
)));
515 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
516 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
517 dom_bb
->index
, bb
->index
);
521 if (!is_predicated (bb
))
525 bc
= bb_predicate (bb
);
526 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
527 if (is_true_predicate (bc
))
529 reset_bb_predicate (bb
);
534 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
535 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
536 tp
= &TREE_OPERAND (bc
, 0);
539 if (!is_gimple_condexpr (*tp
))
542 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
543 add_bb_predicate_gimplified_stmts (bb
, stmts
);
545 set_bb_predicate (bb
, bc
);
548 /* Add the condition COND to the previous condition PREV_COND, and add
549 this to the predicate list of the destination of edge E. LOOP is
550 the loop to be if-converted. */
553 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
554 tree prev_cond
, tree cond
)
556 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
559 if (!is_true_predicate (prev_cond
))
560 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
563 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
564 add_to_predicate_list (loop
, e
->dest
, cond
);
567 /* Return true if one of the successor edges of BB exits LOOP. */
570 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
575 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
576 if (loop_exit_edge_p (loop
, e
))
582 /* Given PHI which has more than two arguments, this function checks if
583 it's if-convertible by degenerating its arguments. Specifically, if
584 below two conditions are satisfied:
586 1) Number of PHI arguments with different values equals to 2 and one
587 argument has the only occurrence.
588 2) The edge corresponding to the unique argument isn't critical edge.
590 Such PHI can be handled as PHIs have only two arguments. For example,
593 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
595 can be transformed into:
597 res = (predicate of e3) ? A_2 : A_1;
599 Return TRUE if it is the case, FALSE otherwise. */
602 phi_convertible_by_degenerating_args (gphi
*phi
)
605 tree arg
, t1
= NULL
, t2
= NULL
;
606 unsigned int i
, i1
= 0, i2
= 0, n1
= 0, n2
= 0;
607 unsigned int num_args
= gimple_phi_num_args (phi
);
609 gcc_assert (num_args
> 2);
611 for (i
= 0; i
< num_args
; i
++)
613 arg
= gimple_phi_arg_def (phi
, i
);
614 if (t1
== NULL
|| operand_equal_p (t1
, arg
, 0))
620 else if (t2
== NULL
|| operand_equal_p (t2
, arg
, 0))
630 if (n1
!= 1 && n2
!= 1)
633 /* Check if the edge corresponding to the unique arg is critical. */
634 e
= gimple_phi_arg_edge (phi
, (n1
== 1) ? i1
: i2
);
635 if (EDGE_COUNT (e
->src
->succs
) > 1)
641 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
642 and it belongs to basic block BB.
644 PHI is not if-convertible if:
645 - it has more than 2 arguments.
647 When the aggressive_if_conv is set, PHI can have more than
651 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
)
653 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
655 fprintf (dump_file
, "-------------------------\n");
656 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
659 if (bb
!= loop
->header
)
661 if (gimple_phi_num_args (phi
) > 2
662 && !aggressive_if_conv
663 && !phi_convertible_by_degenerating_args (phi
))
665 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
666 fprintf (dump_file
, "Phi can't be predicated by single cond.\n");
674 /* Records the status of a data reference. This struct is attached to
675 each DR->aux field. */
678 bool rw_unconditionally
;
679 bool w_unconditionally
;
680 bool written_at_least_once
;
684 tree base_w_predicate
;
687 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
688 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
689 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
690 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
692 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
693 HASH tables. While storing them in HASH table, it checks if the
694 reference is unconditionally read or written and stores that as a flag
695 information. For base reference it checks if it is written atlest once
696 unconditionally and stores it as flag information along with DR.
697 In other words for every data reference A in STMT there exist other
698 accesses to a data reference with the same base with predicates that
699 add up (OR-up) to the true predicate: this ensures that the data
700 reference A is touched (read or written) on every iteration of the
701 if-converted loop. */
703 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
706 data_reference_p
*master_dr
, *base_master_dr
;
707 tree base_ref
= DR_BASE_OBJECT (a
);
708 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
709 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
712 master_dr
= &innermost_DR_map
->get_or_insert (innermost
, &exist1
);
718 IFC_DR (*master_dr
)->w_predicate
719 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
720 IFC_DR (*master_dr
)->w_predicate
);
721 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
722 DR_W_UNCONDITIONALLY (*master_dr
) = true;
724 IFC_DR (*master_dr
)->rw_predicate
725 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
726 IFC_DR (*master_dr
)->rw_predicate
);
727 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
728 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
732 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
735 IFC_DR (*base_master_dr
)->base_w_predicate
736 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
737 IFC_DR (*base_master_dr
)->base_w_predicate
);
738 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
739 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
743 /* Return true when the memory references of STMT won't trap in the
744 if-converted code. There are two things that we have to check for:
746 - writes to memory occur to writable memory: if-conversion of
747 memory writes transforms the conditional memory writes into
748 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
749 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
750 be executed at all in the original code, it may be a readonly
751 memory. To check that A is not const-qualified, we check that
752 there exists at least an unconditional write to A in the current
755 - reads or writes to memory are valid memory accesses for every
756 iteration. To check that the memory accesses are correctly formed
757 and that we are allowed to read and write in these locations, we
758 check that the memory accesses to be if-converted occur at every
759 iteration unconditionally.
761 Returns true for the memory reference in STMT, same memory reference
762 is read or written unconditionally atleast once and the base memory
763 reference is written unconditionally once. This is to check reference
764 will not write fault. Also retuns true if the memory reference is
765 unconditionally read once then we are conditionally writing to memory
766 which is defined as read and write and is bound to the definition
769 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
771 data_reference_p
*master_dr
, *base_master_dr
;
772 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
774 tree base
= DR_BASE_OBJECT (a
);
775 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
777 gcc_assert (DR_STMT (a
) == stmt
);
778 gcc_assert (DR_BASE_ADDRESS (a
) || DR_OFFSET (a
)
779 || DR_INIT (a
) || DR_STEP (a
));
781 master_dr
= innermost_DR_map
->get (innermost
);
782 gcc_assert (master_dr
!= NULL
);
784 base_master_dr
= baseref_DR_map
->get (base
);
786 /* If a is unconditionally written to it doesn't trap. */
787 if (DR_W_UNCONDITIONALLY (*master_dr
))
790 /* If a is unconditionally accessed then ... */
791 if (DR_RW_UNCONDITIONALLY (*master_dr
))
793 /* an unconditional read won't trap. */
797 /* an unconditionaly write won't trap if the base is written
798 to unconditionally. */
800 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
801 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
804 /* or the base is know to be not readonly. */
805 tree base_tree
= get_base_address (DR_REF (a
));
806 if (DECL_P (base_tree
)
807 && decl_binds_to_current_def_p (base_tree
)
808 && ! TREE_READONLY (base_tree
))
809 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
815 /* Return true if STMT could be converted into a masked load or store
816 (conditional load or store based on a mask computed from bb predicate). */
819 ifcvt_can_use_mask_load_store (gimple
*stmt
)
823 basic_block bb
= gimple_bb (stmt
);
826 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
827 || bb
->loop_father
->dont_vectorize
828 || !gimple_assign_single_p (stmt
)
829 || gimple_has_volatile_ops (stmt
))
832 /* Check whether this is a load or store. */
833 lhs
= gimple_assign_lhs (stmt
);
834 if (gimple_store_p (stmt
))
836 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
841 else if (gimple_assign_load_p (stmt
))
844 ref
= gimple_assign_rhs1 (stmt
);
849 if (may_be_nonaddressable_p (ref
))
852 /* Mask should be integer mode of the same size as the load/store
854 mode
= TYPE_MODE (TREE_TYPE (lhs
));
855 if (int_mode_for_mode (mode
) == BLKmode
856 || VECTOR_MODE_P (mode
))
859 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
865 /* Return true when STMT is if-convertible.
867 GIMPLE_ASSIGN statement is not if-convertible if,
870 - LHS is not var decl. */
873 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
874 vec
<data_reference_p
> refs
)
876 tree lhs
= gimple_assign_lhs (stmt
);
878 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
880 fprintf (dump_file
, "-------------------------\n");
881 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
884 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
887 /* Some of these constrains might be too conservative. */
888 if (stmt_ends_bb_p (stmt
)
889 || gimple_has_volatile_ops (stmt
)
890 || (TREE_CODE (lhs
) == SSA_NAME
891 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
892 || gimple_has_side_effects (stmt
))
894 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
895 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
899 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
900 in between if_convertible_loop_p and combine_blocks
901 we can perform loop versioning. */
902 gimple_set_plf (stmt
, GF_PLF_2
, false);
904 if ((! gimple_vuse (stmt
)
905 || gimple_could_trap_p_1 (stmt
, false, false)
906 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
907 && gimple_could_trap_p (stmt
))
909 if (ifcvt_can_use_mask_load_store (stmt
))
911 gimple_set_plf (stmt
, GF_PLF_2
, true);
912 any_pred_load_store
= true;
915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
916 fprintf (dump_file
, "tree could trap...\n");
920 /* When if-converting stores force versioning, likewise if we
921 ended up generating store data races. */
922 if (gimple_vdef (stmt
))
923 any_pred_load_store
= true;
928 /* Return true when STMT is if-convertible.
930 A statement is if-convertible if:
931 - it is an if-convertible GIMPLE_ASSIGN,
932 - it is a GIMPLE_LABEL or a GIMPLE_COND,
933 - it is builtins call. */
936 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
)
938 switch (gimple_code (stmt
))
946 return if_convertible_gimple_assign_stmt_p (stmt
, refs
);
950 tree fndecl
= gimple_call_fndecl (stmt
);
953 int flags
= gimple_call_flags (stmt
);
954 if ((flags
& ECF_CONST
)
955 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
956 /* We can only vectorize some builtins at the moment,
957 so restrict if-conversion to those. */
958 && DECL_BUILT_IN (fndecl
))
965 /* Don't know what to do with 'em so don't do anything. */
966 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
968 fprintf (dump_file
, "don't know what to do\n");
969 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
978 /* Assumes that BB has more than 1 predecessors.
979 Returns false if at least one successor is not on critical edge
980 and true otherwise. */
983 all_preds_critical_p (basic_block bb
)
988 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
989 if (EDGE_COUNT (e
->src
->succs
) == 1)
994 /* Returns true if at least one successor in on critical edge. */
996 has_pred_critical_p (basic_block bb
)
1001 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1002 if (EDGE_COUNT (e
->src
->succs
) > 1)
1007 /* Return true when BB is if-convertible. This routine does not check
1008 basic block's statements and phis.
1010 A basic block is not if-convertible if:
1011 - it is non-empty and it is after the exit block (in BFS order),
1012 - it is after the exit block but before the latch,
1013 - its edges are not normal.
1015 Last restriction is valid if aggressive_if_conv is false.
1017 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1021 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
1026 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1027 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1029 if (EDGE_COUNT (bb
->succs
) > 2)
1034 if (bb
!= loop
->latch
)
1036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1037 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1040 else if (!empty_block_p (bb
))
1042 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1043 fprintf (dump_file
, "non empty basic block after exit bb\n");
1046 else if (bb
== loop
->latch
1048 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1050 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1051 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1056 /* Be less adventurous and handle only normal edges. */
1057 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1058 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1060 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1061 fprintf (dump_file
, "Difficult to handle edges\n");
1065 /* At least one incoming edge has to be non-critical as otherwise edge
1066 predicates are not equal to basic-block predicates of the edge
1067 source. This check is skipped if aggressive_if_conv is true. */
1068 if (!aggressive_if_conv
1069 && EDGE_COUNT (bb
->preds
) > 1
1070 && bb
!= loop
->header
1071 && all_preds_critical_p (bb
))
1073 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1074 fprintf (dump_file
, "only critical predecessors\n");
1081 /* Return true when all predecessor blocks of BB are visited. The
1082 VISITED bitmap keeps track of the visited blocks. */
1085 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1089 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1090 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1096 /* Get body of a LOOP in suitable order for if-conversion. It is
1097 caller's responsibility to deallocate basic block list.
1098 If-conversion suitable order is, breadth first sort (BFS) order
1099 with an additional constraint: select a block only if all its
1100 predecessors are already selected. */
1102 static basic_block
*
1103 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1105 basic_block
*blocks
, *blocks_in_bfs_order
;
1108 unsigned int index
= 0;
1109 unsigned int visited_count
= 0;
1111 gcc_assert (loop
->num_nodes
);
1112 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1114 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1115 visited
= BITMAP_ALLOC (NULL
);
1117 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1120 while (index
< loop
->num_nodes
)
1122 bb
= blocks_in_bfs_order
[index
];
1124 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1126 free (blocks_in_bfs_order
);
1127 BITMAP_FREE (visited
);
1132 if (!bitmap_bit_p (visited
, bb
->index
))
1134 if (pred_blocks_visited_p (bb
, &visited
)
1135 || bb
== loop
->header
)
1137 /* This block is now visited. */
1138 bitmap_set_bit (visited
, bb
->index
);
1139 blocks
[visited_count
++] = bb
;
1145 if (index
== loop
->num_nodes
1146 && visited_count
!= loop
->num_nodes
)
1150 free (blocks_in_bfs_order
);
1151 BITMAP_FREE (visited
);
1155 /* Returns true when the analysis of the predicates for all the basic
1156 blocks in LOOP succeeded.
1158 predicate_bbs first allocates the predicates of the basic blocks.
1159 These fields are then initialized with the tree expressions
1160 representing the predicates under which a basic block is executed
1161 in the LOOP. As the loop->header is executed at each iteration, it
1162 has the "true" predicate. Other statements executed under a
1163 condition are predicated with that condition, for example
1170 S1 will be predicated with "x", and
1171 S2 will be predicated with "!x". */
1174 predicate_bbs (loop_p loop
)
1178 for (i
= 0; i
< loop
->num_nodes
; i
++)
1179 init_bb_predicate (ifc_bbs
[i
]);
1181 for (i
= 0; i
< loop
->num_nodes
; i
++)
1183 basic_block bb
= ifc_bbs
[i
];
1187 /* The loop latch and loop exit block are always executed and
1188 have no extra conditions to be processed: skip them. */
1189 if (bb
== loop
->latch
1190 || bb_with_exit_edge_p (loop
, bb
))
1192 reset_bb_predicate (bb
);
1196 cond
= bb_predicate (bb
);
1197 stmt
= last_stmt (bb
);
1198 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1201 edge true_edge
, false_edge
;
1202 location_t loc
= gimple_location (stmt
);
1203 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1205 gimple_cond_lhs (stmt
),
1206 gimple_cond_rhs (stmt
));
1208 /* Add new condition into destination's predicate list. */
1209 extract_true_false_edges_from_block (gimple_bb (stmt
),
1210 &true_edge
, &false_edge
);
1212 /* If C is true, then TRUE_EDGE is taken. */
1213 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1216 /* If C is false, then FALSE_EDGE is taken. */
1217 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1219 add_to_dst_predicate_list (loop
, false_edge
,
1220 unshare_expr (cond
), c2
);
1225 /* If current bb has only one successor, then consider it as an
1226 unconditional goto. */
1227 if (single_succ_p (bb
))
1229 basic_block bb_n
= single_succ (bb
);
1231 /* The successor bb inherits the predicate of its
1232 predecessor. If there is no predicate in the predecessor
1233 bb, then consider the successor bb as always executed. */
1234 if (cond
== NULL_TREE
)
1235 cond
= boolean_true_node
;
1237 add_to_predicate_list (loop
, bb_n
, cond
);
1241 /* The loop header is always executed. */
1242 reset_bb_predicate (loop
->header
);
1243 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1244 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1247 /* Return true when LOOP is if-convertible. This is a helper function
1248 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1249 in if_convertible_loop_p. */
1252 if_convertible_loop_p_1 (struct loop
*loop
, vec
<data_reference_p
> *refs
)
1255 basic_block exit_bb
= NULL
;
1257 if (find_data_references_in_loop (loop
, refs
) == chrec_dont_know
)
1260 calculate_dominance_info (CDI_DOMINATORS
);
1261 calculate_dominance_info (CDI_POST_DOMINATORS
);
1263 /* Allow statements that can be handled during if-conversion. */
1264 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1268 fprintf (dump_file
, "Irreducible loop\n");
1272 for (i
= 0; i
< loop
->num_nodes
; i
++)
1274 basic_block bb
= ifc_bbs
[i
];
1276 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1279 if (bb_with_exit_edge_p (loop
, bb
))
1283 for (i
= 0; i
< loop
->num_nodes
; i
++)
1285 basic_block bb
= ifc_bbs
[i
];
1286 gimple_stmt_iterator gsi
;
1288 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1289 switch (gimple_code (gsi_stmt (gsi
)))
1296 gimple_set_uid (gsi_stmt (gsi
), 0);
1303 data_reference_p dr
;
1306 = new hash_map
<innermost_loop_behavior_hash
, data_reference_p
>;
1307 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1309 predicate_bbs (loop
);
1311 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1313 tree ref
= DR_REF (dr
);
1315 dr
->aux
= XNEW (struct ifc_dr
);
1316 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1317 DR_RW_UNCONDITIONALLY (dr
) = false;
1318 DR_W_UNCONDITIONALLY (dr
) = false;
1319 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1320 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1321 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1322 if (gimple_uid (DR_STMT (dr
)) == 0)
1323 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1325 /* If DR doesn't have innermost loop behavior or it's a compound
1326 memory reference, we synthesize its innermost loop behavior
1328 if (TREE_CODE (ref
) == COMPONENT_REF
1329 || TREE_CODE (ref
) == IMAGPART_EXPR
1330 || TREE_CODE (ref
) == REALPART_EXPR
1331 || !(DR_BASE_ADDRESS (dr
) || DR_OFFSET (dr
)
1332 || DR_INIT (dr
) || DR_STEP (dr
)))
1334 while (TREE_CODE (ref
) == COMPONENT_REF
1335 || TREE_CODE (ref
) == IMAGPART_EXPR
1336 || TREE_CODE (ref
) == REALPART_EXPR
)
1337 ref
= TREE_OPERAND (ref
, 0);
1339 DR_BASE_ADDRESS (dr
) = ref
;
1340 DR_OFFSET (dr
) = NULL
;
1341 DR_INIT (dr
) = NULL
;
1342 DR_STEP (dr
) = NULL
;
1343 DR_ALIGNED_TO (dr
) = NULL
;
1345 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1348 for (i
= 0; i
< loop
->num_nodes
; i
++)
1350 basic_block bb
= ifc_bbs
[i
];
1351 gimple_stmt_iterator itr
;
1353 /* Check the if-convertibility of statements in predicated BBs. */
1354 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1355 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1356 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
))
1360 for (i
= 0; i
< loop
->num_nodes
; i
++)
1361 free_bb_predicate (ifc_bbs
[i
]);
1363 /* Checking PHIs needs to be done after stmts, as the fact whether there
1364 are any masked loads or stores affects the tests. */
1365 for (i
= 0; i
< loop
->num_nodes
; i
++)
1367 basic_block bb
= ifc_bbs
[i
];
1370 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1371 if (!if_convertible_phi_p (loop
, bb
, itr
.phi ()))
1376 fprintf (dump_file
, "Applying if-conversion\n");
1381 /* Return true when LOOP is if-convertible.
1382 LOOP is if-convertible if:
1384 - it has two or more basic blocks,
1385 - it has only one exit,
1386 - loop header is not the exit edge,
1387 - if its basic blocks and phi nodes are if convertible. */
1390 if_convertible_loop_p (struct loop
*loop
)
1395 vec
<data_reference_p
> refs
;
1397 /* Handle only innermost loop. */
1398 if (!loop
|| loop
->inner
)
1400 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1401 fprintf (dump_file
, "not innermost loop\n");
1405 /* If only one block, no need for if-conversion. */
1406 if (loop
->num_nodes
<= 2)
1408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1409 fprintf (dump_file
, "less than 2 basic blocks\n");
1413 /* More than one loop exit is too much to handle. */
1414 if (!single_exit (loop
))
1416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1417 fprintf (dump_file
, "multiple exits\n");
1421 /* If one of the loop header's edge is an exit edge then do not
1422 apply if-conversion. */
1423 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1424 if (loop_exit_edge_p (loop
, e
))
1428 res
= if_convertible_loop_p_1 (loop
, &refs
);
1430 data_reference_p dr
;
1432 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1435 free_data_refs (refs
);
1437 delete innermost_DR_map
;
1438 innermost_DR_map
= NULL
;
1440 delete baseref_DR_map
;
1441 baseref_DR_map
= NULL
;
1446 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1447 which is in predicated basic block.
1448 In fact, the following PHI pattern is searching:
1450 reduc_1 = PHI <..., reduc_2>
1454 reduc_2 = PHI <reduc_1, reduc_3>
1456 ARG_0 and ARG_1 are correspondent PHI arguments.
1457 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1458 EXTENDED is true if PHI has > 2 arguments. */
1461 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1462 tree
*op0
, tree
*op1
, bool extended
)
1464 tree lhs
, r_op1
, r_op2
;
1466 gimple
*header_phi
= NULL
;
1467 enum tree_code reduction_op
;
1468 basic_block bb
= gimple_bb (phi
);
1469 struct loop
*loop
= bb
->loop_father
;
1470 edge latch_e
= loop_latch_edge (loop
);
1471 imm_use_iterator imm_iter
;
1472 use_operand_p use_p
;
1475 bool result
= false;
1476 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1479 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1482 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1483 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1485 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1488 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1489 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1493 if (gimple_bb (header_phi
) != loop
->header
)
1496 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1499 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1500 || gimple_has_volatile_ops (stmt
))
1503 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1506 if (!is_predicated (gimple_bb (stmt
)))
1509 /* Check that stmt-block is predecessor of phi-block. */
1510 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1519 if (!has_single_use (lhs
))
1522 reduction_op
= gimple_assign_rhs_code (stmt
);
1523 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1525 r_op1
= gimple_assign_rhs1 (stmt
);
1526 r_op2
= gimple_assign_rhs2 (stmt
);
1528 /* Make R_OP1 to hold reduction variable. */
1529 if (r_op2
== PHI_RESULT (header_phi
)
1530 && reduction_op
== PLUS_EXPR
)
1531 std::swap (r_op1
, r_op2
);
1532 else if (r_op1
!= PHI_RESULT (header_phi
))
1535 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1536 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1538 gimple
*use_stmt
= USE_STMT (use_p
);
1539 if (is_gimple_debug (use_stmt
))
1541 if (use_stmt
== stmt
)
1543 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1547 *op0
= r_op1
; *op1
= r_op2
;
1552 /* Converts conditional scalar reduction into unconditional form, e.g.
1554 if (_5 != 0) goto bb_5 else goto bb_6
1560 # res_2 = PHI <res_13(4), res_6(5)>
1563 will be converted into sequence
1564 _ifc__1 = _5 != 0 ? 1 : 0;
1565 res_2 = res_13 + _ifc__1;
1566 Argument SWAP tells that arguments of conditional expression should be
1568 Returns rhs of resulting PHI assignment. */
1571 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1572 tree cond
, tree op0
, tree op1
, bool swap
)
1574 gimple_stmt_iterator stmt_it
;
1577 tree rhs1
= gimple_assign_rhs1 (reduc
);
1578 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1580 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1582 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1584 fprintf (dump_file
, "Found cond scalar reduction.\n");
1585 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1588 /* Build cond expression using COND and constant operand
1589 of reduction rhs. */
1590 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1591 unshare_expr (cond
),
1595 /* Create assignment stmt and insert it at GSI. */
1596 new_assign
= gimple_build_assign (tmp
, c
);
1597 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1598 /* Build rhs for unconditional increment/decrement. */
1599 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1600 TREE_TYPE (rhs1
), op0
, tmp
);
1602 /* Delete original reduction stmt. */
1603 stmt_it
= gsi_for_stmt (reduc
);
1604 gsi_remove (&stmt_it
, true);
1605 release_defs (reduc
);
1609 /* Produce condition for all occurrences of ARG in PHI node. */
1612 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1613 gimple_stmt_iterator
*gsi
)
1617 tree cond
= NULL_TREE
;
1621 len
= occur
->length ();
1622 gcc_assert (len
> 0);
1623 for (i
= 0; i
< len
; i
++)
1625 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1626 c
= bb_predicate (e
->src
);
1627 if (is_true_predicate (c
))
1629 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1630 is_gimple_condexpr
, NULL_TREE
,
1631 true, GSI_SAME_STMT
);
1632 if (cond
!= NULL_TREE
)
1634 /* Must build OR expression. */
1635 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1636 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1637 is_gimple_condexpr
, NULL_TREE
,
1638 true, GSI_SAME_STMT
);
1643 gcc_assert (cond
!= NULL_TREE
);
1647 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1648 This routine can handle PHI nodes with more than two arguments.
1651 S1: A = PHI <x1(1), x2(5)>
1653 S2: A = cond ? x1 : x2;
1655 The generated code is inserted at GSI that points to the top of
1656 basic block's statement list.
1657 If PHI node has more than two arguments a chain of conditional
1658 expression is produced. */
1662 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1664 gimple
*new_stmt
= NULL
, *reduc
;
1665 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1667 unsigned int index0
;
1668 unsigned int max
, args_len
;
1673 res
= gimple_phi_result (phi
);
1674 if (virtual_operand_p (res
))
1677 if ((rhs
= degenerate_phi_result (phi
))
1678 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1680 && !chrec_contains_undetermined (scev
)
1682 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1684 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1686 fprintf (dump_file
, "Degenerate phi!\n");
1687 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1689 new_stmt
= gimple_build_assign (res
, rhs
);
1690 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1691 update_stmt (new_stmt
);
1695 bb
= gimple_bb (phi
);
1696 if (EDGE_COUNT (bb
->preds
) == 2)
1698 /* Predicate ordinary PHI node with 2 arguments. */
1699 edge first_edge
, second_edge
;
1700 basic_block true_bb
;
1701 first_edge
= EDGE_PRED (bb
, 0);
1702 second_edge
= EDGE_PRED (bb
, 1);
1703 cond
= bb_predicate (first_edge
->src
);
1704 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1705 std::swap (first_edge
, second_edge
);
1706 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1708 cond
= bb_predicate (second_edge
->src
);
1709 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1710 cond
= TREE_OPERAND (cond
, 0);
1712 first_edge
= second_edge
;
1715 cond
= bb_predicate (first_edge
->src
);
1716 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1717 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1718 is_gimple_condexpr
, NULL_TREE
,
1719 true, GSI_SAME_STMT
);
1720 true_bb
= first_edge
->src
;
1721 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1723 arg0
= gimple_phi_arg_def (phi
, 1);
1724 arg1
= gimple_phi_arg_def (phi
, 0);
1728 arg0
= gimple_phi_arg_def (phi
, 0);
1729 arg1
= gimple_phi_arg_def (phi
, 1);
1731 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1733 /* Convert reduction stmt into vectorizable form. */
1734 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1735 true_bb
!= gimple_bb (reduc
));
1737 /* Build new RHS using selected condition and arguments. */
1738 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1740 new_stmt
= gimple_build_assign (res
, rhs
);
1741 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1742 update_stmt (new_stmt
);
1744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1746 fprintf (dump_file
, "new phi replacement stmt\n");
1747 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1752 /* Create hashmap for PHI node which contain vector of argument indexes
1753 having the same value. */
1755 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1756 unsigned int num_args
= gimple_phi_num_args (phi
);
1758 /* Vector of different PHI argument values. */
1759 auto_vec
<tree
> args (num_args
);
1761 /* Compute phi_arg_map. */
1762 for (i
= 0; i
< num_args
; i
++)
1766 arg
= gimple_phi_arg_def (phi
, i
);
1767 if (!phi_arg_map
.get (arg
))
1768 args
.quick_push (arg
);
1769 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1772 /* Determine element with max number of occurrences. */
1775 args_len
= args
.length ();
1776 for (i
= 0; i
< args_len
; i
++)
1779 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1786 /* Put element with max number of occurences to the end of ARGS. */
1787 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1788 std::swap (args
[args_len
- 1], args
[max_ind
]);
1790 /* Handle one special case when number of arguments with different values
1791 is equal 2 and one argument has the only occurrence. Such PHI can be
1792 handled as if would have only 2 arguments. */
1793 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1796 indexes
= phi_arg_map
.get (args
[0]);
1797 index0
= (*indexes
)[0];
1800 e
= gimple_phi_arg_edge (phi
, index0
);
1801 cond
= bb_predicate (e
->src
);
1802 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1805 cond
= TREE_OPERAND (cond
, 0);
1807 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1808 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1809 is_gimple_condexpr
, NULL_TREE
,
1810 true, GSI_SAME_STMT
);
1811 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1813 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1817 /* Convert reduction stmt into vectorizable form. */
1818 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1820 new_stmt
= gimple_build_assign (res
, rhs
);
1821 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1822 update_stmt (new_stmt
);
1828 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1831 for (i
= 0; i
< args_len
; i
++)
1834 indexes
= phi_arg_map
.get (args
[i
]);
1835 if (i
!= args_len
- 1)
1836 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1839 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1840 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1842 new_stmt
= gimple_build_assign (lhs
, rhs
);
1843 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1844 update_stmt (new_stmt
);
1849 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1851 fprintf (dump_file
, "new extended phi replacement stmt\n");
1852 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1856 /* Replaces in LOOP all the scalar phi nodes other than those in the
1857 LOOP->header block with conditional modify expressions. */
1860 predicate_all_scalar_phis (struct loop
*loop
)
1863 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1866 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1869 gimple_stmt_iterator gsi
;
1870 gphi_iterator phi_gsi
;
1873 if (bb
== loop
->header
)
1876 phi_gsi
= gsi_start_phis (bb
);
1877 if (gsi_end_p (phi_gsi
))
1880 gsi
= gsi_after_labels (bb
);
1881 while (!gsi_end_p (phi_gsi
))
1883 phi
= phi_gsi
.phi ();
1884 predicate_scalar_phi (phi
, &gsi
);
1885 release_phi_node (phi
);
1886 gsi_next (&phi_gsi
);
1889 set_phi_nodes (bb
, NULL
);
1893 /* Insert in each basic block of LOOP the statements produced by the
1894 gimplification of the predicates. */
1897 insert_gimplified_predicates (loop_p loop
)
1901 for (i
= 0; i
< loop
->num_nodes
; i
++)
1903 basic_block bb
= ifc_bbs
[i
];
1905 if (!is_predicated (bb
))
1906 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1907 if (!is_predicated (bb
))
1909 /* Do not insert statements for a basic block that is not
1910 predicated. Also make sure that the predicate of the
1911 basic block is set to true. */
1912 reset_bb_predicate (bb
);
1916 stmts
= bb_predicate_gimplified_stmts (bb
);
1919 if (any_pred_load_store
)
1921 /* Insert the predicate of the BB just after the label,
1922 as the if-conversion of memory writes will use this
1924 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1925 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1929 /* Insert the predicate of the BB at the end of the BB
1930 as this would reduce the register pressure: the only
1931 use of this predicate will be in successor BBs. */
1932 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1935 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1936 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1938 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1941 /* Once the sequence is code generated, set it to NULL. */
1942 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1947 /* Helper function for predicate_mem_writes. Returns index of existent
1948 mask if it was created for given SIZE and -1 otherwise. */
1951 mask_exists (int size
, vec
<int> vec
)
1955 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1961 /* Predicate each write to memory in LOOP.
1963 This function transforms control flow constructs containing memory
1966 | for (i = 0; i < N; i++)
1970 into the following form that does not contain control flow:
1972 | for (i = 0; i < N; i++)
1973 | A[i] = cond ? expr : A[i];
1975 The original CFG looks like this:
1982 | if (i < N) goto bb_5 else goto bb_2
1986 | cond = some_computation;
1987 | if (cond) goto bb_3 else goto bb_4
1999 insert_gimplified_predicates inserts the computation of the COND
2000 expression at the beginning of the destination basic block:
2007 | if (i < N) goto bb_5 else goto bb_2
2011 | cond = some_computation;
2012 | if (cond) goto bb_3 else goto bb_4
2016 | cond = some_computation;
2025 predicate_mem_writes is then predicating the memory write as follows:
2032 | if (i < N) goto bb_5 else goto bb_2
2036 | if (cond) goto bb_3 else goto bb_4
2040 | cond = some_computation;
2041 | A[i] = cond ? expr : A[i];
2049 and finally combine_blocks removes the basic block boundaries making
2050 the loop vectorizable:
2054 | if (i < N) goto bb_5 else goto bb_1
2058 | cond = some_computation;
2059 | A[i] = cond ? expr : A[i];
2060 | if (i < N) goto bb_5 else goto bb_4
2069 predicate_mem_writes (loop_p loop
)
2071 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2072 auto_vec
<int, 1> vect_sizes
;
2073 auto_vec
<tree
, 1> vect_masks
;
2075 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2077 gimple_stmt_iterator gsi
;
2078 basic_block bb
= ifc_bbs
[i
];
2079 tree cond
= bb_predicate (bb
);
2084 if (is_true_predicate (cond
) || is_false_predicate (cond
))
2088 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2091 cond
= TREE_OPERAND (cond
, 0);
2094 vect_sizes
.truncate (0);
2095 vect_masks
.truncate (0);
2097 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2098 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2100 else if (gimple_plf (stmt
, GF_PLF_2
))
2102 tree lhs
= gimple_assign_lhs (stmt
);
2103 tree rhs
= gimple_assign_rhs1 (stmt
);
2104 tree ref
, addr
, ptr
, mask
;
2106 gimple_seq stmts
= NULL
;
2107 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2108 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2109 mark_addressable (ref
);
2110 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2111 true, NULL_TREE
, true,
2113 if (!vect_sizes
.is_empty ()
2114 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2115 /* Use created mask. */
2116 mask
= vect_masks
[index
];
2119 if (COMPARISON_CLASS_P (cond
))
2120 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2122 TREE_OPERAND (cond
, 0),
2123 TREE_OPERAND (cond
, 1));
2126 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2133 = constant_boolean_node (true, TREE_TYPE (mask
));
2134 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2135 TREE_TYPE (mask
), mask
, true_val
);
2137 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2139 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2140 /* Save mask and its size for further use. */
2141 vect_sizes
.safe_push (bitsize
);
2142 vect_masks
.safe_push (mask
);
2144 ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2145 get_object_alignment (ref
));
2146 /* Copy points-to info if possible. */
2147 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2148 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2150 if (TREE_CODE (lhs
) == SSA_NAME
)
2153 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2155 gimple_call_set_lhs (new_stmt
, lhs
);
2159 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2161 gsi_replace (&gsi
, new_stmt
, true);
2163 else if (gimple_vdef (stmt
))
2165 tree lhs
= gimple_assign_lhs (stmt
);
2166 tree rhs
= gimple_assign_rhs1 (stmt
);
2167 tree type
= TREE_TYPE (lhs
);
2169 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2170 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2172 std::swap (lhs
, rhs
);
2173 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2174 is_gimple_condexpr
, NULL_TREE
,
2175 true, GSI_SAME_STMT
);
2176 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2177 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2183 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2184 other than the exit and latch of the LOOP. Also resets the
2185 GIMPLE_DEBUG information. */
2188 remove_conditions_and_labels (loop_p loop
)
2190 gimple_stmt_iterator gsi
;
2193 for (i
= 0; i
< loop
->num_nodes
; i
++)
2195 basic_block bb
= ifc_bbs
[i
];
2197 if (bb_with_exit_edge_p (loop
, bb
)
2198 || bb
== loop
->latch
)
2201 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2202 switch (gimple_code (gsi_stmt (gsi
)))
2206 gsi_remove (&gsi
, true);
2210 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2211 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2213 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2214 update_stmt (gsi_stmt (gsi
));
2225 /* Combine all the basic blocks from LOOP into one or two super basic
2226 blocks. Replace PHI nodes with conditional modify expressions. */
2229 combine_blocks (struct loop
*loop
)
2231 basic_block bb
, exit_bb
, merge_target_bb
;
2232 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2237 predicate_bbs (loop
);
2238 remove_conditions_and_labels (loop
);
2239 insert_gimplified_predicates (loop
);
2240 predicate_all_scalar_phis (loop
);
2242 if (any_pred_load_store
)
2243 predicate_mem_writes (loop
);
2245 /* Merge basic blocks: first remove all the edges in the loop,
2246 except for those from the exit block. */
2248 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2249 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2252 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2253 free_bb_predicate (bb
);
2254 if (bb_with_exit_edge_p (loop
, bb
))
2256 gcc_assert (exit_bb
== NULL
);
2260 gcc_assert (exit_bb
!= loop
->latch
);
2262 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2266 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2268 if (e
->src
== exit_bb
)
2275 if (exit_bb
!= NULL
)
2277 if (exit_bb
!= loop
->header
)
2279 /* Connect this node to loop header. */
2280 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2281 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2284 /* Redirect non-exit edges to loop->latch. */
2285 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2287 if (!loop_exit_edge_p (loop
, e
))
2288 redirect_edge_and_branch (e
, loop
->latch
);
2290 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2294 /* If the loop does not have an exit, reconnect header and latch. */
2295 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2296 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2299 merge_target_bb
= loop
->header
;
2300 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2302 gimple_stmt_iterator gsi
;
2303 gimple_stmt_iterator last
;
2307 if (bb
== exit_bb
|| bb
== loop
->latch
)
2310 /* Make stmts member of loop->header and clear range info from all stmts
2311 in BB which is now no longer executed conditional on a predicate we
2312 could have derived it from. */
2313 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2315 gimple
*stmt
= gsi_stmt (gsi
);
2316 gimple_set_bb (stmt
, merge_target_bb
);
2321 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2322 reset_flow_sensitive_info (op
);
2326 /* Update stmt list. */
2327 last
= gsi_last_bb (merge_target_bb
);
2328 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2329 set_bb_seq (bb
, NULL
);
2331 delete_basic_block (bb
);
2334 /* If possible, merge loop header to the block with the exit edge.
2335 This reduces the number of basic blocks to two, to please the
2336 vectorizer that handles only loops with two nodes. */
2338 && exit_bb
!= loop
->header
2339 && can_merge_blocks_p (loop
->header
, exit_bb
))
2340 merge_blocks (loop
->header
, exit_bb
);
2347 /* Version LOOP before if-converting it; the original loop
2348 will be if-converted, the new copy of the loop will not,
2349 and the LOOP_VECTORIZED internal call will be guarding which
2350 loop to execute. The vectorizer pass will fold this
2351 internal call into either true or false. */
2354 version_loop_for_if_conversion (struct loop
*loop
)
2356 basic_block cond_bb
;
2357 tree cond
= make_ssa_name (boolean_type_node
);
2358 struct loop
*new_loop
;
2360 gimple_stmt_iterator gsi
;
2362 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2363 build_int_cst (integer_type_node
, loop
->num
),
2365 gimple_call_set_lhs (g
, cond
);
2367 initialize_original_copy_tables ();
2368 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2369 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2370 REG_BR_PROB_BASE
, true);
2371 free_original_copy_tables ();
2372 if (new_loop
== NULL
)
2374 new_loop
->dont_vectorize
= true;
2375 new_loop
->force_vectorize
= false;
2376 gsi
= gsi_last_bb (cond_bb
);
2377 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2378 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2379 update_ssa (TODO_update_ssa
);
2383 /* Performs splitting of critical edges if aggressive_if_conv is true.
2384 Returns false if loop won't be if converted and true otherwise. */
2387 ifcvt_split_critical_edges (struct loop
*loop
)
2391 unsigned int num
= loop
->num_nodes
;
2401 if (!single_exit (loop
))
2404 body
= get_loop_body (loop
);
2405 for (i
= 0; i
< num
; i
++)
2408 if (bb
== loop
->latch
2409 || bb_with_exit_edge_p (loop
, bb
))
2411 stmt
= last_stmt (bb
);
2412 /* Skip basic blocks not ending with conditional branch. */
2413 if (!(stmt
&& gimple_code (stmt
) == GIMPLE_COND
))
2415 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2416 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2423 /* Assumes that lhs of DEF_STMT have multiple uses.
2424 Delete one use by (1) creation of copy DEF_STMT with
2425 unique lhs; (2) change original use of lhs in one
2426 use statement with newly created lhs. */
2429 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2434 gimple_stmt_iterator gsi
;
2435 use_operand_p use_p
;
2436 imm_use_iterator imm_iter
;
2438 var
= gimple_assign_lhs (def_stmt
);
2439 copy_stmt
= gimple_copy (def_stmt
);
2440 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2441 gimple_assign_set_lhs (copy_stmt
, lhs
);
2442 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2443 /* Insert copy of DEF_STMT. */
2444 gsi
= gsi_for_stmt (def_stmt
);
2445 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2446 /* Change use of var to lhs in use_stmt. */
2447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2449 fprintf (dump_file
, "Change use of var ");
2450 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2451 fprintf (dump_file
, " to ");
2452 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2453 fprintf (dump_file
, "\n");
2455 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2457 if (USE_STMT (use_p
) != use_stmt
)
2459 SET_USE (use_p
, lhs
);
2464 /* Traverse bool pattern recursively starting from VAR.
2465 Save its def and use statements to defuse_list if VAR does
2466 not have single use. */
2469 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2473 enum tree_code code
;
2476 def_stmt
= SSA_NAME_DEF_STMT (var
);
2477 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2479 if (!has_single_use (var
))
2481 /* Put def and use stmts into defuse_list. */
2482 defuse_list
->safe_push (def_stmt
);
2483 defuse_list
->safe_push (use_stmt
);
2484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2486 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2487 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2490 rhs1
= gimple_assign_rhs1 (def_stmt
);
2491 code
= gimple_assign_rhs_code (def_stmt
);
2495 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2498 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2499 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2500 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2502 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2505 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2510 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2511 rhs2
= gimple_assign_rhs2 (def_stmt
);
2512 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2520 /* Returns true if STMT can be a root of bool pattern applied
2524 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2526 enum tree_code code
;
2529 code
= gimple_assign_rhs_code (stmt
);
2530 if (CONVERT_EXPR_CODE_P (code
))
2532 lhs
= gimple_assign_lhs (stmt
);
2533 rhs
= gimple_assign_rhs1 (stmt
);
2534 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2536 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2540 else if (code
== COND_EXPR
)
2542 rhs
= gimple_assign_rhs1 (stmt
);
2543 if (TREE_CODE (rhs
) != SSA_NAME
)
2550 /* Traverse all statements in BB which correspond to loop header to
2551 find out all statements which can start bool pattern applied by
2552 vectorizer and convert multiple uses in it to conform pattern
2553 restrictions. Such case can occur if the same predicate is used both
2554 for phi node conversion and load/store mask. */
2557 ifcvt_repair_bool_pattern (basic_block bb
)
2561 gimple_stmt_iterator gsi
;
2562 vec
<gimple
*> defuse_list
= vNULL
;
2563 vec
<gimple
*> pattern_roots
= vNULL
;
2568 /* Collect all root pattern statements. */
2569 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2571 stmt
= gsi_stmt (gsi
);
2572 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2574 if (!stmt_is_root_of_bool_pattern (stmt
))
2576 pattern_roots
.safe_push (stmt
);
2579 if (pattern_roots
.is_empty ())
2582 /* Split all statements with multiple uses iteratively since splitting
2583 may create new multiple uses. */
2588 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2590 rhs
= gimple_assign_rhs1 (stmt
);
2591 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2592 while (defuse_list
.length () > 0)
2595 gimple
*def_stmt
, *use_stmt
;
2596 use_stmt
= defuse_list
.pop ();
2597 def_stmt
= defuse_list
.pop ();
2598 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2603 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2604 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2608 /* Delete redundant statements produced by predication which prevents
2609 loop vectorization. */
2612 ifcvt_local_dce (basic_block bb
)
2617 gimple_stmt_iterator gsi
;
2618 auto_vec
<gimple
*> worklist
;
2619 enum gimple_code code
;
2620 use_operand_p use_p
;
2621 imm_use_iterator imm_iter
;
2623 worklist
.create (64);
2624 /* Consider all phi as live statements. */
2625 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2627 phi
= gsi_stmt (gsi
);
2628 gimple_set_plf (phi
, GF_PLF_2
, true);
2629 worklist
.safe_push (phi
);
2631 /* Consider load/store statements, CALL and COND as live. */
2632 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2634 stmt
= gsi_stmt (gsi
);
2635 if (gimple_store_p (stmt
)
2636 || gimple_assign_load_p (stmt
)
2637 || is_gimple_debug (stmt
))
2639 gimple_set_plf (stmt
, GF_PLF_2
, true);
2640 worklist
.safe_push (stmt
);
2643 code
= gimple_code (stmt
);
2644 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2646 gimple_set_plf (stmt
, GF_PLF_2
, true);
2647 worklist
.safe_push (stmt
);
2650 gimple_set_plf (stmt
, GF_PLF_2
, false);
2652 if (code
== GIMPLE_ASSIGN
)
2654 tree lhs
= gimple_assign_lhs (stmt
);
2655 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2657 stmt1
= USE_STMT (use_p
);
2658 if (gimple_bb (stmt1
) != bb
)
2660 gimple_set_plf (stmt
, GF_PLF_2
, true);
2661 worklist
.safe_push (stmt
);
2667 /* Propagate liveness through arguments of live stmt. */
2668 while (worklist
.length () > 0)
2671 use_operand_p use_p
;
2674 stmt
= worklist
.pop ();
2675 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2677 use
= USE_FROM_PTR (use_p
);
2678 if (TREE_CODE (use
) != SSA_NAME
)
2680 stmt1
= SSA_NAME_DEF_STMT (use
);
2681 if (gimple_bb (stmt1
) != bb
2682 || gimple_plf (stmt1
, GF_PLF_2
))
2684 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2685 worklist
.safe_push (stmt1
);
2688 /* Delete dead statements. */
2689 gsi
= gsi_start_bb (bb
);
2690 while (!gsi_end_p (gsi
))
2692 stmt
= gsi_stmt (gsi
);
2693 if (gimple_plf (stmt
, GF_PLF_2
))
2698 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2700 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2701 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2703 gsi_remove (&gsi
, true);
2704 release_defs (stmt
);
2708 /* If-convert LOOP when it is legal. For the moment this pass has no
2709 profitability analysis. Returns non-zero todo flags when something
2713 tree_if_conversion (struct loop
*loop
)
2715 unsigned int todo
= 0;
2717 any_pred_load_store
= false;
2719 /* Set up aggressive if-conversion for loops marked with simd pragma. */
2720 aggressive_if_conv
= loop
->force_vectorize
;
2721 /* Check either outer loop was marked with simd pragma. */
2722 if (!aggressive_if_conv
)
2724 struct loop
*outer_loop
= loop_outer (loop
);
2725 if (outer_loop
&& outer_loop
->force_vectorize
)
2726 aggressive_if_conv
= true;
2729 if (aggressive_if_conv
)
2730 if (!ifcvt_split_critical_edges (loop
))
2733 if (!if_convertible_loop_p (loop
)
2734 || !dbg_cnt (if_conversion_tree
))
2737 if (any_pred_load_store
2738 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2739 || loop
->dont_vectorize
))
2742 if (any_pred_load_store
&& !version_loop_for_if_conversion (loop
))
2745 /* Now all statements are if-convertible. Combine all the basic
2746 blocks into one huge basic block doing the if-conversion
2748 combine_blocks (loop
);
2750 /* Delete dead predicate computations and repair tree correspondent
2751 to bool pattern to delete multiple uses of predicates. */
2752 if (aggressive_if_conv
)
2754 ifcvt_local_dce (loop
->header
);
2755 ifcvt_repair_bool_pattern (loop
->header
);
2758 todo
|= TODO_cleanup_cfg
;
2759 mark_virtual_operands_for_renaming (cfun
);
2760 todo
|= TODO_update_ssa_only_virtuals
;
2767 for (i
= 0; i
< loop
->num_nodes
; i
++)
2768 free_bb_predicate (ifc_bbs
[i
]);
2773 free_dominance_info (CDI_POST_DOMINATORS
);
2778 /* Tree if-conversion pass management. */
2782 const pass_data pass_data_if_conversion
=
2784 GIMPLE_PASS
, /* type */
2786 OPTGROUP_NONE
, /* optinfo_flags */
2787 TV_NONE
, /* tv_id */
2788 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2789 0, /* properties_provided */
2790 0, /* properties_destroyed */
2791 0, /* todo_flags_start */
2792 0, /* todo_flags_finish */
2795 class pass_if_conversion
: public gimple_opt_pass
2798 pass_if_conversion (gcc::context
*ctxt
)
2799 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2802 /* opt_pass methods: */
2803 virtual bool gate (function
*);
2804 virtual unsigned int execute (function
*);
2806 }; // class pass_if_conversion
2809 pass_if_conversion::gate (function
*fun
)
2811 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2812 && flag_tree_loop_if_convert
!= 0)
2813 || flag_tree_loop_if_convert
== 1
2814 || flag_tree_loop_if_convert_stores
== 1);
2818 pass_if_conversion::execute (function
*fun
)
2823 if (number_of_loops (fun
) <= 1)
2826 FOR_EACH_LOOP (loop
, 0)
2827 if (flag_tree_loop_if_convert
== 1
2828 || flag_tree_loop_if_convert_stores
== 1
2829 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2830 && !loop
->dont_vectorize
))
2831 todo
|= tree_if_conversion (loop
);
2836 FOR_EACH_BB_FN (bb
, fun
)
2837 gcc_assert (!bb
->aux
);
2846 make_pass_if_conversion (gcc::context
*ctxt
)
2848 return new pass_if_conversion (ctxt
);