|
0
|
1 /* Perform branch target register load optimizations.
|
|
|
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
|
|
|
3 Free Software Foundation, Inc.
|
|
|
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 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "coretypes.h"
|
|
|
24 #include "tm.h"
|
|
|
25 #include "rtl.h"
|
|
|
26 #include "hard-reg-set.h"
|
|
|
27 #include "regs.h"
|
|
|
28 #include "fibheap.h"
|
|
|
29 #include "output.h"
|
|
|
30 #include "target.h"
|
|
|
31 #include "expr.h"
|
|
|
32 #include "flags.h"
|
|
|
33 #include "insn-attr.h"
|
|
|
34 #include "function.h"
|
|
|
35 #include "except.h"
|
|
|
36 #include "tm_p.h"
|
|
|
37 #include "toplev.h"
|
|
|
38 #include "tree-pass.h"
|
|
|
39 #include "recog.h"
|
|
|
40 #include "df.h"
|
|
|
41
|
|
|
42 /* Target register optimizations - these are performed after reload. */
|
|
|
43
|
|
|
44 typedef struct btr_def_group_s
|
|
|
45 {
|
|
|
46 struct btr_def_group_s *next;
|
|
|
47 rtx src;
|
|
|
48 struct btr_def_s *members;
|
|
|
49 } *btr_def_group;
|
|
|
50
|
|
|
51 typedef struct btr_user_s
|
|
|
52 {
|
|
|
53 struct btr_user_s *next;
|
|
|
54 basic_block bb;
|
|
|
55 int luid;
|
|
|
56 rtx insn;
|
|
|
57 /* If INSN has a single use of a single branch register, then
|
|
|
58 USE points to it within INSN. If there is more than
|
|
|
59 one branch register use, or the use is in some way ambiguous,
|
|
|
60 then USE is NULL. */
|
|
|
61 rtx use;
|
|
|
62 int n_reaching_defs;
|
|
|
63 int first_reaching_def;
|
|
|
64 char other_use_this_block;
|
|
|
65 } *btr_user;
|
|
|
66
|
|
|
67 /* btr_def structs appear on three lists:
|
|
|
68 1. A list of all btr_def structures (head is
|
|
|
69 ALL_BTR_DEFS, linked by the NEXT field).
|
|
|
70 2. A list of branch reg definitions per basic block (head is
|
|
|
71 BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).
|
|
|
72 3. A list of all branch reg definitions belonging to the same
|
|
|
73 group (head is in a BTR_DEF_GROUP struct, linked by
|
|
|
74 NEXT_THIS_GROUP field). */
|
|
|
75
|
|
|
76 typedef struct btr_def_s
|
|
|
77 {
|
|
|
78 struct btr_def_s *next_this_bb;
|
|
|
79 struct btr_def_s *next_this_group;
|
|
|
80 basic_block bb;
|
|
|
81 int luid;
|
|
|
82 rtx insn;
|
|
|
83 int btr;
|
|
|
84 int cost;
|
|
|
85 /* For a branch register setting insn that has a constant
|
|
|
86 source (i.e. a label), group links together all the
|
|
|
87 insns with the same source. For other branch register
|
|
|
88 setting insns, group is NULL. */
|
|
|
89 btr_def_group group;
|
|
|
90 btr_user uses;
|
|
|
91 /* If this def has a reaching use which is not a simple use
|
|
|
92 in a branch instruction, then has_ambiguous_use will be true,
|
|
|
93 and we will not attempt to migrate this definition. */
|
|
|
94 char has_ambiguous_use;
|
|
|
95 /* live_range is an approximation to the true live range for this
|
|
|
96 def/use web, because it records the set of blocks that contain
|
|
|
97 the live range. There could be other live ranges for the same
|
|
|
98 branch register in that set of blocks, either in the block
|
|
|
99 containing the def (before the def), or in a block containing
|
|
|
100 a use (after the use). If there are such other live ranges, then
|
|
|
101 other_btr_uses_before_def or other_btr_uses_after_use must be set true
|
|
|
102 as appropriate. */
|
|
|
103 char other_btr_uses_before_def;
|
|
|
104 char other_btr_uses_after_use;
|
|
|
105 /* We set own_end when we have moved a definition into a dominator.
|
|
|
106 Thus, when a later combination removes this definition again, we know
|
|
|
107 to clear out trs_live_at_end again. */
|
|
|
108 char own_end;
|
|
|
109 bitmap live_range;
|
|
|
110 } *btr_def;
|
|
|
111
|
|
|
112 static int issue_rate;
|
|
|
113
|
|
|
114 static int basic_block_freq (const_basic_block);
|
|
|
115 static int insn_sets_btr_p (const_rtx, int, int *);
|
|
|
116 static rtx *find_btr_use (rtx);
|
|
|
117 static int btr_referenced_p (rtx, rtx *);
|
|
|
118 static int find_btr_reference (rtx *, void *);
|
|
|
119 static void find_btr_def_group (btr_def_group *, btr_def);
|
|
|
120 static btr_def add_btr_def (fibheap_t, basic_block, int, rtx,
|
|
|
121 unsigned int, int, btr_def_group *);
|
|
|
122 static btr_user new_btr_user (basic_block, int, rtx);
|
|
|
123 static void dump_hard_reg_set (HARD_REG_SET);
|
|
|
124 static void dump_btrs_live (int);
|
|
|
125 static void note_other_use_this_block (unsigned int, btr_user);
|
|
|
126 static void compute_defs_uses_and_gen (fibheap_t, btr_def *,btr_user *,
|
|
|
127 sbitmap *, sbitmap *, HARD_REG_SET *);
|
|
|
128 static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *);
|
|
|
129 static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int);
|
|
|
130 static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int);
|
|
|
131 static void build_btr_def_use_webs (fibheap_t);
|
|
|
132 static int block_at_edge_of_live_range_p (int, btr_def);
|
|
|
133 static void clear_btr_from_live_range (btr_def def);
|
|
|
134 static void add_btr_to_live_range (btr_def, int);
|
|
|
135 static void augment_live_range (bitmap, HARD_REG_SET *, basic_block,
|
|
|
136 basic_block, int);
|
|
|
137 static int choose_btr (HARD_REG_SET);
|
|
|
138 static void combine_btr_defs (btr_def, HARD_REG_SET *);
|
|
|
139 static void btr_def_live_range (btr_def, HARD_REG_SET *);
|
|
|
140 static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *);
|
|
|
141 static int migrate_btr_def (btr_def, int);
|
|
|
142 static void migrate_btr_defs (enum reg_class, int);
|
|
|
143 static int can_move_up (const_basic_block, const_rtx, int);
|
|
|
144 static void note_btr_set (rtx, const_rtx, void *);
|
|
|
145
|
|
|
146 /* The following code performs code motion of target load instructions
|
|
|
147 (instructions that set branch target registers), to move them
|
|
|
148 forward away from the branch instructions and out of loops (or,
|
|
|
149 more generally, from a more frequently executed place to a less
|
|
|
150 frequently executed place).
|
|
|
151 Moving target load instructions further in front of the branch
|
|
|
152 instruction that uses the target register value means that the hardware
|
|
|
153 has a better chance of preloading the instructions at the branch
|
|
|
154 target by the time the branch is reached. This avoids bubbles
|
|
|
155 when a taken branch needs to flush out the pipeline.
|
|
|
156 Moving target load instructions out of loops means they are executed
|
|
|
157 less frequently. */
|
|
|
158
|
|
|
159 /* An obstack to hold the def-use web data structures built up for
|
|
|
160 migrating branch target load instructions. */
|
|
|
161 static struct obstack migrate_btrl_obstack;
|
|
|
162
|
|
|
163 /* Array indexed by basic block number, giving the set of registers
|
|
|
164 live in that block. */
|
|
|
165 static HARD_REG_SET *btrs_live;
|
|
|
166
|
|
|
167 /* Array indexed by basic block number, giving the set of registers live at
|
|
|
168 the end of that block, including any uses by a final jump insn, if any. */
|
|
|
169 static HARD_REG_SET *btrs_live_at_end;
|
|
|
170
|
|
|
171 /* Set of all target registers that we are willing to allocate. */
|
|
|
172 static HARD_REG_SET all_btrs;
|
|
|
173
|
|
|
174 /* Provide lower and upper bounds for target register numbers, so that
|
|
|
175 we don't need to search through all the hard registers all the time. */
|
|
|
176 static int first_btr, last_btr;
|
|
|
177
|
|
|
178
|
|
|
179
|
|
|
180 /* Return an estimate of the frequency of execution of block bb. */
|
|
|
181 static int
|
|
|
182 basic_block_freq (const_basic_block bb)
|
|
|
183 {
|
|
|
184 return bb->frequency;
|
|
|
185 }
|
|
|
186
|
|
|
187 static rtx *btr_reference_found;
|
|
|
188
|
|
|
189 /* A subroutine of btr_referenced_p, called through for_each_rtx.
|
|
|
190 PREG is a pointer to an rtx that is to be excluded from the
|
|
|
191 traversal. If we find a reference to a target register anywhere
|
|
|
192 else, return 1, and put a pointer to it into btr_reference_found. */
|
|
|
193 static int
|
|
|
194 find_btr_reference (rtx *px, void *preg)
|
|
|
195 {
|
|
|
196 rtx x;
|
|
|
197
|
|
|
198 if (px == preg)
|
|
|
199 return -1;
|
|
|
200 x = *px;
|
|
|
201 if (!REG_P (x))
|
|
|
202 return 0;
|
|
|
203 if (overlaps_hard_reg_set_p (all_btrs, GET_MODE (x), REGNO (x)))
|
|
|
204 {
|
|
|
205 btr_reference_found = px;
|
|
|
206 return 1;
|
|
|
207 }
|
|
|
208 return -1;
|
|
|
209 }
|
|
|
210
|
|
|
211 /* Return nonzero if X references (sets or reads) any branch target register.
|
|
|
212 If EXCLUDEP is set, disregard any references within the rtx pointed to
|
|
|
213 by it. If returning nonzero, also set btr_reference_found as above. */
|
|
|
214 static int
|
|
|
215 btr_referenced_p (rtx x, rtx *excludep)
|
|
|
216 {
|
|
|
217 return for_each_rtx (&x, find_btr_reference, excludep);
|
|
|
218 }
|
|
|
219
|
|
|
220 /* Return true if insn is an instruction that sets a target register.
|
|
|
221 if CHECK_CONST is true, only return true if the source is constant.
|
|
|
222 If such a set is found and REGNO is nonzero, assign the register number
|
|
|
223 of the destination register to *REGNO. */
|
|
|
224 static int
|
|
|
225 insn_sets_btr_p (const_rtx insn, int check_const, int *regno)
|
|
|
226 {
|
|
|
227 rtx set;
|
|
|
228
|
|
|
229 if (NONJUMP_INSN_P (insn)
|
|
|
230 && (set = single_set (insn)))
|
|
|
231 {
|
|
|
232 rtx dest = SET_DEST (set);
|
|
|
233 rtx src = SET_SRC (set);
|
|
|
234
|
|
|
235 if (GET_CODE (dest) == SUBREG)
|
|
|
236 dest = XEXP (dest, 0);
|
|
|
237
|
|
|
238 if (REG_P (dest)
|
|
|
239 && TEST_HARD_REG_BIT (all_btrs, REGNO (dest)))
|
|
|
240 {
|
|
|
241 gcc_assert (!btr_referenced_p (src, NULL));
|
|
|
242
|
|
|
243 if (!check_const || CONSTANT_P (src))
|
|
|
244 {
|
|
|
245 if (regno)
|
|
|
246 *regno = REGNO (dest);
|
|
|
247 return 1;
|
|
|
248 }
|
|
|
249 }
|
|
|
250 }
|
|
|
251 return 0;
|
|
|
252 }
|
|
|
253
|
|
|
254 /* Find and return a use of a target register within an instruction INSN. */
|
|
|
255 static rtx *
|
|
|
256 find_btr_use (rtx insn)
|
|
|
257 {
|
|
|
258 return btr_referenced_p (insn, NULL) ? btr_reference_found : NULL;
|
|
|
259 }
|
|
|
260
|
|
|
261 /* Find the group that the target register definition DEF belongs
|
|
|
262 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such
|
|
|
263 group exists, create one. Add def to the group. */
|
|
|
264 static void
|
|
|
265 find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def)
|
|
|
266 {
|
|
|
267 if (insn_sets_btr_p (def->insn, 1, NULL))
|
|
|
268 {
|
|
|
269 btr_def_group this_group;
|
|
|
270 rtx def_src = SET_SRC (single_set (def->insn));
|
|
|
271
|
|
|
272 /* ?? This linear search is an efficiency concern, particularly
|
|
|
273 as the search will almost always fail to find a match. */
|
|
|
274 for (this_group = *all_btr_def_groups;
|
|
|
275 this_group != NULL;
|
|
|
276 this_group = this_group->next)
|
|
|
277 if (rtx_equal_p (def_src, this_group->src))
|
|
|
278 break;
|
|
|
279
|
|
|
280 if (!this_group)
|
|
|
281 {
|
|
|
282 this_group = XOBNEW (&migrate_btrl_obstack, struct btr_def_group_s);
|
|
|
283 this_group->src = def_src;
|
|
|
284 this_group->members = NULL;
|
|
|
285 this_group->next = *all_btr_def_groups;
|
|
|
286 *all_btr_def_groups = this_group;
|
|
|
287 }
|
|
|
288 def->group = this_group;
|
|
|
289 def->next_this_group = this_group->members;
|
|
|
290 this_group->members = def;
|
|
|
291 }
|
|
|
292 else
|
|
|
293 def->group = NULL;
|
|
|
294 }
|
|
|
295
|
|
|
296 /* Create a new target register definition structure, for a definition in
|
|
|
297 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
|
|
|
298 the new definition. */
|
|
|
299 static btr_def
|
|
|
300 add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn,
|
|
|
301 unsigned int dest_reg, int other_btr_uses_before_def,
|
|
|
302 btr_def_group *all_btr_def_groups)
|
|
|
303 {
|
|
|
304 btr_def this_def = XOBNEW (&migrate_btrl_obstack, struct btr_def_s);
|
|
|
305 this_def->bb = bb;
|
|
|
306 this_def->luid = insn_luid;
|
|
|
307 this_def->insn = insn;
|
|
|
308 this_def->btr = dest_reg;
|
|
|
309 this_def->cost = basic_block_freq (bb);
|
|
|
310 this_def->has_ambiguous_use = 0;
|
|
|
311 this_def->other_btr_uses_before_def = other_btr_uses_before_def;
|
|
|
312 this_def->other_btr_uses_after_use = 0;
|
|
|
313 this_def->next_this_bb = NULL;
|
|
|
314 this_def->next_this_group = NULL;
|
|
|
315 this_def->uses = NULL;
|
|
|
316 this_def->live_range = NULL;
|
|
|
317 find_btr_def_group (all_btr_def_groups, this_def);
|
|
|
318
|
|
|
319 fibheap_insert (all_btr_defs, -this_def->cost, this_def);
|
|
|
320
|
|
|
321 if (dump_file)
|
|
|
322 fprintf (dump_file,
|
|
|
323 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
|
|
|
324 dest_reg, bb->index, INSN_UID (insn),
|
|
|
325 (this_def->group ? "" : ":not const"), this_def->cost);
|
|
|
326
|
|
|
327 return this_def;
|
|
|
328 }
|
|
|
329
|
|
|
330 /* Create a new target register user structure, for a use in block BB,
|
|
|
331 instruction INSN. Return the new user. */
|
|
|
332 static btr_user
|
|
|
333 new_btr_user (basic_block bb, int insn_luid, rtx insn)
|
|
|
334 {
|
|
|
335 /* This instruction reads target registers. We need
|
|
|
336 to decide whether we can replace all target register
|
|
|
337 uses easily.
|
|
|
338 */
|
|
|
339 rtx *usep = find_btr_use (PATTERN (insn));
|
|
|
340 rtx use;
|
|
|
341 btr_user user = NULL;
|
|
|
342
|
|
|
343 if (usep)
|
|
|
344 {
|
|
|
345 int unambiguous_single_use;
|
|
|
346
|
|
|
347 /* We want to ensure that USE is the only use of a target
|
|
|
348 register in INSN, so that we know that to rewrite INSN to use
|
|
|
349 a different target register, all we have to do is replace USE. */
|
|
|
350 unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep);
|
|
|
351 if (!unambiguous_single_use)
|
|
|
352 usep = NULL;
|
|
|
353 }
|
|
|
354 use = usep ? *usep : NULL_RTX;
|
|
|
355 user = XOBNEW (&migrate_btrl_obstack, struct btr_user_s);
|
|
|
356 user->bb = bb;
|
|
|
357 user->luid = insn_luid;
|
|
|
358 user->insn = insn;
|
|
|
359 user->use = use;
|
|
|
360 user->other_use_this_block = 0;
|
|
|
361 user->next = NULL;
|
|
|
362 user->n_reaching_defs = 0;
|
|
|
363 user->first_reaching_def = -1;
|
|
|
364
|
|
|
365 if (dump_file)
|
|
|
366 {
|
|
|
367 fprintf (dump_file, "Uses target reg: { bb %d, insn %d }",
|
|
|
368 bb->index, INSN_UID (insn));
|
|
|
369
|
|
|
370 if (user->use)
|
|
|
371 fprintf (dump_file, ": unambiguous use of reg %d\n",
|
|
|
372 REGNO (user->use));
|
|
|
373 }
|
|
|
374
|
|
|
375 return user;
|
|
|
376 }
|
|
|
377
|
|
|
378 /* Write the contents of S to the dump file. */
|
|
|
379 static void
|
|
|
380 dump_hard_reg_set (HARD_REG_SET s)
|
|
|
381 {
|
|
|
382 int reg;
|
|
|
383 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
|
|
|
384 if (TEST_HARD_REG_BIT (s, reg))
|
|
|
385 fprintf (dump_file, " %d", reg);
|
|
|
386 }
|
|
|
387
|
|
|
388 /* Write the set of target regs live in block BB to the dump file. */
|
|
|
389 static void
|
|
|
390 dump_btrs_live (int bb)
|
|
|
391 {
|
|
|
392 fprintf (dump_file, "BB%d live:", bb);
|
|
|
393 dump_hard_reg_set (btrs_live[bb]);
|
|
|
394 fprintf (dump_file, "\n");
|
|
|
395 }
|
|
|
396
|
|
|
397 /* REGNO is the number of a branch target register that is being used or
|
|
|
398 set. USERS_THIS_BB is a list of preceding branch target register users;
|
|
|
399 If any of them use the same register, set their other_use_this_block
|
|
|
400 flag. */
|
|
|
401 static void
|
|
|
402 note_other_use_this_block (unsigned int regno, btr_user users_this_bb)
|
|
|
403 {
|
|
|
404 btr_user user;
|
|
|
405
|
|
|
406 for (user = users_this_bb; user != NULL; user = user->next)
|
|
|
407 if (user->use && REGNO (user->use) == regno)
|
|
|
408 user->other_use_this_block = 1;
|
|
|
409 }
|
|
|
410
|
|
|
411 typedef struct {
|
|
|
412 btr_user users_this_bb;
|
|
|
413 HARD_REG_SET btrs_written_in_block;
|
|
|
414 HARD_REG_SET btrs_live_in_block;
|
|
|
415 sbitmap bb_gen;
|
|
|
416 sbitmap *btr_defset;
|
|
|
417 } defs_uses_info;
|
|
|
418
|
|
|
419 /* Called via note_stores or directly to register stores into /
|
|
|
420 clobbers of a branch target register DEST that are not recognized as
|
|
|
421 straightforward definitions. DATA points to information about the
|
|
|
422 current basic block that needs updating. */
|
|
|
423 static void
|
|
|
424 note_btr_set (rtx dest, const_rtx set ATTRIBUTE_UNUSED, void *data)
|
|
|
425 {
|
|
|
426 defs_uses_info *info = (defs_uses_info *) data;
|
|
|
427 int regno, end_regno;
|
|
|
428
|
|
|
429 if (!REG_P (dest))
|
|
|
430 return;
|
|
|
431 regno = REGNO (dest);
|
|
|
432 end_regno = END_HARD_REGNO (dest);
|
|
|
433 for (; regno < end_regno; regno++)
|
|
|
434 if (TEST_HARD_REG_BIT (all_btrs, regno))
|
|
|
435 {
|
|
|
436 note_other_use_this_block (regno, info->users_this_bb);
|
|
|
437 SET_HARD_REG_BIT (info->btrs_written_in_block, regno);
|
|
|
438 SET_HARD_REG_BIT (info->btrs_live_in_block, regno);
|
|
|
439 sbitmap_difference (info->bb_gen, info->bb_gen,
|
|
|
440 info->btr_defset[regno - first_btr]);
|
|
|
441 }
|
|
|
442 }
|
|
|
443
|
|
|
444 static void
|
|
|
445 compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array,
|
|
|
446 btr_user *use_array, sbitmap *btr_defset,
|
|
|
447 sbitmap *bb_gen, HARD_REG_SET *btrs_written)
|
|
|
448 {
|
|
|
449 /* Scan the code building up the set of all defs and all uses.
|
|
|
450 For each target register, build the set of defs of that register.
|
|
|
451 For each block, calculate the set of target registers
|
|
|
452 written in that block.
|
|
|
453 Also calculate the set of btrs ever live in that block.
|
|
|
454 */
|
|
|
455 int i;
|
|
|
456 int insn_luid = 0;
|
|
|
457 btr_def_group all_btr_def_groups = NULL;
|
|
|
458 defs_uses_info info;
|
|
|
459
|
|
|
460 sbitmap_vector_zero (bb_gen, n_basic_blocks);
|
|
|
461 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
|
|
462 {
|
|
|
463 basic_block bb = BASIC_BLOCK (i);
|
|
|
464 int reg;
|
|
|
465 btr_def defs_this_bb = NULL;
|
|
|
466 rtx insn;
|
|
|
467 rtx last;
|
|
|
468 int can_throw = 0;
|
|
|
469
|
|
|
470 info.users_this_bb = NULL;
|
|
|
471 info.bb_gen = bb_gen[i];
|
|
|
472 info.btr_defset = btr_defset;
|
|
|
473
|
|
|
474 CLEAR_HARD_REG_SET (info.btrs_live_in_block);
|
|
|
475 CLEAR_HARD_REG_SET (info.btrs_written_in_block);
|
|
|
476 for (reg = first_btr; reg <= last_btr; reg++)
|
|
|
477 if (TEST_HARD_REG_BIT (all_btrs, reg)
|
|
|
478 && REGNO_REG_SET_P (df_get_live_in (bb), reg))
|
|
|
479 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
|
|
|
480
|
|
|
481 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
|
|
|
482 insn != last;
|
|
|
483 insn = NEXT_INSN (insn), insn_luid++)
|
|
|
484 {
|
|
|
485 if (INSN_P (insn))
|
|
|
486 {
|
|
|
487 int regno;
|
|
|
488 int insn_uid = INSN_UID (insn);
|
|
|
489
|
|
|
490 if (insn_sets_btr_p (insn, 0, ®no))
|
|
|
491 {
|
|
|
492 btr_def def = add_btr_def (
|
|
|
493 all_btr_defs, bb, insn_luid, insn, regno,
|
|
|
494 TEST_HARD_REG_BIT (info.btrs_live_in_block, regno),
|
|
|
495 &all_btr_def_groups);
|
|
|
496
|
|
|
497 def_array[insn_uid] = def;
|
|
|
498 SET_HARD_REG_BIT (info.btrs_written_in_block, regno);
|
|
|
499 SET_HARD_REG_BIT (info.btrs_live_in_block, regno);
|
|
|
500 sbitmap_difference (bb_gen[i], bb_gen[i],
|
|
|
501 btr_defset[regno - first_btr]);
|
|
|
502 SET_BIT (bb_gen[i], insn_uid);
|
|
|
503 def->next_this_bb = defs_this_bb;
|
|
|
504 defs_this_bb = def;
|
|
|
505 SET_BIT (btr_defset[regno - first_btr], insn_uid);
|
|
|
506 note_other_use_this_block (regno, info.users_this_bb);
|
|
|
507 }
|
|
|
508 /* Check for the blockage emitted by expand_nl_goto_receiver. */
|
|
|
509 else if (cfun->has_nonlocal_label
|
|
|
510 && GET_CODE (PATTERN (insn)) == UNSPEC_VOLATILE)
|
|
|
511 {
|
|
|
512 btr_user user;
|
|
|
513
|
|
|
514 /* Do the equivalent of calling note_other_use_this_block
|
|
|
515 for every target register. */
|
|
|
516 for (user = info.users_this_bb; user != NULL;
|
|
|
517 user = user->next)
|
|
|
518 if (user->use)
|
|
|
519 user->other_use_this_block = 1;
|
|
|
520 IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs);
|
|
|
521 IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs);
|
|
|
522 sbitmap_zero (info.bb_gen);
|
|
|
523 }
|
|
|
524 else
|
|
|
525 {
|
|
|
526 if (btr_referenced_p (PATTERN (insn), NULL))
|
|
|
527 {
|
|
|
528 btr_user user = new_btr_user (bb, insn_luid, insn);
|
|
|
529
|
|
|
530 use_array[insn_uid] = user;
|
|
|
531 if (user->use)
|
|
|
532 SET_HARD_REG_BIT (info.btrs_live_in_block,
|
|
|
533 REGNO (user->use));
|
|
|
534 else
|
|
|
535 {
|
|
|
536 int reg;
|
|
|
537 for (reg = first_btr; reg <= last_btr; reg++)
|
|
|
538 if (TEST_HARD_REG_BIT (all_btrs, reg)
|
|
|
539 && refers_to_regno_p (reg, reg + 1, user->insn,
|
|
|
540 NULL))
|
|
|
541 {
|
|
|
542 note_other_use_this_block (reg,
|
|
|
543 info.users_this_bb);
|
|
|
544 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
|
|
|
545 }
|
|
|
546 note_stores (PATTERN (insn), note_btr_set, &info);
|
|
|
547 }
|
|
|
548 user->next = info.users_this_bb;
|
|
|
549 info.users_this_bb = user;
|
|
|
550 }
|
|
|
551 if (CALL_P (insn))
|
|
|
552 {
|
|
|
553 HARD_REG_SET *clobbered = &call_used_reg_set;
|
|
|
554 HARD_REG_SET call_saved;
|
|
|
555 rtx pat = PATTERN (insn);
|
|
|
556 int i;
|
|
|
557
|
|
|
558 /* Check for sibcall. */
|
|
|
559 if (GET_CODE (pat) == PARALLEL)
|
|
|
560 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
|
|
|
561 if (GET_CODE (XVECEXP (pat, 0, i)) == RETURN)
|
|
|
562 {
|
|
|
563 COMPL_HARD_REG_SET (call_saved,
|
|
|
564 call_used_reg_set);
|
|
|
565 clobbered = &call_saved;
|
|
|
566 }
|
|
|
567
|
|
|
568 for (regno = first_btr; regno <= last_btr; regno++)
|
|
|
569 if (TEST_HARD_REG_BIT (*clobbered, regno))
|
|
|
570 note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info);
|
|
|
571 }
|
|
|
572 }
|
|
|
573 }
|
|
|
574 }
|
|
|
575
|
|
|
576 COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block);
|
|
|
577 COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block);
|
|
|
578
|
|
|
579 REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], df_get_live_out (bb));
|
|
|
580 /* If this block ends in a jump insn, add any uses or even clobbers
|
|
|
581 of branch target registers that it might have. */
|
|
|
582 for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); )
|
|
|
583 insn = PREV_INSN (insn);
|
|
|
584 /* ??? for the fall-through edge, it would make sense to insert the
|
|
|
585 btr set on the edge, but that would require to split the block
|
|
|
586 early on so that we can distinguish between dominance from the fall
|
|
|
587 through edge - which can use the call-clobbered registers - from
|
|
|
588 dominance by the throw edge. */
|
|
|
589 if (can_throw_internal (insn))
|
|
|
590 {
|
|
|
591 HARD_REG_SET tmp;
|
|
|
592
|
|
|
593 COPY_HARD_REG_SET (tmp, call_used_reg_set);
|
|
|
594 AND_HARD_REG_SET (tmp, all_btrs);
|
|
|
595 IOR_HARD_REG_SET (btrs_live_at_end[i], tmp);
|
|
|
596 can_throw = 1;
|
|
|
597 }
|
|
|
598 if (can_throw || JUMP_P (insn))
|
|
|
599 {
|
|
|
600 int regno;
|
|
|
601
|
|
|
602 for (regno = first_btr; regno <= last_btr; regno++)
|
|
|
603 if (refers_to_regno_p (regno, regno+1, insn, NULL))
|
|
|
604 SET_HARD_REG_BIT (btrs_live_at_end[i], regno);
|
|
|
605 }
|
|
|
606
|
|
|
607 if (dump_file)
|
|
|
608 dump_btrs_live(i);
|
|
|
609 }
|
|
|
610 }
|
|
|
611
|
|
|
612 static void
|
|
|
613 compute_kill (sbitmap *bb_kill, sbitmap *btr_defset,
|
|
|
614 HARD_REG_SET *btrs_written)
|
|
|
615 {
|
|
|
616 int i;
|
|
|
617 int regno;
|
|
|
618
|
|
|
619 /* For each basic block, form the set BB_KILL - the set
|
|
|
620 of definitions that the block kills. */
|
|
|
621 sbitmap_vector_zero (bb_kill, n_basic_blocks);
|
|
|
622 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
|
|
623 {
|
|
|
624 for (regno = first_btr; regno <= last_btr; regno++)
|
|
|
625 if (TEST_HARD_REG_BIT (all_btrs, regno)
|
|
|
626 && TEST_HARD_REG_BIT (btrs_written[i], regno))
|
|
|
627 sbitmap_a_or_b (bb_kill[i], bb_kill[i],
|
|
|
628 btr_defset[regno - first_btr]);
|
|
|
629 }
|
|
|
630 }
|
|
|
631
|
|
|
632 static void
|
|
|
633 compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid)
|
|
|
634 {
|
|
|
635 /* Perform iterative dataflow:
|
|
|
636 Initially, for all blocks, BB_OUT = BB_GEN.
|
|
|
637 For each block,
|
|
|
638 BB_IN = union over predecessors of BB_OUT(pred)
|
|
|
639 BB_OUT = (BB_IN - BB_KILL) + BB_GEN
|
|
|
640 Iterate until the bb_out sets stop growing. */
|
|
|
641 int i;
|
|
|
642 int changed;
|
|
|
643 sbitmap bb_in = sbitmap_alloc (max_uid);
|
|
|
644
|
|
|
645 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
|
|
646 sbitmap_copy (bb_out[i], bb_gen[i]);
|
|
|
647
|
|
|
648 changed = 1;
|
|
|
649 while (changed)
|
|
|
650 {
|
|
|
651 changed = 0;
|
|
|
652 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
|
|
653 {
|
|
|
654 sbitmap_union_of_preds (bb_in, bb_out, i);
|
|
|
655 changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i],
|
|
|
656 bb_in, bb_kill[i]);
|
|
|
657 }
|
|
|
658 }
|
|
|
659 sbitmap_free (bb_in);
|
|
|
660 }
|
|
|
661
|
|
|
662 static void
|
|
|
663 link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out,
|
|
|
664 sbitmap *btr_defset, int max_uid)
|
|
|
665 {
|
|
|
666 int i;
|
|
|
667 sbitmap reaching_defs = sbitmap_alloc (max_uid);
|
|
|
668
|
|
|
669 /* Link uses to the uses lists of all of their reaching defs.
|
|
|
670 Count up the number of reaching defs of each use. */
|
|
|
671 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
|
|
672 {
|
|
|
673 basic_block bb = BASIC_BLOCK (i);
|
|
|
674 rtx insn;
|
|
|
675 rtx last;
|
|
|
676
|
|
|
677 sbitmap_union_of_preds (reaching_defs, bb_out, i);
|
|
|
678 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
|
|
|
679 insn != last;
|
|
|
680 insn = NEXT_INSN (insn))
|
|
|
681 {
|
|
|
682 if (INSN_P (insn))
|
|
|
683 {
|
|
|
684 int insn_uid = INSN_UID (insn);
|
|
|
685
|
|
|
686 btr_def def = def_array[insn_uid];
|
|
|
687 btr_user user = use_array[insn_uid];
|
|
|
688 if (def != NULL)
|
|
|
689 {
|
|
|
690 /* Remove all reaching defs of regno except
|
|
|
691 for this one. */
|
|
|
692 sbitmap_difference (reaching_defs, reaching_defs,
|
|
|
693 btr_defset[def->btr - first_btr]);
|
|
|
694 SET_BIT(reaching_defs, insn_uid);
|
|
|
695 }
|
|
|
696
|
|
|
697 if (user != NULL)
|
|
|
698 {
|
|
|
699 /* Find all the reaching defs for this use. */
|
|
|
700 sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid);
|
|
|
701 unsigned int uid = 0;
|
|
|
702 sbitmap_iterator sbi;
|
|
|
703
|
|
|
704 if (user->use)
|
|
|
705 sbitmap_a_and_b (
|
|
|
706 reaching_defs_of_reg,
|
|
|
707 reaching_defs,
|
|
|
708 btr_defset[REGNO (user->use) - first_btr]);
|
|
|
709 else
|
|
|
710 {
|
|
|
711 int reg;
|
|
|
712
|
|
|
713 sbitmap_zero (reaching_defs_of_reg);
|
|
|
714 for (reg = first_btr; reg <= last_btr; reg++)
|
|
|
715 if (TEST_HARD_REG_BIT (all_btrs, reg)
|
|
|
716 && refers_to_regno_p (reg, reg + 1, user->insn,
|
|
|
717 NULL))
|
|
|
718 sbitmap_a_or_b_and_c (reaching_defs_of_reg,
|
|
|
719 reaching_defs_of_reg,
|
|
|
720 reaching_defs,
|
|
|
721 btr_defset[reg - first_btr]);
|
|
|
722 }
|
|
|
723 EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid, sbi)
|
|
|
724 {
|
|
|
725 btr_def def = def_array[uid];
|
|
|
726
|
|
|
727 /* We now know that def reaches user. */
|
|
|
728
|
|
|
729 if (dump_file)
|
|
|
730 fprintf (dump_file,
|
|
|
731 "Def in insn %d reaches use in insn %d\n",
|
|
|
732 uid, insn_uid);
|
|
|
733
|
|
|
734 user->n_reaching_defs++;
|
|
|
735 if (!user->use)
|
|
|
736 def->has_ambiguous_use = 1;
|
|
|
737 if (user->first_reaching_def != -1)
|
|
|
738 { /* There is more than one reaching def. This is
|
|
|
739 a rare case, so just give up on this def/use
|
|
|
740 web when it occurs. */
|
|
|
741 def->has_ambiguous_use = 1;
|
|
|
742 def_array[user->first_reaching_def]
|
|
|
743 ->has_ambiguous_use = 1;
|
|
|
744 if (dump_file)
|
|
|
745 fprintf (dump_file,
|
|
|
746 "(use %d has multiple reaching defs)\n",
|
|
|
747 insn_uid);
|
|
|
748 }
|
|
|
749 else
|
|
|
750 user->first_reaching_def = uid;
|
|
|
751 if (user->other_use_this_block)
|
|
|
752 def->other_btr_uses_after_use = 1;
|
|
|
753 user->next = def->uses;
|
|
|
754 def->uses = user;
|
|
|
755 }
|
|
|
756 sbitmap_free (reaching_defs_of_reg);
|
|
|
757 }
|
|
|
758
|
|
|
759 if (CALL_P (insn))
|
|
|
760 {
|
|
|
761 int regno;
|
|
|
762
|
|
|
763 for (regno = first_btr; regno <= last_btr; regno++)
|
|
|
764 if (TEST_HARD_REG_BIT (all_btrs, regno)
|
|
|
765 && TEST_HARD_REG_BIT (call_used_reg_set, regno))
|
|
|
766 sbitmap_difference (reaching_defs, reaching_defs,
|
|
|
767 btr_defset[regno - first_btr]);
|
|
|
768 }
|
|
|
769 }
|
|
|
770 }
|
|
|
771 }
|
|
|
772 sbitmap_free (reaching_defs);
|
|
|
773 }
|
|
|
774
|
|
|
775 static void
|
|
|
776 build_btr_def_use_webs (fibheap_t all_btr_defs)
|
|
|
777 {
|
|
|
778 const int max_uid = get_max_uid ();
|
|
|
779 btr_def *def_array = XCNEWVEC (btr_def, max_uid);
|
|
|
780 btr_user *use_array = XCNEWVEC (btr_user, max_uid);
|
|
|
781 sbitmap *btr_defset = sbitmap_vector_alloc (
|
|
|
782 (last_btr - first_btr) + 1, max_uid);
|
|
|
783 sbitmap *bb_gen = sbitmap_vector_alloc (n_basic_blocks, max_uid);
|
|
|
784 HARD_REG_SET *btrs_written = XCNEWVEC (HARD_REG_SET, n_basic_blocks);
|
|
|
785 sbitmap *bb_kill;
|
|
|
786 sbitmap *bb_out;
|
|
|
787
|
|
|
788 sbitmap_vector_zero (btr_defset, (last_btr - first_btr) + 1);
|
|
|
789
|
|
|
790 compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset,
|
|
|
791 bb_gen, btrs_written);
|
|
|
792
|
|
|
793 bb_kill = sbitmap_vector_alloc (n_basic_blocks, max_uid);
|
|
|
794 compute_kill (bb_kill, btr_defset, btrs_written);
|
|
|
795 free (btrs_written);
|
|
|
796
|
|
|
797 bb_out = sbitmap_vector_alloc (n_basic_blocks, max_uid);
|
|
|
798 compute_out (bb_out, bb_gen, bb_kill, max_uid);
|
|
|
799
|
|
|
800 sbitmap_vector_free (bb_gen);
|
|
|
801 sbitmap_vector_free (bb_kill);
|
|
|
802
|
|
|
803 link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid);
|
|
|
804
|
|
|
805 sbitmap_vector_free (bb_out);
|
|
|
806 sbitmap_vector_free (btr_defset);
|
|
|
807 free (use_array);
|
|
|
808 free (def_array);
|
|
|
809 }
|
|
|
810
|
|
|
811 /* Return true if basic block BB contains the start or end of the
|
|
|
812 live range of the definition DEF, AND there are other live
|
|
|
813 ranges of the same target register that include BB. */
|
|
|
814 static int
|
|
|
815 block_at_edge_of_live_range_p (int bb, btr_def def)
|
|
|
816 {
|
|
|
817 if (def->other_btr_uses_before_def && BASIC_BLOCK (bb) == def->bb)
|
|
|
818 return 1;
|
|
|
819 else if (def->other_btr_uses_after_use)
|
|
|
820 {
|
|
|
821 btr_user user;
|
|
|
822 for (user = def->uses; user != NULL; user = user->next)
|
|
|
823 if (BASIC_BLOCK (bb) == user->bb)
|
|
|
824 return 1;
|
|
|
825 }
|
|
|
826 return 0;
|
|
|
827 }
|
|
|
828
|
|
|
829 /* We are removing the def/use web DEF. The target register
|
|
|
830 used in this web is therefore no longer live in the live range
|
|
|
831 of this web, so remove it from the live set of all basic blocks
|
|
|
832 in the live range of the web.
|
|
|
833 Blocks at the boundary of the live range may contain other live
|
|
|
834 ranges for the same target register, so we have to be careful
|
|
|
835 to remove the target register from the live set of these blocks
|
|
|
836 only if they do not contain other live ranges for the same register. */
|
|
|
837 static void
|
|
|
838 clear_btr_from_live_range (btr_def def)
|
|
|
839 {
|
|
|
840 unsigned bb;
|
|
|
841 bitmap_iterator bi;
|
|
|
842
|
|
|
843 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
|
|
|
844 {
|
|
|
845 if ((!def->other_btr_uses_before_def
|
|
|
846 && !def->other_btr_uses_after_use)
|
|
|
847 || !block_at_edge_of_live_range_p (bb, def))
|
|
|
848 {
|
|
|
849 CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr);
|
|
|
850 CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
|
|
|
851 if (dump_file)
|
|
|
852 dump_btrs_live (bb);
|
|
|
853 }
|
|
|
854 }
|
|
|
855 if (def->own_end)
|
|
|
856 CLEAR_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
|
|
|
857 }
|
|
|
858
|
|
|
859
|
|
|
860 /* We are adding the def/use web DEF. Add the target register used
|
|
|
861 in this web to the live set of all of the basic blocks that contain
|
|
|
862 the live range of the web.
|
|
|
863 If OWN_END is set, also show that the register is live from our
|
|
|
864 definitions at the end of the basic block where it is defined. */
|
|
|
865 static void
|
|
|
866 add_btr_to_live_range (btr_def def, int own_end)
|
|
|
867 {
|
|
|
868 unsigned bb;
|
|
|
869 bitmap_iterator bi;
|
|
|
870
|
|
|
871 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
|
|
|
872 {
|
|
|
873 SET_HARD_REG_BIT (btrs_live[bb], def->btr);
|
|
|
874 SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
|
|
|
875 if (dump_file)
|
|
|
876 dump_btrs_live (bb);
|
|
|
877 }
|
|
|
878 if (own_end)
|
|
|
879 {
|
|
|
880 SET_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
|
|
|
881 def->own_end = 1;
|
|
|
882 }
|
|
|
883 }
|
|
|
884
|
|
|
885 /* Update a live range to contain the basic block NEW_BLOCK, and all
|
|
|
886 blocks on paths between the existing live range and NEW_BLOCK.
|
|
|
887 HEAD is a block contained in the existing live range that dominates
|
|
|
888 all other blocks in the existing live range.
|
|
|
889 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
|
|
|
890 are live in the blocks that we add to the live range.
|
|
|
891 If FULL_RANGE is set, include the full live range of NEW_BB;
|
|
|
892 otherwise, if NEW_BB dominates HEAD_BB, only add registers that
|
|
|
893 are life at the end of NEW_BB for NEW_BB itself.
|
|
|
894 It is a precondition that either NEW_BLOCK dominates HEAD,or
|
|
|
895 HEAD dom NEW_BLOCK. This is used to speed up the
|
|
|
896 implementation of this function. */
|
|
|
897 static void
|
|
|
898 augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range,
|
|
|
899 basic_block head_bb, basic_block new_bb, int full_range)
|
|
|
900 {
|
|
|
901 basic_block *worklist, *tos;
|
|
|
902
|
|
|
903 tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
|
|
|
904
|
|
|
905 if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb))
|
|
|
906 {
|
|
|
907 if (new_bb == head_bb)
|
|
|
908 {
|
|
|
909 if (full_range)
|
|
|
910 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_bb->index]);
|
|
|
911 free (tos);
|
|
|
912 return;
|
|
|
913 }
|
|
|
914 *tos++ = new_bb;
|
|
|
915 }
|
|
|
916 else
|
|
|
917 {
|
|
|
918 edge e;
|
|
|
919 edge_iterator ei;
|
|
|
920 int new_block = new_bb->index;
|
|
|
921
|
|
|
922 gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb));
|
|
|
923
|
|
|
924 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]);
|
|
|
925 bitmap_set_bit (live_range, new_block);
|
|
|
926 /* A previous btr migration could have caused a register to be
|
|
|
927 live just at the end of new_block which we need in full, so
|
|
|
928 use trs_live_at_end even if full_range is set. */
|
|
|
929 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]);
|
|
|
930 if (full_range)
|
|
|
931 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]);
|
|
|
932 if (dump_file)
|
|
|
933 {
|
|
|
934 fprintf (dump_file,
|
|
|
935 "Adding end of block %d and rest of %d to live range\n",
|
|
|
936 new_block, head_bb->index);
|
|
|
937 fprintf (dump_file,"Now live btrs are ");
|
|
|
938 dump_hard_reg_set (*btrs_live_in_range);
|
|
|
939 fprintf (dump_file, "\n");
|
|
|
940 }
|
|
|
941 FOR_EACH_EDGE (e, ei, head_bb->preds)
|
|
|
942 *tos++ = e->src;
|
|
|
943 }
|
|
|
944
|
|
|
945 while (tos != worklist)
|
|
|
946 {
|
|
|
947 basic_block bb = *--tos;
|
|
|
948 if (!bitmap_bit_p (live_range, bb->index))
|
|
|
949 {
|
|
|
950 edge e;
|
|
|
951 edge_iterator ei;
|
|
|
952
|
|
|
953 bitmap_set_bit (live_range, bb->index);
|
|
|
954 IOR_HARD_REG_SET (*btrs_live_in_range,
|
|
|
955 btrs_live[bb->index]);
|
|
|
956 /* A previous btr migration could have caused a register to be
|
|
|
957 live just at the end of a block which we need in full. */
|
|
|
958 IOR_HARD_REG_SET (*btrs_live_in_range,
|
|
|
959 btrs_live_at_end[bb->index]);
|
|
|
960 if (dump_file)
|
|
|
961 {
|
|
|
962 fprintf (dump_file,
|
|
|
963 "Adding block %d to live range\n", bb->index);
|
|
|
964 fprintf (dump_file,"Now live btrs are ");
|
|
|
965 dump_hard_reg_set (*btrs_live_in_range);
|
|
|
966 fprintf (dump_file, "\n");
|
|
|
967 }
|
|
|
968
|
|
|
969 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
970 {
|
|
|
971 basic_block pred = e->src;
|
|
|
972 if (!bitmap_bit_p (live_range, pred->index))
|
|
|
973 *tos++ = pred;
|
|
|
974 }
|
|
|
975 }
|
|
|
976 }
|
|
|
977
|
|
|
978 free (worklist);
|
|
|
979 }
|
|
|
980
|
|
|
981 /* Return the most desirable target register that is not in
|
|
|
982 the set USED_BTRS. */
|
|
|
983 static int
|
|
|
984 choose_btr (HARD_REG_SET used_btrs)
|
|
|
985 {
|
|
|
986 int i;
|
|
|
987
|
|
|
988 if (!hard_reg_set_subset_p (all_btrs, used_btrs))
|
|
|
989 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
|
|
|
990 {
|
|
|
991 #ifdef REG_ALLOC_ORDER
|
|
|
992 int regno = reg_alloc_order[i];
|
|
|
993 #else
|
|
|
994 int regno = i;
|
|
|
995 #endif
|
|
|
996 if (TEST_HARD_REG_BIT (all_btrs, regno)
|
|
|
997 && !TEST_HARD_REG_BIT (used_btrs, regno))
|
|
|
998 return regno;
|
|
|
999 }
|
|
|
1000 return -1;
|
|
|
1001 }
|
|
|
1002
|
|
|
1003 /* Calculate the set of basic blocks that contain the live range of
|
|
|
1004 the def/use web DEF.
|
|
|
1005 Also calculate the set of target registers that are live at time
|
|
|
1006 in this live range, but ignore the live range represented by DEF
|
|
|
1007 when calculating this set. */
|
|
|
1008 static void
|
|
|
1009 btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range)
|
|
|
1010 {
|
|
|
1011 if (!def->live_range)
|
|
|
1012 {
|
|
|
1013 btr_user user;
|
|
|
1014
|
|
|
1015 def->live_range = BITMAP_ALLOC (NULL);
|
|
|
1016
|
|
|
1017 bitmap_set_bit (def->live_range, def->bb->index);
|
|
|
1018 COPY_HARD_REG_SET (*btrs_live_in_range,
|
|
|
1019 (flag_btr_bb_exclusive
|
|
|
1020 ? btrs_live : btrs_live_at_end)[def->bb->index]);
|
|
|
1021
|
|
|
1022 for (user = def->uses; user != NULL; user = user->next)
|
|
|
1023 augment_live_range (def->live_range, btrs_live_in_range,
|
|
|
1024 def->bb, user->bb,
|
|
|
1025 (flag_btr_bb_exclusive
|
|
|
1026 || user->insn != BB_END (def->bb)
|
|
|
1027 || !JUMP_P (user->insn)));
|
|
|
1028 }
|
|
|
1029 else
|
|
|
1030 {
|
|
|
1031 /* def->live_range is accurate, but we need to recompute
|
|
|
1032 the set of target registers live over it, because migration
|
|
|
1033 of other PT instructions may have affected it.
|
|
|
1034 */
|
|
|
1035 unsigned bb;
|
|
|
1036 unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index;
|
|
|
1037 bitmap_iterator bi;
|
|
|
1038
|
|
|
1039 CLEAR_HARD_REG_SET (*btrs_live_in_range);
|
|
|
1040 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
|
|
|
1041 {
|
|
|
1042 IOR_HARD_REG_SET (*btrs_live_in_range,
|
|
|
1043 (def_bb == bb
|
|
|
1044 ? btrs_live_at_end : btrs_live) [bb]);
|
|
|
1045 }
|
|
|
1046 }
|
|
|
1047 if (!def->other_btr_uses_before_def &&
|
|
|
1048 !def->other_btr_uses_after_use)
|
|
|
1049 CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr);
|
|
|
1050 }
|
|
|
1051
|
|
|
1052 /* Merge into the def/use web DEF any other def/use webs in the same
|
|
|
1053 group that are dominated by DEF, provided that there is a target
|
|
|
1054 register available to allocate to the merged web. */
|
|
|
1055 static void
|
|
|
1056 combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range)
|
|
|
1057 {
|
|
|
1058 btr_def other_def;
|
|
|
1059
|
|
|
1060 for (other_def = def->group->members;
|
|
|
1061 other_def != NULL;
|
|
|
1062 other_def = other_def->next_this_group)
|
|
|
1063 {
|
|
|
1064 if (other_def != def
|
|
|
1065 && other_def->uses != NULL
|
|
|
1066 && ! other_def->has_ambiguous_use
|
|
|
1067 && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb))
|
|
|
1068 {
|
|
|
1069 /* def->bb dominates the other def, so def and other_def could
|
|
|
1070 be combined. */
|
|
|
1071 /* Merge their live ranges, and get the set of
|
|
|
1072 target registers live over the merged range. */
|
|
|
1073 int btr;
|
|
|
1074 HARD_REG_SET combined_btrs_live;
|
|
|
1075 bitmap combined_live_range = BITMAP_ALLOC (NULL);
|
|
|
1076 btr_user user;
|
|
|
1077
|
|
|
1078 if (other_def->live_range == NULL)
|
|
|
1079 {
|
|
|
1080 HARD_REG_SET dummy_btrs_live_in_range;
|
|
|
1081 btr_def_live_range (other_def, &dummy_btrs_live_in_range);
|
|
|
1082 }
|
|
|
1083 COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range);
|
|
|
1084 bitmap_copy (combined_live_range, def->live_range);
|
|
|
1085
|
|
|
1086 for (user = other_def->uses; user != NULL; user = user->next)
|
|
|
1087 augment_live_range (combined_live_range, &combined_btrs_live,
|
|
|
1088 def->bb, user->bb,
|
|
|
1089 (flag_btr_bb_exclusive
|
|
|
1090 || user->insn != BB_END (def->bb)
|
|
|
1091 || !JUMP_P (user->insn)));
|
|
|
1092
|
|
|
1093 btr = choose_btr (combined_btrs_live);
|
|
|
1094 if (btr != -1)
|
|
|
1095 {
|
|
|
1096 /* We can combine them. */
|
|
|
1097 if (dump_file)
|
|
|
1098 fprintf (dump_file,
|
|
|
1099 "Combining def in insn %d with def in insn %d\n",
|
|
|
1100 INSN_UID (other_def->insn), INSN_UID (def->insn));
|
|
|
1101
|
|
|
1102 def->btr = btr;
|
|
|
1103 user = other_def->uses;
|
|
|
1104 while (user != NULL)
|
|
|
1105 {
|
|
|
1106 btr_user next = user->next;
|
|
|
1107
|
|
|
1108 user->next = def->uses;
|
|
|
1109 def->uses = user;
|
|
|
1110 user = next;
|
|
|
1111 }
|
|
|
1112 /* Combining def/use webs can make target registers live
|
|
|
1113 after uses where they previously were not. This means
|
|
|
1114 some REG_DEAD notes may no longer be correct. We could
|
|
|
1115 be more precise about this if we looked at the combined
|
|
|
1116 live range, but here I just delete any REG_DEAD notes
|
|
|
1117 in case they are no longer correct. */
|
|
|
1118 for (user = def->uses; user != NULL; user = user->next)
|
|
|
1119 remove_note (user->insn,
|
|
|
1120 find_regno_note (user->insn, REG_DEAD,
|
|
|
1121 REGNO (user->use)));
|
|
|
1122 clear_btr_from_live_range (other_def);
|
|
|
1123 other_def->uses = NULL;
|
|
|
1124 bitmap_copy (def->live_range, combined_live_range);
|
|
|
1125 if (other_def->btr == btr && other_def->other_btr_uses_after_use)
|
|
|
1126 def->other_btr_uses_after_use = 1;
|
|
|
1127 COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live);
|
|
|
1128
|
|
|
1129 /* Delete the old target register initialization. */
|
|
|
1130 delete_insn (other_def->insn);
|
|
|
1131
|
|
|
1132 }
|
|
|
1133 BITMAP_FREE (combined_live_range);
|
|
|
1134 }
|
|
|
1135 }
|
|
|
1136 }
|
|
|
1137
|
|
|
1138 /* Move the definition DEF from its current position to basic
|
|
|
1139 block NEW_DEF_BB, and modify it to use branch target register BTR.
|
|
|
1140 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
|
|
|
1141 Update all reaching uses of DEF in the RTL to use BTR.
|
|
|
1142 If this new position means that other defs in the
|
|
|
1143 same group can be combined with DEF then combine them. */
|
|
|
1144 static void
|
|
|
1145 move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range,
|
|
|
1146 HARD_REG_SET *btrs_live_in_range)
|
|
|
1147 {
|
|
|
1148 /* We can move the instruction.
|
|
|
1149 Set a target register in block NEW_DEF_BB to the value
|
|
|
1150 needed for this target register definition.
|
|
|
1151 Replace all uses of the old target register definition by
|
|
|
1152 uses of the new definition. Delete the old definition. */
|
|
|
1153 basic_block b = new_def_bb;
|
|
|
1154 rtx insp = BB_HEAD (b);
|
|
|
1155 rtx old_insn = def->insn;
|
|
|
1156 rtx src;
|
|
|
1157 rtx btr_rtx;
|
|
|
1158 rtx new_insn;
|
|
|
1159 enum machine_mode btr_mode;
|
|
|
1160 btr_user user;
|
|
|
1161 rtx set;
|
|
|
1162
|
|
|
1163 if (dump_file)
|
|
|
1164 fprintf(dump_file, "migrating to basic block %d, using reg %d\n",
|
|
|
1165 new_def_bb->index, btr);
|
|
|
1166
|
|
|
1167 clear_btr_from_live_range (def);
|
|
|
1168 def->btr = btr;
|
|
|
1169 def->bb = new_def_bb;
|
|
|
1170 def->luid = 0;
|
|
|
1171 def->cost = basic_block_freq (new_def_bb);
|
|
|
1172 bitmap_copy (def->live_range, live_range);
|
|
|
1173 combine_btr_defs (def, btrs_live_in_range);
|
|
|
1174 btr = def->btr;
|
|
|
1175 def->other_btr_uses_before_def
|
|
|
1176 = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0;
|
|
|
1177 add_btr_to_live_range (def, 1);
|
|
|
1178 if (LABEL_P (insp))
|
|
|
1179 insp = NEXT_INSN (insp);
|
|
|
1180 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
|
|
|
1181 optimizations can result in insp being both first and last insn of
|
|
|
1182 its basic block. */
|
|
|
1183 /* ?? some assertions to check that insp is sensible? */
|
|
|
1184
|
|
|
1185 if (def->other_btr_uses_before_def)
|
|
|
1186 {
|
|
|
1187 insp = BB_END (b);
|
|
|
1188 for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp))
|
|
|
1189 gcc_assert (insp != BB_HEAD (b));
|
|
|
1190
|
|
|
1191 if (JUMP_P (insp) || can_throw_internal (insp))
|
|
|
1192 insp = PREV_INSN (insp);
|
|
|
1193 }
|
|
|
1194
|
|
|
1195 set = single_set (old_insn);
|
|
|
1196 src = SET_SRC (set);
|
|
|
1197 btr_mode = GET_MODE (SET_DEST (set));
|
|
|
1198 btr_rtx = gen_rtx_REG (btr_mode, btr);
|
|
|
1199
|
|
|
1200 new_insn = gen_move_insn (btr_rtx, src);
|
|
|
1201
|
|
|
1202 /* Insert target register initialization at head of basic block. */
|
|
|
1203 def->insn = emit_insn_after (new_insn, insp);
|
|
|
1204
|
|
|
1205 df_set_regs_ever_live (btr, true);
|
|
|
1206
|
|
|
1207 if (dump_file)
|
|
|
1208 fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n",
|
|
|
1209 INSN_UID (def->insn), INSN_UID (insp));
|
|
|
1210
|
|
|
1211 /* Delete the old target register initialization. */
|
|
|
1212 delete_insn (old_insn);
|
|
|
1213
|
|
|
1214 /* Replace each use of the old target register by a use of the new target
|
|
|
1215 register. */
|
|
|
1216 for (user = def->uses; user != NULL; user = user->next)
|
|
|
1217 {
|
|
|
1218 /* Some extra work here to ensure consistent modes, because
|
|
|
1219 it seems that a target register REG rtx can be given a different
|
|
|
1220 mode depending on the context (surely that should not be
|
|
|
1221 the case?). */
|
|
|
1222 rtx replacement_rtx;
|
|
|
1223 if (GET_MODE (user->use) == GET_MODE (btr_rtx)
|
|
|
1224 || GET_MODE (user->use) == VOIDmode)
|
|
|
1225 replacement_rtx = btr_rtx;
|
|
|
1226 else
|
|
|
1227 replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr);
|
|
|
1228 validate_replace_rtx (user->use, replacement_rtx, user->insn);
|
|
|
1229 user->use = replacement_rtx;
|
|
|
1230 }
|
|
|
1231 }
|
|
|
1232
|
|
|
1233 /* We anticipate intra-block scheduling to be done. See if INSN could move
|
|
|
1234 up within BB by N_INSNS. */
|
|
|
1235 static int
|
|
|
1236 can_move_up (const_basic_block bb, const_rtx insn, int n_insns)
|
|
|
1237 {
|
|
|
1238 while (insn != BB_HEAD (bb) && n_insns > 0)
|
|
|
1239 {
|
|
|
1240 insn = PREV_INSN (insn);
|
|
|
1241 /* ??? What if we have an anti-dependency that actually prevents the
|
|
|
1242 scheduler from doing the move? We'd like to re-allocate the register,
|
|
|
1243 but not necessarily put the load into another basic block. */
|
|
|
1244 if (INSN_P (insn))
|
|
|
1245 n_insns--;
|
|
|
1246 }
|
|
|
1247 return n_insns <= 0;
|
|
|
1248 }
|
|
|
1249
|
|
|
1250 /* Attempt to migrate the target register definition DEF to an
|
|
|
1251 earlier point in the flowgraph.
|
|
|
1252
|
|
|
1253 It is a precondition of this function that DEF is migratable:
|
|
|
1254 i.e. it has a constant source, and all uses are unambiguous.
|
|
|
1255
|
|
|
1256 Only migrations that reduce the cost of DEF will be made.
|
|
|
1257 MIN_COST is the lower bound on the cost of the DEF after migration.
|
|
|
1258 If we migrate DEF so that its cost falls below MIN_COST,
|
|
|
1259 then we do not attempt to migrate further. The idea is that
|
|
|
1260 we migrate definitions in a priority order based on their cost,
|
|
|
1261 when the cost of this definition falls below MIN_COST, then
|
|
|
1262 there is another definition with cost == MIN_COST which now
|
|
|
1263 has a higher priority than this definition.
|
|
|
1264
|
|
|
1265 Return nonzero if there may be benefit from attempting to
|
|
|
1266 migrate this DEF further (i.e. we have reduced the cost below
|
|
|
1267 MIN_COST, but we may be able to reduce it further).
|
|
|
1268 Return zero if no further migration is possible. */
|
|
|
1269 static int
|
|
|
1270 migrate_btr_def (btr_def def, int min_cost)
|
|
|
1271 {
|
|
|
1272 bitmap live_range;
|
|
|
1273 HARD_REG_SET btrs_live_in_range;
|
|
|
1274 int btr_used_near_def = 0;
|
|
|
1275 int def_basic_block_freq;
|
|
|
1276 basic_block attempt;
|
|
|
1277 int give_up = 0;
|
|
|
1278 int def_moved = 0;
|
|
|
1279 btr_user user;
|
|
|
1280 int def_latency;
|
|
|
1281
|
|
|
1282 if (dump_file)
|
|
|
1283 fprintf (dump_file,
|
|
|
1284 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
|
|
|
1285 INSN_UID (def->insn), def->cost, min_cost);
|
|
|
1286
|
|
|
1287 if (!def->group || def->has_ambiguous_use)
|
|
|
1288 /* These defs are not migratable. */
|
|
|
1289 {
|
|
|
1290 if (dump_file)
|
|
|
1291 fprintf (dump_file, "it's not migratable\n");
|
|
|
1292 return 0;
|
|
|
1293 }
|
|
|
1294
|
|
|
1295 if (!def->uses)
|
|
|
1296 /* We have combined this def with another in the same group, so
|
|
|
1297 no need to consider it further.
|
|
|
1298 */
|
|
|
1299 {
|
|
|
1300 if (dump_file)
|
|
|
1301 fprintf (dump_file, "it's already combined with another pt\n");
|
|
|
1302 return 0;
|
|
|
1303 }
|
|
|
1304
|
|
|
1305 btr_def_live_range (def, &btrs_live_in_range);
|
|
|
1306 live_range = BITMAP_ALLOC (NULL);
|
|
|
1307 bitmap_copy (live_range, def->live_range);
|
|
|
1308
|
|
|
1309 #ifdef INSN_SCHEDULING
|
|
|
1310 def_latency = insn_default_latency (def->insn) * issue_rate;
|
|
|
1311 #else
|
|
|
1312 def_latency = issue_rate;
|
|
|
1313 #endif
|
|
|
1314
|
|
|
1315 for (user = def->uses; user != NULL; user = user->next)
|
|
|
1316 {
|
|
|
1317 if (user->bb == def->bb
|
|
|
1318 && user->luid > def->luid
|
|
|
1319 && (def->luid + def_latency) > user->luid
|
|
|
1320 && ! can_move_up (def->bb, def->insn,
|
|
|
1321 (def->luid + def_latency) - user->luid))
|
|
|
1322 {
|
|
|
1323 btr_used_near_def = 1;
|
|
|
1324 break;
|
|
|
1325 }
|
|
|
1326 }
|
|
|
1327
|
|
|
1328 def_basic_block_freq = basic_block_freq (def->bb);
|
|
|
1329
|
|
|
1330 for (attempt = get_immediate_dominator (CDI_DOMINATORS, def->bb);
|
|
|
1331 !give_up && attempt && attempt != ENTRY_BLOCK_PTR && def->cost >= min_cost;
|
|
|
1332 attempt = get_immediate_dominator (CDI_DOMINATORS, attempt))
|
|
|
1333 {
|
|
|
1334 /* Try to move the instruction that sets the target register into
|
|
|
1335 basic block ATTEMPT. */
|
|
|
1336 int try_freq = basic_block_freq (attempt);
|
|
|
1337 edge_iterator ei;
|
|
|
1338 edge e;
|
|
|
1339
|
|
|
1340 /* If ATTEMPT has abnormal edges, skip it. */
|
|
|
1341 FOR_EACH_EDGE (e, ei, attempt->succs)
|
|
|
1342 if (e->flags & EDGE_COMPLEX)
|
|
|
1343 break;
|
|
|
1344 if (e)
|
|
|
1345 continue;
|
|
|
1346
|
|
|
1347 if (dump_file)
|
|
|
1348 fprintf (dump_file, "trying block %d ...", attempt->index);
|
|
|
1349
|
|
|
1350 if (try_freq < def_basic_block_freq
|
|
|
1351 || (try_freq == def_basic_block_freq && btr_used_near_def))
|
|
|
1352 {
|
|
|
1353 int btr;
|
|
|
1354 augment_live_range (live_range, &btrs_live_in_range, def->bb, attempt,
|
|
|
1355 flag_btr_bb_exclusive);
|
|
|
1356 if (dump_file)
|
|
|
1357 {
|
|
|
1358 fprintf (dump_file, "Now btrs live in range are: ");
|
|
|
1359 dump_hard_reg_set (btrs_live_in_range);
|
|
|
1360 fprintf (dump_file, "\n");
|
|
|
1361 }
|
|
|
1362 btr = choose_btr (btrs_live_in_range);
|
|
|
1363 if (btr != -1)
|
|
|
1364 {
|
|
|
1365 move_btr_def (attempt, btr, def, live_range, &btrs_live_in_range);
|
|
|
1366 bitmap_copy(live_range, def->live_range);
|
|
|
1367 btr_used_near_def = 0;
|
|
|
1368 def_moved = 1;
|
|
|
1369 def_basic_block_freq = basic_block_freq (def->bb);
|
|
|
1370 }
|
|
|
1371 else
|
|
|
1372 {
|
|
|
1373 /* There are no free target registers available to move
|
|
|
1374 this far forward, so give up */
|
|
|
1375 give_up = 1;
|
|
|
1376 if (dump_file)
|
|
|
1377 fprintf (dump_file,
|
|
|
1378 "giving up because there are no free target registers\n");
|
|
|
1379 }
|
|
|
1380
|
|
|
1381 }
|
|
|
1382 }
|
|
|
1383 if (!def_moved)
|
|
|
1384 {
|
|
|
1385 give_up = 1;
|
|
|
1386 if (dump_file)
|
|
|
1387 fprintf (dump_file, "failed to move\n");
|
|
|
1388 }
|
|
|
1389 BITMAP_FREE (live_range);
|
|
|
1390 return !give_up;
|
|
|
1391 }
|
|
|
1392
|
|
|
1393 /* Attempt to move instructions that set target registers earlier
|
|
|
1394 in the flowgraph, away from their corresponding uses. */
|
|
|
1395 static void
|
|
|
1396 migrate_btr_defs (enum reg_class btr_class, int allow_callee_save)
|
|
|
1397 {
|
|
|
1398 fibheap_t all_btr_defs = fibheap_new ();
|
|
|
1399 int reg;
|
|
|
1400
|
|
|
1401 gcc_obstack_init (&migrate_btrl_obstack);
|
|
|
1402 if (dump_file)
|
|
|
1403 {
|
|
|
1404 int i;
|
|
|
1405
|
|
|
1406 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
|
|
|
1407 {
|
|
|
1408 basic_block bb = BASIC_BLOCK (i);
|
|
|
1409 fprintf(dump_file,
|
|
|
1410 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
|
|
|
1411 " loop-depth = %d idom = %d\n",
|
|
|
1412 i, (HOST_WIDEST_INT) bb->count, bb->loop_depth,
|
|
|
1413 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
|
|
|
1414 }
|
|
|
1415 }
|
|
|
1416
|
|
|
1417 CLEAR_HARD_REG_SET (all_btrs);
|
|
|
1418 for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
|
|
|
1419 if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg)
|
|
|
1420 && (allow_callee_save || call_used_regs[reg]
|
|
|
1421 || df_regs_ever_live_p (reg)))
|
|
|
1422 {
|
|
|
1423 SET_HARD_REG_BIT (all_btrs, reg);
|
|
|
1424 last_btr = reg;
|
|
|
1425 if (first_btr < 0)
|
|
|
1426 first_btr = reg;
|
|
|
1427 }
|
|
|
1428
|
|
|
1429 btrs_live = XCNEWVEC (HARD_REG_SET, n_basic_blocks);
|
|
|
1430 btrs_live_at_end = XCNEWVEC (HARD_REG_SET, n_basic_blocks);
|
|
|
1431
|
|
|
1432 build_btr_def_use_webs (all_btr_defs);
|
|
|
1433
|
|
|
1434 while (!fibheap_empty (all_btr_defs))
|
|
|
1435 {
|
|
|
1436 btr_def def = (btr_def) fibheap_extract_min (all_btr_defs);
|
|
|
1437 int min_cost = -fibheap_min_key (all_btr_defs);
|
|
|
1438 if (migrate_btr_def (def, min_cost))
|
|
|
1439 {
|
|
|
1440 fibheap_insert (all_btr_defs, -def->cost, (void *) def);
|
|
|
1441 if (dump_file)
|
|
|
1442 {
|
|
|
1443 fprintf (dump_file,
|
|
|
1444 "Putting insn %d back on queue with priority %d\n",
|
|
|
1445 INSN_UID (def->insn), def->cost);
|
|
|
1446 }
|
|
|
1447 }
|
|
|
1448 else
|
|
|
1449 BITMAP_FREE (def->live_range);
|
|
|
1450 }
|
|
|
1451
|
|
|
1452 free (btrs_live);
|
|
|
1453 free (btrs_live_at_end);
|
|
|
1454 obstack_free (&migrate_btrl_obstack, NULL);
|
|
|
1455 fibheap_delete (all_btr_defs);
|
|
|
1456 }
|
|
|
1457
|
|
|
1458 static void
|
|
|
1459 branch_target_load_optimize (bool after_prologue_epilogue_gen)
|
|
|
1460 {
|
|
|
1461 enum reg_class klass = targetm.branch_target_register_class ();
|
|
|
1462 if (klass != NO_REGS)
|
|
|
1463 {
|
|
|
1464 /* Initialize issue_rate. */
|
|
|
1465 if (targetm.sched.issue_rate)
|
|
|
1466 issue_rate = targetm.sched.issue_rate ();
|
|
|
1467 else
|
|
|
1468 issue_rate = 1;
|
|
|
1469
|
|
|
1470 if (!after_prologue_epilogue_gen)
|
|
|
1471 {
|
|
|
1472 /* Build the CFG for migrate_btr_defs. */
|
|
|
1473 #if 1
|
|
|
1474 /* This may or may not be needed, depending on where we
|
|
|
1475 run this phase. */
|
|
|
1476 cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0);
|
|
|
1477 #endif
|
|
|
1478 }
|
|
|
1479 df_analyze ();
|
|
|
1480
|
|
|
1481
|
|
|
1482 /* Dominator info is also needed for migrate_btr_def. */
|
|
|
1483 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
1484 migrate_btr_defs (klass,
|
|
|
1485 (targetm.branch_target_register_callee_saved
|
|
|
1486 (after_prologue_epilogue_gen)));
|
|
|
1487
|
|
|
1488 free_dominance_info (CDI_DOMINATORS);
|
|
|
1489 }
|
|
|
1490 }
|
|
|
1491
|
|
|
1492 static bool
|
|
|
1493 gate_handle_branch_target_load_optimize1 (void)
|
|
|
1494 {
|
|
|
1495 return flag_branch_target_load_optimize;
|
|
|
1496 }
|
|
|
1497
|
|
|
1498
|
|
|
1499 static unsigned int
|
|
|
1500 rest_of_handle_branch_target_load_optimize1 (void)
|
|
|
1501 {
|
|
|
1502 branch_target_load_optimize (epilogue_completed);
|
|
|
1503 return 0;
|
|
|
1504 }
|
|
|
1505
|
|
|
1506 struct rtl_opt_pass pass_branch_target_load_optimize1 =
|
|
|
1507 {
|
|
|
1508 {
|
|
|
1509 RTL_PASS,
|
|
|
1510 "btl1", /* name */
|
|
|
1511 gate_handle_branch_target_load_optimize1, /* gate */
|
|
|
1512 rest_of_handle_branch_target_load_optimize1, /* execute */
|
|
|
1513 NULL, /* sub */
|
|
|
1514 NULL, /* next */
|
|
|
1515 0, /* static_pass_number */
|
|
|
1516 0, /* tv_id */
|
|
|
1517 0, /* properties_required */
|
|
|
1518 0, /* properties_provided */
|
|
|
1519 0, /* properties_destroyed */
|
|
|
1520 0, /* todo_flags_start */
|
|
|
1521 TODO_dump_func |
|
|
|
1522 TODO_verify_rtl_sharing |
|
|
|
1523 TODO_ggc_collect, /* todo_flags_finish */
|
|
|
1524 }
|
|
|
1525 };
|
|
|
1526
|
|
|
1527 static bool
|
|
|
1528 gate_handle_branch_target_load_optimize2 (void)
|
|
|
1529 {
|
|
|
1530 return (optimize > 0 && flag_branch_target_load_optimize2);
|
|
|
1531 }
|
|
|
1532
|
|
|
1533
|
|
|
1534 static unsigned int
|
|
|
1535 rest_of_handle_branch_target_load_optimize2 (void)
|
|
|
1536 {
|
|
|
1537 static int warned = 0;
|
|
|
1538
|
|
|
1539 /* Leave this a warning for now so that it is possible to experiment
|
|
|
1540 with running this pass twice. In 3.6, we should either make this
|
|
|
1541 an error, or use separate dump files. */
|
|
|
1542 if (flag_branch_target_load_optimize
|
|
|
1543 && flag_branch_target_load_optimize2
|
|
|
1544 && !warned)
|
|
|
1545 {
|
|
|
1546 warning (0, "branch target register load optimization is not intended "
|
|
|
1547 "to be run twice");
|
|
|
1548
|
|
|
1549 warned = 1;
|
|
|
1550 }
|
|
|
1551
|
|
|
1552 branch_target_load_optimize (epilogue_completed);
|
|
|
1553 return 0;
|
|
|
1554 }
|
|
|
1555
|
|
|
1556 struct rtl_opt_pass pass_branch_target_load_optimize2 =
|
|
|
1557 {
|
|
|
1558 {
|
|
|
1559 RTL_PASS,
|
|
|
1560 "btl2", /* name */
|
|
|
1561 gate_handle_branch_target_load_optimize2, /* gate */
|
|
|
1562 rest_of_handle_branch_target_load_optimize2, /* execute */
|
|
|
1563 NULL, /* sub */
|
|
|
1564 NULL, /* next */
|
|
|
1565 0, /* static_pass_number */
|
|
|
1566 0, /* tv_id */
|
|
|
1567 0, /* properties_required */
|
|
|
1568 0, /* properties_provided */
|
|
|
1569 0, /* properties_destroyed */
|
|
|
1570 0, /* todo_flags_start */
|
|
|
1571 TODO_dump_func |
|
|
|
1572 TODO_ggc_collect, /* todo_flags_finish */
|
|
|
1573 }
|
|
|
1574 };
|
|
|
1575
|
