1 /* Vectorizer Specific Loop Manipulations
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012
3 Free Software Foundation, Inc.
4 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 and Ira Rosen <irar@il.ibm.com>
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 "gimple-pretty-print.h"
31 #include "tree-flow.h"
32 #include "tree-pass.h"
34 #include "diagnostic-core.h"
35 #include "tree-scalar-evolution.h"
36 #include "tree-vectorizer.h"
37 #include "langhooks.h"
39 /*************************************************************************
40 Simple Loop Peeling Utilities
42 Utilities to support loop peeling for vectorization purposes.
43 *************************************************************************/
46 /* Renames the use *OP_P. */
49 rename_use_op (use_operand_p op_p)
53 if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
56 new_name = get_current_def (USE_FROM_PTR (op_p));
58 /* Something defined outside of the loop. */
62 /* An ordinary ssa name defined in the loop. */
64 SET_USE (op_p, new_name);
68 /* Renames the variables in basic block BB. */
71 rename_variables_in_bb (basic_block bb)
73 gimple_stmt_iterator gsi;
79 struct loop *loop = bb->loop_father;
81 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
83 stmt = gsi_stmt (gsi);
84 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
85 rename_use_op (use_p);
88 FOR_EACH_EDGE (e, ei, bb->succs)
90 if (!flow_bb_inside_loop_p (loop, e->dest))
92 for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
93 rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi), e));
98 /* Renames variables in new generated LOOP. */
101 rename_variables_in_loop (struct loop *loop)
106 bbs = get_loop_body (loop);
108 for (i = 0; i < loop->num_nodes; i++)
109 rename_variables_in_bb (bbs[i]);
120 DEF_VEC_O(adjust_info);
121 DEF_VEC_ALLOC_O_STACK(adjust_info);
122 #define VEC_adjust_info_stack_alloc(alloc) VEC_stack_alloc (adjust_info, alloc)
124 /* A stack of values to be adjusted in debug stmts. We have to
125 process them LIFO, so that the closest substitution applies. If we
126 processed them FIFO, without the stack, we might substitute uses
127 with a PHI DEF that would soon become non-dominant, and when we got
128 to the suitable one, it wouldn't have anything to substitute any
130 static VEC(adjust_info, stack) *adjust_vec;
132 /* Adjust any debug stmts that referenced AI->from values to use the
133 loop-closed AI->to, if the references are dominated by AI->bb and
134 not by the definition of AI->from. */
137 adjust_debug_stmts_now (adjust_info *ai)
139 basic_block bbphi = ai->bb;
140 tree orig_def = ai->from;
141 tree new_def = ai->to;
142 imm_use_iterator imm_iter;
144 basic_block bbdef = gimple_bb (SSA_NAME_DEF_STMT (orig_def));
146 gcc_assert (dom_info_available_p (CDI_DOMINATORS));
148 /* Adjust any debug stmts that held onto non-loop-closed
150 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, orig_def)
155 if (!is_gimple_debug (stmt))
158 gcc_assert (gimple_debug_bind_p (stmt));
160 bbuse = gimple_bb (stmt);
163 || dominated_by_p (CDI_DOMINATORS, bbuse, bbphi))
165 || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef)))
168 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
169 SET_USE (use_p, new_def);
172 gimple_debug_bind_reset_value (stmt);
179 /* Adjust debug stmts as scheduled before. */
182 adjust_vec_debug_stmts (void)
184 if (!MAY_HAVE_DEBUG_STMTS)
187 gcc_assert (adjust_vec);
189 while (!VEC_empty (adjust_info, adjust_vec))
191 adjust_debug_stmts_now (VEC_last (adjust_info, adjust_vec));
192 VEC_pop (adjust_info, adjust_vec);
195 VEC_free (adjust_info, stack, adjust_vec);
198 /* Adjust any debug stmts that referenced FROM values to use the
199 loop-closed TO, if the references are dominated by BB and not by
200 the definition of FROM. If adjust_vec is non-NULL, adjustments
201 will be postponed until adjust_vec_debug_stmts is called. */
204 adjust_debug_stmts (tree from, tree to, basic_block bb)
208 if (MAY_HAVE_DEBUG_STMTS && TREE_CODE (from) == SSA_NAME
209 && SSA_NAME_VAR (from) != gimple_vop (cfun))
216 VEC_safe_push (adjust_info, stack, adjust_vec, &ai);
218 adjust_debug_stmts_now (&ai);
222 /* Change E's phi arg in UPDATE_PHI to NEW_DEF, and record information
223 to adjust any debug stmts that referenced the old phi arg,
224 presumably non-loop-closed references left over from other
228 adjust_phi_and_debug_stmts (gimple update_phi, edge e, tree new_def)
230 tree orig_def = PHI_ARG_DEF_FROM_EDGE (update_phi, e);
232 SET_PHI_ARG_DEF (update_phi, e->dest_idx, new_def);
234 if (MAY_HAVE_DEBUG_STMTS)
235 adjust_debug_stmts (orig_def, PHI_RESULT (update_phi),
236 gimple_bb (update_phi));
240 /* Update the PHI nodes of NEW_LOOP.
242 NEW_LOOP is a duplicate of ORIG_LOOP.
243 AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
244 AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
245 executes before it. */
248 slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
249 struct loop *new_loop, bool after)
252 gimple phi_new, phi_orig;
254 edge orig_loop_latch = loop_latch_edge (orig_loop);
255 edge orig_entry_e = loop_preheader_edge (orig_loop);
256 edge new_loop_exit_e = single_exit (new_loop);
257 edge new_loop_entry_e = loop_preheader_edge (new_loop);
258 edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
259 gimple_stmt_iterator gsi_new, gsi_orig;
262 step 1. For each loop-header-phi:
263 Add the first phi argument for the phi in NEW_LOOP
264 (the one associated with the entry of NEW_LOOP)
266 step 2. For each loop-header-phi:
267 Add the second phi argument for the phi in NEW_LOOP
268 (the one associated with the latch of NEW_LOOP)
270 step 3. Update the phis in the successor block of NEW_LOOP.
272 case 1: NEW_LOOP was placed before ORIG_LOOP:
273 The successor block of NEW_LOOP is the header of ORIG_LOOP.
274 Updating the phis in the successor block can therefore be done
275 along with the scanning of the loop header phis, because the
276 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
277 phi nodes, organized in the same order.
279 case 2: NEW_LOOP was placed after ORIG_LOOP:
280 The successor block of NEW_LOOP is the original exit block of
281 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
282 We postpone updating these phis to a later stage (when
283 loop guards are added).
287 /* Scan the phis in the headers of the old and new loops
288 (they are organized in exactly the same order). */
290 for (gsi_new = gsi_start_phis (new_loop->header),
291 gsi_orig = gsi_start_phis (orig_loop->header);
292 !gsi_end_p (gsi_new) && !gsi_end_p (gsi_orig);
293 gsi_next (&gsi_new), gsi_next (&gsi_orig))
295 source_location locus;
296 phi_new = gsi_stmt (gsi_new);
297 phi_orig = gsi_stmt (gsi_orig);
300 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
301 locus = gimple_phi_arg_location_from_edge (phi_orig, entry_arg_e);
302 add_phi_arg (phi_new, def, new_loop_entry_e, locus);
305 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
306 locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
307 if (TREE_CODE (def) != SSA_NAME)
310 new_ssa_name = get_current_def (def);
313 /* This only happens if there are no definitions
314 inside the loop. use the phi_result in this case. */
315 new_ssa_name = PHI_RESULT (phi_new);
318 /* An ordinary ssa name defined in the loop. */
319 add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
321 /* Drop any debug references outside the loop, if they would
322 become ill-formed SSA. */
323 adjust_debug_stmts (def, NULL, single_exit (orig_loop)->dest);
325 /* step 3 (case 1). */
328 gcc_assert (new_loop_exit_e == orig_entry_e);
329 adjust_phi_and_debug_stmts (phi_orig, new_loop_exit_e, new_ssa_name);
335 /* Update PHI nodes for a guard of the LOOP.
338 - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
339 controls whether LOOP is to be executed. GUARD_EDGE is the edge that
340 originates from the guard-bb, skips LOOP and reaches the (unique) exit
341 bb of LOOP. This loop-exit-bb is an empty bb with one successor.
342 We denote this bb NEW_MERGE_BB because before the guard code was added
343 it had a single predecessor (the LOOP header), and now it became a merge
344 point of two paths - the path that ends with the LOOP exit-edge, and
345 the path that ends with GUARD_EDGE.
346 - NEW_EXIT_BB: New basic block that is added by this function between LOOP
347 and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
349 ===> The CFG before the guard-code was added:
352 if (exit_loop) goto update_bb
353 else goto LOOP_header_bb
356 ==> The CFG after the guard-code was added:
358 if (LOOP_guard_condition) goto new_merge_bb
359 else goto LOOP_header_bb
362 if (exit_loop_condition) goto new_merge_bb
363 else goto LOOP_header_bb
368 ==> The CFG after this function:
370 if (LOOP_guard_condition) goto new_merge_bb
371 else goto LOOP_header_bb
374 if (exit_loop_condition) goto new_exit_bb
375 else goto LOOP_header_bb
382 1. creates and updates the relevant phi nodes to account for the new
383 incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
384 1.1. Create phi nodes at NEW_MERGE_BB.
385 1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
386 UPDATE_BB). UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
387 2. preserves loop-closed-ssa-form by creating the required phi nodes
388 at the exit of LOOP (i.e, in NEW_EXIT_BB).
390 There are two flavors to this function:
392 slpeel_update_phi_nodes_for_guard1:
393 Here the guard controls whether we enter or skip LOOP, where LOOP is a
394 prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
395 for variables that have phis in the loop header.
397 slpeel_update_phi_nodes_for_guard2:
398 Here the guard controls whether we enter or skip LOOP, where LOOP is an
399 epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
400 for variables that have phis in the loop exit.
402 I.E., the overall structure is:
405 guard1 (goto loop1/merge1_bb)
408 guard2 (goto merge1_bb/merge2_bb)
415 slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
416 loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
417 that have phis in loop1->header).
419 slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
420 loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
421 that have phis in next_bb). It also adds some of these phis to
424 slpeel_update_phi_nodes_for_guard1 is always called before
425 slpeel_update_phi_nodes_for_guard2. They are both needed in order
426 to create correct data-flow and loop-closed-ssa-form.
428 Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
429 that change between iterations of a loop (and therefore have a phi-node
430 at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
431 phis for variables that are used out of the loop (and therefore have
432 loop-closed exit phis). Some variables may be both updated between
433 iterations and used after the loop. This is why in loop1_exit_bb we
434 may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
435 and exit phis (created by slpeel_update_phi_nodes_for_guard2).
437 - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
438 an original loop. i.e., we have:
441 guard_bb (goto LOOP/new_merge)
447 If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
451 guard_bb (goto LOOP/new_merge)
457 The SSA names defined in the original loop have a current
458 reaching definition that that records the corresponding new
459 ssa-name used in the new duplicated loop copy.
462 /* Function slpeel_update_phi_nodes_for_guard1
465 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
466 - DEFS - a bitmap of ssa names to mark new names for which we recorded
469 In the context of the overall structure, we have:
472 guard1 (goto loop1/merge1_bb)
475 guard2 (goto merge1_bb/merge2_bb)
482 For each name updated between loop iterations (i.e - for each name that has
483 an entry (loop-header) phi in LOOP) we create a new phi in:
484 1. merge1_bb (to account for the edge from guard1)
485 2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
489 slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
490 bool is_new_loop, basic_block *new_exit_bb)
492 gimple orig_phi, new_phi;
493 gimple update_phi, update_phi2;
494 tree guard_arg, loop_arg;
495 basic_block new_merge_bb = guard_edge->dest;
496 edge e = EDGE_SUCC (new_merge_bb, 0);
497 basic_block update_bb = e->dest;
498 basic_block orig_bb = loop->header;
500 tree current_new_name;
501 gimple_stmt_iterator gsi_orig, gsi_update;
503 /* Create new bb between loop and new_merge_bb. */
504 *new_exit_bb = split_edge (single_exit (loop));
506 new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
508 for (gsi_orig = gsi_start_phis (orig_bb),
509 gsi_update = gsi_start_phis (update_bb);
510 !gsi_end_p (gsi_orig) && !gsi_end_p (gsi_update);
511 gsi_next (&gsi_orig), gsi_next (&gsi_update))
513 source_location loop_locus, guard_locus;
514 orig_phi = gsi_stmt (gsi_orig);
515 update_phi = gsi_stmt (gsi_update);
517 /** 1. Handle new-merge-point phis **/
519 /* 1.1. Generate new phi node in NEW_MERGE_BB: */
520 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
523 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
524 of LOOP. Set the two phi args in NEW_PHI for these edges: */
525 loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
526 loop_locus = gimple_phi_arg_location_from_edge (orig_phi,
527 EDGE_SUCC (loop->latch,
529 guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
531 = gimple_phi_arg_location_from_edge (orig_phi,
532 loop_preheader_edge (loop));
534 add_phi_arg (new_phi, loop_arg, new_exit_e, loop_locus);
535 add_phi_arg (new_phi, guard_arg, guard_edge, guard_locus);
537 /* 1.3. Update phi in successor block. */
538 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
539 || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
540 adjust_phi_and_debug_stmts (update_phi, e, PHI_RESULT (new_phi));
541 update_phi2 = new_phi;
544 /** 2. Handle loop-closed-ssa-form phis **/
546 if (!is_gimple_reg (PHI_RESULT (orig_phi)))
549 /* 2.1. Generate new phi node in NEW_EXIT_BB: */
550 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
553 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
554 add_phi_arg (new_phi, loop_arg, single_exit (loop), loop_locus);
556 /* 2.3. Update phi in successor of NEW_EXIT_BB: */
557 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
558 adjust_phi_and_debug_stmts (update_phi2, new_exit_e,
559 PHI_RESULT (new_phi));
561 /* 2.4. Record the newly created name with set_current_def.
562 We want to find a name such that
563 name = get_current_def (orig_loop_name)
564 and to set its current definition as follows:
565 set_current_def (name, new_phi_name)
567 If LOOP is a new loop then loop_arg is already the name we're
568 looking for. If LOOP is the original loop, then loop_arg is
569 the orig_loop_name and the relevant name is recorded in its
570 current reaching definition. */
572 current_new_name = loop_arg;
575 current_new_name = get_current_def (loop_arg);
576 /* current_def is not available only if the variable does not
577 change inside the loop, in which case we also don't care
578 about recording a current_def for it because we won't be
579 trying to create loop-exit-phis for it. */
580 if (!current_new_name)
583 gcc_assert (get_current_def (current_new_name) == NULL_TREE);
585 set_current_def (current_new_name, PHI_RESULT (new_phi));
590 /* Function slpeel_update_phi_nodes_for_guard2
593 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
595 In the context of the overall structure, we have:
598 guard1 (goto loop1/merge1_bb)
601 guard2 (goto merge1_bb/merge2_bb)
608 For each name used out side the loop (i.e - for each name that has an exit
609 phi in next_bb) we create a new phi in:
610 1. merge2_bb (to account for the edge from guard_bb)
611 2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
612 3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
613 if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
617 slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
618 bool is_new_loop, basic_block *new_exit_bb)
620 gimple orig_phi, new_phi;
621 gimple update_phi, update_phi2;
622 tree guard_arg, loop_arg;
623 basic_block new_merge_bb = guard_edge->dest;
624 edge e = EDGE_SUCC (new_merge_bb, 0);
625 basic_block update_bb = e->dest;
627 tree orig_def, orig_def_new_name;
628 tree new_name, new_name2;
630 gimple_stmt_iterator gsi;
632 /* Create new bb between loop and new_merge_bb. */
633 *new_exit_bb = split_edge (single_exit (loop));
635 new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
637 for (gsi = gsi_start_phis (update_bb); !gsi_end_p (gsi); gsi_next (&gsi))
639 update_phi = gsi_stmt (gsi);
640 orig_phi = update_phi;
641 orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
642 /* This loop-closed-phi actually doesn't represent a use
643 out of the loop - the phi arg is a constant. */
644 if (TREE_CODE (orig_def) != SSA_NAME)
646 orig_def_new_name = get_current_def (orig_def);
649 /** 1. Handle new-merge-point phis **/
651 /* 1.1. Generate new phi node in NEW_MERGE_BB: */
652 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
655 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
656 of LOOP. Set the two PHI args in NEW_PHI for these edges: */
658 new_name2 = NULL_TREE;
659 if (orig_def_new_name)
661 new_name = orig_def_new_name;
662 /* Some variables have both loop-entry-phis and loop-exit-phis.
663 Such variables were given yet newer names by phis placed in
664 guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
665 new_name2 = get_current_def (get_current_def (orig_name)). */
666 new_name2 = get_current_def (new_name);
671 guard_arg = orig_def;
676 guard_arg = new_name;
680 guard_arg = new_name2;
682 add_phi_arg (new_phi, loop_arg, new_exit_e, UNKNOWN_LOCATION);
683 add_phi_arg (new_phi, guard_arg, guard_edge, UNKNOWN_LOCATION);
685 /* 1.3. Update phi in successor block. */
686 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
687 adjust_phi_and_debug_stmts (update_phi, e, PHI_RESULT (new_phi));
688 update_phi2 = new_phi;
691 /** 2. Handle loop-closed-ssa-form phis **/
693 /* 2.1. Generate new phi node in NEW_EXIT_BB: */
694 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
697 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
698 add_phi_arg (new_phi, loop_arg, single_exit (loop), UNKNOWN_LOCATION);
700 /* 2.3. Update phi in successor of NEW_EXIT_BB: */
701 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
702 adjust_phi_and_debug_stmts (update_phi2, new_exit_e,
703 PHI_RESULT (new_phi));
706 /** 3. Handle loop-closed-ssa-form phis for first loop **/
708 /* 3.1. Find the relevant names that need an exit-phi in
709 GUARD_BB, i.e. names for which
710 slpeel_update_phi_nodes_for_guard1 had not already created a
711 phi node. This is the case for names that are used outside
712 the loop (and therefore need an exit phi) but are not updated
713 across loop iterations (and therefore don't have a
716 slpeel_update_phi_nodes_for_guard1 is responsible for
717 creating loop-exit phis in GUARD_BB for names that have a
718 loop-header-phi. When such a phi is created we also record
719 the new name in its current definition. If this new name
720 exists, then guard_arg was set to this new name (see 1.2
721 above). Therefore, if guard_arg is not this new name, this
722 is an indication that an exit-phi in GUARD_BB was not yet
723 created, so we take care of it here. */
724 if (guard_arg == new_name2)
728 /* 3.2. Generate new phi node in GUARD_BB: */
729 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
732 /* 3.3. GUARD_BB has one incoming edge: */
733 gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
734 add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0),
737 /* 3.4. Update phi in successor of GUARD_BB: */
738 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
740 adjust_phi_and_debug_stmts (update_phi2, guard_edge,
741 PHI_RESULT (new_phi));
746 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
747 that starts at zero, increases by one and its limit is NITERS.
749 Assumption: the exit-condition of LOOP is the last stmt in the loop. */
752 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
754 tree indx_before_incr, indx_after_incr;
757 edge exit_edge = single_exit (loop);
758 gimple_stmt_iterator loop_cond_gsi;
759 gimple_stmt_iterator incr_gsi;
761 tree init = build_int_cst (TREE_TYPE (niters), 0);
762 tree step = build_int_cst (TREE_TYPE (niters), 1);
766 orig_cond = get_loop_exit_condition (loop);
767 gcc_assert (orig_cond);
768 loop_cond_gsi = gsi_for_stmt (orig_cond);
770 standard_iv_increment_position (loop, &incr_gsi, &insert_after);
771 create_iv (init, step, NULL_TREE, loop,
772 &incr_gsi, insert_after, &indx_before_incr, &indx_after_incr);
774 indx_after_incr = force_gimple_operand_gsi (&loop_cond_gsi, indx_after_incr,
775 true, NULL_TREE, true,
777 niters = force_gimple_operand_gsi (&loop_cond_gsi, niters, true, NULL_TREE,
778 true, GSI_SAME_STMT);
780 code = (exit_edge->flags & EDGE_TRUE_VALUE) ? GE_EXPR : LT_EXPR;
781 cond_stmt = gimple_build_cond (code, indx_after_incr, niters, NULL_TREE,
784 gsi_insert_before (&loop_cond_gsi, cond_stmt, GSI_SAME_STMT);
786 /* Remove old loop exit test: */
787 gsi_remove (&loop_cond_gsi, true);
789 loop_loc = find_loop_location (loop);
790 if (dump_file && (dump_flags & TDF_DETAILS))
792 if (loop_loc != UNKNOWN_LOC)
793 fprintf (dump_file, "\nloop at %s:%d: ",
794 LOC_FILE (loop_loc), LOC_LINE (loop_loc));
795 print_gimple_stmt (dump_file, cond_stmt, 0, TDF_SLIM);
798 loop->nb_iterations = niters;
802 /* Given LOOP this function generates a new copy of it and puts it
803 on E which is either the entry or exit of LOOP. */
806 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
808 struct loop *new_loop;
809 basic_block *new_bbs, *bbs;
812 basic_block exit_dest;
816 gimple_stmt_iterator gsi;
818 at_exit = (e == single_exit (loop));
819 if (!at_exit && e != loop_preheader_edge (loop))
822 bbs = get_loop_body (loop);
824 /* Check whether duplication is possible. */
825 if (!can_copy_bbs_p (bbs, loop->num_nodes))
831 /* Generate new loop structure. */
832 new_loop = duplicate_loop (loop, loop_outer (loop));
839 exit_dest = single_exit (loop)->dest;
840 was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
841 exit_dest) == loop->header ?
844 new_bbs = XNEWVEC (basic_block, loop->num_nodes);
846 exit = single_exit (loop);
847 copy_bbs (bbs, loop->num_nodes, new_bbs,
848 &exit, 1, &new_exit, NULL,
851 /* Duplicating phi args at exit bbs as coming
852 also from exit of duplicated loop. */
853 for (gsi = gsi_start_phis (exit_dest); !gsi_end_p (gsi); gsi_next (&gsi))
855 phi = gsi_stmt (gsi);
856 phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
859 edge new_loop_exit_edge;
860 source_location locus;
862 locus = gimple_phi_arg_location_from_edge (phi, single_exit (loop));
863 if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
864 new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
866 new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
868 add_phi_arg (phi, phi_arg, new_loop_exit_edge, locus);
872 if (at_exit) /* Add the loop copy at exit. */
874 redirect_edge_and_branch_force (e, new_loop->header);
875 PENDING_STMT (e) = NULL;
876 set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
878 set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
880 else /* Add the copy at entry. */
883 edge entry_e = loop_preheader_edge (loop);
884 basic_block preheader = entry_e->src;
886 if (!flow_bb_inside_loop_p (new_loop,
887 EDGE_SUCC (new_loop->header, 0)->dest))
888 new_exit_e = EDGE_SUCC (new_loop->header, 0);
890 new_exit_e = EDGE_SUCC (new_loop->header, 1);
892 redirect_edge_and_branch_force (new_exit_e, loop->header);
893 PENDING_STMT (new_exit_e) = NULL;
894 set_immediate_dominator (CDI_DOMINATORS, loop->header,
897 /* We have to add phi args to the loop->header here as coming
898 from new_exit_e edge. */
899 for (gsi = gsi_start_phis (loop->header);
903 phi = gsi_stmt (gsi);
904 phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
906 add_phi_arg (phi, phi_arg, new_exit_e,
907 gimple_phi_arg_location_from_edge (phi, entry_e));
910 redirect_edge_and_branch_force (entry_e, new_loop->header);
911 PENDING_STMT (entry_e) = NULL;
912 set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
922 /* Given the condition statement COND, put it as the last statement
923 of GUARD_BB; EXIT_BB is the basic block to skip the loop;
924 Assumes that this is the single exit of the guarded loop.
925 Returns the skip edge, inserts new stmts on the COND_EXPR_STMT_LIST. */
928 slpeel_add_loop_guard (basic_block guard_bb, tree cond,
929 gimple_seq cond_expr_stmt_list,
930 basic_block exit_bb, basic_block dom_bb)
932 gimple_stmt_iterator gsi;
935 gimple_seq gimplify_stmt_list = NULL;
937 enter_e = EDGE_SUCC (guard_bb, 0);
938 enter_e->flags &= ~EDGE_FALLTHRU;
939 enter_e->flags |= EDGE_FALSE_VALUE;
940 gsi = gsi_last_bb (guard_bb);
942 cond = force_gimple_operand_1 (cond, &gimplify_stmt_list, is_gimple_condexpr,
944 if (gimplify_stmt_list)
945 gimple_seq_add_seq (&cond_expr_stmt_list, gimplify_stmt_list);
946 cond_stmt = gimple_build_cond_from_tree (cond, NULL_TREE, NULL_TREE);
947 if (cond_expr_stmt_list)
948 gsi_insert_seq_after (&gsi, cond_expr_stmt_list, GSI_NEW_STMT);
950 gsi = gsi_last_bb (guard_bb);
951 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
953 /* Add new edge to connect guard block to the merge/loop-exit block. */
954 new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
955 set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
960 /* This function verifies that the following restrictions apply to LOOP:
962 (2) it consists of exactly 2 basic blocks - header, and an empty latch.
963 (3) it is single entry, single exit
964 (4) its exit condition is the last stmt in the header
965 (5) E is the entry/exit edge of LOOP.
969 slpeel_can_duplicate_loop_p (const struct loop *loop, const_edge e)
971 edge exit_e = single_exit (loop);
972 edge entry_e = loop_preheader_edge (loop);
973 gimple orig_cond = get_loop_exit_condition (loop);
974 gimple_stmt_iterator loop_exit_gsi = gsi_last_bb (exit_e->src);
976 if (need_ssa_update_p (cfun))
980 /* All loops have an outer scope; the only case loop->outer is NULL is for
981 the function itself. */
982 || !loop_outer (loop)
983 || loop->num_nodes != 2
984 || !empty_block_p (loop->latch)
985 || !single_exit (loop)
986 /* Verify that new loop exit condition can be trivially modified. */
987 || (!orig_cond || orig_cond != gsi_stmt (loop_exit_gsi))
988 || (e != exit_e && e != entry_e))
994 #ifdef ENABLE_CHECKING
996 slpeel_verify_cfg_after_peeling (struct loop *first_loop,
997 struct loop *second_loop)
999 basic_block loop1_exit_bb = single_exit (first_loop)->dest;
1000 basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
1001 basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
1003 /* A guard that controls whether the second_loop is to be executed or skipped
1004 is placed in first_loop->exit. first_loop->exit therefore has two
1005 successors - one is the preheader of second_loop, and the other is a bb
1008 gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
1010 /* 1. Verify that one of the successors of first_loop->exit is the preheader
1013 /* The preheader of new_loop is expected to have two predecessors:
1014 first_loop->exit and the block that precedes first_loop. */
1016 gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
1017 && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
1018 && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
1019 || (EDGE_PRED (loop2_entry_bb, 1)->src == loop1_exit_bb
1020 && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
1022 /* Verify that the other successor of first_loop->exit is after the
1028 /* If the run time cost model check determines that vectorization is
1029 not profitable and hence scalar loop should be generated then set
1030 FIRST_NITERS to prologue peeled iterations. This will allow all the
1031 iterations to be executed in the prologue peeled scalar loop. */
1034 set_prologue_iterations (basic_block bb_before_first_loop,
1040 basic_block cond_bb, then_bb;
1041 tree var, prologue_after_cost_adjust_name;
1042 gimple_stmt_iterator gsi;
1044 edge e_true, e_false, e_fallthru;
1046 gimple_seq stmts = NULL;
1047 tree cost_pre_condition = NULL_TREE;
1048 tree scalar_loop_iters =
1049 unshare_expr (LOOP_VINFO_NITERS_UNCHANGED (loop_vec_info_for_loop (loop)));
1051 e = single_pred_edge (bb_before_first_loop);
1052 cond_bb = split_edge(e);
1054 e = single_pred_edge (bb_before_first_loop);
1055 then_bb = split_edge(e);
1056 set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb);
1058 e_false = make_single_succ_edge (cond_bb, bb_before_first_loop,
1060 set_immediate_dominator (CDI_DOMINATORS, bb_before_first_loop, cond_bb);
1062 e_true = EDGE_PRED (then_bb, 0);
1063 e_true->flags &= ~EDGE_FALLTHRU;
1064 e_true->flags |= EDGE_TRUE_VALUE;
1066 e_fallthru = EDGE_SUCC (then_bb, 0);
1068 gsi = gsi_last_bb (cond_bb);
1069 cost_pre_condition =
1070 fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
1071 build_int_cst (TREE_TYPE (scalar_loop_iters), th));
1072 cost_pre_condition =
1073 force_gimple_operand_gsi_1 (&gsi, cost_pre_condition, is_gimple_condexpr,
1074 NULL_TREE, false, GSI_CONTINUE_LINKING);
1075 cond_stmt = gimple_build_cond_from_tree (cost_pre_condition,
1076 NULL_TREE, NULL_TREE);
1077 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
1079 var = create_tmp_var (TREE_TYPE (scalar_loop_iters),
1080 "prologue_after_cost_adjust");
1081 add_referenced_var (var);
1082 prologue_after_cost_adjust_name =
1083 force_gimple_operand (scalar_loop_iters, &stmts, false, var);
1085 gsi = gsi_last_bb (then_bb);
1087 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT);
1089 newphi = create_phi_node (var, bb_before_first_loop);
1090 add_phi_arg (newphi, prologue_after_cost_adjust_name, e_fallthru,
1092 add_phi_arg (newphi, *first_niters, e_false, UNKNOWN_LOCATION);
1094 *first_niters = PHI_RESULT (newphi);
1097 /* Function slpeel_tree_peel_loop_to_edge.
1099 Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
1100 that is placed on the entry (exit) edge E of LOOP. After this transformation
1101 we have two loops one after the other - first-loop iterates FIRST_NITERS
1102 times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
1103 If the cost model indicates that it is profitable to emit a scalar
1104 loop instead of the vector one, then the prolog (epilog) loop will iterate
1105 for the entire unchanged scalar iterations of the loop.
1108 - LOOP: the loop to be peeled.
1109 - E: the exit or entry edge of LOOP.
1110 If it is the entry edge, we peel the first iterations of LOOP. In this
1111 case first-loop is LOOP, and second-loop is the newly created loop.
1112 If it is the exit edge, we peel the last iterations of LOOP. In this
1113 case, first-loop is the newly created loop, and second-loop is LOOP.
1114 - NITERS: the number of iterations that LOOP iterates.
1115 - FIRST_NITERS: the number of iterations that the first-loop should iterate.
1116 - UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible
1117 for updating the loop bound of the first-loop to FIRST_NITERS. If it
1118 is false, the caller of this function may want to take care of this
1119 (this can be useful if we don't want new stmts added to first-loop).
1120 - TH: cost model profitability threshold of iterations for vectorization.
1121 - CHECK_PROFITABILITY: specify whether cost model check has not occurred
1122 during versioning and hence needs to occur during
1123 prologue generation or whether cost model check
1124 has not occurred during prologue generation and hence
1125 needs to occur during epilogue generation.
1129 The function returns a pointer to the new loop-copy, or NULL if it failed
1130 to perform the transformation.
1132 The function generates two if-then-else guards: one before the first loop,
1133 and the other before the second loop:
1135 if (FIRST_NITERS == 0) then skip the first loop,
1136 and go directly to the second loop.
1137 The second guard is:
1138 if (FIRST_NITERS == NITERS) then skip the second loop.
1140 If the optional COND_EXPR and COND_EXPR_STMT_LIST arguments are given
1141 then the generated condition is combined with COND_EXPR and the
1142 statements in COND_EXPR_STMT_LIST are emitted together with it.
1144 FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
1145 FORNOW the resulting code will not be in loop-closed-ssa form.
1149 slpeel_tree_peel_loop_to_edge (struct loop *loop,
1150 edge e, tree *first_niters,
1151 tree niters, bool update_first_loop_count,
1152 unsigned int th, bool check_profitability,
1153 tree cond_expr, gimple_seq cond_expr_stmt_list)
1155 struct loop *new_loop = NULL, *first_loop, *second_loop;
1157 tree pre_condition = NULL_TREE;
1158 basic_block bb_before_second_loop, bb_after_second_loop;
1159 basic_block bb_before_first_loop;
1160 basic_block bb_between_loops;
1161 basic_block new_exit_bb;
1162 gimple_stmt_iterator gsi;
1163 edge exit_e = single_exit (loop);
1165 tree cost_pre_condition = NULL_TREE;
1167 if (!slpeel_can_duplicate_loop_p (loop, e))
1170 /* If the loop has a virtual PHI, but exit bb doesn't, create a virtual PHI
1171 in the exit bb and rename all the uses after the loop. This simplifies
1172 the *guard[12] routines, which assume loop closed SSA form for all PHIs
1173 (but normally loop closed SSA form doesn't require virtual PHIs to be
1174 in the same form). Doing this early simplifies the checking what
1175 uses should be renamed. */
1176 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1177 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1179 gimple phi = gsi_stmt (gsi);
1180 for (gsi = gsi_start_phis (exit_e->dest);
1181 !gsi_end_p (gsi); gsi_next (&gsi))
1182 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
1184 if (gsi_end_p (gsi))
1186 gimple new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (phi)),
1188 tree vop = PHI_ARG_DEF_FROM_EDGE (phi, EDGE_SUCC (loop->latch, 0));
1189 imm_use_iterator imm_iter;
1191 tree new_vop = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)),
1193 use_operand_p use_p;
1195 add_phi_arg (new_phi, vop, exit_e, UNKNOWN_LOCATION);
1196 gimple_phi_set_result (new_phi, new_vop);
1197 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, vop)
1198 if (stmt != new_phi && gimple_bb (stmt) != loop->header)
1199 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1200 SET_USE (use_p, new_vop);
1205 /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1206 Resulting CFG would be:
1219 if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e)))
1221 loop_loc = find_loop_location (loop);
1222 if (dump_file && (dump_flags & TDF_DETAILS))
1224 if (loop_loc != UNKNOWN_LOC)
1225 fprintf (dump_file, "\n%s:%d: note: ",
1226 LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1227 fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
1232 if (MAY_HAVE_DEBUG_STMTS)
1234 gcc_assert (!adjust_vec);
1235 adjust_vec = VEC_alloc (adjust_info, stack, 32);
1240 /* NEW_LOOP was placed after LOOP. */
1242 second_loop = new_loop;
1246 /* NEW_LOOP was placed before LOOP. */
1247 first_loop = new_loop;
1251 slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
1252 rename_variables_in_loop (new_loop);
1255 /* 2. Add the guard code in one of the following ways:
1257 2.a Add the guard that controls whether the first loop is executed.
1258 This occurs when this function is invoked for prologue or epilogue
1259 generation and when the cost model check can be done at compile time.
1261 Resulting CFG would be:
1263 bb_before_first_loop:
1264 if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1271 bb_before_second_loop:
1279 2.b Add the cost model check that allows the prologue
1280 to iterate for the entire unchanged scalar
1281 iterations of the loop in the event that the cost
1282 model indicates that the scalar loop is more
1283 profitable than the vector one. This occurs when
1284 this function is invoked for prologue generation
1285 and the cost model check needs to be done at run
1288 Resulting CFG after prologue peeling would be:
1290 if (scalar_loop_iterations <= th)
1291 FIRST_NITERS = scalar_loop_iterations
1293 bb_before_first_loop:
1294 if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1301 bb_before_second_loop:
1309 2.c Add the cost model check that allows the epilogue
1310 to iterate for the entire unchanged scalar
1311 iterations of the loop in the event that the cost
1312 model indicates that the scalar loop is more
1313 profitable than the vector one. This occurs when
1314 this function is invoked for epilogue generation
1315 and the cost model check needs to be done at run
1316 time. This check is combined with any pre-existing
1317 check in COND_EXPR to avoid versioning.
1319 Resulting CFG after prologue peeling would be:
1321 bb_before_first_loop:
1322 if ((scalar_loop_iterations <= th)
1324 FIRST_NITERS == 0) GOTO bb_before_second_loop
1331 bb_before_second_loop:
1340 bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
1341 bb_before_second_loop = split_edge (single_exit (first_loop));
1343 /* Epilogue peeling. */
1344 if (!update_first_loop_count)
1347 fold_build2 (LE_EXPR, boolean_type_node, *first_niters,
1348 build_int_cst (TREE_TYPE (*first_niters), 0));
1349 if (check_profitability)
1351 tree scalar_loop_iters
1352 = unshare_expr (LOOP_VINFO_NITERS_UNCHANGED
1353 (loop_vec_info_for_loop (loop)));
1354 cost_pre_condition =
1355 fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
1356 build_int_cst (TREE_TYPE (scalar_loop_iters), th));
1358 pre_condition = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1359 cost_pre_condition, pre_condition);
1364 fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1366 fold_build1 (TRUTH_NOT_EXPR, boolean_type_node,
1371 /* Prologue peeling. */
1374 if (check_profitability)
1375 set_prologue_iterations (bb_before_first_loop, first_niters,
1379 fold_build2 (LE_EXPR, boolean_type_node, *first_niters,
1380 build_int_cst (TREE_TYPE (*first_niters), 0));
1383 skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
1384 cond_expr_stmt_list,
1385 bb_before_second_loop, bb_before_first_loop);
1386 slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
1387 first_loop == new_loop,
1391 /* 3. Add the guard that controls whether the second loop is executed.
1392 Resulting CFG would be:
1394 bb_before_first_loop:
1395 if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1403 if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1404 GOTO bb_before_second_loop
1406 bb_before_second_loop:
1412 bb_after_second_loop:
1417 bb_between_loops = new_exit_bb;
1418 bb_after_second_loop = split_edge (single_exit (second_loop));
1421 fold_build2 (EQ_EXPR, boolean_type_node, *first_niters, niters);
1422 skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition, NULL,
1423 bb_after_second_loop, bb_before_first_loop);
1424 slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
1425 second_loop == new_loop, &new_exit_bb);
1427 /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1429 if (update_first_loop_count)
1430 slpeel_make_loop_iterate_ntimes (first_loop, *first_niters);
1432 delete_update_ssa ();
1434 adjust_vec_debug_stmts ();
1439 /* Function vect_get_loop_location.
1441 Extract the location of the loop in the source code.
1442 If the loop is not well formed for vectorization, an estimated
1443 location is calculated.
1444 Return the loop location if succeed and NULL if not. */
1447 find_loop_location (struct loop *loop)
1451 gimple_stmt_iterator si;
1456 stmt = get_loop_exit_condition (loop);
1458 if (stmt && gimple_location (stmt) != UNKNOWN_LOC)
1459 return gimple_location (stmt);
1461 /* If we got here the loop is probably not "well formed",
1462 try to estimate the loop location */
1469 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
1471 stmt = gsi_stmt (si);
1472 if (gimple_location (stmt) != UNKNOWN_LOC)
1473 return gimple_location (stmt);
1480 /* This function builds ni_name = number of iterations loop executes
1481 on the loop preheader. If SEQ is given the stmt is instead emitted
1485 vect_build_loop_niters (loop_vec_info loop_vinfo, gimple_seq seq)
1488 gimple_seq stmts = NULL;
1490 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1491 tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
1493 var = create_tmp_var (TREE_TYPE (ni), "niters");
1494 add_referenced_var (var);
1495 ni_name = force_gimple_operand (ni, &stmts, false, var);
1497 pe = loop_preheader_edge (loop);
1501 gimple_seq_add_seq (&seq, stmts);
1504 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1505 gcc_assert (!new_bb);
1513 /* This function generates the following statements:
1515 ni_name = number of iterations loop executes
1516 ratio = ni_name / vf
1517 ratio_mult_vf_name = ratio * vf
1519 and places them at the loop preheader edge or in COND_EXPR_STMT_LIST
1520 if that is non-NULL. */
1523 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
1525 tree *ratio_mult_vf_name_ptr,
1526 tree *ratio_name_ptr,
1527 gimple_seq cond_expr_stmt_list)
1533 tree ni_name, ni_minus_gap_name;
1536 tree ratio_mult_vf_name;
1537 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1538 tree ni = LOOP_VINFO_NITERS (loop_vinfo);
1539 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1542 pe = loop_preheader_edge (loop);
1544 /* Generate temporary variable that contains
1545 number of iterations loop executes. */
1547 ni_name = vect_build_loop_niters (loop_vinfo, cond_expr_stmt_list);
1548 log_vf = build_int_cst (TREE_TYPE (ni), exact_log2 (vf));
1550 /* If epilogue loop is required because of data accesses with gaps, we
1551 subtract one iteration from the total number of iterations here for
1552 correct calculation of RATIO. */
1553 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo))
1555 ni_minus_gap_name = fold_build2 (MINUS_EXPR, TREE_TYPE (ni_name),
1557 build_one_cst (TREE_TYPE (ni_name)));
1558 if (!is_gimple_val (ni_minus_gap_name))
1560 var = create_tmp_var (TREE_TYPE (ni), "ni_gap");
1561 add_referenced_var (var);
1564 ni_minus_gap_name = force_gimple_operand (ni_minus_gap_name, &stmts,
1566 if (cond_expr_stmt_list)
1567 gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
1570 pe = loop_preheader_edge (loop);
1571 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1572 gcc_assert (!new_bb);
1577 ni_minus_gap_name = ni_name;
1579 /* Create: ratio = ni >> log2(vf) */
1581 ratio_name = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ni_minus_gap_name),
1582 ni_minus_gap_name, log_vf);
1583 if (!is_gimple_val (ratio_name))
1585 var = create_tmp_var (TREE_TYPE (ni), "bnd");
1586 add_referenced_var (var);
1589 ratio_name = force_gimple_operand (ratio_name, &stmts, true, var);
1590 if (cond_expr_stmt_list)
1591 gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
1594 pe = loop_preheader_edge (loop);
1595 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1596 gcc_assert (!new_bb);
1600 /* Create: ratio_mult_vf = ratio << log2 (vf). */
1602 ratio_mult_vf_name = fold_build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name),
1603 ratio_name, log_vf);
1604 if (!is_gimple_val (ratio_mult_vf_name))
1606 var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
1607 add_referenced_var (var);
1610 ratio_mult_vf_name = force_gimple_operand (ratio_mult_vf_name, &stmts,
1612 if (cond_expr_stmt_list)
1613 gimple_seq_add_seq (&cond_expr_stmt_list, stmts);
1616 pe = loop_preheader_edge (loop);
1617 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
1618 gcc_assert (!new_bb);
1622 *ni_name_ptr = ni_name;
1623 *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
1624 *ratio_name_ptr = ratio_name;
1629 /* Function vect_can_advance_ivs_p
1631 In case the number of iterations that LOOP iterates is unknown at compile
1632 time, an epilog loop will be generated, and the loop induction variables
1633 (IVs) will be "advanced" to the value they are supposed to take just before
1634 the epilog loop. Here we check that the access function of the loop IVs
1635 and the expression that represents the loop bound are simple enough.
1636 These restrictions will be relaxed in the future. */
1639 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
1641 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1642 basic_block bb = loop->header;
1644 gimple_stmt_iterator gsi;
1646 /* Analyze phi functions of the loop header. */
1648 if (vect_print_dump_info (REPORT_DETAILS))
1649 fprintf (vect_dump, "vect_can_advance_ivs_p:");
1651 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1653 tree access_fn = NULL;
1654 tree evolution_part;
1656 phi = gsi_stmt (gsi);
1657 if (vect_print_dump_info (REPORT_DETAILS))
1659 fprintf (vect_dump, "Analyze phi: ");
1660 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1663 /* Skip virtual phi's. The data dependences that are associated with
1664 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
1666 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1668 if (vect_print_dump_info (REPORT_DETAILS))
1669 fprintf (vect_dump, "virtual phi. skip.");
1673 /* Skip reduction phis. */
1675 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
1677 if (vect_print_dump_info (REPORT_DETAILS))
1678 fprintf (vect_dump, "reduc phi. skip.");
1682 /* Analyze the evolution function. */
1684 access_fn = instantiate_parameters
1685 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
1689 if (vect_print_dump_info (REPORT_DETAILS))
1690 fprintf (vect_dump, "No Access function.");
1694 if (vect_print_dump_info (REPORT_DETAILS))
1696 fprintf (vect_dump, "Access function of PHI: ");
1697 print_generic_expr (vect_dump, access_fn, TDF_SLIM);
1700 evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
1702 if (evolution_part == NULL_TREE)
1704 if (vect_print_dump_info (REPORT_DETAILS))
1705 fprintf (vect_dump, "No evolution.");
1709 /* FORNOW: We do not transform initial conditions of IVs
1710 which evolution functions are a polynomial of degree >= 2. */
1712 if (tree_is_chrec (evolution_part))
1720 /* Function vect_update_ivs_after_vectorizer.
1722 "Advance" the induction variables of LOOP to the value they should take
1723 after the execution of LOOP. This is currently necessary because the
1724 vectorizer does not handle induction variables that are used after the
1725 loop. Such a situation occurs when the last iterations of LOOP are
1727 1. We introduced new uses after LOOP for IVs that were not originally used
1728 after LOOP: the IVs of LOOP are now used by an epilog loop.
1729 2. LOOP is going to be vectorized; this means that it will iterate N/VF
1730 times, whereas the loop IVs should be bumped N times.
1733 - LOOP - a loop that is going to be vectorized. The last few iterations
1734 of LOOP were peeled.
1735 - NITERS - the number of iterations that LOOP executes (before it is
1736 vectorized). i.e, the number of times the ivs should be bumped.
1737 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
1738 coming out from LOOP on which there are uses of the LOOP ivs
1739 (this is the path from LOOP->exit to epilog_loop->preheader).
1741 The new definitions of the ivs are placed in LOOP->exit.
1742 The phi args associated with the edge UPDATE_E in the bb
1743 UPDATE_E->dest are updated accordingly.
1745 Assumption 1: Like the rest of the vectorizer, this function assumes
1746 a single loop exit that has a single predecessor.
1748 Assumption 2: The phi nodes in the LOOP header and in update_bb are
1749 organized in the same order.
1751 Assumption 3: The access function of the ivs is simple enough (see
1752 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
1754 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
1755 coming out of LOOP on which the ivs of LOOP are used (this is the path
1756 that leads to the epilog loop; other paths skip the epilog loop). This
1757 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
1758 needs to have its phis updated.
1762 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
1765 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1766 basic_block exit_bb = single_exit (loop)->dest;
1768 gimple_stmt_iterator gsi, gsi1;
1769 basic_block update_bb = update_e->dest;
1771 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
1773 /* Make sure there exists a single-predecessor exit bb: */
1774 gcc_assert (single_pred_p (exit_bb));
1776 for (gsi = gsi_start_phis (loop->header), gsi1 = gsi_start_phis (update_bb);
1777 !gsi_end_p (gsi) && !gsi_end_p (gsi1);
1778 gsi_next (&gsi), gsi_next (&gsi1))
1781 tree step_expr, off;
1783 tree var, ni, ni_name;
1784 gimple_stmt_iterator last_gsi;
1785 stmt_vec_info stmt_info;
1787 phi = gsi_stmt (gsi);
1788 phi1 = gsi_stmt (gsi1);
1789 if (vect_print_dump_info (REPORT_DETAILS))
1791 fprintf (vect_dump, "vect_update_ivs_after_vectorizer: phi: ");
1792 print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
1795 /* Skip virtual phi's. */
1796 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1798 if (vect_print_dump_info (REPORT_DETAILS))
1799 fprintf (vect_dump, "virtual phi. skip.");
1803 /* Skip reduction phis. */
1804 stmt_info = vinfo_for_stmt (phi);
1805 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def)
1807 if (vect_print_dump_info (REPORT_DETAILS))
1808 fprintf (vect_dump, "reduc phi. skip.");
1812 type = TREE_TYPE (gimple_phi_result (phi));
1813 step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info);
1814 step_expr = unshare_expr (step_expr);
1816 /* FORNOW: We do not support IVs whose evolution function is a polynomial
1817 of degree >= 2 or exponential. */
1818 gcc_assert (!tree_is_chrec (step_expr));
1820 init_expr = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1822 off = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr),
1823 fold_convert (TREE_TYPE (step_expr), niters),
1825 if (POINTER_TYPE_P (type))
1826 ni = fold_build_pointer_plus (init_expr, off);
1828 ni = fold_build2 (PLUS_EXPR, type,
1829 init_expr, fold_convert (type, off));
1831 var = create_tmp_var (type, "tmp");
1832 add_referenced_var (var);
1834 last_gsi = gsi_last_bb (exit_bb);
1835 ni_name = force_gimple_operand_gsi (&last_gsi, ni, false, var,
1836 true, GSI_SAME_STMT);
1838 /* Fix phi expressions in the successor bb. */
1839 adjust_phi_and_debug_stmts (phi1, update_e, ni_name);
1843 /* Function vect_do_peeling_for_loop_bound
1845 Peel the last iterations of the loop represented by LOOP_VINFO.
1846 The peeled iterations form a new epilog loop. Given that the loop now
1847 iterates NITERS times, the new epilog loop iterates
1848 NITERS % VECTORIZATION_FACTOR times.
1850 The original loop will later be made to iterate
1851 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).
1853 COND_EXPR and COND_EXPR_STMT_LIST are combined with a new generated
1857 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio,
1858 unsigned int th, bool check_profitability)
1860 tree ni_name, ratio_mult_vf_name;
1861 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1862 struct loop *new_loop;
1864 basic_block preheader;
1867 tree cond_expr = NULL_TREE;
1868 gimple_seq cond_expr_stmt_list = NULL;
1870 if (vect_print_dump_info (REPORT_DETAILS))
1871 fprintf (vect_dump, "=== vect_do_peeling_for_loop_bound ===");
1873 initialize_original_copy_tables ();
1875 /* Generate the following variables on the preheader of original loop:
1877 ni_name = number of iteration the original loop executes
1878 ratio = ni_name / vf
1879 ratio_mult_vf_name = ratio * vf */
1880 vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
1881 &ratio_mult_vf_name, ratio,
1882 cond_expr_stmt_list);
1884 loop_num = loop->num;
1886 new_loop = slpeel_tree_peel_loop_to_edge (loop, single_exit (loop),
1887 &ratio_mult_vf_name, ni_name, false,
1888 th, check_profitability,
1889 cond_expr, cond_expr_stmt_list);
1890 gcc_assert (new_loop);
1891 gcc_assert (loop_num == loop->num);
1892 #ifdef ENABLE_CHECKING
1893 slpeel_verify_cfg_after_peeling (loop, new_loop);
1896 /* A guard that controls whether the new_loop is to be executed or skipped
1897 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
1898 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
1899 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
1900 is on the path where the LOOP IVs are used and need to be updated. */
1902 preheader = loop_preheader_edge (new_loop)->src;
1903 if (EDGE_PRED (preheader, 0)->src == single_exit (loop)->dest)
1904 update_e = EDGE_PRED (preheader, 0);
1906 update_e = EDGE_PRED (preheader, 1);
1908 /* Update IVs of original loop as if they were advanced
1909 by ratio_mult_vf_name steps. */
1910 vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e);
1912 max_iter = LOOP_VINFO_VECT_FACTOR (loop_vinfo) - 1;
1913 if (check_profitability)
1914 max_iter = MAX (max_iter, (int) th);
1915 record_niter_bound (new_loop, shwi_to_double_int (max_iter), false, true);
1916 if (dump_file && (dump_flags & TDF_DETAILS))
1917 fprintf (dump_file, "Setting upper bound of nb iterations for epilogue "
1918 "loop to %d\n", max_iter);
1920 /* After peeling we have to reset scalar evolution analyzer. */
1923 free_original_copy_tables ();
1927 /* Function vect_gen_niters_for_prolog_loop
1929 Set the number of iterations for the loop represented by LOOP_VINFO
1930 to the minimum between LOOP_NITERS (the original iteration count of the loop)
1931 and the misalignment of DR - the data reference recorded in
1932 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
1933 this loop, the data reference DR will refer to an aligned location.
1935 The following computation is generated:
1937 If the misalignment of DR is known at compile time:
1938 addr_mis = int mis = DR_MISALIGNMENT (dr);
1939 Else, compute address misalignment in bytes:
1940 addr_mis = addr & (vectype_size - 1)
1942 prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
1944 (elem_size = element type size; an element is the scalar element whose type
1945 is the inner type of the vectype)
1947 When the step of the data-ref in the loop is not 1 (as in interleaved data
1948 and SLP), the number of iterations of the prolog must be divided by the step
1949 (which is equal to the size of interleaved group).
1951 The above formulas assume that VF == number of elements in the vector. This
1952 may not hold when there are multiple-types in the loop.
1953 In this case, for some data-references in the loop the VF does not represent
1954 the number of elements that fit in the vector. Therefore, instead of VF we
1955 use TYPE_VECTOR_SUBPARTS. */
1958 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters)
1960 struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
1961 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1964 tree iters, iters_name;
1967 gimple dr_stmt = DR_STMT (dr);
1968 stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt);
1969 tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1970 int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT;
1971 tree niters_type = TREE_TYPE (loop_niters);
1972 int nelements = TYPE_VECTOR_SUBPARTS (vectype);
1974 pe = loop_preheader_edge (loop);
1976 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
1978 int npeel = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
1980 if (vect_print_dump_info (REPORT_DETAILS))
1981 fprintf (vect_dump, "known peeling = %d.", npeel);
1983 iters = build_int_cst (niters_type, npeel);
1987 gimple_seq new_stmts = NULL;
1988 bool negative = tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0;
1989 tree offset = negative
1990 ? size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1) : NULL_TREE;
1991 tree start_addr = vect_create_addr_base_for_vector_ref (dr_stmt,
1992 &new_stmts, offset, loop);
1993 tree type = unsigned_type_for (TREE_TYPE (start_addr));
1994 tree vectype_size_minus_1 = build_int_cst (type, vectype_align - 1);
1995 tree elem_size_log =
1996 build_int_cst (type, exact_log2 (vectype_align/nelements));
1997 tree nelements_minus_1 = build_int_cst (type, nelements - 1);
1998 tree nelements_tree = build_int_cst (type, nelements);
2002 new_bb = gsi_insert_seq_on_edge_immediate (pe, new_stmts);
2003 gcc_assert (!new_bb);
2005 /* Create: byte_misalign = addr & (vectype_size - 1) */
2007 fold_build2 (BIT_AND_EXPR, type, fold_convert (type, start_addr),
2008 vectype_size_minus_1);
2010 /* Create: elem_misalign = byte_misalign / element_size */
2012 fold_build2 (RSHIFT_EXPR, type, byte_misalign, elem_size_log);
2014 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
2016 iters = fold_build2 (MINUS_EXPR, type, elem_misalign, nelements_tree);
2018 iters = fold_build2 (MINUS_EXPR, type, nelements_tree, elem_misalign);
2019 iters = fold_build2 (BIT_AND_EXPR, type, iters, nelements_minus_1);
2020 iters = fold_convert (niters_type, iters);
2023 /* Create: prolog_loop_niters = min (iters, loop_niters) */
2024 /* If the loop bound is known at compile time we already verified that it is
2025 greater than vf; since the misalignment ('iters') is at most vf, there's
2026 no need to generate the MIN_EXPR in this case. */
2027 if (TREE_CODE (loop_niters) != INTEGER_CST)
2028 iters = fold_build2 (MIN_EXPR, niters_type, iters, loop_niters);
2030 if (vect_print_dump_info (REPORT_DETAILS))
2032 fprintf (vect_dump, "niters for prolog loop: ");
2033 print_generic_expr (vect_dump, iters, TDF_SLIM);
2036 var = create_tmp_var (niters_type, "prolog_loop_niters");
2037 add_referenced_var (var);
2039 iters_name = force_gimple_operand (iters, &stmts, false, var);
2041 /* Insert stmt on loop preheader edge. */
2044 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts);
2045 gcc_assert (!new_bb);
2052 /* Function vect_update_init_of_dr
2054 NITERS iterations were peeled from LOOP. DR represents a data reference
2055 in LOOP. This function updates the information recorded in DR to
2056 account for the fact that the first NITERS iterations had already been
2057 executed. Specifically, it updates the OFFSET field of DR. */
2060 vect_update_init_of_dr (struct data_reference *dr, tree niters)
2062 tree offset = DR_OFFSET (dr);
2064 niters = fold_build2 (MULT_EXPR, sizetype,
2065 fold_convert (sizetype, niters),
2066 fold_convert (sizetype, DR_STEP (dr)));
2067 offset = fold_build2 (PLUS_EXPR, sizetype,
2068 fold_convert (sizetype, offset), niters);
2069 DR_OFFSET (dr) = offset;
2073 /* Function vect_update_inits_of_drs
2075 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
2076 This function updates the information recorded for the data references in
2077 the loop to account for the fact that the first NITERS iterations had
2078 already been executed. Specifically, it updates the initial_condition of
2079 the access_function of all the data_references in the loop. */
2082 vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters)
2085 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2086 struct data_reference *dr;
2088 if (vect_print_dump_info (REPORT_DETAILS))
2089 fprintf (vect_dump, "=== vect_update_inits_of_dr ===");
2091 FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
2092 vect_update_init_of_dr (dr, niters);
2096 /* Function vect_do_peeling_for_alignment
2098 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
2099 'niters' is set to the misalignment of one of the data references in the
2100 loop, thereby forcing it to refer to an aligned location at the beginning
2101 of the execution of this loop. The data reference for which we are
2102 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
2105 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo,
2106 unsigned int th, bool check_profitability)
2108 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2109 tree niters_of_prolog_loop, ni_name;
2111 tree wide_prolog_niters;
2112 struct loop *new_loop;
2115 if (vect_print_dump_info (REPORT_DETAILS))
2116 fprintf (vect_dump, "=== vect_do_peeling_for_alignment ===");
2118 initialize_original_copy_tables ();
2120 ni_name = vect_build_loop_niters (loop_vinfo, NULL);
2121 niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo,
2124 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
2126 slpeel_tree_peel_loop_to_edge (loop, loop_preheader_edge (loop),
2127 &niters_of_prolog_loop, ni_name, true,
2128 th, check_profitability, NULL_TREE, NULL);
2130 gcc_assert (new_loop);
2131 #ifdef ENABLE_CHECKING
2132 slpeel_verify_cfg_after_peeling (new_loop, loop);
2134 max_iter = LOOP_VINFO_VECT_FACTOR (loop_vinfo) - 1;
2135 if (check_profitability)
2136 max_iter = MAX (max_iter, (int) th);
2137 record_niter_bound (new_loop, shwi_to_double_int (max_iter), false, true);
2138 if (dump_file && (dump_flags & TDF_DETAILS))
2139 fprintf (dump_file, "Setting upper bound of nb iterations for prologue "
2140 "loop to %d\n", max_iter);
2142 /* Update number of times loop executes. */
2143 n_iters = LOOP_VINFO_NITERS (loop_vinfo);
2144 LOOP_VINFO_NITERS (loop_vinfo) = fold_build2 (MINUS_EXPR,
2145 TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop);
2147 if (types_compatible_p (sizetype, TREE_TYPE (niters_of_prolog_loop)))
2148 wide_prolog_niters = niters_of_prolog_loop;
2151 gimple_seq seq = NULL;
2152 edge pe = loop_preheader_edge (loop);
2153 tree wide_iters = fold_convert (sizetype, niters_of_prolog_loop);
2154 tree var = create_tmp_var (sizetype, "prolog_loop_adjusted_niters");
2155 add_referenced_var (var);
2156 wide_prolog_niters = force_gimple_operand (wide_iters, &seq, false,
2160 /* Insert stmt on loop preheader edge. */
2161 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
2162 gcc_assert (!new_bb);
2166 /* Update the init conditions of the access functions of all data refs. */
2167 vect_update_inits_of_drs (loop_vinfo, wide_prolog_niters);
2169 /* After peeling we have to reset scalar evolution analyzer. */
2172 free_original_copy_tables ();
2176 /* Function vect_create_cond_for_align_checks.
2178 Create a conditional expression that represents the alignment checks for
2179 all of data references (array element references) whose alignment must be
2183 COND_EXPR - input conditional expression. New conditions will be chained
2184 with logical AND operation.
2185 LOOP_VINFO - two fields of the loop information are used.
2186 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
2187 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
2190 COND_EXPR_STMT_LIST - statements needed to construct the conditional
2192 The returned value is the conditional expression to be used in the if
2193 statement that controls which version of the loop gets executed at runtime.
2195 The algorithm makes two assumptions:
2196 1) The number of bytes "n" in a vector is a power of 2.
2197 2) An address "a" is aligned if a%n is zero and that this
2198 test can be done as a&(n-1) == 0. For example, for 16
2199 byte vectors the test is a&0xf == 0. */
2202 vect_create_cond_for_align_checks (loop_vec_info loop_vinfo,
2204 gimple_seq *cond_expr_stmt_list)
2206 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2207 VEC(gimple,heap) *may_misalign_stmts
2208 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
2210 int mask = LOOP_VINFO_PTR_MASK (loop_vinfo);
2213 tree int_ptrsize_type;
2215 tree or_tmp_name = NULL_TREE;
2216 tree and_tmp, and_tmp_name;
2219 tree part_cond_expr;
2221 /* Check that mask is one less than a power of 2, i.e., mask is
2222 all zeros followed by all ones. */
2223 gcc_assert ((mask != 0) && ((mask & (mask+1)) == 0));
2225 int_ptrsize_type = signed_type_for (ptr_type_node);
2227 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
2228 of the first vector of the i'th data reference. */
2230 FOR_EACH_VEC_ELT (gimple, may_misalign_stmts, i, ref_stmt)
2232 gimple_seq new_stmt_list = NULL;
2234 tree addr_tmp, addr_tmp_name;
2235 tree or_tmp, new_or_tmp_name;
2236 gimple addr_stmt, or_stmt;
2237 stmt_vec_info stmt_vinfo = vinfo_for_stmt (ref_stmt);
2238 tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
2239 bool negative = tree_int_cst_compare
2240 (DR_STEP (STMT_VINFO_DATA_REF (stmt_vinfo)), size_zero_node) < 0;
2241 tree offset = negative
2242 ? size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1) : NULL_TREE;
2244 /* create: addr_tmp = (int)(address_of_first_vector) */
2246 vect_create_addr_base_for_vector_ref (ref_stmt, &new_stmt_list,
2248 if (new_stmt_list != NULL)
2249 gimple_seq_add_seq (cond_expr_stmt_list, new_stmt_list);
2251 sprintf (tmp_name, "%s%d", "addr2int", i);
2252 addr_tmp = create_tmp_reg (int_ptrsize_type, tmp_name);
2253 add_referenced_var (addr_tmp);
2254 addr_tmp_name = make_ssa_name (addr_tmp, NULL);
2255 addr_stmt = gimple_build_assign_with_ops (NOP_EXPR, addr_tmp_name,
2256 addr_base, NULL_TREE);
2257 SSA_NAME_DEF_STMT (addr_tmp_name) = addr_stmt;
2258 gimple_seq_add_stmt (cond_expr_stmt_list, addr_stmt);
2260 /* The addresses are OR together. */
2262 if (or_tmp_name != NULL_TREE)
2264 /* create: or_tmp = or_tmp | addr_tmp */
2265 sprintf (tmp_name, "%s%d", "orptrs", i);
2266 or_tmp = create_tmp_reg (int_ptrsize_type, tmp_name);
2267 add_referenced_var (or_tmp);
2268 new_or_tmp_name = make_ssa_name (or_tmp, NULL);
2269 or_stmt = gimple_build_assign_with_ops (BIT_IOR_EXPR,
2271 or_tmp_name, addr_tmp_name);
2272 SSA_NAME_DEF_STMT (new_or_tmp_name) = or_stmt;
2273 gimple_seq_add_stmt (cond_expr_stmt_list, or_stmt);
2274 or_tmp_name = new_or_tmp_name;
2277 or_tmp_name = addr_tmp_name;
2281 mask_cst = build_int_cst (int_ptrsize_type, mask);
2283 /* create: and_tmp = or_tmp & mask */
2284 and_tmp = create_tmp_reg (int_ptrsize_type, "andmask" );
2285 add_referenced_var (and_tmp);
2286 and_tmp_name = make_ssa_name (and_tmp, NULL);
2288 and_stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, and_tmp_name,
2289 or_tmp_name, mask_cst);
2290 SSA_NAME_DEF_STMT (and_tmp_name) = and_stmt;
2291 gimple_seq_add_stmt (cond_expr_stmt_list, and_stmt);
2293 /* Make and_tmp the left operand of the conditional test against zero.
2294 if and_tmp has a nonzero bit then some address is unaligned. */
2295 ptrsize_zero = build_int_cst (int_ptrsize_type, 0);
2296 part_cond_expr = fold_build2 (EQ_EXPR, boolean_type_node,
2297 and_tmp_name, ptrsize_zero);
2299 *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2300 *cond_expr, part_cond_expr);
2302 *cond_expr = part_cond_expr;
2306 /* Function vect_vfa_segment_size.
2308 Create an expression that computes the size of segment
2309 that will be accessed for a data reference. The functions takes into
2310 account that realignment loads may access one more vector.
2313 DR: The data reference.
2314 LENGTH_FACTOR: segment length to consider.
2316 Return an expression whose value is the size of segment which will be
2320 vect_vfa_segment_size (struct data_reference *dr, tree length_factor)
2322 tree segment_length;
2324 if (integer_zerop (DR_STEP (dr)))
2325 segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr)));
2327 segment_length = size_binop (MULT_EXPR,
2328 fold_convert (sizetype, DR_STEP (dr)),
2329 fold_convert (sizetype, length_factor));
2331 if (vect_supportable_dr_alignment (dr, false)
2332 == dr_explicit_realign_optimized)
2334 tree vector_size = TYPE_SIZE_UNIT
2335 (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr))));
2337 segment_length = size_binop (PLUS_EXPR, segment_length, vector_size);
2339 return segment_length;
2343 /* Function vect_create_cond_for_alias_checks.
2345 Create a conditional expression that represents the run-time checks for
2346 overlapping of address ranges represented by a list of data references
2347 relations passed as input.
2350 COND_EXPR - input conditional expression. New conditions will be chained
2351 with logical AND operation.
2352 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
2356 COND_EXPR - conditional expression.
2357 COND_EXPR_STMT_LIST - statements needed to construct the conditional
2361 The returned value is the conditional expression to be used in the if
2362 statement that controls which version of the loop gets executed at runtime.
2366 vect_create_cond_for_alias_checks (loop_vec_info loop_vinfo,
2368 gimple_seq * cond_expr_stmt_list)
2370 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2371 VEC (ddr_p, heap) * may_alias_ddrs =
2372 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo);
2373 int vect_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2374 tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
2378 tree part_cond_expr, length_factor;
2380 /* Create expression
2381 ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
2382 || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
2386 ((store_ptr_n + store_segment_length_n) <= load_ptr_n)
2387 || (load_ptr_n + load_segment_length_n) <= store_ptr_n)) */
2389 if (VEC_empty (ddr_p, may_alias_ddrs))
2392 FOR_EACH_VEC_ELT (ddr_p, may_alias_ddrs, i, ddr)
2394 struct data_reference *dr_a, *dr_b;
2395 gimple dr_group_first_a, dr_group_first_b;
2396 tree addr_base_a, addr_base_b;
2397 tree segment_length_a, segment_length_b;
2398 gimple stmt_a, stmt_b;
2399 tree seg_a_min, seg_a_max, seg_b_min, seg_b_max;
2402 stmt_a = DR_STMT (DDR_A (ddr));
2403 dr_group_first_a = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a));
2404 if (dr_group_first_a)
2406 stmt_a = dr_group_first_a;
2407 dr_a = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_a));
2411 stmt_b = DR_STMT (DDR_B (ddr));
2412 dr_group_first_b = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_b));
2413 if (dr_group_first_b)
2415 stmt_b = dr_group_first_b;
2416 dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_b));
2420 vect_create_addr_base_for_vector_ref (stmt_a, cond_expr_stmt_list,
2423 vect_create_addr_base_for_vector_ref (stmt_b, cond_expr_stmt_list,
2426 if (!operand_equal_p (DR_STEP (dr_a), DR_STEP (dr_b), 0))
2427 length_factor = scalar_loop_iters;
2429 length_factor = size_int (vect_factor);
2430 segment_length_a = vect_vfa_segment_size (dr_a, length_factor);
2431 segment_length_b = vect_vfa_segment_size (dr_b, length_factor);
2433 if (vect_print_dump_info (REPORT_DR_DETAILS))
2436 "create runtime check for data references ");
2437 print_generic_expr (vect_dump, DR_REF (dr_a), TDF_SLIM);
2438 fprintf (vect_dump, " and ");
2439 print_generic_expr (vect_dump, DR_REF (dr_b), TDF_SLIM);
2442 seg_a_min = addr_base_a;
2443 seg_a_max = fold_build_pointer_plus (addr_base_a, segment_length_a);
2444 if (tree_int_cst_compare (DR_STEP (dr_a), size_zero_node) < 0)
2445 seg_a_min = seg_a_max, seg_a_max = addr_base_a;
2447 seg_b_min = addr_base_b;
2448 seg_b_max = fold_build_pointer_plus (addr_base_b, segment_length_b);
2449 if (tree_int_cst_compare (DR_STEP (dr_b), size_zero_node) < 0)
2450 seg_b_min = seg_b_max, seg_b_max = addr_base_b;
2453 fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
2454 fold_build2 (LE_EXPR, boolean_type_node, seg_a_max, seg_b_min),
2455 fold_build2 (LE_EXPR, boolean_type_node, seg_b_max, seg_a_min));
2458 *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2459 *cond_expr, part_cond_expr);
2461 *cond_expr = part_cond_expr;
2464 if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS))
2465 fprintf (vect_dump, "created %u versioning for alias checks.\n",
2466 VEC_length (ddr_p, may_alias_ddrs));
2470 /* Function vect_loop_versioning.
2472 If the loop has data references that may or may not be aligned or/and
2473 has data reference relations whose independence was not proven then
2474 two versions of the loop need to be generated, one which is vectorized
2475 and one which isn't. A test is then generated to control which of the
2476 loops is executed. The test checks for the alignment of all of the
2477 data references that may or may not be aligned. An additional
2478 sequence of runtime tests is generated for each pairs of DDRs whose
2479 independence was not proven. The vectorized version of loop is
2480 executed only if both alias and alignment tests are passed.
2482 The test generated to check which version of loop is executed
2483 is modified to also check for profitability as indicated by the
2484 cost model initially.
2486 The versioning precondition(s) are placed in *COND_EXPR and
2487 *COND_EXPR_STMT_LIST. */
2490 vect_loop_versioning (loop_vec_info loop_vinfo,
2491 unsigned int th, bool check_profitability)
2493 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2494 basic_block condition_bb;
2495 gimple_stmt_iterator gsi, cond_exp_gsi;
2496 basic_block merge_bb;
2497 basic_block new_exit_bb;
2499 gimple orig_phi, new_phi;
2500 tree cond_expr = NULL_TREE;
2501 gimple_seq cond_expr_stmt_list = NULL;
2503 unsigned prob = 4 * REG_BR_PROB_BASE / 5;
2504 gimple_seq gimplify_stmt_list = NULL;
2505 tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo);
2507 if (check_profitability)
2509 cond_expr = fold_build2 (GT_EXPR, boolean_type_node, scalar_loop_iters,
2510 build_int_cst (TREE_TYPE (scalar_loop_iters), th));
2511 cond_expr = force_gimple_operand_1 (cond_expr, &cond_expr_stmt_list,
2512 is_gimple_condexpr, NULL_TREE);
2515 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo))
2516 vect_create_cond_for_align_checks (loop_vinfo, &cond_expr,
2517 &cond_expr_stmt_list);
2519 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo))
2520 vect_create_cond_for_alias_checks (loop_vinfo, &cond_expr,
2521 &cond_expr_stmt_list);
2523 cond_expr = force_gimple_operand_1 (cond_expr, &gimplify_stmt_list,
2524 is_gimple_condexpr, NULL_TREE);
2525 gimple_seq_add_seq (&cond_expr_stmt_list, gimplify_stmt_list);
2527 initialize_original_copy_tables ();
2528 loop_version (loop, cond_expr, &condition_bb,
2529 prob, prob, REG_BR_PROB_BASE - prob, true);
2530 free_original_copy_tables();
2532 /* Loop versioning violates an assumption we try to maintain during
2533 vectorization - that the loop exit block has a single predecessor.
2534 After versioning, the exit block of both loop versions is the same
2535 basic block (i.e. it has two predecessors). Just in order to simplify
2536 following transformations in the vectorizer, we fix this situation
2537 here by adding a new (empty) block on the exit-edge of the loop,
2538 with the proper loop-exit phis to maintain loop-closed-form. */
2540 merge_bb = single_exit (loop)->dest;
2541 gcc_assert (EDGE_COUNT (merge_bb->preds) == 2);
2542 new_exit_bb = split_edge (single_exit (loop));
2543 new_exit_e = single_exit (loop);
2544 e = EDGE_SUCC (new_exit_bb, 0);
2546 for (gsi = gsi_start_phis (merge_bb); !gsi_end_p (gsi); gsi_next (&gsi))
2548 orig_phi = gsi_stmt (gsi);
2549 new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
2551 arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
2552 add_phi_arg (new_phi, arg, new_exit_e,
2553 gimple_phi_arg_location_from_edge (orig_phi, e));
2554 adjust_phi_and_debug_stmts (orig_phi, e, PHI_RESULT (new_phi));
2557 /* End loop-exit-fixes after versioning. */
2559 update_ssa (TODO_update_ssa);
2560 if (cond_expr_stmt_list)
2562 cond_exp_gsi = gsi_last_bb (condition_bb);
2563 gsi_insert_seq_before (&cond_exp_gsi, cond_expr_stmt_list,