|
0
|
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 }
|
