Fix mapping of unmaterialized global values during metadata linking

Summary:
The patch to move metadata linking after global value linking didn't
correctly map unmaterialized global values to null a

Fix mapping of unmaterialized global values during metadata linking

Summary:
The patch to move metadata linking after global value linking didn't
correctly map unmaterialized global values to null as desired. They
were in fact mapped to the source copy. It largely worked by accident
since most module linker clients destroyed the source module which
caused the source GVs to be replaced by null, but caused a failure with
LTO linking on Windows:
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20151109/312869.html

The problem is that a null return value from materializeValueFor is
handled by mapping the value to self. This is the desired behavior when
materializeValueFor is passed a non-GlobalValue. The problem is how to
distinguish that case from the case where we really do want to map to
null.

This patch addresses this by passing in a new flag to the value mapper
indicating that unmapped global values should be mapped to null. Other
Value types are handled as before.

Note that the documented behavior of asserting on unmapped values when
the flag RF_IgnoreMissingValues isn't set is currently disabled with
FIXME notes due to bootstrap failures. I modified these disabled asserts
so when they are eventually enabled again it won't assert for the
unmapped values when the new RF_NullMapMissingGlobalValues flag is set.

I also considered using a callback into the value materializer, but a
flag seemed cleaner given that there are already existing flags.
I also considered modifying materializeValueFor to return the input
value when we want to map to source and then treat a null return
to mean map to null. However, there are other value materializer
subclasses that implement materializeValueFor, and they would all need
to be audited and the return values possibly changed, which seemed
error-prone.

Reviewers: dexonsmith, joker.eph

Subscribers: pcc, llvm-commits

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

llvm-svn: 253170

show more ...

[opaque pointer type]: Pass explicit pointee type when building a constant GEP.

Gets a bit tricky in the ValueMapper, of course - not sure if we should
just expose a list of explicit types for each

[opaque pointer type]: Pass explicit pointee type when building a constant GEP.

Gets a bit tricky in the ValueMapper, of course - not sure if we should
just expose a list of explicit types for each Value so that the
ValueMapper can be neutral to these special cases (it's OK for things
like load, where the explicit type is the result type - but when that's
not the case, it means plumbing through another "special" type... )

llvm-svn: 245728

show more ...

ValueMapper: Resolve uniquing cycles more aggressively

As a follow-up to r244181, resolve uniquing cycles underneath distinct
nodes on the fly. This prevents uniquing cycles in early operands from

ValueMapper: Resolve uniquing cycles more aggressively

As a follow-up to r244181, resolve uniquing cycles underneath distinct
nodes on the fly. This prevents uniquing cycles in early operands from
affecting later operands. It also removes an iteration through distinct
nodes' operands.

No real functional change here, just more prompt resolution of temporary
nodes.

llvm-svn: 244302

show more ...

ValueMapper: Pull out helper to resolve cycles, NFC

Pull out a helper for resolving uniquing cycles of `Metadata` to remove
the boiler-plate of downcasting to `MDNode`.

llvm-svn: 244301

ValueMapper: Rotate distinct node remapping algorithm

Rotate the algorithm for remapping distinct nodes in order to simplify
how uniquing cycles get resolved. This removes some of the recursion,
an

ValueMapper: Rotate distinct node remapping algorithm

Rotate the algorithm for remapping distinct nodes in order to simplify
how uniquing cycles get resolved. This removes some of the recursion,
and, most importantly, exposes all uniquing cycles at the top-level.
Besides being a little more efficient -- temporary MDNodes won't live as
long -- the clearer logic should help protect against bugs like those
fixed in r243961 and r243976.

What are uniquing cycles? Why do they present challenges when remapping
metadata?

!0 = !{!1}
!1 = !{!0}

!0 and !1 form a simple uniquing cycle. When remapping from one
metadata graph to another, every uniquing cycle gets "duplicated"
through a dance:

!0-temp = !{!1?} ; map(!0): clone !0, VM[!0] = !0-temp
!1-temp = !{!0?} ; ..map(!1): clone !1, VM[!1] = !1-temp
!1-temp = !{!0-temp} ; ..map(!1): remap !1's operands
!2 = !{!0-temp} ; ..map(!1): uniquify: !1-temp => !2
!0-temp = !{!2} ; map(!0): remap !0's operands
!3 = !{!2} ; map(!0): uniquify: !0-temp => !3

; Result
!2 = !{!3}
!3 = !{!2}

(In the two "uniquify" steps above, the operands of !X-temp are compared
to the operands of !X. If they're the same, then !X-temp gets RAUW'ed
to !X; if they're different, then !X-temp is promoted to a new unique
node. The latter case always hits in for uniquing cycles, so we
duplicate all the nodes involved.)

Why is this a problem? Uniquable Metadata nodes that have temporary
node as transitive operands keep RAUW support until the temporary nodes
get finalized. With non-cycles, this happens automatically: when a
uniquable node's count of unresolved operands drops to zero, it
immediately sheds its own RAUW support (possibly triggering the same in
any node that references it). However, uniquing cycles create a
reference cycle, and uniqued nodes that transitively reference a
uniquing cycle are "stuck" in an unresolved state until someone calls
`MDNode::resolveCycles()` on a node in the unresolved subgraph.

Distinct nodes should help here (and mostly do): since they aren't
uniqued anywhere, they are guaranteed not to be RAUW'ed. They
effectively form a barrier between uniqued nodes, breaking some uniquing
cycles, and shielding uniqued nodes from uniquing cycles.

Unfortunately, with this barrier in place, the unresolved subgraph(s)
can be disjoint from the top-level node. The mapping algorithm needs to
find at least one representative from each disjoint subgraph. But which
nodes are *stuck*, and which will get resolved automatically? And which
nodes are in the unresolved subgraph? The old logic was conservative.

This commit rotates the logic for distinct nodes, so that we have access
to unresolved nodes at the top-level call to `llvm::MapMetadata()`.
Each time we return to the top-level, we know that all temporaries have
been RAUW'ed away. Here, it's safe (and necessary) to call
`resolveCycles()` immediately on unresolved operands.

This should also perform better than the old algorithm. The recursion
stack is shorter, temporary nodes don't live as long, and there are
fewer tracking references to unresolved nodes. As the debug info graph
introduces more 'distinct' nodes, remapping should incrementally get
cheaper and cheaper.

Aside from possible performance improvements (and reduced cruft in the
`LLVMContext`), there should be no functionality change here.

llvm-svn: 244181

show more ...

ValueMapper: Simplify remap() helper function, NFC

Rename `remap()` to `remapOperands()`, and restrict its contract to
remapping operands. Previously, it also called `mapToMetadata()`, but
this log

ValueMapper: Simplify remap() helper function, NFC

Rename `remap()` to `remapOperands()`, and restrict its contract to
remapping operands. Previously, it also called `mapToMetadata()`, but
this logic is hard to reason about externally. In particular, this
refactors `mapUniquedNode()` to avoid redundant mapping calls, taking
advantage of the RAUWs that are already in place.

llvm-svn: 244168

show more ...

Fix 80-column

llvm-svn: 243977

Linker: Fix ASan failure from r243961

r243883 and r243961 made a use-after-free far more likely:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/6041/steps/check-llvm%20asan/log

Linker: Fix ASan failure from r243961

r243883 and r243961 made a use-after-free far more likely:
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/6041/steps/check-llvm%20asan/logs/stdio

Unresolved nodes get inserted into the `Cycles` array. If they later
get resolved through RAUW, we need to update the reference. It's
interesting that this never hit before (maybe an asan-ified clang
bootstrap with `-flto -g` would have hit it, but I admit I haven't tried
anything quite that crazy).

llvm-svn: 243976

show more ...

Linker: Fix references to uniqued nodes after r243883

r243883 started moving 'distinct' nodes instead of duplicated them in
lib/Linker. This had the side-effect of sometimes not cloning uniqued
nod

Linker: Fix references to uniqued nodes after r243883

r243883 started moving 'distinct' nodes instead of duplicated them in
lib/Linker. This had the side-effect of sometimes not cloning uniqued
nodes that reference them. I missed a corner case:

!named = !{!0}
!0 = !{!1}
!1 = distinct !{!0}

!0 is the entry point for "remapping", and a temporary clone (say,
!0-temp) is created and mapped in case we need to model a uniquing
cycle.

Recursive descent into !1. !1 is distinct, so we leave it alone,
but update its operand to !0-temp.

Pop back out to !0. Its only operand, !1, hasn't changed, so we don't
need to use !0-temp. !0-temp goes out of scope, and we're finished
remapping, but we're left with:

!named = !{!0}
!0 = !{!1}
!1 = distinct !{null} ; uh oh...

Previously, if !0 and !0-temp ended up with identical operands, then
!0-temp couldn't have been referenced at all. Now that distinct nodes
don't get duplicated, that assumption is invalid. We need to
!0-temp->replaceAllUsesWith(!0) before freeing !0-temp.

I found this while running an internal `-flto -g` bootstrap. Strangely,
there was no case of this in the open source bootstrap I'd done before
commit...

llvm-svn: 243961

show more ...

Linker: Move distinct MDNodes instead of cloning

Instead of cloning distinct `MDNode`s when linking in a module, just
move them over. The module linker destroys the source module, so the
old node w

Linker: Move distinct MDNodes instead of cloning

Instead of cloning distinct `MDNode`s when linking in a module, just
move them over. The module linker destroys the source module, so the
old node would otherwise just be leaked on the context. Create the new
node in place. This also reduces the number of cloned uniqued nodes
(since it's less likely their operands have changed).

This mapping strategy is only correct when we're discarding the source,
so the linker turns it on via a ValueMapper flag, `RF_MoveDistinctMDs`.

There's nothing observable in terms of `llvm-link` output here: the
linked module should be semantically identical.

I'll be adding more 'distinct' nodes to the debug info metadata graph in
order to break uniquing cycles, so the benefits of this will partly come
in future commits. However, we should get some gains immediately, since
we have a fair number of 'distinct' `DILocation`s being linked in.

llvm-svn: 243883

show more ...

ValueMapper: Only check for cycles if operands change

This is a minor optimization to only check for unresolved operands
inside `mapDistinctNode()` if the operands have actually changed. This
shoul

ValueMapper: Only check for cycles if operands change

This is a minor optimization to only check for unresolved operands
inside `mapDistinctNode()` if the operands have actually changed. This
shouldn't really cause any change in behaviour. I didn't actually see a
slowdown in a profile, I was just poking around nearby and saw the
opportunity.

llvm-svn: 243866

show more ...

ValueMapper: Use a range-based for, NFC

llvm-svn: 243865

ValueMapper: Reuse local variable, NFC

llvm-svn: 243864

[opaque pointer type] Explicitly store the pointee type of the result of a GEP

Alternatively, this type could be derived on-demand whenever
getResultElementType is called - if someone thinks that's

[opaque pointer type] Explicitly store the pointee type of the result of a GEP

Alternatively, this type could be derived on-demand whenever
getResultElementType is called - if someone thinks that's the better
choice (simple time/space tradeoff), I'm happy to give it a go.

llvm-svn: 238716

show more ...

[opaque pointer type] Track explicit GEP pointee type through in-memory IR

llvm-svn: 236510

[opaque pointer type] Store the value type of an alloca

llvm-svn: 236175

Recommit r235458: [opaque pointer type] Avoid using PointerType::getElementType for a few cases of CallInst

(reverted in r235533)

Original commit message:

"Calls to llvm::Value::mutateType are bec

Recommit r235458: [opaque pointer type] Avoid using PointerType::getElementType for a few cases of CallInst

(reverted in r235533)

Original commit message:

"Calls to llvm::Value::mutateType are becoming extra-sensitive now that
instructions have extra type information that will not be derived from
operands or result type (alloca, gep, load, call/invoke, etc... ). The
special-handling for mutateType will get more complicated as this work
continues - it might be worth making mutateType virtual & pushing the
complexity down into the classes that need special handling. But with
only two significant uses of mutateType (vectorization and linking) this
seems OK for now.

Totally open to ideas/suggestions/improvements, of course.

With this, and a bunch of exceptions, we can roundtrip an indirect call
site through bitcode and IR. (a direct call site is actually trickier...
I haven't figured out how to deal with the IR deserializer's lazy
construction of Function/GlobalVariable decl's based on the type of the
entity which means looking through the "pointer to T" type referring to
the global)"

The remapping done in ValueMapper for LTO was insufficient as the types
weren't correctly mapped (though I was using the post-mapped operands,
some of those operands might not have been mapped yet so the type
wouldn't be post-mapped yet). Instead use the pre-mapped type and
explicitly map all the types.

llvm-svn: 235651

show more ...

Revert "[opaque pointer type] Avoid using PointerType::getElementType for a few cases of CallInst"

This reverts commit r235458.

It looks like this might be breaking something LTO-ish. Looking into

Revert "[opaque pointer type] Avoid using PointerType::getElementType for a few cases of CallInst"

This reverts commit r235458.

It looks like this might be breaking something LTO-ish. Looking into it
& will recommit with a fix/test case/etc once I've got more to go on.

llvm-svn: 235533

show more ...

[opaque pointer type] Avoid using PointerType::getElementType for a few cases of CallInst

Calls to llvm::Value::mutateType are becoming extra-sensitive now that
instructions have extra type informat

[opaque pointer type] Avoid using PointerType::getElementType for a few cases of CallInst

Calls to llvm::Value::mutateType are becoming extra-sensitive now that
instructions have extra type information that will not be derived from
operands or result type (alloca, gep, load, call/invoke, etc... ). The
special-handling for mutateType will get more complicated as this work
continues - it might be worth making mutateType virtual & pushing the
complexity down into the classes that need special handling. But with
only two significant uses of mutateType (vectorization and linking) this
seems OK for now.

Totally open to ideas/suggestions/improvements, of course.

With this, and a bunch of exceptions, we can roundtrip an indirect call
site through bitcode and IR. (a direct call site is actually trickier...
I haven't figured out how to deal with the IR deserializer's lazy
construction of Function/GlobalVariable decl's based on the type of the
entity which means looking through the "pointer to T" type referring to
the global)

llvm-svn: 235458

show more ...

MapMetadata: Allow unresolved metadata if it won't change

Allow unresolved nodes through the `MapMetadata()` if
`RF_NoModuleLevelChanges`, since there's no remapping to do anyway.

This fixes PR2292

MapMetadata: Allow unresolved metadata if it won't change

Allow unresolved nodes through the `MapMetadata()` if
`RF_NoModuleLevelChanges`, since there's no remapping to do anyway.

This fixes PR22929. I'll add a clang test as a follow-up.

llvm-svn: 232449

show more ...

Utils: Resolve cycles under distinct MDNodes

Track unresolved nodes under distinct `MDNode`s during `MapMetadata()`,
and resolve them at the end. Previously, these cycles wouldn't get
resolved.

ll

Utils: Resolve cycles under distinct MDNodes

Track unresolved nodes under distinct `MDNode`s during `MapMetadata()`,
and resolve them at the end. Previously, these cycles wouldn't get
resolved.

llvm-svn: 228180

show more ...

IR: Move MDNode clone() methods from ValueMapper to MDNode, NFC

Now that the clone methods used by `MapMetadata()` don't do any
remapping (and return a temporary), they make more sense as member
fun

IR: Move MDNode clone() methods from ValueMapper to MDNode, NFC

Now that the clone methods used by `MapMetadata()` don't do any
remapping (and return a temporary), they make more sense as member
functions on `MDNode` (and subclasses).

llvm-svn: 226541

show more ...

IR: Introduce GenericDwarfNode

As part of PR22235, introduce `DwarfNode` and `GenericDwarfNode`. The
former is a metadata node with a DWARF tag. The latter matches our
current (generic) schema of

IR: Introduce GenericDwarfNode

As part of PR22235, introduce `DwarfNode` and `GenericDwarfNode`. The
former is a metadata node with a DWARF tag. The latter matches our
current (generic) schema of a header with string (and stringified
integer) data and an arbitrary number of operands.

This doesn't move it into place yet; that change will require a large
number of testcase updates.

llvm-svn: 226529

show more ...

IR: Merge UniquableMDNode back into MDNode, NFC

As pointed out in r226501, the distinction between `MDNode` and
`UniquableMDNode` is confusing. When we need subclasses of `MDNode`
that don't use al

IR: Merge UniquableMDNode back into MDNode, NFC

As pointed out in r226501, the distinction between `MDNode` and
`UniquableMDNode` is confusing. When we need subclasses of `MDNode`
that don't use all its functionality it might make sense to break it
apart again, but until then this makes the code clearer.

llvm-svn: 226520

show more ...

Utils: Simplify MapMetadata(), NFC

Extract out the operand remapping loops, which are now very similar.

llvm-svn: 226515