Index: CMakeLists.txt =================================================================== --- CMakeLists.txt +++ CMakeLists.txt @@ -1,4 +1,5 @@ add_subdirectory(remove-cstr-calls) +add_subdirectory(loop-convert) # Add the common testsuite after all the tools. add_subdirectory(test) Index: loop-convert/CMakeLists.txt =================================================================== --- /dev/null +++ loop-convert/CMakeLists.txt @@ -0,0 +1,20 @@ +set(LLVM_LINK_COMPONENTS support) +set(LLVM_USED_LIBS clangTooling clangBasic clangAST) + +add_clang_executable(loop-convert + LoopConvert.cpp + LoopActions.cpp + LoopActions.h + LoopMatchers.cpp + LoopMatchers.h + StmtAncestor.cpp + StmtAncestor.h + VariableNaming.cpp + VariableNaming.h + ) + +target_link_libraries(loop-convert + clangTooling + clangBasic + clangASTMatchers + ) Index: loop-convert/LoopActions.h =================================================================== --- /dev/null +++ loop-convert/LoopActions.h @@ -0,0 +1,75 @@ +//===-- loop-convert/LoopActions.h - C++11 For loop migration ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares matchers and callbacks for use in migrating C++ for loops. +// +//===----------------------------------------------------------------------===// +#ifndef _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_LOOPACTIONS_H_ +#define _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_LOOPACTIONS_H_ + +#include "StmtAncestor.h" +#include "clang/Tooling/Refactoring.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/RecursiveASTVisitor.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" + +namespace clang { +namespace loop_migrate { +using clang::ast_matchers::MatchFinder; +using clang::ast_matchers::StatementMatcher; + +/// \brief The level of safety to require of transformations. +enum TranslationConfidenceKind { + TCK_Risky, + TCK_Extra, + TCK_Safe +}; + +enum LoopFixerKind { + LFK_Array, + LFK_Iterator, + LFK_PseudoArray +}; + +/// \brief Argument pack for LoopFixer. +/// +// Contains long-lived data structures that should be preserved across matcher +/// callback runs. +struct LoopFixerArgs { + tooling::Replacements *Replace; + StmtGeneratedVarNameMap *GeneratedDecls; + ReplacedVarsMap *ReplacedVarRanges; + unsigned AcceptedChanges; + unsigned DeferredChanges; + unsigned RejectedChanges; + bool CountOnly; + TranslationConfidenceKind ConfidenceLevel; +}; + +/// LoopFixer: The callback to be used for loop migration matchers. +/// +/// The callback does extra checking not possible in matchers, and attempts to +/// convert the for loop, if possible. + +class LoopFixer : public MatchFinder::MatchCallback { + private: + StmtAncestorASTVisitor *ParentFinder; + LoopFixerArgs *Args; + LoopFixerKind FixerKind; + + public: + LoopFixer(LoopFixerArgs *Args, StmtAncestorASTVisitor *ParentFinder, + LoopFixerKind FixerKind) : + ParentFinder(ParentFinder), Args(Args) , FixerKind(FixerKind) { } + virtual void run(const MatchFinder::MatchResult &Result); +}; + +} // namespace loop_migrate +} // namespace clang +#endif // _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_LOOPACTIONS_H_ Index: loop-convert/LoopActions.cpp =================================================================== --- /dev/null +++ loop-convert/LoopActions.cpp @@ -0,0 +1,772 @@ +#include "LoopActions.h" +#include "LoopMatchers.h" +#include "VariableNaming.h" + +#include "clang/Lex/Lexer.h" + +namespace clang { +namespace loop_migrate { + +using namespace clang::ast_matchers; +using namespace clang::tooling; + +typedef llvm::SmallVector< + std::pair, 1> ContainerResult; + +/// Usage - the information needed to describe a valid convertible usage +/// of an array index or iterator. +struct Usage { + const Expr *E; + bool IsArrow; + /// Range is only used if IsArrow is set to true; + /// otherwise, E->getSourceRange() should be used. + /// This is needed to work around the range of operator-> not being exactly + /// what needs to be replaced. + SourceRange Range; +}; + +// The true return value of ForLoopIndexUseVisitor. +typedef llvm::SmallVector UsageResult; + +/// ForLoopIndexUseVisitor - discover usages of expressions indexing into +/// containers. +/// +/// Given an index variable, recursively crawls a for loop to discover if the +/// index variable is used in a way consistent with range-based for loop access. +class ForLoopIndexUseVisitor + : public RecursiveASTVisitor { + public: + ForLoopIndexUseVisitor(ASTContext *Context, const VarDecl *IndexVar, + const VarDecl *EndVar, const Expr *ContainerExpr, + bool ContainerNeedsDereference) : + OnlyUsedAsIndex(true), Context(Context), IndexVar(IndexVar), + EndVar(EndVar), AliasDecl(NULL), ContainerExpr(ContainerExpr), + ContainerNeedsDereference(ContainerNeedsDereference) { + if (ContainerExpr) { + addComponent(ContainerExpr); + llvm::FoldingSetNodeID ID; + const Expr *E = ContainerExpr->IgnoreParenImpCasts(); + E->Profile(ID, *Context, true); + ContainersIndexed.push_back(std::make_pair(E, ID)); + } + } + + /// Accessor for Usages. + const UsageResult &getUsages() const { return Usages; } + + /// Accessor for ContainersIndexed. + const ContainerResult &getContainersIndexed() const { + return ContainersIndexed; + } + + /// Accessor for ConfidenceLevel. + TranslationConfidenceKind getConfidenceLevel() const { + return ConfidenceLevel; + } + + /// Returns the statement declaring the variable created as an alias for the + /// loop element, if any. + const DeclStmt *getAliasDecl() const { return AliasDecl; } + + /// Add a set of components that we should consider relevant to the container. + void addComponents(const ComponentVector &Components) { + // FIXME: add sort(on ID)+unique to avoid extra work. + for (ComponentVector::const_iterator I = Components.begin(), + E = Components.end(); I != E; ++I) + addComponent(*I); + } + + // 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 as an array index. + // + // The general strategy is to reject any DeclRefExprs referencing IndexVar, + // with the exception of certain acceptable patterns. + // For arrays, the DeclRefExpr for IndexVar must appear as the index of an + // ArraySubscriptExpression. + bool findUsages(const Stmt *Body) { + ConfidenceLevel = TCK_Safe; + TraverseStmt(const_cast(Body)); + return OnlyUsedAsIndex; + } + + private: + bool OnlyUsedAsIndex; + ASTContext *Context; + // A container which holds all usages of IndexVar as the index of + // ArraySubscriptExpressions. + UsageResult Usages; + /// A set which holds expressions containing the referenced arrays. + ContainerResult ContainersIndexed; + /// The index variable's VarDecl. + const VarDecl *IndexVar; + // The loop's 'end' variable, which cannot be mentioned at all. + const VarDecl *EndVar; + // The DeclStmt for an alias to the container element. + const DeclStmt *AliasDecl; + // The Expr which refers to the container. + const Expr *ContainerExpr; + bool ContainerNeedsDereference; + TranslationConfidenceKind ConfidenceLevel; + llvm::SmallVector< + std::pair, 16> DependentExprs; + + void addComponent(const Expr *E) { + llvm::FoldingSetNodeID ID; + const Expr *Node = E->IgnoreParenImpCasts(); + Node->Profile(ID, *Context, true); + DependentExprs.push_back(std::make_pair(Node, ID)); + } + + /// Typedef used in CRTP functions. + typedef RecursiveASTVisitor VisitorBase; + friend class RecursiveASTVisitor; + + /// Overriden methods for RecursiveASTVisitor's traversal. + bool TraverseArraySubscriptExpr(ArraySubscriptExpr *ASE); + bool TraverseCXXMemberCallExpr(CXXMemberCallExpr *MemberCall); + bool TraverseCXXOperatorCallExpr(CXXOperatorCallExpr *OpCall); + bool TraverseMemberExpr(MemberExpr *Member); + bool TraverseUnaryOperator(UnaryOperator *Uop); + bool VisitDeclRefExpr(DeclRefExpr *DRE); + bool VisitDeclStmt(DeclStmt *DS); + // Used to call Traverse...Operator() correctly + bool TraverseStmt(Stmt *S); +}; + +// Obtain the original source code text from a SourceRange. +// FIXME: Maybe put this somewhere more generally accessible? +static StringRef getStringFromRange(SourceManager &SourceMgr, + const LangOptions &LangOpts, + SourceRange Range) { + if (SourceMgr.getFileID(Range.getBegin()) != + SourceMgr.getFileID(Range.getEnd())) + return NULL; + + CharSourceRange SourceChars(Range, true); + return Lexer::getSourceText(SourceChars, SourceMgr, LangOpts); +} + +// Returns the DeclRefExpr represented by E, or NULL if there isn't one. +static const DeclRefExpr *getDeclRef(const Expr *E) { + return dyn_cast(E->IgnoreParenImpCasts()); +} + +// If the given expression is actually a DeclRefExpr, find and return the +// underlying VarDecl; otherwise, return NULL. +static const VarDecl *getReferencedVariable(const Expr *E) { + if (const DeclRefExpr *DRE = getDeclRef(E)) + return dyn_cast(DRE->getDecl()); + return NULL; +} + +// Returns true when the given expression is a direct member expression +static bool isDirectMemberExpr(const Expr *E) { + if (const MemberExpr *Member = dyn_cast(E->IgnoreParenImpCasts())) + return isa(Member->getBase()->IgnoreParenImpCasts()); + return false; +} + +// Returns true when two ValueDecls are the same variable. +static bool areSameVariable(const ValueDecl *First, const ValueDecl *Second) { + return First && Second && + First->getCanonicalDecl() == Second->getCanonicalDecl(); +} + +// Determines if an expression is a declaration reference to a particular +// variable. +static bool exprIsVariable(const ValueDecl *Target, const Expr *E) { + if (!Target || !E) + return false; + const DeclRefExpr *DRE = getDeclRef(E); + return DRE && areSameVariable(Target, DRE->getDecl()); +} + +// Returns true when two Exprs are equivalent. +static bool areSameExpr(ASTContext* Context, const Expr *First, + const Expr *Second) { + if (!First || !Second) + return false; + + llvm::FoldingSetNodeID FirstID, SecondID; + First->Profile(FirstID, *Context, true); + Second->Profile(SecondID, *Context, true); + return FirstID == SecondID; +} + +/// Look through conversion/copy constructors to see the object being converted +/// from, returning it if such an object is found. The point is to look at +/// vector::iterator it = v.begin() +/// and retrieve `v.begin()` as the expression used to initialize `it`. +static const Expr *digThroughConstructors(const Expr *E) { + if (!E) + return NULL; + E = E->IgnoreParenImpCasts(); + if (const CXXConstructExpr *ConstructExpr = dyn_cast(E)) { + // The initial constructor must take exactly one parameter, but base class + // and deferred constructors can take more. + if (ConstructExpr->getNumArgs() != 1 || + ConstructExpr->getConstructionKind() != CXXConstructExpr::CK_Complete) + return NULL; + E = ConstructExpr->getArg(0); + if (const MaterializeTemporaryExpr *MTE = + dyn_cast(E)) + E = MTE->GetTemporaryExpr(); + return digThroughConstructors(E); + } + return E; +} + +// If the expression is a dereference or call to operator*(), return the +// operand. Otherwise, returns NULL. +static const Expr *getDereferenceOperand(const Expr *E) { + if (const UnaryOperator *Uop = dyn_cast(E)) + return Uop->getOpcode() == UO_Deref ? Uop->getSubExpr() : NULL; + + if (const CXXOperatorCallExpr *OpCall = dyn_cast(E)) + return OpCall->getOperator() == OO_Star && OpCall->getNumArgs() == 1 ? + OpCall->getArg(0) : NULL; + + return NULL; +} + +// Returns true when the ContainerResult contains an Expr equivalent to E. +template +static bool containsExpr(ASTContext *Context, const ContainerT *Container, + const Expr *E) { + llvm::FoldingSetNodeID ID; + E->Profile(ID, *Context, true); + for (typename ContainerT::const_iterator I = Container->begin(), + End = Container->end(); I != End; ++I) + if (ID == I->second) + return true; + return false; +} + +// Returns true when the index expression is a declaration reference to +// IndexVar and the array's base exists. +static bool isIndexInSubscriptExpr(const Expr *IndexExpr, + const VarDecl *IndexVar, + const Expr *Arr) { + const DeclRefExpr *Idx = getDeclRef(IndexExpr); + return Arr && Idx && Idx->getType()->isIntegerType() + && areSameVariable(IndexVar, Idx->getDecl()); +} + +// Returns true when the index expression is a declaration reference to +// IndexVar, Obj is the same expression as SourceExpr after all parens and +// implicit casts are stirpped off. +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)) + return false; + + if (areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(), + Obj->IgnoreParenImpCasts())) + return true; + + if (const Expr *InnerObj = getDereferenceOperand(Obj->IgnoreParenImpCasts())) + if (PermitDeref && areSameExpr(Context, SourceExpr->IgnoreParenImpCasts(), + InnerObj->IgnoreParenImpCasts())) + return true; + + return false; +} + +// Returns true when Opcall is a call a one-parameter operator on IndexVar. +// Note that this function assumes that the opcode is operator* or operator->. +static bool isValidDereference(const CXXOperatorCallExpr *OpCall, + const VarDecl *IndexVar) { + return OpCall->getNumArgs() == 1 && + exprIsVariable(IndexVar, OpCall->getArg(0)); +} + +// 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*). +static bool isValidUop(const UnaryOperator *Uop, const VarDecl *IndexVar) { + return Uop->getOpcode() == UO_Deref && + exprIsVariable(IndexVar, Uop->getSubExpr()); +} + +// Determines whether the given Decl defines an alias to the given variable. +static bool isAliasDecl(const Decl *TheDecl, const VarDecl *TargetDecl) { + const VarDecl *VDecl = dyn_cast(TheDecl); + if (!VDecl) + return false; + + if (!VDecl->hasInit()) + return false; + const Expr *Init = + digThroughConstructors(VDecl->getInit()->IgnoreImpCasts()); + + switch (Init->getStmtClass()) { + case Stmt::ArraySubscriptExprClass: { + const ArraySubscriptExpr *ASE = cast(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()); + } + + case Stmt::UnaryOperatorClass: + return isValidUop(cast(Init), TargetDecl); + + case Stmt::CXXOperatorCallExprClass: { + const CXXOperatorCallExpr *OpCall = cast(Init); + if (OpCall->getOperator() == OO_Star) + return isValidDereference(OpCall, TargetDecl); + break; + } + + default: + break; + } + return false; +} + +// Determines whether the bound of a for loop condition expression is the same +// as the statically computable size of ArrayType. +static bool arrayMatchesBoundExpr(ASTContext *Context, + const QualType &ArrayType, + const Expr *ConditionExpr) { + const Type *T = ArrayType.getCanonicalType().getTypePtr(); + if (const ConstantArrayType *CAT = dyn_cast(T)) { + llvm::APSInt ConditionSize; + if (!ConditionExpr->isIntegerConstantExpr(ConditionSize, *Context)) + return false; + llvm::APSInt ArraySize(CAT->getSize()); + return llvm::APSInt::isSameValue(ConditionSize, ArraySize); + } + return false; +} + +// A workaround to allow a redefinition of Traverse...Operator. +bool ForLoopIndexUseVisitor::TraverseStmt(Stmt *S) { + // Without this, an assert is triggered somewhere in RecursiveASTVisitor. + if (!S) + return true; + + switch (S->getStmtClass()) { + case Stmt::UnaryOperatorClass: + return TraverseUnaryOperator(cast(S)); + default: + return VisitorBase::TraverseStmt(S); + } +} + +// Traverses the subexpression of Uop. Permitted usages here are dereferences of +// pointer types. +bool ForLoopIndexUseVisitor::TraverseUnaryOperator(UnaryOperator *Uop) { + // If we dereference an iterator that's actually a pointer, count the + // occurrence. + if (isValidUop(Uop, IndexVar)) { + Usage U = {Uop, /*IsArrow=*/false, SourceRange()}; + Usages.push_back(U); + return true; + } + + // Otherwise, continue recursively. + return TraverseStmt(Uop->getSubExpr()); +} + +/// Arrow expressions are okay in iterator loops, so we note them +/// for conversion. +bool ForLoopIndexUseVisitor::TraverseMemberExpr(MemberExpr *Member) { + const Expr *Base = Member->getBase(); + const DeclRefExpr *Obj = getDeclRef(Base); + const Expr *ResultExpr = Member; + QualType ExprType; + if (const CXXOperatorCallExpr *Call = + dyn_cast(Base->IgnoreParenImpCasts())) { + // If operator->() is a MemberExpr containing a CXXOperatorCallExpr, then + // the MemberExpr does not have the expression we want. We therefore catch + // that instance here. + if(Call->getOperator() == OO_Arrow) { + assert(Call->getNumArgs() == 1 && + "Operator-> takes more than one argument"); + Obj = getDeclRef(Call->getArg(0)); + ResultExpr = Obj; + ExprType = Call->getCallReturnType(); + } + } + + if (Member->isArrow() && Obj && exprIsVariable(IndexVar, Obj)) { + if (ExprType.isNull()) + ExprType = Obj->getType(); + + assert(ExprType->isPointerType() && "Operator-> returned non-pointer type"); + // FIXME: This works around not having the location of the arrow operator. + // Consider adding OperatorLoc to MemberExpr? + SourceLocation ArrowLoc = + Lexer::getLocForEndOfToken(Base->getExprLoc(), 0, + Context->getSourceManager(), + Context->getLangOpts()); + // If something complicated is happening (i.e. the next token isn't an + // arrow), give up on making this work. + if (!ArrowLoc.isInvalid()) { + Usage U = {ResultExpr, /*IsArrow=*/true, + SourceRange(Base->getExprLoc(), ArrowLoc)}; + Usages.push_back(U); + return true; + } + } + return TraverseStmt(Member->getBase()); +} + +// Calls on the iterator object are not permitted, unless done through +// operator->(). The one exception is allowing vector::at() for pseudoarrays. +// We also treat the base object as being an rvalue if the member function is +// const. +bool ForLoopIndexUseVisitor::TraverseCXXMemberCallExpr( + CXXMemberCallExpr *MemberCall) { + MemberExpr *Member = cast(MemberCall->getCallee()); + // We specifically allow an accessor named "at" to let STL in, though + // this is restricted to pseudo-arrays by requiring a single, integer + // argument. + const IdentifierInfo *Ident = Member->getMemberDecl()->getIdentifier(); + if (Ident->isStr("at") && MemberCall->getNumArgs() == 1) { + if (isIndexInSubscriptExpr(Context, MemberCall->getArg(0), IndexVar, + Member->getBase(), ContainerExpr, + ContainerNeedsDereference)) { + Usage U = {MemberCall, /*IsArrow=*/false, SourceRange()}; + Usages.push_back(U); + return true; + } + } + + if (containsExpr(Context, &DependentExprs, Member->getBase())) + ConfidenceLevel = std::min(ConfidenceLevel, TCK_Risky); + + bool BaseResult = TraverseMemberExpr(Member); + for (unsigned I = 0; I < MemberCall->getNumArgs(); ++I) + BaseResult = BaseResult && TraverseStmt(MemberCall->getArg(I)); + return BaseResult; +} + +// Overloaded operator* and operator-> are permitted for iterator-based loops. +bool ForLoopIndexUseVisitor::TraverseCXXOperatorCallExpr( + CXXOperatorCallExpr *OpCall) { + switch (OpCall->getOperator()) { + case OO_Star: + if (isValidDereference(OpCall, IndexVar)) { + Usage U = {OpCall, /*IsArrow=*/false, SourceRange()}; + Usages.push_back(U); + return true; + } + break; + + case OO_Arrow: + if (isValidDereference(OpCall, IndexVar)) { + Usage U = {OpCall, /*IsArrow=*/true, + SourceRange(OpCall->getLocStart(), OpCall->getOperatorLoc())}; + Usages.push_back(U); + return true; + } + + case OO_Subscript: + if (OpCall->getNumArgs() != 2) + break; + if (isIndexInSubscriptExpr(Context, OpCall->getArg(1), IndexVar, + OpCall->getArg(0), ContainerExpr, + ContainerNeedsDereference)) { + Usage U = {OpCall, /*IsArrow=*/false, SourceRange()}; + Usages.push_back(U); + return true; + } + break; + + default: + break; + } + return VisitorBase::TraverseCXXOperatorCallExpr(OpCall); +} + +// If we encounter an array with IndexVar as the index, note it and prune the +// AST traversal so that VisitDeclRefExpr() doesn't discover the reference to +// the index and mark it as unconvertible. +// Otherwise, continue the traversal recursively. +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)); + } + Usage U = {ASE, /*IsArrow=*/false, SourceRange()}; + Usages.push_back(U); + return true; + } + return VisitorBase::TraverseArraySubscriptExpr(ASE); +} + +// If we encounter a reference to IndexVar in an unpruned branch of the +// traversal, mark this loop as unconvertible. +bool ForLoopIndexUseVisitor::VisitDeclRefExpr(DeclRefExpr *DRE) { + const ValueDecl *TheDecl = DRE->getDecl(); + if (areSameVariable(IndexVar, TheDecl) || areSameVariable(EndVar, TheDecl)) + OnlyUsedAsIndex = false; + if (containsExpr(Context, &DependentExprs, DRE)) + ConfidenceLevel = std::min(ConfidenceLevel, TCK_Risky); + return true; +} + +// If we find that another variable is created just to refer to the loop +// element, we can reuse it as the loop variable. +bool ForLoopIndexUseVisitor::VisitDeclStmt(DeclStmt *DS) { + if (!AliasDecl && DS->isSingleDecl() && + isAliasDecl(DS->getSingleDecl(), IndexVar)) + AliasDecl = DS; + return true; +} + +// Apply the source transformations necessary to migrate the loop! +static void doConversion(ASTContext *Context, LoopFixerArgs *Args, + const StmtParentMap *ParentMap, + const VarDecl *IndexVar, const VarDecl *EndVar, + const Expr *ContainerExpr, + const UsageResult &Usages, const DeclStmt *AliasDecl, + const ForStmt *TheLoop, + bool ContainerNeedsDereference) { + const VarDecl *MaybeContainer = getReferencedVariable(ContainerExpr); + std::string VarName; + + if (Usages.size() == 1 && AliasDecl) { + const VarDecl *AliasVar = cast(AliasDecl->getSingleDecl()); + VarName = AliasVar->getName().str(); + // We keep along the entire DeclStmt to keep the correct range here. + const SourceRange &ReplaceRange = AliasDecl->getSourceRange(); + if (!Args->CountOnly) + Args->Replace->insert( + Replacement(Context->getSourceManager(), + CharSourceRange::getTokenRange(ReplaceRange), "")); + // 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, Args->GeneratedDecls, ParentMap, + IndexVar->getDeclContext(), 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; + SourceRange ReplaceRange; + if (I->IsArrow) { + ReplaceRange = I->Range; + ReplaceText = VarName + "."; + } else { + ReplaceRange = I->E->getSourceRange(); + ReplaceText = VarName; + } + Args->ReplacedVarRanges->insert(std::make_pair(TheLoop, IndexVar)); + if (!Args->CountOnly) + Args->Replace->insert( + Replacement(Context->getSourceManager(), + CharSourceRange::getTokenRange(ReplaceRange), + ReplaceText)); + } + } + + // Now, we need to construct the new range expresion. + SourceRange ParenRange(TheLoop->getLParenLoc(), TheLoop->getRParenLoc()); + StringRef ContainerString = + getStringFromRange(Context->getSourceManager(), Context->getLangOpts(), + ContainerExpr->getSourceRange()); + + QualType AutoRefType = + Context->getLValueReferenceType(Context->getAutoDeductType()); + + std::string MaybeDereference = ContainerNeedsDereference ? "*" : ""; + std::string TypeString = AutoRefType.getAsString(); + std::string Range = ("(" + TypeString + " " + VarName + " : " + + MaybeDereference + ContainerString + ")").str(); + if (!Args->CountOnly) + Args->Replace->insert(Replacement(Context->getSourceManager(), + CharSourceRange::getTokenRange(ParenRange), + Range)); + Args->GeneratedDecls->insert(make_pair(TheLoop, VarName)); +} + +/// Determine whether VDecl appears to be an initializing an iterator. +/// 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) { + // FIXME: Maybe allow declaration/initialization outside of the for loop? + const CXXMemberCallExpr *TheCall = + dyn_cast_or_null(digThroughConstructors(Init)); + if (!TheCall || TheCall->getNumArgs() != 0) + return NULL; + + const MemberExpr *Member = cast(TheCall->getCallee()); + const std::string Name = Member->getMemberDecl()->getName(); + const std::string TargetName = IsBegin ? "begin" : "end"; + if (Name != TargetName) + return NULL; + + const Expr *SourceExpr = Member->getBase(); + if (!SourceExpr) + return NULL; + + *IsArrow = Member->isArrow(); + return SourceExpr; +} + +/// Determines the variable 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, + 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) + return NULL; + const Expr *EndSourceExpr = getContainerFromInitializer(EndInitExpr, + /*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)) + return NULL; + + *ContainerNeedsDereference = BeginIsArrow; + return ContainerExpr; +} + +// 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) { + TranslationConfidenceKind ConfidenceLevel = TCK_Safe; + ASTContext *Context = Result.Context; + const ForStmt *TheLoop = Result.Nodes.getStmtAs(LoopName); + + if (!Context->getSourceManager().isFromMainFile(TheLoop->getForLoc())) + return; + + const VarDecl *LoopVar = Result.Nodes.getDeclAs(IncrementVarName); + const VarDecl *CondVar = Result.Nodes.getDeclAs(ConditionVarName); + const VarDecl *InitVar = Result.Nodes.getDeclAs(InitVarName); + + if (!areSameVariable(LoopVar, CondVar) || !areSameVariable(LoopVar, InitVar)) + return; + const Expr *BoundExpr= Result.Nodes.getStmtAs(ConditionBoundName); + const VarDecl *EndVar = Result.Nodes.getDeclAs(EndVarName); + const Expr *ContainerExpr = NULL; + + // 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(EndCallName); + + // If the loop calls end()/size() after each iteration, lower our confidence + // level. + if (FixerKind != LFK_Array && !EndVar) { + if (!EndCall) + return; + ConfidenceLevel = std::min(ConfidenceLevel, TCK_Extra); + } + + 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(EndCall->getCallee())->isArrow(); + } + + ForLoopIndexUseVisitor Finder(Context, LoopVar, EndVar, ContainerExpr, + ContainerNeedsDereference); + + // Either a container or an integral upper bound must exist. + if (ContainerExpr) { + ComponentFinderASTVisitor ComponentFinder; + ComponentFinder.findExprComponents(ContainerExpr->IgnoreParenImpCasts()); + Finder.addComponents(ComponentFinder.getComponents()); + } else if (!BoundExpr) + return; + + // Either a container or an integral upper bound must exist. + if (!Finder.findUsages(TheLoop->getBody())) + return; + + const ContainerResult &ContainersIndexed = Finder.getContainersIndexed(); + if (ContainersIndexed.size() != 1) + return; + + ConfidenceLevel = std::min(ConfidenceLevel, 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 = ContainersIndexed.begin()->first; + if (!arrayMatchesBoundExpr(Context, ContainerExpr->getType(), BoundExpr)) + return; + // 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. + if (!getReferencedVariable(ContainerExpr) && + !isDirectMemberExpr(ContainerExpr)) + ConfidenceLevel = std::min(ConfidenceLevel, TCK_Risky); + } + + // If we already modified the range of this for loop, don't do any further + // updates on this iteration. + // FIXME: Once Replacements can detect conflicting edits, replace this + // implementation and rely on conflicting edit detection instead. + if (Args->ReplacedVarRanges->count(TheLoop)) { + Args->DeferredChanges++; + return; + } + + ParentFinder->gatherAncestors(Context->getTranslationUnitDecl(), + /*RunEvenIfNotEmpty=*/false); + + // 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(), + Args->ReplacedVarRanges, TheLoop); + // Not all of these are actually deferred changes. + // FIXME: Determine when the external dependency isn't an expression converted + // by another loop. + if (DependencyFinder.dependsOnOutsideVariable(ContainerExpr)) { + Args->DeferredChanges++; + return; + } + + if (ConfidenceLevel < Args->ConfidenceLevel) { + Args->RejectedChanges++; + return; + } + + doConversion(Context, Args, &ParentFinder->getStmtToParentStmtMap(), + LoopVar, EndVar, ContainerExpr, Finder.getUsages(), + Finder.getAliasDecl(), TheLoop, ContainerNeedsDereference); + + Args->AcceptedChanges++; +} + +} // namespace loop_migrate +} // namespace clang Index: loop-convert/LoopConvert.cpp =================================================================== --- /dev/null +++ loop-convert/LoopConvert.cpp @@ -0,0 +1,134 @@ +//===-- loop-convert/LoopConvert.cpp - C++11 For loop migration -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a tool that migrates for loops to take advantage of the +// range-basead syntax new to C++11. +// +// Usage: +// loop-convert ... +// +// Where is a CMake build directory containing a file named +// compile_commands.json. +// +// ... specify the pahs of files in the CMake source tree, with the same +// requirements as other tools built on LibTooling. +// +//===----------------------------------------------------------------------===// + +#include "LoopActions.h" +#include "LoopMatchers.h" + +#include "clang/Basic/FileManager.h" +#include "clang/Frontend/CompilerInstance.h" +#include "clang/Frontend/FrontendActions.h" +#include "clang/Tooling/Tooling.h" +#include "clang/Tooling/Refactoring.h" + +using clang::ast_matchers::MatchFinder; +namespace cl = llvm::cl; +using namespace clang::tooling; +using namespace clang::loop_migrate; + +static cl::opt BuildPath( + cl::Positional, + cl::desc("")); + +static cl::list SourcePaths( + cl::Positional, + cl::desc(" [... ]"), + cl::OneOrMore); + +// General options go here: +static cl::opt CountOnly( + "count-only", cl::desc("Do not apply transformations; only count them.")); + +static cl::opt TransformationLevel( + cl::desc("Choose safety requirements for transformations:"), + cl::values(clEnumValN(TCK_Safe, "A0", "Enable safe transformations"), + clEnumValN(TCK_Extra, "A1", + "Enable transformations that might change semantics " + "(default)"), + clEnumValN(TCK_Risky, "A2", + "Enable transformations that are likely " + "to change semantics"), + clEnumValEnd), + cl::init(TCK_Extra)); + +int main(int argc, const char **argv) { + // Adjust arguments to force compilation in C++11 mode. + int NumArgs = argc + 1; + const char **Args = new const char *[NumArgs]; + for (int I = 0; I < argc; ++I) + Args[I] = argv[I]; + Args[NumArgs - 1] = "-std=c++11"; + llvm::OwningPtr Compilations( + FixedCompilationDatabase::loadFromCommandLine(NumArgs, Args)); + cl::ParseCommandLineOptions(NumArgs, Args); + if (!Compilations) { + std::string ErrorMessage; + Compilations.reset( + !BuildPath.empty() ? + CompilationDatabase::autoDetectFromDirectory(BuildPath, ErrorMessage) : + CompilationDatabase::autoDetectFromSource(SourcePaths[0], + ErrorMessage)); + if (!Compilations) + llvm::report_fatal_error(ErrorMessage); + } + ClangTool SyntaxTool(*Compilations, SourcePaths); + + // First, let's check to make sure there were no errors. + if (int result = SyntaxTool.run( + newFrontendActionFactory())) { + llvm::errs() << "Error compiling files.\n"; + return result; + } + + RefactoringTool LoopTool(*Compilations, SourcePaths); + StmtAncestorASTVisitor ParentFinder; + StmtGeneratedVarNameMap GeneratedDecls; + ReplacedVarsMap ReplacedVars; + LoopFixerArgs FixerArgs = {&LoopTool.getReplacements(), &GeneratedDecls, + &ReplacedVars, /*AcceptedChanges=*/0, + /*DeferredChanges=*/0, /*RejectedChanges=*/0, + CountOnly, TransformationLevel}; + MatchFinder Finder; + LoopFixer ArrayLoopFixer(&FixerArgs, &ParentFinder, LFK_Array); + Finder.addMatcher(makeArrayLoopMatcher(), &ArrayLoopFixer); + LoopFixer IteratorLoopFixer(&FixerArgs, &ParentFinder, LFK_Iterator); + Finder.addMatcher(makeIteratorLoopMatcher(), &IteratorLoopFixer); + LoopFixer PseudoarrrayLoopFixer(&FixerArgs, &ParentFinder, LFK_PseudoArray); + Finder.addMatcher(makePseudoArrayLoopMatcher(), &PseudoarrrayLoopFixer); + if (int result = LoopTool.run(newFrontendActionFactory(&Finder))) { + llvm::errs() << "Error encountered during translation.\n"; + return result; + } + + llvm::outs() << "\nFor Loop Conversion:\n\t" << FixerArgs.AcceptedChanges + << " converted loop(s)\n\t" << FixerArgs.DeferredChanges + << " potentially conflicting change(s) deferred.\n\t" + << FixerArgs.RejectedChanges << " change(s) rejected.\n"; + if (FixerArgs.DeferredChanges > 0) + llvm::outs() << "Re-run this tool to attempt applying deferred changes.\n"; + if (FixerArgs.RejectedChanges > 0) + llvm::outs() << "Re-run this tool with a lower required confidence level " + "to apply rejected changes.\n"; + + if (FixerArgs.AcceptedChanges > 0) { + // Check to see if the changes introduced any new errors. + ClangTool EndSyntaxTool(*Compilations, SourcePaths); + if (int result = EndSyntaxTool.run( + newFrontendActionFactory())) { + llvm::errs() << "Error compiling files after translation.\n"; + return result; + } + } + + delete[] Args; + return 0; +} Index: loop-convert/LoopMatchers.h =================================================================== --- /dev/null +++ loop-convert/LoopMatchers.h @@ -0,0 +1,38 @@ +//===-- loop-convert/LoopMatchers.h - Matchers for for loops ----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains declarations of the matchers for use in migrating +// C++ for loops. +// +//===----------------------------------------------------------------------===// +#ifndef _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_LOOP_MATCHERS_H_ +#define _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_LOOP_MATCHERS_H_ + +#include "clang/ASTMatchers/ASTMatchers.h" + +namespace clang { +namespace loop_migrate { + +// Constants used for matcher name bindings +extern const char LoopName[]; +extern const char ConditionBoundName[]; +extern const char ConditionVarName[]; +extern const char IncrementVarName[]; +extern const char InitVarName[]; +extern const char EndExprName[]; +extern const char EndCallName[]; +extern const char EndVarName[]; + +ast_matchers::StatementMatcher makeArrayLoopMatcher(); +ast_matchers::StatementMatcher makeIteratorLoopMatcher(); +ast_matchers::StatementMatcher makePseudoArrayLoopMatcher(); +} //namespace loop_migrate +} //namespace clang + +#endif //_LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_LOOP_MATCHERS_H_ Index: loop-convert/LoopMatchers.cpp =================================================================== --- /dev/null +++ loop-convert/LoopMatchers.cpp @@ -0,0 +1,144 @@ +#include "LoopMatchers.h" + +namespace clang { +namespace loop_migrate { + +using namespace clang::ast_matchers; +const char LoopName[] = "forLoop"; +const char ConditionBoundName[] = "conditionBound"; +const char ConditionVarName[] = "conditionVar"; +const char IncrementVarName[] = "incrementVar"; +const char InitVarName[] = "initVar"; +const char EndCallName[] = "endCall"; +const char EndVarName[] = "endVar"; + +static const TypeMatcher AnyType = anything(); + +// FIXME: How best to document complicated matcher expressions? They're fairly +// self-documenting...but there may be some unintuitive parts. + +StatementMatcher makeArrayLoopMatcher() { + static StatementMatcher LHSMatcher = + expression(ignoringImpCasts(declarationReference(to( + variable(hasType(isInteger())).bind(ConditionVarName))))); + static StatementMatcher RHSMatcher = + expression(hasType(isInteger())).bind(ConditionBoundName); + + return id(LoopName, forStmt( + hasLoopInit(declarationStatement(hasSingleDecl(id(InitVarName, variable( + hasInitializer(ignoringImpCasts(integerLiteral(equals(0))))))))), + hasCondition(binaryOperator(hasOperatorName("<"), + hasLHS(LHSMatcher), + hasRHS(RHSMatcher))), + hasIncrement(unaryOperator( + hasOperatorName("++"), + hasUnaryOperand(declarationReference(to( + variable(hasType(isInteger())).bind(IncrementVarName)))))))); +} + +// The matcher used for for loops. +StatementMatcher makeIteratorLoopMatcher() { + StatementMatcher BeginCallMatcher = + memberCall(argumentCountIs(0), callee(method(hasName("begin")))); + + DeclarationMatcher InitDeclMatcher = + variable(hasInitializer(anything())).bind(InitVarName); + + DeclarationMatcher EndDeclMatcher = + variable(hasInitializer(anything())).bind(EndVarName); + + StatementMatcher EndCallMatcher = + memberCall(argumentCountIs(0), callee(method(hasName("end")))); + + StatementMatcher IteratorBoundMatcher = + expression(anyOf(ignoringParenImpCasts(declarationReference(to( + variable().bind(EndCallName)))), + ignoringParenImpCasts( + expression(EndCallMatcher).bind(EndCallName)), + materializeTemporaryExpression( + ignoringParenImpCasts( + expression(EndCallMatcher).bind(EndCallName))))); + + StatementMatcher IteratorComparisonMatcher = + expression(ignoringParenImpCasts(declarationReference(to( + variable().bind(ConditionVarName))))); + + StatementMatcher OverloadedNEQMatcher = overloadedOperatorCall( + hasOverloadedOperatorName("!="), + argumentCountIs(2), + 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))))))))); +} + +// The matcher used for array-like containers. +StatementMatcher makePseudoArrayLoopMatcher() { + DeclarationMatcher InitDeclMatcher = + variable(hasInitializer(ignoringParenImpCasts( + integerLiteral(equals(0))))).bind(InitVarName); + StatementMatcher SizeCallMatcher = + memberCall(argumentCountIs(0), callee(method(hasName("size")))); + + StatementMatcher EndInitMatcher = + expression(anyOf( + ignoringParenImpCasts(expression(SizeCallMatcher).bind(EndCallName)), + explicitCast(hasSourceExpression(ignoringParenImpCasts( + expression(SizeCallMatcher).bind(EndCallName)))))); + + DeclarationMatcher EndDeclMatcher = + variable(hasInitializer(EndInitMatcher)).bind(EndVarName); + + StatementMatcher IntegerComparisonMatcher = + expression(ignoringParenImpCasts(declarationReference(to( + variable(hasType(isInteger())).bind(ConditionVarName))))); + + StatementMatcher ArrayBoundMatcher = + expression(anyOf( + ignoringParenImpCasts(declarationReference(to( + variable(hasType(isInteger())).bind(EndCallName)))), + EndInitMatcher)); + + return id(LoopName, forStmt( + hasLoopInit(anyOf( + declarationStatement(declCountIs(2), + containsDeclaration(0, InitDeclMatcher), + containsDeclaration(1, EndDeclMatcher)), + declarationStatement(hasSingleDecl(InitDeclMatcher)))), + hasCondition(anyOf( + binaryOperator(hasOperatorName("<"), + hasLHS(IntegerComparisonMatcher), + hasRHS(ArrayBoundMatcher)), + binaryOperator(hasOperatorName(">"), + hasLHS(ArrayBoundMatcher), + hasRHS(IntegerComparisonMatcher)))), + hasIncrement(unaryOperator( + hasOperatorName("++"), + hasUnaryOperand(declarationReference(to( + variable(hasType(isInteger())).bind(IncrementVarName)))))))); +} + +} // namespace loop_migrate +} // namespace clang Index: loop-convert/StmtAncestor.h =================================================================== --- /dev/null +++ loop-convert/StmtAncestor.h @@ -0,0 +1,169 @@ +//===-- loop-convert/StmtAncestor.h - AST property visitors -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains the declaration several RecursiveASTVisitors used to build +// and check data structures used in loop migration. +// +//===----------------------------------------------------------------------===// +#ifndef _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_STMT_ANCESTOR_H_ +#define _LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_STMT_ANCESTOR_H_ +#include "clang/AST/RecursiveASTVisitor.h" + +namespace clang { +namespace loop_migrate { + +// A map used to walk the AST in reverse: maps child Stmt to parent Stmt. +typedef llvm::DenseMap StmtParentMap; +// A map used to walk the AST in reverse: +// maps VarDecl to the to parent DeclStmt. +typedef llvm::DenseMap 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 ReplacedVarsMap; +// A map used to remember the variable names generated in a Stmt +typedef llvm::DenseMap StmtGeneratedVarNameMap; +// A vector used to store the AST subtrees of an Expr. +typedef llvm::SmallVector ComponentVector; + +/// \brief Class used build the reverse AST properties needed to detect +/// name conflicts and free variables. +class StmtAncestorASTVisitor : + public RecursiveASTVisitor { + public: + StmtAncestorASTVisitor() { + StmtStack.push_back(NULL); + } + + /// \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()) { + TraverseDecl(const_cast(TUD)); + } + } + + /// Accessor for StmtAncestors. + const StmtParentMap &getStmtToParentStmtMap() { + return StmtAncestors; + } + + /// Accessor for DeclParents. + const DeclParentMap &getDeclToParentStmtMap() { + return DeclParents; + } + + friend class RecursiveASTVisitor; + + private: + StmtParentMap StmtAncestors; + DeclParentMap DeclParents; + llvm::SmallVector StmtStack; + + bool TraverseStmt(Stmt *Statement); + bool VisitDeclStmt(DeclStmt *Statement); +}; + +/// Class used to find the variables and member expressions on which an +/// arbitrary expression depends. +class ComponentFinderASTVisitor : + public RecursiveASTVisitor { + public: + ComponentFinderASTVisitor() { } + + /// Find the components of an expression and place them in a ComponentVector. + void findExprComponents(const Expr *SourceExpr) { + Expr *E = const_cast(SourceExpr); + RecursiveASTVisitor::TraverseStmt(E); + } + + /// Accessor for Components. + const ComponentVector &getComponents() { + return Components; + } + + friend class RecursiveASTVisitor; + + private: + ComponentVector Components; + + bool VisitDeclRefExpr(DeclRefExpr *E); + bool VisitMemberExpr(MemberExpr *Member); +}; + +/// Class used to determine if an expression is dependent on a variable declared +/// inside of the loop where it would be used. +class DependencyFinderASTVisitor : + public RecursiveASTVisitor { + public: + DependencyFinderASTVisitor(const StmtParentMap *StmtParents, + const DeclParentMap *DeclParents, + const ReplacedVarsMap *ReplacedVars, + const Stmt *ContainingStmt) : + 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. + bool dependsOnOutsideVariable(const Stmt *Body) { + DependsOnOutsideVariable = false; + TraverseStmt(const_cast(Body)); + return DependsOnOutsideVariable; + } + + friend class RecursiveASTVisitor; + + private: + const StmtParentMap *StmtParents; + const DeclParentMap *DeclParents; + const Stmt *ContainingStmt; + const ReplacedVarsMap *ReplacedVars; + bool DependsOnOutsideVariable; + + bool VisitVarDecl(VarDecl *VD); + bool VisitDeclRefExpr(DeclRefExpr *DRE); +}; + +/// Class used to determine if any declarations used in a Stmt would conflict +/// with a particular identifier. This search includes the names that don't +/// actually appear in the AST (i.e. created by a refactoring tool) by including +/// a map from Stmts to generated names associated with those stmts. +class DeclFinderASTVisitor : public RecursiveASTVisitor { + public: + DeclFinderASTVisitor(const std::string &Name, + const StmtGeneratedVarNameMap *GeneratedDecls) : + Name(Name), GeneratedDecls(GeneratedDecls), Found(false) { } + + /// Attempts to find any usages of variables name Name in Body, returning + /// true when it is used in Body. This includes the generated loop variables + /// of ForStmts which have already been transformed. + bool findUsages(const Stmt *Body) { + Found = false; + TraverseStmt(const_cast(Body)); + return Found; + } + + friend class RecursiveASTVisitor; + + private: + std::string Name; + // GeneratedDecls keeps track of ForStmts which have been tranformed, mapping + // each modified ForStmt to the variable generated in the loop. + const StmtGeneratedVarNameMap *GeneratedDecls; + bool Found; + + bool VisitForStmt(ForStmt *FS); + bool VisitNamedDecl(NamedDecl *ND); + bool VisitDeclRefExpr(DeclRefExpr *DRE); +}; + +} // namespace for_migrate +} // namespace clang +#endif //_LLVM_TOOLS_CLANG_TOOLS_LOOP_CONVERT_STMT_ANCESTOR_H_ Index: loop-convert/StmtAncestor.cpp =================================================================== --- /dev/null +++ loop-convert/StmtAncestor.cpp @@ -0,0 +1,101 @@ +#include "StmtAncestor.h" + +namespace clang { +namespace loop_migrate { + +// All this really does is inject push_back() before running +// RecursiveASTVisitor::TraverseStmt() and pop_back() afterwards. The Stmt atop +// the stack is the parent of the current statement (NULL for the topmost +// statement). +bool StmtAncestorASTVisitor::TraverseStmt(Stmt *Statement) { + StmtAncestors.insert(std::make_pair(Statement, StmtStack.back())); + StmtStack.push_back(Statement); + RecursiveASTVisitor::TraverseStmt(Statement); + StmtStack.pop_back(); + return true; +} + +// Keep track of the DeclStmt associated with each VarDecl. Combined with +// StmtAncestors, this provides roughly the same information as Scope, as we can +// map a VarDecl to its DeclStmt, then walk up the parent tree using +// StmtAncestors. +bool StmtAncestorASTVisitor::VisitDeclStmt(DeclStmt *Decls) { + for (DeclStmt::const_decl_iterator I = Decls->decl_begin(), + E = Decls->decl_end(); I != E; ++I) + if (const VarDecl *VD = dyn_cast(*I)) + DeclParents.insert(std::make_pair(VD, Decls)); + return true; +} + +bool ComponentFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *E) { + Components.push_back(E); + return true; +} + +bool ComponentFinderASTVisitor::VisitMemberExpr(MemberExpr *Member) { + Components.push_back(Member); + return true; +} + +// Just forward any DeclRefExprs to a check on the actual variable declaration. +bool DependencyFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DRE) { + if (VarDecl *VD = dyn_cast_or_null(DRE->getDecl())) + return VisitVarDecl(VD); + return true; +} + +// Determine if any this variable is declared inside the ContainingStmt. +bool DependencyFinderASTVisitor::VisitVarDecl(VarDecl *VD) { + const Stmt *Curr = DeclParents->lookup(VD); + // First, see if the variable was declared within an inner scope of the loop. + while (Curr != NULL) { + if (Curr == ContainingStmt) { + DependsOnOutsideVariable = true; + return false; + } + Curr = StmtParents->lookup(Curr); + } + + // Next, check if the variable was removed from existence by an earlier + // iteration. + for (ReplacedVarsMap::const_iterator I = ReplacedVars->begin(), + E = ReplacedVars->end(); I != E; ++I) + if ((*I).second == VD) { + DependsOnOutsideVariable = true; + return false; + } + return true; +} + +// If we already created a variable for TheLoop, check to make sure that the +// name was not already taken. +bool DeclFinderASTVisitor::VisitForStmt(ForStmt *TheLoop) { + StmtGeneratedVarNameMap::const_iterator I = GeneratedDecls->find(TheLoop); + if (I != GeneratedDecls->end() && I->second == Name) { + Found = true; + return false; + } + return true; +} + +// If any named declaration has the same name, then consider Name already spoken +// for. +bool DeclFinderASTVisitor::VisitNamedDecl(NamedDecl *ND) { + const IdentifierInfo *Ident = ND->getIdentifier(); + if (Ident && Ident->getName() == Name) { + Found = true; + return false; + } + return true; +} + +// Forward any declaration references to the actual check on the referenced +// declaration. +bool DeclFinderASTVisitor::VisitDeclRefExpr(DeclRefExpr *DRE) { + if (NamedDecl *ND = dyn_cast_or_null(DRE->getDecl())) + return VisitNamedDecl(ND); + return true; +} + +} // namespace clang +} // namespace for_migrate Index: loop-convert/VariableNaming.h =================================================================== --- /dev/null +++ loop-convert/VariableNaming.h @@ -0,0 +1,63 @@ +//===-- loop-convert/VariableNaming.h - Gererate variable names -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file contains the declaration of the VariableNamer class, which is +// responsible for generating new variable names and ensuring that they do not +// conflict with existing ones. +// +//===----------------------------------------------------------------------===// +#ifndef _LLVM_TOOLS_CLANG_TOOLS_LOOP_VARIABLE_NAMING_H_ +#define _LLVM_TOOLS_CLANG_TOOLS_LOOP_VARIABLE_NAMING_H_ + +#include "StmtAncestor.h" +#include "clang/AST/ASTContext.h" + +namespace clang { +namespace loop_migrate { +/// \brief VariableNamer - 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. +/// It creates a variable name using hints from a source container and the old +/// 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) { } + + /// \brief Generate a new index name. + /// + /// Generates the name to be used for an inserted iterator. It relies on + /// declarationExists() to determine that there are no naming conflicts, and + /// tries to use some hints from the container name and the old index name. + 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); +}; + +} // namespace loop_migrate +} // namespace clang +#endif //_LLVM_TOOLS_CLANG_TOOLS_LOOP_VARIABLE_NAMING_H_ Index: loop-convert/VariableNaming.cpp =================================================================== --- /dev/null +++ loop-convert/VariableNaming.cpp @@ -0,0 +1,82 @@ +#include "VariableNaming.h" + +namespace clang { +namespace loop_migrate { + +std::string VariableNamer::createIndexName() { + // FIXME: Add in naming conventions to handle: + // - Uppercase/lowercase indices + // - How to handle conflicts + // - An interactive process for naming + std::string IteratorName; + std::string ContainerName; + if (TheContainer) + ContainerName = TheContainer->getName().str(); + + size_t Len = ContainerName.length(); + if (Len > 1 && ContainerName[Len - 1] == 's') + IteratorName = ContainerName.substr(0, Len - 1); + else + IteratorName = "elem"; + + // FIXME: Maybe create a class so that this call doesn't need 6 parameters + // every time? + if (!declarationExists(IteratorName)) + return IteratorName; + + IteratorName = ContainerName + "_" + OldIndex->getName().str(); + if (!declarationExists(IteratorName)) + return IteratorName; + + IteratorName = ContainerName + "_elem"; + if (!declarationExists(IteratorName)) + return IteratorName; + + IteratorName += "_elem"; + if (!declarationExists(IteratorName)) + return IteratorName; + + IteratorName = "_elem_"; + + // Someone defeated my naming scheme... + while (declarationExists(IteratorName)) + IteratorName += "i"; + return IteratorName; +} + +// Determines whether or not the the name Symbol exists in LoopContext, any of +// its parent contexts, or any of its child statements. +// 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; + } + + // 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); + if (I != GeneratedDecls->end() && I->second == Symbol) + return true; + } + + // Finally, determine if the symbol was used in the loop or a child context. + DeclFinderASTVisitor DeclFinder(Symbol, GeneratedDecls); + return DeclFinder.findUsages(SourceStmt); +} + +} // namespace loop_migrate +} // namespace clang Index: test/CMakeLists.txt =================================================================== --- test/CMakeLists.txt +++ test/CMakeLists.txt @@ -22,7 +22,7 @@ clang clang-headers FileCheck count not # Individual tools we test. - remove-cstr-calls + remove-cstr-calls loop-convert ) add_lit_testsuite(check-clang-tools "Running the Clang extra tools' regression tests" Index: test/loop-convert/Inputs/negative-header.h =================================================================== --- /dev/null +++ test/loop-convert/Inputs/negative-header.h @@ -0,0 +1,14 @@ +#ifndef _CLANG_TOOLS_EXTRA_H_ +#define _CLANG_TOOLS_EXTRA_H_ + +// Single FileCheck line to make sure that no loops are converted. +// CHECK-NOT: for ({{.*[^:]:[^:].*}}) +static void loopInHeader() { + const int N = 10; + int arr[N]; + int sum = 0; + for (int i = 0; i < N; ++i) + sum += arr[i]; +} + +#endif //_CLANG_TOOLS_EXTRA_H_ Index: test/loop-convert/Inputs/structures.h =================================================================== --- /dev/null +++ test/loop-convert/Inputs/structures.h @@ -0,0 +1,139 @@ +#ifndef _LLVM_TOOLS_CLANG_TOOLS_TESTS_TOOLING_STRUCTURES_H_ +#define _LLVM_TOOLS_CLANG_TOOLS_TESTS_TOOLING_STRUCTURES_H_ + +extern "C" { +extern int printf(const char *restrict, ...); +} + +struct Val {int x; void g(); }; + +struct MutableVal { + void constFun(int) const; + void nonConstFun(int, int); + void constFun(MutableVal &) const; + void constParamFun(const MutableVal &) const; + void nonConstParamFun(const MutableVal &); + int x; +}; + +struct S { + typedef MutableVal *iterator; + typedef const MutableVal *const_iterator; + const_iterator begin() const; + const_iterator end() const; + iterator begin(); + iterator end(); +}; + +struct T { + struct iterator { + int& operator*(); + const int& operator*()const; + iterator& operator ++(); + bool operator!=(const iterator &other); + void insert(int); + int x; + }; + iterator begin(); + iterator end(); +}; + +struct U { + struct iterator { + Val& operator*(); + const Val& operator*()const; + iterator& operator ++(); + bool operator!=(const iterator &other); + Val *operator->(); + }; + iterator begin(); + iterator end(); + int x; +}; + +struct X { + S s; + T t; + U u; + S getS(); +}; + +template +class dependent{ + public: + struct iterator_base { + const ElemType& operator*()const; + iterator_base& operator ++(); + bool operator!=(const iterator_base &other) const; + const ElemType *operator->() const; + }; + + struct iterator : iterator_base { + ElemType& operator*(); + iterator& operator ++(); + ElemType *operator->(); + }; + + typedef iterator_base const_iterator; + const_iterator begin() const; + const_iterator end() const; + iterator begin(); + iterator end(); + unsigned size() const; + ElemType & operator[](unsigned); + const ElemType & operator[](unsigned) const; + ElemType & at(unsigned); + const ElemType & at(unsigned) const; + + // Intentionally evil. + dependent operator*(); + + void foo(); +}; + +template +class doublyDependent{ + public: + struct Value { + First first; + Second second; + }; + + struct iterator_base { + const Value& operator*()const; + iterator_base& operator ++(); + bool operator!=(const iterator_base &other) const; + const Value *operator->() const; + }; + + struct iterator : iterator_base { + Value& operator*(); + Value& operator ++(); + Value *operator->(); + }; + + typedef iterator_base const_iterator; + const_iterator begin() const; + const_iterator end() const; + iterator begin(); + iterator end(); +}; + +template +class transparent { + public: + Contained *at(); + Contained *operator->(); + Contained operator*(); +}; + +template +struct Nested { + typedef IteratorType* iterator; + IteratorType *operator->(); + IteratorType operator*(); + iterator begin(); + iterator end(); +}; + +#endif // _LLVM_TOOLS_CLANG_TOOLS_TESTS_TOOLING_STRUCTURES_H_ Index: test/loop-convert/loop-convert-array.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-array.cpp @@ -0,0 +1,133 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: cp %t.cpp %t.base +// RUN: loop-convert -count-only . %t.cpp -- -I %S/Inputs > %T/out \ +// RUN: && FileCheck -check-prefix=COUNTONLY -input-file=%T/out %s \ +// RUN: && diff %t.cpp %t.base + +const int N = 6; +const int NMinusOne = N - 1; +int arr[N] = {1, 2, 3, 4, 5, 6}; +int (*pArr)[N] = &arr; +#include "structures.h" +void f() { + int sum = 0; + // Update the number of correctly converted loops as this test changes: + // COUNTONLY: 14 converted + // COUNTONLY-NEXT: 0 potentially conflicting + // COUNTONLY-NEXT: 0 change(s) rejected + + for (int i = 0; i < N; ++i) { + sum += arr[i]; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) { + // CHECK-NEXT: sum += [[VAR]]; + // CHECK-NEXT: } + + for (int i = 0; i < N; ++i) { + printf("Fibonacci number is %d\n", arr[i]); + sum += arr[i] + 2; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + // CHECK-NEXT: sum += [[VAR]] + 2; + + for (int i = 0; i < N; ++i) { + int x = arr[i]; + int y = arr[i] + 2; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) + // CHECK-NEXT: int x = [[VAR]]; + // CHECK-NEXT: int y = [[VAR]] + 2; + + for (int i = 0; i < N; ++i) { + int x = N; + x = arr[i]; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) + // CHECK-NEXT: int x = N; + // CHECK-NEXT: x = [[VAR]]; + + for (int i = 0; i < N; ++i) { + arr[i] += 1; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) { + // CHECK-NEXT: [[VAR]] += 1; + // CHECK-NEXT: } + + for (int i = 0; i < N; ++i) { + int x = arr[i] + 2; + arr[i] ++; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) + // CHECK-NEXT: int x = [[VAR]] + 2; + // CHECK-NEXT: [[VAR]] ++; + + for (int i = 0; i < N; ++i) { + arr[i] = 4 + arr[i]; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) + // CHECK-NEXT: [[VAR]] = 4 + [[VAR]]; + + for (int i = 0; i < NMinusOne + 1; ++i) { + sum += arr[i]; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) { + // CHECK-NEXT: sum += [[VAR]]; + // CHECK-NEXT: } + + for (int i = 0; i < N; ++i) { + printf("Fibonacci number %d has address %p\n", arr[i], &arr[i]); + sum += arr[i] + 2; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) + // CHECK-NEXT: printf("Fibonacci number %d has address %p\n", [[VAR]], &[[VAR]]); + // CHECK-NEXT: sum += [[VAR]] + 2; + + Val teas[N]; + for (int i = 0; i < N; ++i) { + teas[i].g(); + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : teas) { + // CHECK-NEXT: [[VAR]].g(); + // CHECK-NEXT: } +} + +struct HasArr { + int Arr[N]; + Val ValArr[N]; + void implicitThis() { + for (int i = 0; i < N; ++i) { + printf("%d", Arr[i]); + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : Arr) { + // CHECK-NEXT: printf("%d", [[VAR]]); + // CHECK-NEXT: } + + for (int i = 0; i < N; ++i) { + printf("%d", ValArr[i].x); + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : ValArr) { + // CHECK-NEXT: printf("%d", [[VAR]].x); + // CHECK-NEXT: } + } + + void explicitThis() { + for (int i = 0; i < N; ++i) { + printf("%d", this->Arr[i]); + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : this->Arr) { + // CHECK-NEXT: printf("%d", [[VAR]]); + // CHECK-NEXT: } + + for (int i = 0; i < N; ++i) { + printf("%d", this->ValArr[i].x); + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : this->ValArr) { + // CHECK-NEXT: printf("%d", [[VAR]].x); + // CHECK-NEXT: } + } +}; Index: test/loop-convert/loop-convert-confidence.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-confidence.cpp @@ -0,0 +1,36 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s +// RUN: loop-convert . %t.cpp -A2 -- -I %S/Inputs \ +// RUN: && FileCheck -check-prefix=RISKY -input-file=%t.cpp %s + +#include "structures.h" + +void f() { + const int N = 5; + const int M = 7; + int (*pArr)[N]; + int Arr[N][M]; + int sum = 0; + + for (int i = 0; i < M; ++i) { + sum += Arr[0][i]; + } + // CHECK: for (int i = 0; i < M; ++i) { + // CHECK-NEXT: sum += Arr[0][i]; + // CHECK-NEXT: } + // RISKY: for (auto & [[VAR:[a-z_]+]] : Arr[0]) { + // RISKY-NEXT: sum += [[VAR]]; + // RISKY-NEXT: } + + for (int i = 0; i < N; ++i) { + sum += (*pArr)[i]; + } + // RISKY: for (auto & [[VAR:[a-z_]+]] : *pArr) { + // RISKY-NEXT: sum += [[VAR]]; + // RISKY-NEXT: } + // CHECK: for (int i = 0; i < N; ++i) { + // CHECK-NEXT: sum += (*pArr)[i]; + // CHECK-NEXT: } +} Index: test/loop-convert/loop-convert-dependency.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-dependency.cpp @@ -0,0 +1,27 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- && FileCheck -input-file=%t.cpp %s + +void f() { + const int N = 6; + const int M = 8; + int arr[N][M]; + + for (int i = 0; i < N; ++i) { + int a = 0; + int b = arr[i][a]; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : arr) { + // CHECK-NEXT: int a = 0; + // CHECK-NEXT: int b = [[VAR]][a]; + // CHECK-NEXT: } + + for (int j = 0; j < M; ++j) { + int a = 0; + int b = arr[a][j]; + } + // CHECK: for (int j = 0; j < M; ++j) { + // CHECK-NEXT: int a = 0; + // CHECK-NEXT: int b = arr[a][j]; + // CHECK-NEXT: } +} Index: test/loop-convert/loop-convert-iterator.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-iterator.cpp @@ -0,0 +1,106 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: rm -rf %t.cpp + +#include "structures.h" + +void f() { + /// begin()/end() - based for loops here: + T t; + for (T::iterator it = t.begin(), e = t.end(); it != e; ++it) { + printf("I found %d\n", *it); + } + // CHECK: for ({{[a-zA-Z_ ]+&? ?}}[[VAR:[a-z_]+]] : t) + // CHECK-NEXT: printf("I found %d\n", [[VAR]]); + + T *pt; + for (T::iterator it = pt->begin(), e = pt->end(); it != e; ++it) { + printf("I found %d\n", *it); + } + // CHECK: for ({{[a-zA-Z_ ]+&? ?}}[[VAR:[a-z_]+]] : *pt) + // CHECK-NEXT: printf("I found %d\n", [[VAR]]); + + S s; + for (S::const_iterator it = s.begin(), e = s.end(); it != e; ++it) { + printf("s has value %d\n", (*it).x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: printf("s has value %d\n", ([[VAR]]).x); + + S *ps; + for (S::const_iterator it = ps->begin(), e = ps->end(); it != e; ++it) { + printf("s has value %d\n", (*it).x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : *ps) + // CHECK-NEXT: printf("s has value %d\n", ([[VAR]]).x); + + for (S::const_iterator it = s.begin(), e = s.end(); it != e; ++it) { + printf("s has value %d\n", it->x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: printf("s has value %d\n", [[VAR]].x); + + for (S::iterator it = s.begin(), e = s.end(); it != e; ++it) { + it->x = 3; + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: [[VAR]].x = 3; + + for (S::iterator it = s.begin(), e = s.end(); it != e; ++it) { + (*it).x = 3; + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: ([[VAR]]).x = 3; + + for (S::iterator it = s.begin(), e = s.end(); it != e; ++it) { + it->nonConstFun(4, 5); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: [[VAR]].nonConstFun(4, 5); + + U u; + for (U::iterator it = u.begin(), e = u.end(); it != e; ++it) { + printf("s has value %d\n", it->x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : u) + // CHECK-NEXT: printf("s has value %d\n", [[VAR]].x); + + for (U::iterator it = u.begin(), e = u.end(); it != e; ++it) { + printf("s has value %d\n", (*it).x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : u) + // CHECK-NEXT: printf("s has value %d\n", ([[VAR]]).x); + + U::iterator A; + for (U::iterator i = u.begin(), e = u.end(); i != e; ++i) + int k = A->x + i->x; + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : u) + // CHECK-NEXT: int k = A->x + [[VAR]].x; + + dependent v; + for (dependent::const_iterator it = v.begin(), e = v.end(); + it != e; ++it) { + printf("Fibonacci number is %d\n", *it); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : v) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + + for (dependent::const_iterator it(v.begin()), e = v.end(); + it != e; ++it) { + printf("Fibonacci number is %d\n", *it); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : v) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + + doublyDependent intmap; + for (doublyDependent::iterator it = intmap.begin(), e = intmap.end(); + it != e; ++it) { + printf("intmap[%d] = %d", it->first, it->second); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : intmap) + // CHECK-NEXT: printf("intmap[%d] = %d", [[VAR]].first, [[VAR]].second); + +} Index: test/loop-convert/loop-convert-naming.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-naming.cpp @@ -0,0 +1,68 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s + +#include "structures.h" + +const int N = 10; +int nums[N]; +int sum = 0; + +Val Arr[N]; +Val &func(Val &); + +void aliasing() { + // The extra blank braces are left as a placeholder for after the variable + // declaration is deleted. + for (int i = 0; i < N; ++i) { + Val &t = Arr[i]; { } + int y = t.x; + } + // CHECK: for (auto & t : Arr) + // CHECK-NEXT: { } + // CHECK-NEXT: int y = t.x; + + for (int i = 0; i < N; ++i) { + Val &t = Arr[i]; + int y = t.x; + int z = Arr[i].x + t.x; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : Arr) + // CHECK-NEXT: Val &t = [[VAR]]; + // CHECK-NEXT: int y = t.x; + // CHECK-NEXT: int z = [[VAR]].x + t.x; + + for (int i = 0; i < N; ++i) { + Val t = Arr[i]; + int y = t.x; + int z = Arr[i].x + t.x; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : Arr) + // CHECK-NEXT: Val t = [[VAR]]; + // CHECK-NEXT: int y = t.x; + // CHECK-NEXT: int z = [[VAR]].x + t.x; + + for (int i = 0; i < N; ++i) { + Val &t = func(Arr[i]); + int y = t.x; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : Arr) + // CHECK-NEXT: Val &t = func([[VAR]]); + // CHECK-NEXT: int y = t.x; +} + +void sameNames() { + int num = 0; + for (int i = 0; i < N; ++i) { + printf("Fibonacci number is %d\n", nums[i]); + sum += nums[i] + 2 + num; + (void) nums[i]; + } + // CHECK: int num = 0; + // CHECK-NEXT: for (auto & [[VAR:[a-z_]+]] : nums) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + // CHECK-NEXT: sum += [[VAR]] + 2 + num; + // CHECK-NOT: (void) num; + // CHECK: } +} Index: test/loop-convert/loop-convert-negative-iterator.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-negative-iterator.cpp @@ -0,0 +1,155 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s + +#include "structures.h" + +// Single FileCheck line to make sure that no loops are converted. +// CHECK-NOT: for ({{.*[^:]:[^:].*}}) + +S s; +T t; +U u; + +struct BadBeginEnd : T { + iterator notBegin(); + iterator notEnd(); +}; + +void notBeginOrEnd() { + BadBeginEnd Bad; + for (T::iterator i = Bad.notBegin(), e = Bad.end(); i != e; ++i) + int k = *i; + + for (T::iterator i = Bad.begin(), e = Bad.notEnd(); i != e; ++i) + int k = *i; +} + +void badLoopShapes() { + for (T::iterator i = t.begin(), e = t.end(), f = e; i != e; ++i) + int k = *i; + + for (T::iterator i = t.begin(), e = t.end(); i != e; ) + int k = *i; + + for (T::iterator i = t.begin(), e = t.end(); ; ++i) + int k = *i; + + T::iterator outsideI; + T::iterator outsideE; + + for (; outsideI != outsideE ; ++outsideI) + int k = *outsideI; +} + +void iteratorArrayMix() { + int lower; + const int N = 6; + for (T::iterator i = t.begin(), e = t.end(); lower < N; ++i) + int k = *i; + + for (T::iterator i = t.begin(), e = t.end(); lower < N; ++lower) + int k = *i; +} + +struct ExtraConstructor : T::iterator { + ExtraConstructor(T::iterator, int); + explicit ExtraConstructor(T::iterator); +}; + +void badConstructor() { + for (T::iterator i = ExtraConstructor(t.begin(), 0), e = t.end(); + i != e; ++i) + int k = *i; + for (T::iterator i = ExtraConstructor(t.begin()), e = t.end(); i != e; ++i) + int k = *i; +} + +void iteratorMemberUsed() { + for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) + i.x = *i; + + for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) + int k = i.x + *i; + + for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) + int k = e.x + *i; +} + +void iteratorMethodCalled() { + for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) + i.insert(3); + + for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) + if (i != i) + int k = 3; +} + +void iteratorOperatorCalled() { + for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) + int k = *(++i); + + for (S::iterator i = s.begin(), e = s.end(); i != e; ++i) + MutableVal k = *(++i); +} + +void differentContainers() { + T other; + for (T::iterator i = t.begin(), e = other.end(); i != e; ++i) + int k = *i; + + for (T::iterator i = other.begin(), e = t.end(); i != e; ++i) + int k = *i; + + S otherS; + for (S::iterator i = s.begin(), e = otherS.end(); i != e; ++i) + MutableVal k = *i; + + for (S::iterator i = otherS.begin(), e = s.end(); i != e; ++i) + MutableVal k = *i; +} + +struct EvilArrow : U { + // Please, no one ever write code like this. + U* operator->(); +}; + +void differentMemberAccessTypes() { + EvilArrow A; + for (EvilArrow::iterator i = A.begin(), e = A->end(); i != e; ++i) + Val k = *i; + for (EvilArrow::iterator i = A->begin(), e = A.end(); i != e; ++i) + Val k = *i; +} + +void f(const T::iterator &it, int); +void f(const T &it, int); +void g(T &it, int); + +void iteratorPassedToFunction() { + for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) + f(i, *i); +} + +// FIXME: Disallow this except for containers passed by value and/or const +// reference. Or maybe this is correct enough for any container? +void containerPassedToFunction() { +// for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) +// f(t, *i); +// for (T::iterator i = t.begin(), e = t.end(); i != e; ++i) +// g(t, *i); +} + +// FIXME: These tests can be removed if this tool ever does enough analysis to +// decide that this is a safe transformation. +// Until then, we don't want it applied. +void iteratorDefinedOutside() { + T::iterator theEnd = t.end(); + for (T::iterator i = t.begin(); i != theEnd; ++i) + int k = *i; + + T::iterator theBegin = t.begin(); + for (T::iterator e = t.end(); theBegin != e; ++theBegin) + int k = *theBegin; +} Index: test/loop-convert/loop-convert-negative-multi-end-call.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-negative-multi-end-call.cpp @@ -0,0 +1,65 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert -A0 . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s + +#include "structures.h" + +// Single FileCheck line to make sure that no loops are converted. +// CHECK-NOT: for ({{.*[^:]:[^:].*}}) + +S s; +T t; +U u; + +void multipleEnd() { + for (S::iterator i = s.begin(); i != s.end(); ++i) + MutableVal k = *i; + + for (T::iterator i = t.begin(); i != t.end(); ++i) + int k = *i; + + for (U::iterator i = u.begin(); i != u.end(); ++i) + Val k = *i; +} + +void f(X); +void f(S); +void f(T); + +void complexContainer() { + X x; + for (S::iterator i = x.s.begin(), e = x.s.end(); i != e; ++i) { + f(x); + MutableVal k = *i; + } + + for (T::iterator i = x.t.begin(), e = x.t.end(); i != e; ++i) { + f(x); + int k = *i; + } + + for (S::iterator i = x.s.begin(), e = x.s.end(); i != e; ++i) { + f(x.s); + MutableVal k = *i; + } + + for (T::iterator i = x.t.begin(), e = x.t.end(); i != e; ++i) { + f(x.t); + int k = *i; + } + + for (S::iterator i = x.getS().begin(), e = x.getS().end(); i != e; ++i) { + f(x.getS()); + MutableVal k = *i; + } + + X exes[5]; + int index = 0; + + for (S::iterator i = exes[index].getS().begin(), + e = exes[index].getS().end(); i != e; ++i) { + index++; + MutableVal k = *i; + } +} Index: test/loop-convert/loop-convert-negative-pseudoarray.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-negative-pseudoarray.cpp @@ -0,0 +1,124 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert -A1 . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s + +#include "structures.h" + +// Single FileCheck line to make sure that no loops are converted. +// CHECK-NOT: for ({{.*[^:]:[^:].*}}) + +const int N = 6; +dependent v; +dependent *pv; + +transparent > cv; +int sum = 0; + +// Checks for the index start and end: +void indexStartAndEnd() { + for (int i = 0; i < v.size() + 1; ++i) + sum += v[i]; + + for (int i = 0; i < v.size() - 1; ++i) + sum += v[i]; + + for (int i = 1; i < v.size(); ++i) + sum += v[i]; + + for (int i = 1; i < v.size(); ++i) + sum += v[i]; + + for (int i = 0; ; ++i) + sum += (*pv)[i]; +} + +// Checks for invalid increment steps: +void increment() { + for (int i = 0; i < v.size(); --i) + sum += v[i]; + + for (int i = 0; i < v.size(); i) + sum += v[i]; + + for (int i = 0; i < v.size();) + sum += v[i]; + + for (int i = 0; i < v.size(); i += 2) + sum ++; +} + +// Checks to make sure that the index isn't used outside of the container: +void indexUse() { + for (int i = 0; i < v.size(); ++i) + v[i] += 1 + i; +} + +// Checks for incorrect loop variables. +void mixedVariables() { + int badIndex; + for (int i = 0; badIndex < v.size(); ++i) + sum += v[i]; + + for (int i = 0; i < v.size(); ++badIndex) + sum += v[i]; + + for (int i = 0; badIndex < v.size(); ++badIndex) + sum += v[i]; + + for (int i = 0; badIndex < v.size(); ++badIndex) + sum += v[badIndex]; +} + +// Checks for an array indexed in addition to the container. +void multipleArrays() { + int badArr[N]; + + for (int i = 0; i < v.size(); ++i) + sum += v[i] + badArr[i]; + + for (int i = 0; i < v.size(); ++i) + sum += badArr[i]; + + for (int i = 0; i < v.size(); ++i) { + int k = badArr[i]; + sum += k + 2; + } + + for (int i = 0; i < v.size(); ++i) { + int k = badArr[i]; + sum += v[i] + k; + } +} + +// Checks for multipile containers being indexed container. +void multipleContainers() { + dependent badArr; + + for (int i = 0; i < v.size(); ++i) + sum += v[i] + badArr[i]; + + for (int i = 0; i < v.size(); ++i) + sum += badArr[i]; + + for (int i = 0; i < v.size(); ++i) { + int k = badArr[i]; + sum += k + 2; + } + + for (int i = 0; i < v.size(); ++i) { + int k = badArr[i]; + sum += v[i] + k; + } +} + +// Check to make sure that dereferenced pointers-to-containers behave nicely +void derefContainer() { + // Note the dependent::operator*() returns another dependent. + // This test makes sure that we don't allow an arbitrary number of *'s. + for (int i = 0; i < pv->size(); ++i) + sum += (**pv).at(i); + + for (int i = 0; i < pv->size(); ++i) + sum += (**pv)[i]; +} Index: test/loop-convert/loop-convert-negative.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-negative.cpp @@ -0,0 +1,125 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %S/Inputs/negative-header.h > \ +// RUN: %T/negative-header.h +// RUN: loop-convert . %t.cpp -- -I %S/Inputs/ \ +// RUN: && FileCheck -input-file=%t.cpp %s \ +// RUN: && FileCheck -input-file=%T/negative-header.h \ +// RUN: %S/Inputs/negative-header.h + +#include "negative-header.h" +#include "structures.h" + +// Single FileCheck line to make sure that no loops are converted. +// CHECK-NOT: for ({{.*[^:]:[^:].*}}) + +const int N = 6; +int arr[N] = {1, 2, 3, 4, 5, 6}; +int (*pArr)[N] = &arr; +int sum = 0; + +// Checks for the index start and end: +void indexStartAndEnd() { + for (int i = 0; i < N + 1; ++i) + sum += arr[i]; + + for (int i = 0; i < N - 1; ++i) + sum += arr[i]; + + for (int i = 1; i < N; ++i) + sum += arr[i]; + + for (int i = 1; i < N; ++i) + sum += arr[i]; + + for (int i = 0; ; ++i) + sum += (*pArr)[i]; +} + +// Checks for invalid increment steps: +void increment() { + for (int i = 0; i < N; --i) + sum += arr[i]; + + for (int i = 0; i < N; i) + sum += arr[i]; + + for (int i = 0; i < N;) + sum += arr[i]; + + for (int i = 0; i < N; i += 2) + sum ++; +} + +// Checks to make sure that the index isn't used outside of the array: +void indexUse() { + for (int i = 0; i < N; ++i) + arr[i] += 1 + i; +} + +// Check for loops that don't mention arrays +void noArray() { + for (int i = 0; i < N; ++i) + sum += i; + + for (int i = 0; i < N; ++i) { } + + for (int i = 0; i < N; ++i) ; +} + +// Checks for incorrect loop variables. +void mixedVariables() { + int badIndex; + for (int i = 0; badIndex < N; ++i) + sum += arr[i]; + + for (int i = 0; i < N; ++badIndex) + sum += arr[i]; + + for (int i = 0; badIndex < N; ++badIndex) + sum += arr[i]; + + for (int i = 0; badIndex < N; ++badIndex) + sum += arr[badIndex]; +} + +// Checks for multiple arrays indexed. +void multipleArrays() { + int badArr[N]; + + for (int i = 0; i < N; ++i) + sum += arr[i] + badArr[i]; + + for (int i = 0; i < N; ++i) { + int k = badArr[i]; + sum += arr[i] + k; + } +} + +struct HasArr { + int Arr[N]; + Val ValArr[N]; +}; + +struct HasIndirectArr { + HasArr HA; + void implicitThis() { + for (int i = 0; i < N; ++i) { + printf("%d", HA.Arr[i]); + } + + for (int i = 0; i < N; ++i) { + printf("%d", HA.ValArr[i].x); + } + } + + void explicitThis() { + for (int i = 0; i < N; ++i) { + printf("%d", this->HA.Arr[i]); + } + + for (int i = 0; i < N; ++i) { + printf("%d", this->HA.ValArr[i].x); + } + } +}; Index: test/loop-convert/loop-convert-nesting.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-nesting.cpp @@ -0,0 +1,58 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s + +#include "structures.h" + +void f() { + const int N = 10; + const int M = 15; + Val Arr[N]; + for (int i = 0; i < N; ++i) { + for (int j = 0; j < N; ++j) { + int k = Arr[i].x + Arr[j].x; + // The repeat is there to allow FileCheck to make sure the two variable + // names aren't the same. + int l = Arr[i].x + Arr[j].x; + } + } + // CHECK: for (auto & [[VAR:[a-zA-Z_]+]] : Arr) + // CHECK-NEXT: for (auto & [[INNERVAR:[a-zA-Z_]+]] : Arr) + // CHECK-NEXT: int k = [[VAR]].x + [[INNERVAR]].x; + // CHECK-NOT: int l = [[VAR]].x + [[VAR]].x; + + Val Nest[N][M]; + for (int i = 0; i < N; ++i) { + for (int j = 0; j < M; ++j) { + printf("Got item %d", Nest[i][j].x); + } + } + // The inner loop is also convertible, but doesn't need to be converted + // immediately. Update this test when that changes! + // CHECK: for (auto & [[VAR:[a-zA-Z_]+]] : Nest) + // CHECK-NEXT: for (int j = 0; j < M; ++j) + // CHECK-NEXT: printf("Got item %d", [[VAR]][j].x); + + // Note that the order of M and N are switched for this test. + for (int j = 0; j < M; ++j) { + for (int i = 0; i < N; ++i) { + printf("Got item %d", Nest[i][j].x); + } + } + // CHECK-NOT: for (auto & {{[a-zA-Z_]+}} : Nest[i]) + // CHECK: for (int j = 0; j < M; ++j) + // CHECK-NEXT: for (auto & [[VAR:[a-zA-Z_]+]] : Nest) + // CHECK-NEXT: printf("Got item %d", [[VAR]][j].x); + Nested NestT; + for (Nested::iterator I = NestT.begin(), E = NestT.end(); I != E; ++I) { + for (T::iterator TI = (*I).begin(), TE = (*I).end(); TI != TE; ++TI) { + printf("%d", *TI); + } + } + // The inner loop is also convertible, but doesn't need to be converted + // immediately. Update this test when that changes! + // CHECK: for (auto & [[VAR:[a-zA-Z_]+]] : NestT) { + // CHECK-NEXT: for (T::iterator TI = ([[VAR]]).begin(), TE = ([[VAR]]).end(); TI != TE; ++TI) { + // CHECK-NEXT: printf("%d", *TI); +} Index: test/loop-convert/loop-convert-nocompile.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-nocompile.cpp @@ -0,0 +1,23 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: || FileCheck -input-file=%t.cpp %s +// Note that this test expects the compilation to fail! + +void valid() { + const int arr[5]; + int sum = 0; + for (int i = 0; i < 5; ++i) { + sum += arr[i]; + } +} +void hasSyntaxError = 3; +// CHECK: void valid() { +// CHECK-NEXT: const int arr[5]; +// CHECK-NEXT: int sum = 0; +// CHECK-NEXT: for (int i = 0; i < 5; ++i) { +// CHECK-NEXT: sum += arr[i]; +// CHECK-NEXT: } +// CHECK-NEXT: } + +// CHECK-NEXT: void hasSyntaxError = 3; Index: test/loop-convert/loop-convert-pseudoarray.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-pseudoarray.cpp @@ -0,0 +1,68 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s +// RUN: rm -rf %t.cpp +#include "structures.h" + +const int N = 6; +dependent v; +dependent *pv; + +transparent > cv; + +void f() { + int sum = 0; + for (int i = 0, e = v.size(); i < e; ++i) { + printf("Fibonacci number is %d\n", v[i]); + sum += v[i] + 2; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : v) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + // CHECK-NEXT: sum += [[VAR]] + 2; + + for (int i = 0, e = v.size(); i < e; ++i) { + printf("Fibonacci number is %d\n", v.at(i)); + sum += v.at(i) + 2; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : v) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + // CHECK-NEXT: sum += [[VAR]] + 2; + + for (int i = 0, e = pv->size(); i < e; ++i) { + printf("Fibonacci number is %d\n", pv->at(i)); + sum += pv->at(i) + 2; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : *pv) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + // CHECK-NEXT: sum += [[VAR]] + 2; + + // This test will fail if size() isn't called repeatedly, since it + // returns unsigned int, and 0 is deduced to be signed int. + // FIXME: Insert the necessary explicit conversion, or write out the types + // explicitly. + for (int i = 0; i < pv->size(); ++i) { + printf("Fibonacci number is %d\n", (*pv).at(i)); + sum += (*pv)[i] + 2; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : *pv) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + // CHECK-NEXT: sum += [[VAR]] + 2; + + for (int i = 0; i < cv->size(); ++i) { + printf("Fibonacci number is %d\n", cv->at(i)); + sum += cv->at(i) + 2; + } + // CHECK: for (auto & [[VAR:[a-z_]+]] : *cv) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + // CHECK-NEXT: sum += [[VAR]] + 2; +} + +// Check for loops that don't mention containers +void noContainer() { + for (auto i = 0; i < v.size(); ++i) { } + // CHECK: for (auto & [[VAR:[a-z_]+]] : v) { } + + for (auto i = 0; i < v.size(); ++i) ; + // CHECK: for (auto & [[VAR:[a-z_]+]] : v) ; +} Index: test/loop-convert/loop-convert-single-iterator.cpp =================================================================== --- /dev/null +++ test/loop-convert/loop-convert-single-iterator.cpp @@ -0,0 +1,118 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: rm -rf %t.cpp + +#include "structures.h" + +void complexContainer() { + X exes[5]; + int index = 0; + + for (S::iterator i = exes[index].getS().begin(), e = exes[index].getS().end(); i != e; ++i) { + MutableVal k = *i; + MutableVal j = *i; + } + // CHECK: for ({{[a-zA-Z_ ]+&? ?}}[[VAR:[a-z_]+]] : exes[index].getS()) + // CHECK-NEXT: MutableVal k = [[VAR]]; + // CHECK-NEXT: MutableVal j = [[VAR]]; +} + +void f() { + /// begin()/end() - based for loops here: + T t; + for (T::iterator it = t.begin(); it != t.end(); ++it) { + printf("I found %d\n", *it); + } + // CHECK: for ({{[a-zA-Z_ ]+&? ?}}[[VAR:[a-z_]+]] : t) + // CHECK-NEXT: printf("I found %d\n", [[VAR]]); + + T *pt; + for (T::iterator it = pt->begin(); it != pt->end(); ++it) { + printf("I found %d\n", *it); + } + // CHECK: for ({{[a-zA-Z_ ]+&? ?}}[[VAR:[a-z_]+]] : *pt) + // CHECK-NEXT: printf("I found %d\n", [[VAR]]); + + S s; + for (S::const_iterator it = s.begin(); it != s.end(); ++it) { + printf("s has value %d\n", (*it).x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: printf("s has value %d\n", ([[VAR]]).x); + + S *ps; + for (S::const_iterator it = ps->begin(); it != ps->end(); ++it) { + printf("s has value %d\n", (*it).x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : *ps) + // CHECK-NEXT: printf("s has value %d\n", ([[VAR]]).x); + + for (S::const_iterator it = s.begin(); it != s.end(); ++it) { + printf("s has value %d\n", it->x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: printf("s has value %d\n", [[VAR]].x); + + for (S::iterator it = s.begin(); it != s.end(); ++it) { + it->x = 3; + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: [[VAR]].x = 3; + + for (S::iterator it = s.begin(); it != s.end(); ++it) { + (*it).x = 3; + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: ([[VAR]]).x = 3; + + for (S::iterator it = s.begin(); it != s.end(); ++it) { + it->nonConstFun(4, 5); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : s) + // CHECK-NEXT: [[VAR]].nonConstFun(4, 5); + + U u; + for (U::iterator it = u.begin(); it != u.end(); ++it) { + printf("s has value %d\n", it->x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : u) + // CHECK-NEXT: printf("s has value %d\n", [[VAR]].x); + + for (U::iterator it = u.begin(); it != u.end(); ++it) { + printf("s has value %d\n", (*it).x); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : u) + // CHECK-NEXT: printf("s has value %d\n", ([[VAR]]).x); + + U::iterator A; + for (U::iterator i = u.begin(); i != u.end(); ++i) + int k = A->x + i->x; + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : u) + // CHECK-NEXT: int k = A->x + [[VAR]].x; + + dependent v; + for (dependent::const_iterator it = v.begin(); + it != v.end(); ++it) { + printf("Fibonacci number is %d\n", *it); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : v) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + + for (dependent::const_iterator it(v.begin()); + it != v.end(); ++it) { + printf("Fibonacci number is %d\n", *it); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : v) + // CHECK-NEXT: printf("Fibonacci number is %d\n", [[VAR]]); + + doublyDependent intmap; + for (doublyDependent::iterator it = intmap.begin(); + it != intmap.end(); ++it) { + printf("intmap[%d] = %d", it->first, it->second); + } + // CHECK: for ({{[a-zA-Z_ ]*&? ?}}[[VAR:[a-z_]+]] : intmap) + // CHECK-NEXT: printf("intmap[%d] = %d", [[VAR]].first, [[VAR]].second); +} Index: test/loop-convert/negative-pseudoarray-extra.cpp =================================================================== --- /dev/null +++ test/loop-convert/negative-pseudoarray-extra.cpp @@ -0,0 +1,30 @@ +// RUN: rm -rf %t.cpp +// RUN: grep -Ev "//\s*[A-Z-]+:" %s > %t.cpp +// RUN: loop-convert -A1 . %t.cpp -- -I %S/Inputs \ +// RUN: && FileCheck -input-file=%t.cpp %s + +#include "structures.h" + +// Single FileCheck line to make sure that no loops are converted. +// CHECK-NOT: for ({{.*[^:]:[^:].*}}) + +const int N = 6; +dependent v; +dependent *pv; + +int sum = 0; + +// Checks to see that non-const member functions are not called on the container +// object. +// These could be conceivably allowed with a lower required confidence level. +void memberFunctionCalled() { + for (int i = 0; i < v.size(); ++i) { + sum += v[i]; + v.foo(); + } + + for (int i = 0; i < v.size(); ++i) { + sum += v[i]; + dependent::iterator it = v.begin(); + } +}