This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Question regarding the "Clean up how cse works" project

Steven Bosscher wrote:

I don't see how I could do the same with the new scheme from the projects
page, which goes like this (quoted from that page):
For arithmetic, each hash table elt has the following slots:

    * Operation. This is an rtx code.
    * Mode.
    * Operands 0, 1 and 2. These point to other hash table elements.

So, if we want to enter (plus:SI (reg:SI 30) (const_int 104)), we first
enter (const_int 104) and find the entry that (reg:SI 30) now points to.
Then we put these elts into operands 0 and 1 of a new elt. We put PLUS
and SI into the new elt.

Registers and mem refs would never be entered into the table as such.
However, the values they contain would be entered. There would be a
table indexed by regno which points at the hash entry for the value in
that reg.

With this new scheme, assuming we record REG_EQUAL notes first, we would
record the mult expression, then the plus expression, and then make the
equivalence entry for reg 82 point to the hash table element for either
the plus or the mult.  The mult and the plus would hash to different
buckets and there wouldn't be any way to equivalence the two (same_value
links are not there, remember? ;-).  Whenever we now see reg 82 and we
want to try to substitute its known value, and substituting the mult
fails, we can't try to substitute the plus because we have no way to find

In summary, I don't believe the idea would actually work very well.
Apparently, cselib roughly follows the suggested implementation from the
projects page, but it just does not deal with this problem at all, because
it does not record anything from REG notes.

That brings me to a few questions:

Does anyone see some way to "fix" the idea in the projects page to make
it possible to equivalence expressions that don't at first look the same?

You need another step of indirection. The hash table elements each contain a pointer to a 'value' structure which is allocated elsewhere, and if you find that the two values A and B you had previously allocated for (plus (foo) (plus (foo) (foo))) and (mult (foo) 3) are identical, you need to have a way to equivalence them by eliminating one of them and changing all pointers from A to point to B instead.
IIRC cselib has exactly this kind of data structure, but lacks code to do the equivalencing.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]