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
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135 #include "config.h"
00136 #include "system.h"
00137 #include "toplev.h"
00138 #include "rtl.h"
00139 #include "tm_p.h"
00140 #include "hard-reg-set.h"
00141 #include "basic-block.h"
00142 #include "regs.h"
00143 #include "function.h"
00144 #include "flags.h"
00145 #include "insn-config.h"
00146 #include "insn-attr.h"
00147 #include "except.h"
00148 #include "toplev.h"
00149 #include "recog.h"
00150 #include "sched-int.h"
00151 #include "target.h"
00152
00153 #ifdef INSN_SCHEDULING
00154
00155
00156
00157
00158
00159 static int issue_rate;
00160
00161
00162
00163
00164
00165 int insert_schedule_bubbles_p = 0;
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176 static int sched_verbose_param = 0;
00177 int sched_verbose = 0;
00178
00179
00180
00181 FILE *sched_dump = 0;
00182
00183
00184 static int old_max_uid;
00185
00186
00187
00188
00189 void
00190 fix_sched_param (param, val)
00191 const char *param, *val;
00192 {
00193 if (!strcmp (param, "verbose"))
00194 sched_verbose_param = atoi (val);
00195 else
00196 warning ("fix_sched_param: unknown param: %s", param);
00197 }
00198
00199 struct haifa_insn_data *h_i_d;
00200
00201 #define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note)
00202 #define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick)
00203
00204
00205
00206 static rtx *line_note_head;
00207
00208
00209
00210 static rtx note_list;
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256
00257
00258
00259
00260
00261
00262
00263
00264
00265 #define MAX_INSN_QUEUE_INDEX max_insn_queue_index_macro_value
00266
00267 static rtx *insn_queue;
00268 static int q_ptr = 0;
00269 static int q_size = 0;
00270 #define NEXT_Q(X) (((X)+1) & MAX_INSN_QUEUE_INDEX)
00271 #define NEXT_Q_AFTER(X, C) (((X)+C) & MAX_INSN_QUEUE_INDEX)
00272
00273
00274
00275 static int max_insn_queue_index_macro_value;
00276
00277
00278
00279 state_t curr_state;
00280
00281
00282
00283
00284 static size_t dfa_state_size;
00285
00286
00287
00288 static char *ready_try;
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298 struct ready_list
00299 {
00300 rtx *vec;
00301 int veclen;
00302 int first;
00303 int n_ready;
00304 };
00305
00306 static int may_trap_exp PARAMS ((rtx, int));
00307
00308
00309 #define CONST_BASED_ADDRESS_P(x) \
00310 (GET_CODE (x) == REG \
00311 || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \
00312 || (GET_CODE (x) == LO_SUM)) \
00313 && (CONSTANT_P (XEXP (x, 0)) \
00314 || CONSTANT_P (XEXP (x, 1)))))
00315
00316
00317
00318
00319 static int
00320 may_trap_exp (x, is_store)
00321 rtx x;
00322 int is_store;
00323 {
00324 enum rtx_code code;
00325
00326 if (x == 0)
00327 return TRAP_FREE;
00328 code = GET_CODE (x);
00329 if (is_store)
00330 {
00331 if (code == MEM && may_trap_p (x))
00332 return TRAP_RISKY;
00333 else
00334 return TRAP_FREE;
00335 }
00336 if (code == MEM)
00337 {
00338
00339 if (MEM_VOLATILE_P (x))
00340 return IRISKY;
00341
00342 if (!may_trap_p (x))
00343 return IFREE;
00344
00345 if (CONST_BASED_ADDRESS_P (XEXP (x, 0)))
00346 return PFREE_CANDIDATE;
00347
00348 return PRISKY_CANDIDATE;
00349 }
00350 else
00351 {
00352 const char *fmt;
00353 int i, insn_class = TRAP_FREE;
00354
00355
00356 if (may_trap_p (x))
00357 return TRAP_RISKY;
00358
00359 fmt = GET_RTX_FORMAT (code);
00360 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
00361 {
00362 if (fmt[i] == 'e')
00363 {
00364 int tmp_class = may_trap_exp (XEXP (x, i), is_store);
00365 insn_class = WORST_CLASS (insn_class, tmp_class);
00366 }
00367 else if (fmt[i] == 'E')
00368 {
00369 int j;
00370 for (j = 0; j < XVECLEN (x, i); j++)
00371 {
00372 int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store);
00373 insn_class = WORST_CLASS (insn_class, tmp_class);
00374 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
00375 break;
00376 }
00377 }
00378 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
00379 break;
00380 }
00381 return insn_class;
00382 }
00383 }
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394 int
00395 haifa_classify_insn (insn)
00396 rtx insn;
00397 {
00398 rtx pat = PATTERN (insn);
00399 int tmp_class = TRAP_FREE;
00400 int insn_class = TRAP_FREE;
00401 enum rtx_code code;
00402
00403 if (GET_CODE (pat) == PARALLEL)
00404 {
00405 int i, len = XVECLEN (pat, 0);
00406
00407 for (i = len - 1; i >= 0; i--)
00408 {
00409 code = GET_CODE (XVECEXP (pat, 0, i));
00410 switch (code)
00411 {
00412 case CLOBBER:
00413
00414 tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1);
00415 break;
00416 case SET:
00417
00418 tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1);
00419 if (tmp_class == TRAP_RISKY)
00420 break;
00421
00422 tmp_class
00423 = WORST_CLASS (tmp_class,
00424 may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)),
00425 0));
00426 break;
00427 case COND_EXEC:
00428 case TRAP_IF:
00429 tmp_class = TRAP_RISKY;
00430 break;
00431 default:
00432 ;
00433 }
00434 insn_class = WORST_CLASS (insn_class, tmp_class);
00435 if (insn_class == TRAP_RISKY || insn_class == IRISKY)
00436 break;
00437 }
00438 }
00439 else
00440 {
00441 code = GET_CODE (pat);
00442 switch (code)
00443 {
00444 case CLOBBER:
00445
00446 tmp_class = may_trap_exp (XEXP (pat, 0), 1);
00447 break;
00448 case SET:
00449
00450 tmp_class = may_trap_exp (SET_DEST (pat), 1);
00451 if (tmp_class == TRAP_RISKY)
00452 break;
00453
00454 tmp_class =
00455 WORST_CLASS (tmp_class,
00456 may_trap_exp (SET_SRC (pat), 0));
00457 break;
00458 case COND_EXEC:
00459 case TRAP_IF:
00460 tmp_class = TRAP_RISKY;
00461 break;
00462 default:;
00463 }
00464 insn_class = tmp_class;
00465 }
00466
00467 return insn_class;
00468 }
00469
00470
00471
00472
00473
00474 static unsigned int blockage_range PARAMS ((int, rtx));
00475 static void clear_units PARAMS ((void));
00476 static void schedule_unit PARAMS ((int, rtx, int));
00477 static int actual_hazard PARAMS ((int, rtx, int, int));
00478 static int potential_hazard PARAMS ((int, rtx, int));
00479
00480 static int priority PARAMS ((rtx));
00481 static int rank_for_schedule PARAMS ((const PTR, const PTR));
00482 static void swap_sort PARAMS ((rtx *, int));
00483 static void queue_insn PARAMS ((rtx, int));
00484 static void schedule_insn PARAMS ((rtx, struct ready_list *, int));
00485 static void find_insn_reg_weight PARAMS ((int));
00486 static void adjust_priority PARAMS ((rtx));
00487 static void advance_one_cycle PARAMS ((void));
00488
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512 static rtx unlink_other_notes PARAMS ((rtx, rtx));
00513 static rtx unlink_line_notes PARAMS ((rtx, rtx));
00514 static rtx reemit_notes PARAMS ((rtx, rtx));
00515
00516 static rtx *ready_lastpos PARAMS ((struct ready_list *));
00517 static void ready_sort PARAMS ((struct ready_list *));
00518 static rtx ready_remove_first PARAMS ((struct ready_list *));
00519
00520 static void queue_to_ready PARAMS ((struct ready_list *));
00521
00522 static void debug_ready_list PARAMS ((struct ready_list *));
00523
00524 static rtx move_insn1 PARAMS ((rtx, rtx));
00525 static rtx move_insn PARAMS ((rtx, rtx));
00526
00527
00528
00529 static rtx ready_element PARAMS ((struct ready_list *, int));
00530 static rtx ready_remove PARAMS ((struct ready_list *, int));
00531 static int max_issue PARAMS ((struct ready_list *, int *));
00532
00533 static rtx choose_ready PARAMS ((struct ready_list *));
00534
00535 #endif
00536
00537
00538 struct sched_info *current_sched_info;
00539
00540 #ifndef INSN_SCHEDULING
00541 void
00542 schedule_insns (dump_file)
00543 FILE *dump_file ATTRIBUTE_UNUSED;
00544 {
00545 }
00546 #else
00547
00548
00549
00550
00551
00552 static rtx last_scheduled_insn;
00553
00554
00555
00556
00557
00558
00559
00560
00561 #ifndef KEY
00562 HAIFA_INLINE
00563 #endif
00564 int
00565 insn_unit (insn)
00566 rtx insn;
00567 {
00568 int unit = INSN_UNIT (insn);
00569
00570 if (unit == 0)
00571 {
00572 recog_memoized (insn);
00573
00574
00575
00576
00577 if (INSN_CODE (insn) < 0)
00578 unit = -1;
00579 else
00580 {
00581 unit = function_units_used (insn);
00582
00583 if (unit >= 0)
00584 unit++;
00585 }
00586
00587
00588 if (FUNCTION_UNITS_SIZE < HOST_BITS_PER_SHORT
00589 || unit >= 0
00590 || (unit & ~((1 << (HOST_BITS_PER_SHORT - 1)) - 1)) == 0)
00591 INSN_UNIT (insn) = unit;
00592 }
00593 return (unit > 0 ? unit - 1 : unit);
00594 }
00595
00596
00597
00598
00599
00600
00601
00602
00603 HAIFA_INLINE static unsigned int
00604 blockage_range (unit, insn)
00605 int unit;
00606 rtx insn;
00607 {
00608 unsigned int blockage = INSN_BLOCKAGE (insn);
00609 unsigned int range;
00610
00611 if ((int) UNIT_BLOCKED (blockage) != unit + 1)
00612 {
00613 range = function_units[unit].blockage_range_function (insn);
00614
00615
00616 if (HOST_BITS_PER_INT >= UNIT_BITS + 2 * BLOCKAGE_BITS)
00617 INSN_BLOCKAGE (insn) = ENCODE_BLOCKAGE (unit + 1, range);
00618 }
00619 else
00620 range = BLOCKAGE_RANGE (blockage);
00621
00622 return range;
00623 }
00624
00625
00626
00627
00628
00629 #if FUNCTION_UNITS_SIZE
00630 static rtx unit_last_insn[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
00631 #else
00632 static rtx unit_last_insn[1];
00633 #endif
00634
00635
00636
00637
00638
00639 #if FUNCTION_UNITS_SIZE
00640 static int unit_tick[FUNCTION_UNITS_SIZE * MAX_MULTIPLICITY];
00641 #else
00642 static int unit_tick[1];
00643 #endif
00644
00645
00646
00647
00648 #if FUNCTION_UNITS_SIZE
00649 static int unit_n_insns[FUNCTION_UNITS_SIZE];
00650 #else
00651 static int unit_n_insns[1];
00652 #endif
00653
00654
00655
00656
00657
00658 rtx
00659 get_unit_last_insn (instance)
00660 int instance;
00661 {
00662 return unit_last_insn[instance];
00663 }
00664
00665
00666
00667 static void
00668 clear_units ()
00669 {
00670 memset ((char *) unit_last_insn, 0, sizeof (unit_last_insn));
00671 memset ((char *) unit_tick, 0, sizeof (unit_tick));
00672 memset ((char *) unit_n_insns, 0, sizeof (unit_n_insns));
00673 }
00674
00675
00676
00677
00678 #ifndef KEY
00679 HAIFA_INLINE
00680 #endif
00681 int
00682 insn_issue_delay (insn)
00683 rtx insn;
00684 {
00685 int i, delay = 0;
00686 int unit = insn_unit (insn);
00687
00688
00689
00690
00691
00692 if (unit >= 0)
00693 {
00694 if (function_units[unit].blockage_range_function &&
00695 function_units[unit].blockage_function)
00696 delay = function_units[unit].blockage_function (insn, insn);
00697 }
00698 else
00699 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
00700 if ((unit & 1) != 0 && function_units[i].blockage_range_function
00701 && function_units[i].blockage_function)
00702 delay = MAX (delay, function_units[i].blockage_function (insn, insn));
00703
00704 return delay;
00705 }
00706
00707
00708
00709
00710
00711
00712 #ifndef KEY
00713 HAIFA_INLINE
00714 #endif
00715 int
00716 actual_hazard_this_instance (unit, instance, insn, clock, cost)
00717 int unit, instance, clock, cost;
00718 rtx insn;
00719 {
00720 int tick = unit_tick[instance];
00721
00722 if (tick - clock > cost)
00723 {
00724
00725
00726
00727
00728
00729
00730
00731
00732
00733 if (function_units[unit].blockage_range_function)
00734 {
00735 if (function_units[unit].blockage_function)
00736 tick += (function_units[unit].blockage_function
00737 (unit_last_insn[instance], insn)
00738 - function_units[unit].max_blockage);
00739 else
00740 tick += ((int) MAX_BLOCKAGE_COST (blockage_range (unit, insn))
00741 - function_units[unit].max_blockage);
00742 }
00743 if (tick - clock > cost)
00744 cost = tick - clock;
00745 }
00746 return cost;
00747 }
00748
00749
00750
00751
00752
00753 HAIFA_INLINE static void
00754 schedule_unit (unit, insn, clock)
00755 int unit, clock;
00756 rtx insn;
00757 {
00758 int i;
00759
00760 if (unit >= 0)
00761 {
00762 int instance = unit;
00763 #if MAX_MULTIPLICITY > 1
00764
00765
00766 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
00767 {
00768 if (!actual_hazard_this_instance (unit, instance, insn, clock, 0))
00769 break;
00770 instance += FUNCTION_UNITS_SIZE;
00771 }
00772 #endif
00773 unit_last_insn[instance] = insn;
00774 unit_tick[instance] = (clock + function_units[unit].max_blockage);
00775 }
00776 else
00777 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
00778 if ((unit & 1) != 0)
00779 schedule_unit (i, insn, clock);
00780 }
00781
00782
00783
00784
00785
00786
00787 HAIFA_INLINE static int
00788 actual_hazard (unit, insn, clock, cost)
00789 int unit, clock, cost;
00790 rtx insn;
00791 {
00792 int i;
00793
00794 if (unit >= 0)
00795 {
00796
00797 int instance = unit;
00798 int best_cost = actual_hazard_this_instance (unit, instance, insn,
00799 clock, cost);
00800 #if MAX_MULTIPLICITY > 1
00801 int this_cost;
00802
00803 if (best_cost > cost)
00804 {
00805 for (i = function_units[unit].multiplicity - 1; i > 0; i--)
00806 {
00807 instance += FUNCTION_UNITS_SIZE;
00808 this_cost = actual_hazard_this_instance (unit, instance, insn,
00809 clock, cost);
00810 if (this_cost < best_cost)
00811 {
00812 best_cost = this_cost;
00813 if (this_cost <= cost)
00814 break;
00815 }
00816 }
00817 }
00818 #endif
00819 cost = MAX (cost, best_cost);
00820 }
00821 else
00822 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
00823 if ((unit & 1) != 0)
00824 cost = actual_hazard (i, insn, clock, cost);
00825
00826 return cost;
00827 }
00828
00829
00830
00831
00832
00833
00834
00835
00836
00837
00838 HAIFA_INLINE static int
00839 potential_hazard (unit, insn, cost)
00840 int unit, cost;
00841 rtx insn;
00842 {
00843 int i, ncost;
00844 unsigned int minb, maxb;
00845
00846 if (unit >= 0)
00847 {
00848 minb = maxb = function_units[unit].max_blockage;
00849 if (maxb > 1)
00850 {
00851 if (function_units[unit].blockage_range_function)
00852 {
00853 maxb = minb = blockage_range (unit, insn);
00854 maxb = MAX_BLOCKAGE_COST (maxb);
00855 minb = MIN_BLOCKAGE_COST (minb);
00856 }
00857
00858 if (maxb > 1)
00859 {
00860
00861
00862
00863
00864 ncost = minb * 0x40 + maxb;
00865 ncost *= (unit_n_insns[unit] - 1) * 0x1000 + unit;
00866 if (ncost > cost)
00867 cost = ncost;
00868 }
00869 }
00870 }
00871 else
00872 for (i = 0, unit = ~unit; unit; i++, unit >>= 1)
00873 if ((unit & 1) != 0)
00874 cost = potential_hazard (i, insn, cost);
00875
00876 return cost;
00877 }
00878
00879
00880
00881
00882
00883 #ifndef KEY
00884 HAIFA_INLINE
00885 #endif
00886 int
00887 insn_cost (insn, link, used)
00888 rtx insn, link, used;
00889 {
00890 int cost = INSN_COST (insn);
00891
00892 if (cost < 0)
00893 {
00894
00895
00896
00897
00898 if (recog_memoized (insn) < 0)
00899 {
00900 INSN_COST (insn) = 0;
00901 return 0;
00902 }
00903 else
00904 {
00905 if (targetm.sched.use_dfa_pipeline_interface
00906 && (*targetm.sched.use_dfa_pipeline_interface) ())
00907 cost = insn_default_latency (insn);
00908 else
00909 cost = result_ready_cost (insn);
00910
00911 if (cost < 0)
00912 cost = 0;
00913
00914 INSN_COST (insn) = cost;
00915 }
00916 }
00917
00918
00919 if (link == 0 || used == 0)
00920 return cost;
00921
00922
00923
00924
00925 if (recog_memoized (used) < 0)
00926 cost = 0;
00927 else
00928 {
00929 if (targetm.sched.use_dfa_pipeline_interface
00930 && (*targetm.sched.use_dfa_pipeline_interface) ())
00931 {
00932 if (INSN_CODE (insn) >= 0)
00933 {
00934 if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
00935 cost = 0;
00936 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
00937 {
00938 cost = (insn_default_latency (insn)
00939 - insn_default_latency (used));
00940 if (cost <= 0)
00941 cost = 1;
00942 }
00943 else if (bypass_p (insn))
00944 cost = insn_latency (insn, used);
00945 }
00946 }
00947
00948 if (targetm.sched.adjust_cost)
00949 cost = (*targetm.sched.adjust_cost) (used, link, insn, cost);
00950
00951 if (cost < 0)
00952 cost = 0;
00953 }
00954
00955 return cost;
00956 }
00957
00958
00959
00960 static int
00961 priority (insn)
00962 rtx insn;
00963 {
00964 rtx link;
00965
00966 if (! INSN_P (insn))
00967 return 0;
00968
00969 if (! INSN_PRIORITY_KNOWN (insn))
00970 {
00971 int this_priority = 0;
00972
00973 if (INSN_DEPEND (insn) == 0)
00974 this_priority = insn_cost (insn, 0, 0);
00975 else
00976 {
00977 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1))
00978 {
00979 rtx next;
00980 int next_priority;
00981
00982 if (RTX_INTEGRATED_P (link))
00983 continue;
00984
00985 next = XEXP (link, 0);
00986
00987
00988 if (! (*current_sched_info->contributes_to_priority) (next, insn))
00989 continue;
00990
00991 next_priority = insn_cost (insn, link, next) + priority (next);
00992 if (next_priority > this_priority)
00993 this_priority = next_priority;
00994 }
00995 }
00996 INSN_PRIORITY (insn) = this_priority;
00997 INSN_PRIORITY_KNOWN (insn) = 1;
00998 }
00999
01000 return INSN_PRIORITY (insn);
01001 }
01002
01003
01004
01005
01006 #define SCHED_SORT(READY, N_READY) \
01007 do { if ((N_READY) == 2) \
01008 swap_sort (READY, N_READY); \
01009 else if ((N_READY) > 2) \
01010 qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \
01011 while (0)
01012
01013
01014
01015
01016
01017 static int
01018 rank_for_schedule (x, y)
01019 const PTR x;
01020 const PTR y;
01021 {
01022 rtx tmp = *(const rtx *) y;
01023 rtx tmp2 = *(const rtx *) x;
01024 rtx link;
01025 int tmp_class, tmp2_class, depend_count1, depend_count2;
01026 int val, priority_val, weight_val, info_val;
01027
01028
01029 priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
01030 if (priority_val)
01031 return priority_val;
01032
01033
01034 if (!reload_completed &&
01035 (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2)))
01036 return (weight_val);
01037
01038 info_val = (*current_sched_info->rank) (tmp, tmp2);
01039 if (info_val)
01040 return info_val;
01041
01042
01043 if (last_scheduled_insn)
01044 {
01045
01046
01047
01048
01049
01050 link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn));
01051 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1)
01052 tmp_class = 3;
01053 else if (REG_NOTE_KIND (link) == 0)
01054 tmp_class = 1;
01055 else
01056 tmp_class = 2;
01057
01058 link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn));
01059 if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1)
01060 tmp2_class = 3;
01061 else if (REG_NOTE_KIND (link) == 0)
01062 tmp2_class = 1;
01063 else
01064 tmp2_class = 2;
01065
01066 if ((val = tmp2_class - tmp_class))
01067 return val;
01068 }
01069
01070
01071
01072
01073 depend_count1 = 0;
01074 for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1))
01075 depend_count1++;
01076
01077 depend_count2 = 0;
01078 for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1))
01079 depend_count2++;
01080
01081 val = depend_count2 - depend_count1;
01082 if (val)
01083 return val;
01084
01085
01086
01087
01088 return INSN_LUID (tmp) - INSN_LUID (tmp2);
01089 }
01090
01091
01092
01093 HAIFA_INLINE static void
01094 swap_sort (a, n)
01095 rtx *a;
01096 int n;
01097 {
01098 rtx insn = a[n - 1];
01099 int i = n - 2;
01100
01101 while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0)
01102 {
01103 a[i + 1] = a[i];
01104 i -= 1;
01105 }
01106 a[i + 1] = insn;
01107 }
01108
01109
01110
01111
01112
01113 HAIFA_INLINE static void
01114 queue_insn (insn, n_cycles)
01115 rtx insn;
01116 int n_cycles;
01117 {
01118 int next_q = NEXT_Q_AFTER (q_ptr, n_cycles);
01119 rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]);
01120 insn_queue[next_q] = link;
01121 q_size += 1;
01122
01123 if (sched_verbose >= 2)
01124 {
01125 fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ",
01126 (*current_sched_info->print_insn) (insn, 0));
01127
01128 fprintf (sched_dump, "queued for %d cycles.\n", n_cycles);
01129 }
01130 }
01131
01132
01133
01134
01135 HAIFA_INLINE static rtx *
01136 ready_lastpos (ready)
01137 struct ready_list *ready;
01138 {
01139 if (ready->n_ready == 0)
01140 abort ();
01141 return ready->vec + ready->first - ready->n_ready + 1;
01142 }
01143
01144
01145
01146
01147 #ifndef KEY
01148 HAIFA_INLINE
01149 #endif
01150 void
01151 ready_add (ready, insn)
01152 struct ready_list *ready;
01153 rtx insn;
01154 {
01155 if (ready->first == ready->n_ready)
01156 {
01157 memmove (ready->vec + ready->veclen - ready->n_ready,
01158 ready_lastpos (ready),
01159 ready->n_ready * sizeof (rtx));
01160 ready->first = ready->veclen - 1;
01161 }
01162 ready->vec[ready->first - ready->n_ready] = insn;
01163 ready->n_ready++;
01164 }
01165
01166
01167
01168
01169 HAIFA_INLINE static rtx
01170 ready_remove_first (ready)
01171 struct ready_list *ready;
01172 {
01173 rtx t;
01174 if (ready->n_ready == 0)
01175 abort ();
01176 t = ready->vec[ready->first--];
01177 ready->n_ready--;
01178
01179 if (ready->n_ready == 0)
01180 ready->first = ready->veclen - 1;
01181 return t;
01182 }
01183
01184
01185
01186
01187
01188
01189
01190
01191
01192 HAIFA_INLINE static rtx
01193 ready_element (ready, index)
01194 struct ready_list *ready;
01195 int index;
01196 {
01197 if (ready->n_ready == 0 || index >= ready->n_ready)
01198 abort ();
01199 return ready->vec[ready->first - index];
01200 }
01201
01202
01203
01204
01205
01206 HAIFA_INLINE static rtx
01207 ready_remove (ready, index)
01208 struct ready_list *ready;
01209 int index;
01210 {
01211 rtx t;
01212 int i;
01213
01214 if (index == 0)
01215 return ready_remove_first (ready);
01216 if (ready->n_ready == 0 || index >= ready->n_ready)
01217 abort ();
01218 t = ready->vec[ready->first - index];
01219 ready->n_ready--;
01220 for (i = index; i < ready->n_ready; i++)
01221 ready->vec[ready->first - i] = ready->vec[ready->first - i - 1];
01222 return t;
01223 }
01224
01225
01226
01227
01228
01229 HAIFA_INLINE static void
01230 ready_sort (ready)
01231 struct ready_list *ready;
01232 {
01233 rtx *first = ready_lastpos (ready);
01234 SCHED_SORT (first, ready->n_ready);
01235 }
01236
01237
01238
01239
01240
01241 HAIFA_INLINE static void
01242 adjust_priority (prev)
01243 rtx prev;
01244 {
01245
01246
01247
01248
01249
01250
01251
01252 if (targetm.sched.adjust_priority)
01253 INSN_PRIORITY (prev) =
01254 (*targetm.sched.adjust_priority) (prev, INSN_PRIORITY (prev));
01255 }
01256
01257
01258 HAIFA_INLINE static void
01259 advance_one_cycle ()
01260 {
01261 if (targetm.sched.use_dfa_pipeline_interface
01262 && (*targetm.sched.use_dfa_pipeline_interface) ())
01263 {
01264 if (targetm.sched.dfa_pre_cycle_insn)
01265 state_transition (curr_state,
01266 (*targetm.sched.dfa_pre_cycle_insn) ());
01267
01268 state_transition (curr_state, NULL);
01269
01270 if (targetm.sched.dfa_post_cycle_insn)
01271 state_transition (curr_state,
01272 (*targetm.sched.dfa_post_cycle_insn) ());
01273 }
01274 }
01275
01276
01277 static int last_clock_var;
01278
01279
01280
01281
01282
01283
01284 static void
01285 schedule_insn (insn, ready, clock)
01286 rtx insn;
01287 struct ready_list *ready;
01288 int clock;
01289 {
01290 rtx link;
01291 int unit = 0;
01292
01293 if (!targetm.sched.use_dfa_pipeline_interface
01294 || !(*targetm.sched.use_dfa_pipeline_interface) ())
01295 unit = insn_unit (insn);
01296
01297 if (targetm.sched.use_dfa_pipeline_interface
01298 && (*targetm.sched.use_dfa_pipeline_interface) ()
01299 && sched_verbose >= 1)
01300 {
01301 char buf[2048];
01302
01303 print_insn (buf, insn, 0);
01304 buf[40]=0;
01305 fprintf (sched_dump, ";;\t%3i--> %-40s:", clock, buf);
01306
01307 if (recog_memoized (insn) < 0)
01308 fprintf (sched_dump, "nothing");
01309 else
01310 print_reservation (sched_dump, insn);
01311 fputc ('\n', sched_dump);
01312 }
01313 else if (sched_verbose >= 2)
01314 {
01315 fprintf (sched_dump, ";;\t\t--> scheduling insn <<<%d>>> on unit ",
01316 INSN_UID (insn));
01317 insn_print_units (insn);
01318 fputc ('\n', sched_dump);
01319 }
01320
01321 if (!targetm.sched.use_dfa_pipeline_interface
01322 || !(*targetm.sched.use_dfa_pipeline_interface) ())
01323 {
01324 if (sched_verbose && unit == -1)
01325 visualize_no_unit (insn);
01326
01327
01328 if (MAX_BLOCKAGE > 1 || issue_rate > 1 || sched_verbose)
01329 schedule_unit (unit, insn, clock);
01330
01331 if (INSN_DEPEND (insn) == 0)
01332 return;
01333 }
01334
01335 for (link = INSN_DEPEND (insn); link != 0; link = XEXP (link, 1))
01336 {
01337 rtx next = XEXP (link, 0);
01338 int cost = insn_cost (insn, link, next);
01339
01340 INSN_TICK (next) = MAX (INSN_TICK (next), clock + cost);
01341
01342 if ((INSN_DEP_COUNT (next) -= 1) == 0)
01343 {
01344 int effective_cost = INSN_TICK (next) - clock;
01345
01346 if (! (*current_sched_info->new_ready) (next))
01347 continue;
01348
01349 if (sched_verbose >= 2)
01350 {
01351 fprintf (sched_dump, ";;\t\tdependences resolved: insn %s ",
01352 (*current_sched_info->print_insn) (next, 0));
01353
01354 if (effective_cost < 1)
01355 fprintf (sched_dump, "into ready\n");
01356 else
01357 fprintf (sched_dump, "into queue with cost=%d\n", effective_cost);
01358 }
01359
01360
01361
01362 adjust_priority (next);
01363 if (effective_cost < 1)
01364 ready_add (ready, next);
01365 else
01366 queue_insn (next, effective_cost);
01367 }
01368 }
01369
01370
01371
01372
01373
01374
01375 if (reload_completed && issue_rate > 1
01376 && GET_CODE (PATTERN (insn)) != USE
01377 && GET_CODE (PATTERN (insn)) != CLOBBER)
01378 {
01379 PUT_MODE (insn, clock > last_clock_var ? TImode : VOIDmode);
01380 last_clock_var = clock;
01381 }
01382 }
01383
01384
01385
01386
01387
01388
01389
01390 static rtx
01391 unlink_other_notes (insn, tail)
01392 rtx insn, tail;
01393 {
01394 rtx prev = PREV_INSN (insn);
01395
01396 while (insn != tail && GET_CODE (insn) == NOTE)
01397 {
01398 rtx next = NEXT_INSN (insn);
01399
01400 if (prev)
01401 NEXT_INSN (prev) = next;
01402 if (next)
01403 PREV_INSN (next) = prev;
01404
01405
01406 if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG
01407 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
01408 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG
01409 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END)
01410 {
01411
01412 PREV_INSN (insn) = note_list;
01413 if (note_list)
01414 NEXT_INSN (note_list) = insn;
01415 note_list = insn;
01416 }
01417
01418 insn = next;
01419 }
01420 return insn;
01421 }
01422
01423
01424
01425
01426 static rtx
01427 unlink_line_notes (insn, tail)
01428 rtx insn, tail;
01429 {
01430 rtx prev = PREV_INSN (insn);
01431
01432 while (insn != tail && GET_CODE (insn) == NOTE)
01433 {
01434 rtx next = NEXT_INSN (insn);
01435
01436 if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0)
01437 {
01438
01439 if (prev)
01440 NEXT_INSN (prev) = next;
01441 if (next)
01442 PREV_INSN (next) = prev;
01443
01444
01445 LINE_NOTE (insn) = insn;
01446 }
01447 else
01448 prev = insn;
01449
01450 insn = next;
01451 }
01452 return insn;
01453 }
01454
01455
01456
01457 void
01458 get_block_head_tail (b, headp, tailp)
01459 int b;
01460 rtx *headp;
01461 rtx *tailp;
01462 {
01463
01464 rtx head = BLOCK_HEAD (b);
01465 rtx tail = BLOCK_END (b);
01466
01467
01468
01469 while (head != tail)
01470 {
01471 if (GET_CODE (head) == NOTE)
01472 head = NEXT_INSN (head);
01473 else if (GET_CODE (tail) == NOTE)
01474 tail = PREV_INSN (tail);
01475 else if (GET_CODE (head) == CODE_LABEL)
01476 head = NEXT_INSN (head);
01477 else
01478 break;
01479 }
01480
01481 *headp = head;
01482 *tailp = tail;
01483 }
01484
01485
01486
01487 int
01488 no_real_insns_p (head, tail)
01489 rtx head, tail;
01490 {
01491 while (head != NEXT_INSN (tail))
01492 {
01493 if (GET_CODE (head) != NOTE && GET_CODE (head) != CODE_LABEL)
01494 return 0;
01495 head = NEXT_INSN (head);
01496 }
01497 return 1;
01498 }
01499
01500
01501
01502
01503
01504 void
01505 rm_line_notes (head, tail)
01506 rtx head, tail;
01507 {
01508 rtx next_tail;
01509 rtx insn;
01510
01511 next_tail = NEXT_INSN (tail);
01512 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
01513 {
01514 rtx prev;
01515
01516
01517
01518
01519 if (GET_CODE (insn) == NOTE)
01520 {
01521 prev = insn;
01522 insn = unlink_line_notes (insn, next_tail);
01523
01524 if (prev == tail)
01525 abort ();
01526 if (prev == head)
01527 abort ();
01528 if (insn == next_tail)
01529 abort ();
01530 }
01531 }
01532 }
01533
01534
01535
01536
01537 void
01538 save_line_notes (b, head, tail)
01539 int b;
01540 rtx head, tail;
01541 {
01542 rtx next_tail;
01543
01544
01545
01546
01547
01548
01549 rtx line = line_note_head[b];
01550 rtx insn;
01551
01552 next_tail = NEXT_INSN (tail);
01553
01554 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
01555 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
01556 line = insn;
01557 else
01558 LINE_NOTE (insn) = line;
01559 }
01560
01561
01562
01563
01564
01565 void
01566 restore_line_notes (head, tail)
01567 rtx head, tail;
01568 {
01569 rtx line, note, prev, new;
01570 int added_notes = 0;
01571 rtx next_tail, insn;
01572
01573 head = head;
01574 next_tail = NEXT_INSN (tail);
01575
01576
01577
01578
01579
01580
01581
01582 for (line = head; line; line = PREV_INSN (line))
01583 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
01584 break;
01585
01586
01587
01588 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
01589 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
01590 line = insn;
01591
01592
01593
01594
01595 else if (GET_CODE (insn) != NOTE
01596 && INSN_UID (insn) < old_max_uid
01597 && (note = LINE_NOTE (insn)) != 0
01598 && note != line
01599 && (line == 0
01600 || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line)
01601 || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line)))
01602 {
01603 line = note;
01604 prev = PREV_INSN (insn);
01605 if (LINE_NOTE (note))
01606 {
01607
01608 LINE_NOTE (note) = 0;
01609 PREV_INSN (note) = prev;
01610 NEXT_INSN (prev) = note;
01611 PREV_INSN (insn) = note;
01612 NEXT_INSN (note) = insn;
01613 }
01614 else
01615 {
01616 added_notes++;
01617 new = emit_note_after (NOTE_LINE_NUMBER (note), prev);
01618 NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note);
01619 RTX_INTEGRATED_P (new) = RTX_INTEGRATED_P (note);
01620 }
01621 }
01622 if (sched_verbose && added_notes)
01623 fprintf (sched_dump, ";; added %d line-number notes\n", added_notes);
01624 }
01625
01626
01627
01628
01629 void
01630 rm_redundant_line_notes ()
01631 {
01632 rtx line = 0;
01633 rtx insn = get_insns ();
01634 int active_insn = 0;
01635 int notes = 0;
01636
01637
01638
01639
01640 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
01641 if (GET_CODE (insn) == NOTE && NOTE_LINE_NUMBER (insn) > 0)
01642 {
01643
01644 if (active_insn == 0)
01645 {
01646 notes++;
01647 NOTE_SOURCE_FILE (insn) = 0;
01648 NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
01649 }
01650
01651 else if (line
01652 && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn)
01653 && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn))
01654 {
01655 notes++;
01656 NOTE_SOURCE_FILE (line) = 0;
01657 NOTE_LINE_NUMBER (line) = NOTE_INSN_DELETED;
01658 line = insn;
01659 }
01660 else
01661 line = insn;
01662 active_insn = 0;
01663 }
01664 else if (!((GET_CODE (insn) == NOTE
01665 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
01666 || (GET_CODE (insn) == INSN
01667 && (GET_CODE (PATTERN (insn)) == USE
01668 || GET_CODE (PATTERN (insn)) == CLOBBER))))
01669 active_insn++;
01670
01671 if (sched_verbose && notes)
01672 fprintf (sched_dump, ";; deleted %d line-number notes\n", notes);
01673 }
01674
01675
01676
01677
01678 void
01679 rm_other_notes (head, tail)
01680 rtx head;
01681 rtx tail;
01682 {
01683 rtx next_tail;
01684 rtx insn;
01685
01686 note_list = 0;
01687 if (head == tail && (! INSN_P (head)))
01688 return;
01689
01690 next_tail = NEXT_INSN (tail);
01691 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
01692 {
01693 rtx prev;
01694
01695
01696
01697
01698 if (GET_CODE (insn) == NOTE)
01699 {
01700 prev = insn;
01701
01702 insn = unlink_other_notes (insn, next_tail);
01703
01704 if (prev == tail)
01705 abort ();
01706 if (prev == head)
01707 abort ();
01708 if (insn == next_tail)
01709 abort ();
01710 }
01711 }
01712 }
01713
01714
01715
01716
01717
01718 static void
01719 find_insn_reg_weight (b)
01720 int b;
01721 {
01722 rtx insn, next_tail, head, tail;
01723
01724 get_block_head_tail (b, &head, &tail);
01725 next_tail = NEXT_INSN (tail);
01726
01727 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
01728 {
01729 int reg_weight = 0;
01730 rtx x;
01731
01732
01733 if (! INSN_P (insn))
01734 continue;
01735
01736
01737 x = PATTERN (insn);
01738 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
01739 && register_operand (SET_DEST (x), VOIDmode))
01740 reg_weight++;
01741 else if (GET_CODE (x) == PARALLEL)
01742 {
01743 int j;
01744 for (j = XVECLEN (x, 0) - 1; j >= 0; j--)
01745 {
01746 x = XVECEXP (PATTERN (insn), 0, j);
01747 if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
01748 && register_operand (SET_DEST (x), VOIDmode))
01749 reg_weight++;
01750 }
01751 }
01752
01753
01754 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
01755 {
01756 if (REG_NOTE_KIND (x) == REG_DEAD
01757 || REG_NOTE_KIND (x) == REG_UNUSED)
01758 reg_weight--;
01759 }
01760
01761 INSN_REG_WEIGHT (insn) = reg_weight;
01762 }
01763 }
01764
01765
01766 static int clock_var;
01767
01768
01769
01770 static void
01771 queue_to_ready (ready)
01772 struct ready_list *ready;
01773 {
01774 rtx insn;
01775 rtx link;
01776
01777 q_ptr = NEXT_Q (q_ptr);
01778
01779
01780
01781 for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1))
01782 {
01783 insn = XEXP (link, 0);
01784 q_size -= 1;
01785
01786 if (sched_verbose >= 2)
01787 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
01788 (*current_sched_info->print_insn) (insn, 0));
01789
01790 ready_add (ready, insn);
01791 if (sched_verbose >= 2)
01792 fprintf (sched_dump, "moving to ready without stalls\n");
01793 }
01794 insn_queue[q_ptr] = 0;
01795
01796
01797
01798 if (ready->n_ready == 0)
01799 {
01800 int stalls;
01801
01802 for (stalls = 1; stalls <= MAX_INSN_QUEUE_INDEX; stalls++)
01803 {
01804 if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]))
01805 {
01806 for (; link; link = XEXP (link, 1))
01807 {
01808 insn = XEXP (link, 0);
01809 q_size -= 1;
01810
01811 if (sched_verbose >= 2)
01812 fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ",
01813 (*current_sched_info->print_insn) (insn, 0));
01814
01815 ready_add (ready, insn);
01816 if (sched_verbose >= 2)
01817 fprintf (sched_dump, "moving to ready with %d stalls\n", stalls);
01818 }
01819 insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = 0;
01820
01821 advance_one_cycle ();
01822
01823 break;
01824 }
01825
01826 advance_one_cycle ();
01827 }
01828
01829 if ((!targetm.sched.use_dfa_pipeline_interface
01830 || !(*targetm.sched.use_dfa_pipeline_interface) ())
01831 && sched_verbose && stalls)
01832 visualize_stall_cycles (stalls);
01833
01834 q_ptr = NEXT_Q_AFTER (q_ptr, stalls);
01835 clock_var += stalls;
01836 }
01837 }
01838
01839
01840
01841 static void
01842 debug_ready_list (ready)
01843 struct ready_list *ready;
01844 {
01845 rtx *p;
01846 int i;
01847
01848 if (ready->n_ready == 0)
01849 {
01850 fprintf (sched_dump, "\n");
01851 return;
01852 }
01853
01854 p = ready_lastpos (ready);
01855 for (i = 0; i < ready->n_ready; i++)
01856 fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0));
01857 fprintf (sched_dump, "\n");
01858 }
01859
01860
01861
01862 static rtx
01863 move_insn1 (insn, last)
01864 rtx insn, last;
01865 {
01866 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
01867 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
01868
01869 NEXT_INSN (insn) = NEXT_INSN (last);
01870 PREV_INSN (NEXT_INSN (last)) = insn;
01871
01872 NEXT_INSN (last) = insn;
01873 PREV_INSN (insn) = last;
01874
01875 return insn;
01876 }
01877
01878
01879
01880
01881
01882
01883
01884
01885 static rtx
01886 reemit_notes (insn, last)
01887 rtx insn;
01888 rtx last;
01889 {
01890 rtx note, retval;
01891
01892 retval = last;
01893 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
01894 {
01895 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE)
01896 {
01897 enum insn_note note_type = INTVAL (XEXP (note, 0));
01898
01899 last = emit_note_before (note_type, last);
01900 remove_note (insn, note);
01901 note = XEXP (note, 1);
01902 if (note_type == NOTE_INSN_EH_REGION_BEG
01903 || note_type == NOTE_INSN_EH_REGION_END)
01904 NOTE_EH_HANDLER (last) = INTVAL (XEXP (note, 0));
01905 remove_note (insn, note);
01906 }
01907 }
01908 return retval;
01909 }
01910
01911
01912
01913
01914
01915
01916
01917 static rtx
01918 move_insn (insn, last)
01919 rtx insn, last;
01920 {
01921 rtx retval = NULL;
01922
01923
01924
01925 while (SCHED_GROUP_P (insn))
01926 {
01927 rtx prev = PREV_INSN (insn);
01928
01929
01930 move_insn1 (insn, last);
01931
01932
01933 if (retval == NULL_RTX)
01934 retval = reemit_notes (insn, insn);
01935 else
01936 reemit_notes (insn, insn);
01937
01938 SCHED_GROUP_P (insn) = 0;
01939 insn = prev;
01940 }
01941
01942
01943 move_insn1 (insn, last);
01944
01945
01946
01947 if (retval == NULL_RTX)
01948 retval = reemit_notes (insn, insn);
01949 else
01950 reemit_notes (insn, insn);
01951
01952 return retval;
01953 }
01954
01955
01956 struct choice_entry
01957 {
01958
01959 int index;
01960
01961 int rest;
01962
01963 int n;
01964
01965 state_t state;
01966 };
01967
01968
01969
01970 static struct choice_entry *choice_stack;
01971
01972
01973
01974
01975 static int cycle_issued_insns;
01976
01977
01978
01979
01980
01981
01982
01983
01984
01985
01986 static int max_lookahead_tries;
01987
01988
01989
01990
01991 static int cached_first_cycle_multipass_dfa_lookahead = 0;
01992
01993
01994
01995 static int cached_issue_rate = 0;
01996
01997
01998
01999
02000
02001
02002
02003
02004
02005 static int
02006 max_issue (ready, index)
02007 struct ready_list *ready;
02008 int *index;
02009 {
02010 int n, i, all, n_ready, best, delay, tries_num;
02011 struct choice_entry *top;
02012 rtx insn;
02013
02014 best = 0;
02015 memcpy (choice_stack->state, curr_state, dfa_state_size);
02016 top = choice_stack;
02017 top->rest = cached_first_cycle_multipass_dfa_lookahead;
02018 top->n = 0;
02019 n_ready = ready->n_ready;
02020 for (all = i = 0; i < n_ready; i++)
02021 if (!ready_try [i])
02022 all++;
02023 i = 0;
02024 tries_num = 0;
02025 for (;;)
02026 {
02027 if (top->rest == 0 || i >= n_ready)
02028 {
02029 if (top == choice_stack)
02030 break;
02031 if (best < top - choice_stack && ready_try [0])
02032 {
02033 best = top - choice_stack;
02034 *index = choice_stack [1].index;
02035 if (top->n == issue_rate - cycle_issued_insns || best == all)
02036 break;
02037 }
02038 i = top->index;
02039 ready_try [i] = 0;
02040 top--;
02041 memcpy (curr_state, top->state, dfa_state_size);
02042 }
02043 else if (!ready_try [i])
02044 {
02045 tries_num++;
02046 if (tries_num > max_lookahead_tries)
02047 break;
02048 insn = ready_element (ready, i);
02049 delay = state_transition (curr_state, insn);
02050 if (delay < 0)
02051 {
02052 if (state_dead_lock_p (curr_state))
02053 top->rest = 0;
02054 else
02055 top->rest--;
02056 n = top->n;
02057 if (memcmp (top->state, curr_state, dfa_state_size) != 0)
02058 n++;
02059 top++;
02060 top->rest = cached_first_cycle_multipass_dfa_lookahead;
02061 top->index = i;
02062 top->n = n;
02063 memcpy (top->state, curr_state, dfa_state_size);
02064 ready_try [i] = 1;
02065 i = -1;
02066 }
02067 }
02068 i++;
02069 }
02070 while (top != choice_stack)
02071 {
02072 ready_try [top->index] = 0;
02073 top--;
02074 }
02075 memcpy (curr_state, choice_stack->state, dfa_state_size);
02076 return best;
02077 }
02078
02079
02080
02081
02082
02083 static rtx
02084 choose_ready (ready)
02085 struct ready_list *ready;
02086 {
02087 int lookahead = 0;
02088
02089 if (targetm.sched.first_cycle_multipass_dfa_lookahead)
02090 lookahead = (*targetm.sched.first_cycle_multipass_dfa_lookahead) ();
02091 if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0)))
02092 return ready_remove_first (ready);
02093 else
02094 {
02095
02096 int index, i;
02097 rtx insn;
02098
02099 if (cached_first_cycle_multipass_dfa_lookahead != lookahead)
02100 {
02101 cached_first_cycle_multipass_dfa_lookahead = lookahead;
02102 max_lookahead_tries = 100;
02103 for (i = 0; i < issue_rate; i++)
02104 max_lookahead_tries *= lookahead;
02105 }
02106 insn = ready_element (ready, 0);
02107 if (INSN_CODE (insn) < 0)
02108 return ready_remove_first (ready);
02109 for (i = 1; i < ready->n_ready; i++)
02110 {
02111 insn = ready_element (ready, i);
02112 ready_try [i] = INSN_CODE (insn) < 0;
02113 }
02114 if (max_issue (ready, &index) == 0)
02115 return ready_remove_first (ready);
02116 else
02117 return ready_remove (ready, index);
02118 }
02119 }
02120
02121
02122
02123
02124 rtx
02125 sched_emit_insn (pat)
02126 rtx pat;
02127 {
02128 rtx insn = emit_insn_after (pat, last_scheduled_insn);
02129 last_scheduled_insn = insn;
02130 return insn;
02131 }
02132
02133
02134
02135
02136 void
02137 schedule_block (b, rgn_n_insns)
02138 int b;
02139 int rgn_n_insns;
02140 {
02141 struct ready_list ready;
02142 int i;
02143 int first_cycle_insn_p;
02144 int can_issue_more;
02145 state_t temp_state = NULL;
02146
02147
02148 rtx prev_head = current_sched_info->prev_head;
02149 rtx next_tail = current_sched_info->next_tail;
02150 rtx head = NEXT_INSN (prev_head);
02151 rtx tail = PREV_INSN (next_tail);
02152
02153
02154
02155
02156
02157
02158
02159
02160 if (head == tail && (! INSN_P (head)))
02161 abort ();
02162
02163
02164 if (sched_verbose)
02165 {
02166 fprintf (sched_dump, ";; ======================================================\n");
02167 fprintf (sched_dump,
02168 ";; -- basic block %d from %d to %d -- %s reload\n",
02169 b, INSN_UID (head), INSN_UID (tail),
02170 (reload_completed ? "after" : "before"));
02171 fprintf (sched_dump, ";; ======================================================\n");
02172 fprintf (sched_dump, "\n");
02173
02174 visualize_alloc ();
02175 init_block_visualization ();
02176 }
02177
02178 if (targetm.sched.use_dfa_pipeline_interface
02179 && (*targetm.sched.use_dfa_pipeline_interface) ())
02180 state_reset (curr_state);
02181 else
02182 clear_units ();
02183
02184
02185 ready.veclen = rgn_n_insns + 1 + issue_rate;
02186 ready.first = ready.veclen - 1;
02187 ready.vec = (rtx *) xmalloc (ready.veclen * sizeof (rtx));
02188 ready.n_ready = 0;
02189
02190 if (targetm.sched.use_dfa_pipeline_interface
02191 && (*targetm.sched.use_dfa_pipeline_interface) ())
02192 {
02193
02194 temp_state = alloca (dfa_state_size);
02195 ready_try = (char *) xmalloc ((rgn_n_insns + 1) * sizeof (char));
02196 memset (ready_try, 0, (rgn_n_insns + 1) * sizeof (char));
02197 choice_stack
02198 = (struct choice_entry *) xmalloc ((rgn_n_insns + 1)
02199 * sizeof (struct choice_entry));
02200 for (i = 0; i <= rgn_n_insns; i++)
02201 choice_stack[i].state = (state_t) xmalloc (dfa_state_size);
02202 }
02203
02204 (*current_sched_info->init_ready_list) (&ready);
02205
02206 if (targetm.sched.md_init)
02207 (*targetm.sched.md_init) (sched_dump, sched_verbose, ready.veclen);
02208
02209
02210 last_scheduled_insn = prev_head;
02211
02212
02213
02214 q_ptr = 0;
02215 q_size = 0;
02216
02217 if (!targetm.sched.use_dfa_pipeline_interface
02218 || !(*targetm.sched.use_dfa_pipeline_interface) ())
02219 max_insn_queue_index_macro_value = INSN_QUEUE_SIZE - 1;
02220 else
02221 max_insn_queue_index_macro_value = max_insn_queue_index;
02222
02223 insn_queue = (rtx *) alloca ((MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
02224 memset ((char *) insn_queue, 0, (MAX_INSN_QUEUE_INDEX + 1) * sizeof (rtx));
02225 last_clock_var = -1;
02226
02227
02228 clock_var = -1;
02229
02230
02231 while ((*current_sched_info->schedule_more_p) ())
02232 {
02233 clock_var++;
02234
02235 advance_one_cycle ();
02236
02237
02238
02239
02240
02241 queue_to_ready (&ready);
02242
02243 if (ready.n_ready == 0)
02244 abort ();
02245
02246 if (sched_verbose >= 2)
02247 {
02248 fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: ");
02249 debug_ready_list (&ready);
02250 }
02251
02252
02253 ready_sort (&ready);
02254
02255
02256
02257 if (targetm.sched.reorder)
02258 can_issue_more =
02259 (*targetm.sched.reorder) (sched_dump, sched_verbose,
02260 ready_lastpos (&ready),
02261 &ready.n_ready, clock_var);
02262 else
02263 can_issue_more = issue_rate;
02264
02265 first_cycle_insn_p = 1;
02266 cycle_issued_insns = 0;
02267 for (;;)
02268 {
02269 rtx insn;
02270 int cost;
02271
02272 if (sched_verbose >= 2)
02273 {
02274 fprintf (sched_dump, ";;\tReady list (t =%3d): ",
02275 clock_var);
02276 debug_ready_list (&ready);
02277 }
02278
02279 if (!targetm.sched.use_dfa_pipeline_interface
02280 || !(*targetm.sched.use_dfa_pipeline_interface) ())
02281 {
02282 if (ready.n_ready == 0 || !can_issue_more
02283 || !(*current_sched_info->schedule_more_p) ())
02284 break;
02285 insn = choose_ready (&ready);
02286 cost = actual_hazard (insn_unit (insn), insn, clock_var, 0);
02287 }
02288 else
02289 {
02290 if (ready.n_ready == 0 || !can_issue_more
02291 || state_dead_lock_p (curr_state)
02292 || !(*current_sched_info->schedule_more_p) ())
02293 break;
02294
02295
02296 insn = choose_ready (&ready);
02297
02298 memcpy (temp_state, curr_state, dfa_state_size);
02299 if (recog_memoized (insn) < 0)
02300 {
02301 if (!first_cycle_insn_p
02302 && (GET_CODE (PATTERN (insn)) == ASM_INPUT
02303 || asm_noperands (PATTERN (insn)) >= 0))
02304
02305
02306 cost = 1;
02307 else
02308
02309
02310
02311
02312 cost = 0;
02313 }
02314 else
02315 {
02316 cost = state_transition (temp_state, insn);
02317
02318 if (targetm.sched.first_cycle_multipass_dfa_lookahead
02319 && targetm.sched.dfa_bubble)
02320 {
02321 if (cost == 0)
02322 {
02323 int j;
02324 rtx bubble;
02325
02326 for (j = 0;
02327 (bubble = (*targetm.sched.dfa_bubble) (j))
02328 != NULL_RTX;
02329 j++)
02330 {
02331 memcpy (temp_state, curr_state, dfa_state_size);
02332
02333 if (state_transition (temp_state, bubble) < 0
02334 && state_transition (temp_state, insn) < 0)
02335 break;
02336 }
02337
02338 if (bubble != NULL_RTX)
02339 {
02340 if (insert_schedule_bubbles_p)
02341 {
02342 rtx copy;
02343
02344 copy = copy_rtx (PATTERN (bubble));
02345 emit_insn_after (copy, last_scheduled_insn);
02346 last_scheduled_insn
02347 = NEXT_INSN (last_scheduled_insn);
02348 INSN_CODE (last_scheduled_insn)
02349 = INSN_CODE (bubble);
02350
02351
02352
02353 PUT_MODE (last_scheduled_insn,
02354 (clock_var > last_clock_var
02355 ? clock_var - last_clock_var
02356 : VOIDmode));
02357 last_clock_var = clock_var;
02358
02359 if (sched_verbose >= 2)
02360 {
02361 fprintf (sched_dump,
02362 ";;\t\t--> scheduling bubble insn <<<%d>>>:reservation ",
02363 INSN_UID (last_scheduled_insn));
02364
02365 if (recog_memoized (last_scheduled_insn)
02366 < 0)
02367 fprintf (sched_dump, "nothing");
02368 else
02369 print_reservation
02370 (sched_dump, last_scheduled_insn);
02371
02372 fprintf (sched_dump, "\n");
02373 }
02374 }
02375 cost = -1;
02376 }
02377 }
02378 }
02379
02380 if (cost < 0)
02381 cost = 0;
02382 else if (cost == 0)
02383 cost = 1;
02384 }
02385 }
02386
02387
02388 if (cost >= 1)
02389 {
02390 queue_insn (insn, cost);
02391 continue;
02392 }
02393
02394 if (! (*current_sched_info->can_schedule_ready_p) (insn))
02395 goto next;
02396
02397 last_scheduled_insn = move_insn (insn, last_scheduled_insn);
02398
02399 if (targetm.sched.use_dfa_pipeline_interface
02400 && (*targetm.sched.use_dfa_pipeline_interface) ())
02401 {
02402 if (memcmp (curr_state, temp_state, dfa_state_size) != 0)
02403 cycle_issued_insns++;
02404 memcpy (curr_state, temp_state, dfa_state_size);
02405 }
02406
02407 if (targetm.sched.variable_issue)
02408 can_issue_more =
02409 (*targetm.sched.variable_issue) (sched_dump, sched_verbose,
02410 insn, can_issue_more);
02411
02412
02413 else if (GET_CODE (PATTERN (insn)) != USE
02414 && GET_CODE (PATTERN (insn)) != CLOBBER)
02415 can_issue_more--;
02416
02417 schedule_insn (insn, &ready, clock_var);
02418
02419 next:
02420 first_cycle_insn_p = 0;
02421
02422 if (targetm.sched.reorder2)
02423 {
02424
02425 if (ready.n_ready > 0)
02426 ready_sort (&ready);
02427 can_issue_more =
02428 (*targetm.sched.reorder2) (sched_dump,sched_verbose,
02429 ready.n_ready
02430 ? ready_lastpos (&ready) : NULL,
02431 &ready.n_ready, clock_var);
02432 }
02433 }
02434
02435 if ((!targetm.sched.use_dfa_pipeline_interface
02436 || !(*targetm.sched.use_dfa_pipeline_interface) ())
02437 && sched_verbose)
02438
02439 visualize_scheduled_insns (clock_var);
02440 }
02441
02442 if (targetm.sched.md_finish)
02443 (*targetm.sched.md_finish) (sched_dump, sched_verbose);
02444
02445
02446 if (sched_verbose)
02447 {
02448 fprintf (sched_dump, ";;\tReady list (final): ");
02449 debug_ready_list (&ready);
02450 if (!targetm.sched.use_dfa_pipeline_interface
02451 || !(*targetm.sched.use_dfa_pipeline_interface) ())
02452 print_block_visualization ("");
02453 }
02454
02455
02456
02457 if (current_sched_info->queue_must_finish_empty && q_size != 0)
02458 abort ();
02459
02460
02461 head = NEXT_INSN (prev_head);
02462 tail = last_scheduled_insn;
02463
02464
02465
02466
02467 if (note_list != 0)
02468 {
02469 rtx note_head = note_list;
02470
02471 while (PREV_INSN (note_head))
02472 {
02473 note_head = PREV_INSN (note_head);
02474 }
02475
02476 PREV_INSN (note_head) = PREV_INSN (head);
02477 NEXT_INSN (PREV_INSN (head)) = note_head;
02478 PREV_INSN (head) = note_list;
02479 NEXT_INSN (note_list) = head;
02480 head = note_head;
02481 }
02482
02483
02484 if (sched_verbose)
02485 {
02486 fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n",
02487 clock_var, INSN_UID (head));
02488 fprintf (sched_dump, ";; new tail = %d\n\n",
02489 INSN_UID (tail));
02490 visualize_free ();
02491 }
02492
02493 current_sched_info->head = head;
02494 current_sched_info->tail = tail;
02495
02496 free (ready.vec);
02497
02498 if (targetm.sched.use_dfa_pipeline_interface
02499 && (*targetm.sched.use_dfa_pipeline_interface) ())
02500 {
02501 free (ready_try);
02502 for (i = 0; i <= rgn_n_insns; i++)
02503 free (choice_stack [i].state);
02504 free (choice_stack);
02505 }
02506 }
02507
02508
02509
02510 int
02511 set_priorities (head, tail)
02512 rtx head, tail;
02513 {
02514 rtx insn;
02515 int n_insn;
02516
02517 rtx prev_head;
02518
02519 prev_head = PREV_INSN (head);
02520
02521 if (head == tail && (! INSN_P (head)))
02522 return 0;
02523
02524 n_insn = 0;
02525 for (insn = tail; insn != prev_head; insn = PREV_INSN (insn))
02526 {
02527 if (GET_CODE (insn) == NOTE)
02528 continue;
02529
02530 if (!(SCHED_GROUP_P (insn)))
02531 n_insn++;
02532 (void) priority (insn);
02533 }
02534
02535 return n_insn;
02536 }
02537
02538
02539
02540
02541 void
02542 sched_init (dump_file)
02543 FILE *dump_file;
02544 {
02545 int luid;
02546 basic_block b;
02547 rtx insn;
02548 int i;
02549
02550
02551 #ifdef HAVE_cc0
02552 flag_schedule_speculative_load = 0;
02553 #endif
02554
02555
02556
02557
02558 sched_verbose = sched_verbose_param;
02559 if (sched_verbose_param == 0 && dump_file)
02560 sched_verbose = 1;
02561 sched_dump = ((sched_verbose_param >= 10 || !dump_file)
02562 ? stderr : dump_file);
02563
02564
02565 if (targetm.sched.issue_rate)
02566 issue_rate = (*targetm.sched.issue_rate) ();
02567 else
02568 issue_rate = 1;
02569
02570 if (cached_issue_rate != issue_rate)
02571 {
02572 cached_issue_rate = issue_rate;
02573
02574 cached_first_cycle_multipass_dfa_lookahead = 0;
02575 }
02576
02577
02578
02579 old_max_uid = get_max_uid () + 1;
02580
02581 h_i_d = (struct haifa_insn_data *) xcalloc (old_max_uid, sizeof (*h_i_d));
02582
02583 for (i = 0; i < old_max_uid; i++)
02584 h_i_d [i].cost = -1;
02585
02586 if (targetm.sched.use_dfa_pipeline_interface
02587 && (*targetm.sched.use_dfa_pipeline_interface) ())
02588 {
02589 if (targetm.sched.init_dfa_pre_cycle_insn)
02590 (*targetm.sched.init_dfa_pre_cycle_insn) ();
02591
02592 if (targetm.sched.init_dfa_post_cycle_insn)
02593 (*targetm.sched.init_dfa_post_cycle_insn) ();
02594
02595 if (targetm.sched.first_cycle_multipass_dfa_lookahead
02596 && targetm.sched.init_dfa_bubbles)
02597 (*targetm.sched.init_dfa_bubbles) ();
02598
02599 dfa_start ();
02600 dfa_state_size = state_size ();
02601 curr_state = xmalloc (dfa_state_size);
02602 }
02603
02604 h_i_d[0].luid = 0;
02605 luid = 1;
02606 FOR_EACH_BB (b)
02607 for (insn = b->head;; insn = NEXT_INSN (insn))
02608 {
02609 INSN_LUID (insn) = luid;
02610
02611
02612
02613
02614
02615
02616 if (GET_CODE (insn) != NOTE)
02617 ++luid;
02618
02619 if (insn == b->end)
02620 break;
02621 }
02622
02623 init_dependency_caches (luid);
02624
02625 init_alias_analysis ();
02626
02627 if (write_symbols != NO_DEBUG)
02628 {
02629 rtx line;
02630
02631 line_note_head = (rtx *) xcalloc (last_basic_block, sizeof (rtx));
02632
02633
02634
02635
02636
02637
02638
02639 FOR_EACH_BB (b)
02640 {
02641 for (line = b->head; line; line = PREV_INSN (line))
02642 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
02643 {
02644 line_note_head[b->index] = line;
02645 break;
02646 }
02647
02648
02649 for (line = b->head; line; line = NEXT_INSN (line))
02650 {
02651 if (INSN_P (line))
02652 break;
02653 if (GET_CODE (line) == NOTE && NOTE_LINE_NUMBER (line) > 0)
02654 line_note_head[b->index] = line;
02655 }
02656 }
02657 }
02658
02659 if ((!targetm.sched.use_dfa_pipeline_interface
02660 || !(*targetm.sched.use_dfa_pipeline_interface) ())
02661 && sched_verbose)
02662
02663 init_target_units ();
02664
02665
02666
02667
02668 insn = EXIT_BLOCK_PTR->prev_bb->end;
02669 if (NEXT_INSN (insn) == 0
02670 || (GET_CODE (insn) != NOTE
02671 && GET_CODE (insn) != CODE_LABEL
02672
02673 && GET_CODE (NEXT_INSN (insn)) != BARRIER))
02674 {
02675 emit_note_after (NOTE_INSN_DELETED, EXIT_BLOCK_PTR->prev_bb->end);
02676
02677 EXIT_BLOCK_PTR->prev_bb->end = PREV_INSN (EXIT_BLOCK_PTR->prev_bb->end);
02678 }
02679
02680
02681
02682 FOR_EACH_BB_REVERSE (b)
02683 find_insn_reg_weight (b->index);
02684 }
02685
02686
02687
02688 void
02689 sched_finish ()
02690 {
02691 free (h_i_d);
02692
02693 if (targetm.sched.use_dfa_pipeline_interface
02694 && (*targetm.sched.use_dfa_pipeline_interface) ())
02695 {
02696 free (curr_state);
02697 dfa_finish ();
02698 }
02699 free_dependency_caches ();
02700 end_alias_analysis ();
02701 if (write_symbols != NO_DEBUG)
02702 free (line_note_head);
02703 }
02704 #endif