//=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a flow-sensitive, path-insensitive analysis of
// determining reachable blocks within a CFG.
//
//===----------------------------------------------------------------------===//
#include "clang/Analysis/Analyses/ReachableCode.h"
#include "clang/AST/Expr.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/ExprObjC.h"
#include "clang/AST/ParentMap.h"
#include "clang/AST/StmtCXX.h"
#include "clang/Analysis/AnalysisContext.h"
#include "clang/Analysis/CFG.h"
#include "clang/Basic/SourceManager.h"
#include "clang/Lex/Preprocessor.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/SmallVector.h"
using namespace clang;
//===----------------------------------------------------------------------===//
// Core Reachability Analysis routines.
//===----------------------------------------------------------------------===//
static bool isEnumConstant(const Expr *Ex) {
const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex);
if (!DR)
return false;
return isa<EnumConstantDecl>(DR->getDecl());
}
static bool isTrivialExpression(const Expr *Ex) {
Ex = Ex->IgnoreParenCasts();
return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex) ||
isa<CXXBoolLiteralExpr>(Ex) || isa<ObjCBoolLiteralExpr>(Ex) ||
isa<CharacterLiteral>(Ex) ||
isEnumConstant(Ex);
}
static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) {
// Check if the block ends with a do...while() and see if 'S' is the
// condition.
if (const Stmt *Term = B->getTerminator()) {
if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
const Expr *Cond = DS->getCond()->IgnoreParenCasts();
return Cond == S && isTrivialExpression(Cond);
}
}
return false;
}
static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
// Look to see if the current control flow ends with a 'return', and see if
// 'S' is a substatement. The 'return' may not be the last element in the
// block, or may be in a subsequent block because of destructors.
const CFGBlock *Current = B;
while (true) {
for (CFGBlock::const_reverse_iterator I = Current->rbegin(),
E = Current->rend();
I != E; ++I) {
if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
if (RS == S)
return true;
if (const Expr *RE = RS->getRetValue()) {
RE = RE->IgnoreParenCasts();
if (RE == S)
return true;
ParentMap PM(const_cast<Expr *>(RE));
// If 'S' is in the ParentMap, it is a subexpression of
// the return statement.
return PM.getParent(S);
}
}
break;
}
}
// Note also that we are restricting the search for the return statement
// to stop at control-flow; only part of a return statement may be dead,
// without the whole return statement being dead.
if (Current->getTerminator().isTemporaryDtorsBranch()) {
// Temporary destructors have a predictable control flow, thus we want to
// look into the next block for the return statement.
// We look into the false branch, as we know the true branch only contains
// the call to the destructor.
assert(Current->succ_size() == 2);
Current = *(Current->succ_begin() + 1);
} else if (!Current->getTerminator() && Current->succ_size() == 1) {
// If there is only one successor, we're not dealing with outgoing control
// flow. Thus, look into the next block.
Current = *Current->succ_begin();
if (Current->pred_size() > 1) {
// If there is more than one predecessor, we're dealing with incoming
// control flow - if the return statement is in that block, it might
// well be reachable via a different control flow, thus it's not dead.
return false;
}
} else {
// We hit control flow or a dead end. Stop searching.
return false;
}
}
llvm_unreachable("Broke out of infinite loop.");
}
static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM) {
assert(Loc.isMacroID());
SourceLocation Last;
while (Loc.isMacroID()) {
Last = Loc;
Loc = SM.getImmediateMacroCallerLoc(Loc);
}
return Last;
}
/// Returns true if the statement is expanded from a configuration macro.
static bool isExpandedFromConfigurationMacro(const Stmt *S,
Preprocessor &PP,
bool IgnoreYES_NO = false) {
// FIXME: This is not very precise. Here we just check to see if the
// value comes from a macro, but we can do much better. This is likely
// to be over conservative. This logic is factored into a separate function
// so that we can refine it later.
SourceLocation L = S->getLocStart();
if (L.isMacroID()) {
if (IgnoreYES_NO) {
// The Objective-C constant 'YES' and 'NO'
// are defined as macros. Do not treat them
// as configuration values.
SourceManager &SM = PP.getSourceManager();
SourceLocation TopL = getTopMostMacro(L, SM);
StringRef MacroName = PP.getImmediateMacroName(TopL);
if (MacroName == "YES" || MacroName == "NO")
return false;
}
return true;
}
return false;
}
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP);
/// Returns true if the statement represents a configuration value.
///
/// A configuration value is something usually determined at compile-time
/// to conditionally always execute some branch. Such guards are for
/// "sometimes unreachable" code. Such code is usually not interesting
/// to report as unreachable, and may mask truly unreachable code within
/// those blocks.
static bool isConfigurationValue(const Stmt *S,
Preprocessor &PP,
SourceRange *SilenceableCondVal = nullptr,
bool IncludeIntegers = true,
bool WrappedInParens = false) {
if (!S)
return false;
if (const Expr *Ex = dyn_cast<Expr>(S))
S = Ex->IgnoreCasts();
// Special case looking for the sigil '()' around an integer literal.
if (const ParenExpr *PE = dyn_cast<ParenExpr>(S))
if (!PE->getLocStart().isMacroID())
return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal,
IncludeIntegers, true);
if (const Expr *Ex = dyn_cast<Expr>(S))
S = Ex->IgnoreCasts();
bool IgnoreYES_NO = false;
switch (S->getStmtClass()) {
case Stmt::CallExprClass: {
const FunctionDecl *Callee =
dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
return Callee ? Callee->isConstexpr() : false;
}
case Stmt::DeclRefExprClass:
return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP);
case Stmt::ObjCBoolLiteralExprClass:
IgnoreYES_NO = true;
// Fallthrough.
case Stmt::CXXBoolLiteralExprClass:
case Stmt::IntegerLiteralClass: {
const Expr *E = cast<Expr>(S);
if (IncludeIntegers) {
if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())
*SilenceableCondVal = E->getSourceRange();
return WrappedInParens || isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO);
}
return false;
}
case Stmt::MemberExprClass:
return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP);
case Stmt::UnaryExprOrTypeTraitExprClass:
return true;
case Stmt::BinaryOperatorClass: {
const BinaryOperator *B = cast<BinaryOperator>(S);
// Only include raw integers (not enums) as configuration
// values if they are used in a logical or comparison operator
// (not arithmetic).
IncludeIntegers &= (B->isLogicalOp() || B->isComparisonOp());
return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal,
IncludeIntegers) ||
isConfigurationValue(B->getRHS(), PP, SilenceableCondVal,
IncludeIntegers);
}
case Stmt::UnaryOperatorClass: {
const UnaryOperator *UO = cast<UnaryOperator>(S);
if (SilenceableCondVal)
*SilenceableCondVal = UO->getSourceRange();
return UO->getOpcode() == UO_LNot &&
isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal,
IncludeIntegers, WrappedInParens);
}
default:
return false;
}
}
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) {
if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D))
return isConfigurationValue(ED->getInitExpr(), PP);
if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
// As a heuristic, treat globals as configuration values. Note
// that we only will get here if Sema evaluated this
// condition to a constant expression, which means the global
// had to be declared in a way to be a truly constant value.
// We could generalize this to local variables, but it isn't
// clear if those truly represent configuration values that
// gate unreachable code.
if (!VD->hasLocalStorage())
return true;
// As a heuristic, locals that have been marked 'const' explicitly
// can be treated as configuration values as well.
return VD->getType().isLocalConstQualified();
}
return false;
}
/// Returns true if we should always explore all successors of a block.
static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B,
Preprocessor &PP) {
if (const Stmt *Term = B->getTerminator()) {
if (isa<SwitchStmt>(Term))
return true;
// Specially handle '||' and '&&'.
if (isa<BinaryOperator>(Term)) {
return isConfigurationValue(Term, PP);
}
}
const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
return isConfigurationValue(Cond, PP);
}
static unsigned scanFromBlock(const CFGBlock *Start,
llvm::BitVector &Reachable,
Preprocessor *PP,
bool IncludeSometimesUnreachableEdges) {
unsigned count = 0;
// Prep work queue
SmallVector<const CFGBlock*, 32> WL;
// The entry block may have already been marked reachable
// by the caller.
if (!Reachable[Start->getBlockID()]) {
++count;
Reachable[Start->getBlockID()] = true;
}
WL.push_back(Start);
// Find the reachable blocks from 'Start'.
while (!WL.empty()) {
const CFGBlock *item = WL.pop_back_val();
// There are cases where we want to treat all successors as reachable.
// The idea is that some "sometimes unreachable" code is not interesting,
// and that we should forge ahead and explore those branches anyway.
// This allows us to potentially uncover some "always unreachable" code
// within the "sometimes unreachable" code.
// Look at the successors and mark then reachable.
Optional<bool> TreatAllSuccessorsAsReachable;
if (!IncludeSometimesUnreachableEdges)
TreatAllSuccessorsAsReachable = false;
for (CFGBlock::const_succ_iterator I = item->succ_begin(),
E = item->succ_end(); I != E; ++I) {
const CFGBlock *B = *I;
if (!B) do {
const CFGBlock *UB = I->getPossiblyUnreachableBlock();
if (!UB)
break;
if (!TreatAllSuccessorsAsReachable.hasValue()) {
assert(PP);
TreatAllSuccessorsAsReachable =
shouldTreatSuccessorsAsReachable(item, *PP);
}
if (TreatAllSuccessorsAsReachable.getValue()) {
B = UB;
break;
}
}
while (false);
if (B) {
unsigned blockID = B->getBlockID();
if (!Reachable[blockID]) {
Reachable.set(blockID);
WL.push_back(B);
++count;
}
}
}
}
return count;
}
static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
Preprocessor &PP,
llvm::BitVector &Reachable) {
return scanFromBlock(Start, Reachable, &PP, true);
}
//===----------------------------------------------------------------------===//
// Dead Code Scanner.
//===----------------------------------------------------------------------===//
namespace {
class DeadCodeScan {
llvm::BitVector Visited;
llvm::BitVector &Reachable;
SmallVector<const CFGBlock *, 10> WorkList;
Preprocessor &PP;
typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
DeferredLocsTy;
DeferredLocsTy DeferredLocs;
public:
DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP)
: Visited(reachable.size()),
Reachable(reachable),
PP(PP) {}
void enqueue(const CFGBlock *block);
unsigned scanBackwards(const CFGBlock *Start,
clang::reachable_code::Callback &CB);
bool isDeadCodeRoot(const CFGBlock *Block);
const Stmt *findDeadCode(const CFGBlock *Block);
void reportDeadCode(const CFGBlock *B,
const Stmt *S,
clang::reachable_code::Callback &CB);
};
}
void DeadCodeScan::enqueue(const CFGBlock *block) {
unsigned blockID = block->getBlockID();
if (Reachable[blockID] || Visited[blockID])
return;
Visited[blockID] = true;
WorkList.push_back(block);
}
bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
bool isDeadRoot = true;
for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
E = Block->pred_end(); I != E; ++I) {
if (const CFGBlock *PredBlock = *I) {
unsigned blockID = PredBlock->getBlockID();
if (Visited[blockID]) {
isDeadRoot = false;
continue;
}
if (!Reachable[blockID]) {
isDeadRoot = false;
Visited[blockID] = true;
WorkList.push_back(PredBlock);
continue;
}
}
}
return isDeadRoot;
}
static bool isValidDeadStmt(const Stmt *S) {
if (S->getLocStart().isInvalid())
return false;
if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
return BO->getOpcode() != BO_Comma;
return true;
}
const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
const Stmt *S = CS->getStmt();
if (isValidDeadStmt(S))
return S;
}
if (CFGTerminator T = Block->getTerminator()) {
if (!T.isTemporaryDtorsBranch()) {
const Stmt *S = T.getStmt();
if (isValidDeadStmt(S))
return S;
}
}
return nullptr;
}
static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
const std::pair<const CFGBlock *, const Stmt *> *p2) {
if (p1->second->getLocStart() < p2->second->getLocStart())
return -1;
if (p2->second->getLocStart() < p1->second->getLocStart())
return 1;
return 0;
}
unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
clang::reachable_code::Callback &CB) {
unsigned count = 0;
enqueue(Start);
while (!WorkList.empty()) {
const CFGBlock *Block = WorkList.pop_back_val();
// It is possible that this block has been marked reachable after
// it was enqueued.
if (Reachable[Block->getBlockID()])
continue;
// Look for any dead code within the block.
const Stmt *S = findDeadCode(Block);
if (!S) {
// No dead code. Possibly an empty block. Look at dead predecessors.
for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
E = Block->pred_end(); I != E; ++I) {
if (const CFGBlock *predBlock = *I)
enqueue(predBlock);
}
continue;
}
// Specially handle macro-expanded code.
if (S->getLocStart().isMacroID()) {
count += scanMaybeReachableFromBlock(Block, PP, Reachable);
continue;
}
if (isDeadCodeRoot(Block)) {
reportDeadCode(Block, S, CB);
count += scanMaybeReachableFromBlock(Block, PP, Reachable);
}
else {
// Record this statement as the possibly best location in a
// strongly-connected component of dead code for emitting a
// warning.
DeferredLocs.push_back(std::make_pair(Block, S));
}
}
// If we didn't find a dead root, then report the dead code with the
// earliest location.
if (!DeferredLocs.empty()) {
llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
E = DeferredLocs.end(); I != E; ++I) {
const CFGBlock *Block = I->first;
if (Reachable[Block->getBlockID()])
continue;
reportDeadCode(Block, I->second, CB);
count += scanMaybeReachableFromBlock(Block, PP, Reachable);
}
}
return count;
}
static SourceLocation GetUnreachableLoc(const Stmt *S,
SourceRange &R1,
SourceRange &R2) {
R1 = R2 = SourceRange();
if (const Expr *Ex = dyn_cast<Expr>(S))
S = Ex->IgnoreParenImpCasts();
switch (S->getStmtClass()) {
case Expr::BinaryOperatorClass: {
const BinaryOperator *BO = cast<BinaryOperator>(S);
return BO->getOperatorLoc();
}
case Expr::UnaryOperatorClass: {
const UnaryOperator *UO = cast<UnaryOperator>(S);
R1 = UO->getSubExpr()->getSourceRange();
return UO->getOperatorLoc();
}
case Expr::CompoundAssignOperatorClass: {
const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
R1 = CAO->getLHS()->getSourceRange();
R2 = CAO->getRHS()->getSourceRange();
return CAO->getOperatorLoc();
}
case Expr::BinaryConditionalOperatorClass:
case Expr::ConditionalOperatorClass: {
const AbstractConditionalOperator *CO =
cast<AbstractConditionalOperator>(S);
return CO->getQuestionLoc();
}
case Expr::MemberExprClass: {
const MemberExpr *ME = cast<MemberExpr>(S);
R1 = ME->getSourceRange();
return ME->getMemberLoc();
}
case Expr::ArraySubscriptExprClass: {
const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
R1 = ASE->getLHS()->getSourceRange();
R2 = ASE->getRHS()->getSourceRange();
return ASE->getRBracketLoc();
}
case Expr::CStyleCastExprClass: {
const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
R1 = CSC->getSubExpr()->getSourceRange();
return CSC->getLParenLoc();
}
case Expr::CXXFunctionalCastExprClass: {
const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
R1 = CE->getSubExpr()->getSourceRange();
return CE->getLocStart();
}
case Stmt::CXXTryStmtClass: {
return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
}
case Expr::ObjCBridgedCastExprClass: {
const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
R1 = CSC->getSubExpr()->getSourceRange();
return CSC->getLParenLoc();
}
default: ;
}
R1 = S->getSourceRange();
return S->getLocStart();
}
void DeadCodeScan::reportDeadCode(const CFGBlock *B,
const Stmt *S,
clang::reachable_code::Callback &CB) {
// Classify the unreachable code found, or suppress it in some cases.
reachable_code::UnreachableKind UK = reachable_code::UK_Other;
if (isa<BreakStmt>(S)) {
UK = reachable_code::UK_Break;
}
else if (isTrivialDoWhile(B, S)) {
return;
}
else if (isDeadReturn(B, S)) {
UK = reachable_code::UK_Return;
}
SourceRange SilenceableCondVal;
if (UK == reachable_code::UK_Other) {
// Check if the dead code is part of the "loop target" of
// a for/for-range loop. This is the block that contains
// the increment code.
if (const Stmt *LoopTarget = B->getLoopTarget()) {
SourceLocation Loc = LoopTarget->getLocStart();
SourceRange R1(Loc, Loc), R2;
if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
const Expr *Inc = FS->getInc();
Loc = Inc->getLocStart();
R2 = Inc->getSourceRange();
}
CB.HandleUnreachable(reachable_code::UK_Loop_Increment,
Loc, SourceRange(), SourceRange(Loc, Loc), R2);
return;
}
// Check if the dead block has a predecessor whose branch has
// a configuration value that *could* be modified to
// silence the warning.
CFGBlock::const_pred_iterator PI = B->pred_begin();
if (PI != B->pred_end()) {
if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
const Stmt *TermCond =
PredBlock->getTerminatorCondition(/* strip parens */ false);
isConfigurationValue(TermCond, PP, &SilenceableCondVal);
}
}
}
SourceRange R1, R2;
SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2);
}
//===----------------------------------------------------------------------===//
// Reachability APIs.
//===----------------------------------------------------------------------===//
namespace clang { namespace reachable_code {
void Callback::anchor() { }
unsigned ScanReachableFromBlock(const CFGBlock *Start,
llvm::BitVector &Reachable) {
return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
}
void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP,
Callback &CB) {
CFG *cfg = AC.getCFG();
if (!cfg)
return;
// Scan for reachable blocks from the entrance of the CFG.
// If there are no unreachable blocks, we're done.
llvm::BitVector reachable(cfg->getNumBlockIDs());
unsigned numReachable =
scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
if (numReachable == cfg->getNumBlockIDs())
return;
// If there aren't explicit EH edges, we should include the 'try' dispatch
// blocks as roots.
if (!AC.getCFGBuildOptions().AddEHEdges) {
for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
E = cfg->try_blocks_end() ; I != E; ++I) {
numReachable += scanMaybeReachableFromBlock(*I, PP, reachable);
}
if (numReachable == cfg->getNumBlockIDs())
return;
}
// There are some unreachable blocks. We need to find the root blocks that
// contain code that should be considered unreachable.
for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
const CFGBlock *block = *I;
// A block may have been marked reachable during this loop.
if (reachable[block->getBlockID()])
continue;
DeadCodeScan DS(reachable, PP);
numReachable += DS.scanBackwards(block, CB);
if (numReachable == cfg->getNumBlockIDs())
return;
}
}
}} // end namespace clang::reachable_code