[clangd] Proof-of-concept query iterators for Dex symbol index

This patch introduces three essential types of query iterators:
`DocumentIterator`, `AndIterator`, `OrIterator`. It provides a
convenient API for query tree generation and serves as a building block
for the next generation symbol index - Dex. Currently, many
optimizations are missed to improve code readability and to serve as the
reference implementation. Potential improvements are briefly mentioned
in `FIXME`s and will be addressed in the following patches.

Dex RFC in the mailing list:
http://lists.llvm.org/pipermail/clangd-dev/2018-July/000022.html

Iterators, their applications and potential extensions are explained in
detail in the design proposal:
https://docs.google.com/document/d/1C-A6PGT6TynyaX4PXyExNMiGmJ2jL1UwV91Kyx11gOI/edit#heading=h.903u1zon9nkj

Reviewers: ioeric, sammccall, ilya-biryukov

Subscribers: cfe-commits, klimek, jfb, mgrang, mgorny, MaskRay, jkorous,
arphaman

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

llvm-svn: 338017

[x86/SLH] Extract the logic to trace predicate state through calls to
a helper function with a nice overview comment. NFC.

This is a preperatory refactoring to implementing another component of
mitigation here that was descibed in the design document but hadn't been
implemented yet.

llvm-svn: 338016

[clangd] Give an example for symbol-builder usage

`global-symbol-builder` help message mentions `-executor=<string>`
option, but doesn't give any example of what the value could be

Assuming the most popular use case to be building the whole project
index, help message should probably give an example of such usage.

Reviewers: ioeric

Subscribers: cfe-commits

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

llvm-svn: 338015

[test] Do dsymutil update in place

Update the dSYM bundle in place when swapping out the accelerator
tables. This should unbreak the windows bot that have been failing with
an access denied.

llvm-svn: 338014

Allow users of the GCOV API to extend the FileInfo class to implement custom output formats

Summary:
The GCOV API can be used to parse gcda/gcno files, but in order to implement custom output formats, users need to reimplement everything.
If the FileInfo members were protected instead of private, they'd be able to reuse the code.

Reviewers: bogner, davide, scott.smith

Subscribers: llvm-commits

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

llvm-svn: 338013

[clangd] Do not rebuild AST if inputs have not changed

Summary:
If the contents are the same, the update most likely comes from the
fact that compile commands were invalidated. In that case we want to
avoid rebuilds in case the compile commands are actually the same.

Reviewers: ioeric

Reviewed By: ioeric

Subscribers: simark, javed.absar, MaskRay, jkorous, arphaman, jfb, cfe-commits

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

llvm-svn: 338012

[AArch64][NFC] Removed tab characters from test files.

llvm-svn: 338011

[AArch64] Armv8.2-A: add the crypto extensions

This adds MC support for the crypto instructions that were made optional
extensions in Armv8.2-A (AArch64 only).

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

llvm-svn: 338010

[ConstProp] Fix calls-math-finite.ll on FreeBSD

FreeBSD's log(3.0) is less precise than glibc and musl.
Let's forgive its rounding error of more than half an ulp.

llvm-svn: 338009

[AsmParser] Fix preserve-comments-crlf.s on FreeBSD

--strip-trailing-cr is a diffutils option which is also available on
BSD-licensed diff introduced in FreeBSD 11.2, however, it has a bug
comparing files mixing \r and \r\n. Use -b (POSIX) instead.

llvm-svn: 338008

[X86] Don't use CombineTo to skip adding new nodes to the DAGCombiner worklist in combineMul.

I'm not sure if this was trying to avoid optimizing the new nodes further or what. Or maybe to prevent a cycle if something tried to reform the multiply? But I don't think its a reliable way to do that. If the user of the expanded multiply is visited by the DAGCombiner after this conversion happens, the DAGCombiner will check its operands, see that they haven't been visited by the DAGCombiner before and it will then add the first node to the worklist. This process will repeat until all the new nodes are visited.

So this seems like an unreliable prevention at best. So this patch just returns the new nodes like any other combine. If this starts causing problems we can try to add target specific nodes or something to more directly prevent optimizations.

Now that we handle the combine normally, we can combine any negates the mul expansion creates into their users since those will be visited now.

llvm-svn: 338007

[CMake] Don't generate linker script only when shared library isn't statically linked

Since r337668, we support statically linking dependencies only to shared
or static library. However, that change hasn't updated the check whether
to generate a linker script. We shouldn't generate linker script only in
the case when we aren't statically linked ABI into the shared library.

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

llvm-svn: 338006

Copy LLVM CMake configuration for CMake Policy CMP0068

llvm-svn: 338005

[sanitizer] Include signal.h instead of sys/signal.h

llvm-svn: 338004

[Docs] Update of Xray page

Update of supported oses.

Reviewers: dberris

Reviewed By: dberris

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

llvm-svn: 338003

Be more consistent about which bool value means an error occurred

llvm-svn: 338002

Cleanup the last_write_time internals

llvm-svn: 338001

Correct comment about stat truncating st_mtimespec to seconds

llvm-svn: 338000

Fix attribute placement WRT extern C

llvm-svn: 337999

Workaround OS X 10.11 behavior where stat truncates st_mtimespec to seconds.

llvm-svn: 337998

Revert r337981: it breaks the debuginfo-tests

This commit caused a regression in the debuginfo-tests:

FAIL: debuginfo-tests :: apple-accel.cpp (40748 of 46595)
llvm-svn: 337997

[X86] Remove some unnecessary explicit calls to DCI.AddToWorkList.

These calls were making sure some newly created nodes were added to worklist, but the DAGCombiner has internal support for ensuring it has visited all nodes. Any time it visits a node it ensures the operands have been queued to be visited as well. This means if we only need to return the last new node. The DAGCombiner will take care of adding its inputs thus walking backwards through all the new nodes.

llvm-svn: 337996

[Support] Introduce createStringError helper function

The function in question is copy-pasted lots of times in DWARF-related classes.
Thus it will make sense to place its implementation into the Support library.

Reviewed by: lhames

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

llvm-svn: 337995

[GlobalISel] Fall back to SDISel for swifterror/swiftself attributes.

We don't currently support these, fall back until we do.

llvm-svn: 337994

[DWARF v5] Don't report an error when the .debug_rnglists section is empty or non-existent. Fixes PR38297.

Reviewer: JDevlieghere

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

llvm-svn: 337993

[LoadStoreVectorizer] Use const reference

llvm-svn: 337992

Add print statements to help debugging

llvm-svn: 337991

[libc++] Add hack to allow ubsan to work w/o compiler-rt (__muloti4 is undefined)

Summary:
Using int128_t with UBSAN causes link errors unless compiler-rt is providing the runtime library.
Specifically ubsan generates calls to __muloti4 but libgcc doesn't provide a definition.

In order to avoid this, and allow users to continue using sanitized versions of libc++, this patch introduces a hack.
It adds a cribbed version of  the compiler-rt builtin to the libc++ filesystem sources.

I don't think this approach will work in the long run, but it seems OK for now.

Also see:

https://bugs.llvm.org/show_bug.cgi?id=30643
https://bugs.llvm.org/show_bug.cgi?id=16404

Reviewers: mclow.lists, ldionne, rsmith, jyknight, echristo

Reviewed By: echristo

Subscribers: dberris, cfe-commits

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

llvm-svn: 337990

RegUsageInfo: Cleanup; NFC

- Remove unnecessary anchor function
- Remove unnecessary override of getAnalysisUsage
- Use reference instead of pointers where things cannot be nullptr
- Use ArrayRef instead of std::vector where possible

llvm-svn: 337989

CodeGen.cpp: Sort initializers; NFC

llvm-svn: 337988

InitializePasses: Sort declarations; NFC

llvm-svn: 337987

CodeGen: Cleanup regmask construction; NFC

- Avoid duplication of regmask size calculation.
- Simplify allocateRegisterMask() call.
- Rename allocateRegisterMask() to allocateRegMask() to be consistent
  with naming in MachineOperand.

llvm-svn: 337986

[MCA] Avoid an InstrDesc copy in mca::LSUnit::reserve.

Summary:
InstrDesc contains 4 vectors (as well as some other data), so it's
expensive to copy.

Authored By: orodley

Reviewers: andreadb, mattd, dberris

Reviewed By: mattd, dberris

Subscribers: dberris, gbedwell, llvm-commits

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

llvm-svn: 337985

[libc++] Follow-up to r337968: use an explicit cast as suggested by Eric

llvm-svn: 337984

[ELF] Fix linker-script-in-search-path.s

llvm-svn: 337983

[CMake] Don't use LIBCXXABI_ENABLE_STATIC option before its declared

Summary:
rL337867 introduced two new cmake_dependent_option options:
- LIBCXXABI_INSTALL_STATIC_LIBRARY
- LIBCXXABI_INSTALL_SHARED_LIBRARY

They depend on LIBCXXABI_ENABLE_STATIC and LIBCXXABI_ENABLE_SHARED
and so therefore need to (it seems) come after the declaration of
these two options.

Subscribers: mgorny, aheejin, christof, ldionne, cfe-commits

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

llvm-svn: 337982

[DWARF v5] Don't emit multiple DW_AT_rnglists_base attributes. Some refactoring of
range lists emissions and added test cases.

Reviewer: dblaikie

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

llvm-svn: 337981

[dsymutil] Add support for generating DWARF5 accelerator tables.

This patch add support for emitting DWARF5 accelerator tables
(.debug_names) from dsymutil. Just as with the Apple style accelerator
tables, it's possible to update existing dSYMs. This patch includes a
test that show how you can convert back and forth between the two types.

If no kind of table is specified, dsymutil will default to generating
Apple-style accelerator tables whenever it finds those in its input. The
same is true when there are no accelerator tables at all. Finally, in
the remaining case, where there's at least one DWARF v5 table and no
Apple ones, the output will contains a DWARF accelerator tables
(.debug_names).

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

llvm-svn: 337980

[CMake] Don't install c++abi headers in standalone libc++ build

This is a refinement on r337833. Previously we were installing two
copies of c++abi headers in libc++ build directory, one in
include/c++build and another one in include/c++/v1. However, the
second copy is unnecessary when building libc++ standalone.

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

llvm-svn: 337979

[ODRHash] Support hashing enums.

llvm-svn: 337978

bpf: new option -bpf-expand-memcpy-in-order to expand memcpy in order

Some BPF JIT backends would want to optimize memcpy in their own
architecture specific way.

However, at the moment, there is no way for JIT backends to see memcpy
semantics in a reliable way. This is due to LLVM BPF backend is expanding
memcpy into load/store sequences and could possibly schedule them apart from
each other further. So, BPF JIT backends inside kernel can't reliably
recognize memcpy semantics by peephole BPF sequence.

This patch introduce new intrinsic expand infrastructure to memcpy.

To get stable in-order load/store sequence from memcpy, we first lower
memcpy into BPF::MEMCPY node which then expanded into in-order load/store
sequences in expandPostRAPseudo pass which will happen after instruction
scheduling. By this way, kernel JIT backends could reliably recognize
memcpy through scanning BPF sequence.

This new memcpy expand infrastructure is gated by a new option:

  -bpf-expand-memcpy-in-order

Acked-by: Jakub Kicinski <jakub.kicinski@netronome.com>
Signed-off-by: Jiong Wang <jiong.wang@netronome.com>
Signed-off-by: Yonghong Song <yhs@fb.com>
llvm-svn: 337977

Work around GCC bug in constexpr function

llvm-svn: 337976

[ELF] Make linker-script-in-search-path.s robust per r337972

llvm-svn: 337975

Fix GCC build in C++14 w/o c++14 constexpr

llvm-svn: 337974

[GlobalMerge] Handle llvm.compiler.used correctly.

Reuse the handling for llvm.used, and don't transform such globals.

Fixes a failure on the asan buildbot caused by my previous commit.

llvm-svn: 337973

Make a test more robust.

Previously, this test fails if there's other test that happens to
create "t.script" in the current directory.

llvm-svn: 337972

Remove test which shouldn't have been committed

llvm-svn: 337971

Fix failing test under C++14

llvm-svn: 337970

[ELF] Use search paths for --version-script=

Summary: This behavior matches ld.bfd -Ld --version-script=t.script a.o

Reviewers: ruiu, espindola

Subscribers: emaste, arichardson, llvm-commits

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

llvm-svn: 337969

[libc++] Follow-up to r337960: specify lambda's return type to avoid
-Wc++11-narrowing warning on Darwin

The internal CI produced the following diagnostic:
error: non-constant-expression cannot be narrowed from type 'long long' to '__darwin_suseconds_t' (aka 'int') in initializer list [-Wc++11-narrowing]
  struct ::timeval ConvertedTS[2] = {{TS[0].tv_sec, Convert(TS[0].tv_nsec)},
                                                    ^~~~~~~~~~~~~~~~~~~~~~

llvm-svn: 337968

ELF: Do not ICF SHF_LINK_ORDER sections.

We are already ICF'ing these sections as a unit with their dependent
sections, so they don't need to be considered for ICF individually.

This change also "fixes" slowness caused by our quadratic-in-group-size
relocation segregation algorithm on 32-bit ARM platforms with unwind
data and ICF on rodata. In this scenario almost every function's
.ARM.exidx is identical except for the targets of the relocations
that refer to the function and its .ARM.extab, which causes almost
all of the program's .ARM.exidx sections to be initially added to the
same class, which causes us to compare every such section with every
other such section.

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

llvm-svn: 337967

[SelectionDAG] try to convert funnel shift directly to rotate if legal

If the DAGCombiner's rotate matching was working as expected,
I don't think we'd see any test diffs here.

This sidesteps the issue of custom lowering for rotates raised in PR38243:
https://bugs.llvm.org/show_bug.cgi?id=38243
...by only dealing with legal operations.

llvm-svn: 337966

[LSV] Look through selects for consecutive addresses

In some cases LSV sees (load/store _ (select _ <pointer expression>
<pointer expression>)) patterns in input IR, often due to sinking and
other forms of CFG simplification, sometimes interspersed with
bitcasts and all-constant-indices GEPs. With this
patch`areConsecutivePointers` method would attempt to handle select
instructions. This leads to an increased number of successful
vectorizations.

Technically, select instructions could appear in index arithmetic as
well, however, we don't see those in our test suites / benchmarks.
Also, there is a lot more freedom in IR shapes computing integral
indices in general than in what's common in pointer computations, and
it appears that it's quite unreliable to do anything short of making
select instructions first class citizens of Scalar Evolution, which
for the purposes of this patch is most definitely an overkill.

Reviewed By: rampitec

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

llvm-svn: 337965

[AArch, PowerPC] add more tests for legal rotate ops; NFC

llvm-svn: 337964

Revert "[DataFormatters] Add formatter for C++17 std::optional."

I forgot to git add some files. I'm going to recommit the correct
version at once soon.

llvm-svn: 337963

Make <experimental/filesystem> compile with gcc 4.8.5

Patch by Victor Zverovich.

This fixes an error when compiling `<experimental/filesystem>` with gcc 4.8.5:

```
.../libcxx/src/experimental/filesystem/filesystem_common.h:137:34:
error: redeclaration ‘T
std::experimental::filesystem::v1::detail::{anonymous}::error_value() [with T =
bool]’ d
iffers in ‘constexpr’
 constexpr bool error_value<bool>() {
                                  ^
.../libcxx/src/experimental/filesystem/filesystem_common.h:133:3:
error: from previous declaration ‘T
std::experimental::filesystem::v1::detail::{anonymous}::error_value() [with T
 = bool]’
 T error_value();
   ^
```

Reviewed as https://reviews.llvm.org/D49813

llvm-svn: 337962

[GlobalMerge] Allow merging globals with arbitrary alignment.

Instead of depending on implicit padding from the structure layout code,
use a packed struct and emit the padding explicitly.

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

llvm-svn: 337961

[libc++] Use __int128_t to represent file_time_type.

Summary:
The ``file_time_type`` time point is used to represent the write times for files.
Its job is to act as part of a C++ wrapper for less ideal system interfaces. The
underlying filesystem uses the ``timespec`` struct for the same purpose.

However, the initial implementation of ``file_time_type`` could not represent
either the range or resolution of ``timespec``, making it unsuitable. Fixing
this requires an implementation which uses more than 64 bits to store the
time point.

I primarily considered two solutions: Using ``__int128_t`` and using a
arithmetic emulation of ``timespec``. Each has its pros and cons, and both
come with more than one complication.

However, after a lot of consideration, I decided on using `__int128_t`. This patch implements that change.

Please see the [FileTimeType Design Document](http://libcxx.llvm.org/docs/DesignDocs/FileTimeType.html) for more information.

Reviewers: mclow.lists, ldionne, joerg, arthur.j.odwyer, EricWF

Reviewed By: EricWF

Subscribers: christof, K-ballo, cfe-commits, BillyONeal

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

llvm-svn: 337960

[DataFormatters] Add formatter for C++17 std::optional.

<rdar://problem/41471112>

Patch by Shafik Yaghmour.

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

llvm-svn: 337959

[OPENMP] ThreadId in serialized parallel regions is 0.

The first argument for the parallel outlined functions, called as
serialized parallel regions, should be a pointer to the global thread id
that always is 0.

llvm-svn: 337957

Revert r337904: [IPSCCP] Use PredicateInfo to propagate facts from cmp instructions.

I suspect it is causing the clang-stage2-Rthinlto failures.

llvm-svn: 337956

[libc++] Factor duplicate code into function templates

Summary:
The exact same code was replicated 11 times for implementing the basic_istream
input operators (those that don't use numeric_limits). The same code was also
duplicated twice for implementing the basic_istream input operators that take
numeric_limits into account.

This commit factors the common code into function templates to avoid
the duplication.

Reviewers: mclow.lists, EricWF

Subscribers: christof, dexonsmith, cfe-commits

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

llvm-svn: 337955

[analyzer] Update SMT API documentation and methods

Summary:
Update the documentation of all the classes introduced with the new generic SMT API, most of them were referencing Z3 and how previous operations were being done (like including the context as parameter in a few methods).

Renamed the following methods, so it's clear that the operate on bitvectors:
*`mkSignExt` -> `mkBVSignExt`
*`mkZeroExt` -> `mkBVZeroExt`
*`mkExtract` -> `mkBVExtract`
*`mkConcat` -> `mkBVConcat`

Removed the unecessary methods:
* `getDataExpr`: it was an one line method that called `fromData`
* `mkBitvector(const llvm::APSInt Int)`: it was not being used anywhere

Reviewers: NoQ, george.karpenkov

Reviewed By: george.karpenkov

Subscribers: xazax.hun, szepet, a.sidorin

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

llvm-svn: 337954

[Preprocessor] Stop entering included files after hitting a fatal error.

Fixes a problem when we have multiple inclusion cycles and try to
enumerate all possible ways to reach the max inclusion depth.

rdar://problem/38871876

Reviewers: bruno, rsmith, jkorous, aaron.ballman

Reviewed By: bruno, jkorous, aaron.ballman

Subscribers: dexonsmith, cfe-commits

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

llvm-svn: 337953

Add missing 'override', fixing compilation with some compilers since SVN r337950

llvm-svn: 337952

[COFF] Use comdat shared constants for MinGW as well

GNU binutils tools have no problems with this kind of shared constants,
provided that we actually hook it up completely in AsmPrinter and
produce a global symbol.

This effectively reverts SVN r335918 by hooking the rest of it up
properly.

This feature was implemented originally in SVN r213006, with no reason
for why it can't be used for MinGW other than the fact that GCC doesn't
do it while MSVC does.

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

llvm-svn: 337951

[COFF] Hoist constant pool handling from X86AsmPrinter into AsmPrinter

In SVN r334523, the first half of comdat constant pool handling was
hoisted from X86WindowsTargetObjectFile (which despite the name only
was used for msvc targets) into the arch independent
TargetLoweringObjectFileCOFF, but the other half of the handling was
left behind in X86AsmPrinter::GetCPISymbol.

With only half of the handling in place, inconsistent comdat
sections/symbols are created, causing issues with both GNU binutils
(avoided for X86 in SVN r335918) and with the MS linker, which
would complain like this:

fatal error LNK1143: invalid or corrupt file: no symbol for COMDAT section 0x4

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

llvm-svn: 337950

[libFuzzer] Disable handle-unstable.test for ARM and delete duplicated test file.

Summary:
This change should fix the failures mentioned in
https://reviews.llvm.org/D49684#1175245

Reviewers: kevinwkt, morehouse, metzman

Reviewed By: kevinwkt, morehouse

Subscribers: kristof.beyls, delcypher, chrib, #sanitizers, llvm-commits, kcc

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

llvm-svn: 337949

[analyzer] Fix compilation when LLVM_ENABLE_MODULES=ON

llvm-svn: 337948

[LangRef] Clarify undefined behavior for function attributes.

Violating the invariants specified by attributes is undefined behavior.
Maybe we could use poison instead for some of the parameter attributes,
but I don't think it's worthwhile.

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

llvm-svn: 337947

[windows] Fix warning about comparing ints of different signs

This fixes a warning like this:

warning: comparison of integers of different signs:
      'std::__1::__libcpp_tls_key' (aka 'long') and 'DWORD'
      (aka 'unsigned long') [-Wsign-compare]
  if (*__key == FLS_OUT_OF_INDEXES)
      ~~~~~~ ^  ~~~~~~~~~~~~~~~~~~

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

llvm-svn: 337946

[ARM] Prefer lsls+lsrs over lsls+ands or lsrs+ands in Thumb1.

Saves materializing the immediate for the "ands".

Corresponding patterns exist for lsrs+lsls, but that seems less common
in practice.

Now implemented as a DAGCombine.

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

llvm-svn: 337945

[clang:sema] de-duplicate getDepthAndIndex helpers

Summary:
Continuing off of:
https://reviews.llvm.org/D38382

Fixes:
https://bugs.llvm.org/show_bug.cgi?id=12176

Reviewers: srhines, pirama, vsk

Reviewed By: vsk

Subscribers: cfe-commits, vsk, maitesin

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

llvm-svn: 337944

[SCEV] Add [zs]ext{C,+,x} -> (D + [zs]ext{C-D,+,x})<nuw><nsw> transform

as well as sext(C + x + ...) -> (D + sext(C-D + x + ...))<nuw><nsw>
similar to the equivalent transformation for zext's

if the top level addition in (D + (C-D + x * n)) could be proven to
not wrap, where the choice of D also maximizes the number of trailing
zeroes of (C-D + x * n), ensuring homogeneous behaviour of the
transformation and better canonicalization of such AddRec's

(indeed, there are 2^(2w) different expressions in `B1 + ext(B2 + Y)` form for
the same Y, but only 2^(2w - k) different expressions in the resulting `B3 +
ext((B4 * 2^k) + Y)` form, where w is the bit width of the integral type)

This patch generalizes sext(C1 + C2*X) --> sext(C1) + sext(C2*X) and
sext{C1,+,C2} --> sext(C1) + sext{0,+,C2} transformations added in
r209568 relaxing the requirements the following way:

1. C2 doesn't have to be a power of 2, it's enough if it's divisible by 2
 a sufficient number of times;
2. C1 doesn't have to be less than C2, instead of extracting the entire
  C1 we can split it into 2 terms: (00...0XXX + YY...Y000), keep the
  second one that may cause wrapping within the extension operator, and
  move the first one that doesn't affect wrapping out of the extension
  operator, enabling further simplifications;
3. C1 and C2 don't have to be positive, splitting C1 like shown above
 produces a sum that is guaranteed to not wrap, signed or unsigned;
4. in AddExpr case there could be more than 2 terms, and in case of
  AddExpr the 2nd and following terms and in case of AddRecExpr the
  Step component don't have to be in the C2*X form or constant
  (respectively), they just need to have enough trailing zeros,
  which in turn could be guaranteed by means other than arithmetics,
  e.g. by a pointer alignment;
5. the extension operator doesn't have to be a sext, the same
  transformation works and profitable for zext's as well.

Apparently, optimizations like SLPVectorizer currently fail to
vectorize even rather trivial cases like the following:

 double bar(double *a, unsigned n) {
   double x = 0.0;
   double y = 0.0;
   for (unsigned i = 0; i < n; i += 2) {
     x += a[i];
     y += a[i + 1];
   }
   return x * y;
 }

If compiled with `clang -std=c11 -Wpedantic -Wall -O3 main.c -S -o - -emit-llvm`
(!{!"clang version 7.0.0 (trunk 337339) (llvm/trunk 337344)"})

it produces scalar code with the loop not unrolled with the unsigned `n` and
`i` (like shown above), but vectorized and unrolled loop with signed `n` and
`i`. With the changes made in this commit the unsigned version will be
vectorized (though not unrolled for unclear reasons).

How it all works:

Let say we have an AddExpr that looks like (C + x + y + ...), where C
is a constant and x, y, ... are arbitrary SCEVs. Let's compute the
minimum number of trailing zeroes guaranteed of that sum w/o the
constant term: (x + y + ...). If, for example, those terms look like
follows:

        i
XXXX...X000
YYYY...YY00
   ...
ZZZZ...0000

then the rightmost non-guaranteed-zero bit (a potential one at i-th
position above) can change the bits of the sum to the left (and at
i-th position itself), but it can not possibly change the bits to the
right. So we can compute the number of trailing zeroes by taking a
minimum between the numbers of trailing zeroes of the terms.

Now let's say that our original sum with the constant is effectively
just C + X, where X = x + y + .... Let's also say that we've got 2
guaranteed trailing zeros for X:

         j
CCCC...CCCC
XXXX...XX00  // this is X = (x + y + ...)

Any bit of C to the left of j may in the end cause the C + X sum to
wrap, but the rightmost 2 bits of C (at positions j and j - 1) do not
affect wrapping in any way. If the upper bits cause a wrap, it will be
a wrap regardless of the values of the 2 least significant bits of C.
If the upper bits do not cause a wrap, it won't be a wrap regardless
of the values of the 2 bits on the right (again).

So let's split C to 2 constants like follows:

0000...00CC  = D
CCCC...CC00  = (C - D)

and represent the whole sum as D + (C - D + X). The second term of
this new sum looks like this:

CCCC...CC00
XXXX...XX00
-----------  // let's add them up
YYYY...YY00

The sum above (let's call it Y)) may or may not wrap, we don't know,
so we need to keep it under a sext/zext. Adding D to that sum though
will never wrap, signed or unsigned, if performed on the original bit
width or the extended one, because all that that final add does is
setting the 2 least significant bits of Y to the bits of D:

YYYY...YY00 = Y
0000...00CC = D
-----------  <nuw><nsw>
YYYY...YYCC

Which means we can safely move that D out of the sext or zext and
claim that the top-level sum neither sign wraps nor unsigned wraps.

Let's run an example, let's say we're working in i8's and the original
expression (zext's or sext's operand) is 21 + 12x + 8y. So it goes
like this:

0001 0101  // 21
XXXX XX00  // 12x
YYYY Y000  // 8y

0001 0101  // 21
ZZZZ ZZ00  // 12x + 8y

0000 0001  // D
0001 0100  // 21 - D = 20
ZZZZ ZZ00  // 12x + 8y

0000 0001  // D
WWWW WW00  // 21 - D + 12x + 8y = 20 + 12x + 8y

therefore zext(21 + 12x + 8y) = (1 + zext(20 + 12x + 8y))<nuw><nsw>

This approach could be improved if we move away from using trailing
zeroes and use KnownBits instead. For instance, with KnownBits we could
have the following picture:

    i
10 1110...0011  // this is C
XX X1XX...XX00  // this is X = (x + y + ...)

Notice that some of the bits of X are known ones, also notice that
known bits of X are interspersed with unknown bits and not grouped on
the rigth or left.

We can see at the position i that C(i) and X(i) are both known ones,
therefore the (i + 1)th carry bit is guaranteed to be 1 regardless of
the bits of C to the right of i. For instance, the C(i - 1) bit only
affects the bits of the sum at positions i - 1 and i, and does not
influence if the sum is going to wrap or not. Therefore we could split
the constant C the following way:

    i
00 0010...0011  = D
10 1100...0000  = (C - D)

Let's compute the KnownBits of (C - D) + X:

XX1 1            = carry bit, blanks stand for known zeroes
 10 1100...0000  = (C - D)
 XX X1XX...XX00  = X
--- -----------
 XX X0XX...XX00

Will this add wrap or not essentially depends on bits of X. Adding D
to this sum, however, is guaranteed to not to wrap:

0    X
 00 0010...0011  = D
 sX X0XX...XX00  = (C - D) + X
--- -----------
 sX XXXX   XX11

As could be seen above, adding D preserves the sign bit of (C - D) +
X, if any, and has a guaranteed 0 carry out, as expected.

The more bits of (C - D) we constrain, the better the transformations
introduced here canonicalize expressions as it leaves less freedom to
what values the constant part of ((C - D) + x + y + ...) can take.

Reviewed By: mzolotukhin, efriedma

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

llvm-svn: 337943

[windows] Don't inline fieldFromInstruction on Windows

Summary:
The VS compiler (on Windows) has a bug which results in fieldFromInstruction being optimized out in some circumstances. This only happens in *release no debug info* builds that have assertions *turned off* - in all other situations the function is not inlined, so the functionality is correct. All of the bots have assertions turned on, so this path is not regularly tested. The workaround is to not inline the function on Windows - if the bug is fixed in a later release of the VS compiler, the noinline specification can be removed.

The test that consistently reproduces this is Lanai v11.txt test.

Reviewers: asmith, labath, zturner

Subscribers: dblaikie, stella.stamenova, aprantl, JDevlieghere, llvm-commits

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

llvm-svn: 337942

[OPENMP] Exclude service expressions/statements from the list of
the children.

Special internal helper expressions/statements for the OpenMP directives
should not be exposed as children, only the main substatement must be
represented as the child.

llvm-svn: 337941

Add an option to specify the name of
an function whose CFG is to be viewed/printed.

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

llvm-svn: 337940

Fix corruption of result number in LegalizeVectorOps.cpp

When VectorLegalizer::LegalizeOp creates a new SDValue after iterating
over its arguments, we need to refer to the same result number of the
new node that the original value used.

Reviewed by: cameron.mcinally

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

llvm-svn: 337939

[AMDGPU] Use AssumptionCacheTracker in the divrem32 expansion

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

llvm-svn: 337938

[CMake] Use LIBCXXABI_LIBDIR_SUFFIX in libc++abi build

This was changed unintentionally in r335809.

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

llvm-svn: 337937

Fix llvm::ComputeNumSignBits with some operations and llvm.assume

Currently ComputeNumSignBits does early exit while processing some
of the operations (add, sub, mul, and select). This prevents the
function from using AssumptionCacheTracker if passed.

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

llvm-svn: 337936

Revert "dwarfgen: Add support for generating the debug_str_offsets section, take 2"

This reverts commit r337933. The build error is fixed but the test now
fails on the darwin buildbots. Investigating...

llvm-svn: 337935

[Hexagon] Properly scale bit index when extracting elements from vNi1

For example v = <2 x i1> is represented as bbbbaaaa in a predicate register,
where b = v[1], a = v[0]. Extracting v[1] is equivalent to extracting bit 4
from the predicate register.

llvm-svn: 337934

dwarfgen: Add support for generating the debug_str_offsets section, take 2

This recommits r337910 after fixing an "ambiguous call to addAttribute"
error with some compilers (gcc circa 4.9 and MSVC). It seems that these
compilers will consider a "false -> pointer" conversion during overload
resolution. This creates ambiguity because one I added an overload which
takes a MCExpr * as an argument.

I fix this by making the new overload take MCExpr&, which avoids the
conversion. It also documents the fact that we expect a valid MCExpr
object.

Original commit message follows:

The motivation for this is D49493, where we'd like to test details of
debug_str_offsets behavior which is difficult to trigger from a
traditional test.

This adds the plubming necessary for dwarfgen to generate this section.
The more interesting changes are:
- I've moved emitStringOffsetsTableHeader function from DwarfFile to
  DwarfStringPool, so I can generate the section header more easily from
  the unit test.
- added a new addAttribute overload taking an MCExpr*. This is used to
  generate the DW_AT_str_offsets_base, which links a compile unit to the
  offset table.

I've also added a basic test for reading and writing DW_form_strx forms.

Reviewers: dblaikie, JDevlieghere, probinson

Subscribers: llvm-commits, aprantl

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

llvm-svn: 337933

[ProcessGDBRemote] handle result from ConnectToDebugserver

We ignored the result from ConnectToDebugserver, causing certain errors
(like a failed handshake) not to surface.

llvm-svn: 337932

Use LLVM's new ItaniumPartialDemangler in LLDB

Summary:
Replace the existing combination of FastDemangle and the fallback to llvm::itaniumDemangle() with LLVM's new ItaniumPartialDemangler. It slightly reduces complexity and slightly improves performance, but doesn't introduce conceptual changes. This patch is preparing for more fundamental improvements on LLDB's demangling approach.

Reviewers: friss, jingham, erik.pilkington, labath, clayborg, mgorny, davide, JDevlieghere

Reviewed By: JDevlieghere

Subscribers: teemperor, JDevlieghere, labath, clayborg, davide, lldb-commits, mgorny, erik.pilkington

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

llvm-svn: 337931

Move JIT listener C binding fallbackks to ExecutionEngineBindings.cpp.

Initially, in https://reviews.llvm.org/D44890, I had these defined as
empty functions inside the header when the respective event listener
was not built in. As done in that commit, that wasn't correct, because
it was a ODR violation.  Krasimir hot-fixed that in r333265, but that
wasn't quite right either, because it'd lead to the symbol not being
available.

Instead just move the fallbacksto ExecutionEngineBindings.cpp. Could
define them as static inlines in the header too, but I don't think it
matters.

Reviewers: whitequark

Subscribers: llvm-commits

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

llvm-svn: 337930

[XRay tests] Don't filter test-critical calls

By default, xray filters events that takes less than 5uS from its log.
In this existing test, should printf complete very quickly this will
lead to test-critical function calls being filtered (i.e. print_parent_tid).
Given that we're not testing the filtering feature, disable it for this
test.

llvm-svn: 337929

[OPENMP] Fix PR38256: Fix locations of the artificial conditional op.

Fixed the source locations of the conditional op so that they don'r
crash coverage pass.

llvm-svn: 337928

Fix tsan doc

llvm-svn: 337927

[Docs] Update supported oses for safestack, ubsan, asan, tsan and msan

Adding oses others than Linux.

llvm-svn: 337926

[NFC] Fix grammatical mistakes in libc++ FileTimeType design docs

llvm-svn: 337925

Revert "dwarfgen: Add support for generating the debug_str_offsets section"

This reverts commit r337910 as it's generating "ambiguous call to
addAttribute" errors on some bots.

Will resubmit once I get a chance to look into the problem.

llvm-svn: 337924

[analyzer] Use the macro REGISTER_TRAIT_WITH_PROGRAMSTATE in the Z3 backend

Summary:
The macro was manually expanded in the Z3 backend and this patch adds it back.

Adding the expanded code is dangerous as the macro may change in the future and the expanded code might be left outdated.

Reviewers: NoQ, george.karpenkov

Reviewed By: george.karpenkov

Subscribers: xazax.hun, szepet, a.sidorin

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

llvm-svn: 337923

[analyzer] Removed API used by the Refutation Manager from SMTConstraintManager and replace by proper calls to SMTSolver

Summary:
Third patch in the refactoring series, to decouple the SMT Solver from the Refutation Manager (1st: D49668, 2nd: D49767).

The refutation API in the `SMTConstraintManager` was a hack to allow us to create an SMT solver and verify the constraints; it was conceptually wrong from the start. Now, we don't actually need to use the `SMTConstraintManager` and can create an SMT object directly, add the constraints and check them.

While updating the Falsification visitor, I inlined the two functions that were used to collect the constraints and add them to the solver.

As a result of this patch, we could move the SMT API elsewhere and as it's not really dependent on the CSA anymore. Maybe we can create a new dir (utils/smt) for Z3 and future solvers?

Reviewers: NoQ, george.karpenkov

Reviewed By: george.karpenkov

Subscribers: xazax.hun, szepet, a.sidorin

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

llvm-svn: 337922

[analyzer] Moved code from SMTConstraintManager to SMTSolver

Summary:
This is the second part of D49668, and moves all the code that's not specific to a ConstraintManager to SMTSolver.

No functional change intended.

Reviewers: NoQ, george.karpenkov

Reviewed By: george.karpenkov

Subscribers: xazax.hun, szepet, a.sidorin

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

llvm-svn: 337921

[analyzer] Try to minimize the number of equivalent bug reports evaluated by the refutation manager

Summary:
This patch changes how the SMT bug refutation runs in an equivalent bug report class.

Now, all other visitor are executed until they find a valid bug or mark all bugs as invalid. When the one valid bug is found (and crosscheck is enabled), the SMT refutation checks the satisfiability of this single bug.

If the bug is still valid after checking with Z3, it is returned and a bug report is created. If the bug is found to be invalid, the next bug report in the equivalent class goes through the same process, until we find a valid bug or all bugs are marked as invalid.

Massive speedups when verifying redis/src/rax.c, from 1500s to 10s.

Reviewers: NoQ, george.karpenkov

Reviewed By: george.karpenkov

Subscribers: xazax.hun, szepet, a.sidorin

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

llvm-svn: 337920

[analyzer] Moved non solver specific code from Z3ConstraintManager to SMTConstraintManager

Summary:
This patch moves a lot of code from `Z3ConstraintManager` to `SMTConstraintManager`, leaving only the necessary:
* `canReasonAbout` which returns if a Solver can handle a given `SVal` (should be moved to `SMTSolver` in the future).
* `removeDeadBindings`, `assumeExpr` and `print`: methods that need to use `ConstraintZ3Ty`, can probably be moved to `SMTConstraintManager` in the future.

The patch creates a new file, `SMTConstraintManager.cpp` with the moved code. Conceptually, this is move in the right direction and needs further improvements: `SMTConstraintManager` still does a lot of things that are not required by a `ConstraintManager`.

We ought to move the unrelated to `SMTSolver` and remove everything that's not related to a `ConstraintManager`. In particular, we could remove `addRangeConstraints` and `isModelFeasible`, and make the refutation manager create an Z3Solver directly.

Reviewers: NoQ, george.karpenkov

Reviewed By: george.karpenkov

Subscribers: mgorny, xazax.hun, szepet, a.sidorin

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

llvm-svn: 337919

[analyzer] Implemented SMT generic API

Summary:
Created new SMT generic API.

Small changes to `Z3ConstraintManager` because of the new generic objects (`SMTSort` and `SMTExpr`) returned by `SMTSolver`.

Reviewers: george.karpenkov, NoQ

Reviewed By: george.karpenkov

Subscribers: mgorny, xazax.hun, szepet, a.sidorin

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

llvm-svn: 337918

[analyzer] Create generic SMT Expr class

Summary:
New base class for all future SMT Exprs.

No major changes except moving `areEquivalent` and `getFloatSemantics` outside of `Z3Expr` to keep the class minimal.

Reviewers: NoQ, george.karpenkov

Reviewed By: george.karpenkov

Subscribers: xazax.hun, szepet, a.sidorin

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

llvm-svn: 337917