]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/ira-emit.c
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
* ira-int.h (struct ira_object): New.
[thirdparty/gcc.git] / gcc / ira-emit.c
CommitLineData
47dd2e78 1/* Integrated Register Allocator. Changing code and generating moves.
34408c5c 2 Copyright (C) 2006, 2007, 2008, 2009, 2010
47dd2e78 3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22
23#include "config.h"
24#include "system.h"
25#include "coretypes.h"
26#include "tm.h"
27#include "regs.h"
28#include "rtl.h"
29#include "tm_p.h"
30#include "target.h"
31#include "flags.h"
32#include "obstack.h"
33#include "bitmap.h"
34#include "hard-reg-set.h"
35#include "basic-block.h"
36#include "expr.h"
37#include "recog.h"
38#include "params.h"
39#include "timevar.h"
40#include "tree-pass.h"
41#include "output.h"
42#include "reload.h"
47dd2e78 43#include "df.h"
44#include "ira-int.h"
45
46
47typedef struct move *move_t;
48
49/* The structure represents an allocno move. Both allocnos have the
50 same origional regno but different allocation. */
51struct move
52{
53 /* The allocnos involved in the move. */
54 ira_allocno_t from, to;
55 /* The next move in the move sequence. */
56 move_t next;
57 /* Used for finding dependencies. */
58 bool visited_p;
59 /* The size of the following array. */
60 int deps_num;
61 /* Moves on which given move depends on. Dependency can be cyclic.
62 It means we need a temporary to generates the moves. Sequence
63 A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
64 B1 are assigned to reg R2 is an example of the cyclic
65 dependencies. */
66 move_t *deps;
67 /* First insn generated for the move. */
68 rtx insn;
69};
70
71/* Array of moves (indexed by BB index) which should be put at the
72 start/end of the corresponding basic blocks. */
73static move_t *at_bb_start, *at_bb_end;
74
75/* Max regno before renaming some pseudo-registers. For example, the
76 same pseudo-register can be renamed in a loop if its allocation is
77 different outside the loop. */
78static int max_regno_before_changing;
79
80/* Return new move of allocnos TO and FROM. */
81static move_t
82create_move (ira_allocno_t to, ira_allocno_t from)
83{
84 move_t move;
85
86 move = (move_t) ira_allocate (sizeof (struct move));
87 move->deps = NULL;
88 move->deps_num = 0;
89 move->to = to;
90 move->from = from;
91 move->next = NULL;
92 move->insn = NULL_RTX;
93 move->visited_p = false;
94 return move;
95}
96
97/* Free memory for MOVE and its dependencies. */
98static void
99free_move (move_t move)
100{
101 if (move->deps != NULL)
102 ira_free (move->deps);
103 ira_free (move);
104}
105
106/* Free memory for list of the moves given by its HEAD. */
107static void
108free_move_list (move_t head)
109{
110 move_t next;
48e1416a 111
47dd2e78 112 for (; head != NULL; head = next)
113 {
114 next = head->next;
115 free_move (head);
116 }
117}
118
119/* Return TRUE if the the move list LIST1 and LIST2 are equal (two
120 moves are equal if they involve the same allocnos). */
121static bool
122eq_move_lists_p (move_t list1, move_t list2)
123{
124 for (; list1 != NULL && list2 != NULL;
125 list1 = list1->next, list2 = list2->next)
126 if (list1->from != list2->from || list1->to != list2->to)
127 return false;
128 return list1 == list2;
129}
130
0c42b4f4 131/* Print move list LIST into file F. */
132static void
133print_move_list (FILE *f, move_t list)
134{
135 for (; list != NULL; list = list->next)
136 fprintf (f, " a%dr%d->a%dr%d",
137 ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from),
138 ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to));
139 fprintf (f, "\n");
140}
141
142extern void ira_debug_move_list (move_t list);
143
144/* Print move list LIST into stderr. */
145void
146ira_debug_move_list (move_t list)
147{
148 print_move_list (stderr, list);
149}
150
47dd2e78 151/* This recursive function changes pseudo-registers in *LOC if it is
152 necessary. The function returns TRUE if a change was done. */
153static bool
154change_regs (rtx *loc)
155{
156 int i, regno, result = false;
157 const char *fmt;
158 enum rtx_code code;
2fdae035 159 rtx reg;
47dd2e78 160
161 if (*loc == NULL_RTX)
162 return false;
163 code = GET_CODE (*loc);
164 if (code == REG)
165 {
166 regno = REGNO (*loc);
167 if (regno < FIRST_PSEUDO_REGISTER)
168 return false;
169 if (regno >= max_regno_before_changing)
170 /* It is a shared register which was changed already. */
171 return false;
172 if (ira_curr_regno_allocno_map[regno] == NULL)
173 return false;
2fdae035 174 reg = ALLOCNO_REG (ira_curr_regno_allocno_map[regno]);
175 if (reg == *loc)
176 return false;
177 *loc = reg;
47dd2e78 178 return true;
179 }
180
181 fmt = GET_RTX_FORMAT (code);
182 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
183 {
184 if (fmt[i] == 'e')
185 result = change_regs (&XEXP (*loc, i)) || result;
186 else if (fmt[i] == 'E')
187 {
188 int j;
189
190 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
191 result = change_regs (&XVECEXP (*loc, i, j)) || result;
192 }
193 }
194 return result;
195}
196
197/* Attach MOVE to the edge E. The move is attached to the head of the
198 list if HEAD_P is TRUE. */
199static void
200add_to_edge_list (edge e, move_t move, bool head_p)
201{
202 move_t last;
203
204 if (head_p || e->aux == NULL)
205 {
206 move->next = (move_t) e->aux;
207 e->aux = move;
208 }
209 else
210 {
211 for (last = (move_t) e->aux; last->next != NULL; last = last->next)
212 ;
213 last->next = move;
214 move->next = NULL;
215 }
216}
217
218/* Create and return new pseudo-register with the same attributes as
219 ORIGINAL_REG. */
220static rtx
221create_new_reg (rtx original_reg)
222{
223 rtx new_reg;
224
225 new_reg = gen_reg_rtx (GET_MODE (original_reg));
226 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
227 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
228 REG_POINTER (new_reg) = REG_POINTER (original_reg);
229 REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
230 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
231 fprintf (ira_dump_file, " Creating newreg=%i from oldreg=%i\n",
232 REGNO (new_reg), REGNO (original_reg));
233 return new_reg;
234}
235
236/* Return TRUE if loop given by SUBNODE inside the loop given by
237 NODE. */
238static bool
239subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
240{
241 for (; subnode != NULL; subnode = subnode->parent)
242 if (subnode == node)
243 return true;
244 return false;
245}
246
247/* Set up member `reg' to REG for allocnos which has the same regno as
248 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
249static void
250set_allocno_reg (ira_allocno_t allocno, rtx reg)
251{
252 int regno;
253 ira_allocno_t a;
254 ira_loop_tree_node_t node;
255
256 node = ALLOCNO_LOOP_TREE_NODE (allocno);
257 for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
258 a != NULL;
259 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
260 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
261 ALLOCNO_REG (a) = reg;
262 for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
263 ALLOCNO_REG (a) = reg;
264 regno = ALLOCNO_REGNO (allocno);
265 for (a = allocno;;)
266 {
267 if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
268 {
269 node = node->parent;
270 if (node == NULL)
271 break;
272 a = node->regno_allocno_map[regno];
273 }
274 if (a == NULL)
275 continue;
276 if (ALLOCNO_CHILD_RENAMED_P (a))
277 break;
278 ALLOCNO_CHILD_RENAMED_P (a) = true;
279 }
280}
281
0b1329df 282/* Return true if there is an entry to given loop not from its parent
283 (or grandparent) block. For example, it is possible for two
284 adjacent loops inside another loop. */
47dd2e78 285static bool
0b1329df 286entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
287{
288 ira_loop_tree_node_t bb_node, src_loop_node, parent;
289 edge e;
290 edge_iterator ei;
291
292 for (bb_node = loop_node->children; bb_node != NULL; bb_node = bb_node->next)
293 if (bb_node->bb != NULL)
294 {
295 FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
296 if (e->src != ENTRY_BLOCK_PTR
297 && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
298 {
299 for (parent = src_loop_node->parent;
300 parent != NULL;
301 parent = parent->parent)
302 if (parent == loop_node)
303 break;
304 if (parent != NULL)
305 /* That is an exit from a nested loop -- skip it. */
306 continue;
307 for (parent = loop_node->parent;
308 parent != NULL;
309 parent = parent->parent)
310 if (src_loop_node == parent)
311 break;
312 if (parent == NULL)
313 return true;
314 }
315 }
316 return false;
317}
318
319/* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
320static void
321setup_entered_from_non_parent_p (void)
322{
323 unsigned int i;
324 loop_p loop;
325
326 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
327 if (ira_loop_nodes[i].regno_allocno_map != NULL)
328 ira_loop_nodes[i].entered_from_non_parent_p
329 = entered_from_non_parent_p (&ira_loop_nodes[i]);
330}
331
332/* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
333 DEST_ALLOCNO (assigned to memory) can be removed beacuse it does
334 not change value of the destination. One possible reason for this
335 is the situation when SRC_ALLOCNO is not modified in the
336 corresponding loop. */
337static bool
338store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
47dd2e78 339{
340 int regno, orig_regno;
341 ira_allocno_t a;
342 ira_loop_tree_node_t node;
343
344 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
345 && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
346 orig_regno = ALLOCNO_REGNO (src_allocno);
347 regno = REGNO (ALLOCNO_REG (dest_allocno));
348 for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
349 node != NULL;
350 node = node->parent)
0b1329df 351 {
352 a = node->regno_allocno_map[orig_regno];
353 ira_assert (a != NULL);
354 if (REGNO (ALLOCNO_REG (a)) == (unsigned) regno)
355 /* We achieved the destination and everything is ok. */
356 return true;
357 else if (bitmap_bit_p (node->modified_regnos, orig_regno))
358 return false;
359 else if (node->entered_from_non_parent_p)
360 /* If there is a path from a destination loop block to the
361 source loop header containing basic blocks of non-parents
362 (grandparents) of the source loop, we should have checked
363 modifications of the pseudo on this path too to decide
364 about possibility to remove the store. It could be done by
365 solving a data-flow problem. Unfortunately such global
366 solution would complicate IR flattening. Therefore we just
367 prohibit removal of the store in such complicated case. */
368 return false;
369 }
370 gcc_unreachable ();
47dd2e78 371}
372
373/* Generate and attach moves to the edge E. This looks at the final
374 regnos of allocnos living on the edge with the same original regno
375 to figure out when moves should be generated. */
376static void
377generate_edge_moves (edge e)
378{
379 ira_loop_tree_node_t src_loop_node, dest_loop_node;
380 unsigned int regno;
381 bitmap_iterator bi;
382 ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
383 move_t move;
384
385 src_loop_node = IRA_BB_NODE (e->src)->parent;
386 dest_loop_node = IRA_BB_NODE (e->dest)->parent;
387 e->aux = NULL;
388 if (src_loop_node == dest_loop_node)
389 return;
390 src_map = src_loop_node->regno_allocno_map;
391 dest_map = dest_loop_node->regno_allocno_map;
2dd81ece 392 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e->dest),
47dd2e78 393 FIRST_PSEUDO_REGISTER, regno, bi)
2dd81ece 394 if (bitmap_bit_p (DF_LR_OUT (e->src), regno))
47dd2e78 395 {
396 src_allocno = src_map[regno];
397 dest_allocno = dest_map[regno];
398 if (REGNO (ALLOCNO_REG (src_allocno))
399 == REGNO (ALLOCNO_REG (dest_allocno)))
400 continue;
76b340db 401 /* Remove unnecessary stores at the region exit. We should do
402 this for readonly memory for sure and this is guaranteed by
403 that we never generate moves on region borders (see
404 checking ira_reg_equiv_invariant_p in function
405 change_loop). */
47dd2e78 406 if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
407 && ALLOCNO_HARD_REGNO (src_allocno) >= 0
0b1329df 408 && store_can_be_removed_p (src_allocno, dest_allocno))
47dd2e78 409 {
410 ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno) = dest_allocno;
411 ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno) = true;
412 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
413 fprintf (ira_dump_file, " Remove r%d:a%d->a%d(mem)\n",
414 regno, ALLOCNO_NUM (src_allocno),
415 ALLOCNO_NUM (dest_allocno));
416 continue;
417 }
418 move = create_move (dest_allocno, src_allocno);
419 add_to_edge_list (e, move, true);
420 }
421}
422
423/* Bitmap of allocnos local for the current loop. */
424static bitmap local_allocno_bitmap;
425
426/* This bitmap is used to find that we need to generate and to use a
427 new pseudo-register when processing allocnos with the same original
428 regno. */
429static bitmap used_regno_bitmap;
430
431/* This bitmap contains regnos of allocnos which were renamed locally
432 because the allocnos correspond to disjoint live ranges in loops
433 with a common parent. */
434static bitmap renamed_regno_bitmap;
435
436/* Change (if necessary) pseudo-registers inside loop given by loop
437 tree node NODE. */
438static void
439change_loop (ira_loop_tree_node_t node)
440{
441 bitmap_iterator bi;
442 unsigned int i;
443 int regno;
444 bool used_p;
445 ira_allocno_t allocno, parent_allocno, *map;
446 rtx insn, original_reg;
447 enum reg_class cover_class;
448 ira_loop_tree_node_t parent;
449
450 if (node != ira_loop_tree_root)
451 {
48e1416a 452
47dd2e78 453 if (node->bb != NULL)
454 {
455 FOR_BB_INSNS (node->bb, insn)
456 if (INSN_P (insn) && change_regs (&insn))
457 {
458 df_insn_rescan (insn);
459 df_notes_rescan (insn);
460 }
461 return;
462 }
48e1416a 463
47dd2e78 464 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
465 fprintf (ira_dump_file,
466 " Changing RTL for loop %d (header bb%d)\n",
467 node->loop->num, node->loop->header->index);
48e1416a 468
47dd2e78 469 parent = ira_curr_loop_tree_node->parent;
470 map = parent->regno_allocno_map;
471 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
472 0, i, bi)
473 {
474 allocno = ira_allocnos[i];
475 regno = ALLOCNO_REGNO (allocno);
476 cover_class = ALLOCNO_COVER_CLASS (allocno);
477 parent_allocno = map[regno];
478 ira_assert (regno < ira_reg_equiv_len);
479 /* We generate the same hard register move because the
480 reload pass can put an allocno into memory in this case
481 we will have live range splitting. If it does not happen
482 such the same hard register moves will be removed. The
483 worst case when the both allocnos are put into memory by
484 the reload is very rare. */
485 if (parent_allocno != NULL
486 && (ALLOCNO_HARD_REGNO (allocno)
487 == ALLOCNO_HARD_REGNO (parent_allocno))
488 && (ALLOCNO_HARD_REGNO (allocno) < 0
489 || (parent->reg_pressure[cover_class] + 1
490 <= ira_available_class_regs[cover_class])
491 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
492 [ALLOCNO_MODE (allocno)],
493 ALLOCNO_HARD_REGNO (allocno))
494 /* don't create copies because reload can spill an
495 allocno set by copy although the allocno will not
496 get memory slot. */
497 || ira_reg_equiv_invariant_p[regno]
498 || ira_reg_equiv_const[regno] != NULL_RTX))
499 continue;
500 original_reg = ALLOCNO_REG (allocno);
501 if (parent_allocno == NULL
502 || REGNO (ALLOCNO_REG (parent_allocno)) == REGNO (original_reg))
503 {
504 if (internal_flag_ira_verbose > 3 && ira_dump_file)
505 fprintf (ira_dump_file, " %i vs parent %i:",
506 ALLOCNO_HARD_REGNO (allocno),
507 ALLOCNO_HARD_REGNO (parent_allocno));
508 set_allocno_reg (allocno, create_new_reg (original_reg));
509 }
510 }
511 }
512 /* Rename locals: Local allocnos with same regno in different loops
513 might get the different hard register. So we need to change
514 ALLOCNO_REG. */
515 bitmap_and_compl (local_allocno_bitmap,
2bae4acc 516 ira_curr_loop_tree_node->all_allocnos,
47dd2e78 517 ira_curr_loop_tree_node->border_allocnos);
518 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
519 {
520 allocno = ira_allocnos[i];
521 regno = ALLOCNO_REGNO (allocno);
522 if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
523 continue;
524 used_p = bitmap_bit_p (used_regno_bitmap, regno);
525 bitmap_set_bit (used_regno_bitmap, regno);
526 ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
527 if (! used_p)
528 continue;
529 bitmap_set_bit (renamed_regno_bitmap, regno);
530 set_allocno_reg (allocno, create_new_reg (ALLOCNO_REG (allocno)));
531 }
532}
533
534/* Process to set up flag somewhere_renamed_p. */
535static void
536set_allocno_somewhere_renamed_p (void)
537{
538 unsigned int regno;
539 ira_allocno_t allocno;
540 ira_allocno_iterator ai;
541
542 FOR_EACH_ALLOCNO (allocno, ai)
543 {
544 regno = ALLOCNO_REGNO (allocno);
545 if (bitmap_bit_p (renamed_regno_bitmap, regno)
546 && REGNO (ALLOCNO_REG (allocno)) == regno)
547 ALLOCNO_SOMEWHERE_RENAMED_P (allocno) = true;
548 }
549}
550
551/* Return TRUE if move lists on all edges given in vector VEC are
552 equal. */
553static bool
554eq_edge_move_lists_p (VEC(edge,gc) *vec)
555{
556 move_t list;
557 int i;
558
559 list = (move_t) EDGE_I (vec, 0)->aux;
560 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
561 if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
562 return false;
563 return true;
564}
565
566/* Look at all entry edges (if START_P) or exit edges of basic block
567 BB and put move lists at the BB start or end if it is possible. In
568 other words, this decreases code duplication of allocno moves. */
569static void
570unify_moves (basic_block bb, bool start_p)
571{
572 int i;
573 edge e;
574 move_t list;
575 VEC(edge,gc) *vec;
576
577 vec = (start_p ? bb->preds : bb->succs);
578 if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
579 return;
580 e = EDGE_I (vec, 0);
581 list = (move_t) e->aux;
582 if (! start_p && control_flow_insn_p (BB_END (bb)))
583 return;
584 e->aux = NULL;
585 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
586 {
587 e = EDGE_I (vec, i);
588 free_move_list ((move_t) e->aux);
589 e->aux = NULL;
590 }
591 if (start_p)
592 at_bb_start[bb->index] = list;
593 else
594 at_bb_end[bb->index] = list;
595}
596
597/* Last move (in move sequence being processed) setting up the
598 corresponding hard register. */
599static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
600
601/* If the element value is equal to CURR_TICK then the corresponding
602 element in `hard_regno_last_set' is defined and correct. */
603static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
604
605/* Last move (in move sequence being processed) setting up the
606 corresponding allocno. */
607static move_t *allocno_last_set;
608
609/* If the element value is equal to CURR_TICK then the corresponding
610 element in . `allocno_last_set' is defined and correct. */
611static int *allocno_last_set_check;
612
613/* Definition of vector of moves. */
614DEF_VEC_P(move_t);
615DEF_VEC_ALLOC_P(move_t, heap);
616
617/* This vec contains moves sorted topologically (depth-first) on their
618 dependency graph. */
619static VEC(move_t,heap) *move_vec;
620
621/* The variable value is used to check correctness of values of
622 elements of arrays `hard_regno_last_set' and
623 `allocno_last_set_check'. */
624static int curr_tick;
625
626/* This recursive function traverses dependencies of MOVE and produces
627 topological sorting (in depth-first order). */
628static void
629traverse_moves (move_t move)
630{
631 int i;
632
633 if (move->visited_p)
634 return;
635 move->visited_p = true;
636 for (i = move->deps_num - 1; i >= 0; i--)
637 traverse_moves (move->deps[i]);
638 VEC_safe_push (move_t, heap, move_vec, move);
639}
640
641/* Remove unnecessary moves in the LIST, makes topological sorting,
642 and removes cycles on hard reg dependencies by introducing new
643 allocnos assigned to memory and additional moves. It returns the
644 result move list. */
645static move_t
646modify_move_list (move_t list)
647{
648 int i, n, nregs, hard_regno;
ae9587ed 649 ira_allocno_t to, from;
47dd2e78 650 move_t move, new_move, set_move, first, last;
651
652 if (list == NULL)
653 return NULL;
654 /* Creat move deps. */
655 curr_tick++;
656 for (move = list; move != NULL; move = move->next)
657 {
658 to = move->to;
659 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
660 continue;
661 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
662 for (i = 0; i < nregs; i++)
663 {
664 hard_regno_last_set[hard_regno + i] = move;
665 hard_regno_last_set_check[hard_regno + i] = curr_tick;
666 }
667 }
668 for (move = list; move != NULL; move = move->next)
669 {
670 from = move->from;
671 to = move->to;
672 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
673 {
674 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
675 for (n = i = 0; i < nregs; i++)
676 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
677 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
678 != ALLOCNO_REGNO (from)))
679 n++;
680 move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
681 for (n = i = 0; i < nregs; i++)
682 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
683 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
684 != ALLOCNO_REGNO (from)))
685 move->deps[n++] = hard_regno_last_set[hard_regno + i];
686 move->deps_num = n;
687 }
688 }
689 /* Toplogical sorting: */
690 VEC_truncate (move_t, move_vec, 0);
691 for (move = list; move != NULL; move = move->next)
692 traverse_moves (move);
693 last = NULL;
694 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
695 {
696 move = VEC_index (move_t, move_vec, i);
697 move->next = NULL;
698 if (last != NULL)
699 last->next = move;
700 last = move;
701 }
702 first = VEC_last (move_t, move_vec);
703 /* Removing cycles: */
704 curr_tick++;
705 VEC_truncate (move_t, move_vec, 0);
706 for (move = first; move != NULL; move = move->next)
707 {
708 from = move->from;
709 to = move->to;
710 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
711 {
712 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (from)];
713 for (i = 0; i < nregs; i++)
714 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
715 && ALLOCNO_HARD_REGNO
716 (hard_regno_last_set[hard_regno + i]->to) >= 0)
717 {
ae9587ed 718 ira_allocno_t new_allocno;
719 ira_object_t new_obj;
720
47dd2e78 721 set_move = hard_regno_last_set[hard_regno + i];
722 /* It does not matter what loop_tree_node (of TO or
723 FROM) to use for the new allocno because of
724 subsequent IRA internal representation
725 flattening. */
726 new_allocno
727 = ira_create_allocno (ALLOCNO_REGNO (set_move->to), false,
728 ALLOCNO_LOOP_TREE_NODE (set_move->to));
729 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
730 ira_set_allocno_cover_class
731 (new_allocno, ALLOCNO_COVER_CLASS (set_move->to));
ae9587ed 732 ira_create_allocno_object (new_allocno);
47dd2e78 733 ALLOCNO_ASSIGNED_P (new_allocno) = true;
734 ALLOCNO_HARD_REGNO (new_allocno) = -1;
735 ALLOCNO_REG (new_allocno)
736 = create_new_reg (ALLOCNO_REG (set_move->to));
ae9587ed 737
738 new_obj = ALLOCNO_OBJECT (new_allocno);
739
47dd2e78 740 /* Make it possibly conflicting with all earlier
741 created allocnos. Cases where temporary allocnos
742 created to remove the cycles are quite rare. */
ae9587ed 743 OBJECT_MIN (new_obj) = 0;
744 OBJECT_MAX (new_obj) = ira_objects_num - 1;
47dd2e78 745 new_move = create_move (set_move->to, new_allocno);
746 set_move->to = new_allocno;
747 VEC_safe_push (move_t, heap, move_vec, new_move);
748 ira_move_loops_num++;
749 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
750 fprintf (ira_dump_file,
751 " Creating temporary allocno a%dr%d\n",
752 ALLOCNO_NUM (new_allocno),
753 REGNO (ALLOCNO_REG (new_allocno)));
754 }
755 }
756 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
757 continue;
758 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (to)];
759 for (i = 0; i < nregs; i++)
760 {
761 hard_regno_last_set[hard_regno + i] = move;
762 hard_regno_last_set_check[hard_regno + i] = curr_tick;
763 }
764 }
765 for (i = (int) VEC_length (move_t, move_vec) - 1; i >= 0; i--)
766 {
767 move = VEC_index (move_t, move_vec, i);
768 move->next = NULL;
769 last->next = move;
770 last = move;
771 }
772 return first;
773}
774
775/* Generate RTX move insns from the move list LIST. This updates
776 allocation cost using move execution frequency FREQ. */
777static rtx
778emit_move_list (move_t list, int freq)
779{
780 int cost;
781 rtx result, insn;
782 enum machine_mode mode;
783 enum reg_class cover_class;
784
785 start_sequence ();
786 for (; list != NULL; list = list->next)
787 {
788 start_sequence ();
789 emit_move_insn (ALLOCNO_REG (list->to), ALLOCNO_REG (list->from));
790 list->insn = get_insns ();
791 end_sequence ();
792 /* The reload needs to have set up insn codes. If the reload
793 sets up insn codes by itself, it may fail because insns will
794 have hard registers instead of pseudos and there may be no
795 machine insn with given hard registers. */
796 for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
797 recog_memoized (insn);
798 emit_insn (list->insn);
799 mode = ALLOCNO_MODE (list->to);
800 cover_class = ALLOCNO_COVER_CLASS (list->to);
801 cost = 0;
802 if (ALLOCNO_HARD_REGNO (list->to) < 0)
803 {
804 if (ALLOCNO_HARD_REGNO (list->from) >= 0)
805 {
806 cost = ira_memory_move_cost[mode][cover_class][0] * freq;
807 ira_store_cost += cost;
808 }
809 }
810 else if (ALLOCNO_HARD_REGNO (list->from) < 0)
811 {
812 if (ALLOCNO_HARD_REGNO (list->to) >= 0)
813 {
814 cost = ira_memory_move_cost[mode][cover_class][0] * freq;
815 ira_load_cost += cost;
816 }
817 }
818 else
819 {
8f6c49f5 820 cost = (ira_get_register_move_cost (mode, cover_class, cover_class)
821 * freq);
47dd2e78 822 ira_shuffle_cost += cost;
823 }
824 ira_overall_cost += cost;
825 }
826 result = get_insns ();
827 end_sequence ();
828 return result;
829}
830
831/* Generate RTX move insns from move lists attached to basic blocks
832 and edges. */
833static void
834emit_moves (void)
835{
836 basic_block bb;
837 edge_iterator ei;
838 edge e;
839 rtx insns, tmp;
840
841 FOR_EACH_BB (bb)
842 {
843 if (at_bb_start[bb->index] != NULL)
844 {
845 at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
846 insns = emit_move_list (at_bb_start[bb->index],
847 REG_FREQ_FROM_BB (bb));
848 tmp = BB_HEAD (bb);
849 if (LABEL_P (tmp))
850 tmp = NEXT_INSN (tmp);
851 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
852 tmp = NEXT_INSN (tmp);
853 if (tmp == BB_HEAD (bb))
854 emit_insn_before (insns, tmp);
855 else if (tmp != NULL_RTX)
856 emit_insn_after (insns, PREV_INSN (tmp));
857 else
858 emit_insn_after (insns, get_last_insn ());
859 }
860
861 if (at_bb_end[bb->index] != NULL)
862 {
863 at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
864 insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
865 ira_assert (! control_flow_insn_p (BB_END (bb)));
866 emit_insn_after (insns, BB_END (bb));
867 }
868
869 FOR_EACH_EDGE (e, ei, bb->succs)
870 {
871 if (e->aux == NULL)
872 continue;
873 ira_assert ((e->flags & EDGE_ABNORMAL) == 0
874 || ! EDGE_CRITICAL_P (e));
875 e->aux = modify_move_list ((move_t) e->aux);
876 insert_insn_on_edge
877 (emit_move_list ((move_t) e->aux,
878 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
879 e);
880 if (e->src->next_bb != e->dest)
881 ira_additional_jumps_num++;
882 }
883 }
884}
885
886/* Update costs of A and corresponding allocnos on upper levels on the
887 loop tree from reading (if READ_P) or writing A on an execution
888 path with FREQ. */
889static void
890update_costs (ira_allocno_t a, bool read_p, int freq)
891{
892 ira_loop_tree_node_t parent;
893
894 for (;;)
895 {
896 ALLOCNO_NREFS (a)++;
897 ALLOCNO_FREQ (a) += freq;
898 ALLOCNO_MEMORY_COST (a)
899 += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)]
900 [read_p ? 1 : 0] * freq);
901 if (ALLOCNO_CAP (a) != NULL)
902 a = ALLOCNO_CAP (a);
903 else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
904 || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
905 break;
906 }
907}
908
909/* Process moves from LIST with execution FREQ to add ranges, copies,
910 and modify costs for allocnos involved in the moves. All regnos
911 living through the list is in LIVE_THROUGH, and the loop tree node
912 used to find corresponding allocnos is NODE. */
913static void
914add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
915 bitmap live_through, int freq)
916{
917 int start, n;
918 unsigned int regno;
919 move_t move;
ae9587ed 920 ira_allocno_t a;
47dd2e78 921 ira_copy_t cp;
fbff82f4 922 live_range_t r;
47dd2e78 923 bitmap_iterator bi;
924 HARD_REG_SET hard_regs_live;
925
926 if (list == NULL)
927 return;
928 n = 0;
929 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
930 n++;
931 REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
932 /* This is a trick to guarantee that new ranges is not merged with
933 the old ones. */
934 ira_max_point++;
935 start = ira_max_point;
936 for (move = list; move != NULL; move = move->next)
937 {
ae9587ed 938 ira_allocno_t from = move->from;
939 ira_allocno_t to = move->to;
940 ira_object_t from_obj = ALLOCNO_OBJECT (from);
941 ira_object_t to_obj = ALLOCNO_OBJECT (to);
942 if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
47dd2e78 943 {
944 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
945 fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
946 ALLOCNO_NUM (to), REGNO (ALLOCNO_REG (to)));
ae9587ed 947 ira_allocate_object_conflicts (to_obj, n);
47dd2e78 948 }
949 bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
950 bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
ae9587ed 951 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (from_obj), hard_regs_live);
952 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj), hard_regs_live);
953 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj), hard_regs_live);
954 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj), hard_regs_live);
47dd2e78 955 update_costs (from, true, freq);
956 update_costs (to, false, freq);
b7c06809 957 cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
47dd2e78 958 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
959 fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
960 cp->num, ALLOCNO_NUM (cp->first),
961 REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
962 REGNO (ALLOCNO_REG (cp->second)));
963 r = ALLOCNO_LIVE_RANGES (from);
964 if (r == NULL || r->finish >= 0)
965 {
966 ALLOCNO_LIVE_RANGES (from)
967 = ira_create_allocno_live_range (from, start, ira_max_point, r);
968 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
969 fprintf (ira_dump_file,
970 " Adding range [%d..%d] to allocno a%dr%d\n",
971 start, ira_max_point, ALLOCNO_NUM (from),
972 REGNO (ALLOCNO_REG (from)));
973 }
974 else
0c42b4f4 975 {
976 r->finish = ira_max_point;
977 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
978 fprintf (ira_dump_file,
979 " Adding range [%d..%d] to allocno a%dr%d\n",
980 r->start, ira_max_point, ALLOCNO_NUM (from),
981 REGNO (ALLOCNO_REG (from)));
982 }
47dd2e78 983 ira_max_point++;
984 ALLOCNO_LIVE_RANGES (to)
985 = ira_create_allocno_live_range (to, ira_max_point, -1,
986 ALLOCNO_LIVE_RANGES (to));
987 ira_max_point++;
988 }
989 for (move = list; move != NULL; move = move->next)
990 {
991 r = ALLOCNO_LIVE_RANGES (move->to);
992 if (r->finish < 0)
993 {
994 r->finish = ira_max_point - 1;
995 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
996 fprintf (ira_dump_file,
997 " Adding range [%d..%d] to allocno a%dr%d\n",
998 r->start, r->finish, ALLOCNO_NUM (move->to),
999 REGNO (ALLOCNO_REG (move->to)));
1000 }
1001 }
1002 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1003 {
ae9587ed 1004 ira_allocno_t to;
47dd2e78 1005 a = node->regno_allocno_map[regno];
0c42b4f4 1006 if ((to = ALLOCNO_MEM_OPTIMIZED_DEST (a)) != NULL)
1007 a = to;
1008 ALLOCNO_LIVE_RANGES (a)
1009 = ira_create_allocno_live_range (a, start, ira_max_point - 1,
1010 ALLOCNO_LIVE_RANGES (a));
1011 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1012 fprintf
1013 (ira_dump_file,
1014 " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1015 start, ira_max_point - 1,
1016 to != NULL ? "upper level" : "",
1017 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
47dd2e78 1018 }
1019}
1020
1021/* Process all move list to add ranges, conflicts, copies, and modify
1022 costs for allocnos involved in the moves. */
1023static void
1024add_ranges_and_copies (void)
1025{
1026 basic_block bb;
1027 edge_iterator ei;
1028 edge e;
1029 ira_loop_tree_node_t node;
1030 bitmap live_through;
1031
1032 live_through = ira_allocate_bitmap ();
1033 FOR_EACH_BB (bb)
1034 {
1035 /* It does not matter what loop_tree_node (of source or
1036 destination block) to use for searching allocnos by their
1037 regnos because of subsequent IR flattening. */
1038 node = IRA_BB_NODE (bb)->parent;
2dd81ece 1039 bitmap_copy (live_through, DF_LR_IN (bb));
47dd2e78 1040 add_range_and_copies_from_move_list
1041 (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
2dd81ece 1042 bitmap_copy (live_through, DF_LR_OUT (bb));
47dd2e78 1043 add_range_and_copies_from_move_list
1044 (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1045 FOR_EACH_EDGE (e, ei, bb->succs)
1046 {
2dd81ece 1047 bitmap_and (live_through, DF_LR_IN (e->dest), DF_LR_OUT (bb));
47dd2e78 1048 add_range_and_copies_from_move_list
1049 ((move_t) e->aux, node, live_through,
1050 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1051 }
1052 }
1053 ira_free_bitmap (live_through);
1054}
1055
1056/* The entry function changes code and generates shuffling allocnos on
1057 region borders for the regional (LOOPS_P is TRUE in this case)
1058 register allocation. */
1059void
1060ira_emit (bool loops_p)
1061{
1062 basic_block bb;
14792f4e 1063 rtx insn;
47dd2e78 1064 edge_iterator ei;
1065 edge e;
1066 ira_allocno_t a;
1067 ira_allocno_iterator ai;
1068
1069 FOR_EACH_ALLOCNO (a, ai)
1070 ALLOCNO_REG (a) = regno_reg_rtx[ALLOCNO_REGNO (a)];
1071 if (! loops_p)
1072 return;
1073 at_bb_start = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1074 memset (at_bb_start, 0, sizeof (move_t) * last_basic_block);
1075 at_bb_end = (move_t *) ira_allocate (sizeof (move_t) * last_basic_block);
1076 memset (at_bb_end, 0, sizeof (move_t) * last_basic_block);
1077 local_allocno_bitmap = ira_allocate_bitmap ();
1078 used_regno_bitmap = ira_allocate_bitmap ();
1079 renamed_regno_bitmap = ira_allocate_bitmap ();
1080 max_regno_before_changing = max_reg_num ();
1081 ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1082 set_allocno_somewhere_renamed_p ();
1083 ira_free_bitmap (used_regno_bitmap);
1084 ira_free_bitmap (renamed_regno_bitmap);
1085 ira_free_bitmap (local_allocno_bitmap);
0b1329df 1086 setup_entered_from_non_parent_p ();
47dd2e78 1087 FOR_EACH_BB (bb)
1088 {
1089 at_bb_start[bb->index] = NULL;
1090 at_bb_end[bb->index] = NULL;
1091 FOR_EACH_EDGE (e, ei, bb->succs)
1092 if (e->dest != EXIT_BLOCK_PTR)
1093 generate_edge_moves (e);
1094 }
1095 allocno_last_set
1096 = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1097 allocno_last_set_check
1098 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1099 memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1100 memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1101 curr_tick = 0;
1102 FOR_EACH_BB (bb)
1103 unify_moves (bb, true);
1104 FOR_EACH_BB (bb)
1105 unify_moves (bb, false);
1106 move_vec = VEC_alloc (move_t, heap, ira_allocnos_num);
1107 emit_moves ();
1108 add_ranges_and_copies ();
1109 /* Clean up: */
1110 FOR_EACH_BB (bb)
1111 {
1112 free_move_list (at_bb_start[bb->index]);
1113 free_move_list (at_bb_end[bb->index]);
1114 FOR_EACH_EDGE (e, ei, bb->succs)
1115 {
1116 free_move_list ((move_t) e->aux);
1117 e->aux = NULL;
1118 }
1119 }
1120 VEC_free (move_t, heap, move_vec);
1121 ira_free (allocno_last_set_check);
1122 ira_free (allocno_last_set);
1123 commit_edge_insertions ();
14792f4e 1124 /* Fix insn codes. It is necessary to do it before reload because
1125 reload assumes initial insn codes defined. The insn codes can be
1126 invalidated by CFG infrastructure for example in jump
1127 redirection. */
1128 FOR_EACH_BB (bb)
1129 FOR_BB_INSNS_REVERSE (bb, insn)
1130 if (INSN_P (insn))
1131 recog_memoized (insn);
47dd2e78 1132 ira_free (at_bb_end);
1133 ira_free (at_bb_start);
1134}
Mirror of https://gcc.gnu.org/git/gcc.git