+
+/* Uses the natural loop discovery to recreate loop notes. */
+void
+create_loop_notes (void)
+{
+ rtx insn, head, end;
+ struct loops loops;
+ struct loop *loop;
+ basic_block *first, *last, bb, pbb;
+ struct loop **stack, **top;
+
+#ifdef ENABLE_CHECKING
+ /* Verify that there really are no loop notes. */
+ for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
+ gcc_assert (!NOTE_P (insn) ||
+ NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
+#endif
+
+ flow_loops_find (&loops);
+ free_dominance_info (CDI_DOMINATORS);
+ if (loops.num > 1)
+ {
+ last = xcalloc (loops.num, sizeof (basic_block));
+
+ FOR_EACH_BB (bb)
+ {
+ for (loop = bb->loop_father; loop->outer; loop = loop->outer)
+ last[loop->num] = bb;
+ }
+
+ first = xcalloc (loops.num, sizeof (basic_block));
+ stack = xcalloc (loops.num, sizeof (struct loop *));
+ top = stack;
+
+ FOR_EACH_BB (bb)
+ {
+ for (loop = bb->loop_father; loop->outer; loop = loop->outer)
+ {
+ if (!first[loop->num])
+ {
+ *top++ = loop;
+ first[loop->num] = bb;
+ }
+
+ if (bb == last[loop->num])
+ {
+ /* Prevent loops from overlapping. */
+ while (*--top != loop)
+ last[(*top)->num] = EXIT_BLOCK_PTR;
+
+ /* If loop starts with jump into it, place the note in
+ front of the jump. */
+ insn = PREV_INSN (BB_HEAD (first[loop->num]));
+ if (insn
+ && BARRIER_P (insn))
+ insn = PREV_INSN (insn);
+
+ if (insn
+ && JUMP_P (insn)
+ && any_uncondjump_p (insn)
+ && onlyjump_p (insn))
+ {
+ pbb = BLOCK_FOR_INSN (insn);
+ gcc_assert (pbb && single_succ_p (pbb));
+
+ if (!flow_bb_inside_loop_p (loop, single_succ (pbb)))
+ insn = BB_HEAD (first[loop->num]);
+ }
+ else
+ insn = BB_HEAD (first[loop->num]);
+
+ head = BB_HEAD (first[loop->num]);
+ emit_note_before (NOTE_INSN_LOOP_BEG, insn);
+ BB_HEAD (first[loop->num]) = head;
+
+ /* Position the note correctly wrto barrier. */
+ insn = BB_END (last[loop->num]);
+ if (NEXT_INSN (insn)
+ && BARRIER_P (NEXT_INSN (insn)))
+ insn = NEXT_INSN (insn);
+
+ end = BB_END (last[loop->num]);
+ emit_note_after (NOTE_INSN_LOOP_END, insn);
+ BB_END (last[loop->num]) = end;
+ }
+ }
+ }
+
+ free (first);
+ free (last);
+ free (stack);
+ }
+ flow_loops_free (&loops);
+}
+
+/* This function is called from loop_version. It splits the entry edge
+ of the loop we want to version, adds the versioning condition, and
+ adjust the edges to the two versions of the loop appropriately.
+ e is an incoming edge. Returns the basic block containing the
+ condition.
+
+ --- edge e ---- > [second_head]
+
+ Split it and insert new conditional expression and adjust edges.
+
+ --- edge e ---> [cond expr] ---> [first_head]
+ |
+ +---------> [second_head]
+*/
+
+static basic_block
+lv_adjust_loop_entry_edge (basic_block first_head,
+ basic_block second_head,
+ edge e,
+ tree cond_expr)
+{
+ basic_block new_head = NULL;
+ edge e1;
+
+ gcc_assert (e->dest == second_head);
+
+ /* Split edge 'e'. This will create a new basic block, where we can
+ insert conditional expr. */
+ new_head = split_edge (e);
+
+
+ lv_add_condition_to_bb (first_head, second_head, new_head,
+ cond_expr);
+
+ e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
+ set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
+ set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
+
+ /* Adjust loop header phi nodes. */
+ lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
+
+ return new_head;
+}
+
+/* Main entry point for Loop Versioning transformation.
+
+This transformation given a condition and a loop, creates
+-if (condition) { loop_copy1 } else { loop_copy2 },
+where loop_copy1 is the loop transformed in one way, and loop_copy2
+is the loop transformed in another way (or unchanged). 'condition'
+may be a run time test for things that were not resolved by static
+analysis (overlapping ranges (anti-aliasing), alignment, etc.). */
+
+struct loop *
+loop_version (struct loops *loops, struct loop * loop,
+ void *cond_expr, basic_block *condition_bb)
+{
+ basic_block first_head, second_head;
+ edge entry, latch_edge, exit, true_edge, false_edge;
+ int irred_flag;
+ struct loop *nloop;
+
+ /* CHECKME: Loop versioning does not handle nested loop at this point. */
+ if (loop->inner)
+ return NULL;
+
+ /* Record entry and latch edges for the loop */
+ entry = loop_preheader_edge (loop);
+ irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
+ entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
+
+ /* Note down head of loop as first_head. */
+ first_head = entry->dest;
+
+ /* Duplicate loop. */
+ if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, loops, 1,
+ NULL, NULL, NULL, NULL, 0))
+ return NULL;
+
+ /* After duplication entry edge now points to new loop head block.
+ Note down new head as second_head. */
+ second_head = entry->dest;
+
+ /* Split loop entry edge and insert new block with cond expr. */
+ *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head,
+ entry, cond_expr);
+ if (!*condition_bb)
+ {
+ entry->flags |= irred_flag;
+ return NULL;
+ }
+
+ latch_edge = single_succ_edge (loop->latch->rbi->copy);
+
+ extract_cond_bb_edges (*condition_bb, &true_edge, &false_edge);
+ nloop = loopify (loops,
+ latch_edge,
+ single_pred_edge (loop->header->rbi->copy),
+ *condition_bb, true_edge, false_edge,
+ false /* Do not redirect all edges. */);
+
+ exit = loop->single_exit;
+ if (exit)
+ nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
+
+ /* loopify redirected latch_edge. Update its PENDING_STMTS. */
+ lv_flush_pending_stmts (latch_edge);
+
+ /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS. */
+ extract_cond_bb_edges (*condition_bb, &true_edge, &false_edge);
+ lv_flush_pending_stmts (false_edge);
+ /* Adjust irreducible flag. */
+ if (irred_flag)
+ {
+ (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
+ loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
+ single_pred_edge ((*condition_bb))->flags |= EDGE_IRREDUCIBLE_LOOP;
+ }
+
+ /* At this point condition_bb is loop predheader with two successors,
+ first_head and second_head. Make sure that loop predheader has only
+ one successor. */
+ loop_split_edge_with (loop_preheader_edge (loop), NULL);
+ loop_split_edge_with (loop_preheader_edge (nloop), NULL);
+
+ return nloop;
+}
+
+/* The structure of LOOPS might have changed. Some loops might get removed
+ (and their headers and latches were set to NULL), loop exists might get
+ removed (thus the loop nesting may be wrong), and some blocks and edges
+ were changed (so the information about bb --> loop mapping does not have
+ to be correct). But still for the remaining loops the header dominates
+ the latch, and loops did not get new subloobs (new loops might possibly
+ get created, but we are not interested in them). Fix up the mess.
+
+ If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
+ marked in it. */
+
+void
+fix_loop_structure (struct loops *loops, bitmap changed_bbs)
+{
+ basic_block bb;
+ struct loop *loop, *ploop;
+ unsigned i;
+
+ /* Remove the old bb -> loop mapping. */
+ FOR_EACH_BB (bb)
+ {
+ bb->aux = (void *) (size_t) bb->loop_father->depth;
+ bb->loop_father = loops->tree_root;
+ }
+
+ /* Remove the dead loops from structures. */
+ loops->tree_root->num_nodes = n_basic_blocks + 2;
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ loop->num_nodes = 0;
+ if (loop->header)
+ continue;
+
+ while (loop->inner)
+ {
+ ploop = loop->inner;
+ flow_loop_tree_node_remove (ploop);
+ flow_loop_tree_node_add (loop->outer, ploop);
+ }
+
+ /* Remove the loop and free its data. */
+ flow_loop_tree_node_remove (loop);
+ loops->parray[loop->num] = NULL;
+ flow_loop_free (loop);
+ }
+
+ /* Rescan the bodies of loops, starting from the outermost. */
+ loop = loops->tree_root;
+ while (1)
+ {
+ if (loop->inner)
+ loop = loop->inner;
+ else
+ {
+ while (!loop->next
+ && loop != loops->tree_root)
+ loop = loop->outer;
+ if (loop == loops->tree_root)
+ break;
+
+ loop = loop->next;
+ }
+
+ loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
+ }
+
+ /* Now fix the loop nesting. */
+ for (i = 1; i < loops->num; i++)
+ {
+ loop = loops->parray[i];
+ if (!loop)
+ continue;
+
+ bb = loop_preheader_edge (loop)->src;
+ if (bb->loop_father != loop->outer)
+ {
+ flow_loop_tree_node_remove (loop);
+ flow_loop_tree_node_add (bb->loop_father, loop);
+ }
+ }
+
+ /* Mark the blocks whose loop has changed. */
+ FOR_EACH_BB (bb)
+ {
+ if (changed_bbs
+ && (void *) (size_t) bb->loop_father->depth != bb->aux)
+ bitmap_set_bit (changed_bbs, bb->index);
+
+ bb->aux = NULL;
+ }
+
+ mark_single_exit_loops (loops);
+ mark_irreducible_loops (loops);
+}