Re: [PATCH] Improve integer division on IA-64

[Roger Sayle <roger at eyesopen dot com>]

Hi Richard,

On Fri, 23 Dec 2005, Roger Sayle wrote:
> Interestingly, the distributions I generate appear to contradict
> your alpha findings that x/10 is extremely common.  From my testing
> __udivdi by 32 is by far the most common operation in my workload,
> and divisions by 10 are rarer than divisions by 72!

Investigating even further, and guessing your typical workload :),
I believe I may have discovered the source of your large number of
divisions by 10.  Changing the set of source files I was feeding
cc1 suddenly resulted in large numbers of divisions with identical
operands:

udivdi3: 18446744073709551606 10

After fun in gdb trying to deal with LD_PRELOAD, I discovered that
the culprit is libcpp/expr.c:cpp_interpret_integer.  Everytime the
C/C++ preprocessor processes a number larger than a single digit it
calculates a value "max" at which it should start worrying about
overflow.  This didn't show up in my earlier investigations as I
was using preprocessed source files that could be fed directly to
cc1 without include paths, etc...


I'm not sure whether its better to tweak GCC or improve __divdi3,
but there are a number of possible fixes.  One is to move the
calculation of max a little earlier into the earlier clauses that
set base.

i.e. from

      if ((type & CPP_N_RADIX) == CPP_N_OCTAL)
        {
          base = 8;
          p++;
        }
      else if ((type & CPP_N_RADIX) == CPP_N_HEX)
        {
          base = 16;
          p += 2;
        }

      /* We can add a digit to numbers strictly less than this without
         needing the precision and slowness of double integers.  */
      max = ~(cpp_num_part) 0;
      if (precision < PART_PRECISION)
        max >>= PART_PRECISION - precision;
      max = (max - base + 1) / base + 1;

into

      max = ~(cpp_num_part) 0;
      if (precision < PART_PRECISION)
        max >>= PART_PRECISION - precision;
      if ((type & CPP_N_RADIX) == CPP_N_OCTAL)
        {
	  max = (max - 7) / 8 + 1;
          base = 8;
          p++;
        }
      else if ((type & CPP_N_RADIX) == CPP_N_HEX)
        {
	  max = (max - 15) / 16 + 1;
          base = 16;
          p += 2;
        }
      else
	max = (max - 9) / 10 + 1;


But an even better alternative is to realize that PART_PRECISION is
a compile-time constant, and CPP_OPTION (pfile, precision) is a
run-time constant, meaning that max8, max10 and max16 should all be
constants across a compilation unit and could be calculated once
and stored in cpp_reader (or statically).


Roger
--