IdempotentOperationChecker.cpp [plain text]
#include "ClangSACheckers.h"
#include "clang/Analysis/CFGStmtMap.h"
#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
#include "clang/AST/Stmt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/Support/ErrorHandling.h"
using namespace clang;
using namespace ento;
namespace {
class IdempotentOperationChecker
: public Checker<check::PreStmt<BinaryOperator>,
check::PostStmt<BinaryOperator>,
check::EndAnalysis> {
public:
void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
void checkPostStmt(const BinaryOperator *B, CheckerContext &C) const;
void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,ExprEngine &Eng) const;
private:
enum Assumption { Possible = 0, Impossible, Equal, LHSis1, RHSis1, LHSis0,
RHSis0 };
static void UpdateAssumption(Assumption &A, const Assumption &New);
static bool isSelfAssign(const Expr *LHS, const Expr *RHS);
static bool isUnused(const Expr *E, AnalysisDeclContext *AC);
static bool isTruncationExtensionAssignment(const Expr *LHS,
const Expr *RHS);
static bool pathWasCompletelyAnalyzed(AnalysisDeclContext *AC,
const CFGBlock *CB,
const CoreEngine &CE);
static bool CanVary(const Expr *Ex,
AnalysisDeclContext *AC);
static bool isConstantOrPseudoConstant(const DeclRefExpr *DR,
AnalysisDeclContext *AC);
static bool containsNonLocalVarDecl(const Stmt *S);
struct BinaryOperatorData {
BinaryOperatorData() : assumption(Possible) {}
Assumption assumption;
ExplodedNodeSet explodedNodes; };
typedef llvm::DenseMap<const BinaryOperator *, BinaryOperatorData>
AssumptionMap;
mutable AssumptionMap hash;
mutable OwningPtr<BugType> BT;
};
}
void IdempotentOperationChecker::checkPreStmt(const BinaryOperator *B,
CheckerContext &C) const {
BinaryOperatorData &Data = hash[B];
Assumption &A = Data.assumption;
AnalysisDeclContext *AC = C.getCurrentAnalysisDeclContext();
if (A == Impossible)
return;
const Expr *LHS = B->getLHS();
const Expr *RHS = B->getRHS();
bool LHSContainsFalsePositive = false, RHSContainsFalsePositive = false;
if (A == Possible) {
LHSContainsFalsePositive = !CanVary(LHS, AC)
|| containsNonLocalVarDecl(LHS);
RHSContainsFalsePositive = !CanVary(RHS, AC)
|| containsNonLocalVarDecl(RHS);
}
ProgramStateRef state = C.getState();
const LocationContext *LCtx = C.getLocationContext();
SVal LHSVal = state->getSVal(LHS, LCtx);
SVal RHSVal = state->getSVal(RHS, LCtx);
if (LHSVal.isUnknownOrUndef() || RHSVal.isUnknownOrUndef()) {
A = Impossible;
return;
}
BinaryOperator::Opcode Op = B->getOpcode();
switch (Op) {
default:
break;
case BO_AddAssign:
case BO_SubAssign:
case BO_MulAssign:
case BO_DivAssign:
case BO_AndAssign:
case BO_OrAssign:
case BO_XorAssign:
case BO_ShlAssign:
case BO_ShrAssign:
case BO_Assign:
if (!isa<Loc>(LHSVal)) {
A = Impossible;
return;
}
LHSVal = state->getSVal(cast<Loc>(LHSVal), LHS->getType());
}
switch (Op) {
default:
break;
case BO_Assign:
if (isSelfAssign(LHS, RHS)) {
if (!isUnused(LHS, AC) && !isTruncationExtensionAssignment(LHS, RHS)) {
UpdateAssumption(A, Equal);
return;
}
else {
A = Impossible;
return;
}
}
case BO_SubAssign:
case BO_DivAssign:
case BO_AndAssign:
case BO_OrAssign:
case BO_XorAssign:
case BO_Sub:
case BO_Div:
case BO_And:
case BO_Or:
case BO_Xor:
case BO_LOr:
case BO_LAnd:
case BO_EQ:
case BO_NE:
if (LHSVal != RHSVal || LHSContainsFalsePositive
|| RHSContainsFalsePositive)
break;
UpdateAssumption(A, Equal);
return;
}
switch (Op) {
default:
break;
case BO_MulAssign:
case BO_DivAssign:
case BO_Mul:
case BO_Div:
case BO_LOr:
case BO_LAnd:
if (!RHSVal.isConstant(1) || RHSContainsFalsePositive)
break;
UpdateAssumption(A, RHSis1);
return;
}
switch (Op) {
default:
break;
case BO_MulAssign:
case BO_Mul:
case BO_LOr:
case BO_LAnd:
if (!LHSVal.isConstant(1) || LHSContainsFalsePositive)
break;
UpdateAssumption(A, LHSis1);
return;
}
switch (Op) {
default:
break;
case BO_AddAssign:
case BO_SubAssign:
case BO_MulAssign:
case BO_AndAssign:
case BO_OrAssign:
case BO_XorAssign:
case BO_Add:
case BO_Sub:
case BO_Mul:
case BO_And:
case BO_Or:
case BO_Xor:
case BO_Shl:
case BO_Shr:
case BO_LOr:
case BO_LAnd:
if (!RHSVal.isConstant(0) || RHSContainsFalsePositive)
break;
UpdateAssumption(A, RHSis0);
return;
}
switch (Op) {
default:
break;
case BO_SubAssign: case BO_MulAssign:
case BO_DivAssign:
case BO_AndAssign:
case BO_ShlAssign:
case BO_ShrAssign:
case BO_Add:
case BO_Sub:
case BO_Mul:
case BO_Div:
case BO_And:
case BO_Or:
case BO_Xor:
case BO_Shl:
case BO_Shr:
case BO_LOr:
case BO_LAnd:
if (!LHSVal.isConstant(0) || LHSContainsFalsePositive)
break;
UpdateAssumption(A, LHSis0);
return;
}
A = Impossible;
}
void IdempotentOperationChecker::checkPostStmt(const BinaryOperator *B,
CheckerContext &C) const {
BinaryOperatorData &Data = hash[B];
const Stmt *predStmt
= cast<StmtPoint>(C.getPredecessor()->getLocation()).getStmt();
if (!isa<BinaryOperator>(predStmt))
return;
Data.explodedNodes.Add(C.getPredecessor());
}
void IdempotentOperationChecker::checkEndAnalysis(ExplodedGraph &G,
BugReporter &BR,
ExprEngine &Eng) const {
if (!BT)
BT.reset(new BugType("Idempotent operation", "Dead code"));
for (AssumptionMap::const_iterator i = hash.begin(); i != hash.end(); ++i) {
const BinaryOperatorData &Data = i->second;
const Assumption &A = Data.assumption;
const ExplodedNodeSet &ES = Data.explodedNodes;
if (ES.begin() == ES.end())
continue;
const BinaryOperator *B = i->first;
if (A == Impossible)
continue;
if (Eng.hasWorkRemaining()) {
AnalysisDeclContext *AC = (*ES.begin())->getLocationContext()
->getAnalysisDeclContext();
if (!pathWasCompletelyAnalyzed(AC,
AC->getCFGStmtMap()->getBlock(B),
Eng.getCoreEngine()))
continue;
}
SmallString<128> buf;
llvm::raw_svector_ostream os(buf);
bool LHSRelevant = false, RHSRelevant = false;
switch (A) {
case Equal:
LHSRelevant = true;
RHSRelevant = true;
if (B->getOpcode() == BO_Assign)
os << "Assigned value is always the same as the existing value";
else
os << "Both operands to '" << B->getOpcodeStr()
<< "' always have the same value";
break;
case LHSis1:
LHSRelevant = true;
os << "The left operand to '" << B->getOpcodeStr() << "' is always 1";
break;
case RHSis1:
RHSRelevant = true;
os << "The right operand to '" << B->getOpcodeStr() << "' is always 1";
break;
case LHSis0:
LHSRelevant = true;
os << "The left operand to '" << B->getOpcodeStr() << "' is always 0";
break;
case RHSis0:
RHSRelevant = true;
os << "The right operand to '" << B->getOpcodeStr() << "' is always 0";
break;
case Possible:
llvm_unreachable("Operation was never marked with an assumption");
case Impossible:
llvm_unreachable(0);
}
for (ExplodedNodeSet::iterator I = ES.begin(), E = ES.end(); I != E; ++I) {
BugReport *report = new BugReport(*BT, os.str(), *I);
if (LHSRelevant) {
const Expr *LHS = i->first->getLHS();
report->addRange(LHS->getSourceRange());
FindLastStoreBRVisitor::registerStatementVarDecls(*report, LHS);
}
if (RHSRelevant) {
const Expr *RHS = i->first->getRHS();
report->addRange(i->first->getRHS()->getSourceRange());
FindLastStoreBRVisitor::registerStatementVarDecls(*report, RHS);
}
BR.EmitReport(report);
}
}
hash.clear();
}
inline void IdempotentOperationChecker::UpdateAssumption(Assumption &A,
const Assumption &New) {
if (A == New)
return;
switch (A) {
case Possible:
A = New;
return;
case Impossible:
return;
default:
A = Impossible;
return;
}
}
bool IdempotentOperationChecker::isSelfAssign(const Expr *LHS, const Expr *RHS) {
LHS = LHS->IgnoreParenCasts();
RHS = RHS->IgnoreParenCasts();
const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS);
if (!LHS_DR)
return false;
const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
if (!VD)
return false;
const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS);
if (!RHS_DR)
return false;
if (VD != RHS_DR->getDecl())
return false;
return true;
}
bool IdempotentOperationChecker::isUnused(const Expr *E,
AnalysisDeclContext *AC) {
if (!E)
return false;
const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts());
if (!DR)
return false;
const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
if (!VD)
return false;
if (AC->getPseudoConstantAnalysis()->wasReferenced(VD))
return false;
return true;
}
bool IdempotentOperationChecker::isTruncationExtensionAssignment(
const Expr *LHS,
const Expr *RHS) {
const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParenCasts());
if (!LHS_DR)
return false;
const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
if (!VD)
return false;
const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS->IgnoreParenCasts());
if (!RHS_DR)
return false;
if (VD != RHS_DR->getDecl())
return false;
return dyn_cast<DeclRefExpr>(RHS->IgnoreParenLValueCasts()) == NULL;
}
bool
IdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisDeclContext *AC,
const CFGBlock *CB,
const CoreEngine &CE) {
CFGReverseBlockReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis();
typedef CoreEngine::BlocksExhausted::const_iterator ExhaustedIterator;
for (ExhaustedIterator I = CE.blocks_exhausted_begin(),
E = CE.blocks_exhausted_end(); I != E; ++I) {
const BlockEdge &BE = I->first;
const CFGBlock *destBlock = BE.getDst();
if (destBlock == CB || CRA->isReachable(destBlock, CB))
return false;
}
typedef CoreEngine::BlocksAborted::const_iterator AbortedIterator;
for (AbortedIterator I = CE.blocks_aborted_begin(),
E = CE.blocks_aborted_end(); I != E; ++I) {
const CFGBlock *destBlock = I->first;
if (destBlock == CB || CRA->isReachable(destBlock, CB))
return false;
}
class VisitWL : public WorkList::Visitor {
const CFGStmtMap *CBM;
const CFGBlock *TargetBlock;
CFGReverseBlockReachabilityAnalysis &CRA;
public:
VisitWL(const CFGStmtMap *cbm, const CFGBlock *targetBlock,
CFGReverseBlockReachabilityAnalysis &cra)
: CBM(cbm), TargetBlock(targetBlock), CRA(cra) {}
virtual bool visit(const WorkListUnit &U) {
ProgramPoint P = U.getNode()->getLocation();
const CFGBlock *B = 0;
if (StmtPoint *SP = dyn_cast<StmtPoint>(&P)) {
B = CBM->getBlock(SP->getStmt());
}
else if (BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
B = BE->getDst();
}
else if (BlockEntrance *BEnt = dyn_cast<BlockEntrance>(&P)) {
B = BEnt->getBlock();
}
else if (BlockExit *BExit = dyn_cast<BlockExit>(&P)) {
B = BExit->getBlock();
}
if (!B)
return true;
return B == TargetBlock || CRA.isReachable(B, TargetBlock);
}
};
VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA);
if (CE.getWorkList()->visitItemsInWorkList(visitWL))
return false;
if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB))
return false;
return true;
}
bool IdempotentOperationChecker::CanVary(const Expr *Ex,
AnalysisDeclContext *AC) {
Ex = Ex->IgnoreParenCasts();
if (Ex->getLocStart().isMacroID())
return false;
switch (Ex->getStmtClass()) {
case Stmt::ArraySubscriptExprClass:
case Stmt::MemberExprClass:
case Stmt::StmtExprClass:
case Stmt::CallExprClass:
case Stmt::VAArgExprClass:
case Stmt::ShuffleVectorExprClass:
return true;
default:
return true;
case Stmt::IntegerLiteralClass:
case Stmt::CharacterLiteralClass:
case Stmt::FloatingLiteralClass:
case Stmt::PredefinedExprClass:
case Stmt::ImaginaryLiteralClass:
case Stmt::StringLiteralClass:
case Stmt::OffsetOfExprClass:
case Stmt::CompoundLiteralExprClass:
case Stmt::AddrLabelExprClass:
case Stmt::BinaryTypeTraitExprClass:
case Stmt::GNUNullExprClass:
case Stmt::InitListExprClass:
case Stmt::DesignatedInitExprClass:
case Stmt::BlockExprClass:
return false;
case Stmt::UnaryExprOrTypeTraitExprClass: {
const UnaryExprOrTypeTraitExpr *SE =
cast<const UnaryExprOrTypeTraitExpr>(Ex);
if (SE->getKind() != UETT_SizeOf)
return false;
return SE->getTypeOfArgument()->isVariableArrayType();
}
case Stmt::DeclRefExprClass:
return !isConstantOrPseudoConstant(cast<DeclRefExpr>(Ex), AC);
case Stmt::BinaryOperatorClass: {
const BinaryOperator *B = cast<const BinaryOperator>(Ex);
if (B->getOpcode() == BO_Sub || B->getOpcode() == BO_Add)
if (B->getLHS()->getType()->getAs<PointerType>())
return false;
return CanVary(B->getRHS(), AC)
|| CanVary(B->getLHS(), AC);
}
case Stmt::UnaryOperatorClass: {
const UnaryOperator *U = cast<const UnaryOperator>(Ex);
switch (U->getOpcode()) {
case UO_Extension:
return false;
default:
return CanVary(U->getSubExpr(), AC);
}
}
case Stmt::ChooseExprClass:
return CanVary(cast<const ChooseExpr>(Ex)->getChosenSubExpr(
AC->getASTContext()), AC);
case Stmt::ConditionalOperatorClass:
case Stmt::BinaryConditionalOperatorClass:
return CanVary(cast<AbstractConditionalOperator>(Ex)->getCond(), AC);
}
}
bool IdempotentOperationChecker::isConstantOrPseudoConstant(
const DeclRefExpr *DR,
AnalysisDeclContext *AC) {
if (DR->getType().isConstQualified())
return true;
if (isa<EnumConstantDecl>(DR->getDecl()))
return true;
const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
if (!VD)
return true;
PseudoConstantAnalysis *PCA = AC->getPseudoConstantAnalysis();
if (PCA->isPseudoConstant(VD))
return true;
return false;
}
bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) {
const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S);
if (DR)
if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
if (!VD->hasLocalStorage())
return true;
for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
++I)
if (const Stmt *child = *I)
if (containsNonLocalVarDecl(child))
return true;
return false;
}
void ento::registerIdempotentOperationChecker(CheckerManager &mgr) {
mgr.registerChecker<IdempotentOperationChecker>();
}