This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
Re: PR/7344 - O(n^2) algorithm?
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: tm <tm at mail dot kloo dot net>
- Cc: gcc-bugs at gcc dot gnu dot org, jh at suse dot cz
- Date: Thu, 29 Aug 2002 19:48:06 +0200
- Subject: Re: PR/7344 - O(n^2) algorithm?
- References: <Pine.LNX.4.21.0208141743580.4373-100000@mail.kloo.net>
Hello,
> I looked at PR/7344 which is entitled
>
> "performance regression on huge case statements"
>
> The problem appears to be bad O-complexity scalability in
> process_note_prediction. It contains this loop:
>
> /* Now find the edge that leads to our branch and aply the
> prediction. */
>
> if (y == last_basic_block)
> return;
> for (e = BASIC_BLOCK (y)->succ; e; e = e->succ_next)
> if (e->dest->index >= 0
> && dominated_by_p (post_dominators, e->dest, bb))
> predict_edge_def (e, pred, taken);
>
> This algorithm appears to be O(n^2) for our testcase.
> There seem to be 10,000 basic blocks dominated by each other,
> so predict_edge_def() would be called 100 million times.
>
> Is there an alternate solution for this problem?
Yes, I can imagine it can happen. Considering that
- handling the situation correctly&fast in this case is not easy
- resulting predictions are not very useful nor reliable
- this case should not be too frequent
I would solve this by simply giving up provided that BASIC_BLOCK (y) has
more than some constant number of succesors.
Zdenek