2012-11-28 Oleg Raikhman <oleg@adapteva.com>
[official-gcc.git] / gcc / tree-if-conv.c
blobb7e280483986475bdb59c46996ec2f676a2369ae
1 /* If-conversion for vectorizer.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3 Free Software Foundation, Inc.
4 Contributed by Devang Patel <dpatel@apple.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass implements a tree level if-conversion of loops. Its
23 initial goal is to help the vectorizer to vectorize loops with
24 conditions.
26 A short description of if-conversion:
28 o Decide if a loop is if-convertible or not.
29 o Walk all loop basic blocks in breadth first order (BFS order).
30 o Remove conditional statements (at the end of basic block)
31 and propagate condition into destination basic blocks'
32 predicate list.
33 o Replace modify expression with conditional modify expression
34 using current basic block's condition.
35 o Merge all basic blocks
36 o Replace phi nodes with conditional modify expr
37 o Merge all basic blocks into header
39 Sample transformation:
41 INPUT
42 -----
44 # i_23 = PHI <0(0), i_18(10)>;
45 <L0>:;
46 j_15 = A[i_23];
47 if (j_15 > 41) goto <L1>; else goto <L17>;
49 <L17>:;
50 goto <bb 3> (<L3>);
52 <L1>:;
54 # iftmp.2_4 = PHI <0(8), 42(2)>;
55 <L3>:;
56 A[i_23] = iftmp.2_4;
57 i_18 = i_23 + 1;
58 if (i_18 <= 15) goto <L19>; else goto <L18>;
60 <L19>:;
61 goto <bb 1> (<L0>);
63 <L18>:;
65 OUTPUT
66 ------
68 # i_23 = PHI <0(0), i_18(10)>;
69 <L0>:;
70 j_15 = A[i_23];
72 <L3>:;
73 iftmp.2_4 = j_15 > 41 ? 42 : 0;
74 A[i_23] = iftmp.2_4;
75 i_18 = i_23 + 1;
76 if (i_18 <= 15) goto <L19>; else goto <L18>;
78 <L19>:;
79 goto <bb 1> (<L0>);
81 <L18>:;
84 #include "config.h"
85 #include "system.h"
86 #include "coretypes.h"
87 #include "tm.h"
88 #include "tree.h"
89 #include "flags.h"
90 #include "basic-block.h"
91 #include "gimple-pretty-print.h"
92 #include "tree-flow.h"
93 #include "cfgloop.h"
94 #include "tree-chrec.h"
95 #include "tree-data-ref.h"
96 #include "tree-scalar-evolution.h"
97 #include "tree-pass.h"
98 #include "dbgcnt.h"
100 /* List of basic blocks in if-conversion-suitable order. */
101 static basic_block *ifc_bbs;
103 /* Structure used to predicate basic blocks. This is attached to the
104 ->aux field of the BBs in the loop to be if-converted. */
105 typedef struct bb_predicate_s {
107 /* The condition under which this basic block is executed. */
108 tree predicate;
110 /* PREDICATE is gimplified, and the sequence of statements is
111 recorded here, in order to avoid the duplication of computations
112 that occur in previous conditions. See PR44483. */
113 gimple_seq predicate_gimplified_stmts;
114 } *bb_predicate_p;
116 /* Returns true when the basic block BB has a predicate. */
118 static inline bool
119 bb_has_predicate (basic_block bb)
121 return bb->aux != NULL;
124 /* Returns the gimplified predicate for basic block BB. */
126 static inline tree
127 bb_predicate (basic_block bb)
129 return ((bb_predicate_p) bb->aux)->predicate;
132 /* Sets the gimplified predicate COND for basic block BB. */
134 static inline void
135 set_bb_predicate (basic_block bb, tree cond)
137 gcc_assert ((TREE_CODE (cond) == TRUTH_NOT_EXPR
138 && is_gimple_condexpr (TREE_OPERAND (cond, 0)))
139 || is_gimple_condexpr (cond));
140 ((bb_predicate_p) bb->aux)->predicate = cond;
143 /* Returns the sequence of statements of the gimplification of the
144 predicate for basic block BB. */
146 static inline gimple_seq
147 bb_predicate_gimplified_stmts (basic_block bb)
149 return ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts;
152 /* Sets the sequence of statements STMTS of the gimplification of the
153 predicate for basic block BB. */
155 static inline void
156 set_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
158 ((bb_predicate_p) bb->aux)->predicate_gimplified_stmts = stmts;
161 /* Adds the sequence of statements STMTS to the sequence of statements
162 of the predicate for basic block BB. */
164 static inline void
165 add_bb_predicate_gimplified_stmts (basic_block bb, gimple_seq stmts)
167 gimple_seq_add_seq
168 (&(((bb_predicate_p) bb->aux)->predicate_gimplified_stmts), stmts);
171 /* Initializes to TRUE the predicate of basic block BB. */
173 static inline void
174 init_bb_predicate (basic_block bb)
176 bb->aux = XNEW (struct bb_predicate_s);
177 set_bb_predicate_gimplified_stmts (bb, NULL);
178 set_bb_predicate (bb, boolean_true_node);
181 /* Free the predicate of basic block BB. */
183 static inline void
184 free_bb_predicate (basic_block bb)
186 gimple_seq stmts;
188 if (!bb_has_predicate (bb))
189 return;
191 /* Release the SSA_NAMEs created for the gimplification of the
192 predicate. */
193 stmts = bb_predicate_gimplified_stmts (bb);
194 if (stmts)
196 gimple_stmt_iterator i;
198 for (i = gsi_start (stmts); !gsi_end_p (i); gsi_next (&i))
199 free_stmt_operands (gsi_stmt (i));
202 free (bb->aux);
203 bb->aux = NULL;
206 /* Free the predicate of BB and reinitialize it with the true
207 predicate. */
209 static inline void
210 reset_bb_predicate (basic_block bb)
212 free_bb_predicate (bb);
213 init_bb_predicate (bb);
216 /* Returns a new SSA_NAME of type TYPE that is assigned the value of
217 the expression EXPR. Inserts the statement created for this
218 computation before GSI and leaves the iterator GSI at the same
219 statement. */
221 static tree
222 ifc_temp_var (tree type, tree expr, gimple_stmt_iterator *gsi)
224 tree new_name = make_temp_ssa_name (type, NULL, "_ifc_");
225 gimple stmt = gimple_build_assign (new_name, expr);
226 gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
227 return new_name;
230 /* Return true when COND is a true predicate. */
232 static inline bool
233 is_true_predicate (tree cond)
235 return (cond == NULL_TREE
236 || cond == boolean_true_node
237 || integer_onep (cond));
240 /* Returns true when BB has a predicate that is not trivial: true or
241 NULL_TREE. */
243 static inline bool
244 is_predicated (basic_block bb)
246 return !is_true_predicate (bb_predicate (bb));
249 /* Parses the predicate COND and returns its comparison code and
250 operands OP0 and OP1. */
252 static enum tree_code
253 parse_predicate (tree cond, tree *op0, tree *op1)
255 gimple s;
257 if (TREE_CODE (cond) == SSA_NAME
258 && is_gimple_assign (s = SSA_NAME_DEF_STMT (cond)))
260 if (TREE_CODE_CLASS (gimple_assign_rhs_code (s)) == tcc_comparison)
262 *op0 = gimple_assign_rhs1 (s);
263 *op1 = gimple_assign_rhs2 (s);
264 return gimple_assign_rhs_code (s);
267 else if (gimple_assign_rhs_code (s) == TRUTH_NOT_EXPR)
269 tree op = gimple_assign_rhs1 (s);
270 tree type = TREE_TYPE (op);
271 enum tree_code code = parse_predicate (op, op0, op1);
273 return code == ERROR_MARK ? ERROR_MARK
274 : invert_tree_comparison (code, HONOR_NANS (TYPE_MODE (type)));
277 return ERROR_MARK;
280 if (TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison)
282 *op0 = TREE_OPERAND (cond, 0);
283 *op1 = TREE_OPERAND (cond, 1);
284 return TREE_CODE (cond);
287 return ERROR_MARK;
290 /* Returns the fold of predicate C1 OR C2 at location LOC. */
292 static tree
293 fold_or_predicates (location_t loc, tree c1, tree c2)
295 tree op1a, op1b, op2a, op2b;
296 enum tree_code code1 = parse_predicate (c1, &op1a, &op1b);
297 enum tree_code code2 = parse_predicate (c2, &op2a, &op2b);
299 if (code1 != ERROR_MARK && code2 != ERROR_MARK)
301 tree t = maybe_fold_or_comparisons (code1, op1a, op1b,
302 code2, op2a, op2b);
303 if (t)
304 return t;
307 return fold_build2_loc (loc, TRUTH_OR_EXPR, boolean_type_node, c1, c2);
310 /* Returns true if N is either a constant or a SSA_NAME. */
312 static bool
313 constant_or_ssa_name (tree n)
315 switch (TREE_CODE (n))
317 case SSA_NAME:
318 case INTEGER_CST:
319 case REAL_CST:
320 case COMPLEX_CST:
321 case VECTOR_CST:
322 return true;
323 default:
324 return false;
328 /* Returns either a COND_EXPR or the folded expression if the folded
329 expression is a MIN_EXPR, a MAX_EXPR, an ABS_EXPR,
330 a constant or a SSA_NAME. */
332 static tree
333 fold_build_cond_expr (tree type, tree cond, tree rhs, tree lhs)
335 tree rhs1, lhs1, cond_expr;
336 cond_expr = fold_ternary (COND_EXPR, type, cond,
337 rhs, lhs);
339 if (cond_expr == NULL_TREE)
340 return build3 (COND_EXPR, type, cond, rhs, lhs);
342 STRIP_USELESS_TYPE_CONVERSION (cond_expr);
344 if (constant_or_ssa_name (cond_expr))
345 return cond_expr;
347 if (TREE_CODE (cond_expr) == ABS_EXPR)
349 rhs1 = TREE_OPERAND (cond_expr, 1);
350 STRIP_USELESS_TYPE_CONVERSION (rhs1);
351 if (constant_or_ssa_name (rhs1))
352 return build1 (ABS_EXPR, type, rhs1);
355 if (TREE_CODE (cond_expr) == MIN_EXPR
356 || TREE_CODE (cond_expr) == MAX_EXPR)
358 lhs1 = TREE_OPERAND (cond_expr, 0);
359 STRIP_USELESS_TYPE_CONVERSION (lhs1);
360 rhs1 = TREE_OPERAND (cond_expr, 1);
361 STRIP_USELESS_TYPE_CONVERSION (rhs1);
362 if (constant_or_ssa_name (rhs1)
363 && constant_or_ssa_name (lhs1))
364 return build2 (TREE_CODE (cond_expr), type, lhs1, rhs1);
366 return build3 (COND_EXPR, type, cond, rhs, lhs);
369 /* Add condition NC to the predicate list of basic block BB. */
371 static inline void
372 add_to_predicate_list (basic_block bb, tree nc)
374 tree bc, *tp;
376 if (is_true_predicate (nc))
377 return;
379 if (!is_predicated (bb))
380 bc = nc;
381 else
383 bc = bb_predicate (bb);
384 bc = fold_or_predicates (EXPR_LOCATION (bc), nc, bc);
385 if (is_true_predicate (bc))
387 reset_bb_predicate (bb);
388 return;
392 /* Allow a TRUTH_NOT_EXPR around the main predicate. */
393 if (TREE_CODE (bc) == TRUTH_NOT_EXPR)
394 tp = &TREE_OPERAND (bc, 0);
395 else
396 tp = &bc;
397 if (!is_gimple_condexpr (*tp))
399 gimple_seq stmts;
400 *tp = force_gimple_operand_1 (*tp, &stmts, is_gimple_condexpr, NULL_TREE);
401 add_bb_predicate_gimplified_stmts (bb, stmts);
403 set_bb_predicate (bb, bc);
406 /* Add the condition COND to the previous condition PREV_COND, and add
407 this to the predicate list of the destination of edge E. LOOP is
408 the loop to be if-converted. */
410 static void
411 add_to_dst_predicate_list (struct loop *loop, edge e,
412 tree prev_cond, tree cond)
414 if (!flow_bb_inside_loop_p (loop, e->dest))
415 return;
417 if (!is_true_predicate (prev_cond))
418 cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
419 prev_cond, cond);
421 add_to_predicate_list (e->dest, cond);
424 /* Return true if one of the successor edges of BB exits LOOP. */
426 static bool
427 bb_with_exit_edge_p (struct loop *loop, basic_block bb)
429 edge e;
430 edge_iterator ei;
432 FOR_EACH_EDGE (e, ei, bb->succs)
433 if (loop_exit_edge_p (loop, e))
434 return true;
436 return false;
439 /* Return true when PHI is if-convertible. PHI is part of loop LOOP
440 and it belongs to basic block BB.
442 PHI is not if-convertible if:
443 - it has more than 2 arguments.
445 When the flag_tree_loop_if_convert_stores is not set, PHI is not
446 if-convertible if:
447 - a virtual PHI is immediately used in another PHI node,
448 - there is a virtual PHI in a BB other than the loop->header. */
450 static bool
451 if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
453 if (dump_file && (dump_flags & TDF_DETAILS))
455 fprintf (dump_file, "-------------------------\n");
456 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
459 if (bb != loop->header && gimple_phi_num_args (phi) != 2)
461 if (dump_file && (dump_flags & TDF_DETAILS))
462 fprintf (dump_file, "More than two phi node args.\n");
463 return false;
466 if (flag_tree_loop_if_convert_stores)
467 return true;
469 /* When the flag_tree_loop_if_convert_stores is not set, check
470 that there are no memory writes in the branches of the loop to be
471 if-converted. */
472 if (virtual_operand_p (gimple_phi_result (phi)))
474 imm_use_iterator imm_iter;
475 use_operand_p use_p;
477 if (bb != loop->header)
479 if (dump_file && (dump_flags & TDF_DETAILS))
480 fprintf (dump_file, "Virtual phi not on loop->header.\n");
481 return false;
484 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (phi))
486 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI)
488 if (dump_file && (dump_flags & TDF_DETAILS))
489 fprintf (dump_file, "Difficult to handle this virtual phi.\n");
490 return false;
495 return true;
498 /* Records the status of a data reference. This struct is attached to
499 each DR->aux field. */
501 struct ifc_dr {
502 /* -1 when not initialized, 0 when false, 1 when true. */
503 int written_at_least_once;
505 /* -1 when not initialized, 0 when false, 1 when true. */
506 int rw_unconditionally;
509 #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux)
510 #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once)
511 #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally)
513 /* Returns true when the memory references of STMT are read or written
514 unconditionally. In other words, this function returns true when
515 for every data reference A in STMT there exist other accesses to
516 a data reference with the same base with predicates that add up (OR-up) to
517 the true predicate: this ensures that the data reference A is touched
518 (read or written) on every iteration of the if-converted loop. */
520 static bool
521 memrefs_read_or_written_unconditionally (gimple stmt,
522 vec<data_reference_p> drs)
524 int i, j;
525 data_reference_p a, b;
526 tree ca = bb_predicate (gimple_bb (stmt));
528 for (i = 0; drs.iterate (i, &a); i++)
529 if (DR_STMT (a) == stmt)
531 bool found = false;
532 int x = DR_RW_UNCONDITIONALLY (a);
534 if (x == 0)
535 return false;
537 if (x == 1)
538 continue;
540 for (j = 0; drs.iterate (j, &b); j++)
542 tree ref_base_a = DR_REF (a);
543 tree ref_base_b = DR_REF (b);
545 if (DR_STMT (b) == stmt)
546 continue;
548 while (TREE_CODE (ref_base_a) == COMPONENT_REF
549 || TREE_CODE (ref_base_a) == IMAGPART_EXPR
550 || TREE_CODE (ref_base_a) == REALPART_EXPR)
551 ref_base_a = TREE_OPERAND (ref_base_a, 0);
553 while (TREE_CODE (ref_base_b) == COMPONENT_REF
554 || TREE_CODE (ref_base_b) == IMAGPART_EXPR
555 || TREE_CODE (ref_base_b) == REALPART_EXPR)
556 ref_base_b = TREE_OPERAND (ref_base_b, 0);
558 if (!operand_equal_p (ref_base_a, ref_base_b, 0))
560 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
562 if (DR_RW_UNCONDITIONALLY (b) == 1
563 || is_true_predicate (cb)
564 || is_true_predicate (ca
565 = fold_or_predicates (EXPR_LOCATION (cb), ca, cb)))
567 DR_RW_UNCONDITIONALLY (a) = 1;
568 DR_RW_UNCONDITIONALLY (b) = 1;
569 found = true;
570 break;
575 if (!found)
577 DR_RW_UNCONDITIONALLY (a) = 0;
578 return false;
582 return true;
585 /* Returns true when the memory references of STMT are unconditionally
586 written. In other words, this function returns true when for every
587 data reference A written in STMT, there exist other writes to the
588 same data reference with predicates that add up (OR-up) to the true
589 predicate: this ensures that the data reference A is written on
590 every iteration of the if-converted loop. */
592 static bool
593 write_memrefs_written_at_least_once (gimple stmt,
594 vec<data_reference_p> drs)
596 int i, j;
597 data_reference_p a, b;
598 tree ca = bb_predicate (gimple_bb (stmt));
600 for (i = 0; drs.iterate (i, &a); i++)
601 if (DR_STMT (a) == stmt
602 && DR_IS_WRITE (a))
604 bool found = false;
605 int x = DR_WRITTEN_AT_LEAST_ONCE (a);
607 if (x == 0)
608 return false;
610 if (x == 1)
611 continue;
613 for (j = 0; drs.iterate (j, &b); j++)
614 if (DR_STMT (b) != stmt
615 && DR_IS_WRITE (b)
616 && same_data_refs_base_objects (a, b))
618 tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
620 if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1
621 || is_true_predicate (cb)
622 || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
623 ca, cb)))
625 DR_WRITTEN_AT_LEAST_ONCE (a) = 1;
626 DR_WRITTEN_AT_LEAST_ONCE (b) = 1;
627 found = true;
628 break;
632 if (!found)
634 DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
635 return false;
639 return true;
642 /* Return true when the memory references of STMT won't trap in the
643 if-converted code. There are two things that we have to check for:
645 - writes to memory occur to writable memory: if-conversion of
646 memory writes transforms the conditional memory writes into
647 unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
648 into "A[i] = cond ? foo : A[i]", and as the write to memory may not
649 be executed at all in the original code, it may be a readonly
650 memory. To check that A is not const-qualified, we check that
651 there exists at least an unconditional write to A in the current
652 function.
654 - reads or writes to memory are valid memory accesses for every
655 iteration. To check that the memory accesses are correctly formed
656 and that we are allowed to read and write in these locations, we
657 check that the memory accesses to be if-converted occur at every
658 iteration unconditionally. */
660 static bool
661 ifcvt_memrefs_wont_trap (gimple stmt, vec<data_reference_p> refs)
663 return write_memrefs_written_at_least_once (stmt, refs)
664 && memrefs_read_or_written_unconditionally (stmt, refs);
667 /* Wrapper around gimple_could_trap_p refined for the needs of the
668 if-conversion. Try to prove that the memory accesses of STMT could
669 not trap in the innermost loop containing STMT. */
671 static bool
672 ifcvt_could_trap_p (gimple stmt, vec<data_reference_p> refs)
674 if (gimple_vuse (stmt)
675 && !gimple_could_trap_p_1 (stmt, false, false)
676 && ifcvt_memrefs_wont_trap (stmt, refs))
677 return false;
679 return gimple_could_trap_p (stmt);
682 /* Return true when STMT is if-convertible.
684 GIMPLE_ASSIGN statement is not if-convertible if,
685 - it is not movable,
686 - it could trap,
687 - LHS is not var decl. */
689 static bool
690 if_convertible_gimple_assign_stmt_p (gimple stmt,
691 vec<data_reference_p> refs)
693 tree lhs = gimple_assign_lhs (stmt);
694 basic_block bb;
696 if (dump_file && (dump_flags & TDF_DETAILS))
698 fprintf (dump_file, "-------------------------\n");
699 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
702 if (!is_gimple_reg_type (TREE_TYPE (lhs)))
703 return false;
705 /* Some of these constrains might be too conservative. */
706 if (stmt_ends_bb_p (stmt)
707 || gimple_has_volatile_ops (stmt)
708 || (TREE_CODE (lhs) == SSA_NAME
709 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
710 || gimple_has_side_effects (stmt))
712 if (dump_file && (dump_flags & TDF_DETAILS))
713 fprintf (dump_file, "stmt not suitable for ifcvt\n");
714 return false;
717 if (flag_tree_loop_if_convert_stores)
719 if (ifcvt_could_trap_p (stmt, refs))
721 if (dump_file && (dump_flags & TDF_DETAILS))
722 fprintf (dump_file, "tree could trap...\n");
723 return false;
725 return true;
728 if (gimple_assign_rhs_could_trap_p (stmt))
730 if (dump_file && (dump_flags & TDF_DETAILS))
731 fprintf (dump_file, "tree could trap...\n");
732 return false;
735 bb = gimple_bb (stmt);
737 if (TREE_CODE (lhs) != SSA_NAME
738 && bb != bb->loop_father->header
739 && !bb_with_exit_edge_p (bb->loop_father, bb))
741 if (dump_file && (dump_flags & TDF_DETAILS))
743 fprintf (dump_file, "LHS is not var\n");
744 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
746 return false;
749 return true;
752 /* Return true when STMT is if-convertible.
754 A statement is if-convertible if:
755 - it is an if-convertible GIMPLE_ASSIGN,
756 - it is a GIMPLE_LABEL or a GIMPLE_COND. */
758 static bool
759 if_convertible_stmt_p (gimple stmt, vec<data_reference_p> refs)
761 switch (gimple_code (stmt))
763 case GIMPLE_LABEL:
764 case GIMPLE_DEBUG:
765 case GIMPLE_COND:
766 return true;
768 case GIMPLE_ASSIGN:
769 return if_convertible_gimple_assign_stmt_p (stmt, refs);
771 case GIMPLE_CALL:
773 tree fndecl = gimple_call_fndecl (stmt);
774 if (fndecl)
776 int flags = gimple_call_flags (stmt);
777 if ((flags & ECF_CONST)
778 && !(flags & ECF_LOOPING_CONST_OR_PURE)
779 /* We can only vectorize some builtins at the moment,
780 so restrict if-conversion to those. */
781 && DECL_BUILT_IN (fndecl))
782 return true;
784 return false;
787 default:
788 /* Don't know what to do with 'em so don't do anything. */
789 if (dump_file && (dump_flags & TDF_DETAILS))
791 fprintf (dump_file, "don't know what to do\n");
792 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
794 return false;
795 break;
798 return true;
801 /* Return true when BB post-dominates all its predecessors. */
803 static bool
804 bb_postdominates_preds (basic_block bb)
806 unsigned i;
808 for (i = 0; i < EDGE_COUNT (bb->preds); i++)
809 if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb))
810 return false;
812 return true;
815 /* Return true when BB is if-convertible. This routine does not check
816 basic block's statements and phis.
818 A basic block is not if-convertible if:
819 - it is non-empty and it is after the exit block (in BFS order),
820 - it is after the exit block but before the latch,
821 - its edges are not normal.
823 EXIT_BB is the basic block containing the exit of the LOOP. BB is
824 inside LOOP. */
826 static bool
827 if_convertible_bb_p (struct loop *loop, basic_block bb, basic_block exit_bb)
829 edge e;
830 edge_iterator ei;
832 if (dump_file && (dump_flags & TDF_DETAILS))
833 fprintf (dump_file, "----------[%d]-------------\n", bb->index);
835 if (EDGE_COUNT (bb->preds) > 2
836 || EDGE_COUNT (bb->succs) > 2)
837 return false;
839 if (exit_bb)
841 if (bb != loop->latch)
843 if (dump_file && (dump_flags & TDF_DETAILS))
844 fprintf (dump_file, "basic block after exit bb but before latch\n");
845 return false;
847 else if (!empty_block_p (bb))
849 if (dump_file && (dump_flags & TDF_DETAILS))
850 fprintf (dump_file, "non empty basic block after exit bb\n");
851 return false;
853 else if (bb == loop->latch
854 && bb != exit_bb
855 && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
857 if (dump_file && (dump_flags & TDF_DETAILS))
858 fprintf (dump_file, "latch is not dominated by exit_block\n");
859 return false;
863 /* Be less adventurous and handle only normal edges. */
864 FOR_EACH_EDGE (e, ei, bb->succs)
865 if (e->flags & (EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
867 if (dump_file && (dump_flags & TDF_DETAILS))
868 fprintf (dump_file, "Difficult to handle edges\n");
869 return false;
872 if (EDGE_COUNT (bb->preds) == 2
873 && bb != loop->header
874 && !bb_postdominates_preds (bb))
875 return false;
877 return true;
880 /* Return true when all predecessor blocks of BB are visited. The
881 VISITED bitmap keeps track of the visited blocks. */
883 static bool
884 pred_blocks_visited_p (basic_block bb, bitmap *visited)
886 edge e;
887 edge_iterator ei;
888 FOR_EACH_EDGE (e, ei, bb->preds)
889 if (!bitmap_bit_p (*visited, e->src->index))
890 return false;
892 return true;
895 /* Get body of a LOOP in suitable order for if-conversion. It is
896 caller's responsibility to deallocate basic block list.
897 If-conversion suitable order is, breadth first sort (BFS) order
898 with an additional constraint: select a block only if all its
899 predecessors are already selected. */
901 static basic_block *
902 get_loop_body_in_if_conv_order (const struct loop *loop)
904 basic_block *blocks, *blocks_in_bfs_order;
905 basic_block bb;
906 bitmap visited;
907 unsigned int index = 0;
908 unsigned int visited_count = 0;
910 gcc_assert (loop->num_nodes);
911 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
913 blocks = XCNEWVEC (basic_block, loop->num_nodes);
914 visited = BITMAP_ALLOC (NULL);
916 blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
918 index = 0;
919 while (index < loop->num_nodes)
921 bb = blocks_in_bfs_order [index];
923 if (bb->flags & BB_IRREDUCIBLE_LOOP)
925 free (blocks_in_bfs_order);
926 BITMAP_FREE (visited);
927 free (blocks);
928 return NULL;
931 if (!bitmap_bit_p (visited, bb->index))
933 if (pred_blocks_visited_p (bb, &visited)
934 || bb == loop->header)
936 /* This block is now visited. */
937 bitmap_set_bit (visited, bb->index);
938 blocks[visited_count++] = bb;
942 index++;
944 if (index == loop->num_nodes
945 && visited_count != loop->num_nodes)
946 /* Not done yet. */
947 index = 0;
949 free (blocks_in_bfs_order);
950 BITMAP_FREE (visited);
951 return blocks;
954 /* Returns true when the analysis of the predicates for all the basic
955 blocks in LOOP succeeded.
957 predicate_bbs first allocates the predicates of the basic blocks.
958 These fields are then initialized with the tree expressions
959 representing the predicates under which a basic block is executed
960 in the LOOP. As the loop->header is executed at each iteration, it
961 has the "true" predicate. Other statements executed under a
962 condition are predicated with that condition, for example
964 | if (x)
965 | S1;
966 | else
967 | S2;
969 S1 will be predicated with "x", and
970 S2 will be predicated with "!x". */
972 static bool
973 predicate_bbs (loop_p loop)
975 unsigned int i;
977 for (i = 0; i < loop->num_nodes; i++)
978 init_bb_predicate (ifc_bbs[i]);
980 for (i = 0; i < loop->num_nodes; i++)
982 basic_block bb = ifc_bbs[i];
983 tree cond;
984 gimple_stmt_iterator itr;
986 /* The loop latch is always executed and has no extra conditions
987 to be processed: skip it. */
988 if (bb == loop->latch)
990 reset_bb_predicate (loop->latch);
991 continue;
994 cond = bb_predicate (bb);
996 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
998 gimple stmt = gsi_stmt (itr);
1000 switch (gimple_code (stmt))
1002 case GIMPLE_LABEL:
1003 case GIMPLE_ASSIGN:
1004 case GIMPLE_CALL:
1005 case GIMPLE_DEBUG:
1006 break;
1008 case GIMPLE_COND:
1010 tree c2;
1011 edge true_edge, false_edge;
1012 location_t loc = gimple_location (stmt);
1013 tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
1014 boolean_type_node,
1015 gimple_cond_lhs (stmt),
1016 gimple_cond_rhs (stmt));
1018 /* Add new condition into destination's predicate list. */
1019 extract_true_false_edges_from_block (gimple_bb (stmt),
1020 &true_edge, &false_edge);
1022 /* If C is true, then TRUE_EDGE is taken. */
1023 add_to_dst_predicate_list (loop, true_edge,
1024 unshare_expr (cond),
1025 unshare_expr (c));
1027 /* If C is false, then FALSE_EDGE is taken. */
1028 c2 = build1_loc (loc, TRUTH_NOT_EXPR,
1029 boolean_type_node, unshare_expr (c));
1030 add_to_dst_predicate_list (loop, false_edge,
1031 unshare_expr (cond), c2);
1033 cond = NULL_TREE;
1034 break;
1037 default:
1038 /* Not handled yet in if-conversion. */
1039 return false;
1043 /* If current bb has only one successor, then consider it as an
1044 unconditional goto. */
1045 if (single_succ_p (bb))
1047 basic_block bb_n = single_succ (bb);
1049 /* The successor bb inherits the predicate of its
1050 predecessor. If there is no predicate in the predecessor
1051 bb, then consider the successor bb as always executed. */
1052 if (cond == NULL_TREE)
1053 cond = boolean_true_node;
1055 add_to_predicate_list (bb_n, cond);
1059 /* The loop header is always executed. */
1060 reset_bb_predicate (loop->header);
1061 gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
1062 && bb_predicate_gimplified_stmts (loop->latch) == NULL);
1064 return true;
1067 /* Return true when LOOP is if-convertible. This is a helper function
1068 for if_convertible_loop_p. REFS and DDRS are initialized and freed
1069 in if_convertible_loop_p. */
1071 static bool
1072 if_convertible_loop_p_1 (struct loop *loop,
1073 vec<loop_p> *loop_nest,
1074 vec<data_reference_p> *refs,
1075 vec<ddr_p> *ddrs)
1077 bool res;
1078 unsigned int i;
1079 basic_block exit_bb = NULL;
1081 /* Don't if-convert the loop when the data dependences cannot be
1082 computed: the loop won't be vectorized in that case. */
1083 res = compute_data_dependences_for_loop (loop, true, loop_nest, refs, ddrs);
1084 if (!res)
1085 return false;
1087 calculate_dominance_info (CDI_DOMINATORS);
1088 calculate_dominance_info (CDI_POST_DOMINATORS);
1090 /* Allow statements that can be handled during if-conversion. */
1091 ifc_bbs = get_loop_body_in_if_conv_order (loop);
1092 if (!ifc_bbs)
1094 if (dump_file && (dump_flags & TDF_DETAILS))
1095 fprintf (dump_file, "Irreducible loop\n");
1096 return false;
1099 for (i = 0; i < loop->num_nodes; i++)
1101 basic_block bb = ifc_bbs[i];
1103 if (!if_convertible_bb_p (loop, bb, exit_bb))
1104 return false;
1106 if (bb_with_exit_edge_p (loop, bb))
1107 exit_bb = bb;
1110 res = predicate_bbs (loop);
1111 if (!res)
1112 return false;
1114 if (flag_tree_loop_if_convert_stores)
1116 data_reference_p dr;
1118 for (i = 0; refs->iterate (i, &dr); i++)
1120 dr->aux = XNEW (struct ifc_dr);
1121 DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
1122 DR_RW_UNCONDITIONALLY (dr) = -1;
1126 for (i = 0; i < loop->num_nodes; i++)
1128 basic_block bb = ifc_bbs[i];
1129 gimple_stmt_iterator itr;
1131 for (itr = gsi_start_phis (bb); !gsi_end_p (itr); gsi_next (&itr))
1132 if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
1133 return false;
1135 /* Check the if-convertibility of statements in predicated BBs. */
1136 if (is_predicated (bb))
1137 for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
1138 if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
1139 return false;
1142 if (dump_file)
1143 fprintf (dump_file, "Applying if-conversion\n");
1145 return true;
1148 /* Return true when LOOP is if-convertible.
1149 LOOP is if-convertible if:
1150 - it is innermost,
1151 - it has two or more basic blocks,
1152 - it has only one exit,
1153 - loop header is not the exit edge,
1154 - if its basic blocks and phi nodes are if convertible. */
1156 static bool
1157 if_convertible_loop_p (struct loop *loop)
1159 edge e;
1160 edge_iterator ei;
1161 bool res = false;
1162 vec<data_reference_p> refs;
1163 vec<ddr_p> ddrs;
1164 vec<loop_p> loop_nest;
1166 /* Handle only innermost loop. */
1167 if (!loop || loop->inner)
1169 if (dump_file && (dump_flags & TDF_DETAILS))
1170 fprintf (dump_file, "not innermost loop\n");
1171 return false;
1174 /* If only one block, no need for if-conversion. */
1175 if (loop->num_nodes <= 2)
1177 if (dump_file && (dump_flags & TDF_DETAILS))
1178 fprintf (dump_file, "less than 2 basic blocks\n");
1179 return false;
1182 /* More than one loop exit is too much to handle. */
1183 if (!single_exit (loop))
1185 if (dump_file && (dump_flags & TDF_DETAILS))
1186 fprintf (dump_file, "multiple exits\n");
1187 return false;
1190 /* If one of the loop header's edge is an exit edge then do not
1191 apply if-conversion. */
1192 FOR_EACH_EDGE (e, ei, loop->header->succs)
1193 if (loop_exit_edge_p (loop, e))
1194 return false;
1196 refs.create (5);
1197 ddrs.create (25);
1198 loop_nest.create (3);
1199 res = if_convertible_loop_p_1 (loop, &loop_nest, &refs, &ddrs);
1201 if (flag_tree_loop_if_convert_stores)
1203 data_reference_p dr;
1204 unsigned int i;
1206 for (i = 0; refs.iterate (i, &dr); i++)
1207 free (dr->aux);
1210 loop_nest.release ();
1211 free_data_refs (refs);
1212 free_dependence_relations (ddrs);
1213 return res;
1216 /* Basic block BB has two predecessors. Using predecessor's bb
1217 predicate, set an appropriate condition COND for the PHI node
1218 replacement. Return the true block whose phi arguments are
1219 selected when cond is true. LOOP is the loop containing the
1220 if-converted region, GSI is the place to insert the code for the
1221 if-conversion. */
1223 static basic_block
1224 find_phi_replacement_condition (struct loop *loop,
1225 basic_block bb, tree *cond,
1226 gimple_stmt_iterator *gsi)
1228 edge first_edge, second_edge;
1229 tree tmp_cond;
1231 gcc_assert (EDGE_COUNT (bb->preds) == 2);
1232 first_edge = EDGE_PRED (bb, 0);
1233 second_edge = EDGE_PRED (bb, 1);
1235 /* Use condition based on following criteria:
1237 S1: x = !c ? a : b;
1239 S2: x = c ? b : a;
1241 S2 is preferred over S1. Make 'b' first_bb and use its condition.
1243 2) Do not make loop header first_bb.
1246 S1: x = !(c == d)? a : b;
1248 S21: t1 = c == d;
1249 S22: x = t1 ? b : a;
1251 S3: x = (c == d) ? b : a;
1253 S3 is preferred over S1 and S2*, Make 'b' first_bb and use
1254 its condition.
1256 4) If pred B is dominated by pred A then use pred B's condition.
1257 See PR23115. */
1259 /* Select condition that is not TRUTH_NOT_EXPR. */
1260 tmp_cond = bb_predicate (first_edge->src);
1261 gcc_assert (tmp_cond);
1263 if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
1265 edge tmp_edge;
1267 tmp_edge = first_edge;
1268 first_edge = second_edge;
1269 second_edge = tmp_edge;
1272 /* Check if FIRST_BB is loop header or not and make sure that
1273 FIRST_BB does not dominate SECOND_BB. */
1274 if (first_edge->src == loop->header
1275 || dominated_by_p (CDI_DOMINATORS,
1276 second_edge->src, first_edge->src))
1278 *cond = bb_predicate (second_edge->src);
1280 if (TREE_CODE (*cond) == TRUTH_NOT_EXPR)
1281 *cond = TREE_OPERAND (*cond, 0);
1282 else
1283 /* Select non loop header bb. */
1284 first_edge = second_edge;
1286 else
1287 *cond = bb_predicate (first_edge->src);
1289 /* Gimplify the condition to a valid cond-expr conditonal operand. */
1290 *cond = force_gimple_operand_gsi_1 (gsi, unshare_expr (*cond),
1291 is_gimple_condexpr, NULL_TREE,
1292 true, GSI_SAME_STMT);
1294 return first_edge->src;
1297 /* Replace a scalar PHI node with a COND_EXPR using COND as condition.
1298 This routine does not handle PHI nodes with more than two
1299 arguments.
1301 For example,
1302 S1: A = PHI <x1(1), x2(5)>
1303 is converted into,
1304 S2: A = cond ? x1 : x2;
1306 The generated code is inserted at GSI that points to the top of
1307 basic block's statement list. When COND is true, phi arg from
1308 TRUE_BB is selected. */
1310 static void
1311 predicate_scalar_phi (gimple phi, tree cond,
1312 basic_block true_bb,
1313 gimple_stmt_iterator *gsi)
1315 gimple new_stmt;
1316 basic_block bb;
1317 tree rhs, res, arg, scev;
1319 gcc_assert (gimple_code (phi) == GIMPLE_PHI
1320 && gimple_phi_num_args (phi) == 2);
1322 res = gimple_phi_result (phi);
1323 /* Do not handle virtual phi nodes. */
1324 if (virtual_operand_p (res))
1325 return;
1327 bb = gimple_bb (phi);
1329 if ((arg = degenerate_phi_result (phi))
1330 || ((scev = analyze_scalar_evolution (gimple_bb (phi)->loop_father,
1331 res))
1332 && !chrec_contains_undetermined (scev)
1333 && scev != res
1334 && (arg = gimple_phi_arg_def (phi, 0))))
1335 rhs = arg;
1336 else
1338 tree arg_0, arg_1;
1339 /* Use condition that is not TRUTH_NOT_EXPR in conditional modify expr. */
1340 if (EDGE_PRED (bb, 1)->src == true_bb)
1342 arg_0 = gimple_phi_arg_def (phi, 1);
1343 arg_1 = gimple_phi_arg_def (phi, 0);
1345 else
1347 arg_0 = gimple_phi_arg_def (phi, 0);
1348 arg_1 = gimple_phi_arg_def (phi, 1);
1351 gcc_checking_assert (bb == bb->loop_father->header
1352 || bb_postdominates_preds (bb));
1354 /* Build new RHS using selected condition and arguments. */
1355 rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
1356 arg_0, arg_1);
1359 new_stmt = gimple_build_assign (res, rhs);
1360 SSA_NAME_DEF_STMT (gimple_phi_result (phi)) = new_stmt;
1361 gsi_insert_before (gsi, new_stmt, GSI_SAME_STMT);
1362 update_stmt (new_stmt);
1364 if (dump_file && (dump_flags & TDF_DETAILS))
1366 fprintf (dump_file, "new phi replacement stmt\n");
1367 print_gimple_stmt (dump_file, new_stmt, 0, TDF_SLIM);
1371 /* Replaces in LOOP all the scalar phi nodes other than those in the
1372 LOOP->header block with conditional modify expressions. */
1374 static void
1375 predicate_all_scalar_phis (struct loop *loop)
1377 basic_block bb;
1378 unsigned int orig_loop_num_nodes = loop->num_nodes;
1379 unsigned int i;
1381 for (i = 1; i < orig_loop_num_nodes; i++)
1383 gimple phi;
1384 tree cond = NULL_TREE;
1385 gimple_stmt_iterator gsi, phi_gsi;
1386 basic_block true_bb = NULL;
1387 bb = ifc_bbs[i];
1389 if (bb == loop->header)
1390 continue;
1392 phi_gsi = gsi_start_phis (bb);
1393 if (gsi_end_p (phi_gsi))
1394 continue;
1396 /* BB has two predecessors. Using predecessor's aux field, set
1397 appropriate condition for the PHI node replacement. */
1398 gsi = gsi_after_labels (bb);
1399 true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
1401 while (!gsi_end_p (phi_gsi))
1403 phi = gsi_stmt (phi_gsi);
1404 predicate_scalar_phi (phi, cond, true_bb, &gsi);
1405 release_phi_node (phi);
1406 gsi_next (&phi_gsi);
1409 set_phi_nodes (bb, NULL);
1413 /* Insert in each basic block of LOOP the statements produced by the
1414 gimplification of the predicates. */
1416 static void
1417 insert_gimplified_predicates (loop_p loop)
1419 unsigned int i;
1421 for (i = 0; i < loop->num_nodes; i++)
1423 basic_block bb = ifc_bbs[i];
1424 gimple_seq stmts;
1426 if (!is_predicated (bb))
1428 /* Do not insert statements for a basic block that is not
1429 predicated. Also make sure that the predicate of the
1430 basic block is set to true. */
1431 reset_bb_predicate (bb);
1432 continue;
1435 stmts = bb_predicate_gimplified_stmts (bb);
1436 if (stmts)
1438 if (flag_tree_loop_if_convert_stores)
1440 /* Insert the predicate of the BB just after the label,
1441 as the if-conversion of memory writes will use this
1442 predicate. */
1443 gimple_stmt_iterator gsi = gsi_after_labels (bb);
1444 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1446 else
1448 /* Insert the predicate of the BB at the end of the BB
1449 as this would reduce the register pressure: the only
1450 use of this predicate will be in successor BBs. */
1451 gimple_stmt_iterator gsi = gsi_last_bb (bb);
1453 if (gsi_end_p (gsi)
1454 || stmt_ends_bb_p (gsi_stmt (gsi)))
1455 gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
1456 else
1457 gsi_insert_seq_after (&gsi, stmts, GSI_SAME_STMT);
1460 /* Once the sequence is code generated, set it to NULL. */
1461 set_bb_predicate_gimplified_stmts (bb, NULL);
1466 /* Predicate each write to memory in LOOP.
1468 This function transforms control flow constructs containing memory
1469 writes of the form:
1471 | for (i = 0; i < N; i++)
1472 | if (cond)
1473 | A[i] = expr;
1475 into the following form that does not contain control flow:
1477 | for (i = 0; i < N; i++)
1478 | A[i] = cond ? expr : A[i];
1480 The original CFG looks like this:
1482 | bb_0
1483 | i = 0
1484 | end_bb_0
1486 | bb_1
1487 | if (i < N) goto bb_5 else goto bb_2
1488 | end_bb_1
1490 | bb_2
1491 | cond = some_computation;
1492 | if (cond) goto bb_3 else goto bb_4
1493 | end_bb_2
1495 | bb_3
1496 | A[i] = expr;
1497 | goto bb_4
1498 | end_bb_3
1500 | bb_4
1501 | goto bb_1
1502 | end_bb_4
1504 insert_gimplified_predicates inserts the computation of the COND
1505 expression at the beginning of the destination basic block:
1507 | bb_0
1508 | i = 0
1509 | end_bb_0
1511 | bb_1
1512 | if (i < N) goto bb_5 else goto bb_2
1513 | end_bb_1
1515 | bb_2
1516 | cond = some_computation;
1517 | if (cond) goto bb_3 else goto bb_4
1518 | end_bb_2
1520 | bb_3
1521 | cond = some_computation;
1522 | A[i] = expr;
1523 | goto bb_4
1524 | end_bb_3
1526 | bb_4
1527 | goto bb_1
1528 | end_bb_4
1530 predicate_mem_writes is then predicating the memory write as follows:
1532 | bb_0
1533 | i = 0
1534 | end_bb_0
1536 | bb_1
1537 | if (i < N) goto bb_5 else goto bb_2
1538 | end_bb_1
1540 | bb_2
1541 | if (cond) goto bb_3 else goto bb_4
1542 | end_bb_2
1544 | bb_3
1545 | cond = some_computation;
1546 | A[i] = cond ? expr : A[i];
1547 | goto bb_4
1548 | end_bb_3
1550 | bb_4
1551 | goto bb_1
1552 | end_bb_4
1554 and finally combine_blocks removes the basic block boundaries making
1555 the loop vectorizable:
1557 | bb_0
1558 | i = 0
1559 | if (i < N) goto bb_5 else goto bb_1
1560 | end_bb_0
1562 | bb_1
1563 | cond = some_computation;
1564 | A[i] = cond ? expr : A[i];
1565 | if (i < N) goto bb_5 else goto bb_4
1566 | end_bb_1
1568 | bb_4
1569 | goto bb_1
1570 | end_bb_4
1573 static void
1574 predicate_mem_writes (loop_p loop)
1576 unsigned int i, orig_loop_num_nodes = loop->num_nodes;
1578 for (i = 1; i < orig_loop_num_nodes; i++)
1580 gimple_stmt_iterator gsi;
1581 basic_block bb = ifc_bbs[i];
1582 tree cond = bb_predicate (bb);
1583 bool swap;
1584 gimple stmt;
1586 if (is_true_predicate (cond))
1587 continue;
1589 swap = false;
1590 if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
1592 swap = true;
1593 cond = TREE_OPERAND (cond, 0);
1596 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1597 if ((stmt = gsi_stmt (gsi))
1598 && gimple_assign_single_p (stmt)
1599 && gimple_vdef (stmt))
1601 tree lhs = gimple_assign_lhs (stmt);
1602 tree rhs = gimple_assign_rhs1 (stmt);
1603 tree type = TREE_TYPE (lhs);
1605 lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
1606 rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
1607 if (swap)
1609 tree tem = lhs;
1610 lhs = rhs;
1611 rhs = tem;
1613 cond = force_gimple_operand_gsi_1 (&gsi, unshare_expr (cond),
1614 is_gimple_condexpr, NULL_TREE,
1615 true, GSI_SAME_STMT);
1616 rhs = fold_build_cond_expr (type, unshare_expr (cond), rhs, lhs);
1617 gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
1618 update_stmt (stmt);
1623 /* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
1624 other than the exit and latch of the LOOP. Also resets the
1625 GIMPLE_DEBUG information. */
1627 static void
1628 remove_conditions_and_labels (loop_p loop)
1630 gimple_stmt_iterator gsi;
1631 unsigned int i;
1633 for (i = 0; i < loop->num_nodes; i++)
1635 basic_block bb = ifc_bbs[i];
1637 if (bb_with_exit_edge_p (loop, bb)
1638 || bb == loop->latch)
1639 continue;
1641 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
1642 switch (gimple_code (gsi_stmt (gsi)))
1644 case GIMPLE_COND:
1645 case GIMPLE_LABEL:
1646 gsi_remove (&gsi, true);
1647 break;
1649 case GIMPLE_DEBUG:
1650 /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
1651 if (gimple_debug_bind_p (gsi_stmt (gsi)))
1653 gimple_debug_bind_reset_value (gsi_stmt (gsi));
1654 update_stmt (gsi_stmt (gsi));
1656 gsi_next (&gsi);
1657 break;
1659 default:
1660 gsi_next (&gsi);
1665 /* Combine all the basic blocks from LOOP into one or two super basic
1666 blocks. Replace PHI nodes with conditional modify expressions. */
1668 static void
1669 combine_blocks (struct loop *loop)
1671 basic_block bb, exit_bb, merge_target_bb;
1672 unsigned int orig_loop_num_nodes = loop->num_nodes;
1673 unsigned int i;
1674 edge e;
1675 edge_iterator ei;
1677 remove_conditions_and_labels (loop);
1678 insert_gimplified_predicates (loop);
1679 predicate_all_scalar_phis (loop);
1681 if (flag_tree_loop_if_convert_stores)
1682 predicate_mem_writes (loop);
1684 /* Merge basic blocks: first remove all the edges in the loop,
1685 except for those from the exit block. */
1686 exit_bb = NULL;
1687 for (i = 0; i < orig_loop_num_nodes; i++)
1689 bb = ifc_bbs[i];
1690 free_bb_predicate (bb);
1691 if (bb_with_exit_edge_p (loop, bb))
1693 gcc_assert (exit_bb == NULL);
1694 exit_bb = bb;
1697 gcc_assert (exit_bb != loop->latch);
1699 for (i = 1; i < orig_loop_num_nodes; i++)
1701 bb = ifc_bbs[i];
1703 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei));)
1705 if (e->src == exit_bb)
1706 ei_next (&ei);
1707 else
1708 remove_edge (e);
1712 if (exit_bb != NULL)
1714 if (exit_bb != loop->header)
1716 /* Connect this node to loop header. */
1717 make_edge (loop->header, exit_bb, EDGE_FALLTHRU);
1718 set_immediate_dominator (CDI_DOMINATORS, exit_bb, loop->header);
1721 /* Redirect non-exit edges to loop->latch. */
1722 FOR_EACH_EDGE (e, ei, exit_bb->succs)
1724 if (!loop_exit_edge_p (loop, e))
1725 redirect_edge_and_branch (e, loop->latch);
1727 set_immediate_dominator (CDI_DOMINATORS, loop->latch, exit_bb);
1729 else
1731 /* If the loop does not have an exit, reconnect header and latch. */
1732 make_edge (loop->header, loop->latch, EDGE_FALLTHRU);
1733 set_immediate_dominator (CDI_DOMINATORS, loop->latch, loop->header);
1736 merge_target_bb = loop->header;
1737 for (i = 1; i < orig_loop_num_nodes; i++)
1739 gimple_stmt_iterator gsi;
1740 gimple_stmt_iterator last;
1742 bb = ifc_bbs[i];
1744 if (bb == exit_bb || bb == loop->latch)
1745 continue;
1747 /* Make stmts member of loop->header. */
1748 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1749 gimple_set_bb (gsi_stmt (gsi), merge_target_bb);
1751 /* Update stmt list. */
1752 last = gsi_last_bb (merge_target_bb);
1753 gsi_insert_seq_after (&last, bb_seq (bb), GSI_NEW_STMT);
1754 set_bb_seq (bb, NULL);
1756 delete_basic_block (bb);
1759 /* If possible, merge loop header to the block with the exit edge.
1760 This reduces the number of basic blocks to two, to please the
1761 vectorizer that handles only loops with two nodes. */
1762 if (exit_bb
1763 && exit_bb != loop->header
1764 && can_merge_blocks_p (loop->header, exit_bb))
1765 merge_blocks (loop->header, exit_bb);
1767 free (ifc_bbs);
1768 ifc_bbs = NULL;
1770 /* Post-dominators are corrupt now. */
1771 free_dominance_info (CDI_POST_DOMINATORS);
1774 /* If-convert LOOP when it is legal. For the moment this pass has no
1775 profitability analysis. Returns true when something changed. */
1777 static bool
1778 tree_if_conversion (struct loop *loop)
1780 bool changed = false;
1781 ifc_bbs = NULL;
1783 if (!if_convertible_loop_p (loop)
1784 || !dbg_cnt (if_conversion_tree))
1785 goto cleanup;
1787 /* Now all statements are if-convertible. Combine all the basic
1788 blocks into one huge basic block doing the if-conversion
1789 on-the-fly. */
1790 combine_blocks (loop);
1792 if (flag_tree_loop_if_convert_stores)
1793 mark_virtual_operands_for_renaming (cfun);
1795 changed = true;
1797 cleanup:
1798 if (ifc_bbs)
1800 unsigned int i;
1802 for (i = 0; i < loop->num_nodes; i++)
1803 free_bb_predicate (ifc_bbs[i]);
1805 free (ifc_bbs);
1806 ifc_bbs = NULL;
1809 return changed;
1812 /* Tree if-conversion pass management. */
1814 static unsigned int
1815 main_tree_if_conversion (void)
1817 loop_iterator li;
1818 struct loop *loop;
1819 bool changed = false;
1820 unsigned todo = 0;
1822 if (number_of_loops () <= 1)
1823 return 0;
1825 FOR_EACH_LOOP (li, loop, 0)
1826 changed |= tree_if_conversion (loop);
1828 if (changed)
1829 todo |= TODO_cleanup_cfg;
1831 if (changed && flag_tree_loop_if_convert_stores)
1832 todo |= TODO_update_ssa_only_virtuals;
1834 free_dominance_info (CDI_POST_DOMINATORS);
1836 #ifdef ENABLE_CHECKING
1838 basic_block bb;
1839 FOR_EACH_BB (bb)
1840 gcc_assert (!bb->aux);
1842 #endif
1844 return todo;
1847 /* Returns true when the if-conversion pass is enabled. */
1849 static bool
1850 gate_tree_if_conversion (void)
1852 return ((flag_tree_vectorize && flag_tree_loop_if_convert != 0)
1853 || flag_tree_loop_if_convert == 1
1854 || flag_tree_loop_if_convert_stores == 1);
1857 struct gimple_opt_pass pass_if_conversion =
1860 GIMPLE_PASS,
1861 "ifcvt", /* name */
1862 OPTGROUP_NONE, /* optinfo_flags */
1863 gate_tree_if_conversion, /* gate */
1864 main_tree_if_conversion, /* execute */
1865 NULL, /* sub */
1866 NULL, /* next */
1867 0, /* static_pass_number */
1868 TV_NONE, /* tv_id */
1869 PROP_cfg | PROP_ssa, /* properties_required */
1870 0, /* properties_provided */
1871 0, /* properties_destroyed */
1872 0, /* todo_flags_start */
1873 TODO_verify_stmts | TODO_verify_flow
1874 /* todo_flags_finish */