Author: szepet Date: Wed Jul 19 17:05:25 2017 New Revision: 308561 URL: http://llvm.org/viewvc/llvm-project?rev=308561&view=rev Log: [StaticAnalyzer] Completely unrolling specific loops with known bound option
Missing files added to rL308558. Added: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp cfe/trunk/test/Analysis/loop-unrolling.cpp Added: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h?rev=308561&view=auto ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h (added) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h Wed Jul 19 17:05:25 2017 @@ -0,0 +1,33 @@ +//===--- LoopUnrolling.h - Unroll loops -------------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// +/// This header contains the declarations of functions which are used to decide +/// which loops should be completely unrolled and mark their corresponding +/// CFGBlocks. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPUNROLLING_H +#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_LOOPUNROLLING_H + +#include "clang/Analysis/CFG.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" + +namespace clang { +namespace ento { +ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State, + CFGStmtMap *StmtToBlockMap); +bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev); +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx); + +} // end namespace ento +} // end namespace clang + +#endif Added: cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp?rev=308561&view=auto ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp (added) +++ cfe/trunk/lib/StaticAnalyzer/Core/LoopUnrolling.cpp Wed Jul 19 17:05:25 2017 @@ -0,0 +1,203 @@ +//===--- LoopUnrolling.cpp - Unroll 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 functions which are used to decide if a loop worth to be +/// unrolled. Moreover contains function which mark the CFGBlocks which belongs +/// to the unrolled loop and store them in ProgramState. +/// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/CFGStmtMap.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/AST/ParentMap.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h" +#include "llvm/ADT/Statistic.h" + +using namespace clang; +using namespace ento; +using namespace clang::ast_matchers; + +#define DEBUG_TYPE "LoopUnrolling" + +STATISTIC(NumTimesLoopUnrolled, + "The # of times a loop has got completely unrolled"); + +REGISTER_MAP_WITH_PROGRAMSTATE(UnrolledLoops, const Stmt *, const CFGStmtMap *) + +namespace clang { +namespace ento { + +static bool isLoopStmt(const Stmt *S) { + return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S)); +} + +static internal::Matcher<Stmt> simpleCondition(StringRef BindName) { + return binaryOperator( + anyOf(hasOperatorName("<"), hasOperatorName(">"), hasOperatorName("<="), + hasOperatorName(">="), hasOperatorName("!=")), + hasEitherOperand(ignoringParenImpCasts( + declRefExpr(to(varDecl(hasType(isInteger())).bind(BindName))))), + hasEitherOperand(ignoringParenImpCasts(integerLiteral()))); +} + +static internal::Matcher<Stmt> changeIntBoundNode(StringRef NodeName) { + return anyOf(hasDescendant(unaryOperator( + anyOf(hasOperatorName("--"), hasOperatorName("++")), + hasUnaryOperand(ignoringParenImpCasts( + declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))))), + hasDescendant(binaryOperator( + anyOf(hasOperatorName("="), hasOperatorName("+="), + hasOperatorName("/="), hasOperatorName("*="), + hasOperatorName("-=")), + hasLHS(ignoringParenImpCasts( + declRefExpr(to(varDecl(equalsBoundNode(NodeName))))))))); +} + +static internal::Matcher<Stmt> callByRef(StringRef NodeName) { + return hasDescendant(callExpr(forEachArgumentWithParam( + declRefExpr(to(varDecl(equalsBoundNode(NodeName)))), + parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))))); +} + +static internal::Matcher<Stmt> assignedToRef(StringRef NodeName) { + return hasDescendant(varDecl( + allOf(hasType(referenceType()), + hasInitializer(anyOf( + initListExpr(has( + declRefExpr(to(varDecl(equalsBoundNode(NodeName)))))), + declRefExpr(to(varDecl(equalsBoundNode(NodeName))))))))); +} + +static internal::Matcher<Stmt> getAddrTo(StringRef NodeName) { + return hasDescendant(unaryOperator( + hasOperatorName("&"), + hasUnaryOperand(declRefExpr(hasDeclaration(equalsBoundNode(NodeName)))))); +} + +static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) { + return anyOf(hasDescendant(gotoStmt()), hasDescendant(switchStmt()), + // Escaping and not known mutation of the loop counter is handled + // by exclusion of assigning and address-of operators and + // pass-by-ref function calls on the loop counter from the body. + changeIntBoundNode(NodeName), callByRef(NodeName), + getAddrTo(NodeName), assignedToRef(NodeName)); +} + +static internal::Matcher<Stmt> forLoopMatcher() { + return forStmt( + hasCondition(simpleCondition("initVarName")), + // Initialization should match the form: 'int i = 6' or 'i = 42'. + hasLoopInit( + anyOf(declStmt(hasSingleDecl( + varDecl(allOf(hasInitializer(integerLiteral()), + equalsBoundNode("initVarName"))))), + binaryOperator(hasLHS(declRefExpr(to(varDecl( + equalsBoundNode("initVarName"))))), + hasRHS(integerLiteral())))), + // Incrementation should be a simple increment or decrement + // operator call. + hasIncrement(unaryOperator( + anyOf(hasOperatorName("++"), hasOperatorName("--")), + hasUnaryOperand(declRefExpr( + to(varDecl(allOf(equalsBoundNode("initVarName"), + hasType(isInteger())))))))), + unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop"); +} + +bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx) { + + if (!isLoopStmt(LoopStmt)) + return false; + + // TODO: Match the cases where the bound is not a concrete literal but an + // integer with known value + + auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx); + return !Matches.empty(); +} + +namespace { +class LoopBlockVisitor : public ConstStmtVisitor<LoopBlockVisitor> { +public: + LoopBlockVisitor(llvm::SmallPtrSet<const CFGBlock *, 8> &BS) : BlockSet(BS) {} + + void VisitChildren(const Stmt *S) { + for (const Stmt *Child : S->children()) + if (Child) + Visit(Child); + } + + void VisitStmt(const Stmt *S) { + // In case of nested loops we only unroll the inner loop if it's marked too. + if (!S || (isLoopStmt(S) && S != LoopStmt)) + return; + BlockSet.insert(StmtToBlockMap->getBlock(S)); + VisitChildren(S); + } + + void setBlocksOfLoop(const Stmt *Loop, const CFGStmtMap *M) { + BlockSet.clear(); + StmtToBlockMap = M; + LoopStmt = Loop; + Visit(LoopStmt); + } + +private: + llvm::SmallPtrSet<const CFGBlock *, 8> &BlockSet; + const CFGStmtMap *StmtToBlockMap; + const Stmt *LoopStmt; +}; +} +// TODO: refactor this function using ScopeContext - once we have the +// information when the simulation reaches the end of the loop we can cleanup +// the state +bool isUnrolledLoopBlock(const CFGBlock *Block, ExplodedNode *Prev) { + const Stmt *Term = Block->getTerminator(); + auto State = Prev->getState(); + // In case of nested loops in an inlined function should not be unrolled only + // if the inner loop is marked. + if (Term && isLoopStmt(Term) && !State->contains<UnrolledLoops>(Term)) + return false; + + const CFGBlock *SearchedBlock; + llvm::SmallPtrSet<const CFGBlock *, 8> BlockSet; + LoopBlockVisitor LBV(BlockSet); + // Check the CFGBlocks of every marked loop. + for (auto &E : State->get<UnrolledLoops>()) { + SearchedBlock = Block; + const StackFrameContext *StackFrame = Prev->getStackFrame(); + LBV.setBlocksOfLoop(E.first, E.second); + // In case of an inlined function call check if any of its callSiteBlock is + // marked. + while (SearchedBlock && BlockSet.find(SearchedBlock) == BlockSet.end()) { + SearchedBlock = StackFrame->getCallSiteBlock(); + StackFrame = StackFrame->getParent()->getCurrentStackFrame(); + } + + if (SearchedBlock) + return true; + } + return false; +} + +ProgramStateRef markLoopAsUnrolled(const Stmt *Term, ProgramStateRef State, + CFGStmtMap *StmtToBlockMap) { + if (State->contains<UnrolledLoops>(Term)) + return State; + + State = State->set<UnrolledLoops>(Term, StmtToBlockMap); + ++NumTimesLoopUnrolled; + return State; +} +} +} Added: cfe/trunk/test/Analysis/loop-unrolling.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/test/Analysis/loop-unrolling.cpp?rev=308561&view=auto ============================================================================== --- cfe/trunk/test/Analysis/loop-unrolling.cpp (added) +++ cfe/trunk/test/Analysis/loop-unrolling.cpp Wed Jul 19 17:05:25 2017 @@ -0,0 +1,181 @@ +// REQUIRES: asserts +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -analyzer-config unroll-loops=true -analyzer-stats -verify -std=c++11 %s 2>&1 | FileCheck %s + +void clang_analyzer_numTimesReached(); + +int getNum(); +void foo(int &); +// Testing for loops. +int simple_unroll1() { + int a[9]; + int k = 42; + for (int i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{9}} + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_unroll2() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{9}} + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_no_unroll1() { + int a[9]; + int k = 42; + for (int i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + foo(i); + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_no_unroll2() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + i += getNum(); + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_no_unroll3() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + (void)&i; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int simple_no_unroll4() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + int &j = i; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int simple_no_unroll5() { + int a[9]; + int k = 42; + int i; + for (i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + a[i] = 42; + int &j{i}; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int nested_outer_unrolled() { + int a[9]; + int k = 42; + int j = 0; + for (int i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{16}} + for (j = 0; j < getNum(); ++j) { + clang_analyzer_numTimesReached(); // expected-warning {{15}} + a[j] = 22; + } + a[i] = 42; + } + int b = 22 / (k - 42); // no-warning + return 0; +} + +int nested_inner_unrolled() { + int a[9]; + int k = 42; + int j = 0; + for (int i = 0; i < getNum(); i++) { + clang_analyzer_numTimesReached(); // expected-warning {{4}} + for (j = 0; j < 8; ++j) { + clang_analyzer_numTimesReached(); // expected-warning {{32}} + a[j] = 22; + } + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int nested_both_unrolled() { + int a[9]; + int k = 42; + int j = 0; + for (int i = 0; i < 7; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{7}} + for (j = 0; j < 6; ++j) { + clang_analyzer_numTimesReached(); // expected-warning {{42}} + a[j] = 22; + } + a[i] = 42; + } + int b = 22 / (k - 42); // expected-warning {{Division by zero}} + return 0; +} + +int simple_known_bound_loop() { + for (int i = 2; i < 12; i++) { + // This function is inlined in nested_inlined_unroll1() + clang_analyzer_numTimesReached(); // expected-warning {{90}} + } + return 0; +} + +int simple_unknown_bound_loop() { + for (int i = 2; i < getNum(); i++) { + clang_analyzer_numTimesReached(); // expected-warning {{10}} + } + return 0; +} + +int nested_inlined_unroll1() { + int k; + for (int i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{9}} + k = simple_known_bound_loop(); // no reevaluation without inlining + } + int a = 22 / k; // expected-warning {{Division by zero}} + return 0; +} + +int nested_inlined_no_unroll1() { + int k; + for (int i = 0; i < 9; i++) { + clang_analyzer_numTimesReached(); // expected-warning {{26}} + k = simple_unknown_bound_loop(); // reevaluation without inlining + } + int a = 22 / k; // no-warning + return 0; +} + +// CHECK: ... Statistics Collected ... +// CHECK: 5 ExprEngine - The # of times we re-evaluated a call without inlining +// CHECK: 9 LoopUnrolling - The # of times a loop has got completely unrolled _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits