+
+ fail:
+ free (bbs);
+ return false;
+}
+
+
+DEF_VEC_I(source_location);
+DEF_VEC_ALLOC_I(source_location,heap);
+
+/* Transform the loop nest into a perfect nest, if possible.
+ LOOP is the loop nest to transform into a perfect nest
+ LBOUNDS are the lower bounds for the loops to transform
+ UBOUNDS are the upper bounds for the loops to transform
+ STEPS is the STEPS for the loops to transform.
+ LOOPIVS is the induction variables for the loops to transform.
+
+ Basically, for the case of
+
+ FOR (i = 0; i < 50; i++)
+ {
+ FOR (j =0; j < 50; j++)
+ {
+ <whatever>
+ }
+ <some code>
+ }
+
+ This function will transform it into a perfect loop nest by splitting the
+ outer loop into two loops, like so:
+
+ FOR (i = 0; i < 50; i++)
+ {
+ FOR (j = 0; j < 50; j++)
+ {
+ <whatever>
+ }
+ }
+
+ FOR (i = 0; i < 50; i ++)
+ {
+ <some code>
+ }
+
+ Return FALSE if we can't make this loop into a perfect nest. */
+
+static bool
+perfect_nestify (struct loop *loop,
+ VEC(tree,heap) *lbounds,
+ VEC(tree,heap) *ubounds,
+ VEC(int,heap) *steps,
+ VEC(tree,heap) *loopivs)
+{
+ basic_block *bbs;
+ gimple exit_condition;
+ gimple cond_stmt;
+ basic_block preheaderbb, headerbb, bodybb, latchbb, olddest;
+ int i;
+ gimple_stmt_iterator bsi, firstbsi;
+ bool insert_after;
+ edge e;
+ struct loop *newloop;
+ gimple phi;
+ tree uboundvar;
+ gimple stmt;
+ tree oldivvar, ivvar, ivvarinced;
+ VEC(tree,heap) *phis = NULL;
+ VEC(source_location,heap) *locations = NULL;
+ htab_t replacements = NULL;
+
+ /* Create the new loop. */
+ olddest = single_exit (loop)->dest;
+ preheaderbb = split_edge (single_exit (loop));
+ headerbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+
+ /* Push the exit phi nodes that we are moving. */
+ for (bsi = gsi_start_phis (olddest); !gsi_end_p (bsi); gsi_next (&bsi))
+ {
+ phi = gsi_stmt (bsi);
+ VEC_reserve (tree, heap, phis, 2);
+ VEC_reserve (source_location, heap, locations, 1);
+ VEC_quick_push (tree, phis, PHI_RESULT (phi));
+ VEC_quick_push (tree, phis, PHI_ARG_DEF (phi, 0));
+ VEC_quick_push (source_location, locations,
+ gimple_phi_arg_location (phi, 0));
+ }
+ e = redirect_edge_and_branch (single_succ_edge (preheaderbb), headerbb);
+
+ /* Remove the exit phis from the old basic block. */
+ for (bsi = gsi_start_phis (olddest); !gsi_end_p (bsi); )
+ remove_phi_node (&bsi, false);
+
+ /* and add them back to the new basic block. */
+ while (VEC_length (tree, phis) != 0)
+ {
+ tree def;
+ tree phiname;
+ source_location locus;
+ def = VEC_pop (tree, phis);
+ phiname = VEC_pop (tree, phis);
+ locus = VEC_pop (source_location, locations);
+ phi = create_phi_node (phiname, preheaderbb);
+ add_phi_arg (phi, def, single_pred_edge (preheaderbb), locus);
+ }
+ flush_pending_stmts (e);
+ VEC_free (tree, heap, phis);
+
+ bodybb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+ latchbb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
+ make_edge (headerbb, bodybb, EDGE_FALLTHRU);
+ cond_stmt = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
+ NULL_TREE, NULL_TREE);
+ bsi = gsi_start_bb (bodybb);
+ gsi_insert_after (&bsi, cond_stmt, GSI_NEW_STMT);
+ e = make_edge (bodybb, olddest, EDGE_FALSE_VALUE);
+ make_edge (bodybb, latchbb, EDGE_TRUE_VALUE);
+ make_edge (latchbb, headerbb, EDGE_FALLTHRU);
+
+ /* Update the loop structures. */
+ newloop = duplicate_loop (loop, olddest->loop_father);
+ newloop->header = headerbb;
+ newloop->latch = latchbb;
+ add_bb_to_loop (latchbb, newloop);
+ add_bb_to_loop (bodybb, newloop);
+ add_bb_to_loop (headerbb, newloop);
+ set_immediate_dominator (CDI_DOMINATORS, bodybb, headerbb);
+ set_immediate_dominator (CDI_DOMINATORS, headerbb, preheaderbb);
+ set_immediate_dominator (CDI_DOMINATORS, preheaderbb,
+ single_exit (loop)->src);
+ set_immediate_dominator (CDI_DOMINATORS, latchbb, bodybb);
+ set_immediate_dominator (CDI_DOMINATORS, olddest,
+ recompute_dominator (CDI_DOMINATORS, olddest));
+ /* Create the new iv. */
+ oldivvar = VEC_index (tree, loopivs, 0);
+ ivvar = create_tmp_var (TREE_TYPE (oldivvar), "perfectiv");
+ add_referenced_var (ivvar);
+ standard_iv_increment_position (newloop, &bsi, &insert_after);
+ create_iv (VEC_index (tree, lbounds, 0),
+ build_int_cst (TREE_TYPE (oldivvar), VEC_index (int, steps, 0)),
+ ivvar, newloop, &bsi, insert_after, &ivvar, &ivvarinced);
+
+ /* Create the new upper bound. This may be not just a variable, so we copy
+ it to one just in case. */
+
+ exit_condition = get_loop_exit_condition (newloop);
+ uboundvar = create_tmp_var (TREE_TYPE (VEC_index (tree, ubounds, 0)),
+ "uboundvar");
+ add_referenced_var (uboundvar);
+ stmt = gimple_build_assign (uboundvar, VEC_index (tree, ubounds, 0));
+ uboundvar = make_ssa_name (uboundvar, stmt);
+ gimple_assign_set_lhs (stmt, uboundvar);
+
+ if (insert_after)
+ gsi_insert_after (&bsi, stmt, GSI_SAME_STMT);
+ else
+ gsi_insert_before (&bsi, stmt, GSI_SAME_STMT);
+ update_stmt (stmt);
+ gimple_cond_set_condition (exit_condition, GE_EXPR, uboundvar, ivvarinced);
+ update_stmt (exit_condition);
+ replacements = htab_create_ggc (20, tree_map_hash,
+ tree_map_eq, NULL);
+ bbs = get_loop_body_in_dom_order (loop);
+ /* Now move the statements, and replace the induction variable in the moved
+ statements with the correct loop induction variable. */
+ oldivvar = VEC_index (tree, loopivs, 0);
+ firstbsi = gsi_start_bb (bodybb);
+ for (i = loop->num_nodes - 1; i >= 0 ; i--)
+ {
+ gimple_stmt_iterator tobsi = gsi_last_bb (bodybb);
+ if (bbs[i]->loop_father == loop)
+ {
+ /* If this is true, we are *before* the inner loop.
+ If this isn't true, we are *after* it.
+
+ The only time can_convert_to_perfect_nest returns true when we
+ have statements before the inner loop is if they can be moved
+ into the inner loop.
+
+ The only time can_convert_to_perfect_nest returns true when we
+ have statements after the inner loop is if they can be moved into
+ the new split loop. */
+
+ if (dominated_by_p (CDI_DOMINATORS, loop->inner->header, bbs[i]))
+ {
+ gimple_stmt_iterator header_bsi
+ = gsi_after_labels (loop->inner->header);
+
+ for (bsi = gsi_start_bb (bbs[i]); !gsi_end_p (bsi);)
+ {
+ gimple stmt = gsi_stmt (bsi);
+
+ if (stmt == exit_condition
+ || not_interesting_stmt (stmt)
+ || stmt_is_bumper_for_loop (loop, stmt))
+ {
+ gsi_next (&bsi);
+ continue;
+ }
+
+ gsi_move_before (&bsi, &header_bsi);
+ }
+ }
+ else
+ {
+ /* Note that the bsi only needs to be explicitly incremented
+ when we don't move something, since it is automatically
+ incremented when we do. */
+ for (bsi = gsi_start_bb (bbs[i]); !gsi_end_p (bsi);)
+ {
+ gimple stmt = gsi_stmt (bsi);
+
+ if (stmt == exit_condition
+ || not_interesting_stmt (stmt)
+ || stmt_is_bumper_for_loop (loop, stmt))
+ {
+ gsi_next (&bsi);
+ continue;
+ }
+
+ replace_uses_equiv_to_x_with_y
+ (loop, stmt, oldivvar, VEC_index (int, steps, 0), ivvar,
+ VEC_index (tree, lbounds, 0), replacements, &firstbsi);
+
+ gsi_move_before (&bsi, &tobsi);
+
+ /* If the statement has any virtual operands, they may
+ need to be rewired because the original loop may
+ still reference them. */
+ if (gimple_vuse (stmt))
+ mark_sym_for_renaming (gimple_vop (cfun));
+ }
+ }
+
+ }
+ }
+
+ free (bbs);
+ htab_delete (replacements);
+ return perfect_nest_p (loop);