37 /* This pass performs loop unrolling and peeling.  We only perform these
48       exception, as this causes loop to be cancelled completely and
68    how many times we should unroll the loop; the experiments I have made
104    the unrolled loop.  */
113   basic_block loop_exit;           /* The loop exit basic block.  */
114   basic_block loop_preheader;      /* The loop preheader basic block.  */
119 static void decide_peel_simple (struct loop *, int);
120 static void decide_peel_once_rolling (struct loop *, int);
121 static void decide_peel_completely (struct loop *, int);
122 static void decide_unroll_stupid (struct loop *, int);
123 static void decide_unroll_constant_iterations (struct loop *, int);
124 static void decide_unroll_runtime_iterations (struct loop *, int);
125 static void peel_loop_simple (struct loops *, struct loop *);
126 static void peel_loop_completely (struct loops *, struct loop *);
127 static void unroll_loop_stupid (struct loops *, struct loop *);
128 static void unroll_loop_constant_iterations (struct loops *, struct loop *);
129 static void unroll_loop_runtime_iterations (struct loops *, struct loop *);
130 static struct opt_info *analyze_insns_in_loop (struct loop *);
134 static struct var_to_expand *analyze_insn_to_expand_var (struct loop*, rtx);
135 static bool referenced_in_one_insn_in_loop_p (struct loop *, rtx);
147   struct loop *loop, *next;
150   /* First perform complete loop peeling (it is almost surely a win,
157   loop = loops->tree_root;
158   while (loop->inner)
159     loop = loop->inner;
162   while (loop != loops->tree_root)
164       if (loop->next)
166 	  next = loop->next;
171 	next = loop->outer;
175       switch (loop->lpt_decision.decision)
181 	  peel_loop_simple (loops, loop);
184 	  unroll_loop_constant_iterations (loops, loop);
187 	  unroll_loop_runtime_iterations (loops, loop);
190 	  unroll_loop_stupid (loops, loop);
205       loop = next;
211 /* Check whether exit of the LOOP is at the end of loop body.  */
214 loop_exit_at_end_p (struct loop *loop)
216   struct niter_desc *desc = get_simple_loop_desc (loop);
219   if (desc->in_edge->dest != loop->latch)
223   FOR_BB_INSNS (loop->latch, insn)
236   struct loop *loop;
242       loop = loops->parray[i];
243       if (!loop)
246       loop->lpt_decision.decision = LPT_NONE;
250 		 "\n;; *** Considering loop %d for complete peeling ***\n",
251 		 loop->num);
253       loop->ninsns = num_loop_insns (loop);
255       decide_peel_once_rolling (loop, flags);
256       if (loop->lpt_decision.decision == LPT_NONE)
257 	decide_peel_completely (loop, flags);
259       if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
261 	  peel_loop_completely (loops, loop);
274   struct loop *loop = loops->tree_root, *next;
276   while (loop->inner)
277     loop = loop->inner;
280   while (loop != loops->tree_root)
282       if (loop->next)
284 	  next = loop->next;
289 	next = loop->outer;
291       loop->lpt_decision.decision = LPT_NONE;
294 	fprintf (dump_file, "\n;; *** Considering loop %d ***\n", loop->num);
297       if (!maybe_hot_bb_p (loop->header))
300 	    fprintf (dump_file, ";; Not considering loop, cold area\n");
301 	  loop = next;
305       /* Can the loop be manipulated?  */
306       if (!can_duplicate_loop_p (loop))
310 		     ";; Not considering loop, cannot duplicate\n");
311 	  loop = next;
316       if (loop->inner)
319 	    fprintf (dump_file, ";; Not considering loop, is not innermost\n");
320 	  loop = next;
324       loop->ninsns = num_loop_insns (loop);
325       loop->av_ninsns = average_num_loop_insns (loop);
330       decide_unroll_constant_iterations (loop, flags);
331       if (loop->lpt_decision.decision == LPT_NONE)
332 	decide_unroll_runtime_iterations (loop, flags);
333       if (loop->lpt_decision.decision == LPT_NONE)
334 	decide_unroll_stupid (loop, flags);
335       if (loop->lpt_decision.decision == LPT_NONE)
336 	decide_peel_simple (loop, flags);
338       loop = next;
345 decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
350     fprintf (dump_file, "\n;; Considering peeling once rolling loop\n");
352   /* Is the loop small enough?  */
353   if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS) < loop->ninsns)
356 	fprintf (dump_file, ";; Not considering loop, is too big\n");
361   desc = get_simple_loop_desc (loop);
372 		 ";; Unable to prove that the loop rolls exactly once\n");
378     fprintf (dump_file, ";; Decided to peel exactly once rolling loop\n");
379   loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
384 decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
393   if (loop->inner)
396 	fprintf (dump_file, ";; Not considering loop, is not innermost\n");
401   if (!maybe_hot_bb_p (loop->header))
404 	fprintf (dump_file, ";; Not considering loop, cold area\n");
408   /* Can the loop be manipulated?  */
409   if (!can_duplicate_loop_p (loop))
413 		 ";; Not considering loop, cannot duplicate\n");
418   npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS) / loop->ninsns;
422   /* Is the loop small enough?  */
426 	fprintf (dump_file, ";; Not considering loop, is too big\n");
431   desc = get_simple_loop_desc (loop);
441 		 ";; Unable to prove that the loop iterates constant times\n");
450 		   ";; Not peeling loop completely, rolls too much (");
459     fprintf (dump_file, ";; Decided to peel loop completely\n");
460   loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
463 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
478 peel_loop_completely (struct loops *loops, struct loop *loop)
484   struct niter_desc *desc = get_simple_loop_desc (loop);
503         opt_info = analyze_insns_in_loop (loop);
506       ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
531   free_simple_loop_desc (loop);
534      the loop.  */
538     fprintf (dump_file, ";; Peeled loop completely, %d times\n", (int) npeel);
545 decide_unroll_constant_iterations (struct loop *loop, int flags)
558 	     "\n;; Considering unrolling loop with constant "
561   /* nunroll = total number of copies of the original loop body in
562      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
563   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
565     = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
575 	fprintf (dump_file, ";; Not considering loop, is too big\n");
580   desc = get_simple_loop_desc (loop);
587 		 ";; Unable to prove that the loop iterates constant times\n");
591   /* Check whether the loop rolls enough to consider.  */
595 	fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
600      nunroll so that as few as possible copies of loop body are
613       if (!loop_exit_at_end_p (loop))
632   loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
633   loop->lpt_decision.times = best_unroll;
637 	     ";; Decided to unroll the constant times rolling loop, %d times.\n",
638 	     loop->lpt_decision.times);
661 unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
668   unsigned max_unroll = loop->lpt_decision.times;
669   struct niter_desc *desc = get_simple_loop_desc (loop);
670   bool exit_at_end = loop_exit_at_end_p (loop);
676   /* Should not get here (such loop should be peeled instead).  */
688     opt_info = analyze_insns_in_loop (loop);
692       /* The exit is not at the end of the loop; leave exit test
697 	fprintf (dump_file, ";; Condition on beginning of loop.\n");
707           ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
730 	 the loop tests the condition at the end of loop body.  */
733 	fprintf (dump_file, ";; Condition on end of loop.\n");
736 	 case when we would exit before reaching the loop.  So just peel
746 	  ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
770   /* Now unroll the loop.  */
773   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
819 	     ";; Unrolled loop %d times, constant # of iterations %i insns\n",
820 	     max_unroll, num_loop_insns (loop));
826 decide_unroll_runtime_iterations (struct loop *loop, int flags)
839 	     "\n;; Considering unrolling loop with runtime "
842   /* nunroll = total number of copies of the original loop body in
843      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
844   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
845   nunroll_by_av = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
855 	fprintf (dump_file, ";; Not considering loop, is too big\n");
860   desc = get_simple_loop_desc (loop);
879   /* If we have profile feedback, check whether the loop rolls.  */
880   if (loop->header->count && expected_loop_iterations (loop) < 2 * nunroll)
883 	fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
892   loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
893   loop->lpt_decision.times = i - 1;
898 	     "times rolling loop, %d times.\n",
899 	     loop->lpt_decision.times);
934 unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
945   unsigned max_unroll = loop->lpt_decision.times;
946   struct niter_desc *desc = get_simple_loop_desc (loop);
947   bool exit_at_end = loop_exit_at_end_p (loop);
953     opt_info = analyze_insns_in_loop (loop);
959   body = get_loop_body (loop);
960   for (i = 0; i < loop->num_nodes; i++)
967 	if (!flow_bb_inside_loop_p (loop, ldom[j]))
1011   /* Precondition the loop.  */
1012   loop_split_edge_with (loop_preheader_edge (loop), init_code);
1019   /* Peel the first copy of loop body (almost always we must leave exit test
1027   ezc_swtch = loop_preheader_edge (loop)->src;
1028   ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1036   swtch = loop_split_edge_with (loop_preheader_edge (loop),
1045       ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1056       preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
1074       preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
1090   /* And unroll loop.  */
1096   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1139      of the loop.  After passing through the above code, we see that
1156 	     ";; Unrolled loop %d times, counting # of iterations "
1158 	     max_unroll, num_loop_insns (loop));
1166 decide_peel_simple (struct loop *loop, int flags)
1178     fprintf (dump_file, "\n;; Considering simply peeling loop\n");
1181   npeel = PARAM_VALUE (PARAM_MAX_PEELED_INSNS) / loop->ninsns;
1189 	fprintf (dump_file, ";; Not considering loop, is too big\n");
1194   desc = get_simple_loop_desc (loop);
1206   if (num_loop_branches (loop) > 1)
1213   if (loop->header->count)
1215       unsigned niter = expected_loop_iterations (loop);
1220 	      fprintf (dump_file, ";; Not peeling loop, rolls too much (");
1232       /* For now we have no good heuristics to decide whether loop peeling
1236 		 ";; Not peeling loop, no evidence it will be profitable\n");
1241   loop->lpt_decision.decision = LPT_PEEL_SIMPLE;
1242   loop->lpt_decision.times = npeel;
1245     fprintf (dump_file, ";; Decided to simply peel the loop, %d times.\n",
1246 	     loop->lpt_decision.times);
1264 peel_loop_simple (struct loops *loops, struct loop *loop)
1267   unsigned npeel = loop->lpt_decision.times;
1268   struct niter_desc *desc = get_simple_loop_desc (loop);
1273     opt_info = analyze_insns_in_loop (loop);
1280   ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1308 	     inside loop.  We could handle this by counting the number into
1311 	  free_simple_loop_desc (loop);
1315     fprintf (dump_file, ";; Peeling loop %d times\n", npeel);
1320 decide_unroll_stupid (struct loop *loop, int flags)
1332     fprintf (dump_file, "\n;; Considering unrolling loop stupidly\n");
1334   /* nunroll = total number of copies of the original loop body in
1335      unrolled loop (i.e. if it is 2, we have to duplicate loop body once.  */
1336   nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
1338     = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
1348 	fprintf (dump_file, ";; Not considering loop, is too big\n");
1353   desc = get_simple_loop_desc (loop);
1359 	fprintf (dump_file, ";; The loop is simple\n");
1365   if (num_loop_branches (loop) > 1)
1372   /* If we have profile feedback, check whether the loop rolls.  */
1373   if (loop->header->count
1374       && expected_loop_iterations (loop) < 2 * nunroll)
1377 	fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
1387   loop->lpt_decision.decision = LPT_UNROLL_STUPID;
1388   loop->lpt_decision.times = i - 1;
1392 	     ";; Decided to unroll the loop stupidly, %d times.\n",
1393 	     loop->lpt_decision.times);
1414 unroll_loop_stupid (struct loops *loops, struct loop *loop)
1417   unsigned nunroll = loop->lpt_decision.times;
1418   struct niter_desc *desc = get_simple_loop_desc (loop);
1424     opt_info = analyze_insns_in_loop (loop);
1431   ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1451 	 for a loop to be really simple.  We could update the counts, but the
1460     fprintf (dump_file, ";; Unrolled loop %d times, %i insns\n",
1461 	     nunroll, num_loop_insns (loop));
1506 referenced_in_one_insn_in_loop_p (struct loop *loop, rtx reg)
1513   body = get_loop_body (loop); 
1514   for (i = 0; i < loop->num_nodes; i++)
1551 analyze_insn_to_expand_var (struct loop *loop, rtx insn)
1594   if (!referenced_in_one_insn_in_loop_p (loop, dest))
1698 analyze_insns_in_loop (struct loop *loop)
1708   edge *edges = get_loop_exit_edges (loop, &num_edges);
1711   iv_analysis_loop_init (loop);
1713   body = get_loop_body (loop);
1716     opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
1719   /* Record the loop exit bb and loop preheader before the unrolling.  */
1720   if (!loop_preheader_edge (loop)->src)
1722       loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
1723       opt_info->loop_preheader = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
1726     opt_info->loop_preheader = loop_preheader_edge (loop)->src;
1737     opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
1740   for (i = 0; i < loop->num_nodes; i++)
1743       if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1762           ves = analyze_insn_to_expand_var (loop, insn);
1777 /* Called just before loop duplication.  Records start of duplicated area
1790    (not peeling) the loop.  */
1797       /* If we are unrolling, initialization is done in the original loop
1804 	 number 1.  The original loop (number 0) is the last.  */
1975 /* Initialize the variable expansions in loop preheader.  
1976    Callbacks for htab_traverse.  PLACE_P is the loop-preheader 
2017 /*  Combine the variable expansions at the loop exit.  
2018     Callbacks for htab_traverse.  PLACE_P is the loop exit
2064 /* Apply loop optimizations in loop copies using the 
2068    UNROLLING is true if we unrolled (not peeled) the loop.
2070    the loop (as it should happen in complete unrolling, but not in ordinary
2071    peeling of the loop).  */
2084   /* Sanity check -- we need to put initialization in the original loop
2148   /* Initialize the variable expansions in the loop preheader
2149      and take care of combining them at the loop exit.  */ 
2160   /* Rewrite also the original loop body.  Find them as originals of the blocks

Indexes created Thu May 23 20:32:32 MDT 2024