Line data Source code
1 : /* Discovery of auto-inc and auto-dec instructions.
2 : Copyright (C) 2006-2026 Free Software Foundation, Inc.
3 : Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
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 "predict.h"
29 : #include "df.h"
30 : #include "insn-config.h"
31 : #include "memmodel.h"
32 : #include "emit-rtl.h"
33 : #include "recog.h"
34 : #include "cfgrtl.h"
35 : #include "expr.h"
36 : #include "tree-pass.h"
37 : #include "dbgcnt.h"
38 : #include "print-rtl.h"
39 : #include "valtrack.h"
40 :
41 : /* This pass was originally removed from flow.c. However there is
42 : almost nothing that remains of that code.
43 :
44 : There are (4) basic forms that are matched:
45 :
46 : (1) FORM_PRE_ADD
47 : a <- b + c
48 : ...
49 : *a
50 :
51 : becomes
52 :
53 : a <- b
54 : ...
55 : *(a += c) pre
56 :
57 : or, alternately,
58 :
59 : a <- b + c
60 : ...
61 : *b
62 :
63 : becomes
64 :
65 : a <- b
66 : ...
67 : *(a += c) post
68 :
69 : This uses a post-add, but it's handled as FORM_PRE_ADD because
70 : the "increment" insn appears before the memory access.
71 :
72 :
73 : (2) FORM_PRE_INC
74 : a += c
75 : ...
76 : *a
77 :
78 : becomes
79 :
80 : ...
81 : *(a += c) pre
82 :
83 :
84 : (3) FORM_POST_ADD
85 : *a
86 : ...
87 : b <- a + c
88 :
89 : (For this case to be true, b must not be assigned or used between
90 : the *a and the assignment to b. B must also be a Pmode reg.)
91 :
92 : becomes
93 :
94 : b <- a
95 : *(b += c) post
96 : ...
97 :
98 :
99 : (4) FORM_POST_INC
100 : *a
101 : ...
102 : a <- a + c
103 :
104 : becomes
105 :
106 : *(a += c) post
107 : ...
108 :
109 :
110 : There are three types of values of c.
111 :
112 : 1) c is a constant equal to the width of the value being accessed by
113 : the pointer. This is useful for machines that have
114 : HAVE_PRE_INCREMENT, HAVE_POST_INCREMENT, HAVE_PRE_DECREMENT or
115 : HAVE_POST_DECREMENT defined.
116 :
117 : 2) c is a constant not equal to the width of the value being accessed
118 : by the pointer. This is useful for machines that have
119 : HAVE_PRE_MODIFY_DISP, HAVE_POST_MODIFY_DISP defined.
120 :
121 : 3) c is a register. This is useful for machines that have
122 : HAVE_PRE_MODIFY_REG, HAVE_POST_MODIFY_REG
123 :
124 : The is one special case: if a already had an offset equal to it +-
125 : its width and that offset is equal to -c when the increment was
126 : before the ref or +c if the increment was after the ref, then if we
127 : can do the combination but switch the pre/post bit. */
128 :
129 :
130 : enum form
131 : {
132 : FORM_PRE_ADD,
133 : FORM_PRE_INC,
134 : FORM_POST_ADD,
135 : FORM_POST_INC,
136 : FORM_last
137 : };
138 :
139 : /* The states of the second operands of mem refs and inc insns. If no
140 : second operand of the mem_ref was found, it is assumed to just be
141 : ZERO. SIZE is the size of the mode accessed in the memref. The
142 : ANY is used for constants that are not +-size or 0. REG is used if
143 : the forms are reg1 + reg2. */
144 :
145 : enum inc_state
146 : {
147 : INC_ZERO, /* == 0 */
148 : INC_NEG_SIZE, /* == +size */
149 : INC_POS_SIZE, /* == -size */
150 : INC_NEG_ANY, /* == some -constant */
151 : INC_POS_ANY, /* == some +constant */
152 : INC_REG, /* == some register */
153 : INC_last
154 : };
155 :
156 : /* The eight forms that pre/post inc/dec can take. */
157 : enum gen_form
158 : {
159 : NOTHING,
160 : SIMPLE_PRE_INC, /* ++size */
161 : SIMPLE_POST_INC, /* size++ */
162 : SIMPLE_PRE_DEC, /* --size */
163 : SIMPLE_POST_DEC, /* size-- */
164 : DISP_PRE, /* ++con */
165 : DISP_POST, /* con++ */
166 : REG_PRE, /* ++reg */
167 : REG_POST /* reg++ */
168 : };
169 :
170 : /* Tmp mem rtx for use in cost modeling. */
171 : static rtx mem_tmp;
172 :
173 : static enum inc_state
174 0 : set_inc_state (HOST_WIDE_INT val, poly_int64 size)
175 : {
176 0 : if (val == 0)
177 : return INC_ZERO;
178 0 : if (val < 0)
179 0 : return known_eq (val, -size) ? INC_NEG_SIZE : INC_NEG_ANY;
180 : else
181 0 : return known_eq (val, size) ? INC_POS_SIZE : INC_POS_ANY;
182 : }
183 :
184 : /* The DECISION_TABLE that describes what form, if any, the increment
185 : or decrement will take. It is a three dimensional table. The first
186 : index is the type of constant or register found as the second
187 : operand of the inc insn. The second index is the type of constant
188 : or register found as the second operand of the memory reference (if
189 : no second operand exists, 0 is used). The third index is the form
190 : and location (relative to the mem reference) of inc insn. */
191 :
192 : static bool initialized = false;
193 : static enum gen_form decision_table[INC_last][INC_last][FORM_last];
194 :
195 : static void
196 0 : init_decision_table (void)
197 : {
198 0 : enum gen_form value;
199 :
200 0 : if (HAVE_PRE_INCREMENT || HAVE_PRE_MODIFY_DISP)
201 : {
202 : /* Prefer the simple form if both are available. */
203 : value = (HAVE_PRE_INCREMENT) ? SIMPLE_PRE_INC : DISP_PRE;
204 :
205 : decision_table[INC_POS_SIZE][INC_ZERO][FORM_PRE_ADD] = value;
206 : decision_table[INC_POS_SIZE][INC_ZERO][FORM_PRE_INC] = value;
207 :
208 : decision_table[INC_POS_SIZE][INC_POS_SIZE][FORM_POST_ADD] = value;
209 : decision_table[INC_POS_SIZE][INC_POS_SIZE][FORM_POST_INC] = value;
210 : }
211 :
212 0 : if (HAVE_POST_INCREMENT || HAVE_POST_MODIFY_DISP)
213 : {
214 : /* Prefer the simple form if both are available. */
215 : value = (HAVE_POST_INCREMENT) ? SIMPLE_POST_INC : DISP_POST;
216 :
217 : decision_table[INC_POS_SIZE][INC_ZERO][FORM_POST_ADD] = value;
218 : decision_table[INC_POS_SIZE][INC_ZERO][FORM_POST_INC] = value;
219 :
220 : decision_table[INC_POS_SIZE][INC_NEG_SIZE][FORM_PRE_ADD] = value;
221 : decision_table[INC_POS_SIZE][INC_NEG_SIZE][FORM_PRE_INC] = value;
222 : }
223 :
224 0 : if (HAVE_PRE_DECREMENT || HAVE_PRE_MODIFY_DISP)
225 : {
226 : /* Prefer the simple form if both are available. */
227 : value = (HAVE_PRE_DECREMENT) ? SIMPLE_PRE_DEC : DISP_PRE;
228 :
229 : decision_table[INC_NEG_SIZE][INC_ZERO][FORM_PRE_ADD] = value;
230 : decision_table[INC_NEG_SIZE][INC_ZERO][FORM_PRE_INC] = value;
231 :
232 : decision_table[INC_NEG_SIZE][INC_NEG_SIZE][FORM_POST_ADD] = value;
233 : decision_table[INC_NEG_SIZE][INC_NEG_SIZE][FORM_POST_INC] = value;
234 : }
235 :
236 0 : if (HAVE_POST_DECREMENT || HAVE_POST_MODIFY_DISP)
237 : {
238 : /* Prefer the simple form if both are available. */
239 : value = (HAVE_POST_DECREMENT) ? SIMPLE_POST_DEC : DISP_POST;
240 :
241 : decision_table[INC_NEG_SIZE][INC_ZERO][FORM_POST_ADD] = value;
242 : decision_table[INC_NEG_SIZE][INC_ZERO][FORM_POST_INC] = value;
243 :
244 : decision_table[INC_NEG_SIZE][INC_POS_SIZE][FORM_PRE_ADD] = value;
245 : decision_table[INC_NEG_SIZE][INC_POS_SIZE][FORM_PRE_INC] = value;
246 : }
247 :
248 0 : if (HAVE_PRE_MODIFY_DISP)
249 : {
250 : decision_table[INC_POS_ANY][INC_ZERO][FORM_PRE_ADD] = DISP_PRE;
251 : decision_table[INC_POS_ANY][INC_ZERO][FORM_PRE_INC] = DISP_PRE;
252 :
253 : decision_table[INC_POS_ANY][INC_POS_ANY][FORM_POST_ADD] = DISP_PRE;
254 : decision_table[INC_POS_ANY][INC_POS_ANY][FORM_POST_INC] = DISP_PRE;
255 :
256 : decision_table[INC_NEG_ANY][INC_ZERO][FORM_PRE_ADD] = DISP_PRE;
257 : decision_table[INC_NEG_ANY][INC_ZERO][FORM_PRE_INC] = DISP_PRE;
258 :
259 : decision_table[INC_NEG_ANY][INC_NEG_ANY][FORM_POST_ADD] = DISP_PRE;
260 : decision_table[INC_NEG_ANY][INC_NEG_ANY][FORM_POST_INC] = DISP_PRE;
261 : }
262 :
263 0 : if (HAVE_POST_MODIFY_DISP)
264 : {
265 : decision_table[INC_POS_ANY][INC_ZERO][FORM_POST_ADD] = DISP_POST;
266 : decision_table[INC_POS_ANY][INC_ZERO][FORM_POST_INC] = DISP_POST;
267 :
268 : decision_table[INC_POS_ANY][INC_NEG_ANY][FORM_PRE_ADD] = DISP_POST;
269 : decision_table[INC_POS_ANY][INC_NEG_ANY][FORM_PRE_INC] = DISP_POST;
270 :
271 : decision_table[INC_NEG_ANY][INC_ZERO][FORM_POST_ADD] = DISP_POST;
272 : decision_table[INC_NEG_ANY][INC_ZERO][FORM_POST_INC] = DISP_POST;
273 :
274 : decision_table[INC_NEG_ANY][INC_POS_ANY][FORM_PRE_ADD] = DISP_POST;
275 : decision_table[INC_NEG_ANY][INC_POS_ANY][FORM_PRE_INC] = DISP_POST;
276 : }
277 :
278 : /* This is much simpler than the other cases because we do not look
279 : for the reg1-reg2 case. Note that we do not have a INC_POS_REG
280 : and INC_NEG_REG states. Most of the use of such states would be
281 : on a target that had an R1 - R2 update address form.
282 :
283 : There is the remote possibility that you could also catch a = a +
284 : b; *(a - b) as a postdecrement of (a + b). However, it is
285 : unclear if *(a - b) would ever be generated on a machine that did
286 : not have that kind of addressing mode. The IA-64 and RS6000 will
287 : not do this, and I cannot speak for any other. If any
288 : architecture does have an a-b update for, these cases should be
289 : added. */
290 0 : if (HAVE_PRE_MODIFY_REG)
291 : {
292 : decision_table[INC_REG][INC_ZERO][FORM_PRE_ADD] = REG_PRE;
293 : decision_table[INC_REG][INC_ZERO][FORM_PRE_INC] = REG_PRE;
294 :
295 : decision_table[INC_REG][INC_REG][FORM_POST_ADD] = REG_PRE;
296 : decision_table[INC_REG][INC_REG][FORM_POST_INC] = REG_PRE;
297 : }
298 :
299 0 : if (HAVE_POST_MODIFY_REG)
300 : {
301 : decision_table[INC_REG][INC_ZERO][FORM_POST_ADD] = REG_POST;
302 : decision_table[INC_REG][INC_ZERO][FORM_POST_INC] = REG_POST;
303 : }
304 :
305 0 : initialized = true;
306 0 : }
307 :
308 : /* Parsed fields of an inc insn of the form "reg_res = reg0+reg1" or
309 : "reg_res = reg0+c". */
310 :
311 : static struct inc_insn
312 : {
313 : rtx_insn *insn; /* The insn being parsed. */
314 : rtx pat; /* The pattern of the insn. */
315 : bool reg1_is_const; /* True if reg1 is const, false if reg1 is a reg. */
316 : enum form form;
317 : rtx reg_res;
318 : rtx reg0;
319 : rtx reg1;
320 : enum inc_state reg1_state;/* The form of the const if reg1 is a const. */
321 : HOST_WIDE_INT reg1_val;/* Value if reg1 is const. */
322 : } inc_insn;
323 :
324 :
325 : /* Dump the parsed inc insn to FILE. */
326 :
327 : static void
328 0 : dump_inc_insn (FILE *file)
329 : {
330 0 : const char *f = ((inc_insn.form == FORM_PRE_ADD)
331 0 : || (inc_insn.form == FORM_PRE_INC)) ? "pre" : "post";
332 :
333 0 : dump_insn_slim (file, inc_insn.insn);
334 :
335 0 : switch (inc_insn.form)
336 : {
337 0 : case FORM_PRE_ADD:
338 0 : case FORM_POST_ADD:
339 0 : if (inc_insn.reg1_is_const)
340 0 : fprintf (file, "found %s add(%d) r[%d]=r[%d]+%d\n",
341 0 : f, INSN_UID (inc_insn.insn),
342 0 : REGNO (inc_insn.reg_res),
343 0 : REGNO (inc_insn.reg0), (int) inc_insn.reg1_val);
344 : else
345 0 : fprintf (file, "found %s add(%d) r[%d]=r[%d]+r[%d]\n",
346 0 : f, INSN_UID (inc_insn.insn),
347 0 : REGNO (inc_insn.reg_res),
348 0 : REGNO (inc_insn.reg0), REGNO (inc_insn.reg1));
349 : break;
350 :
351 0 : case FORM_PRE_INC:
352 0 : case FORM_POST_INC:
353 0 : if (inc_insn.reg1_is_const)
354 0 : fprintf (file, "found %s inc(%d) r[%d]+=%d\n",
355 0 : f, INSN_UID (inc_insn.insn),
356 0 : REGNO (inc_insn.reg_res), (int) inc_insn.reg1_val);
357 : else
358 0 : fprintf (file, "found %s inc(%d) r[%d]+=r[%d]\n",
359 0 : f, INSN_UID (inc_insn.insn),
360 0 : REGNO (inc_insn.reg_res), REGNO (inc_insn.reg1));
361 : break;
362 :
363 : default:
364 : break;
365 : }
366 0 : }
367 :
368 :
369 : /* Parsed fields of a mem ref of the form "*(reg0+reg1)" or "*(reg0+c)". */
370 :
371 : static struct mem_insn
372 : {
373 : rtx_insn *insn; /* The insn being parsed. */
374 : rtx pat; /* The pattern of the insn. */
375 : rtx *mem_loc; /* The address of the field that holds the mem */
376 : /* that is to be replaced. */
377 : bool reg1_is_const; /* True if reg1 is const, false if reg1 is a reg. */
378 : rtx reg0;
379 : rtx reg1; /* This is either a reg or a const depending on
380 : reg1_is_const. */
381 : enum inc_state reg1_state;/* The form of the const if reg1 is a const. */
382 : HOST_WIDE_INT reg1_val;/* Value if reg1 is const. */
383 : } mem_insn;
384 :
385 :
386 : /* Dump the parsed mem insn to FILE. */
387 :
388 : static void
389 0 : dump_mem_insn (FILE *file)
390 : {
391 0 : dump_insn_slim (file, mem_insn.insn);
392 :
393 0 : if (mem_insn.reg1_is_const)
394 0 : fprintf (file, "found mem(%d) *(r[%d]+%d)\n",
395 0 : INSN_UID (mem_insn.insn),
396 0 : REGNO (mem_insn.reg0), (int) mem_insn.reg1_val);
397 : else
398 0 : fprintf (file, "found mem(%d) *(r[%d]+r[%d])\n",
399 0 : INSN_UID (mem_insn.insn),
400 0 : REGNO (mem_insn.reg0), REGNO (mem_insn.reg1));
401 0 : }
402 :
403 :
404 : /* The following three arrays contain pointers to instructions. They
405 : are indexed by REGNO. At any point in the basic block where we are
406 : looking these three arrays contain, respectively, the next insn
407 : that uses REGNO, the next inc or add insn that uses REGNO and the
408 : next insn that sets REGNO.
409 :
410 : The arrays are not cleared when we move from block to block so
411 : whenever an insn is retrieved from these arrays, it's block number
412 : must be compared with the current block.
413 : */
414 :
415 : static rtx_insn **reg_next_debug_use = NULL;
416 : static rtx_insn **reg_next_use = NULL;
417 : static rtx_insn **reg_next_inc_use = NULL;
418 : static rtx_insn **reg_next_def = NULL;
419 :
420 :
421 : /* Move dead note that match PATTERN to TO_INSN from FROM_INSN. We do
422 : not really care about moving any other notes from the inc or add
423 : insn. Moving the REG_EQUAL and REG_EQUIV is clearly wrong and it
424 : does not appear that there are any other kinds of relevant notes. */
425 :
426 : static void
427 0 : move_dead_notes (rtx_insn *to_insn, rtx_insn *from_insn, rtx pattern)
428 : {
429 0 : rtx note;
430 0 : rtx next_note;
431 0 : rtx prev_note = NULL;
432 :
433 0 : for (note = REG_NOTES (from_insn); note; note = next_note)
434 : {
435 0 : next_note = XEXP (note, 1);
436 :
437 0 : if ((REG_NOTE_KIND (note) == REG_DEAD)
438 0 : && pattern == XEXP (note, 0))
439 : {
440 0 : XEXP (note, 1) = REG_NOTES (to_insn);
441 0 : REG_NOTES (to_insn) = note;
442 0 : if (prev_note)
443 0 : XEXP (prev_note, 1) = next_note;
444 : else
445 0 : REG_NOTES (from_insn) = next_note;
446 : }
447 : else prev_note = note;
448 : }
449 0 : }
450 :
451 : /* Change mem_insn.mem_loc so that uses NEW_ADDR which has an
452 : increment of INC_REG. To have reached this point, the change is a
453 : legitimate one from a dataflow point of view. The only questions
454 : are is this a valid change to the instruction and is this a
455 : profitable change to the instruction. */
456 :
457 : static bool
458 0 : attempt_change (rtx new_addr, rtx inc_reg)
459 : {
460 : /* There are four cases: For the two cases that involve an add
461 : instruction, we are going to have to delete the add and insert a
462 : mov. We are going to assume that the mov is free. This is
463 : fairly early in the backend and there are a lot of opportunities
464 : for removing that move later. In particular, there is the case
465 : where the move may be dead, this is what dead code elimination
466 : passes are for. The two cases where we have an inc insn will be
467 : handled mov free. */
468 :
469 0 : basic_block bb = BLOCK_FOR_INSN (mem_insn.insn);
470 0 : rtx_insn *mov_insn = NULL;
471 0 : int regno;
472 0 : rtx mem = *mem_insn.mem_loc;
473 0 : machine_mode mode = GET_MODE (mem);
474 0 : int align = MEM_ALIGN (mem);
475 0 : rtx new_mem;
476 0 : int old_cost = 0;
477 0 : int new_cost = 0;
478 0 : bool speed = optimize_bb_for_speed_p (bb);
479 :
480 0 : PUT_MODE (mem_tmp, mode);
481 0 : XEXP (mem_tmp, 0) = new_addr;
482 0 : set_mem_align (mem_tmp, align);
483 :
484 0 : old_cost = (set_src_cost (mem, mode, speed)
485 0 : + set_rtx_cost (PATTERN (inc_insn.insn), speed));
486 :
487 0 : new_cost = set_src_cost (mem_tmp, mode, speed);
488 :
489 : /* In the FORM_PRE_ADD and FORM_POST_ADD cases we emit an extra move
490 : whose cost we should account for. */
491 0 : if (inc_insn.form == FORM_PRE_ADD
492 0 : || inc_insn.form == FORM_POST_ADD)
493 : {
494 0 : start_sequence ();
495 0 : emit_move_insn (inc_insn.reg_res, inc_insn.reg0);
496 0 : mov_insn = end_sequence ();
497 0 : new_cost += seq_cost (mov_insn, speed);
498 : }
499 :
500 : /* The first item of business is to see if this is profitable. */
501 0 : if (old_cost < new_cost)
502 : {
503 0 : if (dump_file)
504 0 : fprintf (dump_file, "cost failure old=%d new=%d\n", old_cost, new_cost);
505 0 : return false;
506 : }
507 :
508 : /* Jump through a lot of hoops to keep the attributes up to date. We
509 : do not want to call one of the change address variants that take
510 : an offset even though we know the offset in many cases. These
511 : assume you are changing where the address is pointing by the
512 : offset. */
513 0 : new_mem = replace_equiv_address_nv (mem, new_addr);
514 0 : if (! validate_change (mem_insn.insn, mem_insn.mem_loc, new_mem, 0))
515 : {
516 0 : if (dump_file)
517 0 : fprintf (dump_file, "validation failure\n");
518 0 : return false;
519 : }
520 :
521 : /* From here to the end of the function we are committed to the
522 : change, i.e. nothing fails. Generate any necessary movs, move
523 : any regnotes, and fix up the reg_next_{use,inc_use,def}. */
524 0 : switch (inc_insn.form)
525 : {
526 0 : case FORM_PRE_ADD:
527 : /* Replace the addition with a move. Do it at the location of
528 : the addition since the operand of the addition may change
529 : before the memory reference. */
530 0 : gcc_assert (mov_insn);
531 0 : emit_insn_before (mov_insn, inc_insn.insn);
532 0 : regno = REGNO (inc_insn.reg0);
533 : /* ??? Could REGNO possibly be used in MEM_INSN other than in
534 : the MEM address, and still die there, so that move_dead_notes
535 : would incorrectly move the note? */
536 0 : if (reg_next_use[regno] == mem_insn.insn)
537 0 : move_dead_notes (mov_insn, mem_insn.insn, inc_insn.reg0);
538 : else
539 0 : move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0);
540 :
541 0 : regno = REGNO (inc_insn.reg_res);
542 0 : if (reg_next_debug_use && reg_next_debug_use[regno]
543 0 : && BLOCK_FOR_INSN (reg_next_debug_use[regno]) == bb)
544 : {
545 0 : rtx adjres = gen_rtx_PLUS (GET_MODE (inc_insn.reg_res),
546 : inc_insn.reg_res, inc_insn.reg1);
547 0 : if (dump_file)
548 0 : fprintf (dump_file, "adjusting debug insns\n");
549 0 : propagate_for_debug (PREV_INSN (reg_next_debug_use[regno]),
550 : mem_insn.insn,
551 : inc_insn.reg_res, adjres, bb);
552 0 : reg_next_debug_use[regno] = NULL;
553 : }
554 0 : reg_next_def[regno] = mov_insn;
555 0 : reg_next_use[regno] = NULL;
556 :
557 0 : regno = REGNO (inc_insn.reg0);
558 0 : if (reg_next_debug_use && reg_next_debug_use[regno]
559 0 : && BLOCK_FOR_INSN (reg_next_debug_use[regno]) == bb
560 0 : && find_reg_note (mov_insn, REG_DEAD, inc_insn.reg0))
561 : {
562 0 : if (dump_file)
563 0 : fprintf (dump_file, "remapping debug insns\n");
564 0 : propagate_for_debug (PREV_INSN (reg_next_debug_use[regno]),
565 : mem_insn.insn,
566 : inc_insn.reg0, inc_insn.reg_res, bb);
567 0 : reg_next_debug_use[regno] = NULL;
568 : }
569 0 : reg_next_use[regno] = mov_insn;
570 0 : df_recompute_luids (bb);
571 0 : break;
572 :
573 0 : case FORM_POST_INC:
574 0 : regno = REGNO (inc_insn.reg_res);
575 0 : if (reg_next_debug_use && reg_next_debug_use[regno]
576 0 : && BLOCK_FOR_INSN (reg_next_debug_use[regno]) == bb)
577 : {
578 0 : rtx adjres = gen_rtx_MINUS (GET_MODE (inc_insn.reg_res),
579 : inc_insn.reg_res, inc_insn.reg1);
580 0 : if (dump_file)
581 0 : fprintf (dump_file, "adjusting debug insns\n");
582 0 : propagate_for_debug (PREV_INSN (reg_next_debug_use[regno]),
583 : inc_insn.insn,
584 : inc_insn.reg_res, adjres, bb);
585 0 : reg_next_debug_use[regno] = NULL;
586 : }
587 0 : if (reg_next_use[regno] == reg_next_inc_use[regno])
588 0 : reg_next_inc_use[regno] = NULL;
589 :
590 : /* Fallthru. */
591 0 : case FORM_PRE_INC:
592 0 : regno = REGNO (inc_insn.reg_res);
593 : /* Despite the fall-through, we won't run this twice: we'll have
594 : already cleared reg_next_debug_use[regno] before falling
595 : through. */
596 0 : if (reg_next_debug_use && reg_next_debug_use[regno]
597 0 : && BLOCK_FOR_INSN (reg_next_debug_use[regno]) == bb)
598 : {
599 0 : rtx adjres = gen_rtx_PLUS (GET_MODE (inc_insn.reg_res),
600 : inc_insn.reg_res, inc_insn.reg1);
601 0 : if (dump_file)
602 0 : fprintf (dump_file, "adjusting debug insns\n");
603 0 : propagate_for_debug (PREV_INSN (reg_next_debug_use[regno]),
604 : mem_insn.insn,
605 : inc_insn.reg_res, adjres, bb);
606 0 : if (DF_INSN_LUID (mem_insn.insn)
607 0 : < DF_INSN_LUID (reg_next_debug_use[regno]))
608 0 : reg_next_debug_use[regno] = NULL;
609 : }
610 0 : reg_next_def[regno] = mem_insn.insn;
611 0 : reg_next_use[regno] = NULL;
612 :
613 0 : break;
614 :
615 0 : case FORM_POST_ADD:
616 0 : gcc_assert (mov_insn);
617 0 : emit_insn_before (mov_insn, mem_insn.insn);
618 0 : move_dead_notes (mov_insn, inc_insn.insn, inc_insn.reg0);
619 :
620 : /* Do not move anything to the mov insn because the instruction
621 : pointer for the main iteration has not yet hit that. It is
622 : still pointing to the mem insn. */
623 0 : regno = REGNO (inc_insn.reg_res);
624 : /* The pseudo is now set earlier, so it must have been dead in
625 : that range, and dead registers cannot be referenced in debug
626 : insns. */
627 0 : gcc_assert (!(reg_next_debug_use && reg_next_debug_use[regno]
628 : && BLOCK_FOR_INSN (reg_next_debug_use[regno]) == bb));
629 0 : reg_next_def[regno] = mem_insn.insn;
630 0 : reg_next_use[regno] = NULL;
631 :
632 0 : regno = REGNO (inc_insn.reg0);
633 0 : if (reg_next_debug_use && reg_next_debug_use[regno]
634 0 : && BLOCK_FOR_INSN (reg_next_debug_use[regno]) == bb
635 0 : && find_reg_note (mov_insn, REG_DEAD, inc_insn.reg0))
636 : {
637 0 : if (dump_file)
638 0 : fprintf (dump_file, "remapping debug insns\n");
639 0 : propagate_for_debug (PREV_INSN (reg_next_debug_use[regno]),
640 : inc_insn.insn,
641 : inc_insn.reg0, inc_insn.reg_res, bb);
642 0 : reg_next_debug_use[regno] = NULL;
643 : }
644 0 : reg_next_use[regno] = mem_insn.insn;
645 0 : if ((reg_next_use[regno] == reg_next_inc_use[regno])
646 0 : || (reg_next_inc_use[regno] == inc_insn.insn))
647 0 : reg_next_inc_use[regno] = NULL;
648 0 : df_recompute_luids (bb);
649 0 : break;
650 :
651 0 : case FORM_last:
652 0 : default:
653 0 : gcc_unreachable ();
654 : }
655 :
656 0 : if (!inc_insn.reg1_is_const)
657 : {
658 0 : regno = REGNO (inc_insn.reg1);
659 0 : reg_next_use[regno] = mem_insn.insn;
660 0 : if ((reg_next_use[regno] == reg_next_inc_use[regno])
661 0 : || (reg_next_inc_use[regno] == inc_insn.insn))
662 0 : reg_next_inc_use[regno] = NULL;
663 : }
664 :
665 0 : delete_insn (inc_insn.insn);
666 :
667 0 : if (dump_file && mov_insn)
668 : {
669 0 : fprintf (dump_file, "inserting mov ");
670 0 : dump_insn_slim (dump_file, mov_insn);
671 : }
672 :
673 : /* Record that this insn has an implicit side effect. */
674 0 : add_reg_note (mem_insn.insn, REG_INC, inc_reg);
675 :
676 0 : if (dump_file)
677 : {
678 0 : fprintf (dump_file, "****success ");
679 0 : dump_insn_slim (dump_file, mem_insn.insn);
680 : }
681 :
682 : return true;
683 : }
684 :
685 :
686 : /* Try to combine the instruction in INC_INSN with the instruction in
687 : MEM_INSN. First the form is determined using the DECISION_TABLE
688 : and the results of parsing the INC_INSN and the MEM_INSN.
689 : Assuming the form is ok, a prototype new address is built which is
690 : passed to ATTEMPT_CHANGE for final processing. */
691 :
692 : static bool
693 0 : try_merge (void)
694 : {
695 0 : enum gen_form gen_form;
696 0 : rtx mem = *mem_insn.mem_loc;
697 0 : rtx inc_reg = inc_insn.form == FORM_POST_ADD ?
698 : inc_insn.reg_res : mem_insn.reg0;
699 :
700 : /* The width of the mem being accessed. */
701 0 : poly_int64 size = GET_MODE_SIZE (GET_MODE (mem));
702 0 : rtx_insn *last_insn = NULL;
703 0 : machine_mode reg_mode = GET_MODE (inc_reg);
704 :
705 0 : switch (inc_insn.form)
706 : {
707 0 : case FORM_PRE_ADD:
708 0 : case FORM_PRE_INC:
709 0 : last_insn = mem_insn.insn;
710 0 : break;
711 0 : case FORM_POST_INC:
712 0 : case FORM_POST_ADD:
713 0 : last_insn = inc_insn.insn;
714 0 : break;
715 0 : case FORM_last:
716 0 : default:
717 0 : gcc_unreachable ();
718 : }
719 :
720 : /* Cannot handle auto inc of the stack. */
721 0 : if (inc_reg == stack_pointer_rtx)
722 : {
723 0 : if (dump_file)
724 0 : fprintf (dump_file, "cannot inc stack %d failure\n", REGNO (inc_reg));
725 0 : return false;
726 : }
727 :
728 : /* Look to see if the inc register is dead after the memory
729 : reference. If it is, do not do the combination. */
730 0 : if (find_regno_note (last_insn, REG_DEAD, REGNO (inc_reg)))
731 : {
732 0 : if (dump_file)
733 0 : fprintf (dump_file, "dead failure %d\n", REGNO (inc_reg));
734 0 : return false;
735 : }
736 :
737 0 : mem_insn.reg1_state = (mem_insn.reg1_is_const)
738 0 : ? set_inc_state (mem_insn.reg1_val, size) : INC_REG;
739 0 : inc_insn.reg1_state = (inc_insn.reg1_is_const)
740 0 : ? set_inc_state (inc_insn.reg1_val, size) : INC_REG;
741 :
742 : /* Now get the form that we are generating. */
743 0 : gen_form = decision_table
744 0 : [inc_insn.reg1_state][mem_insn.reg1_state][inc_insn.form];
745 :
746 0 : if (dbg_cnt (auto_inc_dec) == false)
747 : return false;
748 :
749 0 : switch (gen_form)
750 : {
751 : default:
752 : case NOTHING:
753 : return false;
754 :
755 0 : case SIMPLE_PRE_INC: /* ++size */
756 0 : if (dump_file)
757 0 : fprintf (dump_file, "trying SIMPLE_PRE_INC\n");
758 0 : return attempt_change (gen_rtx_PRE_INC (reg_mode, inc_reg), inc_reg);
759 :
760 0 : case SIMPLE_POST_INC: /* size++ */
761 0 : if (dump_file)
762 0 : fprintf (dump_file, "trying SIMPLE_POST_INC\n");
763 0 : return attempt_change (gen_rtx_POST_INC (reg_mode, inc_reg), inc_reg);
764 :
765 0 : case SIMPLE_PRE_DEC: /* --size */
766 0 : if (dump_file)
767 0 : fprintf (dump_file, "trying SIMPLE_PRE_DEC\n");
768 0 : return attempt_change (gen_rtx_PRE_DEC (reg_mode, inc_reg), inc_reg);
769 :
770 0 : case SIMPLE_POST_DEC: /* size-- */
771 0 : if (dump_file)
772 0 : fprintf (dump_file, "trying SIMPLE_POST_DEC\n");
773 0 : return attempt_change (gen_rtx_POST_DEC (reg_mode, inc_reg), inc_reg);
774 :
775 0 : case DISP_PRE: /* ++con */
776 0 : if (dump_file)
777 0 : fprintf (dump_file, "trying DISP_PRE\n");
778 0 : return attempt_change (gen_rtx_PRE_MODIFY (reg_mode,
779 : inc_reg,
780 : gen_rtx_PLUS (reg_mode,
781 : inc_reg,
782 : inc_insn.reg1)),
783 0 : inc_reg);
784 :
785 0 : case DISP_POST: /* con++ */
786 0 : if (dump_file)
787 0 : fprintf (dump_file, "trying POST_DISP\n");
788 0 : return attempt_change (gen_rtx_POST_MODIFY (reg_mode,
789 : inc_reg,
790 : gen_rtx_PLUS (reg_mode,
791 : inc_reg,
792 : inc_insn.reg1)),
793 0 : inc_reg);
794 :
795 0 : case REG_PRE: /* ++reg */
796 0 : if (dump_file)
797 0 : fprintf (dump_file, "trying PRE_REG\n");
798 0 : return attempt_change (gen_rtx_PRE_MODIFY (reg_mode,
799 : inc_reg,
800 : gen_rtx_PLUS (reg_mode,
801 : inc_reg,
802 : inc_insn.reg1)),
803 0 : inc_reg);
804 :
805 0 : case REG_POST: /* reg++ */
806 0 : if (dump_file)
807 0 : fprintf (dump_file, "trying POST_REG\n");
808 0 : return attempt_change (gen_rtx_POST_MODIFY (reg_mode,
809 : inc_reg,
810 : gen_rtx_PLUS (reg_mode,
811 : inc_reg,
812 : inc_insn.reg1)),
813 0 : inc_reg);
814 : }
815 : }
816 :
817 : /* Return the next insn that uses (if reg_next_use is passed in
818 : NEXT_ARRAY) or defines (if reg_next_def is passed in NEXT_ARRAY)
819 : REGNO in BB. */
820 :
821 : static rtx_insn *
822 0 : get_next_ref (int regno, basic_block bb, rtx_insn **next_array)
823 : {
824 0 : rtx_insn *insn = next_array[regno];
825 :
826 : /* Lazy about cleaning out the next_arrays. */
827 0 : if (insn && BLOCK_FOR_INSN (insn) != bb)
828 : {
829 0 : next_array[regno] = NULL;
830 0 : insn = NULL;
831 : }
832 :
833 0 : return insn;
834 : }
835 :
836 :
837 : /* Return true if INSN is of a form "a = b op c" where a and b are
838 : regs. op is + if c is a reg and +|- if c is a const. Fill in
839 : INC_INSN with what is found.
840 :
841 : This function is called in two contexts, if BEFORE_MEM is true,
842 : this is called for each insn in the basic block. If BEFORE_MEM is
843 : false, it is called for the instruction in the block that uses the
844 : index register for some memory reference that is currently being
845 : processed. */
846 :
847 : static bool
848 0 : parse_add_or_inc (rtx_insn *insn, bool before_mem)
849 : {
850 0 : rtx pat = single_set (insn);
851 0 : if (!pat)
852 : return false;
853 :
854 : /* Result must be single reg. */
855 0 : if (!REG_P (SET_DEST (pat)))
856 : return false;
857 :
858 0 : if ((GET_CODE (SET_SRC (pat)) != PLUS)
859 0 : && (GET_CODE (SET_SRC (pat)) != MINUS))
860 : return false;
861 :
862 0 : if (!REG_P (XEXP (SET_SRC (pat), 0)))
863 : return false;
864 :
865 0 : inc_insn.insn = insn;
866 0 : inc_insn.pat = pat;
867 0 : inc_insn.reg_res = SET_DEST (pat);
868 0 : inc_insn.reg0 = XEXP (SET_SRC (pat), 0);
869 :
870 : /* Block any auto increment of the frame pointer since it expands into
871 : an addition and cannot be removed by copy propagation. */
872 0 : if (inc_insn.reg0 == frame_pointer_rtx)
873 : return false;
874 :
875 0 : if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg0))
876 0 : inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC;
877 : else
878 0 : inc_insn.form = before_mem ? FORM_PRE_ADD : FORM_POST_ADD;
879 :
880 0 : if (CONST_INT_P (XEXP (SET_SRC (pat), 1)))
881 : {
882 : /* Process a = b + c where c is a const. */
883 0 : inc_insn.reg1_is_const = true;
884 0 : if (GET_CODE (SET_SRC (pat)) == PLUS)
885 : {
886 0 : inc_insn.reg1 = XEXP (SET_SRC (pat), 1);
887 0 : inc_insn.reg1_val = INTVAL (inc_insn.reg1);
888 : }
889 : else
890 : {
891 0 : inc_insn.reg1_val = -INTVAL (XEXP (SET_SRC (pat), 1));
892 0 : inc_insn.reg1 = GEN_INT (inc_insn.reg1_val);
893 : }
894 0 : return true;
895 : }
896 : else if ((HAVE_PRE_MODIFY_REG || HAVE_POST_MODIFY_REG)
897 : && (REG_P (XEXP (SET_SRC (pat), 1)))
898 : && GET_CODE (SET_SRC (pat)) == PLUS)
899 : {
900 : /* Process a = b + c where c is a reg. */
901 : inc_insn.reg1 = XEXP (SET_SRC (pat), 1);
902 : inc_insn.reg1_is_const = false;
903 :
904 : if (inc_insn.form == FORM_PRE_INC
905 : || inc_insn.form == FORM_POST_INC)
906 : return true;
907 : else if (rtx_equal_p (inc_insn.reg_res, inc_insn.reg1))
908 : {
909 : /* Reverse the two operands and turn *_ADD into *_INC since
910 : a = c + a. */
911 : std::swap (inc_insn.reg0, inc_insn.reg1);
912 : inc_insn.form = before_mem ? FORM_PRE_INC : FORM_POST_INC;
913 : return true;
914 : }
915 : else
916 : return true;
917 : }
918 :
919 : return false;
920 : }
921 :
922 :
923 : /* A recursive function that checks all of the mem uses in
924 : ADDRESS_OF_X to see if any single one of them is compatible with
925 : what has been found in inc_insn. To avoid accidental matches, we
926 : will only find MEMs with FINDREG, be it inc_insn.reg_res, be it
927 : inc_insn.reg0.
928 :
929 : -1 is returned for success. 0 is returned if nothing was found and
930 : 1 is returned for failure. */
931 :
932 : static int
933 0 : find_address (rtx *address_of_x, rtx findreg)
934 : {
935 0 : rtx x = *address_of_x;
936 0 : enum rtx_code code = GET_CODE (x);
937 0 : const char *const fmt = GET_RTX_FORMAT (code);
938 0 : int i;
939 0 : int value = 0;
940 0 : int tem;
941 :
942 0 : if (code == MEM && findreg == inc_insn.reg_res
943 0 : && rtx_equal_p (XEXP (x, 0), inc_insn.reg_res))
944 : {
945 : /* Match with *reg_res. */
946 0 : mem_insn.mem_loc = address_of_x;
947 0 : mem_insn.reg0 = inc_insn.reg_res;
948 0 : mem_insn.reg1_is_const = true;
949 0 : mem_insn.reg1_val = 0;
950 0 : mem_insn.reg1 = GEN_INT (0);
951 0 : return -1;
952 : }
953 0 : if (code == MEM && inc_insn.reg1_is_const && inc_insn.reg0
954 0 : && findreg == inc_insn.reg0
955 0 : && rtx_equal_p (XEXP (x, 0), inc_insn.reg0))
956 : {
957 : /* Match with *reg0, assumed to be equivalent to
958 : *(reg_res - reg1_val); callers must check whether this is the case. */
959 0 : mem_insn.mem_loc = address_of_x;
960 0 : mem_insn.reg0 = inc_insn.reg_res;
961 0 : mem_insn.reg1_is_const = true;
962 0 : mem_insn.reg1_val = -inc_insn.reg1_val;
963 0 : mem_insn.reg1 = GEN_INT (mem_insn.reg1_val);
964 0 : return -1;
965 : }
966 0 : if (code == MEM && findreg == inc_insn.reg_res
967 0 : && GET_CODE (XEXP (x, 0)) == PLUS
968 0 : && rtx_equal_p (XEXP (XEXP (x, 0), 0), inc_insn.reg_res))
969 : {
970 0 : rtx b = XEXP (XEXP (x, 0), 1);
971 0 : mem_insn.mem_loc = address_of_x;
972 0 : mem_insn.reg0 = inc_insn.reg_res;
973 0 : mem_insn.reg1 = b;
974 0 : mem_insn.reg1_is_const = inc_insn.reg1_is_const;
975 0 : if (CONST_INT_P (b))
976 : {
977 : /* Match with *(reg0 + reg1) where reg1 is a const. */
978 0 : HOST_WIDE_INT val = INTVAL (b);
979 0 : if (inc_insn.reg1_is_const
980 0 : && (inc_insn.reg1_val == val || inc_insn.reg1_val == -val))
981 : {
982 0 : mem_insn.reg1_val = val;
983 0 : return -1;
984 : }
985 : }
986 0 : else if (!inc_insn.reg1_is_const
987 0 : && rtx_equal_p (inc_insn.reg1, b))
988 : /* Match with *(reg0 + reg1). */
989 : return -1;
990 : }
991 :
992 0 : if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
993 : {
994 : /* If REG occurs inside a MEM used in a bit-field reference,
995 : that is unacceptable. */
996 0 : if (find_address (&XEXP (x, 0), findreg))
997 : return 1;
998 : }
999 :
1000 0 : if (x == inc_insn.reg_res)
1001 : return 1;
1002 :
1003 : /* Time for some deep diving. */
1004 0 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1005 : {
1006 0 : if (fmt[i] == 'e')
1007 : {
1008 0 : tem = find_address (&XEXP (x, i), findreg);
1009 : /* If this is the first use, let it go so the rest of the
1010 : insn can be checked. */
1011 0 : if (value == 0)
1012 : value = tem;
1013 0 : else if (tem != 0)
1014 : /* More than one match was found. */
1015 : return 1;
1016 : }
1017 0 : else if (fmt[i] == 'E')
1018 : {
1019 0 : int j;
1020 0 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1021 : {
1022 0 : tem = find_address (&XVECEXP (x, i, j), findreg);
1023 : /* If this is the first use, let it go so the rest of
1024 : the insn can be checked. */
1025 0 : if (value == 0)
1026 : value = tem;
1027 0 : else if (tem != 0)
1028 : /* More than one match was found. */
1029 : return 1;
1030 : }
1031 : }
1032 : }
1033 : return value;
1034 : }
1035 :
1036 : /* Once a suitable mem reference has been found and the MEM_INSN
1037 : structure has been filled in, FIND_INC is called to see if there is
1038 : a suitable add or inc insn that follows the mem reference and
1039 : determine if it is suitable to merge.
1040 :
1041 : In the case where the MEM_INSN has two registers in the reference,
1042 : this function may be called recursively. The first time looking
1043 : for an add of the first register, and if that fails, looking for an
1044 : add of the second register. The FIRST_TRY parameter is used to
1045 : only allow the parameters to be reversed once. */
1046 :
1047 : static bool
1048 0 : find_inc (bool first_try)
1049 : {
1050 0 : rtx_insn *insn;
1051 0 : basic_block bb = BLOCK_FOR_INSN (mem_insn.insn);
1052 0 : rtx_insn *other_insn;
1053 0 : df_ref def;
1054 :
1055 : /* Make sure this reg appears only once in this insn. */
1056 0 : if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg0, 1) != 1)
1057 : {
1058 0 : if (dump_file)
1059 0 : fprintf (dump_file, "mem count failure\n");
1060 0 : return false;
1061 : }
1062 :
1063 0 : if (dump_file)
1064 0 : dump_mem_insn (dump_file);
1065 :
1066 : /* Find the next use that is an inc. */
1067 0 : insn = get_next_ref (REGNO (mem_insn.reg0),
1068 0 : BLOCK_FOR_INSN (mem_insn.insn),
1069 : reg_next_inc_use);
1070 0 : if (!insn)
1071 0 : return false;
1072 :
1073 : /* Even though we know the next use is an add or inc because it came
1074 : from the reg_next_inc_use, we must still reparse. */
1075 0 : if (!parse_add_or_inc (insn, false))
1076 : {
1077 : /* Next use was not an add. Look for one extra case. It could be
1078 : that we have:
1079 :
1080 : *(a + b)
1081 : ...= a;
1082 : ...= b + a
1083 :
1084 : if we reverse the operands in the mem ref we would
1085 : find this. Only try it once though. */
1086 0 : if (first_try && !mem_insn.reg1_is_const)
1087 : {
1088 0 : std::swap (mem_insn.reg0, mem_insn.reg1);
1089 0 : return find_inc (false);
1090 : }
1091 : else
1092 : return false;
1093 : }
1094 :
1095 : /* Need to assure that none of the operands of the inc instruction are
1096 : assigned to by the mem insn. */
1097 0 : FOR_EACH_INSN_DEF (def, mem_insn.insn)
1098 : {
1099 0 : unsigned int regno = DF_REF_REGNO (def);
1100 0 : if ((regno == REGNO (inc_insn.reg0))
1101 0 : || (regno == REGNO (inc_insn.reg_res)))
1102 : {
1103 0 : if (dump_file)
1104 0 : fprintf (dump_file, "inc conflicts with store failure.\n");
1105 0 : return false;
1106 : }
1107 0 : if (!inc_insn.reg1_is_const && (regno == REGNO (inc_insn.reg1)))
1108 : {
1109 0 : if (dump_file)
1110 0 : fprintf (dump_file, "inc conflicts with store failure.\n");
1111 0 : return false;
1112 : }
1113 : }
1114 :
1115 0 : if (dump_file)
1116 0 : dump_inc_insn (dump_file);
1117 :
1118 0 : if (inc_insn.form == FORM_POST_ADD)
1119 : {
1120 : /* Make sure that there is no insn that assigns to inc_insn.res
1121 : between the mem_insn and the inc_insn. */
1122 0 : rtx_insn *other_insn = get_next_ref (REGNO (inc_insn.reg_res),
1123 0 : BLOCK_FOR_INSN (mem_insn.insn),
1124 : reg_next_def);
1125 0 : if (other_insn != inc_insn.insn)
1126 : {
1127 0 : if (dump_file)
1128 0 : fprintf (dump_file,
1129 : "result of add is assigned to between mem and inc insns.\n");
1130 0 : return false;
1131 : }
1132 :
1133 0 : other_insn = get_next_ref (REGNO (inc_insn.reg_res),
1134 0 : BLOCK_FOR_INSN (mem_insn.insn),
1135 : reg_next_use);
1136 0 : if (other_insn
1137 0 : && (other_insn != inc_insn.insn)
1138 0 : && (DF_INSN_LUID (inc_insn.insn) > DF_INSN_LUID (other_insn)))
1139 : {
1140 0 : if (dump_file)
1141 0 : fprintf (dump_file,
1142 : "result of add is used between mem and inc insns.\n");
1143 0 : return false;
1144 : }
1145 :
1146 : /* For the post_add to work, the result_reg of the inc must not be
1147 : used in the mem insn since this will become the new index
1148 : register. */
1149 0 : if (reg_overlap_mentioned_p (inc_insn.reg_res, PATTERN (mem_insn.insn)))
1150 : {
1151 0 : if (dump_file)
1152 0 : fprintf (dump_file, "base reg replacement failure.\n");
1153 0 : return false;
1154 : }
1155 : }
1156 :
1157 0 : if (mem_insn.reg1_is_const)
1158 : {
1159 0 : if (mem_insn.reg1_val == 0)
1160 : {
1161 0 : if (!inc_insn.reg1_is_const)
1162 : {
1163 : /* The mem looks like *r0 and the rhs of the add has two
1164 : registers. */
1165 0 : int luid = DF_INSN_LUID (inc_insn.insn);
1166 0 : if (inc_insn.form == FORM_POST_ADD)
1167 : {
1168 : /* The trick is that we are not going to increment r0,
1169 : we are going to increment the result of the add insn.
1170 : For this trick to be correct, the result reg of
1171 : the inc must be a valid addressing reg. */
1172 0 : addr_space_t as = MEM_ADDR_SPACE (*mem_insn.mem_loc);
1173 0 : if (GET_MODE (inc_insn.reg_res)
1174 0 : != targetm.addr_space.address_mode (as))
1175 : {
1176 0 : if (dump_file)
1177 0 : fprintf (dump_file, "base reg mode failure.\n");
1178 0 : return false;
1179 : }
1180 :
1181 : /* We also need to make sure that the next use of
1182 : inc result is after the inc. */
1183 0 : other_insn
1184 0 : = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use);
1185 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1186 : return false;
1187 :
1188 0 : if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1189 0 : std::swap (inc_insn.reg0, inc_insn.reg1);
1190 : }
1191 :
1192 0 : other_insn
1193 0 : = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1194 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1195 : return false;
1196 : }
1197 : }
1198 : /* Both the inc/add and the mem have a constant. Need to check
1199 : that the constants are ok. */
1200 0 : else if ((mem_insn.reg1_val != inc_insn.reg1_val)
1201 0 : && (mem_insn.reg1_val != -inc_insn.reg1_val))
1202 : return false;
1203 : }
1204 : else
1205 : {
1206 : /* The mem insn is of the form *(a + b) where a and b are both
1207 : regs. It may be that in order to match the add or inc we
1208 : need to treat it as if it was *(b + a). It may also be that
1209 : the add is of the form a + c where c does not match b and
1210 : then we just abandon this. */
1211 :
1212 0 : int luid = DF_INSN_LUID (inc_insn.insn);
1213 0 : rtx_insn *other_insn;
1214 :
1215 : /* Make sure this reg appears only once in this insn. */
1216 0 : if (count_occurrences (PATTERN (mem_insn.insn), mem_insn.reg1, 1) != 1)
1217 : return false;
1218 :
1219 0 : if (inc_insn.form == FORM_POST_ADD)
1220 : {
1221 : /* For this trick to be correct, the result reg of the inc
1222 : must be a valid addressing reg. */
1223 0 : addr_space_t as = MEM_ADDR_SPACE (*mem_insn.mem_loc);
1224 0 : if (GET_MODE (inc_insn.reg_res)
1225 0 : != targetm.addr_space.address_mode (as))
1226 : {
1227 0 : if (dump_file)
1228 0 : fprintf (dump_file, "base reg mode failure.\n");
1229 0 : return false;
1230 : }
1231 :
1232 0 : if (rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1233 : {
1234 0 : if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1))
1235 : {
1236 : /* See comment above on find_inc (false) call. */
1237 0 : if (first_try)
1238 : {
1239 0 : std::swap (mem_insn.reg0, mem_insn.reg1);
1240 0 : return find_inc (false);
1241 : }
1242 : else
1243 : return false;
1244 : }
1245 :
1246 : /* Need to check that there are no assignments to b
1247 : before the add insn. */
1248 0 : other_insn
1249 0 : = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1250 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1251 : return false;
1252 : /* All ok for the next step. */
1253 : }
1254 : else
1255 : {
1256 : /* We know that mem_insn.reg0 must equal inc_insn.reg1
1257 : or else we would not have found the inc insn. */
1258 0 : std::swap (mem_insn.reg0, mem_insn.reg1);
1259 0 : if (!rtx_equal_p (mem_insn.reg0, inc_insn.reg0))
1260 : {
1261 : /* See comment above on find_inc (false) call. */
1262 0 : if (first_try)
1263 0 : return find_inc (false);
1264 : else
1265 : return false;
1266 : }
1267 : /* To have gotten here know that.
1268 : *(b + a)
1269 :
1270 : ... = (b + a)
1271 :
1272 : We also know that the lhs of the inc is not b or a. We
1273 : need to make sure that there are no assignments to b
1274 : between the mem ref and the inc. */
1275 :
1276 0 : other_insn
1277 0 : = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_def);
1278 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1279 : return false;
1280 : }
1281 :
1282 : /* Need to check that the next use of the add result is later than
1283 : add insn since this will be the reg incremented. */
1284 0 : other_insn
1285 0 : = get_next_ref (REGNO (inc_insn.reg_res), bb, reg_next_use);
1286 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1287 : return false;
1288 : }
1289 : else /* FORM_POST_INC. There is less to check here because we
1290 : know that operands must line up. */
1291 : {
1292 0 : if (!rtx_equal_p (mem_insn.reg1, inc_insn.reg1))
1293 : /* See comment above on find_inc (false) call. */
1294 : {
1295 0 : if (first_try)
1296 : {
1297 0 : std::swap (mem_insn.reg0, mem_insn.reg1);
1298 0 : return find_inc (false);
1299 : }
1300 : else
1301 : return false;
1302 : }
1303 :
1304 : /* To have gotten here know that.
1305 : *(a + b)
1306 :
1307 : ... = (a + b)
1308 :
1309 : We also know that the lhs of the inc is not b. We need to make
1310 : sure that there are no assignments to b between the mem ref and
1311 : the inc. */
1312 0 : other_insn
1313 0 : = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1314 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1315 : return false;
1316 : }
1317 : }
1318 :
1319 0 : if (inc_insn.form == FORM_POST_INC)
1320 : {
1321 0 : other_insn
1322 0 : = get_next_ref (REGNO (inc_insn.reg0), bb, reg_next_use);
1323 : /* When we found inc_insn, we were looking for the
1324 : next add or inc, not the next insn that used the
1325 : reg. Because we are going to increment the reg
1326 : in this form, we need to make sure that there
1327 : were no intervening uses of reg. */
1328 0 : if (inc_insn.insn != other_insn)
1329 : return false;
1330 : }
1331 :
1332 0 : return try_merge ();
1333 : }
1334 :
1335 :
1336 : /* A recursive function that walks ADDRESS_OF_X to find all of the mem
1337 : uses in pat that could be used as an auto inc or dec. It then
1338 : calls FIND_INC for each one. */
1339 :
1340 : static bool
1341 0 : find_mem (rtx *address_of_x)
1342 : {
1343 0 : rtx x = *address_of_x;
1344 0 : enum rtx_code code = GET_CODE (x);
1345 0 : const char *const fmt = GET_RTX_FORMAT (code);
1346 0 : int i;
1347 :
1348 0 : if (code == MEM && REG_P (XEXP (x, 0)))
1349 : {
1350 : /* Match with *reg0. */
1351 0 : mem_insn.mem_loc = address_of_x;
1352 0 : mem_insn.reg0 = XEXP (x, 0);
1353 0 : mem_insn.reg1_is_const = true;
1354 0 : mem_insn.reg1_val = 0;
1355 0 : mem_insn.reg1 = GEN_INT (0);
1356 0 : if (find_inc (true))
1357 : return true;
1358 : }
1359 0 : if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
1360 0 : && REG_P (XEXP (XEXP (x, 0), 0)))
1361 : {
1362 0 : rtx reg1 = XEXP (XEXP (x, 0), 1);
1363 0 : mem_insn.mem_loc = address_of_x;
1364 0 : mem_insn.reg0 = XEXP (XEXP (x, 0), 0);
1365 0 : mem_insn.reg1 = reg1;
1366 0 : if (CONST_INT_P (reg1))
1367 : {
1368 0 : mem_insn.reg1_is_const = true;
1369 : /* Match with *(reg0 + c) where c is a const. */
1370 0 : mem_insn.reg1_val = INTVAL (reg1);
1371 0 : if (find_inc (true))
1372 : return true;
1373 : }
1374 0 : else if (REG_P (reg1))
1375 : {
1376 : /* Match with *(reg0 + reg1). */
1377 0 : mem_insn.reg1_is_const = false;
1378 0 : if (find_inc (true))
1379 : return true;
1380 : }
1381 : }
1382 :
1383 0 : if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
1384 : {
1385 : /* If REG occurs inside a MEM used in a bit-field reference,
1386 : that is unacceptable. */
1387 : return false;
1388 : }
1389 :
1390 : /* Time for some deep diving. */
1391 0 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1392 : {
1393 0 : if (fmt[i] == 'e')
1394 : {
1395 0 : if (find_mem (&XEXP (x, i)))
1396 : return true;
1397 : }
1398 0 : else if (fmt[i] == 'E')
1399 : {
1400 0 : int j;
1401 0 : for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1402 0 : if (find_mem (&XVECEXP (x, i, j)))
1403 : return true;
1404 : }
1405 : }
1406 : return false;
1407 : }
1408 :
1409 :
1410 : /* Try to combine all incs and decs by constant values with memory
1411 : references in BB. */
1412 :
1413 : static void
1414 0 : merge_in_block (int max_reg, basic_block bb)
1415 : {
1416 0 : rtx_insn *insn;
1417 0 : rtx_insn *curr;
1418 0 : int success_in_block = 0;
1419 :
1420 0 : if (dump_file)
1421 0 : fprintf (dump_file, "\n\nstarting bb %d\n", bb->index);
1422 :
1423 0 : FOR_BB_INSNS_REVERSE_SAFE (bb, insn, curr)
1424 : {
1425 0 : bool insn_is_add_or_inc = true;
1426 :
1427 0 : if (!NONDEBUG_INSN_P (insn))
1428 : {
1429 0 : if (DEBUG_BIND_INSN_P (insn))
1430 : {
1431 0 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1432 0 : df_ref use;
1433 :
1434 0 : if (dump_file)
1435 0 : dump_insn_slim (dump_file, insn);
1436 :
1437 0 : FOR_EACH_INSN_INFO_USE (use, insn_info)
1438 0 : reg_next_debug_use[DF_REF_REGNO (use)] = insn;
1439 : }
1440 0 : continue;
1441 0 : }
1442 :
1443 : /* Reload should handle auto-inc within a jump correctly, while LRA
1444 : is known to have issues with autoinc. */
1445 0 : if (JUMP_P (insn) && targetm.lra_p ())
1446 0 : continue;
1447 :
1448 0 : if (dump_file)
1449 0 : dump_insn_slim (dump_file, insn);
1450 :
1451 : /* Does this instruction increment or decrement a register? */
1452 0 : if (parse_add_or_inc (insn, true))
1453 : {
1454 0 : int regno = REGNO (inc_insn.reg_res);
1455 : /* Cannot handle case where there are three separate regs
1456 : before a mem ref. Too many moves would be needed to be
1457 : profitable. */
1458 0 : if ((inc_insn.form == FORM_PRE_INC) || inc_insn.reg1_is_const)
1459 : {
1460 0 : mem_insn.insn = get_next_ref (regno, bb, reg_next_use);
1461 0 : if (mem_insn.insn)
1462 : {
1463 0 : bool ok = true;
1464 0 : if (!inc_insn.reg1_is_const)
1465 : {
1466 : /* We are only here if we are going to try a
1467 : HAVE_*_MODIFY_REG type transformation. c is a
1468 : reg and we must sure that the path from the
1469 : inc_insn to the mem_insn.insn is both def and use
1470 : clear of c because the inc insn is going to move
1471 : into the mem_insn.insn. */
1472 0 : int luid = DF_INSN_LUID (mem_insn.insn);
1473 0 : rtx_insn *other_insn
1474 0 : = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_use);
1475 :
1476 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1477 : ok = false;
1478 :
1479 0 : other_insn
1480 0 : = get_next_ref (REGNO (inc_insn.reg1), bb, reg_next_def);
1481 :
1482 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1483 : ok = false;
1484 : }
1485 :
1486 0 : if (dump_file)
1487 0 : dump_inc_insn (dump_file);
1488 :
1489 0 : if (ok && find_address (&PATTERN (mem_insn.insn),
1490 : inc_insn.reg_res) == -1)
1491 : {
1492 0 : if (dump_file)
1493 0 : dump_mem_insn (dump_file);
1494 0 : if (try_merge ())
1495 : {
1496 0 : success_in_block++;
1497 0 : insn_is_add_or_inc = false;
1498 : }
1499 : }
1500 : }
1501 :
1502 0 : if (insn_is_add_or_inc
1503 : /* find_address will only recognize an address
1504 : with a reg0 that's not reg_res when
1505 : reg1_is_const, so cut it off early if we
1506 : already know it won't match. */
1507 0 : && inc_insn.reg1_is_const
1508 0 : && inc_insn.reg0
1509 0 : && inc_insn.reg0 != inc_insn.reg_res)
1510 : {
1511 : /* If we identified an inc_insn that uses two
1512 : different pseudos, it's of the form
1513 :
1514 : (set reg_res (plus reg0 reg1))
1515 :
1516 : where reg1 is a constant (*).
1517 :
1518 : The next use of reg_res was not identified by
1519 : find_address as a mem_insn that we could turn
1520 : into auto-inc, so see if we find a suitable
1521 : MEM in the next use of reg0, as long as it's
1522 : before any subsequent use of reg_res:
1523 :
1524 : ... (mem (... reg0 ...)) ...
1525 :
1526 : ... reg_res ...
1527 :
1528 : In this case, we can turn the plus into a
1529 : copy, and the reg0 in the MEM address into a
1530 : post_inc of reg_res:
1531 :
1532 : (set reg_res reg0)
1533 :
1534 : ... (mem (... (post_add reg_res reg1) ...)) ...
1535 :
1536 : reg_res will then have the correct value at
1537 : subsequent uses, and reg0 will remain
1538 : unchanged.
1539 :
1540 : (*) We could support non-const reg1, but then
1541 : we'd have to check that reg1 remains
1542 : unchanged all the way to the modified MEM,
1543 : and we'd have to extend find_address to
1544 : represent a non-const negated reg1. */
1545 0 : regno = REGNO (inc_insn.reg0);
1546 0 : rtx_insn *reg0_use = get_next_ref (regno, bb,
1547 : reg_next_use);
1548 :
1549 : /* Give up if the next use of reg0 is after the next
1550 : use of reg_res (same insn is ok; we might have
1551 : found a MEM with reg_res before, and that failed,
1552 : but now we try reg0, which might work), or defs
1553 : of reg_res (same insn is not ok, we'd introduce
1554 : another def in the same insn) or reg0. */
1555 0 : if (reg0_use)
1556 : {
1557 0 : int luid = DF_INSN_LUID (reg0_use);
1558 :
1559 : /* It might seem pointless to introduce an
1560 : auto-inc if there's no subsequent use of
1561 : reg_res (i.e., mem_insn.insn == NULL), but
1562 : the next use might be in the next iteration
1563 : of a loop, and it won't hurt if we make the
1564 : change even if it's not needed. */
1565 0 : if (mem_insn.insn
1566 0 : && luid > DF_INSN_LUID (mem_insn.insn))
1567 : reg0_use = NULL;
1568 :
1569 0 : rtx_insn *other_insn
1570 0 : = get_next_ref (REGNO (inc_insn.reg_res), bb,
1571 : reg_next_def);
1572 :
1573 0 : if (other_insn && luid >= DF_INSN_LUID (other_insn))
1574 : reg0_use = NULL;
1575 :
1576 0 : other_insn
1577 0 : = get_next_ref (REGNO (inc_insn.reg0), bb,
1578 : reg_next_def);
1579 :
1580 0 : if (other_insn && luid > DF_INSN_LUID (other_insn))
1581 : reg0_use = NULL;
1582 : }
1583 :
1584 0 : mem_insn.insn = reg0_use;
1585 :
1586 0 : if (mem_insn.insn
1587 0 : && find_address (&PATTERN (mem_insn.insn),
1588 : inc_insn.reg0) == -1)
1589 : {
1590 0 : if (dump_file)
1591 0 : dump_mem_insn (dump_file);
1592 0 : if (try_merge ())
1593 : {
1594 0 : success_in_block++;
1595 0 : insn_is_add_or_inc = false;
1596 : }
1597 : }
1598 : }
1599 : }
1600 : }
1601 : else
1602 : {
1603 0 : insn_is_add_or_inc = false;
1604 : /* We can't use auto inc/dec for bare USEs and CLOBBERs,
1605 : since they aren't supposed to generate any code. */
1606 0 : rtx_code code = GET_CODE (PATTERN (insn));
1607 0 : if (code != USE && code != CLOBBER)
1608 : {
1609 0 : mem_insn.insn = insn;
1610 0 : if (find_mem (&PATTERN (insn)))
1611 0 : success_in_block++;
1612 : }
1613 : }
1614 :
1615 : /* If the inc insn was merged with a mem, the inc insn is gone
1616 : and there is noting to update. */
1617 0 : if (df_insn_info *insn_info = DF_INSN_INFO_GET (insn))
1618 : {
1619 0 : df_ref def, use;
1620 :
1621 : /* Need to update next use. */
1622 0 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
1623 : {
1624 0 : if (reg_next_debug_use)
1625 0 : reg_next_debug_use[DF_REF_REGNO (def)] = NULL;
1626 0 : reg_next_use[DF_REF_REGNO (def)] = NULL;
1627 0 : reg_next_inc_use[DF_REF_REGNO (def)] = NULL;
1628 0 : reg_next_def[DF_REF_REGNO (def)] = insn;
1629 : }
1630 :
1631 0 : FOR_EACH_INSN_INFO_USE (use, insn_info)
1632 : {
1633 0 : if (reg_next_debug_use)
1634 : /* This may seem surprising, but we know we may only
1635 : modify the value of a REG between an insn and the
1636 : next nondebug use thereof. Any debug uses after
1637 : the next nondebug use can be left alone, the REG
1638 : will hold the expected value there. */
1639 0 : reg_next_debug_use[DF_REF_REGNO (use)] = NULL;
1640 0 : reg_next_use[DF_REF_REGNO (use)] = insn;
1641 0 : if (insn_is_add_or_inc)
1642 0 : reg_next_inc_use[DF_REF_REGNO (use)] = insn;
1643 : else
1644 0 : reg_next_inc_use[DF_REF_REGNO (use)] = NULL;
1645 : }
1646 : }
1647 0 : else if (dump_file)
1648 0 : fprintf (dump_file, "skipping update of deleted insn %d\n",
1649 : INSN_UID (insn));
1650 : }
1651 :
1652 : /* If we were successful, try again. There may have been several
1653 : opportunities that were interleaved. This is rare but
1654 : gcc.c-torture/compile/pr17273.c actually exhibits this. */
1655 0 : if (success_in_block)
1656 : {
1657 : /* In this case, we must clear these vectors since the trick of
1658 : testing if the stale insn in the block will not work. */
1659 0 : if (reg_next_debug_use)
1660 0 : memset (reg_next_debug_use, 0, max_reg * sizeof (rtx));
1661 0 : memset (reg_next_use, 0, max_reg * sizeof (rtx));
1662 0 : memset (reg_next_inc_use, 0, max_reg * sizeof (rtx));
1663 0 : memset (reg_next_def, 0, max_reg * sizeof (rtx));
1664 0 : df_recompute_luids (bb);
1665 0 : merge_in_block (max_reg, bb);
1666 : }
1667 0 : }
1668 :
1669 : /* Discover auto-inc auto-dec instructions. */
1670 :
1671 : namespace {
1672 :
1673 : const pass_data pass_data_inc_dec =
1674 : {
1675 : RTL_PASS, /* type */
1676 : "auto_inc_dec", /* name */
1677 : OPTGROUP_NONE, /* optinfo_flags */
1678 : TV_AUTO_INC_DEC, /* tv_id */
1679 : 0, /* properties_required */
1680 : 0, /* properties_provided */
1681 : 0, /* properties_destroyed */
1682 : 0, /* todo_flags_start */
1683 : TODO_df_finish, /* todo_flags_finish */
1684 : };
1685 :
1686 : class pass_inc_dec : public rtl_opt_pass
1687 : {
1688 : public:
1689 285722 : pass_inc_dec (gcc::context *ctxt)
1690 571444 : : rtl_opt_pass (pass_data_inc_dec, ctxt)
1691 : {}
1692 :
1693 : /* opt_pass methods: */
1694 1471370 : bool gate (function *) final override
1695 : {
1696 1471370 : if (!AUTO_INC_DEC)
1697 1471370 : return false;
1698 :
1699 : return (optimize > 0 && flag_auto_inc_dec);
1700 : }
1701 :
1702 :
1703 : unsigned int execute (function *) final override;
1704 :
1705 : }; // class pass_inc_dec
1706 :
1707 : unsigned int
1708 0 : pass_inc_dec::execute (function *fun ATTRIBUTE_UNUSED)
1709 : {
1710 0 : if (!AUTO_INC_DEC)
1711 0 : return 0;
1712 :
1713 : basic_block bb;
1714 : int max_reg = max_reg_num ();
1715 :
1716 : if (!initialized)
1717 : init_decision_table ();
1718 :
1719 : mem_tmp = gen_rtx_MEM (Pmode, NULL_RTX);
1720 :
1721 : df_note_add_problem ();
1722 : df_analyze ();
1723 :
1724 : if (MAY_HAVE_DEBUG_BIND_INSNS)
1725 : reg_next_debug_use = XCNEWVEC (rtx_insn *, max_reg);
1726 : else
1727 : /* An earlier function may have had debug binds. */
1728 : reg_next_debug_use = NULL;
1729 : reg_next_use = XCNEWVEC (rtx_insn *, max_reg);
1730 : reg_next_inc_use = XCNEWVEC (rtx_insn *, max_reg);
1731 : reg_next_def = XCNEWVEC (rtx_insn *, max_reg);
1732 : FOR_EACH_BB_FN (bb, fun)
1733 : merge_in_block (max_reg, bb);
1734 :
1735 : free (reg_next_debug_use);
1736 : free (reg_next_use);
1737 : free (reg_next_inc_use);
1738 : free (reg_next_def);
1739 :
1740 : mem_tmp = NULL;
1741 :
1742 : return 0;
1743 : }
1744 :
1745 : } // anon namespace
1746 :
1747 : rtl_opt_pass *
1748 285722 : make_pass_inc_dec (gcc::context *ctxt)
1749 : {
1750 285722 : return new pass_inc_dec (ctxt);
1751 : }
|
