1 //===- ScalarEvolutionNormalization.cpp - See below -----------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements utilities for working with "normalized" expressions.
11 // See the comments at the top of ScalarEvolutionNormalization.h for details.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/Analysis/LoopInfo.h"
16 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
17 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
18 using namespace llvm;
19 
20 /// TransformKind - Different types of transformations that
21 /// TransformForPostIncUse can do.
22 enum TransformKind {
23   /// Normalize - Normalize according to the given loops.
24   Normalize,
25   /// Denormalize - Perform the inverse transform on the expression with the
26   /// given loop set.
27   Denormalize
28 };
29 
30 namespace {
31 struct NormalizeDenormalizeRewriter
32     : public SCEVRewriteVisitor<NormalizeDenormalizeRewriter> {
33   const TransformKind Kind;
34 
35   // NB! Pred is a function_ref.  Storing it here is okay only because
36   // we're careful about the lifetime of NormalizeDenormalizeRewriter.
37   const NormalizePredTy Pred;
38 
39   NormalizeDenormalizeRewriter(TransformKind Kind, NormalizePredTy Pred,
40                                ScalarEvolution &SE)
41       : SCEVRewriteVisitor<NormalizeDenormalizeRewriter>(SE), Kind(Kind),
42         Pred(Pred) {}
43   const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr);
44 };
45 } // namespace
46 
47 const SCEV *
48 NormalizeDenormalizeRewriter::visitAddRecExpr(const SCEVAddRecExpr *AR) {
49   SmallVector<const SCEV *, 8> Operands;
50 
51   transform(AR->operands(), std::back_inserter(Operands),
52             [&](const SCEV *Op) { return visit(Op); });
53 
54   // Conservatively use AnyWrap until/unless we need FlagNW.
55   const SCEV *Result =
56       SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap);
57   switch (Kind) {
58   case Normalize:
59     // We want to normalize step expression, because otherwise we might not be
60     // able to denormalize to the original expression.
61     //
62     // Here is an example what will happen if we don't normalize step:
63     //  ORIGINAL ISE:
64     //    {(100 /u {1,+,1}<%bb16>),+,(100 /u {1,+,1}<%bb16>)}<%bb25>
65     //  NORMALIZED ISE:
66     //    {((-1 * (100 /u {1,+,1}<%bb16>)) + (100 /u {0,+,1}<%bb16>)),+,
67     //     (100 /u {0,+,1}<%bb16>)}<%bb25>
68     //  DENORMALIZED BACK ISE:
69     //    {((2 * (100 /u {1,+,1}<%bb16>)) + (-1 * (100 /u {2,+,1}<%bb16>))),+,
70     //     (100 /u {1,+,1}<%bb16>)}<%bb25>
71     //  Note that the initial value changes after normalization +
72     //  denormalization, which isn't correct.
73     if (Pred(AR)) {
74       const SCEV *TransformedStep = visit(AR->getStepRecurrence(SE));
75       Result = SE.getMinusSCEV(Result, TransformedStep);
76     }
77     break;
78   case Denormalize:
79     // Here we want to normalize step expressions for the same reasons, as
80     // stated above.
81     if (Pred(AR)) {
82       const SCEV *TransformedStep = visit(AR->getStepRecurrence(SE));
83       Result = SE.getAddExpr(Result, TransformedStep);
84     }
85     break;
86   }
87   return Result;
88 }
89 
90 const SCEV *llvm::normalizeForPostIncUse(const SCEV *S,
91                                          const PostIncLoopSet &Loops,
92                                          ScalarEvolution &SE) {
93   auto Pred = [&](const SCEVAddRecExpr *AR) {
94     return Loops.count(AR->getLoop());
95   };
96   return NormalizeDenormalizeRewriter(Normalize, Pred, SE).visit(S);
97 }
98 
99 const SCEV *llvm::normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred,
100                                            ScalarEvolution &SE) {
101   return NormalizeDenormalizeRewriter(Normalize, Pred, SE).visit(S);
102 }
103 
104 const SCEV *llvm::denormalizeForPostIncUse(const SCEV *S,
105                                            const PostIncLoopSet &Loops,
106                                            ScalarEvolution &SE) {
107   auto Pred = [&](const SCEVAddRecExpr *AR) {
108     return Loops.count(AR->getLoop());
109   };
110   return NormalizeDenormalizeRewriter(Denormalize, Pred, SE).visit(S);
111 }
112