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