1448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//===- llvm/Analysis/ScalarEvolutionNormalization.h - See below -*- C++ -*-===//
2448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
3448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//                     The LLVM Compiler Infrastructure
4448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
5448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// This file is distributed under the University of Illinois Open Source
6448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// License. See LICENSE.TXT for details.
7448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
8448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//===----------------------------------------------------------------------===//
9448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
10448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// This file defines utilities for working with "normalized" ScalarEvolution
11448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// expressions.
12448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
13448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// The following example illustrates post-increment uses and how normalized
14448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// expressions help.
15448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
16448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//   for (i=0; i!=n; ++i) {
17448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//     ...
18448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//   }
19448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//   use(i);
20448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
21448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// While the expression for most uses of i inside the loop is {0,+,1}<%L>, the
22448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// expression for the use of i outside the loop is {1,+,1}<%L>, since i is
23448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// incremented at the end of the loop body. This is inconveient, since it
24448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// suggests that we need two different induction variables, one that starts
25448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// at 0 and one that starts at 1. We'd prefer to be able to think of these as
26448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// the same induction variable, with uses inside the loop using the
27448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// "pre-incremented" value, and uses after the loop using the
28448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// "post-incremented" value.
29448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
30448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// Expressions for post-incremented uses are represented as an expression
31448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// paired with a set of loops for which the expression is in "post-increment"
32448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman// mode (there may be multiple loops).
33448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//
34448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman//===----------------------------------------------------------------------===//
35448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
36674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONNORMALIZATION_H
37674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_SCALAREVOLUTIONNORMALIZATION_H
38448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
39448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman#include "llvm/ADT/SmallPtrSet.h"
40448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
41448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmannamespace llvm {
42448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
43448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanclass Instruction;
44448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanclass DominatorTree;
45448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanclass Loop;
46448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanclass ScalarEvolution;
47448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanclass SCEV;
48448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanclass Value;
49448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
50448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman/// TransformKind - Different types of transformations that
51448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman/// TransformForPostIncUse can do.
52448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanenum TransformKind {
53448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman  /// Normalize - Normalize according to the given loops.
54448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman  Normalize,
55448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman  /// NormalizeAutodetect - Detect post-inc opportunities on new expressions,
56448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman  /// update the given loop set, and normalize.
57448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman  NormalizeAutodetect,
58448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman  /// Denormalize - Perform the inverse transform on the expression with the
59448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman  /// given loop set.
60448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman  Denormalize
61448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman};
62448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
63448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman/// PostIncLoopSet - A set of loops.
64448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmantypedef SmallPtrSet<const Loop *, 2> PostIncLoopSet;
65448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
66448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman/// TransformForPostIncUse - Transform the given expression according to the
67448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman/// given transformation kind.
68448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohmanconst SCEV *TransformForPostIncUse(TransformKind Kind,
69448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman                                   const SCEV *S,
70448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman                                   Instruction *User,
71448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman                                   Value *OperandValToReplace,
72448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman                                   PostIncLoopSet &Loops,
73448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman                                   ScalarEvolution &SE,
74448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman                                   DominatorTree &DT);
75448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
76448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman}
77448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman
78448db1cdef5872713ef77beffacf502ae3450cd7Dan Gohman#endif
79