1 /* Scanning of rtl for dataflow analysis.
2 Copyright (C) 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Kenneth Zadeck (zadeck@naturalbridge.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 "rtl.h"
28 #include "tm_p.h"
29 #include "flags.h"
30 #include "regs.h"
31 #include "output.h"
32 #include "except.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
35 #include "timevar.h"
36 #include "df.h"
37
38
39 struct regstat_n_sets_and_refs_t *regstat_n_sets_and_refs;
40
41 /*----------------------------------------------------------------------------
42 REG_N_SETS and REG_N_REFS.
43 ----------------------------------------------------------------------------*/
44
45 /* If a pass need to change these values in some magical way or the
46 pass needs to have accurate values for these and is not using
47 incremental df scanning, then it should use REG_N_SETS and
48 REG_N_USES. If the pass is doing incremental scanning then it
49 should be getting the info from DF_REG_DEF_COUNT and
50 DF_REG_USE_COUNT. */
51
52 void
regstat_init_n_sets_and_refs(void)53 regstat_init_n_sets_and_refs (void)
54 {
55 unsigned int i;
56 unsigned int max_regno = max_reg_num ();
57
58 timevar_push (TV_REG_STATS);
59 df_grow_reg_info ();
60 gcc_assert (!regstat_n_sets_and_refs);
61
62 regstat_n_sets_and_refs = XNEWVEC (struct regstat_n_sets_and_refs_t, max_regno);
63
64 if (MAY_HAVE_DEBUG_INSNS)
65 for (i = 0; i < max_regno; i++)
66 {
67 int use_count;
68 df_ref use;
69
70 use_count = DF_REG_USE_COUNT (i);
71 for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
72 if (DF_REF_INSN_INFO (use) && DEBUG_INSN_P (DF_REF_INSN (use)))
73 use_count--;
74
75
76 SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
77 SET_REG_N_REFS (i, use_count + REG_N_SETS (i));
78 }
79 else
80 for (i = 0; i < max_regno; i++)
81 {
82 SET_REG_N_SETS (i, DF_REG_DEF_COUNT (i));
83 SET_REG_N_REFS (i, DF_REG_USE_COUNT (i) + REG_N_SETS (i));
84 }
85 timevar_pop (TV_REG_STATS);
86
87 }
88
89
90 /* Free the array that holds the REG_N_SETS and REG_N_REFS. */
91
92 void
regstat_free_n_sets_and_refs(void)93 regstat_free_n_sets_and_refs (void)
94 {
95 gcc_assert (regstat_n_sets_and_refs);
96 free (regstat_n_sets_and_refs);
97 regstat_n_sets_and_refs = NULL;
98 }
99
100
101 /*----------------------------------------------------------------------------
102 REGISTER INFORMATION
103
104 Process REG_N_DEATHS, REG_LIVE_LENGTH, REG_N_CALLS_CROSSED,
105 REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
106
107 ----------------------------------------------------------------------------*/
108
109 static bitmap setjmp_crosses;
110 struct reg_info_t *reg_info_p;
111
112 /* The number allocated elements of reg_info_p. */
113 size_t reg_info_p_size;
114
115 /* Compute register info: lifetime, bb, and number of defs and uses
116 for basic block BB. The three bitvectors are scratch regs used
117 here. */
118
119 static void
regstat_bb_compute_ri(unsigned int bb_index,bitmap live,bitmap do_not_gen,bitmap artificial_uses,bitmap local_live,bitmap local_processed)120 regstat_bb_compute_ri (unsigned int bb_index,
121 bitmap live, bitmap do_not_gen, bitmap artificial_uses,
122 bitmap local_live, bitmap local_processed)
123 {
124 basic_block bb = BASIC_BLOCK (bb_index);
125 rtx insn;
126 df_ref *def_rec;
127 df_ref *use_rec;
128 int luid = 0;
129 bitmap_iterator bi;
130 unsigned int regno;
131
132 bitmap_copy (live, df_get_live_out (bb));
133 bitmap_clear (artificial_uses);
134
135 /* Process the regs live at the end of the block. Mark them as
136 not local to any one basic block. */
137 EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
138 REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
139
140 /* Process the artificial defs and uses at the bottom of the block
141 to begin processing. */
142 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
143 {
144 df_ref def = *def_rec;
145 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
146 bitmap_clear_bit (live, DF_REF_REGNO (def));
147 }
148
149 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
150 {
151 df_ref use = *use_rec;
152 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
153 {
154 regno = DF_REF_REGNO (use);
155 bitmap_set_bit (live, regno);
156 bitmap_set_bit (artificial_uses, regno);
157 }
158 }
159
160 FOR_BB_INSNS_REVERSE (bb, insn)
161 {
162 unsigned int uid = INSN_UID (insn);
163 unsigned int regno;
164 bitmap_iterator bi;
165 struct df_mw_hardreg **mws_rec;
166 rtx link;
167
168 if (!NONDEBUG_INSN_P (insn))
169 continue;
170
171 /* Increment the live_length for all of the registers that
172 are are referenced in this block and live at this
173 particular point. */
174 EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi)
175 {
176 REG_LIVE_LENGTH (regno)++;
177 }
178 luid++;
179
180 bitmap_clear (do_not_gen);
181
182 link = REG_NOTES (insn);
183 while (link)
184 {
185 if (REG_NOTE_KIND (link) == REG_DEAD)
186 REG_N_DEATHS(REGNO (XEXP (link, 0)))++;
187 link = XEXP (link, 1);
188 }
189
190 /* Process the defs. */
191 if (CALL_P (insn))
192 {
193 bool can_throw = can_throw_internal (insn);
194 bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL);
195 EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
196 {
197 REG_N_CALLS_CROSSED (regno)++;
198 REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
199 if (can_throw)
200 REG_N_THROWING_CALLS_CROSSED (regno)++;
201
202 /* We have a problem with any pseudoreg that lives
203 across the setjmp. ANSI says that if a user variable
204 does not change in value between the setjmp and the
205 longjmp, then the longjmp preserves it. This
206 includes longjmp from a place where the pseudo
207 appears dead. (In principle, the value still exists
208 if it is in scope.) If the pseudo goes in a hard
209 reg, some other value may occupy that hard reg where
210 this pseudo is dead, thus clobbering the pseudo.
211 Conclusion: such a pseudo must not go in a hard
212 reg. */
213 if (set_jump)
214 bitmap_set_bit (setjmp_crosses, regno);
215 }
216 }
217
218 /* We only care about real sets for calls. Clobbers only
219 may clobbers cannot be depended on. */
220 for (mws_rec = DF_INSN_UID_MWS (uid); *mws_rec; mws_rec++)
221 {
222 struct df_mw_hardreg *mws = *mws_rec;
223 if (DF_MWS_REG_DEF_P (mws))
224 {
225 bool all_dead = true;
226 unsigned int r;
227
228 for (r=mws->start_regno; r <= mws->end_regno; r++)
229 if ((bitmap_bit_p (live, r))
230 || bitmap_bit_p (artificial_uses, r))
231 {
232 all_dead = false;
233 break;
234 }
235
236 if (all_dead)
237 {
238 unsigned int regno = mws->start_regno;
239 bitmap_set_bit (do_not_gen, regno);
240 /* Only do this if the value is totally dead. */
241 REG_LIVE_LENGTH (regno)++;
242 }
243 }
244 }
245
246 /* All of the defs except the return value are some sort of
247 clobber. This code is for the return. */
248 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
249 {
250 df_ref def = *def_rec;
251 if ((!CALL_P (insn))
252 || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
253 {
254 unsigned int dregno = DF_REF_REGNO (def);
255
256 if (bitmap_bit_p (live, dregno))
257 {
258 /* If we have seen this regno, then it has already been
259 processed correctly with the per insn increment. If we
260 have not seen it we need to add the length from here to
261 the end of the block to the live length. */
262 if (bitmap_bit_p (local_processed, dregno))
263 {
264 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
265 bitmap_clear_bit (local_live, dregno);
266 }
267 else
268 {
269 bitmap_set_bit (local_processed, dregno);
270 REG_LIVE_LENGTH (dregno) += luid;
271 }
272 }
273 else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG))
274 && (!bitmap_bit_p (artificial_uses, dregno)))
275 {
276 REG_LIVE_LENGTH (dregno)++;
277 }
278
279 if (dregno >= FIRST_PSEUDO_REGISTER)
280 {
281 REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
282 if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
283 REG_BASIC_BLOCK (dregno) = bb->index;
284 else if (REG_BASIC_BLOCK (dregno) != bb->index)
285 REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
286 }
287
288 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
289 bitmap_set_bit (do_not_gen, dregno);
290
291 /* Kill this register if it is not a subreg store or conditional store. */
292 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
293 bitmap_clear_bit (live, dregno);
294 }
295 }
296
297 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
298 {
299 df_ref use = *use_rec;
300 unsigned int uregno = DF_REF_REGNO (use);
301
302 if (uregno >= FIRST_PSEUDO_REGISTER)
303 {
304 REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
305 if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
306 REG_BASIC_BLOCK (uregno) = bb->index;
307 else if (REG_BASIC_BLOCK (uregno) != bb->index)
308 REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
309 }
310
311 if (bitmap_set_bit (live, uregno))
312 {
313 /* This register is now live. */
314
315 /* If we have seen this regno, then it has already been
316 processed correctly with the per insn increment. If
317 we have not seen it we set the bit so that begins to
318 get processed locally. Note that we don't even get
319 here if the variable was live at the end of the block
320 since just a ref inside the block does not effect the
321 calculations. */
322 REG_LIVE_LENGTH (uregno) ++;
323 bitmap_set_bit (local_live, uregno);
324 bitmap_set_bit (local_processed, uregno);
325 }
326 }
327 }
328
329 /* Add the length of the block to all of the registers that were not
330 referenced, but still live in this block. */
331 bitmap_and_compl_into (live, local_processed);
332 EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
333 REG_LIVE_LENGTH (regno) += luid;
334
335 bitmap_clear (local_processed);
336 bitmap_clear (local_live);
337 }
338
339
340 /* Compute register info: lifetime, bb, and number of defs and uses. */
341 void
regstat_compute_ri(void)342 regstat_compute_ri (void)
343 {
344 basic_block bb;
345 bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
346 bitmap do_not_gen = BITMAP_ALLOC (&df_bitmap_obstack);
347 bitmap artificial_uses = BITMAP_ALLOC (&df_bitmap_obstack);
348 bitmap local_live = BITMAP_ALLOC (&df_bitmap_obstack);
349 bitmap local_processed = BITMAP_ALLOC (&df_bitmap_obstack);
350 unsigned int regno;
351 bitmap_iterator bi;
352
353 /* Initialize everything. */
354
355 gcc_assert (!reg_info_p);
356
357 timevar_push (TV_REG_STATS);
358 setjmp_crosses = BITMAP_ALLOC (&df_bitmap_obstack);
359 max_regno = max_reg_num ();
360 reg_info_p_size = max_regno;
361 reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
362
363 FOR_EACH_BB (bb)
364 {
365 regstat_bb_compute_ri (bb->index, live, do_not_gen, artificial_uses,
366 local_live, local_processed);
367 }
368
369 BITMAP_FREE (live);
370 BITMAP_FREE (do_not_gen);
371 BITMAP_FREE (artificial_uses);
372
373 /* See the setjmp comment in regstat_ri_bb_compute. */
374 EXECUTE_IF_SET_IN_BITMAP (setjmp_crosses, FIRST_PSEUDO_REGISTER, regno, bi)
375 {
376 REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
377 REG_LIVE_LENGTH (regno) = -1;
378 }
379
380 BITMAP_FREE (local_live);
381 BITMAP_FREE (local_processed);
382 timevar_pop (TV_REG_STATS);
383 }
384
385
386 /* Free all storage associated with the problem. */
387
388 void
regstat_free_ri(void)389 regstat_free_ri (void)
390 {
391 gcc_assert (reg_info_p);
392 reg_info_p_size = 0;
393 free (reg_info_p);
394 reg_info_p = NULL;
395
396 BITMAP_FREE (setjmp_crosses);
397 }
398
399
400 /* Return a bitmap containing the set of registers that cross a setjmp.
401 The client should not change or delete this bitmap. */
402
403 bitmap
regstat_get_setjmp_crosses(void)404 regstat_get_setjmp_crosses (void)
405 {
406 return setjmp_crosses;
407 }
408
409 /*----------------------------------------------------------------------------
410 Process REG_N_CALLS_CROSSED.
411
412 This is used by sched_deps. A good implementation of sched-deps
413 would really process the blocks directly rather than going through
414 lists of insns. If it did this, it could use the exact regs that
415 cross an individual call rather than using this info that merges
416 the info for all calls.
417
418 ----------------------------------------------------------------------------*/
419
420
421
422 /* Compute calls crossed for BB. Live is a scratch bitvector. */
423
424 static void
regstat_bb_compute_calls_crossed(unsigned int bb_index,bitmap live)425 regstat_bb_compute_calls_crossed (unsigned int bb_index, bitmap live)
426 {
427 basic_block bb = BASIC_BLOCK (bb_index);
428 rtx insn;
429 df_ref *def_rec;
430 df_ref *use_rec;
431
432 bitmap_copy (live, df_get_live_out (bb));
433
434 /* Process the artificial defs and uses at the bottom of the block
435 to begin processing. */
436 for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
437 {
438 df_ref def = *def_rec;
439 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
440 bitmap_clear_bit (live, DF_REF_REGNO (def));
441 }
442
443 for (use_rec = df_get_artificial_uses (bb_index); *use_rec; use_rec++)
444 {
445 df_ref use = *use_rec;
446 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
447 bitmap_set_bit (live, DF_REF_REGNO (use));
448 }
449
450 FOR_BB_INSNS_REVERSE (bb, insn)
451 {
452 unsigned int uid = INSN_UID (insn);
453 unsigned int regno;
454
455 if (!INSN_P (insn))
456 continue;
457
458 /* Process the defs. */
459 if (CALL_P (insn))
460 {
461 bitmap_iterator bi;
462 EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
463 {
464 REG_N_CALLS_CROSSED (regno)++;
465 REG_FREQ_CALLS_CROSSED (regno) += REG_FREQ_FROM_BB (bb);
466 }
467 }
468
469 /* All of the defs except the return value are some sort of
470 clobber. This code is for the return. */
471 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
472 {
473 df_ref def = *def_rec;
474 if ((!CALL_P (insn))
475 || (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))))
476 {
477 /* Kill this register if it is not a subreg store or conditional store. */
478 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
479 bitmap_clear_bit (live, DF_REF_REGNO (def));
480 }
481 }
482
483 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
484 {
485 df_ref use = *use_rec;
486 bitmap_set_bit (live, DF_REF_REGNO (use));
487 }
488 }
489 }
490
491
492 /* Compute register info: lifetime, bb, and number of defs and uses. */
493 void
regstat_compute_calls_crossed(void)494 regstat_compute_calls_crossed (void)
495 {
496 basic_block bb;
497 bitmap live = BITMAP_ALLOC (&df_bitmap_obstack);
498
499 /* Initialize everything. */
500 gcc_assert (!reg_info_p);
501
502 timevar_push (TV_REG_STATS);
503 max_regno = max_reg_num ();
504 reg_info_p_size = max_regno;
505 reg_info_p = XCNEWVEC (struct reg_info_t, max_regno);
506
507 FOR_EACH_BB (bb)
508 {
509 regstat_bb_compute_calls_crossed (bb->index, live);
510 }
511
512 BITMAP_FREE (live);
513 timevar_pop (TV_REG_STATS);
514 }
515
516
517 /* Free all storage associated with the problem. */
518
519 void
regstat_free_calls_crossed(void)520 regstat_free_calls_crossed (void)
521 {
522 gcc_assert (reg_info_p);
523 reg_info_p_size = 0;
524 free (reg_info_p);
525 reg_info_p = NULL;
526 }
527
528