Re: Solaris bootstrap failure

[Colin Howell <chowell at redhat dot com>]

Sorry for the delayed response.

Bernd Schmidt writes:
> On Tue, 13 Mar 2001, Colin Howell wrote:
> >
> > What exactly went wrong here?  To me, it looks like the root cause of
> > the problem is that cselib_lookup() hashes the expression based on its
> > structure, not on its value.  Therefore when it checks its hash table,
> > it does not check the table entry which actually contains the value of
> > the expression, entry 17.  (The hash value for this entry when it was
> > created was 188, while the hash value for the expression being checked
> > is 183; therefore the expression being checked doesn't hash to the
> > right place!)
> 
> You mean
> 	(zero_extend:SI (reg:QI 9 %o1 [117]))
> 
> has hash value 183, and
> 
> 	(zero_extend:SI (mem/s:QI (plus:SI (reg/v/f:SI 24 %i0 [109])
>         	                           (const_int 8 [0x8])) 100))
> 
> has hash value 188?  That shouldn't happen.  We should have noticed
> that the reg and the mem have the same value, and given them the same
> hash value.

Yup.  Agreed.

hash_rtx() calculates the hash value of both expressions.  Here's how
it computes the hash value of:

(zero_extend:SI (mem/s:QI (plus:SI (reg/v/f:SI 24 %i0 [109])
				   (const_int 8 [0x8])) 100))

	code + mode of (zero_extend:SI ...) = 117 + 4 = 121

	plus code + mode of (mem:QI ...) = 62 + 2 = 64

	plus value number of MEM subexpression = 3

	The sum is 188.

Here's how hash_rtx() computes the hash value of:

(zero_extend:SI (reg:QI 9 %o1 [117]))

	code + mode of (zero_extend:SI ...) = 117 + 4 = 121

	plus code + mode of (reg:QI ...) = 57 + 2 = 59

	plus value number of REG subexpression = 3
	(Note that this is the same value number as that for the MEM
	subexpression above, since they are the same value.)

	The sum is 183.

So we get different hash values from different expressions for the
same value.  Neat, huh?

It looks to me as if it's a mistake to add the REG or MEM code into
the hash value, since for this purpose we only care about what the
value is, not where we got it from.

> What did table entry 7 contain when the first expression is inserted
> into the table?

I'm not sure what you mean by this question.  For the stage2 compiler,
table entry 7 is never used up to the point we care about and is
always NULL.  (It has not been used earlier and then deleted; that
would be represented using a distinct value.)  For the stage1
compiler, table entry 7 gets the following expression from insn 31:

(plus:SI (reg:SI 9 %o1 [117])
    (const_int -21 [0xffffffeb]))

This expression goes in table entry 6 in the stage2 compiler.  It goes 
into entry 7 in the stage1 compiler because entry 6 already has the
following expression, from insn 25:

(plus:SI (reg/f:SI 8 %o0 [110])
    (reg:SI 10 %o2 [113]))

This expression hashes to different values in the stage1 and stage2
compilers, and thus goes in different slots.  In the stage2 compiler
it goes in entry 14.  It hashes to different values in the two
compilers because the first REG is a common subexpression with the
expression (from insn 18):

(lo_sum:SI (value:SI)
    (symbol_ref:SI ("tree_code_type")))

The value number for this expression is generated from its hash code,
which is partly generated from the pointer for the SYMBOL_REF rtx.
The REG expression shares this same value number, which will be
different in the two compilers because the pointer values differ.

> I suspect some kind of problem with the hash algorithm.

If you mean the hash function, I agree.  As you can see, it sounds
rather strange and inconsistent.

> Maybe deletions break the structure of the hash table?

I don't think so.  Deletions can be a problem for this kind of hash
table, but the code seems to correctly handle deleted slots separately
from empty ones.

> The code originally used a different kind of hash table where
> entries were chained in lists; the move to the other implementation
> may have been a bad idea.

Perhaps.

> Thanks for the excellent detective work.

You're welcome.

-- 
Colin Douglas Howell            E-mail:  chowell@redhat.com
Support Engineer                Support line:  (408) 542-9601
Red Hat, Inc.