This is the mail archive of the gcc@gcc.gnu.org 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: RFC: GIMPLE tuples. Design and implementation proposal


2007/4/10, Dave Korn <dave.korn@artimi.com> wrote:
On 10 April 2007 20:02, Diego Novillo wrote:

>> The obvious way to make the proposed tuples position independent would
>> be to use array offsets rather than pointers.  This has the obvious
>> disadvantage that every access through a pointer requires an
>> additional memory reference.  On the other hand, it has some other
>> advantages: it may no longer be necessary to keep a previous pointer
>
> I doubt this.  We had started with single-linked chains but reverse
> traversals do occur, and they were very painful and slow.

Reverse-traversing an array really isn't all that painful or slow!

>> in each tuple; we can delete tuples by marking them with a deleted
>> code, and we can periodically garbage collect deleted tuples and fix
>> up the next pointers.  On a 64-bit system, we do not need to burn 64
>> bits for each pointer; 32 bits will be sufficient for an array offset.
>>
>> I would like us to seriously think about this approach.  Most of the
>> details would be hidden by accessor macros when it comes to actual
>> coding.  The question is whether we can tolerate some slow down for
>> normal processing in return for a benefit to LTO.
>>
>> If anybody can see how to get the best of both worlds, that would of
>> course be even better.
>
> I've thought about this a little bit and it may not be all that onerous.
>  So, if you take the components of a tuple:
>
>   next        Could be a UID to the next tuple
>   prev        Likewise


How about delta-linked lists? Makes your iterators bigger, but makes every single node smaller.

    cheers,
      DaveK
--
Can't think of a witty .sigline today....



delta-linked lists? Better one iterator than complicating this with several iterators.

Function prev_of_this_instruction(word) -> word

The singleton (global structure) of prev_of_this_instruction
contains a small cache to accelerate the reverse-traversing.

This cache is like a hashmap of { word this instruction => word prev
instruction }.
If this instruction isn't in the cache then go to the beginning of a BB of this
instruction and start to traverse adding pointers to the cache.
Use LRU/old-age-used/less-frequently-used to replace their entries.

To have many smaller nodes in the heap is better.

J.C. Pizarro :)


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