2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 This file is part of GCC.
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
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
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
22 /* Loop Vectorization Pass.
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).
29 For example, the vectorizer transforms the following simple loop:
31 short a[N]; short b[N]; short c[N]; int i;
37 as if it was manually vectorized by rewriting the source code into:
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;
44 for (i=0; i<N/8; i++){
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.
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.
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.
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.
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.
86 For example, say stmt S1 was vectorized into stmt VS1:
89 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
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 by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
95 resulting sequence would be:
98 S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
100 S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
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.
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.
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.
119 For additional information on this project see:
120 http://gcc.gnu.org/projects/tree-ssa/vectorization.html
125 #include "coretypes.h"
131 #include "basic-block.h"
132 #include "diagnostic.h"
133 #include "tree-flow.h"
134 #include "tree-dump.h"
137 #include "cfglayout.h"
141 #include "tree-chrec.h"
142 #include "tree-data-ref.h"
143 #include "tree-scalar-evolution.h"
145 #include "tree-vectorizer.h"
146 #include "tree-pass.h"
148 /*************************************************************************
149 Simple Loop Peeling Utilities
150 *************************************************************************/
151 static struct loop
*slpeel_tree_duplicate_loop_to_edge_cfg
152 (struct loop
*, struct loops
*, edge
);
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
);
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
*);
165 /*************************************************************************
166 General Vectorization Utilities
167 *************************************************************************/
168 static void vect_set_dump_settings (void);
170 /* vect_dump will be set to stderr or dump_file if exist. */
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
;
177 /* Number of loops, at the beginning of vectorization. */
178 unsigned int vect_loops_num
;
181 static LOC vect_loop_location
;
183 /*************************************************************************
184 Simple Loop Peeling Utilities
186 Utilities to support loop peeling for vectorization purposes.
187 *************************************************************************/
190 /* Renames the use *OP_P. */
193 rename_use_op (use_operand_p op_p
)
197 if (TREE_CODE (USE_FROM_PTR (op_p
)) != SSA_NAME
)
200 new_name
= get_current_def (USE_FROM_PTR (op_p
));
202 /* Something defined outside of the loop. */
206 /* An ordinary ssa name defined in the loop. */
208 SET_USE (op_p
, new_name
);
212 /* Renames the variables in basic block BB. */
215 rename_variables_in_bb (basic_block bb
)
218 block_stmt_iterator bsi
;
224 struct loop
*loop
= bb
->loop_father
;
226 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
228 stmt
= bsi_stmt (bsi
);
229 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
,
230 (SSA_OP_ALL_USES
| SSA_OP_ALL_KILLS
))
231 rename_use_op (use_p
);
234 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
236 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
238 for (phi
= phi_nodes (e
->dest
); phi
; phi
= PHI_CHAIN (phi
))
239 rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, e
));
244 /* Renames variables in new generated LOOP. */
247 rename_variables_in_loop (struct loop
*loop
)
252 bbs
= get_loop_body (loop
);
254 for (i
= 0; i
< loop
->num_nodes
; i
++)
255 rename_variables_in_bb (bbs
[i
]);
261 /* Update the PHI nodes of NEW_LOOP.
263 NEW_LOOP is a duplicate of ORIG_LOOP.
264 AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
265 AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
266 executes before it. */
269 slpeel_update_phis_for_duplicate_loop (struct loop
*orig_loop
,
270 struct loop
*new_loop
, bool after
)
273 tree phi_new
, phi_orig
;
275 edge orig_loop_latch
= loop_latch_edge (orig_loop
);
276 edge orig_entry_e
= loop_preheader_edge (orig_loop
);
277 edge new_loop_exit_e
= new_loop
->single_exit
;
278 edge new_loop_entry_e
= loop_preheader_edge (new_loop
);
279 edge entry_arg_e
= (after
? orig_loop_latch
: orig_entry_e
);
282 step 1. For each loop-header-phi:
283 Add the first phi argument for the phi in NEW_LOOP
284 (the one associated with the entry of NEW_LOOP)
286 step 2. For each loop-header-phi:
287 Add the second phi argument for the phi in NEW_LOOP
288 (the one associated with the latch of NEW_LOOP)
290 step 3. Update the phis in the successor block of NEW_LOOP.
292 case 1: NEW_LOOP was placed before ORIG_LOOP:
293 The successor block of NEW_LOOP is the header of ORIG_LOOP.
294 Updating the phis in the successor block can therefore be done
295 along with the scanning of the loop header phis, because the
296 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
297 phi nodes, organized in the same order.
299 case 2: NEW_LOOP was placed after ORIG_LOOP:
300 The successor block of NEW_LOOP is the original exit block of
301 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
302 We postpone updating these phis to a later stage (when
303 loop guards are added).
307 /* Scan the phis in the headers of the old and new loops
308 (they are organized in exactly the same order). */
310 for (phi_new
= phi_nodes (new_loop
->header
),
311 phi_orig
= phi_nodes (orig_loop
->header
);
313 phi_new
= PHI_CHAIN (phi_new
), phi_orig
= PHI_CHAIN (phi_orig
))
316 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, entry_arg_e
);
317 add_phi_arg (phi_new
, def
, new_loop_entry_e
);
320 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, orig_loop_latch
);
321 if (TREE_CODE (def
) != SSA_NAME
)
324 new_ssa_name
= get_current_def (def
);
327 /* This only happens if there are no definitions
328 inside the loop. use the phi_result in this case. */
329 new_ssa_name
= PHI_RESULT (phi_new
);
332 /* An ordinary ssa name defined in the loop. */
333 add_phi_arg (phi_new
, new_ssa_name
, loop_latch_edge (new_loop
));
335 /* step 3 (case 1). */
338 gcc_assert (new_loop_exit_e
== orig_entry_e
);
339 SET_PHI_ARG_DEF (phi_orig
,
340 new_loop_exit_e
->dest_idx
,
347 /* Update PHI nodes for a guard of the LOOP.
350 - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
351 controls whether LOOP is to be executed. GUARD_EDGE is the edge that
352 originates from the guard-bb, skips LOOP and reaches the (unique) exit
353 bb of LOOP. This loop-exit-bb is an empty bb with one successor.
354 We denote this bb NEW_MERGE_BB because before the guard code was added
355 it had a single predecessor (the LOOP header), and now it became a merge
356 point of two paths - the path that ends with the LOOP exit-edge, and
357 the path that ends with GUARD_EDGE.
358 - NEW_EXIT_BB: New basic block that is added by this function between LOOP
359 and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
361 ===> The CFG before the guard-code was added:
364 if (exit_loop) goto update_bb
365 else goto LOOP_header_bb
368 ==> The CFG after the guard-code was added:
370 if (LOOP_guard_condition) goto new_merge_bb
371 else goto LOOP_header_bb
374 if (exit_loop_condition) goto new_merge_bb
375 else goto LOOP_header_bb
380 ==> The CFG after this function:
382 if (LOOP_guard_condition) goto new_merge_bb
383 else goto LOOP_header_bb
386 if (exit_loop_condition) goto new_exit_bb
387 else goto LOOP_header_bb
394 1. creates and updates the relevant phi nodes to account for the new
395 incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
396 1.1. Create phi nodes at NEW_MERGE_BB.
397 1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
398 UPDATE_BB). UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
399 2. preserves loop-closed-ssa-form by creating the required phi nodes
400 at the exit of LOOP (i.e, in NEW_EXIT_BB).
402 There are two flavors to this function:
404 slpeel_update_phi_nodes_for_guard1:
405 Here the guard controls whether we enter or skip LOOP, where LOOP is a
406 prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
407 for variables that have phis in the loop header.
409 slpeel_update_phi_nodes_for_guard2:
410 Here the guard controls whether we enter or skip LOOP, where LOOP is an
411 epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
412 for variables that have phis in the loop exit.
414 I.E., the overall structure is:
417 guard1 (goto loop1/merg1_bb)
420 guard2 (goto merge1_bb/merge2_bb)
427 slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
428 loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
429 that have phis in loop1->header).
431 slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
432 loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
433 that have phis in next_bb). It also adds some of these phis to
436 slpeel_update_phi_nodes_for_guard1 is always called before
437 slpeel_update_phi_nodes_for_guard2. They are both needed in order
438 to create correct data-flow and loop-closed-ssa-form.
440 Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
441 that change between iterations of a loop (and therefore have a phi-node
442 at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
443 phis for variables that are used out of the loop (and therefore have
444 loop-closed exit phis). Some variables may be both updated between
445 iterations and used after the loop. This is why in loop1_exit_bb we
446 may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
447 and exit phis (created by slpeel_update_phi_nodes_for_guard2).
449 - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
450 an original loop. i.e., we have:
453 guard_bb (goto LOOP/new_merge)
459 If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
463 guard_bb (goto LOOP/new_merge)
469 The SSA names defined in the original loop have a current
470 reaching definition that that records the corresponding new
471 ssa-name used in the new duplicated loop copy.
474 /* Function slpeel_update_phi_nodes_for_guard1
477 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
478 - DEFS - a bitmap of ssa names to mark new names for which we recorded
481 In the context of the overall structure, we have:
484 guard1 (goto loop1/merg1_bb)
487 guard2 (goto merge1_bb/merge2_bb)
494 For each name updated between loop iterations (i.e - for each name that has
495 an entry (loop-header) phi in LOOP) we create a new phi in:
496 1. merge1_bb (to account for the edge from guard1)
497 2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
501 slpeel_update_phi_nodes_for_guard1 (edge guard_edge
, struct loop
*loop
,
502 bool is_new_loop
, basic_block
*new_exit_bb
,
505 tree orig_phi
, new_phi
;
506 tree update_phi
, update_phi2
;
507 tree guard_arg
, loop_arg
;
508 basic_block new_merge_bb
= guard_edge
->dest
;
509 edge e
= EDGE_SUCC (new_merge_bb
, 0);
510 basic_block update_bb
= e
->dest
;
511 basic_block orig_bb
= loop
->header
;
513 tree current_new_name
;
515 /* Create new bb between loop and new_merge_bb. */
516 *new_exit_bb
= split_edge (loop
->single_exit
);
517 add_bb_to_loop (*new_exit_bb
, loop
->outer
);
519 new_exit_e
= EDGE_SUCC (*new_exit_bb
, 0);
521 for (orig_phi
= phi_nodes (orig_bb
), update_phi
= phi_nodes (update_bb
);
522 orig_phi
&& update_phi
;
523 orig_phi
= PHI_CHAIN (orig_phi
), update_phi
= PHI_CHAIN (update_phi
))
525 /** 1. Handle new-merge-point phis **/
527 /* 1.1. Generate new phi node in NEW_MERGE_BB: */
528 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
531 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
532 of LOOP. Set the two phi args in NEW_PHI for these edges: */
533 loop_arg
= PHI_ARG_DEF_FROM_EDGE (orig_phi
, EDGE_SUCC (loop
->latch
, 0));
534 guard_arg
= PHI_ARG_DEF_FROM_EDGE (orig_phi
, loop_preheader_edge (loop
));
536 add_phi_arg (new_phi
, loop_arg
, new_exit_e
);
537 add_phi_arg (new_phi
, guard_arg
, guard_edge
);
539 /* 1.3. Update phi in successor block. */
540 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi
, e
) == loop_arg
541 || PHI_ARG_DEF_FROM_EDGE (update_phi
, e
) == guard_arg
);
542 SET_PHI_ARG_DEF (update_phi
, e
->dest_idx
, PHI_RESULT (new_phi
));
543 update_phi2
= new_phi
;
546 /** 2. Handle loop-closed-ssa-form phis **/
548 /* 2.1. Generate new phi node in NEW_EXIT_BB: */
549 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
552 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
553 add_phi_arg (new_phi
, loop_arg
, loop
->single_exit
);
555 /* 2.3. Update phi in successor of NEW_EXIT_BB: */
556 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2
, new_exit_e
) == loop_arg
);
557 SET_PHI_ARG_DEF (update_phi2
, new_exit_e
->dest_idx
, PHI_RESULT (new_phi
));
559 /* 2.4. Record the newly created name with set_current_def.
560 We want to find a name such that
561 name = get_current_def (orig_loop_name)
562 and to set its current definition as follows:
563 set_current_def (name, new_phi_name)
565 If LOOP is a new loop then loop_arg is already the name we're
566 looking for. If LOOP is the original loop, then loop_arg is
567 the orig_loop_name and the relevant name is recorded in its
568 current reaching definition. */
570 current_new_name
= loop_arg
;
573 current_new_name
= get_current_def (loop_arg
);
574 /* current_def is not available only if the variable does not
575 change inside the loop, in which case we also don't care
576 about recording a current_def for it because we won't be
577 trying to create loop-exit-phis for it. */
578 if (!current_new_name
)
581 gcc_assert (get_current_def (current_new_name
) == NULL_TREE
);
583 set_current_def (current_new_name
, PHI_RESULT (new_phi
));
584 bitmap_set_bit (*defs
, SSA_NAME_VERSION (current_new_name
));
587 set_phi_nodes (new_merge_bb
, phi_reverse (phi_nodes (new_merge_bb
)));
591 /* Function slpeel_update_phi_nodes_for_guard2
594 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
596 In the context of the overall structure, we have:
599 guard1 (goto loop1/merg1_bb)
602 guard2 (goto merge1_bb/merge2_bb)
609 For each name used out side the loop (i.e - for each name that has an exit
610 phi in next_bb) we create a new phi in:
611 1. merge2_bb (to account for the edge from guard_bb)
612 2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
613 3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
614 if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
618 slpeel_update_phi_nodes_for_guard2 (edge guard_edge
, struct loop
*loop
,
619 bool is_new_loop
, basic_block
*new_exit_bb
)
621 tree orig_phi
, new_phi
;
622 tree update_phi
, update_phi2
;
623 tree guard_arg
, loop_arg
;
624 basic_block new_merge_bb
= guard_edge
->dest
;
625 edge e
= EDGE_SUCC (new_merge_bb
, 0);
626 basic_block update_bb
= e
->dest
;
628 tree orig_def
, orig_def_new_name
;
629 tree new_name
, new_name2
;
632 /* Create new bb between loop and new_merge_bb. */
633 *new_exit_bb
= split_edge (loop
->single_exit
);
634 add_bb_to_loop (*new_exit_bb
, loop
->outer
);
636 new_exit_e
= EDGE_SUCC (*new_exit_bb
, 0);
638 for (update_phi
= phi_nodes (update_bb
); update_phi
;
639 update_phi
= PHI_CHAIN (update_phi
))
641 orig_phi
= update_phi
;
642 orig_def
= PHI_ARG_DEF_FROM_EDGE (orig_phi
, e
);
643 orig_def_new_name
= get_current_def (orig_def
);
646 /** 1. Handle new-merge-point phis **/
648 /* 1.1. Generate new phi node in NEW_MERGE_BB: */
649 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
652 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
653 of LOOP. Set the two PHI args in NEW_PHI for these edges: */
655 new_name2
= NULL_TREE
;
656 if (orig_def_new_name
)
658 new_name
= orig_def_new_name
;
659 /* Some variables have both loop-entry-phis and loop-exit-phis.
660 Such variables were given yet newer names by phis placed in
661 guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
662 new_name2 = get_current_def (get_current_def (orig_name)). */
663 new_name2
= get_current_def (new_name
);
668 guard_arg
= orig_def
;
673 guard_arg
= new_name
;
677 guard_arg
= new_name2
;
679 add_phi_arg (new_phi
, loop_arg
, new_exit_e
);
680 add_phi_arg (new_phi
, guard_arg
, guard_edge
);
682 /* 1.3. Update phi in successor block. */
683 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi
, e
) == orig_def
);
684 SET_PHI_ARG_DEF (update_phi
, e
->dest_idx
, PHI_RESULT (new_phi
));
685 update_phi2
= new_phi
;
688 /** 2. Handle loop-closed-ssa-form phis **/
690 /* 2.1. Generate new phi node in NEW_EXIT_BB: */
691 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
694 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
695 add_phi_arg (new_phi
, loop_arg
, loop
->single_exit
);
697 /* 2.3. Update phi in successor of NEW_EXIT_BB: */
698 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2
, new_exit_e
) == loop_arg
);
699 SET_PHI_ARG_DEF (update_phi2
, new_exit_e
->dest_idx
, PHI_RESULT (new_phi
));
702 /** 3. Handle loop-closed-ssa-form phis for first loop **/
704 /* 3.1. Find the relevant names that need an exit-phi in
705 GUARD_BB, i.e. names for which
706 slpeel_update_phi_nodes_for_guard1 had not already created a
707 phi node. This is the case for names that are used outside
708 the loop (and therefore need an exit phi) but are not updated
709 across loop iterations (and therefore don't have a
712 slpeel_update_phi_nodes_for_guard1 is responsible for
713 creating loop-exit phis in GUARD_BB for names that have a
714 loop-header-phi. When such a phi is created we also record
715 the new name in its current definition. If this new name
716 exists, then guard_arg was set to this new name (see 1.2
717 above). Therefore, if guard_arg is not this new name, this
718 is an indication that an exit-phi in GUARD_BB was not yet
719 created, so we take care of it here. */
720 if (guard_arg
== new_name2
)
724 /* 3.2. Generate new phi node in GUARD_BB: */
725 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
728 /* 3.3. GUARD_BB has one incoming edge: */
729 gcc_assert (EDGE_COUNT (guard_edge
->src
->preds
) == 1);
730 add_phi_arg (new_phi
, arg
, EDGE_PRED (guard_edge
->src
, 0));
732 /* 3.4. Update phi in successor of GUARD_BB: */
733 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2
, guard_edge
)
735 SET_PHI_ARG_DEF (update_phi2
, guard_edge
->dest_idx
, PHI_RESULT (new_phi
));
738 set_phi_nodes (new_merge_bb
, phi_reverse (phi_nodes (new_merge_bb
)));
742 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
743 that starts at zero, increases by one and its limit is NITERS.
745 Assumption: the exit-condition of LOOP is the last stmt in the loop. */
748 slpeel_make_loop_iterate_ntimes (struct loop
*loop
, tree niters
)
750 tree indx_before_incr
, indx_after_incr
, cond_stmt
, cond
;
752 edge exit_edge
= loop
->single_exit
;
753 block_stmt_iterator loop_cond_bsi
;
754 block_stmt_iterator incr_bsi
;
756 tree begin_label
= tree_block_label (loop
->latch
);
757 tree exit_label
= tree_block_label (loop
->single_exit
->dest
);
758 tree init
= build_int_cst (TREE_TYPE (niters
), 0);
759 tree step
= build_int_cst (TREE_TYPE (niters
), 1);
764 orig_cond
= get_loop_exit_condition (loop
);
765 gcc_assert (orig_cond
);
766 loop_cond_bsi
= bsi_for_stmt (orig_cond
);
768 standard_iv_increment_position (loop
, &incr_bsi
, &insert_after
);
769 create_iv (init
, step
, NULL_TREE
, loop
,
770 &incr_bsi
, insert_after
, &indx_before_incr
, &indx_after_incr
);
772 if (exit_edge
->flags
& EDGE_TRUE_VALUE
) /* 'then' edge exits the loop. */
774 cond
= build2 (GE_EXPR
, boolean_type_node
, indx_after_incr
, niters
);
775 then_label
= build1 (GOTO_EXPR
, void_type_node
, exit_label
);
776 else_label
= build1 (GOTO_EXPR
, void_type_node
, begin_label
);
778 else /* 'then' edge loops back. */
780 cond
= build2 (LT_EXPR
, boolean_type_node
, indx_after_incr
, niters
);
781 then_label
= build1 (GOTO_EXPR
, void_type_node
, begin_label
);
782 else_label
= build1 (GOTO_EXPR
, void_type_node
, exit_label
);
785 cond_stmt
= build3 (COND_EXPR
, TREE_TYPE (orig_cond
), cond
,
786 then_label
, else_label
);
787 bsi_insert_before (&loop_cond_bsi
, cond_stmt
, BSI_SAME_STMT
);
789 /* Remove old loop exit test: */
790 bsi_remove (&loop_cond_bsi
);
792 loop_loc
= find_loop_location (loop
);
793 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
795 if (loop_loc
!= UNKNOWN_LOC
)
796 fprintf (dump_file
, "\nloop at %s:%d: ",
797 LOC_FILE (loop_loc
), LOC_LINE (loop_loc
));
798 print_generic_expr (dump_file
, cond_stmt
, TDF_SLIM
);
801 loop
->nb_iterations
= niters
;
805 /* Given LOOP this function generates a new copy of it and puts it
806 on E which is either the entry or exit of LOOP. */
809 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop
*loop
, struct loops
*loops
,
812 struct loop
*new_loop
;
813 basic_block
*new_bbs
, *bbs
;
816 basic_block exit_dest
;
819 at_exit
= (e
== loop
->single_exit
);
820 if (!at_exit
&& e
!= loop_preheader_edge (loop
))
823 bbs
= get_loop_body (loop
);
825 /* Check whether duplication is possible. */
826 if (!can_copy_bbs_p (bbs
, loop
->num_nodes
))
832 /* Generate new loop structure. */
833 new_loop
= duplicate_loop (loops
, loop
, loop
->outer
);
840 exit_dest
= loop
->single_exit
->dest
;
841 was_imm_dom
= (get_immediate_dominator (CDI_DOMINATORS
,
842 exit_dest
) == loop
->header
?
845 new_bbs
= xmalloc (sizeof (basic_block
) * loop
->num_nodes
);
847 copy_bbs (bbs
, loop
->num_nodes
, new_bbs
,
848 &loop
->single_exit
, 1, &new_loop
->single_exit
, NULL
);
850 /* Duplicating phi args at exit bbs as coming
851 also from exit of duplicated loop. */
852 for (phi
= phi_nodes (exit_dest
); phi
; phi
= PHI_CHAIN (phi
))
854 phi_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, loop
->single_exit
);
857 edge new_loop_exit_edge
;
859 if (EDGE_SUCC (new_loop
->header
, 0)->dest
== new_loop
->latch
)
860 new_loop_exit_edge
= EDGE_SUCC (new_loop
->header
, 1);
862 new_loop_exit_edge
= EDGE_SUCC (new_loop
->header
, 0);
864 add_phi_arg (phi
, phi_arg
, new_loop_exit_edge
);
868 if (at_exit
) /* Add the loop copy at exit. */
870 redirect_edge_and_branch_force (e
, new_loop
->header
);
871 set_immediate_dominator (CDI_DOMINATORS
, new_loop
->header
, e
->src
);
873 set_immediate_dominator (CDI_DOMINATORS
, exit_dest
, new_loop
->header
);
875 else /* Add the copy at entry. */
878 edge entry_e
= loop_preheader_edge (loop
);
879 basic_block preheader
= entry_e
->src
;
881 if (!flow_bb_inside_loop_p (new_loop
,
882 EDGE_SUCC (new_loop
->header
, 0)->dest
))
883 new_exit_e
= EDGE_SUCC (new_loop
->header
, 0);
885 new_exit_e
= EDGE_SUCC (new_loop
->header
, 1);
887 redirect_edge_and_branch_force (new_exit_e
, loop
->header
);
888 set_immediate_dominator (CDI_DOMINATORS
, loop
->header
,
891 /* We have to add phi args to the loop->header here as coming
892 from new_exit_e edge. */
893 for (phi
= phi_nodes (loop
->header
); phi
; phi
= PHI_CHAIN (phi
))
895 phi_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, entry_e
);
897 add_phi_arg (phi
, phi_arg
, new_exit_e
);
900 redirect_edge_and_branch_force (entry_e
, new_loop
->header
);
901 set_immediate_dominator (CDI_DOMINATORS
, new_loop
->header
, preheader
);
911 /* Given the condition statement COND, put it as the last statement
912 of GUARD_BB; EXIT_BB is the basic block to skip the loop;
913 Assumes that this is the single exit of the guarded loop.
914 Returns the skip edge. */
917 slpeel_add_loop_guard (basic_block guard_bb
, tree cond
, basic_block exit_bb
,
920 block_stmt_iterator bsi
;
922 tree cond_stmt
, then_label
, else_label
;
924 enter_e
= EDGE_SUCC (guard_bb
, 0);
925 enter_e
->flags
&= ~EDGE_FALLTHRU
;
926 enter_e
->flags
|= EDGE_FALSE_VALUE
;
927 bsi
= bsi_last (guard_bb
);
929 then_label
= build1 (GOTO_EXPR
, void_type_node
,
930 tree_block_label (exit_bb
));
931 else_label
= build1 (GOTO_EXPR
, void_type_node
,
932 tree_block_label (enter_e
->dest
));
933 cond_stmt
= build3 (COND_EXPR
, void_type_node
, cond
,
934 then_label
, else_label
);
935 bsi_insert_after (&bsi
, cond_stmt
, BSI_NEW_STMT
);
936 /* Add new edge to connect guard block to the merge/loop-exit block. */
937 new_e
= make_edge (guard_bb
, exit_bb
, EDGE_TRUE_VALUE
);
938 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, dom_bb
);
943 /* This function verifies that the following restrictions apply to LOOP:
945 (2) it consists of exactly 2 basic blocks - header, and an empty latch.
946 (3) it is single entry, single exit
947 (4) its exit condition is the last stmt in the header
948 (5) E is the entry/exit edge of LOOP.
952 slpeel_can_duplicate_loop_p (struct loop
*loop
, edge e
)
954 edge exit_e
= loop
->single_exit
;
955 edge entry_e
= loop_preheader_edge (loop
);
956 tree orig_cond
= get_loop_exit_condition (loop
);
957 block_stmt_iterator loop_exit_bsi
= bsi_last (exit_e
->src
);
959 if (need_ssa_update_p ())
963 /* All loops have an outer scope; the only case loop->outer is NULL is for
964 the function itself. */
966 || loop
->num_nodes
!= 2
967 || !empty_block_p (loop
->latch
)
968 || !loop
->single_exit
969 /* Verify that new loop exit condition can be trivially modified. */
970 || (!orig_cond
|| orig_cond
!= bsi_stmt (loop_exit_bsi
))
971 || (e
!= exit_e
&& e
!= entry_e
))
977 #ifdef ENABLE_CHECKING
979 slpeel_verify_cfg_after_peeling (struct loop
*first_loop
,
980 struct loop
*second_loop
)
982 basic_block loop1_exit_bb
= first_loop
->single_exit
->dest
;
983 basic_block loop2_entry_bb
= loop_preheader_edge (second_loop
)->src
;
984 basic_block loop1_entry_bb
= loop_preheader_edge (first_loop
)->src
;
986 /* A guard that controls whether the second_loop is to be executed or skipped
987 is placed in first_loop->exit. first_loopt->exit therefore has two
988 successors - one is the preheader of second_loop, and the other is a bb
991 gcc_assert (EDGE_COUNT (loop1_exit_bb
->succs
) == 2);
993 /* 1. Verify that one of the successors of first_loopt->exit is the preheader
996 /* The preheader of new_loop is expected to have two predecessors:
997 first_loop->exit and the block that precedes first_loop. */
999 gcc_assert (EDGE_COUNT (loop2_entry_bb
->preds
) == 2
1000 && ((EDGE_PRED (loop2_entry_bb
, 0)->src
== loop1_exit_bb
1001 && EDGE_PRED (loop2_entry_bb
, 1)->src
== loop1_entry_bb
)
1002 || (EDGE_PRED (loop2_entry_bb
, 1)->src
== loop1_exit_bb
1003 && EDGE_PRED (loop2_entry_bb
, 0)->src
== loop1_entry_bb
)));
1005 /* Verify that the other successor of first_loopt->exit is after the
1011 /* Function slpeel_tree_peel_loop_to_edge.
1013 Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
1014 that is placed on the entry (exit) edge E of LOOP. After this transformation
1015 we have two loops one after the other - first-loop iterates FIRST_NITERS
1016 times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
1019 - LOOP: the loop to be peeled.
1020 - E: the exit or entry edge of LOOP.
1021 If it is the entry edge, we peel the first iterations of LOOP. In this
1022 case first-loop is LOOP, and second-loop is the newly created loop.
1023 If it is the exit edge, we peel the last iterations of LOOP. In this
1024 case, first-loop is the newly created loop, and second-loop is LOOP.
1025 - NITERS: the number of iterations that LOOP iterates.
1026 - FIRST_NITERS: the number of iterations that the first-loop should iterate.
1027 - UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible
1028 for updating the loop bound of the first-loop to FIRST_NITERS. If it
1029 is false, the caller of this function may want to take care of this
1030 (this can be useful if we don't want new stmts added to first-loop).
1033 The function returns a pointer to the new loop-copy, or NULL if it failed
1034 to perform the transformation.
1036 The function generates two if-then-else guards: one before the first loop,
1037 and the other before the second loop:
1039 if (FIRST_NITERS == 0) then skip the first loop,
1040 and go directly to the second loop.
1041 The second guard is:
1042 if (FIRST_NITERS == NITERS) then skip the second loop.
1044 FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
1045 FORNOW the resulting code will not be in loop-closed-ssa form.
1049 slpeel_tree_peel_loop_to_edge (struct loop
*loop
, struct loops
*loops
,
1050 edge e
, tree first_niters
,
1051 tree niters
, bool update_first_loop_count
)
1053 struct loop
*new_loop
= NULL
, *first_loop
, *second_loop
;
1057 basic_block bb_before_second_loop
, bb_after_second_loop
;
1058 basic_block bb_before_first_loop
;
1059 basic_block bb_between_loops
;
1060 basic_block new_exit_bb
;
1061 edge exit_e
= loop
->single_exit
;
1064 if (!slpeel_can_duplicate_loop_p (loop
, e
))
1067 /* We have to initialize cfg_hooks. Then, when calling
1068 cfg_hooks->split_edge, the function tree_split_edge
1069 is actually called and, when calling cfg_hooks->duplicate_block,
1070 the function tree_duplicate_bb is called. */
1071 tree_register_cfg_hooks ();
1074 /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1075 Resulting CFG would be:
1088 if (!(new_loop
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, loops
, e
)))
1090 loop_loc
= find_loop_location (loop
);
1091 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1093 if (loop_loc
!= UNKNOWN_LOC
)
1094 fprintf (dump_file
, "\n%s:%d: note: ",
1095 LOC_FILE (loop_loc
), LOC_LINE (loop_loc
));
1096 fprintf (dump_file
, "tree_duplicate_loop_to_edge_cfg failed.\n");
1103 /* NEW_LOOP was placed after LOOP. */
1105 second_loop
= new_loop
;
1109 /* NEW_LOOP was placed before LOOP. */
1110 first_loop
= new_loop
;
1114 definitions
= ssa_names_to_replace ();
1115 slpeel_update_phis_for_duplicate_loop (loop
, new_loop
, e
== exit_e
);
1116 rename_variables_in_loop (new_loop
);
1119 /* 2. Add the guard that controls whether the first loop is executed.
1120 Resulting CFG would be:
1122 bb_before_first_loop:
1123 if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1130 bb_before_second_loop:
1139 bb_before_first_loop
= split_edge (loop_preheader_edge (first_loop
));
1140 add_bb_to_loop (bb_before_first_loop
, first_loop
->outer
);
1141 bb_before_second_loop
= split_edge (first_loop
->single_exit
);
1142 add_bb_to_loop (bb_before_second_loop
, first_loop
->outer
);
1145 fold_build2 (LE_EXPR
, boolean_type_node
, first_niters
, integer_zero_node
);
1146 skip_e
= slpeel_add_loop_guard (bb_before_first_loop
, pre_condition
,
1147 bb_before_second_loop
, bb_before_first_loop
);
1148 slpeel_update_phi_nodes_for_guard1 (skip_e
, first_loop
,
1149 first_loop
== new_loop
,
1150 &new_exit_bb
, &definitions
);
1153 /* 3. Add the guard that controls whether the second loop is executed.
1154 Resulting CFG would be:
1156 bb_before_first_loop:
1157 if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1165 if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1166 GOTO bb_before_second_loop
1168 bb_before_second_loop:
1174 bb_after_second_loop:
1179 bb_between_loops
= new_exit_bb
;
1180 bb_after_second_loop
= split_edge (second_loop
->single_exit
);
1181 add_bb_to_loop (bb_after_second_loop
, second_loop
->outer
);
1184 fold_build2 (EQ_EXPR
, boolean_type_node
, first_niters
, niters
);
1185 skip_e
= slpeel_add_loop_guard (bb_between_loops
, pre_condition
,
1186 bb_after_second_loop
, bb_before_first_loop
);
1187 slpeel_update_phi_nodes_for_guard2 (skip_e
, second_loop
,
1188 second_loop
== new_loop
, &new_exit_bb
);
1190 /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1192 if (update_first_loop_count
)
1193 slpeel_make_loop_iterate_ntimes (first_loop
, first_niters
);
1195 BITMAP_FREE (definitions
);
1196 delete_update_ssa ();
1201 /* Function vect_get_loop_location.
1203 Extract the location of the loop in the source code.
1204 If the loop is not well formed for vectorization, an estimated
1205 location is calculated.
1206 Return the loop location if succeed and NULL if not. */
1209 find_loop_location (struct loop
*loop
)
1211 tree node
= NULL_TREE
;
1213 block_stmt_iterator si
;
1218 node
= get_loop_exit_condition (loop
);
1220 if (node
&& EXPR_P (node
) && EXPR_HAS_LOCATION (node
)
1221 && EXPR_FILENAME (node
) && EXPR_LINENO (node
))
1222 return EXPR_LOC (node
);
1224 /* If we got here the loop is probably not "well formed",
1225 try to estimate the loop location */
1232 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
1234 node
= bsi_stmt (si
);
1235 if (node
&& EXPR_P (node
) && EXPR_HAS_LOCATION (node
))
1236 return EXPR_LOC (node
);
1243 /*************************************************************************
1244 Vectorization Debug Information.
1245 *************************************************************************/
1247 /* Function vect_set_verbosity_level.
1249 Called from toplev.c upon detection of the
1250 -ftree-vectorizer-verbose=N option. */
1253 vect_set_verbosity_level (const char *val
)
1258 if (vl
< MAX_VERBOSITY_LEVEL
)
1259 vect_verbosity_level
= vl
;
1261 vect_verbosity_level
= MAX_VERBOSITY_LEVEL
- 1;
1265 /* Function vect_set_dump_settings.
1267 Fix the verbosity level of the vectorizer if the
1268 requested level was not set explicitly using the flag
1269 -ftree-vectorizer-verbose=N.
1270 Decide where to print the debugging information (dump_file/stderr).
1271 If the user defined the verbosity level, but there is no dump file,
1272 print to stderr, otherwise print to the dump file. */
1275 vect_set_dump_settings (void)
1277 vect_dump
= dump_file
;
1279 /* Check if the verbosity level was defined by the user: */
1280 if (vect_verbosity_level
!= MAX_VERBOSITY_LEVEL
)
1282 /* If there is no dump file, print to stderr. */
1288 /* User didn't specify verbosity level: */
1289 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1290 vect_verbosity_level
= REPORT_DETAILS
;
1291 else if (dump_file
&& (dump_flags
& TDF_STATS
))
1292 vect_verbosity_level
= REPORT_UNVECTORIZED_LOOPS
;
1294 vect_verbosity_level
= REPORT_NONE
;
1296 gcc_assert (dump_file
|| vect_verbosity_level
== REPORT_NONE
);
1300 /* Function debug_loop_details.
1302 For vectorization debug dumps. */
1305 vect_print_dump_info (enum verbosity_levels vl
)
1307 if (vl
> vect_verbosity_level
)
1310 if (vect_loop_location
== UNKNOWN_LOC
)
1311 fprintf (vect_dump
, "\n%s:%d: note: ",
1312 DECL_SOURCE_FILE (current_function_decl
),
1313 DECL_SOURCE_LINE (current_function_decl
));
1315 fprintf (vect_dump
, "\n%s:%d: note: ",
1316 LOC_FILE (vect_loop_location
), LOC_LINE (vect_loop_location
));
1323 /*************************************************************************
1324 Vectorization Utilities.
1325 *************************************************************************/
1327 /* Function new_stmt_vec_info.
1329 Create and initialize a new stmt_vec_info struct for STMT. */
1332 new_stmt_vec_info (tree stmt
, loop_vec_info loop_vinfo
)
1335 res
= (stmt_vec_info
) xcalloc (1, sizeof (struct _stmt_vec_info
));
1337 STMT_VINFO_TYPE (res
) = undef_vec_info_type
;
1338 STMT_VINFO_STMT (res
) = stmt
;
1339 STMT_VINFO_LOOP_VINFO (res
) = loop_vinfo
;
1340 STMT_VINFO_RELEVANT_P (res
) = 0;
1341 STMT_VINFO_LIVE_P (res
) = 0;
1342 STMT_VINFO_VECTYPE (res
) = NULL
;
1343 STMT_VINFO_VEC_STMT (res
) = NULL
;
1344 STMT_VINFO_DATA_REF (res
) = NULL
;
1345 if (TREE_CODE (stmt
) == PHI_NODE
)
1346 STMT_VINFO_DEF_TYPE (res
) = vect_unknown_def_type
;
1348 STMT_VINFO_DEF_TYPE (res
) = vect_loop_def
;
1349 STMT_VINFO_MEMTAG (res
) = NULL
;
1350 STMT_VINFO_PTR_INFO (res
) = NULL
;
1351 STMT_VINFO_SUBVARS (res
) = NULL
;
1352 STMT_VINFO_VECT_DR_BASE_ADDRESS (res
) = NULL
;
1353 STMT_VINFO_VECT_INIT_OFFSET (res
) = NULL_TREE
;
1354 STMT_VINFO_VECT_STEP (res
) = NULL_TREE
;
1355 STMT_VINFO_VECT_BASE_ALIGNED_P (res
) = false;
1356 STMT_VINFO_VECT_MISALIGNMENT (res
) = NULL_TREE
;
1357 STMT_VINFO_SAME_ALIGN_REFS (res
) = VEC_alloc (dr_p
, heap
, 5);
1363 /* Function new_loop_vec_info.
1365 Create and initialize a new loop_vec_info struct for LOOP, as well as
1366 stmt_vec_info structs for all the stmts in LOOP. */
1369 new_loop_vec_info (struct loop
*loop
)
1373 block_stmt_iterator si
;
1376 res
= (loop_vec_info
) xcalloc (1, sizeof (struct _loop_vec_info
));
1378 bbs
= get_loop_body (loop
);
1380 /* Create stmt_info for all stmts in the loop. */
1381 for (i
= 0; i
< loop
->num_nodes
; i
++)
1383 basic_block bb
= bbs
[i
];
1386 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1388 tree_ann_t ann
= get_tree_ann (phi
);
1389 set_stmt_info (ann
, new_stmt_vec_info (phi
, res
));
1392 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
1394 tree stmt
= bsi_stmt (si
);
1397 ann
= stmt_ann (stmt
);
1398 set_stmt_info ((tree_ann_t
)ann
, new_stmt_vec_info (stmt
, res
));
1402 LOOP_VINFO_LOOP (res
) = loop
;
1403 LOOP_VINFO_BBS (res
) = bbs
;
1404 LOOP_VINFO_EXIT_COND (res
) = NULL
;
1405 LOOP_VINFO_NITERS (res
) = NULL
;
1406 LOOP_VINFO_VECTORIZABLE_P (res
) = 0;
1407 LOOP_PEELING_FOR_ALIGNMENT (res
) = 0;
1408 LOOP_VINFO_VECT_FACTOR (res
) = 0;
1409 VARRAY_GENERIC_PTR_INIT (LOOP_VINFO_DATAREF_WRITES (res
), 20,
1410 "loop_write_datarefs");
1411 VARRAY_GENERIC_PTR_INIT (LOOP_VINFO_DATAREF_READS (res
), 20,
1412 "loop_read_datarefs");
1413 LOOP_VINFO_UNALIGNED_DR (res
) = NULL
;
1419 /* Function destroy_loop_vec_info.
1421 Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
1422 stmts in the loop. */
1425 destroy_loop_vec_info (loop_vec_info loop_vinfo
)
1430 block_stmt_iterator si
;
1436 loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1438 bbs
= LOOP_VINFO_BBS (loop_vinfo
);
1439 nbbs
= loop
->num_nodes
;
1441 for (j
= 0; j
< nbbs
; j
++)
1443 basic_block bb
= bbs
[j
];
1445 stmt_vec_info stmt_info
;
1447 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
1449 tree_ann_t ann
= get_tree_ann (phi
);
1451 stmt_info
= vinfo_for_stmt (phi
);
1453 set_stmt_info (ann
, NULL
);
1456 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
1458 tree stmt
= bsi_stmt (si
);
1459 stmt_ann_t ann
= stmt_ann (stmt
);
1460 stmt_vec_info stmt_info
= vinfo_for_stmt (stmt
);
1464 VEC_free (dr_p
, heap
, STMT_VINFO_SAME_ALIGN_REFS (stmt_info
));
1466 set_stmt_info ((tree_ann_t
)ann
, NULL
);
1471 free (LOOP_VINFO_BBS (loop_vinfo
));
1472 varray_clear (LOOP_VINFO_DATAREF_WRITES (loop_vinfo
));
1473 varray_clear (LOOP_VINFO_DATAREF_READS (loop_vinfo
));
1479 /* Function vect_strip_conversions
1481 Strip conversions that don't narrow the mode. */
1484 vect_strip_conversion (tree expr
)
1486 tree to
, ti
, oprnd0
;
1488 while (TREE_CODE (expr
) == NOP_EXPR
|| TREE_CODE (expr
) == CONVERT_EXPR
)
1490 to
= TREE_TYPE (expr
);
1491 oprnd0
= TREE_OPERAND (expr
, 0);
1492 ti
= TREE_TYPE (oprnd0
);
1494 if (!INTEGRAL_TYPE_P (to
) || !INTEGRAL_TYPE_P (ti
))
1496 if (GET_MODE_SIZE (TYPE_MODE (to
)) < GET_MODE_SIZE (TYPE_MODE (ti
)))
1505 /* Function vect_force_dr_alignment_p.
1507 Returns whether the alignment of a DECL can be forced to be aligned
1508 on ALIGNMENT bit boundary. */
1511 vect_can_force_dr_alignment_p (tree decl
, unsigned int alignment
)
1513 if (TREE_CODE (decl
) != VAR_DECL
)
1516 if (DECL_EXTERNAL (decl
))
1519 if (TREE_ASM_WRITTEN (decl
))
1522 if (TREE_STATIC (decl
))
1523 return (alignment
<= MAX_OFILE_ALIGNMENT
);
1525 /* This is not 100% correct. The absolute correct stack alignment
1526 is STACK_BOUNDARY. We're supposed to hope, but not assume, that
1527 PREFERRED_STACK_BOUNDARY is honored by all translation units.
1528 However, until someone implements forced stack alignment, SSE
1529 isn't really usable without this. */
1530 return (alignment
<= PREFERRED_STACK_BOUNDARY
);
1534 /* Function get_vectype_for_scalar_type.
1536 Returns the vector type corresponding to SCALAR_TYPE as supported
1540 get_vectype_for_scalar_type (tree scalar_type
)
1542 enum machine_mode inner_mode
= TYPE_MODE (scalar_type
);
1543 int nbytes
= GET_MODE_SIZE (inner_mode
);
1547 if (nbytes
== 0 || nbytes
>= UNITS_PER_SIMD_WORD
)
1550 /* FORNOW: Only a single vector size per target (UNITS_PER_SIMD_WORD)
1552 nunits
= UNITS_PER_SIMD_WORD
/ nbytes
;
1554 vectype
= build_vector_type (scalar_type
, nunits
);
1555 if (vect_print_dump_info (REPORT_DETAILS
))
1557 fprintf (vect_dump
, "get vectype with %d units of type ", nunits
);
1558 print_generic_expr (vect_dump
, scalar_type
, TDF_SLIM
);
1564 if (vect_print_dump_info (REPORT_DETAILS
))
1566 fprintf (vect_dump
, "vectype: ");
1567 print_generic_expr (vect_dump
, vectype
, TDF_SLIM
);
1570 if (!VECTOR_MODE_P (TYPE_MODE (vectype
))
1571 && !INTEGRAL_MODE_P (TYPE_MODE (vectype
)))
1573 if (vect_print_dump_info (REPORT_DETAILS
))
1574 fprintf (vect_dump
, "mode not supported by target.");
1582 /* Function vect_supportable_dr_alignment
1584 Return whether the data reference DR is supported with respect to its
1587 enum dr_alignment_support
1588 vect_supportable_dr_alignment (struct data_reference
*dr
)
1590 tree vectype
= STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr
)));
1591 enum machine_mode mode
= (int) TYPE_MODE (vectype
);
1593 if (aligned_access_p (dr
))
1596 /* Possibly unaligned access. */
1598 if (DR_IS_READ (dr
))
1600 if (vec_realign_load_optab
->handlers
[mode
].insn_code
!= CODE_FOR_nothing
1601 && (!targetm
.vectorize
.builtin_mask_for_load
1602 || targetm
.vectorize
.builtin_mask_for_load ()))
1603 return dr_unaligned_software_pipeline
;
1605 if (movmisalign_optab
->handlers
[mode
].insn_code
!= CODE_FOR_nothing
)
1606 /* Can't software pipeline the loads, but can at least do them. */
1607 return dr_unaligned_supported
;
1611 return dr_unaligned_unsupported
;
1615 /* Function vect_is_simple_use.
1618 LOOP - the loop that is being vectorized.
1619 OPERAND - operand of a stmt in LOOP.
1620 DEF - the defining stmt in case OPERAND is an SSA_NAME.
1622 Returns whether a stmt with OPERAND can be vectorized.
1623 Supportable operands are constants, loop invariants, and operands that are
1624 defined by the current iteration of the loop. Unsupportable operands are
1625 those that are defined by a previous iteration of the loop (as is the case
1626 in reduction/induction computations). */
1629 vect_is_simple_use (tree operand
, loop_vec_info loop_vinfo
, tree
*def_stmt
,
1630 tree
*def
, enum vect_def_type
*dt
)
1633 stmt_vec_info stmt_vinfo
;
1634 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1636 *def_stmt
= NULL_TREE
;
1639 if (vect_print_dump_info (REPORT_DETAILS
))
1641 fprintf (vect_dump
, "vect_is_simple_use: operand ");
1642 print_generic_expr (vect_dump
, operand
, TDF_SLIM
);
1645 if (TREE_CODE (operand
) == INTEGER_CST
|| TREE_CODE (operand
) == REAL_CST
)
1647 *dt
= vect_constant_def
;
1651 if (TREE_CODE (operand
) != SSA_NAME
)
1653 if (vect_print_dump_info (REPORT_DETAILS
))
1654 fprintf (vect_dump
, "not ssa-name.");
1658 *def_stmt
= SSA_NAME_DEF_STMT (operand
);
1659 if (*def_stmt
== NULL_TREE
)
1661 if (vect_print_dump_info (REPORT_DETAILS
))
1662 fprintf (vect_dump
, "no def_stmt.");
1666 if (vect_print_dump_info (REPORT_DETAILS
))
1668 fprintf (vect_dump
, "def_stmt: ");
1669 print_generic_expr (vect_dump
, *def_stmt
, TDF_SLIM
);
1672 /* empty stmt is expected only in case of a function argument.
1673 (Otherwise - we expect a phi_node or a modify_expr). */
1674 if (IS_EMPTY_STMT (*def_stmt
))
1676 tree arg
= TREE_OPERAND (*def_stmt
, 0);
1677 if (TREE_CODE (arg
) == INTEGER_CST
|| TREE_CODE (arg
) == REAL_CST
)
1680 *dt
= vect_invariant_def
;
1684 if (vect_print_dump_info (REPORT_DETAILS
))
1685 fprintf (vect_dump
, "Unexpected empty stmt.");
1689 bb
= bb_for_stmt (*def_stmt
);
1690 if (!flow_bb_inside_loop_p (loop
, bb
))
1691 *dt
= vect_invariant_def
;
1694 stmt_vinfo
= vinfo_for_stmt (*def_stmt
);
1695 *dt
= STMT_VINFO_DEF_TYPE (stmt_vinfo
);
1698 if (*dt
== vect_unknown_def_type
)
1700 if (vect_print_dump_info (REPORT_DETAILS
))
1701 fprintf (vect_dump
, "Unsupported pattern.");
1705 /* stmts inside the loop that have been identified as performing
1706 a reduction operation cannot have uses in the loop. */
1707 if (*dt
== vect_reduction_def
&& TREE_CODE (*def_stmt
) != PHI_NODE
)
1709 if (vect_print_dump_info (REPORT_DETAILS
))
1710 fprintf (vect_dump
, "reduction used in loop.");
1714 if (vect_print_dump_info (REPORT_DETAILS
))
1715 fprintf (vect_dump
, "type of def: %d.",*dt
);
1717 switch (TREE_CODE (*def_stmt
))
1720 *def
= PHI_RESULT (*def_stmt
);
1721 gcc_assert (*dt
== vect_induction_def
|| *dt
== vect_reduction_def
1722 || *dt
== vect_invariant_def
);
1726 *def
= TREE_OPERAND (*def_stmt
, 0);
1727 gcc_assert (*dt
== vect_loop_def
|| *dt
== vect_invariant_def
);
1731 if (vect_print_dump_info (REPORT_DETAILS
))
1732 fprintf (vect_dump
, "unsupported defining stmt: ");
1736 if (*dt
== vect_induction_def
)
1738 if (vect_print_dump_info (REPORT_DETAILS
))
1739 fprintf (vect_dump
, "induction not supported.");
1747 /* Function reduction_code_for_scalar_code
1750 CODE - tree_code of a reduction operations.
1753 REDUC_CODE - the corresponding tree-code to be used to reduce the
1754 vector of partial results into a single scalar result (which
1755 will also reside in a vector).
1757 Return TRUE if a corresponding REDUC_CODE was found, FALSE otherwise. */
1760 reduction_code_for_scalar_code (enum tree_code code
,
1761 enum tree_code
*reduc_code
)
1766 *reduc_code
= REDUC_MAX_EXPR
;
1770 *reduc_code
= REDUC_MIN_EXPR
;
1774 *reduc_code
= REDUC_PLUS_EXPR
;
1783 /* Function vect_is_simple_reduction
1785 Detect a cross-iteration def-use cucle that represents a simple
1786 reduction computation. We look for the following pattern:
1791 a2 = operation (a3, a1)
1794 1. operation is commutative and associative and it is safe to
1795 change the the order of the computation.
1796 2. no uses for a2 in the loop (a2 is used out of the loop)
1797 3. no uses of a1 in the loop besides the reduction operation.
1799 Condition 1 is tested here.
1800 Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized. */
1803 vect_is_simple_reduction (struct loop
*loop ATTRIBUTE_UNUSED
,
1804 tree phi ATTRIBUTE_UNUSED
)
1806 edge latch_e
= loop_latch_edge (loop
);
1807 tree loop_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, latch_e
);
1808 tree def_stmt
, def1
, def2
;
1809 enum tree_code code
;
1811 tree operation
, op1
, op2
;
1814 if (TREE_CODE (loop_arg
) != SSA_NAME
)
1816 if (vect_print_dump_info (REPORT_DETAILS
))
1818 fprintf (vect_dump
, "reduction: not ssa_name: ");
1819 print_generic_expr (vect_dump
, loop_arg
, TDF_SLIM
);
1824 def_stmt
= SSA_NAME_DEF_STMT (loop_arg
);
1827 if (vect_print_dump_info (REPORT_DETAILS
))
1828 fprintf (vect_dump
, "reduction: no def_stmt.");
1832 if (TREE_CODE (def_stmt
) != MODIFY_EXPR
)
1834 if (vect_print_dump_info (REPORT_DETAILS
))
1836 print_generic_expr (vect_dump
, def_stmt
, TDF_SLIM
);
1841 operation
= TREE_OPERAND (def_stmt
, 1);
1842 code
= TREE_CODE (operation
);
1843 if (!commutative_tree_code (code
) || !associative_tree_code (code
))
1845 if (vect_print_dump_info (REPORT_DETAILS
))
1847 fprintf (vect_dump
, "reduction: not commutative/associative: ");
1848 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1853 op_type
= TREE_CODE_LENGTH (code
);
1854 if (op_type
!= binary_op
)
1856 if (vect_print_dump_info (REPORT_DETAILS
))
1858 fprintf (vect_dump
, "reduction: not binary operation: ");
1859 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1864 op1
= TREE_OPERAND (operation
, 0);
1865 op2
= TREE_OPERAND (operation
, 1);
1866 if (TREE_CODE (op1
) != SSA_NAME
|| TREE_CODE (op2
) != SSA_NAME
)
1868 if (vect_print_dump_info (REPORT_DETAILS
))
1870 fprintf (vect_dump
, "reduction: uses not ssa_names: ");
1871 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1876 /* Check that it's ok to change the order of the computation. */
1877 type
= TREE_TYPE (operation
);
1878 if (TYPE_MAIN_VARIANT (type
) != TYPE_MAIN_VARIANT (TREE_TYPE (op1
))
1879 || TYPE_MAIN_VARIANT (type
) != TYPE_MAIN_VARIANT (TREE_TYPE (op2
)))
1881 if (vect_print_dump_info (REPORT_DETAILS
))
1883 fprintf (vect_dump
, "reduction: multiple types: operation type: ");
1884 print_generic_expr (vect_dump
, type
, TDF_SLIM
);
1885 fprintf (vect_dump
, ", operands types: ");
1886 print_generic_expr (vect_dump
, TREE_TYPE (op1
), TDF_SLIM
);
1887 fprintf (vect_dump
, ",");
1888 print_generic_expr (vect_dump
, TREE_TYPE (op2
), TDF_SLIM
);
1893 /* CHECKME: check for !flag_finite_math_only too? */
1894 if (SCALAR_FLOAT_TYPE_P (type
) && !flag_unsafe_math_optimizations
)
1896 /* Changing the order of operations changes the sematics. */
1897 if (vect_print_dump_info (REPORT_DETAILS
))
1899 fprintf (vect_dump
, "reduction: unsafe fp math optimization: ");
1900 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1904 else if (INTEGRAL_TYPE_P (type
) && !TYPE_UNSIGNED (type
) && flag_trapv
)
1906 /* Changing the order of operations changes the sematics. */
1907 if (vect_print_dump_info (REPORT_DETAILS
))
1909 fprintf (vect_dump
, "reduction: unsafe int math optimization: ");
1910 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1915 /* reduction is safe. we're dealing with one of the following:
1916 1) integer arithmetic and no trapv
1917 2) floating point arithmetic, and special flags permit this optimization.
1919 def1
= SSA_NAME_DEF_STMT (op1
);
1920 def2
= SSA_NAME_DEF_STMT (op2
);
1923 if (vect_print_dump_info (REPORT_DETAILS
))
1925 fprintf (vect_dump
, "reduction: no defs for operands: ");
1926 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1931 if (TREE_CODE (def1
) == MODIFY_EXPR
1932 && flow_bb_inside_loop_p (loop
, bb_for_stmt (def1
))
1935 if (vect_print_dump_info (REPORT_DETAILS
))
1937 fprintf (vect_dump
, "detected reduction:");
1938 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1942 else if (TREE_CODE (def2
) == MODIFY_EXPR
1943 && flow_bb_inside_loop_p (loop
, bb_for_stmt (def2
))
1949 /* Swap operands (just for simplicity - so that the rest of the code
1950 can assume that the reduction variable is always the last (second)
1952 if (vect_print_dump_info (REPORT_DETAILS
))
1954 fprintf (vect_dump
, "detected reduction: need to swap operands:");
1955 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1959 FOR_EACH_SSA_USE_OPERAND (use
, def_stmt
, iter
, SSA_OP_USE
)
1961 tree tuse
= USE_FROM_PTR (use
);
1964 else if (tuse
== op2
)
1971 if (vect_print_dump_info (REPORT_DETAILS
))
1973 fprintf (vect_dump
, "reduction: unknown pattern.");
1974 print_generic_expr (vect_dump
, operation
, TDF_SLIM
);
1981 /* Function vect_is_simple_iv_evolution.
1983 FORNOW: A simple evolution of an induction variables in the loop is
1984 considered a polynomial evolution with constant step. */
1987 vect_is_simple_iv_evolution (unsigned loop_nb
, tree access_fn
, tree
* init
,
1993 tree evolution_part
= evolution_part_in_loop_num (access_fn
, loop_nb
);
1995 /* When there is no evolution in this loop, the evolution function
1997 if (evolution_part
== NULL_TREE
)
2000 /* When the evolution is a polynomial of degree >= 2
2001 the evolution function is not "simple". */
2002 if (tree_is_chrec (evolution_part
))
2005 step_expr
= evolution_part
;
2006 init_expr
= unshare_expr (initial_condition_in_loop_num (access_fn
,
2009 if (vect_print_dump_info (REPORT_DETAILS
))
2011 fprintf (vect_dump
, "step: ");
2012 print_generic_expr (vect_dump
, step_expr
, TDF_SLIM
);
2013 fprintf (vect_dump
, ", init: ");
2014 print_generic_expr (vect_dump
, init_expr
, TDF_SLIM
);
2020 if (TREE_CODE (step_expr
) != INTEGER_CST
)
2022 if (vect_print_dump_info (REPORT_DETAILS
))
2023 fprintf (vect_dump
, "step unknown.");
2031 /* Function vectorize_loops.
2033 Entry Point to loop vectorization phase. */
2036 vectorize_loops (struct loops
*loops
)
2039 unsigned int num_vectorized_loops
= 0;
2041 /* Fix the verbosity level if not defined explicitly by the user. */
2042 vect_set_dump_settings ();
2044 /* ----------- Analyze loops. ----------- */
2046 /* If some loop was duplicated, it gets bigger number
2047 than all previously defined loops. This fact allows us to run
2048 only over initial loops skipping newly generated ones. */
2049 vect_loops_num
= loops
->num
;
2050 for (i
= 1; i
< vect_loops_num
; i
++)
2052 loop_vec_info loop_vinfo
;
2053 struct loop
*loop
= loops
->parray
[i
];
2058 vect_loop_location
= find_loop_location (loop
);
2059 loop_vinfo
= vect_analyze_loop (loop
);
2060 loop
->aux
= loop_vinfo
;
2062 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
2065 vect_transform_loop (loop_vinfo
, loops
);
2066 num_vectorized_loops
++;
2069 if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS
))
2070 fprintf (vect_dump
, "vectorized %u loops in function.\n",
2071 num_vectorized_loops
);
2073 /* ----------- Finalize. ----------- */
2075 for (i
= 1; i
< vect_loops_num
; i
++)
2077 struct loop
*loop
= loops
->parray
[i
];
2078 loop_vec_info loop_vinfo
;
2082 loop_vinfo
= loop
->aux
;
2083 destroy_loop_vec_info (loop_vinfo
);