OSDN Git Service

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