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 "tree-pretty-print.h"
31 #include "gimple-pretty-print.h"
32 #include "tree-flow.h"
33 #include "tree-dump.h"
35 #include "diagnostic-core.h"
36 #include "tree-scalar-evolution.h"
37 #include "tree-vectorizer.h"
38 #include "langhooks.h"
40 /*************************************************************************
41 Simple Loop Peeling Utilities
43 Utilities to support loop peeling for vectorization purposes.
44 *************************************************************************/
47 /* Renames the use *OP_P. */
50 rename_use_op (use_operand_p op_p
)
54 if (TREE_CODE (USE_FROM_PTR (op_p
)) != SSA_NAME
)
57 new_name
= get_current_def (USE_FROM_PTR (op_p
));
59 /* Something defined outside of the loop. */
63 /* An ordinary ssa name defined in the loop. */
65 SET_USE (op_p
, new_name
);
69 /* Renames the variables in basic block BB. */
72 rename_variables_in_bb (basic_block bb
)
74 gimple_stmt_iterator gsi
;
80 struct loop
*loop
= bb
->loop_father
;
82 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
84 stmt
= gsi_stmt (gsi
);
85 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_ALL_USES
)
86 rename_use_op (use_p
);
89 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
91 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
93 for (gsi
= gsi_start_phis (e
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
94 rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi
), e
));
99 /* Renames variables in new generated LOOP. */
102 rename_variables_in_loop (struct loop
*loop
)
107 bbs
= get_loop_body (loop
);
109 for (i
= 0; i
< loop
->num_nodes
; i
++)
110 rename_variables_in_bb (bbs
[i
]);
121 DEF_VEC_O(adjust_info
);
122 DEF_VEC_ALLOC_O_STACK(adjust_info
);
123 #define VEC_adjust_info_stack_alloc(alloc) VEC_stack_alloc (adjust_info, alloc)
125 /* A stack of values to be adjusted in debug stmts. We have to
126 process them LIFO, so that the closest substitution applies. If we
127 processed them FIFO, without the stack, we might substitute uses
128 with a PHI DEF that would soon become non-dominant, and when we got
129 to the suitable one, it wouldn't have anything to substitute any
131 static VEC(adjust_info
, stack
) *adjust_vec
;
133 /* Adjust any debug stmts that referenced AI->from values to use the
134 loop-closed AI->to, if the references are dominated by AI->bb and
135 not by the definition of AI->from. */
138 adjust_debug_stmts_now (adjust_info
*ai
)
140 basic_block bbphi
= ai
->bb
;
141 tree orig_def
= ai
->from
;
142 tree new_def
= ai
->to
;
143 imm_use_iterator imm_iter
;
145 basic_block bbdef
= gimple_bb (SSA_NAME_DEF_STMT (orig_def
));
147 gcc_assert (dom_info_available_p (CDI_DOMINATORS
));
149 /* Adjust any debug stmts that held onto non-loop-closed
151 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, orig_def
)
156 if (!is_gimple_debug (stmt
))
159 gcc_assert (gimple_debug_bind_p (stmt
));
161 bbuse
= gimple_bb (stmt
);
164 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbphi
))
166 || dominated_by_p (CDI_DOMINATORS
, bbuse
, bbdef
)))
169 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
170 SET_USE (use_p
, new_def
);
173 gimple_debug_bind_reset_value (stmt
);
180 /* Adjust debug stmts as scheduled before. */
183 adjust_vec_debug_stmts (void)
185 if (!MAY_HAVE_DEBUG_STMTS
)
188 gcc_assert (adjust_vec
);
190 while (!VEC_empty (adjust_info
, adjust_vec
))
192 adjust_debug_stmts_now (VEC_last (adjust_info
, adjust_vec
));
193 VEC_pop (adjust_info
, adjust_vec
);
196 VEC_free (adjust_info
, stack
, adjust_vec
);
199 /* Adjust any debug stmts that referenced FROM values to use the
200 loop-closed TO, if the references are dominated by BB and not by
201 the definition of FROM. If adjust_vec is non-NULL, adjustments
202 will be postponed until adjust_vec_debug_stmts is called. */
205 adjust_debug_stmts (tree from
, tree to
, basic_block bb
)
209 if (MAY_HAVE_DEBUG_STMTS
&& TREE_CODE (from
) == SSA_NAME
210 && SSA_NAME_VAR (from
) != gimple_vop (cfun
))
217 VEC_safe_push (adjust_info
, stack
, adjust_vec
, &ai
);
219 adjust_debug_stmts_now (&ai
);
223 /* Change E's phi arg in UPDATE_PHI to NEW_DEF, and record information
224 to adjust any debug stmts that referenced the old phi arg,
225 presumably non-loop-closed references left over from other
229 adjust_phi_and_debug_stmts (gimple update_phi
, edge e
, tree new_def
)
231 tree orig_def
= PHI_ARG_DEF_FROM_EDGE (update_phi
, e
);
233 SET_PHI_ARG_DEF (update_phi
, e
->dest_idx
, new_def
);
235 if (MAY_HAVE_DEBUG_STMTS
)
236 adjust_debug_stmts (orig_def
, PHI_RESULT (update_phi
),
237 gimple_bb (update_phi
));
241 /* Update the PHI nodes of NEW_LOOP.
243 NEW_LOOP is a duplicate of ORIG_LOOP.
244 AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
245 AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
246 executes before it. */
249 slpeel_update_phis_for_duplicate_loop (struct loop
*orig_loop
,
250 struct loop
*new_loop
, bool after
)
253 gimple phi_new
, phi_orig
;
255 edge orig_loop_latch
= loop_latch_edge (orig_loop
);
256 edge orig_entry_e
= loop_preheader_edge (orig_loop
);
257 edge new_loop_exit_e
= single_exit (new_loop
);
258 edge new_loop_entry_e
= loop_preheader_edge (new_loop
);
259 edge entry_arg_e
= (after
? orig_loop_latch
: orig_entry_e
);
260 gimple_stmt_iterator gsi_new
, gsi_orig
;
263 step 1. For each loop-header-phi:
264 Add the first phi argument for the phi in NEW_LOOP
265 (the one associated with the entry of NEW_LOOP)
267 step 2. For each loop-header-phi:
268 Add the second phi argument for the phi in NEW_LOOP
269 (the one associated with the latch of NEW_LOOP)
271 step 3. Update the phis in the successor block of NEW_LOOP.
273 case 1: NEW_LOOP was placed before ORIG_LOOP:
274 The successor block of NEW_LOOP is the header of ORIG_LOOP.
275 Updating the phis in the successor block can therefore be done
276 along with the scanning of the loop header phis, because the
277 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
278 phi nodes, organized in the same order.
280 case 2: NEW_LOOP was placed after ORIG_LOOP:
281 The successor block of NEW_LOOP is the original exit block of
282 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
283 We postpone updating these phis to a later stage (when
284 loop guards are added).
288 /* Scan the phis in the headers of the old and new loops
289 (they are organized in exactly the same order). */
291 for (gsi_new
= gsi_start_phis (new_loop
->header
),
292 gsi_orig
= gsi_start_phis (orig_loop
->header
);
293 !gsi_end_p (gsi_new
) && !gsi_end_p (gsi_orig
);
294 gsi_next (&gsi_new
), gsi_next (&gsi_orig
))
296 source_location locus
;
297 phi_new
= gsi_stmt (gsi_new
);
298 phi_orig
= gsi_stmt (gsi_orig
);
301 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, entry_arg_e
);
302 locus
= gimple_phi_arg_location_from_edge (phi_orig
, entry_arg_e
);
303 add_phi_arg (phi_new
, def
, new_loop_entry_e
, locus
);
306 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, orig_loop_latch
);
307 locus
= gimple_phi_arg_location_from_edge (phi_orig
, orig_loop_latch
);
308 if (TREE_CODE (def
) != SSA_NAME
)
311 new_ssa_name
= get_current_def (def
);
314 /* This only happens if there are no definitions
315 inside the loop. use the phi_result in this case. */
316 new_ssa_name
= PHI_RESULT (phi_new
);
319 /* An ordinary ssa name defined in the loop. */
320 add_phi_arg (phi_new
, new_ssa_name
, loop_latch_edge (new_loop
), locus
);
322 /* Drop any debug references outside the loop, if they would
323 become ill-formed SSA. */
324 adjust_debug_stmts (def
, NULL
, single_exit (orig_loop
)->dest
);
326 /* step 3 (case 1). */
329 gcc_assert (new_loop_exit_e
== orig_entry_e
);
330 adjust_phi_and_debug_stmts (phi_orig
, new_loop_exit_e
, new_ssa_name
);
336 /* Update PHI nodes for a guard of the LOOP.
339 - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
340 controls whether LOOP is to be executed. GUARD_EDGE is the edge that
341 originates from the guard-bb, skips LOOP and reaches the (unique) exit
342 bb of LOOP. This loop-exit-bb is an empty bb with one successor.
343 We denote this bb NEW_MERGE_BB because before the guard code was added
344 it had a single predecessor (the LOOP header), and now it became a merge
345 point of two paths - the path that ends with the LOOP exit-edge, and
346 the path that ends with GUARD_EDGE.
347 - NEW_EXIT_BB: New basic block that is added by this function between LOOP
348 and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
350 ===> The CFG before the guard-code was added:
353 if (exit_loop) goto update_bb
354 else goto LOOP_header_bb
357 ==> The CFG after the guard-code was added:
359 if (LOOP_guard_condition) goto new_merge_bb
360 else goto LOOP_header_bb
363 if (exit_loop_condition) goto new_merge_bb
364 else goto LOOP_header_bb
369 ==> The CFG after this function:
371 if (LOOP_guard_condition) goto new_merge_bb
372 else goto LOOP_header_bb
375 if (exit_loop_condition) goto new_exit_bb
376 else goto LOOP_header_bb
383 1. creates and updates the relevant phi nodes to account for the new
384 incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
385 1.1. Create phi nodes at NEW_MERGE_BB.
386 1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
387 UPDATE_BB). UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
388 2. preserves loop-closed-ssa-form by creating the required phi nodes
389 at the exit of LOOP (i.e, in NEW_EXIT_BB).
391 There are two flavors to this function:
393 slpeel_update_phi_nodes_for_guard1:
394 Here the guard controls whether we enter or skip LOOP, where LOOP is a
395 prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
396 for variables that have phis in the loop header.
398 slpeel_update_phi_nodes_for_guard2:
399 Here the guard controls whether we enter or skip LOOP, where LOOP is an
400 epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
401 for variables that have phis in the loop exit.
403 I.E., the overall structure is:
406 guard1 (goto loop1/merge1_bb)
409 guard2 (goto merge1_bb/merge2_bb)
416 slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
417 loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
418 that have phis in loop1->header).
420 slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
421 loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
422 that have phis in next_bb). It also adds some of these phis to
425 slpeel_update_phi_nodes_for_guard1 is always called before
426 slpeel_update_phi_nodes_for_guard2. They are both needed in order
427 to create correct data-flow and loop-closed-ssa-form.
429 Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
430 that change between iterations of a loop (and therefore have a phi-node
431 at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
432 phis for variables that are used out of the loop (and therefore have
433 loop-closed exit phis). Some variables may be both updated between
434 iterations and used after the loop. This is why in loop1_exit_bb we
435 may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
436 and exit phis (created by slpeel_update_phi_nodes_for_guard2).
438 - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
439 an original loop. i.e., we have:
442 guard_bb (goto LOOP/new_merge)
448 If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
452 guard_bb (goto LOOP/new_merge)
458 The SSA names defined in the original loop have a current
459 reaching definition that that records the corresponding new
460 ssa-name used in the new duplicated loop copy.
463 /* Function slpeel_update_phi_nodes_for_guard1
466 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
467 - DEFS - a bitmap of ssa names to mark new names for which we recorded
470 In the context of the overall structure, we have:
473 guard1 (goto loop1/merge1_bb)
476 guard2 (goto merge1_bb/merge2_bb)
483 For each name updated between loop iterations (i.e - for each name that has
484 an entry (loop-header) phi in LOOP) we create a new phi in:
485 1. merge1_bb (to account for the edge from guard1)
486 2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
490 slpeel_update_phi_nodes_for_guard1 (edge guard_edge
, struct loop
*loop
,
491 bool is_new_loop
, basic_block
*new_exit_bb
)
493 gimple orig_phi
, new_phi
;
494 gimple update_phi
, update_phi2
;
495 tree guard_arg
, loop_arg
;
496 basic_block new_merge_bb
= guard_edge
->dest
;
497 edge e
= EDGE_SUCC (new_merge_bb
, 0);
498 basic_block update_bb
= e
->dest
;
499 basic_block orig_bb
= loop
->header
;
501 tree current_new_name
;
502 gimple_stmt_iterator gsi_orig
, gsi_update
;
504 /* Create new bb between loop and new_merge_bb. */
505 *new_exit_bb
= split_edge (single_exit (loop
));
507 new_exit_e
= EDGE_SUCC (*new_exit_bb
, 0);
509 for (gsi_orig
= gsi_start_phis (orig_bb
),
510 gsi_update
= gsi_start_phis (update_bb
);
511 !gsi_end_p (gsi_orig
) && !gsi_end_p (gsi_update
);
512 gsi_next (&gsi_orig
), gsi_next (&gsi_update
))
514 source_location loop_locus
, guard_locus
;
515 orig_phi
= gsi_stmt (gsi_orig
);
516 update_phi
= gsi_stmt (gsi_update
);
518 /** 1. Handle new-merge-point phis **/
520 /* 1.1. Generate new phi node in NEW_MERGE_BB: */
521 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
524 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
525 of LOOP. Set the two phi args in NEW_PHI for these edges: */
526 loop_arg
= PHI_ARG_DEF_FROM_EDGE (orig_phi
, EDGE_SUCC (loop
->latch
, 0));
527 loop_locus
= gimple_phi_arg_location_from_edge (orig_phi
,
528 EDGE_SUCC (loop
->latch
,
530 guard_arg
= PHI_ARG_DEF_FROM_EDGE (orig_phi
, loop_preheader_edge (loop
));
532 = gimple_phi_arg_location_from_edge (orig_phi
,
533 loop_preheader_edge (loop
));
535 add_phi_arg (new_phi
, loop_arg
, new_exit_e
, loop_locus
);
536 add_phi_arg (new_phi
, guard_arg
, guard_edge
, guard_locus
);
538 /* 1.3. Update phi in successor block. */
539 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi
, e
) == loop_arg
540 || PHI_ARG_DEF_FROM_EDGE (update_phi
, e
) == guard_arg
);
541 adjust_phi_and_debug_stmts (update_phi
, e
, PHI_RESULT (new_phi
));
542 update_phi2
= new_phi
;
545 /** 2. Handle loop-closed-ssa-form phis **/
547 if (!is_gimple_reg (PHI_RESULT (orig_phi
)))
550 /* 2.1. Generate new phi node in NEW_EXIT_BB: */
551 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
554 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
555 add_phi_arg (new_phi
, loop_arg
, single_exit (loop
), loop_locus
);
557 /* 2.3. Update phi in successor of NEW_EXIT_BB: */
558 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2
, new_exit_e
) == loop_arg
);
559 adjust_phi_and_debug_stmts (update_phi2
, new_exit_e
,
560 PHI_RESULT (new_phi
));
562 /* 2.4. Record the newly created name with set_current_def.
563 We want to find a name such that
564 name = get_current_def (orig_loop_name)
565 and to set its current definition as follows:
566 set_current_def (name, new_phi_name)
568 If LOOP is a new loop then loop_arg is already the name we're
569 looking for. If LOOP is the original loop, then loop_arg is
570 the orig_loop_name and the relevant name is recorded in its
571 current reaching definition. */
573 current_new_name
= loop_arg
;
576 current_new_name
= get_current_def (loop_arg
);
577 /* current_def is not available only if the variable does not
578 change inside the loop, in which case we also don't care
579 about recording a current_def for it because we won't be
580 trying to create loop-exit-phis for it. */
581 if (!current_new_name
)
584 gcc_assert (get_current_def (current_new_name
) == NULL_TREE
);
586 set_current_def (current_new_name
, PHI_RESULT (new_phi
));
591 /* Function slpeel_update_phi_nodes_for_guard2
594 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
596 In the context of the overall structure, we have:
599 guard1 (goto loop1/merge1_bb)
602 guard2 (goto merge1_bb/merge2_bb)
609 For each name used out side the loop (i.e - for each name that has an exit
610 phi in next_bb) we create a new phi in:
611 1. merge2_bb (to account for the edge from guard_bb)
612 2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
613 3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
614 if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
618 slpeel_update_phi_nodes_for_guard2 (edge guard_edge
, struct loop
*loop
,
619 bool is_new_loop
, basic_block
*new_exit_bb
)
621 gimple orig_phi
, new_phi
;
622 gimple update_phi
, update_phi2
;
623 tree guard_arg
, loop_arg
;
624 basic_block new_merge_bb
= guard_edge
->dest
;
625 edge e
= EDGE_SUCC (new_merge_bb
, 0);
626 basic_block update_bb
= e
->dest
;
628 tree orig_def
, orig_def_new_name
;
629 tree new_name
, new_name2
;
631 gimple_stmt_iterator gsi
;
633 /* Create new bb between loop and new_merge_bb. */
634 *new_exit_bb
= split_edge (single_exit (loop
));
636 new_exit_e
= EDGE_SUCC (*new_exit_bb
, 0);
638 for (gsi
= gsi_start_phis (update_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
640 update_phi
= gsi_stmt (gsi
);
641 orig_phi
= update_phi
;
642 orig_def
= PHI_ARG_DEF_FROM_EDGE (orig_phi
, e
);
643 /* This loop-closed-phi actually doesn't represent a use
644 out of the loop - the phi arg is a constant. */
645 if (TREE_CODE (orig_def
) != SSA_NAME
)
647 orig_def_new_name
= get_current_def (orig_def
);
650 /** 1. Handle new-merge-point phis **/
652 /* 1.1. Generate new phi node in NEW_MERGE_BB: */
653 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
656 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
657 of LOOP. Set the two PHI args in NEW_PHI for these edges: */
659 new_name2
= NULL_TREE
;
660 if (orig_def_new_name
)
662 new_name
= orig_def_new_name
;
663 /* Some variables have both loop-entry-phis and loop-exit-phis.
664 Such variables were given yet newer names by phis placed in
665 guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
666 new_name2 = get_current_def (get_current_def (orig_name)). */
667 new_name2
= get_current_def (new_name
);
672 guard_arg
= orig_def
;
677 guard_arg
= new_name
;
681 guard_arg
= new_name2
;
683 add_phi_arg (new_phi
, loop_arg
, new_exit_e
, UNKNOWN_LOCATION
);
684 add_phi_arg (new_phi
, guard_arg
, guard_edge
, UNKNOWN_LOCATION
);
686 /* 1.3. Update phi in successor block. */
687 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi
, e
) == orig_def
);
688 adjust_phi_and_debug_stmts (update_phi
, e
, PHI_RESULT (new_phi
));
689 update_phi2
= new_phi
;
692 /** 2. Handle loop-closed-ssa-form phis **/
694 /* 2.1. Generate new phi node in NEW_EXIT_BB: */
695 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
698 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
699 add_phi_arg (new_phi
, loop_arg
, single_exit (loop
), UNKNOWN_LOCATION
);
701 /* 2.3. Update phi in successor of NEW_EXIT_BB: */
702 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2
, new_exit_e
) == loop_arg
);
703 adjust_phi_and_debug_stmts (update_phi2
, new_exit_e
,
704 PHI_RESULT (new_phi
));
707 /** 3. Handle loop-closed-ssa-form phis for first loop **/
709 /* 3.1. Find the relevant names that need an exit-phi in
710 GUARD_BB, i.e. names for which
711 slpeel_update_phi_nodes_for_guard1 had not already created a
712 phi node. This is the case for names that are used outside
713 the loop (and therefore need an exit phi) but are not updated
714 across loop iterations (and therefore don't have a
717 slpeel_update_phi_nodes_for_guard1 is responsible for
718 creating loop-exit phis in GUARD_BB for names that have a
719 loop-header-phi. When such a phi is created we also record
720 the new name in its current definition. If this new name
721 exists, then guard_arg was set to this new name (see 1.2
722 above). Therefore, if guard_arg is not this new name, this
723 is an indication that an exit-phi in GUARD_BB was not yet
724 created, so we take care of it here. */
725 if (guard_arg
== new_name2
)
729 /* 3.2. Generate new phi node in GUARD_BB: */
730 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
733 /* 3.3. GUARD_BB has one incoming edge: */
734 gcc_assert (EDGE_COUNT (guard_edge
->src
->preds
) == 1);
735 add_phi_arg (new_phi
, arg
, EDGE_PRED (guard_edge
->src
, 0),
738 /* 3.4. Update phi in successor of GUARD_BB: */
739 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2
, guard_edge
)
741 adjust_phi_and_debug_stmts (update_phi2
, guard_edge
,
742 PHI_RESULT (new_phi
));
747 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
748 that starts at zero, increases by one and its limit is NITERS.
750 Assumption: the exit-condition of LOOP is the last stmt in the loop. */
753 slpeel_make_loop_iterate_ntimes (struct loop
*loop
, tree niters
)
755 tree indx_before_incr
, indx_after_incr
;
758 edge exit_edge
= single_exit (loop
);
759 gimple_stmt_iterator loop_cond_gsi
;
760 gimple_stmt_iterator incr_gsi
;
762 tree init
= build_int_cst (TREE_TYPE (niters
), 0);
763 tree step
= build_int_cst (TREE_TYPE (niters
), 1);
767 orig_cond
= get_loop_exit_condition (loop
);
768 gcc_assert (orig_cond
);
769 loop_cond_gsi
= gsi_for_stmt (orig_cond
);
771 standard_iv_increment_position (loop
, &incr_gsi
, &insert_after
);
772 create_iv (init
, step
, NULL_TREE
, loop
,
773 &incr_gsi
, insert_after
, &indx_before_incr
, &indx_after_incr
);
775 indx_after_incr
= force_gimple_operand_gsi (&loop_cond_gsi
, indx_after_incr
,
776 true, NULL_TREE
, true,
778 niters
= force_gimple_operand_gsi (&loop_cond_gsi
, niters
, true, NULL_TREE
,
779 true, GSI_SAME_STMT
);
781 code
= (exit_edge
->flags
& EDGE_TRUE_VALUE
) ? GE_EXPR
: LT_EXPR
;
782 cond_stmt
= gimple_build_cond (code
, indx_after_incr
, niters
, NULL_TREE
,
785 gsi_insert_before (&loop_cond_gsi
, cond_stmt
, GSI_SAME_STMT
);
787 /* Remove old loop exit test: */
788 gsi_remove (&loop_cond_gsi
, true);
790 loop_loc
= find_loop_location (loop
);
791 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
793 if (loop_loc
!= UNKNOWN_LOC
)
794 fprintf (dump_file
, "\nloop at %s:%d: ",
795 LOC_FILE (loop_loc
), LOC_LINE (loop_loc
));
796 print_gimple_stmt (dump_file
, cond_stmt
, 0, TDF_SLIM
);
799 loop
->nb_iterations
= niters
;
803 /* Given LOOP this function generates a new copy of it and puts it
804 on E which is either the entry or exit of LOOP. */
807 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop
*loop
, edge e
)
809 struct loop
*new_loop
;
810 basic_block
*new_bbs
, *bbs
;
813 basic_block exit_dest
;
817 gimple_stmt_iterator gsi
;
819 at_exit
= (e
== single_exit (loop
));
820 if (!at_exit
&& e
!= loop_preheader_edge (loop
))
823 bbs
= get_loop_body (loop
);
825 /* Check whether duplication is possible. */
826 if (!can_copy_bbs_p (bbs
, loop
->num_nodes
))
832 /* Generate new loop structure. */
833 new_loop
= duplicate_loop (loop
, loop_outer (loop
));
840 exit_dest
= single_exit (loop
)->dest
;
841 was_imm_dom
= (get_immediate_dominator (CDI_DOMINATORS
,
842 exit_dest
) == loop
->header
?
845 new_bbs
= XNEWVEC (basic_block
, loop
->num_nodes
);
847 exit
= single_exit (loop
);
848 copy_bbs (bbs
, loop
->num_nodes
, new_bbs
,
849 &exit
, 1, &new_exit
, NULL
,
852 /* Duplicating phi args at exit bbs as coming
853 also from exit of duplicated loop. */
854 for (gsi
= gsi_start_phis (exit_dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
856 phi
= gsi_stmt (gsi
);
857 phi_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, single_exit (loop
));
860 edge new_loop_exit_edge
;
861 source_location locus
;
863 locus
= gimple_phi_arg_location_from_edge (phi
, single_exit (loop
));
864 if (EDGE_SUCC (new_loop
->header
, 0)->dest
== new_loop
->latch
)
865 new_loop_exit_edge
= EDGE_SUCC (new_loop
->header
, 1);
867 new_loop_exit_edge
= EDGE_SUCC (new_loop
->header
, 0);
869 add_phi_arg (phi
, phi_arg
, new_loop_exit_edge
, locus
);
873 if (at_exit
) /* Add the loop copy at exit. */
875 redirect_edge_and_branch_force (e
, new_loop
->header
);
876 PENDING_STMT (e
) = NULL
;
877 set_immediate_dominator (CDI_DOMINATORS
, new_loop
->header
, e
->src
);
879 set_immediate_dominator (CDI_DOMINATORS
, exit_dest
, new_loop
->header
);
881 else /* Add the copy at entry. */
884 edge entry_e
= loop_preheader_edge (loop
);
885 basic_block preheader
= entry_e
->src
;
887 if (!flow_bb_inside_loop_p (new_loop
,
888 EDGE_SUCC (new_loop
->header
, 0)->dest
))
889 new_exit_e
= EDGE_SUCC (new_loop
->header
, 0);
891 new_exit_e
= EDGE_SUCC (new_loop
->header
, 1);
893 redirect_edge_and_branch_force (new_exit_e
, loop
->header
);
894 PENDING_STMT (new_exit_e
) = NULL
;
895 set_immediate_dominator (CDI_DOMINATORS
, loop
->header
,
898 /* We have to add phi args to the loop->header here as coming
899 from new_exit_e edge. */
900 for (gsi
= gsi_start_phis (loop
->header
);
904 phi
= gsi_stmt (gsi
);
905 phi_arg
= PHI_ARG_DEF_FROM_EDGE (phi
, entry_e
);
907 add_phi_arg (phi
, phi_arg
, new_exit_e
,
908 gimple_phi_arg_location_from_edge (phi
, entry_e
));
911 redirect_edge_and_branch_force (entry_e
, new_loop
->header
);
912 PENDING_STMT (entry_e
) = NULL
;
913 set_immediate_dominator (CDI_DOMINATORS
, new_loop
->header
, preheader
);
923 /* Given the condition statement COND, put it as the last statement
924 of GUARD_BB; EXIT_BB is the basic block to skip the loop;
925 Assumes that this is the single exit of the guarded loop.
926 Returns the skip edge, inserts new stmts on the COND_EXPR_STMT_LIST. */
929 slpeel_add_loop_guard (basic_block guard_bb
, tree cond
,
930 gimple_seq cond_expr_stmt_list
,
931 basic_block exit_bb
, basic_block dom_bb
)
933 gimple_stmt_iterator gsi
;
936 gimple_seq gimplify_stmt_list
= NULL
;
938 enter_e
= EDGE_SUCC (guard_bb
, 0);
939 enter_e
->flags
&= ~EDGE_FALLTHRU
;
940 enter_e
->flags
|= EDGE_FALSE_VALUE
;
941 gsi
= gsi_last_bb (guard_bb
);
943 cond
= force_gimple_operand_1 (cond
, &gimplify_stmt_list
, is_gimple_condexpr
,
945 if (gimplify_stmt_list
)
946 gimple_seq_add_seq (&cond_expr_stmt_list
, gimplify_stmt_list
);
947 cond_stmt
= gimple_build_cond_from_tree (cond
, NULL_TREE
, NULL_TREE
);
948 if (cond_expr_stmt_list
)
949 gsi_insert_seq_after (&gsi
, cond_expr_stmt_list
, GSI_NEW_STMT
);
951 gsi
= gsi_last_bb (guard_bb
);
952 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
954 /* Add new edge to connect guard block to the merge/loop-exit block. */
955 new_e
= make_edge (guard_bb
, exit_bb
, EDGE_TRUE_VALUE
);
956 set_immediate_dominator (CDI_DOMINATORS
, exit_bb
, dom_bb
);
961 /* This function verifies that the following restrictions apply to LOOP:
963 (2) it consists of exactly 2 basic blocks - header, and an empty latch.
964 (3) it is single entry, single exit
965 (4) its exit condition is the last stmt in the header
966 (5) E is the entry/exit edge of LOOP.
970 slpeel_can_duplicate_loop_p (const struct loop
*loop
, const_edge e
)
972 edge exit_e
= single_exit (loop
);
973 edge entry_e
= loop_preheader_edge (loop
);
974 gimple orig_cond
= get_loop_exit_condition (loop
);
975 gimple_stmt_iterator loop_exit_gsi
= gsi_last_bb (exit_e
->src
);
977 if (need_ssa_update_p (cfun
))
981 /* All loops have an outer scope; the only case loop->outer is NULL is for
982 the function itself. */
983 || !loop_outer (loop
)
984 || loop
->num_nodes
!= 2
985 || !empty_block_p (loop
->latch
)
986 || !single_exit (loop
)
987 /* Verify that new loop exit condition can be trivially modified. */
988 || (!orig_cond
|| orig_cond
!= gsi_stmt (loop_exit_gsi
))
989 || (e
!= exit_e
&& e
!= entry_e
))
995 #ifdef ENABLE_CHECKING
997 slpeel_verify_cfg_after_peeling (struct loop
*first_loop
,
998 struct loop
*second_loop
)
1000 basic_block loop1_exit_bb
= single_exit (first_loop
)->dest
;
1001 basic_block loop2_entry_bb
= loop_preheader_edge (second_loop
)->src
;
1002 basic_block loop1_entry_bb
= loop_preheader_edge (first_loop
)->src
;
1004 /* A guard that controls whether the second_loop is to be executed or skipped
1005 is placed in first_loop->exit. first_loop->exit therefore has two
1006 successors - one is the preheader of second_loop, and the other is a bb
1009 gcc_assert (EDGE_COUNT (loop1_exit_bb
->succs
) == 2);
1011 /* 1. Verify that one of the successors of first_loop->exit is the preheader
1014 /* The preheader of new_loop is expected to have two predecessors:
1015 first_loop->exit and the block that precedes first_loop. */
1017 gcc_assert (EDGE_COUNT (loop2_entry_bb
->preds
) == 2
1018 && ((EDGE_PRED (loop2_entry_bb
, 0)->src
== loop1_exit_bb
1019 && EDGE_PRED (loop2_entry_bb
, 1)->src
== loop1_entry_bb
)
1020 || (EDGE_PRED (loop2_entry_bb
, 1)->src
== loop1_exit_bb
1021 && EDGE_PRED (loop2_entry_bb
, 0)->src
== loop1_entry_bb
)));
1023 /* Verify that the other successor of first_loop->exit is after the
1029 /* If the run time cost model check determines that vectorization is
1030 not profitable and hence scalar loop should be generated then set
1031 FIRST_NITERS to prologue peeled iterations. This will allow all the
1032 iterations to be executed in the prologue peeled scalar loop. */
1035 set_prologue_iterations (basic_block bb_before_first_loop
,
1041 basic_block cond_bb
, then_bb
;
1042 tree var
, prologue_after_cost_adjust_name
;
1043 gimple_stmt_iterator gsi
;
1045 edge e_true
, e_false
, e_fallthru
;
1047 gimple_seq stmts
= NULL
;
1048 tree cost_pre_condition
= NULL_TREE
;
1049 tree scalar_loop_iters
=
1050 unshare_expr (LOOP_VINFO_NITERS_UNCHANGED (loop_vec_info_for_loop (loop
)));
1052 e
= single_pred_edge (bb_before_first_loop
);
1053 cond_bb
= split_edge(e
);
1055 e
= single_pred_edge (bb_before_first_loop
);
1056 then_bb
= split_edge(e
);
1057 set_immediate_dominator (CDI_DOMINATORS
, then_bb
, cond_bb
);
1059 e_false
= make_single_succ_edge (cond_bb
, bb_before_first_loop
,
1061 set_immediate_dominator (CDI_DOMINATORS
, bb_before_first_loop
, cond_bb
);
1063 e_true
= EDGE_PRED (then_bb
, 0);
1064 e_true
->flags
&= ~EDGE_FALLTHRU
;
1065 e_true
->flags
|= EDGE_TRUE_VALUE
;
1067 e_fallthru
= EDGE_SUCC (then_bb
, 0);
1069 gsi
= gsi_last_bb (cond_bb
);
1070 cost_pre_condition
=
1071 fold_build2 (LE_EXPR
, boolean_type_node
, scalar_loop_iters
,
1072 build_int_cst (TREE_TYPE (scalar_loop_iters
), th
));
1073 cost_pre_condition
=
1074 force_gimple_operand_gsi_1 (&gsi
, cost_pre_condition
, is_gimple_condexpr
,
1075 NULL_TREE
, false, GSI_CONTINUE_LINKING
);
1076 cond_stmt
= gimple_build_cond_from_tree (cost_pre_condition
,
1077 NULL_TREE
, NULL_TREE
);
1078 gsi_insert_after (&gsi
, cond_stmt
, GSI_NEW_STMT
);
1080 var
= create_tmp_var (TREE_TYPE (scalar_loop_iters
),
1081 "prologue_after_cost_adjust");
1082 add_referenced_var (var
);
1083 prologue_after_cost_adjust_name
=
1084 force_gimple_operand (scalar_loop_iters
, &stmts
, false, var
);
1086 gsi
= gsi_last_bb (then_bb
);
1088 gsi_insert_seq_after (&gsi
, stmts
, GSI_NEW_STMT
);
1090 newphi
= create_phi_node (var
, bb_before_first_loop
);
1091 add_phi_arg (newphi
, prologue_after_cost_adjust_name
, e_fallthru
,
1093 add_phi_arg (newphi
, *first_niters
, e_false
, UNKNOWN_LOCATION
);
1095 *first_niters
= PHI_RESULT (newphi
);
1098 /* Function slpeel_tree_peel_loop_to_edge.
1100 Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
1101 that is placed on the entry (exit) edge E of LOOP. After this transformation
1102 we have two loops one after the other - first-loop iterates FIRST_NITERS
1103 times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
1104 If the cost model indicates that it is profitable to emit a scalar
1105 loop instead of the vector one, then the prolog (epilog) loop will iterate
1106 for the entire unchanged scalar iterations of the loop.
1109 - LOOP: the loop to be peeled.
1110 - E: the exit or entry edge of LOOP.
1111 If it is the entry edge, we peel the first iterations of LOOP. In this
1112 case first-loop is LOOP, and second-loop is the newly created loop.
1113 If it is the exit edge, we peel the last iterations of LOOP. In this
1114 case, first-loop is the newly created loop, and second-loop is LOOP.
1115 - NITERS: the number of iterations that LOOP iterates.
1116 - FIRST_NITERS: the number of iterations that the first-loop should iterate.
1117 - UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible
1118 for updating the loop bound of the first-loop to FIRST_NITERS. If it
1119 is false, the caller of this function may want to take care of this
1120 (this can be useful if we don't want new stmts added to first-loop).
1121 - TH: cost model profitability threshold of iterations for vectorization.
1122 - CHECK_PROFITABILITY: specify whether cost model check has not occurred
1123 during versioning and hence needs to occur during
1124 prologue generation or whether cost model check
1125 has not occurred during prologue generation and hence
1126 needs to occur during epilogue generation.
1130 The function returns a pointer to the new loop-copy, or NULL if it failed
1131 to perform the transformation.
1133 The function generates two if-then-else guards: one before the first loop,
1134 and the other before the second loop:
1136 if (FIRST_NITERS == 0) then skip the first loop,
1137 and go directly to the second loop.
1138 The second guard is:
1139 if (FIRST_NITERS == NITERS) then skip the second loop.
1141 If the optional COND_EXPR and COND_EXPR_STMT_LIST arguments are given
1142 then the generated condition is combined with COND_EXPR and the
1143 statements in COND_EXPR_STMT_LIST are emitted together with it.
1145 FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
1146 FORNOW the resulting code will not be in loop-closed-ssa form.
1150 slpeel_tree_peel_loop_to_edge (struct loop
*loop
,
1151 edge e
, tree
*first_niters
,
1152 tree niters
, bool update_first_loop_count
,
1153 unsigned int th
, bool check_profitability
,
1154 tree cond_expr
, gimple_seq cond_expr_stmt_list
)
1156 struct loop
*new_loop
= NULL
, *first_loop
, *second_loop
;
1158 tree pre_condition
= NULL_TREE
;
1159 basic_block bb_before_second_loop
, bb_after_second_loop
;
1160 basic_block bb_before_first_loop
;
1161 basic_block bb_between_loops
;
1162 basic_block new_exit_bb
;
1163 gimple_stmt_iterator gsi
;
1164 edge exit_e
= single_exit (loop
);
1166 tree cost_pre_condition
= NULL_TREE
;
1168 if (!slpeel_can_duplicate_loop_p (loop
, e
))
1171 /* If the loop has a virtual PHI, but exit bb doesn't, create a virtual PHI
1172 in the exit bb and rename all the uses after the loop. This simplifies
1173 the *guard[12] routines, which assume loop closed SSA form for all PHIs
1174 (but normally loop closed SSA form doesn't require virtual PHIs to be
1175 in the same form). Doing this early simplifies the checking what
1176 uses should be renamed. */
1177 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1178 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi
))))
1180 gimple phi
= gsi_stmt (gsi
);
1181 for (gsi
= gsi_start_phis (exit_e
->dest
);
1182 !gsi_end_p (gsi
); gsi_next (&gsi
))
1183 if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi
))))
1185 if (gsi_end_p (gsi
))
1187 gimple new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (phi
)),
1189 tree vop
= PHI_ARG_DEF_FROM_EDGE (phi
, EDGE_SUCC (loop
->latch
, 0));
1190 imm_use_iterator imm_iter
;
1192 tree new_vop
= make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi
)),
1194 use_operand_p use_p
;
1196 add_phi_arg (new_phi
, vop
, exit_e
, UNKNOWN_LOCATION
);
1197 gimple_phi_set_result (new_phi
, new_vop
);
1198 FOR_EACH_IMM_USE_STMT (stmt
, imm_iter
, vop
)
1199 if (stmt
!= new_phi
&& gimple_bb (stmt
) != loop
->header
)
1200 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1201 SET_USE (use_p
, new_vop
);
1206 /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1207 Resulting CFG would be:
1220 if (!(new_loop
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, e
)))
1222 loop_loc
= find_loop_location (loop
);
1223 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1225 if (loop_loc
!= UNKNOWN_LOC
)
1226 fprintf (dump_file
, "\n%s:%d: note: ",
1227 LOC_FILE (loop_loc
), LOC_LINE (loop_loc
));
1228 fprintf (dump_file
, "tree_duplicate_loop_to_edge_cfg failed.\n");
1233 if (MAY_HAVE_DEBUG_STMTS
)
1235 gcc_assert (!adjust_vec
);
1236 adjust_vec
= VEC_alloc (adjust_info
, stack
, 32);
1241 /* NEW_LOOP was placed after LOOP. */
1243 second_loop
= new_loop
;
1247 /* NEW_LOOP was placed before LOOP. */
1248 first_loop
= new_loop
;
1252 slpeel_update_phis_for_duplicate_loop (loop
, new_loop
, e
== exit_e
);
1253 rename_variables_in_loop (new_loop
);
1256 /* 2. Add the guard code in one of the following ways:
1258 2.a Add the guard that controls whether the first loop is executed.
1259 This occurs when this function is invoked for prologue or epilogue
1260 generation and when the cost model check can be done at compile time.
1262 Resulting CFG would be:
1264 bb_before_first_loop:
1265 if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1272 bb_before_second_loop:
1280 2.b Add the cost model check that allows the prologue
1281 to iterate for the entire unchanged scalar
1282 iterations of the loop in the event that the cost
1283 model indicates that the scalar loop is more
1284 profitable than the vector one. This occurs when
1285 this function is invoked for prologue generation
1286 and the cost model check needs to be done at run
1289 Resulting CFG after prologue peeling would be:
1291 if (scalar_loop_iterations <= th)
1292 FIRST_NITERS = scalar_loop_iterations
1294 bb_before_first_loop:
1295 if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1302 bb_before_second_loop:
1310 2.c Add the cost model check that allows the epilogue
1311 to iterate for the entire unchanged scalar
1312 iterations of the loop in the event that the cost
1313 model indicates that the scalar loop is more
1314 profitable than the vector one. This occurs when
1315 this function is invoked for epilogue generation
1316 and the cost model check needs to be done at run
1317 time. This check is combined with any pre-existing
1318 check in COND_EXPR to avoid versioning.
1320 Resulting CFG after prologue peeling would be:
1322 bb_before_first_loop:
1323 if ((scalar_loop_iterations <= th)
1325 FIRST_NITERS == 0) GOTO bb_before_second_loop
1332 bb_before_second_loop:
1341 bb_before_first_loop
= split_edge (loop_preheader_edge (first_loop
));
1342 bb_before_second_loop
= split_edge (single_exit (first_loop
));
1344 /* Epilogue peeling. */
1345 if (!update_first_loop_count
)
1348 fold_build2 (LE_EXPR
, boolean_type_node
, *first_niters
,
1349 build_int_cst (TREE_TYPE (*first_niters
), 0));
1350 if (check_profitability
)
1352 tree scalar_loop_iters
1353 = unshare_expr (LOOP_VINFO_NITERS_UNCHANGED
1354 (loop_vec_info_for_loop (loop
)));
1355 cost_pre_condition
=
1356 fold_build2 (LE_EXPR
, boolean_type_node
, scalar_loop_iters
,
1357 build_int_cst (TREE_TYPE (scalar_loop_iters
), th
));
1359 pre_condition
= fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1360 cost_pre_condition
, pre_condition
);
1365 fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
1367 fold_build1 (TRUTH_NOT_EXPR
, boolean_type_node
,
1372 /* Prologue peeling. */
1375 if (check_profitability
)
1376 set_prologue_iterations (bb_before_first_loop
, first_niters
,
1380 fold_build2 (LE_EXPR
, boolean_type_node
, *first_niters
,
1381 build_int_cst (TREE_TYPE (*first_niters
), 0));
1384 skip_e
= slpeel_add_loop_guard (bb_before_first_loop
, pre_condition
,
1385 cond_expr_stmt_list
,
1386 bb_before_second_loop
, bb_before_first_loop
);
1387 slpeel_update_phi_nodes_for_guard1 (skip_e
, first_loop
,
1388 first_loop
== new_loop
,
1392 /* 3. Add the guard that controls whether the second loop is executed.
1393 Resulting CFG would be:
1395 bb_before_first_loop:
1396 if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1404 if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1405 GOTO bb_before_second_loop
1407 bb_before_second_loop:
1413 bb_after_second_loop:
1418 bb_between_loops
= new_exit_bb
;
1419 bb_after_second_loop
= split_edge (single_exit (second_loop
));
1422 fold_build2 (EQ_EXPR
, boolean_type_node
, *first_niters
, niters
);
1423 skip_e
= slpeel_add_loop_guard (bb_between_loops
, pre_condition
, NULL
,
1424 bb_after_second_loop
, bb_before_first_loop
);
1425 slpeel_update_phi_nodes_for_guard2 (skip_e
, second_loop
,
1426 second_loop
== new_loop
, &new_exit_bb
);
1428 /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1430 if (update_first_loop_count
)
1431 slpeel_make_loop_iterate_ntimes (first_loop
, *first_niters
);
1433 delete_update_ssa ();
1435 adjust_vec_debug_stmts ();
1440 /* Function vect_get_loop_location.
1442 Extract the location of the loop in the source code.
1443 If the loop is not well formed for vectorization, an estimated
1444 location is calculated.
1445 Return the loop location if succeed and NULL if not. */
1448 find_loop_location (struct loop
*loop
)
1452 gimple_stmt_iterator si
;
1457 stmt
= get_loop_exit_condition (loop
);
1459 if (stmt
&& gimple_location (stmt
) != UNKNOWN_LOC
)
1460 return gimple_location (stmt
);
1462 /* If we got here the loop is probably not "well formed",
1463 try to estimate the loop location */
1470 for (si
= gsi_start_bb (bb
); !gsi_end_p (si
); gsi_next (&si
))
1472 stmt
= gsi_stmt (si
);
1473 if (gimple_location (stmt
) != UNKNOWN_LOC
)
1474 return gimple_location (stmt
);
1481 /* This function builds ni_name = number of iterations loop executes
1482 on the loop preheader. If SEQ is given the stmt is instead emitted
1486 vect_build_loop_niters (loop_vec_info loop_vinfo
, gimple_seq seq
)
1489 gimple_seq stmts
= NULL
;
1491 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1492 tree ni
= unshare_expr (LOOP_VINFO_NITERS (loop_vinfo
));
1494 var
= create_tmp_var (TREE_TYPE (ni
), "niters");
1495 add_referenced_var (var
);
1496 ni_name
= force_gimple_operand (ni
, &stmts
, false, var
);
1498 pe
= loop_preheader_edge (loop
);
1502 gimple_seq_add_seq (&seq
, stmts
);
1505 basic_block new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
1506 gcc_assert (!new_bb
);
1514 /* This function generates the following statements:
1516 ni_name = number of iterations loop executes
1517 ratio = ni_name / vf
1518 ratio_mult_vf_name = ratio * vf
1520 and places them at the loop preheader edge or in COND_EXPR_STMT_LIST
1521 if that is non-NULL. */
1524 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo
,
1526 tree
*ratio_mult_vf_name_ptr
,
1527 tree
*ratio_name_ptr
,
1528 gimple_seq cond_expr_stmt_list
)
1534 tree ni_name
, ni_minus_gap_name
;
1537 tree ratio_mult_vf_name
;
1538 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1539 tree ni
= LOOP_VINFO_NITERS (loop_vinfo
);
1540 int vf
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
1543 pe
= loop_preheader_edge (loop
);
1545 /* Generate temporary variable that contains
1546 number of iterations loop executes. */
1548 ni_name
= vect_build_loop_niters (loop_vinfo
, cond_expr_stmt_list
);
1549 log_vf
= build_int_cst (TREE_TYPE (ni
), exact_log2 (vf
));
1551 /* If epilogue loop is required because of data accesses with gaps, we
1552 subtract one iteration from the total number of iterations here for
1553 correct calculation of RATIO. */
1554 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo
))
1556 ni_minus_gap_name
= fold_build2 (MINUS_EXPR
, TREE_TYPE (ni_name
),
1558 build_one_cst (TREE_TYPE (ni_name
)));
1559 if (!is_gimple_val (ni_minus_gap_name
))
1561 var
= create_tmp_var (TREE_TYPE (ni
), "ni_gap");
1562 add_referenced_var (var
);
1565 ni_minus_gap_name
= force_gimple_operand (ni_minus_gap_name
, &stmts
,
1567 if (cond_expr_stmt_list
)
1568 gimple_seq_add_seq (&cond_expr_stmt_list
, stmts
);
1571 pe
= loop_preheader_edge (loop
);
1572 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
1573 gcc_assert (!new_bb
);
1578 ni_minus_gap_name
= ni_name
;
1580 /* Create: ratio = ni >> log2(vf) */
1582 ratio_name
= fold_build2 (RSHIFT_EXPR
, TREE_TYPE (ni_minus_gap_name
),
1583 ni_minus_gap_name
, log_vf
);
1584 if (!is_gimple_val (ratio_name
))
1586 var
= create_tmp_var (TREE_TYPE (ni
), "bnd");
1587 add_referenced_var (var
);
1590 ratio_name
= force_gimple_operand (ratio_name
, &stmts
, true, var
);
1591 if (cond_expr_stmt_list
)
1592 gimple_seq_add_seq (&cond_expr_stmt_list
, stmts
);
1595 pe
= loop_preheader_edge (loop
);
1596 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
1597 gcc_assert (!new_bb
);
1601 /* Create: ratio_mult_vf = ratio << log2 (vf). */
1603 ratio_mult_vf_name
= fold_build2 (LSHIFT_EXPR
, TREE_TYPE (ratio_name
),
1604 ratio_name
, log_vf
);
1605 if (!is_gimple_val (ratio_mult_vf_name
))
1607 var
= create_tmp_var (TREE_TYPE (ni
), "ratio_mult_vf");
1608 add_referenced_var (var
);
1611 ratio_mult_vf_name
= force_gimple_operand (ratio_mult_vf_name
, &stmts
,
1613 if (cond_expr_stmt_list
)
1614 gimple_seq_add_seq (&cond_expr_stmt_list
, stmts
);
1617 pe
= loop_preheader_edge (loop
);
1618 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
1619 gcc_assert (!new_bb
);
1623 *ni_name_ptr
= ni_name
;
1624 *ratio_mult_vf_name_ptr
= ratio_mult_vf_name
;
1625 *ratio_name_ptr
= ratio_name
;
1630 /* Function vect_can_advance_ivs_p
1632 In case the number of iterations that LOOP iterates is unknown at compile
1633 time, an epilog loop will be generated, and the loop induction variables
1634 (IVs) will be "advanced" to the value they are supposed to take just before
1635 the epilog loop. Here we check that the access function of the loop IVs
1636 and the expression that represents the loop bound are simple enough.
1637 These restrictions will be relaxed in the future. */
1640 vect_can_advance_ivs_p (loop_vec_info loop_vinfo
)
1642 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1643 basic_block bb
= loop
->header
;
1645 gimple_stmt_iterator gsi
;
1647 /* Analyze phi functions of the loop header. */
1649 if (vect_print_dump_info (REPORT_DETAILS
))
1650 fprintf (vect_dump
, "vect_can_advance_ivs_p:");
1652 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1654 tree access_fn
= NULL
;
1655 tree evolution_part
;
1657 phi
= gsi_stmt (gsi
);
1658 if (vect_print_dump_info (REPORT_DETAILS
))
1660 fprintf (vect_dump
, "Analyze phi: ");
1661 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
1664 /* Skip virtual phi's. The data dependences that are associated with
1665 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */
1667 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi
))))
1669 if (vect_print_dump_info (REPORT_DETAILS
))
1670 fprintf (vect_dump
, "virtual phi. skip.");
1674 /* Skip reduction phis. */
1676 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi
)) == vect_reduction_def
)
1678 if (vect_print_dump_info (REPORT_DETAILS
))
1679 fprintf (vect_dump
, "reduc phi. skip.");
1683 /* Analyze the evolution function. */
1685 access_fn
= instantiate_parameters
1686 (loop
, analyze_scalar_evolution (loop
, PHI_RESULT (phi
)));
1690 if (vect_print_dump_info (REPORT_DETAILS
))
1691 fprintf (vect_dump
, "No Access function.");
1695 if (vect_print_dump_info (REPORT_DETAILS
))
1697 fprintf (vect_dump
, "Access function of PHI: ");
1698 print_generic_expr (vect_dump
, access_fn
, TDF_SLIM
);
1701 evolution_part
= evolution_part_in_loop_num (access_fn
, loop
->num
);
1703 if (evolution_part
== NULL_TREE
)
1705 if (vect_print_dump_info (REPORT_DETAILS
))
1706 fprintf (vect_dump
, "No evolution.");
1710 /* FORNOW: We do not transform initial conditions of IVs
1711 which evolution functions are a polynomial of degree >= 2. */
1713 if (tree_is_chrec (evolution_part
))
1721 /* Function vect_update_ivs_after_vectorizer.
1723 "Advance" the induction variables of LOOP to the value they should take
1724 after the execution of LOOP. This is currently necessary because the
1725 vectorizer does not handle induction variables that are used after the
1726 loop. Such a situation occurs when the last iterations of LOOP are
1728 1. We introduced new uses after LOOP for IVs that were not originally used
1729 after LOOP: the IVs of LOOP are now used by an epilog loop.
1730 2. LOOP is going to be vectorized; this means that it will iterate N/VF
1731 times, whereas the loop IVs should be bumped N times.
1734 - LOOP - a loop that is going to be vectorized. The last few iterations
1735 of LOOP were peeled.
1736 - NITERS - the number of iterations that LOOP executes (before it is
1737 vectorized). i.e, the number of times the ivs should be bumped.
1738 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
1739 coming out from LOOP on which there are uses of the LOOP ivs
1740 (this is the path from LOOP->exit to epilog_loop->preheader).
1742 The new definitions of the ivs are placed in LOOP->exit.
1743 The phi args associated with the edge UPDATE_E in the bb
1744 UPDATE_E->dest are updated accordingly.
1746 Assumption 1: Like the rest of the vectorizer, this function assumes
1747 a single loop exit that has a single predecessor.
1749 Assumption 2: The phi nodes in the LOOP header and in update_bb are
1750 organized in the same order.
1752 Assumption 3: The access function of the ivs is simple enough (see
1753 vect_can_advance_ivs_p). This assumption will be relaxed in the future.
1755 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
1756 coming out of LOOP on which the ivs of LOOP are used (this is the path
1757 that leads to the epilog loop; other paths skip the epilog loop). This
1758 path starts with the edge UPDATE_E, and its destination (denoted update_bb)
1759 needs to have its phis updated.
1763 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo
, tree niters
,
1766 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1767 basic_block exit_bb
= single_exit (loop
)->dest
;
1769 gimple_stmt_iterator gsi
, gsi1
;
1770 basic_block update_bb
= update_e
->dest
;
1772 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
1774 /* Make sure there exists a single-predecessor exit bb: */
1775 gcc_assert (single_pred_p (exit_bb
));
1777 for (gsi
= gsi_start_phis (loop
->header
), gsi1
= gsi_start_phis (update_bb
);
1778 !gsi_end_p (gsi
) && !gsi_end_p (gsi1
);
1779 gsi_next (&gsi
), gsi_next (&gsi1
))
1782 tree step_expr
, off
;
1784 tree var
, ni
, ni_name
;
1785 gimple_stmt_iterator last_gsi
;
1786 stmt_vec_info stmt_info
;
1788 phi
= gsi_stmt (gsi
);
1789 phi1
= gsi_stmt (gsi1
);
1790 if (vect_print_dump_info (REPORT_DETAILS
))
1792 fprintf (vect_dump
, "vect_update_ivs_after_vectorizer: phi: ");
1793 print_gimple_stmt (vect_dump
, phi
, 0, TDF_SLIM
);
1796 /* Skip virtual phi's. */
1797 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi
))))
1799 if (vect_print_dump_info (REPORT_DETAILS
))
1800 fprintf (vect_dump
, "virtual phi. skip.");
1804 /* Skip reduction phis. */
1805 stmt_info
= vinfo_for_stmt (phi
);
1806 if (STMT_VINFO_DEF_TYPE (stmt_info
) == vect_reduction_def
)
1808 if (vect_print_dump_info (REPORT_DETAILS
))
1809 fprintf (vect_dump
, "reduc phi. skip.");
1813 type
= TREE_TYPE (gimple_phi_result (phi
));
1814 step_expr
= STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info
);
1815 step_expr
= unshare_expr (step_expr
);
1817 /* FORNOW: We do not support IVs whose evolution function is a polynomial
1818 of degree >= 2 or exponential. */
1819 gcc_assert (!tree_is_chrec (step_expr
));
1821 init_expr
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1823 off
= fold_build2 (MULT_EXPR
, TREE_TYPE (step_expr
),
1824 fold_convert (TREE_TYPE (step_expr
), niters
),
1826 if (POINTER_TYPE_P (type
))
1827 ni
= fold_build_pointer_plus (init_expr
, off
);
1829 ni
= fold_build2 (PLUS_EXPR
, type
,
1830 init_expr
, fold_convert (type
, off
));
1832 var
= create_tmp_var (type
, "tmp");
1833 add_referenced_var (var
);
1835 last_gsi
= gsi_last_bb (exit_bb
);
1836 ni_name
= force_gimple_operand_gsi (&last_gsi
, ni
, false, var
,
1837 true, GSI_SAME_STMT
);
1839 /* Fix phi expressions in the successor bb. */
1840 adjust_phi_and_debug_stmts (phi1
, update_e
, ni_name
);
1844 /* Function vect_do_peeling_for_loop_bound
1846 Peel the last iterations of the loop represented by LOOP_VINFO.
1847 The peeled iterations form a new epilog loop. Given that the loop now
1848 iterates NITERS times, the new epilog loop iterates
1849 NITERS % VECTORIZATION_FACTOR times.
1851 The original loop will later be made to iterate
1852 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).
1854 COND_EXPR and COND_EXPR_STMT_LIST are combined with a new generated
1858 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo
, tree
*ratio
,
1859 unsigned int th
, bool check_profitability
)
1861 tree ni_name
, ratio_mult_vf_name
;
1862 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1863 struct loop
*new_loop
;
1865 basic_block preheader
;
1868 tree cond_expr
= NULL_TREE
;
1869 gimple_seq cond_expr_stmt_list
= NULL
;
1871 if (vect_print_dump_info (REPORT_DETAILS
))
1872 fprintf (vect_dump
, "=== vect_do_peeling_for_loop_bound ===");
1874 initialize_original_copy_tables ();
1876 /* Generate the following variables on the preheader of original loop:
1878 ni_name = number of iteration the original loop executes
1879 ratio = ni_name / vf
1880 ratio_mult_vf_name = ratio * vf */
1881 vect_generate_tmps_on_preheader (loop_vinfo
, &ni_name
,
1882 &ratio_mult_vf_name
, ratio
,
1883 cond_expr_stmt_list
);
1885 loop_num
= loop
->num
;
1887 new_loop
= slpeel_tree_peel_loop_to_edge (loop
, single_exit (loop
),
1888 &ratio_mult_vf_name
, ni_name
, false,
1889 th
, check_profitability
,
1890 cond_expr
, cond_expr_stmt_list
);
1891 gcc_assert (new_loop
);
1892 gcc_assert (loop_num
== loop
->num
);
1893 #ifdef ENABLE_CHECKING
1894 slpeel_verify_cfg_after_peeling (loop
, new_loop
);
1897 /* A guard that controls whether the new_loop is to be executed or skipped
1898 is placed in LOOP->exit. LOOP->exit therefore has two successors - one
1899 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other
1900 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that
1901 is on the path where the LOOP IVs are used and need to be updated. */
1903 preheader
= loop_preheader_edge (new_loop
)->src
;
1904 if (EDGE_PRED (preheader
, 0)->src
== single_exit (loop
)->dest
)
1905 update_e
= EDGE_PRED (preheader
, 0);
1907 update_e
= EDGE_PRED (preheader
, 1);
1909 /* Update IVs of original loop as if they were advanced
1910 by ratio_mult_vf_name steps. */
1911 vect_update_ivs_after_vectorizer (loop_vinfo
, ratio_mult_vf_name
, update_e
);
1913 max_iter
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1;
1914 if (check_profitability
)
1915 max_iter
= MAX (max_iter
, (int) th
);
1916 record_niter_bound (new_loop
, shwi_to_double_int (max_iter
), false, true);
1917 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1918 fprintf (dump_file
, "Setting upper bound of nb iterations for epilogue "
1919 "loop to %d\n", max_iter
);
1921 /* After peeling we have to reset scalar evolution analyzer. */
1924 free_original_copy_tables ();
1928 /* Function vect_gen_niters_for_prolog_loop
1930 Set the number of iterations for the loop represented by LOOP_VINFO
1931 to the minimum between LOOP_NITERS (the original iteration count of the loop)
1932 and the misalignment of DR - the data reference recorded in
1933 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of
1934 this loop, the data reference DR will refer to an aligned location.
1936 The following computation is generated:
1938 If the misalignment of DR is known at compile time:
1939 addr_mis = int mis = DR_MISALIGNMENT (dr);
1940 Else, compute address misalignment in bytes:
1941 addr_mis = addr & (vectype_size - 1)
1943 prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
1945 (elem_size = element type size; an element is the scalar element whose type
1946 is the inner type of the vectype)
1948 When the step of the data-ref in the loop is not 1 (as in interleaved data
1949 and SLP), the number of iterations of the prolog must be divided by the step
1950 (which is equal to the size of interleaved group).
1952 The above formulas assume that VF == number of elements in the vector. This
1953 may not hold when there are multiple-types in the loop.
1954 In this case, for some data-references in the loop the VF does not represent
1955 the number of elements that fit in the vector. Therefore, instead of VF we
1956 use TYPE_VECTOR_SUBPARTS. */
1959 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo
, tree loop_niters
)
1961 struct data_reference
*dr
= LOOP_VINFO_UNALIGNED_DR (loop_vinfo
);
1962 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
1965 tree iters
, iters_name
;
1968 gimple dr_stmt
= DR_STMT (dr
);
1969 stmt_vec_info stmt_info
= vinfo_for_stmt (dr_stmt
);
1970 tree vectype
= STMT_VINFO_VECTYPE (stmt_info
);
1971 int vectype_align
= TYPE_ALIGN (vectype
) / BITS_PER_UNIT
;
1972 tree niters_type
= TREE_TYPE (loop_niters
);
1973 int nelements
= TYPE_VECTOR_SUBPARTS (vectype
);
1975 pe
= loop_preheader_edge (loop
);
1977 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
) > 0)
1979 int npeel
= LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo
);
1981 if (vect_print_dump_info (REPORT_DETAILS
))
1982 fprintf (vect_dump
, "known peeling = %d.", npeel
);
1984 iters
= build_int_cst (niters_type
, npeel
);
1988 gimple_seq new_stmts
= NULL
;
1989 bool negative
= tree_int_cst_compare (DR_STEP (dr
), size_zero_node
) < 0;
1990 tree offset
= negative
1991 ? size_int (-TYPE_VECTOR_SUBPARTS (vectype
) + 1) : NULL_TREE
;
1992 tree start_addr
= vect_create_addr_base_for_vector_ref (dr_stmt
,
1993 &new_stmts
, offset
, loop
);
1994 tree type
= unsigned_type_for (TREE_TYPE (start_addr
));
1995 tree vectype_size_minus_1
= build_int_cst (type
, vectype_align
- 1);
1996 tree elem_size_log
=
1997 build_int_cst (type
, exact_log2 (vectype_align
/nelements
));
1998 tree nelements_minus_1
= build_int_cst (type
, nelements
- 1);
1999 tree nelements_tree
= build_int_cst (type
, nelements
);
2003 new_bb
= gsi_insert_seq_on_edge_immediate (pe
, new_stmts
);
2004 gcc_assert (!new_bb
);
2006 /* Create: byte_misalign = addr & (vectype_size - 1) */
2008 fold_build2 (BIT_AND_EXPR
, type
, fold_convert (type
, start_addr
),
2009 vectype_size_minus_1
);
2011 /* Create: elem_misalign = byte_misalign / element_size */
2013 fold_build2 (RSHIFT_EXPR
, type
, byte_misalign
, elem_size_log
);
2015 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */
2017 iters
= fold_build2 (MINUS_EXPR
, type
, elem_misalign
, nelements_tree
);
2019 iters
= fold_build2 (MINUS_EXPR
, type
, nelements_tree
, elem_misalign
);
2020 iters
= fold_build2 (BIT_AND_EXPR
, type
, iters
, nelements_minus_1
);
2021 iters
= fold_convert (niters_type
, iters
);
2024 /* Create: prolog_loop_niters = min (iters, loop_niters) */
2025 /* If the loop bound is known at compile time we already verified that it is
2026 greater than vf; since the misalignment ('iters') is at most vf, there's
2027 no need to generate the MIN_EXPR in this case. */
2028 if (TREE_CODE (loop_niters
) != INTEGER_CST
)
2029 iters
= fold_build2 (MIN_EXPR
, niters_type
, iters
, loop_niters
);
2031 if (vect_print_dump_info (REPORT_DETAILS
))
2033 fprintf (vect_dump
, "niters for prolog loop: ");
2034 print_generic_expr (vect_dump
, iters
, TDF_SLIM
);
2037 var
= create_tmp_var (niters_type
, "prolog_loop_niters");
2038 add_referenced_var (var
);
2040 iters_name
= force_gimple_operand (iters
, &stmts
, false, var
);
2042 /* Insert stmt on loop preheader edge. */
2045 basic_block new_bb
= gsi_insert_seq_on_edge_immediate (pe
, stmts
);
2046 gcc_assert (!new_bb
);
2053 /* Function vect_update_init_of_dr
2055 NITERS iterations were peeled from LOOP. DR represents a data reference
2056 in LOOP. This function updates the information recorded in DR to
2057 account for the fact that the first NITERS iterations had already been
2058 executed. Specifically, it updates the OFFSET field of DR. */
2061 vect_update_init_of_dr (struct data_reference
*dr
, tree niters
)
2063 tree offset
= DR_OFFSET (dr
);
2065 niters
= fold_build2 (MULT_EXPR
, sizetype
,
2066 fold_convert (sizetype
, niters
),
2067 fold_convert (sizetype
, DR_STEP (dr
)));
2068 offset
= fold_build2 (PLUS_EXPR
, sizetype
,
2069 fold_convert (sizetype
, offset
), niters
);
2070 DR_OFFSET (dr
) = offset
;
2074 /* Function vect_update_inits_of_drs
2076 NITERS iterations were peeled from the loop represented by LOOP_VINFO.
2077 This function updates the information recorded for the data references in
2078 the loop to account for the fact that the first NITERS iterations had
2079 already been executed. Specifically, it updates the initial_condition of
2080 the access_function of all the data_references in the loop. */
2083 vect_update_inits_of_drs (loop_vec_info loop_vinfo
, tree niters
)
2086 VEC (data_reference_p
, heap
) *datarefs
= LOOP_VINFO_DATAREFS (loop_vinfo
);
2087 struct data_reference
*dr
;
2089 if (vect_print_dump_info (REPORT_DETAILS
))
2090 fprintf (vect_dump
, "=== vect_update_inits_of_dr ===");
2092 FOR_EACH_VEC_ELT (data_reference_p
, datarefs
, i
, dr
)
2093 vect_update_init_of_dr (dr
, niters
);
2097 /* Function vect_do_peeling_for_alignment
2099 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
2100 'niters' is set to the misalignment of one of the data references in the
2101 loop, thereby forcing it to refer to an aligned location at the beginning
2102 of the execution of this loop. The data reference for which we are
2103 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */
2106 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo
,
2107 unsigned int th
, bool check_profitability
)
2109 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2110 tree niters_of_prolog_loop
, ni_name
;
2112 tree wide_prolog_niters
;
2113 struct loop
*new_loop
;
2116 if (vect_print_dump_info (REPORT_DETAILS
))
2117 fprintf (vect_dump
, "=== vect_do_peeling_for_alignment ===");
2119 initialize_original_copy_tables ();
2121 ni_name
= vect_build_loop_niters (loop_vinfo
, NULL
);
2122 niters_of_prolog_loop
= vect_gen_niters_for_prolog_loop (loop_vinfo
,
2125 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */
2127 slpeel_tree_peel_loop_to_edge (loop
, loop_preheader_edge (loop
),
2128 &niters_of_prolog_loop
, ni_name
, true,
2129 th
, check_profitability
, NULL_TREE
, NULL
);
2131 gcc_assert (new_loop
);
2132 #ifdef ENABLE_CHECKING
2133 slpeel_verify_cfg_after_peeling (new_loop
, loop
);
2135 max_iter
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
) - 1;
2136 if (check_profitability
)
2137 max_iter
= MAX (max_iter
, (int) th
);
2138 record_niter_bound (new_loop
, shwi_to_double_int (max_iter
), false, true);
2139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2140 fprintf (dump_file
, "Setting upper bound of nb iterations for prologue "
2141 "loop to %d\n", max_iter
);
2143 /* Update number of times loop executes. */
2144 n_iters
= LOOP_VINFO_NITERS (loop_vinfo
);
2145 LOOP_VINFO_NITERS (loop_vinfo
) = fold_build2 (MINUS_EXPR
,
2146 TREE_TYPE (n_iters
), n_iters
, niters_of_prolog_loop
);
2148 if (types_compatible_p (sizetype
, TREE_TYPE (niters_of_prolog_loop
)))
2149 wide_prolog_niters
= niters_of_prolog_loop
;
2152 gimple_seq seq
= NULL
;
2153 edge pe
= loop_preheader_edge (loop
);
2154 tree wide_iters
= fold_convert (sizetype
, niters_of_prolog_loop
);
2155 tree var
= create_tmp_var (sizetype
, "prolog_loop_adjusted_niters");
2156 add_referenced_var (var
);
2157 wide_prolog_niters
= force_gimple_operand (wide_iters
, &seq
, false,
2161 /* Insert stmt on loop preheader edge. */
2162 basic_block new_bb
= gsi_insert_seq_on_edge_immediate (pe
, seq
);
2163 gcc_assert (!new_bb
);
2167 /* Update the init conditions of the access functions of all data refs. */
2168 vect_update_inits_of_drs (loop_vinfo
, wide_prolog_niters
);
2170 /* After peeling we have to reset scalar evolution analyzer. */
2173 free_original_copy_tables ();
2177 /* Function vect_create_cond_for_align_checks.
2179 Create a conditional expression that represents the alignment checks for
2180 all of data references (array element references) whose alignment must be
2184 COND_EXPR - input conditional expression. New conditions will be chained
2185 with logical AND operation.
2186 LOOP_VINFO - two fields of the loop information are used.
2187 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
2188 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
2191 COND_EXPR_STMT_LIST - statements needed to construct the conditional
2193 The returned value is the conditional expression to be used in the if
2194 statement that controls which version of the loop gets executed at runtime.
2196 The algorithm makes two assumptions:
2197 1) The number of bytes "n" in a vector is a power of 2.
2198 2) An address "a" is aligned if a%n is zero and that this
2199 test can be done as a&(n-1) == 0. For example, for 16
2200 byte vectors the test is a&0xf == 0. */
2203 vect_create_cond_for_align_checks (loop_vec_info loop_vinfo
,
2205 gimple_seq
*cond_expr_stmt_list
)
2207 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2208 VEC(gimple
,heap
) *may_misalign_stmts
2209 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo
);
2211 int mask
= LOOP_VINFO_PTR_MASK (loop_vinfo
);
2214 tree int_ptrsize_type
;
2216 tree or_tmp_name
= NULL_TREE
;
2217 tree and_tmp
, and_tmp_name
;
2220 tree part_cond_expr
;
2222 /* Check that mask is one less than a power of 2, i.e., mask is
2223 all zeros followed by all ones. */
2224 gcc_assert ((mask
!= 0) && ((mask
& (mask
+1)) == 0));
2226 int_ptrsize_type
= signed_type_for (ptr_type_node
);
2228 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
2229 of the first vector of the i'th data reference. */
2231 FOR_EACH_VEC_ELT (gimple
, may_misalign_stmts
, i
, ref_stmt
)
2233 gimple_seq new_stmt_list
= NULL
;
2235 tree addr_tmp
, addr_tmp_name
;
2236 tree or_tmp
, new_or_tmp_name
;
2237 gimple addr_stmt
, or_stmt
;
2238 stmt_vec_info stmt_vinfo
= vinfo_for_stmt (ref_stmt
);
2239 tree vectype
= STMT_VINFO_VECTYPE (stmt_vinfo
);
2240 bool negative
= tree_int_cst_compare
2241 (DR_STEP (STMT_VINFO_DATA_REF (stmt_vinfo
)), size_zero_node
) < 0;
2242 tree offset
= negative
2243 ? size_int (-TYPE_VECTOR_SUBPARTS (vectype
) + 1) : NULL_TREE
;
2245 /* create: addr_tmp = (int)(address_of_first_vector) */
2247 vect_create_addr_base_for_vector_ref (ref_stmt
, &new_stmt_list
,
2249 if (new_stmt_list
!= NULL
)
2250 gimple_seq_add_seq (cond_expr_stmt_list
, new_stmt_list
);
2252 sprintf (tmp_name
, "%s%d", "addr2int", i
);
2253 addr_tmp
= create_tmp_var (int_ptrsize_type
, tmp_name
);
2254 add_referenced_var (addr_tmp
);
2255 addr_tmp_name
= make_ssa_name (addr_tmp
, NULL
);
2256 addr_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, addr_tmp_name
,
2257 addr_base
, NULL_TREE
);
2258 SSA_NAME_DEF_STMT (addr_tmp_name
) = addr_stmt
;
2259 gimple_seq_add_stmt (cond_expr_stmt_list
, addr_stmt
);
2261 /* The addresses are OR together. */
2263 if (or_tmp_name
!= NULL_TREE
)
2265 /* create: or_tmp = or_tmp | addr_tmp */
2266 sprintf (tmp_name
, "%s%d", "orptrs", i
);
2267 or_tmp
= create_tmp_var (int_ptrsize_type
, tmp_name
);
2268 add_referenced_var (or_tmp
);
2269 new_or_tmp_name
= make_ssa_name (or_tmp
, NULL
);
2270 or_stmt
= gimple_build_assign_with_ops (BIT_IOR_EXPR
,
2272 or_tmp_name
, addr_tmp_name
);
2273 SSA_NAME_DEF_STMT (new_or_tmp_name
) = or_stmt
;
2274 gimple_seq_add_stmt (cond_expr_stmt_list
, or_stmt
);
2275 or_tmp_name
= new_or_tmp_name
;
2278 or_tmp_name
= addr_tmp_name
;
2282 mask_cst
= build_int_cst (int_ptrsize_type
, mask
);
2284 /* create: and_tmp = or_tmp & mask */
2285 and_tmp
= create_tmp_var (int_ptrsize_type
, "andmask" );
2286 add_referenced_var (and_tmp
);
2287 and_tmp_name
= make_ssa_name (and_tmp
, NULL
);
2289 and_stmt
= gimple_build_assign_with_ops (BIT_AND_EXPR
, and_tmp_name
,
2290 or_tmp_name
, mask_cst
);
2291 SSA_NAME_DEF_STMT (and_tmp_name
) = and_stmt
;
2292 gimple_seq_add_stmt (cond_expr_stmt_list
, and_stmt
);
2294 /* Make and_tmp the left operand of the conditional test against zero.
2295 if and_tmp has a nonzero bit then some address is unaligned. */
2296 ptrsize_zero
= build_int_cst (int_ptrsize_type
, 0);
2297 part_cond_expr
= fold_build2 (EQ_EXPR
, boolean_type_node
,
2298 and_tmp_name
, ptrsize_zero
);
2300 *cond_expr
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2301 *cond_expr
, part_cond_expr
);
2303 *cond_expr
= part_cond_expr
;
2307 /* Function vect_vfa_segment_size.
2309 Create an expression that computes the size of segment
2310 that will be accessed for a data reference. The functions takes into
2311 account that realignment loads may access one more vector.
2314 DR: The data reference.
2315 LENGTH_FACTOR: segment length to consider.
2317 Return an expression whose value is the size of segment which will be
2321 vect_vfa_segment_size (struct data_reference
*dr
, tree length_factor
)
2323 tree segment_length
;
2325 if (integer_zerop (DR_STEP (dr
)))
2326 segment_length
= TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
)));
2328 segment_length
= size_binop (MULT_EXPR
,
2329 fold_convert (sizetype
, DR_STEP (dr
)),
2330 fold_convert (sizetype
, length_factor
));
2332 if (vect_supportable_dr_alignment (dr
, false)
2333 == dr_explicit_realign_optimized
)
2335 tree vector_size
= TYPE_SIZE_UNIT
2336 (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr
))));
2338 segment_length
= size_binop (PLUS_EXPR
, segment_length
, vector_size
);
2340 return segment_length
;
2344 /* Function vect_create_cond_for_alias_checks.
2346 Create a conditional expression that represents the run-time checks for
2347 overlapping of address ranges represented by a list of data references
2348 relations passed as input.
2351 COND_EXPR - input conditional expression. New conditions will be chained
2352 with logical AND operation.
2353 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs
2357 COND_EXPR - conditional expression.
2358 COND_EXPR_STMT_LIST - statements needed to construct the conditional
2362 The returned value is the conditional expression to be used in the if
2363 statement that controls which version of the loop gets executed at runtime.
2367 vect_create_cond_for_alias_checks (loop_vec_info loop_vinfo
,
2369 gimple_seq
* cond_expr_stmt_list
)
2371 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2372 VEC (ddr_p
, heap
) * may_alias_ddrs
=
2373 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo
);
2374 int vect_factor
= LOOP_VINFO_VECT_FACTOR (loop_vinfo
);
2375 tree scalar_loop_iters
= LOOP_VINFO_NITERS (loop_vinfo
);
2379 tree part_cond_expr
, length_factor
;
2381 /* Create expression
2382 ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
2383 || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
2387 ((store_ptr_n + store_segment_length_n) <= load_ptr_n)
2388 || (load_ptr_n + load_segment_length_n) <= store_ptr_n)) */
2390 if (VEC_empty (ddr_p
, may_alias_ddrs
))
2393 FOR_EACH_VEC_ELT (ddr_p
, may_alias_ddrs
, i
, ddr
)
2395 struct data_reference
*dr_a
, *dr_b
;
2396 gimple dr_group_first_a
, dr_group_first_b
;
2397 tree addr_base_a
, addr_base_b
;
2398 tree segment_length_a
, segment_length_b
;
2399 gimple stmt_a
, stmt_b
;
2400 tree seg_a_min
, seg_a_max
, seg_b_min
, seg_b_max
;
2403 stmt_a
= DR_STMT (DDR_A (ddr
));
2404 dr_group_first_a
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a
));
2405 if (dr_group_first_a
)
2407 stmt_a
= dr_group_first_a
;
2408 dr_a
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_a
));
2412 stmt_b
= DR_STMT (DDR_B (ddr
));
2413 dr_group_first_b
= GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_b
));
2414 if (dr_group_first_b
)
2416 stmt_b
= dr_group_first_b
;
2417 dr_b
= STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_b
));
2421 vect_create_addr_base_for_vector_ref (stmt_a
, cond_expr_stmt_list
,
2424 vect_create_addr_base_for_vector_ref (stmt_b
, cond_expr_stmt_list
,
2427 if (!operand_equal_p (DR_STEP (dr_a
), DR_STEP (dr_b
), 0))
2428 length_factor
= scalar_loop_iters
;
2430 length_factor
= size_int (vect_factor
);
2431 segment_length_a
= vect_vfa_segment_size (dr_a
, length_factor
);
2432 segment_length_b
= vect_vfa_segment_size (dr_b
, length_factor
);
2434 if (vect_print_dump_info (REPORT_DR_DETAILS
))
2437 "create runtime check for data references ");
2438 print_generic_expr (vect_dump
, DR_REF (dr_a
), TDF_SLIM
);
2439 fprintf (vect_dump
, " and ");
2440 print_generic_expr (vect_dump
, DR_REF (dr_b
), TDF_SLIM
);
2443 seg_a_min
= addr_base_a
;
2444 seg_a_max
= fold_build_pointer_plus (addr_base_a
, segment_length_a
);
2445 if (tree_int_cst_compare (DR_STEP (dr_a
), size_zero_node
) < 0)
2446 seg_a_min
= seg_a_max
, seg_a_max
= addr_base_a
;
2448 seg_b_min
= addr_base_b
;
2449 seg_b_max
= fold_build_pointer_plus (addr_base_b
, segment_length_b
);
2450 if (tree_int_cst_compare (DR_STEP (dr_b
), size_zero_node
) < 0)
2451 seg_b_min
= seg_b_max
, seg_b_max
= addr_base_b
;
2454 fold_build2 (TRUTH_OR_EXPR
, boolean_type_node
,
2455 fold_build2 (LE_EXPR
, boolean_type_node
, seg_a_max
, seg_b_min
),
2456 fold_build2 (LE_EXPR
, boolean_type_node
, seg_b_max
, seg_a_min
));
2459 *cond_expr
= fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2460 *cond_expr
, part_cond_expr
);
2462 *cond_expr
= part_cond_expr
;
2465 if (vect_print_dump_info (REPORT_VECTORIZED_LOCATIONS
))
2466 fprintf (vect_dump
, "created %u versioning for alias checks.\n",
2467 VEC_length (ddr_p
, may_alias_ddrs
));
2471 /* Function vect_loop_versioning.
2473 If the loop has data references that may or may not be aligned or/and
2474 has data reference relations whose independence was not proven then
2475 two versions of the loop need to be generated, one which is vectorized
2476 and one which isn't. A test is then generated to control which of the
2477 loops is executed. The test checks for the alignment of all of the
2478 data references that may or may not be aligned. An additional
2479 sequence of runtime tests is generated for each pairs of DDRs whose
2480 independence was not proven. The vectorized version of loop is
2481 executed only if both alias and alignment tests are passed.
2483 The test generated to check which version of loop is executed
2484 is modified to also check for profitability as indicated by the
2485 cost model initially.
2487 The versioning precondition(s) are placed in *COND_EXPR and
2488 *COND_EXPR_STMT_LIST. */
2491 vect_loop_versioning (loop_vec_info loop_vinfo
,
2492 unsigned int th
, bool check_profitability
)
2494 struct loop
*loop
= LOOP_VINFO_LOOP (loop_vinfo
);
2495 basic_block condition_bb
;
2496 gimple_stmt_iterator gsi
, cond_exp_gsi
;
2497 basic_block merge_bb
;
2498 basic_block new_exit_bb
;
2500 gimple orig_phi
, new_phi
;
2501 tree cond_expr
= NULL_TREE
;
2502 gimple_seq cond_expr_stmt_list
= NULL
;
2504 unsigned prob
= 4 * REG_BR_PROB_BASE
/ 5;
2505 gimple_seq gimplify_stmt_list
= NULL
;
2506 tree scalar_loop_iters
= LOOP_VINFO_NITERS (loop_vinfo
);
2508 if (check_profitability
)
2510 cond_expr
= fold_build2 (GT_EXPR
, boolean_type_node
, scalar_loop_iters
,
2511 build_int_cst (TREE_TYPE (scalar_loop_iters
), th
));
2512 cond_expr
= force_gimple_operand_1 (cond_expr
, &cond_expr_stmt_list
,
2513 is_gimple_condexpr
, NULL_TREE
);
2516 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo
))
2517 vect_create_cond_for_align_checks (loop_vinfo
, &cond_expr
,
2518 &cond_expr_stmt_list
);
2520 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo
))
2521 vect_create_cond_for_alias_checks (loop_vinfo
, &cond_expr
,
2522 &cond_expr_stmt_list
);
2524 cond_expr
= force_gimple_operand_1 (cond_expr
, &gimplify_stmt_list
,
2525 is_gimple_condexpr
, NULL_TREE
);
2526 gimple_seq_add_seq (&cond_expr_stmt_list
, gimplify_stmt_list
);
2528 initialize_original_copy_tables ();
2529 loop_version (loop
, cond_expr
, &condition_bb
,
2530 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
2531 free_original_copy_tables();
2533 /* Loop versioning violates an assumption we try to maintain during
2534 vectorization - that the loop exit block has a single predecessor.
2535 After versioning, the exit block of both loop versions is the same
2536 basic block (i.e. it has two predecessors). Just in order to simplify
2537 following transformations in the vectorizer, we fix this situation
2538 here by adding a new (empty) block on the exit-edge of the loop,
2539 with the proper loop-exit phis to maintain loop-closed-form. */
2541 merge_bb
= single_exit (loop
)->dest
;
2542 gcc_assert (EDGE_COUNT (merge_bb
->preds
) == 2);
2543 new_exit_bb
= split_edge (single_exit (loop
));
2544 new_exit_e
= single_exit (loop
);
2545 e
= EDGE_SUCC (new_exit_bb
, 0);
2547 for (gsi
= gsi_start_phis (merge_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2549 orig_phi
= gsi_stmt (gsi
);
2550 new_phi
= create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi
)),
2552 arg
= PHI_ARG_DEF_FROM_EDGE (orig_phi
, e
);
2553 add_phi_arg (new_phi
, arg
, new_exit_e
,
2554 gimple_phi_arg_location_from_edge (orig_phi
, e
));
2555 adjust_phi_and_debug_stmts (orig_phi
, e
, PHI_RESULT (new_phi
));
2558 /* End loop-exit-fixes after versioning. */
2560 update_ssa (TODO_update_ssa
);
2561 if (cond_expr_stmt_list
)
2563 cond_exp_gsi
= gsi_last_bb (condition_bb
);
2564 gsi_insert_seq_before (&cond_exp_gsi
, cond_expr_stmt_list
,