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.h"
110 #include "tree-ssa-loop-niter.h"
111 #include "tree-ssa-loop-ivopts.h"
112 #include "tree-ssa-address.h"
114 #include "tree-hash-traits.h"
116 #include "builtins.h"
120 /* Only handle PHIs with no more arguments unless we are asked to by
122 #define MAX_PHI_ARG_NUM \
123 ((unsigned) PARAM_VALUE (PARAM_MAX_TREE_IF_CONVERSION_PHI_ARGS))
125 /* Indicate if new load/store that needs to be predicated is introduced
126 during if conversion. */
127 static bool any_pred_load_store
;
129 /* Indicate if there are any complicated PHIs that need to be handled in
130 if-conversion. Complicated PHI has more than two arguments and can't
131 be degenerated to two arguments PHI. See more information in comment
132 before phi_convertible_by_degenerating_args. */
133 static bool any_complicated_phi
;
135 /* Hash for struct innermost_loop_behavior. It depends on the user to
138 struct innermost_loop_behavior_hash
: nofree_ptr_hash
<innermost_loop_behavior
>
140 static inline hashval_t
hash (const value_type
&);
141 static inline bool equal (const value_type
&,
142 const compare_type
&);
146 innermost_loop_behavior_hash::hash (const value_type
&e
)
150 hash
= iterative_hash_expr (e
->base_address
, 0);
151 hash
= iterative_hash_expr (e
->offset
, hash
);
152 hash
= iterative_hash_expr (e
->init
, hash
);
153 return iterative_hash_expr (e
->step
, hash
);
157 innermost_loop_behavior_hash::equal (const value_type
&e1
,
158 const compare_type
&e2
)
160 if ((e1
->base_address
&& !e2
->base_address
)
161 || (!e1
->base_address
&& e2
->base_address
)
162 || (!e1
->offset
&& e2
->offset
)
163 || (e1
->offset
&& !e2
->offset
)
164 || (!e1
->init
&& e2
->init
)
165 || (e1
->init
&& !e2
->init
)
166 || (!e1
->step
&& e2
->step
)
167 || (e1
->step
&& !e2
->step
))
170 if (e1
->base_address
&& e2
->base_address
171 && !operand_equal_p (e1
->base_address
, e2
->base_address
, 0))
173 if (e1
->offset
&& e2
->offset
174 && !operand_equal_p (e1
->offset
, e2
->offset
, 0))
176 if (e1
->init
&& e2
->init
177 && !operand_equal_p (e1
->init
, e2
->init
, 0))
179 if (e1
->step
&& e2
->step
180 && !operand_equal_p (e1
->step
, e2
->step
, 0))
186 /* List of basic blocks in if-conversion-suitable order. */
187 static basic_block
*ifc_bbs
;
189 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
190 static hash_map
<innermost_loop_behavior_hash
,
191 data_reference_p
> *innermost_DR_map
;
193 /* Hash table to store <base reference, DR> pairs. */
194 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
196 /* Structure used to predicate basic blocks. This is attached to the
197 ->aux field of the BBs in the loop to be if-converted. */
198 struct bb_predicate
{
200 /* The condition under which this basic block is executed. */
203 /* PREDICATE is gimplified, and the sequence of statements is
204 recorded here, in order to avoid the duplication of computations
205 that occur in previous conditions. See PR44483. */
206 gimple_seq predicate_gimplified_stmts
;
209 /* Returns true when the basic block BB has a predicate. */
212 bb_has_predicate (basic_block bb
)
214 return bb
->aux
!= NULL
;
217 /* Returns the gimplified predicate for basic block BB. */
220 bb_predicate (basic_block bb
)
222 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
225 /* Sets the gimplified predicate COND for basic block BB. */
228 set_bb_predicate (basic_block bb
, tree cond
)
230 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
231 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
232 || is_gimple_condexpr (cond
));
233 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
236 /* Returns the sequence of statements of the gimplification of the
237 predicate for basic block BB. */
239 static inline gimple_seq
240 bb_predicate_gimplified_stmts (basic_block bb
)
242 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
245 /* Sets the sequence of statements STMTS of the gimplification of the
246 predicate for basic block BB. */
249 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
251 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
254 /* Adds the sequence of statements STMTS to the sequence of statements
255 of the predicate for basic block BB. */
258 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
261 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
264 /* Initializes to TRUE the predicate of basic block BB. */
267 init_bb_predicate (basic_block bb
)
269 bb
->aux
= XNEW (struct bb_predicate
);
270 set_bb_predicate_gimplified_stmts (bb
, NULL
);
271 set_bb_predicate (bb
, boolean_true_node
);
274 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
275 but don't actually free it. */
278 release_bb_predicate (basic_block bb
)
280 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
283 gimple_stmt_iterator i
;
285 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
286 free_stmt_operands (cfun
, gsi_stmt (i
));
287 set_bb_predicate_gimplified_stmts (bb
, NULL
);
291 /* Free the predicate of basic block BB. */
294 free_bb_predicate (basic_block bb
)
296 if (!bb_has_predicate (bb
))
299 release_bb_predicate (bb
);
304 /* Reinitialize predicate of BB with the true predicate. */
307 reset_bb_predicate (basic_block bb
)
309 if (!bb_has_predicate (bb
))
310 init_bb_predicate (bb
);
313 release_bb_predicate (bb
);
314 set_bb_predicate (bb
, boolean_true_node
);
318 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
319 the expression EXPR. Inserts the statement created for this
320 computation before GSI and leaves the iterator GSI at the same
324 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
326 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
327 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
328 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
332 /* Return true when COND is a false predicate. */
335 is_false_predicate (tree cond
)
337 return (cond
!= NULL_TREE
338 && (cond
== boolean_false_node
339 || integer_zerop (cond
)));
342 /* Return true when COND is a true predicate. */
345 is_true_predicate (tree cond
)
347 return (cond
== NULL_TREE
348 || cond
== boolean_true_node
349 || integer_onep (cond
));
352 /* Returns true when BB has a predicate that is not trivial: true or
356 is_predicated (basic_block bb
)
358 return !is_true_predicate (bb_predicate (bb
));
361 /* Parses the predicate COND and returns its comparison code and
362 operands OP0 and OP1. */
364 static enum tree_code
365 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
369 if (TREE_CODE (cond
) == SSA_NAME
370 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
372 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
374 *op0
= gimple_assign_rhs1 (s
);
375 *op1
= gimple_assign_rhs2 (s
);
376 return gimple_assign_rhs_code (s
);
379 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
381 tree op
= gimple_assign_rhs1 (s
);
382 tree type
= TREE_TYPE (op
);
383 enum tree_code code
= parse_predicate (op
, op0
, op1
);
385 return code
== ERROR_MARK
? ERROR_MARK
386 : invert_tree_comparison (code
, HONOR_NANS (type
));
392 if (COMPARISON_CLASS_P (cond
))
394 *op0
= TREE_OPERAND (cond
, 0);
395 *op1
= TREE_OPERAND (cond
, 1);
396 return TREE_CODE (cond
);
402 /* Returns the fold of predicate C1 OR C2 at location LOC. */
405 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
407 tree op1a
, op1b
, op2a
, op2b
;
408 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
409 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
411 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
413 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
419 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
422 /* Returns either a COND_EXPR or the folded expression if the folded
423 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
424 a constant or a SSA_NAME. */
427 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
429 tree rhs1
, lhs1
, cond_expr
;
431 /* If COND is comparison r != 0 and r has boolean type, convert COND
432 to SSA_NAME to accept by vect bool pattern. */
433 if (TREE_CODE (cond
) == NE_EXPR
)
435 tree op0
= TREE_OPERAND (cond
, 0);
436 tree op1
= TREE_OPERAND (cond
, 1);
437 if (TREE_CODE (op0
) == SSA_NAME
438 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
439 && (integer_zerop (op1
)))
442 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
, rhs
, lhs
);
444 if (cond_expr
== NULL_TREE
)
445 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
447 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
449 if (is_gimple_val (cond_expr
))
452 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
454 rhs1
= TREE_OPERAND (cond_expr
, 1);
455 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
456 if (is_gimple_val (rhs1
))
457 return build1 (ABS_EXPR
, type
, rhs1
);
460 if (TREE_CODE (cond_expr
) == MIN_EXPR
461 || TREE_CODE (cond_expr
) == MAX_EXPR
)
463 lhs1
= TREE_OPERAND (cond_expr
, 0);
464 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
465 rhs1
= TREE_OPERAND (cond_expr
, 1);
466 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
467 if (is_gimple_val (rhs1
) && is_gimple_val (lhs1
))
468 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
470 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
473 /* Add condition NC to the predicate list of basic block BB. LOOP is
474 the loop to be if-converted. Use predicate of cd-equivalent block
475 for join bb if it exists: we call basic blocks bb1 and bb2
476 cd-equivalent if they are executed under the same condition. */
479 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
484 if (is_true_predicate (nc
))
487 /* If dominance tells us this basic block is always executed,
488 don't record any predicates for it. */
489 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
492 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
493 /* We use notion of cd equivalence to get simpler predicate for
494 join block, e.g. if join block has 2 predecessors with predicates
495 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
496 p1 & p2 | p1 & !p2. */
497 if (dom_bb
!= loop
->header
498 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
500 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
501 bc
= bb_predicate (dom_bb
);
502 if (!is_true_predicate (bc
))
503 set_bb_predicate (bb
, bc
);
505 gcc_assert (is_true_predicate (bb_predicate (bb
)));
506 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
507 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
508 dom_bb
->index
, bb
->index
);
512 if (!is_predicated (bb
))
516 bc
= bb_predicate (bb
);
517 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
518 if (is_true_predicate (bc
))
520 reset_bb_predicate (bb
);
525 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
526 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
527 tp
= &TREE_OPERAND (bc
, 0);
530 if (!is_gimple_condexpr (*tp
))
533 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
534 add_bb_predicate_gimplified_stmts (bb
, stmts
);
536 set_bb_predicate (bb
, bc
);
539 /* Add the condition COND to the previous condition PREV_COND, and add
540 this to the predicate list of the destination of edge E. LOOP is
541 the loop to be if-converted. */
544 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
545 tree prev_cond
, tree cond
)
547 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
550 if (!is_true_predicate (prev_cond
))
551 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
554 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
555 add_to_predicate_list (loop
, e
->dest
, cond
);
558 /* Return true if one of the successor edges of BB exits LOOP. */
561 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
566 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
567 if (loop_exit_edge_p (loop
, e
))
573 /* Given PHI which has more than two arguments, this function checks if
574 it's if-convertible by degenerating its arguments. Specifically, if
575 below two conditions are satisfied:
577 1) Number of PHI arguments with different values equals to 2 and one
578 argument has the only occurrence.
579 2) The edge corresponding to the unique argument isn't critical edge.
581 Such PHI can be handled as PHIs have only two arguments. For example,
584 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
586 can be transformed into:
588 res = (predicate of e3) ? A_2 : A_1;
590 Return TRUE if it is the case, FALSE otherwise. */
593 phi_convertible_by_degenerating_args (gphi
*phi
)
596 tree arg
, t1
= NULL
, t2
= NULL
;
597 unsigned int i
, i1
= 0, i2
= 0, n1
= 0, n2
= 0;
598 unsigned int num_args
= gimple_phi_num_args (phi
);
600 gcc_assert (num_args
> 2);
602 for (i
= 0; i
< num_args
; i
++)
604 arg
= gimple_phi_arg_def (phi
, i
);
605 if (t1
== NULL
|| operand_equal_p (t1
, arg
, 0))
611 else if (t2
== NULL
|| operand_equal_p (t2
, arg
, 0))
621 if (n1
!= 1 && n2
!= 1)
624 /* Check if the edge corresponding to the unique arg is critical. */
625 e
= gimple_phi_arg_edge (phi
, (n1
== 1) ? i1
: i2
);
626 if (EDGE_COUNT (e
->src
->succs
) > 1)
632 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
633 and it belongs to basic block BB. Note at this point, it is sure
634 that PHI is if-convertible. This function updates global variable
635 ANY_COMPLICATED_PHI if PHI is complicated. */
638 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
)
640 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
642 fprintf (dump_file
, "-------------------------\n");
643 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
646 if (bb
!= loop
->header
647 && gimple_phi_num_args (phi
) > 2
648 && !phi_convertible_by_degenerating_args (phi
))
649 any_complicated_phi
= true;
654 /* Records the status of a data reference. This struct is attached to
655 each DR->aux field. */
658 bool rw_unconditionally
;
659 bool w_unconditionally
;
660 bool written_at_least_once
;
664 tree base_w_predicate
;
667 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
668 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
669 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
670 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
672 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
673 HASH tables. While storing them in HASH table, it checks if the
674 reference is unconditionally read or written and stores that as a flag
675 information. For base reference it checks if it is written atlest once
676 unconditionally and stores it as flag information along with DR.
677 In other words for every data reference A in STMT there exist other
678 accesses to a data reference with the same base with predicates that
679 add up (OR-up) to the true predicate: this ensures that the data
680 reference A is touched (read or written) on every iteration of the
681 if-converted loop. */
683 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
686 data_reference_p
*master_dr
, *base_master_dr
;
687 tree base_ref
= DR_BASE_OBJECT (a
);
688 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
689 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
692 master_dr
= &innermost_DR_map
->get_or_insert (innermost
, &exist1
);
698 IFC_DR (*master_dr
)->w_predicate
699 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
700 IFC_DR (*master_dr
)->w_predicate
);
701 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
702 DR_W_UNCONDITIONALLY (*master_dr
) = true;
704 IFC_DR (*master_dr
)->rw_predicate
705 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
706 IFC_DR (*master_dr
)->rw_predicate
);
707 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
708 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
712 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
715 IFC_DR (*base_master_dr
)->base_w_predicate
716 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
717 IFC_DR (*base_master_dr
)->base_w_predicate
);
718 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
719 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
723 /* Return TRUE if can prove the index IDX of an array reference REF is
724 within array bound. Return false otherwise. */
727 idx_within_array_bound (tree ref
, tree
*idx
, void *dta
)
730 widest_int niter
, valid_niter
, delta
, wi_step
;
733 struct loop
*loop
= (struct loop
*) dta
;
735 /* Only support within-bound access for array references. */
736 if (TREE_CODE (ref
) != ARRAY_REF
)
739 /* For arrays at the end of the structure, we are not guaranteed that they
740 do not really extend over their declared size. However, for arrays of
741 size greater than one, this is unlikely to be intended. */
742 if (array_at_struct_end_p (ref
))
745 ev
= analyze_scalar_evolution (loop
, *idx
);
746 ev
= instantiate_parameters (loop
, ev
);
747 init
= initial_condition (ev
);
748 step
= evolution_part_in_loop_num (ev
, loop
->num
);
750 if (!init
|| TREE_CODE (init
) != INTEGER_CST
751 || (step
&& TREE_CODE (step
) != INTEGER_CST
))
754 low
= array_ref_low_bound (ref
);
755 high
= array_ref_up_bound (ref
);
757 /* The case of nonconstant bounds could be handled, but it would be
759 if (TREE_CODE (low
) != INTEGER_CST
760 || !high
|| TREE_CODE (high
) != INTEGER_CST
)
763 /* Check if the intial idx is within bound. */
764 if (wi::to_widest (init
) < wi::to_widest (low
)
765 || wi::to_widest (init
) > wi::to_widest (high
))
768 /* The idx is always within bound. */
769 if (!step
|| integer_zerop (step
))
772 if (!max_loop_iterations (loop
, &niter
))
775 if (wi::to_widest (step
) < 0)
777 delta
= wi::to_widest (init
) - wi::to_widest (low
);
778 wi_step
= -wi::to_widest (step
);
782 delta
= wi::to_widest (high
) - wi::to_widest (init
);
783 wi_step
= wi::to_widest (step
);
786 valid_niter
= wi::div_floor (delta
, wi_step
, SIGNED
, &overflow
);
787 /* The iteration space of idx is within array bound. */
788 if (!overflow
&& niter
<= valid_niter
)
794 /* Return TRUE if ref is a within bound array reference. */
797 ref_within_array_bound (gimple
*stmt
, tree ref
)
799 struct loop
*loop
= loop_containing_stmt (stmt
);
801 gcc_assert (loop
!= NULL
);
802 return for_each_index (&ref
, idx_within_array_bound
, loop
);
806 /* Given a memory reference expression T, return TRUE if base object
807 it refers to is writable. The base object of a memory reference
808 is the main object being referenced, which is returned by function
812 base_object_writable (tree ref
)
814 tree base_tree
= get_base_address (ref
);
817 && DECL_P (base_tree
)
818 && decl_binds_to_current_def_p (base_tree
)
819 && !TREE_READONLY (base_tree
));
822 /* Return true when the memory references of STMT won't trap in the
823 if-converted code. There are two things that we have to check for:
825 - writes to memory occur to writable memory: if-conversion of
826 memory writes transforms the conditional memory writes into
827 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
828 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
829 be executed at all in the original code, it may be a readonly
830 memory. To check that A is not const-qualified, we check that
831 there exists at least an unconditional write to A in the current
834 - reads or writes to memory are valid memory accesses for every
835 iteration. To check that the memory accesses are correctly formed
836 and that we are allowed to read and write in these locations, we
837 check that the memory accesses to be if-converted occur at every
838 iteration unconditionally.
840 Returns true for the memory reference in STMT, same memory reference
841 is read or written unconditionally atleast once and the base memory
842 reference is written unconditionally once. This is to check reference
843 will not write fault. Also retuns true if the memory reference is
844 unconditionally read once then we are conditionally writing to memory
845 which is defined as read and write and is bound to the definition
848 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
850 data_reference_p
*master_dr
, *base_master_dr
;
851 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
853 tree base
= DR_BASE_OBJECT (a
);
854 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
856 gcc_assert (DR_STMT (a
) == stmt
);
857 gcc_assert (DR_BASE_ADDRESS (a
) || DR_OFFSET (a
)
858 || DR_INIT (a
) || DR_STEP (a
));
860 master_dr
= innermost_DR_map
->get (innermost
);
861 gcc_assert (master_dr
!= NULL
);
863 base_master_dr
= baseref_DR_map
->get (base
);
865 /* If a is unconditionally written to it doesn't trap. */
866 if (DR_W_UNCONDITIONALLY (*master_dr
))
869 /* If a is unconditionally accessed then ...
871 Even a is conditional access, we can treat it as an unconditional
872 one if it's an array reference and all its index are within array
874 if (DR_RW_UNCONDITIONALLY (*master_dr
)
875 || ref_within_array_bound (stmt
, DR_REF (a
)))
877 /* an unconditional read won't trap. */
881 /* an unconditionaly write won't trap if the base is written
882 to unconditionally. */
884 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
885 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
886 /* or the base is known to be not readonly. */
887 else if (base_object_writable (DR_REF (a
)))
888 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
894 /* Return true if STMT could be converted into a masked load or store
895 (conditional load or store based on a mask computed from bb predicate). */
898 ifcvt_can_use_mask_load_store (gimple
*stmt
)
902 basic_block bb
= gimple_bb (stmt
);
905 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
906 || bb
->loop_father
->dont_vectorize
907 || !gimple_assign_single_p (stmt
)
908 || gimple_has_volatile_ops (stmt
))
911 /* Check whether this is a load or store. */
912 lhs
= gimple_assign_lhs (stmt
);
913 if (gimple_store_p (stmt
))
915 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
920 else if (gimple_assign_load_p (stmt
))
923 ref
= gimple_assign_rhs1 (stmt
);
928 if (may_be_nonaddressable_p (ref
))
931 /* Mask should be integer mode of the same size as the load/store
933 mode
= TYPE_MODE (TREE_TYPE (lhs
));
934 if (int_mode_for_mode (mode
) == BLKmode
935 || VECTOR_MODE_P (mode
))
938 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
944 /* Return true when STMT is if-convertible.
946 GIMPLE_ASSIGN statement is not if-convertible if,
949 - LHS is not var decl. */
952 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
953 vec
<data_reference_p
> refs
)
955 tree lhs
= gimple_assign_lhs (stmt
);
957 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
959 fprintf (dump_file
, "-------------------------\n");
960 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
963 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
966 /* Some of these constrains might be too conservative. */
967 if (stmt_ends_bb_p (stmt
)
968 || gimple_has_volatile_ops (stmt
)
969 || (TREE_CODE (lhs
) == SSA_NAME
970 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
971 || gimple_has_side_effects (stmt
))
973 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
974 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
978 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
979 in between if_convertible_loop_p and combine_blocks
980 we can perform loop versioning. */
981 gimple_set_plf (stmt
, GF_PLF_2
, false);
983 if ((! gimple_vuse (stmt
)
984 || gimple_could_trap_p_1 (stmt
, false, false)
985 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
986 && gimple_could_trap_p (stmt
))
988 if (ifcvt_can_use_mask_load_store (stmt
))
990 gimple_set_plf (stmt
, GF_PLF_2
, true);
991 any_pred_load_store
= true;
994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
995 fprintf (dump_file
, "tree could trap...\n");
999 /* When if-converting stores force versioning, likewise if we
1000 ended up generating store data races. */
1001 if (gimple_vdef (stmt
))
1002 any_pred_load_store
= true;
1007 /* Return true when STMT is if-convertible.
1009 A statement is if-convertible if:
1010 - it is an if-convertible GIMPLE_ASSIGN,
1011 - it is a GIMPLE_LABEL or a GIMPLE_COND,
1012 - it is builtins call. */
1015 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
)
1017 switch (gimple_code (stmt
))
1025 return if_convertible_gimple_assign_stmt_p (stmt
, refs
);
1029 tree fndecl
= gimple_call_fndecl (stmt
);
1032 int flags
= gimple_call_flags (stmt
);
1033 if ((flags
& ECF_CONST
)
1034 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
1035 /* We can only vectorize some builtins at the moment,
1036 so restrict if-conversion to those. */
1037 && DECL_BUILT_IN (fndecl
))
1044 /* Don't know what to do with 'em so don't do anything. */
1045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1047 fprintf (dump_file
, "don't know what to do\n");
1048 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1057 /* Assumes that BB has more than 1 predecessors.
1058 Returns false if at least one successor is not on critical edge
1059 and true otherwise. */
1062 all_preds_critical_p (basic_block bb
)
1067 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1068 if (EDGE_COUNT (e
->src
->succs
) == 1)
1073 /* Returns true if at least one successor in on critical edge. */
1075 has_pred_critical_p (basic_block bb
)
1080 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1081 if (EDGE_COUNT (e
->src
->succs
) > 1)
1086 /* Return true when BB is if-convertible. This routine does not check
1087 basic block's statements and phis.
1089 A basic block is not if-convertible if:
1090 - it is non-empty and it is after the exit block (in BFS order),
1091 - it is after the exit block but before the latch,
1092 - its edges are not normal.
1094 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1098 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
1103 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1104 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1106 if (EDGE_COUNT (bb
->succs
) > 2)
1111 if (bb
!= loop
->latch
)
1113 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1114 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1117 else if (!empty_block_p (bb
))
1119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1120 fprintf (dump_file
, "non empty basic block after exit bb\n");
1123 else if (bb
== loop
->latch
1125 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1127 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1128 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1133 /* Be less adventurous and handle only normal edges. */
1134 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1135 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1137 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1138 fprintf (dump_file
, "Difficult to handle edges\n");
1145 /* Return true when all predecessor blocks of BB are visited. The
1146 VISITED bitmap keeps track of the visited blocks. */
1149 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1153 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1154 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1160 /* Get body of a LOOP in suitable order for if-conversion. It is
1161 caller's responsibility to deallocate basic block list.
1162 If-conversion suitable order is, breadth first sort (BFS) order
1163 with an additional constraint: select a block only if all its
1164 predecessors are already selected. */
1166 static basic_block
*
1167 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1169 basic_block
*blocks
, *blocks_in_bfs_order
;
1172 unsigned int index
= 0;
1173 unsigned int visited_count
= 0;
1175 gcc_assert (loop
->num_nodes
);
1176 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1178 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1179 visited
= BITMAP_ALLOC (NULL
);
1181 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1184 while (index
< loop
->num_nodes
)
1186 bb
= blocks_in_bfs_order
[index
];
1188 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1190 free (blocks_in_bfs_order
);
1191 BITMAP_FREE (visited
);
1196 if (!bitmap_bit_p (visited
, bb
->index
))
1198 if (pred_blocks_visited_p (bb
, &visited
)
1199 || bb
== loop
->header
)
1201 /* This block is now visited. */
1202 bitmap_set_bit (visited
, bb
->index
);
1203 blocks
[visited_count
++] = bb
;
1209 if (index
== loop
->num_nodes
1210 && visited_count
!= loop
->num_nodes
)
1214 free (blocks_in_bfs_order
);
1215 BITMAP_FREE (visited
);
1219 /* Returns true when the analysis of the predicates for all the basic
1220 blocks in LOOP succeeded.
1222 predicate_bbs first allocates the predicates of the basic blocks.
1223 These fields are then initialized with the tree expressions
1224 representing the predicates under which a basic block is executed
1225 in the LOOP. As the loop->header is executed at each iteration, it
1226 has the "true" predicate. Other statements executed under a
1227 condition are predicated with that condition, for example
1234 S1 will be predicated with "x", and
1235 S2 will be predicated with "!x". */
1238 predicate_bbs (loop_p loop
)
1242 for (i
= 0; i
< loop
->num_nodes
; i
++)
1243 init_bb_predicate (ifc_bbs
[i
]);
1245 for (i
= 0; i
< loop
->num_nodes
; i
++)
1247 basic_block bb
= ifc_bbs
[i
];
1251 /* The loop latch and loop exit block are always executed and
1252 have no extra conditions to be processed: skip them. */
1253 if (bb
== loop
->latch
1254 || bb_with_exit_edge_p (loop
, bb
))
1256 reset_bb_predicate (bb
);
1260 cond
= bb_predicate (bb
);
1261 stmt
= last_stmt (bb
);
1262 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1265 edge true_edge
, false_edge
;
1266 location_t loc
= gimple_location (stmt
);
1267 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1269 gimple_cond_lhs (stmt
),
1270 gimple_cond_rhs (stmt
));
1272 /* Add new condition into destination's predicate list. */
1273 extract_true_false_edges_from_block (gimple_bb (stmt
),
1274 &true_edge
, &false_edge
);
1276 /* If C is true, then TRUE_EDGE is taken. */
1277 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1280 /* If C is false, then FALSE_EDGE is taken. */
1281 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1283 add_to_dst_predicate_list (loop
, false_edge
,
1284 unshare_expr (cond
), c2
);
1289 /* If current bb has only one successor, then consider it as an
1290 unconditional goto. */
1291 if (single_succ_p (bb
))
1293 basic_block bb_n
= single_succ (bb
);
1295 /* The successor bb inherits the predicate of its
1296 predecessor. If there is no predicate in the predecessor
1297 bb, then consider the successor bb as always executed. */
1298 if (cond
== NULL_TREE
)
1299 cond
= boolean_true_node
;
1301 add_to_predicate_list (loop
, bb_n
, cond
);
1305 /* The loop header is always executed. */
1306 reset_bb_predicate (loop
->header
);
1307 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1308 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1311 /* Return true when LOOP is if-convertible. This is a helper function
1312 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1313 in if_convertible_loop_p. */
1316 if_convertible_loop_p_1 (struct loop
*loop
, vec
<data_reference_p
> *refs
)
1319 basic_block exit_bb
= NULL
;
1321 if (find_data_references_in_loop (loop
, refs
) == chrec_dont_know
)
1324 calculate_dominance_info (CDI_DOMINATORS
);
1325 calculate_dominance_info (CDI_POST_DOMINATORS
);
1327 /* Allow statements that can be handled during if-conversion. */
1328 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1331 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1332 fprintf (dump_file
, "Irreducible loop\n");
1336 for (i
= 0; i
< loop
->num_nodes
; i
++)
1338 basic_block bb
= ifc_bbs
[i
];
1340 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1343 if (bb_with_exit_edge_p (loop
, bb
))
1347 for (i
= 0; i
< loop
->num_nodes
; i
++)
1349 basic_block bb
= ifc_bbs
[i
];
1350 gimple_stmt_iterator gsi
;
1352 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1353 switch (gimple_code (gsi_stmt (gsi
)))
1360 gimple_set_uid (gsi_stmt (gsi
), 0);
1367 data_reference_p dr
;
1370 = new hash_map
<innermost_loop_behavior_hash
, data_reference_p
>;
1371 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1373 predicate_bbs (loop
);
1375 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1377 tree ref
= DR_REF (dr
);
1379 dr
->aux
= XNEW (struct ifc_dr
);
1380 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1381 DR_RW_UNCONDITIONALLY (dr
) = false;
1382 DR_W_UNCONDITIONALLY (dr
) = false;
1383 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1384 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1385 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1386 if (gimple_uid (DR_STMT (dr
)) == 0)
1387 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1389 /* If DR doesn't have innermost loop behavior or it's a compound
1390 memory reference, we synthesize its innermost loop behavior
1392 if (TREE_CODE (ref
) == COMPONENT_REF
1393 || TREE_CODE (ref
) == IMAGPART_EXPR
1394 || TREE_CODE (ref
) == REALPART_EXPR
1395 || !(DR_BASE_ADDRESS (dr
) || DR_OFFSET (dr
)
1396 || DR_INIT (dr
) || DR_STEP (dr
)))
1398 while (TREE_CODE (ref
) == COMPONENT_REF
1399 || TREE_CODE (ref
) == IMAGPART_EXPR
1400 || TREE_CODE (ref
) == REALPART_EXPR
)
1401 ref
= TREE_OPERAND (ref
, 0);
1403 DR_BASE_ADDRESS (dr
) = ref
;
1404 DR_OFFSET (dr
) = NULL
;
1405 DR_INIT (dr
) = NULL
;
1406 DR_STEP (dr
) = NULL
;
1407 DR_ALIGNED_TO (dr
) = NULL
;
1409 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1412 for (i
= 0; i
< loop
->num_nodes
; i
++)
1414 basic_block bb
= ifc_bbs
[i
];
1415 gimple_stmt_iterator itr
;
1417 /* Check the if-convertibility of statements in predicated BBs. */
1418 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1419 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1420 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
))
1424 for (i
= 0; i
< loop
->num_nodes
; i
++)
1425 free_bb_predicate (ifc_bbs
[i
]);
1427 /* Checking PHIs needs to be done after stmts, as the fact whether there
1428 are any masked loads or stores affects the tests. */
1429 for (i
= 0; i
< loop
->num_nodes
; i
++)
1431 basic_block bb
= ifc_bbs
[i
];
1434 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1435 if (!if_convertible_phi_p (loop
, bb
, itr
.phi ()))
1440 fprintf (dump_file
, "Applying if-conversion\n");
1445 /* Return true when LOOP is if-convertible.
1446 LOOP is if-convertible if:
1448 - it has two or more basic blocks,
1449 - it has only one exit,
1450 - loop header is not the exit edge,
1451 - if its basic blocks and phi nodes are if convertible. */
1454 if_convertible_loop_p (struct loop
*loop
)
1459 vec
<data_reference_p
> refs
;
1461 /* Handle only innermost loop. */
1462 if (!loop
|| loop
->inner
)
1464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1465 fprintf (dump_file
, "not innermost loop\n");
1469 /* If only one block, no need for if-conversion. */
1470 if (loop
->num_nodes
<= 2)
1472 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1473 fprintf (dump_file
, "less than 2 basic blocks\n");
1477 /* More than one loop exit is too much to handle. */
1478 if (!single_exit (loop
))
1480 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1481 fprintf (dump_file
, "multiple exits\n");
1485 /* If one of the loop header's edge is an exit edge then do not
1486 apply if-conversion. */
1487 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1488 if (loop_exit_edge_p (loop
, e
))
1492 res
= if_convertible_loop_p_1 (loop
, &refs
);
1494 data_reference_p dr
;
1496 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1499 free_data_refs (refs
);
1501 delete innermost_DR_map
;
1502 innermost_DR_map
= NULL
;
1504 delete baseref_DR_map
;
1505 baseref_DR_map
= NULL
;
1510 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1511 which is in predicated basic block.
1512 In fact, the following PHI pattern is searching:
1514 reduc_1 = PHI <..., reduc_2>
1518 reduc_2 = PHI <reduc_1, reduc_3>
1520 ARG_0 and ARG_1 are correspondent PHI arguments.
1521 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1522 EXTENDED is true if PHI has > 2 arguments. */
1525 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1526 tree
*op0
, tree
*op1
, bool extended
)
1528 tree lhs
, r_op1
, r_op2
;
1530 gimple
*header_phi
= NULL
;
1531 enum tree_code reduction_op
;
1532 basic_block bb
= gimple_bb (phi
);
1533 struct loop
*loop
= bb
->loop_father
;
1534 edge latch_e
= loop_latch_edge (loop
);
1535 imm_use_iterator imm_iter
;
1536 use_operand_p use_p
;
1539 bool result
= false;
1540 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1543 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1546 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1547 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1549 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1552 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1553 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1557 if (gimple_bb (header_phi
) != loop
->header
)
1560 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1563 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1564 || gimple_has_volatile_ops (stmt
))
1567 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1570 if (!is_predicated (gimple_bb (stmt
)))
1573 /* Check that stmt-block is predecessor of phi-block. */
1574 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1583 if (!has_single_use (lhs
))
1586 reduction_op
= gimple_assign_rhs_code (stmt
);
1587 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1589 r_op1
= gimple_assign_rhs1 (stmt
);
1590 r_op2
= gimple_assign_rhs2 (stmt
);
1592 /* Make R_OP1 to hold reduction variable. */
1593 if (r_op2
== PHI_RESULT (header_phi
)
1594 && reduction_op
== PLUS_EXPR
)
1595 std::swap (r_op1
, r_op2
);
1596 else if (r_op1
!= PHI_RESULT (header_phi
))
1599 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1600 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1602 gimple
*use_stmt
= USE_STMT (use_p
);
1603 if (is_gimple_debug (use_stmt
))
1605 if (use_stmt
== stmt
)
1607 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1611 *op0
= r_op1
; *op1
= r_op2
;
1616 /* Converts conditional scalar reduction into unconditional form, e.g.
1618 if (_5 != 0) goto bb_5 else goto bb_6
1624 # res_2 = PHI <res_13(4), res_6(5)>
1627 will be converted into sequence
1628 _ifc__1 = _5 != 0 ? 1 : 0;
1629 res_2 = res_13 + _ifc__1;
1630 Argument SWAP tells that arguments of conditional expression should be
1632 Returns rhs of resulting PHI assignment. */
1635 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1636 tree cond
, tree op0
, tree op1
, bool swap
)
1638 gimple_stmt_iterator stmt_it
;
1641 tree rhs1
= gimple_assign_rhs1 (reduc
);
1642 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1644 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1646 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1648 fprintf (dump_file
, "Found cond scalar reduction.\n");
1649 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1652 /* Build cond expression using COND and constant operand
1653 of reduction rhs. */
1654 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1655 unshare_expr (cond
),
1659 /* Create assignment stmt and insert it at GSI. */
1660 new_assign
= gimple_build_assign (tmp
, c
);
1661 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1662 /* Build rhs for unconditional increment/decrement. */
1663 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1664 TREE_TYPE (rhs1
), op0
, tmp
);
1666 /* Delete original reduction stmt. */
1667 stmt_it
= gsi_for_stmt (reduc
);
1668 gsi_remove (&stmt_it
, true);
1669 release_defs (reduc
);
1673 /* Produce condition for all occurrences of ARG in PHI node. */
1676 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1677 gimple_stmt_iterator
*gsi
)
1681 tree cond
= NULL_TREE
;
1685 len
= occur
->length ();
1686 gcc_assert (len
> 0);
1687 for (i
= 0; i
< len
; i
++)
1689 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1690 c
= bb_predicate (e
->src
);
1691 if (is_true_predicate (c
))
1693 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1694 is_gimple_condexpr
, NULL_TREE
,
1695 true, GSI_SAME_STMT
);
1696 if (cond
!= NULL_TREE
)
1698 /* Must build OR expression. */
1699 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1700 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1701 is_gimple_condexpr
, NULL_TREE
,
1702 true, GSI_SAME_STMT
);
1707 gcc_assert (cond
!= NULL_TREE
);
1711 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1712 This routine can handle PHI nodes with more than two arguments.
1715 S1: A = PHI <x1(1), x2(5)>
1717 S2: A = cond ? x1 : x2;
1719 The generated code is inserted at GSI that points to the top of
1720 basic block's statement list.
1721 If PHI node has more than two arguments a chain of conditional
1722 expression is produced. */
1726 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1728 gimple
*new_stmt
= NULL
, *reduc
;
1729 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1731 unsigned int index0
;
1732 unsigned int max
, args_len
;
1737 res
= gimple_phi_result (phi
);
1738 if (virtual_operand_p (res
))
1741 if ((rhs
= degenerate_phi_result (phi
))
1742 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1744 && !chrec_contains_undetermined (scev
)
1746 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1748 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1750 fprintf (dump_file
, "Degenerate phi!\n");
1751 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1753 new_stmt
= gimple_build_assign (res
, rhs
);
1754 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1755 update_stmt (new_stmt
);
1759 bb
= gimple_bb (phi
);
1760 if (EDGE_COUNT (bb
->preds
) == 2)
1762 /* Predicate ordinary PHI node with 2 arguments. */
1763 edge first_edge
, second_edge
;
1764 basic_block true_bb
;
1765 first_edge
= EDGE_PRED (bb
, 0);
1766 second_edge
= EDGE_PRED (bb
, 1);
1767 cond
= bb_predicate (first_edge
->src
);
1768 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1769 std::swap (first_edge
, second_edge
);
1770 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1772 cond
= bb_predicate (second_edge
->src
);
1773 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1774 cond
= TREE_OPERAND (cond
, 0);
1776 first_edge
= second_edge
;
1779 cond
= bb_predicate (first_edge
->src
);
1780 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1781 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1782 is_gimple_condexpr
, NULL_TREE
,
1783 true, GSI_SAME_STMT
);
1784 true_bb
= first_edge
->src
;
1785 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1787 arg0
= gimple_phi_arg_def (phi
, 1);
1788 arg1
= gimple_phi_arg_def (phi
, 0);
1792 arg0
= gimple_phi_arg_def (phi
, 0);
1793 arg1
= gimple_phi_arg_def (phi
, 1);
1795 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1797 /* Convert reduction stmt into vectorizable form. */
1798 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1799 true_bb
!= gimple_bb (reduc
));
1801 /* Build new RHS using selected condition and arguments. */
1802 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1804 new_stmt
= gimple_build_assign (res
, rhs
);
1805 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1806 update_stmt (new_stmt
);
1808 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1810 fprintf (dump_file
, "new phi replacement stmt\n");
1811 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1816 /* Create hashmap for PHI node which contain vector of argument indexes
1817 having the same value. */
1819 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1820 unsigned int num_args
= gimple_phi_num_args (phi
);
1822 /* Vector of different PHI argument values. */
1823 auto_vec
<tree
> args (num_args
);
1825 /* Compute phi_arg_map. */
1826 for (i
= 0; i
< num_args
; i
++)
1830 arg
= gimple_phi_arg_def (phi
, i
);
1831 if (!phi_arg_map
.get (arg
))
1832 args
.quick_push (arg
);
1833 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1836 /* Determine element with max number of occurrences. */
1839 args_len
= args
.length ();
1840 for (i
= 0; i
< args_len
; i
++)
1843 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1850 /* Put element with max number of occurences to the end of ARGS. */
1851 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1852 std::swap (args
[args_len
- 1], args
[max_ind
]);
1854 /* Handle one special case when number of arguments with different values
1855 is equal 2 and one argument has the only occurrence. Such PHI can be
1856 handled as if would have only 2 arguments. */
1857 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1860 indexes
= phi_arg_map
.get (args
[0]);
1861 index0
= (*indexes
)[0];
1864 e
= gimple_phi_arg_edge (phi
, index0
);
1865 cond
= bb_predicate (e
->src
);
1866 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1869 cond
= TREE_OPERAND (cond
, 0);
1871 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1872 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1873 is_gimple_condexpr
, NULL_TREE
,
1874 true, GSI_SAME_STMT
);
1875 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1877 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1881 /* Convert reduction stmt into vectorizable form. */
1882 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1884 new_stmt
= gimple_build_assign (res
, rhs
);
1885 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1886 update_stmt (new_stmt
);
1892 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1895 for (i
= 0; i
< args_len
; i
++)
1898 indexes
= phi_arg_map
.get (args
[i
]);
1899 if (i
!= args_len
- 1)
1900 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1903 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1904 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1906 new_stmt
= gimple_build_assign (lhs
, rhs
);
1907 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1908 update_stmt (new_stmt
);
1913 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1915 fprintf (dump_file
, "new extended phi replacement stmt\n");
1916 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1920 /* Replaces in LOOP all the scalar phi nodes other than those in the
1921 LOOP->header block with conditional modify expressions. */
1924 predicate_all_scalar_phis (struct loop
*loop
)
1927 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1930 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1933 gimple_stmt_iterator gsi
;
1934 gphi_iterator phi_gsi
;
1937 if (bb
== loop
->header
)
1940 phi_gsi
= gsi_start_phis (bb
);
1941 if (gsi_end_p (phi_gsi
))
1944 gsi
= gsi_after_labels (bb
);
1945 while (!gsi_end_p (phi_gsi
))
1947 phi
= phi_gsi
.phi ();
1948 predicate_scalar_phi (phi
, &gsi
);
1949 release_phi_node (phi
);
1950 gsi_next (&phi_gsi
);
1953 set_phi_nodes (bb
, NULL
);
1957 /* Insert in each basic block of LOOP the statements produced by the
1958 gimplification of the predicates. */
1961 insert_gimplified_predicates (loop_p loop
)
1965 for (i
= 0; i
< loop
->num_nodes
; i
++)
1967 basic_block bb
= ifc_bbs
[i
];
1969 if (!is_predicated (bb
))
1970 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1971 if (!is_predicated (bb
))
1973 /* Do not insert statements for a basic block that is not
1974 predicated. Also make sure that the predicate of the
1975 basic block is set to true. */
1976 reset_bb_predicate (bb
);
1980 stmts
= bb_predicate_gimplified_stmts (bb
);
1983 if (any_pred_load_store
)
1985 /* Insert the predicate of the BB just after the label,
1986 as the if-conversion of memory writes will use this
1988 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1989 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1993 /* Insert the predicate of the BB at the end of the BB
1994 as this would reduce the register pressure: the only
1995 use of this predicate will be in successor BBs. */
1996 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1999 || stmt_ends_bb_p (gsi_stmt (gsi
)))
2000 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2002 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
2005 /* Once the sequence is code generated, set it to NULL. */
2006 set_bb_predicate_gimplified_stmts (bb
, NULL
);
2011 /* Helper function for predicate_mem_writes. Returns index of existent
2012 mask if it was created for given SIZE and -1 otherwise. */
2015 mask_exists (int size
, vec
<int> vec
)
2019 FOR_EACH_VEC_ELT (vec
, ix
, v
)
2025 /* Predicate each write to memory in LOOP.
2027 This function transforms control flow constructs containing memory
2030 | for (i = 0; i < N; i++)
2034 into the following form that does not contain control flow:
2036 | for (i = 0; i < N; i++)
2037 | A[i] = cond ? expr : A[i];
2039 The original CFG looks like this:
2046 | if (i < N) goto bb_5 else goto bb_2
2050 | cond = some_computation;
2051 | if (cond) goto bb_3 else goto bb_4
2063 insert_gimplified_predicates inserts the computation of the COND
2064 expression at the beginning of the destination basic block:
2071 | if (i < N) goto bb_5 else goto bb_2
2075 | cond = some_computation;
2076 | if (cond) goto bb_3 else goto bb_4
2080 | cond = some_computation;
2089 predicate_mem_writes is then predicating the memory write as follows:
2096 | if (i < N) goto bb_5 else goto bb_2
2100 | if (cond) goto bb_3 else goto bb_4
2104 | cond = some_computation;
2105 | A[i] = cond ? expr : A[i];
2113 and finally combine_blocks removes the basic block boundaries making
2114 the loop vectorizable:
2118 | if (i < N) goto bb_5 else goto bb_1
2122 | cond = some_computation;
2123 | A[i] = cond ? expr : A[i];
2124 | if (i < N) goto bb_5 else goto bb_4
2133 predicate_mem_writes (loop_p loop
)
2135 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2136 auto_vec
<int, 1> vect_sizes
;
2137 auto_vec
<tree
, 1> vect_masks
;
2139 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2141 gimple_stmt_iterator gsi
;
2142 basic_block bb
= ifc_bbs
[i
];
2143 tree cond
= bb_predicate (bb
);
2148 if (is_true_predicate (cond
) || is_false_predicate (cond
))
2152 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2155 cond
= TREE_OPERAND (cond
, 0);
2158 vect_sizes
.truncate (0);
2159 vect_masks
.truncate (0);
2161 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2162 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2164 else if (gimple_plf (stmt
, GF_PLF_2
))
2166 tree lhs
= gimple_assign_lhs (stmt
);
2167 tree rhs
= gimple_assign_rhs1 (stmt
);
2168 tree ref
, addr
, ptr
, mask
;
2170 gimple_seq stmts
= NULL
;
2171 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2172 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2173 mark_addressable (ref
);
2174 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2175 true, NULL_TREE
, true,
2177 if (!vect_sizes
.is_empty ()
2178 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2179 /* Use created mask. */
2180 mask
= vect_masks
[index
];
2183 if (COMPARISON_CLASS_P (cond
))
2184 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2186 TREE_OPERAND (cond
, 0),
2187 TREE_OPERAND (cond
, 1));
2190 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2197 = constant_boolean_node (true, TREE_TYPE (mask
));
2198 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2199 TREE_TYPE (mask
), mask
, true_val
);
2201 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2203 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2204 /* Save mask and its size for further use. */
2205 vect_sizes
.safe_push (bitsize
);
2206 vect_masks
.safe_push (mask
);
2208 ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2209 get_object_alignment (ref
));
2210 /* Copy points-to info if possible. */
2211 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2212 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2214 if (TREE_CODE (lhs
) == SSA_NAME
)
2217 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2219 gimple_call_set_lhs (new_stmt
, lhs
);
2223 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2225 gsi_replace (&gsi
, new_stmt
, true);
2227 else if (gimple_vdef (stmt
))
2229 tree lhs
= gimple_assign_lhs (stmt
);
2230 tree rhs
= gimple_assign_rhs1 (stmt
);
2231 tree type
= TREE_TYPE (lhs
);
2233 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2234 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2236 std::swap (lhs
, rhs
);
2237 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2238 is_gimple_condexpr
, NULL_TREE
,
2239 true, GSI_SAME_STMT
);
2240 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2241 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2247 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2248 other than the exit and latch of the LOOP. Also resets the
2249 GIMPLE_DEBUG information. */
2252 remove_conditions_and_labels (loop_p loop
)
2254 gimple_stmt_iterator gsi
;
2257 for (i
= 0; i
< loop
->num_nodes
; i
++)
2259 basic_block bb
= ifc_bbs
[i
];
2261 if (bb_with_exit_edge_p (loop
, bb
)
2262 || bb
== loop
->latch
)
2265 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2266 switch (gimple_code (gsi_stmt (gsi
)))
2270 gsi_remove (&gsi
, true);
2274 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2275 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2277 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2278 update_stmt (gsi_stmt (gsi
));
2289 /* Combine all the basic blocks from LOOP into one or two super basic
2290 blocks. Replace PHI nodes with conditional modify expressions. */
2293 combine_blocks (struct loop
*loop
)
2295 basic_block bb
, exit_bb
, merge_target_bb
;
2296 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2301 predicate_bbs (loop
);
2302 remove_conditions_and_labels (loop
);
2303 insert_gimplified_predicates (loop
);
2304 predicate_all_scalar_phis (loop
);
2306 if (any_pred_load_store
)
2307 predicate_mem_writes (loop
);
2309 /* Merge basic blocks: first remove all the edges in the loop,
2310 except for those from the exit block. */
2312 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2313 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2316 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2317 free_bb_predicate (bb
);
2318 if (bb_with_exit_edge_p (loop
, bb
))
2320 gcc_assert (exit_bb
== NULL
);
2324 gcc_assert (exit_bb
!= loop
->latch
);
2326 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2330 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2332 if (e
->src
== exit_bb
)
2339 if (exit_bb
!= NULL
)
2341 if (exit_bb
!= loop
->header
)
2343 /* Connect this node to loop header. */
2344 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2345 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2348 /* Redirect non-exit edges to loop->latch. */
2349 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2351 if (!loop_exit_edge_p (loop
, e
))
2352 redirect_edge_and_branch (e
, loop
->latch
);
2354 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2358 /* If the loop does not have an exit, reconnect header and latch. */
2359 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2360 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2363 merge_target_bb
= loop
->header
;
2364 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2366 gimple_stmt_iterator gsi
;
2367 gimple_stmt_iterator last
;
2371 if (bb
== exit_bb
|| bb
== loop
->latch
)
2374 /* Make stmts member of loop->header and clear range info from all stmts
2375 in BB which is now no longer executed conditional on a predicate we
2376 could have derived it from. */
2377 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2379 gimple
*stmt
= gsi_stmt (gsi
);
2380 gimple_set_bb (stmt
, merge_target_bb
);
2385 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2386 reset_flow_sensitive_info (op
);
2390 /* Update stmt list. */
2391 last
= gsi_last_bb (merge_target_bb
);
2392 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2393 set_bb_seq (bb
, NULL
);
2395 delete_basic_block (bb
);
2398 /* If possible, merge loop header to the block with the exit edge.
2399 This reduces the number of basic blocks to two, to please the
2400 vectorizer that handles only loops with two nodes. */
2402 && exit_bb
!= loop
->header
2403 && can_merge_blocks_p (loop
->header
, exit_bb
))
2404 merge_blocks (loop
->header
, exit_bb
);
2411 /* Version LOOP before if-converting it; the original loop
2412 will be if-converted, the new copy of the loop will not,
2413 and the LOOP_VECTORIZED internal call will be guarding which
2414 loop to execute. The vectorizer pass will fold this
2415 internal call into either true or false. */
2418 version_loop_for_if_conversion (struct loop
*loop
)
2420 basic_block cond_bb
;
2421 tree cond
= make_ssa_name (boolean_type_node
);
2422 struct loop
*new_loop
;
2424 gimple_stmt_iterator gsi
;
2426 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2427 build_int_cst (integer_type_node
, loop
->num
),
2429 gimple_call_set_lhs (g
, cond
);
2431 initialize_original_copy_tables ();
2432 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2433 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2434 REG_BR_PROB_BASE
, true);
2435 free_original_copy_tables ();
2436 if (new_loop
== NULL
)
2438 new_loop
->dont_vectorize
= true;
2439 new_loop
->force_vectorize
= false;
2440 gsi
= gsi_last_bb (cond_bb
);
2441 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2442 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2443 update_ssa (TODO_update_ssa
);
2447 /* Performs splitting of critical edges. Skip splitting and return false
2448 if LOOP will not be converted because:
2450 - LOOP is not well formed.
2451 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
2453 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
2456 ifcvt_split_critical_edges (struct loop
*loop
, bool aggressive_if_conv
)
2460 unsigned int num
= loop
->num_nodes
;
2465 auto_vec
<edge
> critical_edges
;
2467 /* Loop is not well formed. */
2468 if (num
<= 2 || loop
->inner
|| !single_exit (loop
))
2471 body
= get_loop_body (loop
);
2472 for (i
= 0; i
< num
; i
++)
2475 if (!aggressive_if_conv
2477 && EDGE_COUNT (bb
->preds
) > MAX_PHI_ARG_NUM
)
2479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2481 "BB %d has complicated PHI with more than %u args.\n",
2482 bb
->index
, MAX_PHI_ARG_NUM
);
2487 if (bb
== loop
->latch
|| bb_with_exit_edge_p (loop
, bb
))
2490 stmt
= last_stmt (bb
);
2491 /* Skip basic blocks not ending with conditional branch. */
2492 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2495 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2496 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2497 critical_edges
.safe_push (e
);
2501 while (critical_edges
.length () > 0)
2503 e
= critical_edges
.pop ();
2504 /* Don't split if bb can be predicated along non-critical edge. */
2505 if (EDGE_COUNT (e
->dest
->preds
) > 2 || all_preds_critical_p (e
->dest
))
2512 /* Assumes that lhs of DEF_STMT have multiple uses.
2513 Delete one use by (1) creation of copy DEF_STMT with
2514 unique lhs; (2) change original use of lhs in one
2515 use statement with newly created lhs. */
2518 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2523 gimple_stmt_iterator gsi
;
2524 use_operand_p use_p
;
2525 imm_use_iterator imm_iter
;
2527 var
= gimple_assign_lhs (def_stmt
);
2528 copy_stmt
= gimple_copy (def_stmt
);
2529 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2530 gimple_assign_set_lhs (copy_stmt
, lhs
);
2531 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2532 /* Insert copy of DEF_STMT. */
2533 gsi
= gsi_for_stmt (def_stmt
);
2534 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2535 /* Change use of var to lhs in use_stmt. */
2536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2538 fprintf (dump_file
, "Change use of var ");
2539 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2540 fprintf (dump_file
, " to ");
2541 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2542 fprintf (dump_file
, "\n");
2544 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2546 if (USE_STMT (use_p
) != use_stmt
)
2548 SET_USE (use_p
, lhs
);
2553 /* Traverse bool pattern recursively starting from VAR.
2554 Save its def and use statements to defuse_list if VAR does
2555 not have single use. */
2558 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2562 enum tree_code code
;
2565 if (TREE_CODE (var
) != SSA_NAME
)
2568 def_stmt
= SSA_NAME_DEF_STMT (var
);
2569 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2571 if (!has_single_use (var
))
2573 /* Put def and use stmts into defuse_list. */
2574 defuse_list
->safe_push (def_stmt
);
2575 defuse_list
->safe_push (use_stmt
);
2576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2578 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2579 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2582 rhs1
= gimple_assign_rhs1 (def_stmt
);
2583 code
= gimple_assign_rhs_code (def_stmt
);
2587 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2590 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2591 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2592 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2594 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2597 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2602 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2603 rhs2
= gimple_assign_rhs2 (def_stmt
);
2604 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2612 /* Returns true if STMT can be a root of bool pattern applied
2616 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2618 enum tree_code code
;
2621 code
= gimple_assign_rhs_code (stmt
);
2622 if (CONVERT_EXPR_CODE_P (code
))
2624 lhs
= gimple_assign_lhs (stmt
);
2625 rhs
= gimple_assign_rhs1 (stmt
);
2626 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2628 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2632 else if (code
== COND_EXPR
)
2634 rhs
= gimple_assign_rhs1 (stmt
);
2635 if (TREE_CODE (rhs
) != SSA_NAME
)
2642 /* Traverse all statements in BB which correspond to loop header to
2643 find out all statements which can start bool pattern applied by
2644 vectorizer and convert multiple uses in it to conform pattern
2645 restrictions. Such case can occur if the same predicate is used both
2646 for phi node conversion and load/store mask. */
2649 ifcvt_repair_bool_pattern (basic_block bb
)
2653 gimple_stmt_iterator gsi
;
2654 vec
<gimple
*> defuse_list
= vNULL
;
2655 vec
<gimple
*> pattern_roots
= vNULL
;
2660 /* Collect all root pattern statements. */
2661 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2663 stmt
= gsi_stmt (gsi
);
2664 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2666 if (!stmt_is_root_of_bool_pattern (stmt
))
2668 pattern_roots
.safe_push (stmt
);
2671 if (pattern_roots
.is_empty ())
2674 /* Split all statements with multiple uses iteratively since splitting
2675 may create new multiple uses. */
2680 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2682 rhs
= gimple_assign_rhs1 (stmt
);
2683 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2684 while (defuse_list
.length () > 0)
2687 gimple
*def_stmt
, *use_stmt
;
2688 use_stmt
= defuse_list
.pop ();
2689 def_stmt
= defuse_list
.pop ();
2690 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2695 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2696 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2700 /* Delete redundant statements produced by predication which prevents
2701 loop vectorization. */
2704 ifcvt_local_dce (basic_block bb
)
2709 gimple_stmt_iterator gsi
;
2710 auto_vec
<gimple
*> worklist
;
2711 enum gimple_code code
;
2712 use_operand_p use_p
;
2713 imm_use_iterator imm_iter
;
2715 worklist
.create (64);
2716 /* Consider all phi as live statements. */
2717 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2719 phi
= gsi_stmt (gsi
);
2720 gimple_set_plf (phi
, GF_PLF_2
, true);
2721 worklist
.safe_push (phi
);
2723 /* Consider load/store statements, CALL and COND as live. */
2724 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2726 stmt
= gsi_stmt (gsi
);
2727 if (gimple_store_p (stmt
)
2728 || gimple_assign_load_p (stmt
)
2729 || is_gimple_debug (stmt
))
2731 gimple_set_plf (stmt
, GF_PLF_2
, true);
2732 worklist
.safe_push (stmt
);
2735 code
= gimple_code (stmt
);
2736 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2738 gimple_set_plf (stmt
, GF_PLF_2
, true);
2739 worklist
.safe_push (stmt
);
2742 gimple_set_plf (stmt
, GF_PLF_2
, false);
2744 if (code
== GIMPLE_ASSIGN
)
2746 tree lhs
= gimple_assign_lhs (stmt
);
2747 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2749 stmt1
= USE_STMT (use_p
);
2750 if (gimple_bb (stmt1
) != bb
)
2752 gimple_set_plf (stmt
, GF_PLF_2
, true);
2753 worklist
.safe_push (stmt
);
2759 /* Propagate liveness through arguments of live stmt. */
2760 while (worklist
.length () > 0)
2763 use_operand_p use_p
;
2766 stmt
= worklist
.pop ();
2767 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2769 use
= USE_FROM_PTR (use_p
);
2770 if (TREE_CODE (use
) != SSA_NAME
)
2772 stmt1
= SSA_NAME_DEF_STMT (use
);
2773 if (gimple_bb (stmt1
) != bb
2774 || gimple_plf (stmt1
, GF_PLF_2
))
2776 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2777 worklist
.safe_push (stmt1
);
2780 /* Delete dead statements. */
2781 gsi
= gsi_start_bb (bb
);
2782 while (!gsi_end_p (gsi
))
2784 stmt
= gsi_stmt (gsi
);
2785 if (gimple_plf (stmt
, GF_PLF_2
))
2790 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2792 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2793 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2795 gsi_remove (&gsi
, true);
2796 release_defs (stmt
);
2800 /* If-convert LOOP when it is legal. For the moment this pass has no
2801 profitability analysis. Returns non-zero todo flags when something
2805 tree_if_conversion (struct loop
*loop
)
2807 unsigned int todo
= 0;
2808 bool aggressive_if_conv
;
2811 any_pred_load_store
= false;
2812 any_complicated_phi
= false;
2814 /* Apply more aggressive if-conversion when loop or its outer loop were
2815 marked with simd pragma. When that's the case, we try to if-convert
2816 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
2817 aggressive_if_conv
= loop
->force_vectorize
;
2818 if (!aggressive_if_conv
)
2820 struct loop
*outer_loop
= loop_outer (loop
);
2821 if (outer_loop
&& outer_loop
->force_vectorize
)
2822 aggressive_if_conv
= true;
2825 if (!ifcvt_split_critical_edges (loop
, aggressive_if_conv
))
2828 if (!if_convertible_loop_p (loop
)
2829 || !dbg_cnt (if_conversion_tree
))
2832 if ((any_pred_load_store
|| any_complicated_phi
)
2833 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2834 || loop
->dont_vectorize
))
2837 if ((any_pred_load_store
|| any_complicated_phi
)
2838 && !version_loop_for_if_conversion (loop
))
2841 /* Now all statements are if-convertible. Combine all the basic
2842 blocks into one huge basic block doing the if-conversion
2844 combine_blocks (loop
);
2846 /* Delete dead predicate computations and repair tree correspondent
2847 to bool pattern to delete multiple uses of predicates. */
2848 ifcvt_local_dce (loop
->header
);
2849 ifcvt_repair_bool_pattern (loop
->header
);
2851 todo
|= TODO_cleanup_cfg
;
2852 mark_virtual_operands_for_renaming (cfun
);
2853 todo
|= TODO_update_ssa_only_virtuals
;
2860 for (i
= 0; i
< loop
->num_nodes
; i
++)
2861 free_bb_predicate (ifc_bbs
[i
]);
2866 free_dominance_info (CDI_POST_DOMINATORS
);
2871 /* Tree if-conversion pass management. */
2875 const pass_data pass_data_if_conversion
=
2877 GIMPLE_PASS
, /* type */
2879 OPTGROUP_NONE
, /* optinfo_flags */
2880 TV_NONE
, /* tv_id */
2881 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2882 0, /* properties_provided */
2883 0, /* properties_destroyed */
2884 0, /* todo_flags_start */
2885 0, /* todo_flags_finish */
2888 class pass_if_conversion
: public gimple_opt_pass
2891 pass_if_conversion (gcc::context
*ctxt
)
2892 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2895 /* opt_pass methods: */
2896 virtual bool gate (function
*);
2897 virtual unsigned int execute (function
*);
2899 }; // class pass_if_conversion
2902 pass_if_conversion::gate (function
*fun
)
2904 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2905 && flag_tree_loop_if_convert
!= 0)
2906 || flag_tree_loop_if_convert
== 1
2907 || flag_tree_loop_if_convert_stores
== 1);
2911 pass_if_conversion::execute (function
*fun
)
2916 if (number_of_loops (fun
) <= 1)
2919 /* If there are infinite loops, during CDI_POST_DOMINATORS computation
2920 we can pick pretty much random bb inside of the infinite loop that
2921 has the fake edge. If we are unlucky enough, this can confuse the
2922 add_to_predicate_list post-dominator check to optimize as if that
2923 bb or some other one is a join block when it actually is not.
2925 connect_infinite_loops_to_exit ();
2927 FOR_EACH_LOOP (loop
, 0)
2928 if (flag_tree_loop_if_convert
== 1
2929 || flag_tree_loop_if_convert_stores
== 1
2930 || ((flag_tree_loop_vectorize
|| loop
->force_vectorize
)
2931 && !loop
->dont_vectorize
))
2932 todo
|= tree_if_conversion (loop
);
2934 remove_fake_exit_edges ();
2939 FOR_EACH_BB_FN (bb
, fun
)
2940 gcc_assert (!bb
->aux
);
2949 make_pass_if_conversion (gcc::context
*ctxt
)
2951 return new pass_if_conversion (ctxt
);