1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- llvm/Analysis/ScalarEvolutionNormalization.h - See below -*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file defines utilities for working with "normalized" ScalarEvolution 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// expressions. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The following example illustrates post-increment uses and how normalized 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// expressions help. 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// for (i=0; i!=n; ++i) { 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// ... 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// } 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// use(i); 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// While the expression for most uses of i inside the loop is {0,+,1}<%L>, the 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// expression for the use of i outside the loop is {1,+,1}<%L>, since i is 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// incremented at the end of the loop body. This is inconveient, since it 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// suggests that we need two different induction variables, one that starts 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// at 0 and one that starts at 1. We'd prefer to be able to think of these as 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// the same induction variable, with uses inside the loop using the 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// "pre-incremented" value, and uses after the loop using the 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// "post-incremented" value. 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// Expressions for post-incremented uses are represented as an expression 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// paired with a set of loops for which the expression is in "post-increment" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// mode (there may be multiple loops). 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_NORMALIZATION_H 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_ANALYSIS_SCALAREVOLUTION_NORMALIZATION_H 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallPtrSet.h" 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass Instruction; 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass DominatorTree; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass Loop; 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass ScalarEvolution; 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass SCEV; 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanclass Value; 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// TransformKind - Different types of transformations that 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// TransformForPostIncUse can do. 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanenum TransformKind { 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Normalize - Normalize according to the given loops. 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Normalize, 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// NormalizeAutodetect - Detect post-inc opportunities on new expressions, 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// update the given loop set, and normalize. 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NormalizeAutodetect, 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Denormalize - Perform the inverse transform on the expression with the 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// given loop set. 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Denormalize 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman}; 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// PostIncLoopSet - A set of loops. 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumantypedef SmallPtrSet<const Loop *, 2> PostIncLoopSet; 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// TransformForPostIncUse - Transform the given expression according to the 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// given transformation kind. 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanconst SCEV *TransformForPostIncUse(TransformKind Kind, 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SCEV *S, 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *User, 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *OperandValToReplace, 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PostIncLoopSet &Loops, 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScalarEvolution &SE, 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DominatorTree &DT); 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 79