Mercurial > hg > CbC > CbC_gcc

comparison gcc/ira-emit.c @ 0:a06113de4d67

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