On Wed, 26 Aug 2020, Jakub Jelinek wrote:
> Hi!
>
> The addition of NOTE_INSN_BEGIN_STMT and NOTE_INSN_INLINE_ENTRY notes
> reintroduced quadratic behavior into dwarf2out_var_location.
> This function needs to know the next real instruction to which the var
> location note applies, but the way final_scan_insn is called outside of
> final.c main loop doesn't make it easy to look up the next real insn in
> there (and for non-dwarf it is even useless). Usually next real insn is
> only a few notes away, but we can have hundreds of thousands of consecutive
> notes only followed by a real insn. dwarf2out_var_location to avoid the
> quadratic behavior contains a cache, it remembers the next note and when it
> is called again on that loc_note, it can use the previously computed
> dwarf2out_next_real_insn result, rather than walking the insn chain once
> again. But, for NOTE_INSN_{BEGIN_STMT,INLINE_ENTRY} dwarf2out_var_location
> is not called while the code puts into the cache those notes, which means if
> we have e.g. in the worst case NOTE_INSN_VAR_LOCATION and
> NOTE_INSN_BEGIN_STMT notes alternating, the cache is not really used.
>
> The following patch fixes it by looking up the next NOTE_INSN_VAR_LOCATION
> if any. While the lookup could be perhaps done together with looking for
> the next real insn once (e.g. in dwarf2out_next_real_insn or its copy),
> there are other dwarf2out_next_real_insn callers which don't need/want that
> behavior and if there are more than two NOTE_INSN_VAR_LOCATION notes
> followed by the same real insn, we need to do that "find next
> NOTE_INSN_VAR_LOCATION" walk anyway.
>
> On the testcase from the PR this patch speeds it 2.8times, from 0m0.674s
> to 0m0.236s (why it takes for the reporter more than 60s is unknown).
>
> Bootstrapped/regtested on i686-linux, ok for trunk?
LGTM.
Richard.
> 2020-08-26 Jakub Jelinek <ja...@redhat.com>
>
> PR debug/96729
> * dwarf2out.c (dwarf2out_next_real_insn): Adjust function comment.
> (dwarf2out_var_location): Look for next_note only if next_real is
> non-NULL, in that case look for the first non-deleted
> NOTE_INSN_VAR_LOCATION between loc_note and next_real, if any.
>
> --- gcc/dwarf2out.c.jj 2020-08-25 21:27:57.241094806 +0200
> +++ gcc/dwarf2out.c 2020-08-25 21:51:43.475775792 +0200
> @@ -27204,7 +27204,7 @@ static bool maybe_at_text_label_p = true
> /* One above highest N where .LVLN label might be equal to .Ltext0 label. */
> static unsigned int first_loclabel_num_not_at_text_label;
>
> -/* Look ahead for a real insn, or for a begin stmt marker. */
> +/* Look ahead for a real insn. */
>
> static rtx_insn *
> dwarf2out_next_real_insn (rtx_insn *loc_note)
> @@ -27229,7 +27229,7 @@ dwarf2out_var_location (rtx_insn *loc_no
> {
> char loclabel[MAX_ARTIFICIAL_LABEL_BYTES + 2];
> struct var_loc_node *newloc;
> - rtx_insn *next_real, *next_note;
> + rtx_insn *next_real;
> rtx_insn *call_insn = NULL;
> static const char *last_label;
> static const char *last_postcall_label;
> @@ -27254,7 +27254,6 @@ dwarf2out_var_location (rtx_insn *loc_no
> var_loc_p = false;
>
> next_real = dwarf2out_next_real_insn (call_insn);
> - next_note = NULL;
> cached_next_real_insn = NULL;
> goto create_label;
> }
> @@ -27282,7 +27281,6 @@ dwarf2out_var_location (rtx_insn *loc_no
> var_loc_p = false;
>
> next_real = dwarf2out_next_real_insn (call_insn);
> - next_note = NULL;
> cached_next_real_insn = NULL;
> goto create_label;
> }
> @@ -27311,22 +27309,28 @@ dwarf2out_var_location (rtx_insn *loc_no
> next_real = NULL;
> }
>
> - next_note = NEXT_INSN (loc_note);
> - if (! next_note
> - || next_note->deleted ()
> - || ! NOTE_P (next_note)
> - || (NOTE_KIND (next_note) != NOTE_INSN_VAR_LOCATION
> - && NOTE_KIND (next_note) != NOTE_INSN_BEGIN_STMT
> - && NOTE_KIND (next_note) != NOTE_INSN_INLINE_ENTRY))
> - next_note = NULL;
> -
> if (! next_real)
> next_real = dwarf2out_next_real_insn (loc_note);
>
> - if (next_note)
> + if (next_real)
> {
> - expected_next_loc_note = next_note;
> - cached_next_real_insn = next_real;
> + rtx_insn *next_note = NEXT_INSN (loc_note);
> + while (next_note != next_real)
> + {
> + if (! next_note->deleted ()
> + && NOTE_P (next_note)
> + && NOTE_KIND (next_note) == NOTE_INSN_VAR_LOCATION)
> + break;
> + next_note = NEXT_INSN (next_note);
> + }
> +
> + if (next_note == next_real)
> + cached_next_real_insn = NULL;
> + else
> + {
> + expected_next_loc_note = next_note;
> + cached_next_real_insn = next_real;
> + }
> }
> else
> cached_next_real_insn = NULL;
>
> Jakub
>
>
--
Richard Biener <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
