ScalarEvolutionExpander.h revision 0bba49cebc50c7bd4662a4807bcb3ee7f42cb470 
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
21namespace llvm {
22  /// SCEVExpander - This class uses information about analyze scalars to
23  /// rewrite expressions in canonical form.
24  ///
25  /// Clients should create an instance of this class when rewriting is needed,
26  /// and destroy it when finished to allow the release of the associated
27  /// memory.
28  struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
29    ScalarEvolution &SE;
30    std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> >
31      InsertedExpressions;
32    std::set<Value*> InsertedValues;
33
34    typedef IRBuilder<true, TargetFolder> BuilderType;
35    BuilderType Builder;
36
37    friend struct SCEVVisitor<SCEVExpander, Value*>;
38  public:
39    explicit SCEVExpander(ScalarEvolution &se)
40      : SE(se), Builder(TargetFolder(se.TD, se.getContext())) {}
41
42    /// clear - Erase the contents of the InsertedExpressions map so that users
43    /// trying to expand the same expression into multiple BasicBlocks or
44    /// different places within the same BasicBlock can do so.
45    void clear() { InsertedExpressions.clear(); }
46
47    /// getOrInsertCanonicalInductionVariable - This method returns the
48    /// canonical induction variable of the specified type for the specified
49    /// loop (inserting one if there is none).  A canonical induction variable
50    /// starts at zero and steps by one on each iteration.
51    Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty);
52
53    /// expandCodeFor - Insert code to directly compute the specified SCEV
54    /// expression into the program.  The inserted code is inserted into the
55    /// specified block.
56    Value *expandCodeFor(const SCEV *SH, const Type *Ty, Instruction *IP) {
57      Builder.SetInsertPoint(IP->getParent(), IP);
58      return expandCodeFor(SH, Ty);
59    }
60
61  private:
62    LLVMContext *getContext() const { return SE.getContext(); }
63
64    /// InsertBinop - Insert the specified binary operator, doing a small amount
65    /// of work to avoid inserting an obviously redundant operation.
66    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
67
68    /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
69    /// which must be possible with a noop cast, doing what we can to
70    /// share the casts.
71    Value *InsertNoopCastOfTo(Value *V, const Type *Ty);
72
73    /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP
74    /// instead of using ptrtoint+arithmetic+inttoptr.
75    Value *expandAddToGEP(const SCEV *const *op_begin,
76                          const SCEV *const *op_end,
77                          const PointerType *PTy, const Type *Ty, Value *V);
78
79    Value *expand(const SCEV *S);
80
81    /// expandCodeFor - Insert code to directly compute the specified SCEV
82    /// expression into the program.  The inserted code is inserted into the
83    /// SCEVExpander's current insertion point. If a type is specified, the
84    /// result will be expanded to have that type, with a cast if necessary.
85    Value *expandCodeFor(const SCEV *SH, const Type *Ty = 0);
86
87    /// isInsertedInstruction - Return true if the specified instruction was
88    /// inserted by the code rewriter.  If so, the client should not modify the
89    /// instruction.
90    bool isInsertedInstruction(Instruction *I) const {
91      return InsertedValues.count(I);
92    }
93
94    Value *visitConstant(const SCEVConstant *S) {
95      return S->getValue();
96    }
97
98    Value *visitTruncateExpr(const SCEVTruncateExpr *S);
99
100    Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
101
102    Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
103
104    Value *visitAddExpr(const SCEVAddExpr *S);
105
106    Value *visitMulExpr(const SCEVMulExpr *S);
107
108    Value *visitUDivExpr(const SCEVUDivExpr *S);
109
110    Value *visitAddRecExpr(const SCEVAddRecExpr *S);
111
112    Value *visitSMaxExpr(const SCEVSMaxExpr *S);
113
114    Value *visitUMaxExpr(const SCEVUMaxExpr *S);
115
116    Value *visitUnknown(const SCEVUnknown *S) {
117      return S->getValue();
118    }
119  };
120}
121
122#endif
123
124