contrib/llvm/lib/Analysis/ScalarEvolutionNormalization.cpp

   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 }