Fixes according to code review comments
authorSam Panzer <espanz@gmail.com>
Fri, 24 Aug 2012 22:10:15 +0000 (22:10 +0000)
committerSam Panzer <espanz@gmail.com>
Fri, 24 Aug 2012 22:10:15 +0000 (22:10 +0000)
llvm-svn: 162611

clang-tools-extra/loop-convert/LoopActions.cpp
clang-tools-extra/loop-convert/LoopActions.h
clang-tools-extra/loop-convert/LoopConvert.cpp
clang-tools-extra/loop-convert/LoopMatchers.cpp
clang-tools-extra/loop-convert/LoopMatchers.h
clang-tools-extra/loop-convert/StmtAncestor.h
clang-tools-extra/loop-convert/VariableNaming.cpp
clang-tools-extra/loop-convert/VariableNaming.h

index 9a2e1cc..41803c5 100644 (file)
@@ -10,10 +10,6 @@ namespace loop_migrate {
 using namespace clang::ast_matchers;
 using namespace clang::tooling;
 
-/// \brief A type for holding the list of containers indexed.
-typedef llvm::SmallVector<
-  std::pair<const Expr *, llvm::FoldingSetNodeID>, 1> ContainerResult;
-
 /// \brief The information needed to describe a valid convertible usage
 /// of an array index or iterator.
 struct Usage {
@@ -60,9 +56,10 @@ class ForLoopIndexUseVisitor
  public:
   ForLoopIndexUseVisitor(ASTContext *Context, const VarDecl *IndexVar,
                          const VarDecl *EndVar, const Expr *ContainerExpr,
+                         const Expr *ArrayBoundExpr,
                          bool ContainerNeedsDereference) :
     Context(Context), IndexVar(IndexVar), EndVar(EndVar),
-    ContainerExpr(ContainerExpr),
+    ContainerExpr(ContainerExpr), ArrayBoundExpr(ArrayBoundExpr),
     ContainerNeedsDereference(ContainerNeedsDereference),
     OnlyUsedAsIndex(true),  AliasDecl(NULL), ConfidenceLevel(TCK_Safe) {
      if (ContainerExpr) {
@@ -70,13 +67,12 @@ class ForLoopIndexUseVisitor
        llvm::FoldingSetNodeID ID;
        const Expr *E = ContainerExpr->IgnoreParenImpCasts();
        E->Profile(ID, *Context, true);
-       ContainersIndexed.push_back(std::make_pair(E, ID));
      }
   }
 
   /// \brief Finds all uses of IndexVar in Body, placing all usages in Usages,
-  /// all referenced arrays in ContainersIndexed, and returns true if IndexVar
-  /// was only used in a way consistent with a range-based for loop.
+  /// and returns true if IndexVar was only used in a way consistent with a
+  /// range-based for loop.
   ///
   /// The general strategy is to reject any DeclRefExprs referencing IndexVar,
   /// with the exception of certain acceptable patterns.
@@ -87,7 +83,7 @@ class ForLoopIndexUseVisitor
   /// function and in overloaded operator[].
   bool findAndVerifyUsages(const Stmt *Body) {
     TraverseStmt(const_cast<Stmt *>(Body));
-    return OnlyUsedAsIndex;
+    return OnlyUsedAsIndex && ContainerExpr;
   }
 
   /// \brief Add a set of components that we should consider relevant to the
@@ -102,19 +98,9 @@ class ForLoopIndexUseVisitor
   /// \brief Accessor for Usages.
   const UsageResult &getUsages() const { return Usages; }
 
-  /// \brief Determines whether or not exactly one container was indexed by
-  /// IndexVar.
-  bool indexesSingleContainer() const {
-    return ContainersIndexed.size() == 1;
-  }
-
-  /// \brief Get the container indexed by IndexVar.
-  ///
-  /// This method asserts that there is only one container indexed; check that
-  /// indexesSingleContainer() returns true first.
-  const Expr *getSingleContainerIndexed() const {
-    assert(indexesSingleContainer() && "Index used for multiple containers");
-    return ContainersIndexed.begin()->first;
+  /// \brief Get the container indexed by IndexVar, if any.
+  const Expr *getContainerIndexed() const {
+    return ContainerExpr;
   }
 
   /// \brief Returns the statement declaring the variable created as an alias
@@ -157,6 +143,8 @@ class ForLoopIndexUseVisitor
   const VarDecl *EndVar;
   /// The Expr which refers to the container.
   const Expr *ContainerExpr;
+  /// The Expr which refers to the terminating condition for array-based loops.
+  const Expr *ArrayBoundExpr;
   bool ContainerNeedsDereference;
 
   // Output member variables:
@@ -164,8 +152,6 @@ class ForLoopIndexUseVisitor
   /// ArraySubscriptExpressions.
   UsageResult Usages;
   bool OnlyUsedAsIndex;
-  /// A set which holds expressions containing the referenced arrays.
-  ContainerResult ContainersIndexed;
   /// The DeclStmt for an alias to the container element.
   const DeclStmt *AliasDecl;
   Confidence ConfidenceLevel;
@@ -271,7 +257,7 @@ static const Expr *digThroughConstructors(const Expr *E) {
 }
 
 /// \brief If the expression is a dereference or call to operator*(), return the
-/// operand. Otherwise, returns NULL.
+/// operand. Otherwise, return NULL.
 static const Expr *getDereferenceOperand(const Expr *E) {
   if (const UnaryOperator *Uop = dyn_cast<UnaryOperator>(E))
     return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() : NULL;
@@ -297,7 +283,7 @@ static bool containsExpr(ASTContext *Context, const ContainerT *Container,
 }
 
 /// \brief Returns true when the index expression is a declaration reference to
-/// IndexVar and the array's base exists.
+/// IndexVar.
 ///
 /// If the index variable is `index`, this function returns true on
 ///    arrayExpression[index];
@@ -305,10 +291,9 @@ static bool containsExpr(ASTContext *Context, const ContainerT *Container,
 /// but not
 ///    containerExpression[notIndex];
 static bool isIndexInSubscriptExpr(const Expr *IndexExpr,
-                                   const VarDecl *IndexVar,
-                                   const Expr *Arr) {
+                                   const VarDecl *IndexVar) {
   const DeclRefExpr *Idx = getDeclRef(IndexExpr);
-  return Arr && Idx && Idx->getType()->isIntegerType()
+  return Idx && Idx->getType()->isIntegerType()
              && areSameVariable(IndexVar, Idx->getDecl());
 }
 
@@ -336,12 +321,11 @@ static bool isIndexInSubscriptExpr(const Expr *IndexExpr,
 static bool isIndexInSubscriptExpr(ASTContext *Context, const Expr *IndexExpr,
                                    const VarDecl *IndexVar, const Expr *Obj,
                                    const Expr *SourceExpr, bool PermitDeref) {
-  if (!SourceExpr || !Obj
-      || !isIndexInSubscriptExpr(IndexExpr, IndexVar, Obj))
+  if (!SourceExpr || !Obj || !isIndexInSubscriptExpr(IndexExpr, IndexVar))
     return false;
 
   if (areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(),
-                   Obj->IgnoreParenImpCasts()))
+                  Obj->IgnoreParenImpCasts()))
     return true;
 
   if (const Expr *InnerObj = getDereferenceOperand(Obj->IgnoreParenImpCasts()))
@@ -352,10 +336,9 @@ static bool isIndexInSubscriptExpr(ASTContext *Context, const Expr *IndexExpr,
   return false;
 }
 
-/// \brief Returns true when Opcall is a call a one-parameter operator on
+/// \brief Returns true when Opcall is a call a one-parameter dereference of
 /// IndexVar.
 ///
-/// Note that this function assumes that the opcode is operator* or operator->.
 /// For example, if the index variable is `index`, returns true for
 ///   *index
 /// but not
@@ -363,15 +346,12 @@ static bool isIndexInSubscriptExpr(ASTContext *Context, const Expr *IndexExpr,
 ///   *notIndex
 static bool isDereferenceOfOpCall(const CXXOperatorCallExpr *OpCall,
                                   const VarDecl *IndexVar) {
-  return OpCall->getNumArgs() == 1 &&
+  return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 &&
          exprReferencesVariable(IndexVar, OpCall->getArg(0));
 }
 
 /// \brief Returns true when Uop is a dereference of IndexVar.
 ///
-/// Note that this is the
-/// only isValidXXX function that confirms that the opcode is correct, as there
-/// is only one way to trigger this case (namely, the builtin operator*).
 /// For example, if the index variable is `index`, returns true for
 ///   *index
 /// but not
@@ -396,14 +376,14 @@ static bool isDereferenceOfUop(const UnaryOperator *Uop,
 ///     T t = *i;
 ///     // use t, do not use i
 ///   }
-static bool isAliasDecl(const Decl *TheDecl, const VarDecl *TargetDecl) {
+static bool isAliasDecl(const Decl *TheDecl, const VarDecl *IndexVar) {
   const VarDecl *VDecl = dyn_cast<VarDecl>(TheDecl);
   if (!VDecl)
     return false;
   if (!VDecl->hasInit())
     return false;
   const Expr *Init =
-      digThroughConstructors(VDecl->getInit()->IgnoreImpCasts());
+      digThroughConstructors(VDecl->getInit()->IgnoreParenImpCasts());
   if (!Init)
     return false;
 
@@ -412,16 +392,16 @@ static bool isAliasDecl(const Decl *TheDecl, const VarDecl *TargetDecl) {
     const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(Init);
     // We don't really care which array is used here. We check to make sure
     // it was the correct one later, since the AST will traverse it next.
-    return isIndexInSubscriptExpr(ASE->getIdx(), TargetDecl, ASE->getBase());
+    return isIndexInSubscriptExpr(ASE->getIdx(), IndexVar);
   }
 
   case Stmt::UnaryOperatorClass:
-    return isDereferenceOfUop(cast<UnaryOperator>(Init), TargetDecl);
+    return isDereferenceOfUop(cast<UnaryOperator>(Init), IndexVar);
 
   case Stmt::CXXOperatorCallExprClass: {
       const CXXOperatorCallExpr *OpCall = cast<CXXOperatorCallExpr>(Init);
       if (OpCall->getOperator() == OO_Star)
-        return isDereferenceOfOpCall(OpCall, TargetDecl);
+        return isDereferenceOfOpCall(OpCall, IndexVar);
       break;
   }
 
@@ -609,7 +589,7 @@ bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
   return VisitorBase::TraverseCXXOperatorCallExpr(OpCall);
 }
 
-/// If we encounter an array with IndexVar as the index of an
+/// \brief If we encounter an array with IndexVar as the index of an
 /// ArraySubsriptExpression, note it as a consistent usage and prune the
 /// AST traversal.
 ///
@@ -618,23 +598,31 @@ bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr(
 ///   int arr[N];
 /// This is intended to permit
 ///   for (int i = 0; i < N; ++i) {  /* use arr[i] */ }
+/// but not
 ///   for (int i = 0; i < N; ++i) {  /* use notArr[i] */ }
 /// and further checking needs to be done later to ensure that exactly one array
 /// is referenced.
 bool ForLoopIndexUseVisitor::TraverseArraySubscriptExpr(
     ArraySubscriptExpr *ASE) {
   Expr *Arr = ASE->getBase();
-  if (isIndexInSubscriptExpr(ASE->getIdx(), IndexVar, Arr)) {
-    const Expr *ArrReduced = Arr->IgnoreParenCasts();
-    if (!containsExpr(Context, &ContainersIndexed, ArrReduced)) {
-      llvm::FoldingSetNodeID ID;
-      ArrReduced->Profile(ID, *Context, true);
-      ContainersIndexed.push_back(std::make_pair(ArrReduced, ID));
-    }
-    Usages.push_back(Usage(ASE));
-    return true;
+  if (!isIndexInSubscriptExpr(ASE->getIdx(), IndexVar))
+    return VisitorBase::TraverseArraySubscriptExpr(ASE);
+
+  if ((ContainerExpr && !areSameExpr(Context, Arr->IgnoreParenImpCasts(),
+                                     ContainerExpr->IgnoreParenImpCasts()))
+      || !arrayMatchesBoundExpr(Context, Arr->IgnoreImpCasts()->getType(),
+                                ArrayBoundExpr)) {
+    // If we have already discovered the array being indexed and this isn't it
+    // or this array doesn't match, mark this loop as unconvertible.
+    OnlyUsedAsIndex = false;
+    return VisitorBase::TraverseArraySubscriptExpr(ASE);
   }
-  return VisitorBase::TraverseArraySubscriptExpr(ASE);
+
+  if (!ContainerExpr)
+    ContainerExpr = Arr;
+
+  Usages.push_back(Usage(ASE));
+  return true;
 }
 
 /// \brief If we encounter a reference to IndexVar in an unpruned branch of the
@@ -690,7 +678,7 @@ bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *DS) {
 
 //// \brief Apply the source transformations necessary to migrate the loop!
 void LoopFixer::doConversion(ASTContext *Context,
-                             const VarDecl *IndexVar, const VarDecl *EndVar,
+                             const VarDecl *IndexVar,
                              const Expr *ContainerExpr,
                              const UsageResult &Usages,
                              const DeclStmt *AliasDecl,
@@ -711,21 +699,14 @@ void LoopFixer::doConversion(ASTContext *Context,
     // No further replacements are made to the loop, since the iterator or index
     // was used exactly once - in the initialization of AliasVar.
   } else {
-    VariableNamer Namer(Context, GeneratedDecls,
-                        &ParentFinder->getStmtToParentStmtMap(),
-                        IndexVar->getDeclContext(), TheLoop, IndexVar,
-                        MaybeContainer);
+    VariableNamer Namer(GeneratedDecls, &ParentFinder->getStmtToParentStmtMap(),
+                        TheLoop, IndexVar, MaybeContainer);
     VarName = Namer.createIndexName();
     // First, replace all usages of the array subscript expression with our new
     // variable.
     for (UsageResult::const_iterator I = Usages.begin(), E = Usages.end();
          I != E; ++I) {
-      std::string ReplaceText;
-      if (I->IsArrow)
-        ReplaceText = VarName + ".";
-      else
-        ReplaceText = VarName;
-
+      std::string ReplaceText = I->IsArrow ? VarName + "." : VarName;
       ReplacedVarRanges->insert(std::make_pair(TheLoop, IndexVar));
       if (!CountOnly)
         Replace->insert(
@@ -750,8 +731,8 @@ void LoopFixer::doConversion(ASTContext *Context,
                            + MaybeDereference + ContainerString + ")").str();
   if (!CountOnly)
     Replace->insert(Replacement(Context->getSourceManager(),
-                                     CharSourceRange::getTokenRange(ParenRange),
-                                     Range));
+                                CharSourceRange::getTokenRange(ParenRange),
+                                Range));
   GeneratedDecls->insert(make_pair(TheLoop, VarName));
 }
 
@@ -760,8 +741,8 @@ void LoopFixer::doConversion(ASTContext *Context,
 /// If it is, returns the object whose begin() or end() method is called, and
 /// the output parameter isArrow is set to indicate whether the initialization
 /// is called via . or ->.
-static const Expr *getContainerFromInitializer(const Expr* Init,
-                                               bool IsBegin, bool *IsArrow) {
+static const Expr *getContainerFromBeginEndCall(const Expr* Init, bool IsBegin,
+                                                bool *IsArrow) {
   // FIXME: Maybe allow declaration/initialization outside of the for loop?
   const CXXMemberCallExpr *TheCall =
       dyn_cast_or_null<CXXMemberCallExpr>(digThroughConstructors(Init));
@@ -782,114 +763,61 @@ static const Expr *getContainerFromInitializer(const Expr* Init,
   return SourceExpr;
 }
 
-/// \brief Determines the variable whose begin() and end() functions are called
+/// \brief Determines the container whose begin() and end() functions are called
 /// for an iterator-based loop.
-static const Expr *findContainer(ASTContext *Context, const VarDecl *BeginVar,
-                                 const VarDecl *EndVar, const Expr *EndExpr,
+///
+/// BeginExpr must be a member call to a function named "begin()", and EndExpr
+/// must be a member .
+static const Expr *findContainer(ASTContext *Context, const Expr *BeginExpr,
+                                 const Expr *EndExpr,
                                  bool *ContainerNeedsDereference) {
-  const Expr *BeginInitExpr = BeginVar->getInit();
-  const Expr *EndInitExpr = EndVar ? EndVar->getInit() : EndExpr;
-
   // Now that we know the loop variable and test expression, make sure they are
   // valid.
   bool BeginIsArrow = false;
   bool EndIsArrow = false;
-  const Expr *ContainerExpr = getContainerFromInitializer(BeginInitExpr,
-                                                          /*IsBegin=*/true,
-                                                          &BeginIsArrow);
-  if (!ContainerExpr)
+  const Expr *BeginContainerExpr =
+      getContainerFromBeginEndCall(BeginExpr, /*IsBegin=*/true, &BeginIsArrow);
+  if (!BeginContainerExpr)
       return NULL;
-  const Expr *EndSourceExpr = getContainerFromInitializer(EndInitExpr,
-                                                          /*IsBegin=*/false,
-                                                          &EndIsArrow);
+
+  const Expr *EndContainerExpr =
+      getContainerFromBeginEndCall(EndExpr, /*IsBegin=*/false, &EndIsArrow);
   // Disallow loops that try evil things like this (note the dot and arrow):
   //  for (IteratorType It = Obj.begin(), E = Obj->end(); It != E; ++It) { }
-  if (!EndSourceExpr || BeginIsArrow != EndIsArrow ||
-      !areSameExpr(Context, EndSourceExpr, ContainerExpr))
+  if (!EndContainerExpr || BeginIsArrow != EndIsArrow ||
+      !areSameExpr(Context, EndContainerExpr, BeginContainerExpr))
     return NULL;
 
   *ContainerNeedsDereference = BeginIsArrow;
-  return ContainerExpr;
+  return BeginContainerExpr;
 }
 
-/// \brief The LoopFixer callback, which determines if loops discovered by the
-/// matchers are convertible, printing information about the loops if so.
-void LoopFixer::run(const MatchFinder::MatchResult &Result) {
-  Confidence ConfidenceLevel(TCK_Safe);
-  ASTContext *Context = Result.Context;
-  const ForStmt *TheLoop = Result.Nodes.getStmtAs<ForStmt>(LoopName);
-
-  if (!Context->getSourceManager().isFromMainFile(TheLoop->getForLoc()))
-    return;
-
-  const VarDecl *LoopVar = Result.Nodes.getDeclAs<VarDecl>(IncrementVarName);
-  const VarDecl *CondVar = Result.Nodes.getDeclAs<VarDecl>(ConditionVarName);
-  const VarDecl *InitVar = Result.Nodes.getDeclAs<VarDecl>(InitVarName);
-
-  if (!areSameVariable(LoopVar, CondVar) || !areSameVariable(LoopVar, InitVar))
-    return;
-  const Expr *BoundExpr= Result.Nodes.getStmtAs<Expr>(ConditionBoundName);
-  const VarDecl *EndVar = Result.Nodes.getDeclAs<VarDecl>(EndVarName);
-  const VarDecl *ConditionEndVar =
-        Result.Nodes.getDeclAs<VarDecl>(ConditionEndVarName);
-  const Expr *ContainerExpr = NULL;
-
-  // Make sure that the end iterator defined in the loop is actually used in the
-  // loop condition.
-  if (EndVar && !areSameVariable(EndVar, ConditionEndVar))
-    return;
-
-  // If the end comparison isn't a variable, we can try to work with the
-  // expression the loop variable is being tested against instead.
-  const CXXMemberCallExpr *EndCall =
-      Result.Nodes.getStmtAs<CXXMemberCallExpr>(EndCallName);
-
-  // If the loop calls end()/size() after each iteration, lower our confidence
-  // level.
-  if (FixerKind != LFK_Array && !EndVar) {
-    if (!EndCall)
-      return;
-    ConfidenceLevel.lowerTo(TCK_Reasonable);
-  }
-
-  bool ContainerNeedsDereference = false;
-  // FIXME: Try to put most of this logic inside a matcher. Currently, matchers
-  // don't allow the right-recursive checks in digThroughConstructors.
-  if (FixerKind == LFK_Iterator)
-    ContainerExpr = findContainer(Context, LoopVar, EndVar, EndCall,
-                                  &ContainerNeedsDereference);
-  else if (FixerKind == LFK_PseudoArray) {
-    ContainerExpr = EndCall->getImplicitObjectArgument();
-    ContainerNeedsDereference =
-        cast<MemberExpr>(EndCall->getCallee())->isArrow();
-  }
-
+/// \brief Given that we have verified that the loop's header appears to be
+/// convertible, run the complete analysis on the loop to determine if the
+/// loop's body is convertible.
+void LoopFixer::FindAndVerifyUsages(ASTContext *Context,
+                                    const VarDecl *LoopVar,
+                                    const VarDecl *EndVar,
+                                    const Expr *ContainerExpr,
+                                    const Expr *BoundExpr,
+                                    bool ContainerNeedsDereference,
+                                    const ForStmt *TheLoop,
+                                    Confidence ConfidenceLevel) {
   ForLoopIndexUseVisitor Finder(Context, LoopVar, EndVar, ContainerExpr,
-                           ContainerNeedsDereference);
-
-  // Either a container or an integral upper bound must exist.
+                                BoundExpr, ContainerNeedsDereference);
   if (ContainerExpr) {
     ComponentFinderASTVisitor ComponentFinder;
     ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts());
     Finder.addComponents(ComponentFinder.getComponents());
-  } else if (!BoundExpr)
-    return;
+  }
 
   if (!Finder.findAndVerifyUsages(TheLoop->getBody()))
     return;
 
-  if (!Finder.indexesSingleContainer())
-    return;
-
   ConfidenceLevel.lowerTo(Finder.getConfidenceLevel());
-  // We require that a single array/container be indexed into by LoopVar.
-  // This check is done by ForLoopIndexUseVisitor for non-array loops, but we
-  // may not know which array is being looped over until the end of the
-  // traversal.
   if (FixerKind == LFK_Array) {
-    ContainerExpr = Finder.getSingleContainerIndexed();
-    if (!arrayMatchesBoundExpr(Context, ContainerExpr->getType(), BoundExpr))
-      return;
+    // The array being indexed by IndexVar was discovered during traversal.
+    ContainerExpr = Finder.getContainerIndexed()->IgnoreParenImpCasts();
     // Very few loops are over expressions that generate arrays rather than
     // array variables. Consider loops over arrays that aren't just represented
     // by a variable to be risky conversions.
@@ -907,15 +835,14 @@ void LoopFixer::run(const MatchFinder::MatchResult &Result) {
     return;
   }
 
-  ParentFinder->gatherAncestors(Context->getTranslationUnitDecl(),
-                                /*RunEvenIfNotEmpty=*/false);
-
+  ParentFinder->gatherAncestors(Context->getTranslationUnitDecl());
   // Ensure that we do not try to move an expression dependent on a local
   // variable declared inside the loop outside of it!
   DependencyFinderASTVisitor
       DependencyFinder(&ParentFinder->getStmtToParentStmtMap(),
                        &ParentFinder->getDeclToParentStmtMap(),
                        ReplacedVarRanges, TheLoop);
+
   // Not all of these are actually deferred changes.
   // FIXME: Determine when the external dependency isn't an expression converted
   // by another loop.
@@ -923,17 +850,74 @@ void LoopFixer::run(const MatchFinder::MatchResult &Result) {
     ++*DeferredChanges;
     return;
   }
-
   if (ConfidenceLevel.get() < RequiredConfidenceLevel) {
     ++*RejectedChanges;
     return;
   }
 
-  doConversion(Context, LoopVar, EndVar, ContainerExpr, Finder.getUsages(),
+  doConversion(Context, LoopVar, ContainerExpr, Finder.getUsages(),
                Finder.getAliasDecl(), TheLoop, ContainerNeedsDereference);
-
   ++*AcceptedChanges;
 }
 
+/// \brief The LoopFixer callback, which determines if loops discovered by the
+/// matchers are convertible, printing information about the loops if so.
+void LoopFixer::run(const MatchFinder::MatchResult &Result) {
+  const BoundNodes &Nodes = Result.Nodes;
+  Confidence ConfidenceLevel(TCK_Safe);
+  ASTContext *Context = Result.Context;
+  const ForStmt *TheLoop = Nodes.getStmtAs<ForStmt>(LoopName);
+
+  if (!Context->getSourceManager().isFromMainFile(TheLoop->getForLoc()))
+    return;
+
+  // Check that we have exactly one index variable and at most one end variable.
+  const VarDecl *LoopVar = Nodes.getDeclAs<VarDecl>(IncrementVarName);
+  const VarDecl *CondVar = Nodes.getDeclAs<VarDecl>(ConditionVarName);
+  const VarDecl *InitVar = Nodes.getDeclAs<VarDecl>(InitVarName);
+  if (!areSameVariable(LoopVar, CondVar) || !areSameVariable(LoopVar, InitVar))
+    return;
+  const VarDecl *EndVar = Nodes.getDeclAs<VarDecl>(EndVarName);
+  const VarDecl *ConditionEndVar =
+      Nodes.getDeclAs<VarDecl>(ConditionEndVarName);
+  if (EndVar && !areSameVariable(EndVar, ConditionEndVar))
+    return;
+
+  // If the end comparison isn't a variable, we can try to work with the
+  // expression the loop variable is being tested against instead.
+  const CXXMemberCallExpr *EndCall =
+      Nodes.getStmtAs<CXXMemberCallExpr>(EndCallName);
+  const Expr *BoundExpr = Nodes.getStmtAs<Expr>(ConditionBoundName);
+  // If the loop calls end()/size() after each iteration, lower our confidence
+  // level.
+  if (FixerKind == LFK_Array && !BoundExpr)
+      return;
+  if (FixerKind != LFK_Array && !EndVar) {
+    if (!EndCall)
+      return;
+    ConfidenceLevel.lowerTo(TCK_Reasonable);
+  }
+
+  const Expr *ContainerExpr = NULL;
+  bool ContainerNeedsDereference = false;
+  // FIXME: Try to put most of this logic inside a matcher. Currently, matchers
+  // don't allow the right-recursive checks in digThroughConstructors.
+  if (FixerKind == LFK_Iterator)
+    ContainerExpr = findContainer(Context, LoopVar->getInit(),
+                                  EndVar ? EndVar->getInit() : EndCall,
+                                  &ContainerNeedsDereference);
+  else if (FixerKind == LFK_PseudoArray) {
+    ContainerExpr = EndCall->getImplicitObjectArgument();
+    ContainerNeedsDereference =
+        cast<MemberExpr>(EndCall->getCallee())->isArrow();
+  }
+  // We must know the container being iterated over by now for non-array loops.
+  if (!ContainerExpr && FixerKind != LFK_Array)
+    return;
+
+  FindAndVerifyUsages(Context, LoopVar, EndVar, ContainerExpr, BoundExpr,
+                      ContainerNeedsDereference, TheLoop, ConfidenceLevel);
+}
+
 } // namespace loop_migrate
 } // namespace clang
index 8772ed6..b1bc558 100644 (file)
@@ -23,6 +23,7 @@ namespace clang {
 namespace loop_migrate {
 
 struct Usage;
+class Confidence;
 // The main computational result of ForLoopIndexUseVisitor.
 typedef llvm::SmallVector<Usage, 8> UsageResult;
 
@@ -75,11 +76,21 @@ class LoopFixer : public ast_matchers::MatchFinder::MatchCallback {
   /// \brief Computes the changes needed to convert a given for loop, and
   /// applies it if this->CountOnly is false.
   void doConversion(ASTContext *Context,
-                    const VarDecl *IndexVar, const VarDecl *EndVar,
+                    const VarDecl *IndexVar,
                     const Expr *ContainerExpr, const UsageResult &Usages,
                     const DeclStmt *AliasDecl, const ForStmt *TheLoop,
                     bool ContainerNeedsDereference);
 
+  /// \brief Given a loop header that would be convertible, discover all usages
+  /// of the index variable and convert the loop if possible.
+  void FindAndVerifyUsages(ASTContext *Context,
+                           const VarDecl *LoopVar,
+                           const VarDecl *EndVar,
+                           const Expr *ContainerExpr,
+                           const Expr *BoundExpr,
+                           bool ContainerNeedsDereference,
+                           const ForStmt *TheLoop,
+                           Confidence ConfidenceLevel);
 };
 
 } // namespace loop_migrate
index eb30089..6e75bbc 100644 (file)
@@ -77,8 +77,8 @@ int main(int argc, const char **argv) {
   ClangTool SyntaxTool(*Compilations, SourcePaths);
 
   // First, let's check to make sure there were no errors.
-  if (int result = SyntaxTool.run(
-      newFrontendActionFactory<clang::SyntaxOnlyAction>())) {
+  if (int result =
+        SyntaxTool.run(newFrontendActionFactory<clang::SyntaxOnlyAction>())) {
     llvm::errs() << "Error compiling files.\n";
     return result;
   }
index ef3f750..92602d9 100644 (file)
@@ -13,8 +13,21 @@ const char EndCallName[] = "endCall";
 const char ConditionEndVarName[] = "conditionEndVar";
 const char EndVarName[] = "endVar";
 
+// shared matchers
 static const TypeMatcher AnyType = anything();
 
+static const StatementMatcher IntegerComparisonMatcher =
+    expression(ignoringParenImpCasts(declarationReference(to(
+        variable(hasType(isInteger())).bind(ConditionVarName)))));
+
+static const DeclarationMatcher InitToZeroMatcher =
+    variable(hasInitializer(ignoringParenImpCasts(
+        integerLiteral(equals(0))))).bind(InitVarName);
+
+static const StatementMatcher IncrementVarMatcher =
+    declarationReference(to(
+        variable(hasType(isInteger())).bind(IncrementVarName)));
+
 // FIXME: How best to document complicated matcher expressions? They're fairly
 // self-documenting...but there may be some unintuitive parts.
 
@@ -35,25 +48,20 @@ static const TypeMatcher AnyType = anything();
 ///   - The index variable is only used as an array index.
 ///   - All arrays indexed by the loop are the same.
 StatementMatcher makeArrayLoopMatcher() {
-  StatementMatcher ArrayComparisonMatcher =
-      expression(ignoringParenImpCasts(declarationReference(to(
-          variable(hasType(isInteger())).bind(ConditionVarName)))));
   StatementMatcher ArrayBoundMatcher =
       expression(hasType(isInteger())).bind(ConditionBoundName);
 
-  return id(LoopName, forStmt(
-      hasLoopInit(declarationStatement(hasSingleDecl(id(InitVarName, variable(
-          hasInitializer(ignoringParenImpCasts(integerLiteral(equals(0))))))))),
+  return forStmt(
+      hasLoopInit(declarationStatement(hasSingleDecl(InitToZeroMatcher))),
       hasCondition(anyOf(binaryOperator(hasOperatorName("<"),
-                                        hasLHS(ArrayComparisonMatcher),
+                                        hasLHS(IntegerComparisonMatcher),
                                         hasRHS(ArrayBoundMatcher)),
                          binaryOperator(hasOperatorName(">"),
                                         hasLHS(ArrayBoundMatcher),
-                                        hasRHS(ArrayComparisonMatcher)))),
-      hasIncrement(unaryOperator(
-          hasOperatorName("++"),
-          hasUnaryOperand(declarationReference(to(
-              variable(hasType(isInteger())).bind(IncrementVarName))))))));
+                                        hasRHS(IntegerComparisonMatcher)))),
+      hasIncrement(unaryOperator(hasOperatorName("++"),
+                                 hasUnaryOperand(IncrementVarMatcher))))
+      .bind(LoopName);
 }
 
 /// \brief The matcher used for iterator-based for loops.
@@ -113,29 +121,30 @@ StatementMatcher makeIteratorLoopMatcher() {
       hasArgument(0, IteratorComparisonMatcher),
       hasArgument(1, IteratorBoundMatcher));
 
-  return id(LoopName, forStmt(
-            hasLoopInit(anyOf(
-                declarationStatement(declCountIs(2),
-                                     containsDeclaration(0, InitDeclMatcher),
-                                     containsDeclaration(1, EndDeclMatcher)),
-                declarationStatement(hasSingleDecl(InitDeclMatcher)))),
-            hasCondition(anyOf(
-                binaryOperator(hasOperatorName("!="),
-                               hasLHS(IteratorComparisonMatcher),
-                               hasRHS(IteratorBoundMatcher)),
-                binaryOperator(hasOperatorName("!="),
-                               hasLHS(IteratorBoundMatcher),
-                               hasRHS(IteratorComparisonMatcher)),
-                OverloadedNEQMatcher)),
-            hasIncrement(anyOf(
-                unaryOperator(hasOperatorName("++"),
-                              hasUnaryOperand(declarationReference(to(
-                                  variable(hasType(pointsTo(AnyType)))
-                                     .bind(IncrementVarName))))),
-                overloadedOperatorCall(
-                    hasOverloadedOperatorName("++"),
-                    hasArgument(0, declarationReference(to(
-                        variable().bind(IncrementVarName)))))))));
+  return forStmt(
+      hasLoopInit(anyOf(
+          declarationStatement(declCountIs(2),
+                               containsDeclaration(0, InitDeclMatcher),
+                               containsDeclaration(1, EndDeclMatcher)),
+          declarationStatement(hasSingleDecl(InitDeclMatcher)))),
+      hasCondition(anyOf(
+          binaryOperator(hasOperatorName("!="),
+                         hasLHS(IteratorComparisonMatcher),
+                         hasRHS(IteratorBoundMatcher)),
+          binaryOperator(hasOperatorName("!="),
+                         hasLHS(IteratorBoundMatcher),
+                         hasRHS(IteratorComparisonMatcher)),
+          OverloadedNEQMatcher)),
+      hasIncrement(anyOf(
+          unaryOperator(hasOperatorName("++"),
+                        hasUnaryOperand(declarationReference(to(
+                            variable(hasType(pointsTo(AnyType)))
+                            .bind(IncrementVarName))))),
+          overloadedOperatorCall(
+              hasOverloadedOperatorName("++"),
+              hasArgument(0, declarationReference(to(
+                  variable().bind(IncrementVarName))))))))
+      .bind(LoopName);
 }
 
 /// \brief The matcher used for array-like containers (pseudoarrays).
@@ -165,9 +174,6 @@ StatementMatcher makeIteratorLoopMatcher() {
 ///   - If the end iterator variable 'g' is defined, it is the same as 'j'
 ///   - The container's iterators would not be invalidated during the loop
 StatementMatcher makePseudoArrayLoopMatcher() {
-  DeclarationMatcher InitDeclMatcher =
-         variable(hasInitializer(ignoringParenImpCasts(
-             integerLiteral(equals(0))))).bind(InitVarName);
   StatementMatcher SizeCallMatcher =
       memberCall(argumentCountIs(0), callee(method(anyOf(hasName("size"),
                                                          hasName("length")))));
@@ -181,33 +187,29 @@ StatementMatcher makePseudoArrayLoopMatcher() {
   DeclarationMatcher EndDeclMatcher =
        variable(hasInitializer(EndInitMatcher)).bind(EndVarName);
 
-  StatementMatcher IntegerComparisonMatcher =
-      expression(ignoringParenImpCasts(declarationReference(to(
-          variable(hasType(isInteger())).bind(ConditionVarName)))));
-
-  StatementMatcher ArrayBoundMatcher =
+  StatementMatcher IndexBoundMatcher =
       expression(anyOf(
           ignoringParenImpCasts(declarationReference(to(
               variable(hasType(isInteger())).bind(ConditionEndVarName)))),
           EndInitMatcher));
 
-  return id(LoopName, forStmt(
+  return forStmt(
       hasLoopInit(anyOf(
           declarationStatement(declCountIs(2),
-                               containsDeclaration(0, InitDeclMatcher),
+                               containsDeclaration(0, InitToZeroMatcher),
                                containsDeclaration(1, EndDeclMatcher)),
-          declarationStatement(hasSingleDecl(InitDeclMatcher)))),
+          declarationStatement(hasSingleDecl(InitToZeroMatcher)))),
       hasCondition(anyOf(
           binaryOperator(hasOperatorName("<"),
                          hasLHS(IntegerComparisonMatcher),
-                         hasRHS(ArrayBoundMatcher)),
+                         hasRHS(IndexBoundMatcher)),
           binaryOperator(hasOperatorName(">"),
-                         hasLHS(ArrayBoundMatcher),
+                         hasLHS(IndexBoundMatcher),
                          hasRHS(IntegerComparisonMatcher)))),
       hasIncrement(unaryOperator(
           hasOperatorName("++"),
-          hasUnaryOperand(declarationReference(to(
-              variable(hasType(isInteger())).bind(IncrementVarName))))))));
+          hasUnaryOperand(IncrementVarMatcher))))
+      .bind(LoopName);
 }
 
 } // namespace loop_migrate
index 273fd63..8dfc17e 100644 (file)
@@ -36,6 +36,7 @@ extern const char EndVarName[];
 ast_matchers::StatementMatcher makeArrayLoopMatcher();
 ast_matchers::StatementMatcher makeIteratorLoopMatcher();
 ast_matchers::StatementMatcher makePseudoArrayLoopMatcher();
+
 } //namespace loop_migrate
 } //namespace clang
 
index 858fa09..9b1ec94 100644 (file)
@@ -20,14 +20,18 @@ namespace loop_migrate {
 
 /// A map used to walk the AST in reverse: maps child Stmt to parent Stmt.
 typedef llvm::DenseMap<const Stmt*, const Stmt*> StmtParentMap;
+
 /// A map used to walk the AST in reverse:
 ///  maps VarDecl to the to parent DeclStmt.
 typedef llvm::DenseMap<const VarDecl*, const DeclStmt*> DeclParentMap;
+
 /// A map used to track which variables have been removed by a refactoring pass.
 /// It maps the parent ForStmt to the removed index variable's VarDecl.
 typedef llvm::DenseMap<const ForStmt*, const VarDecl *> ReplacedVarsMap;
+
 /// A map used to remember the variable names generated in a Stmt
 typedef llvm::DenseMap<const Stmt*, std::string> StmtGeneratedVarNameMap;
+
 /// A vector used to store the AST subtrees of an Expr.
 typedef llvm::SmallVector<const Expr *, 16> ComponentVector;
 
@@ -42,12 +46,10 @@ class StmtAncestorASTVisitor :
 
   /// \brief Run the analysis on the TranslationUnitDecl.
   ///
-  /// In case we're running this analysis multiple times, don't repeat the
-  /// work unless RunEvenIfNotEmpty is set to true.
-  void gatherAncestors(const TranslationUnitDecl *TUD, bool RunEvenIfNotEmpty) {
-    if (RunEvenIfNotEmpty || StmtAncestors.empty()) {
+  /// In case we're running this analysis multiple times, don't repeat the work.
+  void gatherAncestors(const TranslationUnitDecl *TUD) {
+    if (StmtAncestors.empty())
       TraverseDecl(const_cast<TranslationUnitDecl *>(TUD));
-    }
   }
 
   /// Accessor for StmtAncestors.
@@ -110,8 +112,33 @@ class DependencyFinderASTVisitor :
     StmtParents(StmtParents), DeclParents(DeclParents),
     ContainingStmt(ContainingStmt), ReplacedVars(ReplacedVars) { }
 
-  /// Run the analysis on Body, and return true iff the expression depends on
-  /// some variable declared within ContainingStmt.
+  /// \brief Run the analysis on Body, and return true iff the expression
+  /// depends on some variable declared within ContainingStmt.
+  ///
+  /// This is intended to protect against hoisting the container expression
+  /// outside of an inner context if part of that expression is declared in that
+  /// inner context.
+  ///
+  /// For example,
+  ///   const int N = 10, M = 20;
+  ///   int arr[N][M];
+  ///   int getRow();
+  ///
+  ///   for (int i = 0; i < M; ++i) {
+  ///     int k = getRow();
+  ///     printf("%d:", arr[k][i]);
+  ///   }
+  ///
+  /// At first glance, this loop looks like it could be changed to
+  ///   for (int elem : arr[k]) {
+  ///     int k = getIndex();
+  ///     printf("%d:", elem);
+  ///   }
+  /// But this is malformed, since `k` is used before it is defined!
+  ///
+  /// In order to avoid this, this class looks at the container expression
+  /// `arr[k]` and decides whether or not it contains a sub-expression declared
+  /// within the the loop body.
   bool dependsOnOutsideVariable(const Stmt *Body) {
     DependsOnOutsideVariable = false;
     TraverseStmt(const_cast<Stmt *>(Body));
index eb9f955..89dc488 100644 (file)
@@ -19,8 +19,6 @@ std::string VariableNamer::createIndexName() {
   else
     IteratorName = "elem";
 
-  // FIXME: Maybe create a class so that this call doesn't need 6 parameters
-  // every time?
   if (!declarationExists(IteratorName))
     return IteratorName;
 
@@ -49,24 +47,7 @@ std::string VariableNamer::createIndexName() {
 ///
 /// We also check to see if the same identifier was generated by this loop
 /// converter in a loop nested within SourceStmt.
-bool VariableNamer::declarationExists(const std::string& Symbol) {
-  IdentifierInfo& Identifier = Context->Idents.get(Symbol);
-  DeclarationName Name =
-      Context->DeclarationNames.getIdentifier(&Identifier);
-
-  // First, let's check the parent context.
-  // FIXME: lookup() always returns the pair (NULL, NULL) because its
-  // StoredDeclsMap is not initialized (i.e. LookupPtr.getInt() is false inside
-  // of DeclContext::lookup()). Why is this?
-  // NOTE: We work around this by checking when a shadowed declaration is
-  // referenced, rather than now.
-  for (const DeclContext *CurrContext = LoopContext; CurrContext != NULL;
-       CurrContext = CurrContext->getLookupParent()) {
-    DeclContext::lookup_const_result Result = CurrContext->lookup(Name);
-    if (Result.first != Result.second)
-        return true;
-  }
-
+bool VariableNamer::declarationExists(const StringRef Symbol) {
   // Determine if the symbol was generated in a parent context.
   for (const Stmt *S = SourceStmt; S != NULL; S = ReverseAST->lookup(S)) {
     StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(S);
@@ -74,6 +55,12 @@ bool VariableNamer::declarationExists(const std::string& Symbol) {
       return true;
   }
 
+  // FIXME: Rather than detecting conflicts at their usages, we should check the
+  // parent context.
+  // For some reason, lookup() always returns the pair (NULL, NULL) because its
+  // StoredDeclsMap is not initialized (i.e. LookupPtr.getInt() is false inside
+  // of DeclContext::lookup()). Why is this?
+
   // Finally, determine if the symbol was used in the loop or a child context.
   DeclFinderASTVisitor DeclFinder(Symbol, GeneratedDecls);
   return DeclFinder.findUsages(SourceStmt);
index 6df9c42..b3bc58e 100644 (file)
@@ -20,8 +20,8 @@
 
 namespace clang {
 namespace loop_migrate {
-/// \brief VariableNamer - Create names for generated variables within
-/// a particular statement.
+
+/// \brief Create names for generated variables within a particular statement.
 ///
 /// VariableNamer uses a DeclContext as a reference point, checking for any
 /// conflicting declarations higher up in the context or within SourceStmt.
@@ -29,13 +29,11 @@ namespace loop_migrate {
 /// index, if they exist.
 class VariableNamer {
  public:
-  VariableNamer(ASTContext *Context, StmtGeneratedVarNameMap *GeneratedDecls,
-                const StmtParentMap *ReverseAST, const DeclContext *LoopContext,
-                const Stmt *SourceStmt, const VarDecl *OldIndex,
-                const VarDecl *TheContainer) :
-  Context(Context), GeneratedDecls(GeneratedDecls), ReverseAST(ReverseAST),
-  LoopContext(LoopContext), SourceStmt(SourceStmt), OldIndex(OldIndex),
-  TheContainer(TheContainer) { }
+  VariableNamer(StmtGeneratedVarNameMap *GeneratedDecls,
+                const StmtParentMap *ReverseAST, const Stmt *SourceStmt,
+                const VarDecl *OldIndex, const VarDecl *TheContainer) :
+  GeneratedDecls(GeneratedDecls), ReverseAST(ReverseAST),
+  SourceStmt(SourceStmt), OldIndex(OldIndex), TheContainer(TheContainer) { }
 
   /// \brief Generate a new index name.
   ///
@@ -45,17 +43,15 @@ class VariableNamer {
   std::string createIndexName();
 
  private:
-  ASTContext *Context;
   StmtGeneratedVarNameMap *GeneratedDecls;
   const StmtParentMap *ReverseAST;
-  const DeclContext *LoopContext;
   const Stmt *SourceStmt;
   const VarDecl *OldIndex;
   const VarDecl *TheContainer;
 
   // Determine whether or not a declaration that would conflict with Symbol
   // exists in an outer context or in any statement contained in SourceStmt.
-  bool declarationExists(const std::string &Symbol);
+  bool declarationExists(const StringRef Symbol);
 };
 
 } // namespace loop_migrate