Re: RFC: GIMPLE tuples. Design and implementation proposal

[Diego Novillo <dnovillo at redhat dot com>]

Ian Lance Taylor wrote on 04/10/07 14:13:
> Diego Novillo <dnovillo@redhat.com> writes:
> 
>> Following up on the recent discussion about GIMPLE tuples
>> (http://gcc.gnu.org/ml/gcc/2007-03/msg01126.html), we have summarized
>> our main ideas and implementation proposal in the attached document.
>>
>> This should be enough to get the implementation going, but there will be
>> many details that still need to be addressed.
>>
>> Thoughts/comments on the proposal?
> 
> For purposes of LTO, it is essential that we be able to efficiently
> load the IR during the whole program optimization phase.

Certainly.  Now, is GIMPLE going to be our bytecode?  Or do we want to
invest the time in some other bytecode representation with an eye
towards a future JIT component?

Regardless of that, streaming GIMPLE is certainly something worth
pursuing.  Even if it is just to give us the ability to load IL snippets
and inject them into the optimizers without having to go through all the
intermediate steps.

> Part of that is almost certainly going to mean having some sort of
> index which will tell us whether to load the IR at all--if the
> functions represented in some .o file are rarely called, then we
> should use the .o file as-is, and not try to further optimize it.
> This is not part of the current LTO plan, but I think it is inevitable
> if we are to avoid an hours-long compilation process.
> 
> But there is another part: we need to have an IR which can be very
> quickly loaded into memory for further processing.  When it comes to
> loading IR, there is nothing faster than mmap.  That requires that the
> IR be stored in the .o file in a form which can be used directly when
> it is read in from memory.  And ideally that means no pointer
> swizzling: the IR should be usable when loaded without modification.
> And because the link phase can see arbitrary .o files, we can not use
> the PCH hack of requiring a specific memory address.  So that requires
> an IR which is position independent.
> 
> 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.

> 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
  bb          Use bb->index here
  locus       Not needed.  INSN_LOCATOR.
  block       Likewise.

The operands may get tricky, but perhaps not so much.  We have

a- _DECLs.  These are easily replaced with their UID and a symbol table.
b- SSA_NAMEs.  Just the SSA name version is enough.
c- *_CONST.  They're just a bit pattern, no swizzling required.  But we
may need to define byte ordering.
c- *_REF.  These may be tricky, but we could emit them using a REF table
and just put the index here.

We then reserve the first few bits to distinguish the class of operand
and the remaining bits as the index into the respective table.