]> gcc.gnu.org Git - gcc.git/blame - gcc/regrename.c
git://gcc.gnu.org / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
fold-const.c (force_fit_type): Unsigned values can overflow if they are sizetype.
[gcc.git] / gcc / regrename.c
CommitLineData
7b82b5da
SC		 1/* Register renaming for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
3
4 This file is part of GNU CC.
5
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
20
21#include "config.h"
22#include "system.h"
23#include "tree.h"
24#include "rtl.h"
efc9bd41 25#include "hard-reg-set.h"
7b82b5da
SC		 26#include "basic-block.h"
27#include "insn-config.h"
28#include "regs.h"
7b82b5da
SC		 29#include "flags.h"
30#include "output.h"
31#include "function.h"
32#include "recog.h"
33#include "resource.h"
34
35static const char *const reg_class_names[] = REG_CLASS_NAMES;
36
37/* ??? Consider a more sparse data structure? */
38typedef struct def_uses
39 {
40 /* high bound of defs and uses */
41 int high_bound;
42
43 /* 1 if insn y defines a reg whose use crosses a call
44 y is the ordinal position of the insn within the block */
45 sbitmap require_call_save_reg;
46
47 /* REGNO x INSN y 1 if insn y sets reg x */
48 sbitmap *defs;
49
50 /* REGNO x INSN y The register class for this def */
51 enum reg_class *def_class;
52
53 /* REGNO x INSN y 1 if insn y uses reg x */
54 sbitmap *uses;
55
56 /* REGNO x INSN y The register class for this use */
57 enum reg_class *use_class;
58 }
59def_uses;
60
61#define DU_REG_CLASS(rc,r,high_bound,i) (rc[r * high_bound + i])
62
63typedef struct ext_basic_blocks
64 {
65 /* n_basic_blocks x n_basic_blocks y 1 if bb y is in extended bb
66 having entry x */
67 sbitmap *basic_block;
68
69 /* n_basic_blocks x n_basic_blocks y 1 if bb y is an exit block */
70 sbitmap *exit;
71 }
72ext_basic_blocks;
73
74#define UID_RUID_HIGH_BOUND 64
75#define DESTINATION 1
76#define SOURCE 2
77
1a43c33f
RK		 78static void build_def_use PARAMS ((int, ext_basic_blocks *,
79 HARD_REG_SET *, def_uses *,
80 sbitmap *));
81static int replace_reg_in_block PARAMS ((def_uses *, varray_type *,
82 int, rtx, unsigned int));
83static int consider_def PARAMS ((rtx, int, def_uses *, int));
84static int consider_available PARAMS ((rtx, int, HARD_REG_SET *,
85 int, def_uses *, int));
86static rtx rr_replace_reg PARAMS ((rtx, rtx, rtx, int, rtx,
87 int *));
88static int consider_use PARAMS ((rtx, int, int, int));
89static int condmove_p PARAMS ((rtx));
90static void dump_def_use_chain PARAMS ((HARD_REG_SET *, def_uses *,
91 varray_type *));
92static void dump_ext_bb_info PARAMS ((int, ext_basic_blocks *));
93static void find_ext_basic_blocks PARAMS ((ext_basic_blocks *));
94static void find_one_ext_basic_block PARAMS ((int, basic_block, sbitmap *,
95 ext_basic_blocks *));
96static enum reg_class get_reg_class PARAMS ((rtx, rtx, int,
97 enum reg_class));
98static rtx regno_first_use_in PARAMS ((unsigned int, rtx));
99\f
7b82b5da
SC		 100void
101regrename_optimize ()
102{
103 int b, eb, i, inum, r, rc, replace_ok;
104 rtx insn;
c0ee5d52
KG		 105 def_uses du;
106 ext_basic_blocks ebb;
7b82b5da 107
7b82b5da
SC		 108 /* Registers used in a given class */
109 HARD_REG_SET class_regs;
110
111 /* Registers available for use as renaming registers */
112 HARD_REG_SET avail_regs;
113
114 /* Registers used in the block */
115 HARD_REG_SET regs_used;
116
117 /* Registers which have been used as renaming registers */
118 HARD_REG_SET renamed_regs;
119
120 HARD_REG_SET global_live_at_end, global_live_at_start;
121
122 HARD_REG_SET null_bitmap, tmp_bitmap;
123
124 /* 1 if insn y sets a register which is live at the end of the block */
125 sbitmap defs_live_exit;
126
127 /* Mapping from insn y (ordinal position in block) to INSN_UID */
128 varray_type uid_ruid;
129
130 /* Mapping from insn y (ordinal position in block) to block id */
131 varray_type uid_rbid;
132
133 /* Ordinal position in block of defining insn */
134 int *def_idx;
135
136 VARRAY_RTX_INIT (uid_ruid, UID_RUID_HIGH_BOUND + 1, "uid_ruid");
137 VARRAY_LONG_INIT (uid_rbid, UID_RUID_HIGH_BOUND + 1, "uid_rbid");
138
1a43c33f
RK		 139 ebb.basic_block
140 = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
c0ee5d52 141 sbitmap_vector_zero (ebb.basic_block, n_basic_blocks);
1a43c33f
RK		 142 ebb.exit
143 = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
c0ee5d52 144 sbitmap_vector_zero (ebb.exit, n_basic_blocks);
7b82b5da 145
c0ee5d52 146 find_ext_basic_blocks (&ebb);
7b82b5da 147
c0ee5d52 148 du.def_class = du.use_class = 0;
7b82b5da
SC		 149
150 /* Build uid_ruid and uid_rbid for this extended basic block */
151 for (b = 0; b < n_basic_blocks; b++)
c0ee5d52 152 if (TEST_BIT (ebb.basic_block[b], b))
7b82b5da 153 {
c0ee5d52 154 for (eb = du.high_bound = 0; eb < n_basic_blocks; eb++)
1a43c33f
RK		 155 if (TEST_BIT (ebb.basic_block[b], eb))
156 {
157 basic_block bb = BASIC_BLOCK (eb);
158
159 /* Calculate high bound for uid_ruid and allocate if necessary */
160 for (insn = bb->head;
161 insn != NEXT_INSN (bb->end);
162 du.high_bound++, insn = NEXT_INSN (insn))
163 {
164 int uid_ruid_high_bound = VARRAY_SIZE (uid_ruid);
165
166 if (du.high_bound + 4 >= uid_ruid_high_bound)
167 {
168 VARRAY_GROW (uid_ruid, uid_ruid_high_bound * 2);
169 VARRAY_GROW (uid_rbid, uid_ruid_high_bound * 2);
170 }
171
172 VARRAY_RTX (uid_ruid, du.high_bound) = insn;
173 VARRAY_LONG (uid_rbid, du.high_bound) = eb;
174 }
175 }
7b82b5da
SC		 176
177 CLEAR_HARD_REG_SET (null_bitmap);
178 CLEAR_HARD_REG_SET (class_regs);
179 CLEAR_HARD_REG_SET (regs_used);
180 CLEAR_HARD_REG_SET (avail_regs);
181 CLEAR_HARD_REG_SET (tmp_bitmap);
182 CLEAR_HARD_REG_SET (renamed_regs);
183
1a43c33f
RK		 184 du.defs
185 = sbitmap_vector_alloc (FIRST_PSEUDO_REGISTER, du.high_bound + 1);
c0ee5d52 186 sbitmap_vector_zero (du.defs, FIRST_PSEUDO_REGISTER);
1a43c33f
RK		 187 du.uses
188 = sbitmap_vector_alloc (FIRST_PSEUDO_REGISTER, du.high_bound + 1);
c0ee5d52
KG		 189 sbitmap_vector_zero (du.uses, FIRST_PSEUDO_REGISTER);
190 du.require_call_save_reg = sbitmap_alloc (du.high_bound + 1);
191 sbitmap_zero (du.require_call_save_reg);
192 defs_live_exit = sbitmap_alloc (du.high_bound + 1);
7b82b5da
SC		 193 sbitmap_zero (defs_live_exit);
194
1a43c33f
RK		 195 du.def_class
196 = xrealloc (du.def_class,
197 (sizeof (enum reg_class) * FIRST_PSEUDO_REGISTER
198 * du.high_bound));
7b82b5da 199
1a43c33f
RK		 200 du.use_class
201 = xrealloc (du.use_class,
202 (sizeof (enum reg_class) * FIRST_PSEUDO_REGISTER
203 * du.high_bound));
7b82b5da 204
1a43c33f 205 build_def_use (b, &ebb, &regs_used, &du, &defs_live_exit);
7b82b5da
SC		 206
207 if (rtl_dump_file)
208 {
c0ee5d52
KG		 209 dump_ext_bb_info (b, &ebb);
210 dump_def_use_chain (&global_live_at_end, &du, &uid_ruid);
7b82b5da
SC		 211 }
212
213 /* Available registers are not: used in the block, live at the start,
214 live at the end, a register we've renamed to. */
215 /* ??? The current algorithm is pessimistic for extended basic blocks
216 as it just treats them as a big basic block. */
217
218 COPY_HARD_REG_SET (tmp_bitmap, regs_used);
1a43c33f
RK		 219 REG_SET_TO_HARD_REG_SET (global_live_at_start,
220 BASIC_BLOCK (b)->global_live_at_start);
7b82b5da
SC		 221 IOR_HARD_REG_SET (tmp_bitmap, global_live_at_start);
222 for (eb = 0; eb < n_basic_blocks; eb++)
1a43c33f
RK		 223 if (TEST_BIT (ebb.basic_block[b], eb))
224 {
225 basic_block bb = BASIC_BLOCK (eb);
226
227 REG_SET_TO_HARD_REG_SET (global_live_at_end,
228 bb->global_live_at_end);
229 IOR_HARD_REG_SET (tmp_bitmap, global_live_at_end);
230 }
7b82b5da 231
c0ee5d52 232 def_idx = xcalloc (du.high_bound, sizeof (int));
7b82b5da
SC		 233
234 /* Only consider registers in this extended block and in this class
235 that are defined more than once. Replace them if permissible. */
236 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
237 {
238 int avail_reg, ar_idx, def, def_cnt = 0, use_idx, call_idx;
239
240 if (!TEST_HARD_REG_BIT (regs_used, r)
241 || fixed_regs[r]
242 || r == FRAME_POINTER_REGNUM)
243 continue;
244
245 /* Find def_idx[N] where hbound of N is the number of
246 definitions of this register in this block. and def_idx
247 is the ordinal position of this insn in the block. */
1a43c33f
RK		 248 for (i = 0, def_idx[def_cnt] = 0; i < du.high_bound; i++)
249 if (TEST_BIT (du.defs[r], i)
250 && consider_def (VARRAY_RTX (uid_ruid, i), r, &du, i))
251 {
252 int first_use = 1;
253 def_idx[def_cnt] = i;
7b82b5da 254
1a43c33f
RK		 255 /* Only consider definitions that have a use. */
256 for (use_idx = i + 1; use_idx < du.high_bound; use_idx++)
257 {
258 if (TEST_BIT (du.uses[r], use_idx))
7b82b5da 259 {
1a43c33f
RK		 260 if (consider_use (VARRAY_RTX (uid_ruid, use_idx), r,
261 VARRAY_LONG (uid_rbid, i),
262 VARRAY_LONG (uid_rbid, use_idx)))
263 {
264 if (first_use)
265 {
266 first_use = 0;
267 def_cnt++;
268 }
269 }
270 else
271 {
272 /* Don't consider def if we don't want this
273 use. */
274 if (!first_use)
275 def_cnt--;
276
277 break;
278 }
7b82b5da 279 }
1a43c33f
RK		 280
281 if (TEST_BIT (du.defs[r], use_idx))
282 break;
283 }
284
285 /* Scan until the next def to avoid renaming
286 parameter registers. */
287 /* ??? consider using CALL_INSN_FUNCTION_USAGE */
288 for (call_idx = i; call_idx <= use_idx; call_idx++)
289 if (VARRAY_RTX (uid_ruid, call_idx)
290 && (GET_CODE (VARRAY_RTX (uid_ruid, call_idx))
291 == CALL_INSN))
292 SET_BIT (du.require_call_save_reg, i);
293 }
294
7b82b5da
SC		 295 if (def_cnt < 2)
296 continue;
297
298 /* We have more than one def so rename until we exhaust
299 renaming registers. */
300 /* ??? Should we continue renaming round robin when we exhaust
301 renaming registers? */
302 for (def = 0; def < def_cnt - 1; def++)
303 {
304 if (!TEST_BIT (defs_live_exit, def_idx[def])
305 && (GET_RTX_CLASS
306 (GET_CODE (VARRAY_RTX (uid_ruid,
307 def_idx[def]))) == 'i'))
308 {
1a43c33f
RK		 309 rtx reg_use
310 = regno_first_use_in
311 (r, PATTERN (VARRAY_RTX (uid_ruid, def_idx[def])));
7b82b5da
SC		 312
313 if (!reg_use)
314 break;
315#ifdef STACK_REGS
316 /* Don't bother with stacked float registers */
317 if (GET_MODE_CLASS (GET_MODE (reg_use)) == MODE_FLOAT)
318 break;
319#endif
c0ee5d52 320 rc = (int) DU_REG_CLASS (du.def_class,
1a43c33f 321 r, du.high_bound, def_idx[def]);
7b82b5da
SC		 322 COPY_HARD_REG_SET (avail_regs,
323 reg_class_contents[(enum reg_class) rc]);
324 AND_COMPL_HARD_REG_SET (avail_regs, tmp_bitmap);
325 AND_COMPL_HARD_REG_SET (avail_regs, renamed_regs);
326
327 /* No available registers in this class */
328 GO_IF_HARD_REG_EQUAL (avail_regs, null_bitmap,
329 no_available_regs);
1a43c33f 330
7b82b5da
SC		 331 for (ar_idx = 0; ar_idx < FIRST_PSEUDO_REGISTER
332 && TEST_HARD_REG_BIT (avail_regs, ar_idx); ar_idx++)
333 ;
1a43c33f 334
7b82b5da
SC		 335 if (ar_idx == FIRST_PSEUDO_REGISTER)
336 goto no_available_regs;
337
338 /* Only try register renaming if there is an available
339 register in this class. */
1a43c33f 340 for (ar_idx = 0; ar_idx < FIRST_PSEUDO_REGISTER; ar_idx++)
7b82b5da 341 {
030e2b51 342#ifdef REG_ALLOC_ORDER
7b82b5da 343 avail_reg = reg_alloc_order[ar_idx];
030e2b51
CP		 344#else
345 avail_reg = ar_idx;
346#endif
1a43c33f
RK		 347 if (consider_available (reg_use, avail_reg,
348 &avail_regs, rc, &du,
349 def_idx[def]))
50e60bc3 350 goto found_avail_reg;
7b82b5da
SC		 351 }
352
50e60bc3 353 if (rtl_dump_file)
7b82b5da 354 {
50e60bc3
ZW		 355 fprintf (rtl_dump_file, "Register %s in class %s",
356 reg_names[r], reg_class_names[rc]);
357 fprintf (rtl_dump_file, " in insn %d",
358 INSN_UID (VARRAY_RTX (uid_ruid,
359 def_idx[def])));
1a43c33f 360
50e60bc3
ZW		 361 if (TEST_BIT (du.require_call_save_reg,
362 def_idx[def]))
363 fprintf (rtl_dump_file, " crosses a call");
1a43c33f 364
50e60bc3 365 fprintf (rtl_dump_file, ". No available registers\n");
7b82b5da 366 }
50e60bc3 367 goto try_next_def;
7b82b5da 368
50e60bc3 369 found_avail_reg:
7b82b5da
SC		 370 SET_HARD_REG_BIT (renamed_regs, avail_reg);
371 CLEAR_HARD_REG_BIT (avail_regs, avail_reg);
372
373 /* Replace in destination. Replace in source for
374 remainder of block until new register is defined
375 again */
1a43c33f
RK		 376 replace_ok
377 = replace_reg_in_block (&du, &uid_ruid, def_idx[def],
378 reg_use, avail_reg);
379
7b82b5da
SC		 380 /* Replace failed, so restore previous register */
381 if (!replace_ok)
382 {
c0ee5d52 383 replace_reg_in_block (&du, &uid_ruid, def_idx[def],
1a43c33f
RK		 384 gen_rtx_REG (GET_MODE (reg_use),
385 avail_reg),
7b82b5da 386 REGNO (reg_use));
1a43c33f 387
7b82b5da 388 if (rtl_dump_file)
1a43c33f
RK		 389 {
390 fprintf (rtl_dump_file,
391 "Register %s in class %s Renaming as %s ",
392 reg_names[r], reg_class_names[rc],
393 reg_names[avail_reg]);
394 fprintf (rtl_dump_file,
395 "would not satisfy constraints\n");
396 }
7b82b5da 397 }
1a43c33f 398
7b82b5da 399 else if (rtl_dump_file)
1a43c33f
RK		 400 {
401 fprintf (rtl_dump_file,
402 "Register %s in class %s Renamed as %s ",
403 reg_names[r], reg_class_names[rc],
404 reg_names[avail_reg]);
405 fprintf (rtl_dump_file, "at insn %d\n",
406 INSN_UID (VARRAY_RTX (uid_ruid,
407 def_idx[def])));
408 }
7b82b5da 409 }
1a43c33f 410
7b82b5da
SC		 411 try_next_def:
412 continue;
413 }
1a43c33f 414
c0ee5d52 415 sbitmap_zero (du.defs[r]);
1a43c33f 416
7b82b5da
SC		 417 no_available_regs:
418 continue;
419 }
1a43c33f 420
7b82b5da 421 free (def_idx);
c0ee5d52
KG		 422 sbitmap_vector_free (du.defs);
423 sbitmap_vector_free (du.uses);
424 sbitmap_free (du.require_call_save_reg);
7b82b5da
SC		 425 sbitmap_free (defs_live_exit);
426 CLEAR_HARD_REG_SET (regs_used);
427 CLEAR_HARD_REG_SET (renamed_regs);
428
429 for (inum = 0; inum < (int) VARRAY_SIZE (uid_ruid); inum++)
430 VARRAY_RTX (uid_ruid, inum) = (rtx) 0;
431 }
432
c0ee5d52
KG		 433 sbitmap_vector_free (ebb.basic_block);
434 sbitmap_vector_free (ebb.exit);
7b82b5da
SC		 435}
436
437/* Build def/use chain DU for extended basic block EBB having root B.
438 Also determine which regs are used, REGS_USED, and which insns define
439 a live at exit def, DEFS_LIVE_EXIT */
440
441static void
442build_def_use (b, ebb, regs_used, du, defs_live_exit)
443 int b;
444 ext_basic_blocks *ebb;
445 HARD_REG_SET *regs_used;
446 def_uses *du;
447 sbitmap *defs_live_exit;
448{
449 rtx insn;
1a43c33f
RK		 450 int eb, inum;
451 unsigned int r;
7b82b5da
SC		 452
453 inum = 0;
454 for (eb = 0; eb < n_basic_blocks; eb++)
455 {
456 basic_block bb = BASIC_BLOCK (eb);
457
458 if (!TEST_BIT (ebb->basic_block[b], eb))
459 continue;
460
461 for (insn = bb->head;
462 insn != NEXT_INSN (bb->end);
463 inum++, insn = NEXT_INSN (insn))
464 {
465 struct resources insn_res;
466 struct resources insn_sets;
467
2c3c49de 468 if (! INSN_P (insn))
7b82b5da
SC		 469 continue;
470
471 CLEAR_RESOURCE (&insn_sets);
472 mark_set_resources (insn, &insn_sets, 0, MARK_DEST);
473
1a43c33f 474 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
7b82b5da
SC		 475 {
476 if (!TEST_HARD_REG_BIT (insn_sets.regs, r))
477 continue;
478
479 SET_HARD_REG_BIT (*regs_used, r);
480 if (REGNO_REG_SET_P (bb->global_live_at_end, r))
481 SET_BIT (*defs_live_exit, inum);
1a43c33f 482
7b82b5da
SC		 483 if (!insn_sets.memory)
484 SET_BIT (du->defs[r], inum);
1a43c33f
RK		 485
486 DU_REG_CLASS (du->def_class, r, du->high_bound, inum)
487 = get_reg_class (insn, regno_first_use_in (r, PATTERN (insn)),
488 DESTINATION, NO_REGS);
7b82b5da
SC		 489 }
490
491 CLEAR_RESOURCE (&insn_res);
492 mark_referenced_resources (insn, &insn_res, 0);
493
1a43c33f 494 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
7b82b5da
SC		 495 {
496 if (!TEST_HARD_REG_BIT (insn_res.regs, r))
497 continue;
498
499 SET_HARD_REG_BIT (*regs_used, r);
500 SET_BIT (du->uses[r], inum);
1a43c33f
RK		 501 DU_REG_CLASS (du->use_class, r, du->high_bound, inum)
502 = get_reg_class (insn, regno_use_in (r, PATTERN (insn)),
503 SOURCE, NO_REGS);
7b82b5da
SC		 504 }
505 }
506 }
1a43c33f 507
7b82b5da
SC		 508 free_resource_info ();
509}
510
511/* Return nonzero if regno AVAIL_REG can replace REG_DEF for insns in UID_RUID
512 starting at insn DEF in def/use chain DU. */
513
514static int
515replace_reg_in_block (du, uid_ruid, def, reg_def, avail_reg)
516 def_uses *du;
517 varray_type *uid_ruid;
518 int def;
519 rtx reg_def;
1a43c33f 520 unsigned int avail_reg;
7b82b5da
SC		 521{
522 int du_idx, status = 1;
5fa41e13 523 int last_replaced_insn;
1a43c33f 524 unsigned int r = REGNO (reg_def);
7b82b5da 525 rtx death_note;
5fa41e13 526 rtx reg_notes;
50e60bc3 527 rtx reg_use = 0;
7b82b5da
SC		 528 rtx new_reg = gen_rtx_REG (GET_MODE (reg_def), avail_reg);
529
1a43c33f
RK		 530 rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid, def)), reg_def, new_reg,
531 DESTINATION, VARRAY_RTX (*uid_ruid, def), &status);
7b82b5da 532
7b82b5da
SC		 533 if (!status)
534 return status;
535
5fa41e13
SC		 536 death_note = 0;
537 /* This typically happens if a constraint check failed and the register
538 changes are being reversed. */
539 for (reg_notes = REG_NOTES (VARRAY_RTX (*uid_ruid, def));
540 reg_notes; reg_notes = XEXP (reg_notes, 1))
541 {
542 if (REG_NOTE_KIND (reg_notes) == REG_DEAD
543 && REGNO (XEXP (reg_notes, 0)) == avail_reg)
544 death_note = reg_notes;
545 }
1a43c33f 546
7b82b5da 547 if (death_note)
5fa41e13
SC		 548 remove_note (VARRAY_RTX (*uid_ruid, def), death_note);
549
550 /* The old destination is now dead if it is also a source. */
551 if (regno_use_in (r, PATTERN (VARRAY_RTX (*uid_ruid, def))))
552 REG_NOTES (VARRAY_RTX (*uid_ruid, def))
553 = gen_rtx_EXPR_LIST (REG_DEAD, reg_def,
554 REG_NOTES (VARRAY_RTX (*uid_ruid,
555 def)));
556
557 last_replaced_insn = 0;
558
559 /* Now replace in the uses. */
7b82b5da
SC		 560 for (du_idx = def + 1; du_idx < du->high_bound; du_idx++)
561 {
2c3c49de 562 if (! INSN_P (VARRAY_RTX (*uid_ruid, du_idx)))
7b82b5da 563 continue;
7b82b5da 564
1a43c33f 565 reg_use = regno_use_in (r, PATTERN (VARRAY_RTX (*uid_ruid, du_idx)));
5fa41e13 566
7b82b5da
SC		 567 if (reg_use && TEST_BIT (du->uses[r], du_idx))
568 {
569 new_reg = gen_rtx_REG (GET_MODE (reg_use), avail_reg);
5fa41e13 570
7b82b5da
SC		 571 rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid, du_idx)), reg_use,
572 new_reg, SOURCE, VARRAY_RTX (*uid_ruid, du_idx),
573 &status);
574 death_note = find_reg_note (VARRAY_RTX (*uid_ruid, du_idx),
575 REG_DEAD, reg_use);
7b82b5da 576 if (death_note)
5fa41e13
SC		 577 {
578 REG_NOTES (VARRAY_RTX (*uid_ruid, du_idx))
579 = gen_rtx_EXPR_LIST (REG_DEAD, new_reg,
580 REG_NOTES (VARRAY_RTX (*uid_ruid,
581 du_idx)));
582 remove_note (VARRAY_RTX (*uid_ruid, du_idx),
583 find_reg_note (VARRAY_RTX (*uid_ruid, du_idx),
584 REG_DEAD, reg_use));
585 }
586 }
1a43c33f 587
5fa41e13
SC		 588 /* This insn may contain shared rtl replaced in the previous iteration.
589 Treat this equivalent to the rr_replace_reg case. */
590 if (TEST_BIT (du->uses[r], du_idx))
591 {
592 last_replaced_insn = du_idx;
593
7b82b5da
SC		 594 SET_BIT (du->uses[avail_reg], du_idx);
595 RESET_BIT (du->uses[r], du_idx);
596 if (!status)
597 return status;
598 }
1a43c33f 599
7b82b5da
SC		 600 if (TEST_BIT (du->defs[r], du_idx))
601 break;
602 }
1a43c33f 603
5fa41e13
SC		 604 /* Add REG_DEAD note for replaced register at last use. */
605
606 if (last_replaced_insn)
607 {
608 new_reg = regno_use_in (avail_reg,
609 PATTERN (VARRAY_RTX (*uid_ruid,
610 last_replaced_insn)));
611 if (new_reg
612 && ! find_reg_note (VARRAY_RTX (*uid_ruid, last_replaced_insn),
613 REG_DEAD, new_reg))
614 {
615 REG_NOTES (VARRAY_RTX (*uid_ruid, last_replaced_insn))
616 = gen_rtx_EXPR_LIST (REG_DEAD, new_reg,
617 REG_NOTES (VARRAY_RTX (*uid_ruid,
618 last_replaced_insn)));
619 remove_note (VARRAY_RTX (*uid_ruid, last_replaced_insn),
620 find_reg_note (VARRAY_RTX (*uid_ruid, last_replaced_insn),
621 REG_DEAD, reg_use));
622 }
623 }
624
7b82b5da
SC		 625 return status;
626}
627
628/* Try to replace REG_USE in X with REG_SUB if INSN has a REPLACE_TYPE.
629 STATUS is zero if the resulting pattern is not valid. */
630
631static rtx
632rr_replace_reg (x, reg_use, reg_sub, replace_type, insn, status)
633 rtx x;
634 rtx reg_use;
635 rtx reg_sub;
636 int replace_type;
637 rtx insn;
638 int *status;
639{
640 enum rtx_code code;
641 int i;
642 const char *fmt;
643 int n;
644
645 if (x == 0)
646 return x;
647
648 code = GET_CODE (x);
649 switch (code)
650 {
651 case REG:
652 if (REGNO (x) == REGNO (reg_use))
653 {
654 if (GET_MODE (x) == GET_MODE (reg_use))
655 return reg_sub;
656 else
5fa41e13 657 return gen_rtx_REG (GET_MODE (x), REGNO (reg_sub));
7b82b5da 658 }
1a43c33f 659
7b82b5da
SC		 660 return x;
661
662 case SET:
663 if (replace_type == DESTINATION)
664 SET_DEST (x) = rr_replace_reg (SET_DEST (x), reg_use, reg_sub,
665 replace_type, insn, status);
666 else if (replace_type == SOURCE)
667 {
5ac9118e 668 unsigned int dest_subregno = 0;
1a43c33f 669 int had_subreg = GET_CODE (SET_DEST (x)) == SUBREG;
7b82b5da 670
1a43c33f 671 if (had_subreg)
7b82b5da 672 dest_subregno = REGNO (XEXP (SET_DEST (x), 0));
7b82b5da
SC		 673
674 SET_SRC (x) = rr_replace_reg (SET_SRC (x), reg_use, reg_sub,
675 replace_type, insn, status);
1a43c33f 676
7b82b5da
SC		 677 /* If the replacement register is not part of the source
678 then it may be part of a source mem operand. */
679 if (GET_CODE (SET_DEST (x)) == MEM
680 || GET_CODE (SET_DEST (x)) == ZERO_EXTRACT
681 || GET_CODE (SET_DEST (x)) == SIGN_EXTRACT
682 || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
683 SET_DEST (x) = rr_replace_reg (SET_DEST (x), reg_use, reg_sub,
684 replace_type, insn, status);
1a43c33f
RK		 685 /* Shared rtl sanity check. */
686 if (had_subreg && dest_subregno != REGNO (XEXP (SET_DEST (x), 0)))
7b82b5da
SC		 687 {
688 *status = 0;
689 return x;
690 }
691 }
692
693 n = recog_memoized (insn);
694 if (n >= 0)
695 {
696 int id;
1a43c33f 697
7b82b5da
SC		 698 extract_insn (insn);
699
700 /* Any MATCH_DUP's which are REGs must still match */
701 for (id = insn_data[n].n_dups - 1; id >= 0; id--)
702 {
703 int opno = recog_data.dup_num[id];
1a43c33f 704
7b82b5da
SC		 705 if (GET_CODE (*recog_data.dup_loc[id]) == REG
706 && GET_CODE (*recog_data.operand_loc[opno]) == REG
1a43c33f
RK		 707 && (REGNO (*recog_data.dup_loc[id])
708 != REGNO (*recog_data.operand_loc[opno])))
7b82b5da
SC		 709 *status = 0;
710 }
711
712 if (!constrain_operands (1))
713 {
714 *status = 0;
715 validate_replace_rtx (reg_sub, reg_use, insn);
716 }
717 }
718 else
719 *status = 0;
720
721 return x;
722
723 default:
724 break;
725 }
726
727 fmt = GET_RTX_FORMAT (code);
728 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
729 {
730 if (fmt[i] == 'e')
731 XEXP (x, i) = rr_replace_reg (XEXP (x, i), reg_use, reg_sub,
732 replace_type, insn, status);
733 if (fmt[i] == 'E')
734 {
735 register int xv;
1a43c33f 736
7b82b5da
SC		 737 for (xv = 0; xv < XVECLEN (x, i); xv++)
738 {
739 XVECEXP (x, i, xv) = rr_replace_reg (XVECEXP (x, i, xv), reg_use,
740 reg_sub, replace_type, insn,
741 status);
742 n = recog_memoized (insn);
743 if (n >= 0)
744 {
745 extract_insn (insn);
746 if (!constrain_operands (1))
747 {
748 *status = 0;
749 validate_replace_rtx (reg_sub, reg_use, insn);
750 }
751 }
752 else
753 *status = 0;
754 }
755 }
756 }
1a43c33f 757
7b82b5da
SC		 758 return x;
759}
760
761/* Can REGNO in INSN be considered for renaming, given def INUM in d/u
762 chain DU? */
763
764static int
765consider_def (insn, regno, du, inum)
766 rtx insn;
767 int regno;
1a43c33f
RK		 768 def_uses *du ATTRIBUTE_UNUSED;
769 int inum ATTRIBUTE_UNUSED;
7b82b5da
SC		 770{
771 /* Don't rename windowed registers across a call */
772#ifdef INCOMING_REGNO
773 if (TEST_BIT (du->require_call_save_reg, inum)
774 && INCOMING_REGNO (regno) != regno)
775 return 0;
776#endif
777
778 /* Don't consider conditional moves. Predicate architectures may
779 use two complementary conditional moves and the regno shouldn't change */
780 if (condmove_p (insn))
781 return 0;
782
783 /* Don't rename call used registers across a call */
784 if (!(GET_CODE (insn) == CALL_INSN
785 && TEST_HARD_REG_BIT (call_used_reg_set, regno)))
786 return 1;
787 else
788 return 0;
789}
790
791/* Can the use of REGNO in INSN of block USE_BLOCK be considered for renaming
792 for a def in def_block? */
793
794static int
795consider_use (insn, regno, def_block, use_block)
796 rtx insn;
797 int regno;
798 int def_block;
799 int use_block;
800{
801 rtx reg_use;
802 edge e;
803 basic_block ub = BASIC_BLOCK (use_block);
804
2c3c49de 805 if (! INSN_P (insn))
7b82b5da
SC		 806 return 0;
807
808 /* If a use's basic block is different than the def's basic block,
809 then insure another predecessor does not also define this register */
810 if (def_block != use_block)
811 for (e = ub->pred; e; e = e->pred_next)
1a43c33f
RK		 812 if (e->src->index != def_block
813 && e->src->index != -1
814 && REGNO_REG_SET_P (BASIC_BLOCK (e->src->index)->global_live_at_end,
815 regno))
816 return 0;
7b82b5da
SC		 817
818 /* Don't consider conditional moves. Predicate architectures may
819 use two complementary conditional moves and the regno shouldn't change */
820
821 if (condmove_p (insn))
822 return 0;
823
824 reg_use = regno_first_use_in (regno, PATTERN (insn));
825 if (reg_use)
826 {
827 /* Don't consider multi-reg values. */
828 if (HARD_REGNO_NREGS (regno, GET_MODE (reg_use)) != 1
829 && GET_MODE (reg_use) != CCmode)
830 return 0;
831
832 /* Don't consider register if the only use is in a USE */
1a43c33f
RK		 833 return ! reg_mentioned_p (gen_rtx_USE (VOIDmode, reg_use),
834 PATTERN (insn));
7b82b5da
SC		 835 }
836 else
837 return 0;
838}
839
840/* Can REG_USE be replaced by regno AVAIL_REG if it is in AVAIL_REGS
841 and it is in regclass RC, given insn INUM of def/use chain DU? */
842
843static int
844consider_available (reg_use, avail_reg, avail_regs, rc, du, inum)
845 rtx reg_use;
846 int avail_reg;
847 HARD_REG_SET *avail_regs;
848 int rc;
849 def_uses *du;
850 int inum;
851{
852 if (!TEST_HARD_REG_BIT (*avail_regs, avail_reg))
853 return 0;
854
055be976
RH		 855 if (fixed_regs[avail_reg])
856 return 0;
857
7b82b5da
SC		 858#ifdef HARD_REGNO_RENAME_OK
859 if (!HARD_REGNO_RENAME_OK (REGNO (reg_use), avail_reg))
860 return 0;
861#endif
862
863 /* Don't consider windowed leaf registers which will be renamed by
864 leaf_renumber_regs */
865#ifdef LEAF_REG_REMAP
866 if (current_function_uses_only_leaf_regs)
867 if (LEAF_REG_REMAP (avail_reg) < 0)
868 return 0;
869#endif
870
871 /* A register is considered available if it is available at the beginning of
872 the basic block. We may want to refine this to when a register becomes
873 available within the block. We don't consider multi-reg values. */
874 /* ??? Consider a representation that would allow multi-reg support? */
875 if (!TEST_HARD_REG_BIT (reg_class_contents[(enum reg_class) rc], avail_reg)
876 || !HARD_REGNO_MODE_OK (avail_reg, GET_MODE (reg_use))
877 || (HARD_REGNO_NREGS (avail_reg, GET_MODE (reg_use)) != 1
878 && GET_MODE (reg_use) != CCmode)
879 || (call_fixed_regs[avail_reg]
880#ifdef HARD_REGNO_RENAME_OK
881 && !HARD_REGNO_RENAME_OK (REGNO (reg_use), avail_reg)
882#endif
883 )
884 || (TEST_BIT (du->require_call_save_reg, inum)
1a43c33f 885 && (call_used_regs[avail_reg] || call_used_regs[REGNO (reg_use)])))
7b82b5da
SC		 886 return 0;
887
888 /* If register is a callee-saved register it must be saved in the frame.
889 call saved registers can not be added to regs_ever_live after reload,
890 as it would invalidate most elimination offsets */
1a43c33f 891 return regs_ever_live[avail_reg] || call_used_regs[avail_reg];
7b82b5da
SC		 892}
893
894/* Return 1 if INSN is a conditional move */
895
896static int
897condmove_p (insn)
898 rtx insn;
899{
1a43c33f
RK		 900 return (GET_CODE (insn) == INSN
901 && GET_CODE (PATTERN (insn)) == SET
902 && GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE);
7b82b5da
SC		 903}
904
905/* Searches X for the first reference to REGNO, returning the rtx of the
906 reference found if any. Otherwise, returns NULL_RTX. */
907
908static rtx
909regno_first_use_in (regno, x)
1a43c33f 910 unsigned int regno;
7b82b5da
SC		 911 rtx x;
912{
913 register const char *fmt;
914 int i, j;
915 rtx tem;
916
917 if (GET_CODE (x) == REG && REGNO (x) == regno)
918 return x;
919
920 fmt = GET_RTX_FORMAT (GET_CODE (x));
921 for (i = 0; i <= GET_RTX_LENGTH (GET_CODE (x)) - 1; i++)
922 {
923 if (fmt[i] == 'e')
924 {
925 if ((tem = regno_first_use_in (regno, XEXP (x, i))))
926 return tem;
927 }
1a43c33f 928
7b82b5da
SC		 929 else if (fmt[i] == 'E')
930 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
931 if ((tem = regno_first_use_in (regno, XVECEXP (x, i, j))))
932 return tem;
933 }
934
1a43c33f 935 return 0;
7b82b5da
SC		 936}
937
938/* Dump def/use chain DU to RTL_DUMP_FILE, given insns in UID_RUID and
939 which regs are live at end, GLOBAL_LIVE_AT_END */
940
941static void
942dump_def_use_chain (global_live_at_end, du, uid_ruid)
943 HARD_REG_SET *global_live_at_end;
944 def_uses *du;
945 varray_type *uid_ruid;
946{
1a43c33f
RK		 947 unsigned int r;
948 int inum;
949
7b82b5da
SC		 950 for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
951 {
952 int set = 0;
1a43c33f
RK		 953
954 for (inum = 0; inum <= du->high_bound; inum++)
7b82b5da
SC		 955 {
956 rtx insn = VARRAY_RTX (*uid_ruid, inum);
957#if 0
958 if (!insn
959 || GET_RTX_CLASS (GET_CODE
960 (insn)) != 'i')
961 continue;
1a43c33f 962
7b82b5da
SC		 963 reg_use = regno_first_use_in (r, PATTERN (insn));
964 if (!reg_use)
965 continue;
966#endif
967 if (!set && (TEST_BIT (du->defs[r], inum)
968 || TEST_BIT (du->uses[r], inum)))
969 {
970 fprintf (rtl_dump_file, "Register %s: ", reg_names[r]);
971 if (fixed_regs[r])
972 fprintf (rtl_dump_file, "Fixed ");
973 else if (call_fixed_regs[r])
974 fprintf (rtl_dump_file, "Call Fixed ");
975 if (TEST_HARD_REG_BIT (*global_live_at_end, r))
976 fprintf (rtl_dump_file, "Live at Exit ");
977 set = 1;
978 }
1a43c33f 979
7b82b5da
SC		 980 if (TEST_BIT (du->defs[r], inum))
981 fprintf (rtl_dump_file, "=%d ", INSN_UID (insn));
982 if (TEST_BIT (du->uses[r], inum))
983 fprintf (rtl_dump_file, "%d ", INSN_UID (insn));
984 }
1a43c33f 985
7b82b5da
SC		 986 if (set)
987 fprintf (rtl_dump_file, "\n");
988 }
989}
990
991/* Dump info for extended basic block EBB having root EB */
992
993static void
994dump_ext_bb_info (eb, ebb)
995 int eb;
996 ext_basic_blocks *ebb;
997{
998 int b;
1a43c33f 999 int have_ebb = 0;
7b82b5da 1000
1a43c33f
RK		 1001 for (b = 0; b < n_basic_blocks; b++)
1002 {
1003 if (TEST_BIT (ebb->basic_block[eb], b))
1004 {
1005 if (!have_ebb)
1006 {
7b82b5da 1007#ifndef RENAME_EXTENDED_BLOCKS
1a43c33f 1008 fprintf (rtl_dump_file, "\nBasic block %d: ", b);
7b82b5da 1009#else
1a43c33f 1010 fprintf (rtl_dump_file, "\nExtended basic block %d: ", b);
7b82b5da 1011#endif
1a43c33f
RK		 1012 have_ebb = 1;
1013 }
1014 fprintf (rtl_dump_file, "%d ", b);
1015 }
1016
1017 if (TEST_BIT (ebb->exit[eb], b))
1018 fprintf (rtl_dump_file, "(exit) ");
1019 }
1020
1021 if (have_ebb)
1022 fprintf (rtl_dump_file, "\n");
7b82b5da
SC		 1023}
1024
1025/* Initialize EBB with extended basic block info if RENAME_EXTENDED_BLOCKS is
1026 defined. Otherwise just use basic blocks */
1027
1028static void
1029find_ext_basic_blocks (ebb)
1030 ext_basic_blocks *ebb;
1031{
1032 sbitmap bb_processed;
1033 int b;
1034
1035 bb_processed = sbitmap_alloc (n_basic_blocks);
1036 sbitmap_zero (bb_processed);
1037
1038#ifndef RENAME_EXTENDED_BLOCKS
1039 for (b = 0; b < n_basic_blocks; b++)
1040 {
1041 basic_block bb = BASIC_BLOCK (b);
1042 SET_BIT (ebb->basic_block[bb->index], bb->index);
1043 }
1044#else
1045 for (b = 0; b < n_basic_blocks; b++)
1046 {
1a43c33f 1047
7b82b5da
SC		 1048 basic_block bb = BASIC_BLOCK (b);
1049 if (!TEST_BIT (bb_processed, b))
1050 {
1051 find_one_ext_basic_block (bb->index, bb, &bb_processed, ebb);
1052 }
1053 }
1054#endif
1055 sbitmap_free (bb_processed);
1056}
1057
1058/* Find one extended basic block EBB having root ENTRY containing block
1059 BB */
1060
1061static void
1062find_one_ext_basic_block (entry, bb, bb_processed, ebb)
1063 int entry;
1064 basic_block bb;
1065 sbitmap *bb_processed;
1066 ext_basic_blocks *ebb;
1067{
1068 edge e;
1069
1070 if (!TEST_BIT (*bb_processed, bb->index))
1071 {
1072 SET_BIT (ebb->basic_block[entry], bb->index);
1073 SET_BIT (*bb_processed, bb->index);
1074 }
1075
1076 for (e = bb->succ; e; e = e->succ_next)
1077 if (!TEST_BIT (*bb_processed, e->dest->index))
1078 {
1079 if (!e->dest->pred->pred_next
1080 && (!TEST_BIT (*bb_processed, e->dest->index)))
1a43c33f 1081 find_one_ext_basic_block (entry, e->dest, bb_processed, ebb);
7b82b5da 1082 else
1a43c33f 1083 SET_BIT (ebb->exit[entry], bb->index);
7b82b5da
SC		 1084 }
1085}
1086
1087/* Find the register class for register REG_USE having TYPE (DESTINATION or
1088 SOURCE) in INSN. Use DEFAULT_CLASS if we cannot determine a class. */
1089
1090static enum reg_class
1091get_reg_class (insn, reg_use, type, default_class)
1092 rtx insn;
1093 rtx reg_use;
1094 int type;
1095 enum reg_class default_class;
1096{
1097 int alt, id = 0;
1098
1099 extract_insn (insn);
1100 constrain_operands (1);
1101 alt = which_alternative;
1102
1103 preprocess_constraints ();
1104
1105 if (type == DESTINATION)
1a43c33f
RK		 1106 {
1107 for (id = 0; id < recog_data.n_operands; id++)
7b82b5da
SC		 1108 if (rtx_equal_p (recog_data.operand[id], reg_use))
1109 break;
1a43c33f
RK		 1110 }
1111
7b82b5da
SC		 1112 else if (type == SOURCE)
1113 for (id = recog_data.n_operands - 1; id >= 0; id--)
1a43c33f
RK		 1114 if (rtx_equal_p (recog_data.operand[id], reg_use))
1115 break;
7b82b5da
SC		 1116
1117 if (id == -1 || id == recog_data.n_operands)
1118 return default_class;
1119
1120 return recog_op_alt[id][alt].class;
1121}
GNU Compiler Collection
This page took 0.319944 seconds and 5 git commands to generate.