From b83e9eb71cb4a21b31f8f47782da821a5a0ddb32 Mon Sep 17 00:00:00 2001 From: Joel Brobecker Date: Wed, 9 Sep 2009 17:39:21 +0000 Subject: [PATCH] Avoid quadratic behavior when computing the value of a register. * frame.c (frame_stash): New static constant. (frame_stash_add, frame_stash_find, frame_stash_invalidate): New functions. (get_frame_id): Minor reformatting. Add the frame to the frame stash. (frame_find_by_id): Search the frame stash first before walking all frames starting from te current_frame. (reinit_frame_stash): Add call to frame_stash_invalidate (); --- gdb/ChangeLog | 11 +++++++++++ gdb/frame.c | 55 ++++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 63 insertions(+), 3 deletions(-) diff --git a/gdb/ChangeLog b/gdb/ChangeLog index 173b937412a..52d87232916 100644 --- a/gdb/ChangeLog +++ b/gdb/ChangeLog @@ -1,3 +1,14 @@ +2009-09-08 Joel Brobecker + + Avoid quadratic behavior when computing the value of a register. + * frame.c (frame_stash): New static constant. + (frame_stash_add, frame_stash_find, frame_stash_invalidate): + New functions. + (get_frame_id): Minor reformatting. Add the frame to the frame stash. + (frame_find_by_id): Search the frame stash first before walking all + frames starting from te current_frame. + (reinit_frame_stash): Add call to frame_stash_invalidate (); + 2009-09-08 Joel Brobecker * block.c (contained_in): Return zero for nested functions. diff --git a/gdb/frame.c b/gdb/frame.c index 67ef967dd98..9ca69bf6596 100644 --- a/gdb/frame.c +++ b/gdb/frame.c @@ -122,6 +122,40 @@ struct frame_info enum unwind_stop_reason stop_reason; }; +/* A frame stash used to speed up frame lookups. */ + +/* We currently only stash one frame at a time, as this seems to be + sufficient for now. */ +static struct frame_info *frame_stash = NULL; + +/* Add the following FRAME to the frame stash. */ + +static void +frame_stash_add (struct frame_info *frame) +{ + frame_stash = frame; +} + +/* Search the frame stash for an entry with the given frame ID. + If found, return that frame. Otherwise return NULL. */ + +static struct frame_info * +frame_stash_find (struct frame_id id) +{ + if (frame_stash && frame_id_eq (frame_stash->this_id.value, id)) + return frame_stash; + + return NULL; +} + +/* Invalidate the frame stash by removing all entries in it. */ + +static void +frame_stash_invalidate (void) +{ + frame_stash = NULL; +} + /* Flag to control debugging. */ int frame_debug; @@ -279,9 +313,8 @@ struct frame_id get_frame_id (struct frame_info *fi) { if (fi == NULL) - { - return null_frame_id; - } + return null_frame_id; + if (!fi->this_id.p) { if (frame_debug) @@ -300,6 +333,9 @@ get_frame_id (struct frame_info *fi) fprintf_unfiltered (gdb_stdlog, " }\n"); } } + + frame_stash_add (fi); + return fi->this_id.value; } @@ -514,6 +550,18 @@ frame_find_by_id (struct frame_id id) if (!frame_id_p (id)) return NULL; + /* Try using the frame stash first. Finding it there removes the need + to perform the search by looping over all frames, which can be very + CPU-intensive if the number of frames is very high (the loop is O(n) + and get_prev_frame performs a series of checks that are relatively + expensive). This optimization is particularly useful when this function + is called from another function (such as value_fetch_lazy, case + VALUE_LVAL (val) == lval_register) which already loops over all frames, + making the overall behavior O(n^2). */ + frame = frame_stash_find (id); + if (frame) + return frame; + for (frame = get_current_frame (); ; frame = prev_frame) { struct frame_id this = get_frame_id (frame); @@ -1285,6 +1333,7 @@ reinit_frame_cache (void) current_frame = NULL; /* Invalidate cache */ select_frame (NULL); + frame_stash_invalidate (); if (frame_debug) fprintf_unfiltered (gdb_stdlog, "{ reinit_frame_cache () }\n"); } -- 2.39.2