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