136946Ssteve//===- llvm/Analysis/ScalarEvolutionNormalization.h - See below -*- C++ -*-===// 236946Ssteve// 336946Ssteve// The LLVM Compiler Infrastructure 436946Ssteve// 536946Ssteve// This file is distributed under the University of Illinois Open Source 636946Ssteve// License. See LICENSE.TXT for details. 736946Ssteve// 836946Ssteve//===----------------------------------------------------------------------===// 936946Ssteve// 1036946Ssteve// This file defines utilities for working with "normalized" ScalarEvolution 1136946Ssteve// expressions. 1236946Ssteve// 1336946Ssteve// The following example illustrates post-increment uses and how normalized 1436946Ssteve// expressions help. 1536946Ssteve// 1636946Ssteve// for (i=0; i!=n; ++i) { 1736946Ssteve// ... 1836946Ssteve// } 1936946Ssteve// use(i); 2036946Ssteve// 2136946Ssteve// While the expression for most uses of i inside the loop is {0,+,1}<%L>, the 2236946Ssteve// expression for the use of i outside the loop is {1,+,1}<%L>, since i is 2336946Ssteve// incremented at the end of the loop body. This is inconveient, since it 2436946Ssteve// suggests that we need two different induction variables, one that starts 2536946Ssteve// at 0 and one that starts at 1. We'd prefer to be able to think of these as 2636946Ssteve// the same induction variable, with uses inside the loop using the 2736946Ssteve// "pre-incremented" value, and uses after the loop using the 2836946Ssteve// "post-incremented" value. 2936946Ssteve// 3036946Ssteve// Expressions for post-incremented uses are represented as an expression 3136946Ssteve// paired with a set of loops for which the expression is in "post-increment" 3236946Ssteve// mode (there may be multiple loops). 3336946Ssteve// 3436946Ssteve//===----------------------------------------------------------------------===// 3536946Ssteve 3636946Ssteve#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONNORMALIZATION_H 3736946Ssteve#define LLVM_ANALYSIS_SCALAREVOLUTIONNORMALIZATION_H 3836946Ssteve 3936946Ssteve#include "llvm/ADT/SmallPtrSet.h" 4036946Ssteve 4136946Sstevenamespace llvm { 4236946Ssteve 4336946Ssteveclass Instruction; 4436946Ssteveclass DominatorTree; 4536946Ssteveclass Loop; 4636946Ssteveclass ScalarEvolution; 4736946Ssteveclass SCEV; 4836946Ssteveclass Value; 4936946Ssteve 5036946Ssteve/// TransformKind - Different types of transformations that 5136946Ssteve/// TransformForPostIncUse can do. 5236946Ssteveenum TransformKind { 5336946Ssteve /// Normalize - Normalize according to the given loops. 5436946Ssteve Normalize, 5536946Ssteve /// NormalizeAutodetect - Detect post-inc opportunities on new expressions, 5636946Ssteve /// update the given loop set, and normalize. 5736946Ssteve NormalizeAutodetect, 5836946Ssteve /// Denormalize - Perform the inverse transform on the expression with the 5936946Ssteve /// given loop set. 6036946Ssteve Denormalize 6136946Ssteve}; 6236946Ssteve 6336946Ssteve/// PostIncLoopSet - A set of loops. 6436946Sstevetypedef SmallPtrSet<const Loop *, 2> PostIncLoopSet; 6536946Ssteve 6636946Ssteve/// TransformForPostIncUse - Transform the given expression according to the 6736946Ssteve/// given transformation kind. 6836946Ssteveconst SCEV *TransformForPostIncUse(TransformKind Kind, 6936946Ssteve const SCEV *S, 7036946Ssteve Instruction *User, 7136946Ssteve Value *OperandValToReplace, 7236946Ssteve PostIncLoopSet &Loops, 7336946Ssteve ScalarEvolution &SE, 7436946Ssteve DominatorTree &DT); 7536946Ssteve 7636946Ssteve} 7736946Ssteve 7836946Ssteve#endif 7936946Ssteve