26#include "llvm/ADT/BitVector.h"
27#include "llvm/ADT/SmallVector.h"
40 return isa<EnumConstantDecl>(DR->
getDecl());
45 return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex) ||
46 isa<CXXBoolLiteralExpr>(Ex) || isa<ObjCBoolLiteralExpr>(Ex) ||
47 isa<CharacterLiteral>(Ex) ||
55 if (
const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
64 if (
const auto *DRE = dyn_cast<DeclRefExpr>(S))
65 if (
const auto *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl()))
66 return FDecl->getIdentifier() &&
67 FDecl->getBuiltinID() == Builtin::BI__builtin_unreachable;
79 if (
const auto *CE = dyn_cast<CallExpr>(CS->getStmt())) {
80 return CE->getCallee()->IgnoreCasts() == S && CE->isBuiltinAssumeFalse(
C);
92 for (
const CFGElement &CE : llvm::reverse(*Current)) {
93 if (std::optional<CFGStmt> CS = CE.getAs<
CFGStmt>()) {
94 if (
const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
97 if (
const Expr *RE = RS->getRetValue()) {
98 RE = RE->IgnoreParenCasts();
113 if (Current->getTerminator().isTemporaryDtorsBranch()) {
118 assert(Current->succ_size() == 2);
119 Current = *(Current->succ_begin() + 1);
120 }
else if (!Current->getTerminatorStmt() && Current->succ_size() == 1) {
123 Current = *Current->succ_begin();
124 if (Current->pred_size() > 1) {
135 llvm_unreachable(
"Broke out of infinite loop.");
143 Loc =
SM.getImmediateMacroCallerLoc(Loc);
151 bool IgnoreYES_NO =
false) {
165 if (MacroName ==
"YES" || MacroName ==
"NO")
171 if (MacroName ==
"false" || MacroName ==
"true")
191 bool IncludeIntegers =
true,
192 bool WrappedInParens =
false) {
196 if (
const auto *Ex = dyn_cast<Expr>(S))
197 S = Ex->IgnoreImplicit();
199 if (
const auto *Ex = dyn_cast<Expr>(S))
200 S = Ex->IgnoreCasts();
203 if (
const ParenExpr *PE = dyn_cast<ParenExpr>(S))
204 if (!PE->getBeginLoc().isMacroID())
206 IncludeIntegers,
true);
208 if (
const Expr *Ex = dyn_cast<Expr>(S))
209 S = Ex->IgnoreCasts();
211 bool IgnoreYES_NO =
false;
213 switch (S->getStmtClass()) {
214 case Stmt::CallExprClass: {
216 dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
217 return Callee ? Callee->isConstexpr() :
false;
219 case Stmt::DeclRefExprClass:
221 case Stmt::ObjCBoolLiteralExprClass:
224 case Stmt::CXXBoolLiteralExprClass:
225 case Stmt::IntegerLiteralClass: {
226 const Expr *E = cast<Expr>(S);
227 if (IncludeIntegers) {
228 if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())
230 return WrappedInParens ||
235 case Stmt::MemberExprClass:
237 case Stmt::UnaryExprOrTypeTraitExprClass:
239 case Stmt::BinaryOperatorClass: {
250 case Stmt::UnaryOperatorClass: {
254 bool SilenceableCondValNotSet =
255 SilenceableCondVal && SilenceableCondVal->getBegin().isInvalid();
256 bool IsSubExprConfigValue =
258 IncludeIntegers, WrappedInParens);
261 if (SilenceableCondValNotSet &&
262 SilenceableCondVal->getBegin().isValid() &&
263 *SilenceableCondVal ==
266 return IsSubExprConfigValue;
276 if (
const VarDecl *VD = dyn_cast<VarDecl>(D)) {
284 if (!VD->hasLocalStorage())
289 return VD->getType().isLocalConstQualified();
298 if (isa<SwitchStmt>(Term))
301 if (isa<BinaryOperator>(Term)) {
307 if (
const auto *IS = dyn_cast<IfStmt>(Term);
308 IS !=
nullptr && IS->isConstexpr())
317 llvm::BitVector &Reachable,
319 bool IncludeSometimesUnreachableEdges) {
335 while (!WL.empty()) {
336 const CFGBlock *item = WL.pop_back_val();
344 std::optional<bool> TreatAllSuccessorsAsReachable;
345 if (!IncludeSometimesUnreachableEdges)
346 TreatAllSuccessorsAsReachable =
false;
349 E = item->
succ_end(); I != E; ++I) {
352 const CFGBlock *UB = I->getPossiblyUnreachableBlock();
356 if (!TreatAllSuccessorsAsReachable) {
358 TreatAllSuccessorsAsReachable =
362 if (*TreatAllSuccessorsAsReachable) {
371 if (!Reachable[blockID]) {
372 Reachable.set(blockID);
384 llvm::BitVector &Reachable) {
395 llvm::BitVector &Reachable;
403 DeferredLocsTy DeferredLocs;
408 Reachable(reachable),
411 void enqueue(
const CFGBlock *block);
412 unsigned scanBackwards(
const CFGBlock *Start,
419 void reportDeadCode(
const CFGBlock *B,
425void DeadCodeScan::enqueue(
const CFGBlock *block) {
427 if (Reachable[blockID] ||
Visited[blockID])
430 WorkList.push_back(block);
434 bool isDeadRoot =
true;
438 if (
const CFGBlock *PredBlock = *I) {
439 unsigned blockID = PredBlock->getBlockID();
444 if (!Reachable[blockID]) {
447 WorkList.push_back(PredBlock);
457 if (S->getBeginLoc().isInvalid())
460 return BO->getOpcode() != BO_Comma;
466 if (std::optional<CFGStmt> CS = I->getAs<
CFGStmt>()) {
467 const Stmt *S = CS->getStmt();
482static int SrcCmp(
const std::pair<const CFGBlock *, const Stmt *> *p1,
483 const std::pair<const CFGBlock *, const Stmt *> *p2) {
484 if (p1->second->getBeginLoc() < p2->second->getBeginLoc())
486 if (p2->second->getBeginLoc() < p1->second->getBeginLoc())
497 while (!WorkList.empty()) {
519 if (S->getBeginLoc().isMacroID()) {
524 if (isDeadCodeRoot(
Block)) {
525 reportDeadCode(
Block, S, CB);
532 DeferredLocs.push_back(std::make_pair(
Block, S));
538 if (!DeferredLocs.empty()) {
539 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(),
SrcCmp);
540 for (
const auto &I : DeferredLocs) {
544 reportDeadCode(
Block, I.second, CB);
557 if (
const Expr *Ex = dyn_cast<Expr>(S))
558 S = Ex->IgnoreParenImpCasts();
560 switch (S->getStmtClass()) {
561 case Expr::BinaryOperatorClass: {
565 case Expr::UnaryOperatorClass: {
570 case Expr::CompoundAssignOperatorClass: {
576 case Expr::BinaryConditionalOperatorClass:
577 case Expr::ConditionalOperatorClass: {
579 cast<AbstractConditionalOperator>(S);
582 case Expr::MemberExprClass: {
587 case Expr::ArraySubscriptExprClass: {
593 case Expr::CStyleCastExprClass: {
598 case Expr::CXXFunctionalCastExprClass: {
603 case Stmt::CXXTryStmtClass: {
604 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
606 case Expr::ObjCBridgedCastExprClass: {
613 R1 = S->getSourceRange();
614 return S->getBeginLoc();
617void DeadCodeScan::reportDeadCode(
const CFGBlock *B,
623 if (isa<BreakStmt>(S)) {
633 const auto *AS = dyn_cast<AttributedStmt>(S);
634 bool HasFallThroughAttr =
635 AS && hasSpecificAttr<FallThroughAttr>(AS->getAttrs());
647 if (
const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
648 const Expr *
Inc = FS->getInc();
649 Loc =
Inc->getBeginLoc();
650 R2 =
Inc->getSourceRange();
664 if (
const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
665 const Stmt *TermCond =
666 PredBlock->getTerminatorCondition(
false);
681namespace clang {
namespace reachable_code {
683void Callback::anchor() { }
686 llvm::BitVector &Reachable) {
693 CFG *cfg = AC.getCFG();
700 unsigned numReachable =
707 if (!AC.getCFGBuildOptions().AddEHEdges) {
716 for (
const CFGBlock *block : *cfg) {
721 DeadCodeScan DS(reachable, PP, AC.getASTContext());
722 numReachable += DS.scanBackwards(block, CB);
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
Defines enum values for all the target-independent builtin functions.
Defines the clang::Expr interface and subclasses for C++ expressions.
llvm::DenseSet< const void * > Visited
Defines the clang::Preprocessor interface.
static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM)
static bool isEnumConstant(const Expr *Ex)
static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B, Preprocessor &PP)
Returns true if we should always explore all successors of a block.
static int SrcCmp(const std::pair< const CFGBlock *, const Stmt * > *p1, const std::pair< const CFGBlock *, const Stmt * > *p2)
static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S)
static bool isExpandedFromConfigurationMacro(const Stmt *S, Preprocessor &PP, bool IgnoreYES_NO=false)
Returns true if the statement is expanded from a configuration macro.
static bool isValidDeadStmt(const Stmt *S)
static unsigned scanFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable, Preprocessor *PP, bool IncludeSometimesUnreachableEdges)
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP)
static bool isBuiltinUnreachable(const Stmt *S)
static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S, ASTContext &C)
static bool isDeadReturn(const CFGBlock *B, const Stmt *S)
static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start, Preprocessor &PP, llvm::BitVector &Reachable)
static SourceLocation GetUnreachableLoc(const Stmt *S, SourceRange &R1, SourceRange &R2)
static bool isTrivialExpression(const Expr *Ex)
Defines the SourceManager interface.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
AbstractConditionalOperator - An abstract base class for ConditionalOperator and BinaryConditionalOpe...
SourceLocation getQuestionLoc() const
AnalysisDeclContext contains the context data for the function, method or block under analysis.
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
SourceLocation getRBracketLoc() const
Expr * getLHS()
An array access can be written A[4] or 4[A] (both are equivalent).
A builtin binary operation expression such as "x + y" or "x <= y".
static bool isLogicalOp(Opcode Opc)
static bool isComparisonOp(Opcode Opc)
SourceLocation getOperatorLoc() const
Represents a single basic block in a source-level CFG.
ElementList::const_iterator const_iterator
CFGTerminator getTerminator() const
succ_iterator succ_begin()
Stmt * getTerminatorStmt()
const Stmt * getLoopTarget() const
AdjacentBlocks::const_iterator const_pred_iterator
pred_iterator pred_begin()
unsigned getBlockID() const
Stmt * getTerminatorCondition(bool StripParens=true)
AdjacentBlocks::const_iterator const_succ_iterator
Represents a top-level expression in a basic block.
std::optional< T > getAs() const
Convert to the specified CFGElement type, returning std::nullopt if this CFGElement is not of the des...
Represents CFGBlock terminator statement.
bool isStmtBranch() const
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
try_block_range try_blocks() const
unsigned getNumBlockIDs() const
Returns the total number of BlockIDs allocated (which start at 0).
CStyleCastExpr - An explicit cast in C (C99 6.5.4) or a C-style cast in C++ (C++ [expr....
SourceLocation getLParenLoc() const
Represents an explicit C++ type conversion that uses "functional" notation (C++ [expr....
SourceLocation getBeginLoc() const LLVM_READONLY
CompoundAssignOperator - For compound assignments (e.g.
A reference to a declared variable, function, enum, etc.
DoStmt - This represents a 'do/while' stmt.
An instance of this object exists for each enum constant that is defined.
This represents one expression.
Expr * IgnoreParenCasts() LLVM_READONLY
Skip past any parentheses and casts which might surround this expression until reaching a fixed point...
Expr * IgnoreCasts() LLVM_READONLY
Skip past any casts which might surround this expression until reaching a fixed point.
ForStmt - This represents a 'for (init;cond;inc)' stmt.
Represents a function declaration or definition.
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
SourceLocation getMemberLoc() const
getMemberLoc - Return the location of the "member", in X->F, it is the location of 'F'.
An Objective-C "bridged" cast expression, which casts between Objective-C pointers and C pointers,...
SourceLocation getLParenLoc() const
ParenExpr - This represents a parethesized expression, e.g.
Stmt * getParent(Stmt *) const
Engages in a tight little dance with the lexer to efficiently preprocess tokens.
SourceManager & getSourceManager() const
StringRef getImmediateMacroName(SourceLocation Loc)
Retrieve the name of the immediate macro expansion.
const LangOptions & getLangOpts() const
ReturnStmt - This represents a return, optionally of an expression: return; return 4;.
Encodes a location in the source.
This class handles loading and caching of source files into memory.
A trivial tuple used to represent a source range.
Stmt - This represents one statement.
SourceRange getSourceRange() const LLVM_READONLY
SourceLocation tokens are not useful in isolation - they are low level value objects created/interpre...
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
SourceLocation getOperatorLoc() const
getOperatorLoc - Return the location of the operator.
Expr * getSubExpr() const
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Represents a variable declaration or definition.
virtual void HandleUnreachable(UnreachableKind UK, SourceLocation L, SourceRange ConditionVal, SourceRange R1, SourceRange R2, bool HasFallThroughAttr)=0
bool Inc(InterpState &S, CodePtr OpPC)
1) Pops a pointer from the stack 2) Load the value from the pointer 3) Writes the value increased by ...
void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP, Callback &CB)
unsigned ScanReachableFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable)
ScanReachableFromBlock - Mark all blocks reachable from Start.
UnreachableKind
Classifications of unreachable code.
@ C
Languages that the frontend can parse and compile.