[rtlopt] speed improvement of branch prediction
Segher Boessenkool
segher@koffie.nl
Thu Jan 9 22:41:00 GMT 2003
Josef Zlomek wrote:
>
> > > this is a corrected patch which speeds up branch prediction by using
> > > sreal.c (simple real library) instead of real.c
> >
> > Speed up real.c instead.
Speed up the use of real.c instead. See attached patch.
It gets rid of most divisions in branch prediction.
> real.c already does not do operations bit by bit
> but by groups of bits (size of unsigned long)
> so I do not know how to speed it up.
It does do division bit by bit. Speeding up real.c isn't worth it
imho; there are bigger fish to fry, and it would be quite hard to
significantly speed up real.c while keeping it correct.
This patch achieves a speedup of GCC by a few percent on compiling
combine.c; any suggestions for better compile-time benchmarks gladly
accepted.
2003-01-08 Segher Boessenkool <segher@koffie.nl>
* predict.c (real_inv_br_prob_base): New variable.
(propagate_freq): Use multiply by reciprocal instead of
division. Don't divide by 1.0 at all.
(estimate_bb_frequencies): Similar.
*** predict.c.orig Wed Jan 8 16:13:45 2003
--- predict.c Wed Jan 8 16:14:27 2003
*************** Software Foundation, 59 Temple Place - S
*** 51,60 ****
#include "target.h"
#include "loop.h"
! /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE, 0.5,
! REAL_BB_FREQ_MAX. */
static REAL_VALUE_TYPE real_zero, real_one, real_almost_one, real_br_prob_base,
! real_one_half, real_bb_freq_max;
/* Random guesstimation given names. */
#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
--- 51,60 ----
#include "target.h"
#include "loop.h"
! /* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
! 1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
static REAL_VALUE_TYPE real_zero, real_one, real_almost_one, real_br_prob_base,
! real_inv_br_prob_base, real_one_half, real_bb_freq_max;
/* Random guesstimation given names. */
#define PROB_VERY_UNLIKELY (REG_BR_PROB_BASE / 10 - 1)
*************** propagate_freq (loop)
*** 986,1005 ****
TYPE_MODE (double_type_node));
REAL_ARITHMETIC (tmp, MULT_EXPR, tmp,
BLOCK_INFO (e->src)->frequency);
! REAL_ARITHMETIC (tmp, RDIV_EXPR, tmp, real_br_prob_base);
REAL_ARITHMETIC (frequency, PLUS_EXPR, frequency, tmp);
}
! if (REAL_VALUES_LESS (real_almost_one, cyclic_probability))
! memcpy (&cyclic_probability, &real_almost_one, sizeof (real_zero));
! /* BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability)
! */
! REAL_ARITHMETIC (cyclic_probability, MINUS_EXPR, real_one,
cyclic_probability);
! REAL_ARITHMETIC (BLOCK_INFO (bb)->frequency,
! RDIV_EXPR, frequency, cyclic_probability);
}
BLOCK_INFO (bb)->tovisit = 0;
--- 986,1010 ----
TYPE_MODE (double_type_node));
REAL_ARITHMETIC (tmp, MULT_EXPR, tmp,
BLOCK_INFO (e->src)->frequency);
! REAL_ARITHMETIC (tmp, MULT_EXPR, tmp, real_inv_br_prob_base);
REAL_ARITHMETIC (frequency, PLUS_EXPR, frequency, tmp);
}
! if (REAL_VALUES_IDENTICAL (cyclic_probability, real_zero))
! memcpy (&BLOCK_INFO (bb)->frequency, &frequency, sizeof (frequency));
! else
! {
! if (REAL_VALUES_LESS (real_almost_one, cyclic_probability))
! memcpy (&cyclic_probability, &real_almost_one, sizeof (real_zero));
! /* BLOCK_INFO (bb)->frequency = frequency / (1 - cyclic_probability)
! */
! REAL_ARITHMETIC (cyclic_probability, MINUS_EXPR, real_one,
cyclic_probability);
! REAL_ARITHMETIC (BLOCK_INFO (bb)->frequency,
! RDIV_EXPR, frequency, cyclic_probability);
! }
}
BLOCK_INFO (bb)->tovisit = 0;
*************** propagate_freq (loop)
*** 1018,1024 ****
REAL_ARITHMETIC (tmp, MULT_EXPR, tmp,
BLOCK_INFO (bb)->frequency);
REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
! RDIV_EXPR, tmp, real_br_prob_base);
}
--- 1023,1029 ----
REAL_ARITHMETIC (tmp, MULT_EXPR, tmp,
BLOCK_INFO (bb)->frequency);
REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
! MULT_EXPR, tmp, real_inv_br_prob_base);
}
*************** estimate_bb_frequencies (loops)
*** 1149,1159 ****
REAL_VALUE_FROM_INT (real_br_prob_base, REG_BR_PROB_BASE, 0, double_mode);
REAL_VALUE_FROM_INT (real_bb_freq_max, BB_FREQ_MAX, 0, double_mode);
REAL_VALUE_FROM_INT (real_one_half, 2, 0, double_mode);
-
REAL_ARITHMETIC (real_one_half, RDIV_EXPR, real_one, real_one_half);
!
! REAL_ARITHMETIC (real_almost_one, RDIV_EXPR, real_one, real_br_prob_base);
! REAL_ARITHMETIC (real_almost_one, MINUS_EXPR, real_one, real_almost_one);
mark_dfs_back_edges ();
/* Fill in the probability values in flowgraph based on the REG_BR_PROB
--- 1154,1162 ----
REAL_VALUE_FROM_INT (real_br_prob_base, REG_BR_PROB_BASE, 0, double_mode);
REAL_VALUE_FROM_INT (real_bb_freq_max, BB_FREQ_MAX, 0, double_mode);
REAL_VALUE_FROM_INT (real_one_half, 2, 0, double_mode);
REAL_ARITHMETIC (real_one_half, RDIV_EXPR, real_one, real_one_half);
! REAL_ARITHMETIC (real_inv_br_prob_base, RDIV_EXPR, real_one, real_br_prob_base);
! REAL_ARITHMETIC (real_almost_one, MINUS_EXPR, real_one, real_inv_br_prob_base);
mark_dfs_back_edges ();
/* Fill in the probability values in flowgraph based on the REG_BR_PROB
*************** estimate_bb_frequencies (loops)
*** 1197,1204 ****
REAL_VALUE_FROM_INT (EDGE_INFO (e)->back_edge_prob,
e->probability, 0, double_mode);
REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
! RDIV_EXPR, EDGE_INFO (e)->back_edge_prob,
! real_br_prob_base);
}
}
--- 1200,1207 ----
REAL_VALUE_FROM_INT (EDGE_INFO (e)->back_edge_prob,
e->probability, 0, double_mode);
REAL_ARITHMETIC (EDGE_INFO (e)->back_edge_prob,
! MULT_EXPR, EDGE_INFO (e)->back_edge_prob,
! real_inv_br_prob_base);
}
}
*************** estimate_bb_frequencies (loops)
*** 1213,1225 ****
memcpy (&freq_max, &BLOCK_INFO (bb)->frequency,
sizeof (freq_max));
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
{
REAL_VALUE_TYPE tmp;
REAL_ARITHMETIC (tmp, MULT_EXPR, BLOCK_INFO (bb)->frequency,
! real_bb_freq_max);
! REAL_ARITHMETIC (tmp, RDIV_EXPR, tmp, freq_max);
REAL_ARITHMETIC (tmp, PLUS_EXPR, tmp, real_one_half);
bb->frequency = REAL_VALUE_UNSIGNED_FIX (tmp);
}
--- 1216,1229 ----
memcpy (&freq_max, &BLOCK_INFO (bb)->frequency,
sizeof (freq_max));
+ REAL_ARITHMETIC (freq_max, RDIV_EXPR, real_bb_freq_max, freq_max);
+
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
{
REAL_VALUE_TYPE tmp;
REAL_ARITHMETIC (tmp, MULT_EXPR, BLOCK_INFO (bb)->frequency,
! freq_max);
REAL_ARITHMETIC (tmp, PLUS_EXPR, tmp, real_one_half);
bb->frequency = REAL_VALUE_UNSIGNED_FIX (tmp);
}
More information about the Gcc-patches
mailing list