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