Coverage Report

Created: 2019-07-24 05:18

/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
}