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/STLExtras.h" 39#include "llvm/ADT/SmallPtrSet.h" 40 41namespace llvm { 42 43class Loop; 44class ScalarEvolution; 45class SCEV; 46class SCEVAddRecExpr; 47 48typedef SmallPtrSet<const Loop *, 2> PostIncLoopSet; 49 50typedef function_ref<bool(const SCEVAddRecExpr *)> NormalizePredTy; 51 52/// Normalize \p S to be post-increment for all loops present in \p 53/// Loops. 54const SCEV *normalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, 55 ScalarEvolution &SE); 56 57/// Normalize \p S for all add recurrence sub-expressions for which \p 58/// Pred returns true. 59const SCEV *normalizeForPostIncUseIf(const SCEV *S, NormalizePredTy Pred, 60 ScalarEvolution &SE); 61 62/// Denormalize \p S to be post-increment for all loops present in \p 63/// Loops. 64const SCEV *denormalizeForPostIncUse(const SCEV *S, const PostIncLoopSet &Loops, 65 ScalarEvolution &SE); 66} // namespace llvm 67 68#endif 69