OSDN Git Service

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