The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling).

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

llvm-svn: 267231

E.g. for:

  !1 = {"llvm.distribute", i32 1}

it now returns the MDOperand for 1.

I will use this in LoopDistribution to check the value of the metadata.

Note that the change is backward-compatible with its current use in
LoopVersioningLICM.  An Optional implicitly converts to a bool depending
whether it contains a value or not.

llvm-svn: 267190

Summary:
CachingMemorySSAWalker::invalidateInfo was using IsCall to determine
which cache map needed to be cleared of entries referring to the invalidated
MemoryAccess, but there could also be entries referring to it in the
other cache map (value entries, not key entries).  This change just
clears both tables to be conservatively correct.

Also add a verifyRemoved() function, called when expensive
checks (i.e. XDEBUG) are enabled to verify that the invalidated
MemoryAccess object is not referenced in any of the caches.

Reviewers: dberlin, george.burgess.iv

Subscribers: mcrosier, llvm-commits

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

llvm-svn: 267157

This reverts commit r267022, due to an ASan failure:

  http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549

llvm-svn: 267115

Re-layer the functions in the new (i.e., newly correct) post-order
traversals in ValueEnumerator (r266947) and ValueMapper (r266949).
Instead of adding a node to the worklist in a helper function and
returning a flag to say what happened, return the node itself.  This
makes the code way cleaner: the worklist is local to the main function,
there is no flag for an early loop exit (since we can cleanly bury the
loop), and it's perfectly clear when pointers into the worklist might be
invalidated.

I'm fixing both algorithms in the same commit to avoid repeating the
commit message; if you take the time to understand one the other should
be easy.  The diff itself isn't entirely obvious since the traversals
have some noise (i.e., things to do), but here's the high-level change:

    auto helper = [&WL](T *Op) {     auto helper = [](T **&I, T **E) {
                                 =>    while (I != E) {
      if (shouldVisit(Op)) {             T *Op = *I++;
        WL.push(Op, Op->begin());        if (shouldVisit(Op)) {
        return true;                       return Op;
      }                                }
      return false;                    return nullptr;
    };                               };
                                 =>
    WL.push(S, S->begin());          WL.push(S, S->begin());
    while (!empty()) {               while (!empty()) {
      auto *N = WL.top().N;            auto *N = WL.top().N;
      auto *&I = WL.top().I;           auto *&I = WL.top().I;
      bool DidChange = false;
      while (I != N->end())
        if (helper(*I++)) {      =>    if (T *Op = helper(I, N->end()) {
          DidChange = true;              WL.push(Op, Op->begin());
          break;                         continue;
        }                              }
      if (DidChange)
        continue;

      POT.push(WL.pop());        =>    POT.push(WL.pop());
    }                                }

Thanks to Mehdi for helping me find a better way to layer this.

llvm-svn: 267099

This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations.

The bisection is enabled using a new command line option (-opt-bisect-limit).  Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit.  A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used.

The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check.  Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute.  A new function call has been added for module and SCC passes that behaves in a similar way.

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

llvm-svn: 267022

llvm-svn: 267016

These ensure that operand array has at least one element and it is the
self-reference.

llvm-svn: 267015

The decl is in LoopUtils.h.  I think that this was added to
LoopVersioningLICM.cpp by mistake.

llvm-svn: 267014

Summary:
`llvm.guard(false)` always bails out of the current compilation unit, so
we can prune any control flow following it.

Reviewers: hfinkel, pcc, reames

Subscribers: majnemer, reames, mcrosier, llvm-commits

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

llvm-svn: 266955

The iteratitive algorithm from r265456 claimed but failed to create a
post-order traversal.  It had the same error that was fixed in the
ValueEnumerator in r266947: now, instead of pushing all operands on the
worklist at once, we pause whenever an operand gets pushed in order to
go depth-first (I know, it sounds obvious).

Sadly, I have no idea how to observe this from outside the algorithm and
so I haven't written a test.  The output should be the same; it should
just use fewer temporary nodes now.  I've added some comments that I
hope make the current logic clear enough it's unlikely to regress.

llvm-svn: 266949

Phabricator Revision: http://reviews.llvm.org/D19277

llvm-svn: 266904

Summary:
This patch prevents importing from (and therefore exporting from) any
module with a "llvm.used" local value. Local values need to be promoted
and renamed when importing, and their presense on the llvm.used variable
indicates that there are opaque uses that won't see the rename. One such
example is a use in inline assembly.

See also the discussion at:
http://lists.llvm.org/pipermail/llvm-dev/2016-April/098047.html

As part of this, move collectUsedGlobalVariables out of Transforms/Utils
and into IR/Module so that it can be used more widely. There are several
other places in LLVM that used copies of this code that can be cleaned
up as a follow on NFC patch.

Reviewers: joker.eph

Subscribers: pcc, llvm-commits, joker.eph

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

llvm-svn: 266877

This linkage is *not* intended to express that a declaration refers
to a weak symbol, but that the symbol might not be present at link
time. I don't believe it was the intent.

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 266856

This patch improves SimplifyCFG to catch cases like:

  if (a < b) {
    if (a > b) <- known to be false
      unreachable;
  }

Phabricator Revision: http://reviews.llvm.org/D18905

llvm-svn: 266767

Summary:
Need to use predecessors for reverse graph, successors for forward graph.
succ_iterator/pred_iterator are not compatible, this patch is all the work necessary to work around that (which is what everywhere else does).  Not sure if there is a better way, so cc'ing some random folks to take a gander :)

Reviewers: dblaikie, qcolombet, echristo

Subscribers: llvm-commits

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

llvm-svn: 266718

Removed some unused headers, replaced some headers with forward class declarations.

Found using simple scripts like this one:
clear && ack --cpp -l '#include "llvm/ADT/IndexedMap.h"' | xargs grep -L 'IndexedMap[<]' | xargs grep -n --color=auto 'IndexedMap'

Patch by Eugene Kosov <claprix@yandex.ru>

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

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 266595

This catches two nullptr insertions into the ValueMap I missed in
r266567.  I missed CloneFunction becuase it never calls RemapInstruction
directly.  Here's one of the still-failing bots:
  http://lab.llvm.org:8011/builders/clang-x64-ninja-win7/builds/11496

llvm-svn: 266570

Add an assertion to ValueMapper that prevents double-scheduling of
GlobalValues to remap, and fix the one place it happened.  There are
tons of tests that fail with this assertion in place and without the
code change, so I'm not adding another.

Although it looks related, r266563 was, indeed, removing dead code.
AFAICT, this cross-file double-scheduling started in r266510 when the
cross-file recursion was removed.

llvm-svn: 266569

Apparently there isn't test coverage for all of these.  I'd appreciate
if someone with could reproduce and send me something to reduce, but for
now I've just looked for users of RemapInstruction and MapValue and
ensured they don't accidentally insert nullptr.  Here is one of the
bootstraps that caught:

  http://lab.llvm.org:8011/builders/clang-x64-ninja-win7/builds/11494

llvm-svn: 266567

As a follow-up to r123058, assert that there are no null mappings in the
ValueMap instead of just ignoring them when they are there.  There were
a couple of accidental insertions in CloneFunction so I cleaned those up
(caught by testcases).

llvm-svn: 266565

Rather than relying on the structural equivalence of DICompositeType to
merge type definitions, use an explicit map on the LLVMContext that
LLParser and BitcodeReader consult when constructing new nodes.
Each non-forward-declaration DICompositeType with a non-empty
'identifier:' field is stored/loaded from the type map, and the first
definiton will "win".

This map is opt-in: clients that expect ODR types from different modules
to be merged must call LLVMContext::ensureDITypeMap.

  - Clients that just happen to load more than one Module in the same
    LLVMContext won't magically merge types.

  - Clients (like LTO) that want to continue to merge types based on ODR
    identifiers should opt-in immediately.

I have updated LTOCodeGenerator.cpp, the two "linking" spots in
gold-plugin.cpp, and llvm-link (unless -disable-debug-info-type-map) to
set this.

With this in place, it will be straightforward to remove the DITypeRef
concept (i.e., referencing types by their 'identifier:' string rather
than pointing at them directly).

llvm-svn: 266549

Since the result of a mapped distinct node is known up front, it's more
efficient to map them separately from uniqued nodes.  This commit pulls
them out of the post-order traversal and stores them in a worklist to be
remapped at the top-level.

This is essentially reapplying r244181 ("ValueMapper: Rotate distinct
node remapping algorithm") to the new iterative algorithm from r265456
("ValueMapper: Rewrite Mapper::mapMetadata without recursion").

Now that the traversal logic only handles uniqued MDNodes, it's much
simpler to inline it all into MDNodeMapper::createPOT (I've killed the
MDNodeMapper::push and MDNodeMapper::tryToPop helpers and localized the
traversal worklist).

The resulting high-level algorithm for MDNodeMapper::map now looks like
this:

  - Distinct nodes are immediately mapped and added to
    MDNodeMapper::DistinctWorklist using MDNodeMapper::mapDistinctNode.

  - Uniqued nodes are mapped via MDNodeMapper::mapTopLevelUniquedNode,
    which traverses the transitive uniqued subgraph of a node to
    calculate uniqued node mappings in bulk.

      - This is a simplified version of MDNodeMapper::map from before
        this commit (originally r265456) that doesn't traverse through
        any distinct nodes.

      - Distinct nodes are added to MDNodeMapper::DistinctWorklist via
        MDNodeMapper::mapDistinctNode.

      - This uses MDNodeMapper::createPOT to fill a
        MDNodeMapper::UniquedGraph (a post-order traversal and side
        table), UniquedGraph::propagateChanges to track which uniqued
        nodes need to change, and MDNodeMapper::mapNodesInPOT to create
        the uniqued nodes.

      - Placeholders for forward references are now only needed when
        there's a uniquing cycle (a cycle of uniqued nodes unbroken by
        distinct nodes).  This is the key functionality change that
        we're reintroducing (from r244181).  As of r265456, a temporary
        forward reference might be needed for any cycle that involved
        uniqued nodes.

  - After mapping the first node appropriately, MDNodeMapper::map works
    through MDNodeMapper::DistinctWorklist.  For each distinct node, its
    operands are remapped with MDNodeMapper::mapDistinctNode and
    MDNodeMapper::mapTopLevelUniquedNode until all nodes have been
    mapped.

Sadly there's nothing observable I can test here; no real functionality
change, just a compile-time speedup from reduced malloc traffic.

llvm-svn: 266537

As a minor fixup to r266258, only track nodes that needed a placeholder
in CyclicNodes in MDNodeMapper::mapUniquedNodes.  There should be no
observable functionality change, just some local memory savings because
CyclicNodes only needs to grow to accommodate nodes that are actually
involved in cycles.  (This was the original intent of r266258, or else
the vector would have been called "ChangedNodes".)

llvm-svn: 266536

llvm-svn: 266529

Stop memoizing ConstantAsMetadata in ValueMapper::mapMetadata.  Now we
have to recompute it, but these metadata aren't particularly common, and
it restricts the lifetime of the Metadata map unnecessarily.

(The motivation is that I have a patch which uses a single Metadata map
for the lifetime of IRMover.  Mehdi profiled r266446 with the patch
applied and we saw a pretty big speedup in lib/Linker.)

llvm-svn: 266513

This reverts commit r266507, reapplying r266503 (and r266505
"ValueMapper: Use API from r266503 in unit tests, NFC") completely
unchanged.

I reverted because of a bot failure here:
  http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/16810/

However, looking more closely, the failure was from a host-compiler
crash (clang 3.7.1) when building:
  lib/CodeGen/AsmPrinter/CMakeFiles/LLVMAsmPrinter.dir/DwarfAccelTable.cpp.o

I didn't modify that file, or anything it includes, with that commit.

The next build (which hadn't picked up my revert) got past it:
  http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/16811/

I think this was just unfortunate timing.  I suppose the bot must be
flakey.

llvm-svn: 266510

This reverts commit r266503, in case it's the root cause of this bot
failure:

  http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/16810

I'm also reverting r266505 -- "ValueMapper: Use API from r266503 in unit
tests, NFC" -- since it's in the way.

llvm-svn: 266507

Eliminate co-recursion of Mapper::mapValue through
ValueMaterializer::materializeInitFor, through a major redesign of the
ValueMapper.cpp interface.

  - Expose a ValueMapper class that controls the entry points to the
    mapping algorithms.
  - Change IRLinker to use ValueMapper directly, rather than
    llvm::RemapInstruction, llvm::MapValue, etc.
  - Use (e.g.) ValueMapper::scheduleMapGlobalInit to add mapping work to
    a worklist in ValueMapper instead of recursing.

There were two fairly major complications.

Firstly, IRLinker::linkAppendingVarProto incorporates an on-the-fly IR
ugprade that I had to split apart.  Long-term, this upgrade should be
done in the bitcode reader (and we should only accept the "new" form),
but for now I've just made it work and added a FIXME.  The hold-op is
that we need to deprecate C API that relies on this.

Secondly, IRLinker has special logic to correctly implement aliases with
comdats, and uses two ValueToValueMapTy instances and two
ValueMaterializers.  I supported this by allowing clients to register an
alternate mapping context, whose MCID can be passed in when scheduling
new work.

While out of scope for this commit, it should now be straightforward to
remove recursion from Mapper::mapValue.

llvm-svn: 266503

Change Mapper::VM to a pointer and add a `getVM()` accessor for it.
While this has no functionality change, it minimizes the diff on an
upcoming patch that allows switching between instances of
ValueToValueMapTy on a single Mapper instance.

llvm-svn: 266490

Currently each Function points to a DISubprogram and DISubprogram has a
scope field. For member functions the scope is a DICompositeType. DIScopes
point to the DICompileUnit to facilitate type uniquing.

Distinct DISubprograms (with isDefinition: true) are not part of the type
hierarchy and cannot be uniqued. This change removes the subprograms
list from DICompileUnit and instead adds a pointer to the owning compile
unit to distinct DISubprograms. This would make it easy for ThinLTO to
strip unneeded DISubprograms and their transitively referenced debug info.

Motivation
----------

Materializing DISubprograms is currently the most expensive operation when
doing a ThinLTO build of clang.

We want the DISubprogram to be stored in a separate Bitcode block (or the
same block as the function body) so we can avoid having to expensively
deserialize all DISubprograms together with the global metadata. If a
function has been inlined into another subprogram we need to store a
reference the block containing the inlined subprogram.

Attached to https://llvm.org/bugs/show_bug.cgi?id=27284 is a python script
that updates LLVM IR testcases to the new format.

http://reviews.llvm.org/D19034
<rdar://problem/25256815>

llvm-svn: 266446

This is almost identical to:
http://reviews.llvm.org/rL264527

This doesn't solve PR27344; it just allows the profile weights to survive. 
To solve the bug, we need to use the profile weights in the backend.

llvm-svn: 266442

Summary: This fixes the buildbot failure.

Reviewers: dnovillo, davidxl

Subscribers: llvm-commits

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

llvm-svn: 266360

Summary: Add discriminator for nested call correctly.

Reviewers: davidxl, dnovillo

Subscribers: llvm-commits

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

llvm-svn: 266354

llvm-svn: 266350

Fix a major bug from r265456.  Although it's now much rarer, ValueMapper
sometimes has to duplicate cycles.  The
might-transitively-reference-a-temporary counts don't decrement on their
own when there are cycles, and you need to call MDNode::resolveCycles to
fix it.

r265456 was checking the input nodes to see if they were unresolved.
This is useless; they should never be unresolved.  Instead we should
check the output nodes and resolve cycles on them.

llvm-svn: 266258

Patch by Li Huang (li1.huang@intel.com)

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

llvm-svn: 266200

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 266151

Summary:
For correct handling of alias to nameless
function, we need to be able to refer them through a GUID in the summary.
Here we name them using a hash of the non-private global names in the module.

Reviewers: tejohnson

Subscribers: joker.eph, llvm-commits

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

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 266132

This is more robust to changes in the link ordering.

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

From: Mehdi Amini <mehdi.amini@apple.com>
llvm-svn: 266018