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