[LVI] Learn value ranges from ctpop results (#121945)

Fixes #115751.

[LVI] Thread binop over select with constant arms (#110212)

Motivating case from https://github.com/delta-io/delta-rs:
https://alive2.llvm.org/ce/z/3mzr4C

[LVI] Fix insertelement of constexpr

Bail out when evaluating an insertelement of a constant expression.
Unlike other ValueLattice kinds, these don't have implicit splat
semantics and we end up with

[LVI] Fix insertelement of constexpr

Bail out when evaluating an insertelement of a constant expression.
Unlike other ValueLattice kinds, these don't have implicit splat
semantics and we end up with type mismatches. If we actually wanted
to handle these, we should actually evaluate the insertion via
constant folding. I'm not bothering with that, as these should
get constant folded on construction already.

show more ...

[LVI] Infer non-zero from equality icmp (#112838)

This following pattern is common in loop headers:
```
%101 = sub nuw i64 %78, %98
%103 = icmp eq i64 %78, %98
br i1 %103, label %.thread.i

[LVI] Infer non-zero from equality icmp (#112838)

This following pattern is common in loop headers:
```
%101 = sub nuw i64 %78, %98
%103 = icmp eq i64 %78, %98
br i1 %103, label %.thread.i.i, label %.preheader.preheader.i.i

.preheader.preheader.i.i:
%invariant.umin.i.i = call i64 @llvm.umin.i64(i64 %101, i64 9)
%umax.i = call i64 @llvm.umax.i64(i64 %invariant.umin.i.i, i64 1)
br label %.preheader.i.i

.preheader.i.i:
...
%116 = add nuw nsw i64 %.011.i.i, 1
%exitcond.not.i = icmp eq i64 %116, %umax.i
br i1 %exitcond.not.i, label %.critedge.i.i, label %.preheader.i.i
```
As `%78` is not equal to `%98` in BB `.preheader.preheader.i.i`, we can
prove `%101` is non-zero. Then we can simplify the loop exit condition.

Addresses regression introduced by
https://github.com/llvm/llvm-project/pull/112742.

show more ...

[LLVM] Add `Intrinsic::getDeclarationIfExists` (#112428)

Add `Intrinsic::getDeclarationIfExists` to lookup an existing
declaration of an intrinsic in a `Module`.

[ValueTracking] Use isSafeToSpeculativelyExecuteWithVariableReplaced() in more places (#109149)

This replaces some uses of isSafeToSpeculativelyExecute() with
isSafeToSpeculativelyExecuteWithVariab

[ValueTracking] Use isSafeToSpeculativelyExecuteWithVariableReplaced() in more places (#109149)

This replaces some uses of isSafeToSpeculativelyExecute() with
isSafeToSpeculativelyExecuteWithVariableReplaced(), in cases where we
are guarding against operand changes rather plain speculation.

I believe that this is NFC with the current implementation of the
function (as it only does something different from loads), but this
makes us more defensive against future generalizations.

show more ...

[ValueLattice] Move intersect from LVI into ValueLattice API (NFC)

So we can reuse the logic inside IPSCCP.

[Analysis] Copy-construct SmallVector (NFC) (#105911)

[LLVM] Fix missing includes for function declarations that will be needed for explicit symbol visibility (#103900)

In multiple source files function definitions never sees there
declaration in a he

[LLVM] Fix missing includes for function declarations that will be needed for explicit symbol visibility (#103900)

In multiple source files function definitions never sees there
declaration in a header because its never included causing linker errors
when explicit symbol visibility macros\dllexport are added to the
declarations.

Most of these were originally found by @tstellar in
https://github.com/llvm/llvm-project/pull/67502

TargetRegistry.h is needed in MCExternalSymbolizer.cpp for
createMCSymbolizer
Analysis/Passes.h is needed in LazyValueInfo.cpp and RegionInfo.cpp for
createLazyValueInfoPassin and createRegionInfoPass
Transforms/Scalar.h is needed in SpeculativeExecution.cpp for
createSpeculativeExecutionPass

show more ...

[LVI][NFC] Delete an outdated comment (#101504)

Transitioned from inheritance to has-a relationship in 9db7948e

[CVP][LVI] Add support for InsertElementInst in LVI (#99368)

Currently, the LVI analysis pass doesn't support InsertElementInst
vector instruction. Due to this, some optimization opportunities are

[CVP][LVI] Add support for InsertElementInst in LVI (#99368)

Currently, the LVI analysis pass doesn't support InsertElementInst
vector instruction. Due to this, some optimization opportunities are
missed. For example, in the below example, ICMP instruction can be
folded but it doesn't.

```
...
%ie1 = insertelement <2 x i32> poison, i32 10, i64 0
%ie2 = insertelement <2 x i32> %ie1, i32 20, i64 1
%icmp = icmp <2 x i1> %ie2, <i32 40, i32 40>
...
```

This change adds InsertElementInst support in the LVI analysis pass to
fix the motivating example.

show more ...

[ValueLattice] Add asConstantRange() helper (NFC)

Move the toConstantRange() helper from LVI into ValueLattice,
so it can be reused in other places like SCCP.

[LVI][CVP] Add support for vector comparisons

[IR] Add Constant::toConstantRange() (NFC)

The logic in llvm::getVectorConstantRange() can be a bit
inconvenient to use in some cases because of the need to handle
the scalar case separately. Genera

[IR] Add Constant::toConstantRange() (NFC)

The logic in llvm::getVectorConstantRange() can be a bit
inconvenient to use in some cases because of the need to handle
the scalar case separately. Generalize it to handle all constants,
and move it to live directly on Constant.

show more ...

[LVI] Use Constant instead of Tristate for predicate results

A lot of the users just end up converting it into a Constant
themselves. Doing this in the API leaves less room for error
with vector typ

[LVI] Use Constant instead of Tristate for predicate results

A lot of the users just end up converting it into a Constant
themselves. Doing this in the API leaves less room for error
with vector types, and brings getPredicateResult() closer to
LatticeValueElement::getCompare(), hopefully allowing us to
consolidate them.

show more ...

[LVI] Simplify the getPredicateResult() implementation (NFC)

By using ConstantRange::icmp().

[CVP][LVI] Fix incorrect scalar type when getting constant folded vec (#97682)

Fixes #97674

After #97428 added support for vectors, our constant ranges can now be
from splat vectors so when they

[CVP][LVI] Fix incorrect scalar type when getting constant folded vec (#97682)

Fixes #97674

After #97428 added support for vectors, our constant ranges can now be
from splat vectors so when they reduce to a singe constant value, we
need to return the original type as opposed to just an int.

show more ...

[LVI] Use CmpInst::Predicate in APIs (NFC)

Unfortunately this requires including InstrTypes.h in the header,
but I think that's fine given that that LazyValueInfo.h is not
widely used.

[ValueTracking][LVI] Consolidate vector constant range calculation

Add a common helper used for computeConstantRange() and LVI. The
implementation is a mix of both, with the efficient handling for
C

[ValueTracking][LVI] Consolidate vector constant range calculation

Add a common helper used for computeConstantRange() and LVI. The
implementation is a mix of both, with the efficient handling for
ConstantDataVector taken from computeConstantRange(), and the
general handling (including non-splat poison) from LVI.

show more ...

[CVP][LVI] Add support for vectors (#97428)

The core change here is to add support for converting vector constants
into constant ranges. The rest is just relaxing isIntegerTy() checks and
making s

[CVP][LVI] Add support for vectors (#97428)

The core change here is to add support for converting vector constants
into constant ranges. The rest is just relaxing isIntegerTy() checks and
making sure we don't use APIs that assume vectors.

There are a couple of places that don't support vectors yet, most
notably the "simplest" fold (comparisons to a constant) isn't supported
yet. I'll leave these to a followup.

show more ...

[IR] Don't include Module.h in Analysis.h (NFC) (#97023)

Replace it with a forward declaration instead. Analysis.h is pulled in
by all passes, but not all passes need to access the module.

[IR] Add getDataLayout() helpers to Function and GlobalValue (#96919)

Similar to https://github.com/llvm/llvm-project/pull/96902, this adds
`getDataLayout()` helpers to Function and GlobalValue, re

[IR] Add getDataLayout() helpers to Function and GlobalValue (#96919)

Similar to https://github.com/llvm/llvm-project/pull/96902, this adds
`getDataLayout()` helpers to Function and GlobalValue, replacing the
current `getParent()->getDataLayout()` pattern.

show more ...

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[llvm] format and terminate namespaces with closing comment (#94917)

Namespaces are terminated with a closing comment in the majority of the
codebase so do the same here for consistency. Also forma

[llvm] format and terminate namespaces with closing comment (#94917)

Namespaces are terminated with a closing comment in the majority of the
codebase so do the same here for consistency. Also format code within
some namespaces to make clang-format happy.

show more ...

[LVI][ConstantRange] Generalize mask not equal conditions handling

Extend `V & Mask != 0` for non-zero constants if satisfiable, when
retrieving constraint value information from a non-equality comp

[LVI][ConstantRange] Generalize mask not equal conditions handling

Extend `V & Mask != 0` for non-zero constants if satisfiable, when
retrieving constraint value information from a non-equality comparison.

Proof: https://alive2.llvm.org/ce/z/dc5BeT.

Motivating example: https://github.com/gcc-mirror/gcc/blob/master/gcc/testsuite/gcc.dg/tree-ssa/vrp76.c.

show more ...