This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] rtlopt branch merge part 6 - speed improvement of branch predictions
- From: Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 3 Feb 2003 11:18:19 +0100
- Subject: [patch] rtlopt branch merge part 6 - speed improvement of branch predictions
Hi,
this patch contains a simple and fast library for "floating point
numbers"
and its use in predict.c.
The speed up of branch prediction is mainly done by several reasons:
Only a half of processor's integers is used for computing the operations
(so that for example multiplication does not overflow
(16-bit * 16-bit = 32-bit on 32-bit machine))
and the sreal values are computed using processor's instructions for
adding, substracting, multiplying and dividing.
Since we do not need a high precission for branch prediction
I am using 32-bit precission in sreal (divided to two 16-bit parts on
32-bit machines), moreover so that division would be fast its
precission is "only" 24-bit.
But since predicted basic block frequencies are in range 0..10000
the precission is good enough.
By this approach, branch prediction pass is about two times faster
(on i386) and it speeds up bootstrap by several percents.
Bootstrapped/regtested i386.
Bootstrapped/regtested i386 and x86-64 one week ago (today I can't
access any x86-64 machine.
Josef
2003-02-03 Josef Zlomek <zlomekj@suse.cz>
* Makefile.in (sreal.o): Added.
(predict.o): Depends on sreal.h instead of real.h.
* sreal.c: New file.
* sreal.h: New file.
* predict.c: Use sreal.c instead of real.c.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.985
diff -c -3 -p -r1.985 Makefile.in
*** Makefile.in 1 Feb 2003 18:59:40 -0000 1.985
--- Makefile.in 2 Feb 2003 16:38:23 -0000
*************** OBJS = alias.o bb-reorder.o bitmap.o bui
*** 781,787 ****
real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \
reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o \
sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o \
! sibcall.o simplify-rtx.o ssa.o ssa-ccp.o ssa-dce.o stmt.o \
stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
alloc-pool.o et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
--- 781,787 ----
real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \
reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o \
sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o \
! sibcall.o simplify-rtx.o sreal.o ssa.o ssa-ccp.o ssa-dce.o stmt.o \
stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
alloc-pool.o et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
*************** recog.o : recog.c $(CONFIG_H) $(SYSTEM_H
*** 1673,1681 ****
reg-stack.o : reg-stack.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
$(RECOG_H) $(REGS_H) hard-reg-set.h flags.h insn-config.h toplev.h reload.h \
varray.h function.h $(TM_P_H) $(GGC_H) gt-reg-stack.h
predict.o: predict.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
flags.h insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h \
! $(RECOG_H) function.h except.h $(EXPR_H) $(TM_P_H) $(PREDICT_H) real.h \
$(PARAMS_H) $(TARGET_H) cfgloop.h
lists.o: lists.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) toplev.h $(RTL_H) $(GGC_H)
bb-reorder.o : bb-reorder.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
--- 1673,1682 ----
reg-stack.o : reg-stack.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
$(RECOG_H) $(REGS_H) hard-reg-set.h flags.h insn-config.h toplev.h reload.h \
varray.h function.h $(TM_P_H) $(GGC_H) gt-reg-stack.h
+ sreal.o: sreal.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) sreal.h
predict.o: predict.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
flags.h insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h \
! $(RECOG_H) function.h except.h $(EXPR_H) $(TM_P_H) $(PREDICT_H) sreal.h \
$(PARAMS_H) $(TARGET_H) cfgloop.h
lists.o: lists.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) toplev.h $(RTL_H) $(GGC_H)
bb-reorder.o : bb-reorder.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.80
diff -c -3 -p -r1.80 predict.c
*** predict.c 24 Jan 2003 20:27:02 -0000 1.80
--- predict.c 2 Feb 2003 16:38:23 -0000
*************** Software Foundation, 59 Temple Place - S
*** 48,54 ****
#include "expr.h"
#include "predict.h"
#include "profile.h"
! #include "real.h"
#include "params.h"
#include "target.h"
#include "loop.h"
--- 48,54 ----
#include "expr.h"
#include "predict.h"
#include "profile.h"
! #include "sreal.h"
#include "params.h"
#include "target.h"
#include "loop.h"
*************** Software Foundation, 59 Temple Place - S
*** 56,63 ****
/* 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)
--- 56,63 ----
/* 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 sreal 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)
*************** note_prediction_to_br_prob ()
*** 905,911 ****
typedef struct block_info_def
{
/* Estimated frequency of execution of basic_block. */
! REAL_VALUE_TYPE frequency;
/* To keep queue of basic blocks to process. */
basic_block next;
--- 905,911 ----
typedef struct block_info_def
{
/* Estimated frequency of execution of basic_block. */
! sreal frequency;
/* To keep queue of basic blocks to process. */
basic_block next;
*************** typedef struct edge_info_def
*** 923,929 ****
/* In case edge is an loopback edge, the probability edge will be reached
in case header is. Estimated number of iterations of the loop can be
then computed as 1 / (1 - back_edge_prob). */
! REAL_VALUE_TYPE back_edge_prob;
/* True if the edge is an loopback edge in the natural loop. */
int back_edge:1;
} *edge_info;
--- 923,929 ----
/* In case edge is an loopback edge, the probability edge will be reached
in case header is. Estimated number of iterations of the loop can be
then computed as 1 / (1 - back_edge_prob). */
! sreal back_edge_prob;
/* True if the edge is an loopback edge in the natural loop. */
int back_edge:1;
} *edge_info;
*************** propagate_freq (loop)
*** 968,974 ****
last = head;
for (bb = head; bb; bb = nextbb)
{
! REAL_VALUE_TYPE cyclic_probability, frequency;
memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
memcpy (&frequency, &real_zero, sizeof (real_zero));
--- 968,974 ----
last = head;
for (bb = head; bb; bb = nextbb)
{
! sreal cyclic_probability, frequency;
memcpy (&cyclic_probability, &real_zero, sizeof (real_zero));
memcpy (&frequency, &real_zero, sizeof (real_zero));
*************** propagate_freq (loop)
*** 988,1027 ****
for (e = bb->pred; e; e = e->pred_next)
if (EDGE_INFO (e)->back_edge)
{
! REAL_ARITHMETIC (cyclic_probability, PLUS_EXPR,
! cyclic_probability,
! EDGE_INFO (e)->back_edge_prob);
}
else if (!(e->flags & EDGE_DFS_BACK))
{
! REAL_VALUE_TYPE tmp;
/* frequency += (e->probability
* BLOCK_INFO (e->src)->frequency /
REG_BR_PROB_BASE); */
! REAL_VALUE_FROM_INT (tmp, e->probability, 0,
! 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);
}
}
--- 988,1029 ----
for (e = bb->pred; e; e = e->pred_next)
if (EDGE_INFO (e)->back_edge)
{
! sreal_add (&cyclic_probability, &cyclic_probability,
! &EDGE_INFO (e)->back_edge_prob);
}
else if (!(e->flags & EDGE_DFS_BACK))
{
! sreal tmp;
/* frequency += (e->probability
* BLOCK_INFO (e->src)->frequency /
REG_BR_PROB_BASE); */
! sreal_init (&tmp, e->probability, 0);
! sreal_mul (&tmp, &tmp, &BLOCK_INFO (e->src)->frequency);
! sreal_mul (&tmp, &tmp, &real_inv_br_prob_base);
! sreal_add (&frequency, &frequency, &tmp);
}
! if (sreal_compare (&cyclic_probability, &real_zero) == 0)
! {
! memcpy (&BLOCK_INFO (bb)->frequency, &frequency,
! sizeof (frequency));
! }
else
{
! if (sreal_compare (&cyclic_probability, &real_almost_one) > 0)
! {
! memcpy (&cyclic_probability, &real_almost_one,
! sizeof (real_almost_one));
! }
! /* BLOCK_INFO (bb)->frequency = frequency
! / (1 - cyclic_probability) */
! sreal_sub (&cyclic_probability, &real_one, &cyclic_probability);
! sreal_div (&BLOCK_INFO (bb)->frequency,
! &frequency, &cyclic_probability);
}
}
*************** propagate_freq (loop)
*** 1031,1048 ****
for (e = bb->succ; e; e = e->succ_next)
if (e->dest == head)
{
! REAL_VALUE_TYPE tmp;
/* EDGE_INFO (e)->back_edge_prob
= ((e->probability * BLOCK_INFO (bb)->frequency)
/ REG_BR_PROB_BASE); */
- REAL_VALUE_FROM_INT (tmp, e->probability, 0,
- TYPE_MODE (double_type_node));
- 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);
}
/* Propagate to successor blocks. */
--- 1033,1048 ----
for (e = bb->succ; e; e = e->succ_next)
if (e->dest == head)
{
! sreal tmp;
/* EDGE_INFO (e)->back_edge_prob
= ((e->probability * BLOCK_INFO (bb)->frequency)
/ REG_BR_PROB_BASE); */
+ sreal_init (&tmp, e->probability, 0);
+ sreal_mul (&tmp, &tmp, &BLOCK_INFO (bb)->frequency);
+ sreal_mul (&EDGE_INFO (e)->back_edge_prob,
+ &tmp, &real_inv_br_prob_base);
}
/* Propagate to successor blocks. */
*************** estimate_bb_frequencies (loops)
*** 1160,1180 ****
struct loops *loops;
{
basic_block bb;
! REAL_VALUE_TYPE freq_max;
! enum machine_mode double_mode = TYPE_MODE (double_type_node);
if (flag_branch_probabilities)
counts_to_freqs ();
else
{
! REAL_VALUE_FROM_INT (real_zero, 0, 0, double_mode);
! REAL_VALUE_FROM_INT (real_one, 1, 0, double_mode);
! 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
--- 1160,1178 ----
struct loops *loops;
{
basic_block bb;
! sreal freq_max;
if (flag_branch_probabilities)
counts_to_freqs ();
else
{
! sreal_init (&real_zero, 0, 0);
! sreal_init (&real_one, 1, 0);
! sreal_init (&real_br_prob_base, REG_BR_PROB_BASE, 0);
! sreal_init (&real_bb_freq_max, BB_FREQ_MAX, 0);
! sreal_init (&real_one_half, 1, -1);
! sreal_div (&real_inv_br_prob_base, &real_one, &real_br_prob_base);
! sreal_sub (&real_almost_one, &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)
*** 1215,1225 ****
BLOCK_INFO (bb)->tovisit = 0;
for (e = bb->succ; e; e = e->succ_next)
{
! 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);
}
}
--- 1213,1222 ----
BLOCK_INFO (bb)->tovisit = 0;
for (e = bb->succ; e; e = e->succ_next)
{
! sreal_init (&EDGE_INFO (e)->back_edge_prob, e->probability, 0);
! sreal_mul (&EDGE_INFO (e)->back_edge_prob,
! &EDGE_INFO (e)->back_edge_prob,
! &real_inv_br_prob_base);
}
}
*************** estimate_bb_frequencies (loops)
*** 1229,1249 ****
memcpy (&freq_max, &real_zero, sizeof (real_zero));
FOR_EACH_BB (bb)
! if (REAL_VALUES_LESS
! (freq_max, BLOCK_INFO (bb)->frequency))
! 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);
}
free_aux_for_blocks ();
--- 1226,1242 ----
memcpy (&freq_max, &real_zero, sizeof (real_zero));
FOR_EACH_BB (bb)
! if (sreal_compare (&freq_max, &BLOCK_INFO (bb)->frequency) < 0)
! memcpy (&freq_max, &BLOCK_INFO (bb)->frequency, sizeof (freq_max));
+ sreal_div (&freq_max, &real_bb_freq_max, &freq_max);
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
{
! sreal tmp;
! sreal_mul (&tmp, &BLOCK_INFO (bb)->frequency, &freq_max);
! sreal_add (&tmp, &tmp, &real_one_half);
! bb->frequency = sreal_to_int (&tmp);
}
free_aux_for_blocks ();
Index: sreal.c
===================================================================
RCS file: sreal.c
diff -N sreal.c
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- sreal.c 2 Feb 2003 16:38:29 -0000
***************
*** 0 ****
--- 1,591 ----
+ /* Simple data type for positive real numbers for the GNU compiler.
+ Copyright (C) 2002, 2003 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 2, or (at your option) any later
+ version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ /* This library supports positive real numbers and 0;
+ inf and nan are NOT supported.
+ It is written to be simple and fast.
+
+ Value of sreal is
+ x = sig * 2 ^ exp
+ where
+ sig = significant
+ (for < 64-bit machines sig = sig_lo + sig_hi * 2 ^ SREAL_PART_BITS)
+ exp = exponent
+
+ One HOST_WIDE_INT is used for the significant on 64-bit (and more than
+ 64-bit) machines,
+ otherwise two HOST_WIDE_INTs are used for the significant.
+ Only a half of significant bits is used (in normalized sreals) so that we do
+ not have problems with overflow, for example when c->sig = a->sig * b->sig.
+ So the precission for 64-bit and 32-bit machines is 32-bit.
+
+ Invariant: The numbers are normalized before and after each call of sreal_*.
+
+ Normalized sreals:
+ All numbers (except zero) meet following conditions:
+ SREAL_MIN_SIG <= sig && sig <= SREAL_MAX_SIG
+ -SREAL_MAX_EXP <= exp && exp <= SREAL_MAX_EXP
+
+ If the number would be too large, it is set to upper bounds of these
+ conditions.
+
+ If the number is zero or would be too small it meets following conditions:
+ sig == 0 && exp == -SREAL_MAX_EXP
+ */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "sreal.h"
+
+ void dump_sreal PARAMS ((FILE *, sreal *));
+ static inline void copy PARAMS ((sreal *, sreal *));
+ static inline void shift_right PARAMS ((sreal *, int));
+ static void normalize PARAMS ((sreal *));
+
+ /* Print the content of struct sreal. */
+
+ void
+ dump_sreal (file, x)
+ FILE *file;
+ sreal *x;
+ {
+ #if SREAL_PART_BITS < 32
+ fprintf (file, "((");
+ fprintf (file, HOST_WIDE_INT_PRINT_UNSIGNED, x->sig_hi);
+ fprintf (file, " * 2^16 + ");
+ fprintf (file, HOST_WIDE_INT_PRINT_UNSIGNED, x->sig_lo);
+ fprintf (file, ") * 2^%d)", x->exp);
+ #else
+ fprintf (file, "(");
+ fprintf (file, HOST_WIDE_INT_PRINT_UNSIGNED, x->sig);
+ fprintf (file, " * 2^%d)", x->exp);
+ #endif
+ }
+
+ /* Copy the sreal number. */
+
+ static inline void
+ copy (r, a)
+ sreal *r;
+ sreal *a;
+ {
+ #if SREAL_PART_BITS < 32
+ r->sig_lo = a->sig_lo;
+ r->sig_hi = a->sig_hi;
+ #else
+ r->sig = a->sig;
+ #endif
+ r->exp = a->exp;
+ }
+
+ /* Shift X right by S bits. Needed: 0 < S <= SREAL_BITS.
+ When the most significant bit shifted out is 1, add 1 to X (rounding). */
+
+ static inline void
+ shift_right (x, s)
+ sreal *x;
+ int s;
+ {
+ #ifdef ENABLE_CHECKING
+ if (s <= 0 || s > SREAL_BITS)
+ abort ();
+ if (x->exp + s > SREAL_MAX_EXP)
+ {
+ /* Exponent should never be so large because shift_right is used only by
+ sreal_add and sreal_sub ant thus the number cannot be shifted out from
+ exponent range. */
+ abort ();
+ }
+ #endif
+
+ x->exp += s;
+
+ #if SREAL_PART_BITS < 32
+ if (s > SREAL_PART_BITS)
+ {
+ s -= SREAL_PART_BITS;
+ x->sig_hi += (uhwi) 1 << (s - 1);
+ x->sig_lo = x->sig_hi >> s;
+ x->sig_hi = 0;
+ }
+ else
+ {
+ x->sig_lo += (uhwi) 1 << (s - 1);
+ if (x->sig_lo & ((uhwi) 1 << SREAL_PART_BITS))
+ {
+ x->sig_hi++;
+ x->sig_lo -= (uhwi) 1 << SREAL_PART_BITS;
+ }
+ x->sig_lo >>= s;
+ x->sig_lo |= (x->sig_hi & (((uhwi) 1 << s) - 1)) << (SREAL_PART_BITS - s);
+ x->sig_hi >>= s;
+ }
+ #else
+ x->sig += (uhwi) 1 << (s - 1);
+ x->sig >>= s;
+ #endif
+ }
+
+ /* Normalize *X. */
+
+ static void
+ normalize (x)
+ sreal *x;
+ {
+ #if SREAL_PART_BITS < 32
+ int shift;
+ HOST_WIDE_INT mask;
+
+ if (x->sig_lo == 0 && x->sig_hi == 0)
+ {
+ x->exp = -SREAL_MAX_EXP;
+ }
+ else if (x->sig_hi < SREAL_MIN_SIG)
+ {
+ if (x->sig_hi == 0)
+ {
+ /* Move lower part of significant to higher part. */
+ x->sig_hi = x->sig_lo;
+ x->sig_lo = 0;
+ x->exp -= SREAL_PART_BITS;
+ }
+ shift = 0;
+ while (x->sig_hi < SREAL_MIN_SIG)
+ {
+ x->sig_hi <<= 1;
+ x->exp--;
+ shift++;
+ }
+ /* Check underflow. */
+ if (x->exp < -SREAL_MAX_EXP)
+ {
+ x->exp = -SREAL_MAX_EXP;
+ x->sig_hi = 0;
+ x->sig_lo = 0;
+ }
+ else if (shift)
+ {
+ mask = (1 << SREAL_PART_BITS) - (1 << (SREAL_PART_BITS - shift));
+ x->sig_hi |= (x->sig_lo & mask) >> (SREAL_PART_BITS - shift);
+ x->sig_lo = (x->sig_lo << shift) & (((uhwi) 1 << SREAL_PART_BITS) - 1);
+ }
+ }
+ else if (x->sig_hi > SREAL_MAX_SIG)
+ {
+ unsigned HOST_WIDE_INT tmp = x->sig_hi;
+
+ /* Find out how many bits will be shifted. */
+ shift = 0;
+ do
+ {
+ tmp >>= 1;
+ shift++;
+ }
+ while (tmp > SREAL_MAX_SIG);
+
+ /* Round the number. */
+ x->sig_lo += (uhwi) 1 << (shift - 1);
+
+ x->sig_lo >>= shift;
+ x->sig_lo += ((x->sig_hi & (((uhwi) 1 << shift) - 1))
+ << (SREAL_PART_BITS - shift));
+ x->sig_hi >>= shift;
+ x->exp += shift;
+ if (x->sig_lo & ((uhwi) 1 << SREAL_PART_BITS))
+ {
+ x->sig_lo -= (uhwi) 1 << SREAL_PART_BITS;
+ x->sig_hi++;
+ if (x->sig_hi > SREAL_MAX_SIG)
+ {
+ /* x->sig_hi was SREAL_MAX_SIG before increment
+ so now last bit is zero. */
+ x->sig_hi >>= 1;
+ x->sig_lo >>= 1;
+ x->exp++;
+ }
+ }
+
+ /* Check overflow. */
+ if (x->exp > SREAL_MAX_EXP)
+ {
+ x->exp = SREAL_MAX_EXP;
+ x->sig_hi = SREAL_MAX_SIG;
+ x->sig_lo = SREAL_MAX_SIG;
+ }
+ }
+ #else
+ if (x->sig == 0)
+ {
+ x->exp = -SREAL_MAX_EXP;
+ }
+ else if (x->sig < SREAL_MIN_SIG)
+ {
+ do
+ {
+ x->sig <<= 1;
+ x->exp--;
+ }
+ while (x->sig < SREAL_MIN_SIG);
+
+ /* Check underflow. */
+ if (x->exp < -SREAL_MAX_EXP)
+ {
+ x->exp = -SREAL_MAX_EXP;
+ x->sig = 0;
+ }
+ }
+ else if (x->sig > SREAL_MAX_SIG)
+ {
+ int last_bit;
+ do
+ {
+ last_bit = x->sig & 1;
+ x->sig >>= 1;
+ x->exp++;
+ }
+ while (x->sig > SREAL_MAX_SIG);
+
+ /* Round the number. */
+ x->sig += last_bit;
+ if (x->sig > SREAL_MAX_SIG)
+ {
+ x->sig >>= 1;
+ x->exp++;
+ }
+
+ /* Check overflow. */
+ if (x->exp > SREAL_MAX_EXP)
+ {
+ x->exp = SREAL_MAX_EXP;
+ x->sig = SREAL_MAX_SIG;
+ }
+ }
+ #endif
+ }
+
+ /* Set *R to SIG * 2 ^ EXP. Return R. */
+
+ sreal *
+ sreal_init (r, sig, exp)
+ sreal *r;
+ unsigned HOST_WIDE_INT sig;
+ signed int exp;
+ {
+ #if SREAL_PART_BITS < 32
+ r->sig_lo = 0;
+ r->sig_hi = sig;
+ r->exp = exp - 16;
+ #else
+ r->sig = sig;
+ r->exp = exp;
+ #endif
+ normalize (r);
+ return r;
+ }
+
+ /* Return integer value of *R. */
+
+ HOST_WIDE_INT
+ sreal_to_int (r)
+ sreal *r;
+ {
+ #if SREAL_PART_BITS < 32
+ if (r->exp <= -SREAL_BITS)
+ return 0;
+ if (r->exp >= 0)
+ return MAX_HOST_WIDE_INT;
+ return ((r->sig_hi << SREAL_PART_BITS) + r->sig_lo) >> -r->exp;
+ #else
+ if (r->exp <= -SREAL_BITS)
+ return 0;
+ if (r->exp >= SREAL_PART_BITS)
+ return MAX_HOST_WIDE_INT;
+ if (r->exp > 0)
+ return r->sig << r->exp;
+ if (r->exp < 0)
+ return r->sig >> -r->exp;
+ return r->sig;
+ #endif
+ }
+
+ /* Compare *A and *B. Return -1 if *A < *B, 1 if *A > *B and 0 if *A == *B. */
+
+ int
+ sreal_compare (a, b)
+ sreal *a;
+ sreal *b;
+ {
+ if (a->exp > b->exp)
+ return 1;
+ if (a->exp < b->exp)
+ return -1;
+ #if SREAL_PART_BITS < 32
+ if (a->sig_hi > b->sig_hi)
+ return 1;
+ if (a->sig_hi < b->sig_hi)
+ return -1;
+ if (a->sig_lo > b->sig_lo)
+ return 1;
+ if (a->sig_lo < b->sig_lo)
+ return -1;
+ #else
+ if (a->sig > b->sig)
+ return 1;
+ if (a->sig < b->sig)
+ return -1;
+ #endif
+ return 0;
+ }
+
+ /* *R = *A + *B. Return R. */
+
+ sreal *
+ sreal_add (r, a, b)
+ sreal *r;
+ sreal *a;
+ sreal *b;
+ {
+ int dexp;
+ sreal tmp;
+ sreal *bb;
+
+ if (sreal_compare (a, b) < 0)
+ {
+ sreal *swap;
+ swap = a;
+ a = b;
+ b = swap;
+ }
+
+ dexp = a->exp - b->exp;
+ r->exp = a->exp;
+ if (dexp > SREAL_BITS)
+ {
+ #if SREAL_PART_BITS < 32
+ r->sig_hi = a->sig_hi;
+ r->sig_lo = a->sig_lo;
+ #else
+ r->sig = a->sig;
+ #endif
+ return r;
+ }
+
+ if (dexp == 0)
+ bb = b;
+ else
+ {
+ copy (&tmp, b);
+ shift_right (&tmp, dexp);
+ bb = &tmp;
+ }
+
+ #if SREAL_PART_BITS < 32
+ r->sig_hi = a->sig_hi + bb->sig_hi;
+ r->sig_lo = a->sig_lo + bb->sig_lo;
+ if (r->sig_lo & ((uhwi) 1 << SREAL_PART_BITS))
+ {
+ r->sig_hi++;
+ r->sig_lo -= (uhwi) 1 << SREAL_PART_BITS;
+ }
+ #else
+ r->sig = a->sig + bb->sig;
+ #endif
+ normalize (r);
+ return r;
+ }
+
+ /* *R = *A - *B. Return R. */
+
+ sreal *
+ sreal_sub (r, a, b)
+ sreal *r;
+ sreal *a;
+ sreal *b;
+ {
+ int dexp;
+ sreal tmp;
+ sreal *bb;
+
+ if (sreal_compare (a, b) < 0)
+ {
+ abort ();
+ }
+
+ dexp = a->exp - b->exp;
+ r->exp = a->exp;
+ if (dexp > SREAL_BITS)
+ {
+ #if SREAL_PART_BITS < 32
+ r->sig_hi = a->sig_hi;
+ r->sig_lo = a->sig_lo;
+ #else
+ r->sig = a->sig;
+ #endif
+ return r;
+ }
+ if (dexp == 0)
+ bb = b;
+ else
+ {
+ copy (&tmp, b);
+ shift_right (&tmp, dexp);
+ bb = &tmp;
+ }
+
+ #if SREAL_PART_BITS < 32
+ if (a->sig_lo < bb->sig_lo)
+ {
+ r->sig_hi = a->sig_hi - bb->sig_hi - 1;
+ r->sig_lo = a->sig_lo + ((uhwi) 1 << SREAL_PART_BITS) - bb->sig_lo;
+ }
+ else
+ {
+ r->sig_hi = a->sig_hi - bb->sig_hi;
+ r->sig_lo = a->sig_lo - bb->sig_lo;
+ }
+ #else
+ r->sig = a->sig - bb->sig;
+ #endif
+ normalize (r);
+ return r;
+ }
+
+ /* *R = *A * *B. Return R. */
+
+ sreal *
+ sreal_mul (r, a, b)
+ sreal *r;
+ sreal *a;
+ sreal *b;
+ {
+ #if SREAL_PART_BITS < 32
+ if (a->sig_hi < SREAL_MIN_SIG || b->sig_hi < SREAL_MIN_SIG)
+ {
+ r->sig_lo = 0;
+ r->sig_hi = 0;
+ r->exp = -SREAL_MAX_EXP;
+ }
+ else
+ {
+ unsigned HOST_WIDE_INT tmp1, tmp2, tmp3;
+ if (sreal_compare (a, b) < 0)
+ {
+ sreal *swap;
+ swap = a;
+ a = b;
+ b = swap;
+ }
+
+ r->exp = a->exp + b->exp + SREAL_PART_BITS;
+
+ tmp1 = a->sig_lo * b->sig_lo;
+ tmp2 = a->sig_lo * b->sig_hi;
+ tmp3 = a->sig_hi * b->sig_lo + (tmp1 >> SREAL_PART_BITS);
+
+ r->sig_hi = a->sig_hi * b->sig_hi;
+ r->sig_hi += (tmp2 >> SREAL_PART_BITS) + (tmp3 >> SREAL_PART_BITS);
+ tmp2 &= ((uhwi) 1 << SREAL_PART_BITS) - 1;
+ tmp3 &= ((uhwi) 1 << SREAL_PART_BITS) - 1;
+ tmp1 = tmp2 + tmp3;
+
+ r->sig_lo = tmp1 & (((uhwi) 1 << SREAL_PART_BITS) - 1);
+ r->sig_hi += tmp1 >> SREAL_PART_BITS;
+
+ normalize (r);
+ }
+ #else
+ if (a->sig < SREAL_MIN_SIG || b->sig < SREAL_MIN_SIG)
+ {
+ r->sig = 0;
+ r->exp = -SREAL_MAX_EXP;
+ }
+ else
+ {
+ r->sig = a->sig * b->sig;
+ r->exp = a->exp + b->exp;
+ normalize (r);
+ }
+ #endif
+ return r;
+ }
+
+ /* *R = *A / *B. Return R. */
+
+ sreal *
+ sreal_div (r, a, b)
+ sreal *r;
+ sreal *a;
+ sreal *b;
+ {
+ #if SREAL_PART_BITS < 32
+ unsigned HOST_WIDE_INT tmp, tmp1, tmp2;
+
+ if (b->sig_hi < SREAL_MIN_SIG)
+ {
+ abort ();
+ }
+ else if (a->sig_hi < SREAL_MIN_SIG)
+ {
+ r->sig_hi = 0;
+ r->sig_lo = 0;
+ r->exp = -SREAL_MAX_EXP;
+ }
+ else
+ {
+ /* Since division by the whole number is pretty ugly to write
+ we are dividing by first 3/4 of bits of number. */
+
+ tmp1 = (a->sig_hi << SREAL_PART_BITS) + a->sig_lo;
+ tmp2 = ((b->sig_hi << (SREAL_PART_BITS / 2))
+ + (b->sig_lo >> (SREAL_PART_BITS / 2)));
+ if (b->sig_lo & ((uhwi) 1 << ((SREAL_PART_BITS / 2) - 1)))
+ tmp2++;
+
+ r->sig_lo = 0;
+ tmp = tmp1 / tmp2;
+ tmp1 = (tmp1 % tmp2) << (SREAL_PART_BITS / 2);
+ r->sig_hi = tmp << SREAL_PART_BITS;
+
+ tmp = tmp1 / tmp2;
+ tmp1 = (tmp1 % tmp2) << (SREAL_PART_BITS / 2);
+ r->sig_hi += tmp << (SREAL_PART_BITS / 2);
+
+ tmp = tmp1 / tmp2;
+ r->sig_hi += tmp;
+
+ r->exp = a->exp - b->exp - SREAL_BITS - SREAL_PART_BITS / 2;
+ normalize (r);
+ }
+ #else
+ if (b->sig == 0)
+ {
+ abort ();
+ }
+ else
+ {
+ r->sig = (a->sig << SREAL_PART_BITS) / b->sig;
+ r->exp = a->exp - b->exp - SREAL_PART_BITS;
+ normalize (r);
+ }
+ #endif
+ return r;
+ }
Index: sreal.h
===================================================================
RCS file: sreal.h
diff -N sreal.h
*** /dev/null 1 Jan 1970 00:00:00 -0000
--- sreal.h 2 Feb 2003 16:38:29 -0000
***************
*** 0 ****
--- 1,67 ----
+ /* Definitions for simple data type for positive real numbers.
+ Copyright (C) 2002 Free Software Foundation, Inc.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it under
+ the terms of the GNU General Public License as published by the Free
+ Software Foundation; either version 2, or (at your option) any later
+ version.
+
+ GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+ #ifndef GCC_SREAL_H
+ #define GCC_SREAL_H
+
+ /* SREAL_PART_BITS has to be an even number. */
+ #if (HOST_BITS_PER_WIDE_INT / 2) % 2 == 1
+ #define SREAL_PART_BITS (HOST_BITS_PER_WIDE_INT / 2 - 1)
+ #else
+ #define SREAL_PART_BITS (HOST_BITS_PER_WIDE_INT / 2)
+ #endif
+
+ #define uhwi unsigned HOST_WIDE_INT
+ #define MAX_HOST_WIDE_INT (((uhwi) 1 << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
+
+ #define SREAL_MIN_SIG ((uhwi) 1 << (SREAL_PART_BITS - 1))
+ #define SREAL_MAX_SIG (((uhwi) 1 << SREAL_PART_BITS) - 1)
+ #define SREAL_MAX_EXP (INT_MAX / 4)
+
+ #if SREAL_PART_BITS < 32
+ #define SREAL_BITS (SREAL_PART_BITS * 2)
+ #else
+ #define SREAL_BITS SREAL_PART_BITS
+ #endif
+
+ /* Structure for holding a simple real number. */
+ typedef struct sreal
+ {
+ #if SREAL_PART_BITS < 32
+ unsigned HOST_WIDE_INT sig_lo; /* Significant (lower part). */
+ unsigned HOST_WIDE_INT sig_hi; /* Significant (higher part). */
+ #else
+ unsigned HOST_WIDE_INT sig; /* Significant. */
+ #endif
+ signed int exp; /* Exponent. */
+ } sreal;
+
+ extern void dump_sreal PARAMS ((FILE *, sreal *));
+ extern sreal *sreal_init PARAMS ((sreal *,
+ unsigned HOST_WIDE_INT,
+ signed int));
+ extern HOST_WIDE_INT sreal_to_int PARAMS ((sreal *));
+ extern int sreal_compare PARAMS ((sreal *, sreal *));
+ extern sreal *sreal_add PARAMS ((sreal *, sreal *, sreal *));
+ extern sreal *sreal_sub PARAMS ((sreal *, sreal *, sreal *));
+ extern sreal *sreal_mul PARAMS ((sreal *, sreal *, sreal *));
+ extern sreal *sreal_div PARAMS ((sreal *, sreal *, sreal *));
+
+ #endif