OSDN Git Service

2012-04-03 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / tree-vect-loop-manip.c
1 /* Vectorizer Specific Loop Manipulations
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012
3    Free Software Foundation, Inc.
4    Contributed by Dorit Naishlos <dorit@il.ibm.com>
5    and Ira Rosen <irar@il.ibm.com>
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3.  If not see
21 <http://www.gnu.org/licenses/>.  */
22
23 #include "config.h"
24 #include "system.h"
25 #include "coretypes.h"
26 #include "tm.h"
27 #include "ggc.h"
28 #include "tree.h"
29 #include "basic-block.h"
30 #include "tree-pretty-print.h"
31 #include "gimple-pretty-print.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
34 #include "cfgloop.h"
35 #include "cfglayout.h"
36 #include "diagnostic-core.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-vectorizer.h"
39 #include "langhooks.h"
40
41 /*************************************************************************
42   Simple Loop Peeling Utilities
43
44   Utilities to support loop peeling for vectorization purposes.
45  *************************************************************************/
46
47
48 /* Renames the use *OP_P.  */
49
50 static void
51 rename_use_op (use_operand_p op_p)
52 {
53   tree new_name;
54
55   if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
56     return;
57
58   new_name = get_current_def (USE_FROM_PTR (op_p));
59
60   /* Something defined outside of the loop.  */
61   if (!new_name)
62     return;
63
64   /* An ordinary ssa name defined in the loop.  */
65
66   SET_USE (op_p, new_name);
67 }
68
69
70 /* Renames the variables in basic block BB.  */
71
72 void
73 rename_variables_in_bb (basic_block bb)
74 {
75   gimple_stmt_iterator gsi;
76   gimple stmt;
77   use_operand_p use_p;
78   ssa_op_iter iter;
79   edge e;
80   edge_iterator ei;
81   struct loop *loop = bb->loop_father;
82
83   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
84     {
85       stmt = gsi_stmt (gsi);
86       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
87         rename_use_op (use_p);
88     }
89
90   FOR_EACH_EDGE (e, ei, bb->succs)
91     {
92       if (!flow_bb_inside_loop_p (loop, e->dest))
93         continue;
94       for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
95         rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi), e));
96     }
97 }
98
99
100 /* Renames variables in new generated LOOP.  */
101
102 void
103 rename_variables_in_loop (struct loop *loop)
104 {
105   unsigned i;
106   basic_block *bbs;
107
108   bbs = get_loop_body (loop);
109
110   for (i = 0; i < loop->num_nodes; i++)
111     rename_variables_in_bb (bbs[i]);
112
113   free (bbs);
114 }
115
116 typedef struct
117 {
118   tree from, to;
119   basic_block bb;
120 } adjust_info;
121
122 DEF_VEC_O(adjust_info);
123 DEF_VEC_ALLOC_O_STACK(adjust_info);
124 #define VEC_adjust_info_stack_alloc(alloc) VEC_stack_alloc (adjust_info, alloc)
125
126 /* A stack of values to be adjusted in debug stmts.  We have to
127    process them LIFO, so that the closest substitution applies.  If we
128    processed them FIFO, without the stack, we might substitute uses
129    with a PHI DEF that would soon become non-dominant, and when we got
130    to the suitable one, it wouldn't have anything to substitute any
131    more.  */
132 static VEC(adjust_info, stack) *adjust_vec;
133
134 /* Adjust any debug stmts that referenced AI->from values to use the
135    loop-closed AI->to, if the references are dominated by AI->bb and
136    not by the definition of AI->from.  */
137
138 static void
139 adjust_debug_stmts_now (adjust_info *ai)
140 {
141   basic_block bbphi = ai->bb;
142   tree orig_def = ai->from;
143   tree new_def = ai->to;
144   imm_use_iterator imm_iter;
145   gimple stmt;
146   basic_block bbdef = gimple_bb (SSA_NAME_DEF_STMT (orig_def));
147
148   gcc_assert (dom_info_available_p (CDI_DOMINATORS));
149
150   /* Adjust any debug stmts that held onto non-loop-closed
151      references.  */
152   FOR_EACH_IMM_USE_STMT (stmt, imm_iter, orig_def)
153     {
154       use_operand_p use_p;
155       basic_block bbuse;
156
157       if (!is_gimple_debug (stmt))
158         continue;
159
160       gcc_assert (gimple_debug_bind_p (stmt));
161
162       bbuse = gimple_bb (stmt);
163
164       if ((bbuse == bbphi
165            || dominated_by_p (CDI_DOMINATORS, bbuse, bbphi))
166           && !(bbuse == bbdef
167                || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef)))
168         {
169           if (new_def)
170             FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
171               SET_USE (use_p, new_def);
172           else
173             {
174               gimple_debug_bind_reset_value (stmt);
175               update_stmt (stmt);
176             }
177         }
178     }
179 }
180
181 /* Adjust debug stmts as scheduled before.  */
182
183 static void
184 adjust_vec_debug_stmts (void)
185 {
186   if (!MAY_HAVE_DEBUG_STMTS)
187     return;
188
189   gcc_assert (adjust_vec);
190
191   while (!VEC_empty (adjust_info, adjust_vec))
192     {
193       adjust_debug_stmts_now (VEC_last (adjust_info, adjust_vec));
194       VEC_pop (adjust_info, adjust_vec);
195     }
196
197   VEC_free (adjust_info, stack, adjust_vec);
198 }
199
200 /* Adjust any debug stmts that referenced FROM values to use the
201    loop-closed TO, if the references are dominated by BB and not by
202    the definition of FROM.  If adjust_vec is non-NULL, adjustments
203    will be postponed until adjust_vec_debug_stmts is called.  */
204
205 static void
206 adjust_debug_stmts (tree from, tree to, basic_block bb)
207 {
208   adjust_info ai;
209
210   if (MAY_HAVE_DEBUG_STMTS && TREE_CODE (from) == SSA_NAME
211       && SSA_NAME_VAR (from) != gimple_vop (cfun))
212     {
213       ai.from = from;
214       ai.to = to;
215       ai.bb = bb;
216
217       if (adjust_vec)
218         VEC_safe_push (adjust_info, stack, adjust_vec, &ai);
219       else
220         adjust_debug_stmts_now (&ai);
221     }
222 }
223
224 /* Change E's phi arg in UPDATE_PHI to NEW_DEF, and record information
225    to adjust any debug stmts that referenced the old phi arg,
226    presumably non-loop-closed references left over from other
227    transformations.  */
228
229 static void
230 adjust_phi_and_debug_stmts (gimple update_phi, edge e, tree new_def)
231 {
232   tree orig_def = PHI_ARG_DEF_FROM_EDGE (update_phi, e);
233
234   SET_PHI_ARG_DEF (update_phi, e->dest_idx, new_def);
235
236   if (MAY_HAVE_DEBUG_STMTS)
237     adjust_debug_stmts (orig_def, PHI_RESULT (update_phi),
238                         gimple_bb (update_phi));
239 }
240
241
242 /* Update the PHI nodes of NEW_LOOP.
243
244    NEW_LOOP is a duplicate of ORIG_LOOP.
245    AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
246    AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
247    executes before it.  */
248
249 static void
250 slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
251                                        struct loop *new_loop, bool after)
252 {
253   tree new_ssa_name;
254   gimple phi_new, phi_orig;
255   tree def;
256   edge orig_loop_latch = loop_latch_edge (orig_loop);
257   edge orig_entry_e = loop_preheader_edge (orig_loop);
258   edge new_loop_exit_e = single_exit (new_loop);
259   edge new_loop_entry_e = loop_preheader_edge (new_loop);
260   edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
261   gimple_stmt_iterator gsi_new, gsi_orig;
262
263   /*
264      step 1. For each loop-header-phi:
265              Add the first phi argument for the phi in NEW_LOOP
266             (the one associated with the entry of NEW_LOOP)
267
268      step 2. For each loop-header-phi:
269              Add the second phi argument for the phi in NEW_LOOP
270             (the one associated with the latch of NEW_LOOP)
271
272      step 3. Update the phis in the successor block of NEW_LOOP.
273
274         case 1: NEW_LOOP was placed before ORIG_LOOP:
275                 The successor block of NEW_LOOP is the header of ORIG_LOOP.
276                 Updating the phis in the successor block can therefore be done
277                 along with the scanning of the loop header phis, because the
278                 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
279                 phi nodes, organized in the same order.
280
281         case 2: NEW_LOOP was placed after ORIG_LOOP:
282                 The successor block of NEW_LOOP is the original exit block of
283                 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
284                 We postpone updating these phis to a later stage (when
285                 loop guards are added).
286    */
287
288
289   /* Scan the phis in the headers of the old and new loops
290      (they are organized in exactly the same order).  */
291
292   for (gsi_new = gsi_start_phis (new_loop->header),
293        gsi_orig = gsi_start_phis (orig_loop->header);
294        !gsi_end_p (gsi_new) && !gsi_end_p (gsi_orig);
295        gsi_next (&gsi_new), gsi_next (&gsi_orig))
296     {
297       source_location locus;
298       phi_new = gsi_stmt (gsi_new);
299       phi_orig = gsi_stmt (gsi_orig);
300
301       /* step 1.  */
302       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
303       locus = gimple_phi_arg_location_from_edge (phi_orig, entry_arg_e);
304       add_phi_arg (phi_new, def, new_loop_entry_e, locus);
305
306       /* step 2.  */
307       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
308       locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
309       if (TREE_CODE (def) != SSA_NAME)
310         continue;
311
312       new_ssa_name = get_current_def (def);
313       if (!new_ssa_name)
314         {
315           /* This only happens if there are no definitions
316              inside the loop. use the phi_result in this case.  */
317           new_ssa_name = PHI_RESULT (phi_new);
318         }
319
320       /* An ordinary ssa name defined in the loop.  */
321       add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
322
323       /* Drop any debug references outside the loop, if they would
324          become ill-formed SSA.  */
325       adjust_debug_stmts (def, NULL, single_exit (orig_loop)->dest);
326
327       /* step 3 (case 1).  */
328       if (!after)
329         {
330           gcc_assert (new_loop_exit_e == orig_entry_e);
331           adjust_phi_and_debug_stmts (phi_orig, new_loop_exit_e, new_ssa_name);
332         }
333     }
334 }
335
336
337 /* Update PHI nodes for a guard of the LOOP.
338
339    Input:
340    - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
341         controls whether LOOP is to be executed.  GUARD_EDGE is the edge that
342         originates from the guard-bb, skips LOOP and reaches the (unique) exit
343         bb of LOOP.  This loop-exit-bb is an empty bb with one successor.
344         We denote this bb NEW_MERGE_BB because before the guard code was added
345         it had a single predecessor (the LOOP header), and now it became a merge
346         point of two paths - the path that ends with the LOOP exit-edge, and
347         the path that ends with GUARD_EDGE.
348    - NEW_EXIT_BB: New basic block that is added by this function between LOOP
349         and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
350
351    ===> The CFG before the guard-code was added:
352         LOOP_header_bb:
353           loop_body
354           if (exit_loop) goto update_bb
355           else           goto LOOP_header_bb
356         update_bb:
357
358    ==> The CFG after the guard-code was added:
359         guard_bb:
360           if (LOOP_guard_condition) goto new_merge_bb
361           else                      goto LOOP_header_bb
362         LOOP_header_bb:
363           loop_body
364           if (exit_loop_condition) goto new_merge_bb
365           else                     goto LOOP_header_bb
366         new_merge_bb:
367           goto update_bb
368         update_bb:
369
370    ==> The CFG after this function:
371         guard_bb:
372           if (LOOP_guard_condition) goto new_merge_bb
373           else                      goto LOOP_header_bb
374         LOOP_header_bb:
375           loop_body
376           if (exit_loop_condition) goto new_exit_bb
377           else                     goto LOOP_header_bb
378         new_exit_bb:
379         new_merge_bb:
380           goto update_bb
381         update_bb:
382
383    This function:
384    1. creates and updates the relevant phi nodes to account for the new
385       incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
386       1.1. Create phi nodes at NEW_MERGE_BB.
387       1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
388            UPDATE_BB).  UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
389    2. preserves loop-closed-ssa-form by creating the required phi nodes
390       at the exit of LOOP (i.e, in NEW_EXIT_BB).
391
392    There are two flavors to this function:
393
394    slpeel_update_phi_nodes_for_guard1:
395      Here the guard controls whether we enter or skip LOOP, where LOOP is a
396      prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
397      for variables that have phis in the loop header.
398
399    slpeel_update_phi_nodes_for_guard2:
400      Here the guard controls whether we enter or skip LOOP, where LOOP is an
401      epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
402      for variables that have phis in the loop exit.
403
404    I.E., the overall structure is:
405
406         loop1_preheader_bb:
407                 guard1 (goto loop1/merge1_bb)
408         loop1
409         loop1_exit_bb:
410                 guard2 (goto merge1_bb/merge2_bb)
411         merge1_bb
412         loop2
413         loop2_exit_bb
414         merge2_bb
415         next_bb
416
417    slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
418    loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
419    that have phis in loop1->header).
420
421    slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
422    loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
423    that have phis in next_bb). It also adds some of these phis to
424    loop1_exit_bb.
425
426    slpeel_update_phi_nodes_for_guard1 is always called before
427    slpeel_update_phi_nodes_for_guard2. They are both needed in order
428    to create correct data-flow and loop-closed-ssa-form.
429
430    Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
431    that change between iterations of a loop (and therefore have a phi-node
432    at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
433    phis for variables that are used out of the loop (and therefore have
434    loop-closed exit phis). Some variables may be both updated between
435    iterations and used after the loop. This is why in loop1_exit_bb we
436    may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
437    and exit phis (created by slpeel_update_phi_nodes_for_guard2).
438
439    - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
440      an original loop. i.e., we have:
441
442            orig_loop
443            guard_bb (goto LOOP/new_merge)
444            new_loop <-- LOOP
445            new_exit
446            new_merge
447            next_bb
448
449      If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
450      have:
451
452            new_loop
453            guard_bb (goto LOOP/new_merge)
454            orig_loop <-- LOOP
455            new_exit
456            new_merge
457            next_bb
458
459      The SSA names defined in the original loop have a current
460      reaching definition that that records the corresponding new
461      ssa-name used in the new duplicated loop copy.
462   */
463
464 /* Function slpeel_update_phi_nodes_for_guard1
465
466    Input:
467    - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
468    - DEFS - a bitmap of ssa names to mark new names for which we recorded
469             information.
470
471    In the context of the overall structure, we have:
472
473         loop1_preheader_bb:
474                 guard1 (goto loop1/merge1_bb)
475 LOOP->  loop1
476         loop1_exit_bb:
477                 guard2 (goto merge1_bb/merge2_bb)
478         merge1_bb
479         loop2
480         loop2_exit_bb
481         merge2_bb
482         next_bb
483
484    For each name updated between loop iterations (i.e - for each name that has
485    an entry (loop-header) phi in LOOP) we create a new phi in:
486    1. merge1_bb (to account for the edge from guard1)
487    2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
488 */
489
490 static void
491 slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
492                                     bool is_new_loop, basic_block *new_exit_bb,
493                                     bitmap *defs)
494 {
495   gimple orig_phi, new_phi;
496   gimple update_phi, update_phi2;
497   tree guard_arg, loop_arg;
498   basic_block new_merge_bb = guard_edge->dest;
499   edge e = EDGE_SUCC (new_merge_bb, 0);
500   basic_block update_bb = e->dest;
501   basic_block orig_bb = loop->header;
502   edge new_exit_e;
503   tree current_new_name;
504   gimple_stmt_iterator gsi_orig, gsi_update;
505
506   /* Create new bb between loop and new_merge_bb.  */
507   *new_exit_bb = split_edge (single_exit (loop));
508
509   new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
510
511   for (gsi_orig = gsi_start_phis (orig_bb),
512        gsi_update = gsi_start_phis (update_bb);
513        !gsi_end_p (gsi_orig) && !gsi_end_p (gsi_update);
514        gsi_next (&gsi_orig), gsi_next (&gsi_update))
515     {
516       source_location loop_locus, guard_locus;
517       orig_phi = gsi_stmt (gsi_orig);
518       update_phi = gsi_stmt (gsi_update);
519
520       /** 1. Handle new-merge-point phis  **/
521
522       /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
523       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
524                                  new_merge_bb);
525
526       /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
527             of LOOP. Set the two phi args in NEW_PHI for these edges:  */
528       loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
529       loop_locus = gimple_phi_arg_location_from_edge (orig_phi,
530                                                       EDGE_SUCC (loop->latch,
531                                                                  0));
532       guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
533       guard_locus
534         = gimple_phi_arg_location_from_edge (orig_phi,
535                                              loop_preheader_edge (loop));
536
537       add_phi_arg (new_phi, loop_arg, new_exit_e, loop_locus);
538       add_phi_arg (new_phi, guard_arg, guard_edge, guard_locus);
539
540       /* 1.3. Update phi in successor block.  */
541       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
542                   || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
543       adjust_phi_and_debug_stmts (update_phi, e, PHI_RESULT (new_phi));
544       update_phi2 = new_phi;
545
546
547       /** 2. Handle loop-closed-ssa-form phis  **/
548
549       if (!is_gimple_reg (PHI_RESULT (orig_phi)))
550         continue;
551
552       /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
553       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
554                                  *new_exit_bb);
555
556       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
557       add_phi_arg (new_phi, loop_arg, single_exit (loop), loop_locus);
558
559       /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
560       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
561       adjust_phi_and_debug_stmts (update_phi2, new_exit_e,
562                                   PHI_RESULT (new_phi));
563
564       /* 2.4. Record the newly created name with set_current_def.
565          We want to find a name such that
566                 name = get_current_def (orig_loop_name)
567          and to set its current definition as follows:
568                 set_current_def (name, new_phi_name)
569
570          If LOOP is a new loop then loop_arg is already the name we're
571          looking for. If LOOP is the original loop, then loop_arg is
572          the orig_loop_name and the relevant name is recorded in its
573          current reaching definition.  */
574       if (is_new_loop)
575         current_new_name = loop_arg;
576       else
577         {
578           current_new_name = get_current_def (loop_arg);
579           /* current_def is not available only if the variable does not
580              change inside the loop, in which case we also don't care
581              about recording a current_def for it because we won't be
582              trying to create loop-exit-phis for it.  */
583           if (!current_new_name)
584             continue;
585         }
586       gcc_assert (get_current_def (current_new_name) == NULL_TREE);
587
588       set_current_def (current_new_name, PHI_RESULT (new_phi));
589       bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
590     }
591 }
592
593
594 /* Function slpeel_update_phi_nodes_for_guard2
595
596    Input:
597    - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
598
599    In the context of the overall structure, we have:
600
601         loop1_preheader_bb:
602                 guard1 (goto loop1/merge1_bb)
603         loop1
604         loop1_exit_bb:
605                 guard2 (goto merge1_bb/merge2_bb)
606         merge1_bb
607 LOOP->  loop2
608         loop2_exit_bb
609         merge2_bb
610         next_bb
611
612    For each name used out side the loop (i.e - for each name that has an exit
613    phi in next_bb) we create a new phi in:
614    1. merge2_bb (to account for the edge from guard_bb)
615    2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
616    3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
617       if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
618 */
619
620 static void
621 slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
622                                     bool is_new_loop, basic_block *new_exit_bb)
623 {
624   gimple orig_phi, new_phi;
625   gimple update_phi, update_phi2;
626   tree guard_arg, loop_arg;
627   basic_block new_merge_bb = guard_edge->dest;
628   edge e = EDGE_SUCC (new_merge_bb, 0);
629   basic_block update_bb = e->dest;
630   edge new_exit_e;
631   tree orig_def, orig_def_new_name;
632   tree new_name, new_name2;
633   tree arg;
634   gimple_stmt_iterator gsi;
635
636   /* Create new bb between loop and new_merge_bb.  */
637   *new_exit_bb = split_edge (single_exit (loop));
638
639   new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
640
641   for (gsi = gsi_start_phis (update_bb); !gsi_end_p (gsi); gsi_next (&gsi))
642     {
643       update_phi = gsi_stmt (gsi);
644       orig_phi = update_phi;
645       orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
646       /* This loop-closed-phi actually doesn't represent a use
647          out of the loop - the phi arg is a constant.  */
648       if (TREE_CODE (orig_def) != SSA_NAME)
649         continue;
650       orig_def_new_name = get_current_def (orig_def);
651       arg = NULL_TREE;
652
653       /** 1. Handle new-merge-point phis  **/
654
655       /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
656       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
657                                  new_merge_bb);
658
659       /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
660             of LOOP. Set the two PHI args in NEW_PHI for these edges:  */
661       new_name = orig_def;
662       new_name2 = NULL_TREE;
663       if (orig_def_new_name)
664         {
665           new_name = orig_def_new_name;
666           /* Some variables have both loop-entry-phis and loop-exit-phis.
667              Such variables were given yet newer names by phis placed in
668              guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
669              new_name2 = get_current_def (get_current_def (orig_name)).  */
670           new_name2 = get_current_def (new_name);
671         }
672
673       if (is_new_loop)
674         {
675           guard_arg = orig_def;
676           loop_arg = new_name;
677         }
678       else
679         {
680           guard_arg = new_name;
681           loop_arg = orig_def;
682         }
683       if (new_name2)
684         guard_arg = new_name2;
685
686       add_phi_arg (new_phi, loop_arg, new_exit_e, UNKNOWN_LOCATION);
687       add_phi_arg (new_phi, guard_arg, guard_edge, UNKNOWN_LOCATION);
688
689       /* 1.3. Update phi in successor block.  */
690       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
691       adjust_phi_and_debug_stmts (update_phi, e, PHI_RESULT (new_phi));
692       update_phi2 = new_phi;
693
694
695       /** 2. Handle loop-closed-ssa-form phis  **/
696
697       /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
698       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
699                                  *new_exit_bb);
700
701       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
702       add_phi_arg (new_phi, loop_arg, single_exit (loop), UNKNOWN_LOCATION);
703
704       /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
705       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
706       adjust_phi_and_debug_stmts (update_phi2, new_exit_e,
707                                   PHI_RESULT (new_phi));
708
709
710       /** 3. Handle loop-closed-ssa-form phis for first loop  **/
711
712       /* 3.1. Find the relevant names that need an exit-phi in
713          GUARD_BB, i.e. names for which
714          slpeel_update_phi_nodes_for_guard1 had not already created a
715          phi node. This is the case for names that are used outside
716          the loop (and therefore need an exit phi) but are not updated
717          across loop iterations (and therefore don't have a
718          loop-header-phi).
719
720          slpeel_update_phi_nodes_for_guard1 is responsible for
721          creating loop-exit phis in GUARD_BB for names that have a
722          loop-header-phi.  When such a phi is created we also record
723          the new name in its current definition.  If this new name
724          exists, then guard_arg was set to this new name (see 1.2
725          above).  Therefore, if guard_arg is not this new name, this
726          is an indication that an exit-phi in GUARD_BB was not yet
727          created, so we take care of it here.  */
728       if (guard_arg == new_name2)
729         continue;
730       arg = guard_arg;
731
732       /* 3.2. Generate new phi node in GUARD_BB:  */
733       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
734                                  guard_edge->src);
735
736       /* 3.3. GUARD_BB has one incoming edge:  */
737       gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
738       add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0),
739                    UNKNOWN_LOCATION);
740
741       /* 3.4. Update phi in successor of GUARD_BB:  */
742       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
743                                                                 == guard_arg);
744       adjust_phi_and_debug_stmts (update_phi2, guard_edge,
745                                   PHI_RESULT (new_phi));
746     }
747 }
748
749
750 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
751    that starts at zero, increases by one and its limit is NITERS.
752
753    Assumption: the exit-condition of LOOP is the last stmt in the loop.  */
754
755 void
756 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
757 {
758   tree indx_before_incr, indx_after_incr;
759   gimple cond_stmt;
760   gimple orig_cond;
761   edge exit_edge = single_exit (loop);
762   gimple_stmt_iterator loop_cond_gsi;
763   gimple_stmt_iterator incr_gsi;
764   bool insert_after;
765   tree init = build_int_cst (TREE_TYPE (niters), 0);
766   tree step = build_int_cst (TREE_TYPE (niters), 1);
767   LOC loop_loc;
768   enum tree_code code;
769
770   orig_cond = get_loop_exit_condition (loop);
771   gcc_assert (orig_cond);
772   loop_cond_gsi = gsi_for_stmt (orig_cond);
773
774   standard_iv_increment_position (loop, &incr_gsi, &insert_after);
775   create_iv (init, step, NULL_TREE, loop,
776              &incr_gsi, insert_after, &indx_before_incr, &indx_after_incr);
777
778   indx_after_incr = force_gimple_operand_gsi (&loop_cond_gsi, indx_after_incr,
779                                               true, NULL_TREE, true,
780                                               GSI_SAME_STMT);
781   niters = force_gimple_operand_gsi (&loop_cond_gsi, niters, true, NULL_TREE,
782                                      true, GSI_SAME_STMT);
783
784   code = (exit_edge->flags & EDGE_TRUE_VALUE) ? GE_EXPR : LT_EXPR;
785   cond_stmt = gimple_build_cond (code, indx_after_incr, niters, NULL_TREE,
786                                  NULL_TREE);
787
788   gsi_insert_before (&loop_cond_gsi, cond_stmt, GSI_SAME_STMT);
789
790   /* Remove old loop exit test:  */
791   gsi_remove (&loop_cond_gsi, true);
792
793   loop_loc = find_loop_location (loop);
794   if (dump_file && (dump_flags & TDF_DETAILS))
795     {
796       if (loop_loc != UNKNOWN_LOC)
797         fprintf (dump_file, "\nloop at %s:%d: ",
798                  LOC_FILE (loop_loc), LOC_LINE (loop_loc));
799       print_gimple_stmt (dump_file, cond_stmt, 0, TDF_SLIM);
800     }
801
802   loop->nb_iterations = niters;
803 }
804
805
806 /* Given LOOP this function generates a new copy of it and puts it
807    on E which is either the entry or exit of LOOP.  */
808
809 struct loop *
810 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
811 {
812   struct loop *new_loop;
813   basic_block *new_bbs, *bbs;
814   bool at_exit;
815   bool was_imm_dom;
816   basic_block exit_dest;
817   gimple phi;
818   tree phi_arg;
819   edge exit, new_exit;
820   gimple_stmt_iterator gsi;
821
822   at_exit = (e == single_exit (loop));
823   if (!at_exit && e != loop_preheader_edge (loop))
824     return NULL;
825
826   bbs = get_loop_body (loop);
827
828   /* Check whether duplication is possible.  */
829   if (!can_copy_bbs_p (bbs, loop->num_nodes))
830     {
831       free (bbs);
832       return NULL;
833     }
834
835   /* Generate new loop structure.  */
836   new_loop = duplicate_loop (loop, loop_outer (loop));
837   if (!new_loop)
838     {
839       free (bbs);
840       return NULL;
841     }
842
843   exit_dest = single_exit (loop)->dest;
844   was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
845                                           exit_dest) == loop->header ?
846                  true : false);
847
848   new_bbs = XNEWVEC (basic_block, loop->num_nodes);
849
850   exit = single_exit (loop);
851   copy_bbs (bbs, loop->num_nodes, new_bbs,
852             &exit, 1, &new_exit, NULL,
853             e->src);
854
855   /* Duplicating phi args at exit bbs as coming
856      also from exit of duplicated loop.  */
857   for (gsi = gsi_start_phis (exit_dest); !gsi_end_p (gsi); gsi_next (&gsi))
858     {
859       phi = gsi_stmt (gsi);
860       phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
861       if (phi_arg)
862         {
863           edge new_loop_exit_edge;
864           source_location locus;
865
866           locus = gimple_phi_arg_location_from_edge (phi, single_exit (loop));
867           if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
868             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
869           else
870             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
871
872           add_phi_arg (phi, phi_arg, new_loop_exit_edge, locus);
873         }
874     }
875
876   if (at_exit) /* Add the loop copy at exit.  */
877     {
878       redirect_edge_and_branch_force (e, new_loop->header);
879       PENDING_STMT (e) = NULL;
880       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
881       if (was_imm_dom)
882         set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
883     }
884   else /* Add the copy at entry.  */
885     {
886       edge new_exit_e;
887       edge entry_e = loop_preheader_edge (loop);
888       basic_block preheader = entry_e->src;
889
890       if (!flow_bb_inside_loop_p (new_loop,
891                                   EDGE_SUCC (new_loop->header, 0)->dest))
892         new_exit_e = EDGE_SUCC (new_loop->header, 0);
893       else
894         new_exit_e = EDGE_SUCC (new_loop->header, 1);
895
896       redirect_edge_and_branch_force (new_exit_e, loop->header);
897       PENDING_STMT (new_exit_e) = NULL;
898       set_immediate_dominator (CDI_DOMINATORS, loop->header,
899                                new_exit_e->src);
900
901       /* We have to add phi args to the loop->header here as coming
902          from new_exit_e edge.  */
903       for (gsi = gsi_start_phis (loop->header);
904            !gsi_end_p (gsi);
905            gsi_next (&gsi))
906         {
907           phi = gsi_stmt (gsi);
908           phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
909           if (phi_arg)
910             add_phi_arg (phi, phi_arg, new_exit_e,
911                          gimple_phi_arg_location_from_edge (phi, entry_e));
912         }
913
914       redirect_edge_and_branch_force (entry_e, new_loop->header);
915       PENDING_STMT (entry_e) = NULL;
916       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
917     }
918
919   free (new_bbs);
920   free (bbs);
921
922   return new_loop;
923 }
924
925
926 /* Given the condition statement COND, put it as the last statement
927    of GUARD_BB; EXIT_BB is the basic block to skip the loop;
928    Assumes that this is the single exit of the guarded loop.
929    Returns the skip edge, inserts new stmts on the COND_EXPR_STMT_LIST.  */
930
931 static edge
932 slpeel_add_loop_guard (basic_block guard_bb, tree cond,
933                        gimple_seq cond_expr_stmt_list,
934                        basic_block exit_bb, basic_block dom_bb)
935 {
936   gimple_stmt_iterator gsi;
937   edge new_e, enter_e;
938   gimple cond_stmt;
939   gimple_seq gimplify_stmt_list = NULL;
940
941   enter_e = EDGE_SUCC (guard_bb, 0);
942   enter_e->flags &= ~EDGE_FALLTHRU;
943   enter_e->flags |= EDGE_FALSE_VALUE;
944   gsi = gsi_last_bb (guard_bb);
945
946   cond = force_gimple_operand (cond, &gimplify_stmt_list, true, NULL_TREE);
947   if (gimplify_stmt_list)
948     gimple_seq_add_seq (&cond_expr_stmt_list, gimplify_stmt_list);
949   cond_stmt = gimple_build_cond (NE_EXPR,
950                                  cond, build_int_cst (TREE_TYPE (cond), 0),
951                                  NULL_TREE, NULL_TREE);
952   if (cond_expr_stmt_list)
953     gsi_insert_seq_after (&gsi, cond_expr_stmt_list, GSI_NEW_STMT);
954
955   gsi = gsi_last_bb (guard_bb);
956   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
957
958   /* Add new edge to connect guard block to the merge/loop-exit block.  */
959   new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
960   set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
961   return new_e;
962 }
963
964
965 /* This function verifies that the following restrictions apply to LOOP:
966    (1) it is innermost
967    (2) it consists of exactly 2 basic blocks - header, and an empty latch.
968    (3) it is single entry, single exit
969    (4) its exit condition is the last stmt in the header
970    (5) E is the entry/exit edge of LOOP.
971  */
972
973 bool
974 slpeel_can_duplicate_loop_p (const struct loop *loop, const_edge e)
975 {
976   edge exit_e = single_exit (loop);
977   edge entry_e = loop_preheader_edge (loop);
978   gimple orig_cond = get_loop_exit_condition (loop);
979   gimple_stmt_iterator loop_exit_gsi = gsi_last_bb (exit_e->src);
980
981   if (need_ssa_update_p (cfun))
982     return false;
983
984   if (loop->inner
985       /* All loops have an outer scope; the only case loop->outer is NULL is for
986          the function itself.  */
987       || !loop_outer (loop)
988       || loop->num_nodes != 2
989       || !empty_block_p (loop->latch)
990       || !single_exit (loop)
991       /* Verify that new loop exit condition can be trivially modified.  */
992       || (!orig_cond || orig_cond != gsi_stmt (loop_exit_gsi))
993       || (e != exit_e && e != entry_e))
994     return false;
995
996   return true;
997 }
998
999 #ifdef ENABLE_CHECKING
1000 static void
1001 slpeel_verify_cfg_after_peeling (struct loop *first_loop,
1002                                  struct loop *second_loop)
1003 {
1004   basic_block loop1_exit_bb = single_exit (first_loop)->dest;
1005   basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
1006   basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
1007
1008   /* A guard that controls whether the second_loop is to be executed or skipped
1009      is placed in first_loop->exit.  first_loop->exit therefore has two
1010      successors - one is the preheader of second_loop, and the other is a bb
1011      after second_loop.
1012    */
1013   gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
1014
1015   /* 1. Verify that one of the successors of first_loop->exit is the preheader
1016         of second_loop.  */
1017
1018   /* The preheader of new_loop is expected to have two predecessors:
1019      first_loop->exit and the block that precedes first_loop.  */
1020
1021   gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
1022               && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
1023                    && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
1024                || (EDGE_PRED (loop2_entry_bb, 1)->src ==  loop1_exit_bb
1025                    && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
1026
1027   /* Verify that the other successor of first_loop->exit is after the
1028      second_loop.  */
1029   /* TODO */
1030 }
1031 #endif
1032
1033 /* If the run time cost model check determines that vectorization is
1034    not profitable and hence scalar loop should be generated then set
1035    FIRST_NITERS to prologue peeled iterations. This will allow all the
1036    iterations to be executed in the prologue peeled scalar loop.  */
1037
1038 static void
1039 set_prologue_iterations (basic_block bb_before_first_loop,
1040                          tree *first_niters,
1041                          struct loop *loop,
1042                          unsigned int th)
1043 {
1044   edge e;
1045   basic_block cond_bb, then_bb;
1046   tree var, prologue_after_cost_adjust_name;
1047   gimple_stmt_iterator gsi;
1048   gimple newphi;
1049   edge e_true, e_false, e_fallthru;
1050   gimple cond_stmt;
1051   gimple_seq gimplify_stmt_list = NULL, stmts = NULL;
1052   tree cost_pre_condition = NULL_TREE;
1053   tree scalar_loop_iters =
1054     unshare_expr (LOOP_VINFO_NITERS_UNCHANGED (loop_vec_info_for_loop (loop)));
1055
1056   e = single_pred_edge (bb_before_first_loop);
1057   cond_bb = split_edge(e);
1058
1059   e = single_pred_edge (bb_before_first_loop);
1060   then_bb = split_edge(e);
1061   set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb);
1062
1063   e_false = make_single_succ_edge (cond_bb, bb_before_first_loop,
1064                                    EDGE_FALSE_VALUE);
1065   set_immediate_dominator (CDI_DOMINATORS, bb_before_first_loop, cond_bb);
1066
1067   e_true = EDGE_PRED (then_bb, 0);
1068   e_true->flags &= ~EDGE_FALLTHRU;
1069   e_true->flags |= EDGE_TRUE_VALUE;
1070
1071   e_fallthru = EDGE_SUCC (then_bb, 0);
1072
1073   cost_pre_condition =
1074     fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
1075                  build_int_cst (TREE_TYPE (scalar_loop_iters), th));
1076   cost_pre_condition =
1077     force_gimple_operand (cost_pre_condition, &gimplify_stmt_list,
1078                           true, NULL_TREE);
1079   cond_stmt = gimple_build_cond (NE_EXPR, cost_pre_condition,
1080                                  build_int_cst (TREE_TYPE (cost_pre_condition),
1081                                                 0), NULL_TREE, NULL_TREE);
1082
1083   gsi = gsi_last_bb (cond_bb);
1084   if (gimplify_stmt_list)
1085     gsi_insert_seq_after (&gsi, gimplify_stmt_list, GSI_NEW_STMT);
1086
1087   gsi = gsi_last_bb (cond_bb);
1088   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
1089
1090   var = create_tmp_var (TREE_TYPE (scalar_loop_iters),
1091                         "prologue_after_cost_adjust");
1092   add_referenced_var (var);
1093   prologue_after_cost_adjust_name =
1094     force_gimple_operand (scalar_loop_iters, &stmts, false, var);
1095
1096   gsi = gsi_last_bb (then_bb);
1097   if (stmts)
1098     gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
1099
1100   newphi = create_phi_node (var, bb_before_first_loop);
1101   add_phi_arg (newphi, prologue_after_cost_adjust_name, e_fallthru,
1102                UNKNOWN_LOCATION);
1103   add_phi_arg (newphi, *first_niters, e_false, UNKNOWN_LOCATION);
1104
1105   *first_niters = PHI_RESULT (newphi);
1106 }
1107
1108 /* Function slpeel_tree_peel_loop_to_edge.
1109
1110    Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
1111    that is placed on the entry (exit) edge E of LOOP. After this transformation
1112    we have two loops one after the other - first-loop iterates FIRST_NITERS
1113    times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
1114    If the cost model indicates that it is profitable to emit a scalar
1115    loop instead of the vector one, then the prolog (epilog) loop will iterate
1116    for the entire unchanged scalar iterations of the loop.
1117
1118    Input:
1119    - LOOP: the loop to be peeled.
1120    - E: the exit or entry edge of LOOP.
1121         If it is the entry edge, we peel the first iterations of LOOP. In this
1122         case first-loop is LOOP, and second-loop is the newly created loop.
1123         If it is the exit edge, we peel the last iterations of LOOP. In this
1124         case, first-loop is the newly created loop, and second-loop is LOOP.
1125    - NITERS: the number of iterations that LOOP iterates.
1126    - FIRST_NITERS: the number of iterations that the first-loop should iterate.
1127    - UPDATE_FIRST_LOOP_COUNT:  specified whether this function is responsible
1128         for updating the loop bound of the first-loop to FIRST_NITERS.  If it
1129         is false, the caller of this function may want to take care of this
1130         (this can be useful if we don't want new stmts added to first-loop).
1131    - TH: cost model profitability threshold of iterations for vectorization.
1132    - CHECK_PROFITABILITY: specify whether cost model check has not occurred
1133                           during versioning and hence needs to occur during
1134                           prologue generation or whether cost model check
1135                           has not occurred during prologue generation and hence
1136                           needs to occur during epilogue generation.
1137
1138
1139    Output:
1140    The function returns a pointer to the new loop-copy, or NULL if it failed
1141    to perform the transformation.
1142
1143    The function generates two if-then-else guards: one before the first loop,
1144    and the other before the second loop:
1145    The first guard is:
1146      if (FIRST_NITERS == 0) then skip the first loop,
1147      and go directly to the second loop.
1148    The second guard is:
1149      if (FIRST_NITERS == NITERS) then skip the second loop.
1150
1151    If the optional COND_EXPR and COND_EXPR_STMT_LIST arguments are given
1152    then the generated condition is combined with COND_EXPR and the
1153    statements in COND_EXPR_STMT_LIST are emitted together with it.
1154
1155    FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
1156    FORNOW the resulting code will not be in loop-closed-ssa form.
1157 */
1158
1159 static struct loop*
1160 slpeel_tree_peel_loop_to_edge (struct loop *loop,
1161                                edge e, tree *first_niters,
1162                                tree niters, bool update_first_loop_count,
1163                                unsigned int th, bool check_profitability,
1164                                tree cond_expr, gimple_seq cond_expr_stmt_list)
1165 {
1166   struct loop *new_loop = NULL, *first_loop, *second_loop;
1167   edge skip_e;
1168   tree pre_condition = NULL_TREE;
1169   bitmap definitions;
1170   basic_block bb_before_second_loop, bb_after_second_loop;
1171   basic_block bb_before_first_loop;
1172   basic_block bb_between_loops;
1173   basic_block new_exit_bb;
1174   gimple_stmt_iterator gsi;
1175   edge exit_e = single_exit (loop);
1176   LOC loop_loc;
1177   tree cost_pre_condition = NULL_TREE;
1178
1179   if (!slpeel_can_duplicate_loop_p (loop, e))
1180     return NULL;
1181
1182   /* We have to initialize cfg_hooks. Then, when calling
1183    cfg_hooks->split_edge, the function tree_split_edge
1184    is actually called and, when calling cfg_hooks->duplicate_block,
1185    the function tree_duplicate_bb is called.  */
1186   gimple_register_cfg_hooks ();
1187
1188   /* If the loop has a virtual PHI, but exit bb doesn't, create a virtual PHI
1189      in the exit bb and rename all the uses after the loop.  This simplifies
1190      the *guard[12] routines, which assume loop closed SSA form for all PHIs
1191      (but normally loop closed SSA form doesn't require virtual PHIs to be
1192      in the same form).  Doing this early simplifies the checking what
1193      uses should be renamed.  */
1194   for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1195     if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1196       {
1197         gimple phi = gsi_stmt (gsi);
1198         for (gsi = gsi_start_phis (exit_e->dest);
1199              !gsi_end_p (gsi); gsi_next (&gsi))
1200           if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1201             break;
1202         if (gsi_end_p (gsi))
1203           {
1204             gimple new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (phi)),
1205                                               exit_e->dest);
1206             tree vop = PHI_ARG_DEF_FROM_EDGE (phi, EDGE_SUCC (loop->latch, 0));
1207             imm_use_iterator imm_iter;
1208             gimple stmt;
1209             tree new_vop = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)),
1210                                           new_phi);
1211             use_operand_p use_p;
1212
1213             add_phi_arg (new_phi, vop, exit_e, UNKNOWN_LOCATION);
1214             gimple_phi_set_result (new_phi, new_vop);
1215             FOR_EACH_IMM_USE_STMT (stmt, imm_iter, vop)
1216               if (stmt != new_phi && gimple_bb (stmt) != loop->header)
1217                 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1218                   SET_USE (use_p, new_vop);
1219           }
1220         break;
1221       }
1222
1223   /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1224         Resulting CFG would be:
1225
1226         first_loop:
1227         do {
1228         } while ...
1229
1230         second_loop:
1231         do {
1232         } while ...
1233
1234         orig_exit_bb:
1235    */
1236
1237   if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e)))
1238     {
1239       loop_loc = find_loop_location (loop);
1240       if (dump_file && (dump_flags & TDF_DETAILS))
1241         {
1242           if (loop_loc != UNKNOWN_LOC)
1243             fprintf (dump_file, "\n%s:%d: note: ",
1244                      LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1245           fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
1246         }
1247       return NULL;
1248     }
1249
1250   if (MAY_HAVE_DEBUG_STMTS)
1251     {
1252       gcc_assert (!adjust_vec);
1253       adjust_vec = VEC_alloc (adjust_info, stack, 32);
1254     }
1255
1256   if (e == exit_e)
1257     {
1258       /* NEW_LOOP was placed after LOOP.  */
1259       first_loop = loop;
1260       second_loop = new_loop;
1261     }
1262   else
1263     {
1264       /* NEW_LOOP was placed before LOOP.  */
1265       first_loop = new_loop;
1266       second_loop = loop;
1267     }
1268
1269   definitions = ssa_names_to_replace ();
1270   slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
1271   rename_variables_in_loop (new_loop);
1272
1273
1274   /* 2.  Add the guard code in one of the following ways:
1275
1276      2.a Add the guard that controls whether the first loop is executed.
1277          This occurs when this function is invoked for prologue or epilogue
1278          generation and when the cost model check can be done at compile time.
1279
1280          Resulting CFG would be:
1281
1282          bb_before_first_loop:
1283          if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1284                                 GOTO first-loop
1285
1286          first_loop:
1287          do {
1288          } while ...
1289
1290          bb_before_second_loop:
1291
1292          second_loop:
1293          do {
1294          } while ...
1295
1296          orig_exit_bb:
1297
1298      2.b Add the cost model check that allows the prologue
1299          to iterate for the entire unchanged scalar
1300          iterations of the loop in the event that the cost
1301          model indicates that the scalar loop is more
1302          profitable than the vector one. This occurs when
1303          this function is invoked for prologue generation
1304          and the cost model check needs to be done at run
1305          time.
1306
1307          Resulting CFG after prologue peeling would be:
1308
1309          if (scalar_loop_iterations <= th)
1310            FIRST_NITERS = scalar_loop_iterations
1311
1312          bb_before_first_loop:
1313          if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1314                                 GOTO first-loop
1315
1316          first_loop:
1317          do {
1318          } while ...
1319
1320          bb_before_second_loop:
1321
1322          second_loop:
1323          do {
1324          } while ...
1325
1326          orig_exit_bb:
1327
1328      2.c Add the cost model check that allows the epilogue
1329          to iterate for the entire unchanged scalar
1330          iterations of the loop in the event that the cost
1331          model indicates that the scalar loop is more
1332          profitable than the vector one. This occurs when
1333          this function is invoked for epilogue generation
1334          and the cost model check needs to be done at run
1335          time.  This check is combined with any pre-existing
1336          check in COND_EXPR to avoid versioning.
1337
1338          Resulting CFG after prologue peeling would be:
1339
1340          bb_before_first_loop:
1341          if ((scalar_loop_iterations <= th)
1342              ||
1343              FIRST_NITERS == 0) GOTO bb_before_second_loop
1344                                 GOTO first-loop
1345
1346          first_loop:
1347          do {
1348          } while ...
1349
1350          bb_before_second_loop:
1351
1352          second_loop:
1353          do {
1354          } while ...
1355
1356          orig_exit_bb:
1357   */
1358
1359   bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
1360   bb_before_second_loop = split_edge (single_exit (first_loop));
1361
1362   /* Epilogue peeling.  */
1363   if (!update_first_loop_count)
1364     {
1365       pre_condition =
1366         fold_build2 (LE_EXPR, boolean_type_node, *first_niters,
1367                      build_int_cst (TREE_TYPE (*first_niters), 0));
1368       if (check_profitability)
1369         {
1370           tree scalar_loop_iters
1371             = unshare_expr (LOOP_VINFO_NITERS_UNCHANGED
1372                                         (loop_vec_info_for_loop (loop)));
1373           cost_pre_condition =
1374             fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
1375                          build_int_cst (TREE_TYPE (scalar_loop_iters), th));
1376
1377           pre_condition = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1378                                        cost_pre_condition, pre_condition);
1379         }
1380       if (cond_expr)
1381         {
1382           pre_condition =
1383             fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1384                          pre_condition,
1385                          fold_build1 (TRUTH_NOT_EXPR, boolean_type_node,
1386                                       cond_expr));
1387         }
1388     }
1389
1390   /* Prologue peeling.  */
1391   else
1392     {
1393       if (check_profitability)
1394         set_prologue_iterations (bb_before_first_loop, first_niters,
1395                                  loop, th);
1396
1397       pre_condition =
1398         fold_build2 (LE_EXPR, boolean_type_node, *first_niters,
1399                      build_int_cst (TREE_TYPE (*first_niters), 0));
1400     }
1401
1402   skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
1403                                   cond_expr_stmt_list,
1404                                   bb_before_second_loop, bb_before_first_loop);
1405   slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
1406                                       first_loop == new_loop,
1407                                       &new_exit_bb, &definitions);
1408
1409
1410   /* 3. Add the guard that controls whether the second loop is executed.
1411         Resulting CFG would be:
1412
1413         bb_before_first_loop:
1414         if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1415                                GOTO first-loop
1416
1417         first_loop:
1418         do {
1419         } while ...
1420
1421         bb_between_loops:
1422         if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1423                                     GOTO bb_before_second_loop
1424
1425         bb_before_second_loop:
1426
1427         second_loop:
1428         do {
1429         } while ...
1430
1431         bb_after_second_loop:
1432
1433         orig_exit_bb:
1434    */
1435
1436   bb_between_loops = new_exit_bb;
1437   bb_after_second_loop = split_edge (single_exit (second_loop));
1438
1439   pre_condition =
1440         fold_build2 (EQ_EXPR, boolean_type_node, *first_niters, niters);
1441   skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition, NULL,
1442                                   bb_after_second_loop, bb_before_first_loop);
1443   slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
1444                                      second_loop == new_loop, &new_exit_bb);
1445
1446   /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1447    */
1448   if (update_first_loop_count)
1449     slpeel_make_loop_iterate_ntimes (first_loop, *first_niters);
1450
1451   BITMAP_FREE (definitions);
1452   delete_update_ssa ();
1453
1454   adjust_vec_debug_stmts ();
1455
1456   return new_loop;
1457 }
1458
1459 /* Function vect_get_loop_location.
1460
1461    Extract the location of the loop in the source code.
1462    If the loop is not well formed for vectorization, an estimated
1463    location is calculated.
1464    Return the loop location if succeed and NULL if not.  */
1465
1466 LOC
1467 find_loop_location (struct loop *loop)
1468 {
1469   gimple stmt = NULL;
1470   basic_block bb;
1471   gimple_stmt_iterator si;
1472
1473   if (!loop)
1474     return UNKNOWN_LOC;
1475
1476   stmt = get_loop_exit_condition (loop);
1477
1478   if (stmt && gimple_location (stmt) != UNKNOWN_LOC)
1479     return gimple_location (stmt);
1480
1481   /* If we got here the loop is probably not "well formed",
1482      try to estimate the loop location */
1483
1484   if (!loop->header)
1485     return UNKNOWN_LOC;
1486
1487   bb = loop->header;
1488
1489   for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1490     {
1491       stmt = gsi_stmt (si);
1492       if (gimple_location (stmt) != UNKNOWN_LOC)
1493         return gimple_location (stmt);
1494     }
1495
1496   return UNKNOWN_LOC;
1497 }
1498
1499
1500 /* This function builds ni_name = number of iterations loop executes
1501    on the loop preheader.  If SEQ is given the stmt is instead emitted
1502    there.  */
1503
1504 static tree
1505 vect_build_loop_niters (loop_vec_info loop_vinfo, gimple_seq seq)
1506 {
1507   tree ni_name, var;
1508   gimple_seq stmts = NULL;
1509   edge pe;
1510   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1511   tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
1512
1513   var = create_tmp_var (TREE_TYPE (ni), "niters");
1514   add_referenced_var (var);
1515   ni_name = force_gimple_operand (ni, &stmts, false, var);
1516
1517   pe = loop_preheader_edge (loop);
1518   if (stmts)
1519     {
1520       if (seq)
1521         gimple_seq_add_seq (&seq, stmts);
1522       else
1523         {
1524           basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1525           gcc_assert (!new_bb);
1526         }
1527     }
1528
1529   return ni_name;
1530 }
1531
1532
1533 /* This function generates the following statements:
1534
1535  ni_name = number of iterations loop executes
1536  ratio = ni_name / vf
1537  ratio_mult_vf_name = ratio * vf
1538
1539  and places them at the loop preheader edge or in COND_EXPR_STMT_LIST
1540  if that is non-NULL.  */
1541
1542 static void
1543 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
1544                                  tree *ni_name_ptr,
1545                                  tree *ratio_mult_vf_name_ptr,
1546                                  tree *ratio_name_ptr,
1547                                  gimple_seq cond_expr_stmt_list)
1548 {
1549
1550   edge pe;
1551   basic_block new_bb;
1552   gimple_seq stmts;
1553   tree ni_name, ni_minus_gap_name;
1554   tree var;
1555   tree ratio_name;
1556   tree ratio_mult_vf_name;
1557   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1558   tree ni = LOOP_VINFO_NITERS (loop_vinfo);
1559   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1560   tree log_vf;
1561
1562   pe = loop_preheader_edge (loop);
1563
1564   /* Generate temporary variable that contains
1565      number of iterations loop executes.  */
1566
1567   ni_name = vect_build_loop_niters (loop_vinfo, cond_expr_stmt_list);
1568   log_vf = build_int_cst (TREE_TYPE (ni), exact_log2 (vf));
1569
1570   /* If epilogue loop is required because of data accesses with gaps, we
1571      subtract one iteration from the total number of iterations here for
1572      correct calculation of RATIO.  */
1573   if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
1574     {
1575       ni_minus_gap_name = fold_build2 (MINUS_EXPR, TREE_TYPE (ni_name),
1576                                        ni_name,
1577                                        build_one_cst (TREE_TYPE (ni_name)));
1578       if (!is_gimple_val (ni_minus_gap_name))
1579         {
1580           var = create_tmp_var (TREE_TYPE (ni), "ni_gap");
1581           add_referenced_var (var);
1582
1583           stmts = NULL;
1584           ni_minus_gap_name = force_gimple_operand (ni_minus_gap_name, &stmts,
1585                                                     true, var);
1586           if (cond_expr_stmt_list)
1587             gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
1588           else
1589             {
1590               pe = loop_preheader_edge (loop);
1591               new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1592               gcc_assert (!new_bb);
1593             }
1594         }
1595     }
1596   else
1597     ni_minus_gap_name = ni_name;
1598
1599   /* Create: ratio = ni >> log2(vf) */
1600
1601   ratio_name = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ni_minus_gap_name),
1602                             ni_minus_gap_name, log_vf);
1603   if (!is_gimple_val (ratio_name))
1604     {
1605       var = create_tmp_var (TREE_TYPE (ni), "bnd");
1606       add_referenced_var (var);
1607
1608       stmts = NULL;
1609       ratio_name = force_gimple_operand (ratio_name, &stmts, true, var);
1610       if (cond_expr_stmt_list)
1611         gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
1612       else
1613         {
1614           pe = loop_preheader_edge (loop);
1615           new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1616           gcc_assert (!new_bb);
1617         }
1618     }
1619
1620   /* Create: ratio_mult_vf = ratio << log2 (vf).  */
1621
1622   ratio_mult_vf_name = fold_build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name),
1623                                     ratio_name, log_vf);
1624   if (!is_gimple_val (ratio_mult_vf_name))
1625     {
1626       var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
1627       add_referenced_var (var);
1628
1629       stmts = NULL;
1630       ratio_mult_vf_name = force_gimple_operand (ratio_mult_vf_name, &stmts,
1631                                                  true, var);
1632       if (cond_expr_stmt_list)
1633         gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
1634       else
1635         {
1636           pe = loop_preheader_edge (loop);
1637           new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1638           gcc_assert (!new_bb);
1639         }
1640     }
1641
1642   *ni_name_ptr = ni_name;
1643   *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
1644   *ratio_name_ptr = ratio_name;
1645
1646   return;
1647 }
1648
1649 /* Function vect_can_advance_ivs_p
1650
1651    In case the number of iterations that LOOP iterates is unknown at compile
1652    time, an epilog loop will be generated, and the loop induction variables
1653    (IVs) will be "advanced" to the value they are supposed to take just before
1654    the epilog loop.  Here we check that the access function of the loop IVs
1655    and the expression that represents the loop bound are simple enough.
1656    These restrictions will be relaxed in the future.  */
1657
1658 bool
1659 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
1660 {
1661   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1662   basic_block bb = loop->header;
1663   gimple phi;
1664   gimple_stmt_iterator gsi;
1665
1666   /* Analyze phi functions of the loop header.  */
1667
1668   if (vect_print_dump_info (REPORT_DETAILS))
1669     fprintf (vect_dump, "vect_can_advance_ivs_p:");
1670
1671   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1672     {
1673       tree access_fn = NULL;
1674       tree evolution_part;
1675
1676       phi = gsi_stmt (gsi);
1677       if (vect_print_dump_info (REPORT_DETAILS))
1678         {
1679           fprintf (vect_dump, "Analyze phi: ");
1680           print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1681         }
1682
1683       /* Skip virtual phi's. The data dependences that are associated with
1684          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
1685
1686       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1687         {
1688           if (vect_print_dump_info (REPORT_DETAILS))
1689             fprintf (vect_dump, "virtual phi. skip.");
1690           continue;
1691         }
1692
1693       /* Skip reduction phis.  */
1694
1695       if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
1696         {
1697           if (vect_print_dump_info (REPORT_DETAILS))
1698             fprintf (vect_dump, "reduc phi. skip.");
1699           continue;
1700         }
1701
1702       /* Analyze the evolution function.  */
1703
1704       access_fn = instantiate_parameters
1705         (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
1706
1707       if (!access_fn)
1708         {
1709           if (vect_print_dump_info (REPORT_DETAILS))
1710             fprintf (vect_dump, "No Access function.");
1711           return false;
1712         }
1713
1714       if (vect_print_dump_info (REPORT_DETAILS))
1715         {
1716           fprintf (vect_dump, "Access function of PHI: ");
1717           print_generic_expr (vect_dump, access_fn, TDF_SLIM);
1718         }
1719
1720       evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
1721
1722       if (evolution_part == NULL_TREE)
1723         {
1724           if (vect_print_dump_info (REPORT_DETAILS))
1725             fprintf (vect_dump, "No evolution.");
1726           return false;
1727         }
1728
1729       /* FORNOW: We do not transform initial conditions of IVs
1730          which evolution functions are a polynomial of degree >= 2.  */
1731
1732       if (tree_is_chrec (evolution_part))
1733         return false;
1734     }
1735
1736   return true;
1737 }
1738
1739
1740 /*   Function vect_update_ivs_after_vectorizer.
1741
1742      "Advance" the induction variables of LOOP to the value they should take
1743      after the execution of LOOP.  This is currently necessary because the
1744      vectorizer does not handle induction variables that are used after the
1745      loop.  Such a situation occurs when the last iterations of LOOP are
1746      peeled, because:
1747      1. We introduced new uses after LOOP for IVs that were not originally used
1748         after LOOP: the IVs of LOOP are now used by an epilog loop.
1749      2. LOOP is going to be vectorized; this means that it will iterate N/VF
1750         times, whereas the loop IVs should be bumped N times.
1751
1752      Input:
1753      - LOOP - a loop that is going to be vectorized. The last few iterations
1754               of LOOP were peeled.
1755      - NITERS - the number of iterations that LOOP executes (before it is
1756                 vectorized). i.e, the number of times the ivs should be bumped.
1757      - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
1758                   coming out from LOOP on which there are uses of the LOOP ivs
1759                   (this is the path from LOOP->exit to epilog_loop->preheader).
1760
1761                   The new definitions of the ivs are placed in LOOP->exit.
1762                   The phi args associated with the edge UPDATE_E in the bb
1763                   UPDATE_E->dest are updated accordingly.
1764
1765      Assumption 1: Like the rest of the vectorizer, this function assumes
1766      a single loop exit that has a single predecessor.
1767
1768      Assumption 2: The phi nodes in the LOOP header and in update_bb are
1769      organized in the same order.
1770
1771      Assumption 3: The access function of the ivs is simple enough (see
1772      vect_can_advance_ivs_p).  This assumption will be relaxed in the future.
1773
1774      Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
1775      coming out of LOOP on which the ivs of LOOP are used (this is the path
1776      that leads to the epilog loop; other paths skip the epilog loop).  This
1777      path starts with the edge UPDATE_E, and its destination (denoted update_bb)
1778      needs to have its phis updated.
1779  */
1780
1781 static void
1782 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
1783                                   edge update_e)
1784 {
1785   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1786   basic_block exit_bb = single_exit (loop)->dest;
1787   gimple phi, phi1;
1788   gimple_stmt_iterator gsi, gsi1;
1789   basic_block update_bb = update_e->dest;
1790
1791   /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
1792
1793   /* Make sure there exists a single-predecessor exit bb:  */
1794   gcc_assert (single_pred_p (exit_bb));
1795
1796   for (gsi = gsi_start_phis (loop->header), gsi1 = gsi_start_phis (update_bb);
1797        !gsi_end_p (gsi) && !gsi_end_p (gsi1);
1798        gsi_next (&gsi), gsi_next (&gsi1))
1799     {
1800       tree init_expr;
1801       tree step_expr, off;
1802       tree type;
1803       tree var, ni, ni_name;
1804       gimple_stmt_iterator last_gsi;
1805       stmt_vec_info stmt_info;
1806
1807       phi = gsi_stmt (gsi);
1808       phi1 = gsi_stmt (gsi1);
1809       if (vect_print_dump_info (REPORT_DETAILS))
1810         {
1811           fprintf (vect_dump, "vect_update_ivs_after_vectorizer: phi: ");
1812           print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1813         }
1814
1815       /* Skip virtual phi's.  */
1816       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1817         {
1818           if (vect_print_dump_info (REPORT_DETAILS))
1819             fprintf (vect_dump, "virtual phi. skip.");
1820           continue;
1821         }
1822
1823       /* Skip reduction phis.  */
1824       stmt_info = vinfo_for_stmt (phi);
1825       if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
1826         {
1827           if (vect_print_dump_info (REPORT_DETAILS))
1828             fprintf (vect_dump, "reduc phi. skip.");
1829           continue;
1830         }
1831
1832       type = TREE_TYPE (gimple_phi_result (phi));
1833       step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
1834       step_expr = unshare_expr (step_expr);
1835
1836       /* FORNOW: We do not support IVs whose evolution function is a polynomial
1837          of degree >= 2 or exponential.  */
1838       gcc_assert (!tree_is_chrec (step_expr));
1839
1840       init_expr = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1841
1842       off = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
1843                          fold_convert (TREE_TYPE (step_expr), niters),
1844                          step_expr);
1845       if (POINTER_TYPE_P (type))
1846         ni = fold_build_pointer_plus (init_expr, off);
1847       else
1848         ni = fold_build2 (PLUS_EXPR, type,
1849                           init_expr, fold_convert (type, off));
1850
1851       var = create_tmp_var (type, "tmp");
1852       add_referenced_var (var);
1853
1854       last_gsi = gsi_last_bb (exit_bb);
1855       ni_name = force_gimple_operand_gsi (&last_gsi, ni, false, var,
1856                                           true, GSI_SAME_STMT);
1857
1858       /* Fix phi expressions in the successor bb.  */
1859       adjust_phi_and_debug_stmts (phi1, update_e, ni_name);
1860     }
1861 }
1862
1863 /* Return the more conservative threshold between the
1864    min_profitable_iters returned by the cost model and the user
1865    specified threshold, if provided.  */
1866
1867 static unsigned int
1868 conservative_cost_threshold (loop_vec_info loop_vinfo,
1869                              int min_profitable_iters)
1870 {
1871   unsigned int th;
1872   int min_scalar_loop_bound;
1873
1874   min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
1875                             * LOOP_VINFO_VECT_FACTOR (loop_vinfo)) - 1);
1876
1877   /* Use the cost model only if it is more conservative than user specified
1878      threshold.  */
1879   th = (unsigned) min_scalar_loop_bound;
1880   if (min_profitable_iters
1881       && (!min_scalar_loop_bound
1882           || min_profitable_iters > min_scalar_loop_bound))
1883     th = (unsigned) min_profitable_iters;
1884
1885   if (th && vect_print_dump_info (REPORT_COST))
1886     fprintf (vect_dump, "Profitability threshold is %u loop iterations.", th);
1887
1888   return th;
1889 }
1890
1891 /* Function vect_do_peeling_for_loop_bound
1892
1893    Peel the last iterations of the loop represented by LOOP_VINFO.
1894    The peeled iterations form a new epilog loop.  Given that the loop now
1895    iterates NITERS times, the new epilog loop iterates
1896    NITERS % VECTORIZATION_FACTOR times.
1897
1898    The original loop will later be made to iterate
1899    NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).
1900
1901    COND_EXPR and COND_EXPR_STMT_LIST are combined with a new generated
1902    test.  */
1903
1904 void
1905 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio,
1906                                 tree cond_expr, gimple_seq cond_expr_stmt_list)
1907 {
1908   tree ni_name, ratio_mult_vf_name;
1909   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1910   struct loop *new_loop;
1911   edge update_e;
1912   basic_block preheader;
1913   int loop_num;
1914   bool check_profitability = false;
1915   unsigned int th = 0;
1916   int min_profitable_iters;
1917
1918   if (vect_print_dump_info (REPORT_DETAILS))
1919     fprintf (vect_dump, "=== vect_do_peeling_for_loop_bound ===");
1920
1921   initialize_original_copy_tables ();
1922
1923   /* Generate the following variables on the preheader of original loop:
1924
1925      ni_name = number of iteration the original loop executes
1926      ratio = ni_name / vf
1927      ratio_mult_vf_name = ratio * vf  */
1928   vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
1929                                    &ratio_mult_vf_name, ratio,
1930                                    cond_expr_stmt_list);
1931
1932   loop_num  = loop->num;
1933
1934   /* If cost model check not done during versioning and
1935      peeling for alignment.  */
1936   if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
1937       && !LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo)
1938       && !LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo)
1939       && !cond_expr)
1940     {
1941       check_profitability = true;
1942
1943       /* Get profitability threshold for vectorized loop.  */
1944       min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
1945
1946       th = conservative_cost_threshold (loop_vinfo,
1947                                         min_profitable_iters);
1948     }
1949
1950   new_loop = slpeel_tree_peel_loop_to_edge (loop, single_exit (loop),
1951                                             &ratio_mult_vf_name, ni_name, false,
1952                                             th, check_profitability,
1953                                             cond_expr, cond_expr_stmt_list);
1954   gcc_assert (new_loop);
1955   gcc_assert (loop_num == loop->num);
1956 #ifdef ENABLE_CHECKING
1957   slpeel_verify_cfg_after_peeling (loop, new_loop);
1958 #endif
1959
1960   /* A guard that controls whether the new_loop is to be executed or skipped
1961      is placed in LOOP->exit.  LOOP->exit therefore has two successors - one
1962      is the preheader of NEW_LOOP, where the IVs from LOOP are used.  The other
1963      is a bb after NEW_LOOP, where these IVs are not used.  Find the edge that
1964      is on the path where the LOOP IVs are used and need to be updated.  */
1965
1966   preheader = loop_preheader_edge (new_loop)->src;
1967   if (EDGE_PRED (preheader, 0)->src == single_exit (loop)->dest)
1968     update_e = EDGE_PRED (preheader, 0);
1969   else
1970     update_e = EDGE_PRED (preheader, 1);
1971
1972   /* Update IVs of original loop as if they were advanced
1973      by ratio_mult_vf_name steps.  */
1974   vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e);
1975
1976   /* After peeling we have to reset scalar evolution analyzer.  */
1977   scev_reset ();
1978
1979   free_original_copy_tables ();
1980 }
1981
1982
1983 /* Function vect_gen_niters_for_prolog_loop
1984
1985    Set the number of iterations for the loop represented by LOOP_VINFO
1986    to the minimum between LOOP_NITERS (the original iteration count of the loop)
1987    and the misalignment of DR - the data reference recorded in
1988    LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO).  As a result, after the execution of
1989    this loop, the data reference DR will refer to an aligned location.
1990
1991    The following computation is generated:
1992
1993    If the misalignment of DR is known at compile time:
1994      addr_mis = int mis = DR_MISALIGNMENT (dr);
1995    Else, compute address misalignment in bytes:
1996      addr_mis = addr & (vectype_size - 1)
1997
1998    prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
1999
2000    (elem_size = element type size; an element is the scalar element whose type
2001    is the inner type of the vectype)
2002
2003    When the step of the data-ref in the loop is not 1 (as in interleaved data
2004    and SLP), the number of iterations of the prolog must be divided by the step
2005    (which is equal to the size of interleaved group).
2006
2007    The above formulas assume that VF == number of elements in the vector. This
2008    may not hold when there are multiple-types in the loop.
2009    In this case, for some data-references in the loop the VF does not represent
2010    the number of elements that fit in the vector.  Therefore, instead of VF we
2011    use TYPE_VECTOR_SUBPARTS.  */
2012
2013 static tree
2014 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters)
2015 {
2016   struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
2017   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2018   tree var;
2019   gimple_seq stmts;
2020   tree iters, iters_name;
2021   edge pe;
2022   basic_block new_bb;
2023   gimple dr_stmt = DR_STMT (dr);
2024   stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt);
2025   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2026   int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT;
2027   tree niters_type = TREE_TYPE (loop_niters);
2028   int nelements = TYPE_VECTOR_SUBPARTS (vectype);
2029
2030   pe = loop_preheader_edge (loop);
2031
2032   if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
2033     {
2034       int npeel = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
2035
2036       if (vect_print_dump_info (REPORT_DETAILS))
2037         fprintf (vect_dump, "known peeling = %d.", npeel);
2038
2039       iters = build_int_cst (niters_type, npeel);
2040     }
2041   else
2042     {
2043       gimple_seq new_stmts = NULL;
2044       bool negative = tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0;
2045       tree offset = negative
2046           ? size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1) : NULL_TREE;
2047       tree start_addr = vect_create_addr_base_for_vector_ref (dr_stmt,
2048                                                 &new_stmts, offset, loop);
2049       tree ptr_type = TREE_TYPE (start_addr);
2050       tree size = TYPE_SIZE (ptr_type);
2051       tree type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
2052       tree vectype_size_minus_1 = build_int_cst (type, vectype_align - 1);
2053       tree elem_size_log =
2054         build_int_cst (type, exact_log2 (vectype_align/nelements));
2055       tree nelements_minus_1 = build_int_cst (type, nelements - 1);
2056       tree nelements_tree = build_int_cst (type, nelements);
2057       tree byte_misalign;
2058       tree elem_misalign;
2059
2060       new_bb = gsi_insert_seq_on_edge_immediate (pe, new_stmts);
2061       gcc_assert (!new_bb);
2062
2063       /* Create:  byte_misalign = addr & (vectype_size - 1)  */
2064       byte_misalign =
2065         fold_build2 (BIT_AND_EXPR, type, fold_convert (type, start_addr), 
2066                      vectype_size_minus_1);
2067
2068       /* Create:  elem_misalign = byte_misalign / element_size  */
2069       elem_misalign =
2070         fold_build2 (RSHIFT_EXPR, type, byte_misalign, elem_size_log);
2071
2072       /* Create:  (niters_type) (nelements - elem_misalign)&(nelements - 1)  */
2073       if (negative)
2074         iters = fold_build2 (MINUS_EXPR, type, elem_misalign, nelements_tree);
2075       else
2076         iters = fold_build2 (MINUS_EXPR, type, nelements_tree, elem_misalign);
2077       iters = fold_build2 (BIT_AND_EXPR, type, iters, nelements_minus_1);
2078       iters = fold_convert (niters_type, iters);
2079     }
2080
2081   /* Create:  prolog_loop_niters = min (iters, loop_niters) */
2082   /* If the loop bound is known at compile time we already verified that it is
2083      greater than vf; since the misalignment ('iters') is at most vf, there's
2084      no need to generate the MIN_EXPR in this case.  */
2085   if (TREE_CODE (loop_niters) != INTEGER_CST)
2086     iters = fold_build2 (MIN_EXPR, niters_type, iters, loop_niters);
2087
2088   if (vect_print_dump_info (REPORT_DETAILS))
2089     {
2090       fprintf (vect_dump, "niters for prolog loop: ");
2091       print_generic_expr (vect_dump, iters, TDF_SLIM);
2092     }
2093
2094   var = create_tmp_var (niters_type, "prolog_loop_niters");
2095   add_referenced_var (var);
2096   stmts = NULL;
2097   iters_name = force_gimple_operand (iters, &stmts, false, var);
2098
2099   /* Insert stmt on loop preheader edge.  */
2100   if (stmts)
2101     {
2102       basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
2103       gcc_assert (!new_bb);
2104     }
2105
2106   return iters_name;
2107 }
2108
2109
2110 /* Function vect_update_init_of_dr
2111
2112    NITERS iterations were peeled from LOOP.  DR represents a data reference
2113    in LOOP.  This function updates the information recorded in DR to
2114    account for the fact that the first NITERS iterations had already been
2115    executed.  Specifically, it updates the OFFSET field of DR.  */
2116
2117 static void
2118 vect_update_init_of_dr (struct data_reference *dr, tree niters)
2119 {
2120   tree offset = DR_OFFSET (dr);
2121
2122   niters = fold_build2 (MULT_EXPR, sizetype,
2123                         fold_convert (sizetype, niters),
2124                         fold_convert (sizetype, DR_STEP (dr)));
2125   offset = fold_build2 (PLUS_EXPR, sizetype,
2126                         fold_convert (sizetype, offset), niters);
2127   DR_OFFSET (dr) = offset;
2128 }
2129
2130
2131 /* Function vect_update_inits_of_drs
2132
2133    NITERS iterations were peeled from the loop represented by LOOP_VINFO.
2134    This function updates the information recorded for the data references in
2135    the loop to account for the fact that the first NITERS iterations had
2136    already been executed.  Specifically, it updates the initial_condition of
2137    the access_function of all the data_references in the loop.  */
2138
2139 static void
2140 vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters)
2141 {
2142   unsigned int i;
2143   VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2144   struct data_reference *dr;
2145
2146   if (vect_print_dump_info (REPORT_DETAILS))
2147     fprintf (vect_dump, "=== vect_update_inits_of_dr ===");
2148
2149   FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
2150     vect_update_init_of_dr (dr, niters);
2151 }
2152
2153
2154 /* Function vect_do_peeling_for_alignment
2155
2156    Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
2157    'niters' is set to the misalignment of one of the data references in the
2158    loop, thereby forcing it to refer to an aligned location at the beginning
2159    of the execution of this loop.  The data reference for which we are
2160    peeling is recorded in LOOP_VINFO_UNALIGNED_DR.  */
2161
2162 void
2163 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo)
2164 {
2165   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2166   tree niters_of_prolog_loop, ni_name;
2167   tree n_iters;
2168   tree wide_prolog_niters;
2169   struct loop *new_loop;
2170   unsigned int th = 0;
2171   int min_profitable_iters;
2172
2173   if (vect_print_dump_info (REPORT_DETAILS))
2174     fprintf (vect_dump, "=== vect_do_peeling_for_alignment ===");
2175
2176   initialize_original_copy_tables ();
2177
2178   ni_name = vect_build_loop_niters (loop_vinfo, NULL);
2179   niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo,
2180                                                            ni_name);
2181
2182   /* Get profitability threshold for vectorized loop.  */
2183   min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
2184   th = conservative_cost_threshold (loop_vinfo,
2185                                     min_profitable_iters);
2186
2187   /* Peel the prolog loop and iterate it niters_of_prolog_loop.  */
2188   new_loop =
2189     slpeel_tree_peel_loop_to_edge (loop, loop_preheader_edge (loop),
2190                                    &niters_of_prolog_loop, ni_name, true,
2191                                    th, true, NULL_TREE, NULL);
2192
2193   gcc_assert (new_loop);
2194 #ifdef ENABLE_CHECKING
2195   slpeel_verify_cfg_after_peeling (new_loop, loop);
2196 #endif
2197
2198   /* Update number of times loop executes.  */
2199   n_iters = LOOP_VINFO_NITERS (loop_vinfo);
2200   LOOP_VINFO_NITERS (loop_vinfo) = fold_build2 (MINUS_EXPR,
2201                 TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop);
2202
2203   if (types_compatible_p (sizetype, TREE_TYPE (niters_of_prolog_loop)))
2204     wide_prolog_niters = niters_of_prolog_loop;
2205   else
2206     {
2207       gimple_seq seq = NULL;
2208       edge pe = loop_preheader_edge (loop);
2209       tree wide_iters = fold_convert (sizetype, niters_of_prolog_loop);
2210       tree var = create_tmp_var (sizetype, "prolog_loop_adjusted_niters");
2211       add_referenced_var (var);
2212       wide_prolog_niters = force_gimple_operand (wide_iters, &seq, false,
2213                                                  var);
2214       if (seq)
2215         {
2216           /* Insert stmt on loop preheader edge.  */
2217           basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
2218           gcc_assert (!new_bb);
2219         }
2220     }
2221
2222   /* Update the init conditions of the access functions of all data refs.  */
2223   vect_update_inits_of_drs (loop_vinfo, wide_prolog_niters);
2224
2225   /* After peeling we have to reset scalar evolution analyzer.  */
2226   scev_reset ();
2227
2228   free_original_copy_tables ();
2229 }
2230
2231
2232 /* Function vect_create_cond_for_align_checks.
2233
2234    Create a conditional expression that represents the alignment checks for
2235    all of data references (array element references) whose alignment must be
2236    checked at runtime.
2237
2238    Input:
2239    COND_EXPR  - input conditional expression.  New conditions will be chained
2240                 with logical AND operation.
2241    LOOP_VINFO - two fields of the loop information are used.
2242                 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
2243                 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
2244
2245    Output:
2246    COND_EXPR_STMT_LIST - statements needed to construct the conditional
2247                          expression.
2248    The returned value is the conditional expression to be used in the if
2249    statement that controls which version of the loop gets executed at runtime.
2250
2251    The algorithm makes two assumptions:
2252      1) The number of bytes "n" in a vector is a power of 2.
2253      2) An address "a" is aligned if a%n is zero and that this
2254         test can be done as a&(n-1) == 0.  For example, for 16
2255         byte vectors the test is a&0xf == 0.  */
2256
2257 static void
2258 vect_create_cond_for_align_checks (loop_vec_info loop_vinfo,
2259                                    tree *cond_expr,
2260                                    gimple_seq *cond_expr_stmt_list)
2261 {
2262   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2263   VEC(gimple,heap) *may_misalign_stmts
2264     = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
2265   gimple ref_stmt;
2266   int mask = LOOP_VINFO_PTR_MASK (loop_vinfo);
2267   tree mask_cst;
2268   unsigned int i;
2269   tree psize;
2270   tree int_ptrsize_type;
2271   char tmp_name[20];
2272   tree or_tmp_name = NULL_TREE;
2273   tree and_tmp, and_tmp_name;
2274   gimple and_stmt;
2275   tree ptrsize_zero;
2276   tree part_cond_expr;
2277
2278   /* Check that mask is one less than a power of 2, i.e., mask is
2279      all zeros followed by all ones.  */
2280   gcc_assert ((mask != 0) && ((mask & (mask+1)) == 0));
2281
2282   /* CHECKME: what is the best integer or unsigned type to use to hold a
2283      cast from a pointer value?  */
2284   psize = TYPE_SIZE (ptr_type_node);
2285   int_ptrsize_type
2286     = lang_hooks.types.type_for_size (tree_low_cst (psize, 1), 0);
2287
2288   /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
2289      of the first vector of the i'th data reference. */
2290
2291   FOR_EACH_VEC_ELT (gimple, may_misalign_stmts, i, ref_stmt)
2292     {
2293       gimple_seq new_stmt_list = NULL;
2294       tree addr_base;
2295       tree addr_tmp, addr_tmp_name;
2296       tree or_tmp, new_or_tmp_name;
2297       gimple addr_stmt, or_stmt;
2298       stmt_vec_info stmt_vinfo = vinfo_for_stmt (ref_stmt);
2299       tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
2300       bool negative = tree_int_cst_compare
2301         (DR_STEP (STMT_VINFO_DATA_REF (stmt_vinfo)), size_zero_node) < 0;
2302       tree offset = negative
2303         ? size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1) : NULL_TREE;
2304
2305       /* create: addr_tmp = (int)(address_of_first_vector) */
2306       addr_base =
2307         vect_create_addr_base_for_vector_ref (ref_stmt, &new_stmt_list,
2308                                               offset, loop);
2309       if (new_stmt_list != NULL)
2310         gimple_seq_add_seq (cond_expr_stmt_list, new_stmt_list);
2311
2312       sprintf (tmp_name, "%s%d", "addr2int", i);
2313       addr_tmp = create_tmp_var (int_ptrsize_type, tmp_name);
2314       add_referenced_var (addr_tmp);
2315       addr_tmp_name = make_ssa_name (addr_tmp, NULL);
2316       addr_stmt = gimple_build_assign_with_ops (NOP_EXPR, addr_tmp_name,
2317                                                 addr_base, NULL_TREE);
2318       SSA_NAME_DEF_STMT (addr_tmp_name) = addr_stmt;
2319       gimple_seq_add_stmt (cond_expr_stmt_list, addr_stmt);
2320
2321       /* The addresses are OR together.  */
2322
2323       if (or_tmp_name != NULL_TREE)
2324         {
2325           /* create: or_tmp = or_tmp | addr_tmp */
2326           sprintf (tmp_name, "%s%d", "orptrs", i);
2327           or_tmp = create_tmp_var (int_ptrsize_type, tmp_name);
2328           add_referenced_var (or_tmp);
2329           new_or_tmp_name = make_ssa_name (or_tmp, NULL);
2330           or_stmt = gimple_build_assign_with_ops (BIT_IOR_EXPR,
2331                                                   new_or_tmp_name,
2332                                                   or_tmp_name, addr_tmp_name);
2333           SSA_NAME_DEF_STMT (new_or_tmp_name) = or_stmt;
2334           gimple_seq_add_stmt (cond_expr_stmt_list, or_stmt);
2335           or_tmp_name = new_or_tmp_name;
2336         }
2337       else
2338         or_tmp_name = addr_tmp_name;
2339
2340     } /* end for i */
2341
2342   mask_cst = build_int_cst (int_ptrsize_type, mask);
2343
2344   /* create: and_tmp = or_tmp & mask  */
2345   and_tmp = create_tmp_var (int_ptrsize_type, "andmask" );
2346   add_referenced_var (and_tmp);
2347   and_tmp_name = make_ssa_name (and_tmp, NULL);
2348
2349   and_stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, and_tmp_name,
2350                                            or_tmp_name, mask_cst);
2351   SSA_NAME_DEF_STMT (and_tmp_name) = and_stmt;
2352   gimple_seq_add_stmt (cond_expr_stmt_list, and_stmt);
2353
2354   /* Make and_tmp the left operand of the conditional test against zero.
2355      if and_tmp has a nonzero bit then some address is unaligned.  */
2356   ptrsize_zero = build_int_cst (int_ptrsize_type, 0);
2357   part_cond_expr = fold_build2 (EQ_EXPR, boolean_type_node,
2358                                 and_tmp_name, ptrsize_zero);
2359   if (*cond_expr)
2360     *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2361                               *cond_expr, part_cond_expr);
2362   else
2363     *cond_expr = part_cond_expr;
2364 }
2365
2366
2367 /* Function vect_vfa_segment_size.
2368
2369    Create an expression that computes the size of segment
2370    that will be accessed for a data reference.  The functions takes into
2371    account that realignment loads may access one more vector.
2372
2373    Input:
2374      DR: The data reference.
2375      LENGTH_FACTOR: segment length to consider.
2376
2377    Return an expression whose value is the size of segment which will be
2378    accessed by DR.  */
2379
2380 static tree
2381 vect_vfa_segment_size (struct data_reference *dr, tree length_factor)
2382 {
2383   tree segment_length;
2384
2385   if (!compare_tree_int (DR_STEP (dr), 0))
2386     segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
2387   else
2388     segment_length = size_binop (MULT_EXPR,
2389                                  fold_convert (sizetype, DR_STEP (dr)),
2390                                  fold_convert (sizetype, length_factor));
2391
2392   if (vect_supportable_dr_alignment (dr, false)
2393         == dr_explicit_realign_optimized)
2394     {
2395       tree vector_size = TYPE_SIZE_UNIT
2396                           (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr))));
2397
2398       segment_length = size_binop (PLUS_EXPR, segment_length, vector_size);
2399     }
2400   return segment_length;
2401 }
2402
2403
2404 /* Function vect_create_cond_for_alias_checks.
2405
2406    Create a conditional expression that represents the run-time checks for
2407    overlapping of address ranges represented by a list of data references
2408    relations passed as input.
2409
2410    Input:
2411    COND_EXPR  - input conditional expression.  New conditions will be chained
2412                 with logical AND operation.
2413    LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
2414                 to be checked.
2415
2416    Output:
2417    COND_EXPR - conditional expression.
2418    COND_EXPR_STMT_LIST - statements needed to construct the conditional
2419                          expression.
2420
2421
2422    The returned value is the conditional expression to be used in the if
2423    statement that controls which version of the loop gets executed at runtime.
2424 */
2425
2426 static void
2427 vect_create_cond_for_alias_checks (loop_vec_info loop_vinfo,
2428                                    tree * cond_expr,
2429                                    gimple_seq * cond_expr_stmt_list)
2430 {
2431   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2432   VEC (ddr_p, heap) * may_alias_ddrs =
2433     LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
2434   int vect_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2435   tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
2436
2437   ddr_p ddr;
2438   unsigned int i;
2439   tree part_cond_expr, length_factor;
2440
2441   /* Create expression
2442      ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
2443      || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
2444      &&
2445      ...
2446      &&
2447      ((store_ptr_n + store_segment_length_n) <= load_ptr_n)
2448      || (load_ptr_n + load_segment_length_n) <= store_ptr_n))  */
2449
2450   if (VEC_empty (ddr_p, may_alias_ddrs))
2451     return;
2452
2453   FOR_EACH_VEC_ELT (ddr_p, may_alias_ddrs, i, ddr)
2454     {
2455       struct data_reference *dr_a, *dr_b;
2456       gimple dr_group_first_a, dr_group_first_b;
2457       tree addr_base_a, addr_base_b;
2458       tree segment_length_a, segment_length_b;
2459       gimple stmt_a, stmt_b;
2460       tree seg_a_min, seg_a_max, seg_b_min, seg_b_max;
2461
2462       dr_a = DDR_A (ddr);
2463       stmt_a = DR_STMT (DDR_A (ddr));
2464       dr_group_first_a = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a));
2465       if (dr_group_first_a)
2466         {
2467           stmt_a = dr_group_first_a;
2468           dr_a = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_a));
2469         }
2470
2471       dr_b = DDR_B (ddr);
2472       stmt_b = DR_STMT (DDR_B (ddr));
2473       dr_group_first_b = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_b));
2474       if (dr_group_first_b)
2475         {
2476           stmt_b = dr_group_first_b;
2477           dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_b));
2478         }
2479
2480       addr_base_a =
2481         vect_create_addr_base_for_vector_ref (stmt_a, cond_expr_stmt_list,
2482                                               NULL_TREE, loop);
2483       addr_base_b =
2484         vect_create_addr_base_for_vector_ref (stmt_b, cond_expr_stmt_list,
2485                                               NULL_TREE, loop);
2486
2487       if (!operand_equal_p (DR_STEP (dr_a), DR_STEP (dr_b), 0))
2488         length_factor = scalar_loop_iters;
2489       else
2490         length_factor = size_int (vect_factor);
2491       segment_length_a = vect_vfa_segment_size (dr_a, length_factor);
2492       segment_length_b = vect_vfa_segment_size (dr_b, length_factor);
2493
2494       if (vect_print_dump_info (REPORT_DR_DETAILS))
2495         {
2496           fprintf (vect_dump,
2497                    "create runtime check for data references ");
2498           print_generic_expr (vect_dump, DR_REF (dr_a), TDF_SLIM);
2499           fprintf (vect_dump, " and ");
2500           print_generic_expr (vect_dump, DR_REF (dr_b), TDF_SLIM);
2501         }
2502
2503       seg_a_min = addr_base_a;
2504       seg_a_max = fold_build_pointer_plus (addr_base_a, segment_length_a);
2505       if (tree_int_cst_compare (DR_STEP (dr_a), size_zero_node) < 0)
2506         seg_a_min = seg_a_max, seg_a_max = addr_base_a;
2507
2508       seg_b_min = addr_base_b;
2509       seg_b_max = fold_build_pointer_plus (addr_base_b, segment_length_b);
2510       if (tree_int_cst_compare (DR_STEP (dr_b), size_zero_node) < 0)
2511         seg_b_min = seg_b_max, seg_b_max = addr_base_b;
2512
2513       part_cond_expr =
2514         fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
2515           fold_build2 (LE_EXPR, boolean_type_node, seg_a_max, seg_b_min),
2516           fold_build2 (LE_EXPR, boolean_type_node, seg_b_max, seg_a_min));
2517
2518       if (*cond_expr)
2519         *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2520                                   *cond_expr, part_cond_expr);
2521       else
2522         *cond_expr = part_cond_expr;
2523     }
2524
2525   if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS))
2526     fprintf (vect_dump, "created %u versioning for alias checks.\n",
2527              VEC_length (ddr_p, may_alias_ddrs));
2528 }
2529
2530
2531 /* Function vect_loop_versioning.
2532
2533    If the loop has data references that may or may not be aligned or/and
2534    has data reference relations whose independence was not proven then
2535    two versions of the loop need to be generated, one which is vectorized
2536    and one which isn't.  A test is then generated to control which of the
2537    loops is executed.  The test checks for the alignment of all of the
2538    data references that may or may not be aligned.  An additional
2539    sequence of runtime tests is generated for each pairs of DDRs whose
2540    independence was not proven.  The vectorized version of loop is
2541    executed only if both alias and alignment tests are passed.
2542
2543    The test generated to check which version of loop is executed
2544    is modified to also check for profitability as indicated by the
2545    cost model initially.
2546
2547    The versioning precondition(s) are placed in *COND_EXPR and
2548    *COND_EXPR_STMT_LIST.  If DO_VERSIONING is true versioning is
2549    also performed, otherwise only the conditions are generated.  */
2550
2551 void
2552 vect_loop_versioning (loop_vec_info loop_vinfo, bool do_versioning,
2553                       tree *cond_expr, gimple_seq *cond_expr_stmt_list)
2554 {
2555   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2556   basic_block condition_bb;
2557   gimple_stmt_iterator gsi, cond_exp_gsi;
2558   basic_block merge_bb;
2559   basic_block new_exit_bb;
2560   edge new_exit_e, e;
2561   gimple orig_phi, new_phi;
2562   tree arg;
2563   unsigned prob = 4 * REG_BR_PROB_BASE / 5;
2564   gimple_seq gimplify_stmt_list = NULL;
2565   tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
2566   int min_profitable_iters = 0;
2567   unsigned int th;
2568
2569   /* Get profitability threshold for vectorized loop.  */
2570   min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
2571
2572   th = conservative_cost_threshold (loop_vinfo,
2573                                     min_profitable_iters);
2574
2575   *cond_expr =
2576     fold_build2 (GT_EXPR, boolean_type_node, scalar_loop_iters,
2577                  build_int_cst (TREE_TYPE (scalar_loop_iters), th));
2578
2579   *cond_expr = force_gimple_operand (*cond_expr, cond_expr_stmt_list,
2580                                      false, NULL_TREE);
2581
2582   if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
2583       vect_create_cond_for_align_checks (loop_vinfo, cond_expr,
2584                                          cond_expr_stmt_list);
2585
2586   if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2587     vect_create_cond_for_alias_checks (loop_vinfo, cond_expr,
2588                                        cond_expr_stmt_list);
2589
2590   *cond_expr =
2591     fold_build2 (NE_EXPR, boolean_type_node, *cond_expr, integer_zero_node);
2592   *cond_expr =
2593     force_gimple_operand (*cond_expr, &gimplify_stmt_list, true, NULL_TREE);
2594   gimple_seq_add_seq (cond_expr_stmt_list, gimplify_stmt_list);
2595
2596   /* If we only needed the extra conditions and a new loop copy
2597      bail out here.  */
2598   if (!do_versioning)
2599     return;
2600
2601   initialize_original_copy_tables ();
2602   loop_version (loop, *cond_expr, &condition_bb,
2603                 prob, prob, REG_BR_PROB_BASE - prob, true);
2604   free_original_copy_tables();
2605
2606   /* Loop versioning violates an assumption we try to maintain during
2607      vectorization - that the loop exit block has a single predecessor.
2608      After versioning, the exit block of both loop versions is the same
2609      basic block (i.e. it has two predecessors). Just in order to simplify
2610      following transformations in the vectorizer, we fix this situation
2611      here by adding a new (empty) block on the exit-edge of the loop,
2612      with the proper loop-exit phis to maintain loop-closed-form.  */
2613
2614   merge_bb = single_exit (loop)->dest;
2615   gcc_assert (EDGE_COUNT (merge_bb->preds) == 2);
2616   new_exit_bb = split_edge (single_exit (loop));
2617   new_exit_e = single_exit (loop);
2618   e = EDGE_SUCC (new_exit_bb, 0);
2619
2620   for (gsi = gsi_start_phis (merge_bb); !gsi_end_p (gsi); gsi_next (&gsi))
2621     {
2622       orig_phi = gsi_stmt (gsi);
2623       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
2624                                   new_exit_bb);
2625       arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
2626       add_phi_arg (new_phi, arg, new_exit_e,
2627                    gimple_phi_arg_location_from_edge (orig_phi, e));
2628       adjust_phi_and_debug_stmts (orig_phi, e, PHI_RESULT (new_phi));
2629     }
2630
2631   /* End loop-exit-fixes after versioning.  */
2632
2633   update_ssa (TODO_update_ssa);
2634   if (*cond_expr_stmt_list)
2635     {
2636       cond_exp_gsi = gsi_last_bb (condition_bb);
2637       gsi_insert_seq_before (&cond_exp_gsi, *cond_expr_stmt_list,
2638                              GSI_SAME_STMT);
2639       *cond_expr_stmt_list = NULL;
2640     }
2641   *cond_expr = NULL_TREE;
2642 }
2643