gcc/gcc/tree-ssa-loop-ivcanon.c

1 /* Induction variable canonicalization and loop peeling.
34      - simple peeling (i.e. copying few initial iterations prior the loop)
81 #include "tree-ssa-loop-manip.h"
82 #include "tree-ssa-loop-niter.h"
83 #include "tree-ssa-loop.h"
111 create_canonical_iv (struct loop *loop, edge exit, tree niter)
121       fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
143 	     NULL_TREE, loop,
153 /* Describe size of loop as detected by tree_estimate_loop_size.  */
156   /* Number of instructions in the loop.  */
160      peeled iterations of loop  (i.e. computation based on induction
164   /* Same statistics for last iteration of loop: it is smaller because
178   /* Number of statements other than calls in the loop.  */
187 constant_after_peeling (tree op, gimple stmt, struct loop *loop)
211 		  && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
221   if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false))
232    iteration of the loop.
234    of loop.
239 tree_estimate_loop_size (struct loop *loop, edge exit, edge edge_to_cancel, struct loop_size *size,
242   basic_block *body = get_loop_body (loop);
246   vec<basic_block> path = get_loop_hot_path (loop);
259     fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
260   for (i = 0; i < loop->num_nodes; i++)
307 	      && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
317 		   && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt, loop)
320 		       				  stmt, loop)))
329 		    && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
330 		    && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop))
334 						  stmt, loop)))
383 	        && (!constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
384 		    || constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop)))
388 					       stmt, loop)))
403 /* Estimate number of insns of completely unrolled loop.
404    It is (NUNROLL + 1) * size of loop body with taking into account
430 /* Loop LOOP is known to not loop.  See if there is an edge in the loop
431    body that can be remove to make the loop to always exit and at
443    Here we prove the loop to iterate 5 times but we do not know
448    with side effect that may otherwise terminate the execution of loop
452    loop-niter identified as having undefined effect in the last iteration.
456 loop_edge_to_cancel (struct loop *loop)
463   /* We want only one predecestor of the loop.  */
464   if (EDGE_COUNT (loop->latch->preds) > 1)
467   exits = get_loop_exit_edges (loop);
471        /* Find the other edge than the loop exit
484       /* We should never have conditionals in the loop latch. */
485       gcc_assert (edge_to_cancel->dest != loop->header);
487       /* Check that it leads to loop latch.  */
488       if (edge_to_cancel->dest != loop->latch)
493       /* Verify that the code in loop latch does nothing that may end program
496       for (gsi = gsi_start_bb (loop->latch); !gsi_end_p (gsi); gsi_next (&gsi))
510 remove_exits_and_undefined_stmts (struct loop *loop, unsigned int npeeled)
515   for (elt = loop->bounds; elt; elt = elt->next)
548 	  if (!loop_exit_edge_p (loop, exit_edge))
550 	  gcc_checking_assert (loop_exit_edge_p (loop, exit_edge));
563 /* Remove all exits that are known to be never taken because of the loop bound
567 remove_redundant_iv_tests (struct loop *loop)
572   if (!loop->any_upper_bound)
574   for (elt = loop->bounds; elt; elt = elt->next)
576       /* Exit is pointless if it won't be taken before loop reaches
578       if (elt->is_exit && loop->any_upper_bound
579           && wi::ltu_p (loop->nb_iterations_upper_bound, elt->bound))
585 	  if (!loop_exit_edge_p (loop, exit_edge))
590 	  if (!number_of_iterations_exit (loop, exit_edge,
596 	      || !wi::ltu_p (loop->nb_iterations_upper_bound,
617 /* Stores loops that will be unlooped after we process whole loop tree. */
624    across loop boundaries trashing loop closed SSA form as well
631    when we need to go into loop closed SSA form.  */
639       struct loop *loop = loops_to_unloop.pop ();
641       basic_block latch = loop->latch;
642       edge latch_edge = loop_latch_edge (loop);
648       remove_exits_and_undefined_stmts (loop, n_unroll);
651       unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
676    EXIT is the exit of the loop that should be eliminated.
679    LOCUS corresponding to the loop is used when emitting
683 try_unroll_loop_completely (struct loop *loop,
698      the loop.
701      of the unrolled sequence and is expected to make the final loop not
704      If the number of execution of loop is determined by standard induction
720   /* See if we can improve our estimate by using recorded loop bounds.  */
737 	fprintf (dump_file, "Not unrolling loop %d "
739 		 loop->num);
744     edge_to_cancel = loop_edge_to_cancel (loop);
757 		 (loop, exit, edge_to_cancel, &size,
763 	    fprintf (dump_file, "Not unrolling loop %d: it is too large.\n",
764 		     loop->num);
780 	     one instruction in the loop prologue we do not account
785 	 otheriwse.  We still can cancel loopback edge of not rolling loop;
790 	    fprintf (dump_file, "Not unrolling loop %d: size would grow.\n",
791 		     loop->num);
795 	 unrolling unless we can do a lot of propagation into the inner loop
796 	 body.  For now we disable outer loop unrolling when the code would
798       else if (loop->inner)
801 	    fprintf (dump_file, "Not unrolling loop %d: "
803 		     loop->num);
806       /* If there is call on a hot path through the loop, then
811 	    fprintf (dump_file, "Not unrolling loop %d: "
813 		     loop->num);
817 	 can still optimize the unrolled loop body if it contains
822 		  and one useful stmt.  That is about minimal loop
828 	    fprintf (dump_file, "Not unrolling loop %d: "
830 		     loop->num);
834 	 one big basic block is created.  If the loop contains control flow
835 	 the optimization may still be a win because of eliminating the loop
843 	    fprintf (dump_file, "Not unrolling loop %d: "
846 		     loop->num);
853 	    fprintf (dump_file, "Not unrolling loop %d: "
855 		     loop->num);
859                        "loop turned into non-loop; it never loops.\n");
866       if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
875 	    fprintf (dump_file, "Failed to duplicate the loop\n");
891   /* Remove the conditional from the last copy of the loop.  */
900       /* Do not remove the path. Doing so may remove outer loop
904   /* Store the loop for later unlooping and exit removal.  */
905   loops_to_unloop.safe_push (loop);
912                          "loop turned into non-loop; it never loops\n");
916                            "loop with %d iterations completely unrolled",
921                          (int)loop->header->count);
950 /* If the loop is expected to iterate N times and is
951    small enough, duplicate the loop body N+1 times before
952    the loop itself.  This way the hot path will never
953    enter the loop.
957 try_peel_loop (struct loop *loop,
978   if (loop->inner)
981         fprintf (dump_file, "Not peeling: outer loop\n");
985   if (!optimize_loop_for_speed_p (loop))
988         fprintf (dump_file, "Not peeling: cold loop\n");
993   npeel = estimated_loop_iterations_int (loop);
1010      enter the loop on quick path).  Check against PARAM_MAX_PEEL_TIMES
1022   tree_estimate_loop_size (loop, exit, NULL, &size,
1038   if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1057       fprintf (dump_file, "Peeled loop %d, %i times.\n",
1058 	       loop->num, npeel);
1060   if (loop->any_upper_bound)
1061     loop->nb_iterations_upper_bound -= npeel;
1062   loop->nb_iterations_estimate = 0;
1063   /* Make sure to mark loop cold so we do not try to peel it more.  */
1064   scale_loop_profile (loop, 1, 0);
1065   loop->header->count = 0;
1071    to determine the number of iterations of a loop by direct evaluation.
1075 canonicalize_loop_induction_variables (struct loop *loop,
1085   niter = number_of_latch_executions (loop);
1086   exit = single_exit (loop);
1091       /* If the loop has more than one exit, try checking all of them
1094 	niter = find_loop_niter (loop, &exit);
1100 	niter = find_loop_niter_by_eval (loop, &exit);
1113       record_niter_bound (loop, wi::to_widest (niter),
1114 			  exit == single_likely_exit (loop), true);
1117   /* Force re-computation of loop bounds so we can remove redundant exits.  */
1118   maxiter = max_loop_iterations_int (loop);
1123       fprintf (dump_file, "Loop %d iterates ", loop->num);
1130       fprintf (dump_file, "Loop %d iterates at most %i times.\n", loop->num,
1134   /* Remove exits that are known to be never taken based on loop bound.
1136      populates the loop bounds.  */
1137   modified |= remove_redundant_iv_tests (loop);
1139   if (try_unroll_loop_completely (loop, exit, niter, ul, maxiter, locus))
1144       && exit && just_once_each_iteration_p (loop, exit->src))
1145     create_canonical_iv (loop, exit, niter);
1148     modified |= try_peel_loop (loop, exit, niter, maxiter);
1159   struct loop *loop;
1167   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1169       changed |= canonicalize_loop_induction_variables (loop,
1241    loop we unrolled.  */
1246 				struct loop *loop)
1248   struct loop *loop_father;
1250   struct loop *inner;
1254   for (inner = loop->inner; inner != NULL; inner = inner->next)
1259   /* If we changed an inner loop we cannot process outer loops in this
1267   if (loop->force_vectorize)
1270   /* Try to unroll this loop.  */
1271   loop_father = loop_outer (loop);
1275   if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
1284         (loop, false, ul, !flag_tree_loop_ivcanon))
1330 	  struct loop **iter;
1364 	     from the loop structures so we can continue unrolling now