On Tue, Feb 7, 2012 at 10:38 AM, Douglas Gregor <[email protected]> wrote:
>
> On Feb 6, 2012, at 1:00 PM, Eli Friedman wrote:
>
> > On Mon, Feb 6, 2012 at 2:50 PM, Richard Trieu <[email protected]> wrote:
> >> On Mon, Feb 6, 2012 at 2:02 PM, Eli Friedman <[email protected]>
> wrote:
> >>>
> >>> On Mon, Feb 6, 2012 at 1:55 PM, Richard Trieu <[email protected]>
> wrote:
> >>>> The motivation of this path is to catch code like this:
> >>>>
> >>>> for (int i = 0; i < 10; ++i)
> >>>> for (int j = 0; j < 10; ++i)
> >>>> { }
> >>>>
> >>>> The second for loop increments i instead of j causing an infinite
> loop.
> >>>> The
> >>>> warning also checks the body of the for loop so it will trigger on:
> >>>>
> >>>> for (int i; i <10; ) { }
> >>>>
> >>>> But not trigger on:
> >>>>
> >>>> for (int i; i< 10; ) { ++i; }
> >>>>
> >>>> I'm still fine-tuning the trigger conditions, but would like some
> >>>> feedback
> >>>> on this patch.
> >>>
> >>> Adding an additional recursive traversal of the body of every parsed
> >>> for loop is very expensive.
> >>>
> >>> -Eli
> >>
> >>
> >> Is it that expensive? I would think that once the AST was constructed,
> the
> >> visitor would be pretty fast, especially if no action is taken on most
> of
> >> the nodes. I also made the warning default ignore and put in an early
> >> return to prevent the visitors from running in the default case.
> >>
> >> Do you have any suggestions on removing the recursive traversal?
> >
> > Okay, thinking about it a bit more, maybe it's not that expensive, but
> > you should at least measure to make sure.
>
> I'm still very nervous about adding such an AST traversal. Presumably,
> it's not going to be a concern in practice because most of the time, the
> increment statement of the 'for' loop will mention one of the variables in
> the condition, and therefore we'll short-circuit the expensive walk of the
> loop body. It would be helpful to know that's the case.
>
> > I don't have any good suggestion for an alternative.
>
>
> Nor do I.
>
> A couple more comments:
>
> + ValueDecl *VD = E->getDecl();
> + for (SmallVectorImpl<ValueDecl*>::iterator I = Decls.begin(),
> + E = Decls.end();
> + I != E; ++I)
> + if (*I == VD) {
> + FoundDecl = true;
> + return;
> + }
>
> This is linear; please use a SmallPtrSet instead.
>
Done.
>
> Plus, I think you want to narrow this check to only consider VarDecls.
> Functions and enumerators are not interesting.
>
Done.
>
> + S.Diag(Second->getLocStart(), diag::warn_variables_not_in_loop_body)
> + << Second->getSourceRange();
>
> This warning needs to specify which variables were not used or point to
> them in the source.
>
The diagnostic now underlines all the variables in the condition.
>
> Do we want to actually look for modification, e.g., any use of the
> variable that isn't immediately consumed by an lvalue-to-rvalue conversion?
>
Yes, that is exactly what we are checking for. The VisitCastExpr checks
for LvalueToRvalue casts and skips any DeclRefExpr's that are direct
sub-expressions.
>
> - Doug
>
I also did a comparison between runs with and without -Wloop-analysis.
Even with the heavily nested loop, the extra recursive checks don't take
too much extra time to run.
clang loop.cc -fsyntax-only
.460 - .480s
clang loop.cc -fsyntax-only -Wloop-analysis
.520 - .540s
Code with increments removed to trigger 2044 for loop warnings
clang loop.cc -fsyntax-only
.310 - .330s
clang loop.cc -fsyntax-only -Wloop-analysis 2>/dev/null
.740 - .780s
clang loop.cc -fsyntax-only -Wloop-analysis
1.430 - 1.550s
// Test loop code.
#define M(A) A A
#define L1 for(int a1 = 0; a1 < 10;){M(L2) }
#define L2 for(int a2 = 0; a2 < 10;){M(L3) a1++; }
#define L3 for(int a3 = 0; a3 < 10;){M(L4) a2++; }
#define L4 for(int a4 = 0; a4 < 10;){M(L5) a3++; }
#define L5 for(int a5 = 0; a5 < 10;){M(L6) a4++; }
#define L6 for(int a6 = 0; a6 < 10;){M(L7) a5++; }
#define L7 for(int a7 = 0; a7 < 10;){M(L8) a6++; }
#define L8 for(int a8 = 0; a8 < 10;){M(L9) a7++; }
#define L9 for(int a9 = 0; a9 < 10;){M(L) a8++; }
#define L a9++;
void foo() {
L1
L1
L1
L1
}
Index: test/SemaCXX/warn-loop-analysis.cpp
===================================================================
--- test/SemaCXX/warn-loop-analysis.cpp (revision 0)
+++ test/SemaCXX/warn-loop-analysis.cpp (revision 0)
@@ -0,0 +1,36 @@
+// RUN: %clang_cc1 -fsyntax-only -Wloop-analysis -verify %s
+
+struct S {
+ bool stop() { return false; }
+ bool keep_running;
+};
+
+void by_ref(int &value) { }
+void by_value(int value) { }
+void by_pointer(int *value) {}
+
+void test1() {
+ S s;
+ for (; !s.stop();) {}
+ for (; s.keep_running;) {}
+ for (int i; i < 1; ++i) {}
+ for (int i; i < 1; ) {} // expected-warning {{variables used in loop condition not modified in loop body}}
+ for (int i; i < 1; ) { ++i; }
+ for (int i; i < 1; ) { return; }
+ for (int i; i < 1; ) { break; }
+ for (int i; i < 1; ) { goto exit_loop; }
+exit_loop:
+ for (int i; i < 1; ) { by_ref(i); }
+ for (int i; i < 1; ) { by_value(i); } // expected-warning {{variables used in loop condition not modified in loop body}}
+ for (int i; i < 1; ) { by_pointer(&i); }
+
+ for (int i; i < 1; ++i)
+ for (int j; j < 1; ++j)
+ { }
+ for (int i; i < 1; ++i)
+ for (int j; j < 1; ++i) // expected-warning {{variables used in loop condition not modified in loop body}}
+ { }
+ for (int i; i < 1; ++i)
+ for (int j; i < 1; ++j) // expected-warning {{variables used in loop condition not modified in loop body}}
+ { }
+}
Index: include/clang/Basic/DiagnosticSemaKinds.td
===================================================================
--- include/clang/Basic/DiagnosticSemaKinds.td (revision 150501)
+++ include/clang/Basic/DiagnosticSemaKinds.td (working copy)
@@ -14,6 +14,11 @@
let Component = "Sema" in {
let CategoryName = "Semantic Issue" in {
+// For loop analysis
+def warn_variables_not_in_loop_body : Warning<
+ "variables used in loop condition not modified in loop body">,
+ InGroup<DiagGroup<"loop-analysis">>, DefaultIgnore;
+
// Constant expressions
def err_expr_not_ice : Error<
"expression is not an %select{integer|integral}0 constant expression">;
Index: lib/Sema/SemaStmt.cpp
===================================================================
--- lib/Sema/SemaStmt.cpp (revision 150501)
+++ lib/Sema/SemaStmt.cpp (working copy)
@@ -19,6 +19,7 @@
#include "clang/AST/ASTContext.h"
#include "clang/AST/CharUnits.h"
#include "clang/AST/DeclObjC.h"
+#include "clang/AST/EvaluatedExprVisitor.h"
#include "clang/AST/ExprCXX.h"
#include "clang/AST/ExprObjC.h"
#include "clang/AST/StmtObjC.h"
@@ -28,6 +29,7 @@
#include "clang/Basic/TargetInfo.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
using namespace clang;
using namespace sema;
@@ -1009,6 +1011,150 @@
return Owned(new (Context) DoStmt(Body, Cond, DoLoc, WhileLoc, CondRParen));
}
+namespace {
+ // This visitor will traverse a conditional statement and store all
+ // the evaluated decls into a vector. Simple is set to true if none
+ // of the excluded constructs are used.
+ class DeclExtractor : public EvaluatedExprVisitor<DeclExtractor> {
+ llvm::SmallPtrSet<VarDecl*, 4> &Decls;
+ bool Simple;
+ PartialDiagnostic &PDiag;
+public:
+ typedef EvaluatedExprVisitor<DeclExtractor> Inherited;
+
+ DeclExtractor(Sema &S, llvm::SmallPtrSet<VarDecl*, 4> &Decls,
+ PartialDiagnostic &PDiag) :
+ Inherited(S.Context), Decls(Decls), Simple(true), PDiag(PDiag) {}
+
+ bool isSimple() { return Simple; }
+
+ void VisitMemberExpr(MemberExpr *E) {
+ // Don't do analysis on classes.
+ Simple = false;
+ return;
+ }
+
+ void VisitCastExpr(CastExpr *E) {
+ // Don't do analysis on function calls or arrays.
+ if (E->getCastKind() == CK_FunctionToPointerDecay ||
+ E->getCastKind() == CK_ArrayToPointerDecay) {
+ Simple = false;
+ return;
+ }
+
+ Visit(E->getSubExpr());
+ }
+
+ void VisitDeclRefExpr(DeclRefExpr *E) {
+ VarDecl *VD = dyn_cast<VarDecl>(E->getDecl());
+ if (!VD) return;
+
+ PDiag << E->getSourceRange();
+
+ // Dont do analysis on pointers.
+ if (VD->getType()->isAnyPointerType()) {
+ Simple = false;
+ return;
+ }
+
+ Decls.insert(VD);
+ }
+
+ }; // end class DeclExtractor
+
+ // DeclMatcher checks to see if the decls are used in a non-evauluated
+ // context.
+ class DeclMatcher : public StmtVisitor<DeclMatcher> {
+ llvm::SmallPtrSet<VarDecl*, 4> &Decls;
+ bool FoundDecl;
+
+public:
+ DeclMatcher(llvm::SmallPtrSet<VarDecl*, 4> &Decls, Stmt *Statement) :
+ Decls(Decls), FoundDecl(false) {
+ if (!Statement) return;
+ if (Expr *E = dyn_cast<Expr>(Statement)) {
+ VisitExpr(E);
+ return;
+ }
+
+ Visit(Statement);
+ }
+
+ void VisitStmt(Stmt *S) {
+ for (Stmt::child_range C = S->children(); C; ++C)
+ if (*C)
+ this->Visit(*C);
+ }
+
+ void VisitReturnStmt(ReturnStmt *S) {
+ FoundDecl = true;
+ }
+
+ void VisitBreakStmt(BreakStmt *S) {
+ FoundDecl = true;
+ }
+
+ void VisitGotoStmt(GotoStmt *S) {
+ FoundDecl = true;
+ }
+
+ void VisitCastExpr(CastExpr *E) {
+ // Decl is evaluated, not updated. Ignore.
+ if (E->getCastKind() == CK_LValueToRValue)
+ if (isa<DeclRefExpr>(E->getSubExpr()))
+ return;
+
+ Visit(E->getSubExpr());
+ }
+
+ void VisitDeclRefExpr(DeclRefExpr *E) {
+ if (VarDecl *VD = dyn_cast<VarDecl>(E->getDecl()))
+ if (Decls.count(VD)) {
+ FoundDecl = true;
+ return;
+ }
+ }
+
+ bool FoundDeclInUse() { return FoundDecl; }
+
+ }; // end class DeclMatcher
+
+ void CheckForLoopConditionalStatement(Sema &S, Expr *Second,
+ Expr *Third, Stmt *Body) {
+ // Condition is empty
+ if (!Second) return;
+
+ if (S.Diags.getDiagnosticLevel(diag::warn_variables_not_in_loop_body,
+ Second->getLocStart())
+ == DiagnosticsEngine::Ignored)
+ return;
+
+ PartialDiagnostic PDiag = S.PDiag(diag::warn_variables_not_in_loop_body);
+ llvm::SmallPtrSet<VarDecl*, 4> Decls;
+ DeclExtractor DE(S, Decls, PDiag);
+ DE.Visit(Second);
+
+ // Don't analyze complex conditionals.
+ if (!DE.isSimple()) return;
+
+ // No decls found.
+ if (Decls.size() == 0) return;
+
+ // Don't warn on volatile decls.
+ for (llvm::SmallPtrSet<VarDecl*, 4>::iterator I = Decls.begin(),
+ E = Decls.end();
+ I != E; ++I)
+ if ((*I)->getType().isVolatileQualified()) return;
+
+ if (!DeclMatcher(Decls, Second).FoundDeclInUse() &&
+ !DeclMatcher(Decls, Third).FoundDeclInUse() &&
+ !DeclMatcher(Decls, Body).FoundDeclInUse()) {
+ S.Diag(Second->getExprLoc(), PDiag);
+ }
+ }
+
+} // end namespace
+
StmtResult
Sema::ActOnForStmt(SourceLocation ForLoc, SourceLocation LParenLoc,
Stmt *First, FullExprArg second, Decl *secondVar,
@@ -1031,6 +1177,8 @@
}
}
+ CheckForLoopConditionalStatement(*this, second.get(), third.get(), Body);
+
ExprResult SecondResult(second.release());
VarDecl *ConditionVar = 0;
if (secondVar) {
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
