/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp
Line | Count | Source |
1 | | //===- ScalarEvolutionNormalization.cpp - See below -----------------------===// |
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 implements utilities for working with "normalized" expressions. |
10 | | // See the comments at the top of ScalarEvolutionNormalization.h for details. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "llvm/Analysis/ScalarEvolutionNormalization.h" |
15 | | #include "llvm/Analysis/LoopInfo.h" |
16 | | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
17 | | using namespace llvm; |
18 | | |
19 | | /// TransformKind - Different types of transformations that |
20 | | /// TransformForPostIncUse can do. |
21 | | enum TransformKind { |
22 | | /// Normalize - Normalize according to the given loops. |
23 | | Normalize, |
24 | | /// Denormalize - Perform the inverse transform on the expression with the |
25 | | /// given loop set. |
26 | | Denormalize |
27 | | }; |
28 | | |
29 | | namespace { |
30 | | struct NormalizeDenormalizeRewriter |
31 | | : public SCEVRewriteVisitor<NormalizeDenormalizeRewriter> { |
32 | | const TransformKind Kind; |
33 | | |
34 | | // NB! Pred is a function_ref. Storing it here is okay only because |
35 | | // we're careful about the lifetime of NormalizeDenormalizeRewriter. |
36 | | const NormalizePredTy Pred; |
37 | | |
38 | | NormalizeDenormalizeRewriter(TransformKind Kind, NormalizePredTy Pred, |
39 | | ScalarEvolution &SE) |
40 | | : SCEVRewriteVisitor<NormalizeDenormalizeRewriter>(SE), Kind(Kind), |
41 | 2.44M | Pred(Pred) {} |
42 | | const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr); |
43 | | }; |
44 | | } // namespace |
45 | | |
46 | | const SCEV * |
47 | 2.38M | NormalizeDenormalizeRewriter::visitAddRecExpr(const SCEVAddRecExpr *AR) { |
48 | 2.38M | SmallVector<const SCEV *, 8> Operands; |
49 | 2.38M | |
50 | 2.38M | transform(AR->operands(), std::back_inserter(Operands), |
51 | 4.76M | [&](const SCEV *Op) { return visit(Op); }); |
52 | 2.38M | |
53 | 2.38M | if (!Pred(AR)) |
54 | 1.84M | return SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap); |
55 | 531k | |
56 | 531k | // Normalization and denormalization are fancy names for decrementing and |
57 | 531k | // incrementing a SCEV expression with respect to a set of loops. Since |
58 | 531k | // Pred(AR) has returned true, we know we need to normalize or denormalize AR |
59 | 531k | // with respect to its loop. |
60 | 531k | |
61 | 531k | if (Kind == Denormalize) { |
62 | 152k | // Denormalization / "partial increment" is essentially the same as \c |
63 | 152k | // SCEVAddRecExpr::getPostIncExpr. Here we use an explicit loop to make the |
64 | 152k | // symmetry with Normalization clear. |
65 | 304k | for (int i = 0, e = Operands.size() - 1; i < e; i++152k ) |
66 | 152k | Operands[i] = SE.getAddExpr(Operands[i], Operands[i + 1]); |
67 | 379k | } else { |
68 | 379k | assert(Kind == Normalize && "Only two possibilities!"); |
69 | 379k | |
70 | 379k | // Normalization / "partial decrement" is a bit more subtle. Since |
71 | 379k | // incrementing a SCEV expression (in general) changes the step of the SCEV |
72 | 379k | // expression as well, we cannot use the step of the current expression. |
73 | 379k | // Instead, we have to use the step of the very expression we're trying to |
74 | 379k | // compute! |
75 | 379k | // |
76 | 379k | // We solve the issue by recursively building up the result, starting from |
77 | 379k | // the "least significant" operand in the add recurrence: |
78 | 379k | // |
79 | 379k | // Base case: |
80 | 379k | // Single operand add recurrence. It's its own normalization. |
81 | 379k | // |
82 | 379k | // N-operand case: |
83 | 379k | // {S_{N-1},+,S_{N-2},+,...,+,S_0} = S |
84 | 379k | // |
85 | 379k | // Since the step recurrence of S is {S_{N-2},+,...,+,S_0}, we know its |
86 | 379k | // normalization by induction. We subtract the normalized step |
87 | 379k | // recurrence from S_{N-1} to get the normalization of S. |
88 | 379k | |
89 | 759k | for (int i = Operands.size() - 2; i >= 0; i--380k ) |
90 | 380k | Operands[i] = SE.getMinusSCEV(Operands[i], Operands[i + 1]); |
91 | 379k | } |
92 | 531k | |
93 | 531k | return SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap); |
94 | 531k | } |
95 | | |
96 | | const SCEV *llvm::normalizeForPostIncUse(const SCEV *S, |
97 | | const PostIncLoopSet &Loops, |
98 | 1.17M | ScalarEvolution &SE) { |
99 | 1.17M | auto Pred = [&](const SCEVAddRecExpr *AR) { |
100 | 1.17M | return Loops.count(AR->getLoop()); |
101 | 1.17M | }; |
102 | 1.17M | return NormalizeDenormalizeRewriter(Normalize, Pred, SE).visit(S); |
103 | 1.17M | } |
104 | | |
105 | | const SCEV *llvm::normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, |
106 | 599k | ScalarEvolution &SE) { |
107 | 599k | return NormalizeDenormalizeRewriter(Normalize, Pred, SE).visit(S); |
108 | 599k | } |
109 | | |
110 | | const SCEV *llvm::denormalizeForPostIncUse(const SCEV *S, |
111 | | const PostIncLoopSet &Loops, |
112 | 666k | ScalarEvolution &SE) { |
113 | 666k | auto Pred = [&](const SCEVAddRecExpr *AR) { |
114 | 565k | return Loops.count(AR->getLoop()); |
115 | 565k | }; |
116 | 666k | return NormalizeDenormalizeRewriter(Denormalize, Pred, SE).visit(S); |
117 | 666k | } |