Perform replacement of access relations and creation of new arrays according to the packing transformation

This is the third patch to apply the BLIS matmul optimization pattern on matmul
kernels (http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf).
BLIS implements gemm as three nested loops around a macro-kernel, plus two
packing routines. The macro-kernel is implemented in terms of two additional
loops around a micro-kernel. The micro-kernel is a loop around a rank-1
(i.e., outer product) update. In this change we perform replacement of
the access relations and create empty arrays, which are steps to implement
the packing transformation. In subsequent changes we will implement copying
to created arrays.

Reviewed-by: Tobias Grosser <tobias@grosser.es>
Differential Revision: http://reviews.llvm.org/D22187

llvm-svn: 278666

[AMDGPU] fix failure on printing of non-existing instruction operands.

Differential revision: https://reviews.llvm.org/D23323

llvm-svn: 278665

Fix a race in Broadcaster/Listener interaction

Summary:
The following problem was occuring:
- broadcaster B had two listeners: L1 and L2 (thread T1)
- (T1) B has started to broadcast an event, it has locked a shared_ptr to L1 (in
  ListenerIterator())
- on another thread T2 the penultimate reference to L1 was destroyed (the transient object in B is
  now the last reference)
- (T2) the last reference to L2 was destroyed as well
- (T1) B has finished broadcasting the event to L1 and destroyed the last shared_ptr
- (T1) this triggered the destructor, which called into B->RemoveListener()
- (T1) all pointers in the m_listeners list were now stale, so RemoveListener emptied the list
- (T1) Eventually control returned to the ListenerIterator() for doing broadcasting, which was
  still in the middle of iterating through the list
- (T1) Only now, it was holding onto a dangling iterator. BOOM.

I fix this issue by making sure nothing can interfere with the
iterate-and-remove-expired-pointers loop, by moving this logic into a single function, which
first locks (or clears) the whole list and then returns the list of valid and locked Listeners
for further processing. Instead of std::list I use an llvm::SmallVector which should hopefully
offset the fact that we create a copy of the list for the common case where we have only a few
listeners (no heap allocations).

A slight difference in behaviour is that now RemoveListener does not remove an element from the
list -- it only sets it's mask to 0, which means it will be removed during the next iteration of
GetListeners(). This is purely an implementation detail and it should not be externally
noticable.

I was not able to reproduce this bug reliably without inserting sleep statements into the code,
so I do not add a test for it. Instead, I add some unit tests for the functions that I do modify.

Reviewers: clayborg, jingham

Subscribers: tberghammer, lldb-commits

Differential Revision: https://reviews.llvm.org/D23406

llvm-svn: 278664

[ELF] Linkerscript: fix bug in assignOffsets (check Sym for non-null)

llvm-svn: 278663

Fixup r278524 for non-apple targets

The commit started passing a nullptr port into GDBRemoteCommunication::StartDebugserverProcess.
The function was mostly handling the null value correctly, but it one case it did not check it's
value before assigning to it. Fix that.

llvm-svn: 278662

MachineLoop: add methods findLoopControlBlock and findLoopPreheader

This adds two new utility functions findLoopControlBlock and findLoopPreheader
to MachineLoop and MachineLoopInfo. These functions are refactored and taken
from the Hexagon target as they are target independent; thus this is intendend to
be a non-functional change.

Differential Revision: https://reviews.llvm.org/D22959

llvm-svn: 278661

[SimplifyCFG] Rewrite SinkThenElseCodeToEnd

The new version has several advantages:
  1) IMSHO it's more readable and neater
  2) It handles loads and stores properly
  3) It can handle any number of incoming blocks rather than just two. I'll be taking advantage of this in a followup patch.

With this change we can now finally sink load-modify-store idioms such as:

    if (a)
      return *b += 3;
    else
      return *b += 4;

    =>

    %z = load i32, i32* %y
    %.sink = select i1 %a, i32 5, i32 7
    %b = add i32 %z, %.sink
    store i32 %b, i32* %y
    ret i32 %b

When this works for switches it'll be even more powerful.

llvm-svn: 278660

[Thumb] Validate branch target for CBZ/CBNZ instructions.

Summary:
The assembler currently does not check the branch target for CBZ/CBNZ
instructions, which only permit branching forwards with a positive offset. This
adds validation for the branch target to ensure negative PC-relative offsets are
not encoded into the instruction, whether specified as a literal or as an
assembler symbol.

Reviewers: rengolin, t.p.northover

Subscribers: llvm-commits, rengolin

Differential Revision: https://reviews.llvm.org/D23312

llvm-svn: 278659

[LSR] Don't try and create post-inc expressions on non-rotated loops

If a loop is not rotated (for example when optimizing for size), the latch is not the backedge. If we promote an expression to post-inc form, we not only increase register pressure and add a COPY for that IV expression but for all IVs!

Motivating testcase:

    void f(float *a, float *b, float *c, int n) {
      while (n-- > 0)
        *c++ = *a++ + *b++;
    }

It's imperative that the pointer increments be located in the latch block and not the header block; if not, we cannot use post-increment loads and stores and we have to keep both the post-inc and pre-inc values around until the end of the latch which bloats register usage.

llvm-svn: 278658

[ELF] Do not add start and end symbols in case they are already defined

llvm-svn: 278657

[CodeGen] Ignore unnamed bitfields before handling vector fields

We processed unnamed bitfields after our logic for non-vector field
elements in records larger than 128 bits.  The vector logic would
determine that the bit-field disqualifies the record from occupying a
register despite the unnamed bit-field not participating in the record
size nor its alignment.

N.B. This behavior matches GCC and ICC.

llvm-svn: 278656

[CodeGen] Correctly implement the AVX512 psABI rules

An __m512 vector type wrapped in a structure should be passed in a
vector register.

Our prior implementation was based on a draft version of the psABI.

This fixes PR28975.

N.B. The update to the ABI was made here:
https://github.com/hjl-tools/x86-psABI/commit/30f9c9

llvm-svn: 278655

[X86] PADDUSB/W instructions should be commutable.

llvm-svn: 278654

[X86] Mark some of the X86 SDNodes as commutative.

llvm-svn: 278653

[X86] X86ISD::FANDN is not commutative or associative.

llvm-svn: 278652

[ScopedNoAliasAA] collectMDInDomain should be a free function

collectMDInDomain doesn't use any class members, making it a free
function is not a functional change.

llvm-svn: 278651

cxx_status: update features implemented in clang 3.9 from "svn" to "Clang 3.9" now that svn trunk is 4.0.

llvm-svn: 278650

cxx_status: mark decomposition declarations as "partial": the implementation is
essentially complete, other than parts where design questions have been raised
(lambda capture, decomposition of arrays by copy).

llvm-svn: 278649

Disable lambda-capture of decomposition declaration bindings for now, until CWG
agrees on how they're supposed to work.

llvm-svn: 278648

Add a triple to this test to make buildbots happier.

llvm-svn: 278647

[ScopedNoAliasAA] Only collect noalias nodes if we have alias.scope nodes

No functional change is intended.

llvm-svn: 278646

[ScopedNoAliasAA] Replace !ScopeNodes.size() with ScopeNodes.empty()

No functional change is intended.

llvm-svn: 278645

Revert "[ScopedNoAliasAA] Remove an unneccesary set"

This reverts commit r278641.  I'm not sure why but this has upset the
multistage builders...

llvm-svn: 278644

Check in SFINAE base class for use in optional/variant

llvm-svn: 278643

P0217R3: code generation support for decomposition declarations.

llvm-svn: 278642

[ScopedNoAliasAA] Remove an unneccesary set

We are trying to prove that one group of operands is a subset of
another.  We did this by populating two Sets and determining that every
element within one was inside the other.

However, this is unnecessary.  We can simply construct a single set and
test if each operand is within it.

llvm-svn: 278641

Explicitly generate a reference variable to hold the initializer for a
tuple-like decomposition declaration. This significantly simplifies the
semantics of BindingDecls for AST consumers (they can now always be evalated
at the point of use).

llvm-svn: 278640

[InstCombine] add test for missing vector icmp fold

llvm-svn: 278639

Add private option to change build dialect from C++11

Although libc++ only requires C++11 to build, there are other
reasons to turn on a newer dialect in the build. For example
IDE's may not highlight any C++14/C++17 in the headers when
configured for C++11. This patch add's a private option for
changing this.

llvm-svn: 278638

[InstCombine] add tests for vector icmp folds

llvm-svn: 278637

[InstCombine] add test for potentially missing vector icmp fold

llvm-svn: 278636

[InstCombine] add test for missing vector icmp fold

llvm-svn: 278635

[InstCombine] add tests for missing vector icmp folds

llvm-svn: 278634

[InstCombine] remove unnecessary function attributes from tests

llvm-svn: 278633

[InstCombine] add tests for missing vector icmp folds

llvm-svn: 278632

[InstCombine] add test for missing vector icmp fold

llvm-svn: 278631

[InstCombine] add test for missing vector icmp fold

llvm-svn: 278630

[AVX-512] Mark VPMADDWD as commutable to match SSE/AVX version.

llvm-svn: 278629

[AVX-512] Add masked commutable floating point max/min instructions to folding tables.

llvm-svn: 278628

[AVX-512] Add masked logical operations to memory folding tables.

llvm-svn: 278627

[AVX512] Fix VFPCLASSSD/VFPCLASSSS intrinsic lowering. The i1 result should be zero extended according to SPEC.

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

llvm-svn: 278626

elf-core: set powerpc vector byte order correctly

It was being set to the fp reg set's byte order due to an apparent
copy-and-pasteo.

llvm-svn: 278625

autogenerate checks

llvm-svn: 278624

[AVX512] Fix insertelement i1 lowering.
1. Use shuffle to insert element i1 into vector. The previous implementation was incorrect ( dest_bit OR src_bit , it doesn't clear the bit if src_bit=0 )
2. Improve shuffle i1 vector, use CVT2MASK if supported instead TRUNCATE.

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

llvm-svn: 278623

Revert "gold: add a cast to appease std::max NFC"

This was fixed differently by Teresa and this should no longer be needed.

llvm-svn: 278622

Revert "CodeGen: If Convert blocks that would form a diamond when tail-merged."

This reverts commit r278287.

This commit broke the clang-cmake-thumbv7-a15-full-sh bot.
See https://llvm.org/bugs/show_bug.cgi?id=28949

llvm-svn: 278621

Revert "Codegen: Don't tail-duplicate blocks with un-analyzable fallthrough."

This reverts commit r278288.

r278287 broke the clang-cmake-thumbv7-a15-full-sh bot.
Revert this so we can get to r278287.

llvm-svn: 278620

[IRCE] Change variable grouping; NFC

llvm-svn: 278619

[IRCE] Create llvm::Loop instances for cloned out loops

llvm-svn: 278618

[IRCE] Don't iterate on loops that were cloned out

IRCE has the ability to further version pre-loops and post-loops that it
created, but this isn't useful at all.  This change teaches IRCE to
leave behind some metadata in the loops it creates (by cloning the main
loop) so that these new loops are not re-processed by IRCE.

Today this bug is hidden by another bug -- IRCE does not update LoopInfo
properly so the loop pass manager does not re-invoke IRCE on the loops
it split out.  However, once the latter is fixed the bug addressed in
this change causes IRCE to infinite-loop in some cases (e.g. it splits
out a pre-loop, a pre-pre-loop from that, a pre-pre-pre-loop from that
and so on).

llvm-svn: 278617

[IRCE] Add better DEBUG diagnostic; NFC

NFC meaning IRCE should not _do_ anything different, but
-debug-only=irce will be a little friendlier.

llvm-svn: 278616

Fix bitcode auto-upgrade when using bitcode lazy loading

The auto-upgrade path could be called before the VST (global
names) was fully parsed, and thus intrinsic names were not
available and the autoupgrade logic could not operate.

Fix link failures with ThinLTO.

This is a recommit of r278610 with a different fix.

llvm-svn: 278615

Fix unsupported relocation type R_HEX_6_X' for symbol .rodata

LowerTargetConstantPool is not properly setting the TargetFlag to indicate
desired relocation. Coding error, the offset parameter was omitted, so the
TargetFlag was used as the offset, and the TargetFlag defaulted to zero.

This only affects -fpic compilation, and only those items created in a
Constant Pool, for example a vector of constants. Halide ran into this issue.

llvm-svn: 278614

Revert "Fix bitcode auto-upgrade when using bitcode lazy loading"

This reverts commit r278610. Tests are broken

llvm-svn: 278613

[IRCE] Fix test case; NFC

The (negative) test case is supposed to check that IRCE does not muck
with range checks it cannot handle, not that it does the right thing in
the absence of profiling information.

llvm-svn: 278612

[IRCE] Be resilient in the face of non-simplified loops

Loops containing `indirectbr` may not be in simplified form, even after
running LoopSimplify.  Reject then gracefully, instead of tripping an
assert.

llvm-svn: 278611

Fix bitcode auto-upgrade when using bitcode lazy loading

The auto-upgrade path could be called before the VST (global
names) was fully parsed, and thus intrinsic names were not
available and the autoupgrade logic could not operate.

Fix link failures with ThinLTO.

llvm-svn: 278610

Revert "Revert "Invariant start/end intrinsics overloaded for address space""

This reverts commit 32fc6488e48eafc0ca1bac1bd9cbf0008224d530.

llvm-svn: 278609

Revert "Invariant start/end intrinsics overloaded for address space"

This reverts commit r276447.

llvm-svn: 278608

[IRCE] Use dyn_cast instead of explicit isa/cast; NFC

llvm-svn: 278607

[IRCE] Use range-for; NFC

llvm-svn: 278606

[ADT] Add a reserve() method to DenseSet as well as an insert() for R-value

Recommit 278600 with some fixes to make the test more robust.

llvm-svn: 278604

Revert "[ADT] Add a reserve method to DenseSet as well as an insert() for R-value"

This reverts commit r278600. The unittest does not pass on MSVC, there is
an extra move. Investigating how to make it more robust.

llvm-svn: 278603

Limit DenseMap::setNumEntries input to 1<<31, in accordance with the 31 bits allocated to NumEntries.
std::numeric_limits<int>::max() may be something else than 1<<31.

llvm-svn: 278602

Add missing REQUIRES in sancov/print_coverage_pcs.test: it requires aarch64 as well now

llvm-svn: 278601

[ADT] Add a reserve method to DenseSet as well as an insert() for R-value

llvm-svn: 278600

[x86] add tests to show missed 64-bit immediate merging

Tests are slightly modified versions of those written by
Sunita Marathe in D23391.

llvm-svn: 278599

Test commit

llvm-svn: 278598

[X86] Add a check of isCommutable at the top of X86InstrInfo::findCommutedOpIndices. Most callers don't check if the instruction is commutable before calling.

This saves us the trouble of ending up in the default of the switch and having to determine if this is an FMA or not.

llvm-svn: 278597

[AVX-512] Add isCommutable to scalar FMA3 instructions.

llvm-svn: 278596

[AVX-512] Add commutable flags to 132 form FMA3 instructions.

llvm-svn: 278595

[X86] Remove patterns for (vzmovl (insert_subvector undef, (scalar_to_vector))) as the (vzmovl VR256) pattern has higher priority. NFC

llvm-svn: 278594

[AVX-512] Remove an AddedComplexity that was prioritizing basic vzmovl patterns over more complex ones that produce better code.

llvm-svn: 278593

[AVX-512] Add patterns to support VZEXT_MOVL from 512-bit vectors with 64-bit and 32-bit elements.

Fixes PR28961.

llvm-svn: 278592

[PM] Port LoopDataPrefetch to new pass manager

Summary:
Refactor the existing support into a LoopDataPrefetch implementation
class and a LoopDataPrefetchLegacyPass class that invokes it.
Add a new LoopDataPrefetchPass for the new pass manager that utilizes
the LoopDataPrefetch implementation class.

Reviewers: mehdi_amini

Subscribers: sanjoy, mzolotukhin, nemanjai, llvm-commits

Differential Revision: https://reviews.llvm.org/D23483

llvm-svn: 278591

AMDGPU: Fix not estimating MBB operand sizes correctly

llvm-svn: 278590

AMDGPU: Fix missing test for addressing mode with odd offsets

Add test if the constant offset looks unaligned.

llvm-svn: 278589

AMDGPU/R600: Remove macros

llvm-svn: 278588

Fix more dereferenced end() iterators after r278532

llvm-svn: 278587

Fix build broken after llvm/ADT/DenseMap.h replacement of climits with limits.

llvm-svn: 278586

Constify ValueTracking.  NFC.

Almost all of the method here are only analysing Value's as opposed to
mutating them.  Mark all of the easy ones as const.

llvm-svn: 278585

[IndVars] Ignore (s|z)exts that don't extend the induction variable

`IVVisitor::visitCast` used to have the invariant that if the
instruction it was passed was a sext or zext instruction, the result of
the instruction would be wider than the induction variable.  This is no
longer true after rL275037, so this change teaches `IndVarSimplify` s
implementation of `IVVisitor::visitCast` to work with the relaxed
invariant.

A corresponding change to SimplifyIndVar to preserve the said invariant
after rL275037 would also work, but given how `IVVisitor::visitCast` is
spelled (no indication of said invariant), I figured the current fix is
cleaner.

Fixes PR28935.

llvm-svn: 278584

Fix some Clang-tidy modernize-use-using and Include What You Use warnings.

Differential revision: https://reviews.llvm.org/D23478

llvm-svn: 278583

[libFuzzer] mention one more trophie in LLVM

llvm-svn: 278582

[LSV] Use a set rather than an ArraySlice at the end of getVectorizablePrefix. NFC

Summary: This avoids a small O(n^2) loop.

Reviewers: asbirlea

Subscribers: mzolotukhin, llvm-commits, arsenm

Differential Revision: https://reviews.llvm.org/D23473

llvm-svn: 278581

[LSV] Use OrderedBasicBlock instead of rolling it ourselves. NFC

Summary:
In getVectorizablePrefix, this is less efficient (because we have to
iterate over the BB twice), but boy is it simpler.  Given how much
trouble we've had here, I think the simplicity gain is worthwhile.

In reorder(), this is actually more efficient, as
DominatorTree::dominates iterates over the BB from the beginning when
the two instructions are in the same BB.

Reviewers: asbirlea

Subscribers: arsenm, llvm-commits, mzolotukhin

Differential Revision: https://reviews.llvm.org/D23472

llvm-svn: 278580

Fix ASAN failures in the demangler

These were found fuzzing with ASAN.

llvm-svn: 278579

Minor comment fix ("generate" --> "generates").

llvm-svn: 278578

X86: Fix another dereferenced end() iterator after r278532

llvm-svn: 278577

[WebAssembly] Re-enable disabled debug value test

Summary:
This test was resulting in asan/valgrind failures due to undefined
DWARF register mappings for WebAssembly, and was disabled in r278495.
These have been resolved.

Reviewers: sunfish, dschuff

Subscribers: bkramer, llvm-commits, jfb

Differential Revision: https://reviews.llvm.org/D23459

llvm-svn: 278576

Reapply [BranchFolding] Restrict tail merging loop blocks after MBP

Fixed a bug in the test case.

To fix PR28104, this patch restricts tail merging to blocks that belong to the
same loop after MBP.

llvm-svn: 278575

Avoid accessing LLVM/DWARF register mappings if undefined

Summary:
If the backend does not define LLVM/DWARF register mappings, the associated
variables are undefined since the map initializer is called by auto-generated
TableGen routines. This patch initializes the pointers and sizes to nullptr
and zero, respectively, and checks that they are valid before searching
for a mapping.

Reviewers: grosbach, dschuff

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D23458

llvm-svn: 278574

[LoopVectorize] Detect loops in the innermost loop before creating InnerLoopVectorizer

InnerLoopVectorizer shouldn't handle a loop with cycles inside the loop
body, even if that cycle isn't a natural loop.

Fixes PR28541.

Differential Revision: https://reviews.llvm.org/D22952

llvm-svn: 278573

X86: Stop dereferencing end() in X86FrameLowering::emitEpilogue

On a Windows build of Chromium, r278532 (up to r278539)
X86FrameLowering::emitEpilogue because it wasn't wary enough of the
return of MachineBasicBlock::getFirstTerminator.  Guard all the uses
here.

Note that r278532 *looks* like an NFC commit (just an API change), but
it removes a couple of layers of abstraction and is probably causing
optimization differences in MSVC.

llvm-svn: 278572

[Inliner] Don't treat inalloca allocas as static

They aren't static, and moving them to the entry block across something
else will only result in tears.

Root cause of http://crbug.com/636558.

llvm-svn: 278571

Add support to paternmatch for simple const Value cases.

Pattern match has some paths which can operate on constant instructions,
but not all.  This adds a version of m_value() to return const Value* and
changes ICmp matching to use auto so that it can match both constant and
mutable instructions.

Tests also included for both mutable and constant ICmpInst matching.

This will be used in a future commit to constify ValueTracking.cpp.

llvm-svn: 278570

[ADT] Add filter_iterator for filtering elements

Differential Revision: https://reviews.llvm.org/D22951

llvm-svn: 278569

[NVPTX] Use untyped (.b) integer registers in PTX.

This bring LLVM-generated PTX closer to what nvcc generates and avoids
triggering issues in ptxas.

For instance, ptxas does not accept .s16 (or .u16) registers as operands
for .fp16 instructions.

Differential Revision: https://reviews.llvm.org/D23460

llvm-svn: 278568

gold: add a cast to appease std::max NFC

llvm-svn: 278567

[PM] BitcodeWriterPass should derive from PassInfoMixin

Summary:
The BitcodeWriterPass was ported a couple years ago, and predates the
PassInfoMixin. Make BitcodeWriterPass from that base class.

Should BitcodeWriterPass be added to the PassRegistry.def file? It seems
like that is only for passes that can be added arbitrarily, e.g. via the
-passes flag to the opt tool. Whereas the bitcode writer is added
specially based on the output type (and requires an output stream and
other parameters). For now I have left it out of the PassRegistry, but
let me know if it should go there.

Finally, I was considering an NFC change of the legacy WriteBitcodePass
to BitcodeWriterLegacyPass to make its usage clearer and more consistent
with other legacy passes. WDYT?

Reviewers: mehdi_amini

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D23465

llvm-svn: 278566