]>
Commit | Line | Data |
---|---|---|
6fb5fa3c | 1 | /* Discovery of auto-inc and auto-dec instructions. |
fa10beec | 2 | Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc. |
6fb5fa3c DB |
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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
6fb5fa3c DB |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6fb5fa3c DB |
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 | ||
0d52bcc1 | 92 | 2) c is a constant not equal to the width of the value being accessed |
6fb5fa3c DB |
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 | |
0d52bcc1 | 447 | does not appear that there are any other kinds of relevant notes. */ |
6fb5fa3c DB |
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; | |
f40751dd | 518 | bool speed = optimize_bb_for_speed_p (bb); |
6fb5fa3c DB |
519 | |
520 | PUT_MODE (mem_tmp, mode); | |
521 | XEXP (mem_tmp, 0) = new_addr; | |
522 | ||
f40751dd JH |
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); | |
6fb5fa3c DB |
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: | |
c8305c98 KZ |
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, | |
6fb5fa3c DB |
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. */ | |
65c5f2a6 | 625 | add_reg_note (mem_insn.insn, REG_INC, inc_reg); |
6fb5fa3c DB |
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 | |
fa10beec | 639 | and the results of parsing the INC_INSN and the MEM_INSN. |
6fb5fa3c DB |
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 | |
c8305c98 | 679 | reference. If it is, do not do the combination. */ |
6fb5fa3c DB |
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; | |
57512f53 | 1010 | df_ref *def_rec; |
6fb5fa3c DB |
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 | { | |
57512f53 | 1056 | df_ref def = *def_rec; |
6fb5fa3c DB |
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 | ||
0d52bcc1 | 1200 | /* Need to check that there are no assignments to b |
6fb5fa3c DB |
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 | |
6ed3da00 | 1281 | were no intervening uses of reg. */ |
6fb5fa3c DB |
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 | { | |
57512f53 KZ |
1457 | df_ref *def_rec; |
1458 | df_ref *use_rec; | |
6fb5fa3c DB |
1459 | /* Need to update next use. */ |
1460 | for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) | |
1461 | { | |
57512f53 | 1462 | df_ref def = *def_rec; |
6fb5fa3c DB |
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 | { | |
57512f53 | 1470 | df_ref use = *use_rec; |
6fb5fa3c DB |
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 | ||
8ddbbcae | 1543 | struct rtl_opt_pass pass_inc_dec = |
6fb5fa3c | 1544 | { |
8ddbbcae JH |
1545 | { |
1546 | RTL_PASS, | |
6fb5fa3c DB |
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 */ | |
8ddbbcae | 1560 | } |
6fb5fa3c DB |
1561 | }; |
1562 |