OSDN Git Service

2007-04-22 Uros Bizjak <ubizjak@gmail.com>
[pf3gnuchains/gcc-fork.git] / gcc / tree-vectorizer.c
1 /* Loop Vectorization
2    Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3    Contributed by Dorit Naishlos <dorit@il.ibm.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21
22 /* Loop Vectorization Pass.
23
24    This pass tries to vectorize loops. This first implementation focuses on
25    simple inner-most loops, with no conditional control flow, and a set of
26    simple operations which vector form can be expressed using existing
27    tree codes (PLUS, MULT etc).
28
29    For example, the vectorizer transforms the following simple loop:
30
31         short a[N]; short b[N]; short c[N]; int i;
32
33         for (i=0; i<N; i++){
34           a[i] = b[i] + c[i];
35         }
36
37    as if it was manually vectorized by rewriting the source code into:
38
39         typedef int __attribute__((mode(V8HI))) v8hi;
40         short a[N];  short b[N]; short c[N];   int i;
41         v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
42         v8hi va, vb, vc;
43
44         for (i=0; i<N/8; i++){
45           vb = pb[i];
46           vc = pc[i];
47           va = vb + vc;
48           pa[i] = va;
49         }
50
51         The main entry to this pass is vectorize_loops(), in which
52    the vectorizer applies a set of analyses on a given set of loops,
53    followed by the actual vectorization transformation for the loops that
54    had successfully passed the analysis phase.
55
56         Throughout this pass we make a distinction between two types of
57    data: scalars (which are represented by SSA_NAMES), and memory references
58    ("data-refs"). These two types of data require different handling both 
59    during analysis and transformation. The types of data-refs that the 
60    vectorizer currently supports are ARRAY_REFS which base is an array DECL 
61    (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
62    accesses are required to have a  simple (consecutive) access pattern.
63
64    Analysis phase:
65    ===============
66         The driver for the analysis phase is vect_analyze_loop_nest().
67    It applies a set of analyses, some of which rely on the scalar evolution 
68    analyzer (scev) developed by Sebastian Pop.
69
70         During the analysis phase the vectorizer records some information
71    per stmt in a "stmt_vec_info" struct which is attached to each stmt in the 
72    loop, as well as general information about the loop as a whole, which is
73    recorded in a "loop_vec_info" struct attached to each loop.
74
75    Transformation phase:
76    =====================
77         The loop transformation phase scans all the stmts in the loop, and
78    creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
79    the loop that needs to be vectorized. It insert the vector code sequence
80    just before the scalar stmt S, and records a pointer to the vector code
81    in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct 
82    attached to S). This pointer will be used for the vectorization of following
83    stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
84    otherwise, we rely on dead code elimination for removing it.
85
86         For example, say stmt S1 was vectorized into stmt VS1:
87
88    VS1: vb = px[i];
89    S1:  b = x[i];    STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
90    S2:  a = b;
91
92    To vectorize stmt S2, the vectorizer first finds the stmt that defines
93    the operand 'b' (S1), and gets the relevant vector def 'vb' from the
94    vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
95    resulting sequence would be:
96
97    VS1: vb = px[i];
98    S1:  b = x[i];       STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
99    VS2: va = vb;
100    S2:  a = b;          STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
101
102         Operands that are not SSA_NAMEs, are data-refs that appear in 
103    load/store operations (like 'x[i]' in S1), and are handled differently.
104
105    Target modeling:
106    =================
107         Currently the only target specific information that is used is the
108    size of the vector (in bytes) - "UNITS_PER_SIMD_WORD". Targets that can 
109    support different sizes of vectors, for now will need to specify one value 
110    for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
111
112         Since we only vectorize operations which vector form can be
113    expressed using existing tree codes, to verify that an operation is
114    supported, the vectorizer checks the relevant optab at the relevant
115    machine_mode (e.g, add_optab->handlers[(int) V8HImode].insn_code). If
116    the value found is CODE_FOR_nothing, then there's no target support, and
117    we can't vectorize the stmt.
118
119    For additional information on this project see:
120    http://gcc.gnu.org/projects/tree-ssa/vectorization.html
121 */
122
123 #include "config.h"
124 #include "system.h"
125 #include "coretypes.h"
126 #include "tm.h"
127 #include "ggc.h"
128 #include "tree.h"
129 #include "target.h"
130 #include "rtl.h"
131 #include "basic-block.h"
132 #include "diagnostic.h"
133 #include "tree-flow.h"
134 #include "tree-dump.h"
135 #include "timevar.h"
136 #include "cfgloop.h"
137 #include "cfglayout.h"
138 #include "expr.h"
139 #include "recog.h"
140 #include "optabs.h"
141 #include "params.h"
142 #include "toplev.h"
143 #include "tree-chrec.h"
144 #include "tree-data-ref.h"
145 #include "tree-scalar-evolution.h"
146 #include "input.h"
147 #include "tree-vectorizer.h"
148 #include "tree-pass.h"
149
150 /*************************************************************************
151   Simple Loop Peeling Utilities
152  *************************************************************************/
153 static void slpeel_update_phis_for_duplicate_loop 
154   (struct loop *, struct loop *, bool after);
155 static void slpeel_update_phi_nodes_for_guard1 
156   (edge, struct loop *, bool, basic_block *, bitmap *); 
157 static void slpeel_update_phi_nodes_for_guard2 
158   (edge, struct loop *, bool, basic_block *);
159 static edge slpeel_add_loop_guard (basic_block, tree, basic_block, basic_block);
160
161 static void rename_use_op (use_operand_p);
162 static void rename_variables_in_bb (basic_block);
163 static void rename_variables_in_loop (struct loop *);
164
165 /*************************************************************************
166   General Vectorization Utilities
167  *************************************************************************/
168 static void vect_set_dump_settings (void);
169
170 /* vect_dump will be set to stderr or dump_file if exist.  */
171 FILE *vect_dump;
172
173 /* vect_verbosity_level set to an invalid value 
174    to mark that it's uninitialized.  */
175 enum verbosity_levels vect_verbosity_level = MAX_VERBOSITY_LEVEL;
176
177 /* Loop location.  */
178 static LOC vect_loop_location;
179
180 /* Bitmap of virtual variables to be renamed.  */
181 bitmap vect_memsyms_to_rename;
182 \f
183 /*************************************************************************
184   Simple Loop Peeling Utilities
185
186   Utilities to support loop peeling for vectorization purposes.
187  *************************************************************************/
188
189
190 /* Renames the use *OP_P.  */
191
192 static void
193 rename_use_op (use_operand_p op_p)
194 {
195   tree new_name;
196
197   if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
198     return;
199
200   new_name = get_current_def (USE_FROM_PTR (op_p));
201
202   /* Something defined outside of the loop.  */
203   if (!new_name)
204     return;
205
206   /* An ordinary ssa name defined in the loop.  */
207
208   SET_USE (op_p, new_name);
209 }
210
211
212 /* Renames the variables in basic block BB.  */
213
214 static void
215 rename_variables_in_bb (basic_block bb)
216 {
217   tree phi;
218   block_stmt_iterator bsi;
219   tree stmt;
220   use_operand_p use_p;
221   ssa_op_iter iter;
222   edge e;
223   edge_iterator ei;
224   struct loop *loop = bb->loop_father;
225
226   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
227     {
228       stmt = bsi_stmt (bsi);
229       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
230         rename_use_op (use_p);
231     }
232
233   FOR_EACH_EDGE (e, ei, bb->succs)
234     {
235       if (!flow_bb_inside_loop_p (loop, e->dest))
236         continue;
237       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
238         rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e));
239     }
240 }
241
242
243 /* Renames variables in new generated LOOP.  */
244
245 static void
246 rename_variables_in_loop (struct loop *loop)
247 {
248   unsigned i;
249   basic_block *bbs;
250
251   bbs = get_loop_body (loop);
252
253   for (i = 0; i < loop->num_nodes; i++)
254     rename_variables_in_bb (bbs[i]);
255
256   free (bbs);
257 }
258
259
260 /* Update the PHI nodes of NEW_LOOP.
261
262    NEW_LOOP is a duplicate of ORIG_LOOP.
263    AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
264    AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
265    executes before it.  */
266
267 static void
268 slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
269                                        struct loop *new_loop, bool after)
270 {
271   tree new_ssa_name;
272   tree phi_new, phi_orig;
273   tree def;
274   edge orig_loop_latch = loop_latch_edge (orig_loop);
275   edge orig_entry_e = loop_preheader_edge (orig_loop);
276   edge new_loop_exit_e = single_exit (new_loop);
277   edge new_loop_entry_e = loop_preheader_edge (new_loop);
278   edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
279
280   /*
281      step 1. For each loop-header-phi:
282              Add the first phi argument for the phi in NEW_LOOP
283             (the one associated with the entry of NEW_LOOP)
284
285      step 2. For each loop-header-phi:
286              Add the second phi argument for the phi in NEW_LOOP
287             (the one associated with the latch of NEW_LOOP)
288
289      step 3. Update the phis in the successor block of NEW_LOOP.
290
291         case 1: NEW_LOOP was placed before ORIG_LOOP:
292                 The successor block of NEW_LOOP is the header of ORIG_LOOP.
293                 Updating the phis in the successor block can therefore be done
294                 along with the scanning of the loop header phis, because the
295                 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
296                 phi nodes, organized in the same order.
297
298         case 2: NEW_LOOP was placed after ORIG_LOOP:
299                 The successor block of NEW_LOOP is the original exit block of 
300                 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
301                 We postpone updating these phis to a later stage (when
302                 loop guards are added).
303    */
304
305
306   /* Scan the phis in the headers of the old and new loops
307      (they are organized in exactly the same order).  */
308
309   for (phi_new = phi_nodes (new_loop->header),
310        phi_orig = phi_nodes (orig_loop->header);
311        phi_new && phi_orig;
312        phi_new = PHI_CHAIN (phi_new), phi_orig = PHI_CHAIN (phi_orig))
313     {
314       /* step 1.  */
315       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
316       add_phi_arg (phi_new, def, new_loop_entry_e);
317
318       /* step 2.  */
319       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
320       if (TREE_CODE (def) != SSA_NAME)
321         continue;
322
323       new_ssa_name = get_current_def (def);
324       if (!new_ssa_name)
325         {
326           /* This only happens if there are no definitions
327              inside the loop. use the phi_result in this case.  */
328           new_ssa_name = PHI_RESULT (phi_new);
329         }
330
331       /* An ordinary ssa name defined in the loop.  */
332       add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
333
334       /* step 3 (case 1).  */
335       if (!after)
336         {
337           gcc_assert (new_loop_exit_e == orig_entry_e);
338           SET_PHI_ARG_DEF (phi_orig,
339                            new_loop_exit_e->dest_idx,
340                            new_ssa_name);
341         }
342     }
343 }
344
345
346 /* Update PHI nodes for a guard of the LOOP.
347
348    Input:
349    - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
350         controls whether LOOP is to be executed.  GUARD_EDGE is the edge that
351         originates from the guard-bb, skips LOOP and reaches the (unique) exit
352         bb of LOOP.  This loop-exit-bb is an empty bb with one successor.
353         We denote this bb NEW_MERGE_BB because before the guard code was added
354         it had a single predecessor (the LOOP header), and now it became a merge
355         point of two paths - the path that ends with the LOOP exit-edge, and
356         the path that ends with GUARD_EDGE.
357    - NEW_EXIT_BB: New basic block that is added by this function between LOOP
358         and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
359
360    ===> The CFG before the guard-code was added:
361         LOOP_header_bb:
362           loop_body
363           if (exit_loop) goto update_bb
364           else           goto LOOP_header_bb
365         update_bb:
366
367    ==> The CFG after the guard-code was added:
368         guard_bb:
369           if (LOOP_guard_condition) goto new_merge_bb
370           else                      goto LOOP_header_bb
371         LOOP_header_bb:
372           loop_body
373           if (exit_loop_condition) goto new_merge_bb
374           else                     goto LOOP_header_bb
375         new_merge_bb:
376           goto update_bb
377         update_bb:
378
379    ==> The CFG after this function:
380         guard_bb:
381           if (LOOP_guard_condition) goto new_merge_bb
382           else                      goto LOOP_header_bb
383         LOOP_header_bb:
384           loop_body
385           if (exit_loop_condition) goto new_exit_bb
386           else                     goto LOOP_header_bb
387         new_exit_bb:
388         new_merge_bb:
389           goto update_bb
390         update_bb:
391
392    This function:
393    1. creates and updates the relevant phi nodes to account for the new
394       incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
395       1.1. Create phi nodes at NEW_MERGE_BB.
396       1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
397            UPDATE_BB).  UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
398    2. preserves loop-closed-ssa-form by creating the required phi nodes
399       at the exit of LOOP (i.e, in NEW_EXIT_BB).
400
401    There are two flavors to this function:
402
403    slpeel_update_phi_nodes_for_guard1:
404      Here the guard controls whether we enter or skip LOOP, where LOOP is a
405      prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
406      for variables that have phis in the loop header.
407
408    slpeel_update_phi_nodes_for_guard2:
409      Here the guard controls whether we enter or skip LOOP, where LOOP is an
410      epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
411      for variables that have phis in the loop exit.
412
413    I.E., the overall structure is:
414
415         loop1_preheader_bb:
416                 guard1 (goto loop1/merg1_bb)
417         loop1
418         loop1_exit_bb:
419                 guard2 (goto merge1_bb/merge2_bb)
420         merge1_bb
421         loop2
422         loop2_exit_bb
423         merge2_bb
424         next_bb
425
426    slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
427    loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
428    that have phis in loop1->header).
429
430    slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
431    loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
432    that have phis in next_bb). It also adds some of these phis to
433    loop1_exit_bb.
434
435    slpeel_update_phi_nodes_for_guard1 is always called before
436    slpeel_update_phi_nodes_for_guard2. They are both needed in order
437    to create correct data-flow and loop-closed-ssa-form.
438
439    Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
440    that change between iterations of a loop (and therefore have a phi-node
441    at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
442    phis for variables that are used out of the loop (and therefore have 
443    loop-closed exit phis). Some variables may be both updated between 
444    iterations and used after the loop. This is why in loop1_exit_bb we
445    may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
446    and exit phis (created by slpeel_update_phi_nodes_for_guard2).
447
448    - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
449      an original loop. i.e., we have:
450
451            orig_loop
452            guard_bb (goto LOOP/new_merge)
453            new_loop <-- LOOP
454            new_exit
455            new_merge
456            next_bb
457
458      If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
459      have:
460
461            new_loop
462            guard_bb (goto LOOP/new_merge)
463            orig_loop <-- LOOP
464            new_exit
465            new_merge
466            next_bb
467
468      The SSA names defined in the original loop have a current
469      reaching definition that that records the corresponding new
470      ssa-name used in the new duplicated loop copy.
471   */
472
473 /* Function slpeel_update_phi_nodes_for_guard1
474    
475    Input:
476    - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
477    - DEFS - a bitmap of ssa names to mark new names for which we recorded
478             information. 
479    
480    In the context of the overall structure, we have:
481
482         loop1_preheader_bb: 
483                 guard1 (goto loop1/merg1_bb)
484 LOOP->  loop1
485         loop1_exit_bb:
486                 guard2 (goto merge1_bb/merge2_bb)
487         merge1_bb
488         loop2
489         loop2_exit_bb
490         merge2_bb
491         next_bb
492
493    For each name updated between loop iterations (i.e - for each name that has
494    an entry (loop-header) phi in LOOP) we create a new phi in:
495    1. merge1_bb (to account for the edge from guard1)
496    2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
497 */
498
499 static void
500 slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
501                                     bool is_new_loop, basic_block *new_exit_bb,
502                                     bitmap *defs)
503 {
504   tree orig_phi, new_phi;
505   tree update_phi, update_phi2;
506   tree guard_arg, loop_arg;
507   basic_block new_merge_bb = guard_edge->dest;
508   edge e = EDGE_SUCC (new_merge_bb, 0);
509   basic_block update_bb = e->dest;
510   basic_block orig_bb = loop->header;
511   edge new_exit_e;
512   tree current_new_name;
513   tree name;
514
515   /* Create new bb between loop and new_merge_bb.  */
516   *new_exit_bb = split_edge (single_exit (loop));
517
518   new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
519
520   for (orig_phi = phi_nodes (orig_bb), update_phi = phi_nodes (update_bb);
521        orig_phi && update_phi;
522        orig_phi = PHI_CHAIN (orig_phi), update_phi = PHI_CHAIN (update_phi))
523     {
524       /* Virtual phi; Mark it for renaming. We actually want to call
525          mar_sym_for_renaming, but since all ssa renaming datastructures
526          are going to be freed before we get to call ssa_upate, we just
527          record this name for now in a bitmap, and will mark it for
528          renaming later.  */
529       name = PHI_RESULT (orig_phi);
530       if (!is_gimple_reg (SSA_NAME_VAR (name)))
531         bitmap_set_bit (vect_memsyms_to_rename, DECL_UID (SSA_NAME_VAR (name)));
532
533       /** 1. Handle new-merge-point phis  **/
534
535       /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
536       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
537                                  new_merge_bb);
538
539       /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
540             of LOOP. Set the two phi args in NEW_PHI for these edges:  */
541       loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
542       guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
543
544       add_phi_arg (new_phi, loop_arg, new_exit_e);
545       add_phi_arg (new_phi, guard_arg, guard_edge);
546
547       /* 1.3. Update phi in successor block.  */
548       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
549                   || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
550       SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
551       update_phi2 = new_phi;
552
553
554       /** 2. Handle loop-closed-ssa-form phis  **/
555
556       if (!is_gimple_reg (PHI_RESULT (orig_phi)))
557         continue;
558
559       /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
560       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
561                                  *new_exit_bb);
562
563       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
564       add_phi_arg (new_phi, loop_arg, single_exit (loop));
565
566       /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
567       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
568       SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
569
570       /* 2.4. Record the newly created name with set_current_def.
571          We want to find a name such that
572                 name = get_current_def (orig_loop_name)
573          and to set its current definition as follows:
574                 set_current_def (name, new_phi_name)
575
576          If LOOP is a new loop then loop_arg is already the name we're
577          looking for. If LOOP is the original loop, then loop_arg is
578          the orig_loop_name and the relevant name is recorded in its
579          current reaching definition.  */
580       if (is_new_loop)
581         current_new_name = loop_arg;
582       else
583         {
584           current_new_name = get_current_def (loop_arg);
585           /* current_def is not available only if the variable does not
586              change inside the loop, in which case we also don't care
587              about recording a current_def for it because we won't be
588              trying to create loop-exit-phis for it.  */
589           if (!current_new_name)
590             continue;
591         }
592       gcc_assert (get_current_def (current_new_name) == NULL_TREE);
593
594       set_current_def (current_new_name, PHI_RESULT (new_phi));
595       bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
596     }
597
598   set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
599 }
600
601
602 /* Function slpeel_update_phi_nodes_for_guard2
603
604    Input:
605    - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
606
607    In the context of the overall structure, we have:
608
609         loop1_preheader_bb: 
610                 guard1 (goto loop1/merg1_bb)
611         loop1
612         loop1_exit_bb: 
613                 guard2 (goto merge1_bb/merge2_bb)
614         merge1_bb
615 LOOP->  loop2
616         loop2_exit_bb
617         merge2_bb
618         next_bb
619
620    For each name used out side the loop (i.e - for each name that has an exit
621    phi in next_bb) we create a new phi in:
622    1. merge2_bb (to account for the edge from guard_bb) 
623    2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
624    3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
625       if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
626 */
627
628 static void
629 slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
630                                     bool is_new_loop, basic_block *new_exit_bb)
631 {
632   tree orig_phi, new_phi;
633   tree update_phi, update_phi2;
634   tree guard_arg, loop_arg;
635   basic_block new_merge_bb = guard_edge->dest;
636   edge e = EDGE_SUCC (new_merge_bb, 0);
637   basic_block update_bb = e->dest;
638   edge new_exit_e;
639   tree orig_def, orig_def_new_name;
640   tree new_name, new_name2;
641   tree arg;
642
643   /* Create new bb between loop and new_merge_bb.  */
644   *new_exit_bb = split_edge (single_exit (loop));
645
646   new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
647
648   for (update_phi = phi_nodes (update_bb); update_phi; 
649        update_phi = PHI_CHAIN (update_phi))
650     {
651       orig_phi = update_phi;
652       orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
653       /* This loop-closed-phi actually doesn't represent a use
654          out of the loop - the phi arg is a constant.  */ 
655       if (TREE_CODE (orig_def) != SSA_NAME)
656         continue;
657       orig_def_new_name = get_current_def (orig_def);
658       arg = NULL_TREE;
659
660       /** 1. Handle new-merge-point phis  **/
661
662       /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
663       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
664                                  new_merge_bb);
665
666       /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
667             of LOOP. Set the two PHI args in NEW_PHI for these edges:  */
668       new_name = orig_def;
669       new_name2 = NULL_TREE;
670       if (orig_def_new_name)
671         {
672           new_name = orig_def_new_name;
673           /* Some variables have both loop-entry-phis and loop-exit-phis.
674              Such variables were given yet newer names by phis placed in
675              guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
676              new_name2 = get_current_def (get_current_def (orig_name)).  */
677           new_name2 = get_current_def (new_name);
678         }
679   
680       if (is_new_loop)
681         {
682           guard_arg = orig_def;
683           loop_arg = new_name;
684         }
685       else
686         {
687           guard_arg = new_name;
688           loop_arg = orig_def;
689         }
690       if (new_name2)
691         guard_arg = new_name2;
692   
693       add_phi_arg (new_phi, loop_arg, new_exit_e);
694       add_phi_arg (new_phi, guard_arg, guard_edge);
695
696       /* 1.3. Update phi in successor block.  */
697       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
698       SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
699       update_phi2 = new_phi;
700
701
702       /** 2. Handle loop-closed-ssa-form phis  **/
703
704       /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
705       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
706                                  *new_exit_bb);
707
708       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
709       add_phi_arg (new_phi, loop_arg, single_exit (loop));
710
711       /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
712       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
713       SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
714
715
716       /** 3. Handle loop-closed-ssa-form phis for first loop  **/
717
718       /* 3.1. Find the relevant names that need an exit-phi in
719          GUARD_BB, i.e. names for which
720          slpeel_update_phi_nodes_for_guard1 had not already created a
721          phi node. This is the case for names that are used outside
722          the loop (and therefore need an exit phi) but are not updated
723          across loop iterations (and therefore don't have a
724          loop-header-phi).
725
726          slpeel_update_phi_nodes_for_guard1 is responsible for
727          creating loop-exit phis in GUARD_BB for names that have a
728          loop-header-phi.  When such a phi is created we also record
729          the new name in its current definition.  If this new name
730          exists, then guard_arg was set to this new name (see 1.2
731          above).  Therefore, if guard_arg is not this new name, this
732          is an indication that an exit-phi in GUARD_BB was not yet
733          created, so we take care of it here.  */
734       if (guard_arg == new_name2)
735         continue;
736       arg = guard_arg;
737
738       /* 3.2. Generate new phi node in GUARD_BB:  */
739       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
740                                  guard_edge->src);
741
742       /* 3.3. GUARD_BB has one incoming edge:  */
743       gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
744       add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0));
745
746       /* 3.4. Update phi in successor of GUARD_BB:  */
747       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
748                                                                 == guard_arg);
749       SET_PHI_ARG_DEF (update_phi2, guard_edge->dest_idx, PHI_RESULT (new_phi));
750     }
751
752   set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
753 }
754
755
756 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
757    that starts at zero, increases by one and its limit is NITERS.
758
759    Assumption: the exit-condition of LOOP is the last stmt in the loop.  */
760
761 void
762 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
763 {
764   tree indx_before_incr, indx_after_incr, cond_stmt, cond;
765   tree orig_cond;
766   edge exit_edge = single_exit (loop);
767   block_stmt_iterator loop_cond_bsi;
768   block_stmt_iterator incr_bsi;
769   bool insert_after;
770   tree begin_label = tree_block_label (loop->latch);
771   tree exit_label = tree_block_label (single_exit (loop)->dest);
772   tree init = build_int_cst (TREE_TYPE (niters), 0);
773   tree step = build_int_cst (TREE_TYPE (niters), 1);
774   tree then_label;
775   tree else_label;
776   LOC loop_loc;
777
778   orig_cond = get_loop_exit_condition (loop);
779   gcc_assert (orig_cond);
780   loop_cond_bsi = bsi_for_stmt (orig_cond);
781
782   standard_iv_increment_position (loop, &incr_bsi, &insert_after);
783   create_iv (init, step, NULL_TREE, loop,
784              &incr_bsi, insert_after, &indx_before_incr, &indx_after_incr);
785
786   if (exit_edge->flags & EDGE_TRUE_VALUE) /* 'then' edge exits the loop.  */
787     {
788       cond = build2 (GE_EXPR, boolean_type_node, indx_after_incr, niters);
789       then_label = build1 (GOTO_EXPR, void_type_node, exit_label);
790       else_label = build1 (GOTO_EXPR, void_type_node, begin_label);
791     }
792   else /* 'then' edge loops back.  */
793     {
794       cond = build2 (LT_EXPR, boolean_type_node, indx_after_incr, niters);
795       then_label = build1 (GOTO_EXPR, void_type_node, begin_label);
796       else_label = build1 (GOTO_EXPR, void_type_node, exit_label);
797     }
798
799   cond_stmt = build3 (COND_EXPR, TREE_TYPE (orig_cond), cond,
800                      then_label, else_label);
801   bsi_insert_before (&loop_cond_bsi, cond_stmt, BSI_SAME_STMT);
802
803   /* Remove old loop exit test:  */
804   bsi_remove (&loop_cond_bsi, true);
805
806   loop_loc = find_loop_location (loop);
807   if (dump_file && (dump_flags & TDF_DETAILS))
808     {
809       if (loop_loc != UNKNOWN_LOC)
810         fprintf (dump_file, "\nloop at %s:%d: ",
811                  LOC_FILE (loop_loc), LOC_LINE (loop_loc));
812       print_generic_expr (dump_file, cond_stmt, TDF_SLIM);
813     }
814
815   loop->nb_iterations = niters;
816 }
817
818
819 /* Given LOOP this function generates a new copy of it and puts it 
820    on E which is either the entry or exit of LOOP.  */
821
822 static struct loop *
823 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
824 {
825   struct loop *new_loop;
826   basic_block *new_bbs, *bbs;
827   bool at_exit;
828   bool was_imm_dom;
829   basic_block exit_dest; 
830   tree phi, phi_arg;
831   edge exit, new_exit;
832
833   at_exit = (e == single_exit (loop)); 
834   if (!at_exit && e != loop_preheader_edge (loop))
835     return NULL;
836
837   bbs = get_loop_body (loop);
838
839   /* Check whether duplication is possible.  */
840   if (!can_copy_bbs_p (bbs, loop->num_nodes))
841     {
842       free (bbs);
843       return NULL;
844     }
845
846   /* Generate new loop structure.  */
847   new_loop = duplicate_loop (loop, loop->outer);
848   if (!new_loop)
849     {
850       free (bbs);
851       return NULL;
852     }
853
854   exit_dest = single_exit (loop)->dest;
855   was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS, 
856                                           exit_dest) == loop->header ? 
857                  true : false);
858
859   new_bbs = XNEWVEC (basic_block, loop->num_nodes);
860
861   exit = single_exit (loop);
862   copy_bbs (bbs, loop->num_nodes, new_bbs,
863             &exit, 1, &new_exit, NULL,
864             e->src);
865
866   /* Duplicating phi args at exit bbs as coming 
867      also from exit of duplicated loop.  */
868   for (phi = phi_nodes (exit_dest); phi; phi = PHI_CHAIN (phi))
869     {
870       phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
871       if (phi_arg)
872         {
873           edge new_loop_exit_edge;
874
875           if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
876             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
877           else
878             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
879   
880           add_phi_arg (phi, phi_arg, new_loop_exit_edge);       
881         }
882     }    
883    
884   if (at_exit) /* Add the loop copy at exit.  */
885     {
886       redirect_edge_and_branch_force (e, new_loop->header);
887       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
888       if (was_imm_dom)
889         set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
890     }
891   else /* Add the copy at entry.  */
892     {
893       edge new_exit_e;
894       edge entry_e = loop_preheader_edge (loop);
895       basic_block preheader = entry_e->src;
896            
897       if (!flow_bb_inside_loop_p (new_loop, 
898                                   EDGE_SUCC (new_loop->header, 0)->dest))
899         new_exit_e = EDGE_SUCC (new_loop->header, 0);
900       else
901         new_exit_e = EDGE_SUCC (new_loop->header, 1); 
902
903       redirect_edge_and_branch_force (new_exit_e, loop->header);
904       set_immediate_dominator (CDI_DOMINATORS, loop->header,
905                                new_exit_e->src);
906
907       /* We have to add phi args to the loop->header here as coming 
908          from new_exit_e edge.  */
909       for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
910         {
911           phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
912           if (phi_arg)
913             add_phi_arg (phi, phi_arg, new_exit_e);     
914         }    
915
916       redirect_edge_and_branch_force (entry_e, new_loop->header);
917       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
918     }
919
920   free (new_bbs);
921   free (bbs);
922
923   return new_loop;
924 }
925
926
927 /* Given the condition statement COND, put it as the last statement
928    of GUARD_BB; EXIT_BB is the basic block to skip the loop;
929    Assumes that this is the single exit of the guarded loop.  
930    Returns the skip edge.  */
931
932 static edge
933 slpeel_add_loop_guard (basic_block guard_bb, tree cond, basic_block exit_bb,
934                         basic_block dom_bb)
935 {
936   block_stmt_iterator bsi;
937   edge new_e, enter_e;
938   tree cond_stmt, then_label, else_label;
939
940   enter_e = EDGE_SUCC (guard_bb, 0);
941   enter_e->flags &= ~EDGE_FALLTHRU;
942   enter_e->flags |= EDGE_FALSE_VALUE;
943   bsi = bsi_last (guard_bb);
944
945   then_label = build1 (GOTO_EXPR, void_type_node,
946                        tree_block_label (exit_bb));
947   else_label = build1 (GOTO_EXPR, void_type_node,
948                        tree_block_label (enter_e->dest));
949   cond_stmt = build3 (COND_EXPR, void_type_node, cond,
950                      then_label, else_label);
951   bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
952   /* Add new edge to connect guard block to the merge/loop-exit block.  */
953   new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
954   set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
955   return new_e;
956 }
957
958
959 /* This function verifies that the following restrictions apply to LOOP:
960    (1) it is innermost
961    (2) it consists of exactly 2 basic blocks - header, and an empty latch.
962    (3) it is single entry, single exit
963    (4) its exit condition is the last stmt in the header
964    (5) E is the entry/exit edge of LOOP.
965  */
966
967 bool
968 slpeel_can_duplicate_loop_p (struct loop *loop, edge e)
969 {
970   edge exit_e = single_exit (loop);
971   edge entry_e = loop_preheader_edge (loop);
972   tree orig_cond = get_loop_exit_condition (loop);
973   block_stmt_iterator loop_exit_bsi = bsi_last (exit_e->src);
974
975   if (need_ssa_update_p ())
976     return false;
977
978   if (loop->inner
979       /* All loops have an outer scope; the only case loop->outer is NULL is for
980          the function itself.  */
981       || !loop->outer
982       || loop->num_nodes != 2
983       || !empty_block_p (loop->latch)
984       || !single_exit (loop)
985       /* Verify that new loop exit condition can be trivially modified.  */
986       || (!orig_cond || orig_cond != bsi_stmt (loop_exit_bsi))
987       || (e != exit_e && e != entry_e))
988     return false;
989
990   return true;
991 }
992
993 #ifdef ENABLE_CHECKING
994 void
995 slpeel_verify_cfg_after_peeling (struct loop *first_loop,
996                                  struct loop *second_loop)
997 {
998   basic_block loop1_exit_bb = single_exit (first_loop)->dest;
999   basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
1000   basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
1001
1002   /* A guard that controls whether the second_loop is to be executed or skipped
1003      is placed in first_loop->exit.  first_loopt->exit therefore has two
1004      successors - one is the preheader of second_loop, and the other is a bb
1005      after second_loop.
1006    */
1007   gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
1008    
1009   /* 1. Verify that one of the successors of first_loopt->exit is the preheader
1010         of second_loop.  */
1011    
1012   /* The preheader of new_loop is expected to have two predecessors:
1013      first_loop->exit and the block that precedes first_loop.  */
1014
1015   gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2 
1016               && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
1017                    && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
1018                || (EDGE_PRED (loop2_entry_bb, 1)->src ==  loop1_exit_bb
1019                    && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
1020   
1021   /* Verify that the other successor of first_loopt->exit is after the
1022      second_loop.  */
1023   /* TODO */
1024 }
1025 #endif
1026
1027 /* Function slpeel_tree_peel_loop_to_edge.
1028
1029    Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
1030    that is placed on the entry (exit) edge E of LOOP. After this transformation
1031    we have two loops one after the other - first-loop iterates FIRST_NITERS
1032    times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
1033
1034    Input:
1035    - LOOP: the loop to be peeled.
1036    - E: the exit or entry edge of LOOP.
1037         If it is the entry edge, we peel the first iterations of LOOP. In this
1038         case first-loop is LOOP, and second-loop is the newly created loop.
1039         If it is the exit edge, we peel the last iterations of LOOP. In this
1040         case, first-loop is the newly created loop, and second-loop is LOOP.
1041    - NITERS: the number of iterations that LOOP iterates.
1042    - FIRST_NITERS: the number of iterations that the first-loop should iterate.
1043    - UPDATE_FIRST_LOOP_COUNT:  specified whether this function is responsible
1044         for updating the loop bound of the first-loop to FIRST_NITERS.  If it
1045         is false, the caller of this function may want to take care of this
1046         (this can be useful if we don't want new stmts added to first-loop).
1047
1048    Output:
1049    The function returns a pointer to the new loop-copy, or NULL if it failed
1050    to perform the transformation.
1051
1052    The function generates two if-then-else guards: one before the first loop,
1053    and the other before the second loop:
1054    The first guard is:
1055      if (FIRST_NITERS == 0) then skip the first loop,
1056      and go directly to the second loop.
1057    The second guard is:
1058      if (FIRST_NITERS == NITERS) then skip the second loop.
1059
1060    FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
1061    FORNOW the resulting code will not be in loop-closed-ssa form.
1062 */
1063
1064 struct loop*
1065 slpeel_tree_peel_loop_to_edge (struct loop *loop, 
1066                                edge e, tree first_niters, 
1067                                tree niters, bool update_first_loop_count,
1068                                unsigned int th)
1069 {
1070   struct loop *new_loop = NULL, *first_loop, *second_loop;
1071   edge skip_e;
1072   tree pre_condition;
1073   bitmap definitions;
1074   basic_block bb_before_second_loop, bb_after_second_loop;
1075   basic_block bb_before_first_loop;
1076   basic_block bb_between_loops;
1077   basic_block new_exit_bb;
1078   edge exit_e = single_exit (loop);
1079   LOC loop_loc;
1080   
1081   if (!slpeel_can_duplicate_loop_p (loop, e))
1082     return NULL;
1083   
1084   /* We have to initialize cfg_hooks. Then, when calling
1085    cfg_hooks->split_edge, the function tree_split_edge 
1086    is actually called and, when calling cfg_hooks->duplicate_block,
1087    the function tree_duplicate_bb is called.  */
1088   tree_register_cfg_hooks ();
1089
1090
1091   /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1092         Resulting CFG would be:
1093
1094         first_loop:
1095         do {
1096         } while ...
1097
1098         second_loop:
1099         do {
1100         } while ...
1101
1102         orig_exit_bb:
1103    */
1104   
1105   if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e)))
1106     {
1107       loop_loc = find_loop_location (loop);
1108       if (dump_file && (dump_flags & TDF_DETAILS))
1109         {
1110           if (loop_loc != UNKNOWN_LOC)
1111             fprintf (dump_file, "\n%s:%d: note: ",
1112                      LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1113           fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
1114         }
1115       return NULL;
1116     }
1117   
1118   if (e == exit_e)
1119     {
1120       /* NEW_LOOP was placed after LOOP.  */
1121       first_loop = loop;
1122       second_loop = new_loop;
1123     }
1124   else
1125     {
1126       /* NEW_LOOP was placed before LOOP.  */
1127       first_loop = new_loop;
1128       second_loop = loop;
1129     }
1130
1131   definitions = ssa_names_to_replace ();
1132   slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
1133   rename_variables_in_loop (new_loop);
1134
1135
1136   /* 2. Add the guard that controls whether the first loop is executed.
1137         Resulting CFG would be:
1138
1139         bb_before_first_loop:
1140         if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1141                                GOTO first-loop
1142
1143         first_loop:
1144         do {
1145         } while ...
1146
1147         bb_before_second_loop:
1148
1149         second_loop:
1150         do {
1151         } while ...
1152
1153         orig_exit_bb:
1154    */
1155
1156   bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
1157   bb_before_second_loop = split_edge (single_exit (first_loop));
1158
1159   pre_condition =
1160     fold_build2 (LE_EXPR, boolean_type_node, first_niters, 
1161         build_int_cst (TREE_TYPE (first_niters), th));
1162
1163   skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
1164                                   bb_before_second_loop, bb_before_first_loop);
1165   slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
1166                                       first_loop == new_loop,
1167                                       &new_exit_bb, &definitions);
1168
1169
1170   /* 3. Add the guard that controls whether the second loop is executed.
1171         Resulting CFG would be:
1172
1173         bb_before_first_loop:
1174         if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1175                                GOTO first-loop
1176
1177         first_loop:
1178         do {
1179         } while ...
1180
1181         bb_between_loops:
1182         if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1183                                     GOTO bb_before_second_loop
1184
1185         bb_before_second_loop:
1186
1187         second_loop:
1188         do {
1189         } while ...
1190
1191         bb_after_second_loop:
1192
1193         orig_exit_bb:
1194    */
1195
1196   bb_between_loops = new_exit_bb;
1197   bb_after_second_loop = split_edge (single_exit (second_loop));
1198
1199   pre_condition = 
1200         fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
1201   skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition,
1202                                   bb_after_second_loop, bb_before_first_loop);
1203   slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
1204                                      second_loop == new_loop, &new_exit_bb);
1205
1206   /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1207    */
1208   if (update_first_loop_count)
1209     slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
1210
1211   BITMAP_FREE (definitions);
1212   delete_update_ssa ();
1213
1214   return new_loop;
1215 }
1216
1217 /* Function vect_get_loop_location.
1218
1219    Extract the location of the loop in the source code.
1220    If the loop is not well formed for vectorization, an estimated
1221    location is calculated.
1222    Return the loop location if succeed and NULL if not.  */
1223
1224 LOC
1225 find_loop_location (struct loop *loop)
1226 {
1227   tree node = NULL_TREE;
1228   basic_block bb;
1229   block_stmt_iterator si;
1230
1231   if (!loop)
1232     return UNKNOWN_LOC;
1233
1234   node = get_loop_exit_condition (loop);
1235
1236   if (node && CAN_HAVE_LOCATION_P (node) && EXPR_HAS_LOCATION (node)
1237       && EXPR_FILENAME (node) && EXPR_LINENO (node))
1238     return EXPR_LOC (node);
1239
1240   /* If we got here the loop is probably not "well formed",
1241      try to estimate the loop location */
1242
1243   if (!loop->header)
1244     return UNKNOWN_LOC;
1245
1246   bb = loop->header;
1247
1248   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1249     {
1250       node = bsi_stmt (si);
1251       if (node && CAN_HAVE_LOCATION_P (node) && EXPR_HAS_LOCATION (node))
1252         return EXPR_LOC (node);
1253     }
1254
1255   return UNKNOWN_LOC;
1256 }
1257
1258
1259 /*************************************************************************
1260   Vectorization Debug Information.
1261  *************************************************************************/
1262
1263 /* Function vect_set_verbosity_level.
1264
1265    Called from toplev.c upon detection of the
1266    -ftree-vectorizer-verbose=N option.  */
1267
1268 void
1269 vect_set_verbosity_level (const char *val)
1270 {
1271    unsigned int vl;
1272
1273    vl = atoi (val);
1274    if (vl < MAX_VERBOSITY_LEVEL)
1275      vect_verbosity_level = vl;
1276    else
1277      vect_verbosity_level = MAX_VERBOSITY_LEVEL - 1;
1278 }
1279
1280
1281 /* Function vect_set_dump_settings.
1282
1283    Fix the verbosity level of the vectorizer if the
1284    requested level was not set explicitly using the flag
1285    -ftree-vectorizer-verbose=N.
1286    Decide where to print the debugging information (dump_file/stderr).
1287    If the user defined the verbosity level, but there is no dump file,
1288    print to stderr, otherwise print to the dump file.  */
1289
1290 static void
1291 vect_set_dump_settings (void)
1292 {
1293   vect_dump = dump_file;
1294
1295   /* Check if the verbosity level was defined by the user:  */
1296   if (vect_verbosity_level != MAX_VERBOSITY_LEVEL)
1297     {
1298       /* If there is no dump file, print to stderr.  */
1299       if (!dump_file)
1300         vect_dump = stderr;
1301       return;
1302     }
1303
1304   /* User didn't specify verbosity level:  */
1305   if (dump_file && (dump_flags & TDF_DETAILS))
1306     vect_verbosity_level = REPORT_DETAILS;
1307   else if (dump_file && (dump_flags & TDF_STATS))
1308     vect_verbosity_level = REPORT_UNVECTORIZED_LOOPS;
1309   else
1310     vect_verbosity_level = REPORT_NONE;
1311
1312   gcc_assert (dump_file || vect_verbosity_level == REPORT_NONE);
1313 }
1314
1315
1316 /* Function debug_loop_details.
1317
1318    For vectorization debug dumps.  */
1319
1320 bool
1321 vect_print_dump_info (enum verbosity_levels vl)
1322 {
1323   if (vl > vect_verbosity_level)
1324     return false;
1325
1326   if (!current_function_decl || !vect_dump)
1327     return false;
1328
1329   if (vect_loop_location == UNKNOWN_LOC)
1330     fprintf (vect_dump, "\n%s:%d: note: ",
1331              DECL_SOURCE_FILE (current_function_decl),
1332              DECL_SOURCE_LINE (current_function_decl));
1333   else
1334     fprintf (vect_dump, "\n%s:%d: note: ", 
1335              LOC_FILE (vect_loop_location), LOC_LINE (vect_loop_location));
1336
1337   return true;
1338 }
1339
1340
1341 /*************************************************************************
1342   Vectorization Utilities.
1343  *************************************************************************/
1344
1345 /* Function new_stmt_vec_info.
1346
1347    Create and initialize a new stmt_vec_info struct for STMT.  */
1348
1349 stmt_vec_info
1350 new_stmt_vec_info (tree stmt, loop_vec_info loop_vinfo)
1351 {
1352   stmt_vec_info res;
1353   res = (stmt_vec_info) xcalloc (1, sizeof (struct _stmt_vec_info));
1354
1355   STMT_VINFO_TYPE (res) = undef_vec_info_type;
1356   STMT_VINFO_STMT (res) = stmt;
1357   STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
1358   STMT_VINFO_RELEVANT (res) = 0;
1359   STMT_VINFO_LIVE_P (res) = false;
1360   STMT_VINFO_VECTYPE (res) = NULL;
1361   STMT_VINFO_VEC_STMT (res) = NULL;
1362   STMT_VINFO_IN_PATTERN_P (res) = false;
1363   STMT_VINFO_RELATED_STMT (res) = NULL;
1364   STMT_VINFO_DATA_REF (res) = NULL;
1365   if (TREE_CODE (stmt) == PHI_NODE)
1366     STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
1367   else
1368     STMT_VINFO_DEF_TYPE (res) = vect_loop_def;
1369   STMT_VINFO_SAME_ALIGN_REFS (res) = VEC_alloc (dr_p, heap, 5);
1370   DR_GROUP_FIRST_DR (res) = NULL_TREE;
1371   DR_GROUP_NEXT_DR (res) = NULL_TREE;
1372   DR_GROUP_SIZE (res) = 0;
1373   DR_GROUP_STORE_COUNT (res) = 0;
1374   DR_GROUP_GAP (res) = 0;
1375   DR_GROUP_SAME_DR_STMT (res) = NULL_TREE;
1376   DR_GROUP_READ_WRITE_DEPENDENCE (res) = false;
1377
1378   return res;
1379 }
1380
1381
1382 /* Function new_loop_vec_info.
1383
1384    Create and initialize a new loop_vec_info struct for LOOP, as well as
1385    stmt_vec_info structs for all the stmts in LOOP.  */
1386
1387 loop_vec_info
1388 new_loop_vec_info (struct loop *loop)
1389 {
1390   loop_vec_info res;
1391   basic_block *bbs;
1392   block_stmt_iterator si;
1393   unsigned int i;
1394
1395   res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
1396
1397   bbs = get_loop_body (loop);
1398
1399   /* Create stmt_info for all stmts in the loop.  */
1400   for (i = 0; i < loop->num_nodes; i++)
1401     {
1402       basic_block bb = bbs[i];
1403       tree phi;
1404
1405       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1406         {
1407           stmt_ann_t ann = get_stmt_ann (phi);
1408           set_stmt_info (ann, new_stmt_vec_info (phi, res));
1409         }
1410
1411       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1412         {
1413           tree stmt = bsi_stmt (si);
1414           stmt_ann_t ann;
1415
1416           ann = stmt_ann (stmt);
1417           set_stmt_info (ann, new_stmt_vec_info (stmt, res));
1418         }
1419     }
1420
1421   LOOP_VINFO_LOOP (res) = loop;
1422   LOOP_VINFO_BBS (res) = bbs;
1423   LOOP_VINFO_EXIT_COND (res) = NULL;
1424   LOOP_VINFO_NITERS (res) = NULL;
1425   LOOP_VINFO_VECTORIZABLE_P (res) = 0;
1426   LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
1427   LOOP_VINFO_VECT_FACTOR (res) = 0;
1428   LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
1429   LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
1430   LOOP_VINFO_UNALIGNED_DR (res) = NULL;
1431   LOOP_VINFO_MAY_MISALIGN_STMTS (res)
1432     = VEC_alloc (tree, heap, PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS));
1433
1434   return res;
1435 }
1436
1437
1438 /* Function destroy_loop_vec_info.
1439  
1440    Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the 
1441    stmts in the loop.  */
1442
1443 void
1444 destroy_loop_vec_info (loop_vec_info loop_vinfo)
1445 {
1446   struct loop *loop;
1447   basic_block *bbs;
1448   int nbbs;
1449   block_stmt_iterator si;
1450   int j;
1451
1452   if (!loop_vinfo)
1453     return;
1454
1455   loop = LOOP_VINFO_LOOP (loop_vinfo);
1456
1457   bbs = LOOP_VINFO_BBS (loop_vinfo);
1458   nbbs = loop->num_nodes;
1459
1460   for (j = 0; j < nbbs; j++)
1461     {
1462       basic_block bb = bbs[j];
1463       tree phi;
1464       stmt_vec_info stmt_info;
1465
1466       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1467         {
1468           stmt_ann_t ann = stmt_ann (phi);
1469
1470           stmt_info = vinfo_for_stmt (phi);
1471           free (stmt_info);
1472           set_stmt_info (ann, NULL);
1473         }
1474
1475       for (si = bsi_start (bb); !bsi_end_p (si); )
1476         {
1477           tree stmt = bsi_stmt (si);
1478           stmt_ann_t ann = stmt_ann (stmt);
1479           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1480
1481           if (stmt_info)
1482             {
1483               /* Check if this is a "pattern stmt" (introduced by the 
1484                  vectorizer during the pattern recognition pass).  */
1485               bool remove_stmt_p = false;
1486               tree orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
1487               if (orig_stmt)
1488                 {
1489                   stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
1490                   if (orig_stmt_info
1491                       && STMT_VINFO_IN_PATTERN_P (orig_stmt_info))
1492                     remove_stmt_p = true; 
1493                 }
1494                         
1495               /* Free stmt_vec_info.  */
1496               VEC_free (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmt_info));
1497               free (stmt_info);
1498               set_stmt_info (ann, NULL);
1499
1500               /* Remove dead "pattern stmts".  */
1501               if (remove_stmt_p)
1502                 bsi_remove (&si, true);
1503             }
1504           bsi_next (&si);
1505         }
1506     }
1507
1508   free (LOOP_VINFO_BBS (loop_vinfo));
1509   free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
1510   free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
1511   VEC_free (tree, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
1512
1513   free (loop_vinfo);
1514   loop->aux = NULL;
1515 }
1516
1517
1518 /* Function vect_force_dr_alignment_p.
1519
1520    Returns whether the alignment of a DECL can be forced to be aligned
1521    on ALIGNMENT bit boundary.  */
1522
1523 bool 
1524 vect_can_force_dr_alignment_p (tree decl, unsigned int alignment)
1525 {
1526   if (TREE_CODE (decl) != VAR_DECL)
1527     return false;
1528
1529   if (DECL_EXTERNAL (decl))
1530     return false;
1531
1532   if (TREE_ASM_WRITTEN (decl))
1533     return false;
1534
1535   if (TREE_STATIC (decl))
1536     return (alignment <= MAX_OFILE_ALIGNMENT);
1537   else
1538     /* This is not 100% correct.  The absolute correct stack alignment
1539        is STACK_BOUNDARY.  We're supposed to hope, but not assume, that
1540        PREFERRED_STACK_BOUNDARY is honored by all translation units.
1541        However, until someone implements forced stack alignment, SSE
1542        isn't really usable without this.  */  
1543     return (alignment <= PREFERRED_STACK_BOUNDARY); 
1544 }
1545
1546
1547 /* Function get_vectype_for_scalar_type.
1548
1549    Returns the vector type corresponding to SCALAR_TYPE as supported
1550    by the target.  */
1551
1552 tree
1553 get_vectype_for_scalar_type (tree scalar_type)
1554 {
1555   enum machine_mode inner_mode = TYPE_MODE (scalar_type);
1556   int nbytes = GET_MODE_SIZE (inner_mode);
1557   int nunits;
1558   tree vectype;
1559
1560   if (nbytes == 0 || nbytes >= UNITS_PER_SIMD_WORD)
1561     return NULL_TREE;
1562
1563   /* FORNOW: Only a single vector size per target (UNITS_PER_SIMD_WORD)
1564      is expected.  */
1565   nunits = UNITS_PER_SIMD_WORD / nbytes;
1566
1567   vectype = build_vector_type (scalar_type, nunits);
1568   if (vect_print_dump_info (REPORT_DETAILS))
1569     {
1570       fprintf (vect_dump, "get vectype with %d units of type ", nunits);
1571       print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
1572     }
1573
1574   if (!vectype)
1575     return NULL_TREE;
1576
1577   if (vect_print_dump_info (REPORT_DETAILS))
1578     {
1579       fprintf (vect_dump, "vectype: ");
1580       print_generic_expr (vect_dump, vectype, TDF_SLIM);
1581     }
1582
1583   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
1584       && !INTEGRAL_MODE_P (TYPE_MODE (vectype)))
1585     {
1586       if (vect_print_dump_info (REPORT_DETAILS))
1587         fprintf (vect_dump, "mode not supported by target.");
1588       return NULL_TREE;
1589     }
1590
1591   return vectype;
1592 }
1593
1594
1595 /* Function vect_supportable_dr_alignment
1596
1597    Return whether the data reference DR is supported with respect to its
1598    alignment.  */
1599
1600 enum dr_alignment_support
1601 vect_supportable_dr_alignment (struct data_reference *dr)
1602 {
1603   tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
1604   enum machine_mode mode = (int) TYPE_MODE (vectype);
1605
1606   if (aligned_access_p (dr))
1607     return dr_aligned;
1608
1609   /* Possibly unaligned access.  */
1610   
1611   if (DR_IS_READ (dr))
1612     {
1613       if (vec_realign_load_optab->handlers[mode].insn_code != CODE_FOR_nothing
1614           && (!targetm.vectorize.builtin_mask_for_load
1615               || targetm.vectorize.builtin_mask_for_load ()))
1616         return dr_unaligned_software_pipeline;
1617
1618       if (movmisalign_optab->handlers[mode].insn_code != CODE_FOR_nothing)
1619         /* Can't software pipeline the loads, but can at least do them.  */
1620         return dr_unaligned_supported;
1621     }
1622
1623   /* Unsupported.  */
1624   return dr_unaligned_unsupported;
1625 }
1626
1627
1628 /* Function vect_is_simple_use.
1629
1630    Input:
1631    LOOP - the loop that is being vectorized.
1632    OPERAND - operand of a stmt in LOOP.
1633    DEF - the defining stmt in case OPERAND is an SSA_NAME.
1634
1635    Returns whether a stmt with OPERAND can be vectorized.
1636    Supportable operands are constants, loop invariants, and operands that are
1637    defined by the current iteration of the loop. Unsupportable operands are 
1638    those that are defined by a previous iteration of the loop (as is the case
1639    in reduction/induction computations).  */
1640
1641 bool
1642 vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt,
1643                     tree *def, enum vect_def_type *dt)
1644
1645   basic_block bb;
1646   stmt_vec_info stmt_vinfo;
1647   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1648
1649   *def_stmt = NULL_TREE;
1650   *def = NULL_TREE;
1651   
1652   if (vect_print_dump_info (REPORT_DETAILS))
1653     {
1654       fprintf (vect_dump, "vect_is_simple_use: operand ");
1655       print_generic_expr (vect_dump, operand, TDF_SLIM);
1656     }
1657     
1658   if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
1659     {
1660       *dt = vect_constant_def;
1661       return true;
1662     }
1663     
1664   if (TREE_CODE (operand) != SSA_NAME)
1665     {
1666       if (vect_print_dump_info (REPORT_DETAILS))
1667         fprintf (vect_dump, "not ssa-name.");
1668       return false;
1669     }
1670     
1671   *def_stmt = SSA_NAME_DEF_STMT (operand);
1672   if (*def_stmt == NULL_TREE )
1673     {
1674       if (vect_print_dump_info (REPORT_DETAILS))
1675         fprintf (vect_dump, "no def_stmt.");
1676       return false;
1677     }
1678
1679   if (vect_print_dump_info (REPORT_DETAILS))
1680     {
1681       fprintf (vect_dump, "def_stmt: ");
1682       print_generic_expr (vect_dump, *def_stmt, TDF_SLIM);
1683     }
1684
1685   /* empty stmt is expected only in case of a function argument.
1686      (Otherwise - we expect a phi_node or a GIMPLE_MODIFY_STMT).  */
1687   if (IS_EMPTY_STMT (*def_stmt))
1688     {
1689       tree arg = TREE_OPERAND (*def_stmt, 0);
1690       if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST)
1691         {
1692           *def = operand;
1693           *dt = vect_invariant_def;
1694           return true;
1695         }
1696
1697       if (vect_print_dump_info (REPORT_DETAILS))
1698         fprintf (vect_dump, "Unexpected empty stmt.");
1699       return false;
1700     }
1701
1702   bb = bb_for_stmt (*def_stmt);
1703   if (!flow_bb_inside_loop_p (loop, bb))
1704     *dt = vect_invariant_def;
1705   else
1706     {
1707       stmt_vinfo = vinfo_for_stmt (*def_stmt);
1708       *dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
1709     }
1710
1711   if (*dt == vect_unknown_def_type)
1712     {
1713       if (vect_print_dump_info (REPORT_DETAILS))
1714         fprintf (vect_dump, "Unsupported pattern.");
1715       return false;
1716     }
1717
1718   if (vect_print_dump_info (REPORT_DETAILS))
1719     fprintf (vect_dump, "type of def: %d.",*dt);
1720
1721   switch (TREE_CODE (*def_stmt))
1722     {
1723     case PHI_NODE:
1724       *def = PHI_RESULT (*def_stmt);
1725       gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def
1726                   || *dt == vect_invariant_def);
1727       break;
1728
1729     case GIMPLE_MODIFY_STMT:
1730       *def = GIMPLE_STMT_OPERAND (*def_stmt, 0);
1731       break;
1732
1733     default:
1734       if (vect_print_dump_info (REPORT_DETAILS))
1735         fprintf (vect_dump, "unsupported defining stmt: ");
1736       return false;
1737     }
1738
1739   return true;
1740 }
1741
1742
1743 /* Function supportable_widening_operation
1744
1745    Check whether an operation represented by the code CODE is a 
1746    widening operation that is supported by the target platform in 
1747    vector form (i.e., when operating on arguments of type VECTYPE).
1748     
1749    The two kinds of widening operations we currently support are
1750    NOP and WIDEN_MULT. This function checks if these operations
1751    are supported by the target platform either directly (via vector 
1752    tree-codes), or via target builtins.
1753
1754    Output:
1755    - CODE1 and CODE2 are codes of vector operations to be used when 
1756    vectorizing the operation, if available. 
1757    - DECL1 and DECL2 are decls of target builtin functions to be used
1758    when vectorizing the operation, if available. In this case,
1759    CODE1 and CODE2 are CALL_EXPR.  */
1760
1761 bool
1762 supportable_widening_operation (enum tree_code code, tree stmt, tree vectype,
1763                                 tree *decl1, tree *decl2,
1764                                 enum tree_code *code1, enum tree_code *code2)
1765 {
1766   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1767   bool ordered_p;
1768   enum machine_mode vec_mode;
1769   enum insn_code icode1, icode2;
1770   optab optab1, optab2;
1771   tree expr = GIMPLE_STMT_OPERAND (stmt, 1);
1772   tree type = TREE_TYPE (expr);
1773   tree wide_vectype = get_vectype_for_scalar_type (type);
1774   enum tree_code c1, c2;
1775
1776   /* The result of a vectorized widening operation usually requires two vectors
1777      (because the widened results do not fit int one vector). The generated 
1778      vector results would normally be expected to be generated in the same 
1779      order as in the original scalar computation. i.e. if 8 results are 
1780      generated in each vector iteration, they are to be organized as follows:
1781         vect1: [res1,res2,res3,res4], vect2: [res5,res6,res7,res8]. 
1782
1783      However, in the special case that the result of the widening operation is 
1784      used in a reduction computation only, the order doesn't matter (because
1785      when vectorizing a reduction we change the order of the computation). 
1786      Some targets can take advantage of this and generate more efficient code.
1787      For example, targets like Altivec, that support widen_mult using a sequence
1788      of {mult_even,mult_odd} generate the following vectors:
1789         vect1: [res1,res3,res5,res7], vect2: [res2,res4,res6,res8].  */
1790
1791    if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_by_reduction)
1792      ordered_p = false;
1793    else
1794      ordered_p = true;
1795
1796   if (!ordered_p
1797       && code == WIDEN_MULT_EXPR
1798       && targetm.vectorize.builtin_mul_widen_even
1799       && targetm.vectorize.builtin_mul_widen_even (vectype)
1800       && targetm.vectorize.builtin_mul_widen_odd
1801       && targetm.vectorize.builtin_mul_widen_odd (vectype))
1802     {
1803       if (vect_print_dump_info (REPORT_DETAILS))
1804         fprintf (vect_dump, "Unordered widening operation detected.");
1805
1806       *code1 = *code2 = CALL_EXPR;
1807       *decl1 = targetm.vectorize.builtin_mul_widen_even (vectype);
1808       *decl2 = targetm.vectorize.builtin_mul_widen_odd (vectype);
1809       return true;
1810     }
1811
1812   switch (code)
1813     {
1814     case WIDEN_MULT_EXPR:
1815       if (BYTES_BIG_ENDIAN)
1816         {
1817           c1 = VEC_WIDEN_MULT_HI_EXPR;
1818           c2 = VEC_WIDEN_MULT_LO_EXPR;
1819         }
1820       else
1821         {
1822           c2 = VEC_WIDEN_MULT_HI_EXPR;
1823           c1 = VEC_WIDEN_MULT_LO_EXPR;
1824         }
1825       break;
1826
1827     case NOP_EXPR:
1828       if (BYTES_BIG_ENDIAN)
1829         {
1830           c1 = VEC_UNPACK_HI_EXPR;
1831           c2 = VEC_UNPACK_LO_EXPR;
1832         }
1833       else
1834         {
1835           c2 = VEC_UNPACK_HI_EXPR;
1836           c1 = VEC_UNPACK_LO_EXPR;
1837         }
1838       break;
1839
1840     default:
1841       gcc_unreachable ();
1842     }
1843
1844   *code1 = c1;
1845   *code2 = c2;
1846   optab1 = optab_for_tree_code (c1, vectype);
1847   optab2 = optab_for_tree_code (c2, vectype);
1848
1849   if (!optab1 || !optab2)
1850     return false;
1851
1852   vec_mode = TYPE_MODE (vectype);
1853   if ((icode1 = optab1->handlers[(int) vec_mode].insn_code) == CODE_FOR_nothing
1854       || insn_data[icode1].operand[0].mode != TYPE_MODE (wide_vectype)
1855       || (icode2 = optab2->handlers[(int) vec_mode].insn_code)
1856                                                         == CODE_FOR_nothing
1857       || insn_data[icode2].operand[0].mode != TYPE_MODE (wide_vectype))
1858     return false;
1859
1860   return true;
1861 }
1862
1863
1864 /* Function reduction_code_for_scalar_code
1865
1866    Input:
1867    CODE - tree_code of a reduction operations.
1868
1869    Output:
1870    REDUC_CODE - the corresponding tree-code to be used to reduce the
1871       vector of partial results into a single scalar result (which
1872       will also reside in a vector).
1873
1874    Return TRUE if a corresponding REDUC_CODE was found, FALSE otherwise.  */
1875
1876 bool
1877 reduction_code_for_scalar_code (enum tree_code code,
1878                                 enum tree_code *reduc_code)
1879 {
1880   switch (code)
1881   {
1882   case MAX_EXPR:
1883     *reduc_code = REDUC_MAX_EXPR;
1884     return true;
1885
1886   case MIN_EXPR:
1887     *reduc_code = REDUC_MIN_EXPR;
1888     return true;
1889
1890   case PLUS_EXPR:
1891     *reduc_code = REDUC_PLUS_EXPR;
1892     return true;
1893
1894   default:
1895     return false;
1896   }
1897 }
1898
1899
1900 /* Function vect_is_simple_reduction
1901
1902    Detect a cross-iteration def-use cucle that represents a simple
1903    reduction computation. We look for the following pattern:
1904
1905    loop_header:
1906      a1 = phi < a0, a2 >
1907      a3 = ...
1908      a2 = operation (a3, a1)
1909   
1910    such that:
1911    1. operation is commutative and associative and it is safe to 
1912       change the order of the computation.
1913    2. no uses for a2 in the loop (a2 is used out of the loop)
1914    3. no uses of a1 in the loop besides the reduction operation.
1915
1916    Condition 1 is tested here.
1917    Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.  */
1918
1919 tree
1920 vect_is_simple_reduction (struct loop *loop, tree phi)
1921 {
1922   edge latch_e = loop_latch_edge (loop);
1923   tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
1924   tree def_stmt, def1, def2;
1925   enum tree_code code;
1926   int op_type;
1927   tree operation, op1, op2;
1928   tree type;
1929   int nloop_uses;
1930   tree name;
1931   imm_use_iterator imm_iter;
1932   use_operand_p use_p;
1933
1934   name = PHI_RESULT (phi);
1935   nloop_uses = 0;
1936   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1937     {
1938       tree use_stmt = USE_STMT (use_p);
1939       if (flow_bb_inside_loop_p (loop, bb_for_stmt (use_stmt))
1940           && vinfo_for_stmt (use_stmt)
1941           && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
1942         nloop_uses++;
1943       if (nloop_uses > 1)
1944         {
1945           if (vect_print_dump_info (REPORT_DETAILS))
1946             fprintf (vect_dump, "reduction used in loop.");
1947           return NULL_TREE;
1948         }
1949     }
1950
1951   if (TREE_CODE (loop_arg) != SSA_NAME)
1952     {
1953       if (vect_print_dump_info (REPORT_DETAILS))
1954         {
1955           fprintf (vect_dump, "reduction: not ssa_name: ");
1956           print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
1957         }
1958       return NULL_TREE;
1959     }
1960
1961   def_stmt = SSA_NAME_DEF_STMT (loop_arg);
1962   if (!def_stmt)
1963     {
1964       if (vect_print_dump_info (REPORT_DETAILS))
1965         fprintf (vect_dump, "reduction: no def_stmt.");
1966       return NULL_TREE;
1967     }
1968
1969   if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
1970     {
1971       if (vect_print_dump_info (REPORT_DETAILS))
1972         print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
1973       return NULL_TREE;
1974     }
1975
1976   name = GIMPLE_STMT_OPERAND (def_stmt, 0);
1977   nloop_uses = 0;
1978   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
1979     {
1980       tree use_stmt = USE_STMT (use_p);
1981       if (flow_bb_inside_loop_p (loop, bb_for_stmt (use_stmt))
1982           && vinfo_for_stmt (use_stmt)
1983           && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
1984         nloop_uses++;
1985       if (nloop_uses > 1)
1986         {
1987           if (vect_print_dump_info (REPORT_DETAILS))
1988             fprintf (vect_dump, "reduction used in loop.");
1989           return NULL_TREE;
1990         }
1991     }
1992
1993   operation = GIMPLE_STMT_OPERAND (def_stmt, 1);
1994   code = TREE_CODE (operation);
1995   if (!commutative_tree_code (code) || !associative_tree_code (code))
1996     {
1997       if (vect_print_dump_info (REPORT_DETAILS))
1998         {
1999           fprintf (vect_dump, "reduction: not commutative/associative: ");
2000           print_generic_expr (vect_dump, operation, TDF_SLIM);
2001         }
2002       return NULL_TREE;
2003     }
2004
2005   op_type = TREE_OPERAND_LENGTH (operation);
2006   if (op_type != binary_op)
2007     {
2008       if (vect_print_dump_info (REPORT_DETAILS))
2009         {
2010           fprintf (vect_dump, "reduction: not binary operation: ");
2011           print_generic_expr (vect_dump, operation, TDF_SLIM);
2012         }
2013       return NULL_TREE;
2014     }
2015
2016   op1 = TREE_OPERAND (operation, 0);
2017   op2 = TREE_OPERAND (operation, 1);
2018   if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
2019     {
2020       if (vect_print_dump_info (REPORT_DETAILS))
2021         {
2022           fprintf (vect_dump, "reduction: uses not ssa_names: ");
2023           print_generic_expr (vect_dump, operation, TDF_SLIM);
2024         }
2025       return NULL_TREE;
2026     }
2027
2028   /* Check that it's ok to change the order of the computation.  */
2029   type = TREE_TYPE (operation);
2030   if (TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op1))
2031       || TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op2)))
2032     {
2033       if (vect_print_dump_info (REPORT_DETAILS))
2034         {
2035           fprintf (vect_dump, "reduction: multiple types: operation type: ");
2036           print_generic_expr (vect_dump, type, TDF_SLIM);
2037           fprintf (vect_dump, ", operands types: ");
2038           print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
2039           fprintf (vect_dump, ",");
2040           print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
2041         }
2042       return NULL_TREE;
2043     }
2044
2045   /* CHECKME: check for !flag_finite_math_only too?  */
2046   if (SCALAR_FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
2047     {
2048       /* Changing the order of operations changes the semantics.  */
2049       if (vect_print_dump_info (REPORT_DETAILS))
2050         {
2051           fprintf (vect_dump, "reduction: unsafe fp math optimization: ");
2052           print_generic_expr (vect_dump, operation, TDF_SLIM);
2053         }
2054       return NULL_TREE;
2055     }
2056   else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type))
2057     {
2058       /* Changing the order of operations changes the semantics.  */
2059       if (vect_print_dump_info (REPORT_DETAILS))
2060         {
2061           fprintf (vect_dump, "reduction: unsafe int math optimization: ");
2062           print_generic_expr (vect_dump, operation, TDF_SLIM);
2063         }
2064       return NULL_TREE;
2065     }
2066
2067   /* reduction is safe. we're dealing with one of the following:
2068      1) integer arithmetic and no trapv
2069      2) floating point arithmetic, and special flags permit this optimization.
2070    */
2071   def1 = SSA_NAME_DEF_STMT (op1);
2072   def2 = SSA_NAME_DEF_STMT (op2);
2073   if (!def1 || !def2 || IS_EMPTY_STMT (def1) || IS_EMPTY_STMT (def2))
2074     {
2075       if (vect_print_dump_info (REPORT_DETAILS))
2076         {
2077           fprintf (vect_dump, "reduction: no defs for operands: ");
2078           print_generic_expr (vect_dump, operation, TDF_SLIM);
2079         }
2080       return NULL_TREE;
2081     }
2082
2083
2084   /* Check that one def is the reduction def, defined by PHI,
2085      the other def is either defined in the loop by a GIMPLE_MODIFY_STMT,
2086      or it's an induction (defined by some phi node).  */
2087
2088   if (def2 == phi
2089       && flow_bb_inside_loop_p (loop, bb_for_stmt (def1))
2090       && (TREE_CODE (def1) == GIMPLE_MODIFY_STMT 
2091           || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1)) == vect_induction_def))
2092     {
2093       if (vect_print_dump_info (REPORT_DETAILS))
2094         {
2095           fprintf (vect_dump, "detected reduction:");
2096           print_generic_expr (vect_dump, operation, TDF_SLIM);
2097         }
2098       return def_stmt;
2099     }
2100   else if (def1 == phi
2101            && flow_bb_inside_loop_p (loop, bb_for_stmt (def2))
2102            && (TREE_CODE (def2) == GIMPLE_MODIFY_STMT 
2103                || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2)) == vect_induction_def))
2104     {
2105       /* Swap operands (just for simplicity - so that the rest of the code
2106          can assume that the reduction variable is always the last (second)
2107          argument).  */
2108       if (vect_print_dump_info (REPORT_DETAILS))
2109         {
2110           fprintf (vect_dump, "detected reduction: need to swap operands:");
2111           print_generic_expr (vect_dump, operation, TDF_SLIM);
2112         }
2113       swap_tree_operands (def_stmt, &TREE_OPERAND (operation, 0), 
2114                                     &TREE_OPERAND (operation, 1));
2115       return def_stmt;
2116     }
2117   else
2118     {
2119       if (vect_print_dump_info (REPORT_DETAILS))
2120         {
2121           fprintf (vect_dump, "reduction: unknown pattern.");
2122           print_generic_expr (vect_dump, operation, TDF_SLIM);
2123         }
2124       return NULL_TREE;
2125     }
2126 }
2127
2128
2129 /* Function vect_is_simple_iv_evolution.
2130
2131    FORNOW: A simple evolution of an induction variables in the loop is
2132    considered a polynomial evolution with constant step.  */
2133
2134 bool
2135 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init, 
2136                              tree * step)
2137 {
2138   tree init_expr;
2139   tree step_expr;
2140   tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
2141
2142   /* When there is no evolution in this loop, the evolution function
2143      is not "simple".  */  
2144   if (evolution_part == NULL_TREE)
2145     return false;
2146   
2147   /* When the evolution is a polynomial of degree >= 2
2148      the evolution function is not "simple".  */
2149   if (tree_is_chrec (evolution_part))
2150     return false;
2151   
2152   step_expr = evolution_part;
2153   init_expr = unshare_expr (initial_condition_in_loop_num (access_fn, loop_nb));
2154
2155   if (vect_print_dump_info (REPORT_DETAILS))
2156     {
2157       fprintf (vect_dump, "step: ");
2158       print_generic_expr (vect_dump, step_expr, TDF_SLIM);
2159       fprintf (vect_dump, ",  init: ");
2160       print_generic_expr (vect_dump, init_expr, TDF_SLIM);
2161     }
2162
2163   *init = init_expr;
2164   *step = step_expr;
2165
2166   if (TREE_CODE (step_expr) != INTEGER_CST)
2167     { 
2168       if (vect_print_dump_info (REPORT_DETAILS))
2169         fprintf (vect_dump, "step unknown.");
2170       return false;
2171     }
2172
2173   return true;
2174 }
2175
2176
2177 /* Function vectorize_loops.
2178    
2179    Entry Point to loop vectorization phase.  */
2180
2181 unsigned
2182 vectorize_loops (void)
2183 {
2184   unsigned int i;
2185   unsigned int num_vectorized_loops = 0;
2186   unsigned int vect_loops_num;
2187   loop_iterator li;
2188   struct loop *loop;
2189
2190   vect_loops_num = number_of_loops ();
2191
2192   /* Bail out if there are no loops.  */
2193   if (vect_loops_num <= 1)
2194     return 0;
2195
2196   /* Fix the verbosity level if not defined explicitly by the user.  */
2197   vect_set_dump_settings ();
2198
2199   /* Allocate the bitmap that records which virtual variables that 
2200      need to be renamed.  */
2201   vect_memsyms_to_rename = BITMAP_ALLOC (NULL);
2202
2203   /*  ----------- Analyze loops. -----------  */
2204
2205   /* If some loop was duplicated, it gets bigger number 
2206      than all previously defined loops. This fact allows us to run 
2207      only over initial loops skipping newly generated ones.  */
2208   FOR_EACH_LOOP (li, loop, 0)
2209     {
2210       loop_vec_info loop_vinfo;
2211
2212       vect_loop_location = find_loop_location (loop);
2213       loop_vinfo = vect_analyze_loop (loop);
2214       loop->aux = loop_vinfo;
2215
2216       if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
2217         continue;
2218
2219       vect_transform_loop (loop_vinfo);
2220       num_vectorized_loops++;
2221     }
2222   vect_loop_location = UNKNOWN_LOC;
2223
2224   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)
2225       || (vect_print_dump_info (REPORT_VECTORIZED_LOOPS)
2226           && num_vectorized_loops > 0))
2227     fprintf (vect_dump, "vectorized %u loops in function.\n",
2228              num_vectorized_loops);
2229
2230   /*  ----------- Finalize. -----------  */
2231
2232   BITMAP_FREE (vect_memsyms_to_rename);
2233
2234   for (i = 1; i < vect_loops_num; i++)
2235     {
2236       loop_vec_info loop_vinfo;
2237
2238       loop = get_loop (i);
2239       if (!loop)
2240         continue;
2241       loop_vinfo = loop->aux;
2242       destroy_loop_vec_info (loop_vinfo);
2243       loop->aux = NULL;
2244     }
2245
2246   return num_vectorized_loops > 0 ? TODO_cleanup_cfg : 0;
2247 }
2248
2249 /* Increase alignment of global arrays to improve vectorization potential.
2250    TODO:
2251    - Consider also structs that have an array field.
2252    - Use ipa analysis to prune arrays that can't be vectorized?
2253      This should involve global alignment analysis and in the future also
2254      array padding.  */
2255
2256 static unsigned int
2257 increase_alignment (void)
2258 {
2259   struct varpool_node *vnode;
2260
2261   /* Increase the alignment of all global arrays for vectorization.  */
2262   for (vnode = varpool_nodes_queue;
2263        vnode;
2264        vnode = vnode->next_needed)
2265     {
2266       tree vectype, decl = vnode->decl;
2267       unsigned int alignment;
2268
2269       if (TREE_CODE (TREE_TYPE (decl)) != ARRAY_TYPE)
2270         continue;
2271       vectype = get_vectype_for_scalar_type (TREE_TYPE (TREE_TYPE (decl)));
2272       if (!vectype)
2273         continue;
2274       alignment = TYPE_ALIGN (vectype);
2275       if (DECL_ALIGN (decl) >= alignment)
2276         continue;
2277
2278       if (vect_can_force_dr_alignment_p (decl, alignment))
2279         { 
2280           DECL_ALIGN (decl) = TYPE_ALIGN (vectype);
2281           DECL_USER_ALIGN (decl) = 1;
2282           if (dump_file)
2283             { 
2284               fprintf (dump_file, "Increasing alignment of decl: ");
2285               print_generic_expr (dump_file, decl, TDF_SLIM);
2286             }
2287         }
2288     }
2289   return 0;
2290 }
2291
2292 static bool
2293 gate_increase_alignment (void)
2294 {
2295   return flag_section_anchors && flag_tree_vectorize;
2296 }
2297
2298 struct tree_opt_pass pass_ipa_increase_alignment = 
2299 {
2300   "increase_alignment",                 /* name */
2301   gate_increase_alignment,              /* gate */
2302   increase_alignment,                   /* execute */
2303   NULL,                                 /* sub */
2304   NULL,                                 /* next */
2305   0,                                    /* static_pass_number */
2306   0,                                    /* tv_id */
2307   0,                                    /* properties_required */
2308   0,                                    /* properties_provided */
2309   0,                                    /* properties_destroyed */
2310   0,                                    /* todo_flags_start */
2311   0,                                    /* todo_flags_finish */
2312   0                                     /* letter */
2313 };