Add -Wloop-analysis. This warning will fire on for loops which the variables

in the loop conditional do not change.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@155835 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 368 insertions, 0 deletions

diff --git a/include/clang/Basic/DiagnosticSemaKinds.td b/include/clang/Basic/DiagnosticSemaKinds.td
index 2fc9d9a0aa..53fb9ec952 100644
--- a/include/clang/Basic/DiagnosticSemaKinds.td
+++ b/include/clang/Basic/DiagnosticSemaKinds.td
@@ -14,6 +14,12 @@
 let Component = "Sema" in {
 let CategoryName = "Semantic Issue" in {
 
+// For loop analysis
+def warn_variables_not_in_loop_body : Warning<
+  "variable%select{s| %1|s %1 and %2|s %1 %2 and %3|s %1 %2 %3 and %4}0 "
+  "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">;
diff --git a/lib/Sema/SemaStmt.cpp b/lib/Sema/SemaStmt.cpp
index 252d3971dc..66ddbaabf1 100644
--- a/lib/Sema/SemaStmt.cpp
+++ b/lib/Sema/SemaStmt.cpp
@@ -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;
@@ -1037,6 +1039,218 @@ Sema::ActOnDoStmt(SourceLocation DoLoc, Stmt *Body,
   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*, 8> &Decls;
+    llvm::SmallVector<SourceRange, 10> &Ranges;
+    bool Simple;
+    PartialDiagnostic &PDiag;
+public:
+  typedef EvaluatedExprVisitor<DeclExtractor> Inherited;
+
+  DeclExtractor(Sema &S, llvm::SmallPtrSet<VarDecl*, 8> &Decls,
+                llvm::SmallVector<SourceRange, 10> &Ranges,
+                PartialDiagnostic &PDiag) :
+      Inherited(S.Context),
+      Decls(Decls),
+      Ranges(Ranges),
+      Simple(true),
+      PDiag(PDiag) {}
+
+  bool isSimple() { return Simple; }
+
+  // Replaces the method in EvaluatedExprVisitor.
+  void VisitMemberExpr(MemberExpr* E) {
+    Simple = false;
+  }
+
+  // Any Stmt not whitelisted will cause the condition to be marked complex.
+  void VisitStmt(Stmt *S) {
+    Simple = false;
+  }
+
+  void VisitBinaryOperator(BinaryOperator *E) {
+    Visit(E->getLHS());
+    Visit(E->getRHS());
+  }
+
+  void VisitCastExpr(CastExpr *E) {
+    Visit(E->getSubExpr());
+  }
+
+  void VisitUnaryOperator(UnaryOperator *E) {
+    // Skip checking conditionals with derefernces.
+    if (E->getOpcode() == UO_Deref)
+      Simple = false;
+    else
+      Visit(E->getSubExpr());
+  }
+
+  void VisitConditionalOperator(ConditionalOperator *E) {
+    Visit(E->getCond());
+    Visit(E->getTrueExpr());
+    Visit(E->getFalseExpr());
+  }
+
+  void VisitParenExpr(ParenExpr *E) {
+    Visit(E->getSubExpr());
+  }
+
+  void VisitBinaryConditionalOperator(BinaryConditionalOperator *E) {
+    Visit(E->getOpaqueValue()->getSourceExpr());
+    Visit(E->getFalseExpr());
+  }
+
+  void VisitIntegerLiteral(IntegerLiteral *E) { }
+  void VisitFloatingLiteral(FloatingLiteral *E) { }
+  void VisitCXXBoolLiteralExpr(CXXBoolLiteralExpr *E) { }
+  void VisitCharacterLiteral(CharacterLiteral *E) { }
+  void VisitGNUNullExpr(GNUNullExpr *E) { }
+  void VisitImaginaryLiteral(ImaginaryLiteral *E) { }
+
+  void VisitDeclRefExpr(DeclRefExpr *E) {
+    VarDecl *VD = dyn_cast<VarDecl>(E->getDecl());
+    if (!VD) return;
+
+    Ranges.push_back(E->getSourceRange());
+
+    Decls.insert(VD);
+  }
+
+  }; // end class DeclExtractor
+
+  // DeclMatcher checks to see if the decls are used in a non-evauluated
+  // context.  
+  class DeclMatcher : public EvaluatedExprVisitor<DeclMatcher> {
+    llvm::SmallPtrSet<VarDecl*, 8> &Decls;
+    bool FoundDecl;
+    //bool EvalDecl;
+
+public:
+  typedef EvaluatedExprVisitor<DeclMatcher> Inherited;
+
+  DeclMatcher(Sema &S, llvm::SmallPtrSet<VarDecl*, 8> &Decls, Stmt *Statement) :
+      Inherited(S.Context), Decls(Decls), FoundDecl(false) {
+    if (!Statement) return;
+
+    Visit(Statement);
+  }
+
+  void VisitReturnStmt(ReturnStmt *S) {
+    FoundDecl = true;
+  }
+
+  void VisitBreakStmt(BreakStmt *S) {
+    FoundDecl = true;
+  }
+
+  void VisitGotoStmt(GotoStmt *S) {
+    FoundDecl = true;
+  }
+
+  void VisitCastExpr(CastExpr *E) {
+    if (E->getCastKind() == CK_LValueToRValue)
+      CheckLValueToRValueCast(E->getSubExpr());
+    else
+      Visit(E->getSubExpr());
+  }
+
+  void CheckLValueToRValueCast(Expr *E) {
+    E = E->IgnoreParenImpCasts();
+
+    if (isa<DeclRefExpr>(E)) {
+      return;
+    }
+
+    if (ConditionalOperator *CO = dyn_cast<ConditionalOperator>(E)) {
+      Visit(CO->getCond());
+      CheckLValueToRValueCast(CO->getTrueExpr());
+      CheckLValueToRValueCast(CO->getFalseExpr());
+      return;
+    }
+
+    if (BinaryConditionalOperator *BCO =
+            dyn_cast<BinaryConditionalOperator>(E)) {
+      CheckLValueToRValueCast(BCO->getOpaqueValue()->getSourceExpr());
+      CheckLValueToRValueCast(BCO->getFalseExpr());
+      return;
+    }
+
+    Visit(E);
+  }
+
+  void VisitDeclRefExpr(DeclRefExpr *E) {
+    if (VarDecl *VD = dyn_cast<VarDecl>(E->getDecl()))
+      if (Decls.count(VD))
+        FoundDecl = true;
+  }
+
+  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*, 8> Decls;
+    llvm::SmallVector<SourceRange, 10> Ranges;
+    DeclExtractor DE(S, Decls, Ranges, 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*, 8>::iterator I = Decls.begin(),
+                                                  E = Decls.end();
+         I != E; ++I)
+      if ((*I)->getType().isVolatileQualified()) return;
+
+    if (DeclMatcher(S, Decls, Second).FoundDeclInUse() ||
+        DeclMatcher(S, Decls, Third).FoundDeclInUse() ||
+        DeclMatcher(S, Decls, Body).FoundDeclInUse())
+      return;
+
+    // Load decl names into diagnostic.
+    if (Decls.size() > 4)
+      PDiag << 0;
+    else {
+      PDiag << Decls.size();
+      for (llvm::SmallPtrSet<VarDecl*, 8>::iterator I = Decls.begin(),
+                                                    E = Decls.end();
+           I != E; ++I)
+        PDiag << (*I)->getDeclName();
+    }
+
+    // Load SourceRanges into diagnostic if there is room.
+    // Otherwise, load the SourceRange of the conditional expression.
+    if (Ranges.size() <= PartialDiagnostic::MaxArguments)
+      for (llvm::SmallVector<SourceRange, 10>::iterator I = Ranges.begin(),
+                                                        E = Ranges.end();
+           I != E; ++I)
+        PDiag << *I;
+    else
+      PDiag << Second->getSourceRange();
+
+    S.Diag(Ranges.begin()->getBegin(), PDiag);
+  }
+
+} // end namespace
+
 StmtResult
 Sema::ActOnForStmt(SourceLocation ForLoc, SourceLocation LParenLoc,
                    Stmt *First, FullExprArg second, Decl *secondVar,
@@ -1059,6 +1273,8 @@ Sema::ActOnForStmt(SourceLocation ForLoc, SourceLocation LParenLoc,
     }
   }
 
+  CheckForLoopConditionalStatement(*this, second.get(), third.get(), Body);
+
   ExprResult SecondResult(second.release());
   VarDecl *ConditionVar = 0;
   if (secondVar) {
diff --git a/test/SemaCXX/warn-loop-analysis.cpp b/test/SemaCXX/warn-loop-analysis.cpp
new file mode 100644
index 0000000000..802ce52c4e
--- /dev/null
+++ b/test/SemaCXX/warn-loop-analysis.cpp
@@ -0,0 +1,146 @@
+// 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 {{variable 'i' 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 {{variable 'i' 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 {{variable 'j' used in loop condition not modified in loop body}}
+      { }
+  for (int i; i < 1; ++i)
+    for (int j; i < 1; ++j)  // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+      { }
+
+  for (int *i, *j; i < j; ++i) {}
+  for (int *i, *j; i < j;) {}  // expected-warning {{variables 'i' and 'j' used in loop condition not modified in loop body}}
+
+  // Dereferencing pointers is ignored for now.
+  for (int *i; *i; ) {}
+}
+
+void test2() {
+  int i, j, k;
+  int *ptr;
+
+  // Testing CastExpr
+  for (; i; ) {} // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i; ) { i = 5; }
+
+  // Testing BinaryOperator
+  for (; i < j; ) {} // expected-warning {{variables 'i' and 'j' used in loop condition not modified in loop body}}
+  for (; i < j; ) { i = 5; }
+  for (; i < j; ) { j = 5; }
+
+  // Testing IntegerLiteral
+  for (; i < 5; ) {} // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i < 5; ) { i = 5; }
+
+  // Testing FloatingLiteral
+  for (; i < 5.0; ) {} // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i < 5.0; ) { i = 5; }
+
+  // Testing CharacterLiteral
+  for (; i == 'a'; ) {} // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i == 'a'; ) { i = 5; }
+
+  // Testing CXXBoolLiteralExpr
+  for (; i == true; ) {} // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i == true; ) { i = 5; }
+
+  // Testing GNUNullExpr
+  for (; ptr == __null; ) {} // expected-warning {{variable 'ptr' used in loop condition not modified in loop body}}
+  for (; ptr == __null; ) { ptr = &i; }
+
+  // Testing UnaryOperator
+  for (; -i > 5; ) {} // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; -i > 5; ) { ++i; }
+
+  // Testing ImaginaryLiteral
+  for (; i != 3i; ) {} // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i != 3i; ) { ++i; }
+
+  // Testing ConditionalOperator
+  for (; i ? j : k; ) {} // expected-warning {{variables 'i' 'j' and 'k' used in loop condition not modified in loop body}}
+  for (; i ? j : k; ) { ++i; }
+  for (; i ? j : k; ) { ++j; }
+  for (; i ? j : k; ) { ++k; }
+  for (; i; ) { j = i ? i : i; }  // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i; ) { j = (i = 1) ? i : i; }
+  for (; i; ) { j = i ? i : ++i; }
+
+  // Testing BinaryConditionalOperator
+  for (; i ?: j; ) {} // expected-warning {{variables 'i' and 'j' used in loop condition not modified in loop body}}
+  for (; i ?: j; ) { ++i; }
+  for (; i ?: j; ) { ++j; }
+  for (; i; ) { j = i ?: i; }  // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+
+  // Testing ParenExpr
+  for (; (i); ) { }  // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; (i); ) { ++i; }
+
+  // Testing non-evaluated variables
+  for (; i < sizeof(j); ) { }  // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i < sizeof(j); ) { ++j; }  // expected-warning {{variable 'i' used in loop condition not modified in loop body}}
+  for (; i < sizeof(j); ) { ++i; }
+}
+
+// False positive and how to silence.
+void test3() {
+  int x;
+  int *ptr = &x;
+  for (;x<5;) { *ptr = 6; }  // expected-warning {{variable 'x' used in loop condition not modified in loop body}}
+
+  for (;x<5;) {
+    *ptr = 6;
+    (void)x;
+  }
+}
+
+// Check ordering and printing of variables.  Max variables is currently 4.
+void test4() {
+  int a, b, c, d, e, f;
+  for (; a;);  // expected-warning {{variable 'a' used in loop condition not modified in loop body}}
+  for (; a + b;);  // expected-warning {{variables 'a' and 'b' used in loop condition not modified in loop body}}
+  for (; a + b + c;);  // expected-warning {{variables 'a' 'b' and 'c' used in loop condition not modified in loop body}}
+  for (; a + b + c + d;);  // expected-warning {{variables 'a' 'b' 'c' and 'd' used in loop condition not modified in loop body}}
+  for (; a + b + c + d + e;);  // expected-warning {{variables used in loop condition not modified in loop body}}
+  for (; a + b + c + d + e + f;);  // expected-warning {{variables used in loop condition not modified in loop body}}
+  for (; a + c + d + b;);  // expected-warning {{variables 'a' 'c' 'd' and 'b' used in loop condition not modified in loop body}}
+  for (; d + c + b + a;);  // expected-warning {{variables 'd' 'c' 'b' and 'a' used in loop condition not modified in loop body}}
+}
+
+// Ensure that the warning doesn't fail when lots of variables are used
+// in the conditional.
+void test5() {
+  for (int a; a+a+a+a+a+a+a+a+a+a;); // \
+   // expected-warning {{variable 'a' used in loop condition not modified in loop body}}
+  for (int a; a+a+a+a+a+a+a+a+a+a+a;); // \
+   // expected-warning {{variable 'a' used in loop condition not modified in loop body}}
+  for (int a; a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a;);  // \
+   // expected-warning {{variable 'a' used in loop condition not modified in loop body}}
+  for (int a; a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a+a;);//\
+   // expected-warning {{variable 'a' used in loop condition not modified in loop body}}
+}