1 //===--- LoopUnrolling.cpp - Unroll loops -----------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// This file contains functions which are used to decide if a loop worth to be
10 /// unrolled. Moreover, these functions manages the stack of loop which is
11 /// tracked by the ProgramState.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/ASTMatchers/ASTMatchers.h"
16 #include "clang/ASTMatchers/ASTMatchFinder.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
20 
21 using namespace clang;
22 using namespace ento;
23 using namespace clang::ast_matchers;
24 
25 static const int MAXIMUM_STEP_UNROLLED = 128;
26 
27 struct LoopState {
28 private:
29   enum Kind { Normal, Unrolled } K;
30   const Stmt *LoopStmt;
31   const LocationContext *LCtx;
32   unsigned maxStep;
33   LoopState(Kind InK, const Stmt *S, const LocationContext *L, unsigned N)
34       : K(InK), LoopStmt(S), LCtx(L), maxStep(N) {}
35 
36 public:
37   static LoopState getNormal(const Stmt *S, const LocationContext *L,
38                              unsigned N) {
39     return LoopState(Normal, S, L, N);
40   }
41   static LoopState getUnrolled(const Stmt *S, const LocationContext *L,
42                                unsigned N) {
43     return LoopState(Unrolled, S, L, N);
44   }
45   bool isUnrolled() const { return K == Unrolled; }
46   unsigned getMaxStep() const { return maxStep; }
47   const Stmt *getLoopStmt() const { return LoopStmt; }
48   const LocationContext *getLocationContext() const { return LCtx; }
49   bool operator==(const LoopState &X) const {
50     return K == X.K && LoopStmt == X.LoopStmt;
51   }
52   void Profile(llvm::FoldingSetNodeID &ID) const {
53     ID.AddInteger(K);
54     ID.AddPointer(LoopStmt);
55     ID.AddPointer(LCtx);
56     ID.AddInteger(maxStep);
57   }
58 };
59 
60 // The tracked stack of loops. The stack indicates that which loops the
61 // simulated element contained by. The loops are marked depending if we decided
62 // to unroll them.
63 // TODO: The loop stack should not need to be in the program state since it is
64 // lexical in nature. Instead, the stack of loops should be tracked in the
65 // LocationContext.
66 REGISTER_LIST_WITH_PROGRAMSTATE(LoopStack, LoopState)
67 
68 namespace clang {
69 namespace ento {
70 
71 static bool isLoopStmt(const Stmt *S) {
72   return S && (isa<ForStmt>(S) || isa<WhileStmt>(S) || isa<DoStmt>(S));
73 }
74 
75 ProgramStateRef processLoopEnd(const Stmt *LoopStmt, ProgramStateRef State) {
76   auto LS = State->get<LoopStack>();
77   if (!LS.isEmpty() && LS.getHead().getLoopStmt() == LoopStmt)
78     State = State->set<LoopStack>(LS.getTail());
79   return State;
80 }
81 
82 static internal::Matcher<Stmt> simpleCondition(StringRef BindName) {
83   return binaryOperator(anyOf(hasOperatorName("<"), hasOperatorName(">"),
84                               hasOperatorName("<="), hasOperatorName(">="),
85                               hasOperatorName("!=")),
86                         hasEitherOperand(ignoringParenImpCasts(declRefExpr(
87                             to(varDecl(hasType(isInteger())).bind(BindName))))),
88                         hasEitherOperand(ignoringParenImpCasts(
89                             integerLiteral().bind("boundNum"))))
90       .bind("conditionOperator");
91 }
92 
93 static internal::Matcher<Stmt>
94 changeIntBoundNode(internal::Matcher<Decl> VarNodeMatcher) {
95   return anyOf(
96       unaryOperator(anyOf(hasOperatorName("--"), hasOperatorName("++")),
97                     hasUnaryOperand(ignoringParenImpCasts(
98                         declRefExpr(to(varDecl(VarNodeMatcher)))))),
99       binaryOperator(isAssignmentOperator(),
100                      hasLHS(ignoringParenImpCasts(
101                          declRefExpr(to(varDecl(VarNodeMatcher)))))));
102 }
103 
104 static internal::Matcher<Stmt>
105 callByRef(internal::Matcher<Decl> VarNodeMatcher) {
106   return callExpr(forEachArgumentWithParam(
107       declRefExpr(to(varDecl(VarNodeMatcher))),
108       parmVarDecl(hasType(references(qualType(unless(isConstQualified())))))));
109 }
110 
111 static internal::Matcher<Stmt>
112 assignedToRef(internal::Matcher<Decl> VarNodeMatcher) {
113   return declStmt(hasDescendant(varDecl(
114       allOf(hasType(referenceType()),
115             hasInitializer(anyOf(
116                 initListExpr(has(declRefExpr(to(varDecl(VarNodeMatcher))))),
117                 declRefExpr(to(varDecl(VarNodeMatcher)))))))));
118 }
119 
120 static internal::Matcher<Stmt>
121 getAddrTo(internal::Matcher<Decl> VarNodeMatcher) {
122   return unaryOperator(
123       hasOperatorName("&"),
124       hasUnaryOperand(declRefExpr(hasDeclaration(VarNodeMatcher))));
125 }
126 
127 static internal::Matcher<Stmt> hasSuspiciousStmt(StringRef NodeName) {
128   return hasDescendant(stmt(
129       anyOf(gotoStmt(), switchStmt(), returnStmt(),
130             // Escaping and not known mutation of the loop counter is handled
131             // by exclusion of assigning and address-of operators and
132             // pass-by-ref function calls on the loop counter from the body.
133             changeIntBoundNode(equalsBoundNode(NodeName)),
134             callByRef(equalsBoundNode(NodeName)),
135             getAddrTo(equalsBoundNode(NodeName)),
136             assignedToRef(equalsBoundNode(NodeName)))));
137 }
138 
139 static internal::Matcher<Stmt> forLoopMatcher() {
140   return forStmt(
141              hasCondition(simpleCondition("initVarName")),
142              // Initialization should match the form: 'int i = 6' or 'i = 42'.
143              hasLoopInit(
144                  anyOf(declStmt(hasSingleDecl(
145                            varDecl(allOf(hasInitializer(ignoringParenImpCasts(
146                                              integerLiteral().bind("initNum"))),
147                                          equalsBoundNode("initVarName"))))),
148                        binaryOperator(hasLHS(declRefExpr(to(varDecl(
149                                           equalsBoundNode("initVarName"))))),
150                                       hasRHS(ignoringParenImpCasts(
151                                           integerLiteral().bind("initNum")))))),
152              // Incrementation should be a simple increment or decrement
153              // operator call.
154              hasIncrement(unaryOperator(
155                  anyOf(hasOperatorName("++"), hasOperatorName("--")),
156                  hasUnaryOperand(declRefExpr(
157                      to(varDecl(allOf(equalsBoundNode("initVarName"),
158                                       hasType(isInteger())))))))),
159              unless(hasBody(hasSuspiciousStmt("initVarName")))).bind("forLoop");
160 }
161 
162 static bool isPossiblyEscaped(const VarDecl *VD, ExplodedNode *N) {
163   // Global variables assumed as escaped variables.
164   if (VD->hasGlobalStorage())
165     return true;
166 
167   while (!N->pred_empty()) {
168     // FIXME: getStmtForDiagnostics() does nasty things in order to provide
169     // a valid statement for body farms, do we need this behavior here?
170     const Stmt *S = N->getStmtForDiagnostics();
171     if (!S) {
172       N = N->getFirstPred();
173       continue;
174     }
175 
176     if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) {
177       for (const Decl *D : DS->decls()) {
178         // Once we reach the declaration of the VD we can return.
179         if (D->getCanonicalDecl() == VD)
180           return false;
181       }
182     }
183     // Check the usage of the pass-by-ref function calls and adress-of operator
184     // on VD and reference initialized by VD.
185     ASTContext &ASTCtx =
186         N->getLocationContext()->getAnalysisDeclContext()->getASTContext();
187     auto Match =
188         match(stmt(anyOf(callByRef(equalsNode(VD)), getAddrTo(equalsNode(VD)),
189                          assignedToRef(equalsNode(VD)))),
190               *S, ASTCtx);
191     if (!Match.empty())
192       return true;
193 
194     N = N->getFirstPred();
195   }
196   llvm_unreachable("Reached root without finding the declaration of VD");
197 }
198 
199 bool shouldCompletelyUnroll(const Stmt *LoopStmt, ASTContext &ASTCtx,
200                             ExplodedNode *Pred, unsigned &maxStep) {
201 
202   if (!isLoopStmt(LoopStmt))
203     return false;
204 
205   // TODO: Match the cases where the bound is not a concrete literal but an
206   // integer with known value
207   auto Matches = match(forLoopMatcher(), *LoopStmt, ASTCtx);
208   if (Matches.empty())
209     return false;
210 
211   auto CounterVar = Matches[0].getNodeAs<VarDecl>("initVarName");
212   llvm::APInt BoundNum =
213       Matches[0].getNodeAs<IntegerLiteral>("boundNum")->getValue();
214   llvm::APInt InitNum =
215       Matches[0].getNodeAs<IntegerLiteral>("initNum")->getValue();
216   auto CondOp = Matches[0].getNodeAs<BinaryOperator>("conditionOperator");
217   if (InitNum.getBitWidth() != BoundNum.getBitWidth()) {
218     InitNum = InitNum.zextOrSelf(BoundNum.getBitWidth());
219     BoundNum = BoundNum.zextOrSelf(InitNum.getBitWidth());
220   }
221 
222   if (CondOp->getOpcode() == BO_GE || CondOp->getOpcode() == BO_LE)
223     maxStep = (BoundNum - InitNum + 1).abs().getZExtValue();
224   else
225     maxStep = (BoundNum - InitNum).abs().getZExtValue();
226 
227   // Check if the counter of the loop is not escaped before.
228   return !isPossiblyEscaped(CounterVar->getCanonicalDecl(), Pred);
229 }
230 
231 bool madeNewBranch(ExplodedNode *N, const Stmt *LoopStmt) {
232   const Stmt *S = nullptr;
233   while (!N->pred_empty()) {
234     if (N->succ_size() > 1)
235       return true;
236 
237     ProgramPoint P = N->getLocation();
238     if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>())
239       S = BE->getBlock()->getTerminatorStmt();
240 
241     if (S == LoopStmt)
242       return false;
243 
244     N = N->getFirstPred();
245   }
246 
247   llvm_unreachable("Reached root without encountering the previous step");
248 }
249 
250 // updateLoopStack is called on every basic block, therefore it needs to be fast
251 ProgramStateRef updateLoopStack(const Stmt *LoopStmt, ASTContext &ASTCtx,
252                                 ExplodedNode *Pred, unsigned maxVisitOnPath) {
253   auto State = Pred->getState();
254   auto LCtx = Pred->getLocationContext();
255 
256   if (!isLoopStmt(LoopStmt))
257     return State;
258 
259   auto LS = State->get<LoopStack>();
260   if (!LS.isEmpty() && LoopStmt == LS.getHead().getLoopStmt() &&
261       LCtx == LS.getHead().getLocationContext()) {
262     if (LS.getHead().isUnrolled() && madeNewBranch(Pred, LoopStmt)) {
263       State = State->set<LoopStack>(LS.getTail());
264       State = State->add<LoopStack>(
265           LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
266     }
267     return State;
268   }
269   unsigned maxStep;
270   if (!shouldCompletelyUnroll(LoopStmt, ASTCtx, Pred, maxStep)) {
271     State = State->add<LoopStack>(
272         LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
273     return State;
274   }
275 
276   unsigned outerStep = (LS.isEmpty() ? 1 : LS.getHead().getMaxStep());
277 
278   unsigned innerMaxStep = maxStep * outerStep;
279   if (innerMaxStep > MAXIMUM_STEP_UNROLLED)
280     State = State->add<LoopStack>(
281         LoopState::getNormal(LoopStmt, LCtx, maxVisitOnPath));
282   else
283     State = State->add<LoopStack>(
284         LoopState::getUnrolled(LoopStmt, LCtx, innerMaxStep));
285   return State;
286 }
287 
288 bool isUnrolledState(ProgramStateRef State) {
289   auto LS = State->get<LoopStack>();
290   if (LS.isEmpty() || !LS.getHead().isUnrolled())
291     return false;
292   return true;
293 }
294 }
295 }
296