diff options
author | Sam Panzer <espanz@gmail.com> | 2012-08-24 22:10:15 +0000 |
---|---|---|
committer | Sam Panzer <espanz@gmail.com> | 2012-08-24 22:10:15 +0000 |
commit | 49c9a7ae247064d5915dee4dbc1b58acaa638606 (patch) | |
tree | fd65af1360a2c812ed195f20f920721f2a16a9fd | |
parent | 1f4dc0491680daa06f93ef64e00e07c217a73609 (diff) |
Fixes according to code review comments
git-svn-id: https://llvm.org/svn/llvm-project/clang-tools-extra/trunk@162611 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | loop-convert/LoopActions.cpp | 300 | ||||
-rw-r--r-- | loop-convert/LoopActions.h | 13 | ||||
-rw-r--r-- | loop-convert/LoopConvert.cpp | 4 | ||||
-rw-r--r-- | loop-convert/LoopMatchers.cpp | 102 | ||||
-rw-r--r-- | loop-convert/LoopMatchers.h | 1 | ||||
-rw-r--r-- | loop-convert/StmtAncestor.h | 41 | ||||
-rw-r--r-- | loop-convert/VariableNaming.cpp | 27 | ||||
-rw-r--r-- | loop-convert/VariableNaming.h | 20 |
8 files changed, 258 insertions, 250 deletions
diff --git a/loop-convert/LoopActions.cpp b/loop-convert/LoopActions.cpp index 9a2e1cc6..41803c5a 100644 --- a/loop-convert/LoopActions.cpp +++ b/loop-convert/LoopActions.cpp @@ -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 diff --git a/loop-convert/LoopActions.h b/loop-convert/LoopActions.h index 8772ed69..b1bc5581 100644 --- a/loop-convert/LoopActions.h +++ b/loop-convert/LoopActions.h @@ -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 diff --git a/loop-convert/LoopConvert.cpp b/loop-convert/LoopConvert.cpp index eb300897..6e75bbce 100644 --- a/loop-convert/LoopConvert.cpp +++ b/loop-convert/LoopConvert.cpp @@ -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; } diff --git a/loop-convert/LoopMatchers.cpp b/loop-convert/LoopMatchers.cpp index ef3f750c..92602d9d 100644 --- a/loop-convert/LoopMatchers.cpp +++ b/loop-convert/LoopMatchers.cpp @@ -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 diff --git a/loop-convert/LoopMatchers.h b/loop-convert/LoopMatchers.h index 273fd63d..8dfc17e6 100644 --- a/loop-convert/LoopMatchers.h +++ b/loop-convert/LoopMatchers.h @@ -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 diff --git a/loop-convert/StmtAncestor.h b/loop-convert/StmtAncestor.h index 858fa093..9b1ec94d 100644 --- a/loop-convert/StmtAncestor.h +++ b/loop-convert/StmtAncestor.h @@ -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)); diff --git a/loop-convert/VariableNaming.cpp b/loop-convert/VariableNaming.cpp index eb9f9554..89dc4887 100644 --- a/loop-convert/VariableNaming.cpp +++ b/loop-convert/VariableNaming.cpp @@ -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); diff --git a/loop-convert/VariableNaming.h b/loop-convert/VariableNaming.h index 6df9c427..b3bc58e1 100644 --- a/loop-convert/VariableNaming.h +++ b/loop-convert/VariableNaming.h @@ -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 |