From 21e4c9a8db052486c9baf381279d1725048a56f0 Mon Sep 17 00:00:00 2001 From: Bernd Schmidt Date: Thu, 1 Mar 2001 13:21:30 +0000 Subject: [PATCH] Avoid exponential runtime From-SVN: r40145 --- gcc/ChangeLog | 7 +++++++ gcc/haifa-sched.c | 39 ++++++++++++++++++++++----------------- gcc/sched-int.h | 4 ++++ 3 files changed, 33 insertions(+), 17 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index a14925e4d09..40a88ef46be 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2001-03-01 Bernd Schmidt + + * sched-int.h (struct haifa_insn_data): Add new member priority_known. + (INSN_PRIORITY_KNOWN): New accessor macro. + * haifa-sched.c (priority): Use it instead of testing priority against + zero. + 2001-02-28 DJ Delorie * config/m68k/m68k.h (MOVE_BY_PIECES_P): Avoid pushing bytes, diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c index b4053b5e90c..977b6ecd297 100644 --- a/gcc/haifa-sched.c +++ b/gcc/haifa-sched.c @@ -719,38 +719,43 @@ static int priority (insn) rtx insn; { - int this_priority; rtx link; if (! INSN_P (insn)) return 0; - if ((this_priority = INSN_PRIORITY (insn)) == 0) + if (! INSN_PRIORITY_KNOWN (insn)) { + int this_priority = 0; + if (INSN_DEPEND (insn) == 0) this_priority = insn_cost (insn, 0, 0); else - for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) - { - rtx next; - int next_priority; + { + for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) + { + rtx next; + int next_priority; - if (RTX_INTEGRATED_P (link)) - continue; + if (RTX_INTEGRATED_P (link)) + continue; - next = XEXP (link, 0); + next = XEXP (link, 0); - /* Critical path is meaningful in block boundaries only. */ - if (! (*current_sched_info->contributes_to_priority) (next, insn)) - continue; + /* Critical path is meaningful in block boundaries only. */ + if (! (*current_sched_info->contributes_to_priority) (next, insn)) + continue; - next_priority = insn_cost (insn, link, next) + priority (next); - if (next_priority > this_priority) - this_priority = next_priority; - } + next_priority = insn_cost (insn, link, next) + priority (next); + if (next_priority > this_priority) + this_priority = next_priority; + } + } INSN_PRIORITY (insn) = this_priority; + INSN_PRIORITY_KNOWN (insn) = 1; } - return this_priority; + + return INSN_PRIORITY (insn); } /* Macros and functions for keeping the priority queue sorted, and diff --git a/gcc/sched-int.h b/gcc/sched-int.h index 2a7eb6a0384..0eb2e668279 100644 --- a/gcc/sched-int.h +++ b/gcc/sched-int.h @@ -198,6 +198,9 @@ struct haifa_insn_data moved load insn and this one. */ unsigned int fed_by_spec_load : 1; unsigned int is_load_insn : 1; + + /* Nonzero if priority has been computed already. */ + unsigned int priority_known : 1; }; extern struct haifa_insn_data *h_i_d; @@ -209,6 +212,7 @@ extern struct haifa_insn_data *h_i_d; #define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) #define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) #define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) +#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) #define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) #define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units) #define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) -- 2.30.2