OSDN Git Service

848abbc88d6130b2ad96886390463e7b8dfbdaab
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-loop-manip.c
1 /* High-level loop manipulation functions.
2    Copyright (C) 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
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
10    
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY 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, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "output.h"
31 #include "diagnostic.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "timevar.h"
35 #include "cfgloop.h"
36 #include "tree-pass.h"
37 #include "cfglayout.h"
38 #include "tree-scalar-evolution.h"
39
40 /* Creates an induction variable with value BASE + STEP * iteration in LOOP.
41    It is expected that neither BASE nor STEP are shared with other expressions
42    (unless the sharing rules allow this).  Use VAR as a base var_decl for it
43    (if NULL, a new temporary will be created).  The increment will occur at
44    INCR_POS (after it if AFTER is true, before it otherwise).  INCR_POS and 
45    AFTER can be computed using standard_iv_increment_position.  The ssa versions
46    of the variable before and after increment will be stored in VAR_BEFORE and
47    VAR_AFTER (unless they are NULL).  */
48
49 void
50 create_iv (tree base, tree step, tree var, struct loop *loop,
51            block_stmt_iterator *incr_pos, bool after,
52            tree *var_before, tree *var_after)
53 {
54   tree stmt, initial, step1, stmts;
55   tree vb, va;
56   enum tree_code incr_op = PLUS_EXPR;
57
58   if (!var)
59     {
60       var = create_tmp_var (TREE_TYPE (base), "ivtmp");
61       add_referenced_tmp_var (var);
62     }
63
64   vb = make_ssa_name (var, NULL_TREE);
65   if (var_before)
66     *var_before = vb;
67   va = make_ssa_name (var, NULL_TREE);
68   if (var_after)
69     *var_after = va;
70
71   /* For easier readability of the created code, produce MINUS_EXPRs
72      when suitable.  */
73   if (TREE_CODE (step) == INTEGER_CST)
74     {
75       if (TYPE_UNSIGNED (TREE_TYPE (step)))
76         {
77           step1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
78           if (tree_int_cst_lt (step1, step))
79             {
80               incr_op = MINUS_EXPR;
81               step = step1;
82             }
83         }
84       else
85         {
86           if (!tree_expr_nonnegative_p (step)
87               && may_negate_without_overflow_p (step))
88             {
89               incr_op = MINUS_EXPR;
90               step = fold (build1 (NEGATE_EXPR, TREE_TYPE (step), step));
91             }
92         }
93     }
94
95   stmt = build2 (MODIFY_EXPR, void_type_node, va,
96                  build2 (incr_op, TREE_TYPE (base),
97                          vb, step));
98   SSA_NAME_DEF_STMT (va) = stmt;
99   if (after)
100     bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
101   else
102     bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
103
104   initial = force_gimple_operand (base, &stmts, true, var);
105   if (stmts)
106     {
107       edge pe = loop_preheader_edge (loop);
108
109       bsi_insert_on_edge_immediate_loop (pe, stmts);
110     }
111
112   stmt = create_phi_node (vb, loop->header);
113   SSA_NAME_DEF_STMT (vb) = stmt;
114   add_phi_arg (stmt, initial, loop_preheader_edge (loop));
115   add_phi_arg (stmt, va, loop_latch_edge (loop));
116 }
117
118 /* Add exit phis for the USE on EXIT.  */
119
120 static void
121 add_exit_phis_edge (basic_block exit, tree use)
122 {
123   tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
124   basic_block def_bb = bb_for_stmt (def_stmt);
125   struct loop *def_loop;
126   edge e;
127   edge_iterator ei;
128
129   /* Check that some of the edges entering the EXIT block exits a loop in
130      that USE is defined.  */
131   FOR_EACH_EDGE (e, ei, exit->preds)
132     {
133       def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
134       if (!flow_bb_inside_loop_p (def_loop, e->dest))
135         break;
136     }
137
138   if (!e)
139     return;
140
141   phi = create_phi_node (use, exit);
142
143   FOR_EACH_EDGE (e, ei, exit->preds)
144     add_phi_arg (phi, use, e);
145
146   SSA_NAME_DEF_STMT (use) = def_stmt;
147 }
148
149 /* Add exit phis for VAR that is used in LIVEIN.
150    Exits of the loops are stored in EXITS.  */
151
152 static void
153 add_exit_phis_var (tree var, bitmap livein, bitmap exits)
154 {
155   bitmap def;
156   unsigned index;
157   basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
158   bitmap_iterator bi;
159
160   bitmap_clear_bit (livein, def_bb->index);
161
162   def = BITMAP_ALLOC (NULL);
163   bitmap_set_bit (def, def_bb->index);
164   compute_global_livein (livein, def);
165   BITMAP_FREE (def);
166
167   EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
168     {
169       add_exit_phis_edge (BASIC_BLOCK (index), var);
170     }
171 }
172
173 /* Add exit phis for the names marked in NAMES_TO_RENAME.
174    Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
175    names are used are stored in USE_BLOCKS.  */
176
177 static void
178 add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
179 {
180   unsigned i;
181   bitmap_iterator bi;
182
183   EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
184     {
185       add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
186     }
187 }
188
189 /* Returns a bitmap of all loop exit edge targets.  */
190
191 static bitmap
192 get_loops_exits (void)
193 {
194   bitmap exits = BITMAP_ALLOC (NULL);
195   basic_block bb;
196   edge e;
197   edge_iterator ei;
198
199   FOR_EACH_BB (bb)
200     {
201       FOR_EACH_EDGE (e, ei, bb->preds)
202         if (e->src != ENTRY_BLOCK_PTR
203             && !flow_bb_inside_loop_p (e->src->loop_father, bb))
204           {
205             bitmap_set_bit (exits, bb->index);
206             break;
207           }
208     }
209
210   return exits;
211 }
212
213 /* For USE in BB, if it is used outside of the loop it is defined in,
214    mark it for rewrite.  Record basic block BB where it is used
215    to USE_BLOCKS.  */
216
217 static void
218 find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks)
219 {
220   unsigned ver;
221   basic_block def_bb;
222   struct loop *def_loop;
223
224   if (TREE_CODE (use) != SSA_NAME)
225     return;
226
227   ver = SSA_NAME_VERSION (use);
228   def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
229   if (!def_bb)
230     return;
231   def_loop = def_bb->loop_father;
232
233   /* If the definition is not inside loop, it is not interesting.  */
234   if (!def_loop->outer)
235     return;
236
237   if (!use_blocks[ver])
238     use_blocks[ver] = BITMAP_ALLOC (NULL);
239   bitmap_set_bit (use_blocks[ver], bb->index);
240
241   if (!flow_bb_inside_loop_p (def_loop, bb))
242     mark_for_rewrite (use);
243 }
244
245 /* For uses in STMT, mark names that are used outside of the loop they are
246    defined to rewrite.  Record the set of blocks in that the ssa
247    names are defined to USE_BLOCKS.  */
248
249 static void
250 find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks)
251 {
252   ssa_op_iter iter;
253   tree var;
254   basic_block bb = bb_for_stmt (stmt);
255
256   get_stmt_operands (stmt);
257
258   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
259     find_uses_to_rename_use (bb, var, use_blocks);
260 }
261
262 /* Marks names that are used outside of the loop they are defined in
263    for rewrite.  Records the set of blocks in that the ssa
264    names are defined to USE_BLOCKS.  */
265
266 static void
267 find_uses_to_rename (bitmap *use_blocks)
268 {
269   basic_block bb;
270   block_stmt_iterator bsi;
271   tree phi;
272   unsigned i;
273
274   FOR_EACH_BB (bb)
275     {
276       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
277         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
278           find_uses_to_rename_use (EDGE_PRED (bb, i)->src,
279                                    PHI_ARG_DEF (phi, i), use_blocks);
280
281       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
282         find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks);
283     }
284 }
285
286 /* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
287    phi nodes to ensure that no variable is used outside the loop it is
288    defined in.
289
290    This strengthening of the basic ssa form has several advantages:
291
292    1) Updating it during unrolling/peeling/versioning is trivial, since
293       we do not need to care about the uses outside of the loop.
294    2) The behavior of all uses of an induction variable is the same.
295       Without this, you need to distinguish the case when the variable
296       is used outside of the loop it is defined in, for example
297
298       for (i = 0; i < 100; i++)
299         {
300           for (j = 0; j < 100; j++)
301             {
302               k = i + j;
303               use1 (k);
304             }
305           use2 (k);
306         }
307
308       Looking from the outer loop with the normal SSA form, the first use of k
309       is not well-behaved, while the second one is an induction variable with
310       base 99 and step 1.  */
311
312 void
313 rewrite_into_loop_closed_ssa (void)
314 {
315   bitmap loop_exits = get_loops_exits ();
316   bitmap *use_blocks;
317   unsigned i;
318   bitmap names_to_rename;
319
320   gcc_assert (!any_marked_for_rewrite_p ());
321
322   use_blocks = xcalloc (num_ssa_names, sizeof (bitmap));
323
324   /* Find the uses outside loops.  */
325   find_uses_to_rename (use_blocks);
326
327   /* Add the phi nodes on exits of the loops for the names we need to
328      rewrite.  */
329   names_to_rename = marked_ssa_names ();
330   add_exit_phis (names_to_rename, use_blocks, loop_exits);
331
332   for (i = 0; i < num_ssa_names; i++)
333     BITMAP_FREE (use_blocks[i]);
334   free (use_blocks);
335   BITMAP_FREE (loop_exits);
336   BITMAP_FREE (names_to_rename);
337
338   /* Do the rewriting.  */
339   rewrite_ssa_into_ssa ();
340 }
341
342 /* Check invariants of the loop closed ssa form for the USE in BB.  */
343
344 static void
345 check_loop_closed_ssa_use (basic_block bb, tree use)
346 {
347   tree def;
348   basic_block def_bb;
349   
350   if (TREE_CODE (use) != SSA_NAME)
351     return;
352
353   def = SSA_NAME_DEF_STMT (use);
354   def_bb = bb_for_stmt (def);
355   gcc_assert (!def_bb
356               || flow_bb_inside_loop_p (def_bb->loop_father, bb));
357 }
358
359 /* Checks invariants of loop closed ssa form in statement STMT in BB.  */
360
361 static void
362 check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
363 {
364   ssa_op_iter iter;
365   tree var;
366
367   get_stmt_operands (stmt);
368
369   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES)
370     check_loop_closed_ssa_use (bb, var);
371 }
372
373 /* Checks that invariants of the loop closed ssa form are preserved.  */
374
375 void
376 verify_loop_closed_ssa (void)
377 {
378   basic_block bb;
379   block_stmt_iterator bsi;
380   tree phi;
381   unsigned i;
382
383   verify_ssa ();
384
385   FOR_EACH_BB (bb)
386     {
387       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
388         for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
389           check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
390                                      PHI_ARG_DEF (phi, i));
391
392       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
393         check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
394     }
395 }
396
397 /* Split loop exit edge EXIT.  The things are a bit complicated by a need to
398    preserve the loop closed ssa form.  */
399
400 void
401 split_loop_exit_edge (edge exit)
402 {
403   basic_block dest = exit->dest;
404   basic_block bb = loop_split_edge_with (exit, NULL);
405   tree phi, new_phi, new_name, name;
406   use_operand_p op_p;
407
408   for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
409     {
410       op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, EDGE_SUCC (bb, 0));
411
412       name = USE_FROM_PTR (op_p);
413
414       /* If the argument of the phi node is a constant, we do not need
415          to keep it inside loop.  */
416       if (TREE_CODE (name) != SSA_NAME)
417         continue;
418
419       /* Otherwise create an auxiliary phi node that will copy the value
420          of the ssa name out of the loop.  */
421       new_name = duplicate_ssa_name (name, NULL);
422       new_phi = create_phi_node (new_name, bb);
423       SSA_NAME_DEF_STMT (new_name) = new_phi;
424       add_phi_arg (new_phi, name, exit);
425       SET_USE (op_p, new_name);
426     }
427 }
428
429 /* Insert statement STMT to the edge E and update the loop structures.
430    Returns the newly created block (if any).  */
431
432 basic_block
433 bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
434 {
435   basic_block src, dest, new_bb;
436   struct loop *loop_c;
437
438   src = e->src;
439   dest = e->dest;
440
441   loop_c = find_common_loop (src->loop_father, dest->loop_father);
442
443   new_bb = bsi_insert_on_edge_immediate (e, stmt);
444
445   if (!new_bb)
446     return NULL;
447
448   add_bb_to_loop (new_bb, loop_c);
449   if (dest->loop_father->latch == src)
450     dest->loop_father->latch = new_bb;
451
452   return new_bb;
453 }
454
455 /* Returns the basic block in that statements should be emitted for induction
456    variables incremented at the end of the LOOP.  */
457
458 basic_block
459 ip_end_pos (struct loop *loop)
460 {
461   return loop->latch;
462 }
463
464 /* Returns the basic block in that statements should be emitted for induction
465    variables incremented just before exit condition of a LOOP.  */
466
467 basic_block
468 ip_normal_pos (struct loop *loop)
469 {
470   tree last;
471   basic_block bb;
472   edge exit;
473
474   if (EDGE_COUNT (loop->latch->preds) > 1)
475     return NULL;
476
477   bb = EDGE_PRED (loop->latch, 0)->src;
478   last = last_stmt (bb);
479   if (TREE_CODE (last) != COND_EXPR)
480     return NULL;
481
482   exit = EDGE_SUCC (bb, 0);
483   if (exit->dest == loop->latch)
484     exit = EDGE_SUCC (bb, 1);
485
486   if (flow_bb_inside_loop_p (loop, exit->dest))
487     return NULL;
488
489   return bb;
490 }
491
492 /* Stores the standard position for induction variable increment in LOOP
493    (just before the exit condition if it is available and latch block is empty,
494    end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
495    the increment should be inserted after *BSI.  */
496
497 void
498 standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
499                                 bool *insert_after)
500 {
501   basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
502   tree last = last_stmt (latch);
503
504   if (!bb
505       || (last && TREE_CODE (last) != LABEL_EXPR))
506     {
507       *bsi = bsi_last (latch);
508       *insert_after = true;
509     }
510   else
511     {
512       *bsi = bsi_last (bb);
513       *insert_after = false;
514     }
515 }
516
517 /* Copies phi node arguments for duplicated blocks.  The index of the first
518    duplicated block is FIRST_NEW_BLOCK.  */
519
520 static void
521 copy_phi_node_args (unsigned first_new_block)
522 {
523   unsigned i;
524
525   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
526     BASIC_BLOCK (i)->rbi->duplicated = 1;
527
528   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
529     add_phi_args_after_copy_bb (BASIC_BLOCK (i));
530
531   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
532     BASIC_BLOCK (i)->rbi->duplicated = 0;
533 }
534
535 /* Renames variables in the area copied by tree_duplicate_loop_to_header_edge.
536    FIRST_NEW_BLOCK is the first block in the copied area.   DEFINITIONS is
537    a bitmap of all ssa names defined inside the loop.  */
538
539 static void
540 rename_variables (unsigned first_new_block, bitmap definitions)
541 {
542   unsigned i, copy_number = 0;
543   basic_block bb;
544   htab_t ssa_name_map = NULL;
545
546   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
547     {
548       bb = BASIC_BLOCK (i);
549
550       /* We assume that first come all blocks from the first copy, then all
551          blocks from the second copy, etc.  */
552       if (copy_number != (unsigned) bb->rbi->copy_number)
553         {
554           allocate_ssa_names (definitions, &ssa_name_map);
555           copy_number = bb->rbi->copy_number;
556         }
557
558       rewrite_to_new_ssa_names_bb (bb, ssa_name_map);
559     }
560
561   htab_delete (ssa_name_map);
562 }
563
564 /* Sets SSA_NAME_DEF_STMT for results of all phi nodes in BB.  */
565
566 static void
567 set_phi_def_stmts (basic_block bb)
568 {
569   tree phi;
570
571   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
572     SSA_NAME_DEF_STMT (PHI_RESULT (phi)) = phi;
573 }
574
575 /* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also updates
576    ssa.  In order to achieve this, only loops whose exits all lead to the same
577    location are handled.
578    
579    FIXME: we create some degenerate phi nodes that could be avoided by copy
580    propagating them instead.  Unfortunately this is not completely
581    straightforward due to problems with constant folding.  */
582
583 bool
584 tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
585                                     struct loops *loops,
586                                     unsigned int ndupl, sbitmap wont_exit,
587                                     edge orig, edge *to_remove,
588                                     unsigned int *n_to_remove, int flags)
589 {
590   unsigned first_new_block;
591   basic_block bb;
592   unsigned i;
593   bitmap definitions;
594
595   if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
596     return false;
597   if (!(loops->state & LOOPS_HAVE_PREHEADERS))
598     return false;
599
600 #ifdef ENABLE_CHECKING
601   verify_loop_closed_ssa ();
602 #endif
603
604   gcc_assert (!any_marked_for_rewrite_p ());
605
606   first_new_block = last_basic_block;
607   if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
608                                       orig, to_remove, n_to_remove, flags))
609     return false;
610
611   /* Readd the removed phi args for e.  */
612   flush_pending_stmts (e);
613
614   /* Copy the phi node arguments.  */
615   copy_phi_node_args (first_new_block);
616
617   /* Rename the variables.  */
618   definitions = marked_ssa_names ();
619   rename_variables (first_new_block, definitions);
620   unmark_all_for_rewrite ();
621   BITMAP_FREE (definitions);
622
623   /* For some time we have the identical ssa names as results in multiple phi
624      nodes.  When phi node is resized, it sets SSA_NAME_DEF_STMT of its result
625      to the new copy.  This means that we cannot easily ensure that the ssa
626      names defined in those phis are pointing to the right one -- so just
627      recompute SSA_NAME_DEF_STMT for them.  */ 
628
629   for (i = first_new_block; i < (unsigned) last_basic_block; i++)
630     {
631       bb = BASIC_BLOCK (i);
632       set_phi_def_stmts (bb);
633       if (bb->rbi->copy_number == 1)
634         set_phi_def_stmts (bb->rbi->original);
635     }
636
637   scev_reset ();
638 #ifdef ENABLE_CHECKING
639   verify_loop_closed_ssa ();
640 #endif
641
642   return true;
643 }
644
645 /*---------------------------------------------------------------------------
646   Loop versioning
647   ---------------------------------------------------------------------------*/
648  
649 /* Adjust phi nodes for 'first' basic block.  'second' basic block is a copy
650    of 'first'. Both of them are dominated by 'new_head' basic block. When
651    'new_head' was created by 'second's incoming edge it received phi arguments
652    on the edge by split_edge(). Later, additional edge 'e' was created to
653    connect 'new_head' and 'first'. Now this routine adds phi args on this 
654    additional edge 'e' that new_head to second edge received as part of edge 
655    splitting.
656 */
657
658 static void
659 lv_adjust_loop_header_phi (basic_block first, basic_block second,
660                            basic_block new_head, edge e)
661 {
662   tree phi1, phi2;
663
664   /* Browse all 'second' basic block phi nodes and add phi args to
665      edge 'e' for 'first' head. PHI args are always in correct order.  */
666
667   for (phi2 = phi_nodes (second), phi1 = phi_nodes (first); 
668        phi2 && phi1; 
669        phi2 = PHI_CHAIN (phi2),  phi1 = PHI_CHAIN (phi1))
670     {
671       edge e2 = find_edge (new_head, second);
672
673       if (e2)
674         {
675           tree def = PHI_ARG_DEF (phi2, e2->dest_idx);
676           add_phi_arg (phi1, def, e);
677         }
678     }
679 }
680
681 /* Adjust entry edge for lv.
682    
683   e is an incoming edge. 
684
685   --- edge e ---- > [second_head]
686
687   Split it and insert new conditional expression and adjust edges.
688    
689    --- edge e ---> [cond expr] ---> [first_head]
690                         |
691                         +---------> [second_head]
692
693 */
694    
695 static basic_block
696 lv_adjust_loop_entry_edge (basic_block first_head,
697                            basic_block second_head,
698                            edge e,
699                            tree cond_expr)
700
701   block_stmt_iterator bsi;
702   basic_block new_head = NULL;
703   tree goto1 = NULL_TREE;
704   tree goto2 = NULL_TREE;
705   tree new_cond_expr = NULL_TREE;
706   edge e0, e1;
707
708   gcc_assert (e->dest == second_head);
709
710   /* Split edge 'e'. This will create a new basic block, where we can
711      insert conditional expr.  */
712   new_head = split_edge (e);
713
714   /* Build new conditional expr */
715   goto1 = build1 (GOTO_EXPR, void_type_node, tree_block_label (first_head));
716   goto2 = build1 (GOTO_EXPR, void_type_node, tree_block_label (second_head));
717   new_cond_expr = build3 (COND_EXPR, void_type_node, cond_expr, goto1, goto2);
718
719   /* Add new cond. in new head.  */ 
720   bsi = bsi_start (new_head); 
721   bsi_insert_after (&bsi, new_cond_expr, BSI_NEW_STMT);
722
723   /* Adjust edges appropriately to connect new head with first head
724      as well as second head.  */
725   e0 = EDGE_SUCC (new_head, 0);
726   e0->flags &= ~EDGE_FALLTHRU;
727   e0->flags |= EDGE_FALSE_VALUE;
728   e1 = make_edge (new_head, first_head, EDGE_TRUE_VALUE);
729   set_immediate_dominator (CDI_DOMINATORS, first_head, new_head);
730   set_immediate_dominator (CDI_DOMINATORS, second_head, new_head);
731
732   /* Adjust loop header phi nodes.  */
733   lv_adjust_loop_header_phi (first_head, second_head, new_head, e1);
734
735   return new_head;
736 }
737
738 /* Main entry point for Loop Versioning transformation.
739    
740 This transformation given a condition and a loop, creates
741 -if (condition) { loop_copy1 } else { loop_copy2 },
742 where loop_copy1 is the loop transformed in one way, and loop_copy2
743 is the loop transformed in another way (or unchanged). 'condition'
744 may be a run time test for things that were not resolved by static
745 analysis (overlapping ranges (anti-aliasing), alignment, etc.).  */
746
747 struct loop *
748 tree_ssa_loop_version (struct loops *loops, struct loop * loop, 
749                        tree cond_expr, basic_block *condition_bb)
750 {
751   edge entry, latch_edge, exit, true_edge, false_edge;
752   basic_block first_head, second_head;
753   int irred_flag;
754   struct loop *nloop;
755
756   /* CHECKME: Loop versioning does not handle nested loop at this point.  */
757   if (loop->inner)
758     return NULL;
759
760   /* Record entry and latch edges for the loop */
761   entry = loop_preheader_edge (loop);
762
763   /* Note down head of loop as first_head.  */
764   first_head = entry->dest;
765
766   /* Duplicate loop.  */
767   irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
768   entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
769   if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
770                                            NULL, NULL, NULL, NULL, 0))
771     {
772       entry->flags |= irred_flag;
773       return NULL;
774     }
775
776   /* After duplication entry edge now points to new loop head block.
777      Note down new head as second_head.  */
778   second_head = entry->dest;
779
780   /* Split loop entry edge and insert new block with cond expr.  */
781   *condition_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry, 
782                                             cond_expr); 
783
784   latch_edge = EDGE_SUCC (loop->latch->rbi->copy, 0);
785   
786   extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
787   nloop = loopify (loops, 
788                    latch_edge,
789                    EDGE_PRED (loop->header->rbi->copy, 0),
790                    *condition_bb, true_edge, false_edge,
791                    false /* Do not redirect all edges.  */);
792
793   exit = loop->single_exit;
794   if (exit)
795     nloop->single_exit = find_edge (exit->src->rbi->copy, exit->dest);
796
797   /* loopify redirected latch_edge. Update its PENDING_STMTS.  */ 
798   flush_pending_stmts (latch_edge);
799
800   /* loopify redirected condition_bb's succ edge. Update its PENDING_STMTS.  */ 
801   extract_true_false_edges_from_block (*condition_bb, &true_edge, &false_edge);
802   flush_pending_stmts (false_edge);
803
804   /* Adjust irreducible flag.  */
805   if (irred_flag)
806     {
807       (*condition_bb)->flags |= BB_IRREDUCIBLE_LOOP;
808       loop_preheader_edge (loop)->flags |= EDGE_IRREDUCIBLE_LOOP;
809       loop_preheader_edge (nloop)->flags |= EDGE_IRREDUCIBLE_LOOP;
810       EDGE_PRED ((*condition_bb), 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
811     }
812
813   /* At this point condition_bb is loop predheader with two successors, 
814      first_head and second_head.   Make sure that loop predheader has only 
815      one successor.  */
816   loop_split_edge_with (loop_preheader_edge (loop), NULL);
817   loop_split_edge_with (loop_preheader_edge (nloop), NULL);
818
819   return nloop;
820 }