+/* Predicate each write to memory in LOOP.
+
+ This function transforms control flow constructs containing memory
+ writes of the form:
+
+ | for (i = 0; i < N; i++)
+ | if (cond)
+ | A[i] = expr;
+
+ into the following form that does not contain control flow:
+
+ | for (i = 0; i < N; i++)
+ | A[i] = cond ? expr : A[i];
+
+ The original CFG looks like this:
+
+ | bb_0
+ | i = 0
+ | end_bb_0
+ |
+ | bb_1
+ | if (i < N) goto bb_5 else goto bb_2
+ | end_bb_1
+ |
+ | bb_2
+ | cond = some_computation;
+ | if (cond) goto bb_3 else goto bb_4
+ | end_bb_2
+ |
+ | bb_3
+ | A[i] = expr;
+ | goto bb_4
+ | end_bb_3
+ |
+ | bb_4
+ | goto bb_1
+ | end_bb_4
+
+ insert_gimplified_predicates inserts the computation of the COND
+ expression at the beginning of the destination basic block:
+
+ | bb_0
+ | i = 0
+ | end_bb_0
+ |
+ | bb_1
+ | if (i < N) goto bb_5 else goto bb_2
+ | end_bb_1
+ |
+ | bb_2
+ | cond = some_computation;
+ | if (cond) goto bb_3 else goto bb_4
+ | end_bb_2
+ |
+ | bb_3
+ | cond = some_computation;
+ | A[i] = expr;
+ | goto bb_4
+ | end_bb_3
+ |
+ | bb_4
+ | goto bb_1
+ | end_bb_4
+
+ predicate_mem_writes is then predicating the memory write as follows:
+
+ | bb_0
+ | i = 0
+ | end_bb_0
+ |
+ | bb_1
+ | if (i < N) goto bb_5 else goto bb_2
+ | end_bb_1
+ |
+ | bb_2
+ | if (cond) goto bb_3 else goto bb_4
+ | end_bb_2
+ |
+ | bb_3
+ | cond = some_computation;
+ | A[i] = cond ? expr : A[i];
+ | goto bb_4
+ | end_bb_3
+ |
+ | bb_4
+ | goto bb_1
+ | end_bb_4
+
+ and finally combine_blocks removes the basic block boundaries making
+ the loop vectorizable:
+
+ | bb_0
+ | i = 0
+ | if (i < N) goto bb_5 else goto bb_1
+ | end_bb_0
+ |
+ | bb_1
+ | cond = some_computation;
+ | A[i] = cond ? expr : A[i];
+ | if (i < N) goto bb_5 else goto bb_4
+ | end_bb_1
+ |
+ | bb_4
+ | goto bb_1
+ | end_bb_4
+*/
+
+static void
+predicate_mem_writes (loop_p loop)
+{
+ unsigned int i, orig_loop_num_nodes = loop->num_nodes;
+
+ for (i = 1; i < orig_loop_num_nodes; i++)
+ {
+ gimple_stmt_iterator gsi;
+ basic_block bb = ifc_bbs[i];
+ tree cond = bb_predicate (bb);
+ gimple stmt;
+
+ if (is_true_predicate (cond))
+ continue;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if ((stmt = gsi_stmt (gsi))
+ && gimple_assign_single_p (stmt)
+ && gimple_vdef (stmt))
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree type = TREE_TYPE (lhs);
+
+ lhs = ifc_temp_var (type, unshare_expr (lhs), &gsi);
+ rhs = ifc_temp_var (type, unshare_expr (rhs), &gsi);
+ rhs = build3 (COND_EXPR, type, unshare_expr (cond), rhs, lhs);
+ gimple_assign_set_rhs1 (stmt, ifc_temp_var (type, rhs, &gsi));
+ update_stmt (stmt);
+ }
+ }
+}
+
+/* Remove all GIMPLE_CONDs and GIMPLE_LABELs of all the basic blocks
+ other than the exit and latch of the LOOP. Also resets the
+ GIMPLE_DEBUG information. */
+
+static void
+remove_conditions_and_labels (loop_p loop)
+{
+ gimple_stmt_iterator gsi;
+ unsigned int i;
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = ifc_bbs[i];
+
+ if (bb_with_exit_edge_p (loop, bb)
+ || bb == loop->latch)
+ continue;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
+ switch (gimple_code (gsi_stmt (gsi)))
+ {
+ case GIMPLE_COND:
+ case GIMPLE_LABEL:
+ gsi_remove (&gsi, true);
+ break;
+
+ case GIMPLE_DEBUG:
+ /* ??? Should there be conditional GIMPLE_DEBUG_BINDs? */
+ if (gimple_debug_bind_p (gsi_stmt (gsi)))
+ {
+ gimple_debug_bind_reset_value (gsi_stmt (gsi));
+ update_stmt (gsi_stmt (gsi));
+ }
+ gsi_next (&gsi);
+ break;
+
+ default:
+ gsi_next (&gsi);
+ }
+ }
+}
+
+/* Combine all the basic blocks from LOOP into one or two super basic
+ blocks. Replace PHI nodes with conditional modify expressions. */