- loop1_preheader_bb:
- guard1 (goto loop1/merg1_bb)
- loop1
- loop1_exit_bb:
- guard2 (goto merge1_bb/merge2_bb)
- merge1_bb
-LOOP-> loop2
- loop2_exit_bb
- merge2_bb
- next_bb
-
- For each name used out side the loop (i.e - for each name that has an exit
- phi in next_bb) we create a new phi in:
- 1. merge2_bb (to account for the edge from guard_bb)
- 2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
- 3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
- if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
-*/
-
-static void
-slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
- bool is_new_loop, basic_block *new_exit_bb)
-{
- tree orig_phi, new_phi;
- tree update_phi, update_phi2;
- tree guard_arg, loop_arg;
- basic_block new_merge_bb = guard_edge->dest;
- edge e = EDGE_SUCC (new_merge_bb, 0);
- basic_block update_bb = e->dest;
- edge new_exit_e;
- tree orig_def, orig_def_new_name;
- tree new_name, new_name2;
- tree arg;
-
- /* Create new bb between loop and new_merge_bb. */
- *new_exit_bb = split_edge (loop->single_exit);
- add_bb_to_loop (*new_exit_bb, loop->outer);
-
- new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
-
- for (update_phi = phi_nodes (update_bb); update_phi;
- update_phi = PHI_CHAIN (update_phi))
- {
- orig_phi = update_phi;
- orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
- orig_def_new_name = get_current_def (orig_def);
- arg = NULL_TREE;
-
- /** 1. Handle new-merge-point phis **/
-
- /* 1.1. Generate new phi node in NEW_MERGE_BB: */
- new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
- new_merge_bb);
-
- /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
- of LOOP. Set the two PHI args in NEW_PHI for these edges: */
- new_name = orig_def;
- new_name2 = NULL_TREE;
- if (orig_def_new_name)
- {
- new_name = orig_def_new_name;
- /* Some variables have both loop-entry-phis and loop-exit-phis.
- Such variables were given yet newer names by phis placed in
- guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
- new_name2 = get_current_def (get_current_def (orig_name)). */
- new_name2 = get_current_def (new_name);
- }
-
- if (is_new_loop)
- {
- guard_arg = orig_def;
- loop_arg = new_name;
- }
- else
- {
- guard_arg = new_name;
- loop_arg = orig_def;
- }
- if (new_name2)
- guard_arg = new_name2;
-
- add_phi_arg (new_phi, loop_arg, new_exit_e);
- add_phi_arg (new_phi, guard_arg, guard_edge);
-
- /* 1.3. Update phi in successor block. */
- gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
- SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
- update_phi2 = new_phi;
-
-
- /** 2. Handle loop-closed-ssa-form phis **/
-
- /* 2.1. Generate new phi node in NEW_EXIT_BB: */
- new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
- *new_exit_bb);
-
- /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
- add_phi_arg (new_phi, loop_arg, loop->single_exit);
-
- /* 2.3. Update phi in successor of NEW_EXIT_BB: */
- gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
- SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
-
-
- /** 3. Handle loop-closed-ssa-form phis for first loop **/
-
- /* 3.1. Find the relevant names that need an exit-phi in
- GUARD_BB, i.e. names for which
- slpeel_update_phi_nodes_for_guard1 had not already created a
- phi node. This is the case for names that are used outside
- the loop (and therefore need an exit phi) but are not updated
- across loop iterations (and therefore don't have a
- loop-header-phi).
-
- slpeel_update_phi_nodes_for_guard1 is responsible for
- creating loop-exit phis in GUARD_BB for names that have a
- loop-header-phi. When such a phi is created we also record
- the new name in its current definition. If this new name
- exists, then guard_arg was set to this new name (see 1.2
- above). Therefore, if guard_arg is not this new name, this
- is an indication that an exit-phi in GUARD_BB was not yet
- created, so we take care of it here. */
- if (guard_arg == new_name2)
- continue;
- arg = guard_arg;
-
- /* 3.2. Generate new phi node in GUARD_BB: */
- new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
- guard_edge->src);
-
- /* 3.3. GUARD_BB has one incoming edge: */
- gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
- add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0));
-
- /* 3.4. Update phi in successor of GUARD_BB: */
- gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
- == guard_arg);
- SET_PHI_ARG_DEF (update_phi2, guard_edge->dest_idx, PHI_RESULT (new_phi));
- }
-
- set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
-}
-
-
-/* Make the LOOP iterate NITERS times. This is done by adding a new IV
- that starts at zero, increases by one and its limit is NITERS.
-
- Assumption: the exit-condition of LOOP is the last stmt in the loop. */
-
-void
-slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
-{
- tree indx_before_incr, indx_after_incr, cond_stmt, cond;
- tree orig_cond;
- edge exit_edge = loop->single_exit;
- block_stmt_iterator loop_cond_bsi;
- block_stmt_iterator incr_bsi;
- bool insert_after;
- tree begin_label = tree_block_label (loop->latch);
- tree exit_label = tree_block_label (loop->single_exit->dest);
- tree init = build_int_cst (TREE_TYPE (niters), 0);
- tree step = build_int_cst (TREE_TYPE (niters), 1);
- tree then_label;
- tree else_label;
- LOC loop_loc;
-
- orig_cond = get_loop_exit_condition (loop);
- gcc_assert (orig_cond);
- loop_cond_bsi = bsi_for_stmt (orig_cond);
-
- standard_iv_increment_position (loop, &incr_bsi, &insert_after);
- create_iv (init, step, NULL_TREE, loop,
- &incr_bsi, insert_after, &indx_before_incr, &indx_after_incr);
-
- if (exit_edge->flags & EDGE_TRUE_VALUE) /* 'then' edge exits the loop. */
- {
- cond = build2 (GE_EXPR, boolean_type_node, indx_after_incr, niters);
- then_label = build1 (GOTO_EXPR, void_type_node, exit_label);
- else_label = build1 (GOTO_EXPR, void_type_node, begin_label);
- }
- else /* 'then' edge loops back. */
- {
- cond = build2 (LT_EXPR, boolean_type_node, indx_after_incr, niters);
- then_label = build1 (GOTO_EXPR, void_type_node, begin_label);
- else_label = build1 (GOTO_EXPR, void_type_node, exit_label);
- }
-
- cond_stmt = build3 (COND_EXPR, TREE_TYPE (orig_cond), cond,
- then_label, else_label);
- bsi_insert_before (&loop_cond_bsi, cond_stmt, BSI_SAME_STMT);
-
- /* Remove old loop exit test: */
- bsi_remove (&loop_cond_bsi);
-
- loop_loc = find_loop_location (loop);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- if (loop_loc != UNKNOWN_LOC)
- fprintf (dump_file, "\nloop at %s:%d: ",
- LOC_FILE (loop_loc), LOC_LINE (loop_loc));
- print_generic_expr (dump_file, cond_stmt, TDF_SLIM);
- }
-
- loop->nb_iterations = niters;
-}
-
-
-/* Given LOOP this function generates a new copy of it and puts it
- on E which is either the entry or exit of LOOP. */
-
-static struct loop *
-slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, struct loops *loops,
- edge e)
-{
- struct loop *new_loop;
- basic_block *new_bbs, *bbs;
- bool at_exit;
- bool was_imm_dom;
- basic_block exit_dest;
- tree phi, phi_arg;
-
- at_exit = (e == loop->single_exit);
- if (!at_exit && e != loop_preheader_edge (loop))
- return NULL;
-
- bbs = get_loop_body (loop);
-
- /* Check whether duplication is possible. */
- if (!can_copy_bbs_p (bbs, loop->num_nodes))
- {
- free (bbs);
- return NULL;
- }
-
- /* Generate new loop structure. */
- new_loop = duplicate_loop (loops, loop, loop->outer);
- if (!new_loop)
- {
- free (bbs);
- return NULL;
- }
-
- exit_dest = loop->single_exit->dest;
- was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
- exit_dest) == loop->header ?
- true : false);
-
- new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes);
-
- copy_bbs (bbs, loop->num_nodes, new_bbs,
- &loop->single_exit, 1, &new_loop->single_exit, NULL);
-
- /* Duplicating phi args at exit bbs as coming
- also from exit of duplicated loop. */
- for (phi = phi_nodes (exit_dest); phi; phi = PHI_CHAIN (phi))
- {
- phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, loop->single_exit);
- if (phi_arg)
- {
- edge new_loop_exit_edge;
-
- if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
- new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
- else
- new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
-
- add_phi_arg (phi, phi_arg, new_loop_exit_edge);
- }
- }
-
- if (at_exit) /* Add the loop copy at exit. */
- {
- redirect_edge_and_branch_force (e, new_loop->header);
- set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
- if (was_imm_dom)
- set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
- }
- else /* Add the copy at entry. */
- {
- edge new_exit_e;
- edge entry_e = loop_preheader_edge (loop);
- basic_block preheader = entry_e->src;
-
- if (!flow_bb_inside_loop_p (new_loop,
- EDGE_SUCC (new_loop->header, 0)->dest))
- new_exit_e = EDGE_SUCC (new_loop->header, 0);
- else
- new_exit_e = EDGE_SUCC (new_loop->header, 1);
-
- redirect_edge_and_branch_force (new_exit_e, loop->header);
- set_immediate_dominator (CDI_DOMINATORS, loop->header,
- new_exit_e->src);
-
- /* We have to add phi args to the loop->header here as coming
- from new_exit_e edge. */
- for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
- {
- phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
- if (phi_arg)
- add_phi_arg (phi, phi_arg, new_exit_e);
- }
-
- redirect_edge_and_branch_force (entry_e, new_loop->header);
- set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
- }
-
- free (new_bbs);
- free (bbs);
-
- return new_loop;
-}
-
-
-/* Given the condition statement COND, put it as the last statement
- of GUARD_BB; EXIT_BB is the basic block to skip the loop;
- Assumes that this is the single exit of the guarded loop.
- Returns the skip edge. */
-
-static edge
-slpeel_add_loop_guard (basic_block guard_bb, tree cond, basic_block exit_bb,
- basic_block dom_bb)
-{
- block_stmt_iterator bsi;
- edge new_e, enter_e;
- tree cond_stmt, then_label, else_label;
-
- enter_e = EDGE_SUCC (guard_bb, 0);
- enter_e->flags &= ~EDGE_FALLTHRU;
- enter_e->flags |= EDGE_FALSE_VALUE;
- bsi = bsi_last (guard_bb);
-
- then_label = build1 (GOTO_EXPR, void_type_node,
- tree_block_label (exit_bb));
- else_label = build1 (GOTO_EXPR, void_type_node,
- tree_block_label (enter_e->dest));
- cond_stmt = build3 (COND_EXPR, void_type_node, cond,
- then_label, else_label);
- bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
- /* Add new edge to connect guard block to the merge/loop-exit block. */
- new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
- set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
- return new_e;
-}
-
-
-/* This function verifies that the following restrictions apply to LOOP:
- (1) it is innermost
- (2) it consists of exactly 2 basic blocks - header, and an empty latch.
- (3) it is single entry, single exit
- (4) its exit condition is the last stmt in the header
- (5) E is the entry/exit edge of LOOP.
- */
-
-bool
-slpeel_can_duplicate_loop_p (struct loop *loop, edge e)
-{
- edge exit_e = loop->single_exit;
- edge entry_e = loop_preheader_edge (loop);
- tree orig_cond = get_loop_exit_condition (loop);
- block_stmt_iterator loop_exit_bsi = bsi_last (exit_e->src);
-
- if (need_ssa_update_p ())
- return false;
-
- if (loop->inner
- /* All loops have an outer scope; the only case loop->outer is NULL is for
- the function itself. */
- || !loop->outer
- || loop->num_nodes != 2
- || !empty_block_p (loop->latch)
- || !loop->single_exit
- /* Verify that new loop exit condition can be trivially modified. */
- || (!orig_cond || orig_cond != bsi_stmt (loop_exit_bsi))
- || (e != exit_e && e != entry_e))
- return false;
-
- return true;
-}
-
-#ifdef ENABLE_CHECKING
-void
-slpeel_verify_cfg_after_peeling (struct loop *first_loop,
- struct loop *second_loop)
-{
- basic_block loop1_exit_bb = first_loop->single_exit->dest;
- basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
- basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
-
- /* A guard that controls whether the second_loop is to be executed or skipped
- is placed in first_loop->exit. first_loopt->exit therefore has two
- successors - one is the preheader of second_loop, and the other is a bb
- after second_loop.
- */
- gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
-
- /* 1. Verify that one of the successors of first_loopt->exit is the preheader
- of second_loop. */
-
- /* The preheader of new_loop is expected to have two predecessors:
- first_loop->exit and the block that precedes first_loop. */
-
- gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
- && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
- && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
- || (EDGE_PRED (loop2_entry_bb, 1)->src == loop1_exit_bb
- && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
-
- /* Verify that the other successor of first_loopt->exit is after the
- second_loop. */
- /* TODO */
-}
-#endif
-
-/* Function slpeel_tree_peel_loop_to_edge.
-
- Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
- that is placed on the entry (exit) edge E of LOOP. After this transformation
- we have two loops one after the other - first-loop iterates FIRST_NITERS
- times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
-
- Input:
- - LOOP: the loop to be peeled.
- - E: the exit or entry edge of LOOP.
- If it is the entry edge, we peel the first iterations of LOOP. In this
- case first-loop is LOOP, and second-loop is the newly created loop.
- If it is the exit edge, we peel the last iterations of LOOP. In this
- case, first-loop is the newly created loop, and second-loop is LOOP.
- - NITERS: the number of iterations that LOOP iterates.
- - FIRST_NITERS: the number of iterations that the first-loop should iterate.
- - UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible
- for updating the loop bound of the first-loop to FIRST_NITERS. If it
- is false, the caller of this function may want to take care of this
- (this can be useful if we don't want new stmts added to first-loop).
-
- Output:
- The function returns a pointer to the new loop-copy, or NULL if it failed
- to perform the transformation.
-
- The function generates two if-then-else guards: one before the first loop,
- and the other before the second loop:
- The first guard is:
- if (FIRST_NITERS == 0) then skip the first loop,
- and go directly to the second loop.
- The second guard is:
- if (FIRST_NITERS == NITERS) then skip the second loop.
-
- FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
- FORNOW the resulting code will not be in loop-closed-ssa form.
-*/
-
-struct loop*
-slpeel_tree_peel_loop_to_edge (struct loop *loop, struct loops *loops,
- edge e, tree first_niters,
- tree niters, bool update_first_loop_count)
-{
- struct loop *new_loop = NULL, *first_loop, *second_loop;
- edge skip_e;
- tree pre_condition;
- bitmap definitions;
- basic_block bb_before_second_loop, bb_after_second_loop;
- basic_block bb_before_first_loop;
- basic_block bb_between_loops;
- basic_block new_exit_bb;
- edge exit_e = loop->single_exit;
- LOC loop_loc;
-
- if (!slpeel_can_duplicate_loop_p (loop, e))
- return NULL;
-
- /* We have to initialize cfg_hooks. Then, when calling
- cfg_hooks->split_edge, the function tree_split_edge
- is actually called and, when calling cfg_hooks->duplicate_block,
- the function tree_duplicate_bb is called. */
- tree_register_cfg_hooks ();
-
-
- /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
- Resulting CFG would be:
-
- first_loop:
- do {
- } while ...
-
- second_loop:
- do {
- } while ...
-
- orig_exit_bb:
- */
-
- if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, loops, e)))
- {
- loop_loc = find_loop_location (loop);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- if (loop_loc != UNKNOWN_LOC)
- fprintf (dump_file, "\n%s:%d: note: ",
- LOC_FILE (loop_loc), LOC_LINE (loop_loc));
- fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
- }
- return NULL;
- }
-
- if (e == exit_e)
- {
- /* NEW_LOOP was placed after LOOP. */
- first_loop = loop;
- second_loop = new_loop;
- }
- else
- {
- /* NEW_LOOP was placed before LOOP. */
- first_loop = new_loop;
- second_loop = loop;
- }
-
- definitions = ssa_names_to_replace ();
- slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
- rename_variables_in_loop (new_loop);
-
-
- /* 2. Add the guard that controls whether the first loop is executed.
- Resulting CFG would be:
-
- bb_before_first_loop:
- if (FIRST_NITERS == 0) GOTO bb_before_second_loop
- GOTO first-loop
-
- first_loop:
- do {
- } while ...
-
- bb_before_second_loop:
-
- second_loop:
- do {
- } while ...
-
- orig_exit_bb:
- */
-
- bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
- add_bb_to_loop (bb_before_first_loop, first_loop->outer);
- bb_before_second_loop = split_edge (first_loop->single_exit);
- add_bb_to_loop (bb_before_second_loop, first_loop->outer);
-
- pre_condition =
- fold_build2 (LE_EXPR, boolean_type_node, first_niters,
- build_int_cst (TREE_TYPE (first_niters), 0));
- skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
- bb_before_second_loop, bb_before_first_loop);
- slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
- first_loop == new_loop,
- &new_exit_bb, &definitions);
-
-
- /* 3. Add the guard that controls whether the second loop is executed.
- Resulting CFG would be:
-
- bb_before_first_loop:
- if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
- GOTO first-loop
-
- first_loop:
- do {
- } while ...
-
- bb_between_loops:
- if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
- GOTO bb_before_second_loop
-
- bb_before_second_loop:
-
- second_loop:
- do {
- } while ...
-
- bb_after_second_loop:
-
- orig_exit_bb:
- */
-
- bb_between_loops = new_exit_bb;
- bb_after_second_loop = split_edge (second_loop->single_exit);
- add_bb_to_loop (bb_after_second_loop, second_loop->outer);
-
- pre_condition =
- fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
- skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition,
- bb_after_second_loop, bb_before_first_loop);
- slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
- second_loop == new_loop, &new_exit_bb);
-
- /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
- */
- if (update_first_loop_count)
- slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
-
- BITMAP_FREE (definitions);
- delete_update_ssa ();
-
- return new_loop;
-}
-
-/* Function vect_get_loop_location.
-
- Extract the location of the loop in the source code.
- If the loop is not well formed for vectorization, an estimated
- location is calculated.
- Return the loop location if succeed and NULL if not. */
-
-LOC
-find_loop_location (struct loop *loop)
-{
- tree node = NULL_TREE;
- basic_block bb;
- block_stmt_iterator si;
-
- if (!loop)
- return UNKNOWN_LOC;
-
- node = get_loop_exit_condition (loop);
-
- if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node)
- && EXPR_FILENAME (node) && EXPR_LINENO (node))
- return EXPR_LOC (node);
-
- /* If we got here the loop is probably not "well formed",
- try to estimate the loop location */
-
- if (!loop->header)
- return UNKNOWN_LOC;
-
- bb = loop->header;
-
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- {
- node = bsi_stmt (si);
- if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node))
- return EXPR_LOC (node);
- }
-
- return UNKNOWN_LOC;
-}
-
-
-/*************************************************************************
- Vectorization Debug Information.
- *************************************************************************/