1 //===- ScalarEvolutionNormalization.cpp - See below -----------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file implements utilities for working with "normalized" expressions.
10 // See the comments at the top of ScalarEvolutionNormalization.h for details.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
15 #include "llvm/Analysis/LoopInfo.h"
16 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
19 /// TransformKind - Different types of transformations that
20 /// TransformForPostIncUse can do.
22 /// Normalize - Normalize according to the given loops.
24 /// Denormalize - Perform the inverse transform on the expression with the
30 struct NormalizeDenormalizeRewriter
31 : public SCEVRewriteVisitor<NormalizeDenormalizeRewriter> {
32 const TransformKind Kind;
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;
38 NormalizeDenormalizeRewriter(TransformKind Kind, NormalizePredTy Pred,
40 : SCEVRewriteVisitor<NormalizeDenormalizeRewriter>(SE), Kind(Kind),
42 const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr);
47 NormalizeDenormalizeRewriter::visitAddRecExpr(const SCEVAddRecExpr *AR) {
48 SmallVector<const SCEV *, 8> Operands;
50 transform(AR->operands(), std::back_inserter(Operands),
51 [&](const SCEV *Op) { return visit(Op); });
54 return SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap);
56 // Normalization and denormalization are fancy names for decrementing and
57 // incrementing a SCEV expression with respect to a set of loops. Since
58 // Pred(AR) has returned true, we know we need to normalize or denormalize AR
59 // with respect to its loop.
61 if (Kind == Denormalize) {
62 // Denormalization / "partial increment" is essentially the same as \c
63 // SCEVAddRecExpr::getPostIncExpr. Here we use an explicit loop to make the
64 // symmetry with Normalization clear.
65 for (int i = 0, e = Operands.size() - 1; i < e; i++)
66 Operands[i] = SE.getAddExpr(Operands[i], Operands[i + 1]);
68 assert(Kind == Normalize && "Only two possibilities!");
70 // Normalization / "partial decrement" is a bit more subtle. Since
71 // incrementing a SCEV expression (in general) changes the step of the SCEV
72 // expression as well, we cannot use the step of the current expression.
73 // Instead, we have to use the step of the very expression we're trying to
76 // We solve the issue by recursively building up the result, starting from
77 // the "least significant" operand in the add recurrence:
80 // Single operand add recurrence. It's its own normalization.
83 // {S_{N-1},+,S_{N-2},+,...,+,S_0} = S
85 // Since the step recurrence of S is {S_{N-2},+,...,+,S_0}, we know its
86 // normalization by induction. We subtract the normalized step
87 // recurrence from S_{N-1} to get the normalization of S.
89 for (int i = Operands.size() - 2; i >= 0; i--)
90 Operands[i] = SE.getMinusSCEV(Operands[i], Operands[i + 1]);
93 return SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap);
96 const SCEV *llvm::normalizeForPostIncUse(const SCEV *S,
97 const PostIncLoopSet &Loops,
98 ScalarEvolution &SE) {
99 auto Pred = [&](const SCEVAddRecExpr *AR) {
100 return Loops.count(AR->getLoop());
102 return NormalizeDenormalizeRewriter(Normalize, Pred, SE).visit(S);
105 const SCEV *llvm::normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred,
106 ScalarEvolution &SE) {
107 return NormalizeDenormalizeRewriter(Normalize, Pred, SE).visit(S);
110 const SCEV *llvm::denormalizeForPostIncUse(const SCEV *S,
111 const PostIncLoopSet &Loops,
112 ScalarEvolution &SE) {
113 auto Pred = [&](const SCEVAddRecExpr *AR) {
114 return Loops.count(AR->getLoop());
116 return NormalizeDenormalizeRewriter(Denormalize, Pred, SE).visit(S);