Make ValueEnumerator::print use OS for metadata too. Noticed by inspection.

llvm-svn: 224404

Bitcode: Add METADATA_NODE and METADATA_VALUE

This reflects the typelessness of `Metadata` in the bitcode format,
removing types from all metadata operands.

`METADATA_VALUE` represents a `ValueAsMe

Bitcode: Add METADATA_NODE and METADATA_VALUE

This reflects the typelessness of `Metadata` in the bitcode format,
removing types from all metadata operands.

`METADATA_VALUE` represents a `ValueAsMetadata`, and always has two
fields: the type and the value.

`METADATA_NODE` represents an `MDNode`, and unlike `METADATA_OLD_NODE`,
doesn't store types. It stores operands at their ID+1 so that `0` can
reference `nullptr` operands.

Part of PR21532.

llvm-svn: 224073

show more ...

IR: Split Metadata from Value

Split `Metadata` away from the `Value` class hierarchy, as part of
PR21532. Assembly and bitcode changes are in the wings, but this is the
bulk of the change for the I

IR: Split Metadata from Value

Split `Metadata` away from the `Value` class hierarchy, as part of
PR21532. Assembly and bitcode changes are in the wings, but this is the
bulk of the change for the IR C++ API.

I have a follow-up patch prepared for `clang`. If this breaks other
sub-projects, I apologize in advance :(. Help me compile it on Darwin
I'll try to fix it. FWIW, the errors should be easy to fix, so it may
be simpler to just fix it yourself.

This breaks the build for all metadata-related code that's out-of-tree.
Rest assured the transition is mechanical and the compiler should catch
almost all of the problems.

Here's a quick guide for updating your code:

- `Metadata` is the root of a class hierarchy with three main classes:
`MDNode`, `MDString`, and `ValueAsMetadata`. It is distinct from
the `Value` class hierarchy. It is typeless -- i.e., instances do
*not* have a `Type`.

- `MDNode`'s operands are all `Metadata *` (instead of `Value *`).

- `TrackingVH<MDNode>` and `WeakVH` referring to metadata can be
replaced with `TrackingMDNodeRef` and `TrackingMDRef`, respectively.

If you're referring solely to resolved `MDNode`s -- post graph
construction -- just use `MDNode*`.

- `MDNode` (and the rest of `Metadata`) have only limited support for
`replaceAllUsesWith()`.

As long as an `MDNode` is pointing at a forward declaration -- the
result of `MDNode::getTemporary()` -- it maintains a side map of its
uses and can RAUW itself. Once the forward declarations are fully
resolved RAUW support is dropped on the ground. This means that
uniquing collisions on changing operands cause nodes to become
"distinct". (This already happened fairly commonly, whenever an
operand went to null.)

If you're constructing complex (non self-reference) `MDNode` cycles,
you need to call `MDNode::resolveCycles()` on each node (or on a
top-level node that somehow references all of the nodes). Also,
don't do that. Metadata cycles (and the RAUW machinery needed to
construct them) are expensive.

- An `MDNode` can only refer to a `Constant` through a bridge called
`ConstantAsMetadata` (one of the subclasses of `ValueAsMetadata`).

As a side effect, accessing an operand of an `MDNode` that is known
to be, e.g., `ConstantInt`, takes three steps: first, cast from
`Metadata` to `ConstantAsMetadata`; second, extract the `Constant`;
third, cast down to `ConstantInt`.

The eventual goal is to introduce `MDInt`/`MDFloat`/etc. and have
metadata schema owners transition away from using `Constant`s when
the type isn't important (and they don't care about referring to
`GlobalValue`s).

In the meantime, I've added transitional API to the `mdconst`
namespace that matches semantics with the old code, in order to
avoid adding the error-prone three-step equivalent to every call
site. If your old code was:

MDNode *N = foo();
bar(isa <ConstantInt>(N->getOperand(0)));
baz(cast <ConstantInt>(N->getOperand(1)));
bak(cast_or_null <ConstantInt>(N->getOperand(2)));
bat(dyn_cast <ConstantInt>(N->getOperand(3)));
bay(dyn_cast_or_null<ConstantInt>(N->getOperand(4)));

you can trivially match its semantics with:

MDNode *N = foo();
bar(mdconst::hasa <ConstantInt>(N->getOperand(0)));
baz(mdconst::extract <ConstantInt>(N->getOperand(1)));
bak(mdconst::extract_or_null <ConstantInt>(N->getOperand(2)));
bat(mdconst::dyn_extract <ConstantInt>(N->getOperand(3)));
bay(mdconst::dyn_extract_or_null<ConstantInt>(N->getOperand(4)));

and when you transition your metadata schema to `MDInt`:

MDNode *N = foo();
bar(isa <MDInt>(N->getOperand(0)));
baz(cast <MDInt>(N->getOperand(1)));
bak(cast_or_null <MDInt>(N->getOperand(2)));
bat(dyn_cast <MDInt>(N->getOperand(3)));
bay(dyn_cast_or_null<MDInt>(N->getOperand(4)));

- A `CallInst` -- specifically, intrinsic instructions -- can refer to
metadata through a bridge called `MetadataAsValue`. This is a
subclass of `Value` where `getType()->isMetadataTy()`.

`MetadataAsValue` is the *only* class that can legally refer to a
`LocalAsMetadata`, which is a bridged form of non-`Constant` values
like `Argument` and `Instruction`. It can also refer to any other
`Metadata` subclass.

(I'll break all your testcases in a follow-up commit, when I propagate
this change to assembly.)

llvm-svn: 223802

show more ...

Prologue support

Patch by Ben Gamari!

This redefines the `prefix` attribute introduced previously and
introduces a `prologue` attribute. There are a two primary usecases
that these attributes aim

Prologue support

Patch by Ben Gamari!

This redefines the `prefix` attribute introduced previously and
introduces a `prologue` attribute. There are a two primary usecases
that these attributes aim to serve,

1. Function prologue sigils

2. Function hot-patching: Enable the user to insert `nop` operations
at the beginning of the function which can later be safely replaced
with a call to some instrumentation facility

3. Runtime metadata: Allow a compiler to insert data for use by the
runtime during execution. GHC is one example of a compiler that
needs this functionality for its tables-next-to-code functionality.

Previously `prefix` served cases (1) and (2) quite well by allowing the user
to introduce arbitrary data at the entrypoint but before the function
body. Case (3), however, was poorly handled by this approach as it
required that prefix data was valid executable code.

Here we redefine the notion of prefix data to instead be data which
occurs immediately before the function entrypoint (i.e. the symbol
address). Since prefix data now occurs before the function entrypoint,
there is no need for the data to be valid code.

The previous notion of prefix data now goes under the name "prologue
data" to emphasize its duality with the function epilogue.

The intention here is to handle cases (1) and (2) with prologue data and
case (3) with prefix data.

References
----------

This idea arose out of discussions[1] with Reid Kleckner in response to a
proposal to introduce the notion of symbol offsets to enable handling of
case (3).

[1] http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-May/073235.html

Test Plan: testsuite

Differential Revision: http://reviews.llvm.org/D6454

llvm-svn: 223189

show more ...

Add and use Type::subtypes. NFC.

llvm-svn: 222682

Pass a reference to ValueEnumerator.

NFC. This will just make it easier to use std::unique_ptr in a caller.

llvm-svn: 222170

Revert "IR: MDNode => Value"

Instead, we're going to separate metadata from the Value hierarchy. See
PR21532.

This reverts commit r221375.
This reverts commit r221373.
This reverts commit r221359.

Revert "IR: MDNode => Value"

Instead, we're going to separate metadata from the Value hierarchy. See
PR21532.

This reverts commit r221375.
This reverts commit r221373.
This reverts commit r221359.
This reverts commit r221167.
This reverts commit r221027.
This reverts commit r221024.
This reverts commit r221023.
This reverts commit r220995.
This reverts commit r220994.

llvm-svn: 221711

show more ...

IR: MDNode => Value: Instruction::getAllMetadataOtherThanDebugLoc()

Change `Instruction::getAllMetadataOtherThanDebugLoc()` from a vector of
`MDNode` to one of `Value`. Part of PR21433.

llvm-svn:

IR: MDNode => Value: Instruction::getAllMetadataOtherThanDebugLoc()

Change `Instruction::getAllMetadataOtherThanDebugLoc()` from a vector of
`MDNode` to one of `Value`. Part of PR21433.

llvm-svn: 221167

show more ...

IR: Reorder metadata bitcode serialization, NFC

Enumerate `MDNode`'s operands *before* the node itself, so that the
reader requires less RAUW. Although this will cause different code
paths to be hi

IR: Reorder metadata bitcode serialization, NFC

Enumerate `MDNode`'s operands *before* the node itself, so that the
reader requires less RAUW. Although this will cause different code
paths to be hit in the reader, this should effectively be no
functionality change.

llvm-svn: 220340

show more ...

IR: Remove dead code in metadata bitcode writing, NFC

No one cares how many uses each metadata value has, so don't bother
counting.

llvm-svn: 220337

UseListOrder: Handle self-users

Correctly sort self-users (such as PHI nodes). I added a targeted test
in `test/Bitcode/use-list-order.ll` and the final missing RUN line to
tests in `test/Assembly`

UseListOrder: Handle self-users

Correctly sort self-users (such as PHI nodes). I added a targeted test
in `test/Bitcode/use-list-order.ll` and the final missing RUN line to
tests in `test/Assembly`.

This is part of PR5680.

llvm-svn: 214417

show more ...

UseListOrder: Don't give constant IDs to GlobalValues

Since initializers of GlobalValues are being assigned IDs before
GlobalValues themselves, explicitly exclude GlobalValues from the
constant pool

UseListOrder: Don't give constant IDs to GlobalValues

Since initializers of GlobalValues are being assigned IDs before
GlobalValues themselves, explicitly exclude GlobalValues from the
constant pool. Added targeted test in `test/Bitcode/use-list-order.ll`
and added two more RUN lines in `test/Assembly`.

This is part of PR5680.

llvm-svn: 214368

show more ...

UseListOrder: Visit global values

When predicting use-list order, we visit functions in reverse order
followed by `GlobalValue`s and write out use-lists at the first
opportunity. In the reader, thi

UseListOrder: Visit global values

When predicting use-list order, we visit functions in reverse order
followed by `GlobalValue`s and write out use-lists at the first
opportunity. In the reader, this will translate to *after* the last use
has been added.

For this to work, we actually need to descend into `GlobalValue`s.
Added a targeted test in `use-list-order.ll` and `RUN` lines to the
newly passing tests in `test/Bitcode`.

There are two remaining failures in `test/Bitcode`:

- blockaddress.ll: I haven't thought through how to model the way
block addresses change the order of use-lists (or how to work around
it).

- metadata-2.ll: There's an old-style `@llvm.used` global array here
that I suspect the .ll parser isn't upgrading properly. When it
round-trips through bitcode, the .bc reader *does* upgrade it, so
the extra variable (`i8* null`) has an extra use, and the shuffle
vector doesn't match.

I think the fix is to upgrade old-style global arrays (or reject
them?) in the .ll parser.

This is part of PR5680.

llvm-svn: 214321

show more ...

Reapply "UseListOrder: Order GlobalValue uses after initializers"

This reverts commit r214249, reapplying r214242 and r214243, now that
r214270 has fixed the UB.

llvm-svn: 214271

UseListOrder: Fix undefined behaviour

This commit fixes undefined behaviour that caused the revert in r214249.

The problem was two unsequenced operations on a `DenseMap<>`, giving
different behavio

UseListOrder: Fix undefined behaviour

This commit fixes undefined behaviour that caused the revert in r214249.

The problem was two unsequenced operations on a `DenseMap<>`, giving
different behaviour in GCC and Clang. This:

DenseMap<T*, unsigned> DM;
for (auto &X : ...)
DM[&X] = DM.size() + 1;

should have been:

DenseMap<T*, unsigned> DM;
for (auto &X : ...) {
unsigned Size = DM.size();
DM[&X] = Size + 1;
}

Until r214242, this difference between compilers didn't matter. In
r214242, `OrderMap::LastGlobalValueID` was introduced and compared
against IDs, which in GCC were off-by-one my expectations.

llvm-svn: 214270

show more ...

Revert "UseListOrder: Order GlobalValue uses after initializers"

This reverts commits r214242 and r214243 while I investigate buildbot
failures [1][2][3]. I can't reproduce these failures locally,

Revert "UseListOrder: Order GlobalValue uses after initializers"

This reverts commits r214242 and r214243 while I investigate buildbot
failures [1][2][3]. I can't reproduce these failures locally, so if
anyone can see what I've done wrong, I'd appreciate a note.

[1]: http://lab.llvm.org:8011/builders/llvm-hexagon-elf/builds/9840
[2]: http://lab.llvm.org:8011/builders/clang-hexagon-elf/builds/14981
[3]: http://bb.pgr.jp/builders/cmake-llvm-x86_64-linux/builds/15191

llvm-svn: 214249

show more ...

UseListOrder: Order GlobalValue uses after initializers

To avoid unnecessary forward references, the reader doesn't process
initializers of `GlobalValue`s until after the constant pool has been
proc

UseListOrder: Order GlobalValue uses after initializers

To avoid unnecessary forward references, the reader doesn't process
initializers of `GlobalValue`s until after the constant pool has been
processed, and then in reverse order. Model this when predicting
use-list order. This gets two more Bitcode tests passing with
`llvm-uselistorder`.

Part of PR5680.

llvm-svn: 214242

show more ...

UseListOrder: Create a struct around OrderMap, NFC

llvm-svn: 214241

IR: Create the use-list order shuffle vector in-place

Per David Blaikie's review of r214135, this is a more natural way to
initialize.

llvm-svn: 214184

Bitcode: Correctly compare a Use against itself

Fix the sort of expected order in the reader to correctly return `false`
when comparing a `Use` against itself.

This was caught by test/Bitcode/binar

Bitcode: Correctly compare a Use against itself

Fix the sort of expected order in the reader to correctly return `false`
when comparing a `Use` against itself.

This was caught by test/Bitcode/binaryIntInstructions.3.2.ll, so I'm
adding a `RUN` line using `llvm-uselistorder` for every test in
`test/Bitcode` that passes.

A few tests still fail, so I'll investigate those next.

This is part of PR5680.

llvm-svn: 214157

show more ...

IR: Optimize size of use-list order shuffle vectors

Since we're storing lots of these, save two-pointers per vector with a
custom type rather than using the relatively heavy `SmallVector`.

Part of

IR: Optimize size of use-list order shuffle vectors

Since we're storing lots of these, save two-pointers per vector with a
custom type rather than using the relatively heavy `SmallVector`.

Part of PR5680.

llvm-svn: 214135

show more ...

Bitcode: Serialize (and recover) use-list order

Predict and serialize use-list order in bitcode. This makes the option
`-preserve-bc-use-list-order` work *most* of the time, but this is still
exper

Bitcode: Serialize (and recover) use-list order

Predict and serialize use-list order in bitcode. This makes the option
`-preserve-bc-use-list-order` work *most* of the time, but this is still
experimental.

- Builds a full value-table up front in the writer, sets up a list of
use-list orders to write out, and discards the table. This is a
simpler first step than determining the order from the various
overlapping IDs of values on-the-fly.

- The shuffles stored in the use-list order list have an unnecessarily
large memory footprint.

- `blockaddress` expressions cause functions to be materialized
out-of-order. For now I've ignored this problem, so use-list orders
will be wrong for constants used by functions that have block
addresses taken. There are a couple of ways to fix this, but I
don't have a concrete plan yet.

- When materializing functions lazily, the use-lists for constants
will not be correct. This use case is out of scope: what should the
use-list order be, if it's incomplete?

This is part of PR5680.

llvm-svn: 214125

show more ...

Bitcode: Don't optimize constants when preserving use-list order

`ValueEnumerator::OptimizeConstants()` creates forward references within
the constant pools, which makes predicting constants' use-li

Bitcode: Don't optimize constants when preserving use-list order

`ValueEnumerator::OptimizeConstants()` creates forward references within
the constant pools, which makes predicting constants' use-list order
difficult. For now, just disable the optimization.

This can be re-enabled in the future in one of two ways:

- Enable a limited version of this optimization that doesn't create
forward references. One idea is to categorize constants by their
"height" and make that the top-level sort.

- Enable it entirely. This requires predicting how may times each
constant will be recreated as its operands' and operands' operands'
(etc.) forward references get resolved.

This is part of PR5680.

llvm-svn: 213953

show more ...

IR: Add COMDATs to the IR

This new IR facility allows us to represent the object-file semantic of
a COMDAT group.

COMDATs allow us to tie together sections and make the inclusion of one
dependent o

IR: Add COMDATs to the IR

This new IR facility allows us to represent the object-file semantic of
a COMDAT group.

COMDATs allow us to tie together sections and make the inclusion of one
dependent on another. This is required to implement features like MS
ABI VFTables and optimizing away certain kinds of initialization in C++.

This functionality is only representable in COFF and ELF, Mach-O has no
similar mechanism.

Differential Revision: http://reviews.llvm.org/D4178

llvm-svn: 211920

show more ...

Convert a few loops to use ranges.

llvm-svn: 211089