[ConstraintElim] Queue facts and checks directly.

This allows interleaving facts and checks in a single block. In
particular this enables using facts from assumes for conditions in the
same block th

[ConstraintElim] Queue facts and checks directly.

This allows interleaving facts and checks in a single block. In
particular this enables using facts from assumes for conditions in the
same block that come after the assume.

This could be extended to only try to simplify checks at the point where
a condition is used.

Reviewed By: nikic

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

show more ...

[ConstraintElim] Update comment after recent changes.

Update the comment to reflect the current code.

[ConstraintElim] Use collectOffset result for chained gep support.

This slightly simplifies the code and addresses a correctness issue
where the index scaling for the precondition was not considered

[ConstraintElim] Use collectOffset result for chained gep support.

This slightly simplifies the code and addresses a correctness issue
where the index scaling for the precondition was not considered
properly.

Thanks to @nikic for pointing that out in D137840.

show more ...

[ConstraintElim] Use collectOffset instead of custom GEP idx iteration.

Use collectOffset to collect scaled indices and constant offset for GEP
instead of custom code. This simplifies the logic in d

[ConstraintElim] Use collectOffset instead of custom GEP idx iteration.

Use collectOffset to collect scaled indices and constant offset for GEP
instead of custom code. This simplifies the logic in decomposeGEP and
allows to handle all cases supported by the generic helper.

show more ...

[ConstraintElimination] Use SmallVectorImpl (NFC)

When passing a SmallVector by reference, don't specify its size.

[ConstraintElimination] Add Decomposition struct (NFCI)

Replace the vector of DecompEntry with a struct that stores the
constant offset separately. I think this is cleaner than giving the
first elem

[ConstraintElimination] Add Decomposition struct (NFCI)

Replace the vector of DecompEntry with a struct that stores the
constant offset separately. I think this is cleaner than giving the
first element special handling.

This probably also fixes some potential ubsan errors by more
consistently using addWithOverflow/multiplyWithOverflow.

show more ...

[ConstraintElimination] Make decompose() infallible

decompose() currently returns a mix of {} and 0 + 1*V on failure.
This changes it to always return the 0 + 1*V form, thus making
decompose() infal

[ConstraintElimination] Make decompose() infallible

decompose() currently returns a mix of {} and 0 + 1*V on failure.
This changes it to always return the 0 + 1*V form, thus making
decompose() infallible.

This makes the code marginally more powerful, e.g. we now fold
sub_decomp_i80 by treating the constant as a symbolic value.

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

show more ...

[ConstraintElim] Drop bail out for scalable vectors after using getTrue

ConstantInt::getTrue/getFalse can materialize scalable vectors with all
lanes true/false.

[ConstraintElim] Use ConstantInt::getTrue to create constants (NFC).

Use existing ConstantInt::getTrue/getFalse functionality instead of
custom getScalarConstOrSplat as suggested by @nikic.

[ConstraintElimination] Skip compares with scalable vector types.

Materializing scalable vectors with boolean values is not implemented
yet. Skip those cases for now and leave a TODO.

[ConstraintElimination] Generate true/false vectors for vector cmps.

This fixes crashes when vector compares can be simplified to true/false.

[ConstraintElimination] Do not crash on vector GEP in decomposeGEP

Commit 359bc5c541ae4b02 caused
Assertion `isa<To>(Val) && "cast<Ty>() argument of incompatible type!"'
failures in decomposeGEP wh

[ConstraintElimination] Do not crash on vector GEP in decomposeGEP

Commit 359bc5c541ae4b02 caused
Assertion `isa<To>(Val) && "cast<Ty>() argument of incompatible type!"'
failures in decomposeGEP when the GEP pointer operand is a vector.

Fix is to use DataLayout::getIndexTypeSizeInBits when fetching the
index size, as it will use the scalar type in case of a ptr vector.

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

show more ...

[ConstraintElimination] Fix nested GEP check.

At the moment, the implementation requires that the outer GEP has a
single index, the inner GEP can have an arbitrary indices, because the
general `deco

[ConstraintElimination] Fix nested GEP check.

At the moment, the implementation requires that the outer GEP has a
single index, the inner GEP can have an arbitrary indices, because the
general `decompose` helper is used.

show more ...

ConstraintElimination - pass const DataLayout by reference in (recursive) MergeResults lambda capture. NFC.

There's no need to copy this and fixes a coverity remark about large copy by value

[ConstraintElim] Use helper to allow overflow for coefficients of GEPs

If the arithmetic for indices of inbounds GEPs overflows, the result is
poison. This means it is also OK for the coefficients t

[ConstraintElim] Use helper to allow overflow for coefficients of GEPs

If the arithmetic for indices of inbounds GEPs overflows, the result is
poison. This means it is also OK for the coefficients to overflow. GEP
decomposition is limited to cases where the index size is <= 64 bit,
which can be represented by int64_t used for the coefficients in the
constraint system.

show more ...

[ConstraintElim] Fix signed integer overflow for inbounds GEP.

For inbounds GEPs, signed overflow yields poison, so it is fine for the
coefficients to wrap as well. This fixes an UBSan failure.

[ConstraintElim] Replace custom GEP index handling by using existing code

Instead of duplicating the existing decomposition code for GEP indices
just use the existing code by calling the existing de

[ConstraintElim] Replace custom GEP index handling by using existing code

Instead of duplicating the existing decomposition code for GEP indices
just use the existing code by calling the existing decompose function on
the index expression and multiply the result's coefficients by the scale of
the index.

This both reduces code duplication and generalizes the pattern we can
handle.

show more ...

[ConstraintElim] Support `add nsw` for unsigned preds with positive ops.

If both operands of an `add nsw` are known positive, it can be treated
the same as `add nuw` and added to the unsigned system

[ConstraintElim] Support `add nsw` for unsigned preds with positive ops.

If both operands of an `add nsw` are known positive, it can be treated
the same as `add nuw` and added to the unsigned system.

https://alive2.llvm.org/ce/z/6gprff

show more ...

[ConstraintElim] Support unsigned decomposition of mul/shl nuw..const

Support decomposition for `mul/shl nuw` with constant operand for unsigned
queries. Those expressions should not wrap in the uns

[ConstraintElim] Support unsigned decomposition of mul/shl nuw..const

Support decomposition for `mul/shl nuw` with constant operand for unsigned
queries. Those expressions should not wrap in the unsigned sense and can
be added directly to the unsigned system.

show more ...

[ConstraintElim] Support signed decomposition of `add nsw`.

Add support decomposition for `add nsw` for signed queries.
`add nsw` won't wrap and can be directly added to the signed
system.

[ConstraintElimination] Move logic for replacing ssub overflow users (NFC)

Reviewed By: fhahn

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

[ConstraintElim] Add debug message when decomposition fails.

[ConstraintElim] Add support for GEPs with multiple indices.

Lift restriction on GEPs with a single index by iterating over all
indices and joining the {Coefficient, Variable} entries for all indice

[ConstraintElim] Add support for GEPs with multiple indices.

Lift restriction on GEPs with a single index by iterating over all
indices and joining the {Coefficient, Variable} entries for all indices
together.

show more ...

[ConstraintElim] Move check-and-replace logic to helper function (NFC).

Move logic to check and replace conditions to a helper function. This
isolates the code, allows using early returns, reduces t

[ConstraintElim] Move check-and-replace logic to helper function (NFC).

Move logic to check and replace conditions to a helper function. This
isolates the code, allows using early returns, reduces the
indentation and simplifies eliminateConstraints.

show more ...

[ConstraintElim] Use MulOverflow to avoid UB on signed overflow.

This fixes an UBSan failure after 359bc5c541ae. For inbounds GEP with
index sizes <= 64, having the coefficients overflowing is fine.