This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] PR/7344, O(n^2) branch prediction
- From: tm <tm at mail dot kloo dot net>
- To: gcc-patches 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, 4 Sep 2002 12:42:10 -0700 (PDT)
- Subject: [PATCH] PR/7344, O(n^2) branch prediction
Refs:
http://gcc.gnu.org/ml/gcc-bugs/2002-08/msg00355.html
http://gcc.gnu.org/ml/gcc-bugs/2002-08/msg00655.html
http://gcc.gnu.org/ml/gcc-bugs/2002-08/msg00662.html
Here's a fix. With this patch the testcase compiles in finite time even
on a P2/300:
real 2m12.805s
user 2m12.140s
sys 0m0.550s
2002-09-04 Toshiyasu Morita <toshiyasu.morita@hsa.hitachi.com>
* predict.c (process_note_prediction): Ignore multiway branches.
*** predict.c.bak Tue Sep 3 11:35:51 2002
--- predict.c Wed Sep 4 10:59:23 2002
*************** process_note_prediction (bb, heads, domi
*** 723,729 ****
int flags;
{
edge e;
! int y;
bool taken;
taken = flags & IS_TAKEN;
--- 723,729 ----
int flags;
{
edge e;
! int y, count;
bool taken;
taken = flags & IS_TAKEN;
*************** process_note_prediction (bb, heads, domi
*** 761,774 ****
}
y = heads[bb->index];
! /* 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);
}
/* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them
--- 761,779 ----
}
y = heads[bb->index];
! /* Now find the edge that leads to our branch and apply the prediction.
! Ignore blocks with multiway branches to reduce O-complexity. (PR/7344). */
if (y == last_basic_block)
return;
! for (e = BASIC_BLOCK (y)->succ, count = 0; e; e = e->succ_next)
! {
! if (++count >= 2)
! break;
! if (e->dest->index >= 0
! && dominated_by_p (post_dominators, e->dest, bb))
! predict_edge_def (e, pred, taken);
! }
}
/* Gathers NOTE_INSN_PREDICTIONs in given basic block and turns them