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