LLVM  15.0.0git
ScalarEvolutionNormalization.cpp
Go to the documentation of this file.
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 
15 #include "llvm/Analysis/LoopInfo.h"
18 using namespace llvm;
19 
20 /// TransformKind - Different types of transformations that
21 /// TransformForPostIncUse can do.
23  /// Normalize - Normalize according to the given loops.
25  /// Denormalize - Perform the inverse transform on the expression with the
26  /// given loop set.
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)
42  Pred(Pred) {}
43  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr);
44 };
45 } // namespace
46 
47 const SCEV *
48 NormalizeDenormalizeRewriter::visitAddRecExpr(const SCEVAddRecExpr *AR) {
50 
51  transform(AR->operands(), std::back_inserter(Operands),
52  [&](const SCEV *Op) { return visit(Op); });
53 
54  if (!Pred(AR))
55  return SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap);
56 
57  // Normalization and denormalization are fancy names for decrementing and
58  // incrementing a SCEV expression with respect to a set of loops. Since
59  // Pred(AR) has returned true, we know we need to normalize or denormalize AR
60  // with respect to its loop.
61 
62  if (Kind == Denormalize) {
63  // Denormalization / "partial increment" is essentially the same as \c
64  // SCEVAddRecExpr::getPostIncExpr. Here we use an explicit loop to make the
65  // symmetry with Normalization clear.
66  for (int i = 0, e = Operands.size() - 1; i < e; i++)
67  Operands[i] = SE.getAddExpr(Operands[i], Operands[i + 1]);
68  } else {
69  assert(Kind == Normalize && "Only two possibilities!");
70 
71  // Normalization / "partial decrement" is a bit more subtle. Since
72  // incrementing a SCEV expression (in general) changes the step of the SCEV
73  // expression as well, we cannot use the step of the current expression.
74  // Instead, we have to use the step of the very expression we're trying to
75  // compute!
76  //
77  // We solve the issue by recursively building up the result, starting from
78  // the "least significant" operand in the add recurrence:
79  //
80  // Base case:
81  // Single operand add recurrence. It's its own normalization.
82  //
83  // N-operand case:
84  // {S_{N-1},+,S_{N-2},+,...,+,S_0} = S
85  //
86  // Since the step recurrence of S is {S_{N-2},+,...,+,S_0}, we know its
87  // normalization by induction. We subtract the normalized step
88  // recurrence from S_{N-1} to get the normalization of S.
89 
90  for (int i = Operands.size() - 2; i >= 0; i--)
91  Operands[i] = SE.getMinusSCEV(Operands[i], Operands[i + 1]);
92  }
93 
94  return SE.getAddRecExpr(Operands, AR->getLoop(), SCEV::FlagAnyWrap);
95 }
96 
98  const PostIncLoopSet &Loops,
99  ScalarEvolution &SE) {
100  auto Pred = [&](const SCEVAddRecExpr *AR) {
101  return Loops.count(AR->getLoop());
102  };
103  return NormalizeDenormalizeRewriter(Normalize, Pred, SE).visit(S);
104 }
105 
107  ScalarEvolution &SE) {
108  return NormalizeDenormalizeRewriter(Normalize, Pred, SE).visit(S);
109 }
110 
112  const PostIncLoopSet &Loops,
113  ScalarEvolution &SE) {
114  auto Pred = [&](const SCEVAddRecExpr *AR) {
115  return Loops.count(AR->getLoop());
116  };
117  return NormalizeDenormalizeRewriter(Denormalize, Pred, SE).visit(S);
118 }
i
i
Definition: README.txt:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
ScalarEvolutionNormalization.h
Denormalize
@ Denormalize
Denormalize - Perform the inverse transform on the expression with the given loop set.
Definition: ScalarEvolutionNormalization.cpp:27
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::denormalizeForPostIncUse
const SCEV * denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Denormalize S to be post-increment for all loops present in Loops.
Definition: ScalarEvolutionNormalization.cpp:111
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
ScalarEvolution.h
llvm::SmallPtrSet< const Loop *, 2 >
llvm::SCEVNAryExpr::operands
op_range operands() const
Definition: ScalarEvolutionExpressions.h:211
llvm::normalizeForPostIncUseIf
const SCEV * normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, ScalarEvolution &SE)
Normalize S for all add recurrence sub-expressions for which Pred returns true.
Definition: ScalarEvolutionNormalization.cpp:106
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
LoopInfo.h
Operands
mir Rename Register Operands
Definition: MIRNamerPass.cpp:74
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::SCEV::FlagAnyWrap
@ FlagAnyWrap
Definition: ScalarEvolution.h:131
llvm::SCEVRewriteVisitor
This visitor recursively visits a SCEV expression and re-writes it.
Definition: ScalarEvolutionExpressions.h:757
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Normalize
@ Normalize
Normalize - Normalize according to the given loops.
Definition: ScalarEvolutionNormalization.cpp:24
llvm::transform
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1711
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
TransformKind
TransformKind
TransformKind - Different types of transformations that TransformForPostIncUse can do.
Definition: ScalarEvolutionNormalization.cpp:22
llvm::SCEVAddRecExpr::getLoop
const Loop * getLoop() const
Definition: ScalarEvolutionExpressions.h:354
llvm::normalizeForPostIncUse
const SCEV * normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, ScalarEvolution &SE)
Normalize S to be post-increment for all loops present in Loops.
Definition: ScalarEvolutionNormalization.cpp:97
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:341
llvm::SCEVAddRecExpr
This node represents a polynomial recurrence on the trip count of the specified loop.
Definition: ScalarEvolutionExpressions.h:342
ScalarEvolutionExpressions.h