| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Removing statefullness also adds the benefit of short circuiting.
|
|
DenseSet (#157685)
The `inAssignment` variable is actually used as a set; let's declare it as a set.
|
|
|
|
This API was never used in the clang code base.
There might be downstream users, but I highly doubt that. I think the
best is to get rid of this unused API.
|
|
(#157657)
This is just more conventional.
|
|
This was likely accidentally omitted when `liveBindings` was introduced.
I don't think in practice it matters.
|
|
|
|
These are identified by misc-include-cleaner. I've filtered out those
that break builds. Also, I'm staying away from llvm-config.h,
config.h, and Compiler.h, which likely cause platform- or
compiler-specific build failures.
|
|
attempt) (#127406)
In my previous attempt (#126913) of fixing the flaky case was on a good
track when I used the begin locations as a stable ordering. However, I
forgot to consider the case when the begin locations are the same among
the Exprs.
In an `EXPENSIVE_CHECKS` build, arrays are randomly shuffled prior to
sorting them. This exposed the flaky behavior much more often basically
breaking the "stability" of the vector - as it should.
Because of this, I had to revert the previous fix attempt in #127034.
To fix this, I use this time `Expr::getID` for a stable ID for an Expr.
Hopefully fixes #126619
Hopefully fixes #126804
|
|
Multiple people reported flaky bot failures tied to
`clang/test/Analysis/live-stmts.cpp` I tried reproducing the flaky
behavior on my Linux x86_64 system, but the tests appears to be stable
in my context.
Only by looking at the failures reported, I could formulate a potential
diagnosis.
The output always looked almost the same, except that the Exprs dumped
per Basic block were shuffled compared to my expectation. This suggests
to me some ordering issue.
If you look at the backing storage of
`blocksEndToLiveness[B].liveExprs`,
it uses `llvm::ImmutableSet<const Expr *>`.
That container likely uses the pointer values as keys, thus the runtime
values of the addresses influence the iteration order.
To fix this, before dumping, I sort the expressions by their
"beginLocs". It should be efficient enough for a debug checker, where
there is no performance constraint.
This should hopefully fix the flaky behavior on systems where ASLR works
differently than (my) Linux system.
Hopefully fixes #126619
Hopefully fixes #126804
|
|
conditional (#100745)
Fix the false negative caused by state merging in the evaluation of a
short-circuiting expression inside the condition of a ternary operator.
The fixed symptom is that CSA always evaluates `(x || x) ? n : m` to
`m`.
This change forces the analyzer to consider all logical expressions
prone to short-circuiting alive until the entire conditional expression
is evaluated. Here is why.
By default, LiveVariables analysis marks only direct subexpressions as
live relative to any expression. So for `a ? b : c` it will consider
`a`, `b`, and `c` alive when evaluating the ternary operator expression.
To explore both possibilities opened by a ternary operator, it is
important to keep something different about the exploded nodes created
after the evaluation of its branches. These two nodes come to the same
location, so they must have different states. Otherwise, they will be
considered identical and can engender only one outcome.
`ExprEngine::visitGuardedExpr` chooses the first predecessor exploded
node to carry the value of the conditional expression. It works well in
the case of a simple condition, because when `a ? b : c` is evaluated,
`a` is kept alive, so the two branches differ in the value of `a`.
However, before this patch is applied, this strategy breaks for `(x ||
x) ? n : m`. `x` is not a direct child of the ternary expression. Due to
short-circuiting, once `x` is assumed to be `true`, evaluation jumps
directly to `n` and then to the result of the entire ternary expression.
Given that the result of the entire condition `(x || x)` is not
constructed, and `x` is not kept alive, the difference between the path
coming through `n` and through `m` disappears. As a result, exploded
nodes coming from the "true expression" and the "false expression"
engender identical successors and merge the execution paths.
|
|
This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".
This is part of an effort to migrate from llvm::Optional to
std::optional:
https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
|
|
This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.
I'll post a separate patch to actually replace llvm::Optional with
std::optional.
This is part of an effort to migrate from llvm::Optional to
std::optional:
https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
|
|
Introducing support for creating structured binding
to tuple-like types.
Differential Revision: https://reviews.llvm.org/D128837
|
|
appear in an assignment
Suppose you stumble across a DeclRefExpr in the AST, that references a VarDecl.
How would you know that that variable is written in the containing statement, or
not? One trick would be to ascend the AST through Stmt::getParent, and see
whether the variable appears on the left hand side of the assignment.
Liveness does something similar, but instead of ascending the AST, it descends
into it with a StmtVisitor, and after finding an assignment, it notes that the
LHS appears in the context of an assignemnt. However, as [1] demonstrates, the
analysis isn't ran on the AST of an entire function, but rather on CFG, where
the order of the statements, visited in order, would make it impossible to know
this information by descending.
void f() {
int i;
i = 5;
}
`-FunctionDecl 0x55a6e1b070b8 <test.cpp:1:1, line:5:1> line:1:6 f 'void ()'
`-CompoundStmt 0x55a6e1b07298 <col:10, line:5:1>
|-DeclStmt 0x55a6e1b07220 <line:2:3, col:8>
| `-VarDecl 0x55a6e1b071b8 <col:3, col:7> col:7 used i 'int'
`-BinaryOperator 0x55a6e1b07278 <line:4:3, col:7> 'int' lvalue '='
|-DeclRefExpr 0x55a6e1b07238 <col:3> 'int' lvalue Var 0x55a6e1b071b8 'i' 'int'
`-IntegerLiteral 0x55a6e1b07258 <col:7> 'int' 5
void f()
[B2 (ENTRY)]
Succs (1): B1
[B1]
1: int i;
2: 5
3: i
4: [B1.3] = [B1.2]
Preds (1): B2
Succs (1): B0
[B0 (EXIT)]
Preds (1): B1
You can see that the arguments (rightfully so, they need to be evaluated first)
precede the assignment operator. For this reason, Liveness implemented a pass to
scan the CFG and note which variables appear in an assignment.
BUT.
This problem only exists if we traverse a CFGBlock in order. And Liveness in
fact does it reverse order. So a distinct pass is indeed unnecessary, we can
note the appearance of the assignment by the time we reach the variable.
[1] http://lists.llvm.org/pipermail/cfe-dev/2020-July/066330.html
Differential Revision: https://reviews.llvm.org/D87518
|
|
thing doesn't exist
The summary and very short discussion in D82122 summarizes whats happening here.
In short, liveness talks about variables, or expressions, anything that
has a value. Well, statements just simply don't have a one.
Differential Revision: https://reviews.llvm.org/D82598
|
|
management
|
|
Right now every dataflow algorithm uses its own worklist implementation.
This is a first step to reduce this duplication. Some upcoming
algorithms such as the lifetime analysis is going to use the factored
out implementations.
Differential Revision: https://reviews.llvm.org/D72380
|
|
Turn it into a variant class instead. This conversion does indeed save some code
but there's a plan to add support for more kinds of terminators that aren't
necessarily based on statements, and with those in mind it becomes more and more
confusing to have CFGTerminators implicitly convertible to a Stmt *.
Differential Revision: https://reviews.llvm.org/D61814
llvm-svn: 361586
|
|
to reflect the new license.
We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.
Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.
llvm-svn: 351636
|
|
StaticAnalyzer uses the CFG-based RelaxedLiveVariables analysis in order to,
in particular, figure out values of which expressions are still needed.
When the expression becomes "dead", it is garbage-collected during
the dead binding scan.
Expressions that constitute branches/bodies of control flow statements,
eg. `E1' in `if (C1) E1;' but not `E2' in `if (C2) { E2; }', were kept alive
for too long. This caused false positives in MoveChecker because it relies
on cleaning up loop-local variables when they go out of scope, but some of those
live-for-too-long expressions were keeping a reference to those variables.
Fix liveness analysis to correctly mark these expressions as dead.
Add a debug checker, debug.DumpLiveStmts, in order to test expressions liveness.
Differential Revision: https://reviews.llvm.org/D55566
llvm-svn: 349320
|
|
A ConstantExpr class represents a full expression that's in a context where a
constant expression is required. This class reflects the path the evaluator
took to reach the expression rather than the syntactic context in which the
expression occurs.
In the future, the class will be expanded to cache the result of the evaluated
expression so that it's not needlessly re-evaluated
Reviewed By: rsmith
Differential Revision: https://reviews.llvm.org/D53475
llvm-svn: 345692
|
|
Summary: The convenience wrapper in STLExtras is available since rL342102.
Reviewers: rsmith, #clang, dblaikie
Reviewed By: rsmith, #clang
Subscribers: mgrang, arphaman, kadircet, cfe-commits
Differential Revision: https://reviews.llvm.org/D52576
llvm-svn: 343147
|
|
Summary:
Migrate callers to print().
dump() should be useful to downstreams and third parties as a debugging
aid. Everyone trips up on this and creates confusing output.
Subscribers: cfe-commits
Differential Revision: https://reviews.llvm.org/D50661
llvm-svn: 339810
|
|
Reviewers: teemperor!
Subscribers: jholewinski, whisperity, jfb, cfe-commits
Differential Revision: https://reviews.llvm.org/D50350
llvm-svn: 339385
|
|
sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h}
llvm-svn: 338291
|
|
This reverts commit 2fa3e3edc4ed6547cc4ce46a8c79d1891a5b3b36.
Removed the wrong variable.
llvm-svn: 329445
|
|
llvm-svn: 329444
|
|
llvm-svn: 328968
|
|
C++ structured bindings for non-tuple-types are defined in a peculiar
way, where the resulting declaration is not a VarDecl, but a
BindingDecl.
That means a lot of existing machinery stops working.
rdar://36912381
Differential Revision: https://reviews.llvm.org/D44956
llvm-svn: 328910
|
|
r327219 added wrappers to std::sort which randomly shuffle the container before
sorting. This will help in uncovering non-determinism caused due to undefined
sorting order of objects having the same key.
To make use of that infrastructure we need to invoke llvm::sort instead of
std::sort.
llvm-svn: 328636
|
|
The implementation is in AnalysisDeclContext.cpp and the class is called
AnalysisDeclContext.
Making those match up has numerous benefits, including:
- Easier jump from header to/from implementation.
- Easily identify filename from class.
Differential Revision: https://reviews.llvm.org/D37500
llvm-svn: 312671
|
|
The class DataflowWorklist internally maintains a sorted list of pointers to CFGBlock
and the method enqueuePredecessors has to call sortWorklist to maintain the invariant.
The implementation based on vector + sort works well for small sizes
but gets infeasible for relatively large sizes. In particular the issue takes place
for some cryptographic libraries which use code generation.
The diff replaces vector + sort with priority queue.
For one of the implementations of AES this patch reduces
the time for analysis from 204 seconds to 8 seconds.
Test plan: make -j8 check-clang
Differential revision: https://reviews.llvm.org/D25503
llvm-svn: 284166
|
|
No functionality change intended.
llvm-svn: 241355
|
|
llvm-svn: 240353
|
|
The patch is generated using this command:
$ tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \
-checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \
work/llvm/tools/clang
To reduce churn, not touching namespaces spanning less than 10 lines.
llvm-svn: 240270
|
|
Convert uses of those APIs into ranged for loops. NFC.
llvm-svn: 228404
|
|
llvm-svn: 220264
|
|
llvm-svn: 218296
|
|
to recover the performance after r214064.
Also sorts out the naming for PostOrderCFGView, ReversePostOrderCFGView,
BackwardDataflowWorklist and ForwardDataflowWorklist, to match the accepted
terminology.
Also unifies BackwardDataflowWorklist and ForwardDataflowWorklist to share
the "worklist for prioritization, post-order traversal for fallback" logic,
and to avoid repetitive sorting.
Also cleans up comments in the affected area.
llvm-svn: 215650
|
|
llvm-svn: 214064
|
|
llvm-svn: 209191
|
|
found with a smarter version of -Wunused-member-function that I'm playwing with.
Appologies in advance if I removed someone's WIP code.
ARCMigrate/TransProperties.cpp | 8 -----
AST/MicrosoftMangle.cpp | 1
Analysis/AnalysisDeclContext.cpp | 5 ---
Analysis/LiveVariables.cpp | 14 ----------
Index/USRGeneration.cpp | 10 -------
Sema/Sema.cpp | 33 +++++++++++++++++++++---
Sema/SemaChecking.cpp | 3 --
Sema/SemaDecl.cpp | 20 ++------------
StaticAnalyzer/Checkers/GenericTaintChecker.cpp | 1
9 files changed, 34 insertions(+), 61 deletions(-)
llvm-svn: 204561
|
|
iterator_range decls(). Updating all of the usages of the iterators with range-based for loops.
llvm-svn: 203947
|
|
No functionality change.
llvm-svn: 203289
|
|
llvm-svn: 202639
|
|
This reverts commit r189090.
The original patch introduced regressions (see the added live-variables.* tests). The patch depends on the correctness of live variable analyses, which are not computed correctly. I've opened PR18159 to track the proper resolution to this problem.
The patch was a stepping block to r189746. This is why part of the patch reverts temporary destructor tests that started crashing. The temporary destructors feature is disabled by default.
llvm-svn: 196593
|
|
No functionality change intended.
llvm-svn: 189112
|
|
Summary:
Instead of digging through the ExplodedGraph, to figure out which edge brought
us here, I compute the value of conditional expression by looking at the
sub-expression values.
To do this, I needed to change the liveness algorithm a bit -- now, the full
conditional expression also depends on all atomic sub-expressions, not only the
outermost ones.
Reviewers: jordan_rose
CC: cfe-commits
Differential Revision: http://llvm-reviews.chandlerc.com/D1340
llvm-svn: 189090
|
|
Use Optional<CFG*> where invalid states were needed previously. In the one case
where that's not possible (beginAutomaticObjDtorsInsert) just use a dummy
CFGAutomaticObjDtor.
Thanks for the help from Jordan Rose & discussion/feedback from Ted Kremenek
and Doug Gregor.
Post commit code review feedback on r175796 by Ted Kremenek.
llvm-svn: 175938
|
