This was fun to track down

This was fun to track down

[David S. Miller]

Mon Sep 22 22:18:48 1997  David S. Miller  <davem@tanya.rutgers.edu>

	* expmed.c (expand_divmod): If compute_mode is not the same as
	mode, handle the case where convert_modes() causes op1 to no
	longer be a CONST_INT.

--- expmed.c.~1~	Sun Sep  7 18:10:31 1997
+++ expmed.c	Mon Sep 22 22:18:27 1997
@@ -2831,6 +2831,14 @@
     {
       op0 = convert_modes (compute_mode, mode, op0, unsignedp);
       op1 = convert_modes (compute_mode, mode, op1, unsignedp);
+
+      /* convert_modes() may have tossed op1 into a register, so we
+	 absolutely must recompute the following.  */
+      op1_is_constant = GET_CODE (op1) == CONST_INT;
+      op1_is_pow2 = (op1_is_constant
+		     && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
+			  || (! unsignedp
+			      && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1))))));
     }
 
   /* If one of the operands is a volatile MEM, copy it into a register.  */

Re: This was fun to track down

[Jeffrey A Law]

  > +      /* convert_modes() may have tossed op1 into a register, so we
  > +	 absolutely must recompute the following.  */
Minor note for the future -- don't put '()' after the name of a function
in comments or documentation.

I've installed this patch with the minor doc change.
Jeff

Re: This was fun to track down

[Torbjorn Granlund]

	* expmed.c (expand_divmod): If compute_mode is not the same as
	mode, handle the case where convert_modes() causes op1 to no
	longer be a CONST_INT.

Under what circumstances does this happen?
(A test case would be nice.)

Re: This was fun to track down

[David S. Miller]

   Date: Tue, 23 Sep 1997 10:49:27 +0200
   From: Torbjorn Granlund <tege@nada.kth.se>

   Under what circumstances does this happen?  (A test case would be
   nice.)

I first saw the bug in a cross compiler from sparc-linux-gnulibc1 to
sparc64-linux (my patches for sparc64-linux support are in the process
of being merged in still).  Here is a small test case:

struct node {
	struct node *next;
	struct node *sibling;
	int hash;
};

struct node *htable[59];

extern void *alloc(int size);

void divmodbug(int hash, struct node *sib)
{
	struct node *p;

	p = alloc(sizeof(*p));
	p->hash = hash;
	p->sibling = sib;
	p->next = htable[hash % 59];
	htable[hash % 59] = p;
}

(this is just a simplified version of tree_add_hash() in gcc/tree.c as
that was what was originally miscompiled for me)

When compiled with no optimizations on, the following occurs in the
second call to expand_divmod() which is for the statement:

	htable[hash % 59] = p;

In expand_divmod() firstly:

	op1_is_constant is set to 1, since op1 is the '59' CONST_INT
	op1_is_pow2 is set to 0 for obvious reasons

Target is NULL_RTX, optab1 and optab2 are determined, the mode of 59
is smaller than Pmode so compute_mode ends up being a larger mode.

Since compute_mode != mode, convert_modes() is called on both op0 and
op1.  Since for sparc64 target code expanding from a signed 32-bit
mode to a 64-bit unsigned mode (SImode to DImode in this case)
requires an actual instruction, the 59 is thrown into a register and
op1 becomes this reg.

Now op1_is_constant is inaccurate.  Which is why I recompute it right
there, along with op1_is_pow2.  I also note that none of the decisions
already made about the old value of op1_is_constant and op1_is_pow2
need to be undone, so this is why I determined this fix to be
correct.

We then hit the switch statement coming up, specifically at cases
TRUNC_MOD_EXPR & TRUNC_DIV_EXPR.  Here op1_is_constant is tested, and
so is unsignedp, if these are both true (and they were before the fix
for this case) the variable 'd' is set to INTVAL(op1).  What was
amusing in my case was that op1 ended up in a pseudo reg with number
'128' so that is what ended up in 'd'.  Lo' and behold this is an
exact power or 2 and thus the next conditional passes, generating bad
code.

Later,
David "Sparc" Miller
davem@caip.rutgers.edu

Re: This was fun to track down

[Torbjorn Granlund]

That change is wrong.  It is not the right way to fix the observed problem.
Jeff, I think you should take it out again.

I asked for a trigger case, since being the person who wrote expand_divmod,
it makes sense that I fix problems in it.  But I got no test case.

Torbjorn

Re: This was fun to track down

[David S. Miller]

   Date: Tue, 23 Sep 1997 22:41:00 +0200
   From: Torbjorn Granlund <tege@pdc.kth.se>

   That change is wrong.  It is not the right way to fix the observed
   problem.  Jeff, I think you should take it out again.

Could you please tell me what specifically is wrong with the change?

   I asked for a trigger case, since being the person who wrote
   expand_divmod, it makes sense that I fix problems in it.  But I got
   no test case.

Yes, I just got in and read your request and will try to put together
something which reproduces the bug, please be patient.

Later,
David "Sparc" Miller
davem@caip.rutgers.edu

Re: This was fun to track down

[Torbjorn Granlund]

     That change is wrong.  It is not the right way to fix the observed
     problem.  Jeff, I think you should take it out again.

  Could you please tell me what specifically is wrong with the change?

Sure.

1. It seems strange that convert_modes put a constant into a register.
   Maybe that is a bug.
2. If convert_modes is really right, the proper fix to expand_divmod
   would be to avoid calling it when op1 is constant.

Torbjorn

Re: This was fun to track down

[David S. Miller]

   Date: Tue, 23 Sep 1997 22:53:47 +0200
   From: Torbjorn Granlund <tege@pdc.kth.se>

   1. It seems strange that convert_modes put a constant into a register.
      Maybe that is a bug.
   2. If convert_modes is really right, the proper fix to expand_divmod
      would be to avoid calling it when op1 is constant.

What if you are computing an offset from a Pmode ptr (which is the
case in the test case I just sent to this list) and the CONST_INT is
_negative_ and of a smaller mode than Pmode, and the CONST_INT is
SImod and Pmode is DImode (32 and 64 bits respecticaly) on a 64-bit
target?

So I don't see convert_modes() as doing anything wrong, if anything
you could say at best that it is missing an optimization opportunity,
for the case when the CONST_INT is not negative.

For "2" I say that your suggestion is just moving an optimization into
expand_divmod() which really belongs in convert_modes().  And for the
"CONST_INT and negative" case your suggestion would generate incorrect
code on certain targets.

Later,
David "Sparc" Miller
davem@caip.rutgers.edu

Re: This was fun to track down

[Jeffrey A Law]

  In message < 199709232053.WAA03509@squid.pdc.kth.se >you write:
  > 1. It seems strange that convert_modes put a constant into a register.
  >    Maybe that is a bug.
convert_modes has always put a constant into a reg if it couldn't
make find any other way to change the mode of the constant.  This
is nothing new.

I believe this can happen when you need to truncate from one
mode to another, but such truncations are not "nops" -- ie they
need real instructions.

There's probably similar situations when extending a constant
from one mode to another.

I think it's safe to say that convert_modes is doing the correct
thing.


  > 2. If convert_modes is really right, the proper fix to expand_divmod
  >    would be to avoid calling it when op1 is constant.
I don't think you can just avoid the call -- you can't just
operate on constants without any regard to their size.  That's
one of the things that gets us in trouble so often with
64bit targets.


jeff

Re: This was fun to track down

[Jim Wilson]

	  > 2. If convert_modes is really right, the proper fix to expand_divmod
	  >    would be to avoid calling it when op1 is constant.
	I don't think you can just avoid the call -- you can't just
	operate on constants without any regard to their size.

Gcc has two different kinds of conversion routines.

There are routines that convert RTL to RTL, and which will never emit insns.
This includes gen_lowpart and operand_subword.

There are routines that emit the insns that are required if any to convert
one RTL to another RTL.  This includes convert_modes.

These two different kinds of conversion routines are often confused.
The former is equivalent to converting a int to a float via a union, and
the later is equivalent to converting a int to a float via a cast.

I see no reason why expand_divmod needs to call convert_modes in this case.
If we are passed in a constant value, then we should keep the value as a
constant, so that we have a chance of emitting optimized code for the divide.
There is no need to emit insns to perform an actual conversion on the value.
All we need to do is convert the RTL itself, and I don't even think that is
necessary, since a CONST_INT is valid regardless of the mode.

Hence, it looks like expmed.c should be calling gen_lowpart (or something
similar) instead of convert_modes if op1 is a constant.  This will give
better code than the current patch by retaining the constant.

Jim

Re: This was fun to track down

[Jeffrey A Law]

  In message < 199709241957.MAA01872@cygnus.com >you write:
  > I see no reason why expand_divmod needs to call convert_modes in this case.
  > If we are passed in a constant value, then we should keep the value as a
  > constant, so that we have a chance of emitting optimized code for the divide.
  > There is no need to emit insns to perform an actual conversion on the value.
  > All we need to do is convert the RTL itself, and I don't even think that is
  > necessary, since a CONST_INT is valid regardless of the mode.
  > 
  > Hence, it looks like expmed.c should be calling gen_lowpart (or something
  > similar) instead of convert_modes if op1 is a constant.  This will give
  > better code than the current patch by retaining the constant.
Note the following comment in convert_modes; it may apply to any attempt
to use gen_lowpart:

  /* There is one case that we must handle specially: If we are converting
     a CONST_INT into a mode whose size is twice HOST_BITS_PER_WIDE_INT and
     we are to interpret the constant as unsigned, gen_lowpart will do
     the wrong if the constant appears negative.  What we want to do is
     make the high-order word of the constant zero, not all ones.  */

Re: This was fun to track down

[Torbjorn Granlund]

  Note the following comment in convert_modes; it may apply to any attempt
  to use gen_lowpart:

    /* There is one case that we must handle specially: If we are converting
       a CONST_INT into a mode whose size is twice HOST_BITS_PER_WIDE_INT and
       we are to interpret the constant as unsigned, gen_lowpart will do
       the wrong if the constant appears negative.  What we want to do is
       make the high-order word of the constant zero, not all ones.  */

An `unsigned' constant that appears negative should never be generated.
Such constants should use const_double.

I think the gen_lowpart code connected to that comment is wrong.  When that
code went in, I suggested that the bug in the caller that relied on that
bogus behaviour be fixed instead.

Now gcc's constant representation is ambiguous.

Re: This was fun to track down

[Jeffrey A Law]

  In message < 199709272040.WAA16828@squid.pdc.kth.se >you write:
  > An `unsigned' constant that appears negative should never be generated.
  > Such constants should use const_double.
That's the theory.  However, recent conversations with Wilson and
Kenner would tend to indicate otherwise.

Note that I do agree that we shouldn't have this braindamage!  The
way we deal with CONST_INTs is ambigious and, IMHO, should be fixed.


Jeff

Re: This was fun to track down

[Jim Wilson]

>	An `unsigned' constant that appears negative should never be generated.

They are.  See immed_double_const in varasm.c:

      /* If MODE fits within HOST_BITS_PER_WIDE_INT, always use a CONST_INT.

	 ??? Strictly speaking, this is wrong if we create a CONST_INT
	 for a large unsigned constant with the size of MODE being
	 HOST_BITS_PER_WIDE_INT and later try to interpret that constant in a
	 wider mode.  In that case we will mis-interpret it as a negative
	 number.

	 Unfortunately, the only alternative is to make a CONST_DOUBLE
	 for any constant in any mode if it is an unsigned constant larger
	 than the maximum signed integer in an int on the host.  However,
	 doing this will break everyone that always expects to see a CONST_INT
	 for SImode and smaller.

	 We have always been making CONST_INTs in this case, so nothing new
	 is being broken.  */

>	Such constants should use const_double.

This would be nice, however, this means that every port needs to bit fixed
to handle CONST_DOUBLEs everyplace where they currently handle a CONST_INT,
and that would be a great deal of work.  It isn't clear whether fixing this
problem is worthwhile at this time.

>	Now gcc's constant representation is ambiguous.

It has always been ambiguous.  This has primarily been a problem for cross
compilers, but is now starting to affect native compilers too now that mixed
32/64 bit systems are becoming more common, because they share some of the
same traits as cross compilers.  I ran into a number of problems while doing
the irix6 port which is a mixed 32/64 bit system.

Many problems have been fixed over the years by modifying various bits of code
that create CONST_INT and CONST_DOUBLE to create them in particular ways (see
for instance what simplify_binary_operation does at the end, see also
immed_double_const).

Unfortunately there are still cases that are ambiguous.  For instance, on a
machine with a 32 bit HOST_WIDE_INT, given the number 0xffffffff80000000 it
will be represented as (CONST_INT 0x80000000).  If we then pass this to
exact_log2, it returns true, because 0x80000000 has only one bit set.
However, this answer is wrong, because the original number is clearly not
a power of two.  In order to get the right answer, we need to know the mode
of the constant, so we know how to correctly interpret the constant, or
else we need to represent any constant (signed or unsigned) as a CONST_DOUBLE
whenever the high order bit is set.

Jim