00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #include "config.h"
00027 #include "system.h"
00028 #include "coretypes.h"
00029 #include "tm.h"
00030 #include "toplev.h"
00031 #include "rtl.h"
00032 #include "tm_p.h"
00033 #include "hard-reg-set.h"
00034 #include "regs.h"
00035 #include "function.h"
00036 #include "flags.h"
00037 #include "insn-config.h"
00038 #include "insn-attr.h"
00039 #include "except.h"
00040 #include "toplev.h"
00041 #include "recog.h"
00042 #include "sched-int.h"
00043 #include "params.h"
00044 #include "cselib.h"
00045 #include "df.h"
00046
00047
00048 static regset reg_pending_sets;
00049 static regset reg_pending_clobbers;
00050 static regset reg_pending_uses;
00051
00052
00053
00054
00055 enum reg_pending_barrier_mode
00056 {
00057 NOT_A_BARRIER = 0,
00058 MOVE_BARRIER,
00059 TRUE_BARRIER
00060 };
00061
00062 static enum reg_pending_barrier_mode reg_pending_barrier;
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077 static bitmap_head *true_dependency_cache;
00078 static bitmap_head *output_dependency_cache;
00079 static bitmap_head *anti_dependency_cache;
00080 static bitmap_head *spec_dependency_cache;
00081 static int cache_size;
00082
00083
00084
00085
00086
00087 #ifdef ENABLE_CHECKING
00088 static bitmap_head *forward_dependency_cache;
00089 #endif
00090
00091 static int deps_may_trap_p (rtx);
00092 static void add_dependence_list (rtx, rtx, int, enum reg_note);
00093 static void add_dependence_list_and_free (rtx, rtx *, int, enum reg_note);
00094 static void delete_all_dependences (rtx);
00095 static void fixup_sched_groups (rtx);
00096
00097 static void flush_pending_lists (struct deps *, rtx, int, int);
00098 static void sched_analyze_1 (struct deps *, rtx, rtx);
00099 static void sched_analyze_2 (struct deps *, rtx, rtx);
00100 static void sched_analyze_insn (struct deps *, rtx, rtx);
00101
00102 static rtx sched_get_condition (rtx);
00103 static int conditions_mutex_p (rtx, rtx);
00104
00105 static enum DEPS_ADJUST_RESULT maybe_add_or_update_back_dep_1 (rtx, rtx,
00106 enum reg_note, ds_t, rtx, rtx, rtx **);
00107 static enum DEPS_ADJUST_RESULT add_or_update_back_dep_1 (rtx, rtx,
00108 enum reg_note, ds_t, rtx, rtx, rtx **);
00109 static void add_back_dep (rtx, rtx, enum reg_note, ds_t);
00110
00111 static void adjust_add_sorted_back_dep (rtx, rtx, rtx *);
00112 static void adjust_back_add_forw_dep (rtx, rtx *);
00113 static void delete_forw_dep (rtx, rtx);
00114 static dw_t estimate_dep_weak (rtx, rtx);
00115 #ifdef INSN_SCHEDULING
00116 #ifdef ENABLE_CHECKING
00117 static void check_dep_status (enum reg_note, ds_t, bool);
00118 #endif
00119 #endif
00120
00121
00122
00123 static int
00124 deps_may_trap_p (rtx mem)
00125 {
00126 rtx addr = XEXP (mem, 0);
00127
00128 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER)
00129 {
00130 rtx t = get_reg_known_value (REGNO (addr));
00131 if (t)
00132 addr = t;
00133 }
00134 return rtx_addr_can_trap_p (addr);
00135 }
00136
00137
00138
00139
00140 rtx
00141 find_insn_list (rtx insn, rtx list)
00142 {
00143 while (list)
00144 {
00145 if (XEXP (list, 0) == insn)
00146 return list;
00147 list = XEXP (list, 1);
00148 }
00149 return 0;
00150 }
00151
00152
00153
00154 static rtx
00155 sched_get_condition (rtx insn)
00156 {
00157 rtx pat = PATTERN (insn);
00158 rtx src;
00159
00160 if (pat == 0)
00161 return 0;
00162
00163 if (GET_CODE (pat) == COND_EXEC)
00164 return COND_EXEC_TEST (pat);
00165
00166 if (!any_condjump_p (insn) || !onlyjump_p (insn))
00167 return 0;
00168
00169 src = SET_SRC (pc_set (insn));
00170
00171 if (XEXP (src, 2) == pc_rtx)
00172 return XEXP (src, 0);
00173 else if (XEXP (src, 1) == pc_rtx)
00174 {
00175 rtx cond = XEXP (src, 0);
00176 enum rtx_code revcode = reversed_comparison_code (cond, insn);
00177
00178 if (revcode == UNKNOWN)
00179 return 0;
00180 return gen_rtx_fmt_ee (revcode, GET_MODE (cond), XEXP (cond, 0),
00181 XEXP (cond, 1));
00182 }
00183
00184 return 0;
00185 }
00186
00187
00188
00189
00190 static int
00191 conditions_mutex_p (rtx cond1, rtx cond2)
00192 {
00193 if (COMPARISON_P (cond1)
00194 && COMPARISON_P (cond2)
00195 && GET_CODE (cond1) == reversed_comparison_code (cond2, NULL)
00196 && XEXP (cond1, 0) == XEXP (cond2, 0)
00197 && XEXP (cond1, 1) == XEXP (cond2, 1))
00198 return 1;
00199 return 0;
00200 }
00201
00202
00203
00204 bool
00205 sched_insns_conditions_mutex_p (rtx insn1, rtx insn2)
00206 {
00207 rtx cond1, cond2;
00208
00209
00210
00211 if (!CALL_P (insn1) && !CALL_P (insn2))
00212 {
00213 cond1 = sched_get_condition (insn1);
00214 cond2 = sched_get_condition (insn2);
00215 if (cond1 && cond2
00216 && conditions_mutex_p (cond1, cond2)
00217
00218
00219 && !modified_in_p (cond1, insn2)
00220
00221
00222 && !modified_in_p (cond2, insn1))
00223 return true;
00224 }
00225 return false;
00226 }
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240 static enum DEPS_ADJUST_RESULT
00241 maybe_add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
00242 ds_t ds, rtx mem1, rtx mem2,
00243 rtx **changed_linkpp)
00244 {
00245 gcc_assert (INSN_P (insn) && INSN_P (elem));
00246
00247
00248 if (insn == elem)
00249 {
00250 #ifdef INSN_SCHEDULING
00251 if (current_sched_info->flags & DO_SPECULATION)
00252
00253 HAS_INTERNAL_DEP (insn) = 1;
00254 #endif
00255 return 0;
00256 }
00257
00258 return add_or_update_back_dep_1 (insn, elem, dep_type,
00259 ds, mem1, mem2, changed_linkpp);
00260 }
00261
00262
00263
00264
00265
00266 static enum DEPS_ADJUST_RESULT
00267 add_or_update_back_dep_1 (rtx insn, rtx elem, enum reg_note dep_type,
00268 ds_t ds ATTRIBUTE_UNUSED,
00269 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED,
00270 rtx **changed_linkpp ATTRIBUTE_UNUSED)
00271 {
00272 bool maybe_present_p = true, present_p = false;
00273
00274 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
00275
00276 #ifdef INSN_SCHEDULING
00277
00278 #ifdef ENABLE_CHECKING
00279 check_dep_status (dep_type, ds, mem1 != NULL);
00280 #endif
00281
00282
00283
00284
00285 if (true_dependency_cache != NULL)
00286 {
00287 enum reg_note present_dep_type;
00288
00289 gcc_assert (output_dependency_cache);
00290 gcc_assert (anti_dependency_cache);
00291 if (!(current_sched_info->flags & USE_DEPS_LIST))
00292 {
00293 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
00294 INSN_LUID (elem)))
00295 present_dep_type = REG_DEP_TRUE;
00296 else if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
00297 INSN_LUID (elem)))
00298 present_dep_type = REG_DEP_OUTPUT;
00299 else if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
00300 INSN_LUID (elem)))
00301 present_dep_type = REG_DEP_ANTI;
00302 else
00303 maybe_present_p = false;
00304
00305 if (maybe_present_p)
00306 {
00307 if ((int) dep_type >= (int) present_dep_type)
00308 return DEP_PRESENT;
00309
00310 present_p = true;
00311 }
00312 }
00313 else
00314 {
00315 ds_t present_dep_types = 0;
00316
00317 if (bitmap_bit_p (&true_dependency_cache[INSN_LUID (insn)],
00318 INSN_LUID (elem)))
00319 present_dep_types |= DEP_TRUE;
00320 if (bitmap_bit_p (&output_dependency_cache[INSN_LUID (insn)],
00321 INSN_LUID (elem)))
00322 present_dep_types |= DEP_OUTPUT;
00323 if (bitmap_bit_p (&anti_dependency_cache[INSN_LUID (insn)],
00324 INSN_LUID (elem)))
00325 present_dep_types |= DEP_ANTI;
00326
00327 if (present_dep_types)
00328 {
00329 if (!(current_sched_info->flags & DO_SPECULATION)
00330 || !bitmap_bit_p (&spec_dependency_cache[INSN_LUID (insn)],
00331 INSN_LUID (elem)))
00332 {
00333 if ((present_dep_types | (ds & DEP_TYPES))
00334 == present_dep_types)
00335
00336 return DEP_PRESENT;
00337 }
00338 else
00339 {
00340
00341
00342 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI))
00343 == present_dep_types);
00344
00345
00346
00347
00348
00349 }
00350
00351 present_p = true;
00352 }
00353 else
00354 maybe_present_p = false;
00355 }
00356 }
00357 #endif
00358
00359
00360 if (maybe_present_p)
00361 {
00362 rtx *linkp;
00363
00364 for (linkp = &LOG_LINKS (insn); *linkp; linkp = &XEXP (*linkp, 1))
00365 {
00366 rtx link = *linkp;
00367
00368 gcc_assert (true_dependency_cache == 0 || present_p);
00369
00370 if (XEXP (link, 0) == elem)
00371 {
00372 enum DEPS_ADJUST_RESULT changed_p = DEP_PRESENT;
00373
00374 #ifdef INSN_SCHEDULING
00375 if (current_sched_info->flags & USE_DEPS_LIST)
00376 {
00377 ds_t new_status = ds | DEP_STATUS (link);
00378
00379 if (new_status & SPECULATIVE)
00380 {
00381 if (!(ds & SPECULATIVE)
00382 || !(DEP_STATUS (link) & SPECULATIVE))
00383
00384 {
00385 new_status &= ~SPECULATIVE;
00386 if (true_dependency_cache
00387 && (DEP_STATUS (link) & SPECULATIVE))
00388 bitmap_clear_bit (&spec_dependency_cache
00389 [INSN_LUID (insn)],
00390 INSN_LUID (elem));
00391 }
00392 else
00393 {
00394
00395 if (mem1)
00396 {
00397 dw_t dw;
00398
00399 dw = estimate_dep_weak (mem1, mem2);
00400 ds = set_dep_weak (ds, BEGIN_DATA, dw);
00401 }
00402
00403 new_status = ds_merge (DEP_STATUS (link), ds);
00404 }
00405 }
00406
00407 ds = new_status;
00408 }
00409
00410
00411
00412 if (true_dependency_cache != NULL
00413 && !(current_sched_info->flags & USE_DEPS_LIST))
00414 {
00415 enum reg_note kind = REG_NOTE_KIND (link);
00416
00417 switch (kind)
00418 {
00419 case REG_DEP_OUTPUT:
00420 bitmap_clear_bit (&output_dependency_cache
00421 [INSN_LUID (insn)], INSN_LUID (elem));
00422 break;
00423 case REG_DEP_ANTI:
00424 bitmap_clear_bit (&anti_dependency_cache
00425 [INSN_LUID (insn)], INSN_LUID (elem));
00426 break;
00427 default:
00428 gcc_unreachable ();
00429 }
00430 }
00431
00432 if ((current_sched_info->flags & USE_DEPS_LIST)
00433 && DEP_STATUS (link) != ds)
00434 {
00435 DEP_STATUS (link) = ds;
00436 changed_p = DEP_CHANGED;
00437 }
00438 #endif
00439
00440
00441
00442
00443 if ((int) dep_type < (int) REG_NOTE_KIND (link))
00444 {
00445 PUT_REG_NOTE_KIND (link, dep_type);
00446 changed_p = DEP_CHANGED;
00447 }
00448
00449 #ifdef INSN_SCHEDULING
00450
00451
00452 if (true_dependency_cache != NULL)
00453 {
00454 if (!(current_sched_info->flags & USE_DEPS_LIST))
00455 {
00456 if (REG_NOTE_KIND (link) == REG_DEP_TRUE)
00457 bitmap_set_bit (&true_dependency_cache
00458 [INSN_LUID (insn)], INSN_LUID (elem));
00459 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
00460 bitmap_set_bit (&output_dependency_cache
00461 [INSN_LUID (insn)], INSN_LUID (elem));
00462 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
00463 bitmap_set_bit (&anti_dependency_cache
00464 [INSN_LUID (insn)], INSN_LUID (elem));
00465 }
00466 else
00467 {
00468 if (ds & DEP_TRUE)
00469 bitmap_set_bit (&true_dependency_cache
00470 [INSN_LUID (insn)], INSN_LUID (elem));
00471 if (ds & DEP_OUTPUT)
00472 bitmap_set_bit (&output_dependency_cache
00473 [INSN_LUID (insn)], INSN_LUID (elem));
00474 if (ds & DEP_ANTI)
00475 bitmap_set_bit (&anti_dependency_cache
00476 [INSN_LUID (insn)], INSN_LUID (elem));
00477
00478
00479
00480 }
00481 }
00482
00483 if (changed_linkpp && changed_p == DEP_CHANGED)
00484 *changed_linkpp = linkp;
00485 #endif
00486 return changed_p;
00487 }
00488 }
00489
00490 gcc_assert (!present_p);
00491 }
00492
00493
00494
00495
00496
00497
00498 if (mem1)
00499 {
00500 gcc_assert (current_sched_info->flags & DO_SPECULATION);
00501 ds = set_dep_weak (ds, BEGIN_DATA, estimate_dep_weak (mem1, mem2));
00502 }
00503
00504 add_back_dep (insn, elem, dep_type, ds);
00505
00506 return DEP_CREATED;
00507 }
00508
00509
00510
00511 static void
00512 add_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
00513 {
00514 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
00515
00516 if (current_sched_info->flags & USE_DEPS_LIST)
00517 LOG_LINKS (insn) = alloc_DEPS_LIST (elem, LOG_LINKS (insn), ds);
00518 else
00519 LOG_LINKS (insn) = alloc_INSN_LIST (elem, LOG_LINKS (insn));
00520
00521
00522 PUT_REG_NOTE_KIND (LOG_LINKS (insn), dep_type);
00523
00524 #ifdef INSN_SCHEDULING
00525 #ifdef ENABLE_CHECKING
00526 check_dep_status (dep_type, ds, false);
00527 #endif
00528
00529
00530
00531 if (true_dependency_cache != NULL)
00532 {
00533 if (!(current_sched_info->flags & USE_DEPS_LIST))
00534 {
00535 if (dep_type == REG_DEP_TRUE)
00536 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
00537 INSN_LUID (elem));
00538 else if (dep_type == REG_DEP_OUTPUT)
00539 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
00540 INSN_LUID (elem));
00541 else if (dep_type == REG_DEP_ANTI)
00542 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
00543 INSN_LUID (elem));
00544 }
00545 else
00546 {
00547 if (ds & DEP_TRUE)
00548 bitmap_set_bit (&true_dependency_cache[INSN_LUID (insn)],
00549 INSN_LUID (elem));
00550 if (ds & DEP_OUTPUT)
00551 bitmap_set_bit (&output_dependency_cache[INSN_LUID (insn)],
00552 INSN_LUID (elem));
00553 if (ds & DEP_ANTI)
00554 bitmap_set_bit (&anti_dependency_cache[INSN_LUID (insn)],
00555 INSN_LUID (elem));
00556 if (ds & SPECULATIVE)
00557 {
00558 gcc_assert (current_sched_info->flags & DO_SPECULATION);
00559 bitmap_set_bit (&spec_dependency_cache[INSN_LUID (insn)],
00560 INSN_LUID (elem));
00561 }
00562 }
00563 }
00564 #endif
00565 }
00566
00567
00568
00569 static void
00570 add_dependence_list (rtx insn, rtx list, int uncond, enum reg_note dep_type)
00571 {
00572 for (; list; list = XEXP (list, 1))
00573 {
00574 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
00575 add_dependence (insn, XEXP (list, 0), dep_type);
00576 }
00577 }
00578
00579
00580
00581 static void
00582 add_dependence_list_and_free (rtx insn, rtx *listp, int uncond,
00583 enum reg_note dep_type)
00584 {
00585 rtx list, next;
00586 for (list = *listp, *listp = NULL; list ; list = next)
00587 {
00588 next = XEXP (list, 1);
00589 if (uncond || ! sched_insns_conditions_mutex_p (insn, XEXP (list, 0)))
00590 add_dependence (insn, XEXP (list, 0), dep_type);
00591 free_INSN_LIST_node (list);
00592 }
00593 }
00594
00595
00596
00597 static void
00598 delete_all_dependences (rtx insn)
00599 {
00600
00601
00602 #ifdef INSN_SCHEDULING
00603 if (true_dependency_cache != NULL)
00604 {
00605 bitmap_clear (&true_dependency_cache[INSN_LUID (insn)]);
00606 bitmap_clear (&output_dependency_cache[INSN_LUID (insn)]);
00607 bitmap_clear (&anti_dependency_cache[INSN_LUID (insn)]);
00608
00609
00610 if (current_sched_info->flags & DO_SPECULATION)
00611 bitmap_clear (&spec_dependency_cache[INSN_LUID (insn)]);
00612 }
00613 #endif
00614
00615 if (!(current_sched_info->flags & USE_DEPS_LIST))
00616
00617
00618 free_INSN_LIST_list (&LOG_LINKS (insn));
00619 else
00620 free_DEPS_LIST_list (&LOG_LINKS (insn));
00621 }
00622
00623
00624
00625
00626
00627
00628
00629 static void
00630 fixup_sched_groups (rtx insn)
00631 {
00632 rtx link, prev_nonnote;
00633
00634 for (link = LOG_LINKS (insn); link ; link = XEXP (link, 1))
00635 {
00636 rtx i = insn;
00637 do
00638 {
00639 i = prev_nonnote_insn (i);
00640
00641 if (XEXP (link, 0) == i)
00642 goto next_link;
00643 } while (SCHED_GROUP_P (i));
00644 if (! sched_insns_conditions_mutex_p (i, XEXP (link, 0)))
00645 add_dependence (i, XEXP (link, 0), REG_NOTE_KIND (link));
00646 next_link:;
00647 }
00648
00649 delete_all_dependences (insn);
00650
00651 prev_nonnote = prev_nonnote_insn (insn);
00652 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote)
00653 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote))
00654 add_dependence (insn, prev_nonnote, REG_DEP_ANTI);
00655 }
00656
00657
00658
00659
00660
00661
00662
00663
00664
00665
00666
00667
00668
00669
00670
00671
00672 static void
00673 add_insn_mem_dependence (struct deps *deps, rtx *insn_list, rtx *mem_list,
00674 rtx insn, rtx mem)
00675 {
00676 rtx link;
00677
00678 link = alloc_INSN_LIST (insn, *insn_list);
00679 *insn_list = link;
00680
00681 if (current_sched_info->use_cselib)
00682 {
00683 mem = shallow_copy_rtx (mem);
00684 XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0));
00685 }
00686 link = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list);
00687 *mem_list = link;
00688
00689 deps->pending_lists_length++;
00690 }
00691
00692
00693
00694
00695
00696 static void
00697 flush_pending_lists (struct deps *deps, rtx insn, int for_read,
00698 int for_write)
00699 {
00700 if (for_write)
00701 {
00702 add_dependence_list_and_free (insn, &deps->pending_read_insns, 1,
00703 REG_DEP_ANTI);
00704 free_EXPR_LIST_list (&deps->pending_read_mems);
00705 }
00706
00707 add_dependence_list_and_free (insn, &deps->pending_write_insns, 1,
00708 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
00709 free_EXPR_LIST_list (&deps->pending_write_mems);
00710 deps->pending_lists_length = 0;
00711
00712 add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 1,
00713 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT);
00714 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX);
00715 deps->pending_flush_length = 1;
00716 }
00717
00718
00719
00720
00721
00722 static void
00723 sched_analyze_reg (struct deps *deps, int regno, enum machine_mode mode,
00724 enum rtx_code ref, rtx insn)
00725 {
00726
00727
00728 if (regno < FIRST_PSEUDO_REGISTER)
00729 {
00730 int i = hard_regno_nregs[regno][mode];
00731 if (ref == SET)
00732 {
00733 while (--i >= 0)
00734 SET_REGNO_REG_SET (reg_pending_sets, regno + i);
00735 }
00736 else if (ref == USE)
00737 {
00738 while (--i >= 0)
00739 SET_REGNO_REG_SET (reg_pending_uses, regno + i);
00740 }
00741 else
00742 {
00743 while (--i >= 0)
00744 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i);
00745 }
00746 }
00747
00748
00749
00750
00751 else if (regno >= deps->max_reg)
00752 {
00753 enum rtx_code code = GET_CODE (PATTERN (insn));
00754 gcc_assert (code == USE || code == CLOBBER);
00755 }
00756
00757 else
00758 {
00759 if (ref == SET)
00760 SET_REGNO_REG_SET (reg_pending_sets, regno);
00761 else if (ref == USE)
00762 SET_REGNO_REG_SET (reg_pending_uses, regno);
00763 else
00764 SET_REGNO_REG_SET (reg_pending_clobbers, regno);
00765
00766
00767
00768
00769 if (!reload_completed && get_reg_known_equiv_p (regno))
00770 {
00771 rtx t = get_reg_known_value (regno);
00772 if (MEM_P (t))
00773 sched_analyze_2 (deps, XEXP (t, 0), insn);
00774 }
00775
00776
00777
00778 if (REG_N_CALLS_CROSSED (regno) == 0)
00779 {
00780 if (ref == USE)
00781 deps->sched_before_next_call
00782 = alloc_INSN_LIST (insn, deps->sched_before_next_call);
00783 else
00784 add_dependence_list (insn, deps->last_function_call, 1,
00785 REG_DEP_ANTI);
00786 }
00787 }
00788 }
00789
00790
00791
00792
00793
00794 static void
00795 sched_analyze_1 (struct deps *deps, rtx x, rtx insn)
00796 {
00797 rtx dest = XEXP (x, 0);
00798 enum rtx_code code = GET_CODE (x);
00799
00800 if (dest == 0)
00801 return;
00802
00803 if (GET_CODE (dest) == PARALLEL)
00804 {
00805 int i;
00806
00807 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
00808 if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
00809 sched_analyze_1 (deps,
00810 gen_rtx_CLOBBER (VOIDmode,
00811 XEXP (XVECEXP (dest, 0, i), 0)),
00812 insn);
00813
00814 if (GET_CODE (x) == SET)
00815 sched_analyze_2 (deps, SET_SRC (x), insn);
00816 return;
00817 }
00818
00819 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG
00820 || GET_CODE (dest) == ZERO_EXTRACT)
00821 {
00822 if (GET_CODE (dest) == STRICT_LOW_PART
00823 || GET_CODE (dest) == ZERO_EXTRACT
00824 || df_read_modify_subreg_p (dest))
00825 {
00826
00827
00828
00829
00830
00831
00832 sched_analyze_2 (deps, XEXP (dest, 0), insn);
00833 }
00834 if (GET_CODE (dest) == ZERO_EXTRACT)
00835 {
00836
00837 sched_analyze_2 (deps, XEXP (dest, 1), insn);
00838 sched_analyze_2 (deps, XEXP (dest, 2), insn);
00839 }
00840 dest = XEXP (dest, 0);
00841 }
00842
00843 if (REG_P (dest))
00844 {
00845 int regno = REGNO (dest);
00846 enum machine_mode mode = GET_MODE (dest);
00847
00848 sched_analyze_reg (deps, regno, mode, code, insn);
00849
00850 #ifdef STACK_REGS
00851
00852 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
00853 {
00854
00855 if (regno != FIRST_STACK_REG)
00856 sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn);
00857 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
00858 }
00859 #endif
00860 }
00861 else if (MEM_P (dest))
00862 {
00863
00864 rtx t = dest;
00865
00866 if (current_sched_info->use_cselib)
00867 {
00868 t = shallow_copy_rtx (dest);
00869 cselib_lookup (XEXP (t, 0), Pmode, 1);
00870 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
00871 }
00872 t = canon_rtx (t);
00873
00874 if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH)
00875 {
00876
00877
00878
00879
00880
00881 flush_pending_lists (deps, insn, false, true);
00882 }
00883 else
00884 {
00885 rtx pending, pending_mem;
00886
00887 pending = deps->pending_read_insns;
00888 pending_mem = deps->pending_read_mems;
00889 while (pending)
00890 {
00891 if (anti_dependence (XEXP (pending_mem, 0), t)
00892 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
00893 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
00894
00895 pending = XEXP (pending, 1);
00896 pending_mem = XEXP (pending_mem, 1);
00897 }
00898
00899 pending = deps->pending_write_insns;
00900 pending_mem = deps->pending_write_mems;
00901 while (pending)
00902 {
00903 if (output_dependence (XEXP (pending_mem, 0), t)
00904 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
00905 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
00906
00907 pending = XEXP (pending, 1);
00908 pending_mem = XEXP (pending_mem, 1);
00909 }
00910
00911 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
00912 REG_DEP_ANTI);
00913
00914 add_insn_mem_dependence (deps, &deps->pending_write_insns,
00915 &deps->pending_write_mems, insn, dest);
00916 }
00917 sched_analyze_2 (deps, XEXP (dest, 0), insn);
00918 }
00919
00920
00921 if (GET_CODE (x) == SET)
00922 sched_analyze_2 (deps, SET_SRC (x), insn);
00923 }
00924
00925
00926
00927 static void
00928 sched_analyze_2 (struct deps *deps, rtx x, rtx insn)
00929 {
00930 int i;
00931 int j;
00932 enum rtx_code code;
00933 const char *fmt;
00934
00935 if (x == 0)
00936 return;
00937
00938 code = GET_CODE (x);
00939
00940 switch (code)
00941 {
00942 case CONST_INT:
00943 case CONST_DOUBLE:
00944 case CONST_VECTOR:
00945 case SYMBOL_REF:
00946 case CONST:
00947 case LABEL_REF:
00948
00949
00950
00951 return;
00952
00953 #ifdef HAVE_cc0
00954 case CC0:
00955
00956 SCHED_GROUP_P (insn) = 1;
00957
00958
00959 CANT_MOVE (prev_nonnote_insn (insn)) = 1;
00960 return;
00961 #endif
00962
00963 case REG:
00964 {
00965 int regno = REGNO (x);
00966 enum machine_mode mode = GET_MODE (x);
00967
00968 sched_analyze_reg (deps, regno, mode, USE, insn);
00969
00970 #ifdef STACK_REGS
00971
00972 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG)
00973 {
00974
00975 if (regno != FIRST_STACK_REG)
00976 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn);
00977 sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn);
00978 }
00979 #endif
00980 return;
00981 }
00982
00983 case MEM:
00984 {
00985
00986 rtx u;
00987 rtx pending, pending_mem;
00988 rtx t = x;
00989
00990 if (current_sched_info->use_cselib)
00991 {
00992 t = shallow_copy_rtx (t);
00993 cselib_lookup (XEXP (t, 0), Pmode, 1);
00994 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0));
00995 }
00996 t = canon_rtx (t);
00997 pending = deps->pending_read_insns;
00998 pending_mem = deps->pending_read_mems;
00999 while (pending)
01000 {
01001 if (read_dependence (XEXP (pending_mem, 0), t)
01002 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
01003 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI);
01004
01005 pending = XEXP (pending, 1);
01006 pending_mem = XEXP (pending_mem, 1);
01007 }
01008
01009 pending = deps->pending_write_insns;
01010 pending_mem = deps->pending_write_mems;
01011 while (pending)
01012 {
01013 if (true_dependence (XEXP (pending_mem, 0), VOIDmode,
01014 t, rtx_varies_p)
01015 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
01016 {
01017 if (current_sched_info->flags & DO_SPECULATION)
01018 maybe_add_or_update_back_dep_1 (insn, XEXP (pending, 0),
01019 REG_DEP_TRUE,
01020 BEGIN_DATA | DEP_TRUE,
01021 XEXP (pending_mem, 0), t, 0);
01022 else
01023 add_dependence (insn, XEXP (pending, 0), REG_DEP_TRUE);
01024 }
01025
01026 pending = XEXP (pending, 1);
01027 pending_mem = XEXP (pending_mem, 1);
01028 }
01029
01030 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1))
01031 if (! JUMP_P (XEXP (u, 0)) || deps_may_trap_p (x))
01032 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI);
01033
01034
01035
01036 add_insn_mem_dependence (deps, &deps->pending_read_insns,
01037 &deps->pending_read_mems, insn, x);
01038
01039
01040 sched_analyze_2 (deps, XEXP (x, 0), insn);
01041 return;
01042 }
01043
01044
01045 case TRAP_IF:
01046 flush_pending_lists (deps, insn, true, false);
01047 break;
01048
01049 case ASM_OPERANDS:
01050 case ASM_INPUT:
01051 case UNSPEC_VOLATILE:
01052 {
01053
01054
01055
01056
01057
01058
01059
01060 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
01061 reg_pending_barrier = TRUE_BARRIER;
01062
01063
01064
01065
01066
01067
01068 if (code == ASM_OPERANDS)
01069 {
01070 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
01071 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn);
01072 return;
01073 }
01074 break;
01075 }
01076
01077 case PRE_DEC:
01078 case POST_DEC:
01079 case PRE_INC:
01080 case POST_INC:
01081
01082
01083
01084
01085
01086
01087 sched_analyze_2 (deps, XEXP (x, 0), insn);
01088 sched_analyze_1 (deps, x, insn);
01089 return;
01090
01091 case POST_MODIFY:
01092 case PRE_MODIFY:
01093
01094 sched_analyze_2 (deps, XEXP (x, 0), insn);
01095 sched_analyze_2 (deps, XEXP (x, 1), insn);
01096 sched_analyze_1 (deps, x, insn);
01097 return;
01098
01099 default:
01100 break;
01101 }
01102
01103
01104 fmt = GET_RTX_FORMAT (code);
01105 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
01106 {
01107 if (fmt[i] == 'e')
01108 sched_analyze_2 (deps, XEXP (x, i), insn);
01109 else if (fmt[i] == 'E')
01110 for (j = 0; j < XVECLEN (x, i); j++)
01111 sched_analyze_2 (deps, XVECEXP (x, i, j), insn);
01112 }
01113 }
01114
01115
01116
01117 static void
01118 sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
01119 {
01120 RTX_CODE code = GET_CODE (x);
01121 rtx link;
01122 unsigned i;
01123 reg_set_iterator rsi;
01124
01125 if (code == COND_EXEC)
01126 {
01127 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn);
01128
01129
01130
01131 x = COND_EXEC_CODE (x);
01132 code = GET_CODE (x);
01133 }
01134 if (code == SET || code == CLOBBER)
01135 {
01136 sched_analyze_1 (deps, x, insn);
01137
01138
01139
01140
01141 if (code == CLOBBER)
01142 add_dependence_list (insn, deps->last_function_call, 1, REG_DEP_OUTPUT);
01143 }
01144 else if (code == PARALLEL)
01145 {
01146 for (i = XVECLEN (x, 0); i--;)
01147 {
01148 rtx sub = XVECEXP (x, 0, i);
01149 code = GET_CODE (sub);
01150
01151 if (code == COND_EXEC)
01152 {
01153 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn);
01154 sub = COND_EXEC_CODE (sub);
01155 code = GET_CODE (sub);
01156 }
01157 if (code == SET || code == CLOBBER)
01158 sched_analyze_1 (deps, sub, insn);
01159 else
01160 sched_analyze_2 (deps, sub, insn);
01161 }
01162 }
01163 else
01164 sched_analyze_2 (deps, x, insn);
01165
01166
01167 if (CALL_P (insn))
01168 {
01169 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
01170 {
01171 if (GET_CODE (XEXP (link, 0)) == CLOBBER)
01172 sched_analyze_1 (deps, XEXP (link, 0), insn);
01173 else
01174 sched_analyze_2 (deps, XEXP (link, 0), insn);
01175 }
01176 if (find_reg_note (insn, REG_SETJMP, NULL))
01177 reg_pending_barrier = MOVE_BARRIER;
01178 }
01179
01180 if (JUMP_P (insn))
01181 {
01182 rtx next;
01183 next = next_nonnote_insn (insn);
01184 if (next && BARRIER_P (next))
01185 reg_pending_barrier = TRUE_BARRIER;
01186 else
01187 {
01188 rtx pending, pending_mem;
01189 regset_head tmp_uses, tmp_sets;
01190 INIT_REG_SET (&tmp_uses);
01191 INIT_REG_SET (&tmp_sets);
01192
01193 (*current_sched_info->compute_jump_reg_dependencies)
01194 (insn, &deps->reg_conditional_sets, &tmp_uses, &tmp_sets);
01195
01196 EXECUTE_IF_SET_IN_REG_SET (&tmp_uses, 0, i, rsi)
01197 {
01198 struct deps_reg *reg_last = &deps->reg_last[i];
01199 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI);
01200 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI);
01201 reg_last->uses_length++;
01202 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
01203 }
01204 IOR_REG_SET (reg_pending_sets, &tmp_sets);
01205
01206 CLEAR_REG_SET (&tmp_uses);
01207 CLEAR_REG_SET (&tmp_sets);
01208
01209
01210
01211
01212
01213 pending = deps->pending_write_insns;
01214 pending_mem = deps->pending_write_mems;
01215 while (pending)
01216 {
01217 if (! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
01218 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
01219 pending = XEXP (pending, 1);
01220 pending_mem = XEXP (pending_mem, 1);
01221 }
01222
01223 pending = deps->pending_read_insns;
01224 pending_mem = deps->pending_read_mems;
01225 while (pending)
01226 {
01227 if (MEM_VOLATILE_P (XEXP (pending_mem, 0))
01228 && ! sched_insns_conditions_mutex_p (insn, XEXP (pending, 0)))
01229 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT);
01230 pending = XEXP (pending, 1);
01231 pending_mem = XEXP (pending_mem, 1);
01232 }
01233
01234 add_dependence_list (insn, deps->last_pending_memory_flush, 1,
01235 REG_DEP_ANTI);
01236 }
01237 }
01238
01239
01240
01241
01242
01243
01244
01245 if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn))
01246 || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn)))
01247 reg_pending_barrier = MOVE_BARRIER;
01248
01249
01250 if (reg_pending_barrier)
01251 {
01252
01253
01254 if (sched_get_condition (insn))
01255 {
01256 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
01257 {
01258 struct deps_reg *reg_last = &deps->reg_last[i];
01259 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
01260 add_dependence_list
01261 (insn, reg_last->sets, 0,
01262 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
01263 add_dependence_list
01264 (insn, reg_last->clobbers, 0,
01265 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
01266 }
01267 }
01268 else
01269 {
01270 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
01271 {
01272 struct deps_reg *reg_last = &deps->reg_last[i];
01273 add_dependence_list_and_free (insn, ®_last->uses, 0,
01274 REG_DEP_ANTI);
01275 add_dependence_list_and_free
01276 (insn, ®_last->sets, 0,
01277 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
01278 add_dependence_list_and_free
01279 (insn, ®_last->clobbers, 0,
01280 reg_pending_barrier == TRUE_BARRIER ? REG_DEP_TRUE : REG_DEP_ANTI);
01281 reg_last->uses_length = 0;
01282 reg_last->clobbers_length = 0;
01283 }
01284 }
01285
01286 for (i = 0; i < (unsigned)deps->max_reg; i++)
01287 {
01288 struct deps_reg *reg_last = &deps->reg_last[i];
01289 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
01290 SET_REGNO_REG_SET (&deps->reg_last_in_use, i);
01291 }
01292
01293 flush_pending_lists (deps, insn, true, true);
01294 CLEAR_REG_SET (&deps->reg_conditional_sets);
01295 reg_pending_barrier = NOT_A_BARRIER;
01296 }
01297 else
01298 {
01299
01300
01301 if (sched_get_condition (insn))
01302 {
01303 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
01304 {
01305 struct deps_reg *reg_last = &deps->reg_last[i];
01306 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
01307 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
01308 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
01309 reg_last->uses_length++;
01310 }
01311 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
01312 {
01313 struct deps_reg *reg_last = &deps->reg_last[i];
01314 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
01315 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
01316 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
01317 reg_last->clobbers_length++;
01318 }
01319 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
01320 {
01321 struct deps_reg *reg_last = &deps->reg_last[i];
01322 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
01323 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT);
01324 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
01325 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
01326 SET_REGNO_REG_SET (&deps->reg_conditional_sets, i);
01327 }
01328 }
01329 else
01330 {
01331 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi)
01332 {
01333 struct deps_reg *reg_last = &deps->reg_last[i];
01334 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE);
01335 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE);
01336 reg_last->uses_length++;
01337 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses);
01338 }
01339 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi)
01340 {
01341 struct deps_reg *reg_last = &deps->reg_last[i];
01342 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH
01343 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH)
01344 {
01345 add_dependence_list_and_free (insn, ®_last->sets, 0,
01346 REG_DEP_OUTPUT);
01347 add_dependence_list_and_free (insn, ®_last->uses, 0,
01348 REG_DEP_ANTI);
01349 add_dependence_list_and_free (insn, ®_last->clobbers, 0,
01350 REG_DEP_OUTPUT);
01351 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
01352 reg_last->clobbers_length = 0;
01353 reg_last->uses_length = 0;
01354 }
01355 else
01356 {
01357 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT);
01358 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI);
01359 }
01360 reg_last->clobbers_length++;
01361 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers);
01362 }
01363 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi)
01364 {
01365 struct deps_reg *reg_last = &deps->reg_last[i];
01366 add_dependence_list_and_free (insn, ®_last->sets, 0,
01367 REG_DEP_OUTPUT);
01368 add_dependence_list_and_free (insn, ®_last->clobbers, 0,
01369 REG_DEP_OUTPUT);
01370 add_dependence_list_and_free (insn, ®_last->uses, 0,
01371 REG_DEP_ANTI);
01372 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets);
01373 reg_last->uses_length = 0;
01374 reg_last->clobbers_length = 0;
01375 CLEAR_REGNO_REG_SET (&deps->reg_conditional_sets, i);
01376 }
01377 }
01378
01379 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses);
01380 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers);
01381 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets);
01382 }
01383 CLEAR_REG_SET (reg_pending_uses);
01384 CLEAR_REG_SET (reg_pending_clobbers);
01385 CLEAR_REG_SET (reg_pending_sets);
01386
01387
01388
01389
01390
01391 if (deps->libcall_block_tail_insn)
01392 {
01393 SCHED_GROUP_P (insn) = 1;
01394 CANT_MOVE (insn) = 1;
01395 }
01396
01397
01398
01399
01400
01401
01402
01403
01404
01405
01406 if (deps->in_post_call_group_p)
01407 {
01408 rtx tmp, set = single_set (insn);
01409 int src_regno, dest_regno;
01410
01411 if (set == NULL)
01412 goto end_call_group;
01413
01414 tmp = SET_DEST (set);
01415 if (GET_CODE (tmp) == SUBREG)
01416 tmp = SUBREG_REG (tmp);
01417 if (REG_P (tmp))
01418 dest_regno = REGNO (tmp);
01419 else
01420 goto end_call_group;
01421
01422 tmp = SET_SRC (set);
01423 if (GET_CODE (tmp) == SUBREG)
01424 tmp = SUBREG_REG (tmp);
01425 if ((GET_CODE (tmp) == PLUS
01426 || GET_CODE (tmp) == MINUS)
01427 && REG_P (XEXP (tmp, 0))
01428 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM
01429 && dest_regno == STACK_POINTER_REGNUM)
01430 src_regno = STACK_POINTER_REGNUM;
01431 else if (REG_P (tmp))
01432 src_regno = REGNO (tmp);
01433 else
01434 goto end_call_group;
01435
01436 if (src_regno < FIRST_PSEUDO_REGISTER
01437 || dest_regno < FIRST_PSEUDO_REGISTER)
01438 {
01439 if (deps->in_post_call_group_p == post_call_initial)
01440 deps->in_post_call_group_p = post_call;
01441
01442 SCHED_GROUP_P (insn) = 1;
01443 CANT_MOVE (insn) = 1;
01444 }
01445 else
01446 {
01447 end_call_group:
01448 deps->in_post_call_group_p = not_post_call;
01449 }
01450 }
01451
01452
01453 if (SCHED_GROUP_P (insn))
01454 fixup_sched_groups (insn);
01455 }
01456
01457
01458
01459
01460 void
01461 sched_analyze (struct deps *deps, rtx head, rtx tail)
01462 {
01463 rtx insn;
01464
01465 if (current_sched_info->use_cselib)
01466 cselib_init (true);
01467
01468
01469
01470
01471 if (! reload_completed && !LABEL_P (head))
01472 {
01473 insn = prev_nonnote_insn (head);
01474 if (insn && CALL_P (insn))
01475 deps->in_post_call_group_p = post_call_initial;
01476 }
01477 for (insn = head;; insn = NEXT_INSN (insn))
01478 {
01479 rtx link, end_seq, r0, set;
01480
01481 if (NONJUMP_INSN_P (insn) || JUMP_P (insn))
01482 {
01483
01484 free_INSN_LIST_list (&LOG_LINKS (insn));
01485
01486
01487
01488 if (JUMP_P (insn))
01489 {
01490
01491 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH)
01492 flush_pending_lists (deps, insn, true, true);
01493 else
01494 deps->last_pending_memory_flush
01495 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush);
01496 }
01497 sched_analyze_insn (deps, PATTERN (insn), insn);
01498 }
01499 else if (CALL_P (insn))
01500 {
01501 int i;
01502
01503 CANT_MOVE (insn) = 1;
01504
01505
01506 free_INSN_LIST_list (&LOG_LINKS (insn));
01507
01508 if (find_reg_note (insn, REG_SETJMP, NULL))
01509 {
01510
01511
01512 reg_pending_barrier = MOVE_BARRIER;
01513 }
01514 else
01515 {
01516 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
01517
01518 if (global_regs[i])
01519 {
01520 SET_REGNO_REG_SET (reg_pending_sets, i);
01521 SET_REGNO_REG_SET (reg_pending_uses, i);
01522 }
01523
01524
01525
01526
01527 else if (HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i])
01528 || TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
01529 SET_REGNO_REG_SET (reg_pending_clobbers, i);
01530
01531
01532
01533 else if (fixed_regs[i])
01534 SET_REGNO_REG_SET (reg_pending_uses, i);
01535
01536
01537
01538
01539
01540 else if (i == FRAME_POINTER_REGNUM
01541 || (i == HARD_FRAME_POINTER_REGNUM
01542 && (! reload_completed || frame_pointer_needed)))
01543 SET_REGNO_REG_SET (reg_pending_uses, i);
01544 }
01545
01546
01547
01548 add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1,
01549 REG_DEP_ANTI);
01550
01551 sched_analyze_insn (deps, PATTERN (insn), insn);
01552
01553
01554
01555
01556
01557 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn));
01558
01559
01560 free_INSN_LIST_list (&deps->last_function_call);
01561 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX);
01562
01563
01564
01565 if (! reload_completed)
01566 deps->in_post_call_group_p = post_call;
01567 }
01568
01569
01570
01571 if (NOTE_P (insn))
01572 gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
01573 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END);
01574
01575 if (current_sched_info->use_cselib)
01576 cselib_process_insn (insn);
01577
01578
01579
01580
01581
01582
01583
01584
01585
01586
01587
01588
01589 if (!reload_completed
01590
01591
01592 && deps->libcall_block_tail_insn == 0
01593
01594 && NONJUMP_INSN_P (insn)
01595 && GET_CODE (PATTERN (insn)) == CLOBBER
01596 && (r0 = XEXP (PATTERN (insn), 0), REG_P (r0))
01597 && REG_P (XEXP (PATTERN (insn), 0))
01598
01599 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
01600 && (end_seq = XEXP (link, 0)) != 0
01601
01602
01603
01604 && (set = single_set (end_seq)) != 0
01605 && SET_DEST (set) == r0 && SET_SRC (set) == r0
01606
01607
01608 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0
01609 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0)
01610 deps->libcall_block_tail_insn = XEXP (link, 0);
01611
01612
01613
01614 if (deps->libcall_block_tail_insn == insn)
01615 deps->libcall_block_tail_insn = 0;
01616
01617 if (insn == tail)
01618 {
01619 if (current_sched_info->use_cselib)
01620 cselib_finish ();
01621 return;
01622 }
01623 }
01624 gcc_unreachable ();
01625 }
01626
01627
01628
01629
01630
01631 void
01632 add_forw_dep (rtx to, rtx link)
01633 {
01634 rtx new_link, from;
01635
01636 from = XEXP (link, 0);
01637
01638 #ifdef ENABLE_CHECKING
01639
01640
01641
01642
01643
01644
01645 gcc_assert (INSN_P (from));
01646 gcc_assert (!INSN_DELETED_P (from));
01647 if (true_dependency_cache)
01648 {
01649 gcc_assert (!bitmap_bit_p (&forward_dependency_cache[INSN_LUID (from)],
01650 INSN_LUID (to)));
01651 bitmap_set_bit (&forward_dependency_cache[INSN_LUID (from)],
01652 INSN_LUID (to));
01653 }
01654 else
01655 gcc_assert (!find_insn_list (to, INSN_DEPEND (from)));
01656 #endif
01657
01658 if (!(current_sched_info->flags & USE_DEPS_LIST))
01659 new_link = alloc_INSN_LIST (to, INSN_DEPEND (from));
01660 else
01661 new_link = alloc_DEPS_LIST (to, INSN_DEPEND (from), DEP_STATUS (link));
01662
01663 PUT_REG_NOTE_KIND (new_link, REG_NOTE_KIND (link));
01664
01665 INSN_DEPEND (from) = new_link;
01666 INSN_DEP_COUNT (to) += 1;
01667 }
01668
01669
01670
01671
01672
01673 void
01674 compute_forward_dependences (rtx head, rtx tail)
01675 {
01676 rtx insn;
01677 rtx next_tail;
01678
01679 next_tail = NEXT_INSN (tail);
01680 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
01681 {
01682 rtx link;
01683
01684 if (! INSN_P (insn))
01685 continue;
01686
01687 if (current_sched_info->flags & DO_SPECULATION)
01688 {
01689 rtx new = 0, link, next;
01690
01691 for (link = LOG_LINKS (insn); link; link = next)
01692 {
01693 next = XEXP (link, 1);
01694 adjust_add_sorted_back_dep (insn, link, &new);
01695 }
01696
01697 LOG_LINKS (insn) = new;
01698 }
01699
01700 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
01701 add_forw_dep (insn, link);
01702 }
01703 }
01704
01705
01706
01707
01708 void
01709 init_deps (struct deps *deps)
01710 {
01711 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ());
01712
01713 deps->max_reg = max_reg;
01714 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg);
01715 INIT_REG_SET (&deps->reg_last_in_use);
01716 INIT_REG_SET (&deps->reg_conditional_sets);
01717
01718 deps->pending_read_insns = 0;
01719 deps->pending_read_mems = 0;
01720 deps->pending_write_insns = 0;
01721 deps->pending_write_mems = 0;
01722 deps->pending_lists_length = 0;
01723 deps->pending_flush_length = 0;
01724 deps->last_pending_memory_flush = 0;
01725 deps->last_function_call = 0;
01726 deps->sched_before_next_call = 0;
01727 deps->in_post_call_group_p = not_post_call;
01728 deps->libcall_block_tail_insn = 0;
01729 }
01730
01731
01732
01733 void
01734 free_deps (struct deps *deps)
01735 {
01736 unsigned i;
01737 reg_set_iterator rsi;
01738
01739 free_INSN_LIST_list (&deps->pending_read_insns);
01740 free_EXPR_LIST_list (&deps->pending_read_mems);
01741 free_INSN_LIST_list (&deps->pending_write_insns);
01742 free_EXPR_LIST_list (&deps->pending_write_mems);
01743 free_INSN_LIST_list (&deps->last_pending_memory_flush);
01744
01745
01746
01747
01748 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
01749 {
01750 struct deps_reg *reg_last = &deps->reg_last[i];
01751 if (reg_last->uses)
01752 free_INSN_LIST_list (®_last->uses);
01753 if (reg_last->sets)
01754 free_INSN_LIST_list (®_last->sets);
01755 if (reg_last->clobbers)
01756 free_INSN_LIST_list (®_last->clobbers);
01757 }
01758 CLEAR_REG_SET (&deps->reg_last_in_use);
01759 CLEAR_REG_SET (&deps->reg_conditional_sets);
01760
01761 free (deps->reg_last);
01762 }
01763
01764
01765
01766
01767
01768 void
01769 init_dependency_caches (int luid)
01770 {
01771
01772
01773
01774
01775
01776
01777 if (luid / n_basic_blocks > 100 * 5)
01778 {
01779 cache_size = 0;
01780 extend_dependency_caches (luid, true);
01781 }
01782 }
01783
01784
01785
01786 void
01787 extend_dependency_caches (int n, bool create_p)
01788 {
01789 if (create_p || true_dependency_cache)
01790 {
01791 int i, luid = cache_size + n;
01792
01793 true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache,
01794 luid);
01795 output_dependency_cache = XRESIZEVEC (bitmap_head,
01796 output_dependency_cache, luid);
01797 anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache,
01798 luid);
01799 #ifdef ENABLE_CHECKING
01800 forward_dependency_cache = XRESIZEVEC (bitmap_head,
01801 forward_dependency_cache, luid);
01802 #endif
01803 if (current_sched_info->flags & DO_SPECULATION)
01804 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache,
01805 luid);
01806
01807 for (i = cache_size; i < luid; i++)
01808 {
01809 bitmap_initialize (&true_dependency_cache[i], 0);
01810 bitmap_initialize (&output_dependency_cache[i], 0);
01811 bitmap_initialize (&anti_dependency_cache[i], 0);
01812 #ifdef ENABLE_CHECKING
01813 bitmap_initialize (&forward_dependency_cache[i], 0);
01814 #endif
01815 if (current_sched_info->flags & DO_SPECULATION)
01816 bitmap_initialize (&spec_dependency_cache[i], 0);
01817 }
01818 cache_size = luid;
01819 }
01820 }
01821
01822
01823
01824 void
01825 free_dependency_caches (void)
01826 {
01827 if (true_dependency_cache)
01828 {
01829 int i;
01830
01831 for (i = 0; i < cache_size; i++)
01832 {
01833 bitmap_clear (&true_dependency_cache[i]);
01834 bitmap_clear (&output_dependency_cache[i]);
01835 bitmap_clear (&anti_dependency_cache[i]);
01836 #ifdef ENABLE_CHECKING
01837 bitmap_clear (&forward_dependency_cache[i]);
01838 #endif
01839 if (current_sched_info->flags & DO_SPECULATION)
01840 bitmap_clear (&spec_dependency_cache[i]);
01841 }
01842 free (true_dependency_cache);
01843 true_dependency_cache = NULL;
01844 free (output_dependency_cache);
01845 output_dependency_cache = NULL;
01846 free (anti_dependency_cache);
01847 anti_dependency_cache = NULL;
01848 #ifdef ENABLE_CHECKING
01849 free (forward_dependency_cache);
01850 forward_dependency_cache = NULL;
01851 #endif
01852 if (current_sched_info->flags & DO_SPECULATION)
01853 {
01854 free (spec_dependency_cache);
01855 spec_dependency_cache = NULL;
01856 }
01857 }
01858 }
01859
01860
01861
01862
01863 void
01864 init_deps_global (void)
01865 {
01866 reg_pending_sets = ALLOC_REG_SET (®_obstack);
01867 reg_pending_clobbers = ALLOC_REG_SET (®_obstack);
01868 reg_pending_uses = ALLOC_REG_SET (®_obstack);
01869 reg_pending_barrier = NOT_A_BARRIER;
01870 }
01871
01872
01873
01874 void
01875 finish_deps_global (void)
01876 {
01877 FREE_REG_SET (reg_pending_sets);
01878 FREE_REG_SET (reg_pending_clobbers);
01879 FREE_REG_SET (reg_pending_uses);
01880 }
01881
01882
01883
01884 static void
01885 adjust_add_sorted_back_dep (rtx insn, rtx link, rtx *linkp)
01886 {
01887 gcc_assert (current_sched_info->flags & DO_SPECULATION);
01888
01889
01890
01891 if (HAS_INTERNAL_DEP (insn)
01892 && (DEP_STATUS (link) & SPECULATIVE))
01893 {
01894 DEP_STATUS (link) &= ~SPECULATIVE;
01895
01896 if (true_dependency_cache)
01897 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
01898 INSN_LUID (XEXP (link, 0)));
01899 }
01900
01901
01902
01903 if (DEP_STATUS (link) & SPECULATIVE)
01904 while (*linkp && !(DEP_STATUS (*linkp) & SPECULATIVE))
01905 linkp = &XEXP (*linkp, 1);
01906
01907 XEXP (link, 1) = *linkp;
01908 *linkp = link;
01909 }
01910
01911
01912
01913
01914 static void
01915 adjust_back_add_forw_dep (rtx insn, rtx *linkp)
01916 {
01917 rtx link;
01918
01919 gcc_assert (current_sched_info->flags & DO_SPECULATION);
01920
01921 link = *linkp;
01922 *linkp = XEXP (*linkp, 1);
01923
01924 adjust_add_sorted_back_dep (insn, link, &LOG_LINKS (insn));
01925 add_forw_dep (insn, link);
01926 }
01927
01928
01929 static void
01930 delete_forw_dep (rtx insn, rtx elem)
01931 {
01932 gcc_assert (current_sched_info->flags & DO_SPECULATION);
01933
01934 #ifdef ENABLE_CHECKING
01935 if (true_dependency_cache)
01936 bitmap_clear_bit (&forward_dependency_cache[INSN_LUID (elem)],
01937 INSN_LUID (insn));
01938 #endif
01939
01940 remove_free_DEPS_LIST_elem (insn, &INSN_DEPEND (elem));
01941 INSN_DEP_COUNT (insn)--;
01942 }
01943
01944
01945 static dw_t
01946 estimate_dep_weak (rtx mem1, rtx mem2)
01947 {
01948 rtx r1, r2;
01949
01950 if (mem1 == mem2)
01951
01952 return MIN_DEP_WEAK;
01953
01954 r1 = XEXP (mem1, 0);
01955 r2 = XEXP (mem2, 0);
01956
01957 if (r1 == r2
01958 || (REG_P (r1) && REG_P (r2)
01959 && REGNO (r1) == REGNO (r2)))
01960
01961 return MIN_DEP_WEAK;
01962 else if ((REG_P (r1) && !REG_P (r2))
01963 || (!REG_P (r1) && REG_P (r2)))
01964
01965
01966 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2;
01967 else
01968
01969 return UNCERTAIN_DEP_WEAK;
01970 }
01971
01972
01973
01974
01975 void
01976 add_dependence (rtx insn, rtx elem, enum reg_note dep_type)
01977 {
01978 ds_t ds;
01979
01980 if (dep_type == REG_DEP_TRUE)
01981 ds = DEP_TRUE;
01982 else if (dep_type == REG_DEP_OUTPUT)
01983 ds = DEP_OUTPUT;
01984 else if (dep_type == REG_DEP_ANTI)
01985 ds = DEP_ANTI;
01986 else
01987 gcc_unreachable ();
01988
01989 maybe_add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
01990 }
01991
01992
01993
01994
01995 enum DEPS_ADJUST_RESULT
01996 add_or_update_back_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
01997 {
01998 return add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, 0);
01999 }
02000
02001
02002
02003 void
02004 add_or_update_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type,
02005 ds_t ds)
02006 {
02007 enum DEPS_ADJUST_RESULT res;
02008 rtx *linkp;
02009
02010 res = add_or_update_back_dep_1 (insn, elem, dep_type, ds, 0, 0, &linkp);
02011
02012 if (res == DEP_CHANGED || res == DEP_CREATED)
02013 {
02014 if (res == DEP_CHANGED)
02015 delete_forw_dep (insn, elem);
02016 else if (res == DEP_CREATED)
02017 linkp = &LOG_LINKS (insn);
02018
02019 adjust_back_add_forw_dep (insn, linkp);
02020 }
02021 }
02022
02023
02024
02025 void
02026 add_back_forw_dep (rtx insn, rtx elem, enum reg_note dep_type, ds_t ds)
02027 {
02028 add_back_dep (insn, elem, dep_type, ds);
02029 adjust_back_add_forw_dep (insn, &LOG_LINKS (insn));
02030 }
02031
02032
02033 void
02034 delete_back_forw_dep (rtx insn, rtx elem)
02035 {
02036 gcc_assert (current_sched_info->flags & DO_SPECULATION);
02037
02038 if (true_dependency_cache != NULL)
02039 {
02040 bitmap_clear_bit (&true_dependency_cache[INSN_LUID (insn)],
02041 INSN_LUID (elem));
02042 bitmap_clear_bit (&anti_dependency_cache[INSN_LUID (insn)],
02043 INSN_LUID (elem));
02044 bitmap_clear_bit (&output_dependency_cache[INSN_LUID (insn)],
02045 INSN_LUID (elem));
02046 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)],
02047 INSN_LUID (elem));
02048 }
02049
02050 remove_free_DEPS_LIST_elem (elem, &LOG_LINKS (insn));
02051 delete_forw_dep (insn, elem);
02052 }
02053
02054
02055 dw_t
02056 get_dep_weak (ds_t ds, ds_t type)
02057 {
02058 ds = ds & type;
02059 switch (type)
02060 {
02061 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break;
02062 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break;
02063 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break;
02064 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break;
02065 default: gcc_unreachable ();
02066 }
02067
02068 gcc_assert (MIN_DEP_WEAK <= ds && ds <= MAX_DEP_WEAK);
02069 return (dw_t) ds;
02070 }
02071
02072
02073
02074 ds_t
02075 set_dep_weak (ds_t ds, ds_t type, dw_t dw)
02076 {
02077 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK);
02078
02079 ds &= ~type;
02080 switch (type)
02081 {
02082 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break;
02083 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break;
02084 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break;
02085 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break;
02086 default: gcc_unreachable ();
02087 }
02088 return ds;
02089 }
02090
02091
02092 ds_t
02093 ds_merge (ds_t ds1, ds_t ds2)
02094 {
02095 ds_t ds, t;
02096
02097 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE));
02098
02099 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES);
02100
02101 t = FIRST_SPEC_TYPE;
02102 do
02103 {
02104 if ((ds1 & t) && !(ds2 & t))
02105 ds |= ds1 & t;
02106 else if (!(ds1 & t) && (ds2 & t))
02107 ds |= ds2 & t;
02108 else if ((ds1 & t) && (ds2 & t))
02109 {
02110 ds_t dw;
02111
02112 dw = ((ds_t) get_dep_weak (ds1, t)) * ((ds_t) get_dep_weak (ds2, t));
02113 dw /= MAX_DEP_WEAK;
02114 if (dw < MIN_DEP_WEAK)
02115 dw = MIN_DEP_WEAK;
02116
02117 ds = set_dep_weak (ds, t, (dw_t) dw);
02118 }
02119
02120 if (t == LAST_SPEC_TYPE)
02121 break;
02122 t <<= SPEC_TYPE_SHIFT;
02123 }
02124 while (1);
02125
02126 return ds;
02127 }
02128
02129 #ifdef INSN_SCHEDULING
02130 #ifdef ENABLE_CHECKING
02131
02132
02133 static void
02134 check_dep_status (enum reg_note dt, ds_t ds, bool relaxed_p)
02135 {
02136
02137 if (dt == REG_DEP_TRUE)
02138 gcc_assert (ds & DEP_TRUE);
02139 else if (dt == REG_DEP_OUTPUT)
02140 gcc_assert ((ds & DEP_OUTPUT)
02141 && !(ds & DEP_TRUE));
02142 else
02143 gcc_assert ((dt == REG_DEP_ANTI)
02144 && (ds & DEP_ANTI)
02145 && !(ds & (DEP_OUTPUT | DEP_TRUE)));
02146
02147
02148 gcc_assert (!(ds & HARD_DEP));
02149
02150
02151
02152 if (!(current_sched_info->flags & DO_SPECULATION))
02153 gcc_assert (!(ds & SPECULATIVE));
02154 else if (ds & SPECULATIVE)
02155 {
02156 if (!relaxed_p)
02157 {
02158 ds_t type = FIRST_SPEC_TYPE;
02159
02160
02161 do
02162 {
02163 if (ds & type)
02164 get_dep_weak (ds, type);
02165
02166 if (type == LAST_SPEC_TYPE)
02167 break;
02168 type <<= SPEC_TYPE_SHIFT;
02169 }
02170 while (1);
02171 }
02172
02173 if (ds & BEGIN_SPEC)
02174 {
02175
02176 if (ds & BEGIN_DATA)
02177 gcc_assert (ds & DEP_TRUE);
02178
02179
02180
02181
02182 if (ds & BEGIN_CONTROL)
02183 gcc_assert (ds & DEP_ANTI);
02184 }
02185 else
02186 {
02187
02188 gcc_assert ((ds & DEP_TYPES) == DEP_TRUE);
02189 }
02190
02191
02192
02193 if (ds & DEP_TRUE)
02194 gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC));
02195
02196 gcc_assert (!(ds & DEP_OUTPUT));
02197 if (ds & DEP_ANTI)
02198 gcc_assert (ds & BEGIN_CONTROL);
02199 }
02200 }
02201 #endif
02202 #endif