From: Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>
To: Paolo Bonzini <bonzini@gnu.org>
Cc: Andrew MacLeod <amacleod@redhat.com>,
gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: [ssaupdate] Local dominance info
Date: Thu, 21 Oct 2004 10:53:00 -0000 [thread overview]
Message-ID: <20041021102555.GA7330@atrey.karlin.mff.cuni.cz> (raw)
In-Reply-To: <41778CA3.1050702@gnu.org>
Hello,
> >I think trying to keep numbered order of stmts within blocks for the
> >duration of SSA is a very bad idea since most optimizations do not care.
> >So you have the overhead of making sure that you keep things kosher
> >everytime you ever move anything.
>
> Zdenek, do you have an analysis of the amortized worst-case complexity
> of bsi_insert_before and bsi_insert_after?
no; the algorithm is quite ad-hoc and I believe that it behaves
quite badly from the theoretic point of view. It should (and seems to)
behave well under "normal" workload (i.e. relatively few insertions on
single place), but it of course would be better to have here something
for that some upper bound could be proved (I am fairly sure it would be
possible, and probably the solution would not be much more complicated
than the current one).
Zdenek
next prev parent reply other threads:[~2004-10-21 10:25 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-10-19 21:54 Zdenek Dvorak
2004-10-20 13:32 ` Andrew MacLeod
2004-10-20 19:35 ` Zdenek Dvorak
2004-10-20 22:26 ` Andrew MacLeod
2004-10-20 22:54 ` Zdenek Dvorak
2004-10-21 3:06 ` Jeffrey A Law
2004-10-22 16:38 ` Michael Matz
2004-10-22 17:05 ` Andrew MacLeod
2004-10-22 21:33 ` Zdenek Dvorak
2004-10-22 21:47 ` Andrew MacLeod
2004-10-21 10:25 ` Paolo Bonzini
2004-10-21 10:53 ` Zdenek Dvorak [this message]
2004-10-21 10:54 ` Paolo Bonzini
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20041021102555.GA7330@atrey.karlin.mff.cuni.cz \
--to=rakdver@atrey.karlin.mff.cuni.cz \
--cc=amacleod@redhat.com \
--cc=bonzini@gnu.org \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).