1 | /* Perform doloop optimizations |
2 | Copyright (C) 2004-2023 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 | doloop_condition_get (rtx_insn *doloop_pat) |
74 | { |
75 | rtx cmp; |
76 | rtx inc; |
77 | rtx reg; |
78 | rtx inc_src; |
79 | rtx condition; |
80 | rtx pattern; |
81 | rtx cc_reg = NULL_RTX; |
82 | 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 | pattern = PATTERN (insn: doloop_pat); |
113 | |
114 | if (GET_CODE (pattern) != PARALLEL) |
115 | { |
116 | rtx cond; |
117 | rtx_insn *prev_insn = prev_nondebug_insn (doloop_pat); |
118 | rtx cmp_arg1, cmp_arg2; |
119 | 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 | if (prev_insn == NULL_RTX || !INSN_P (prev_insn)) |
128 | return 0; |
129 | |
130 | cmp = pattern; |
131 | if (GET_CODE (PATTERN (prev_insn)) == PARALLEL) |
132 | { |
133 | /* The third case: the compare and decrement instructions |
134 | immediately precede the branch. */ |
135 | cmp_orig = XVECEXP (PATTERN (prev_insn), 0, 0); |
136 | if (GET_CODE (cmp_orig) != SET) |
137 | return 0; |
138 | if (GET_CODE (SET_SRC (cmp_orig)) != COMPARE) |
139 | return 0; |
140 | cmp_arg1 = XEXP (SET_SRC (cmp_orig), 0); |
141 | cmp_arg2 = XEXP (SET_SRC (cmp_orig), 1); |
142 | if (cmp_arg2 != const0_rtx |
143 | || GET_CODE (cmp_arg1) != PLUS) |
144 | return 0; |
145 | reg_orig = XEXP (cmp_arg1, 0); |
146 | if (XEXP (cmp_arg1, 1) != GEN_INT (-1) |
147 | || !REG_P (reg_orig)) |
148 | return 0; |
149 | cc_reg = SET_DEST (cmp_orig); |
150 | |
151 | inc = XVECEXP (PATTERN (prev_insn), 0, 1); |
152 | } |
153 | else |
154 | inc = PATTERN (insn: prev_insn); |
155 | 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 | cond = XEXP (SET_SRC (cmp), 0); |
159 | if (GET_CODE (cond) != NE || XEXP (cond, 1) != const0_rtx) |
160 | return 0; |
161 | } |
162 | } |
163 | else |
164 | { |
165 | cmp = XVECEXP (pattern, 0, 0); |
166 | inc = XVECEXP (pattern, 0, 1); |
167 | } |
168 | |
169 | /* Check for (set (reg) (something)). */ |
170 | if (GET_CODE (inc) != SET) |
171 | return 0; |
172 | reg = SET_DEST (inc); |
173 | 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 | inc_src = SET_SRC (inc); |
179 | if (GET_CODE (inc_src) == IF_THEN_ELSE) |
180 | inc_src = XEXP (inc_src, 1); |
181 | if (GET_CODE (inc_src) != PLUS |
182 | || XEXP (inc_src, 0) != reg |
183 | || 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 | if (GET_CODE (cmp) != SET |
190 | || SET_DEST (cmp) != pc_rtx |
191 | || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE |
192 | || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF |
193 | || XEXP (SET_SRC (cmp), 2) != pc_rtx) |
194 | return 0; |
195 | |
196 | /* Extract loop termination condition. */ |
197 | condition = XEXP (SET_SRC (cmp), 0); |
198 | |
199 | /* We expect a GE or NE comparison with 0 or 1. */ |
200 | if ((GET_CODE (condition) != GE |
201 | && GET_CODE (condition) != NE) |
202 | || (XEXP (condition, 1) != const0_rtx |
203 | && XEXP (condition, 1) != const1_rtx)) |
204 | return 0; |
205 | |
206 | if ((XEXP (condition, 0) == reg) |
207 | /* For the third case: */ |
208 | || ((cc_reg != NULL_RTX) |
209 | && (XEXP (condition, 0) == cc_reg) |
210 | && (reg_orig == reg)) |
211 | || (GET_CODE (XEXP (condition, 0)) == PLUS |
212 | && XEXP (XEXP (condition, 0), 0) == reg)) |
213 | { |
214 | 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 | condition = gen_rtx_fmt_ee (NE, VOIDmode, inc_src, const1_rtx); |
250 | |
251 | 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 | doloop_valid_p (class loop *loop, class niter_desc *desc) |
266 | { |
267 | basic_block *body = get_loop_body (loop), bb; |
268 | rtx_insn *insn; |
269 | unsigned i; |
270 | bool result = true; |
271 | |
272 | /* Check for loops that may not terminate under special conditions. */ |
273 | if (!desc->simple_p |
274 | || desc->assumptions |
275 | || 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 | if (dump_file) |
300 | fprintf (stream: dump_file, format: "Doloop: Possible infinite iteration case.\n" ); |
301 | result = false; |
302 | goto cleanup; |
303 | } |
304 | |
305 | for (i = 0; i < loop->num_nodes; i++) |
306 | { |
307 | bb = body[i]; |
308 | |
309 | for (insn = BB_HEAD (bb); |
310 | insn != NEXT_INSN (BB_END (bb)); |
311 | 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 | const char * invalid = targetm.invalid_within_doloop (insn); |
318 | if (invalid) |
319 | { |
320 | if (dump_file) |
321 | fprintf (stream: dump_file, format: "Doloop: %s\n" , invalid); |
322 | result = false; |
323 | goto cleanup; |
324 | } |
325 | } |
326 | } |
327 | result = true; |
328 | |
329 | cleanup: |
330 | free (ptr: body); |
331 | |
332 | 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 | add_test (rtx cond, edge *e, basic_block dest) |
342 | { |
343 | rtx_insn *seq, *jump; |
344 | rtx_code_label *label; |
345 | machine_mode mode; |
346 | rtx op0 = XEXP (cond, 0), op1 = XEXP (cond, 1); |
347 | enum rtx_code code = GET_CODE (cond); |
348 | basic_block bb; |
349 | /* The jump is supposed to handle an unlikely special case. */ |
350 | profile_probability prob = profile_probability::guessed_never (); |
351 | |
352 | mode = GET_MODE (XEXP (cond, 0)); |
353 | if (mode == VOIDmode) |
354 | mode = GET_MODE (XEXP (cond, 1)); |
355 | |
356 | start_sequence (); |
357 | op0 = force_operand (op0, NULL_RTX); |
358 | op1 = force_operand (op1, NULL_RTX); |
359 | label = block_label (dest); |
360 | do_compare_rtx_and_jump (op0, op1, code, 0, mode, NULL_RTX, NULL, label, |
361 | prob); |
362 | |
363 | jump = get_last_insn (); |
364 | if (!jump || !JUMP_P (jump)) |
365 | { |
366 | /* The condition is always false and the jump was optimized out. */ |
367 | end_sequence (); |
368 | return true; |
369 | } |
370 | |
371 | seq = get_insns (); |
372 | unshare_all_rtl_in_chain (seq); |
373 | end_sequence (); |
374 | |
375 | /* There always is at least the jump insn in the sequence. */ |
376 | gcc_assert (seq != NULL_RTX); |
377 | |
378 | bb = split_edge_and_insert (*e, seq); |
379 | *e = single_succ_edge (bb); |
380 | |
381 | if (any_uncondjump_p (jump) && onlyjump_p (jump)) |
382 | { |
383 | /* The condition is always true. */ |
384 | delete_insn (jump); |
385 | redirect_edge_and_branch_force (*e, dest); |
386 | return false; |
387 | } |
388 | |
389 | JUMP_LABEL (jump) = label; |
390 | |
391 | LABEL_NUSES (label)++; |
392 | |
393 | edge e2 = make_edge (bb, dest, (*e)->flags & ~EDGE_FALLTHRU); |
394 | e2->probability = prob; |
395 | (*e)->probability = prob.invert (); |
396 | update_br_prob_note (e2->src); |
397 | 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 | doloop_simplify_count (class loop *loop, scalar_int_mode mode, rtx count) |
415 | { |
416 | widest_int iterations; |
417 | if (GET_CODE (count) == ZERO_EXTEND) |
418 | { |
419 | rtx extop0 = XEXP (count, 0); |
420 | if (GET_CODE (extop0) == PLUS) |
421 | { |
422 | rtx addop0 = XEXP (extop0, 0); |
423 | rtx addop1 = XEXP (extop0, 1); |
424 | |
425 | if (get_max_loop_iterations (loop, nit: &iterations) |
426 | && wi::ltu_p (x: iterations, GET_MODE_MASK (GET_MODE (addop0))) |
427 | && addop1 == constm1_rtx) |
428 | return simplify_gen_unary (code: ZERO_EXTEND, mode, op: addop0, |
429 | GET_MODE (addop0)); |
430 | } |
431 | } |
432 | |
433 | return simplify_gen_binary (code: PLUS, mode, op0: count, const1_rtx); |
434 | } |
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 | doloop_modify (class loop *loop, class niter_desc *desc, |
444 | rtx_insn *doloop_seq, rtx condition, rtx count) |
445 | { |
446 | rtx counter_reg; |
447 | rtx tmp, noloop = NULL_RTX; |
448 | rtx_insn *sequence; |
449 | rtx_insn *jump_insn; |
450 | rtx_code_label *jump_label; |
451 | int nonneg = 0; |
452 | bool increment_count; |
453 | basic_block loop_end = desc->out_edge->src; |
454 | scalar_int_mode mode; |
455 | widest_int iterations; |
456 | |
457 | jump_insn = BB_END (loop_end); |
458 | |
459 | if (dump_file) |
460 | { |
461 | fprintf (stream: dump_file, format: "Doloop: Inserting doloop pattern (" ); |
462 | if (desc->const_iter) |
463 | fprintf (stream: dump_file, format: "%" PRId64, desc->niter); |
464 | else |
465 | fputs (s: "runtime" , stream: dump_file); |
466 | fputs (s: " iterations).\n" , stream: 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 | delete_insn (jump_insn); |
472 | |
473 | counter_reg = XEXP (condition, 0); |
474 | if (GET_CODE (counter_reg) == PLUS) |
475 | counter_reg = XEXP (counter_reg, 0); |
476 | /* These patterns must operate on integer counters. */ |
477 | mode = as_a <scalar_int_mode> (GET_MODE (counter_reg)); |
478 | |
479 | increment_count = false; |
480 | switch (GET_CODE (condition)) |
481 | { |
482 | case NE: |
483 | /* Currently only NE tests against zero and one are supported. */ |
484 | noloop = XEXP (condition, 1); |
485 | if (noloop != const0_rtx) |
486 | { |
487 | gcc_assert (noloop == const1_rtx); |
488 | increment_count = true; |
489 | } |
490 | break; |
491 | |
492 | case GE: |
493 | /* Currently only GE tests against zero are supported. */ |
494 | gcc_assert (XEXP (condition, 1) == const0_rtx); |
495 | |
496 | noloop = constm1_rtx; |
497 | |
498 | /* The iteration count does not need incrementing for a GE test. */ |
499 | 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 | if (get_max_loop_iterations (loop, nit: &iterations) |
504 | && wi::leu_p (x: iterations, |
505 | y: wi::set_bit_in_zero <widest_int> |
506 | (GET_MODE_PRECISION (mode) - 1))) |
507 | nonneg = 1; |
508 | break; |
509 | |
510 | /* Abort if an invalid doloop pattern has been generated. */ |
511 | default: |
512 | gcc_unreachable (); |
513 | } |
514 | |
515 | if (increment_count) |
516 | count = doloop_simplify_count (loop, mode, count); |
517 | |
518 | /* Insert initialization of the count register into the loop header. */ |
519 | start_sequence (); |
520 | /* count has been already copied through copy_rtx. */ |
521 | reset_used_flags (count); |
522 | set_used_flags (condition); |
523 | tmp = force_operand (count, counter_reg); |
524 | convert_move (counter_reg, tmp, 1); |
525 | sequence = get_insns (); |
526 | unshare_all_rtl_in_chain (sequence); |
527 | end_sequence (); |
528 | emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src)); |
529 | |
530 | if (desc->noloop_assumptions) |
531 | { |
532 | rtx ass = copy_rtx (desc->noloop_assumptions); |
533 | basic_block = loop_preheader_edge (loop)->src; |
534 | basic_block set_zero = split_edge (loop_preheader_edge (loop)); |
535 | basic_block = split_edge (loop_preheader_edge (loop)); |
536 | edge te; |
537 | |
538 | /* Expand the condition testing the assumptions and if it does not pass, |
539 | reset the count register to 0. */ |
540 | redirect_edge_and_branch_force (single_succ_edge (bb: preheader), new_preheader); |
541 | set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader); |
542 | |
543 | set_zero->count = profile_count::uninitialized (); |
544 | |
545 | te = single_succ_edge (bb: preheader); |
546 | for (; ass; ass = XEXP (ass, 1)) |
547 | if (!add_test (XEXP (ass, 0), e: &te, dest: set_zero)) |
548 | break; |
549 | |
550 | 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 | set_zero->count = preheader->count; |
559 | } |
560 | |
561 | if (EDGE_COUNT (set_zero->preds) == 0) |
562 | { |
563 | /* All the conditions were simplified to false, remove the |
564 | unreachable set_zero block. */ |
565 | delete_basic_block (set_zero); |
566 | } |
567 | else |
568 | { |
569 | /* Reset the counter to zero in the set_zero block. */ |
570 | start_sequence (); |
571 | convert_move (counter_reg, noloop, 0); |
572 | sequence = get_insns (); |
573 | end_sequence (); |
574 | emit_insn_after (sequence, BB_END (set_zero)); |
575 | |
576 | set_immediate_dominator (CDI_DOMINATORS, set_zero, |
577 | recompute_dominator (CDI_DOMINATORS, |
578 | set_zero)); |
579 | } |
580 | |
581 | 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 | if (targetm.have_doloop_begin ()) |
589 | if (rtx_insn *seq = targetm.gen_doloop_begin (counter_reg, doloop_seq)) |
590 | emit_insn_after (seq, BB_END (loop_preheader_edge (loop)->src)); |
591 | |
592 | /* Insert the new low-overhead looping insn. */ |
593 | emit_jump_insn_after (doloop_seq, BB_END (loop_end)); |
594 | jump_insn = BB_END (loop_end); |
595 | jump_label = block_label (desc->in_edge->dest); |
596 | JUMP_LABEL (jump_insn) = jump_label; |
597 | LABEL_NUSES (jump_label)++; |
598 | |
599 | /* Ensure the right fallthru edge is marked, for case we have reversed |
600 | the condition. */ |
601 | desc->in_edge->flags &= ~EDGE_FALLTHRU; |
602 | 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 | if (nonneg) |
607 | add_reg_note (jump_insn, REG_NONNEG, NULL_RTX); |
608 | |
609 | /* Update the REG_BR_PROB note. */ |
610 | if (desc->in_edge->probability.initialized_p ()) |
611 | add_reg_br_prob_note (jump_insn, desc->in_edge->probability); |
612 | } |
613 | |
614 | /* Called through note_stores. */ |
615 | |
616 | static void |
617 | record_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data) |
618 | { |
619 | bitmap mod = (bitmap)data; |
620 | if (REG_P (x)) |
621 | { |
622 | unsigned int regno = REGNO (x); |
623 | if (HARD_REGISTER_P (x)) |
624 | { |
625 | unsigned int end_regno = end_hard_regno (GET_MODE (x), regno); |
626 | do |
627 | bitmap_set_bit (mod, regno); |
628 | while (++regno < end_regno); |
629 | } |
630 | else |
631 | bitmap_set_bit (mod, regno); |
632 | } |
633 | } |
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 | doloop_optimize (class loop *loop) |
642 | { |
643 | scalar_int_mode mode; |
644 | rtx doloop_reg; |
645 | rtx count; |
646 | widest_int iterations, iterations_max; |
647 | rtx_code_label *start_label; |
648 | rtx condition; |
649 | unsigned level; |
650 | HOST_WIDE_INT est_niter; |
651 | int max_cost; |
652 | class niter_desc *desc; |
653 | unsigned word_mode_size; |
654 | unsigned HOST_WIDE_INT word_mode_max; |
655 | int entered_at_top; |
656 | |
657 | if (dump_file) |
658 | fprintf (stream: dump_file, format: "Doloop: Processing loop %d.\n" , loop->num); |
659 | |
660 | iv_analysis_loop_init (loop); |
661 | |
662 | /* Find the simple exit of a LOOP. */ |
663 | desc = get_simple_loop_desc (loop); |
664 | |
665 | /* Check that loop is a candidate for a low-overhead looping insn. */ |
666 | if (!doloop_valid_p (loop, desc)) |
667 | { |
668 | if (dump_file) |
669 | fprintf (stream: dump_file, |
670 | format: "Doloop: The loop is not suitable.\n" ); |
671 | return false; |
672 | } |
673 | mode = desc->mode; |
674 | |
675 | est_niter = get_estimated_loop_iterations_int (loop); |
676 | if (est_niter == -1) |
677 | est_niter = get_likely_max_loop_iterations_int (loop); |
678 | |
679 | if (est_niter >= 0 && est_niter < 3) |
680 | { |
681 | if (dump_file) |
682 | fprintf (stream: dump_file, |
683 | format: "Doloop: Too few iterations (%u) to be profitable.\n" , |
684 | (unsigned int)est_niter); |
685 | return false; |
686 | } |
687 | |
688 | max_cost |
689 | = COSTS_N_INSNS (param_max_iterations_computation_cost); |
690 | if (set_src_cost (x: desc->niter_expr, mode, speed_p: optimize_loop_for_speed_p (loop)) |
691 | > max_cost) |
692 | { |
693 | if (dump_file) |
694 | fprintf (stream: dump_file, |
695 | format: "Doloop: number of iterations too costly to compute.\n" ); |
696 | return false; |
697 | } |
698 | |
699 | if (desc->const_iter) |
700 | iterations = widest_int::from (x: rtx_mode_t (desc->niter_expr, mode), |
701 | sgn: UNSIGNED); |
702 | else |
703 | iterations = 0; |
704 | if (!get_max_loop_iterations (loop, nit: &iterations_max)) |
705 | iterations_max = 0; |
706 | level = get_loop_level (loop) + 1; |
707 | entered_at_top = (loop->latch == desc->in_edge->dest |
708 | && contains_no_active_insn_p (loop->latch)); |
709 | if (!targetm.can_use_doloop_p (iterations, iterations_max, level, |
710 | entered_at_top)) |
711 | { |
712 | if (dump_file) |
713 | fprintf (stream: dump_file, format: "Loop rejected by can_use_doloop_p.\n" ); |
714 | 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 | count = copy_rtx (desc->niter_expr); |
721 | start_label = block_label (desc->in_edge->dest); |
722 | doloop_reg = gen_reg_rtx (mode); |
723 | rtx_insn *doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label); |
724 | |
725 | word_mode_size = GET_MODE_PRECISION (mode: word_mode); |
726 | word_mode_max = (HOST_WIDE_INT_1U << (word_mode_size - 1) << 1) - 1; |
727 | if (! doloop_seq |
728 | && 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 | && (word_mode_size >= GET_MODE_PRECISION (mode) |
733 | || wi::leu_p (x: iterations_max, y: word_mode_max))) |
734 | { |
735 | if (word_mode_size > GET_MODE_PRECISION (mode)) |
736 | count = simplify_gen_unary (code: ZERO_EXTEND, mode: word_mode, op: count, op_mode: mode); |
737 | else |
738 | count = lowpart_subreg (outermode: word_mode, op: count, innermode: mode); |
739 | PUT_MODE (x: doloop_reg, mode: word_mode); |
740 | doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label); |
741 | } |
742 | if (! doloop_seq) |
743 | { |
744 | if (dump_file) |
745 | fprintf (stream: dump_file, |
746 | format: "Doloop: Target unwilling to use doloop pattern!\n" ); |
747 | 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 | while (NEXT_INSN (insn: doloop_insn) != NULL_RTX) |
754 | doloop_insn = NEXT_INSN (insn: doloop_insn); |
755 | if (!JUMP_P (doloop_insn) |
756 | || !(condition = doloop_condition_get (doloop_pat: doloop_insn))) |
757 | { |
758 | if (dump_file) |
759 | fprintf (stream: dump_file, format: "Doloop: Unrecognizable doloop pattern!\n" ); |
760 | 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 | { |
766 | bitmap modified = BITMAP_ALLOC (NULL); |
767 | |
768 | for (rtx_insn *i = doloop_seq; i != NULL; i = NEXT_INSN (insn: i)) |
769 | note_stores (i, record_reg_sets, modified); |
770 | |
771 | basic_block loop_end = desc->out_edge->src; |
772 | bool fail = bitmap_intersect_p (df_get_live_out (bb: loop_end), modified); |
773 | BITMAP_FREE (modified); |
774 | |
775 | if (fail) |
776 | { |
777 | if (dump_file) |
778 | fprintf (stream: dump_file, format: "Doloop: doloop pattern clobbers live out\n" ); |
779 | return false; |
780 | } |
781 | } |
782 | |
783 | doloop_modify (loop, desc, doloop_seq, condition, count); |
784 | return true; |
785 | } |
786 | |
787 | /* This is the main entry point. Process all loops using doloop_optimize. */ |
788 | |
789 | void |
790 | doloop_optimize_loops (void) |
791 | { |
792 | if (optimize == 1) |
793 | { |
794 | df_live_add_problem (); |
795 | df_live_set_all_dirty (); |
796 | } |
797 | |
798 | for (auto loop : loops_list (cfun, 0)) |
799 | doloop_optimize (loop); |
800 | |
801 | if (optimize == 1) |
802 | df_remove_problem (df_live); |
803 | |
804 | iv_analysis_done (); |
805 | |
806 | checking_verify_loop_structure (); |
807 | } |
808 | |