+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "basic block after exit bb but before latch\n");
+ return false;
+ }
+ else if (!empty_block_p (bb))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "non empty basic block after exit bb\n");
+ return false;
+ }
+ else if (bb == loop->latch
+ && bb != exit_bb
+ && !dominated_by_p (CDI_DOMINATORS, bb, exit_bb))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "latch is not dominated by exit_block\n");
+ return false;
+ }
+ }
+
+ /* Be less adventurous and handle only normal edges. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->flags &
+ (EDGE_ABNORMAL_CALL | EDGE_EH | EDGE_ABNORMAL | EDGE_IRREDUCIBLE_LOOP))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Difficult to handle edges\n");
+ return false;
+ }
+
+ return true;
+}
+
+/* Return true when all predecessor blocks of BB are visited. The
+ VISITED bitmap keeps track of the visited blocks. */
+
+static bool
+pred_blocks_visited_p (basic_block bb, bitmap *visited)
+{
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (!bitmap_bit_p (*visited, e->src->index))
+ return false;
+
+ return true;
+}
+
+/* Get body of a LOOP in suitable order for if-conversion. It is
+ caller's responsibility to deallocate basic block list.
+ If-conversion suitable order is, breadth first sort (BFS) order
+ with an additional constraint: select a block only if all its
+ predecessors are already selected. */
+
+static basic_block *
+get_loop_body_in_if_conv_order (const struct loop *loop)
+{
+ basic_block *blocks, *blocks_in_bfs_order;
+ basic_block bb;
+ 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, tem;
+ 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, unshare_expr (c));
+
+ /* If C is false, then FALSE_EDGE is taken. */
+ c2 = invert_truthvalue_loc (loc, unshare_expr (c));
+ tem = canonicalize_cond_expr_cond (c2);
+ if (tem)
+ c2 = tem;
+ 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. This is a helper function
+ for if_convertible_loop_p. REFS and DDRS are initialized and freed
+ in if_convertible_loop_p. */
+
+static bool
+if_convertible_loop_p_1 (struct loop *loop,
+ VEC (data_reference_p, heap) **refs,
+ VEC (ddr_p, heap) **ddrs)
+{
+ bool res;
+ unsigned int i;
+ basic_block exit_bb = NULL;
+
+ /* Don't if-convert the loop when the data dependences cannot be
+ computed: the loop won't be vectorized in that case. */
+ res = compute_data_dependences_for_loop (loop, true, refs, ddrs);
+ if (!res)
+ return false;
+
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* Allow statements that can be handled during if-conversion. */
+ ifc_bbs = get_loop_body_in_if_conv_order (loop);
+ if (!ifc_bbs)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Irreducible loop\n");
+ return false;
+ }
+
+ for (i = 0; i < loop->num_nodes; i++)
+ {
+ basic_block bb = ifc_bbs[i];
+
+ if (!if_convertible_bb_p (loop, bb, exit_bb))
+ return false;
+
+ if (bb_with_exit_edge_p (loop, bb))
+ exit_bb = bb;
+ }
+
+ res = predicate_bbs (loop);
+ if (!res)
+ return false;
+
+ if (flag_tree_loop_if_convert_stores)
+ {
+ data_reference_p dr;
+
+ for (i = 0; VEC_iterate (data_reference_p, *refs, i, dr); i++)
+ {
+ dr->aux = XNEW (struct ifc_dr);
+ DR_WRITTEN_AT_LEAST_ONCE (dr) = -1;
+ DR_RW_UNCONDITIONALLY (dr) = -1;
OSDN Git Service
