ScalarEvolutionExpander.h revision 9269926bfb713e92e328e9578c6d8826c68dcb9d 
1//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- 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 the classes used to generate code from scalar expressions.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
15#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
16
17#include "llvm/Analysis/ScalarEvolutionExpressions.h"
18#include "llvm/Support/IRBuilder.h"
19#include "llvm/Support/TargetFolder.h"
20#include <set>
21
22namespace llvm {
23  /// SCEVExpander - This class uses information about analyze scalars to
24  /// rewrite expressions in canonical form.
25  ///
26  /// Clients should create an instance of this class when rewriting is needed,
27  /// and destroy it when finished to allow the release of the associated
28  /// memory.
29  class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
30    ScalarEvolution &SE;
31    std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> >
32      InsertedExpressions;
33    std::set<Value*> InsertedValues;
34
35    /// PostIncLoop - When non-null, expanded addrecs referring to the given
36    /// loop expanded in post-inc mode. For example, expanding {1,+,1}<L> in
37    /// post-inc mode returns the add instruction that adds one to the phi
38    /// for {0,+,1}<L>, as opposed to a new phi starting at 1. This is only
39    /// supported in non-canonical mode.
40    const Loop *PostIncLoop;
41
42    /// IVIncInsertPos - When this is non-null, addrecs expanded in the
43    /// loop it indicates should be inserted with increments at
44    /// IVIncInsertPos.
45    const Loop *IVIncInsertLoop;
46
47    /// IVIncInsertPos - When expanding addrecs in the IVIncInsertLoop loop,
48    /// insert the IV increment at this position.
49    Instruction *IVIncInsertPos;
50
51    /// CanonicalMode - When true, expressions are expanded in "canonical"
52    /// form. In particular, addrecs are expanded as arithmetic based on
53    /// a canonical induction variable. When false, expression are expanded
54    /// in a more literal form.
55    bool CanonicalMode;
56
57    typedef IRBuilder<true, TargetFolder> BuilderType;
58    BuilderType Builder;
59
60    friend struct SCEVVisitor<SCEVExpander, Value*>;
61
62  public:
63    /// SCEVExpander - Construct a SCEVExpander in "canonical" mode.
64    explicit SCEVExpander(ScalarEvolution &se)
65      : SE(se), PostIncLoop(0), IVIncInsertLoop(0), CanonicalMode(true),
66        Builder(se.getContext(), TargetFolder(se.TD)) {}
67
68    /// clear - Erase the contents of the InsertedExpressions map so that users
69    /// trying to expand the same expression into multiple BasicBlocks or
70    /// different places within the same BasicBlock can do so.
71    void clear() { InsertedExpressions.clear(); }
72
73    /// getOrInsertCanonicalInductionVariable - This method returns the
74    /// canonical induction variable of the specified type for the specified
75    /// loop (inserting one if there is none).  A canonical induction variable
76    /// starts at zero and steps by one on each iteration.
77    Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty);
78
79    /// expandCodeFor - Insert code to directly compute the specified SCEV
80    /// expression into the program.  The inserted code is inserted into the
81    /// specified block.
82    Value *expandCodeFor(const SCEV *SH, const Type *Ty, Instruction *I) {
83      BasicBlock::iterator IP = I;
84      while (isInsertedInstruction(IP)) ++IP;
85      Builder.SetInsertPoint(IP->getParent(), IP);
86      return expandCodeFor(SH, Ty);
87    }
88
89    /// setIVIncInsertPos - Set the current IV increment loop and position.
90    void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
91      assert(!CanonicalMode &&
92             "IV increment positions are not supported in CanonicalMode");
93      IVIncInsertLoop = L;
94      IVIncInsertPos = Pos;
95    }
96
97    /// setPostInc - If L is non-null, enable post-inc expansion for addrecs
98    /// referring to the given loop. If L is null, disable post-inc expansion
99    /// completely. Post-inc expansion is only supported in non-canonical
100    /// mode.
101    void setPostInc(const Loop *L) {
102      assert(!CanonicalMode &&
103             "Post-inc expansion is not supported in CanonicalMode");
104      PostIncLoop = L;
105    }
106
107    /// disableCanonicalMode - Disable the behavior of expanding expressions in
108    /// canonical form rather than in a more literal form. Non-canonical mode
109    /// is useful for late optimization passes.
110    void disableCanonicalMode() { CanonicalMode = false; }
111
112  private:
113    LLVMContext &getContext() const { return SE.getContext(); }
114
115    /// InsertBinop - Insert the specified binary operator, doing a small amount
116    /// of work to avoid inserting an obviously redundant operation.
117    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
118
119    /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
120    /// which must be possible with a noop cast, doing what we can to
121    /// share the casts.
122    Value *InsertNoopCastOfTo(Value *V, const Type *Ty);
123
124    /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP
125    /// instead of using ptrtoint+arithmetic+inttoptr.
126    Value *expandAddToGEP(const SCEV *const *op_begin,
127                          const SCEV *const *op_end,
128                          const PointerType *PTy, const Type *Ty, Value *V);
129
130    Value *expand(const SCEV *S);
131
132    /// expandCodeFor - Insert code to directly compute the specified SCEV
133    /// expression into the program.  The inserted code is inserted into the
134    /// SCEVExpander's current insertion point. If a type is specified, the
135    /// result will be expanded to have that type, with a cast if necessary.
136    Value *expandCodeFor(const SCEV *SH, const Type *Ty = 0);
137
138    /// isInsertedInstruction - Return true if the specified instruction was
139    /// inserted by the code rewriter.  If so, the client should not modify the
140    /// instruction.
141    bool isInsertedInstruction(Instruction *I) const {
142      return InsertedValues.count(I);
143    }
144
145    Value *visitConstant(const SCEVConstant *S) {
146      return S->getValue();
147    }
148
149    Value *visitTruncateExpr(const SCEVTruncateExpr *S);
150
151    Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
152
153    Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
154
155    Value *visitAddExpr(const SCEVAddExpr *S);
156
157    Value *visitMulExpr(const SCEVMulExpr *S);
158
159    Value *visitUDivExpr(const SCEVUDivExpr *S);
160
161    Value *visitAddRecExpr(const SCEVAddRecExpr *S);
162
163    Value *visitSMaxExpr(const SCEVSMaxExpr *S);
164
165    Value *visitUMaxExpr(const SCEVUMaxExpr *S);
166
167    Value *visitUnknown(const SCEVUnknown *S) {
168      return S->getValue();
169    }
170
171    void rememberInstruction(Value *I) {
172      if (!PostIncLoop) InsertedValues.insert(I);
173    }
174
175    Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
176    PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
177                                       const Loop *L,
178                                       const Type *ExpandTy,
179                                       const Type *IntTy);
180  };
181}
182
183#endif
184