Mercurial > hg > CbC > CbC_gcc
comparison gcc/auto-inc-dec.c @ 0:a06113de4d67
first commit
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 17 Jul 2009 14:47:48 +0900 (2009-07-17) |
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 |