1 /* Vectorizer Specific Loop Manipulations
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software
4 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 and Ira Rosen <irar@il.ibm.com>
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
29 #include "basic-block.h"
30 #include "diagnostic.h"
31 #include "tree-flow.h"
32 #include "tree-dump.h"
34 #include "cfglayout.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-vectorizer.h"
39 #include "langhooks.h"
41 /*************************************************************************
42 Simple Loop Peeling Utilities
44 Utilities to support loop peeling for vectorization purposes.
45 *************************************************************************/
48 /* Renames the use *OP_P. */
51 rename_use_op (use_operand_p op_p)
55 if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
58 new_name = get_current_def (USE_FROM_PTR (op_p));
60 /* Something defined outside of the loop. */
64 /* An ordinary ssa name defined in the loop. */
66 SET_USE (op_p, new_name);
70 /* Renames the variables in basic block BB. */
73 rename_variables_in_bb (basic_block bb)
75 gimple_stmt_iterator gsi;
81 struct loop *loop = bb->loop_father;
83 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
85 stmt = gsi_stmt (gsi);
86 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
87 rename_use_op (use_p);
90 FOR_EACH_EDGE (e, ei, bb->succs)
92 if (!flow_bb_inside_loop_p (loop, e->dest))
94 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
95 rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi), e));
100 /* Renames variables in new generated LOOP. */
103 rename_variables_in_loop (struct loop *loop)
108 bbs = get_loop_body (loop);
110 for (i = 0; i < loop->num_nodes; i++)
111 rename_variables_in_bb (bbs[i]);
117 /* Update the PHI nodes of NEW_LOOP.
119 NEW_LOOP is a duplicate of ORIG_LOOP.
120 AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
121 AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
122 executes before it. */
125 slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
126 struct loop *new_loop, bool after)
129 gimple phi_new, phi_orig;
131 edge orig_loop_latch = loop_latch_edge (orig_loop);
132 edge orig_entry_e = loop_preheader_edge (orig_loop);
133 edge new_loop_exit_e = single_exit (new_loop);
134 edge new_loop_entry_e = loop_preheader_edge (new_loop);
135 edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
136 gimple_stmt_iterator gsi_new, gsi_orig;
139 step 1. For each loop-header-phi:
140 Add the first phi argument for the phi in NEW_LOOP
141 (the one associated with the entry of NEW_LOOP)
143 step 2. For each loop-header-phi:
144 Add the second phi argument for the phi in NEW_LOOP
145 (the one associated with the latch of NEW_LOOP)
147 step 3. Update the phis in the successor block of NEW_LOOP.
149 case 1: NEW_LOOP was placed before ORIG_LOOP:
150 The successor block of NEW_LOOP is the header of ORIG_LOOP.
151 Updating the phis in the successor block can therefore be done
152 along with the scanning of the loop header phis, because the
153 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
154 phi nodes, organized in the same order.
156 case 2: NEW_LOOP was placed after ORIG_LOOP:
157 The successor block of NEW_LOOP is the original exit block of
158 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
159 We postpone updating these phis to a later stage (when
160 loop guards are added).
164 /* Scan the phis in the headers of the old and new loops
165 (they are organized in exactly the same order). */
167 for (gsi_new = gsi_start_phis (new_loop->header),
168 gsi_orig = gsi_start_phis (orig_loop->header);
169 !gsi_end_p (gsi_new) && !gsi_end_p (gsi_orig);
170 gsi_next (&gsi_new), gsi_next (&gsi_orig))
172 phi_new = gsi_stmt (gsi_new);
173 phi_orig = gsi_stmt (gsi_orig);
176 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
177 add_phi_arg (phi_new, def, new_loop_entry_e);
180 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
181 if (TREE_CODE (def) != SSA_NAME)
184 new_ssa_name = get_current_def (def);
187 /* This only happens if there are no definitions
188 inside the loop. use the phi_result in this case. */
189 new_ssa_name = PHI_RESULT (phi_new);
192 /* An ordinary ssa name defined in the loop. */
193 add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
195 /* step 3 (case 1). */
198 gcc_assert (new_loop_exit_e == orig_entry_e);
199 SET_PHI_ARG_DEF (phi_orig,
200 new_loop_exit_e->dest_idx,
207 /* Update PHI nodes for a guard of the LOOP.
210 - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
211 controls whether LOOP is to be executed. GUARD_EDGE is the edge that
212 originates from the guard-bb, skips LOOP and reaches the (unique) exit
213 bb of LOOP. This loop-exit-bb is an empty bb with one successor.
214 We denote this bb NEW_MERGE_BB because before the guard code was added
215 it had a single predecessor (the LOOP header), and now it became a merge
216 point of two paths - the path that ends with the LOOP exit-edge, and
217 the path that ends with GUARD_EDGE.
218 - NEW_EXIT_BB: New basic block that is added by this function between LOOP
219 and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
221 ===> The CFG before the guard-code was added:
224 if (exit_loop) goto update_bb
225 else goto LOOP_header_bb
228 ==> The CFG after the guard-code was added:
230 if (LOOP_guard_condition) goto new_merge_bb
231 else goto LOOP_header_bb
234 if (exit_loop_condition) goto new_merge_bb
235 else goto LOOP_header_bb
240 ==> The CFG after this function:
242 if (LOOP_guard_condition) goto new_merge_bb
243 else goto LOOP_header_bb
246 if (exit_loop_condition) goto new_exit_bb
247 else goto LOOP_header_bb
254 1. creates and updates the relevant phi nodes to account for the new
255 incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
256 1.1. Create phi nodes at NEW_MERGE_BB.
257 1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
258 UPDATE_BB). UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
259 2. preserves loop-closed-ssa-form by creating the required phi nodes
260 at the exit of LOOP (i.e, in NEW_EXIT_BB).
262 There are two flavors to this function:
264 slpeel_update_phi_nodes_for_guard1:
265 Here the guard controls whether we enter or skip LOOP, where LOOP is a
266 prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
267 for variables that have phis in the loop header.
269 slpeel_update_phi_nodes_for_guard2:
270 Here the guard controls whether we enter or skip LOOP, where LOOP is an
271 epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
272 for variables that have phis in the loop exit.
274 I.E., the overall structure is:
277 guard1 (goto loop1/merge1_bb)
280 guard2 (goto merge1_bb/merge2_bb)
287 slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
288 loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
289 that have phis in loop1->header).
291 slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
292 loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
293 that have phis in next_bb). It also adds some of these phis to
296 slpeel_update_phi_nodes_for_guard1 is always called before
297 slpeel_update_phi_nodes_for_guard2. They are both needed in order
298 to create correct data-flow and loop-closed-ssa-form.
300 Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
301 that change between iterations of a loop (and therefore have a phi-node
302 at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
303 phis for variables that are used out of the loop (and therefore have
304 loop-closed exit phis). Some variables may be both updated between
305 iterations and used after the loop. This is why in loop1_exit_bb we
306 may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
307 and exit phis (created by slpeel_update_phi_nodes_for_guard2).
309 - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
310 an original loop. i.e., we have:
313 guard_bb (goto LOOP/new_merge)
319 If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
323 guard_bb (goto LOOP/new_merge)
329 The SSA names defined in the original loop have a current
330 reaching definition that that records the corresponding new
331 ssa-name used in the new duplicated loop copy.
334 /* Function slpeel_update_phi_nodes_for_guard1
337 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
338 - DEFS - a bitmap of ssa names to mark new names for which we recorded
341 In the context of the overall structure, we have:
344 guard1 (goto loop1/merge1_bb)
347 guard2 (goto merge1_bb/merge2_bb)
354 For each name updated between loop iterations (i.e - for each name that has
355 an entry (loop-header) phi in LOOP) we create a new phi in:
356 1. merge1_bb (to account for the edge from guard1)
357 2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
361 slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
362 bool is_new_loop, basic_block *new_exit_bb,
365 gimple orig_phi, new_phi;
366 gimple update_phi, update_phi2;
367 tree guard_arg, loop_arg;
368 basic_block new_merge_bb = guard_edge->dest;
369 edge e = EDGE_SUCC (new_merge_bb, 0);
370 basic_block update_bb = e->dest;
371 basic_block orig_bb = loop->header;
373 tree current_new_name;
374 gimple_stmt_iterator gsi_orig, gsi_update;
376 /* Create new bb between loop and new_merge_bb. */
377 *new_exit_bb = split_edge (single_exit (loop));
379 new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
381 for (gsi_orig = gsi_start_phis (orig_bb),
382 gsi_update = gsi_start_phis (update_bb);
383 !gsi_end_p (gsi_orig) && !gsi_end_p (gsi_update);
384 gsi_next (&gsi_orig), gsi_next (&gsi_update))
386 orig_phi = gsi_stmt (gsi_orig);
387 update_phi = gsi_stmt (gsi_update);
389 /** 1. Handle new-merge-point phis **/
391 /* 1.1. Generate new phi node in NEW_MERGE_BB: */
392 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
395 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
396 of LOOP. Set the two phi args in NEW_PHI for these edges: */
397 loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
398 guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
400 add_phi_arg (new_phi, loop_arg, new_exit_e);
401 add_phi_arg (new_phi, guard_arg, guard_edge);
403 /* 1.3. Update phi in successor block. */
404 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
405 || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
406 SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
407 update_phi2 = new_phi;
410 /** 2. Handle loop-closed-ssa-form phis **/
412 if (!is_gimple_reg (PHI_RESULT (orig_phi)))
415 /* 2.1. Generate new phi node in NEW_EXIT_BB: */
416 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
419 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
420 add_phi_arg (new_phi, loop_arg, single_exit (loop));
422 /* 2.3. Update phi in successor of NEW_EXIT_BB: */
423 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
424 SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
426 /* 2.4. Record the newly created name with set_current_def.
427 We want to find a name such that
428 name = get_current_def (orig_loop_name)
429 and to set its current definition as follows:
430 set_current_def (name, new_phi_name)
432 If LOOP is a new loop then loop_arg is already the name we're
433 looking for. If LOOP is the original loop, then loop_arg is
434 the orig_loop_name and the relevant name is recorded in its
435 current reaching definition. */
437 current_new_name = loop_arg;
440 current_new_name = get_current_def (loop_arg);
441 /* current_def is not available only if the variable does not
442 change inside the loop, in which case we also don't care
443 about recording a current_def for it because we won't be
444 trying to create loop-exit-phis for it. */
445 if (!current_new_name)
448 gcc_assert (get_current_def (current_new_name) == NULL_TREE);
450 set_current_def (current_new_name, PHI_RESULT (new_phi));
451 bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
456 /* Function slpeel_update_phi_nodes_for_guard2
459 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
461 In the context of the overall structure, we have:
464 guard1 (goto loop1/merge1_bb)
467 guard2 (goto merge1_bb/merge2_bb)
474 For each name used out side the loop (i.e - for each name that has an exit
475 phi in next_bb) we create a new phi in:
476 1. merge2_bb (to account for the edge from guard_bb)
477 2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
478 3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
479 if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
483 slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
484 bool is_new_loop, basic_block *new_exit_bb)
486 gimple orig_phi, new_phi;
487 gimple update_phi, update_phi2;
488 tree guard_arg, loop_arg;
489 basic_block new_merge_bb = guard_edge->dest;
490 edge e = EDGE_SUCC (new_merge_bb, 0);
491 basic_block update_bb = e->dest;
493 tree orig_def, orig_def_new_name;
494 tree new_name, new_name2;
496 gimple_stmt_iterator gsi;
498 /* Create new bb between loop and new_merge_bb. */
499 *new_exit_bb = split_edge (single_exit (loop));
501 new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
503 for (gsi = gsi_start_phis (update_bb); !gsi_end_p (gsi); gsi_next (&gsi))
505 update_phi = gsi_stmt (gsi);
506 orig_phi = update_phi;
507 orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
508 /* This loop-closed-phi actually doesn't represent a use
509 out of the loop - the phi arg is a constant. */
510 if (TREE_CODE (orig_def) != SSA_NAME)
512 orig_def_new_name = get_current_def (orig_def);
515 /** 1. Handle new-merge-point phis **/
517 /* 1.1. Generate new phi node in NEW_MERGE_BB: */
518 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
521 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
522 of LOOP. Set the two PHI args in NEW_PHI for these edges: */
524 new_name2 = NULL_TREE;
525 if (orig_def_new_name)
527 new_name = orig_def_new_name;
528 /* Some variables have both loop-entry-phis and loop-exit-phis.
529 Such variables were given yet newer names by phis placed in
530 guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
531 new_name2 = get_current_def (get_current_def (orig_name)). */
532 new_name2 = get_current_def (new_name);
537 guard_arg = orig_def;
542 guard_arg = new_name;
546 guard_arg = new_name2;
548 add_phi_arg (new_phi, loop_arg, new_exit_e);
549 add_phi_arg (new_phi, guard_arg, guard_edge);
551 /* 1.3. Update phi in successor block. */
552 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
553 SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
554 update_phi2 = new_phi;
557 /** 2. Handle loop-closed-ssa-form phis **/
559 /* 2.1. Generate new phi node in NEW_EXIT_BB: */
560 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
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));
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));
571 /** 3. Handle loop-closed-ssa-form phis for first loop **/
573 /* 3.1. Find the relevant names that need an exit-phi in
574 GUARD_BB, i.e. names for which
575 slpeel_update_phi_nodes_for_guard1 had not already created a
576 phi node. This is the case for names that are used outside
577 the loop (and therefore need an exit phi) but are not updated
578 across loop iterations (and therefore don't have a
581 slpeel_update_phi_nodes_for_guard1 is responsible for
582 creating loop-exit phis in GUARD_BB for names that have a
583 loop-header-phi. When such a phi is created we also record
584 the new name in its current definition. If this new name
585 exists, then guard_arg was set to this new name (see 1.2
586 above). Therefore, if guard_arg is not this new name, this
587 is an indication that an exit-phi in GUARD_BB was not yet
588 created, so we take care of it here. */
589 if (guard_arg == new_name2)
593 /* 3.2. Generate new phi node in GUARD_BB: */
594 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
597 /* 3.3. GUARD_BB has one incoming edge: */
598 gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
599 add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0));
601 /* 3.4. Update phi in successor of GUARD_BB: */
602 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
604 SET_PHI_ARG_DEF (update_phi2, guard_edge->dest_idx, PHI_RESULT (new_phi));
609 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
610 that starts at zero, increases by one and its limit is NITERS.
612 Assumption: the exit-condition of LOOP is the last stmt in the loop. */
615 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
617 tree indx_before_incr, indx_after_incr;
620 edge exit_edge = single_exit (loop);
621 gimple_stmt_iterator loop_cond_gsi;
622 gimple_stmt_iterator incr_gsi;
624 tree init = build_int_cst (TREE_TYPE (niters), 0);
625 tree step = build_int_cst (TREE_TYPE (niters), 1);
629 orig_cond = get_loop_exit_condition (loop);
630 gcc_assert (orig_cond);
631 loop_cond_gsi = gsi_for_stmt (orig_cond);
633 standard_iv_increment_position (loop, &incr_gsi, &insert_after);
634 create_iv (init, step, NULL_TREE, loop,
635 &incr_gsi, insert_after, &indx_before_incr, &indx_after_incr);
637 indx_after_incr = force_gimple_operand_gsi (&loop_cond_gsi, indx_after_incr,
638 true, NULL_TREE, true,
640 niters = force_gimple_operand_gsi (&loop_cond_gsi, niters, true, NULL_TREE,
641 true, GSI_SAME_STMT);
643 code = (exit_edge->flags & EDGE_TRUE_VALUE) ? GE_EXPR : LT_EXPR;
644 cond_stmt = gimple_build_cond (code, indx_after_incr, niters, NULL_TREE,
647 gsi_insert_before (&loop_cond_gsi, cond_stmt, GSI_SAME_STMT);
649 /* Remove old loop exit test: */
650 gsi_remove (&loop_cond_gsi, true);
652 loop_loc = find_loop_location (loop);
653 if (dump_file && (dump_flags & TDF_DETAILS))
655 if (loop_loc != UNKNOWN_LOC)
656 fprintf (dump_file, "\nloop at %s:%d: ",
657 LOC_FILE (loop_loc), LOC_LINE (loop_loc));
658 print_gimple_stmt (dump_file, cond_stmt, 0, TDF_SLIM);
661 loop->nb_iterations = niters;
665 /* Given LOOP this function generates a new copy of it and puts it
666 on E which is either the entry or exit of LOOP. */
669 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
671 struct loop *new_loop;
672 basic_block *new_bbs, *bbs;
675 basic_block exit_dest;
679 gimple_stmt_iterator gsi;
681 at_exit = (e == single_exit (loop));
682 if (!at_exit && e != loop_preheader_edge (loop))
685 bbs = get_loop_body (loop);
687 /* Check whether duplication is possible. */
688 if (!can_copy_bbs_p (bbs, loop->num_nodes))
694 /* Generate new loop structure. */
695 new_loop = duplicate_loop (loop, loop_outer (loop));
702 exit_dest = single_exit (loop)->dest;
703 was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
704 exit_dest) == loop->header ?
707 new_bbs = XNEWVEC (basic_block, loop->num_nodes);
709 exit = single_exit (loop);
710 copy_bbs (bbs, loop->num_nodes, new_bbs,
711 &exit, 1, &new_exit, NULL,
714 /* Duplicating phi args at exit bbs as coming
715 also from exit of duplicated loop. */
716 for (gsi = gsi_start_phis (exit_dest); !gsi_end_p (gsi); gsi_next (&gsi))
718 phi = gsi_stmt (gsi);
719 phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
722 edge new_loop_exit_edge;
724 if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
725 new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
727 new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
729 add_phi_arg (phi, phi_arg, new_loop_exit_edge);
733 if (at_exit) /* Add the loop copy at exit. */
735 redirect_edge_and_branch_force (e, new_loop->header);
736 PENDING_STMT (e) = NULL;
737 set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
739 set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
741 else /* Add the copy at entry. */
744 edge entry_e = loop_preheader_edge (loop);
745 basic_block preheader = entry_e->src;
747 if (!flow_bb_inside_loop_p (new_loop,
748 EDGE_SUCC (new_loop->header, 0)->dest))
749 new_exit_e = EDGE_SUCC (new_loop->header, 0);
751 new_exit_e = EDGE_SUCC (new_loop->header, 1);
753 redirect_edge_and_branch_force (new_exit_e, loop->header);
754 PENDING_STMT (new_exit_e) = NULL;
755 set_immediate_dominator (CDI_DOMINATORS, loop->header,
758 /* We have to add phi args to the loop->header here as coming
759 from new_exit_e edge. */
760 for (gsi = gsi_start_phis (loop->header);
764 phi = gsi_stmt (gsi);
765 phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
767 add_phi_arg (phi, phi_arg, new_exit_e);
770 redirect_edge_and_branch_force (entry_e, new_loop->header);
771 PENDING_STMT (entry_e) = NULL;
772 set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
782 /* Given the condition statement COND, put it as the last statement
783 of GUARD_BB; EXIT_BB is the basic block to skip the loop;
784 Assumes that this is the single exit of the guarded loop.
785 Returns the skip edge, inserts new stmts on the COND_EXPR_STMT_LIST. */
788 slpeel_add_loop_guard (basic_block guard_bb, tree cond,
789 gimple_seq cond_expr_stmt_list,
790 basic_block exit_bb, basic_block dom_bb)
792 gimple_stmt_iterator gsi;
795 gimple_seq gimplify_stmt_list = NULL;
797 enter_e = EDGE_SUCC (guard_bb, 0);
798 enter_e->flags &= ~EDGE_FALLTHRU;
799 enter_e->flags |= EDGE_FALSE_VALUE;
800 gsi = gsi_last_bb (guard_bb);
802 cond = force_gimple_operand (cond, &gimplify_stmt_list, true, NULL_TREE);
803 if (gimplify_stmt_list)
804 gimple_seq_add_seq (&cond_expr_stmt_list, gimplify_stmt_list);
805 cond_stmt = gimple_build_cond (NE_EXPR,
806 cond, build_int_cst (TREE_TYPE (cond), 0),
807 NULL_TREE, NULL_TREE);
808 if (cond_expr_stmt_list)
809 gsi_insert_seq_after (&gsi, cond_expr_stmt_list, GSI_NEW_STMT);
811 gsi = gsi_last_bb (guard_bb);
812 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
814 /* Add new edge to connect guard block to the merge/loop-exit block. */
815 new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
816 set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
821 /* This function verifies that the following restrictions apply to LOOP:
823 (2) it consists of exactly 2 basic blocks - header, and an empty latch.
824 (3) it is single entry, single exit
825 (4) its exit condition is the last stmt in the header
826 (5) E is the entry/exit edge of LOOP.
830 slpeel_can_duplicate_loop_p (const struct loop *loop, const_edge e)
832 edge exit_e = single_exit (loop);
833 edge entry_e = loop_preheader_edge (loop);
834 gimple orig_cond = get_loop_exit_condition (loop);
835 gimple_stmt_iterator loop_exit_gsi = gsi_last_bb (exit_e->src);
837 if (need_ssa_update_p (cfun))
841 /* All loops have an outer scope; the only case loop->outer is NULL is for
842 the function itself. */
843 || !loop_outer (loop)
844 || loop->num_nodes != 2
845 || !empty_block_p (loop->latch)
846 || !single_exit (loop)
847 /* Verify that new loop exit condition can be trivially modified. */
848 || (!orig_cond || orig_cond != gsi_stmt (loop_exit_gsi))
849 || (e != exit_e && e != entry_e))
855 #ifdef ENABLE_CHECKING
857 slpeel_verify_cfg_after_peeling (struct loop *first_loop,
858 struct loop *second_loop)
860 basic_block loop1_exit_bb = single_exit (first_loop)->dest;
861 basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
862 basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
864 /* A guard that controls whether the second_loop is to be executed or skipped
865 is placed in first_loop->exit. first_loop->exit therefore has two
866 successors - one is the preheader of second_loop, and the other is a bb
869 gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
871 /* 1. Verify that one of the successors of first_loop->exit is the preheader
874 /* The preheader of new_loop is expected to have two predecessors:
875 first_loop->exit and the block that precedes first_loop. */
877 gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
878 && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
879 && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
880 || (EDGE_PRED (loop2_entry_bb, 1)->src == loop1_exit_bb
881 && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
883 /* Verify that the other successor of first_loop->exit is after the
889 /* If the run time cost model check determines that vectorization is
890 not profitable and hence scalar loop should be generated then set
891 FIRST_NITERS to prologue peeled iterations. This will allow all the
892 iterations to be executed in the prologue peeled scalar loop. */
895 set_prologue_iterations (basic_block bb_before_first_loop,
901 basic_block cond_bb, then_bb;
902 tree var, prologue_after_cost_adjust_name;
903 gimple_stmt_iterator gsi;
905 edge e_true, e_false, e_fallthru;
907 gimple_seq gimplify_stmt_list = NULL, stmts = NULL;
908 tree cost_pre_condition = NULL_TREE;
909 tree scalar_loop_iters =
910 unshare_expr (LOOP_VINFO_NITERS_UNCHANGED (loop_vec_info_for_loop (loop)));
912 e = single_pred_edge (bb_before_first_loop);
913 cond_bb = split_edge(e);
915 e = single_pred_edge (bb_before_first_loop);
916 then_bb = split_edge(e);
917 set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb);
919 e_false = make_single_succ_edge (cond_bb, bb_before_first_loop,
921 set_immediate_dominator (CDI_DOMINATORS, bb_before_first_loop, cond_bb);
923 e_true = EDGE_PRED (then_bb, 0);
924 e_true->flags &= ~EDGE_FALLTHRU;
925 e_true->flags |= EDGE_TRUE_VALUE;
927 e_fallthru = EDGE_SUCC (then_bb, 0);
930 fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
931 build_int_cst (TREE_TYPE (scalar_loop_iters), th));
933 force_gimple_operand (cost_pre_condition, &gimplify_stmt_list,
935 cond_stmt = gimple_build_cond (NE_EXPR, cost_pre_condition,
936 build_int_cst (TREE_TYPE (cost_pre_condition),
937 0), NULL_TREE, NULL_TREE);
939 gsi = gsi_last_bb (cond_bb);
940 if (gimplify_stmt_list)
941 gsi_insert_seq_after (&gsi, gimplify_stmt_list, GSI_NEW_STMT);
943 gsi = gsi_last_bb (cond_bb);
944 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
946 var = create_tmp_var (TREE_TYPE (scalar_loop_iters),
947 "prologue_after_cost_adjust");
948 add_referenced_var (var);
949 prologue_after_cost_adjust_name =
950 force_gimple_operand (scalar_loop_iters, &stmts, false, var);
952 gsi = gsi_last_bb (then_bb);
954 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
956 newphi = create_phi_node (var, bb_before_first_loop);
957 add_phi_arg (newphi, prologue_after_cost_adjust_name, e_fallthru);
958 add_phi_arg (newphi, first_niters, e_false);
960 first_niters = PHI_RESULT (newphi);
964 /* Function slpeel_tree_peel_loop_to_edge.
966 Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
967 that is placed on the entry (exit) edge E of LOOP. After this transformation
968 we have two loops one after the other - first-loop iterates FIRST_NITERS
969 times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
970 If the cost model indicates that it is profitable to emit a scalar
971 loop instead of the vector one, then the prolog (epilog) loop will iterate
972 for the entire unchanged scalar iterations of the loop.
975 - LOOP: the loop to be peeled.
976 - E: the exit or entry edge of LOOP.
977 If it is the entry edge, we peel the first iterations of LOOP. In this
978 case first-loop is LOOP, and second-loop is the newly created loop.
979 If it is the exit edge, we peel the last iterations of LOOP. In this
980 case, first-loop is the newly created loop, and second-loop is LOOP.
981 - NITERS: the number of iterations that LOOP iterates.
982 - FIRST_NITERS: the number of iterations that the first-loop should iterate.
983 - UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible
984 for updating the loop bound of the first-loop to FIRST_NITERS. If it
985 is false, the caller of this function may want to take care of this
986 (this can be useful if we don't want new stmts added to first-loop).
987 - TH: cost model profitability threshold of iterations for vectorization.
988 - CHECK_PROFITABILITY: specify whether cost model check has not occurred
989 during versioning and hence needs to occur during
990 prologue generation or whether cost model check
991 has not occurred during prologue generation and hence
992 needs to occur during epilogue generation.
996 The function returns a pointer to the new loop-copy, or NULL if it failed
997 to perform the transformation.
999 The function generates two if-then-else guards: one before the first loop,
1000 and the other before the second loop:
1002 if (FIRST_NITERS == 0) then skip the first loop,
1003 and go directly to the second loop.
1004 The second guard is:
1005 if (FIRST_NITERS == NITERS) then skip the second loop.
1007 If the optional COND_EXPR and COND_EXPR_STMT_LIST arguments are given
1008 then the generated condition is combined with COND_EXPR and the
1009 statements in COND_EXPR_STMT_LIST are emitted together with it.
1011 FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
1012 FORNOW the resulting code will not be in loop-closed-ssa form.
1016 slpeel_tree_peel_loop_to_edge (struct loop *loop,
1017 edge e, tree first_niters,
1018 tree niters, bool update_first_loop_count,
1019 unsigned int th, bool check_profitability,
1020 tree cond_expr, gimple_seq cond_expr_stmt_list)
1022 struct loop *new_loop = NULL, *first_loop, *second_loop;
1024 tree pre_condition = NULL_TREE;
1026 basic_block bb_before_second_loop, bb_after_second_loop;
1027 basic_block bb_before_first_loop;
1028 basic_block bb_between_loops;
1029 basic_block new_exit_bb;
1030 edge exit_e = single_exit (loop);
1032 tree cost_pre_condition = NULL_TREE;
1034 if (!slpeel_can_duplicate_loop_p (loop, e))
1037 /* We have to initialize cfg_hooks. Then, when calling
1038 cfg_hooks->split_edge, the function tree_split_edge
1039 is actually called and, when calling cfg_hooks->duplicate_block,
1040 the function tree_duplicate_bb is called. */
1041 gimple_register_cfg_hooks ();
1044 /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1045 Resulting CFG would be:
1058 if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e)))
1060 loop_loc = find_loop_location (loop);
1061 if (dump_file && (dump_flags & TDF_DETAILS))
1063 if (loop_loc != UNKNOWN_LOC)
1064 fprintf (dump_file, "\n%s:%d: note: ",
1065 LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1066 fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
1073 /* NEW_LOOP was placed after LOOP. */
1075 second_loop = new_loop;
1079 /* NEW_LOOP was placed before LOOP. */
1080 first_loop = new_loop;
1084 definitions = ssa_names_to_replace ();
1085 slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
1086 rename_variables_in_loop (new_loop);
1089 /* 2. Add the guard code in one of the following ways:
1091 2.a Add the guard that controls whether the first loop is executed.
1092 This occurs when this function is invoked for prologue or epilogue
1093 generation and when the cost model check can be done at compile time.
1095 Resulting CFG would be:
1097 bb_before_first_loop:
1098 if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1105 bb_before_second_loop:
1113 2.b Add the cost model check that allows the prologue
1114 to iterate for the entire unchanged scalar
1115 iterations of the loop in the event that the cost
1116 model indicates that the scalar loop is more
1117 profitable than the vector one. This occurs when
1118 this function is invoked for prologue generation
1119 and the cost model check needs to be done at run
1122 Resulting CFG after prologue peeling would be:
1124 if (scalar_loop_iterations <= th)
1125 FIRST_NITERS = scalar_loop_iterations
1127 bb_before_first_loop:
1128 if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1135 bb_before_second_loop:
1143 2.c Add the cost model check that allows the epilogue
1144 to iterate for the entire unchanged scalar
1145 iterations of the loop in the event that the cost
1146 model indicates that the scalar loop is more
1147 profitable than the vector one. This occurs when
1148 this function is invoked for epilogue generation
1149 and the cost model check needs to be done at run
1150 time. This check is combined with any pre-existing
1151 check in COND_EXPR to avoid versioning.
1153 Resulting CFG after prologue peeling would be:
1155 bb_before_first_loop:
1156 if ((scalar_loop_iterations <= th)
1158 FIRST_NITERS == 0) GOTO bb_before_second_loop
1165 bb_before_second_loop:
1174 bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
1175 bb_before_second_loop = split_edge (single_exit (first_loop));
1177 /* Epilogue peeling. */
1178 if (!update_first_loop_count)
1181 fold_build2 (LE_EXPR, boolean_type_node, first_niters,
1182 build_int_cst (TREE_TYPE (first_niters), 0));
1183 if (check_profitability)
1185 tree scalar_loop_iters
1186 = unshare_expr (LOOP_VINFO_NITERS_UNCHANGED
1187 (loop_vec_info_for_loop (loop)));
1188 cost_pre_condition =
1189 fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
1190 build_int_cst (TREE_TYPE (scalar_loop_iters), th));
1192 pre_condition = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1193 cost_pre_condition, pre_condition);
1198 fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1200 fold_build1 (TRUTH_NOT_EXPR, boolean_type_node,
1205 /* Prologue peeling. */
1208 if (check_profitability)
1209 set_prologue_iterations (bb_before_first_loop, first_niters,
1213 fold_build2 (LE_EXPR, boolean_type_node, first_niters,
1214 build_int_cst (TREE_TYPE (first_niters), 0));
1217 skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
1218 cond_expr_stmt_list,
1219 bb_before_second_loop, bb_before_first_loop);
1220 slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
1221 first_loop == new_loop,
1222 &new_exit_bb, &definitions);
1225 /* 3. Add the guard that controls whether the second loop is executed.
1226 Resulting CFG would be:
1228 bb_before_first_loop:
1229 if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1237 if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1238 GOTO bb_before_second_loop
1240 bb_before_second_loop:
1246 bb_after_second_loop:
1251 bb_between_loops = new_exit_bb;
1252 bb_after_second_loop = split_edge (single_exit (second_loop));
1255 fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
1256 skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition, NULL,
1257 bb_after_second_loop, bb_before_first_loop);
1258 slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
1259 second_loop == new_loop, &new_exit_bb);
1261 /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1263 if (update_first_loop_count)
1264 slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
1266 BITMAP_FREE (definitions);
1267 delete_update_ssa ();
1272 /* Function vect_get_loop_location.
1274 Extract the location of the loop in the source code.
1275 If the loop is not well formed for vectorization, an estimated
1276 location is calculated.
1277 Return the loop location if succeed and NULL if not. */
1280 find_loop_location (struct loop *loop)
1284 gimple_stmt_iterator si;
1289 stmt = get_loop_exit_condition (loop);
1291 if (stmt && gimple_location (stmt) != UNKNOWN_LOC)
1292 return gimple_location (stmt);
1294 /* If we got here the loop is probably not "well formed",
1295 try to estimate the loop location */
1302 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1304 stmt = gsi_stmt (si);
1305 if (gimple_location (stmt) != UNKNOWN_LOC)
1306 return gimple_location (stmt);
1313 /* This function builds ni_name = number of iterations loop executes
1314 on the loop preheader. If SEQ is given the stmt is instead emitted
1318 vect_build_loop_niters (loop_vec_info loop_vinfo, gimple_seq seq)
1321 gimple_seq stmts = NULL;
1323 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1324 tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
1326 var = create_tmp_var (TREE_TYPE (ni), "niters");
1327 add_referenced_var (var);
1328 ni_name = force_gimple_operand (ni, &stmts, false, var);
1330 pe = loop_preheader_edge (loop);
1334 gimple_seq_add_seq (&seq, stmts);
1337 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1338 gcc_assert (!new_bb);
1346 /* This function generates the following statements:
1348 ni_name = number of iterations loop executes
1349 ratio = ni_name / vf
1350 ratio_mult_vf_name = ratio * vf
1352 and places them at the loop preheader edge or in COND_EXPR_STMT_LIST
1353 if that is non-NULL. */
1356 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
1358 tree *ratio_mult_vf_name_ptr,
1359 tree *ratio_name_ptr,
1360 gimple_seq cond_expr_stmt_list)
1369 tree ratio_mult_vf_name;
1370 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1371 tree ni = LOOP_VINFO_NITERS (loop_vinfo);
1372 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1375 pe = loop_preheader_edge (loop);
1377 /* Generate temporary variable that contains
1378 number of iterations loop executes. */
1380 ni_name = vect_build_loop_niters (loop_vinfo, cond_expr_stmt_list);
1381 log_vf = build_int_cst (TREE_TYPE (ni), exact_log2 (vf));
1383 /* Create: ratio = ni >> log2(vf) */
1385 ratio_name = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ni_name), ni_name, log_vf);
1386 if (!is_gimple_val (ratio_name))
1388 var = create_tmp_var (TREE_TYPE (ni), "bnd");
1389 add_referenced_var (var);
1392 ratio_name = force_gimple_operand (ratio_name, &stmts, true, var);
1393 if (cond_expr_stmt_list)
1394 gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
1397 pe = loop_preheader_edge (loop);
1398 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1399 gcc_assert (!new_bb);
1403 /* Create: ratio_mult_vf = ratio << log2 (vf). */
1405 ratio_mult_vf_name = fold_build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name),
1406 ratio_name, log_vf);
1407 if (!is_gimple_val (ratio_mult_vf_name))
1409 var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
1410 add_referenced_var (var);
1413 ratio_mult_vf_name = force_gimple_operand (ratio_mult_vf_name, &stmts,
1415 if (cond_expr_stmt_list)
1416 gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
1419 pe = loop_preheader_edge (loop);
1420 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1421 gcc_assert (!new_bb);
1425 *ni_name_ptr = ni_name;
1426 *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
1427 *ratio_name_ptr = ratio_name;
1432 /* Function vect_can_advance_ivs_p
1434 In case the number of iterations that LOOP iterates is unknown at compile
1435 time, an epilog loop will be generated, and the loop induction variables
1436 (IVs) will be "advanced" to the value they are supposed to take just before
1437 the epilog loop. Here we check that the access function of the loop IVs
1438 and the expression that represents the loop bound are simple enough.
1439 These restrictions will be relaxed in the future. */
1442 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
1444 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1445 basic_block bb = loop->header;
1447 gimple_stmt_iterator gsi;
1449 /* Analyze phi functions of the loop header. */
1451 if (vect_print_dump_info (REPORT_DETAILS))
1452 fprintf (vect_dump, "vect_can_advance_ivs_p:");
1454 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1456 tree access_fn = NULL;
1457 tree evolution_part;
1459 phi = gsi_stmt (gsi);
1460 if (vect_print_dump_info (REPORT_DETAILS))
1462 fprintf (vect_dump, "Analyze phi: ");
1463 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1466 /* Skip virtual phi's. The data dependences that are associated with
1467 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
1469 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1471 if (vect_print_dump_info (REPORT_DETAILS))
1472 fprintf (vect_dump, "virtual phi. skip.");
1476 /* Skip reduction phis. */
1478 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
1480 if (vect_print_dump_info (REPORT_DETAILS))
1481 fprintf (vect_dump, "reduc phi. skip.");
1485 /* Analyze the evolution function. */
1487 access_fn = instantiate_parameters
1488 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
1492 if (vect_print_dump_info (REPORT_DETAILS))
1493 fprintf (vect_dump, "No Access function.");
1497 if (vect_print_dump_info (REPORT_DETAILS))
1499 fprintf (vect_dump, "Access function of PHI: ");
1500 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
1503 evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
1505 if (evolution_part == NULL_TREE)
1507 if (vect_print_dump_info (REPORT_DETAILS))
1508 fprintf (vect_dump, "No evolution.");
1512 /* FORNOW: We do not transform initial conditions of IVs
1513 which evolution functions are a polynomial of degree >= 2. */
1515 if (tree_is_chrec (evolution_part))
1523 /* Function vect_update_ivs_after_vectorizer.
1525 "Advance" the induction variables of LOOP to the value they should take
1526 after the execution of LOOP. This is currently necessary because the
1527 vectorizer does not handle induction variables that are used after the
1528 loop. Such a situation occurs when the last iterations of LOOP are
1530 1. We introduced new uses after LOOP for IVs that were not originally used
1531 after LOOP: the IVs of LOOP are now used by an epilog loop.
1532 2. LOOP is going to be vectorized; this means that it will iterate N/VF
1533 times, whereas the loop IVs should be bumped N times.
1536 - LOOP - a loop that is going to be vectorized. The last few iterations
1537 of LOOP were peeled.
1538 - NITERS - the number of iterations that LOOP executes (before it is
1539 vectorized). i.e, the number of times the ivs should be bumped.
1540 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
1541 coming out from LOOP on which there are uses of the LOOP ivs
1542 (this is the path from LOOP->exit to epilog_loop->preheader).
1544 The new definitions of the ivs are placed in LOOP->exit.
1545 The phi args associated with the edge UPDATE_E in the bb
1546 UPDATE_E->dest are updated accordingly.
1548 Assumption 1: Like the rest of the vectorizer, this function assumes
1549 a single loop exit that has a single predecessor.
1551 Assumption 2: The phi nodes in the LOOP header and in update_bb are
1552 organized in the same order.
1554 Assumption 3: The access function of the ivs is simple enough (see
1555 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
1557 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
1558 coming out of LOOP on which the ivs of LOOP are used (this is the path
1559 that leads to the epilog loop; other paths skip the epilog loop). This
1560 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
1561 needs to have its phis updated.
1565 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
1568 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1569 basic_block exit_bb = single_exit (loop)->dest;
1571 gimple_stmt_iterator gsi, gsi1;
1572 basic_block update_bb = update_e->dest;
1574 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
1576 /* Make sure there exists a single-predecessor exit bb: */
1577 gcc_assert (single_pred_p (exit_bb));
1579 for (gsi = gsi_start_phis (loop->header), gsi1 = gsi_start_phis (update_bb);
1580 !gsi_end_p (gsi) && !gsi_end_p (gsi1);
1581 gsi_next (&gsi), gsi_next (&gsi1))
1583 tree access_fn = NULL;
1584 tree evolution_part;
1586 tree step_expr, off;
1588 tree var, ni, ni_name;
1589 gimple_stmt_iterator last_gsi;
1591 phi = gsi_stmt (gsi);
1592 phi1 = gsi_stmt (gsi1);
1593 if (vect_print_dump_info (REPORT_DETAILS))
1595 fprintf (vect_dump, "vect_update_ivs_after_vectorizer: phi: ");
1596 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1599 /* Skip virtual phi's. */
1600 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1602 if (vect_print_dump_info (REPORT_DETAILS))
1603 fprintf (vect_dump, "virtual phi. skip.");
1607 /* Skip reduction phis. */
1608 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
1610 if (vect_print_dump_info (REPORT_DETAILS))
1611 fprintf (vect_dump, "reduc phi. skip.");
1615 access_fn = analyze_scalar_evolution (loop, PHI_RESULT (phi));
1616 gcc_assert (access_fn);
1617 /* We can end up with an access_fn like
1618 (short int) {(short unsigned int) i_49, +, 1}_1
1619 for further analysis we need to strip the outer cast but we
1620 need to preserve the original type. */
1621 type = TREE_TYPE (access_fn);
1622 STRIP_NOPS (access_fn);
1624 unshare_expr (evolution_part_in_loop_num (access_fn, loop->num));
1625 gcc_assert (evolution_part != NULL_TREE);
1627 /* FORNOW: We do not support IVs whose evolution function is a polynomial
1628 of degree >= 2 or exponential. */
1629 gcc_assert (!tree_is_chrec (evolution_part));
1631 step_expr = evolution_part;
1632 init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
1634 init_expr = fold_convert (type, init_expr);
1636 off = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
1637 fold_convert (TREE_TYPE (step_expr), niters),
1639 if (POINTER_TYPE_P (TREE_TYPE (init_expr)))
1640 ni = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (init_expr),
1642 fold_convert (sizetype, off));
1644 ni = fold_build2 (PLUS_EXPR, TREE_TYPE (init_expr),
1646 fold_convert (TREE_TYPE (init_expr), off));
1648 var = create_tmp_var (TREE_TYPE (init_expr), "tmp");
1649 add_referenced_var (var);
1651 last_gsi = gsi_last_bb (exit_bb);
1652 ni_name = force_gimple_operand_gsi (&last_gsi, ni, false, var,
1653 true, GSI_SAME_STMT);
1655 /* Fix phi expressions in the successor bb. */
1656 SET_PHI_ARG_DEF (phi1, update_e->dest_idx, ni_name);
1660 /* Return the more conservative threshold between the
1661 min_profitable_iters returned by the cost model and the user
1662 specified threshold, if provided. */
1665 conservative_cost_threshold (loop_vec_info loop_vinfo,
1666 int min_profitable_iters)
1669 int min_scalar_loop_bound;
1671 min_scalar_loop_bound = ((PARAM_VALUE (PARAM_MIN_VECT_LOOP_BOUND)
1672 * LOOP_VINFO_VECT_FACTOR (loop_vinfo)) - 1);
1674 /* Use the cost model only if it is more conservative than user specified
1676 th = (unsigned) min_scalar_loop_bound;
1677 if (min_profitable_iters
1678 && (!min_scalar_loop_bound
1679 || min_profitable_iters > min_scalar_loop_bound))
1680 th = (unsigned) min_profitable_iters;
1682 if (th && vect_print_dump_info (REPORT_COST))
1683 fprintf (vect_dump, "Profitability threshold is %u loop iterations.", th);
1688 /* Function vect_do_peeling_for_loop_bound
1690 Peel the last iterations of the loop represented by LOOP_VINFO.
1691 The peeled iterations form a new epilog loop. Given that the loop now
1692 iterates NITERS times, the new epilog loop iterates
1693 NITERS % VECTORIZATION_FACTOR times.
1695 The original loop will later be made to iterate
1696 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).
1698 COND_EXPR and COND_EXPR_STMT_LIST are combined with a new generated
1702 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio,
1703 tree cond_expr, gimple_seq cond_expr_stmt_list)
1705 tree ni_name, ratio_mult_vf_name;
1706 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1707 struct loop *new_loop;
1709 basic_block preheader;
1711 bool check_profitability = false;
1712 unsigned int th = 0;
1713 int min_profitable_iters;
1715 if (vect_print_dump_info (REPORT_DETAILS))
1716 fprintf (vect_dump, "=== vect_do_peeling_for_loop_bound ===");
1718 initialize_original_copy_tables ();
1720 /* Generate the following variables on the preheader of original loop:
1722 ni_name = number of iteration the original loop executes
1723 ratio = ni_name / vf
1724 ratio_mult_vf_name = ratio * vf */
1725 vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
1726 &ratio_mult_vf_name, ratio,
1727 cond_expr_stmt_list);
1729 loop_num = loop->num;
1731 /* If cost model check not done during versioning and
1732 peeling for alignment. */
1733 if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)
1734 && !LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo)
1735 && !LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo)
1738 check_profitability = true;
1740 /* Get profitability threshold for vectorized loop. */
1741 min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
1743 th = conservative_cost_threshold (loop_vinfo,
1744 min_profitable_iters);
1747 new_loop = slpeel_tree_peel_loop_to_edge (loop, single_exit (loop),
1748 ratio_mult_vf_name, ni_name, false,
1749 th, check_profitability,
1750 cond_expr, cond_expr_stmt_list);
1751 gcc_assert (new_loop);
1752 gcc_assert (loop_num == loop->num);
1753 #ifdef ENABLE_CHECKING
1754 slpeel_verify_cfg_after_peeling (loop, new_loop);
1757 /* A guard that controls whether the new_loop is to be executed or skipped
1758 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
1759 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
1760 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
1761 is on the path where the LOOP IVs are used and need to be updated. */
1763 preheader = loop_preheader_edge (new_loop)->src;
1764 if (EDGE_PRED (preheader, 0)->src == single_exit (loop)->dest)
1765 update_e = EDGE_PRED (preheader, 0);
1767 update_e = EDGE_PRED (preheader, 1);
1769 /* Update IVs of original loop as if they were advanced
1770 by ratio_mult_vf_name steps. */
1771 vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e);
1773 /* After peeling we have to reset scalar evolution analyzer. */
1776 free_original_copy_tables ();
1780 /* Function vect_gen_niters_for_prolog_loop
1782 Set the number of iterations for the loop represented by LOOP_VINFO
1783 to the minimum between LOOP_NITERS (the original iteration count of the loop)
1784 and the misalignment of DR - the data reference recorded in
1785 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
1786 this loop, the data reference DR will refer to an aligned location.
1788 The following computation is generated:
1790 If the misalignment of DR is known at compile time:
1791 addr_mis = int mis = DR_MISALIGNMENT (dr);
1792 Else, compute address misalignment in bytes:
1793 addr_mis = addr & (vectype_size - 1)
1795 prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
1797 (elem_size = element type size; an element is the scalar element whose type
1798 is the inner type of the vectype)
1800 When the step of the data-ref in the loop is not 1 (as in interleaved data
1801 and SLP), the number of iterations of the prolog must be divided by the step
1802 (which is equal to the size of interleaved group).
1804 The above formulas assume that VF == number of elements in the vector. This
1805 may not hold when there are multiple-types in the loop.
1806 In this case, for some data-references in the loop the VF does not represent
1807 the number of elements that fit in the vector. Therefore, instead of VF we
1808 use TYPE_VECTOR_SUBPARTS. */
1811 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters)
1813 struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
1814 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1817 tree iters, iters_name;
1820 gimple dr_stmt = DR_STMT (dr);
1821 stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt);
1822 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1823 int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT;
1824 tree niters_type = TREE_TYPE (loop_niters);
1826 int element_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
1827 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1829 if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
1830 step = DR_GROUP_SIZE (vinfo_for_stmt (DR_GROUP_FIRST_DR (stmt_info)));
1832 pe = loop_preheader_edge (loop);
1834 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
1836 int byte_misalign = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
1837 int elem_misalign = byte_misalign / element_size;
1839 if (vect_print_dump_info (REPORT_DETAILS))
1840 fprintf (vect_dump, "known alignment = %d.", byte_misalign);
1842 iters = build_int_cst (niters_type,
1843 (((nelements - elem_misalign) & (nelements - 1)) / step));
1847 gimple_seq new_stmts = NULL;
1848 tree start_addr = vect_create_addr_base_for_vector_ref (dr_stmt,
1849 &new_stmts, NULL_TREE, loop);
1850 tree ptr_type = TREE_TYPE (start_addr);
1851 tree size = TYPE_SIZE (ptr_type);
1852 tree type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
1853 tree vectype_size_minus_1 = build_int_cst (type, vectype_align - 1);
1854 tree elem_size_log =
1855 build_int_cst (type, exact_log2 (vectype_align/nelements));
1856 tree nelements_minus_1 = build_int_cst (type, nelements - 1);
1857 tree nelements_tree = build_int_cst (type, nelements);
1861 new_bb = gsi_insert_seq_on_edge_immediate (pe, new_stmts);
1862 gcc_assert (!new_bb);
1864 /* Create: byte_misalign = addr & (vectype_size - 1) */
1866 fold_build2 (BIT_AND_EXPR, type, fold_convert (type, start_addr), vectype_size_minus_1);
1868 /* Create: elem_misalign = byte_misalign / element_size */
1870 fold_build2 (RSHIFT_EXPR, type, byte_misalign, elem_size_log);
1872 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
1873 iters = fold_build2 (MINUS_EXPR, type, nelements_tree, elem_misalign);
1874 iters = fold_build2 (BIT_AND_EXPR, type, iters, nelements_minus_1);
1875 iters = fold_convert (niters_type, iters);
1878 /* Create: prolog_loop_niters = min (iters, loop_niters) */
1879 /* If the loop bound is known at compile time we already verified that it is
1880 greater than vf; since the misalignment ('iters') is at most vf, there's
1881 no need to generate the MIN_EXPR in this case. */
1882 if (TREE_CODE (loop_niters) != INTEGER_CST)
1883 iters = fold_build2 (MIN_EXPR, niters_type, iters, loop_niters);
1885 if (vect_print_dump_info (REPORT_DETAILS))
1887 fprintf (vect_dump, "niters for prolog loop: ");
1888 print_generic_expr (vect_dump, iters, TDF_SLIM);
1891 var = create_tmp_var (niters_type, "prolog_loop_niters");
1892 add_referenced_var (var);
1894 iters_name = force_gimple_operand (iters, &stmts, false, var);
1896 /* Insert stmt on loop preheader edge. */
1899 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1900 gcc_assert (!new_bb);
1907 /* Function vect_update_init_of_dr
1909 NITERS iterations were peeled from LOOP. DR represents a data reference
1910 in LOOP. This function updates the information recorded in DR to
1911 account for the fact that the first NITERS iterations had already been
1912 executed. Specifically, it updates the OFFSET field of DR. */
1915 vect_update_init_of_dr (struct data_reference *dr, tree niters)
1917 tree offset = DR_OFFSET (dr);
1919 niters = fold_build2 (MULT_EXPR, sizetype,
1920 fold_convert (sizetype, niters),
1921 fold_convert (sizetype, DR_STEP (dr)));
1922 offset = fold_build2 (PLUS_EXPR, sizetype,
1923 fold_convert (sizetype, offset), niters);
1924 DR_OFFSET (dr) = offset;
1928 /* Function vect_update_inits_of_drs
1930 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
1931 This function updates the information recorded for the data references in
1932 the loop to account for the fact that the first NITERS iterations had
1933 already been executed. Specifically, it updates the initial_condition of
1934 the access_function of all the data_references in the loop. */
1937 vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters)
1940 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1941 struct data_reference *dr;
1943 if (vect_print_dump_info (REPORT_DETAILS))
1944 fprintf (vect_dump, "=== vect_update_inits_of_dr ===");
1946 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
1947 vect_update_init_of_dr (dr, niters);
1951 /* Function vect_do_peeling_for_alignment
1953 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
1954 'niters' is set to the misalignment of one of the data references in the
1955 loop, thereby forcing it to refer to an aligned location at the beginning
1956 of the execution of this loop. The data reference for which we are
1957 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
1960 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo)
1962 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1963 tree niters_of_prolog_loop, ni_name;
1965 struct loop *new_loop;
1966 unsigned int th = 0;
1967 int min_profitable_iters;
1969 if (vect_print_dump_info (REPORT_DETAILS))
1970 fprintf (vect_dump, "=== vect_do_peeling_for_alignment ===");
1972 initialize_original_copy_tables ();
1974 ni_name = vect_build_loop_niters (loop_vinfo, NULL);
1975 niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo, ni_name);
1978 /* Get profitability threshold for vectorized loop. */
1979 min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
1980 th = conservative_cost_threshold (loop_vinfo,
1981 min_profitable_iters);
1983 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
1985 slpeel_tree_peel_loop_to_edge (loop, loop_preheader_edge (loop),
1986 niters_of_prolog_loop, ni_name, true,
1987 th, true, NULL_TREE, NULL);
1989 gcc_assert (new_loop);
1990 #ifdef ENABLE_CHECKING
1991 slpeel_verify_cfg_after_peeling (new_loop, loop);
1994 /* Update number of times loop executes. */
1995 n_iters = LOOP_VINFO_NITERS (loop_vinfo);
1996 LOOP_VINFO_NITERS (loop_vinfo) = fold_build2 (MINUS_EXPR,
1997 TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop);
1999 /* Update the init conditions of the access functions of all data refs. */
2000 vect_update_inits_of_drs (loop_vinfo, niters_of_prolog_loop);
2002 /* After peeling we have to reset scalar evolution analyzer. */
2005 free_original_copy_tables ();
2009 /* Function vect_create_cond_for_align_checks.
2011 Create a conditional expression that represents the alignment checks for
2012 all of data references (array element references) whose alignment must be
2016 COND_EXPR - input conditional expression. New conditions will be chained
2017 with logical AND operation.
2018 LOOP_VINFO - two fields of the loop information are used.
2019 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
2020 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
2023 COND_EXPR_STMT_LIST - statements needed to construct the conditional
2025 The returned value is the conditional expression to be used in the if
2026 statement that controls which version of the loop gets executed at runtime.
2028 The algorithm makes two assumptions:
2029 1) The number of bytes "n" in a vector is a power of 2.
2030 2) An address "a" is aligned if a%n is zero and that this
2031 test can be done as a&(n-1) == 0. For example, for 16
2032 byte vectors the test is a&0xf == 0. */
2035 vect_create_cond_for_align_checks (loop_vec_info loop_vinfo,
2037 gimple_seq *cond_expr_stmt_list)
2039 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2040 VEC(gimple,heap) *may_misalign_stmts
2041 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
2043 int mask = LOOP_VINFO_PTR_MASK (loop_vinfo);
2047 tree int_ptrsize_type;
2049 tree or_tmp_name = NULL_TREE;
2050 tree and_tmp, and_tmp_name;
2053 tree part_cond_expr;
2055 /* Check that mask is one less than a power of 2, i.e., mask is
2056 all zeros followed by all ones. */
2057 gcc_assert ((mask != 0) && ((mask & (mask+1)) == 0));
2059 /* CHECKME: what is the best integer or unsigned type to use to hold a
2060 cast from a pointer value? */
2061 psize = TYPE_SIZE (ptr_type_node);
2063 = lang_hooks.types.type_for_size (tree_low_cst (psize, 1), 0);
2065 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
2066 of the first vector of the i'th data reference. */
2068 for (i = 0; VEC_iterate (gimple, may_misalign_stmts, i, ref_stmt); i++)
2070 gimple_seq new_stmt_list = NULL;
2072 tree addr_tmp, addr_tmp_name;
2073 tree or_tmp, new_or_tmp_name;
2074 gimple addr_stmt, or_stmt;
2076 /* create: addr_tmp = (int)(address_of_first_vector) */
2078 vect_create_addr_base_for_vector_ref (ref_stmt, &new_stmt_list,
2080 if (new_stmt_list != NULL)
2081 gimple_seq_add_seq (cond_expr_stmt_list, new_stmt_list);
2083 sprintf (tmp_name, "%s%d", "addr2int", i);
2084 addr_tmp = create_tmp_var (int_ptrsize_type, tmp_name);
2085 add_referenced_var (addr_tmp);
2086 addr_tmp_name = make_ssa_name (addr_tmp, NULL);
2087 addr_stmt = gimple_build_assign_with_ops (NOP_EXPR, addr_tmp_name,
2088 addr_base, NULL_TREE);
2089 SSA_NAME_DEF_STMT (addr_tmp_name) = addr_stmt;
2090 gimple_seq_add_stmt (cond_expr_stmt_list, addr_stmt);
2092 /* The addresses are OR together. */
2094 if (or_tmp_name != NULL_TREE)
2096 /* create: or_tmp = or_tmp | addr_tmp */
2097 sprintf (tmp_name, "%s%d", "orptrs", i);
2098 or_tmp = create_tmp_var (int_ptrsize_type, tmp_name);
2099 add_referenced_var (or_tmp);
2100 new_or_tmp_name = make_ssa_name (or_tmp, NULL);
2101 or_stmt = gimple_build_assign_with_ops (BIT_IOR_EXPR,
2103 or_tmp_name, addr_tmp_name);
2104 SSA_NAME_DEF_STMT (new_or_tmp_name) = or_stmt;
2105 gimple_seq_add_stmt (cond_expr_stmt_list, or_stmt);
2106 or_tmp_name = new_or_tmp_name;
2109 or_tmp_name = addr_tmp_name;
2113 mask_cst = build_int_cst (int_ptrsize_type, mask);
2115 /* create: and_tmp = or_tmp & mask */
2116 and_tmp = create_tmp_var (int_ptrsize_type, "andmask" );
2117 add_referenced_var (and_tmp);
2118 and_tmp_name = make_ssa_name (and_tmp, NULL);
2120 and_stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, and_tmp_name,
2121 or_tmp_name, mask_cst);
2122 SSA_NAME_DEF_STMT (and_tmp_name) = and_stmt;
2123 gimple_seq_add_stmt (cond_expr_stmt_list, and_stmt);
2125 /* Make and_tmp the left operand of the conditional test against zero.
2126 if and_tmp has a nonzero bit then some address is unaligned. */
2127 ptrsize_zero = build_int_cst (int_ptrsize_type, 0);
2128 part_cond_expr = fold_build2 (EQ_EXPR, boolean_type_node,
2129 and_tmp_name, ptrsize_zero);
2131 *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2132 *cond_expr, part_cond_expr);
2134 *cond_expr = part_cond_expr;
2138 /* Function vect_vfa_segment_size.
2140 Create an expression that computes the size of segment
2141 that will be accessed for a data reference. The functions takes into
2142 account that realignment loads may access one more vector.
2145 DR: The data reference.
2146 VECT_FACTOR: vectorization factor.
2148 Return an expression whose value is the size of segment which will be
2152 vect_vfa_segment_size (struct data_reference *dr, tree vect_factor)
2154 tree segment_length = fold_build2 (MULT_EXPR, integer_type_node,
2155 DR_STEP (dr), vect_factor);
2157 if (vect_supportable_dr_alignment (dr) == dr_explicit_realign_optimized)
2159 tree vector_size = TYPE_SIZE_UNIT
2160 (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr))));
2162 segment_length = fold_build2 (PLUS_EXPR, integer_type_node,
2163 segment_length, vector_size);
2165 return fold_convert (sizetype, segment_length);
2169 /* Function vect_create_cond_for_alias_checks.
2171 Create a conditional expression that represents the run-time checks for
2172 overlapping of address ranges represented by a list of data references
2173 relations passed as input.
2176 COND_EXPR - input conditional expression. New conditions will be chained
2177 with logical AND operation.
2178 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
2182 COND_EXPR - conditional expression.
2183 COND_EXPR_STMT_LIST - statements needed to construct the conditional
2187 The returned value is the conditional expression to be used in the if
2188 statement that controls which version of the loop gets executed at runtime.
2192 vect_create_cond_for_alias_checks (loop_vec_info loop_vinfo,
2194 gimple_seq * cond_expr_stmt_list)
2196 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2197 VEC (ddr_p, heap) * may_alias_ddrs =
2198 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
2200 build_int_cst (integer_type_node, LOOP_VINFO_VECT_FACTOR (loop_vinfo));
2204 tree part_cond_expr;
2206 /* Create expression
2207 ((store_ptr_0 + store_segment_length_0) < load_ptr_0)
2208 || (load_ptr_0 + load_segment_length_0) < store_ptr_0))
2212 ((store_ptr_n + store_segment_length_n) < load_ptr_n)
2213 || (load_ptr_n + load_segment_length_n) < store_ptr_n)) */
2215 if (VEC_empty (ddr_p, may_alias_ddrs))
2218 for (i = 0; VEC_iterate (ddr_p, may_alias_ddrs, i, ddr); i++)
2220 struct data_reference *dr_a, *dr_b;
2221 gimple dr_group_first_a, dr_group_first_b;
2222 tree addr_base_a, addr_base_b;
2223 tree segment_length_a, segment_length_b;
2224 gimple stmt_a, stmt_b;
2227 stmt_a = DR_STMT (DDR_A (ddr));
2228 dr_group_first_a = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt_a));
2229 if (dr_group_first_a)
2231 stmt_a = dr_group_first_a;
2232 dr_a = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_a));
2236 stmt_b = DR_STMT (DDR_B (ddr));
2237 dr_group_first_b = DR_GROUP_FIRST_DR (vinfo_for_stmt (stmt_b));
2238 if (dr_group_first_b)
2240 stmt_b = dr_group_first_b;
2241 dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_b));
2245 vect_create_addr_base_for_vector_ref (stmt_a, cond_expr_stmt_list,
2248 vect_create_addr_base_for_vector_ref (stmt_b, cond_expr_stmt_list,
2251 segment_length_a = vect_vfa_segment_size (dr_a, vect_factor);
2252 segment_length_b = vect_vfa_segment_size (dr_b, vect_factor);
2254 if (vect_print_dump_info (REPORT_DR_DETAILS))
2257 "create runtime check for data references ");
2258 print_generic_expr (vect_dump, DR_REF (dr_a), TDF_SLIM);
2259 fprintf (vect_dump, " and ");
2260 print_generic_expr (vect_dump, DR_REF (dr_b), TDF_SLIM);
2265 fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
2266 fold_build2 (LT_EXPR, boolean_type_node,
2267 fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr_base_a),
2271 fold_build2 (LT_EXPR, boolean_type_node,
2272 fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (addr_base_b),
2278 *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2279 *cond_expr, part_cond_expr);
2281 *cond_expr = part_cond_expr;
2284 if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS))
2285 fprintf (vect_dump, "created %u versioning for alias checks.\n",
2286 VEC_length (ddr_p, may_alias_ddrs));
2290 /* Function vect_loop_versioning.
2292 If the loop has data references that may or may not be aligned or/and
2293 has data reference relations whose independence was not proven then
2294 two versions of the loop need to be generated, one which is vectorized
2295 and one which isn't. A test is then generated to control which of the
2296 loops is executed. The test checks for the alignment of all of the
2297 data references that may or may not be aligned. An additional
2298 sequence of runtime tests is generated for each pairs of DDRs whose
2299 independence was not proven. The vectorized version of loop is
2300 executed only if both alias and alignment tests are passed.
2302 The test generated to check which version of loop is executed
2303 is modified to also check for profitability as indicated by the
2304 cost model initially.
2306 The versioning precondition(s) are placed in *COND_EXPR and
2307 *COND_EXPR_STMT_LIST. If DO_VERSIONING is true versioning is
2308 also performed, otherwise only the conditions are generated. */
2311 vect_loop_versioning (loop_vec_info loop_vinfo, bool do_versioning,
2312 tree *cond_expr, gimple_seq *cond_expr_stmt_list)
2314 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2316 basic_block condition_bb;
2317 gimple_stmt_iterator gsi, cond_exp_gsi;
2318 basic_block merge_bb;
2319 basic_block new_exit_bb;
2321 gimple orig_phi, new_phi;
2323 unsigned prob = 4 * REG_BR_PROB_BASE / 5;
2324 gimple_seq gimplify_stmt_list = NULL;
2325 tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
2326 int min_profitable_iters = 0;
2329 /* Get profitability threshold for vectorized loop. */
2330 min_profitable_iters = LOOP_VINFO_COST_MODEL_MIN_ITERS (loop_vinfo);
2332 th = conservative_cost_threshold (loop_vinfo,
2333 min_profitable_iters);
2336 fold_build2 (GT_EXPR, boolean_type_node, scalar_loop_iters,
2337 build_int_cst (TREE_TYPE (scalar_loop_iters), th));
2339 *cond_expr = force_gimple_operand (*cond_expr, cond_expr_stmt_list,
2342 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
2343 vect_create_cond_for_align_checks (loop_vinfo, cond_expr,
2344 cond_expr_stmt_list);
2346 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2347 vect_create_cond_for_alias_checks (loop_vinfo, cond_expr,
2348 cond_expr_stmt_list);
2351 fold_build2 (NE_EXPR, boolean_type_node, *cond_expr, integer_zero_node);
2353 force_gimple_operand (*cond_expr, &gimplify_stmt_list, true, NULL_TREE);
2354 gimple_seq_add_seq (cond_expr_stmt_list, gimplify_stmt_list);
2356 /* If we only needed the extra conditions and a new loop copy
2361 initialize_original_copy_tables ();
2362 nloop = loop_version (loop, *cond_expr, &condition_bb,
2363 prob, prob, REG_BR_PROB_BASE - prob, true);
2364 free_original_copy_tables();
2366 /* Loop versioning violates an assumption we try to maintain during
2367 vectorization - that the loop exit block has a single predecessor.
2368 After versioning, the exit block of both loop versions is the same
2369 basic block (i.e. it has two predecessors). Just in order to simplify
2370 following transformations in the vectorizer, we fix this situation
2371 here by adding a new (empty) block on the exit-edge of the loop,
2372 with the proper loop-exit phis to maintain loop-closed-form. */
2374 merge_bb = single_exit (loop)->dest;
2375 gcc_assert (EDGE_COUNT (merge_bb->preds) == 2);
2376 new_exit_bb = split_edge (single_exit (loop));
2377 new_exit_e = single_exit (loop);
2378 e = EDGE_SUCC (new_exit_bb, 0);
2380 for (gsi = gsi_start_phis (merge_bb); !gsi_end_p (gsi); gsi_next (&gsi))
2382 orig_phi = gsi_stmt (gsi);
2383 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
2385 arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
2386 add_phi_arg (new_phi, arg, new_exit_e);
2387 SET_PHI_ARG_DEF (orig_phi, e->dest_idx, PHI_RESULT (new_phi));
2390 /* End loop-exit-fixes after versioning. */
2392 update_ssa (TODO_update_ssa);
2393 if (*cond_expr_stmt_list)
2395 cond_exp_gsi = gsi_last_bb (condition_bb);
2396 gsi_insert_seq_before (&cond_exp_gsi, *cond_expr_stmt_list,
2398 *cond_expr_stmt_list = NULL;
2400 *cond_expr = NULL_TREE;