Branch data Line data Source code
1 : : /* Perform doloop optimizations
2 : : Copyright (C) 2004-2024 Free Software Foundation, Inc.
3 : : Based on code by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it under
8 : : the terms of the GNU General Public License as published by the Free
9 : : Software Foundation; either version 3, or (at your option) any later
10 : : version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : : for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "config.h"
22 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "backend.h"
25 : : #include "target.h"
26 : : #include "rtl.h"
27 : : #include "tree.h"
28 : : #include "cfghooks.h"
29 : : #include "memmodel.h"
30 : : #include "emit-rtl.h"
31 : : #include "dojump.h"
32 : : #include "expr.h"
33 : : #include "cfgloop.h"
34 : : #include "cfgrtl.h"
35 : : #include "dumpfile.h"
36 : : #include "loop-unroll.h"
37 : : #include "regs.h"
38 : : #include "df.h"
39 : :
40 : : /* This module is used to modify loops with a determinable number of
41 : : iterations to use special low-overhead looping instructions.
42 : :
43 : : It first validates whether the loop is well behaved and has a
44 : : determinable number of iterations (either at compile or run-time).
45 : : It then modifies the loop to use a low-overhead looping pattern as
46 : : follows:
47 : :
48 : : 1. A pseudo register is allocated as the loop iteration counter.
49 : :
50 : : 2. The number of loop iterations is calculated and is stored
51 : : in the loop counter.
52 : :
53 : : 3. At the end of the loop, the jump insn is replaced by the
54 : : doloop_end pattern. The compare must remain because it might be
55 : : used elsewhere. If the loop-variable or condition register are
56 : : used elsewhere, they will be eliminated by flow.
57 : :
58 : : 4. An optional doloop_begin pattern is inserted at the top of the
59 : : loop.
60 : :
61 : : TODO The optimization should only performed when either the biv used for exit
62 : : condition is unused at all except for the exit test, or if we do not have to
63 : : change its value, since otherwise we have to add a new induction variable,
64 : : which usually will not pay up (unless the cost of the doloop pattern is
65 : : somehow extremely lower than the cost of compare & jump, or unless the bct
66 : : register cannot be used for anything else but doloop -- ??? detect these
67 : : cases). */
68 : :
69 : : /* Return the loop termination condition for PATTERN or zero
70 : : if it is not a decrement and branch jump insn. */
71 : :
72 : : rtx
73 : 0 : doloop_condition_get (rtx_insn *doloop_pat)
74 : : {
75 : 0 : rtx cmp;
76 : 0 : rtx inc;
77 : 0 : rtx reg;
78 : 0 : rtx inc_src;
79 : 0 : rtx condition;
80 : 0 : rtx pattern;
81 : 0 : rtx cc_reg = NULL_RTX;
82 : 0 : rtx reg_orig = NULL_RTX;
83 : :
84 : : /* The canonical doloop pattern we expect has one of the following
85 : : forms:
86 : :
87 : : 1) (parallel [(set (pc) (if_then_else (condition)
88 : : (label_ref (label))
89 : : (pc)))
90 : : (set (reg) (plus (reg) (const_int -1)))
91 : : (additional clobbers and uses)])
92 : :
93 : : The branch must be the first entry of the parallel (also required
94 : : by jump.cc), and the second entry of the parallel must be a set of
95 : : the loop counter register. Some targets (IA-64) wrap the set of
96 : : the loop counter in an if_then_else too.
97 : :
98 : : 2) (set (reg) (plus (reg) (const_int -1))
99 : : (set (pc) (if_then_else (reg != 0)
100 : : (label_ref (label))
101 : : (pc))).
102 : :
103 : : Some targets (ARM) do the comparison before the branch, as in the
104 : : following form:
105 : :
106 : : 3) (parallel [(set (cc) (compare ((plus (reg) (const_int -1), 0)))
107 : : (set (reg) (plus (reg) (const_int -1)))])
108 : : (set (pc) (if_then_else (cc == NE)
109 : : (label_ref (label))
110 : : (pc))) */
111 : :
112 : 0 : pattern = PATTERN (doloop_pat);
113 : :
114 : 0 : if (GET_CODE (pattern) != PARALLEL)
115 : : {
116 : 0 : rtx cond;
117 : 0 : rtx_insn *prev_insn = prev_nondebug_insn (doloop_pat);
118 : 0 : rtx cmp_arg1, cmp_arg2;
119 : 0 : rtx cmp_orig;
120 : :
121 : : /* In case the pattern is not PARALLEL we expect two forms
122 : : of doloop which are cases 2) and 3) above: in case 2) the
123 : : decrement immediately precedes the branch, while in case 3)
124 : : the compare and decrement instructions immediately precede
125 : : the branch. */
126 : :
127 : 0 : if (prev_insn == NULL_RTX || !INSN_P (prev_insn))
128 : : return 0;
129 : :
130 : 0 : cmp = pattern;
131 : 0 : if (GET_CODE (PATTERN (prev_insn)) == PARALLEL)
132 : : {
133 : : /* The third case: the compare and decrement instructions
134 : : immediately precede the branch. */
135 : 0 : cmp_orig = XVECEXP (PATTERN (prev_insn), 0, 0);
136 : 0 : if (GET_CODE (cmp_orig) != SET)
137 : : return 0;
138 : 0 : if (GET_CODE (SET_SRC (cmp_orig)) != COMPARE)
139 : : return 0;
140 : 0 : cmp_arg1 = XEXP (SET_SRC (cmp_orig), 0);
141 : 0 : cmp_arg2 = XEXP (SET_SRC (cmp_orig), 1);
142 : 0 : if (cmp_arg2 != const0_rtx
143 : 0 : || GET_CODE (cmp_arg1) != PLUS)
144 : : return 0;
145 : 0 : reg_orig = XEXP (cmp_arg1, 0);
146 : 0 : if (XEXP (cmp_arg1, 1) != GEN_INT (-1)
147 : 0 : || !REG_P (reg_orig))
148 : : return 0;
149 : 0 : cc_reg = SET_DEST (cmp_orig);
150 : :
151 : 0 : inc = XVECEXP (PATTERN (prev_insn), 0, 1);
152 : : }
153 : : else
154 : : inc = PATTERN (prev_insn);
155 : 0 : if (GET_CODE (cmp) == SET && GET_CODE (SET_SRC (cmp)) == IF_THEN_ELSE)
156 : : {
157 : : /* We expect the condition to be of the form (reg != 0) */
158 : 0 : cond = XEXP (SET_SRC (cmp), 0);
159 : 0 : if (GET_CODE (cond) != NE || XEXP (cond, 1) != const0_rtx)
160 : : return 0;
161 : : }
162 : : }
163 : : else
164 : : {
165 : 0 : cmp = XVECEXP (pattern, 0, 0);
166 : 0 : inc = XVECEXP (pattern, 0, 1);
167 : : }
168 : :
169 : : /* Check for (set (reg) (something)). */
170 : 0 : if (GET_CODE (inc) != SET)
171 : : return 0;
172 : 0 : reg = SET_DEST (inc);
173 : 0 : if (! REG_P (reg))
174 : : return 0;
175 : :
176 : : /* Check if something = (plus (reg) (const_int -1)).
177 : : On IA-64, this decrement is wrapped in an if_then_else. */
178 : 0 : inc_src = SET_SRC (inc);
179 : 0 : if (GET_CODE (inc_src) == IF_THEN_ELSE)
180 : 0 : inc_src = XEXP (inc_src, 1);
181 : 0 : if (GET_CODE (inc_src) != PLUS
182 : 0 : || XEXP (inc_src, 0) != reg
183 : 0 : || XEXP (inc_src, 1) != constm1_rtx)
184 : : return 0;
185 : :
186 : : /* Check for (set (pc) (if_then_else (condition)
187 : : (label_ref (label))
188 : : (pc))). */
189 : 0 : if (GET_CODE (cmp) != SET
190 : 0 : || SET_DEST (cmp) != pc_rtx
191 : 0 : || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
192 : 0 : || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
193 : 0 : || XEXP (SET_SRC (cmp), 2) != pc_rtx)
194 : : return 0;
195 : :
196 : : /* Extract loop termination condition. */
197 : 0 : condition = XEXP (SET_SRC (cmp), 0);
198 : :
199 : : /* We expect a GE or NE comparison with 0 or 1. */
200 : 0 : if ((GET_CODE (condition) != GE
201 : 0 : && GET_CODE (condition) != NE)
202 : 0 : || (XEXP (condition, 1) != const0_rtx
203 : 0 : && XEXP (condition, 1) != const1_rtx))
204 : : return 0;
205 : :
206 : 0 : if ((XEXP (condition, 0) == reg)
207 : : /* For the third case: */
208 : 0 : || ((cc_reg != NULL_RTX)
209 : 0 : && (XEXP (condition, 0) == cc_reg)
210 : 0 : && (reg_orig == reg))
211 : 0 : || (GET_CODE (XEXP (condition, 0)) == PLUS
212 : 0 : && XEXP (XEXP (condition, 0), 0) == reg))
213 : : {
214 : 0 : if (GET_CODE (pattern) != PARALLEL)
215 : : /* For the second form we expect:
216 : :
217 : : (set (reg) (plus (reg) (const_int -1))
218 : : (set (pc) (if_then_else (reg != 0)
219 : : (label_ref (label))
220 : : (pc))).
221 : :
222 : : is equivalent to the following:
223 : :
224 : : (parallel [(set (pc) (if_then_else (reg != 1)
225 : : (label_ref (label))
226 : : (pc)))
227 : : (set (reg) (plus (reg) (const_int -1)))
228 : : (additional clobbers and uses)])
229 : :
230 : : For the third form we expect:
231 : :
232 : : (parallel [(set (cc) (compare ((plus (reg) (const_int -1)), 0))
233 : : (set (reg) (plus (reg) (const_int -1)))])
234 : : (set (pc) (if_then_else (cc == NE)
235 : : (label_ref (label))
236 : : (pc)))
237 : :
238 : : which is equivalent to the following:
239 : :
240 : : (parallel [(set (cc) (compare (reg, 1))
241 : : (set (reg) (plus (reg) (const_int -1)))
242 : : (set (pc) (if_then_else (NE == cc)
243 : : (label_ref (label))
244 : : (pc))))])
245 : :
246 : : So we return the second form instead for the two cases.
247 : :
248 : : */
249 : 0 : condition = gen_rtx_fmt_ee (NE, VOIDmode, inc_src, const1_rtx);
250 : :
251 : 0 : return condition;
252 : : }
253 : :
254 : : /* ??? If a machine uses a funny comparison, we could return a
255 : : canonicalized form here. */
256 : :
257 : : return 0;
258 : : }
259 : :
260 : : /* Return nonzero if the loop specified by LOOP is suitable for
261 : : the use of special low-overhead looping instructions. DESC
262 : : describes the number of iterations of the loop. */
263 : :
264 : : static bool
265 : 0 : doloop_valid_p (class loop *loop, class niter_desc *desc)
266 : : {
267 : 0 : basic_block *body = get_loop_body (loop), bb;
268 : 0 : rtx_insn *insn;
269 : 0 : unsigned i;
270 : 0 : bool result = true;
271 : :
272 : : /* Check for loops that may not terminate under special conditions. */
273 : 0 : if (!desc->simple_p
274 : 0 : || desc->assumptions
275 : 0 : || desc->infinite)
276 : : {
277 : : /* There are some cases that would require a special attention.
278 : : For example if the comparison is LEU and the comparison value
279 : : is UINT_MAX then the loop will not terminate. Similarly, if the
280 : : comparison code is GEU and the comparison value is 0, the
281 : : loop will not terminate.
282 : :
283 : : If the absolute increment is not 1, the loop can be infinite
284 : : even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
285 : :
286 : : ??? We could compute these conditions at run-time and have a
287 : : additional jump around the loop to ensure an infinite loop.
288 : : However, it is very unlikely that this is the intended
289 : : behavior of the loop and checking for these rare boundary
290 : : conditions would pessimize all other code.
291 : :
292 : : If the loop is executed only a few times an extra check to
293 : : restart the loop could use up most of the benefits of using a
294 : : count register loop. Note however, that normally, this
295 : : restart branch would never execute, so it could be predicted
296 : : well by the CPU. We should generate the pessimistic code by
297 : : default, and have an option, e.g. -funsafe-loops that would
298 : : enable count-register loops in this case. */
299 : 0 : if (dump_file)
300 : 0 : fprintf (dump_file, "Doloop: Possible infinite iteration case.\n");
301 : 0 : result = false;
302 : 0 : goto cleanup;
303 : : }
304 : :
305 : 0 : for (i = 0; i < loop->num_nodes; i++)
306 : : {
307 : 0 : bb = body[i];
308 : :
309 : 0 : for (insn = BB_HEAD (bb);
310 : 0 : insn != NEXT_INSN (BB_END (bb));
311 : 0 : insn = NEXT_INSN (insn))
312 : : {
313 : : /* Different targets have different necessities for low-overhead
314 : : looping. Call the back end for each instruction within the loop
315 : : to let it decide whether the insn prohibits a low-overhead loop.
316 : : It will then return the cause for it to emit to the dump file. */
317 : 0 : const char * invalid = targetm.invalid_within_doloop (insn);
318 : 0 : if (invalid)
319 : : {
320 : 0 : if (dump_file)
321 : 0 : fprintf (dump_file, "Doloop: %s\n", invalid);
322 : 0 : result = false;
323 : 0 : goto cleanup;
324 : : }
325 : : }
326 : : }
327 : : result = true;
328 : :
329 : 0 : cleanup:
330 : 0 : free (body);
331 : :
332 : 0 : return result;
333 : : }
334 : :
335 : : /* Adds test of COND jumping to DEST on edge *E and set *E to the new fallthru
336 : : edge. If the condition is always false, do not do anything. If it is always
337 : : true, redirect E to DEST and return false. In all other cases, true is
338 : : returned. */
339 : :
340 : : static bool
341 : 0 : add_test (rtx cond, edge *e, basic_block dest)
342 : : {
343 : 0 : rtx_insn *seq, *jump;
344 : 0 : rtx_code_label *label;
345 : 0 : machine_mode mode;
346 : 0 : rtx op0 = XEXP (cond, 0), op1 = XEXP (cond, 1);
347 : 0 : enum rtx_code code = GET_CODE (cond);
348 : 0 : basic_block bb;
349 : : /* The jump is supposed to handle an unlikely special case. */
350 : 0 : profile_probability prob = profile_probability::guessed_never ();
351 : :
352 : 0 : mode = GET_MODE (XEXP (cond, 0));
353 : 0 : if (mode == VOIDmode)
354 : 0 : mode = GET_MODE (XEXP (cond, 1));
355 : :
356 : 0 : start_sequence ();
357 : 0 : op0 = force_operand (op0, NULL_RTX);
358 : 0 : op1 = force_operand (op1, NULL_RTX);
359 : 0 : label = block_label (dest);
360 : 0 : do_compare_rtx_and_jump (op0, op1, code, 0, mode, NULL_RTX, NULL, label,
361 : : prob);
362 : :
363 : 0 : jump = get_last_insn ();
364 : 0 : if (!jump || !JUMP_P (jump))
365 : : {
366 : : /* The condition is always false and the jump was optimized out. */
367 : 0 : end_sequence ();
368 : 0 : return true;
369 : : }
370 : :
371 : 0 : seq = get_insns ();
372 : 0 : unshare_all_rtl_in_chain (seq);
373 : 0 : end_sequence ();
374 : :
375 : : /* There always is at least the jump insn in the sequence. */
376 : 0 : gcc_assert (seq != NULL_RTX);
377 : :
378 : 0 : bb = split_edge_and_insert (*e, seq);
379 : 0 : *e = single_succ_edge (bb);
380 : :
381 : 0 : if (any_uncondjump_p (jump) && onlyjump_p (jump))
382 : : {
383 : : /* The condition is always true. */
384 : 0 : delete_insn (jump);
385 : 0 : redirect_edge_and_branch_force (*e, dest);
386 : 0 : return false;
387 : : }
388 : :
389 : 0 : JUMP_LABEL (jump) = label;
390 : :
391 : 0 : LABEL_NUSES (label)++;
392 : :
393 : 0 : edge e2 = make_edge (bb, dest, (*e)->flags & ~EDGE_FALLTHRU);
394 : 0 : e2->probability = prob;
395 : 0 : (*e)->probability = prob.invert ();
396 : 0 : update_br_prob_note (e2->src);
397 : 0 : return true;
398 : : }
399 : :
400 : : /* Fold (add -1; zero_ext; add +1) operations to zero_ext if not wrapping. i.e:
401 : :
402 : : 73: r145:SI=r123:DI#0-0x1
403 : : 74: r144:DI=zero_extend (r145:SI)
404 : : 75: r143:DI=r144:DI+0x1
405 : : ...
406 : : 31: r135:CC=cmp (r123:DI,0)
407 : : 72: {pc={(r143:DI!=0x1)?L70:pc};r143:DI=r143:DI-0x1;...}
408 : :
409 : : r123:DI#0-0x1 is param count derived from loop->niter_expr equal to number of
410 : : loop iterations, if loop iterations expression doesn't overflow, then
411 : : (zero_extend (r123:DI#0-1))+1 can be simplified to zero_extend. */
412 : :
413 : : static rtx
414 : 0 : doloop_simplify_count (class loop *loop, scalar_int_mode mode, rtx count)
415 : : {
416 : 0 : widest_int iterations;
417 : 0 : if (GET_CODE (count) == ZERO_EXTEND)
418 : : {
419 : 0 : rtx extop0 = XEXP (count, 0);
420 : 0 : if (GET_CODE (extop0) == PLUS)
421 : : {
422 : 0 : rtx addop0 = XEXP (extop0, 0);
423 : 0 : rtx addop1 = XEXP (extop0, 1);
424 : :
425 : 0 : if (get_max_loop_iterations (loop, &iterations)
426 : 0 : && wi::ltu_p (iterations, GET_MODE_MASK (GET_MODE (addop0)))
427 : 0 : && addop1 == constm1_rtx)
428 : 0 : return simplify_gen_unary (ZERO_EXTEND, mode, addop0,
429 : 0 : GET_MODE (addop0));
430 : : }
431 : : }
432 : :
433 : 0 : return simplify_gen_binary (PLUS, mode, count, const1_rtx);
434 : 0 : }
435 : :
436 : : /* Modify the loop to use the low-overhead looping insn where LOOP
437 : : describes the loop, DESC describes the number of iterations of the
438 : : loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
439 : : end of the loop. CONDITION is the condition separated from the
440 : : DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
441 : :
442 : : static void
443 : 0 : doloop_modify (class loop *loop, class niter_desc *desc,
444 : : rtx_insn *doloop_seq, rtx condition, rtx count)
445 : : {
446 : 0 : rtx counter_reg;
447 : 0 : rtx tmp, noloop = NULL_RTX;
448 : 0 : rtx_insn *sequence;
449 : 0 : rtx_insn *jump_insn;
450 : 0 : rtx_code_label *jump_label;
451 : 0 : int nonneg = 0;
452 : 0 : bool increment_count;
453 : 0 : basic_block loop_end = desc->out_edge->src;
454 : 0 : scalar_int_mode mode;
455 : 0 : widest_int iterations;
456 : :
457 : 0 : jump_insn = BB_END (loop_end);
458 : :
459 : 0 : if (dump_file)
460 : : {
461 : 0 : fprintf (dump_file, "Doloop: Inserting doloop pattern (");
462 : 0 : if (desc->const_iter)
463 : 0 : fprintf (dump_file, "%" PRId64, desc->niter);
464 : : else
465 : 0 : fputs ("runtime", dump_file);
466 : 0 : fputs (" iterations).\n", dump_file);
467 : : }
468 : :
469 : : /* Discard original jump to continue loop. The original compare
470 : : result may still be live, so it cannot be discarded explicitly. */
471 : 0 : delete_insn (jump_insn);
472 : :
473 : 0 : counter_reg = XEXP (condition, 0);
474 : 0 : if (GET_CODE (counter_reg) == PLUS)
475 : 0 : counter_reg = XEXP (counter_reg, 0);
476 : : /* These patterns must operate on integer counters. */
477 : 0 : mode = as_a <scalar_int_mode> (GET_MODE (counter_reg));
478 : :
479 : 0 : increment_count = false;
480 : 0 : switch (GET_CODE (condition))
481 : : {
482 : 0 : case NE:
483 : : /* Currently only NE tests against zero and one are supported. */
484 : 0 : noloop = XEXP (condition, 1);
485 : 0 : if (noloop != const0_rtx)
486 : : {
487 : 0 : gcc_assert (noloop == const1_rtx);
488 : : increment_count = true;
489 : : }
490 : : break;
491 : :
492 : 0 : case GE:
493 : : /* Currently only GE tests against zero are supported. */
494 : 0 : gcc_assert (XEXP (condition, 1) == const0_rtx);
495 : :
496 : 0 : noloop = constm1_rtx;
497 : :
498 : : /* The iteration count does not need incrementing for a GE test. */
499 : 0 : increment_count = false;
500 : :
501 : : /* Determine if the iteration counter will be non-negative.
502 : : Note that the maximum value loaded is iterations_max - 1. */
503 : 0 : if (get_max_loop_iterations (loop, &iterations)
504 : 0 : && wi::leu_p (iterations,
505 : : wi::set_bit_in_zero <widest_int>
506 : 0 : (GET_MODE_PRECISION (mode) - 1)))
507 : 0 : nonneg = 1;
508 : : break;
509 : :
510 : : /* Abort if an invalid doloop pattern has been generated. */
511 : 0 : default:
512 : 0 : gcc_unreachable ();
513 : : }
514 : :
515 : 0 : if (increment_count)
516 : 0 : count = doloop_simplify_count (loop, mode, count);
517 : :
518 : : /* Insert initialization of the count register into the loop header. */
519 : 0 : start_sequence ();
520 : : /* count has been already copied through copy_rtx. */
521 : 0 : reset_used_flags (count);
522 : 0 : set_used_flags (condition);
523 : 0 : tmp = force_operand (count, counter_reg);
524 : 0 : convert_move (counter_reg, tmp, 1);
525 : 0 : sequence = get_insns ();
526 : 0 : unshare_all_rtl_in_chain (sequence);
527 : 0 : end_sequence ();
528 : 0 : emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
529 : :
530 : 0 : if (desc->noloop_assumptions)
531 : : {
532 : 0 : rtx ass = copy_rtx (desc->noloop_assumptions);
533 : 0 : basic_block preheader = loop_preheader_edge (loop)->src;
534 : 0 : basic_block set_zero = split_edge (loop_preheader_edge (loop));
535 : 0 : basic_block new_preheader = split_edge (loop_preheader_edge (loop));
536 : 0 : edge te;
537 : :
538 : : /* Expand the condition testing the assumptions and if it does not pass,
539 : : reset the count register to 0. */
540 : 0 : redirect_edge_and_branch_force (single_succ_edge (preheader), new_preheader);
541 : 0 : set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
542 : :
543 : 0 : set_zero->count = profile_count::uninitialized ();
544 : :
545 : 0 : te = single_succ_edge (preheader);
546 : 0 : for (; ass; ass = XEXP (ass, 1))
547 : 0 : if (!add_test (XEXP (ass, 0), &te, set_zero))
548 : : break;
549 : :
550 : 0 : if (ass)
551 : : {
552 : : /* We reached a condition that is always true. This is very hard to
553 : : reproduce (such a loop does not roll, and thus it would most
554 : : likely get optimized out by some of the preceding optimizations).
555 : : In fact, I do not have any testcase for it. However, it would
556 : : also be very hard to show that it is impossible, so we must
557 : : handle this case. */
558 : 0 : set_zero->count = preheader->count;
559 : : }
560 : :
561 : 0 : if (EDGE_COUNT (set_zero->preds) == 0)
562 : : {
563 : : /* All the conditions were simplified to false, remove the
564 : : unreachable set_zero block. */
565 : 0 : delete_basic_block (set_zero);
566 : : }
567 : : else
568 : : {
569 : : /* Reset the counter to zero in the set_zero block. */
570 : 0 : start_sequence ();
571 : 0 : convert_move (counter_reg, noloop, 0);
572 : 0 : sequence = get_insns ();
573 : 0 : end_sequence ();
574 : 0 : emit_insn_after (sequence, BB_END (set_zero));
575 : :
576 : 0 : set_immediate_dominator (CDI_DOMINATORS, set_zero,
577 : : recompute_dominator (CDI_DOMINATORS,
578 : : set_zero));
579 : : }
580 : :
581 : 0 : set_immediate_dominator (CDI_DOMINATORS, new_preheader,
582 : : recompute_dominator (CDI_DOMINATORS,
583 : : new_preheader));
584 : : }
585 : :
586 : : /* Some targets (eg, C4x) need to initialize special looping
587 : : registers. */
588 : 0 : if (targetm.have_doloop_begin ())
589 : 0 : if (rtx_insn *seq = targetm.gen_doloop_begin (counter_reg, doloop_seq))
590 : 0 : emit_insn_after (seq, BB_END (loop_preheader_edge (loop)->src));
591 : :
592 : : /* Insert the new low-overhead looping insn. */
593 : 0 : emit_jump_insn_after (doloop_seq, BB_END (loop_end));
594 : 0 : jump_insn = BB_END (loop_end);
595 : 0 : jump_label = block_label (desc->in_edge->dest);
596 : 0 : JUMP_LABEL (jump_insn) = jump_label;
597 : 0 : LABEL_NUSES (jump_label)++;
598 : :
599 : : /* Ensure the right fallthru edge is marked, for case we have reversed
600 : : the condition. */
601 : 0 : desc->in_edge->flags &= ~EDGE_FALLTHRU;
602 : 0 : desc->out_edge->flags |= EDGE_FALLTHRU;
603 : :
604 : : /* Add a REG_NONNEG note if the actual or estimated maximum number
605 : : of iterations is non-negative. */
606 : 0 : if (nonneg)
607 : 0 : add_reg_note (jump_insn, REG_NONNEG, NULL_RTX);
608 : :
609 : : /* Update the REG_BR_PROB note. */
610 : 0 : if (desc->in_edge->probability.initialized_p ())
611 : 0 : add_reg_br_prob_note (jump_insn, desc->in_edge->probability);
612 : 0 : }
613 : :
614 : : /* Called through note_stores. */
615 : :
616 : : static void
617 : 0 : record_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
618 : : {
619 : 0 : bitmap mod = (bitmap)data;
620 : 0 : if (REG_P (x))
621 : : {
622 : 0 : unsigned int regno = REGNO (x);
623 : 0 : if (HARD_REGISTER_P (x))
624 : : {
625 : 0 : unsigned int end_regno = end_hard_regno (GET_MODE (x), regno);
626 : 0 : do
627 : 0 : bitmap_set_bit (mod, regno);
628 : 0 : while (++regno < end_regno);
629 : : }
630 : : else
631 : 0 : bitmap_set_bit (mod, regno);
632 : : }
633 : 0 : }
634 : :
635 : : /* Process loop described by LOOP validating that the loop is suitable for
636 : : conversion to use a low overhead looping instruction, replacing the jump
637 : : insn where suitable. Returns true if the loop was successfully
638 : : modified. */
639 : :
640 : : static bool
641 : 0 : doloop_optimize (class loop *loop)
642 : : {
643 : 0 : scalar_int_mode mode;
644 : 0 : rtx doloop_reg;
645 : 0 : rtx count;
646 : 0 : widest_int iterations, iterations_max;
647 : 0 : rtx_code_label *start_label;
648 : 0 : rtx condition;
649 : 0 : unsigned level;
650 : 0 : HOST_WIDE_INT est_niter;
651 : 0 : int max_cost;
652 : 0 : class niter_desc *desc;
653 : 0 : unsigned word_mode_size;
654 : 0 : unsigned HOST_WIDE_INT word_mode_max;
655 : 0 : int entered_at_top;
656 : :
657 : 0 : if (dump_file)
658 : 0 : fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
659 : :
660 : 0 : iv_analysis_loop_init (loop);
661 : :
662 : : /* Find the simple exit of a LOOP. */
663 : 0 : desc = get_simple_loop_desc (loop);
664 : :
665 : : /* Check that loop is a candidate for a low-overhead looping insn. */
666 : 0 : if (!doloop_valid_p (loop, desc))
667 : : {
668 : 0 : if (dump_file)
669 : 0 : fprintf (dump_file,
670 : : "Doloop: The loop is not suitable.\n");
671 : 0 : return false;
672 : : }
673 : 0 : mode = desc->mode;
674 : :
675 : 0 : est_niter = get_estimated_loop_iterations_int (loop);
676 : 0 : if (est_niter == -1)
677 : 0 : est_niter = get_likely_max_loop_iterations_int (loop);
678 : :
679 : 0 : if (est_niter >= 0 && est_niter < 3)
680 : : {
681 : 0 : if (dump_file)
682 : 0 : fprintf (dump_file,
683 : : "Doloop: Too few iterations (%u) to be profitable.\n",
684 : : (unsigned int)est_niter);
685 : 0 : return false;
686 : : }
687 : :
688 : 0 : max_cost
689 : 0 : = COSTS_N_INSNS (param_max_iterations_computation_cost);
690 : 0 : if (set_src_cost (desc->niter_expr, mode, optimize_loop_for_speed_p (loop))
691 : : > max_cost)
692 : : {
693 : 0 : if (dump_file)
694 : 0 : fprintf (dump_file,
695 : : "Doloop: number of iterations too costly to compute.\n");
696 : 0 : return false;
697 : : }
698 : :
699 : 0 : if (desc->const_iter)
700 : 0 : iterations = widest_int::from (rtx_mode_t (desc->niter_expr, mode),
701 : 0 : UNSIGNED);
702 : : else
703 : 0 : iterations = 0;
704 : 0 : if (!get_max_loop_iterations (loop, &iterations_max))
705 : 0 : iterations_max = 0;
706 : 0 : level = get_loop_level (loop) + 1;
707 : 0 : entered_at_top = (loop->latch == desc->in_edge->dest
708 : 0 : && contains_no_active_insn_p (loop->latch));
709 : 0 : if (!targetm.can_use_doloop_p (iterations, iterations_max, level,
710 : : entered_at_top))
711 : : {
712 : 0 : if (dump_file)
713 : 0 : fprintf (dump_file, "Loop rejected by can_use_doloop_p.\n");
714 : 0 : return false;
715 : : }
716 : :
717 : : /* Generate looping insn. If the pattern FAILs then give up trying
718 : : to modify the loop since there is some aspect the back-end does
719 : : not like. */
720 : 0 : count = copy_rtx (desc->niter_expr);
721 : 0 : start_label = block_label (desc->in_edge->dest);
722 : 0 : doloop_reg = gen_reg_rtx (mode);
723 : 0 : rtx_insn *doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
724 : :
725 : 0 : word_mode_size = GET_MODE_PRECISION (word_mode);
726 : 0 : word_mode_max = (HOST_WIDE_INT_1U << (word_mode_size - 1) << 1) - 1;
727 : 0 : if (! doloop_seq
728 : 0 : && mode != word_mode
729 : : /* Before trying mode different from the one in that # of iterations is
730 : : computed, we must be sure that the number of iterations fits into
731 : : the new mode. */
732 : 0 : && (word_mode_size >= GET_MODE_PRECISION (mode)
733 : 0 : || wi::leu_p (iterations_max, word_mode_max)))
734 : : {
735 : 0 : if (word_mode_size > GET_MODE_PRECISION (mode))
736 : 0 : count = simplify_gen_unary (ZERO_EXTEND, word_mode, count, mode);
737 : : else
738 : 0 : count = lowpart_subreg (word_mode, count, mode);
739 : 0 : PUT_MODE (doloop_reg, word_mode);
740 : 0 : doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
741 : : }
742 : 0 : if (! doloop_seq)
743 : : {
744 : 0 : if (dump_file)
745 : 0 : fprintf (dump_file,
746 : : "Doloop: Target unwilling to use doloop pattern!\n");
747 : 0 : return false;
748 : : }
749 : :
750 : : /* If multiple instructions were created, the last must be the
751 : : jump instruction. */
752 : : rtx_insn *doloop_insn = doloop_seq;
753 : 0 : while (NEXT_INSN (doloop_insn) != NULL_RTX)
754 : : doloop_insn = NEXT_INSN (doloop_insn);
755 : 0 : if (!JUMP_P (doloop_insn)
756 : 0 : || !(condition = doloop_condition_get (doloop_insn)))
757 : : {
758 : 0 : if (dump_file)
759 : 0 : fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
760 : 0 : return false;
761 : : }
762 : :
763 : : /* Ensure that the new sequence doesn't clobber a register that
764 : : is live at the end of the block. */
765 : 0 : {
766 : 0 : bitmap modified = BITMAP_ALLOC (NULL);
767 : :
768 : 0 : for (rtx_insn *i = doloop_seq; i != NULL; i = NEXT_INSN (i))
769 : 0 : note_stores (i, record_reg_sets, modified);
770 : :
771 : 0 : basic_block loop_end = desc->out_edge->src;
772 : 0 : bool fail = bitmap_intersect_p (df_get_live_out (loop_end), modified);
773 : 0 : BITMAP_FREE (modified);
774 : :
775 : 0 : if (fail)
776 : : {
777 : 0 : if (dump_file)
778 : 0 : fprintf (dump_file, "Doloop: doloop pattern clobbers live out\n");
779 : 0 : return false;
780 : : }
781 : : }
782 : :
783 : 0 : doloop_modify (loop, desc, doloop_seq, condition, count);
784 : 0 : return true;
785 : 0 : }
786 : :
787 : : /* This is the main entry point. Process all loops using doloop_optimize. */
788 : :
789 : : void
790 : 0 : doloop_optimize_loops (void)
791 : : {
792 : 0 : if (optimize == 1)
793 : : {
794 : 0 : df_live_add_problem ();
795 : 0 : df_live_set_all_dirty ();
796 : : }
797 : :
798 : 0 : for (auto loop : loops_list (cfun, 0))
799 : 0 : doloop_optimize (loop);
800 : :
801 : 0 : if (optimize == 1)
802 : 0 : df_remove_problem (df_live);
803 : :
804 : 0 : iv_analysis_done ();
805 : :
806 : 0 : checking_verify_loop_structure ();
807 : 0 : }
|
