gcc/
[official-gcc.git] / gcc / tree-if-conv.c
blob1f8ef03375ee36db3b71a05b91e1b72166c3b102
1 /* If-conversion for vectorizer.
2 Copyright (C) 2004-2014 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
10 version.
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
15 for more details.
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
23 conditions.
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'
31 predicate list.
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:
40 INPUT
41 -----
43 # i_23 = PHI <0(0), i_18(10)>;
44 <L0>:;
45 j_15 = A[i_23];
46 if (j_15 > 41) goto <L1>; else goto <L17>;
48 <L17>:;
49 goto <bb 3> (<L3>);
51 <L1>:;
53 # iftmp.2_4 = PHI <0(8), 42(2)>;
54 <L3>:;
55 A[i_23] = iftmp.2_4;
56 i_18 = i_23 + 1;
57 if (i_18 <= 15) goto <L19>; else goto <L18>;
59 <L19>:;
60 goto <bb 1> (<L0>);
62 <L18>:;
64 OUTPUT
65 ------
67 # i_23 = PHI <0(0), i_18(10)>;
68 <L0>:;
69 j_15 = A[i_23];
71 <L3>:;
72 iftmp.2_4 = j_15 > 41 ? 42 : 0;
73 A[i_23] = iftmp.2_4;
74 i_18 = i_23 + 1;
75 if (i_18 <= 15) goto <L19>; else goto <L18>;
77 <L19>:;
78 goto <bb 1> (<L0>);
80 <L18>:;
83 #include "config.h"
84 #include "system.h"
85 #include "coretypes.h"
86 #include "tm.h"
87 #include "tree.h"
88 #include "stor-layout.h"
89 #include "flags.h"
90 #include "basic-block.h"
91 #include "gimple-pretty-print.h"
92 #include "tree-ssa-alias.h"
93 #include "internal-fn.h"
94 #include "gimple-fold.h"
95 #include "gimple-expr.h"
96 #include "is-a.h"
97 #include "gimple.h"
98 #include "gimplify.h"
99 #include "gimple-iterator.h"
100 #include "gimplify-me.h"
101 #include "gimple-ssa.h"
102 #include "tree-cfg.h"
103 #include "tree-phinodes.h"
104 #include "ssa-iterators.h"
105 #include "stringpool.h"
106 #include "tree-ssanames.h"
107 #include "tree-into-ssa.h"
108 #include "tree-ssa.h"
109 #include "cfgloop.h"
110 #include "tree-chrec.h"
111 #include "tree-data-ref.h"
112 #include "tree-scalar-evolution.h"
113 #include "tree-ssa-loop-ivopts.h"
114 #include "tree-ssa-address.h"
115 #include "tree-pass.h"
116 #include "dbgcnt.h"
117 #include "expr.h"
118 #include "optabs.h"
120 /* List of basic blocks in if-conversion-suitable order. */
121 static basic_block *ifc_bbs;
123 /* Structure used to predicate basic blocks. This is attached to the
124 ->aux field of the BBs in the loop to be if-converted. */
125 typedef struct bb_predicate_s {
127 /* The condition under which this basic block is executed. */
128 tree predicate;
130 /* PREDICATE is gimplified, and the sequence of statements is
131 recorded here, in order to avoid the duplication of computations
132 that occur in previous conditions. See PR44483. */
133 gimple_seq predicate_gimplified_stmts;
134 } *bb_predicate_p;
136 /* Returns true when the basic block BB has a predicate. */
138 static inline bool
139 bb_has_predicate (basic_block bb)
141 return bb->aux != NULL;
144 /* Returns the gimplified predicate for basic block BB. */
146 static inline tree
147 bb_predicate (basic_block bb)
149 return ((bb_predicate_p) bb->aux)->predicate;
152 /* Sets the gimplified predicate COND for basic block BB. */
154 static inline void
155 set_bb_predicate (basic_block bb, tree cond)
157 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
158 && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
159 || is_gimple_condexpr (cond));
160 ((bb_predicate_p) bb->aux)->predicate = cond;
163 /* Returns the sequence of statements of the gimplification of the
164 predicate for basic block BB. */
166 static inline gimple_seq
167 bb_predicate_gimplified_stmts (basic_block bb)
169 return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts;
172 /* Sets the sequence of statements STMTS of the gimplification of the
173 predicate for basic block BB. */
175 static inline void
176 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
178 ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts;
181 /* Adds the sequence of statements STMTS to the sequence of statements
182 of the predicate for basic block BB. */
184 static inline void
185 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
187 gimple_seq_add_seq
188 (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts);
191 /* Initializes to TRUE the predicate of basic block BB. */
193 static inline void
194 init_bb_predicate (basic_block bb)
196 bb->aux = XNEW (struct bb_predicate_s);
197 set_bb_predicate_gimplified_stmts (bb, NULL);
198 set_bb_predicate (bb, boolean_true_node);
201 /* Release the SSA_NAMEs associated with the predicate of basic block BB,
202 but don't actually free it. */
204 static inline void
205 release_bb_predicate (basic_block bb)
207 gimple_seq stmts = bb_predicate_gimplified_stmts (bb);
208 if (stmts)
210 gimple_stmt_iterator i;
212 for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
213 free_stmt_operands (cfun, gsi_stmt (i));
214 set_bb_predicate_gimplified_stmts (bb, NULL);
218 /* Free the predicate of basic block BB. */
220 static inline void
221 free_bb_predicate (basic_block bb)
223 if (!bb_has_predicate (bb))
224 return;
226 release_bb_predicate (bb);
227 free (bb->aux);
228 bb->aux = NULL;
231 /* Reinitialize predicate of BB with the true predicate. */
233 static inline void
234 reset_bb_predicate (basic_block bb)
236 if (!bb_has_predicate (bb))
237 init_bb_predicate (bb);
238 else
240 release_bb_predicate (bb);
241 set_bb_predicate (bb, boolean_true_node);
245 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
246 the expression EXPR. Inserts the statement created for this
247 computation before GSI and leaves the iterator GSI at the same
248 statement. */
250 static tree
251 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
253 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
254 gimple stmt = gimple_build_assign (new_name, expr);
255 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
256 return new_name;
259 /* Return true when COND is a true predicate. */
261 static inline bool
262 is_true_predicate (tree cond)
264 return (cond == NULL_TREE
265 || cond == boolean_true_node
266 || integer_onep (cond));
269 /* Returns true when BB has a predicate that is not trivial: true or
270 NULL_TREE. */
272 static inline bool
273 is_predicated (basic_block bb)
275 return !is_true_predicate (bb_predicate (bb));
278 /* Parses the predicate COND and returns its comparison code and
279 operands OP0 and OP1. */
281 static enum tree_code
282 parse_predicate (tree cond, tree *op0, tree *op1)
284 gimple s;
286 if (TREE_CODE (cond) == SSA_NAME
287 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
289 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
291 *op0 = gimple_assign_rhs1 (s);
292 *op1 = gimple_assign_rhs2 (s);
293 return gimple_assign_rhs_code (s);
296 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
298 tree op = gimple_assign_rhs1 (s);
299 tree type = TREE_TYPE (op);
300 enum tree_code code = parse_predicate (op, op0, op1);
302 return code == ERROR_MARK ? ERROR_MARK
303 : invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (type)));
306 return ERROR_MARK;
309 if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
311 *op0 = TREE_OPERAND (cond, 0);
312 *op1 = TREE_OPERAND (cond, 1);
313 return TREE_CODE (cond);
316 return ERROR_MARK;
319 /* Returns the fold of predicate C1 OR C2 at location LOC. */
321 static tree
322 fold_or_predicates (location_t loc, tree c1, tree c2)
324 tree op1a, op1b, op2a, op2b;
325 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
326 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
328 if (code1 != ERROR_MARK && code2 != ERROR_MARK)
330 tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
331 code2, op2a, op2b);
332 if (t)
333 return t;
336 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
339 /* Returns true if N is either a constant or a SSA_NAME. */
341 static bool
342 constant_or_ssa_name (tree n)
344 switch (TREE_CODE (n))
346 case SSA_NAME:
347 case INTEGER_CST:
348 case REAL_CST:
349 case COMPLEX_CST:
350 case VECTOR_CST:
351 return true;
352 default:
353 return false;
357 /* Returns either a COND_EXPR or the folded expression if the folded
358 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
359 a constant or a SSA_NAME. */
361 static tree
362 fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
364 tree rhs1, lhs1, cond_expr;
365 cond_expr = fold_ternary (COND_EXPR, type, cond,
366 rhs, lhs);
368 if (cond_expr == NULL_TREE)
369 return build3 (COND_EXPR, type, cond, rhs, lhs);
371 STRIP_USELESS_TYPE_CONVERSION (cond_expr);
373 if (constant_or_ssa_name (cond_expr))
374 return cond_expr;
376 if (TREE_CODE (cond_expr) == ABS_EXPR)
378 rhs1 = TREE_OPERAND (cond_expr, 1);
379 STRIP_USELESS_TYPE_CONVERSION (rhs1);
380 if (constant_or_ssa_name (rhs1))
381 return build1 (ABS_EXPR, type, rhs1);
384 if (TREE_CODE (cond_expr) == MIN_EXPR
385 || TREE_CODE (cond_expr) == MAX_EXPR)
387 lhs1 = TREE_OPERAND (cond_expr, 0);
388 STRIP_USELESS_TYPE_CONVERSION (lhs1);
389 rhs1 = TREE_OPERAND (cond_expr, 1);
390 STRIP_USELESS_TYPE_CONVERSION (rhs1);
391 if (constant_or_ssa_name (rhs1)
392 && constant_or_ssa_name (lhs1))
393 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
395 return build3 (COND_EXPR, type, cond, rhs, lhs);
398 /* Add condition NC to the predicate list of basic block BB. LOOP is
399 the loop to be if-converted. */
401 static inline void
402 add_to_predicate_list (struct loop *loop, basic_block bb, tree nc)
404 tree bc, *tp;
406 if (is_true_predicate (nc))
407 return;
409 if (!is_predicated (bb))
411 /* If dominance tells us this basic block is always executed, don't
412 record any predicates for it. */
413 if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
414 return;
416 bc = nc;
418 else
420 bc = bb_predicate (bb);
421 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
422 if (is_true_predicate (bc))
424 reset_bb_predicate (bb);
425 return;
429 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
430 if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
431 tp = &TREE_OPERAND (bc, 0);
432 else
433 tp = &bc;
434 if (!is_gimple_condexpr (*tp))
436 gimple_seq stmts;
437 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
438 add_bb_predicate_gimplified_stmts (bb, stmts);
440 set_bb_predicate (bb, bc);
443 /* Add the condition COND to the previous condition PREV_COND, and add
444 this to the predicate list of the destination of edge E. LOOP is
445 the loop to be if-converted. */
447 static void
448 add_to_dst_predicate_list (struct loop *loop, edge e,
449 tree prev_cond, tree cond)
451 if (!flow_bb_inside_loop_p (loop, e->dest))
452 return;
454 if (!is_true_predicate (prev_cond))
455 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
456 prev_cond, cond);
458 add_to_predicate_list (loop, e->dest, cond);
461 /* Return true if one of the successor edges of BB exits LOOP. */
463 static bool
464 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
466 edge e;
467 edge_iterator ei;
469 FOR_EACH_EDGE (e, ei, bb->succs)
470 if (loop_exit_edge_p (loop, e))
471 return true;
473 return false;
476 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
477 and it belongs to basic block BB.
479 PHI is not if-convertible if:
480 - it has more than 2 arguments.
482 When the flag_tree_loop_if_convert_stores is not set, PHI is not
483 if-convertible if:
484 - a virtual PHI is immediately used in another PHI node,
485 - there is a virtual PHI in a BB other than the loop->header. */
487 static bool
488 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi,
489 bool any_mask_load_store)
491 if (dump_file && (dump_flags & TDF_DETAILS))
493 fprintf (dump_file, "-------------------------\n");
494 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
497 if (bb != loop->header && gimple_phi_num_args (phi) != 2)
499 if (dump_file && (dump_flags & TDF_DETAILS))
500 fprintf (dump_file, "More than two phi node args.\n");
501 return false;
504 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
505 return true;
507 /* When the flag_tree_loop_if_convert_stores is not set, check
508 that there are no memory writes in the branches of the loop to be
509 if-converted. */
510 if (virtual_operand_p (gimple_phi_result (phi)))
512 imm_use_iterator imm_iter;
513 use_operand_p use_p;
515 if (bb != loop->header)
517 if (dump_file && (dump_flags & TDF_DETAILS))
518 fprintf (dump_file, "Virtual phi not on loop->header.\n");
519 return false;
522 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
524 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
526 if (dump_file && (dump_flags & TDF_DETAILS))
527 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
528 return false;
533 return true;
536 /* Records the status of a data reference. This struct is attached to
537 each DR->aux field. */
539 struct ifc_dr {
540 /* -1 when not initialized, 0 when false, 1 when true. */
541 int written_at_least_once;
543 /* -1 when not initialized, 0 when false, 1 when true. */
544 int rw_unconditionally;
547 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
548 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
549 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
551 /* Returns true when the memory references of STMT are read or written
552 unconditionally. In other words, this function returns true when
553 for every data reference A in STMT there exist other accesses to
554 a data reference with the same base with predicates that add up (OR-up) to
555 the true predicate: this ensures that the data reference A is touched
556 (read or written) on every iteration of the if-converted loop. */
558 static bool
559 memrefs_read_or_written_unconditionally (gimple stmt,
560 vec<data_reference_p> drs)
562 int i, j;
563 data_reference_p a, b;
564 tree ca = bb_predicate (gimple_bb (stmt));
566 for (i = 0; drs.iterate (i, &a); i++)
567 if (DR_STMT (a) == stmt)
569 bool found = false;
570 int x = DR_RW_UNCONDITIONALLY (a);
572 if (x == 0)
573 return false;
575 if (x == 1)
576 continue;
578 for (j = 0; drs.iterate (j, &b); j++)
580 tree ref_base_a = DR_REF (a);
581 tree ref_base_b = DR_REF (b);
583 if (DR_STMT (b) == stmt)
584 continue;
586 while (TREE_CODE (ref_base_a) == COMPONENT_REF
587 || TREE_CODE (ref_base_a) == IMAGPART_EXPR
588 || TREE_CODE (ref_base_a) == REALPART_EXPR)
589 ref_base_a = TREE_OPERAND (ref_base_a, 0);
591 while (TREE_CODE (ref_base_b) == COMPONENT_REF
592 || TREE_CODE (ref_base_b) == IMAGPART_EXPR
593 || TREE_CODE (ref_base_b) == REALPART_EXPR)
594 ref_base_b = TREE_OPERAND (ref_base_b, 0);
596 if (!operand_equal_p (ref_base_a, ref_base_b, 0))
598 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
600 if (DR_RW_UNCONDITIONALLY (b) == 1
601 || is_true_predicate (cb)
602 || is_true_predicate (ca
603 = fold_or_predicates (EXPR_LOCATION (cb), ca, cb)))
605 DR_RW_UNCONDITIONALLY (a) = 1;
606 DR_RW_UNCONDITIONALLY (b) = 1;
607 found = true;
608 break;
613 if (!found)
615 DR_RW_UNCONDITIONALLY (a) = 0;
616 return false;
620 return true;
623 /* Returns true when the memory references of STMT are unconditionally
624 written. In other words, this function returns true when for every
625 data reference A written in STMT, there exist other writes to the
626 same data reference with predicates that add up (OR-up) to the true
627 predicate: this ensures that the data reference A is written on
628 every iteration of the if-converted loop. */
630 static bool
631 write_memrefs_written_at_least_once (gimple stmt,
632 vec<data_reference_p> drs)
634 int i, j;
635 data_reference_p a, b;
636 tree ca = bb_predicate (gimple_bb (stmt));
638 for (i = 0; drs.iterate (i, &a); i++)
639 if (DR_STMT (a) == stmt
640 && DR_IS_WRITE (a))
642 bool found = false;
643 int x = DR_WRITTEN_AT_LEAST_ONCE (a);
645 if (x == 0)
646 return false;
648 if (x == 1)
649 continue;
651 for (j = 0; drs.iterate (j, &b); j++)
652 if (DR_STMT (b) != stmt
653 && DR_IS_WRITE (b)
654 && same_data_refs_base_objects (a, b))
656 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
658 if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1
659 || is_true_predicate (cb)
660 || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
661 ca, cb)))
663 DR_WRITTEN_AT_LEAST_ONCE (a) = 1;
664 DR_WRITTEN_AT_LEAST_ONCE (b) = 1;
665 found = true;
666 break;
670 if (!found)
672 DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
673 return false;
677 return true;
680 /* Return true when the memory references of STMT won't trap in the
681 if-converted code. There are two things that we have to check for:
683 - writes to memory occur to writable memory: if-conversion of
684 memory writes transforms the conditional memory writes into
685 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
686 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
687 be executed at all in the original code, it may be a readonly
688 memory. To check that A is not const-qualified, we check that
689 there exists at least an unconditional write to A in the current
690 function.
692 - reads or writes to memory are valid memory accesses for every
693 iteration. To check that the memory accesses are correctly formed
694 and that we are allowed to read and write in these locations, we
695 check that the memory accesses to be if-converted occur at every
696 iteration unconditionally. */
698 static bool
699 ifcvt_memrefs_wont_trap (gimple stmt, vec<data_reference_p> refs)
701 return write_memrefs_written_at_least_once (stmt, refs)
702 && memrefs_read_or_written_unconditionally (stmt, refs);
705 /* Wrapper around gimple_could_trap_p refined for the needs of the
706 if-conversion. Try to prove that the memory accesses of STMT could
707 not trap in the innermost loop containing STMT. */
709 static bool
710 ifcvt_could_trap_p (gimple stmt, vec<data_reference_p> refs)
712 if (gimple_vuse (stmt)
713 && !gimple_could_trap_p_1 (stmt, false, false)
714 && ifcvt_memrefs_wont_trap (stmt, refs))
715 return false;
717 return gimple_could_trap_p (stmt);
720 /* Return true if STMT could be converted into a masked load or store
721 (conditional load or store based on a mask computed from bb predicate). */
723 static bool
724 ifcvt_can_use_mask_load_store (gimple stmt)
726 tree lhs, ref;
727 enum machine_mode mode;
728 basic_block bb = gimple_bb (stmt);
729 bool is_load;
731 if (!(flag_tree_loop_vectorize || bb->loop_father->force_vectorize)
732 || bb->loop_father->dont_vectorize
733 || !gimple_assign_single_p (stmt)
734 || gimple_has_volatile_ops (stmt))
735 return false;
737 /* Check whether this is a load or store. */
738 lhs = gimple_assign_lhs (stmt);
739 if (gimple_store_p (stmt))
741 if (!is_gimple_val (gimple_assign_rhs1 (stmt)))
742 return false;
743 is_load = false;
744 ref = lhs;
746 else if (gimple_assign_load_p (stmt))
748 is_load = true;
749 ref = gimple_assign_rhs1 (stmt);
751 else
752 return false;
754 if (may_be_nonaddressable_p (ref))
755 return false;
757 /* Mask should be integer mode of the same size as the load/store
758 mode. */
759 mode = TYPE_MODE (TREE_TYPE (lhs));
760 if (int_mode_for_mode (mode) == BLKmode
761 || VECTOR_MODE_P (mode))
762 return false;
764 if (can_vec_mask_load_store_p (mode, is_load))
765 return true;
767 return false;
770 /* Return true when STMT is if-convertible.
772 GIMPLE_ASSIGN statement is not if-convertible if,
773 - it is not movable,
774 - it could trap,
775 - LHS is not var decl. */
777 static bool
778 if_convertible_gimple_assign_stmt_p (gimple stmt,
779 vec<data_reference_p> refs,
780 bool *any_mask_load_store)
782 tree lhs = gimple_assign_lhs (stmt);
783 basic_block bb;
785 if (dump_file && (dump_flags & TDF_DETAILS))
787 fprintf (dump_file, "-------------------------\n");
788 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
791 if (!is_gimple_reg_type (TREE_TYPE (lhs)))
792 return false;
794 /* Some of these constrains might be too conservative. */
795 if (stmt_ends_bb_p (stmt)
796 || gimple_has_volatile_ops (stmt)
797 || (TREE_CODE (lhs) == SSA_NAME
798 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
799 || gimple_has_side_effects (stmt))
801 if (dump_file && (dump_flags & TDF_DETAILS))
802 fprintf (dump_file, "stmt not suitable for ifcvt\n");
803 return false;
806 /* tree-into-ssa.c uses GF_PLF_1, so avoid it, because
807 in between if_convertible_loop_p and combine_blocks
808 we can perform loop versioning. */
809 gimple_set_plf (stmt, GF_PLF_2, false);
811 if (flag_tree_loop_if_convert_stores)
813 if (ifcvt_could_trap_p (stmt, refs))
815 if (ifcvt_can_use_mask_load_store (stmt))
817 gimple_set_plf (stmt, GF_PLF_2, true);
818 *any_mask_load_store = true;
819 return true;
821 if (dump_file && (dump_flags & TDF_DETAILS))
822 fprintf (dump_file, "tree could trap...\n");
823 return false;
825 return true;
828 if (gimple_assign_rhs_could_trap_p (stmt))
830 if (ifcvt_can_use_mask_load_store (stmt))
832 gimple_set_plf (stmt, GF_PLF_2, true);
833 *any_mask_load_store = true;
834 return true;
836 if (dump_file && (dump_flags & TDF_DETAILS))
837 fprintf (dump_file, "tree could trap...\n");
838 return false;
841 bb = gimple_bb (stmt);
843 if (TREE_CODE (lhs) != SSA_NAME
844 && bb != bb->loop_father->header
845 && !bb_with_exit_edge_p (bb->loop_father, bb))
847 if (ifcvt_can_use_mask_load_store (stmt))
849 gimple_set_plf (stmt, GF_PLF_2, true);
850 *any_mask_load_store = true;
851 return true;
853 if (dump_file && (dump_flags & TDF_DETAILS))
855 fprintf (dump_file, "LHS is not var\n");
856 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
858 return false;
861 return true;
864 /* Return true when STMT is if-convertible.
866 A statement is if-convertible if:
867 - it is an if-convertible GIMPLE_ASSIGN,
868 - it is a GIMPLE_LABEL or a GIMPLE_COND. */
870 static bool
871 if_convertible_stmt_p (gimple stmt, vec<data_reference_p> refs,
872 bool *any_mask_load_store)
874 switch (gimple_code (stmt))
876 case GIMPLE_LABEL:
877 case GIMPLE_DEBUG:
878 case GIMPLE_COND:
879 return true;
881 case GIMPLE_ASSIGN:
882 return if_convertible_gimple_assign_stmt_p (stmt, refs,
883 any_mask_load_store);
885 case GIMPLE_CALL:
887 tree fndecl = gimple_call_fndecl (stmt);
888 if (fndecl)
890 int flags = gimple_call_flags (stmt);
891 if ((flags & ECF_CONST)
892 && !(flags & ECF_LOOPING_CONST_OR_PURE)
893 /* We can only vectorize some builtins at the moment,
894 so restrict if-conversion to those. */
895 && DECL_BUILT_IN (fndecl))
896 return true;
898 return false;
901 default:
902 /* Don't know what to do with 'em so don't do anything. */
903 if (dump_file && (dump_flags & TDF_DETAILS))
905 fprintf (dump_file, "don't know what to do\n");
906 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
908 return false;
909 break;
912 return true;
915 /* Return true when BB is if-convertible. This routine does not check
916 basic block's statements and phis.
918 A basic block is not if-convertible if:
919 - it is non-empty and it is after the exit block (in BFS order),
920 - it is after the exit block but before the latch,
921 - its edges are not normal.
923 EXIT_BB is the basic block containing the exit of the LOOP. BB is
924 inside LOOP. */
926 static bool
927 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
929 edge e;
930 edge_iterator ei;
932 if (dump_file && (dump_flags & TDF_DETAILS))
933 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
935 if (EDGE_COUNT (bb->preds) > 2
936 || EDGE_COUNT (bb->succs) > 2)
937 return false;
939 if (exit_bb)
941 if (bb != loop->latch)
943 if (dump_file && (dump_flags & TDF_DETAILS))
944 fprintf (dump_file, "basic block after exit bb but before latch\n");
945 return false;
947 else if (!empty_block_p (bb))
949 if (dump_file && (dump_flags & TDF_DETAILS))
950 fprintf (dump_file, "non empty basic block after exit bb\n");
951 return false;
953 else if (bb == loop->latch
954 && bb != exit_bb
955 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
957 if (dump_file && (dump_flags & TDF_DETAILS))
958 fprintf (dump_file, "latch is not dominated by exit_block\n");
959 return false;
963 /* Be less adventurous and handle only normal edges. */
964 FOR_EACH_EDGE (e, ei, bb->succs)
965 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
967 if (dump_file && (dump_flags & TDF_DETAILS))
968 fprintf (dump_file, "Difficult to handle edges\n");
969 return false;
972 /* At least one incoming edge has to be non-critical as otherwise edge
973 predicates are not equal to basic-block predicates of the edge
974 source. */
975 if (EDGE_COUNT (bb->preds) > 1
976 && bb != loop->header)
978 bool found = false;
979 FOR_EACH_EDGE (e, ei, bb->preds)
980 if (EDGE_COUNT (e->src->succs) == 1)
981 found = true;
982 if (!found)
984 if (dump_file && (dump_flags & TDF_DETAILS))
985 fprintf (dump_file, "only critical predecessors\n");
986 return false;
990 return true;
993 /* Return true when all predecessor blocks of BB are visited. The
994 VISITED bitmap keeps track of the visited blocks. */
996 static bool
997 pred_blocks_visited_p (basic_block bb, bitmap *visited)
999 edge e;
1000 edge_iterator ei;
1001 FOR_EACH_EDGE (e, ei, bb->preds)
1002 if (!bitmap_bit_p (*visited, e->src->index))
1003 return false;
1005 return true;
1008 /* Get body of a LOOP in suitable order for if-conversion. It is
1009 caller's responsibility to deallocate basic block list.
1010 If-conversion suitable order is, breadth first sort (BFS) order
1011 with an additional constraint: select a block only if all its
1012 predecessors are already selected. */
1014 static basic_block *
1015 get_loop_body_in_if_conv_order (const struct loop *loop)
1017 basic_block *blocks, *blocks_in_bfs_order;
1018 basic_block bb;
1019 bitmap visited;
1020 unsigned int index = 0;
1021 unsigned int visited_count = 0;
1023 gcc_assert (loop->num_nodes);
1024 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1026 blocks = XCNEWVEC (basic_block, loop->num_nodes);
1027 visited = BITMAP_ALLOC (NULL);
1029 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
1031 index = 0;
1032 while (index < loop->num_nodes)
1034 bb = blocks_in_bfs_order [index];
1036 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1038 free (blocks_in_bfs_order);
1039 BITMAP_FREE (visited);
1040 free (blocks);
1041 return NULL;
1044 if (!bitmap_bit_p (visited, bb->index))
1046 if (pred_blocks_visited_p (bb, &visited)
1047 || bb == loop->header)
1049 /* This block is now visited. */
1050 bitmap_set_bit (visited, bb->index);
1051 blocks[visited_count++] = bb;
1055 index++;
1057 if (index == loop->num_nodes
1058 && visited_count != loop->num_nodes)
1059 /* Not done yet. */
1060 index = 0;
1062 free (blocks_in_bfs_order);
1063 BITMAP_FREE (visited);
1064 return blocks;
1067 /* Returns true when the analysis of the predicates for all the basic
1068 blocks in LOOP succeeded.
1070 predicate_bbs first allocates the predicates of the basic blocks.
1071 These fields are then initialized with the tree expressions
1072 representing the predicates under which a basic block is executed
1073 in the LOOP. As the loop->header is executed at each iteration, it
1074 has the "true" predicate. Other statements executed under a
1075 condition are predicated with that condition, for example
1077 | if (x)
1078 | S1;
1079 | else
1080 | S2;
1082 S1 will be predicated with "x", and
1083 S2 will be predicated with "!x". */
1085 static void
1086 predicate_bbs (loop_p loop)
1088 unsigned int i;
1090 for (i = 0; i < loop->num_nodes; i++)
1091 init_bb_predicate (ifc_bbs[i]);
1093 for (i = 0; i < loop->num_nodes; i++)
1095 basic_block bb = ifc_bbs[i];
1096 tree cond;
1097 gimple stmt;
1099 /* The loop latch is always executed and has no extra conditions
1100 to be processed: skip it. */
1101 if (bb == loop->latch)
1103 reset_bb_predicate (loop->latch);
1104 continue;
1107 cond = bb_predicate (bb);
1108 stmt = last_stmt (bb);
1109 if (stmt && gimple_code (stmt) == GIMPLE_COND)
1111 tree c2;
1112 edge true_edge, false_edge;
1113 location_t loc = gimple_location (stmt);
1114 tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
1115 boolean_type_node,
1116 gimple_cond_lhs (stmt),
1117 gimple_cond_rhs (stmt));
1119 /* Add new condition into destination's predicate list. */
1120 extract_true_false_edges_from_block (gimple_bb (stmt),
1121 &true_edge, &false_edge);
1123 /* If C is true, then TRUE_EDGE is taken. */
1124 add_to_dst_predicate_list (loop, true_edge, unshare_expr (cond),
1125 unshare_expr (c));
1127 /* If C is false, then FALSE_EDGE is taken. */
1128 c2 = build1_loc (loc, TRUTH_NOT_EXPR, boolean_type_node,
1129 unshare_expr (c));
1130 add_to_dst_predicate_list (loop, false_edge,
1131 unshare_expr (cond), c2);
1133 cond = NULL_TREE;
1136 /* If current bb has only one successor, then consider it as an
1137 unconditional goto. */
1138 if (single_succ_p (bb))
1140 basic_block bb_n = single_succ (bb);
1142 /* The successor bb inherits the predicate of its
1143 predecessor. If there is no predicate in the predecessor
1144 bb, then consider the successor bb as always executed. */
1145 if (cond == NULL_TREE)
1146 cond = boolean_true_node;
1148 add_to_predicate_list (loop, bb_n, cond);
1152 /* The loop header is always executed. */
1153 reset_bb_predicate (loop->header);
1154 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1155 && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1158 /* Return true when LOOP is if-convertible. This is a helper function
1159 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1160 in if_convertible_loop_p. */
1162 static bool
1163 if_convertible_loop_p_1 (struct loop *loop,
1164 vec<loop_p> *loop_nest,
1165 vec<data_reference_p> *refs,
1166 vec<ddr_p> *ddrs, bool *any_mask_load_store)
1168 bool res;
1169 unsigned int i;
1170 basic_block exit_bb = NULL;
1172 /* Don't if-convert the loop when the data dependences cannot be
1173 computed: the loop won't be vectorized in that case. */
1174 res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs);
1175 if (!res)
1176 return false;
1178 calculate_dominance_info (CDI_DOMINATORS);
1180 /* Allow statements that can be handled during if-conversion. */
1181 ifc_bbs = get_loop_body_in_if_conv_order (loop);
1182 if (!ifc_bbs)
1184 if (dump_file && (dump_flags & TDF_DETAILS))
1185 fprintf (dump_file, "Irreducible loop\n");
1186 return false;
1189 for (i = 0; i < loop->num_nodes; i++)
1191 basic_block bb = ifc_bbs[i];
1193 if (!if_convertible_bb_p (loop, bb, exit_bb))
1194 return false;
1196 if (bb_with_exit_edge_p (loop, bb))
1197 exit_bb = bb;
1200 for (i = 0; i < loop->num_nodes; i++)
1202 basic_block bb = ifc_bbs[i];
1203 gimple_stmt_iterator gsi;
1205 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1206 switch (gimple_code (gsi_stmt (gsi)))
1208 case GIMPLE_LABEL:
1209 case GIMPLE_ASSIGN:
1210 case GIMPLE_CALL:
1211 case GIMPLE_DEBUG:
1212 case GIMPLE_COND:
1213 break;
1214 default:
1215 return false;
1219 if (flag_tree_loop_if_convert_stores)
1221 data_reference_p dr;
1223 for (i = 0; refs->iterate (i, &dr); i++)
1225 dr->aux = XNEW (struct ifc_dr);
1226 DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
1227 DR_RW_UNCONDITIONALLY (dr) = -1;
1229 predicate_bbs (loop);
1232 for (i = 0; i < loop->num_nodes; i++)
1234 basic_block bb = ifc_bbs[i];
1235 gimple_stmt_iterator itr;
1237 /* Check the if-convertibility of statements in predicated BBs. */
1238 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1239 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1240 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs,
1241 any_mask_load_store))
1242 return false;
1245 if (flag_tree_loop_if_convert_stores)
1246 for (i = 0; i < loop->num_nodes; i++)
1247 free_bb_predicate (ifc_bbs[i]);
1249 /* Checking PHIs needs to be done after stmts, as the fact whether there
1250 are any masked loads or stores affects the tests. */
1251 for (i = 0; i < loop->num_nodes; i++)
1253 basic_block bb = ifc_bbs[i];
1254 gimple_stmt_iterator itr;
1256 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1257 if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr),
1258 *any_mask_load_store))
1259 return false;
1262 if (dump_file)
1263 fprintf (dump_file, "Applying if-conversion\n");
1265 return true;
1268 /* Return true when LOOP is if-convertible.
1269 LOOP is if-convertible if:
1270 - it is innermost,
1271 - it has two or more basic blocks,
1272 - it has only one exit,
1273 - loop header is not the exit edge,
1274 - if its basic blocks and phi nodes are if convertible. */
1276 static bool
1277 if_convertible_loop_p (struct loop *loop, bool *any_mask_load_store)
1279 edge e;
1280 edge_iterator ei;
1281 bool res = false;
1282 vec<data_reference_p> refs;
1283 vec<ddr_p> ddrs;
1285 /* Handle only innermost loop. */
1286 if (!loop || loop->inner)
1288 if (dump_file && (dump_flags & TDF_DETAILS))
1289 fprintf (dump_file, "not innermost loop\n");
1290 return false;
1293 /* If only one block, no need for if-conversion. */
1294 if (loop->num_nodes <= 2)
1296 if (dump_file && (dump_flags & TDF_DETAILS))
1297 fprintf (dump_file, "less than 2 basic blocks\n");
1298 return false;
1301 /* More than one loop exit is too much to handle. */
1302 if (!single_exit (loop))
1304 if (dump_file && (dump_flags & TDF_DETAILS))
1305 fprintf (dump_file, "multiple exits\n");
1306 return false;
1309 /* If one of the loop header's edge is an exit edge then do not
1310 apply if-conversion. */
1311 FOR_EACH_EDGE (e, ei, loop->header->succs)
1312 if (loop_exit_edge_p (loop, e))
1313 return false;
1315 refs.create (5);
1316 ddrs.create (25);
1317 auto_vec<loop_p, 3> loop_nest;
1318 res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs,
1319 any_mask_load_store);
1321 if (flag_tree_loop_if_convert_stores)
1323 data_reference_p dr;
1324 unsigned int i;
1326 for (i = 0; refs.iterate (i, &dr); i++)
1327 free (dr->aux);
1330 free_data_refs (refs);
1331 free_dependence_relations (ddrs);
1332 return res;
1335 /* Basic block BB has two predecessors. Using predecessor's bb
1336 predicate, set an appropriate condition COND for the PHI node
1337 replacement. Return the true block whose phi arguments are
1338 selected when cond is true. LOOP is the loop containing the
1339 if-converted region, GSI is the place to insert the code for the
1340 if-conversion. */
1342 static basic_block
1343 find_phi_replacement_condition (basic_block bb, tree *cond,
1344 gimple_stmt_iterator *gsi)
1346 edge first_edge, second_edge;
1347 tree tmp_cond;
1349 gcc_assert (EDGE_COUNT (bb->preds) == 2);
1350 first_edge = EDGE_PRED (bb, 0);
1351 second_edge = EDGE_PRED (bb, 1);
1353 /* Prefer an edge with a not negated predicate.
1354 ??? That's a very weak cost model. */
1355 tmp_cond = bb_predicate (first_edge->src);
1356 gcc_assert (tmp_cond);
1357 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
1359 edge tmp_edge;
1361 tmp_edge = first_edge;
1362 first_edge = second_edge;
1363 second_edge = tmp_edge;
1366 /* Check if the edge we take the condition from is not critical.
1367 We know that at least one non-critical edge exists. */
1368 if (EDGE_COUNT (first_edge->src->succs) > 1)
1370 *cond = bb_predicate (second_edge->src);
1372 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
1373 *cond = TREE_OPERAND (*cond, 0);
1374 else
1375 /* Select non loop header bb. */
1376 first_edge = second_edge;
1378 else
1379 *cond = bb_predicate (first_edge->src);
1381 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1382 *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond),
1383 is_gimple_condexpr, NULL_TREE,
1384 true, GSI_SAME_STMT);
1386 return first_edge->src;
1389 /* Returns true if def-stmt for phi argument ARG is simple increment/decrement
1390 which is in predicated basic block.
1391 In fact, the following PHI pattern is searching:
1392 loop-header:
1393 reduc_1 = PHI <..., reduc_2>
1395 if (...)
1396 reduc_3 = ...
1397 reduc_2 = PHI <reduc_1, reduc_3>
1399 REDUC, OP0 and OP1 contain reduction stmt and its operands. */
1401 static bool
1402 is_cond_scalar_reduction (gimple phi, gimple *reduc,
1403 tree *op0, tree *op1)
1405 tree lhs, r_op1, r_op2;
1406 tree arg_0, arg_1;
1407 gimple stmt;
1408 gimple header_phi = NULL;
1409 enum tree_code reduction_op;
1410 basic_block bb = gimple_bb (phi);
1411 struct loop *loop = bb->loop_father;
1412 edge latch_e = loop_latch_edge (loop);
1413 imm_use_iterator imm_iter;
1414 use_operand_p use_p;
1416 arg_0 = PHI_ARG_DEF (phi, 0);
1417 arg_1 = PHI_ARG_DEF (phi, 1);
1418 if (TREE_CODE (arg_0) != SSA_NAME || TREE_CODE (arg_1) != SSA_NAME)
1419 return false;
1421 if (gimple_code (SSA_NAME_DEF_STMT (arg_0)) == GIMPLE_PHI)
1423 lhs = arg_1;
1424 header_phi = SSA_NAME_DEF_STMT (arg_0);
1425 stmt = SSA_NAME_DEF_STMT (arg_1);
1427 else if (gimple_code (SSA_NAME_DEF_STMT (arg_1)) == GIMPLE_PHI)
1429 lhs = arg_0;
1430 header_phi = SSA_NAME_DEF_STMT (arg_1);
1431 stmt = SSA_NAME_DEF_STMT (arg_0);
1433 else
1434 return false;
1435 if (gimple_bb (header_phi) != loop->header)
1436 return false;
1438 if (PHI_ARG_DEF_FROM_EDGE (header_phi, latch_e) != PHI_RESULT (phi))
1439 return false;
1441 if (gimple_code (stmt) != GIMPLE_ASSIGN
1442 || gimple_has_volatile_ops (stmt))
1443 return false;
1445 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1446 return false;
1448 if (!is_predicated (gimple_bb (stmt)))
1449 return false;
1451 /* Check that stmt-block is predecessor of phi-block. */
1452 if (EDGE_PRED (bb, 0)->src != gimple_bb (stmt)
1453 && EDGE_PRED (bb, 1)->src != gimple_bb (stmt))
1454 return false;
1456 if (!has_single_use (lhs))
1457 return false;
1459 reduction_op = gimple_assign_rhs_code (stmt);
1460 if (reduction_op != PLUS_EXPR && reduction_op != MINUS_EXPR)
1461 return false;
1462 r_op1 = gimple_assign_rhs1 (stmt);
1463 r_op2 = gimple_assign_rhs2 (stmt);
1465 /* Make R_OP1 to hold reduction variable. */
1466 if (r_op2 == PHI_RESULT (header_phi)
1467 && reduction_op == PLUS_EXPR)
1469 tree tmp = r_op1;
1470 r_op1 = r_op2;
1471 r_op2 = tmp;
1473 else if (r_op1 != PHI_RESULT (header_phi))
1474 return false;
1476 /* Check that R_OP1 is used in reduction stmt or in PHI only. */
1477 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, r_op1)
1479 gimple use_stmt = USE_STMT (use_p);
1480 if (is_gimple_debug (use_stmt))
1481 continue;
1482 if (use_stmt == stmt)
1483 continue;
1484 if (gimple_code (use_stmt) != GIMPLE_PHI)
1485 return false;
1488 *op0 = r_op1; *op1 = r_op2;
1489 *reduc = stmt;
1490 return true;
1493 /* Converts conditional scalar reduction into unconditional form, e.g.
1494 bb_4
1495 if (_5 != 0) goto bb_5 else goto bb_6
1496 end_bb_4
1497 bb_5
1498 res_6 = res_13 + 1;
1499 end_bb_5
1500 bb_6
1501 # res_2 = PHI <res_13(4), res_6(5)>
1502 end_bb_6
1504 will be converted into sequence
1505 _ifc__1 = _5 != 0 ? 1 : 0;
1506 res_2 = res_13 + _ifc__1;
1507 Argument SWAP tells that arguments of conditional expression should be
1508 swapped.
1509 Returns rhs of resulting PHI assignment. */
1511 static tree
1512 convert_scalar_cond_reduction (gimple reduc, gimple_stmt_iterator *gsi,
1513 tree cond, tree op0, tree op1, bool swap)
1515 gimple_stmt_iterator stmt_it;
1516 gimple new_assign;
1517 tree rhs;
1518 tree rhs1 = gimple_assign_rhs1 (reduc);
1519 tree tmp = make_temp_ssa_name (TREE_TYPE (rhs1), NULL, "_ifc_");
1520 tree c;
1521 tree zero = build_zero_cst (TREE_TYPE (rhs1));
1523 if (dump_file && (dump_flags & TDF_DETAILS))
1525 fprintf (dump_file, "Found cond scalar reduction.\n");
1526 print_gimple_stmt (dump_file, reduc, 0, TDF_SLIM);
1529 /* Build cond expression using COND and constant operand
1530 of reduction rhs. */
1531 c = fold_build_cond_expr (TREE_TYPE (rhs1),
1532 unshare_expr (cond),
1533 swap ? zero : op1,
1534 swap ? op1 : zero);
1536 /* Create assignment stmt and insert it at GSI. */
1537 new_assign = gimple_build_assign (tmp, c);
1538 gsi_insert_before (gsi, new_assign, GSI_SAME_STMT);
1539 /* Build rhs for unconditional increment/decrement. */
1540 rhs = fold_build2 (gimple_assign_rhs_code (reduc),
1541 TREE_TYPE (rhs1), op0, tmp);
1543 /* Delete original reduction stmt. */
1544 stmt_it = gsi_for_stmt (reduc);
1545 gsi_remove (&stmt_it, true);
1546 release_defs (reduc);
1547 return rhs;
1550 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1551 This routine does not handle PHI nodes with more than two
1552 arguments.
1554 For example,
1555 S1: A = PHI <x1(1), x2(5)>
1556 is converted into,
1557 S2: A = cond ? x1 : x2;
1559 The generated code is inserted at GSI that points to the top of
1560 basic block's statement list. When COND is true, phi arg from
1561 TRUE_BB is selected. */
1563 static void
1564 predicate_scalar_phi (gimple phi, tree cond,
1565 basic_block true_bb,
1566 gimple_stmt_iterator *gsi)
1568 gimple new_stmt;
1569 basic_block bb;
1570 tree rhs, res, arg, scev;
1572 gcc_assert (gimple_code (phi) == GIMPLE_PHI
1573 && gimple_phi_num_args (phi) == 2);
1575 res = gimple_phi_result (phi);
1576 /* Do not handle virtual phi nodes. */
1577 if (virtual_operand_p (res))
1578 return;
1580 bb = gimple_bb (phi);
1582 if ((arg = degenerate_phi_result (phi))
1583 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
1584 res))
1585 && !chrec_contains_undetermined (scev)
1586 && scev != res
1587 && (arg = gimple_phi_arg_def (phi, 0))))
1588 rhs = arg;
1589 else
1591 tree arg_0, arg_1;
1592 tree op0, op1;
1593 gimple reduc;
1595 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
1596 if (EDGE_PRED (bb, 1)->src == true_bb)
1598 arg_0 = gimple_phi_arg_def (phi, 1);
1599 arg_1 = gimple_phi_arg_def (phi, 0);
1601 else
1603 arg_0 = gimple_phi_arg_def (phi, 0);
1604 arg_1 = gimple_phi_arg_def (phi, 1);
1606 if (is_cond_scalar_reduction (phi, &reduc, &op0, &op1))
1607 /* Convert reduction stmt into vectorizable form. */
1608 rhs = convert_scalar_cond_reduction (reduc, gsi, cond, op0, op1,
1609 true_bb != gimple_bb (reduc));
1610 else
1611 /* Build new RHS using selected condition and arguments. */
1612 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1613 arg_0, arg_1);
1616 new_stmt = gimple_build_assign (res, rhs);
1617 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1618 update_stmt (new_stmt);
1620 if (dump_file && (dump_flags & TDF_DETAILS))
1622 fprintf (dump_file, "new phi replacement stmt\n");
1623 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1627 /* Replaces in LOOP all the scalar phi nodes other than those in the
1628 LOOP->header block with conditional modify expressions. */
1630 static void
1631 predicate_all_scalar_phis (struct loop *loop)
1633 basic_block bb;
1634 unsigned int orig_loop_num_nodes = loop->num_nodes;
1635 unsigned int i;
1637 for (i = 1; i < orig_loop_num_nodes; i++)
1639 gimple phi;
1640 tree cond = NULL_TREE;
1641 gimple_stmt_iterator gsi, phi_gsi;
1642 basic_block true_bb = NULL;
1643 bb = ifc_bbs[i];
1645 if (bb == loop->header)
1646 continue;
1648 phi_gsi = gsi_start_phis (bb);
1649 if (gsi_end_p (phi_gsi))
1650 continue;
1652 /* BB has two predecessors. Using predecessor's aux field, set
1653 appropriate condition for the PHI node replacement. */
1654 gsi = gsi_after_labels (bb);
1655 true_bb = find_phi_replacement_condition (bb, &cond, &gsi);
1657 while (!gsi_end_p (phi_gsi))
1659 phi = gsi_stmt (phi_gsi);
1660 predicate_scalar_phi (phi, cond, true_bb, &gsi);
1661 release_phi_node (phi);
1662 gsi_next (&phi_gsi);
1665 set_phi_nodes (bb, NULL);
1669 /* Insert in each basic block of LOOP the statements produced by the
1670 gimplification of the predicates. */
1672 static void
1673 insert_gimplified_predicates (loop_p loop, bool any_mask_load_store)
1675 unsigned int i;
1677 for (i = 0; i < loop->num_nodes; i++)
1679 basic_block bb = ifc_bbs[i];
1680 gimple_seq stmts;
1682 if (!is_predicated (bb))
1684 /* Do not insert statements for a basic block that is not
1685 predicated. Also make sure that the predicate of the
1686 basic block is set to true. */
1687 reset_bb_predicate (bb);
1688 continue;
1691 stmts = bb_predicate_gimplified_stmts (bb);
1692 if (stmts)
1694 if (flag_tree_loop_if_convert_stores
1695 || any_mask_load_store)
1697 /* Insert the predicate of the BB just after the label,
1698 as the if-conversion of memory writes will use this
1699 predicate. */
1700 gimple_stmt_iterator gsi = gsi_after_labels (bb);
1701 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1703 else
1705 /* Insert the predicate of the BB at the end of the BB
1706 as this would reduce the register pressure: the only
1707 use of this predicate will be in successor BBs. */
1708 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1710 if (gsi_end_p (gsi)
1711 || stmt_ends_bb_p (gsi_stmt (gsi)))
1712 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1713 else
1714 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
1717 /* Once the sequence is code generated, set it to NULL. */
1718 set_bb_predicate_gimplified_stmts (bb, NULL);
1723 /* Predicate each write to memory in LOOP.
1725 This function transforms control flow constructs containing memory
1726 writes of the form:
1728 | for (i = 0; i < N; i++)
1729 | if (cond)
1730 | A[i] = expr;
1732 into the following form that does not contain control flow:
1734 | for (i = 0; i < N; i++)
1735 | A[i] = cond ? expr : A[i];
1737 The original CFG looks like this:
1739 | bb_0
1740 | i = 0
1741 | end_bb_0
1743 | bb_1
1744 | if (i < N) goto bb_5 else goto bb_2
1745 | end_bb_1
1747 | bb_2
1748 | cond = some_computation;
1749 | if (cond) goto bb_3 else goto bb_4
1750 | end_bb_2
1752 | bb_3
1753 | A[i] = expr;
1754 | goto bb_4
1755 | end_bb_3
1757 | bb_4
1758 | goto bb_1
1759 | end_bb_4
1761 insert_gimplified_predicates inserts the computation of the COND
1762 expression at the beginning of the destination basic block:
1764 | bb_0
1765 | i = 0
1766 | end_bb_0
1768 | bb_1
1769 | if (i < N) goto bb_5 else goto bb_2
1770 | end_bb_1
1772 | bb_2
1773 | cond = some_computation;
1774 | if (cond) goto bb_3 else goto bb_4
1775 | end_bb_2
1777 | bb_3
1778 | cond = some_computation;
1779 | A[i] = expr;
1780 | goto bb_4
1781 | end_bb_3
1783 | bb_4
1784 | goto bb_1
1785 | end_bb_4
1787 predicate_mem_writes is then predicating the memory write as follows:
1789 | bb_0
1790 | i = 0
1791 | end_bb_0
1793 | bb_1
1794 | if (i < N) goto bb_5 else goto bb_2
1795 | end_bb_1
1797 | bb_2
1798 | if (cond) goto bb_3 else goto bb_4
1799 | end_bb_2
1801 | bb_3
1802 | cond = some_computation;
1803 | A[i] = cond ? expr : A[i];
1804 | goto bb_4
1805 | end_bb_3
1807 | bb_4
1808 | goto bb_1
1809 | end_bb_4
1811 and finally combine_blocks removes the basic block boundaries making
1812 the loop vectorizable:
1814 | bb_0
1815 | i = 0
1816 | if (i < N) goto bb_5 else goto bb_1
1817 | end_bb_0
1819 | bb_1
1820 | cond = some_computation;
1821 | A[i] = cond ? expr : A[i];
1822 | if (i < N) goto bb_5 else goto bb_4
1823 | end_bb_1
1825 | bb_4
1826 | goto bb_1
1827 | end_bb_4
1830 static void
1831 predicate_mem_writes (loop_p loop)
1833 unsigned int i, orig_loop_num_nodes = loop->num_nodes;
1835 for (i = 1; i < orig_loop_num_nodes; i++)
1837 gimple_stmt_iterator gsi;
1838 basic_block bb = ifc_bbs[i];
1839 tree cond = bb_predicate (bb);
1840 bool swap;
1841 gimple stmt;
1843 if (is_true_predicate (cond))
1844 continue;
1846 swap = false;
1847 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1849 swap = true;
1850 cond = TREE_OPERAND (cond, 0);
1853 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1854 if (!gimple_assign_single_p (stmt = gsi_stmt (gsi)))
1855 continue;
1856 else if (gimple_plf (stmt, GF_PLF_2))
1858 tree lhs = gimple_assign_lhs (stmt);
1859 tree rhs = gimple_assign_rhs1 (stmt);
1860 tree ref, addr, ptr, masktype, mask_op0, mask_op1, mask;
1861 gimple new_stmt;
1862 int bitsize = GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (lhs)));
1864 masktype = build_nonstandard_integer_type (bitsize, 1);
1865 mask_op0 = build_int_cst (masktype, swap ? 0 : -1);
1866 mask_op1 = build_int_cst (masktype, swap ? -1 : 0);
1867 ref = TREE_CODE (lhs) == SSA_NAME ? rhs : lhs;
1868 mark_addressable (ref);
1869 addr = force_gimple_operand_gsi (&gsi, build_fold_addr_expr (ref),
1870 true, NULL_TREE, true,
1871 GSI_SAME_STMT);
1872 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
1873 is_gimple_condexpr, NULL_TREE,
1874 true, GSI_SAME_STMT);
1875 mask = fold_build_cond_expr (masktype, unshare_expr (cond),
1876 mask_op0, mask_op1);
1877 mask = ifc_temp_var (masktype, mask, &gsi);
1878 ptr = build_int_cst (reference_alias_ptr_type (ref), 0);
1879 /* Copy points-to info if possible. */
1880 if (TREE_CODE (addr) == SSA_NAME && !SSA_NAME_PTR_INFO (addr))
1881 copy_ref_info (build2 (MEM_REF, TREE_TYPE (ref), addr, ptr),
1882 ref);
1883 if (TREE_CODE (lhs) == SSA_NAME)
1885 new_stmt
1886 = gimple_build_call_internal (IFN_MASK_LOAD, 3, addr,
1887 ptr, mask);
1888 gimple_call_set_lhs (new_stmt, lhs);
1890 else
1891 new_stmt
1892 = gimple_build_call_internal (IFN_MASK_STORE, 4, addr, ptr,
1893 mask, rhs);
1894 gsi_replace (&gsi, new_stmt, true);
1896 else if (gimple_vdef (stmt))
1898 tree lhs = gimple_assign_lhs (stmt);
1899 tree rhs = gimple_assign_rhs1 (stmt);
1900 tree type = TREE_TYPE (lhs);
1902 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
1903 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
1904 if (swap)
1906 tree tem = lhs;
1907 lhs = rhs;
1908 rhs = tem;
1910 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
1911 is_gimple_condexpr, NULL_TREE,
1912 true, GSI_SAME_STMT);
1913 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
1914 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
1915 update_stmt (stmt);
1920 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1921 other than the exit and latch of the LOOP. Also resets the
1922 GIMPLE_DEBUG information. */
1924 static void
1925 remove_conditions_and_labels (loop_p loop)
1927 gimple_stmt_iterator gsi;
1928 unsigned int i;
1930 for (i = 0; i < loop->num_nodes; i++)
1932 basic_block bb = ifc_bbs[i];
1934 if (bb_with_exit_edge_p (loop, bb)
1935 || bb == loop->latch)
1936 continue;
1938 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1939 switch (gimple_code (gsi_stmt (gsi)))
1941 case GIMPLE_COND:
1942 case GIMPLE_LABEL:
1943 gsi_remove (&gsi, true);
1944 break;
1946 case GIMPLE_DEBUG:
1947 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
1948 if (gimple_debug_bind_p (gsi_stmt (gsi)))
1950 gimple_debug_bind_reset_value (gsi_stmt (gsi));
1951 update_stmt (gsi_stmt (gsi));
1953 gsi_next (&gsi);
1954 break;
1956 default:
1957 gsi_next (&gsi);
1962 /* Combine all the basic blocks from LOOP into one or two super basic
1963 blocks. Replace PHI nodes with conditional modify expressions. */
1965 static void
1966 combine_blocks (struct loop *loop, bool any_mask_load_store)
1968 basic_block bb, exit_bb, merge_target_bb;
1969 unsigned int orig_loop_num_nodes = loop->num_nodes;
1970 unsigned int i;
1971 edge e;
1972 edge_iterator ei;
1974 predicate_bbs (loop);
1975 remove_conditions_and_labels (loop);
1976 insert_gimplified_predicates (loop, any_mask_load_store);
1977 predicate_all_scalar_phis (loop);
1979 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
1980 predicate_mem_writes (loop);
1982 /* Merge basic blocks: first remove all the edges in the loop,
1983 except for those from the exit block. */
1984 exit_bb = NULL;
1985 for (i = 0; i < orig_loop_num_nodes; i++)
1987 bb = ifc_bbs[i];
1988 free_bb_predicate (bb);
1989 if (bb_with_exit_edge_p (loop, bb))
1991 gcc_assert (exit_bb == NULL);
1992 exit_bb = bb;
1995 gcc_assert (exit_bb != loop->latch);
1997 for (i = 1; i < orig_loop_num_nodes; i++)
1999 bb = ifc_bbs[i];
2001 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
2003 if (e->src == exit_bb)
2004 ei_next (&ei);
2005 else
2006 remove_edge (e);
2010 if (exit_bb != NULL)
2012 if (exit_bb != loop->header)
2014 /* Connect this node to loop header. */
2015 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
2016 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
2019 /* Redirect non-exit edges to loop->latch. */
2020 FOR_EACH_EDGE (e, ei, exit_bb->succs)
2022 if (!loop_exit_edge_p (loop, e))
2023 redirect_edge_and_branch (e, loop->latch);
2025 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
2027 else
2029 /* If the loop does not have an exit, reconnect header and latch. */
2030 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
2031 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
2034 merge_target_bb = loop->header;
2035 for (i = 1; i < orig_loop_num_nodes; i++)
2037 gimple_stmt_iterator gsi;
2038 gimple_stmt_iterator last;
2040 bb = ifc_bbs[i];
2042 if (bb == exit_bb || bb == loop->latch)
2043 continue;
2045 /* Make stmts member of loop->header. */
2046 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2047 gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
2049 /* Update stmt list. */
2050 last = gsi_last_bb (merge_target_bb);
2051 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
2052 set_bb_seq (bb, NULL);
2054 delete_basic_block (bb);
2057 /* If possible, merge loop header to the block with the exit edge.
2058 This reduces the number of basic blocks to two, to please the
2059 vectorizer that handles only loops with two nodes. */
2060 if (exit_bb
2061 && exit_bb != loop->header
2062 && can_merge_blocks_p (loop->header, exit_bb))
2063 merge_blocks (loop->header, exit_bb);
2065 free (ifc_bbs);
2066 ifc_bbs = NULL;
2069 /* Version LOOP before if-converting it, the original loop
2070 will be then if-converted, the new copy of the loop will not,
2071 and the LOOP_VECTORIZED internal call will be guarding which
2072 loop to execute. The vectorizer pass will fold this
2073 internal call into either true or false. */
2075 static bool
2076 version_loop_for_if_conversion (struct loop *loop)
2078 basic_block cond_bb;
2079 tree cond = make_ssa_name (boolean_type_node, NULL);
2080 struct loop *new_loop;
2081 gimple g;
2082 gimple_stmt_iterator gsi;
2084 g = gimple_build_call_internal (IFN_LOOP_VECTORIZED, 2,
2085 build_int_cst (integer_type_node, loop->num),
2086 integer_zero_node);
2087 gimple_call_set_lhs (g, cond);
2089 initialize_original_copy_tables ();
2090 new_loop = loop_version (loop, cond, &cond_bb,
2091 REG_BR_PROB_BASE, REG_BR_PROB_BASE,
2092 REG_BR_PROB_BASE, true);
2093 free_original_copy_tables ();
2094 if (new_loop == NULL)
2095 return false;
2096 new_loop->dont_vectorize = true;
2097 new_loop->force_vectorize = false;
2098 gsi = gsi_last_bb (cond_bb);
2099 gimple_call_set_arg (g, 1, build_int_cst (integer_type_node, new_loop->num));
2100 gsi_insert_before (&gsi, g, GSI_SAME_STMT);
2101 update_ssa (TODO_update_ssa);
2102 return true;
2105 /* If-convert LOOP when it is legal. For the moment this pass has no
2106 profitability analysis. Returns non-zero todo flags when something
2107 changed. */
2109 static unsigned int
2110 tree_if_conversion (struct loop *loop)
2112 unsigned int todo = 0;
2113 ifc_bbs = NULL;
2114 bool any_mask_load_store = false;
2116 if (!if_convertible_loop_p (loop, &any_mask_load_store)
2117 || !dbg_cnt (if_conversion_tree))
2118 goto cleanup;
2120 if (any_mask_load_store
2121 && ((!flag_tree_loop_vectorize && !loop->force_vectorize)
2122 || loop->dont_vectorize))
2123 goto cleanup;
2125 if (any_mask_load_store && !version_loop_for_if_conversion (loop))
2126 goto cleanup;
2128 /* Now all statements are if-convertible. Combine all the basic
2129 blocks into one huge basic block doing the if-conversion
2130 on-the-fly. */
2131 combine_blocks (loop, any_mask_load_store);
2133 todo |= TODO_cleanup_cfg;
2134 if (flag_tree_loop_if_convert_stores || any_mask_load_store)
2136 mark_virtual_operands_for_renaming (cfun);
2137 todo |= TODO_update_ssa_only_virtuals;
2140 cleanup:
2141 if (ifc_bbs)
2143 unsigned int i;
2145 for (i = 0; i < loop->num_nodes; i++)
2146 free_bb_predicate (ifc_bbs[i]);
2148 free (ifc_bbs);
2149 ifc_bbs = NULL;
2152 return todo;
2155 /* Tree if-conversion pass management. */
2157 namespace {
2159 const pass_data pass_data_if_conversion =
2161 GIMPLE_PASS, /* type */
2162 "ifcvt", /* name */
2163 OPTGROUP_NONE, /* optinfo_flags */
2164 TV_NONE, /* tv_id */
2165 ( PROP_cfg | PROP_ssa ), /* properties_required */
2166 0, /* properties_provided */
2167 0, /* properties_destroyed */
2168 0, /* todo_flags_start */
2169 0, /* todo_flags_finish */
2172 class pass_if_conversion : public gimple_opt_pass
2174 public:
2175 pass_if_conversion (gcc::context *ctxt)
2176 : gimple_opt_pass (pass_data_if_conversion, ctxt)
2179 /* opt_pass methods: */
2180 virtual bool gate (function *);
2181 virtual unsigned int execute (function *);
2183 }; // class pass_if_conversion
2185 bool
2186 pass_if_conversion::gate (function *fun)
2188 return (((flag_tree_loop_vectorize || fun->has_force_vectorize_loops)
2189 && flag_tree_loop_if_convert != 0)
2190 || flag_tree_loop_if_convert == 1
2191 || flag_tree_loop_if_convert_stores == 1);
2194 unsigned int
2195 pass_if_conversion::execute (function *fun)
2197 struct loop *loop;
2198 unsigned todo = 0;
2200 if (number_of_loops (fun) <= 1)
2201 return 0;
2203 FOR_EACH_LOOP (loop, 0)
2204 if (flag_tree_loop_if_convert == 1
2205 || flag_tree_loop_if_convert_stores == 1
2206 || ((flag_tree_loop_vectorize || loop->force_vectorize)
2207 && !loop->dont_vectorize))
2208 todo |= tree_if_conversion (loop);
2210 #ifdef ENABLE_CHECKING
2212 basic_block bb;
2213 FOR_EACH_BB_FN (bb, fun)
2214 gcc_assert (!bb->aux);
2216 #endif
2218 return todo;
2221 } // anon namespace
2223 gimple_opt_pass *
2224 make_pass_if_conversion (gcc::context *ctxt)
2226 return new pass_if_conversion (ctxt);