Re: Solaris bootstrap failure

[Bernd Schmidt <bernds at cambridge dot redhat dot com>]

On Tue, 13 Mar 2001, Colin Howell wrote:

[....]

> In the stage2 compiler, table entry 7 is empty, so the check fails.
> Therefore the hash table lookup has failed for the stage2 compiler,
> and cselib_lookup() also fails.  The stage2 compiler has not found a
> suitable expression that can be substituted for the source expression
> of insn 37.
>
> However, in the stage1 compiler, table entry 7 contains the
> expression:

[....]

> Now the stage1 compiler checks the next hash table entry to use
> according to its open addressing scheme.  This is entry 17, which
> contains a list of two expressions.  In order, these are:
>
> (reg:SI 10 %o2 [113])
>
> (zero_extend:SI (value:QI))
>
> The VALUE rtx here refers to table entry 3, which also has two common
> subexpressions; in order, these are:
>
> (reg:QI 9 %o1 [117])
>
> (mem/s:QI (plus:SI (reg/v/f:SI 24 %i0 [109])
> 		   (const_int 8 [0x8])) 100)
>
> (Table entry 17 is actually the same in both the stage1 and stage2
> compilers, as is table entry 3.)

[....]

> In the stage1 compiler, reload_cse_simplify_set() has now found a
> register which is the same as the source expression, so it changes
> insn 37 to use the register.
>
> ****************************************************************
>
> 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.

What did table entry 7 contain when the first expression is inserted
into the table?  I suspect some kind of problem with the hash algorithm.
Maybe deletions break the structure of the hash table?  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.

Thanks for the excellent detective work.


Bernd