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"
118 /* Only handle PHIs with no more arguments unless we are asked to by
120 #define MAX_PHI_ARG_NUM \
121 ((unsigned) PARAM_VALUE (PARAM_MAX_TREE_IF_CONVERSION_PHI_ARGS))
123 /* Indicate if new load/store that needs to be predicated is introduced
124 during if conversion. */
125 static bool any_pred_load_store
;
127 /* Indicate if there are any complicated PHIs that need to be handled in
128 if-conversion. Complicated PHI has more than two arguments and can't
129 be degenerated to two arguments PHI. See more information in comment
130 before phi_convertible_by_degenerating_args. */
131 static bool any_complicated_phi
;
133 /* Hash for struct innermost_loop_behavior. It depends on the user to
136 struct innermost_loop_behavior_hash
: nofree_ptr_hash
<innermost_loop_behavior
>
138 static inline hashval_t
hash (const value_type
&);
139 static inline bool equal (const value_type
&,
140 const compare_type
&);
144 innermost_loop_behavior_hash::hash (const value_type
&e
)
148 hash
= iterative_hash_expr (e
->base_address
, 0);
149 hash
= iterative_hash_expr (e
->offset
, hash
);
150 hash
= iterative_hash_expr (e
->init
, hash
);
151 return iterative_hash_expr (e
->step
, hash
);
155 innermost_loop_behavior_hash::equal (const value_type
&e1
,
156 const compare_type
&e2
)
158 if ((e1
->base_address
&& !e2
->base_address
)
159 || (!e1
->base_address
&& e2
->base_address
)
160 || (!e1
->offset
&& e2
->offset
)
161 || (e1
->offset
&& !e2
->offset
)
162 || (!e1
->init
&& e2
->init
)
163 || (e1
->init
&& !e2
->init
)
164 || (!e1
->step
&& e2
->step
)
165 || (e1
->step
&& !e2
->step
))
168 if (e1
->base_address
&& e2
->base_address
169 && !operand_equal_p (e1
->base_address
, e2
->base_address
, 0))
171 if (e1
->offset
&& e2
->offset
172 && !operand_equal_p (e1
->offset
, e2
->offset
, 0))
174 if (e1
->init
&& e2
->init
175 && !operand_equal_p (e1
->init
, e2
->init
, 0))
177 if (e1
->step
&& e2
->step
178 && !operand_equal_p (e1
->step
, e2
->step
, 0))
184 /* List of basic blocks in if-conversion-suitable order. */
185 static basic_block
*ifc_bbs
;
187 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
188 static hash_map
<innermost_loop_behavior_hash
,
189 data_reference_p
> *innermost_DR_map
;
191 /* Hash table to store <base reference, DR> pairs. */
192 static hash_map
<tree_operand_hash
, data_reference_p
> *baseref_DR_map
;
194 /* Structure used to predicate basic blocks. This is attached to the
195 ->aux field of the BBs in the loop to be if-converted. */
196 struct bb_predicate
{
198 /* The condition under which this basic block is executed. */
201 /* PREDICATE is gimplified, and the sequence of statements is
202 recorded here, in order to avoid the duplication of computations
203 that occur in previous conditions. See PR44483. */
204 gimple_seq predicate_gimplified_stmts
;
207 /* Returns true when the basic block BB has a predicate. */
210 bb_has_predicate (basic_block bb
)
212 return bb
->aux
!= NULL
;
215 /* Returns the gimplified predicate for basic block BB. */
218 bb_predicate (basic_block bb
)
220 return ((struct bb_predicate
*) bb
->aux
)->predicate
;
223 /* Sets the gimplified predicate COND for basic block BB. */
226 set_bb_predicate (basic_block bb
, tree cond
)
228 gcc_assert ((TREE_CODE (cond
) == TRUTH_NOT_EXPR
229 && is_gimple_condexpr (TREE_OPERAND (cond
, 0)))
230 || is_gimple_condexpr (cond
));
231 ((struct bb_predicate
*) bb
->aux
)->predicate
= cond
;
234 /* Returns the sequence of statements of the gimplification of the
235 predicate for basic block BB. */
237 static inline gimple_seq
238 bb_predicate_gimplified_stmts (basic_block bb
)
240 return ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
;
243 /* Sets the sequence of statements STMTS of the gimplification of the
244 predicate for basic block BB. */
247 set_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
249 ((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
= stmts
;
252 /* Adds the sequence of statements STMTS to the sequence of statements
253 of the predicate for basic block BB. */
256 add_bb_predicate_gimplified_stmts (basic_block bb
, gimple_seq stmts
)
259 (&(((struct bb_predicate
*) bb
->aux
)->predicate_gimplified_stmts
), stmts
);
262 /* Initializes to TRUE the predicate of basic block BB. */
265 init_bb_predicate (basic_block bb
)
267 bb
->aux
= XNEW (struct bb_predicate
);
268 set_bb_predicate_gimplified_stmts (bb
, NULL
);
269 set_bb_predicate (bb
, boolean_true_node
);
272 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
273 but don't actually free it. */
276 release_bb_predicate (basic_block bb
)
278 gimple_seq stmts
= bb_predicate_gimplified_stmts (bb
);
281 gimple_stmt_iterator i
;
283 for (i
= gsi_start (stmts
); !gsi_end_p (i
); gsi_next (&i
))
284 free_stmt_operands (cfun
, gsi_stmt (i
));
285 set_bb_predicate_gimplified_stmts (bb
, NULL
);
289 /* Free the predicate of basic block BB. */
292 free_bb_predicate (basic_block bb
)
294 if (!bb_has_predicate (bb
))
297 release_bb_predicate (bb
);
302 /* Reinitialize predicate of BB with the true predicate. */
305 reset_bb_predicate (basic_block bb
)
307 if (!bb_has_predicate (bb
))
308 init_bb_predicate (bb
);
311 release_bb_predicate (bb
);
312 set_bb_predicate (bb
, boolean_true_node
);
316 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
317 the expression EXPR. Inserts the statement created for this
318 computation before GSI and leaves the iterator GSI at the same
322 ifc_temp_var (tree type
, tree expr
, gimple_stmt_iterator
*gsi
)
324 tree new_name
= make_temp_ssa_name (type
, NULL
, "_ifc_");
325 gimple
*stmt
= gimple_build_assign (new_name
, expr
);
326 gsi_insert_before (gsi
, stmt
, GSI_SAME_STMT
);
330 /* Return true when COND is a false predicate. */
333 is_false_predicate (tree cond
)
335 return (cond
!= NULL_TREE
336 && (cond
== boolean_false_node
337 || integer_zerop (cond
)));
340 /* Return true when COND is a true predicate. */
343 is_true_predicate (tree cond
)
345 return (cond
== NULL_TREE
346 || cond
== boolean_true_node
347 || integer_onep (cond
));
350 /* Returns true when BB has a predicate that is not trivial: true or
354 is_predicated (basic_block bb
)
356 return !is_true_predicate (bb_predicate (bb
));
359 /* Parses the predicate COND and returns its comparison code and
360 operands OP0 and OP1. */
362 static enum tree_code
363 parse_predicate (tree cond
, tree
*op0
, tree
*op1
)
367 if (TREE_CODE (cond
) == SSA_NAME
368 && is_gimple_assign (s
= SSA_NAME_DEF_STMT (cond
)))
370 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s
)) == tcc_comparison
)
372 *op0
= gimple_assign_rhs1 (s
);
373 *op1
= gimple_assign_rhs2 (s
);
374 return gimple_assign_rhs_code (s
);
377 else if (gimple_assign_rhs_code (s
) == TRUTH_NOT_EXPR
)
379 tree op
= gimple_assign_rhs1 (s
);
380 tree type
= TREE_TYPE (op
);
381 enum tree_code code
= parse_predicate (op
, op0
, op1
);
383 return code
== ERROR_MARK
? ERROR_MARK
384 : invert_tree_comparison (code
, HONOR_NANS (type
));
390 if (COMPARISON_CLASS_P (cond
))
392 *op0
= TREE_OPERAND (cond
, 0);
393 *op1
= TREE_OPERAND (cond
, 1);
394 return TREE_CODE (cond
);
400 /* Returns the fold of predicate C1 OR C2 at location LOC. */
403 fold_or_predicates (location_t loc
, tree c1
, tree c2
)
405 tree op1a
, op1b
, op2a
, op2b
;
406 enum tree_code code1
= parse_predicate (c1
, &op1a
, &op1b
);
407 enum tree_code code2
= parse_predicate (c2
, &op2a
, &op2b
);
409 if (code1
!= ERROR_MARK
&& code2
!= ERROR_MARK
)
411 tree t
= maybe_fold_or_comparisons (code1
, op1a
, op1b
,
417 return fold_build2_loc (loc
, TRUTH_OR_EXPR
, boolean_type_node
, c1
, c2
);
420 /* Returns either a COND_EXPR or the folded expression if the folded
421 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
422 a constant or a SSA_NAME. */
425 fold_build_cond_expr (tree type
, tree cond
, tree rhs
, tree lhs
)
427 tree rhs1
, lhs1
, cond_expr
;
429 /* If COND is comparison r != 0 and r has boolean type, convert COND
430 to SSA_NAME to accept by vect bool pattern. */
431 if (TREE_CODE (cond
) == NE_EXPR
)
433 tree op0
= TREE_OPERAND (cond
, 0);
434 tree op1
= TREE_OPERAND (cond
, 1);
435 if (TREE_CODE (op0
) == SSA_NAME
436 && TREE_CODE (TREE_TYPE (op0
)) == BOOLEAN_TYPE
437 && (integer_zerop (op1
)))
440 cond_expr
= fold_ternary (COND_EXPR
, type
, cond
, rhs
, lhs
);
442 if (cond_expr
== NULL_TREE
)
443 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
445 STRIP_USELESS_TYPE_CONVERSION (cond_expr
);
447 if (is_gimple_val (cond_expr
))
450 if (TREE_CODE (cond_expr
) == ABS_EXPR
)
452 rhs1
= TREE_OPERAND (cond_expr
, 1);
453 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
454 if (is_gimple_val (rhs1
))
455 return build1 (ABS_EXPR
, type
, rhs1
);
458 if (TREE_CODE (cond_expr
) == MIN_EXPR
459 || TREE_CODE (cond_expr
) == MAX_EXPR
)
461 lhs1
= TREE_OPERAND (cond_expr
, 0);
462 STRIP_USELESS_TYPE_CONVERSION (lhs1
);
463 rhs1
= TREE_OPERAND (cond_expr
, 1);
464 STRIP_USELESS_TYPE_CONVERSION (rhs1
);
465 if (is_gimple_val (rhs1
) && is_gimple_val (lhs1
))
466 return build2 (TREE_CODE (cond_expr
), type
, lhs1
, rhs1
);
468 return build3 (COND_EXPR
, type
, cond
, rhs
, lhs
);
471 /* Add condition NC to the predicate list of basic block BB. LOOP is
472 the loop to be if-converted. Use predicate of cd-equivalent block
473 for join bb if it exists: we call basic blocks bb1 and bb2
474 cd-equivalent if they are executed under the same condition. */
477 add_to_predicate_list (struct loop
*loop
, basic_block bb
, tree nc
)
482 if (is_true_predicate (nc
))
485 /* If dominance tells us this basic block is always executed,
486 don't record any predicates for it. */
487 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
490 dom_bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
491 /* We use notion of cd equivalence to get simpler predicate for
492 join block, e.g. if join block has 2 predecessors with predicates
493 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
494 p1 & p2 | p1 & !p2. */
495 if (dom_bb
!= loop
->header
496 && get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
) == bb
)
498 gcc_assert (flow_bb_inside_loop_p (loop
, dom_bb
));
499 bc
= bb_predicate (dom_bb
);
500 if (!is_true_predicate (bc
))
501 set_bb_predicate (bb
, bc
);
503 gcc_assert (is_true_predicate (bb_predicate (bb
)));
504 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
505 fprintf (dump_file
, "Use predicate of bb#%d for bb#%d\n",
506 dom_bb
->index
, bb
->index
);
510 if (!is_predicated (bb
))
514 bc
= bb_predicate (bb
);
515 bc
= fold_or_predicates (EXPR_LOCATION (bc
), nc
, bc
);
516 if (is_true_predicate (bc
))
518 reset_bb_predicate (bb
);
523 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
524 if (TREE_CODE (bc
) == TRUTH_NOT_EXPR
)
525 tp
= &TREE_OPERAND (bc
, 0);
528 if (!is_gimple_condexpr (*tp
))
531 *tp
= force_gimple_operand_1 (*tp
, &stmts
, is_gimple_condexpr
, NULL_TREE
);
532 add_bb_predicate_gimplified_stmts (bb
, stmts
);
534 set_bb_predicate (bb
, bc
);
537 /* Add the condition COND to the previous condition PREV_COND, and add
538 this to the predicate list of the destination of edge E. LOOP is
539 the loop to be if-converted. */
542 add_to_dst_predicate_list (struct loop
*loop
, edge e
,
543 tree prev_cond
, tree cond
)
545 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
548 if (!is_true_predicate (prev_cond
))
549 cond
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
552 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, e
->dest
))
553 add_to_predicate_list (loop
, e
->dest
, cond
);
556 /* Return true if one of the successor edges of BB exits LOOP. */
559 bb_with_exit_edge_p (struct loop
*loop
, basic_block bb
)
564 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
565 if (loop_exit_edge_p (loop
, e
))
571 /* Given PHI which has more than two arguments, this function checks if
572 it's if-convertible by degenerating its arguments. Specifically, if
573 below two conditions are satisfied:
575 1) Number of PHI arguments with different values equals to 2 and one
576 argument has the only occurrence.
577 2) The edge corresponding to the unique argument isn't critical edge.
579 Such PHI can be handled as PHIs have only two arguments. For example,
582 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
584 can be transformed into:
586 res = (predicate of e3) ? A_2 : A_1;
588 Return TRUE if it is the case, FALSE otherwise. */
591 phi_convertible_by_degenerating_args (gphi
*phi
)
594 tree arg
, t1
= NULL
, t2
= NULL
;
595 unsigned int i
, i1
= 0, i2
= 0, n1
= 0, n2
= 0;
596 unsigned int num_args
= gimple_phi_num_args (phi
);
598 gcc_assert (num_args
> 2);
600 for (i
= 0; i
< num_args
; i
++)
602 arg
= gimple_phi_arg_def (phi
, i
);
603 if (t1
== NULL
|| operand_equal_p (t1
, arg
, 0))
609 else if (t2
== NULL
|| operand_equal_p (t2
, arg
, 0))
619 if (n1
!= 1 && n2
!= 1)
622 /* Check if the edge corresponding to the unique arg is critical. */
623 e
= gimple_phi_arg_edge (phi
, (n1
== 1) ? i1
: i2
);
624 if (EDGE_COUNT (e
->src
->succs
) > 1)
630 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
631 and it belongs to basic block BB. Note at this point, it is sure
632 that PHI is if-convertible. This function updates global variable
633 ANY_COMPLICATED_PHI if PHI is complicated. */
636 if_convertible_phi_p (struct loop
*loop
, basic_block bb
, gphi
*phi
)
638 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
640 fprintf (dump_file
, "-------------------------\n");
641 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
644 if (bb
!= loop
->header
645 && gimple_phi_num_args (phi
) > 2
646 && !phi_convertible_by_degenerating_args (phi
))
647 any_complicated_phi
= true;
652 /* Records the status of a data reference. This struct is attached to
653 each DR->aux field. */
656 bool rw_unconditionally
;
657 bool w_unconditionally
;
658 bool written_at_least_once
;
662 tree base_w_predicate
;
665 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
666 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
667 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
668 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
670 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
671 HASH tables. While storing them in HASH table, it checks if the
672 reference is unconditionally read or written and stores that as a flag
673 information. For base reference it checks if it is written atlest once
674 unconditionally and stores it as flag information along with DR.
675 In other words for every data reference A in STMT there exist other
676 accesses to a data reference with the same base with predicates that
677 add up (OR-up) to the true predicate: this ensures that the data
678 reference A is touched (read or written) on every iteration of the
679 if-converted loop. */
681 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a
)
684 data_reference_p
*master_dr
, *base_master_dr
;
685 tree base_ref
= DR_BASE_OBJECT (a
);
686 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
687 tree ca
= bb_predicate (gimple_bb (DR_STMT (a
)));
690 master_dr
= &innermost_DR_map
->get_or_insert (innermost
, &exist1
);
696 IFC_DR (*master_dr
)->w_predicate
697 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
698 IFC_DR (*master_dr
)->w_predicate
);
699 if (is_true_predicate (IFC_DR (*master_dr
)->w_predicate
))
700 DR_W_UNCONDITIONALLY (*master_dr
) = true;
702 IFC_DR (*master_dr
)->rw_predicate
703 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
704 IFC_DR (*master_dr
)->rw_predicate
);
705 if (is_true_predicate (IFC_DR (*master_dr
)->rw_predicate
))
706 DR_RW_UNCONDITIONALLY (*master_dr
) = true;
710 base_master_dr
= &baseref_DR_map
->get_or_insert (base_ref
, &exist2
);
713 IFC_DR (*base_master_dr
)->base_w_predicate
714 = fold_or_predicates (UNKNOWN_LOCATION
, ca
,
715 IFC_DR (*base_master_dr
)->base_w_predicate
);
716 if (is_true_predicate (IFC_DR (*base_master_dr
)->base_w_predicate
))
717 DR_BASE_W_UNCONDITIONALLY (*base_master_dr
) = true;
721 /* Return true when the memory references of STMT won't trap in the
722 if-converted code. There are two things that we have to check for:
724 - writes to memory occur to writable memory: if-conversion of
725 memory writes transforms the conditional memory writes into
726 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
727 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
728 be executed at all in the original code, it may be a readonly
729 memory. To check that A is not const-qualified, we check that
730 there exists at least an unconditional write to A in the current
733 - reads or writes to memory are valid memory accesses for every
734 iteration. To check that the memory accesses are correctly formed
735 and that we are allowed to read and write in these locations, we
736 check that the memory accesses to be if-converted occur at every
737 iteration unconditionally.
739 Returns true for the memory reference in STMT, same memory reference
740 is read or written unconditionally atleast once and the base memory
741 reference is written unconditionally once. This is to check reference
742 will not write fault. Also retuns true if the memory reference is
743 unconditionally read once then we are conditionally writing to memory
744 which is defined as read and write and is bound to the definition
747 ifcvt_memrefs_wont_trap (gimple
*stmt
, vec
<data_reference_p
> drs
)
749 data_reference_p
*master_dr
, *base_master_dr
;
750 data_reference_p a
= drs
[gimple_uid (stmt
) - 1];
752 tree base
= DR_BASE_OBJECT (a
);
753 innermost_loop_behavior
*innermost
= &DR_INNERMOST (a
);
755 gcc_assert (DR_STMT (a
) == stmt
);
756 gcc_assert (DR_BASE_ADDRESS (a
) || DR_OFFSET (a
)
757 || DR_INIT (a
) || DR_STEP (a
));
759 master_dr
= innermost_DR_map
->get (innermost
);
760 gcc_assert (master_dr
!= NULL
);
762 base_master_dr
= baseref_DR_map
->get (base
);
764 /* If a is unconditionally written to it doesn't trap. */
765 if (DR_W_UNCONDITIONALLY (*master_dr
))
768 /* If a is unconditionally accessed then ... */
769 if (DR_RW_UNCONDITIONALLY (*master_dr
))
771 /* an unconditional read won't trap. */
775 /* an unconditionaly write won't trap if the base is written
776 to unconditionally. */
778 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr
))
779 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
782 /* or the base is know to be not readonly. */
783 tree base_tree
= get_base_address (DR_REF (a
));
784 if (DECL_P (base_tree
)
785 && decl_binds_to_current_def_p (base_tree
)
786 && ! TREE_READONLY (base_tree
))
787 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES
);
793 /* Return true if STMT could be converted into a masked load or store
794 (conditional load or store based on a mask computed from bb predicate). */
797 ifcvt_can_use_mask_load_store (gimple
*stmt
)
801 basic_block bb
= gimple_bb (stmt
);
804 if (!(flag_tree_loop_vectorize
|| bb
->loop_father
->force_vectorize
)
805 || bb
->loop_father
->dont_vectorize
806 || !gimple_assign_single_p (stmt
)
807 || gimple_has_volatile_ops (stmt
))
810 /* Check whether this is a load or store. */
811 lhs
= gimple_assign_lhs (stmt
);
812 if (gimple_store_p (stmt
))
814 if (!is_gimple_val (gimple_assign_rhs1 (stmt
)))
819 else if (gimple_assign_load_p (stmt
))
822 ref
= gimple_assign_rhs1 (stmt
);
827 if (may_be_nonaddressable_p (ref
))
830 /* Mask should be integer mode of the same size as the load/store
832 mode
= TYPE_MODE (TREE_TYPE (lhs
));
833 if (int_mode_for_mode (mode
) == BLKmode
834 || VECTOR_MODE_P (mode
))
837 if (can_vec_mask_load_store_p (mode
, VOIDmode
, is_load
))
843 /* Return true when STMT is if-convertible.
845 GIMPLE_ASSIGN statement is not if-convertible if,
848 - LHS is not var decl. */
851 if_convertible_gimple_assign_stmt_p (gimple
*stmt
,
852 vec
<data_reference_p
> refs
)
854 tree lhs
= gimple_assign_lhs (stmt
);
856 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
858 fprintf (dump_file
, "-------------------------\n");
859 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
862 if (!is_gimple_reg_type (TREE_TYPE (lhs
)))
865 /* Some of these constrains might be too conservative. */
866 if (stmt_ends_bb_p (stmt
)
867 || gimple_has_volatile_ops (stmt
)
868 || (TREE_CODE (lhs
) == SSA_NAME
869 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs
))
870 || gimple_has_side_effects (stmt
))
872 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
873 fprintf (dump_file
, "stmt not suitable for ifcvt\n");
877 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
878 in between if_convertible_loop_p and combine_blocks
879 we can perform loop versioning. */
880 gimple_set_plf (stmt
, GF_PLF_2
, false);
882 if ((! gimple_vuse (stmt
)
883 || gimple_could_trap_p_1 (stmt
, false, false)
884 || ! ifcvt_memrefs_wont_trap (stmt
, refs
))
885 && gimple_could_trap_p (stmt
))
887 if (ifcvt_can_use_mask_load_store (stmt
))
889 gimple_set_plf (stmt
, GF_PLF_2
, true);
890 any_pred_load_store
= true;
893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
894 fprintf (dump_file
, "tree could trap...\n");
898 /* When if-converting stores force versioning, likewise if we
899 ended up generating store data races. */
900 if (gimple_vdef (stmt
))
901 any_pred_load_store
= true;
906 /* Return true when STMT is if-convertible.
908 A statement is if-convertible if:
909 - it is an if-convertible GIMPLE_ASSIGN,
910 - it is a GIMPLE_LABEL or a GIMPLE_COND,
911 - it is builtins call. */
914 if_convertible_stmt_p (gimple
*stmt
, vec
<data_reference_p
> refs
)
916 switch (gimple_code (stmt
))
924 return if_convertible_gimple_assign_stmt_p (stmt
, refs
);
928 tree fndecl
= gimple_call_fndecl (stmt
);
931 int flags
= gimple_call_flags (stmt
);
932 if ((flags
& ECF_CONST
)
933 && !(flags
& ECF_LOOPING_CONST_OR_PURE
)
934 /* We can only vectorize some builtins at the moment,
935 so restrict if-conversion to those. */
936 && DECL_BUILT_IN (fndecl
))
943 /* Don't know what to do with 'em so don't do anything. */
944 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
946 fprintf (dump_file
, "don't know what to do\n");
947 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
956 /* Assumes that BB has more than 1 predecessors.
957 Returns false if at least one successor is not on critical edge
958 and true otherwise. */
961 all_preds_critical_p (basic_block bb
)
966 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
967 if (EDGE_COUNT (e
->src
->succs
) == 1)
972 /* Returns true if at least one successor in on critical edge. */
974 has_pred_critical_p (basic_block bb
)
979 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
980 if (EDGE_COUNT (e
->src
->succs
) > 1)
985 /* Return true when BB is if-convertible. This routine does not check
986 basic block's statements and phis.
988 A basic block is not if-convertible if:
989 - it is non-empty and it is after the exit block (in BFS order),
990 - it is after the exit block but before the latch,
991 - its edges are not normal.
993 EXIT_BB is the basic block containing the exit of the LOOP. BB is
997 if_convertible_bb_p (struct loop
*loop
, basic_block bb
, basic_block exit_bb
)
1002 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1003 fprintf (dump_file
, "----------[%d]-------------\n", bb
->index
);
1005 if (EDGE_COUNT (bb
->succs
) > 2)
1010 if (bb
!= loop
->latch
)
1012 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1013 fprintf (dump_file
, "basic block after exit bb but before latch\n");
1016 else if (!empty_block_p (bb
))
1018 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1019 fprintf (dump_file
, "non empty basic block after exit bb\n");
1022 else if (bb
== loop
->latch
1024 && !dominated_by_p (CDI_DOMINATORS
, bb
, exit_bb
))
1026 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1027 fprintf (dump_file
, "latch is not dominated by exit_block\n");
1032 /* Be less adventurous and handle only normal edges. */
1033 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1034 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
| EDGE_IRREDUCIBLE_LOOP
))
1036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1037 fprintf (dump_file
, "Difficult to handle edges\n");
1044 /* Return true when all predecessor blocks of BB are visited. The
1045 VISITED bitmap keeps track of the visited blocks. */
1048 pred_blocks_visited_p (basic_block bb
, bitmap
*visited
)
1052 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1053 if (!bitmap_bit_p (*visited
, e
->src
->index
))
1059 /* Get body of a LOOP in suitable order for if-conversion. It is
1060 caller's responsibility to deallocate basic block list.
1061 If-conversion suitable order is, breadth first sort (BFS) order
1062 with an additional constraint: select a block only if all its
1063 predecessors are already selected. */
1065 static basic_block
*
1066 get_loop_body_in_if_conv_order (const struct loop
*loop
)
1068 basic_block
*blocks
, *blocks_in_bfs_order
;
1071 unsigned int index
= 0;
1072 unsigned int visited_count
= 0;
1074 gcc_assert (loop
->num_nodes
);
1075 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1077 blocks
= XCNEWVEC (basic_block
, loop
->num_nodes
);
1078 visited
= BITMAP_ALLOC (NULL
);
1080 blocks_in_bfs_order
= get_loop_body_in_bfs_order (loop
);
1083 while (index
< loop
->num_nodes
)
1085 bb
= blocks_in_bfs_order
[index
];
1087 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1089 free (blocks_in_bfs_order
);
1090 BITMAP_FREE (visited
);
1095 if (!bitmap_bit_p (visited
, bb
->index
))
1097 if (pred_blocks_visited_p (bb
, &visited
)
1098 || bb
== loop
->header
)
1100 /* This block is now visited. */
1101 bitmap_set_bit (visited
, bb
->index
);
1102 blocks
[visited_count
++] = bb
;
1108 if (index
== loop
->num_nodes
1109 && visited_count
!= loop
->num_nodes
)
1113 free (blocks_in_bfs_order
);
1114 BITMAP_FREE (visited
);
1118 /* Returns true when the analysis of the predicates for all the basic
1119 blocks in LOOP succeeded.
1121 predicate_bbs first allocates the predicates of the basic blocks.
1122 These fields are then initialized with the tree expressions
1123 representing the predicates under which a basic block is executed
1124 in the LOOP. As the loop->header is executed at each iteration, it
1125 has the "true" predicate. Other statements executed under a
1126 condition are predicated with that condition, for example
1133 S1 will be predicated with "x", and
1134 S2 will be predicated with "!x". */
1137 predicate_bbs (loop_p loop
)
1141 for (i
= 0; i
< loop
->num_nodes
; i
++)
1142 init_bb_predicate (ifc_bbs
[i
]);
1144 for (i
= 0; i
< loop
->num_nodes
; i
++)
1146 basic_block bb
= ifc_bbs
[i
];
1150 /* The loop latch and loop exit block are always executed and
1151 have no extra conditions to be processed: skip them. */
1152 if (bb
== loop
->latch
1153 || bb_with_exit_edge_p (loop
, bb
))
1155 reset_bb_predicate (bb
);
1159 cond
= bb_predicate (bb
);
1160 stmt
= last_stmt (bb
);
1161 if (stmt
&& gimple_code (stmt
) == GIMPLE_COND
)
1164 edge true_edge
, false_edge
;
1165 location_t loc
= gimple_location (stmt
);
1166 tree c
= build2_loc (loc
, gimple_cond_code (stmt
),
1168 gimple_cond_lhs (stmt
),
1169 gimple_cond_rhs (stmt
));
1171 /* Add new condition into destination's predicate list. */
1172 extract_true_false_edges_from_block (gimple_bb (stmt
),
1173 &true_edge
, &false_edge
);
1175 /* If C is true, then TRUE_EDGE is taken. */
1176 add_to_dst_predicate_list (loop
, true_edge
, unshare_expr (cond
),
1179 /* If C is false, then FALSE_EDGE is taken. */
1180 c2
= build1_loc (loc
, TRUTH_NOT_EXPR
, boolean_type_node
,
1182 add_to_dst_predicate_list (loop
, false_edge
,
1183 unshare_expr (cond
), c2
);
1188 /* If current bb has only one successor, then consider it as an
1189 unconditional goto. */
1190 if (single_succ_p (bb
))
1192 basic_block bb_n
= single_succ (bb
);
1194 /* The successor bb inherits the predicate of its
1195 predecessor. If there is no predicate in the predecessor
1196 bb, then consider the successor bb as always executed. */
1197 if (cond
== NULL_TREE
)
1198 cond
= boolean_true_node
;
1200 add_to_predicate_list (loop
, bb_n
, cond
);
1204 /* The loop header is always executed. */
1205 reset_bb_predicate (loop
->header
);
1206 gcc_assert (bb_predicate_gimplified_stmts (loop
->header
) == NULL
1207 && bb_predicate_gimplified_stmts (loop
->latch
) == NULL
);
1210 /* Return true when LOOP is if-convertible. This is a helper function
1211 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1212 in if_convertible_loop_p. */
1215 if_convertible_loop_p_1 (struct loop
*loop
, vec
<data_reference_p
> *refs
)
1218 basic_block exit_bb
= NULL
;
1220 if (find_data_references_in_loop (loop
, refs
) == chrec_dont_know
)
1223 calculate_dominance_info (CDI_DOMINATORS
);
1224 calculate_dominance_info (CDI_POST_DOMINATORS
);
1226 /* Allow statements that can be handled during if-conversion. */
1227 ifc_bbs
= get_loop_body_in_if_conv_order (loop
);
1230 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1231 fprintf (dump_file
, "Irreducible loop\n");
1235 for (i
= 0; i
< loop
->num_nodes
; i
++)
1237 basic_block bb
= ifc_bbs
[i
];
1239 if (!if_convertible_bb_p (loop
, bb
, exit_bb
))
1242 if (bb_with_exit_edge_p (loop
, bb
))
1246 for (i
= 0; i
< loop
->num_nodes
; i
++)
1248 basic_block bb
= ifc_bbs
[i
];
1249 gimple_stmt_iterator gsi
;
1251 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1252 switch (gimple_code (gsi_stmt (gsi
)))
1259 gimple_set_uid (gsi_stmt (gsi
), 0);
1266 data_reference_p dr
;
1269 = new hash_map
<innermost_loop_behavior_hash
, data_reference_p
>;
1270 baseref_DR_map
= new hash_map
<tree_operand_hash
, data_reference_p
>;
1272 predicate_bbs (loop
);
1274 for (i
= 0; refs
->iterate (i
, &dr
); i
++)
1276 tree ref
= DR_REF (dr
);
1278 dr
->aux
= XNEW (struct ifc_dr
);
1279 DR_BASE_W_UNCONDITIONALLY (dr
) = false;
1280 DR_RW_UNCONDITIONALLY (dr
) = false;
1281 DR_W_UNCONDITIONALLY (dr
) = false;
1282 IFC_DR (dr
)->rw_predicate
= boolean_false_node
;
1283 IFC_DR (dr
)->w_predicate
= boolean_false_node
;
1284 IFC_DR (dr
)->base_w_predicate
= boolean_false_node
;
1285 if (gimple_uid (DR_STMT (dr
)) == 0)
1286 gimple_set_uid (DR_STMT (dr
), i
+ 1);
1288 /* If DR doesn't have innermost loop behavior or it's a compound
1289 memory reference, we synthesize its innermost loop behavior
1291 if (TREE_CODE (ref
) == COMPONENT_REF
1292 || TREE_CODE (ref
) == IMAGPART_EXPR
1293 || TREE_CODE (ref
) == REALPART_EXPR
1294 || !(DR_BASE_ADDRESS (dr
) || DR_OFFSET (dr
)
1295 || DR_INIT (dr
) || DR_STEP (dr
)))
1297 while (TREE_CODE (ref
) == COMPONENT_REF
1298 || TREE_CODE (ref
) == IMAGPART_EXPR
1299 || TREE_CODE (ref
) == REALPART_EXPR
)
1300 ref
= TREE_OPERAND (ref
, 0);
1302 DR_BASE_ADDRESS (dr
) = ref
;
1303 DR_OFFSET (dr
) = NULL
;
1304 DR_INIT (dr
) = NULL
;
1305 DR_STEP (dr
) = NULL
;
1306 DR_ALIGNED_TO (dr
) = NULL
;
1308 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr
);
1311 for (i
= 0; i
< loop
->num_nodes
; i
++)
1313 basic_block bb
= ifc_bbs
[i
];
1314 gimple_stmt_iterator itr
;
1316 /* Check the if-convertibility of statements in predicated BBs. */
1317 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1318 for (itr
= gsi_start_bb (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1319 if (!if_convertible_stmt_p (gsi_stmt (itr
), *refs
))
1323 for (i
= 0; i
< loop
->num_nodes
; i
++)
1324 free_bb_predicate (ifc_bbs
[i
]);
1326 /* Checking PHIs needs to be done after stmts, as the fact whether there
1327 are any masked loads or stores affects the tests. */
1328 for (i
= 0; i
< loop
->num_nodes
; i
++)
1330 basic_block bb
= ifc_bbs
[i
];
1333 for (itr
= gsi_start_phis (bb
); !gsi_end_p (itr
); gsi_next (&itr
))
1334 if (!if_convertible_phi_p (loop
, bb
, itr
.phi ()))
1339 fprintf (dump_file
, "Applying if-conversion\n");
1344 /* Return true when LOOP is if-convertible.
1345 LOOP is if-convertible if:
1347 - it has two or more basic blocks,
1348 - it has only one exit,
1349 - loop header is not the exit edge,
1350 - if its basic blocks and phi nodes are if convertible. */
1353 if_convertible_loop_p (struct loop
*loop
)
1358 vec
<data_reference_p
> refs
;
1360 /* Handle only innermost loop. */
1361 if (!loop
|| loop
->inner
)
1363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1364 fprintf (dump_file
, "not innermost loop\n");
1368 /* If only one block, no need for if-conversion. */
1369 if (loop
->num_nodes
<= 2)
1371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1372 fprintf (dump_file
, "less than 2 basic blocks\n");
1376 /* More than one loop exit is too much to handle. */
1377 if (!single_exit (loop
))
1379 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1380 fprintf (dump_file
, "multiple exits\n");
1384 /* If one of the loop header's edge is an exit edge then do not
1385 apply if-conversion. */
1386 FOR_EACH_EDGE (e
, ei
, loop
->header
->succs
)
1387 if (loop_exit_edge_p (loop
, e
))
1391 res
= if_convertible_loop_p_1 (loop
, &refs
);
1393 data_reference_p dr
;
1395 for (i
= 0; refs
.iterate (i
, &dr
); i
++)
1398 free_data_refs (refs
);
1400 delete innermost_DR_map
;
1401 innermost_DR_map
= NULL
;
1403 delete baseref_DR_map
;
1404 baseref_DR_map
= NULL
;
1409 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1410 which is in predicated basic block.
1411 In fact, the following PHI pattern is searching:
1413 reduc_1 = PHI <..., reduc_2>
1417 reduc_2 = PHI <reduc_1, reduc_3>
1419 ARG_0 and ARG_1 are correspondent PHI arguments.
1420 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1421 EXTENDED is true if PHI has > 2 arguments. */
1424 is_cond_scalar_reduction (gimple
*phi
, gimple
**reduc
, tree arg_0
, tree arg_1
,
1425 tree
*op0
, tree
*op1
, bool extended
)
1427 tree lhs
, r_op1
, r_op2
;
1429 gimple
*header_phi
= NULL
;
1430 enum tree_code reduction_op
;
1431 basic_block bb
= gimple_bb (phi
);
1432 struct loop
*loop
= bb
->loop_father
;
1433 edge latch_e
= loop_latch_edge (loop
);
1434 imm_use_iterator imm_iter
;
1435 use_operand_p use_p
;
1438 bool result
= false;
1439 if (TREE_CODE (arg_0
) != SSA_NAME
|| TREE_CODE (arg_1
) != SSA_NAME
)
1442 if (!extended
&& gimple_code (SSA_NAME_DEF_STMT (arg_0
)) == GIMPLE_PHI
)
1445 header_phi
= SSA_NAME_DEF_STMT (arg_0
);
1446 stmt
= SSA_NAME_DEF_STMT (arg_1
);
1448 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1
)) == GIMPLE_PHI
)
1451 header_phi
= SSA_NAME_DEF_STMT (arg_1
);
1452 stmt
= SSA_NAME_DEF_STMT (arg_0
);
1456 if (gimple_bb (header_phi
) != loop
->header
)
1459 if (PHI_ARG_DEF_FROM_EDGE (header_phi
, latch_e
) != PHI_RESULT (phi
))
1462 if (gimple_code (stmt
) != GIMPLE_ASSIGN
1463 || gimple_has_volatile_ops (stmt
))
1466 if (!flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1469 if (!is_predicated (gimple_bb (stmt
)))
1472 /* Check that stmt-block is predecessor of phi-block. */
1473 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->succs
)
1482 if (!has_single_use (lhs
))
1485 reduction_op
= gimple_assign_rhs_code (stmt
);
1486 if (reduction_op
!= PLUS_EXPR
&& reduction_op
!= MINUS_EXPR
)
1488 r_op1
= gimple_assign_rhs1 (stmt
);
1489 r_op2
= gimple_assign_rhs2 (stmt
);
1491 /* Make R_OP1 to hold reduction variable. */
1492 if (r_op2
== PHI_RESULT (header_phi
)
1493 && reduction_op
== PLUS_EXPR
)
1494 std::swap (r_op1
, r_op2
);
1495 else if (r_op1
!= PHI_RESULT (header_phi
))
1498 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1499 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, r_op1
)
1501 gimple
*use_stmt
= USE_STMT (use_p
);
1502 if (is_gimple_debug (use_stmt
))
1504 if (use_stmt
== stmt
)
1506 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1510 *op0
= r_op1
; *op1
= r_op2
;
1515 /* Converts conditional scalar reduction into unconditional form, e.g.
1517 if (_5 != 0) goto bb_5 else goto bb_6
1523 # res_2 = PHI <res_13(4), res_6(5)>
1526 will be converted into sequence
1527 _ifc__1 = _5 != 0 ? 1 : 0;
1528 res_2 = res_13 + _ifc__1;
1529 Argument SWAP tells that arguments of conditional expression should be
1531 Returns rhs of resulting PHI assignment. */
1534 convert_scalar_cond_reduction (gimple
*reduc
, gimple_stmt_iterator
*gsi
,
1535 tree cond
, tree op0
, tree op1
, bool swap
)
1537 gimple_stmt_iterator stmt_it
;
1540 tree rhs1
= gimple_assign_rhs1 (reduc
);
1541 tree tmp
= make_temp_ssa_name (TREE_TYPE (rhs1
), NULL
, "_ifc_");
1543 tree zero
= build_zero_cst (TREE_TYPE (rhs1
));
1545 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1547 fprintf (dump_file
, "Found cond scalar reduction.\n");
1548 print_gimple_stmt (dump_file
, reduc
, 0, TDF_SLIM
);
1551 /* Build cond expression using COND and constant operand
1552 of reduction rhs. */
1553 c
= fold_build_cond_expr (TREE_TYPE (rhs1
),
1554 unshare_expr (cond
),
1558 /* Create assignment stmt and insert it at GSI. */
1559 new_assign
= gimple_build_assign (tmp
, c
);
1560 gsi_insert_before (gsi
, new_assign
, GSI_SAME_STMT
);
1561 /* Build rhs for unconditional increment/decrement. */
1562 rhs
= fold_build2 (gimple_assign_rhs_code (reduc
),
1563 TREE_TYPE (rhs1
), op0
, tmp
);
1565 /* Delete original reduction stmt. */
1566 stmt_it
= gsi_for_stmt (reduc
);
1567 gsi_remove (&stmt_it
, true);
1568 release_defs (reduc
);
1572 /* Produce condition for all occurrences of ARG in PHI node. */
1575 gen_phi_arg_condition (gphi
*phi
, vec
<int> *occur
,
1576 gimple_stmt_iterator
*gsi
)
1580 tree cond
= NULL_TREE
;
1584 len
= occur
->length ();
1585 gcc_assert (len
> 0);
1586 for (i
= 0; i
< len
; i
++)
1588 e
= gimple_phi_arg_edge (phi
, (*occur
)[i
]);
1589 c
= bb_predicate (e
->src
);
1590 if (is_true_predicate (c
))
1592 c
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (c
),
1593 is_gimple_condexpr
, NULL_TREE
,
1594 true, GSI_SAME_STMT
);
1595 if (cond
!= NULL_TREE
)
1597 /* Must build OR expression. */
1598 cond
= fold_or_predicates (EXPR_LOCATION (c
), c
, cond
);
1599 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1600 is_gimple_condexpr
, NULL_TREE
,
1601 true, GSI_SAME_STMT
);
1606 gcc_assert (cond
!= NULL_TREE
);
1610 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1611 This routine can handle PHI nodes with more than two arguments.
1614 S1: A = PHI <x1(1), x2(5)>
1616 S2: A = cond ? x1 : x2;
1618 The generated code is inserted at GSI that points to the top of
1619 basic block's statement list.
1620 If PHI node has more than two arguments a chain of conditional
1621 expression is produced. */
1625 predicate_scalar_phi (gphi
*phi
, gimple_stmt_iterator
*gsi
)
1627 gimple
*new_stmt
= NULL
, *reduc
;
1628 tree rhs
, res
, arg0
, arg1
, op0
, op1
, scev
;
1630 unsigned int index0
;
1631 unsigned int max
, args_len
;
1636 res
= gimple_phi_result (phi
);
1637 if (virtual_operand_p (res
))
1640 if ((rhs
= degenerate_phi_result (phi
))
1641 || ((scev
= analyze_scalar_evolution (gimple_bb (phi
)->loop_father
,
1643 && !chrec_contains_undetermined (scev
)
1645 && (rhs
= gimple_phi_arg_def (phi
, 0))))
1647 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1649 fprintf (dump_file
, "Degenerate phi!\n");
1650 print_gimple_stmt (dump_file
, phi
, 0, TDF_SLIM
);
1652 new_stmt
= gimple_build_assign (res
, rhs
);
1653 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1654 update_stmt (new_stmt
);
1658 bb
= gimple_bb (phi
);
1659 if (EDGE_COUNT (bb
->preds
) == 2)
1661 /* Predicate ordinary PHI node with 2 arguments. */
1662 edge first_edge
, second_edge
;
1663 basic_block true_bb
;
1664 first_edge
= EDGE_PRED (bb
, 0);
1665 second_edge
= EDGE_PRED (bb
, 1);
1666 cond
= bb_predicate (first_edge
->src
);
1667 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1668 std::swap (first_edge
, second_edge
);
1669 if (EDGE_COUNT (first_edge
->src
->succs
) > 1)
1671 cond
= bb_predicate (second_edge
->src
);
1672 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1673 cond
= TREE_OPERAND (cond
, 0);
1675 first_edge
= second_edge
;
1678 cond
= bb_predicate (first_edge
->src
);
1679 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1680 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1681 is_gimple_condexpr
, NULL_TREE
,
1682 true, GSI_SAME_STMT
);
1683 true_bb
= first_edge
->src
;
1684 if (EDGE_PRED (bb
, 1)->src
== true_bb
)
1686 arg0
= gimple_phi_arg_def (phi
, 1);
1687 arg1
= gimple_phi_arg_def (phi
, 0);
1691 arg0
= gimple_phi_arg_def (phi
, 0);
1692 arg1
= gimple_phi_arg_def (phi
, 1);
1694 if (is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1696 /* Convert reduction stmt into vectorizable form. */
1697 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1698 true_bb
!= gimple_bb (reduc
));
1700 /* Build new RHS using selected condition and arguments. */
1701 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1703 new_stmt
= gimple_build_assign (res
, rhs
);
1704 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1705 update_stmt (new_stmt
);
1707 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1709 fprintf (dump_file
, "new phi replacement stmt\n");
1710 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1715 /* Create hashmap for PHI node which contain vector of argument indexes
1716 having the same value. */
1718 hash_map
<tree_operand_hash
, auto_vec
<int> > phi_arg_map
;
1719 unsigned int num_args
= gimple_phi_num_args (phi
);
1721 /* Vector of different PHI argument values. */
1722 auto_vec
<tree
> args (num_args
);
1724 /* Compute phi_arg_map. */
1725 for (i
= 0; i
< num_args
; i
++)
1729 arg
= gimple_phi_arg_def (phi
, i
);
1730 if (!phi_arg_map
.get (arg
))
1731 args
.quick_push (arg
);
1732 phi_arg_map
.get_or_insert (arg
).safe_push (i
);
1735 /* Determine element with max number of occurrences. */
1738 args_len
= args
.length ();
1739 for (i
= 0; i
< args_len
; i
++)
1742 if ((len
= phi_arg_map
.get (args
[i
])->length ()) > max
)
1749 /* Put element with max number of occurences to the end of ARGS. */
1750 if (max_ind
!= -1 && max_ind
+1 != (int) args_len
)
1751 std::swap (args
[args_len
- 1], args
[max_ind
]);
1753 /* Handle one special case when number of arguments with different values
1754 is equal 2 and one argument has the only occurrence. Such PHI can be
1755 handled as if would have only 2 arguments. */
1756 if (args_len
== 2 && phi_arg_map
.get (args
[0])->length () == 1)
1759 indexes
= phi_arg_map
.get (args
[0]);
1760 index0
= (*indexes
)[0];
1763 e
= gimple_phi_arg_edge (phi
, index0
);
1764 cond
= bb_predicate (e
->src
);
1765 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
1768 cond
= TREE_OPERAND (cond
, 0);
1770 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1771 cond
= force_gimple_operand_gsi_1 (gsi
, unshare_expr (cond
),
1772 is_gimple_condexpr
, NULL_TREE
,
1773 true, GSI_SAME_STMT
);
1774 if (!(is_cond_scalar_reduction (phi
, &reduc
, arg0
, arg1
,
1776 rhs
= fold_build_cond_expr (TREE_TYPE (res
), unshare_expr (cond
),
1780 /* Convert reduction stmt into vectorizable form. */
1781 rhs
= convert_scalar_cond_reduction (reduc
, gsi
, cond
, op0
, op1
,
1783 new_stmt
= gimple_build_assign (res
, rhs
);
1784 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1785 update_stmt (new_stmt
);
1791 tree type
= TREE_TYPE (gimple_phi_result (phi
));
1794 for (i
= 0; i
< args_len
; i
++)
1797 indexes
= phi_arg_map
.get (args
[i
]);
1798 if (i
!= args_len
- 1)
1799 lhs
= make_temp_ssa_name (type
, NULL
, "_ifc_");
1802 cond
= gen_phi_arg_condition (phi
, indexes
, gsi
);
1803 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
),
1805 new_stmt
= gimple_build_assign (lhs
, rhs
);
1806 gsi_insert_before (gsi
, new_stmt
, GSI_SAME_STMT
);
1807 update_stmt (new_stmt
);
1812 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1814 fprintf (dump_file
, "new extended phi replacement stmt\n");
1815 print_gimple_stmt (dump_file
, new_stmt
, 0, TDF_SLIM
);
1819 /* Replaces in LOOP all the scalar phi nodes other than those in the
1820 LOOP->header block with conditional modify expressions. */
1823 predicate_all_scalar_phis (struct loop
*loop
)
1826 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
1829 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
1832 gimple_stmt_iterator gsi
;
1833 gphi_iterator phi_gsi
;
1836 if (bb
== loop
->header
)
1839 phi_gsi
= gsi_start_phis (bb
);
1840 if (gsi_end_p (phi_gsi
))
1843 gsi
= gsi_after_labels (bb
);
1844 while (!gsi_end_p (phi_gsi
))
1846 phi
= phi_gsi
.phi ();
1847 predicate_scalar_phi (phi
, &gsi
);
1848 release_phi_node (phi
);
1849 gsi_next (&phi_gsi
);
1852 set_phi_nodes (bb
, NULL
);
1856 /* Insert in each basic block of LOOP the statements produced by the
1857 gimplification of the predicates. */
1860 insert_gimplified_predicates (loop_p loop
)
1864 for (i
= 0; i
< loop
->num_nodes
; i
++)
1866 basic_block bb
= ifc_bbs
[i
];
1868 if (!is_predicated (bb
))
1869 gcc_assert (bb_predicate_gimplified_stmts (bb
) == NULL
);
1870 if (!is_predicated (bb
))
1872 /* Do not insert statements for a basic block that is not
1873 predicated. Also make sure that the predicate of the
1874 basic block is set to true. */
1875 reset_bb_predicate (bb
);
1879 stmts
= bb_predicate_gimplified_stmts (bb
);
1882 if (any_pred_load_store
)
1884 /* Insert the predicate of the BB just after the label,
1885 as the if-conversion of memory writes will use this
1887 gimple_stmt_iterator gsi
= gsi_after_labels (bb
);
1888 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1892 /* Insert the predicate of the BB at the end of the BB
1893 as this would reduce the register pressure: the only
1894 use of this predicate will be in successor BBs. */
1895 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
1898 || stmt_ends_bb_p (gsi_stmt (gsi
)))
1899 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
1901 gsi_insert_seq_after (&gsi
, stmts
, GSI_SAME_STMT
);
1904 /* Once the sequence is code generated, set it to NULL. */
1905 set_bb_predicate_gimplified_stmts (bb
, NULL
);
1910 /* Helper function for predicate_mem_writes. Returns index of existent
1911 mask if it was created for given SIZE and -1 otherwise. */
1914 mask_exists (int size
, vec
<int> vec
)
1918 FOR_EACH_VEC_ELT (vec
, ix
, v
)
1924 /* Predicate each write to memory in LOOP.
1926 This function transforms control flow constructs containing memory
1929 | for (i = 0; i < N; i++)
1933 into the following form that does not contain control flow:
1935 | for (i = 0; i < N; i++)
1936 | A[i] = cond ? expr : A[i];
1938 The original CFG looks like this:
1945 | if (i < N) goto bb_5 else goto bb_2
1949 | cond = some_computation;
1950 | if (cond) goto bb_3 else goto bb_4
1962 insert_gimplified_predicates inserts the computation of the COND
1963 expression at the beginning of the destination basic block:
1970 | if (i < N) goto bb_5 else goto bb_2
1974 | cond = some_computation;
1975 | if (cond) goto bb_3 else goto bb_4
1979 | cond = some_computation;
1988 predicate_mem_writes is then predicating the memory write as follows:
1995 | if (i < N) goto bb_5 else goto bb_2
1999 | if (cond) goto bb_3 else goto bb_4
2003 | cond = some_computation;
2004 | A[i] = cond ? expr : A[i];
2012 and finally combine_blocks removes the basic block boundaries making
2013 the loop vectorizable:
2017 | if (i < N) goto bb_5 else goto bb_1
2021 | cond = some_computation;
2022 | A[i] = cond ? expr : A[i];
2023 | if (i < N) goto bb_5 else goto bb_4
2032 predicate_mem_writes (loop_p loop
)
2034 unsigned int i
, orig_loop_num_nodes
= loop
->num_nodes
;
2035 auto_vec
<int, 1> vect_sizes
;
2036 auto_vec
<tree
, 1> vect_masks
;
2038 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2040 gimple_stmt_iterator gsi
;
2041 basic_block bb
= ifc_bbs
[i
];
2042 tree cond
= bb_predicate (bb
);
2047 if (is_true_predicate (cond
) || is_false_predicate (cond
))
2051 if (TREE_CODE (cond
) == TRUTH_NOT_EXPR
)
2054 cond
= TREE_OPERAND (cond
, 0);
2057 vect_sizes
.truncate (0);
2058 vect_masks
.truncate (0);
2060 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2061 if (!gimple_assign_single_p (stmt
= gsi_stmt (gsi
)))
2063 else if (gimple_plf (stmt
, GF_PLF_2
))
2065 tree lhs
= gimple_assign_lhs (stmt
);
2066 tree rhs
= gimple_assign_rhs1 (stmt
);
2067 tree ref
, addr
, ptr
, mask
;
2069 gimple_seq stmts
= NULL
;
2070 int bitsize
= GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs
)));
2071 ref
= TREE_CODE (lhs
) == SSA_NAME
? rhs
: lhs
;
2072 mark_addressable (ref
);
2073 addr
= force_gimple_operand_gsi (&gsi
, build_fold_addr_expr (ref
),
2074 true, NULL_TREE
, true,
2076 if (!vect_sizes
.is_empty ()
2077 && (index
= mask_exists (bitsize
, vect_sizes
)) != -1)
2078 /* Use created mask. */
2079 mask
= vect_masks
[index
];
2082 if (COMPARISON_CLASS_P (cond
))
2083 mask
= gimple_build (&stmts
, TREE_CODE (cond
),
2085 TREE_OPERAND (cond
, 0),
2086 TREE_OPERAND (cond
, 1));
2089 gcc_assert (TREE_CODE (cond
) == SSA_NAME
);
2096 = constant_boolean_node (true, TREE_TYPE (mask
));
2097 mask
= gimple_build (&stmts
, BIT_XOR_EXPR
,
2098 TREE_TYPE (mask
), mask
, true_val
);
2100 gsi_insert_seq_before (&gsi
, stmts
, GSI_SAME_STMT
);
2102 mask
= ifc_temp_var (TREE_TYPE (mask
), mask
, &gsi
);
2103 /* Save mask and its size for further use. */
2104 vect_sizes
.safe_push (bitsize
);
2105 vect_masks
.safe_push (mask
);
2107 ptr
= build_int_cst (reference_alias_ptr_type (ref
),
2108 get_object_alignment (ref
));
2109 /* Copy points-to info if possible. */
2110 if (TREE_CODE (addr
) == SSA_NAME
&& !SSA_NAME_PTR_INFO (addr
))
2111 copy_ref_info (build2 (MEM_REF
, TREE_TYPE (ref
), addr
, ptr
),
2113 if (TREE_CODE (lhs
) == SSA_NAME
)
2116 = gimple_build_call_internal (IFN_MASK_LOAD
, 3, addr
,
2118 gimple_call_set_lhs (new_stmt
, lhs
);
2122 = gimple_build_call_internal (IFN_MASK_STORE
, 4, addr
, ptr
,
2124 gsi_replace (&gsi
, new_stmt
, true);
2126 else if (gimple_vdef (stmt
))
2128 tree lhs
= gimple_assign_lhs (stmt
);
2129 tree rhs
= gimple_assign_rhs1 (stmt
);
2130 tree type
= TREE_TYPE (lhs
);
2132 lhs
= ifc_temp_var (type
, unshare_expr (lhs
), &gsi
);
2133 rhs
= ifc_temp_var (type
, unshare_expr (rhs
), &gsi
);
2135 std::swap (lhs
, rhs
);
2136 cond
= force_gimple_operand_gsi_1 (&gsi
, unshare_expr (cond
),
2137 is_gimple_condexpr
, NULL_TREE
,
2138 true, GSI_SAME_STMT
);
2139 rhs
= fold_build_cond_expr (type
, unshare_expr (cond
), rhs
, lhs
);
2140 gimple_assign_set_rhs1 (stmt
, ifc_temp_var (type
, rhs
, &gsi
));
2146 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2147 other than the exit and latch of the LOOP. Also resets the
2148 GIMPLE_DEBUG information. */
2151 remove_conditions_and_labels (loop_p loop
)
2153 gimple_stmt_iterator gsi
;
2156 for (i
= 0; i
< loop
->num_nodes
; i
++)
2158 basic_block bb
= ifc_bbs
[i
];
2160 if (bb_with_exit_edge_p (loop
, bb
)
2161 || bb
== loop
->latch
)
2164 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); )
2165 switch (gimple_code (gsi_stmt (gsi
)))
2169 gsi_remove (&gsi
, true);
2173 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2174 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
2176 gimple_debug_bind_reset_value (gsi_stmt (gsi
));
2177 update_stmt (gsi_stmt (gsi
));
2188 /* Combine all the basic blocks from LOOP into one or two super basic
2189 blocks. Replace PHI nodes with conditional modify expressions. */
2192 combine_blocks (struct loop
*loop
)
2194 basic_block bb
, exit_bb
, merge_target_bb
;
2195 unsigned int orig_loop_num_nodes
= loop
->num_nodes
;
2200 predicate_bbs (loop
);
2201 remove_conditions_and_labels (loop
);
2202 insert_gimplified_predicates (loop
);
2203 predicate_all_scalar_phis (loop
);
2205 if (any_pred_load_store
)
2206 predicate_mem_writes (loop
);
2208 /* Merge basic blocks: first remove all the edges in the loop,
2209 except for those from the exit block. */
2211 bool *predicated
= XNEWVEC (bool, orig_loop_num_nodes
);
2212 for (i
= 0; i
< orig_loop_num_nodes
; i
++)
2215 predicated
[i
] = !is_true_predicate (bb_predicate (bb
));
2216 free_bb_predicate (bb
);
2217 if (bb_with_exit_edge_p (loop
, bb
))
2219 gcc_assert (exit_bb
== NULL
);
2223 gcc_assert (exit_bb
!= loop
->latch
);
2225 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2229 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
));)
2231 if (e
->src
== exit_bb
)
2238 if (exit_bb
!= NULL
)
2240 if (exit_bb
!= loop
->header
)
2242 /* Connect this node to loop header. */
2243 make_edge (loop
->header
, exit_bb
, EDGE_FALLTHRU
);
2244 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, loop
->header
);
2247 /* Redirect non-exit edges to loop->latch. */
2248 FOR_EACH_EDGE (e
, ei
, exit_bb
->succs
)
2250 if (!loop_exit_edge_p (loop
, e
))
2251 redirect_edge_and_branch (e
, loop
->latch
);
2253 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, exit_bb
);
2257 /* If the loop does not have an exit, reconnect header and latch. */
2258 make_edge (loop
->header
, loop
->latch
, EDGE_FALLTHRU
);
2259 set_immediate_dominator (CDI_DOMINATORS
, loop
->latch
, loop
->header
);
2262 merge_target_bb
= loop
->header
;
2263 for (i
= 1; i
< orig_loop_num_nodes
; i
++)
2265 gimple_stmt_iterator gsi
;
2266 gimple_stmt_iterator last
;
2270 if (bb
== exit_bb
|| bb
== loop
->latch
)
2273 /* Make stmts member of loop->header and clear range info from all stmts
2274 in BB which is now no longer executed conditional on a predicate we
2275 could have derived it from. */
2276 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2278 gimple
*stmt
= gsi_stmt (gsi
);
2279 gimple_set_bb (stmt
, merge_target_bb
);
2284 FOR_EACH_SSA_TREE_OPERAND (op
, stmt
, i
, SSA_OP_DEF
)
2285 reset_flow_sensitive_info (op
);
2289 /* Update stmt list. */
2290 last
= gsi_last_bb (merge_target_bb
);
2291 gsi_insert_seq_after (&last
, bb_seq (bb
), GSI_NEW_STMT
);
2292 set_bb_seq (bb
, NULL
);
2294 delete_basic_block (bb
);
2297 /* If possible, merge loop header to the block with the exit edge.
2298 This reduces the number of basic blocks to two, to please the
2299 vectorizer that handles only loops with two nodes. */
2301 && exit_bb
!= loop
->header
2302 && can_merge_blocks_p (loop
->header
, exit_bb
))
2303 merge_blocks (loop
->header
, exit_bb
);
2310 /* Version LOOP before if-converting it; the original loop
2311 will be if-converted, the new copy of the loop will not,
2312 and the LOOP_VECTORIZED internal call will be guarding which
2313 loop to execute. The vectorizer pass will fold this
2314 internal call into either true or false. */
2317 version_loop_for_if_conversion (struct loop
*loop
)
2319 basic_block cond_bb
;
2320 tree cond
= make_ssa_name (boolean_type_node
);
2321 struct loop
*new_loop
;
2323 gimple_stmt_iterator gsi
;
2325 g
= gimple_build_call_internal (IFN_LOOP_VECTORIZED
, 2,
2326 build_int_cst (integer_type_node
, loop
->num
),
2328 gimple_call_set_lhs (g
, cond
);
2330 initialize_original_copy_tables ();
2331 new_loop
= loop_version (loop
, cond
, &cond_bb
,
2332 REG_BR_PROB_BASE
, REG_BR_PROB_BASE
,
2333 REG_BR_PROB_BASE
, true);
2334 free_original_copy_tables ();
2335 if (new_loop
== NULL
)
2337 new_loop
->dont_vectorize
= true;
2338 new_loop
->force_vectorize
= false;
2339 gsi
= gsi_last_bb (cond_bb
);
2340 gimple_call_set_arg (g
, 1, build_int_cst (integer_type_node
, new_loop
->num
));
2341 gsi_insert_before (&gsi
, g
, GSI_SAME_STMT
);
2342 update_ssa (TODO_update_ssa
);
2346 /* Performs splitting of critical edges. Skip splitting and return false
2347 if LOOP will not be converted because:
2349 - LOOP is not well formed.
2350 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
2352 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
2355 ifcvt_split_critical_edges (struct loop
*loop
, bool aggressive_if_conv
)
2359 unsigned int num
= loop
->num_nodes
;
2364 auto_vec
<edge
> critical_edges
;
2366 /* Loop is not well formed. */
2367 if (num
<= 2 || loop
->inner
|| !single_exit (loop
))
2370 body
= get_loop_body (loop
);
2371 for (i
= 0; i
< num
; i
++)
2374 if (!aggressive_if_conv
2376 && EDGE_COUNT (bb
->preds
) > MAX_PHI_ARG_NUM
)
2378 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2380 "BB %d has complicated PHI with more than %u args.\n",
2381 bb
->index
, MAX_PHI_ARG_NUM
);
2386 if (bb
== loop
->latch
|| bb_with_exit_edge_p (loop
, bb
))
2389 stmt
= last_stmt (bb
);
2390 /* Skip basic blocks not ending with conditional branch. */
2391 if (!stmt
|| gimple_code (stmt
) != GIMPLE_COND
)
2394 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2395 if (EDGE_CRITICAL_P (e
) && e
->dest
->loop_father
== loop
)
2396 critical_edges
.safe_push (e
);
2400 while (critical_edges
.length () > 0)
2402 e
= critical_edges
.pop ();
2403 /* Don't split if bb can be predicated along non-critical edge. */
2404 if (EDGE_COUNT (e
->dest
->preds
) > 2 || all_preds_critical_p (e
->dest
))
2411 /* Assumes that lhs of DEF_STMT have multiple uses.
2412 Delete one use by (1) creation of copy DEF_STMT with
2413 unique lhs; (2) change original use of lhs in one
2414 use statement with newly created lhs. */
2417 ifcvt_split_def_stmt (gimple
*def_stmt
, gimple
*use_stmt
)
2422 gimple_stmt_iterator gsi
;
2423 use_operand_p use_p
;
2424 imm_use_iterator imm_iter
;
2426 var
= gimple_assign_lhs (def_stmt
);
2427 copy_stmt
= gimple_copy (def_stmt
);
2428 lhs
= make_temp_ssa_name (TREE_TYPE (var
), NULL
, "_ifc_");
2429 gimple_assign_set_lhs (copy_stmt
, lhs
);
2430 SSA_NAME_DEF_STMT (lhs
) = copy_stmt
;
2431 /* Insert copy of DEF_STMT. */
2432 gsi
= gsi_for_stmt (def_stmt
);
2433 gsi_insert_after (&gsi
, copy_stmt
, GSI_SAME_STMT
);
2434 /* Change use of var to lhs in use_stmt. */
2435 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2437 fprintf (dump_file
, "Change use of var ");
2438 print_generic_expr (dump_file
, var
, TDF_SLIM
);
2439 fprintf (dump_file
, " to ");
2440 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
2441 fprintf (dump_file
, "\n");
2443 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, var
)
2445 if (USE_STMT (use_p
) != use_stmt
)
2447 SET_USE (use_p
, lhs
);
2452 /* Traverse bool pattern recursively starting from VAR.
2453 Save its def and use statements to defuse_list if VAR does
2454 not have single use. */
2457 ifcvt_walk_pattern_tree (tree var
, vec
<gimple
*> *defuse_list
,
2461 enum tree_code code
;
2464 if (TREE_CODE (var
) != SSA_NAME
)
2467 def_stmt
= SSA_NAME_DEF_STMT (var
);
2468 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2470 if (!has_single_use (var
))
2472 /* Put def and use stmts into defuse_list. */
2473 defuse_list
->safe_push (def_stmt
);
2474 defuse_list
->safe_push (use_stmt
);
2475 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2477 fprintf (dump_file
, "Multiple lhs uses in stmt\n");
2478 print_gimple_stmt (dump_file
, def_stmt
, 0, TDF_SLIM
);
2481 rhs1
= gimple_assign_rhs1 (def_stmt
);
2482 code
= gimple_assign_rhs_code (def_stmt
);
2486 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2489 if ((TYPE_PRECISION (TREE_TYPE (rhs1
)) != 1
2490 || !TYPE_UNSIGNED (TREE_TYPE (rhs1
)))
2491 && TREE_CODE (TREE_TYPE (rhs1
)) != BOOLEAN_TYPE
)
2493 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2496 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2501 ifcvt_walk_pattern_tree (rhs1
, defuse_list
, def_stmt
);
2502 rhs2
= gimple_assign_rhs2 (def_stmt
);
2503 ifcvt_walk_pattern_tree (rhs2
, defuse_list
, def_stmt
);
2511 /* Returns true if STMT can be a root of bool pattern applied
2515 stmt_is_root_of_bool_pattern (gimple
*stmt
)
2517 enum tree_code code
;
2520 code
= gimple_assign_rhs_code (stmt
);
2521 if (CONVERT_EXPR_CODE_P (code
))
2523 lhs
= gimple_assign_lhs (stmt
);
2524 rhs
= gimple_assign_rhs1 (stmt
);
2525 if (TREE_CODE (TREE_TYPE (rhs
)) != BOOLEAN_TYPE
)
2527 if (TREE_CODE (TREE_TYPE (lhs
)) == BOOLEAN_TYPE
)
2531 else if (code
== COND_EXPR
)
2533 rhs
= gimple_assign_rhs1 (stmt
);
2534 if (TREE_CODE (rhs
) != SSA_NAME
)
2541 /* Traverse all statements in BB which correspond to loop header to
2542 find out all statements which can start bool pattern applied by
2543 vectorizer and convert multiple uses in it to conform pattern
2544 restrictions. Such case can occur if the same predicate is used both
2545 for phi node conversion and load/store mask. */
2548 ifcvt_repair_bool_pattern (basic_block bb
)
2552 gimple_stmt_iterator gsi
;
2553 vec
<gimple
*> defuse_list
= vNULL
;
2554 vec
<gimple
*> pattern_roots
= vNULL
;
2559 /* Collect all root pattern statements. */
2560 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2562 stmt
= gsi_stmt (gsi
);
2563 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
2565 if (!stmt_is_root_of_bool_pattern (stmt
))
2567 pattern_roots
.safe_push (stmt
);
2570 if (pattern_roots
.is_empty ())
2573 /* Split all statements with multiple uses iteratively since splitting
2574 may create new multiple uses. */
2579 FOR_EACH_VEC_ELT (pattern_roots
, ix
, stmt
)
2581 rhs
= gimple_assign_rhs1 (stmt
);
2582 ifcvt_walk_pattern_tree (rhs
, &defuse_list
, stmt
);
2583 while (defuse_list
.length () > 0)
2586 gimple
*def_stmt
, *use_stmt
;
2587 use_stmt
= defuse_list
.pop ();
2588 def_stmt
= defuse_list
.pop ();
2589 ifcvt_split_def_stmt (def_stmt
, use_stmt
);
2594 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2595 fprintf (dump_file
, "Repair bool pattern takes %d iterations. \n",
2599 /* Delete redundant statements produced by predication which prevents
2600 loop vectorization. */
2603 ifcvt_local_dce (basic_block bb
)
2608 gimple_stmt_iterator gsi
;
2609 auto_vec
<gimple
*> worklist
;
2610 enum gimple_code code
;
2611 use_operand_p use_p
;
2612 imm_use_iterator imm_iter
;
2614 worklist
.create (64);
2615 /* Consider all phi as live statements. */
2616 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2618 phi
= gsi_stmt (gsi
);
2619 gimple_set_plf (phi
, GF_PLF_2
, true);
2620 worklist
.safe_push (phi
);
2622 /* Consider load/store statements, CALL and COND as live. */
2623 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2625 stmt
= gsi_stmt (gsi
);
2626 if (gimple_store_p (stmt
)
2627 || gimple_assign_load_p (stmt
)
2628 || is_gimple_debug (stmt
))
2630 gimple_set_plf (stmt
, GF_PLF_2
, true);
2631 worklist
.safe_push (stmt
);
2634 code
= gimple_code (stmt
);
2635 if (code
== GIMPLE_COND
|| code
== GIMPLE_CALL
)
2637 gimple_set_plf (stmt
, GF_PLF_2
, true);
2638 worklist
.safe_push (stmt
);
2641 gimple_set_plf (stmt
, GF_PLF_2
, false);
2643 if (code
== GIMPLE_ASSIGN
)
2645 tree lhs
= gimple_assign_lhs (stmt
);
2646 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, lhs
)
2648 stmt1
= USE_STMT (use_p
);
2649 if (gimple_bb (stmt1
) != bb
)
2651 gimple_set_plf (stmt
, GF_PLF_2
, true);
2652 worklist
.safe_push (stmt
);
2658 /* Propagate liveness through arguments of live stmt. */
2659 while (worklist
.length () > 0)
2662 use_operand_p use_p
;
2665 stmt
= worklist
.pop ();
2666 FOR_EACH_PHI_OR_STMT_USE (use_p
, stmt
, iter
, SSA_OP_USE
)
2668 use
= USE_FROM_PTR (use_p
);
2669 if (TREE_CODE (use
) != SSA_NAME
)
2671 stmt1
= SSA_NAME_DEF_STMT (use
);
2672 if (gimple_bb (stmt1
) != bb
2673 || gimple_plf (stmt1
, GF_PLF_2
))
2675 gimple_set_plf (stmt1
, GF_PLF_2
, true);
2676 worklist
.safe_push (stmt1
);
2679 /* Delete dead statements. */
2680 gsi
= gsi_start_bb (bb
);
2681 while (!gsi_end_p (gsi
))
2683 stmt
= gsi_stmt (gsi
);
2684 if (gimple_plf (stmt
, GF_PLF_2
))
2689 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2691 fprintf (dump_file
, "Delete dead stmt in bb#%d\n", bb
->index
);
2692 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
2694 gsi_remove (&gsi
, true);
2695 release_defs (stmt
);
2699 /* If-convert LOOP when it is legal. For the moment this pass has no
2700 profitability analysis. Returns non-zero todo flags when something
2704 tree_if_conversion (struct loop
*loop
)
2706 unsigned int todo
= 0;
2707 bool aggressive_if_conv
;
2710 any_pred_load_store
= false;
2711 any_complicated_phi
= false;
2713 /* Apply more aggressive if-conversion when loop or its outer loop were
2714 marked with simd pragma. When that's the case, we try to if-convert
2715 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
2716 aggressive_if_conv
= loop
->force_vectorize
;
2717 if (!aggressive_if_conv
)
2719 struct loop
*outer_loop
= loop_outer (loop
);
2720 if (outer_loop
&& outer_loop
->force_vectorize
)
2721 aggressive_if_conv
= true;
2724 if (!ifcvt_split_critical_edges (loop
, aggressive_if_conv
))
2727 if (!if_convertible_loop_p (loop
)
2728 || !dbg_cnt (if_conversion_tree
))
2731 if ((any_pred_load_store
|| any_complicated_phi
)
2732 && ((!flag_tree_loop_vectorize
&& !loop
->force_vectorize
)
2733 || loop
->dont_vectorize
))
2736 if ((any_pred_load_store
|| any_complicated_phi
)
2737 && !version_loop_for_if_conversion (loop
))
2740 /* Now all statements are if-convertible. Combine all the basic
2741 blocks into one huge basic block doing the if-conversion
2743 combine_blocks (loop
);
2745 /* Delete dead predicate computations and repair tree correspondent
2746 to bool pattern to delete multiple uses of predicates. */
2747 ifcvt_local_dce (loop
->header
);
2748 ifcvt_repair_bool_pattern (loop
->header
);
2750 todo
|= TODO_cleanup_cfg
;
2751 mark_virtual_operands_for_renaming (cfun
);
2752 todo
|= TODO_update_ssa_only_virtuals
;
2759 for (i
= 0; i
< loop
->num_nodes
; i
++)
2760 free_bb_predicate (ifc_bbs
[i
]);
2765 free_dominance_info (CDI_POST_DOMINATORS
);
2770 /* Tree if-conversion pass management. */
2774 const pass_data pass_data_if_conversion
=
2776 GIMPLE_PASS
, /* type */
2778 OPTGROUP_NONE
, /* optinfo_flags */
2779 TV_NONE
, /* tv_id */
2780 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2781 0, /* properties_provided */
2782 0, /* properties_destroyed */
2783 0, /* todo_flags_start */
2784 0, /* todo_flags_finish */
2787 class pass_if_conversion
: public gimple_opt_pass
2790 pass_if_conversion (gcc::context
*ctxt
)
2791 : gimple_opt_pass (pass_data_if_conversion
, ctxt
)
2794 /* opt_pass methods: */
2795 virtual bool gate (function
*);
2796 virtual unsigned int execute (function
*);
2798 }; // class pass_if_conversion
2801 pass_if_conversion::gate (function
*fun
)
2803 return (((flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
)
2804 && flag_tree_loop_if_convert
!= 0)
2805 || flag_tree_loop_if_convert
== 1
2806 || flag_tree_loop_if_convert_stores
== 1);
2810 pass_if_conversion::execute (function
*fun
)
2815 if (number_of_loops (fun
) <= 1)
2818 /* If there are infinite loops, during CDI_POST_DOMINATORS computation
2819 we can pick pretty much random bb inside of the infinite loop that
2820 has the fake edge. If we are unlucky enough, this can confuse the
2821 add_to_predicate_list post-dominator check to optimize as if that
2822 bb or some other one is a join block when it actually is not.
2824 connect_infinite_loops_to_exit ();
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
);
2833 remove_fake_exit_edges ();
2838 FOR_EACH_BB_FN (bb
, fun
)
2839 gcc_assert (!bb
->aux
);
2848 make_pass_if_conversion (gcc::context
*ctxt
)
2850 return new pass_if_conversion (ctxt
);