[analyzer] Keep alive short-circuiting condition subexpressions in a conditional (#100745)

Fix the false negative caused by state merging in the evaluation of a
short-circuiting expression inside t

[analyzer] Keep alive short-circuiting condition subexpressions in a 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.

show more ...

[clang] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is p

[clang] Use std::optional instead of llvm::Optional (NFC)

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

show more ...

[clang] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Option

[clang] Add #include <optional> (NFC)

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

show more ...

[analyzer] Structured binding to tuple-like types

Introducing support for creating structured binding
to tuple-like types.

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

[analyzer][Liveness][NFC] Remove an unneeded pass to collect variables that appear in an assignment

Suppose you stumble across a DeclRefExpr in the AST, that references a VarDecl.
How would you know

[analyzer][Liveness][NFC] Remove an unneeded pass to collect variables that 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

show more ...

[analyzer][Liveness][NFC] Get rid of statement liveness, because such a thing doesn't exist

The summary and very short discussion in D82122 summarizes whats happening here.

In short, liveness talks

[analyzer][Liveness][NFC] Get rid of statement liveness, because such a 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

show more ...

AnalysisDeclContext::ManagedAnalyses: Use unique_ptr to simplify memory management

[DataFlow] Factor two worklist implementations out

Right now every dataflow algorithm uses its own worklist implementation.
This is a first step to reduce this duplication. Some upcoming
algorithms

[DataFlow] Factor two worklist implementations out

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

show more ...

[CFG] NFC: Remove implicit conversion from CFGTerminator to Stmt *.

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

[CFG] NFC: Remove implicit conversion from CFGTerminator to Stmt *.

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

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
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

show more ...

[analyzer] Fix some expressions staying live too long. Add a debug checker.

StaticAnalyzer uses the CFG-based RelaxedLiveVariables analysis in order to,
in particular, figure out values of which exp

[analyzer] Fix some expressions staying live too long. Add a debug checker.

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

show more ...

Create ConstantExpr class

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

Create ConstantExpr class

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

show more ...

llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)

Summary: The convenience wrapper in STLExtras is available since rL342102.

Reviewers: rsmith, #clang, dblaikie

Reviewed By: rsmith, #clang

llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)

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

show more ...

Add a newline to SourceLocation dump output

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

Add a newline to SourceLocation dump output

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

show more ...

Port getLocStart -> getBeginLoc

Reviewers: teemperor!

Subscribers: jholewinski, whisperity, jfb, cfe-commits

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

llvm-svn: 339385

Remove trailing space

sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h}

llvm-svn: 338291

Revert "[analyzer] Remove an unused variable"

This reverts commit 2fa3e3edc4ed6547cc4ce46a8c79d1891a5b3b36.

Removed the wrong variable.

llvm-svn: 329445

[analyzer] Remove an unused variable

llvm-svn: 329444

Fix unused variable warning introduced at revision 328910.

llvm-svn: 328968

[analyzer] Fix liveness calculation for C++17 structured bindings

C++ structured bindings for non-tuple-types are defined in a peculiar
way, where the resulting declaration is not a VarDecl, but a
B

[analyzer] Fix liveness calculation for C++17 structured bindings

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

show more ...

[clang] Change std::sort to llvm::sort in response to r327219

r327219 added wrappers to std::sort which randomly shuffle the container before
sorting. This will help in uncovering non-determinism c

[clang] Change std::sort to llvm::sort in response to r327219

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

show more ...

[CSA] [NFC] Move AnalysisContext.h to AnalysisDeclContext.h

The implementation is in AnalysisDeclContext.cpp and the class is called
AnalysisDeclContext.

Making those match up has numerous benefits

[CSA] [NFC] Move AnalysisContext.h to AnalysisDeclContext.h

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

show more ...

[analyzer] Remove superquadratic behaviour from DataflowWorklist

The class DataflowWorklist internally maintains a sorted list of pointers to CFGBlock
and the method enqueuePredecessors has to call

[analyzer] Remove superquadratic behaviour from DataflowWorklist

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

show more ...

Rewrite users of Stmt::child_begin/end into for-range loops.

No functionality change intended.

llvm-svn: 241355

Revert r240270 ("Fixed/added namespace ending comments using clang-tidy").

llvm-svn: 240353