[LLVMdev] Use-list order assembly declarations for PR20515

[Duncan P. N. Exon Smith]

I'm now looking at implementing `-preserve-ll-use-list-order` (PR20515)
to preserve use-list order when round-tripping to assembly -- the
counterpart to `-preserve-bc-use-list-order`.

After a quick look at `LLParser` and `AssemblyWriter`, I believe we can
use the same technique as for bitcode.  In particular, we can predict in
`AssemblyWriter` how use-lists will look in the `LLParser` and write out
use-list-order directives to be processed as they're seen.

There are a couple of bike sheds to paint.

Use-list-order directives
=========================

A use-list order directive needs to reference a `Value` with users and
describe how to reorder it.  Here's my proposed syntax:

    uselistorder <ty> <value>, { <order-indexes> }

Example assembly
----------------

Following is a simple module with some examples.  For demonstration
purposes, I've given a directive to every value that has multiple users.

    @global = global i32 7
    @alias = alias i32* @global
    @global2 = global i32* @global

    define void @foo(i32 %arg1, i32 %arg2) {
    entry:
      %call1 = call i32 @bar(i32 %arg1)
      %call2 = call i32 @bar(i32 %arg2)
      %cmp = icmp lt i32 %call1, %call2
      br i1 %cmp, label %0, label %named

    ; <label %0>:
      %loaded = load i32* @global
      %sum = add i32 %loaded, %arg1
      %product = mul i32 %sum, 7
      br label %named

    named:
      %val = phi i32 [ %arg1, %named ], [ %product, %0 ]
      ret %val

    ; local uselistorders for @foo
      uselistorder i32 %arg1, { 1, 0, 2 }
      uselistorder label %0, { 2, 0, 1 }
      uselistorder label %named, { 1, 0 }
    }
    declare i32 @bar(i32);

    ; global uselistorders
    uselistorder i32* @global, { 1, 2, 0 }
    uselistorder i32 7, { 1, 0 }
    uselistorder i32 (i32) @bar, { 1, 0 }

Semantics
---------

I propose using the same semantics as in the bitcode.  The order-indexes
are assigned to each `Use` in order, then the `Use`s are sorted
according to their indexes.  The directives would be applied immediately
on parse.

Failure conditions
==================

There are a few ways that a `uselistorder` can fail:

  - Referenced value is not yet defined.
  - Referenced value has the wrong type.
  - Referenced value has the wrong number of uses.
  - Order indexes form a no-op (already in order).

Should these failures be warnings or errors?  I think they should all be
errors.  This makes it more difficult to hand-modify assembly with
`uselistorder` directives, but if someone is modifying the assembly they
should strip out the `uselistorder` directives anyway.

Use-lists of basic blocks that escape
=====================================

Typical basic blocks sort their use-lists via `uselistorder` directives
at function scope.  The example above shows a couple of those.

However, basic blocks whose addresses are taken via `blockaddress`
expressions need special treatment because `LLParser` won't have seen
all the uses by the end of the function definition.  Their
`uselistorder` directives need to be after the last `Use` has been
parsed.

I propose the following syntax for non-local directives for basic
blocks:

    uselistorderbb @function, %block, { <order-indexes> }

For example:

    uselistorderbb @foo, %bb, { 0, 1, 5, 3, 2, 4 }
    uselistorderbb @foo, %12, { 0, 1, 5, 3, 2, 4 }