[ConstraintElim] Remove dead code. NFC. (#118983)

`R2` should be always greater than `R1` here because both `R1` and `R2` are not modified inside the loop.

[Analysis] Use range-based for loops (NFC) (#96587)

[ConstraintSystem] Drop left-over parentheses. (NFC)

Remove left over redundant parentheses after 9b6127d7 as pointed out by
@nikic.

[ConstraintSystem] Remove GCD handling (NFCI).

As @dtcxzyw pointed out in
https://github.com/llvm/llvm-project/pull/76299#pullrequestreview-1795471115
the current GCD handling is effectively a no-op

[ConstraintSystem] Remove GCD handling (NFCI).

As @dtcxzyw pointed out in
https://github.com/llvm/llvm-project/pull/76299#pullrequestreview-1795471115
the current GCD handling is effectively a no-op, as NewGCD will always
by 1, as it is initially initialized as 1.

This patch removes the uses of GCD and its computation. This slightly
reduces compile-time [1], while not causing any binary changes (due to always
dividing by 1) in the large test-set I checked.

Division by GCD could be added in the future again and it in theory
should help reduce overflows by normalizing the coefficients (sketched
in cadbfdf8605e743e092217c54e2b837245a0a330), but this also doesn't seem
to have much (any) impact in practice.

[1] https://llvm-compile-time-tracker.com/compare.php?from=0de030e4dcb798228731ab25d4dd31df4dcaba2b&to=cadbfdf8605e743e092217c54e2b837245a0a330&stat=instructions:u

show more ...

[ConstraintElim] Fix integer overflow in ConstraintSystem::negate.

This fixes another integer overflow that was exposed by a variant of the
test case from #62226.

[ConstraintSystem] Use sparse representation for constraints. (NFC)

Update ConstraintSystem to use a sparse representation for entries in a
row. Most rows only contain a small number of variables, s

[ConstraintSystem] Use sparse representation for constraints. (NFC)

Update ConstraintSystem to use a sparse representation for entries in a
row. Most rows only contain a small number of variables, so the sparse
representation can result in significant speedups.

For a large test case from D135915, it halves the time spent in
ConstraintElimination.

To ensure this returns the same results as the old implementation in all
cases, I built a large set of projects with an extra assertion that it
produces the same result as the old implementation.

show more ...

[ConstriantElimination] Add NODEBUG condition around `dump`

Recommit "[ConstraintElimination] Change debug output to display variable names."

This reverts commit 02ae7e72b3f00969eeb579a2b4346082827f0b35.

include Value.h in ConstraintSystem.h

Revert "Recommit "[ConstraintElimination] Change debug output to display variable names.""

This reverts commit 2a2a6bfcfe8e62886542cb673ac8df349cf26499.

This causes build failures:

/home/npopo

Revert "Recommit "[ConstraintElimination] Change debug output to display variable names.""

This reverts commit 2a2a6bfcfe8e62886542cb673ac8df349cf26499.

This causes build failures:

/home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp: In member function ‘llvm::SmallVector<std::__cxx11::basic_string<char> > llvm::ConstraintSystem::getVarNamesList() const’:
/home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp:118:10: error: invalid use of incomplete type ‘class llvm::Value’
118 | if (V->getName().empty())
| ^~
In file included from /home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp:9:
/home/npopov/repos/llvm-project/llvm/include/llvm/Analysis/ConstraintSystem.h:21:7: note: forward declaration of ‘class llvm::Value’
21 | class Value;
| ^~~~~
/home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp:119:22: error: invalid use of incomplete type ‘class llvm::Value’
119 | OperandName = V->getNameOrAsOperand();
| ^~
/home/npopov/repos/llvm-project/llvm/include/llvm/Analysis/ConstraintSystem.h:21:7: note: forward declaration of ‘class llvm::Value’
21 | class Value;
| ^~~~~
/home/npopov/repos/llvm-project/llvm/lib/Analysis/ConstraintSystem.cpp:121:41: error: invalid use of incomplete type ‘class llvm::Value’
121 | OperandName = std::string("%") + V->getName().str();
| ^~
/home/npopov/repos/llvm-project/llvm/include/llvm/Analysis/ConstraintSystem.h:21:7: note: forward declaration of ‘class llvm::Value’
21 | class Value;
| ^~~~~

show more ...

Recommit "[ConstraintElimination] Change debug output to display variable names."

This reverts commit 62d0e1a8541f93dfbf66d982f66da32676df2df7.

remove `dumpWithNames` function

Revert "[ConstraintElimination] Change debug output to display variable names."

This reverts commit 869c87ad10e87db7c032c3464338ab9d50916510.

`dumpWithNames` function should be removed

[ConstraintElimination] Change debug output to display variable names.

Previously when constraint system outputs the rows in the system the variables used are x1,2...n making it hard to infer which

[ConstraintElimination] Change debug output to display variable names.

Previously when constraint system outputs the rows in the system the variables used are x1,2...n making it hard to infer which ones they relate to in the IR

Reviewed By: fhahn

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

show more ...

[ConstraintElim] Update existing constraint system in place (NFC).

This patch breaks up the solving step into 2 phases:

1. Collect all rows where the variable to eliminate is != 0 and remove
it

[ConstraintElim] Update existing constraint system in place (NFC).

This patch breaks up the solving step into 2 phases:

1. Collect all rows where the variable to eliminate is != 0 and remove
it from the original system.
2. Process all collect rows to build new set of constraints, add them to
the original system.

This is much more efficient for excessive cases, as this avoids a large
number of moves to the new system. This reduces the time spent in
ConstraintElimination for the test case shared in D135915 from ~3s to
0.6s.

show more ...

[ConstraintElim] Move some array accesses to variables (NFC).

Move some accesses that are use multiple times to variables. This also
will make updating them easier in the future.

[ConstraintSystem] Remove last variable, use move instead of copy. (NFC)

At the moment, a large amount of time is spent construction vectors
by pushing back all elements except the first variable. F

[ConstraintSystem] Remove last variable, use move instead of copy. (NFC)

At the moment, a large amount of time is spent construction vectors
by pushing back all elements except the first variable. For large
inputs, such as discussed in https://reviews.llvm.org/D135915#4057050
this can result in excessive compile-time.

Instead, it is more efficient to remove the last variable. Then the
original vector can be re-used by simply popping the last element and
then moving the contents to the new system.

This improves time spent in ConstraintElimination for the linked
reproducer from ~43s to ~3s.

show more ...

Move from llvm::makeArrayRef to ArrayRef deduction guides - llvm/ part

Use deduction guides instead of helper functions.

The only non-automatic changes have been:

1. ArrayRef(some_uint8_pointer, 0

Move from llvm::makeArrayRef to ArrayRef deduction guides - llvm/ part

Use deduction guides instead of helper functions.

The only non-automatic changes have been:

1. ArrayRef(some_uint8_pointer, 0) needs to be changed into ArrayRef(some_uint8_pointer, (size_t)0) to avoid an ambiguous call with ArrayRef((uint8_t*), (uint8_t*))
2. CVSymbol sym(makeArrayRef(symStorage)); needed to be rewritten as CVSymbol sym{ArrayRef(symStorage)}; otherwise the compiler is confused and thinks we have a (bad) function prototype. There was a few similar situation across the codebase.
3. ADL doesn't seem to work the same for deduction-guides and functions, so at some point the llvm namespace must be explicitly stated.
4. The "reference mode" of makeArrayRef(ArrayRef<T> &) that acts as no-op is not supported (a constructor cannot achieve that).

Per reviewers' comment, some useless makeArrayRef have been removed in the process.

This is a follow-up to https://reviews.llvm.org/D140896 that introduced
the deduction guides.

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

show more ...

[Analysis] Qualify auto variables in for loops (NFC)

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Diff

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120659

show more ...

[ConstraintSystem] Mark function as const (NFC).

[llvm] Remove redundant string initialization (NFC)

Identified with readability-redundant-string-init.

[ConstraintElimination] Bail out if system gets too big.

For some inputs, the constraint system can grow quite large during
solving, because it replaces complex constraints with one or more
simpler

[ConstraintElimination] Bail out if system gets too big.

For some inputs, the constraint system can grow quite large during
solving, because it replaces complex constraints with one or more
simpler constraints. This adds a cut-off to avoid compile-time explosion
on problematic inputs.

show more ...

[ConstraintElimination] Wrap dump() call in LLVM_DEBUG (NFC).

ConstraintSystem::dump only generates output with -debug, but there's no
need to call it without -debug.

[ConstraintElimination] Handle constraints with all zero var coeffs.

Constraints where all variable coefficients are 0 do not add any useful
information. When checking, we can check if they are alwa

[ConstraintElimination] Handle constraints with all zero var coeffs.

Constraints where all variable coefficients are 0 do not add any useful
information. When checking, we can check if they are always true/false.

show more ...

[ConstraintSystem] Remove local variable that is set but not read [NFC]

gcc 7.4 warns about it.

[ConstraintSolver] Add isConditionImplied helper.

This patch adds a isConditionImplied function that
takes a constraint and returns true if the constraint
is implied by the current constraints in th

[ConstraintSolver] Add isConditionImplied helper.

This patch adds a isConditionImplied function that
takes a constraint and returns true if the constraint
is implied by the current constraints in the system.

Reviewed By: spatel

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

show more ...