[ConstraintElim] Use default depth for most calls of isNonNegative.

Helps to improve resuls in some cases, while being overall neutral with
respect to compile-time,
https://llvm-compile-time-tracker

[ConstraintElim] Use default depth for most calls of isNonNegative.

Helps to improve resuls in some cases, while being overall neutral with
respect to compile-time,
https://llvm-compile-time-tracker.com/compare.php?from=2c9b6c1b36b8185299de083c3058e0c1e7760442&to=5984b1649dc12741308089de235647cf036df95f&stat=instructions:u

show more ...

[ConstraintElim] Add (UGE, var, 0) to unsigned system for new vars. (#76262)

The constraint system used for ConstraintElimination assumes all
varibles to be signed. This can cause missed optimizati

[ConstraintElim] Add (UGE, var, 0) to unsigned system for new vars. (#76262)

The constraint system used for ConstraintElimination assumes all
varibles to be signed. This can cause missed optimization in the
unsigned system, due to missing the information that all variables are
unsigned (non-negative).

Variables can be marked as non-negative by adding Var >= 0 for all
variables. This is done for arguments on ConstraintInfo construction and
after adding new variables. This handles cases like the ones outlined in
https://discourse.llvm.org/t/why-does-llvm-not-perform-range-analysis-on-integer-values/74341

The original example shared above is now handled without this change,
but adding another variable means that instcombine won't be able to
simplify examples like https://godbolt.org/z/hTnra7zdY

Adding the extra variables comes with a slight compile-time increase
https://llvm-compile-time-tracker.com/compare.php?from=7568b36a2bc1a1e496ec29246966ffdfc3a8b87f&to=641a47f0acce7755e340447386013a2e086f03d9&stat=instructions:u

stage1-O3 stage1-ReleaseThinLTO stage1-ReleaseLTO-g stage1-O0-g
+0.04% +0.07% +0.05% +0.02%
stage2-O3 stage2-O0-g stage2-clang
+0.05% +0.05% +0.05%

https://github.com/llvm/llvm-project/pull/76262

show more ...

[ConstraintElim] Handle trivial (ICMP_ULE, 0, B) in doesHold.

D152730 may add trivial pre-conditions of the form (ICMP_ULE, 0, B),
which won't be handled automatically by the constraint system, beca

[ConstraintElim] Handle trivial (ICMP_ULE, 0, B) in doesHold.

D152730 may add trivial pre-conditions of the form (ICMP_ULE, 0, B),
which won't be handled automatically by the constraint system, because
we don't add Var >= 0 for all variables in the unsigned system.

Handling the trivial condition explicitly here avoids having the
increase the number of rows in the system per variable.

https://alive2.llvm.org/ce/z/QC92ur

Depends on D152730.

Fixes #63125.

Reviewed By: nikic

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

show more ...

[ConstraintElim] Add A < B if A is an increasing phi for A != B.

This patch adds additional logic to add additional facts for A != B, if
A is a monotonically increasing induction phi. The motivating

[ConstraintElim] Add A < B if A is an increasing phi for A != B.

This patch adds additional logic to add additional facts for A != B, if
A is a monotonically increasing induction phi. The motivating use case
for this is removing checks when using iterators with hardened libc++,
e.g. https://godbolt.org/z/zhKEP37vG.

The patch pulls in SCEV to detect AddRecs. If possible, the patch adds
the following facts for a AddRec phi PN with StartValue as incoming
value from the loo preheader and B being an upper bound for PN from a
condition in the loop header.

* (ICMP_UGE, PN, StartValue)
* (ICMP_ULT, PN, B) [if (ICMP_ULE, StartValue, B)]

The patch also adds an optional precondition to FactOrCheck (the new
DoesHold field) , which can be used to only add a fact if the
precondition holds at the point the fact is added to the constraint
system.

Depends on D151799.

Reviewed By: nikic

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

show more ...

[ConstraintElim] Remove dead compares after simplification.

Remove compares after replacing all uses. Cleaning dead compares can
enable additional simplifications when adjusting the position of the

[ConstraintElim] Remove dead compares after simplification.

Remove compares after replacing all uses. Cleaning dead compares can
enable additional simplifications when adjusting the position of the
pass slightly. In particular, it seems like the additional dead
instructions may prevent SimplifyCFG performing some folds.

Reviewed By: nikic

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

show more ...

[ConstraintElimination] Add test that crash in earlier var handling.

Add a test that caused a crash in the new variable handling code in
earlier versions.

[ConstraintElimination] Update tests to use opaque pointers.

[ConstraintElimination] Allow adding pre-conditions for constraints.

With this patch pre-conditions can be added to a list of constraints.
Constraints with pre-conditions can only be used if all pre

[ConstraintElimination] Allow adding pre-conditions for constraints.

With this patch pre-conditions can be added to a list of constraints.
Constraints with pre-conditions can only be used if all pre-conditions
are satisfied when the constraint is used.

The pre-conditions at the moment are specified as a list of
(Predicate, Value *,Value *) tuples. This allow easily checking them
like any other condition, using the existing infrastructure.

This then is used to limit GEP decomposition to cases where we can
prove that offsets are signed positive.

This fixes a couple of incorrect transforms where GEP offsets where
assumed to be signed positive, but they were not.

Note that this effectively disables GEP decomposition, as there's no
support for reasoning about signed predicates. D118806 adds initial
signed support.

Fixes PR49624.

Reviewed By: reames

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

show more ...

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
I

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
In this patch focus has been put on test cases for ConstantMerge,
ConstraintElimination, CorrelatedValuePropagation, GlobalDCE,
GlobalOpt, SCCP, TailCallElim and PredicateInfo.

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

show more ...

[ConstraintElimination] Decompose a few more GEP indices.

This patch adds handling for zero-extended GEP indices.

[ConstraintElimination] Improve index handing during constraint building.

This patch improves the index management during constraint building.
Previously, the code rejected constraints which used va

[ConstraintElimination] Improve index handing during constraint building.

This patch improves the index management during constraint building.
Previously, the code rejected constraints which used values that were not
part of Value2Index, but after combining the coefficients of the new
indices were 0 (if ShouldAdd was 0).

In those cases, no new indices need to be added. Instead of adding to
Value2Index directly, add new indices to the NewIndices map. The caller
can then check if it needs to add any new indices.

This enables checking constraints like `a + x <= a + n` to `x <= n`,
even if there is no constraint for `a` directly.

show more ...

[ConstraintElimination] Add additional tests.

Adds additional test cases with zexts, conditions that require temporary
indices.

[ConstraintElimination] Extend test coverage.

This patch adds a lot of additional tests, focusing on loops and GEP
arithmetic. Some of the tests expose existing problems, which will be
fixed soon.