1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2016 Free Software Foundation, Inc.
3 Contributed by Devang Patel <dpatel@apple.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This pass implements a tree level if-conversion of loops. Its
22 initial goal is to help the vectorizer to vectorize loops with
25 A short description of if-conversion:
27 o Decide if a loop is if-convertible or not.
28 o Walk all loop basic blocks in breadth first order (BFS order).
29 o Remove conditional statements (at the end of basic block)
30 and propagate condition into destination basic blocks'
32 o Replace modify expression with conditional modify expression
33 using current basic block's condition.
34 o Merge all basic blocks
35 o Replace phi nodes with conditional modify expr
36 o Merge all basic blocks into header
38 Sample transformation:
43 # i_23 = PHI <0(0), i_18(10)>;
46 if (j_15 > 41) goto <L1>; else goto <L17>;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
67 # i_23 = PHI <0(0), i_18(10)>;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
85 #include "coretypes.h"
91 #include "tree-pass.h"
94 #include "optabs-query.h"
95 #include "gimple-pretty-print.h"
97 #include "fold-const.h"
98 #include "stor-layout.h"
99 #include "gimple-fold.h"
100 #include "gimplify.h"
101 #include "gimple-iterator.h"
102 #include "gimplify-me.h"
103 #include "tree-cfg.h"
104 #include "tree-into-ssa.h"
105 #include "tree-ssa.h"
107 #include "tree-data-ref.h"
108 #include "tree-scalar-evolution.h"
109 #include "tree-ssa-loop-ivopts.h"
110 #include "tree-ssa-address.h"
112 #include "tree-hash-traits.h"
114 #include "builtins.h"
117 /* Only handle PHIs with no more arguments unless we are asked to by
119 #define MAX_PHI_ARG_NUM \
120 ((unsigned) PARAM_VALUE (PARAM_MAX_TREE_IF_CONVERSION_PHI_ARGS))
122 /* Indicate if new load/store that needs to be predicated is introduced
123 during if conversion. */
124 static bool any_pred_load_store;
126 /* Indicate if there are any complicated PHIs that need to be handled in
127 if-conversion. Complicated PHI has more than two arguments and can't
128 be degenerated to two arguments PHI. See more information in comment
129 before phi_convertible_by_degenerating_args. */
130 static bool any_complicated_phi;
132 /* Hash for struct innermost_loop_behavior. It depends on the user to
135 struct innermost_loop_behavior_hash : nofree_ptr_hash <innermost_loop_behavior>
137 static inline hashval_t hash (const value_type &);
138 static inline bool equal (const value_type &,
139 const compare_type &);
143 innermost_loop_behavior_hash::hash (const value_type &e)
147 hash = iterative_hash_expr (e->base_address, 0);
148 hash = iterative_hash_expr (e->offset, hash);
149 hash = iterative_hash_expr (e->init, hash);
150 return iterative_hash_expr (e->step, hash);
154 innermost_loop_behavior_hash::equal (const value_type &e1,
155 const compare_type &e2)
157 if ((e1->base_address && !e2->base_address)
158 || (!e1->base_address && e2->base_address)
159 || (!e1->offset && e2->offset)
160 || (e1->offset && !e2->offset)
161 || (!e1->init && e2->init)
162 || (e1->init && !e2->init)
163 || (!e1->step && e2->step)
164 || (e1->step && !e2->step))
167 if (e1->base_address && e2->base_address
168 && !operand_equal_p (e1->base_address, e2->base_address, 0))
170 if (e1->offset && e2->offset
171 && !operand_equal_p (e1->offset, e2->offset, 0))
173 if (e1->init && e2->init
174 && !operand_equal_p (e1->init, e2->init, 0))
176 if (e1->step && e2->step
177 && !operand_equal_p (e1->step, e2->step, 0))
183 /* List of basic blocks in if-conversion-suitable order. */
184 static basic_block *ifc_bbs;
186 /* Hash table to store <DR's innermost loop behavior, DR> pairs. */
187 static hash_map<innermost_loop_behavior_hash,
188 data_reference_p> *innermost_DR_map;
190 /* Hash table to store <base reference, DR> pairs. */
191 static hash_map<tree_operand_hash, data_reference_p> *baseref_DR_map;
193 /* Structure used to predicate basic blocks. This is attached to the
194 ->aux field of the BBs in the loop to be if-converted. */
195 struct bb_predicate {
197 /* The condition under which this basic block is executed. */
200 /* PREDICATE is gimplified, and the sequence of statements is
201 recorded here, in order to avoid the duplication of computations
202 that occur in previous conditions. See PR44483. */
203 gimple_seq predicate_gimplified_stmts;
206 /* Returns true when the basic block BB has a predicate. */
209 bb_has_predicate (basic_block bb)
211 return bb->aux != NULL;
214 /* Returns the gimplified predicate for basic block BB. */
217 bb_predicate (basic_block bb)
219 return ((struct bb_predicate *) bb->aux)->predicate;
222 /* Sets the gimplified predicate COND for basic block BB. */
225 set_bb_predicate (basic_block bb, tree cond)
227 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
228 && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
229 || is_gimple_condexpr (cond));
230 ((struct bb_predicate *) bb->aux)->predicate = cond;
233 /* Returns the sequence of statements of the gimplification of the
234 predicate for basic block BB. */
236 static inline gimple_seq
237 bb_predicate_gimplified_stmts (basic_block bb)
239 return ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts;
242 /* Sets the sequence of statements STMTS of the gimplification of the
243 predicate for basic block BB. */
246 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
248 ((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts = stmts;
251 /* Adds the sequence of statements STMTS to the sequence of statements
252 of the predicate for basic block BB. */
255 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
258 (&(((struct bb_predicate *) bb->aux)->predicate_gimplified_stmts), stmts);
261 /* Initializes to TRUE the predicate of basic block BB. */
264 init_bb_predicate (basic_block bb)
266 bb->aux = XNEW (struct bb_predicate);
267 set_bb_predicate_gimplified_stmts (bb, NULL);
268 set_bb_predicate (bb, boolean_true_node);
271 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
272 but don't actually free it. */
275 release_bb_predicate (basic_block bb)
277 gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
280 gimple_stmt_iterator i;
282 for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
283 free_stmt_operands (cfun, gsi_stmt (i));
284 set_bb_predicate_gimplified_stmts (bb, NULL);
288 /* Free the predicate of basic block BB. */
291 free_bb_predicate (basic_block bb)
293 if (!bb_has_predicate (bb))
296 release_bb_predicate (bb);
301 /* Reinitialize predicate of BB with the true predicate. */
304 reset_bb_predicate (basic_block bb)
306 if (!bb_has_predicate (bb))
307 init_bb_predicate (bb);
310 release_bb_predicate (bb);
311 set_bb_predicate (bb, boolean_true_node);
315 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
316 the expression EXPR. Inserts the statement created for this
317 computation before GSI and leaves the iterator GSI at the same
321 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
323 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
324 gimple *stmt = gimple_build_assign (new_name, expr);
325 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
329 /* Return true when COND is a false predicate. */
332 is_false_predicate (tree cond)
334 return (cond != NULL_TREE
335 && (cond == boolean_false_node
336 || integer_zerop (cond)));
339 /* Return true when COND is a true predicate. */
342 is_true_predicate (tree cond)
344 return (cond == NULL_TREE
345 || cond == boolean_true_node
346 || integer_onep (cond));
349 /* Returns true when BB has a predicate that is not trivial: true or
353 is_predicated (basic_block bb)
355 return !is_true_predicate (bb_predicate (bb));
358 /* Parses the predicate COND and returns its comparison code and
359 operands OP0 and OP1. */
361 static enum tree_code
362 parse_predicate (tree cond, tree *op0, tree *op1)
366 if (TREE_CODE (cond) == SSA_NAME
367 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
369 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
371 *op0 = gimple_assign_rhs1 (s);
372 *op1 = gimple_assign_rhs2 (s);
373 return gimple_assign_rhs_code (s);
376 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
378 tree op = gimple_assign_rhs1 (s);
379 tree type = TREE_TYPE (op);
380 enum tree_code code = parse_predicate (op, op0, op1);
382 return code == ERROR_MARK ? ERROR_MARK
383 : invert_tree_comparison (code, HONOR_NANS (type));
389 if (COMPARISON_CLASS_P (cond))
391 *op0 = TREE_OPERAND (cond, 0);
392 *op1 = TREE_OPERAND (cond, 1);
393 return TREE_CODE (cond);
399 /* Returns the fold of predicate C1 OR C2 at location LOC. */
402 fold_or_predicates (location_t loc, tree c1, tree c2)
404 tree op1a, op1b, op2a, op2b;
405 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
406 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
408 if (code1 != ERROR_MARK && code2 != ERROR_MARK)
410 tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
416 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
419 /* Returns true if N is either a constant or a SSA_NAME. */
422 constant_or_ssa_name (tree n)
424 switch (TREE_CODE (n))
437 /* Returns either a COND_EXPR or the folded expression if the folded
438 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
439 a constant or a SSA_NAME. */
442 fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
444 tree rhs1, lhs1, cond_expr;
446 /* If COND is comparison r != 0 and r has boolean type, convert COND
447 to SSA_NAME to accept by vect bool pattern. */
448 if (TREE_CODE (cond) == NE_EXPR)
450 tree op0 = TREE_OPERAND (cond, 0);
451 tree op1 = TREE_OPERAND (cond, 1);
452 if (TREE_CODE (op0) == SSA_NAME
453 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
454 && (integer_zerop (op1)))
457 cond_expr = fold_ternary (COND_EXPR, type, cond,
460 if (cond_expr == NULL_TREE)
461 return build3 (COND_EXPR, type, cond, rhs, lhs);
463 STRIP_USELESS_TYPE_CONVERSION (cond_expr);
465 if (constant_or_ssa_name (cond_expr))
468 if (TREE_CODE (cond_expr) == ABS_EXPR)
470 rhs1 = TREE_OPERAND (cond_expr, 1);
471 STRIP_USELESS_TYPE_CONVERSION (rhs1);
472 if (constant_or_ssa_name (rhs1))
473 return build1 (ABS_EXPR, type, rhs1);
476 if (TREE_CODE (cond_expr) == MIN_EXPR
477 || TREE_CODE (cond_expr) == MAX_EXPR)
479 lhs1 = TREE_OPERAND (cond_expr, 0);
480 STRIP_USELESS_TYPE_CONVERSION (lhs1);
481 rhs1 = TREE_OPERAND (cond_expr, 1);
482 STRIP_USELESS_TYPE_CONVERSION (rhs1);
483 if (constant_or_ssa_name (rhs1)
484 && constant_or_ssa_name (lhs1))
485 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
487 return build3 (COND_EXPR, type, cond, rhs, lhs);
490 /* Add condition NC to the predicate list of basic block BB. LOOP is
491 the loop to be if-converted. Use predicate of cd-equivalent block
492 for join bb if it exists: we call basic blocks bb1 and bb2
493 cd-equivalent if they are executed under the same condition. */
496 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
501 if (is_true_predicate (nc))
504 /* If dominance tells us this basic block is always executed,
505 don't record any predicates for it. */
506 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
509 dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
510 /* We use notion of cd equivalence to get simpler predicate for
511 join block, e.g. if join block has 2 predecessors with predicates
512 p1 & p2 and p1 & !p2, we'd like to get p1 for it instead of
513 p1 & p2 | p1 & !p2. */
514 if (dom_bb != loop->header
515 && get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb) == bb)
517 gcc_assert (flow_bb_inside_loop_p (loop, dom_bb));
518 bc = bb_predicate (dom_bb);
519 if (!is_true_predicate (bc))
520 set_bb_predicate (bb, bc);
522 gcc_assert (is_true_predicate (bb_predicate (bb)));
523 if (dump_file && (dump_flags & TDF_DETAILS))
524 fprintf (dump_file, "Use predicate of bb#%d for bb#%d\n",
525 dom_bb->index, bb->index);
529 if (!is_predicated (bb))
533 bc = bb_predicate (bb);
534 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
535 if (is_true_predicate (bc))
537 reset_bb_predicate (bb);
542 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
543 if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
544 tp = &TREE_OPERAND (bc, 0);
547 if (!is_gimple_condexpr (*tp))
550 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
551 add_bb_predicate_gimplified_stmts (bb, stmts);
553 set_bb_predicate (bb, bc);
556 /* Add the condition COND to the previous condition PREV_COND, and add
557 this to the predicate list of the destination of edge E. LOOP is
558 the loop to be if-converted. */
561 add_to_dst_predicate_list (struct loop *loop, edge e,
562 tree prev_cond, tree cond)
564 if (!flow_bb_inside_loop_p (loop, e->dest))
567 if (!is_true_predicate (prev_cond))
568 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
571 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, e->dest))
572 add_to_predicate_list (loop, e->dest, cond);
575 /* Return true if one of the successor edges of BB exits LOOP. */
578 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
583 FOR_EACH_EDGE (e, ei, bb->succs)
584 if (loop_exit_edge_p (loop, e))
590 /* Given PHI which has more than two arguments, this function checks if
591 it's if-convertible by degenerating its arguments. Specifically, if
592 below two conditions are satisfied:
594 1) Number of PHI arguments with different values equals to 2 and one
595 argument has the only occurrence.
596 2) The edge corresponding to the unique argument isn't critical edge.
598 Such PHI can be handled as PHIs have only two arguments. For example,
601 res = PHI <A_1(e1), A_1(e2), A_2(e3)>;
603 can be transformed into:
605 res = (predicate of e3) ? A_2 : A_1;
607 Return TRUE if it is the case, FALSE otherwise. */
610 phi_convertible_by_degenerating_args (gphi *phi)
613 tree arg, t1 = NULL, t2 = NULL;
614 unsigned int i, i1 = 0, i2 = 0, n1 = 0, n2 = 0;
615 unsigned int num_args = gimple_phi_num_args (phi);
617 gcc_assert (num_args > 2);
619 for (i = 0; i < num_args; i++)
621 arg = gimple_phi_arg_def (phi, i);
622 if (t1 == NULL || operand_equal_p (t1, arg, 0))
628 else if (t2 == NULL || operand_equal_p (t2, arg, 0))
638 if (n1 != 1 && n2 != 1)
641 /* Check if the edge corresponding to the unique arg is critical. */
642 e = gimple_phi_arg_edge (phi, (n1 == 1) ? i1 : i2);
643 if (EDGE_COUNT (e->src->succs) > 1)
649 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
650 and it belongs to basic block BB. Note at this point, it is sure
651 that PHI is if-convertible. This function updates global variable
652 ANY_COMPLICATED_PHI if PHI is complicated. */
655 if_convertible_phi_p (struct loop *loop, basic_block bb, gphi *phi)
657 if (dump_file && (dump_flags & TDF_DETAILS))
659 fprintf (dump_file, "-------------------------\n");
660 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
663 if (bb != loop->header
664 && gimple_phi_num_args (phi) > 2
665 && !phi_convertible_by_degenerating_args (phi))
666 any_complicated_phi = true;
671 /* Records the status of a data reference. This struct is attached to
672 each DR->aux field. */
675 bool rw_unconditionally;
676 bool w_unconditionally;
677 bool written_at_least_once;
681 tree base_w_predicate;
684 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
685 #define DR_BASE_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->written_at_least_once)
686 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
687 #define DR_W_UNCONDITIONALLY(DR) (IFC_DR (DR)->w_unconditionally)
689 /* Iterates over DR's and stores refs, DR and base refs, DR pairs in
690 HASH tables. While storing them in HASH table, it checks if the
691 reference is unconditionally read or written and stores that as a flag
692 information. For base reference it checks if it is written atlest once
693 unconditionally and stores it as flag information along with DR.
694 In other words for every data reference A in STMT there exist other
695 accesses to a data reference with the same base with predicates that
696 add up (OR-up) to the true predicate: this ensures that the data
697 reference A is touched (read or written) on every iteration of the
698 if-converted loop. */
700 hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a)
703 data_reference_p *master_dr, *base_master_dr;
704 tree base_ref = DR_BASE_OBJECT (a);
705 innermost_loop_behavior *innermost = &DR_INNERMOST (a);
706 tree ca = bb_predicate (gimple_bb (DR_STMT (a)));
709 master_dr = &innermost_DR_map->get_or_insert (innermost, &exist1);
715 IFC_DR (*master_dr)->w_predicate
716 = fold_or_predicates (UNKNOWN_LOCATION, ca,
717 IFC_DR (*master_dr)->w_predicate);
718 if (is_true_predicate (IFC_DR (*master_dr)->w_predicate))
719 DR_W_UNCONDITIONALLY (*master_dr) = true;
721 IFC_DR (*master_dr)->rw_predicate
722 = fold_or_predicates (UNKNOWN_LOCATION, ca,
723 IFC_DR (*master_dr)->rw_predicate);
724 if (is_true_predicate (IFC_DR (*master_dr)->rw_predicate))
725 DR_RW_UNCONDITIONALLY (*master_dr) = true;
729 base_master_dr = &baseref_DR_map->get_or_insert (base_ref, &exist2);
732 IFC_DR (*base_master_dr)->base_w_predicate
733 = fold_or_predicates (UNKNOWN_LOCATION, ca,
734 IFC_DR (*base_master_dr)->base_w_predicate);
735 if (is_true_predicate (IFC_DR (*base_master_dr)->base_w_predicate))
736 DR_BASE_W_UNCONDITIONALLY (*base_master_dr) = true;
740 /* Return true when the memory references of STMT won't trap in the
741 if-converted code. There are two things that we have to check for:
743 - writes to memory occur to writable memory: if-conversion of
744 memory writes transforms the conditional memory writes into
745 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
746 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
747 be executed at all in the original code, it may be a readonly
748 memory. To check that A is not const-qualified, we check that
749 there exists at least an unconditional write to A in the current
752 - reads or writes to memory are valid memory accesses for every
753 iteration. To check that the memory accesses are correctly formed
754 and that we are allowed to read and write in these locations, we
755 check that the memory accesses to be if-converted occur at every
756 iteration unconditionally.
758 Returns true for the memory reference in STMT, same memory reference
759 is read or written unconditionally atleast once and the base memory
760 reference is written unconditionally once. This is to check reference
761 will not write fault. Also retuns true if the memory reference is
762 unconditionally read once then we are conditionally writing to memory
763 which is defined as read and write and is bound to the definition
766 ifcvt_memrefs_wont_trap (gimple *stmt, vec<data_reference_p> drs)
768 data_reference_p *master_dr, *base_master_dr;
769 data_reference_p a = drs[gimple_uid (stmt) - 1];
771 tree base = DR_BASE_OBJECT (a);
772 innermost_loop_behavior *innermost = &DR_INNERMOST (a);
774 gcc_assert (DR_STMT (a) == stmt);
775 gcc_assert (DR_BASE_ADDRESS (a) || DR_OFFSET (a)
776 || DR_INIT (a) || DR_STEP (a));
778 master_dr = innermost_DR_map->get (innermost);
779 gcc_assert (master_dr != NULL);
781 base_master_dr = baseref_DR_map->get (base);
783 /* If a is unconditionally written to it doesn't trap. */
784 if (DR_W_UNCONDITIONALLY (*master_dr))
787 /* If a is unconditionally accessed then ... */
788 if (DR_RW_UNCONDITIONALLY (*master_dr))
790 /* an unconditional read won't trap. */
794 /* an unconditionaly write won't trap if the base is written
795 to unconditionally. */
797 && DR_BASE_W_UNCONDITIONALLY (*base_master_dr))
798 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
801 /* or the base is know to be not readonly. */
802 tree base_tree = get_base_address (DR_REF (a));
803 if (DECL_P (base_tree)
804 && decl_binds_to_current_def_p (base_tree)
805 && ! TREE_READONLY (base_tree))
806 return PARAM_VALUE (PARAM_ALLOW_STORE_DATA_RACES);
812 /* Return true if STMT could be converted into a masked load or store
813 (conditional load or store based on a mask computed from bb predicate). */
816 ifcvt_can_use_mask_load_store (gimple *stmt)
820 basic_block bb = gimple_bb (stmt);
823 if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
824 || bb->loop_father->dont_vectorize
825 || !gimple_assign_single_p (stmt)
826 || gimple_has_volatile_ops (stmt))
829 /* Check whether this is a load or store. */
830 lhs = gimple_assign_lhs (stmt);
831 if (gimple_store_p (stmt))
833 if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
838 else if (gimple_assign_load_p (stmt))
841 ref = gimple_assign_rhs1 (stmt);
846 if (may_be_nonaddressable_p (ref))
849 /* Mask should be integer mode of the same size as the load/store
851 mode = TYPE_MODE (TREE_TYPE (lhs));
852 if (int_mode_for_mode (mode) == BLKmode
853 || VECTOR_MODE_P (mode))
856 if (can_vec_mask_load_store_p (mode, VOIDmode, is_load))
862 /* Return true when STMT is if-convertible.
864 GIMPLE_ASSIGN statement is not if-convertible if,
867 - LHS is not var decl. */
870 if_convertible_gimple_assign_stmt_p (gimple *stmt,
871 vec<data_reference_p> refs)
873 tree lhs = gimple_assign_lhs (stmt);
875 if (dump_file && (dump_flags & TDF_DETAILS))
877 fprintf (dump_file, "-------------------------\n");
878 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
881 if (!is_gimple_reg_type (TREE_TYPE (lhs)))
884 /* Some of these constrains might be too conservative. */
885 if (stmt_ends_bb_p (stmt)
886 || gimple_has_volatile_ops (stmt)
887 || (TREE_CODE (lhs) == SSA_NAME
888 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
889 || gimple_has_side_effects (stmt))
891 if (dump_file && (dump_flags & TDF_DETAILS))
892 fprintf (dump_file, "stmt not suitable for ifcvt\n");
896 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
897 in between if_convertible_loop_p and combine_blocks
898 we can perform loop versioning. */
899 gimple_set_plf (stmt, GF_PLF_2, false);
901 if ((! gimple_vuse (stmt)
902 || gimple_could_trap_p_1 (stmt, false, false)
903 || ! ifcvt_memrefs_wont_trap (stmt, refs))
904 && gimple_could_trap_p (stmt))
906 if (ifcvt_can_use_mask_load_store (stmt))
908 gimple_set_plf (stmt, GF_PLF_2, true);
909 any_pred_load_store = true;
912 if (dump_file && (dump_flags & TDF_DETAILS))
913 fprintf (dump_file, "tree could trap...\n");
917 /* When if-converting stores force versioning, likewise if we
918 ended up generating store data races. */
919 if (gimple_vdef (stmt))
920 any_pred_load_store = true;
925 /* Return true when STMT is if-convertible.
927 A statement is if-convertible if:
928 - it is an if-convertible GIMPLE_ASSIGN,
929 - it is a GIMPLE_LABEL or a GIMPLE_COND,
930 - it is builtins call. */
933 if_convertible_stmt_p (gimple *stmt, vec<data_reference_p> refs)
935 switch (gimple_code (stmt))
943 return if_convertible_gimple_assign_stmt_p (stmt, refs);
947 tree fndecl = gimple_call_fndecl (stmt);
950 int flags = gimple_call_flags (stmt);
951 if ((flags & ECF_CONST)
952 && !(flags & ECF_LOOPING_CONST_OR_PURE)
953 /* We can only vectorize some builtins at the moment,
954 so restrict if-conversion to those. */
955 && DECL_BUILT_IN (fndecl))
962 /* Don't know what to do with 'em so don't do anything. */
963 if (dump_file && (dump_flags & TDF_DETAILS))
965 fprintf (dump_file, "don't know what to do\n");
966 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
975 /* Assumes that BB has more than 1 predecessors.
976 Returns false if at least one successor is not on critical edge
977 and true otherwise. */
980 all_preds_critical_p (basic_block bb)
985 FOR_EACH_EDGE (e, ei, bb->preds)
986 if (EDGE_COUNT (e->src->succs) == 1)
991 /* Returns true if at least one successor in on critical edge. */
993 has_pred_critical_p (basic_block bb)
998 FOR_EACH_EDGE (e, ei, bb->preds)
999 if (EDGE_COUNT (e->src->succs) > 1)
1004 /* Return true when BB is if-convertible. This routine does not check
1005 basic block's statements and phis.
1007 A basic block is not if-convertible if:
1008 - it is non-empty and it is after the exit block (in BFS order),
1009 - it is after the exit block but before the latch,
1010 - its edges are not normal.
1012 EXIT_BB is the basic block containing the exit of the LOOP. BB is
1016 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
1021 if (dump_file && (dump_flags & TDF_DETAILS))
1022 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
1024 if (EDGE_COUNT (bb->succs) > 2)
1029 if (bb != loop->latch)
1031 if (dump_file && (dump_flags & TDF_DETAILS))
1032 fprintf (dump_file, "basic block after exit bb but before latch\n");
1035 else if (!empty_block_p (bb))
1037 if (dump_file && (dump_flags & TDF_DETAILS))
1038 fprintf (dump_file, "non empty basic block after exit bb\n");
1041 else if (bb == loop->latch
1043 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
1045 if (dump_file && (dump_flags & TDF_DETAILS))
1046 fprintf (dump_file, "latch is not dominated by exit_block\n");
1051 /* Be less adventurous and handle only normal edges. */
1052 FOR_EACH_EDGE (e, ei, bb->succs)
1053 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
1055 if (dump_file && (dump_flags & TDF_DETAILS))
1056 fprintf (dump_file, "Difficult to handle edges\n");
1063 /* Return true when all predecessor blocks of BB are visited. The
1064 VISITED bitmap keeps track of the visited blocks. */
1067 pred_blocks_visited_p (basic_block bb, bitmap *visited)
1071 FOR_EACH_EDGE (e, ei, bb->preds)
1072 if (!bitmap_bit_p (*visited, e->src->index))
1078 /* Get body of a LOOP in suitable order for if-conversion. It is
1079 caller's responsibility to deallocate basic block list.
1080 If-conversion suitable order is, breadth first sort (BFS) order
1081 with an additional constraint: select a block only if all its
1082 predecessors are already selected. */
1084 static basic_block *
1085 get_loop_body_in_if_conv_order (const struct loop *loop)
1087 basic_block *blocks, *blocks_in_bfs_order;
1090 unsigned int index = 0;
1091 unsigned int visited_count = 0;
1093 gcc_assert (loop->num_nodes);
1094 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1096 blocks = XCNEWVEC (basic_block, loop->num_nodes);
1097 visited = BITMAP_ALLOC (NULL);
1099 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1102 while (index < loop->num_nodes)
1104 bb = blocks_in_bfs_order [index];
1106 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1108 free (blocks_in_bfs_order);
1109 BITMAP_FREE (visited);
1114 if (!bitmap_bit_p (visited, bb->index))
1116 if (pred_blocks_visited_p (bb, &visited)
1117 || bb == loop->header)
1119 /* This block is now visited. */
1120 bitmap_set_bit (visited, bb->index);
1121 blocks[visited_count++] = bb;
1127 if (index == loop->num_nodes
1128 && visited_count != loop->num_nodes)
1132 free (blocks_in_bfs_order);
1133 BITMAP_FREE (visited);
1137 /* Returns true when the analysis of the predicates for all the basic
1138 blocks in LOOP succeeded.
1140 predicate_bbs first allocates the predicates of the basic blocks.
1141 These fields are then initialized with the tree expressions
1142 representing the predicates under which a basic block is executed
1143 in the LOOP. As the loop->header is executed at each iteration, it
1144 has the "true" predicate. Other statements executed under a
1145 condition are predicated with that condition, for example
1152 S1 will be predicated with "x", and
1153 S2 will be predicated with "!x". */
1156 predicate_bbs (loop_p loop)
1160 for (i = 0; i < loop->num_nodes; i++)
1161 init_bb_predicate (ifc_bbs[i]);
1163 for (i = 0; i < loop->num_nodes; i++)
1165 basic_block bb = ifc_bbs[i];
1169 /* The loop latch and loop exit block are always executed and
1170 have no extra conditions to be processed: skip them. */
1171 if (bb == loop->latch
1172 || bb_with_exit_edge_p (loop, bb))
1174 reset_bb_predicate (bb);
1178 cond = bb_predicate (bb);
1179 stmt = last_stmt (bb);
1180 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1183 edge true_edge, false_edge;
1184 location_t loc = gimple_location (stmt);
1185 tree c = build2_loc (loc, gimple_cond_code (stmt),
1187 gimple_cond_lhs (stmt),
1188 gimple_cond_rhs (stmt));
1190 /* Add new condition into destination's predicate list. */
1191 extract_true_false_edges_from_block (gimple_bb (stmt),
1192 &true_edge, &false_edge);
1194 /* If C is true, then TRUE_EDGE is taken. */
1195 add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1198 /* If C is false, then FALSE_EDGE is taken. */
1199 c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1201 add_to_dst_predicate_list (loop, false_edge,
1202 unshare_expr (cond), c2);
1207 /* If current bb has only one successor, then consider it as an
1208 unconditional goto. */
1209 if (single_succ_p (bb))
1211 basic_block bb_n = single_succ (bb);
1213 /* The successor bb inherits the predicate of its
1214 predecessor. If there is no predicate in the predecessor
1215 bb, then consider the successor bb as always executed. */
1216 if (cond == NULL_TREE)
1217 cond = boolean_true_node;
1219 add_to_predicate_list (loop, bb_n, cond);
1223 /* The loop header is always executed. */
1224 reset_bb_predicate (loop->header);
1225 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1226 && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1229 /* Return true when LOOP is if-convertible. This is a helper function
1230 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1231 in if_convertible_loop_p. */
1234 if_convertible_loop_p_1 (struct loop *loop, vec<data_reference_p> *refs)
1237 basic_block exit_bb = NULL;
1239 if (find_data_references_in_loop (loop, refs) == chrec_dont_know)
1242 calculate_dominance_info (CDI_DOMINATORS);
1243 calculate_dominance_info (CDI_POST_DOMINATORS);
1245 /* Allow statements that can be handled during if-conversion. */
1246 ifc_bbs = get_loop_body_in_if_conv_order (loop);
1249 if (dump_file && (dump_flags & TDF_DETAILS))
1250 fprintf (dump_file, "Irreducible loop\n");
1254 for (i = 0; i < loop->num_nodes; i++)
1256 basic_block bb = ifc_bbs[i];
1258 if (!if_convertible_bb_p (loop, bb, exit_bb))
1261 if (bb_with_exit_edge_p (loop, bb))
1265 for (i = 0; i < loop->num_nodes; i++)
1267 basic_block bb = ifc_bbs[i];
1268 gimple_stmt_iterator gsi;
1270 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1271 switch (gimple_code (gsi_stmt (gsi)))
1278 gimple_set_uid (gsi_stmt (gsi), 0);
1285 data_reference_p dr;
1288 = new hash_map<innermost_loop_behavior_hash, data_reference_p>;
1289 baseref_DR_map = new hash_map<tree_operand_hash, data_reference_p>;
1291 predicate_bbs (loop);
1293 for (i = 0; refs->iterate (i, &dr); i++)
1295 tree ref = DR_REF (dr);
1297 dr->aux = XNEW (struct ifc_dr);
1298 DR_BASE_W_UNCONDITIONALLY (dr) = false;
1299 DR_RW_UNCONDITIONALLY (dr) = false;
1300 DR_W_UNCONDITIONALLY (dr) = false;
1301 IFC_DR (dr)->rw_predicate = boolean_false_node;
1302 IFC_DR (dr)->w_predicate = boolean_false_node;
1303 IFC_DR (dr)->base_w_predicate = boolean_false_node;
1304 if (gimple_uid (DR_STMT (dr)) == 0)
1305 gimple_set_uid (DR_STMT (dr), i + 1);
1307 /* If DR doesn't have innermost loop behavior or it's a compound
1308 memory reference, we synthesize its innermost loop behavior
1310 if (TREE_CODE (ref) == COMPONENT_REF
1311 || TREE_CODE (ref) == IMAGPART_EXPR
1312 || TREE_CODE (ref) == REALPART_EXPR
1313 || !(DR_BASE_ADDRESS (dr) || DR_OFFSET (dr)
1314 || DR_INIT (dr) || DR_STEP (dr)))
1316 while (TREE_CODE (ref) == COMPONENT_REF
1317 || TREE_CODE (ref) == IMAGPART_EXPR
1318 || TREE_CODE (ref) == REALPART_EXPR)
1319 ref = TREE_OPERAND (ref, 0);
1321 DR_BASE_ADDRESS (dr) = ref;
1322 DR_OFFSET (dr) = NULL;
1323 DR_INIT (dr) = NULL;
1324 DR_STEP (dr) = NULL;
1325 DR_ALIGNED_TO (dr) = NULL;
1327 hash_memrefs_baserefs_and_store_DRs_read_written_info (dr);
1330 for (i = 0; i < loop->num_nodes; i++)
1332 basic_block bb = ifc_bbs[i];
1333 gimple_stmt_iterator itr;
1335 /* Check the if-convertibility of statements in predicated BBs. */
1336 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1337 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1338 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
1342 for (i = 0; i < loop->num_nodes; i++)
1343 free_bb_predicate (ifc_bbs[i]);
1345 /* Checking PHIs needs to be done after stmts, as the fact whether there
1346 are any masked loads or stores affects the tests. */
1347 for (i = 0; i < loop->num_nodes; i++)
1349 basic_block bb = ifc_bbs[i];
1352 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1353 if (!if_convertible_phi_p (loop, bb, itr.phi ()))
1358 fprintf (dump_file, "Applying if-conversion\n");
1363 /* Return true when LOOP is if-convertible.
1364 LOOP is if-convertible if:
1366 - it has two or more basic blocks,
1367 - it has only one exit,
1368 - loop header is not the exit edge,
1369 - if its basic blocks and phi nodes are if convertible. */
1372 if_convertible_loop_p (struct loop *loop)
1377 vec<data_reference_p> refs;
1379 /* Handle only innermost loop. */
1380 if (!loop || loop->inner)
1382 if (dump_file && (dump_flags & TDF_DETAILS))
1383 fprintf (dump_file, "not innermost loop\n");
1387 /* If only one block, no need for if-conversion. */
1388 if (loop->num_nodes <= 2)
1390 if (dump_file && (dump_flags & TDF_DETAILS))
1391 fprintf (dump_file, "less than 2 basic blocks\n");
1395 /* More than one loop exit is too much to handle. */
1396 if (!single_exit (loop))
1398 if (dump_file && (dump_flags & TDF_DETAILS))
1399 fprintf (dump_file, "multiple exits\n");
1403 /* If one of the loop header's edge is an exit edge then do not
1404 apply if-conversion. */
1405 FOR_EACH_EDGE (e, ei, loop->header->succs)
1406 if (loop_exit_edge_p (loop, e))
1410 res = if_convertible_loop_p_1 (loop, &refs);
1412 data_reference_p dr;
1414 for (i = 0; refs.iterate (i, &dr); i++)
1417 free_data_refs (refs);
1419 delete innermost_DR_map;
1420 innermost_DR_map = NULL;
1422 delete baseref_DR_map;
1423 baseref_DR_map = NULL;
1428 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1429 which is in predicated basic block.
1430 In fact, the following PHI pattern is searching:
1432 reduc_1 = PHI <..., reduc_2>
1436 reduc_2 = PHI <reduc_1, reduc_3>
1438 ARG_0 and ARG_1 are correspondent PHI arguments.
1439 REDUC, OP0 and OP1 contain reduction stmt and its operands.
1440 EXTENDED is true if PHI has > 2 arguments. */
1443 is_cond_scalar_reduction (gimple *phi, gimple **reduc, tree arg_0, tree arg_1,
1444 tree *op0, tree *op1, bool extended)
1446 tree lhs, r_op1, r_op2;
1448 gimple *header_phi = NULL;
1449 enum tree_code reduction_op;
1450 basic_block bb = gimple_bb (phi);
1451 struct loop *loop = bb->loop_father;
1452 edge latch_e = loop_latch_edge (loop);
1453 imm_use_iterator imm_iter;
1454 use_operand_p use_p;
1457 bool result = false;
1458 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1461 if (!extended && gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1464 header_phi = SSA_NAME_DEF_STMT (arg_0);
1465 stmt = SSA_NAME_DEF_STMT (arg_1);
1467 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1470 header_phi = SSA_NAME_DEF_STMT (arg_1);
1471 stmt = SSA_NAME_DEF_STMT (arg_0);
1475 if (gimple_bb (header_phi) != loop->header)
1478 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
1481 if (gimple_code (stmt) != GIMPLE_ASSIGN
1482 || gimple_has_volatile_ops (stmt))
1485 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1488 if (!is_predicated (gimple_bb (stmt)))
1491 /* Check that stmt-block is predecessor of phi-block. */
1492 FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1501 if (!has_single_use (lhs))
1504 reduction_op = gimple_assign_rhs_code (stmt);
1505 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
1507 r_op1 = gimple_assign_rhs1 (stmt);
1508 r_op2 = gimple_assign_rhs2 (stmt);
1510 /* Make R_OP1 to hold reduction variable. */
1511 if (r_op2 == PHI_RESULT (header_phi)
1512 && reduction_op == PLUS_EXPR)
1513 std::swap (r_op1, r_op2);
1514 else if (r_op1 != PHI_RESULT (header_phi))
1517 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1518 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1520 gimple *use_stmt = USE_STMT (use_p);
1521 if (is_gimple_debug (use_stmt))
1523 if (use_stmt == stmt)
1525 if (gimple_code (use_stmt) != GIMPLE_PHI)
1529 *op0 = r_op1; *op1 = r_op2;
1534 /* Converts conditional scalar reduction into unconditional form, e.g.
1536 if (_5 != 0) goto bb_5 else goto bb_6
1542 # res_2 = PHI <res_13(4), res_6(5)>
1545 will be converted into sequence
1546 _ifc__1 = _5 != 0 ? 1 : 0;
1547 res_2 = res_13 + _ifc__1;
1548 Argument SWAP tells that arguments of conditional expression should be
1550 Returns rhs of resulting PHI assignment. */
1553 convert_scalar_cond_reduction (gimple *reduc, gimple_stmt_iterator *gsi,
1554 tree cond, tree op0, tree op1, bool swap)
1556 gimple_stmt_iterator stmt_it;
1559 tree rhs1 = gimple_assign_rhs1 (reduc);
1560 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
1562 tree zero = build_zero_cst (TREE_TYPE (rhs1));
1564 if (dump_file && (dump_flags & TDF_DETAILS))
1566 fprintf (dump_file, "Found cond scalar reduction.\n");
1567 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
1570 /* Build cond expression using COND and constant operand
1571 of reduction rhs. */
1572 c = fold_build_cond_expr (TREE_TYPE (rhs1),
1573 unshare_expr (cond),
1577 /* Create assignment stmt and insert it at GSI. */
1578 new_assign = gimple_build_assign (tmp, c);
1579 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
1580 /* Build rhs for unconditional increment/decrement. */
1581 rhs = fold_build2 (gimple_assign_rhs_code (reduc),
1582 TREE_TYPE (rhs1), op0, tmp);
1584 /* Delete original reduction stmt. */
1585 stmt_it = gsi_for_stmt (reduc);
1586 gsi_remove (&stmt_it, true);
1587 release_defs (reduc);
1591 /* Produce condition for all occurrences of ARG in PHI node. */
1594 gen_phi_arg_condition (gphi *phi, vec<int> *occur,
1595 gimple_stmt_iterator *gsi)
1599 tree cond = NULL_TREE;
1603 len = occur->length ();
1604 gcc_assert (len > 0);
1605 for (i = 0; i < len; i++)
1607 e = gimple_phi_arg_edge (phi, (*occur)[i]);
1608 c = bb_predicate (e->src);
1609 if (is_true_predicate (c))
1611 c = force_gimple_operand_gsi_1 (gsi, unshare_expr (c),
1612 is_gimple_condexpr, NULL_TREE,
1613 true, GSI_SAME_STMT);
1614 if (cond != NULL_TREE)
1616 /* Must build OR expression. */
1617 cond = fold_or_predicates (EXPR_LOCATION (c), c, cond);
1618 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1619 is_gimple_condexpr, NULL_TREE,
1620 true, GSI_SAME_STMT);
1625 gcc_assert (cond != NULL_TREE);
1629 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1630 This routine can handle PHI nodes with more than two arguments.
1633 S1: A = PHI <x1(1), x2(5)>
1635 S2: A = cond ? x1 : x2;
1637 The generated code is inserted at GSI that points to the top of
1638 basic block's statement list.
1639 If PHI node has more than two arguments a chain of conditional
1640 expression is produced. */
1644 predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
1646 gimple *new_stmt = NULL, *reduc;
1647 tree rhs, res, arg0, arg1, op0, op1, scev;
1649 unsigned int index0;
1650 unsigned int max, args_len;
1655 res = gimple_phi_result (phi);
1656 if (virtual_operand_p (res))
1659 if ((rhs = degenerate_phi_result (phi))
1660 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
1662 && !chrec_contains_undetermined (scev)
1664 && (rhs = gimple_phi_arg_def (phi, 0))))
1666 if (dump_file && (dump_flags & TDF_DETAILS))
1668 fprintf (dump_file, "Degenerate phi!\n");
1669 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
1671 new_stmt = gimple_build_assign (res, rhs);
1672 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1673 update_stmt (new_stmt);
1677 bb = gimple_bb (phi);
1678 if (EDGE_COUNT (bb->preds) == 2)
1680 /* Predicate ordinary PHI node with 2 arguments. */
1681 edge first_edge, second_edge;
1682 basic_block true_bb;
1683 first_edge = EDGE_PRED (bb, 0);
1684 second_edge = EDGE_PRED (bb, 1);
1685 cond = bb_predicate (first_edge->src);
1686 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1687 std::swap (first_edge, second_edge);
1688 if (EDGE_COUNT (first_edge->src->succs) > 1)
1690 cond = bb_predicate (second_edge->src);
1691 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1692 cond = TREE_OPERAND (cond, 0);
1694 first_edge = second_edge;
1697 cond = bb_predicate (first_edge->src);
1698 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1699 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1700 is_gimple_condexpr, NULL_TREE,
1701 true, GSI_SAME_STMT);
1702 true_bb = first_edge->src;
1703 if (EDGE_PRED (bb, 1)->src == true_bb)
1705 arg0 = gimple_phi_arg_def (phi, 1);
1706 arg1 = gimple_phi_arg_def (phi, 0);
1710 arg0 = gimple_phi_arg_def (phi, 0);
1711 arg1 = gimple_phi_arg_def (phi, 1);
1713 if (is_cond_scalar_reduction (phi, &reduc, arg0, arg1,
1715 /* Convert reduction stmt into vectorizable form. */
1716 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1717 true_bb != gimple_bb (reduc));
1719 /* Build new RHS using selected condition and arguments. */
1720 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1722 new_stmt = gimple_build_assign (res, rhs);
1723 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1724 update_stmt (new_stmt);
1726 if (dump_file && (dump_flags & TDF_DETAILS))
1728 fprintf (dump_file, "new phi replacement stmt\n");
1729 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1734 /* Create hashmap for PHI node which contain vector of argument indexes
1735 having the same value. */
1737 hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
1738 unsigned int num_args = gimple_phi_num_args (phi);
1740 /* Vector of different PHI argument values. */
1741 auto_vec<tree> args (num_args);
1743 /* Compute phi_arg_map. */
1744 for (i = 0; i < num_args; i++)
1748 arg = gimple_phi_arg_def (phi, i);
1749 if (!phi_arg_map.get (arg))
1750 args.quick_push (arg);
1751 phi_arg_map.get_or_insert (arg).safe_push (i);
1754 /* Determine element with max number of occurrences. */
1757 args_len = args.length ();
1758 for (i = 0; i < args_len; i++)
1761 if ((len = phi_arg_map.get (args[i])->length ()) > max)
1768 /* Put element with max number of occurences to the end of ARGS. */
1769 if (max_ind != -1 && max_ind +1 != (int) args_len)
1770 std::swap (args[args_len - 1], args[max_ind]);
1772 /* Handle one special case when number of arguments with different values
1773 is equal 2 and one argument has the only occurrence. Such PHI can be
1774 handled as if would have only 2 arguments. */
1775 if (args_len == 2 && phi_arg_map.get (args[0])->length () == 1)
1778 indexes = phi_arg_map.get (args[0]);
1779 index0 = (*indexes)[0];
1782 e = gimple_phi_arg_edge (phi, index0);
1783 cond = bb_predicate (e->src);
1784 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1787 cond = TREE_OPERAND (cond, 0);
1789 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1790 cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (cond),
1791 is_gimple_condexpr, NULL_TREE,
1792 true, GSI_SAME_STMT);
1793 if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1,
1795 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1799 /* Convert reduction stmt into vectorizable form. */
1800 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1802 new_stmt = gimple_build_assign (res, rhs);
1803 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1804 update_stmt (new_stmt);
1810 tree type = TREE_TYPE (gimple_phi_result (phi));
1813 for (i = 0; i < args_len; i++)
1816 indexes = phi_arg_map.get (args[i]);
1817 if (i != args_len - 1)
1818 lhs = make_temp_ssa_name (type, NULL, "_ifc_");
1821 cond = gen_phi_arg_condition (phi, indexes, gsi);
1822 rhs = fold_build_cond_expr (type, unshare_expr (cond),
1824 new_stmt = gimple_build_assign (lhs, rhs);
1825 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1826 update_stmt (new_stmt);
1831 if (dump_file && (dump_flags & TDF_DETAILS))
1833 fprintf (dump_file, "new extended phi replacement stmt\n");
1834 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1838 /* Replaces in LOOP all the scalar phi nodes other than those in the
1839 LOOP->header block with conditional modify expressions. */
1842 predicate_all_scalar_phis (struct loop *loop)
1845 unsigned int orig_loop_num_nodes = loop->num_nodes;
1848 for (i = 1; i < orig_loop_num_nodes; i++)
1851 gimple_stmt_iterator gsi;
1852 gphi_iterator phi_gsi;
1855 if (bb == loop->header)
1858 phi_gsi = gsi_start_phis (bb);
1859 if (gsi_end_p (phi_gsi))
1862 gsi = gsi_after_labels (bb);
1863 while (!gsi_end_p (phi_gsi))
1865 phi = phi_gsi.phi ();
1866 predicate_scalar_phi (phi, &gsi);
1867 release_phi_node (phi);
1868 gsi_next (&phi_gsi);
1871 set_phi_nodes (bb, NULL);
1875 /* Insert in each basic block of LOOP the statements produced by the
1876 gimplification of the predicates. */
1879 insert_gimplified_predicates (loop_p loop)
1883 for (i = 0; i < loop->num_nodes; i++)
1885 basic_block bb = ifc_bbs[i];
1887 if (!is_predicated (bb))
1888 gcc_assert (bb_predicate_gimplified_stmts (bb) == NULL);
1889 if (!is_predicated (bb))
1891 /* Do not insert statements for a basic block that is not
1892 predicated. Also make sure that the predicate of the
1893 basic block is set to true. */
1894 reset_bb_predicate (bb);
1898 stmts = bb_predicate_gimplified_stmts (bb);
1901 if (any_pred_load_store)
1903 /* Insert the predicate of the BB just after the label,
1904 as the if-conversion of memory writes will use this
1906 gimple_stmt_iterator gsi = gsi_after_labels (bb);
1907 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1911 /* Insert the predicate of the BB at the end of the BB
1912 as this would reduce the register pressure: the only
1913 use of this predicate will be in successor BBs. */
1914 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1917 || stmt_ends_bb_p (gsi_stmt (gsi)))
1918 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1920 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
1923 /* Once the sequence is code generated, set it to NULL. */
1924 set_bb_predicate_gimplified_stmts (bb, NULL);
1929 /* Helper function for predicate_mem_writes. Returns index of existent
1930 mask if it was created for given SIZE and -1 otherwise. */
1933 mask_exists (int size, vec<int> vec)
1937 FOR_EACH_VEC_ELT (vec, ix, v)
1943 /* Predicate each write to memory in LOOP.
1945 This function transforms control flow constructs containing memory
1948 | for (i = 0; i < N; i++)
1952 into the following form that does not contain control flow:
1954 | for (i = 0; i < N; i++)
1955 | A[i] = cond ? expr : A[i];
1957 The original CFG looks like this:
1964 | if (i < N) goto bb_5 else goto bb_2
1968 | cond = some_computation;
1969 | if (cond) goto bb_3 else goto bb_4
1981 insert_gimplified_predicates inserts the computation of the COND
1982 expression at the beginning of the destination basic block:
1989 | if (i < N) goto bb_5 else goto bb_2
1993 | cond = some_computation;
1994 | if (cond) goto bb_3 else goto bb_4
1998 | cond = some_computation;
2007 predicate_mem_writes is then predicating the memory write as follows:
2014 | if (i < N) goto bb_5 else goto bb_2
2018 | if (cond) goto bb_3 else goto bb_4
2022 | cond = some_computation;
2023 | A[i] = cond ? expr : A[i];
2031 and finally combine_blocks removes the basic block boundaries making
2032 the loop vectorizable:
2036 | if (i < N) goto bb_5 else goto bb_1
2040 | cond = some_computation;
2041 | A[i] = cond ? expr : A[i];
2042 | if (i < N) goto bb_5 else goto bb_4
2051 predicate_mem_writes (loop_p loop)
2053 unsigned int i, orig_loop_num_nodes = loop->num_nodes;
2054 auto_vec<int, 1> vect_sizes;
2055 auto_vec<tree, 1> vect_masks;
2057 for (i = 1; i < orig_loop_num_nodes; i++)
2059 gimple_stmt_iterator gsi;
2060 basic_block bb = ifc_bbs[i];
2061 tree cond = bb_predicate (bb);
2066 if (is_true_predicate (cond) || is_false_predicate (cond))
2070 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
2073 cond = TREE_OPERAND (cond, 0);
2076 vect_sizes.truncate (0);
2077 vect_masks.truncate (0);
2079 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2080 if (!gimple_assign_single_p (stmt = gsi_stmt (gsi)))
2082 else if (gimple_plf (stmt, GF_PLF_2))
2084 tree lhs = gimple_assign_lhs (stmt);
2085 tree rhs = gimple_assign_rhs1 (stmt);
2086 tree ref, addr, ptr, mask;
2088 gimple_seq stmts = NULL;
2089 int bitsize = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs)));
2090 ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
2091 mark_addressable (ref);
2092 addr = force_gimple_operand_gsi (&gsi, build_fold_addr_expr (ref),
2093 true, NULL_TREE, true,
2095 if (!vect_sizes.is_empty ()
2096 && (index = mask_exists (bitsize, vect_sizes)) != -1)
2097 /* Use created mask. */
2098 mask = vect_masks[index];
2101 if (COMPARISON_CLASS_P (cond))
2102 mask = gimple_build (&stmts, TREE_CODE (cond),
2104 TREE_OPERAND (cond, 0),
2105 TREE_OPERAND (cond, 1));
2108 gcc_assert (TREE_CODE (cond) == SSA_NAME);
2115 = constant_boolean_node (true, TREE_TYPE (mask));
2116 mask = gimple_build (&stmts, BIT_XOR_EXPR,
2117 TREE_TYPE (mask), mask, true_val);
2119 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
2121 mask = ifc_temp_var (TREE_TYPE (mask), mask, &gsi);
2122 /* Save mask and its size for further use. */
2123 vect_sizes.safe_push (bitsize);
2124 vect_masks.safe_push (mask);
2126 ptr = build_int_cst (reference_alias_ptr_type (ref),
2127 get_object_alignment (ref));
2128 /* Copy points-to info if possible. */
2129 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
2130 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
2132 if (TREE_CODE (lhs) == SSA_NAME)
2135 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
2137 gimple_call_set_lhs (new_stmt, lhs);
2141 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
2143 gsi_replace (&gsi, new_stmt, true);
2145 else if (gimple_vdef (stmt))
2147 tree lhs = gimple_assign_lhs (stmt);
2148 tree rhs = gimple_assign_rhs1 (stmt);
2149 tree type = TREE_TYPE (lhs);
2151 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
2152 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
2154 std::swap (lhs, rhs);
2155 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
2156 is_gimple_condexpr, NULL_TREE,
2157 true, GSI_SAME_STMT);
2158 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
2159 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
2165 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
2166 other than the exit and latch of the LOOP. Also resets the
2167 GIMPLE_DEBUG information. */
2170 remove_conditions_and_labels (loop_p loop)
2172 gimple_stmt_iterator gsi;
2175 for (i = 0; i < loop->num_nodes; i++)
2177 basic_block bb = ifc_bbs[i];
2179 if (bb_with_exit_edge_p (loop, bb)
2180 || bb == loop->latch)
2183 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2184 switch (gimple_code (gsi_stmt (gsi)))
2188 gsi_remove (&gsi, true);
2192 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
2193 if (gimple_debug_bind_p (gsi_stmt (gsi)))
2195 gimple_debug_bind_reset_value (gsi_stmt (gsi));
2196 update_stmt (gsi_stmt (gsi));
2207 /* Combine all the basic blocks from LOOP into one or two super basic
2208 blocks. Replace PHI nodes with conditional modify expressions. */
2211 combine_blocks (struct loop *loop)
2213 basic_block bb, exit_bb, merge_target_bb;
2214 unsigned int orig_loop_num_nodes = loop->num_nodes;
2219 predicate_bbs (loop);
2220 remove_conditions_and_labels (loop);
2221 insert_gimplified_predicates (loop);
2222 predicate_all_scalar_phis (loop);
2224 if (any_pred_load_store)
2225 predicate_mem_writes (loop);
2227 /* Merge basic blocks: first remove all the edges in the loop,
2228 except for those from the exit block. */
2230 bool *predicated = XNEWVEC (bool, orig_loop_num_nodes);
2231 for (i = 0; i < orig_loop_num_nodes; i++)
2234 predicated[i] = !is_true_predicate (bb_predicate (bb));
2235 free_bb_predicate (bb);
2236 if (bb_with_exit_edge_p (loop, bb))
2238 gcc_assert (exit_bb == NULL);
2242 gcc_assert (exit_bb != loop->latch);
2244 for (i = 1; i < orig_loop_num_nodes; i++)
2248 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
2250 if (e->src == exit_bb)
2257 if (exit_bb != NULL)
2259 if (exit_bb != loop->header)
2261 /* Connect this node to loop header. */
2262 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
2263 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
2266 /* Redirect non-exit edges to loop->latch. */
2267 FOR_EACH_EDGE (e, ei, exit_bb->succs)
2269 if (!loop_exit_edge_p (loop, e))
2270 redirect_edge_and_branch (e, loop->latch);
2272 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
2276 /* If the loop does not have an exit, reconnect header and latch. */
2277 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
2278 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
2281 merge_target_bb = loop->header;
2282 for (i = 1; i < orig_loop_num_nodes; i++)
2284 gimple_stmt_iterator gsi;
2285 gimple_stmt_iterator last;
2289 if (bb == exit_bb || bb == loop->latch)
2292 /* Make stmts member of loop->header and clear range info from all stmts
2293 in BB which is now no longer executed conditional on a predicate we
2294 could have derived it from. */
2295 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2297 gimple *stmt = gsi_stmt (gsi);
2298 gimple_set_bb (stmt, merge_target_bb);
2303 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
2304 reset_flow_sensitive_info (op);
2308 /* Update stmt list. */
2309 last = gsi_last_bb (merge_target_bb);
2310 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
2311 set_bb_seq (bb, NULL);
2313 delete_basic_block (bb);
2316 /* If possible, merge loop header to the block with the exit edge.
2317 This reduces the number of basic blocks to two, to please the
2318 vectorizer that handles only loops with two nodes. */
2320 && exit_bb != loop->header
2321 && can_merge_blocks_p (loop->header, exit_bb))
2322 merge_blocks (loop->header, exit_bb);
2329 /* Version LOOP before if-converting it; the original loop
2330 will be if-converted, the new copy of the loop will not,
2331 and the LOOP_VECTORIZED internal call will be guarding which
2332 loop to execute. The vectorizer pass will fold this
2333 internal call into either true or false. */
2336 version_loop_for_if_conversion (struct loop *loop)
2338 basic_block cond_bb;
2339 tree cond = make_ssa_name (boolean_type_node);
2340 struct loop *new_loop;
2342 gimple_stmt_iterator gsi;
2344 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
2345 build_int_cst (integer_type_node, loop->num),
2347 gimple_call_set_lhs (g, cond);
2349 initialize_original_copy_tables ();
2350 new_loop = loop_version (loop, cond, &cond_bb,
2351 REG_BR_PROB_BASE, REG_BR_PROB_BASE,
2352 REG_BR_PROB_BASE, true);
2353 free_original_copy_tables ();
2354 if (new_loop == NULL)
2356 new_loop->dont_vectorize = true;
2357 new_loop->force_vectorize = false;
2358 gsi = gsi_last_bb (cond_bb);
2359 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
2360 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2361 update_ssa (TODO_update_ssa);
2365 /* Performs splitting of critical edges. Skip splitting and return false
2366 if LOOP will not be converted because:
2368 - LOOP is not well formed.
2369 - LOOP has PHI with more than MAX_PHI_ARG_NUM arguments.
2371 Last restriction is valid only if AGGRESSIVE_IF_CONV is false. */
2374 ifcvt_split_critical_edges (struct loop *loop, bool aggressive_if_conv)
2378 unsigned int num = loop->num_nodes;
2383 vec<edge> critical_edges = vNULL;
2385 /* Loop is not well formed. */
2386 if (num <= 2 || loop->inner || !single_exit (loop))
2389 body = get_loop_body (loop);
2390 for (i = 0; i < num; i++)
2393 if (!aggressive_if_conv
2395 && EDGE_COUNT (bb->preds) > MAX_PHI_ARG_NUM)
2397 if (dump_file && (dump_flags & TDF_DETAILS))
2399 "BB %d has complicated PHI with more than %u args.\n",
2400 bb->index, MAX_PHI_ARG_NUM);
2403 critical_edges.release ();
2406 if (bb == loop->latch || bb_with_exit_edge_p (loop, bb))
2409 stmt = last_stmt (bb);
2410 /* Skip basic blocks not ending with conditional branch. */
2411 if (!stmt || gimple_code (stmt) != GIMPLE_COND)
2414 FOR_EACH_EDGE (e, ei, bb->succs)
2415 if (EDGE_CRITICAL_P (e) && e->dest->loop_father == loop)
2416 critical_edges.safe_push (e);
2420 while (critical_edges.length () > 0)
2422 e = critical_edges.pop ();
2423 /* Don't split if bb can be predicated along non-critical edge. */
2424 if (EDGE_COUNT (e->dest->preds) > 2 || all_preds_critical_p (e->dest))
2431 /* Assumes that lhs of DEF_STMT have multiple uses.
2432 Delete one use by (1) creation of copy DEF_STMT with
2433 unique lhs; (2) change original use of lhs in one
2434 use statement with newly created lhs. */
2437 ifcvt_split_def_stmt (gimple *def_stmt, gimple *use_stmt)
2442 gimple_stmt_iterator gsi;
2443 use_operand_p use_p;
2444 imm_use_iterator imm_iter;
2446 var = gimple_assign_lhs (def_stmt);
2447 copy_stmt = gimple_copy (def_stmt);
2448 lhs = make_temp_ssa_name (TREE_TYPE (var), NULL, "_ifc_");
2449 gimple_assign_set_lhs (copy_stmt, lhs);
2450 SSA_NAME_DEF_STMT (lhs) = copy_stmt;
2451 /* Insert copy of DEF_STMT. */
2452 gsi = gsi_for_stmt (def_stmt);
2453 gsi_insert_after (&gsi, copy_stmt, GSI_SAME_STMT);
2454 /* Change use of var to lhs in use_stmt. */
2455 if (dump_file && (dump_flags & TDF_DETAILS))
2457 fprintf (dump_file, "Change use of var ");
2458 print_generic_expr (dump_file, var, TDF_SLIM);
2459 fprintf (dump_file, " to ");
2460 print_generic_expr (dump_file, lhs, TDF_SLIM);
2461 fprintf (dump_file, "\n");
2463 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
2465 if (USE_STMT (use_p) != use_stmt)
2467 SET_USE (use_p, lhs);
2472 /* Traverse bool pattern recursively starting from VAR.
2473 Save its def and use statements to defuse_list if VAR does
2474 not have single use. */
2477 ifcvt_walk_pattern_tree (tree var, vec<gimple *> *defuse_list,
2481 enum tree_code code;
2484 def_stmt = SSA_NAME_DEF_STMT (var);
2485 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2487 if (!has_single_use (var))
2489 /* Put def and use stmts into defuse_list. */
2490 defuse_list->safe_push (def_stmt);
2491 defuse_list->safe_push (use_stmt);
2492 if (dump_file && (dump_flags & TDF_DETAILS))
2494 fprintf (dump_file, "Multiple lhs uses in stmt\n");
2495 print_gimple_stmt (dump_file, def_stmt, 0, TDF_SLIM);
2498 rhs1 = gimple_assign_rhs1 (def_stmt);
2499 code = gimple_assign_rhs_code (def_stmt);
2503 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2506 if ((TYPE_PRECISION (TREE_TYPE (rhs1)) != 1
2507 || !TYPE_UNSIGNED (TREE_TYPE (rhs1)))
2508 && TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE)
2510 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2513 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2518 ifcvt_walk_pattern_tree (rhs1, defuse_list, def_stmt);
2519 rhs2 = gimple_assign_rhs2 (def_stmt);
2520 ifcvt_walk_pattern_tree (rhs2, defuse_list, def_stmt);
2528 /* Returns true if STMT can be a root of bool pattern applied
2532 stmt_is_root_of_bool_pattern (gimple *stmt)
2534 enum tree_code code;
2537 code = gimple_assign_rhs_code (stmt);
2538 if (CONVERT_EXPR_CODE_P (code))
2540 lhs = gimple_assign_lhs (stmt);
2541 rhs = gimple_assign_rhs1 (stmt);
2542 if (TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE)
2544 if (TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE)
2548 else if (code == COND_EXPR)
2550 rhs = gimple_assign_rhs1 (stmt);
2551 if (TREE_CODE (rhs) != SSA_NAME)
2558 /* Traverse all statements in BB which correspond to loop header to
2559 find out all statements which can start bool pattern applied by
2560 vectorizer and convert multiple uses in it to conform pattern
2561 restrictions. Such case can occur if the same predicate is used both
2562 for phi node conversion and load/store mask. */
2565 ifcvt_repair_bool_pattern (basic_block bb)
2569 gimple_stmt_iterator gsi;
2570 vec<gimple *> defuse_list = vNULL;
2571 vec<gimple *> pattern_roots = vNULL;
2576 /* Collect all root pattern statements. */
2577 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2579 stmt = gsi_stmt (gsi);
2580 if (gimple_code (stmt) != GIMPLE_ASSIGN)
2582 if (!stmt_is_root_of_bool_pattern (stmt))
2584 pattern_roots.safe_push (stmt);
2587 if (pattern_roots.is_empty ())
2590 /* Split all statements with multiple uses iteratively since splitting
2591 may create new multiple uses. */
2596 FOR_EACH_VEC_ELT (pattern_roots, ix, stmt)
2598 rhs = gimple_assign_rhs1 (stmt);
2599 ifcvt_walk_pattern_tree (rhs, &defuse_list, stmt);
2600 while (defuse_list.length () > 0)
2603 gimple *def_stmt, *use_stmt;
2604 use_stmt = defuse_list.pop ();
2605 def_stmt = defuse_list.pop ();
2606 ifcvt_split_def_stmt (def_stmt, use_stmt);
2611 if (dump_file && (dump_flags & TDF_DETAILS))
2612 fprintf (dump_file, "Repair bool pattern takes %d iterations. \n",
2616 /* Delete redundant statements produced by predication which prevents
2617 loop vectorization. */
2620 ifcvt_local_dce (basic_block bb)
2625 gimple_stmt_iterator gsi;
2626 auto_vec<gimple *> worklist;
2627 enum gimple_code code;
2628 use_operand_p use_p;
2629 imm_use_iterator imm_iter;
2631 worklist.create (64);
2632 /* Consider all phi as live statements. */
2633 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2635 phi = gsi_stmt (gsi);
2636 gimple_set_plf (phi, GF_PLF_2, true);
2637 worklist.safe_push (phi);
2639 /* Consider load/store statements, CALL and COND as live. */
2640 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2642 stmt = gsi_stmt (gsi);
2643 if (gimple_store_p (stmt)
2644 || gimple_assign_load_p (stmt)
2645 || is_gimple_debug (stmt))
2647 gimple_set_plf (stmt, GF_PLF_2, true);
2648 worklist.safe_push (stmt);
2651 code = gimple_code (stmt);
2652 if (code == GIMPLE_COND || code == GIMPLE_CALL)
2654 gimple_set_plf (stmt, GF_PLF_2, true);
2655 worklist.safe_push (stmt);
2658 gimple_set_plf (stmt, GF_PLF_2, false);
2660 if (code == GIMPLE_ASSIGN)
2662 tree lhs = gimple_assign_lhs (stmt);
2663 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
2665 stmt1 = USE_STMT (use_p);
2666 if (gimple_bb (stmt1) != bb)
2668 gimple_set_plf (stmt, GF_PLF_2, true);
2669 worklist.safe_push (stmt);
2675 /* Propagate liveness through arguments of live stmt. */
2676 while (worklist.length () > 0)
2679 use_operand_p use_p;
2682 stmt = worklist.pop ();
2683 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
2685 use = USE_FROM_PTR (use_p);
2686 if (TREE_CODE (use) != SSA_NAME)
2688 stmt1 = SSA_NAME_DEF_STMT (use);
2689 if (gimple_bb (stmt1) != bb
2690 || gimple_plf (stmt1, GF_PLF_2))
2692 gimple_set_plf (stmt1, GF_PLF_2, true);
2693 worklist.safe_push (stmt1);
2696 /* Delete dead statements. */
2697 gsi = gsi_start_bb (bb);
2698 while (!gsi_end_p (gsi))
2700 stmt = gsi_stmt (gsi);
2701 if (gimple_plf (stmt, GF_PLF_2))
2706 if (dump_file && (dump_flags & TDF_DETAILS))
2708 fprintf (dump_file, "Delete dead stmt in bb#%d\n", bb->index);
2709 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
2711 gsi_remove (&gsi, true);
2712 release_defs (stmt);
2716 /* If-convert LOOP when it is legal. For the moment this pass has no
2717 profitability analysis. Returns non-zero todo flags when something
2721 tree_if_conversion (struct loop *loop)
2723 unsigned int todo = 0;
2724 bool aggressive_if_conv;
2727 any_pred_load_store = false;
2728 any_complicated_phi = false;
2730 /* Apply more aggressive if-conversion when loop or its outer loop were
2731 marked with simd pragma. When that's the case, we try to if-convert
2732 loop containing PHIs with more than MAX_PHI_ARG_NUM arguments. */
2733 aggressive_if_conv = loop->force_vectorize;
2734 if (!aggressive_if_conv)
2736 struct loop *outer_loop = loop_outer (loop);
2737 if (outer_loop && outer_loop->force_vectorize)
2738 aggressive_if_conv = true;
2741 if (!ifcvt_split_critical_edges (loop, aggressive_if_conv))
2744 if (!if_convertible_loop_p (loop)
2745 || !dbg_cnt (if_conversion_tree))
2748 if ((any_pred_load_store || any_complicated_phi)
2749 && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
2750 || loop->dont_vectorize))
2753 if ((any_pred_load_store || any_complicated_phi)
2754 && !version_loop_for_if_conversion (loop))
2757 /* Now all statements are if-convertible. Combine all the basic
2758 blocks into one huge basic block doing the if-conversion
2760 combine_blocks (loop);
2762 /* Delete dead predicate computations and repair tree correspondent
2763 to bool pattern to delete multiple uses of predicates. */
2764 ifcvt_local_dce (loop->header);
2765 ifcvt_repair_bool_pattern (loop->header);
2767 todo |= TODO_cleanup_cfg;
2768 mark_virtual_operands_for_renaming (cfun);
2769 todo |= TODO_update_ssa_only_virtuals;
2776 for (i = 0; i < loop->num_nodes; i++)
2777 free_bb_predicate (ifc_bbs[i]);
2782 free_dominance_info (CDI_POST_DOMINATORS);
2787 /* Tree if-conversion pass management. */
2791 const pass_data pass_data_if_conversion =
2793 GIMPLE_PASS, /* type */
2795 OPTGROUP_NONE, /* optinfo_flags */
2796 TV_NONE, /* tv_id */
2797 ( PROP_cfg | PROP_ssa ), /* properties_required */
2798 0, /* properties_provided */
2799 0, /* properties_destroyed */
2800 0, /* todo_flags_start */
2801 0, /* todo_flags_finish */
2804 class pass_if_conversion : public gimple_opt_pass
2807 pass_if_conversion (gcc::context *ctxt)
2808 : gimple_opt_pass (pass_data_if_conversion, ctxt)
2811 /* opt_pass methods: */
2812 virtual bool gate (function *);
2813 virtual unsigned int execute (function *);
2815 }; // class pass_if_conversion
2818 pass_if_conversion::gate (function *fun)
2820 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
2821 && flag_tree_loop_if_convert != 0)
2822 || flag_tree_loop_if_convert == 1
2823 || flag_tree_loop_if_convert_stores == 1);
2827 pass_if_conversion::execute (function *fun)
2832 if (number_of_loops (fun) <= 1)
2835 FOR_EACH_LOOP (loop, 0)
2836 if (flag_tree_loop_if_convert == 1
2837 || flag_tree_loop_if_convert_stores == 1
2838 || ((flag_tree_loop_vectorize || loop->force_vectorize)
2839 && !loop->dont_vectorize))
2840 todo |= tree_if_conversion (loop);
2845 FOR_EACH_BB_FN (bb, fun)
2846 gcc_assert (!bb->aux);
2855 make_pass_if_conversion (gcc::context *ctxt)
2857 return new pass_if_conversion (ctxt);