This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
PR/7344 - O(n^2) algorithm?
- From: tm <tm at mail dot kloo dot net>
- To: gcc-bugs at gcc dot gnu dot org
- Cc: jh at suse dot cz, rakdver at atrey dot karlin dot mff dot cuni dot cz
- Date: Wed, 14 Aug 2002 17:47:42 -0700 (PDT)
- Subject: PR/7344 - O(n^2) algorithm?
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?
Toshi