Skip to content

Commit dd53bdb

Browse files
SzelethusSzelethus
committedAug 14, 2019
[analyzer][CFG] Don't track the condition of asserts
Well, what is says on the tin I guess! Some more changes: * Move isInevitablySinking() from BugReporter.cpp to CFGBlock's interface * Rename and move findBlockForNode() from BugReporter.cpp to ExplodedNode::getCFGBlock() Differential Revision: https://reviews.llvm.org/D65287 llvm-svn: 368836
1 parent 90c2794 commit dd53bdb

File tree

6 files changed

+365
-100
lines changed

6 files changed

+365
-100
lines changed
 

Diff for: ‎clang/include/clang/Analysis/CFG.h

+4
Original file line numberDiff line numberDiff line change
@@ -855,6 +855,10 @@ class CFGBlock {
855855
void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
856856
void setHasNoReturnElement() { HasNoReturnElement = true; }
857857

858+
/// Returns true if the block would eventually end with a sink (a noreturn
859+
/// node).
860+
bool isInevitablySinking() const;
861+
858862
CFGTerminator getTerminator() const { return Terminator; }
859863

860864
Stmt *getTerminatorStmt() { return Terminator.getStmt(); }

Diff for: ‎clang/lib/Analysis/CFG.cpp

+65
Original file line numberDiff line numberDiff line change
@@ -5652,6 +5652,71 @@ void CFGBlock::printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
56525652
Out << JsonFormat(TempOut.str(), AddQuotes);
56535653
}
56545654

5655+
// Returns true if by simply looking at the block, we can be sure that it
5656+
// results in a sink during analysis. This is useful to know when the analysis
5657+
// was interrupted, and we try to figure out if it would sink eventually.
5658+
// There may be many more reasons why a sink would appear during analysis
5659+
// (eg. checkers may generate sinks arbitrarily), but here we only consider
5660+
// sinks that would be obvious by looking at the CFG.
5661+
static bool isImmediateSinkBlock(const CFGBlock *Blk) {
5662+
if (Blk->hasNoReturnElement())
5663+
return true;
5664+
5665+
// FIXME: Throw-expressions are currently generating sinks during analysis:
5666+
// they're not supported yet, and also often used for actually terminating
5667+
// the program. So we should treat them as sinks in this analysis as well,
5668+
// at least for now, but once we have better support for exceptions,
5669+
// we'd need to carefully handle the case when the throw is being
5670+
// immediately caught.
5671+
if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) {
5672+
if (Optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>())
5673+
if (isa<CXXThrowExpr>(StmtElm->getStmt()))
5674+
return true;
5675+
return false;
5676+
}))
5677+
return true;
5678+
5679+
return false;
5680+
}
5681+
5682+
bool CFGBlock::isInevitablySinking() const {
5683+
const CFG &Cfg = *getParent();
5684+
5685+
const CFGBlock *StartBlk = this;
5686+
if (isImmediateSinkBlock(StartBlk))
5687+
return true;
5688+
5689+
llvm::SmallVector<const CFGBlock *, 32> DFSWorkList;
5690+
llvm::SmallPtrSet<const CFGBlock *, 32> Visited;
5691+
5692+
DFSWorkList.push_back(StartBlk);
5693+
while (!DFSWorkList.empty()) {
5694+
const CFGBlock *Blk = DFSWorkList.back();
5695+
DFSWorkList.pop_back();
5696+
Visited.insert(Blk);
5697+
5698+
// If at least one path reaches the CFG exit, it means that control is
5699+
// returned to the caller. For now, say that we are not sure what
5700+
// happens next. If necessary, this can be improved to analyze
5701+
// the parent StackFrameContext's call site in a similar manner.
5702+
if (Blk == &Cfg.getExit())
5703+
return false;
5704+
5705+
for (const auto &Succ : Blk->succs()) {
5706+
if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) {
5707+
if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) {
5708+
// If the block has reachable child blocks that aren't no-return,
5709+
// add them to the worklist.
5710+
DFSWorkList.push_back(SuccBlk);
5711+
}
5712+
}
5713+
}
5714+
}
5715+
5716+
// Nothing reached the exit. It can only mean one thing: there's no return.
5717+
return true;
5718+
}
5719+
56555720
const Expr *CFGBlock::getLastCondition() const {
56565721
// If the terminator is a temporary dtor or a virtual base, etc, we can't
56575722
// retrieve a meaningful condition, bail out.

Diff for: ‎clang/lib/StaticAnalyzer/Core/BugReporter.cpp

+3-86
Original file line numberDiff line numberDiff line change
@@ -2716,90 +2716,6 @@ struct FRIEC_WLItem {
27162716

27172717
} // namespace
27182718

2719-
static const CFGBlock *findBlockForNode(const ExplodedNode *N) {
2720-
ProgramPoint P = N->getLocation();
2721-
if (auto BEP = P.getAs<BlockEntrance>())
2722-
return BEP->getBlock();
2723-
2724-
// Find the node's current statement in the CFG.
2725-
if (const Stmt *S = PathDiagnosticLocation::getStmt(N))
2726-
return N->getLocationContext()->getAnalysisDeclContext()
2727-
->getCFGStmtMap()->getBlock(S);
2728-
2729-
return nullptr;
2730-
}
2731-
2732-
// Returns true if by simply looking at the block, we can be sure that it
2733-
// results in a sink during analysis. This is useful to know when the analysis
2734-
// was interrupted, and we try to figure out if it would sink eventually.
2735-
// There may be many more reasons why a sink would appear during analysis
2736-
// (eg. checkers may generate sinks arbitrarily), but here we only consider
2737-
// sinks that would be obvious by looking at the CFG.
2738-
static bool isImmediateSinkBlock(const CFGBlock *Blk) {
2739-
if (Blk->hasNoReturnElement())
2740-
return true;
2741-
2742-
// FIXME: Throw-expressions are currently generating sinks during analysis:
2743-
// they're not supported yet, and also often used for actually terminating
2744-
// the program. So we should treat them as sinks in this analysis as well,
2745-
// at least for now, but once we have better support for exceptions,
2746-
// we'd need to carefully handle the case when the throw is being
2747-
// immediately caught.
2748-
if (std::any_of(Blk->begin(), Blk->end(), [](const CFGElement &Elm) {
2749-
if (Optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>())
2750-
if (isa<CXXThrowExpr>(StmtElm->getStmt()))
2751-
return true;
2752-
return false;
2753-
}))
2754-
return true;
2755-
2756-
return false;
2757-
}
2758-
2759-
// Returns true if by looking at the CFG surrounding the node's program
2760-
// point, we can be sure that any analysis starting from this point would
2761-
// eventually end with a sink. We scan the child CFG blocks in a depth-first
2762-
// manner and see if all paths eventually end up in an immediate sink block.
2763-
static bool isInevitablySinking(const ExplodedNode *N) {
2764-
const CFG &Cfg = N->getCFG();
2765-
2766-
const CFGBlock *StartBlk = findBlockForNode(N);
2767-
if (!StartBlk)
2768-
return false;
2769-
if (isImmediateSinkBlock(StartBlk))
2770-
return true;
2771-
2772-
llvm::SmallVector<const CFGBlock *, 32> DFSWorkList;
2773-
llvm::SmallPtrSet<const CFGBlock *, 32> Visited;
2774-
2775-
DFSWorkList.push_back(StartBlk);
2776-
while (!DFSWorkList.empty()) {
2777-
const CFGBlock *Blk = DFSWorkList.back();
2778-
DFSWorkList.pop_back();
2779-
Visited.insert(Blk);
2780-
2781-
// If at least one path reaches the CFG exit, it means that control is
2782-
// returned to the caller. For now, say that we are not sure what
2783-
// happens next. If necessary, this can be improved to analyze
2784-
// the parent StackFrameContext's call site in a similar manner.
2785-
if (Blk == &Cfg.getExit())
2786-
return false;
2787-
2788-
for (const auto &Succ : Blk->succs()) {
2789-
if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) {
2790-
if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) {
2791-
// If the block has reachable child blocks that aren't no-return,
2792-
// add them to the worklist.
2793-
DFSWorkList.push_back(SuccBlk);
2794-
}
2795-
}
2796-
}
2797-
}
2798-
2799-
// Nothing reached the exit. It can only mean one thing: there's no return.
2800-
return true;
2801-
}
2802-
28032719
static BugReport *
28042720
FindReportInEquivalenceClass(BugReportEquivClass& EQ,
28052721
SmallVectorImpl<BugReport*> &bugReports) {
@@ -2851,8 +2767,9 @@ FindReportInEquivalenceClass(BugReportEquivClass& EQ,
28512767
// to being post-dominated by a sink. This works better when the analysis
28522768
// is incomplete and we have never reached the no-return function call(s)
28532769
// that we'd inevitably bump into on this path.
2854-
if (isInevitablySinking(errorNode))
2855-
continue;
2770+
if (const CFGBlock *ErrorB = errorNode->getCFGBlock())
2771+
if (ErrorB->isInevitablySinking())
2772+
continue;
28562773

28572774
// At this point we know that 'N' is not a sink and it has at least one
28582775
// successor. Use a DFS worklist to find a non-sink end-of-path node.

Diff for: ‎clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

+38-14
Original file line numberDiff line numberDiff line change
@@ -1710,18 +1710,6 @@ class TrackControlDependencyCondBRVisitor final : public BugReporterVisitor {
17101710
};
17111711
} // end of anonymous namespace
17121712

1713-
static CFGBlock *GetRelevantBlock(const ExplodedNode *Node) {
1714-
if (auto SP = Node->getLocationAs<StmtPoint>()) {
1715-
const Stmt *S = SP->getStmt();
1716-
assert(S);
1717-
1718-
return const_cast<CFGBlock *>(Node->getLocationContext()
1719-
->getAnalysisDeclContext()->getCFGStmtMap()->getBlock(S));
1720-
}
1721-
1722-
return nullptr;
1723-
}
1724-
17251713
static std::shared_ptr<PathDiagnosticEventPiece>
17261714
constructDebugPieceForTrackedCondition(const Expr *Cond,
17271715
const ExplodedNode *N,
@@ -1742,24 +1730,60 @@ constructDebugPieceForTrackedCondition(const Expr *Cond,
17421730
(Twine() + "Tracking condition '" + ConditionText + "'").str());
17431731
}
17441732

1733+
static bool isAssertlikeBlock(const CFGBlock *B, ASTContext &Context) {
1734+
if (B->succ_size() != 2)
1735+
return false;
1736+
1737+
const CFGBlock *Then = B->succ_begin()->getReachableBlock();
1738+
const CFGBlock *Else = (B->succ_begin() + 1)->getReachableBlock();
1739+
1740+
if (!Then || !Else)
1741+
return false;
1742+
1743+
if (Then->isInevitablySinking() != Else->isInevitablySinking())
1744+
return true;
1745+
1746+
// For the following condition the following CFG would be built:
1747+
//
1748+
// ------------->
1749+
// / \
1750+
// [B1] -> [B2] -> [B3] -> [sink]
1751+
// assert(A && B || C); \ \
1752+
// -----------> [go on with the execution]
1753+
//
1754+
// It so happens that CFGBlock::getTerminatorCondition returns 'A' for block
1755+
// B1, 'A && B' for B2, and 'A && B || C' for B3. Let's check whether we
1756+
// reached the end of the condition!
1757+
if (const Stmt *ElseCond = Else->getTerminatorCondition())
1758+
if (isa<BinaryOperator>(ElseCond)) {
1759+
assert(cast<BinaryOperator>(ElseCond)->isLogicalOp());
1760+
return isAssertlikeBlock(Else, Context);
1761+
}
1762+
1763+
return false;
1764+
}
1765+
17451766
PathDiagnosticPieceRef TrackControlDependencyCondBRVisitor::VisitNode(
17461767
const ExplodedNode *N, BugReporterContext &BRC, BugReport &BR) {
17471768
// We can only reason about control dependencies within the same stack frame.
17481769
if (Origin->getStackFrame() != N->getStackFrame())
17491770
return nullptr;
17501771

1751-
CFGBlock *NB = GetRelevantBlock(N);
1772+
CFGBlock *NB = const_cast<CFGBlock *>(N->getCFGBlock());
17521773

17531774
// Skip if we already inspected this block.
17541775
if (!VisitedBlocks.insert(NB).second)
17551776
return nullptr;
17561777

1757-
CFGBlock *OriginB = GetRelevantBlock(Origin);
1778+
CFGBlock *OriginB = const_cast<CFGBlock *>(Origin->getCFGBlock());
17581779

17591780
// TODO: Cache CFGBlocks for each ExplodedNode.
17601781
if (!OriginB || !NB)
17611782
return nullptr;
17621783

1784+
if (isAssertlikeBlock(NB, BRC.getASTContext()))
1785+
return nullptr;
1786+
17631787
if (ControlDeps.isControlDependent(OriginB, NB)) {
17641788
if (const Expr *Condition = NB->getLastCondition()) {
17651789
// Keeping track of the already tracked conditions on a visitor level

Diff for: ‎clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

+16
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@
1616
#include "clang/AST/ExprObjC.h"
1717
#include "clang/AST/ParentMap.h"
1818
#include "clang/AST/Stmt.h"
19+
#include "clang/Analysis/CFGStmtMap.h"
1920
#include "clang/Analysis/ProgramPoint.h"
2021
#include "clang/Analysis/Support/BumpVector.h"
2122
#include "clang/Basic/LLVM.h"
@@ -292,6 +293,21 @@ bool ExplodedNode::isTrivial() const {
292293
getFirstPred()->succ_size() == 1;
293294
}
294295

296+
const CFGBlock *ExplodedNode::getCFGBlock() const {
297+
ProgramPoint P = getLocation();
298+
if (auto BEP = P.getAs<BlockEntrance>())
299+
return BEP->getBlock();
300+
301+
// Find the node's current statement in the CFG.
302+
if (const Stmt *S = PathDiagnosticLocation::getStmt(this))
303+
return getLocationContext()
304+
->getAnalysisDeclContext()
305+
->getCFGStmtMap()
306+
->getBlock(S);
307+
308+
return nullptr;
309+
}
310+
295311
ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
296312
ProgramStateRef State,
297313
bool IsSink,

Diff for: ‎clang/test/Analysis/track-control-dependency-conditions.cpp

+239
Original file line numberDiff line numberDiff line change
@@ -458,3 +458,242 @@ void f(int flag) {
458458
}
459459

460460
} // end of namespace unimportant_write_before_collapse_point
461+
462+
namespace dont_track_assertlike_conditions {
463+
464+
extern void __assert_fail(__const char *__assertion, __const char *__file,
465+
unsigned int __line, __const char *__function)
466+
__attribute__((__noreturn__));
467+
#define assert(expr) \
468+
((expr) ? (void)(0) : __assert_fail(#expr, __FILE__, __LINE__, __func__))
469+
470+
int getInt();
471+
472+
int cond1;
473+
474+
void bar() {
475+
cond1 = getInt();
476+
}
477+
478+
void f(int flag) {
479+
int *x = 0; // expected-note{{'x' initialized to a null pointer value}}
480+
481+
flag = getInt();
482+
483+
bar();
484+
assert(cond1); // expected-note{{Assuming 'cond1' is not equal to 0}}
485+
// expected-note@-1{{'?' condition is true}}
486+
487+
if (flag) // expected-note{{'flag' is not equal to 0}}
488+
// expected-note@-1{{Taking true branch}}
489+
// debug-note@-2{{Tracking condition 'flag'}}
490+
*x = 5; // expected-warning{{Dereference of null pointer}}
491+
// expected-note@-1{{Dereference of null pointer}}
492+
}
493+
494+
#undef assert
495+
} // end of namespace dont_track_assertlike_conditions
496+
497+
namespace dont_track_assertlike_and_conditions {
498+
499+
extern void __assert_fail(__const char *__assertion, __const char *__file,
500+
unsigned int __line, __const char *__function)
501+
__attribute__((__noreturn__));
502+
#define assert(expr) \
503+
((expr) ? (void)(0) : __assert_fail(#expr, __FILE__, __LINE__, __func__))
504+
505+
int getInt();
506+
507+
int cond1;
508+
int cond2;
509+
510+
void bar() {
511+
cond1 = getInt();
512+
cond2 = getInt();
513+
}
514+
515+
void f(int flag) {
516+
int *x = 0; // expected-note{{'x' initialized to a null pointer value}}
517+
518+
flag = getInt();
519+
520+
bar();
521+
assert(cond1 && cond2);
522+
// expected-note@-1{{Assuming 'cond1' is not equal to 0}}
523+
// expected-note@-2{{Assuming 'cond2' is not equal to 0}}
524+
// expected-note@-3{{'?' condition is true}}
525+
// expected-note@-4{{Left side of '&&' is true}}
526+
527+
if (flag) // expected-note{{'flag' is not equal to 0}}
528+
// expected-note@-1{{Taking true branch}}
529+
// debug-note@-2{{Tracking condition 'flag'}}
530+
*x = 5; // expected-warning{{Dereference of null pointer}}
531+
// expected-note@-1{{Dereference of null pointer}}
532+
}
533+
534+
#undef assert
535+
} // end of namespace dont_track_assertlike_and_conditions
536+
537+
namespace dont_track_assertlike_or_conditions {
538+
539+
extern void __assert_fail(__const char *__assertion, __const char *__file,
540+
unsigned int __line, __const char *__function)
541+
__attribute__((__noreturn__));
542+
#define assert(expr) \
543+
((expr) ? (void)(0) : __assert_fail(#expr, __FILE__, __LINE__, __func__))
544+
545+
int getInt();
546+
547+
int cond1;
548+
int cond2;
549+
550+
void bar() {
551+
cond1 = getInt();
552+
cond2 = getInt();
553+
}
554+
555+
void f(int flag) {
556+
int *x = 0; // expected-note{{'x' initialized to a null pointer value}}
557+
558+
flag = getInt();
559+
560+
bar();
561+
assert(cond1 || cond2);
562+
// expected-note@-1{{Assuming 'cond1' is not equal to 0}}
563+
// expected-note@-2{{Left side of '||' is true}}
564+
565+
if (flag) // expected-note{{'flag' is not equal to 0}}
566+
// expected-note@-1{{Taking true branch}}
567+
// debug-note@-2{{Tracking condition 'flag'}}
568+
*x = 5; // expected-warning{{Dereference of null pointer}}
569+
// expected-note@-1{{Dereference of null pointer}}
570+
}
571+
572+
#undef assert
573+
} // end of namespace dont_track_assertlike_or_conditions
574+
575+
namespace dont_track_assert2like_conditions {
576+
577+
extern void __assert_fail(__const char *__assertion, __const char *__file,
578+
unsigned int __line, __const char *__function)
579+
__attribute__((__noreturn__));
580+
#define assert(expr) \
581+
do { \
582+
if (!(expr)) \
583+
__assert_fail(#expr, __FILE__, __LINE__, __func__); \
584+
} while (0)
585+
586+
int getInt();
587+
588+
int cond1;
589+
590+
void bar() {
591+
cond1 = getInt();
592+
}
593+
594+
void f(int flag) {
595+
int *x = 0; // expected-note{{'x' initialized to a null pointer value}}
596+
597+
flag = getInt();
598+
599+
bar();
600+
assert(cond1); // expected-note{{Assuming 'cond1' is not equal to 0}}
601+
// expected-note@-1{{Taking false branch}}
602+
// expected-note@-2{{Loop condition is false. Exiting loop}}
603+
604+
if (flag) // expected-note{{'flag' is not equal to 0}}
605+
// expected-note@-1{{Taking true branch}}
606+
// debug-note@-2{{Tracking condition 'flag'}}
607+
*x = 5; // expected-warning{{Dereference of null pointer}}
608+
// expected-note@-1{{Dereference of null pointer}}
609+
}
610+
611+
#undef assert
612+
} // end of namespace dont_track_assert2like_conditions
613+
614+
namespace dont_track_assert2like_and_conditions {
615+
616+
extern void __assert_fail(__const char *__assertion, __const char *__file,
617+
unsigned int __line, __const char *__function)
618+
__attribute__((__noreturn__));
619+
#define assert(expr) \
620+
do { \
621+
if (!(expr)) \
622+
__assert_fail(#expr, __FILE__, __LINE__, __func__); \
623+
} while (0)
624+
625+
int getInt();
626+
627+
int cond1;
628+
int cond2;
629+
630+
void bar() {
631+
cond1 = getInt();
632+
cond2 = getInt();
633+
}
634+
635+
void f(int flag) {
636+
int *x = 0; // expected-note{{'x' initialized to a null pointer value}}
637+
638+
flag = getInt();
639+
640+
bar();
641+
assert(cond1 && cond2);
642+
// expected-note@-1{{Assuming 'cond1' is not equal to 0}}
643+
// expected-note@-2{{Left side of '&&' is true}}
644+
// expected-note@-3{{Assuming the condition is false}}
645+
// expected-note@-4{{Taking false branch}}
646+
// expected-note@-5{{Loop condition is false. Exiting loop}}
647+
648+
if (flag) // expected-note{{'flag' is not equal to 0}}
649+
// expected-note@-1{{Taking true branch}}
650+
// debug-note@-2{{Tracking condition 'flag'}}
651+
*x = 5; // expected-warning{{Dereference of null pointer}}
652+
// expected-note@-1{{Dereference of null pointer}}
653+
}
654+
655+
#undef assert
656+
} // end of namespace dont_track_assert2like_and_conditions
657+
658+
namespace dont_track_assert2like_or_conditions {
659+
660+
extern void __assert_fail(__const char *__assertion, __const char *__file,
661+
unsigned int __line, __const char *__function)
662+
__attribute__((__noreturn__));
663+
#define assert(expr) \
664+
do { \
665+
if (!(expr)) \
666+
__assert_fail(#expr, __FILE__, __LINE__, __func__); \
667+
} while (0)
668+
669+
int getInt();
670+
671+
int cond1;
672+
int cond2;
673+
674+
void bar() {
675+
cond1 = getInt();
676+
cond2 = getInt();
677+
}
678+
679+
void f(int flag) {
680+
int *x = 0; // expected-note{{'x' initialized to a null pointer value}}
681+
682+
flag = getInt();
683+
684+
bar();
685+
assert(cond1 || cond2);
686+
// expected-note@-1{{Assuming 'cond1' is not equal to 0}}
687+
// expected-note@-2{{Left side of '||' is true}}
688+
// expected-note@-3{{Taking false branch}}
689+
// expected-note@-4{{Loop condition is false. Exiting loop}}
690+
691+
if (flag) // expected-note{{'flag' is not equal to 0}}
692+
// expected-note@-1{{Taking true branch}}
693+
// debug-note@-2{{Tracking condition 'flag'}}
694+
*x = 5; // expected-warning{{Dereference of null pointer}}
695+
// expected-note@-1{{Dereference of null pointer}}
696+
}
697+
698+
#undef assert
699+
} // end of namespace dont_track_assert2like_or_conditions

0 commit comments

Comments
 (0)
Please sign in to comment.