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

  - 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.


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?

I've looked more deeply into how values are stored in bitcode.

Here are some notes about how values are stored in bitcode, how reading
affects their use-list-orders, my plan on how to proceed (skip there for
TL;DR), and unresolved questions about future direction.

How values are stored in bitcode

I had a long discussion with Nick about this where he changed several of my core assumptions and feelings about the best way to proceed here. I’d rather he provide his perspective rather me try to repeat it, so poking him on this thread…

Okay, looking forward to hearing what Nick has to say.

I'm on pace to have a working prototype Monday-ish, so I'll continue to
commit incrementally for now. Then we'll have something more concrete to
talk about.


The bitcode side of this is essentially finished. My original plan had
more complex reuse of data structures in `ValueEnumerator`, but the
overhead doesn't seem particularly high so I'm planning to leave it as
is and file a couple of follow-up PRs.

I'll send out a proposal for assembly syntax in a moment.