llvm dev - Jul 2014 - [LLVMdev] Continuing PR5680: preserve order of use lists in bitcode

I'm looking to tackle PR5680 [1].  The primary goal is to prevent
behaviour changes in passes that depend on the order of use lists when
serializing/deserializing the IR to a bitcode file (.bc) between passes.

Here's a quick high-level summary:

  - When writing bitcode, calculate what the use list order will be
    after reading the bitcode.  (Assumption: the order is predictable.)

  - Write a use-list-order-diff in a new (optional) section in the
    bitcode.

  - When reading bitcode, apply the use-list-order-diff to restore the
    original use list order.

A secondary goal is to have the same feature for assembly files (.ll).
How to represent the use-list-order(-diff?) in assembly is a little
unclear, so I'll send an RFC when I get to that point.

My plan is to pick up where Chad's commits (e.g., r146078, r146090,
r146442, and r146531) left off.  If someone has a major concern with the
direction, let me know.

[1]: http://llvm.org/bugs/show_bug.cgi?id=5680

On Tue, Jul 8, 2014 at 4:29 PM, Duncan P. N. Exon Smith <
duncan at exonsmith.com> wrote:
> I'm looking to tackle PR5680 [1].  The primary goal is to prevent
> behaviour changes in passes that depend on the order of use lists when
> serializing/deserializing the IR to a bitcode file (.bc) between passes.
>
> Here's a quick high-level summary:
>
>   - When writing bitcode, calculate what the use list order will be
>     after reading the bitcode.  (Assumption: the order is predictable.)
>
>   - Write a use-list-order-diff in a new (optional) section in the
>     bitcode.
>
>   - When reading bitcode, apply the use-list-order-diff to restore the
>     original use list order.
>
So, it may be totally obvious, but is there a reason not to embed the
observed order of the use list in the bitcode more directly? This seems
quite round-about, and I'm curious why its needed.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140708/99997663/attachment.html>

> On 2014-Jul-08, at 16:48, Chandler Carruth <chandlerc at google.com>
wrote:
> 
> 
>> On Tue, Jul 8, 2014 at 4:29 PM, Duncan P. N. Exon Smith <duncan at
exonsmith.com> wrote:
>> I'm looking to tackle PR5680 [1].  The primary goal is to prevent
>> behaviour changes in passes that depend on the order of use lists when
>> serializing/deserializing the IR to a bitcode file (.bc) between
passes.
>> 
>> Here's a quick high-level summary:
>> 
>>   - When writing bitcode, calculate what the use list order will be
>>     after reading the bitcode.  (Assumption: the order is predictable.)
>> 
>>   - Write a use-list-order-diff in a new (optional) section in the
>>     bitcode.
>> 
>>   - When reading bitcode, apply the use-list-order-diff to restore the
>>     original use list order.
> 
> So, it may be totally obvious, but is there a reason not to embed the
observed order of the use list in the bitcode more directly? This seems quite
round-about, and I'm curious why its needed.
I think it would be harder (for the author *and* the compiler) to
read in the "correct" order on-the-fly.  In particular, I'm not
sure how to do it without explicitly storing full use-lists and
creating forward-refs to fill them up.

So this design (when it's turned on) trades increased writer
complexity for smaller file size and decreased reader complexity.

Make sense?