1 | //===- llvm/Analysis/ScalarEvolutionNormalization.h - See below -*- C++ -*-===// |
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 defines utilities for working with "normalized" ScalarEvolution |
10 | // expressions. |
11 | // |
12 | // The following example illustrates post-increment uses and how normalized |
13 | // expressions help. |
14 | // |
15 | // for (i=0; i!=n; ++i) { |
16 | // ... |
17 | // } |
18 | // use(i); |
19 | // |
20 | // While the expression for most uses of i inside the loop is {0,+,1}<%L>, the |
21 | // expression for the use of i outside the loop is {1,+,1}<%L>, since i is |
22 | // incremented at the end of the loop body. This is inconveient, since it |
23 | // suggests that we need two different induction variables, one that starts |
24 | // at 0 and one that starts at 1. We'd prefer to be able to think of these as |
25 | // the same induction variable, with uses inside the loop using the |
26 | // "pre-incremented" value, and uses after the loop using the |
27 | // "post-incremented" value. |
28 | // |
29 | // Expressions for post-incremented uses are represented as an expression |
30 | // paired with a set of loops for which the expression is in "post-increment" |
31 | // mode (there may be multiple loops). |
32 | // |
33 | //===----------------------------------------------------------------------===// |
34 | |
35 | #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONNORMALIZATION_H |
36 | #define LLVM_ANALYSIS_SCALAREVOLUTIONNORMALIZATION_H |
37 | |
38 | #include "llvm/ADT/STLFunctionalExtras.h" |
39 | #include "llvm/ADT/SmallPtrSet.h" |
40 | |
41 | namespace llvm { |
42 | |
43 | class Loop; |
44 | class ScalarEvolution; |
45 | class SCEV; |
46 | class SCEVAddRecExpr; |
47 | |
48 | typedef SmallPtrSet<const Loop *, 2> PostIncLoopSet; |
49 | |
50 | typedef function_ref<bool(const SCEVAddRecExpr *)> NormalizePredTy; |
51 | |
52 | /// Normalize \p S to be post-increment for all loops present in \p |
53 | /// Loops. Returns nullptr if the result is not invertible and \p |
54 | /// CheckInvertible is true. |
55 | const SCEV *normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, |
56 | ScalarEvolution &SE, |
57 | bool CheckInvertible = true); |
58 | |
59 | /// Normalize \p S for all add recurrence sub-expressions for which \p |
60 | /// Pred returns true. |
61 | const SCEV *normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, |
62 | ScalarEvolution &SE); |
63 | |
64 | /// Denormalize \p S to be post-increment for all loops present in \p |
65 | /// Loops. |
66 | const SCEV *denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, |
67 | ScalarEvolution &SE); |
68 | } // namespace llvm |
69 | |
70 | #endif |
71 | |