+ bitmap visited;
+ unsigned int index = 0;
+ unsigned int visited_count = 0;
+
+ gcc_assert (loop->num_nodes);
+ gcc_assert (loop->latch != EXIT_BLOCK_PTR);
+
+ blocks = XCNEWVEC (basic_block, loop->num_nodes);
+ visited = BITMAP_ALLOC (NULL);
+
+ blocks_in_bfs_order = get_loop_body_in_bfs_order (loop);
+
+ index = 0;
+ while (index < loop->num_nodes)
+ {
+ bb = blocks_in_bfs_order [index];
+
+ if (bb->flags & BB_IRREDUCIBLE_LOOP)
+ {
+ free (blocks_in_bfs_order);
+ BITMAP_FREE (visited);
+ free (blocks);
+ return NULL;
+ }
+
+ if (!bitmap_bit_p (visited, bb->index))
+ {
+ if (pred_blocks_visited_p (bb, &visited)
+ || bb == loop->header)
+ {
+ /* This block is now visited. */
+ bitmap_set_bit (visited, bb->index);
+ blocks[visited_count++] = bb;
+ }
+ }
+
+ index++;
+
+ if (index == loop->num_nodes
+ && visited_count != loop->num_nodes)
+ /* Not done yet. */
+ index = 0;
+ }
+ free (blocks_in_bfs_order);
+ BITMAP_FREE (visited);
+ return blocks;
+}
+
+/* Returns true when the analysis of the predicates for all the basic
+ blocks in LOOP succeeded.
+
+ predicate_bbs first allocates the predicates of the basic blocks.
+ These fields are then initialized with the tree expressions
+ representing the predicates under which a basic block is executed
+ in the LOOP. As the loop->header is executed at each iteration, it
+ has the "true" predicate. Other statements executed under a
+ condition are predicated with that condition, for example
+
+ | if (x)
+ | S1;
+ | else
+ | S2;
+
+ S1 will be predicated with "x", and
+ S2 will be predicated with "!x". */
+
+static bool
+predicate_bbs (loop_p loop)
+{
+ unsigned int i;
+
+ for (i = 0; i < loop->num_nodes; i++)
+ init_bb_predicate (ifc_bbs[i]);
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = ifc_bbs[i];
+ tree cond;
+ gimple_stmt_iterator itr;
+
+ /* The loop latch is always executed and has no extra conditions
+ to be processed: skip it. */
+ if (bb == loop->latch)
+ {
+ reset_bb_predicate (loop->latch);
+ continue;
+ }
+
+ cond = bb_predicate (bb);
+ if (cond
+ && bb != loop->header)
+ {
+ gimple_seq stmts;
+
+ cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
+ add_bb_predicate_gimplified_stmts (bb, stmts);
+ }
+
+ for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
+ {
+ gimple stmt = gsi_stmt (itr);
+
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_LABEL:
+ case GIMPLE_ASSIGN:
+ case GIMPLE_CALL:
+ case GIMPLE_DEBUG:
+ break;
+
+ case GIMPLE_COND:
+ {
+ tree c2;
+ edge true_edge, false_edge;
+ location_t loc = gimple_location (stmt);
+ tree c = fold_build2_loc (loc, gimple_cond_code (stmt),
+ boolean_type_node,
+ gimple_cond_lhs (stmt),
+ gimple_cond_rhs (stmt));
+
+ /* Add new condition into destination's predicate list. */
+ extract_true_false_edges_from_block (gimple_bb (stmt),
+ &true_edge, &false_edge);
+
+ /* If C is true, then TRUE_EDGE is taken. */
+ add_to_dst_predicate_list (loop, true_edge, cond, c);
+
+ /* If C is false, then FALSE_EDGE is taken. */
+ c2 = invert_truthvalue_loc (loc, unshare_expr (c));
+ add_to_dst_predicate_list (loop, false_edge, cond, c2);
+
+ cond = NULL_TREE;
+ break;
+ }
+
+ default:
+ /* Not handled yet in if-conversion. */
+ return false;
+ }
+ }
+
+ /* If current bb has only one successor, then consider it as an
+ unconditional goto. */
+ if (single_succ_p (bb))
+ {
+ basic_block bb_n = single_succ (bb);
+
+ /* The successor bb inherits the predicate of its
+ predecessor. If there is no predicate in the predecessor
+ bb, then consider the successor bb as always executed. */
+ if (cond == NULL_TREE)
+ cond = boolean_true_node;
+
+ add_to_predicate_list (bb_n, cond);
+ }
+ }
+
+ /* The loop header is always executed. */
+ reset_bb_predicate (loop->header);
+ gcc_assert (bb_predicate_gimplified_stmts (loop->header) == NULL
+ && bb_predicate_gimplified_stmts (loop->latch) == NULL);
+
+ return true;
+}
+
+/* Return true when LOOP is if-convertible.
+ LOOP is if-convertible if:
+ - it is innermost,
+ - it has two or more basic blocks,
+ - it has only one exit,
+ - loop header is not the exit edge,
+ - if its basic blocks and phi nodes are if convertible. */
+
+static bool
+if_convertible_loop_p (struct loop *loop)
+{