| Age | Commit message (Collapse) | Author |
|---|
|
Remove left over redundant parentheses after 9b6127d7 as pointed out by
@nikic.
|
|
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
|
|
This fixes another integer overflow that was exposed by a variant of the
test case from #62226.
|
|
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.
|
|
|
|
names."
This reverts commit 02ae7e72b3f00969eeb579a2b4346082827f0b35.
include Value.h in ConstraintSystem.h
|
|
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;
| ^~~~~
|
|
names."
This reverts commit 62d0e1a8541f93dfbf66d982f66da32676df2df7.
remove `dumpWithNames` function
|
|
This reverts commit 869c87ad10e87db7c032c3464338ab9d50916510.
`dumpWithNames` function should be removed
|
|
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
|
|
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.
|
|
Move some accesses that are use multiple times to variables. This also
will make updating them easier in the future.
|
|
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.
|
|
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
|
|
|
|
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
|
|
|
|
Identified with readability-redundant-string-init.
|
|
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.
|
|
ConstraintSystem::dump only generates output with -debug, but there's no
need to call it without -debug.
|
|
Constraints where all variable coefficients are 0 do not add any useful
information. When checking, we can check if they are always true/false.
|
|
gcc 7.4 warns about it.
|
|
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
|
|
This patch recommits "[ConstraintSystem] Add helpers to deal with linear constraints."
(it reverts the revert commit 8da6ae4ce1b686c5c13698e4c5ee937811fda6f7).
The reason for the revert was using __builtin_multiply_overflow, which
is not available for all compilers. The patch has been updated to use
MulOverflow from MathExtras.h
|
|
This reverts commit 3eb141e5078a0ce9d92eadc721bc49d214d23056.
This uses __builtin_mul_overflow which is not available everywhere.
|
|
This patch introduces a new ConstraintSystem class, that maintains a set
of linear constraints and uses Fourier–Motzkin elimination to eliminate
constraints to check if there are solutions for the system.
It also adds a convert-constraint-log-to-z3.py script, which can parse
the debug output of the constraint system and convert it to a python
script that feeds the constraints into Z3 and checks if it produces the
same result as the LLVM implementation. This is for verification
purposes.
Reviewed By: spatel
Differential Revision: https://reviews.llvm.org/D84544
|
