From e5af3ce53ec58995b09381ba645ab2117a46647b Mon Sep 17 00:00:00 2001 From: Mike Stump Date: Mon, 20 Jul 2009 23:24:15 +0000 Subject: [PATCH] Add yet more analysis for CFGs involving conditionals that are actually constant. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@76500 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/Analysis/CFG.h | 8 +- lib/Analysis/CFG.cpp | 124 ++++++++++++++++++++++++------ lib/Frontend/AnalysisConsumer.cpp | 2 +- test/Analysis/dead-stores.c | 82 ++++++++++++++++++++ 4 files changed, 187 insertions(+), 29 deletions(-) diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h index e67bf46134..9e7446dc65 100644 --- a/include/clang/Analysis/CFG.h +++ b/include/clang/Analysis/CFG.h @@ -30,7 +30,8 @@ namespace clang { class CFG; class PrinterHelper; class LangOptions; - + class ASTContext; + /// CFGBlock - Represents a single basic block in a source-level CFG. /// It consists of: /// @@ -177,7 +178,8 @@ public: void reverseStmts(); void addSuccessor(CFGBlock* Block) { - Block->Preds.push_back(this); + if (Block) + Block->Preds.push_back(this); Succs.push_back(Block); } @@ -204,7 +206,7 @@ public: /// buildCFG - Builds a CFG from an AST. The responsibility to free the /// constructed CFG belongs to the caller. - static CFG* buildCFG(Stmt* AST); + static CFG* buildCFG(Stmt* AST, ASTContext *C); /// createBlock - Create a new block in the CFG. The CFG owns the block; /// the caller should not directly free it. diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index 5a9e611432..11deec4a23 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -62,6 +62,7 @@ static SourceLocation GetEndLoc(Decl* D) { /// implicit fall-throughs without extra basic blocks. /// class VISIBILITY_HIDDEN CFGBuilder { + ASTContext *Context; CFG* cfg; CFGBlock* Block; CFGBlock* Succ; @@ -94,7 +95,7 @@ public: ~CFGBuilder() { delete cfg; } // buildCFG - Used by external clients to construct the CFG. - CFG* buildCFG(Stmt* Statement); + CFG* buildCFG(Stmt *Statement, ASTContext *C); private: // Visitors to walk an AST and construct the CFG. @@ -166,7 +167,8 @@ static VariableArrayType* FindVA(Type* t) { /// body (compound statement). The ownership of the returned CFG is /// transferred to the caller. If CFG construction fails, this method returns /// NULL. -CFG* CFGBuilder::buildCFG(Stmt* Statement) { +CFG* CFGBuilder::buildCFG(Stmt* Statement, ASTContext* C) { + Context = C; assert(cfg); if (!Statement) return NULL; @@ -397,6 +399,19 @@ CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, bool alwaysAdd) { CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, bool alwaysAdd) { if (B->isLogicalOp()) { // && or || + // See if this is a known constant. + bool KnownTrue = false; + bool KnownFalse = false; + Expr::EvalResult Result; + if (B->getLHS()->Evaluate(Result, *Context) + && Result.Val.isInt()) { + if ((B->getOpcode() == BinaryOperator::LAnd) + == Result.Val.getInt().getBoolValue()) + KnownTrue = true; + else + KnownFalse = true; + } + CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); ConfluenceBlock->appendStmt(B); @@ -416,12 +431,24 @@ CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, bool alwaysAdd) { // Now link the LHSBlock with RHSBlock. if (B->getOpcode() == BinaryOperator::LOr) { - LHSBlock->addSuccessor(ConfluenceBlock); - LHSBlock->addSuccessor(RHSBlock); + if (KnownTrue) + LHSBlock->addSuccessor(0); + else + LHSBlock->addSuccessor(ConfluenceBlock); + if (KnownFalse) + LHSBlock->addSuccessor(0); + else + LHSBlock->addSuccessor(RHSBlock); } else { assert (B->getOpcode() == BinaryOperator::LAnd); - LHSBlock->addSuccessor(RHSBlock); - LHSBlock->addSuccessor(ConfluenceBlock); + if (KnownFalse) + LHSBlock->addSuccessor(0); + else + LHSBlock->addSuccessor(RHSBlock); + if (KnownTrue) + LHSBlock->addSuccessor(0); + else + LHSBlock->addSuccessor(ConfluenceBlock); } // Generate the blocks for evaluating the LHS. @@ -530,6 +557,18 @@ CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { } CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C) { + // See if this is a known constant. + bool KnownTrue = false; + bool KnownFalse = false; + Expr::EvalResult Result; + if (C->getCond()->Evaluate(Result, *Context) + && Result.Val.isInt()) { + if (Result.Val.getInt().getBoolValue()) + KnownTrue = true; + else + KnownFalse = true; + } + // Create the confluence block that will "merge" the results of the ternary // expression. CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); @@ -560,22 +599,36 @@ CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C) { // Create the block that will contain the condition. Block = createBlock(false); - if (LHSBlock) - Block->addSuccessor(LHSBlock); - else { - // If we have no LHS expression, add the ConfluenceBlock as a direct - // successor for the block containing the condition. Moreover, we need to - // reverse the order of the predecessors in the ConfluenceBlock because - // the RHSBlock will have been added to the succcessors already, and we - // want the first predecessor to the the block containing the expression - // for the case when the ternary expression evaluates to true. - Block->addSuccessor(ConfluenceBlock); - assert (ConfluenceBlock->pred_size() == 2); - std::reverse(ConfluenceBlock->pred_begin(), - ConfluenceBlock->pred_end()); + if (LHSBlock) { + if (KnownFalse) + Block->addSuccessor(0); + else + Block->addSuccessor(LHSBlock); + } else { + if (KnownFalse) { + // If we know the condition is false, add NULL as the successor for + // the block containing the condition. In this case, the confluence + // block will have just one predecessor. + Block->addSuccessor(0); + assert (ConfluenceBlock->pred_size() == 1); + } else { + // If we have no LHS expression, add the ConfluenceBlock as a direct + // successor for the block containing the condition. Moreover, we need to + // reverse the order of the predecessors in the ConfluenceBlock because + // the RHSBlock will have been added to the succcessors already, and we + // want the first predecessor to the the block containing the expression + // for the case when the ternary expression evaluates to true. + Block->addSuccessor(ConfluenceBlock); + assert (ConfluenceBlock->pred_size() == 2); + std::reverse(ConfluenceBlock->pred_begin(), + ConfluenceBlock->pred_end()); + } } - Block->addSuccessor(RHSBlock); + if (KnownTrue) + Block->addSuccessor(0); + else + Block->addSuccessor(RHSBlock); Block->setTerminator(C); return addStmt(C->getCond()); @@ -648,6 +701,18 @@ CFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { } CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { + // See if this is a known constant first. + bool KnownTrue = false; + bool KnownFalse = false; + Expr::EvalResult Result; + if (I->getCond()->Evaluate(Result, *Context) + && Result.Val.isInt()) { + if (Result.Val.getInt().getBoolValue()) + KnownTrue = true; + else + KnownFalse = true; + } + // We may see an if statement in the middle of a basic block, or it may be the // first statement we are processing. In either case, we create a new basic // block. First, we create the blocks for the then...else statements, and @@ -711,8 +776,14 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { Block->setTerminator(I); // Now add the successors. - Block->addSuccessor(ThenBlock); - Block->addSuccessor(ElseBlock); + if (KnownFalse) + Block->addSuccessor(0); + else + Block->addSuccessor(ThenBlock); + if (KnownTrue) + Block->addSuccessor(0); + else + Block->addSuccessor(ElseBlock); // Add the condition as the last statement in the new block. This may create // new blocks as the condition may contain control-flow. Any newly created @@ -1438,9 +1509,9 @@ CFGBlock* CFG::createBlock() { /// buildCFG - Constructs a CFG from an AST. Ownership of the returned /// CFG is returned to the caller. -CFG* CFG::buildCFG(Stmt* Statement) { +CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { CFGBuilder Builder; - return Builder.buildCFG(Statement); + return Builder.buildCFG(Statement, C); } /// reverseStmts - Reverses the orders of statements within a CFGBlock. @@ -1826,7 +1897,10 @@ static void print_block(llvm::raw_ostream& OS, const CFG* cfg, if (i == 8 || (i-8) % 10 == 0) OS << "\n "; - OS << " B" << (*I)->getBlockID(); + if (*I) + OS << " B" << (*I)->getBlockID(); + else + OS << " NULL"; } OS << '\n'; diff --git a/lib/Frontend/AnalysisConsumer.cpp b/lib/Frontend/AnalysisConsumer.cpp index 468bbf63ab..7d1dc058ad 100644 --- a/lib/Frontend/AnalysisConsumer.cpp +++ b/lib/Frontend/AnalysisConsumer.cpp @@ -158,7 +158,7 @@ namespace { } virtual CFG* getCFG() { - if (!cfg) cfg.reset(CFG::buildCFG(getBody())); + if (!cfg) cfg.reset(CFG::buildCFG(getBody(), &getContext())); return cfg.get(); } diff --git a/test/Analysis/dead-stores.c b/test/Analysis/dead-stores.c index 1aa971422a..f8677e1cfa 100644 --- a/test/Analysis/dead-stores.c +++ b/test/Analysis/dead-stores.c @@ -185,3 +185,85 @@ int f21() { } return 1; } + +int j; +void f22() { + int x = 4; + int y1 = 4; + int y2 = 4; + int y3 = 4; + int y4 = 4; + int y5 = 4; + int y6 = 4; + int y7 = 4; + int y8 = 4; + int y9 = 4; + int y10 = 4; + + ++x; // expected-warning{{never read}} + ++y1; + ++y2; + ++y3; + ++y4; + ++y5; + ++y6; + ++y7; + ++y8; + ++y9; + ++y10; + + switch (j) { + case 1: + if (0) + (void)x; + if (1) { + (void)y1; + return; + } + (void)x; + break; + case 2: + if (0) + (void)x; + else { + (void)y2; + return; + } + (void)x; + break; + case 3: + if (1) { + (void)y3; + return; + } else + (void)x; + (void)x; + break; + case 4: + 0 ? : ((void)y4, ({ return; })); + (void)x; + break; + case 5: + 1 ? : (void)x; + 0 ? (void)x : ((void)y5, ({ return; })); + (void)x; + break; + case 6: + 1 ? ((void)y6, ({ return; })) : (void)x; + (void)x; + break; + case 7: + (void)(0 && x); + (void)y7; + (void)(0 || (y8, ({ return; }), 1)); + (void)x; + break; + case 8: + (void)(1 && (y9, ({ return; }), 1)); + (void)x; + break; + case 9: + (void)(1 || x); + (void)y10; + } +} -- 2.40.0