Mercurial > hg > CbC > CbC_gcc

comparison gcc/auto-inc-dec.c @ 0:a06113de4d67

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