ScalarEvolutionExpander.h revision 472fdf7090bb00af3a3f9dcbe22263120a527533 
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
84    /// setIVIncInsertPos - Set the current IV increment loop and position.
85    void setIVIncInsertPos(const Loop *L, Instruction *Pos) {
86      assert(!CanonicalMode &&
87             "IV increment positions are not supported in CanonicalMode");
88      IVIncInsertLoop = L;
89      IVIncInsertPos = Pos;
90    }
91
92    /// setPostInc - If L is non-null, enable post-inc expansion for addrecs
93    /// referring to the given loop. If L is null, disable post-inc expansion
94    /// completely. Post-inc expansion is only supported in non-canonical
95    /// mode.
96    void setPostInc(const Loop *L) {
97      assert(!CanonicalMode &&
98             "Post-inc expansion is not supported in CanonicalMode");
99      PostIncLoop = L;
100    }
101
102    /// disableCanonicalMode - Disable the behavior of expanding expressions in
103    /// canonical form rather than in a more literal form. Non-canonical mode
104    /// is useful for late optimization passes.
105    void disableCanonicalMode() { CanonicalMode = false; }
106
107    /// clearInsertPoint - Clear the current insertion point. This is useful
108    /// if the instruction that had been serving as the insertion point may
109    /// have been deleted.
110    void clearInsertPoint() {
111      Builder.ClearInsertionPoint();
112    }
113
114  private:
115    LLVMContext &getContext() const { return SE.getContext(); }
116
117    /// InsertBinop - Insert the specified binary operator, doing a small amount
118    /// of work to avoid inserting an obviously redundant operation.
119    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
120
121    /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
122    /// which must be possible with a noop cast, doing what we can to
123    /// share the casts.
124    Value *InsertNoopCastOfTo(Value *V, const Type *Ty);
125
126    /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP
127    /// instead of using ptrtoint+arithmetic+inttoptr.
128    Value *expandAddToGEP(const SCEV *const *op_begin,
129                          const SCEV *const *op_end,
130                          const PointerType *PTy, const Type *Ty, Value *V);
131
132    Value *expand(const SCEV *S);
133
134    /// expandCodeFor - Insert code to directly compute the specified SCEV
135    /// expression into the program.  The inserted code is inserted into the
136    /// SCEVExpander's current insertion point. If a type is specified, the
137    /// result will be expanded to have that type, with a cast if necessary.
138    Value *expandCodeFor(const SCEV *SH, const Type *Ty = 0);
139
140    /// isInsertedInstruction - Return true if the specified instruction was
141    /// inserted by the code rewriter.  If so, the client should not modify the
142    /// instruction.
143    bool isInsertedInstruction(Instruction *I) const {
144      return InsertedValues.count(I);
145    }
146
147    Value *visitConstant(const SCEVConstant *S) {
148      return S->getValue();
149    }
150
151    Value *visitTruncateExpr(const SCEVTruncateExpr *S);
152
153    Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
154
155    Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
156
157    Value *visitAddExpr(const SCEVAddExpr *S);
158
159    Value *visitMulExpr(const SCEVMulExpr *S);
160
161    Value *visitUDivExpr(const SCEVUDivExpr *S);
162
163    Value *visitAddRecExpr(const SCEVAddRecExpr *S);
164
165    Value *visitSMaxExpr(const SCEVSMaxExpr *S);
166
167    Value *visitUMaxExpr(const SCEVUMaxExpr *S);
168
169    Value *visitUnknown(const SCEVUnknown *S) {
170      return S->getValue();
171    }
172
173    void rememberInstruction(Value *I);
174
175    void restoreInsertPoint(BasicBlock *BB, BasicBlock::iterator I);
176
177    Value *expandAddRecExprLiterally(const SCEVAddRecExpr *);
178    PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
179                                       const Loop *L,
180                                       const Type *ExpandTy,
181                                       const Type *IntTy);
182  };
183}
184
185#endif
186