contrib/gcc/tree-vectorizer.c

29    For example, the vectorizer transforms the following simple loop:
72    loop, as well as general information about the loop as a whole, which is
73    recorded in a "loop_vec_info" struct attached to each loop.
77 	The loop transformation phase scans all the stmts in the loop, and
79    the loop that needs to be vectorized. It insert the vector code sequence
152 static struct loop *slpeel_tree_duplicate_loop_to_edge_cfg
153   (struct loop *, struct loops *, edge);
155   (struct loop *, struct loop *, bool after);
157   (edge, struct loop *, bool, basic_block *, bitmap *);
159   (edge, struct loop *, bool, basic_block *);
164 static void rename_variables_in_loop (struct loop *);
191   Utilities to support loop peeling for vectorization purposes.
207   /* Something defined outside of the loop.  */
211   /* An ordinary ssa name defined in the loop.  */
229   struct loop *loop = bb->loop_father;
241       if (!flow_bb_inside_loop_p (loop, e->dest))
252 rename_variables_in_loop (struct loop *loop)
257   bbs = get_loop_body (loop);
259   for (i = 0; i < loop->num_nodes; i++)
274 slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
275 				       struct loop *new_loop, bool after)
287      step 1. For each loop-header-phi:
291      step 2. For each loop-header-phi:
300                 along with the scanning of the loop header phis, because the
306                 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
308                 loop guards are added).
333 	     inside the loop. use the phi_result in this case.  */
337       /* An ordinary ssa name defined in the loop.  */
355    - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
358         bb of LOOP.  This loop-exit-bb is an empty bb with one successor.
364         and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
404    2. preserves loop-closed-ssa-form by creating the required phi nodes
412      for variables that have phis in the loop header.
417      for variables that have phis in the loop exit.
443    to create correct data-flow and loop-closed-ssa-form.
446    that change between iterations of a loop (and therefore have a phi-node
447    at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
448    phis for variables that are used out of the loop (and therefore have
449    loop-closed exit phis). Some variables may be both updated between
450    iterations and used after the loop. This is why in loop1_exit_bb we
455      an original loop. i.e., we have:
464      If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
474      The SSA names defined in the original loop have a current
476      ssa-name used in the new duplicated loop copy.
499    For each name updated between loop iterations (i.e - for each name that has
500    an entry (loop-header) phi in LOOP) we create a new phi in:
502    2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
506 slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
516   basic_block orig_bb = loop->header;
521   /* Create new bb between loop and new_merge_bb.  */
522   *new_exit_bb = split_edge (loop->single_exit);
523   add_bb_to_loop (*new_exit_bb, loop->outer);
548       loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
549       guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
561       /** 2. Handle loop-closed-ssa-form phis  **/
567       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
568       add_phi_arg (new_phi, loop_arg, loop->single_exit);
580          If LOOP is a new loop then loop_arg is already the name we're
581          looking for. If LOOP is the original loop, then loop_arg is
590 	     change inside the loop, in which case we also don't care
592 	     trying to create loop-exit-phis for it.  */
624    For each name used out side the loop (i.e - for each name that has an exit
627    2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
628    3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
633 slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
647   /* Create new bb between loop and new_merge_bb.  */
648   *new_exit_bb = split_edge (loop->single_exit);
649   add_bb_to_loop (*new_exit_bb, loop->outer);
658       /* This loop-closed-phi actually doesn't represent a use
659          out of the loop - the phi arg is a constant.  */
678 	  /* Some variables have both loop-entry-phis and loop-exit-phis.
707       /** 2. Handle loop-closed-ssa-form phis  **/
713       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
714       add_phi_arg (new_phi, loop_arg, loop->single_exit);
721       /** 3. Handle loop-closed-ssa-form phis for first loop  **/
727 	 the loop (and therefore need an exit phi) but are not updated
728 	 across loop iterations (and therefore don't have a
729 	 loop-header-phi).
732 	 creating loop-exit phis in GUARD_BB for names that have a
733 	 loop-header-phi.  When such a phi is created we also record
764    Assumption: the exit-condition of LOOP is the last stmt in the loop.  */
767 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
771   edge exit_edge = loop->single_exit;
775   tree begin_label = tree_block_label (loop->latch);
776   tree exit_label = tree_block_label (loop->single_exit->dest);
783   orig_cond = get_loop_exit_condition (loop);
787   standard_iv_increment_position (loop, &incr_bsi, &insert_after);
788   create_iv (init, step, NULL_TREE, loop,
791   if (exit_edge->flags & EDGE_TRUE_VALUE) /* 'then' edge exits the loop.  */
808   /* Remove old loop exit test:  */
811   loop_loc = find_loop_location (loop);
820   loop->nb_iterations = niters;
827 static struct loop *
828 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, struct loops *loops,
831   struct loop *new_loop;
838   at_exit = (e == loop->single_exit);
839   if (!at_exit && e != loop_preheader_edge (loop))
842   bbs = get_loop_body (loop);
845   if (!can_copy_bbs_p (bbs, loop->num_nodes))
851   /* Generate new loop structure.  */
852   new_loop = duplicate_loop (loops, loop, loop->outer);
859   exit_dest = loop->single_exit->dest;
861 					  exit_dest) == loop->header ?
864   new_bbs = XNEWVEC (basic_block, loop->num_nodes);
866   copy_bbs (bbs, loop->num_nodes, new_bbs,
867 	    &loop->single_exit, 1, &new_loop->single_exit, NULL,
871      also from exit of duplicated loop.  */
874       phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, loop->single_exit);
888   if (at_exit) /* Add the loop copy at exit.  */
898       edge entry_e = loop_preheader_edge (loop);
907       redirect_edge_and_branch_force (new_exit_e, loop->header);
908       set_immediate_dominator (CDI_DOMINATORS, loop->header,
911       /* We have to add phi args to the loop->header here as coming
913       for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
932    of GUARD_BB; EXIT_BB is the basic block to skip the loop;
933    Assumes that this is the single exit of the guarded loop.
956   /* Add new edge to connect guard block to the merge/loop-exit block.  */
972 slpeel_can_duplicate_loop_p (struct loop *loop, edge e)
974   edge exit_e = loop->single_exit;
975   edge entry_e = loop_preheader_edge (loop);
976   tree orig_cond = get_loop_exit_condition (loop);
982   if (loop->inner
983       /* All loops have an outer scope; the only case loop->outer is NULL is for
985       || !loop->outer
986       || loop->num_nodes != 2
987       || !empty_block_p (loop->latch)
988       || !loop->single_exit
989       /* Verify that new loop exit condition can be trivially modified.  */
999 slpeel_verify_cfg_after_peeling (struct loop *first_loop,
1000                                  struct loop *second_loop)
1033    Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
1035    we have two loops one after the other - first-loop iterates FIRST_NITERS
1036    times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
1039    - LOOP: the loop to be peeled.
1042         case first-loop is LOOP, and second-loop is the newly created loop.
1044         case, first-loop is the newly created loop, and second-loop is LOOP.
1046    - FIRST_NITERS: the number of iterations that the first-loop should iterate.
1048         for updating the loop bound of the first-loop to FIRST_NITERS.  If it
1050         (this can be useful if we don't want new stmts added to first-loop).
1053    The function returns a pointer to the new loop-copy, or NULL if it failed
1056    The function generates two if-then-else guards: one before the first loop,
1057    and the other before the second loop:
1059      if (FIRST_NITERS == 0) then skip the first loop,
1060      and go directly to the second loop.
1062      if (FIRST_NITERS == NITERS) then skip the second loop.
1065    FORNOW the resulting code will not be in loop-closed-ssa form.
1068 struct loop*
1069 slpeel_tree_peel_loop_to_edge (struct loop *loop, struct loops *loops,
1073   struct loop *new_loop = NULL, *first_loop, *second_loop;
1081   edge exit_e = loop->single_exit;
1084   if (!slpeel_can_duplicate_loop_p (loop, e))
1108   if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, loops, e)))
1110       loop_loc = find_loop_location (loop);
1124       first_loop = loop;
1131       second_loop = loop;
1135   slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
1139   /* 2. Add the guard that controls whether the first loop is executed.
1144                                GOTO first-loop
1174   /* 3. Add the guard that controls whether the second loop is executed.
1178         if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1179                                GOTO first-loop
1186         if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1211   /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1224    Extract the location of the loop in the source code.
1225    If the loop is not well formed for vectorization, an estimated
1227    Return the loop location if succeed and NULL if not.  */
1230 find_loop_location (struct loop *loop)
1236   if (!loop)
1239   node = get_loop_exit_condition (loop);
1245   /* If we got here the loop is probably not "well formed",
1246      try to estimate the loop location */
1248   if (!loop->header)
1251   bb = loop->header;
1386 new_loop_vec_info (struct loop *loop)
1395   bbs = get_loop_body (loop);
1397   /* Create stmt_info for all stmts in the loop.  */
1398   for (i = 0; i < loop->num_nodes; i++)
1419   LOOP_VINFO_LOOP (res) = loop;
1439    stmts in the loop.  */
1444   struct loop *loop;
1453   loop = LOOP_VINFO_LOOP (loop_vinfo);
1456   nbbs = loop->num_nodes;
1628    LOOP - the loop that is being vectorized.
1633    Supportable operands are constants, loop invariants, and operands that are
1634    defined by the current iteration of the loop. Unsupportable operands are
1635    those that are defined by a previous iteration of the loop (as is the case
1644   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1700   if (!flow_bb_inside_loop_p (loop, bb))
1715   /* stmts inside the loop that have been identified as performing
1716      a reduction operation cannot have uses in the loop.  */
1720         fprintf (vect_dump, "reduction used in loop.");
1806    2. no uses for a2 in the loop (a2 is used out of the loop)
1807    3. no uses of a1 in the loop besides the reduction operation.
1813 vect_is_simple_reduction (struct loop *loop, tree phi)
1815   edge latch_e = loop_latch_edge (loop);
1941       && flow_bb_inside_loop_p (loop, bb_for_stmt (def1))
1952       && flow_bb_inside_loop_p (loop, bb_for_stmt (def2))
1981    FORNOW: A simple evolution of an induction variables in the loop is
1993   /* When there is no evolution in this loop, the evolution function
2031    Entry Point to loop vectorization phase.  */
2048   /* If some loop was duplicated, it gets bigger number
2055       struct loop *loop = loops->parray[i];
2057       if (!loop)
2060       vect_loop_location = find_loop_location (loop);
2061       loop_vinfo = vect_analyze_loop (loop);
2062       loop->aux = loop_vinfo;
2082       struct loop *loop = loops->parray[i];
2085       if (!loop)
2087       loop_vinfo = loop->aux;
2089       loop->aux = NULL;