OSDN Git Service

* tree-vrp.c (execute_vrp): Do not pass loops structure through
[pf3gnuchains/gcc-fork.git] / gcc / cfgloopmanip.c
1 /* Loop manipulation code for GNU compiler.
2    Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "obstack.h"
28 #include "basic-block.h"
29 #include "cfgloop.h"
30 #include "cfglayout.h"
31 #include "cfghooks.h"
32 #include "output.h"
33
34 static void duplicate_subloops (struct loop *, struct loop *);
35 static void copy_loops_to (struct loop **, int,
36                            struct loop *);
37 static void loop_redirect_edge (edge, basic_block);
38 static bool loop_delete_branch_edge (edge, int);
39 static void remove_bbs (basic_block *, int);
40 static bool rpe_enum_p (basic_block, void *);
41 static int find_path (edge, basic_block **);
42 static bool alp_enum_p (basic_block, void *);
43 static void fix_loop_placements (struct loop *, bool *);
44 static bool fix_bb_placement (basic_block);
45 static void fix_bb_placements (basic_block, bool *);
46 static void place_new_loop (struct loop *);
47 static void scale_loop_frequencies (struct loop *, int, int);
48 static basic_block create_preheader (struct loop *, int);
49 static void unloop (struct loop *, bool *);
50
51 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
52
53 /* Checks whether basic block BB is dominated by DATA.  */
54 static bool
55 rpe_enum_p (basic_block bb, void *data)
56 {
57   return dominated_by_p (CDI_DOMINATORS, bb, data);
58 }
59
60 /* Remove basic blocks BBS.  NBBS is the number of the basic blocks.  */
61
62 static void
63 remove_bbs (basic_block *bbs, int nbbs)
64 {
65   int i;
66
67   for (i = 0; i < nbbs; i++)
68     delete_basic_block (bbs[i]);
69 }
70
71 /* Find path -- i.e. the basic blocks dominated by edge E and put them
72    into array BBS, that will be allocated large enough to contain them.
73    E->dest must have exactly one predecessor for this to work (it is
74    easy to achieve and we do not put it here because we do not want to
75    alter anything by this function).  The number of basic blocks in the
76    path is returned.  */
77 static int
78 find_path (edge e, basic_block **bbs)
79 {
80   gcc_assert (EDGE_COUNT (e->dest->preds) <= 1);
81
82   /* Find bbs in the path.  */
83   *bbs = XCNEWVEC (basic_block, n_basic_blocks);
84   return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
85                              n_basic_blocks, e->dest);
86 }
87
88 /* Fix placement of basic block BB inside loop hierarchy --
89    Let L be a loop to that BB belongs.  Then every successor of BB must either
90      1) belong to some superloop of loop L, or
91      2) be a header of loop K such that K->outer is superloop of L
92    Returns true if we had to move BB into other loop to enforce this condition,
93    false if the placement of BB was already correct (provided that placements
94    of its successors are correct).  */
95 static bool
96 fix_bb_placement (basic_block bb)
97 {
98   edge e;
99   edge_iterator ei;
100   struct loop *loop = current_loops->tree_root, *act;
101
102   FOR_EACH_EDGE (e, ei, bb->succs)
103     {
104       if (e->dest == EXIT_BLOCK_PTR)
105         continue;
106
107       act = e->dest->loop_father;
108       if (act->header == e->dest)
109         act = act->outer;
110
111       if (flow_loop_nested_p (loop, act))
112         loop = act;
113     }
114
115   if (loop == bb->loop_father)
116     return false;
117
118   remove_bb_from_loops (bb);
119   add_bb_to_loop (bb, loop);
120
121   return true;
122 }
123
124 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
125    enforce condition condition stated in description of fix_bb_placement. We
126    start from basic block FROM that had some of its successors removed, so that
127    his placement no longer has to be correct, and iteratively fix placement of
128    its predecessors that may change if placement of FROM changed.  Also fix
129    placement of subloops of FROM->loop_father, that might also be altered due
130    to this change; the condition for them is similar, except that instead of
131    successors we consider edges coming out of the loops.
132  
133    If the changes may invalidate the information about irreducible regions,
134    IRRED_INVALIDATED is set to true.  */
135
136 static void
137 fix_bb_placements (basic_block from,
138                    bool *irred_invalidated)
139 {
140   sbitmap in_queue;
141   basic_block *queue, *qtop, *qbeg, *qend;
142   struct loop *base_loop;
143   edge e;
144
145   /* We pass through blocks back-reachable from FROM, testing whether some
146      of their successors moved to outer loop.  It may be necessary to
147      iterate several times, but it is finite, as we stop unless we move
148      the basic block up the loop structure.  The whole story is a bit
149      more complicated due to presence of subloops, those are moved using
150      fix_loop_placement.  */
151
152   base_loop = from->loop_father;
153   if (base_loop == current_loops->tree_root)
154     return;
155
156   in_queue = sbitmap_alloc (last_basic_block);
157   sbitmap_zero (in_queue);
158   SET_BIT (in_queue, from->index);
159   /* Prevent us from going out of the base_loop.  */
160   SET_BIT (in_queue, base_loop->header->index);
161
162   queue = XNEWVEC (basic_block, base_loop->num_nodes + 1);
163   qtop = queue + base_loop->num_nodes + 1;
164   qbeg = queue;
165   qend = queue + 1;
166   *qbeg = from;
167
168   while (qbeg != qend)
169     {
170       edge_iterator ei;
171       from = *qbeg;
172       qbeg++;
173       if (qbeg == qtop)
174         qbeg = queue;
175       RESET_BIT (in_queue, from->index);
176
177       if (from->loop_father->header == from)
178         {
179           /* Subloop header, maybe move the loop upward.  */
180           if (!fix_loop_placement (from->loop_father))
181             continue;
182         }
183       else
184         {
185           /* Ordinary basic block.  */
186           if (!fix_bb_placement (from))
187             continue;
188         }
189
190       FOR_EACH_EDGE (e, ei, from->succs)
191         {
192           if (e->flags & EDGE_IRREDUCIBLE_LOOP)
193             *irred_invalidated = true;
194         }
195
196       /* Something has changed, insert predecessors into queue.  */
197       FOR_EACH_EDGE (e, ei, from->preds)
198         {
199           basic_block pred = e->src;
200           struct loop *nca;
201
202           if (e->flags & EDGE_IRREDUCIBLE_LOOP)
203             *irred_invalidated = true;
204
205           if (TEST_BIT (in_queue, pred->index))
206             continue;
207
208           /* If it is subloop, then it either was not moved, or
209              the path up the loop tree from base_loop do not contain
210              it.  */
211           nca = find_common_loop (pred->loop_father, base_loop);
212           if (pred->loop_father != base_loop
213               && (nca == base_loop
214                   || nca != pred->loop_father))
215             pred = pred->loop_father->header;
216           else if (!flow_loop_nested_p (from->loop_father, pred->loop_father))
217             {
218               /* No point in processing it.  */
219               continue;
220             }
221
222           if (TEST_BIT (in_queue, pred->index))
223             continue;
224
225           /* Schedule the basic block.  */
226           *qend = pred;
227           qend++;
228           if (qend == qtop)
229             qend = queue;
230           SET_BIT (in_queue, pred->index);
231         }
232     }
233   free (in_queue);
234   free (queue);
235 }
236
237 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
238    and update loop structures and dominators.  Return true if we were able
239    to remove the path, false otherwise (and nothing is affected then).  */
240 bool
241 remove_path (edge e)
242 {
243   edge ae;
244   basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
245   int i, nrem, n_bord_bbs, n_dom_bbs, nreml;
246   sbitmap seen;
247   bool deleted, irred_invalidated = false;
248   struct loop **deleted_loop;
249
250   if (!loop_delete_branch_edge (e, 0))
251     return false;
252
253   /* Keep track of whether we need to update information about irreducible
254      regions.  This is the case if the removed area is a part of the
255      irreducible region, or if the set of basic blocks that belong to a loop
256      that is inside an irreducible region is changed, or if such a loop is
257      removed.  */
258   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
259     irred_invalidated = true;
260
261   /* We need to check whether basic blocks are dominated by the edge
262      e, but we only have basic block dominators.  This is easy to
263      fix -- when e->dest has exactly one predecessor, this corresponds
264      to blocks dominated by e->dest, if not, split the edge.  */
265   if (!single_pred_p (e->dest))
266     e = single_pred_edge (split_edge (e));
267
268   /* It may happen that by removing path we remove one or more loops
269      we belong to.  In this case first unloop the loops, then proceed
270      normally.   We may assume that e->dest is not a header of any loop,
271      as it now has exactly one predecessor.  */
272   while (e->src->loop_father->outer
273          && dominated_by_p (CDI_DOMINATORS,
274                             e->src->loop_father->latch, e->dest))
275     unloop (e->src->loop_father, &irred_invalidated);
276
277   /* Identify the path.  */
278   nrem = find_path (e, &rem_bbs);
279
280   n_bord_bbs = 0;
281   bord_bbs = XCNEWVEC (basic_block, n_basic_blocks);
282   seen = sbitmap_alloc (last_basic_block);
283   sbitmap_zero (seen);
284
285   /* Find "border" hexes -- i.e. those with predecessor in removed path.  */
286   for (i = 0; i < nrem; i++)
287     SET_BIT (seen, rem_bbs[i]->index);
288   for (i = 0; i < nrem; i++)
289     {
290       edge_iterator ei;
291       bb = rem_bbs[i];
292       FOR_EACH_EDGE (ae, ei, rem_bbs[i]->succs)
293         if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
294           {
295             SET_BIT (seen, ae->dest->index);
296             bord_bbs[n_bord_bbs++] = ae->dest;
297           
298             if (ae->flags & EDGE_IRREDUCIBLE_LOOP)
299               irred_invalidated = true;
300           }
301     }
302
303   /* Remove the path.  */
304   from = e->src;
305   deleted = loop_delete_branch_edge (e, 1);
306   gcc_assert (deleted);
307   dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
308
309   /* Cancel loops contained in the path.  */
310   deleted_loop = XNEWVEC (struct loop *, nrem);
311   nreml = 0;
312   for (i = 0; i < nrem; i++)
313     if (rem_bbs[i]->loop_father->header == rem_bbs[i])
314       deleted_loop[nreml++] = rem_bbs[i]->loop_father;
315
316   remove_bbs (rem_bbs, nrem);
317   free (rem_bbs);
318
319   for (i = 0; i < nreml; i++)
320     cancel_loop_tree (deleted_loop[i]);
321   free (deleted_loop);
322
323   /* Find blocks whose dominators may be affected.  */
324   n_dom_bbs = 0;
325   sbitmap_zero (seen);
326   for (i = 0; i < n_bord_bbs; i++)
327     {
328       basic_block ldom;
329
330       bb = get_immediate_dominator (CDI_DOMINATORS, bord_bbs[i]);
331       if (TEST_BIT (seen, bb->index))
332         continue;
333       SET_BIT (seen, bb->index);
334
335       for (ldom = first_dom_son (CDI_DOMINATORS, bb);
336            ldom;
337            ldom = next_dom_son (CDI_DOMINATORS, ldom))
338         if (!dominated_by_p (CDI_DOMINATORS, from, ldom))
339           dom_bbs[n_dom_bbs++] = ldom;
340     }
341
342   free (seen);
343
344   /* Recount dominators.  */
345   iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
346   free (dom_bbs);
347   free (bord_bbs);
348
349   /* Fix placements of basic blocks inside loops and the placement of
350      loops in the loop tree.  */
351   fix_bb_placements (from, &irred_invalidated);
352   fix_loop_placements (from->loop_father, &irred_invalidated);
353
354   if (irred_invalidated
355       && (current_loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) != 0)
356     mark_irreducible_loops ();
357
358   return true;
359 }
360
361 /* Predicate for enumeration in add_loop.  */
362 static bool
363 alp_enum_p (basic_block bb, void *alp_header)
364 {
365   return bb != (basic_block) alp_header;
366 }
367
368 /* Given LOOP structure with filled header and latch, find the body of the
369    corresponding loop and add it to loops tree.  Insert the LOOP as a son of
370    outer.  */
371
372 static void
373 add_loop (struct loop *loop, struct loop *outer)
374 {
375   basic_block *bbs;
376   int i, n;
377
378   /* Add it to loop structure.  */
379   place_new_loop (loop);
380   flow_loop_tree_node_add (outer, loop);
381
382   /* Find its nodes.  */
383   bbs = XCNEWVEC (basic_block, n_basic_blocks);
384   n = dfs_enumerate_from (loop->latch, 1, alp_enum_p,
385                           bbs, n_basic_blocks, loop->header);
386
387   for (i = 0; i < n; i++)
388     {
389       remove_bb_from_loops (bbs[i]);
390       add_bb_to_loop (bbs[i], loop);
391     }
392   remove_bb_from_loops (loop->header);
393   add_bb_to_loop (loop->header, loop);
394
395   free (bbs);
396 }
397
398 /* Multiply all frequencies in LOOP by NUM/DEN.  */
399 static void
400 scale_loop_frequencies (struct loop *loop, int num, int den)
401 {
402   basic_block *bbs;
403
404   bbs = get_loop_body (loop);
405   scale_bbs_frequencies_int (bbs, loop->num_nodes, num, den);
406   free (bbs);
407 }
408
409 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
410    latch to header and update loop tree and dominators
411    accordingly. Everything between them plus LATCH_EDGE destination must
412    be dominated by HEADER_EDGE destination, and back-reachable from
413    LATCH_EDGE source.  HEADER_EDGE is redirected to basic block SWITCH_BB,
414    FALSE_EDGE of SWITCH_BB to original destination of HEADER_EDGE and
415    TRUE_EDGE of SWITCH_BB to original destination of LATCH_EDGE.
416    Returns newly created loop.  */
417
418 struct loop *
419 loopify (edge latch_edge, edge header_edge,
420          basic_block switch_bb, edge true_edge, edge false_edge,
421          bool redirect_all_edges)
422 {
423   basic_block succ_bb = latch_edge->dest;
424   basic_block pred_bb = header_edge->src;
425   basic_block *dom_bbs, *body;
426   unsigned n_dom_bbs, i;
427   sbitmap seen;
428   struct loop *loop = XCNEW (struct loop);
429   struct loop *outer = succ_bb->loop_father->outer;
430   int freq, prob, tot_prob;
431   gcov_type cnt;
432   edge e;
433   edge_iterator ei;
434
435   loop->header = header_edge->dest;
436   loop->latch = latch_edge->src;
437
438   freq = EDGE_FREQUENCY (header_edge);
439   cnt = header_edge->count;
440   prob = EDGE_SUCC (switch_bb, 0)->probability;
441   tot_prob = prob + EDGE_SUCC (switch_bb, 1)->probability;
442   if (tot_prob == 0)
443     tot_prob = 1;
444
445   /* Redirect edges.  */
446   loop_redirect_edge (latch_edge, loop->header);
447   loop_redirect_edge (true_edge, succ_bb);
448
449   /* During loop versioning, one of the switch_bb edge is already properly
450      set. Do not redirect it again unless redirect_all_edges is true.  */
451   if (redirect_all_edges)
452     {
453       loop_redirect_edge (header_edge, switch_bb);
454       loop_redirect_edge (false_edge, loop->header);
455
456       /* Update dominators.  */
457       set_immediate_dominator (CDI_DOMINATORS, switch_bb, pred_bb);
458       set_immediate_dominator (CDI_DOMINATORS, loop->header, switch_bb);
459     }
460
461   set_immediate_dominator (CDI_DOMINATORS, succ_bb, switch_bb);
462
463   /* Compute new loop.  */
464   add_loop (loop, outer);
465
466   /* Add switch_bb to appropriate loop.  */
467   if (switch_bb->loop_father)
468     remove_bb_from_loops (switch_bb);
469   add_bb_to_loop (switch_bb, outer);
470
471   /* Fix frequencies.  */
472   switch_bb->frequency = freq;
473   switch_bb->count = cnt;
474   FOR_EACH_EDGE (e, ei, switch_bb->succs)
475     e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE;
476   scale_loop_frequencies (loop, prob, tot_prob);
477   scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob);
478
479   /* Update dominators of blocks outside of LOOP.  */
480   dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
481   n_dom_bbs = 0;
482   seen = sbitmap_alloc (last_basic_block);
483   sbitmap_zero (seen);
484   body = get_loop_body (loop);
485
486   for (i = 0; i < loop->num_nodes; i++)
487     SET_BIT (seen, body[i]->index);
488
489   for (i = 0; i < loop->num_nodes; i++)
490     {
491       basic_block ldom;
492
493       for (ldom = first_dom_son (CDI_DOMINATORS, body[i]);
494            ldom;
495            ldom = next_dom_son (CDI_DOMINATORS, ldom))
496         if (!TEST_BIT (seen, ldom->index))
497           {
498             SET_BIT (seen, ldom->index);
499             dom_bbs[n_dom_bbs++] = ldom;
500           }
501     }
502
503   iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
504
505   free (body);
506   free (seen);
507   free (dom_bbs);
508
509   return loop;
510 }
511
512 /* Remove the latch edge of a LOOP and update loops to indicate that
513    the LOOP was removed.  After this function, original loop latch will
514    have no successor, which caller is expected to fix somehow.
515
516    If this may cause the information about irreducible regions to become
517    invalid, IRRED_INVALIDATED is set to true.  */
518
519 static void
520 unloop (struct loop *loop, bool *irred_invalidated)
521 {
522   basic_block *body;
523   struct loop *ploop;
524   unsigned i, n;
525   basic_block latch = loop->latch;
526   bool dummy = false;
527
528   if (loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
529     *irred_invalidated = true;
530
531   /* This is relatively straightforward.  The dominators are unchanged, as
532      loop header dominates loop latch, so the only thing we have to care of
533      is the placement of loops and basic blocks inside the loop tree.  We
534      move them all to the loop->outer, and then let fix_bb_placements do
535      its work.  */
536
537   body = get_loop_body (loop);
538   n = loop->num_nodes;
539   for (i = 0; i < n; i++)
540     if (body[i]->loop_father == loop)
541       {
542         remove_bb_from_loops (body[i]);
543         add_bb_to_loop (body[i], loop->outer);
544       }
545   free(body);
546
547   while (loop->inner)
548     {
549       ploop = loop->inner;
550       flow_loop_tree_node_remove (ploop);
551       flow_loop_tree_node_add (loop->outer, ploop);
552     }
553
554   /* Remove the loop and free its data.  */
555   flow_loop_tree_node_remove (loop);
556   current_loops->parray[loop->num] = NULL;
557   flow_loop_free (loop);
558
559   remove_edge (single_succ_edge (latch));
560
561   /* We do not pass IRRED_INVALIDATED to fix_bb_placements here, as even if
562      there is an irreducible region inside the cancelled loop, the flags will
563      be still correct.  */
564   fix_bb_placements (latch, &dummy);
565 }
566
567 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
568    FATHER of LOOP such that all of the edges coming out of LOOP belong to
569    FATHER, and set it as outer loop of LOOP.  Return true if placement of
570    LOOP changed.  */
571
572 int
573 fix_loop_placement (struct loop *loop)
574 {
575   basic_block *body;
576   unsigned i;
577   edge e;
578   edge_iterator ei;
579   struct loop *father = loop->pred[0], *act;
580
581   body = get_loop_body (loop);
582   for (i = 0; i < loop->num_nodes; i++)
583     FOR_EACH_EDGE (e, ei, body[i]->succs)
584       if (!flow_bb_inside_loop_p (loop, e->dest))
585         {
586           act = find_common_loop (loop, e->dest->loop_father);
587           if (flow_loop_nested_p (father, act))
588             father = act;
589         }
590   free (body);
591
592   if (father != loop->outer)
593     {
594       for (act = loop->outer; act != father; act = act->outer)
595         act->num_nodes -= loop->num_nodes;
596       flow_loop_tree_node_remove (loop);
597       flow_loop_tree_node_add (father, loop);
598       return 1;
599     }
600   return 0;
601 }
602
603 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
604    condition stated in description of fix_loop_placement holds for them.
605    It is used in case when we removed some edges coming out of LOOP, which
606    may cause the right placement of LOOP inside loop tree to change.
607  
608    IRRED_INVALIDATED is set to true if a change in the loop structures might
609    invalidate the information about irreducible regions.  */
610
611 static void
612 fix_loop_placements (struct loop *loop, bool *irred_invalidated)
613 {
614   struct loop *outer;
615
616   while (loop->outer)
617     {
618       outer = loop->outer;
619       if (!fix_loop_placement (loop))
620         break;
621
622       /* Changing the placement of a loop in the loop tree may alter the
623          validity of condition 2) of the description of fix_bb_placement
624          for its preheader, because the successor is the header and belongs
625          to the loop.  So call fix_bb_placements to fix up the placement
626          of the preheader and (possibly) of its predecessors.  */
627       fix_bb_placements (loop_preheader_edge (loop)->src,
628                          irred_invalidated);
629       loop = outer;
630     }
631 }
632
633 /* Creates place for a new LOOP in loops structure.  */
634 static void
635 place_new_loop (struct loop *loop)
636 {
637   current_loops->parray =
638     xrealloc (current_loops->parray, (current_loops->num + 1) * sizeof (struct loop *));
639   current_loops->parray[current_loops->num] = loop;
640
641   loop->num = current_loops->num++;
642 }
643
644 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
645    created loop into loops structure.  */
646 struct loop *
647 duplicate_loop (struct loop *loop, struct loop *target)
648 {
649   struct loop *cloop;
650   cloop = XCNEW (struct loop);
651   place_new_loop (cloop);
652
653   /* Mark the new loop as copy of LOOP.  */
654   loop->copy = cloop;
655
656   /* Add it to target.  */
657   flow_loop_tree_node_add (target, cloop);
658
659   return cloop;
660 }
661
662 /* Copies structure of subloops of LOOP into TARGET loop, placing
663    newly created loops into loop tree.  */
664 static void
665 duplicate_subloops (struct loop *loop, struct loop *target)
666 {
667   struct loop *aloop, *cloop;
668
669   for (aloop = loop->inner; aloop; aloop = aloop->next)
670     {
671       cloop = duplicate_loop (aloop, target);
672       duplicate_subloops (aloop, cloop);
673     }
674 }
675
676 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
677    into TARGET loop, placing newly created loops into loop tree.  */
678 static void
679 copy_loops_to (struct loop **copied_loops, int n, struct loop *target)
680 {
681   struct loop *aloop;
682   int i;
683
684   for (i = 0; i < n; i++)
685     {
686       aloop = duplicate_loop (copied_loops[i], target);
687       duplicate_subloops (copied_loops[i], aloop);
688     }
689 }
690
691 /* Redirects edge E to basic block DEST.  */
692 static void
693 loop_redirect_edge (edge e, basic_block dest)
694 {
695   if (e->dest == dest)
696     return;
697
698   redirect_edge_and_branch_force (e, dest);
699 }
700
701 /* Deletes edge E from a branch if possible.  Unless REALLY_DELETE is set,
702    just test whether it is possible to remove the edge.  */
703 static bool
704 loop_delete_branch_edge (edge e, int really_delete)
705 {
706   basic_block src = e->src;
707   basic_block newdest;
708   int irr;
709   edge snd;
710
711   gcc_assert (EDGE_COUNT (src->succs) > 1);
712
713   /* Cannot handle more than two exit edges.  */
714   if (EDGE_COUNT (src->succs) > 2)
715     return false;
716   /* And it must be just a simple branch.  */
717   if (!any_condjump_p (BB_END (src)))
718     return false;
719
720   snd = e == EDGE_SUCC (src, 0) ? EDGE_SUCC (src, 1) : EDGE_SUCC (src, 0);
721   newdest = snd->dest;
722   if (newdest == EXIT_BLOCK_PTR)
723     return false;
724
725   /* Hopefully the above conditions should suffice.  */
726   if (!really_delete)
727     return true;
728
729   /* Redirecting behaves wrongly wrto this flag.  */
730   irr = snd->flags & EDGE_IRREDUCIBLE_LOOP;
731
732   if (!redirect_edge_and_branch (e, newdest))
733     return false;
734   single_succ_edge (src)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
735   single_succ_edge (src)->flags |= irr;
736
737   return true;
738 }
739
740 /* Check whether LOOP's body can be duplicated.  */
741 bool
742 can_duplicate_loop_p (struct loop *loop)
743 {
744   int ret;
745   basic_block *bbs = get_loop_body (loop);
746
747   ret = can_copy_bbs_p (bbs, loop->num_nodes);
748   free (bbs);
749
750   return ret;
751 }
752
753 /* The NBBS blocks in BBS will get duplicated and the copies will be placed
754    to LOOP.  Update the single_exit information in superloops of LOOP.  */
755
756 static void
757 update_single_exits_after_duplication (basic_block *bbs, unsigned nbbs,
758                                        struct loop *loop)
759 {
760   unsigned i;
761
762   for (i = 0; i < nbbs; i++)
763     bbs[i]->flags |= BB_DUPLICATED;
764
765   for (; loop->outer; loop = loop->outer)
766     {
767       if (!single_exit (loop))
768         continue;
769
770       if (single_exit (loop)->src->flags & BB_DUPLICATED)
771         set_single_exit (loop, NULL);
772     }
773
774   for (i = 0; i < nbbs; i++)
775     bbs[i]->flags &= ~BB_DUPLICATED;
776 }
777
778 /* Updates single exit information for the copy of LOOP.  */
779
780 static void
781 update_single_exit_for_duplicated_loop (struct loop *loop)
782 {
783   struct loop *copy = loop->copy;
784   basic_block src, dest;
785   edge exit = single_exit (loop);
786
787   if (!exit)
788     return;
789
790   src = get_bb_copy (exit->src);
791   dest = exit->dest;
792   if (dest->flags & BB_DUPLICATED)
793     dest = get_bb_copy (dest);
794
795   exit = find_edge (src, dest);
796   gcc_assert (exit != NULL);
797   set_single_exit (copy, exit);
798 }
799
800 /* Updates single exit information for copies of ORIG_LOOPS and their subloops.
801    N is the number of the loops in the ORIG_LOOPS array.  */
802
803 static void
804 update_single_exit_for_duplicated_loops (struct loop *orig_loops[], unsigned n)
805 {
806   unsigned i;
807
808   for (i = 0; i < n; i++)
809     update_single_exit_for_duplicated_loop (orig_loops[i]);
810 }
811
812 /* Duplicates body of LOOP to given edge E NDUPL times.  Takes care of updating
813    loop structure and dominators.  E's destination must be LOOP header for
814    this to work, i.e. it must be entry or latch edge of this loop; these are
815    unique, as the loops must have preheaders for this function to work
816    correctly (in case E is latch, the function unrolls the loop, if E is entry
817    edge, it peels the loop).  Store edges created by copying ORIG edge from
818    copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
819    original LOOP body, the other copies are numbered in order given by control
820    flow through them) into TO_REMOVE array.  Returns false if duplication is
821    impossible.  */
822 bool
823 duplicate_loop_to_header_edge (struct loop *loop, edge e,
824                                unsigned int ndupl, sbitmap wont_exit,
825                                edge orig, edge *to_remove,
826                                unsigned int *n_to_remove, int flags)
827 {
828   struct loop *target, *aloop;
829   struct loop **orig_loops;
830   unsigned n_orig_loops;
831   basic_block header = loop->header, latch = loop->latch;
832   basic_block *new_bbs, *bbs, *first_active;
833   basic_block new_bb, bb, first_active_latch = NULL;
834   edge ae, latch_edge;
835   edge spec_edges[2], new_spec_edges[2];
836 #define SE_LATCH 0
837 #define SE_ORIG 1
838   unsigned i, j, n;
839   int is_latch = (latch == e->src);
840   int scale_act = 0, *scale_step = NULL, scale_main = 0;
841   int p, freq_in, freq_le, freq_out_orig;
842   int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
843   int add_irreducible_flag;
844   basic_block place_after;
845
846   gcc_assert (e->dest == loop->header);
847   gcc_assert (ndupl > 0);
848
849   if (orig)
850     {
851       /* Orig must be edge out of the loop.  */
852       gcc_assert (flow_bb_inside_loop_p (loop, orig->src));
853       gcc_assert (!flow_bb_inside_loop_p (loop, orig->dest));
854     }
855
856   n = loop->num_nodes;
857   bbs = get_loop_body_in_dom_order (loop);
858   gcc_assert (bbs[0] == loop->header);
859   gcc_assert (bbs[n  - 1] == loop->latch);
860
861   /* Check whether duplication is possible.  */
862   if (!can_copy_bbs_p (bbs, loop->num_nodes))
863     {
864       free (bbs);
865       return false;
866     }
867   new_bbs = XNEWVEC (basic_block, loop->num_nodes);
868
869   /* In case we are doing loop peeling and the loop is in the middle of
870      irreducible region, the peeled copies will be inside it too.  */
871   add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
872   gcc_assert (!is_latch || !add_irreducible_flag);
873
874   /* Find edge from latch.  */
875   latch_edge = loop_latch_edge (loop);
876
877   if (flags & DLTHE_FLAG_UPDATE_FREQ)
878     {
879       /* Calculate coefficients by that we have to scale frequencies
880          of duplicated loop bodies.  */
881       freq_in = header->frequency;
882       freq_le = EDGE_FREQUENCY (latch_edge);
883       if (freq_in == 0)
884         freq_in = 1;
885       if (freq_in < freq_le)
886         freq_in = freq_le;
887       freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le;
888       if (freq_out_orig > freq_in - freq_le)
889         freq_out_orig = freq_in - freq_le;
890       prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
891       prob_pass_wont_exit =
892               RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in);
893
894       scale_step = XNEWVEC (int, ndupl);
895
896         for (i = 1; i <= ndupl; i++)
897           scale_step[i - 1] = TEST_BIT (wont_exit, i)
898                                 ? prob_pass_wont_exit
899                                 : prob_pass_thru;
900
901       /* Complete peeling is special as the probability of exit in last
902          copy becomes 1.  */
903       if (flags & DLTHE_FLAG_COMPLETTE_PEEL)
904         {
905           int wanted_freq = EDGE_FREQUENCY (e);
906
907           if (wanted_freq > freq_in)
908             wanted_freq = freq_in;
909
910           gcc_assert (!is_latch);
911           /* First copy has frequency of incoming edge.  Each subsequent
912              frequency should be reduced by prob_pass_wont_exit.  Caller
913              should've managed the flags so all except for original loop
914              has won't exist set.  */
915           scale_act = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
916           /* Now simulate the duplication adjustments and compute header
917              frequency of the last copy.  */
918           for (i = 0; i < ndupl; i++)
919             wanted_freq = RDIV (wanted_freq * scale_step[i], REG_BR_PROB_BASE);
920           scale_main = RDIV (wanted_freq * REG_BR_PROB_BASE, freq_in);
921         }
922       else if (is_latch)
923         {
924           prob_pass_main = TEST_BIT (wont_exit, 0)
925                                 ? prob_pass_wont_exit
926                                 : prob_pass_thru;
927           p = prob_pass_main;
928           scale_main = REG_BR_PROB_BASE;
929           for (i = 0; i < ndupl; i++)
930             {
931               scale_main += p;
932               p = RDIV (p * scale_step[i], REG_BR_PROB_BASE);
933             }
934           scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main);
935           scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE);
936         }
937       else
938         {
939           scale_main = REG_BR_PROB_BASE;
940           for (i = 0; i < ndupl; i++)
941             scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE);
942           scale_act = REG_BR_PROB_BASE - prob_pass_thru;
943         }
944       for (i = 0; i < ndupl; i++)
945         gcc_assert (scale_step[i] >= 0 && scale_step[i] <= REG_BR_PROB_BASE);
946       gcc_assert (scale_main >= 0 && scale_main <= REG_BR_PROB_BASE
947                   && scale_act >= 0  && scale_act <= REG_BR_PROB_BASE);
948     }
949
950   /* Loop the new bbs will belong to.  */
951   target = e->src->loop_father;
952
953   /* Original loops.  */
954   n_orig_loops = 0;
955   for (aloop = loop->inner; aloop; aloop = aloop->next)
956     n_orig_loops++;
957   orig_loops = XCNEWVEC (struct loop *, n_orig_loops);
958   for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
959     orig_loops[i] = aloop;
960
961   loop->copy = target;
962
963   first_active = XNEWVEC (basic_block, n);
964   if (is_latch)
965     {
966       memcpy (first_active, bbs, n * sizeof (basic_block));
967       first_active_latch = latch;
968     }
969
970   /* Update the information about single exits.  */
971   if (current_loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
972     update_single_exits_after_duplication (bbs, n, target);
973
974   /* Record exit edge in original loop body.  */
975   if (orig && TEST_BIT (wont_exit, 0))
976     to_remove[(*n_to_remove)++] = orig;
977
978   spec_edges[SE_ORIG] = orig;
979   spec_edges[SE_LATCH] = latch_edge;
980
981   place_after = e->src;
982   for (j = 0; j < ndupl; j++)
983     {
984       /* Copy loops.  */
985       copy_loops_to (orig_loops, n_orig_loops, target);
986
987       /* Copy bbs.  */
988       copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop,
989                 place_after);
990       place_after = new_spec_edges[SE_LATCH]->src;
991
992       if (current_loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
993         {
994           for (i = 0; i < n; i++)
995             bbs[i]->flags |= BB_DUPLICATED;
996           update_single_exit_for_duplicated_loops (orig_loops, n_orig_loops);
997           for (i = 0; i < n; i++)
998             bbs[i]->flags &= ~BB_DUPLICATED;
999         }
1000
1001       if (flags & DLTHE_RECORD_COPY_NUMBER)
1002         for (i = 0; i < n; i++)
1003           {
1004             gcc_assert (!new_bbs[i]->aux);
1005             new_bbs[i]->aux = (void *)(size_t)(j + 1);
1006           }
1007
1008       /* Note whether the blocks and edges belong to an irreducible loop.  */
1009       if (add_irreducible_flag)
1010         {
1011           for (i = 0; i < n; i++)
1012             new_bbs[i]->flags |= BB_DUPLICATED;
1013           for (i = 0; i < n; i++)
1014             {
1015               edge_iterator ei;
1016               new_bb = new_bbs[i];
1017               if (new_bb->loop_father == target)
1018                 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
1019
1020               FOR_EACH_EDGE (ae, ei, new_bb->succs)
1021                 if ((ae->dest->flags & BB_DUPLICATED)
1022                     && (ae->src->loop_father == target
1023                         || ae->dest->loop_father == target))
1024                   ae->flags |= EDGE_IRREDUCIBLE_LOOP;
1025             }
1026           for (i = 0; i < n; i++)
1027             new_bbs[i]->flags &= ~BB_DUPLICATED;
1028         }
1029
1030       /* Redirect the special edges.  */
1031       if (is_latch)
1032         {
1033           redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
1034           redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1035                                           loop->header);
1036           set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], latch);
1037           latch = loop->latch = new_bbs[n - 1];
1038           e = latch_edge = new_spec_edges[SE_LATCH];
1039         }
1040       else
1041         {
1042           redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1043                                           loop->header);
1044           redirect_edge_and_branch_force (e, new_bbs[0]);
1045           set_immediate_dominator (CDI_DOMINATORS, new_bbs[0], e->src);
1046           e = new_spec_edges[SE_LATCH];
1047         }
1048
1049       /* Record exit edge in this copy.  */
1050       if (orig && TEST_BIT (wont_exit, j + 1))
1051         to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG];
1052
1053       /* Record the first copy in the control flow order if it is not
1054          the original loop (i.e. in case of peeling).  */
1055       if (!first_active_latch)
1056         {
1057           memcpy (first_active, new_bbs, n * sizeof (basic_block));
1058           first_active_latch = new_bbs[n - 1];
1059         }
1060
1061       /* Set counts and frequencies.  */
1062       if (flags & DLTHE_FLAG_UPDATE_FREQ)
1063         {
1064           scale_bbs_frequencies_int (new_bbs, n, scale_act, REG_BR_PROB_BASE);
1065           scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
1066         }
1067     }
1068   free (new_bbs);
1069   free (orig_loops);
1070
1071   /* Update the original loop.  */
1072   if (!is_latch)
1073     set_immediate_dominator (CDI_DOMINATORS, e->dest, e->src);
1074   if (flags & DLTHE_FLAG_UPDATE_FREQ)
1075     {
1076       scale_bbs_frequencies_int (bbs, n, scale_main, REG_BR_PROB_BASE);
1077       free (scale_step);
1078     }
1079
1080   /* Update dominators of outer blocks if affected.  */
1081   for (i = 0; i < n; i++)
1082     {
1083       basic_block dominated, dom_bb, *dom_bbs;
1084       int n_dom_bbs,j;
1085
1086       bb = bbs[i];
1087       bb->aux = 0;
1088
1089       n_dom_bbs = get_dominated_by (CDI_DOMINATORS, bb, &dom_bbs);
1090       for (j = 0; j < n_dom_bbs; j++)
1091         {
1092           dominated = dom_bbs[j];
1093           if (flow_bb_inside_loop_p (loop, dominated))
1094             continue;
1095           dom_bb = nearest_common_dominator (
1096                         CDI_DOMINATORS, first_active[i], first_active_latch);
1097           set_immediate_dominator (CDI_DOMINATORS, dominated, dom_bb);
1098         }
1099       free (dom_bbs);
1100     }
1101   free (first_active);
1102
1103   free (bbs);
1104
1105   return true;
1106 }
1107
1108 /* A callback for make_forwarder block, to redirect all edges except for
1109    MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
1110    whether to redirect it.  */
1111
1112 static edge mfb_kj_edge;
1113 static bool
1114 mfb_keep_just (edge e)
1115 {
1116   return e != mfb_kj_edge;
1117 }
1118
1119 /* Creates a pre-header for a LOOP.  Returns newly created block.  Unless
1120    CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1121    entry; otherwise we also force preheader block to have only one successor.
1122    The function also updates dominators.  */
1123
1124 static basic_block
1125 create_preheader (struct loop *loop, int flags)
1126 {
1127   edge e, fallthru;
1128   basic_block dummy;
1129   int nentry = 0;
1130   bool irred = false;
1131   bool latch_edge_was_fallthru;
1132   edge one_succ_pred = 0;
1133   edge_iterator ei;
1134
1135   FOR_EACH_EDGE (e, ei, loop->header->preds)
1136     {
1137       if (e->src == loop->latch)
1138         continue;
1139       irred |= (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
1140       nentry++;
1141       if (single_succ_p (e->src))
1142         one_succ_pred = e;
1143     }
1144   gcc_assert (nentry);
1145   if (nentry == 1)
1146     {
1147       /* Get an edge that is different from the one from loop->latch
1148          to loop->header.  */
1149       e = EDGE_PRED (loop->header,
1150                      EDGE_PRED (loop->header, 0)->src == loop->latch);
1151
1152       if (!(flags & CP_SIMPLE_PREHEADERS) || single_succ_p (e->src))
1153         return NULL;
1154     }
1155
1156   mfb_kj_edge = loop_latch_edge (loop);
1157   latch_edge_was_fallthru = (mfb_kj_edge->flags & EDGE_FALLTHRU) != 0;
1158   fallthru = make_forwarder_block (loop->header, mfb_keep_just, NULL);
1159   dummy = fallthru->src;
1160   loop->header = fallthru->dest;
1161
1162   /* Try to be clever in placing the newly created preheader.  The idea is to
1163      avoid breaking any "fallthruness" relationship between blocks.
1164
1165      The preheader was created just before the header and all incoming edges
1166      to the header were redirected to the preheader, except the latch edge.
1167      So the only problematic case is when this latch edge was a fallthru
1168      edge: it is not anymore after the preheader creation so we have broken
1169      the fallthruness.  We're therefore going to look for a better place.  */
1170   if (latch_edge_was_fallthru)
1171     {
1172       if (one_succ_pred)
1173         e = one_succ_pred;
1174       else
1175         e = EDGE_PRED (dummy, 0);
1176
1177       move_block_after (dummy, e->src);
1178     }
1179
1180   if (irred)
1181     {
1182       dummy->flags |= BB_IRREDUCIBLE_LOOP;
1183       single_succ_edge (dummy)->flags |= EDGE_IRREDUCIBLE_LOOP;
1184     }
1185
1186   if (dump_file)
1187     fprintf (dump_file, "Created preheader block for loop %i\n",
1188              loop->num);
1189
1190   return dummy;
1191 }
1192
1193 /* Create preheaders for each loop; for meaning of FLAGS see create_preheader.  */
1194
1195 void
1196 create_preheaders (int flags)
1197 {
1198   unsigned i;
1199   for (i = 1; i < current_loops->num; i++)
1200     create_preheader (current_loops->parray[i], flags);
1201   current_loops->state |= LOOPS_HAVE_PREHEADERS;
1202 }
1203
1204 /* Forces all loop latches to have only single successor.  */
1205
1206 void
1207 force_single_succ_latches (void)
1208 {
1209   unsigned i;
1210   struct loop *loop;
1211   edge e;
1212
1213   for (i = 1; i < current_loops->num; i++)
1214     {
1215       loop = current_loops->parray[i];
1216       if (loop->latch != loop->header && single_succ_p (loop->latch))
1217         continue;
1218
1219       e = find_edge (loop->latch, loop->header);
1220
1221       split_edge (e);
1222     }
1223   current_loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
1224 }
1225
1226 /* This function is called from loop_version.  It splits the entry edge
1227    of the loop we want to version, adds the versioning condition, and
1228    adjust the edges to the two versions of the loop appropriately.
1229    e is an incoming edge. Returns the basic block containing the
1230    condition.
1231
1232    --- edge e ---- > [second_head]
1233
1234    Split it and insert new conditional expression and adjust edges.
1235
1236     --- edge e ---> [cond expr] ---> [first_head]
1237                         |
1238                         +---------> [second_head]
1239 */
1240
1241 static basic_block
1242 lv_adjust_loop_entry_edge (basic_block first_head,
1243                            basic_block second_head,
1244                            edge e,
1245                            void *cond_expr)
1246 {
1247   basic_block new_head = NULL;
1248   edge e1;
1249
1250   gcc_assert (e->dest == second_head);
1251
1252   /* Split edge 'e'. This will create a new basic block, where we can
1253      insert conditional expr.  */
1254   new_head = split_edge (e);
1255
1256
1257   lv_add_condition_to_bb (first_head, second_head, new_head,
1258                           cond_expr);
1259
1260   /* Don't set EDGE_TRUE_VALUE in RTL mode, as it's invalid there.  */
1261   e1 = make_edge (new_head, first_head,
1262                   current_ir_type () == IR_GIMPLE ? EDGE_TRUE_VALUE : 0);
1263   set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
1264   set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
1265
1266   /* Adjust loop header phi nodes.  */
1267   lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
1268
1269   return new_head;
1270 }
1271
1272 /* Main entry point for Loop Versioning transformation.
1273
1274    This transformation given a condition and a loop, creates
1275    -if (condition) { loop_copy1 } else { loop_copy2 },
1276    where loop_copy1 is the loop transformed in one way, and loop_copy2
1277    is the loop transformed in another way (or unchanged). 'condition'
1278    may be a run time test for things that were not resolved by static
1279    analysis (overlapping ranges (anti-aliasing), alignment, etc.).
1280
1281    If PLACE_AFTER is true, we place the new loop after LOOP in the
1282    instruction stream, otherwise it is placed before LOOP.  */
1283
1284 struct loop *
1285 loop_version (struct loop *loop,
1286               void *cond_expr, basic_block *condition_bb,
1287               bool place_after)
1288 {
1289   basic_block first_head, second_head;
1290   edge entry, latch_edge, exit, true_edge, false_edge;
1291   int irred_flag;
1292   struct loop *nloop;
1293   basic_block cond_bb;
1294
1295   /* CHECKME: Loop versioning does not handle nested loop at this point.  */
1296   if (loop->inner)
1297     return NULL;
1298
1299   /* Record entry and latch edges for the loop */
1300   entry = loop_preheader_edge (loop);
1301   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
1302   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
1303
1304   /* Note down head of loop as first_head.  */
1305   first_head = entry->dest;
1306
1307   /* Duplicate loop.  */
1308   if (!cfg_hook_duplicate_loop_to_header_edge (loop, entry, 1,
1309                                                NULL, NULL, NULL, NULL, 0))
1310     return NULL;
1311
1312   /* After duplication entry edge now points to new loop head block.
1313      Note down new head as second_head.  */
1314   second_head = entry->dest;
1315
1316   /* Split loop entry edge and insert new block with cond expr.  */
1317   cond_bb =  lv_adjust_loop_entry_edge (first_head, second_head,
1318                                         entry, cond_expr);
1319   if (condition_bb)
1320     *condition_bb = cond_bb;
1321
1322   if (!cond_bb)
1323     {
1324       entry->flags |= irred_flag;
1325       return NULL;
1326     }
1327
1328   latch_edge = single_succ_edge (get_bb_copy (loop->latch));
1329
1330   extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1331   nloop = loopify (latch_edge,
1332                    single_pred_edge (get_bb_copy (loop->header)),
1333                    cond_bb, true_edge, false_edge,
1334                    false /* Do not redirect all edges.  */);
1335
1336   exit = single_exit (loop);
1337   if (exit)
1338     set_single_exit (nloop, find_edge (get_bb_copy (exit->src), exit->dest));
1339
1340   /* loopify redirected latch_edge. Update its PENDING_STMTS.  */
1341   lv_flush_pending_stmts (latch_edge);
1342
1343   /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */
1344   extract_cond_bb_edges (cond_bb, &true_edge, &false_edge);
1345   lv_flush_pending_stmts (false_edge);
1346   /* Adjust irreducible flag.  */
1347   if (irred_flag)
1348     {
1349       cond_bb->flags |= BB_IRREDUCIBLE_LOOP;
1350       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1351       loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
1352       single_pred_edge (cond_bb)->flags |= EDGE_IRREDUCIBLE_LOOP;
1353     }
1354
1355   if (place_after)
1356     {
1357       basic_block *bbs = get_loop_body_in_dom_order (nloop), after;
1358       unsigned i;
1359
1360       after = loop->latch;
1361
1362       for (i = 0; i < nloop->num_nodes; i++)
1363         {
1364           move_block_after (bbs[i], after);
1365           after = bbs[i];
1366         }
1367       free (bbs);
1368     }
1369
1370   /* At this point condition_bb is loop predheader with two successors,
1371      first_head and second_head.   Make sure that loop predheader has only
1372      one successor.  */
1373   split_edge (loop_preheader_edge (loop));
1374   split_edge (loop_preheader_edge (nloop));
1375
1376   return nloop;
1377 }
1378
1379 /* The structure of loops might have changed.  Some loops might get removed
1380    (and their headers and latches were set to NULL), loop exists might get
1381    removed (thus the loop nesting may be wrong), and some blocks and edges
1382    were changed (so the information about bb --> loop mapping does not have
1383    to be correct).  But still for the remaining loops the header dominates
1384    the latch, and loops did not get new subloobs (new loops might possibly
1385    get created, but we are not interested in them).  Fix up the mess.
1386
1387    If CHANGED_BBS is not NULL, basic blocks whose loop has changed are
1388    marked in it.  */
1389
1390 void
1391 fix_loop_structure (bitmap changed_bbs)
1392 {
1393   basic_block bb;
1394   struct loop *loop, *ploop;
1395   unsigned i;
1396
1397   /* Remove the old bb -> loop mapping.  */
1398   FOR_EACH_BB (bb)
1399     {
1400       bb->aux = (void *) (size_t) bb->loop_father->depth;
1401       bb->loop_father = current_loops->tree_root;
1402     }
1403
1404   /* Remove the dead loops from structures.  */
1405   current_loops->tree_root->num_nodes = n_basic_blocks;
1406   for (i = 1; i < current_loops->num; i++)
1407     {
1408       loop = current_loops->parray[i];
1409       if (!loop)
1410         continue;
1411
1412       loop->num_nodes = 0;
1413       if (loop->header)
1414         continue;
1415
1416       while (loop->inner)
1417         {
1418           ploop = loop->inner;
1419           flow_loop_tree_node_remove (ploop);
1420           flow_loop_tree_node_add (loop->outer, ploop);
1421         }
1422
1423       /* Remove the loop and free its data.  */
1424       flow_loop_tree_node_remove (loop);
1425       current_loops->parray[loop->num] = NULL;
1426       flow_loop_free (loop);
1427     }
1428
1429   /* Rescan the bodies of loops, starting from the outermost.  */
1430   loop = current_loops->tree_root;
1431   while (1)
1432     {
1433       if (loop->inner)
1434         loop = loop->inner;
1435       else
1436         {
1437           while (!loop->next
1438                  && loop != current_loops->tree_root)
1439             loop = loop->outer;
1440           if (loop == current_loops->tree_root)
1441             break;
1442
1443           loop = loop->next;
1444         }
1445
1446       loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
1447     }
1448
1449   /* Now fix the loop nesting.  */
1450   for (i = 1; i < current_loops->num; i++)
1451     {
1452       loop = current_loops->parray[i];
1453       if (!loop)
1454         continue;
1455
1456       bb = loop_preheader_edge (loop)->src;
1457       if (bb->loop_father != loop->outer)
1458         {
1459           flow_loop_tree_node_remove (loop);
1460           flow_loop_tree_node_add (bb->loop_father, loop);
1461         }
1462     }
1463
1464   /* Mark the blocks whose loop has changed.  */
1465   FOR_EACH_BB (bb)
1466     {
1467       if (changed_bbs
1468           && (void *) (size_t) bb->loop_father->depth != bb->aux)
1469         bitmap_set_bit (changed_bbs, bb->index);
1470
1471       bb->aux = NULL;
1472     }
1473
1474   if (current_loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS)
1475     mark_single_exit_loops ();
1476   if (current_loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1477     mark_irreducible_loops ();
1478 }